Analyzing Provenance Graphs for Programming Errors

Kurzfassung

In dieser Arbeit wird die Erkennung von Programmierfehlern mit Hilfe von Provenance Graphen untersucht, indem der Datenfluss und die Funktionsaufrufe während der Ausführung aufgezeichnet werden. Zwei spezifische Fehlertypen stehen dabei im Mittelpunkt: Der erste bezieht sich auf ungenutzte Daten. Dieser kann leicht durch die Überprüfung der Kanten der Knoten vom Typ Entity im Graphen erkannt werden. Der zweite Fehlertyp sind falsche Sequenzen von Funktionsaufrufen. Diese können im Graphen des Programms identifiziert werden, indem die Subgraphen, welche Aufrufsequenzen darstellen, mit dem Graphen der korrekten Sequenz mit Hilfe der Graph Edit Distance (GED) verglichen werden. In der Graphentheorie wird dieses Problem als inexact subgraph matching bezeichnet. Es wird gezeigt, dass die Berechnung des GED auf knotengefärbten, gerichteten Graphen NP-schwer ist. Aufgrund der Komplexität der Berechnung der GED wird die Größe des ursprünglichen Graphen des Programms reduziert. Indem der Datenfluss zwischen den Funktionen extrahiert wird, wobei die notwendigen Informationen zur Erkennung von falschen Aufrufsequenzen beibehalten werden, kann die Komplexität der Graphen reduziert werden. Dadurch kann die Berechnung in einer akzeptablen Zeit durchgeführt werden. Außerdem wird ein heuristischer Ansatz zum Auffinden dieses Fehlers beschrieben. Zunächst wird nach einem kleinen Teil der korrekten Sequenz im Graphen des Programms gesucht. Dann werden aus den identifizierten Positionen die Teilgraphen extrahiert, die die vollständigen Aufrufsequenzen repräsentieren. Anschließend wird die GED zwischen den Teilgraphen und dem Graphen, der die korrekte Sequenz kodiert, berechnet und das Ergebnis als korrekter, inkorrekter oder nicht verwandter Aufruf klassifiziert. Um das Potential der Fehlererkennung mittels Provenance Graphen zu testen, wird ein Proof-of-Concept-Tool bereitgestellt und an einem generierten Datensatz getestet. Dabei konnten fehlerhafte Aufrufsequenzen von Funktionen erfolgreich erkannt werden. Die Ergebnisse zeigen das Potential von Provenance Graphen für die automatisierte Fehlererkennung, für ein einfacheres und schnelleres Debugging.