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 × n array on g symbols such that every t × n subarray contains every t × 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 this situation, 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%. We present algebraic constructions for testing arrays with high 3- and 4-way configuration coverage. Two vectors u, v ∈ Zn are qualitatively independent if for each ordered pair (a, b)∈ Zg × Zg there is a position 1 ≤ i ≤ 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 array on a graph is an array with a row for each vertex of the graph with the property that any two rows which correspond to adjacent vertices are qualitatively independent. Given a graph G and a positive integer g, a covering array on G with minimum size n is called optimal. Our primary focus is with constructions that make optimal covering arrays on large graphs that are obtained from a product of smaller graphs. We consider four most extensively studied graph products in the literature and give upper and lower bounds on the size of an optimal covering array on a product graph. We find families of graphs for which the size of a covering array on a product graph achieves the lower bound with respect to the Cartesian product. In addition, we present a polynomial time approximation algorithm for constructing covering arrays on graphs having k prime factors with respect to the Cartesian product. We consider a generalization of covering arrays on graphs to higher strength, called mixed covering arrays on 3-uniform hypergraphs. The addition of a graph or hypergraph structure to covering arrays makes it possible to use methods from graph and hypergraph theory to study covering arrays. We introduce four hypergraph operations that allow us to add new vertices to a hypergraph while preserving the size of a mixed covering array on the hypergraph. Using these operations, for the case in which H is a 3-uniform α -acyclic hypergraph, a 3-uniform interval hypergraph, a 3-uniform conformal hypertree having a binary tree as host tree, a 2-tree hypergraph, or a 3-uniform loose cycle, we construct an optimal mixed covering array on H.