Skip to content

Software Quality

Regression test selection

Regression test selection asks, for a specific change, which tests could behave differently, and skips the rest for this run. Nothing is deleted; the unselected tests remain for the next change.

What it does

Among the regression-suite management techniques, selection is the one whose value turns on safety: a safe technique selects every test whose output the change could alter (Rothermel and Harrold 1997)1. The original safe technique compares the control-flow graphs of the old and new program and selects any test whose execution path crosses a changed edge.

Dependency-based selection

Modern practical selection works at coarser granularity, trading precision for a cheaper, more robust analysis:

  • Dynamic file dependencies. Ekstazi records, per test, the set of files (classes) it actually accessed during its last run; on the next change it re-runs a test only if one of its recorded dependencies changed (Gligoric et al. 2015)2. File-level granularity makes the dependency set cheap to collect and store, and robust to refactors that break finer, statement-level analysis.
  • Static class firewalls. STARTS computes the dependency graph statically from type relationships and selects the transitive closure of changed classes, avoiding the need to run tests to learn their dependencies at the cost of selecting somewhat more.

The catch is inherent: when a change touches a widely-used core file, its dependents are most of the codebase, and a safe technique correctly selects most of the suite. Selection pays off in proportion to how local changes are, and buys nothing on a sweeping refactor.

Predictive selection at scale

At the scale of a monorepo taking millions of test runs a day, even dependency-based selection is too coarse, and the field moved to machine-learned, deliberately unsafe selection. Facebook's predictive test selection trains a gradient-boosted model on the historical record of (change, test, outcome) tuples, using features such as the file-path distance between the change and the test and the test's recent failure rate, then runs only the tests the model predicts a given diff will break (Machalica et al. 2019)3. The model is tuned to a target recall of failures rather than to coverage: the operators pick a tolerable probability of missing a real failure (a small fraction of a percent) and accept it in exchange for running a small fraction of the suite. The approach needs a large failure history to train on and cannot anticipate a failure mode it has never seen, which is why it is layered on top of, not in place of, periodic full runs.

Google's continuous-integration work combines dependency-based selection with time-window heuristics (run what changed, plus what failed in the recent past) to keep a very large suite tractable per commit (Elbaum et al. 2014)4.

Tools

Tool Notes
Ekstazi Dynamic, file-level RTS for JVM/Maven projects; records per-test file dependencies and re-runs only affected tests.
STARTS Static, class-firewall RTS for Maven; no instrumentation run needed, selects a slightly larger set than Ekstazi.
CI-native selection Bazel's target-graph test filtering, and the "affected tests" features of hosted CI, are dependency-based selection built into the build tool.

When to use, when not

Use it when changes are local and the suite is slow. A safe, dependency-based technique (Ekstazi) on a modular codebase cuts most of the run on a typical small change. Predictive selection is justified only at large scale, and only with a rich failure history.

Unsafe selection is not a line of defense on its own. A tuned-recall model will eventually skip a test that would have failed, so a full run stays in the loop.

Evidence

  • Predictive selection trades a measured miss rate for a large reduction. Facebook reported running a small fraction of the suite while capturing the large majority of individually-failing test outcomes, at a deliberately chosen, non-zero probability of missing a failure (Machalica et al. 2019)3. It is a statistical optimization, not a guarantee.

Classification

  • Quality dimensions: Maintainability (bounds the compute cost of regression testing per change by skipping unaffected tests) — picks, per change, the subset of tests that change could affect and skips the rest; it schedules tests, it does not run or verify them, so it sits off the code-verification axes.
  • Area: Regression suites large or slow enough that running all of them on every change costs too much: continuous-integration pipelines and monorepos.

Referenced by

References

  1. Rothermel, Gregg, and Mary Jean Harrold. 1997. "A Safe, Efficient Regression Test Selection Technique." ACM Transactions on Software Engineering and Methodology 6 (2): 173–210. https://doi.org/10.1145/248233.248262. ↩

  2. Gligoric, Milos, Lamyaa Eloussi, and Darko Marinov. 2015. "Practical Regression Test Selection with Dynamic File Dependencies." Proceedings of the 2015 International Symposium on Software Testing and Analysis (ISSTA 2015), 211–22. https://doi.org/10.1145/2771783.2771784. ↩

  3. Machalica, Mateusz, Alex Samylkin, Meredith Porth, and Satish Chandra. 2019. "Predictive Test Selection." 2019 IEEE/ACM 41st International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), 91–100. https://doi.org/10.1109/ICSE-SEIP.2019.00018. ↩↩

  4. Elbaum, Sebastian, Gregg Rothermel, and John Penix. 2014. "Techniques for Improving Regression Testing in Continuous Integration Development Environments." Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2014), 235–45. https://doi.org/10.1145/2635868.2635910. ↩