Source-linked AI summary
REINS: Agent-guided Thread Scheduling for Concurrency Bug Detection and Reproduction
Yu Zhang, Corina S. Pasareanu, Guowei Yang
TL;DR
Concurrency bugs may depend on rare interleavings, and controlled testing can struggle to find them within a limited budget because it insufficiently exploits program semantics. REINS combines runtime observations and static information to form bug hypotheses, translate them into scheduling constraints, and refine them using execution evidence. It detects more bugs than baselines across three public benchmarks and finds previously unknown bugs in real-world projects.
Problem
Method
REINS combines runtime observations and static program information to form bug hypotheses, translate them into event-order and variable-state constraints, and refine plans from controlled execution results.
Source: §1 · p. 2Results
Across three public benchmarks, REINS detected more bugs than all baselines, including 38 more than the best-performing baseline on RaceBench within the same time budget; it found six previously unknown bugs, three developer-confirmed.
Source: §1 · p. 2Takeaways & Limitations
On these benchmarks and projects, agent reasoning about concurrency semantics can guide scheduling toward bug-triggering interleavings and support reproducible detections.
Source: §8 · p. 15The evaluation used one run per tool and configuration and a single model, while LLM output randomness may vary hypotheses and plans across runs.
Source: §6 · p. 14
Abstract
from arXiv · showhide
Concurrency bugs manifest only under specific thread interleavings, making them hard to detect and reproduce. Existing controlled concurrency testing techniques take over thread scheduling to explore the interleaving space. As the space grows rapidly with program scale, finding interleavings that can trigger bugs within a limited budget remains challenging. The program's concurrency semantics can reveal which variable accesses and synchronization operations under specific interleavings lead to unexpected program behavior, and thus help focus the exploration on bug-relevant interleavings. However, prior techniques have not fully exploited such semantic information. In this paper, we present REINS, an agentic approach for detecting and reproducing concurrency bugs. At its core, REINS guides thread scheduling with the agent's reasoning about the concurrency semantics and known concurrency bug patterns. REINS starts with runtime observations and combines them with static information to reason about the program's concurrency behavior and formulate hypotheses about potential bugs. A hypothesis translates into a set of constraints on event orders and variable states, guiding a controlled scheduler toward interleavings likely to trigger the bug. REINS draws conclusions from the execution results and keeps refining the constraints until the bug is triggered or the hypothesis is refuted. Compared with existing techniques on three public benchmarks, REINS detects more bugs within the same time budget. Furthermore, REINS found six previously unknown concurrency bugs in real-world projects, three of which have been confirmed by the developers.
1 Introduction
Concurrency bugs can require rare interleavings and specific program states, which existing controlled scheduling approaches struggle to find within limited budgets. REINS uses agent reasoning about concurrency semantics to guide and refine schedules, and detects more bugs than baselines across three public benchmarks.
1 Introduction
- Existing controlled testing struggles to expose bugs with narrow triggering windows and specific state preconditions within a limited budget.These methods insufficiently exploit program semantics, such as which accesses are dangerous and which states trigger failure.Source: §1 · p. 1
- REINS turns semantic bug hypotheses into event-order and variable-state constraints, then uses controlled executions as evidence to refine or reject them.It validates proposed events and variables before execution and records triggering schedules for deterministic replay.Source: §1 · p. 2
- REINS iterates through comprehend, attempt, and assess phases, proposing hypotheses, testing schedule plans, and deciding what to investigate next.Its design addresses incomplete semantic understanding, the gap between semantic reasoning and low-level scheduling, and unreliable agent output.Source: §1 · p. 2
- REINS detected more bugs than all baselines across three public benchmarks, including 38 more than the best-performing baseline on RaceBench within the same time budget.It also found six previously unknown concurrency bugs in real-world projects, three confirmed by developers.Source: §1 · p. 2
2 Overview
The SpiderMonkey example shows how a brief race can leave a cached flag inconsistent with the map and cause an out-of-bounds access to crash. REINS uses runtime and static information to identify bug-relevant orders and states, then guides and revises controlled schedules.
2 Overview
- A stale write to CodeExists after a concurrent registration can leave the map non-empty while the flag is false, allowing a later out-of-bounds access to skip its bounds check and crash.The triggering window lasts one statement after the last code block is unregistered, so natural scheduling is unlikely to produce the needed sequence.Source: §2 · p. 3
- Controlled scheduling can record and replay executions, but numerous scheduling points obscure which decisions matter for bugs with narrow windows and multiple ordering constraints.Figure 2 depicts three agent phases under a total time limit, with per-subagent limits on plan versions and runs per plan.Source: §2 · p. 3, Figure 2 · p. 4
- REINS combines runtime observations and static information to hypothesize a bug, then constrains relevant event orders and variable states while scheduling other points randomly.For the example, the worker must register and access memory before the main thread writes stale false, then access out of bounds again while the false value remains.Source: §2 · p. 4
3 Preliminary
REINS targets observable failures from common concurrency bug patterns in shared-memory programs, excluding silent errors that terminate normally. The preliminary section defines the program, access, hypothesis, plan, and execution-result concepts used to express and evaluate its schedules.
3 Preliminary
- An access site τ denotes a read or write of variable v at a source location, while an event e pairs that site with the thread performing it.The observed access summary σv records events in observed order and the locks held when each event occurs.Source: §3 · p. 4
- A bug hypothesis records the involved variables, access sites, and a natural-language account of the suspected interleaving and expected failure.A schedule plan combines ordering constraints on events with state constraints requiring predicates to hold at specified events.Source: §3 · pp. 4–5
- Each plan run records termination, satisfied order and state constraints, a scheduling trace for replay, and newly reached code coverage.Aggregated results summarize these fields across repeated runs of a plan.Source: §3 · p. 5
- The target is detecting and reproducing common concurrency bugs that cause observable failures, such as crashes, assertion failures, or hangs; silent wrong results are excluded.Target patterns include data races, atomicity violations, order violations, and deadlocks.Source: §3 · p. 5
4 Methodology
REINS runs bounded rounds that move between understanding concurrency behavior, testing candidate bugs with schedule plans, and assessing evidence to steer subsequent work. Its infrastructure tracks program observations and candidate status, constrains selected scheduling points, and records traces for replay.
4 Methodology
- REINS operates in rounds under a total time budget, dispatching one bounded subagent per candidate and reporting detected bugs with scheduling traces for reproduction.Each subagent has a time limit, a maximum number of plan versions, and a maximum number of runs per plan.Source: §4 · p. 5
4.1 Global States and Execution Infrastructure
- Global states track reached files, observed shared-variable accesses, hypothesis status, and plan attempts; the controlled scheduler prioritizes plan constraints and randomizes irrelevant threads.The scheduler serializes instrumented variable accesses and intercepted synchronization operations, records each scheduling decision, and can replay a triggering trace deterministically.Source: §4.1 · pp. 5–6
4.2 Comprehend: Hypothesizing from Runtime Observations and Static Information
- In comprehend, runtime traces identify shared variables and conflicting accesses, which guide selective source inspection and static queries before the agent proposes bug hypotheses.The agent combines these clues with program behavior and known bug patterns to reason about risky interleavings and their consequences.Source: §4.2 · p. 7
4.3 Attempt: Guiding Thread Scheduling to Confirm or Refute Bug Hypotheses
- In attempt, subagents turn each hypothesis into event-order and variable-state constraints, validate and execute plans, then revise them using whether runs engaged the plan and triggered the expected failure.Attempts stop on a trigger, refuting evidence, or exhaustion of the plan-version or time budget; successful candidates retain a replay trace.Source: §4.3 · pp. 7–8
4.4 Assess: Analyzing Results to Steer the Next Round or Conclude
- In assess, REINS propagates related evidence, analyzes success and failure patterns, reviews new coverage, and chooses whether the next round resumes comprehension or attempts.The process ends when all candidates are settled or the time budget is exhausted.Source: §4.4 · p. 8
5 Evaluation
REINS is evaluated against controlled-scheduling techniques on three benchmarks, on two real-world projects, and through analyses of its key designs. It detects more RaceBench bugs than the best baseline within the same time budget and finds six previously unknown real-world bugs.
5.1 Experimental Setup
- The evaluation used 42 curated SCTBench programs, 10 ConVul bugs, and 75 RaceBench targets, with a five-hour total budget per target.REINS also used a limit of five plan versions, 50 runs per plan, and 30 minutes per subagent.Source: §5.2 · p. 9, §5.1 · p. 9
5.2 RQ1: Comparison with Existing Techniques
- REINS detected 48/52 SCTBench and ConVul programs versus 46 for SURW, 47 for RFF, 44 for PCT-3, 43 for PCT-10, and 35 for RW.All REINS detections finished within about 100 schedules, but its median time to trigger was about 7 minutes and it was two to three orders of magnitude slower than the baselines.Source: Figure 3 · p. 9, §5.2 · p. 10
- REINS missed bugs requiring rare state values and within-statement interleavings that its source-level instrumentation could not control; RaceBench’s seed-only input and five-hour budget also limited all tools.Some RaceBench bugs require mutated inputs, and detection curves for REINS, SURW, and RFF were still rising when the budget ended.Source: §5.2 · pp. 10–11
- 769 of 1,500 RaceBench bugs were detected by REINS, 38 more than SURW’s 731; REINS surpassed SURW between 60 and 90 minutes and continued growing through the budget.Figure 4 plots cumulative detections summed over 75 targets.Source: §5.2 · p. 10, Figure 4 · p. 11
5.3 RQ2: Bug Finding in Real-world Projects
- REINS found six previously unknown bugs in NSPR and SpiderMonkey; three SpiderMonkey bugs were confirmed and fixed by their developers.The bugs include atomicity violations, a deadlock, and data races.Source: §5.3 · pp. 11–12
5.4 RQ3: Analysis of Key Designs in REINS
- On five x264 variants, full REINS detected the most bugs; removing runtime observation reduced dispatch effectiveness to 6.6%, while removing static inspection reduced it to 11.8%.Without runtime clues, candidates often diverged from executed paths; without static inspection, benign races reached dispatch and increased its cost.Source: §5.4 · p. 12, Table 4 · p. 13
- Of 68 x264 bugs, 45 were triggered by the first plan version and 23 by a revised version; 27 appeared in the first round and 41 in later rounds.The assess phase prioritized candidates for later rounds and expanded the pool; 453 candidates were proposed, but only 159 were dispatched.Source: Figure 5 · p. 13, §5.4 · p. 13
- All agent-guided configurations detected more bugs than random walk, and full REINS detected more than twice as many while covering every bug random walk found.The schedule plans direct the scheduler at relevant points while it schedules the rest randomly.Source: §5.4 · p. 13
6 Discussion
REINS’s agent reasoning accounts for much of its runtime cost, while sequential subagent execution is a potential efficiency improvement. Its evaluation and current implementation also have scope boundaries involving run variability, supported programs, and observable bug symptoms.
Cost and Efficiency
- About 87% of REINS’s wall time is spent in subagents, which ran sequentially per round; parallel execution is possible and could significantly reduce wall time.About 90% of input tokens are prompt-cache reads, and cheaper models may suit simpler subagent tasks.Source: §6 · p. 14
Threats to Validity
- The evaluation runs each tool and configuration once with a single model, leaving LLM-output randomness as a threat; original-paper schedule-budget results are not directly comparable to the shared time-budget evaluation.The authors say the 127 targets and more than 1,500 bugs mitigate the randomness risk by grounding conclusions in overall results.Source: §6 · p. 14
Limitations
- REINS is limited to code reached by the given entries and inputs, C/C++ shared-memory multithreading, and bugs manifesting as crashes, assertion failures, or hangs.Silent symptoms such as data corruption require additional oracles.Source: §6 · p. 14
7 Related Work
Prior controlled-scheduling work guides exploration using bounds, probabilities, or execution signals, while active testing targets predefined bug patterns. REINS instead forms semantics-based hypotheses and revises schedule plans using execution results; its agent-driven scheduling is complementary to other agent testing approaches.
7 Related Work
- Prior controlled-scheduling techniques choose schedules using bounds, probabilities, or execution signals, while active testing predicts instances of predefined bug patterns and schedules them.Examples include RACEFUZZER for races, CTRIGGER for atomicity violations, and DEADLOCKFUZZER for deadlocks.Source: §7 · p. 14
- REINS is not limited to predefined patterns: its semantics-based hypotheses constrain variable numbers of events and program states, and execution results revise later plans or hypotheses.This contrasts with the fixed pattern focus of active testing.Source: §7 · p. 15
- SLYP [25] uses agents to locate race-induced memory corruption and synthesize concurrent-invocation PoCs, whereas REINS takes over and guides thread scheduling.CONCOVUP [6] generates test drivers and access-pair coverage; its focus complements REINS’s scheduling control over covered code.Source: §7 · p. 15
8 Conclusion
The paper presents agent-guided thread scheduling in REINS, reporting stronger bug detection than existing controlled-scheduling techniques on three public benchmarks and six previously unknown bugs from two real-world projects.
8 Conclusion
- Agent-guided thread scheduling uses an agent’s reasoning about concurrency semantics to guide schedules toward bug-relevant interleavings.Source: §8 · p. 15
- REINS detects more bugs than existing controlled-scheduling techniques on three public benchmarks.Source: §8 · p. 15
- REINS finds six previously unknown concurrency bugs in two real-world projects.Source: §8 · p. 15