A Greedy based Approach for Generating Minimal Covering Array and Optimal Test Suit for Combinatorial Testing

Abstract

In software testing, a system have various factors like different configurations of hardware and software, or different types of input parameters and there values. If these factors have mutual interactions between them, and that may affect the software under test, then it is logical to test with a test suite covering all these factors and their interactions. But in such cases the necessary test suite is generally too large, making exhaustive testing usually impractical and often infeasible. As a result, we need to make a trade-off between testing efficiency and cost. One way to do this is to use Combinatorial Testing (CT), also called combinatorial interaction testing. Combinatorial testing is applied for finding errors which are triggered by the interaction of parameters (configuration parameters and input parameters) of the software applications. Errors occur, when the usage of the software increases and interaction between those parameters grows rapidly. Due to combinatorial explosion of values of parameters it is not possible to check all the possible combinations of values hence, pairwise testing provides an economical alternative to test all possible combinations of a set of variables/parameters. In pairwise testing a set of test cases is generated that covers all combinations of the selected test data values for each pair of variables. Finding the least number of test cases has been proven to be an NP-complete problem .This means that an efficient way to find an optimal solution is not known and that the time required finding a minimum number of test cases grows rapidly when the numbers of parameters and possible values increase. This thesis provides an algorithm and its implementation which tries to optimize the number of test case generated for combinatorial testing. All the results that have been obtained through this algorithm (applying on different number of parameters and there values) has been discussed at the end.