Klassifikationsbaum-Methode
# Klassifikationsbaum-Methode

Die Klassifikationsbaum-Methode (englisch classification tree method) ist eine im Bereich von eingebetteter Software verbreitete Methode zur Ermittlung funktionaler Blackbox-Tests. Sie wurde ursprünglich 1993 von Grimm und Grochtmann entwickelt. Es handelt sich dabei nicht um Klassifikationsbäume im Sinne von Entscheidungsbäumen.

Die Klassifikationsbaum-Methode besteht im Wesentlichen aus zwei Schritten:

* Bestimmung der testrelevanten Aspekte (so genannte Klassifikationen) und möglicher Ausprägungen (genannt Klassen), so wie
* Kombination von unterschiedlichen Klassen für alle Klassifikationen zu Testfällen.

Ausgangspunkt ist die funktionale Spezifikation (z. B. Anforderungen, Anwendungsfall, …) des Testobjekts. Der zweite Schritt der Methode folgt den Prinzipien des kombinatorischen Testentwurfs.

Ergebnis ist eine Menge von Testfallspezifikationen, die möglichst fehler-sensitive, jedoch keine redundanten Testfallspezifikationen enthalten soll. Durch die methodische Vorgehensweise soll sichergestellt werden, dass die resultierende Menge von Testfallspezifikationen alle relevanten Testfälle enthält.

Obwohl die Methode mit Stift und Papier anwendbar ist, wird üblicherweise der Klassifikationsbaum-Editor (engl. Classification Tree Editor) dafür verwendet.

## Die Anwendung der Klassifikationsbaum-Methode

Voraussetzung für die Anwendung der Methode ist die Festlegung eines Testobjekts. Die Klassifikationsbaum-Methode ist eine Methode für den Black-Box-Test und unterstützt dabei ganz unterschiedliche Arten von Prüflingen, wie beispielsweise Hardware-Systeme, integrierte Hardware-Software-Systeme, reine Software-Systeme, insbesondere auch Eingebettete Systeme, Benutzer-Schnittstellen, Betriebssysteme, Parser, so wie auch Teilsysteme dieser.

Nach Auswahl des Prüflings besteht der erste Schritt nun in der Ermittlung der testrelevanten Aspekte. Ein jedes System lässt sich beschreiben als eine Sammlung aus Klassifikationen für alle Eingabe- und Ausgabe-Parameter. (Wobei Eingabe-Parameter auch Umgebungsvariablen, Pre-Conditions und weitere, eher untypische Parameter enthalten können.) Jede Klassifikation besteht aus einer beliebigen Menge von disjunkten Klassen, welche mögliche Ausprägungen der Parameter beschreiben. Die Wahl der Klassen folgt dabei typischerweise dem Prinzip der Äquivalenzklassen-Bildung für abstrakte Testfälle und der Grenzwert-Analyse für konkrete Testfälle. Zusammen bilden alle Klassifikationen und Klassen den Klassifikationsbaum. Darüber hinaus lassen sich Klassifikationen auch semantisch in Kompositionen gruppieren.

Diese Aufteilung des Problems in verschiedene Aspekte, die im Folgenden separat verfeinert werden können, reduziert die Komplexität des ursprünglichen Testproblems.

Eine Äquivalenzklasse kann man nach zusätzlichen Gesichtspunkten weiter klassifizieren. Durch die wiederholte Bildung von Unter-Klassifikationen mit den dazugehörigen Klassen ergibt sich schlussendlich der Klassifikationsbaum. Seine Wurzel bildet die Problemstellung; er wächst von oben nach unten; Klassifikationen sind durch Rechtecke eingerahmt; Klassen haben keinen Rahmen.

Im zweiten wesentlichen Schritt der Methode werden Testfällen dann dadurch gebildet, dass für jede Klassifikation im Baum genau eine Klasse gewählt wird. Die Auswahl der Testfälle war ursprünglich eine manuelle Tätigkeit des Testers.

Die Blätter des Klassifikationsbaums (d. h. Klassen ohne weitere Klassifikation) bilden den Kopf der Kombinationstabelle. Eine Zeile in der Kombinationstabelle spezifiziert einen Testfall, indem die Blattklassen des Baums markiert werden, aus denen ein Wert für diesen Testfall verwendet wird.

### Beispiel

Für ein Datenbanksystem soll ein Testentwurf durchgeführt werden. Bei der Anwendung der Klassifikationsbaum-Methode ergibt die Festlegung der testrelevanten Aspekte im ersten Schritt die Klassifikationen: Benutzerrolle, Datenbankanfrage und Zugriffsart. Für die Benutzerrollen wurden zwei Klassen identifiziert: Normaler Benutzer und Administrator. Es gibt drei Arten von Datenbankanfragen: Hinzufügen, Bearbeiten und Löschen. Für Zugriffsart wurden drei Klassen gefunden: Natives Tool, Webbrowser, API. Die Webbrowser-Klasse ist weiter verfeinert mit dem Testaspekt Marke, drei mögliche Klassen gibt es hier: Internet Explorer, Mozilla Firefox, and Apple Safari.

Der erste Schritt der Methode ist nun abgeschlossen. Natürlich gibt es weitere mögliche Testaspekte, wie zum Beispiel die Geschwindigkeit der Netzanbindung oder die Zahl der vorhandenen Datenbankeinträge. Durch die graphische Darstellung der Testaspekte im Baum lassen sich die gewählten Aspekte und die vorgesehenen Werte schnell einsehen.

Im zweiten Schritt wurden drei Testfälle manuell gewählt:

* Ein normaler Benutzer fügt einen neuen Datensatz mittels eines nativen Tools ein.
* Ein Administrator bearbeitet einen bestehenden Datensatz mit dem Firefox Browser.
* Ein normaler Benutzer löscht einen Datensatz über die API.

Noch ein wenig Statistik: Es gibt 30 mögliche Testfälle insgesamt (2 Benutzerrollen * 3 Datenbankanfragen * 5 Zugriffsarten). Für die Minimalabdeckung reichen 5 Testfälle aus, da es 5 Zugriffsarten gibt (und Zugriffsart die Klassifikation mit der größten Anzahl an Klassen ist).

## Erweiterungen

### Ursprung

Die Klassifikationsbaum-Methode wurde im Software-Forschungslabor von Daimler-Benz in Berlin entwickelt und ist eine Weiterentwicklung der Category-Partition Method (CPM) von Ostrand und Balcer. Gegenüber der CPM bietet sie folgende Vorteile:

* Notation: Bei der CPM gab es nur texuelle Beschreibung im Gegensatz zur graphischen Baum-Darstellung.
* Verfeinerungen erlauben die Spezifikation von bedingten Testaspekten.

    CPM bot nur Restriktionen. Die Klassifikationsbaum-Methode bietet hierarchische Verfeinerungen direkt im Baum für implizite Abhängigkeiten.
* Werkzeugunterstützung: Das Werkzeug von Ostrand und Balcer unterstützte nur Testfallgenerierung ohne Bestimmung der Testaspekte.

    Der Klassifikationsbaumeditor Testona (ehemals Classification Tree Editor (CTE)) von Grochtmann und Wegener hingegen unterstützt sowohl Partitionierung als auch Testfallgenerierung.

### Klassifikationsbaum-Methode für eingebettete Systeme

Die Klassifikationsbaum-Methode war ursprünglich für Entwurf und Spezifikation abstrakter Testfälle vorgesehen. Mit der Klassifikationsbaum-Methode für eingebettete Systeme lassen sich auch Tests implementieren. Dazu wurden einige Zusatzinformationen vorgesehen:

* Zusätzlich zu atomaren Testfällen lassen sich Testsequenzen mit mehreren einzelnen Testschritten definieren.
* Konkretes Zeitverhalten (z. B. in Sekunden, Minuten …) kann für jeden einzelnen Testschritt festgelegt werden.
* Signalverläufe (z. B. Linear, Spline, Sinus …) können zwischen gewählten Klassen aufeinander folgender Testschritte angegeben werden.
* Eine Unterscheidung zwischen Aktion und Zustand lässt sich modellieren. Sie wird durch unterschiedliche graphische Markierungen im Test dargestellt.

Das Modultest-Werkzeug TESSY nutzt ebenfalls einige dieser Erweiterungen.

### Konkrete Testdaten und zeitliche Aspekte

Ansätze aus Klassifikationsbäumen Testdaten zu generieren wurden ebenfalls verfolgt.

Die Methode Time Partition Testing (TPT) ist eine Erweiterung der Klassifikationsbaum-Methode um zeitliche Aspekte, die beim Test von Steuerungs- und Regelungssystemen eine große Rolle spielen. E. Lehmann beschreibt in seiner Dissertation, wie Klassifikationen auf Zustände und Zustandsübergänge in den TPT-Automaten abgebildet werden können, und so auch zeitliche Aspekte abgebildet werden können.

### Abhängigkeitsregeln und Automatische Testfallgenerierung

Der Verfeinerungsmechanismus in der Klassifikationsbaum-Methode lässt sich für die Modellierung von Abhängigkeiten nutzen. Allerdings lassen sich so keine Abhängigkeiten zwischen Klassen unterschiedlicher Klassifikationen modellieren. Lehmann und Wegener haben Abhängigkeitsregeln basierend auf Boolescher Algebra für den CTE eingeführt. Außerdem ermöglichten sie die automatische Generierung von Testfallmengen basierend auf kombinatorischem Testdesign (z. B. der Pairwise-Methode).

### Priorisierende Testfallgenerierung

Jüngere Erweiterungen zu Klassifikationbaum-Methode betreffen die priorisierende Testfallgenerierung: Mit ihnen ist es möglich, Elementen des Klassifikationsbaums Gewichte in Form von Eintrittswahrscheinlichkeit, Fehlerwahrscheinlichkeit und Risiko zuzuordnen. Diese Gewichte lassen sich dann in der Testfallgenerierung verwenden, um Testfälle in Reihenfolge ihrer Priorität (der abgedeckten Gewichte) zu erzeugen. Statistisches Testen (z. B. für den Test von Materialermüdung und Verschleiß) ist ebenfalls möglich, indem die zugeordneten Gewichte als diskrete Wahrscheinlichkeitsverteilung interpretiert werden.

### Testsequenz-Generation

Durch das Hinzufügen von gültigen Übergängen zwischen den einzelnen Klassen einer Klassifikation lassen sich diese Klassifikationen als State-Machine interpretieren. Die Gesamtheit aller Klassifikationen im Baum wird zum Statechart. Dieses Vorgehen definiert eine erlaubte Abfolge von Klassenverwendungen in Testschritten und damit auch die automatische Generierung von gültigen Testsequenzen. Unterschiedliche Abdeckungsraten sind verfügbar, wie Zustandsüberdeckung, Transitionsüberdeckung (Pfadüberdeckung) und Abdeckung von Zustandspaaren und Transitionspaaren.

### Numerische Abhängigkeiten

Zusätzlich zu Booleschen Abhängigkeiten, die Aussagen über das gemeinsame Auftreten von Klassen in einem Testfall machen, lassen sich auch numerische Abhängigkeiten definieren, die eine Berechnungsvorschrift vorgeben, bei denen Klassifikationen als Variablen interpretiert werden und deren Belegung sich aus den im Testfall genutzten Klassen ergibt.

## Classification Tree Editor Testona

Der Klassifikationsbaumeditor Testona (ehemals CTE) unterstützt den Entwurf des Klassifikationsbaums sowie die Spezifikation der Testfälle. Testona besitzt einen Graphikeditor, der speziell zum Zeichnen von Klassifikationsbäumen gedacht ist. Beispielsweise berücksichtigt Testona die vorgeschriebene Abfolge von Klassifikation bzw. Komposition und Klasse und schlägt beim Zeichnen das jeweils passende Baumelement vor. Die Testfallspezifikationen werden in der Kombinationstabelle angelegt und durch Testona verwaltet. Sie können in Testsequenzen zusammengefasst werden, die zur Beschreibung von dynamischen Abläufen benötigt werden. Zur Dokumentation können von Testona Reports in Excel, Word oder als Textdatei erzeugt werden. Zum Modultest-Werkzeug TESSY können die erstellten Testfälle direkt exportiert werden.

## Vorteile

### Visualisierung der Testideen

Ein wesentlicher Vorteil der Klassifikationsbaum-Methode ist die Visualisierung der Testideen, die somit leicht vermittelbar sind, beispielsweise bei Reviews. Reviews sind auch ein probates Mittel, wenn es darum geht, sich zu versichern, dass keine Testfallspezifikationen fehlen.

### Schafft Vertrauen

Hat man einen sorgfältig erarbeiteten Baum und wohlüberlegte Testfallspezifikationen erstellt, gibt es eine große Wahrscheinlichkeit dafür, dass man die meisten oder vielleicht sogar fast alle Fehler finden wird.

### Reduziert die Komplexität

Beim ersten Nachdenken über die notwendigen Testfälle für ein bestimmtes Problem hat man zumeist zahlreiche Einfälle und Ideen. Die Herausforderung besteht eher darin, die Einfälle zu strukturieren und redundante Testfälle zu erkennen. Die Klassifikationsbaum-Methode reduziert die in dieser Aufgabe liegende Komplexität, denn sie erlaubt, einzelne Aspekte (Klassifikationen) isoliert zu betrachten und sich gezielt Gedanken über die nötigen (und unnötigen!) Äquivalenzklassen zu machen.

### Überprüft die Spezifikation

Der erste Schritt der Klassifikationsbaum-Methode ist die Analyse der Problemspezifikation. Dies erzwingt automatisch die Überprüfung der Spezifikation auf Auslassungen, Widersprüche und Unklarheiten.

### Abschätzung des Testaufwands

Schon aus dem Klassifikationsbaum kann man gewisse Maße ermitteln, z. B. die minimale Anzahl von Testfällen für einen gegebenen Baum. Diese und andere Maße werden durch das Werkzeug Testona ermittelt.

## Nachteile und Kritik

Das Erstellen von guten Klassifikationsbäumen wird durch die Vermischung unterschiedlicher Aspekte erschwert. Während bei der Äquivalenzklassenmethode und der Grenzwertanalyse zunächst jede Größe für die Zerlegung in relevante Bereiche allein betrachtet wird und erst in einem zweiten Schritt Abhängigkeiten zwischen Größen betrachtet werden, müssen beide Schritte im Sinn der Klassifikationsbaum-Methode zusammen erfolgen. Dies ist notwendig, da die Baumstruktur wesentlich von Abhängigkeiten zwischen Größen beeinflusst wird.

Klassifikationsbäume sind übersichtlich bei einer begrenzten Anzahl von Klassifikationen, Äquivalenzklassen und Testfällen. Bei großen Klassifikationsbäumen ist es schwierig die Übersicht zu behalten.

