Research And Application Of Combinatorial Testing

Software testing run through the entire software development cycle, which takes more than 40% of its workload. It is an important method to guarantee software quality. Software testing is a process that aims to find the error of software and execute software under test(SUT) it chooses different test case generation carefully strategies in order to generate test cases, then uses these test cases to find errors. In software testing process, the scale and the detection error ability of test suite determine the software testing effect directly. Therefore, how to choose a small scale and high error detection ability test suite is the core and key subject to software testing.Combinatorial testing strategy is an important test case generation technology, which impact to the system according to the the interaction among several input parameters of SUT and tests the SUT effectively with smaller test suite. The stragety can generate small-scale and high detection ability test suite.The aim of this thesis is to further improve the effect and practical applicatiable of combinatorial testing. Firstly, we make the futher study of the domestic and international combinatorial testing strategies. Then, we compare various strategeties, and select IPOG as our research object.The main contributions are as follows.1) In all existing combinatorial tesing strategies, once a parameter value was selected, the strategies just take it as the best choice, and no longer change it in the later extention process. On this occasion, we present a new combinatorial testing strategy. The strategy uses real-time feedback information of test case generation process to handle redundancy value timely, and get more optimal test suite. We also prove the validity of the algorithm by experiments.2) In some practical software systems, input parameters depends on each other, so we extend the improved algorithm and present a algorithm based on constrained combainatorial testing. The algorithm computes implied constraints firstly; then, removes constraints from uncovered combination set in each extension, and selects parameter values that not consitute a constraint until all the parameters extension ends. Experiment results demonstrate that this algorithm can not only handle the relationships among input parameters effectively but also generate more optimal test cases than other method based on constrained combinatorial testing.3) In some practical software systems, the interaction of input parameters may be very complicated and the strength of these interactions may be different, it is not always having interactions among any t input parameters; or there may be some interactions among input parameters more than t-way. In order to handle the complicated interactions, we make the further improve of the algorithm based on constrained combinatorial testing and present a variable strength combinatorial testing algorithm based on constraint and input/output (IO) relationship. The algorithm sorts the imput parameters according to the output parameters, and generates the test cases based on the classification.The ultimate goal of testing is to revise the errors, but the first thing is locating the combinations that induce errors before the revision. We improve a test data supplement generated based error localization method, and propose a new error localization method. This method generates error modes according to IO relationship, rather than generating all error modes for each test case. Experiments show that the method improves the efficiency of error location.4) In the end of the thesis, we select programs that are written in c++ language as our research object, and make the further extention of the variable strength combinatorial testing based on constraint and input/output (IO) relationship. Because pointer is one of the characteristics of the C++ language, points-to information unclear leads to conservative estimate of IO relationships, further affects the accuracy of them. So we propose a method to get accurate points-to information. The method improves the inclusion-based pointer analysis method by extending the language of inclusion constraints. Experimental results show that this method can analyzes points-to information accurately at any level. On the basis of pointer analysis, we give a combinatorial testing method that is using gray box testing strategy. The method considers part internal structures of SUT when generates test cases, which optimizes the test suite and also improves the error location ability.