Title
Test Data Generation for Evolutionary Mutation Testing of Object-Oriented Programs.
Abstract
Software testing aims to identify bugs in the software under test to raise its quality and to ensure its correctness and usefulness for the user. It is an important phase of software development life-cycle and it consumes most of the resources in terms of time and money. Among all the activities of software testing, the test case generation consumes most of the effort and can be laborious if software testers perform it manually. Automatic generation of test cases can help in reducing the amount of resources and the effort this activity requires. Mutation testing can be very useful in generating effective test cases that can catch injected faults from the program under test. Besides that mutation testing is useful in measuring the effectiveness of given test suite. Mutation testing is computationally expensive because it requires execution of a large number of mutant programs while generating test cases. Evolutionary testing techniques (like genetic algorithm) can be used with mutation testing to reduce the computational overhead. This leads to a new testing technique named as evolutionary mutation testing that aims to automatically generate test cases using a genetic algorithm to kill non-equivalent mutants. During the test case generation, the performance of genetic algorithm depends on guidance that it gets from its fitness function.
An object-oriented program has two main components; data (object’s state) and control (execution path). The fitness function should consider objects state as well as control flow information of the program under test to correctly evaluate a test case and to provide better guidance to genetic algorithm. Otherwise the process can become stuck or random at times in absence of enough guidance.
There exist several evolutionary mutation testing techniques in literature. The literature survey shows that although existing mutation based testing techniques cover some important aspects of program and use the information to evaluate fitness of a test case yet none of them uses object’s state and control-flow information of program for fitness evaluation. The conventional crossover method generates two offsprings from parents by merging first segment of a parent to the second segment of the other and vice versa. This merger usually occurs at a randomly selected crossover point. This type of crossover can actually generate four offsprings by combing first segment of a parent to both the segments (first and second) of the other and vice versa.
Experiments show that this type of crossover can help exploring the input domain comprehensively. But none of the existing evolutionary testing techniques uses this method. Existing evolutionary mutation testing techniques use a fixed rate of biological mutation in genetic algorithm. In some cases more random effect is required to generate the required input values that crossover cannot produce. But since mutation rate is fixed, search process has to wait for biological mutation’s turn and hence unnecessary crossover wastes some effort.
In this thesis, we target object-oriented programs and present four proposals to improve evolutionary mutation testing process. We have applied these proposals on genetic algorithm to reduce test case generation effort. The first two improvements are related to fitness function where we propose evaluating object’s state and control flow information as part of the test case fitness. With the help of object’s state fitness, it becomes easier to check if a given test case is able to achieve the desired state of an object or if it requires further improvement. On the other hand using control flow information of both original and mutated programs, fitness function checks if mutated program is exercising expected behavior on a test case. Sometimes this information helps in identifying logical programming errors (bugs) in the program. The third proposal is introduction of new two-way crossover method to evolve test cases using object’s state fitness so they converge towards the target quickly. Finally we propose using an adaptable mutation rate during execution of genetic algorithm that adjusts according to the situation and saves testing effort.
In the later part of this thesis we present the proof of concept tool eMuJava that stands for evolutionary Mutation testing of Java programs. We have performed extensive experiments using this tool to compare our proposed approach with other approaches. We have also compared the results with EvoSuite, which is the most related tool we have found in literature. Our proposed approach is able to increase mutation scores ranging from 6% to 10% im comparison to other testing techniques (random testing and two variants of genetic algorithm). The results show that our proposals help improving the evolutionary mutation testing by reducing the amount of time required to achieve the targets.