💻 computer science

Misquoted No More: Securely Extracting F* Programs with IO

Dit artikel introduceert SEIO*, een framework dat relationele citatie combineert met geverifieerde syntaxisgeneratie om veilig ondiep ingebedde F*-programma's met I/O en verfijningstypen te extraheren naar een diep ingebed calculus, waarbij machine-gecontroleerde bewijzen van Robust Relational Hyperproperty Preservation (RrHP) worden geleverd om beveiliging tegen willekeurige adversariële koppeling te garanderen.

Oorspronkelijke auteurs: Cezar-Constantin Andrici, Abigail Pribisova, Danel Ahman, Catalin Hritcu, Exequiel Rivas, Théo Winterhalter

Gepubliceerd 2026-07-20

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Cezar-Constantin Andrici, Abigail Pribisova, Danel Ahman, Catalin Hritcu, Exequiel Rivas, Théo Winterhalter

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Onzichtbare Veiligheidsnet

Stel je voor dat je een meesterarchitect bent die een prachtige, zelfrijdende auto heeft ontworpen in een perfect, denkbeeldige wereld waar de natuurkunde zich altijd precies gedraagt zoals jij het voorspelt. Je hebt de blauwdrukken geschreven in een speciale, superprecieze taal waarmee je wiskundig kunt bewijzen dat de auto nooit zal crashen, nooit zal remmen wanneer dat niet moet, en altijd de verkeersregels zal volgen. Dit is wat computerwetenschappers "formele verificatie" noemen. Het is alsof je een auto bouwt in een droom waarin je 100% zeker bent van elke bout en draad.

Maar hier komt de adder onder het gras: die droomwereld bestaat niet op de echte weg. Om de auto daadwerkelijk te laten rijden, moet je je perfecte blauwdrukken vertalen naar een taal die echte motoren en banden begrijpen, zoals C of OCaml. Dit vertaalproces wordt "extractie" genoemd. Het probleem is dat de vertaler (het computerprogramma dat de conversie uitvoert) niet perfect is. Het kan een bout laten vallen, een draad verdraaien of een regel verkeerd begrijpen. Als de auto in de echte wereld gebouwd is op een fout die tijdens de vertaling is gemaakt, is je perfecte bewijs van veiligheid nutteloos. De auto ziet er op papier misschien veilig uit, maar crasht in de werkelijkheid.

Jarenlang hebben wetenschappers geprobeerd dit op te lossen door het werk van de vertaler achteraf te controleren, een beetje zoals een monteur die een auto inspecteert nadat deze is gebouwd om te zien of deze overeenkomt met de plannen. Maar dit artikel introduceert een slimmere manier: in plaats van alleen de afgewerkte auto te controleren, bouwen ze tijdens de vertaling een "veiligheidscertificaat" dat wiskundig bewijst dat de echte auto een perfecte tweeling is van de droomauto, zelfs als de vertaler een fout maakt. Ze noemen dit een "secure extraction" framework, en het is ontworpen om je digitale creaties veilig te houden, zelfs wanneer ze worden gemengd met de rommelige, ongeverifieerde code van de buitenwereld.

Het Grote Idee van het Papier: De "Relational Quotation" Magische Truk

De auteurs van dit artikel, een team van computerwetenschappers, hebben een nieuw framework gebouwd genaamd SEIO★ (Secure Extraction of IO-star). Hun doel was om het "vertaalprobleem" op te lossen voor programma's geschreven in F★, een taal die wordt gebruikt voor het schrijven van zeer beveiligde software zoals cryptografische tools. Deze F★-programma's zijn vaak "shallowly embedded", wat een chique manier is om te zeggen dat ze in een hoogwaardige, abstracte stijl zijn geschreven die geweldig is voor het bewijzen van zaken, maar moeilijk door computers om te zetten in echte code.

Normaal gesproken, wanneer je deze abstracte programma's omzet in echte code, moet je een "metaprogram" (een programma dat andere programma's schrijft) gebruiken om het zware werk te doen. De oude manier van doen was riskant: het metaprogram zou de nieuwe code schrijven en vervolgens proberen een bewijs te schrijven dat de nieuwe code correct is. Als het bewijs faalde, moest je opnieuw beginnen. Als het bewijs slaagde, moest je nog steeds erop vertrouwen dat het metaprogram geen bug had binnengesmokkeld terwijl het het bewijs schreef. Het was alsof je een leerling vroeg om zijn eigen huiswerk te nakijken en hoopte dat hij niet had gesjoemeld.

De doorbraak van de auteurs is een techniek die ze Relational Quotation noemen. In plaats van het metaprogram te vragen om de definitieve code en het bewijs te schrijven, vragen ze het om iets veel simpelers te doen: een typing derivation schrijven. Denk aan dit als een stapsgewijze receptenkaart die zegt: "Stap 1: Neem dit ingrediënt. Stap 2: Meng het met dat." Deze receptenkaart kookt het gerecht niet echt; het bewijst alleen dat de ingrediënten in een specifiek gerecht gekookt zouden kunnen worden.

Hier is het slimme deel:

Het Metaprogram (De Receptenschrijver): Het ongeverifieerde metaprogram kijkt naar het oorspronkelijke abstracte programma en genereert deze "receptenkaart" (de typing derivation). Omdat de receptenkaart exact de structuur van het oorspronkelijke programma volgt, is het heel eenvoudig om dit te schrijven.
De Controle (De Inspecteur): De F★-taal zelf controleert deze receptenkaart. De taal vraagt: "Beschrijft dit recept daadwerkelijk het oorspronkelijke programma?" Als het metaprogram een fout heeft gemaakt en een recept voor een taart heeft geschreven terwijl het oorspronkelijke een soep was, faalt de controle. Maar als het recept overeenkomt, is de F★-taal 100% zeker dat het recept geldig is.
De Geverifieerde Stap (De Meesterkok): Zodra de receptenkaart is geverifieerd, neemt een andere, volledig geverifieerde functie (een "Meesterkok" die wiskundig bewezen perfect is) dat recept en kookt het definitieve gerecht (de echte code). Omdat het is bewezen dat het recept overeenkomt met het origineel, en de kok bewezen exact kookt zoals het recept voorschrijft, is het definitieve gerecht gegarandeerd een perfecte tweeling van het origineel.

Deze aanpak minimaliseert de "vertrouwen" die we aan het ongeverifieerde metaprogram moeten schenken. We vertrouwen het alleen om het recept te schrijven, niet om het eten te koken of het huiswerk te nakijken. Het moeilijke deel — bewijzen dat het eten veilig is — wordt gedaan door de geverifieerde Meesterkok.

De "Secure Compilation" Superkracht

Het artikel gaat verder dan alleen controleren of de code correct is; het gaat een stap verder om te garanderen dat de code ook veilig is. In de echte wereld kan je geverifieerde programma gekoppeld worden aan andere code die niet geverifieerd is — misschien code geschreven door een hacker, of gewoon slordige code van een ander team. Deze "adversariële" code probeert de regels van jouw programma te brezen.

De auteurs bewijzen dat hun SEIO★-framework voldoet aan een supersterke beveiligingsregel genaamd Robust Relational Hyperproperty Preservation (RrHP). Om dit te begrijpen, stel je voor dat je geverifieerde programma een fort is.

Oude methoden zouden zeggen: "De muren van het fort zijn sterk, dus het is veilig."
Dit artikel zegt: "Zelfs als een hacker probeert via de achterdeur binnen te sluipen, of als ze proberen de bewakers te misleiden, of als ze proberen de regels van het spel te veranderen, zal jouw fort nog steeds zich precies zo gedragen als jij hebt ontworpen."

Ze bewijzen dit met behulp van twee "logische relaties", die werken als spiegels aan beide kanten. Eén spiegel controleert of de echte code alles doet wat de abstracte code zou kunnen doen. De andere spiegel controleert of de echte code niet doet wat de abstracte code niet zou kunnen doen. Door beide te bewijzen, laten ze zien dat de echte code een perfecte, veilige schaduw is van het origineel, ongeacht met welke rommelige code het gekoppeld wordt.

Wat Ze Daadwerkelijk Hebben Gedaan (en Niet)

Het team heeft dit framework volledig binnen de F★-taal gebouwd en een computer gebruikt om elke stap van hun bewijs te controleren. Ze hebben niet alleen geraden of gesimuleerd; ze hebben het wiskundig bewezen.

Wat werkt: Ze zijn erin geslaagd programma's te extraheren die bestand Input/Output (I/O) afhandelen (het lezen en schrijven van bestanden) en gebruikmaken van "refinement types" (typen met extra regels, zoals "dit getal moet positief zijn"). Ze hebben aangetoond dat de extractie zelfs met deze complexe functies veilig blijft.
Wat nog een werk in uitvoering is: Het artikel geeft toe dat hun huidige systeem niet op de meest natuurlijke manier omgaat met recursieve functies (functies die zichzelf aanroepen) of volledige "dependent types" (waarbij types afhankelijk zijn van waarden). Ze moesten een workaround gebruiken met iteratoren (lussen) voor recursie. Ze merken ook op dat hun metaprogram soms moet raden waar bepaalde veiligheidscontroles geplaatst moeten worden, wat een beetje onhandig kan zijn.
De Conclusie: Ze hebben niet elk probleem in het universum van programmeren opgelost, maar ze hebben een nieuwe, veel veiligere brug gebouwd tussen de wereld van perfecte bewijzen en de rommelige wereld van echte code. Ze hebben bewezen dat door de taak te splitsen in een "fase van receptschrijven" en een "fase van koken", je sterke beveiligingsgaranties krijgt zonder het receptschrijver volledig te hoeven vertrouwen.

Kortom, SEIO★ is een nieuw hulpmiddel dat programmeurs in staat stelt om hun perfecte, geverifieerde ideeën om te zetten in echte software met een wiskundig gegarandeerd veiligheidsnet, waardoor wordt gewaarborgd dat zelfs als het vertaalproces imperfect is, het eindresultaat nog steeds veilig is voor de chaos van de buitenwereld.

Technische Samenvatting: Misquoted No More: Securely Extracting F★Programs with IO

1. Probleemstelling

De bewijsgerichte taal F★ wordt breed gebruikt voor het schrijven en verifiëren van programma's die shallowly embedded zijn met behulp van monaden om effecten (bijv. I/O) te representeren. Eenmaal geverifieerd, worden deze programma's doorgaans geëxtraheerd naar mainstream talen zoals OCaml of C voor uitvoering. Dit extractieproces is echter momenteel ongeverifieerd en vormt onderdeel van de trusted computing base (TCB).

De kernuitdaging ligt in de "quotation"-stap die vereist is voor het extraheren van shallowly embedded programma's. Quotation houdt in dat een shallowly embedded programma (waarbij effecten worden gerepresenteerd door monadische types) wordt vertaald naar een deeply embedded syntactische boom (een concrete representatie van de doeltaal). Het verifiëren van deze quotation-metaprogram is een grote openstaande uitdaging, omdat het een gemachiniseerde meta-theorie voor de brontaal vereist, en zelfs voor volwassen systemen zoals Rocq blijft het verifiëren van quotation onopgelost.

Eerdere benaderingen voor het certificeren van extractie vertrouwen zwaar op translation validation, waarbij een metaprogram zowel de geëxtraheerde code als een bewijs van correctheid genereert, dat vervolgens type-gecheckt wordt. Hoewel dit de TCB vermindert vergeleken met het verifiëren van het metaprogram zelf, vertrouwt het nog steeds op het metaprogram om geldige bewijzen te genereren, wat kan falen of incorrect kan zijn. Bovendien richt bestaand werk zich primair op correctheid (het behoud van functioneel gedrag) in plaats van op beveiliging. Wanneer geëxtraheerde code wordt gelinkt met ongeverifieerde adversariële code, kunnen de formele garanties van het oorspronkelijke geverifieerde programma in gevaar komen, wat leidt tot unsoundness of beveiligingsschendingen.

2. Methodologie

De auteurs introduceren SEIO★, een framework voor het extraheren van shallowly embedded F★-programma's met I/O en refinement types naar een deeply embedded simply typed $\lambda$ -calculus ( $\lambda_{io}$ ). De methodologie splitst het extractieproces in twee afzonderlijke fasen om de afhankelijkheid van translation validation te minimaliseren:

Fase 1: Relational Quotation (Translation Validation)
In plaats van direct de doelcode te genereren, gebruikt het framework een metaprogram om een typing derivation (typeringafleiding) te generen voor het oorspronkelijke shallowly embedded programma.

Relational Typing Relation: De auteurs definiëren een typing relatie die de subset van F★ (genoemd IO★) die geëxtraheerd wordt, karakteriseert. Deze relatie opereert op "open F★ waarden" (functies van evaluatie-omgevingen naar waarden) in plaats van op syntactische expressies, waardoor het vrije variabelen in een shallow embedding kan afhandelen.
Metaprogram: Een eenvoudig metaprogram doorloopt de structuur van het bronprogramma en construeert een overeenkomstige typing derivation.
Validatie: De gegenereerde afleiding wordt door F★ type-gecheckt. Omdat de typing relatie afhankelijk van types (dependent types) is, verifieert de type-checker dat de afleiding syntactisch en semantisch overeenkomt met het oorspronkelijke programma. Deze stap is het enige deel dat steunt op translation validation.

Fase 2: Verified Syntax Generation
Zodra een geldige typing derivation is verkregen, genereert een pure, geverifieerde F★ functie recursief de doel- $\lambda_{io}$ syntaxis.

Omdat de typing derivation structureel verbonden is met het bronprogramma via dependent types, is de syntax generatie functie gegarandeerd om code te produceren die semantisch gerelateerd is aan het origineel.
Deze stap is volledig geverifieerd binnen F★, waardoor de noodzaak voor translation validation in de code generatie fase wordt geëlimineerd.

Beveiligingsgaranties via Logical Relations
Om beveiliging te bewijzen, definiëren de auteurs twee cross-language logical relations tussen de bron (IO★) en doel ( $\lambda_{io}$ ) talen:

Target-to-Source: Relateert een doelprogramma aan een bronprogramma, wat garandeert dat elke doelgedraging een overeenkomstige brongedraging heeft.
Source-to-Target: Relateert een bronprogramma aan een doelprogramma, wat garandeert dat elke brongedraging een overeenkomstige doelgedraging heeft.

Deze relaties zijn gedefinieerd over trace-producing semantics, waarbij I/O-operaties gebeurtenissen (traces) genereren. De auteurs bewijzen dat SEIO★ voldoet aan Robust Relational Hyperproperty Preservation (RrHP), de sterkste veilige compilatie-criteria gedefinieerd door Abate et al. [1]. RrHP impliceert full abstraction (behoud van observationele equivalentie) en het behoud van trace-eigenschappen en hyperproperties (bijv. noninterference) tegen willekeurige adversariële contexten.

Afhandeling van Refinement Types
Het framework wordt uitgebreid om ondersteuning te bieden voor refinement types (logische restricties op types). Aangezien F★ refinement bewijzen afhandelt met behulp van SMT-solvers zonder expliciete bewijs-termen te produceren, moet de relationele quotation metaprogram de zwakste preconditionen (weakest preconditions) vanaf nul opnieuw berekenen tijdens de quotation en deze opnieuw bewijzen om te garanderen dat de typing derivation geldig blijft.

3. Belangrijkste Bijdragen

Relational Quotation: Een nieuwe translation validation techniek die gebruik maakt van dependent types om een typing relatie voor shallowly embedded programma's te definiëren. Het stelt een metaprogram in staat om een typing derivation te genereren die type-gecheckt wordt om te waarborgen dat deze overeenkomt met het bronprogramma, waardoor de noodzaak om het metaprogram zelf te verifiëren wordt vermeden.
SEIO★ Framework: Een compleet extractie framework voor F★-programma's met I/O en refinement types, die ze extraheert naar een deeply embedded $\lambda$ -calculus.
Formele Veilige Compilatie: Een machine-gecontroleerd bewijs in F★ dat SEIO★ voldoet aan RrHP. Dit is het eerste extractie framework voor een bewijsgerichte taal dat dergelijke sterke beveiligingsgaranties biedt tegen willekeurige gelinkte adversariële code.
Cross-Language Logical Relations: De definitie en het bewijs van twee asymmetrische logical relations die de kloof overbruggen tussen een shallowly embedded taal met trace-producing semantics en een deeply embedded taal met standaard operationele semantics.
Refinement Type Support: Een uitbreiding van het framework om refinement types te behandelen door de preconditionen tijdens de quotation opnieuw te berekenen en te herverifiëren.

4. Resultaten

De auteurs hebben SEIO★ geïmplementeerd in F★, inclus\nuit meer dan 900 top-level definities.
Ze hebben succesvol een draaiend voorbeeld geëxtraheerd: een validatie-wrapper voor ongeverifieerde AI-agents die een bestand leest, een agent aanroept en het resultaat verifieert.
Het framework is getest met diverse agents (zowel correcte als kwaadwillende) geschreven in de doel- $\lambda_{io}$ taal.
Het machine-gecontroleerde bewijs bevestigt dat de extractie veiligheidseigenschappen behoudt, zelfs wanneer deze gelinkt wordt met willekeurige ongeverifieerde code, waarmee aan RrHP wordt voldaan.
Het artefact bevat een pipeline om de geëxtraheerde $\lambda_{io}$ code te compileren naar OCaml met behulp van het Peregrine framework en Malfunction, wat praktische uitvoering mogelijk maakt.

5. Betekenis en Claims

Het artikel beweert het staats van de kunst op twee belangrijke manieren vooruit te helpen:

Minimaliseren van Translation Validation: Door translation validation te beperken tot de generatie van een typing derivation (relational quotation) en de daaropvolgende syntax generatie stap te verifiëren, vermindert het framework de afhankelijkheid van ongeverifieerde metaprogrammen vergeleken met eerder werk op het gebied van certifying extraction.
Beveiliging boven Correctheid: In tegen tegenstelling tot eerder werk dat zich richtte op functionele correctheid, biedt SEIO★ formele veilige compilatiegaranties. Het zorgt ervoor dat geverifieerde F★-programma's hun beveiligingseigenschappen (zoals noninterference en trace-eigenschappen) behouden, zelfs wanneer ze gelinkt worden met willekeurige, ongeverifieerde of adversariële code.

De auteurs merken op dat dit werk verder gaat dan de huidige stand van de techniek, die nog geen dergelijke sterke veilige compilatiegaranties heeft geboden voor extractie uit bewijsgerichte talen. Zij erkennen beperkingen, zoals de huidige afwezigheid van ondersteuning voor algemene recursieve functies en volledige dependent types, die als toekomstig werk worden beschouwd. Het artikel benadrukt dat hoewel de relationele quotation metaprogram ongeverifieerd is, de eenvoud ervan en de rigoureuze verificatie van de daaropvolgende stappen het algemene proces robuust maken.