Wie fast alle systematischen Testverfahren beruht die Klassifikationsbaum-Methode [Gro93] auf der Idee des Partition Testing. Der Eingabedatenraum der zu prüfenden Software wird in Teilmengen zerlegt, die sich bezüglich des Verhaltens des Prüflings jeweils gleichen. Der Test mit einem Repräsentanten aus jeder Teilmenge reicht folglich aus.
Klassifikationsbaum-Methode
Für die Partitionierung des Eingabedatenraums werden mit der Klassifikationsbaum-Methode die für den Test relevanten Gesichtspunkte (meist aus der Softwarespezifikation) ermittelt. Diese werden als Klassifikation bezeichnet. Zu jeder Klassifikation erfolgt eine vollständige Zerlegung des Eingabedatenraums in disjunkte Teilmengen, Klassen genannt.
Beispiel: Für den Spurhalteassistenten eines PKW ist die Art der Fahrbahnmarkierung eine wichtige Klassifikation mit einer Unterscheidung von einfachen und doppelten Fahrbahnmarkierungen. Für die Fahrbahnmarkierungen ist weiter zwischen gestrichelten und durchgezogenen Linien zu unterscheiden. Für die doppelte Fahrbahnmarkierung ergeben sich vier Kombinationen aus den beiden Linienarten. Durch die rekursive Anwendung von Klassifikationen auf Klassen entsteht der Klassifikationsbaum.
Alle vom Tester eingeführten testrelevanten Gesichtspunkte mit den jeweils gewählten Fallunterscheidungen sind im Klassifikationsbaum ersichtlich. Er bildet den Kopf einer Kombinationstabelle. Die Zeilen der Tabelle sind die Testfälle, die Spalten ergeben sich aus den Blattklassen des Baums. In der Kombinationstabelle werden die Testfälle durch die Kombination der Blattklassen unterschiedlicher Klassifikationen gebildet (s. Abb. 1).
Mit der Klassifikationsbaum-Methode lassen sich viele etablierte Testverfahren, wie Äquivalenzklassen- und Grenzwerttest einfach abbilden. Aufgrund der eingängigen grafischen Repräsentation und leistungsfähiger Werkzeuge (z. B. [TESTONA]) hat sich die Klassifikationsbaum-Methode schnell in der Praxis etabliert und findet sich auch im aktuellen ISO Standard 29119 Software Testing wieder.
Inzwischen gibt es eine Vielzahl von Erweiterungen der ursprünglichen Methode, die im Folgenden kurz skizziert werden.
Abb. 1: Ausschnitt eines Klassifikationsbaums für einen Spurhalteassistenten
Abhängigkeiten
Aussagenlogische Formeln können Abhängigkeiten zwischen den Elementen des Klassifikationsbaums beschreiben. Im Klassifikationsbaum aus Abbildung 1 ist es damit unter anderem möglich, die Verwendung von doppelten Fahrbahnmarkierungen auf Autobahntests (mit hohen Geschwindigkeiten) zu beschränken. Die Abhängigkeitsregel stellt dann sicher, dass doppelte Fahrbahnmarkierungen nur zusammen mit einer entsprechenden Geschwindigkeitsklasse gewählt werden.
Kombinatorisches Testen
Kombinatorisches Testen ermöglicht die autmatische Generierung von Testfällen entsprechend einer vom Tester vorgegebenen Kombinatorik. Es stehen Operatoren für die einfache, vollständige, paarweise oder mehrfach verschränkte Kombination von Klassifikationen und Klassen zur Verfügung. Zusätzliche Generierungsmechanismen ermöglichen die Erzeugung statistischer Tests und priorisierender Tests, bei denen die generierten Testfälle eine Ordnung besitzen. Auch die Modellierung von Testsequenzen ist mit den entsprechenden Erweiterungen möglich.
Time Partition Testing
Ein anderes Testverfahren, das aus der Klassifikationsbaum-Methode hervorgegangen ist und sich auf den Test eingebetteter Software fokussiert, ist das Time Partition Testing (TPT, [Leh03]). TPT ist ein modellbasiertes Testverfahren, das hybride, hierarchische Automaten einsetzt, mit denen auch parallele und reaktive Testabläufe abgebildet werden können. Es bietet sich damit auch für Closed-Loop-Tests an.
Der zeitliche Ablauf der Testfälle wird mit Hilfe des hybriden Automaten in einzelne Phasen zerlegt. An die Zustände und Transitionen werden Signaldefinitionen und Übergangsbedingungen annotiert, die das Verhalten des Testfalls beschreiben. Die Automaten haben eine Echtzeitsemantik, unterstützen kontinuierliche Signalverläufe und ermöglichen durch die Verwendung von Variationspunkten in Zuständen und Transitionen die Modellierung vieler unterschiedlich parametrierter Testabläufe in einem Automaten. Zustände und Transitionen des Automaten können dabei beliebig viele alternative Signaldefinitionen beziehungsweise Übergangsbedingungen tragen, die dann manuell oder automatisch zu Testfällen kombiniert werden können.
Mit dem TPT lassen sich Testspezifikationen bis zur Ausführbarkeit verfeinern. Die Testdaten für Eingangssignale werden als Funktion der Zeit und reaktiv in Abhängigkeit von anderen Signalen definiert. Für eine automatische Auswertung und Bewertung der Testergebnisse können Erwartungswerte im Modell vermerkt werden. Nach der Testdurchführung werden die Testergebnisse anhand definierter Auswertungsregeln automatisch bewertet.
Evolutionäre und suchbasierte Testverfahren
Die Testfallermittlung wird bei den evolutionären beziehungsweise suchbasierten Testverfahren als Suche nach den relevantesten Testfällen interpretiert [Weg01]. Zur Suche werden heuristische Verfahren eingesetzt, zum Beispiel evolutionäre Algorithmen oder Schwarmmethoden. Die Testfallermittlung wird damit vollständig automatisiert. Der Tester muss lediglich das Testziel geeignet formalisieren, sodass daraus eine Zielfunktion für die Suche abgeleitet werden kann. Evolutionäre Tests können vor allem für die Prüfung nicht-funktionaler Eigenschaften eingesetzt werden, aber auch zur Automatisierung klassischer Testverfahren wie Funktionstests und Strukturtests.
Das Grundprinzip des evolutionären Tests ist ein Nachbilden der Evolution. Jedes Individuum entspricht dabei einem Testdatum. Ausgehend von einer zufällig generierten Population von Individuen, der Startpopulation, werden solange neue Individuen erzeugt und bewertet, bis das Testziel erreicht ist oder ein anderes Abbruchkriterium den Test beendet.
Ein Individuum ist typischerweise ein Vektor unterschiedlicher Werte. Im einfachsten Fall entspricht der Vektor 1:1 seinem Testdatum.
In komplexeren Fällen wird das Testdatum mit Hilfe einer eindeutigen Transformationsvorschrift aus dem Individuum gewonnen.
Für jedes Individuum wird anhand der Zielfunktion bewertet, wie gut es das Testziel erreicht.
Muss der Spurhalteassistent beispielsweise sicherstellen, dass das Fahrzeug beim Erreichen der Fahrbahnmarkierung binnen einer Sekunde wieder in die Fahrspur zurückgeführt wird, so besteht ein Testziel darin, ein Testdatum zu finden, für das diese Anforderung nicht eingehalten wird, um einen Fehler nachzuweisen. In diesem Fall nähern Individuen mit langen Laufzeiten das Testziel besser an als Individuen mit kurzen Laufzeiten.
Dem evolutionären Kreislauf folgend werden Individuen mit langen Laufzeiten ausgewählt, um daraus neue Individuen zu kombinieren, denn sie sind offensichtlich Träger von Eigenschaften, die für das Erreichen des Testziels von Interesse sind. Durch die Kombination von Individuen mit langen Laufzeiten sollen Individuen mit noch längeren Laufzeiten gewonnen werden. Die Kombination kann zum Beispiel über den Austausch von Werten zwischen den Individuenvektoren realisiert werden.
Zur Nachbildung von Mutationen werden auch zufällige Veränderungen an Individuen vorgenommen, um damit neue Informationen in die Population einzubringen und ein zu schnelles Konvergieren der Suche zu verhindern.
Der evolutionäre Kreislauf wird so lange wiederholt, bis das Testziel erreicht wird oder ein anderes Abbruchkriterium zur Beendigung des Tests führt.
Referenzen
[Gro93]
M. Grochtmann, K. Grimm, Classification Trees for Partition Testing. Journal on Software Testing, in: Verification & Reliability, 3. Jg., Nr.2, S. 63 ff., 1993
[Leh03]
E. Lehmann, Time Partition Testing: Systematischer Test des kontinuierlichen Verhaltens von eingebetteten Systemen, Dissertation, Technische Universität Berlin, 2003
[TESTONA]
www.testona.net
[Weg01]
J. Wegener, Evolutionärer Test des Zeitverhaltens von Realzeit-Systemen, Shaker Verlag, 2001
