Combinatorial Coverage
Combinatorial Coverage Measurement
Since it is nearly always intractable to test all possible combinations, combinatorial testing is a reasonable alternative. For some value of t, testing all tway interactions among n parameters will detect nearly all errors. It is possible that t = n, but reviewing the empirical data on failures, we would expect t to be relatively small. Determining the level of input or configuration state space coverage can help in understanding the degree of risk that remains after testing. If 90%  100% of the state space has been covered, then presumably the risk is small, but if coverage is much smaller, then the risk may be substantial. This tutorial describes some measures of combinatorial coverage that can be helpful in estimating this risk.
Even in the absence of knowledge about a program’s inner structure, we can apply combinatorial methods to produce precise and useful measures. In this case, we measure the state space of inputs. Suppose we have a program that accepts two inputs, x and y, with 10 values each. Then the input state space consists of the 10^{2} = 100 pairs of x and y values, which can be pictured as a checkerboard square of 10 rows by 10 columns. With three inputs, x, y, and z, we would have a cube with 10^{3} = 1,000 points in its input state space. Extending the example to n inputs we would have a (hard to visualize) hypercube of n dimensions with 10^{n} points. Exhaustive testing would require inputs of all 10^{n} combinations, but combinatorial testing could be used to reduce the size of the test set.
How should state space coverage be measured? Looking closely at the nature of combinatorial testing leads to several measures that are useful. We begin by introducing what will be called a variablevalue configuration.
Definition. For a set of t variables, a variablevalue configuration is a set of t valid values, one for each of the variables.
Example. Given four binary variables, a, b, c, and d, a=0, c=1, d=0 is a variablevalue configuration, and a=1, c=1, d=0 is a different variablevalue configuration for the same three variables a, c, and d.
Of the total number of tway combinations for a given collection of variables, what percentage will be covered by the test set? If the test set is a covering array, then coverage is 100%, by definition, but many test sets not based on covering arrays may still provide significant tway coverage. If the test set is large, but not designed as a covering array, it is very possible that it provides 2way coverage or better. For example, random input generation may have been used to produce the tests, and good branch or condition coverage may have been achieved. In addition to the structural coverage figure, for software assurance it would be helpful to know what percentage of 2way, 3way, etc. coverage has been obtained.
Definition: For a given test set for n variables, simple tway combination coverage is the proportion of tway combinations of n variables for which all variablevalues configurations are fully covered.
Example. Figure 1 shows an example with four binary variables, a, b, c, and d, where each row represents a test. Of the six 2way combinations, ab, ac, ad, bc, bd, cd, only bd and cd have all four binary values covered, so simple 2way coverage for the four tests in Figure 1 is 1/3 = 33.3%. There are four 3way combinations, abc, abd, acd, bcd, each with eight possible configurations: 000, 001, 010, 011, 100, 101, 110, 111. Of the four combinations, none has all eight configurations covered, so simple 3way coverage for this test set is 0%.
a

b

c

d

0

0

0

0

0

1

1

0

1

0

0

1

0

1

1

1

 1. An example test array for a
system with four binary components
A test set that provides full combinatorial coverage for tway combinations will also provide some degree of coverage for (t+1)way combinations, (t+2)way combinations, etc. This statistic may be useful for comparing two combinatorial test sets. For example, different algorithms may be used to generate 3way covering arrays. They both achieve 100% 3way coverage, but if one provides better 4way and 5way coverage, then it can be considered to provide more software testing assurance.
Definition. For a given test set for n variables, (t+k)way combination coverage is the proportion of (t+k)way combinations of n variables for which all variablevalues configurations are fully covered. (Note that this measure would normally be applied only to a tway covering array, as a measure of coverage beyond t).
Example. If the test set in Figure 1 is extended as shown in Figure 2, we can extend 3way coverage. For this test set, bcd is covered, out of the four 3way combinations, so 2way coverage is 100%, and (2+1)way = 3way coverage is 25%.
a

b

c

d

0

0

0

0

0

1

1

0

1

0

0

1

0

1

1

1

1

1

0

1

1

0

1

1

1

0

1

0

0

1

0

0

 2. Eight tests for four binary variables.
So far we have only considered measures of the proportion of combinations for which all configurations of t variables are fully covered. But when t variables with v values each are considered, each ttuple has v^{t}^{ }configurations. For example, in pairwise (2way) coverage of binary variables, every 2way combination has 2^{2} = 4 configurations: 00, 01, 10, 11. We can define two measures with respect to configurations:
Definition. For a given combination of t variables, variablevalue configuration coverage is the proportion of variablevalue configurations that are covered.
Definition. For a given set of n variables, (p, t)completeness is the proportion of the C(n, t) combinations that have configuration coverage of at least p.
Example. For Figure 1 above, there are C(4, 2) = 6 possible variable combinations and C(4,2)2^{2} = 24 possible variablevalue configurations. Of these, 19 variablevalue configurations are covered and the only ones missing are ab=11, ac=11, ad=10, bc=01, bc=10. But only two, bd and cd, are covered with all 4 value pairs. So for the basic definition of simple tway coverage, we have only 33% (2/6) coverage, but 79% (19/24) for the configuration coverage metric. For a better understanding of this test set, we can compute the configuration coverage for each of the six variable combinations, as shown in Figure 3. So for this test set, one of the combinations (bc) is covered at the 50% level, three (ab, ac, ad) are covered at the 75% level, and two (bd, cd) are covered at the 100% level. And, as noted above, for the whole set of tests, 79% of variablevalue configurations are covered. All 2way combinations have at least 50% configuration coverage, so (.50, 2)completeness for this set of tests is 100%.
Although the example in Figure 1 uses variables with the same number of values, this is not essential for the measurement. Later sections of this document show how to use the tool for computing coverage of test sets where variables have different numbers of parameters.
Vars

Configurations covered

Config coverage

a b

00, 01, 10

.75

a c

00, 01, 10

.75

a d

00, 01, 11

.75

b c

00, 11

.50

b d

00, 01, 10, 11

1.0

c d

00, 01, 10, 11

1.0

 total 2way coverage = 19/24 = .79167
 (.50, 2)completeness = 6/6 = 1.0
 (.75, 2)completeness = 5/6 = 0.83333
 (1.0, 2)completeness = 2/6 = 0.33333
 3. The test array covers all possible 2way combinations of a, b, c,
and d to different levels.
The graph below shows a graphical display of the coverage data for the tests in Figure 1. Coverage is given as the Y axis, with the percentage of combinations reaching a particular coverage level as the X axis. Note from Fig. 1 that 100% of the combinations are covered to at least the .50 level, 83% are covered to the .75 level or higher, and a third covered 100%. Thus the rightmost horizontal line on the graph corresponds to the smallest coverage value from the test set, in this case 50%.
Additional tests can be added to provide greater coverage. Suppose an additonal test [1,1,0,1] is added. Coverage then increases as shown below. Now we can see immediately that all combinations are covered to at least the 75% level, as shown by the rightmost horizontal line (in this case there is only one horizontal line). The lefmost vertical line reaches the 1.0 level of coverage, showing that 50% of combinations are covered to the 100% level.
Adding another test, [1,0,1,1] results in the coverage shown below.
If a test [1,0,1,0] is then added, 100% coverage for all combinations is reached:
The graph can thus be thought of as a “coverage strength meter”, where the red indicator line moves to the right as higher coverage levels are reached. A covering array, which by definition covers 100% of variablevalue configurations will always produce a figure as above, with full coverage for all combinations.