Universität Stuttgart Fakultät Informatik Studiengang: Softwaretechnik Prüfer: Prof. Dr. Kurt Rothermel Betreuer: Dr. Cora Burger Stella Papakosta Beginn am: 01. Dezember 2001 Beendet am: 31. Mai 2002 CR-Klassifikation: C.2.1, C.2.2, D.2.2, D.2.4, D.3.1, F.3.1, I.6.3, I.6.4, J.6 Diplomarbeit Nr. 1980 Evaluation von Systemen zur Korrektheitsuntersuchung am Beispiel von Konsistenz- erhaltungsprotokollen Sören Schneider Institut für parallele und verteilte Höchstleistungsrechnersysteme Breitwiesenstraße 20-22 D-70565 Stuttgart Inhaltsverzeichnis 2 Inhaltsverzeichnis 1 Einleitung 8 1.1 Motivation 8 1.2 Aufgabenstellung 9 1.3 Kapitelübersicht 10 2 Grundlagen und Hintergründe 11 2.1 Model Checking 11 2.1.1 Verteilte & Parallele Systeme 11 2.1.1.1 Fehler 12 2.1.1.2 Validierung (Simulation und Verifikation) 14 2.1.1.3 Modellierung und Spezifikation 16 2.1.2 Transitionssysteme 17 2.1.2.1 Grundlegendes 17 2.1.2.2 Parallelität 18 2.1.2.3 Sicherheits- und Lebendigkeitseigenschaften 19 2.1.2.4 Analyse von Transitionssystemen 20 2.1.3 Spezifikationssprachen 21 2.1.3.1 PROMELA 23 2.1.4 Temporale Logik 24 2.1.4.1 Computation Tree Logic (CTL) 24 2.1.4.2 Linear Temporal Logic (LTL) 26 2.2 Computergestützte Gruppenarbeit (CSCW) 27 2.2.1 Begriffsklärung 27 2.2.2 Klassifizierung 28 2.2.3 Wichtige Konzepte 29 3 Bewertungskriterien der Verifikationstools 30 3.1 Grundlegendes 30 3.2 Bewertungskriterien 30 3.2.1 Verifikationstools 30 3.2.2 Spezifikationssprachen 32 3.2.3 Lehre 32 Inhaltsverzeichnis 3 3.3 Erläuterung der Bewertungskriterien 32 3.3.1 Verifikationstools 32 3.3.2 Spezifikationssprachen 35 3.3.3 Lehre 37 3.4 Gewichtung der Bewertungskriterien 39 3.4.1 Verifikationstools 39 3.4.2 Spezifikationssprachen 40 3.4.3 Lehre 40 4 Verifikationstools 42 4.1 Anforderungen 42 4.2 Auswahl der zu evaluierenden Verifikationstools 43 4.3 Ausgewählte Verifikationstools 44 5 Nebenläufigkeitskontrolle 47 5.1 Grundlegendes 47 5.2 Mechanismen 48 5.3 Der Grove-Algorithmus im Detail 50 5.3.1 Grundlagen 50 5.3.2 Definition und Ablauf 51 5.3.3 Beispiel 54 6 Charakteristika von Protokollen zur Konsistenzerhaltung 56 6.1 Kriterien zur Ermittlung der Protokollcharakteristik 56 6.2 Erläuterung der Bewertungskriterien 57 6.3 Gewichtung der Kriterien 58 7 Evaluation 59 7.1 Grundlegendes 59 7.2 UPPAAL 60 7.2.1 Verifikationstools 60 7.2.2 Spezifikationssprache 64 7.2.3 Lehre 65 7.3 Spin 67 7.3.1 Verifikationstools 67 7.3.2 Spezifikationssprache 70 7.3.3 Lehre 72 Inhaltsverzeichnis 4 7.4 Verisoft 74 7.4.1 Verifikationstools 74 7.4.2 Spezifikationssprache 77 7.4.3 Lehre 78 7.5 Ergebnisse 80 7.5.1 Verifikationstools 80 7.5.2 Grove-Algorithmus 83 8 Zusammenfassung und Ausblick 85 8.1 Zusammenfassung 85 8.2 Ausblick 85 9 Literaturverzeichnis 87 9.1 Online ­ Literatur 87 9.2 Offline ­ Literatur 88 A Funktionsumfang und Spezifikationssprachen der getesteten Verifikationstools 91 A.1 UPPAAL 91 A.2 SPIN 94 A.3 Verisoft 99 B Modellierung des Grove-Algorithmus 101 B.1 UPPAAL 101 B.2 SPIN 106 B.3 Verisoft 114 C Überblick über existierende Verifikationstools 120 Abbildungsverzeichnis 5 Abbildungsverzeichnis Abb.1-1: Problem(e) bei der gemeinsamen Bearbeitung von Dokumenten 8 Abb.2-1: Beispiel für einen Deadlock 13 Abb.2-2: schematische Darstellung von CTL 26 Abb.2-3: Unterstützungsfunktionen [Sch00] 28 Abb.4-1: Simulator (UPPAAL) 44 Abb.4-2: graphisches Interface von Spin (XSpin) 45 Abb.4-3: Simulator (Verisoft) 46 Abb.5-1: Klassifizierung von Verfahren zur Nebenläufigkeitskontrolle 47 Abb.5-2: Beispiel einer Gittertopologie 50 Abb.5-3: Ablauf des Grove-Algorithmus 53 Abb.5-4: Beispiel für den Grove-Algorithmus 55 Abb.7-1: Skalierung zu visualisierender Variablen (Darstellungsfehler) 61 Abb.7-2: Lernkurve (UPPAAL) 66 Abb.7-3: Lernkurve (Spin) 73 Abb.7-4: Lernkurve (Verisoft) 79 Abb.B-1: Prioritätsberechnung (Prozess ­ member) 102 Abb.B-2: Warteschlange Qi (Prozess ­ member) 103 Abb.B-3: Operationslogbuch Li (Prozess ­ member) 103 Abb.B-4: Operationsgenerierung (Prozess ­ genInput) 104 Abb.B-5: Operationsgenerierung (Prozess ­ member) 104 Abb.B-6: Operationspropagierung bzw. -sendung (Prozess ­ sendOperation) 104 Abb.B-7: Operationspropagierung bzw. -sendung (Prozess ­ member) 105 Abb.B-8: Operationsempfang (Prozess ­ member) 105 Abb.B-9: Operationstransformation (Prozess ­ member) 105 Abb.B-10: Operationsausführung (Prozess ­ member) 106 Tabellenverzeichnis 6 Tabellenverzeichnis Tab 3-1: Gewichtung der Bewertungskriterien (Verifikationstools) 40 Tab 3-2: Gewichtung der Bewertungskriterien (Spezifikationssprachen) 40 Tab 3-3: Gewichtung der Bewertungskriterien (Lehre) 41 Tab 6-1: Gewichtung der Bewertungskriterien (Konsistenzerhaltungsprotokolle) 58 Tab.7-1: Bewertungsmaßstab für die Kriterien 59 Tab.7-2: Bewertungsergebnisse (Verifikationstools) 81 Tab.7-3: Bewertungsergebnis (Spezifikationssprachen) 81 Tab.7-4: Bewertungsergebnis (Lehre) 82 Tab.7-5: Verifikationsergebnis des Grove-Algorithmus (Spin) 84 Tab.C-1: gefundene (nicht kommerzielle) Verifikationstools (Überblick) 122 Tab.C-2: gefundene (kommerzielle) Verifikationstools (Überblick) 122 Tab.C-3: gefundene (nicht kommerzielle) Verifikationstools (Charakterisierung) 126 Tab.C-4: gefundene (kommerzielle) Verifikationstools (Charakterisierung) 127 Abkürzungen 7 Abkürzungen API Application Programming Interface CSCW Computer Supported Cooperative Work CTL Computation Tree Logic EDV elektronische Datenverarbeitung FIFO first in first out GUI Graphical User Interface i.Allg. im Allgemeinen i.d.R. in der Regel LTL Linear Temporal Logic MSC Message Sequence Chart Prtkl. Protokollen SDL Specification and Description Language TS Teilnehmersystem u.v.m. und vieles mehr VS Verteilte Systeme vs. versus Kapitel 1 - Einleitung 8 Kapitel 1 1 E EIINNLLEEIITTUUNNG G In diesem Kapitel wird einleitend zum Thema der Diplomarbeit das Problem der Er- stellung, Simulation und Verifikation von Protokollen zur Konsistenzerhaltung be- schrieben. Anschließend wird ein kurzer Überblick über die Aufgabenstellung und die inhaltliche Gliederung der Arbeit gegeben. 1.1 Motivation Ein großes Problem bei der gemeinsamen Erstellung von Dokumenten durch mehre- re Personen betrifft die Konsistenz der Daten, denn jeder sollte beliebige Änderun- gen vornehmen können. Dies gilt in besonderem Maß, wenn Benutzer mit mobilen Endgeräten beteiligt sind, welche nicht permanent mit den Datenservern verbunden sind und somit die meiste Zeit Offline arbeiten. D.h. die Daten werden lokal bearbei- tet und Änderungen eher abschnittsweise, auf einmal in das gemeinsame Dokument eingebracht. Um die dabei nicht zwangsweise entstehenden Inkonsistenzen zu kon- trollieren und zu beheben, wurden bereits eine Reihe von Protokollen zur Konsis- tenzerhaltung (z.B. Grove, 2-Phasen-Sperren) vorgeschlagen. Co|la Co|la das; -[s], -s die; -[s], -s Person A Person B Co|la das; -[s], -s od. die; -, -s Co|la (ugs. kurz für Coca-Cola) der; -[s], -s ((( ((( ((( ((( Person C Konsistenz ? Konsistenz ? Abb.1-1: Problem(e) bei der gemeinsamen Bearbeitung von Dokumenten Diese, mit zunehmender Komplexität, verwendeten Protokolle bestimmen in großem Maß den reibungslosen Ablauf bei der gemeinsamen Erstellung/Bearbeitung von Dokumenten. Deren Zuverlässigkeit scheint eine unabdingbare Forderung zu sein. Der Nachweis der fehlerfreien Funktion" (Verifikation) ist jedoch ein sehr schwieriges Unterfangen. Kapitel 1 - Einleitung 9 Die am häufigsten verwendeten Verifikationstechniken sind Test (z.B. Blackbox- und Glasboxtest) und Simulation. Diese Verfahren sind jedoch sehr aufwändig und ga- rantieren keine 100%ige Fehlerfreiheit. Anfang der 80er Jahre wurde eine Methode entwickelt, welche es erlaubt, die logi- sche Struktur komplexer Systeme/Protokolle vollautomatisch zu analysieren und den Nachweis der gestellten Anforderungen zu erbringen. Diese Technik wird Model Checking genannt und ist Grundbaustein moderner Verifikationswerkzeuge (z.B. Spin, Verisoft, UPPAAL, ...). Diese Werkzeuge erlauben die Modellierung und Verifi- kation von parallelen Systemen, Kommunikationsprotokollen und u.v.m. Dabei werden die unterschiedlichsten Methoden verwendet. Beispielsweise besitzt Spin eine eigene Spezifikationssprache, mit welcher z.B. Kommunikationsprotokolle nachgebildet werden können, wogegen Verisoft auf dem Sourcecode arbeitet und die gestellten Forderungen direkt im zu überprüfenden System/Protokoll definiert werden können. Um die an ein zu verifizierendes System gestellten Forderungen präzise formulieren und überprüfen (z.B. Finden von Deadlocks (Verklemmungen) und unerreichbaren" Unterroutinen) zu können, verwenden die einzelnen Werkzeuge gesonderte oder integrierte Spezifikationsformalismen (z.B. LTL, CTL). 1.2 Aufgabenstellung Ziel der Arbeit ist die Bewertung von Systemen zur Korrektheitsuntersuchung am Beispiel von ausgewählten Konsistenzerhaltungsprotokollen. Dazu sind die folgen- den Teilaufgaben zu bearbeiten: 1) Erstellen eines Zeitplanes 2) Einarbeitung in Spezifikationssprachen und Validationswerkzeuge 3) Aufstellen von Kriterien im Hinblick auf den Einsatz in der Lehre und Auswahl eines Werkzeuges 4) Spezifikation von Korrektheitsanforderungen bei Konsistenz unter besonderer Berücksichtigung mobiler Benutzer 5) Einarbeitung in Protokolle zur Konsistenzerhaltung 6) Aufstellen von Kriterien und Auswahl eines typischen Vertreters 7) Spezifikation dieses Protokolls in der ausgewählten Spezifikationssprache 8) Anwendung des Verifikationswerkzeuges zum Test der Korrektheitsanforde- rungen 9) Schriftliche Ausarbeitung (Dokumentation der Schritte 2 bis 8 der Aufgaben- stellung sowie der Verifikationsergebnisse) 10) Vortrag im VS-Kolloquium Vorgehensweise Nach der Auswahl und der Einarbeitung in die Verifikationswerkzeuge sowie in die Spezifikationssprachen (z.B. Spin/PROMELA) und Protokolle werden die Kriterien für die Bewertung der Systeme zur Korrektheitsuntersuchung ausgearbeitet. Später werden ausgewählte Vertreter der Werkzeuge am Beispiel eines Konsistenzerhal- tungsprotokolls anhand der zu evaluierenden Kriterien analysiert und bewertet. Kapitel 1 - Einleitung 10 1.3 Kapitelübersicht Der Einleitung folgend werden im 2. Kapitel die Grundlagen und Hintergründe zum Verständnis des Model Checking's und dessen praktische Anwendung am Beispiel von Computergestützter Gruppenarbeit (CSCW) gelegt. Dazu werden unter anderem Verteilte & Parallele Systeme, mögliche Fehler, Validierung & Simulation sowie Tran- sitionssysteme und verwendete Spezifikationssprachen vorgestellt. Anschließend werden wichtige Kriterien der Computergestützten Gruppenarbeit näher beleuchtet. Das 3. Kapitel beschreibt die Kriterien, anhand derer die Auswahl der Verifikations- tools getroffen sowie deren Evaluation durchgeführt wird. Das nächste Kapitel gibt einen kleinen Überblick über die Vielzahl vorhandener Tools und fasst die wichtigsten Anforderungen an Verifikationstools nochmals kurz zu- sammen. Am Ende werden die ausgewählten Werkzeuge vorgestellt. In den Kapiteln 5 und 6 wird auf die Eigenschaften und Mechanismen der Nebenläu- figkeitskontrolle, den als Vertreter der Konsistenzerhaltungsprotokolle ausgewählten Grove-Algorithmus und die Kriterien zur Charakterisierung von Konsistenzerhal- tungsprotokollen eingegangen. Das Kapitel 7 beschreibt schließlich die Evaluation der Verifikationstools anhand der aufgestellten Bewertungskriterien sowie die Resultate bzgl. der Tools und des zum Testen verwendeten Grove-Algorithmusses. Die Kapitel 8 und 9 beinhalten eine Zusammenfassung der Ergebnisse und das Lite- raturverzeichnis. In Anhang werden der Funktionsumfang der getesteten Verifikationstools und dessen Spezifikationssprachen beleuchtet und anschließend die Realisierung des Grove- Algorithmus mit Hilfe dieser Tools beschrieben. Kapitel 2 ­ Grundlagen und Hintergründe 11 Kapitel 2 2 G GRRUUNNDDLLAAG GE EN N U UN ND D H HIINNTTEERRG GR RÜ ÜN ND DE E Computersysteme gewinnen vor allem in den letzten Jahren immer mehr an Bedeu- tung. Wir vertrauen auf digitale Kontroller zur Überwachung unserer Autos, Flugzeu- ge und Industrieanlagen. Digitale Technologien ersetzen analoge Komponenten z.B. in der Telekommunikation. Die Entwicklung komplexer Sicherheits- und Kommunika- tionsprotokolle ermöglicht E-Commerceanwendungen und eröffnet die Möglichkeit der Teamarbeit in Verteilten Systemen. Überall dort sind eine Analyse der logischen Struktur und ein Nachweis der an die o.g. Systeme gestellten Anforderungen notwendig. Dazu werden in den meisten Fäl- len abstrakte Modelle herangezogen, welche die relevanten Funktionen des Systems repräsentieren (formale Definition der Systemeigenschaften). Mit Hilfe von Verifikati- onstools kann deren Verhalten simuliert und die an sie gestellte Anforderungen nach- gewiesen werden. Der Fokus dieser Diplomarbeit liegt auf der Evaluation solcher Verifikationstools am Beispiel von Konsistenzerhaltungsprotokollen im Bereich der Computergestützten Gruppenarbeit. Ziele dieses Kapitels, sind die Hintergründe des Model Checking zu erläutern sowie die Grundlagen, zum Verständnis dieser Verifikationsmethoden zu legen. 2.1 Model Checking 2.1.1 Verteilte & Parallele Systeme Die ständig wachsende Bedeutung verteilter bzw. paralleler Systeme ist auf ver- schiedene Faktoren zurückzuführen. Zum einen sind die Kosten für die Prozessoren und Speicherkomponenten in den vergangenen Jahren kontinuierlich gefallen, zum anderen sind Netztechnologien mit hoher Bandbreite im Bereich der verteilten Sys- teme, inzwischen problemlos verfügbar. Aber auch die wachsende Vielfalt von ver- teilten Anwendungen und die Forderung nach immer kürzeren Antwortzeiten lassen diese Art von Systemen immer attraktiver werden. Im Gegensatz zu parallelen Systemen besitzen die verteilten Systeme Knoten (Knoten mindestens eine CPU und Speicher) ohne gemeinsamen (physischen) Speicher ein Verbindungsnetzwerk, haben keinen single point of failure" wie z.B. Multiprozessorsysteme und erfüllen die Verteilungstranzparenz. Wie man aus der Definiton eines Knotens sieht, können parallele Systeme Teile ver- teilter Systeme sein. Ein paralleles System besteht wiederum aus mehreren Teilsystemen, die parallel (zeitgleich oder zeitlich überlappend) arbeiten und miteinander kommunizieren, d.h. Nachrichten austauschen. Die Teilsysteme können Prozesse aus dem Soft- oder Hardwarebereich sein, aber auch menschliche Benutzer oder physikalische Prozes- Kapitel 2 ­ Grundlagen und Hintergründe 12 se. Sie werden auch als "Agenten" bezeichnet. Typische Beispiele für parallele Sys- teme sind Datenbanksysteme (z.B. Reservierungssystem) und Betriebssysteme. Die Korrektheit solcher Systeme wird durch folgende Punkte bestimmt: 1. Endlosbetrieb 2. Kommunikation 3. Nebenläufigkeit 4. Konkurrenz und Koordinierung Endlosbetrieb Parallele Systeme stehen in ständiger Interaktion mit Ihrer Umgebung und reagieren auf deren Ereignisse und Stimulationen. Man spricht deshalb auch von reaktiven Systemen [MaPn92][MaPn92]. Kommunikation Der Informationsaustausch der gleichzeitig oder zeitlich überlappend agierenden Teilsysteme, ist für das Verhalten eines parallelen oder verteilten Systems von gro- ßer Bedeutung. Dabei wird zwischen der Kommunikation durch Verwendung ge- meinsamer Variablen und dem Nachrichtenaustausch über Kanäle (Message Pas- sing) unterschieden. Nebenläufigkeit Unter Nebenläufigkeit versteht man das gleichzeitige Ablaufen von Prozessen, die auf dem gleichen oder unterschiedlichen Prozessoren ausgeführt werden. Üblicher- weise wird der Begriff der Nebenläufigkeit für Systeme verwendet, deren (Teil)Prozesse asynchron arbeiten. Konkurrenz und Koordination Die o.g. Kommunikationsprinzipien bzw. die Nebenläufigkeit in parallelen bzw. ver- teilten Systemen birgt eine Reihe von Problemen, die sich hauptsächlich aus den Abhängigkeiten zwischen den einzelnen Prozessen ergeben. Man unterscheidet da- bei zwischen a) einseitiger Abhängigkeit, die z.B. beim asynchronen Nachrichtenaustausch auf- tritt. Hier ist i.d.R. der Empfänger vom Sender abhängig sowie b) gegenseitiger Abhängigkeit, die z.B. beim synchronen Nachrichtenaustausch auf- tritt. Diese Abhängigkeiten erfordern Koordinations- bzw. Synchronisationsmaßnahmen. 2.1.1.1 Fehler Jede Abweichung eines Systems von den Anforderungen ist ein Mangel. Besteht dieser Mangel in einer klaren qualitativen Abweichung von den Anforderungen, so sprechen wir von einem Fehler ­ man unterscheidet allgemeine und anwendungs- spezifische Fehler. In vielen Anwendungen kann das Auftreten von Fehlern schwerwiegende Folgen ha- ben, die z.B. das gesamte System zusammenbrechen lassen. Gerade in parallelen und verteilten Systemen besteht die Gefahr, durch fehlende bzw. fehlerhafte Koordi- nations-/Synchronisationsmaßnahmen fehlerhaftes Verhalten zu verursachen. Für diese Diplomarbeit sind die folgenden Fehlerarten von Bedeutung: Kapitel 2 ­ Grundlagen und Hintergründe 13 a) Deadlocks Ein Deadlock tritt ein, wenn kein Prozess eine Operation mehr ausführen kann. Im folgenden Beispiel soll eine zufällige, positive Zahl quadriert und in einer Da- tenbank gespeichert werden. Wie man sehen kann, tritt aufgrund der Operation x--" (es werden nur negative Zahlen berechnet) im Prozess zwei ein Deadlock im System auf. Die ausgefüllten" Knoten können nicht erreicht werden. y = 2 x > 0 z = xy Prozess 1 flag = 0 flag = 1 x-- x = 0 flag == 1 writeToDB (z) Prozess 2 Abb.2-1: Beispiel für einen Deadlock b) Livelocks Ein Livelock tritt ein, wenn ein Prozess innerhalb einer bestimmten Sequenz von Operationen keine neue Operation ausführt. Dies tritt vor allem bei Schleifenkon- strukten auf, deren Abbruchbedingung fehlerhaft ist. Das folgende Programmfragment zeigt einen Livelock in einer FOR-Schleife (der Zähler i wird nicht reduziert Abbruchbedingung wird nicht erreicht). // berechnen von 2^5 int x = 2; int i = 0; for (i = 5; i>0;) { x = x*x; } printf("2^5 = %d", x); c) Assertion violations (Invarianten) Eine assertion violation tritt ein, wenn ein definiertes Argument den Wert false er- hält. Ein Beispiel ist das Prüfbit. Hat es den Wert false, liegt ein Fehler bei der Übertragung vor. d) Divergences Eine Divergenz liegt vor, falls innerhalb eines definierten Zeitraums keine weitere Operation ausgeführt wird. Solche Fehler treten sehr häufig in verteilten Syste- men auf. Ein typisches Beispiel ist der Timeout (die Antwort auf einen Request erfolgt nicht innerhalb eines bestimmten Zeitraumes). e) Verletzung von anwendungsspezifischen Korrektheitskriterien Die meisten Verifikationstools unterstützen die Definition von Korrektheitskriterien, d.h. es können mit Hilfe dieser Tools vom Benutzer definierte Anforderungen ü- berprüft werden. Eine Möglichkeit ist z.B. das Finden von nicht erreichbaren Zu- ständen (Methoden) mit Hilfe von assertion violations oder die Konsistenzprüfung, falls das System einen bestimmten Zustand erreicht. f) Sonstige Programmfehler Unter sonstigen Programmfehlern verstehe ich hier sämtliche Fehler, die durch die Punkte (a)-(e) nicht abgedeckt werden. Dazu zählen Syntaxfehler, wie z.B. fehlerhafte Operatoren und falsch definierte Array-Grenzen, aber auch Fehler, welche bei der Modellierung von Echtzeitsystemen, wie z.B. Timelocks, auftreten. Diese Art der Fehler wird jedoch nicht näher betrachtet. Kapitel 2 ­ Grundlagen und Hintergründe 14 2.1.1.2 Validierung (Simulation und Verifikation) Validierung steht für Prüfen auf Fehler, d.h. ob die an das System gestellten Anforde- rungen erfüllt sind. Man unterscheidet prinzipiell zwei verschiedene Strategien zur Validierung von Computersystemen (Hardware- und Computersysteme) Testen und Simulation (formale) Verifikation Beide Validationstechniken sind zueinander komplementär und haben jeweils Ihre Daseinsberechtigung. Testen und Simulation Test Testen [Bei90] ist die Ausführung eines Systems unter Bedingungen, für die das kor- rekte Ergebnis bzw. Verhalten bekannt ist und mit dem die Resultate verglichen wer- den können. Der Ablauf eines Tests beginnt mit der Testplanung und endet nach der Testdurchführung mit der Auswertung. Bis heute ist der Test die in industriellen Anwendungen am stärksten verbreitete Va- lidierungstechnik. Er ist jedoch sehr zeitaufwendig, kostenintensiv und erst dann an- wendbar, wenn eine Implementierung des Systems bereits vorliegt. Auch wenn der Test vor der Inbetriebnahme eines komplexen Systems unerlässlich ist, so lassen sich doch die Kosten drastisch reduzieren, wenn man zusätzliche Validierungstech- niken bereits in frühen Entwurfsphasen einsetzt. Simulation Der wesentliche Unterschied zwischen Simulation und Test ist die Verwendung eines semantischen Modells (i.a. der Systementwurf), anstelle eines realen Systems, um Fehler aufzudecken. Es gibt verschiedene Simulationstechniken [OnLi12], die je nach Art des zu entwi- ckelnden Systems eingesetzt werden sollten. Diese Art der Validation wird vorwie- gend in den frühen Entwurfsphasen eingesetzt, um einen ersten Eindruck vom prin- zipiellen Verhalten des Systems zu erhalten und zu prüfen, ob die grundlegenden Anforderungen erfüllt werden. Ein klarer Vorteil von Test bzw. Simulation ist, dass sie einen Einblick in das gesamte Systemverhalten geben und ebenso nicht explizit definierte Eigenschaften überprüft werden können. Ein gravierender Nachteil aller Test- und Simulationstechniken ist, dass sie niemals eine 100prozentige Fehlerfreiheit garantieren können. (formale) Verifikation Im Gegensatz zum Test bzw. der Simulation, kann durch die Verifikation ein mathe- matischer Korrektheitsbeweis erbracht werden, der die Fehlerfreiheit eines System- entwurfs garantiert. Dazu werden jedoch beweisfähige Formalismen benötigt. Die Verifikation basiert auf mathematisch präzisen Beschreibungen für das System bzw. den Systementwurf, durch ein semantisches Modell den Anforderungskatalog, durch eine Spezifikation, z.B. logische Formeln die "Erfülltrelation", die angibt, wann ein Modell eine Spezifikation erfüllt Kapitel 2 ­ Grundlagen und Hintergründe 15 Erfülltrelation Die Erfülltrelation gibt an, für welche Belegungen eine Formel wahr ist. Formal ist eine Menge bestehend aus Paaren ( , ), wobei eine Belegung und eine Formel ist. Man schreibt anstelle von ( , ) . Falls , dann nennt man eine erfüllende Belegung für . Beispiel: = (a1 a2) a3, mit (a1)=0, (a2)= (a3)=1 dann gilt: a1 a2 a 3 Aufgrund der formalisierten Darstellung des Systems und der Anforderungen, wird ein höherer Abstraktionsgrad erreicht, wodurch die Gefahr von Modellierungs- und Spezifikationsfehlern entsteht. Diese können jedoch durch den Einsatz von Simulati- ons- und Testmethoden abgefangen werden. Aufgrund der möglichen Fehler ergibt sich, dass die Verifikation höchstens so gut wie das Modell ist. Grundsätzlich ist es sehr schwierig für ein bereits vorhandenes Computersystem ein abstraktes Modell zu entwerfen, welches nur die für den Nachweis der wesentlichen Eigenschaften relevanten Details enthält. Bei einer schrittweisen Verfeinerung des zu konzipierenden Systems ist es meist sehr einfach von den jeweiligen Systementwür- fen auf ein geeignetes abstraktes Modell zu schließen, da die Systementwürfe oft- mals semantische Modelle sind, die für die Verifikation eingesetzt werden können. Ein deutlicher Vorteil der Verifikation ist, dass sie die Fehlerfreiheit eines Entwurfs garantiert. Die Verifikationsmethoden werden in der Literatur in zwei Kategorien ein- geteilt: a) Deduktive Methoden Der deduktive Ansatz verwendet ein sog. deduktives System (auch Beweissystem genannt) in dem Axiome und Regeln für die Erfülltrelation als "elementare Be- weisschritte" vorgegeben sind. Die Idee besteht darin, für den Nachweis, dass das semantische Modell die Spezifikation erfüllt, nur diese elementaren Beweis- schritte zuzulassen. Häufig wird ein homogener Ansatz benutzt, in dem das zu verifizierende System und die geforderten Eigenschaften im selben Formalismus dargestellt werden. Die Idee des homogenen logikbasierten Ansatzes besteht darin, das System durch eine logische Formel Sys, die Anforderungen durch eine Formel Spec dar- zustellen und die Gültigkeit der Formel Sys Spec nachzuweisen. Dabei steht " " für den Implikationsoperator a b = a b. Deduktive Verifikation lässt sich auch computerunterstützt mit einem sog. Theo- rembeweiser [NeSh93] realisieren. Der eigentliche Verifikationsvorgang wird maßgeblich vom Benutzer gesteuert. Die Aufgabe des Theorembeweisers ist es, Vorschläge für den jeweils nächsten möglichen Beweisschritt zu machen. Häufig kann der Benutzer, neben den vom Theorembeweiser vorgeschlagenen Beweis- schritten, selbst Beweisschritte entwerfen, deren Korrektheit vom Theorembewei- ser überprüft werden können. Der Nachteil des deduktiven Ansatzes ist der sehr hohe Zeitaufwand und die da- mit entstehenden Kosten, welche durch die ständigen Interaktionen mit dem Be- Kapitel 2 ­ Grundlagen und Hintergründe 16 nutzer verursacht werden. Zusätzlich erfordert die deduktive Verifikation einen fachkundigen Benutzer, der spezifische Kenntnisse bezüglich des Systems, der Spezifikationsformalismen und des Theorembeweisers haben muss, um die Kor- rektheit des Systems beweisen oder widerlegen zu können. Der Vorteil dieses Ansatzes ist, dass er für fast alle Modelltypen und Spezifikationsformalismen ein- setzbar ist. b) Model Checking (vollautomatisierbare Verifikation) Als Model Checking bezeichnet man ein algorithmisches Verifikationsverfahren, das als Eingabe das abstrakte Modell und die Spezifikation eines Systems hat und als Resultat das Ergebnis Spezifikation erfüllt bzw. Spezifikation nicht erfüllt ausgibt. Darüber hinaus können die meisten Model-Checker im Fehlerfall einen Hinweis auf eine Fehlerquelle geben. Von einigen Model-Checkern werden Ge- genbeispiele erzeugt, die mit Hilfe von geeigneten Simulatoren (meist in den Mo- dell-Checkern integriert) nachvollzogen werden können. Model Checking basiert also auf einem Entscheidungsverfahren für folgende Problemstellung (die Abkürzung sat steht dabei für satisfaction relation): Gegeben: semantisches Modell M und eine Spezifikation Spec Gefragt: M sat Spec ? Daraus ergeben sich gewisse Einschränkungen, die sicherstellen, dass die ge- nannte Problemstellung entscheidbar ist. Die einfachste Forderung ist die End- lichkeit des Zustandsraums des semantischen Modells M. Im Bereich von Softwaresystemen ist diese Forderung schwer zu erfüllen ­ durch den Entwurf eines endlichen semantischen Modells in frühen Entwurfsphasen je- doch erfüllbar. Vielen Kommunikationsprotokollen liegt zum Beispiel ein endliches semantisches Modell zugrunde. Der Vorteil des Model Checkings gegenüber dem deduktiven Ansatz ist die sehr benutzerfreundliche und wesentlich effizientere Vorgehensweise. 2.1.1.3 Modellierung und Spezifikation Verifikation setzt beweisfähige mathematische Formalismen für die Systementwürfe und Anforderungen sowie vollständig und präzise definierte Erfülltrelationen voraus. Unter dem Systementwurf versteht man ein semantisches Modell M eines bestimm- ten Typs. Die Anforderungen werden in der Spezifikation SPEC festgehalten und die Erfülltrelation ist eine binäre Relation sat Modelltyp Spezifikationstyp Semantische Modelle (Modelltypen) Zu üblichen semantischen Modelltypen für Systeme, die zur Formalisierung paralleler Systeme eingesetzt werden, zählen Transitionssysteme und Petrinetze [Bau90]. Die- se basieren im Wesentlichen auf einer Darstellung des Systems durch Zustände, Zustandswechsel sowie Anfangs- und Endzustände. Für die spätere Verifikation der semantischen Modelle ist der Grad der Abstraktion von sehr großer Bedeutung. Ist das Modell zu detailliert, wird die Verifikation erschwert bzw. ist unentscheidbar oder nicht effizient durchführbar. Ist die Abstraktionsebene des Modells jedoch zu hoch, können evtl. nicht alle nachzuweisenden Eigenschaften getestet werden. Optimaler Weise sollte das semantische Modell alle Details verwerfen, die für die in Frage ste- henden Eigenschaften unerheblich sind. Im Rahmen dieser Diplomarbeit werden lediglich die Transitionssysteme als seman- tisches Modell betrachtet. Sie sind Digraphen, in denen die Kanten für mögliche Akti- onen stehen und die Knoten für Kontrollpunkte. Kapitel 2 ­ Grundlagen und Hintergründe 17 Spezifikationsformalismen für Anforderungen Die zunächst informell beschriebenen Anforderungen müssen für die Verifikation in eine mathematisch präzise Spezifikation transformiert werden. Man unterscheidet zwischen deklarativen Spezifikationen (Anforderungsspezifikationen) und prozedura- len Systemspezifikationen. Die Anforderungsspezifikationen legen fest, was das Sys- tem leisten soll. Die Systemspezifikation gibt vor, wie sich das System verhalten soll. Für Anforderungsspezifikationen verwendet man meistens Logiken, wie z.B. die tem- poralen Logiken. Das gewünschte Systemverhalten wird also durch eine logische Formel beschrieben. Dadurch lassen sich Eigenschaften sehr leicht durch Konjunkti- onen miteinander verknüpfen. Den Anforderungsspezifikationen liegt ein heterogener Ansatz zu Grunde. Im Gegensatz dazu, basieren Systemspezifikationen auf einem homogenen Ansatz. Die Anforderungen werden durch ein semantisches Modell beschrieben. Die zugrun- de liegende Erfülltrelation sat ist eine sog. Implementierungsrelation die angibt, wann ein Modell eine korrekte Implementierung eines anderen (verfeinerten) Modells ist. Systemspezifikationen spielen eine entscheidende Rolle, für den Entwurf durch schrittweises Verfeinern. 2.1.2 Transitionssysteme Sowohl für den Entwurf als auch für die vollautomatische Verifikation von Computer- systemen haben sich die von Keller (1976) eingeführten Transitionssysteme als Standardformalismus etabliert. Den meisten anderen semantischen Modellen, wie z.B. Petri-Netzen, liegt eine Transitionssystemsemantik zugrunde. Entsprechendes gilt für die Hardwaresynthese und -analyse, in denen Varianten endlicher Automaten (Mealy- und Moore-Automaten) eine zentrale Rolle spielen, die ebenfalls durch Tran- sitionssysteme beschrieben werden können. 2.1.2.1 Grundlegendes Ein Transitionssystem ist ein gerichteter Graph mit Zusatzinformationen, d.h. die Knoten stehen für die Systemzustände und die Kanten für einen Zustandswechsel. Formale Definition Ein Transitionssystem ist ein Tupel T = (S, Act, , S0, AP, L) bestehend aus einer Menge S von Zuständen einer Menge Act von Aktionen einer Menge S0 von Anfangszuständen mit S0 S einer Menge AP von atomaren Aussagen (atomic propositions) einer Markierungsfunktion L: S 2AP einer Transitionsrelation mit s 's T heißt endlich, falls S, Act und AP endlich sind. Das schrittweise Verhalten eines Transitionssystems kann wie folgt beschrieben wer- den: Das Transitionssystem "startet" in einem Anfangszustand s0 S0. Ist s der ak- tuelle Zustand, dann wird eine von s ausgehende Transition s 's gewählt, die Aktion ausgeführt und zu Zustand s' übergegangen. Jedem Zustand wird durch die Markierungsfunktion eine Menge L(s) 2AP atomarer Aussagen zu- Kapitel 2 ­ Grundlagen und Hintergründe 18 geordnet. L(s) steht für genau diejenigen atomaren Aussagen a AP, die im Zustand s erfüllt sind, d.h. ist eine aussagenlogische Formel, so erfüllt s die Formel , wenn die durch L(s) induzierte Belegung die Formel wahr macht (s gdw L(s) Vorgänger und Nachfolger Sei T ein Transitionssystem mit T = (S, Act, , S0, AP, L) und s S, Act, dann ist s' ein unmittelbarer -Nachfolger, wenn gilt: Post(s, ) = 's S:[s 's ] , Post(s) = Post( ,s ) und s' Post(s, ). Damit ist Act Zustand s': s' Post(s) unmittelbarer Nachfolger von s. Sei T ein Transitionssystem mit T = (S, Act, , S0, AP, L) und s S, Act, dann ist s' ein unmittelbarer -Vorgänger, wenn gilt: Pre(s, ) = 's S : s ( Post 's, ) , Pre(s) = 's S : s ( Post 's ) und s' Pre(s, ). Da- mit ist Zustand s': s' Pre(s) unmittelbarer Vorgänger von s. Terminale Zustände Ein Zustand s heißt terminal, wenn es keine von s ausgehenden Transitionen gibt, also wenn Post(s) = . Liegt ein Transitionssystem T für ein paralleles, endloses System vor, dann hat T keine terminalen Zustände, es sei denn, es liegt ein Fehverhalten des Systems vor. Erreichbare Zustände Ein Zustand s' heißt erreichbar in T, falls s' von einem Anfangszustand s S _ _ 0 über eine Ausführungsfolge erreichbar ist, also falls gilt: s 0 1 s1 2 .... n sn 's Reach (T) bezeichnet die Menge aller erreichbaren Zustände. 2.1.2.2 Parallelität Transitionssysteme stellen Nebenläufigkeit durch Interleaving dar, d.h. die nichtde- terministische Wahl zwischen den Aktivitäten der parallel ausgeführten Prozesse. Dies entspricht der Sichtweise, dass nur ein Prozessor zur Verfügung steht, auf dem die Aktionen der Teilprozesse ausgeführt werden. Dabei werden keinerlei Annahmen über die Reihenfolge, in der die Teilprozesse Aktionen ausführen, gemacht. Liegen z.B. zwei nicht terminierende Prozesse vor, die unabhängig voneinander agieren, dann sind P1 P2 P1 P2 P1 P2 P1 P2 P1 P1 P1 P2 P1 P1 P2 P1 P1 P2 P1 P2 P1 P1 P2 P1 P1 P1 P2 mögliche Ausführungsreihenfolgen. Die Interleavingdarstellung geht von einem Scheduler aus, der nach einer unbekann- ten Strategie, die Schritte der nebenläufig ausgeführten Prozesse verzahnt. Dadurch wird eine Abstraktion von den Geschwindigkeiten der beteiligten Prozessoren mög- lich, d.h. es können von der Einprozessormaschine bis hin zu Multiprozessorsyste- men alle möglichen Konstellationen realisiert werden. Kapitel 2 ­ Grundlagen und Hintergründe 19 2.1.2.3 Sicherheits- und Lebendigkeitseigenschaften Sicherheitseigenschaften Sicherheitseigenschaften sollen garantieren, dass nichts Unerwünschtes" passiert, wobei das unerwünschte Ereignis, sofern es eintritt, in endlicher Zeit passiert. Ein typisches Beispiel für eine Sicherheitseigenschaft ist die mutale Ausschlussei- genschaft MUTEX [Tan90]. In diesem Fall besteht das schlechte Ergebnis darin, dass beide Teilprozesse gleichzeitig im kritischen Abschnitt sind. Ein anderer typi- scher Vertreter für eine Sicherheitseigenschaft ist die Deadlockfreiheit. Die o.g. genannten Beispiele gehören alle zu einer Form von Sicherheitseigenschaf- ten, die man Invarianzen nennt. Invarianzen sichern zu, dass die Eigenschaft a für alle erreichbaren Zustände gilt, d.h. a charakterisiert dann genau die Zustände, auf die nichts "Unerwünschtes" zutrifft. Formale Definition (Invarianz) Eine LT-Eigenschaft (Lebendigkeitseingenschaft) EINV über AP heißt Invarianz, falls es eine aussagenlogische Formel a über AP gibt, so dass E AP INV= (2 ) : j [ [ ]j a] und [j]=Aj für =A0, A1, ... gilt. So kann z.B. für MUTEX die Invarianzeigenschaft durch crit1 crit2 beschrieben werden. Invarianz­Checking Um Invarianzen durch Model Checking Algorithmen nachzuweisen, setzt man zu- nächst ein endliches Transitionssystem T = (S, Act, , S0, AP, L) voraus. D.h. die Komponenten S, Act und AP sind endlich. Weiterhin ist a eine aussagenlogische Formel über AP und EINV die zu a gehörende Invarianz. Nun liegt es auf der Hand, dass die Gültigkeit von EINV für T durch eine Erreichbarkeitsanalyse im Zustandsgra- phen GT, die die Zustandsmenge Reach(T) berechnet, geprüft werden kann. Gilt s a für alle Zustände s Reach(T), dann ist die Invarianz erfüllt. In der Literatur werden verschiedene Algorithmen zum Invarianz-Checking vorge- stellt, die jeweils ihre Vor- und Nachteile besitzen. So ist z.B. der Ansatz, für jeden Knoten s zu prüfen, ob die Invarianzbedingung a erfüllt ist, zwar anwendbar, im Feh- lerfall die Angabe eines Gegenbeispiels jedoch nicht ohne weiteres möglich. Lebendigkeitseigenschaften Lebendigkeitseigenschaften sichern zu, dass "etwas Erwünschtes" irgendwann in der Zukunft passieren wird. Im Gegensatz zu Sicherheitseigenschaften, bei denen das auszuschließende unerwünschte Ereignis eine Anforderung an die endlichen Pfad- fragmente ist, ist das erwünschte Ereignis einer Lebendigkeitseigenschaft eine Be- dingung, die an unendliche Pfade gestellt wird. In der Literatur werden viele Arten von Lebendigkeitseigenschaften vorgeschlagen, unter anderem eine Charakterisierungen von Manna & Pnueli (1990), die eine Hie- rarchie von Lebendigkeitseigenschaften angegeben haben: Eigenschaften die zusichern, dass irgendwann in Zukunft ein guter Zustand er- reicht wird Rekurrenzeigenschaften die zusichern, dass ein Ereignis unendlich oft eintreten wird Fortschrittseigenschaften wie z.B. "Jede Anfrage wird irgendwann beantwortet." Kapitel 2 ­ Grundlagen und Hintergründe 20 Reaktivitätseigenschaften wie z.B. "Jedem Prozess, der unendlich oft eine Res- source beantragt, wird unendlich oft eine Ressource zugeteilt." Fairness Fairness ist eine Lebendigkeitseigenschaft, die zusichert, dass der Nichtdeterminis- mus aufgelöst wird. Prozessfairness ist die vermutlich wichtigste Art von Fairness, da sie regelt, welcher Prozess den nächsten Schritt macht. Sie ist eine Forderung, die an die Auflösung des durch Interleaving entstandenen Nichtdeterminismus gestellt wird. Weiter können Fairnessannahmen eine Forderung sein, die an die Mechanis- men zur Auflösung von Konkurrenzsituationen gestellt werden. Als Faustregel für die Modellierung von asynchronen Systemen mit Transitions- systemen, wird in der Literatur die Gleichung Parallelität = Interleaving (Nichtdeter- minismus) + Fairness angegeben. Fairnessbedingungen können unterschiedlich stark formuliert werden: a) unbedingte Fairness - z.B. "Jeder Prozess wird unendlich oft aktiviert." b) starke Fairness - z.B. "Jeder Prozess, der unendlich oft aktivierbar ist, wird un- endlich oft aktiviert." c) schwache Fairness: z.B. "Jeder Prozess, der kontinuierlich ab einem gewissen Zeitpunkt aktivierbar ist, wird unendlich oft aktiviert." Der Begriff "aktivierbar" ist hier im Sinn von "bereit zur Ausführung einer Transition" zu verstehen. Dagegen steht "wird aktiviert" für die Ausführung einer beliebigen Transition. Dabei kann es sich um die Zuteilung einer Ressource, einer Kommunika- tionsaktion und anderer Aktionen, handeln. 2.1.2.4 Analyse von Transitionssystemen Für die Analyse eines Transitionssystems kann entweder ein aktionsbasierter oder ein zustandsbasierter Ansatz zu Grunde gelegt werden. Beim aktionsbasierten An- satz wird von den Zuständen abstrahiert wird. D.h. es werden nur die Aktionsbe- schriftungen der Transitionen berücksichtigt. Dagegen wird beim zustandsbasierten Ansatz von den Aktionen abstrahiert und sich alleine nach den sog. Spuren (Traces) gerichtet, die sich aus den Pfaden ergeben, in dem von den Zuständen auf die je- weils gültigen atomaren Aussagen projiziert wird. D.h. es werden nur die Markierun- gen in den Zustandsfolgen berücksichtigt. Prinzipiell ist eine Kombination der aktions- und zustandsbasierten Sichten denkbar. Daraus resultiert jedoch ein sehr komplexer Beschreibungsformalismus, der viele Redundanzen enthalten kann und die Analyse erschwert. Aus diesem Grund ist es üblich, von einem der beiden o.g. Aspekte zu abstrahieren. In dieser Diplomarbeit wird im Wesentlichen nur der zustandsbasierte Ansatz ver- folgt, da die Aktionsbeschriftungen der Transitionen nur" zur Modellierung von Kommunikation benötigt werden und wir uns im Anwendungsfall auf Konsistenzerhal- tungsprotokolle beschränken, bei denen die Kommunikation zwischen den einzelnen Systemen abstrahiert; also nicht näher betrachtet wird. Die Model Checking Algorithmen werden daher auf dem Zustandsgraphen eines Transitionssystems operieren, aber keinen Gebrauch von den Aktionsnamen ma- chen. Formale Definition des Zustandsgraphen Sei T ein Transitionssystem mit T = (S, Act, , S0, AP, L), dann ist der Zustands- Kapitel 2 ­ Grundlagen und Hintergründe 21 graph GT definiert durch G T = (S,R) mit R= ( , s ' s ) : Act[s ' s ] , d.h. der Zustandsgraph GT von T ist der zugrunde liegende Digraph, dessen Knoten die Zustände sind und dessen Kantenmenge durch R definiert ist. Pfade und Pfadfragmente Die Pfade eines Transitionssystems sind maximale Wege im Zustandsgraphen, d.h. es sind diejenigen Zustandsfolgen, die sich aus den Ausführungen ergeben, wenn die Aktionen weggelassen werden. Pfade sind Teilmengen der Pfadfragmente, die verschiedene Eigenschaften erfüllen. Formale Definition Sei T ein Transitionssystem mit T = (S, Act, , S0, AP, L), dann ist ein Pfadfragment eine endliche oder unendliche (nichtleere) Zustandsfolge mit =s0, s1, ..., sn oder =s0, s1, s2 ... , so dass si Post(si-1), i=1, ..., n bzw. i=1, 2, ... gilt. Ein endliches Pfadfragment heißt maximal, falls der letzte Zustand sn von termi- nal ist. Weiterhin sind alle unendlichen Pfadfragmente maximal. Ein Pfadfragment heißt initial, falls der erste Zustand s0 ein Anfangszustand von T ist. Jedes initiale, maximale Pfadfragment wird Pfad genannt. 2.1.3 Spezifikationssprachen Neben den Transitionssystemen haben sich zur Abbildung der formalen Spezifikation eines Systems die sog. Spezifikationssprachen etabliert. Sie dienen zur sprachlichen und/oder graphischen Darstellung von Programmen, Systemen und Verhaltenswei- sen. Im Gegensatz zu Programmiersprachen wird in einer Spezifikationssprache nicht das Wie (Beschreibung der genauen algorithmischen Abläufe) sondern das Was (Beschreibung der gewünschten Eigenschaften des Systems) eines Systems beschrieben, also eine lösungsunabhängige Sichtweise. Die formale Spezifikation eines Systems mit Hilfe von Spezifikationssprachen erfolgt in den frühen Phasen des Entwurfs. Die Vorteile liegen auf der Hand: was formal und präzise definiert ist, kann mit den Mitteln der Mathematik und mit automatischen Werkzeugen bearbeitet werden, d.h. Konsistenzen können geprüft und evtl. Fehlver- halten frühzeitig erkannt und behoben werden. Die Spezifikationssprachen lassen sich in die folgenden drei Gruppen gliedern: 1) Algebraische Sprachen [Klae83] basieren auf algebraischen Beschreibungen z.B. PROMELA, LOTOS 2) Endliche Automaten basieren auf (erweiterten) Automaten z.B. SDL, Estelle [Hogr89] 3) Logische Sprachen basieren auf Prädikatenlogik z.B. Z [Nic95] Kapitel 2 ­ Grundlagen und Hintergründe 22 Betrachtungsschema der Spezifikationssprachen Das folgende Betrachtungsschema wurde aus [Kai98] übernommen. Die verschiedenen Sprachen werden nach folgendem Schema betrachtet: 1) Hintergrund (z.B. Entstehungszeitpunkt, Verwandtschaft mit anderen Sprachen) 2) Einordnung in Klassen 3) Prinzipien, auf denen die Sprache basiert 4) Elemente (z.B. Prozesse, Kanäle) 5) Datentypen 6) Hierarchische Strukturierungsmöglichkeiten 7) Besonderheiten Zusätzlich werden die Spezifikationssprachen in die in [Kru90] verwendeten Klassen eingeordnet: 1. Modellierungskonzept (a) Instanzen-konzentriert Das Hauptaugenmerk liegt in diesen Sprachen auf der Spezifikation von In- stanzen. (b) Kopplungs-konzentriert Die Beschreibung der Verknüpfungen von Instanzen steht bei diesen Spra- chen im Vordergrund. (c) Zweigeteilt Sowohl Instanzen als auch ihre Kopplungen sind hier von großer Wichtigkeit. 2. Spezifikationsform (a) konstruktiv In diesem Sprachtyp gibt es genau ein Modell, das der Spezifikation ent- spricht. Die Elemente und Zusammensetzung des Systems definieren das Modell eindeutig. i. direkt Unmittelbare Verwendung eines erweiterten endlichen Automaten, um die Funktionsweise des Systems zu spezifizieren. ii. algebraisch Das Verhalten einer Instanz bezüglich ihrer Umgebung wird algebraisch als Lösung eines Gleichungssystems festgelegt. (b) deskriptiv Für eine Spezifikation gibt es mehrere Modelle, die den Anforderungen ent- sprechen. Es werden Aussagen über das System gemacht, die von mehreren Modellen erfüllt werden können. Es werden logische Kalküle eingesetzt. i. logische Techniken Flexible Wahl der Abstraktionsebene, schrittweise Konkretisierung wäh- rend des Entwurfs. ii. Assertionstechniken Konzentration auf Korrektheitsbeweise 3. Darstellungsform (a) textuell-tabellarisch, z.B. in Form einer Zustandsübergangstabelle. (b) textuell-programmiersprachlich. Kapitel 2 ­ Grundlagen und Hintergründe 23 (c) graphisch-zur Förderung der Lesbarkeit (z.B. Zustandsübergangsdia- gramme). Ausgehend von diesem Schema wird im folgenden Abschnitt die Spezifikationsspra- che PROMELA (Spezifikationssprache von Spin ­ getestetes Verifikationstool) be- trachtet. Auch hier wurden die Ausführungen von [Kai98] übernommen. 2.1.3.1 PROMELA Eine Einführung in Promela befindet sich in [Hol91]. Eine Darstellung der Syntax fin- det sich im Anhang A.2 und eine Beispielspezifikation im Anhang B.2 Hintergrund Promela (Protocol Meta Language) wurde 1985 durch G. Holzmann definiert. Sie ist syntaktisch an C orientiert und semantisch von den Guarded Commands von Dijkstra beeinflusst. Klassifikation Das Modellierungskonzept von Promela ist zweigeteilt. Die Spezifikationsform ist konstruktiv, mit algebraischer Ausprägung. Sie besitzt jedoch gewisse Elemente as- sertionsorientierter Sprachen, was auf den Einfluss deskriptiver Sprachen schließen lässt. Prinzipien Promela hat das Ziel, Protokolle zu verifizieren. Dies wird durch Validierungsmodelle erreicht, in denen Details wie z.B. Nachrichtenaufbau und Routinen für die Speicher- verwaltung vermieden werden. Der Schritt von der Spezifikation zur Implementierung wird erst nach einer ausführlichen Prüfung gemacht. Elemente und ihr Verhalten Syntaktisch ist Promela von C beeinflusst. Wie in C kann man mit #define Konstan- ten und Makros definieren und mit #include externe Dateien einfügen. Unterschiede zu C finden sich dagegen in der Verwendung eines init-Prozesses, der die Initialisie- rung zu Beginn eines Ablaufs spezifiziert. Bei der Betrachtung der Anweisungen fällt auf, dass Auswahl und Wiederholung nach dem Prinzip der "Guarded Commands" von Dijkstra arbeiten und damit nichtdeterministisch sind. Zusätzlich stehen einfache Sende- und Empfangsanweisungen zur Verfügung. Mit Hilfe der Anweisung atomic, kann eine Anweisungsfolge als eine nicht unterbrechbare Einheit ausgeführt werden. Datentypen Es wird ein eingeschränkter Satz von Datentypen durch die Sprache vorgegeben. Das sind bit, byte, int und chan (repräsentiert die Kommunikationskanäle). Des Wei- teren besteht die Möglichkeit Arrays und eigene Datentypen (mit typedef) zu definie- ren. Hierarchie Promela erlaubt nur einfache Strukturen, da Prozesse nicht ineinander geschachtelt werden können. Besonderheiten Mit einem never-Prozess können Korrektheitsforderungen angegeben werden. Mit assert werden Anforderungen ausgedrückt, die ­ falls sie in einem eigenständigen Prozess enthalten sind ­ eine Invariante darstellen. Kapitel 2 ­ Grundlagen und Hintergründe 24 Mit Hilfe von Marken können Zustände als end-Marke (korrekte Endzustände), pro- gress-Marke (unerlässliche Zustände für den Fortschritt eines Protokolls) oder ac- cept-Marke (ungeeignete Zustände für wiederholte Ausführung) definiert werden. 2.1.4 Temporale Logik Für parallele Systeme spielen temporale Eigenschaften wie z.B. das Erreichen oder das Eintreten eines gewissen Zustandes eine wesentliche Rolle. Temporale Logiken ermöglichen eine intuitive und mathematisch präzise Schreibweise für temporale Ei- genschaften. Der Einsatz solcher Logiken für die Verifikation von komplexen Compu- tersystemen wurde bereits 1977 von Amir Pnueli vorgeschlagen. Temporale Logiken sind Erweiterungen bereits bekannter Logiken (z.B. Aussagen- oder Prädikatenlogik) um Modalitäten, die es erlauben über das unendliche Verhalten eines Systems zu sprechen. Zu den Basismodalitäten, zählen die Operatoren "eventually" (irgendwann in Zukunft) "always" (jetzt und zu allen zukünftigen Zeitpunkten) Die in den nächsten beiden Abschnitten vorgestellten temporalen Logiken CTL und LTL gehören zu Gruppe der aussagenlogischen temporalen Logiken. Der Begriff temporal" kann leicht missverstanden werden, denn bei der Spezifikation von asynchronen Systemen lassen die temporalen Modalitäten keinerlei Interpretati- on über das Echtzeitverhalten zu. D.h. die Logiken (Formeln) können keine konkre- ten Zeitangaben wie z.B. "in 2 Sekunden" oder "mindestens 5 Minuten" machen. Eine Echtzeitinterpretation von LTL- oder CTL-Formeln ist nur für synchrone Systeme möglich. 2.1.4.1 Computation Tree Logic (CTL) Die nun folgende formale Definition von CTL basiert auf [OnLi10] und [Hau97]. Mit CTL Formeln können Aussagen über Zustände von System getroffen werden. Neben Operatoren der klassischen Logik verfügt CTL über Operatoren der linearen temporalen Logik und zusätzliche sog. path quantifiers A, E (Beschreibung siehe weiter unten in diesem Kapitel). Sei M=(S, , ) ein CTL-Modell, bestehend aus einer Menge von Zuständen S zu- sammen mit einer binären Relation , so dass zu jedem s S ein s S mit s s' gehört und einer Menge von Zustandsmarkierungen . Für jeden beliebigen Zustand s S ist definiert, ob eine CTL-Formel in diesem Zustand s gültig ist. Dies wird durch M, s formalisiert. Temporale Operatoren A Nachfolgende Formel ist für alle möglichen Pfade erfüllt E Es existiert mindestens ein möglicher Pfad, für den die nachfolgende Formel erfüllt ist. Die Formel, die der Pfad zu erfüllen hat, kann folgende Operatoren der linearen tem- poralen Logik enthalten. G Die Formel ist vom aktuellen Zustand an immer erfüllt. (globally) F Es gibt vom aktuellen Zustand an mindestens einen Zustand, bei dem die Formel erfüllt ist (finally). Kapitel 2 ­ Grundlagen und Hintergründe 25 X Die Formel ist in dem auf den aktuellen Zustand folgenden Zustand erfüllt (next). U Die Formel ist vom aktuellen Zustand an solange erfüllt, bis ein existieren- der Zustand erreicht wird, in dem die Formel erfüllt ist (until). V Wenn es einen Zustand gibt, bei dem die Formel g erfüllt ist, so ist die For- mel vom aktuellen Zustand an solange erfüllt, bis der Zustand bei dem erfüllt ist, erreicht wird. Andernfalls ist die Formel bei allen auf den aktuel- len Zustand folgenden Zuständen erfüllt (unless, waits-for). Induktive Definition M, s0 p gdw. p (s0) M, s0 gdw. M, s0 M, s0 gdw. M, s0 und M, s0 M, s0 EG gdw. ex. Pfad s0, s1, s2, ... mit M, sk für alle k 0 M, s0 EF gdw. ex. Pfad s0, s1, s2, ... mit M, sk für ein k 0 M, s0 EX gdw. ex. Pfad s0, s1, s2, ... mit M, s1 M, s0 EU gdw. ex. Pfad s0, s1, s2, ... und k 0 mit mit M, sk und M, sj für alle 0 j < k M, s0 EV gdw. M, s0 EU oder M, s0 EG Die induktive Definition der A-Formeln ist analog zu den eben aufgeführten. Sie gel- ten jedoch für alle Pfade. Gültigkeit M gdw. M, s für alle s I (I=Menge der Anfangszustände) ­ gültig in M gdw. M, s für alle M, s ­ allgemeingültig CTL schematisch EG p AG p p p p s0 p s0 p p p p p p EF p AF p p s0 p s0 p p EX p AX p p p s0 s0 p Kapitel 2 ­ Grundlagen und Hintergründe 26 p EU q p AU q p p q s0 q s0 q p p q p EV q p AV q p p q s0 s0 q p q p p p p Abb.2-2: schematische Darstellung von CTL 2.1.4.2 Linear Temporal Logic (LTL) Die nun folgende formale Definition von LTL basiert auf [OnLi10]. Im Gegensatz zu CTL betrachtet man LTL-Formeln nicht in Bezug auf einen Zu- standsbaum, sondern lediglich in Bezug auf die Pfade des Systems. Daher entfallen die Pfadquantoren A und E aus CTL, während man aber boolsche Verknüpfungen und Temporaloperatoren jetzt beliebig schachteln kann. Weiterhin gilt, wenn der Pfad =s1 s2 ... ist so ist ²=s2 s3 ... . Temporale Formeln ( G ) gilt ab jetzt immer (globally) ( F ) gilt irgendwann in der Zukunft (finally) ( X ) gilt im nächsten Zustand (next) until ( U ) so lange, bis gilt (until) unless ( V ) schwacher until-Operator (unless, waits-for) Gültigkeit M gdw. für alle Abläufe von M ­ gültig in M Formeln interpretiert über unendliche Zustandsfolgen =s0, s1, s2, ... |i bezeichnet eine Teilfolge si, si+1, ... von p gdw. s0 p gdw. gdw. und gdw. |i für alle i 0 gdw. |i für ein i 0 gdw. |1 until gdw. ex. i 0 mit |i und für alle 0 j < i gilt |j unless gdw. until oder Kapitel 2 ­ Grundlagen und Hintergründe 27 2.2 Computergestützte Gruppenarbeit (CSCW) Der Einsatz von Arbeitsplatzrechnern zusammen mit deren Vernetzung führt seit ei- niger Zeit zu Bestrebungen, diese Ressourcen nicht nur zur verteilten Datenverar- beitung zu verwenden, sondern auch kollaboratives Arbeiten zu ermöglichen. In die- sem Zusammenhang tauchen Begriffe wie CSCW (Computer Supported Cooperative Work) und Groupware auf. Der Begriff CSCW steht dabei für theoretische Grundla- gen bzw. die Modellierung von Gruppenarbeit sowie Formen und Bewertungen der Computerunterstützung und ist ein interdisziplinäres Forschungsgebiet. Während CSCW also das universelle Arbeitsgebiet und die dazugehörigen Forschungsfelder bezeichnet, ist unter Groupware die entsprechende Systemlösung zu verstehen. Dieses Kapitel gibt einen kurzen Einblick in die Welt der CSCW-Systeme. Nach einer kurzen Definition und Charakterisierung werden die CSCW-Systeme klassifiziert und wichtige Konzepte und Systemklassen beschrieben. Detaillierte In- formationen sind in [Sch00] zu finden. 2.2.1 Begriffsklärung Der Begriff CSCW ist in den frühen 80er Jahren entstanden und steht im Deutschen für Computergestützte Gruppenarbeit oder Rechnergestützte Gruppenarbeit. In [Sch00] werden für CSCW die folgenden drei Begriffsauslegungen unterschieden. (1) Rechnergestützte Gruppenarbeit Hier steht die Gruppe im Zentrum der Betrachtungen. Die Untersuchungen zielen auf die Erforschung und Unterstützung von Gruppenprozessen ab. Einerseits wird die kooperative Arbeit nach sozialpsychologischen Gesichtspunkten interpretiert, andererseits aber auch als planmäßiges Zusammenwirken mehrerer Personen mit der gleichen Zielsetzung (ohne sozialpsychologische Annahmen). (2) Rechnergestützte kooperative Arbeit Hier steht der Kooperationsbegriff im Vordergrund. Kooperation wird hier als Gruppenarbeitsform, aber auch als planmäßige Zusammenarbeit mehrerer Per- sonen mit gleicher Zielsetzung betrachtet. (3) Rechnerunterstützung für organisierte Arbeit Diese Interpretation des Begriffs CSCW konzentriert sich nicht wie die beiden ers- ten auf die Rechnerunterstützung mehrerer Personen, sondern auf die zur Aufga- benbewältigung erforderlichen kooperativen und individuellen Arbeitselemente. Wichtige Aspekte Unterstützung des Gruppenbewusstseins ("group awareness") Darunter sind das Wissen der Gruppenteilnehmer hinsichtlich der Gruppenzu- sammensetzung und deren Aktivitäten zu verstehen. Gestaltung der gemeinsamen Arbeitsumgebung und des gemeinsamen Kontex- tes Wichtige Elemente sind hier die gemeinsame Sicht der Gruppenteilnehmer auf die von der Gruppe bearbeiteten Objekte, Mehrbenutzerschnittstellen, die Reali- sierung eines gemeinsamen Informationsraums, in dem sich die Gruppenmitglie- der bewegen sowie die Heterogenität auf verschiedenen Ebenen (z.B. Sicht, Dar- stellung von Objekten, Software, Hardware). Koordination von Aktivitäten Darunter ist die Spezifikation der zeitlichen und kausalen Abhängigkeiten der Ak- tivitäten der Gruppenteilnehmer zu verstehen. Kapitel 2 ­ Grundlagen und Hintergründe 28 Konsistenz der Information / Nebenläufigkeitskontrolle Durch die gemeinsame Benutzung und das Austauschen von Information ist eine geeignete Nebenläufigkeitskontrolle (siehe Kapitel 5) zu berücksichtigen ­ Fokus der Diplomarbeit. Kommunikationsinfrastruktur Die Mitglieder von CSCW-Systemen kommunizieren über LAN und WAN. Dabei ist in der heutigen Zeit die Unterstützung von sog. kontinuierlichen Medien, wie z.B. Video und Audio notwendig. Interdisziplinarität CSCW ist eine gebietsübergreifende Anwendung. Aus diesem Grund ist es notwendig, dass eine gemeinsame Sprache, Begriffswelt sowie ein gemeinsames Verständnis erreicht werden. CSCW besitzt neben sozialen und technischen auch eine organisatorische Kom- ponente 2.2.2 Klassifizierung Die zwei bekanntesten Klassifizierungen von CSCW-Systemen sind die Raum-Zeit- Matrix und das 3-K Modell. Raum-Zeit-Matrix Die Raum-Zeit-Matrix, welche auf Johansen zurückgeht, unterscheidet die Verteilung der Gruppenmitglieder nach Raum und Zeit. In der Literatur ist eine Darstellung der CSCW Klassifikation in einer Raum/Zeit-Matrix, basierend auf einer differenzierteren Betrachtungsweise von Grudin zu finden. 3-K Modell Dieses Modell unterscheidet nach dem Grad der Interaktionen zwischen den Grup- penmitgliedern. Je nach dem Grad der Intensität der Zusammenarbeit innerhalb ei- ner Gruppe kann zwischen Kommunikation, Koordination und Kooperation unter- schieden werden. Die folgende Abbildung zeigt den Zusammenhang zwischen den drei verschiedenen Unterstützungsfunktion Kommunikations-, Koordinations- und Kooperationsunterstützung. Abb.2-3: Unterstützungsfunktionen [Sch00] Kapitel 2 ­ Grundlagen und Hintergründe 29 2.2.3 Wichtige Konzepte Gruppenprozess(e) Ein Gruppenprozess spezifiziert die Informationen, die Aktivitäten und die Eigen- schaften der elektronisch unterstützten Gruppe und den Rahmen, in dem die Grup- penarbeit stattfindet. Er besitzt einen Anfangs- und Endzustand, wobei der Endzu- stand das Ergebnis der Gruppenarbeit ­ das sowohl Erfolg, als auch Misserfolg sein kann ­ repräsentiert. Architektur von CSCW-Systemen Die Unterstützung synchroner und asynchroner Kooperation in Gruppen (d.h. das gemeinsame Bearbeiten von Objekten, die auch verteilt sein können), erfordert An- wendungen, die geeignete Benutzerschnittstellen und Formen der Zusammenarbeit bereitstellen. Die Grundlagen für solche Anwendungen sind zentrale bzw. replizierte Architekturen. WYSIWIS WYSIWIS steht für what you see is what i see" und entspricht einer konsistenten Darstellung der gemeinsamen Information für alle Teilnehmer. Dieses Konzept er- möglicht u.a. die Verfolgung des Arbeitsfortschrittes von anderen Teilnehmern, be- sitzt die Möglichkeit die von anderen Benutzern bearbeiteten Informationen darzu- stellen und wird vor allem bei synchroner Kooperation eingesetzt. Nebenläufigkeitskontrolle Die gemeinsame Bearbeitung sowie der Austauschen von Informationen ist zentraler Teil von Gruppenprozessen. Dabei ist die Kontrolle der Nebenläufigkeit die sog. con- currency control von größter Wichtigkeit, d.h. die Informationen müssen konsistent gehalten werden (siehe Kapitel 5). Operationstransformation Operationstransformation ist ein Mechanismus zur pessimistischen Nebenläufigkeits- kontrolle. Jeder Teilnehmer am Gruppenprozess darf seine Manipulationen am Do- kument sofort durchführen. Dabei wird gegebenenfalls eine Operationstransformation notwendig. Dieses Verfahren wird bei Anwendungen mit replizierten Informationen angewandt. Ein typischer Vertreter einer solchen CSCW-Anwendung ist Grove (siehe Abschnitt 5.3). Group Awareness Unter group awareness versteht man das Wissen darüber, was in einer Gruppe ge- macht wird bzw. was in der Vergangenheit in der Gruppe gemacht wurde. Ein typi- sches Beispiel für ein System mit group awareness ist Nessie [OnLi13]. Kapitel 3 - Bewertungskriterien der Verifikationstools 30 Kapitel 3 BBEEW WE ER RTTU UN NG GS SK KR RIITTE ER RIIE EN N D DE ER R 3 V VEERRIIFFIIKKAATTIIO ON NS STTO OO OLLS S In diesem Kapitel werden die Kriterien beschrieben, anhand derer die Verifikations- tools zu bewerten sind. Dabei sind neben der bloßen" Verwendungsmöglichkeit, auch Kriterien im Hinblick auf den Einsatz in der Lehre zu beachten. 3.1 Grundlegendes Die in diesem Kapitel aufgestellten Bewertungskriterien gliedern sich in drei ver- schiedene Kategorien: (1) Bewertungskriterien für das Verifikationstool (2) Bewertungskriterien für die vom Verifikationstool unterstützten bzw. verwende- ten Spezifikationssprachen (3) Bewertungskriterien im Hinblick auf den Einsatz in der Lehre Die Reihenfolge der Kriterien entspricht gleichzeitig deren Bedeutung während der Bewertung (siehe dazu Gewichtung der Bewertungskriterien ­ weiter unten in diesem Kapitel). Einige der Kriterien, wie z.B. die Erlernbarkeit können nur subjektiv beurteilt werden, da im Rahmen dieser Diplomarbeit nicht genügend Zeit für umfangreiche Studien zur Verfügung steht. Aus diesem Grund erfolgt die Bewertung dieser Punkte auf der Basis meiner persönlichen Erfahrungen im Umgang mit neuen Applikationen und Entwicklungsumgebungen. Subjektiv bewertete Kriterien sind entsprechend ge- kennzeichnet. Zunächst werden die einzelnen Kriterien aufgelistet und im Abschnitt 3.3 erklärt. 3.2 Bewertungskriterien 3.2.1 Verifikationstools BT1. Simulator BT1a. Simulationsmodi I step-by-step II random III user-defined IV Wechselmöglichkeit des Simulationsmodus (I, II, III) ­ zu einem beliebigen Zeitpunkt BT1b. Suspend- und Go-On-Modus BT1c. Syntax-Checking BT1d. Protokollierung BT1e. Undo-Funktionalität (Anzahl der Schritte, bis zu definiertem Punkt) Kapitel 3 - Bewertungskriterien der Verifikationstools 31 BT2. Verifikation BT2a. Grad der Überdeckung BT2b. Generierung von test cases BT2c. Simulationsausführung mit den generierten test cases als Eingabe BT2d. Verifikationsgeschwindigkeit BT2e. Erzeugung und Ausführung von Gegenbeispielen im Fehlerfall BT2f. Vorhandene Verfahren zur Verbesserung des Geschwindigkeitsgrades BT3. Simulations- und Verifikationstechniken (besitzt es eigene oder werden nur" Schnittstellen zu bereits vorhandenen Simulatoren/Tools angeboten) BT3a. Erstellung und Eingabe der Spezifikation & Korrektheitskriterien I Intelligente Editoren (z.B. Code Completion) II Syntax-Checking III Wizards IV Visuelle Erstellung und Bearbeitung BT3b. Visualisierung I individuelle Visualisierungsanpassung (Customization) II visuelle Konfiguration der V-Komponenten BT4. integrierte Bibliothek(en) BT4a. vorgefertigte Protokollspezifikationen bzw. Spezifikationsmodule (z.B. Spezifikationen für fehlerhaftes Protokoll-Verhalten oder Intruder- Verhalten) BT4b. Erweiterbarkeit BT4c. Suchoptionen und -kriterien BT4d. Austauschbarkeit BT5. Lizenz und Kosten BT6. Plattformunabhängigkeit BT7. Erlernbarkeit, Verständlichkeit BT8. Dokumentation BT9. Erweiterbarkeit BT10. Schnittstelle(n) (APIs) zu anderen Tools BT11. Stabilität/Technische Ausgereiftheit BT12. Verfügbarkeit BT13. Verbreitung und Bekanntheitsgrad Kapitel 3 - Bewertungskriterien der Verifikationstools 32 3.2.2 Spezifikationssprachen BS1. Definition von Korrektheitskriterien BS2. Modularität BS3. Eignung für die Modellierung von Interaktionen zwischen Prozessen in Verteil- ten Systemen (VS) BS4. Vollständigkeit/Mächtigkeit BS5. Erlernbarkeit, Verständlichkeit BS6. Dokumentation BS7. Implementierbarkeit BS8. Verbreitung und Bekanntheitsgrad (u.a. vorhandene Tools) BS9. Abbildbarkeit in andere Sprachen (z.B. Java) BS10. Überprüfbarkeit (u.a. Lesbarkeit für Fachleute) BS11. Lockerheit 3.2.3 Lehre BL1. Erlernbarkeit, Verständlichkeit BL2. Dokumentation/Hilfen BL3. Lernkurve (u.a. Lernziele erreichbar ?) BL4. Benutzerführung BL5. Standardisierung BL6. Verbreitung und Bekanntheitsgrad BL7. Verfügbarkeit BL8. Schnittstellen (APIs) zu anderen Tools 3.3 Erläuterung der Bewertungskriterien In diesem Abschnitt erfolgt eine Beschreibung der wichtigsten Bewertungskriterien. Wie man feststellen konnte, befinden sich einige dieser Kriterien in verschiedenen Kategorien. Sie haben jedoch nicht immer die gleiche Bedeutung. Die oft im Detail liegenden Unterschiede, sollen hier herausgestellt werden. 3.3.1 Verifikationstools (BT1) Simulator Der lateinische Wortstamm simulare", der vortäuschen" bedeutet, bezeichnet all- gemein worum es geht. In unserem Fall ist der Simulator eine Funktion des Verifika- tionstools, um spezifizierte Prozessabläufe und Systemfunktionen nachzubilden (sie- he auch Kapitel 2). Als Interaktion bezeichnet man die Kommunikation zwischen Mensch und Maschine. In diesem speziellen Fall ­ die Interaktionen zwischen Simulator und Anwender (z.B. Kapitel 3 - Bewertungskriterien der Verifikationstools 33 im step-by-step Modus). Da dies besonders für das Verständnis des Protokolls und das weitere Vorgehen während der Simulation von Bedeutung ist, fließt die Interakti- on indirekt in jedes Bewertungskriterium des Simulators mit ein. Dieses Kriterium bewertet, welche Funktionen vom Simulator des Tools unterstützt werden. (BT2) Verifikation Wie der Simulator, ist der Verifikator ein wichtiger Baustein der zu evaluierenden Tools. Er dient zum Beweis der Korrektheit eines spezifizierten Prozessablaufs. Dieses Kriterium bewertet, welche Möglichkeiten der Verifikator bietet, um spezifizier- te Prozessabläufe auf ihre Korrektheit zu untersuchen. Dazu gehören neben dem Überdeckungsgrad, die Verifikationsgeschwindigkeit im Vergleich zu anderen Tools und die Erzeugung von Gegenbeispielen im Fehlerfall. (BT3) Simulations- und Verifikationstechniken Unter diesem Bewertungskriterium werden alle die Funktionen und Methoden ver- standen, die die Bedienung von Simulator, Verifikator und Spezifizierungsmodul" er- möglichen, vereinfachen und unterstützen. Tools zur Erstellung und Eingabe der Spezifikation und Korrektheitskriterien Um den Anwender bei der Eingabe von Protokollspezifikation und Korrektheitskrite- rien zu unterstützen, sollten Verifikationstools neben intelligenten Editoren (z.B. Code Completion) und Syntax-Checking (während der Eingabe der Prozessspezifikation) auch Wizards (Hilfsprogramme, die den Anwender bei der Erstellung, Bearbeitung und Konfiguration von Standardvorgängen unterstützen) beinhalten. Visualisierung Da jeder Anwender verschiedene Vorlieben, für das Aussehen z.B. von Editoren (Schriftgröße, Schriftfarbe, ...) oder die Ergebnisdarstellung (z.B. Zeit-Sequenz- Diagramme) besitzt, sollten diese Komponenten konfigurierbar sein. Dieses Kriterium bewertet, welche Funktionen/Techniken vom Verifikationstool unter- stützt werden und wie hilfreich diese sind (diese Bewertung erfolgt zum Teil subjek- tiv). (BT4) Integrierte Bibliotheken Viele moderne Anwendungsprogramme besitzen sog. Bibliotheken, eine Sammlung von vorgefertigten, bereits existierenden Teillösungen. Bibliotheken ermöglichen eine einfachere und schnellere Spezifikation von Prozessabläufen, falls vorhandene Teil- lösungen verwendet werden können. Bei Verifikationstools könnten Bibliotheken z.B. Gerüste für Kommunikationsprotokolle enthalten. Weitere wichtige Gesichtspunkte sind Suchfunktionen und die Erweiterbarkeit (evtl. Verwendung von Bibliotheken anderer Tools) von Bibliotheken. Dieses Kriterium bewertet, ob Bibliotheken verfügbar sind und welche Möglichkeiten diese bieten. Kapitel 3 - Bewertungskriterien der Verifikationstools 34 (BT5) Lizenz und Kosten Lateinisch Befugnis, Erlaubnis", beschreibt Lizenz das Recht des Software- gebrauchs, d.h. wie darf ein Lizenznehmer die Software verwenden (z.B. darf er sie verändern, kopieren, weiter verbreiten, verkaufen, kommerziell einsetzen). Dabei gilt: je mehr erlaubt ist, desto höher ist die Bewertung. Unter Kosten verstehe ich hier die Beschaffungskosten des Tools und evtl. benötigter zusätzlicher Software. Dabei gilt: je niedriger die Kosten, desto höher die Bewertung. Eine besondere Stellung nehmen sog. Floating Licenses bzw. Server/-Client Licen- ses ein, da diese vor allem an Universitäten, also beim Einsatz in der Lehre, von Be- deutung sind. Dieses Kriterium bewertet, wie gut" die Lizenz und wie hoch die Beschaffungskosten eines Tools im Vergleich zu anderen Verifikationstools sind. (BT6) Plattformunabhängigkeit Plattform bezeichnet in der EDV das Betriebssystem (z.B. Linux, MacOS, MS Win- dows 9x/NT/2000/XP, UNIX, MS DOS, ...) eines Computers. Einige der Verifikations- tools sind z.B. in Java geschrieben. Diese Sprache garantiert eine relativ hohe Platt- formunabhängigkeit, d.h. das Tool funktioniert z.B. unter Linux, MS Windows und UNIX. Dabei ist jedoch zu beachten, dass evtl. durch ein Interface unterstützte, ande- re Tools nur auf einer bestimmten Plattform laufen. Das schränkt die Plattformunab- hängigkeit wieder ein (Dieser Gesichtspunkt wird bei diesem Bewertungskriterium jedoch nur gering gewichtet). Dieses Kriterium bewertet, wie hoch die Abhängigkeit eines Tools von einer bestimm- ten Plattform ist. (BT7) Erlernbarkeit, Verständlichkeit Dieses Kriterium bewertet, wie schnell eine Einarbeitung und wie gut die Verständ- lichkeit des Verifikationstools ist. Z.B., ob eine intuitive Bedienung des Tools möglich ist (diese Bewertung erfolgt subjektiv). (BT8) Dokumentation Gerade für Neueinsteiger ist eine gute Dokumentation aller Funktionen sehr wichtig. Hierzu gehören die ausführliche und vor allem vollständige Beschreibung der gesam- ten GUI und Optionen sowie einfache und aufeinander aufbauende Bedienungsbei- spiele. Dieses Kriterium bewertet, wie gut die Dokumentation des Verifikationstools ist (diese Bewertung erfolgt subjektiv). (BT9) Erweiterbarkeit Gerade Verifikationstools sind häufig OpenSource, d.h. der Sourcecode des Pro- gramms steht zur Verfügung und kann verändert werden. Solche Tools können dann durch eigene Funktionen erweitert werden. Dieses Kriterium bewertet also, ob und in welchem Umfang (z.B. nur die GUI) das Tool erweitert werden kann. Dabei wird zusätzlich auf die Dokumentation des Sour- cecodes bzw. auf Dokumentationen/Hilfen zur Erweiterung des Tools wert gelegt. Kapitel 3 - Bewertungskriterien der Verifikationstools 35 (BT10) Schnittstelle(n) (API) zu anderen Tools Eine Schnittstelle (engl. Interface) ist der Berührungspunkt" verschiedener Systeme ­ in unserem Fall zweier oder mehrerer Verifikationstools ­ mit dem Zweck, unter- schiedliche Merkmale auszugleichen. Dieses Kriterium bewertet, welche Möglichkeiten die Schnittstelle bietet, um andere Tools einzubinden. Dabei werden neben dem Grad der Integrierbarkeit auch die Verbreitung und der Bekanntheitsgrad der integrierbaren Tools mit einbezogen (die- se Bewertung erfolgt zum Teil subjektiv). (BT11) Stabilität/Technische Ausgereiftheit Viele Anwendungen werden veröffentlicht, ohne dass ausreichende Funktionstests durchgeführt wurden. Es fehlen die nötige Stabilität und wichtige Funktionen ­ ihr eigentlicher Nutzen geht verloren oder wird durch Instabilität und unzureichende Konfigurationsmöglichkeiten vermindert. Verifikationstools stecken häufig noch in den Kinderschuhen, haben viele Fehler und unzureichende Konfigurationsmöglich- keiten. Solche Tools werden als Alpha bzw. Betaversionen bezeichnet. Dieses Kriterium bewertet, wie stabil das Tool läuft, d.h. wie viele vom Benutzer nicht beeinflussbare Fehlermeldungen und Abstürze des Tools auftreten bzw. nicht auftre- ten (diese Bewertung erfolgt subjektiv). (BT12) Verfügbarkeit Oft gibt es verschiedene Versionen von Verifikationstools (z.B. Education Edition, Professional Edition), die unterschiedliche Funktionen besitzen. Versionen treten häufig bei kommerziellen Tools auf. Neben den verschiedenen Versionen spielt je- doch auch deren Disponibilität (z.B. sind noch ältere Versionen verfügbar, wie lange dauert die Beschaffung, müssen Registrierungen vorgenommen werden) eine wichti- ge Rolle. Dieses Kriterium bewertet, welche Versionen des Tools existieren, wo die Unter- schiede in den einzelnen Versionen liegen und wie hoch der Beschaffungsaufwand ist. (BT13) Verbreitung und Bekanntheitsgrad Dieses Kriterium bewertet, in wie weit das Verifikationstool in der Praxis zum Einsatz kommt, ob die Kenntnis über die Funktion auch in weiteren Projekten bzw. Aufga- benstellungen genutzt werden kann und ob umfangreiche Literatur und Referenzen verfügbar sind (diese Bewertung ist subjektiv). 3.3.2 Spezifikationssprachen (BS1) Definition von Korrektheitskriterien Dieses Kriterium bewertet, ob und in welchem Umfang die Spezifikationssprache die Definition von Korrektheitskriterien erlaubt. Dabei werden jedoch nur Kriterien in Be- zug auf Protokolle zur Konsistenterhaltung betrachtet (siehe Kapitel 6). (BS2) Modularität Die Modularität steht in engem Zusammenhang mit der Überprüfbarkeit einer Spezi- fikationssprache. Nur bei übersichtlichem und gut strukturiertem Code und unter Verwendung von Information Hiding (Erzeugung von Abstraktionsebenen) ist es Kapitel 3 - Bewertungskriterien der Verifikationstools 36 möglich, den Code auch für andere lesbar und damit überprüfbar zu machen. Dazu gehört unter anderem die Erzeugung von Modulen, d.h. von in sich geschlossenen Bestandteilen. Dieses Kriterium bewertet nun, in wie weit eine modulare Struktur durch die Spezifi- kationssprache unterstützt wird. (BS3) Eignung für die Modellierung von Interaktionen zwischen Prozessen in VS Dieses Kriterium bewertet, ob der Anwender mit Hilfe der Spezifikationssprache in der Lage ist, Interaktion zwischen Prozessen in VS (in unserem speziellen Fall, Kon- sistenzerhaltungsprotokolle) nachzubilden. (BS4) Vollständigkeit/Mächtigkeit Die Vollständigkeit einer Sprache steht in engem Zusammenhang mit dem vorange- gangenen Kriterium. Sie erweitert diesen Punkt jedoch um die Chance, alle erdenkli- chen Anwendungsfälle abzudecken, also nicht nur Interaktionen zwischen Prozessen in VS. Dies hat den Vorteil, dass nicht für jeden neuen Verwendungszweck eine neue Sprache verwendet und erlernt werden muss. Dieses Kriterium bewertet, wie breit das Anwendungsspektrum der Spezifikations- sprache ist (diese Bewertung erfolgt subjektiv). (BS5) Erlernbarkeit, Verständlichkeit Dieses Kriterium bewertet, wie schnell eine Einarbeitung und wie gut die Verständ- lichkeit der Spezifikationssprache ist (diese Bewertung erfolgt subjektiv). (BS6) Dokumentation Gerade für Neueinsteiger ist eine gute Dokumentation der Spezifikationssprache sehr wichtig. Hierzu gehören die ausführliche Beschreibung der gesamten Syntax sowie kleine" und große" Beispiele. Dieses Kriterium bewertet, wie gut die Dokumentation einer Sprache ist, um sie er- folgreich zu verwenden (diese Bewertung erfolgt subjektiv). (BS7) Implementierbarkeit Dieses Kriterium bewertet, wie schnell und mit welchem Aufwand Code erzeugt wer- den kann (diese Bewertung erfolgt subjektiv). (BS8) Verbreitung und Bekanntheitsgrad Dieses Kriterium bewertet, in wie weit die Spezifikationssprache in der Praxis zum Einsatz kommt, ob die Kenntnis über die Funktion auch in weiteren Projekten bzw. Aufgabenstellungen genutzt werden kann und ob umfangreiche Literatur und Refe- renzen verfügbar sind (diese Bewertung erfolgt subjektiv). (BS9) Abbildbarkeit in andere Sprachen (z.B. Java) Gerade im Bereich der Forschung (z.B. an Universitäten) sollen Weiterentwicklungen bzw. Verbesserungen von Spezifikationssprachen durchgeführt werden. Dazu benö- tigt man Kenntnis über die API der Sprache. Diese ist jedoch nicht immer verfügbar. Als Ausweg kann eine Portierung in eine andere Sprache (z.B. in Java) dienen. Dazu Kapitel 3 - Bewertungskriterien der Verifikationstools 37 müssen die Syntax sowie die Semantik der zu portierenden Sprache bekannt und in der Zielsprache realisierbar sein, d.h. sie muss z.B. in Java abbildbar sein. Dieses Kriterium bewertet, wie gut eine Sprache in eine Andere (z.B. Java) abgebil- det werden kann (diese Bewertung erfolgt subjektiv). (BS10) Überprüfbarkeit Häufig kommt es vor, dass Spezifikationssprachen schwer lesbar sind, d.h. sie ent- halten Konstrukte, die nur unter großem Zeitaufwand von Fachleuten verstanden werden können. Dazu gehören z.B. komplexe Reguläre Ausdrücke. Da solche Spra- chen gerade auch in der Lehre ein Hindernis darstellen, ist es wünschenswert, dass diese Sprachen einfache und leicht verständliche Ausdrücke besitzen, mit denen je- doch auch komplexe Aussagen möglich sind. Dieses Kriterium bewertet, ob eine Spezifikationssprache lesbar ist, d.h. ob sie von Fachleuten, unter geringem Aufwand verstanden und auf Fehler hin überprüft wer- den kann (diese Bewertung erfolgt subjektiv). (BS11) Lockerheit Dieses Kriterium bewertet, ob und in welchem Maß die Spezifikationssprache Unvoll- ständigkeiten und Nichtdeterminismus erlaubt. 3.3.3 Lehre (BL1) Erlernbarkeit, Verständlichkeit Sind Tool und Sprache zu kompliziert und unverständlich, eignen sie sich nicht für den Einsatz in der Lehre, da die Einarbeitungszeit zu lange ist und die Motivation der Studierenden negativ beeinflusst wird. Weitere Aspekte sind die Ergebnisaufberei- tung (Visualisierung; z.B. Animationen, Zeit-Sequenz-Diagramme, Zustandsdia- gramme, ...) und die Interaktionen des Tools mit dem Anwender, um die Verständ- lichkeit der Funktion von Protokollen zu verbessern. Welche Anforderungen an die Visualisierung und die Art der Interaktion zu stellen sind wird in [BRM98] erläutert. Dieses Kriterium bewertet, wie schnell eine Einarbeitung in das Tool und die Sprache erfolgt sowie die Möglichkeit(en) des Einsatzes in der Lehre (diese Bewertung erfolgt subjektiv). (BL2) Dokumentation/Hilfen Besonders beim Einsatz in der Lehre ist eine gute und ausführliche Dokumentation des Tools sowie der verwendeten Spezifikationssprache(n) notwendig. Hinzu kommen ausführlich (step-by-step) erklärte Beispiele, anhand derer ein Über- blick und Verständnis für das jeweilige Tool/Sprache gewonnen werden kann. Dieses Kriterium bewertet, wie gut die Dokumentation/Hilfe eines Tools/Sprache ist, um es erfolgreich in der Lehre zu verwenden (diese Bewertung erfolgt subjektiv). (BL3) Lernkurve Unter Lernen versteht man den Vorgang der Erkenntnisgewinnung durch das Aneig- nen von Wissen/Kenntnissen und deren Anwendung. Die Lernkurve beschreibt dabei die Geschwindigkeit und den Erfolg, ein gesetztes Lernziel zu erreichen. Kapitel 3 - Bewertungskriterien der Verifikationstools 38 Dieses Kriterium bewertet also, wie gut ein Tool/Sprache geeignet ist, um gesetzte Lernziele (z.B. in entsprechenden Vorlesungen) schnell und erfolgreich zu erreichen (diese Bewertung erfolgt subjektiv). (BL4) Benutzerführung Unter Benutzerführung versteht man die Art der Bedienung eines Programms. Die benutzbaren Funktionen, Befehle und Möglichkeiten sollten so angeboten wer- den, dass der Benutzer keine abstrakten Kommandos lernen oder nachschlagen muss. Dieses Kriterium bewertet, in wie weit der Benutzer des Tools durch das Programm geführt wird und wie leicht oder kompliziert die Verwendung bzw. Anwendung des Tools ist (diese Bewertung erfolgt subjektiv). (BL5) Standardisierung Standards sind Festlegungen, die zur Vereinheitlichung und Qualitätssicherung bei- tragen. Gerade im Bereich der Lehre ist darauf zu achten, dass Tools verwendet werden, die den internationalen Standards entsprechen und keine Individualprodukte darstellen. Dadurch wird gewährleistet, dass das vermittelte Wissen auch noch im späteren beruflichen Umfeld von Bedeutung ist. Dieses Kriterium bewertet, in welchem Maß die international definierten Standards unterstützt werden (diese Bewertung erfolgt subjektiv). (BL6) Verbreitung und Bekanntheitsgrad Um sich grundlegendes Wissen für das spätere Berufsleben anzueignen, sind solche Tools und Sprachen zu wählen, die weit verbreitet sind und einen gewissen Be- kanntheitsgrad besitzen. Dieses Kriterium bewertet, ob das Verifikationstool sowie die Spezifikationssprache zum Einsatz in der Lehre geeignet sind, d.h. ob die Kenntnis über die Anwendung und Funktion des Tools bzw. der Sprache auch nach Abschluss der Ausbildung noch relevant ist (diese Bewertung erfolgt subjektiv). (BL7) Verfügbarkeit Beim Einsatz von Verifikationstools in der Lehre ist es wichtig, dass die verwendeten Verifikationstools und Spezifikationssprachen kostengünstig bzw. kostenlos verfüg- bar sind. Oft gibt es spezielle Versionen, die genau für diesen Zweck entwickelt wur- den, teilweise jedoch Funktionseinschränkungen besitzen. Dieses Kriterium bewertet, welche Versionen des Tools bzw. der Sprache existieren und in wie weit sie für den Einsatz in Lehre geeignet sind. (BL8) Schnittstellen (API) zu anderen Tools Eine Schnittstelle ist der Berührungspunkt" zweier unterschiedlicher Systeme, in un- serem Fall zweier unterschiedlicher Verifikationstools, mit dem Zweck, unterschiedli- che Merkmale auszugleichen. Gerade wieder in der Lehre ist es wichtig, dass das verwendete Tool eine möglichst breite Schnittstelle zu weiteren, verbreiteten und be- kannten Verifikationstools besitzt. So kann die zusätzliche Einarbeitungszeit in fremde" Tools, durch die bereits bekannte Funktionalität des verwendeten Tools verkürzt werden. Kapitel 3 - Bewertungskriterien der Verifikationstools 39 Dieses Kriterium bewertet, wie gut, wie viele und welche Verifikationstools durch die Schnittstelle unterstützt werden (diese Bewertung erfolgt zum Teil subjektiv). 3.4 Gewichtung der Bewertungskriterien 3.4.1 Verifikationstools Bewertungskriterien (Tools) Gewichtung in % subjektive Beurteilung BT1 20 BT1a 10 I 2,5 II 2,5 III 2,5 IV 2,5 BT1b 3 BT1c 2,5 BT1d 2,5 BT1e 2 BT2 16 BT2a 5,5 BT2b 4 BT2c 2,5 BT2d 2 BT2e 1 BT2f 1 BT3 14 ( ) BT3a 10 I 4 II 3,5 III 1,5 IV 1 BT3b 4 I 2 II 2 BT4 10 BT4a 3,5 BT4b 3 Kapitel 3 - Bewertungskriterien der Verifikationstools 40 Bewertungskriterien (Tools) Gewichtung in % subjektive Beurteilung BT4c 2 BT4d 1,5 BT5 8,5 BT6 6,5 BT7 5,5 BT8 5 BT9 4 BT10 3,5 ( ) BT11 3 BT12 2,5 BT13 1,5 Tab 3-1: Gewichtung der Bewertungskriterien (Verifikationstools) 3.4.2 Spezifikationssprachen Bewertungskriterien (Sprachen) Gewichtung in % subjektive Beurteilung BS1 20 BS2 15 BS3 13 BS4 12,5 BS5 10 BS6 8,5 BS7 6,5 BS8 6 BS9 4,5 BS10 3 BS11 1 Tab 3-2: Gewichtung der Bewertungskriterien (Spezifikationssprachen) 3.4.3 Lehre Bewertungskriterien (Lehre) Gewichtung in % subjektive Beurteilung BL1 25 BL2 18 Kapitel 3 - Bewertungskriterien der Verifikationstools 41 BL3 15 BL4 12 BL5 10,5 BL6 8 BL7 7,5 BL8 4 ( ) Tab 3-3: Gewichtung der Bewertungskriterien (Lehre) subjektive Beurteilung ( ) teilweise subjektive Beurteilung Kapitel 4 - Verifikationstools 42 Kapitel 4 4 V VEERRIIFFIIKKAATTIIO ON NS STTO OO OLLS S Um die automatische Überprüfung von Systemen zu ermöglichen, werden ­ wie in Kapitel 2 bereits erläutert ­ sog. Verifikationstools eingesetzt. Mit Hilfe von Simulato- ren und Verifikatoren, welche von den meistens Tools zur Verfügung gestellt werden, können das Verhalten simuliert sowie die vom System zu erfüllenden Anforderungen frühzeitig getestet werden. Wie in Kapitel C zu sehen ist, gibt es sehr viele verschie- dene Vertreter von Verifikationstools. Jedes einzelne hat seine Vor- und Nachteile. Da im Rahmen dieser Diplomarbeit ein ausführlicher Test sämtlicher existierender Tools nicht möglich ist, werden drei typische Vertreter ausgewählt. In den folgenden Abschnitten sollen die wichtigsten Anforderungen an ein Verifikati- onstool nochmals kurz aufgegriffen, die Auswahl der zu evaluierenden Tools be- schrieben sowie eine kurze Einführung in die getesteten Verifikationstools gegeben werden. 4.1 Anforderungen Simulator Gerade beim Test von komplexen Systemen ist ein schneller, flexibler und mit einer umfangreichen Funktionalität ausgestatteter Simulator unabdingbar. Viele der im Ka- pitel C vorgestellten Verifikationstools besitzen einen integrierten Simulator, der je- doch selten die im Kapitel 3 definierten Kriterien eines Simulators erfüllt. Manche bie- ten eine gute visuelle Darstellung der Abläufe, sind jedoch instabil oder sehr lang- sam. Ferner sollten die integrierten Simulatoren auch die Möglichkeit des Debuggings bie- ten, da die Abbildung der gewünschten Verhaltensweisen eines Systems nicht immer trivial ist. D.h. bevor ein System auf die Erfüllung der gestellten Anforderungen hin überprüft werden kann (mittels Verifikator), muss es korrekt im verwendeten Verifika- tionstool abgebildet werden. Simulatoren die eine schrittweise (step-by-step) Ausfüh- rung ermöglichen und evtl. sogar die Anzeige von aktuellen Variablenwerten ermög- lichen, helfen Fehler bei der Abbildung des zu testenden Systems schnell zu finden. Verifikator Nachdem das zu testende System im Verifikationstool spezifiziert und auf seine syn- taktische Korrektheit hin überprüft wurde (Syntax Checking + Simulationsläufe), kommt der Verifikator zum Zug. Er kontrolliert, ob die vom Anwender an das System gestellten Anforderungen erfüllt werden können. Auch hier werden von den Werk- zeugen die verschiedensten Methoden zur Verfügung gestellt. Von Bedeutung sind jedoch vor allem der Grad der Überdeckung, die Generierung von Gegenbeispielen (falls ein Korrektheitskriterium nicht erfüllt werden kann) sowie die Möglichkeit der Ausführung des Gegenbeispiels im Simulator, um evtl. Fehler in der Spezifikation des Systems nachzuvollziehen und zu korrigieren. Die meisten Verifikationstools erfüllen diese Anforderungen, haben jedoch Probleme in Bezug auf die Effizienz. D.h. das Überprüfen größerer Systeme scheitert oft an zu Kapitel 4 - Verifikationstools 43 großem Speicherbedarf und sehr langen Wartezeiten (Abbruch der Verifikation durch den ungeduldigen" Benutzer). Sonstige Anforderungen Neben dem Simulator und dem Verifikator existieren eine Reihe weiterer wichtiger Anforderungen, ohne die ein modernes Verifikationstool nicht mehr auskommt. Dazu gehören z.B. die Anforderungen an moderne Spezifikationssprachen (siehe Abschnitt 3.3.2). Sie sind oft nicht Mächtig genug, um für die Verifikation des modellierten Sys- tems irrelevante Dinge (z.B. Warteschlangen, bei Konsistenzerhaltungsprotokollen) zu abstrahieren bzw. wichtige Details abzubilden (z.B. ist die Abbildung von Zeit in vielen Verifikationstools nicht möglich, d.h. die Simulation und Verifikation von Echt- zeitsystemen wird unmöglich). Ferner sind die Art und Weise der Definition von Korrektheitsbedingungen sowie die Einsatzfähigkeit in der Lehre von großer Bedeutung, da diese Tools häufig an Uni- versitäten im Rahmen von Vorlesungen eingesetzt werden. Dort wird versucht, durch die Verwendung von Verifikationstools, das Verständnis für die Arbeitsweise und die Verifikation von (komplexen) Systemen zu verbessern. 4.2 Auswahl der zu evaluierenden Verifikationstools Um die zu evaluierenden Verifikationstools auszuwählen, wurden die in Kapitel 3 de- finierten Bewertungskriterien herangezogen. Dabei war zu beachten, dass zumindest in den wesentlichen Punkten des Kriterienkataloges eine Bewertung möglich ist, d.h. die Tools mussten von vornherein einen bestimmten Funktionsumfang (eine Spezifi- kationssprache, einen Simulator und einen Verifikator) sowie ein graphisches Inter- face besitzen. Ferner wurden Werkzeuge mit unterschiedlichen Prinzipien zur Abbil- dung eines zu validierenden Systems ausgewählt. Dabei wurde zwischen den drei Methoden 1) Abbildung mit Hilfe von Transitionssystemen und einer Spezifikationssprache zur Definition von Guards, Assignments, Invarianten und Synchronisationen, 2) komplette Abbildung durch eine Spezifikationssprache und 3) Abbildung durch die vollständige Implementierung und Verifikation sowie Simula- tion auf diesem Code unterschieden. Nach einer ersten Auswahl auf der Basis der o.g. Kriterien, standen die folgenden Tools zur Wahl: CADP, FC2Tools, Model-Checking-Kit, PEP, Spin, Temporal Rover, UPPAAL, Verisoft, Vip Leider konnten im Rahmen dieser Diplomarbeit nicht alle diese Tools getestet wer- den, d.h. die Auswahl wurde weiter eingeschränkt. Um die grundlegenden Methoden und Verfahren des Model Checking und ihre Tools zu testen, sowie eine gerechte Bewertung zu gewährleisten, wurden alle die Tools verworfen, die Schnittstellen zu Spezifikationssprachen bzw. Funktionen und Algorithmen anderer Werkzeuge besit- zen (z.B. PEP ­ Schnittstellen zu INA, FC2Tools, SMV, Spin). Daraus folgt, dass alle ausgewählten Werkzeuge in die Kategorie der Tools fallen. Zusätzlich wurde beson- ders auf die Plattformunabhängigkeit, die Verbreitung und die Dokumentation geach- tet. Übrig geblieben sind die Tools UPPAAL, Spin und Verisoft. Kapitel 4 - Verifikationstools 44 4.3 Ausgewählte Verifikationstools UPPAAL UPPAAL fällt in die Gruppe der Tools, d.h. es gibt keine Schnittstellen zu anderen Verifikationstools. Es besitzt eine eigene Spezifikationssprache" zur Definition von Systemprozessen (z.B. zur Spezifikation von Guards) und Korrektheitskriterien (siehe Anhang A.1). Die Abbildung des zu validierenden Systems erfolgt auf der Basis von Transitions- systemen, die durch Konstrukte wie z.B. Guards, Assignments und Synchronisatio- nen vervollständigt werden. UPPAAL besitzt einen integrierten graphischen Simulator. Dieser ermöglicht u.a. die schrittweise Ausführung sowie das Laden und Speichern von Traces. Der Verifikator dieses Tools ist neben der normalen" Validation in der Lage, Gegen- beispiele zu erzeugen und diese in den Simulator zu laden und auszuführen. Die folgende Abbildung zeigt den Simulator von UPPAAL. Abb.4-1: Simulator (UPPAAL) Spin Genau wie UPPAAL, besitzt Spin keine Schnittstellen zu anderen Verifikationstools, d.h. es fällt ebenfalls in die Gruppe der Tools und besitzt eine eigene Spezifikations- sprache (Promela). Ein zu validierendes Systems wird komplett über die Spezifikationssprache abgebil- det. Der integrierte Simulator und Verifikator ist textorientiert, d.h. in der Basisversion von Spin erfolgt keine graphische Ausgabe. Es existiert jedoch ein Frontend (XSpin ­ siehe Abbildung 4-4), mit dessen Hilfe eine Visualisierung ermöglicht wird. Ferner Kapitel 4 - Verifikationstools 45 können vom Verifikator im Fehlerfall (Nichterfüllung einer Anforderung) gespeicherte Traces im Simulator ausgeführt werden. Abb.4-2: graphisches Interface von Spin (XSpin) Verisoft Auch Verisoft gehört zur Gruppe der Tools. Es besitzt keinerlei Schnittstellen zu an- deren Verifikationstools, d.h. Simulator und Verifikator sind hier integrierte" Kompo- nenten. Im Gegensatz zu UPPAAL und Spin kann das zu validierende System in einer belie- bigen Programmiersprache spezifiziert werden (in der getesteten Version in C). Simulator und Verifikator basieren auf except (Tcl-Applikation, zur Automatisierung der Kontrolle von interaktiven Programmen) und gdb (C/C++ Debugger). Die Ausga- ben sind graphisch oder textuell. Ein weiterer Unterschied zu UPPAAL und Spin ist die Definition und Überprüfung von Korrektheitskriterien ­ die Definition erfolgt direkt im Code, die Überprüfung der Krite- rien während der Simulation. Auch hier können die vom Verifikator gefundenen Feh- lerpfade im Simulator (Abb. 4-5) nachvollzogen werden. Die drei in diesem Abschnitt vorgestellten Verifikationstools sollen später anhand ei- nes Protokolls zur Konsistenzerhaltung getestet werden. Wichtige Grundlagen zum Verständnis dieser Protokolle werden im nächsten Kapitel gelegt. Kapitel 4 - Verifikationstools 46 Abb.4-3: Simulator (Verisoft) Kapitel 5 - Nebenläufigkeitskontrolle 47 Kapitel 5 5 N NEEBBEENNLLÄÄUUFFIIG GK KE EIITTS SK KO ON NTTR RO OLLLLE E Das gemeinsame Benutzen und Austauschen von Informationen ist integraler Teil von CSCW-Systemen. Die Kontrolle der Nebenläufigkeit ist daher wichtig, um die Informationen konsistent zu halten. Wichtige Aspekte sind dabei neben kurzen Ant- wort- (Zeit bis eigene Änderungen sichtbar werden) und Benachrichtigungszeiten (Zeit bis eigene Änderungen an alle anderen Teilnehmer propagiert wurden) auch die Robustheit (Wiederanlauf nach Maschinenabstürzen oder Kommunikationsfehlern) sowie die Notifikation (Mechnismen zur Benachrichtigung bei Veränderungen). Es gibt nun eine ganze Reihe von Verfahren, um die verschiedensten Konsistenzan- forderungen zu erfüllen. Im Rahmen dieses Kapitels sollen die wichtigsten Mecha- nismen kurz vorgestellt und charakterisiert werden. Im Anschluss wird der zum Test der Verifikationstools verwendete Grove-Algorithmus im Detail beschrieben. 5.1 Grundlegendes Die Verfahren zur Nebenläufigkeitskontrolle in existierenden CSCW-Systemen wer- den nach [BoSc95] wie folgt klassifiziert: Verfahren optimistische pessimistische dezentrale Kontrolle zentrale Kontrolle mit Votierung ohne Votierung Abb.5-1: Klassifizierung von Verfahren zur Nebenläufigkeitskontrolle Die optimistischen Verfahren sichern die Konsistenz der Daten nicht in jedem Fall. Sie erlauben dagegen einen inkonsistenten Zugriff, was für spezielle Anwendungen von Vorteil sein kann. Im Gegensatz dazu stehen die pessimistischen Verfahren, die keine inkonsistenten Zugriffe erlauben. In CSCW-Systemen, wie z.B. Mehrbenutzereditoren, muss das Problem des neben- läufigen Zugriffs auf gemeinsame Daten und deren Konsistenz gelöst werden. Dabei spielen u.a. die Techniken der verteilten Datenbanksysteme (z.B. Transaktionen) eine Rolle. Diese i.Allg. pessimistischen Ansätze sind in vielen CSCW-Anwendungen äußerst unpraktisch (Einschränkung der Parallelität) und überflüssig(zu strenge Ne- benläufigkeitskontrolle ­ keine inkonsistenten Zugriffe erlaubt). Eine weniger pessi- mistische Nebenläufigkeitskontrolle kann den Grad des parallelen Arbeitens erhöhen, ohne auf die notwendigen Konsistenzanforderungen zu verzichten. Aufgrund der hohen Anforderungen bezüglich der Antwortzeiten an CSCW-Systeme liegen die gemeinsamen Daten meistens in replizierter Form vor. Dies ist besonders Kapitel 5 - Nebenläufigkeitskontrolle 48 bei lesenden Zugriffen von Vorteil, da die Benutzer nicht mehr auf entfernte Daten sondern auf eine lokale Kopie zugreifen können. Bei schreibenden Zugriffen erhöhen sich i.Allg. die Antwortzeiten, da der Aufwand für die Konsistenzerhaltung steigt. Es gibt nun eine ganze Reihe von Verfahren, mit deren Hilfe man die unterschied- lichsten Konsistenzanforderungen erfüllen kann. Aus dem Bereich der verteilten Da- teisysteme stammen die modernsten uns heute bekannten Verfahren. Sie basieren in erster Linie auf Verfahren mit dezentraler Kontrolle. Hierzu zählen z.B. die Votie- rungsverfahren. Die verwendeten Mechanismen werden in dieser Arbeit nach dem Grad der Konsis- tenzerhaltung gegliedert, wobei mit den optimistischen Verfahren begonnen wird. optimistische Verfahren optimistisch einfache Sperrverfahren Floor Passing-Verfahren Transaktionsverfahren Transformationsverfahren Votierungsverfahren Gitterprotokoll pessimistisch 5.2 Mechanismen In diesem Abschnitt werden die Mechanismen zur Kontrolle der Nebenläufigkeit kurz charakterisiert. Diese basieren auf den Ausführungen in [BoSc95]. Optimistische Verfahren Durch den Einsatz von optimistischen Verfahren ist es den Benutzern möglich, zu jedem Zeitpunkt Knoten zu ändern und neu zu erstellen ­ unter Knoten wird hier die Aufteilung eines Textes in viele Einzelknoten (z.B. einzelne Buchstaben oder Wörter) verstanden. Da viele Knoten parallel geändert werden können, wird eine Leistungs- steigerung erreicht. Die Wahrscheinlichkeit der konkurrierenden Zugriffe sinkt, Kon- flikte treten dennoch auf ­ aus diesem Grund sollten sie eher selten sein. Gerade im Bereich der verteilten Mehrbenutzereditoren kann von einer geringen Wahrschein- lichkeit für Zugriffe auf dieselben Knoten nicht ausgegangen werden. Deshalb wer- den nichtoptimistische Verfahren eingesetzt, die zwar die Leistung optimistischer Verfahren nicht erreichen, jedoch eine Konsistenzerhaltung selbst bei einer höheren Wahrscheinlichkeit konkurrierender Zugriffe erlauben. Einfache Sperrverfahren Bei den einfachen Sperrverfahren besitzen die gemeinsamen Daten Lese- und Schreibsperren, wobei die folgenden drei Punkte zu beachten sind: 1) Zusatzaufwand für das Anfordern und Setzen der Sperre + evtl. Wartezeiten, falls die Sperre nicht sofort gewährt wird. 2) Die Sperrgranularität hat entscheidenden Einfluss auf den Grad der Nebenläufig- keit (z.B. Sperren eines einzelnen Zeichens oder der ganzen Datei). 3) Wann soll eine Sperre gesetzt werden? Man unterscheidet zwischen Sperren durch Zugriffsrechtemasken, Sperrverfahren ohne Replikation, Sperrverfahren mit Caching und zentralisierte Sperrverfahren bei vollständiger Replikation. Kapitel 5 - Nebenläufigkeitskontrolle 49 Floor Passing-Verfahren Im Gegensatz zu den Sperrverfahren werden bei diesen Mechanismen keine Sper- ren benötigt, da die Zugriffsrechte abwechselnd an die Gruppenteilnehmer vergeben werden. Die Floor-Passing-Verfahren werden erfolgreich in sog. Konferenzsystemen eingesetzt. Sie verhindern jedoch eine parallele Arbeitsweise. Man unterscheidet dabei explizite und implizite sowie Verfahren mit und ohne Zeit- beschränkung. Innerhalb der impliziten Verfahren gibt es ferner eine Verfahrensklas- se mit dezentraler Koordination. Transaktionsverfahren Transaktionsverfahren werden i.d.R. dann verwendet, wenn die Gruppenarbeit asyn- chron stattfindet, d.h. die Gruppenteilnehmer arbeiten zu verschiedenen Zeiten und an verschiedenen Orten an einem gemeinsamen Objekt. Die Operationen eines Benutzers werden zu einer Transaktion zusammengefasst. Diese greift auf gemeinsame Daten ohne Beeinflussung durch andere Transaktionen zu, wodurch die Serialisierbarkeit von Operationen erreicht wird. Es gelten die ACID Eigenschaften. Die Nachteile von Transaktionen sind, dass die Verteilung der Infor- mationen zu langen Antwortzeiten und zur Isolierung der Benutzer (dem Benutzer wird vorgegaukelt, er sei alleiniger Benutzer) führt. Diese Mechanismen werden hauptsächlich in Datenbanksystemen verwendet. Transformationsverfahren Transformationsverfahren greifen auf kleine Dateneinheiten, wie z.B. einzelne Wörter oder gar einzelne Zeichen zu. Sie werden deshalb für eng gekoppelte, synchrone Gruppenarbeit verwendet. Änderungen durch Gruppenteilnehmer werden sofort wirk- sam und allen anderen Teilnehmern propagiert und sichtbar gemacht (WYSIWIS- Prinzip). Zeitaufwendige Transaktionsverfahren sind deshalb nicht möglich, d.h. es muss auf eine strenge Serialisierbarkeit der Editiervorgänge verzichtet und eine op- timistischere Nebenläufigkeitskontrolle akzeptiert werden. Ein typischer Vertreter ist Grove (siehe Abschnitt 5.3). Votierungsverfahren Votierungsverfahren gehören zur Klasse der pessimistischen Verfahren zur Siche- rung der Nebenläufigkeitskontrolle. Sie werden seit langem erfolgreich in verteilten Systemen eingesetzt, finden dagegen in CSCW-Systemen keine Anwendung. Votierungsverfahren eignen sich besonders dann, wenn z.B. ganze Dateien als Zugriffseinheit verwendet werden. Sie garantieren eine hohe Verfügbarkeit ohne auf die geforderte Konsistenz zu verzichten. In den vergangenen Jahren wurden viele verschiedene Varianten entwickelt. Dazu gehören z.B. Verfahren mit Mehrheitsent- scheidung und das gewichtete Votieren. Gitterprotokoll Das Gitterprotokoll dient, genau wie die Votierungsverfahren, zur Synchronisation der Zugriffe auf replizierte Daten. Im Gegensatz zum Votierungsverfahren wird der gegenseitige Ausschluss nicht durch ein geeignetes Lese- oder Schreibequorum er- reicht, sondern aufgrund einer logischen Organisation der dateibesitzenden Rechner im Netz und einer geschickten Ausnutzung dieser Organisation. Dadurch stehen Le- se- und Schreibzugriffe unter gegenseitigem Ausschluss (dateibesitzende Rechner werden in einer sog. Gittertopologie logisch organisiert). Kapitel 5 - Nebenläufigkeitskontrolle 50 R9 R10 R11 R12 + = Schreibe-Votum R5 R6 R7 R8 = Lese-Votum R1 R2 R3 R4 Abb.5-2: Beispiel einer Gittertopologie Lese- und Schreibzugriffe benötigen ein Votum. - Ein lesender Zugriff muss die Zugriffszustimmung von mindestens einem Rechner in jeder Spalte haben. - Ein schreibender Zugriff muss die Zugriffszustimmung von mindestens einem Rechner in jeder Spalte und zusätzlich die Zustimmung aller Rechner mindestens einer Spalte im Gitter besitzen. 5.3 Der Grove-Algorithmus im Detail Zu einem typischen Vertreter der Transformationsverfahren zählt der Grove- Algorithmus. Er wurde verwendet, um die in Kapitel 4 ausgewählten Verifikationstool, am Beispiel eines Konsistenzerhaltungsprotokolls zu bewerten und zu testen. Ferner soll mit Hilfe der in Abschnitt 4.2 ausgewählten Verifikationstools, die in [BoSc95] bewiesene Korrektheit des Grove-Algorithmusses überprüft werden. Der nun folgende Abschnitt gibt eine detaillierte Definition des o.g. Algorithmus wie- der. Definition und Charakterisierung basieren dabei auf [Sch00] und [BoSc95]. 5.3.1 Grundlagen Grove steht für Group Outline Viewing Editor und ist ein Mehrbenutzereditor, der von Ellis et al. am MCC in Austin Texas, USA, im Rahmen eines Software-Technologie- Programms entwickelt wurde. Er verwendet den Mechanismus der Operationstrans- formation zur pessimistischen Nebenläufigkeitskontrolle. Dabei wird auf eine strenge Serialisierbarkeit der Editiervorgänge verzichtet und eine "optimistischere" Nebenläu- figkeitskontrolle akzeptiert, Änderungen werden sofort wirksam. Das Verfahren findet für replizierte Informationen Anwendung. Die Nebenläufigkeitskontrolle in Grove basiert auf dem Begriff der Operationstrans- formation, d.h. für zwei Operationen o1 und o2 muss gelten: o2' o1 = o1' o2, wobei o1' und o2' die transformierten Operationen zu o1 und o2 sind. Grove sichert die Kon- sistenz des Dokuments, unabhängig von der Art und Reihenfolge der Operationen (insert, delete), zu. Semantische Konflikte werden nicht erkannt. Voraussetzungen - Alle Operationen werden sofort lokal ausgeführt, d.h. Sperren werden nicht benö- tigt. - Der Algorithmus ist robust gegenüber Rechnerabstürzen. - Die Zugriffsgranularität ist ein einzelnes Zeichen. - Die Anzahl der beteiligten Rechner ist konstant. - Alle Nachrichten werden genau einmal und fehlerfrei gesendet bzw. empfangen. Kapitel 5 - Nebenläufigkeitskontrolle 51 - Alle Nachrichten werden explizit von den Benutzern generiert. Prinzip des Grove-Algorithmus Nachdem eine Operation an einem Rechner initiiert wurde, wird sie lokal ausgeführt und eine Priorität für diese Operation berechnet. Anschließend wird die Operation zusammen mit der Priorität an alle beteiligten Rechner propagiert. Die Empfänger reihen diese in ihre Warteschlange ein. Wurden vorher konkurrierende Operationen ({insert,insert}, {insert, delete}, {delete, insert}, {delete, delete}) ausgeführt, wird de- ren Priorität überprüft und gegebenenfalls eine Transformation durchgeführt. Nach ihrer Ausführung werden die Operation und ihre Priorität im Operationslogbuch ge- speichert. Nachteile - Alle Operationen werden im Operationslogbuch gespeichert ­ die Datenstruktur wächst kontinuierlich. - Die Granularität des Systems ist sehr fein ­ die große Datenmenge im Logbuch, kann die Leistung des Verfahrens stark verringern. - Vor jeder Operationstransformation muss das gesamte Logbuch durchsucht wer- den. Aus diesem Grund erzwingt Grove regelmäßige Ruhephasen, in denen die noch ausstehenden Operationen vollständig abgearbeitet und die Logbücher gelehrt wer- den. Laut Aussagen der Designer sollten die Ruhepausen im Mittel alle 10 Sekunden erfolgen, was ein flüssiges arbeiten jedoch stark beeinträchtigt. Korrektheit In [BoSc95] wird ein Korrektheitsbeweis für den hier beschriebenen Grove- Algorithmus angegeben. Den zu überprüfen, wird die Aufgabe der ausgewählten Ve- rifikationstools sein (siehe Abschnitt 7.5.2). 5.3.2 Definition und Ablauf Teilnehmersysteme Sei G ein Gruppenprozess und g ein Element der Menge der Gruppensitzungen von G. g ist eine synchrone, verteilte Gruppensitzung, an der n > 1 Gruppenteilnehmer teilnehmen. g wird modelliert als Paar (TS, O). TS ist die Menge der Teilnehmersys- teme. Pro Gruppenteilnehmer von g gibt es genau ein Teilnehmersystem s TS. Im Allgemeinen läuft s auf einem Rechner ab, z.B. auf dem Arbeitsplatzrechner des Be- nutzers. Mehrere s TS können auf demselben Rechner parallel ablaufen. O sei eine Menge von parametrisierten Operatoren. Die Ausführung eines Operators unter Angabe der Parameter heißt Operation Jedes Teilnehmersystem s TS besteht aus einem Tripel (TS-Prozess, TS-Objekt, Ts-Identifikator) mit: TS-Identifikator ­ eindeutiger Bezeichner für das Teilnehmersystem von g TS-Objekt ­ passives Datenobjekt (z.B. Dokument, das bearbeitet wird) TS-Prozess ­ Erzeugung von Operationen, Empfang einer Operationsanforde- rung, Ausführung einer Operationsanforderung Weiterhin wird angenommen, dass innerhalb von g ein Textverarbeitungssystem verwendet wird, d.h. das TS-Objekt von s ist eine Zeichenkette. Daraus resultieren die folgenden beiden Operationen: Kapitel 5 - Nebenläufigkeitskontrolle 52 1) O1 = insert[X; ] ­ das Zeichen X wird an Position eingefügt 2) O2 = delete[ ] ­ das Zeichen an Position wird gelöscht Transformationsmatrix Zur Transformation von Operationen wird eine Transformationsmatrix benutzt. Sei g=(TS, O) eine Gruppensitzung und T eine Transformationsmatrix (m m) von g, mit m=|O|. Seien oi, oj Operationen mit Prioritäten pi und pj. Ou bzw. Ov mit u,v {1,...,m} seien die zu oi bzw. oj gehörigen Operatoren. Weiterhin existiere ein T mit den bei- den Elementen oj'= Tvu (oj, oi, pj, pi) für oj oj' gemäß oi und oi'= Tuv (oi, oj, pi, pj) für oi oi' gemäß oj, das die Bedingung oj' oi = oi' oj erfüllt. Für das Element oi' gilt bei gegebenen Operationen insert und delete die folgende Transformationsmatrix: insert ( [Xi; i],insert[Xj; j],pi,pj) insert ( [Xi; i], [ delete j],pi,pj ) ( [ delete i],insert[Xj; j],pi,pj) ( [ delete i]; [ delete j]) Sei oi die ursprüngliche und oi' die transformierte Operation, dann könnte eine mögli- che Implementierung der Transformationsmatrix so aussehen: (insert [Xi; i], insert [Xj; j], pi , pj) if ( i < j) then oi':=insert[Xi; i]; else if ( i > j) then oi':=insert[Xi; i+1]; else if (Xi = Xj) then oi'= ; /* Position & Operation beider Operationen sind gleich, d.h. Opertion darf nur einmal ausgeführt werden. */ else if (pi > pj) then oi':=insert[Xi; i+1]; /* oi wird vor oj ausgeführt, d.h. oi muss um eine Stelle nach rechts geschoben werden */ else oi':=insert[Xi; i]; fi; fi; fi; fi; (insert [Xi; i], delete [ j], pi , pj) if ( i < j) then oi':=insert[Xi; i]; else oi':=insert[Xi; i-1]; fi; (delete [ i], insert [Xj; j], pi , pj) if ( i < j) then oi':=delete[ i]; else oi':=delete[ i+1]; fi; (delete [ i], delete [ j], pi , pj) if ( i < j) then oi':=delete[ i]; else if ( i > j) then oi':=delete[ i-1]; else oi'= ; fi; fi; Datenstrukturen Zustandsvektor Sei N = |TS| von g, i TS: (TS-Identifikator von i) [1, N]: TS-Indentifikator ist eindeutig. Ein Zustandsvektor si ist ein Vektor aus N Komponenten, wobei die j-te Komponente angibt, wie viele Operationen des TS j durch das TS i bereits ausgeführt wurden. Seien si und sj Zustandsvektoren der Teilnehmersysteme i und j, dann gilt: si = sj, d.h. k [1, N]: (si)k = (sj)k si < sj, d.h. k [1, N]: (si)k (sj)k und l [1, N]: (si)l < (sj)l si > sj, d.h. k [1, N]: (si)k > (sj)k Priorität Die Priorität einer Operation o wird zur Zeit der Ausführung beim Erzeuger- Teilnehmersystem i berechnet und über die Operations-Anforderung an alle ande- ren Teilnehmersysteme verbreitet. Kapitel 5 - Nebenläufigkeitskontrolle 53 Seien sr die Originalposition" der Operation einer Anforderung r in Li und so die Position der erzeugten Operation o sowie pr die Priorität der Operation von r und po die Priorität von o Berechnung der Priorität po von o: es existiert eine bereits ausgeführte Operation mit gleicher Position k Li: sk = so und ( r Li: sk = sr und pk pr), dann gilt: po = (pk, i) sonst gilt: po = (i), wobei i = Index von TS Vergleich von Prioritäten Seien ps, pr die Prioritäten der Operationen von s und r, dann hat die Operation von s eine höhere Priorität als die Operation von r a) k [1..|ps|]: (ps)k > (pr)k und l [1..k]: (ps)l = (pr)l b) |ps| > |pr| und ( l [1..|pr|]: (ps)l = (pr)l Operationsanforderung Eine Operationsanforderung ist ein Quadrupel der Form , mit i: TS-Identifikator des Teilnehmersystems s: Zustandsvektor des Teilnehmersystems i o: Operation p: Priorität von Operation o Operationswarteschlange Initiierte bzw. empfangene Operationen werden bis zur Ausführung in einer War- teschlange gehalten, wobei Qi die Operationswarteschlange des Rechners i be- zeichnet. Operationslogbuch Ausgeführte Operationen werden nach Ihrer Ausführung in ein Operationslogbuch eingetragen, wobei Li das Operationslogbuch des Rechners i bezeichnet. Ablauf des Grove-Algorithmus In diesem Abschnitt wird der Grove-Algorithmus ("Distributed Operational Transfor- mation" (dOPT) Algorithmus), wie er aus der Sicht des Teilnehmersystems i abläuft, beschrieben. Hole Operation o aus Qi hat der Sender von o o in Q Operationen ausge- i zurück- schreiben führt, aber i noch nicht? hat i Operationen aus- Operation o ausführen geführt, aber der Sen- und in L der von o noch nicht ? i eintragen transformiere o mit allen Operationen aus Li, die Sender von o noch nicht ausgeführt hat Abb.5-3: Ablauf des Grove-Algorithmus Kapitel 5 - Nebenläufigkeitskontrolle 54 main() { Initialisierung(); while not abort do { if there is an input o then { generate_request (o) /* lokale Operation */ execute_request() } else { receive_request() /* entfernte Operation */ execute_request() } } } Initialisierung() { Li = Qi = si = <0,0, ...0> /* 0 für alle Teilnehmersysteme */ } generate_request(o) { empfange Operation o vom Benutzer berechne Priorität p von o r = Qi = Qi + r propagiere r an alle anderen Teilnehmersysteme } receive_request() { empfange vom Netz r' = Qi = Qi + r' } execute_request() { for each Qi mit sj si do { Qi = Qi - if sj < si then { and oj do { if (die k-te Komponente von sj die k-te Komponente von sk) then { sei u Index des Operators Ou (oj ist Instanz von Ou) sei v Index des Operators Ov (ok ist Instanz von Ov) oj := Tuv } := nächster, relevanter Eintrag in Li; (oder ) } /* end while */ } /* end if */ führe Operation oj aus; Li = Li + si := si mit j-ter Komponente um eins inkrementiert } /* end for each */ } 5.3.3 Beispiel Anhand des folgenden Beispiels soll die Arbeitsweise des Grove-Algorithmus noch- mals kurz verdeutlicht werden. Seien zwei Prozesse P1 und P2 gegeben, die jeweils genau eine Operation erzeugen können, d.h. P1 und P2 müssen genau 2 Operationen ausführen (P1: die erzeugte Operation und die empfangene Operation von P2; P2: die erzeugte Operation sowie die empfangene Operation von P1). Dabei ist die durch P1 erzeugte Operation mit insert [´x´; 1] und die durch P2 erzeugte Operation mit insert [´y´; 1] gegeben. Weiter- hin ist definiert: i1, i2 sind die TS-Identifikatoren von P1 und P2 s1, s2 sind die Statusvektoren von P1 und P2 o1, o2 sind die Operationen von P1 und P2 p1, p2 sind die Prioritäten von P1 und P2 Kapitel 5 - Nebenläufigkeitskontrolle 55 Q1, Q2 sind die Warteschlangen von P1 und P2 L1, L2 sind die Logbücher von P1 und P2 Damit ist ein möglicher Ablauf: P1 P2 i1 = 1 s1 = (0,0) i2 = 2 o1 = insert[´x´;1] s2 = (0,0) p1 = 1 o2 = insert [´y´;1] p2 = 2 Q1 ={(1, (0,0), insert[´x´;1], 1)} Q2 = {(2, (0,0), insert[´y´;1], 2)} L1 ={(1, (0,0), insert[´x´;1], 1)} s1 = (1,0) L2 = {(2, (0,0), insert[´y´;1], 2)} s2 = (0,1) i2 = 2 s2 = (0,0) o2 = insert [´y´;1] p2 = 2 i1 = 1 s1 = (0,0) Q1 ={(2, (0,0), insert[´y´;1], 2)} o1 = insert[´x´;1] p1 = 1 o1' = insert [´y´;2] Q2 = {(1, (0,0), insert[´x´;1], 1)} L1 = {(1, (0,0), insert[´x´;1], 1), (2, (0,0), insert[´y´;2], 2)} o2' = insert[´x´;1] s1 = (1,1) L2 ={(2, (0,0), insert[´y´;1], 2), (1, (0,0), insert[´x´;1], 1)} s2 = (1,1) xy xy Abb.5-4: Beispiel für den Grove-Algorithmus Kapitel 6 ­ Charakteristika von Prtkl. zur Konsistenzerhaltung 56 Kapitel 6 6 C CHHAARRAAKKTTEERRIISSTTIIKKAA VVO ON N P PRRO OTTO OK KO OLLLLE EN N Z ZU UR R K KO ON NS SIIS STTE EN NZZE ER RH HA ALLTTU UN NG G In diesem Kapitel werden Kriterien beschrieben, anhand derer die Charakteristika von Konsistenzerhaltungsprotokollen ermittelt werden können. Dabei liegt der Fokus auf der Konsistenz und den Anwendungsaspekten, was vor allem für mobile Benut- zer von großer Bedeutung ist. Wie in Kapitel 3 können einige der Kriterien ebenfalls nur subjektiv bewertet werden. Die Reihenfolge der Kriterien entspricht gleichzeitig deren Wichtigkeit während der Bewertung" (siehe dazu Gewichtung der Kriterien ­ weiter unten in diesem Kapitel). Eine detaillierte Beschreibung der einzelnen Punkte ist im Abschnitt 6.2 zu finden. 6.1 Kriterien zur Ermittlung der Protokollcharakte- ristik CP1. Konsistenz CP1a. Datenkonsistenz I. Konsistenz bei zentraler Instanz II. Konsistenz bei Replikaten III. syntaktische und semantische Konsistenz IV. interne und externe Konsistenz V. Grad der Konsistenz CP1b. Protokollkonsistenz I. Deadlocks II. Livelocks III. Terminierung IV. Fairness (Monopolisierung) CP2. Anwendungsaspekte CP2a. Atomizität CP2b. Sicherheit vor Angriffen CP2c. Fehlertoleranz CP2d. Verfügbarkeit CP2e. Nachweisbarkeit CP3. Komplexität/Leistung CP3a. Nachrichten CP3b. Protokoll Kapitel 6 ­ Charakteristika von Prtkl. zur Konsistenzerhaltung 57 CP3c. Implementierung CP4. Verbreitung und Bekanntheitsgrad 6.2 Erläuterung der Bewertungskriterien In diesem Kapitel erfolgt eine Beschreibung der wichtigsten Bewertungskriterien. (CP1) Konsistenz Das lateinische Wort Konsistenz", bedeutet soviel wie Widerspruchslosigkeit bzw. streng logischer Zusammenhang. Es bezieht sich in der Informatik hauptsächlich auf den Zustand von Daten, aber auch auf Protokolle. Gerade in VS, vor allem unter Be- rücksichtigung mobiler Benutzer, spielen Protokolle zur Konsistenzerhaltung eine zentrale Rolle. Hier gilt es jedoch nicht nur die Konsistenz der Daten zu erhalten, sondern auch den Einsatz von konsistenten Protokollen zu gewährleisten. Datenkonsistenz Unter Datenkonsistenz verstehe ich die Eignung des Protokolls zur Erhaltung der Konsistenz bei zentraler Datenhaltung (zentrale Instanzen) bzw. verteilter Datenhal- tung (Replikate), die syntaktische, semantische, interne und externe Konsistenz so- wie den Grad der Konsistenz (Nebenläufigkeitskontrolle). Protokollkonsistenz Unter Protokollkonsistenz fasse ich die Eigenschaften eines Protokolls bezüglich evtl. verursachender Deadlocks bzw. Livelocks, dessen Terminierung sowie der Fairness (Monopolisierung) zusammen. Dieses Kriterium bewertet, wie gut" das Protokoll die Konsistenz der Daten gewähr- leisten kann und welche Verfahren vom Protokoll verwendet werden, um Fehler und Inkonsistenzen zu vermeiden. (CP2) Anwendungsaspekte Unter Anwendungsaspekten verstehe ich fünf Gesichtspunkte, die die Konsistenzer- haltungsprotokolle für den Einsatz" qualifizieren. Dazu gehören die Atomizität, die Nachweisbarkeit, die Sicherheit vor Angriffen (Intrudern), die Fehlertoleranz (z.B. bei Knotenausfällen oder Netzwerkpartitionierung) sowie die Verfügbarkeit (Analyse der Verfügbarkeit von Replikaten, durch die Protokolle). Dieses Kriterium bewertet, wie gut" ein Protokoll für den Einsatz zur Konsistenzer- haltung in VS (anhand der o.g. Gesichtspunkte) geeignet ist. (CP3) Komplexität/Leistung Das Komplexitätskriterium muss zu einer sinnvollen Charakterisierung von Konsis- tenzerhaltungsprotokollen differenziert betrachtet werden, da es erheblichen Einfluss auf die Verwendbarkeit bzw. die Leistung des Protokolls besitzt. Aus diesem Grund werden die folgenden Komplexitäten unterschieden: die Nachrichtenkomplexität (An- zahl der Nachrichtenübertragungen, die vom Protokoll verursacht werden), die Pro- tokollkomplexität und die Implementierungskomplexität (Aufwand zur Implementie- rung des Protokolls). Dieses Kriterium bewertet die Verwendbarkeit eines Konsistenzerhaltungsprotokolls (diese Bewertung erfolgt zum Teil subjektiv). Kapitel 6 ­ Charakteristika von Prtkl. zur Konsistenzerhaltung 58 (CP4) Verbreitung und Bekanntheitsgrad Dieses Kriterium bewertet, in wie weit das Protokoll in der Praxis zum Einsatz kommt, ob die Kenntnis über die Funktion auch in weiteren Projekten bzw. Aufgabenstellun- gen von Nutzen ist und umfangreiche Literatur und Referenzen verfügbar sind (diese Bewertung erfolgt subjektiv). 6.3 Gewichtung der Kriterien Kriterien für Protokolle zur Konsistenzerhaltung Gewichtung in % subjektive Beurteilung CP1 56 CP1a 32 I 6,5 II 6,5 III 6,5 IV 6,5 V 6 CP1b 24 I 6 II 6 III 6 IV 6 CP2 28 CP2a 6,5 CP2b 6 CP2c 6 CP2d 5,5 CP2e 4 CP3 12,5 ( ) CP3a 7 CP3b 3,5 CP3c 2 CP4 3,5 Tab 6-1: Gewichtung der Bewertungskriterien (Konsistenzerhaltungsprotokolle) subjektive Beurteilung ( ) teilweise subjektive Beurteilung Kapitel 7 ­ Evaluation 59 Kapitel 7 7 E EVVAALLUUAATTIIO ON N In diesem Kapitel wird die Evaluation der ausgewählten Verifikationstools vorge- nommen. Dies erfolgt anhand der in Kapitel 3 beschriebenen Bewertungskriterien. Zunächst wird jedoch eine Notenabstufung vorgenommen und verdeutlicht, mit Hilfe welcher Berechnungsvorschrift die einzelnen Noten und Gewichtungen zu einem Gesamtwert zusammengefasst werden. 7.1 Grundlegendes Wie man in Kapitel 3 sehen kann, werden die Bewertungskriterien in drei verschie- dene Kategorien unterteilt. Diese Kategorien bleiben auch weiterhin bestehen, d.h. die Bewertung erfolgt getrennt voneinander. Am Ende erhält man also drei verschie- dene Bewertungen pro Verifikationstool. Da die einzelnen Kriterien von unterschiedlicher Bedeutung sind, wird jedem Kriteri- um eine Gewichtung in Prozent zugeordnet ­ addiert man alle Gewichtungen einer Kategorie ergibt die Summe 100 %. Zur Bewertung der einzelnen Kriterien werden Noten" von 1-6 vergeben. Dabei steht 6 für sehr gut und 1 für sehr schlecht. Die folgende Tabelle zeigt den Bewertungs- maßstab nochmals im Überblick. Stufe sehr gut gut befriedigend ausreichend schlecht sehr schlecht Wert 6 5 4 3 2 1 Tab.7-1: Bewertungsmaßstab für die Kriterien Bei der Wahl einer korrekten Berechnungsvorschrift für den Gesamtwert ist zu be- achten, dass der Wert für ein in allen Kriterien gleich gutes Tool besser ausfallen sollte als für eines mit sehr unausgeglichenen Werten. In dem hier benutzten Ansatz [Kai98], entsprechen die Gesamtwerte für Kategorien mit ähnlichen Bewertungen dem gewichteten arithmetischen Mittel. Driften die Einzelwerte jedoch auseinander, hat dies eine Abweichung für den Gesamtwert zur Folge. Die Berechnungsvorschrift lautet: 2 n x ges m i xi i 1 Dabei steht xges für den Gesamtwert, n für die Anzahl der Kriterien einer Kategorie, mi für das Gewicht eines Kriteriums und xi für die Bewertung selbst. Um eine gerechte Bewertung zu gewährleisten, wurde der im Abschnitt 5.3 beschrie- bene Grove-Algorithmus mit Hilfe der Tools abgebildet, simuliert und eine Verifikation durchgeführt. Kapitel 7 ­ Evaluation 60 7.2 UPPAAL 7.2.1 Verifikationstools (BT1) Simulator (BT1a) Simulationsmodi Der Simulator von UPPAAL stellt alle gewünschten Simulationsmodi zur Verfügung. Ferner hat der Anwender die Möglichkeit zu einem beliebigen Zeitpunkt den Simula- tionsmodus zu wechseln. Daraus ergeben sich 6 Punkte für jeden der drei Simulationsmodi und 6 Punk- te für die Wechselmöglichkeit der Simulationsmodi. (BT1b) Suspend- und Go-On-Modus Auch diese Möglichkeit wird vom Simulator unterstützt. So kann beispielsweise ein zufälliger Simulationslauf unterbrochen und schrittweise fortgesetzt werden. 6 Punkte (BT1c) Syntax-Checking Ein Syntax-Checking durch den Simulator erfolgt nicht. Diese Funktionalität währe jedoch z.B. für die Überprüfung des Überschreitens von Arraygrenzen während der Simulation hilfreich. 0 Punkte, da nicht vorhanden (BT1d) Protokollierung Der Simulator ist in der Lage alle ausgeführten Schritte während einer Simulationsausführung zu protokollieren und abzuspeichern, d.h. durch einen Simulationslauf erhaltene Traces können wiederholt ausgeführt werden, solange keine Änderungen am Systemmodell vorgenommen wurden. Es traten jedoch Fehler beim Laden gespeicherter Simulationsabläufe auf. 4 Punkte. (BT1e) Undo-Funktionalität Auch diese Funktionalität wird vom Simulator unterstützt. Es ist sehr einfach möglich, zu jedem Zeitpunkt, an einen gewünschten, protokollierten Punkt einer Simulation zu springen. Dazu werden vom Simulator alle aufgezeichneten Schritte angezeigt. Durch einen einfachen Klick, springt man zum gewünschten Zeitpunkt zurück. Leider ist hier keine Skalierung der angezeigten Punkte möglich, d.h. man muss unter Um- ständen lange Suchen, um den gewünschten Rücksprungpunkt zu finden. Eine Art Bookmarkfunktionalität wäre wünschenswert. 4,5 Punkte. (BT2) Verifikation (BT2a) Grad der Überdeckung Eine 100ige Überdeckung des Anwendungsbeispiels (Grove-Algorithmus) wurde er- reicht. 6 Punkte (BT2b) Generierung von test cases Der Verifikator von UPPAAL ist nicht zu einer automatischen Generierung von test cases in der Lage. Um kritische Eingabewerte zu überprüfen, müssen diese vom Be- nutzer im Systemmodell erzeugt werden. 0 Punkte Kapitel 7 ­ Evaluation 61 (BT2c) Simulationsausführung mit den generierten test cases als Eingabe Da die Generierung von test cases weder durch das Tool noch durch den Be- nutzer möglich ist, können auch hier nur 0 Punkte vergeben werden. (BT2d) Verifikationsgeschwindigkeit In Hinblick auf die Programmiersprache des Tools (Java) ist die Verifikationsge- schwindigkeit gut, jedoch nur ausreichend im Vergleich zu anderen Tools. 3 Punkte. (BT2e) Erzeugung und Ausführung von Gegenbeispielen im Fehlerfall Eine durch die immer komplexer werdenden Systeme nahezu notwendige Funktion ist die Erzeugung von Gegenbeispielen bei Nichterfüllung einer Anforderung und de- ren Ausführung im Simulator. Diese Funktionalität wird von UPPAAL zur Verfügung gestellt und kann gegebenenfalls deaktiviert werden. Da keine ersichtlichen Informationsmängel (z.B. Fehlen von zu protokollierenden Transitionen) und sonstigen Fehler während der Arbeit mit dieser Funktion des Verifikators auftraten, gibt es 6 Punkte. (BT2f) Vorhandene Verfahren zur Verbesserung des Geschwindigkeitsgrades Der Verifikator von UPPAAL bietet zahlreiche Funktionen zur Verbesserung der Veri- fikationsgeschwindigkeit. Direkten Einfluss auf die Geschwindigkeit der Verifikation hat jedoch nur die Search-Order-Option (Breadth First, Depth First). Der Rest beein- flusst lediglich die Zustandsraumverwaltung. 3,5 Punkte (BT3) Simulations- und Verifikationstechniken (BT3a) Erstellung und Eingabe der Spezifikation & Korrektheitskriterien Die Erstellung und Spezifikation von Systemen erfolgt in UPPAAL grafisch und tex- tuell. D.h. die Definition der Abläufe innerhalb eines Prozesses erfolgt mittels Transi- tionssystemen, die Steuerung und Synchronisation dagegen mit Hilfe einer Spezifika- tionssprache. Positiv ist die einfache Erstellung der Transitionssysteme durch einen grafischen Edi- tor, die klare Gliederung des Verifikators sowie die sehr übersichtliche und struktu- rierte Darstellung der Simulationsausführung. Negativ aufgefallen sind die folgenden Punkte: Die Skalierung der aktuellen Wertanzeige ist bei der Existenz von vielen Variab- len unmöglich. Abb.7-1: Skalierung zu visualisierender Variablen (Darstellungsfehler) Die Ausrichtung von definierten Aktionen an den Transitionskan- ten ist nicht unproblematisch, da diese immer in der Mitte der Verbindung zwischen den beiden Knoten der Kanten ausgerich- z:=3 tet werden, was bei großen Transitionssystemen zum Suchen der Aktionen führen kann. Kapitel 7 ­ Evaluation 62 Die Komponenten bzw. eine Gruppe von Komponenten kann nicht kopiert wer- den. Wurde ein Ansichtenwechsel durchgeführt, springt der Editor nicht an den ur- sprünglichen Bearbeitungspunkt zurück, was bei großen Systemen sehr hinder- lich sein kann. Bei Neugenerierung des Simulators werden alle View-Einstellungen verworfen. Einschränkung bei Bezeichnung der Knoten (z.B. sj<=si" nicht möglich) Fehler in großen Diagrammen sind schwer zu finden, da sie nur Rot unterstrichen werden. Syntax Checking - keine Arrayüberprüfung - keine Integerbegrenzungsüberprüfung (z.B. int[0,3] ... i=5) Veränderungen am Transitionssystem können nicht zurückgesetzt (Undo) wer- den. Daraus ergibt sich die folgende Punkteverteilung: Intelligente Editoren ­ 0 Punkte (nicht existent) Syntax-Checking ­ 3,5 Punkte Wizards ­ 0 Punkte (nicht existent) Visuelle Erstellung und Bearbeitung ­ 4 Punkte (BT3b) Visualisierung UPPAAL bietet lediglich eine Zoomfunktion (Simulator & grafischer Editor) und eine Snapfunktion für den grafischen Editor an. Die visuelle Konfiguration der V-Kompo- nenten ist nicht möglich. Daraus ergeben sich 3 Punkte für die individuelle Visualisierungsanpassung (Customization) und 0 Punkte für die visuelle Konfiguration der V- Komponenten. (BT4) Integrierte Bibliotheken UPPAAL besitzt keine integrierte Bibliothek, jedoch die Möglichkeit, definierte Templates und Korrektheitskriterien abzuspeichern und in anderen Systemen wieder zu verwenden. Dies ergibt die folgende Punktevergabe: Vorgefertigte Protokollspezifikationen bzw. Spezifikationsmodule ­ 1 Punkt (nur sehr wenige und einfache Beispiele im Web erhältlich) Erweiterbarkeit ­ 3 Punkte Suchoptionen und -kriterien ­ 0 Punkte (nicht vorhanden) Austauschbarkeit ­ 2 Punkte (Kompatibilität der Transitionssysteme) (BT5) Lizenz und Kosten UPPAAL ist frei verfügbar. Es fallen lediglich die Kosten für den Download an. Zu beachtende Lizenzen ­ ASF (The Apache Software License, Version 1.1) und W3C (W3C IPR SOFTWARE NOTICE) 5 Punkte (BT6) Plattformunabhängigkeit Da UPPAAL in Java programmiert wurde, ist eine sehr hohe Plattformunabhängigkeit gegeben. 6 Punkte Kapitel 7 ­ Evaluation 63 (BT7) Erlernbarkeit, Verständlichkeit Nach meiner Auffassung ist UPPAAL leicht verständlich und erlernbar, vorausge- setzt, man hat sich vorher mit Transitionssystemen beschäftigt. Etwas komplexer ist jedoch die Abbildung von Zeit sowie das Verständnis von urgent locations (der Ab- lauf von Zeit ist in diesen Lokationen bzw. Zuständen nicht möglich, d.h. ein Warten ist nicht möglich) bzw. committed locations (befindet sich der Simulator in einer commited location, dann ist die einzige nächste Transition immer, die diesem Zu- stand folgende. Ein commit state ist unverzüglich zu verlassen). Daher können hier nur 4,5 Punkte vergeben werden. (BT8) Dokumentation Die Dokumentation von UPPAAL ist etwas kurz gehalten. Es werden zwar alle benö- tigten Funktionen erklärt, doch es fehlen ausführliche Beispiele. Dabei kommt be- sonders das Zeitverständnis in UPPAAL zu kurz. 4,5 Punkte (BT9) Erweiterbarkeit 0 Punkte, da kein Source-Code verfügbar ist (BT10) Schnittstelle(n) (APIs) zu anderen Tools 0 Punkte (nicht vorhanden) (BT11) Stabilität/Technische Ausgereiftheit Bis auf kleinere Fehler innerhalb des Simulators (z.B. Fehler beim Laden einer ge- speicherten Simulationsausführung) sowie kontinuierlich steigendem Speicherplatz- bedarf während der Verifikation konnten keine Stabilitätsprobleme oder technische Unausgereiftheiten festgestellt werden. 4,5 Punkte (BT12) Verfügbarkeit Soweit mir bekannt ist, werden regelmäßig Updates und neue Versionen von UP- PAAL zur Verfügung gestellt. Der Download ist einfach und die benötigten zusätzli- chen Programme (in diesem Fall das JDK ab Version 1.3) sind problemlos und ohne größere Kosten verfügbar. Eine Registrierung ist nicht notwendig. Gegen Aufpreis zu erhaltene Zusatzfunktio- nen sind mir nicht bekannt. 6 Punkte (BT13) Verbreitung und Bekanntheitsgrad Die Bewertung der Verbreitung und des Bekanntheitsgrades ist etwas schwierig, da diese nur subjektiv, anhand von Internetrecherchen (Suche nach UPPAAL" ­ mit Google) beurteilt werden konnten. Aus diesem Grund ist das Kriterium mit etwas Vorsicht zu genießen. Das Ergebnis ist überraschend. Obwohl Spin" in der Literatur als das Beispiel für Verifikationstools gilt, ist es weniger häufig (2760 Treffer) im In- ternet zu finden als UPPAAL (4480 Treffer). Das mag verschiedene Gründe haben, z.B. das ein und dieselbe Seite mehrfach im Index der Suchmaschine ist. Aus die- sem Grund erhält UPPAAL eine recht hohe Punktzahl, welche jedoch genau aus dem o.g. Grund noch etwas nach unten korrigiert wird. 4,5 Punkte. Kapitel 7 ­ Evaluation 64 7.2.2 Spezifikationssprache (BS1) Definition von Korrektheitskriterien Mit Hilfe der Spezifikationssprache von UPPAAL konnten alle im Beispiel benötigten Korrektheitskriterien definiert werden. Die Erstellung solcher Kriterien ist sehr ein- fach. Einen kleinen Abzug gibt's für die teilweise etwas langen Definitionen, um ein- fache Konsistenzen zu überprüfen (z.B. ist das Ergebnis in einem Array gespeichert, muss jeder einzelne Index miteinander verglichen werden ­ p[] == q[] ist nicht mög- lich) 5 Punkte (BS2) Modularität Eine Modularisierung von Teilsystemen ist in UPPAAL nicht möglich, es sei denn, sie werden als eigenständiger Prozess modelliert. Das wiederum erfordert eine Syn- chronisation mit den anderen Prozessen des Systems. Aus diesem Grund können nur 1,5 Punkte vergeben werden. (BS3) Eignung für die Modellierung von Interaktionen zwischen Prozessen in VS Mit Hilfe von UPPAAL können Interaktionen zwischen Prozessen nur bedingt nach- gebildet werden. Positiv fällt dabei die Möglichkeit der Zeitmodellierung auf. Als ne- gativ sind die teilweise fehlenden Abstraktionsmöglichkeiten zu betrachten. So kann z.B. die Verwaltung von Warteschlangen nicht abstrahiert werden und muss voll- ständig modelliert werden, was das Systemmodell, wie man im Anhang B.1 sehen kann, unter Umständen verkompliziert und einschränkt. 3 Punkte (BS4) Vollständigkeit/Mächtigkeit. Da das zu modellierende System in UPPAAL nur teilweise über die integrierte Spezi- fikationssprache abgebildet wird, werden hier auch die Möglichkeiten und die Mäch- tigkeit von Transitionssystemen mit einbezogen. Wenn man von der Größe und Ü- bersichtlichkeit absieht, können mit Hilfe von Transitionssystemen und der hier vor- handenen Spezifikationssprachen alle nötigen Funktionen nachgebildet werden, je- doch auf Kosten der Komplexität und Übersichtlichkeit. Wie in den beiden vorange- gangenen Kriterien bereits beschrieben, besitzt die Spezifikationssprache einige Ein- schränkungen keine mehrdimensionalen und dynamischen Arrays, keine Zeiger, z.B. zur Definition von Listen, sehr eingeschränkte Modularisierung sowie lediglich die Datentypen int, chan und clock. 2,5 Punkte (BS5) Erlernbarkeit, Verständlichkeit Da die Mächtigkeit der Spezifikationssprache eingeschränkt ist, sollte die Einarbei- tung recht schnell und einfach möglich sein. Aufgrund der Transitionssysteme und vereinzelter Beispiele ist ein zügiges Verständnis für die Funktionsprinzipien des Tools gegeben. 4 Punkte Kapitel 7 ­ Evaluation 65 (BS6) Dokumentation Die Dokumentation der Spezifikationssprache beschränkt sich auf ein Minimum. E- xistierende Befehle bzw. Funktionen werden nur sehr kurz erläutert, die Syntax in BNF-Form dargestellt und nur wenige typische Beispiele angegeben. Obwohl die Dokumentation sehr kurz gehalten ist, ist sie zum Verständnis der Spezifikations- sprache ausreichend. Ich bin mir jedoch nicht sicher, ob ich alle Möglichkeiten der einzelnen Funktionen ausschöpfen konnte. 3,5 Punkte (BS7) Implementierbarkeit Zu diesem Punkt kann ich sagen, dass eine Implementierung, vorausgesetzt man kennt die Möglichkeiten der Spezifikationssprache, schnell und einfach von statten geht. 4,5 Punkte (es gibt einen Abzug von 1,5, aufgrund der sehr einfachen Struk- tur der Spezifikationssprache) (BS8) Verbreitung und Bekanntheitsgrad Da die Spezifikationssprache des Tools auch nur für dieses verwendet werden kann, entsprechen die Verbreitung und der Bekanntheitsgrad, dem des Tools. 4,5 Punkte (BS9) Abbildbarkeit in andere Sprachen Betrachtet man lediglich die Spezifikationssprache, also nicht die eigentliche Model- lierung des Prozessablaufs durch Transitionssystem, dann ist sie ohne großen Auf- wand in jede beliebige Sprache abbildbar. Der Grund hierfür sind die simplen Funkti- onen der Spezifikationssprache. 4,5 Punkte (es gibt einen Abzug von 1,5, aufgrund der sehr einfachen Struk- tur der Spezifikationssprache) (BS10) Überprüfbarkeit Aufgrund der einfachen Struktur der Spezifikationssprache ist sie sehr leicht lesbar und kann von Fachleuten ohne großen Zeitaufwand verstanden und überprüft wer- den. 5 Punkte (es gibt einen Abzug von 1,5, aufgrund der sehr einfachen Struktur der Spezifikationssprache und ein Plus von 0,5, aufgrund der guten Ver- ständlichkeit von definierten Korrektheitskriterien). (BS11) Lockerheit Auch bei diesem Kriterium kann die Spezifikationssprache selbst nicht betrachtet werden, da Nichtdeterminismus und Unvollständigkeiten im Prozessablauf durch das Transitionssystem definiert werden. Setzt man den Fokus jedoch auf das eben er- wähnte Transitionssystem zur Modellierung von nichtdeterministischen und evtl. un- vollständigen Systemen, kann man keine Einschränkungen erkennen. 4,5 Punkte (es gibt einen Abzug von 1,5, aufgrund der Abbildung durch Tran- sitionssysteme) 7.2.3 Lehre (BL1) Erlernbarkeit, Verständlichkeit UPPAAL ist sehr gut für den Einsatz in der Lehre geeignet, sofern keine allzu kom- plexen Systeme simuliert und verifiziert werden müssen. Eine schnelle Einarbeitung sowie eine gute Verständlichkeit sind gegeben ­ vorausgesetzt, der Anwender kann ein Grundwissen bezüglich Transitionssystemen und Model Checking vorweisen. Die Kapitel 7 ­ Evaluation 66 Darstellung der Resultate und die Durchführung von Simulationsläufen sind intuitiv und leicht nachvollziehbar. Wie bereits mehrmals erwähnt, wird das Gesamtbild lediglich durch die Einschrän- kungen der Spezifikationssprache und die Verifikationsgeschwindigkeit getrübt. Das ergibt ein gut", also 5 Punkte. (BL2) Dokumentation/Hilfen Die Dokumentationen und integrierten Hilfen von UPPAAL sind, falls dieses Verifika- tionstool in der Lehre verwendet wird, zu knapp. Es fehlen ausführlich dokumentierte Beispiele sowie präzise Definitionen bzw. Erklärungen der existierenden Funktionen. Lediglich ein paar simple Beispiele werden angeführt. 4 Punkte (BL3) Lernkurve Dieses Kriterium ist sehr schwierig zu beurteilen, da jeder Mensch Dinge auf seine eigene Art und Weise versteht und erlernt. Dem einen reicht die formale Definition eines Systems, um dessen Funktionsweise zu begreifen, der andere muss es an ei- nem Beispiel sehen. Nach meiner Auffassung ist UPPAAL ein wirklich gutes Tool, um einfache Kommunikationsprotokolle zu verstehen. Während der Modellierung eines Systems (Spezifikation), werden die ersten Erkenntnisse gesammelt ­ sehr einfache Modellierung mit Hilfe von Transitionssystemen und der recht einfachen Spezifkati- onssprache. Danach vervollständigt der Simulator das Gesamtbild, indem durch die schrittweise Ausführung, Zusammenhänge schnell verstanden werden können. Eine wichtige Rolle spielen dabei die Transitionssysteme, die die Ablaufstruktur des mo- dellierten Systems einfach und klar verständlich repräsentieren. W i Spezifikation s s Simulation e n Zeit Abb.7-2: Lernkurve (UPPAAL) 5 Punkte (BL4) Benutzerführung Die Benutzerführung des Tools ist einwandfrei. Die vorhandenen Funktionen sind klar gegliedert und schnell anwählbar. Einen kleinen Minuspunkt gibt es für die Er- stellung der Transitionssysteme, da hier keine Kopier- und Undo-Funktionalität zur Verfügung steht. 5 Punkte (BL5) Standardisierung Da dieses Tool auf Transitionssystemen, deren Definition als Quasi-Standard be- trachtet werden kann, und einer eigenen Spezifikationssprache basiert, kann nur ei- ne sehr subjektive Bewertung (auf der Basis der von Transitionssystemen sowie der Verbreitung und dem Bekanntheitsgrad von UPPAAL) getroffen werden. 5 Punkte Kapitel 7 ­ Evaluation 67 (BL6) Verbreitung und Bekanntheitsgrad In diesem Fall stimmt dieser Wert mit den Punkten des entsprechenden Kriteriums des Verifikationstools und der Spezifikationssprache überein. 4,5 Punkte (BL7) Verfügbarkeit Wie bereits in BT12 begründet, hat dieses Verifikationstool eine sehr gute Verfügbar- keit 6 Punkte (BL8) Schnittstellen (APIs) zu andern Tools 0 Punkte (nicht existent) 7.3 Spin 7.3.1 Verifikationstools (BT1) Simulator (BT1a) Simulationsmodi Der Simulator von Spin stellt, genau wie der von UPPAAL, alle gewünschten Modi zur Verfügung. Ferner hat der Anwender die Möglichkeit zu einem beliebigen Zeit- punkt den Simulationsmodus zu wechseln. Daraus ergeben sich 6 Punkte für jeden der drei Simulationsmodi und 6 Punk- te für die Wechselmöglichkeit der Simulationsmodi. (BT1b) Suspend- und Go-On-Modus Auch diese Möglichkeit wird vom Simulator unterstützt. So kann Beispielsweise ein zufälliger Simulationslauf unterbrochen und schrittweise fortgesetzt werden. 6 Punkte (BT1c) Syntax-Checking Ein Syntax-Checking durch den Simulator erfolgt vor (beim Kompilieren) und wäh- rend der Simulation. Hier wird z.B. das Überschreiten von Arraygrenzen überprüft. Positiv ist, dass der Simulationslauf beim Auftreten von Fehlern nicht unbedingt ab- gebrochen wird (werden z.B. Arraygrenzen überschritten, wird eine Fehlermeldung angezeigt, die Simulation jedoch fortgesetzt). Die angezeigten Fehlermeldungen sind verständlich und nachvollziehbar. 5 Punkte. (BT1d) Protokollierung Der Simulator ist in der Lage alle ausgeführten Schritte während einer Simulationsausführung zu protokollieren und abzuspeichern. Gespeicherte Traces können nicht in Spin geladen und wiederholt ausgeführt werden 3 Punkte. (BT1e) Undo-Funktionalität Diese Funktionalität wird vom Simulator nicht unterstützt. 0 Punkte. (BT2) Verifikation (BT2a) Grad der Überdeckung Eine 100ige Überdeckung wird durch die von Spin zur Verfügung gestellten Suchver- fahren (siehe Abschnitt A.2), auch in komplexeren Systemen, gewährleistet, wobei Kapitel 7 ­ Evaluation 68 jedoch der Speicherbedarf und die Verifikationsgeschwindigkeit im Verhältnis zum Nutzen, eine natürliche Grenze setzen. 6 Punkte (BT2b) Generierung von test cases Der Verifikator von Spin ist zu einer automatischen Generierung von test cases in der Lage. So können z.B. die Lebendigkeit von Sequenzen und Schleifen überprüft so- wie unerreichbare Codefragmente gefunden werden. Eine Skalierung der zu generie- renden test cases ist jedoch nur bedingt möglich. Aus diesem Grund gibt es nur" 5 Punkte. (BT2c) Simulationsausführung mit den generierten test cases als Eingabe Da die Generierung der test cases und die Verifikation im Rahmen einer Si- mulationsausführung durchgeführt wird, können hier ebenfalls 5 Punkte ver- geben werden. (BT2d) Verifikationsgeschwindigkeit Die Verifikationsgeschwindigkeit von Spin ist im Vergleich zu andern Tools sehr gut, könnte jedoch noch etwas schneller sein. 5,5 Punkte (BT2e) Erzeugung und Ausführung von Gegenbeispielen im Fehlerfall Eine durch die immer komplexer werdenden Systeme nahezu notwendige Funktion ist die Erzeugung von Gegenbeispielen bei Nichterfüllung einer Anforderung und de- ren Ausführung im Simulator. Diese Funktionalität wird von Spin zur Verfügung ge- stellt. Ferner kann ausgewählt werden, ob alle gefundenen Fehlerpfade gespeichert werden sollen oder ob nach dem ersten Auftreten eines Fehlers die Verifikation ab- gebrochen wird. Da keine ersichtlichen Informationsmängel (z.B. Fehlen von zu protokollierenden Transitionen) und sonstigen Fehler während der Arbeit mit dieser Funktion des Verifikators auftraten, gibt es 6 Punkte. (BT2f) Vorhandene Verfahren zur Verbesserung des Geschwindigkeitsgrades Der Verifikator von Spin bietet zahlreiche Funktionen zur Verbesserung der Verifika- tionsgeschwindigkeit. Der Anwender hat direkten Einfluss auf die verwendeten Such- verfahren sowie die Speicherverwaltung während der Verifikation und damit direkten Einfluss auf die Geschwindigkeit der Verifikation. 6 Punkte (BT3) Simulations- und Verifikationstechniken (BT3a) Erstellung und Eingabe der Spezifikation & Korrektheitskriterien Die Erstellung und Spezifikation von Systemen erfolgt in Spin in einem Text- Interface. Es existiert jedoch ein Frontend (XSpin), welches ein graphisches Interface zur Eingabe der Spezifikation und der Korrektheitskriterien zur Verfügung stellt. Posi- tiv sind die einfache Erstellung von Korrektheitskriterien und die anschließende Veri- fikation durch einen Wizard", die einfache und schnelle Konfiguration der Simulati- ons- und Verifikationsoptionen (XSpin) sowie aussagekräftige Fehlermeldungen Negativ aufgefallen sind die folgenden Punkte: ungenügende Skalierung der aktuellen Wertanzeige von Variablen (XSpin) Visualisierung der Simulationsausgabe und vor allem der aktuellen Variablenwer- te bremst die Simulationsausführung stark (XSpin). keine Filterung und Suche innerhalb der Simulationsausgabe möglich (XSpin) kein intelligenter Editor zur Eingabe der Spezifikation verfügbar Kapitel 7 ­ Evaluation 69 Syntax Checking - keine Arrayüberprüfung - keine Deklarationsüberprüfung (z.B. int a,b; ... a = b[_pid];) - keine Syntaxprüfung von Kommentaren (z.B. /* Warteschlange) kein Undo Daraus ergibt sich die folgende Punkteverteilung: Intelligente Editoren ­ 0 Punkte (nicht existent) Syntax-Checking ­ 3,5 Punkte Wizards ­ 3 Punkte Visuelle Erstellung und Bearbeitung ­ 3,5 Punkte (BT3b) Visualisierung Eine individuelle Visualisierungsanpassung ist nur bedingt möglich, d.h. der Benutzer kann zwar die anzuzeigenden Informationen (z.B. MSC [Hau97], lokale oder globale Variablenwerte) auswählen ­ eine Konfiguration der Komponenten selbst ­ ist jedoch nicht möglich. Daraus ergeben sich 4 Punkte für das Customization und 0 Punk- te für die visuelle Konfiguration der V-Komponenten. (BT4) Integrierte Bibliotheken Spin besitzt keine integrierte Bibliothek, bietet jedoch die Möglichkeit, definierte Spe- zifikationen und Korrektheitskriterien wieder zu verwenden, da diese mit Hilfe der integrierten Spezifikationssprache definiert und als Datei abgespeichert werden kön- nen. Ferner gibt es die Möglichkeit definierte Prozesse über #include in ein beste- hendes System einzubinden. Dies ergibt die folgende Punktevergabe: Vorgefertigte Protokollspezifikationen bzw. Spezifikationsmodule ­ 3,5 Punkte (zahlreiche Beispiele im Web erhältlich) Erweiterbarkeit ­ 4,5 Punkte Suchoptionen und -kriterien ­ 0 Punkte (nicht vorhanden) Austauschbarkeit ­ 2 Punkte (Spezifikationen der Systeme müssen kompatibel sein) (BT5) Lizenz und Kosten Spin ist frei verfügbar. Es fallen lediglich die Kosten für den Download an. Die Lizenz beschränkt die Verwendung jedoch auf Lehrzwecke. 4,5 Punkte (BT6) Plattformunabhängigkeit Spin ist in ANSI C programmiert und für die wichtigsten Plattformen (Unix, Linux, Windows) verfügbar. Man kann jedoch nicht von einer Plattformunabhängigkeit spre- chen. 4,5 Punkte (BT7) Erlernbarkeit, Verständlichkeit Meiner Meinung nach ist Spin im Gegensatz zu UPPAAL etwas schwerer zu verste- hen. Der Grund liegt jedoch im immensen Funktionsumfang des Tools, für dessen Verständnis einfach mehr Zeitaufwand einkalkuliert werden muss. Voraussetzung sind auch hier wieder Kenntnisse auf dem Gebiet des Model Checking. 4 Punkte (BT8) Dokumentation Die Dokumentation von Spin ist sehr ausführlich. Trotz zahlreicher Beispiele ist es jedoch nicht immer leicht, die Bedeutung der einzelnen Funktionen zu verstehen. 4,5 Punkte Kapitel 7 ­ Evaluation 70 (BT9) Erweiterbarkeit Da zumindest für Unix-Systeme der Source-Code zur Verfügung steht, ist eine Erwei- terung von Spin prinzipiell möglich. In den mitgelieferten Sourcen fehlt jedoch eine ausführliche Dokumentation ­ eine Beschreibung der in Spin verwendeten Algorith- men ist im Internet zu finden [OnLi08]. 3 Punkte (BT10) Schnittstelle(n) (APIs) zu anderen Tools 0 Punkte (nicht vorhanden) (BT11) Stabilität/Technische Ausgereiftheit Es konnten während der gesamten Arbeit mit Spin keine Instabilitäten oder techni- sche Unausgereiftheiten festgestellt (auch unter Linux) werden. Lediglich einige Ver- besserungen am graphischen Interface sind wünschenswert (übersichtlichere Aufbe- reitung der angezeigten Informationen während eines Simulationslaufes). 5 Punkte (BT12) Verfügbarkeit Die Verfügbarkeit dieses Verifikationstools ist als sehr hoch einzustufen. Regelmäßi- ge Updates sowie Verbesserungen des Tools sind selbstverständlich. Der Download der benötigten Software (Tcl/Tk, GNU C) ist ebenso unproblematisch. Eine Registrie- rung ist nicht notwendig. Gegen Aufpreis zu erhaltene Zusatzfunktionen sind mir nicht bekannt. 6 Punkte (BT13) Verbreitung und Bekanntheitsgrad Die Bewertung der Verbreitung und des Bekanntheitsgrades ist etwas schwierig, da diese nur subjektiv, anhand von Internetrecherchen (Suche nach Spin" ­ mit Google), beurteilt werden konnten. Aus diesem Grund ist das Kriterium mit etwas Vorsicht zu genießen. Spin wird in der Literatur als das Beispiel für Verifikationstools gehandelt, ist im Inter- net jedoch nicht so häufig anzutreffen ( nur" 2760 Treffer). Da Spin weltweit an vielen Universitäten eingesetzt wird, kann die Punktzahl noch etwas nach oben korrigiert werden. 5 Punkte. 7.3.2 Spezifikationssprache (BS1) Definition von Korrektheitskriterien Mit Hilfe der Spezifikationssprache von Spin und der unterstützten Temporalen Logik LTL können alle benötigten Korrektheitskriterien definiert werden. Die Erstellung ist sehr einfach. Mit Hilfe eines Konversationstools können in LTL definierte Korrekt- heitskriterien automatisch in eine für die Spezifikationssprache verständliche Form gebracht werden. Aufgrund der zusätzlichen Einarbeitung in LTL werden nur" 5,5 Punkte ver- geben. (BS2) Modularität Eine Modularisierung von Teilsystemen ist möglich ­ theoretisch kann jeder Prozess in einer eigenen Datei spezifiziert werden. Ferner sind die Definition von Makros und Prozeduren" (Variablen innerhalb einer Prozedur" sind global) möglich. 4,5 Punkte Kapitel 7 ­ Evaluation 71 (BS3) Eignung für die Modellierung von Interaktionen zwischen Prozessen in VS Mit Hilfe von Spin können Interaktionen zwischen Prozessen ohne weiteres darge- stellt werden. Einziger Nachteil ist der fehlende Zeitaspekt, d.h. Zeit kann durch die Spezifikationssprache nicht abgebildet werden. Genau wie in UPPAAL, sind die teil- weise fehlenden Abstraktionsmöglichkeiten zu berücksichtigen. So kann auch in Spin die Verwaltung von Warteschlangen nicht abstrahiert werden ­ dass hieß für die Imp- lementierung des Anwendungsbeispiels vollständige Modellierung der Prioritätslisten und der Operationswarteschlangen sowie der Operationslogbücher (siehe dazu An- hang B.2). 4 Punkte (BS4) Vollständigkeit/Mächtigkeit. Die Spezifikationssprache von Spin bietet vielfältige und vor allem einfache Möglich- keiten zur Modellierung von Systemen. Es können schnell und ohne großen Zeitauf- wand komplexere Kommunikationsprotokolle erstellt werden, ohne eine wichtige Funktion zu vermissen. Von großem Vorteil sind dabei die Funktionen if (if- statement), do (Schleifenfunktion), atomic (definiert eine Reihe untrennbarer Aktio- nen), never (Deklaration von Korrektheitskriterien) und typedef (Deklaration benut- zerdefinierter Datentypen) ­ siehe Anhang A.2. Aber auch in Spin fehlen benötigte Funktionen: - keine Pointer möglich, z.B. zur Definition von Listen - Lokale Variablen existieren nur innerhalb von Prozessen, nicht aber in Proze- duren - Mit #include geladene Dateien müssen mindestens einen Prozess beinhalten - Es existieren nur die Datentypen bit, byte, short, int und chan ­ String- oder Real-Typen wären sinnvoll die zu einer Einschränkung des zu modellierenden Systems führen. 4 Punkte (BS5) Erlernbarkeit, Verständlichkeit Da der Umfang und die Komplexität der Spezifikationssprache recht hoch, die Funk- tionen teilweise aus C bekannt sind und eine gute Dokumentation existiert, ist eine Einarbeitung schnell und einfach möglich. 4,5 Punkte (BS6) Dokumentation Die Dokumentation der Spezifikationssprache ist sehr ausführlich und versucht an- hand von Beispielen, die einzelnen Funktionen und ihre Besonderheiten zu be- schreiben. Sie ist klar gegliedert und baut logisch aufeinander auf. Einen kleinen Ab- zug gibt's jedoch für den Umfang ­ manche Beschreibungen wären einfacher zu ver- stehen, würden sie kurz und prägnant erläutert. 5 Punkte (BS7) Implementierbarkeit Hat man Erfahrungen mit anderen Programmiersprachen und kennt die Möglichkei- ten der Spezifikationssprache von Spin, dann ist eine schnelle und unkomplizierte Implementierung möglich. Einziges Handicap sind einige wenige irreführende Feh- lermeldungen des Syntax Checkers, da diese andere Ursachen, als die angegebe- nen, haben. 5 Punkte Kapitel 7 ­ Evaluation 72 (BS8) Verbreitung und Bekanntheitsgrad Die Verbreitung und der Bekanntheitsgrad der Spezifikationssprache profitiert auf der einen Seite vom Bekanntheitsgrad des Tools selbst und auf der anderen Seite von der Mächtigkeit dieser Sprache ­ Promela wird neben Spin auch von vielen anderen Verifikationstools benutzt (z.B. PEP). 6 Punkte (BS9) Abbildbarkeit in andere Sprachen Betrachtet man die Funktionen der Spezifikationssprache und die Ähnlichkeit der Syntax zu C, dann kann man sich vorstellen, dass sie in viele Sprachen (z.B. Java, C++, Delphi, Modula3) abgebildet werden kann. Einzige Voraussetzung ist, dass die Zielsprache die Funktionalität von Promela abbilden kann, also z.B. die Generierung von Prozessen ermöglicht. 5 Punkte (es gibt einen Abzug von 1 Punkt, aufgrund der recht komplexen Struktur der Spezifikationssprache, die durch die Zielsprache abgebildet werden muss) (BS10) Überprüfbarkeit Nach meiner Erfahrung kann Spin leicht von entsprechenden Fachleuten verstanden und überprüft werden. 4,5 Punkte (es gibt einen Abzug von 1,5, aufgrund der recht komplexen Struktur der Spezifikationssprache und der nicht immer einfach verständli- chen Definition von Korrektheitskriterien). (BS11) Lockerheit Die Spezifikationssprache von Spin unterstützt die Modellierung von Nichtdetermi- nismus und Unvollständigkeiten im Prozessablauf, sofern dadurch keine syntakti- schen Fehler innerhalb der Spezifikation auftreten ­ es konnten keine Einschränkun- gen erkannt werden. 6 Punkte 7.3.3 Lehre (BL1) Erlernbarkeit, Verständlichkeit Neben UPPAAL ist auch Spin gut für den Einsatz in der Lehre geeignet. Eine schnel- le Einarbeitung sowie eine gute Verständlichkeit sind gegeben, vorausgesetzt, der Anwender kann ein Grundwissen bezüglich Model Checking vorweisen. Die Darstel- lung der Resultate und die Durchführung von Simulationsläufen sowie der Verifikati- on sind intuitiv und leicht nachvollziehbar. 6 Punkte. (BL2) Dokumentation/Hilfen Die Dokumentationen und integrierten Hilfen von Spin sind gut und beinhalten ausführlich beschriebene Beispiele. So können auch ohne umfangreiche Kenntnisse schnell, einfache Systeme spezifiziert, simuliert und verifiziert werden. 5 Punkte (BL3) Lernkurve Dieses Kriterium ist sehr schwierig zu beurteilen, da jeder Mensch Dinge auf seine eigene Art und Weise versteht und erlernt. Dem Einen reicht die formale Definition eines Systems, um dessen Funktionsweise zu begreifen, der Andere muss es an einem Beispiel sehen. Nach meiner Meinung ist Spin gut geeignet, um auch komple- xere Kommunikationsprotokolle zu verstehen. Während der Modellierung eines Sys- Kapitel 7 ­ Evaluation 73 tems (Spezifikation), werden die ersten Erkenntnisse gesammelt ­ im Gegensatz zu UPPAAL werden detailliertere Kenntnisse über das System und die Spezifikations- sprache benötigt. Danach vervollständigt der Simulator das Gesamtbild, indem durch die schrittweise Ausführung, Zusammenhänge schnell verstanden werden können. Eine wichtige Rolle spielt dabei die Visualisierung der Prozessabläufe, die den Ablauf des modellierten Systems einfach und klar verständlich darstellen. W i s Spezifikation s e Simulation n Zeit Abb.7-3: Lernkurve (Spin) 5 Punkte (BL4) Benutzerführung Die Benutzerführung des Tools ist einwandfrei. Die vorhandenen Funktionen sind klar gegliedert und schnell anwählbar. Einen kleinen Minuspunkt gibt es für den Edi- tor zur Erstellung der Spezifikation (XSpin), da hier einige Funktionen (z.B. Syntax Highlighting, Bearbeitungspunkte) nicht zur Verfügung stehen. 5 Punkte (BL5) Standardisierung Wie aus der Verbreitung und dem Bekanntheitsgrad von Spin ersichtlich ist, wird das Tool an vielen Universitäten verwendet und die Spezifikationssprache von anderen Verifikationstools benutzt, d.h. man kann von einem Quasi-Standard des Tool spre- chen. 5 Punkte (BL6) Verbreitung und Bekanntheitsgrad Wie in BT13 bereits erläutert, wird Spin an vielen Universitäten der Welt zu Lehrzwe- cken eingesetzt. Aus diesem Grund, gibt es hier 6 Punkte. (BL7) Verfügbarkeit Wie bereits in BT12 begründet, hat dieses Verifikationstool eine sehr gute Verfügbar- keit. 6 Punkte (BL8) Schnittstellen (APIs) zu andern Tools 0 Punkte (nicht existent) Kapitel 7 ­ Evaluation 74 7.4 Verisoft 7.4.1 Verifikationstools (BT1) Simulator (BT1a) Simulationsmodi Es sind alle Simulationsmodi im Simulator von Verisoft verfügbar. Der gewünschte Simulationsmodus, wird vor dem Start der Simulation festgelegt. Besonders positiv fallen die Funktionen des Simulators während der schrittweisen Ausführung auf (ak- tueller Wert einer Variablen kann durch die Markierung dieser im Process View an- gezeigt werden; Debugger-Funktionen) Daraus ergeben sich 6 Punkte für jeden der Simulationsmodi und 4,5 Punkte für die Wechselmöglichkeit der Simulationsmodi. (BT1b) Suspend- und Go-On-Modus Nur die schrittweise (step-by-step, user-defined) Simulationsausführung kann unter- brochen und wieder fortgesetzt werden. 4,5 Punkte (BT1c) Syntax-Checking Das Syntax-Checking durch den Simulator erfolgt während der Simulation. Hier wird z.B. das Überschreiten von Arraygrenzen überprüft. Treten Fehler auf, wird die Simu- lation, im Gegensatz zu Spin, sofort unterbrochen. 4 Punkte. (BT1d) Protokollierung Der Simulator ist in der Lage, ausgeführte Schritte (nur die für den Scheduler von Verisoft sichtbaren Operationen ­ VS-Operationen, Abschnitt A.3) während einer Si- mulationsausführung zu protokollieren und abzuspeichern. Die gespeicherten Traces können wieder geladen und ausgeführt werden. Es ist jedoch nur eine schrittweise Ausführung möglich. 4,5 Punkte. (BT1e) Undo-Funktionalität Diese Funktionalität wird vom Simulator unterstützt. Innerhalb des Trace-Views kann zu den protokollierten Punkten gesprungen werden. Dabei traten jedoch Fehler (Pro- grammabstürze) auf. 4 Punkte. (BT2) Verifikation (BT2a) Grad der Überdeckung Eine 100ige Überdeckung des Anwendungsbeispiels (Grove-Algorithmus) wurde er- reicht. 6 Punkte (BT2b) Generierung von test cases Der Verifikator von Verisoft ist zu einer automatischen Generierung von test cases in der Lage. So können z.B. die Lebendigkeit von Sequenzen und Schleifen überprüft sowie unerreichbare Codefragmente gefunden werden. Eine Skalierung der zu gene- rierenden test cases ist jedoch nur bedingt möglich. Aus diesem Grund gibt es nur" 5 Punkte. Kapitel 7 ­ Evaluation 75 (BT2c) Simulationsausführung mit den generierten test cases als Eingabe Da die Generierung der test cases und die Verifikation im Rahmen einer Si- mulationsausführung durchgeführt wird, können hier ebenfalls 5 Punkte ver- geben werden. (BT2d) Verifikationsgeschwindigkeit Die Verifikationsgeschwindigkeit von Verisoft ist mir der von Spin vergleichbar. Deshalb gibt's die gleiche Punktzahl wie Spin: 5,5 Punkte. (BT2e) Erzeugung und Ausführung von Gegenbeispielen im Fehlerfall Eine durch die immer komplexer werdenden Systeme nahezu notwendige Funktion ist die Erzeugung von Gegenbeispielen bei Nichterfüllung einer Anforderung und de- ren Ausführung im Simulator. Diese Funktionalität wird von Verisoft zur Verfügung gestellt. Ferner kann ausgewählt werden, ob alle gefundenen Fehlerpfade gespei- chert werden sollen oder ob nach dem ersten Auftreten eines Fehlers die Verifikation abgebrochen wird. Da keine ersichtlichen Informationsmängel (z.B. Fehlen von zu protokollie- renden Transitionen) und sonstigen Fehler während der Arbeit mit dieser Funktion des Verifikators auftraten, gibt es 6 Punkte. (BT2f) Vorhandene Verfahren zur Verbesserung des Geschwindigkeitsgrades Der Verifikator von Verisoft bietet nur sehr wenige Funktionen zur Verbesserung der Verifikationsgeschwindigkeit. Der Anwender hat keinen direkten Einfluss auf die ver- wendeten Suchverfahren sowie die Speicherverwaltung während der Verifikation. Er kann lediglich den Suchraum des Verifikators einschränken und somit die Suche ver- kürzen. 2 Punkte (BT3) Simulations- und Verifikationstechniken (BT3a) Erstellung und Eingabe der Spezifikation & Korrektheitskriterien In Verisoft werden zu modellierende Systeme nicht durch eine eigene Spezifikati- onsprache abgebildet. Es stehen lediglich Funktionen zur Definition von Korrekt- heitskriterien und zur Abbildung von Nichtdeterminismus zur Verfügung. In der hier getesteten Version wurde das Anwendungsbeispiel komplett in C modelliert und mit Hilfe der von Verisoft zur Verfügung gestellten Funktion, Nichtdeterminismus und Korrektheitskriterien modelliert. Dies hat den Vorteil, dass sich der Benutzer einen beliebigen Editor (z.B. Emacs) zur Systemspezifikation auswählen kann. Lediglich der Simulator und der Verifikator sind feste Bestandteile von Verisoft. Um nun eine gerechte Bewertung treffen zu können, gehe ich von einem Editor aus, der zumindest die wichtigsten Funktionen, wie z.B. Syntax Highlighting und Syntax-Checking, besitzt. Daraus ergibt sich die folgende Punkteverteilung: Intelligente Editoren ­ 4 Punkte (nicht existent) Syntax-Checking ­ 4 Punkte Wizards ­ 4 Punkte Visuelle Erstellung und Bearbeitung ­ 4 Punkte (BT3b) Visualisierung Verisoft bietet lediglich eine Zoomfunktion an. Die visuelle Konfiguration der V- Komponenten ist nicht möglich. Daraus ergeben sich 2,5 Punkte für das Customization und 0 Punkte für die visuelle Konfiguration der V-Komponenten. Kapitel 7 ­ Evaluation 76 (BT4) Integrierte Bibliotheken Verisoft besitzt keine integrierte Bibliothek, bietet jedoch die Möglichkeit, definierte Spezifikationen und Korrektheitskriterien wieder zu verwenden ­ definierte Funktio- nen, Korrektheitskriterien und Teilprozesse können über #include in ein bestehendes System eingebunden werden. Dies ergibt die folgende Punktevergabe: Vorgefertigte Protokollspezifikationen bzw. Spezifikationsmodule ­ 1,5 Punkte (nur sehr wenige Beispiele im Web erhältlich) Erweiterbarkeit ­ 5 Punkte (da es im Web sehr viele Module, in vielen von Verisoft unterstützten Sprachen, gibt - z.B. für Listen) Suchoptionen und -kriterien ­ 0 Punkte (nicht vorhanden) Austauschbarkeit ­ 3,5 Punkte (Spezifikationen der Systeme müssen kompati- bel sein) (BT5) Lizenz und Kosten Verisoft ist frei verfügbar. Es fallen lediglich die Kosten für den Download an. Die Li- zenz beschränkt die Verwendung jedoch auf Lehrzwecke. 4,5 Punkte (BT6) Plattformunabhängigkeit Verisoft ist auf die Plattformen Sun Solaris und Linux beschränkt. Ein Grund dafür sind die benutzten Tools, welche teilweise nur für diese Betriebssysteme zur Verfü- gung stehen. Eine Plattformunabhängigkeit ist nicht gegeben. 1 Punkt (BT7) Erlernbarkeit, Verständlichkeit Die von Verisoft zur Verfügung gestellten Funktionen sind intuitiv und leicht verständ- lich. Voraussetzung sind jedoch Debugging-Kenntnisse. 4,5 Punkte (BT8) Dokumentation Die Dokumentation von Verisoft, zum Verständnis der grundlegenden Funktionen des Simulators und Verifikators, ist als gut einzustufen. Anhand eines Beispiels wer- den die wichtigsten von ihnen vorgestellt. Weiterführende Erklärungen zu einzelnen Funktionen des Simulators, sind in speziellen Kapiteln des Manuals zu finden. 5 Punkte (BT9) Erweiterbarkeit 0 Punkte, da kein Source-Code verfügbar ist. (BT10) Schnittstelle(n) (APIs) zu anderen Tools 0 Punkte (nicht vorhanden) (BT11) Stabilität/Technische Ausgereiftheit Bis auf einzelne Instabilitäten des Simulators (beim Zurücksetzen der Simulation an einen protokollierten Zustand) konnten keine Stabilitätsprobleme oder technische Unausgereiftheiten festgestellt werden. 4,5 Punkte (BT12) Verfügbarkeit Die Verfügbarkeit dieses Verifikationstools ist als hoch einzustufen. Regelmäßige Updates sowie Verbesserungen des Tools sind selbstverständlich. Der Download der benötigten Software (Expect, gdb) ist unproblematisch. Eine Registrierung ist not- Kapitel 7 ­ Evaluation 77 wendig. Gegen einen Aufpreis, sind zusätzliche Funktionen (z.B. zur Spezifikation von Client/Server-Protokollen) erhältlich. 4 Punkte (BT13) Verbreitung und Bekanntheitsgrad Die Bewertung der Verbreitung und des Bekanntheitsgrades ist etwas schwierig, da diese nur subjektiv, anhand von Internetrecherchen (Suche nach Verisoft" ­ mit Google), beurteilt werden konnten. Aus diesem Grund ist das Kriterium mit etwas Vorsicht zu genießen. Verisoft konnte bei der Internetsuche mit einer ähnlichen Trefferrate wie Spin aufwar- ten (2100 Treffer). Da Verisoft im Gegensatz zu Spin jedoch kaum bekannt ist, kann nur" ein ausreichend vergeben werden ­ 3 Punkte. 7.4.2 Spezifikationssprache (BS1) Definition von Korrektheitskriterien Mit Hilfe der Spezifikationssprache von Verisoft können Korrektheitskriterien nur in einem sehr begrenzten Rahmen definiert werden. Lediglich die vordefinierten" Krite- rien, wie z.B. Livelocks und Deadlocks sowie durch den Anwender definierte asserti- on violations können überprüft werden. Aufgrund dieser Einschränkung, können nur 2,5 Punkte vergeben werden. (BS2) Modularität Eine Modularisierung von Teilsystemen ist möglich ­ theoretisch kann jeder Prozess in einer eigenen Datei spezifiziert sowie Prozesse ineinander verschachtelt werden. Aufgrund der unterstützten Hochsprachen durch Verisoft, wie z.B. C/C++ und Java ist eine gute Modularisierung möglich 5,5 Punkte (BS3) Eignung für die Modellierung von Interaktionen zwischen Prozessen in VS Mit Hilfe von Verisoft können Interaktionen zwischen Prozessen ohne weiteres dar- gestellt werden. Genau wie in den beiden vorangegangenen Verifikationstools, sind fehlende Abstraktionsmöglichkeiten zu berücksichtigen. So werden zwar Funktion für einen bounded FIFO-Queue und Semaphore zur Verfügung gestellt, eine Synchroni- sation bleibt dem Anwender jedoch nicht erspart. Die Kommunikation zwischen Pro- zessen erfolgt über Kanäle ­ damit ist z.B. bei der Abbildung eines Konsistenzerhal- tungsprotokolls der gesamte Nachrichtenverkehr zwischen den einzelnen Prozessen zu implementieren. 3,5 Punkte (BS4) Vollständigkeit/Mächtigkeit. Bis auf die Einschränkungen bezüglich der Definition von Korrektheitskriterien, sind keine fehlenden Funktionen festzustellen. 4,5 Punkte (BS5) Erlernbarkeit, Verständlichkeit Voraussetzung für eine schnelle Einarbeitung sind Kenntnisse in der Programmie- rung von Kommunikationsprotokollen, da diese vollständig (Informationsaustausch und Synchronisation) implementiert werden müssen. Die Funktionen der Spezifikati- onssprache sind zwar intuitiv, jedoch ohne Grundkenntnisse schwer nachvollziehbar. Kapitel 7 ­ Evaluation 78 Aus diesem Grund ist ein wesentlich höherer Aufwand zum Verständnis, als z.B. bei Spin und UPPAAL notwendig. 3,5 Punkte (BS6) Dokumentation Die Dokumentation der Spezifikationssprache ist schlecht. Es existieren zwar Bei- spiele, die sind jedoch schlecht erklärt und beschränken sich auf sehr einfache Vor- gänge. Funktionen zur Abbildung der Prozesskommunikation sind unvollständig oder gar nicht erklärt. 2 Punkte (BS7) Implementierbarkeit Hat man Erfahrungen mit den von Verisoft unterstützten Programmiersprachen und kennt die Möglichkeiten der Spezifikationssprache, dann ist eine recht zügige Imple- mentierung möglich. Einziges Handicap sind wiederum der Nachrichtenaustausch sowie dessen Synchronisation. 4 Punkte (BS8) Verbreitung und Bekanntheitsgrad Die Verbreitung und der Bekanntheitsgrad der Spezifikationssprache sind be- schränkt. Betrachtet man jedoch die Sprachen, mit der das System eigentlich spezifi- ziert wird, so sind die Verbreitung und der Bekanntheitsgrad sehr hoch. Aus diesem Grund wird zur Bewertung dieses Kriteriums ein Mittelwert aus der Verbreitung und dem Bekanntheitsgrad der beiden Sprachen gebildet. Daraus ergeben sich 4,5 Punkte. (BS9) Abbildbarkeit in andere Sprachen Eine Abbildung der existierenden Funktionen der eigentlichen Spezifikationssprache (nicht der von Verisoft unterstützten Programmiersprachen) ist ohne weiteres mög- lich. 5 Punkte (BS10) Überprüfbarkeit Die Spezifikationen von Verisoft können von entsprechenden Fachleuten gut nach- vollzogen und überprüft werden 4,5 Punkte (es gibt einen Abzug von 1,5, da die Abstraktion eines Systems stark eingeschränkt wird und somit eine komplette Implementierung erfolgen muss ­> hoher Zeitaufwand zur Einarbeitung in das abgebildete System). (BS11) Lockerheit Die Spezifikationssprache von Verisoft unterstützt die Modellierung von Nichtdeter- minismus und Unvollständigkeiten im Prozessablauf, sofern dadurch keine syntakti- schen Fehler innerhalb der Spezifikation auftreten ­ es konnten keine Einschränkun- gen erkannt werden. 6 Punkte 7.4.3 Lehre (BL1) Erlernbarkeit, Verständlichkeit Verisoft ist nur bedingt für den Einsatz in der Lehre geeignet. Ein Grund dafür ist die nicht immer einfache Verständlichkeit der Funktionsweise, ein anderer die fehlende Abstraktionsmöglichkeit von unwichtigen" Abläufen (z.B. Warteschlangen). Positiv Kapitel 7 ­ Evaluation 79 aufgefallen sind dagegen der Simulator sowie die Visualisierung der Prozessabläufe. 3,5 Punkte. (BL2) Dokumentation/Hilfen Die Dokumentationen und integrierten Hilfen von Verisoft sind ausreichend. Anhand von einfachen Beispielen werden die grundlegenden Funktionen erklärt. Damit kön- nen jedoch nur sehr einfache System spezifiziert und verifiziert werden. 3,5 Punkte (BL3) Lernkurve Dieses Kriterium ist sehr schwierig zu beurteilen, da jeder Mensch Dinge auf seine eigene Art und Weise versteht und erlernt. Dem Einen reicht die formale Definition eines Systems, um dessen Funktionsweise zu begreifen, der Andere muss es an einem Beispiel sehen. Verisoft ist trotz der Notwendigkeit einer detaillierten Spezifi- kation des Systems gut geeignet, um Kommunikationsprotokolle zu verstehen. Wäh- rend der Modellierung werden detailliert Erkenntnisse über den Ablauf innerhalb ei- nes Prozesses gesammelt ­ zur Abbildung des zu simulierenden Systems sind be- reits sehr umfangreiche Kenntnisse über die Spezifikationssprache (z.B. C/C++) so- wie über die Vorgänge des Systems notwendig (evtl. erste Resignationserscheinun- gen). Danach vervollständigt der Simulator das Gesamtbild, indem durch die schritt- weise Ausführung, Zusammenhänge und Beziehungen zwischen den einzelnen Teil- systemen verdeutlicht werden. W i s Spezifikation s e Simulation n Zeit Abb.7-4: Lernkurve (Verisoft) 4 Punkte (BL4) Benutzerführung Die Benutzerführung des Tools ist einwandfrei. Die vorhandenen Funktionen sind klar gegliedert und schnell anwählbar. 5 Punkte (BL5) Standardisierung Da dieses Tool, genau wie UPPAAL, nur über eine sehr beschränkte Spezifikations- sprache (zur Abbildung von Nebenläufigkeiten und zur Definition von Korrektheitskri- terien) verfügt und die Modellierung der Systeme z.B. über C/C++ (ANSI/ISO- Standardisierung 1998) erfolgt, kann nur eine sehr subjektive Bewertung getroffen werden. 5 Punkte (BL6) Verbreitung und Bekanntheitsgrad Wie aus den Ausführungen von BT13 entnommen werden kann, sind der Bekannt- heitsgrad und die Verbreitung des Tools nicht sehr hoch. Aus diesem Grund macht der Einsatz diese Verifikationstools im Bereich der Lehre nur Sinn, falls der Fokus Kapitel 7 ­ Evaluation 80 nicht auf der Verifikation, sondern auf der Implementierung und dem Verständnis von Systemen (z.B. Kommunikationsprotokollen) liegt, da hier die Modellierung mit Hilfe von vorwiegend standardisierten Sprachen erfolgt. Aus diesem Grund, gibt es hier 3 Punkte. (BL7) Verfügbarkeit Wie bereits in BT12 begründet, besitzt dieses Verifikationstool nur eine befriedigende Verfügbarkeit. 3 Punkte (BL8) Schnittstellen (APIs) zu andern Tools 0 Punkte (nicht existent) 7.5 Ergebnisse Der folgende Abschnitt stellt die ermittelten Werte sowie die berechneten Gesamt- werte der einzelnen Kategorien tabellarisch dar und fasst die gewonnen Erkenntnis- se aus der Evaluation der Verifikationstools kurz zusammen. In einem separaten Abschnitt werden die Ergebnisse der Verifikation bezüglich des getesteten Algorithmusses dargestellt. 7.5.1 Verifikationstools Bewertungskriterien (Tools) Gewichtung in % subjektive Beurteilung UPPAAL Spin Verisoft BT1 20 38.5 38.0 39.5 BT1a 10 24.00 24.00 22.50 I 2.5 6.0 6.0 6.0 II 2.5 6.0 6.0 6.0 III 2.5 6.0 6.0 6.0 IV 2.5 6.0 6.0 4.5 BT1b 3 6.0 6.0 4.5 BT1c 2.5 0.0 5.0 4.0 BT1d 2.5 4.0 3.0 4.5 BT1e 2 4.5 0.0 4.0 BT2 16 18.5 33.5 29.5 BT2a 5.5 6.0 6.0 6.0 BT2b 4 0.0 5.0 5.0 BT2c 2.5 0.0 5.0 5.0 BT2d 2 3.0 5.5 5.5 BT2e 1 6.0 6.0 6.0 BT2f 1 3.5 6.0 2.0 BT3 14 ( ) 10.5 14 18.5 BT3a 10 7.5 10.0 16.0 I 4 0.0 0.0 4.0 II 3.5 3.5 3.5 4.0 Kapitel 7 ­ Evaluation 81 Bewertungskriterien (Tools) Gewichtung in % subjektive Beurteilung UPPAAL Spin Verisoft III 1.5 0.0 3.0 4.0 IV 1 4.0 3.5 4.0 BT3b 4 3.0 4.0 2.5 I 2 3.0 4.0 2.5 II 2 0.0 0.0 0.0 BT4 10 6 10 10 BT4a 3.5 1.0 3.5 1.5 BT4b 3 3.0 4.5 0.0 BT4c 2 0.0 0.0 5.0 BT4d 1.5 2.0 2.0 3.5 BT5 8.5 5.0 4.5 4.5 BT6 6.5 6.0 4.5 1.0 BT7 5.5 4.5 4.0 4.5 BT8 5 4.5 4.5 5.0 BT9 4 0.0 3.0 0.0 BT10 3.5 ( ) 0.0 0.0 0.0 BT11 3 4.5 5.0 4.5 BT12 2.5 6.0 6.0 4.0 BT13 1.5 4.5 5.0 3.0 2.50 3.76 3.36 Tab.7-2: Bewertungsergebnisse (Verifikationstools) Bewertungskriterien (Sprachen) Gewichtung in % subjektive Beurteilung UPPAAL Spin Verisoft BS1 20 5.0 5.5 2.5 BS2 15 1.5 4.5 5.5 BS3 13 3.0 4.0 3.5 BS4 12.5 2.5 4.0 4.5 BS5 10 4.0 4.5 3.5 BS6 8.5 3.5 5.0 2.0 BS7 6.5 4.5 5.0 4.0 BS8 6 4.5 6.0 4.5 BS9 4.5 4.5 5.0 5.0 BS10 3 5.0 4.5 4.5 BS11 1 4.5 6.0 6.0 3.47 4.75 3.72 Tab.7-3: Bewertungsergebnis (Spezifikationssprachen) Kapitel 7 ­ Evaluation 82 Bewertungskriterien (Lehre) Gewichtung in % subjektive Beurteilung UPPAAL Spin Verisoft BL1 25 5.0 6.0 3.5 BL2 18 4.0 5.0 3.5 BL3 15 5.0 5.0 4.0 BL4 12 5.0 5.0 5.0 BL5 10.5 5.0 5.0 5.0 BL6 8 4.5 6.0 3.0 BL7 7.5 6.0 6.0 3.0 BL8 4 ( ) 0.0 0.0 0.0 4.46 4.99 3.52 Tab.7-4: Bewertungsergebnis (Lehre) Aus der obigen Tabelle ist ersichtlich, dass jedes der getesteten Tools seine Stärken und Schwächen besitzt. So hat Verisoft den besten Simulator, kann in punkto Verifi- kator mit Spin jedoch nicht mithalten. UPPAAL schneidet am schlechtesten ab. Hier liegt der Grund in der schlechten Verifikationsgeschwindigkeit sowie der nicht vor- handenen test case ­ Generierung. In Bezug auf Bibliotheken und vordefinierten Pro- tokollspezifikationen kann keines der getesteten Werkzeuge wirklich überzeugen. In der 2. Kategorie (Spezifikationssprachen) konnte Spin erneut überzeugen. Die Stärken liegen vor allem in der Definition von Korrektheitskriterien sowie der vorhan- den Funktionsvielfalt, um die Eigenschaften konkurrierender Systeme zu modellie- ren. Obwohl UPPAAL die geringste Bewertung in dieser Kategorie erhielt, besticht dieses Tool durch eine gute Lesbarkeit definierter Systeme und gewährleistet eine einfache und schnelle Modellierung. Verisoft kann durch die Unterstützung von Hochsprachen (C/C++) zur Spezifikation von Systemen mit der besten Modularität aufwarten. In der dritten und letzten Kategorie kristallisierten sich 2 Tools heraus. Beide über- zeugen sie durch eine einfache Bedienung und einer kurzen Einarbeitungszeit. Die Lernkurven aller Tools sind ähnlich. Im Gegensatz zu UPPAAL und Spin müssen bei Verisoft bereits zur der Modellierung eines Systems detaillierte Kenntnisse über die Kommunikation zwischen Prozessen vorliegen, da diese nicht abstrahiert werden können. Die insgesamt beste Bewertung erhielt Spin. Es konnte in allen Kategorien überzeu- gen. Trotz einiger Schwächen hat es das Potential, sich zu einem der Referenzpro- dukte auf dem Gebiet der Verifikationstools zu entwickeln. Kapitel 7 ­ Evaluation 83 7.5.2 Grove-Algorithmus Wie bereits im Abschnitt 5.3 erwähnt, dient der Grove-Algorithmus zur Konsistenzer- haltung bei einer parallelen Bearbeitung von gleichen Dokumentenbereichen, d.h. die Replikate des Dokumentes müssen im Ruhezustand auf allen Teilnehmersystemen konsistent (gleich) sein. Mit Hilfe der drei getesteten Verifikationstools, konnte die in [BoSc95] bewiesene Korrektheit des Grove-Algorithmus nicht nachgewiesen werden. Bereits bei mehr als 2 generierten Operationen pro TS, konnten Inkonsistenzen festgestellt werden. Das folgende Beispiel zeigt das Resultat einer Verifikation des Algorithmusses durch Spin. Es wurden 3 Teilnehmer simuliert, die zufällig 2 Operationen (insert oder delete) aus- führen. Als Korrektheitskriterium wurde definiert: /* Prozesse sind im Ruhezustand inkosistent -> FEHLER !!! * * Formula As Typed: [] (cond_1 -> ([] cond_2)) * The Never Claim Below Corresponds * To The Negated Formula !([] (cond_1 -> ([] cond_2))) * (formalizing violations of the original) */ never T0_init: if :: (! ((cond_2)) && (cond_1)) -> goto accept_all :: ((cond_1)) -> goto T0_S4 :: (1) -> goto T0_init fi; T0_S4: if :: (! ((cond_2))) -> goto accept_all :: (1) -> goto T0_S4 fi; accept_all: printf("Result (0): %d\n", finishedRes[0]); printf("Result (1): %d\n", finishedRes[1]); printf("Result (2): %d\n", finishedRes[2]); } mit: cond_1 = true, falls alle TS im Ruhezustand cond_2 = true, falls Dokumente" konsistent Die Tabelle 7-5 zeigt die Ergebnisse der Verifikation. Die drei Spalten P0 bis P2 rep- räsentieren die einzelnen Teilnehmer. Zusätzlich wird jeweils der aktuelle Zustands- vektor si (rot) sowie die Warteschlange (blau) und das Logbuch (schwarz) in der Form (i, s, o, p) angegeben. Die Operation selbst besteht aus drei Komponenten (x, y, z), wobei x für die Art der Operation (0 = Insert, 1 = Delete), y für das einzufügen- de Zeichen (y : 0 und A[ ] verwendbar und ID.ID steht für process name.location name". BNF-Grammatik für die Definition von Korrektheitsanfoderung in UPPAAL: Prop ::= A[] SP | E<> SP | E[] SP | A<> SP | SP --> SP SP ::= AP | not SP | ( SP ) | SP or SP | SP and SP | SP imply SP | deadlock AP ::= ID.ID | CGuard | IGuard CGuard ::= ID REL NAT | ID REL ID | ID REL ID + NAT | ID REL ID - NAT IGuard ::= IExpr REL IExpr | IExpr != IExpr IExpr ::= ID | ID[IExpr] | NAT | -IExpr | (IExpr) | IExpr OP IExpr REL ::= < | <= | >= | > | == OP ::= + | - | * | / Beispiele: A[](1<2) ­ es gilt immer, 1<2. E<>(p1.cs and p2.cs) ­ true, wenn das System einen Punkt erreichen kann, wo die Prozesse p1 und p2 im Zustand cs sind. A[](p1.cs imply not p2.cs) ­ es gilt immer, wenn der Prozess p1 im Zustand cs ist, dann ist p2 nicht im Zustand cs. A[] not deadlock ­ das System ist Deadlockfrei P1.req --> P1.wait ­ wann immer der Prozess P1 die kritische Region betreten will, kann er eventuell in den Wait-Zustand gelangen. Spezifikationssprache Der folgende Abschnitt gibt einen Überblick über die wichtigsten Methoden bzw. Funktionen der in UPPAAL implementierten Spezifikationssprache. Die Beschrei- bung der einzelnen Methoden bzw. Funktionen erfolgt wie bei den Korrektheitskrite- rien in einer BNF-Grammatik. Identifiers Ein gültiger Identifier ist in UPPAAL durch den folgenden regulären Ausdruck defi- niert: [a-zA-Z]([a-zA-Z0-9_])*. Beispiel: a, B, c2, d2 ­ gültige Identifiernamen 1, 2a, 3B, 4c5 - ungültige Identifiernamen Anhang A 93 Declarations Deklarationen sind entweder lokal oder global (in Bezug auf einen Prozess) und kön- nen globale Uhren, (bounded) Integers, Konstanten und Channels beinhalten. Declarations ::= (Decl ';')* Decl ::= 'int' VIL | 'int' '[' CExpr ',' CExpr ']' VIL | 'clock' IL | 'chan' IL | 'urgent' 'chan' IL | 'const' ID CExpr CExpr ::= NAT | ID | '(' CExpr ')' | CExpr OP CExpr | '-' CExpr OP ::= '+' | '-' | '*' | '/' IL ::= ID (',' ID)* VIL ::= VID (',' VID)* VID ::= ID | ID := CExpr | ID '[' CExpr ']' (ID in CExpr muss eine definierte Konstante sein) Beispiele: const a 1; - Konstante a mit dem Wert 1 int[0,1] b[8], c[4]; - zwei boolean Arrays b und c, mit 8 und 4 Elementen int[0,100] a:=5; - eine Integervariable mit dem Bereich 0,...,100; initialisiert mit 5 clock x, y; - 2 Uhren x und y Guards GList ::= [Guard (',' Guard)*] Guard ::= CGuard | IGuard CGuard ::= ID REL CExpr | ID REL ID | ID REL ID + CExpr IGuard ::= IExpr REL IExpr | IExpr != IExpr REL ::= '<' | '<=' | '>=' | '>' | '==' IExpr ::= ID | ID'['IExpr']' | NAT | '-' IExpr | '(' IExpr ')' | IExpr OP IExpr | '(' IGuard '?' IExpr ':' IExpr ')' Beispiele: x>=1, x<=2 ­ 1<=x<=2 (i[0]+1)!=(i[1]*10) ­ ein Integer-Guard Synchronisations Synchronisationen sind syntaktisch sehr simpel. Sie sind von der Form a'?' (Empfän- gerseite) oder a'!' (Senderseite), wobei a der Name eines Channels ist. Assignments AList ::= [Assign (',' Assign)*] Assign ::= IAssign | CAssign CAssign ::= ID := CExpr IAssign ::= ID := IExpr (ID's in IExpr können Integerwerte oder Konstanten, aber keine Clocks sein) Beispiele: x := 0 - clock (or integer variable) x wird zurückgesetzt j := (i[1]>i[2] ? i[1] : i[2]) - j hat den Wert von i[1], falls i[1]>i[2], andernfalls hat j den Wert von i[2]. Template Parameters Param ::= [TDecl (';' TDecl)*] TDecl ::= int TIL | int '[' CExpr ',' CExpr ']' TIL | clock IL | chan IL | urgent chan IL | const IL TIL ::= TID (',' TID)* Anhang A 94 TID ::= ID | ID '[' CExpr ']' (die Parameterliste endet nicht mit ";") Beispiele: p(clock x; int[0,1] bit) ­ das Prozesstemplate p hat 2 Parameter: die Uhr x und die Booleanva- riable bit. Process Assigments Process assignments werden zur Deklaration von Instanzen von Prozesstemplates verwendet. PAList ::= (ID ':=' ID '(' [Values] ')' ';')* Values ::= (ID | CExpr) (',' (ID | CExpr))* Beispiele: P:=Q(); - der Prozess P ist eine Instanz des Templates Q, welches keine Parameter besitzt S:=R(x, 1); - der Prozess S ist eine Instanz des Templates R, welches zwei Parameter besitzt System Definition Eine Systemdefinition ist eine Liste von Prozess-Identifiern Sys ::= 'system' ID (',' ID)* ';' (ID muss ein Prozess-Identifier oder ein Template ohne Parameter sein) Beispiel: system P, Q; - ein System, bestehend aus den Prozessen P und Q A.2 SPIN In diesem Kapitel werden die Funktionen behandelt, die das Frontend zu Spin, XSpin 3.4.7, zur Verfügung stellt, d.h. Kommandozeilenparameter werden nicht erläutert (siehe dazu [OnLi08]) Funktionen des Simulators Display Mode MSC Panel ­ erzeugt ein MSC für eine "geführte" oder zufällige Simulationsaus- führung. Ferner sind die Optionen Step Number Labels oder Source Text Labels sowie Normal Spacing oder Condensed Spacing auswählbar. Time Sequence Panel ­ zeigt ein Time-Sequence-Diagramm an, mit den Op- tionen One Window per Process, One Trace per Process bzw. Interleaved Steps. Data Values Panel ­ zeigt die aktuellen Werte der definierten Variablen an. Die Skalierung der angezeigten Variablen erfolgt durch die Optionen Track Buffered Channels, Track Global Variables, Track Local Variables, Display vars marked ´show´ in MSC Execution Bar Panel ­ zeigt ein Säulendiagram, welches die Anzahl der Ausfüh- rungen jedes einzelnen Prozesses darstellt. Simulation Style Random ­ startet eine zufällige Simulationsausführung, bei der die Auswahl der nächsten Transition (falls mehrere aktiviert werden können) zufällig ermittelt wird. Guided ­ startet eine Simulation, bei der ein bereits ausgeführter Simulationslauf wiederholt wird. Diese Methode der Simulation wird z.B. verwendet, um bei der Verifikation gefundene Fehler, deren Tracepfad in pan.trail ­ files gespeichert Anhang A 95 wird, nachzuvollziehen. Zusätzlich kann angegeben werden, wie viele Schritte je- weils zu überspringen sind. Interactive - startet eine interaktive Simulationsausführung, d.h. die Auswahl der nächsten Transition (falls mehrere aktiviert werden können) wird vom Benutzer durchgeführt. Simulation Output Single Step ­ führt die nächste mögliche Transition aus Run ­ automatischer Simulationslauf, der falls die Spezifikation nicht terminiert, mit Hilfe von "Suspend" abgebrochen werden kann Suspend ­ bricht einen automatischen Simulationsdurchlauf ab Cancel ­ beendet den Simulator und setzt alle Werte zurück Funktionen des Verifikators Correctness Properties Mit Hilfe dieser Optionen kann man die zu überprüfenden Korrektheitseigenschaften definieren. Dazu gehört u.a. die Lebendigkeit (Liveness), benutzerdefinierte Korrekt- heitsanforderungen (never ­ Claim) und unerreichbarer Code. Search Mode In Spin können drei verschiedene Such-Modi ausgewählt werden. Dies sind Ex- haustive (vollständige Überdeckung), Supertrace/Bitstate und Hash-Compact. Im Gegensatz zu Exhaustive, sind Supertrace/Bitstate und Hash-Compact sogenannte Bit-State-Hashingverfahren, bei denen nicht gewährleistet wird, dass jeder theore- tisch erreichbare Zustand auch erzeugt wird, d.h. der Erreichbarkeitsgraph kann in Teilen beschnitten sein. Nähre Informationen zu diesen Algorithmen, sind in [Mey01] zu finden. Advanced Verification Options Physical Memory Available ­ physikalischer Speicher des Computers, auf dem Spin ausgeführt wird Estimated State Space Size ­ wird verwendet, um die Größe des Zustandsrau- mes (z.B. der Hash-Table) zu berechnen. Maximum Search Depth ­ definiert die Größe des Stacks für die Depth-First- Suche Verify an LTL Property Über diese Option kann ein in LTL definiertes Korrektheitskriterium automatisch in einen Never-Claim konvertiert und die Verifikation durchgeführt werden. Never-Claim dient zur Definition von Korrektheitskriterien SYNTAX never {sequence} Beispiel never {/* ![]p = <>!p*/ do :: skip :: !p -> break od } Anhang A 96 Spezifikationssprache (Promela) Promela Grammatik spec : module [ module ] * module : proctype /* proctype declaration */ | init /* init process */ | never /* never claim */ | trace /* event trace, 3.0 only*/ | utype /* user defined types */ | mtype /* mtype declaration */ | decl_lst /* global vars, chans */ proctype: [ active ] PROCTYPE name '(' [ decl_lst ]')' [ priority ] [ enabler ] '{' sequence '}' init : INIT [ priority ] '{' sequence '}' never : NEVER '{' sequence '}' trace : TRACE '{' sequence '}' utype : TYPEDEF name '{' decl_lst '}' mtype : MTYPE [ '=' ] '{' name [ ',' name ] * '}' decl_lst: one_decl [ ';' one_decl ] * one_decl: [ visible ] typename ivar [',' ivar ] * typename: BIT | BOOL | BYTE | SHORT | INT | MTYPE | CHAN | uname /* user defined type names (see utype) */ active : ACTIVE [ '[' const ']' ] /* instantiation */ priority: PRIORITY const /* simulation priority */ enabler : PROVIDED '(' expr ')' /* execution constraint */ visible : HIDDEN | SHOW sequence: step [ ';' step ] * step : stmnt [ UNLESS stmnt ] | decl_lst | XR varref [',' varref ] * | XS varref [',' varref ] * ivar : name [ '[' const ']' ] [ '=' any_expr | '=' ch_init ] ch_init : '[' const ']' OF '{' typename [ ',' typename ] * '}' varref : name [ '[' any_expr ']' ] [ '.' varref ] send : varref '!' send_args /* normal fifo send */ | varref '!' '!' send_args /* sorted send */ receive : varref '?' recv_args /* normal receive */ | varref '?' '?' recv_args /* random receive */ | varref '?' '<' recv_args '>' /* poll with side-effect */ | varref '?' '?' '<' recv_args '>' /* ditto */ poll : varref '?' '[' recv_args ']' /* poll without side-effect */ | varref '?' '?' '[' recv_args ']' /* ditto */ send_args: arg_lst | any_expr '(' arg_lst ')' arg_lst : any_expr [ ',' any_expr ] * recv_args: recv_arg [ ',' recv_arg ] * | recv_arg '(' recv_args ')' recv_arg : varref | EVAL '(' varref ')' | [ '-' ] const assign : varref '=' any_expr /* standard assignment */ | varref '+' '+' /* increment */ | varref '-' '-' /* decrement */ stmnt : IF options FI /* selection */ | DO options OD /* iteration */ | ATOMIC '{' sequence '}' /* atomic sequence */ | D_STEP '{' sequence '}' /* deterministic atomic */ | '{' sequence '}' /* normal sequence */ | send | receive | assign | ELSE /* used inside options */ | BREAK /* used inside iterations */ | GOTO name | name ':' stmnt /* labeled statement */ | PRINT '(' string [ ',' arg_lst ] ')' | ASSERT expr | expr /* condition */ options : ':' ':' sequence [ ':' ':' sequence ] * andor : '&' '&' | '|' '|' binarop : '+' | '-' | '*' | '/' | '%' | '&' | '^' | '|' Anhang A 97 | '>' | '<' | '>' '=' | '<' '=' | '=' '=' | '!' '=' | '<' '<' | '>' '>' | andor unarop : '~' | '-' | '!' any_expr: '(' any_expr ')' | any_expr binarop any_expr | unarop any_expr | '(' any_expr '-' '>' any_expr ':' any_expr ')' | LEN '(' varref ')' /* nr of messages in chan */ | poll | varref | const | TIMEOUT | NP_ /* non-progress system state */ | ENABLED '(' any_expr ')' /* refers to a pid */ | PC_VALUE '(' any_expr ')' /* refers to a pid */ | name '[' any_expr ']' '@' name /* refers to a pid */ | RUN name '(' [ arg_lst ] ')' [ priority ] expr : any_expr | '(' expr ')' | expr andor expr | chanpoll '(' varref ')' /* may not be negated */ chanpoll: FULL | EMPTY | NFULL | NEMPTY string : '"' [ any_ascii_char ] * '"' uname : name name : alpha [ alpha | number ] * const : TRUE | FALSE | SKIP | number [ number ] * alpha : 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z' | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z' | '_' number : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' Wichtige Funktionen und Methoden Macros Präprozessor-Anweisungen Syntax: #define name token-string #define name(arg, ..., arg) token-string #ifdef name #ifndef name #if constant-expression #else #endif #undef name #include "filename" Beispiel: #define EQUAL 0 #define SMALLER 1 #define BIGGER 2 typedef dient zur Definition eines benutzerdefinierten Datentyps Syntax: typedef name{ decl_lst} Beispiel: typedef elemQueue { byte i; byte s[APR]; byte o[OP]; byte p[APRIO]; } inline Prozedurmechanismus Syntax: inline name( [ arg_lst] ) { sequence} Anhang A 98 Beispiel: inline comparePrio (compPi, compPj, compResult) {...} if - Konstrukt Auswahlanweisung Syntax: if :: sequence[ :: sequence]* fi Beispiel: if :: (a != b) -> ... :: (a == b) -> ... fi printf dient zur Textausgabe während der Simulation Syntax: printf( string [ , arg_lst] ) Beispiel: printf ("5+3 = %d", 8); do - Schleife Wiederholungsanweisung Syntax: do :: sequence[ :: sequence]* od Beispiel: do :: count = count + 1 :: count = count - 1 :: (count == 0) -> break od skip ist ein Meta-Term, der von Spin in die Boolean-Konstante 1, also true, übersetzt wird Beispiel: if :: i<2 -> z=z*z; :: else -> skip; fi; break steht innerhalb einer Wiederholungsanweisung und bewirkt die Beendigung, d.h. den Sprung hinter die Kontrollstruktur _pid von Promela definierte Variable (read-only), welche die Prozessinstanziierungs- nummer enthält proctype dient zur Definition eines Prozessverhaltens Syntax: proctype name ( [ decl_lst ] ) { sequence } Beispiel: proctype A(mtype x) { byte state; state = x } active definiert ein Präfix für proctype-Deklarationen, zur Instanziierung von Initial- Prozessen Syntax: active proctype name ( [ decl_lst ] ) { sequence } active '[' const ']' proctype name ( [ decl_lst ] ) { sequence } Beispiel: active [4] proctype B() { ... } (kreiert 4 Prozesse des proctype's B) Anhang A 99 atomic startet eine Sequenz von Anweisungen, die unteilbar ausgeführt werden (paralle- le Ausführung von Anweisungen eines anderen Prozesses wird ausgeschlossen) Syntax: atomic {sequence} label dient zur Identifizierung eines eindeutigen Kontrollzustandes in einer proctype- Deklaration. Syntax: name : stmnt Beispiel: active proctype example() { S1: if :: i>2 -> goto S2 :: else -> goto S3 fi; S2: ... S3: ... } A.3 Verisoft Funktionen des Simulators Trace View Load/Save ­ Laden/Speichern eines Szenarios in bzw. von einem ".path" file Reset ­ setzt das gesamte System in den Startzustand zurück Next Event ­ setzt die Ausführung der Simulation bis zum Erreichen der nächsten sichtbaren Operation fort Move ­ setzt die Simulation in den gewünschten Zustand zurück Go To End ­ springt an das Ende des aktuellen Szenarios Quit ­ beendet den Simulator Process View Step ­ führt die nächste Anweisung des Prozesses aus (springt in Funktionsauf- rufe) Next ­ führt die nächste Anweisung des Prozesses aus (überspringt Funktions- aufrufe) Continue ­ setzt die Ausführung des Prozesses bis zum Erreichen der nächsten sichtbaren Operation fort Print ­ gibt den Wert einer markierten Variable aus Quit ­ beendet VeriSoft Simulationsmodi verisoft .c -simul startet Verisoft im manuellen Simulationsmodus verisoft .c startet Verisoft im automatischen Simulationsmodus verisoft .c -simul .path startet Verisoft im "geführten" Simulationsmodus Anhang A 100 Funktionen des Verifikators In Verisoft existiert kein eigentlicher Verifikator. Stattdessen werden benutzerdefinier- te (z.B. mit Hilfe von VS_assert) und vordefinierte" (z.B. Deadlocks, Livelocks) Kor- rektheitskriterien während der Simulationsausführung überprüft. Spezifikationssprache Search Parameters depth_incr ­ Tiefe einer Suchebene bei der Breadth-First - Suche divergence_limit ­ max. Verzögerung (in Sekunden) bevor eine Divergenz ge- meldet wird ignore_deadlock ­ wenn 1, Deadlocks werden nicht gemeldet livelock_limit ­ max. Anzahl der aufeinander folgenden Transitionen in den ein Prozess blockiert sein kann, ohne einen Livelock zu haben max_depth ­ maximale Suchtiefe max_sss ­ max. Größe des sss.VS in MByte nproc ­ exakte Anzahl der Prozesse im System random_seed ­ setzt einen beliebigen int-Wert, um den zufälligen Suchmodus" zu initialisieren save_state_space ­ wenn 1, Zustandsraum wir im sss.VS gespeichert stop_at_error ­ Anzahl der Fehler (ausgenommen Divergenzen), bis die Suche abgebrochen wird stop_at_state ­ max. Anzahl der Zustände, die untersucht werden sollen FIFO Queue is_queue_empty ­ wenn 1, der Queue ist leer is_queue_full ­ wenn 1, der Queue ist voll rcv_from_queue ­ Message vom Queue empfangen send_to_queue - Message an Queue senden Semaphore semsignal ­ "sendet" ein Signal (beim Verlassen einer kritischen Region) semwait ­ "wartet" auf ein Signal (beim Betreten einer kritischen Region) sonstige Operationen fork ­ erzeugt einen Prozess VS_abort ­ falls das angegebene Argument falsch (0 bzw. false) wird, unterbleibt die Untersuchung des Folgezustandes. VS_assert ­ meldet eine assertion violation, falls das angegebene Argument falsch (0 bzw. false) wird. VS_print ­ gibt einen einzeiligen (nicht "\n") String (z.B. einen Kommentar) im Tra- ce View des Verisoft-Simulators aus. VS_toss ­ wird verwendet, um Nichtdeterminismus zu simulieren Anhang B 101 Anhang B MM B O OD DE ELLLLIIE ER RU UN NG G D DE ES S G GRRO OV VE E--A ALLG GO OR RIITTH HM MU US S Dieses Kapitel beschreibt, wie der Grove-Algorithmus durch die drei getesteten Veri- fikationstools UPPAAL, Spin und Verisoft abgebildet werden konnte und welche Kompromisse bei der Modellierung eingegangen werden mussten. B.1 UPPAAL Bei der Abbildung des Grove-Algorithmus mit Hilfe von UPPAAL, mussten die größ- ten Einschränkungen gemacht werden. So wurde die Anzahl der Teilnehmer auf 3 beschränkt und jedem Prozess genau eine zu erzeugende Operation (insert [Xi; i]) zugeordnet. Dadurch konnte die Übersicht bewahrt und die Größe des Transitions- systems stark verringert werden, was sich positiv auf die Verifikationszeit auswirkte. Systemdefinition Prozessdefinition Zur Realisierung des Grove-Algorithmus wurden 6 Prozesse benötigt, einen für jeden Teilnehmer, einen für die Generierung der Operation und einen (pro Teilnehmer) zum Senden der erzeugten Operation. system P1, P2, P3, genInput, S1, S2, S3; Prozessinitialisierung Die Modellierung der Prozesse zum Senden und des eigentlichen Teilnehmersys- tems wurde nur einmal durchgeführt, da Instanzen erzeugt werden konnten. Jede Instanz des modellierten Prozesses wurde mit einer eindeutigen Id versehen, um eine spätere Identifikation des Teilnehmersystems zu ermöglichen (z.B. member(1) und sendOperation(1) sind Prozesse des Teilnehmers 1) P1:=member(1); P2:=member(2); P3:=member(3); S1:=sendOperation(1); S2:=sendOperation(2); S3:=sendOperation(3); Variablen Weiterhin wurden die folgenden Variablen wurden definiert global // Channels chan input, receive, sendOp; // Zeicheneingabe des Users (UPPAAL "nur" Integer) // char [x,y] -> [Zeichen, Position] int char[2]; // Rechner, auf dem Zeichen eingegeben wurde (Verwendung einer Id - z.B. 1 für TS A) int comp; // 1 = Operation des Teilnehmers x (0-2) bereits erzeugt und an TS gesendet int[0,1] wasSend[3]; // 1 = Zeichen bereits von einem Rechner empfangen int[0,2] wasRec[6]; // globaler Empfangsqueue - 10 pro Prozess int sendedOp[30]; // SenderId int [0,3] senderId; Anhang B 102 member // 1 = Operation wurde von Member generiert int [0,1] wasInput; int s_tmp[3]; int[0,2] flag; int[0,3] compFlag; int [1,2] index; // Textfeld int[0,3] txt_res[3]; // speichert Id der empfangenen Messages int[0,3] recMessage; // Operations-Anforderung int i; //TS-Identifikation int s[3]; //Zustandsvektor s int o[2]; //Operation [x,y] -> [Zeichen, Position] int p[4]; //Priorität der Operation o; [Prio1, Prio2, Prio3, Anzahl der gültigen Prios] // Operations-Warteschlange Qi int iQ_1, iQ_2, iQ_3, iQ; //TS-Identifikation int sQ_1[3], sQ_2[3], sQ_3[3], sQ[3]; //Zustandsvektor s int oQ_1[2], oQ_2[2], oQ_3[2], oQ[2]; //Operation [x,y] -> [Zeichen, Position] int pQ_1[4], pQ_2[4], pQ_3[4], pQ[4]; //Priorität der Operation o; [Prio1, Prio2, Prio3, Anzahl der gültigen Prios] int[0,1] full_Q[3]; // Operations-Logbuch Li int iL_1, iL_2, iL_3, iL; //TS-Identifikation int sL_1[3], sL_2[3], sL_3[3], sL[3]; //Zustandsvektor s int oL_1[2], oL_2[2], oL_3[2], oL[2]; //Operation [x,y] -> [Zeichen, Position] int pL_1[4], pL_2[4], pL_3[4], pL[4]; //Priorität der Operation o; [Prio1, Prio2, Prio3, Anzahl der gültigen Prios] int[0,1] full_L[3]; Prioritätsberechnung Abb.B-1: Prioritätsberechnung (Prozess ­ member) Anhang B 103 Realisierung von Warteschlange und Logbuch Abb.B-2: Warteschlange Qi (Prozess ­ member) Abb.B-3: Operationslogbuch Li (Prozess ­ member) Anhang B 104 Operationsgenerierung Abb.B-4: Operationsgenerierung (Prozess ­ genInput) Abb.B-5: Operationsgenerierung (Prozess ­ member) Operationspropagierung bzw. -sendung Abb.B-6: Operationspropagierung bzw. -sendung (Prozess ­ sendOperation) Anhang B 105 Abb.B-7: Operationspropagierung bzw. -sendung (Prozess ­ member) Operationsempfang Abb.B-8: Operationsempfang (Prozess ­ member) Operationstransformation und -ausführung Abb.B-9: Operationstransformation (Prozess ­ member) Anhang B 106 Abb.B-10: Operationsausführung (Prozess ­ member) Definition der Korrektheitskriterien Zur Überprüfung der Korrektheit des Grove-Algorithmus und der Modellierung wur- den die folgenden Korrektheitskriterien formuliert: a) Ist das System deadlock-free ? A[] not deadlock b) Diese Anfrage sollte ein konsistentes Resultat finden E<> (P1.finished and P2.finished and P3.finished and P1.txt_res[0]==P2.txt_res[0] and P1.txt_res[0]==P3.txt_res[0] and P2.txt_res[0]==P3.txt_res[0] and P1.txt_res[1]==P2.txt_res[1] and P1.txt_res[1]==P3.txt_res[1] and P2.txt_res[1]==P3.txt_res[1] and P1.txt_res[2]==P2.txt_res[2] and P1.txt_res[2]==P3.txt_res[2] and P2.txt_res[2]==P3.txt_res[2]) c) Alle Ereignisse wurden verarbeitet. Der Grove-Algorithmus ist im Ruhezustand. (Die Konsistenz der Ergebnisse wird nicht überprüft) HINWEIS: Bei (Depth First, Agressive, DBM, Reuse State Space, Clock Reducti- on, Diagnostic Trace) wird innerhalb weniger Sekunden ein konsistentes Ergebnis gefunden) E<> (P1.finished and P2.finished and P3.finished) d) Hier sollte eine Inkonsistenz der Resultate gefunden werden. E<> ((P1.finished and P2.finished and P3.finished) and (P1.txt_res[0]!=P2.txt_res[0] or P1.txt_res[0]!=P3.txt_res[0] or P2.txt_res[0]!=P3.txt_res[0] or P1.txt_res[1]!=P2.txt_res[1] or P1.txt_res[1]!=P3.txt_res[1] or P2.txt_res[1]!=P3.txt_res[1] or P1.txt_res[2]!=P2.txt_res[2] or P1.txt_res[2]!=P3.txt_res[2] or P2.txt_res[2]!=P3.txt_res[2])) e) Kann der Status not_reachable erreicht werden? (Sollte aufgrund der Einschrän- kungen nicht möglich sein) E<> (P1.not_reachable) f) Können alle drei Speicherelemente der Warteschlange belegt werden? (Sollte aufgrund der Einschränkungen nicht möglich sein) E<> (P1.full_Q[0]==1 and P1.full_Q[1]==1 and P1.full_Q[2]==1) g) Kann etwas in der Warteschlange gespeichert werden? E<> (P1.full_Q[0]==1) B.2 SPIN Bei der Abbildung des Grove-Algorithmus mit Hilfe von SPIN bzw. Promela, mussten, genau wie in UPPAAL, Einschränkungen gemacht werden, um die Größe und Über- sichtlichkeit der Spezifikation zu gewährleisten. Die Anzahl der Teilnehmer wurde auf 2 bis max.-3 beschränkt. Jeder Prozess kann eine beliebige Anzahl von Operationen (insert [Xi; i], delete [ i], mit i : 0 i 9) erzeugen. Anhang B 107 Systemdefinition Prozessdefinition Im Gegensatz zu UPPAAL wurde zur Realisierung des Grove-Algorithmusses in Spin nur" jeweils 1 Prozess pro Teilnehmer benötigt, d.h. insgesamt zwei bzw. drei Pro- zesse. Prozessinitialisierung Die Modellierung der Prozesse wurde auch hier nur einmal durchgeführt, da Instan- zen erzeugt werden konnten. Jede Instanz des modellierten Prozesses wurde mit einer eindeutigen Id (mit Hilfe von _pid") versehen, um eine spätere Identifikation des Teilnehmersystems zu ermöglichen. active [APR_HELP] proctype MemberProc () Variablen Weiterhin wurden die folgenden Variablen definiert global #define APR_HELP 2 /* Anzahl der Prozesse - dient zum beschränken auf 2 Prozesse */ #define AREC_HELP 1 /* max. Anzahl empfangener Anforderungen (APR_HELP-1)*AOP */ #define AOP 1 /* max. Anzahl der möglichen Operationen */ #define AREC 2 /* max. Anzahl empfangener Anforderungen (APR-1)*AOP */ #define APRIO 4 /* Priorität besteht aus max. N Komponenten (APR*AOP)+1 */ #define AELEM 3 /* max. Anzahl der Elemente in Qi und Li (APR*AOP) */ #define APR 3 /* Anzahl der Prozesse (NICHT verändern)*/ #define OP 3 /* Operation besteht aus N Komponenten (NICHT verändern)*/ #define INSERT 0 /* Operation INSERT (x,y) */ #define DELETE 1 /* Operation DELETE (x,y) */ #define NULL 2 /* keine Operation ausführen */ #define EQUAL 0 #define SMALLER 1 #define BIGGER 2 #define INPROGRESS 0 #define FINISHED 1 #define cond_1 ((finishedFlag[0] == FINISHED) && (finishedFlag[1] == FINISHED)) #define cond_2 (finishedRes[0] == finishedRes[1]) /* Typdefinition - Anforderung */ typedef elemQueue { byte i; byte s[APR]; byte o[OP]; byte p[APRIO]; } /* Empfangspuffer der Prozesse */ typedef memQueue { elemQueue Queue[AREC]; } /* empfangene Requests der Prozesse */ memQueue recQueue[APR]; /* Anzahl der Anforderungen im RequestsQueue */ byte anzElemQueue[APR]; int finishedRes[APR_HELP]; byte finishedFlag[APR_HELP]; memberProc elemQueue Li[AELEM]; /* Logbuch */ elemQueue Qi[AELEM]; /* Warteschlange */ byte anzElemLi; /* Anzahl der Elemente in Li */ byte anzElemQi; /* Anzahl der Elemente in Qi */ byte index; /* Index der aktuellen Operation in Qi */ byte s[APR]; /* Zustandsvektor des Prozesses */ byte i; /* Hilfsvariable */ byte resultSiSj; /* ResultFlag beim Vergleich von Zustandsvektoren */ byte textArray[APRIO]; /* Enthält die "Zeichenkette" */ byte anzRecRequests; /* Anzahl der empfangenen Anforderungen */ Anhang B 108 byte anzGenRequests; /* Anzahl der generierte Anforderungen */ Vergleich der Zustandsvektoren /* Vergleich von Si und Sj -> compSi - Zustandsvektor Si -> compSj - Zustandsvektor Sj -> return EQUAL (Si == Sj) SMALLER (Si < Sj) BIGGER (Si > Sj) */ inline compSiSj (compSi, compSj, resultFlag) { short counter; bit compFlag; compFlag = 0; counter = 0; /* Si = Sj */ if :: (compSi[0] == compSj[0]) -> counter++; :: else -> skip; fi; if :: (compSi[1] == compSj[1]) -> counter++; :: else -> skip; fi; if :: (compSi[2] == compSj[2]) -> counter++; :: else -> skip; fi; if :: (counter < 3) -> { /* (Si < Sj) oder (Si > Sj) */ counter = 0; if :: (compSi[0] < compSj[0]) -> counter++; :: (compSi[0] > compSj[0]) -> compFlag = 1; :: else -> skip; fi; if :: (compSi[1] < compSj[1]) -> counter++; :: (compSi[1] > compSj[1]) -> compFlag = 1; :: else -> skip; fi; if :: (compSi[2] < compSj[2]) -> counter++; :: (compSi[2] > compSj[2]) -> compFlag = 1; :: else -> skip; fi; if /* Si > Sj */ :: ((counter == 0) || (compFlag == 1)) -> resultFlag = BIGGER; /* Si < Sj */ :: ((counter > 0) && (compFlag == 0)) -> resultFlag = SMALLER; fi; } /* Si = Sj */ :: else -> resultFlag = EQUAL; fi; } Prioritätsberechnung und -vergleich Prioritätsberechnung /* berechnen der Priorität -> LiRef - "Referenz" auf das Logbuch -> QiRef - "Referenz" auf die Warteschlange -> anzLi - Anzahl der Elemente im Logbuch */ inline calcPrio (LiRef, QiRef, anzLi) { byte j; byte flag; byte calcDummy[APRIO]; byte calcFlag; j = 0; do /* Li enthält Elemente */ Anhang B 109 :: (j { compSiSj (LiRef[j].s, QiRef.s, flag); if /* Li enthält Element mit gleicher Position (si == sj) */ :: (flag == EQUAL) -> { /* hat Li höhere Priorität als ein bereits gefundenes */ comparePrio(LiRef[j].p, calcDummy, calcFlag); if :: (calcFlag == BIGGER) -> setPrio(LiRef[j].p, calcDummy); :: else -> skip; fi; j++; } /* Li[j] enthält kein Element mit gleicher Position (Si != Sj) */ :: else -> j++; fi; } /* (j >= anzLi) || Li enthält keine Elemente */ :: else -> { calcDummy[0] = 0; break; } od; setPrio (calcDummy, QiRef.p); QiRef.p[0]++; QiRef.p[QiRef.p[0]] = _pid; } Prioritätsvergleich /* Vergleich von Pi und Pj -> compPi - Prioritätenvektor Si -> compPj - Zustandsvektor Sj -> return SMALLER (Pi < Pj) BIGGER (Pi > Pj) */ inline comparePrio (compPi, compPj, compResult) { int k; int compCount; compCount = 0; k = 0; if /* #Komponenten in Pi = #Komponenten in Pj */ :: (compPi[0] == compPj[0]) -> { /* Prioritäten vergleichen */ do :: (k < compPj[0]) -> { k++; if :: (compPi[k] > compPj[k]) -> break; :: (compPi[k] == compPj[k]) -> compCount++; :: else -> compCount--; fi; } :: else -> break; od; if /* restliche Komponenten sind gleich */ :: (compCount == (k-1)) -> compResult = BIGGER; /* mindestens ein Komponente von Pi ist kleiner */ :: else -> compResult = SMALLER; fi; } /* #Komponenten in Pi > #Komponenten in Pj */ :: (compPi[0] > compPj[0]) -> { k = compPj[0]; /* Prioritäten vergleichen */ do :: (k > 0) -> { if :: (compPi[k] == compPj[k]) -> compCount++; :: else -> skip; fi; k--; } :: else -> break; od; if :: (compCount == compPj[0]) -> compResult = BIGGER; Anhang B 110 :: else -> compResult = SMALLER; fi; } :: else -> compResult = SMALLER; fi; } Realisierung von Warteschlange und Logbuch Die Warteschlange und das Operationslogbuch sind Arrays vom Typ typedef elemQueue { byte i; byte s[APR]; byte o[OP]; byte p[APRIO]; } Bedeutung: Hat ein CSCW-System z.B. 2 Teilnehmer und kann pro Teilnehmer ge- nau eine Operation erzeugen, dann können in Li bzw. Qi max. 2 Operationsanforde- rungen stehen, womit Qi durch elemQueue Qi[2] und Li durch elemQueue Li[2] zu definieren ist. Operationsgenerierung /* generiert eine neue Operation -> anzChar - Anzahl der "Zeichen", die schon generiert wurden -> operation - "Zeiger" auf die Position in Qi, in der die Operation gespeichert werden soll */ inline genInput (anzChar, operation) { byte p; /* ermitteln der Operation INSERT v DELETE */ if :: (anzChar == 0) -> operation[0]=INSERT; :: else -> { if :: skip -> operation[0] = INSERT; :: skip -> operation[0] = DELETE; fi; } fi; /*******************************************/ /* ermitteln des einzufügenden Zeichens */ if :: skip -> operation[1] = 0; :: skip -> operation[1] = 1; :: skip -> operation[1] = 2; :: skip -> operation[1] = 3; :: skip -> operation[1] = 4; :: skip -> operation[1] = 5; :: skip -> operation[1] = 6; :: skip -> operation[1] = 7; :: skip -> operation[1] = 8; :: skip -> operation[1] = 9; fi; /****************************************/ /* ermitteln der Lösch- bzw. Einfügeposition */ p = 1; do :: (p <= anzChar) -> if :: skip -> p++; :: skip -> { if :: (p > 1) -> p--; :: else skip; fi; } :: skip -> break; fi; :: else -> break; od; if Anhang B 111 ::((operation[0] == DELETE) && (p > anzChar)) -> operation[2] = anzChar; :: else -> operation[2] = p; fi; /*********************************************/ } Operationspropagierung bzw. -sendung Kommunikationsmechanismus Die Kommunikation der Prozesse bzw. der TS erfolgt über gemeinsame Variablen, welche durch /* Empfangspuffer der Prozesse */ typedef memQueue { elemQueue Queue[AREC]; } /* empfangene Requests der Prozesse */ memQueue recQueue[APR]; definiert sind. Senden der erzeugten Operationsanforderungen an alle andern Teilnehmer atomic { ... /* propagiere Request an alle TS */ i = 0; do :: (i if :: (i!=_pid) -> { recQueue[i].Queue[(anzElemQueue[i])].i = Qi[index].i; recQueue[i].Queue[(anzElemQueue[i])].s[0] = Qi[index].s[0]; recQueue[i].Queue[(anzElemQueue[i])].s[1] = Qi[index].s[1]; recQueue[i].Queue[(anzElemQueue[i])].s[2] = Qi[index].s[2]; recQueue[i].Queue[(anzElemQueue[i])].o[0] = Qi[index].o[0]; recQueue[i].Queue[(anzElemQueue[i])].o[1] = Qi[index].o[1]; recQueue[i].Queue[(anzElemQueue[i])].o[2] = Qi[index].o[2]; setPrio(Qi[index].p, recQueue[i].Queue[(anzElemQueue[i])].p); anzElemQueue[i]++; i++; }; :: else -> i++; fi; :: else -> break; od; } /*********************************/ Operationsempfang atomic { /* Empfangen und Speichern einer Anforderung in Qi*/ anzElemQi++; anzRecRequests++; anzElemQueue[_pid]--; Qi[index].i = recQueue[_pid].Queue[(anzElemQueue[_pid])].i; Qi[index].s[0] = recQueue[_pid].Queue[(anzElemQueue[_pid])].s[0]; Qi[index].s[1] = recQueue[_pid].Queue[(anzElemQueue[_pid])].s[1]; Qi[index].s[2] = recQueue[_pid].Queue[(anzElemQueue[_pid])].s[2]; Qi[index].o[0] = recQueue[_pid].Queue[(anzElemQueue[_pid])].o[0]; Qi[index].o[1] = recQueue[_pid].Queue[(anzElemQueue[_pid])].o[1]; Qi[index].o[2] = recQueue[_pid].Queue[(anzElemQueue[_pid])].o[2]; setPrio(recQueue[_pid].Queue[(anzElemQueue[_pid])].p, Qi[index].p); /**************************************************/ printf("incoming Request (%d): %d %d %d\n", _pid, Qi[index].o[0], Qi[index].o[1], Qi[index].o[2]); /* Entfernen der Anforderung aus der Empfangsliste */ recQueue[_pid].Queue[(anzElemQueue[_pid])].i = 0; recQueue[_pid].Queue[(anzElemQueue[_pid])].s[0] = 0; recQueue[_pid].Queue[(anzElemQueue[_pid])].s[1] = 0; recQueue[_pid].Queue[(anzElemQueue[_pid])].s[2] = 0; Anhang B 112 recQueue[_pid].Queue[(anzElemQueue[_pid])].o[0] = 0; recQueue[_pid].Queue[(anzElemQueue[_pid])].o[1] = 0; recQueue[_pid].Queue[(anzElemQueue[_pid])].o[2] = 0; recQueue[_pid].Queue[(anzElemQueue[_pid])].p[0] = 0; /***************************************************/ index++; } Operationstransformation und -ausführung Operationstransformation /* führt die Operationstransformation durch transQi - zu transformierende Operation transLi - jüngster Eintrag in Li mit Sk<= Sj */ inline transformOp (transQi, transLi) { byte transFlag; if /* k-te Komponente von Sj <= k-te Komponente von Sk */ :: (Qi.s[transLi.i] <= transLi.s[transLi.i]) -> { if :: ((transQi.o[0] == INSERT) && (transLi.o[0] == INSERT)) -> { if /* 0i<0k */ :: (transQi.o[2] < transLi.o[2]) -> skip; /* 0i>0k */ :: (transQi.o[2] > transLi.o[2]) -> transQi.o[2]++; /* 0i=0k & Xi=Xk */ :: ((transQi.o[2] == transLi.o[2]) && (transQi.o[1] == transLi.o[1])) -> transQi.o[0] = NULL; /* 0i=0k & Xi<>Xk */ :: ((transQi.o[2] == transLi.o[2]) && (transQi.o[1] != transLi.o[1])) -> comparePrio (transQi.p, transLi.p, transFlag); if :: (transFlag == BIGGER) -> transQi.o[2]++; :: (transFlag == SMALLER) -> skip; fi; fi; } :: ((transQi.o[0] == INSERT) && (transLi.o[0] == DELETE)) -> { if /* 0i<0k */ :: (transQi.o[2] < transLi.o[2]) -> skip; :: else -> transQi.o[2]--; fi; } :: ((transQi.o[0] == DELETE) && (transLi.o[0] == INSERT)) -> { if /* 0i<0k */ :: (transQi.o[2] < transLi.o[2]) -> skip; :: else -> transQi.o[2]++; fi; } :: ((transQi.o[0] == DELETE) && (transLi.o[0] == DELETE)) -> { if /* 0i<0k */ :: (transQi.o[2] < transLi.o[2]) -> skip; /* 0i>0k */ :: (transQi.o[2] > transLi.o[2]) -> transQi.o[2]--; :: else -> transQi.o[0] = NULL; fi; } fi; } :: else -> skip; fi; } Operationsausführung /* ausführen einer Anforderung opQi - Warteschlange opIndex - Index auf die Anforderung in Qi opTextArray - Textfeld in dem die Operation auszuführen ist */ inline executeOp (opQi, opIndex, opTextArray) { if :: (opQi[opIndex].o[0] == INSERT) -> Anhang B 113 insert (opQi[opIndex].o[1], opQi[opIndex].o[2], opTextArray); :: (opQi[opIndex].o[0] == DELETE) -> delete (opQi[opIndex].o[2], opTextArray); :: (opQi[opIndex].o[0] == NULL) -> skip; fi; } Ruhezustand Der Ruhezustand eines Teilnehmersystems wird erreicht, wenn alle Operationen er- zeugt und ausgeführt sowie alle Operationen der anderen Teilnehmersysteme emp- fangen und ausgeführt wurden. /* Ruhezustand erreicht ? */ if :: ((anzRecRequests < AREC_HELP) || (anzGenRequests < AOP) || (anzElemQi>0)) -> goto startAlgorithm; :: else -> skip; /* Ruhezustand erreicht */ fi; Definition der Korrektheitskriterien Zur Überprüfung der Korrektheit des Grove-Algorithmus wurden die folgenden bei- den Korrektheitskriterien formuliert: a) Sind die Resultate der Teilnehmersysteme im Ruhzustand inkonsistent? /* Prozesse sind im Ruhezustand inkosistent -> FEHLER !!! * * Formula As Typed (LTL): [] (cond_1 -> ([] cond_2)) * The Never Claim Below Corresponds * To The Negated Formula (LTL) !([] (cond_1 -> ([] cond_2))) * (formalizing violations of the original) */ never { /* !([] (cond_1 -> ([] cond_2)))" */ T0_init: if :: (! ((cond_2)) && (cond_1)) -> goto accept_all :: ((cond_1)) -> goto T0_S4 :: (1) -> goto T0_init fi; T0_S4: if :: (! ((cond_2))) -> goto accept_all :: (1) -> goto T0_S4 fi; accept_all: printf("Result (0): %d\n", finishedRes[0]); printf("Result (1): %d\n", finishedRes[1]); } b) Existiert eine Ausführung, bei der die Resultate der TS im Ruhezustand konsi- stent sind? /* Prozesse sind im Ruhezustand konsistent - KORREKT !!! * * Formula As Typed (LTL): [] (cond_1 -> (! cond_2)) * The Never Claim Below Corresponds * To The Negated Formula (LTL) !([] (cond_1 -> (! cond_2))) * (formalizing violations of the original) */ never { T0_init: if :: ((cond_1) && (cond_2)) -> goto accept_all :: (1) -> goto T0_init fi; accept_all: printf("Result (0): %d\n", finishedRes[0]); printf("Result (1): %d\n", finishedRes[1]); printf("Result (2): %d\n", finishedRes[2]); } Anhang B 114 B.3 Verisoft Bei der Abbildung des Grove-Algorithmus mit Hilfe von Verisoft bzw. C, mussten im Gegensatz zu UPPAAL und Spin, keine Kompromisse eingegangen werden. Die An- zahl der Teilnehmer und deren Operationen (insert [Xi; i], delete [ i], mit i : 0 i 9) kann durch die Verwendung von symbolischen Konstanten beliebig verändert werden. Systemdefinition Prozessdefinition Genau wie in Spin wird in Verisoft für jeden Teilnehmer genau ein Prozess zur Reali- sierung des Grove-Algorithmus benötigt. Prozessinitialisierung Die Modellierung der Prozesse wurde, genau wie bei den anderen beiden Verifikati- onstools, nur einmal durchgeführt, da Instanzen erzeugt werden konnten. Jede In- stanz des modellierten Prozesses wurde mit einer eindeutigen Id versehen, um eine spätere Identifikation des Teilnehmersystems zu ermöglichen. for (i=0; i<(APR-1); i++) { if (fork() == 0) { P1(i); } } P1(APR-1); void P1 (int id) {...} Variablen Weiterhin wurden die folgenden Variablen wurden definiert global #define APR 2 // # der Prozesse #define AOP 2 // # der Operationen pro Prozess #define QSZ 40 // (APR-1) * AOP #define EQUAL 0 #define SMALLER 1 #define BIGGER 2 #define INSERT 0 #define DELETE 1 #define INPROGRESS 0 #define FINISHED 1 #define EXECUTED 0 #define BREAKOFF 1 #define READY 0 #define WAIT 1 #define MAX 3 // max. Stellen der zu sendenden Zahlen (z.B. 123 => MAX 3) int queueId[APR] // ID des bounded FIFO Queues PrioListDef typedef struct PrioList { int prio; struct PrioList *next; struct PrioList *prev; } PrioListElem; LiQiListDef typedef struct LiQiList { int i; struct StatusList *s; int o[3]; Anhang B 115 struct PrioList *p; struct LiQiList *next; struct LiQiList *prev; } LiQiListElem; StatusDef typedef struct StatusList { int status; struct StatusList *next; struct StatusList *prev; } StatusListElem; TextFieldDef typedef struct TextField { char token; struct TextField *next; struct TextField *prev; } TextFieldElem; Vergleich der Zustandsvektoren int compStatus (StatusListElem *Si, StatusListElem *Sj) { int result; StatusListElem *dummySi, *dummySj; dummySi = Si; dummySj = Sj; result = EQUAL; while (dummySi != Si->prev) { if (dummySi->status > dummySj->status) { result = BIGGER; break; } if (dummySi->status < dummySj->status) result = SMALLER; dummySi = dummySi->next; dummySj = dummySj->next; } if (dummySi->status > dummySj->status) result = BIGGER; if (dummySi->status < dummySj->status) result = SMALLER; return result; } Prioritätsberechnung und -vergleich Prioritätsberechnung PrioListElem* calcPrio (PrioListElem *p, LiQiListElem *Li, StatusListElem *s, int id) { int i, num, resFlag; LiQiListElem *dummy; PrioListElem *found; num = getAnzElemLiQi(Li); found = initPrio (); dummy = Li; for (i=0; is, s); if (resFlag == EQUAL) { resFlag = compPrio (dummy->p, found); if (resFlag == BIGGER) found = dummy->p; } dummy = dummy->next; } p = setPrio (p, found, id); return p; } Prioritätsvergleich int compPrio (PrioListElem *Pi, PrioListElem *Pj) { int result, num_i, num_j, i, counter; Anhang B 116 PrioListElem *dummyPi, *dummyPj; if (Pj == NULL) return BIGGER; num_i = getAnzElemPrio(Pi); num_j = getAnzElemPrio(Pj); dummyPi = Pi; dummyPj = Pj; counter = 0; if (num_i == num_j) { for (i = 0; i < num_i; i++) { if (dummyPi->prio > dummyPj->prio) break; else counter++; dummyPi = dummyPi->next; dummyPj = dummyPj->next; } if ((counter-1) == i) return BIGGER; else return SMALLER; } if (num_i > num_j) { for (i = 0; i < num_j; i++) { if (dummyPi->prio != dummyPj->prio) return SMALLER; dummyPi = dummyPi->next; dummyPj = dummyPj->next; } return BIGGER; } if (num_i < num_j) { return SMALLER; } } Realisierung von Warteschlange und Logbuch Die Warteschlange und das Operationslogbuch sind als doppelt verkettete Listen realisiert. Operationsgenerierung LiQiListElem* genRequest (TextFieldElem *Ti, LiQiListElem *Qi, LiQiListElem *Li, StatusListElem *Si, int id) { int o[3]; int anzToken; PrioListElem *p; StatusListElem *s; p = initPrio(); anzToken = getAnzToken (Ti); // *** Operation ermitteln *** switch (VS_toss(1)) { case 0: o[0] = INSERT; break; case 1: o[0] = DELETE; break; } if (anzToken == 0) o[0] = INSERT; // *************************** // *** einzufügendes Zeichen ermitteln **** switch (VS_toss(8)) { case 0: o[1] = 1; break; case 1: o[1] = 2; break; case 2: o[1] = 3; Anhang B 117 break; case 3: o[1] = 4; break; case 4: o[1] = 5; break; case 5: o[1] = 6; break; case 6: o[1] = 7; break; case 7: o[1] = 8; break; case 8: o[1] = 9; break; } if (o[0] == DELETE) o[1] = 0; // **************************************** // *** Einfüge- o. Löschposition ermitteln *** if (anzToken == 0) o[2] = 1; else { srand((unsigned int)time((time_t *)NULL)); o[2] = ((rand()%anzToken) + 1); if ((o[0] == DELETE) && (o[2] > anzToken)) o[2] = anzToken; } // ******************************************* // *** Si duplizieren **** s = initStatus(APR); copyStatus (Si, s); // *** Berechnen der Priorität p = calcPrio (p, Li, s, id); // *** speichern der Werte in Qi *** Qi = addLiQi (Qi, id, s, o, p); return Qi; } Operationspropagierung bzw. -sendung Kommunikationsmechanismus Die Kommunikation der Prozesse bzw. der TS erfolgt über bounded FIFO Queues und Semaphore, welche eine Synchronisation der Kommunikation ermöglichen. for (i=0; iprev->i; int2str(num, go); send_to_queue(id, QSZ, go); s = Qi->prev->s; for (i=0; istatus; int2str(num, go); send_to_queue(id, QSZ, go); s = s->next; } Anhang B 118 help = Qi->prev->o[0]; int2str(help, go); send_to_queue(id, QSZ, go); help = Qi->prev->o[1]; int2str(help, go); send_to_queue(id, QSZ, go); help = Qi->prev->o[2]; int2str(help, go); send_to_queue(id, QSZ, go); p = Qi->prev->p; num = getAnzElemPrio (p); help = num; int2str(help, go); send_to_queue(id, QSZ, go); for (i=0; iprio; int2str(help, go); send_to_queue(id, QSZ, go); p = p->next; } } Operationsempfang i = is_queue_empty(queueId[id], QSZ); if (i != 1) { while (i != 1) { recQueue = recFromOther (queueId[id], recQueue); Qi = addCopyLiQi (recQueue, Qi); i = is_queue_empty(queueId[id], QSZ); } ... } LiQiListElem* recFromOther (int id, LiQiListElem *queue) { int num, k; int i; int o[3]; PrioListElem *p; StatusListElem *s; char *help; help = (char *) rcv_from_queue(id, QSZ); i = atoi(help); s = initStatus(APR); for (k=0; kstatus = atoi(help); s=s->next; } help = (char *) rcv_from_queue(id, QSZ); o[0] = atoi(help); help = (char *) rcv_from_queue(id, QSZ); o[1] = atoi(help); help = (char *) rcv_from_queue(id, QSZ); o[2] = atoi(help); p = initPrio(); help = (char *) rcv_from_queue(id, QSZ); num = atoi(help); for (k=0; ks, Si); if (resFlag == EQUAL) { // sj <= si // Ausführen ohne Transformation ... *flag = EXECUTED; } if (resFlag == SMALLER) { // sj < si // Ausführen mit Transformation ... *flag = EXECUTED; } if (resFlag == BIGGER) { // sj > si *flag = BREAKOFF; } if (*flag == EXECUTED) { Li = addCopyLiQi (dummy, Li); } else { printf("++++++++++ Zurückgestellt\n ++++++++++++"); } return Li; } Ruhezustand Der Ruhezustand eines Teilnehmersystems wird erreicht, wenn alle Operationen er- zeugt und ausgeführt sowie alle Operationen der anderen Teilnehmersysteme emp- fangen und ausgeführt wurden. if (numOP >= (AOP*APR)) flag = FINISHED; Definition der Korrektheitskriterien Die direkte Definition von Korrektheitskriterien ist mit Hilfe von Verisoft nicht möglich. Sie können implizit über die Verisoftfunktionen VS_assert und VS_abort spezifiziert werden. Anhang C 120 Anhang C ÜÜ C B BE ER RB BLLIIC CK K Ü ÜB BE ER R E EX XIIS STTIIE ER RE EN ND DE E V VEERRIIFFIIKKAATTIIO ON NS STTO OO OLLS S Dieses Kapitel gibt einen Überblick über die zum Zeitpunkt der Bearbeitung dieser Diplomarbeit existierenden Verifikationstools. Dabei wird zwischen nicht kommerziel- len und kommerziellen Tools unterschieden. Verifikations-Tools Nicht kommerzielle Tools Name Autor Unterstützte Algebren und Sprachen Unterstützte Plattformen Implementierungs- sprache ACL2 University of Texas at Austin LISP Unix, Linux, Windows 98, and Macintosh Atelier B Steria Mediterrane B method / Abstract Ma- SunOS 4.1.x, Solaris 2.x, HP-UX chine Notation (AMN) 9.x, Linux 2.x C/C++ extended SMV, synchro- Windows NT, Windows 95, Cadence SMV Cadence Berkeley Laboratories nous verilog, CTL, LTL, SunSparc(Solaris, SunOS), HP- ANSI C RTL UX, IRIX, Linux SunOS 4.1.* (Solaris 1.*) SunOS 5.* (Solaris 2.5, 2.6, 7, and 8) Linux with libc6/glibc2 binaries CADP INRIA LOTOS, XTL (Debian 2.2 or higher, RedHat 6.1 or higher, etc.) PC computers running Windows 98, NT4, or 2000 (with the Cygwin package providing Unix- like extensions) Circal University of South Australia XCircal Concurrency SUNY at Stony Factory Brook, NC State VPL (compiled into Facile) C++ University Concurrency Workbench of University of Edin- TCCS, SCCS, modal mu- SunSPARC (SunOS, Solaris), Endinburgh burgh calculus x86 (Linux) Concurrency SunSPARC (SunOS, Solaris), Workbench of North Carolina CCS, TCCS, CSP, Lotos, x86 (Linux, WinNT, Win95), Standard ML of New North Carolina State University modal mu-calculus, CTL MIPS (Irix), RS6000n (Aix), Jersey HPPA (HPUX), Alpha (OSF/1) ELUDO University of Ottawa LOTOS SunSparc(SunOS 4.1.3) C FC2Tools INRIA, Ecole des Mines de Paris FC2 Sun Solaris 2x, PC Linux 2.x, SunOS4, Dec Alpha Osf 1.x C/C++ Formal Systems SunSPARC (SunOS, Solaris), FDR2 Design and Devel- CSP HP PA-RISC (HP-UX), RS/6000 opment Inc. (AIX), x86 (FreeBSD, Linux, Solaris86) Laboratory for HOL Applied Logic, Brigham Young ML, HOL Logic Linux, Alpha, Solaris University Anhang C 121 Verifikations-Tools Nicht kommerzielle Tools Name Autor Unterstützte Algebren und Sprachen Unterstützte Plattformen Implementierungs- sprache HyTech University of Berke- ICTL, Linear hybrid auto- Digital Unix, DEC Ultrix, HP-UX, ley mata Linux C/C++ JACK University of Pisa ACTL SunSPARC (SunOS 4.1.3) C/C++ JACK 3 University of Pisa ACTL SunSPARC (SunOS 4.1.3) Java ? Kronos VERIMAG Timed automata Sun Solaris 5.1 , Linux LTSA University of Lon- don LTS, FSP Windows 95, 98 & NT Java Mobility Work- Universities of bench Edinburgh and Pi-calculus SunSparc(SunOS) Standard ML Uppsala University of Cali- · C with Tcl/Tk and Tix MOCHA / jMO- fornia, Berkley - ATL (CTL is sublanguage SunOS4, Solaris, DEC-Alpha, (cMOCHA) CHA 2.0 University of Penn- of ATL) DEC-Mips, HP-UX, Linux, Win- · Java JDK 1.2.2 sylvania dows (jMOCHA 2.0) (jMOCHA) Model- Technical University Checking Kit of Munich LTL, CTL Solaris., Linux Several IRST, CMU, Uni- Almost every UNIX platform, NuSMV 2 versity of Genova, NuSMV language (C-like), binaries for Solaris 2.5 University of Trento CTL and LTL logics (Sparc),Solaris 2.6 (Ultran Sparc), Linux (x86) PARAGON University of Penn- sylvania GCSR C/C++ PEP / PEP 2 Universität Olden- (beta) burg CTL, LTL Solaris 2.x, Linux, IRIX Tcl/Tk, JDK 1.0.2, Liquid reality, C/C++ RTGIL University of Cali- fornia (UCSB) SunOS 4.1.3, Solaris 2.5.1 Common Lisp Institute of Informa- SGM tion Science, Aca- TA, TCTL DOS, Windows (no GUI), Sun- demia Sinica Sparc(Solaris, SunOS), Linux School of Computer Windows NT, Linux, Sun- SMV Science,Carnegie CTL Sparc(SunOS4, SunOS5, So- C Mellon University laris), DECstation(Ultrix) SPIN Bell Laboratories PROMELA (based on all UNIX-based systems, x86 CSR), LTL (Win95, WinNT) ANSI C SyMP Carnegie Mellon School of CS SyMP (based on ML) UNIX, Linux Standard ML Truth MCS-Group CCS, mu-calculus SunSparc(Solaris 2.5), Linux 2.x(elf) Haskell, C, Java UPPAAL Uppsala and Aal- borg University Linux, SunSparc(SunOS), Win- dows 95/98/NT Java, C++ Verisoft Lucent Technolo- any language (C, C++, Tcl, gies etc.) SunSparc(SunOS 5.x), Linux 2.x VERSA University of Penn- sylvania ACSR SunSPARC (SunOS) C/C++ VIS University of Cali- CTL, Verilog HDL SunOS 4, Solaris 5, Ultrix V4.5, C Anhang C 122 Verifikations-Tools Nicht kommerzielle Tools Name Autor Unterstützte Algebren und Sprachen Unterstützte Plattformen Implementierungs- sprache fornia, Berkley Digital UNIX V4.0, Linux 2.x, HP-UX, Windows9x, IRIX 5.3, AIX Tab.C-1: gefundene (nicht kommerzielle) Verifikationstools (Überblick) Verifikations-Tools Kommerzielle Tools Name Autor Unterstützte Algebren und Sprachen Unterstützte Plattformen Implementierungs- sprache Temporal- Rover Time Rover Inc. LTL, MTL C/C++, Java, Verilog, VHDL FormalCheck Cadence Design Systems Tab.C-2: gefundene (kommerzielle) Verifikationstools (Überblick) Die folgenden beiden Tabellen zeigen detaillierte Informationen zu den einzelnen Verifikationstools. Dabei wird wiederum zwischen kommerziellen und nicht kommer- ziellen sowie zwischen Tools und Tool-Kit's unterschieden. Als Tool werden die Werkzeuge eingeordnet, die eigenständige Simulatoren und Ve- rifikatoren sowie eigene Spezifikationssprachen und evtl. entsprechende Schnittstel- len besitzen. Im Gegensatz dazu, besitzen Tool-Kit's Schnittstellen zu anderen Veri- fikationstools (z.B. besitzt PEP eine Schnittstelle zu Spin). Verifikations-Tools Nicht kommerzielle Tools Name Tool Tool-Kit Links Beschreibung · mathematical logic together with a mechanical theorem prover · theorem prover is an industrial strength'' version of the ACL2 http://www.cs.ute- xas.edu/users/moore/acl2/ Boyer-Moore theorem prover, Nqthm. · Models of all kinds of computing systems can be built · an ACL2 model of a system - run able · use ACL2 to prove theorems about the model · Atelier B is an industrial set of tools to apply the B method (B method is used to develop critical software Atelier B http://www.ate- lierb.societe.com/index_uk components as well as to validate critical system specifi- .html cations) · Graphical Interface · allows several forms of specification, including the http://www- temporal logics CTL and LTL, finite automata, embedded Cadence SMV cad.eecs.berke- assertions, and refinement specifications ley.edu/~kenmcmil/smv/ · graphical user interface · source level debugging capabilities. · Several input languages: process algebra with values (International Standard LOTOS), finite state machines, and networks of communicating finite state machines. · Three different tools for computing bisimulations (mini- CADP http://www.inrial- pes.fr/vasy/cadp/ mizations and comparisons): ALDEBARAN, BCG_MIN, and FC2TOOLS. · Two different model-checkers for various temporal logic and mu-calculus: EVALUATOR and XTL. · Several verification algorithms: exhaustive verification, Anhang C 123 Verifikations-Tools Nicht kommerzielle Tools Name Tool Tool-Kit Links Beschreibung on-the-fly verification, symbolic verification using Binary- Decision-Diagrams, compositional verification based on refinement. · graphical Interface · tool box · two versions: (1) explicit representation of the state space http://www.acrc.uni- (2) implicit representation in terms of OBDD's. Circal sa.edu.au/doc/circal/circal · tool based on the process algebra Circal _system.html · used for the specification and automatic verification of concurrent systems · A graphical user interface. It allows non-experts to design concurrent systems using GCCS, a graphical version of the process algebra CCS. · A textual user interface for VPL, a simple language for concurrent processes that communicate values from a Concurrency finite data domain. Factory http://www.cs.su- nysb.edu/~concurr/ · A set of simulators for both VPL and GCCS. · A suite of analysis routines that includes a local model checker for the modal mu-calculus, a powerful temporal logic.. · A set of code generators. Currently Java and Ada'95 code can be automatically generated for the concurrent systems designed by the users. · manipulation and analysis of concurrent systems (tex- Concurrency ted-based) Workbench of http://www.dcs.ed.ac.uk/ho · CWB allows for various equivalence, preorder and Endinburgh me/cwb/ model checking using a variety of different process semantics Concurrency text-based or graphical interface Workbench of North Carolina · takes a LOTOS specification as input, checks its static semantics, and executes the specification to produce the next possible actions as output. ELUDO http://lotos.site.uotta- wa.ca/eludo/ · step-by-step mode (interpretation, a.k.a. ISLA) · symbolic tree generation mode (a.k.a. SELA) · goal-oriented mode · text-based or graphical interface http://www- · a symbolic/explicit verification toolset for concurrent FC2Tools sop.inria.fr/mei- processes je/verification/ · graphical interface · model-checking tool for state machines, with founda- FDR2 http://www.for- tions in the theory of concurrency based around CSP mal.demon.co.uk/FDR2.ht · graphical interface ml · useful mainly in hardware/software verification with HOL ability to prove pure mathematical problems · Emacs interface, graphical interface, Tcl/Tk interface http://www- a symbolic model checker for embedded systems HyTech cad.eecs.berke- ley.edu/~tah/HyTech/ JACK http://rep1.iei.pi.cnr.it/pro- set of verification tools supported by a graphical interface jects/JACK/ Anhang C 124 Verifikations-Tools Nicht kommerzielle Tools Name Tool Tool-Kit Links Beschreibung JACK 3 http://rep1.iei.pi.cnr.it/pro- jects/JACK/ http://www.imag.fr/VERIM formal verification of real-time systems based on timed Kronos AG/TEMPORISE/kronos/in automata and temporal logic dex-english.html · verification tool for concurrent systems· checks that the LTSA http://www.doc.ic.ac.uk/~jn m/book/ltsa/LTSA.html specification of a concurrent system satisfies the proper- ties required of its behaviour· graphical interface · prototype version Mobility Work- · just equivalence checking bench http://www.docs.uu.se/~vic tor/mwb.html · a tool for manipulating and analyzing mobile concurrent systems described in the pi-calculus · interactive software environment for system specifica- tion and verification · exploit, rather than destroy, design structure in auto- matic verification MOCHA / jMOCHA http://www- · capabilities: 2.0 cad.eecs.berke- (1) System specification ley.edu/~mocha/what.shtm (2) System execution l (3) Requirement specification (4) Requirement verification (5) Implementation verification · graphical interface · a collection of programs which allow to model a finite- state system http://wwwbrau- · using a variety of modelling languages · verify it using a variety of checkers Model-Checking er.informatik.tu- · deadlock-checkers Kit muen- chen.de/gruppen/theorie/K · reachability-checkers IT/ · model-checkers · Independently of the description language chosen by the user (almost - all checkers can be applied to the same model) · symbolic model checker · reimplementation and extension of SMV · based on BDDs. NuSMV 2 http://nusmv.irst.itc.it/ · open architecture for model checking · SAT-based model checking component that includes an RBC-based Bounded Model Checker · graphical interface, textual interactive interface · a tool for visual specification and verification of distrib- uted real-time systems · graphical editor for the GCSR specification language · visual simulator for GCSR specifications (under con- PARAGON http://www.cis.u- penn.edu/~lee/paragon.ht struction) ml · a graphical user interface to VERSA (a verification tool for ACSR specifications) · Translators between GCSR and ACSR · graphical interface · set of modelling, compilation, simulation and verification components · PEP's modelling components facilitate the design of parallel systems by parallel programs (B(PN)^2 and SDL), interacting finite automata, process algebra, or PEP / PEP 2 (beta) http://theoreti- ca.informatik.uni- high-level/low-level Petri nets. oldenburg.de/~pep/ · compilers generate Petri nets from such models. · simulators allow automatic or user-driven simulation of high-level / low-level nets and may trigger simulation of the corresponding programs and/or a 3D model. · verification component contains various Petri net in- Anhang C 125 Verifikations-Tools Nicht kommerzielle Tools Name Tool Tool-Kit Links Beschreibung digenous algorithms to check, e.g., reachability proper- ties and deadlock-freeness, as well as verification algo- rithms · interfaces to INA, FC2TOOLS, SMV, SPIN · open platform (further algorithms can be integrated in the user interface) · graphical interface · specifying and reasoning about time-bounded safety and liveness properties of concurrent real-time systems · include a syntax-directed editor · a theorem prover based on a decision procedure RTGIL http://beta.ece.ucsb.edu/rt (checks the validity of attempted proofs and produces a gil.html counterexample if an attempted proof is invalid) · a proof management and database system that tracks proof dependencies and allows graphical formulas to be stored and retrieved · graphical interface · high-level real-time state-graph manipulation tool for concurrent system specification and verification SGM http://www.cs.ccu.edu.tw/~ pahsiung/sgm/ · text or graphical interface · Windows-version (just Interactive/Batch Interfaces) · tool for checking finite state system against specifica- tion in temporal logic CTL SMV http://www.cs.cmu.edu/~m · input language of SMV is designed to allow the descrip- odelcheck/ tion of finite state system that range from completely synchronous to completely asynchronous · Emacs and Vim syntax highlightning · efficient software verification, not hardware verification · used to trace logical design errors in distributed sys- tems design, such as operating systems, data communi- cations protocols, switching systems, concurrent algo- rithms, railway signaling protocols, etc. · checks the logical consistency of a specification (dead- locks, unspecified receptions, flags incompleteness, race conditions, unwarranted assumptions about the relative speeds of processes. · Spin works on-the-fly http://netlib.bell- · full LTL model checking system SPIN labs.com/netlib/spin/whatis · supports dynamically growing and shrinking numbers of pin.html processes, using a rubber state vector technique. · supports both rendezvous and buffered message pass- ing, communication through shared memory, Mixed systems, using both synchronous and asynchronous communications · supports random, interactive and guided simulation, and both exhaustive and partial proof techniques · To optimize the verification runs, the tool exploits effi- cient partial order reduction techniques, and (optionally) BDD-like storage techniques. · graphical interface · model checking and theorem proving on specific mod- http://www- els (not for general theorems)· used mainly for hardware SyMP 2.cs.cmu.edu/~modelchec verification· can be viewed as a front-end for low-level k/ verification techniques (BDDs, explicit state model checking, etc...)· requires SMV as a back-end model checker · a verification tool especially for testing new concepts for http://www- specification, modelling concurrency, logic and model i2.informatik.rwth- checking algorithms Truth aa- · needs daVinci, Java(JDK 1.1.1), Java Swing, Object- chen.de/Forschung/MCS/T space and dotty(graphviz) ruth/ · just Beta-Version · graphical interface Anhang C 126 Verifikations-Tools Nicht kommerzielle Tools Name Tool Tool-Kit Links Beschreibung · tool environment for modelling, simulation and verifica- tion of real-time systems · Typical application areas include real-time controllers and communication protocols in particular, those where timing aspects are critical · on-the-fly searching technique · a symbolic technique whose reduces verification prob- UPPAAL http://www.docs.uu.se/doc s/rtmv/uppaal/index.shtml lems to that of efficient manipulation and solving of con- straints · automatically generation of a diagnostic trace that explains why a property is (or is not) satisfied by a sys- tem description (diagnostic traces can be loaded auto- matically to the simulator, which may be used for visuali- zation and investigation of the trace) · graphical interface · searches for coordination problems (deadlocks, etc.) and assertion violations in a software system by generat- ing, controlling, and observing the possible executions and interactions of all its components · integrates automatic test generation, execution and evaluation in a single framework · includes an interactive graphical simulator that can Verisoft http://www1.bell- labs.com/project/verisoft/ drive existing debuggers for examining precisely the concurrent execution of multiple processes. · can test software applications developed in any lan- guage (C, C++, Tcl, etc.) · optimized for analyzing multi-process applications · key technology -> a new form of systematic state-space exploration. · graphical interface · Verification, Execution and Rewrite System for ACSR · supports three types of analysis techniques: (1) Application of rewriting rules to ACSR specifications to deduce system properties (2) Construction of a state machine and automatic exploration and analysis of the state space to verify VERSA http://www.cis.upenn.edu/ ~lee/duncan/versa.html safety properties and test equivalence of alternative process formulations (3) Interactive execution of the process specification to explore specific system behaviours and sample the execution traces of the system · basic is command oriented interface (graphic interface is available -> X-VERSA) · for formal verification, synthesis, and simulation of finite state systems · simulation of logic circuits (proof of concept only). http://www- · formal "implementation" verification of combinational VIS cad.eecs.berke- and sequential circuits (proof of concept only) ley.edu/Respep/Research/ · State-of-the-art formal "design" verification using fair vis/ CTL model checking and language emptiness. · logic synthesis via hierarchy restructuring and a path to and from SIS · text interface Tab.C-3: gefundene (nicht kommerzielle) Verifikationstools (Charakterisierung) Verifikations-Tools Kommerzielle Tools Name Tool Tool-Kit Links Beschreibung · formal verification of complex control units without vectors or a testbench FormalCheck http://www.cadence.com/pro ducts/formalcheck.html · Non-determinism (all cases are covered) · GUI and flexible Tcl/Tk command-line interpreter Anhang C 127 Verifikations-Tools Kommerzielle Tools Name Tool Tool-Kit Links Beschreibung · formal specification, using Linear-Time Temporal Logic (LTL) and Metric Temporal Logic (MTL), with conventional simulation/execution based testing · tailored for the verification of complex protocols and reactive systems where behaviour is time dependent Temporal-Rover http://www.time- · generates executable code from LTL and MTL asser- rover.com/TRindex.html tions written as comments in the source code · during application execution the generated code validates the executing program against the formal temporal specification requirements · using MTL, real time and relative time constraints can be validated Tab.C-4: gefundene (kommerzielle) Verifikationstools (Charakterisierung) Erklärung 128 Ich versichere, dass ich diese Arbeit selbständig verfasst und nur die angegebenen Hilfsmittel verwendet habe. (Sören Schneider)