Counting before you test: state spaces, covering arrays and combinatorial testing

A settings panel with ten switches, each on or off, describes 1,024 configurations. That number is not an estimate but the product of the values each switch can take, fixed the moment the panel is described, and the same arithmetic rules out exhaustive testing: 1,024 runs, each needing a checked result.

This unit argues that the size of a state space is a computable design fact. A covering array buys an exact guarantee at a chosen strength rather than evidence that no fault remains. NIST's tutorial covers every three-way combination of those ten settings in thirteen tests (Kuhn, Kacker and Lei, 2010), any three columns of its worked array containing all eight value triples a trio of switches can form. What that proves is exactly what the parameters and the strength say, so the value of the method is bounded by the reasoning that chose them. Unit 5 turns from counting combinations to the probability that a step fails.

The state space is a number you compute

Ostrand and Balcer (1988) turn a specification into a countable object: in their category-partition method an engineer analyses a specification into categories with sets of choices, then hands it to a generator with constraints suppressing impossible or redundant combinations, so the size of the test set is controlled by annotating the specification rather than by sampling after the fact.

A login dialog makes the count concrete. A username field takes an empty, a valid or an unknown entry; a password field takes the same three. A remember-me box is on or off, and a caps-lock warning is shown or hidden. The product is 3 times 3 times 2 times 2, or 36 configurations, fixed by the specification before a line of code exists. Drop the impossible pair of an empty username with a caps-lock warning, and the constraint has removed four rows.

A state space is a function of a model, so its count is only as honest as the categories, and a parameter left out of the analysis adds nothing to the product and nothing to the guarantee.

The product rule sizes the space, not the plan

The reversal at the centre of the unit is that the number which sizes the space is not the number which sizes the plan. Cohen, Dalal, Fredman and Patton (1997) built AETG, which generates test sets covering all pairwise, triple or n-way parameter combinations and grows logarithmically in the number of parameters. For twenty binary settings, exhaustive coverage is 2 to the 20, or 1,048,576 runs, while a pairwise set arrives at a few dozen rows.

Hartman and Raskin (2004) supply the combinatorial spine, surveying algorithms and bounds for small arrays that cover all t-way combinations and relate strength, parameters and tests. Their framing fixes what a strength is, a chosen t rather than a property of the system, so nothing in the mathematics says which t an interface needs and a strength is admissible evidence only for a claim the designer made about which interactions matter.

The case for a small strength rests on four systems

Support for stopping at small t comes from failure reports. Kuhn and Reilly (2002) examined error reports from a browser and a web server and found the number of conditions needed to trigger most failures small. Kuhn, Wallace and Gallo (2004) generalised it: failures across domains came from combinations of relatively few conditions, so if all faults depend on n or fewer parameters then testing all n-tuples is effectively exhaustive. The equivalence carries two conditions the authors state: behaviour must not depend on complex event sequences, and variables must take few discrete values.

Those conditions are exactly what an interface form tends to break. A checkout flow is a sequence of events, and a drag is not a small set of discrete values. Kuhn, Kacker and Lei (2010) name the pattern the interaction rule: single-factor faults and two-factor interactions dominate, and three-or-more-factor interactions are progressively rarer. Pairwise testing may miss between 10 and 40 per cent or more of faults, and three-way coverage may detect 90 per cent or more of bugs. In a NASA distributed database, the report's prose attributes 67, 93 and 98 per cent to one-, two- and three-way interactions.

The same report tabulates cumulative detection rates for four systems, and the columns do not move together:

• medical devices: 66, 93 and 96 per cent at one, two and three interactions;
• a browser: 40, 76 and 95 per cent;
• a web server: 29, 71 and 87 per cent;
• the NASA database: 68, 92 and 97 per cent (Kuhn, Kacker and Lei, 2010).

Three-way coverage detects 95 per cent of the browser's failures but 87 per cent of the web server's, so the strength that suffices is a property of the system. The report's prose also attributes 98 per cent of the NASA database's failures to three-way interactions, while its own table records 97 per cent: an inconsistency worth naming rather than smoothing.

An exact guarantee that stops at the strength you chose

The guarantee a strength buys is exact and narrow. In the ten-switch panel, the report's worked three-way array exercises all eight combinations of any three switches in thirteen tests, against 1,024 for exhaustive coverage (Kuhn, Kacker and Lei, 2010). That is the strongest form of the unit's claim, and also the weakest, because the quantifier stops at three. Thirteen rows cannot show the absence of a fault that needs four switches at once. The report adds that most parameters are continuous and must be discretised before an array can be built, a modelling decision that raising the strength cannot undo.

Coverage is a family of choices, not one guarantee

The choice of t sits inside a larger family. Nie and Leung (2011) classify the field into modelling, test-suite generation, constraints, failure diagnosis and prioritisation, which makes the strength one criterion among several rather than a measure of quality. They also name as open the models that mix continuous and discrete parameters, which is most real interfaces.

Raising the strength is not free, and the cost falls on the wrong side of the problem: La Chance and Halle (2023) investigate distributing the generation of combinatorial test suites across computing resources, and measure the time reduction for large models. What falls is the cost of generating the array, not of executing the tests, so a stronger guarantee buys a more expensive model rather than a longer test run and the reasoning that picks t is the real constraint.

An array earns its keep when it localises the fault

An array can also locate a fault, not only detect it. Yilmaz, Cohen and Porter (2006) target option-related faults that appear only when configuration settings take particular values. They use covering arrays to detect those faults and characterise the subspaces in which they occur. A fault that shows up only when the interface language is Japanese and the theme is dark is reported as that pair of options rather than as a whole configuration, which raises the bar on the model: characterisation is only as good as the parameters it is computed over. The array is also a statement about whose use it covers: the locale that surfaced Yilmaz, Cohen and Porter's fault is a parameter like any other, and so are text scaling, input method, assistive technology and connection quality.

Contested question: is the interaction rule a law or a sample?

The literature disagrees about how far the rule travels, and the disagreement is about evidence rather than arithmetic. Kuhn and Reilly (2002), Kuhn, Wallace and Gallo (2004) and the NIST tutorial (Kuhn, Kacker and Lei, 2010) hold that few-way interactions dominate and that a small strength is a sound default, on the evidence of failure reports from four systems: a browser, a web server, a medical device and a distributed database. The opposing reading is not that the arithmetic is wrong. It is that the sample is small and the systems old, and that a regularity in them is being asked to hold as a law.

Neither side carries the evidence a clinician would want. The supporting side is three reports and a tutorial from one small group of authors, none a preregistered test of the rule; the opposing side is one method stretched to a system whose parameters do not mean what the rule assumes, and one review of a compensating technique rarely evaluated at scale.

Two lines of work make the objection concrete. Ma, Juefei-Xu, Xue, Li and Li (2019) adapt combinatorial testing to deep learning, where the input space is high-dimensional and the latent features large. They test combinations of neurons to expose robustness problems, but their parameters are not independently meaningful in the way a settings switch is, which is the first condition Kuhn, Wallace and Gallo attached to the equivalence. Vilkomir (2016) reviews combinatorial testing for binary inputs in avionics and nuclear power: evidence of adoption rather than of the rule's generality.

The second objection concerns what a small strength costs in a project. Abdul Manan, Abang Jawawi, Ahmad and others (2021) review prioritisation in combinatorial testing, arguing that a small t weakens fault detection and that the techniques proposed to compensate are far more often proposed than evaluated on real systems. A plan can cover its strength exactly and still spend its budget on rows that find nothing: coverage is guaranteed, fault-finding is not.

What would settle it is a study that is not another single-system report. The rule would be tested by preregistering a domain-stratified set of systems whose complete fault lists are known, recording for each fault the smallest number of parameters that triggers it and reporting the distribution alongside the two assumptions the equivalence needs. If the tail moves with the domain and with the presence of event sequences, the rule is a regularity of the sampled systems rather than a law. A second study is needed for the prioritisation question: apply the proposed orderings to systems with a known fault list and report detection at a fixed budget.

Meanwhile, set the strength from the parameter list rather than from habit: use two-way coverage as a floor, raise it where a parameter encodes a sequence or a continuous quantity, and publish the strength beside the parameter list.

Where the argument is heading

The direction of travel is to make the array a bounded instrument rather than a certificate. The models that mix continuous and discrete parameters are where the counting has to be extended, and Ma and colleagues show the method stretched to systems whose parameters do not mean what the rule assumes. Distributing generation makes higher strengths affordable, which sharpens rather than settles the question of which strength a design deserves (La Chance and Halle, 2023). The thesis holds for as long as the parameter list is treated as a design claim rather than a clerical one.

The sources this unit rests on

• Ostrand, T. J. and Balcer, M. J. (1988). The category-partition method for specifying and generating functional tests. Communications of the ACM, 31(6), 676-686. doi:10.1145/62959.62964 Turns a specification into categories and choices and generates tests from it, with constraints suppressing impossible combinations; the test-set size follows from the specification rather than from sampling.
• Cohen, D. M., Dalal, S. R., Fredman, M. L. and Patton, G. C. (1997). The AETG system: an approach to testing based on combinatorial design. IEEE Transactions on Software Engineering, 23(7), 437-444. doi:10.1109/32.605761 Describes AETG, whose test sets grow logarithmically in the parameter count while covering all pairwise to n-way combinations. The product rule does not size the plan.
• Kuhn, D. R. and Reilly, M. J. (2002). An investigation of the applicability of design of experiments to software testing. Proceedings of the 27th Annual NASA Goddard/IEEE Software Engineering Workshop. doi:10.1109/SEW.2002.1199454 Examines browser and web-server error reports and finds that most failures need few conditions. The first empirical account of the interaction rule.
• Kuhn, D. R., Wallace, D. R. and Gallo, A. M. (2004). Software fault interactions and implications for software testing. IEEE Transactions on Software Engineering, 30(6), 418-421. doi:10.1109/TSE.2004.24 Shows that failures came from relatively few conditions, so n-tuple testing is effectively exhaustive if faults depend on n or fewer parameters. It states the two assumptions an interface form tends to break.
• Hartman, A. and Raskin, L. (2004). Problems and algorithms for covering arrays. Discrete Mathematics, 284(1-3), 149-156. doi:10.1016/j.disc.2003.11.029 Surveys algorithms and bounds for covering arrays that cover all t-way combinations: the mathematical spine of the unit.
• Yilmaz, C., Cohen, M. B. and Porter, A. A. (2006). Covering arrays for efficient fault characterization in complex configuration spaces. IEEE Transactions on Software Engineering, 32(1), 20-34. doi:10.1109/TSE.2006.8 Targets option-related faults, using covering arrays to detect them and to characterise their subspaces. It moves the argument from detection to diagnosis.
• Kuhn, D. R., Kacker, R. N. and Lei, Y. (2010). Practical combinatorial testing. NIST Special Publication 800-142. doi:10.6028/NIST.SP.800-142 Defines the covering array, covering ten binary settings in thirteen tests against 1,024 configurations, and gives the interaction rule and the four-system detection table.
• Nie, C. and Leung, H. (2011). A survey of combinatorial testing. ACM Computing Surveys, 43(2), 1-29. doi:10.1145/1883612.1883618 Classifies the field and names the open problem of models that mix continuous and discrete parameters.
• Vilkomir, S. (2016). Combinatorial testing of software with binary inputs: a state-of-the-art review. Proceedings of the IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C). doi:10.1109/QRS-C.2016.12 Reviews binary-input testing for safety-critical systems including avionics and nuclear power.
• Ma, L., Juefei-Xu, F., Xue, M., Li, B. and Li, L. (2019). DeepCT: tomographic combinatorial testing for deep learning systems. Proceedings of the IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER). doi:10.1109/SANER.2019.8668044 Adapts combinatorial testing to deep learning, where the parameters are not independently meaningful.
• Abdul Manan, M. S., Abang Jawawi, D. N., Ahmad, J. and others (2021). A systematic literature review on test case prioritization in combinatorial testing. Proceedings of the 5th International Conference on Algorithms, Computing and Systems (ICACS). doi:10.1145/3490700.3490710 Argues that a small strength weakens detection and reports that prioritisation is proposed far more often than evaluated.
• La Chance, E. and Halle, S. (2023). An investigation of distributed computing for combinatorial testing. Software Testing, Verification and Reliability, 33(4). doi:10.1002/stvr.1842 Distributes the generation of combinatorial suites across computing resources; only generation, not test execution, is reduced.