Covering Array Generation: Algorithms and implementation

Bachelor-Studiengang IT Security

Manuel Leithner

Betreuer: DI Peter Kieseberg

Ausgangslage

Testen ist ein essentieller Bestandteil der Software-Entwicklung, welcher dazu dient, Fehler in einer Anwendung zu erkennen. Dabei ist eine integrierte Vorgehensweise sehr ratsam, denn je später Bugs erkannt werden, desto teurer wird deren Behebung. Im Gegensatz zu den populären Unit Tests, bei denen Anwendungsfälle in ihrer Gesamtheit abgebildet werden, ermöglicht modellbasiertes Testen eine höher granulierte und intensivere Verifizierung einzelner Funktionen oder Prozesse.

Ein solches Modell beinhaltet Informationen zu den verfügbaren Parametern einer Funktion, welche konkreten Werte diese jeweils annehmen können, sowie etwaige Einschränkungen bezüglich ungültiger Eingaben (z.B. „Wenn im ersten Parameter nicht ‚Windows‘ definiert wird, darf im zweiten Parameter nicht ‚Access‘ stehen“). Anhand dieser Spezifikation wird ein Test-Set generiert, welches einzelne Testfälle beinhaltet. Diese Generierung kann auf verschiedene Arten erfolgen: Ein naiver Ansatz wäre es, alle möglichen Kombinationen von Werten heranzuziehen. Damit werden zwar (bei korrekter Modellierung) alle Fehler erkannt, aber die große Anzahl der Testfälle ist meist untragbar.

Kombinatorisches Testen stützt sich auf die Erkenntnisse von empirischen Studien, welche zeigen, dass alle darin analysierten Bugs durch die Interaktion von sechs oder weniger Parametern ausgelöst wurden. Sinnvoll sind also Test-Sets, welche alle Werte-Kombinationen von einigen wenigen Parametern beinhalten. Das Ergebnis ist eine drastische Reduzierung der benötigten Testfälle bei fast gleichbleibender Effektivität zur Erkennung von Fehlern. Die Generierung solcher Tests ist jedoch eine komplexe Aufgabe, für die verschiedene Ansätze zur Verfügung stehen.

Ziel

Ziel dieser Arbeit ist es, jene Algorithmen und Implementierungen zur Generierung von kombinatorischen Test-Sets zu identifizieren, welche für den praktischen Einsatz am besten geeignet sind. Um eine nuancierte Aussage treffen zu können, werden verschiedene Modelle verwendet, welche eine Vielzahl von praktischen Problemstellungen abbilden.

Ergebnis

Das Ergebnis der Evaluierung ist ein quantitativer und qualitativer Vergleich von Tools anhand der Größe des resultierenden Test-Sets, Speicher- und Zeitverbrauch, Unterstützung für Einschränkungen sowie weiterer Metriken aus der aktuellen Forschung im Bereich des kombinatorischen Testens.