Softwaretests Teil 2 – Fehlerlokalisierung

Im ersten Teil habe ich die Grundlagen von Komponententests (auch Unit-Tests genannt) erklärt. Diese werden in der Form (und noch vielfältiger) in der Praxis auch so angewandt. Mit dem heutigen Artikel wollen wir die Praxis langsam verlassen und uns langsam in den Bereich der akademischen Forschung begeben – was nicht heißt, dass der in diesem Artikel vorgestellte Ansatz nicht auch in der Praxis angewendet wird; nur eben deutlich seltener (sollte sich unter meinen Lesern jemand befinden, der die hier beschriebene Technik tatsächlich in der Praxis anwendet, würde ich mich über eine kurze Meldung in den Kommentaren freuen).

Also, worum geht es?

Wie im letzten Artikel vorgestellt, können Tests oder Testmethoden verwendet werden, um einzelne Komponenten eines Programms auf Fehler hin zu untersuchen. Schlägt ein solcher Test fehl, liegt die Vermutung nah, dass die entsprechende Komponente einen Fehler enthält. Sind die Komponenten entsprechend klein gewählt, kann der Fehler somit relativ genau im Programmcode eingegrenzt werden. Stellen die Komponenten also etwa einzelne Methoden im Programm dar – man spricht auch von der Methodenebene als Granularität -, lässt sich ein potentieller Fehlerort auf eine einzelne Methode eingrenzen.

Soweit zumindest die Theorie. In der Praxis scheitert diese Idealvorstellung daran, dass derart feingranulare Komponenten selten komplett unabhängig von anderen getestet werden können. So rufen etwa Funktion während ihrer Abarbeitung meist auch andere Funktionen auf, die wiederum weitere Funktionen aufrufen können und so weiter. Ein fehlschlagender Test weist demzufolge lediglich darauf hin, dass irgendeine der durch ihn direkt oder indirekt aufgerufenen Funktionen einen Fehler enthält (und manchmal ist nicht einmal das sicher – aber dazu vielleicht in einem späteren Artikel mehr). Um dennoch auf Grundlage fehlschlagender Tests einen Fehlerort im Programm bestimmen zu können, kann man sich der Technik der Fehlerlokalisierung (Fault Localization in der Fachliteratur) bedienen.

Ein wichtiger Begriff in diesem Zusammenhang ist der der Abdeckungsmatrix. Wie erwähnt, werden durch einen Test in der Regel mehrere Funktionen direkt oder indirekt aufgerufen. Wird während der Testausführung überwacht, welcher Test welche Funktionen aufruft, können die so gesammelten Informationen in einer Matrix – eben der Abdeckungsmatrix – zusammengefasst werden. Diese hat üblicherweise eine Spalte für jeden ausgeführten Test und eine Zeile für jede ausgeführte Methode (oder was auch immer als Komponente aufgefasst wird; verbreitet sind Methoden und Statements). Eine “1” in einer Zelle der Matrix bedeutet, dass der Test dieser Spalte die entsprechende Methode (direkt oder indirekt) aufruft; eine “0” dementsprechend, dass der Test diese Methode nicht aufruft. Eine derartige Matrix könnte zum Beispiel so aussehen (die 0en wurden der Übersichtlichkeit halber weggelassen):

Diese Matrix sagt uns, dass der Test t₁ die Methoden m₁, m₂ und m₄ aufruft, der Test t₂ die Methoden m₂ und m₃ und so weiter. Schlägt nun t₁ fehlt, müsste sich der Fehler irgendwo in m₁, m₂ und m₄ finden lassen – wo genau, lässt sich aus der Matrix aber natürlich nicht direkt ablesen.

Hier kommt nun allerdings die Technik der Fehlerlokalisierung – oder, genauer: die der abdeckungsbasierten Fehlerlokalisierung – ins Spiel. Schlägt nämlich mehr als ein Test fehl, kann aus dem Verhältnis aus fehlgeschlagenen und fehlerfreien Tests abgeschätzt werden, wo sich der Fehler ungefähr im Programm befinden könnte. Dazu wird mit einem Fehlerlokator ein Ranking aller aufgerufenen Methoden bestimmt; die Methoden mit der höchsten Fehlerwahrscheinlichkeit befinden sich im Ranking oben, die anderen unten.

Ein in der Forschung häufig zitierter Fehlerlokator ist der Tarantula-Lokator (über die Herkunft des Namens müsste ich spekulieren, würde aber meinen, dass er nach einer Spinne benannt wurde, weil er in den Spider Labs der University of California entwickelt wurde; letztere haben vermutlich ihren Namen daher, dass sie sich mit der Bug-Suche beschäftigen…aber das ist alles Spekulation). Dieser Lokator berechnet das Ranking, indem jeder Methode ein Verdächtigkeitswert zugeordnet wird – je verdächtiger eine Methode ist, desto wahrscheinlicher enthält sie einen Fehler. Die Verdächtigkeit einer Methode errechnet sich aus dem Verhältnis von fehlschlagenden und erfolgreichen Tests, von denen sie aufgerufen wird; konkret sieht die Formel so aus:

Die Formel sieht komplizierter aus, als sie ist; gehen wir sie daher Stück für Stück durch. Berechnet werden soll r_T(m_i), also der Rank der Methode m_i mit Hilfe des Tarantula-Lokators r_T. Der Ausdruck f(m_i) bezeichnet die Menge an fehlgeschlagenen Tests, welche die Methode m_i aufrufen; f bezeichnet dagegen die Menge aller Tests, die fehlschlagen. Der Term f(m_i) / f bezeichnet damit das Verhältnis zwischen den fehlschlagenden Tests, die m_i aufrufen, und allen fehlschlagenden Tests. Analog dazu bezeichnet p(m_i) die Menge an erfolgreichen Tests, die m_i aufrufen und p die Menge aller erfolgreichen Tests.

Schauen wir uns dazu ein konkretes Beispiel an. Gegeben sei die folgende Abdeckungsmatrix, wobei die mit f_i bezeichneten Spalten fehlschlagende und die mit p_i bezeichneten Spalten erfolgreiche Tests kennzeichnen:

Rechts neben der Tabelle sind die Verdächtigkeitswerte zu sehen, die durch den Tarantula-Lokator berechnet wurden. m₁ wird nur durch einen einzigen (fehlschlagenden) Test aufgerufen, wodurch sich für die Berechnung der Verdächtigkeit folgende Formel ergibt:

Die Methode m₂ wird von 2 fehlschlagenden und einem erfolgreichen Test aufgerufen, weswegen das Ranking folgendermaßen berechnet wird:

Anschließend werden die Methoden entsprechend ihres Rankings sortiert, in diesem Fall also m₁, m₂, m₄ und als letztes m₃. Der Tarantula-Lokator bewertet Methoden, die von vielen fehlschlagenden und wenig erfolgreichen Tests aufgerufen werden, als größere Kandidaten für einen Fehler als Methoden, die von wenigen fehlschlagenden und vielen erfolgreichen Tests aufgerufen werden. Für die systematische Fehlersuche würde man nun beginnen, zuerst m₁ nach einem Fehler zu durchsuchen, da dies die Methode mit der größten Fehlerwahrscheinlichkeit ist. Sollte sich hier ein Fehler finden, ist die Suche beendet; ansonsten würde mit m₂ fortgefahren werden, dann m₄ und als letztes m₃ (wo dann hoffentlich ein Fehler gefunden wird). Eine Voraussetzung für den Einsatz von Tarantula ist, dass wenigstens ein Test fehlschlägt und wenigstens ein Test erfolgreich durchläuft – ansonsten würde sich in der Formel eine Division durch 0 ergeben, was ja nicht im Sinne der Mathematik ist.

Neben Tarantula gibt es noch weitere (und bessere) Lokatoren, durch welche die getesteten Methoden in ein Ranking überführt werden können. Die meisten von ihnen arbeiten über Formeln, die auf die ein oder andere Weise das Verhältnis von fehlschlagenden zu erfolgreichen Tests, die eine Methode ausführen, bewerten. Ein Problem ist allerdings allen gemein (darin liegt wohl auch begründet, dass die Fehlerlokalisierung nach wie vor ein eher akademisch bearbeitetes Thema ist): Bei hinreichend großen Programmen müssen sehr viele Methoden entsprechend ihres Rankings untersucht werden, bis ein Fehler gefunden wird – zu viele, um in der Praxis gegen den “intuitiven Ansatz” (d. h. einen fehlschlagenden Test debuggen und den Fehler auf Grundlage der Kenntnisse über das Programm suchen) zu bestehen.

Weiterhin ist problematisch, dass dieser Ansatz nur für das Finden eines einzelnen Fehlers geeignet ist. Warum das so ist und welche Lösung es hierfür gibt, werde ich im nächsten Teil der Serie beleuchten.