A survey of methods for constructing covering arrays

The paper presents a survey of methods for constructing covering arrays used in generation of tests for interfaces with a great number of parameters. The application domain of these methods and algorithms used in them are analyzed. Specific characteristics of the methods, including time complexity and estimates of the required memory, are presented. Various—direct, recursive, optimization, genetic, and backtracking—algorithms used for constructing covering arrays are presented. Heuristics are presented that allow one to reduce arrays without loss of completeness, and application domains of these heuristics are outlined.