MC Mutants: Evaluating and Improving Testing for Memory Consistency Specifications

Testing whether a chip honours the memory ordering rules it promises means running tiny concurrent programs millions of times and watching for a forbidden outcome — but how do you tune that testing when a real violation may never appear at all, so you have no signal telling you whether your setup is good or your machine is correct? MC Mutants (UC Santa Cruz, Google) manufactures near-misses — take a forbidden execution, break exactly one edge of the cycle that makes it forbidden, and you get a program whose outcome is now legal, adjacent, and countable.

Why this problem is worth solving

The promise a platform makes about memory is precise, and expensive to keep.

A test for such a promise is a program whose outcome should be impossible.

What people did before, and where it broke

• Execute sequences of memory accesses and analyse the trace. The earliest approach to checking memory behaviour, and a reasonable one before the formal models matured. Where it broke. Without a specification to compare against, it is hard to say which observed orderings are actually violations rather than merely surprising.
• Derive litmus tests from the formal model and run them for many iterations. The modern standard, and genuinely productive — this family has found bugs across many platforms. Where it broke. A test that finds nothing tells you nothing: the forbidden outcome may be impossible, or merely rare and not provoked. Whether the test fires depends heavily on the environment around it.
• Apply memory pressure and thread shuffling around the test. Adding stress threads and randomising placement demonstrably makes rare behaviours appear, and one prior system exposes seventeen tunable parameters for doing so. Where it broke. Tuning seventeen parameters needs a score, and there is none. Prior work tuned by maximising the count of weak-but-legal behaviours in some tests without arguing that this predicts anything.
• Run several test instances in parallel. Done for multicore processors, where it helps. Where it broke. It did not transfer to graphics processors, where thousands of threads are available but assigning them to test instances safely, without divergent control flow, and under tunable stress had no efficient solution — so GPU testing inherited a single-instance design that leaves most of the machine idle.
• Just run the tests longer. Always available, and the reason nobody could say when to stop. Where it broke. With no way to relate running time to the probability of catching a bug, there is no principled budget — which matters enormously when the target is a conformance suite that must run on every commit.
• The gap. Every part of this discipline is calibrated against an event that, for a correct platform, never happens. Without a substitute signal, the environment that decides whether testing works at all can only be tuned by intuition, and prior approaches consequently missed real bugs.

How you measure a test that almost never fires

The idea

You cannot tune an instrument against an event that never happens, so build one that almost happens. This is the whole difficulty of the field stated plainly: everything about memory consistency testing — how much stress to apply, where to put threads, how to lay out memory, how long to run — changes whether a bug appears, and none of it can be evaluated, because the correct outcome and the untested outcome look identical. Both are zero. Prior work resolved this by maximising the number of weak-but-legal behaviours observed in some unrelated tests, an intuition offered without argument, and the price was real bugs going unfound. The move here is to manufacture a signal with the right shape. Take the execution the test forbids, break one edge of the cycle that makes it forbidden, and the resulting program has an outcome that is legal, frequent enough to count, and requires the machine to do very nearly what the bug would require. A whole class of failure that produces no crash and no visible symptom, so that the usual detector has nothing to detect, is the same predicament the container isolation testing work covered elsewhere on this site describes, where a missing check does not make the kernel fall over but quietly answers a question about somebody else.

The mutation is derived from the formal model rather than invented. What keeps this from being a collection of plausible-looking variants is that the notion of adjacent is defined precisely. A disallowed execution is a cycle in happens-before; the edges in that cycle come from different sources, and only some correspond to something a program can change — the order of statements in a thread, whether two accesses name the same address, whether a fence is present. Those are exactly the edges the mutators disrupt, and they are disrupted exhaustively: three cycle templates, every syntactic edge in each, yielding 20 conformance tests and 32 mutants. Each mutant then stands for a specific way an implementation could be wrong. Reversing two accesses in program order asks whether the environment can expose a fine-grained interleaving, which is what a reorder buffer would produce. Redirecting one access to a second address asks about aliasing, the kind of mistake made when addresses are computed dynamically. Removing a fence corresponds directly to the real bug found here, where atomic operations were weakened in an intermediate representation. Writing down formally what the platform is permitted to do, and then converting that statement into a search for hardware that exceeds it, is the same manoeuvre the speculation contract work covered elsewhere on this site makes when it fuzzes a black-box processor against a written statement of what leaking is allowed.

Once the environment can be scored, the obvious improvement becomes findable — and it is enormous. Graphics processors offer thousands of threads and the testing methodology inherited from multicore processors used two of them. The obstacle was assigning test instances to threads without divergent control flow, which these machines execute serially, and while still permitting the stress parameters to vary. The solution is arithmetic: number the threads, pick a value coprime to the count, and multiply modulo the count to get a permutation that pairs each thread with a partner in a few instructions, with no branching and without the trivially adjacent pairings that prior work showed to be ineffective. That turns 300 test instances per tuning run into roughly 125,000, and the mutant death rate rises by a factor of 2,731. It also converts a fifteen-hundred-second observation into a ten-per-second one, which is how the bug that no amount of stress tuning had exposed became routine. And because the death rate is now a number, running time can be turned into a probability: the environment for each test is chosen to put the most devices above the rate a target confidence demands. That such bugs live in the orderings that rarely occur, and that provoking those orderings deliberately is the only way to see them, is the same lesson the message-reordering work covered elsewhere on this site draws about concurrent programs that must be correct under every schedule.

Following one forbidden outcome into a mutant and back

The cycle is what makes the execution illegal, since it says an event happened before itself. Different specifications add different edges, but every platform surveyed forbids this one.

Why it works

• A near-miss is countable where the real thing is not. A correct platform produces zero violations and an untested one produces zero as well, so the quantity everyone cares about carries no information during tuning → but breaking one edge of the forbidding cycle yields an outcome that is legal and therefore appears repeatedly → giving a rate that can be measured on any machine, correct or not.
• Adjacency has a formal definition, so the mutants are not guesses. Plausible-looking variants of a test would prove nothing about what the environment can expose → but the edges of a happens-before cycle are exactly what makes an execution illegal, and disrupting one that the source text controls produces a program requiring nearly the same machine behaviour → so each mutant corresponds to a specific way an implementation could be wrong, and the set is exhaustive for each cycle template.
• Only syntactic edges are usable, and that is a feature. Some edges arise from what happened at runtime and cannot be altered by editing a program → and a program is the only interface a black-box test has to the platform → so restricting mutation to program order, address identity and fence presence guarantees every mutant is actually runnable.
• Thousands of idle threads were the resource nobody could reach. Assigning test instances to threads on a graphics processor risks divergent control flow, which those machines execute serially, undoing the parallelism → but multiplying a thread index by a coprime value modulo the thread count pairs threads in a few branch-free instructions and avoids the adjacent pairings shown to be ineffective → raising instances per run from 300 to about 125,000 and the mutant death rate by a factor of 2,731.
• A rate converts directly into a confidence and therefore into a budget. Testing time had no principled stopping point because nothing related duration to the chance of catching a bug → but if a behaviour is seen a given number of times in a run, the probability that another run of the same length sees it at least once follows immediately → so a per-test environment can be chosen to put the most devices above the rate a target confidence requires, giving 82 percent of mutants killed at 64 seconds per test with the probability of a missed reproduction below one in a hundred thousand.

What it costs (trade-offs and scope)

• The score is only meaningful if the platform is weak enough to show the mutant behaviour. Across four graphics processors, 83.6 percent of mutant behaviours were observable — but the paper is explicit that a strong implementation of a weak specification, such as C++ on a strongly ordered processor, would score poorly while being well tested. The remedy offered is pruning mutants against a precise model of the implementation, which is knowledge that is often unavailable.
• The validation of the whole idea rests on three bugs. The correlation coefficients are high, from 0.893 to 0.996, and they span three vendors and all three mutators — but three points is the entire empirical basis for the claim that killing mutants predicts finding bugs.
• The specification being tested is not official. The platform had no formal memory model at the time, so the authors construct what they describe as a non-controversial foundation. Conformance is measured against their reading of it, which is a reasonable move and still not the same as testing against a standard.
• Only one level of the execution hierarchy is covered. Testing is restricted to threads in different workgroups, for stated and sensible reasons, but these machines have a hierarchy and the interactions between its levels are where formal analysis is hardest.
• The memory model considered is deliberately simplified. Non-atomic accesses are excluded, only release and acquire fences are modelled, and operations carry no per-operation memory ordering. That covers the case study and not the general problem.
• Stress does not help uniformly, and the aggregate hides that. Adding stress to the parallel environment raises the overall mutation score from 72.7 to 83.5 percent, but gives no mutation-score benefit on one vendor, negligible rate benefit on the same one, and on another actually lowers the death rate while raising the score.
• The prior single-instance approach wins on one device, which the paper attributes to search rather than to any advantage — the older environments are a strict subset of the new ones, so an equivalent exists and was not found. That is honest, and it also means the tuning is random search over a large space with no optimality claim.
• Tuning is 150 random configurations chosen for what fits overnight. Seventeen interacting parameters make the full space infeasible, and no argument is made that 150 samples suffice.
• The devices with the weakest memory models are absent. Mobile parts were not supported by the platform at the time, so the vendors whose hardware is furthest from sequential consistency — the ones where violations would be most likely — could not be tested. One browser implementation was used, chosen as the most stable.
• The confidence figure assumes measured rates transfer. A reproducibility target is computed from death rates observed on four devices during tuning, then applied to a conformance suite that will run on hardware nobody has seen. The per-test environment selection is explicitly designed to be robust across devices, and is fit to four of them.
• The mutators are complete for three chosen cycle shapes. Every syntactic edge disruption is enumerated within each template, which is a real completeness claim, but the templates themselves are three shapes selected by the authors.

The evaluation

Check yourself

Sources

The paper is “MC Mutants: Evaluating and Improving Testing for Memory Consistency Specifications” by Reese Levine, Tianhao Guo, Mingun Cho, Alan Baker, Raph Levien, David Neto, Andrew Quinn and Tyler Sorensen, published at ASPLOS 2023, pages 473-488, DOI 10.1145/3575693.3575750. The authors are at UC Santa Cruz and Google.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the two motivating litmus tests and the bugs they exposed, one requiring stress and one requiring parallelism; the background on memory consistency specifications covering data races, the sets and relations used to describe an execution, the definitions of sequential consistency and of coherence as the common floor, and the addition of release and acquire fences; the treatment of litmus tests as cyclic candidate executions and the worked cycles for both motivating tests; the description of the target platform, its execution hierarchy, its unusually wide set of backends and the stated restriction to one scope; the three mutators, each given with its abstract cycle template, its conformance set including the rules for instantiating read-modify-write variants, its edge disruptor and the implementation error that disruptor corresponds to, together with the counts of tests and mutants each produces; the discussion of when mutant behaviour is unobservable and mutants should be pruned; the parallel test environment with its thread-pairing permutation, its memory location assignment, its striping across workgroups and its incorporation of the seventeen prior stress parameters; the test confidence strategy with its reproducibility formula, the environment-merging algorithm and the arithmetic of total reproducibility across a suite; and the evaluation covering the four devices, the tuning methodology and its runtime, the mutation scores and death rates broken down by mutator and device, the budget-versus-score analysis at two reproducibility targets, the correlation analysis against three known bugs, and the adoption of the work into two conformance test suites.