AuthorsA. Arcuri
EditorsO. Watanabe and T. Zeugmann
TitleTheoretical Analysis of Local Search in Software Testing
AfilliationSoftware Engineering, Software Engineering
Publication TypeProceedings, refereed
Year of Publication2009
Conference NameSymposium on Stochastic Algorithms, Foundations and Applications (SAGA)
ISBN NumberDOI: 10.1007/978-3-642-04944-6\_13

The {fi}eld of search based software engineering lacks of theoretical foundations. In this paper we theoretically analyse local search algorithms ap- plied to software testing. We consider an in{fi}nitely large class of software that has an easy search landscape. Although the search landscape is easy, the software can be arbitrarily complex and large. We prove that Hill Climbing asymptotically has a strictly better runtime than Random Search. However, we prove that a very fast variant of Hill Climbing on reasonable size of software actually does not scale up properly. Although that variant has an exponential runtime, we prove that asymptotically it is still better than Random Search. We show that even on the easiest software testing problems, more sophisticated algorithms than local search are still required to get better performance.

Citation KeySimula.SE.657