# Search-based software testing (SBST) Search-based software testing (SBST) casts a testing activity as an *optimization* problem (McMinn 2004)[^mcminn2004]. It searches for a solution with a metaheuristic, usually a genetic algorithm. Finding an input that reaches a hard-to-hit branch, a scenario that violates a safety envelope, and a workload that maximizes running time are all searches. On the input axis SBST is `generative → feedback`. An application of the paradigm is fixed by three choices: - **A representation** — what a candidate is and how it is encoded: a call sequence, an input signal, a driving scenario, a UI event trace. - **A fitness function** — how close a candidate comes to the goal. - **Search operators** — how a candidate mutates and how two recombine, so a population evolves toward higher fitness. SBST is a paradigm, not a single method: the input axis is the only one it fixes. Each application is a concrete method carrying its own oracle and guarantee. ## The fitness function makes it work A naive score — "did the candidate meet the goal, yes or no" — is flat: almost every random candidate scores zero, so there is no gradient for the search to climb. SBST instead scores *how close* a candidate came. For branch coverage the fitness function combines two parts (McMinn 2004)[^mcminn2004]: - **Approach level** counts how many of the target's enclosing decisions the execution got past before diverging. - **Branch distance** measures how close the deciding predicate came to the wanted outcome. For `if (a == b)`, a run where `a` and `b` differ by 2 is closer than one where they differ by 2000, so the distance is a function of `|a - b|`. Other domains supply their own metric: the negative robustness of a temporal-logic property, distance to a collision, elapsed running time. In each the metric converts a pass/fail wall into a smooth landscape the search can climb, which is what lets a genetic algorithm reach goals random generation almost never hits. ## Relationship to fuzzing Coverage-guided [fuzzing](https://quality.stereobooster.com/fuzzing.md) sits at the same input coordinate, `generative → feedback`: both maintain a population, mutate candidates, and keep those a feedback signal rewards. Neither paradigm contains the other. Black-box fuzzing is `generative → random`, pure sampling with no search at all; much of SBST — unit-suite generation, signal falsification, scenario search — is not fuzzing. Where they overlap, what differs is the *granularity* of the guidance: SBST engineers a distance gradient (branch distance), while classic gray-box fuzzing uses a coarse new-edge/no-new-edge signal. Modern fuzzers are eroding that boundary, with input-to-state correspondence and comparison splitting adding gradient-like guidance. ## Applications The paradigm reappears wherever a testing goal can be scored and the candidate space is too large to enumerate: - **Unit-test generation** — evolve call sequences to cover branches and emit a regression suite: [automated test generation](https://quality.stereobooster.com/automated-test-generation.md) (EvoSuite, Pynguin). - **Temporal-logic falsification** — search input signals to a cyber-physical system for one that violates a specification, with negative robustness as the fitness: [temporal-logic falsification](https://quality.stereobooster.com/temporal-logic-falsification.md). - **Scenario search for autonomous systems** — evolve driving scenarios to find safety violations: [testing autonomous systems](https://quality.stereobooster.com/testing-autonomous-systems.md). - **Adversarial-example generation** — search for input perturbations that flip a model's output, with a robustness property as the oracle: [testing ML systems](https://quality.stereobooster.com/testing-ml-systems.md). - **GUI and mobile exploration** — multi-objective search over event sequences, maximizing coverage and crashes while minimizing sequence length, as in Sapienz: [testing GUI and mobile apps](https://quality.stereobooster.com/testing-gui-and-mobile-apps.md). - **Performance and complexity** — search for worst-case inputs that maximize execution cost: [algorithmic complexity testing](https://quality.stereobooster.com/algorithmic-complexity.md) (PerfFuzz, SlowFuzz). Only unit-test generation emits source code, because only there is the candidate itself a program fragment. The rest yield an input, a signal, or a scenario at runtime, exactly as a fuzzer does. ## Evidence - **Whole-suite and many-objective search raise branch coverage** — measured against targeting one branch at a time, for unit-suite generation (Fraser and Arcuri 2013; Panichella et al. 2018)[^fraser2013] [^panichella2018]. - **Scope.** Coverage, or robustness, or elapsed time is the objective the search optimizes, and optimizing it well is not the same as catching real faults. The [automated test generation](https://quality.stereobooster.com/automated-test-generation.md) evidence measures that gap for regression suites. ## Referenced by - [Input](https://quality.stereobooster.com/input.md) · The axes - [Automated test generation](https://quality.stereobooster.com/automated-test-generation.md) · Methods - [Temporal-logic falsification](https://quality.stereobooster.com/temporal-logic-falsification.md) · Methods - [Testing GUI and mobile applications](https://quality.stereobooster.com/testing-gui-and-mobile-apps.md) · Methods - [Testing autonomous and cyber-physical systems](https://quality.stereobooster.com/testing-autonomous-systems.md) · Methods - [Testing machine-learning systems](https://quality.stereobooster.com/testing-ml-systems.md) · Methods - [Verifying numerical code](https://quality.stereobooster.com/numbers.md) · Methods - [Conventional terminology](https://quality.stereobooster.com/terminology.md) · Conventional ## References [^mcminn2004]: McMinn, Phil. 2004. "[Search-Based Software Test Data Generation: A Survey](https://philmcminn.com/publications/mcminn2004.pdf)." *Software Testing, Verification and Reliability* 14 (2): 105–56. . [^fraser2013]: Fraser, Gordon, and Andrea Arcuri. 2013. "[Whole Test Suite Generation](https://www.evosuite.org/wp-content/papercite-data/pdf/tse12_evosuite.pdf)." *IEEE Transactions on Software Engineering* 39 (2): 276–91. . [^panichella2018]: Panichella, Annibale, Fitsum Meshesha Kifetew, and Paolo Tonella. 2018. "[Automated Test Case Generation as a Many-Objective Optimisation Problem with Dynamic Selection of the Targets](https://orbilu.uni.lu/bitstream/10993/30978/1/tse2017.pdf)." *IEEE Transactions on Software Engineering* 44 (2): 122–58. . ## Acronyms - SBST — search-based software testing