A Deterministic Density Algorithm for Pairwise Interaction Coverage

C.J. Colbourn (USA), M.B. Cohen (New Zealand), and R.C. Turban (USA)


software interaction testing, covering array, greedy algorithm, pairwise coverage


Pairwise coverage of factors affecting software has been proposed to screen for potential errors. Techniques to gen erate test suites for pairwise coverage are evaluated accord ing to many criteria. A small number of tests is a main cri terion, as this dictates the time for test execution. Random ness has been exploited to search for small test suites, but variation occurs in the test suite produced. A worst-case guarantee on test suite size is desired; repeatable genera tion is often necessary. The time to construct the test suite is also important. Finally, testers must be able to include certain tests, and to exclude others. The main approaches to generating test suites for pairwise coverage are examined; these are exemplified by AETG, IPO, TCG, TConfig, simulated annealing, and combinatorial design techniques. A greedy variant of AETG and TCG is developed. It is deterministic, guar anteeing reproducibility. It generates only one candidate test at a time, providing faster test suite development. It is shown to provide a logarithmic worst-case guarantee on the test suite size. It permits users to "seed" the test suite with specified tests. Finally, comparisons with other greedy ap proaches demonstrate that it often yields the smallest test suite.

Important Links:

Go Back