Research On Combinatorial Testing Technique And Its Application

Software testing is a key method to guarantee the quality of software under test. But software testing faces many challenges, such as the modeling techniques of software artifacts, the design of test adequacy criterion, the effective test case gen-eration techniques, regression testing, and mutation testing. Combinatorial testing (also known as interaction testing) is an important test case generation technique and is widely researched by many researchers. After modeling the software under test, testers can get an instance composed of factors and values. Combinatorial test-ing can generate test suites with small size by covering interactions of a few factors. Some empirical studies also show that it can effectively reduce the test suite size but still keep high fault detection ability in some testing scenarios. However, the construction of the optimal combinatorial test suite is demonstrated to be NP-hard.In this dissertation, we systematically review the related work of combinato-rial testing technique and its applications. For traditional pairwise testing and its variants, we propose several effective test suite construction algorithms based on meta-heuristic search techniques. For test suite reduction in regression testing, we propose a test suite reduction approach based on pairwise interaction of test require-ments. The contributions of this dissertation can be summarized as follows:(1) For traditional pairwise testing issue, we propose a framework of particle swarm optimization based pairwise testing. To generate a single test case, we apply particle swarm optimization aiming to cover more interactions. Meanwhile we dis-cuss the reasonable settings of search space, fitness function, and heuristics. Based on the above algorithm, we propose two different test suite construction algorithms. One is based on one-test-at-a-time strategy, the other is based on IPO-like strategy. In our empirical study, we analyze the impact factors in our framework and make a comparison with other well-known approaches to show the effectiveness of our framework.(2) For the variant issues of combinatorial testing, we extend the application of ant colony optimization in traditional combinatorial testing to support the con-struction of prioritized combinatorial test suites and variable strength combinatorial test suites. In particular, to build prioritized combinatorial test suites, we use one-test-at-a-time strategy. To generate a single test case, we propose four concrete ant colony optimization strategies (AS, ASelite, ACS, and MM AS) and discuss the set-tings of heuristics. In the part of case studies, we compare our approach to a classical greedy approach WDA (Weighted Density Algorithm) and also make a comparison among these four different approaches. To build variable strength combinatorial test suites, we also use one-test-at-a-time strategy. To generate a single test case, we apply ant colony system (ACS) strategy aiming to cover more interactions and discuss the settings of heuristics. After the test suite is constructed, we can use a test suite minimization algorithm to further reduce this test suite size. In the final case studies, we compare this approach to some classical approaches and tools to show the effectiveness of our approach.(3) For the test suite reduction issue in regression testing, most of traditional test suite reduction approaches only consider the coverage of individual test require-ment, but these approaches may significantly lose fault detection ability of original test suites. We propose a lightweight test suite reduction approach PWIR. In this approach, we consider the coverage of pairwise interaction of test requirements. In our empirical study, we use the Siemens suite as our subjects and find that this approach can effectively increase the fault detection ability of reduced test suite by adding only a few test cases.