Ariadne: evolving test data using grammatical evolution

Software testing is a key component in software quality assurance; it typically involves generating test data that exercises all instructions and tested conditions in a program and, due to its complexity, can consume as much as 50% of overall software development budget. Some evolutionary computing techniques have been successfully applied to automate the process of test data generation but no existing tech- niques exploit variable interdependencies in the process of test data gen- eration, even though several studies from the software testing litera- ture suggest that the variables examined in the branching conditions of real life programs are often interdependent on each other, for example, if (x==y), etc. We propose the Ariadne system which uses Grammatical Evolution (GE) and a simple Attribute Grammar to exploit the variable interdependen- cies in the process of test data generation. Our results show that Ariadne dramatically improves both e ectiveness and e ciency when compared with existing techniques based upon well-established criteria, attaining coverage (the standard software testing success metric for these sorts of problems) of 100% on all benchmarks with far fewer program evaluations (often between a third and a tenth of other systems).