A Survey of Binary Covering Arrays
---
paper_title: Minimax Rendezvous on the Line

paper_content:

Suppose that $n$ players are placed randomly on the real line at consecutive integers, and faced in random directions. Each player has maximum speed one, cannot see the others, and doesn't know his relative position. What is the minimum time $M_n$ required to ensure that all the players can meet together at a single point, regardless of their initial placement? We prove that $M_2=3$, $M_3=4$, and $M_n$ is asymptotic to $n/2.$ We also consider a variant of the problem which requires players who meet to stick together, and find in this case that three players require $5$ time units to ensure a meeting. This paper is thus a minimax version of the rendezvous search problem, which has hitherto been studied only in terms of minimizing the expected meeting time.
---
paper_title: Applying Design of Experiments to Software Testing

paper_content:

Recently, a class of experimental designs has been devised that guarantee input domain coverage up to all combinations of k test factors taken t at a time. With such designs, all pair-wise combinations (or triplets or quadruplets, etc.) are selected at least once. To evaluate their applicability to software testing, we analyzed the extent to which software coverage (i.e., code execution) achieved by these designs for r = 1 ,...,k is representative of that achieved by exhaustively testing all factor combinations. The block coverage obtained for tS2 was comparable with that achieved by exhaustively testing all factor combinations but higher-order values of t were required for path coverage. Implications of these results for software testing are discussed. field, and that there is a total of 151 characters that can be entered across all 20 screen fields, then there are 95’5’~4.3x102g8 different inputs or test cases corresponding to the different ways a user can populate the screen. Clearly, exhaustive input testing is not feasible and hence, a software tester needs to efficiently generate an effective set of test cases as a means of verifying the correct operation of the software.
---
paper_title: Covering arrays for efficient fault characterization in complex configuration spaces

paper_content:

Testing systems with large configurations spaces that change often is a challenging problem. The cost and complexity of QA explodes because often there isn't just one system, but a multitude of related systems. Bugs may appear in certain configurations, but not in others.The Skoll system and process has been developed to test these types of systems through distributed, continuous quality assurance, leveraging user resources around-the-world, around-the-clock. It has been shown to be effective in automatically characterizing configurations in which failures manifest. The derived information helps developers quickly narrow down the cause of failures which then improves turn around time for fixes. However, this method does not scale well. It requires one to exhaustively test each configuration in the configuration space.In this paper we examine an alternative approach. The idea is to systematically sample the configuration space, test only the selected configurations, and conduct fault characterization on the resulting data. The sampling approach we use is based on calculating a mathematical object called a covering array. We empirically assess the effect of using covering array derived test schedules on the resulting fault characterizations and provide guidelines to practitioners for their use.
---
paper_title: Iterative Exhaustive Pattern Generation for Logic Testing

paper_content:

Exhaustive pattern logic testing schemes provide all possible input patterns with respect to an output in the set of test patterns. This paper is concerned with the problem that arises when this is to be done simultaneously with respect to a number of outputs, using a single test set. More specifically, in this paper we describe an iterative procedure for generating a test set consisting of n- dimensional vectors which exhaustively covers all k-subspaces simultaneously, i.e., the projections of n-dimensional vectors in the test set onto any input subset of a specified size k contain all possible patterns of k-tuples. For any given k, we first find an appropriate N (N > k) and generate an efficient N-dimensional test set for exhaustive coverage of all k-subspaces. We next develop a constructive procedure to expand the corresponding test matrix (formed by taking test vectors as its rows) such that a test set of N2-dimensional vectors exhaustively covering the same k-subspaces is obtained. This procedure may be repeated to cover arbitrarily large n (n = N2i after i iterations), while keeping the same k. It is shown that the size of the test set obtained this way grows in size which becomes proportional to (log n) raised to the power of [log (q + 1)], where q is a function of k only, and is approximated (bounded closely below) by k2/4 in binary cases. This approach applies to nonbinary cases as well except that the value of q in an r-ary case is approximated by a number lying between k2/4 and k2/2.
---
paper_title: Recursive generation of locally complete tests

paper_content:

We consider 0–1 matrices with n columns in which any m columns (m < n) contain 2m different rows. Recursive equations and generation algorithms for these matrices are proposed.
---
paper_title: An investigation of the applicability of design of experiments to software testing

paper_content:

Approaches to software testing based on methods from the field of design of experiments have been advocated as a means of providing high coverage at relatively low cost. Tools to generate all pairs, or higher n-degree combinations, of input values have been developed and demonstrated in a few applications, but little empirical evidence is available to aid developers in evaluating the effectiveness of these tools for particular problems. We investigate error reports from two large open-source software projects, a browser and Web server, to provide preliminary answers to three questions: Is there a point of diminishing returns at which generating all n-degree combinations is nearly as effective as all n+1-degree combinations? What is the appropriate value of n for particular classes of software? Does this value differ for different types of software, and by how much? Our findings suggest that more than 95% of errors in the software studied would be detected by test cases that cover all 4-way combinations of values, and that the browser and server software were similar in the percentage of errors detectable by combinations of degree 2 through 6.
---
paper_title: Subcube Fault-tolerance In Hypercubes

paper_content:

Abstract We consider the problem of determining the minimum number of faulty processors, K ( n , m ), and of faulty links, λ( n , m ), in an n -dimensional hypercube computer so that every m -dimensional subcube is faulty. Best known lower bounds for K ( n , m ) and λ( n , m ) are proved, several new recursive inequalities and new upper bounds are established, their asymptotic behavior for fixed m and for fixed n − m is analyzed, and their exact values are determined for small n and m . Most of the methods employed show how to construct sets of faults attaining the bounds. An extensive survey of related work is also included, showing connections to resource allocation, k -independent sets, and exhaustive testing.
---
paper_title: Upper bounds for covering arrays by tabu search

paper_content:

A t-covering array is a collection of k vectors in a discrete space with the property that, in any t coordinate positions, all combinations of the coordinate values occur at least once. Such arrays have applications, for example, in software testing and data compression. Covering arrays are sometimes also called t-surjective arrays or qualitatively t-independent families; when t=2 covering arrays are also called group covering designs or transversal covers. In an optimal covering array the number of vectors is minimized. Constructions for optimal covering arrays are known when t=2 and the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work a tabu search heuristic is used to construct covering arrays that improve on the previously known upper bounds on the sizes of optimal covering arrays.
---
paper_title: Interaction Testing in Model-Based Development: Effect on Model-Coverage

paper_content:

Model-based software development is gaining interest in domains such as avionics, space, and automotives. The model serves as the central artifact for the development efforts (such as, code generation), therefore, it is crucial that the model be extensively validated. Automatic generation of interaction test suites is a candidate for partial automation of this model validation task. Interaction testing is a combinatorial approach that systematically tests all t-way combinations of inputs for a system. In this paper, we report how well interaction test suites (2-way through 5-way interaction test suites) structurally cover a model of the mode- logic of a flight guidance system. We conducted experiments to (1) compare the coverage achieved with interaction test suites to that of randomly generated tests and (2) determine if interaction test suites improve the coverage of black-box test suites derived from system requirements. The experiments show that the interaction test suites provide little benefit over the randomly generated tests and do not improve coverage of the requirements-based tests. These findings raise questions on the application of interaction testing in this domain.
---
paper_title: The AETG system: An approach to testing based on combinatorial design

paper_content:

This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pairwise, triple, or n-way combinations of a system's test parameters. These are the parameters that determine the system's test scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new method in the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers to define test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reduced the cost of test plan development.
---
paper_title: Combination testing strategies: A survey

paper_content:

Combination strategies are test-case selection methods where test cases are identifled by combining values of the difierent test object input parameters based on some combinatorial strategy. This survey presents 15 difierent combination strategies, and covers more than 30 papers that focus on one or several combination strategies. We believe this collection represents most of the existing work performed on combination strategies. This survey describes the basic algorithms used by the combination strategies. Some properties of combination strategies, including coverage criteria and theoretical bounds on the size of test suites, are also included in this description. This survey paper also includes a subsumption hierarchy that attempts to relate the various coverage criteria associated with the identifled combination strategies. Finally, this survey contains short summaries of all the papers that cover combination strategies.
---
paper_title: How robust is the n-cube?

paper_content:

The n-cube network is called faulty if it contains any faulty processor or any faulty link. For any number k we are interested in the minimum number f(n, k) of faults, necessary for an adversary to make any (n-k)-dimensional subcube faulty. Reversely formulated: The existence of a (n-k)- dimensional nonfaulty subcube can be guaranteed, unless there are at least f(n,k) faults in the n-cube. In this paper several lower and upper bounds for f(n, k) are derived such that the resulting gaps are "small". For instance if k ≥ 2 is constant, then f(n, k) = θ(log n). Especially for k = 2 and large n: f(n, 2) ∈ [⌈αn⌉ : ⌈αn⌉ + 2] where αn = log n + 1/2 log log n + 1/2. Or if k = ω(log log n) then 2k ≪ f(n, k) ≪ 2(1+e)k, with e chosen arbitrarily small. The above upper bounds are obtained by analysing the behaviour of an adversary, who makes "worst-case" distributions of a given number of faulty processors. For k = 2 the distribution is obtained constructively, whereas in the general case only the existence is shown using probabilistic arguments. The above bounds change if the notions are relativized with respect to some given parallel faultchecking procedure P. In this case only those subcubes must be made faulty by the adversary, which are possible outputs of P. In the case k = 2 the notion of directed chromatic index is defined to analyse this situation. Relations between the directed chromatic index and the chromatic number are derived, which are of interest in their own right.
---
paper_title: Exhaustive Test Pattern Generation with Constant Weight Vectors

paper_content:

We develop in this paper a simple way of generating a test set which simultaneously provides exhaustive pattern testing with respect to all input subsets of a logic circuit up to a certain size. It is shown that such a test set may be formed with vectors of a particular set of weights. Main theorems and examples are established and illustrated in the binary case (for 2-value logic circuits) and then generalized to nonbinary cases (for multivalue logic circuits). Such test sets are simple in structure and become optimal in size in certain cases. It is also shown that such a test set can be effectively implemented via a scan path type shifter.
---
paper_title: Software and Hardware Testing Using Combinatorial Covering Suites

paper_content:

In the 21st century our society is becoming more and more dependent on software systems. The safety of these systems and the quality of our lives is increasingly dependent on the quality of such systems. A key element in the manufacture and quality assurance process in software engineering is the testing of software and hardware systems. The construction of efficient combinatorial covering suites has important applications in the testing of hardware and software. In this paper we define the general problem, discuss the lower bounds on the size of covering suites, and give a series of constructions that achieve these bounds asymptotically. These constructions include the use of finite field theory, extremal set theory, group theory, coding theory, combinatorial recursive techniques, and other areas of computer science and mathematics. The study of these combinatorial covering suites is a fascinating example of the interplay between pure mathematics and the applied problems generated by software and hardware engineers. The wide range of mathematical techniques used, and the often unexpected applications of combinatorial covering suites make for a rewarding study.
---
paper_title: Almost independent and weakly biased arrays: Efficient constructions and cryptologic applications

paper_content:

The best known constructions for arrays with low bias are those from [1] and the exponential sum method based on the Weil-Carlitz-Uchiyama bound. They all yield essentially the same parameters. We present new efficient coding-theoretic constructions, which allow far-reaching generalizations and improvements. The classical constructions can be described as making use of Reed-Solomon codes. Our recursive construction yields greatly improved parameters even when applied to Reed-Solomon codes. Use of algebraic-geometric codes leads to even better results, which are optimal in an asymptotic sense. The applications comprise universal hashing, authentication, resilient functions and pseudorandomness.
---
paper_title: NOTE EXPLICIT CONSTRUCTION OF EXPONENTIAL SIZED FAMILIES OF k-INDEPENDENT SETS

paper_content:

Abstract Error correcting codes are used to describe explicit collections F k of subsets of {1,2,...; n }, with | F k | > 2 c k · n ( C k > 0), such that for any selections A , B of k 2 and k 1 of members of F k with k 1 + k 2 = k , there are elements in all the members of A and not in the members of B . This settles a problem of Kleitman and Spencer and a similar problem of Kleimman, Shearer and Sturtevant.
---
paper_title: Covering arrays and intersecting codes

paper_content:

A t-covering array is a set of k binary vectors of length n with the property that, in any t coordinate positions, all 2t possibilities occur at least once. Such arrays are used for example in circuit testing, and one wishes to minimize k for given values of n and t. The case t = 2 was solved by Renyi, Katona, and Kleitman and Spencer. The present article is concerned with the case t = 3, where important (but unpublished) contributions were made by Busschbach and Roux in the 1980s. One of the principal constructions makes use of intersecting codes (linear codes with the property that any two nonzero codewords meet). This article studies the properties of 3-covering arrays and intersecting codes, and gives a table of the best 3-covering arrays presently known. For large n the minimal k satisfies 3.21256 < k/log n < 7.56444. © 1993 John Wiley & Sons, Inc.
---
paper_title: Largest induced subgraphs of the n-cube that contain no. 4-cycles

paper_content:

Every induced subgraph of the n-cube, Qn, with more than ⌈2n+13⌉ vertices is shown to contain a 4-cycle; this bound is sharp. The extremal graphs are characterized as translations of a specific subgraph of Qn.
---
paper_title: Covering and radius-covering arrays: Constructions and classification

paper_content:

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.
---
paper_title: NOTE EXPLICIT CONSTRUCTION OF EXPONENTIAL SIZED FAMILIES OF k-INDEPENDENT SETS

paper_content:

Abstract Error correcting codes are used to describe explicit collections F k of subsets of {1,2,...; n }, with | F k | > 2 c k · n ( C k > 0), such that for any selections A , B of k 2 and k 1 of members of F k with k 1 + k 2 = k , there are elements in all the members of A and not in the members of B . This settles a problem of Kleitman and Spencer and a similar problem of Kleimman, Shearer and Sturtevant.
---
paper_title: Subcube Fault-tolerance In Hypercubes

paper_content:

Abstract We consider the problem of determining the minimum number of faulty processors, K ( n , m ), and of faulty links, λ( n , m ), in an n -dimensional hypercube computer so that every m -dimensional subcube is faulty. Best known lower bounds for K ( n , m ) and λ( n , m ) are proved, several new recursive inequalities and new upper bounds are established, their asymptotic behavior for fixed m and for fixed n − m is analyzed, and their exact values are determined for small n and m . Most of the methods employed show how to construct sets of faults attaining the bounds. An extensive survey of related work is also included, showing connections to resource allocation, k -independent sets, and exhaustive testing.
---
paper_title: Sperner systems consisting of pairs of complementary subsets

paper_content:

Abstract It was proved by Erdos, Ko, and Rado (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 12 (1961) , 313–320.) that if A = {;A1,…, Al}; consists of k-subsets of a set with n > 2k elements such that Ai ∩ Aj ≠ ∅ for all i, j then l ⩽ (k−1n−1). Schonheim proved that if A1, …, Al are subsets of a set S with n elements such that Ai ∉ Aj, Ai ∩ Aj ≠ o and Ai ∪ Aj ≠ S for all i ≠ j then l ⩽ ( [ n 2 ] − 1 n − 1 ) . In this note we prove a common strengthening of these results.
---
paper_title: Families of k-independent sets

paper_content:

A collection F of sets is k-independent if for any selections A, B of k"1 and k"2 of its members with k"1+k"2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.
---
paper_title: Sperner type theorems for finite sets

paper_content:

A broom stitching machine having a movable vise assembly including movable jaws for clamping the broom in sewing position wherein reciprocating needles move through the broom straws at substantially 70 DEG to 80 DEG to the plane of the vise jaws for binding the strands together, including improved means for moving the broom vise a predetermined distance between each stitch by providing an intermittent rotating shaft to which the movable vise assembly is connected including means for adjusting the amount of the shaft rotation for regulating the length of the stitch.
---
paper_title: Covering and radius-covering arrays: Constructions and classification

paper_content:

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.
---
paper_title: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs

paper_content:

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood. >
---
paper_title: Iterative Exhaustive Pattern Generation for Logic Testing

paper_content:

Exhaustive pattern logic testing schemes provide all possible input patterns with respect to an output in the set of test patterns. This paper is concerned with the problem that arises when this is to be done simultaneously with respect to a number of outputs, using a single test set. More specifically, in this paper we describe an iterative procedure for generating a test set consisting of n- dimensional vectors which exhaustively covers all k-subspaces simultaneously, i.e., the projections of n-dimensional vectors in the test set onto any input subset of a specified size k contain all possible patterns of k-tuples. For any given k, we first find an appropriate N (N > k) and generate an efficient N-dimensional test set for exhaustive coverage of all k-subspaces. We next develop a constructive procedure to expand the corresponding test matrix (formed by taking test vectors as its rows) such that a test set of N2-dimensional vectors exhaustively covering the same k-subspaces is obtained. This procedure may be repeated to cover arbitrarily large n (n = N2i after i iterations), while keeping the same k. It is shown that the size of the test set obtained this way grows in size which becomes proportional to (log n) raised to the power of [log (q + 1)], where q is a function of k only, and is approximated (bounded closely below) by k2/4 in binary cases. This approach applies to nonbinary cases as well except that the value of q in an r-ary case is approximated by a number lying between k2/4 and k2/2.
---
paper_title: Largest induced subgraphs of the n-cube that contain no. 4-cycles

paper_content:

Every induced subgraph of the n-cube, Qn, with more than ⌈2n+13⌉ vertices is shown to contain a 4-cycle; this bound is sharp. The extremal graphs are characterized as translations of a specific subgraph of Qn.
---
paper_title: Sperner type theorems for finite sets

paper_content:

A broom stitching machine having a movable vise assembly including movable jaws for clamping the broom in sewing position wherein reciprocating needles move through the broom straws at substantially 70 DEG to 80 DEG to the plane of the vise jaws for binding the strands together, including improved means for moving the broom vise a predetermined distance between each stitch by providing an intermittent rotating shaft to which the movable vise assembly is connected including means for adjusting the amount of the shaft rotation for regulating the length of the stitch.
---
paper_title: Binary Covering Arrays and Existentially Closed Graphs

paper_content:

Binary covering arrays have been extensively studied in many different contexts, but the explicit construction of small binary covering arrays with strength larger than three remains poorly understood. Connections with existentially closed graphs and Hadamard matrices are examined, particularly those arising from the Paley graphs and tournaments. Computational results on arrays generated by column translation, such as the Paley graphs, lead to substantial improvements on known existence results for binary covering arrays of strengths four and five.
---
paper_title: Upper bounds for covering arrays by tabu search

paper_content:

A t-covering array is a collection of k vectors in a discrete space with the property that, in any t coordinate positions, all combinations of the coordinate values occur at least once. Such arrays have applications, for example, in software testing and data compression. Covering arrays are sometimes also called t-surjective arrays or qualitatively t-independent families; when t=2 covering arrays are also called group covering designs or transversal covers. In an optimal covering array the number of vectors is minimized. Constructions for optimal covering arrays are known when t=2 and the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work a tabu search heuristic is used to construct covering arrays that improve on the previously known upper bounds on the sizes of optimal covering arrays.
---
paper_title: A density-based greedy algorithm for higher strength covering arrays

paper_content:

Algorithmic construction of software interaction test suites has focussed on pairwise coverage; less is known about the efficient construction of test suites for t-way interactions with t≥3. This study extends an efficient density-based algorithm for pairwise coverage to generate t-way interaction test suites and shows that it guarantees a logarithmic upper bound on the size of the test suites as a function of the number of factors. To complement this theoretical guarantee, an implementation is outlined and some practical improvements are made. Computational comparisons with other published methods are reported. Many of the results improve upon those in the literature. However, limitations on the ability of one-test-at-a-time algorithms are also identified. Copyright © 2008 John Wiley & Sons, Ltd.
---
paper_title: A backtracking search tool for constructing combinatorial test suites

paper_content:

Combinatorial testing is an important testing method. It requires the test cases to cover various combinations of parameters of the system under test. The test generation problem for combinatorial testing can be modeled as constructing a matrix which has certain properties. This paper first discusses two combinatorial testing criteria: covering array and orthogonal array, and then proposes a backtracking search algorithm to construct matrices satisfying them. Several search heuristics and symmetry breaking techniques are used to reduce the search time. This paper also introduces some techniques to generate large covering array instances from smaller ones. All the techniques have been implemented in a tool called EXACT (EXhaustive seArch of Combinatorial Test suites). A new optimal covering array is found by this tool.
---
paper_title: On the Bit Extraction Problem

paper_content:

Consider a coloring of the n-dimensional Boolean cube with c=2/sup s/ colors in such a way that every k-dimensional subcube is equicolored, i.e. each color occurs the same number of times. The author shows that for such a coloring one necessarily has (k-1)/n>or= theta /sub c/=(c/2-1)/(c-1). This resolves the 'bit extraction' or 't-resilient functions' problem (also a special case of the privacy amplification problem) in many cases, such as c-1/n, proving that XOR type colorings are optimal, and always resolves this question to within c/4 in determining the optimal value of k (for any fixed n and c). He also studies the problem of finding almost equicolored colorings when (k-1)/n >
---
paper_title: Bounds on Orthogonal Arrays and Resilient Functions

paper_content:

The only known general bounds on the parameters of orthogonal arrays are those given by Rao in 1947 [J. Roy. Statist. Soc. 9 (1947), 128–139] for general OAγ(t,k,v) and by Bush [Ann. Math. Stat. 23, (1952), 426–434] [3] in 1952 for the special case γ = 1. We present an algebraic method based on characters of homocyclic groups which yields the Rao bounds, the Bush bound in case t ⩾ v, and more importantly a new explicit bound which for large values of t (the strength of the array) is much better than the Rao bound. In the case of binary orthogonal arrays where all rows are distinct this bound was previously proved by Friedman [Proc. 33rd IEEE Symp. on Foundations of Comput. Sci., (1992), 314–319] in a different setting. We also note an application to resilient functions. © 1995 John Wiley & Sons, inc.
---
paper_title: Families of k-independent sets

paper_content:

A collection F of sets is k-independent if for any selections A, B of k"1 and k"2 of its members with k"1+k"2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.
---
paper_title: Strong qualitative independence

paper_content:

The subsets A,B of the n-element X are said to be s-strongly separating if the two sets divide X into four sets of size at least s. The maximum number h(n,s) of pairwise s-strongly separating subsets was asymptotically determined by Frankl (Ars Combin. 1 (1976) 53) for fixed s and large n. A new proof is given. Also, estimates for h(n,cn) are found where c is a small constant.
---
paper_title: Sperner type theorems for finite sets

paper_content:

A broom stitching machine having a movable vise assembly including movable jaws for clamping the broom in sewing position wherein reciprocating needles move through the broom straws at substantially 70 DEG to 80 DEG to the plane of the vise jaws for binding the strands together, including improved means for moving the broom vise a predetermined distance between each stitch by providing an intermittent rotating shaft to which the movable vise assembly is connected including means for adjusting the amount of the shaft rotation for regulating the length of the stitch.
---
paper_title: Generalization of Sperner’s Theorem on the Number of Subsets of a Finite Set

paper_content:

Let a finite set R with n elements be given. A system $\alpha = \{ A_1 , \cdots ,A_r \} $ of r subsets of the set R for which $A_i A_j = \emptyset $ and $\sum A_i = R$ is called a decomposition of R. One says that two decompositions $\alpha = \{ A_i , \cdots ,A_r \} $ and $\beta = \{ B_1 , \cdots ,B_r \} $ are connected and writes $\alpha \sim \beta $ if for at least one i either $A_i \subset B_i $, or $B_i \subset A_i $. $K = \{ \alpha \} $ is the s-system of different decompositions if, for all $\alpha ,\beta \in K,\alpha \nsim \beta $. Let $N(K)$ be the number of possible decompositions. The theorem is:\[ \mathop {\max }\limits_K N(K) = \mathop {\max }\limits_{n_1 , \cdots ,n_r } \frac{{n!}} {{\left( {n_1 } \right)! \cdots \left( {n_2 } \right)!}}. \]
---
paper_title: Covering and radius-covering arrays: Constructions and classification

paper_content:

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.
---
paper_title: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs

paper_content:

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood. >
---
paper_title: Families of k-independent sets

paper_content:

A collection F of sets is k-independent if for any selections A, B of k"1 and k"2 of its members with k"1+k"2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.
---
paper_title: Covering arrays and intersecting codes

paper_content:

A t-covering array is a set of k binary vectors of length n with the property that, in any t coordinate positions, all 2t possibilities occur at least once. Such arrays are used for example in circuit testing, and one wishes to minimize k for given values of n and t. The case t = 2 was solved by Renyi, Katona, and Kleitman and Spencer. The present article is concerned with the case t = 3, where important (but unpublished) contributions were made by Busschbach and Roux in the 1980s. One of the principal constructions makes use of intersecting codes (linear codes with the property that any two nonzero codewords meet). This article studies the properties of 3-covering arrays and intersecting codes, and gives a table of the best 3-covering arrays presently known. For large n the minimal k satisfies 3.21256 < k/log n < 7.56444. © 1993 John Wiley & Sons, Inc.
---
paper_title: Simulated Annealing for constructing binary covering arrays of variable strength

paper_content:

This paper presents new upper bounds for binary covering arrays of variable strength constructed by using a new Simulated Annealing (SA) algorithm. This algorithm incorporates several distinguished features including an efficient heuristic to generate good quality initial solutions, a compound neighborhood function which combines two carefully designed neighborhoods and a fine-tuned cooling schedule. Its performance is investigated through extensive experimentation over well known benchmarks and compared with other state-of-the-art algorithms, showing that the proposed SA algorithm is able to outperform them.
---
paper_title: Interaction Testing in Model-Based Development: Effect on Model-Coverage

paper_content:

Model-based software development is gaining interest in domains such as avionics, space, and automotives. The model serves as the central artifact for the development efforts (such as, code generation), therefore, it is crucial that the model be extensively validated. Automatic generation of interaction test suites is a candidate for partial automation of this model validation task. Interaction testing is a combinatorial approach that systematically tests all t-way combinations of inputs for a system. In this paper, we report how well interaction test suites (2-way through 5-way interaction test suites) structurally cover a model of the mode- logic of a flight guidance system. We conducted experiments to (1) compare the coverage achieved with interaction test suites to that of randomly generated tests and (2) determine if interaction test suites improve the coverage of black-box test suites derived from system requirements. The experiments show that the interaction test suites provide little benefit over the randomly generated tests and do not improve coverage of the requirements-based tests. These findings raise questions on the application of interaction testing in this domain.
---
paper_title: Families of k-independent sets

paper_content:

A collection F of sets is k-independent if for any selections A, B of k"1 and k"2 of its members with k"1+k"2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.
---
paper_title: Families of k-independent sets

paper_content:

A collection F of sets is k-independent if for any selections A, B of k"1 and k"2 of its members with k"1+k"2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.
---
paper_title: Subcube Fault-tolerance In Hypercubes

paper_content:

Abstract We consider the problem of determining the minimum number of faulty processors, K ( n , m ), and of faulty links, λ( n , m ), in an n -dimensional hypercube computer so that every m -dimensional subcube is faulty. Best known lower bounds for K ( n , m ) and λ( n , m ) are proved, several new recursive inequalities and new upper bounds are established, their asymptotic behavior for fixed m and for fixed n − m is analyzed, and their exact values are determined for small n and m . Most of the methods employed show how to construct sets of faults attaining the bounds. An extensive survey of related work is also included, showing connections to resource allocation, k -independent sets, and exhaustive testing.
---
paper_title: Software and Hardware Testing Using Combinatorial Covering Suites

paper_content:

In the 21st century our society is becoming more and more dependent on software systems. The safety of these systems and the quality of our lives is increasingly dependent on the quality of such systems. A key element in the manufacture and quality assurance process in software engineering is the testing of software and hardware systems. The construction of efficient combinatorial covering suites has important applications in the testing of hardware and software. In this paper we define the general problem, discuss the lower bounds on the size of covering suites, and give a series of constructions that achieve these bounds asymptotically. These constructions include the use of finite field theory, extremal set theory, group theory, coding theory, combinatorial recursive techniques, and other areas of computer science and mathematics. The study of these combinatorial covering suites is a fascinating example of the interplay between pure mathematics and the applied problems generated by software and hardware engineers. The wide range of mathematical techniques used, and the often unexpected applications of combinatorial covering suites make for a rewarding study.
---
paper_title: Iterative Exhaustive Pattern Generation for Logic Testing

paper_content:

Exhaustive pattern logic testing schemes provide all possible input patterns with respect to an output in the set of test patterns. This paper is concerned with the problem that arises when this is to be done simultaneously with respect to a number of outputs, using a single test set. More specifically, in this paper we describe an iterative procedure for generating a test set consisting of n- dimensional vectors which exhaustively covers all k-subspaces simultaneously, i.e., the projections of n-dimensional vectors in the test set onto any input subset of a specified size k contain all possible patterns of k-tuples. For any given k, we first find an appropriate N (N > k) and generate an efficient N-dimensional test set for exhaustive coverage of all k-subspaces. We next develop a constructive procedure to expand the corresponding test matrix (formed by taking test vectors as its rows) such that a test set of N2-dimensional vectors exhaustively covering the same k-subspaces is obtained. This procedure may be repeated to cover arbitrarily large n (n = N2i after i iterations), while keeping the same k. It is shown that the size of the test set obtained this way grows in size which becomes proportional to (log n) raised to the power of [log (q + 1)], where q is a function of k only, and is approximated (bounded closely below) by k2/4 in binary cases. This approach applies to nonbinary cases as well except that the value of q in an r-ary case is approximated by a number lying between k2/4 and k2/2.
---
paper_title: Randomized Postoptimization of Covering Arrays

paper_content:

The construction of covering arrays with the fewest rows remains a challenging problem. Most computational and recursive constructions result in extensive repetition of coverage. While some is necessary, some is not. By reducing the repeated coverage, metaheuristic search techniques typically outperform simpler computational methods, but they have been applied in a limited set of cases. Time constraints often prevent them from finding an array of competitive size. We examine a different approach. Having used a simple computation or construction to find a covering array, we employ a postoptimization technique that repeatedly adjusts the array in order to (sometimes) reduce its number of rows. At every stage the array retains full coverage. We demonstrate its value on a collection of previously best known arrays by eliminating, in some cases, 10% of their rows. In the well-studied case of strength two with twenty factors having ten values each, postoptimization produces a covering array with only 162 rows, improving on a wide variety of computational and combinatorial methods. We identify certain important features of covering arrays for which postoptimization is successful.
---
paper_title: Combination testing strategies: A survey

paper_content:

Combination strategies are test-case selection methods where test cases are identifled by combining values of the difierent test object input parameters based on some combinatorial strategy. This survey presents 15 difierent combination strategies, and covers more than 30 papers that focus on one or several combination strategies. We believe this collection represents most of the existing work performed on combination strategies. This survey describes the basic algorithms used by the combination strategies. Some properties of combination strategies, including coverage criteria and theoretical bounds on the size of test suites, are also included in this description. This survey paper also includes a subsumption hierarchy that attempts to relate the various coverage criteria associated with the identifled combination strategies. Finally, this survey contains short summaries of all the papers that cover combination strategies.
---
paper_title: A backtracking search tool for constructing combinatorial test suites

paper_content:

Combinatorial testing is an important testing method. It requires the test cases to cover various combinations of parameters of the system under test. The test generation problem for combinatorial testing can be modeled as constructing a matrix which has certain properties. This paper first discusses two combinatorial testing criteria: covering array and orthogonal array, and then proposes a backtracking search algorithm to construct matrices satisfying them. Several search heuristics and symmetry breaking techniques are used to reduce the search time. This paper also introduces some techniques to generate large covering array instances from smaller ones. All the techniques have been implemented in a tool called EXACT (EXhaustive seArch of Combinatorial Test suites). A new optimal covering array is found by this tool.
---
paper_title: In-parameter-order: a test generation strategy for pairwise testing

paper_content:

Pairwise testing (or 2-way testing) is a specification-based testing criterion, which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. Empirical results show that pairwise testing is practical and effective for various types of software systems. We show that the problem of generating a minimum test set for pairwise testing is NP-complete. We propose a test generation strategy, called in-parameter-order (or IPO), for pairwise testing. For a system with two or more input parameters, the IPO strategy generates a pairwise test set for the first two parameters, extends the test set to generate a pairwise test set for the first three parameters, and continues to do so for each additional parameter. The IPO strategy allows the use of local optimization techniques for test generation and the reuse of existing tests when a system is extended with new parameters or new values of existing parameters. We present practical, IPO-based test generation algorithms. We describe the implementation of an IPO-based test generation tool and show some empirical results.
---
paper_title: IPOG: A General Strategy for T-Way Software Testing

paper_content:

Most existing work on t-way testing has focused on 2-way (or pairwise) testing, which aims to detect faults caused by interactions between any two parameters. However, faults can also be caused by interactions involving more than two parameters. In this paper, we generalize an existing strategy, called in-parameter-order (IPO), from pairwise testing to t-way testing. A major challenge of our generalization effort is dealing with the combinatorial growth in the number of combinations of parameter values. We describe a t-way testing tool, called FireEye, and discuss design decisions that are made to enable an efficient implementation of the generalized IPO strategy. We also report several experiments that are designed to evaluate the effectiveness of FireEye
---
paper_title: Refining the In-Parameter-Order Strategy for Constructing Covering Arrays

paper_content:

Covering arrays are structures for wellrepresenting 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.
---
paper_title: A test generation strategy for pairwise testing

paper_content:

Pairwise testing is a specification-based testing criterion which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. The authors propose a novel test generation strategy for pairwise testing.
---
paper_title: The AETG system: An approach to testing based on combinatorial design

paper_content:

This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pairwise, triple, or n-way combinations of a system's test parameters. These are the parameters that determine the system's test scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new method in the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers to define test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reduced the cost of test plan development.
---
paper_title: NOTE EXPLICIT CONSTRUCTION OF EXPONENTIAL SIZED FAMILIES OF k-INDEPENDENT SETS

paper_content:

Abstract Error correcting codes are used to describe explicit collections F k of subsets of {1,2,...; n }, with | F k | > 2 c k · n ( C k > 0), such that for any selections A , B of k 2 and k 1 of members of F k with k 1 + k 2 = k , there are elements in all the members of A and not in the members of B . This settles a problem of Kleitman and Spencer and a similar problem of Kleimman, Shearer and Sturtevant.
---
paper_title: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs

paper_content:

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood. >
---
paper_title: Families of k-independent sets

paper_content:

A collection F of sets is k-independent if for any selections A, B of k"1 and k"2 of its members with k"1+k"2=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.
---
paper_title: Covering arrays and intersecting codes

paper_content:

A t-covering array is a set of k binary vectors of length n with the property that, in any t coordinate positions, all 2t possibilities occur at least once. Such arrays are used for example in circuit testing, and one wishes to minimize k for given values of n and t. The case t = 2 was solved by Renyi, Katona, and Kleitman and Spencer. The present article is concerned with the case t = 3, where important (but unpublished) contributions were made by Busschbach and Roux in the 1980s. One of the principal constructions makes use of intersecting codes (linear codes with the property that any two nonzero codewords meet). This article studies the properties of 3-covering arrays and intersecting codes, and gives a table of the best 3-covering arrays presently known. For large n the minimal k satisfies 3.21256 < k/log n < 7.56444. © 1993 John Wiley & Sons, Inc.
---
paper_title: Simulated Annealing for constructing binary covering arrays of variable strength

paper_content:

This paper presents new upper bounds for binary covering arrays of variable strength constructed by using a new Simulated Annealing (SA) algorithm. This algorithm incorporates several distinguished features including an efficient heuristic to generate good quality initial solutions, a compound neighborhood function which combines two carefully designed neighborhoods and a fine-tuned cooling schedule. Its performance is investigated through extensive experimentation over well known benchmarks and compared with other state-of-the-art algorithms, showing that the proposed SA algorithm is able to outperform them.
---
paper_title: Memetic algorithms for constructing binary covering arrays of strength three

paper_content:

This paper presents a new Memetic Algorithm (MA) designed to compute near-optimal solutions for the covering array construction problem. It incorporates several distinguished features including an efficient heuristic to generate a good quality initial population, and a local search operator based on a fine tuned Simulated Annealing (SA) algorithm employing a carefully designed compound neighborhood. Its performance is investigated through extensive experimentation over well known benchmarks and compared with other state-of-the-art algorithms, showing improvements on some previous best-known results.
---
paper_title: Tabu search for covering arrays using permutation vectors

paper_content:

Abstract A covering array CA ( N ; t , k , v ) is an N × k array, in which in every N × t subarray, each of the v t possible t-tuples over v symbols occurs at least once. The parameter t is the strength of the array. Covering arrays have a wide range of applications for experimental screening designs, particularly for software interaction testing. A compact representation of certain covering arrays employs “permutation vectors” to encode v t × 1 subarrays of the covering array so that a covering perfect hash family whose entries correspond to permutation vectors yields a covering array. We introduce a method for effective search for covering arrays of this type using tabu search. Using this technique, improved covering arrays of strength 3, 4 and 5 have been found, as well as the first arrays of strength 6 and 7 found by computational search.
---
paper_title: Covering arrays of higher strength from permutation vectors

paper_content:

A covering arrayCA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006
---
paper_title: Small-bias probability spaces: efficient constructions and applications

paper_content:

It is shown how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with “almost” equal probability. They are called $\epsilon $-biased random variables. The number of random bits needed to generate the random variables is $O(\log n + \log \frac{1}{\epsilon })$. Thus, if $\epsilon $ is polynomially small, then the size of the sample space is also polynomial. Random variables that are $\epsilon $-biased can be used to construct “almost” k-wise independent random variables where $\epsilon $ is a function of k.These probability spaces have various applications: l. Derandomization of algorithms: Many randomized algorithms that require only k-wise independence of their random bits (where k is bounded by $O(\log n)$), can be derandomized by using $\epsilon $-biased random variables. 2. Reducing the number of random bits required by certain randomized algorithms, e.g., verification of matrix multiplication. 3. Exhaustive tes...
---
paper_title: Binary Covering Arrays and Existentially Closed Graphs

paper_content:

Binary covering arrays have been extensively studied in many different contexts, but the explicit construction of small binary covering arrays with strength larger than three remains poorly understood. Connections with existentially closed graphs and Hadamard matrices are examined, particularly those arising from the Paley graphs and tournaments. Computational results on arrays generated by column translation, such as the Paley graphs, lead to substantial improvements on known existence results for binary covering arrays of strengths four and five.
---
paper_title: Upper bounds for covering arrays by tabu search

paper_content:

A t-covering array is a collection of k vectors in a discrete space with the property that, in any t coordinate positions, all combinations of the coordinate values occur at least once. Such arrays have applications, for example, in software testing and data compression. Covering arrays are sometimes also called t-surjective arrays or qualitatively t-independent families; when t=2 covering arrays are also called group covering designs or transversal covers. In an optimal covering array the number of vectors is minimized. Constructions for optimal covering arrays are known when t=2 and the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work a tabu search heuristic is used to construct covering arrays that improve on the previously known upper bounds on the sizes of optimal covering arrays.
---
paper_title: Combination testing strategies: A survey

paper_content:

Combination strategies are test-case selection methods where test cases are identifled by combining values of the difierent test object input parameters based on some combinatorial strategy. This survey presents 15 difierent combination strategies, and covers more than 30 papers that focus on one or several combination strategies. We believe this collection represents most of the existing work performed on combination strategies. This survey describes the basic algorithms used by the combination strategies. Some properties of combination strategies, including coverage criteria and theoretical bounds on the size of test suites, are also included in this description. This survey paper also includes a subsumption hierarchy that attempts to relate the various coverage criteria associated with the identifled combination strategies. Finally, this survey contains short summaries of all the papers that cover combination strategies.
---
paper_title: Intersecting codes and independent families

paper_content:

A binary intersecting code is a linear code with the property that any two nonzero codewords have intersecting supports. These codes appear in a wide variety of contexts and applications, e.g., multiple access, cryptography, and information theory. This paper is devoted partly to the study of intersecting codes, and partly to their use in constructing large t-independent families of binary vectors. The latter subject has by now been extensively studied and has application in VLSI testing, defect correction, E-biased probability spaces, and derandomization. By concatenation methods we construct codes with the highest known fate asymptotically. We then generalize the concept to t-wise intersecting codes: we give bounds on the achievable rate of such codes, both existential and constructive. We show how t-wise intersecting codes can be used to obtain (t+1)-independent families. With this method we obtain improved asymptotical constructions of t-independent families. Complexity issues are discussed. >
---
paper_title: Software and Hardware Testing Using Combinatorial Covering Suites

paper_content:

In the 21st century our society is becoming more and more dependent on software systems. The safety of these systems and the quality of our lives is increasingly dependent on the quality of such systems. A key element in the manufacture and quality assurance process in software engineering is the testing of software and hardware systems. The construction of efficient combinatorial covering suites has important applications in the testing of hardware and software. In this paper we define the general problem, discuss the lower bounds on the size of covering suites, and give a series of constructions that achieve these bounds asymptotically. These constructions include the use of finite field theory, extremal set theory, group theory, coding theory, combinatorial recursive techniques, and other areas of computer science and mathematics. The study of these combinatorial covering suites is a fascinating example of the interplay between pure mathematics and the applied problems generated by software and hardware engineers. The wide range of mathematical techniques used, and the often unexpected applications of combinatorial covering suites make for a rewarding study.
---
paper_title: Constructing test suites for interaction testing

paper_content:

Software system faults are often caused by unexpected interactions among components. Yet the size of a test suite required to test all possible combinations of interactions can be prohibitive in even a moderately sized project. Instead, we may use pairwise or t-way testing to provide a guarantee that all pairs or t-way combinations of components are tested together This concept draws on methods used in statistical testing for manufacturing and has been extended to software system testing. A covering array, CA(N; t, k, v), is an N/spl times/k array on v symbols such that every N x t sub-array contains all ordered subsets from v symbols of size t at least once. The properties of these objects, however do not necessarily satisfy real software testing needs. Instead we examine a less studied object, the mixed level covering array and propose a new object, the variable strength covering array, which provides a more robust environment for software interaction testing. Initial results are presented suggesting that heuristic search techniques are more effective than some of the known greedy methods for finding smaller sized test suites. We present a discussion of an integrated approach for finding covering arrays and discuss how application of these techniques can be used to construct variable strength arrays.
---
paper_title: A density-based greedy algorithm for higher strength covering arrays

paper_content:

Algorithmic construction of software interaction test suites has focussed on pairwise coverage; less is known about the efficient construction of test suites for t-way interactions with t≥3. This study extends an efficient density-based algorithm for pairwise coverage to generate t-way interaction test suites and shows that it guarantees a logarithmic upper bound on the size of the test suites as a function of the number of factors. To complement this theoretical guarantee, an implementation is outlined and some practical improvements are made. Computational comparisons with other published methods are reported. Many of the results improve upon those in the literature. However, limitations on the ability of one-test-at-a-time algorithms are also identified. Copyright © 2008 John Wiley & Sons, Ltd.
---
paper_title: In-parameter-order: a test generation strategy for pairwise testing

paper_content:

Pairwise testing (or 2-way testing) is a specification-based testing criterion, which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. Empirical results show that pairwise testing is practical and effective for various types of software systems. We show that the problem of generating a minimum test set for pairwise testing is NP-complete. We propose a test generation strategy, called in-parameter-order (or IPO), for pairwise testing. For a system with two or more input parameters, the IPO strategy generates a pairwise test set for the first two parameters, extends the test set to generate a pairwise test set for the first three parameters, and continues to do so for each additional parameter. The IPO strategy allows the use of local optimization techniques for test generation and the reuse of existing tests when a system is extended with new parameters or new values of existing parameters. We present practical, IPO-based test generation algorithms. We describe the implementation of an IPO-based test generation tool and show some empirical results.
---
paper_title: Covering and radius-covering arrays: Constructions and classification

paper_content:

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.
---
paper_title: Vector sets for exhaustive testing of logic circuits

paper_content:

(L, d)-universal sets are useful for exhaustively testing logic circuits with a large number of functional components, designed so that every functional component depends on at most d inputs. Randomized and deterministic constructions of (L, d)-universal test sets are presented, and lower and upper bounds on the optimal sizes of such sets are proven. It is also proven that the design of an optimal exhaustive test set for an arbitrary logic circuit is an NP-complete problem. >
---
paper_title: Classification of orthogonal arrays by integer programming

paper_content:

Abstract The problem of classifying all isomorphism classes of OA ( N , k , s , t ) 's is shown to be equivalent to finding all isomorphism classes of non-negative integer solutions to a system of linear equations under the symmetry group of the system of equations. A branch-and-cut algorithm developed by Margot [2002. Pruning by isomorphism in branch-and-cut. Math. Programming Ser. A 94, 71–90; 2003a. Exploiting orbits in symmetric ILP. Math. Programming Ser. B 98, 3–21; 2003b. Small covering designs by branch-and-cut. Math. Programming Ser. B 94, 207–220; 2007. Symmetric ILP: coloring and small integers. Discrete Optim., 4, 40–62] for solving integer programming problems with large symmetry groups is used to find all non-isomorphic OA ( 24 , 7 , 2 , 2 ) 's, OA ( 24 , k , 2 , 3 ) 's for 6 ⩽ k ⩽ 11 , OA ( 32 , k , 2 , 3 ) 's for 6 ⩽ k ⩽ 11 , OA ( 40 , k , 2 , 3 ) 's for 6 ⩽ k ⩽ 10 , OA ( 48 , k , 2 , 3 ) 's for 6 ⩽ k ⩽ 8 , OA ( 56 , k , 2 , 3 ) 's, OA ( 80 , k , 2 , 4 ) 's, OA ( 112 , k , 2 , 4 ) 's, for k = 6 , 7 , OA ( 64 , k , 2 , 4 ) 's, OA ( 96 , k , 2 , 4 ) 's for k = 7 , 8 , and OA ( 144 , k , 2 , 4 ) 's for k = 8 , 9 . Further applications to classifying covering arrays with the minimum number of runs and packing arrays with the maximum number of runs are presented.
---
paper_title: Strong qualitative independence

paper_content:

The subsets A,B of the n-element X are said to be s-strongly separating if the two sets divide X into four sets of size at least s. The maximum number h(n,s) of pairwise s-strongly separating subsets was asymptotically determined by Frankl (Ars Combin. 1 (1976) 53) for fixed s and large n. A new proof is given. Also, estimates for h(n,cn) are found where c is a small constant.
---
paper_title: The Test Suite Generation Problem: Optimal Instances and Their Implications

paper_content:

In the test suite generation (TSG) problem for software systems, I is a set of n input parameters where each I@?I has @k(I) data values, and O is a collection of subsets of I where the interactions of the parameters in each O@?O are thought to affect the outcome of the system. A test case for (I,O,@k) is an n-tuple (t"1,t"2,...,t"n) that specifies the value of each input parameter in I. The goal is to generate a smallest-sized test suite (i.e., a set of test cases) that covers all combinations of each O@?O. The decision version of TSG is known to be NP-complete. In this paper, we present new families of (I,O,@k) for which optimal test suites can be constructed efficiently. They differ from the ones already known by the way we characterize (I,O) and @k. We then use these instances to generate test suites for arbitrary software systems. When each O@?O has |O|=2, the sizes of the test suite are guaranteed to be at most @?log"2n@?xOPT, matching the current best bound for this problem. Our constructions utilize the structure of (I,O) and @k; consequently, the less ''complex''(I,O) and @k are, the better are the bounds on the sizes of the test suites.
---
paper_title: Covering arrays on graphs

paper_content:

Two vectors v, w in Zgn are qualitatively independent if for all pairs (a, b) ∈ Zg × Zg there is a position i in the vectors where (a, b) = (vi, wi). A covering array on a graph G, CA (n, G, g), is a |V(G)| × n array on Zg with the property that any two rows which correspond to adjacent vertices in G are qualitatively independent. The smallest possible n is denoted by CAN(G, g). These are an extension of covering arrays. It is known that CAN(Kω(G), g) ≤ CAN(G, g) ≤ CAN(Kχ(G), g). The question we ask is, are there graphs with CAN(G, g) < CAN(Kχ(G), g)? We find an infinite family of graphs that satisfy this inequality. Further we define a family of graphs QI(n, g) that have the property that there exists a CAN(n, G, g) if and only if there is a homomorphism to QI(n, g). Hence, the family of graphs QI(n, g) defines a generalized colouring. For QI(n, 2), we find a formula for both the chromatic and clique number and determine two necessary conditions for CAN (G, 2) < CAN(Kχ(G), 2). We also find the cores of all the QI(n, 2) and use this to prove that the rows of any covering array with g = 2 can be assumed to have the same number of 1's.
---

Title: A Survey of Binary Covering Arrays

Section 1: Introduction
Description 1: This section introduces the basic concepts and definitions related to binary covering arrays and their importance in various applications.

Section 2: Various Formulations
Description 2: This section describes alternative terminologies, definitions, and operations applied to covering arrays, such as orthogonal arrays and t-surjective mappings.

Section 3: Known Values of CAN(k, t)
Description 3: This section presents the exact known values of CAN(k, t) for various parameters and the mathematical arguments behind these values.

Section 4: Bounds on CAN
Description 4: This section discusses lower and upper bounds on CAN(k, t), elucidating the theoretical limits and their derivations.

Section 5: Methods of Finding Covering Arrays
Description 5: This section reviews computational methods, heuristics, and constructive techniques utilized to discover or approximate covering arrays.

Section 6: Computational Complexity
Description 6: This section addresses the computational complexity-related decision problems associated with constructing covering arrays and determining CAN(k, t).

Section 7: Notes and Acknowledgments
Description 7: This section mentions additional topics, like v-valued arrays and radius covering arrays, provides acknowledgments, and recognizes contributions from reviewers and other experts.