A covering array is a mathematical object that can be used for software testing purposes (see the Hartman paper for another introduction). Software often has many possible configurations, each of which could be faulty. Software testing tries to make sure that no actual error occurs in any such configuration. One possible method to achieve this goal is to simulate all possible configurations and check that no error occurs. However, this is typically impractical because there are too many configurations to check.
There are many ways to approach software testing in a more practical way, but few of them capture the abstraction and generality of simply running a ``test and check'' procedure on various sample configurations. To make this method more practical, we can realize that testing all possible configurations of a software program can be redundant and it might be possible to achieve an adequate simulation of all of the program's behavior with a much smaller number of carefully chosen configurations.
The notion of coverage is used to quantify how well a set of sample configurations ``covers'' the set of all configurations. Intuitively, full coverage means that all configurations are chosen and no coverage means that none are chosen. Intermediate levels of coverage are defined in terms of a parameter t. There are two additional parameters that represent the total number of configurations: k is the number of variables a configuration needs to specify and v is the number of possible values each of the k variables can take on. While in practice each variable can take on a different number of values, we only consider the homogeneous case (where all inputs take on the same number of values) on this site. Taking t equal to k will produce full coverage and taking t equal to zero will produce no coverage. To understand what intermediate values of t mean we turn to an example.
We will consider a simple program that takes only four binary variables. Thus, k=4 and v=2. To take t=4 would give full coverage, and thus the following set of configurations to test the program on:
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
If we look at this list of configurations, we notice that whichever two columns out of the four columns are chosen, all possible pairs of values come up. Specifically, the pairs 00, 01, 10 and 11 all appear in the rows when we look at the first and second columns only, the first and third columns only, etc. This is intuitive because the table fully covers the configurations. However, there are other configurations that might also share this property. Specifically, we can consider the table:
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
This table of five configurations does indeed have the property that for each pair of columns chosen, all possible configurations of the two inputs appear. This property is called 2-coverage, and corresponds to when t=2. By abstracting away from the idea of software testing we see this is just an array of numbers and because it satisfies the 2-coverage property we call it a covering array. We can naturally generalize this to arbitrary t by defining t-way coverage to hold on an array when for every choice of t columns from the k columns, all possible v^t t-tuples appear within the rows of the array.
Now that the definition of a covering array is put forth, we can seek optimal covering arrays. That is, for fixed t, v and k values, what is the size of the smallest covering array? As k determines the number of columns, this question is really asking what is the smallest number of rows that an array can have while satisfying the t-covering property. The above covering array with five rows is in fact optimal, as set forth by a paper by Kleitman and Spencer. Except in this special case for t=2 and v=2 it is generally unknown what are the sizes of optimal covering arrays. For example, the following covering array for t=3, v=2, and k=4 has 9 rows, but in fact 8 are sufficient (as listed in Charlie Colbourn's covering array tables).
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
A major application of covering arrays is the task of software testing (see the Hartman paper). Any software package will have two natural parameters, the number of inputs and the number of values each input can take. For simplicity, this site only deals with the homogeneous case of when all of the inputs take on the same number of values. This first parameter corresponds to k and the second corresponds to v, as explained above (and below). A third parameter t needs to be chosen and this dictates the ``level'' of coverage of the input space. Ideally it would be possible to take t=k, but that typically results in too many configurations to test. Empirical studies show that for most software packages t need not be more than 6 to find all errors. Once the parameters are fixed, a covering array can be generated. The rows of the array will correspond to tests that need to be performed on the software package and thus need to be converted into a form the program can use. For example, if a system of networked printing was being tested the inputs might be the operating system, the web-browser, the network type and the time of day. If we take two values for each input, we could modify the above covering array into the test suite below for this system.
| OS | Browser | Network | Time |
|---|---|---|---|
| Mac | Opera | wired | morning |
| Mac | Firefox | wireless | afternoon |
| Linux | Opera | wireless | afternoon |
| Linux | Firefox | wired | afternoon |
| Linux | Firefox | wireless | morning |
t - t is sometimes called the ``strength'' of the array. It is a measure of how ``fully'' we cover the possible rows in the array. For t=0, no rows need to be present and for t=k all rows need to be present (as the number of columns is equal to k). This is because any covering array must satisfy the t-covering property: when any t of the k columns are chosen, all v^t of the possible t-tuples must appear among the rows.
For example, the following array is not a covering array for t=2, v=2, and k=4, because the second and forth columns do not have the 2-tuple (1,0) among the rows.
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
v - v is the number of possible values that each entry in the array can take on. While the actual symbols chosen are irrelevant, they typically the numbers between 0 and v-1. v corresponds to the number of settings an input in the software can take on. While typically this varies for each input, these pages only consider the homogeneous case.
k - k is the number of columns in the array. Thus, the ``size'' of an array is usually given as its number of rows, as the number of columns is fixed. k corresponds to the number of inputs in the software package that is being tested.
CA(t,k,v) - CA(t,k,v) is the so-called ``covering array number'' of the variables t, k, and v. It is the number of rows in the associated covering array. The smallest possible array gives the covering array number denoted CAN(t,k,v), and so these pages present upper-bounds for CAN numbers.
The study of covering arrays is both mathematical and computational. The mathematical questions deal with the size of the smallest known arrays in terms of t, v, and k. Not only are these formulas used to determine sizes for specific values of these parameters, but also to develop limiting values. Areas of math such as algebra and combinatorics are used to study this type of question. The computational side of covering arrays deals with how to construct covering arrays efficiently. It is often the case that the arrays known via mathematical means are either too large (as compared to arrays constructed by heuristics) to be used or take too long to construct. Some of the mathematical techniques are non-constructive and so while they prove the existence of certain sized covering arrays, they provide little insight in how to construct them.
The ACTS project, while interested in all aspects of covering arrays, is primarily trying to develop algorithms to make the construction of covering arrays practical. Thus, it is the actual array that is of interest and not only the size. That is why these pages not only list the size of arrays, like Charlie Colbourn's site but also give the actual arrays. This is done because while the algorithms continue to get faster, they still take a large amount of time and thus these pages seek to archive the best known covering arrays so that others can study the actual arrays, build new arrays from them, and also use these arrays without having to spend the computational resources.
The CAtables are a service of the Mathematical and Computational Sciences Division of the Information Technology Laboratory of the National Institute of Standards and Technology. Development Status: Active Development. We conform to the NIST Privacy Policy.
Last updated: 2008-04-17
For comments please mail the Covering Arrays Team: coveringarrays at nist dot gov