Coping Strategies for Unreliable Regression Tests

Regression Testing

Flaky Tests

Example: libkdumpfile

#! /bin/sh

name=xlatmap
resultfile="out/${name}.result"
expectfile="$srcdir/$name.expect"

echo -n "Checking... "
./xlatmap >"$resultfile"

Excerpt from:
https://github.com/ptesarik/libkdumpfile/blob/c54a90c2756e0ca7f9b45662ad3c987403ee7360/tests/xlatmap-check

Test Interference

Example: libkdumpfile

#! /bin/sh

name=xlatmap
resultfile="out/${name}.result"
expectfile="$srcdir/$name.expect"

mkdir -p out

echo -n "Checking... "
./xlatmap >"$resultfile"

Excerpt from accepted fix:
https://github.com/ptesarik/libkdumpfile/blob/e6c5fde6ac7201185292539bef7203c9618ac773/tests/xlatmap-check

Flaky Test Coping Strategy in Industry: Rerun

• Google: 10x
• Mozilla: 10x + 5x + “CHAOS_MODE”
• Spotify: 3-5x with coverage instrumentation
• Dropbox Athena: Mark tests in pre-submit, re-run in post-submit
• Microsoft Azure: Configurable test/pipeline reruns

If detected: Proceed with integration (no regression),

skip execution of test in the future

Flaky Test Coping Strategies in Academia

• Detection and repair: costly, but massive improvements with recent work (Eder and Winter 2024)
• Avoidance: (Silva et al. 2024)
• ML-based prediction (tests can be both flaky and regression-revealing (Wendler and Winter 2024))

Detection and Repair

• Requires hypothesis on root cause
• Systematic search for sensitivity to root cause
  • Order dependencies (Lam et al. 2019)
  • Implementation dependencies (unordered collections, etc.) (Shi et al. 2016)
  • Resource dependencies (Silva, Teixeira, and d’Amorim 2020; Silva et al. 2024)

Order Dependencies (OD)

Source: (Luo et al. 2014)

Order Dependencies (OD)

Source: (Gruber et al. 2021)

OD Detection Overhead

• Complete detection: Run all test suite permutations (\(n!\))
  • libkdumpfile has 184 tests
  • \(2.2 \times 10^{338}\) test suite permutations
  • 22s per test suite run → \(4.9 \times 10^{339}\)s
    (estimated age of universe: \(4.3 \times 10^{17}\)s)

OD Detection Overhead

• Empirical results: Pairwise permutations mostly suffice (\(n\cdot(n-1)\)) (Zhang et al. 2014; Shi et al. 2019)
  • Factorial down to quadratic complexity
  • 33,672 test pair runs and > 2h for libkdumpfile
  • Still too long to run in CI

Reducing OD Detection Cost

File Descriptors Filtered (FDF)

Reducing OD Detection Cost

Overlay FS + FDF (OFSFDF)

• Insight: Not every write permission leads to an actual change
• Idea: Snapshot filesystem before/after test run

Reducing OD Detection Cost

Overlay FS + FDF (OFSFDF)

Results

Test Order Reductions

Summary

Flaky tests threaten regression testing.
Coping strategies:

• Rerun + skip (considered harmful (Wendler and Winter 2024))
• Prediction (considered imprecise (Wendler and Winter 2024))
• Avoidance (discussed in (Silva et al. 2024))
• Detection + repair (costly, but recently improved (Eder and Winter 2024))