Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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

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 March 28, 2024)
Created August 31, 2008, Updated October 12, 2021