Aufgabenstellung

Graph-Mining-Techniken wurden bereits erfolgreich zur Lokalisierung von Software-Fehlern eingesetzt. Der Schwerpunkt der bisherigen Forschung lag allerdings in der Untersuchung nicht-paralleler Programme. Dabei wurden bereits einige Verfahren entwickelt, die über das reine (Struktur-)Mining von Call-Graphen hinausgehen: In [1] wurde eine Reduktionsform von Call-Graphen verwendet, die die Aufrufhäufigkeit von Methoden als Kantengewichte repräsentiert. Hierdurch können insbesondere häufigkeitsverändernde Fehler lokalisiert werden. Eine andere Art der Kantenannotation verfolgt [3]: hier werden die Kanten des Call-Graphen um eine Repräsentation von Parametern und Rückgabewerten der aufgerufenen Methoden angereichert. Dadurch können auch Fehler gefunden werden, die den Datenfluss betreffen. Bei einer ersten Übertragung von Call-Graph-Mining zur Fehlerlokalisierung in mehrfädigen Programmen in [2] stieß man auf das Problem, dass Änderungen in der Aufrufhäufigkeit von Methoden nun aufgrund von Änderungen im Thread-Scheduling auftreten können. Häufigkeitsänderungen dieser Art sind allerdings - unter dem Aspekt Fehlerlokalisierung betrachtet - meist nicht relevant. Um die Call-Graph-Repräsentation invariant bezüglich Scheduling-induzierten Änderungen der Aufrufhäufigkeiten zu machen, wurde in [2] auf eine „Totalreduktion“ als Repräsentationsform des Graphen zurückgegriffen. Erkauft wird dies jedoch durch einen Nachteil: der totalreduzierte Graph enthält nahezu keine Strukturinformation mehr, in der sich Ausführungen unterscheiden. Ziel dieser Diplomarbeit ist es, eine Repräsentationsform für Call-Graphen zu finden, die wie in [2] invariant gegenüber Scheduling-induzierten Änderungen der Aufrufhäufigkeiten ist, die aber trotzdem unterschiedliche Ausführungen auf strukturell unterschiedliche Graphen abbildet. Dies geschieht mit dem Ziel, Graph-Mining-Algorithmen auch im mehrfädigen Fall genügend Information zur Diskriminanz zwischen korrekten und inkorrekten Ausführungen zu liefern. Weiterhin soll die in [3] entwickelte Technik (Datenfluss-Anreicherung des Call-Graphen) in geeigneter Form auf den mehrfädigen Fall übertragen werden. Im Rahmen dieser Arbeit soll im Einzelnen Folgendes geleistet werden:

1. Es sollen eine oder mehrere Reduktionsformen des Call-Graphen mit den oben beschriebenen wünschenswerten Eigenschaften gefunden und umgesetzt werden. Dazu sollen die Threads eines Programms anhand ihrer Funktionalität in Klassen eingeteilt werden. Threads mit gleicher Funktionalität werden als gleichartig betrachtet und derselben Klasse zugeordnet (Beispiel: eine Menge von funktionsgleichenWorker-Threads). Anschließend werden die durch die Thread-Einteilung entstehenden Subgraphen des Call-Graphen isoliert reduziert. Um die Klasseneinteilung automatisch vornehmen zu können, ist eine Instrumentierung nötig. Dazu muss unter Umständen eine Ergänzung zu den bestehenden Instrumentierungsverfahren entwickelt werden.

2. Durch eine Anreicherung des Call-Graphen um Datenflussinformationen (ähnlich wie in [3]) soll die Menge der lokalisierbaren Fehler ausgeweitet werden. Zusätzlich könnten andere Informationen (z.B. über gesetzte Locks) relevant für multithreading-spezifische Fehler sein. Es sollen Techniken gefunden und umgesetzt werden, solche Informationen in den Graph zu integrieren.

3. Die Evaluation wird anhand der bereits in [2] verwendeten Benchmark-Suite durchgeführt. Hierbei wird insbesondere untersucht, ob die zusätzlich entwickelten Methoden die Lokalisierungsergebnisse in den Fällen verbessern, bei denen [2] schlecht abschneidet.

Literatur
[1] Frank Eichinger, Klemens Böhm und Matthias Huber. Mining Edge-Weighted Call Graphs to Localise Software Bugs. Proceedings of the 8th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). 2008.
[2] Frank Eichinger, Victor Pankratius, Philipp W. L. Große und Klemens Böhm. Localizing Defects in Multithreaded Programs by Mining Dynamic Call Graphs. Proceedings of the 5th Testing: Academic and Industrial Conference - Practice and Research Techniques (TAIC PART). 2010.
[3] Frank Eichinger, Klaus Krogmann, Roland Klug und Klemens Böhm. Software-Defect Localisation by Mining Dataflow-Enabled Call Graphs. Proceedings of the 10th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). 2010.