Verification of a DPLL Transition System in Rocq

Stellen Sie sich eine Welt vor, in der Computer ständig ein hochkarätiges Spiel namens „Wahr oder Falsch“ spielen. In diesem Spiel wird dem Computer ein riesiger, verhedderter Knoten aus logischen Aussagen übergeben – wie ein Rezept, das besagt: „Wenn du Zucker hinzufügst, musst du auch Mehl hinzufügen, aber wenn du Mehl hinzufügst, darfst du kein Salz hinzufügen.“ Das Ziel ist es, einen Weg zu finden, das Rezept zu befolgen, ohne die Regeln zu brechen. Dies ist das Erfüllbarkeitsproblem (SAT). Es ist das digitale Äquivalent dazu, zu versuchen, eine Million verschiedene Puzzleteile in eine Schachtel zu passen, in der einige Teile rot und andere blau sind und die Anweisungen lauten: „Kein Rot neben Blau.“

Warum ist uns das wichtig? Weil dies nicht nur ein Logikrätsel ist; es ist der Motor hinter fast allem Komplexen in der Computertechnik. Vom Design von Mikrochips bis hin zum Beweis, dass ein mathematisches Theorem wahr ist – Computer nutzen SAT-Solver, um durch diese massiven logischen Labyrinthe zu navigieren. Aber hier ist der Haken: Diese Solver sind unglaublich komplex. Wenn sich ein winziger Bug im Code versteckt, könnte der Computer Ihnen voller Selbstvertrauen sagen, dass ein Beweis gültig ist, obwohl er eigentlich völliger Unsinn ist. Deshalb sind Mathematiker und Informatiker besessen von der formalen Verifikation. Betrachten Sie dies als den Bau eines superstrengen, unzerbrechlichen Sicherheitsnetzes. Anstatt nur zu hoffen, dass der Computer funktioniert, verwenden sie eine spezielle Art von „mathematischem Mikroskop“ (einen Proof Assistant), um jeden einzelnen Schritt der Logik zu prüfen und sicherzustellen, dass die Maschine niemals lügen kann, wenn sie eine Antwort gibt.

Das große Abenteuer der Arbeit: Den Bau eines vertrauenswürdigen Logik-Maschinenteils

In dieser Arbeit unternehmen Julia Dijkstra und Benedikt Ahrens einen riesigen Schritt, um diese Logikmaschinen vertrauenswürdig zu machen. Sie haben nicht einfach nur ein Programm geschrieben; sie haben ein mathematisch bewiesenes Skelett einer berühmten Logik-Lösungsmethode namens DPLL (Davis-Putnam-Logemann-Loveland) innerhalb eines Tools namens Rocq aufgebaut.

Betrachten Sie die DPLL-Methode nicht als einen starren Roboter, der einem Skript folgt, sondern als ein „Zustandswechsel“-Spiel. Stellen Sie sich einen Detektiv vor, der versucht, ein Rätsel zu lösen. Der Detektiv beginnt mit einem leeren Notizbuch (keine Hinweise). Er hat einen Satz von Regeln, wie er sein Notizbuch aktualisiert:

1. Die „Ach, ich verstehe!“-Regel (Unit Propagate): Wenn ein Hinweis besagt: „Entweder der Butler war es ODER die Magd“, und der Detektiv bereits weiß, dass die Magd unschuldig ist, muss das Notizbuch aktualisiert werden zu: „Der Butler war es“. Der Detektiv hat keine Wahl; die Logik erzwingt diesen Schritt.
2. Die „Reine Vermutung“-Regel (Pure Literal): Wenn der Detektiv einen Hinweis über „den Gärtner“ sieht, aber niemals einen Hinweis darüber sieht, dass „der Gärtner nicht es war“, kann er sicher vermuten, dass der Gärtner involviert ist, ohne Angst vor einem Widerspruch zu haben.
3. Die „Abzweigung“-Regel (Decide): Wenn der Detektiv feststeckt, wählt er einen zufälligen Hinweis (wie „Der Butler war es“) und schreibt ihn als Entscheidung auf. Dies ist ein Weggabelung.
4. Die „Ups, falsche Abbiegung“-Regel (Backtrack): Wenn der Detektiv eine Entscheidung aufschreibt und später auf einen Widerspruch stößt (einen Hinweis, der besagt: „Der Butler war es nicht“), muss er alles löschen, was nach dieser Entscheidung geschah, die Entscheidung umkehren (jetzt war es der Butler nicht) und erneut versuchen.
5. Die „Spiel vorbei“-Regel (Fail): Wenn er alles löscht, die letzte Entscheidung umkehrt und immer noch auf einen Widerspruch stößt, ist das Spiel vorbei. Das Rätsel ist unlösbar.

Die Hauptleistung der Autoren besteht darin, dieses gesamte Spiel auf eine Weise aufzuschreiben, dass der Rocq-Proof-Assistant es lesen und verifizieren kann. Sie haben nicht nur gesagt: „Das sieht richtig aus.“ Sie haben drei massive Dinge bewiesen:

• Korrektheit (Correctness): Wenn das Spiel mit einer Lösung endet, ist diese Lösung definitiv echt. Der Computer wird kein Modell halluzinieren.
• Vollständigkeit (Completeness): Wenn eine Lösung existiert, wird das Spiel sie finden. Der Computer wird nicht stecken bleiben oder aufgeben, wenn er es nicht sollte.
• Terminierung (Termination): Das Spiel wird niemals ewig laufen. Es ist mathematisch garantiert, dass es stoppt, entweder mit einer Lösung oder einem „Spiel vorbei“.

Eine neue Wendung hinzufügen: Die „Reine“-Regel

Einer der coolen Beiträge der Arbeit ist, dass sie eine spezifische Regel zu ihrem Spiel hinzugefügt haben, die einige frühere Versionen dieser Theorie ausgelassen haben: die Pure-Literal-Regel. In der Detektiv-Analogie ist dies der Moment, in dem der Detektiv erkennt: „Hey, ich habe noch nie etwas gegen den Gärtner gehört, also nehme ich einfach an, dass der Gärtner der Täter ist.“ Die Autoren haben bewiesen, dass das Hinzufügen dieser Regel das Spiel schneller macht, ohne die Sicherheitsgarantien zu verletzen. Sie haben gezeigt, dass die Logik selbst mit dieser zusätzlichen Abkürzung absolut wasserdicht bleibt.

Von der Theorie zu einem echten (aber einfachen) Roboter

Nachdem sie bewiesen hatten, dass die Regeln des Spiels in der Theorie perfekt funktionieren, fragten die Autoren: „Können wir tatsächlich einen Roboter bauen, der dieses Spiel spielt?“ Sie entwickelten eine Strategie – eine Reihe von Anweisungen für den Detektiv, welche Regel als Nächstes zu wählen ist. Sie bauten eine konkrete Version dieser Strategie in Rocq auf und nutzten dann ein magisches Werkzeug namens Extraktion, um ihren mathematischen Beweis in ein echtes Computerprogramm in OCaml zu verwandeln.

Sie testeten diesen neuen Roboter an einigen einfachen Rätseln. Er funktionierte! Er löste Probleme korrekt, einschließlich eines Rätsels namens zebra.cnf mit 155 Variablen und 1.135 Klauseln. Die Autoren sind sich jedoch sehr ehrlich über die Einschränkungen ihres Roboters. Er ist wie ein beweistypisches Spielzeugauto: Er fährt perfekt und beweist, dass der Motor funktioniert, aber er ist noch kein Formel-1-Rennwagen. Er ist langsam, weil er einfache Listen verwendet, um Hinweise zu speichern, während echte Rennwagen Hochgeschwindigkeitsspeicher nutzen. Die Autoren geben zu, dass diese Version noch nicht bereit ist, die Industriem giants zu schlagen, die heute von Unternehmen eingesetzt werden, aber sie ist ein verifizierter Kern. Es ist ein winziges, unzerbrechliches Fundament, auf dem zukünftige, schnellere und intelligentere Solver aufgebaut werden können.

Was dies für die Zukunft bedeutet

Die Arbeit behauptet nicht, das Problem der weltbesten schnellen SAT-Solver gelöst zu haben. Stattdessen behauptet sie, den sichersten möglichen Bauplan erstellt zu haben. Durch den Beweis der abstrakten Regeln in Rocq haben sie einen „vertrauenswürdigen Kern“ geschaffen. Zukünftige Forscher können nun diesen Bauplan nehmen und die ausgefeilten Funktionen moderner Solver hinzufügen – wie das „Lernen aus Fehlern“ (Clause Learning) oder das „Zurückspringen über mehrere Schritte“ (Non-chronological Backtracking) – mit der Gewissheit, dass die zugrunde liegende Logik nach wie vor fundiert ist.

Kurz gesagt: Dijkstra und Ahrens haben nicht nur ein besseres Auto gebaut; sie haben den Bauplan für ein Auto gebaut, das niemals abstürzen kann, indem sie bewiesen haben, dass die Logik hinter den Rädern mathematisch perfekt ist. Es ist ein kleiner, verifizierter Schritt, der den Weg für viel größere, komplexere und vertrauenswürdigere Logikmaschinen in der Zukunft ebnet.