💻 computer science

Contextual Refinement of Higher-Order Concurrent Probabilistic Programs (Extended Version)

Dit paper introduceert Foxtrot, de eerste hogere-orde scheidingslogica die mechanisch is geverifieerd in Rocq en die contextuele verfijning bewijst voor hogere-orde concurrerende probabilistische programma's met hogere-orde lokale staat door geavanceerde principes voor concurrentie en waarschijnlijkheid te integreren.

Oorspronkelijke auteurs: Kwing Hei Li, Alejandro Aguirre, Joseph Tassarotti, Lars Birkedal

Gepubliceerd 2026-04-20

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Kwing Hei Li, Alejandro Aguirre, Joseph Tassarotti, Lars Birkedal

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

Stel je voor dat je twee verschillende recepten hebt voor het bakken van een taart. Het ene recept is heel simpel: "Meng bloem, suiker en eieren." Het andere recept is veel ingewikkelder: "Laat drie vrienden tegelijkertijd eieren breken, terwijl een vierde vriend een willekeurig aantal suikerklontjes toevoegt, en zorg dat ze allemaal samenwerken zonder elkaar te blokkeren."

Het grote vraagstuk in de programmeerwereld is: Hoe weet je zeker dat die twee recepten uiteindelijk precies dezelfde taart opleveren?

In de wereld van computers zijn er twee dingen die dit heel moeilijk maken:

Toeval (Probabiliteit): Net als bij het gooien van een dobbelsteen, kan het resultaat elke keer anders zijn.
Tegelijkertijd (Concurrentie): Net als in een drukke keuken waar meerdere koks tegelijk aan het werk zijn, kunnen dingen in willekeurige volgorde gebeuren.

Deze paper introduceert Foxtrot, een nieuw en slim "receptboek" (een wiskundig bewijsstelsel) dat helpt om te bewijzen dat een ingewikkeld programma (zoals de drukke keuken) veilig vervangen kan worden door een simpeler, ideaal programma (zoals het simpele recept), zelfs als er toeval en chaos bij komen kijken.

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De Grote Uitdaging: Chaos en Toeval

Vroeger hadden we gereedschappen om te bewijzen dat programma's goed werken als ze lineair werken (één ding na het andere) of als ze alleen maar toeval gebruiken. Maar als je toeval en meerdere taken tegelijk combineert, wordt het een ware chaos.

Stel je voor dat je twee mensen hebt die elk een willekeurig getal kiezen.

Programma A: Laat twee mensen tegelijk een getal kiezen en telt ze bij elkaar op.
Programma B: Laat één persoon direct het totaal kiezen.

Wiskundig gezien is het resultaat van A en B hetzelfde. Maar hoe bewijs je dat? Als de twee mensen in Programma A op een rare manier samenwerken (of als de "chef" die bepaalt wie wanneer werkt, een slechte keuze maakt), kan het resultaat anders lijken. Foxtrot is het eerste gereedschap dat dit soort bewijzen kan leveren voor complexe, moderne software.

2. De Magische Tricks van Foxtrot

Foxtrot gebruikt drie slimme trucjes (analogieën) om dit bewijs te leveren:

A. De "Vooruitblikkende Lijst" (Presampling Tapes)

Stel je voor dat je een spelletje speelt waarbij je dobbelstenen gooit. Normaal gesproken gooi je de steen en zie je pas het resultaat.
Foxtrot gebruikt een trucje waarbij we in het bewijs alleen een lijstje maken met wat er zou kunnen vallen, voordat we überhaupt beginnen.

Hoe het werkt: We zeggen: "Oké, we hebben een lijstje met alle mogelijke uitkomsten voor de eerste persoon en de tweede persoon." Vervolgens bewijzen we dat deze lijstjes precies overeenkomen met wat de simpele versie (Programma B) zou doen.
De beperking: Je mag dit lijstje alleen aan de kant van het ingewikkelde programma gebruiken. Je mag het niet gebruiken om de simpele versie te "bedriegen" door vooruit te kijken. Dat zou de logica verstoren.

B. De "Gebroken Koppeling" (Fragmented Couplings)

Soms wil je twee dingen koppelen, maar lukt dat niet in één keer.
Stel je voor dat je een slechte dobbelsteen hebt die vaak "6" gooit, en je wilt bewijzen dat je toch een eerlijke worp krijgt. Je gooit de steen, en als het een 6 is, gooi je opnieuw.

De truc: Foxtrot zegt: "Laten we de gooi splitsen. Als het een goede worp is, koppelen we die direct aan de eerlijke versie. Als het een slechte worp is, laten we die 'weg' en proberen we het opnieuw."
Dit heet "rejection sampling" (verwerpingssteekproef). Foxtrot kan bewijzen dat, zelfs als je vaak moet herhalen, het eindresultaat toch eerlijk is.

C. De "Foutenmunt" (Error Credits)

Soms is het bewijs niet 100% perfect in één stap, maar wel bijna.
Stel je voor dat je een schatting maakt en je hebt een "foutenmunt" van €0,01. Als je bewijst dat je fouten kleiner zijn dan die munt, en je kunt die munt steeds kleiner maken (naar €0,0001, €0,000001...), dan is het bewijs uiteindelijk perfect.
Foxtrot gebruikt deze "muntjes" om te zeggen: "We weten dat het niet 100% perfect is in deze stap, maar we kunnen de fout zo klein maken dat hij verdwijnt."

3. Waarom is dit belangrijk?

De auteurs hebben dit allemaal gebouwd in een digitaal bewijsprogramma (een soort super-rekenmachine voor logica) genaamd Rocq. Ze hebben getest met echte, moeilijke voorbeelden:

Cryptografie: Ze hebben bewezen dat een functie in de beroemde beveiligingsbibliotheek Sodium (die gebruikt wordt om wachtwoorden en berichten te versleutelen) veilig is, zelfs als er veel mensen tegelijkertijd proberen de code te hacken of te manipuleren.
Vondsten: Ze hebben bewezen dat zelfs als een hacker probeert de volgorde van de taken te verstoren, het eindresultaat van een "eerlijke munt" (zoals in het von Neumann-voorbeeld) toch eerlijk blijft.

Conclusie

Kortom: Foxtrot is een revolutionair nieuw gereedschap voor programmeurs en wiskundigen. Het stelt ons in staat om met zekerheid te zeggen: "Ja, die complexe, chaotische, toevallige code die we hebben geschreven, doet precies hetzelfde als die simpele, ideale versie die we in gedachten hebben."

Dit is cruciaal voor de veiligheid van onze digitale wereld, van beveiligde banktransacties tot kunstmatige intelligentie, waar toeval en multitasking steeds belangrijker worden. Foxtrot zorgt ervoor dat we niet hoeven te gokken, maar dat we het weten.

Probleemstelling

Randomisatie (probabilisme) en concurrentie zijn twee fundamentele taalfeatures in de moderne computertechnologie, gebruikt in toepassingen zoals machine learning, cryptografie en gedistribueerde systemen. Hoewel er afzonderlijk uitgebreide formele methoden bestaan voor het redeneren over probabilistische programma's en concurrente programma's, is de combinatie van beide uiterst complex en onderontwikkeld.

De kern van het probleem ligt in de semantische interactie tussen niet-determinisme (voorgesteld door concurrente threads en schedulers) en probabilistische keuzes. In semantische modellen compositeren deze twee concepten niet triviaal. Bestaande technieken voor contextuele equivalentie of verfijning (refinement) zijn beperkt tot:

Alleen probabilistische programma's (zonder concurrentie).
Alleen concurrente programma's (zonder probabilisme).
Eerste-orde programma's of programma's zonder lokale toestand.

Er ontbreekt een expressieve, mechaniseerbare logica voor het bewijzen van contextuele verfijning (contextual refinement) in hogere-orde concurrente probabilistische programma's met lokale toestand. Dit maakt het moeilijk om de correctheid van complexe algoritmen (zoals cryptografische bibliotheken) te verifiëren die zowel willekeurige sampling als parallelle thread-executie gebruiken.

Methodologie: Foxtrot

De auteurs presenteren Foxtrot, de eerste hogere-orde separatielogica (separation logic) die is ontworpen om contextuele verfijning te bewijzen voor concurrente probabilistische programma's met lokale toestand. Foxtrot is gebouwd op het Iris-framework en het Rocq (Coq) bewijsassistent.

De methodologie combineert geavanceerde principes uit drie domeinen:

Concurrentie: Er wordt gebruikgemaakt van standaard principes uit concurrente separatielogica, zoals invarianten (invariants) en ghost resources, om de interactie tussen threads te beheren.
Probabilisme: Er worden koppelingsprincipes (couplings) gebruikt om de verdelingen van twee programma's met elkaar te relateren.
Hogere-orde en Lokale Toestand: De logica ondersteunt dynamisch toegewezen geheugen en hogere-orde functies.

Kernconcepten en Technieken:

Logische Concurrente Probabilistische Verfijning: Het centrale oordeel is $\Delta \models e \preceq e' : \tau$ , wat betekent dat implementatie $e$ de specificatie $e'$ verfijnt. Dit wordt bewezen via een logische relatie gedefinieerd bovenop Hoare-tripels.
Presampling Tapes: Om probabilistische sampling in verschillende threads te relateren aan een enkele sampling, introduceert Foxtrot "presampling tapes". Hiermee kunnen toekomstige willekeurige uitkomsten in de logica "vooraf" worden gereserveerd en deterministisch worden uitgelokt tijdens het bewijs, zonder de daadwerkelijke uitvoering van het programma te veranderen.
Fragmented Couplings: Voor patronen zoals rejection sampling (waarbij een sample wordt verworpen als het niet voldoet aan een voorwaarde) worden gefragmenteerde koppelingen gebruikt. Dit stelt de logica in staat om te redeneren over gevallen waar de uitvoering stopt of doorgaat op basis van een probabilistische uitkomst.
Error Credits en Inductie: Om bewijzen voor algoritmen met onbepaalde lussen (zoals rejection sampling) te voltooien, gebruikt Foxtrot "error credits" ( $E(\varepsilon)$ ). Dit maakt inductie door foutversterking mogelijk: men bewijst dat twee programma's equivalent zijn binnen een foutmarge $\varepsilon$ , en versterkt deze marge inductief tot de fout verwaarloosbaar wordt.
Axioma van Keuze: Een unieke en uitdagende technische innovatie is het gebruik van een versie van het axioma van keuze binnen de Iris-logica. Omdat de logica families van schedulers moet combineren (in plaats van één enkele trace), is dit noodzakelijk om de soundness van het model te garanderen. Dit is uniek voor Iris-gebaseerde logica's.

Belangrijkste Bijdragen

Foxtrot Logica: De eerste hogere-orde separatielogica voor contextuele verfijning van concurrente probabilistische programma's met lokale toestand.
Soundness Bewijs: Een volledig mechaniseerd soundness-bewijs in Rocq, gebaseerd op een nieuw semantisch model dat gebruikmaakt van "full-information schedulers" en het axioma van keuze.
Geavanceerde Redeneerregels: Een verzameling nieuwe regels voor complexe koppelingsproblemen, waaronder:
- Asynchrone koppeling via presampling tapes.
- Koppeling van meerdere threads naar één specifieke uitkomst.
- Behandeling van rejection sampling via inductie met error credits.
Mechanisatie: Alle resultaten zijn volledig geverifieerd in het Rocq bewijsassistent, gebruikmakend van het Iris-framework en de Coquelicot bibliotheek voor reële analyse.

Resultaten en Case Studies

De auteurs demonstreren de expressiviteit van Foxtrot aan de hand van diverse voorbeelden die buiten het bereik van eerdere technieken vallen:

Adversarial von Neumann Coin: Een bewijs dat een programma dat een eerlijke munt simuleert uit een bevooroordeelde munt (die door een adversariaal thread kan worden gemanipuleerd) contextueel equivalent is aan een ideale eerlijke munt. Dit vereist redeneren over onbekende adversariale code via unaire logische relaties.
Sodium randombytes_uniform: Een verificatie van een kritieke functie in de cryptografische bibliotheek Sodium. De functie gebruikt rejection sampling om een uniforme verdeling te genereren. Foxtrot bewijst dat deze implementatie, ondanks concurrentie en niet-atomische sampling, thread-safe is en correct gedraagt als een directe uniforme sampling.
Batch Sampling: Het bewijzen dat het parallelle uitvoeren van twee onafhankelijke sampling-operaties (bijv. rand N en rand M) en het combineren van de resultaten, equivalent is aan één enkele sampling uit een grotere verdeling.
Rejection Sampling: Het verifiëren van algoritmen die samples herhaaldelijk genereren totdat een voorwaarde wordt voldaan, zelfs in een concurrente setting.

Significantie

Dit paper is een doorbraak in het veld van programma-verificatie om de volgende redenen:

Overbrugging van een Kruisbestuiving: Het sluit de kloof tussen probabilistische verificatie en concurrente verificatie, twee gebieden die tot nu toe grotendeels gescheiden waren.
Praktische Toepasselijkheid: Het biedt een bewijsmethode voor complexe, real-world scenario's zoals cryptografische protocollen en veilige willekeurige getallengeneratoren, waar fouten in de logica leiden tot beveiligingslekken.
Theoretische Innovatie: Het introduceert nieuwe semantische concepten (zoals het gebruik van het axioma van keuze in Iris en de specifieke behandeling van schedulers in probabilistische contexten) die de grenzen van wat er mechaniseerbaar bewezen kan worden, verleggen.
Robuustheid: Door alle resultaten te mechaniseren in Rocq, wordt de betrouwbaarheid van de logica en de bewijzen gegarandeerd, wat essentieel is voor het vertrouwen in formele methoden voor veiligheidskritieke software.

Kortom, Foxtrot biedt een krachtig en bewezen raamwerk om de correctheid van de meest complexe vormen van moderne software te garanderen, waarbij willekeur, parallelisme en gedeelde toestand samenkomen.