Random or Evolutionary Search for Object-Oriented Test Suite Generation?

An important aim in software testing is constructing a test suite with high structural code coverage
– that is, ensuring that most if not all of the code under test has been executed by the test cases
comprising the test suite. Several search-based techniques have proved successful at automatically
generating tests that achieve high coverage. However, despite the well-established arguments
behind using evolutionary search algorithms (e.g., genetic algorithms) in preference to random
search, it remains an open question whether the benefits can actually be observed in practice
when generating unit test suites for object-oriented classes. In this paper, we report an empirical
study on the effects of using evolutionary algorithms (including a genetic algorithm and chemical
reaction optimization) to generate test suites, compared with generating test suites incrementally
with random search. We apply the EVOSUITE unit test suite generator to 1,000 classes randomly
selected from the SF110 corpus of open source projects. Surprisingly, the results show that the
difference is much smaller than one might expect: While evolutionary search covers more branches
of the type where standard fitness functions provide guidance, we observed that, in practice, the
vast majority of branches do not provide any guidance to the search. These results suggest that,
although evolutionary algorithms are more effective at covering complex branches, a random
search may suffice to achieve high coverage of most object-oriented classes.