Refining the In-Parameter-Order Strategy for Constructing Covering Arrays |
| |
Authors: | Michael Forbes Jim Lawrence Yu Lei Raghu N Kacker D Richard Kuhn |
| |
Affiliation: | National Institute of Standards and Technology, Gaithersburg, MD 20899;Massachusetts Institute of Technology, Cambridge, MA 02139;National Institute of Standards and Technology, Gaithersburg, MD 20899;George Mason University, Fairfax, VA 22030;University of Texas at Arlington, Arlington, TX 76019;National Institute of Standards and Technology, Gaithersburg, MD 20899 |
| |
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. |
| |
Keywords: | blackbox testing covering arrays pairwise and higher strength testing |
|
|