Skip to content
STIMSMITH

Combinatorial Testing

Concept WIKI v1 · 7/7/2026

Combinatorial Testing (CT) is a black-box software testing technique that systematically exercises interactions among a small number of configuration options (parameters) to detect elusive failures, while avoiding the combinatorial explosion of exhaustive testing. Core CT constructs include covering arrays parameterized by interaction strength t and per-parameter value counts; practical systems often require Constrained Combinatorial Testing (CCT) to exclude or penalize invalid tuples via hard and soft constraints, with solvers ranging from greedy and metaheuristic algorithms to SAT, PB, CSP, and Answer Set Programming (ASP) encodings.

Combinatorial Testing

Definition and Motivation

Combinatorial Testing (CT) is a black-box testing technique aimed at detecting elusive failures in software systems whose configuration spaces are too large to exhaustively test. CT rests on the empirical observation that most faults are triggered by interactions among a small number of configuration options (parameters). Rather than enumerate every possible combination, CT systematically exercises t-way interactions among parameters, producing test suites that are much smaller than exhaustive ones yet more effective than random testing [1].

The typical topics in software testing include model-based testing, combinatorial testing, security testing, and domain-specific testing, and CT is one of the most widely studied techniques in this area [1].

Core Formalism: Covering Arrays

The central combinatorial object in CT is the Covering Array (CA). A covering array of strength t over k parameters with v_j values for parameter j is written CA(t, k, (v_1, ..., v_k)) and guarantees that every t-tuple of parameter values appears in at least one row (test case) of the array. Strength-t CT thus tests all t-tuples of configuration options in a systematic way [1].

Constrained Combinatorial Testing (CCT)

Real-world configurable systems frequently contain constraints between specific configuration options that make certain combinations invalid or undesirable. Constrained Combinatorial Testing (CCT) extends CT with constraint handling and is one of the most widely studied CT techniques in recent years [1].

CCT distinguishes between:

  • Hard constraints — must be strictly satisfied; their violation renders a test case infeasible.
  • Soft constraints — need not be satisfied, but the overall number of violations across the test suite should be minimized.

The objective of generating an optimal (smallest) CCT test suite is to find a Constrained Mixed-level Covering Array (CMCA), written CMCA(t, k, (v_1, ..., v_k), C), which extends a covering array with a constraint C expressed as a Boolean formula in Conjunctive Normal Form (CNF) [2].

A canonical motivating example is a mobile phone product line with parameters such as display type (16 Million Colors, 8 Million Colors, Black and White), email viewer (Graphical, Text, None), camera (2 Megapixels, 1 Megapixel, None), video camera, and video ringtones. Constraints in this domain include requirements such as a Graphical email viewer requiring a color display, a 2 Megapixel camera requiring a color display, and certain combinations (e.g., 16 Million colors + Text + 2 Megapixel camera) being unsupported [2].

Solving Techniques for CCT

Generating optimal CCT test suites is known to be a difficult problem, and several solution strategies have been pursued [1]:

  • Greedy algorithms — quickly produce test suites but cannot guarantee optimality.
  • Metaheuristics-based algorithms — can produce smaller suites by investing more search time, but also lack optimality guarantees.
  • Satisfiability Testing (SAT) — complete methods that can guarantee optimality, but require a dedicated encoder from CCT instances into SAT.
  • Constraint-solver back-ends — most methods delegate constraint checking to off-the-shelf solvers, including SAT, PB (Pseudo-Boolean), and CSP (Constraint Satisfaction Problem) solvers, both to verify that each candidate test case satisfies the constraints during generation and to compute valid tuples during preprocessing [1].

Each class has trade-offs: greedy methods are fast, metaheuristics can improve quality with more time, and complete methods give optimality at higher computational cost [1].

ASP-Based CCT Generation (catnap)

An alternative approach uses Answer Set Programming (ASP). The catnap system accepts a CCT instance in a fact format and combines it with a first-order ASP encoding for CCT solving, which is then solved by an off-the-shelf ASP system (such as clingo) [2]. This high-level approach benefits from:

  • An expressive modeling language.
  • Extensible encodings.
  • Flexible multi-criteria optimization.

The catnap encoding provides (a) a series of compact ASP encodings, (b) easy extension for CCT under limiting resources (the number of test cases, time, etc.), and (c) easy extension of CCT with soft constraints [2]. The approach has been empirically contrasted with dedicated implementations of CCT solving techniques [2].

CT for Deep Learning Systems

Beyond traditional configurable software, CT has been explored for testing deep learning (DL) systems. The challenge is that DL systems have an enormous runtime state space when each neuron is treated as a state, making exhaustive testing infeasible. CT has been adapted to propose coverage criteria for DL systems along with a CT-coverage-guided test generation technique. Empirical evaluation suggests CT is a promising avenue for testing DL systems, while leaving open questions and directions for future work [arxiv 1806.07723].

Open Challenges in CCT

A central open challenge is developing a universal CCT solver that can efficiently generate optimal test suites as well as suboptimal ones for CCT instances having a wide range of hard and soft constraints, even when resources are limited [1]. Additionally, survey work covering 129 papers between 1987 and 2018 highlights that constraint handling, identification, and maintenance remain important, comparatively less well-studied areas despite the prevalence of constrained problem domains in real-world programs [arxiv 1908.02480].

Summary

CT reduces the testing effort required for highly configurable systems by exploiting the empirical regularity that faults involve few-way interactions. When constraints are present, CCT extends CT with hard and soft constraint handling, using CMCA as its principal formalism and a variety of solving techniques — from greedy and metaheuristic methods to SAT, PB, CSP, and ASP encodings — to produce feasible and near-optimal test suites.

LINKED ENTITIES

1 links
Constrained Combinatorial Testing EXTENDS

CITATIONS

8 sources
8 citations
[1] CT is a black-box testing technique that detects elusive failures by systematically testing t-tuples of configuration options, producing much smaller test suites than exhaustive testing and more effective ones than random testing. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[2] Constrained Combinatorial Testing (CCT) extends CT with hard and soft constraints on configuration options and is one of the most widely studied CT techniques. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[3] Generating a CCT test suite is to find a Constrained Mixed-level Covering Array (CMCA), an extension of a covering array with constraints expressed as a Boolean formula in CNF. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[4] CCT solving techniques include greedy algorithms, metaheuristics-based algorithms, SAT-based complete methods, and off-the-shelf constraint solvers (SAT, PB, CSP) used as back-ends. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[5] catnap encodes CCT instances as first-order ASP and solves them with off-the-shelf ASP systems such as clingo, providing compact encodings and easy extension with limiting resources and soft constraints. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[6] Developing a universal CCT solver that efficiently generates optimal and suboptimal suites under hard and soft constraints with limited resources remains challenging. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[7] Adapting CT to deep learning systems proposes coverage criteria and CT-coverage-guided test generation as a promising approach for testing DL robustness, despite the huge neuron-level state space. Combinatorial Testing for Deep Learning Systems
[8] A comprehensive survey of constrained combinatorial testing covers 129 papers from 1987 to 2018, categorizing constraint handling, identification, and maintenance techniques for constrained problem domains. A Survey of Constrained Combinatorial Testing