Modellprüfung

Aufzug Die Steuerungssoftware kann modellüberprüft werden, um beide Sicherheitseigenschaften zu überprüfen, wie es "Die Kabine bewegt sich nie mit offener Tür",^[1] und Lebendigkeitseigenschaften wie "Wann immer das n^th Boden Anruf Die Taste wird gedrückt, die Kabine hält schließlich am n^th Boden und öffnen Sie die Tür ".

Im Informatik, Modellprüfung oder Eigenschaftsprüfung ist eine Methode zur Überprüfung, ob a Finite-State-Modell eines Systems trifft eine gegebene Spezifikation (auch bekannt als Richtigkeit). Dies ist typischerweise mit Hardware- oder Softwaresysteme, wo die Spezifikation Lebendigkeitsanforderungen enthält (z. B. Vermeidung von Lebensunterhalt) sowie Sicherheitsanforderungen (z. B. Vermeidung von Zuständen, die a repräsentieren System Absturz).

Um ein solches Problem zu lösen algorithmischsowohl das Modell des Systems als auch seine Spezifikation werden in einer präzisen mathematischen Sprache formuliert. Zu diesem Zweck wird das Problem als Aufgabe in formuliert Logik, nämlich um zu überprüfen, ob a Struktur erfüllt eine bestimmte logische Formel. Dieses allgemeine Konzept gilt für viele Arten von Logik und viele Arten von Strukturen. Ein einfaches Problem zur Modellprüfung besteht darin, zu überprüfen, ob eine Formel in der Aussagelogik ist durch eine bestimmte Struktur zufrieden.

Überblick

Immobilienprüfung wird verwendet für Überprüfung Wenn zwei Beschreibungen nicht gleichwertig sind. Während RaffinesseDie Spezifikation wird durch Details ergänzt, die sind nicht notwendig in der höheren Spezifikation. Es ist nicht erforderlich, die neu eingeführten Eigenschaften gegen die ursprüngliche Spezifikation zu überprüfen, da dies nicht möglich ist. Daher wird die strenge bidirektionale Äquivalenzprüfung an eine Einweg-Immobilienprüfung gelockert. Die Implementierung oder das Design wird als Modell des Systems angesehen, während die Spezifikationen Eigenschaften sind, die das Modell erfüllen muss.^[2]

Eine wichtige Klasse von Modellprüfmethoden wurde entwickelt, um Modelle von zu überprüfen Hardware- und Software Entwürfe, bei denen die Spezifikation von a angegeben ist zeitliche Logik Formel. Pionierarbeit in der zeitlichen Logikspezifikation wurde von durchgeführt Amir Pnueli, der 1996 den Turing Award für "wegweisende Arbeiten zur Einführung der zeitlichen Logik in die Computerwissenschaft erhielt".^[3] Die Modellprüfung begann mit der Pionierarbeit von E. M. Clarke, E. A. Emerson,^[4][5][6] von J. P. Queille und J. Sifakis.^[7] Clarke, Emerson und Sifakis teilten die 2007 mit Turing Award für ihre wegweisende Arbeiten zur Gründung und Entwicklung des Modells der Modellprüfung.^[8][9]

Die Modellprüfung wird am häufigsten auf Hardwaredesigns angewendet. Für Software aufgrund der Unentschlossenheit (siehe Computerbarkeitstheorie) Der Ansatz kann nicht vollständig algorithmisch sein, für alle Systeme gelten und immer eine Antwort geben. Im allgemeinen Fall kann es eine bestimmte Eigenschaft nicht nachweisen oder widerlegen. Im eingebettete Systeme Hardware ist möglich, eine gelieferte Spezifikation zu validieren, d. H. Mit Hilfe von UML -Aktivitätsdiagramme^[10] oder Kontrolle interpretiert Petri Nets.^[11]

Die Struktur wird normalerweise als Quellcodebeschreibung in einer Industrie angegeben Hardware -Beschreibung Sprache oder eine Spezialsprache. Ein solches Programm entspricht a endliche Zustandsmaschine (FSM), d.h. gerichteter Graph bestehend aus Knoten (oder Eckpunkte) und Kanten. Jeder Knoten ist eine Reihe von Atomausstellungen zugeordnet, wobei typischerweise festgestellt wird, welche Speicherelemente eins sind. Das Knoten Repräsentiert Zustände eines Systems, die Kanten repräsentieren mögliche Übergänge, die den Zustand verändern können, während die Atomaussagen die grundlegenden Eigenschaften darstellen, die an einem Punkt der Ausführung gelten.

Formal kann das Problem wie folgt angegeben werden: Bei einer gewünschten Eigenschaft, ausgedrückt als zeitliche Logikformel ${\ displayStyle p}$und eine Struktur ${\ displayStyle m}$ mit Anfangszustand ${\ displayStyle S}$, entscheide, ob ${\ displayStyle M, S \ Modelle P}$. Wenn ${\ displayStyle m}$ ist endlich, da es in der Hardware ist, das Modellprüfung reduziert sich auf a grafische Suche.

Symbolische Modellprüfung

Anstatt die erreichbaren Zustände einzeln aufzuzählen, kann der Zustandsraum manchmal effizienter durchquert werden, indem eine große Anzahl von Zuständen in einem einzigen Schritt berücksichtigt wird. Wenn eine solche staatliche Space-Traversal auf Darstellungen einer Reihe von Zuständen und Übergangsbeziehungen als logische Formeln basiert, basiert Binäre Entscheidungsdiagramme (BDD) oder andere verwandte Datenstrukturen, die Modellprüfmethode ist symbolisch.

Historisch gesehen verwendeten die ersten symbolischen Methoden BDDs. Nach dem Erfolg von Aussagenerfriedigung bei der Lösung der Planung Problem in künstliche Intelligenz (sehen Satplan) 1996 wurde der gleiche Ansatz auf Modellprüfung verallgemeinert lineare zeitliche Logik (LTL): Das Planungsproblem entspricht der Modellprüfung für Sicherheitseigenschaften. Diese Methode wird als begrenzte Modellprüfung bezeichnet.^[12] Der Erfolg von Boolesche Erfüllbarkeitslöser Bei begrenztem Modell die Überprüfung führte zur weit verbreiteten Verwendung von Erfrischungslöser bei der symbolischen Modellprüfung.^[13]

Beispiel

Ein Beispiel für eine solche Systemanforderung:Zwischen dem Zeitpunkt, an dem ein Aufzug auf einem Boden gerufen wird, und zu dem Zeitpunkt, als er seine Türen auf diesem Boden öffnet, kann der Aufzug höchstens zweimal zu diesem Boden gelangen. Die Autoren von "Mustern in der Eigenschaftspezifikation zur Finite-Zustand-Überprüfung" übersetzen diese Anforderung in die folgende LTL-Formel:^[14]

$oder (atfloor \ land \ lnot offen) ~ {\ mathcal {u}} \\ & (open \ lor ((\ lnot atfloor \ land \ lnot open) ~ {\ mathcal {u} \\ & (open \ lor (lor (open \ lor ( (atfloor \ land \ lnot offen) ~ {\ mathcal {u}} \\ & (öffnen \ lor (\ lnot atfloor ~ {\ mathcal {u} ~ ~ open)))))))) \ end {ausgerichtet}}}$

Hier, ${\ displayStyle \ box}$ sollte als "immer" gelesen werden, ${\ displayStyle \ Diamond}$ als "schließlich", ${\ displaystyle {\ mathcal {u}}}$ als "bis" und die anderen Symbole sind Standard -logische Symbole, ${\ displayStyle \ lor}$ für "oder", ${\ displayStyle \ Land}$ für "und" und ${\ displayStyle \ lnot}$ für "nicht".

Techniken

Modellprüfungswerkzeuge sehen sich einer kombinatorischen Ausblendung des Zustandsraums aus, der allgemein als die bekannt ist StatusxplosionsproblemDas muss angesprochen werden, um die meisten realen Probleme zu lösen. Es gibt mehrere Ansätze, um dieses Problem zu bekämpfen.

1. Symbolische Algorithmen vermeiden immer explizit, dass das Diagramm für die endlichen Zustandsmaschinen (FSM) ausdrücklich erstellt wird. Stattdessen repräsentieren sie die Grafik implizit eine Formel in quantifizierter Aussagenlogik. Die Verwendung von Binärentscheidungsdiagrammen (BDDs) wurde durch die Arbeit von Ken McMillan populär gemacht^[15] und die Entwicklung von Open-Source-BDD-Manipulationsbibliotheken wie Cudd^[16] und Kumpel.^[17]
2. Begrenzte Modell-Überprüfungsalgorithmen löschen die FSM für eine feste Anzahl von Schritten, ${\ displayStyle K}$, und prüfen Sie, ob ein Immobilienverstoß in eintreten kann ${\ displayStyle K}$ oder weniger Schritte. Dies beinhaltet typischerweise die Codierung des eingeschränkten Modells als Instanz von Sa. Der Vorgang kann mit immer größeren Werten von wiederholt werden ${\ displayStyle K}$ Bis alle möglichen Verstöße ausgeschlossen wurden (vgl. Iterative Vertiefung der Tiefe-First-Suche).
3. Abstraktion Versuche, Eigenschaften eines Systems zu beweisen, indem es zuerst vereinfacht wird. Das vereinfachte System erfüllt normalerweise nicht genau die gleichen Eigenschaften wie das ursprüngliche, so dass ein Verfeinerungsprozess erforderlich sein kann. Im Allgemeinen erfordert man die Abstraktion, um es zu sein Klang (Die an der Abstraktion bewiesenen Eigenschaften sind für das ursprüngliche System zutreffend); Manchmal ist die Abstraktion jedoch nicht Komplett (Nicht alle wahren Eigenschaften des ursprünglichen Systems treffen die Abstraktion). Ein Beispiel für Abstraktion besteht darin, die Werte nicht-Boolen-Variablen zu ignorieren und nur boolesche Variablen und den Kontrollfluss des Programms zu betrachten. Eine solche Abstraktion, obwohl sie grob erscheinen mag, kann tatsächlich ausreichen, um z. Eigentum von gegenseitiger Ausschluss.
4. Counterexample-gesteuerte Abstraktionsverfeinerung (CEGAR) beginnt mit einer groben (d. H. Unvollständigen) Abstraktion zu überprüfen und iterativ zu verfeinern. Wenn ein Verstoß (d. H. Gegenbeispiel) wird gefunden, das Tool analysiert es auf Machbarkeit (d. H. Ist die Verletzung echt oder das Ergebnis einer unvollständigen Abstraktion?). Wenn der Verstoß machbar ist, wird er dem Benutzer gemeldet. Wenn dies nicht der Fall ist, wird der Nachweis der Uneinigkeit verwendet, um die Abstraktion zu verfeinern, und die Überprüfung beginnt wieder.^[18]

Modellprüfwerkzeuge wurden ursprünglich entwickelt, um die logische Korrektheit von zu begründen Diskreter Zustand Systeme, wurden aber seitdem für Echtzeit- und begrenzte Formen von erweitert Hybridsysteme.

Logik erster Ordnung

Die Modellprüfung wird auch im Bereich von untersucht Computerkomplexitätstheorie. Insbesondere a logisch erster Ordnung Die Formel ist ohne fixiert freie Variablen und die folgende Entscheidungsproblem gilt als:

Eine endliche DeutungZum Beispiel einer beschrieben als a relationale Datenbank, entscheiden Sie, ob die Interpretation ein Modell der Formel ist.

Dieses Problem ist in der Schaltungsklasse AC⁰. es ist flehbar Wenn die Eingabestruktur einige Einschränkungen auferlegt: zum Beispiel, so dass dies erforderlich ist Baumbreite begrenzt durch eine Konstante (die allgemeiner die Traktabilität der Modellprüfung für die Überprüfung des Modells impliziert Monadische Logik zweiter Ordnung), die Begrenzung der Grad jedes Domänenelements und allgemeinere Bedingungen wie z. begrenzte Expansion, lokal begrenzte Expansion und nirgends dichte Strukturen.^[19] Diese Ergebnisse wurden auf die Aufgabe von ausgedehnt Aufzählung Alle Lösungen für eine Formel erster Ordnung mit freien Variablen.

Werkzeug

Hier finden Sie eine Liste der wichtigsten Tools für Modellprüfungen:

• Legierung (Legierungsanalysator)
• SPRENGEN (Berkeley Lazy Abstraktionssoftware -Überprüfungstool)
• CADP (Konstruktion und Analyse verteilter Prozesse) Eine Toolbox für die Gestaltung von Kommunikationsprotokollen und verteilten Systemen
• CPACHECKER: Ein Open-Source-Software-Modellprüfer für C-Programme basiert auf dem CPA-Framework
• ECLAIR: Eine Plattform für die automatische Analyse, Überprüfung, Testen und Transformation von C- und C ++ - Programmen
• FDR2: Ein Modellprüfer zur Überprüfung von Echtzeitsystemen, die modelliert und spezifiziert als angegeben CSP Prozesse
• ISP Code -Ebene -Überprüfer für MPI Programme
• Java Pathfinder: Ein Open-Source-Modellprüfer für Java-Programme
• Libdmc: Ein Framework für verteilte Modellprüfung
• mcrl2 Toolset, Boost Software Lizenz, Bezogen auf ACP
• Nusmv: Ein neuer symbolischer Modellprüfer
• KLOPFEN: Ein erweiterter Simulator, Modellprüfer und Verfeinerungsprüfer für gleichzeitige und Echtzeitsysteme
• Prisma: Eine probabilistische symbolische Modellprüfung
• Roméo: Eine integrierte Tool-Umgebung zur Modellierung, Simulation und Überprüfung von Echtzeitsystemen, die als parametrische, Zeit- und Stoppuhr-Petri Nets modelliert sind
• DREHEN: Ein allgemeines Instrument zur Überprüfung der Richtigkeit verteilter Softwaremodelle streng und größtenteils automatisiert
• Tapas: Ein Werkzeug zur Analyse der Prozessalgebra
• Tapaal: Eine integrierte Tool-Umgebung zur Modellierung, Validierung und Überprüfung von zeitgesteuerten Arc-Arc Petri Nets
• TLA+ Modellprüfung durch Leslie Lamport
• Uppaal: Eine integrierte Tool-Umgebung zur Modellierung, Validierung und Überprüfung von Echtzeitsystemen, die als Netzwerke zeitgesteuerter Automata modelliert sind
• Zing^[20] - Experimentelles Werkzeug von Microsoft Validierung von staatlichen Softwaremodellen auf verschiedenen Ebenen: Protokollbeschreibungen auf hoher Ebene, Arbeitsablaufspezifikationen, Webdienste, Gerätetreiber und Protokolle im Kern des Betriebssystems. Zing wird derzeit für die Entwicklung von Treibern für Windows verwendet.

Siehe auch

Verweise

Weitere Lektüre

• Modellprüfung, Doron A. Peled, Patrizio Pelliccione, Paola Spoletini, Wiley Encyclopedia of Information and Engineering, 2009.
• Modellprüfung, Edmund M. Clarke, Orna Grumberg und Doron A. Peled, MIT Press, 1999, ISBN0-262-03270-8.
• System- und Softwareverifizierung: Modellprüfungstechniken und -Teools, B. Berard, M. Bidoit, A. Finkel, F. Laroussinie, A. Petit, L. Petrucci, P. Schnoebelen, ISBN3-540-41523-8
• Logik in der Informatik: Modellierung und Argumentation über Systeme, Michael Huth und Mark Ryan, Cambridge University Press, 2004.
• Der Spinmodell Checker: Primer- und Referenzhandbuch, Gerard J. Holzmann, Addison-Wesley, ISBN0-321-22862-6.
• Julian Bradfield und Colin Stirling, Modal Logics und Mu-Calculi, Inf.ed.ac.uk
• Spezifikationsmuster Ksu.edu
• Eigenschaftsmusterzuordnungen für RAFMC Inria.fr
• Radu Mateescu und Mihaela seighireanu Effiziente Modellprüfung auf dem Fliege für regelmäßige alternationsfreie Mu-Kalkulus, Seite 6, Wissenschaft der Computerprogrammierung 46 (3): 255–281, 2003
• Müller-Olm, M., Schmidt, D.A. und Steffen, B. Modellprüfung: Eine Tutorial -Einführung. Proc. 6. statische Analyse -Symposium, G. File und A. Cortesi, Hrsg., Springer LNCS 1694, 1999, S. 330–354.
• Baier, C., Katoen, J.: Prinzipien der Modellprüfung. 2008.
• E. M. Clarke: "Die Geburt der Modellprüfung" doi:10.1007/978-3-540-69850-0_1
• E. Allen Emerson (2008). "Der Beginn der Modellprüfung: Eine persönliche Perspektive". In Orna Grumberg; Helmut Veith (Hrsg.). 25 Jahre Modellprüfung - Geschichte, Erfolge, Perspektiven. Lncs. Vol. 5000. Heidelberg: Springer. S. 27–45. doi:10.1007/978-3-540-69850-0_2. ISBN 978-3-540-69849-4. (Dies ist auch eine sehr gute Einführung und Übersicht über die Modellprüfung)