# Combinatorial and pairwise testing

Combinatorial testing checks every combination of any two parameter
values with a small set of test rows, rather than the full product of
every option. That set is a *covering array*, and its general form
guarantees that **every combination of any *t* parameters appears at
least once**: at interaction strength *t = 2* — *pairwise* testing —
every pair of parameter values is covered, at *t = 3* every triple. The
array replaces full enumeration: a system with ten on/off options has
$2^{10} = 1024$ configurations,
twenty options a million. Testing every combination is infeasible;
testing none of the interactions misses the bug that appears only when
option A *and* option B are both set.

The covering array is generated, not enumerated by hand, and the tester
still supplies an oracle for each row.

## What it catches

- **Interaction faults.** Defects that surface only under a specific
  combination of parameter values — a codec that fails only when
  *hardware decode* is on *and* the input is interlaced, a form that
  rejects valid data only for one locale–currency pair.
- **Configuration and compatibility bugs.** Browser × OS × resolution
  matrices, feature-flag combinations, driver/firmware pairings.
- **Holes a hand-written matrix missed.** A covering array is complete
  to strength *t* by construction; an author's ad-hoc selection has no
  such guarantee and usually skips the unglamorous pairs.

What it does **not** catch: faults that need *more* than *t*
interacting parameters (raise *t*, at rising cost); faults tied to a
specific *value* outside the set the tester modeled (combinatorial
testing covers the modeled values, not the whole domain — pair it
with [boundary-value choices](https://quality.stereobooster.com/example-tests.md)); and, as with any
input-selection method, anything its oracle doesn't check. A parameter
the model omits is invisible to the array.

## The interaction rule

Across fault studies in several domains — medical devices, a browser,
an HTTP server, a NASA database — (Kuhn et al. 2004)[^kuhn2004] found that failures were
triggered by combinations of relatively *few* parameters: most by one
or two, and essentially all by six or fewer.

The implication is the method's whole case: if every fault is
triggered by at most *t* parameters, then a t-way covering array is
*effectively* exhaustive — it provokes every fault a full Cartesian
sweep would, at a tiny fraction of the cost. Pairwise (*t = 2*)
already covers the bulk; *t = 4* to *6* approaches the empirical
ceiling. This is an observed regularity, not a theorem: a system whose
faults need a seven-way interaction will not be covered by a six-way
array.

## The t-way subsumption ladder

Interaction strength is a containment order. A t-way covering array
also covers every $(t-1)$-way combination, so

$$
\text{each-choice (1-way)} \sqsubset \text{pairwise (2-way)} \sqsubset \text{3-way} \sqsubset \cdots \sqsubset \text{exhaustive}
$$

The ladder is bounded above by the full Cartesian product — the same
*exhaustive-within-a-bound* shape the
[guarantee axis](https://quality.stereobooster.com/guarantee.md) gives to
[bounded-exhaustive enumeration](https://quality.stereobooster.com/property-based-testing.md) and bounded
[model checking](https://quality.stereobooster.com/model-checking.md). Raising *t* climbs the
ladder toward a stronger guarantee at a higher row count; the array
size grows roughly logarithmically in the number of parameters but
sharply in *t*, which is why most practice stops at two or three.

## Tools

- **[ACTS](https://csrc.nist.gov/projects/automated-combinatorial-testing-for-software)** (NIST) — the reference generator; supports
  constraints (forbidden combinations), variable-strength arrays, and
  combinatorial *coverage measurement* of an existing suite. Free,
  Java, with a GUI and CLI.
- **[PICT](https://github.com/microsoft/pict)** (Microsoft) — open-source command-line
  generator; compact model syntax, constraints, seeding, and
  sub-model weighting.
- **[CAgen](https://matris.sba-research.org/tools/cagen/)** — a fast covering-array generator for high
  strengths and large models, available as a web tool and CLI.
- **Language libraries:** [allpairspy](https://github.com/thombashi/allpairspy) (Python),
  [jqwik](https://jqwik.net/)'s `@Combinatorial` and table-based generation
  (Java), [tcases](https://github.com/Cornutum/tcases) (model-based, JSON/YAML). Most build
  pairwise arrays inline so the combinations live next to the test.

The practical differentiator is **constraint support**: real
configuration spaces forbid combinations (a feature that exists only
on one platform), and a generator that can exclude them avoids wasting
rows on impossible inputs.

## When to use, when not

**Use:**

- Large configuration, compatibility, or feature-flag spaces where the
  full product is intractable but interactions matter.
- API and function parameters with several discrete options each.
- Software product lines and variability models, where ACTS-style
  constrained generation is the standard tool.

**Don't:**

- When parameters genuinely don't interact — independent options are
  better covered one at a time.
- When the fault is value-specific rather than combination-specific —
  an off-by-one at a numeric boundary is a job for
  [boundary-value example tests](https://quality.stereobooster.com/example-tests.md), not a covering
  array over coarse value classes.
- As a source of oracles. Combinatorial testing chooses *inputs*;
  pair it with a real oracle (expected outputs, invariants, or at
  least a crash check).

## Combinatorial coverage and fault localization

Two adjacent uses fall out of the same model. **Combinatorial coverage
measurement** runs the covering-array construction in reverse: given an
existing suite, measure what fraction of all t-way combinations it
already exercises — a gap-finder for hand-written suites, reported by
ACTS. **Fault localization** exploits the array's structure after a
failure: because each combination's coverage is known, the rows that
pass and fail narrow down which parameter interaction is responsible.

## Evidence

- **The interaction-rule studies.** Across multiple application
  domains, observed failures were triggered by few interacting
  parameters, with none exceeding six (Kuhn et al. 2004)[^kuhn2004]. The sample is
  specific, if varied, so the result is a regularity rather than a
  guarantee that holds for every system.

## Further reading

- **The NIST practitioner guidance** (Kuhn et al. 2010)[^kuhn2010] collects the
  generation algorithms, constraint handling, coverage measurement,
  and worked case studies; it is the standard reference for applying
  the method and the source of the ACTS tooling.
- Combinatorial testing's place among automated test-generation
  methodologies is cataloged in the standard survey (Anand et al. 2013)[^anand2013].

## Related

**Exhaustive enumeration of a bounded input space, compressed several ways**

These methods all exhaustively enumerate a bounded input space; each compresses
the exponential blow-up a different way. [Decision
tables](https://quality.stereobooster.com/decision-tables.md) compress *losslessly*: a "don't-care"
entry folds together combinations that share an outcome, so every case still
maps to one rule, and the row carries its own expected decision. Combinatorial
and pairwise testing *sample*: a
covering array keeps every *t*-way interaction and drops the higher-order ones,
with the oracle supplied separately. [Bounded-exhaustive property
testing](https://quality.stereobooster.com/property-based-testing.md) *bounds the size*: it
enumerates every value up to a depth/size *k* (SmallCheck), relying on the
small-scope hypothesis that faults surface small. [Exhaustive
coverage](https://quality.stereobooster.com/exhaustive-coverage.md) runs from MCC (the full 2ⁿ
truth table) down to MC/DC's *n*+1 independence criterion, and audits an
existing suite rather than generating one. Type systems reach the same
completeness by construction: an exhaustiveness check on a `match` / `switch`
over a sum type has the compiler verify every variant is handled, with no case
written by hand. State-, path-, and schedule-space
enumerators such as model checking, symbolic execution, and systematic
concurrency testing share the idea over a different space; see the reachability
clusters.

**Generative testing**

These methods blur together because they all run the code and check the result
without a hand-written expected value. Two roles pull them apart, and a single test
picks one of each.

**Input generators** choose the input, and differ by the steering signal (the
Generative subtree of the [input axis](https://quality.stereobooster.com/input.md)):

- Random: [property-based testing](https://quality.stereobooster.com/property-based-testing.md) samples
  from a generator or schema.
- Coverage feedback: [fuzzing](https://quality.stereobooster.com/fuzzing.md) mutates inputs steered by
  coverage (raw bytes); [automated test generation](https://quality.stereobooster.com/automated-test-generation.md)
  runs the same feedback loop as a fitness-guided search over structured call sequences.
- Solver: [symbolic execution](https://quality.stereobooster.com/symbolic-execution.md) derives an input
  that reaches a chosen path.
- Systematic: combinatorial testing builds a
  covering array over every t-way combination.

**Oracle suppliers** provide the verdict when no expected value is written:

- [Metamorphic testing](https://quality.stereobooster.com/metamorphic-testing.md) checks a relation between
  the outputs of two related inputs.
- [Differential testing](https://quality.stereobooster.com/differential-testing.md) compares against a
  trusted second implementation.

Pick one generator and one oracle: they compose. A coverage-guided fuzzer that checks a
metamorphic relation is fuzzing and metamorphic at once. (The written-answer end, where
the author picks rows and answers by hand, is [example / parameterized
tests](https://quality.stereobooster.com/example-tests.md).)

## Classification

- **Quality dimensions:** Functionality, Reliability, Security (security-configuration interaction faults).
- **Area:** Configuration spaces, feature-flag and compatibility matrices, API parameter combinations, product-line variability — anywhere interaction faults hide in combinations no one enumerated by hand.
- **Guarantee:** Exhaustive within the interaction strength *t* — every t-way combination is covered; higher-order interactions are not.

## Referenced by

- [Measuring test-suite effectiveness](https://quality.stereobooster.com/measuring-test-effectiveness.md) · Methods
- [Testing GUI and mobile applications](https://quality.stereobooster.com/testing-gui-and-mobile-apps.md) · Methods
- [Testing autonomous and cyber-physical systems](https://quality.stereobooster.com/testing-autonomous-systems.md) · Methods
- [Choosing methods](https://quality.stereobooster.com/choosing.md) · Overview

## References

[^kuhn2004]: Kuhn, D. Richard, Dolores R. Wallace, and Albert M. Gallo. 2004. "[Software Fault Interactions and Implications for Software Testing](https://csrc.nist.rip/groups/SNS/acts/documents/TSE-0172-1003-1.pdf)." *IEEE Transactions on Software Engineering* 30 (6): 418–21. <https://doi.org/10.1109/TSE.2004.24>.
[^kuhn2010]: Kuhn, D. Richard, Raghu N. Kacker, and Yu Lei. 2010. *[Practical Combinatorial Testing](https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-142.pdf)*. NIST Special Publication 800-142. National Institute of Standards; Technology. <https://doi.org/10.6028/NIST.SP.800-142>.
[^anand2013]: Anand, Saswat, Edmund K. Burke, Tsong Yueh Chen, et al. 2013. "[An Orchestrated Survey of Methodologies for Automated Software Test Case Generation](https://romisatriawahono.net/lecture/rm/survey/software%20engineering/Software%20Testing/Anand%20-%20Automated%20Software%20Test%20Case%20generation%20-%202013.pdf)." *Journal of Systems and Software* 86 (8): 1978–2001. <https://doi.org/10.1016/j.jss.2013.02.061>.

## Acronyms

- MC/DC — modified condition/decision coverage
- MCC — multiple-condition coverage