Skip to content
VVS

WEV-SMT

A checker that asks whether a small concurrent program can produce a given outcome under six weak memory models, and that asks Z3 whether a dependency is real before letting it forbid anything. The core theory is machine-checked in Isabelle/HOL.

Role
Design, implementation, proofs; TACAS paper co-authored with my supervisor
Timeline
Jan 2026 to Nov 2026
Status
Two manuscripts under review: TACAS 2027, FSEN 2027
Stack
Java 21, JavaSMT, Z3, Isabelle/HOL, Python, JUnit 5
01

Values out of thin air

Modern CPUs and compilers reorder memory operations. A memory model says which reorderings a program may observe. Make the model too strict and it forbids optimisations real hardware performs; too weak and it allows a value to appear “out of thin air”, justified only by a circular argument in which a load reads a value that a later store wrote because of that very load.

WEAKEST forbids those cycles only when they go through a real dependency. The hard part is the word “real”. In x = r + 1 the stored value depends on r. In x = r ^ r ^ 1 it mentions r but is always 1. A checker that reads syntax treats them the same. WEV-SMT asks a 32-bit bitvector solver whether the stored value can change when the loaded value changes, and keeps only the dependencies that can.

02

Explore executions

Each graph is one candidate execution for a classic litmus test. Choose a model to see its verdict. When a model forbids the outcome, the edges that form the forbidden cycle are highlighted. Hover an event to isolate its edges, and switch relations on and off underneath. Compare LB-fake with LB-real: the shape is identical, only the classification of the dependency edges changes.

Litmus test

Memory model

LB with a fake dependency

outcome: r0 = 1 and r1 = 1

Swipe sideways to see the whole diagram.

thread 1thread 2popofakefakerfrfR y = 1W x = r0^r0^1R x = 1W y = r1^r1^1

Program

T1

r0 = y

x = r0 ^ r0 ^ 1

T2

r1 = x

y = r1 ^ r1 ^ 1

The paper example. Each store mentions the loaded register, but r ^ r ^ 1 is always 1. Is the dependency real?

WEAKESTallowed

The Z3 constancy oracle shows each stored value is 1 whatever the load returns, so both edges are classified fake and left out of sdep. acyclic(sdep ∪ rf) has nothing to reject.

LB-fake-xor-cycle   SC=F TSO=F PSO=F RA=A WEAKEST=A RC11=F | edges DATA:fake DATA:fake
Verdicts: LbProbe, corrected-v1 build, 14 Nov 2026Tool output

Verdicts are copied from the tool's own output: the atlas run for the classic shapes (it has no RC11 column for LB and 2+2W) and LbProbe for the dependency pair. The explanations and the highlighted cycles are my reading of why each verdict holds.

03

How it works

A litmus file goes through a parser for five dialects (x86, PowerPC, ARM, RISC-V and C), then the checker enumerates candidate executions that can produce the asked-for outcome. For every syntactic dependency, the constancy oracle asks Z3 a QF_BV question: is there any pair of loaded values for which the stored value differs? If not, the edge is fake. Each model's consistency axioms are then encoded as SMT constraints over the surviving relations.

Litmus file

x86, PPC, ARM, RISC-V, C

Parser

threads, events, outcome

Candidate executions

rf and co choices

Constancy oracle

Z3, QF_BV, 32-bit

Model encoding

SC to RC11 axioms

Z3

sat or unsat

Verdict

allowed, with a witness

fake edges removed hereonce per model
Fig. 1One query from litmus file to verdict. The dependency step is what separates WEAKEST from a syntax-based check.Illustrative· pipeline
Terminal output of LbProbe on LB-real and LB-fake-xor-cycle
LbProbe on the two load-buffering programs from the paper. LB-real is unreachable once its dependencies are honoured; for LB-fake-xor-cycle both edges are classified fake, and WEAKEST and RA allow the outcome.Tool output· terminal capture
04

Proved, tested, not proved

Formal methods projects are easy to oversell, so the repository separates three kinds of claim, and so does this page.

Proved in Isabelle/HOL
Machine-checked· four sessions, no sorry, no oraclesThe dependency detector never drops a semantic dependency; it is exact on branch-free code; and WEAKEST consistency rules out thin-air cycles. These hold relative to stated assumptions about the oracle, and a further theory shows those assumptions hold for the concrete 32-bit expression semantics. The FSEN results on composed summaries are mechanised too.
Tested
Tool output· mvn test, AtlasReconstruct135 JUnit tests covering the parser, encoder, axioms, edge cases and the F-01 counterexample, plus 5 corpus regressions that need the base artifact (140 in total). The model atlas compares six models against expected verdicts on classic shapes: 190 cells, 190 matches. A separate Python reference checker agrees on 44 of 44 dependency pairs, though it shares Z3, so that is support rather than proof.
Not proved
The Java code is not verified, and nothing links the Isabelle definitions to the encoder mechanically. Z3 is trusted: a “constant” verdict is only as good as its unsat answer. The theorems cover data dependencies in branch-free straight-line code; address and most control dependencies are outside them.
Isabelle build output for four sessions
Clean build of the four Isabelle sessions, followed by the oracle and ancestry checks.Tool output· capture
Maven test summary per test class
mvn test per test class. The corpus regressions are excluded here; with the base artifact they pass too.Tool output· capture
05

A defect I found after submitting

After the TACAS submission I found that the encoder's well-formedness constraints rejected some candidate executions that no model forbids (finding F-01). Over the corpus, 12 of 14,376 verdicts were wrong: three files, each under four models, all reported forbidden where allowed is correct. I fixed the encoder and the witness extractor, added a minimal counterexample as a test, and published a correction notice with the corrected totals rather than quietly replacing them.

Corpus verdicts, allowed / forbidden, from the artifact's correction notice
ModelAs submittedCorrectedChange
PSO1,170 / 1,2261,173 / 1,2233 forbidden → allowed
RA2,089 / 3072,092 / 3043 forbidden → allowed
WEAKEST2,356 / 402,359 / 373 forbidden → allowed
RC112,169 / 2272,172 / 2243 forbidden → allowed
Tool output· CORRECTION-NOTICE.md, corrected-v1 artifact
06

Where it started

WEV-SMT grew out of my MSc dissertation, a JavaFX tool for stepping through executions under WEAKEST and comparing them across models, evaluated with a nine-person user study and graded Exceptional. Its event structure classes are still the library WEV-SMT builds on.

The visualiser's own consistency checks were written for teaching and have known bugs, which is one reason the SMT checker exists. I show it here as a design artifact, not as a source of verdicts.

WEAKEST Execution Visualiser showing the execution graph of message passing
The dissertation visualiser on the message passing test, showing an execution graph with program order, reads-from and coherence edges.Tool output· screenshot
07

Decisions and trade-offs

SMT over enumeration
Encoding consistency as constraints lets Z3 search candidate executions instead of enumerating them, and the same solver answers the dependency question. The cost is trusting Z3.
32-bit bitvectors
Fixed-width semantics match what hardware computes, so overflow and xor cancellations behave as they really would. Wider types and floats are out of scope.
Branch-free first
The theorems are clean for straight-line code. Control dependencies are kept conservatively by the front end rather than analysed, which can over-forbid but never under-forbid.
Exclude, do not patch
Known front-end defects are excluded from the corpus with a stated reason, so every reported verdict comes from a path I trust.
08

Lessons

Separating “proved”, “tested” and “assumed” in the README changed how I wrote the papers. It made the gaps visible, and the F-01 fix came from looking hard at one of them.

The FSEN paper ends with a negative empirical result: across 2,250 litmus tests and eight upstream concurrency code bases, the composed cancellations the theory handles never appeared in a store's data dependencies. I reported it as the finding it is.