Laufzeitüberprüfung

Laufzeitüberprüfung ist ein Analyse des Computersystems und Ausführungsansatzes, das auf dem Extrahieren von Informationen aus einem laufenden System basiert und auf beobachtete Verhaltensweisen erfasst und möglicherweise bestimmte Eigenschaften verletzt.^[1] Einige ganz bestimmte Eigenschaften, wie z. Datarace und Sackgasse Freiheit ist in der Regel von allen Systemen zufrieden und kann algorithmisch am besten implementiert werden. Andere Eigenschaften können bequemer als erfasst werden als formale Spezifikationen. Die Spezifikationen zur Laufzeitüberprüfung werden typischerweise in Trace -Prädikat -Formalismen ausgedrückt, wie z. endliche Staatsmaschinen, Reguläre Ausdrücke, kontextfrei Muster, lineare zeitliche Logikusw. oder Erweiterungen davon. Dies ermöglicht einen weniger Ad-hoc-Ansatz als Normale Tests. Jeder Mechanismus zur Überwachung eines ausführenden Systems wird jedoch als Überprüfung der Laufzeit angesehen, einschließlich der Überprüfung gegen Testoakeln und Referenzimplementierungen. Wenn formale Anforderungenspezifikationen bereitgestellt werden, werden Monitore von ihnen synthetisiert und durch Instrumentierung innerhalb des Systems infundiert. Die Überprüfung der Laufzeit kann für viele Zwecke verwendet werden, wie z. formelle Überprüfung Techniken wie z. Modellprüfung und Theorem beweisen, indem nur ein oder einige Ausführungsspuren analysiert und direkt mit dem tatsächlichen System zusammengearbeitet werden, wodurch relativ gut sichtet und mehr Vertrauen in die Ergebnisse der Analyse verleiht Modellierung des Systems) auf Kosten einer weniger Abdeckung. Darüber hinaus kann die Überprüfung der Laufzeit durch seine reflektierenden Funktionen zu einem integralen Bestandteil des Zielsystems durchgeführt werden, wobei die Ausführung während der Bereitstellung überwacht und leitet.

Geschichte und Kontext

Die formelle oder informell festgelegte Eigenschaften gegen Ausführung von Systemen oder Programmen ist ein altes Thema (bemerkenswerte Beispiele sind Dynamisches Typing in Software oder fehlgeschlagene Geräte oder Watchdog-Timer in Hardware), deren genaue Wurzeln schwer zu identifizieren sind. Die Terminologie Laufzeitüberprüfung wurde offiziell als Name eines 2001 Workshops eingeführt^[2] Ziel, Probleme an der Grenze zwischen formaler Überprüfung und Test zu beheben. Bei großen Codebasen ist das manuelle Schreiben von Testfällen sehr zeitaufwändig. Darüber hinaus können nicht alle Fehler während der Entwicklung erkannt werden. Frühe Beiträge zur automatisierten Überprüfung wurden im NASA Ames Research Center von Klaus Havelund und geleistet Grigore Rosu Archivieren Sie hohe Sicherheitsstandards in Raumfahrzeugen, Rovers und Avionik -Technologie.^[3] Sie schlugen ein Tool vor, um die Spezifikationen in der zeitlichen Logik zu überprüfen und zu erkennen Rennbedingungen und Deadlocks in Java Programme durch Analyse einzelner Ausführungspfade.

Gegenwärtig werden häufig Fahrtechniken mit verschiedenen alternativen Namen wie Laufzeitüberwachung, Laufzeitüberprüfung, Laufzeitreflexion, Laufzeitanalyse angezeigt. Dynamische Analyse, Laufzeit/dynamische symbolische Analyse, Trace-Analyse, Protokolldateianalyse usw., alle beziehen sich auf Instanzen desselben hochrangigen Konzepts, das entweder auf verschiedene Bereiche oder von Wissenschaftlern aus verschiedenen Gemeinschaften angewendet wird. Die Überprüfung der Laufzeit hängt eng mit anderen gut etablierten Bereichen zusammen, wie z. B. Tests (insbesondere modellbasierte Tests), wenn sie vor dem Einsatz verwendet werden Fehlertolerante Systeme bei Verwendung während des Einsatzes.

Innerhalb des breiten Bereichs der Laufzeitüberprüfung kann man verschiedene Kategorien unterscheiden, wie z. B.:

• "Spezifikationslose" Überwachung, die auf einen festen Satz von meist gleichzeitbedingten Eigenschaften wie Atomizität abzielt. Die Pionierarbeit in diesem Bereich ist von Savage et al. Mit dem Radiergorithmus^[4]
• Überwachung in Bezug auf zeitliche Logikspezifikationen; Frühe Beiträge in diese Richtung wurden von Lee, Kannan und ihren Mitarbeitern geleistet.^[5][6] und Havelund und Rosu.^[7][8]

Grundlegende Ansätze

Überblick über den auf Monitor basierenden Überprüfungsprozess, wie von Falcone, Havelund und Reger in beschrieben Ein Tutorial zur Laufzeitüberprüfung.

Das breite Feld der Laufzeitüberprüfungsmethoden kann durch drei Dimensionen klassifiziert werden:^[9]

• Das System kann während der Ausführung selbst (online) oder nach der Ausführung, z. in Form eines Protokollanalyse (offline).
• Der Überprüfungscode ist in das System integriert (wie in Aspekt-orientiertes Programmieren) oder als externe Einheit bereitgestellt.
• Der Monitor kann Verstöße oder Validierung der gewünschten Spezifikation melden.

Dennoch bleibt der grundlegende Prozess bei der Laufzeitüberprüfung ähnlich:^[9]

1. Ein Monitor wird aus einer formellen Spezifikation erstellt. Dieser Vorgang kann normalerweise automatisch durchgeführt werden, wenn es gleichwertig ist Automaten für die Formeln der formelle Sprache Die Eigenschaft ist in. Um a zu transformieren regulären Ausdruck, a Finite-State-Maschine kann verwendet werden; ein Eigentum in lineare zeitliche Logik kann in a verwandelt werden BÜCHI AUTOMATON (siehe auch Lineare zeitliche Logik für Büchi Automaton).
2. Das System ist instrumentiert, um Ereignisse zum Ausführungszustand an den Monitor zu senden.
3. Das System wird ausgeführt und vom Monitor überprüft.
4. Der Monitor überprüft die empfangene Ereignisverfolgung und fördert ein Urteil, ob die Spezifikation erfüllt ist. Darüber hinaus sendet der Monitor Feedback an das System, um möglicherweise falsches Verhalten zu korrigieren. Bei der Verwendung der Offline -Überwachung kann das System der Ursache kein Feedback erhalten, da die Überprüfung zu einem späteren Zeitpunkt durchgeführt wird.

Beispiele

In den folgenden Beispielen werden einige einfache Eigenschaften erörtert, die bis zum Zeitpunkt dieses Schreibens (April 2011) von mehreren Laufzeitüberprüfungsgruppen berücksichtigt wurden. Um sie interessanter zu machen, verwendet jede nachstehende Eigenschaft einen anderen Formalismus, und alle sind parametrisch. Parametrische Eigenschaften sind Eigenschaften zu Spuren, die mit parametrischen Ereignissen gebildet werden, die Ereignisse sind, die Daten an Parameter binden. Hier hat eine parametrische Eigenschaft das Formular ${\ displayStyle \ forall Parameter: \ varphi}$, wo ${\ displayStyle \ varphi}$ ist eine Spezifikation in einem geeigneten Formalismus, der sich auf generische (nicht stantierte) parametrische Ereignisse bezieht. Die Intuition für solche parametrischen Eigenschaften ist, dass die Eigenschaft ausgedrückt durch ${\ displayStyle \ varphi}$ Muss für alle aufgetretenen Parameterinstanzen (durch parametrische Ereignisse) in der beobachteten Spur auftreten. Keine der folgenden Beispiele ist spezifisch für ein bestimmtes Laufzeitüberprüfungssystem, obwohl offensichtlich die Unterstützung für Parameter erforderlich ist. In den folgenden Beispielen wird die Java -Syntax angenommen, so dass "==" eine logische Gleichheit ist, während "=" Zuordnung ist. Einige Methoden (z. B.,, aktualisieren() In der unsicheren Auszeichnung sind Dummy -Methoden, die nicht Teil der Java -API sind, die zur Klarheit verwendet werden.

HasNext

Die HasNext -Eigenschaft

Die Java Iterator Schnittstelle erfordert, dass die HasNext () Methode aufgerufen werden und true vor dem zurückkehren nächste() Methode heißt. Wenn dies nicht der Fall ist, ist es sehr möglich, dass ein Benutzer "am Ende von" a iteriert wird Sammlung. Die Abbildung rechts zeigt eine endliche Zustandsmaschine, die einen möglichen Monitor für die Überprüfung und Durchsetzung dieser Eigenschaft mit Laufzeitüberprüfung definiert. Von dem Unbekannt Zustand ist es immer ein Fehler, das aufzurufen nächste() Methode, weil ein solcher Vorgang unsicher sein könnte. Wenn HasNext () wird gerufen und kehrt zurück Stimmt, es ist sicher anzurufen nächste(), so tritt der Monitor in die mehr Zustand. Wenn jedoch die HasNext () Methode Rückgabe FALSCHEs gibt keine Elemente mehr, und der Monitor tritt in die ein keiner Zustand. In dem mehr und keiner Staaten, die das rufen HasNext () Die Methode liefert keine neuen Informationen. Es ist sicher, das anzurufen nächste() Methode aus der mehr Zustand, aber es wird unbekannt, wenn mehr Elemente existieren Unbekannt Zustand. Schließlich rufen Sie das an nächste() Methode aus der keiner Der Zustand führt dazu Error Zustand. Was folgt, ist eine Darstellung dieser Eigenschaft unter Verwendung der parametrischen Vergangenheit lineare zeitliche Logik.

$oder }$

Diese Formel besagt, dass jeder Anruf an die nächste() Die Methode muss unmittelbar von einem Aufruf an vorangestellt werden HasNext () Methode, die wahr zurückgibt. Die Eigenschaft hier ist im Iterator parametrisch i. Konzeptionell bedeutet dies, dass für jeden möglichen Iterator in einem Testprogramm eine Kopie des Monitors vorhanden ist, obwohl die Laufzeitüberprüfungssysteme ihre parametrischen Monitore auf diese Weise nicht implementieren müssen. Der Monitor für diese Eigenschaft wird so eingestellt, dass sie einen Handler auslösen, wenn die Formel verletzt wird (gleichwertig, wenn die endliche Zustandsmaschine in die eintritt Error Zustand), der auftreten wird, wenn beide nächste() wird ohne zuerst anzurufen genannt HasNext (), oder wann HasNext () wird schon einmal gerufen nächste(), aber zurückgekehrt FALSCH.

Unsicher

Code, der gegen das unsichere Eigentum verstößt

Das Vektor Die Klasse in Java hat zwei Mittel zum Iterieren über seine Elemente. Man kann die Iterator -Schnittstelle verwenden, wie im vorherigen Beispiel zu sehen ist, oder man kann die verwenden Aufzählung Schnittstelle. Neben der Zugabe einer Entfernungsmethode für die Iterator -Schnittstelle besteht der Hauptunterschied darin, dass Iterator "fehlgeschlagen" ist, während die Aufzählung nicht der Fall ist. Dies bedeutet, dass, wenn man den Vektor (außer durch Verwendung der Iterator -Entfernungsmethode) modifiziert, wenn man über den Vektor mit einem Iterator iteriert, a, a ConcurrentModificationException ist geworfen. Bei Verwendung einer Aufzählung ist dies jedoch kein Fall, wie erwähnt. Dies kann zu nicht deterministischen Ergebnissen aus einem Programm führen, da der Vektor aus der Perspektive der Aufzählung in einem inkonsistenten Zustand gelassen wird. Für Legacy -Programme, die die Aufzählungsschnittstelle weiterhin verwenden, möchte man möglicherweise durchsetzen, dass Aufzählungen nicht verwendet werden, wenn ihr zugrunde liegender Vektor geändert wird. Das folgende parametrische reguläre Muster kann verwendet werden, um dieses Verhalten durchzusetzen:

∀ Vektor vAufzählung e: (e = v.elemente ()) (e.NextElement ())^* v.aktualisieren() e.NextElement ()

Dieses Muster ist sowohl in der Aufzählung als auch im Vektor parametrisch. Intuitiv und wie oben, müssen Systeme ihre parametrischen Monitore auf diese Weise nicht implementieren, kann man den parametrischen Monitor für diese Eigenschaft als das Erstellen und Verfolgen einer nichtparametrischen Monitorinstanz für jedes mögliche Vektorpaar und die Aufzählung vorstellen. Einige Ereignisse können mehrere Monitore gleichzeitig betreffen, wie z. v.update ()Das Laufzeitüberprüfungssystem muss sie (wieder konzeptionell) an alle interessierten Monitore senden. Hier wird die Eigenschaft so angegeben, dass sie das schlechte Verhalten des Programms angibt. Diese Eigenschaft muss also auf die Übereinstimmung des Musters überwacht werden. Die Figur rechts zeigt den Java -Code, der diesem Muster entspricht und so die Eigenschaft verletzt. Der Vektor V wird nach der Aufzählung von E aktualisiert, und E wird dann verwendet.

Tresorschloss

Die beiden vorherigen Beispiele zeigen endliche Zustandeigenschaften, aber Eigenschaften, die in der Laufzeitüberprüfung verwendet werden, können viel komplexer sein. Das Safelock -Eigentum setzt die Richtlinie durch, dass die Anzahl der Erwerben und Releases einer (Wiedereintritts-) Sperrklasse innerhalb eines bestimmten Methodenaufrufs übereinstimmt. Dies macht natürlich die Freisetzung von anderen Verschlüssen in anderen Methoden als diejenigen nicht aus, die sie erwerben, aber dies ist sehr möglicherweise ein wünschenswertes Ziel für das getestete System. Im Folgenden finden Sie eine Spezifikation dieser Eigenschaft unter Verwendung eines parametrischen kontextfreien Musters:

∀ Thread t, Sperren l: S→ ε | S Start(t) S Ende(t) | S l.erwerben(t) S l.Veröffentlichung(t)

Eine Spur mit zwei Verstößen gegen das Safelock -Eigentum.

Das Muster gibt ausgewogene Sequenzen von verschachteltem Beginn/Ende an und erfasst/Freisetzungspaare für jeden Thread und Sperre (Sperre ()${\ displayStyle \ Epsilon}$ ist die leere Sequenz). Hier beginnen und enden beziehen sich auf den Beginn und das Ende jeder Methode im Programm (mit Ausnahme der Aufrufe, sich selbst zu erwerben und selbst freizugeben). Sie sind im Thread parametrisch, da es notwendig ist, den Beginn und Ende der Methoden zu verknüpfen, wenn sie zum selben Thread gehören. Die Erwerbs- und Freigabeereignisse sind auch aus dem gleichen Grund im Thread parametrisch. Sie sind außerdem parametrisch im Schloss, weil wir die Veröffentlichungen einer Schloss nicht mit den Erwerben eines anderen in Verbindung bringen möchten. Im Extremwert ist es möglich, dass die Eigenschaft, d. H. Eine Kopie des kontextfreien Parsingmechanismus, für jede mögliche Kombination von Faden mit Sperre; Dies geschieht wiederum intuitiv, da die Laufzeitüberprüfungssysteme dieselbe Funktionalität unterschiedlich implementieren können. Zum Beispiel, wenn ein System Threads hat ${\ displayStyle t_ {1}}$, ${\ displayStyle t_ {2}}$, und ${\ displayStyle t_ {3}}$ mit Schlösser ${\ displayStyle l_ {1}}$ und ${\ displayStyle l_ {2}}$Dann ist es möglich, Immobilieninstanzen für die Paare zu verwalten <${\ displayStyle t_ {1}}$,${\ displayStyle l_ {1}}$>, <${\ displayStyle t_ {1}}$,${\ displayStyle l_ {2}}$>, <${\ displayStyle t_ {2}}$,${\ displayStyle l_ {1}}$>, <${\ displayStyle t_ {2}}$,${\ displayStyle l_ {2}}$>, <${\ displayStyle t_ {3}}$,${\ displayStyle l_ {1}}$> und <${\ displayStyle t_ {3}}$,${\ displayStyle l_ {2}}$>. Diese Eigenschaft sollte überwacht werden, um das Muster zu entsprechen, da das Muster das richtige Verhalten angegeben hat. Die Figur rechts zeigt eine Spur, die zwei Verstöße gegen dieses Eigentum erzeugt. Die Schritte in der Abbildung stellen den Beginn einer Methode dar, während die Schritte nach oben das Ende sind. Die grauen Pfeile in der Abbildung zeigen die Übereinstimmung zwischen gegebenen Erwerben und Releases desselben Schlosses. Der Einfachheit halber zeigt die Spur nur einen Faden und ein Schloss.

Forschungsherausforderungen und Anwendungen

Die meisten Forschungsergebnisse der Laufzeitverifizierung befassen sich mit einem oder mehreren der unten aufgeführten Themen.

Reduzierung der Laufzeitaufwand

Die Beobachtung eines ausführenden Systems verursacht in der Regel einen Überkopf von Laufzeit (Hardware -Monitore können eine Ausnahme machen). Es ist wichtig, den Overhead von Laufzeitüberprüfungs -Tools so weit wie möglich zu reduzieren, insbesondere wenn die generierten Monitore mit dem System eingesetzt werden. Zu den Laufzeit -Überkopf -Reduktechniken gehören:

• Verbesserte Instrumentierung. Das Extrahieren von Ereignissen aus dem ausführenden System und das Senden von Monitoren kann bei naivsteuer eine große Laufzeitaufwand erzeugen. Eine gute Systeminstrumentierung ist für jedes Laufzeit -Überprüfungs -Tool von entscheidender Bedeutung, es sei denn, das Tool zielt explizit vorhandene Ausführungsprotokolle ab. Es gibt viele Instrumentenansätze in der aktuellen Verwendung, jeweils ihre Vor- und Nachteile, die von benutzerdefinierten oder manuellen Instrumenten bis hin zu spezialisierten Bibliotheken reichen, bis hin zur Zusammenstellung von aspektorientierten Sprachen bis hin zur Erweiterung der virtuellen Maschine, um auf Hardwareunterstützung aufzubauen.
• Kombination mit statischer Analyse. Eine häufige Kombination von statischen und dynamischen Analysen, insbesondere bei Compilern, besteht darin, alle Anforderungen zu überwachen, die nicht statisch abgegeben werden können. Ein doppelter und letztendlich gleichwertiger Ansatz wird in der Laufzeitverifizierung zur Norm, nämlich zur Verwendung Statische Analyse Reduzierung der ansonsten erschöpfenden Überwachung. Eine statische Analyse kann sowohl auf der Eigenschaft zum Überwachung als auch auf dem zu überwachenden System durchgeführt werden. Eine statische Analyse der Eigenschaft, um zu überwachen, kann zeigen, dass bestimmte Ereignisse nicht erforderlich sind, um zu überwachen, dass die Schaffung bestimmter Monitore verzögert werden kann und dass bestimmte vorhandene Monitore niemals ausgelöst werden und daher Müll gesammelt werden können. Eine statische Analyse des Systems zur Überwachung kann Code erkennen, der niemals die Monitore beeinflussen kann. Zum Beispiel bei der Überwachung der HasNext Eigenschaft oben benötigt man keine Instrumententeile des Code, bei denen jeder Anruf I.Next () ist sofort auf einem Pfad durch einen Anruf vorausgegangen i.hasnext () Das kehrt zurück Stimmt (Sichtbar auf dem Kontroll-Flow-Diagramm).
• Effiziente Monitor -Generierung und -management. Bei der Überwachung der parametrischen Eigenschaften wie den in den obigen Beispielen muss das Überwachungssystem den Status der überwachten Eigenschaft in Bezug auf jede Parameterinstanz verfolgen. Die Anzahl solcher Fälle ist theoretisch unbegrenzt und ist in der Praxis tendenziell enorm. Eine wichtige Forschungsherausforderung besteht darin, wie beobachtete Ereignisse effizient auf genau jene Fälle gesendet werden können. Eine verwandte Herausforderung besteht darin Sie werden unnötig. Schließlich verallgemeinern parametrische Überwachungsalgorithmen typischerweise ähnliche Algorithmen zur Generierung nichtparametrischer Monitore. Die Qualität der erzeugten nichtparametrischen Monitore bestimmt daher die Qualität der resultierenden parametrischen Monitore. Im Gegensatz zu anderen Überprüfungsansätzen (z. B. Modellprüfung) ist die Anzahl der Zustände oder die Größe des generierten Monitors bei der Überprüfung der Laufzeit weniger wichtig. In der Tat können einige Monitore unendlich viele Staaten haben, wie die für die Tresorschloss Eigentum oben, obwohl zu einem bestimmten Zeitpunkt nur eine begrenzte Anzahl von Staaten aufgetreten ist. Wichtig ist, wie effizient der Monitor von einem Zustand zu seinem nächsten Zustand überträgt, wenn er ein Ereignis vom ausführenden System erhält.

Eigenschaften angeben

Einer der wichtigsten praktischen Hindernisse aller formalen Ansätze ist, dass ihre Benutzer nur ungern berechtigt sind oder nicht lernen und nicht lernen möchten, wie sie Spezifikationen lesen oder schreiben. In einigen Fällen sind die Spezifikationen implizit, wie z. B. für Deadlocks und Datenraces, in den meisten Fällen müssen sie jedoch hergestellt werden. Eine zusätzliche Unannehmlichkeit, insbesondere im Zusammenhang mit der Laufzeitüberprüfung, besteht darin, dass viele vorhandene Spezifikationssprachen nicht ausdrucksstark genug sind, um die beabsichtigten Eigenschaften zu erfassen.

• Bessere Formalismen. Eine erhebliche Menge an Arbeit in der Laufzeitverifizierungsgemeinschaft wurde in die Gestaltung von Spezifikationsformalismen eingesetzt, die den gewünschten Anwendungsdomänen für die Laufzeitverifizierung besser entsprechen als die konventionellen Spezifikationsformalismen. Einige davon bestehen aus geringfügigen oder keinen syntaktischen Veränderungen der konventionellen Formalismen, jedoch nur aus Änderungen ihrer Semantik (z. .). Andere erweitern vorhandene Formalismen mit Merkmalen, die für die Überprüfung der Laufzeit zugänglich sind, aber möglicherweise nicht einfach für andere Überprüfungsansätze bestehen, z. B. das Hinzufügen von Parametern, wie in den obigen Beispielen zu sehen. Schließlich gibt es Spezifikationsformalismen, die speziell für die Überprüfung der Laufzeit konzipiert wurden, um ihr Bestes für diese Domäne zu erreichen und sich wenig um andere Anwendungsdomänen zu kümmern. Das Entwerfen von universell besseren oder domänenspezifisch besseren Spezifikationsformalismen für die Überprüfung der Laufzeit ist und wird weiterhin eine der größten Forschungsherausforderungen sein.
• Quantitative Eigenschaften. Im Vergleich zu anderen Überprüfungsansätzen kann die Laufzeitüberprüfung auf konkreten Werten von Systemzustandsvariablen arbeiten, was es ermöglicht, statistische Informationen über die Programmausführung zu sammeln und diese Informationen zu verwenden, um komplexe quantitative Eigenschaften zu bewerten. Ausdrucksvollere Eigenschaftensprachen, die es uns ermöglichen, diese Fähigkeit vollständig zu nutzen, sind erforderlich.
• Bessere Schnittstellen. Das Lesen und Schreiben von Immobilienspezifikationen ist für Nicht-Experten nicht einfach. Sogar Experten starren oft Minuten auf relativ kleine zeitliche Logikformeln (insbesondere auf "bis" bis zum "Betreiber). Ein wichtiger Forschungsbereich besteht darin, leistungsstarke Benutzeroberflächen für verschiedene Spezifikationsformalismen zu entwickeln, mit denen Benutzer Eigenschaften leichter verstehen, schreiben und sogar visualisieren können.
• Bergbauspezifikationen. Unabhängig davon, welches Tool -Support verfügbar ist, um Benutzern bei der Erstellung von Spezifikationen zu helfen, werden sie sich fast immer freuen, überhaupt keine Spezifikationen zu schreiben, insbesondere wenn sie trivial sind. Glücklicherweise gibt es viele Programme da draußen, die angeblich korrekte Aktionen/Ereignisse verwenden, über die man Eigenschaften haben möchte. Wenn dies der Fall ist, ist es denkbar, dass man diese korrekten Programme nutzen möchte, indem man die gewünschten Eigenschaften automatisch von ihnen lernt. Auch wenn erwartet wird, dass die Gesamtqualität der automatisch abgebauten Spezifikationen niedriger ist als die von manuell erzeugten Spezifikationen, können sie als Startpunkt für letztere oder als Grundlage für automatische Tools zur Laufzeitüberprüfung dienen Die Spezifikation verwandelt sich zu falsch positiven oder negativen, die während des Tests häufig akzeptabel sind).

Ausführungsmodelle und Vorhersageanalyse

Die Fähigkeit eines Laufzeiturteils zur Erkennung von Fehlern hängt streng von seiner Fähigkeit ab, Ausführungsspuren zu analysieren. Wenn die Monitore mit dem System eingesetzt werden, ist die Instrumentierung normalerweise minimal und die Ausführungsspuren sind so einfach wie möglich, um die Laufzeit über dem Kopf zu halten. Wenn die Laufzeitüberprüfung zum Testen verwendet wird, kann man umfassendere Instrumente leisten, die Ereignisse mit wichtigen Systeminformationen erweitern, die von den Monitoren zum Konstruktion und damit raffinierteren Modellen des ausführenden Systems verwendet werden können. Zum Beispiel erhöhen Sie Ereignisse mit Vektoruhr Informationen und mit Daten- und Steuerflussinformationen ermöglichen es den Monitoren, a zu konstruieren Kausalmodell des laufenden Systems, in dem die beobachtete Ausführung nur eine mögliche Instanz war. Jede andere Permutation von Ereignissen, die mit dem Modell übereinstimmen, ist eine praktikable Ausführung des Systems, die unter einem anderen Fadenscharfen auftreten kann. Das Erkennen von Verstößen gegen Eigenschaften in solchen abgeleiteten Hinrichtungen (durch Überwachung) macht den Monitor vorhersagen Fehler, die in der beobachteten Ausführung nicht auftraten, aber in einer anderen Ausführung desselben Systems auftreten können. Eine wichtige Forschungsherausforderung besteht darin, Modelle aus Ausführungsspuren zu extrahieren, die so viele andere Ausführungsspuren wie möglich umfassen.

Verhaltensänderung

Im Gegensatz zu Tests oder erschöpfenden Überprüfung hält die Überprüfung der Laufzeit das Versprechen, dass das System sich von erkannten Verstößen, durch Rekonfiguration, Mikroempfänger oder durch feinere Interventionsmechanismen, die manchmal als Tuning oder Lenkung bezeichnet werden, wiederhergestellt werden können. Die Implementierung dieser Techniken im strengen Rahmen der Laufzeitüberprüfung führt zu zusätzlichen Herausforderungen.

• Spezifikation von Handlungen. Man muss die Änderung angeben, die in einer abstrakt genügenden Weise durchgeführt werden soll, für die der Benutzer nicht irrelevante Implementierungsdetails kennt. Wenn eine solche Änderung stattfinden kann, muss außerdem angegeben werden, um die Integrität des Systems aufrechtzuerhalten.
• Argumentation über Interventionseffekte. Es ist wichtig zu wissen, dass eine Intervention die Situation verbessert oder die Situation zumindest nicht verschlimmert.
• Aktionsschnittstellen. Ähnlich wie bei der Überwachung müssen wir das System ermöglichen, Aktionsaufrufe zu erhalten. Die Mechanismen des Aufrufs sind notwendigerweise von den Implementierungsdetails des Systems abhängig. Auf der Spezifikationsebene müssen wir dem Benutzer jedoch eine deklarative Möglichkeit geben, das System Feedback zu geben, indem wir angeben, welche Aktionen unter welchen Bedingungen angewendet werden sollten.

Verwandte Arbeit

Aspekt-orientiertes Programmieren

Forscher in der Laufzeitüberprüfung erkannten das Potenzial für die Verwendung Aspekt-orientiertes Programmieren als Technik zur modularen Definition von Programminstrumenten. Aspekt-orientierte Programmierung (AOP) fördert im Allgemeinen die Modularisierung von Querschnittsbedenken. Die Laufzeitüberprüfung ist natürlich ein solches Problem und kann daher von bestimmten Eigenschaften von AOP profitieren. Aspektorientierte Monitordefinitionen sind weitgehend deklarativ und sind daher tendenziell einfacher zu argumentieren als in der Instrumentierung, die durch a ausgedrückt wird Programmumwandlung geschrieben in einer imperativen Programmiersprache. Darüber hinaus können statische Analysen die Überwachung von Aspekten leichter als über andere Formen der Programminstrumentierung begründen, da alle Instrumente in einem einzigen Aspekt enthalten sind. Viele aktuelle Tools zur Laufzeitüberprüfung werden daher in Form von Spezifikations Compilern integriert, die eine ausdrucksstarke Spezifikation auf hoher Ebene als Eingabe annehmen und als Ausgangscode in einigen Aspekt-orientierten Programmiersprache (wie z. Aspektj).

Kombination mit formaler Überprüfung

Die Laufzeitüberprüfung kann, wenn sie in Kombination mit nachweislich korrektem Wiederherstellungscode verwendet werden, eine unschätzbare Infrastruktur für die Programmüberprüfung liefern, die die Komplexität des letzteren erheblich senken kann. Beispielsweise ist die formelle Überprüfung des Heap-Sort-Algorithmus eine große Herausforderung. Eine weniger herausfordernde Technik zur Überprüfung der Überwachung der zu sortierenden Ausgabe (ein linearer Komplexitätsmonitor) und, falls nicht sortiert, sortieren Sie sie mit einer leicht überprüfbaren Prozedur, beispielsweise die Insertion -Sortierung. Das resultierende Sortierungsprogramm ist jetzt leichter überprüfbar, das einzige, was von Heap-Sort erforderlich ist, ist, dass es nicht die ursprünglichen Elemente zerstört, die als Multiset angesehen werden, was viel einfacher zu beweisen ist. Wenn man sich aus der anderen Richtung ansieht, kann man die formelle Überprüfung verwenden, um den Overhead der Laufzeitüberprüfung zu verringern, wie oben bereits erwähnt, um eine statische Analyse anstelle einer formalen Überprüfung zu erhalten. In der Tat kann man mit einer vollständig verifizierten Laufzeit beginnen, aber wahrscheinlich langsames Programm. Dann kann man eine formale Überprüfung (oder statische Analyse) verwenden, um Monitore abzuleiten, wie ein Compiler statische Analyse verwendet, um Laufzeitüberprüfungen von Typ -Korrektheit abzuleiten oder Speichersicherheit.

Zunehmende Abdeckung

Im Vergleich zu den traditionelleren Überprüfungsansätzen ist ein unmittelbarer Nachteil der Laufzeitüberprüfung die reduzierte Abdeckung. Dies ist nicht problematisch, wenn die Laufzeitmonitore mit dem System bereitgestellt werden (zusammen mit einem geeigneten Wiederherstellungscode, der ausgeführt wird, wenn die Eigenschaft verletzt wird), kann jedoch die Effektivität der Laufzeitüberprüfung einschränken, wenn er zum Finden von Fehlern in Systemen verwendet wird. Zu den Techniken zur Erhöhung der Abdeckung der Laufzeitüberprüfung für Fehlererkennungszwecke gehören:

• Eingabeerzeugung. Es ist bekannt, dass die Erzeugung eines guten Satzes von Eingängen (Programmeingangsvariablenwerte, Systemaufrufwerte, Thread -Zeitpläne usw.) die Wirksamkeit des Tests enorm erhöhen kann. Dies gilt auch für die Laufzeitüberprüfung, die für die Fehlererkennung verwendet wird. Zusätzlich zur Verwendung des Programmcodes zum Steuern des Eingangsgenerierungsprozesse gewünschte Verhaltensweisen. Diese Verwendung der Laufzeitüberprüfung macht sie eng mit modellbasierten Tests zusammen, obwohl die Spezifikationen zur Laufzeitüberprüfung in der Regel allgemeiner Zweck sind und nicht unbedingt aus Testgründen hergestellt werden. Betrachten Sie zum Beispiel, dass man den allgemeinen Purpose testen möchte Unsicher Eigenschaft oben. Anstatt nur den oben genannten Monitor zu erzeugen, um die Systemausführung passiv zu beobachten, kann man einen intelligenteren Monitor erzeugen, der den Thread einfriert, der versucht, den zweiten zu generieren E.NextElement () Ereignis (kurz bevor es es generiert), lassen Sie die anderen Threads in der Hoffnung ausführen, dass einer von ihnen eine generieren kann v.update () Ereignis, in diesem Fall wurde ein Fehler gefunden.
• Dynamische symbolische Ausführung. In symbolischen Ausführung werden Programme symbolisch ausgeführt und überwacht, dh ohne konkrete Eingaben. Eine symbolische Ausführung des Systems kann einen großen Satz von Betoneingängen abdecken. Off-the-Shelf-Einschränkungen der Lösung oder Befriedigungsprüfungstechniken werden häufig verwendet, um symbolische Ausführungen voranzutreiben oder ihren Speicherplatz systematisch zu untersuchen. Wenn die zugrunde liegenden Befriedigungsprüfer einen Auswahlpunkt nicht bewältigen können, kann ein Betoneingang erstellt werden, um diesen Punkt zu übergeben. Diese Kombination von konzRete und SymbOlic Die Ausführung wird auch als konkolische Ausführung bezeichnet.

Siehe auch

• Dynamische Programmanalyse
• Profilerstellung (Computerprogrammierung)
• Laufzeitfehlererkennung
• Selbstschutz für Laufzeitanwendung (RASPEL)

Verweise