Concurrency bugs without brute-force scheduling: an agent reads semantics, finds 38 more bugs in the same budget
Synopsis
Concurrency bugs surface only under specific thread interleavings, and a scheduler cannot tell which scheduling points matter. Reins turns an agent's reasoning about concurrency semantics into constraints on event orders and variable states for a controlled scheduler, then uses execution results to revise the hypothesis. On three public benchmarks it detects more bugs than existing controlled scheduling techniques within the same time budget, 38 more than the best baseline on the largest benchmark, and finds six previously unknown concurrency bugs in two real-world projects, three confirmed by developers.
Interpretation
Thread scheduling is no longer decided only by probability or coverage signals, but directed by reasoning about the program's concurrency semantics. Prior controlled concurrency testing explored the interleaving space through systematic enumeration, randomized sampling, reinforcement learning, or greybox fuzzing, operating at the schedule level where bug-relevant decisions are hard to distinguish. On the 52 single-bug programs of SCTBench and ConVul, Reins detects 48, while SURW, RFF, PCT-3, PCT-10, and RW detect 46, 47, 44, 43, and 35; all Reins detections finish within about 100 schedules, whereas baselines show long tails of up to tens of thousands of schedules on hard programs.
The agent starts from shared-variable accesses observed in real executions, then reads source code and static information on demand to propose bug hypotheses. Prior techniques did not fully exploit concurrency semantics, such as which access combinations are dangerous under the program logic and what state the program must be in for a bug to trigger. A hypothesis becomes a schedule plan, a set of constraints on event orders and variable states involving only the few key events and variables needed to trigger the bug; the controlled scheduler follows the plan at relevant scheduling points and decides the rest at random, and execution results revise the plan or hypothesis.
Execution results serve as evidence, and a run that triggers the bug records its scheduling trace for deterministic replay. The agent's reasoning may be plausible yet incorrect, and may even hallucinate variables and code locations that do not exist, so its claims do not directly constitute evidence. Events and variables in a plan are validated against the program before execution; on the 75 targets and 1,500 injected bugs of RaceBench, Reins detects 769, 38 more than the best baseline SURW at 731, with its curve still rising when the budget ends.
Perspective
The work targets shared-memory multithreaded programs, detecting and reproducing concurrency bugs within the code reached by given test entries and inputs, covering common patterns such as data races, atomicity violations, order violations, and deadlocks that lead to crashes, assertion failures, or hangs. Evaluation runs on three public benchmarks and two real-world projects, with a total time budget of 5 hours per target. A reader interested in code covered by given test cases will find the scope aligned with this evaluation setup.
The randomness of LLM outputs is the main uncertainty, as hypotheses and plans may differ across runs, and due to cost each tool and configuration is run once with a single model. Injected bugs in RaceBench leave recognizable traces in source code, which the evaluation anonymizes; benchmark code may appear in the model's training corpus, but memorization at most helps locate suspicious code and cannot replace constructing a replayable triggering schedule. Comparisons with baselines are made under the same time budget, so they are not directly comparable with the original papers that budget by schedule count. In addition, no tool detects more than about 51% of the injected bugs within the 5-hour budget, partly because a single seed input is used uniformly and because of the budget itself.
