| This dissertation presents new greedy algorithms to construct covering arrays, mixed-level covering arrays, and ℓ-biased covering arrays. The work on these algorithms is motivated by the application of software interaction testing.; Software systems today are complex and have numerous configurations. Exhaustive testing is often not possible due to limited testing resources. Software interaction testing complements current software testing methods with economical sized test suites that cover all t-way interactions. Covering arrays can represent these test suites.; Numerous methods exist to automatically construct covering arrays. This dissertation summarizes pre-existing methods and then advances ""one-row-at-a-time"" greedy algorithms. ""One-row-at-a-time"" greedy methods are the focus of this research because they are relatively quick and accurate, while providing flexibility for seeding, soft constraints, and prioritization.; Three new research contributions are presented. First, the Deterministic Density Algorithm (DDA) is introduced. It is the only greedy algorithm that generates covering arrays with a theoretical guarantee on the size of solutions. The guarantee does not hinder the competitiveness of the method in practice; computational results show that DDA often provides competitive, or better, solutions than other algorithms in its class.; Second, instead of developing yet another greedy algorithm, a framework for all ""one-row-at-a-time"" greedy algorithms is introduced. The framework provides a mechanism for developers to rapidly evaluate new algorithms of this type with statistical feedback. A large experiment is presented with several thousand instantiations of the framework. The data from this experiment serves as a repository that future developers can gain insight from. In addition, hybrid approaches of these algorithms combined with algebraic, heuristic search, and vertical-growth greedy algorithms are explored.; Finally, additional practical considerations of software interaction testing are introduced: prioritization, hard constraints, and soft constraints. An ℓ-biased covering array is used to represent test suites that adhere to prioritization and soft constraints. Priorities for the importance of covering interactions are modeled with weights, -1.0<o<1.0. The higher the weight associated with an interaction, the more desirable it is to include early in the test suite. On the contrary, a negative weight indicates a soft constraint, an interaction that is less desirable to include in a test suite. A new algorithm utilizes a simple heuristic with the primary goal of covering as much weight as possible, as early as possible, and avoiding negatively weighted interactions. Experimental results show the method to be effective. |
