Im ersten Teil der Artikelserie wurde das Konzept von Komponententests ganz allgemein vorgestellt und im zweiten Teil wurde erklärt, wie mit Hilfe von Komponententests und Fehlerlokatoren eine teilautomatische Fehlersuche durchgeführt werden kann. Am Ende des zweiten Artikels habe ich auf ein generelles Problem von Fehlerlokatoren hingewiesen: Diese funktionieren in der Regel nur für einen einzelnen Fehler gut und führen im Mehrfehlerfall – also der Situation, dass sich in einem Programm mehr als ein Fehler befindet, welcher durch Komponententests ausgeführt wird – zu eher unbrauchbaren Ergebnissen. Warum das so ist und was man dagegen tun kann, möchte ich in diesem Artikel darlegen.
Zur Erinnerung: Lokatoren helfen bei der Fehlersuche, indem sie die aufgerufenen Komponenten (Methoden, Statements, …) nach ihrer Wahrscheinlichkeit, einen Fehler zu enthalten, sortieren. Ein bekannter Lokator ist der Tarantula-Lokator mit folgender Formel:
| rT(mi) = |
|
||||||
|
Die Bezeichnungen in der Formel hatten die folgenden Bedeutungen (man möge mir den kopierten Textbaustein verzeihen): Der Ausdruck f(mi) bezeichnet die Menge an fehlgeschlagenen Tests, welche die Methode mi aufrufen; f bezeichnet dagegen die Menge aller Tests, die fehlschlagen. Der Term f(mi) / f bezeichnet damit das Verhältnis zwischen den fehlschlagenden Tests, die mi aufrufen, und allen fehlschlagenden Tests. Analog dazu bezeichnet p(mi) die Menge an erfolgreichen Tests, die mi aufrufen und p die Menge aller erfolgreichen Tests.
Die Formel offenbart auch schon das erste Problem von Fehlerlokatoren: Sie sortieren die aufgerufenen Komponenten in Abhängigkeit davon, von wie vielen fehlschlagenden Testfällen in Relation zu allen fehlschlagenden Testfällen sie aufgerufen werden. Mit anderen Worten: Die Komponenten werden danach beurteilt, wie gut sie das Fehlschlagen aller Testfälle erklären. Und wo ist hier das Problem?
Ganz einfach: Die fehlschlagenden Testfälle müssen nicht alle aufgrund desselben Fehlers fehlschlagen! Es ist durchaus denkbar, dass einige Testfälle wegen Fehler A fehlschlagen, wohingegen andere aufgrund Fehlers B fehlschlagen und so weiter. Wenn nun einige wenige Testfälle ausschließlich wegen eines Fehlers in einer Methode m1 fehlschlagen, viele andere Testfälle aber aufgrund eines Fehlers in m2 und keiner der Testfälle die jeweils andere Methode aufruft, so wird m2 durch Tarantula (und auch durch andere Lokatoren) dementsprechend als sehr wahrscheinlich fehlerbehaftet eingestuft, da die Methode eben durch viel mehr fehlschlagende Testfälle als m1 aufgerufen wird. Das ist aber natürlich ein Trugschluss!
Daneben existiert noch eine weitere Problematik: Die Sortierung durch einen Fehlerlokator gibt keinen Hinweis darauf, wie viele Fehler sich eigentlich (beziehungsweise mindestens) im Programm befinden. Wenn die durch einen Lokator vorgeschlagenen Methoden durchsucht und ein Fehler gefunden wurde – woher soll der Programmierer wissen, ob er weiter suchen soll oder nicht? Tarantula gibt hierauf keine Antwort – die Forschung zum Glück aber schon. Und auch ich habe mich in meiner Dissertation mit genau dieser Frage beschäftigt und möchte sie hier beantworten.
Zwei Informationen sind somit interessant: Wie viele Fehler befinden sich (mindestens) in einem Programm und an welchen Stellen sollte nach ihnen gesucht werden. In der akademischen Welt existieren einige teilweise relativ komplizierte, da sehr spezialisierte Algorithmen, um diese Informationen zu sammeln. Glücklicherweise kann man sich jedoch auch mit einigen relativ einfachen Algorithmen aus der Mathematik behelfen, um die gewünschten Informationen zu besorgen.
Betrachten wir zum Beispiel einmal die folgende Abdeckungsmatrix (alle Tests sollen als fehlgeschlagen gelten):
| t1 | t2 | t3 | t4 | t5 | t6 | |
| m1 | 1 | 1 | ||||
| m2 | 1 | 1 | ||||
| m3 | 1 | 1 | ||||
| m4 | 1 | 1 | ||||
| m5 | 1 | 1 |
Auf den ersten Blick lässt sich hier nicht viel erkennen. Wir können die Matrix allerdings auch etwas umsortieren, und zwar auf die folgenden Weise:
| t2 | t3 | t5 | t1 | t4 | t6 | |
| m2 | 1 | 1 | ||||
| m5 | 1 | 1 | ||||
| m3 | 1 | 1 | ||||
| m1 | 1 | 1 | ||||
| m4 | 1 | 1 |
Alles, was ich gemacht habe, ist, Zeilen und Spalten in der Matrix zu vertauschen, also sie zu permutieren – und zwar so, dass die Zeilen und Spalten in der Matrix derart angeordnet werden, dass sie voneinander unabhängige Blöcke bilden. Hier die Matrix noch einmal, diesmal mit den markierten Blöcken:
| t2 | t5 | t3 | t1 | t4 | t6 | |
| m2 | 1 | 1 | ||||
| m5 | 1 | 1 | ||||
| m3 | 1 | 1 | ||||
| m1 | 1 | 1 | ||||
| m4 | 1 | 1 |
Eine derartige Matrix nennt sich Blockdiagonalmatrix oder kurz BDM. (Ein wichtiger Hinweis für mitlesende Mathematiker: Blockdiagonalmatrizen sind in der Mathematik üblicherweise quadratisch mit ebenfalls quadratischen Blöcken! In der Informatik müssen wir es mit derartigen Definitionen allerdings nicht ganz so genau nehmen und können auch nichtquadratische Matrizen als BDMs bezeichnen!) Der Name rührt daher, dass die Matrix aus diagonal angeordneten Blöcken besteht und nur in diesen Blöcken nichtleere Elemente (also Zellen, in denen eine “1” eingetragen ist) enthält.
Für die Fehlersuche hilft uns dies folgendermaßen: Durch die Blöcke wissen wir, dass jeder Test eines Blocks ausschließlich auch Methoden dieses Blocks und keine Methoden eines anderen Blocks aufruft. Ebenso wissen wir, dass alle Methoden eines Blocks ausschließlich von den Tests des gleichen Blocks aufgerufen werden. Dies bedeutet aber auch, dass jeder Block mindestens eine fehlerhafte Methode enthalten muss. Und warum? Ganz einfach: Enthält eine Methode eines Blocks einen Fehler, so kann sie höchstens das Fehlschlagen aller Tests in ihrem Block erklären, nicht aber das fehlschlagen von Tests anderer Blöcke, denn diese rufen die Methode ja überhaupt nicht auf, müssen also zwangsläufig eine andere Fehlerursache haben. Da jeder Block unabhängig von den anderen ist, muss es im Programm mindestens so viele Fehler wie Blöcke geben. Ein Programmierer kann also zuerst alle Methoden des ersten Blocks nach einem Fehler durchsuchen (die wiederum durch einen Fehlerlokator wie Tarantula sortiert werden können!), nach dem Fund des Fehlers anschließend alle Methoden des zweiten Blocks und so weiter, bis alle Blöcke abgearbeitet sind. Stehen genügend Programmierer zur Verfügung, können sie die einzelnen Blöcke sogar parallel abarbeiten!
Die Permutation einer Matrix in eine Blockdiagonalmatrix ist trivial (Überlegungen zum Algorithmus überlasse ich den Lesern – sie können gern in den Kommentaren diskutiert werden) und mit relativ wenig Rechenaufwand zu erreichen. Sie bilden damit ein gutes Mittel, um aus einer ursprünglich unübersichtlichen Abdeckungsmatrix eine strukturierte Suche nach Fehlern zu erlauben. Allerdings sind wir an dieser Stelle noch nicht fertig, denn aus der obigen Matrix können wir noch mehr Informationen herausfiltern.
Schauen wir uns zum Beispiel den zweiten Block, bestehend aus den Methoden m1 und m4 an, so stellen wir fest, dass keine von beiden Methoden, sollte sie denn einen Fehler enthalten, das Fehlschlagen aller Tests des Blocks erklärt. Vielmehr erkennen wir, dass beide Methoden fehlerhaft sein müssen, denn nur so wird auch das Fehlschlagen beider Tests erklärt. Den gleichen Ansatz können wir für den ersten Block anwenden: keine der Methoden des Blocks würde, falls sie denn einen Fehler enthält, das Fehlschlagen aller Tests dieses Blocks erklären. Mindestens müssen sowohl m3 als auch entweder m2 oder m5 einen Fehler enthalten, um alle Fehlschläge erklären zu können. Wir können demzufolge die Matrix sogar noch feiner in Blöcke unterteilen (es handelt sich hierbei natürlich nicht mehr um eine Blockdiagonalmatrix):
| t2 | t5 | t3 | t1 | t4 | t6 | |
| m2 | 1 | 1 | ||||
| m5 | 1 | 1 | ||||
| m3 | 1 | 1 | ||||
| m1 | 1 | 1 | ||||
| m4 | 1 | 1 |
Um in der derart zerlegten Abdeckungsmatrix nach Fehlern zu suchen, müssen nacheinander oder parallel 4 Blöcke durchsucht werden. Da drei von ihnen aus lediglich einer einzelnen Methode bestehen, müssen im Grunde nur die Methoden m2 und m5 betrachtet werden (die anderen sind ja garantiert fehlerhaft); dies stellt allerdings eher einen beispielbedingten Sonderfall dar – in der Praxis würden die meisten Blöcke mehr als eine Methode enthalten und müssten dementsprechend dann explizit durchsucht werden, was jedoch immer noch eine gewaltige Ersparnis an Suchaufwand bedeutet. Eine derartige Zerlegung einer Matrix kann übrigens als Mengenpackungsproblem aufgefasst und mit entsprechenden Algorithmen gelöst werden (auf die Niederschrift desselben verzichte ich einmal, reiche sie auf Wunsch aber gerne nach – auch sie ist nicht sonderlich kompliziert).
Aufmerksame Leser werden übrigens an dieser Stelle natürlich erkannt haben, dass m1 und m4 in jedem Fall beide einen Fehler enthalten, da beide Methoden durch jeweils einen Test exklusiv aufgerufen werden; der Test t1 ruft lediglich m1 auf, wohingegen t6 nur m4 aufruft. Ruft ein fehlschlagender Test lediglich eine einzige Methode auf, so muss diese natürlich auch zwangsläufig einen Fehler enthalten. Dieser Test kann zum verkürzen der Suche benutzt werden, reicht aber in der Regel nicht aus, wie der erste Block (und die Praxis – kaum ein Test ruft eine einzelne Methode auf) gezeigt haben.
Blockdiagonalmatrizen und eine darauf aufbauende weitere Zerlegung bieten sich demzufolge geradezu an, eine gegebene Abdeckungsmatrix derart zu zerlegen, dass auf eine in ihr mindestens enthaltene Anzahl von Fehlern geschlossen werden kann und sogar, wo sich diese Fehler ungefähr befinden. Die hierfür bereits existierenden Algorithmen sind jedoch relativ komplex – wie ich in diesem Artikel gezeigt habe, lässt sich das Ziel auch deutlich einfacher erreichen! In der Praxis wird dieser Ansatz meines Wissens bisher kaum bis gar nicht verwendet, was allerdings primär daran liegt, dass die verbreiteten Programmierwerkzeuge ihn schlicht nicht zur Verfügung stellen. Sollte sich jemand dazu berufen fühlen, Eclipse, Visual Studio oder eine andere IDE um einen derartigen praktisch anwendbaren Ansatz zu erweitern (im Rahmen meiner Dissertation sind natürlich Umsetzungen entstanden – nur praxistauglich sind diese nur bedingt), sei er an dieser Stelle herzlichst dazu ermutigt!
Kommentare (10)