PaperlayerView exact revision on arXiv

Source-linked AI summary

Predictive Test Selection

Mateusz Machalica, Alex Samylkin, Meredith Porth, Satish Chandra

arXiv:1810.05286v2cs.SE

TL;DR

At Facebook, repository scale makes exhaustive testing of potentially affected tests impractical. The paper learns predictive test selection from historical outcomes, catching over 95% of individual test failures and over 99.9% of faulty changes while halving infrastructure cost.

  • Problem

    Tens of thousands of weekly mobile-code changes can each affect around ten thousand tests, making exhaustive testing impractical.

    Source: §I · p. 1

  • Method

    The system trains a feature-based classifier on historical changes and test outcomes, and the paper describes compensating for flaky tests.

    Source: §I · p. 2, §IV · p. 5

  • Results

    Over 95% of individual test failures and over 99.9% of faulty code changes are caught, while infrastructure cost falls by a factor of two.

    Source: §I · p. 2

  • Takeaways & Limitations

    The predictive test selection strategy has been operational at Facebook for several months.

    Source: §I · p. 2

    The model considers each potentially impacted test separately and therefore cannot capture overlapping coverage among test subsets.

    Source: §VIII · p. 10

Abstract

from arXiv · show

Change-based testing is a key component of continuous integration at Facebook. However, a large number of tests coupled with a high rate of changes committed to our monolithic repository make it infeasible to run all potentially-impacted tests on each change. We propose a new predictive test selection strategy which selects a subset of tests to exercise for each change submitted to the continuous integration system. The strategy is learned from a large dataset of historical test outcomes using basic machine learning techniques. Deployed in production, the strategy reduces the total infrastructure cost of testing code changes by a factor of two, while guaranteeing that over 95% of individual test failures and over 99.9% of faulty changes are still reported back to developers. The method we present here also accounts for the non-determinism of test outcomes, also known as test flakiness.

I. INTRODUCTION

Facebook’s repository scale makes exhaustive testing of potentially impacted tests impractical. The paper proposes predictive test selection learned from historical outcomes and describes how it addresses flaky tests.

I. INTRODUCTION

  • Build-dependency selection is easy and guaranteed to identify potentially impacted tests, but can select around 10^4 tests despite most changes touching few files.The introduction describes the exhaustive burden as impractical for tens of thousands of weekly mobile-code changes.Source: §I · p. 1
  • Static-analysis selection could use finer-grained code dependencies, but reflection can compromise soundness and cross-language control flow is difficult to handle.Source: §I · p. 1
  • Dynamic analysis may reduce selections, but it is approximate, cannot use a test’s behavior on the exact future code version, and is difficult to maintain at repository scale.Runtime behavior may change arbitrarily after even a small code change, and accurate per-test coverage is impractical in large monolithic repositories.Source: §I · pp. 1–2
  • The proposed classifier learns from historical changes and test outcomes, using change and test features to estimate whether a test will fail on a future change.The paper also identifies flaky outcomes as a source of poor predictions and describes compensating for flakiness.Source: §I · p. 2
  • Over 95% of individual test failures and over 99.9% of faulty code changes are caught, while infrastructure cost falls by a factor of two.The predictive strategy was operational at Facebook for several months.Source: §I · p. 2
  • The predictive strategy selects fewer than a third of the tests selected by build dependencies.Source: §I · p. 2

II. CONTINUOUS INTEGRATION AT FACEBOOK

Facebook’s monolithic repository connects mobile and backend code, while its build system organizes code and tests as targets. Testing occurs at multiple stages of the developer workflow.

A. Repository Structure

  • Facebook stores mobile-application and backend-service code in one repository, where small changes can affect many artifacts.The repository’s shared code model also supports reusable libraries and large-scale refactoring.Source: A. Repository Structure · p. 2
  • The build system materializes code targets from declared inputs and dependencies, and test targets define both test executables and how to run them.A target fails if any assertion fails or its test binary terminates prematurely.Source: A. Repository Structure · pp. 2–3

1) Pre-submit:

  • Before creating a code-review diff, developers typically run a few hand-picked tests to catch quickly detectable breakage and avoid unnecessary reviewer effort.Source: 1) Pre-submit · p. 3

2) Diff-time:

Diff- and land-time testing provide correctness signals and gate changes before landing, while stabilization tests the recent master branch. These stages balance signal quality, latency, and infrastructure cost.

2) Diff-time:

  • At diff-time, continuous integration runs a subset of tests on each new diff version and reports results in code review, ideally within ten minutes.Source: 2) Diff-time · p. 3

3) Land-time:

  • At land-time, a possibly broader test subset gates landing, but parallel changes can pass individually and fail when rebased together.Source: 3) Land-time · p. 3

4) Stabilization:

  • Every few hours, stabilization tests all tests on recent master; batching can lower cost but may hide which diff introduced a failure or let a later fix mask an earlier fault.Source: 4) Stabilization · p. 3
  • Diff- and land-time testing consume an order of magnitude more machine resources than stabilization, so thoroughness trades off against cost, signal latency, and developer context-switching.More thorough pre-landing testing can raise cost or latency; less thorough testing can delay error discovery and reduce productivity.Source: 4) Stabilization · p. 3

III. LEARNING TO SELECT TESTS

Because an exact set of impacted tests cannot be computed at selection time, the paper approximates it by predicting failures from historical data. It measures selection quality by failure recall and the fraction of build-dependency-selected tests that are run.

A. Approximating The Set of Impacted Tests

  • Historical data can approximate the impacted-test set by identifying tests likely to fail, even when the selection is not conservative.The authors argue this approximation can still serve diff- and land-time testing, where thoroughness trades off against infrastructure cost and developer time.Source: A. Approximating The Set of Impacted… · p. 4

B. Measuring Quality of Test Selection

  • The section defines test recall as capturing individual failures and change recall as catching at least one failure on faulty changes.These measures reflect whether selection preserves failure signals at the test and change levels.Source: B. Measuring Quality of Test Selection · p. 4
  • Selection rate measures selected tests relative to build-dependency-based selection, which serves as the comparison baseline.The figure illustrates that approximate and prior-version dynamic selection can miss failures, while code-reference analysis can be more accurate than coarse-grained build dependencies.Source: Figure 2 · p. 4, B. Measuring Quality of Test Selection · p. 5

IV. TEST SELECTION MODEL

The paper selects tests by predicting which ones will fail on a code change. It trains a classifier on historical test outcomes and uses change and test features to estimate failure likelihood.

IV. TEST SELECTION MODEL

  • The model predicts test failures rather than attempting to identify the exact set of tests impacted by a change.All failed tests are impacted, so predicted failures provide a learnable basis for selecting tests.Source: §IV · p. 5
  • A classifier trained on historical outcomes takes features of a change and a test and estimates the likelihood that the test would fail.Feature inputs let it generalize to previously unseen changes instead of memorizing historical change-test pairs.Source: §IV · p. 5
  • The learned selection supports data-guided trade-offs between testing cost and signal quality at diff- and land-time stages.The model's future behavior must be predictable and adjustable to achieve desired correctness guarantees.Source: §IV · p. 5

A. Feature Engineering

The feature set combines attributes of code changes, test targets, and their relationship. These features represent development activity, failure history, and proximity between modified files and tests.

A. Feature Engineering

  • Change-level features include recent file-change history, files touched, triggered targets, file extensions, and author counts.File-change history is measured over 3, 14, and 56 days.Source: A. Feature Engineering · p. 5
  • Target-level features include the target's recent failure rates and project name.Failure rates cover the previous 7, 14, 28, and 56 days.Source: A. Feature Engineering · p. 5
  • Cross features include target size and the distance between modified-file paths and a test, including shared path tokens.Target size proxies covered code area; path distance and shared tokens proxy relevance or proximity.Source: A. Feature Engineering · p. 5

B. Model Architecture

The strategy uses a gradient-boosted decision-tree classifier trained on historical change-test outcomes. It selects targets using both a score threshold and a cap on the highest-scoring targets.

B. Model Architecture

  • Gradient-boosted decision trees were chosen for training speed, support for mixed feature types, and robustness to highly imbalanced examples.The method does not require feature normalization.Source: B. Model Architecture · p. 5
  • Training examples pair a change with a dependent test target and label it positive when that target failed; the classifier returns an estimated failure likelihood.Training uses outcomes recorded for changes submitted over the past three months.Source: B. Model Architecture · pp. 5–6
  • The strategy selects targets that exceed a score threshold or rank among the highest-scoring targets up to a per-change count cutoff.The final selected set is the union of these two selection rules.Source: B. Model Architecture · p. 6

C. Model Calibration

Model calibration uses outcomes from earlier changes to predict future test failures, then evaluates performance on a recent held-out week using sampled full test runs. A weekly deployment process checks predefined criteria before replacing the production model.

C. Model Calibration

  • The evaluation trains on earlier changes and tests on outcomes from the most recent week, approximating future production use.The split keeps testing outcomes out of the training data.Source: C. Model Calibration · p. 6
  • Performance estimates use a small sample of changes with full dependent-test runs, because measuring recall directly requires outcomes for all potentially impacted tests.Running all such tests on every change would defeat the goal of reducing continuous-integration costs.Source: C. Model Calibration · p. 6
  • Learning runs are deferred to off-peak hours, enabling sampling of close to a quarter of submitted changes without increasing peak resource usage.These runs produce no output visible to developers.Source: C. Model Calibration · p. 6

D. Deployment Process

  • Because evaluation covers only one week of outcomes, the model’s performance cannot be guaranteed to remain unchanged over longer periods.The weekly retraining and verification process addresses this uncertainty operationally.Source: D. Deployment Process · p. 6
  • Weekly automation replaces the production model only after its performance meets predefined criteria, with a team member notified if an assertion fails.The process retrains with fresh data, verifies performance, and deploys a qualifying model automatically; automating these steps reduces maintenance cost and the likelihood of human-caused underperformance.Source: D. Deployment Process · p. 6

V. TEST FLAKINESS

The paper separates failures caused by code changes from flaky failures through retries, since training on indistinguishable failures could favor tests that do not detect faults. It also examines how flakiness affects model evaluation and performance in real-world conditions.

V. TEST FLAKINESS

  • Failures unrelated to a code change are treated as flaky, and the paper notes that eliminating test flakiness entirely is not considered economically viable.The paper identifies random-number use, asynchronous timing assumptions, races, production-service reliance, and environmental contamination as typical sources.Source: §V · p. 6
  • Both strategies capture all failed tests in Fig. 4, but selecting more tests also captures more failures unrelated to the change, and the strategies capture different portions of flaky failures.The schematic states that proportions are not preserved.Source: Figure 4 · p. 7
  • Without distinguishing flaky failures, strategies capturing equal shares of all observed failures can differ sharply: one captures change-caused failures, while another captures only flaky ones.Fig. 5 illustrates why equal aggregate performance can conceal an unacceptable strategy.Source: Figure 5 · p. 7, §V · p. 7
  • Failed targets are retried up to ten times or until a successful attempt; a target with both failed and successful attempts is classified as flaky.This de-flaking procedure assumes that any failure is flaky if that test can execute successfully on the same code version.Source: §V · p. 7
  • Retry-based de-flaking may miss some forms of flakiness, so estimated unrelated failures are a lower bound.Source: §V · p. 7

VI. RESULTS

  • The results section studies feature effects on the correctness-cost trade-off and assesses the learned strategy under non-deterministic test outcomes.Source: §VI · p. 7

A. Empirical Performance

The combined strategy selects tests predicted likely to fail and highly ranked tests, achieving high test and change recall with a selection rate below one third. The section also reports reductions in test executions and infrastructure cost, then identifies the feature set used by the best-performing model.

A. Empirical Performance

  • The strategy is calibrated to guarantee TestRecall(s∗) > 0.95 and ChangeRecall(s∗) > 0.999 at land-time testing.The paper reports that only fewer than 5% of individual test failures and fewer than 0.1% of faulty changes are missed.Source: A. Empirical Performance · p. 8
  • Selecting LikelyFailing targets alone yields SelectionRate(s∗) < 0.25, while selecting only highly ranked targets requires at most 230 per change.The average number of targets depending transitively on modified files is much greater than 1,000.Source: A. Empirical Performance · p. 8
  • TestRecall(s∗) > 0.95, ChangeRecall(s∗) > 0.999, and SelectionRate(s∗) < 0.33 for the combined strategy.It selects the union of LikelyFailing(s∗, d) and HighlyRanked(s∗, d) test targets for each change.Source: A. Empirical Performance · p. 8
  • A factor-of-two reduction in infrastructure cost and factor-of-three reduction in test executions were measured relative to build-dependency-based selection.Infrastructure cost is measured by number of machines.Source: A. Empirical Performance · p. 8

B. Feature Selection

  • Feature selection compares SelectionRate ratios at TestRecall(s∗) = 0.9 for classification and CountCutoff ratios for ranking; values below 1 indicate regression.The wrapper method evaluates the full feature set and the set with each feature removed.Source: B. Feature Selection · p. 8
  • The best-performing model uses file extensions, change history, failure rates, project name, number of tests, and minimal distance.Other features introduce regressions; project name is retained despite a ranking-metric regression because it improves the classification metric that dominates selection rate.Source: B. Feature Selection · p. 8

C. Impact of Test Flakiness

The section tests whether flakiness distorts predictive test selection by comparing models trained with and without de-flaking. The results show that the non-de-flaked model overstates failure recall, while de-flaking preserves failure detection relative to flaky outcomes.

C. Impact of Test Flakiness

  • The experiments address whether flakiness affects learned models in practice, following a theoretical argument that identifying unrelated failures matters for empirical evaluation.The section motivates this question by noting that training on flaky outcomes gives very poor predictions.Source: C. Impact of Test Flakiness · p. 8
  • TestRecallWithFlakes measures the empirical probability of selecting a failed outcome, whether or not it was related to the code change.The measure is used alongside TestRecall to assess whether the model identifies fault-detecting tests or tests that would flake.Source: C. Impact of Test Flakiness · p. 9
  • Experiment B treated failed or flaked outcomes as positive training examples, unlike the de-flaked training used for sA.The experiments compare TestRecall and TestRecallWithFlakes against selection rate, with CountCutoff set to 0.Source: C. Impact of Test Flakiness · p. 9
  • TestRecall(sB) ≈0.7, and deployment would miss three times as many test failures as expected; sA outperforms sB at every selection rate.The comparison uses the model trained on non-de-flaked data; Fig. 9 shows TestRecall(sB) below TestRecallWithFlakes(sB).Source: C. Impact of Test Flakiness · p. 9, Figure 9 · p. 9
  • At every selection rate, de-flaked sA has higher TestRecall than sB and TestRecall(sA) ≥ TestRecallWithFlakes(sA).The latter comparison indicates that sA is no worse at catching failed tests than tests that flaked.Source: C. Impact of Test Flakiness · p. 9, Figure 8 · p. 9

VII. RELATED WORK

Prior test-selection work uses static or dynamic dependency analyses, while this paper combines multiple information sources in a learned strategy. The conclusion identifies unexamined feature sources and independent per-test decisions as directions and limitations for future work.

VII. RELATED WORK

  • Static analysis ranges from method-level call graphs to class-, method-, and file-level dependencies, but fine-grained dependency analysis poses scaling challenges in large codebases.The discussion also notes challenges handling features such as Java reflection and multilingual code bases.Source: §VII · pp. 9–10
  • Dynamic test selection methods use execution information at different granularities, but fine-grained execution tracing is infeasible at Facebook’s scale.Examples include basic-block, file, and cross-language tracing techniques,,.Source: §VII · p. 10
  • Memon et al. combine build metadata with dependency-graph distance, which this paper uses as one feature but finds insufficient on its own for accurate selection.Source: §VII · p. 10

VIII. CONCLUSIONS AND FUTURE DIRECTIONS

  • The conclusion presents a learned strategy that combines weak information sources and can be maintained with little to no manual tuning.The authors report that real-world test nondeterminism does not preclude predictive test selection.Source: §VIII · p. 10
  • Code-change history and additional change-impact features are identified as information sources that could be added but were not explored in this work.Source: §VIII · p. 10
  • Because the approach considers each potentially impacted test separately, it cannot capture overlapping coverage or correlated results, and may select test sets with redundant signal.Source: §VIII · p. 10
Loading 1810.05286v2…