Zum Hauptinhalt springen

[Stanford CS146S #9] Autonomes TDD & Formale Verifikation: Z3 SMT-Solver, Property-basierte Invarianten und mathematische Beweise für KI-generierten Code

· 3 Minuten Lesezeit
Jaybee
Jaybee
AI & Robotics Engineer

Autonomes TDD und Formale Verifikation mit Z3 SMT Solver

Willkommen zum neunten Teil unserer technischen Analyse der Stanford-Vorlesungsreihe CS146S: The Modern Software Developer.

In den vorherigen Vorlesungen haben wir uns mit Prompting, MCP, Multi-Agenten-Swarms, eBPF und KI-nativer Architektur befasst. In Vorlesung 9 widmet sich der Stanford-Lehrplan dem ultimativen Dilemma moderner Softwareentwicklung: Wie können Teams probabilistischen, nicht-deterministischen Sprachmodellen vertrauen, wenn es um sicherheitskritischen, fehlerfreien Code in Finanzsystemen, Luft- und Raumfahrt, Kryptographie und verteilten Systemen geht?

Wie Edsger Dijkstra vor über 50 Jahren treffend formulierte: „Program testing can be used to show the presence of bugs, but never to show their absence!“ In dieser Vorlesung zeigen Stanford-Forscher den Übergang von beispielbasierten Unittests zu autonomem Property-Based Testing (PBT), symbolischer Ausführung und formaler Verifikation mit dem Z3 SMT-Solver.

1. Die Grenzen beispielbasierter Unittests bei KI-Code​

Bei traditionellen Unittests prüfen Entwickler wenige Einzelbeispiele:

def test_calculate_fee():
    assert calculate_fee(100) == 5
    assert calculate_fee(0) == 0

Wenn ein KI-Programmieragent Code schreibt, um diese Tests zu bestehen, entsteht häufig Test Overfitting:

  • Der Agent implementiert eine Logik, die exakt diese 2 Fälle besteht, aber bei negativen Zahlen, Integer-Überläufen oder extremen Werten unbemerkt versagt.

2. Property-Based Testing (PBT) mit Hypothesis​

Statt einzelner Werte definiert der Entwickler universelle mathematische Invarianten:

orall x \in ext{Inputs}, \quad ext{Property}(f(x)) = ext{True}

from hypothesis import given, strategies as st

@given(st.integers(min_value=0, max_value=1_000_000))
def test_fee_always_less_than_amount(amount):
    fee = calculate_fee(amount)
    assert 0 <= fee <= amount

Das Test-Framework generiert tausende stochastische Randfälle, findet minimale Gegenbeispiele (Shrinking) und zwingt den KI-Agenten, die vollständige mathematische Logik korrekt zu implementieren.

3. Formale Verifikation mit dem Z3 SMT-Solver​

Die höchste Stufe der Verifikation ist die mathematische Beweisführung mittels SMT-Solver (Satisfiability Modulo Theories):

from z3 import Int, Solver, sat, unsat

# Formale Invarianten-Prüfung
balance = Int('balance')
withdrawal = Int('withdrawal')
s = Solver()

# Postcondition: Kontostand darf niemals negativ werden
new_balance = balance - withdrawal
s.add(balance >= 0)
s.add(withdrawal > 0)
s.add(new_balance < 0) # Gegenbeispiel suchen

if s.check() == unsat:
    print("Mathematisch bewiesen: Invariante hält für alle Eingaben!")
else:
    print("Gegenbeispiel gefunden:", s.model())

Gibt Z3 unsat zurück, ist mathematisch bewiesen, dass unter den definierten Vorbedingungen niemals ein ungültiger Systemzustand eintreten kann — unabhängig davon, wie viele Millionen Transaktionen ausgeführt werden.

📌 Management Summary (3–5 Zeilen)​

  1. Grenzen von Beispiel-Tests: Beispielbasierte Unittests verleiten KI-Agenten zu Test-Overfitting und übersehen gefährliche Randfälle.
  2. Property-Based Invarianten: PBT prüft universelle Systeminvarianten über tausende automatisch generierte Extremwerte.
  3. Mathematische Beweise mit Z3: SMT-Solver beweisen die logische Korrektheit von Algorithmen formell und lückenlos.
  4. CEGAR-Feedbackschleife: Solver-Gegenbeispiele fließen direkt als deterministisches Feedback zurück in den Agenten zur fehlerfreien Selbstheilung.

Referenzen & Kursmaterialien​

ANZEIGE