Guten Morgen! Mein Name ist Eugen Sawin und ich werde den einführenden Vortrag halten zum Seminar Automatenkonstruktionen im Model Checking.

Meine Präsentation soll einen Überblick über die algorithmische Verifikation reaktiver Systeme basierend auf dem automaten-theoretischen Ansatz des Model Checkings geben.

==> 2

Modell M erfüllt PHI.

Das ist der Kern unserer Bemühungen. 

Doch was bedeutet das?

Wir übersetzen das in die Problemstellung der Verifikation.

==> 3

Gegeben sei ein Programm und dessen Spezifikation, das Problem lautet:

erfüllt jeder Pfad des Programms die Spezifikation?

Bevor wir an die Tat schreiten um das Problem zu lösen, 

möchte ich eine andere Frage beantworten.

Wieso das Ganze? Was ist der praktische Nutzen der Verifikation?

==> 4

Hard- und Softwaresysteme haben alle Bereiche der Industrie und damit auch unseren Alltag durchdrungen.

Sie bilden die Infrastruktur unserer Kommunikation, bieten Sicherheit und retten sogar Leben.

Und sie werden immer komplexer.

Die Industrie investiert viel Zeit und Geld in die Verifikation sicherheitskritischer Systeme und der Kernkomponenten anderer Systeme.

Die automatisierte Verifikation hat bereits in der Chip-Verifikation ihre praktische Anwendbarkeit gezeigt und ist in der Softwareindustrie stark gefragt.

==> 4(2)

Hier sind einige promitente Vertreter der Industrie, die Verifikationsmethoden einsetzten.

Also fangen wir an.

==> 5

Wenn ich sage: "Es ist dunkel." ist es nicht eindeutig, was ich damit ausdrücken möchte.

Ich könnte damit meinen "Es ist immer dunkel.", doch das spricht gegen unsere Intuition.

Wir denken als Erstes eher an "Es ist im Moment dunkel.", was auch stimmt, wenn ich damit mich damit auf die Folien beziehe (oder das Wetter draußen).

Wenn wir nach draußen schauen, können wir aus Erfahrung behaupten, dass es "notwendigerweise irgendwann dunkel wird."

Unsere Sprache erlaubt es uns auch kausale Zusammenhänge zu bilden, wie z.B. "Es ist dunkel, bis Jemand das Licht an macht."

Wir sehen, dass die natürliche Sprache nicht eindeutig ist und somit zur formalen Beschreibung ungeeignet.

Wie können wir unsere Sprache zähmen, ohne die Ausdruckskraft zu verlieren.

Nun, als Ersten machen wir das Licht wieder an!

==> 6

Nehmen wir den letzten Satz in einer allgemeineren Form als Beispiel.

Dieser Satz sollte allgemeingültig sein. 

Wie können wir die Aussage dieses Satzes formal festhalten?

Wir bedienen uns der Aussagenlogik und erweitern diese um eine weitere Verknüpfung.

==> 6(2)

Dabei sind p0 und p1 Elementaraussagen, sog. Atome, die entsprechend für "Es is dunkel" und "Es gibt licht" stehen.

Die neue Verknüpfung nennen wir trivialerweise "until" und notieren sie mit dem kalligraphischen U.

Halten wir die Syntax formal fest.

==> 7

Wir definieren die Syntax der linearen temporalen Logik mit Hilfe dieser Produktionen in Backus-Naur-Form.

Somit ist eine LTL-Formel entweder ein aussagenlogisches Atom, eine negierte Formel oder eine Disjunktion zweier Formeln. 

Das kennen wir bereits aus der Aussagenlogik.

Die Erweiterung sind das kalligraphische X, welches für "Next" steht und das "Until" aus dem Beispiel.

Diese Syntaxdefinition bildet das Fundament für weitere abgeleitete Verknüpfungen.

==> 7(2)

Schauen wir diese kurz an.

Eine klassische Ableitung für "Wahr" bietet sich durch p oder nicht p an.

Andere Ableitungen folgen analog.

Interessant sind hierbei wieder die modalen Verknüpfungen, Diamand und Box.

Diamant steht für eine Eventualität und Box steht für eine Notwendigkeit.

==> 8

Wir interpretieren LTL-Formeln über unendliche Sequenzen von Aussagen. 

Die Sequenz entspricht der zeitlichen Abfolge von Ereignissen in einem vorwärts gerichteteten diskreten Zeitverlauf.

Diese Interpretation heißt die Kripke-Semantik.

Das Kripke-Modell der LTL-Semantik besteht aus einer abzählbaren Menge von Zuständen, verknüpft duch die Erreichbarkeitsrelation und der Bewertungsfunktion V.

Da wir nur lineare Abfolgen betrachten, fällt die Erreichbarkeitsrelation einfach aus.

Von einem beliebigen Zustand ist jeweils nur dessen Nachfolger erreichbar.

Die Bewertungsfunktion liefert uns die Menge aller gültigen Atome für einen bestimmten Zustand.

Intuitiv sagt man, ein Atom p ist wahr zum Zeitpunkt i gdw. p in der Menge V(i) ist.

==> 9

Hier ist eine Veranschaulichung eines Beispielmodells.

Man sieht die Zustände s0 bis si und den Zeitverlauf durch die Relation R.

Für jeden Zustand ist die Rückgabe der Bewertungsfunktion als Menge positiver Atome abgebildet.

Wie man sieht, bietet LTL keine gute Grundlage für Science Fiction, weder Zeitreisen noch Parallelwelten sind möglich. 

Luminous Fennell wird in der nächsten Präsentation ein alternatives Modell anbieten, das in dieser Hinsicht etwas interessanter ist und algorithmisch effizienter.

==> 10

Die Erfüllbarkeit einer Formel zu einem Zeitpunkt i im Modell M ist folgendermaßen definiert:

- ein Atom p ist erfüllbar gdw. und p in der Menge V(i) ist

- eine negierte Formel PHI ist erfüllbar gdw. PHI nicht erfüllbar ist

- eine Disjunktion von PHI und PSI ist erfüllbar gdw. PHI oder PSI erfüllbar ist

- Next PHI ist erfüllbar gdw. PHI im darauffolgenden Zeitpunkt erfüllbar ist

- PHI Until PSI ist erfüllbar gdw. es einen Zeitpunkt k gibt, ab dem PSI erfüllbar ist und für alle Zeitpunkte vor k PHI erfüllbar ist.

Mit Hilfe der linearen temporalen Logik lassen sich Programmeigenschaften und derren zeitliche Abhängigkeiten genau beschreiben.

Als nächstes werden wir uns den Automaten widmen, die auf unendlichen Eingaben operieren.

==> 11

Wieso sind unsere Eingaben überhaupt unendlich?

Im Gegensatz zu terminierenden Programmen sind reaktive Systeme fortlaufende Prozesse.

Ein mal initiiert, verbleiben reaktive Systeme in einem aktiven Zustand und reagieren auf nebenläufige Eingaben.

Theoretisch betrachtet, arbeiten solche Systeme somit auf unendlichen Eingabesequenzen.

==> 12

Hier ist ein Beispielautomat, der auf unendlichen Eingaben arbeitet.

Sieht jemand auf Anhieb welche Sprache dieser Automat akzeptiert?

w1 ist eine Eingabe, der Überstrich soll eine unendliche periodische Wiederholung der Sequenz darstellen.

Bei dieser Eingabe werden die folgenden Zustände durchlaufen:

- wir starten in q0, lesen zwei b, somit bleiben wir für beide Eingaben in q0

- als nächstes lesen wir ein a, was uns in Zustand q1 versetzt

- danach folgt ein weiteres a, wir bleiben also in q1

- nun wiederholt sich die Sequenz, wir lesen zwei b, passieren dabei den akzeptierenden Zustand q2 und landen in q0, wo das Ganze von vorne beginnt

w2 bietet ein ähnliches Beispiel, jedoch pendeln wir diesmal zwischen q1 und q2 nach einer kurzen Phase.

Betrachtet man die grün hervorgehobenen Elemente, sieht man, dass der Zustand q2 gd. unendlich mal passiert wird, wenn die Sequenz ab unendlich mal in der Eingabe vorkommt.

==> 13

Nun wollen wir das Komplement des Automaten bilden.

Naiverweise gehe ich dabei vor, wie beim endlichen Automaten und kehre einfach die Akzeptanzeigenschaften der Zustände um.

Man sieht sofort, dass dies nicht der korrekte Komplementautomat ist, denn er akzeptiert immer noch Eingaben mit unendlichen Sequenzen von ab.

Abbildung (b) zeigt die korrekte Version. In Zustand q0 werden beliebige, endliche Sequenzen von as und bs gelesen. Akzeptiert wird ein Wort nur dann, wenn es ab einem bestimmten Zeitpunkt nur noch as oder bs enthält und das natürlich unendlich oft.

Wir sehen, dass der Komplement-Automat im Gegensatz zu dem Automaten nicht deterministisch ist.

Die Konstruktion dieser sog. Co-Büchi-Automaten wird Stephanie Embgen im Detail erörtern, deswegen werde ich auch nicht weiter darauf eingehen.

==> 14

Halten wir das Ganze formal fest.

Wenn ich von Automaten spreche, meine ich im allgemeinen nicht-deterministische Büchi-Automaten.

Diese bestehen aus: 

- einem endlichen Alphabet, in unserem Beispiel war das die Menge {a,b}.

- einer endlichen Menge von Zuständen

- einer Menge von Startzuständen, in unserem Beispiel war das lediglich der Zustand q0

- der Übergangsrelation Delta

- und einer endlichen Menge an akzeptierenden Zuständen, im Beispiel war das der Zustand q2, bzw q1 und q2 bei dem Co-Automat

==> 15

Ein Pfad eines Automaten auf einem Wort w, ist wie wir schon gesehen haben die unendliche Sequenz der dabei durchlaufenen Zustände.

Der erste Zustand muss ein Element der Startzustände sein.

Um bestimmte Elemente der Sequenz zu referenzieren, betrachten wir die Sequenz als Funktion RHO, wobei RHO(i) uns den durchlaufenen Zustand zum Zeitpunkt i zurückgibt.

==> 16

Zur Definition der Akzeptanz bedienen wir uns der Funktion inf, die für einen gegebenen Pfad RHO die Menge an Zuständen zurückgibt, die unendlich mal in RHO durchlaufen werden.

Basierend darauf sagen wir:

ein Pfad RHO eines Automaten A ist akzeptierend gdw. ein akzeptierender Zustand unendlich oft in RHO vorkommt.

Und dann können wir sagen: ein Automat A akzeptiert ein Wort w gdw. es einen Pfad von A auf w gibt, der akzeptierend ist.

==> 17

Die akzeptierte Sprache eines Automaten ist einfach die Menge aller akzeptierten Eingaben.

==> 18

Es existiert eine verallgemeinerte Form des Büchi-Automaten, welche bei der Automatenkonstruktion Vorteile bietet.

Der Unterschied liegt in der Akzeptanzbedingung.

Der verallgemeinerte Büchi-Automat definiert diese über eine endliche Menge von Mengen von akzeptierenden Zuständen.

Ein Pfad RHO eines solchen Automaten ist akzeptierend gdw. es einen Zustand aus jeder Menge Fi aus dieser Mengenfamilie gibt, der unendlich oft in RHO vorkommt.

Wenn man sich die Definition anschaut, wird es offensichtlich, dass die akzeptierte Sprache eines verallgemeinerten Automaten equivalent ist zu der Schnittmenge der akzeptierten Sprachen von k Büchi-Automaten. 

==> 19

Wir kennen nun die Sprache zur Spezifikation von Systemeigenschaften und wir haben Automaten kennengelernt, die auf unendlichen Eingaben arbeiten. 

Für die automaten-theoretische Methode müssen einen Automaten konstruieren anhand einer Systemspezifikation in der linearen temporalen Logik.

In meiner Arbeit geschieht dies über den sog. Fischer-Ladner-Abschluss.

In der Arbeit von Rob Gerth wird eine on-the-fly Konstruktion der Produktautomaten vorgestellt.

Darauf wird Christian Schilling heute Nachmittag genauer eingehen.

==> 20

Die Konstruktion des Systemautomaten ist eindeutig einfacher.

Sei das Programm in dieser Form gegeben, mit einer Menger von Zuständen, einer Startzustand, einer Übergangsrelation und der Bewertungsfunktion, welche für jeden Zustand die Menge an gültigen Atomen liefert.

Eine Berechnung des Programms ergibt einen Pfad, der aus der Sequenz der Mengen besteht, die die Bewertungsfunktionen für den jeweiligen Zustand zurückgibt.

Daraus konstruieren wir den Systemautomaten.

Zu beachten ist, dass die Menge der akzeptierenden Zustände gleich der Menge der Zustände ist, somit ist jeder Pfad des Automaten akzeptierend.

==> 21

Daraus folgt direkt folgender Satz: die akzeptierte Sprache eines Systemautomaten ist gleich der Menge aller Pfade des Automaten.

==> 22

Erinnern wir uns and die Problembeschreibung vom Anfang.

Übersetzt in die Automatentheorie bedeutet das:

Ein System entspricht der Spezifikation, wenn die akzeptierte Sprache des Systemautomaten in der akzeptierten Sprache des Formelautomaten enthalten ist.

Eine mengentheoretische Umformung gibt uns folgende Form:

Ein System entspricht der Spezifikation, wenn der Schnitt der akzeptierten Sprache des Systemautomaten mit der akzeptierten Sprache des Automaten für die negierte Formel gleich der leeren Menge ist.

Die graphentheoretische Methode erlaubt uns nun die Produktautomaten als Graphen zu interpretieren und das Problem durch die Bildung der Zusammenhangskomponente zu lösen.

Die effiziente on-the-fly Methode sucht stattdessen iterativ nach Zyklen.

Wir wissen wie man den Systemautomaten konstruiert und dessen akzeptierte Sprache bestimmt.

Wir wissen wie man Spezifikationen mit Hilfe der linearen temporalen Logik beschreibt.

In den folgenden Vorträgen werden wir u.a. erfahren, wie man den Formelautomaten bildet und effiziente Methoden kennenlernen, wie man die sog. Zustandsexplosion vermeidet.

==> 23

Zum Schluss habe eine kleine Auswahl an Arbeiten vorbereitet.

Meine Arbeit basiert hauptsächlich auf Madhavan Mukund's Veröffentlichung, wobei ich einige Definitionen von Vardi's Paper bevorzugt habe.

Wie bereits erwähnt beschreibt die Arbeit von Rob Gerth und den anderen die on-the-fly Methode.

Das Handbook of Modal Logik kann ich allen empfehlen die sich mehr mit modalen Logiken beschäftigen wollen.

==> 24

Und alle, die eine sehr motivierende, kurze und pregnante Einführung in das präsentierte Thema lesen möchten kann ich nur Vardi's Automated Verification: Graphs, Logic and Automata empfehlen.

Ich hoffe mein Vortrag hat einen Überblick über die Thematik geboten und freue mich auf die weiteren Vorträge, die von mir hinterlassene Lücken füllen oder ganz andere Aspekte einbringen.

Vielen Dank!