Test Case Generation For Mutation Testing Based On Set Evolution And Dominance Relation

Software testing is to seek faults in software,thus improving its quality.One of core issues in software testing is generating high-quality test cases so as to detect faults in software under test.As a fault-based testing technique,mutation testing can not only evaluate previous test cases,but also aid to generate new test cases with high-quality,with the criterion of killing a number of mutants generated in advance.However,the high cost of mutation testing resulted from a large number of mutants seriously affects its applications in practical software testing.Previous methods of test case generation based on mutation testing is of low efficiency,therefore it is necessary to develop new methods of generating test cases for mutation testing.Besides,mutant reduction is cost-efficient when generating test cases.Focusing on mutation testing,this dissertation develops new methods for test case generation so as to efficiently generate test cases with a high capability in detecting faults.To generate mutation based test cases,a set-based evolutionay method is proposed.The proposed method first combines the necessity conditions of killing mutants by the transformation method of weak mutation testing,and further constructs mutant branches by the combined conditions.Thus,the test cases that cover the true parts of mutant branches can kill the corresponding mutants in weak mutation testing.Then,all mutant branches are integrated into the original program to form the new program.The new program transforms the problem of killing mutants into the problem of covering mutant branches.A new mathematical model is built to generate test cases for the new program,and a solving process of the model can generate test cases to kill all mutants.Finally,when solving the above model by set-based evolution,the suitable fitness function and evolutionary strategy are designed.The proposed method saves the cost in generating test cases for mutation testing.A large number of mutant branches add high complexity to the new program,thus decreasing the efficiency of test case generation.To tackle this problem,a method is proposed for reducing mutants based on dominance relation.The proposed method analyzes the dominance relations between mutant branches in the new program.Since the test cases that cover the non-dominated mutant branches can also cover the dominated ones,the corresponding mutants of the dominated mutant branches are redundant,i.e.,the mutants corresponding to the non-dominated ones are those after reduction.When analyzing the non-dominated mutant branches,the dominance relation graph is built and the non-dominated mutant branches are identified according to the vertices with zero in-degree.The test cases generated by only covering the nondominated mutant branches can kill all mutants in weak mutation testing.The proposed method reduces the number of mutants and improves the efficiency of test case generation.In order to improve the efficiency of analyzing dominance relation between mutant branches and enhance the practicality of mutant reduction based on dominance relation,a statistical method is presented for detecting dominance relations.In the method,a statistical analysis model is built for automatically analyzing dominance relations between mutant branches by executing the new program against the given test cases,and the dominance relation graph is built after analyzing.The nondominated mutant branches are obtained according to the vertices with zero in-degree in the graph,and the corresponding mutants of the non-dominated mutant branches are those after reduction.The proposed method can automatically detect dominance relations so as to reduce mutants.Existing research shows that prioritized test cases which make the test cases with high capability of fault detection be early executed will reduce the cost in detecting faults in practical software testing.In view of this,a method based on dominance degree is proposed for generating test cases.In the proposed method,the concept of dominance degree is presented for determining the order of the non-dominated mutant branches to generate test cases.The dominance degree of a non-dominated mutant branch is the number of its dominated ones,i.e.,the out-degree of the vertex in the dominance relation graph corresponding to the non-dominated one.Two strategies are proposed based on dominance degree,so as to prioritize the non-dominated mutant branches to early generate test cases with high ability of fault detection.Additionally,a prototype system of set-based evolution for generating test cases is designed and implemented based on the built mathematical model,and the usage of the prototype is given in detail.The research of this dissertation enriches the theory of mutation testing,saves the cost of mutation testing and improves the efficiency of test case generation.