Verifikation und Model Checking: Eine Einführung mit aktuellen Beispielen aus der Praxis

Einleitung: Warum Verifikation heute wichtiger denn je ist

In einer Welt, in der Software in Herzschrittmachern, autonomen Fahrzeugen und KI-gesteuerten Systemen steckt, wird die Korrektheit von Programmen überlebenswichtig. Der Kurs Compsys705 beschäftigt sich genau damit: Wie beweist man, dass ein System sich so verhält, wie es soll? Im Folgenden lernst du die zentralen Konzepte des Model Checkings und der formalen Verifikation kennen – angereichert mit aktuellen Bezügen zur Praxis.

Grundlagen des Model Checkings

Model Checking ist ein automatisiertes Verfahren, um zu prüfen, ob ein endliches Zustandsmodell eine gegebene Spezifikation erfüllt. Die Spezifikation wird oft in temporalen Logiken wie CTL (Computation Tree Logic) oder LTL (Linear Temporal Logic) formuliert. Ein bekanntes Beispiel ist die Formel AG(p ⇒ AX(p ∧ q)), die besagt: „Immer wenn p gilt, dann gilt im nächsten Schritt auch p und q.“ Solche Formeln werden genutzt, um Sicherheitseigenschaften von Systemen zu garantieren.

Beispiel aus der Praxis: KI-Sicherheit

Stell dir vor, du entwickelst einen KI-Assistenten für ein Smart-Home-System. Eine wichtige Eigenschaft könnte sein: „Immer wenn die Kamera eine Person erkennt, wird im nächsten Schritt das Licht eingeschaltet und ein Logeintrag erstellt.“ In CTL würde das heißen: AG(erkannt ⇒ AX(licht ∧ log)). Mit Model Checking kannst du automatisch prüfen, ob dein System diese Eigenschaft für alle möglichen Abläufe einhält.

CCS-Prozesse und ihre Modellierung

Im Calculus of Communicating Systems (CCS) werden Systeme als Prozesse mit Aktionen modelliert. Zum Beispiel: P = a.P1 + b.c.P2 bedeutet, dass Prozess P entweder die Aktion a ausführt und dann zu P1 wird, oder die Aktion b, gefolgt von c, und dann zu P2. Solche Prozesse können parallel geschaltet werden und über Kanäle kommunizieren. Das ist besonders nützlich für die Modellierung von Protokollen oder nebenläufigen Systemen.

Aktueller Bezug: Smartphone-Apps

Moderne Messenger-Apps wie Signal oder WhatsApp nutzen ähnliche Konzepte zur Modellierung von Nachrichtenflüssen. Ein Prozess könnte den Versand einer Nachricht darstellen, ein anderer den Empfang. Mit CCS kannst du nachweisen, dass keine Nachricht verloren geht oder in falscher Reihenfolge ankommt.

Kripke-Strukturen und CTL-Formeln

Eine Kripke-Struktur ist ein gerichteter Graph, dessen Knoten mit atomaren Aussagen beschriftet sind. Sie dient als Modell für temporale Logiken. In der Prüfung Compsys705 musst du oft gültige CTL-Formeln identifizieren und in eine äquivalente Form umwandeln, die nur eine minimale Menge von Operatoren verwendet. Zum Beispiel kann man AFp („auf jedem Pfad gilt irgendwann p“) durch ¬EG¬p ersetzen.

Übungsaufgabe: Welche Formeln sind gültig?

Gegeben sei eine Kripke-Struktur mit AP={p1,p2,p3}. Prüfe, ob folgende Formeln gelten: AF(p1 ⇒ AXp2) oder AF(p1 ⇒ FG(p1Up2)). Beachte: Nicht alle Formeln sind in jeder Struktur gültig. Du musst die Semantik der Operatoren verstehen: AF bedeutet „auf allen Pfaden irgendwann“, AX „in allen nächsten Zuständen“ und FG „ab einem Zeitpunkt immer“. Mit etwas Übung erkennst du schnell, welche Formeln sinnvoll sind.

Automaten und Sprachen

In der Vorlesung lernst du auch, wie man Sprachen mit Automaten akzeptiert. Ein endlicher Automat besteht aus Zuständen und Übergängen, die mit Buchstaben eines Alphabets Σ beschriftet sind. Die Frage „Wird bbabab* von Automat A1 akzeptiert?“ testet dein Verständnis von regulären Ausdrücken und Automaten. Solche Aufgaben sind typisch für den zweiten Teil der Prüfung.

Beispiel aus der Welt der Spiele

Stell dir vor, du programmierst einen Gegner in einem Videospiel. Der Automat könnte die verschiedenen Angriffsmuster beschreiben: a für Angriff, b für Blocken, c für Ausweichen. Die Frage, ob eine bestimmte Sequenz (z.B. „blocken, blocken, angreifen, ausweichen“) möglich ist, entspricht genau der Akzeptanz eines Wortes durch einen Automaten.

Timed Automata und Echtzeitsysteme

In eingebetteten Systemen wie Herzschrittmachern oder Airbags spielt die Zeit eine entscheidende Rolle. Timed Automata erweitern endliche Automaten um Uhren, die in Echtzeit laufen. Typische Clock Constraints sind Bedingungen wie z >= 12 ∧ x == 20 oder x - y = 1000. In der Prüfung musst du entscheiden, ob solche Constraints gültig sind – also ob sie sich als logische Formeln über reelle Zahlen ausdrücken lassen. Beachte: z == x + 5 ist gültig, x - y = 1000 auch, aber x < z < y ist nicht direkt als einzelne Bedingung formulierbar.

Aktuelles Beispiel: Pacemaker-Sicherheit

Ein Forschungsschwerpunkt ist die Absicherung von medizinischen Geräten gegen Hackerangriffe. Ein Runtime-Monitor könnte einen Timed Automaton verwenden, um ungewöhnliche Signale von einem EKG-Sensor zu erkennen. Wenn der Monitor eine Sequenz von Signalen sieht, die nicht dem normalen Herzrhythmus entspricht, könnte er Alarm schlagen. In der Prüfung sollst du so einen Automaten skizzieren.

Bounded Model Checking mit Z3

Ein praktisches Werkzeug für die Verifikation ist der SMT-Solver Z3. Damit kannst du logische Formeln lösen und nach Gegenbeispielen suchen. In der Prüfung wird oft nach symbolic bounded model checking gefragt: Du modellierst das System und die Eigenschaft als logische Formeln und prüfst mit Z3, ob es eine Verletzung innerhalb einer beschränkten Anzahl von Schritten gibt.

Beispiel: Z3-Code für eine Swap-Funktion

Gegeben seien zwei Funktionen swap1 und swap2, die die Werte von a und b vertauschen sollen. Mit Z3 kannst du prüfen, ob sie tatsächlich das tun, was sie sollen. Der Code dazu:

from z3 import *
a, b, tmp = Ints('a b tmp')
s = Solver()
# swap1: tmp = b; b = a; a = tmp
s.add(And(a == 3, b == 5))  # Beispielwerte
s.add(tmp == b)
s.add(b == a)
s.add(a == tmp)
# Prüfen, ob a=5 und b=3
s.add(And(a == 5, b == 3))
print(s.check())  # sat, wenn swap korrekt ist

Mit ForAll und Exists kannst du auch allgemeine Aussagen über alle möglichen Werte prüfen.

Zusammenfassung und Prüfungsvorbereitung

Die Prüfung Compsys705 deckt ein breites Spektrum ab: von CCS und Kripke-Strukturen über Automaten und Timed Automata bis hin zu praktischem Model Checking mit Z3. Um gut vorbereitet zu sein, solltest du:

• Die Syntax und Semantik von CTL-Formeln beherrschen, insbesondere die Umwandlung in äquivalente Formen.
• Üben, ob ein Wort von einem Automaten akzeptiert wird.
• Verstehen, welche Clock Constraints in Timed Automata gültig sind.
• Einfache Z3-Programme schreiben können, um Eigenschaften zu verifizieren.

Mit diesen Kenntnissen bist du bestens gerüstet für die Prüfung und hast gleichzeitig einen Einblick in hochaktuelle Themen der Softwareverifikation – von KI-Sicherheit bis hin zu medizinischen Geräten.