A Theoretical and Empirical Study of Search-Based Testing: Local, Global, and Hybrid Search

TLDR

Search‑based optimization has been applied to software test data generation since 1992, yet theoretical analysis and large‑scale empirical studies remain scarce. This paper aims to theoretically explore genetic algorithms as a global search technique and to empirically compare global and local search on real‑world programs. The authors theoretically analyze genetic algorithms for global search, conduct a large empirical comparison of global versus local search on real‑world programs, and introduce a Memetic Algorithm whose performance is evaluated. The study finds that certain test data generation problems favor either global or local search, supporting the use of a hybrid Memetic Algorithm, whose empirical evaluation demonstrates improved performance.

Abstract

Search-based optimization techniques have been applied to structural software test data generation since 1992, with a recent upsurge in interest and activity within this area. However, despite the large number of recent studies on the applicability of different search-based optimization approaches, there has been very little theoretical analysis of the types of testing problem for which these techniques are well suited. There are also few empirical studies that present results for larger programs. This paper presents a theoretical exploration of the most widely studied approach, the global search technique embodied by Genetic Algorithms. It also presents results from a large empirical study that compares the behavior of both global and local search-based optimization on real-world programs. The results of this study reveal that cases exist of test data generation problem that suit each algorithm, thereby suggesting that a hybrid global-local search (a Memetic Algorithm) may be appropriate. The paper presents a Memetic Algorithm along with further empirical results studying its performance.