Skip to content

Software Quality

Search-based software testing (SBST)

Search-based software testing (SBST) casts a testing activity as an optimization problem (McMinn 2004)1. 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)1:

  • 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 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 (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.
  • Scenario search for autonomous systems — evolve driving scenarios to find safety violations: testing autonomous systems.
  • Adversarial-example generation — search for input perturbations that flip a model's output, with a robustness property as the oracle: testing ML systems.
  • 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.
  • Performance and complexity — search for worst-case inputs that maximize execution cost: algorithmic complexity testing (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)2 3.
  • 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 evidence measures that gap for regression suites.

Referenced by

References

  1. McMinn, Phil. 2004. "Search-Based Software Test Data Generation: A Survey." Software Testing, Verification and Reliability 14 (2): 105–56. https://doi.org/10.1002/stvr.294. ↩↩

  2. Fraser, Gordon, and Andrea Arcuri. 2013. "Whole Test Suite Generation." IEEE Transactions on Software Engineering 39 (2): 276–91. https://doi.org/10.1109/TSE.2012.14. ↩

  3. 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." IEEE Transactions on Software Engineering 44 (2): 122–58. https://doi.org/10.1109/TSE.2017.2663435. ↩