FerrousPath

Level 5 · Research· Lesson 6 of 9 · 50 min

RustBelt: proving unsafe code sound

Semantic type soundness, separation logic and Iris, the lifetime logic, and how the standard library's unsafe abstractions were machine-verified.

Rust’s central promise is conditional: safe code cannot cause undefined behaviour, provided the unsafe code in the libraries it uses is correct. RustBelt (Jung, Jourdan, Krebbers and Dreyer, POPL 2018) is the work that first turned that promise into a theorem with a machine-checked proof — and gave a precise meaning to “correct” for unsafe code.

The shape of the problem

The classical route to type safety is syntactic (Wright and Felleisen): show that well-typed terms do not get stuck (progress) and that reduction preserves typing (preservation). That proves safety for every program the typing rules accept.

But Vec::push contains raw pointer writes; Cell::set mutates through a shared reference; Mutex::lock hands out &mut T from &Mutex<T>. None of these is typable by the rules for safe code. A syntactic proof must either ignore the standard library or add each such library to the language as a primitive with its own axioms — and then says nothing about the next library someone writes.

What we want is an extensible theorem:

If every unsafe-using library satisfies a verification condition, then any program composed of those libraries and arbitrary safe code is safe.

That requires saying what it means for code to be safe independently of how it was typed.

Semantic typing

The semantic approach (logical relations, in the tradition of Milner, Tait, Girard, Appel and McAllester, Ahmed) interprets each type as a predicate on behaviour:

  • The syntactic judgement Γ ⊢ e : τ means “e can be derived by the typing rules”.
  • The semantic judgement Γ ⊨ e : τ means “e, run in any environment satisfying the interpretation of Γ, is safe and yields something satisfying the interpretation of τ”.

The proof has three parts:

  1. Fundamental theorem. Every syntactic typing rule is sound for the semantic interpretation: Γ ⊢ e : τ implies Γ ⊨ e : τ. Proved once, for the language.
  2. Library proofs. For each unsafe library, prove directly that each function semantically inhabits its type. Proved once per library.
  3. Adequacy. ⊨ e : τ implies e never gets stuck.

Compose them: a program is safe code (covered by 1) calling libraries (covered by 2), so it is semantically well typed, so it is safe (3). A new unsafe library needs only a new proof of kind 2.

The whole difficulty moves into one question: what is the interpretation of a Rust type? It must capture ownership, borrowing, lifetimes, interior mutability and concurrency. Ordinary logic is not up to it.

Separation logic

Separation logic (Reynolds; O’Hearn; Ishtiaq and O’Hearn, around 2001–2002) is Hoare logic with assertions about ownership of heap fragments:

  • ℓ ↦ v — “I own location ℓ, and it contains v”. Ownership is exclusive.
  • P * Q — separating conjunction: the resources can be split into two disjoint parts satisfying P and Q.
  • P -* Q — the magic wand: given resources satisfying P in addition, I can produce Q.
  • The frame rule: if {P} c {Q} then {P * R} c {Q * R}. Code that does not mention R cannot affect it — local reasoning.

Assertions are resources: they cannot be freely duplicated, and using one consumes it. This is an affine logic, and the fit with Rust is immediate:

Rust Separation logic
Owning a Box<T> at ℓ ℓ ↦ v * ⟦T⟧(v)
Moving a value Transferring the assertion
Two disjoint &mut P * Q
A function taking &mut T cannot affect other data The frame rule

Concurrent separation logic (O’Hearn; Brookes, 2004) extends this to threads: disjoint resources go to different threads; shared resources are governed by invariants.

Iris

RustBelt is built in Iris (Jung, Krebbers, Jourdan, Bizjak, Birkedal, Dreyer and others), a higher-order concurrent separation logic framework mechanised in Rocq (formerly Coq). The features that matter here:

  • User-defined ghost state from resource algebras (partial commutative monoids): invent whatever logical bookkeeping the proof needs — fractional permissions, tokens, counters, authoritative/fragment pairs — and Iris provides sound rules for it.
  • Invariants [P]: an assertion that holds at every step of execution, and can be opened by any thread for the duration of one atomic step.
  • Higher-order and impredicative: invariants may mention invariants and stored code. This requires step-indexing, visible as the later modality ▷.
  • Persistent assertions (□ P): duplicable knowledge, as opposed to exclusive resources. Copy types and shared references are interpreted with them.
  • A proof mode in Rocq that makes interactive separation-logic proofs practical.

λRust

The formal language is λRust, a core calculus resembling MIR in continuation-passing style: explicit memory with pointer arithmetic, explicit lifetime begin and end, and data-race detection built into the operational semantics (a race makes the program stuck, so “not stuck” implies “data-race free”). Its type system has ownership, both kinds of reference, lifetime inclusion, and recursive and sum types. Translating surface Rust to λRust is done by hand and is outside the mechanised proof.

The interpretation of types

Every type τ is interpreted by two predicates:

  • an ownership predicate ⟦τ⟧.own(tid, v̄) — what it means for thread tid to own a value of type τ represented by the bytes v̄;
  • a sharing predicate ⟦τ⟧.shr(κ, tid, ℓ) — what it means to hold a shared reference to a τ at location ℓ for lifetime κ.

For plain types the sharing predicate is derived from the ownership predicate (“the location holds, read-only, something satisfying own”). The second predicate exists because of interior mutability: what a shared reference to a Cell<T> lets you do is not determined by what owning a Cell<T> means. Each type gets to choose its own sharing protocol:

Type Sharing predicate, informally
i32, Box<T> Read-only access to memory containing an owned value, for κ
Cell<T> A non-atomic invariant, tied to thread tid, granting full ownership to whoever opens it — hence Cell is not Sync
Mutex<T> An atomic invariant: either the lock flag is set, or the flag is clear and the invariant holds the borrow of the content
RefCell<T> An invariant holding the borrow counter and ghost state linking it to outstanding Ref/RefMut tokens
Rc<T> Ghost state tracking the strong and weak counts, thread-bound

Send and Sync have crisp semantic definitions: τ is Send if own does not depend on the thread identifier; τ is Sync if shr does not.

The lifetime logic

The technical heart of RustBelt is a new piece of separation logic for borrowing. Its key connectives:

  • [κ]_q — a lifetime token: fraction q of the knowledge that lifetime κ is still alive. Tokens split and merge like fractional permissions.
  • [†κ] — the persistent fact that κ has ended.
  • &κ P — a full borrow: ownership of P for the duration of κ.

and its key rules, informally:

Borrowing:   ▷P   ⇛   &κ P  *  ([†κ] ⇛ ▷P)
             split P into a borrow, and an "inheritance" that returns P once κ has ended

Accessing:   &κ P * [κ]_q   ⇛   ▷P  *  (▷P ⇛ &κ P * [κ]_q)
             with a live-ness token you may open the borrow; you must put P back to recover the token

Ending:      [κ]_1   ⇛   [†κ]
             ending a lifetime needs the WHOLE token — so nobody can be in the middle of an access

Read them against Rust: creating &'a mut x splits ownership of x into the reference (the borrow) and the owner’s right to get x back afterwards (the inheritance). Using the reference requires evidence that 'a is alive. A lifetime cannot end while any access is in progress, because ending needs every fraction of the token.

A &'a mut T is then interpreted as a full borrow of the ownership predicate of T; a &'a T as the sharing predicate at 'a. Lifetime inclusion κ ⊑ κ' is defined in the logic, and reborrowing, splitting a borrow of a pair into two borrows, and the like are derived as lemmas.

What was proven

The mechanised development proves the fundamental theorem for λRust’s type system and the soundness of semantic versions of core library types, including Cell, RefCell, Rc, Arc, Mutex, RwLock, mem::swap, thread::spawn, rayon::join and take_mut.

The effort was not merely confirmatory. It found a real bug: MutexGuard<'_, T> was Sync whenever T: Send, when it must require T: Sync — the semantic model made the mistake impossible to prove, and the standard library was fixed.

What it does not prove

Being exact about limits is part of doing research:

  • It is about λRust, not Rust: the translation is manual, and the trait system, unwinding, and many language features are not modelled.
  • The original memory model was sequentially consistent and had no aliasing model.
  • It proves safety (absence of undefined behaviour), not functional correctness.
  • It verifies the libraries as modelled in λRust, not their actual source.

Each limitation became a research programme:

Work Extends RustBelt with
RustBelt Meets Relaxed Memory (Dang, Jourdan, Kaiser, Dreyer, POPL 2020) A weak-memory model (ORC11); re-verified Arc under it and found that Arc::get_mut needed an Acquire rather than Relaxed load
Stacked Borrows (POPL 2020), Tree Borrows (PLDI 2025) Aliasing models, with proofs that optimisations are sound
GhostCell (Yanovski et al., ICFP 2021) A new safe API for shared mutation, designed together with its soundness proof
RustHornBelt (Matsushita et al., PLDI 2022) Functional correctness: types are interpreted with prophecy-based specifications, justifying RustHorn-style verification even for unsafe libraries
RefinedRust (Gäher et al., PLDI 2024) Foundational verification of real Rust source, safe and unsafe, with refinement types producing Rocq proofs
Aeneas, Creusot, Verus, Prusti Practical verifiers that lean on the ownership discipline — next lesson

Why this matters to a practitioner

RustBelt gives the vocabulary for reasoning about unsafe code that this course has used since Level 3:

  • A type’s safety invariant is its ownership predicate. Its behaviour behind & is its sharing predicate. When you design an unsafe abstraction, you are choosing these — usually implicitly. Writing them down, even informally, is the single most effective way to find soundness bugs.
  • “Sound” means: every public function semantically inhabits its signature. The check is modular, per library, and never requires knowing the clients.
  • The reason unsafe code must be judged together with its module is that private fields’ invariants are part of the ownership predicate, and any code that can touch them is part of the proof.

Reading list

  1. Jung, Jourdan, Krebbers, Dreyer, “RustBelt: Securing the Foundations of the Rust Programming Language” (POPL 2018).
  2. Jung, Jourdan, Krebbers, Dreyer, “Safe Systems Programming in Rust” (Communications of the ACM, 2021) — the accessible overview. Start here.
  3. Jung, Understanding and Evolving the Rust Programming Language (PhD thesis, 2020) — the complete account.
  4. Jung et al., “Iris from the ground up” (Journal of Functional Programming, 2018).
  5. Reynolds, “Separation Logic: A Logic for Shared Mutable Data Structures” (LICS 2002); O’Hearn, “Separation Logic” (CACM 2019).
  6. Birkedal and Bizjak, Lecture Notes on Iris — a course-style introduction.
  7. Ahmed, “Step-Indexed Syntactic Logical Relations for Recursive and Quantified Types” (ESOP 2006).
  8. The follow-up papers in the table above.

Exercises

  1. Write, in prose, the ownership predicate for Vec<T> in terms of a pointer, a length, a capacity, points-to assertions, and ⟦T⟧.own. Compare with the invariants listed in the Level 4 capstone.
  2. State the sharing predicate you would choose for a type AtomicCounter wrapping an AtomicU64. Is the type Sync by the semantic definition?
  3. Using the three lifetime-logic rules, explain step by step why this is accepted: create &mut x, write through it, let the lifetime end, read x.
  4. Explain semantically why Cell<T> is Send (when T is) but not Sync.
  5. Read section 2 of the CACM article and summarise the Mutex example in your own words.
  6. Work through the first chapters of the Iris lecture notes in Rocq and verify a counter with a Mutex-like lock.

Check your understanding

Pick an answer to see the explanation.

  1. 1.Why can a syntactic progress-and-preservation proof not establish Rust's safety claim?

  2. 2.In separation logic, what does P * Q assert?

  3. 3.What must a library author prove, in the RustBelt framework, to show an unsafe abstraction is sound?

Key terms in this lesson

Finished the lesson and the exercises?