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

In der Welt der Software gibt es ein ständiges Spannungsfeld zwischen der Art und Weise, wie wir Code schreiben, und der Art und Weise, wie wir wissen, dass er sicher ist. Programmierer verwenden Hochsprachen, um komplexe Logik auf eine Weise zu beschreiben, die lesbar und handhabbar ist, aber die Maschinen, die diesen Code ausführen, sprechen eine viel einfachere, striktere Sprache. Um von der einen zur anderen zu gelangen, fungieren Compiler als Übersetzer, doch genau in diesem Übersetzungsprozess verbergen sich oft Fehler. Ein Fehler in der Übersetzung kann eine sichere Anweisung in eine gefährliche verwandeln, was dazu führt, dass ein Programm abstürzt oder sich unvorhersehbar verhält. Seit Jahrzehnten ist der zuverlässigste Weg, Sicherheit zu gewährleisten, die Verifizierung des fertigen Maschinencodes, was jedoch schwierig ist, da die hochsprachliche Bedeutung des ursprünglichen Programms im Prozess oft verloren geht. Die Frage, die Forscher stellen, ist, ob wir die Klarheit der ursprünglichen Hochsprache beibehalten können und gleichzeitig mit absoluter Gewissheit beweisen können, dass die endgültigen Maschinanweisungen genau das tun, was wir beabsichtigen.

Brent Hartshorn hat ein System entwickelt, das diese Frage beantwortet, indem es ein einzelnes Stück Code als zwei verschiedene Dinge zugleich behandelt. Stellen Sie sich ein Dokument vor, das gleichzeitig als mathematischer Beweis und als Satz von Anweisungen für eine Maschine gelesen werden kann. In dieser neuen Arbeit nimmt der Autor eine Teilmenge einer Programmiersprache namens OCaml, die für ihre strengen Regeln beim Umgang mit Daten bekannt ist, und verleiht jeder Definition zwei unterschiedliche Bedeutungen. Erstens wird der Code als logisches Argument gelesen, wobei die Struktur des Programms selbst als Beweis dient, dass bestimmte Bedingungen immer erfüllt sein werden. Zweitens wird derselbe Code in eine andere Sprache namens Rust übersetzt, die auf Geschwindigkeit und Sicherheit ausgelegt ist, und dann kompiliert, um ein Programm zu erstellen, das ein Computer tatsächlich ausführen kann. Die Brillanz dieses Ansatzes liegt in der Verifizierung: Der logische Beweis wird von einer kleinen, vertrauenswürdigen mathematischen Engine geprüft, während das laufende Programm gegen einen Referenzinterpreter geprüft wird, der den Code Schritt für Schritt simuliert. Wenn beide übereinstimmen und wenn der logische Beweis Bestand hat, ist das Ergebnis eine Software, die ihr eigenes Zertifikat der Sicherheit besitzt.

Die Forscher begannen damit, einen Übersetzer zu bauen, der einen spezifischen Ausschnitt von OCaml versteht. Dieser in Python geschriebene Übersetler ist klein genug, um von einer einzelnen Person gelesen und verstanden werden zu können, was entscheidend ist, denn wenn der Übersetzer selbst zu komplex ist, können wir seinem Output nicht vertrauen. Er nimmt den OCaml-Code und teilt ihn in zwei Pfade auf. Auf dem Beweispfad konvertiert er den Code in ein Format, das eine mathematische Kernel prüfen kann. Diese Kernel ist ein winziges Programm, das als Richter fungiert und die logische Korrektheit prüft, ohne Annahmen zu treffen. Auf dem Programmpfad konvertiert der Übersetzer den Code in Rust, eine Sprache, die in schnellen, nativen Maschinencode kompiliert wird. Um sicherzustellen, dass die Übersetzung perfekt war, baute das Team auch einen Referenzinterpreter, der den ursprünglichen OCaml-Code direkt ausführt. Sie ließen dann dreizehn verschiedene Beispielprogramme sowohl durch die kompilierte Rust-Version als auch durch den Interpreter laufen. In jedem einzelnen Fall lieferte der kompilierte Code exakt das gleiche Ergebnis wie der Interpreter, was bewies, dass der Übersetzungsprozess das Verhalten der Programme nicht verändert hat.

Nachdem der Code erfolgreich übersetzt worden war, wandte das Team eine strenge Sicherheitsprüfung auf die kompilierte Rust-Version an. Sie behandelten den kompilierten Code als einen Vertrag, bei dem spezifische Regeln darüber, wie das Programm sich verhalten sollte, als mathematische Theoreme niedergeschrieben wurden. Beispielsweise prüften sie, ob Ganzzahlberechnungen niemals versehentlich überlaufen und in eine negative Zahl umschlagen würden, eine häufige Quelle von Softwarefehlern. Sie fanden heraus, dass, obwohl die meisten dieser Sicherheitsregeln Bestand hatten, es spezifische Grenzfälle gab, in denen die Regeln gebrochen wurden. In elf verschiedenen Szenarien erreichte der kompilierte Code einen Punkt, an dem eine Ganzzahlberechnung überlaufen konnte, wie etwa wenn man die kleinstmögliche Zahl von Null subtrahiert. Das System identifizierte dies korrekt als offene Verpflichtungen (open obligations), was bedeutet, dass der Code überall sicher war, außer an diesen spezifischen, bekannten Grenzen. Von insgesamt neunzig durchgeführten Sicherheitsprüfungen an den Beispielprogrammen wurden neunundsiebzig vollständig bewiesen, während die verbleibenden elf offen blieben, da sie reale, erreichbare Grenzen in der Art und Weise darstellten, wie der Computer mit Zahlen umgeht.

Das Projekt ging noch weiter, indem es diese Methode auf einen kleinen Betriebssystemkern anwandte, ein Kernstück der Software, das Computerressourcen verwaltet. Die Forscher nahmen einen Kernel, der zuvor in Python und Rust geschrieben worden war, und schrieben ihn in ihre OCaml-Teilmenge um. Sie übersetzten diese neue Version dann in Rust und kompilierten sie. Das Ergebnis war eine dritte Implementierung desselben Kernels. Beim Testen gegen die ursprüngliche Python-Version antwortete die neue, von OCaml abgeleitete Version in allen 236 Testfällen korrekt. Das Team versuchte anschließend, die Sicherheit dieses neuen Kernels zu beweisen. Es gelang ihnen, 227 der 236 Sicherheitsverpflichtungen erfolgreich zu beweisen. Die wenigen, die unbewiesen blieben, waren keine Fehler im Code, sondern Lücken in den mathematischen Werkzeugen, die verwendet wurden, insbesondere im Hinblick darauf, wie das System komplexe Schleifen und Zähler handhabt. Dies demonstrierte, dass die Methode von kleinen Beispielen auf eine funktionale Betriebssystemkomponente skalieren kann.

Der vielleicht beeindruckendste Teil der Arbeit war die Fähigkeit, eine mathematische Gleichung direkt in ein funktionierendes Programm zu verwandeln. Die Forscher nahmen eine formale Gleichung, die das Verhalten eines Kernels beschrieb und in einer standardmäßigen mathematischen Notation geschrieben war, und speisten sie in ein Tool ein, das sie in OCaml-Code umwandelte. Dieser Code wurde dann kompiliert und ausgeführt. Das resultierende Programm verhielt sich exakt so, wie es die Gleichung beschrieb, und entsprach in jedem Fall dem Output des ursprünglichen Python-Modells. Dieser Prozess zeigte, dass eine hochsprachliche mathematische Beschreibung in eine verifizierte, ausführbare Binärdatei transformiert werden kann, ohne ihre Bedeutung zu verlieren. Das Team bewies, dass die kompilierte Version dieser Gleichung die meisten ihrer Sicherheitsverträge erfüllte, obwohl einige der komplexeren logischen Schritte weitere Verfeinerungen in den Prüfwerkzeugen erforderten.

Die Ergebnisse dieser Arbeit legen einen neuen Weg für die Entwicklung zuverlässiger Software nahe. Indem sie den hochsprachlichen Quellcode beibehalten und sowohl seine logische Bedeutung als auch seine kompilierte Form verifizieren, haben die Forscher ein System geschaffen, in dem die Sicherheit des fertigen Programms durch einen mathematischen Beweis untermauert wird. Die Methode identifizierte erfolgreich reale Einschränkungen in der Art und Weise, wie Computer mit Zahlen umgehen, wie etwa Ganzzahlüberläufe, und unterschied diese von tatsächlichen Fehlern. Obwohl das System nicht jede einzelne Sicherheitsregel für die komplexesten Teile des Kernels bewies, bewies es die überwiegende Mehrheit, und diejenigen, die offen blieben, wurden klar als Bereiche identifiziert, in denen die Prüfwerkzeuge selbst und nicht der Code verbessert werden mussten. Die Arbeit steht als Demonstration dafür, dass es möglich ist, den Übersetzungsprozess von hochsprachlichem Code zu Maschinanweisungen zu kontrollieren und sicherzustellen, dass die endgültige ausführbare Datei ein Sicherheitszertifikat trägt, das so rigoros ist wie die Logik, die sie erschaffen hat.