Refining the In-Parameter-Order Strategy for Constructing Covering Arrrays

Published

September 1, 2008

Author(s)

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

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.

Citation

Journal of Research (NIST JRES) -

Volume

113

Issue

5

NIST Pub Series

Journal of Research (NIST JRES)

Pub Type

NIST Pubs

Download Paper

DOI Link

Keywords

blackbox testing, covering arrays, pairwise and higher strength testing

Citation

Forbes, M. , Lawrence, J. , Lei, Y. , Kacker, R. and Kuhn, D. (2008), Refining the In-Parameter-Order Strategy for Constructing Covering Arrrays, Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/jres.113.022 (Accessed October 25, 2025)