Debugging und KI-Halluzinationen

falsch positie, richtig positive und falsch negative Befunde

Dieses Semester unterrichte(te) ich ein Modul zum Thema Software-Testing. Meine Schüler hatten den Auftrag, in einer TypeScript-Implementierung von Vier Gewinnt (engl. Connect Four) durch systematisches Testen (dynamischer Test durch Code-Ausführung und statischer Test durch Code-Analyse) Fehler in der Anwendungslogik zu finden. Dies waren einerseits fehlende Eingabeprüfungen, die sehr einfach zu finden sind, andererseits aber auch Fehler in der Spiellogik (genauer: in der Erkennung einer Gewinnsituation), deren Ermittlung etwas anspruchsvoller ist.

Das Spiel steht im Repository connect-four-debugging zur Verfügung, wird auf der Kommandozeile gespielt und sieht folgendermassen aus:

0 1 2 3 4 5 6
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ _ x _ _
_ o o o o _ _
_ x x x o _ _
o x x x o _ _

Player o: A winner is you!

Der Auftrag ist auf der Modulwebseite genauer beschrieben.

Kontrolle

Pro Klasse wurden drei bis vier Lernende ausgelost, die ihre Lösung (das Testprotokoll mit den Befunden, die Fehlerkorrektur sowie die validierenden automatischen Testfälle) vor der Klasse vorzeigen sollten.

Die fehlende Eingabeprüfungen wurde grundsätzlich gut erkannt und zufriedenstellend korrigiert, wobei die Fehler im Sinne der automatischen Testbarkeit eher in der Kernlogik (board.ts) als im umschliessenden interaktiven Spielcode (main.ts) korrigiert worden sind.

Interessanter waren jedoch die Befunde zur eigentlichen Spiellogik (board.ts).

Aufbau der Gewinnerkennung

Der schwierigste und damit fehleranfälligste Teil des Codes ist die Erkennung einer Gewinnsituation. Hier müssen vier Spielsteine der gleichen Farbe (bzw. des gleichen Symbols x und o) in eine ununterbrochene Reihe gebracht werden, was vertikal, horizontal oder diagonal passieren kann.

Die Methode winner gibt für einen Spieler und vollzogenen Spielzug (die Zeile und Spalte, in welcher der Eingeworfene Spielstein gelandet ist). Für jede Richtung (vertikal, horizontal, diagonal) ist die Auswertung der Gewinnsituation in einer anderen Methode implementiert:

vertikal: verticalWinner
horizontal: horizontalWinner
diagonal: diagonalWinner

Falsch Positiv: vertikal und horizontal

Mehrere Schüler wollen einen Fehler in der vertikalen Siegauswertung gefunden haben, was sie auch in einem Testprotokoll(!) dokumentierten. Als ich sie darum bat, die Korrektur rückgängig zu machen und per git checkout die frühere (vermeintlich nicht funktionierende) Version wiederherzustellen, konnte der Fehler jedoch nicht provoziert werden. Was ist hier passiert?

Betrachten wir die jeweils ersten beiden Zeilen der Methoden verticalWinner und horizontalWinner:

private verticalWinner(player: Player, r: number): Player {
  const col = this.getCol(r);
  // ...
}

private horizontalWinner(player: Player, r: number): Player {
  const row = this.getRow(r);
  // ...
}

Hier fällt zunächst auf, dass der zweite Methodenparameter (fälschlicherweise) jeweils r heisst, was wohl als Abkürzung für row (Zeilenindex) steht. Hierbei handelt es sich aber nur um ein stilistisches Problem, da die vertikale Siegprüfung mittels getCol(r) auf die Spalte zugreift, während die horizontale Siegprüfung mittels getRow(r) auf der Zeile erfolgt. (Hintergrund: beide Methode prüfen, ob für den jeweiligen Spieler die Zeichenkette "xxxx" bzw. "oooo" in der relevanten Spalte bzw. Zeile vorkommt.

Ob es sich hier um ein stilistisches Problem (r ist im ersten Fall falsch benannt) oder um ein Logikproblem handelt (die Spalte wird anhand des Zeilenindex anstelle des Spaltenindex ermittelt), muss beim Aufruf ermittelt werden:

public winner(player: Player, row: number, col: number): Player {
  const horizontal = this.horizontalWinner(player, row); // Aufruf mit row
  if (horizontal != Player.Nobody) {
    return horizontal;
  }
  const vertical = this.verticalWinner(player, col); // Aufruf mit col
  if (vertical != Player.Nobody) {
    return vertical;
  }
  // ...
}

Die Implementierung ist korrekt. Der Funktionsparameter von horizontalWinner sollte jedoch c statt r heissen. Dies ist ein stilistisches Problem, das es sich durchaus zu korrigieren lohnt.

Das Testprotokoll versucht jedoch einen Fehler zu belegen, den es nicht gibt. Offenbar (und zugegebenermassen) wurde hier eine Unregelmässigkeit mithilfe eines KI-Werkzeugs entdeckt; das dazu generierte Testprotokoll ist aber eine reine Halluzination, bzw. ein falsch positiver Befund.

Richtig Positiv: fehlerhafter Indexzugriff

Ein weiterer oft festgestellter Fehlerzustand ist in der Erkennung der diagonalen Siegerstellung zu finden bzw. in der Methode getDiagonals, welche die fallende und steigende Diagonale ermittelt, die durch eine Spielsteinkoordinate geht. Diese Methode ist der komplizierteste Teil der Anwendung und ein offensichtlicher Fehlermagnet:

private getDiagonals(r: number, c: number): [string, string] {
  const rising: Array<string> = [];
  const falling: Array<string> = [];
  for (let i = r, j = c; i >= 0 && j < this.fields[0].length; i--, j++) {
    rising.push(this.fields[i][j]);
  }
  for (let i = r, j = c; i < this.fields.length && j >= 0; i++, j--) {
    rising.push(this.fields[i][j]);
  }
  for (
    let i = r, j = c;
    i < this.fields.length && j < this.fields[0].length;
    i++, j++
  ) {
    falling.push(this.fields[i][j]);
  }
  for (let i = r, j = c; i >= 0 && j >= 0; i--, j--) {
    falling.push(this.fields[i][i]);
  }
  return [rising.join(""), falling.join("")];
}

Eine Unregelmässigkeit findet sich im Zugriff auf die fields-Eigenschaft: Diese findet an drei Orten mit den Indizes i (Zeile) und j (Spalte) als fields[i][j] statt, jedoch am vierten Ort ‒ fälschlicherweise ‒ zweimal mit dem Zeilenindex als fields[i][i]. Dies führt dazu, dass die fallende Diagonale falsche Werte enthält. Eine Gewinnsituation kann dadurch fälchlicherweise erkannt oder nicht erkannt werden.

Hierbei handelt es sich wieder um eine Unregelmässigkeit, die mit einem KI-Werkzeug sehr gut erkannt wird. In diesem Fall ist der Befund aber korrekt: es handelt sich um einen richtig positiven Befund.

Schüler, die den ersten falsch positiven Befund meldeten, haben i.d.R. auch diesen zweiten richtig positiven Befund protokolliert.

Dieser Fehler lässt sich über einen dynamischen Test nur sehr schwierig ermitteln, da er schlecht reproduzierbar ist, zumal scheinbar zufällige Spielsteine aus dem Spielfeld berücksichtigt werden. Die statische Codeanalyse ist also hier sehr wichtig und sinnvoll.

Falsch Negativ: Logikfehler

Der fehlerhafte Indexzugriff fields[i][i] maskiert einen anderen (absichtlich eingebauten) Logikfehler teilweise, d.h. für fallende Diagonalen. Ist der erste Indexzugriff erst einmal korrigiert, findet man den nächsten Fehler durch dynamische Tests: Es werden Siegsituationen bereits nach drei diagonal in einer Reihe liegender Steine erkannt statt nach den verlangten vier.

Der Grund dafür ist, dass beim Aufzählen der diagonal liegenden Steine immer vom zuletzt eingeworfenen Stein ausgegangen wird ‒ und zwar für beide Seiten der Diagonalen! Das grosse X in der Mitte wird in der folgenden Spielsituation also doppelt gezählt:

_ _ x
_ X _
x _ _

Dadurch wird fälschlicherweise eine Gewinnsituation erkannt. Die Initialisierung im Schleifenkopf lautet jeweils let i = r, j = c. Zur Korrektur muss dieser Index jeweils in der zweiten Schleife des Schleifenpaares um eins in die Suchrichtung verschoben werden, z.B. zu let i = r + 1, j = c - 1 in der zweiten Schleife, welche den Abschnitt unten links der steigenden Diagonalen berücksichtigt: i++, j--.

Diesen Fehler haben nur die wenigsten Schüler herausgefunden. Hier liegt keine Unregelmässigkeit im Code vor. Im Gegenteil: der Code ist zu regelmässig und beachtet die Ausnahmesituation des zuletzt eingeworfenen Steines nicht, der dann doppelt gezählt wird.

Fazit

Wenig überraschend haben viele Schüler den Auftrag mithilfe von KI-Werkzeugen bearbeitet. Diese mögen Hinweise auf verdächtige Codestellen geben, welche man aber zuerst überprüfen muss. Diese Art der statischen Code-Analyse zur Ermittlung potenzieller Problemstellen ist ein durchaus legitimer Einsatz von KI-Werkzeugen.

Problematisch ‒ und peinlich ‒ wird es, wenn Schüler ein Testprotokoll durch KI generieren lassen, ohne die Tests selber durchzuspielen. In der Praxis würden dadurch Fehlerberichte erstellt, zu denen es keinen entsprechenden Fehler gibt, was zu Mehraufwand ohne Mehrwert führt.

Das schwierigste Problem ‒ die doppelte Zählung des eingeworfenen Spielsteins bei der Erkennung diagonaler Gewinnsituationen ‒ konnte aber nur durch eine Kombination dynamischer (das Spiel ausprobieren) und statischer Tests (den Code lesen) gefunden und behoben werden. Hierzu ist ein Verständnis der Programmlogik nötig, was v.a. diejenigen Schüler erreicht haben, die sich mit der Materie befasst haben, statt nur den Auftrag und Programmcode in einen Prompt zu kopieren.

Ausblick

Die bei dieser Übung und deren Auswertung gesammelten Erkenntnisse können gewinnbringend für künftige Aufträge genutzt werden:

Verbindet man die Abgabe eines schriftlichen Artefakts mit der Demonstration des darin Dokumentierten, kann schnell festgestellt werden, ob hier tatsächlich Befunde dokumentiert oder bloss Text generiert worden ist.
Unregelmässigkeiten in korrektem Programmcode führen bei der statischen Code-Analyse zu teils falsch-positiven Befunden. Möchte man im Rahmen einer Debugging-Aufgabe Fehler im Programmcode einbauen, sollte dies möglichst unauffällig geschehen: durch fehlerhafte Regelmässigkeit.
Das Verantwortungsbewusstsein der Schüler könnte weiter auf die Probe gestellt werden, indem man etwa bei der Abgabe eines Testprotokolls eine Unterschrift des Schülers verlangt, etwa in Kombination mit einer Erklärung, dass die im Testprotokoll dokumentieren Befunde tatsächlich am Testobjekt gemacht worden sind.