# Automated Combinatorial Testing for Software

## 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 t-way 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 102 = 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 103 = 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 10n points.  Exhaustive testing would require inputs of all 10n 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 variable-value configuration

Definition.  For a set of t variables, a variable-value 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 variable-value configuration, and a=1, c=1, d=0 is a different variable-value configuration for the same three variables a, c, and d.

### Simple t -way combination coverage

Of the total number of t-way 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 t-way coverage.  If the test set is large, but not designed as a covering array, it is very possible that it provides 2-way 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 2-way, 3-way, etc. coverage has been obtained.

Definition:  For a given test set for n variables, simple t-way combination coverage is the proportion of t-way combinations of n variables for which all variable-values 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 2-way combinations, ab, ac, ad, bc, bd, cd, only bd and cd have all four binary values covered, so simple 2-way coverage for the four tests in Figure 1 is 1/3 = 33.3%.  There are four 3-way 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 3-way 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

### (t + k)-way combination coverage

A test set that provides full combinatorial coverage for t-way 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 3-way covering arrays.  They both achieve 100% 3-way coverage, but if one provides better 4-way and 5-way 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 variable-values configurations are fully covered.  (Note that this measure would normally be applied only to a t-way 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 3-way coverage.  For this test set, bcd is covered, out of the four 3-way combinations, so 2-way coverage is 100%, and (2+1)-way = 3-way 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

### Variable-Value Configuration coverage

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 t-tuple has vt configurations.  For example, in pairwise (2-way) coverage of binary variables, every 2-way combination has 22 = 4 configurations:  00, 01, 10, 11.   We can define two measures with respect to configurations:

Definition.  For a given combination of t variables, variable-value configuration coverage is the proportion of variable-value 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)22 = 24 possible variable-value configurations.  Of these, 19 variable-value 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 t-way 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 variable-value configurations are covered.  All 2-way 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 2-way 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

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 variable-value configurations will always produce a figure as above, with full coverage for all combinations.

Rick Kuhn
d.kuhn@nist.gov
(301) 975-3337

Raghu Kacker

#### Group

Security Components and Mechanisms

#### Topics

Security and Privacy: assurance, modeling, testing & validation

Technologies: software

#### Related Projects

Access Control Policy Testing
Created May 24, 2016, Updated March 04, 2019