Was genau ist symbolische Modellprüfung?

8

Ich weiß, dass die symbolische Modellprüfung eine Zustandsraumdurchquerung ist, die auf Darstellungen von Zustandssätzen und Übergangsbeziehungen als Formeln wie in CTL unter Verwendung von Modellen wie dem Kripke-Modell basiert. Ich kenne die Theorie. Aber ich finde es schwierig, die tatsächliche Anwendung zu verstehen. Wo genau wird es verwendet? Was genau macht es und wie funktioniert es?

Kann jemand mit einem realen Beispiel erklären und Theorie mit Praxis in Beziehung setzen?

formal-methods model-checking software-verification Xpleria
quelle
1
Das scheint mir zu breit. Das "Was macht es?" Teil mag vernünftig sein (oder nicht), aber "wo wird es verwendet?" ist a) eine ganz andere Frage und b) wahrscheinlich zu weit gefasst.
Raphael
Darauf aufbauend kann jedoch ein Beispiel genommen und erklärt werden. Das ist nicht zu breit.
Xpleria
2
Warum sind Sie mit der Beschreibung der symbolischen Modellprüfung im Standardlehrbuch nicht zufrieden, z. B. "Prinzipien der Modellprüfung" von Christel Baier und Joost-Pieter Katoen? Über welche Teile bist du verwirrt?
Hengxin
Sie sprechen darüber, wie es gemacht werden soll, aber nicht darüber, wie genau es gemacht wird. Ich versuche, die Theorie und die praktische Umsetzung in Beziehung zu setzen. Ich bin noch neu in diesem Bereich und brauche ein Beispiel.
Xpleria
1
Möglicherweise befinden Sie sich dann auf der falschen Website. Computer Wissenschaft ist über die Konzepte ( „wie es gemacht werden sollte“), werden Sie haben die Praktizierenden zu fragen , über den Teil „ wie es gemacht wird “.
Raphael

Antworten:

4

Die symbolische Modellprüfung ist die Modellprüfung, die für symbolische Zustände funktioniert. Das heißt, sie codieren die Zustände in symbolische Darstellungen, typischerweise geordnete binäre Entscheidungsdiagramme (OBDDs).

Die Frage ist, was sie tun und wie sie arbeiten.

Sie haben zuerst Ihren Quellcode für eine Anwendung. Anschließend wandeln Sie Ihren Quellcode in ein Zustandsübergangsdiagramm wie eine Kripke-Struktur um. Die Zustände sind mit atomaren Sätzen gefüllt, die beschreiben, was in diesem bestimmten Zustand wahr ist. Bei der Überprüfung symbolischer Modelle werden die atomaren Sätze als OBDDs codiert, um Platz zu sparen und die Leistung zu verbessern.

Die Modellprüfung beginnt dann bei einem Anfangszustand und untersucht die Zustände, um nach Fehlern im Zustandsübergangsdiagramm zu suchen. Wenn ein Fehler gefunden wird, wird häufig ein Testfall generiert, der den Fehler demonstriert. Es verwendet die symbolischen OBDDs, um den Zustandsraum etwas optimal zu navigieren. Ich wünschte, ich könnte dort mehr erklären, aber immer noch lernen.

Aber das ist es im Grunde. Sie haben ein Programm in ein formales Modell konvertiert (Zustandsübergangsdiagramm) und verwenden dann symbolische Optimierungen, um im Zustandsraum nach Fehlern zu suchen (indem Sie es mit einer LTL / CTL-Spezifikation vergleichen). Und wenn ein Fehler gefunden wird, bietet Ihnen der Model Checker einige Hilfsmittel, um ihn zu dokumentieren und zu beheben.

Lance Pollard
quelle
5

Die symbolische Modellprüfung kann sehr nützlich sein, um die Richtigkeit von Kommunikations- und Sicherheitsprotokollen zu überprüfen. Zum Beispiel:

  • Ein symbolisches Modell einer OAUTH2-Implementierung könnte dabei helfen, nach unbeabsichtigten Konsequenzen zu suchen, wenn ein Gegner geheime Authentifizierungstoken oder verwandte Umstandsdaten erhält, die ihm helfen könnten, gegen den Prozess zu verstoßen.
  • Ein symbolisches Modell eines kryptografischen Protokolls wie ein TLS-Handshake könnte dazu beitragen, sicherzustellen, dass das kryptografische Design keine unbeabsichtigten Konsequenzen hat.

Dies funktioniert, indem eine symbolische Beschreibung aller primitiven Funktionen und Protokollalgorithmen geschrieben wird und dann ein symbolischer Modellprüfer wie ProVerif den Zustandsraum durchläuft und versucht, Zustandskombinationen zu erkennen, die zu ungünstigen Ergebnissen führen. Im Fall von ProVerif werden symbolische Modelle unter Verwendung des angewandten Pi-Kalküls als Modellierungssprache beschrieben. Dies ermöglicht die Beschreibung von Protokollen in einer funktionalen, ML-ähnlichen Syntax.

Kaepora
quelle