CS Paper Radar

Automatically Detecting and Fixing Deadlocks in Go Code with GoDDaR

Gustavo Feio, Jorge Coelho, Miguel Flor, João M. Lourenço, António Ravara

cs.PL cs.DCcs.SE ·submitted 2026-10-06 18:29 UTC · v1
benchmark

Abstract

The Go programming language provides a lightweight abstraction for concurrent programming through goroutines, which are prone to deadlocks. Go includes a runtime detector that aborts execution when all threads are blocked (a global deadlock). However, due to nondeterministic thread scheduling, this runtime mechanism only detects global deadlocks that manifest during execution and cannot identify partial deadlocks, where a subset of goroutines is permanently blocked while at least one remains runnable. Statically detecting local deadlocks is essential for developing dependable concurrent software. While several tools statically detect deadlocks in concurrent programs, few assist developers in fixing them. Detecting and resolving partial deadlocks requires reasoning about complex interleavings and communication patterns, an inherently challenging task. In this paper, we present GoDDaR, a tool that detects unobserved global or partial deadlocks in Go programs and suggests concrete fixes. GoDDaR translates Go source code into an intermediate representation reflecting message-passing communication events and composition patterns. Partial deadlocks are identified through symbolic analysis over this representation. To resolve detected deadlocks, our algorithms transform the intermediate representation to eliminate problematic synchronization patterns, allowing GoDDaR to generate fix suggestions for the original Go source code as a diff. We evaluate GoDDaR on a benchmark suite of representative deadlock examples from literature and git repositories to validate algorithm correctness and compare performance against the state of the art. Results demonstrate that GoDDaR is competitive with top approaches in partial deadlock detection and advances the state of the art in automated deadlock fixing.

Closest papers

Nearest neighbours by meaning across the whole index.

Validating Concurrent Correctness Witnesses with Ghosts by Thread-Modular Abstract Interpretation

cs.PL cs.SE ·2026-11-18 ·Michael Schwarz, Zhendong Ang, Umang Mathur
top venue similarity 0.68
Abstract · Accepted to POPL '27; Extended version with appendices

Concurrent programs are notoriously difficult to write and to reason about, and even tools based on sound theoretical foundations can produce incorrect results due to implementation bugs. Correctness witnesses have been proposed as a way to increase the confidence in the verdicts of software verifiers by enabling independent validation. Recently, correctness witnesses have been extended to the concurrent setting, by introducing ghost variables to allow encoding more expressive invariants. While different approaches to producing witnesses with ghosts exist, validation techniques are still lacking; instead of leveraging the information encoded in the ghosts to guide the validation process, validators merely treat ghost instrumentation and invariants over ghost variables as additional proof obligations. We propose a novel framework for the validation of concurrent correctness witnesses that exploits the semantic information encoded in ghost variables. It combines a checking phase, which establishes the semantic content of the ghost instrumentation, with an exploitation phase making use of this information. Both phases are formulated as thread-modular abstract interpretation. In particular, we consider two different classes of ghost variables and techniques for exploiting them, one based on resource invariants and one based on phases. Phase ghosts guide the degree to which the abstract interpretation considers interleavings instead of always abstracting them coarsely. In this way, the abstract interpreter can validate witnesses containing invariants beyond the reach of unguided thread-modular analysis, while still retaining its scalability benefits. We have implemented our framework in a static analyzer and evaluate it on witnesses encoding resource invariants obtained from a state-of-the-art software verifier, as well as on hand-crafted witnesses encoding phase information.

0.50

Beyond Locks and Thread IDs: Static Data Race Detection Off The Beaten Path (Extended Version)

cs.PL cs.SE ·2026-08-31 ·Daniel Bund, Julian Erhard, Michael Petter, Michael Schwarz
similarity 0.67
Abstract · 49 pages, 12 figures, 6 tables

Maintaining an abstraction of the execution history of threads can improve the precision of data race detection in static analysis. Here, we extend the digest framework to handle concurrency constructs and synchronization mechanisms that have been ignored in static race detection. We introduce mechanisms for the commonly used thread barriers, as well as pthread_once, which allows to ensure that an action is executed only once. We also instantiate the framework with an abstraction of locksets held by ancestor threads. We propose a suite of litmus tests to evaluate analyses for these features and compare our implementation to state-of-the-art tools, finding that they lack support.

0.39

Sound Automatic Lock Placement for Concurrent Programs with Pointers

cs.LO ·2026-11-12 ·Nicolas Waldburger, Florian Faissole, Ryo Okabe, Denis Cousineau
published similarity 0.67
Abstract · 39 pages, 7 figures

We propose a lightweight method for automatic lock placement in concurrent POSIX programs with explicit pointer manipulation, such as C programs. Given a program that lacks sufficient user-placed mutexes, or contains none at all, our method introduces new mutexes to prevent data races. The method is formally proven to guarantee the absence of data races and mainly consists of three steps. The first step performs lockset analysis and may-happen-in-parallel analysis. The second step conducts a concurrent points-to analysis derived from a Steensgaard-like procedural analysis, where per-thread points-to graphs are unified using a special completion rule. The final step places locks to prevent data races while respecting a lock ordering to avoid deadlocks. In addition, user-annotated critical sections are protected through insertion of dedicated locks. Since lock placement is a complex and error-prone task, our method aims at helping developers write correct concurrent programs.

0.41

Fine-grained Causal Reversibility for Asynchronous Channel-based Programming

cs.PL ·2026-08-29 ·Shunya Oguchi, Shoji Yuen, Nobuko Yoshida, Claudio Antares Mezzina
published similarity 0.67
Abstract · 33 pages, 10 figures. Extended version of the paper accepted at ICTAC 2026. This version includes complete proofs and additional technical m…

Causal reversibility has emerged as an effective technique for debugging concurrent systems. In particular, rolling back and replaying a concurrent program with causal consistency has been found very helpful in debugging concurrency bugs. In channel-based communication, queue ordering creates dependencies that prevent causally independent actions from being rolled back and replayed. To enable efficient rollback and replay without being constrained by queue dependencies, it is necessary to analyse causal dependencies between messages in queues and reorder independent messages. This paper presents revGo, a core of the Go programming language assuming unbounded asynchronous channels. Our rollback-and-replay semantics allows us to reorder messages in the queue if they are not causally related in the forward execution. It is shown that reordering independent messages generates no configuration with non-reachable processes. By reordering independent messages, rollback and replay are implementable with minimality by assigning unique keys to communications.

0.40

Modular Responsiveness Verification of Rust Async Runtimes

cs.PL ·2026-10-06 ·Yanze Li, Ivan Beschastnikh, Alexander J. Summers
published similarity 0.62
Abstract · To appear at ESOP 2027, preprint with appendix

Asynchronous (async) programming is a popular paradigm for managing concurrency. Languages that provide async support typically have a runtime to manage asynchronous executions. These runtimes are critical infrastructure, yet verifying them has received little attention. One reason is that a property that users care most about from an async runtime is a liveness property: tasks submitted to the runtime eventually make progress. Verifying liveness is challenging for libraries that are both concurrent and highly optimized. We present a lightweight and modular proof technique for verifying eventual progression guarantees for Rust async runtimes. We describe this technique in the context of a simple language based on Rust and Rust's async model. We then realize this proof technique as a set of static analyses for Rust and use these to verify eventual progression of several key components of multiple Rust async runtime implementations.

0.19

VerusWeave: A Benchmark for Proof Repair in Concurrent Verus Programs

cs.SE cs.AIcs.LOcs.PL ·2026-10-30 ·Pedro Ribeiro, Martim Afonso, André Vasconcelos, João F. Ferreira
benchmarkcode/data similarity 0.61
Abstract · 4 pages, 2 figures, 2 tables

Concurrent software underpins critical infrastructure, including operating systems and databases, yet thread interactions can have bugs that bypass conventional testing. Verus extends Rust with formal verification capabilities, enabling developers to specify, implement and prove the correctness of concurrent code in the same language. Although coding agents have been explored for automated proof construction, existing Verus benchmarks offer limited coverage of concurrency-specific examples that connect atomic operations to abstract protocols. To address this gap, we introduce VerusWeave, the first benchmark dedicated to concurrent proof repair, derived from four open-source projects. It comprises 75 focused tasks and 17 full-module variants that exercise features used to verify low-level concurrent code. Tasks remove selected proof annotations and require agents to fill gaps, while preserving executable code and specifications. The evaluation harness validates repairs using Verus and a change checker, recording solutions, execution traces, and resource usage. An initial evaluation of four general-purpose coding-agent harnesses achieved 75-85% success on focused tasks and 29-47% on full-module variants, highlighting the challenge of autonomous module-wide repairs. VerusWeave provides a reusable foundation for evaluating automated proof construction for concurrent software.

0.32

REINS: Agent-guided Thread Scheduling for Concurrency Bug Detection and Reproduction

cs.SE ·2026-10-09 ·Yu Zhang, Corina S. Pasareanu, Guowei Yang
similarity 0.61
Abstract

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.

0.26

Handling Complex Interference Compositionally: A Concurrent Garbage Collector Case Study

cs.LO ·2026-09-23 ·Nisansala P. Yatapanage
top venuehot direction similarity 0.60
Abstract · To be published in the 12th International Symposium on Dependable Software Engineering Theories, Tools and Applications (SETTA 2026)

Rely/Guarantee is a well-known verification technique for reasoning about concurrent programs. However, for some algorithms, devising suitable rely and guarantee conditions is challenging, due to the strong interference exhibited in these algorithms. The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions. This paper investigates an approach for verifying the Ben-Ari algorithm, which enables reasoning to be performed in a more compositional manner in cases where compositional reasoning would not otherwise be possible. This is accomplished by reasoning that a given property holds for all instances of a particular variable and then instantiating the variable to the local variable required. As well as providing a reasoning approach which is more compositional, the result is the identification of the core property required of a component, thus enabling a deeper understanding about the reasons why the algorithm works correctly. This helps to reveal the reasons why the rely/guarantee approach does not work directly for some problems.

0.48