Context: Genetic Algorithms are a popular search-based optimisation technique for automatically generating test inputs for structural coverage of a program, but there has been little work investigating the class of programs for which they will perform well. Objective: This paper presents and evaluates a series of program factors that are hypothesised to affect the performance of crossover, a key search operator in Genetic Algorithms, when searching for inputs that cover the branching structure of a C function. Method: Each program factor is evaluated with example programs using Genetic Algorithms with and without crossover. Experiments are also performed to test whether ... [more] crossover is acting as macro-mutation operator rather than usefully recombining the component parts of input vectors when searching for test data. Results: The results show that crossover has an impact for each of the program factors studied. Conclusion: It is concluded crossover plays an increasingly important role for programs with large, multi-dimensional input spaces, where the target structure’s input condition breaks down into independent sub-problems for which solutions may be sought in parallel. Furthermore, it is found that crossover can be inhibited when the program under test is unstructured or involves nested conditional statements; and when intermediate variables are used in branching conditions, as opposed to direct input values.

DOI

Bibtex Entry

@article{McMinn2013,
  author  = "McMinn, Phil",
  title   = "An Identification of Program Factors that Impact Crossover Performance in Evolutionary Test Input Generation for the Branch Coverage of {C} Programs",
  journal = "Information and Software Technology",
  volume  = "55",
  number  = "1",
  pages   = "153--172",
  year    = "2013"
}