Begriff
NuSMV
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Stell dir vor, du hast eine Zeitmaschine, die Milliarden von Möglichkeiten durchspielt. NuSMV ist so eine Maschine für Software-Modelle. Es ist der Nachfolger des legendären SMV (Symbolic Model Verifier). Du beschreibst dein System ("Ampel A schaltet nach 5 Sekunden auf Rot"). Du gibst ihm eine Regel ("Ampel A und B dürfen nie gleichzeitig Grün sein"). NuSMV prüft alle möglichen Zustände (Exhaustive Search). Es beweist mathematisch, ob die Regel verletzt werden kann. Wenn ja, zeigt es dir genau wie ("Trace: Nach 13 Schritten knallt es").
Merksatz: Ein Open-Source Symbolic Model Checker, der LTL und CTL unterstützt und primär für die Verifikation von Hardware-Designs und Protokollen mittels BDDs und SAT-Solvern eingesetzt wird.
Sprache: Eine simple State-Machine-Sprache.
MODULE main
VAR state : {ready, busy};
ASSIGN next(state) := case state=ready : busy; TRUE : ready; esac;
SPEC AG (state=busy -> AF state=ready) (Immer wenn Busy, dann irgendwann wieder Ready).
Kommandozeile: NuSMV file.smv.
Ausgabe: Specification adds up to TRUE. (Puh!).
1. BDDs vs. SAT
NuSMV kann beides.
- BDD (Binary Decision Diagrams): Komprimiert den Zustandsraum extrem. Gut für komplexe Logik, schlecht für zu viele Variablen.
- BMC (Bounded Model Checking) mit SAT: Nutzt SAT-Solver (wie MiniSat). Prüft nur bis Tiefe K ("Gibt es einen Fehler in den ersten 50 Schritten?"). Man kann wählen, was schneller ist.
2. Anwendungen
Hauptsächlich Hardware-Verifikation (Chips), Eisenbahn-Steuerungen und kritische Protokolle (Security).
1. Fairness Constraints: Justice & Compassion
In komplexen Systemen reicht es oft nicht zu sagen, was passieren muss. Man muss auch annehmen, dass der Scheduler "fair" ist. NuSMV unterstützt zwei Arten von Fairness:
- Justice: Eine Bedingung muss unendlich oft wahr sein (
JUSTICE state = ready). - Compassion: Eine stärkere Form: Wenn eine Bedingung unendlich oft angefragt wird, muss sie unendlich oft gewährt werden (
COMPASSION (request, grant)). Ohne diese Constraints würde NuSMV "Gegenbeispiele" finden, die in der Realität unmöglich sind (z. B. ein Prozess, der einfach nie dran kommt, obwohl er bereit ist).
2. Bounded Model Checking (BMC) Encoding
Wenn NuSMV im BMC-Modus (SAT) arbeitet, übersetzt es die LTL-Formel und die Zustandsübergänge für eine feste Tiefe $k$ in ein riesiges logisches Rätsel (CNF). Für eine Tiefe von 100 Schritten entsteht eine Formel mit Millionen von Variablen. NuSMV nutzt hocheffiziente Incremental SAT-Solving Techniken: Es prüft erst $k=1$, dann $k=2$, und nutzt die Erkenntnisse aus dem vorherigen Schritt, um den nächsten schneller zu lösen. Das erlaubt es, Fehler in Protokollen zu finden, bei denen klassische BDDs am Speicherverbrauch ("State Explosion") scheitern würden.
3. Counter-Example Generation
Wenn eine Spezifikation fehlschlägt, generiert NuSMV einen Trace. In der Forschung nutzt man dies für Counter-Example Guided Abstraction Refinement (CEGAR). Das Tool startet mit einem sehr groben (abstrakten) Modell des Systems. Findet NuSMV einen Fehler, prüft das System, ob dieser Fehler "echt" ist oder nur durch die Abstraktion entstand. Wenn er "fake" ist, nutzt das System den Trace, um das Modell automatisch zu verfeinern. Dies ist die Magie, mit der man Millionen Zeilen C-Code formal verifizieren kann, ohne jeden Pointer einzeln zu modellieren.
Quick-Check
Kann es Java prüfen?
Nein. Man prüft das Design ("Das Protokoll"), bevor man eine Zeile Code schreibt. Es gibt aber Tools, die C/Java nach SMV übersetzen (Bandera).Open Source?
Ja, aber strenge Lizenz (LGPL). Es kommt aus der Forschung (Trient, Italien & CMU, USA).Warum "Nu"?
"New" SMV. Das alte SMV war von Ken McMillan (CMU) und proprietär. NuSMV hat es befreit und erweitert.