Stephan Kleuker Formale Modelle der Softwareentwicklung
Aus dem Programm
Datenbanken und Softwareentwicklung
weitere Titel des Autors Grundkurs Datenbankentwicklung von S. Kleuker Grundkurs Software-Engineering mit UML von S. Kleuker
Softwareentwicklung – kompakt und verständlich von H. Brandt-Pook und R. Kollmeier Six Sigma in der SW-Entwicklung von T. M. Fehlmann Management der Software-Entwicklung von C. Steinweg User Interface-orientierte Softwarearchitektur von P. Chlebek Software Engineering von R. Dumke Algorithmen kompakt und verständlich von M. von Rimscha
www.viewegteubner.de
Stephan Kleuker
Formale Modelle der Softwareentwicklung Model-Checking, Verifikation, Analyse und Simulation Mit 206 Abbildungen STUDIUM
Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über
abrufbar.
Das in diesem Werk enthaltene Programm-Material ist mit keiner Verpflichtung oder Garantie irgendeiner Art verbunden. Der Autor übernimmt infolgedessen keine Verantwortung und wird keine daraus folgende oder sonstige Haftung übernehmen, die auf irgendeine Art aus der Benutzung dieses Programm-Materials oder Teilen davon entsteht. Höchste inhaltliche und technische Qualität unserer Produkte ist unser Ziel. Bei der Produktion und Auslieferung unserer Bücher wollen wir die Umwelt schonen: Dieses Buch ist auf säurefreiem und chlorfrei gebleichtem Papier gedruckt. Die Einschweißfolie besteht aus Polyäthylen und damit aus organischen Grundstoffen, die weder bei der Herstellung noch bei der Verbrennung Schadstoffe freisetzen.
1. Auflage 2009 Alle Rechte vorbehalten © Vieweg+Teubner | GWV Fachverlage GmbH, Wiesbaden 2009 Lektorat: Christel Roß | Sybille Thelen Vieweg+Teubner ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.viewegteubner.de Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg Druck und buchbinderische Verarbeitung: STRAUSS GMBH, Mörlenbach Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier. Printed in Germany ISBN 978-3-8348-0669-7
Vorwort Software muss funktionieren, um von Kunden akzeptiert zu werden. Doch wie stellt man sicher, dass die Steuerung eines Raumschiffs, eines Herzschrittmachers oder einer Aktienverwaltung korrekt funktioniert? Neben den klassischen Testansätzen spielen für den Korrektheitsnachweis zunehmend Formale Modelle eine zentrale Rolle. Ein Modell erlaubt es, ein beliebiges sequenzielles oder verteiltes System zu analysieren und zu simulieren. Dadurch, dass Korrektheitsanforderungen präzise definiert werden, kann man sogar beweisen, dass die Anforderungen erfüllt sind. Dieses Buch stellt unterschiedliche Formale Modelle mit ihren Einsatzmöglichkeiten und Werkzeugen vor. Dabei steht bewusst die Anwendung der Modelle und nicht die Theorie dahinter im Vordergrund. Formale Modelle ermöglichen es dabei, Aussagen so zu präzisieren, dass sie von jedem, der das Modell versteht, eindeutig interpretiert werden können. Weiterhin kann für Formale Modelle nachgewiesen werden, dass sie bestimmte Eigenschaften haben. Abhängig von der Art des Formalen Modells erfolgt dieser Nachweis automatisch durch ein Programm oder durch den Entwickler, der Beweisregeln anwendet. Dieses Buch zeigt u. a., wie man Aussagen über Modelle und Anforderungen an Modelle präzise formulieren und ihre Gültigkeit nachweisen kann. Formale Methoden nutzen Formale Modelle und sichern die Korrektheit von Software. Sie werden kontinuierlich seit den 1970er Jahren entwickelt. Die Erkenntnisse führten unter anderem zu den Turing Awards von C.A.R. Hoare (1980), A. Pnueli (1996) und E.M. Clark, E. A. Emerson und J. Sifakis (2007), deren Ansätze zur Programmverifikation und zum Model Checking in diesem Buch vorgestellt werden. Kritisch bleibt anzumerken, dass die formalen Ansätze nur schleppend auch in den sicherheitskritischen Bereichen (Raumfahrt, Luftfahrt, Automobilsysteme) Einzug in die Entwicklung finden. Ein zentraler Grund für dieses Defizit ist, dass die Ansätze bisher immer zusammen mit ihrem sehr komplexen theoretischen Hintergrund präsentiert wurden und es keine Einführungen für „Endanwender“ dieser Ansätze, also Entwickler, gibt. Diese Lücke wird durch dieses Buch geschlossen. Nach einer kurzen Motivation des Themengebiets wird zunächst die Spezifikationssprache PROMELA zusammen mit dem Werkzeug SPIN von G. Holzmann vorgestellt, das 2001 den renommierten ACM Software System Award gewonnen hat. SPIN eignet sich zur Spezifikation, zur interaktiven und automatischen Simulation und zur Verifikation verteilter Systeme. Es wird auch gezeigt, wie man klassische sequenzielle Softwaresysteme als Spezialfall mit SPIN behandeln kann. Timed Automata erlauben die Spezifikation von verteilten Systemen mit Zeit, die dann im Werkzeug Uppaal simuliert und verifiziert werden können. Mit Uppaal
V
Vorwort steht dabei ein graphisches Werkzeug zur Verfügung, das verteilte Abläufe sehr gut visualisieren kann. Petrinetze sind der klassische Einstieg in die systematische Analyse verteilter Systeme und in vielen Varianten theoretisch sehr gut untersucht. Neben der Anschauung steht in diesem Buch die Erkenntnis im Mittelpunkt, dass Ansätze aus verwandten wissenschaftlichen Disziplinen, hier der linearen Algebra, wesentliche Erkenntnisse über Software liefern können. Weiterhin wird gezeigt, wie schwer es ist, eine Komponente in einem Netzwerk verteilter kommunizierender Systeme auszutauschen. Formalere Überlegungen zur Programmverifikation runden dieses Buch ab und zeigen die Fundierung der Probleme und Lösungsansätze für die Korrektheit von Programmen. Der praktische Nutzen wird mit einer Verknüpfung zur Welt des Testens aufgezeigt. Die Kapitel zwei bis fünf sind so geschrieben, dass man sie von vorne nach hinten alleine oder in einer Lehrveranstaltung durcharbeiten kann. Es besteht aber auch die Möglichkeit, die Kapitel einzeln zu betrachten oder Kapitel auszulassen. Mit wenigen Querverweisen wird auf relevante Informationen anderer Kapitel verwiesen. Wer z. B. mehr am Ausprobieren und der Veranschaulichung interessiert ist, kann den Fokus auf die Kapitel zwei und drei legen, wer anfänglich eine theoretische Fundierung der Korrektheitsproblematik wünscht, sollte mit Kapitel fünf starten. Alle in diesem Buch genauer betrachteten Werkzeuge können zum Lernen ohne Kosten aus dem Internet bezogen werden. Gerade diese Möglichkeit, nicht nur über die Werkzeuge zu lesen, sondern mit ihnen zu experimentieren, macht die vorgestellten Ansätze für Praktiker interessant. Statt nach theoretischen Antworten auf Fragen, wie ein Werkzeug in bestimmten Situationen reagiert, zu suchen, ist der Nutzer selbst zum Experimentieren aufgerufen. Die Übungsaufgaben dieses Buches bieten einen guten Startpunkt dazu. Jedes Kapitel schließt mit zwei Arten von Aufgaben ab. Im ersten Aufgabenteil werden Wiederholungsfragen gestellt, die man nach intensiver Lektüre des vorangegangenen Kapitels beantworten können sollte. Die Lösungen zu diesen Aufgaben kann man selbst im Buch nachschlagen. Der zweite Aufgabenteil umfasst Übungsaufgaben, in denen man gezielt das angelesene Wissen anwenden soll. Diese Übungsaufgaben sind in verschiedenen Lehrveranstaltungen erfolgreich eingesetzt worden. Die Bilder, Spezifikationen, Folien zum Buch und Lösungen zu Aufgaben dieses Buches sowie weitere Informationen können von der folgenden Web-Seite http://www.edvsz.fh-osnabrueck.de/kleuker/fmse/index.html
oder von den Web-Seiten des Verlages zum Buch herunter geladen und unter Berücksichtigung des Copyrights genutzt werden. In diesem Buch benutze ich verkürzend ohne Hintergedanken beim Singular wie Leser oder Entwickler die männliche Form. Natürlich möchte ich mit diesem Buch auch die weiblichen Leser Leserinnen ansprechen.
VI
Vorwort Zum Abschluss wünsche ich Ihnen viel Spaß beim Lesen. Konstruktive Kritik wird immer angenommen. Bedenken Sie, dass das Lesen nur ein Teil des Lernens ist. Ähnlich wie in diesem Buch kleine Beispiele eingestreut sind, um einzelne Details zu klären, sollten Sie sich mit den hier vorgestellten Ideen hinsetzen und meine, aber vor allem selbst konstruierte Beispiele durchspielen. Sie runden das Verständnis des Themas wesentlich ab. Osnabrück, Oktober 2009
Stephan Kleuker
Danksagung Ein Buch kann nicht von einer Person alleine verwirklicht werden. Zu einer gelungenen Entstehung tragen viele Personen in unterschiedlichen Rollen bei, denen ich hier danken möchte. Mein erster Dank geht an meine Ehefrau Dr. Cheryl Kleuker, die nicht nur die erste Kontrolle der Inhalte und Texte vorgenommen hat, sondern mir erlaubte, einen Teil der ohnehin zu geringen Zeit für die Familie in dieses Buchprojekt zu stecken. Besonderer Dank gilt Henning Dierks, Jutta Göers, Elke Pulvermüller, Wolfgang Runte und Frank Thiesing, die unterschiedliche Teile einer Vorversion dieses Buches kritisch durchgelesen haben und interessante Anregungen lieferten. Viele Studierende, die Veranstaltungen zum Thema Formale Methoden bei mir gehört haben, trugen durch ihre Fragen und Probleme wesentlich zu der Herangehensweise an die Themen des Buches bei. Abschließend seien Sybille Thelen, Andrea Broßler, Albrecht Weis und den weiteren Mitarbeitern des Verlags Vieweg+Teubner für die konstruktive Mitarbeit gedankt, die dieses Buchprojekt erst ermöglichten.
VII
für Cheryl und Lisa
Inhaltsverzeichnis Vorwort ..................................................................................................................... V 1 Motivation von Formalen Modellen ................................................................ 1 1.1 Modellbegriff................................................................................................................ 1 1.2 Software-Fehler ............................................................................................................ 3 1.3 Software-Engineering ................................................................................................. 7 1.4 Fragen.......................................................................................................................... 11
2 Modelchecking mit PROMELA und SPIN ................................................... 13 2.1 Modelchecking im Entwicklungskontext ............................................................... 14 2.2 Die Spezifikationssprache PROMELA ................................................................... 16 2.3 Simulation von PROMELA-Spezifikationen ......................................................... 36 2.4 Einfache Verifikationsmöglichkeiten ...................................................................... 49 2.4.1 Grundideen des Modelcheckings..................................................................... 49 2.4.2 Modelchecking sehr großer Systeme ............................................................... 56 2.4.3 Lebendigkeit und Sicherheit ............................................................................ 59 2.4.4 Zusicherungen ................................................................................................. 60 2.4.5 Prozessterminierung ........................................................................................ 63 2.4.6 Ausführung einfacher Verifikationen .............................................................. 63 2.4.7 Nachweis von Lebendigkeitseigenschaften ..................................................... 67 2.4.8 Trace-Zusicherungen ....................................................................................... 70 2.4.9 Never-Claims................................................................................................... 72 2.5 Verifikation von in LTL formulierten Anforderungen......................................... 77 2.6 Beispiele ...................................................................................................................... 84 2.7 PROMELA und SDL ................................................................................................. 98 2.8 Aufgaben .................................................................................................................. 106
3 Modelchecking mit Timed Automata und Uppaal ................................... 117 3.1 Synchron kommunizierende Automaten ............................................................. 118 3.2 Spezifikationen mit Zeit.......................................................................................... 125 3.3 Nutzung von Uppaal .............................................................................................. 131 3.4 Timed Computation Tree Logic und Verifikation .............................................. 138 3.5 Beispiele .................................................................................................................... 146
IX
Inhaltsverzeichnis 3.6 Aufgaben .................................................................................................................. 157
4 Petrinetze ........................................................................................................... 163 4.1 Funktionsweise von Petrinetzen ........................................................................... 163 4.2 Erreichbarkeitsgraphen und Überdeckungsgraphen ......................................... 169 4.3 S- und T-Invarianten ............................................................................................... 174 4.4 Werkzeuggestützte Analyse von Petrinetzen ...................................................... 180 4.5 Beispiele .................................................................................................................... 187 4.6 Äquivalenzen von Petri-Netzen ............................................................................ 191 4.7 Aufgaben .................................................................................................................. 197
5 Programmverifikation ..................................................................................... 201 5.1 Eine einfache Programmiersprache ...................................................................... 202 5.2 Operationelle Semantik .......................................................................................... 204 5.3 Zusicherungen ......................................................................................................... 211 5.4 Partielle und totale Korrektheit ............................................................................. 214 5.5 Beweissysteme für partielle und totale Korrektheit ........................................... 219 5.6 Programmverifikation in der Praxis ..................................................................... 233 5.7 Syntax und Semantik paralleler Programme ....................................................... 242 5.8 Beweissysteme für parallele Programme ............................................................. 250 5.9 Parallele Programmierung ..................................................................................... 259 5.10 Aufgaben ................................................................................................................ 266
A Installationsbeschreibungen ........................................................................ 275 A.1 Installation von SPIN ............................................................................................. 275 A.2 Installation von Uppaal ......................................................................................... 277 A.3 Installation von NetLab ......................................................................................... 279
B Kurzeinführung in Java ................................................................................. 281 B.1 Grundlagen .............................................................................................................. 281 B.2 Threads ..................................................................................................................... 288
Literaturverzeichnis ............................................................................................. 293 Sachwortverzeichnis............................................................................................ 297
X
1 Motivation von Formalen Modellen Der Begriff „formal“ kann viele Assoziationen hervorrufen. Eine typische negative führt zum Begriff „Formalismus“, der mit vielen Formularen und einer wuchernden Bürokratie verbunden werden kann. Auf einem anderen Weg kann man aber „formal“ auch mit den Begriffen „genau“, „exakt“ und „präzise“ verbinden. Hieraus leiten sich Assoziationen zu präzise gearbeiteten Kunstwerken, aber auch zu gelungenen Handwerksleistungen, wie sauber verlegten Fliesen, ab. Ich gehöre zu den Leuten, die begeistert davon sind, wenn handwerklich geschickte Menschen ihre Arbeit verrichten. Formale Modelle können ebenfalls beide Arten von Assoziationen wecken. Ziel dieses Buches ist es zu zeigen, dass eine Assoziation mit einem ästhetischen und trotzdem ingenieurwissenschaftlichen Handwerk, nämlich der Erstellung qualitativ hochwertiger Softwaresysteme, am passendsten ist. Dabei sollen natürlich auch Risiken durch die Nutzung des falschen formalen Ansatzes und weitere Restriktionen diskutiert werden. In diesem Kapitel wird anhand von Problemen, die zumindest maßgeblich mit von Software verursacht wurden, gezeigt, warum Formale Modelle notwendig sind. Dazu wird zunächst der Modellbegriff genauer betrachtet. Danach wird an verschiedenen Beispielen verdeutlicht, welche Ursachen Software-Fehler haben können und wie gravierend ihre Auswirkungen teilweise sind. Dieses Buch zeigt, dass Formale Modelle ein wichtiger Baustein bei der Erstellung qualitativ hochwertiger Software sind.
1.1 Modellbegriff Der Modellbegriff wird hier in der folgenden Form genutzt: Ein Modell ist das vereinfachte Abbild einer Realität, wobei Schlüsse, die aus der Untersuchung des Modells gewonnen wurden, auf die Realität übertragen werden können. Dabei heißt ein Modell passend zu einer Aufgabenstellung, wenn es zur korrekten Lösung der Aufgabenstellung beitragen kann. Von der gleichen realen Situation können verschiedene Modelle abgeleitet werden, wobei mehrere Modelle passend zu einer Aufgabenstellung sein können. Natürlich kann man auch unpassende Modelle wählen. Will man z. B. die Mobilität von Menschen im Zusammenhang mit ihrem Einkaufsverhalten untersuchen, kann man unterschiedliche Ansätze mit verschiede-
1
1 Motivation von Formalen Modellen nen Modellen verfolgen. Eine exakte, zum Glück noch nicht realisierte Variante nutzt einen Sender, der Personen umgehängt wird, so dass ihre Position jederzeit bestimmt werden kann. Im Modell werden die Informationen, wer an welcher Position zu welchem Zeitpunkt ist, festgehalten. Kennt man dann die Positionen von Einkaufsmöglichkeiten, kann exakt aus dem Modell herausgelesen werden, wer wie häufig und wie lange in einem Geschäft war. Werden keine Informationen über Einkäufe erhoben, sind allerdings keine Aussagen über konkrete Einkäufe möglich. In einem anderen Ansatz wird der Mensch mit seinen Einkäufen in einem Modell mit seinen Kreditkarten, EC-Karten und Bonuskarten erfasst. Kennt man die Informationen, wer was wann eingekauft hat, kann man Einkäufe und den Aufenthaltsort zusammen bringen. Ob das Modell passend zur Aufgabenstellung ist, kann aber kritisch betrachtet werden, da unklar ist, wie häufig Barzahlung genutzt wurde. Verknüpft man beide Modelle, so erhält man ein komplexeres Modell, aus dem neue Aussagen z. B. über die Aufenthaltsdauer, verknüpft mit der Wahrscheinlichkeit eines Einkaufs gewonnen werden können, allerdings das letzte Problem mit der Barzahlung auch nicht gelöst werden kann. Neben dieser offenen Frage muss auch bedacht werden, dass die Daten der Modelle verknüpft werden müssen, wodurch eine enorme Datenmenge entsteht, die vielleicht mit der gegebenen Hardware nicht bearbeitet werden kann. In diesem Fall hätte man zwar ein passendes Modell, allerdings mit geringem praktischem Nutzen. Ein unpassendes Modell besteht z. B. ausschließlich aus den Adressen aller Personen, die beim Einkauf erfasst werden, da man so zwar Informationen über die Häufigkeit von Menschen an gewissen Orten gewinnen kann, allerdings jedwede Aussage über das Kaufverhalten fehlt. Die hier gewonnenen Kenntnisse über die Modellbildung werden in den folgenden Kapiteln auch auf Formale Modelle übertragbar sein. Man benötigt möglichst gut handhabbare Modelle, aus denen möglichst viele Aussagen gewonnen werden können. Dabei kann es für unterschiedliche Aussagen über reale Software durchaus sinnvoll sein, verschiedene Modelle zu betrachten. Eine Verknüpfung von unterschiedlichen Modellen kann zu einer genaueren Lösung führen; es kann aber passieren, dass der Ansatz nicht mehr praktisch handhabbar ist. Bei dem Modell, bei dem die Positionen der Menschen protokolliert werden, fällt weiterhin auf, dass sehr viele Daten anfallen, die für die Aufgabenstellung nicht benötigt werden. Informationen darüber, dass eine Person acht Stunden schläft, können z. B. vernachlässigt und damit aus den erhobenen Daten gelöscht werden. Generell lässt sich daraus folgende Forderung an ein Modell ableiten: Für ein konkretes System, z. B. eine zu entwickelnde oder schon entwickelte Software, und eine konkrete Aufgabenstellung wird ein möglichst einfaches Modell gesucht, das die Lösung der Aufgabenstellung erlaubt. Dabei bedeutet „möglichst
2
1.2 Software-Fehler einfach“, dass die zugehörigen Daten schnell erhoben und einfach bearbeitbar sind. Maßgeblich kann dazu beitragen, dass nur relativ wenige Daten benötigt werden. Die Suche nach einem passenden Modell ist dabei ein sehr kreativer Prozess, der durch die Kenntnisse unterschiedlicher Modelle fundiert werden kann. Ein Beispiel für eine innovative Wahl eines Modells stellt die Lösung zur Fragestellung nach der Geschwindigkeit einer Ausbreitung einer Epidemie in den USA dar. Zur Analyse werden wieder typischerweise sehr zeitaufwändig und teuer zu erhebende Bewegungsdaten benötigt. Der Modellansatz der Forscher war es allerdings, auf die Daten einer netten Internet-Spielerei zuzugreifen, an der sich relativ viele Amerikaner beteiligen. Auf der Internet-Seite „Where is George“ [WiG], kann man die Seriennummern seiner Ein-Dollar-Scheine (mit einem Bild von George Washington) und seinen Standort eintragen. Dadurch, dass eindeutige Seriennummern mehrfach auftreten, kann man sehen, von wo nach wo sich Dollarscheine und damit ihre zwischenzeitlichen Besitzer bewegt haben. Ein zentrales Ergebnis der Untersuchung ist, dass sich Epidemien wesentlich schneller von der Ost-Küste auf die West-Küste ausbreiten können, als vorher berechnet. Auch bei formalen Modellen werden wir feststellen, dass sie verschiedene Aspekte, z. B. die Nutzung von Zeit betonen und vernachlässigen können, so dass man über die Nutzung mehrerer Modelle für unterschiedliche Anforderungen nachdenken kann.
1.2 Software-Fehler Die relativ kurze Geschichte der Software-Entwicklung, die in den 1930er-Jahren begann [Zus07], ist geprägt durch zwei markante Eigenheiten. Auf der einen Seite steht der enorme Fortschritt in der Hardware-Entwicklung im Zusammenhang mit der stark steigenden Komplexität von Software, die bereits Einzug in einfachste Haushaltsgeräte gefunden hat. Auf der anderen Seite steht die lange Liste von markanten Software-Fehlern oder Fehlern im Zusammenspiel von Software und Hardware, die Menschenleben und viele Milliarden Euro gekostet haben. Seit Mitte der 1960er Jahre wird die kreative Energie der relativ wenigen Personen, die sich bis dahin mit der Software-Entwicklung beschäftigt haben, immer mehr systematisiert, so dass daraus die ingenieur-wissenschaftliche Disziplin des SoftwareEngineering wurde. Bevor wir uns mit den Errungenschaften des SoftwareEngineering im Hinblick auf die Korrektheit von Programmen beschäftigen, sollen hier zur Mahnung einige der markantesten Software-Fehler zusammengefasst werden. Interessierte Leser seien dazu auch auf die vielen interessanten und teilweise dramatischen Berichten hingewiesen, die man bei der Suche im Internet nach Begriffen wie „Software-Fehler“, „Software-Problem“ oder deren englischen Varianten findet.
3
1 Motivation von Formalen Modellen
4
Nr. 1.
Jahr 1962
2.
1971
3.
1978
4.
1979
5.
1982
6.
1987
7.
1988
8.
1990
9.
1990
10.
1991
11.
1993
12.
1993
13.
1994
Vorfall Mariner 1, Cape Canevaral, Trägerrakete sprengt sich nach Kursabweichung selbst, Grund für die Abweichung war ein Komma statt eines Punktes im Quellcode Eole1, französischer Satellit zur Koordination von 141 Wetterballons; 72 Ballons erhalten Befehl vom Satelliten, Daten zu senden, interpretieren dies aber als Befehl zur Selbstzerstörung Amerikanisches Jagdflugzeug F16, im Simulationsbetrieb wird entdeckt, dass sich das Flugzeug beim Überfliegen des Äquators wegen eines Vorzeichenfehlers auf den Kopf dreht Programm zur Berechnung der Erdbebenfestigkeit amerikanischer Kernkraftwerke berechnet kritische Werte, was zu Umbaumaßnahmen führt; Ursache der kritischen Werte war das Berechnen der arithmetischen Summe statt der Wurzel aus der Quadratsumme Falkland Krieg, britische Fregatte Sheffield identifiziert anfliegenden argentinischen Flugkörper als freundlich, da er von einer befreundeten Nation hergestellt wurde; die Fregatte wurde zerstört Therac 25, Gerät zur medizinischen Strahlentherapie; durch die zu schnelle Eingabe wird die Bestrahlung ausgelöst, bevor die Positionierung abgeschlossen ist Airbus A 320, Absturz bei einer Flugshow, da die besondere Flugsituation mit niedriger Höhe und steilem Winkel nicht von der Software unterstützt wurde AT & T-Netzausfall, 60000 Menschen können mehrere Stunden nicht telefonieren, nachdem eine neue Software eingespielt wurde und sich die verbundenen Vermittlungsrechner gegenseitig im Domino-Effekt abschalteten Geldautomat, Person will Geld an einem Geldautomaten in Honolulu abheben, der zentrale Rechner zur Überprüfung steht in New Jersey, durch die Zeitverzögerung des Satellitensignals und einen Protokollfehler wird Geld nicht ausgezahlt und trotzdem abgebucht Flugabwehrsystem Patriot verfehlt im Golfkrieg anfliegende irakische Scud-Rakete; Problem war, dass die Zeit nur in einer einfach genauen Gleitkommazahl gespeichert wurde, was eine vergessene Korrektur der Zeit nach maximal 100 Stunden Laufzeit benötigte Pentium-Chip; durch einen Berechnungsfehler ist die Division bei diesem Chip ungenau, was sich erst mehrere Stellen hinter dem Komma auswirkt, allerdings zu einem sehr teuren Prozessoraustausch führt Programm zur Steuerberechnung in den USA berechnet wegen zwei Software-Fehlern Steuern falsch, das Programm war unter Steuerberatern weit verbreitet Mondsonde Clementine; nach dem erfolgreichen Fotografieren der Mondoberfläche sollte die Sonde einen Asteroiden ansteuern, durch einen Software-Fehler wurden die Triebwerke nach der Kurskorrektur nicht mehr abgestellt
1.2 Software-Fehler Nr. 14.
Jahr 1995
15.
1995
16.
1995
17.
1996
18.
1996
19.
1996
20.
1998
21.
1999
22.
1999
23.
1999
24.
2001
25.
2002
26.
2002
27.
2002
Vorfall Telefonnetz Singapur; 65% der Leitungen sind fünf Stunden nicht nutzbar, die restlichen stark überlastet, da sich Software-Fehler eines Vermittlungsknotens auf weitere Systeme fortpflanzte Automatischer Gepäcktransport am Flughafen Denver; der Start des neuen Flughafens verzögert sich um mehrere Monate, da das Zusammenspiel zwischen Soft- und Hardware (zu viele Steuerungsinformationen) zum vollautomatischen Gepäcktransport zum Verlust und zur Beschädigung des Gepäcks führt Bahnstellwerk Hamburg-Altona; durch einen Speicherüberlauf bei hohem Verkehrsaufkommen stürzt der Rechner ab; es werden drei Tage zur Reparatur benötigt Abrechnungssystem der Telecom erkennt 1. Januar nicht als Feiertag und rechnet falsch ab Ariane 5; Hauptrechner sendet unsinnige Befehle an Triebwerke, Rakete zerstört sich selbst, Problem war die ungeprüfte Übernahme von Software der Ariane 4, die für auftretende Beschleunigungen nicht konzipiert war Passwort-System Kerebos; durch einen Fehler in diesem Protokoll können die genutzten Zufallszahlen vorausberechnet werden, so dass ein Eindringen in die Systeme möglich wird; dieser Fehler existierte acht Jahre NEAR-Sonde; die Sonde soll zum Asteroiden Eros fliegen; die Zündung der Antriebsraketen für das Verlassen der Erdumlaufbahn wird von der Kontrollsoftware abgebrochen, um Fehlzündungen zu vermeiden; eine Korrektur der Software vom Boden aus gelang Mars Climate Orbiter; Marssonde geht in 170 km zu tiefe Umlaufbahn, so dass die Sonde abstürzt; die Entwickler der Software gingen von einem metrischen System mit Metern aus, das Navigationssystem erwartete Angaben im englischen System in Yards Mars Polar Lander; Landefahrzeug stürzt aus 40 Metern Höhe auf die Oberfläche; drei Sensoren hatten die Erschütterung beim Ausfahren der Landebeine als Bodenkontakt interpretiert Software des Wetterdienstes interpretiert schnellen Druckabfall als Messfehler, ohne Meteorologen zu informieren; die notwendige Sturmwarnung für Süddeutschland bleibt aus Fehlerhafte Krebsbestrahlung von Patienten; Bedienfehler waren von der Software nicht erkannt worden, wovon beim Konzept der Bedienoberfläche ausgegangen wurde Bomben AGM 154-A schlagen bei amerikanischer Irak-Bombardierung wegen Berechnungsfehler 15 bis 250 Meter zu weit links ein Berechnung der Delegiertenanzahl für Landesparteitag der Grünen in Baden-Württemberg scheitert durch Fehler in der Nutzung eines Tabellenkalkulationsprogramms; es werden 202 statt benötigter 200 Personen eingeladen Teilweiser Absturz des britischen Luftraumüberwachungssystems beim Versuch, aktualisierte Software in das System einzuspielen; Resultat waren deutliche Verzögerungen im Flugbetrieb
5
1 Motivation von Formalen Modellen Nr. 28.
Jahr 2003
29.
2003
30.
2003
31.
2004
32.
2004
33.
2005
34.
2005
35.
2005
36.
2005
37.
2005
38.
2007
39.
2008
40.
2008
41.
2009
42.
2009
Vorfall Flugabwehrsystem Patriot identifiziert in Kuwait befreundetes britisches Kampfflugzeug als Feind und schießt es ab Stromausfall in USA/Kanada; 50 Millionen Menschen ohne Strom, da die Software des Netzbetreibers auf eine große Lastschwankung des Netzes falsch reagierte Autobahn-Maut-System; Fehler im Zusammenspiel mit der Hardware; Anzeige mautfreier Strecke auf zu bezahlenden Strecken, Verweigerung, Eingaben anzunehmen im laufenden Betrieb, verschiedene Beträge auf gleichen Strecken bei gleichen Konditionen Rückruf von Mercedes-Transportern, da Software zur Dieselsteuerung die Kraftstoffzufuhr in unerwarteten Momenten drosselte, wodurch der Motor ausgehen konnte Mars-Rover Spirit; Probleme in der Steuerung des MarsUntersuchungsgerätes, da nach einiger Zeit das Dateiverwaltungssystem zu viel Speicher benötigt, was zu einem Reset des Systems führt Fehler in der Software zur Berechnung des Arbeitslosengeldes 2 der Bundesagentur für Arbeit, da unter falschen Annahmen die Krankenkassenzahlungen storniert wurden Fehler in der Software zur Berechnung des Arbeitslosengeldes 2 der Bundesagentur für Arbeit, Auszahlungen fanden nicht statt, da bei neunstelligen Kontonummern am Ende eine Null ergänzt wurde, um auf das gewünschte zehnstellige Format zu kommen Londoner Tower-Bridge für einen halben Tag nicht passierbar; durch einen Software-Fehler ist die Brücke nach dem Öffnen nicht schließbar Durch einen Software-Fehler bei der Weiterleitung von E-Mails eines Providers wird eine E-Mail eines Abgeordneten des sächsischen Landtages mehrere Tausend Mal an die Empfänger zugestellt Cryosat-Trägerrakete, durch einen Software-Fehler der neuen russischen Trägerrakete, bei dem ein Signal zum Abschalten der Triebwerke der zweiten Stufe nicht weiter geleitet wurde, stürzt die Rakete ab Die Tabellenkalkulation Excel 2007 zeigt bei Multiplikationen, die 65535 ergeben, z. B. 10.2*6425, den Wert 100000 an Die Eröffnung des fünften Terminals des Flughafens Heathrow verzögert sich und verzögert dann den Flugbetrieb wegen Problemen mit der Gepäckabfertigungssoftware Musikplayer mit dem Freescale MC13783-Prozessor, z. B. Zune von Microsoft, versagt am 31.12.2008 vollständig den Dienst, da es einen Fehler in der Schaltjahresberechnung gibt Bei der Umstellung der Bearbeitung der „Abwrackprämie“ werden durch Überlast verschiedenen Anträgen die gleichen Bearbeitungsnummern zugeteilt, so dass Betätigungsmails private Daten willkürlich verteilen Durch Fehler in der neuen Version einer Software zur Verwaltung der Handy-Nummern der Telecom kann ein Großteil der Nutzer das Handy für vier Stunden nicht nutzen
Abb. 1: Beispiele für Software-Fehler
6
1.3 Software-Engineering Abb. 1 ist zwar durchnummeriert, da die einzelnen Ereignisse noch genauer betrachtet werden sollen, aber natürlich hat sie keinen Anspruch auf Vollständigkeit, wobei sie aus einigen Quellen zusammengetragen wurde [@Jau], [@Spi], [@Gie], [@aeo], [@gol] und ein Schwerpunkt auf aktuelleren Problemen liegt. Da für die genannten Problemfälle nur selten der Quellcode bekannt wurde, ist kritisch zu bemerken, dass Software-Probleme natürlich auch vorgeschoben werden können und dass echte Fehler meist ihre Ursachen in ganz anderen Dingen, wie mangelnden Zeit- und Geldressourcen für Software-Tests, haben können. Neben den genannten markanten Beispielen sind schleichende Fehler in der ITBranche ein großes Problem. Dies sind Fehler, die nicht sofort zu einem Desaster führen, sondern dazu, dass eine sich langsam weiterentwickelnde Software immer schwieriger zu erweitern wird, bis letztendlich keine neuen Software-Versionen mehr ausgeliefert werden können. Beispielhaft sei aus eigener Erfahrung die Geschichte eines kleinen SoftwareUnternehmens genannt, das in der Nahrungsmittelbranche erfolgreich Lösungen zur Verwaltung des Einkaufs von Schlachtvieh über die Steuerung von Produktionsanlagen bis zur Auslieferung erstellte. Die erste Software wurde von wenigen Entwicklern mit großem Know-how in der Lebensmittelbranche entwickelt. Die Software wurde an wenige Kunden verkauft und vor Ort auf die individuellen Bedürfnisse angepasst. Dieser Weg war anfänglich sehr erfolgreich und führte zu hoher Kundenzufriedenheit. Mit steigender Kundenzahl wurden neue Module entwickelt, die zur existierenden Software passen mussten. Da es nicht nur eine Ausgangssoftware für Änderungen gab ƺ die kundenindividuellen Programme mussten ja weiterlaufen ƺ und da zentrale Informationen teilweise mehrfach im System gehalten wurden, stieg der Aufwand für jede neue Software-Entwicklung enorm. Letztendlich wurde die Software unwartbar, so dass Verträge nicht eingehalten wurden und das Unternehmen nach einem Verkauf geschlossen wurde. Aus modelltechnischer Sicht fehlte die Erkenntnis, dass man die Daten so strukturieren muss, dass es für jede Information nur eine Quelle geben darf und dass nur lokal benötigte Informationen für andere nicht sichtbar werden sollten. Mit einem Datenmodell, aus dem Abhängigkeiten von Daten ableitbar gewesen wären, hätte die Erweiterungsfähigkeit langfristig erhalten bleiben können.
1.3 Software-Engineering Um der steigenden Komplexität von Software-Systemen Herr zu werden, wurden verschiedene prozessorientierte Ansätze entwickelt, die Fehlerquellen minimieren, beziehungsweise zur frühzeitigen Entdeckung von Fehlern führen sollen. Dabei spielt die Erkenntnis, dass komplexe Abläufe systematisch als nachvollziehbare Prozesse aufbereitet werden müssen, eine zentrale Rolle. Die Erkenntnis, dass für jeden Arbeitsablauf klar sein muss,
7
1 Motivation von Formalen Modellen – – – –
was gemacht werden soll, wer verantwortlich ist, wer mitarbeitet, welche Voraussetzungen zur erfolgreichen Durchführung erfüllt sein müssen, – welche Hilfsmittel benötigt werden, – welche Alternativen es unter welchen Bedingungen bei der Arbeitsausführung gibt, – wie die Ergebnisse unter welchen Umständen aussehen sollen, wird auch in Unternehmen bei der Geschäftsprozessmodellierung [Gad03] genutzt. Software-Projekte stellen dann in Unternehmen Teilprozesse dar, die entweder zentral für den Unternehmenserfolg bei Software-Produzenten oder wichtiges Hilfsmittel bei der IT-gestützten Verwaltung sind.
Inkrement 1
Inkrement 2
Inkrement 3
Anforderungsanalyse Design
Anforderungsanalyse
Implementierung Test
Design Implementierung
Teilabnahme
Test Teilabnahme
Anforderungsanalyse Design Implementierung Test Abnahme
Abb. 2: Inkrementelle Entwicklung In einem sehr allgemeinen Vorgehen kann man die Software-Entwicklung in die folgenden Phasen aufteilen [Kle09]: Es beginnt mit der Anforderungsanalyse, in der ein Analytiker versucht, mit dem Kunden die Aufgaben des zu erstellenden Systems zu präzisieren. Dieser Schritt ist maßgeblich für die Qualität des Projektergebnisses, da alle folgenden Arbeitsschritte von der Anforderungsanalyse abhängen. Neben den funktionalen Aufgaben sind weitere Randbedingungen zu klären, wie die Hardware, auf der das zu
8
1.3 Software-Engineering entwickelnde System laufen soll, und mit welcher anderen Software des Kunden das neue System zusammen arbeiten muss. Typischerweise findet im nächsten Schritt nicht direkt eine Implementierung statt. Stattdessen wird das zu entwickelnde System zunächst vom Designer im Systemdesign geplant. Die Planungen beinhalten z. B. die Aufteilung der zu erstellenden Software in kleinere Teilsysteme, die von fast unabhängig arbeitenden Implementierern realisiert werden sollen. Weiterhin ist zu entscheiden, welche Mittel überhaupt eingesetzt werden, um eine Erfüllung der technischen Anforderungen zu ermöglichen. In der Implementierungsphase findet die Programmierung statt. Dabei werden meist schrittweise kleine Teilprogramme zu einem großen Programm integriert. Die Entwickler führen dabei für die von ihnen erstellten Programmteile kleine Tests aus, die auch das Zusammenspiel mit anderen Teilen betrachten. In der eigentlichen Testphase wird mit verschiedenen Testfällen geprüft, ob das entwickelte System wirklich die Kundenanforderungen erfüllt. Dabei wird validiert, ob typische Arbeitsabläufe möglich sind und ob auch Grenzsituationen und Fehleingaben korrekt behandelt werden. Danach wird das System dem Kunden vorgeführt, der es selber testet und nach einem erfolgreichen Test die Abnahme durchführt. Es folgt dann die Garantiephase, in der die Entwicklung gefundene Fehler beheben muss. Der beschriebene Entwicklungsprozess wird Wasserfallmodell genannt. In der Realität ist es meist nicht möglich, die Phasen konsequent nacheinander abzuarbeiten. Grundsätzlich muss es bei gefundenen Problemen möglich sein, in frühere Phasen zurück zu springen. Ein wesentliches Problem komplexer Systeme ist, dass man am Anfang nicht hundertprozentig weiß, was das System letztendlich können soll. Es ist schwierig, Anforderungen so präzise zu formulieren, dass genau das Ergebnis heraus kommt, das der Ersteller der Anforderungen wirklich wünscht. Weiterhin ist es typisch, dass sich im Laufe eines längeren Projekts Anforderungen des Kunden ändern, da sich Randbedingungen im Unternehmen verändern oder weitere Wünsche erst später entdeckt werden. Das Ziel eines Software-Entwicklungsprojekts ist es, den Kunden im ausgehandelten Finanzrahmen zufrieden zu stellen. Aus diesem Grund ist es wichtig, auf sich ändernde Anforderungen im Laufe der Entwicklung reagieren zu können. Es gibt verschiedene Entwicklungsmethoden, die diese Herausforderung angehen. Ein Lösungsansatz ist die in Abb. 2 skizzierte inkrementelle Entwicklung, dabei wird die Entwicklung in mehrere Phasen zerlegt, wobei jede der Phasen die Schritte des Wasserfallmodells durchläuft. Teilaufgaben des zu entwickelnden Systems, die noch unklar sind, werden in späteren Inkrementen realisiert. In Folgeinkrementen ist es auch möglich, auf sich ändernde Nutzeranforderungen oder verän-
9
1 Motivation von Formalen Modellen derte technische Randbedingungen zu reagieren. Ein Folgeinkrement kann meist schon vor dem endgültigen Abschluss des vorherigen Inkrements begonnen werden. In [Bal00] findet man einen Überblick über verschiedene SoftwareEntwicklungsprozesse, die zeigen, dass die Reaktionsmöglichkeit auf geänderte Anforderungen ein wichtiges Prozessqualitätsmerkmal ist. Formale Modelle können in verschiedenen Phasen der Entwicklung hilfreich sein. Bei der Anforderungsanalyse kann man Logiken nutzen, um Anforderungen exakt zu formulieren. In der Design-Phase werden Modelle eingesetzt, um Erfahrungen mit dem später zu implementierenden System zu machen. Diese Erfahrungen können die Korrektheit eines neu entwickelten Verfahrens bezüglich bestimmter Anforderungen oder auch Abschätzungen über ein mögliches Laufzeitverhalten beinhalten. Für die Korrektheit ist es teilweise möglich nachzuweisen, dass ein Modell die in einer Logik formulierten Anforderungen erfüllt. Damit dieser Nachweis automatisch erfolgen kann, müssen die Logik und das Modell einige Randbedingungen erfüllen, da das Problem für beliebige Logiken und Modelle unentscheidbar ist. Generell muss man im Hinterkopf behalten, dass es beweisbar ist, dass man kein Programm schreiben kann, das für ein Modell und eine Logik die Frage beantwortet, ob das Modell eine Anforderung in der Logik erfüllt oder nicht [VW04]. Logische Formeln können auch zur Beschreibung von Vor- und Nachbedingungen für Implementierungen genutzt werden. Damit kann formal nachgewiesen werden, dass das Programm eine geforderte Eigenschaft erfüllt. Formale Modelle sind damit ein zentraler Schritt auf dem Weg zu besserer Software. Automatische Beweise können, wenn sie einsetzbar sind, Testverfahren vollständig überflüssig machen. Beweise garantieren die Abwesenheit von Fehlern, Tests können nur für die untersuchten Fälle garantieren, dass keine Fehler vorhanden sind, Fehlerfreiheit lässt sich so nicht garantieren. Für größere Projekte gibt es allerdings keine Konkurrenz zwischen klassischen Verfahren der Qualitätssicherung und dem Einsatz von Formalen Modellen. Formale Modelle sind eine wichtige Ergänzung im Werkzeugpaket der qualitätssichernden Maßnahmen. Auf der einen Seite müssen für die Formalen Modelle selbst qualitätssichernde Maßnahmen betrieben werden. So muss z. B. durch Reviews mit Experten sichergestellt werden, dass Anforderungen auch das ausdrücken, was der Kunde wünscht, und dass ein Modell zur gewünschten Lösung passt. Auf der anderen Seite kann der Einsatz Formaler Modelle relativ zeitaufwändig sein, so dass man aus betriebswirtschaftlicher Sicht unter Berücksichtigung des Ausmaßes möglicher Fehler entscheiden muss, ob man nur klassische qualitätssichernde Maßnahmen einsetzt oder auch Formale Modelle nutzt.
10
1.4 Fragen
1.4 Fragen Wiederholungsfragen Versuchen Sie zur Wiederholung folgende Fragen aus dem Kopf, d. h. ohne nochmaliges Blättern und Lesen, zu beantworten. 1.
Was versteht man unter einem Modell für die Softwareentwicklung?
2.
Welche Ursachen können Softwarefehler haben?
3.
An welche Softwarefehler erinnern Sie sich unabhängig von der Lektüre dieses Buches?
4.
Welche Informationen benötigt man zur Beschreibung eines Arbeitsprozesses?
5.
Was versteht man unter inkrementeller Entwicklung, warum kann sie helfen, Fehler zu reduzieren?
6.
Welche Rollen können Formale Modelle in der Software-Entwicklung spielen?
Übungsaufgaben 1) Teilen Sie die in der vorgestellten SW-Fehler in unterschiedliche Einsatzbereiche bzw. Unternehmensgebiete auf (z. B. Verteidigung). 2) Kann man trotz der recht willkürlichen Auswahl der Fehler Erkenntnisse aus der Gruppierung aus 1) gewinnen? 3) Wenn man die Fehler in genau ansieht, kann man in zwei Fällen feststellen, dass die Korrektur eines Fehlers eines Systems eventuell zu einem anderen genannten Fehler in einem anderen System geführt hat. Welche Fälle sind gemeint, was für ein Problem kann dahinter stecken? 4) Welche dramatischen Konsequenzen können Software-Fehler haben?
11
2 Modelchecking mit PROMELA und SPIN Generell besteht der Wunsch, dass die Korrektheit eines Programms automatisch geprüft werden kann. Dabei muss zunächst geklärt werden, was mit Korrektheit gemeint ist. Dies wird in diesem Kapitel durch Anforderungen präzisiert, die ein Programm erfüllen soll. Aus theoretischer Sicht weiß man, dass ein allgemeines Verfahren, die Korrektheit von Programmen bezüglich gegebener Anforderungen zu zeigen, durch die Nichtentscheidbarkeit vieler Probleme generell nicht möglich ist. Auch aus praktischer Sicht stellt sich die Frage, wie man dies bei all den möglichen Zuständen einer komplexen Software in den Griff bekommen kann. In diesem Kapitel sehen wir, dass man einiges in den Griff bekommt, wenn man es schafft, ein einfaches passendes Modell zu einer Aufgabenstellung zu finden. Auch das Problem mit den eventuell unendlich vielen möglichen Zuständen kann man lösen, wenn man sicher ist, dass nur endlich viele dieser Zustände interessant sind. Modelchecking erlaubt die Analyse großer Zustandsmengen und nutzt den folgenden Ansatz: Gegeben sind ein Modell und eine Anforderung, dann überprüft der Modelchecking-Algorithmus, ob das Modell die Anforderung erfüllt oder nicht. Falls das Modell die Anforderung nicht erfüllt, sollte der Algorithmus ein Gegenbeispiel liefern. Die Umsetzung erster Modelchecking-Ideen [Pnu77] [WVS83], [CES86], [BCM90], die sich auf Ende der 1970er Jahre datieren lassen, fand Mitte der 1980er Jahre statt, da es ab dann neben der Theorie für diesen Ansatz auch verfügbare Computer gab, mit denen große Zustandsräume durchsucht werden konnten. Die grundlegenden Arbeiten von Clarke, Emerson und Sifakis wurden u. a. in 2007 mit der renommiertesten Auszeichnung im Informatik-Umfeld, dem Turing Award, ausgezeichnet. Für die praktische Nutzbarkeit spielt neben der wesentlichen Effizienz des Modelchecking-Verfahrens die möglichst einfache Modellierungssprache, d. h. eine möglichst einfache Sprache zur Formulierung der Modelle und Anforderungen sowie ihre Integration in einem bedienbaren Werkzeug, eine wichtige Rolle. Als erstes Werkzeug wird hier SPIN (Simple PROMELA Interpreter) [Hol04] vorgestellt, das von Gerard Holzmann 1991 veröffentlicht [Hol91] und seitdem kontinuierlich verbessert wurde. Das Werkzeug steht auf der zugehörigen Internetseite [@SPI] mit Installationsanleitungen und vielen weiteren Informationen frei zur Verfügung. Einige Installationsdetails sind im Anhang A.1 zusammengefasst. Holzmann hat mit diesem Werkzeug 2001 den renommierten ACM Software System Award gewonnen, der z. B. 1983 von UNIX, 1987 von Smalltalk, 1991 von TCP/IP, 1995 vom World-Wide Web und 2002 von Java gewonnen wurde [@ACM].
13
2 Modelchecking mit PROMELA und SPIN SPIN ist auch aus einem anderen Gesichtspunkt interessant, da es neben der Verifikationskomponente auch die Möglichkeit zur Simulation der erstellten Modelle gibt. Mit PROMELA steht eine mächtige Spezifikationssprache zur Verfügung, mit der nichtdeterministische, kommunizierende verteilte Systeme spezifiziert werden können. Wichtig ist dabei, dass eine Spezifikationssprache verschiedene Sprachelemente anbietet. Der Nutzer muss entscheiden, ob die angebotenen Ansätze für seine praktische Aufgabenstellung nutzbar sind oder nicht. Kann man z. B. in der Zielimplementierung keine gemeinsamen Variablen für verteilte Prozesse nutzen, sollte man intensiv darüber nachdenken, ob man diese Möglichkeit in der Spezifikation nutzt. Weiterhin werden wir sehen, dass man auch klassische deterministische Programme als Spezialfall in PROMELA beschreiben kann. Im folgenden Abschnitt wird zunächst beschrieben, welche Bedeutung Modelchecking im Rahmen der Software-Entwicklung haben kann. Danach wird die zu SPIN gehörige Spezifikationssprache PROMELA (Process Meta Language) vorgestellt und gezeigt, wie sie zunächst in Simulationen genutzt werden kann. Die Formalisierung von Anforderungen findet in einer temporalen Logik statt, die dann eingeführt wird. Abschließend werden mehrere Fallstudien diskutiert und die Verwandtschaft zur Spezifikationssprache SDL gezeigt.
2.1 Modelchecking im Entwicklungskontext möglicher Arbeitsweg potenzielle Fehlerquelle abgesicherter Weg
Aufgabenstellung unzulässige Interpretation
unpräzise Aufgabenstellung
Lösungsidee fehlerhafte Formalisierung Anforderungen Modelchecking
unpassendes Modell zu starke Vereinfachung
Modell
Programm Transformation
Abb. 3: Fehlerquellen der Programmentwicklung
14
Programmierfehler
2.1 Modelchecking im Entwicklungskontext Um zu verstehen, welche Möglichkeiten das Modelchecking bietet und welche Probleme trotzdem bleiben, ist es hilfreich, Abb. 3 zu analysieren. Die einfachen durchgezogenen Pfeile zeigen mögliche Arbeitswege in der Software-Entwicklung. Ausgehend von der Aufgabenstellung wird eine Lösungsidee entwickelt, die dann z. B. direkt in einem Programm ausprogrammiert wird. In einem formaleren Weg werden, ausgehend von den Ideen, Anforderungen formalisiert, die zur Überprüfung des Programms genutzt werden. Da es oft eine sehr große Herausforderung ist, nicht-triviale Programme zu verifizieren, wie später noch gezeigt wird, wird jetzt zusätzlich ein Modell für die erdachte Lösung erstellt. Dieses Modell wird entweder aus der Lösungsidee entwickelt oder aus dem existierenden Programm abgeleitet. In einem Spezialfall kann man das Programm selbst als das Modell auffassen. Dies ist nur bei einfachen Programmen möglich, da ein Modell handhabbar sein soll und so auf zu untersuchende kritische Elemente reduziert wird. Durch Modelchecking ist es möglich, automatisch nachzuprüfen, ob ein Modell die formulierten Anforderungen erfüllt. Wie ein solches Modell und die Anforderungen beschrieben werden, ist Schwerpunkt der folgenden Unterkapitel. Die Verknüpfung zwischen Modell und Anforderungen ist in Abb. 3 fett eingezeichnet. Ein zweiter dicker Pfeil zeigt die häufig gegebene Möglichkeit, ein Modell automatisch in ein Programm zu übersetzen, genauer: zu transformieren. Dieser Transformationsschritt, der für verschiedene Modellierungssprachen möglich ist, wird in diesem Buch nicht weiter betrachtet, da er stark davon abhängt, welche ZielProgrammiersprache und Ziel-Hardware das Projekt hat. Durch die gestrichelten Pfeile in Abb. 3 sind mögliche Fehlerquellen angedeutet. Dabei wird sichtbar, dass Modelchecking kein Allheilmittel sein kann, da auch als korrekt bewiesene Modelle im Sinn der Aufgabenstellung fehlerhaft sein können. Die erste zentrale Fehlerquelle ist die Umsetzung der Aufgabenstellung in die Lösungsidee, die in der Praxis meist den kritischsten Teil eines Projekts ausmacht. Projekte scheitern häufig, da dem Kunden unklar ist, was im Detail seine Forderungen sind. Diese Fehlerquelle wird verstärkt, wenn auf Entwicklerseite nicht im Detail nachgefragt wird und Annahmen über das zu entwickelnde System gemacht werden, die unzutreffend sind. Eine weitere gravierende Fehlerquelle sind klassische Programmierfehler, die z. B. auf vergessenen Ablaufalternativen beruhen. Auch bei der Formulierung von Anforderungen und Modellen können Fehler auftreten, so dass jeweils Experten für den Arbeitsschritt benötigt werden. Ist z. B. jemand nicht in der Lage, die Anforderungen korrekt in der für den Modelchecker genutzten Logik auszudrücken, haben die nachgewiesenen Anforderungen wenig Aussagekraft. Im schlimmsten Fall werden Anforderungen falsch in Logik umgesetzt, diese falschen Formeln als erfüllt nachgewiesen und dann, basierend auf der vermeintlich nachgewiesenen Anforderung, kritische Entscheidungen getroffen. Auch bei der Modellierung selbst können Fehler auftreten, so dass man sich bei jedem gescheiterten Modelchecking auch fragen muss, ob das Modell und die An-
15
2 Modelchecking mit PROMELA und SPIN forderungen korrekt sind. Leider ist auch der andere Weg möglich, dass eine Anforderung falsch umgesetzt und dann als korrekt bewiesen wird. Eine letzte in der Abbildung nicht eingezeichnete Fehlerquelle stellt natürlich die Möglichkeit eines fehlerhaften Modelcheckers oder fehlerhafter Transformationen dar. Die typische Antwort auf die Frage „wer prüft den Prüfer“ stellt dabei der pragmatische Ansatz dar, dass ein über lange Zeit funktionierendes Prüfverfahren „wohl“ wenig Fehler aufweisen wird. Der theoretisch für andere Systeme verfolgte Ansatz, dass ein Werkzeug zur Prüfung der eigenen Algorithmen genutzt wird, wird für SPIN nicht verfolgt.
2.2 Die Spezifikationssprache PROMELA Für eine Spezifikationssprache, die zum Modelchecking genutzt werden soll, kann man zwei zentrale Forderungen formulieren: 1. Die Modelle sollten möglichst einfach beschreibbar sein. 2. Die Modelle sollten möglichst klein sein. Um die Gefahr falscher Modelle zu reduzieren, ist die Spezifikationssprache PROMELA (PROcess MEta LAnguage) an einfache Programmiersprachen angelehnt. Einzelne Programmkonstrukte sind aus der Programmiersprache C entnommen. Damit die Modelle bei der Untersuchung klein bleiben, muss für Variablen der Datentyp möglichst genau festgelegt werden, dabei spielt jedes eventuell überflüssige Bit eine Rolle. PROMELA wird u. a. zur Spezifikation von Kommunikationsprotokollen eingesetzt, weiterhin eignet sich die Sprache sehr gut zur Modellierung verteilter Systeme oder paralleler Algorithmen, die gemeinsame Variablen nutzen. Sie wurde um spezielle Möglichkeiten zur Kommunikation zwischen den Prozessen durch verschiedene Varianten von Kommunikationskanälen erweitert. In diesem Buch werden zentrale Sprachelemente von PROMELA vorgestellt; weitere Möglichkeiten und noch weiterführende Diskussionen können [Hol04] entnommen werden. Eine weitere Variante einer Einführung befindet sich in [Ben08]. Zur Einführung werden jetzt kleine Spezifikationen betrachtet, die vielleicht nicht typisch für das Einsatzgebiet von PROMELA sind, aber wesentlich zum Verständnis der Sprache beitragen. Die Spezifikation in Abb. 4 beinhaltet drei Prozesse, deren Aufgabe es ist, die Summe der ersten N ganzen Zahlen zu berechnen. Im Beispiel gibt es einen StartProzess, der mit dem Schlüsselwort init gekennzeichnet ist. Durch das Schlüsselwort run ist es möglich, Prozesse zu starten. Im Beispiel gibt es einen Prozess, der die ungeraden Zahlen, und einen zweiten Prozess, der die geraden Zahlen aufsummieren soll.
16
2.2 Die Spezifikationssprache PROMELA #define N 20 int erg; proctype Ungerade(){ int x=1; do :: x<=N -> erg=erg+x; x=x+2 :: x>N -> break od } proctype Gerade(){ int x=0; do :: x<=N -> erg=erg+x; x=x+2 :: x>N -> break od } init{ erg=0; run Ungerade(); run Gerade() }
Abb. 4: Erste Beispielspezifikation in PROMELA Oberhalb der einzelnen Prozessdefinitionen werden gemeinsame Eigenschaften für alle Prozesse festgehalten. Konstanten können wie in C mit dem Makro-Befehl #define definiert werden. Bei der späteren Ausführung wird der Text, hier N, durch den folgenden Text, hier 20, ersetzt. Datentyp bit bool byte chan mtype pid short int unsigned
Wertebereich 0..1 0..1 0..255 1..255 1..255 0...255 -215..215-1 -231..231-1 0..2<Wert>-1
Anmerkung auch Werte true (==1) und false (==0) möglich Kommunikationskanäle (später) Nachrichtenwerte (später) für Prozessidentifikatoren (später)
Anzahl Bits <Wert> wird angegeben, z.B. unsigned x:5; Variable hat dann Maximalwert 31
Abb. 5: Basisdatentypen in PROMELA
17
2 Modelchecking mit PROMELA und SPIN Die globale Variable erg hat den Typen int. Insgesamt stehen die in Abb. 5 angegebenen Typen zur Verfügung. Die Möglichkeit, weitere Typen zu definieren, wird später vorgestellt. Die Wahl eines Typs, der möglichst wenig Speicherplatz verbraucht, ist in den Modellen sehr wichtig, da sich die Anzahl der benötigten Bytes unmittelbar auf den bei der Verifikation genutzen Speicher auswirkt. Der Modelchecking-Algorithmus überprüft dabei alle erreichbaren Kombinationen von Variablenwerten. Innerhalb der Prozesse können lokale Variablen am Prozessanfang definiert werden, globale Variablen stehen außerhalb der Prozessspezifikationen. Eine Besonderheit stellen die Schleifen und Bedingungen in PROMELA da, deren Syntax auf einen Vorschlag von Dijkstra [Dij76] mit seiner Guarded Command Language zurückgeht. Innerhalb der Schleife kann es mehrere Alternativen geben, die durch :: am Anfang gekennzeichnet sind. Bei der Ausführung wird zunächst für jede der Alternativen festgestellt, ob sie ausführbar ist. Dabei sind Boolesche Bedingungen nur ausführbar, wenn sie mit den aktuellen Variablenwerten nach wahr ausgewertet werden können. Andere Anweisungen wie Zuweisungen sind immer ausführbar. Sind mehrere Alternativen ausführbar, so wird nichtdeterministisch eine zur Ausführung gewählt. Für das Modell ist dieser Ansatz sehr flexibel, da so viele mögliche Abläufe ohne besonderen Aufwand spezifiziert werden können. Beim Modelchecking später werden dann alle möglichen Alternativen untersucht. Im konkreten Beispiel wird der Nichtdeterminismus allerdings nicht genutzt, da sich die beiden Booleschen Bedingungen gegenseitig ausschließen. Dies Beispiel zeigt bereits, wie man eine klassische while-Schleife mit while(x<=N) in die do-Schleife in PROMELA übersetzen kann. Typischerweise steht am Anfang einer Alternative eine Boolesche Bedingung. Solche Bedingungen werden nicht nur geprüft, sie können auch die Ausführung verzögern. Das Spezifikationsstück x<4; x>5; erg=42
bedeutet, dass zunächst gewartet wird, bis x einen Wert kleiner 4, und dann, bis x einen Wert größer 5 annimmt. Erst dann wird erg der Wert 42 zugewiesen. Man sagt deshalb, dass eine Boolesche Bedingung ausführbar ist, wenn sie mit den aktuellen Variablenwerten nach wahr ausgewertet werden kann. Im Beispiel und bei den Bedingungen fällt auf, dass am Ende der letzten Zeile kein Semikolon steht. Dieser Ansatz geht auf klassische Programmiersprachen wie Pascal zurück, bei denen ein Semikolon nur stehen muss, um Anweisungen voneinander zu trennen. Da Programmiersprachen ab C hinter jedem Befehl ein Semikolon verlangen, wurde diese Möglichkeit auch in PROMELA eingefügt, so dass man semantisch äquivalent redundant jeweils ein Semikolon nach jedem Befehl setzen könnte.
18
2.2 Die Spezifikationssprache PROMELA Boolesche Bedingungen werden typischerweise von links nach rechts ausgewertet, bei Zuweisungen wird zunächst die rechte Seite berechnet und dann der Wert der Variablen auf der linken Seite zugewiesen. Um Klammern bei der Formulierung von Ausdrücken zu sparen, gibt es Prioritäten zwischen den Operatoren. Operatoren mit höherer Priorität werden vor den Operatoren niedriger Priorität ausgewertet. Bei gleicher Priorität findet die Auswertung von links nach rechts statt. In Abb. 6 sind die Prioritäten in PROMELA festgehalten, dabei steht eine niedrige Nummer für eine höhere Priorität. Ein Boolescher Ausdruck der Form a || b && c steht z. B. für a || (b && c), wobei es natürlich erlaubt ist, immer Klammern zu setzen, um zu verdeutlichen, welche Auswertungsreihenfolge gemeint ist. Priorität 1 2 3 4 5 6 7 8 9 10 11 12
Operator () [] . ! ~ * / % + << >> < <= > >= == != & | && || =
Kommentar Klammern, Feldklammern, Teilkomponente Negation, Bit-Komplement Multiplikation, Division, Modulo Addition, Subtraktion bitweiser Links- und Recht-Shift kleiner, kleiner-gleich, größer, größer-gleich Gleichheit, Ungleichheit bitweise Und bitweise Oder logisches Und logisches Oder Zuweisung
Abb. 6: Prioritäten von Booleschen Operatoren in PROMELA In Schleifen stellen Boolesche Bedingungen Wächter dar: nur wenn sie erfüllt sind, können die nachfolgenden Anweisungen ausgeführt werden. Man beachte dabei das potenzielle Problem, dass :: x==1 bedeutet, dass die Alternative nur dann auswählbar ist, wenn x den Wert 1 hat, dass aber :: x=1 immer ausführbar ist, x den Wert 1 bekommt und dann die nachfolgenden Anweisungen ausgeführt werden. Aus den Ausführungen folgt, dass der Pfeil hinter den Booleschen Wächtern, der auf die folgende Anweisung zeigt, auch durch ein Semikolon ersetzt werden könnte. Wurde eine Schleifenalternative abgearbeitet, wird die Schleife erneut mit einer Überprüfung der Wächter ausgeführt. Schleifen werden durch den break-Befehl verlassen. Betrachtet man die beiden Prozesse Ungerade und Gerade, fällt ihre starke Ähnlichkeit auf. Für Spezifikationen wie für Programmiersprachen gilt, dass man nichts doppelt beschreiben soll. Abb. 7 zeigt eine Vereinfachung der Spezifikation;
19
2 Modelchecking mit PROMELA und SPIN man sieht, dass Prozesse Parameter haben können. Parameter werden Call by Value übergeben, sind also echte Kopien. #define N 20 int erg; proctype Summiere(int start){ int x=start; do :: x<=N -> erg=erg+x; x=x+2 :: x>N -> break od } init{ erg=0; run Summiere(1); run Summiere(0) }
Abb. 7: Optimierte Summenberechnung #define PROZESSE 2 byte x=0; byte y; active [PROZESSE] proctype ifdoSpiel(){ do :: x<10 -> x=x+1 :: (x>0 && x<10) -> x=x-1 :: x<9 -> x=x+3 :: else -> x=x+4; break od; if :: x<10 -> y=0 :: x>=10 && x<15 -> y=1 :: else -> y=2 fi; nochmal: if :: x<10 && y>0 -> goto nochmal :: else -> skip fi }
Abb. 8: Veranschaulichung von do und if
20
2.2 Die Spezifikationssprache PROMELA Die Spezifikation in Abb. 8 zeigt einige weitere Sprachkonstrukte von PROMELA und veranschaulicht das nichtdeterministische Verhalten von do und if. Prozesse können einmal über den Befehl run gestartet werden. Möchte man, dass ein Prozess bereits am Anfang der Spezifikationsausführung läuft, wird der Prozess mit dem Schlüsselwort active gekennzeichnet. Nach active kann in eckigen Klammern stehen, wie viele dieser Prozesse gestartet werden können. Hier sind es zwei. Beim do sind alle Alternativen mit dem Symbol :: gekennzeichnet. Grundsätzlich wird wieder für jede Alternative geprüft, ob der erste Befehl ausführbar ist, hier, ob die Boolesche Bedingung nach wahr ausgewertet werden kann. Einen Spezialfall stellt die mit else markierte Alternative dar. Diese kann nur dann ausgewählt werden, wenn alle anderen Alternativen nicht ausführbar sind. Die Schleife kann nur durch den break-Befehl verlassen werden, sonst wird nach Ausführung der Alternative auch beim else-Zweig immer wieder zum Anfang der do-Schleife zurückgegangen. Das if verhält sich sehr ähnlich wie das do, nur wird nach Beendung der Alternative mit der Spezifikation nach dem fi fortgefahren. Das letzte if zeigt noch eine Möglichkeit, die einen erfahrenen Programmierer erschaudern lässt; es gibt einen goto-Befehl, mit dem man zu einer mit einer eindeutigen Markierung gekennzeichneten Zeile springen kann. Dabei ist zu beachten, dass es sich hierbei um eine Spezifikation handelt, die möglichst kompakt sein soll, weiterhin können die Markierungen noch weitere Bedeutungen haben, was in späteren Abschnitten erläutert wird. Trotzdem sollte man goto nur mit Bedacht einsetzen. Das Beispiel zeigt, wie man mit einer Markierung nochmal und einem goto auch eine Schleife spezifizieren kann. Der Befehl skip, der nichts macht, kann in Spezifikationen genutzt werden, um z. B. aus Alternativen, wie im Beispiel gezeigt, herauszuspringen. Der Befehl goto wird relevant, wenn man z. B. aus einer anderen Beschreibungssprache eine automatische Übersetzung nach PROMELA durchführen möchte. Bei einer genaueren Analyse der Spezifikation ist es interessant, die Zahl der Prozesse zu kennen. Gibt es nur einen Prozess, so kann mit den ersten beiden Alternativen innerhalb der do-Schleife durch mehrere Durchläufe der Wert von x beliebige Werte zwischen 1 und 10 annehmen; weiterhin ist hier Divergenz möglich, was bedeutet, dass die Schleife nicht verlassen werden muss. Die dritte Alternative kann für x<9 ebenfalls immer gewählt werden und ist besonders für Fälle interessant, bei denen x vor der Auswahl einen Wert größer-gleich 7 hat. In diesem Fall ist nach Ausführung der Alternative der Wert von x größer-gleich 10, wodurch dann nur noch der else-Zweig genutzt und die Schleife beendet wird. Wird die Schleife verlassen, hat x entweder den Wert 14 oder den Wert 15. Das erste if verhält sich deterministisch, es wird abhängig von x einer der letzten beiden Fälle ausgeführt. Auch das zweite if ist deterministisch, es kann nur der else-Zweig ausgeführt werden, so dass der Prozess terminiert.
21
2 Modelchecking mit PROMELA und SPIN
Prozess 1 . . . nächste Anweisung: do Auswahl: (x>0 && x<10) nächste Anweisung: x=x-1
x=7
x=10
4-mal
x=x-1 nächste Anweisung: do Auswahl: (x>0 && x<10) x=x-1
nächste Anweisung: do
nächste Anweisung: do Auswahl: x<9 x=x+3 nächste Anweisung: do nur else wählbar else nächste Anweisung: x=x+4
x=9 x=8 x=7 x=6 x=5 x=9
Prozess bleibt in der Schleife und kann x weiter verändern
Prozess 2 . . .
x=x+4 break Schleife terminiert
Abb. 9: Einfluss verteilter Ausführung Hat man mehr als einen Prozess, so ist das Verhalten der letzten beiden if-Blöcke durchaus spannender. Es kann passieren, dass nur eine der do-Schleifen terminiert, aber andere do-Schleifen weiter laufen und den x-Wert verändern, wie es in Abb. 9 dargestellt ist. Es gibt zwei Prozesse, die nach einem Ablauf den Wert von x auf sieben gesetzt haben und sich beide am Anfang der do-Schleife befinden. Beide nutzen eine unterschiedliche ausführbare Variante, und der Prozess 2 schreitet voran. Der zweite Prozess geht mit dem Wert sieben in die dritte Alternative und führt x=x+3 aus, dann geht dieser Prozess in den else-Zweig und steht vor x=x+4. Der erste Prozess führt dann x=x-1 aus, so dass x den Wert neun erhält. Danach geht dieser Prozess vier Mal in die zweite Alternative, so dass x den Wert fünf hat. Dann führt der zweite Prozess x=x+4 aus und verlässt seine Schleife. Danach kann der erste Prozess x wieder im Wertebereich von null bis zehn ändern. Letztendlich kann durch den beschriebenen Ablauf die do-Schleife des Prozesses 2 terminieren,
22
2.2 Die Spezifikationssprache PROMELA während der erste Prozess den Wert von x noch innerhalb der Schleife weiter verändern kann. Die enge Kopplung zwischen x- und y-Wert geht also verloren, so dass beim letzten if auch die erste Alternative ausführbar wird und zu divergentem Verhalten führen kann. In einer anderen Alternative können zwei Prozesse mit dem Wert 11 für x in den else-Teil der Schleife gehen, so dass für beide Prozesse die Schleife terminiert und x den Wert 19 hat. #define ANZAHL 3 mtype = {sekt,wodka,osaft,bier}; mtype = {whisky,wasser}; bool wodkaO=false; typedef Person{ short id; mtype trinkt }; Person nase[ANZAHL]; typedef Kommuniziert{ Person p[2] }; Kommuniziert party[3]; active proctype leben(){ byte i=0; do :: i nase[i].id=i; nase[i].trinkt=i+1; i=i+1 :: else -> break od; i=0; do :: i party[i].p[0].id=nase[i].id; party[i].p[0].trinkt=nase[i].trinkt; party[i].p[1].id=nase[(i+1)%ANZAHL].id; party[i].p[1].trinkt=nase[(i+1)%ANZAHL].trinkt; i=i+1 :: else -> break od; i=0; do :: i if :: (party[i].p[0].trinkt==wodka && party[i].p[1].trinkt==osaft
23
2 Modelchecking mit PROMELA und SPIN || party[i].p[1].trinkt==wodka && party[i].p[0].trinkt==osaft) -> wodkaO=true :: else -> skip fi; i=i+1; :: else -> break od }
Abb. 10: Datentypen in PROMELA Die Spezifikation in Abb. 10 zeigt beispielhaft weitere Möglichkeiten, selbst Datentypen zu definieren. In den später betrachteten Kommunikationsprotokollen können z. B. Nachrichten ausgetauscht werden, die häufig aus einem Nachrichtennamen und den zu übermittelnden Werten bestehen. Die Nachrichtennamen können in einem Aufzählungstyp mtype zusammengefasst werden. Dabei gibt es nur diesen einzigen Aufzählungstyp, der maximal 255 Werte enthalten kann, die keine Schlüsselwörter von PROMELA sein dürfen. Man kann sich diesen Typ als Aufzählungstyp (Enumeration) vorstellen, dabei kann die Definition, wie im Beispiel gezeigt, über mehrere Teildefinitionen verteilt sein. Vom Typ mtype können dann Variablen deklariert werden, so wäre im Beispiel mtype getraenk=wasser;
möglich. Wie in Aufzählungen auch, sind die Werte durchnummeriert und können auch durch byte-Werte angesprochen werden. Als Besonderheit beginnt die Nummerierung mit eins, und die einzelnen Werte werden von rechts nach links durchnummeriert. Die Definition oben hätte also auch mtype getraenk=5; sein können. Ähnlich wie in C oder Sprachen wie Pascal kann man strukturierte Datentypen, auch Records genannt, definieren. Im Beispiel wird ein neuer Datentyp Person definiert, der zwei Attribute id und trinkt hat. Auf die einzelnen Attribute kann mit der Punktnotation . zugegriffen werden. Selbst definierte Datentypen können wieder in neuen Typen genutzt werden. Rekursive Datentypen, in denen ein Typ auf Elemente seines Typs verweist, sind nicht erlaubt. Wertzuweisungen an Variablen mit zusammengesetztem Typ müssen attributweise erfolgen. Dabei werden die Werte kopiert. Für zwei Variablen p1 und p2 vom Typ Person ist z. B. p1=p2; nicht erlaubt, die Zuweisung muss mit p1.id=p2.id; und p1.trinkt=p2.trinkt; erfolgen. Von allen Datentypen können einfache Arrays, auch Reihungen oder Felder genannt, definiert werden, wie man es im Beispiel mit der Variablen nase sieht, die drei Elemente vom Typ Person aufnehmen kann. Wie in den meisten Programmiersprachen beginnt die Nummerierung mit Null, im Beispiel gibt es die einzelnen Felder nase[0], nase[1] sowie nase[2]. Felder können ebenfalls in strukturierten Datentypen genutzt werden.
24
2.2 Die Spezifikationssprache PROMELA Der Beispielprozess besteht aus folgenden Schritten: Zunächst werden die Feldelemente des Feldes nase gefüllt, wobei die Personen der Reihe nach bier, osaft und wodka trinken. Danach wird für die Variable party festgelegt, dass jeweils nase[0] mit nase[1], nase[1] mit nase[2] und nase[2] mit nase[0] kommuniziert, dabei steht % für die Modulo-Rechnung, also den ganzzahligen Rest, z. B. 7%3==1. Abschließend wird geprüft, ob es zwei Kommunikationspartner gibt, von denen einer Wodka und der andere O-Saft trinkt, damit diese vielleicht mischen können. Das Ergebnis steht in der Variablen wodkaO.
zuP2 P1
zuP1
P2
Abb. 11: Kommunizierende Prozesse PROMELA ist besonders geeignet, kommunizierende Prozesse zu spezifizieren. Solche Prozesse sind durch so genannte Kommunikationskanäle verbunden, über die Daten ausgetauscht werden. Zum Datenaustausch gibt es jeweils einen sendenden und einen empfangenden Prozess. In Abb. 11 sind zwei einfache Prozesse skizziert, die mit zwei Kanälen unidirektional verbunden sind. P1 kann über den Kanal zuP2 Informationen an P2 senden, P2 kann über den Kanal zuP1 Informationen an P1 senden. Als Beispiel soll folgendes Protokoll spezifiziert werden. Der Prozess P1 versucht über zuP2 die Werte von 1 bis 10 an P2 zu senden. Eine Nachricht besteht dabei aus den Teilinformationen Nachrichtenname, hier send, und dem übermittelten Wert. P2 empfängt den Wert und schickt zur Bestätigung den gleichen Wert mit dem Nachrichtennamen ack für Acknowledge als Bestätigung an P1 zurück. Nachdem P1 den bestätigten Wert erhalten hat, wird der nächste Wert an P2 übermittelt. Weiterhin soll modelliert werden, dass die Verbindung von P1 nach P2 nicht fehlerfrei funktioniert; wenn P2 einen Wert empfängt und P2 an der Qualität zweifelt, wird der vorher gesandte Wert an P1 gesendet. P1 wiederholt daraufhin den zuletzt übertragenen Wert. Beim ersten empfangenen Wert kann P2 mit dem Antwortwert Null die Wiederholung der Übertragung fordern. Abb. 12 zeigt das Kommunikationsprotokoll in PROMELA. Kanäle werden durch das Schlüsselwort chan definiert, danach steht in Klammern die Anzahl der gepufferten Nachrichten, was später noch genauer betrachtet wird. chan
= [Puffergröße] of {, ... , };
25
2 Modelchecking mit PROMELA und SPIN mtype = {send,ack}; byte N=10; chan zuP2=[0] of {mtype,byte}; chan zuP1=[0] of {mtype,byte}; active proctype P1(){ byte wert=1; byte antwort; do :: wert<=N -> zuP2!send,wert; zuP1?ack,antwort; if :: antwort==wert -> wert=wert+1 :: else ->skip fi :: else -> break od; } active proctype P2(){ byte neu=0; byte ein=0; do :: zuP2?send,ein -> if :: true -> neu=ein; if :: neu==N -> break :: else -> skip fi :: true ->skip fi; zuP1!ack,neu; od; }
Abb. 12: Kommunikationsprotokoll in PROMELA Durch die Zahl Null für die Puffergröße wird gefordert, dass ein Nachrichtenaustausch nur stattfinden kann, wenn Sender und Empfänger gleichzeitig bereit sind, die Nachricht auszutauschen. Ist dies nicht der Fall, muss der Sender warten, bis der Empfänger bereit ist, bzw. der Empfänger warten, bis der Sender bereit ist. Man spricht bei dieser Kommunikationsart von einem Rendezvous oder auch synchroner Kommunikation. Die Spezifikation des Kanals beinhaltet auch die Form der übertragenen Nachrichten, dazu stehen die in einer Nachricht übertragenen Datentypen innerhalb der geschweiften Klammern. Typisch ist, dass der erste Typ mtype ist, was aber nicht unbedingt der Fall sein muss.
26
2.2 Die Spezifikationssprache PROMELA Der Prozess P1 sendet zunächst die Nachricht (send,1). Dies geschieht durch den Befehl zuP2!send,wert; Dabei steht das Ausrufungszeichen für das Senden. Die generelle Sendenachricht hat die Form ! <Wert vom Nachrichtentyp1>, ... , <Wert vom NachrichtentypN>; Statt send,wert, hätte auch send(wert) stehen können, was semantisch die gleiche Bedeutung hat, aber vielleicht mehr veranschaulicht, dass es sich bei send um den Nachrichtennamen handeln soll. Nach dem send wartet P1 auf die Antwort von P2, die mit zuP1?ack,antwort; empfangen wird. Dabei steht ein Fragezeichen für den Nachrichtenempfang. Die generelle Form lautet ? <Wert oder Variablenname vom Nachrichtentyp1>, ..., <Wert oder Variablenname vom NachrichtentypN>; Die Bezeichnung „Wert oder Variablenname“ deutet hier zwei Möglichkeiten an. Wird ein Variablenname angegeben, so bedeutet dies, dass der übertragene Wert in dieser Variablen gespeichert werden soll; dies ist hier mit der Variablen antwort der Fall. Wird statt einer Variablen ein konkreter Wert angegeben, hier der Nachrichtenwert ack, bedeutet dies, dass nur Nachrichten angenommen werden, die als ersten Teil der Nachricht den Wert ack übermitteln. Würde P2 versuchen, eine andere Nachrichtenart zu schicken, wäre P1 nicht bereit, diese Information anzunehmen. In einigen Fällen möchte man, dass ein Nachrichtenteil keiner Konstanten, sondern dem Wert einer Variablen entspricht. Würde man die Variable angeben, so würde einfach der gesendete Wert in diese Variable geschrieben. Dies kann durch das Schlüsselwort eval verhindert werden. So bedeutet zuP1?eval(x),antwort;
dass der Empfang nur möglich ist, wenn der Wert der ersten Nachrichtenkomponente dem Wert der Variablen x entspricht. Ist in der if-Anweisung in P1 die Antwort der zuletzt übertragene Wert, wird die Übertragung des Folgewertes vorbereitet. Im anderen Fall bleibt der alte Wert erhalten, der dann bei der erneuten Ausführung des Schleifenrumpfs wieder übertragen wird. Dies kann theoretisch unendlich oft passieren. Der Prozess P2 empfängt zunächst eine Nachricht mit zuP2?send,ein. Danach wird nichtdeterministisch entschieden, ob die Nachricht in Ordnung ist oder nicht. Durch das if mit den beiden true-Zweigen wird modelliert, dass es sich um ein unsicheres Protokoll handelt. Falls der Wert korrekt angenommen wurde, wird er in der Variablen neu gespeichert und danach geprüft, ob der letzte Wert gesendet wurde, was zur Prozessterminierung, also zum Verlassen der umgebenden Schleife mit break, führt. Sonst wird zum Abschluss der zuletzt erfolgreich angenommene Wert mit der Nachricht ack an P1 geschickt.
27
2 Modelchecking mit PROMELA und SPIN Durch die Puffergröße bei der Kanalspezifikation kann angegeben werden, wie viele Nachrichten der Puffer aufnehmen kann. Die Idee ist dabei, dass Sender und Empfänger nicht aufeinander warten müssen. Ein Sender schickt seine Nachricht ab, was konkret bedeutet, dass die Nachricht in den Puffer des Kanals geschrieben wird. Falls der Puffer voll sein sollte, kann man zwei alternative Ansätze für das Modell später bei der Simulation und Verifikation definieren: 1.
Der Sender muss warten, bis eine Nachricht aus dem Puffer entnommen wurde. Der Sender ist also blockiert.
2.
Die Nachricht geht verloren, ohne dass Sender und Empfänger etwas davon mitbekommen. Der Sender ist aber nicht blockiert.
toP2 P1
toP1
P2
Abb. 13: Asynchrone Kommunikation Empfänger können Nachrichten aus den Puffern der Kanäle entnehmen. Die Puffer sind nach dem FIFO-Prinzip (first in, first out) organisiert, so dass der Empfänger die älteste Nachricht aus dem Puffer entnimmt. Will der Empfänger eine Nachricht entnehmen und ist der Puffer leer, so muss er warten, bis eine Nachricht vorliegt. Das Prinzip der gepufferten Kanäle mit zwei Kanälen mit der Puffergröße vier ist in Abb. 13 skizziert. Man sieht jeweils eine bzw. zwei auf den Empfang wartende Nachrichten. Man spricht dabei von gepufferter oder asynchroner Kommunikation. Generell ist die asynchrone Kommunikation meist schneller, aber wesentlich schwerer zu handhaben als die synchrone Kommunikation. Nach einer erfolgreichen synchronen Kommunikation weiß ein sendender Prozess genau, dass die Nachricht angekommen ist. Er kann damit Annahmen über den aktuellen Zustand des Empfängers machen. Bei einer asynchronen Kommunikation finden sehr viel seltener Blockaden der Prozesse durch Warten statt, ein Sender weiß aber zumindest nicht, wann seine Nachricht wirklich ankommt. Da auch bei dem Empfang einer Nachricht unklar ist, wie lange sie schon im Puffer war, können weder Sender noch Empfänger genauere Annahmen über den Zustand des anderen machen. Würde man für die Spezifikation aus Abb. 12 die Puffergröße der Kanäle ändern, würde sich nichts Wesentliches ändern, da P1 nach dem Senden auf eine Nachricht von P2 wartet und P2 nach dem Empfang unmittelbar eine Nachricht schickt. Außer, dass die Kommunikation in zwei Teilschritte aufgeteilt wird, gibt es hier nur wenige interne Schritte, die ohne den kommunizierenden Prozesspartner durchgeführt werden können.
28
2.2 Die Spezifikationssprache PROMELA Funktion len(k) empty(k) nempty(k) full(k) nfull(k)
Bedeutung / Rückgabewert Nachrichtenanzahl im Kanal k ist Nachrichtenkanal k leer? ist Nachrichtenkanal k nicht leer? ist Nachrichtenkanal k voll? ist Nachrichtenkanal k nicht voll?
Abb. 14: Funktionen zur Analyse des Kanalzustands Damit innerhalb der Spezifikation der Kanalzustand analysiert werden kann, gibt es die in Abb. 14 beschriebenen Funktionen, die nur für asynchrone Kanäle, also Kanäle mit Puffergröße größer als Null, Sinn machen.
S
k
S1
k
S2 S1 S2
E
k
E E1 E2
Abb. 15: Interpretationen eines Kanals Für einen Kanal, der wie folgt spezifiziert ist, kann man verschiedene Interpretationen angeben, die in Abb. 15 visualisiert sind. chan k = [2] of {mtype,byte}
Die einfachste Sichtweise ist die eines gerichteten Kanals, der genau einen Empfänger und einen Sender hat. Grundsätzlich können aber auch mehrere Sender den gleichen Kanal nutzen, der bei einem Empfänger endet. Man kann sich das wie eine Adresse oder Port vorstellen, an die verschiedene Prozesse Anfragen schicken können. In der allgemeinsten Form kann es zusätzlich mehrere Empfänger geben, die alle Daten aus dem gleichen Kommunikationskanal lesen können. Der Kanal wird so zu einem gemeinsamen Austauschmedium zwischen n Sendern und m Empfängern.
29
2 Modelchecking mit PROMELA und SPIN
Teilnehmer 1 toV
Teilnehmer 2
...
toV toP[1]
Teilnehmer n toV
toV
toP[2]
toP[n]
Verteiler Abb. 16: Zentrale Informationsverteilung Als Beispiel für eine Spezifikation mit asynchronen Kanälen soll jetzt eine Informationszentrale spezifiziert werden. Die Idee dabei ist, dass beliebig viele Teilnehmer an einem Verteiler angeschlossen sind, siehe Abb. 16. Dabei nutzen alle Teilnehmer den gleichen Kanal, um Informationen an den Verteiler zu senden. Jede Information, die die Teilnehmer dem Verteiler schicken, wird an alle anderen angeschlossenen Teilnehmer verteilt, wie es z. B. bei Ethernet-Switches der Fall ist. Im Beispiel schicken alle Teilnehmer die Zahlen 1 bis 10, jeder Teilnehmer summiert alle empfangenen Zahlen auf. Durch diese Festlegung ist es recht einfach, eine Terminierungsbedingung anzugeben; bei n Prozessen erhält man (n-1)-mal die Summe der Werte von 1 bis 10. #define PROZESSE 3 #define MAX 10 #define GESAMT ((MAX*(MAX+1))/2) #define PUFFER 2 mtype={send,rec} chan toV = [PUFFER] of {mtype,byte,byte}; chan toP[PROZESSE]= [PUFFER] of {mtype,byte,byte}; proctype Teilnehmer(byte id){ byte i=1; int summe=0; byte wert; do :: atomic{ i<=MAX && nfull(toV); /* 1 */ toV!send,id,i; i=i+1 } :: summe toP[id]?rec,_,wert; summe=summe+wert :: i==MAX+1 && summe==GESAMT *(PROZESSE-1) -> break
30
2.2 Die Spezifikationssprache PROMELA od; } proctype Verteiler(){ byte name; byte wert; byte emp; do :: toV?send,name,wert -> emp=0; do :: emp toP[emp]!rec, name, wert; emp=emp+1 :: emp==name -> emp=emp+1 :: emp==PROZESSE -> break od; od; } init{ atomic{ byte i=0; do :: i run Teilnehmer(i); i=i+1 :: else -> break od; run Verteiler() }; }
Abb. 17: Informationszentrale mit asynchroner Kommunikation Abb. 17 zeigt die Spezifikation der Informationsverteilung. Neben den bereits bekannten Sprachkonstrukten werden noch einige weitere verwandt, die hier zunächst vorgestellt werden. Kommentare kann man an beliebigen Stellen in Spezifikationen ergänzen. Ein Kommentar, der über mehrere Zeilen gehen kann, beginnt mit /* und endet mit */, dies sieht man im Beispiel mit dem Kommentar /* 1 */, der hier als Markierung genutzt wird. Ein wichtiges Sprachkonstrukt ist atomic, wodurch festgelegt wird, dass in den geschweiften Klammern ein ununterbrechbarer Bereich folgt. Die bisher vorgestellten Befehle, wie x=x+1 sind nicht unterbrechbar. Unterbrechungen durch andere Prozesse sind nach jedem Befehl, also anschaulich an jeder Stelle, an der ein Semikolon stehen kann, möglich. Will man eine solche Unterbrechung verhindern, muss sich das Spezifikationsstück in einem atomaren Bereich befinden. Atomare Bereiche
31
2 Modelchecking mit PROMELA und SPIN können auch am Anfang von Auswahlen bei do und if stehen. Dabei wird bei der Überprüfung der Ausführbarkeit untersucht, ob die erste Anweisung des atomaren Bereichs ausführbar ist. Ist das der Fall, dann kann diese Alternative gewählt werden, und bei Auswahl dieser Alternative wird der atomare Bereich vollständig ausgeführt. Atomare Bereiche beinhalten grundsätzlich die Gefahr eines Deadlocks, falls ein Schritt nicht ausgeführt werden kann. Die Semantik von atomic weicht an dieser Stelle von der im späteren Kapitel zur Programmverifikation benutzten Semantik ab. Falls ein atomarer Bereich nicht fortschreiten kann, können andere Prozesse aktiv werden; wenn dann der atomare Bereich den nächsten Schritt machen kann und er voranschreitet, dann wird der Rest des atomaren Bereichs wieder atomar ausgeführt. Für den Fall, dass man keine Unterbrechungsmöglichkeiten für Kommunikationen ermöglichen möchte, gibt es in SPIN den Befehl d_step (für deterministischer Schritt). Dabei darf es im inneren Ablauf keinen Nichtdeterminismus geben, was vom Spezifizierer zu garantieren ist. Befehl c?x,y c?42,y c?eval(x),y c?<x,y> c??42,y
c??<42,y>
Semantik empfangene Werte werden in x und y gespeichert Empfang nur möglich, wenn erster Nachrichtenteil den Wert 42 hat Empfang nur möglich, wenn erster Nachrichtenteil genau den Wert hat, den auch x hat Empfang in x und y, Nachricht wird nicht aus dem Puffer gelöscht es wird die älteste Nachricht aus dem Puffer empfangen, deren erster Wert 42 ist (wenn nicht vorhanden, dann warten) älteste passende Nachricht wird gelesen, bleibt aber im Puffer
synchron + + + -
-
Abb. 18: Varianten von Empfangsmöglichkeiten Neben dem Empfangsbefehl c?x, mit dem ein Wert in die Variable x gelesen wird, gibt es den Befehl c?[x], mit dem überprüft wird, ob die Empfangsaktion durchgeführt werden kann. Diese Boolesche Bedingung dient zur Prüfung der Empfangsbereitschaft, wofür c?x natürlich nicht nutzbar ist, da sonst als ein Seiteneffekt der Überprüfung gleich der Empfang stattfinden würde. In Abb. 18 ist eine Liste der möglichen Empfangsbefehle zusammengefasst, wobei genauere Auswahlen vorliegender Nachrichten nur im asynchronen Fall möglich sind. Alle genannten Befehle können bei asynchroner Kommunikation genutzt werden, bei synchroner Kommunikation sind nur die mit „+“ markierten Befehle möglich. Das doppelte Fragezeichen als Empfangssymbol zeigt die Möglichkeit, statt nur auf die älteste
32
2.2 Die Spezifikationssprache PROMELA Nachricht zu reagieren, sich die älteste Nachricht mit einer bestimmten Eigenschaft heraus zu suchen. In Abb. 19 sind die möglichen Booleschen Prüfungen für den asynchronen Fall, ob diese Empfangsarten möglich sind, zusammengefasst. Befehl c?[x,y] c?[42,y] c?[eval(x),y] c??[42,y]
Semantik Prüfung, ob der Empfang möglich ist Ist c?42,y als nächstes möglich? Ist c?eval(x),y als nächstes möglich? Ist c??42,y möglich?
Abb. 19: Prüfungen auf Kommunikationsbereitschaft im asynchronen Fall Dadurch, dass beim Empfang eine Konstante angegeben wird, z. B. 42 oder eval(x), kann nur eine Nachricht angenommen werden, die genau diesen Wert an der geforderten Stelle der Nachricht hat. Statt c?x könnte auch c?_ stehen, was bedeutet, dass ein Empfang stattfindet, der übergebene Wert allerdings unwichtig ist. Der Unterstrich ist in diesem Sinne eine „write only“-Variable, die beliebige Werte aufnehmen kann, wobei diese Werte nicht weiter verwendet werden können. Die Spezifikation in Abb. 17 zeigt, dass man auch Felder von Kanälen definieren kann, was gerade zur Spezifikation großer Netzwerke mit gleichartigen Prozessen sehr hilfreich ist. Ein Teilnehmer besteht aus einer zentralen Schleife, bei der es drei Auswahlmöglichkeiten gibt. Die erste Möglichkeit mit dem atomic ist, dass noch nicht alle Zahlenwerte gesandt wurden (i<=MAX) und dass der Kanal zum Verteiler bereit ist (nfull(toV)), Nachrichten aufzunehmen. In diesem Fall wird eine Nachricht gesandt. Falls der Teilnehmer noch nicht alle Nachrichten der anderen Prozesse erhalten hat (summe
33
2 Modelchecking mit PROMELA und SPIN In der mit /* 1 */ markierten Zeile kann der atomic-Befehl nicht weggelassen werden. Ohne den atomic-Befehl wäre ein Deadlock möglich: Angenommen, es gibt nur noch einen Pufferplatz des Verteilers und P1 und P2 führen beide die erste Überprüfung aus, dann sendet P2 und P1 muss warten, da der Nachrichtenpuffer voll ist. Wenn der Verteiler jetzt mit der Verteilung einer Nachricht beschäftigt ist und an P1 eine Nachricht schicken will, ist dies nicht möglich, da P1 wartet, bis seine Nachricht abgeschickt wurde. Da der Verteiler aber wartet, bis die Nachricht an P1 übergeben wurde, kehrt er auch nicht an die Stelle der Nachrichtenannahme zurück. P1 und der Verteiler blockieren sich gegenseitig. chan a=[1] of {bit}; chan b=[1] of {bit}; active proctype Sender(){ do :: a!1 :: b!0 od; } active proctype Empfaenger(){ byte count=0; do :: count%2==0 && a?[_] -> a?_; count=count+1 :: count%2==1 && b?[_] -> b?_; count=count+1 od; }
Abb. 20: Bewachte asynchrone Kommunikation Die Spezifikation in Abb. 20 zeigt ein Beispiel für eine bewachte Kommunikation. Der Sender ist immer bereit, über a und b zu senden. Der Empfänger möchte nur abwechselnd über a und b empfangen. Dies wird durch einen Zähler realisiert, wobei a nur bei geradem und b nur bei ungeradem Zählerstand möglich ist. Diese Spezifikation funktioniert nicht mit synchroner Kommunikation, da es dann nicht erlaubt ist, die Kommunikationsbereitschaft zu prüfen, was leider nicht durch die Syntaxprüfung abgefangen wird. Möchte man einen ähnlichen Ansatz mit synchroner Kommunikation nutzen, muss ein vollständig neuer Spezifikationsansatz gefunden werden. Dies ist im Beispiel relativ einfach, da man in einer Schleife immer a?_; b?_ stattfinden lassen kann, führt aber bei komplexeren Spezifikationen zu einigem Umbauaufwand.
34
2.2 Die Spezifikationssprache PROMELA PROMELA erlaubt leider kein else direkt in der Kombination mit Kommunikationen: if :: chan?req -> other!ack; :: else -> x=x+1; fi:
Die vorherigen Zeilen liefern eine Fehlermeldung der Form Error: dubious use of 'else' combined with i/o,
Falls man das else nicht anders ersetzen kann, muss man zur Prüfung der Kommunikationsbereitschaft übergehen, also if :: chan?[req] -> chan?req; other!ack; :: else -> x=x+1; fi:
Der Ansatz ist nur bei asynchroner Kommunikation möglich, bei synchroner Kommunikation muss individuell ein anderer Ansatz gefunden werden. int x=1; int y=1; active proctype P(){ do :: atomic{ x>0 -> x=x-2; y=y-2 } :: atomic{ x<0 -> x=x+2; y=y+2 } :: break od; }
Abb. 21: Atomare Bereiche bei Auswahlalternativen Möchte man atomare Bereiche zusammen mit do und if nutzen, so kann man diese unmittelbar hinter den Doppelpunkten platzieren. Bei der Ausführung wird dann immer für die erste Anweisung des atomaren Blocks geprüft, ob diese ausführbar ist. Für die Spezifikation in Abb. 21 gilt, dass man immer genau einen der atomaren Blöcke auswählen kann und so x und y immer den gleichen Wert, entweder 1 oder -1 haben. Die dritte Alternative zeigt, dass man true -> break abkürzen kann. Generell kann man auf den Pfeil verzichten, da dieser semantisch genau wie ein Semikolon behandelt wird. Die Spezifikationen sind mit Pfeilen etwas lesbarer.
35
2 Modelchecking mit PROMELA und SPIN Generell gilt, dass man Ideen in der Spezifikationssprache ausprobieren soll, bei größeren Spezifikationen aber auf Experimente verzichtet, um nicht syntaktische Probleme mit semantischen Problemen der zu entwickelnden Spezifikation zu vermischen.
2.3 Simulation von PROMELA-Spezifikationen Bisher wurden PROMELA-Spezifikationen notiert, und man musste aus der Semantik der Sprachkonstrukte schließen, welches Verhalten beschrieben wurde. Da der Modelchecker SPIN auch eine Simulationskomponente hat, können PROMELA-Spezifikationen auch ausgeführt werden. Grundsätzlich kann man mit dem Programm spin direkt in der Kommandozeile arbeiten. Da dies aber recht mühselig ist, gibt es dazu eine Oberfläche XSPIN, die die Erstellung, Simulation und Verifikation von Spezifikationen wesentlich erleichtert. XSPIN ist in Tcl/Tk geschrieben und steht zur freien Verfügung. Da sich das Programm seit Mitte der 1990er Jahre vom Design nicht wesentlich geändert hat, wirkt es etwas altmodisch, was es aber durch seine Funktionalität wieder wettmacht. Eine Alternative zu XSPIN ist JSPIN [@Jsp], das etwas komfortabler zu bedienen ist, allerdings nicht alle Möglichkeiten von XSPIN bietet. Generell gilt für die Entwicklung von ausführbaren Programmen und Modellen, dass man immer inkrementell vorgehen sollte. Dazu schreibt man zunächst einen Teil des Codes, der die zentralen Schritte ausführt und nicht auf Alternativen achtet. Das entstehende Teilsystem wird danach, z. B. durch eine Simulationskomponente, ausgeführt, so dass man grundsätzlich die Lauffähigkeit gezeigt hat. Danach werden Schritt für Schritt weitere alternative Abläufe eingebaut und überprüft. Für PROMELA bedeutet dies, dass man zunächst eine Spezifikation erstellt, die im Simulator wie gewünscht läuft und danach die Verifikationsmöglichkeiten von SPIN nutzt. Abb. 22 zeigt XSPIN nach dem Start mit aufgeklapptem File-Menü. Grundsätzlich ist die Oberfläche in zwei Bereiche aufgeteilt; sie besteht aus einem weißen großen Editor-Fenster für Eingaben und einem kleineren schwarzen Fenster unten, in dem die zuletzt ausgeführten Befehle und die Reaktionen von SPIN angezeigt werden. In der rechten oberen Ecke befindet sich im Feld neben „Line#“ eine Angabe, wo sich der Cursor aktuell befindet, was bei Fehlerkorrekturen sehr hilfreich sein kann. Eine ärgerliche Besonderheit ist, dass SPIN vor der Beendigung nicht prüft, ob die aktuell bearbeitete Spezifikation schon abgespeichert wurde. Ein kleiner Trick besteht darin, einen anderen Editor zu nutzen, die Spezifikation mit diesem Editor zu speichern und dann mit „Open..“ in SPIN zu laden. Ändert und speichert man die Spezifikation dann im Editor, kann man durch „ReOpen“ die zuletzt gespeicherte Version der Datei laden.
36
2.3 Simulation von PROMELA-Spezifikationen
Abb. 22: XSPIN-Oberfläche
Abb. 23: Menüstruktur von XSPIN
37
2 Modelchecking mit PROMELA und SPIN Die in Abb. 23 zusammengefassten Menüs zu Edit, View und Help sollten selbsterklärend sein. In der Hilfe angesprochene Themen werden später noch genauer behandelt. Der Punkt „Clear Selections“ wird benutzt, wenn SPIN Zeilen markiert, z. B. um auf Fehler hinzuweisen, da diese Markierungen nicht automatisch zurückgenommen werden.
Abb. 24: Menü "Run..." Nachdem eine Spezifikation in XSPIN eingegeben oder aus einer Datei geladen wurde, besteht der erste Schritt darin, die Syntax zu prüfen. Dazu dient der erste Unterpunkt des in Abb. 24 dargestellten und uns weiterbeschäftigenden Menüs „Run..“. Gefundene Syntax-Fehler werden in einem zusätzlichen Fenster ausgegeben. Wie immer gilt, dass ein erster Fehler häufig zu Folgefehlern in der Syntaxüberprüfung führt, so dass man die Fehler von oben nach unten abarbeiten sollte. Meist ist es sinnvoll, den ersten Fehler zu korrigieren und dann die Syntaxprüfung erneut zu starten. Leider ist die Erklärung des gefundenen Fehlers nicht immer verständlich. Will man eine Simulation durchführen, wird zunächst der Punkt „Set Simulation Parameters..“ gewählt. Die wichtigsten der in Abb. 25 gezeigten komplexen Einstellungsmöglichkeiten werden jetzt Schritt für Schritt erklärt. Dazu wird zunächst die Spezifikation aus Abb. 4 genommen. Beim „Display Mode“ kann angegeben werden, welche Darstellungen man neben dem eigentlichen Simulationsfenster noch sehen möchte. Bei einer Spezifikation, die ohne Kommunikationskanäle arbeitet, ist nur das „Data Values Panel“ interessant, da man hier die Veränderungen globaler und lokaler Variablen, wenn sie ausgewählt sind, verfolgen kann.
38
2.3 Simulation von PROMELA-Spezifikationen
Abb. 25: Einstellungsmöglichkeiten für die Simulation Die zweite zentrale Einstellung wird beim „Simulation Style“ vorgenommen, wobei drei Arten unterschieden werden: -
-
-
Random: Wenn ausgewählt werden kann, welcher Schritt als nächstes möglich ist, wird diese Auswahl vom Simulator getroffen. Über „Seed Value“ wird der Startwert des zugehörigen Zufallszahlengenerators gesetzt. Bei unverändertem Wert erhält man somit immer den „gleichen Zufall“, durch Änderung des Wertes eventuell alternative Abläufe. Guided: Diese Auswahl ist nur sinnvoll, wenn in einer Datei abgespeichert ist, welche Schritte ausgeführt werden sollen. Dies wird besonders beim gescheiterten Modelchecking interessant, da es für den Fehlerfall eine Ausführungssequenz gibt, die man dann schrittweise abarbeiten kann. Interactive: Bei jeder Auswahlmöglichkeit, welcher Schritt als nächstes durchgeführt werden soll, wird der Nutzer befragt.
Im Auswahlbereich „A Full Queue“ wird für asynchrone Kommunikation festgelegt, wie sich das System verhalten soll, wenn ein Sender eine Nachricht schicken
39
2 Modelchecking mit PROMELA und SPIN möchte, es aber keinen freien Pufferplatz mehr gibt. Entweder muss der Sender warten mit „Blocks New Msgs“ oder die Nachricht geht mit „Loses New Msgs“ verloren. Der erste Ansatz garantiert, dass Nachrichten ankommen, kann den Ablauf aber verzögern. Der zweite Ansatz ist z. B. bei Streaming-Protokollen interessant, da es bei Audio- und Videoübertragungen wichtiger ist, dass die Daten fließend ausgegeben werden und verlorene Informationen zwar die Qualität, aber nicht die generelle Funktionalität beeinflussen. Will man ohne Blockierung garantieren, dass eine Nachricht ankommt, muss ein Protokoll aus Sende- und Bestätigungsnachrichten aufgebaut werden. Nun soll zunächst „Random“ als „Simulation Style“ gewählt werden. Die Simulation startet mit dem Start-Knopf rechts unten bei den Simulationseinstellungen. Die Simulation läuft nicht sofort los; man erhält zunächst die in Abb. 26 gezeigten Fenster. Da jede Ausgabe in einem eigenen Fenster passiert, ist darauf zu achten, dass zur Beendigung der Simulation der Knopf „Cancel“ im Hauptfenster „Simulation Output“ der Simulation gedrückt wird.
Abb. 26: Start eines Simulationslaufs
40
2.3 Simulation von PROMELA-Spezifikationen Wird bei der Simulation der „Single Step“-Knopf gedrückt, wird der nächste Schritt ausgeführt. Man kann die Variablenveränderungen in jedem Schritt verfolgen. Durch „Run“ läuft die Spezifikation automatisch ab, bis entweder alle Prozesse beendet sind oder die Simulation von Hand mit „Suspend“ unterbrochen wird. Das Ergebnis des Simulationslaufs ist in Abb. 27 dargestellt.
Abb. 27: Simulationsergebnis
Abb. 28: Interaktive Simulation
41
2 Modelchecking mit PROMELA und SPIN Wählt man bei den Simulationsoptionen „Interactive“, so wird man an jeder Stelle, an der mehrere Prozesse einen Schritt machen könnten oder es in einem if oder do mehrere ausführbare Wächter gibt, gefragt, welcher Schritt als nächstes ausgeführt werden soll. Abb. 28 zeigt ein mögliches Zwischenergebnis für die Spezifikation aus Abb. 4. Im Simulationsfenster sieht man weiterhin, dass insgesamt fünf Möglichkeiten für einen nächsten Schritt geprüft wurden, wovon zwei möglich sind, die dem Nutzer angeboten werden.
Abb. 29: Time Sequence Panel in XSPIN Eine Visualisierungsmöglichkeit ist das „Time Sequence Panel“, mit dem veranschaulicht werden kann, welcher Prozess wann einen Schritt macht. Dieses Panel kann bei verschiedenen Simulationsarten eingestellt werden, und das Ergebnis kann, wie bei anderen Simulationsläufen auch, abgespeichert werden. Ähnlich zu den später vorgestellten Message Sequence Charts kann die so entstehende Dokumentation später bei der Optimierung der Spezifikation hilfreich sein. Neben einer Dokumentation des gewünschten Ablaufs können die entstandenen Diagramme als Vorgabe für die Testfallerstellung genutzt werden, falls z. B. eine vollständige Verifikation nicht möglich ist. Der Ersteller der Spezifikation überlegt sich dazu kritische Fälle und simuliert diese interaktiv. Die resultierenden Time Sequences werden dann in die Dokumente zur Testfallerstellung eingearbeitet. Abb. 29 zeigt den Start einer Time Sequence für die Spezifikation aus Abb. 4. Auf der linken Seite steht, welcher Prozess in welcher Zeile einen Schritt ausgeführt hat. Mit dem in den Simulationsoptionen einschaltbaren „Execution Bar Panel“ wird sichtbar, wie viele Schritte ein einzelner Prozess durchgeführt hat. Das Ergebnis für die Spezifikation aus Abb. 4 ist in Abb. 30 dargestellt. Der Startprozess führt drei Schritte aus, und Gerade führt insgesamt für die Werte 0 und 22 zwei Berech-
42
2.3 Simulation von PROMELA-Spezifikationen nungen mit jeweils zwei Schritten mehr als Ungerade aus. Diese Diagrammart wird dann interessant, wenn man eine Spezifikation erstellt hat, bei der man davon ausgeht, dass einige zentrale Prozesse gleich viele Schritte durchführen. Im Execution Bar Panel werden dann so genannte Bottle-Necks sichtbar, also Prozesse, die sehr viel zu tun haben, gegenüber anderen Prozessen, die eventuell nur auf andere Prozesse warten.
Abb. 30: Bar Chart mit Zahl der ausgeführten Schritte Die vielleicht nützlichste Visualisierungsart von XSPIN sind Message Sequence Charts (MSC). MSC dienen zur Protokollierung der Abläufe kommunizierender Prozesse. Die Kernidee von MSC ist dabei relativ einfach: In der Kopfzeile wird jeder laufende Prozess als ein Kästchen dargestellt, von dem ein langer Strich, die Lebenslinie des Prozesses, nach unten abgeht. Die Zeitachse verläuft ebenfalls von oben nach unten. Wenn ein Prozess eine Nachricht sendet, wird dies zum Zeitpunkt des Sendens an der Lebenslinie des sendenden Prozesses festgehalten. Wird die Nachricht empfangen, wird dies durch einen Pfeil vom Sender zur Lebenslinie des Empfängers, genauer zum Zeitpunkt des Empfangens, festgehalten. Der Pfeil ist typischerweise mit der Nachricht markiert. Ein resultierender MSC für die Spe-
43
2 Modelchecking mit PROMELA und SPIN zifikation aus Abb. 12 ist in Abb. 31 festgehalten. Man sieht zwei Prozesse, die von Anfang an existieren und Nachrichten austauschen. Weiterhin erkennt man bei diesem MSC, dass die Nachricht „2“, erkenntlich als letzter Wert, einmal wiederholt wird. Die Nummern in den Kästen referenzieren Stellen, die im „Simulation Output“ nachzulesen sind.
Abb. 31: Message Sequence Chart
44
2.3 Simulation von PROMELA-Spezifikationen
Abb. 32: MSC für asynchrone Kommunikation Bei asynchroner Kommunikation können die MSC noch komplexer werden, da man hier sieht, dass sich verschiedene Nachrichten überholen, also später produziert und früher empfangen werden können. Ein Beispiel ist zur Spezifikation aus Abb. 17 in Abb. 32 festgehalten. Man sieht z. B., dass die in den Knoten 27 und 30 erzeugten Nachrichten zeitlich in anderer Reihenfolge empfangen werden. Für MSC gelten ähnliche Aussagen wie für Time Sequences, sie können nicht nur zur Dokumentation von Spezifikationsabläufen dienen, sie können auch zur Vorbereitung von Tests sehr hilfreich sein. MSC sind standardisiert und werden in Telekommunikationsstandards zur Dokumentation von Abläufen genutzt. Bei der Visualisierung und der Analyse von Prozessabläufen kann es auch hilfreich sein, dass PROMELA den printf-Befehl aus C zur Ausgabe von Werten unterstützt. Dabei hat der Befehl generell folgende Struktur.
45
2 Modelchecking mit PROMELA und SPIN printf("Text mit Platzhaltern", Var1, …, VarN);
Im eigentlichen Ausgabe-String stehen sogenannte Platzhalter für die Werte der Variablen, die ausgegeben werden sollen. Dabei sind in PROMELA %d zur Ausgabe von Zahlenwerten wie auch bool, und %e zur Ausgabe vom mtype-Werten nutzbar. Hinter dem Ausgabestring stehen die Variablen, die in der Reihenfolge der Platzhalter mit ihren Werten ausgegeben werden. #define PROZESSE 4 byte x=0; active[PROZESSE] proctype P(){ do :: x<8 -> atomic{ x=x+1; printf("Prozess %d: x=%d\n",_pid,x) } :: else -> break od }
Abb. 33: Spezifikation mit Ausgabebefehl In der Spezifikation in Abb. 33 wird die spezielle vordefinierte Variable _pid als Prozessidentifikator genutzt. Genauer wird ausgehend von Null der Wert von _pid für jeden neu erstellten Prozess hochgezählt, wobei zunächst ein möglicher initProzess den Wert Null bekommt, dann der Spezifikationstext von oben nach unten abgearbeitet wird und für jeden erzeugten Prozess der jeweilige _pid-Wert um Eins erhöht wird. Jeder Prozess hat damit eine eindeutige Nummer, die er über diese Variable abrufen kann. Lässt man z. B. die Spezifikation aus Abb. 33 in einer Simulation laufen, so kann man im Simulationsfenster folgende Ausgabe erhalten, die zeigt, welcher der vier Prozesse die globale Variable x erhöht hat. 24: proc
1 (P) line
7 "pan_in" (state 4) [x = (x+1)]
Prozess 1: x=6 25: proc
1 (P) line
8 "pan_in" (state 3) [printf('Prozess %d: x=%d\\n',_pid,x)]
Verzichtet man auf die Nutzung von XSPIN und startet SPIN in der Kommandozeile, so sind dort ebenfalls die Ausgaben sichtbar. Hält man sich an folgende Formatierungen, so sind die Ausgaben auch im Message Sequence Chart sichtbar. Der eigentliche Text muss mit „MSC: “ beginnen, man beachte das Leerzeichen nach dem Doppelpunkt, und mit einem Zeilenumbruch „\n“ enden.
46
2.3 Simulation von PROMELA-Spezifikationen #define PROZESSE 4 byte x=0; active[PROZESSE] proctype P(){ do :: x<8 -> atomic{ x=x+1; printf("MSC: Prozess %d: x=%d\n",_pid,x) } :: else -> break od }
Abb. 34: Spezifikation mit Ausgabebefehl für MSC Wandelt man die Spezifikation aus Abb. 33 nur in der Ausgabezeile, wie in Abb. 34 gezeigt, ab, so kann man z. B. folgenden Message Sequence Chart aus Abb. 35 als Ergebnis sehen.
Abb. 35: MSC mit zusätzlichem Ausgabetext Mit Hilfe eines MSC und der printf-Befehle kann man auch das Verhalten von atomic genauer veranschaulichen. Dazu wird die Spezifikation aus Abb. 36 betrachtet und eine interaktive Simulation gestartet. Am Anfang wird geprüft, ob die jeweils ersten Anweisungen der atomic-Blöcke ausführbar sind; dies ist hier nur für Q der Fall. Da damit ein atomarer Block betreten wurde, wird dieser weiter ausgeführt. Dann ist y==1 nicht ausführbar, y hat den Wert Null, deshalb wird der atomicBlock von Q verlassen und festgestellt, dass jetzt der atomic-Block von P starten kann, der dann auch atomar bis zum Ende ausgeführt wird. Danach kann der atomare Block von Q nicht mehr betreten werden. Es ist ein Deadlock entstanden.
47
2 Modelchecking mit PROMELA und SPIN int x=0; int y=0; active proctype atomic{ x==1; printf("MSC: y=1; printf("MSC: y=y+1; printf("MSC: } } active proctype atomic{ x=1; printf("MSC: y==1; printf("MSC: x=x+1; printf("MSC: } }
P(){ Prozess P: x==1\n"); Prozess P: y=1\n"); /*1*/ Prozess P: y=y+1\n")
Q(){ Prozess Q: x=1\n"); Prozess Q: y==1\n"); Prozess Q: x=x+1\n")
Abb. 36: Spezifikation zur Analyse von atomic
Abb. 37: Sequenzdiagramm zur atomic-Analyse Der zugehörige MSC in Abb. 37 zeigt den beschriebenen Ablauf. Obwohl die interaktive Simulation gewählt wurde, wird der Nutzer nie aufgefordert eine Alternative zu wählen, da jeweils nur eine Alternative zur Verfügung steht. Am Ende zeigt XSPIN einen leeren Auswahlkasten, der etwas unschön den Deadlock anzeigt. Würde man die mit /*1*/ gekennzeichnete Zeile weglassen oder y nicht verändern, würde Prozess Q nach P abgearbeitet werden.
48
2.4 Einfache Verifikationsmöglichkeiten
2.4 Einfache Verifikationsmöglichkeiten SPIN stellt einige einfache Überprüfungsmöglichkeiten für wichtige Eigenschaften zur Verfügung. Die Möglichkeit, Anforderungen direkt zu spezifizieren, wird dann im folgenden Teilkapitel vorgestellt.
2.4.1
Grundideen des Modelcheckings
Zunächst soll prinzipiell geklärt werden, wie dieser Modelchecker funktioniert. Die Ausgangsidee besteht darin, alle möglichen Berechnungen durchzuführen und diese dann zu analysieren. Dabei kann man die Menge aller erreichbaren Zustände als endlichen Automaten auffassen, wobei die für die Zustandsänderungen verantwortlichen Anweisungen an den Kanten stehen, die diese Zustände verbinden. Um genau zu beschreiben, in welcher Situation sich eine Spezifikation befindet, muss man festhalten, welche Werte alle Variablen aktuell haben und an welcher Stelle sich gerade jeder Prozess befindet. Wenn man alle Anweisungen einer Spezifikation nummeriert, kann man die Stelle, an der sich ein Prozess gerade befindet, mit einer Hilfsvariablen festhalten, die die Nummer der als nächstes auszuführenden Anweisung beinhaltet. byte x=0; /* 1 */ byte y=0; /* 2 */ active proctype Mini(){ do /* 3 */ :: x<2 -> /* 4 */ x=x+1 /* 5 */ :: y<2 -> /* 6 */ y=y+1 /* 7 */ :: else -> /* 8 */ break /* 9 */ od; } /* 10 */
Abb. 38: Für Zustandsraum zu analysierende Spezifikation Möchte man einen Zustand einer Spezifikation beschreiben, so muss man für jede Variable und jeden Kanal genau den aktuellen Zustand, also die Wertebelegung, beschreiben. Diese Folge von Informationen wird auch Zustandsvektor genannt. Die Länge des Zustandsvektors hängt von dem Speicherplatz ab, den die jeweiligen Variablen maximal benötigen. Im Beispiel sind es zwei Variablen vom Typ byte, ein Byte benötigt acht Bit, so dass der Zustandsvektor eine Länge von 16 Bit hat. In SPIN selber wird der Zustandsvektor größer sein, da für alle Prozesse gespeichert wird, an welcher Stelle sie sich aktuell befinden. Die Menge aller so erreichbaren Zustandsvektoren, oder einfach Zustände, wird Zustandsraum genannt.
49
2 Modelchecking mit PROMELA und SPIN
(_,3,0,0) y<2
x<2
(0,5,0,0)
(0,7,0,0)
x=x+1
y=y+1
(0,3,1,0) x<2
y<2
(0,5,1,0)
x<2
(0,7,1,0)
x=x+1
x=x+1
y<2
x<2
(0,7,2,0)
(0,5,1,1)
y=y+1
y<2
(0,5,0,1)
y=y+1
(0,3,2,0)
(0,3,0,1)
(0,3,1,1)
(0,7,0,1) y=y+1
(0,3,0,2)
y<2
x<2
(0,7,1,1)
(0,5,0,2)
x=x+1
x=x+1
y=y+1
(0,3,2,1)
(0,3,1,2)
y<2
x<2
(0,7,2,1)
x=x+1
y=y+1
(0,5,1,2)
(0,3,2,2)
else
(0,9,2,2) break
(0,10,2,2)
Abb. 39: Zustandsraum der Spezifikation Für die einfache Spezifikation aus Abb. 38 kann man den in Abb. 39 gezeigten Zustandsraum ableiten. Dabei ist neben den Werten für x und y am Anfang des Zustandsvektors auch festgehalten, an welcher Stelle in der Spezifikation sich die Ausführung aktuell befindet. Der Unterstrich steht dabei für einen beliebigen, hier undefinierten Wert. Der erste Wert steht für den aktiven Prozess; der Unterstrich in diesem Spezialfall für die Vorbereitung mit der Initialisierung der globalen Variablen. Insgesamt setzt sich der Zustandsvektor in der Abbildung aus den Werten für den Prozessidentifikator, der Position dieses Prozesses in der Spezifikation, sowie den Werten für x und y zusammen. Die Markierungen an den Kanten bestehen aus den ausgeführten Spezifikationsbefehlen. Wichtig ist die Erkenntnis aus Abb. 39, dass es verschiedene Wege zum gleichen Zustand geben kann. Grundsätzlich wird für einen Zustand berechnet, welche neuen Zustände durch die Ausführung eines erlaubten Spezifikationsschritts erreicht werden können. Um alle Zustände zu berechnen, gibt es verschiedene An-
50
2.4 Einfache Verifikationsmöglichkeiten sätze; man kann z. B. einen Tiefendurchlauf machen und immer einen der möglichen Folgezustände auswählen. Alternativ berechnet man für jeden Zustand die vollständige Menge der im nächsten Schritt erreichbaren Zustände, was einem Bereitendurchlauf entspricht. Wird ein neuer Zustand berechnet, so muss zunächst überprüft werden, ob dieser Zustand nicht bereits betrachtet wurde. Ist dies der Fall, sind keine weiteren Untersuchungen notwendig; man hat einen Zyklus gefunden und kann sich um andere Zustände kümmern, für die noch nicht alle Nachfolger bestimmt sind. Da es nur endliche Datentypen gibt, ist die Zustandsmenge immer endlich und das Verfahren terminiert. Statt die gesamte Liste der bisher erreichten Zustände immer vollständig durchlaufen zu müssen, gibt es verschiedene Techniken, die erreichten Zustände so zu speichern, dass man einen Zustand leicht wieder finden kann. Typisch ist hierfür ein Ansatz mit einer Hash-Funktion. Dabei wird aus dem Zustandsvektor mit einer möglichst einfachen Funktion ein Zahlenwert in einem vorher vorgegebenen Zahlenbereich, z. B. 0 bis n, berechnet. Zu dem Zahlenbereich gehört ein Feld, in dem Zustandsvektoren, genauer Listen von Zustandsvektoren, eingetragen werden können. Man berechnet zunächst den Hash-Wert und geht dann die zum HashWert gehörende Liste durch. Da verschiedene Zustandsvektoren den gleichen Hash-Wert haben können, reicht ein einfaches Feld nicht aus. Falls der Zustandsvektor nicht in der Liste eingetragen ist, wird er hinten angehängt. Abb. 40 zeigt ein mögliches Ergebnis einer Hash-Funktion für den in Abb. 39 gezeigten Zustandsraum, dabei wurde die Summe der letzten drei Einträge gebildet und modulo 7 gerechnet ((auszuführende Zeile+x+y) % 7). Wert 0 1
(0,3,2,2) (0,7,1,0)
(0,10,2,2) (0,5,1,2)
2
(0,7,2,0)
(0,7,1,1)
3
(_,3,0,0)
(0,7,2,1)
4
(0,3,1,0)
(0,3,0,1)
5
(0,5,0,0) (0,5,1,0)
(0,3,2,0) (0,3,2,1)
6
(0,5,1,1) (0,7,0,1)
(0,7,0,0)
(0,5,0,2)
(0,3,1,1) (0,9,2,2)
(0,3,0,2) (0,3,1,2)
(0,5,0,1)
Abb. 40: Zustandsverwaltung mit Hash-Tabelle Aus den Überlegungen zum Aufbau des Zustandsraums lässt sich leicht ableiten, dass die Größe des Zustandsvektors einen wesentlichen Einfluss auf die Möglichkeit hat, ob Modelchecking praktisch durchführbar ist. Die Grenze wird typischerweise durch den für SPIN vorhandenen Hauptspeicher, in anderen Fällen auch durch die notwendige Rechenzeit vorgegeben.
51
2 Modelchecking mit PROMELA und SPIN Für die Beispielspezifikation ist es also ein Unterschied, ob die Variablen vom Typ byte oder vom typ int, der 32 Bit benötigt, sind. Ähnliche Überlegungen kann man auch zur Puffergröße von Kanälen anstellen, da ein Puffer, der drei Werte vom Typ {mtype,byte} aufnehmen kann, 48 Bit benötigt und ein Puffer mit fünf Werten des gleichen Typs schon 80 Bit benötigt. Die für SPIN in PROMELA erstellten Modelle sollen also möglichst klein sein. Dies bedeutet auch, dass eine eventuell gut lesbare Spezifikation so auf das Wesentliche vereinfacht werden muss, dass das zur Verifikation optimierte Modell nur noch schwer lesbar ist, um die Möglichkeit zum Modelchecking zu haben. Während es bei Datentypen meist noch einfach zu überlegen ist, welche benötigt werden, kann dies bei Puffergrößen schon wesentlich schwieriger sein. Es gibt Modelle, die bei einer Puffergröße n funktionieren, aber bei einer Puffergröße n+1 oder n-1 nicht mehr nutzbar sind. Bei den Datentypen sei an dieser Stelle nochmals auf den Typ der Form unsigned x:5; hingewiesen, wobei die 5 für die Anzahl der Bits steht und x so die Werte von 0 bis 31 annehmen und so die Größe des Zustandsvektors verringert werden kann.. Um die Zahl der Zustände klein zu halten, sollte man für jede Befehlssequenz untersuchen, ob man sie nicht als einen Schritt durchführen, also als atomic- oder d_Step-Block formulieren kann. Falls durch die mögliche Unterbrechung durch andere Prozesse garantiert keine neuen Erkenntnisse zu erwarten sind, kann man mit diesem Ansatz vermeiden, dass überflüssige Abläufe mit in den Zustandsraum aufgenommen werden. Für globale Kommunikationskanäle besteht weiterhin die Möglichkeit, sie innerhalb einer Spezifikation mit xr oder xs zu kennzeichnen, dies kann in einer Spezifikation wie folgt aussehen: chan c1 =[2] of {byte,short}; chan c2 =[2] of {short,bool}; active proctype P(){ xr c1; xs c2; ...
Dabei steht xr dafür, dass der Prozess der einzige ist, der empfangend, also lesend, (read) und xs dafür, dass der Prozess der einzige ist, der sendend auf den Kanal zugreift. Falsche Markierungen werden von SPIN bei der Verifikation entdeckt und führen zu einem Abbruch der Berechnungen. Dabei ist zu beachten, dass auch ein len(c1) einen lesenden Zugriff auf den Kanal bedeutet. Kanalmarkierungen können nicht für einzelne Array-Elemente gesetzt werden. Möchte man eine Verifikation in SPIN durchführen, so müssen unter „Run ..“ zunächst die Verifikationsparameter mit „Set Verification Parameters ..“ eingestellt werden.
52
2.4 Einfache Verifikationsmöglichkeiten
Abb. 41: Verifikationseinstellungen in XSPIN Die komplexen Einstellungsmöglichkeiten, die es in dem Menü in Abb. 41 gibt, werden gleich Schritt für Schritt erläutert. Zunächst soll aber auf die Möglichkeit der „Advanced Options“, rechts unten in der Abbildung, eingegangen werden. Für die erste Nutzung von SPIN sind von den in Abb. 42 gezeigten Optionen insbesondere folgende Einstellungen interessant: Der „Physical Memory“ sollte möglichst genau dem Hauptspeicher entsprechen, der für die Verifikation zur Verfügung steht. Dies hängt natürlich davon ab, welche Prozesse sonst noch auf dem Rechner laufen. Die Angabe einer zu großen Zahl führt zum sehr langsamen „swapping“, wenn Informationen aus dem Hauptspeicher auf die Festplatte ausgelagert werden. Dies führt unter Umständen dazu, dass SPIN theoretisch sehr lange, also mehr als nur einige Stunden, laufen würde. Ein Richtwert ist bei einem PC die halbe Hauptspeichergröße. Die Angabe zur erwarteten Anzahl von Zuständen kann zunächst so belassen werden. Wenn man die Anzahl ungefähr aus einem früheren Verifikationslauf kennt, sollte sie angepasst werden.
53
2 Modelchecking mit PROMELA und SPIN
Abb. 42: Erweiterte Optionen für Verifikation Im Abschnitt „Error Trapping“ links-unten kann festgelegt werden, ob die Verifikation beim ersten entdeckten Fehler abgebrochen werden soll oder nicht. Weiterhin kann die zeit- und speicherintensive Option eingeschaltet werden, dass alle Ausführungspfade, die zu Fehlern führen, gespeichert werden. Automatisch wird nur ein Ausführungspfad gespeichert, der dann in der Simulation genutzt werden kann. Durch „Find Shortest Trail“ fordert man, dass der kürzeste Ausführungspfad zu einem Fehler gefunden werden soll, was wieder einiges an zusätzlicher Rechenzeit in Anspruch nehmen kann. Am Anfang sollte man die Einstellungen wie gezeigt belassen. SPIN macht standardmäßig einen so genannten Tiefendurchlauf durch den Zustandsraum. Dies bedeutet, dass an Stellen, an denen mehrere Alternativen gewählt werden können, immer eine ausgewählt und weiter verfolgt wird. Nur wenn es für diese Alternative keine weiteren Erkenntnisse mehr gibt, wird die zweite Alternative der Stelle betrachtet. Mit der Einstellung „Use Breadth-First Search“ wird die Suche auf einen Breitendurchlauf umgestellt. Dies bedeutet, dass für alle Alternativen der jeweils nächste Schritt ausgeführt und dann die Berechnung erneut für alle erreichten Zustände wiederholt wird. Da der Breitendurchlauf
54
2.4 Einfache Verifikationsmöglichkeiten meist mehr Speicher als der Tiefendurchlauf benötigt, wird diese Einstellung recht selten genutzt.
Abb. 43: Einstellungen für Komplexitätsbetrachtungen Durch „Add Complexity Profiling“ besteht die recht aufwändige Möglichkeit, sich für jede Zeile der Spezifikation berechnen zu lassen, wie häufig sie ausgeführt wurde. Damit dies machbar ist, muss bei den „Extra Verifier Generation Options“ wie in Abb. 43 angedeutet, die Option „-o3“ eingestellt werden. Die obere Auswahl erhält man durch Drücken des „Choose“-Knopfes. Mit „Compute Variable Ranges“ besteht die Möglichkeit, für jede Variable den minimalen und maximalen Wert berechnen zu lassen, den sie annehmen kann. Diese Option kostet zwar einiges an Rechenzeit, sollte aber zumindest einmal für jede Spezifikation genutzt werden, da man so detaillierte Aussagen erhält, ob man einen sinnvollen Datentypen gewählt hat.
55
2 Modelchecking mit PROMELA und SPIN
2.4.2
Modelchecking sehr großer Systeme
Es wurde bereits mehrfach angedeutet, dass Modelchecking bei sehr großen Zustandsräumen an seine Grenzen stoßen kann. Dabei stellt sich die Frage, was das System machen soll, wenn es erkennt, dass es an eine solche Grenze stößt. Hierzu gibt es in den Teilfenstern „Search Mode“ in Abb. 41 und in Abb. 42 verschiedene Einstellungsmöglichkeiten, die hier genauer diskutiert werden sollen. Die maximale Suchtiefe („Maximum Search Depth“) gibt an, wie lang Ausführungspfade in SPIN maximal sein sollen. Die Länge eines solchen Pfades wird durch die Anzahl der ausgeführten Anweisungen bestimmt, weiterhin garantiert die Simulation, dass alle Zustände auf diesem Pfad unterschiedlich sind. Muss die angegebene maximale Pfadlänge überschritten werden, wird die Verifikation auf diesem Pfad nicht weiter verfolgt, was in der späteren Ergebnisausgabe klar angezeigt wird. #define PROZESSE 2 #define GRENZE 10 byte x[PROZESSE]; active [PROZESSE] proctype P(){ x[_pid]=0; do :: x[_pid] x[_pid]=x[_pid]+1 :: else -> break od; }
Abb. 44: Unabhängige Prozesse Die Spezifikation in Abb. 44 zeigt mehrere Prozesse, die alle unabhängig voneinander den Wert eines Feldes hochzählen. Dabei wird wieder _pid, die vordefinierte Variable, die einen prozessindividuellen Identifikator enthält, genutzt.
proctype P1(){ ... a; ... }
proctype P2(){ ... b; ... }
a
z1
b
z11
z12 b
z2
a
Abb. 45: Unabhängige Aktionen Überlegt man, wie der Zustandsraum zur Spezifikation aussieht, so erhält man eine Rautenstruktur, die in Abb. 45 rechts angedeutet ist und die auch bereits in
56
2.4 Einfache Verifikationsmöglichkeiten Abb. 39 sichtbar wurde. Solche Rauten stehen für verschiedene Wege, die den gleichen Zustand erreichen. Ist man z. B. nur daran interessiert, dass alle Prozesse terminieren, so reicht es aus, jeweils nur eine Seite der Raute zu betrachten. Genauer ist für Anweisungen zu analysieren, ob sie unabhängig voneinander sind, sie also vertauscht werden können, ohne dass es einen Einfluss auf das Verifikationsergebnis hat. Dieser Ansatz wird in SPIN „Partial Order Reduction“ genannt und kann als „Type of Run“ in der Oberfläche aus Abb. 42 eingestellt werden. Diese Reduktion kann nicht verwendet werden, wenn man an allen Zuständen interessiert ist und z. B. fordern möchte, dass nie x[0]==7 und gleichzeitig x[1]==4 gilt. Dieser in der Beispielspezifikation sicherlich erreichbare Zustand könnte bei der Reduktion wegfallen. In Abb. 40 wurde gezeigt, dass die Menge aller erreichten Zustände mit HashTabellen verwaltet werden kann. Im Beispiel ist eine kleine Hash-Tabelle mit einer größeren Anzahl von Zuständen zu sehen. Wenn man eine sehr große HashTabelle mit deutlich mehr Einträgen als Zuständen wählt, dann wird es mit zunehmender Größe der Hash-Tabelle und einer gut verteilenden Hash-Funktion immer unwahrscheinlicher, dass zwei verschiedene Zustände den gleichen HashWert haben. Die Optimierungsidee von „Supertrace / Bitstate“-Hashing, was in Abb. 41 eingestellt werden kann, ist, dass statt des Zustandes nur ein Bit zum Speichern genutzt wird. Ein Hash-Eintrag ist genau dann vorhanden, wenn dieses Bit gesetzt ist. Man spart dadurch eine Menge an Speicher, da statt eines viele Byte großen Zustandsvektors nur ein Bit in der Hash-Tabelle gespeichert werden muss. Natürlich birgt dies die Gefahr, dass zwei unterschiedliche Zustände den gleichen Hash-Wert haben und dann als gleich angesehen werden. Dies bedeutet für die Verifikation, dass ein Zustand nicht weiter verfolgt wird und so etwaige Fehler nicht gefunden werden. Im extremen Beispiel in Abb. 40 würden z. B. nur sechs Zustände betrachtet. Man kann für gut verteilende Hash-Funktionen zeigen, dass die Gefahr selbst für sehr große Zustandsmengen relativ gering ist [Hol04], da jetzt eine enorme Menge an Speicher für die Hash-Tabelle zur Verfügung steht. In SPIN gibt es noch die Optimierungsmöglichkeit, statt einer Hash-Funktion mehrere Hash-Funktionen zu wählen. Dabei wird für jede Hash-Funktion eine HashTabelle erstellt, und nur, wenn ein Zustand in allen Tabellen auf ein gesetztes Hash-Bit trifft, wird angenommen, dass es sich um den gleichen Zustand handelt. Die Anzahl der Hash-Funktionen kann mit „Nr of hash-functions in Bitstate mode“ in Abb. 42 eingestellt werden. Als weitere Möglichkeit steht die mit dem vorherigen Ansatz verwandte Variante „Hash-Compact“ als „Search-Mode“ in Abb. 41 zur Verfügung. Die Idee besteht darin, nur einen Hash-Wert zu berechnen, der allerdings aus einem sehr großen Wertebereich, z.B. 0 bis 264, stammt. Dieser Wert, der im Beispiel eine 64-Bit-Größe hat, wird dann in einer regulären Hash-Tabelle, die alle Werte aufnimmt, abgespeichert. Untersuchungen in [Hol98] zeigen, dass es bestimmte Speichergrößen
57
2 Modelchecking mit PROMELA und SPIN geben kann, die bei vollständiger Ausnutzung mit „Hash-Compact“ zu besseren Ergebnissen als mit der „Bitstate“-Technik kommen. Zusammenfassend stellt SPIN damit einen zweiphasigen Ansatz zur Behandlung von Spezifikationen mit großen Zustandsräumen zur Verfügung. Zunächst kann man versuchen, den Speicherbedarf zu reduzieren, ohne dass sich die Korrektheit der Verifikationsaussagen ändert. Im zweiten Schritt wird dann eine möglichst große Teilmenge der erreichbaren Zustände betrachtet, wobei dann einige Modelchecking-Ergebnisse kritisch hinterfragt müssen.
Obermenge der erreichbaren Zustände I1
erreichbare Zustände Teilmenge der erreichbaren Zustände x I2
x
x
F1 x
F2 x
Abb. 46: Annäherung des Zustandsraumes Abb. 46 zeigt eine dritte Möglichkeit, mit zu komplexen Spezifikationen umzugehen. Dabei wird eine Obermenge der erreichbaren Zustände betrachtet. Dies kann z. B. zur Speichereinsparung führen, wenn man sich nicht genau merken muss, dass x die Werte 1, 42 und 73 annehmen kann, sondern nur merkt, dass x alle Werte des byte-Bereichs annimmt. Diese Möglichkeit wird in SPIN nicht genutzt. Die in der Abbildung gezeigten Fehler zeigen die generelle Problematik der Teilmengen- und Obermengenbetrachtung. Der Fehler F1 wird bei der Teilmengenbetrachtung nicht gefunden, der Fehler I1 irrtümlich durch die Betrachtung der Obermenge angenommen. Komplexer werden die Überlegungen, wenn man nicht nur einzelne Zustände, sondern auch Pfade zu den Zuständen, d. h. Folgen von durchlaufenen Zuständen mit bestimmten Eigenschaften fordert, wie sie in der Abbildung als Pfade vom Startzustand zu den Zuständen I2 und F2 eingetragen sind. Der Pfad zu F2 würde bei der Obermengenbetrachtung als legal angesehen, obwohl nicht erreichbare Zustände genutzt werden. Auf der anderen Seite wird der Pfad zu I2 bei einer Teilmengenbetrachtung irrtümlich als nicht möglich angesehen.
58
2.4 Einfache Verifikationsmöglichkeiten
2.4.3
Lebendigkeit und Sicherheit Zustandsraum erlaubt
verboten
Start
erlaubte Abläufe
verbotener Ablauf
Abb. 47: Visualisierung von Sicherheit
Zustandsraum Zustandsmenge mit gewünschtem Verhalten
Start
erlaubte Abläufe
verbotener Ablauf
Abb. 48: Visualisierung von Lebendigkeit
59
2 Modelchecking mit PROMELA und SPIN Generell kann man zwei Arten von Verifikationen unterscheiden, die auch bei den Verifikationseinstellungen in Abb. 41 unterschieden werden: -
Sicherheitseigenschaften (Safety): Dies sind Eigenschaften, die das System in allen Zuständen erfüllen muss. Anschaulich wird so zugesichert, dass „nichts Schlechtes“ passiert. Zur Überprüfung muss für jeden relevanten Zustand überprüft werden, dass er die gewünschte Eigenschaft hat. Abb. 47 zeigt als Kasten alle theoretisch möglichen Zustände. Die Menge dieser Zustände kann in die Menge der erlaubten und der nicht erlaubten Zustände eingeteilt werden. Für jeden sicheren Ablauf, in der Abbildung sind zwei beispielhaft angedeutet, gilt, dass nur erlaubte Zustände genutzt werden.
-
Lebendigkeitseigenschaften (Liveness): Dies sind Forderungen an das System, dass unter bestimmten Bedingungen diese Eigenschaft erreicht werden muss. Anschaulich wird so zugesichert, dass „etwas Gutes“ passieren wird. Zur Überprüfung müssen für jeden relevanten Zustand alle möglichen Folgeabläufe analysiert werden. In der Veranschaulichung in Abb. 48 stehen die Sechsecke für Zustände, bzw. Zustandsmengen, die für „etwas tes“ stehen. Ein erlaubter Ablauf muss dann immer wieder durch ein solches Sechseck laufen, um lebendig zu sein. Lebendigkeitseigenschaften können damit nur sinnvoll für unendliche Abläufe betrachtet werden.
Bei Anforderungen muss genau beachtet werden, wie sie formuliert sind. Die Anforderung „Das System muss immer terminieren können“ kann wie folgt interpretiert werden: Das System muss immer sofort terminieren; dann ist dies eine Sicherheitseigenschaft, da Zustände individuell prüfbar sind. Ist die Interpretation, dass es in jeder Situation möglich sein soll, zu einem Zustand zu kommen, in dem das System terminieren kann, handelt es sich um eine Lebendigkeitsanforderung. Gerade bei komplexeren Anforderungen kann es vorkommen, dass Sicherheits- und Lebendigkeitseigenschaften vermischt sind. Es ist dann meist sinnvoll zu versuchen, diese Anforderungen aufzuteilen.
2.4.4
Zusicherungen
Eine Form von verifizierbaren Sicherheitseigenschaften ist die Überprüfung von Zusicherungen (Assertions). Dazu können in SPIN an beliebigen Stellen Zusicherungen der Form assert(), wie sie aus C, C++, C# und Java bekannt sind, eingebaut werden. Zusicherungen sind immer ausführbar, und bei einer Auswertung der Booleschen Bedingung nach falsch wird ein Fehler signalisiert.
60
2.4 Einfache Verifikationsmöglichkeiten byte y=0; bool b=false; active proctype Invariante(){ assert( !b || y>42) }
Abb. 49: Invariante in PROMELA Baut man Zusicherungen in einen eigenen Prozess ein, kann man damit auch Invarianten überprüfen, d. h. Bedingungen, die für jeden erreichbaren Zustand erfüllt sein sollen. Der Ausschnitt aus einer Spezifikation in Abb. 49 zeigt die Invariante, dass y immer größer 42 ist, wenn b gilt. Da beim Modelchecking alle Ablaufalternativen betrachtet werden, wird diese Zusicherung nach jedem erreichbaren Zustand einmal geprüft. Generell kann man bei der Verifikation nicht nur Variablen, sondern auch Markierungen nutzen. Neben den im Folgenden vorgestellten Markierungsarten, die eine besondere Bedeutung haben, können beliebige Markierungen, die mit einem Buchstaben beginnen, genutzt werden. byte x=0; active[3] proctype P(){ m1: do :: x<10 -> m2: x++ :: x>5 -> m3: break od } active proctype Inv(){ P[0]@m3; P[1]@m3; P[2]@m3; assert(x<=11) }
Abb. 50: Spezifikation nutzt Prozessmarkierungen Abb. 50 zeigt eine Prozessspezifikation mit drei Markierungen, von denen für die konkrete Verifikation nur eine genutzt wird. Generell wird auf Markierungen mit Prozess@Markierung zugegriffen. Das Beispiel zeigt, dass man sogar gleichnamige Prozesse über einen Index unterscheiden kann. Eine Überprüfung P@m3 ist genau dann wahr, wenn P gerade bei der mit der Markierung gekennzeichneten Zeile steht. In der im Beispiel benutzten Form bedeutet dies, dass der Prozess Inv nur von der ersten zur zweiten Marke voranschreiten kann, wenn die Prozesse nacheinander in der angegebenen Reihenfolge an den jeweiligen m3-Marken vorbeige-
61
2 Modelchecking mit PROMELA und SPIN kommen sind. Bei einer Simulation ist zu beachten, dass der Prozess Inv nicht unbedingt ausgeführt werden muss. So kann es passieren, dass die P-Prozesse alle terminieren, der Inv-Prozess aber noch keinen Schritt ausgeführt hat und auch keinen Schritt mehr ausführen kann. Die Verifikation wird für das Beispiel scheitern, da es möglich ist, dass alle drei Prozesse mit x=9 in die oberste Alternative hineingehen und x so letztendlich den Wert 12 annehmen kann. Bei der Nummer in den eckigen Klammern ist zu beachten, dass hier die Prozessnummer, also die _pid steht. Würde vor den P-Prozessen z. B. active[4] proctype Q(){…} stehen, so müsste der erste P-Prozess über P[4] angesprochen werden, da der erste P-Prozess die _pid mit dem Wert 4 hätte. Eine Spezifikation mit P[0] würde dann zur Laufzeit zu einer Fehlermeldung führen, da ein Q-Prozess die _pid mit dem Wert Null hat. bool dran=false; active proctype P(){ byte x=0; do :: x<10 && dran -> x=x+1; dran=!dran :: x>=10 -> break od } active proctype Q(){ byte x=0; do :: x<10 && !dran -> x=x+1; dran=!dran :: x>=10 -> break od } active proctype Inv(){ assert (Q:x-P:x>=0 && Q:x-P:x<=1) }
Abb. 51: Zusicherung nutzt Werte lokaler Variablen Neben Markierungen kann für Verifikationen auch lesend auf lokale Variablen anderer Prozesse zugegriffen werden. Abb. 51 zeigt dazu ein Beispiel. Durch Prozessname:lokaleVariable wird auf den Wert der lokalen Variablen zugegriffen. Im Beispiel kann man mit der Verifikation so erfolgreich prüfen, dass der x-Wert in Q immer maximal um eins größer als der x-Wert in P ist, aber nie kleiner.
62
2.4 Einfache Verifikationsmöglichkeiten Theoretisch kann der lesende Zugriff auch in beliebigen Prozessen genutzt werden. Von dieser Art der Spezifikation wird aber dringend abgeraten, da hierzu globale Variablen nutzbar sind. Spezifikationen, die außerhalb von Verifikationen direkt auf lokale Variablen zugreifen, werden wesentlich schwerer lesbar und Konzepte, wie „Scoping“ und „Information Hiding“ wären endgültig verloren.
2.4.5
Prozessterminierung
Die zweite Sicherheitseigenschaft, die mit SPIN geprüft werden kann, ist die Garantie, dass alle Prozesse sich am Ende, wenn kein Prozess mehr einen Schritt machen kann, in einem sinnvollen Endzustand befinden. Die Verifikation wird durch einen Haken bei „Invalid Endstates“ in Abb. 41 eingeschaltet. Ohne weitere Angaben wird davon ausgegangen, dass alle Prozesse dann terminieren sollen, also ihre endgültige schließende Klammer bei der Ausführung erreicht haben. Für Serverprozesse, wie z. B. der Verteiler-Prozess in Abb. 17, muss diese Annahme nicht sinnvoll sein. Server-Prozesse müssen nicht mitbekommen, wenn ein Client terminiert, sie haben typischerweise eine Ausgangsposition, von der ausgehend sie bereit sind, Aufgaben für andere Prozesse zu erfüllen. Damit ist diese Ausgangsposition ein sinnvoller Endzustand, wenn alle anderen Prozesse terminiert sind. Um einen solchen Zustand als sinnvollen Endzustand zu markieren, steht am Anfang der Zeile eine Marke, die mit end beginnt. Die Marken sollen sich in einem Prozess unterscheiden, deshalb sind beliebige Verlängerungen, wie ende, end1 oder endVerteiler erlaubt. Bei der Verifikation wird dann festgestellt, ob am Ende alle Prozesse entweder terminiert sind oder sich in einem Zustand befinden, der mit end... markiert ist. Für den Verteilerprozess aus Abb. 17 ergibt sich damit folgender Ausschnitt aus der Spezifikation: emp=0; endOK: do :: emp<prozesse && emp!=name -> toP[emp]!rec, name, wert;
2.4.6
Ausführung einfacher Verifikationen
Startet man die Verifikation für die Spezifikation aus Abb. 38 mit der Untersuchung der Sicherheitseigenschaft „Invalid Endstates“ und ausgeschalteter „Partial Order Reduction“, was hier keinen Unterschied macht, so erhält man das Ergebnis aus Abb. 52. Man erhält Angaben darüber, welcher Verifikationsauftrag an SPIN übergeben wurde, wie groß der Zustandsvektor ist, wie viele Zustände betrachtet wurden, eine Statistik über den Speicherverbrauch und Informationen über nicht ausführbare Spezifikationsanteile. Die letzte Information wurde wegen der Einstellung „Report Unreachable Code“ in Abb. 41 ausgegeben.
63
2 Modelchecking mit PROMELA und SPIN
Abb. 52: Beispielausgabe einer Verifikation Falls es Speicherprobleme geben sollte oder eine Technik genutzt wurde, die nicht alle Zustände berücksichtigt, erhält man gegebenenfalls Ratschläge zur Optimierung und Statistiken über die Qualität des gewählten Verfahrens. Wird ein Fehler gefunden, so wird eine Informationsdatei erzeugt, die dann im Simulator unter „Guided“ im „Simulation Style“ in Abb. 25 ablaufen kann und zum Fehler führt.
64
2.4 Einfache Verifikationsmöglichkeiten
Abb. 53: Ausgabe bei gefundenem Fehler Wird die Spezifikation aus Abb. 38 z. B. um die Invariante assert(x!=2 || y!=0) ergänzt und lässt man die Verifikation mit „Assertions“ laufen, so erhält man das in Abb. 53 gezeigte Ergebnis. Es wird eine Datei mit der Endung .trail und dem Namen der Spezifikationsdatei am Anfang erzeugt, die im Simulator zur Fehlersituation führt. Diese Simulation kann im zusätzlich aufgehenden Fenster direkt angestoßen werden. Weiterhin enthält dieses Fenster eine allgemeine Information, wie man eventuell zu einem kürzeren Ablauf kommen kann, der ebenfalls zum gefundenen Fehler führt. Die Information „Warning: Search not completed“ bezieht sich darauf, dass unter den Verifikationseinstellungen aus Abb. 42 eingestellt ist, dass beim ersten Fehler abgebrochen werden soll. Generell läuft die Verifikation mit SPIN nach dem in Abb. 54 gezeigten Verfahren. Ausgehend von der PROMELA-Spezifikation und den Verifikationseinstellungen entwickelt SPIN ein C-Programm zur Zustandsraumanalyse. Dieses C-Programm wird dann kompiliert und ausgeführt. Die Ausgaben werden in einem Fenster dargestellt und gegebenenfalls eine Datei mit einem Ausführungspfad zu einem Fehler erstellt. Da das Fenster für die Ausgabe relativ früh angezeigt wird, kann es etwas bis zur Ausgabe des berechneten Ergebnisses dauern. Bei länger andauernden Verifikationen werden Zwischenergebnisse über die bisher untersuchte Anzahl von Zuständen ausgegeben. Abb. 55 zeigt ein Beispiel dafür, dabei liegt hier das Hauptfenster unterhalb der Verifikationsausgabe, und man kann unten erkennen, dass die vergangene Zeit jeweils im Minutenabstand angezeigt wird. Die Ausgabe gehört zur Analyse der Spezifikation aus Abb. 44 mit sechs Prozessen.
65
2 Modelchecking mit PROMELA und SPIN
PROMELA-Spezifikation
SPIN
C-Programm
kompilieren und ausführen
Verifikationseinstellung
Abb. 54: Verifikationsprozess mit SPIN
Abb. 55: Ausgabe bei längeren Verifikationsläufen
66
Ausgabe
Pfad zum Fehler
2.4 Einfache Verifikationsmöglichkeiten
2.4.7
Nachweis von Lebendigkeitseigenschaften bool guard=true; byte x=1; active proctype P1(){ do :: x<10 -> x=x+1; guard=!guard :: x>1 -> x=x-1; guard=!guard :: guard=!guard od; } active proctype P2(){ progress: do :: x<10 -> x=x+1; guard=!guard :: x>1 -> x=x-1; guard=!guard :: guard=!guard od; } active proctype P3(){ do :: guard -> progress: guard=!guard od; }
/* 1 */
/* 2 */
Abb. 56: Spezifikation zur Analyse von Lebendigkeit Zur Analyse der Verifikationsmöglichkeiten zur Lebendigkeit wird die Spezifikation aus Abb. 56 genutzt. Die Prozesse P1 und P2 sind inhaltlich identisch und wurden für die weiteren Betrachtungen als getrennte Spezifikationen aufgeschrieben. Alle Prozesse laufen beliebig lang. Es handelt sich um ein nicht-terminierendes System, wie es z. B. bei Steuerungsanlagen von Ampeln der Fall ist. P1 und P2 können immer neue Schritte machen, den Wert von x beliebig zwischen 0 und 11 ändern und den Booleschen Wert von guard auf false oder true umschalten. Der Prozess P3 kann nur dann ausgeführt werden, wenn die Boolesche Variable guard gesetzt ist, danach wird sie wieder auf false gesetzt. P3 ist damit nicht immer, aber immer wieder ausführbar. Für nicht-terminierende Systeme gibt es statt der Forderung nach Terminierung die Forderung, dass sie immer einen Fortschritt machen, also „etwas Sinnvolles“ passiert. In einem typischen System ohne Fortschritt finden zwar jede Menge Arbeitsschritte statt, allerdings ohne den Gesamtzustand zu ändern. Konkret können das Systeme sein, in denen jeder Prozess immer fragt, ob er eine Ressource nutzen darf, und immer wieder die Antwort bekommt, dass dies nicht möglich ist. Diese zu einem Deadlock verwandte Situation wird auch Livelock genannt. Bei
67
2 Modelchecking mit PROMELA und SPIN mehreren Prozessen kann sich auch eine Teilmenge der Prozesse in einem partiellen Livelock befinden. Um in PROMELA sinnvollen Fortschritt zu kennzeichnen, erhalten die zugehörigen Befehle eine Progress-Markierung. Diese Markierungen beginnen mit „progress“ und können genau wie „end“-Markierungen danach einen beliebigen Text enthalten. Innerhalb eines Prozesses müssen sich die „progress“-Markierungen im Namen unterscheiden. In der Beispielspezifikation sind zwei Befehle als Fortschritt markiert. Eine Lebendigkeitsforderung ist, dass alle nicht-terminierenden Ausführungspfade unendlich oft eine „progress“-Markierung durchlaufen, es also keine so genannten non-progress-cycles gibt. Führt man eine Verifikation nur mit den Optionen „Liveness“ und „Non-Progress Cycles“ durch, so sieht ein Ausschnitt des Ergebnisses wie folgt aus: pan: non-progress cycle (at depth 50) pan: wrote pan_in.trail
2:22 | | |>(guard) 2:23 | | |>guard = !(guard) 1:14 | |>((x<10)) 1:14 | |>x = (x+1) <<<<<START OF CYCLE>>>>> 0:8 |>guard = !(guard) 0:8 |>guard = !(guard) 2:21 | | |>1:14 | |>0:5 |>-
Abb. 57: Gefundener Non-Progress-Cycle Die Lebendigkeitsanforderung wurde also verletzt. Statt sich den zum Fehler gehörenden Ablauf anzusehen, kann die Verifikation mit einer geringeren Suchtiefe wiederholt werden. Im konkreten Fall reicht mit etwas Experimentieren die Tiefe 15 als „Maximum Search Depth“ in Abb. 42 aus. Das Ende der zugehörigen Time Sequence ist in Abb. 57 dargestellt. Man sieht, dass nach anfänglichen Berechnungen nur noch P1 als links dargestellter Prozess Berechnungen durchführt und immer die letzte Alternative ausgewählt wird. Für ein realistisches System, bei dem die Prozesse auf unterschiedlichen Rechnern laufen, stellt sich die Frage, ob dieser Zyklus realistisch ist. Zwar sind Zeitannahmen in verteilten Systemen immer schwierig zu fassen, allerdings gibt es wenige Gründe, warum ein Prozess überhaupt nicht laufen sollte. Diese Überlegung führt zur Definition des Begriffs Fairness für Prozesse. Definition (Fairness): Gegeben sei ein System aus mehreren parallel laufenden Prozessen. Ein unendlicher Ablaufpfad besteht aus den Zustandsände-
68
2.4 Einfache Verifikationsmöglichkeiten rungen, die schrittweise jeweils von einem Prozess durchgeführt werden. Ein Ablaufpfad heißt schwach fair, wenn jeder Prozess, der unendlich lang einen Schritt ausführen könnte, im Ablaufpfad auch einen Schritt ausführt. Ein Ablaufpfad heißt stark fair, wenn ein Prozess, der immer wieder einen Schritt ausführen könnte, im Ablaufpfad auch einen Schritt ausführt.
ab hier: P3 immer wieder ausführbar ab hier: P2 immer ausführbar ausführbare Prozesse:
P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P2 P3
P2 P2 P2 P2 P2 P2 P2 P2 P3
P3
...
P3
unfairer Pfad
P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P1
...
schwach fairer, nicht stark fairer Pfad
P1 P1 P1 P1 P1 P1 P2 P1 P1 P2 P1 P1
...
stark fairer Pfad
P1 P1 P1 P1 P1 P2 P1 P3 P1 P2 P1 P3
...
Abb. 58: Veranschaulichung von Fairness Abb. 58 veranschaulicht die verschiedenen Fairness-Begriffe. Oben sind die Prozesse genannt, die im aktuellen Zustand einen Schritt ausführen könnten. Der erste Pfad ist unfair, da P2 immer fortschreiten könnte, aber nie zum Zuge kommt. Der zweite Pfad ist schwach fair, da P1 und P2 immer wieder fortschreiten. Der Pfad ist aber nicht stark fair, da P3 immer wieder fortschreiten könnte, aber nie fortschreitet. Diese Eigenschaft hat aber der dritte stark faire Pfad. Die Realisierung von Fairness, z. B. auch auf Ein-Prozessor-Systemen, ist aufwändig, da man sich für schwache Fairness merken muss, wer immer einen Schritt machen könnte. Für starke Fairness wird es noch komplexer, da das „immer mal wieder könnte der Prozess“ beachtet werden muss. Typische Lösungen umfassen eine oder mehrere Warteschlangen, in denen mögliche fortschreitende Prozesse verwaltet werden. Für verteilte Systeme ist zumindest die schwache Fairness eine sinnvolle Annahme, die auch von SPIN unterstützt wird und bei den Verifikationseinstellungen in Abb. 41 mit „With Weak Fairness“ eingefordert werden kann. Starke Fairness wird in SPIN nicht unterstützt.
69
2 Modelchecking mit PROMELA und SPIN Führt man die Verifikation für die Spezifikation aus Abb. 56 mit dieser Option durch, läuft sie problemlos ab. Löscht man die „progress“-Markierung in der mit /* 1 */ markierten Zeile, so bleibt nur die Markierung in P3 übrig. Für P3 gilt allerdings, dass P3 nicht immer ausgeführt werden kann, dafür aber immer wieder, da spätestens nach zwei Durchläufen in P1 oder P2 guard den Wert true haben muss. Da die hier notwendige starke Fairness nicht in SPIN implementiert ist, findet die Verifikation einen schwach, aber nicht stark fairen Pfad mit einem Zyklus ohne „progress“-Markierung. Neben den „progress“-Markierungen gibt es noch die „accept“-Markierungen, deren Suche mit „Acceptance Cycles“ in Abb. 41 eingeschaltet wird. Für „Acceptance Cycles“ gibt es die genau gegenteiligen Anforderungen wie für „Non-Progess Cycles“: jeder unendliche Pfad darf nur endlich oft durch eine „accept“-Markierung laufen. Dabei spielt wieder Fairness eine wichtige Rolle. Diese Markierungen werden selten benutzt, um Anforderungen direkt zu formulieren. Wir werden sie später bei so genannten Never-Claims und der Umsetzung von LTL-Formeln als hilfreich kennen lernen.
2.4.8
Trace-Zusicherungen mtype={send1,send2,ack1,ack2}; chan c12 = [0] of {mtype,byte}; chan c21 = [0] of {mtype,byte}; chan c23 = [0] of {mtype,byte}; chan c32 = [0] of {mtype,byte}; active proctype P1(){ byte i=1; end: do :: i<=10; c12!send1(i); c21?ack1(_); i=i+1; od; } active proctype P2(){ byte x; end : do :: c12?send1(x); if :: x%2==1 -> c21!ack1(x); :: x%2==0 -> c23!send2(x); c32?ack2(x); c21!ack1(x); fi;
70
2.4 Einfache Verifikationsmöglichkeiten od; } active proctype P3(){ byte x; end: do :: c23?send2(x); c32!ack2(x); od; }
Abb. 59: Kommunikationsprotokoll zur Trace-Untersuchung Möchte man ausschließlich das Kommunikationsverhalten einer Spezifikation genauer analysieren, so sind Trace-Zusicherungen sehr hilfreich, die verwandt mit regulären Ausdrücken und Automaten sind. Mit ihnen legt man die gewünschte Reihenfolge der Kommunikationen fest. In der Spezifikation in Abb. 59 ist festgelegt, dass P1 eine Information mit send1 an P2 sendet. P2 kann entweder direkt mit einer Bestätigung ack1 antworten oder die Information z. B. mit send2 zur Überprüfung an P3 weiterleiten. P3 bestätigt den Nachrichtenempfang seinerseits mit einem ack2, das mit ack1 an P1 weitergeleitet wird. P1 überträgt dabei die Zahlen von 1 bis 10, wobei alle geraden Zahlen an P3 weitergeleitet werden. Trace-Zusicherungen werden einfach in der Spezifikation ergänzt. Man gibt mit den üblichen Sprachkonstrukten if und do mögliche Kommunikationsabläufe an, wobei der Fokus ausschließlich auf der Kanalnutzung liegt, jeder Schritt muss ein Kommunikationsereignis sein. Es ist kein Zugriff auf globale Variablen erlaubt, noch können sonst Variablen genutzt werden. Weiterhin ist der Ersteller der TraceZusicherung dafür verantwortlich, dass die Zusicherung deterministisch ist, es also immer eindeutig ist, welche Kommunikationen als nächstes erwartet werden können. Für einen asynchronen Kanal c kann man das Senden c! und das Empfangen c? beobachten. Bei synchronen Kommunikationen ist nur die Beobachtung des Empfangens c? als durchgeführte Kommunikation möglich. trace{ do :: c12?send1(_); c21?ack1(_); od; }
Abb. 60: Beispiel für Trace-Zusicherung Die Trace-Zusicherung in Abb. 60 fordert, dass c12 und c21 immer abwechselnd genutzt werden und dabei send1 und ack1 nutzen, was durch einen Verifikationslauf geprüft werden kann. Wichtig ist, dass sich die Trace-Zusicherung nur auf die Kanäle bezieht, die mindestens einmal in der Trace-Zusicherung vorkommen. Wann z. B. auf c23 kommuniziert wird, spielt für die Zusicherung keine Rolle. Tra-
71
2 Modelchecking mit PROMELA und SPIN ce-Zusicherungen laufen parallel synchron zur eigentlichen Ausführung der Spezifikation, wobei die Ausführung von den unter Beobachtung stehenden Kanälen abhängt. Jedes Mal, wenn eine Kommunikation mit c12 oder c21 stattfindet, macht auch die Trace-Zusicherung einen Schritt.
c12?send1(_) z1
z2 c21?ack1(_)
Abb. 61: Automat zur Trace-Zusicherung Man kann sich die Trace-Zusicherung wie einen endlichen Automaten vorstellen, wie er in Abb. 61 dargestellt ist. Falls eine Kommunikation auf einem Kanal passiert, der in der Trace-Zusicherung betrachtet wird, und der Automat den Schritt nicht mitmachen kann, wurde ein Fehler gefunden. Alternativ hätte für diesen Fall ein Fehlerzustand im Automat ergänzt werden können, der nicht mehr verlassen werden kann. Innerhalb der Trace-Spezifikation können auch „end“, „progress“ und „accept“Markierungen mit den bekannten Effekten genutzt werden. trace{ do ::c12?send1(_); c23?send2(_) od }
Abb. 62: Nicht erfüllbare Trace-Zusicherung Jede Spezifikation darf nur eine Trace-Zusicherung enthalten. Wird die Zusicherung aus Abb. 60 gegen die Zusicherung aus Abb. 62 ausgetauscht, die fordert, dass immer abwechselnd auf c12 mit send1 und auf c23 mit send2 kommuniziert wird, und ein Verifikationslauf gestartet, erhält man ein Gegenbeispiel in der üblichen Form. Trace-Zusicherungen können nicht für Kanal-Arrays genutzt werden.
2.4.9
Never-Claims
Während man mit Trace-Zusicherungen die Kommunikationen auf den Kanälen beobachten kann, dienen die so genannten Never-Claims dazu, das Verhalten der globalen Variablen zu beobachten. Ähnlich wie Trace-Zusicherungen laufen Ne-
72
2.4 Einfache Verifikationsmöglichkeiten ver-Claims eng verwoben mit der Spezifikation ab. Genauer macht zunächst der Never-Claim, dann die Spezifikation, dann wieder der Never-Claim, dann die Spezifikation usw. jeweils einen Schritt. Dies ist ein enges Interleaving, bei dem sich beide kontinuierlich abwechseln, wobei der Never-Claim beginnt. NeverClaims sind dabei flexibler als Trace-Zusicherungen, da sie Nichtdeterminismus enthalten dürfen. Eine Besonderheit der Never-Claims ist es, dass sie unerwünschtes Verhalten beschreiben, also Gegenbeispiele zum eigentlich spezifizierten Verhalten beinhalten. Typisch ist hier auch die Verwendung von „accept“Markierungen. Im folgenden Teilkapitel 2.5 wird weiterhin gezeigt, dass man Never-Claims auch aus Logik-Formeln automatisch ableiten lassen kann. Ein NeverClaim ist erfolgreich, d. h. findet einen Fehler, wenn er entweder terminiert oder unendlich oft durch accept-Markierungen laufen kann.
Abb. 63: Ablauf beim Never-Claim Der Ablauf bei der Verifikation ist in Abb. 63 skizziert. Zunächst werden alle globalen Variablen initialisiert, alle Prozesse gestartet und deren lokale Variablen initialisiert. Bei der Initialisierung ist zu beachten, dass byte x und byte x=1 beides Initialisierungen sind. Bei byte x; x=1 handelt es sich um eine am Anfang ausgeführte Initialisierung und eine später durchgeführte Anweisung. Danach läuft folgender Zyklus ab: Zunächst wird geprüft, ob der Never-Claim terminiert ist, was einem gefundenen Gegenbeispiel entspricht. Dann wird geprüft, ob der Never-Claim einen Schritt machen kann. Ist das nicht der Fall, wurde hier kein Ge-
73
2 Modelchecking mit PROMELA und SPIN genbeispiel gefunden und die Untersuchung dieses Ablaufs beendet. Kann ein Schritt gemacht werden, wird geprüft, ob ein „accept“-Zyklus vorliegt, was einem gefundenen Gegenbeispiel entspricht. Ohne Zyklus kann die Spezifikation, wenn möglich, einen Schritt machen, und die Kontrolle geht wieder über zum NeverClaim, der auch bei terminierter Spezifikation weitere Schritte machen kann. Man beachte, dass das Ausführen eines Schritts jeweils nichtdeterministisch erfolgt und so jeweils mehrere Alternativen untersucht werden. byte x=0; active proctype P(){ x=1 } never{ x==1 }
Abb. 64: Never-Claim findet kein Gegenbeispiel Das „Ping-Pong-Spiel“ zwischen Never-Claim und Spezifikation kann man durch folgende Beispiele verdeutlichen. In der Spezifikation in Abb. 64 muss der NeverClaim, wie immer, den ersten Schritt machen. Da am Anfang x den Wert Null hat, ist dies nicht möglich, deshalb kann der Never-Claim nicht voranschreiten und damit kein Gegenbeispiel konstruieren. Die Verifikation läuft erfolgreich ohne Fehler durch. byte x=3; active proctype P(){ x=1 } never{ x==3; x==1 }
Abb. 65: Never-Claim findet ein Gegenbeispiel Das Beispiel in Abb. 65 zeigt einen Never-Claim, der vollständig durchläuft und damit einen Fehler findet. Wichtig ist, dass die Deklaration und initiale Zuweisung an globale Variablen vor der eigentlichen Ausführung passiert. Damit hat x den Wert drei und der Never-Claim kann seinen ersten Schritt machen, danach macht P seinen ersten Schritt und der Never-Claim den zweiten Schritt. Letztendlich terminiert P und auch der Never-Claim, so dass ein unerwünschter Ablauf gefunden wurde.
74
2.4 Einfache Verifikationsmöglichkeiten byte x=3; active proctype P(){ x=1 } never{ x==3; x==1; x==1; x==1 }
Abb. 66: Never-Claim bei terminierender Spezifikation Einen Spezialfall untersucht die Spezifikation in Abb. 66, in der der Prozess P vor dem Never-Claim terminiert. In diesem Fall wird der Never-Claim weiter ausgeführt und nach einem Gegenbeispiel gesucht. In unserem Fall kann der NeverClaim dann terminieren und findet damit ein Gegenbeispiel. byte x=3; active proctype P(){ x=1; } never{ x==3; do :: x==1 -> accept: skip :: true -> skip od }
Abb. 67: Never-Claim mit accept-Markierung Abb. 67 zeigt eine Variante von Abb. 66, bei der der Never-Claim eine acceptMarkierung enthält. Wieder terminiert P und danach existiert die Möglichkeit, immer wieder durch die „accept“-Markierung zu laufen, da x den Wert Eins hat. Damit ist wieder ein Gegenbeispiel gefunden. Bei der Verifikation muss in Abb. 41 „Apply Never Claim“ gesetzt werden. Für die Spezifikation in Abb. 68 soll gelten, dass immer der Wert der Variablen zustand gleich ok bzw. wenn dies nicht der Fall ist, die Variable alarm ab dann immer den Wert rot hat. Die Spezifikation zeigt auch, dass mtype als Aufzählungstyp
für andere Werte als Nachrichtennamen genutzt werden kann.
75
2 Modelchecking mit PROMELA und SPIN #define p (zustand==ok) #define q (alarm!=rot) mtype={ok,nok,gruen,rot}; mtype zustand=ok; mtype alarm=gruen; byte stand=50; active proctype Rauchmelder(){ zustand=ok; start: if :: stand>100 && zustand==ok; atomic{ zustand=nok; alarm=rot } :: else -> skip fi; if :: stand >20 -> stand=stand-1 :: stand <120 -> stand=stand+1 fi; goto start } never{ do :: (!p && q) -> break :: (!p) -> do :: q -> break :: true od; break :: true od }
Abb. 68: Spezifikation mit Never-Claim Zur Erstellung des Never-Claims muss man sich das möglichst allgemeinste Gegenbeispiel ausdenken. Dies hat die Form, dass zunächst beliebig lang zustand den Wert ok hat und dann, wenn irgendwann zustand nicht mehr ok ist, alarm zu diesem Zeitpunkt (!p && q) oder irgendwann später, überprüft in der inneren do-Schleife, nicht den Wert rot hat. In diesem Fall terminiert der Never-Claim, was neben einem unendlichen „Acceptance Cycle“ die zweite Möglichkeit für einen erfolgreichen Never-Claim, also einen gefundenen Fehler, ist. Der Never-Claim findet in diesem Beispiel keinen Fehler. Würde man den atomic-Block in Rauchmelder auflösen, würde ein Fehler gefunden. Durch die mit true beschriebenen Alternativen hat der Never-Claim die Möglichkeit, an eine beliebige Stelle in der Spezifikationsausführung zu laufen, um da eine Überprüfung zu beginnen.
76
2.5 Verifikation von in LTL formulierten Anforderungen
2.5 Verifikation von in LTL formulierten Anforderungen Die Erstellung von Never-Claims mit der Suche nach dem allgemeinsten Gegenbeispiel ist sehr aufwändig und entspricht meist nicht den Gedankengängen von Spezifizierern, wobei es an einigen Stellen hilfreich sein kann, wenn man in der Lage ist, klare Gegenbeispiele zu definieren. Trotzdem muss es einen einfacheren Weg geben, Anforderungen positiv zu formulieren. Der auf Pnueli [Pnu77] zurückgehende Ansatz ist, Anforderungen mit Hilfe der formalen Logik zu formulieren. Im Fall von SPIN wird die Lineare Temporale Logik (LTL) genutzt. Die Logik basiert auf Prädikaten, wie sie bereits aus assertZusicherungen bekannt sind. Diese Prädikate beziehen sich typischerweise immer nur auf einen Zustand des Systems, wobei für SPIN bereits bekannt ist, dass man mit Zusicherungen auch Invarianten, wie in Abb. 49 gezeigt, spezifizieren kann. Um den Aufbau von LTL-Formeln zu erleichtern, müssen in SPIN alle zusammengesetzten Prädikate, also Prädikate, die Und (&&) oder Oder (||) enthalten, als einfaches Prädikat in einer #define-Anweisung zusammengefasst werden. Dies wurde in der Spezifikation in Abb. 68 bereits mit p und q gezeigt, wobei als Prädikatsnamen natürlich auch sprechendere Namen erlaubt sind. Lebendigkeitsanforderungen beziehen sich auf ganze Ausführungspfade und nicht nur auf einen Zustand. Häufig wird ab einer bestimmten Situation ein bestimmtes Folgeverhalten in der Zukunft verlangt. Hierfür wird der „lineare“ und „temporale“ Anteil der Logik benötigt. Der „temporale“ Anteil steht für den zeitlichen Ablauf, da alle Zustände zeitlich nacheinander durchlaufen werden. Das „lineare“ betont, dass immer ein Ausführungspfad betrachtet wird. In jedem Zustand kann es mehrere Folgezustände geben, diese führen dann zu verschiedenen Ausführungspfaden, die getrennt betrachtet werden. Für diese neuen Logikaspekte werden auch neue Sprachkonstrukte benötigt, die jetzt vorgestellt werden. Definition (Syntax der Linearen Temporalen Logik (LTL)): Zunächst sind alle einfachen Prädikate (auch aussagenlogische Formeln genannt) LTLFormeln. Seien weiterhin p, q und r LTL-Formeln, dann sind auch 1.
p , heißt „always p“, immer p
2. ¡ p , heißt „eventually“, irgendwann p 3. X p , heißt „next“, danach p 4. p U q , heißt „p until q“, p solange bis q syntaktisch korrekte LTL-Formeln. Neue LTL-Formeln entstehen weiterhin durch die Verwendung der bekannten logischen Operatoren , , , o und l. Klammern können genutzt werden, um die Auswertungsreihenfolge vorzugeben. Es gelten sonst die Ausführungsprioritäten aus Abb. 6.
77
2 Modelchecking mit PROMELA und SPIN
Zeit LTL-Formel
z0 z1 z2 z3 z4 z5 z6 z7 ... Pfad
p
p
p
p p p p p p p p ...
.
.
.
.
.
.
. ...
¡p
.
.
.
.
p .
. ...
Xp
. p .
.
.
.
.
. ...
p p p p p .
.
. ...
.
.
. ...
pUq (stark, SPIN)
pUq
(schwach)
auch
.
.
.
.
.
q
p p p p p p p p ... .
.
.
.
.
.
.
. ...
Abb. 69: Veranschaulichung der LTL-Semantik Abb. 69 veranschaulicht die verschiedenen temporalen Operatoren. Wichtig ist, dass sich die Anforderungen immer auf eine unendliche Folge von Zuständen, in der Abbildung Pfad genannt, beziehen. Die Abbildung zeigt jeweils Pfade, die dazu führen, dass die LTL-Formel auf der linken Seite erfüllt wird. Eine Formel ohne die temporalen Quantoren und ¡ ist erfüllt, wenn sie im Startzustand erfüllt ist. Die Punkte in den Kästen stehen für „beliebig“. Dies bedeutet, dass es für die Erfüllung der Anforderung unerheblich ist, ob p wahr oder falsch ist. „Always“ bedeutet, dass in allen Zuständen des Pfades die Eigenschaft gelten muss. Ein „Eventually“ wird erfüllt, wenn irgendein Zustand des Pfades die Eigenschaft p hat. Ein „Next“ bedeutet, dass der Zustand nach dem Startzustand die Eigenschaft p haben muss. Beim „Until“-Operator gibt es zwei Varianten, die eng mit den Fairnessbetrachtungen verknüpft sind. Bei der starken Variante des UntilOperators wird gefordert, dass q letztendlich auch eintrifft. Deshalb ist in der Abbildung nur ein erfüllender Pfad eingezeichnet. Der schwache Until-Operator wird erfüllt, wenn die starke Variante erfüllt ist oder die Bedingung p immer gilt. In der folgenden Semantik werden beide Varianten des Until-Operators vorgestellt, um zu zeigen, wie genau man sich mit der Semantik beschäftigen muss, wenn man eine Anforderung formulieren und Anforderungen anderer verstehen will. In der Literatur werden die beiden Until-Operatoren auch syntaktisch leicht unterschiedlich als U für die schwache und U für die starke Variante dargestellt. SPIN unterstützt nur das starke Until, deshalb wird hier keine Unterscheidung benötigt. Ab
78
2.5 Verifikation von in LTL formulierten Anforderungen jetzt steht ein U immer für ein starkes Until. Weiterhin wird in SPIN der NextOperator standardmäßig nicht unterstützt, da man sonst zunächst eine weitere Eigenschaft der Spezifikation, nämlich Stotterfreiheit [Hol04] als Spezifizierer garantieren müsste. Experten, die sich tiefer in SPIN einarbeiten, werden Optionen finden, mit denen der Next-Operator mit der Warnung vor nicht stotterfreien Spezifikationen eingeschaltet werden kann. Diese Details werden hier nicht weiter verfolgt. Die genaue Semantik von LTL-Formeln wird in der folgenden Definition festgelegt. Definition (Semantik von LTL-Formeln): Gegeben sei eine PROMELASpezifikation P und ein unendlicher Ausführungspfad z der Form z0 z1 ... zi ... von Zuständen einer Ausführung von P, wobei jeder Zustand jeder Variablen einen Wert zuordnet. Die Funktion Sem(,) zur Berechnung der Semantik einfacher Prädikate wertet die Prädikate zusammen mit den konkreten Werten für die Variablen nach wahr oder falsch aus (ein Zustand z ordnet jeder Variable einen Wert zu, z. B. z(a)=3; z(b)=4; dann z. B. Sem(a < b, z) { z(a) < z(b) { 3 < 4 { true, wobei { die semantische Äquivalenz bezeichnet, also beide Ausdrücke bei einer Auswertung immer den gleichen Wahrheitswert liefern) . 1. Sei p eine einfaches Prädikat, dann erfüllt z die LTL-Formel p, wenn Sem(p,z0)=wahr gilt, also der erste Zustand p erfüllt. 2. Sei p eine LTL-Formel, dann erfüllt z diese LTL-Formel, wenn alle Zustände p erfüllen, also für alle i Sem(p,zi)=wahr gilt. 3. Sei ¡ p eine LTL-Formel, dann erfüllt z diese LTL-Formel, wenn ein Zustand p erfüllt, also es ein i mit Sem(p,zi)=wahr gibt. 4. Sei X p eine LTL-Formel, dann erfüllt z diese LTL-Formel, wenn im folgenden Zustand p erfüllt ist, also Sem(p,z1)=wahr gilt. 5. Sei p U q eine LTL Formel, dann erfüllt z die starke Variante des UntilOperators, wenn es einen Zustand zj gibt, so dass für alle Zustände zi mit i<j Sem(p,zi)=wahr gilt und Sem(q,zj)=wahr gilt. 6. Sei p U q eine LTL Formel, dann erfüllt z die schwache Variante des UntilOperators, wenn die starke Variante erfüllt ist oder wenn alle Zustände p erfüllen, also für alle i Sem(p,zi)=wahr gilt. Die schwache Variante des Until-Operators bezieht sich auf die schwache Fairness. Die rekursive Definition fordert, dass irgendwann in einem Zustand q und bis dahin p gilt. Das „bis dahin“ bedeutet aber in der schwachen Variante, dass dieses nie eintreffen muss; in diesem Fall muss aber immer p erfüllt sein. Dies wurde auch in Abb. 69 veranschaulicht, wo beide Varianten skizziert sind, wie die Formel erfüllt werden kann.
79
2 Modelchecking mit PROMELA und SPIN Da LTL-Formeln auch verschachtelte Temporal-Operatoren zulassen, ist es möglich, recht komplexe Anforderungen zu formulieren, die teilweise aber schwer verständlich sein können. Häufiger kann die Visualisierung von Beispielabläufen, wie in Abb. 69 gezeigt, beim Verständnis helfen. Weiterhin hat die Praxis gezeigt, dass viele Anforderungen einen ähnlichen Aufbau haben und man mit dem Verständnis für einige Schablonen schon recht weit kommen kann. Einige der typischen Anforderungsformen sollen jetzt hier diskutiert werden. Eine häufig anzutreffende Form ist die Invariante, mit der gefordert wird, dass eine Eigenschaft p immer gelten muss. Neben der bisher in Abb. 49 gezeigten Möglichkeit zur Formulierung einer Invarianten geht dies auch mit einer Formel der Form p
(Invariante)
In Kommunikationsprotokollen ist es häufig der Fall, dass man für eine versandte Information eine Antwort, z. B. eine Bestätigung, erhalten möchte. Wird das Versenden im Prädikat p und der Empfang in q festgehalten, so ist die Forderung für eine einzelne Nachricht p o ¡q
(Antwort)
Da man immer eine Antwort erhalten will, handelt es sich um eine Invariante, so dass die gesuchte Formel (p o ¡q)
(Senden ƺ Bestätigen)
lautet. Eine kritische Betrachtung der Semantiken der letzten beiden Formeln zeigt, dass diese auch erfüllt werden, wenn q zum gleichen Zeitpunkt wie p gilt. Möchte man dies ausschließen, muss man den Next-Operator nutzen, da sonst kein Bezug zu einem nachfolgenden Zustand aufgebaut werden kann, die Formel würde dann (p o X(¡q)) lauten. Wenn man möchte, dass eine bestimmte Eigenschaft p immer wieder erreicht wird, da durch p z. B. der Fortschritt des Systems beschrieben wird, so lautet die Forderung zunächst ¡p, damit p einmal erfüllt wird. Der kontinuierliche Fortschritt wird dann wieder durch eine Invariante festgelegt: (¡ p)
(Fortschritt)
Eine andere typische Anforderung ist, dass ein System nach einer Berechnung ein Ergebnis hat und mit diesem dann weiter arbeitet. Dies ist die Forderung nach Stabilität. Wenn die abgeschlossene Berechnung durch p beschrieben wird, soll ab einem bestimmten Zeitpunkt immer p erfüllt sein. Dies wird durch ¡ ( p)
(Stabilität)
formalisiert. Typisch ist auch die Forderung, dass solange eine Eigenschaft p erfüllt ist, eine andere Eigenschaft q nicht gelten soll. Dies ist wieder eine Invariante und hat die Form (p o q)
80
(Ausschluss)
2.5 Verifikation von in LTL formulierten Anforderungen Die letzte Anforderung kann noch verallgemeinert werden zum wechselseitigen Ausschluss, so dass immer nur eine der beiden Eigenschaften erfüllt ist. (p l q) (wechselseitiger Ausschluss)
Abb. 70: SPIN-Fenster zur Eingabe von LTL-Formeln
81
2 Modelchecking mit PROMELA und SPIN Anmerkung: Für LTL-Formeln gelten einige Rechenregeln, die den Umgang mit den Formeln erleichtern können. In der folgenden Aufzählung steht { wieder für Äquivalenz und bedeutet, dass man die linke in die rechte Seite und die rechte in die linke Seite umformen kann. ( p)
{
¡ (p)
(¡ p)
{
(p)
(p q)
{
( p) ( q)
¡ (p q)
{
(¡ p) (¡ q)
¡p
{
true U p
¡ (p q)
{
(¡ p) (¡ q)
¡ (p q)
{
( ¡ p) ( ¡ q)
p U (q r)
{
(p U q) (p U r)
(p q) U r
{
(p U r) (q U r)
In SPIN gibt es zwei Möglichkeiten, zur Eingabe von LTL-Formeln zu kommen. Einmal kann unter „Run..“ mit „LTL Property Manager..“ direkt zur Eingabemaske in Abb. 70 gelangt werden. Der andere Weg geht über die Auswahl „[Verify an LTL Property]“ in Abb. 41. Egal welcher Weg gewählt wird, es ist wichtig, die eingegebene Formel mit „Save As..“ rechts unten abzuspeichern, wobei die Formeln getrennt von der Spezifikation gespeichert werden. In der Eingabemaske gibt es die Möglichkeit, LTL-Formeln einzugeben oder die Symbole durch die Knopfleiste „Operators:“ schrittweise zu erzeugen. Dabei wird die in Abb. 71 angegebene Umsetzung der Logik-Symbole in ASCII-Zeichen genutzt. LTL-Formel p p ¡p pUq p poq plq pq pq
ASCII-Darstellung p [] p <> p p U q !p p -> q p <-> q p && q p || q
Abb. 71: LTL-Formeln in ASCII-Darstellung
82
2.5 Verifikation von in LTL formulierten Anforderungen Schablonenname
Formel
Invariance(p)
[] (p)
Response(p,q)
[] ((p) -> (<> (q)))
Precedence(p,q,r)
[] ((p) -> ((q) U (r)))
Objective(p,q,r)
[] ((p) -> <>((q) || (r)))
Abb. 72: LTL-Formelschablonen in SPIN In „Notes“ kann der Nutzer Notizen zu der entwickelten Formel eintragen. Der Standardeintrag „Use Load to open a file or a template“ deutet an, dass man entweder eine schon existierende Formel laden kann oder dass es möglich ist, eine Schablone für den typischen Aufbau einer Formel zu laden. Dabei ist die Auswahl mit den vier in Abb. 72 gezeigten Schablonen relativ gering. Im Feld „Symbol Definitions“ sind die Definitionen der in der Formel genutzten Prädikate einzutragen, dies geschieht in der bekannten Form z. B. durch #define p (zustand==ok && alarm==gruen)
In der Zeile „Property holds for“ wird festgelegt, ob es sich bei der angegebenen Anforderung um eine Formel handelt, die erfüllt werden muss, also „desired behaviour“ oder die niemals erfüllt werden darf, also „error behaviour“. Wir betrachten nur die erste Variante. Ein wichtiges Forschungsergebnis zu LTL-Formeln ist, dass man sie in Automaten übersetzen kann [WVS83], wobei die Kanten mit einfachen Prädikaten markiert sind, die zu Zustandsänderungen führen. Genauer handelt es sich beim Resultat um einen so genannten Büchi-Automaten [Büc60], der für unendliche Ablaufpfade spezifiziert, welche erlaubt sind und welche nicht. Dieser Ansatz wird in SPIN zur automatischen Übersetzung der Formel in einen Never-Claim genutzt, der genau diesem Automaten entspricht. Zu beachten ist, dass ein Never-Claim das maximale nicht gewünschte Verhalten spezifiziert. Der durch den Klick auf „generate“ erhaltene Never-Claim kann dann in der gewohnten Form zur Verifiation eingesetzt werden. Mit „Run Verification“ besteht die Möglichkeit, für die aktuell geladene Spezifikation die Verifikation direkt aus diesem Fenster zu starten. Insgesamt sind LTL-Formeln aus der Sicht von SPIN nur ein komfortabler Weg zur Erstellung von Never-Claims. Abb. 73 zeigt das Ergebnis der Übersetzung der Response-Schablone, mit der immer gefordert wird, dass, wenn p stattfindet, danach irgendwann auch garantiert q stattfindet. Die Definitionen von p und q wurden offen gelassen und müssten noch ergänzt werden. Die Klammern sollen sicherstellen, dass die gewünschte Auswertungsreihenfolge eingehalten wird, wobei eventuell überflüssige Klammern stehen, die allerdings nur die Lesbarkeit etwas stören.
83
2 Modelchecking mit PROMELA und SPIN
Abb. 73: Beispielübersetzung einer LTL-Formel Der generierte Never-Claim zeigt die allgemeinste Form eines Gegenbeispiels, das durch die unendliche Durchlaufmöglichkeit durch die „accept“-Marke beschrieben wird. Um dies zu erreichen, muss zumindest einmal die Situation auftreten, dass p und gleichzeitig nicht q gilt. Wenn das der Fall ist, wurde ein Gegenbeispiel gefunden, wenn ab diesem Zeitpunkt nie q eintritt, da dann durch das goto ein beliebig langer Durchlauf durch accept_S4 möglich ist. Natürlich muss man bei der Verifikation wieder beachten, ob man die schwache Fairness bei der Ausführung einschaltet oder nicht. Weiterhin ist zu beachten, dass man mit LTL-Formeln nicht alle Anforderungen spezifizieren kann, Never-Claims sind mächtiger in ihrer Ausdrucksweise.
2.6 Beispiele Im ersten Beispiel soll ein klassisches sequenzielles Programm untersucht werden. Genauer geht es um die Überprüfung eines Sortierverfahrens für ganze Zahlen, die in einem Array stehen. Das hier betrachtete Verfahren sucht in jedem Durchlauf
84
2.6 Beispiele das kleinste restliche Element in den noch unsortierten Zahlen. Informell kann man folgende Spezifikation nutzen: Laufe mit dem Zähler i von 0 bis zur Arraygröße-1 Laufe mit dem Zähler j von i+1 bis zur Arraygröße falls das j-te Element kleiner als das i-te Element ist, vertausche diese Das Verfahren lässt sich in PROMELA beschreiben, dabei müssen die Schleifen in do-Schleifen umgesetzt werden. Da der Datenbereich int sehr groß ist, wird zur Verifikation eine Einschränkung des Zahlenbereichs gemacht. Zur Verifikation müssen zunächst zufällige Zahlen erzeugt, dann die Sortierung und dann die Prüfung der Sortierung durchgeführt werden.
#define N 5 #define MAX 3 byte byte bool bool
array[N]; save[N]; /* zum Optimieren weglassen */ initialized = false; sorted=false;
proctype Initialize(){ byte count=0; byte rnd=0; do :: count rnd=0; do :: rnd<MAX -> rnd=rnd+1 :: true -> array[count]=rnd; save[count]= array[count]; break od; count=count+1; :: else -> break od; initialized=true } proctype Sort(){ byte i=0; byte j; byte tmp; initialized; do :: i
85
2 Modelchecking mit PROMELA und SPIN j=i+1; do :: j /*< muss <= sein */ if :: array[i]>array[j] -> tmp=array[i]; array[i]=array[j]; array[j]=tmp :: else -> skip fi; j=j+1 :: else -> break od; i=i+1; :: else -> break od; sorted=true } proctype Proof(){ byte count=0; byte count2=0; byte anzahl1=0; byte anzahl2=0; sorted; /* pruefe ob array sortiert ist */ do :: count assert(array[count]<=array[count+1]); count=count+1 :: else -> break od; /* pruefe auf gleiche Elemente */ count=0; do :: count<=MAX -> anzahl1=0; anzahl2=0; count2=0; do :: count2 if :: save[count2] == count -> anzahl1=anzahl1+1 :: else -> skip fi; if :: array[count2] == count ->
86
2.6 Beispiele anzahl2=anzahl2+1 :: else -> skip fi; count2=count2+1 :: else -> break od; assert(anzahl1==anzahl2); count=count+1 :: else -> break od } init{ run Initialize(); run Sort(); run Proof() }
Abb. 74: Verifikation eines Sortierverfahrens Generell muss zunächst festgestellt werden, wann ein Sortierverfahren korrekt ist. Geht man davon aus, dass das zu sortierende Array save und das Ergebnisarray array heißt, reicht die offensichtlich notwendige Forderung, dass in array die Elemente sortiert sind, also array[i] ŭ array[i+1] nicht aus. Die zweite, genau so wichtige und gern vergessene Anforderung ist, dass in array genau die gleichen Elemente in gleicher Anzahl wie in save stehen müssen. Die PROMELA-Umsetzung in Abb. 74 zeigt zunächst die Möglichkeit, in PROMELA mit Funktionen zu spezifizieren. Damit die Funktionen nacheinander ausgeführt werden können, gibt es Boolesche Wächter, die erst dann auf wahr gesetzt werden, wenn eine Funktion bzw. in PROMELA ein Prozess starten darf. Werden Funktionen wiederholt aufgerufen, muss die Idee mit den Wächtern angepasst werden. In Initalize wird jedem Array-Element ein zufälliger Wert zwischen Null und MAX jeweils einschließlich zugeordnet. Diese Werte werden im Array save gespeichert, um die Ausgangssituation festzuhalten und die spätere Analyse zu erleichtern. Sollte es Probleme mit der Speichergröße geben, ist der save-Array als Erstes zu eliminieren, da er für die Untersuchungen nicht unmittelbar notwendig ist, insofern man die zweite Anforderung anderweitig zeigen kann. Generell kann man mit PROMELA nur sogenannte geschlossene Systeme verifizieren. Dies sind Systeme, die bei ihrer Ausführung keine Nutzerinteraktion durchführen können. Um trotzdem Systeme mit Nutzerinteraktion oder beliebigen Parameterlisten zu betrachten, wird der Nutzer durch einen möglichst flexiblen nichtdeterministischen Prozess ersetzt.
87
2 Modelchecking mit PROMELA und SPIN Die Spezifikation hat in Sort, wie durch einen Kommentar angedeutet, einen kleinen Fehler, der bei der Verifikation mit der Zusicherung in Proof gefunden wird. Führt man den fehlerhaften Ablauf aus, so enthält das Data Values Panel am Ende folgende Werte. array[0] = 3 array[1] = 3 array[2] = 3 array[3] = 3 array[4] = 2 initialized = save[0] = 3 save[1] = 3 save[2] = 3 save[3] = 3 save[4] = 2 sorted = 1
1
Man erkennt das Problem, dass die letzte Speicherzelle des Arrays nicht korrekt berücksichtigt wird. Macht man die im Kommentar beschriebene Änderung, läuft die Verifikation problemlos durch. Kritisch ist zu beachten, dass nur Arrays der Größe fünf betrachtet werden. Man muss die Beweisführung um eine Argumentation ergänzen, warum die Erkenntnisse auch auf andere Array-Größen übertragbar sind. Die Argumentation lautet hier, dass die Größe des Arrays keinen Einfluss auf den Suchalgorithmus hat, da es nur wichtig ist, dass es ein erstes und ein letztes zu identifizierendes Element gibt.
Ampel 1
Ampel 0
Abb. 75: Ampelsystem
88
Ampel 0
Ampel 1
2.6 Beispiele Insgesamt sieht man hier ein auch für Tests typisches Szenario. Neben dem zu testenden System gibt es eine Testfallspezifikation mit den zugehörigen Eingaben und den erwarteten Ergebnissen. Als zweites Beispiel soll ein einfaches Ampelsystem für eine Kreuzung modelliert werden. Da ein Modell zwar realistisch, aber möglichst klein sein soll, wird für die reale Situation aus Abb. 75 festgehalten, dass Ampeln nur die Farben rot und grün anzeigen, und dass es ausreicht, zwei Ampeln zu betrachten, da die Ampeln in die andere Richtung immer das gleiche Signal anzeigen. Die konkreten Forderungen sind: 1.
Die Ampeln zeigen entweder rot oder grün an.
2.
Die Ampeln schalten immer wieder zwischen rot und grün hin und her.
3.
Es ist immer maximal eine Ampel grün.
4.
Die Ampeln werden abwechselnd grün.
Um die Forderungen in LTL zu formulieren, muss man entweder wissen, wie die Informationen in der Spezifikation formuliert sind, oder man formuliert zunächst mit abstrakteren Eigenschaften, wie „Ampel 1 ist grün“, die Anforderungen. Der zweite Weg ist leicht zu bevorzugen, da man dann nicht in der Spezifikation steckt und es so vermeiden kann, Denkfehler aus der Spezifikationserstellung in die Formulierung der LTL-Formeln zu übertragen. Es werden folgende Prädikate definiert ampel0rot: gilt genau dann, wenn die Ampel 0 rot ist ampel0grün: gilt genau dann, wenn die Ampel 0 grün ist ampel1rot: gilt genau dann, wenn die Ampel 1 rot ist ampel1grün: gilt genau dann, wenn die Ampel 1 grün ist ampel0zuletzt: gilt genau dann, wenn Ampel 0 zuletzt grün war ampel1zuletzt: gilt genau dann, wenn Ampel 1 zuletzt grün war Die Formalisierung der Anforderungen ist dann: 1.
( ((ampel0rot ampel0grün) (ampel0rot l ampel0grün)) ((ampel1rot ampel1grün) (ampel1rot l ampel1grün) )
2.
( (ampel0rot o (¡ ampel0grün)) (ampel0grün o (¡ ampel0rot)) (ampel1rot o (¡ ampel1grün)) (ampel1grün o (¡ ampel1rot)) )
89
2 Modelchecking mit PROMELA und SPIN 3.
( (ampel0grün o ampel1grün) (ampel1grün o ampel0grün))
4.
( ( (ampel0zuletzt) U (ampel1zuletzt ampel0zuletzt) ) ( (ampel1zuletzt) U (ampel0zuletzt ampel1zuletzt) ) (ampel0zuletzt l ampel1zuletzt) )
Bei der ersten Forderung wird zunächst sichergestellt, dass jede Ampel nur zwei Zustände hat und dass sich diese im zweiten Teil der Formel gegenseitig ausschließen. Bei der zweiten Anforderung tritt nicht das skizzierte Problem mit dem next-Operator auf, da aus 1. folgt, dass nur entweder ampel0rot oder ampel0grün gelten kann. In der dritten Anforderung darf nicht irrtümlicherweise (ampel0grün l ampel1grün) stehen, da dies bedeutet, dass bei einer roten Ampel 1 die Ampel 0 grün sein muss. Dies ist nicht gefordert und würde eine eventuell nicht gewünschte Verschärfung darstellen, weiterhin wird so eine Rotphase für beide Ampeln erlaubt. Bei der Umsetzung der vierten Forderung muss eine Formalisierung von „abwechselnd“ gefunden werden, dabei bedeutet ampel0zuletzt U (ampel1zuletzt ampel0zuletzt) dass irgendwann von der Ampel 0 auf die Ampel 1 umgeschaltet wird und dann auch die Ampel 0 nicht zuletzt dran war. Die letzten Teile der Formel garantieren, dass sich die beiden Prädikate gegenseitig ausschließen. mtype={p,v,rot,gruen}; mtype zustand[2]; bool gestartet=false; chan zentrale= [0] of {mtype,bit}; bit dran=0; /* wer als Nächstes */ proctype ampel(bit name){ do :: zustand[name]==rot -> zentrale!p,name; zustand[name]=gruen; zustand[name]=rot; zentrale!v,name; od; } proctype Semaphor(){ do :: zentrale?p,eval(dran) -> zentrale?v,_; dran=1-dran; od; } init{ atomic{
90
2.6 Beispiele zustand[0]=rot; zustand[1]=rot; run ampel(0); run ampel(1); run Semaphor(); gestartet=true; }; }
Abb. 76: Spezifikation des Ampelsystems Abb. 76 zeigt die zu untersuchende Spezifikation. Dabei wird eine Art Semaphor [Dij68] zur Kontrolle eingesetzt. Ein Semaphor hat eine Aktion, hier Nachricht p, die bei erfolgreicher Durchführung bedeutet, dass eine Komponente in einen kritischen Bereich, hier das Setzen der Ampel auf grün, eintreten kann. Nachdem die kritische Aktion abgeschlossen ist, hier wird die Ampel wieder auf rot gesetzt, wird der Semaphor mit der Nachricht v wieder freigegeben. Nebenbei sorgt der Semaphor in dieser Spezifikation dafür, dass die Ampeln abwechselnd schalten. Im nächsten Schritt müssen die informell formulierten Prädikate formalisiert werden. Häufig ist an dieser Stelle ein Zwischenschritt notwendig, so dass Hilfsvariablen eingeführt werden müssen, um die Prädikate formal beschreiben zu können. Im Beispiel werden keine Hilfsvariablen benötigt, die Anforderungen können damit, wie in Abb. 77 gezeigt, in SPIN genutzt werden.
#define #define #define #define #define #define
ampel0rot (zustand[0]==rot) ampel0gruen (zustand[0]==gruen) ampel1rot (zustand[1]==rot) ampel1gruen (zustand[1]==gruen) ampel0zuletzt (dran==1) ampel1zuletzt (dran==0)
/* 1. */ [] ( ( (ampel0rot || ampel0gruen) &&(ampel0rot <-> (!ampel0gruen))) &&( (ampel1rot || ampel1gruen) &&(ampel1rot <-> (!ampel1gruen))) ) /* 2 */ [] ( (ampel0rot -> (<> ampel0gruen)) &&(ampel0gruen -> (<> ampel0rot)) &&(ampel1rot -> (<> ampel1gruen)) &&(ampel1gruen -> (<> ampel1rot)) ) /* 3 */ [] ( (ampel0gruen -> (!ampel1gruen)) &&(ampel1gruen -> (!ampel0gruen)) )
91
2 Modelchecking mit PROMELA und SPIN /* 4 */ [] ( (ampel0zuletzt U (ampel1zuletzt && (!ampel0zuletzt))) &&(ampel1zuletzt U (ampel0zuletzt && (!ampel1zuletzt))) && (ampel0zuletzt <-> (!ampel1zuletzt)) )
Abb. 77: Formalisierung von Anforderungen in SPIN Theoretisch kann man die vier Formeln mit Und zu einer großen Formel verknüpfen, was aus den vorgestellten Rechenregeln folgt. Dies kann eine Verifikation allerdings sehr komplex machen, so dass üblicherweise die Formeln getrennt nachgewiesen werden. Ein erster Verifikationsversuch schon der ersten Anforderung scheitert. Das Problem ist, dass das System zum Start in den Variablen zustand[i] weder den Wert rot noch den Wert gruen enthält; dies passiert erst in der Initialisierung. Es ist typisch, dass ein System erst initialisiert sein muss, bis die Anforderungen erfüllt sein können. Aus diesem Grund wurde in der Spezifikation bereits die Variable gestartet eingebaut, die erst auf true gesetzt wird, wenn mindestens ein Schaltvorgang erfolgreich abgelaufen ist. Für Anforderungen, die diese Initialisierungsphase abwarten wollen, muss jede alte Anforderung A durch die Anforderung (initialisiert o A) ersetzt werden, dabei gilt hier: #define initialisiert (gestartet==true)
Mit dieser Ergänzung, die nur für die erste Anforderung notwendig ist, laufen alle Verifikationen durch. Das dritte Beispiel behandelt die Möglichkeit, mit PROMELA Prioritäten zu behandeln. Dabei soll ein Prozess in seiner Bearbeitung gegenüber einem anderen bevorzugt werden. Dies ist in der Praxis z. B. sinnvoll, wenn bei einem Programmabsturz die aktuellen Daten noch schnell zwischengespeichert werden sollen und die aktuellen Arbeitsschritte unwichtig werden. req
P
ack req
Q
ack req ack
R
S
Abb. 78: Server mit Prioritätenregelung Die informelle Spezifikation sieht zunächst wie folgt aus: Zu entwickeln ist eine Spezifikation, bei der Prozesse P, Q, und R jeweils über einen eigenen Kanal zu
92
2.6 Beispiele einem Prozess S Anfragen schicken können. Diese Anfrage wird von S immer über einen Rückkanal an den jeweiligen Prozess beantwortet. S nimmt dabei Anfragen von Q nur an, wenn P keine Anfrage stellt, und von R nur an, wenn P und Q keine Anfrage stellen. Der Prozessaufbau mit den verwendeten Nachrichtennamen ist in Abb. 78 dargestellt. Bevor eine erste Spezifikation entwickelt werden kann, muss geprüft werden, ob die Anforderungen präzise genug formuliert sind. Ist dies nicht der Fall, muss frühzeitig eine Klärung mit dem Aufgabensteller erfolgen. Während der grundsätzliche Ablauf aus Anfrage und Antwort eindeutig ist, kann die Prioritätenregelung noch präzisiert werden. Bezüglich der detaillierten Ausführung ist folgende genauere Beschreibung möglich, dass Folgendes immer gelten soll: 1.
Wenn P eine Anfrage stellt und sich S in der Auswahl des zu beantwortenden Prozesses befindet, muss P die Antwort erhalten.
2.
Wenn Q eine Anfrage stellt und sich S in der Auswahl des zu beantwortenden Prozesses befindet und P keine Anfrage gestellt hat, muss Q die Antwort erhalten.
3.
Wenn R eine Anfrage stellt und sich S in der Auswahl des zu beantwortenden Prozesses befindet und weder P noch Q eine Anfrage gestellt haben, muss R die Antwort erhalten.
Die Entwicklung komplexer Spezifikationen kann auch iterativ zusammen mit der Formalisierung der Anforderungen erfolgen. Dabei wird zunächst eine Spezifikation entwickelt und dann die Formalisierung der Anforderungen durchgeführt. Häufig muss die Spezifikation dann ergänzt werden, damit eine Anforderungsformalisierung überhaupt erst möglich wird. Zur Formulierung einer Anfrage wird asynchrone Kommunikation genutzt. Ein Prozess macht eine Anfrage, indem er eine Nachricht in seinen Anfragekanal stellt. mtype={req,ack}; chan pTos = [1] of chan qTos = [1] of chan rTos = [1] of chan sTop = [1] of chan sToq = [1] of chan sTor = [1] of
{mtype}; {mtype}; {mtype}; {mtype}; {mtype}; {mtype};
active proctype P(){ do :: pTos!req -> sTop?ack od; } active proctype Q(){
93
2 Modelchecking mit PROMELA und SPIN do :: qTos!req -> sToq?ack od; } active proctype R(){ do :: rTos!req -> sTor?ack od; }
Abb. 79: Spezifikation der anfragenden Prozesse Die grundlegenden Prozesse P, Q und R, die inhaltlich identisch sind, und die Kanäle sind in Abb. 79 zusammengefasst. Der Serverprozess S muss zu einem bestimmten Zeitpunkt entscheiden, wessen vorliegende Anfrage beantwortet werden muss. Im gleichen Schritt muss diese Antwort auch gesendet werden. Würden die Teilschritte unterbrechbar behandelt, könnte nach der Bearbeitung der Anfrage unmittelbar P eine Anfrage stellen und trotzdem keine Antwort erhalten. Aus diesem Grund muss in der Spezifikation in Abb. 80 ein atomic-Schritt genutzt werden. Es wird geprüft, ob eine Anfrage vorliegt und dann schrittweise analysiert, ob die Anfrage von P, Q oder R stammt. Die gefundene Anfrage wird beantwortet. active proctype S(){ do :: atomic{ pTos?[req] || qTos?[req] || rTos?[req]; if :: pTos?[req] -> pTos?req; sTop!ack :: else -> if :: qTos?[req] -> qTos?req; sToq!ack :: else -> rTos?req; sTor!ack fi; fi; } od; }
Abb. 80: Erste Spezifikation des Servers S
94
2.6 Beispiele Im nächsten Schritt sind die Anforderungen als LTL-Formeln zu präzisieren. Dazu muss es eindeutig beschrieben werden, dass ein Prozess eine Anfrage gestellt und dass er eine Antwort erhalten hat. /* nur für #define pr #define qr #define rr #define pa #define qa #define ra */
die Verifikation eingeführt (pReq) (qReq) (rReq) (pAck) (qAck) (rAck)
mtype={req,ack}; chan chan chan chan chan chan
pTos qTos rTos sTop sToq sTor
= = = = = =
[1] [1] [1] [1] [1] [1]
of of of of of of
{mtype}; {mtype}; {mtype}; {mtype}; {mtype}; {mtype};
/* nur für die Verifikation eingeführt */ bool pReq=false; bool qReq=false; bool rReq=false; bool pAck=false; bool qAck=false; bool rAck=false; active proctype P(){ do :: atomic {pTos!req -> pReq=true} atomic {sTop?ack -> pReq=false; pAck=false} od; } active proctype Q(){ do :: atomic{qTos!req -> qReq=true} atomic{sToq?ack -> qReq=false; qAck=false} od; } active proctype R(){ do :: atomic{rTos!req -> rReq=true} atomic{sTor?ack -> rReq=false; rAck=false} od; }
95
2 Modelchecking mit PROMELA und SPIN active proctype S(){ do :: atomic{ pTos?[req] || qTos?[req] || rTos?[req] -> if :: pTos?[req] -> pTos?req; sTop!ack; pAck=true :: else -> if :: qTos?[req] -> qTos?req; sToq!ack; qAck=true :: else -> rTos?req; sTor!ack; rAck=true fi fi } od }
Abb. 81: Vollständige Spezifikation Hier gibt es verschiedene Ansätze zur Formalisierung. Der vorgestellte Ansatz ist häufig wählbar, eine Alternative wird später angedeutet. Die folgende Erklärung erfolgt für den Prozess P, kann aber auf Q und R genau übertragen werden. Zunächst wird eine Boolesche Variable pReg ergänzt, die genau dann true sein soll, wenn P eine Anfrage gestellt hat. Dies bedeutet, dass mit dem Senden der Anfrage im gleichen Schritt diese Variable auf true gesetzt werden muss. Die Variable muss zu dem Zeitpunkt zurückgesetzt werden, in dem S die Anfrage konsumiert. Mit einer zweiten Booleschen Variable pAck wird festgehalten, wann P eine Antwort erhalten hat. Die Variable wird mit dem Senden der Antwort auf true und mit dem Empfang der Antwort wieder auf false gesetzt. Die vollständige Spezifikation ist in Abb. 81 zu sehen. Nun sind die Anforderungen zu präzisieren. Dazu muss für jeden Satzteil der Anforderung genau festgehalten werden, wie er mit den ergänzten Hilfsvariablen beschrieben wird. Dazu wird die Anforderung bezüglich P konkretisiert, die zunächst den folgenden Aufbau hat. Immer, wenn eine Bedingung für P gilt, dann muss im nachfolgenden Ablauf etwas gelten. Dies kann mit LTL zunächst wie folgt präzisiert werden. ((Bedingung) o (Folgerung)) Die Bedingung „Wenn P eine Anfrage stellt und sich S in der Auswahl des zu beantwortenden Prozesses befindet“ kann ergänzt werden um die Randbedingung, dass P eine Anfrage stellt und keine Antworten auf alte Anfragen mehr unterwegs sind. Falls noch alte Antworten existieren, kann natürlich nicht garantiert werden,
96
2.6 Beispiele dass P die erste Antwort nach seiner Anfrage bekommt, da zuerst auch die alten Antworten konsumiert werden können. Die Präzisierung der Bedingung ist damit, dass P eine Anfrage stellt (pReq==true) und keine alten Antworten vorliegen, also pAck, qAck und rAck false sind. Genauer: (pReq==true && pAck==false && qAck==false && rAck==false)
Wenn die Bedingung gilt, muss als Folgerung P die nächste Antwort erhalten. Dies bedeutet für das System, dass qAck und rAck solange nicht true werden dürfen, bis qAck true ist. Dies lässt sich leicht wie folgt mit dem Until-Operator beschreiben. ( (qAck==false && rAck==false) U pAck==true)
)
Wie bereits angedeutet, dürfen in LTL-Anfragen in SPIN keine Variablen direkt genannt werden. Es sind mit dem define-Befehl symbolische Konstanten anzulegen. Kommentiert man die Konstanten am Anfang der Spezifikation aus, so sieht die Formel für P wie folgt aus. []( (pr && (!pa) && (!qa) && (!ra)) -> ( ((!qa) && (!ra))
U pa) )
Für Q kann man einen sehr ähnlichen Ansatz wählen. Wenn Q eine Anfrage stellt und sich keine alten Antworten mehr im System befinden, dann muss Q oder P die nächste Antwort erhalten. Da P Vorrang vor Q hat, muss diese Alternative berücksichtigt werden. Die LTL-Anforderung sieht dann wie folgt aus. []( (qr && (!pa) && (!qa) && (!ra)) -> ( (!ra)
U (pa||qa) )
)
Interessant ist, dass bei der letzten Anforderung der Teil „pa||“ am Ende nicht weggelassen werden kann. Anschaulich würde die Anforderung bedeuten, dass R nicht vor Q eine Bestätigung bekommen kann. Die Anforderung ist allerdings nicht erfüllt, da es sich um ein starkes Until handelt, so dass auch gefordert wird, dass Q letztendlich immer eine Antwort bekommt. Da es aber möglich ist, dass P immer wieder sofort eine Anfrage stellt, ist es möglich, dass Q nie eine Antwort erhält. Eine ähnliche Formalisierung für R ist möglich, da aber dann auf der rechten Seite wieder beachtet werden muss, dass P und Q immer zusammen, genauer vor R, eine Anfrage stellen, ist die Forderung nur, dass überhaupt eine Antwort gegeben wird. [](
(rr && (!pa) && (!qa) && (!ra)) -> ( <> (ra || pa || qa) )
)
Zur Ausführung der Verifikation muss man entweder die define-Anweisungen aus der Spezifikation in den LTL-Property-Manager verschieben oder den generierten Never-Claim in die Spezifikation kopieren. Wie erwähnt, kann es verschiedene Ansätze zur Verifikation der gleichen Eigenschaft geben. Da in diesem Fall das Stellen der Anfrage als Schreiben in den Kanal spezifiziert wird, kann man alternativ auch über die Länge des Kanals argumentieren, dazu müssten die Konstanten wie folgt ersetzt werden. #define pr (len(pTos)==1)
97
2 Modelchecking mit PROMELA und SPIN #define pa (len(sTop)==1)
Die weitere Konkretisierung sei dem Leser zur Übung überlassen.
2.7 PROMELA und SDL In den vorherigen Teilkapiteln wurde der Kern der Sprache PROMELA mit ihren Anwendungsmöglichkeiten vorgestellt. Eine Spezifikationssprache ist üblicherweise kein Selbstzweck; sie wird eingesetzt, um letztendlich zu einem korrekten System zu kommen. Wenn man PROMELA einsetzt, sollte man deshalb genau planen, welche Sprachkonstrukte genutzt werden, damit eine Übertragung in die Realisierung möglich ist. Einen Spezialfall stellt die Möglichkeit dar, dass man eine Programmiersprache als Spezifikationssprache nutzt, was durch die vielfältigen Möglichkeiten realer Programmiersprachen kaum zu einem effizient nutzbaren Modelchecking-Ansatz führen kann. Dieser trotzdem sehr interessante Ansatz wird z. B. mit dem Projekt Java Pathfinder [MVP05] verfolgt, in dem ausgehend von den Ideen aus SPIN ein Modelchecker für einen Teilbereich von Java entwickelt wurde. Ein verwandter Ansatz zur Nutzung eines Formalen Modells ist es, Transformationen zu entwickeln. Dabei sind beide Richtungen interessant: 1.
Von der Zielsprache nach PROMELA, um existierende Systeme analysieren zu können
2.
Von PROMELA in die Zielsprache, um die mit SPIN bewiesenen Eigenschaften in die Implementierung zu übertragen.
In diesem Teilkapitel wird beispielhaft der erste Weg beschrieben, wobei hier keine konkrete Programmiersprache als Ausgangspunkt genutzt wird. Es soll die in der Telekommunikationswelt weit verbreitete, standardisierte Sprache SDL (Specification and Description Language), genauer ein Kern dieser Sprache, mit ihren Konzepten [Kön03] vorgestellt werden. Es wird damit gezeigt, wie man PROMELA und SPIN dafür nutzen kann, Eigenschaften einer SDL-Spezifikation nachzuweisen, wenn man kein passendes, da meist sehr teueres Werkzeug zur Hand hat, welches dann auch nur simulieren und nicht verifizieren kann. SDL hat eine graphische und eine dazu äquivalente textuelle Darstellung, die die Spezifikation verteilter Systeme auf der Basis von Automaten erlaubt. Abb. 82 zeigt im ersten Schritt zunächst die statische Struktur von Systemen in SDL. Dazu gibt es die hierarchische Möglichkeit, dass ein Block in weitere Blöcke zerlegt werden kann. Auf der unteren Ebene stehen Prozesse, in denen der eigentliche Ablauf dann beschrieben wird. Zwischen diesen Sprachelementen existieren Kanäle, über die Nachrichten zwischen den SDL-Elementen, genauer zwischen den Prozessen ausgetauscht werden können. Dabei können Kanäle auch über Blockgrenzen hinweg genutzt werden.
98
2.7 PROMELA und SDL
System Block
Kanal
Block Block
Prozess
Kanal
Kanal
Prozess
Prozess
Kanal
Block
Prozess
Abb. 82: Prozessstruktur in SDL Weiterhin kann man mit SDL offene Systeme beschreiben, dies sieht man an Kanälen, die mit der Umwelt verbunden sind und so Nachrichten der umgebenden Systeme annehmen bzw. Nachrichten an die umgebenden Systeme generieren können. Dies ist bei PROMELA-Spezifikationen nicht möglich, da das System zum Modelchecking geschlossen sein muss. Das kann man z. B. durch einen zusätzlichen Umgebungsprozess erreichen, der das Verhalten der Umgebung simuliert.
block B
[t]
signal t1,t2 signallist t: t1,t2
block B1
[t]
dcl i Integer; signal a,b,c,d,e signallist s1: a signallist s2: b,c
Prozess1
[s1]
[s2]
Prozess2
Abb. 83: Signale in SDL-Blöcken Abb. 83 zeigt eine verfeinerte Darstellung eines Blocks, dabei können Blöcke lokale Variablen enthalten, die in Kästen mit Eselsohren rechts oben festgehalten werden. Statt des Begriffs Nachricht wird in SDL der Begriff Signal genutzt, dabei können einzelne Signale spezifiziert werden, die dann später in Signallisten zusammengefasst werden können. Diese Listen sind logische Strukturen, so dass ein Signal durchaus in mehreren Listen vorkommen kann. Signale und Signallisten stehen an den Enden von Kanälen und beschreiben, welche Signale über diesen Kanal in welcher Richtung fließen können. Im Beispiel sieht man, dass es über den Kanal,
99
2 Modelchecking mit PROMELA und SPIN der Prozess1 und Prozess2 verbindet, möglich ist, dass Prozess1 die Signale b und c an den Prozess2 schickt, der das Signal a an Prozess1 schicken kann. Weiterhin kann Prozess2 die Signale t1 und t2 nach außen aus der Sicht des Blockes schicken. Im Beispiel werden diese Signale dann zum nächst umgebenden Block weitergereicht.
verbunden b
a x:=x+1 c
Berechnung
-
Ausgabe
terminieren
Zustand
b
Eingabe
zum vorherigen Zustand
Terminierung
Abb. 84: SDL-Prozess Abb. 84 zeigt die typischen Elemente zur Beschreibung von Prozessen in SDL. Abgerundete Rechtecke wie „verbunden“ bezeichnen Zustände. Ein SDL-Prozess verlässt seinen Zustand grundsätzlich nur, wenn er ein Signal erhält. Im Beispiel wird auf die Signale a und b reagiert; was passiert, wenn keines dieser Signale erhalten wird, wird im Folgenden noch genauer beschrieben. Erhält der Prozess ein Signal b, so geht er in den mit einem einfachen Strich gekennzeichneten Zustand. Dabei ist dies eine alternative Darstellung dafür, dass der Prozess zu seinem vorherigen Zustand zurückkehrt, was auch durch den Kommentar, der als gestrichelter rechts offener Kasten mit dem Zustand verknüpft ist, angedeutet wird. Der Prozess ist also in der Lage, im Zustand „verbunden“ beliebig viele b-Signale zu empfangen und kehrt dabei in den Zustand „verbunden“ zurück. Nach dem Empfang eines Signals können beliebige Berechnungen durchgeführt werden, die in einfachen Rechtecken stehen. Weiterhin können beliebig Signale erzeugt werden, wie es im Beispiel mit c der Fall ist. Erhält man im Zustand „verbunden“ ein aSignal, wird die Variable x erhöht, ein c-Signal gesendet und in den Zustand „terminieren“ übergegangen. Die richtige Prozessterminierung wird durch das Symbol ganz unten in der Abbildung beschrieben.
100
2.7 PROMELA und SDL Prozesseingabequeue ... b
x
c
a
... b
x
c
... b
x
... x
a wird verarbeitet
c wird
w1
x wird ge sichert b wird verarbe itet
x wird verarbeitet
...
x
b
a
verwor fen (ge löscht)
w2
b
x
w3
b
Signal wird gerettet, verbleibt in der Eingabequeue
Abb. 85: Signalabarbeitung in SDL Abb. 85 veranschaulicht die Semantik des Kommunikationsverhaltens in SDL. Jeder Prozess hat in SDL eine Prozesseingabequeue, die im PROMELASprachgebrauch einem unendlichen Nachrichtenpuffer entspricht. Diese Queue ist rein zur Veranschaulichung in der Abbildung auf der linken Seite mit den aktuell enthaltenen Nachrichten dargestellt. Zunächst ist der bereits beschriebene typische Spezifikationsfall in der Abbildung sichtbar, der Prozess befindet sich im Zustand w1 und könnte die Signale a oder b bearbeiten, er erhält ein a-Signal, das aus der Queue gelöscht wird, und wechselt in den Zustand w2. In w2 ist der Prozess bereit, ein b oder ein x zu verarbeiten. Bei leerer Queue würde der Prozess grundsätzlich auf ein Signal warten. Passt das älteste Signal der Queue nicht zu den Verarbeitungsmöglichkeiten, wie es in w2 der Fall ist, wird das Signal gelöscht. Es werden damit alle Signale gelöscht, die nicht verarbeitet werden können. SDL bietet einige Möglichkeiten, von diesem standardmäßigen Verhalten abzuweichen. Eine Möglichkeit ist mit dem Signal x in einer Raute angedeutet, was anschaulich bedeutet, dass dieses Signal aktuell nicht verarbeitet werden kann, aber in der Queue verbleiben soll. Dadurch wird dann die zweitälteste Nachricht angeschaut. Im konkreten Fall bleibt das Signal x in der Queue und das Signal b wird verarbeitet. Im nächsten Schritt kann dann das gerettete Signal x verarbeitet werden.
101
2 Modelchecking mit PROMELA und SPIN Prioritäten
Timer set(now+3,t)
warten timer t
normal
hohe Priorität
Bedingung (intern, niedrigste Priorität)
Antwort
else
gefeuerter Timer
Frage Antwort1 Antwort2 else
t
a
Nichtdeterminismus
Alternativen Frage
warten
x>0
b
a
none
w1
b
Abb. 86: Weitere Sprachkonstrukte in SDL In Abb. 86 sind weitere Sprachkonstrukte aus SDL angedeutet. Man kann die Signalverarbeitung dadurch beeinflussen, dass man gewissen Signalen eine höhere Priorität gibt, was anschaulich bedeutet, dass die Queue zunächst nach solchen Nachrichten durchsucht wird. Die Skizze links oben zeigt weiterhin die Möglichkeit, dass ein Prozess auch reagieren kann, wenn kein Signal vorliegt, und dann nur abhängig von einer Bedingung voranschreitet. Die Möglichkeit, Spezifikationen mit Zeit zu entwickeln, ist Teil von SDL, wobei Timer eine besondere Bedeutung haben. Timer bieten anschaulich die Möglichkeit einer Eieruhr, einen Endzeitpunkt zu setzen. Sollte der Timer bis zu diesem Zeitpunkt nicht mit einem reset-Signal abgeschaltet worden sein, erzeugt der Timer ein Signal, das in die Prozessqueue eingefügt und genau wie andere Signale verarbeitet wird. Zwischen der Verarbeitung von Signalen können beliebige Programme ablaufen, die man genauer mit Alternativen, wie sie aus Programmablaufplänen oder Aktivitätsdiagrammen bekannt sind, beschreiben kann. Als weitere Möglichkeit bietet SDL einen Nichtdeterminismus, der durch ein Eingabesignal none beschrieben wird. Der so spezifizierte Weg kann immer genutzt werden. Liegt im Beispielzustand w1 im Diagramm rechts unten ein Signal b vor, kann sich das System nichtdeterministisch entscheiden, entweder b zu verarbeiten oder den none-Weg zu nutzen. Da SDL meist sehr implementierungsnah genutzt wird, wird auf diese und andere zuletzt genannte Möglichkeiten häufig verzichtet.
102
2.7 PROMELA und SDL block Bsp signal i1,i2,term,ack signallist toE: i1,i2,ack signallist toS: term
Sender
SundE [toS]
[toE]
Empfaenger
Abb. 87: Blockstruktur des Beispielsystems Nun soll ein kleines Beispielsystem in SDL spezifiziert und nach PROMELA übertragen werden. Das System soll aus zwei Prozessen bestehen, wobei ein Sender einem Empfänger zunächst Signale i1 und i2 in beliebiger Reihenfolge schickt. Hat der Empfaenger jeweils mehr als zehn i1- und i2-Signale erhalten, schickt er dem Sender ein Terminierungssignal term, was dieser mit einem Bestätigungssignal ack beantwortet. Abb. 87 zeigt die Blockstruktur des Systems. process Sender senden
none
none
i1
i2
-
-
term
ack
Abb. 88: SDL-Spezifikation des Senders Abb. 88 zeigt die Spezifikation des Senders, der nur einen Zustand hat, in dem nichtdeterministisch immer Signale i1 und i2 erzeugt werden können. Falls ein Signal term vorliegt, kann dieses mit ack bestätigt werden und der Prozess terminiert.
103
2 Modelchecking mit PROMELA und SPIN process Empfaenger
dcl x1 Natural =0, x2 Natural =0;
empfangen
i1
i2
x1:=x1+1
x2:=x2+1
x1>10 und x2>10?
beenden
i1
i2
-
-
ack
else -
term beenden
Abb. 89: SDL-Spezifikation des Empfängers Abb. 89 zeigt die Spezifikation des Empfängers, der Signale i1 und i2 empfangen kann, diese zählt und dann prüft, ob er von beiden mehr als zehn erhalten hat („und“ wurde hier zur informellen Spezifikation der Verknüpfung genutzt). Ist dies nicht der Fall, kehrt der Prozess zu seinem Anfangszustand zurück, sonst sendet er ein Signal term und geht in den Zustand „beenden“. Die Abbildung deutet eine Möglichkeit an, Spezifikationen auf Papier zu strukturieren, indem ein Zustand, hier „beenden“, an einer anderen Stelle weiterspezifiziert wird. In diesem Zustand werden Signale i1 und i2 nicht weiter beachtet, nur ein Signal ack führt zur Prozessbeendigung. Theoretisch kann man bei der Beschreibung von „beenden“ die Signale i1 und i2 weglassen, da nach der Semantik der Queueabarbeitung diese Signale gelöscht werden. Solch eine implizite Löschung stellt aber einen schlechten Spezifikationsstil dar, so dass mit dem gezeigten Ansatz verdeutlicht wird, dass bekannt ist, dass die Signale i1 und i2 vorliegen könnten, diese aber hier keine Bedeutung haben. mtype={i1,i2,term,ack}; byte x1=0; byte x2=0; chan SundES=[5] of {mtype}; chan SundEE=[5] of {mtype}; active proctype sender(){ do :: SundEE!i1 :: SundEE!i2 :: SundES?term->
104
2.7 PROMELA und SDL SundEE!ack; break od; } active proctype empfaenger(){ empfangen: if :: SundEE?i1-> x1=x1+1 :: SundEE?i2-> x2=x2+1 fi; if :: x1>10 && x2>10 -> SundES!term; goto beenden :: else -> goto empfangen fi; beenden: do :: SundEE?i1 :: SundEE?i2 :: SundEE?ack -> break od }
Abb. 90: In PROMELA übertragene SDL-Spezifikation Abb. 90 zeigt die Übersetzung der SDL-Spezifikation nach PROMELA, dabei ist die Übersetzung in diesem Fall recht einfach, da in der SDL-Spezifikation nur Sprachkonstrukte genutzt werden, die unmittelbar nach PROMELA übersetzt werden können. In PROMELA muss allerdings die maximale Nachrichtenpuffergröße angegeben werden, die in SDL nicht spezifiziert werden musste, weiterhin kennt PROMELA nur eine Signalliste. Generell muss bei der Übersetzung das Kommunikationsverhalten von SDL berücksichtigt werden, was z. B. dazu führen kann, dass in SDL implizit gelöschte Signale in PROMELA sichtbar verarbeitet, genauer gelöscht werden müssen. Man erkennt am Empfängerprozess, dass es in diesem Fall sinnvoll ist, die Zustandsnamen aus SDL als Markierungen zu übernehmen, um so den Bezug zwischen den Spezifikationen zu verdeutlichen. Man könnte natürlich auch eine PROMELA-Spezifikation ohne goto angeben.
105
2 Modelchecking mit PROMELA und SPIN
2.8 Aufgaben Wiederholungsfragen Versuchen Sie zur Wiederholung folgende Fragen aus dem Kopf, d. h. ohne nochmaliges Blättern und Lesen, zu beantworten. 1.
Erklären Sie aus Sicht der Logik den Begriff Modelchecking.
2.
Welche Fehlerarten kann man mit Modelchecking vermeiden, welche nicht?
3.
Erklären Sie anschaulich die Semantik von if und do in PROMELA.
4.
Erklären Sie die besondere Bedeutung von Booleschen Bedingungen wie (fertig<4) in PROMELA.
5.
Wie kann man neue Datentypen in PROMELA definieren?
6.
Welche Möglichkeiten gibt es in PROMELA, Prozesse zu definieren und zu starten?
7.
Wozu gibt es atomare Bereiche, wie werden sie eingesetzt, was passiert, wenn sie nicht weiter ausgeführt werden können?
8.
Wie kann man die Kommunikation von Prozessen in PROMELA spezifizieren?
9.
Was versteht man unter synchroner und asynchroner Kommunikation, welches Verhalten steckt bei der Ausführung dahinter?
10. Welche zusätzlichen Möglichkeiten gibt es in PROMELA bei asynchroner Kommunikation außer dem reinen Empfangen? 11. Was sind Message Sequence Charts, wozu können sie eingesetzt werden? 12. Was ist der Zustandsraum einer Spezifikation, welche Bedeutung hat er für das Modelchecking, wie kann er verwaltet werden? 13. Wie kann man beim Modelchecking mit sehr großen Spezifikationen umgehen? 14. Was versteht man unter Sicherheits- und Lebendigkeitseigenschaften? 15. Was unterscheidet unfaire, schwach faire und stark faire Systeme? 16. Wie kann man mit Hilfe von assert mit SPIN verifizieren? 17. Wozu dienen end-Markierungen in PROMELA? 18. Wozu dienen progress-Markierungen in PROMELA? 19. Was sind Trace-Zusicherungen, wie werden sie überprüft? 20. Was sind Never-Claims, wie werden sie überprüft? 21. Wie ist die Syntax und Semantik von Formeln der Linearen Temporalen Logik definiert?
106
2.8 Aufgaben 22. Nennen Sie typische Arten von Anforderungen Spezifikationen und ihre Syntax in LTL.
an
PROMELA-
23. Wie können LTL-Formeln im Zusammenhang mit SPIN genutzt werden? 24. Erklären Sie, wie man mit SDL Prozesse spezifizieren kann. 25. Wie werden Nachrichten in SDL verarbeitet? 26. Welche Zusammenhänge kann man zwischen PROMELA und SDL aufbauen? Übungsaufgaben 1) a) Geben Sie folgende Spezifikation in XSPIN ein. byte x=0; active proctype P1(){ x=x+1; x=x+1 } active proctype P2(){ x=2 }
Überprüfen Sie die Syntax, stellen Sie als Simulationsart „Interactive“ ein und starten Sie die Simulation. Versuchen Sie dann durch verschiedene von Hand gesteuerte Simulationen unterschiedliche Ergebnisse für x zu erreichen. Welche Ergebnisse sind möglich? (Um eine Simulation zu beenden, drücken Sie „Cancel“ im Fenster „Simulation Output“.) b) Schreiben Sie eine PROMELA-Spezifikation, mit der Sie feststellen können, wie sich der Datentyp byte bei einem Überlauf und bei einem Unterschreiten des Wertebereichs verhält. c)
Nutzen Sie den Nichtdeterminismus, um in einer globalen Variable x eine zufällige ganze Zahl zwischen 0 und 100 zu generieren; dabei soll die Zahl nicht durch 10 teilbar sein. (Modulorechnung 7 % 3 ist 1, mit 1 als Rest bei der Division, funktioniert auch in PROMELA.) Sie sollten jede erlaubte Zahl durch eine interaktive Simulation erreichen können.
2) Gegeben sei die folgende Spezifikation: byte x; byte y;
107
2 Modelchecking mit PROMELA und SPIN proctype P(){ byte c; c=x; x=y; y=c } init{ x=2; y=3; run P(); run P()
} Überlegen Sie sich mit einer Skizze, welche Werte x und y am Ende haben können. Der Anfang der Skizze könnte wie folgt aussehen; bedenken Sie, dass c jeweils eine lokale Variable ist.
(c1,c2,x,y) (*, *, 2,3) 1: c1=x
2: c2=x
(2,*,2,3)
(*,2,2,3)
Überprüfen Sie die möglichen Endergebnisse, indem Sie diese durch Simulation mit XSPIN erzeugen. 3) Zu entwickeln ist eine Spezifikation mit N Prozessen, wobei jeder Prozess eine Boolesche Variable drucken enthält, diese sind in einem Array bool drucken[N]; global definiert. Jeder der Prozesse soll zum Start eine eindeutige Identifikationsnummer erhalten, weiterhin werden alle Werte des Arrays drucken auf false gesetzt. Jeder Prozess Pi möchte jetzt immer wieder drucken. Wenn er druckt, setzt er seine Variable drucken[i] auf true, nach dem Drucken auf false. Überlegen Sie sich ein Verfahren, dass immer nur ein Prozess druckt, es also maximal ein i gibt, für das drucken[i]==true gilt. 4) Zu entwickeln ist eine Spezifikation, die drei ganzzahlige globale Variablen x, y und z hat, die mit dem Wert Null starten. Weiterhin gibt es drei Prozesse, wobei jeder eine dieser globalen Variablen schrittweise bis einschließlich 10 hochzählt. Die Prozesse sollen sich so synchronisieren, dass jeweils immer nur ein Prozess fortschreiten kann, genauer erst P1, dann P2, dann P3 und dann wieder von vorne. Bei einer interaktiven Simulation sollte damit die Spezifikation durchlaufen, ohne
108
2.8 Aufgaben dass Sie eine Möglichkeit erhalten, irgendeine Auswahl zu treffen. Übertragen Sie Ihre Idee auf eine Spezifikation mit N Variablen und N Prozessen, die sich genauso verhält. 5) Gegeben sei der folgende PROMELA-Prozess mit einer globalen Variablen x. byte x=0; active proctype P(){ atomic{ x=x+1; x=x+1 } }
Schreiben Sie einen zweiten Prozess, der immer terminiert, wenn P die vorgestellte Form hat, und der möglicherweise nicht terminiert, wenn man den atomaren Bereich auflöst, also atomic weglässt. 6) #define PUFFER 0 mtype {send,ack} byte N=10; chan zuP2 = [PUFFER] of {mtype,byte}; chan zuP1= [PUFFER] of {mtype,byte}; active proctype P1(){ byte wert=1; byte antwort=0; do :: wert<=N && wert-antwort<=PUFFER+1-> zuP2!send,wert; wert=wert+1 :: zuP1?ack,antwort -> wert=antwort+1 :: antwort==N -> break od; } active proctype P2(){ byte wert; do :: zuP2?send,wert; zuP1!ack,wert; if :: wert==N -> break
109
2 Modelchecking mit PROMELA und SPIN :: else -> skip fi; }
od;
Gegeben sei die obige Spezifikation. a) Zeichnen Sie von Hand einen MSC, der den typischen Ablauf der Spezifikation zeigt. b) Der Wert von PUFFER wird auf 1 geändert, zeichnen Sie einen von a) abweichenden MSC, der zeigt, dass die Spezifikation terminieren kann. c)
Der Wert von PUFFER wird auf 1 geändert, zeichnen Sie einen MSC von Hand, aus dem hervorgeht, dass das System in einen Deadlock geraten kann, also die Prozesse nicht terminiert sind, aber nicht voranschreiten können.
d) Führen Sie ihre Überlegungen zu a), b) und c) als interaktive Simulationen in XSPIN aus. 7) tom1
Medium1
Sender
fromm1 Empfaenger
tom2
Medium2
fromm2
Zu entwickeln ist eine Spezifikation mit 4 Prozessen Sender, Empfaenger, Medium1 und Medium2. Dabei soll der Sender die Werte 1 bis 10 zum Empfaenger übertragen. Zur Übertragung wählt der Sender nichtdeterministisch das Medium1 oder das Medium2, um einen Wert zu übertragen. Schreiben Sie eine zugehörige Spezifikation, dabei soll jedes Medium die Summe der jeweils übertragenen Zahlen berechnen. Simulieren Sie ihre Spezifikation. Welchen Einfluss hat die Puffergröße auf das Spezifikationsverhalten, genauer die Reihenfolge der übertragenen Werte? 8) In dieser Aufgabe wird schrittweise eine komplexe Spezifikation entwickelt. Es ist ratsam, die Ergebnisse für jede Teilaufgabe getrennt zu speichern. Nach einer erfolgreichen Verifikation sollte man mal einen Fehler einbauen, damit man lernt, das Resultat zu interpretieren.
110
2.8 Aufgaben
P1
c12
c23
P2
P3
Zu spezifizieren sind drei Prozesse, wobei P1 die Zahlen von 1 aufsteigend bis maximal 10 an P2 überträgt und P2 alle erhaltenen Werte an P3 überträgt. P1 kann dabei nichtdeterministisch ab der Zahl 5 entscheiden, ob die Übertragung beendet wird. P2 und P3 summieren jeweils in globalen Variablen die erhaltenen Werte unmittelbar nach Erhalt auf. P1 summiert unmittelbar vor dem Senden eines Wertes die Werte in einer eigenen globalen Variable. a) Übertragen Sie die informelle Spezifikation in eine PROMELASpezifikation mit synchroner Kommunikation. Dabei sind zunächst keine Besonderheiten, wie Endzustände, zu berücksichtigen, allerdings sollen Sie atomic und d_step nur beim Aufsummieren nutzen. Überprüfen Sie mit einem Simulationslauf das korrekte Verhalten (warum ist hier eine Verifikation mit Hilfe der Simulation möglich?). b) Für die drei Summenwerte kann man sich eine globale Invariante, also eine Invariante, die in jedem Zustand gilt, ausdenken. Formulieren Sie eine solche Invariante und spezifizieren Sie einen zusätzlichen Prozess, der die Invariante prüft. Führen Sie eine Verifikation mit XSPIN aus. c)
Nachdem P1 terminiert, werden sich P2 und P3 typischerweise nicht im Endzustand befinden. Ergänzen Sie das Kommunikationsprotokoll so, dass P1 am Ende eine Terminierungsnachricht an P2 schickt, die von P2 an P3 weiter geleitet wird. Überprüfen Sie mit XSPIN, dass alle Prozesse terminieren (Sie benötigen keine end-Markierungen).
c12
P1
c21
c23
P2
c32
P3
d) Ergänzen Sie das Kommunikationsprotokoll so, dass P2 und P3 dem jeweiligen Sender den Empfang einer Zahl durch eine Bestätigungsnachricht (z. B. ack) mit dem empfangenen Wert und die Terminierungsnachricht (z. B. mit termack) bestätigen. Führen Sie die Verifikation aus b) und c) durch. e) Erweitern Sie das Kommunikationsprotokoll so, dass P2 und P3 nichtdeterministisch entscheiden, dass eine empfangene Nachricht nicht in Ordnung ist. In diesem Fall soll dem jeweiligen Sender eine Nachricht mit der Aufforderung zur Wiederholung (repeat) geschickt und der zuletzt erhaltene Wert nicht summiert werden. Beachten Sie, dass auch die Terminierungsnachricht eventuell wiederholt werden muss. Führen Sie die Verifikation aus b) und c) durch. f)
Am Ende der Prozessausführung sollten alle Summenwerte der Prozesse übereinstimmen. Spezifizieren Sie einen zusätzlichen Prozess, der von P1,
111
2 Modelchecking mit PROMELA und SPIN P2 und P3 am Ende der Prozessausführung den Wert der jeweiligen Summe mitgeteilt bekommt (da die Summen global sind, würde es auch ausreichen, den neuen Prozess über die Terminierung zu informieren) und der mit einer Zusicherung prüft, dass alle Summen gleich sind. g) Gehen Sie jetzt von einer synchronen zu einer asynchronen Spezifikation über, dabei soll jeder Kanal die Puffergröße 2 haben. Überlegen Sie sich, welche Probleme mit Ihrem für e) entwickelten Protokoll entstehen können. Führen Sie die Verifikation aus b) und c) durch. 9)
P1
send ack repeat
P2
Spezifizieren Sie zwei Prozesse P1 und P2, wobei P1 zyklisch die Zahlen von 0 bis 255 aufsteigend über einen Kanal send an P2 schickt, also P1 nicht terminiert, und nach der 255 wieder mit 0 begonnen wird. P2 bestätigt jede empfangene Zahl auf dem Kanal ack, wobei P1 erst nach erfolgreicher Bestätigung die nächste Zahl schickt. P2 kann nichtdeterministisch entscheiden, eine Zahl nicht anzunehmen und stattdessen P1 zur Wiederholung der Sendung über den Kanal repeat aufzufordern. a) Übertragen Sie die informelle Spezifikation in eine PROMELASpezifikation mit synchroner Kommunikation. Dabei sind zunächst keine Besonderheiten zu berücksichtigen. b) Markieren Sie die Zeile, in der der zu übertragende Wert um eins erhöht wird, mit einer progress-Markierung. Führen Sie eine Lebendigkeitsprüfung aus und interpretieren Sie das Ergebnis. c)
Erweitern Sie Ihre Spezifikation so, dass P1 nach drei gescheiterten Übertragungsversuchen entscheidet, den nächsten Wert zu senden. Nutzen Sie progress-Markierungen, um nachzuweisen, dass Ihr System immer voran schreitet.
d) Nutzen Sie eine Trace-Zusicherung, um zu zeigen, dass zwischen zwei send-Kommunikationen immer eine andere Kommunikation stattfindet. Wie lautet der zugehörige reguläre Ausdruck? e) Schreiben Sie eine Trace-Zusicherung, die garantiert, dass nach maximal drei repeat-Kommunikationen immer eine ack-Kommunikation folgt, dabei werden nur repeat- und ack-Kommunikationen betrachtet. Die Verifikation dieser Zusicherung sollte scheitern, warum?
112
2.8 Aufgaben 10) Die zu entwickelnde Spezifikation besteht aus N Prozessen P1 bis PN, die jeweils verantwortlich für eine Zahl eines globalen Arrays byte wert[N] sind. Ziel der Spezifikation ist es, dass das Array sortiert ist. Dazu wird folgender Ansatz genutzt: Zunächst schicken alle Pi mit geradem i den Wert wert[i] an Prozess Pi-1. Pi-1 vergleicht den erhaltenen Wert mit seinem Wert wert[i-1], schickt den größeren Wert an Pi zurück und behält den kleineren Wert. Dann schicken alle Pi mit geradem i den Wert wert[i] an Prozess Pi+1. Pi+1 vergleicht den erhaltenen Wert mit seinem Wert wert[i+1], schickt den kleineren Wert an Pi zurück und behält den größeren Wert. Diese beiden Tauschaktionen werden insgesamt N mal durchgeführt, dabei wird synchrone Kommunikation genutzt.
P1
P2
PN
Schreiben Sie eine PROMELA-Spezifikation für Pi, beachten Sie die Spezialfälle P1 und PN. Schreiben Sie dann einen init-Prozess, der zunächst den Array wert mit zufälligen Zahlen zwischen 1 und 3 (jeweils einschließlich) füllt und dann die Prozesse Pi erzeugt. Nur im init-Prozess kann (und soll) atomic zur Reduktion der Zustandszahl eingesetzt werden. Weisen Sie mit XSPIN nach, dass Ihre Spezifikation terminiert und dass der Array am Ende sortiert ist. Dazu sind die Prozesse gegebenenfalls anzupassen oder zu ergänzen. Bevor Sie die Spezifikation erstellen, visualisieren Sie das Sortierverfahren mit einem Beispiel für ein gerades und ein ungerades N. Machen Sie die Verifikationsdurchläufe für N=1 bis N=5. Zum Testen und Verifizieren kann es hilfreich sein, sich die geratenen Werte in einem zusätzlichen Array zu merken, um sie dann mit dem berechneten Ergebnis vergleichen zu können. 11) Gegeben sei folgende PROMELA-Spezifikation. byte x=1; byte y=0; active proctype P1(){ do :: x=x+2 od; } active proctype P2(){ do :: x=x+1
113
2 Modelchecking mit PROMELA und SPIN }
od;
active proctype P3(){ do :: y<x -> y=x od; }
Formulieren Sie folgende Anforderungen möglichst genau als LTL-Formeln. Überlegen Sie zunächst, ob diese Formeln mit oder ohne schwacher Fairness gelten. Überprüfen Sie Ihre Überlegungen mit XSPIN. a) x ist immer ungerade b) x ist irgendwann 10 c)
x ist irgendwann nicht 10
d) es gibt eine Möglichkeit, dass x ab einem bestimmten Zeitpunkt immer ungerade ist e) es gibt eine Möglichkeit, dass x ab einem bestimmten Zeitpunkt immer wieder ungerade ist f)
es gibt eine Möglichkeit, dass x ab einem bestimmten Zeitpunkt immer 10 ist
g) es gilt immer y ist kleiner-gleich x h) auf y ungleich x folgt immer y gleich x i)
auf y gleich x folgt immer y ungleich x
12)
. . .
Hinweis vorweg: Die Skizze des verteilten Systems dient zur Erklärung der Aufgabenstellung. Sie müssen selbst sinnvolle Namen für Kanäle und Nachrichten
114
2.8 Aufgaben wählen; die im Bild enthaltenen Namen sind im Detail nicht immer sinnvoll, da die Nummerierung mit Eins beginnt. Das von Ihnen in PROMELA zu spezifizierende System besteht aus N Sendern, die über M Kanäle (in der Skizze M=2, mit Kanälen toS[1] und toS[2] auf der rechten Seite) mit einem Server kommunizieren können. Es soll M
115
2 Modelchecking mit PROMELA und SPIN c)
Entwickeln Sie die Spezifikation für die Prozesse. Nutzen Sie asynchrone Kommunikation mit Puffergröße 1 und „blocking queues“. Der Ansatz sollte sein, zunächst das Kommunikationsprotokoll von a) umzusetzen und dann b) zu ergänzen. Kommentieren Sie Ihre Spezifikation detailliert.
d) Verifizieren Sie, dass die Anforderungen i.-v. erfüllt sind. Falls Sie die Spezifikation dazu ergänzen müssen, kennzeichnen Sie die Erweiterungen. Nutzen Sie für die Verifikation kleine Werte, z. B. N=3, M=2 und Puffergröße 1. e) Beschreiben Sie den Einfluss der Puffergröße auf Ihre Spezifikation, wie verändert sich z. B. das Verhalten, wenn Sie zu synchroner Kommunikation wechseln müssten? (Es ist nicht gefordert, dass Ihre Spezifikation auch im synchronen Fall funktioniert.) Spezifikationshinweise: – Es ist schwierig zu spezifizieren, dass der Server immer bereit ist, auf seinen M Kanälen Nachrichten anzunehmen. Eine Lösungsvariante ist hier, dass der Server zyklisch alle seine Kanäle auf Kommunikationsbereitschaft prüft. Dies macht den Beweis von i. bis iii. praktisch unmöglich, deshalb können Sie für i. bis iii. die Spezifikation des Servers durch einen Prozess ersetzen, der über eine feste Anzahl von Kanälen wacht. Ausschnitt: do :: toS[1]?_ :: toS[2]?_ :: ...
– Weiterhin kann es für den Nachweis von i. und ii. notwendig sein, die Werte für M und N sinnvoll zu verkleinern. – Interne Berechnungen z. B. im Scheduler sollten in einem Schritt mit atomic oder d_step zusammengefasst werden.
116
3 Modelchecking mit Timed Automata und Uppaal Um die Zusammenarbeit verteilter Systeme zu ermöglichen, gibt es verschiedene Varianten, die typischerweise Kommunikationsmöglichkeiten zum Informationsaustausch und gemeinsame Variablen beinhalten. Spezifikationssprachen unterscheiden sich häufig in der Mächtigkeit der angebotenen Möglichkeiten. Ein weiteres zentrales Unterscheidungskriterium ist der Umgang mit Zeit. Gerade bei verteilten Systemen, aber auch bei sequenziellen Programmen, kann die Dauer von bestimmten Aktionen die Funktionalität und die Qualität eines Systems wesentlich beeinflussen. Reagieren Systeme zu langsam, werden Sie von Endnutzern nicht akzeptiert; technische Komponenten hingegen werden dann nicht warten wollen und schicken Timeout-Nachrichten zum Abbruch. Mit Timed Automata lernen wir in diesem Kapitel eine Spezifikationssprache kennen, die einfache synchrone Kommunikation, globale Variablen und Uhren zur Kontrolle von Aktionen anbietet. Timed Automata können komfortabel mit dem Werkzeug Uppaal bearbeitet werden. Weiterhin bietet Uppaal Modelchecking für Anforderungen in der Timed Computation Tree Logic an. Es handelt sich dabei um eine eingeschränkte Variante der allgemeinen Timed Computation Tree Logic. Wie immer gilt, dass man die Sprachkonstrukte zur Spezifikation auswählen muss, die zum realen System passen. Grundsätzlich kann dieses Kapitel ohne das Vorgänger-Kapitel gelesen werden. An einigen Stellen werden einige Vergleiche mit und Verknüpfungen zu PROMELA aufgezeigt, die man beim alleinigen Studium von Timed Automata einfach überlesen kann. Zur Einführung in das Thema Modelchecking sollte das Teilkapitel 2.1 gelesen werden. Mit PROMELA ist es möglich, verteilte Systeme zu spezifizieren und ihre Eigenschaften nachzuprüfen. PROMELA ist aber für Anfänger relativ schwer zu handhaben, da man sich an die Syntax gewöhnen muss und die Unterstützung bei syntaktischen Fehlern relativ gering ist. Um den Zugang zu Spezifikationen zu erleichtern, kann man auf den Einsatz visueller Möglichkeiten zurückgreifen. Dies ist eine Motivation für den Einsatz von Timed Automata, da hier Spezifikationen auf der Basis graphisch dargestellter endlicher Automaten entwickelt werden. Der Einsatz von PROMELA wird schwierig, wenn man versucht, Aussagen über die benötigte Ausführungszeit von Spezifikationen zu gewinnen. Man kann zwar versuchen, spezielle Zählvariablen für Zeitaspekte einzuführen, sehr viel bringt dieser Ansatz aber nicht, da z. B. das Voranschreiten von Zeit in mehreren Prozessen aufwändig nachmodelliert werden müsste. Timed Automata bilden da eine Abhilfe, da hier spezielle Zeitvariablen, so genannte Uhren, genutzt werden können. Es wird so möglich zu spezifizieren, dass gewisse Zeit in Zuständen verbracht wird und in bestimmten Zeitintervallen Aktionen ausgeführt werden können.
117
3 Modelchecking mit Timed Automata und Uppaal In diesem Kapitel lernen Sie zunächst, wie man verteilte Systeme mit synchroner Kommunikation graphisch spezifizieren kann. Danach wird gezeigt, wie man Spezifikationen um Zeitbedingungen ergänzt und welche Besonderheiten, wie neue auf Zeitrestriktionen beruhende Deadlocks, zu beachten sind. Die Nutzung des hierbei unterstützenden Werkzeugs Uppaal wird dann beschrieben. Eine Vielzahl von Anforderungen können in der dann eingeführten Timed Computation Tree Logic spezifiziert werden. Einige Fallstudien runden das Kapitel ab.
3.1 Synchron kommunizierende Automaten Die Basis von Timed Automata-Spezifikationen sind endliche Automaten, wie sie aus der theoretischen Informatik [VW04] bekannt sind. Es werden nichtdeterministische Automaten genutzt, so dass zu einem konkreten Zeitpunkt Übergänge zu verschiedenen Zuständen mit der gleichen Aktion möglich sein können. Zur Spezifikation verteilter Systeme werden mehrere Automaten eingesetzt, die für Timed Automata Templates genannt werden; der Template-Begriff wird später noch präzisiert. Die Automaten können mit synchronen Kommunikationen Informationen austauschen. Dabei beschreibt c! wieder, dass über einen Kanal c gesendet, und c?, dass über einen Kanal c empfangen werden soll. Diese Kommunikation ist dabei nur möglich, wenn Sender und Empfänger zur Kommunikation bereit sind. Anders als in PROMELA können die Kommunikationen nicht direkt mit einer Wertübertragung zusammen spezifiziert werden. Dies ist aber durch die Nutzung globaler Variablen modellierbar.
c?
a!
Template A
a?
b!
Template B
c!
b?
Template C
Abb. 91: Parallelkomposition von Automaten Als erstes Beispiel wird ein kleines System mit drei Prozessen A, B, C spezifiziert, wobei zunächst A mit B über a, dann B mit C über b und schließlich C mit A über c kommuniziert. Danach beginnt die Kommunikation von vorne. Zunächst werden die Kanäle als globale Variablen spezifiziert. Dies erfolgt durch
118
3.1 Synchron kommunizierende Automaten //global chan a; chan b; chan c;
Als Kommentare stehen die von C++ und Java bekannten Möglichkeiten mit // für einen Kommentar, der bis zum Zeilenende geht, und mit einem längeren Kommentar, der in /* und */ eingeschlossen ist, zur Verfügung. Danach werden die Prozesse als endliche Automaten, ab jetzt Templates genannt, spezifiziert. Die Spezifikation steht in Abb. 91, dabei bezeichnet ein doppelt umrandeter Zustand bei Templates den jeweiligen Startzustand. Zur Spezifikation des Gesamtsystems muss angegeben werden, aus welchen Teilen das System zusammengesetzt wird, dies erfolgt durch system A,B,C;
Durch die Abänderung dieser Zeile ist es z. B. möglich, spezifizierte Templates in der zu untersuchenden Spezifikation nicht zu berücksichtigen. Neben Kommunikationskanälen können in den Spezifikationen auch lokale und globale Variablen mit den „üblichen“ Datentypen int und bool eingesetzt werden. Man kann für jede Transition dann festlegen, welche Veränderungen der Variablen stattfinden sollen. Als Beispiel soll das Template A aus der vorherigen Spezifikation eine lokale Variable x erhalten, die mit dem Wert Null initialisiert, bei jeder a-Kommunikation hochgezählt und bei jeder c-Kommunikation runtergezählt wird. Es wird folgende lokale Variable genutzt. // lokale Variablen int x:=0;
Zuweisungen können bei Timed Automata mit x:=0 oder x=0 erfolgen, was semantisch die gleiche Bedeutung hat. Da die Zuweisung mit := sich besser von dem Vergleich mit == auf Gleichheit unterscheidet, wird dieser Ansatz verfolgt. Abb. 92 zeigt das veränderte Template für A. Man erkennt, dass es verschiedene Möglichkeiten gibt, die Veränderung lokaler Variablen zu beschreiben. Die offensichtlichste Variante ist es, die Änderung direkt an die Transition zu schreiben. Falls es mehrere Änderungen geben soll, sind diese mit einem Komma zu trennen. Die zweite Variante ist die Nutzung von Funktionen, die dann wiederholt im Template genutzt werden können. Diese Funktionen basieren auf der C-Syntax, aus der die Notationen für if, while- sowie for-Schleifen übernommen werden. Die Funktion sub sieht dann wie folgt aus.
119
3 Modelchecking mit Timed Automata und Uppaal Template A
c? sub(x)
a! x:=x+1
Abb. 92: Template mit lokaler Variable void sub (int& v){ v:=v-1; }
Ähnlich wie bei den meisten Programmiersprachen ist bei der Übergabe von Variablen zu klären, wie diese übergeben werden. Es werden folgende Varianten unterstützt. Call by Value (int x): Es wird eine vollständige Kopie des übergebenen Werts erstellt, Veränderungen der Variable x sind nur in der Funktion bekannt und haben keine Auswirkungen auf die beim Aufruf genutzte Variable. Call by Reference (int& x): Es wird eine Referenz auf die übergebene Variable erstellt, x hat den gleichen Speicherplatz wie die übergebene Variable, Veränderungen der Variable x verändern auch die beim Aufruf genutzte Variable. Im konkreten Fall wird die übergebene Variable um Eins verringert. Variablen können auch genutzt werden, um Vorbedingungen anzugeben, die erfüllt sein müssen, damit eine Transition ausgeführt werden kann. Dies soll mit folgendem Beispiel in Abb. 93 verdeutlicht werden.
Template A
Template B v%2==1
q?
d! v:=(v+1)%256
v%2==0 c! v:=v+1
v%4==0 e!
q!
c?
e?
v:=v+1 d?
q!
Abb. 93: Transitionen mit Bedingungen Dabei steht % wieder für die Modulo-Rechnung, also 7%3==1. Die beiden Templates nutzen die folgenden Kommunikationen
120
3.1 Synchron kommunizierende Automaten //global chan c,d,e,q;
Das System wird durch system A,B;
zusammengebaut. Weiterhin hat A eine lokale Variable int[0,255] v:=0;
Durch die Angabe des Intervalls [0,255] wird festgelegt, dass v nur Werte aus diesem Bereich, einschließlich der Grenzen, annehmen darf. Wird der Wertebereich verlassen, handelt es sich um einen Spezifikationsfehler. Betrachtet man die Spezifikation als Parallelkomposition von A und B zunächst ohne Vorbedingungen, dann kann am Anfang nichtdeterministisch zwischen c und e gewählt werden, danach sind dann nur q, d und wieder q möglich. Dies entspricht dem regulären Ausdruck ((c+e).q.d.q)*. Durch die Vorbedingungen ist am Anfang weiterhin die Auswahl zwischen c und e offen. Danach hat v den Wert 1. Nach q.d.q hat v den Wert 2. Jetzt ist v%2==0 erfüllt, aber nicht v%4==0, so dass jetzt nur noch c ausgeführt werden kann. Nach weiteren q.d.q hat v den Wert 4 und c sowie e sind wieder möglich. Insgesamt gehört damit zur Spezifikation der reguläre Ausdruck ((c+e).q.d.q.c.q.d.q)*. Zunächst irritiert es leicht, dass hier die Bezeichnung Template für Automaten genutzt wird. Der Name wird aber plausibel, wenn man die jetzt vorgestellte Möglichkeit kennt, dass man über Parameter steuern kann, dass es mehrere gleichartige Automaten gibt. Dies wird durch folgende Spezifikation veranschaulicht. Für alle Datentypen gibt es zunächst die Möglichkeit, Arrays dieser Datentypen in der von C bekannten Art zu bilden. //global const int N:=4; chan c[N]; chan d[N]; bool gesendet[N];
Konstanten werden durch das Schlüsselwort const eingeleitet, es gibt vier c-Kanäle mit den Namen c[0], c[1], c[2] und c[3], vier d-Kanäle und vier Boolesche Variablen. Die Spezifikation in Abb. 94 zeigt ein parametrisiertes Template Emp. Diesem Template wird ein Parameterwert im Parameter name zur Konstruktion eines neuen konkreten Template übergeben. Danach ist Emp bereit, auf einem c[name]-Kanal zu empfangen und dann auf d[name] zu senden. Die parametrisierten Templates müssen vor der Nutzung der Spezifikation wie folgt zur Erzeugung konkreter Templates genutzt werden, leider gibt es hier keine Schleifennotation.
121
3 Modelchecking mit Timed Automata und Uppaal Template Emp Parameter: int name c[name]?
d[name]!
Abb. 94: Parametrisiertes Template // E0 E1 E2 E3
template instantiations = Emp(0); = Emp(1); = Emp(2); = Emp(3);
Ergänzend soll jetzt ein Prozess V spezifiziert werden, der abwechselnd mit den vier Emp-Prozessen kommuniziert. Die gesamte Spezifikation hat dann die folgende Form. // processes composed to system system V,E0,E1,E2,E3;
Der Ablauf bei V soll so sein, dass mit den vier Emp-Prozessen in beliebiger Reihenfolge einmal die Kommunikationsfolge c[i] und d[i] durchlaufen wird. Erst wenn alle vier Prozesse kommuniziert haben, dann sollen die Prozesse erneut wieder in beliebiger Reihenfolge kommunizieren können. Formal bedeutet dies, dass für jede Sequenz w von Kommunikationen gilt, dass für alle i und j zwischen Eins und Vier die Anzahl der Vorkommen der c[i] in w sich maximal um eins von den Vorkommen der c[j] in w unterscheiden kann. Gleiches gilt auch für dKommunikationen. Template V
i:int[0,N-1] d[i]? check()
i: int[0,N-1] !gesendet[i] c[i]! sum:=sum+i, gesendet[i]:=true
Abb. 95: Parametrisierte Transitionen Formal benötigt V am Anfang vier Kommunikationsmöglichkeiten c[0], c[1], c[2], c[3]. Dies kann, wie in Abb. 95 gezeigt, durch die Nutzung einer parametrisierten Transition vereinfacht werden. Der Ausdruck i:int[0,N-1] bedeutet, dass es für
122
3.1 Synchron kommunizierende Automaten jedes i in dem genannten Intervall, hier mit den Werten 0, 1, 2 und 3, eine Transition geben soll. Auf den Index i kann bei der weiteren Beschreibung der Transition in Vorbedingung, Kommunikation und Nachbedingung direkt zugegriffen werden. Man beachte, dass das i an der mit d[i] beschrifteten Kante nichts mit dem i an der mit c[i] beschrifteten Kante zu tun hat; es handelt sich dabei um lokale Variablen der Transitionen. Damit ein Prozess nicht zu häufig sendet, werden Boolesche Wächter gesendet[i] eingeführt, die am Anfang, insofern keine Startwerte angegeben sind, automatisch auf false gesetzt werden. Nur wenn gesendet[i] noch false ist, kann die zugehörige Kommunikation c[i] ausgeführt werden. Danach wird als Spielerei der Wert von i auf sum aufaddiert. Relevant für den weiteren Ablauf ist, dass der Wert von gesendet[i] auf true gesetzt wird. Die Kommunikation auf d[i] kann ohne Vorbedingung stattfinden, dabei wird die Funktion check ausgeführt. Die lokalen Informationen für V sehen wie folgt aus. // local V int sum:=0; void check(){ bool allegesendet:=true; for(i: int[0,N-1]) allegesendet:=allegesendet && gesendet[i]; if(allegesendet) for(i: int[0,N-1]) gesendet[i]:=false; }
Die Funktion zeigt, dass es neben den aus C bekannten Schleifen auch eine auf der Intervallschreibweise basierende Schleifennotation gibt. Mit der ersten Schleife wird dabei geprüft, ob schon über alle vier Kanäle gesendet wurde, nur wenn dies der Fall ist, hat allegesendet nach der ersten Schleife den Wert true. In diesem Fall werden dann in der zweiten Schleife alle Booleschen Wächter wieder auf false gesetzt. Die Funktionsschreibweise hat den Vorteil, dass man viele Informationen aus der Graphik heraushalten kann. Später wird es sich aber bei der Simulation und der Suche nach Fehlern zeigen, dass es schwierig ist, Fehler in diesen Funktionen zu finden, da sie nicht Schritt für Schritt ausgeführt werden können. Es gibt immer die Alternative zur Nutzung von Funktionen, den Funktionsablauf im Automaten zu beschreiben, was diesen Automaten, wie in Abb. 96 ersichtlich, komplizierter macht, aber später die schrittweise Ausführung in der Simulation zur Fehlersuche erleichtert. Die neue Spezifikation von V, die die alte ersetzt, hat folgende lokale Variablen. // local V int sum:=0; int[0,N] tmp; bool allegesendet;
123
3 Modelchecking mit Timed Automata und Uppaal Die Variable tmp wird als Schleifenzähler genutzt, die Boolesche Variable allegesendet wird wie in der Funktion check genutzt. tmp==N tmp
tmp==N && !allegesendet
gesendet[tmp]:=false, tmp:=tmp+1 tmp==N && allegesendet tmp:=0 tmp
i: int[0,N-1] d[i]? tmp:=0, allegesendet:=true
i: int[0,N-1] !gesendet[i] c[i]! sum:=sum+i, gesendet[i]:=true
allegesendet:= allegesendet && gesendet[tmp], tmp:=tmp+1
Abb. 96: Algorithmus als Template Sollen bei einer Kommunikation Werte übertragen werden, so werden dazu globale Variablen genutzt, die vom Sender beschrieben und vom Empfänger gelesen werden. Dies soll mit einem kleinen Beispiel verdeutlicht werden, bei dem ein Sender die Werte von Eins bis Zehn zu einem Empfänger übertragen möchte.
Template Sender
Template Empfaenger
senden<max c! senden:=senden+1
c? summe:=summe+senden
Abb. 97: Übertragung von Werten Abb. 97 zeigt die Templates zu den Prozessen. Es werden folgende globale Variablen deklariert. const int max:=10; int[0,max] senden:=0; chan c;
Der Empfänger hat noch folgende lokale Variable. int summe:=0;
Das Gesamtsystem ist wie folgt spezifiziert. system Sender,Empfaenger;
124
3.2 Spezifikationen mit Zeit Als erstes wird der Wert 1 an den Empfänger übertragen. Daraus kann man auch die detaillierte Semantik einer gemeinsamen Transitionsausführung zweier Prozesse ableiten. 1.
Es wird mit den aktuellen Werten geprüft, ob die Vorbedingungen erfüllt sind.
2.
Es wird geprüft, ob Sende- und Empfangsoperation stattfinden können.
3.
Wenn 1. und 2. positiv geprüft werden, kann die Kommunikation stattfinden und es werden zuerst die Zuweisungen des Senders und dann die Zuweisungen des Empfängers ausgeführt.
Als weitere Spezifikationsmöglichkeit bieten Timed Automata an, dass Zustände nur erreicht werden können, wenn zugehörige Zusicherungen erfüllt sind, außerdem können Zustände Namen bekommen. Zustandsnamen und Zusicherungen sind fettgedruckt. Das später vorgestellte Werkzeug Uppaal unterstützt die Lesbarkeit durch die Nutzung verschiedener Farben.
z1 x:=x+1 z2
x:=x+1 z3
x%2==1
x%2==0
Abb. 98: Zustände mit Zusicherungen Die Spezifikation in Abb. 98 nutzt folgende lokale Variable. int x:=0;
Zunächst sieht es so aus, dass nichtdeterministisch immer eine der ausgehenden Kanten in z1 nutzbar ist. Da eine Transition aber nur ausgeführt werden kann, wenn die Zusicherung des erreichten Zustands erfüllt ist, werden immer abwechselnd die linke und dann die rechte ausgehende Transition von z1 gewählt.
3.2 Spezifikationen mit Zeit Die Untersuchung zeitlichen Verhaltens spielt bei verteilten Systemen oft eine große Rolle, da Fragen nach der schnellstmöglichen Reaktion und nach maximalen Antwortzeiten beantwortet werden sollen. Weiterhin gibt es Kommunikationsprotokolle, die ohne Zeitbetrachtung funktionieren und erst durch die Berücksichti-
125
3 Modelchecking mit Timed Automata und Uppaal gung der Zeit Probleme haben. Genauso ist die andere Variante möglich, dass die Korrektheit eines Protokolls auf Zeitannahmen basiert. Grundsätzlich verbraucht jeder Rechenschritt, ausgehend von der einfachen Zuweisung bis zur ausgeführten Kommunikation, Zeit. Wenn man allen Schritten einen Zeitaspekt zuordnen will, werden Spezifikationen sehr komplex. Aus diesem Grund nutzen Timed Automata einen anderen Zeitansatz, der aber die Modellierung der anderen Zeitansätze erlaubt. In Timed Automata gibt es den zusätzlichen Datentypen clock. Es ist festgelegt, dass Zeit nur in Zuständen verbraucht wird, also die Ausführung von Transitionen keine Zeit verbraucht. Da der Begriff Zustand im eigentlichen Sinn nicht mit dem Verbrauchen von Zeit in Verbindung gebracht wird, nutzen die Autoren der Timed Automata auch nicht den Begriff Zustand, sondern location, der ins Deutsche als Lokation oder besser Aufenthaltsort übersetzt werden kann. Da der Zustandsbegriff genügend anschaulich ist, wird hier auf eine weitere Begriffsbildung verzichtet. Uhren messen Zeit und dazu wird eine Zeiteinheit benötigt. Bei Timed Automata werden abstrakte Zeiteinheiten genutzt, denen man in realen Spezifikationen z. B. die Semantik von Sekunden oder Mikrosekunden zuordnen kann. Da man durch die Einführung von Zeitvariablen leicht einen unentscheidbaren Modellierungsansatz erhalten kann, gibt es folgende Restriktionen bei der Verwendung von Zeitvariablen in Timed Automata. – Uhren können nur mit einer anderen Uhr oder ganzzahligen Ausdrücken, die keine Uhren enthalten, verglichen werden. – In Bedingungen dürfen mehrere Teilbedingungen, die sich auf Uhren beziehen, nicht mit „oder“ verknüpft werden. – In Zuweisungen können Uhren nur auf den Wert Null zurückgesetzt werden. start x<=2 x>2
weiter
Abb. 99: Template mit Zeit
126
x>1
x<=3
3.2 Spezifikationen mit Zeit Es wird jetzt die Spezifikation aus Abb. 99 mit einer lokalen Uhr clock x; betrachtet. Die Zusicherung in start garantiert, dass dieser Zustand nach spätestens 2 Zeiteinheiten verlassen wird; die beiden Transitionen kann man sich auch mit der Bedingung true beschriftet vorstellen. Wichtig ist, dass Uhren nicht automatisch zurückgesetzt werden. Da es in der Spezifikation kein x:=0 gibt, wodurch eine Uhr zurück gesetzt wird, läuft die Uhr immer weiter. Der Zustand weiter muss nach maximal drei Zeiteinheiten verlassen werden. Da die Zusicherung in start garantiert, dass maximal zwei Zeiteinheiten vergangen sind, kann diese Transition nicht ausgeführt werden, wenn mehr als zwei Zeiteinheiten insgesamt in weiter verbracht wurden. Insgesamt wird also die ausgehende Transition von start im Zeitintervall [0,2] ausgeführt. Ab drei Zeiteinheiten befindet sich die Spezifikation in einem inkonsistenten Zustand, da die Zusicherung des Zustands weiter nicht mehr erfüllt ist und keine ausgehende Transition genutzt werden kann. Da es keine Verpflichtung gibt, Zeit in einem Zustand zu verbringen, kann man beliebig oft beliebig schnell zwischen den beiden Zuständen wechseln. Formal ist eine Verweildauer von Null Zeiteinheiten erlaubt. Dies klingt zunächst irritierend, macht aber den Spezifikationsansatz, wie später gezeigt, flexibler. start
x<=4 x>3 && drei<5
x:=0
x>2 && zwei<5 zwei:=zwei+1
drei:=drei+1
weiter
Abb. 100: Nichtdeterminismus mit Zeit Die Spezifikation aus Abb. 100 wird um folgende lokale Variablen ergänzt. clock x; clock y; int [0,5] zwei:=0; int [0,5] drei:=0;
Der Zustand start muss nach maximal vier Zeiteinheiten verlassen werden, nach mehr als zwei Zeiteinheiten und erfüllter Nebenbedingung zwei<5 kann die linke und nach mehr als drei Zeiteinheiten und erfüllter Nebenbedingung drei<5 auch nichtdeterministisch die rechte Transition genutzt werden.
127
3 Modelchecking mit Timed Automata und Uppaal zwei 0 drei 0
1
2
1
start weiter Zeit
x 0 Gesamtzeit y 0
2.7 2.7
0 9
3.7 0 12.7 12.7
3.1 15.8
Abb. 101: Zeitdiagramm Da es im Zustand weiter keine Zusicherung gibt, kann sich das System beliebig lang in diesem Zustand aufhalten. Es ist dabei jederzeit möglich, in den Zustand start zurückzukehren, wobei dann die Uhr x auf Null gesetzt wird. Abb. 101 zeigt einen möglichen Ablauf in Form eines Zeitdiagramms. Oben erkennt man die Werte bzw. Wertänderungen der Variablen zwei und drei. In der Mitte erkennt man den Wechsel zwischen den Zuständen; unten ist der Wert der Uhr x und die vergangene Gesamtzeit angegeben, dabei schreitet die Zeit kontinuierlich fort. Im Beispiel wird nach 2.7 Zeiteinheiten der Zustand start verlassen. Danach wird eine längere Zeit im Zustand weiter verbracht und mit dem Übergang von weiter nach start der Wert von x von 6.3 auf Null gesetzt. Nach weiteren 3.7 Zeiteinheiten findet ein erneuter Zustandswechsel nach weiter statt, wobei dieser Zustand unmittelbar wieder verlassen wird. Nach weiteren 3.1 Zeiteinheiten wird diesmal die andere Kante in den Zustand weiter genutzt, danach kann das System auch beliebig lange in weiter verweilen. Die Uhr y spielt anscheinend keine Rolle, sie dient aber zum Messen der insgesamt verbrauchten Gesamtzeit. Man kann sich z. B. fragen, welchen Wert y minimal angenommen haben kann, wenn im Zustand start ein Deadlock erreicht wird, bei dem der Zustand nicht mehr verlassen werden kann. Jede ausgehende Transition kann fünfmal gewählt werden, so dass der kleinste Wert von y mehr als 25 Zeiteinheiten sein muss. Da man sich beliebig lange im Zustand weiter aufhalten darf, erübrigt sich die Frage nach dem maximalen Wert. Die Spezifikation in Abb. 102 zeigt die Möglichkeit, die Durchführung eines schnellen Doppelklicks zu spezifizieren. Der Nutzerprozess auf der linken Seite kann dazu zu beliebigen Zeitpunkten eine klick-Kommunikation durchführen. Generell kann man mit Timed Automata nur sogenannte geschlossene Systeme verifizieren. Dies sind Systeme, die bei ihrer Ausführung keine Nutzerinteraktion durchführen können. Um trotzdem Systeme mit Nutzerinteraktion zu betrachten, wird der Nutzer durch einen möglichst flexiblen nichtdeterministischen Prozess ersetzt. Die Klickanalyse nutzt folgende lokale Variablen. clock x; int[0,2] modus:=0;
128
3.2 Spezifikationen mit Zeit start start klick!
klick? x:=0
modus:=1 einfach
x<=3 klick?
modus:=2
doppelt
Abb. 102: Doppelklick Wird ein erster Klick durchgeführt, so wird in den Zustand einfach gegangen und die Uhr x zurückgesetzt. Jetzt hängt der nächste Übergang von der Schnelligkeit des Klicks ab. Ist der Klick zu langsam, nach mehr als drei Zeiteinheiten, wird zurück zu start gewechselt und dies als Einzelklick aufgefasst und der Wert von modus auf eins gesetzt. Ist der Klick schnell genug, nach maximal drei Zeiteinheiten, wird modus auf zwei gesetzt. Der Zustand doppelt ist mit einem C für „Committed“ gekennzeichnet. Dies bedeutet, dass dieser Zustand so schnell wie möglich wieder verlassen werden muss, ohne dass hierfür eine weitere Uhr benötigt wird. Dies kann z. B. dazu genutzt werden, dass bei lokalen Berechnungen im Automaten keine Zeit in den zugehörigen Zuständen verbraucht werden soll.
wegen Zeitbedingung nicht ausführbare Transition
wegen Zeitbedingung nicht betretbarer Zustand
Abb. 103: Deadlocks durch Uhren
129
3 Modelchecking mit Timed Automata und Uppaal Zusammengefasst kann man Uhren zur Spezifikation zeitabhängigen Verhaltens und zur Messung verbrauchter Zeit nutzen. Durch die Uhren gibt es zwei Arten von Deadlocks, die in Abb. 103 dargestellt sind. Oben sieht man die Situation, dass der Startzustand ohne Probleme im Intervall (10,20) verlassen wird, dabei bedeuten runde Intervallklammern, dass die jeweilige Grenze nicht angenommen werden kann. Da die Uhr x dann aber einen Wert größer Zehn hat, kann die Bedingung der nächsten ausgehenden Kante x<5 nicht erfüllt werden. Da dieser Zustand aber keine Zusicherung beinhaltet, kann das System in diesem Zustand ruhen, was nach der Timed Automata-Semantik auch als Deadlock aufgefasst wird. Im unteren Beispiel kann der Startzustand wieder nur im Intervall (10,20) verlassen werden. Da dies aber der Zusicherung im Folgezustand widerspricht, kann keine Transition ausgeführt werden. Diese Situation kann gegebenenfalls zur Spezifikation unerwünschter Zustände genutzt werden, was auch aus der zugehörigen Meldung des Simulators rechts unten in Abb. 103 hervorgeht. (a) Deadlock mit Committed (und Urgent) x>=2 c?
c!
(b) Urgent: c und d ausführbar c?
c!
d!
d?
(c) Committed: nur c ausführbar c?
c!
d!
d?
Abb. 104: Unterscheidung von Urgent und Committed Neben dem bereits in der Abb. 102 genutzten „Committed“-Zustand gibt es auch mit „U“ für „Urgent“ gekennzeichnete Zustände. Die Forderung für CommittedZustände ist, dass dieser Zustand im nächsten Schritt verlassen werden muss und keine Zeit verbraucht wird. Eine Ausnahme gibt es nur, wenn sich mehrere Prozesse in Committed-Zuständen befinden, dann muss einer dieser Zustände und damit gegebenenfalls nachfolgend weitere dieser Zustände ohne verlaufende Zeit verlassen werden. Bei Urgent-Zuständen ist die Forderung etwas schwächer. In
130
3.3 Nutzung von Uppaal ihnen darf auch keine Zeit verbraucht werden, es können aber auch beliebige andere Schritte ausgeführt werden, die keine Zeit verbrauchen. Die Unterscheidung zwischen Urgent und Commited wird anhand der Beispiele in Abb. 104 deutlich. In (a) gibt es einen Deadlock egal ob der Zustand links mit einem „U“ oder „C“ gekennzeichnet ist, da bei Urgent und Commited ohne Zeitverlust eine Aktion stattfinden muss. Unter der Annahme, dass die Uhr x am Anfang den Wert Null hat, kann hier aber kein Schritt unmittelbar passieren. In (b) muss ohne Zeitverlust eine Aktion stattfinden, dies kann aber auch die mögliche dKommunikation sein, die alternativ zur c-Kommunikation ausführbar ist. Danach muss wieder eine Aktion stattfinden, die keine Zeit verbraucht. Dabei muss beachtet werden, dass letztendlich der mit „U“ gekennzeichnete Zustand ohne Zeitverlust letztendlich verlassen wird. In (c) muss ohne Zeitverlust eine Aktion stattfinden und der mit „C“ gekennzeichnete Zustand verlassen werden. Aus diesem Grund kann nur die c-Kommunikation stattfinden.
starten
x>=3
angemeldet
x<=7 Abb. 105: Typische Zeitspezifikation Zusammengefasst zeigt Abb. 105 die typische Form der Verwendung von Zeitvariablen in Timed Automata. Die Spezifikation fordert, dass eine Anmeldung zwischen drei und sieben Zeiteinheiten dauert. Die Spezifikation nutzt eine Uhr x und beschreibt, dass der Zustand starten nach mindestens sieben Zeiteinheiten verlassen werden muss. An der ausgehenden Kante steht die Randbedingung, dass diese Kante frühestens nach drei Zeiteinheiten betreten werden kann, erst danach geht die Spezifikation in den Zustand angemeldet. Insgesamt ist so beschrieben, dass eine Anmeldung zwischen drei und sieben Zeiteinheiten benötigt.
3.3 Nutzung von Uppaal Timed Automata werden zusammen mit dem Werkzeug Uppaal an den Universitäten in Uppsala, Schweden und Aalborg, Dänemark kontinuierlich weiterentwickelt. In diesem Unterkapitel wird anhand eines Beispiels gezeigt, wie man mit Uppaal, hier der Version 4, die für Lernzwecke frei verfügbar ist, eine Spezifikation entwickeln und dann simulieren kann. Spezifiziert werden soll ein Weiterleitungsmodul, kurz TM für transmission module, das Nachrichten übernimmt und weiterleitet. Dann wartet das Modul auf eine
131
3 Modelchecking mit Timed Automata und Uppaal Bestätigung, um diese dann an den ursprünglichen Sender zurück zu leiten. Da man auch mit Uppaal keine offenen Systeme spezifizieren kann, die mit der Umwelt kommunizieren, muss diese Umwelt mit modelliert werden. Hierzu sollen ein einfacher Sender Send und ein Empfänger Emp genutzt werden. Nach dem Start von Uppaal befindet man sich im in Abb. 106 gezeigten TemplateEditor, auf der rechten Seite sind die bereits spezifizierten Templates zu sehen. Ein neues Template kann über „Edit->Insert Template“ eingefügt werden. Im Feld Name kann der vorgegebene Templatename geändert werden. Etwaige Parameter stehen in der Liste Parameters durch Kommata abgetrennt. Im Beispiel werden zwei Kanäle übergeben, die von der Spezifikation auch bearbeitet, also zum Senden und Empfangen genutzt werden können, weshalb das Zeichen & für Call by Reference bei den Parametern wichtig ist. Zustandseingabe Transitionseingabe Kanteneckpunkte (Nails)
Prozessparameter (Templateparameter) Prozessname
Abb. 106: Aufbau des Template-Editors Das eigentliche Erstellen des Automaten wird in der Kopfzeile gesteuert, mit der neue Zustände und Transitionen ergänzt werden können. Für Transitionen können so genannte Nails hinzugefügt und gelöscht werden, die für Knicke in der graphischen Darstellung von Transitionen zuständig sind. Der in Abb. 106 mit einem Kasten umgebene Pfeil oben in der Mitte erlaubt dann die weitere Bearbeitung der Spezifikationselemente. Der Sender sendet über einen Kanal send und erwartet dann eine Antwort auf dem Kanal rec für „receive“.
132
3.3 Nutzung von Uppaal Im Projekteditor auf der linken Seite können die Projekteigenschaften und die Eigenschaften einzelner Templates, wie in Abb. 107 gezeigt, durch das Anklicken von „Declarations“ bearbeitet werden. Im Beispiel sieht man, dass für Send eine lokale Variable, genauer eine Uhr y, eingefügt wird, die hier zur Messung von Laufzeiten dient. Wie in Abb. 107 erwähnt, kann man die Überprüfung der Syntax über die Taste F7 ansteuern. Etwaige Fehlermeldungen werden unterhalb des Eingabefeldes ausgegeben. Dieses Feld muss gegebenenfalls vergrößert werden. Um eine sinnvolle Syntaxüberprüfung zu ermöglichen, sollte zumindest eine erste vollständige Systemspezifikation eingegeben worden sein.
„System Editor“ zur Eingabe „Declarations“: Eingabefenster für lokale Variablen Syntaxprüfung mit F7 (oder File->Check Syntax), Ergebnis wird unten angezeigt (von Hand vergrößern)
Abb. 107: Projektübersicht in Uppaal Durch einen Doppelklick auf einen Zustand können, wie in Abb. 108 gezeigt, dessen Eigenschaften eingegeben werden. Dies ist der Name und die Zusicherung, die man auch Zustandsinvariante nennen kann. Es muss immer genau ein Zustand pro Template als Anfangszustand (Initial) gekennzeichnet werden. Weiterhin ist eine Kennzeichnung mit „Urgent“ oder „Committed“ möglich. Abb. 108 zeigt die Spezifikation des Empfängerprozesses Emp, der keine lokalen Variablen nutzt. Der Prozess wartet auf eine Kommunikation rec, um diese dann mit einer Kommunikation ack für acknowledge zu beantworten.
133
3 Modelchecking mit Timed Automata und Uppaal
Empfängerprozess Emp Doppelklick auf Zustand ermöglicht Eingabe von Invarianten und Zustandsart
Abb. 108: Spezifikation von Zuständen
Abb. 109: Spezifikation von Transitionen
134
3.3 Nutzung von Uppaal Abb. 109 zeigt den Automaten des eigentlichen Weiterleitungsmoduls TM. Weiterhin wurde die linke obere Kante mit einem Rechtsklick geöffnet. Im Select-Feld kann eine Laufvariable eingetragen werden, falls es sich nicht um eine, sondern um eine Menge von Transitionen handeln soll. Im Feld Guard wird die Vorbedingung als Boolesche Bedingung eingetragen. Im Feld Sync steht die synchrone Kommunikation. Im Feld Update werden durch Kommata getrennt alle Änderungen der Variablen eingetragen. Die Spezifikation hat eine lokale Uhr x, die in der Abbildung links unten gezeigt wird. Am Anfang wird auf eine Eingabe über den Kanal in gewartet. Dann benötigt TM zwischen 2 und 5 Zeiteinheiten, um eine Weiterleitung über den Kanal weiter durchzuführen. Danach wird auf eine Kommunikation antwort gewartet, und es vergehen zwischen ein bis vier Zeiteinheiten, bis TM bereit ist, eine Bestätigung über den Kanal zurückzuschicken.
Abb. 110: Globale Projekteigenschaften Abb. 110 zeigt die Möglichkeit, globale Informationen zu spezifizieren. Man sieht, dass es jeweils vier send- und rec-Kanäle geben soll. Das Gesamtsystem wird in dem Eintrag „System declarations“ zusammengebaut, wie es in Abb. 111 gezeigt wird. Dazu werden zunächst aus den parametrisierten Templates konkrete Prozesse, wobei hier keine Schleifen und Arrays erlaubt sind, also Trans[i] ist auf der linken Seite nicht erlaubt. Aus allen Prozessen wird dann die Systemspezifikation zusammengesetzt.
135
3 Modelchecking mit Timed Automata und Uppaal
Hier müssen globale Variablen stehen, direkte Angaben wie 2 als Parameter sind nicht möglich
Abb. 111: Zusammenbau des Systems
Ausführbare Aktionen
bisher ausgeführte Aktionen
Simulationssteuerung
aktuelle Variabenwerte (mit Uhren)
Prozesse in ihren aktuellen Zuständen
ausgeführte Aktionen als Message Sequence Chart
Abb. 112: Überblick über die Simulationskomponente Abb. 112 zeigt einen Überblick über den Simulator, mit dem Spezifikationen interaktiv oder automatisch ausgeführt werden können. Im Bereich „Ausführbare Aktionen“ sind alle Schritte aufgeführt, die als Nächstes ausgeführt werden können. Durch die Auswahl eines Schritts wird die zugehörige Transition in der Prozess-
136
3.3 Nutzung von Uppaal übersicht rechts oben rot markiert. Weiterhin zeigt die Prozessübersicht, in welchen Zuständen sich die einzelnen Prozesse befinden. Für jede ausgewählte Aktion werden im Bereich „aktuelle Variablenwerte“ die aktuellen Werte aller Variablen angegeben. Für Uhren können dies auch Zeitintervalle sein. Weiterhin können für Abstände zwischen Uhren Zeitintervalle angegeben werden. Unterhalb der Aktionssteuerung befindet sich eine Übersicht über die bisher ausgeführten Schritte. Man kann diese Schritte auch anwählen und wird dann über die dort erhaltenen Variablenwerte informiert. Weiterhin kann man dann ausgehend von diesem Zustand andere Aktionen verfolgen. Es ist zu beachten, dass hier immer nur eine ausgeführte Sequenz angezeigt werden kann, was die Analyse von Alternativen recht aufwändig gestaltet. Die ausgeführten Aktionen sind auch in einer Message Sequence Chart rechts unten dargestellt. Geht man mit der Maus über die erwähnten Zustände, erhält man noch zusätzliche Detailinformationen. Links unten befindet sich die Simulationssteuerung, die alternativ zum „Next“ bei den ausführbaren Aktionen gewählt werden kann. Simulationssteuerung: Simulationen können geladen, gespeichert und wiederholt werden
Bei Random läuft die Simulation automatisch ab, dazu kann die Geschwindigkeit eingestellt werden (Ist Togglebutton, bleibt also gedrückt)
Abb. 113: Simulationssteuerung Abb. 113 zeigt die Simulationssteuerung, mit der man einen Schritt rückwärts (Prev) oder einen Schritt vorwärts (Next) gehen kann, insofern eine Ausführungssequenz bearbeitet wird. Die bisher ausgeführten Aktionen kann man mit „Replay“ erneut abspielen. Simulationsabläufe können mit „Open“ geladen und mit „Save“ gespeichert werden. Mit „Random“ (in neueren Versionen „Auto“) wird zufällig eine ausführbare Aktion ausgewählt. Die Geschwindigkeit dieser zufälli-
137
3 Modelchecking mit Timed Automata und Uppaal gen Ausführung kann mit dem Schieberegler darunter eingestellt werden. Um eine zufällige Simulation zu beenden, muss der Random-Knopf erneut gedrückt werden. Weitere Spezifikationsmöglichkeiten werden im folgenden Unterkapitel zusammen mit dem Verifikationsansatz vorgestellt.
3.4 Timed Computation Tree Logic und Verifikation Vergleichbar zu dem Ansatz mit der Spezifikationssprache PROMELA und dem zugehörigen Werkzeug SPIN kann man auch für Timed Automata mit Uppaal Modelchecking durchführen. Während in SPIN die Logik LTL genutzt wurde, wird hier die Timed Computation Tree Logic TCTL eingesetzt, die hier in der Version, die von Uppaal genutzt wird, vorgestellt wird. Ausgangszustand alle möglichen Folgezustände
wieder unendliche Abläufe betrachtet
Abb. 114: Baumdarstellung alternativer Abläufe Ähnlich wie bei LTL werden in TCTL Anforderungen an mögliche Abläufe des Modells spezifiziert. In LTL werden dabei einzelne Abläufe betrachtet, in TCTL alle möglichen Abläufe ab einem bestimmten Zustand. Man kann sich das wie in Abb. 114 dargestellt als einen Baum von alternativen Berechnungen, die ausgehend vom Wurzelknoten möglich sind, vorstellen, wobei es natürlich nicht immer zwei Verzweigungsmöglichkeiten geben muss. Dies begründet die Namensanteile „Computation Tree“. Da wir zusätzlich Schlüsse über die für Timed Automata eingeführten Uhren erlauben, spricht man von einer „Timed“-Logik. Formal kann man zeigen, dass man mit LTL und (T)CTL unterschiedliche Anforderungen spezifizieren kann, und dass das Modelchecking bei den Komplexitätsbetrachtungen für CTL „einfacher“ als für LTL ist. Es wird hier auf eine vollständig formale Einführung in TCTL verzichtet, da sie angelehnt an die LTL-Semantik erfolgen kann. Definition (Syntax der Timed Computation Tree Logik (TCTL)): Einfache Prädikate werden durch folgende Regeln gebildet:
138
3.4 Timed Computation Tree Logic und Verifikation Im können außer Uhren beliebige Variablen vorkommen, z. B. x+y-4. Als Operatoren sind <, <=, !=, ==, >= und > erlaubt. Wenn p und q einfache Prädikate sind, dann auch (p), !p, p imply q sowie die spezielle Formel deadlock.
p && q, p || q,
In TCTL-Formeln darf ein Temporaler Operator genutzt werden, der sich aus zwei Teilen zusammensetzt. Der erste Teil ist der Pfadoperator, für den es zwei Möglichkeiten gibt. A: für alle Pfade E: es gibt einen Pfad Weiterhin gibt es zwei temporale Operatoren. : immer ¡: irgendwann Seien p und q zwei einfache Prädikate, dann sind p und q TCTL-Formeln und auch A p
(all pathes always, „immer“)
A¡ p
(all pathes sometimes, „immer irgendwann“)
E p
(exists a path always, „für einen Weg immer“)
E¡ p
(exists a path sometimes, „kann garantiert irgendwo“)
p q
(p leads to q, „wenn p, dann irgendwann q“)
In Uppaal wird die logische Implikation mit „imply“ ausgeschrieben, da der Pfeil „“ für einen speziellen „leads to“-Operator genutzt wird. Man beachte, dass immer nur ein Pfad- und ein temporaler Operator zusammen hier erlaubt werden, es sind keine Verschachtelungen möglich. In der Literatur wird statt häufig auch G (globally, überall) und statt ¡ F (finally, letztendlich) geschrieben. Anstelle einer präzisen Semantik wird jetzt eine Veranschaulichung der wichtigsten Formeln gegeben.
A
p
A[] p
...
... ...
... ...
... ...
...
: genau hier gilt p
Abb. 115: Veranschaulichung von "immer"
139
3 Modelchecking mit Timed Automata und Uppaal Abb. 115 zeigt die anschauliche Semantik von A p, was einer Invarianten entspricht. Weiterhin ist in dieser und den folgenden Abbildungen immer angegeben, wie die ASCII-Schreibweise in Uppaal aussieht. Dabei ist zu beachten, dass z. B. zwischen A und [] keine Leerzeichen stehen.
E
p
E[] p
...
... ...
... ...
... ...
...
Abb. 116: Veranschaulichung von "auf einem Weg immer" Zur Erfüllung von E p muss es einen unendlichen Pfad geben, wie in Abb. 116 gezeigt, auf dem die geforderte Eigenschaft immer gilt.
A¡p A<> p
...
... ...
... ...
... ...
...
Abb. 117: Veranschaulichung von "immer irgendwann" Die Formel A¡ p wird, wie in Abb. 117 gezeigt, erfüllt, wenn für alle Pfade ausgehend vom untersuchten Zustand immer gilt, dass man bei einem Zustand vorbeikommt, in dem die gesuchte Eigenschaft gilt.
E¡p E<> p
...
... ...
... ...
... ...
Abb. 118: Veranschaulichung von "möglich"
140
...
3.4 Timed Computation Tree Logic und Verifikation Die Formel E¡ p ist, wie in Abb. 118 gezeigt, die schwächste Anforderung, da es hier überhaupt nur die Möglichkeit geben muss, dass die gesuchte Eigenschaft einmal erfüllt wird. Abb. 119 veranschaulicht die „leads to“-Formel, wobei für alle möglichen Abläufe nur gelten muss, dass, wenn p gilt, dann muss garantiert werden, dass q irgendwann später einmal gilt. Man beachte dazu, dass q z. B. links unten in der Abbildung nicht unmittelbar auf den Zustand folgt, der p erfüllt. Würde man unsere temporale Logik erweitern, so könnte man statt pq auch A (p imply (A¡ q)) schreiben.
p q p leads to q
p p
q q
...
q
... ...
q
... ...
q
... ...
...
p --> q
Abb. 119: Veranschaulichung von "wenn, dann später" Es werden typischerweise folgende Formeln für Sicherheit und Lebendigkeit genutzt. - A p, steht für eine Invariante p, also eine Sicherheitseigenschaft. - E p, steht für eine Lebendigkeitseigenschaft, da gefordert wird, dass es eine garantierte Ausführungsmöglichkeit gibt, auf der immer p gilt. Diese Anforderung enthält auch einen Sicherheitsaspekt, da man für jeden Zustand die Eigenschaft prüfen muss, ob ab hier auf einem Pfad immer p gilt. - A¡ p, ist eine Lebendigkeitsanforderung, da garantiert ein Zustand erreicht werden muss, der p erfüllt. - E¡ p, ist wie E p eine Mischung aus einer Lebendigkeitseigenschaft, da gefordert wird, dass es möglich sein muss, p zu erfüllen und einer Sicherheitseigenschaft, da für jeden Zustand die Eigenschaft geprüft wird, ob p später möglich ist. - p q ist eine Lebendigkeitseigenschaft, da ein Zustand, der p erfüllt, immer dazu führen muss, dass in der Zukunft irgendwann einmal q gilt. Abb. 120 zeigt die Verifikationskomponente von Uppaal mit ihren Ein- und Ausgabemöglichkeiten. Zu beachten ist, dass Formeln, in Uppaal Queries genannt, getrennt zur Spezifikation unter „File –> Save Queries“ abgespeichert werden können.
141
3 Modelchecking mit Timed Automata und Uppaal
Ansicht der Formeln (keine Änderung) Formeln werden durch Anklicken selektiert (mehrere mit gedrückter Hochstelltaste) Modelchecking starten, unten wird Ergebnis angezeigt Formelverwaltung Eingabe von Formeln informeller Kommentar
Abb. 120: Aufbau der Verifikationskomponente
int i:=0;
Abb. 121: Analyse von Fairness in Uppaal Wie bei der LTL-Verifikation von verteilten Systemen stellt sich die Frage, wie bei der Verifikation mit Fairness umgegangen wird, wie es im Abschnitt 2.4.6 allgemein erklärt wurde. Dies kann mit dem Template Fairness aus Abb. 121 geprüft werden. Wenn schwache Fairness berücksichtigt wird, dann müsste für alle
142
3.4 Timed Computation Tree Logic und Verifikation unendlichen Abläufe gelten, dass die int-Variable i des Prozesses Fairness irgendwann den Wert Zwei erhält. D. h., die Formel A¡ Fairness.i==2 muss erfüllt sein. Über den Namen des Prozesses kann mit der Punktnotation auf die jeweiligen Prozessvariablen zugegriffen und globale Variablen direkt in den Formeln verwendet werden. Die Prüfung mit Uppaal führt zu dem in Abb. 121 rechts gezeigten Ergebnis, Uppaal berücksichtigt Fairness in keiner Weise. Die zweite Formel wurde ergänzt, um zu zeigen, dass i überhaupt den Wert zwei annehmen kann.
Abb. 122: Verifikationseinstellungen
143
3 Modelchecking mit Timed Automata und Uppaal Ähnlich wie bei SPIN können einige Optionen für die Verifikation eingestellt werden, die man in Abb. 122 sehen kann. Mit der Search Order wird festgelegt, welches Verfahren beim Durchlauf der erreichbaren Zustände genutzt wird. Der Breitendurchlauf „Breadth First“ findet meist kürzere Wege zu Fehlern als der Tiefendurchlauf „Depth First“, der meist mit weniger Speicherplatz auskommt. Statt direkt alle Zustände zu speichern, kann man unter State Space Reduction Optimierungen einschalten, die weniger Speicher, aber mehr Rechenzeit verbrauchen. Die wichtigsten Einstellungen betreffen wieder Systeme, für die die Verifikation zu lange dauern würde oder die zu viel Speicherplatz benötigen würden. Für solche Spezifikationen gibt es die Einstellungsmöglichkeiten „Under Approximation“, wodurch eventuell zu wenig Zustände betrachtet werden und „Over Approximation“, wodurch zu viele Zustände betrachtet werden. Die mit diesen Einstellungen erzielten Ergebnisse lassen keinen endgültigen Schluss auf die Korrektheit des Systems zu, wie in der Diskussion zur Abb. 46 gezeigt wurde. Werden zu wenige Zustände betrachtet, fallen eventuell die kritischen Zustände aus der Betrachtung heraus, bei zu vielen Zuständen werden eventuell genau diese Zustände als Lösung des Problems erkannt. Mit Diagnostic Trace wird festgelegt, ob und wie ein Pfad zu einem Fehler berechnet wird. Mit „None“ wird kein Pfad berechnet, was den Verifikationsaufwand verkürzt. Generell fängt man mit „None“ an, um bei einem Fehlerfall dann eine der anderen Varianten zu nutzen. Formal können die Uhren beliebige reelle Werte annehmen, die im Model Checker auf eine passende endliche Menge von Intervallen aufgeteilt werden. Diese zeitlich aufwändige Aufteilung kann durch verschiedene schnellere Algorithmen im Punkt Extrapolation angenähert werden, durch die aber nur eine Obermenge der erreichbaren Zustände betrachtet wird. Eine Ausnahme stellt die Einstellung „None“ dar, die die aufwändige Intervall-Berechnung abschaltet, aber so gegebenenfalls zu einer nicht-terminierenden Untersuchung führt. Der Punkt „Extrapolation“ ist typischerweise der letzte Punkt, an dem man versucht, eine Verifikation zu optimieren. Die Hash table size ist für die Effizienz des Modelcheckings relevant und richtet sich nach dem zur Verfügung stehenden Hauptspeicher, wird aber nur zusammen mit dem Punkt „Under Approximation“ genutzt. Standardmäßig ist Uppaal so eingestellt, dass keine „Diagnostic Trace“ erstellt wird, um die Verifikation möglichst schnell und speicherplatzsparend auszuführen. Dabei ist zu beachten, dass eine Diagnostic Trace abhängig von der verifizierten Eigenschaft unterschiedliche Bedeutungen haben kann. Schreibt man eine Anforderung mit dem Pfadquantor „für alle Pfade“, kann eine Diagnostic Trace ein Gegenbeispiel liefern. Nutzt man eine Anforderung mit einem Pfadquantor „es gibt einen Pfad“, macht ein Gegenbeispiel keinen Sinn, da nur die Menge aller Gegenbeispiele zusammen interessant ist. Die Diagnostic Trace enthält sinnvollerweise stattdessen einen Ablauf, der die Erfüllung der Anforderung zeigt. Dies soll anhand einiger Beispiele konkretisiert werden.
144
3.4 Timed Computation Tree Logic und Verifikation s3 i:=i+3 s1 x<=2
s2 i:=4, x:=0
i:=i+5 x<8
s5
s4
x<2
i:=i+7
i:=i+2
x<7
x:=0 s6 i:=i+2, x:=0
x<5
Abb. 123: Analysebeispiel Die Spezifikation P in Abb. 123 nutzt die lokalen Variablen clock x und int i. Man kann sich vorstellen, dass in der Variablen i die Kosten für die Durchführung eines Arbeitsschritts berechnet werden, wobei x die Bearbeitungsdauer misst. Zunächst wird die Anforderung aufgestellt, dass P immer den Zustand s3 durchläuft, wobei mit dem Prädikat P.s3 geprüft wird, ob die Eigenschaft „P ist im Zustand s3“ erfüllt ist. Die Anforderung lautet: A¡ P.s3 Uppaal erzeugt ein Gegenbeispiel mit einem unendlichen Ablauf, das dann im Simulator betrachtet werden kann. Die Prüfung, dass i nie den Wert 42 annimmt mit A P.i!=42 liefert ebenfalls ein Gegenbeispiel. Die Prüfung der Anforderung, dass i irgendwann den Wert 5 annehmen kann mit E¡ P.i==5 scheitert. Da dies bedeutet, dass auf allen möglichen Abläufen i nicht den Wert fünf annimmt, ist es nicht möglich, ein Gegenbeispiel zu konstruieren. Die Prüfung der Anforderung, dass es eine Möglichkeit gibt, dass i immer kleiner als sieben ist, mit E P.i<7 scheitert ebenfalls. Wird allerdings die Uhr aus der Spezifikation entfernt, so ist die Verifikation erfolgreich und es wird ein positives Beispiel konstruiert. Da ohne Uhr der Startzustand nicht verlassen werden muss, ist dies bereits das positive Beispiel. Interessanterweise ist die ähnliche Prüfung von E P.i<8 auch mit Uhren erfolgreich. Die dazu konstruierte Diagnostic Trace zeigt, dass die Ausführung über s1 und s2 nach s3 geht, dort wird gewartet, bis x mindestens den Wert sieben hat. Danach kann der Zustand nicht verlassen werden, da sonst die
145
3 Modelchecking mit Timed Automata und Uppaal Zusicherung des Zustandes s5 verletzt werden würde. Dieser Deadlock wird also bei der Verifikation als gewünschter Deadlock des Spezifizierers angenommen und ist auch in Abb. 124 dargestellt.
Abb. 124: Deadlock im Simulator Möchte man nicht mit erwünschten Deadlocks arbeiten, so ist üblicherweise die erste Forderung, die geprüft wird, die nach der Deadlockfreiheit, was durch die Formel A !deadlock geschieht. Uppaal liefert hier mit der zuletzt beschriebenen Trace ein Gegenbeispiel, dessen Ende im Simulator in Abb. 124 dargestellt ist. Bei deadlock handelt es sich um ein einfaches Boolesches Prädikat, das für jede Situation nach wahr oder falsch ausgewertet werden kann. Damit ist es auch möglich, deadlock mit anderen Booleschen Ausdrücken zu kombinieren. Dies ist insbesondere für terminierende Systeme interessant. Weiß man z. B., dass ein System in den Zuständen z1 und z2 eines Templates P terminieren darf, man zwischenzeitlich aber keine Deadlocks möchte, so kann man dies mit folgender Formel verifizieren. A !deadlock || (P.z1 || P.z2)
3.5 Beispiele reset! start timer
x:=0 reset? timer:=0
timer==grenze abort!
s1 x<5
s0 x<4
x:=0 abort?
abort?
s3
146
s2 abort?
abbruch
Abb. 125: Spezifikation eines Timers
x<6 x:=0
3.5 Beispiele Bei reaktiven Systemen spielen häufig Timer eine wichtige Rolle, die sich z. B. darum kümmern, dass, wenn eine bestimmte Zeit lang keine erwartete Antwort kommt, ein Abbruchsignal geschickt wird. Man kann sich dann fragen, ob das System überhaupt innerhalb der Zeitgrenzen reagieren kann und ob die Zeitgrenzen im Normalfall nicht immer eingehalten werden. Abb. 125 zeigt ein System mit einem Timer-Prozess auf der linken Seite mit den lokalen Variablen const int grenze 10; clock timer;
weiterhin stehen folgende globale Kanäle zur Verfügung. chan reset; chan abort;
Auf der rechten Seite ist ein Bearbeiterprozess spezifiziert, für den analysiert werden soll, ob er schnell genug für den Timer ist. Wenn der Bearbeiter mit seiner lokalen Variable clock x schnell genug ist, sendet er eine reset-Kommunikation an den Timer, so dass die Bearbeitung und der Timer von Neuem startet. Man kann dann prüfen, ob es möglich ist, dass nie eine Abbruch-Kommunikation abort stattfindet. Dabei wird ausgenutzt, dass der Timer dann den Zustand abbruch
erreicht. Die Forderung lautet: E !Timer.abbruch Diese Anforderung wird erfüllt. Die zweite zu beantwortende Frage ist, ob man einen Abbruch immer vermeiden kann. Die zugehörige Anforderung lautet: A !Timer.abbruch Diese Forderung wird nicht erfüllt, da in s2 zwischen (10,15)-Zeiteinheiten vergangen sein können.
Abb. 126: Einschwingendes System Wie bereits bei dem Ampelbeispiel am Ende des Kapitels zu PROMELA und SPIN angedeutet, fordert man häufig nicht, dass eine Anforderung sofort erfüllt ist. Das System darf sich erst „einschwingen“ und muss dann eine Anforderung erfüllen. Eine Modellierungsmöglichkeit besteht darin, hierfür explizit eine Boolesche Variable einzusetzen, wie es bei der Spezifikation in Abb. 126 der Fall ist, die unmit-
147
3 Modelchecking mit Timed Automata und Uppaal telbar ohne Zeitverlust gesetzt wird. Die Spezifikation P hat die folgenden lokalen Variablen: int[0,30] i:=0; bool ok:=false;
Betrachtet man die generelle Anforderung, dass der Wert immer zwischen 10 und 20 liegen soll, beschrieben durch A (P.i>10 && P.i<20) so ist diese Anforderung anfänglich nicht erfüllt. Erst nachdem das System vollständig gestartet wurde, was durch das Setzen von ok auf true beschrieben ist, soll diese Anforderung gelten. Die dann beweisbare Anforderung lautet A P.ok imply (P.i>10 && P.i<20) In einer Variante kann man auch auf zusätzliche Boolesche Variablen verzichten, indem man statt P.ok nur bestimmte Zustände überprüft, die nach dem Einschwingen erreicht werden. Mit Timed Automata kann man auch klassische sequenzielle Systeme spezifizieren und verifizieren. Als Beispiel soll das Sortierverfahren aus Abschnitt 2.6 betrachtet werden, das auch mit PROMELA bearbeitet wurde. Zunächst muss man sich überlegen, wie z. B. Schleifen der Form while(b) umgesetzt werden. Dabei kann b einfach als Vorbedingung einer Kante genutzt werden. Nach der Ausführung des Schleifenrumpfes muss man wieder zum Ausgangszustand der Schleife zurück kehren. Dieser Ausgangszustand hat eine weitere Kante, die !b als Voraussetzung hat und für das Terminieren der Schleife steht. Abb. 127 zeigt die Umsetzung des Sortierverfahrens, dabei wurden alle algorithmischen Schritte in der Spezifikation dargestellt. Alternativ hätte man auch Funktionen nutzen können. Um ein Voranschreiten der Berechnungen zu garantieren, werden die Nichtendzustände mit „Urgent“ gekennzeichnet. Die Spezifikation hat folgende Variablen. const int N:=5; const int MAX:=3; int[0,MAX] array[N]; int[0,MAX] save[N]; int count:=0; int[0,N] count2:=0; int[0,N] j:=0; int[0,MAX] tmp; int[0,N] anzahl1; int[0,N] anzahl2;
148
3.5 Beispiele In den Zuständen Initialisieren und WertGesetzt werden Zahlen aus dem Bereich Null bis MAX geraten, danach erfolgt das Sortieren.
Initialisieren
rnd:int[0,MAX] count
array[count]:=rnd, save[count]:=array[count] WertGesetzt
count>=N count:=0 Sortieren
count>=N-1 count:=0
count:=count+1 jarray[j] count
Tauschen
tmp:=array[count], array[count]:=array[j], array[j]:=tmp, j:=j+1
j>=N-1 count:=count+1
j=N-1 count:=0
countarray[count+1] count2>=N && anzahl1!=anzahl2
GleicheElemente
count>MAX
count<=MAX anzahl1:=0, anzahl2:=0, count2:=0 count2
ok
count2>=N && anzahl1==anzahl2
nok
array[count2]==count anzahl2:=anzahl2+1, count2:=count2+1 array[count2]!=count count2:=count2+1
save[count2]==count anzahl1:=anzahl1+1
count:=count+1 save[count2]!=count
Abb. 127: Fehlerhafter Sortierer Die Überprüfung, ob erfolgreich sortiert wurde, findet am Ende der Spezifikation statt. Es wird zunächst geprüft, ob array sortiert ist, und danach, ob genau die Elemente des Ursprungsarrays im Ergebnis vorhanden sind. Wird ein Fehler erkannt, so wird zum Zustand nok übergegangen. Mit diesem Ansatz ist es möglich, Zusicherungen in Timed Automata einzubauen; werden fehlerhafte Werte erkannt, wird in einen Fehlerzustand gesprungen. In der Verifikation wird dann geprüft, dass diese Fehlerzustände nie erreicht werden. Zusätzlich fordert man, dass es
149
3 Modelchecking mit Timed Automata und Uppaal keinen Deadlock geben darf, so dass insgesamt die folgende Anforderung nachgewiesen werden muss: A !deadlock || Process.ok Die Verifikation scheitert, da sich ein kleiner Fehler eingeschlichen hat, durch den das letzte Element des Arrays nicht berücksichtigt wird. Lässt man sich die kürzeste Sequenz zu einem Fehler berechnen, sieht das Ergebnis am Ende wie folgt aus, man erkennt, dass der letzte Wert nicht einsortiert wurde. Process.array[0] = 0 Process.array[1] = 0 Process.array[2] = 0 Process.array[3] = 1 Process.array[4] = 0 Process.save[0] = 0 Process.save[1] = 0 Process.save[2] = 0 Process.save[3] = 1 Process.save[4] = 0 Process.count = 3 Process.j = 4 Process.tmp = 0
Statt mit einem Automaten zu arbeiten, könnte man auch mehrere Automaten nutzen, die die verschiedenen Teilaufgaben realisieren. Man kann dann mit Booleschen Wächtern dafür sorgen, dass der zweite Automat erst dann startet, wenn der erste Automat terminiert hat. Mit diesem Ansatz kann man Funktionsaufrufe nachbilden, so dass der zu untersuchende Algorithmus fast vollständig getrennt in einem Template steht. Der vorgestellte Ansatz kann auch für andere klassische sequenzielle Programme übernommen werden. Die klassischen Sprachkonstrukte wie if, while und do können einfach in Zustände mit Verzweigungen transformiert werden. Wenn sich die Bedingungen an ausgehenden Kanten gegenseitig ausschließen, wird ein deterministisches Verhalten erreicht. Die so erhaltenen Spezifikationen ähneln dann stark klassischen Programmablaufplänen. Da Timed Automata-Spezifikationen im XML-Format abgespeichert werden, ist es weiterhin relativ einfach, aus Teilen der Spezifikation automatisch Programmcode zu generieren. Der Weg von einer anderen Spezifikationssprache nach Timed Automata wird durch das XML-Format ebenfalls erleichtert. Abb. 128 zeigt die Korrektur des Sortierverfahrens, dabei wurden die Vorbedingungen der Schleifen im Zustand Tauschen korrigiert. Die Verifikation verläuft mit der modifizierten Spezifikation erfolgreich.
150
3.5 Beispiele rnd:int[0,MAX] count
array[count]:=rnd, save[count]:=array[count]
Initialisieren WertGesetzt count>=N count:=0 Sortieren count>=N-1 count:=0
count:=count+1 j<=N-1 && array[count]>array[j] count
Tauschen
tmp:=array[count], array[count]:=array[j], array[j]:=tmp, j:=j+1
j>N-1 count:=count+1
j<=N-1 && array[count]<=array[j] j:=j+1 Pruefen count>=N-1 count:=0
countarray[count+1] count2>=N && anzahl1!=anzahl2
GleicheElemente
count>MAX
count<=MAX anzahl1:=0, anzahl2:=0, count2:=0 count2
ok
count2>=N && anzahl1==anzahl2 count:=count+1
nok
array[count2]==count anzahl2:=anzahl2+1, count2:=count2+1 array[count2]!=count count2:=count2+1
save[count2]==count anzahl1:=anzahl1+1 save[count2]!=count
Abb. 128: Korrigierter Sortierer In der folgenden Fallstudie soll ein einfaches Telefonsystem mit einigen Zeitbedingungen modelliert werden. Dabei soll es N Teilnehmer geben, die miteinander durch ein Vermittlungssystem verbunden werden können. Kommunikation dial, x busy connect dialled
Bedeutung Teilnehmer wählt Nummer x Teilnehmer erhält die Information „gewählte Nummer besetzt“ Teilnehmer erhält die Information „gewählte Nummer erreicht“ Teilnehmer erhält die Information, dass er von einem anderen Teilnehmer angerufen wurde
151
3 Modelchecking mit Timed Automata und Uppaal Kommunikation disconnect disconnected
Bedeutung Teilnehmer beendet das Gespräch verbundener Teilnehmer hat Gespräch beendet
Abb. 129: Kommunikationen im Telefonsystem Zwischen den Teilnehmern und dem Vermittlungssystem werden die in Abb. 129 beschriebenen Nachrichten synchron ausgetauscht. Vereinfachend wird angenommen, dass ein erfolgreich angerufener Teilnehmer immer das Gespräch annimmt und dass der Telefonhörer unmittelbar mit busy, disconnect und disconnected aufgelegt wird.
Teilnehmer 1
Vermittlungssystem dial,2
Teilnehmer 2
dialled
connect disconnect disconnected
Teilnehmer 1
Vermittlungssystem dial,2
Teilnehmer 2
dialled
connect disconnect
disconnected
Teilnehmer 1
Vermittlungssystem dial,2 busy
Abb. 130: Mögliche Telefonatsabläufe Abb. 130 zeigt im Überblick drei Kommunikationsabläufe. Im oberen Teil sind der erfolgreiche Verbindungsaufbau und die dann folgende Beendigung des Anrufs durch den Anrufenden beschrieben. In der Mitte beendet der Anrufer das Ge-
152
3.5 Beispiele spräch. Im unteren Teil sieht man, wie ein erfolgloser Anruf verläuft, da der angerufene Teilnehmer mit einem anderen Telefonat beschäftigt ist. Die zentrale funktionale Anforderung ist, dass jeder Teilnehmer immer wieder die Möglichkeit hat, jeden anderen Teilnehmer zu erreichen. Weiterhin soll das System folgende Zeitrandbedingungen berücksichtigen: – Es werden minimal 4 und maximal 7 Zeiteinheiten benötigt, um festzustellen, dass ein Teilnehmer nicht erreichbar ist. – Ein Telefonat (zwischen connect und disconnect, bzw. dialled und disconnect) dauert minimal 20 und maximal 40 Zeiteinheiten. Handelt es sich z. B. um Gratisanrufmöglichkeiten, gibt es in den ersten 20 Einheiten Werbung und dann 20 Einheiten zur freien Verfügung. Es soll u. a. die Frage beantwortet werden, wie lange es maximal dauern kann, bis ein Telefonat bzw. ein Telefonatsversuch beendet wurde. Die folgende Beschreibung enthält das Ergebnis der Spezifikationsentwicklung, die typischerweise inkrementell entsteht. Zunächst fängt man mit zwei Teilnehmern an und ignoriert, dass der andere beschäftigt sein könnte. Später ergänzt man dann schrittweise weitere mögliche Alternativen. i:int[1,N-1] anrufen[ich]:=i start
anrufen[ich]:=0, dauer:=0 busy[ich]?
dauer:=0
anrufen[ich]!=0 dial[ich]! gewaehlt
connect[ich]? y:=0
dialled[ich]? y:=0, dauer:=0
verbunden y>=20 anrufen[ich]:=0, dauer:=0 disconnect[ich]!
y<=40 disconnected[ich]?
anrufen[ich]:=0, dauer:=0
Abb. 131: Spezifikation eines Teilnehmers Die endgültige Spezifikation nutzt die folgenden globalen Informationen: const int N := 5;
// für vier Teilnehmer, mit // Nummern 1,2,3,4 // Teilnehmer 0, bzw. Wert 0 für keine Verbindung chan dial[N];
153
3 Modelchecking mit Timed Automata und Uppaal chan connect[N]; chan busy[N]; chan disconnect[N]; chan disconnected[N]; chan dialled[N]; int[0,N] anrufen[N]; // Nummer, die Teilnehmer i anruft int[0,N] aktiv[N]; // mit wem redet i
Es wird vereinbart, dass ein Eintrag mit dem Wert Null für einen Teilnehmer bedeutet, dass dieser nicht aktiv ist, der Wert wird also als Dummy-Wert genutzt. Die Kommunikationskanäle dienen zur Umsetzung des beschriebenen Protokolls. Der Array anrufen wird zur Kommunikation genutzt, in der Variablen anrufen[i] teilt der Teilnehmer i dem Vermittlungssystem mit, welche Nummer er anrufen möchte. In der Variablen aktiv[i] wird festgehalten, mit wem der Teilnehmer i gerade verbunden ist. Warum diese Variable global ist, wird später deutlich. Abb. 131 enthält die mit int[1,N]