Partitionierung von Fehlerlokalisierungsproblemen mit Algorithmen aus der ganzzahligen linearen Optimierung

Frenkel, Marcus

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.

Software tests have proven to be a reliable tool for detecting faults in a computer program. A failing test of a test suite hints at a possible fault in the executed methods, but does neither give an indication of the actual number of faults, let alone their origin. Alas, the existence of multiple faults in a program is quite likely. It is therefore required to find strategies for interpreting the information given by a test suite execution in a way which allows for finding as much faults as possible. Furthermore, being able to process these information in parallel enables multiple programmers to search for faults at the same time, which minimizes processing times. One approach to parallelize the search for faults is based on the fact that the execution structure of a test suite can also be represented as a matrix. A vast amount of algorithms for partitioning a given matrix have been established in the field of integer linear programming. Why not apply some of them to the problem of parallelizing a fault localization process? In this work, various algorithms taken from this domain are evaluated regarding their applicability to parallelize and hence speed up the fault localization process in presence of multiple faults. One of the evaluated algorithms is further adapted specifically to the fault localization problem, allowing for a more effective fault localization approach. The results of this work suggest that the evaluated approaches can lead to a significant increase in the amount of faults that can be searched at the same time and also to a considerable speed up of the fault localization process. On top of that evaluation, the work outlines various problems that can occur in evaluations, along with their possible solutions.

Vorschau

Zitieren

Zitierform:

Frenkel, Marcus: Partitionierung von Fehlerlokalisierungsproblemen mit Algorithmen aus der ganzzahligen linearen Optimierung. Hagen 2017. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe