A Buffered Genetic Algorithm for Automated Branch Coverage in Software Testing

摘要

Each and every software product has to be tested for assess its quality, which is time-consuming if it is performed manually. Moreover, it is difficult to generate all possible data for finite testing set. Search based Software Testing (SBST) are used to resolve this issue by utilizing metaheuristic algorithms to automate the test data generation. Hence, an efficient test data set could be generated with minimum cost. Among many metaheuristic algorithms, Genetic Algorithm (GA) is widely used for test data generation. This research work implements GA for generating test data to execute all the branches in a program. In the literature, existing approaches for test data generation using genetic algorithms are starts with random test data and find the optimum test data for a targeted branch. Then the entire GA process will be repeated to find the test data for the next target branch and it continues for all the target branches. In this a paper, a novel GA approach with a small buffer space is proposed for automated test data generation for branch coverage. When GA is searching test data for a particular target branch heuristically, it may reach the other target branches, if so happen, then those test data will get stored into the buffer space hence it is not necessary to run GA to cover that branch. Thus the Buffered Genetic Algorithm (BGA) approach outperforms the other GA based automated test data generation approaches in terms of number of iterations and search effectiveness. The proposed approach employs control flow graph to traverse and predicate the branch coverage. Seven benchmark programs are instrumented to evaluate performance of the proposed BGA based approach.