Measuring and specifying combinatorial coverage of test input configurations

Abstract

A key issue in testing is how many tests are needed for a required level of coverage or fault detection. Estimates are often based on error rates in initial testing, or on code coverage. For example, tests may be run until a desired level of statement or branch coverage is achieved. Combinatorial methods present an opportunity for a different approach to estimating required test set size, using characteristics of the test set. This paper describes methods for estimating the coverage of, and ability to detect, t-way interaction faults of a test set based on a covering array. We also develop a connection between (static) combinatorial coverage and (dynamic) code coverage, such that if a specific condition is satisfied, 100 % branch coverage is assured. Using these results, we propose practical recommendations for using combinatorial coverage in specifying test requirements, and for improving estimates of the fault detection capacity of a test set.

Appendices

Appendix 1: Ancillary coverage, ($t+1$)-way and ($t+2$)-way for n-variable covering arrays

Appendix 2

Explanation of charts: Lower and upper bounds on fault coverage are estimated for n-variable covering arrays, using ancillary $(t+1)$-way and $(t+2)$-way coverage for t-way arrays, for $t=2$ through 5. For example, the first column below indicates that a 2-way covering array provides 100 % 1-way and 100 % 2-way coverage, 76.8 % 3-way coverage, and 46.1 % 4-way coverage. Similarly, the second column shows 100 % coverage of 1-way through 3-way for a 3-way array, with 83.5 and 53.5 % 4-way and 5-way coverage. Lower and upper bounds are then computed using the empirical data from Table 1 (reproduced in first two columns below) and expression (2) for $\mathrm{Fault\,coverage}=\sum \nolimits _{1\le t\le k} F_t \times S_t$.

Appendix 3

Explanation of charts: Comparison of fault coverage for two different hypothetical distributions of faults in 10-variable covering arrays, using $(t+1)$-way and $(t+2)$-way coverage for t-way arrays, for $t=2$ through 5. For example, the first column below indicates that a 2-way covering array provides 100 % 1-way and 100 % 2-way coverage, 76.8 % 3-way coverage, and 46.1 % 4-way coverage, resulting in 2-way fault coverage of 49.9 % for distribution 1 (right) and 23.1 % for distribution 2.

Appendix 4

The left panel of Table 4 shows the combinatorial coverage of 7489 tests for a NASA spacecraft documented in [9]. The test set was developed using conventional methods and analyzed to determine the level of combinatorial coverage. The right panel shows fault coverage estimated using expression (2) under various possible hypothetical fault profiles.

Profile ${P}_{1}$ is approximately the upper bound from Table 2, representing an average of fault distributions for previously reported data [5]. ${P}_{2}$ assumes an application for which single-value faults have been removed. ${P}_{3}$ assumes an application has been thoroughly tested and all single-value and 2-way faults have been removed. Fault coverage declines because t-way combinatorial coverage decreases with increasing t. A fault profile such as ${P}_{1}$ might be expected in an average application, while ${P}_{2}$ and ${P}_{3}$ might be seen in more well-tested applications. Note that these figures estimate only the proportion of fault coverage; a previously untested application could be expected to have a higher absolute number of faults than those that have been used and tested extensively.

Table 4 Fault coverage under various assumptions