Institute for Program Structures and Data Organization (IPD), Chair Prof. Böhm

Vorverarbeitung von Kantengewichten für die Fehlerlokalisierung mit Graph-Mining-Techniken

  • chair:Data-Mining, Software-Fehlerlokalisierung
  • type:Studienarbeit
  • time:02.02.2010
  • tutor:

    Dipl. Inform. Christopher Oßner

  • person in charge:

    Hervè Dongmo Kana

Aufgabenstellung

Verschiedene Arbeiten beschäftigen sich mit der Lokalisierung von Fehlern in Software unter Verwendung von Data-Mining-Techniken. Dazu können die Aufrufgraphen des untersuchten Programmes generiert und analysiert werden. Aufrufgraphen können eine Programmausführung auf verschiedenen Ebenen modellieren. In dieser Studienarbeit werden Aufrufgraphen auf Methodenebene eingesetzt; Methoden werden als Knoten und Aufrufe zwischen den Methoden als Kanten dargestellt. Ein Reduktionsverfahren fasst  identische Methoden in einem Knoten zusammen. Ein Kantengewicht modelliert die Häufigkeit der Aufrufe. Unter anderem findet Frequent-Subgraph-Mining (FSM) Anwendung bei der Analyse der Graphen. Gängige Frequent-Subgraph-Mining-Algorithmen sind nicht in der Lage, mit numerischen Attributen an den Kanten umzugehen. Aus diesem Grund verfolgen bisherige Verfahren meist ein Ansatz, der die Gewichte erst ein einem Nachverarbeitungsschritt berücksichtigt.

Ziel dieser Arbeit ist es, durch Diskretisierung der Kantengewichte diese bereits während dem FSM zu nutzen. Durch die Diskretisierung entsteht eine Menge von kategorischen Attributen, die von dem FSM-Algorithmus als Kantenbeschriftung verarbeitet werden können. Daher stellt dieser Ansatz  eine interessante Alternative zur Nachverarbeitung der Gewichte dar. Durch die nun verfügbaren Kantenbeschriftungen ist ein Laufzeitvorteil zu erwarten, denn die Kantenbeschriftungen können vom Algorithmus zur Beschneidung des Suchraums (pruning) verwendet werden.

Die Ausgabe des Frequent-Subgraph-Mining-Algorithmus, eine Menge von Graph-Fragmenten, muss derart aufbereitet werden, dass sie hilfreich bei der Lokalisierung des Fehlers ist. Eine Rangliste der verdächtigen Methoden wäre wünschenswert.

Für die Bearbeitung der Studienarbeit sind die folgenden Schritte zu leisten: 

  1. Ein vorhandener Datensatz muss diskretisiert werden. Dazu ist der Datensatz in eine Darstellung zu überführen, die der Diskretisierer (CAIM) verarbeiten kann.
  2. Das Ergebnis der Diskretisierung muss mit den Graphen des Datensatzes kombiniert werden. Dies muss in einer Form geschehen, die als Eingabe für den Frequent-Subgraph-Mining-Algorithmus genutzt werden kann.
  3. Die Ausgabe des Frequent-Subgraph-Mining-Algorithmus zu einem Ergebnis umgeformt werden, das bei der Lokalisierung eines Fehlers hilfreich ist. Dabei sollen verschiedene Umformungen erarbeitet werden und diese gegeneinander verglichen werden.
  4. Die Ergebnisse sind in einer Evaluation mit bisherigen Ergebnissen zu vergleichen. Dazu ist zum einen die Präzision zu berücksichtigen, also ‚wie viel‘ Quelltext zu inspizieren ist, andererseits soll die Laufzeit des Verfahrens mit der Laufzeit bei einer Nachverarbeitung der Kantengewichte verglichen werden.