A Theoretical and Empirical Analysis of Evolutionary Testing and Hill Climbing for Structural Test Data Generation

by Mark Harman and Phil McMinn

International Symposium on Software Testing and Analysis (ISSTA 2007)


A more recent and expanded journal version of this paper is available — see "A Theoretical and Empirical Study of Search Based Testing: Local, Global and Hybrid Search".


Evolutionary testing has been widely studied as a technique for automating the process of test case generation. However, to date, there has been no theoretical examination of when and why it works. Furthermore, the empirical evidence for the effectiveness of evolutionary testing consists largely of small scale laboratory studies. This paper presents a first theoretical analysis of the scenarios in which evolutionary algorithms are suitable for structural test case generation. The theory is backed up by an empirical study that considers real world programs, the search spaces of which are several orders of magnitude larger than those previously considered.


Reference

Mark Harman and Phil McMinn. A Theoretical and Empirical Analysis of Evolutionary Testing and Hill Climbing for Structural Test Data Generation. International Symposium on Software Testing and Analysis (ISSTA 2007), pp. 73–83, 2007


Bibtex Entry
@inproceedings{Harman2007,
  author    = "Harman, Mark and McMinn, Phil",
  title     = "A Theoretical and Empirical Analysis of Evolutionary Testing and Hill Climbing for Structural Test Data Generation",
  booktitle = "International Symposium on Software Testing and Analysis (ISSTA 2007)",
  pages     = "73--83",
  year      = "2007",
  publisher = "ACM"
}