Ariadne: Evolving test data using grammatical evolution

Heuristic-based optimization techniques have been increasingly used to automate different types of code coverage analysis. Several studies suggest that interdependencies (in the form of comparisons) may exist between the condition constructs of variables and constant values in the different branching conditions of real-world programs e.g. while(i <= 100) and if(i == j), etc. In this work, by interdependencies we refer to the situations where, in order to satisfy a branching condition, there must be a certain relationship between the values of some specific condition constructs (which may or may not be a part of the respective condition predicates). 

 We propose a Grammatical Evolution (GE)-based test data generator, Ariadne, which employs a novel seeding strategy. Our proposed system employs a simple attribute grammar to exploit different kinds of existing interdependencies (involving both variables and constant values) throughout the search process, which enables it to efficiently evolve complex test data. Our results demonstrate that Ariadne dramatically improves both effectiveness and efficiency when compared with existing GA-based techniques, based upon well-established criteria, attaining high levels of coverage (the standard software testing success metric for these sorts of problems) with far fewer fitness evaluations. Moreover, we also performed rigorous performance and scalability analyses to gain better insights about the working and performance of Ariadne and to examine its scalability, respectively. Our results suggest that the improvements achieved by Ariadne are highly cost-effective and that it remains highly scalable when compared to GA-based test data generation approach.