Introduction to Combinatorial Testing - Automatic Generation of Combinatorial Test Data - page 10

In the traditional definition of CAs, the strength t is usually a positive integer. Chen
and Zhang [ 7 ] refined the concept and proposed a new metric for combinatorial test
suites, called tuple density . The metric considers coverage of tuples with dimensions
higher than t ; and it can be a rational number such as 3 . 4.

Definition 1.6 For a CA of strength t ,the tuple density is the sum of t and the percentage
of the covered ( t + 1 ) -tuples out of all possible ( t + 1 ) -tuples.

The tuple density is an extension of the strength t . It can be used to distinguish one
test suite from another, even if they have the same size and strength.

1.4.3 Covering Arrays with Constraints

An important concept in CT is constraints . In some applications, some parameters in
the SUT model must conform to certain restrictions, or else the test case will become
invalid. For example, we may impose the constraint that “Internet Explorer does not run
on Linux”.
Ignoring parameter constraints will lead to coverage holes , i.e., this will make some
test cases to be invalid and cannot be executed. If a combination is only covered by
invalid test cases, then the failure caused by this combination will not be detected, since
no test case containing it will be executed.
Now we give the definition of constraints as follows:

Definition 1.7 A constraint c is a predicate on the assignments of

parameters p i 1 , p i 2 ,..., p i j . A test case t = ( v 1 , v 2 ,..., v k ) satisfies constraint c if and
only if the assignment of those parameters makes the predicate true.

( v i 1 , v i 2 ,..., v i j )

To the engineer (user of a CT tool), an important question is: How can the constraints
be specified? A straightforward way is to list all the forbidden tuples; but this might be
expensive. A more natural way is to use logic expressions to specify the constraints. But
we need to choose a suitable language of logic. In [ 14 ], the constraints are modeled as
Boolean formulas defined over atomic propositions that encode parameter-value pairs.
With the presence of constraints, some combinations of values may violate some
of the constraints and cannot be in any valid test cases. They are called unsatisfiable .
Also, the coverage requirement will be modified, which requires all satisfiable target
combinations be covered by the array. To check the satisfiability of constraints, we may
use a constraint solver or a satisfiability (SAT) solver for the propositional logic. For
more details about constraint solving and SAT, see Sect. 6.1 .
Arcuri and Briand [ 2 ] compared CT with random testing. They analyzed the issue
formally. They obtained several theorems describing the probability of random testing
to detect interaction faults. Their results indicate that random testing may outperform
CT in some cases, if we do not consider constraints among features/parameters. But in
the presence of constraints, random testing can be worse than CT. Thus, they suggest
doing more research in CT for the cases in which constraints are present.