EinführungZiel des Model Checkings ist die Überprüfung einer Systembeschreibung auf die Erfüllung von Anforderungen mittels einer Software. Die automatische Überprüfung erledigt der Model Checker. Zu untersuchende Systeme können mit Hilfe von Zustandsübergangssystemen modelliert werden. Diese lassen sich übersichtlich als Graphen darstellen (Abb. 1). Zustandsübergangssysteme bestehen aus folgenden Komponenten:● Zustände (im Beispiel s0, s1, s2)● Transitionen zwischen den Zuständen (Pfeile)● Zustandsaussagen (im Beispiel p, q, r)Durch Ausführung des Systems entsteht ein Berechnungsbaum, der alle möglichen unendlichen Abläufe des Systems darstellt (Abb. 2). Abläufe werden Pfade genannt.Beim Model Checking müssen Anforderungen an das System formuliert werden. Hierfür werden temporale Logiken genutzt. Diese sind eine Erweiterung der Aussagenlogik um temporale Operatoren. Sie ermöglichen zeitliche Einschränkungen der Gültigkeit von Aussagen

(z.B. „immer“ oder „manchmal“). Temporale Logik ist eine spezielle modale Logik (Verwendung von Modaloperatoren zum Ausdruck von Modalitäten).Es existieren die folgenden temporalen Logiken:● LTL - Linear-time Temporal Logic (~1960)● CTL - Computation Tree Logic (~1980)● CTL* (1986)Im folgenden Abschnitt wird CTL vorgestellt.

CTL – Computation Tree LogicEigenschaften von CTL:● die Zeit wird als Baum aufgefasst● Verzweigung in unterschiedliche Versionen

der Zukunft (Pfade)● Aussagen können auf bestimmte Pfade

beschränkt werdenCTL-Formeln beziehen sich auf einen Zustand s im Modell M. Für eine Formel φ überprüft der Model Checker die ErfüllbarkeitsrelationM ,s²

Meist wird der Model Checker zur Beantwortung der Frage eingesetzt, ob alle Zustände des Modells eine bestimmte Anforderung (=CTL-Formel) erfüllen. Die Antwort ist entweder positiv oder negativ. Bei einem negativen Ergebnis wird derjenige Systemdurchlauf ausgegeben, welcher die Anforderung verletzt hat.

Aufbau von CTL-Formeln

CTL-Formeln bestehen aus den folgenden Elementen● Konstanten true und false● atomare Zustandsaussagen● boolesche Operatoren (not, and, or,

Implikation)● zusammengesetzte Operatoren, bestehend

aus Pfadquantoren und TemporaloperatorenSyntax der CTL-Formeln φ in Backus-Naur-Form:

http://www.se.uni-hannover.de Stand: 27.07.2006

Abb. 1: Zustandsübergangssystem

Abb. 2: Berechnungsbaum (computation tree)

Kurz & Gut

Model Checking I - CTLvon Florian Heyer

Kurz & Gut: Model Checking I – CTL von Florian Heyer

φ ::= | T | p | (¬φ) | (φ φ) | (φ φ) | (φ → φ) | ⊥ ∧ ∨

<compositeOp>

<compositeOp> ::= A<temporalOp> | E<temporalOp>

<temporalOp> ::= X φ | F φ | G φ | [φ U φ]

Bedeutung der Operatoren

Zusammengesetzte Operatoren (Elemente der Klasse <compositeOp>) bestehen aus Paaren von Pfadquantor und Temporaloperator:Pfadquantoren● A - All: Aussage gilt für alle in Zustand s beginnenden

Pfade

● E - Exists: Aussage gilt für mindestens einen Pfad, der in Zustand s beginnt

Temporaloperatoren (bezogen auf die Zukunft)● unär

- X – neXt: Aussage gilt im nächsten Zustand

- F – Future: Aussage gilt in Zustand in der Zukunft

- G – Global: Aussage gilt für kompletten Pfad

● binär

- U – Until: Aussage1 gilt für alle Zustände bis Aussage2 gilt und Aussage2 wird gelten

Es ergeben sich somit die folgenden acht zusammengesetzten Operatoren (Kombination aller Pfadquantoren mit allen Temporaloperatoren):

Operator BedeutungAX φ gilt gdw. in jedem nächsten Zustand φ giltAF φ gilt gdw. man immer einen Zustand erreicht,

der φ erfülltAG φ gilt gdw. in allen Pfaden φ gilt

A[φ U ψ] gilt gdw. immer φ bis zum ersten Auftreten von ψ gilt

EX φ gilt gdw. in (mind.) einem nächsten Zustand φ gilt

EF φ gilt gdw. in (mind.) einem der folgenden Zustände φ gilt

EG φ gilt gdw. es (mind.) einen Pfad gibt, so dass φ entlang des ganzen Pfades gilt

E[φ U ψ] gilt gdw. es einen Pfad gibt, für den gilt: bis zum ersten Auftreten von ψ gilt φ

Der Model CheckerImplementierung der Erfüllbarkeitsrelation

Die Erfüllbarkeitsrelation kann leicht fallweise und rekursiv definiert werden: Für jedes Element der CTL-Formeln kann die Erfüllbarkeit aus der

Erfüllbarkeit der enthaltenen Terme ermittelt werden.

Semantische Äquivalenz von CTL-Formeln

Zwei CTL-Formeln sind dann äquivalent, wenn ein beliebiger Zustand aus einem beliebigen Modell, der die eine Formel erfüllt, auch die andere Formel erfüllt. Dies ermöglicht die Ersetzung von Ausdrücken durch äquivalente Ausdrücke. Auf diese Weise kann die Menge der zusammengesetzten Operatoren auf eine Untermenge beschränkt werden, mit denen die restlichen Operatoren ausdrückbar sind. Ein Beispiel für eine solche adäquate Menge ist AF, EU, EX.Dies erleichtert die Implementierung des Model Checkers, da eine adäquate Menge von Operatoren ausgesucht werden kann, deren Implementierung einfach ist.

Algorithmen für die Verifikation

Markierungsalgorithmus (labelling algorithm)● Eingabe: ein Modell M und eine CTL-Formel

φ● Ausgabe: alle Zustände in M, die φ erfüllen● Effizienz nach Optimierung: Aufwand ist linear

zur Größe von Formel und ModellSymbolisches Model Checking● verwendet OBDD (ordered binary decision

diagrams)

Anwendungen

Siehe Quelle [2].

Bewertung Model CheckingVorteile Nachteile

● wird durch vielfältige Tools gut unterstützt

● wird in der Praxis eingesetzt

● ist aktuelles Lehr- und Forschungsthema

● Abstraktion des realen Systems in ein formales Modell ist schwierig

● CTL-Formeln höchst komplex

● state explosion problem

http://www.se.uni-hannover.de Stand: 27.07.2006

Literatur:[1] Michael Huth, Mark Ryan: „Logic in Computer Science

- Modelling and Reasoning about Systems“, Cambridge University Press, 2004.

[2] Liste von Applikationen zum Thema Model Checking:http://www.pst.ifi.lmu.de/lehre/SS06/modelcheck/mc-list.html