Path Testing using Genetic Algorithm

Abstract

Software testing is a critical stage in the life cycle of software development. The testing process costs hundreds of billions of dollars per year worldwide. Therefore, even small improvements in it could lead to very large savings. In software, testing mainly refers to dynamic testing. It involves designing and generating proper test cases for the software, executing the software with these test cases, and observing the results. The aim is to find maximum number of errors with minimum number of test cases. Black-box testing involves seeing whether the program behaves as expected. White-box testing involves knowledge of the code, to see which parts of the software were exercised during program execution. This thesis is concerned with white-box testing. The strongest form of white-box testing is path testing, in which test data is sought that leads to all different execution paths through a program being exercised. Searching for an input datum in the program's input space that meets the path coverage criterion is a search problem. Evolutionary algorithms have proven to be suitable for searching for test data. The aim of this thesis is to evaluate and improve the use of genetic algorithms (GA) for path testing. First, the capability and limitations of GA-based path testing are identified. Next we investigate possible ways to improve GA for test data generation. The obtained results are a collection of test programs; a classification scheme for test programs; understanding key GA parameters and identifying an effective default GA parameter setup; understanding the effects of infeasible paths; a model that stops GA searching when it seems ineffective to keep going, saving time while still finding almost all feasible paths; and identifying an effective hybrid of GA and local search techniques. The results have the following implications: • The collection of test programs can serve as a testing benchmark for proposed software testing approaches. • The classification of test programs provides ways to group test programs with similar characteristics. • The key parameters are shown in order to be population size, allele range, and number of generations. Suitable default values for these parameters are identified, which can represent a common setup to be used with an unknown new test program. • The existence of infeasible paths is shown not to hinder the process of test data generation, rather it improves the performance by encouraging diversity in the population. This means that the costly task of analyzing target paths to identify and remove infeasible ones is not necessary. • The proposed stopping criteria can stop searching whenever it is not worth continuing because the likelihood of finding further paths is too low. It is shown to be effective in stopping searching quite early, while missing almost no feasible paths. One less arbitrary system parameter (maximum number of generations to search) can be removed as a result. • The hybrid GAs improve the performance both in terms of path coverage and number of generations required for the search.