FerrousPath

Level 5 · Research· Lesson 7 of 9 · 45 min

Formal verification of Rust programs

From Miri and model checking to deductive verifiers — Kani, Creusot, Prusti, Verus, Aeneas, Flux — and why ownership makes Rust unusually verifiable.

The type system proves memory safety. It does not prove that your sort sorts, that your parser never panics, or that your consensus protocol never loses data. Formal verification proves properties like these — for all inputs, not the ones a test happened to try. Rust has become one of the most active targets for verification research, and for a principled reason.

Why Rust is unusually verifiable

Verifying imperative programs is hard mostly because of aliasing. In C, after *p = 1; *q = 2; you cannot conclude *p == 1 without knowing that p and q differ. Every specification must say what a function does not modify (the frame problem), and verifiers need separation logic or dynamic frames to cope.

Safe Rust’s type system has already done this work. &mut T is unique; &T is immutable (interior mutability aside). So:

  • A function taking &mut a and &mut b cannot have them alias: no frame conditions needed.
  • A value behind &T cannot change while you hold the reference.
  • Ownership makes the heap a tree: an owned Vec<Box<T>> can be reasoned about as a mathematical sequence of values.

Several tools exploit this to translate safe Rust into pure functional verification conditions, with no heap model at all. The borrow checker serves as a free, automatic proof of the non-interference lemmas that dominate C verification.

The assurance spectrum

Technique Proves Effort Tools
Testing The cases you wrote low cargo test
Property testing, fuzzing Many random or coverage-guided cases low proptest, cargo fuzz
Dynamic UB detection No UB on executed paths low Miri, sanitizers
Concurrency model checking All interleavings of small tests low–medium loom, shuttle
Bounded model checking All inputs, within bounds medium Kani
Deductive verification All inputs, unbounded, against a specification high Creusot, Prusti, Verus, Flux
Translation to a proof assistant Anything you can prove interactively very high Aeneas, hax, RefinedRust

Move down only as far as the risk justifies. Most code deserves fuzzing; a cryptographic primitive or a kernel’s page-table code may deserve a proof.

Kani: bounded model checking

Kani (developed at AWS) compiles MIR to the input language of CBMC, a bit-precise model checker backed by SAT/SMT solvers. You write a proof harness resembling a test, but over nondeterministic inputs:

fn midpoint_buggy(a: u32, b: u32) -> u32 {
    (a + b) / 2 // overflows when a + b exceeds u32::MAX
}

fn midpoint(a: u32, b: u32) -> u32 {
    a / 2 + b / 2 + (a & b & 1)
}

#[cfg(kani)]
mod proofs {
    use super::*;

    #[kani::proof]
    fn midpoint_is_between() {
        let a: u32 = kani::any(); // every possible u32, symbolically
        let b: u32 = kani::any();
        let m = midpoint(a, b);
        assert!(m >= a.min(b) && m <= a.max(b));
    }

    #[kani::proof]
    fn buggy_version_fails() {
        let (a, b): (u32, u32) = (kani::any(), kani::any());
        let _ = midpoint_buggy(a, b); // Kani reports: arithmetic overflow, with a counterexample
    }
}

fn main() {
    println!("{} {}", midpoint(u32::MAX, u32::MAX - 2), midpoint(3, 4));
}

cargo kani checks, for all 2⁶⁴ input pairs: no panics, no overflow, no out-of-bounds access, no failed assertion — and, for unsafe code, a range of undefined behaviours. On failure it produces a concrete counterexample.

Strengths: almost no annotation burden; bit-precise; handles unsafe and raw pointers. Limits: loops and recursion are unwound to a bound (#[kani::unwind(n)]), so proofs about unbounded data need loop contracts or function contracts; solver time grows quickly with data size.

Kani is the main tool in the verify-rust-std effort, begun in 2024 by AWS with the Rust Foundation, to verify the safety of the standard library’s unsafe code through a set of open challenges.

Deductive verification

Deductive verifiers check code against contracts: preconditions (requires), postconditions (ensures), loop invariants, and termination measures (decreases / variants). The tool generates verification conditions and discharges them with SMT solvers.

Creusot

Creusot (Denis, Jourdan and Marché, ICFEM 2022) translates Rust to Why3 and its solvers. Specifications are written in Pearlite, a logic that looks like Rust:

// Creusot syntax — checked by `cargo creusot`, not by rustc alone.
#[requires(n@ <= 1000)]
#[ensures(result@ == n@ * (n@ + 1) / 2)]
pub fn sum_to(n: u32) -> u32 {
    let mut total = 0;
    let mut i = 0;
    #[invariant(i@ <= n@)]
    #[invariant(total@ == i@ * (i@ + 1) / 2)]
    while i < n {
        i += 1;
        total += i;
    }
    total
}

x@ denotes the logical model of x: an unbounded mathematical integer for a u32, a mathematical sequence for a Vec.

Creusot’s distinctive idea, from RustHorn (Matsushita, Tsukada and Kobayashi, ESOP 2020), is its treatment of mutable borrows by prophecy. A &mut T is modelled as a pair: its current value *x and its final value ^x — the value the referent will hold when the borrow ends. That final value is not known yet; it is prophesied.

#[ensures(^x == *x + 1)] // "the final value of the borrow is the initial value plus one"
pub fn increment(x: &mut i64) {
    *x += 1;
}

When a borrow is created, the lender is told “after the borrow ends, your value equals ^b”. When it expires, the prophecy is resolved. No heap, no separation logic — only first-order logic over values. Its soundness, including in the presence of unsafe libraries, was established by RustHornBelt on top of RustBelt.

Prusti

Prusti (Astrauskas, Müller, Poli and Summers, OOPSLA 2019), from ETH Zürich, translates Rust to the Viper verification infrastructure, which is based on implicit dynamic frames (a permission logic related to separation logic). Rust’s types are converted automatically into the permission annotations Viper needs — the user writes only functional specifications. Borrows that expire are modelled with pledges (after_expiry) rather than prophecies.

Verus

Verus (Lattuada et al., OOPSLA 2023) is an SMT-based verifier aimed at systems code, developed at CMU, VMware Research, Microsoft Research and others. Code is written in three modes inside a verus! macro:

  • exec — ordinary compiled Rust;
  • spec — pure mathematical functions used in specifications;
  • proof — lemmas: code that is checked and then erased.
// Verus syntax — checked by the `verus` tool.
verus! {

spec fn triangle(n: nat) -> nat
    decreases n
{
    if n == 0 { 0 } else { n + triangle((n - 1) as nat) }
}

fn sum_to(n: u32) -> (total: u32)
    requires triangle(n as nat) <= u32::MAX,
    ensures total == triangle(n as nat),
{
    let mut total: u32 = 0;
    let mut i: u32 = 0;
    while i < n
        invariant
            i <= n,
            total == triangle(i as nat),
            triangle(n as nat) <= u32::MAX,
        decreases n - i,
    {
        i = i + 1;
        assert(triangle(i as nat) <= triangle(n as nat)) by { triangle_monotonic(i as nat, n as nat); }
        total = total + i;
    }
    total
}

proof fn triangle_monotonic(a: nat, b: nat)
    requires a <= b,
    ensures triangle(a) <= triangle(b),
    decreases b,
{
    if a < b { triangle_monotonic(a, (b - 1) as nat); }
}

} // verus!

Verus’s notable move is to reuse Rust’s linear type checker on ghost code: tracked ghost values are owned, borrowed and moved like real ones, but erased at compile time. That gives the user a programmable separation logic — ghost permissions to memory (PointsTo), ghost tokens for concurrent protocols — checked by the borrow checker rather than by a separate logic. It is used to verify page tables, storage systems, memory allocators and distributed protocols.

Flux

Flux (Lehmann et al., PLDI 2023) adds refinement types to Rust — i32{v: v > 0}, Vec<T>[n] indexed by its length — with liquid inference of most annotations. It checks properties such as bounds safety with far less annotation than a full deductive verifier, by tying refinements to ownership: strong updates through &mut are sound because the reference is unique.

Translation to proof assistants

When SMT automation is not enough — deep mathematics, or a demand for a small trusted base — translate the program into a proof assistant.

Aeneas (Ho and Protzenko, ICFP 2022) translates safe Rust, via an intermediate language (LLBC) and a symbolic borrow-semantics, into a pure functional program in Lean, Rocq, F* or HOL4. A function taking &mut T becomes a function that returns the updated value; functions that return a mutable borrow produce a “backward function” describing how updates propagate to the lender. You then prove theorems about plain functional code. It is used in verified cryptography and is being applied to parts of real systems.

hax extracts a functional subset of Rust to F*, Rocq and ProVerif, primarily for cryptographic and protocol code.

RefinedRust (Gäher et al., PLDI 2024) produces foundational proofs in Rocq/Iris for both safe and unsafe Rust: the strongest guarantees, at the highest cost.

Choosing

If you need… Consider
“This unsafe function has no UB for any input up to size N” Kani
“This function never panics or overflows” Kani; Flux; Creusot/Verus with trivial postconditions
Functional correctness of algorithmic, mostly safe code Creusot, Prusti
Verified systems code with custom ghost state and concurrency Verus
Proofs that need a proof assistant; verified cryptography Aeneas, hax
Foundational proofs covering unsafe RefinedRust, RustBelt-style Iris proofs

All of these verify with respect to a specification. A wrong or weak specification yields a worthless proof; writing the specification is the real intellectual work, and often it is where the bugs are found.

Trusted base

Every result rests on things that were not themselves proven: the tool’s encoding of Rust semantics; the SMT solver; the specifications of unverified library functions the code calls; the compiler; and, for unsafe code, the unsettled details of Rust’s operational semantics. Be explicit about this list in anything you publish. A formal specification of Rust (next lesson) would shrink it.

Reading list

  1. Matsushita, Tsukada, Kobayashi, “RustHorn: CHC-based Verification for Rust Programs” (ESOP 2020).
  2. Denis, Jourdan, Marché, “Creusot: A Foundry for the Deductive Verification of Rust Programs” (ICFEM 2022).
  3. Astrauskas et al., “Leveraging Rust Types for Modular Specification and Verification” (OOPSLA 2019).
  4. Lattuada et al., “Verus: Verifying Rust Programs using Linear Ghost Types” (OOPSLA 2023).
  5. Ho and Protzenko, “Aeneas: Rust Verification by Functional Translation” (ICFP 2022).
  6. Lehmann et al., “Flux: Liquid Types for Rust” (PLDI 2023).
  7. VanHattum et al., “Verifying Dynamic Trait Objects in Rust” (ICSE-SEIP 2022) — Kani.
  8. Matsushita et al., “RustHornBelt” (PLDI 2022).
  9. The Kani, Verus and Creusot tutorials — all are hands-on and current.

Exercises

  1. Install Kani and verify midpoint. Then write a harness for a binary search over a [u32; 8] asserting that a found index holds the key.
  2. In Verus or Creusot, verify fn max(a: &[i32]) -> i32 with a postcondition stating both that the result is in the slice and that it is at least every element.
  3. Specify (do not yet prove) a sort function. Your postcondition needs two parts; most people forget one. Which?
  4. Using the prophecy model, write the specification of fn swap<T>(a: &mut T, b: &mut T).
  5. Take the MyVec from Level 4 and write Kani harnesses for push/pop sequences with a small bound. What invariant would you state as a function contract?
  6. Read the Aeneas paper’s treatment of fn choose<'a>(b: bool, x: &'a mut T, y: &'a mut T) -> &'a mut T and explain the backward function.

Check your understanding

Pick an answer to see the explanation.

  1. 1.Why is verifying safe Rust easier than verifying C?

  2. 2.What does a bounded model checker such as Kani establish?

  3. 3.What problem do prophecy variables solve in Creusot and RustHorn?

Key terms in this lesson

Finished the lesson and the exercises?