Constrained Combinatorial Testing

Definition

Constrained Combinatorial Testing (CCT) is an extension of Combinatorial Testing (CT) that adds explicit constraint handling to the generation of test suites. It is designed for configurable systems in which certain combinations of configuration options are invalid and therefore cannot be exercised. CCT augments strength-t CT with hard constraints (which must always be satisfied) and soft constraints (whose violations should be minimized). As a consequence, CCT can both exclude invalid tuples that cannot be executed and minimize undesirable tuples that are technically executable but problematic in practice ^[1].

Because CCT inherits the combinatorial interaction coverage objective of CT, it is one of the most widely studied CT extensions and has been the subject of extensive surveys covering techniques and applications across many years of literature [arxiv:1908.02480v1].

Formal Model: Constrained Mixed-level Covering Arrays

A CCT test suite is represented as a Constrained Mixed-level Covering Array (CMCA). A CMCA of size N is written as CMCA(t, k, (v₁, ..., vₖ), C) where ^[2]:

t — interaction strength (the number of parameters combined in each tested tuple);
k — number of parameters (configuration options);
vⱼ — number of values for parameter j;
C — a Boolean constraint formula in Conjunctive Normal Form (CNF), with each clause being a disjunction of positive literals pos(j, d) (parameter j takes value d) and negative literals neg(j, d) (parameter j does not take value d).

A CMCA must satisfy:

Each cell aᵢⱼ belongs to the value domain of parameter j.
Domain constraints — every row satisfies the constraint C. Rows are thus valid configurations only.
Coverage constraints — in every N × t sub-array, every valid t-tuple (e.g., every valid pair when t = 2) that itself satisfies C appears at least once. Tuples that violate C are excluded from the coverage requirement.

A CMCA is optimal when N is the smallest size for which a CMCA satisfying both domain and coverage constraints exists. A t-tuple is called valid if it satisfies C and invalid otherwise.

Worked Example

A simplified mobile-phone product line with five configuration options (Display, Email, Camera, Video, Ringtones) illustrates the concepts ^[2]:

Display: {16MC, 8MC, BW}
Email: {GV, TV, None}
Camera: {2MP, 1MP, None}
Video: {Yes, No}
Ringtones: {Yes, No}

Seven CNF-style constraints apply, including rules such as "graphical email viewer requires color display", "2 megapixel camera requires a color display", and prohibitions such as "graphical email viewer not supported with the 2 megapixel camera".

While exhaustive testing would require 2² × 3³ = 108 configurations and constraint filtering still leaves 31 valid configurations, strength-2 CCT finds an optimal test suite of only 9 test cases that covers every valid pair interaction, including all 7 valid pairs in the (Email, Camera) interaction while excluding invalid pairs such as (GV, 2MP) and (TV, 2MP) ^[2].

Why CCT Is Difficult

Generating optimal CCT test suites is computationally hard. The literature identifies several families of solution methods, each with trade-offs ^[1]:

Method	Strength	Weakness
Greedy algorithms	Fast test-suite generation	Cannot guarantee optimality
Metaheuristic algorithms	Can produce smaller suites than greedy	Higher run-time; no optimality guarantee
SAT-based complete methods	Guaranteed optimality	Expensive to implement a dedicated CCT-to-SAT encoder

Most practical implementations rely on off-the-shelf constraint solvers (SAT, Pseudo-Boolean, CSP) as back-ends to check whether candidate test cases satisfy constraints and to pre-compute valid tuples ^[1]. Few systems, however, simultaneously support soft constraints and limited computational resources (bound on number of test cases or time).

Answer Set Programming Approach: catnap

The catnap system is an Answer Set Programming (ASP) implementation of CCT solving. It accepts a CCT instance in ASP fact format, combines it with a first-order ASP encoding, and delegates the resulting program to an off-the-shelf ASP solver such as clingo ^[1].

The catnap encoding has three distinguishing features ^[1]:

A series of compact ASP encodings for CCT.
An easy extension for CCT under limiting resources.
An easy extension of CCT with soft constraints.

Basic Encoding

The basic encoding generates optimal strength-2 CMCA instances using activation atoms activated(R) for each candidate row R and minimizes the number of activated rows via a #minimize directive ^[3]. Domain constraints are enforced through hard rules (using negative constraints :‑) that forbid assignments violating any clause of C, and coverage is enforced by requiring each valid pair pair(I,J,A,B) to be covered by some assigned row.

Weakened Encoding: Weak Coverage Constraints

When the initial bound on the number of rows is smaller than the minimum optimal CMCA size, the basic encoding cannot produce any test suite because hard coverage constraints become unsatisfiable. catnap addresses this by switching coverage constraints from hard to soft (called weak coverage constraints) ^[3]:

Each covered pair covered(I,J,A,B) is generated when a pair assignment is present.
A #maximize directive maximizes the number of covered pairs.
Multi-criteria lexicographic optimization prioritizes size (minimize) before coverage (maximize), using priority levels size and coverage with size < coverage by default.

This yields two practical benefits ^[3]:

When n is below the minimum feasible size, the weakened encoding still returns a test suite with maximum coverage under the limited budget.
When n is sufficient, it returns an optimal CMCA.
It avoids the expensive pre-calculation of valid pairs that many existing implementations require.

Conceptually, weak coverage constraints complement prioritized CT, which orders or re-orders test cases for earlier failure detection.

Extension with Soft Constraints

The encoding framework extends naturally to soft constraints, where constraint violations contribute to a minimization criterion alongside coverage and size objectives ^[3].

Survey Perspective

A 2019 survey of CCT [arxiv:1908.02480v1] reviewed 129 papers published between 1987 and 2018, covering representations, influences, and techniques for handling constraints in CT. It categorized constraint-handling techniques and surveyed comparatively under-studied areas such as constraint identification and constraint maintenance, motivated by the observation that real-world programs are almost always constrained.

Related Concepts and Tools

catnap — An ASP-based CCT test-suite generator described in the LPNMR 2017 paper "catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming" by Banbara et al. It implements CCT using Answer Set Programming encodings and is evaluated empirically against dedicated implementations ^[1].
ASP encoding for strength-2 CCT solving with weak coverage constraints — A specific CodeArtifact implementing the weakened-encoding variant that handles resource-bounded CCT instances by switching coverage constraints from hard to soft ^[3].
Combinatorial Testing (CT) — The parent technique that CCT extends with constraint handling [arxiv:1908.02480v1].