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

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.


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.
| Model | As submitted | Corrected | Change |
|---|---|---|---|
| PSO | 1,170 / 1,226 | 1,173 / 1,223 | 3 forbidden → allowed |
| RA | 2,089 / 307 | 2,092 / 304 | 3 forbidden → allowed |
| WEAKEST | 2,356 / 40 | 2,359 / 37 | 3 forbidden → allowed |
| RC11 | 2,169 / 227 | 2,172 / 224 | 3 forbidden → allowed |
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.

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