The application of metaheuristic search techniques to the automatic generation of software test data has been shown to be an effective approach for a variety of testing criteria. However, for structural testing, the dependence of a target structure on nested decision statements can cause efficiency problems for the search, and failure in severe cases. This is because all information useful for guiding the search - in the form of the values of variables at branching predicates - is only gradually made available as each nested conditional is satisfied, one after the other. The provision of guidance is further restricted by ... [more] the fact that the path up to that conditional must be maintained by obeying the constraints imposed by ‘earlier’ conditionals. An empirical study presented in this paper shows the prevalence of types of if statement pairs in real-world code, where the second if statement in the pair is nested within the first. A testability transformation is proposed in order to circumvent the problem. The transformation allows all branch predicate information to be evaluated at the same time, regardless of whether ‘earlier’ predicates in the sequence of nested conditionals have been satisfied or not. An experimental study is then presented, which shows the power of the approach, comparing evolutionary search with transformed and untransformed versions of two programs with nested target structures. In the first case, the evolutionary search finds test data in half the time for the transformed program compared to the original version. In the second case, the evolutionary search can only find test data with the transformed version of the program.

Bibtex Entry

@inproceedings{McMinn2005,
  author    = "McMinn, Phil and Binkley, David and Harman, Mark",
  title     = "Testability Transformation for Efficient Automated Test Data Search in the Presence of Nesting",
  booktitle = "UK Software Testing Workshop (UKTest 2005)",
  pages     = "165--182",
  year      = "2005"
}