Abstract

A good strategy to test a software component involves the generation of the whole set of cases that participate in its operation. While testing only individual values may not be enough, exhaustive testing of all possible combinations is not always feasible. An alternative technique to accomplish this goal is called combinatorial testing. Combinatorial testing is a method that can reduce cost and increase the effectiveness of software testing for many applications. It is based on constructing functional test-suites of economical size, which provide coverage of the most prevalent configurations. Covering arrays are combinatorial objects, that have been applied to do functional tests of software components. The use of covering arrays allows to test all the interactions, of a given size, among the input parameters using the minimum number of test cases.

For software testing, the fundamental problem is finding a covering array with the minimum possible number of rows, thus reducing the number of tests, the cost, and the time expended on the software testing process. Because of the importance of the construction of (near) optimal covering arrays, much research has been carried out in developing effective methods for constructing them. There are several reported methods for constructing these combinatorial models, among them are: (1) algebraic methods, recursive methods, (3) greedy methods, and (4) metaheuristics methods.


Metaheuristic methods, particularly through the application of simulated annealing has provided the most accurate results in several instances to date. Simulated annealing algorithm is a general-purpose stochastic optimization method that has proved to be an effective tool for approximating globally optimal solutions to many optimization problems. However, one of the major drawbacks of the simulated annealing is the time it requires to obtain good solutions.

In this thesis, we propose the development of an improved simulated annealing algorithm for constructing covering arrays of strength t >= 2 for their use in software interaction testing. In addition, we propose the use of Grid computing and Supercomputing to address the large amount of computing time necessary to obtain near-optimal covering arrays.