Constructions of covering arrays

Abstract

A covering array of size n, strength t, degree k and order g is a k n array on a set of g symbols with the property that in each t n subarray, every t 1 column appears at least once. Covering arrays have been studied for their applications in the testing of software, hardware, network etc. It is desirable in most applications to minimize the size n of a covering array. In this thesis, we propose techniques for constructing good covering arrays using group theory coupled with computer search. In 2004, Meagher and Stevens developed group construction of covering arrays of strength two which uses an array and a group action on the array. This method employs the action on the symbols of a group of order g 􀀀 1 xing one symbol. We extend this method so that the number of xed symbols is permitted to take any non-negative integer value. A comparison of our method with heuristic tools like NIST IPOG-F shows that our construction produces signi cantly smaller size covering arrays. We also propose a technique for constructing covering arrays of strength three with budget constraints.