Approche basee sur l'intelligence collective pour la generation de donnees de test par mutation.

摘要

In many software organizations software testing accounts for more than 40-50% of the total development costs. Also, testing and test case generation are among the most labor intensive and technically difficult activities in any software project. So, techniques reducing the need for manual intervention will positively affect project costs. Indeed, thorough testing is often unfeasible because of the potentially infinite execution space or high cost with respect to tight budget limitations. Other techniques such as code inspection are known to be more effective, but even more costly than testing. Unfortunately, defects slipped into deployed software may crash safety or mission critical applications with catastrophic consequences. Mutation testing, originally proposed by DeMillo in 1978, consists in injecting simple faults into the original program in order to obtain faulty versions of the program: the mutants. Then, test data are produced to attain the highest possible mutation score, i.e., to kill the highest number of mutants. A mutant is said to be killed if it behaves in a different way than the original program for the same test data. A set of test cases is more adequate than another if it kills a larger number of mutants. On the other hand, a test suite is preferred over others if it contains fewer test cases and is closer to the adequacy criterion. In this case, the adequacy criterion is having the highest mutation score. Intuitively, mutation testing promotes high quality test suites and has high potential for automation. In this thesis, we address the problem of automatic test data generation, as it is a computational expensive activity in the testing process.;This work summarizes the use of a swarm intelligence approach in order to generate data that kills mutants in the context of mutation testing. In the technique proposed in this thesis, test data generation is mapped into a minimization problem guided by a cost function, a fitness function inspired by Bottaci work. The Bottaci fitness function is defined in a way that a test case is able to kill a mutant if it satisfies three conditions used by Offutt in CBT, namely, the reachability, the necessary and the sufficiency conditions. Indeed, this fitness function measures how close a test case is to kill a mutant. This thesis adopted Ant Colony Optimization (ACO) as the metaheuristic algorithm to solve the minimization problem. Two reasons justify our choice. First, metaheuristics have been proven to be suitable approaches for data generation in the context of coverage based testing. Second, ACO leads to implement the well-known "do smarter" approaches in a natural way because ACO intrinsically allows a parallel search. In this thesis ants have the mission of killing one mutant each time by searching a test data that satisfies the three Offutt conditions. Furthermore, our ACO algorithm is enhanced by a probability density estimation process that automatically guides and refines the search in promising regions. This thesis main contributions and innovations are: (1) A new swarm intelligence approach for automatic test data generation in the context of mutation testing, which naturally reduces the computational cost in such test strategy; (2) Exploitation of a new emergent search technique, ACO, to facilitate test data generation and compare results with Hill Climbing, Genetic Algorithm and random search on two programs; (3) Incorporation of new ideas based on a probability density estimation process to automatically define and guide the search toward promising regions; (4) A customization of ACO to the problem of generating test data to kill mutants.;This thesis demonstrates that ACO performed far better than the other metaheuristics we implemented.