Applying Combinatorial Testing To Systems With A Complex Input Space

Abstract

Combinatorial testing, which has been shown very effective in fault detection, is a testing strategy that applies the theory of combinatorial design to test software programs. Given a program under test with k parameters, t-way combinatorial testing requires all combinations of values of t (out of k) parameters be covered at least once, where t is usually a small integer. Combinatorial testing can significantly reduce the cost of testing while increasing its effectiveness.Input space modeling is an important step in combinatorial testing. The input space of a subject program must be modeled before combinatorial testing can be applied to it. The effectiveness of combinatorial testing to a large extent depends on the quality of the input space model. If the input space is modeled perfectly, all faults caused by interactions involving no more than t parameters will be detected. In this dissertation, we develop an input space modeling methodology for combinatorial testing. The main idea is to consider the process of input space modeling as two steps, including input structure modeling and input parameter modeling. The first step tries to capture the structural relationship among different components in the input space. The second step tries to identify parameters, values, relations and constraints for individual components. We present several case studies of applying the proposed methodology to five real-life programs. These studies are designed to validate the proposed methodology in a practical setting. They are also designed to evaluate the effectiveness of combinatorial testing applied to real-life programs. We compare the proposed methodology to two random approaches: (1) pure-random, which generates test sets with minimum effort on modeling; and (2) modeled-random, which generates random tests from the same model created by the proposed methodology. The results show that proposed approach is more effective than the modeled-random approach, which is significantly more effective than the pure-random approach.