Home / Concepts / Covering Arrays
Covering Arrays¶
A covering array is a test matrix that guarantees every t-way combination of parameter values appears in at least one test case.
The Problem¶
When testing a system with multiple parameters, the number of possible combinations grows exponentially. For example:
| Parameters | Values Each | Total Combinations |
|---|---|---|
| 3 | 3 | 27 |
| 5 | 4 | 1,024 |
| 10 | 3 | 59,049 |
| 15 | 4 | 1,073,741,824 |
Exhaustive testing quickly becomes impractical.
The Solution¶
Research shows that most software failures are triggered by interactions between 2 to 6 parameters, not by specific values of a single parameter. A covering array exploits this by guaranteeing that every combination of t parameter values appears at least once — where t (the "strength" or "order") is typically 2 (pairwise) to 6.
Example¶
With 5 parameters of 3 values each:
- Exhaustive: 243 test cases
- Pairwise (t=2): 11 test cases
- 3-way (t=3): 37 test cases
That's a 95% reduction for pairwise and 85% for 3-way, while still covering all interactions at that strength.
Interaction Strength¶
The order (or strength) determines how many parameters are considered simultaneously:
| Order | Name | Covers |
|---|---|---|
| 1 | Each-choice | Every value appears at least once |
| 2 | Pairwise | Every pair of values |
| 3 | 3-way | Every triple of values |
| 4-6 | Higher-order | Every 4/5/6-way combination |
Higher orders provide stronger coverage but require more test cases. Pairwise (order 2) is the most common and is ProTest's default.
Research Foundation¶
NIST research spanning 1999-2004 examined software failures across multiple domains and found that most software bugs and failures are caused by one or two parameters, with progressively fewer by three or more. The maximum interaction degree observed in real-world faults was six — meaning that testing all combinations up to 6-way interactions can be as effective as exhaustive testing.
Key studies:
- Kuhn, D.R., Wallace, D.R., and Gallo Jr, A.M. (2004) — "Software fault interactions and implications for software testing." IEEE Transactions on Software Engineering, 30(6), pp. 418-421.
- Kuhn, D.R. and Reilly, M.J. (2002) — "An investigation of the applicability of design of experiments to software testing." 27th Annual NASA Software Engineering Workshop, pp. 91-95.
- Wallace, D.R. and Kuhn, D.R. (2001) — "Failure Modes in Medical Device Software: an Analysis of 15 Years of Recall Data." International Journal of Reliability, Quality and Safety Engineering, vol. 8, no. 4.
For more information, see NIST: Combinatorial Methods in Testing and NIST SP 800-142: Practical Combinatorial Testing.
How ProTest Generates Covering Arrays¶
ProTest supports two generation engines:
- PICT — Microsoft's Pairwise Independent Combinatorial Testing engine. Uses a greedy algorithm that builds the covering array one row at a time. Generally better for higher interaction strengths (t=3 and above), where its greedy approach is highly effective.
- SIPO — Based on the heuristically enhanced IPO algorithm described in Wagner, Kampel & Simos (2021), "Heuristically Enhanced IPO Algorithms for Covering Array Generation" (IWOCA 2021, LNCS 12757, pp. 571-586). SIPO enhances the classic In-Parameter-Order strategy by injecting simulated annealing improvement steps during construction. Generally better for pairwise (t=2) coverage, where it often produces fewer test cases than PICT.
Both guarantee the same coverage; they differ in the size of the resulting test suite and generation time.