Partitionierung von Fehlerlokalisierungsproblemen mit Algorithmen aus der ganzzahligen linearen Optimierung

Softwaretests sind ein bewährtes Mittel zur Feststellung von Fehlern in Programmen. Das Fehlschlagen von Tests einer Testsuite liefert Hinweise darauf, dass in den ausgeführten Methoden eventuell Fehler vorhanden sind, bietet jedoch in der Regel keinen Anhaltspunkt für die tatsächliche Anzahl der vorhandenen Fehler, geschweige denn deren Ursprungsort. Das Vorhandensein mehrerer Fehler in realen Programmen ist jedoch nicht unwahrscheinlich -- im Gegenteil. Daher werden Strategien benötigt, um die durch die Ausführung einer Testsuite erhaltenen Informationen in einer Art und Weise auswerten zu können, die das Auffinden möglichst viele Fehler erlaubt. Von Vorteil ist zudem, wenn diese Strategien eine parallele Verarbeitung der Informationen erlauben, so dass mehrere Programmierer gleichzeitig auf Fehlersuche gehen können. Auf diese Weise können die verfügbaren Ressourcen effizient eingesetzt und die Suchdauer minimiert werden. Ein Ansatz zur Parallelisierung der Fehlersuche basiert darauf, dass die Ausführungsstruktur einer Testsuite auch als Matrix dargestellt werden kann. Da im Bereich der ganzzahligen linearen Optimierung bereits viele Algorithmen zur Partitionierung von Matrizen entwickelt wurden, liegt die Idee nah, einige von ihnen für die Ableitung von parallel durchführbaren Fehlerlokalisierungsprozessen zu nutzen. Diese Arbeit untersucht daher verschiedene Ansätze aus diesem Forschungsgebiet hinsichtlich ihrer Eignung zur Parallelisierung und Beschleunigung der Fehlersuche bei Anwesenheit multipler Fehler. Einer der untersuchten Algorithmen wird zudem speziell auf das Fehlersuchproblem hin angepasst, um so noch effektiver zur Parallelisierung der Suche beitragen zu können. Die Ergebnisse der Arbeit weisen darauf hin, dass die untersuchten Ansätze zu einer signifikanten Erhöhung der Anzahl der gefundenen Fehler sowie zu einer erheblichen Beschleunigung der Fehlersuche führen können. Zusätzlich dazu werden verschiedene Probleme erläutert, die in Evaluationen im Bereich der Fehlerlokalisierung im Allgemeinen und in dieser Arbeit im Speziellen auftreten können und welche Gegenmaßnahmen getroffen werden sollten, um ihre Auswirkungen zu minimieren.