💻 computer science

Deductive Verification of Weak Memory Programs with View-based Protocols (extended version)

This paper introduces VerCors-relaxed, an extension of the VerCors deductive verification tool that encodes weak memory concurrency using view-based protocols and permission-based separation logics to enable the automated verification of concurrent programs that were previously limited to manual proofs.

Original authors: Ömer Şakar, Soham Chakraborty, Marieke Huisman, Anton Wijs

Published 2026-04-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ömer Şakar, Soham Chakraborty, Marieke Huisman, Anton Wijs

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Chaotic Kitchen" Problem

Imagine a busy kitchen with several chefs (threads) working together to cook a meal (the program). In a perfectly organized kitchen (Sequential Consistency), there is one head chef who dictates exactly when every chef moves. Chef A stirs the pot, then Chef B chops onions, then Chef A adds salt. Everyone sees the same order of events. It's easy to predict the result.

However, modern computer processors are like chaotic kitchens where the head chef has gone on vacation. To make things faster, the chefs are allowed to:

Reorder tasks: Chef A might add salt before stirring the pot if they think it saves a step.
Delay updates: Chef B might chop onions but wait to put them in the bowl until later.
See different things: Chef A might see the salt added, while Chef B still sees the pot empty because the update hasn't "arrived" in their view of the kitchen yet.

This is called Weak Memory. It makes computers fast, but it makes it incredibly hard to prove the meal will turn out right. Sometimes, the chaos leads to a disaster (a bug) that you can't explain by just looking at the order of instructions.

The Problem: Manual Proof is Too Hard

Computer scientists have created "rulebooks" (logics like SLR) to prove that even in this chaotic kitchen, the meal will be safe. But these rulebooks are like complex legal contracts. To use them, you have to manually write out every single possible scenario where a chef might get confused. It's slow, tedious, and prone to human error.

The Solution: "View-Based Protocols" and the "Magic Clipboard"

The authors of this paper built a new tool called VerCors-relaxed. Think of this tool as a super-smart, automated kitchen inspector.

Instead of trying to predict every chaotic move manually, they introduced a concept called View-Based Protocols. Here is how it works using an analogy:

1. The Protocol (The Recipe Card)

Imagine every chef has a specific Recipe Card for every ingredient they touch.

If Chef A is supposed to write "2" to a variable, their card shows a path: Start → Write 1 → Write 2.
If Chef B is supposed to write "1", their card shows: Start → Write 1.
These cards are strict. You can't jump from "Start" to "Write 2" without passing through "Write 1" first. This is the Protocol.

2. The View (The Chef's Glasses)

Every chef wears a pair of special glasses (a Thread-Local View).

These glasses show the chef what they have done so far.
Crucially, the glasses also show a prediction of what the other chefs might have done.
If Chef A looks through their glasses, they might see: "I wrote 2. I think Chef B might have written 1, or maybe they haven't started yet."

3. The Verification (The Inspector's Check)

The VerCors tool acts as the inspector. It doesn't watch the chefs move in real-time. Instead, it simulates the whole kitchen using these cards and glasses.

It asks: "If Chef A looks at the pot, what values could they see based on their glasses and the other chefs' cards?"
It checks if the chefs are following the rules of the Recipe Cards.
It ensures that if a chef sees a value, that value was actually written by someone (no "ghost ingredients").

The Magic Trick: Speculation

The coolest part of this paper is how it handles speculation.

In a chaotic kitchen, Chef A might guess, "Chef B is probably going to write '2' next, so I'll start preparing for that." In old systems, this guess was dangerous. If Chef B actually wrote '1', the whole meal was ruined.

With View-Based Protocols, the tool allows the chefs to make these guesses safely, as long as they can prove later that the guess was valid.

The Analogy: It's like a game of "Telephone." Chef A whispers a guess to the Inspector. The Inspector checks the other chefs' cards. If the cards say "Chef B can write '2' at this stage," the Inspector says, "Okay, your guess is valid." If the cards say "Chef B can only write '1'," the Inspector says, "Stop! That guess is impossible. Throw out that execution."

What Did They Actually Do?

Translated the Theory: They took a very complex mathematical logic (SLR) and translated it into a language the VerCors tool understands.
Built the Encoder: They created a system where you can describe these "Recipe Cards" (protocols) and "Glasses" (views) in code.
Automated the Proof: They tested this on 13 different examples from computer science textbooks (like the famous "2+2W" and "COH" examples).
- Result: The tool automatically proved whether the chaotic kitchen scenarios were safe or broken, usually in less than 2 minutes.

Why Does This Matter?

Safety: It helps software engineers write code for multi-core processors (like your phone or laptop) without worrying that the processor's speed optimizations will cause hidden bugs.
Automation: Before this, proving these programs were safe required a PhD-level mathematician spending weeks on a manual proof. Now, a computer can do it in seconds.
Accessibility: It bridges the gap between high-level theory and practical tools, making it easier to build reliable software for the future.

Summary

The paper introduces a way to automatically check if programs running on fast, chaotic computers will behave correctly. They do this by giving every part of the program a strict "rulebook" (Protocol) and a "view" of what others are doing. The tool then simulates all possible chaotic scenarios to ensure that even if the chefs reorder their tasks, the final meal is always perfect.

1. Problem Statement

Reasoning about concurrent programs under weak memory models (e.g., C11/C++11 relaxed ordering) is significantly more difficult than under Sequential Consistency (SC).

The Challenge: Weak memory models allow program executions that cannot be explained by simple thread interleaving. This leads to unexpected outcomes (e.g., a thread reading a value written by another thread out of order) and makes manual verification error-prone.
The Gap: While several program logics (e.g., RSL, GPS, FSL, SLR) have been developed to reason about weak memory, their usage is currently limited to intricate manual proofs. Conversely, automated deductive verification tools like VerCors are powerful for SC programs but lack native support for weak memory semantics.
Goal: The authors aim to bridge this gap by enabling automated, modular deductive verification of weak memory programs using the VerCors tool.

2. Methodology: View-Based Protocols

The core contribution is a novel encoding approach called VerCors-relaxed, which integrates view-based protocols into VerCors' existing Permission-Based Separation Logic (PBSL).

A. Core Concepts

Per-Thread-Location Protocols:
- Unlike previous approaches (like GPS) that define a single protocol per memory location for the whole program, this approach defines a protocol $P^t_x$ for every thread $t$ and atomic location $x$ .
- A protocol is a finite state machine (tree) modeling the sequence of values a specific thread can write to a specific location.
- States in the protocol represent specific write operations; transitions represent the order of writes.
Thread-Local Views ( $L^t_x$ ):
- Each thread maintains a "view" of the global state. Specifically, for every location $x$ , a thread $t$ holds a mapping $L^t_x: T \to S \cup \{\bot\}$ .
- This view tracks the current state of its own protocol (its own writes) and the speculated states of other threads' protocols (what it believes other threads might have written).
- This mechanism allows the system to reason about speculative writes (reading a value before it is strictly confirmed by the global order).
Operational Semantics (SOS Rules):
- The system uses Structural Operational Semantics (SOS) rules to define how Load and Store operations update the thread-local views and a global modification order ( $\tau$ ).
- Write Rule: When a thread writes, it advances its own protocol state. The global modification order is updated to reflect the new write.
- Read Rule: A thread can read a value $v$ from location $x$ if the state corresponding to $v$ is reachable in the protocol of the writing thread and respects the coherence constraints (specifically, it cannot read a value that was "overwritten" in the modification order relative to its current view).

B. Encoding in VerCors

The authors encode these concepts into VerCors using:

Axiomatic Data Types (ADTs): Protocols (states, transitions, values) are modeled as abstract data types.
Ghost Variables: To track the state of views ( $L$ ), the most recent observed store ( $\pi$ ), and the modification order ( $\tau$ ) without affecting runtime performance.
Contracts: Load and Store methods are equipped with pre/postconditions that enforce the SOS rules. For example, a load contract ensures that the returned value corresponds to a state reachable from the current view, respecting the modification order.

3. Key Contributions

VerCors-relaxed: An extension of the VerCors deductive verifier that supports weak memory concurrency via the encoding of view-based protocols.
Novel Protocol Structure: The introduction of per-thread protocols combined with thread-local views. This differs from prior work by allowing more granular reasoning about speculative writes and coherence per thread.
SLR Encoding: The authors successfully encode the relaxed fragment of the SLR (Separation Logic for Relaxed memory) logic into VerCors-relaxed. They prove the soundness of their approach: if a program verifies under their view-based protocol encoding, it is valid under the SLR logic.
Automation: The approach enables fully automated verification of weak memory examples, moving away from manual proof construction.

4. Results and Evaluation

The authors evaluated the approach on 13 examples from the literature, including standard weak memory litmus tests (e.g., 2+2W, COH, LB, SB, ARM-weak) and variations.

Correctness: The tool successfully verified consistent executions (allowed by the memory model) and rejected inconsistent executions (e.g., those violating SC-per-location or coherence).
Performance:
- Verification times were reasonable, averaging between 48 and 91 seconds per example.
- The examples involved 2 to 9 relaxed load/store operations.
- The encoding size was manageable (e.g., ~100 lines for protocol definitions for 4 states), though it grows exponentially with the number of states due to the need to define distinctness axioms.
Robustness: The system correctly identified incorrect protocols (e.g., missing transitions or wrong values) in test cases like COH-p1 and COH-p2, demonstrating that the protocol is strictly checked against the program behavior.

5. Significance

Bridging Theory and Practice: This work is significant because it translates complex, theoretical separation logics (like SLR) into a practical, automated verification toolchain.
Modularity: Unlike model checking (which often requires exploring the entire state space and struggles with scalability), this deductive approach allows for modular verification. Threads can be verified one by one, considering their instructions in SC order while using the protocols to reason about the weak memory effects.
Speculative Reasoning: The ability to formally reason about speculative writes (where a thread reads a value it expects another thread to write, before that write is globally ordered) is a major advancement in automated weak memory verification.
Future Impact: By demonstrating that weak memory verification can be automated in a tool like VerCors, this work paves the way for verifying real-world concurrent software (e.g., lock-free data structures) that relies on relaxed memory ordering for performance.

Conclusion

The paper presents a successful framework for the automated deductive verification of weak memory programs. By introducing view-based protocols and encoding them into VerCors, the authors provide a method to verify complex concurrency patterns that were previously only manageable via manual, error-prone proofs. The approach is sound with respect to the SLR logic and has been validated on a suite of standard weak memory benchmarks.