A Branch & Bound Algorithm to Derive a Direct Construction for Binary Covering Arrays

Covering arrays are used in testing deterministic systems where failures occur as a result of interactions among subsystems. The goal is to reveal if any interaction induces a failure in the system. Application areas include software and hardware testing. A binary covering array CA(N;t,k,2) is an \(N \times k\) array over the alphabet \(\{0,1\}\) with the property that each set of t columns contains all the \(2^t\) possible t-tuples of 0’s and 1’s at least once. In this paper we propose a direct method to construct binary covering arrays using an specific interpretation of binomial coefficients: a binomial coefficient with parameters k and r will be interpreted as the set of all the k-tuples from \(\{0,1\}\) having r ones and \(k-r\) zeroes. For given values of k and t, the direct method uses an explicit formula in terms of both k and t to provide a covering array CA(N;t,k,2) expressed as the juxtaposition of a set of binomial coefficients; this covering array will be of the minimum size that can be obtained by any juxtaposition of binomial coefficients. In order to derive the formula, a Branch & Bound (B&B) algorithm was first developed; the B&B algorithm provided solutions for small values of k and t that allowed the identification of the general pattern of the solutions. Like others previously reported methods, our direct method finds optimal covering arrays for \(k = t+1\) and \(k = t+2\); however, the major achievement is that nine upper bounds were significantly improved by our direct method, plus the fact that the method is able to set an infinite number of new upper bounds for \(t \ge 7\) given that little work has been done to compute binary covering arrays for general values of k and t.