Test-data generation directed by program path coverage through imperialist competitive algorithm

Abstract

Path coverage testing is an approach to ensure all paths of a program from starting node to terminal node are traversed at least once. Such testing considerably helps reveal program faults. However, disregarding iterated paths in loops, any module of a program with n decisions can have up to 2 n paths. Therefore, finding adequate test data to cover all or most of such paths throughout a program with numerous modules is an NP-Hard problem because it requires an exhaustive search among all possible data. Another concern is determining the efficiency and adequacy of test data according to the coverage criterion. For the path coverage criterion, a test data set is fully efficient if each item of the set covers a separate program path and is fully adequate if the test data cover all program paths. Providing such test data for a program is a very time-consuming action when the program has high complexity (i.e., many paths). A candidate solution for these problems is using Evolutionary Algorithms (EAs). We use an EA named the Imperialist Competitive Algorithm (ICA) to generate test data and assess its effectiveness based on both path coverage and discovered faults. The focus here is on the EA cost function, because it influences the generation of adequate test data. Considering the nondeterministic nature of the EAs in data reproduction, several experiments are carried out by applying statistical tests, ANOVA and T-test to indicate the significant difference between them in producing efficient test data.