DEV Community

Cover image for Fitting a model checker into one million compiler steps
Edy Cu
Edy Cu

Posted on

Fitting a model checker into one million compiler steps

An escrow contract has five actions: Deposit, Lock, Release, Refund, Dispute. Unit tests check the sequences somebody thought of. The bug that drains it is usually the sequence nobody wrote a test for.

So I made the compiler try all of them. In exhaust, fe build runs a breadth-first search over every reachable state of the escrow's state machine, checks five invariants on every state and every transition, and refuses to compile if one breaks. The search has to finish inside a hard wall: Fe 26.6.0 gives each static_assert 1,000,000 evaluator steps and a recursion limit of 64. This post is about fitting a model checker under that ceiling.

Repo: https://github.com/edycutjong/exhaust · 86-second demo: https://youtu.be/xmKGKjVZAwA · page: https://exhaust.edycu.dev/

What it looks like when it works

Remove one condition from the Refund guard:

-                    if s.escrow > 0 && s.seller == 0 {
+                    if s.escrow > 0 {
Enter fullscreen mode Exit fullscreen mode

and run fe build again:

error[3-0036]: assertion failed in const context
= assertion message: invariant 'paid once' broken: buyer and seller both paid
error[8-0081]: static assertion failed
= left: `11234`
Enter fullscreen mode Exit fullscreen mode

The build names the broken invariant, and a second search prints the shortest attack as digits: 11234 = Deposit, Deposit, Lock, Release, Refund. The seller is paid, then the buyer is refunded too. Replaying those five calls on the EVM, the patched contract accepts all five; the real one refuses the Refund.

The search is an ordinary const fn

No plugin, no macro, no external tool. A state (phase, units in escrow, units paid to the seller, units refunded to the buyer) is packed into a u32 by a mixed-radix encode, so a plain bool array is the visited set and a u32 array is the queue:

pub const fn explore_seeds(_ first: u32, _ count: u32, _ stride: u32, _ cap: u32) -> usize {
    var visited: [bool; SIZE] = [false; SIZE]
    var queue: [u32; SIZE] = [0; SIZE]
    var head: usize = 0
    var tail: usize = 0
    // ... enqueue the seeds ...
    while head < tail {
        let x = queue[head]
        head += 1
        let cur = decode(x)
        var a: u32 = 0
        while a < ACTIONS {
            let act = action_of(a)
            let n = step(cur, act, cap)
            if n.ok {
                let v = first_violation(cur, act, n.s, cap)
                if v != OK { require(v) }
                let y = encode(n.s)
                if !visited[y as usize] {
                    visited[y as usize] = true
                    queue[tail] = y
                    tail += 1
                }
            }
            a += 1
        }
    }
    tail
}
Enter fullscreen mode Exit fullscreen mode

(Fe's syntax is close enough to Rust that the highlighter copes.) require is a chain of assert!s, one per invariant, so the compile error carries the invariant's name. And the pin that runs it:

static_assert(explore(CAP) == STATES)   // CAP = 21, STATES = 736
Enter fullscreen mode Exit fullscreen mode

The step function the search calls is the same one the deployed contract's recv handlers call, and the same one fe test runs on the EVM (Sonatina backend) and natively. One function, three executions.

The wall: 1,000,000 steps

The budget lives in the compiler's const evaluator (crates/hir/src/analysis/semantic/ctfe/machine.rs at v26.6.0) and has no CLI or config override. Everything about the design follows from it.

Measuring a budget you can't read. The evaluator doesn't report steps used. So I measured indirectly: a burn loop alone fits 43,476 iterations (about 23 steps each); running a search in the same assert shrinks the headroom, and the difference converts to steps. Resolution is one burn iteration, about 23 steps. From evidence/budget.md:

Search States Steps used Share
explore(0) 1 86,323 8.6%
explore(17) 494 658,271 65.8%
explore(CAP), C = 21 736 940,335 94.0%
counterexample(19) 609 908,455 90.8%
counterexample(20) 671 983,899 98.4%

Three things fell out of that table.

1. Setup is not free. explore(0) visits one state and still costs 86,323 steps, because initialising an array costs about one step per element and the box holds 42,592 encodings. Two tables are 8.6% of the budget before the first state is popped. The encoding is a bijection onto 0..SIZE with SIZE = 4 × 22³, and C = 21 is the largest capacity it holds, so the box can't shrink without shrinking the model.

2. Consts share a budget, asserts don't. A const that references another const is evaluated in the same budget. A separate static_assert gets a fresh million. So every search is its own assert, and the reachable set is also split into shards that each get their own budget: after Lock the total never changes, so the states reachable from (Locked, k, 0, 0) all have total k and shards with different k can't overlap:

static_assert(explore_seeds(LOCKED_BASE + LOCKED_STRIDE, 7, LOCKED_STRIDE, CAP) == 91)
static_assert(explore_seeds(LOCKED_BASE + 8 * LOCKED_STRIDE, 7, LOCKED_STRIDE, CAP) == 238)
static_assert(explore_seeds(LOCKED_BASE + 15 * LOCKED_STRIDE, 7, LOCKED_STRIDE, CAP) == 385)
Enter fullscreen mode Exit fullscreen mode

91 + 238 + 385 plus the 22 Open states is 736. A runtime test checks that sum on both backends, and the independent Python model checks that the shards are disjoint and cover the set.

3. The attack printer runs at a smaller capacity. Printing a trace needs parent pointers and the action that reached each state: four tables instead of two, and more work per state. At C = 21 it doesn't fit. C = 20 fits with 1.6% to spare, which is too close: one conformance check adds two branches to step() and pushes it over. So the printer is pinned at C′ = 19, which leaves room for edits. The trace itself is walked back from the violating edge and accumulated as base-10 digits in a u256, with an assert that stops before 77 digits would overflow.

The recursion limit of 64 is why everything is a while loop. A recursive DFS would hit it long before the step budget.

Why trust the model matches the contract

A model checker that checks the wrong model proves nothing, so three independent things tie them together:

  • the contract's recv handlers are thin adapters: load storage into State, call the same step(), store the result;
  • an exhaustive-edge test replays every reachable transition through the deployed contract (966 accepted edges, 3,680 attempts) and compares the result and the encoded state;
  • tools/ref_model.py, a stdlib-only Python model written separately, agrees with all 15 pins (8 escrow, 7 vault).

A second protocol, a 2-of-3 approval vault with a timelock (211 states, 10 invariants including a transition invariant), uses the same pattern. Nine planted bug patches each have to fail fe build by name, and a CI job fails if any of them builds.

What this does not prove

Bounded-exhaustive, not formal verification. Only the stated capacities are explored (C = 21 for the count, C′ = 19 for the trace). No liveness. The escrow model has no caller identity, so msg.sender authorization is out of scope, and units are abstract counters, so value transfer, reentrancy and gas are too. The model, the Fe code and the oracle share one author, which is why the oracle exists, but it is not a second team. Everything is measured on Fe 26.6.0; 26.7.0 has the same budget in its source and wasn't re-measured.

Try it

git clone https://github.com/edycutjong/exhaust && cd exhaust
# install Fe 26.6.0 as in the README, then:
demo/run.sh          # green build, one-line patch, red build naming 'paid once' with 11234
demo/check-bugs.sh   # every planted bug must fail the build by name
Enter fullscreen mode Exit fullscreen mode

Every number above has a command next to it in DEMO.md. Built for the Fe Builders Challenge 2026. If you write Fe, the pattern (a const fn search, static_assert pins, one asserted search per budget) is the part worth copying.

Top comments (0)