A bug in a multi-threaded program can hide behind the exact order in which the threads happen to run, and the number of possible orders explodes exponentially with the length of the execution, so testing faces a choice between two bad options — sample orders at random and hope, or systematically enumerate a bounded slice of the space and hope the bug lives inside it; this paper (National University of Singapore) refuses both, borrowing the idea behind GREYBOX FUZZING, which finds bugs in ordinary programs by mutating inputs and keeping the ones that produce new behaviour, and applying it to thread orderings instead; the key move is choosing what counts as a genuinely different ordering, and the answer is the READS-FROM relation, which records only which write each read actually observed — two runs with the same reads-from relation follow identical control and data flow, so testing one covers the other, and the number of distinct classes can be exponentially smaller than the number of orderings; on a benchmark where random sampling has roughly a 3-in-100-trillion chance of hitting the bug, the reduced space has four possibilities and the tool finds it in about six attempts.
The argument in one glance
-
Problem
A concurrency bug hides behind one specific ordering out of astronomically many
In a multi-threaded program the result depends not only on the input but on the INTERLEAVING — the precise order in which the threads execute their individual operations. For one fixed input, a bug may appear under a single ordering and never under any other. The trouble is that the number of possible orderings grows exponentially with the length of the execution, so even a short program has a search space beyond enumeration. Worse, the ordering that exposes the bug is often extraordinarily specific. In the paper's own benchmark, 100 threads each set two shared variables while one checker thread inspects them, and the assertion fails only if the checker runs after at least one thread has performed its FIRST write but before any thread has performed its SECOND. Sampling orderings uniformly hits that window with a probability of roughly 3 chances in 100 trillion.
-
What people did
Either sample orderings randomly, or systematically enumerate a bounded slice
The field divided into two camps. The OPTIMISTIC camp runs the program under heavy stress workloads or samples orderings at random, sometimes with clever randomized algorithms carrying probabilistic guarantees, hoping to stumble into the bad ordering. The PESSIMISTIC camp takes control of the scheduler and systematically enumerates orderings, first shrinking the space with partial-order reduction or by bounding the number of context switches allowed, then working toward exhaustive coverage of what remains. Both are reasonable and both have produced strong tools.
-
Why it fell short
Random sampling misses rare windows and enumeration re-tests the same behaviour
Random sampling fails exactly where the target window is narrow, which is where the interesting bugs live. On that 100-thread benchmark, uniform sampling and a state-of-the-art partial-order sampler both have essentially no chance, and a well-known depth-based randomized algorithm fares no better because reaching the bug requires 101 separate ordering constraints while its guarantee decays exponentially in that number. Systematic enumeration has the opposite problem — it is thorough but spends its budget re-testing orderings that are not meaningfully different, since many distinct orderings of the same operations produce identical program behaviour. And both camps share a blind spot that greybox fuzzing solved long ago for ordinary programs: they are memoryless, learning nothing from the orderings they already tried.
-
This paper's idea
Fuzz the orderings, and define new behaviour by which write each read observed
This paper (National University of Singapore — Wolff, Shi, Duck, Mathur, Roychoudhury) is neither optimistic nor pessimistic but, in their word, PRAGMATIC. It adapts greybox fuzzing — which finds bugs in ordinary programs by mutating inputs, keeping those that produce new behaviour, and mutating those further — to the space of thread orderings. The decisive question becomes what counts as genuinely NEW behaviour, and their answer is the READS-FROM relation, which records only which write each read actually observed. Two executions with the same reads-from relation follow identical control and data flow, so they expose exactly the same bugs and testing one covers the other. The number of such classes can be exponentially smaller than the number of orderings — on that benchmark, four possibilities instead of astronomically many, and the tool finds the bug in about six attempts. The fuzzer therefore mutates ABSTRACT schedules, which are just sets of constraints saying this read must, or must not, observe that write; a proactive scheduler then manipulates thread priorities to steer a real execution into satisfying them, falling back gracefully to random sampling when it cannot. Across 49 buggy programs it finds bugs in more of them than any competing tool and usually in fewer attempts.
Why this problem is worth solving
Concurrency bugs are notorious precisely because reproducing them is a matter
of luck, so it is worth being exact about what the search space actually is.
A THREAD
INTERLEAVING is one particular order in which the operations of several
concurrently running threads actually execute. Because the operating system
decides that order and may switch between threads at almost any point, a
single program run on a single input can produce an enormous number of
different interleavings, and the count grows exponentially with the length of
the execution. This is what makes concurrency bugs so hard. An ordinary bug
depends on the input, so once you find a triggering input you can reproduce it
forever. A concurrency bug depends on the input AND the interleaving, so the
same input may run correctly a million times and fail on the next, purely
because the scheduler made a different choice. Testing therefore has to search
not just the space of inputs but the vastly larger space of orderings, and the
orderings that expose bugs are frequently extremely narrow — requiring one
thread to be interrupted at one precise instant while another is at one precise
point
The insight that makes the space tractable is choosing the right notion of
“different”.
The
READS-FROM RELATION of an execution records, for every read of a shared
variable, which write actually supplied the value it saw. It is a compact
summary of what the execution semantically DID, as opposed to the exact order
in which operations happened to be scheduled. Its power comes from a simple
observation. If two executions have the same reads-from relation, then every
read in both saw the same value, so both follow identical control flow and
identical data flow, and therefore both expose exactly the same bugs — testing
one of them covers the other completely. That turns the reads-from relation
into an EQUIVALENCE RELATION that partitions the enormous space of
interleavings into classes, where testing one member per class loses nothing.
The reduction can be dramatic, because the number of classes may be
exponentially smaller than the number of interleavings, and smaller even than
the number of partial orders that other reduction techniques work with. In the
paper’s 100-thread benchmark the interleavings are astronomically many while
the relevant reads-from choices number just four
What people did before, and where it broke
- Stress testing. Hammer the program with heavy and varied workloads and hope corner cases surface. Requires no machinery and is what most teams do, but it is entirely uncontrolled and offers no guarantee of ever producing a rare ordering.
- Randomized sampling with probabilistic guarantees. Algorithms that sample orderings, some carrying provable bounds on the chance of hitting a given interleaving. Genuinely principled, but the bounds collapse when the target is narrow — on the paper’s benchmark, one such algorithm needs 101 separate ordering constraints and its guarantee decays exponentially in that count.
- Systematic model checking and controlled enumeration. Take over the scheduler and enumerate the space after shrinking it with partial-order reduction or a bound on context switches. Thorough within the bound, but it spends effort re-testing orderings that are not meaningfully different, and one leading model checker could not even run on 36 of the 49 evaluated programs because it accepts only a subset of the intermediate language.
- Existing concurrency-aware fuzzers. These exist, but they steer the schedule only loosely — by randomizing thread priorities at creation, or by injecting delays — which lets the environment make some interleavings hard or impossible to reach, and they use proxies such as function-call pairs or event orderings as their feedback rather than anything semantic.
- The gap. Nobody had combined full, fine-grained control of the schedule with a semantic definition of new behaviour and an adaptive, stateful search that learns from what it has already tried. That is the gap this paper fills.
How the fuzzer searches orderings instead of inputs
Mutate constraints on which write each read sees, then steer a real execution to satisfy them
-
The ordering space is too large to sample or enumerate
Interleavings grow exponentially with execution length, and bug-exposing orderings can be vanishingly rare. Random sampling misses narrow windows; systematic enumeration exhausts its budget on orderings that are not meaningfully different from ones already tried.
-
Define different by the reads-from relation new
Record for each read which write supplied its value. Two executions sharing that relation follow identical control and data flow and expose identical bugs, so one representative covers the whole class. The number of classes can be exponentially smaller than the number of interleavings.
-
Search over abstract schedules, not concrete ones new
An abstract schedule is just a set of constraints, each saying that a particular read must observe a particular write, or must NOT observe it. Because it only partially describes an execution, a satisfying run can usually be found — unlike a fully concrete schedule, most mutations of which turn out to be impossible.
-
Mutate the constraints, fuzzer-style new
Four operators change an abstract schedule — insert a constraint, delete one, swap one for another, or flip one from must to must-not — with the events drawn from everything observed so far. Because mutation happens at the semantic level, every mutation that runs produces genuinely different reads-from behaviour.
-
Steer a real execution to satisfy the constraints new
A proactive scheduler runs a small state machine per constraint, raising and lowering thread priorities over time to delay a read until the intended write has happened, then protecting that value from being overwritten. When no constraint applies, or constraints conflict, it degrades gracefully to established random sampling.
-
Keep schedules that revealed something new new
A run is interesting if it produced a reads-from pair no stored schedule accounted for, or if it crashed. Interesting schedules join the corpus for further mutation, and a power schedule directs more effort toward rarely seen reads-from constraints, which measurably evens out the exploration.
The idea
Reject both camps and take the middle. The paper’s framing is unusually crisp. Optimistic approaches sample randomly and learn nothing between attempts; pessimistic ones enumerate exhaustively within an arbitrary bound and choke on scale. Greybox fuzzing already resolved exactly this tension for ordinary programs, by being neither exhaustive nor blind — it searches randomly, but keeps a memory of inputs that produced new behaviour and concentrates its mutations there. Transplanting that to thread orderings gives a search that is adaptive and non-enumerative, and the authors call it pragmatic rather than optimistic or pessimistic. Refusing a settled dichotomy by finding the structure both sides were missing is a move covered elsewhere on this site wherever a system pairs a fast unreliable path with a guided fallback instead of committing to one, and the specific debt to greybox fuzzing connects this page directly to the compiler-differential-testing page, which likewise bolts a new oracle onto the same fuzzing machinery.
Choose the equivalence relation carefully, because it defines the search space. Everything rests on deciding when two orderings are “the same”. The reads-from relation is the right choice because of a precise argument: if every read saw the same value in two executions, then both took the same branches and computed the same data, so they expose identical bugs and one may stand for the other. That collapses an exponential space into a far smaller one, and it is also strictly more informative than the code-coverage feedback ordinary fuzzers use. Collapsing a huge search space by identifying which candidates are semantically interchangeable, then exploring one per class, is the same reason-over-equivalence-classes discipline covered elsewhere on this site — the compiler super-optimizer that keeps all equivalent versions of a program in one structure and extracts once, and the persistency-race detector that reasons about every execution prefix consistent with what it observed rather than re-running each. Three different domains, one idea.
Search an abstraction that is loose enough to be satisfiable. The most instructive detail is a design the authors tried and abandoned. They first treated concrete schedules as the thing to mutate, guided by reads-from coverage, and it performed WORSE than plain random testing. The reason is that a concrete schedule pins down everything, so most mutations of one describe an execution the program cannot actually produce, and storing them is expensive too. Abstract schedules fix this by specifying only a handful of constraints and leaving the rest free, so a satisfying execution usually exists and the proactive scheduler can find it. Deliberately under-specifying what you search over, so that candidates remain feasible, is the same choose-the-right- representation lesson covered elsewhere on this site where promoting the right abstraction to a first-class object is what makes an intractable problem tractable — and reporting the failed alternative is what makes the argument convincing.
Catching a bug that random sampling would never find
From 3 chances in 100 trillion to 1 in 4
The paper's motivating benchmark, and why searching the reads-from space changes everything. Numbers from the paper.
Step 1 of 5
The program and its bug
One hundred worker threads each perform two writes — setting a shared variable to 1, then setting a second shared variable to negative 1. A single checker thread reads both and asserts they are either both untouched or both set. The assertion can only fail if the checker catches the pair mid-update.
concretely the checker must run after at least one worker has done its FIRST write but before any worker has done its SECOND the window is narrow and it closes permanently once any worker completes
Why it works
- Two executions with the same reads-from relation take identical branches and compute identical data → so they expose exactly the same bugs → testing one member of each class loses nothing, and the classes can be exponentially fewer than the orderings.
- Sampling is hopeless when the target window is a vanishing fraction of the space → but that same target may be a large fraction of the reduced space → which is how a 3-in-100-trillion event becomes a 1-in-4 event.
- A concrete schedule fixes every detail, so most mutations of one are infeasible → an abstract schedule fixes only a few constraints and leaves the rest free → so a satisfying execution usually exists and the proactive scheduler can steer toward it.
- Random search alone revisits the same behaviour repeatedly, with one reads-from sequence taking more than half of all executions in one measurement → keeping a corpus and spending more effort on rarely seen constraints spreads the search out → and even coverage is what finds the hard bugs.
- The scheduler cannot always satisfy a constraint, and some constraints conflict → in those cases it falls back to an established random sampling algorithm → so the technique never does worse than that baseline, which the results confirm since the baseline never wins significantly on any program.
What it costs (trade-offs and scope)
- It needs full control of the schedule, which means heavy machinery. The program is rewritten at the binary level and its threading primitives are replaced by a user-space scheduler that serializes execution. That is what makes fine-grained control possible, but it is intrusive and the overhead is real — which is why the evaluation uses a wall-clock budget rather than a schedule count, so that overhead is charged honestly.
- Reads-from equivalence is a proxy, not a guarantee of everything. It captures control and data flow through shared memory, which covers the bugs in these suites, but it is still an abstraction chosen for tractability.
- Abstract schedules may be infeasible. A mutation can produce constraints no execution can satisfy, and a negative constraint can become unavoidably violated, in which case the attempt is wasted. The design reduces this compared to concrete schedules but does not eliminate it.
- Comparison against the closest competitors was not possible. The two state-of-the-art concurrency-aware fuzzers are not publicly available and the authors could not obtain them despite asking; their reimplementation of one could not trigger the motivating bug even after millions of executions, which they report rather than presenting as a fair comparison.
- Feedback arrives only after a full execution, and a rival learns faster. Their own reinforcement-learning comparison finds fewer bugs overall — about 30 against 44 — yet finds the bug on the very first attempt in more programs than any other tool, 13 of them, because it learns from partial traces while the fuzzer only judges a completed run. The authors report this openly.
The evaluation
The tool was measured on 49 programs containing concurrency bugs, drawn from a standard concurrency-testing benchmark suite and a set of real-world programs with concurrency-related memory and pointer vulnerabilities. Most bugs manifest as assertion violations, with four deadlocks and 13 memory-safety issues. The metric is the number of schedules needed to reach the FIRST bug in each program, chosen so that one failure cannot mask another. Each program was given a five-minute budget and each configuration repeated 20 times, against a systematic parallel testing tool, a stateless model checker, a depth-based randomized algorithm, a partial-order sampler, and a custom reinforcement learning implementation using the same reads-from information.
Searching the space of thread interleavings
| Property | Random sampling | Systematic enumeration | Reads-from greybox fuzzing |
|---|---|---|---|
| What it searches | |||
| Learns between attempts | |||
| On a narrow bug window | |||
| Redundant work | |||
| Bugs found of 49 programs |
Check yourself
Check your understanding
1. On the paper's benchmark, uniform sampling hits the bug with probability around 3 in 100 trillion, yet the tool finds it in about six attempts. Predict what changed.
2. The authors first tried mutating concrete schedules guided by reads-from coverage, and found it performed worse than plain random testing. Predict why, and what fixed it.
3. Measuring exploration on the hardest benchmark, one reads-from sequence accounted for over half of all 10000 executions without greybox feedback. Predict why that matters and how feedback helps.
4. The proactive scheduler falls back to an established random sampling algorithm whenever it cannot steer the execution. Predict why that design choice matters.
Sources
- Greybox Fuzzing for Concurrency Testing (ACM DL, DOI 10.1145/3620665.3640389) — ASPLOS 2024.
- Author PDF — the full 17-page paper, read in full for this explainer.
- RFF artifact and infrastructure — the Reads-From Fuzzer, released for use and further research.