Constrained Mixed Covering Array (CMCA)

Definition

A Constrained Mixed Covering Array (CMCA) is an extension of a Covering Array with constraints. A CMCA of size N is an N × k array A = (a_ij), written as:

CMCA(t, k, (v1, . . . , vk), C)

where:

t is the strength of the interaction coverage.
k is the number of parameters.
v_j is the number of values for each parameter j (1 ≤ j ≤ k).
C is a constraint given as a Boolean formula in Conjunctive Normal Form (CNF).

The CNF constraint formula C has the form:

C = ∧_{1≤ℓ≤h} ( ∨_{1≤m≤m_ℓ} pos(j_{m_ℓ}, d'_m)  ∨  ∨_{m_ℓ+1≤n≤n_ℓ} neg(j_{n_ℓ}, d'_n) )

Each constraint clause identified by ℓ (1 ≤ ℓ ≤ h) is a disjunction of pos/2 and neg/2 predicates:

pos(j, d) expresses that parameter j has value d.
neg(j, d) expresses its negation.

The constants n_ℓ and m_ℓ (n_ℓ ≥ m_ℓ ≥ 1) denote the number of both types of atoms and pos atoms respectively, for each clause ℓ.

Required Properties

A CMCA must satisfy the following properties:

Domain constraints: Every row r (1 ≤ r ≤ N) must satisfy the constraint C:

∧_{1≤r≤N, 1≤ℓ≤h} ( ∨_{1≤m≤m_ℓ} (a_{r, j_{m_ℓ}} = d'_m)  ∨  ∨_{m_ℓ+1≤n≤n_ℓ} ¬(a_{r, j_{n_ℓ}} = d'_n) )

Value range: a_ij ∈ {0, 1, 2, …, v_j − 1}.
Coverage constraints: In every N × t sub-array, all possible t-tuples (pairs when t = 2) that satisfy the constraint C must occur at least once.

A CMCA of size N is optimal if N is the smallest n such that a CMCA of size n exists.

A t-tuple is called a valid t-tuple if it satisfies the constraint C; otherwise, it is invalid.

In the standard definition, the constraint C is a hard constraint, and there are no soft constraints.

Illustrative Example (from Banbara et al., 2017)

The authors illustrate CMCA using a simplified software product line of mobile phones with five configuration options (Display, Email, Camera, Video, Ringtones). Three options have three values; two options have two values (Yes/No). Seven constraints restrict valid configurations (for instance, the pair (GV, 2MP) is forbidden in the interaction of Email and Camera). Exhaustive testing of the unconstrained product line would require 2² × 3³ = 108 test cases; the domain constraints reduce this to 31 valid configurations.

The article presents an optimal test suite of strength-2 CCT for this product line, which is an optimal CMCA(2, 5, 3322, C) of size 9, satisfying all eight constraint clauses shown in the paper. The optimal array contains 67 pairs in total across all parameter interactions; 57 of these are valid, and 10 are invalid. Some invalid pairs (such as (BW, Yes) in the interaction of Display × Ringtones) are implicit, derived from combinations of clauses and the requirement that each parameter must have exactly one value, which makes manual enumeration of all valid (or invalid) pairs difficult.

ASP (Answer Set Programming) Encoding for CMCA Finding

The catnap system models CMCAs using ASP. Below is the encoding structure for strength-2 CMCA finding (Listing 2 in the paper).

Fact Format

Facts express the parameter values and constraints of a CMCA instance:

p(j, d) — parameter j can take value d.
c(ID, lit) — a constraint clause with identifier ID containing literal lit, where lit is either pos(j, d) or neg(j, d).

First-Order Encoding

The encoding introduces the following predicates:

assigned(R, I, A) — value A is assigned to the (R, I)-entry of the array.
pair(I, J, A, B) — represents a valid pair (A, B) in the interaction of parameters (I, J); these are pre-calculated valid pairs.
covered(I, J, A, B) — a pair (A, B) is covered in the interaction of parameters (I, J).

Encoding Rules

row(1..n).  col(I) :- p(I,_).  c(ID) :- c(ID,_).

1 { assigned(R,I,A) : p(I,A) } 1 :- row(R); col(I).

% domain constraints
:- not assigned(R,I,A) : c(ID,pos(I,A));
   assigned(R,J,B) : c(ID,neg(J,B)); c(ID); row(R).

% coverage constraints
covered(I,J,A,B) :- assigned(R,I,A); assigned(R,J,B); I<J.
:- not covered(I,J,A,B); pair(I,J,A,B).

Optimal Strength-2 CMCA Finding (Listing 3)

The optimal CMCA finding encoding extends the basic one with activation atoms. The predicate activated(R) indicates that row R is used in the resulting array. The encoding uses blocking variables and minimizes the number of activated rows:

row(1..n).  col(I) :- p(I,_).  c(ID) :- c(ID,_).

% activation atoms
{ activated(R) : row(R) }.
#minimize{ 1@size,R : activated(R) }.
:- not activated(R); activated(R+1); R>0.  % can be omitted

1 { assigned(R,I,A) : p(I,A) } 1 :- activated(R); col(I).

% domain constraints
:- not assigned(R,I,A) : c(ID,pos(I,A));
   assigned(R,J,B) : c(ID,neg(J,B)); c(ID); row(R).

% coverage constraints
covered(I,J,A,B) :- assigned(R,I,A); assigned(R,J,B); I<J.
:- not covered(I,J,A,B); pair(I,J,A,B).

This encoding is referred to as the basic encoding. Rule line 4 generates an activated(R) atom for each row R; rule line 5 minimizes the number of activated rows; rule line 8 generates parameter value assignments only for activated rows. The greedy activation rule on line 6 can be omitted but is kept for performance improvement.

Extensions

The basic catnap encoding can be extended in several ways:

Weakened encoding for CCT under limiting resources (Listing 4): Switches coverage constraints from hard to soft ("weak coverage constraints"), maximizing the number of covered pairs. This allows finding test suites of maximal coverage when the initial bound n is smaller than the minimal CMCA size, while still finding optimal CMCAs when n is sufficient.
Hybridization with prioritized CT: The weakened encoding provides a complementary approach to prioritized combinatorial testing, which uses ordering or re-ordering strategies between test cases for earlier failure detection.

The catnap encodings described in the source paper are restricted to strength t = 2, though the approach generalizes to t ≥ 3.

Related Concepts

Covering Array: A CMCA extends a covering array with CNF domain constraints. Without constraints C, the definition reduces to a standard covering array.

Implementations

ASP encoding for strength-2 CMCA finding (basic, with a given bound n) — provides feasible (not necessarily optimal) CMCAs.
ASP encoding for optimal strength-2 CMCA finding — minimizes the number of rows using activation atoms, yielding the smallest possible CMCA.