Optimizing Cost Function in Imperialist Competitive Algorithm for Path Coverage Problem in Software Testing

Abstract

Search-based optimization methods have been used for software engineering activities such as software testing. In the field of software testing, search-based test data generation refers to application of meta-heuristic optimization methods to generate test data that cover the code space of a program. Automatic test data generation that can cover all the paths of software is known as a major challenge. The paper establishes a new cost function for automatic test data generation, which can traverse the non-iterative paths of software control flow graphs. This function is later compared with similar cost functions proposed in other articles. The results indicate the superior performance of the proposed function. Still another innovation in this paper is the application of the Imperialist Competitive Algorithm in automatic test data generation along with the proposed cost function. Automatic test data generation is implemented through the Imperialist Competitive Algorithm as well as the Genetic and Particle Swarm Optimization Algorithms for three software programs with different search space sizes. The algorithms are compared with each other in terms of convergence speed, computational time, and local search. Test data generated by the proposed method has achieved better results than other algorithms in finding the number of non-iterative paths, the convergence speed and computational time with growing the searching space of the software's control flow graph.

Keywords

• software testing
• Imperialist Competitive Algorithm (ICA)
• test data generation
• Control Flow Graph (CFG)
• program complexity