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):

1 / 2 / 3

Kommentare (8)

  1. #1 Karl Mistelberger
    August 6, 2017

    Ein Beispiel sagt mehr als tausend Worte. Neben theoretischen Überlegungen wäre auch Fälle aus der Praxis ein lohnenswertes Thema.

    Nach gut vier Jahrzehnten einschlägiger Erfahrung bin ich bei openSUSE Tumbleweed gelandet. Die Leute tun ungefähr das, was ich mir immer vorgestellt habe und es funktioniert auch sehr gut.

    Ich habe immer die aktuelle Software und brauche mich um keine Updates kümmern.

    Momentan benutze ich Snapshot 20170802 vom vergangenen Mittwoch. Der ist nicht fehlerfrei, aber ausreichend getestet: Overall Summary of openSUSE Tumbleweed build 20170802.

    Falls es doch einmal haken sollte gibt es schnelle Abhilfe, denn die Programmierer arbeiten sowie daran und ich muss auf keine Backports warten. Ich bin selten so positiv überrascht worden.

    Last Builds for openSUSE Tumbleweed

    • #2 Marcus Frenkel
      August 6, 2017

      Wie genau steht der Kommentar jetzt in Zusammenhang mit dem Thema des Blog-Artikels?

  2. #3 Karl Mistelberger
    August 6, 2017

    Mein Kommentar nimmt Bezug auf alle 3 Teile zum Thema Fehlerlokalisierung, Komponententests, Softwaretests.

    Diese sind ziemlich theoretisch gehalten. Ein Praxisbezug wäre schon nett. Ich habe mir erlaubt ein auf real existierendes und funktionierendes Beispiel hinzuweisen.

    • #4 Marcus Frenkel
      August 6, 2017

      Dass sie theoretisch gehalten sind, ist mir klar. Darum geht es ja auch in den Artikeln – sie sollen die theoretischen Grundlagen erläutern. Was genau hat openSUSE Tumbleweed damit zu tun, wie man theoretisch die Fehlersuche auf Grundlage von Abdeckungsmatrizen parallelisieren kann?

  3. #5 Karl Mistelberger
    August 6, 2017

    > #4 Marcus Frenkel, August 6, 2017
    > Dass sie theoretisch gehalten sind, ist mir klar. Darum geht es ja auch in den Artikeln – sie sollen die theoretischen Grundlagen erläutern.

    Von jeder Theorie erwartet man, dass sie nützlich ist. Darum sollte, wenn die Stichworte Fehlerlokalisierung, Komponententests, Softwaretests auftauchen etwas zum Praxisbezug der Theorie gesagt werden. Im zitierten Artikel schreiben die Autoren:

    Localizing SQL Faults in Database Applications

    The results are encouraging and demonstrate the improvement that can be achieved with our new database-aware technique. There are, however, many areas of future work that can be explored. We performed our studies on three projects. To fully evaluate our technique, and guide additional research, we must identify other suitable subjects for our research.

    Da stellt sich natürlich die Frage, wie sieht es im richtigen Leben aus? Müssen diese Leute noch weiter forschen oder wo genau gibt es bereits Produkte, die auf dieser Basis entwickelt werden und davon auch tatsächlich profitieren? Ich erwarte ja kein selbst geschriebenes White Paper, aber Links auf solche wären schön.

    Apropos: Seit auf meinem Rechner MariaDB läuft gibt es diesbezüglich keine Probleme mehr.

    > Was genau hat openSUSE Tumbleweed damit zu tun, wie man theoretisch die Fehlersuche auf Grundlage von Abdeckungsmatrizen parallelisieren kann?

    Dass Tumbleweed damit zu tun hat habe ich nie behauptet. Anderseits scheinen die Leute die durch die Stichworte angesprochenen Probleme für ihr eigenes Produkt in den Griff gekriegt zu haben, womit sie sich bei mir beliebt gemacht haben.

  4. #6 Robert
    August 10, 2017

    Karl Mistelberger,
    danke für den Mut, praktische Beispiele zu fordern.
    Für Herrn Frenkel ist wahrscheinlich alles sonnenklar, für Außenstehende überhaupt nicht.
    Ich habe früher auch Programme selbst geschrieben und mehr durch Versuch und Irrtum die Fehler zu finden versucht.
    Ich wäre also auch an einer Systematik interessiert. Und das kann man doch auch an einem praktischen Beispiel demonstrieren.

  5. #7 Marcus Frenkel
    August 10, 2017

    Man darf bei der Diskussion nicht vergessen, dass es sich um ein akademisches Thema handelt – praktische Beispiele hierfür bedürfen einer gewissen Größe, wodurch ihre Behandlung im Rahmen dieses Blogs ungeeignet ist. Wenn es allerdings generell Interesse am Thema Unit-Tests (im ersten Teil dieser Serie nur kurz angeschnitten) gibt, kann ich dazu natürlich auch noch einen Beitrag schreiben.

  6. #8 Robert
    August 11, 2017

    Markus Frenkel,
    …….Interesse,
    das besteht. Sie scheinen da wirklich etwas sehr Praktisches konstruiert zu haben.
    Auch ein akademisches Thema kann man an einem Beispiel abarbeiten.
    Das Problem mit solchen mathematischen Modellen ist, dass man nicht sicher weiß, ob man das gleiche meint verstanden zu haben, wie der Autor es gemeint hat.