Selectively Uniform Concurrency Testing

Concurrency bugs hide in a handful of the astronomically many possible orderings of a program's threads, so testers sample orderings at random and hope to hit a buggy one, but this work from the National University of Singapore shows that the popular random samplers are badly biased — they revisit some orderings constantly and almost never reach others; the fix is a surprisingly simple rule, pick each thread with a chance proportional to how many steps it still has left, which samples every ordering with exactly equal probability, and then apply that fairness only to the few memory accesses that actually matter, giving an algorithm called SURW that finds more bugs, and finds them faster, than the leading random testers.

The argument in one glance

Problem

Concurrency bugs hide in a few of astronomically many orderings

A concurrent program's threads can interleave in exponentially many ways, and a bug may appear in only a tiny fraction of them. Testers take control of the scheduler and sample orderings at random, but a good sampler should be uniform — sampling every interleaving with equal probability, since it has no hint where the bug is.
What people did

Pick a random thread, or random context-switch points

Standard randomized testers choose a random ready thread at each step (random walk), or randomly place a few preemption points as the popular PCT family does, hoping to stumble into a buggy interleaving.
Why it fell short

These strategies are badly non-uniform

Picking a random thread or random switch points produces wildly skewed distributions — some interleavings are sampled constantly while others are reached with vanishingly small probability, so small that tens of thousands of trials never witness them. The rare-interleaving bugs, the hardest to find, are exactly the ones missed.
This paper's idea

Sample uniformly, selectively on the events that matter (SURW)

The key insight: to sample interleavings uniformly, at each step pick each thread with probability proportional to how many steps it has left — a weighted random walk needing only per-thread event counts. Applying this uniformity to a selected subset of the events that determine behavior gives SURW, which finds more bugs, and faster, than leading random testers.

Why this problem is worth solving

Concurrency bugs are among the most feared in software because they are both damaging and maddeningly hard to reproduce.

A concurrent program runs several threads at once, and the order in which their individual steps are actually executed — the interleaving — is decided by the operating system’s scheduler, which is non-deterministic. Most orderings behave fine, but a few can trigger a data race, a deadlock, or a corrupted value, and because those orderings arise only occasionally, the bug may appear once in a thousand runs and then vanish, defying reproduction. The number of possible interleavings is exponentially larger than the number of instructions, so the space is astronomically vast. Controlled Concurrency Testing (CCT) tackles this by taking the scheduling decision away from the operating system: the tester serializes the program so that only one thread executes one atomic step at a time, and the tester itself decides which thread goes next. This gives full control to steer the program into orderings that ordinary stress testing, at the mercy of the real scheduler, would almost never reach. The remaining question is the hard one: out of the astronomically many interleavings, which ones should the tester actually explore?

Because enumerating them all is hopeless, the best testers sample, and how they sample turns out to matter enormously.

Since exhaustively enumerating every interleaving is infeasible for real software, effective CCT tools are randomized: they sample interleavings and hope to hit a buggy one, which in practice scales far better than trying to systematically cover the space. The property that should guide such sampling is uniformity. With no prior knowledge of where a bug lives, the least-biased strategy is to sample every interleaving with equal probability, so that no ordering is systematically neglected. Yet the standard randomized strategies fall dramatically short of this. The simplest, a random walk, picks a random ready thread at each step with equal probability among threads — but this does not make interleavings equally likely, because an ordering is a sequence of choices and threads with different numbers of remaining steps contribute unequally. The popular Probabilistic Concurrency Testing (PCT) family instead assigns random thread priorities and inserts a few random preemption points, which targets shallow bugs but is even more skewed over the full interleaving space. The consequence is that these testers oversample a cluster of similar orderings and reach others with probabilities so tiny that, as the paper shows on a trivial two-thread example, tens of thousands of trials still fail to produce them — and those neglected orderings are where the elusive bugs hide.

What people did before, and where it broke

Stress-test and hope the scheduler cooperates. Run the program many times under the real operating-system scheduler and watch for failures. Where it broke. The non-deterministic scheduler explores only a narrow, machine-dependent slice of orderings, so rare-interleaving bugs almost never surface and cannot be reproduced.
Systematically enumerate interleavings. Use a model checker to traverse the interleaving space, often bounding it to few preemptions or short delays. Where it broke. The space is exponentially huge, so within any time budget the enumeration covers only a small clump of similar orderings, especially for large real software.
Random walk over ready threads. At each step, pick a random enabled thread with equal probability. Where it broke. Equal probability per thread is not equal probability per interleaving; the distribution is skewed toward orderings favored by the step-by-step choice structure, so many interleavings are effectively unreachable.
PCT and random preemption points. Assign random priorities and insert a few random context-switch points, aiming at shallow bugs with a probabilistic guarantee. Where it broke. Over the full interleaving space PCT is highly non-uniform; the paper shows a case where it witnesses a particular outcome with probability around two in a billion, missing it even after tens of thousands of trials.
The gap. No randomized tester actually achieved uniform sampling of interleavings, nor a way to focus that uniformity where it best exposes distinct behaviors. Providing both is what SURW does.

How SURW works

From biased random sampling to selective interleaving-uniformity

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Sample the space evenly rather than guessing where bugs live. SURW starts from the principle that a black-box tester, knowing nothing about where a bug hides, should give every possible interleaving an equal chance — uniformity — rather than lavishing attention on a favored cluster of orderings and starving the rest. This is the honest default for exploring an astronomically large space blind, and it is exactly the property prior random testers lacked. Treating unbiased random sampling with a real probabilistic guarantee as the right foundation for searching a space too large to enumerate is the same move the probabilistic concurrency-testing work covered elsewhere on this site makes, replacing ad-hoc randomness with a sampling strategy whose reach over the space of orderings can be reasoned about and bounded rather than left to luck.

Achieve uniformity with one cheap, exact rule: weight by what remains. The paper’s elegant core is that uniform sampling of interleavings does not require heavy machinery or global analysis — it needs only, at each scheduling step, to pick each thread with probability proportional to the number of events that thread still has left to execute. This weighted random walk provably makes every interleaving equally likely, using only an estimate of per-thread remaining event counts, and it runs online as the program executes. Getting a strong, provable guarantee from a small amount of readily-available information, instead of an expensive heavyweight mechanism, is the same spirit the efficient concurrency-bug detection work covered elsewhere on this site is built on, extracting an effective testing capability from lightweight, practical instrumentation so the technique scales to real software rather than collapsing under its own cost.

Aim the fairness at the events that actually decide behavior. SURW’s second insight is that uniformity over every interleaving is not the same as exploring distinct program behaviors evenly, because one behavior can be produced by disproportionately many orderings, so a fully uniform sampler oversamples such behaviors. The fix is selectivity: make the sampling uniform only over a chosen subset of interesting events — typically accesses to the few shared variables that most concurrency bugs actually turn on — so that interleaving-uniformity over that subset becomes a good proxy for exploring behaviors evenly. Concentrating testing effort on the small set of interactions that genuinely determine whether a bug appears, rather than spreading it uniformly across everything, is the same discipline the message-reordering bug-detection work covered elsewhere on this site follows, targeting the specific orderings among the events that matter so that the search lands on the behaviors capable of exposing a fault.

Following a test session through SURW

Sampling interleavings uniformly over the events that matter

A trace of SURW scheduling a concurrent program under test, following the paper's URW and selective-uniformity design.

Step 1 of 5

Take control of the scheduler

SURW runs the program under test in controlled mode: only one thread executes one atomic event at a time, and SURW itself decides which thread proceeds, so it can steer the program into any interleaving rather than depend on the operating system.

This is the controlled concurrency testing setting.

Why it works

Uniformity is the least-biased blind search. Because the tester has no prior knowledge of where a bug lives → sampling every interleaving with equal probability neglects none of them → so the rare orderings that harbor elusive bugs are no longer systematically starved.
Remaining-event weights make interleavings equiprobable. Because an interleaving is a sequence of thread choices and threads have differing numbers of steps left → weighting each thread by its remaining events exactly balances the choice structure → so every ordering ends up equally likely, which uniform thread-picking fails to achieve.
The rule is cheap and online. Because only per-thread counts of remaining events are needed → the weighted random walk runs as the program executes without heavy analysis → so uniformity is practical on large, real-world programs.
Selectivity matches behaviors, not just orderings. Because one behavior can correspond to many interleavings → making sampling uniform over a chosen subset of interesting events approximates uniform exploration of behaviors → so effort is not wasted oversampling behaviors backed by many orderings.
Few shared variables carry most bugs. Because empirical studies show real concurrency bugs usually involve only a handful of shared variables → selecting accesses to a few such variables as the interesting set is a good automatic heuristic → so even a crude subset choice yields strong bug-finding.

What it costs (trade-offs and scope)

It needs accurate remaining-event counts. SURW’s uniformity relies on estimating how many events each thread has left. When this estimate is inaccurate — for instance with data-dependent or unbounded loops whose lengths are not known in advance — the uniformity guarantee degrades, and the paper discusses estimating these counts as a practical concern.
The quality of the interesting subset matters. Selectivity is only as good as the chosen subset. The automatic heuristic (a few random shared variables) works well but is crude; a poorly chosen subset would give weaker behavioral exploration, and the authors note more sophisticated selection could do better.
It targets sequentially consistent, controlled execution. SURW operates in the controlled-testing model where execution is serialized one atomic event at a time, and its behavioral argument leans on each behavior corresponding to at least one interleaving under sequential consistency. Weak memory models and uncontrolled execution are a different setting.
Uniformity is a heuristic for bug-finding, not a guarantee of finding every bug. Sampling all interleavings equally maximizes unbiased coverage, but a bug in one specific ordering can still be missed within a finite budget; SURW improves the odds and speed, it does not prove absence of bugs.
Results are on benchmarks and one case study. The strong bug-finding numbers come from established CCT benchmarks and a LightFTP case study; other programs, especially with very different sharing patterns, could shift the outcomes.
Behavioral uniformity is approximated, not exact. Selective uniformity over interesting events is a proxy for exploring behaviors evenly, not an exact guarantee of behavioral uniformity, which the paper notes is generally impossible to achieve or even measure precisely.

The evaluation

Three randomized ways to schedule concurrency tests

Property	Random walk over threads	PCT (random preemptions)
Uniform over interleavings
Information required		A depth or preemption bound
Focus on behavior-determining events	No	No
Reaches rare interleavings
Bug-finding on benchmarks	Fewer bugs

Three randomized scheduling strategies for controlled concurrency testing, as compared in the paper. A random walk picks each ready thread with equal probability, but this does not make interleavings equally likely because threads have differing numbers of remaining steps, so many orderings are effectively unreachable. The PCT family assigns random priorities and a few random preemption points, catching shallow bugs but sampling the full interleaving space very unevenly — in one example witnessing a particular outcome with probability around two in a billion, missing it even after tens of thousands of trials. SURW makes interleavings equiprobable with a single rule, choosing each thread with probability proportional to its remaining events (a Uniform Random Walk), needing only per-thread event counts and running online. Recognizing that uniform over interleavings is not the same as exploring distinct behaviors evenly, SURW applies the uniformity selectively to a chosen subset of interesting events (accesses to the few shared variables most bugs turn on, picked automatically or by an expert), which serves as a proxy for behavioral uniformity. On leading CCT benchmarks SURW exposed more bugs than comparable randomized algorithms (with statistical significance, and no other algorithm found a bug SURW missed), triggered bugs with fewer schedules on the majority of targets, and explored interleavings and behaviors more evenly on real-world programs.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is a clean, principled result whose appeal is that the core idea is both mathematically crisp and immediately practical. Concurrency bugs hide in a tiny fraction of an astronomically large space of thread interleavings, so randomized testers sample that space, and everything hinges on how they sample. The paper’s first contribution is to take seriously a property everyone wanted but nobody achieved — uniformity, sampling every interleaving with equal probability — and to show it is attainable with a strikingly simple rule: at each step, pick a thread with probability proportional to how many steps it has left. That this weighted random walk yields exact uniformity, needs only per-thread event counts, and runs online is the kind of clean insight that makes prior non-uniform heuristics look accidental. The second contribution is the honest observation that interleaving-uniformity is not the same as exploring distinct behaviors evenly, since one behavior can be backed by many orderings, and the fix — selectivity, applying uniformity only to a subset of interesting events, usually accesses to the few shared variables most bugs involve — is what turns a mathematically elegant property into strong practical bug-finding. Read the scope with care. The uniformity guarantee depends on accurate remaining-event counts, which are harder to estimate for data-dependent or unbounded loops; the behavioral benefit depends on choosing a good interesting subset, and the automatic heuristic, though effective, is deliberately crude; the setting is controlled, sequentially consistent execution rather than weak memory; and uniformity improves the odds and speed of finding bugs without guaranteeing that every bug is found in a finite budget. The evaluation is nonetheless persuasive — more bugs than comparable algorithms with statistical significance, no bug found by others that SURW missed, fewer schedules on most targets, and more even coverage on real programs. The durable idea is that when you must search blind through an enormous space, making the search provably unbiased, and then aiming that unbiased search at the parts that matter, beats piling on cleverer but skewed heuristics.

Background

Why unbiased, targeted sampling is the throughline of concurrency testing

It helps to see SURW within the long effort to make concurrency testing both principled and effective. Because the space of thread interleavings is too large to enumerate, the field has steadily moved from ad-hoc randomness toward sampling strategies with understood statistical behavior, and toward focusing that sampling where bugs actually arise. The memory-consistency testing work covered elsewhere on this site reflects the same drive from the specification side, systematically improving how test programs and outcomes are generated and evaluated so that testing coverage is measured and strengthened rather than left to chance. The common thread is that effective testing of concurrent and memory-model behavior is fundamentally a sampling problem: the space is astronomically large, the interesting cases are rare, and the leverage comes from two moves SURW exemplifies — making the sampling unbiased so nothing is systematically neglected, and directing it at the events or behaviors that determine whether a fault appears. As concurrent software grows and its bugs stay as costly as ever, techniques that combine a provable exploration property with a practical way to focus effort are likely to remain the backbone of how these bugs are hunted, with better subset-selection methods, including learned or expert-guided ones, as a natural next step.

If you remember only three things

1. Concurrency bugs surface in only a tiny fraction of the exponentially many ways a program's threads can interleave, so testers use Controlled Concurrency Testing — serializing execution to one atomic step at a time and deciding the order themselves — and, because enumerating all orderings is hopeless, sample them at random. The property that should guide sampling is uniformity: with no hint where the bug is, sample every interleaving with equal probability so none is neglected. But the standard strategies badly violate this. A random walk that picks a random ready thread with equal probability does not make interleavings equally likely, because threads have different numbers of remaining steps; and the popular PCT family, which assigns random priorities and a few random preemption points, is even more skewed over the full space, sometimes reaching an outcome with a probability around two in a billion and missing it even after tens of thousands of trials — exactly the rare-ordering bugs that are hardest to find.
2. SURW (Selectively Uniform Random Walk) rests on two insights. First, uniform sampling of interleavings is achievable with one cheap, online rule: at each scheduling step, pick each thread with probability proportional to the number of events it still has left to execute. This weighted random walk (URW) provably samples every interleaving with equal probability, needing only per-thread remaining-event counts. Second, interleaving-uniformity is not the same as exploring distinct behaviors evenly, because one behavior can correspond to disproportionately many interleavings, so a fully uniform sampler oversamples such behaviors. The fix is selectivity: apply the uniformity only to a chosen subset of interesting events — whose interleavings map more evenly onto behaviors — while scheduling the rest carefully. SURW is the first randomized tester to achieve interleaving-uniformity over an arbitrary subset of events, and the interesting subset can be inferred automatically (accesses to a few randomly chosen shared variables, since most real bugs involve few shared variables) or supplied by a domain expert.
3. On leading concurrency benchmarks SURW exposed more bugs than comparable randomized algorithms with statistical significance, no other algorithm triggered a bug that SURW missed, it needed fewer schedules to find bugs on the majority of targets, and it explored both interleavings and behaviors more evenly on real-world programs, even with a crude automatic subset heuristic. Scope: the uniformity depends on accurate remaining-event counts (harder for data-dependent or unbounded loops), the behavioral benefit depends on a good interesting subset, the setting is controlled sequentially consistent execution rather than weak memory, and uniformity improves the odds and speed of finding bugs without guaranteeing every bug is found. The durable lesson is that to search blind through an enormous space, making the search provably unbiased and then aiming that unbiased search at the events that matter beats piling on cleverer but skewed heuristics.

Check yourself

Check your understanding

1. What does "uniformity" mean for a randomized concurrency tester, and why does it matter?
2. How does SURW actually achieve uniform sampling of interleavings?
3. Why does SURW add "selectivity" instead of just making all interleavings uniform?
4. What did the evaluation show about SURW, and what are its limits?

Sources

The paper is “Selectively Uniform Concurrency Testing” by Huan Zhao, Dylan Wolff, Umang Mathur, and Abhik Roychoudhury, published at ASPLOS 2025, DOI 10.1145/3669940.3707214. All four authors are at the National University of Singapore.

This explainer is based on the full text of the paper, obtained from the authors’ open-access copy (the CC-BY version) hosted on Umang Mathur’s National University of Singapore publications page (retrieved via the Internet Archive’s Wayback Machine). The problem framing (concurrency bugs manifesting in few of exponentially many interleavings, controlled concurrency testing serializing execution to one atomic event at a time, randomized sampling of the interleaving space, and uniformity as the key desirable property that prior random walk and PCT algorithms fail to achieve, with the two-thread bit-shift example showing skewed distributions and PCT’s near-unreachable outcomes), the SURW design (the Uniform Random Walk that samples interleavings uniformly by choosing each thread with probability proportional to its remaining events, needing only per-thread event counts and running online; the observation that interleaving-uniformity does not equal behavioral uniformity because a behavior can correspond to many interleavings; and the selective uniformity over a chosen subset of interesting events, with the automatic heuristic of selecting accesses to a few randomly chosen shared variables inspired by studies that most concurrency bugs involve few shared variables, or an expert-provided subset as in the LightFTP case study), and the results (SURW exposing more bugs than comparable algorithms with statistical significance, no other algorithm finding a bug SURW missed, best schedule-count performance on the majority of targets, exposing 944 distinct bugs on RaceBenchData, and higher interleaving and behavioral coverage and evenness on LightFTP) are all drawn directly from the paper. Background explanations of thread interleavings, controlled concurrency testing, uniform sampling, and PCT are standard and provided to make the paper’s contribution understandable.