A Theoretical Runtime and Empirical Analysis of Different Alternating Variable Searches for Search-Based Testing

by Joseph Kempka, Phil McMinn and Dirk Sudholt

Genetic and Evolutionary Computation Conference (GECCO 2013)


A more recent and expanded journal version of this paper is available — see "Design and Analysis of Different Alternating Variable Searches for Search-Based Software Testing".


The Alternating Variable Method (AVM) has been shown to be a surprisingly effective and efficient means of generating branch- covering inputs for procedural programs. However, there has been little work that has sought to analyse the technique and further improve its performance. This paper proposes two new local searches that may be used in conjunction with the AVM, Geometric and Lattice Search. A theoretical runtime analysis shows that under certain conditions, the use of these searches is proven to outperform the original AVM. These theoretical results are confirmed by an empirical study with four programs, which shows that increases of ... [more]


Reference

Joseph Kempka, Phil McMinn and Dirk Sudholt. A Theoretical Runtime and Empirical Analysis of Different Alternating Variable Searches for Search-Based Testing. Genetic and Evolutionary Computation Conference (GECCO 2013), pp. 1445–1452, 2013


Bibtex Entry
@inproceedings{Kempka2013,
  author    = "Kempka, Joseph and McMinn, Phil and Sudholt, Dirk",
  title     = "A Theoretical Runtime and Empirical Analysis of Different Alternating Variable Searches for Search-Based Testing",
  booktitle = "Genetic and Evolutionary Computation Conference (GECCO 2013)",
  pages     = "1445--1452",
  year      = "2013",
  publisher = "ACM"
}