Kombinatorisches Testen ist eine Black-Box-Methodik um ein System unter Test (SUT) strukturiert auf unerwünschte Wechselwirkungen in seiner Eingabe zu testen. Es gibt zwei wesentliche Voraussetzungen für die Anwendbarkeit des kombinatorischen Testens:

1. Es muss ein Eingabeparametermodell (kurz: IPM, vom englischen Input-parameter model) geben [1], welches das SUT mittels Parameter und deren jeweiligen Werten modelliert.
2. Es muss ein Test-Orakel geben. Das ist eine Methode, mit der ein:e Tester:in fehlerhaftes Verhalten des SUT beim, beziehungsweise nach, dem Ausführen eines Tests erkennen kann.

Beim Kombinatorischen Testen der Stärke t, werden alle möglichen Wertzuweisungen an t beliebige Parameter des Eingabeparametermodells ausgetestet. Das bedeutet, dass es für jede beliebe Wahl von t Eingabeparametern und jede beliebige Wahl derer Werte mindestens einen Test gibt, in dem die Wertzuweisung an die t Parameter genau dieser Wahl entspricht. Kombinatorisches Testen wurde in den letzten Jahren in verschiedenen Bereichen angewandt [2] und hat sich als effiziente Testmethodik erwiesen, siehe z. B. [3]–[5] und [6]. Für eine umfassende Einführung in das kombinatorische Testen verweisen wir auf [7].

Die theoretische Grundlage des kombinatorischen Testens wird durch kombinatorische Objekte, wie Covering Arrays, gegeben. Letztere können wie folgt definiert werden (siehe dazu auch [8]).

Definition: Ein (einheitliches) Covering Array CA(N; t, k, v) ist ein N × k-Array über einem v-adischen Alphabet, das die Eigenschaft besitzt, dass in jedem N × t-Teilarray, bestehend aus t beliebigen verschiedenen Spalten des Covering Arrays, jede mögliche t-Tupel-Kombination des v-adischen Alphabets mindestens einmal als Zeile vorkommt. Der Parameter t wird als Stärke des Covering Arrays bezeichnet.

Im einfachsten Fall, nämlich dann, wenn das SUT einen Eingaberaum hat, der mit einem IPM mit Eingabeparametern mit homogenen Wertebereichen modelliert werden kann, zwischen denen es keine Nebenbedingungen und Einschränkungen gibt, liefert ein Covering Array der Stärke t bereits eine Menge von (abstrakten) kombinatorischen Tests für das SUT. Um aus einem Covering Array (konkrete) kombinatorische Tests zu erhalten, werden die Zeilen des Arrays verwendet, um die einzelnen Testfälle zu definieren (gegebenenfalls, müssen die abstrakten Werte durch konkrete Werte ersetz und die Zeilen zu ausführbaren Tests übersetzt werden).

Das Bild zeigt ein CA(20;3,11,2), d.h. ein Covering Array der Stärke t=3, über einem binären Alphabet (v=2) mit elf Spalten (k=11) und zwölf Zeilen (N=20). Dieses Array hat die Eigenschaft, dass bei beliebiger Auswahl von drei verschiedenen Spalten b_i, b_j, b_k mit paarweise unterschiedlichen i, j, k ∈ {1,...,11} jedes mögliche binäre Tripel mindestens einmal in dem aus diesen Spalten bestehenden Array (b_i, b_j, b_k) vorkommt. Für k = 11 und v = 2 könnte eine 3-Wege-Interaktion (p2=1, p3=0, p10=1) sein. Diese wird durch die vierte und sechste Zeile des CA(20;3,11,2) im Bild abgedeckt.

Covering Arrays zu gegebener Konfiguration mit der kleinstmöglichen Zeilenanzahl (N) nennt man optimale Covering Arrays. Dazu ist festzuhalten:

• Die Erzeugung von optimalen Covering Arrays ist Gegenstand der Forschung in der Diskreten Mathematik und der Theoretischen Computer Wissenschaft. Beispielsweise sind mathematische Methoden zur Erstellung von optimalen Covering Arrays nur für gewisse Werte von t,k und v sowie einige wenige Einzelfälle bekannt. Weiters ist die Komplexitätsklasse des Problems der Erzeugung von optimalen Covering Arrays im Sinne der Komplexitätstheorie noch unbekannt [9].
• Aus der Perspektive der Anwendungen entspricht die Erzeugung von optimalen Covering Arrays der Erzeugung von minimalen kombinatorischen Testmengen, was sich direkt in vermindertem Ressourcenaufwand fürs Testen widerspiegelt.

Die Erzeugung von Covering Arrays mit möglichst geringer Zeilenanzahl ist ein anspruchsvolles Problem und Gegenstand der aktuellen Forschung.

Für weitere Ressourcen und Literatur verweisen wir auf:

[0] NIST, Combinatorial Methods for Trust and Assurance, https://csrc.nist.gov/projects/automated-combinatorial-testing-for-soft…

[1] M. Grindal and J. Offutt, „Input parameter modeling for combination strategies“, https://www.academia.edu/download/44665754/ipmmodel.pdf

[2] L. Hu, et al., „How does combinatorial testing perform in the real world: An empirical study“, https://link.springer.com/article/10.1007/s10664-019-09799-2

[3] L. S. G. Ghandehari, et al. „Applying combinatorial testing to the Siemens suite“, https://doi.org/10.1109/ICSTW.2013.47

[4] J. Petke, et al., „Practical combinatorial interaction testing: Empirical findings on efficiency and early fault detection“, https://doi.org/10.1109/TSE.2015.2421279

[5] M. Bures and B. S. Ahmed, „On the effectiveness of combinatorial interaction testing: A case study“, https://doi.org/10.1109/QRS-C.2017.20

[6] D. Jarman, et al., „Applying combinatorial testing to large-scale data processing at Adobe“, https://doi.org/10.1109/ICSTW.2019.00051

[7] D. Kuhn, R. Kacker, and Y. Lei, “Introduction to Combinatorial Testing“, https://csrc.nist.gov/pubs/book/2013/06/introduction-to-combinatorial-t…

[8] C. J. Colbourn and J. H. Dinitz, “Handbook of Combinatorial Designs”, https://doi.org/10.1201/9781420010541

[9] L. Kampel and D. E. Simos, „A survey on the state of the art of complexity problems for covering arrays“, https://doi.org/10.1016/j.tcs.2019.10.019