Covering arrays and generalizations

Abstract

Covering arrays have been successfully applied in the design of test suites for testing systems such as software circuits and networks where failures can be caused by the interaction between their parameters There has been a great deal of research on covering arrays for last thirty years Much research has been carried out in developing effective methods to construct covering arrays and generalizations of covering arrays A covering array t CA n k g of size n strength t degree k and order g is a k 215 n array on g symbols such that every t 215 n subarray contains every t 215 1 column on g symbols at least once It is desirable in most applications to minimize the size n A covering array is optimal if it has the minimum number of columns among all covering arrays with the same degree strength and order In this dissertation we give an algebraic construction that can be used to build strength four covering arrays The construction given here yields many new upper bounds on the size of optimal covering arrays when g 3 For software or hardware testing applications each row of a covering array corresponds to a parameter each column corresponds to a test case and the g symbols correspond to the values for each parameter In most software development environments we have limited time computing and human resources to perform the testing of a system To model thissituation we consider the problem of creating a best possible testing array covering the maximum number of t way parameter value configurations within a fixed number of test cases If the testing array is a covering array then configuration coverage is 100 Wepresent algebraic constructions for testing arrays with high 3 and 4 way configurationcoverage Two vectors u v 8712 Zn are qualitatively independent if for each ordered pair a b 8712 Zg 215 Zg there is a position 1 8804 i 8804 n such that u i v i a b A strength two covering array is an array with the property that every pair of rows are qualitatively independent A covering newline newline