CS Paper Radar

Handling Complex Interference Compositionally: A Concurrent Garbage Collector Case Study

Nisansala P. Yatapanage

cs.LO ·submitted 2026-09-23 05:47 UTC · v2
top venuehot direction

Abstract

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.

Comment
To be published in the 12th International Symposium on Dependable Software Engineering Theories, Tools and Applications (SETTA 2026)

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.66
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.47

Non-Leaking Concurrent Objects

cs.DC ·2026-08-23 ·Hagit Attiya, Rotem Oshman, Noa Schiller, Corentin Travers
similarity 0.66
Abstract · Full version of the paper appearing in DISC 2026 (Best Paper Award)

Abstract specifications of concurrent objects determine which values operations may return, but they also implicitly constrain which information operations may know, for example the arguments of other operations that do not affect their outcome, or even whether such operations occurred. Concrete implementations, while correct with respect to the abstract specification, may nonetheless expose additional information through their internal coordination mechanisms. We introduce a framework for reasoning about information leakage in concurrent implementations. The framework uses epistemic logic to compare what a process may know under an abstract specification with what it may know in a concrete implementation, using the abstract object itself as the reference for permissible observations. This yields several notions of non-leaking implementations. Using this framework, we investigate both the possibilities and limitations of non-leaking implementations. We present fully-non-leaking wait-free implementations of multi-valued registers and bounded max registers, but show that a fully-non-leaking unbounded max register cannot be implemented in a wait-free manner from finite-state base objects. We then consider a weaker guarantee, obtaining argument-non-leaking implementations of stacks, queues, and approximate agreement. These results demonstrate that non-leakage guarantees are often compatible with correctness and progress requirements, while also indicating their limitations.

0.29

Blame-aware Recomposition for Secure Compilation Proofs of Low-Level Compartment Isolation

cs.PL cs.CR ·2026-10-19 ·Basile Schlosser, Jérémy Thibault, Catalin Hritcu
similarity 0.64
Abstract

The security guarantees of existing formally verified compilers for compartmentalized programs in unsafe languages like C stop at a rather high level, assuming a built-in protection mechanism and a block-based memory model. Verifying a concrete, low-level enforcement mechanism for compartment isolation is still a major challenge for current proof techniques. In particular, Abate et al.'s proof technique fails because one of their proof steps, recomposition, essentially requires hiding all information about the code of each compartment, which is not practically achievable at a low level. We propose an extension of their proof technique to a low-level setting where compartments can fully observe each other's code. To do so, we introduce an overlay semantics that allows us to characterize these observations as a form of undefined behaviour, and we use a novel variant of recomposition that we call blame-aware recomposition, which essentially allows recomposing executions as needed in the original high-level proof technique, even if the low-level context observes the code, because this context is ultimately going to be discarded. We apply this new proof to a compartment isolation mechanism that uses a programmable tag-based reference monitor.

0.26

Preserving Separation Logic Specifications through Compilation

cs.PL ·2026-10-27 ·Carmine Abate, Kleio Liotati, František Farka, Sebastian Ertel
similarity 0.64
Abstract · 42 pages (25 pages main text, references, 13 pages of appendices), 6 figures, 1 table. Rocq mechanization available from the authors on requ…

Program specifications in separation logic describe ownership of resources and serve as logical interfaces for local reasoning. Compiler correctness, expressed as semantics preservation, does not by itself supply such an interface for compiled code, because it does not explicitly relate source and target resources and assertions. We investigate WP-preserving compilation: when a compiler translates a source program, the weakest preconditions that the program satisfies in a separation logic carry over to the compiled program. Our proof technique consists of a resource-aware simulation over interaction trees: it relates the resources required by corresponding source and target events, and tracks ownership through target operations, such as register accesses, that have no source counterpart. We apply the approach to a compiler from a structured imperative language to an assembly-like language, first for closed programs and then extended with modules and function calls. In the extended setting, each module can be verified in the source logic and compiled separately; its specifications carry over to the compiled module and are preserved when compiled modules are linked. All results are mechanized in Rocq.

0.24

Towards a Deductive Verification Infrastructure for Weighted Programming

cs.PL ·2026-08-19 ·Emma Ahrens, Samuel Rode, Philipp Schröer, Joost-Pieter Katoen
theory similarity 0.63
Abstract

Weighted programs extend guarded commands with trace weights drawn from a semiring, or more generally a monoid-module. Varying this algebra gives one programmatic syntax for a variety of quantitative and symbolic models. Weakest-preweighting semantics provides a compositional basis for reasoning about those programs. We present a deductive verification framework based on a weighted assertion language and an intermediate verification language. Its weight domains are ordered structures with implication and coimplication, which let verification conditions express lower- and upper-bound obligations internally. We prove sound translations of core commands and reusable encodings for various proof rules applying to procedure calls and loops. To facilitate automation, we prove soundness of a quantifier elimination procedure for our assertion language. A prototype in the Caesar verifier checks case studies for probabilistic queueing costs, recursive database provenance with cyclic dependencies, clearance bounds for networks of arbitrary size, and formal-language reasoning about lock-freedom of a compare-and-swap counter.

0.24

A Quantitative Interpretation of Useful Call-by-Value

cs.LO ·2026-10-29 ·Pablo Barenbaum, Delia Kesner, Mariana Milicich
similarity 0.62
Abstract

In this work, we present the first semantic interpretation of useful call-by-value evaluation through a non-idempotent intersection type system called U. One first contribution of this paper is a characterisation of termination of useful call-by-value evaluation via U-typability. That is, a term is typable in system U if and only if it terminates in the useful call-by-value strategy. As a second contribution, we show that system U provides a quantitative interpretation for useful call-by-value evaluation, offering exact step-count information for program evaluation. Even though the specification of the operational semantics of useful evaluation is highly complex, system U is notably simple. As far as we know, system U is one of the scarce quantitative type systems capturing exactly the substitution step-count for variables and abstractions in an open call-by-value strategy. Our third contribution is a termination-equivalence result between standard call-by-value, which may perform erasing reductions, and useful call-by-value, which is non-erasing. To establish this result, we introduce a non-erasing restriction of standard call-by-value, a refinement that serves as an intermediate calculus bridging standard and useful call-by-value. We show that all three calculi have the same termination behaviour, and hence induce the same observational equivalence.

0.29

Automatically Detecting and Fixing Deadlocks in Go Code with GoDDaR

cs.PL cs.DCcs.SE ·2026-10-06 ·Gustavo Feio, Jorge Coelho, Miguel Flor, João M. Lourenço, António Ravara
benchmark similarity 0.60
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.

0.20

Fewer Assumptions by Design: A Reusable Skill for LLM-Assisted Verus Verification

cs.AI cs.PLcs.SE ·2026-09-28 ·Andrada-Livia Antoneac, Dorel Lucanu, Dragoş Teodor Gavriluţ
published similarity 0.60
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

LLM-assisted Verus verification is a less tedious method to verify Rust implementations, but paired with self-referential structures, e.g., Doubly Linked Lists (DLLs)—notoriously difficult to formalise for verification—it becomes a substantially more demanding verification task. Moreover, a specification weakness can arise when verification relies on unproven or invalidated assumptions, such as axiomatic lemmas and assume statements. We investigate whether LLM agents can synthesize strong DLL specifications while minimizing these trusted base. The analysis follows three different approaches: manual verification, property-specific verification, and a defined skill for the specific case of DLLs and certain properties of this type of data structure. The skill encodes domain knowledge and a task-decomposition strategy. We show that an LLM agent equipped with a carefully designed verification skill can generate strong, low-trust specifications for DLLs in Verus.

0.29