Refining the in-parameter-order strategy for constructing covering arrays

Michael Forbes, Jim Lawrence, Yu Lei, Raghu N. Kacker, D. Richard Kuhn

Research output: Contribution to journalArticlepeer-review

Abstract

Covering arrays are structures for well-representing extremely large input spaces and are used to efficiently implement blackbox testing for software and hardware. This paper proposes refinements over the In-Parameter-Order strategy (for arbitrary t). When constructing homogeneous-alphabet covering arrays, these refinements reduce runtime in nearly all cases by a factor of more than 5 and in some cases by factors as large as 280. This trend is increasing with the number of columns in the covering array. Moreover, the resulting covering arrays are about 5 % smaller. Consequently, this new algorithm has constructed many covering arrays that are the smallest in the literature. A heuristic variant of the algorithm sometimes produces comparably sized covering arrays while running significantly faster.

Original languageEnglish (US)
Pages (from-to)287-297
Number of pages11
JournalJournal of Research of the National Institute of Standards and Technology
Volume113
Issue number5
DOIs
StatePublished - 2008

Keywords

  • Blackbox testing
  • Covering arrays
  • Painvise and higher strength testing

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Refining the in-parameter-order strategy for constructing covering arrays'. Together they form a unique fingerprint.

Cite this