| Combinatorial testing (CT) has been shown to be a very effective testing strategy. Given a system with n parameters, t-way combinatorial testing, where t is typically much smaller than n, requires that all t-way combinations, i.e., all combinations involving any t parameter values, be covered by at least one test. This dissertation focuses on two important problems in combinatorial testing, including constrained test generation and combinatorial sequence testing.;For the first problem, we focus on constraint handling during combinatorial test generation. Constraints over input parameters are restrictions that must be satisfied in order for a test to be valid. Constraints can be handled either using constraint solving or using forbidden tuples. An efficient algorithm is proposed for constrained test generation using constraint solving. The proposed algorithm extends an existing combinatorial test generation algorithm that does not handle constraints, and includes several optimizations to improve the performance of constraint handling. Experimental results on both synthesized and real-life systems demonstrate the effectiveness of the propose algorithm and optimizations.;For the second problem, the domain of t-way testing is expanded from test data generation to test sequence generation. Many programs exhibit sequence-related behaviors. We first formally define the system model and coverage for t-way combinatorial sequence testing, and then propose four algorithms for test sequence generation. These algorithms have their own advantages and disadvantages, and can be used for different purposes and in different situations. We have developed a prototype tool that applies t-way sequence testing on Antidote, which is a healthcare data exchange protocol stack. Experimental results suggest that t-way sequence testing can be an effective approach for testing communication protocol implementations. |
