From LaTeX and OCaml to LEAN4 and Executables: Lean-Checked Theorems and Generating Proof-Carrying Rust

In de wereld van software bestaat er een constante spanning tussen hoe we code schrijven en hoe we weten dat deze veilig is. Programmeurs gebruiken programmeertalen op hoog niveau om complexe logica te beschrijven op een manier die leesbaar en beheersbaar is, maar de machines die deze code uitvoeren, spreken een veel eenvoudigere, meer rigide taal. Om van de ene naar de andere te komen, fungeren compilers als vertalers, maar dit vertalingsproces is precies waar fouten vaak aan het licht komen. Een fout in de vertaling kan een veilige instructie veranderen in een gevaarlijke, waardoor een programma crasht of onvoorspelbaar gedrag vertoont. Decennialang was de meest betrouwbare manier om veiligheid te garanderen het verifiëren van de uiteindelijke machinecode, maar dit is moeilijk omdat de hoogwaardige betekenis van het oorspronkelijke programma in het proces vaak verloren gaat. De vraag die onderzoekers stellen is of we de helderheid van de oorspronkelijke programmeertaal op hoog niveau kunnen behouden en tegelijkertijd met absolute zekerheid kunnen bewijzen dat de uiteindelijke machine-instructies precies doen wat we de bedoeling hebben.

Brent Hartshorn heeft een systeem gebouwd dat deze vraag beantwoordt door een enkel stuk code te behandelen als twee verschillende dingen tegelijkertijd. Stel je een document voor dat gelijktijdig gelezen kan worden als een wiskundig bewijs en als een set instructies voor een machine. In dit nieuwe werk neemt de auteur een deelverzameling van een programmeertaal genaamd OCaml, die bekend staat om zijn strikte regels over hoe met gegevens wordt omgegaan, en geeft elke definitie twee afzonderlijke betekenissen. Ten eerste wordt de code gelezen als een logisch argument, waarbij de structuur van het programma zelf dient als een bewijs dat bepaalde voorwaarden altijd zullen worden voldaan. Ten tweede wordt dezelfde code vertaald naar een andere taal genaamd Rust, die is ontworpen voor snelheid en veiligheid, en vervolgens gecompileerd naar een programma dat een computer daadwerkelijk kan uitvoeren. De genialiteit van de aanpak ligt in de verificatie: het logische bewijs wordt gecontroleerd door een kleine, vertrouwde wiskundige engine, terwijl het draaiende programma wordt gecontroleed tegen een referentie-interpreter die de code stap voor stap simuleert. Als de twee overeenkomen, en als het logische bewijs standhoudt, is het resultaat een stuk software dat gepaard gaat met een eigen certificaat van veiligheid.

De onderzoekers begonnen met het bouwen van een vertaler die een specifiek deel van OCaml begrijpt. Deze vertaler, geschreven in Python, is klein genoeg om gelezen en begrepen te worden door één persoon, wat cruciaal is omdat als de vertaler zelf te complex is, we de output ervan niet kunnen vertrouwen. Het neemt de OCaml-code en splitst deze in twee paden. Op het bewijspad zet de vertaler de code om in een formaat dat een wiskundige kernel kan controleren. Deze kernel is een klein programma dat optreedt als een rechter en verifieert dat de logica deugt zonder aannames te doen. Op het programmapad vertaalt de vertaler de code naar Rust, een taal die wordt gecompileerd naar snelle, native machinecode. Om te garanderen dat de vertaling perfect was, heeft het team ook een referentie-interpreter gebouwd die de oorspronkelijke OCaml-code direct uitvoert. Vervolgens hebben ze dertien verschillende voorbeeldprogramma's door zowel de gecompileerde Rust-versie als de interpreter gelopen. In elk geval produceerde de gecompileerde code exact dezelfde output als de interpreter, wat bewees dat het vertalingsproces het gedrag van de programma's niet heeft gewijzigd.

Zodra de code succesvol was vertaald, paste het team een strikte veiligheidscontrole toe op de gecompileerde Rust-versie. Ze behandelden de gecompileerde code als een contract, waarbij specifieke regels over hoe het programma zich zou moeten gedragen, werden opgeschreven als wiskundige stellingen. Ze controleerden bijvoorbeeld of integerberekeningen nooit per ongeluk zouden overstromen (overflow) en zouden omklappen naar een negatief getal, een veelvoorkomende bron van bugs in software. Ze ontdekten dat hoewel de meeste van deze veiligheidsregels waar waren, er specifieke randgevallen waren waar de regels werden geschonden. In elf verschillende scenario's bereikte de gecompileerde code een punt waarop een integerberekening kon omklappen, zoals wanneer het kleinste mogelijke getal van nul wordt afgetrokken. Het systeem identificeerde deze correct als openstaande verplichtingen, wat betekent dat de code overal veilig was, behalve bij deze specifieke, bekende limieten. Van de in totaal negentig uitgevoerde veiligheidscontroles op de voorbeeldprogramma's, werden er zeventien volledig bewezen, terwijl de resterende elf open bleven omdat ze representatief waren voor reële, bereikbare limieten in de manier waarop de computer met getallen omgaat.

Het project ging verder door deze methode toe te passen op een kleine operating system kernel, een kernstuk software dat computerbronnen beheert. De onderzoekers namen een kernel die eerder in Python en Rust was geschreven en schreven deze opnieuw in hun OCaml-deelverzameling. Vervolgens vertaalden ze deze nieuwe versie naar Rust en compileerden deze. Het resultaat was een derde implementatie van dezelfde kernel. Bij het testen tegen de originele Python-versie gaf de nieuwe OCaml-afgeleide versie in alle 236 testgevallen het juiste antwoord. Het team probeerde de veiligheid van deze nieuwe kernel te bewijzen. Ze slaagden erin 227 van de 236 veiligheidsverplichtingen te bewijzen. De weinige die onbewezen bleven, waren geen fouten in de code, maar eerder hiaten in de wiskundige instrumenten die werden gebruikt om ze te controleren, specifiek met betrekking tot hoe het systeem complexe lussen en tellers afhandelt. Dit toonde aan dat de methode kan opschalen van kleine voorbeelden naar een functionele onderdeel van een besturingssysteem.

Misschien wel het meest opmerkelijke deel van het werk was de mogelijkheid om een wiskundige vergelijking direct in een werkend programma te veranderen. De onderzoekers namen een formele vergelijking die het gedrag van een kernel beschreef, geschreven in een standaard wiskundige notatie, en voerden deze in een tool die de vergelijking omzette in OCaml-code. Deze code werd vervolgens gecompileerd en uitgevoerd. Het resulterende programma gedroeg zich exact zoals de vergelijking beschreef, waarbij de output van het originele Python-model in elk geval werd gematcht. Dit proces toonde aan dat een hoogwaardige wiskundige beschrijving kan worden getransformeerd naar een geverifieerde, uitvoerbare binary zonder haar betekenis te verliezen. Het team bewees dat de gecompileerde versie van deze vergelijking de meeste van haar veiligheidscontracten voldeed, hoewel sommige van de complexere logische stappen verdere verfijning vereisten in de controle-instrumenten.

De bevindingen van dit werk suggereren een nieuwe weg voor het bouwen van betrouwbare software. Door de hoogwaardige broncode te behouden en zowel de logische betekenis als de gecompileerde vorm te verifiëren, creëerden de onderzoekers een systeem waarbij de veiligheid van het uiteindelijke programma wordt ondersteund door een wiskundig bewijs. De methode identificeerde succesvol reële beperkingen in de manier waarop computers met getallen omgaan, zoals integer overflow, en maakte onderscheid tussen deze en werkelijke bugs. Hoewel het systeem niet elke enkele veiligheidsregel voor de meest complexe delen van de kernel bewees, bewees het de overgrote meerderheid, en de gevallen die open bleven, werden duidelijk geïdentificeerd als gebieden waar de controle-instrumenten, in plaats van de code zelf, verbetering nodig hadden. Het werk staat als een demonstratie dat het mogelijk is om het vertalingsproces van hoogwaardige code naar machine-instructies te beheersen, waardoor de uiteindelijke uitvoerbare bestand een certificaat van veiligheid draagt dat even rigoureus is als de logica die het heeft gecreëerd.