A strategy for using genetic algorithms to automate branch and fault-based testing

Genetic algorithms have been used successfully to generate software test data automatically; all branches were covered with substantially fewer generated tests than simple random testing. We generated test sets which executed all branches in a variety of programs including a quadratic equation solver, remainder, linear and binary search procedures, and a triangle classifier comprising a system of five procedures. We regard the generation of test sets as a search through the input domain for appropriate inputs. The genetic algorithms generated test data to give 100% branch coverage in up to two orders of magnitude fewer tests than random testing. Whilst some of this benefit is offset by increased computation effort, the adequacy of the test data is improved by the genetic algorithm's ability to generate test sets which are at or close to the input subdomain boundaries. Genetic algorithms may be used for fault-based testing where faults associated with mistakes in branch predicates are revealed. The software has been deliberately seeded with faults in the branch predicates (i.e. mutation testing), and our system successfully killed 97% of the mutants.