Ein iterativer Verifikationsprozess, der zwischen Model Checking eines abstrahierten Systems und Verfeinerungsschritten, die von Gegenbeispielen ausgehen, wechselt, bis die Eigenschaft entweder für das konkrete System bewiesen oder ein echtes Gegenbeispiel gefunden wird.

Prinzip

Gegenbeispiele auf der abstrakten Ebene nutzen, um spurious Verhalten von echten Fehlern zu unterscheiden, und die Abstraktion nur gezielt verfeinern, wodurch falsche Alarme zugunsten gezielter Genauigkeitssteigerungen eingetauscht werden.

Demonstration

Eine Sicherheitsbedingung eines Softwareteils mittels Prädikatsabstraktion verifizieren; liefert der Model Checker ein Gegenbeispiel, dieses auf dem konkreten Programm simulieren. Falls die Simulation zeigt, dass die Spur spurious ist, Prädikate hinzufügen, die den spurious Pfad trennen, und das Model Checking wiederholen, bis die Eigenschaft gilt oder eine reale fehlerhafte Spur vorliegt.

Fehlanwendung

Jedes Gegenbeispiel ungeprüft als echt behandeln und damit falsche Negative akzeptieren, oder fortlaufend Prädikate hinzufügen, die spurious Spuren entfernen, aber zu einer Explosion des Zustandsraums und einem Verlust der Skalierbarkeit führen.

Konsequenz

Bei sounder Abstraktion und geeigneten Verfeinerungsheuristiken erzeugt die Methode typischerweise entweder einen Korrektheitsbeweis in einem kompakten abstrakten Modell oder ein konkretes Gegenbeispiel; in der Praxis kann sie die Skalierbarkeit gegenüber direkten konreten Zustandssuchen deutlich verbessern.

Umkehrung

Eine reine Abstraktionsstrategie, die nie anhand von Gegenbeispielen verfeinert (Einmal‑Abstraktion), oder die exhaustive Suche im konkreten Zustandsraum ohne Abstraktion — beide Extrema erzeugen entweder persistierende spurious Warnungen oder skalieren nicht.

Abgrenzung

Anwendbar, wenn ein abstraktes Modell und eine Verfeinerungsstrategie definierbar sind; garantiert nicht für alle Systeme die Terminierung (z. B. manche unendlichen Zustandsysteme oder schlecht gewählte Verfeinerungsstrategien) und die Wirksamkeit hängt von der Ausdrucksstärke verfügbarer Prädikate oder Verfeinerungsprimitiven ab.

Semantische Spannung

Zwischen Präzision und Skalierbarkeit: stärkere Abstraktionen erhöhen die Skalierbarkeit, erzeugen jedoch mehr spurious Gegenbeispiele; aggressives Verfeinern reduziert Spuriousität, riskiert aber kombinatorische Explosion.

Synthese

CEGAR ist ein geschlossener Verifikationszyklus: abstrahieren, prüfen, Gegenbeispiel analysieren, Abstraktion verfeinern, um spurious Verhalten zu eliminieren, und wiederholen bis zum Beweis oder einem realen Gegenbeispiel; dabei wird Soundness, Präzision und Ressourcenverbrauch abgewogen, wobei Nichtterminierung in Sonderfällen möglich ist.