The density algorithm for pairwise interaction testing

Renée C. Bryce, Charles Colbourn

Research output: Contribution to journalArticlepeer-review

142 Scopus citations


There are many published algorithms for generating interaction test suites for software testing, exemplified by AETG, IPO, TCG, TConfig, simulated annealing and other heuristic search, and combinatorial design techniques. Among these, greedy one-test-at-a-time methods (such as AETG and TCG) have proven to be a reasonable compromise between the needs for small test suites, fast test-suite generation, and flexibility to accommodate a variety of testing scenarios. However, such methods suffer from the lack of a worst-case logarithmic guarantee on test suite size, while methods that provide such a guarantee at present are less efficient or flexible, or do not produce test suites that are competitive in size for practical testing scenarios. In this paper, a new algorithm establishes that efficient, greedy, one-test-at-a-time methods can indeed produce a logarithmic worst-case guarantee on the test suite size. In addition, this can be done while still producing test suites that are of competitive size, and in a time that is comparable to the published methods. It is deterministic, guaranteeing reproducibility. It generates only one candidate test at a time, permits users to 'seed' the test suite with specified tests, and allows users to specify constraints of combinations that should be avoided. Further, statistical analysis examines the impact of five variables used to tune this density algorithm for execution time and test suite size: weighting of density for factors, scaling of density, tie-breaking, use of multiple candidates, and multiple repetitions using randomization.

Original languageEnglish (US)
Pages (from-to)159-182
Number of pages24
JournalSoftware Testing Verification and Reliability
Issue number3
StatePublished - Sep 2007


  • Covering array
  • Mixed-level covering array
  • One-row-at-a-time greedy algorithm
  • Pairwise coverage
  • Software interaction testing

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'The density algorithm for pairwise interaction testing'. Together they form a unique fingerprint.

Cite this