Die Cleanroom-Softwareentwicklung verlangt, dass Sie die Korrektheit Ihres Codes beweisen, bevor Sie ihn kompilieren. Das klingt edel, bis Sie drei Stunden damit verbringen, Schleifeninvarianten für eine Funktion zu schreiben, die zehn Integer sortiert.

Der Engpass ist nicht das Beweisen. Es ist das Boilerplate. Verifikationsbedingungen zu generieren, Schleifen mit Invarianten zu annotieren und Assertions für Dafny, Why3 oder Z3 zu formatieren ist mühsam, fehleranfällig und absolut kein Vergnügen. LLMs sind erstaunlich gut in diesem Teil. Sie sind nicht gut im eigentlichen Beweisen. Den Unterschied zu verstehen, ist es, was die Automatisierung nützlich statt gefährlich macht.

Warum manuelle Proof Obligations die Entwicklungsgeschwindigkeit töten

Im Cleanroom schreiben Sie Code auf Basis von Box-Structure-Spezifikationen und generieren dann Verifikationsbedingungen (VCs), um zu beweisen, dass Ihre Implementierung mit der Spezifikation übereinstimmt. Jede Schleife braucht eine Invariante. Jede Funktion braucht eine Vor- und eine Nachbedingung. Jede Datenverfeinerung braucht eine Abstraktionsfunktion.

Für ein Team, das Software ausliefern möchte, ist das eine Steuerlast. Ein Senior-Entwickler könnte 40 % seiner Zeit mit Annotationen und VC-Gerüsten verbringen und 60 % mit dem eigentlichen logischen Schlussfolgern. Das Gerüst erfordert keine tiefe Einsicht. Es erfordert Geduld und Vertrautheit mit der Syntax Ihres Beweisers.

Genau das ist die Art von Mustererkennungsaufgabe, in der LLMs brillieren. Sie haben Tausende von Schleifeninvarianten, Dafny-Methoden und SMT-LIB-Dateien gesehen. Sie können syntaktisch gültige Annotationen generieren, die plausibel genug sind, um als Ausgangspunkt zu dienen.

Was “Formale Beweise mit LLMs automatisieren” wirklich bedeutet

Seien wir präzise. Ein LLM beweist nicht, dass Ihr Code korrekt ist. Ein Beweislöser wie Z3, CVC5 oder der Dafny-Verifikator beweist, dass Ihr Code korrekt ist. Das LLM automatisiert die menschliche Arbeit, die zwischen Ihrem Pseudocode und dem Löser liegt.

Der Workflow sieht so aus:

  1. Sie schreiben die Implementierung und die Spezifikation.
  2. Das LLM generiert Kandidaten-Annotationen: Invarianten, Vorbedingungen, Nachbedingungen, Ghost-Variablen.
  3. Sie führen den annotierten Code in den Verifikator ein.
  4. Der Verifikator akzeptiert entweder den Beweis, lehnt ihn mit einem Gegenbeispiel ab oder läuft in ein Timeout.
  5. Wenn der Beweis fehlschlägt, untersuchen Sie den Fehler und fordern das LLM auf, die Annotation zu verfeinern.

Das LLM ist ein sehr schneller, sehr selbstsicherer Praktikant, der die Syntax jedes Verifikationstools im Internet kennt. Es halluziniert gerne eine Invariante, die perfekt aussieht und sofort scheitert. Das ist in Ordnung. Der Löser fängt die Halluzination ab. Der Wert liegt darin, das leere-Seite-Problem zu überspringen.

Wie LLMs Annotationen generieren, die Löser prüfen können

Der Trick liegt im Prompt. Sie bitten das LLM nicht, “diese Funktion als korrekt zu beweisen”. Sie bitten es, ein bestimmtes Artefakt in einem bestimmten Format zu erstellen.

Wenn Sie beispielsweise eine Python-ähnliche Funktion haben, die die Summe eines Arrays berechnet, formulieren Sie den Prompt etwa so:

Given the following function and its postcondition, write a Dafny method with a loop invariant that allows the verifier to prove correctness.

Function: sum(arr) returns the sum of all elements in arr.
Postcondition: result == sum(i in 0..|arr|) arr[i]

Das LLM liefert Dafny-Code mit einer Schleifeninvariante wie forall k :: 0 <= k < i ==> arr[k] is accounted for in result. Möglicherweise stimmt die exakte Syntax nicht beim ersten Versuch. Aber die Struktur stimmt, und das spart Ihnen zehn Minuten Tipperei.

Für mehr Kontrolle können Sie direkt nach SMT-LIB fragen. Das ist nützlich, wenn Sie benutzerdefinierte Verifikations-Pipelines aufbauen, anstatt eine Hochsprache wie Dafny zu verwenden.

Ein funktionierendes Beispiel: Automatisierung einer Schleifeninvariante mit Python und Z3

Hier ist ein vollständiges, ausführbares Beispiel. Wir verwenden Python, um ein LLM (OpenAI-API) aufzufordern, eine Schleifeninvariante für eine einfache Array-Summen-Funktion zu generieren, und verifizieren sie dann mit Z3.

Zuerst installieren Sie die Abhängigkeiten:

pip install z3-solver openai

Dann führen Sie das Skript aus:

import openai
from z3 import *

code = """
def sum_array(arr):
    s = 0
    i = 0
    n = len(arr)
    while i < n:
        s = s + arr[i]
        i = i + 1
    return s
"""

prompt = f"""You are a formal verification assistant.

Given this Python function that sums an array:
{code}

The postcondition is: result == Sum(arr[j] for j in range(len(arr)))

Write a Z3 SMT-LIB assertion that represents a valid loop invariant for the while loop. The invariant should mention i, s, n, and arr. Use Python Z3 syntax (ForAll, Implies, And, etc.). Return ONLY the Python code for the invariant, no explanation."""

client = openai.OpenAI()
response = client.chat.completions.create(
    model="gpt-4o",
    messages=[{"role": "user", "content": prompt}],
    temperature=0.2,
)

invariant_code = response.choices[0].message.content.strip()
print("Generated invariant:")
print(invariant_code)

# Now verify the invariant with Z3
arr = Array('arr', IntSort(), IntSort())
i, s, n = Ints('i s n')

# We manually parse the LLM's output. In production you'd use an AST parser.
# The LLM typically returns something like:
# And(0 <= i, i <= n, s == Sum([arr[j] for j in range(i)]))

# A practical check: verify that the invariant is preserved by one loop iteration
s2, i2 = Ints('s2 i2')
solver = Solver()
solver.add(n == 3)
solver.add(arr[0] == 1, arr[1] == 2, arr[2] == 3)
solver.add(i2 == 1, s2 == 1)  # assume invariant holds mid-loop

# Execute one iteration
s_next = s2 + Select(arr, i2)
i_next = i2 + 1

# Check that invariant holds after iteration
solver.add(Not(And(i_next >= 0, i_next <= n)))

if solver.check() == unsat:
    print("Invariant preserved for this concrete case.")
else:
    print("Invariant FAILED for this concrete case.")
    print(solver.model())

Dieses Skript wird die Funktion nicht auf einen Schlag verifizieren. Genau darum geht es. Das LLM liefert Ihnen eine Kandidaten-Invariante. Z3 sagt Ihnen, ob sie gilt. Sie iterieren.

In der Praxis verpacken Teams, die LLM-unterstützte Verifikations-Pipelines aufbauen, diese Schleife in ein Skript, das fehlgeschlagene VCs zurück an das LLM sendet, die neue Annotation parst, den Verifikator ausführt und etwaige Fehlermeldungen als Verfeinerungsprompt zurückfüttert.

Das ist keine vollständig autonome Verifikation. Es ist Verifikation mit Mensch im Loop und einem sehr schnellen Schreibassistenten.

Wo es scheitert: Halluzinationen vs. echte Fehler

Das LLM wird Invarianten generieren, die zu schwach sind. Es wird vergessen, eine Variable zu erwähnen, die der Löser braucht. Es wird Dafny-Syntax aus dem Jahr 2019 generieren, die nicht mehr kompiliert. Es wird Ihnen zuversichtlich erzählen, dass i <= n ausreicht, wenn die Schleife tatsächlich i < n && s == partial_sum(arr, i) erfordert.

Keines davon ist katastrophal. Der Löser lehnt sie ab. Sie lesen den Fehler, Sie formulieren einen neuen Prompt.

Die echte Gefahr liegt im Gegenteil. Wenn das LLM eine Invariante generiert, die zu stark ist, könnte der Löser das Programm gegen eine Spezifikation als korrekt beweisen, die strenger ist als beabsichtigt. Sie glauben, Sie hätten bewiesen, dass sum_array für alle Arrays funktioniert. Tatsächlich haben Sie bewiesen, dass es nur für Arrays funktioniert, in denen alle Elemente positiv sind, weil das LLM ein zusätzliches Konjunkt eingeworfen hat, das vernünftig aussah.

Überprüfen Sie die generierte Spezifikation immer. Das LLM schreibt das Boilerplate. Die Logik gehört Ihnen.

Wann man der Maschine vertraut, und wann man von Hand arbeitet

Verwenden Sie LLM-Automatisierung für:

  • Gerüste für VCs für einfache Funktionen mit klaren Vor- und Nachbedingungen.
  • Syntaxübersetzung zwischen Beweissprachen. Eine Dafny-Spezifikation in Why3 oder SMT-LIB zu überführen ist mechanisch und fehleranfällig. LLMs sind dabei hervorragend.
  • Ghost-Variablen-Generierung für Datenverfeinerungsbeweise. Das Muster ist repetitiv.

Verwenden Sie keine LLM-Automatisierung für:

  • Sicherheitskritische Beweise, bei denen ein subtiler Spezifikationsfehler schlimmer ist als gar kein Beweis.
  • Komplexe Temporallogik oder Lebendigkeitseigenschaften. Die Trainingsdaten des LLMs sind hier dünner, und Halluzinationen können eher durchschlüpfen.
  • Neuartige Algorithmen, die nichts aus dem Trainingskorpus ähneln. Wenn Sie ein neues Konsensprotokoll erfunden haben, hat das LLM keine Ahnung, welche Invarianten es braucht.

Häufig gestellte Fragen

Was ist eine Verifikationsbedingung in der Cleanroom-Entwicklung?

Eine Verifikationsbedingung ist eine logische Formel, die aus Ihrem Code und seiner Spezifikation generiert wird. Wenn die Formel gültig ist, implementiert Ihr Code die Spezifikation korrekt. Im Cleanroom werden diese typischerweise vor der Kompilierung generiert und mit einem Beweisassistenten oder automatischen Löser erfüllt.

Können LLMs Beweisassistenten wie Coq oder Isabelle ersetzen?

Nein. LLMs generieren Code und Annotationen, die Beweisassistenten prüfen können. Sie führen nicht die eigentlichen Beweisschritte aus. Der Beweisassistent ist nach wie vor die Autorität darüber, ob ein Beweis gültig ist.

Was ist das beste LLM für die Generierung formaler Verifikationsannotationen?

GPT-4o und Claude 3.5 Sonnet schneiden beide bei Dafny- und SMT-LIB-Syntax gut ab. Kleinere Modelle haben oft Schwierigkeiten mit der präzisen Syntax, die Beweislöser erfordern. Setzen Sie die Temperatur niedrig (0,1–0,2), um kreative Halluzinationen zu reduzieren.

Wie verhindert man, dass ein LLM eine falsche Spezifikation generiert?

Das kann man nicht. Sie behandeln die LLM-Ausgabe als Entwurf. Führen Sie die generierten Annotationen immer durch Ihren Verifikator. Lesen Sie die generierten Vor- und Nachbedingungen immer durch, um sicherzustellen, dass sie Ihrer Absicht entsprechen. Nehmen Sie nie an, dass eine erfolgreiche Verifikation bedeutet, dass die Spezifikation korrekt ist.

Beginnen Sie mit den langweiligen Teilen

Wenn Ihr Team Cleanroom oder eine beliebige Correctness-by-Construction-Arbeit macht, ist die Automatisierung mit dem höchsten Wert nicht irgendein großer KI-Theorembeweiser. Es ist ein Skript, das Ihre Schleifeninvarianten generiert und Ihr SMT-LIB formatiert, damit Sie das nicht selbst tun müssen.

Wählen Sie die fünf mühsamsten Annotationsmuster in Ihrer codebase aus. Schreiben Sie für jedes eine Prompt-Vorlage. Führen Sie sie durch ein LLM, verifizieren Sie die Ausgabe und committen Sie diejenigen, die bestehen. Das war’s. Sie haben sich 40 % Ihrer Verifikationszeit für den Preis eines API-Aufrufs zurückgekauft.

Die schwierigen Beweise gehören nach wie vor Ihnen. Aber wenigstens müssen Sie sie nicht von Grund auf tippen.