Skip to content

Software Quality

Regression test selection

Regression test selection runs only the tests a specific change could affect and skips the rest for that 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 misses no test able to expose a fault in the changed program. 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 (Rothermel and Harrold 1997)1.

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 it actually accessed during its last run; on the next change it re-runs a test only if one of its recorded dependencies changed. File-level granularity selects more tests than method- or basic-block-level techniques, yet Ekstazi's end-to-end test time is lower than theirs (Gligoric et al. 2015)2.
  • Static class firewalls. A class firewall infers each test's dependencies by static analysis of the inheritance and reference relationships between classes, and re-runs any test that transitively depends on a changed class. No test has to run to record its dependencies, at the cost of selecting more tests on average than Ekstazi (Legunsen et al. 2016)3.

The limit 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 monorepo scale even dependency-based selection is too coarse, and Facebook moved to machine-learned, deliberately unsafe selection. Its predictive test selection trains a gradient-boosted model on the historical record of (change, test, outcome) tuples, using features such as the distance between the changed files and the test and the test's recent failure rate, then runs only the tests the model predicts a given diff will break. The model is calibrated to a target recall of failures: the operators pick how many real failures they tolerate missing. The approach needs a large failure history to train on, and it runs on top of, not in place of, a full run of every test every few hours, which catches what selection missed (Machalica et al. 2019)4.

On Google's continuous-integration data, selection by time window replaces coverage-based selection before submission: a test suite runs if it failed recently, has not run recently, or is new (Elbaum et al. 2014)5.

Tools

Tool Notes
Ekstazi Dynamic, file-level RTS for JVM/Maven projects.
STARTS Static, class-firewall RTS for Maven projects.
Bazel Build tool that caches each test's result against the test target's transitive inputs and re-runs only tests whose inputs changed: dependency-based selection built into the build.

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 shortens 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

  • File-level dependency selection shortens the end-to-end run. On 615 revisions of 32 open-source Java projects, Ekstazi reduced end-to-end testing time by 32% on average against running every test, and by 54% on the longer-running suites (Gligoric et al. 2015)2.
  • Predictive selection trades a measured miss rate for a large reduction. Facebook's model selects fewer than a third of the tests build dependencies would select and still reports over 95% of individual test failures and over 99.9% of faulty changes, at a miss rate the operators chose (Machalica et al. 2019)4. 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. Legunsen, Owolabi, Farah Hariri, August Shi, Yafeng Lu, Lingming Zhang, and Darko Marinov. 2016. "An Extensive Study of Static Regression Test Selection in Modern Software Evolution." Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE). https://doi.org/10.1145/2950290.2950361. ↩

  4. 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. ↩↩

  5. 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. ↩