In der Informatik ist abstrakte Interpretation eine Theorie der gesunden Annäherung der Semantik von Computerprogrammen, die auf monotonischen Funktionen über bestellte Sätze, besonders Gitter gestützt sind. Es kann als eine teilweise Ausführung eines Computerprogramms angesehen werden, das Information über seine Semantik (z.B Kontrollfluss, Datenfluss) gewinnt, ohne alle Berechnungen durchzuführen.

Seine konkrete Hauptanwendung ist formelle statische Analyse, die automatische Förderung der Information über die möglichen Ausführungen von Computerprogrammen; solche Analysen haben zwei Hauptgebrauch:

• innerhalb von Bearbeitern, um Programme zu analysieren, um zu entscheiden, ob bestimmte Optimierungen oder Transformationen anwendbar sind;
• für das Beseitigen oder sogar das Zertifikat von Programmen gegen Klassen von Programmfehlern.

Abstrakte Interpretation wurde von Patrick Cousot und Radhia Cousot formalisiert.

Intuition

Dieser Artikel illustriert jetzt, was abstrakte Interpretation, durch das Verwenden wirklich, Nichtcomputerwissenschaft, Beispiele bedeutet.

Denken Sie die Leute in einem Konferenzraum. Um zu beweisen, dass einige Menschen nicht anwesend gewesen sind, ist eine konkrete Methode, eine Liste der Namen und einiger Bezeichner nachzuschlagen, die zu ihnen wie eine Sozialversicherungsnummer in den Vereinigten Staaten aller Teilnehmer einzigartig sind. Da zwei verschiedene Menschen dieselbe Zahl nicht haben können, ist es möglich, die Anwesenheit eines Teilnehmers einfach durch das Aufblicken seiner oder ihrer Zahl in der Liste zu beweisen oder zu widerlegen.

Jedoch ist es möglich, dass nur die Namen von Anwesenden eingeschrieben wurden. Wenn der Name einer Person in der Liste nicht gefunden wird, können wir sicher beschließen, dass diese Person nicht anwesend gewesen ist; aber wenn es ist, können wir nicht bestimmt ohne Rückfragen, wegen der Möglichkeit von Homonymen (zum Beispiel zwei Menschen genannt John Smith) aufhören. Bemerken Sie, dass diese ungenaue Information noch zu den meisten Zwecken entsprechend sein wird, weil Homonyme in der Praxis selten sind. Jedoch, in der ganzen Strenge, können wir nicht sicher sagen, dass jemand im Zimmer anwesend gewesen ist; alles, was wir sagen können, ist, dass er oder sie vielleicht hier war. Wenn die Person, die wir nachschlagen, ein Verbrecher ist, werden wir eine Warnung ausgeben; aber es gibt natürlich die Möglichkeit, einen Fehlalarm auszugeben. Ähnliche Phänomene werden in der Analyse von Programmen vorkommen.

Wenn wir uns nur für etwas spezifische Information, sagen wir, interessieren, "war dort eine Person volljähriger n im Zimmer", eine Liste aller Namen und Daten von Geburten behaltend, ist unnötig. Wir können sicher, und ohne Verlust der Präzision schränken uns zum Halten einer Liste der Alter der Teilnehmer ein. Wenn das bereits zu viel ist, um zu behandeln, könnten wir nur die minimale M und maximale M Alter behalten. Wenn die Frage über ein Alter ist, ausschließlich sinken als M oder ausschließlich höher als M, dann können wir sicher antworten, dass kein solcher Teilnehmer anwesend gewesen ist. Sonst können wir nur im Stande sein zu sagen, dass wir nicht wissen.

Im Fall von der Computerwissenschaft ist konkrete, genaue Information im Allgemeinen innerhalb der endlichen Zeit und des Gedächtnisses nicht berechenbar (sieh den Lehrsatz von Rice und das stockende Problem). Abstraktion wird verwendet, um vage Antworten auf Fragen (zum Beispiel zu berücksichtigen, "vielleicht" auf ja/no auf Frage antwortend); das vereinfacht die Probleme, die sie zugänglich automatischen Lösungen machen. Eine entscheidende Voraussetzung soll genug Zweideutigkeit hinzufügen, um Probleme lenksam zu machen, während er noch genug Präzision behält, für auf die wichtigen Fragen zu antworten (solche, die "können der Programmabsturz?").

Abstrakte Interpretation von Computerprogrammen

In Anbetracht einer Programmierung oder Spezifizierungssprache besteht abstrakte Interpretation daraus, mehrere durch Beziehungen der Abstraktion verbundene Semantik zu geben. Eine Semantik ist eine mathematische Charakterisierung eines möglichen Verhaltens des Programms. Die genauste Semantik, sehr nah die wirkliche Ausführung des Programms beschreibend, wird die konkrete Semantik genannt. Zum Beispiel kann die konkrete Semantik einer befehlenden Programmiersprache zu jedem Programm den Satz von Ausführungsspuren vereinigen, die es - eine Ausführungsspur erzeugen kann, die eine Folge von möglichen Konsekutivstaaten der Ausführung des Programms ist; ein Staat besteht normalerweise aus dem Wert des Programm-Schalters und der Speicherpositionen (globals, Stapel und Haufen). Abstraktere Semantik wird dann abgeleitet; zum Beispiel kann man nur den Satz von erreichbaren Staaten in den Ausführungen denken (der sich auf das Betrachten der letzten Staaten in begrenzten Spuren beläuft).

Die Absicht der statischen Analyse ist, eine berechenbare semantische Interpretation an einem Punkt abzuleiten. Zum Beispiel kann man beschließen, den Staat eines Programms zu vertreten, das Variablen der ganzen Zahl manipuliert, indem man die Ist-Werte der Variablen vergisst und nur ihre Zeichen (+,  oder 0) behält. Für einige elementare Operationen, wie Multiplikation, verliert solch eine Abstraktion keine Präzision: Um das Zeichen eines Produktes zu bekommen, ist es genügend, das Zeichen des operands zu wissen. Für einige andere Operationen kann die Abstraktion Präzision verlieren: Zum Beispiel ist es unmöglich, das Zeichen einer Summe zu wissen, deren operands beziehungsweise positiv und negativ sind.

Manchmal ist ein Verlust der Präzision notwendig, um die Semantik entscheidbar zu machen (sieh den Lehrsatz von Rice, stockendes Problem). Im Allgemeinen gibt es einen Kompromiss, der zwischen der Präzision der Analyse und seiner Entscheidbarkeit (Berechenbarkeit) oder Lenkbarkeit (Kompliziertheit) zu machen ist.

In der Praxis werden die Abstraktionen, die definiert werden sowohl zu den Programm-Eigenschaften geschneidert, die man wünscht, als auch zum Satz von Zielprogrammen zu analysieren. Die erste in großem Umfang automatisierte Analyse von Computerprogrammen mit der abstrakten Interpretation kann einem Unfall zugeschrieben werden, der auf die Zerstörung des ersten Flugs der Ariane 5 Rakete 1996 hinausgelaufen ist.

Formalisierung

Lassen Sie L ein bestellter Satz, genannt einen konkreten Satz sein und L&prime zu lassen; seien Sie ein anderer bestellter Satz, genannt einen abstrakten Satz. Diese zwei Sätze sind mit einander durch das Definieren von Gesamtfunktionen verbunden, die Elemente von einem bis den anderen kartografisch darstellen.

Eine Funktion α wird eine Abstraktionsfunktion genannt, wenn sie ein Element x im Beton-Satz-L zu einem Element α (x) im abstrakten Satz L&prime kartografisch darstellt;. d. h. Element α (x) in L′ ist die Abstraktion von x in L.

Eine Funktion γ wird eine Concretization-Funktion genannt, wenn sie ein Element x&prime kartografisch darstellt; im abstrakten Satz L′ zu einem Element γ (x&prime) im Beton setzt L. D. h. Element γ (x&prime) in L ist ein concretization x′ in

Lassen Sie L, L, L′ und L′ werde Sätze befohlen. Die konkrete Semantik f ist eine monotonische Funktion von L bis L. Eine Funktion f′ von L′ zu L′ wird gesagt, eine gültige Abstraktion von f wenn für alle x&prime zu sein; in L′ (f  γ) (x&prime)  (γ  f&prime) (x&prime).

Programm-Semantik wird allgemein mit befestigten Punkten in Gegenwart von Schleifen oder rekursiven Verfahren beschrieben. Lassen Sie uns annehmen, dass L ein ganzes Gitter ist und lassen Sie f eine monotonische Funktion von L in L sein. Dann, irgendwelcher x′ solch dass f′ (x&prime)  x′ ist eine Abstraktion von kleinstem festem Punkt von f, der gemäß dem Lehrsatz von Knaster-Tarski besteht.

Die Schwierigkeit ist jetzt, solch einen x&prime zu erhalten;. wenn L′ ist der begrenzten Höhe, oder prüft mindestens die "steigende Kettenbedingung" nach (alle steigenden Folgen sind schließlich stationär), dann solch ein x′ kann als die stationäre Grenze der steigenden Folge x&prime erhalten werden; definiert durch die Induktion wie folgt: x′= (kleinstes Element L&prime) und x′=f′ (x&prime).

In anderen Fällen ist es noch möglich, solch einen x&prime zu erhalten; durch einen sich erweiternden Maschinenbediener : Für den ganzen x und y x  sollte y größer oder gleich sein sowohl als x als auch als y, und für jede Folge y′ die Folge, die durch x′= und x′=x&prime definiert ist;  y′ ist schließlich stationär. Wir können dann y′=f&prime nehmen; (x&prime).

In einigen Fällen ist es möglich, das Abstraktionsverwenden Verbindungen von Galois zu definieren (α, γ), wo α von L bis L&prime ist; und γ ist von L′ zu L. Das nimmt die Existenz von besten Abstraktionen an, die nicht notwendigerweise der Fall ist. Zum Beispiel, wenn wir Sätze von Paaren (x, y) reeller Zahlen abstrahieren, indem wir konvexe Polyeder einschließen, gibt es keine optimale Abstraktion zur Scheibe, die durch x+y  1 definiert ist.

Beispiele von abstrakten Gebieten

Man kann jeder Variable x verfügbar an einem gegebenen Programm-Punkt ein Zwischenraum [L, H] zuteilen. Ein Staat, der den Wert v (x) zur Variable x zuteilt, wird ein concretization dieser Zwischenräume sein, wenn für den ganzen x, dann ist v (x) in [L, H]. Von den Zwischenräumen [L, H] und [L, H] für Variablen x und y, kann man Zwischenräume für x+y ([L+L, H+H]) und für xy ([LH, HL]) leicht erhalten; bemerken Sie, dass das genaue Abstraktionen, seit dem Satz von möglichen Ergebnissen für, sagen wir, x+y sind, ist genau der Zwischenraum ([L+L, H+H]). Kompliziertere Formeln können für die Multiplikation, Abteilung abgeleitet werden, usw. so genannten Zwischenraum arithmetics nachgebend.

Lassen Sie uns jetzt das folgende sehr einfache Programm denken:

y = x;

z = x - y;

</pre>

Mit angemessenen arithmetischen Typen sollte das Ergebnis dafür Null sein. Aber wenn wir Zwischenraum arithmetics tun, von in [0, 1] anfangend, gelangt man [1, +1] hinein. Während jede der Operationen genommen individuell genau abstrahiert wurde, ist ihre Zusammensetzung nicht.

Das Problem ist offensichtlich: Wir sind die Gleichheitsbeziehung zwischen nicht nachgegangen und; wirklich zieht dieses Gebiet von Zwischenräumen keine Beziehungen zwischen Variablen in Betracht, und ist so ein Nichtverwandtschaftsgebiet. Nichtverwandtschaftsgebiete neigen dazu, schnell und einfach zu sein, durchzuführen, aber ungenau.

Einige Beispiele von abstrakten numerischen Verwandtschaftsgebieten sind:

• Kongruenz-Beziehungen auf ganzen Zahlen
• konvexe Polyeder - mit einigen hohen rechenbetonten Kosten
• "Achtecke"
• Unterschied-gebundener matrices
• geradlinige Gleichheiten

und Kombinationen davon.

Wenn man ein abstraktes Gebiet wählt, muss man normalerweise ein Gleichgewicht zwischen Halten feinkörniger Beziehungen und hohen rechenbetonten Kosten schlagen.

Werkzeuge

• Abstrakte Neuschreiben-Maschine
• Polyraum
• CodeSonar
• Coverity verhindern
• Klocwork Scharfsinnigkeit
• Paraweicher Jtest
• Paraweiche C/C ++ prüfen
• Der Goanna der roten Eidechse

Siehe auch

• Standardinterpretation
• Modell, das überprüft
• Symbolische Simulation
• Symbolische Ausführung

Links

• Eine Webseite auf der Abstrakten Interpretation, die von Patrick Cousot aufrechterhalten ist
• Das Papier von Roberto Bagnara, das sich zeigt, wie es möglich ist, eine abstrakte Interpretation durchzuführen, hat statischen Analysator für eine C ähnliche Programmiersprache gestützt

Vortrag bemerkt

• Abstrakte Interpretation. Patrick Cousot. MIT.
• Der Vortrag von David Schmidt bemerkt auf der abstrakten Interpretation
• Der Vortrag von Michael Schwarzbach bemerkt auf der statischen Analyse
• Der Vortrag von Agostino Cortesi bemerkt auf der Programm-Analyse und Überprüfung (in Italienisch)