Formal verification

kernel/verify/ · Five verification instruments over the same mirrored kernel logic: symbolic execution (Kani), model checking (SPIN), concurrency-interleaving enumeration (loom), undefined-behavior detection (Miri), property testing (proptest) — each instrument's proof target, scale, cadence and captured defects · Canonical: kernel/verify/README.md, docs/architecture/security-design.md §3

§1The instrument map

InstrumentMethodProof targetScale (current tree)Cadence
make verifymirror-sync check + property tests + unit testskernel algorithms mirrored into the host crate1,184 #[test] fns (incl. proptest! blocks) + 1,584 in-kernel casesevery push
make kanisymbolic execution — asserts and panic reachability for ALL inputscore unsafe code and protocol invariants164 #[kani::proof] harnesses (34 files)nightly CI
make spinPromela model checking (state enumeration + LTL)lock ordering / futex wait-wake / interrupt-preempt / sched enqueue-dequeue4 models, all PASSnightly CI
loominterleaving enumeration under a preemption boundthe SleepMutex handoff state machine8 scenarios (5 clean + 3 planted must-catch)nightly CI
make miriinterpreted execution + UB detectionthe whole verify mirror cratewith the 1,184 testsnightly CI

All instruments run host-side with no kernel-image dependency: the proof targets are pure types and state machines mirrored from kernel/src into the verify crate. The instruments are complementary — proptest answers "correct on sampled inputs", Kani answers "correct on all inputs", SPIN/loom answer "no deadlock/lost wakeups under every interleaving", Miri answers "no undefined behavior".

§2Kani symbolic execution (164 harnesses)

  • Coverage distribution: arch 22, fs 19, mm 18, drivers 18, process 16, signal 14, net 14, interrupt 11, security 9, sched 9, ipc 5, sync 4, errno 5 (per module; 164 across 34 files).
  • Harness contract style: each harness mirrors pure types from kernel/src into verify (the source file cited verbatim in a comment), takes symbolic inputs with kani::any(), narrows preconditions with kani::assume, and asserts named invariants INV-<domain>-K<n>. Examples: INV-CAP-K1 (capability mask valid at 41 bits), INV-RT-K1 (empty bitmap returns None), INV-INODE-K3 (file types mutually exclusive), INV-PCI-K4 (64-bit BAR detection bit shape), INV-ERRNO-K3 (EWOULDBLOCK == EAGAIN — POSIX).
  • The flagship proof (sync/mutex_kani.rs, the S-1 pilot's data half): K1 proves that for every disciplined operation sequence of length K the invariant table INV-M1..M4 holds after every step, INV-M5 token conservation holds throughout, and INV-M6 no arithmetic panics occur (Kani checks panic reachability directly); K2 proves the designed do_exit orphaned-waiter leak is bounded and does not impair the gate/epoch/anti-starvation paths. Both proofs complete in ~2.2 s (Kani 0.68.0).
  • Invariant density: 902 INV- references in the verify crate across ~150 invariant families; the kernel source carries another 158 runtime invariant references (INV-PCP, INV-LOCK, INV-FUTEX, INV-SCHED etc.).
  • Harness defects were caught too: the first runs surfaced three harness call-discipline gaps, each fixed — the pid-0 free-state alias (two kernel entities share pid 0 and must not be modeled as one), a counted waiter also acquiring ungated (a call sequence no single lock() invocation can produce), and the designed do_exit leak correctly flagged as an INV-M5 violation (detection correct; the model gained a leaked field). One run also repaired a pre-existing vma_kani compile break that had left cargo kani unable to build the crate at all.

§3SPIN model checking (4 models, all PASS)

ModelProperties checkedStatesVerdict
lock_orderingno deadlock cycle in lock acquisition; the hierarchy L0 IRQ → L1 preempt → 2a GRQ → 2b futex bucket → 3 waiter slot; INV-LOCK-5 (bucket→GRQ allowed, GRQ→bucket forbidden)313PASS (errors: 0)
futex_wait_wakeLTL NoLostWakeup + NoPermanentSleep; INV-FUTEX-1 (the waiter sets INTERRUPTIBLE under the bucket lock before dropping it)3,220,543PASS (1.19 s)
interrupt_preemptLTL HardirqBounded (0 ≤ depth ≤ 3) + PreemptNoUnderflow181PASS
sched_enqueue_dequeueLTL NrRunningValid (0 ≤ nr_running ≤ 4) + NoPermanentStarvation; INV-SCHED-1..34,815PASS
  • Run: make spin (spin -a → pan.c → pan -a); PASS requires errors: 0, the report is regenerated, and any FAIL/compile error exits 1; executed by nightly CI.
  • Liveness properties are scoped deliberately: interrupt_preempt intentionally omits starvation elimination ("SPIN explores starvation interleavings that do not exist on real hardware") — the criterion is model-reality correspondence, not state-count maximization.

§4loom interleaving enumeration: the SleepMutex extraction

A faithful extraction of a kernel concurrency primitive: mutex_model.rs extracts the handoff state machine of kernel/src/sync/mutex.rs (R84/R85 fairness + orphaned-handoff recovery) with the environment hooks (get_jiffies/wake_up_one/anti-starvation threshold) injected as parameters; mutex_loom.rs is the driver and the 8 scenarios.

  • The invariant table INV-M1..M6: M1 locked ⇒ depth ≥ 1; M2 !locked ⇒ owner == 0 (the converse does NOT hold: a pid==0 early-boot/IRQ-context caller may hold the lock through the ungated spinner); M3 !locked ⇒ depth == 0; M4 owner ≠ 0 ⇒ locked; M5 token conservation; M6 waiters never underflows. Mutual exclusion is asserted via a shared counter equal to exactly 1 inside every state critical section; deadlock freedom is checked separately.
  • 8 scenarios: 5 clean (two-task / three-task / spinner+sleepers / recursion-and-exit-release / anti-starve override) + 3 planted must-be-caught scenarios (P1 no-epoch recovery = the pre-R85 strand; P2 token-skip decrement = an M5 break; P4 repark-recount) — the instrument's detection power against known defect classes is itself calibrated.
  • Run: 8 scenarios in 59.5 s, preemption bound 3 (release); nightly CI builds with LOOM_MAX_PREEMPTIONS=3 and --cfg loom, failing on FAILED or deadlock.
  • First use caught a real kernel bug in 90 seconds (011a71c5): the recursion arms tested only owner == pid — a FREE lock carries owner == 0 and a no-task context's get_current_pid() returns 0, so a no-task caller hitting a momentarily free lock behind a counted waiter (the handoff window) matched the recursion arm and "recursed into" the unlocked lock, setting depth=1; that bogus guard's release could free a lock another task genuinely holds (mutual exclusion broken). The fix adds st.locked && to four recursion arms plus a deterministic regression test.
  • An exhaustive argument for a design feature: two-task pure-fair contention is strand-free WITHOUT the R85 timer; with 3+ waiters, strand interleavings exist that only the timer bounds — the anti-starvation timer's existence is proven by model checking, not assumed as a heuristic.
  • An interpretation rule on record: the timer is modeled partially (the park-time deadline check delivers the timer wake once other threads advance the model clock past the deadline) — a deadlock with the lock FREE and all waiters parked is the designed bounded-latency state, not a kernel bug.

§5Property testing and Miri

  • Scale: 1,184 #[test] functions in the verify crate (164 files), of which some are proptest! blocks (proptest 1.5, 256 cases per test by default, PROPTEST_CASES configurable); the kernel adds 1,584 cases (the unit-test feature, run in QEMU by make test).
  • Coverage: buddy alignment/involution, refcount never-negative with underflow-free release, VMA non-overlap, Newton integer sqrt and watermark formulas, Sv39 PTE/Satp encoding, RFC 1071 checksum / RFC 6298 RTT / RFC 5681 congestion, longest-prefix match, ARP-cache LRU, path normalization with root-escape prevention, Unix DAC checks (incl. CAP_DAC_OVERRIDE), ext4 indirect/namei/superblock/allocator, OOM badness scoring (10 tests: OOM_SCORE_ADJ_MIN immunity, saturation avoidance, small totalpages unadjusted, symmetry), CFS weight-table monotonicity, deadline bandwidth clamp, futex key matching, capability algebra (De Morgan/subset/complement), cmdline parsing, JBD2 tag arithmetic.
  • The boundary is stated as such: not covered are raw pointers/inline asm/GlobalAlloc impls, runtime concurrency and interrupts, and QEMU-required integration — "verify answers 'is the algorithm correct', unit tests answer 'is the implementation correct'"; the integration face is carried by LTP and the stress fleet.
  • Miri: interprets the entire verify crate with -Zmiri-disable-isolation; any UB fails the run (nightly, 360-minute budget).

§6The mirror-sync discipline: proofs pinned to the proven code

  • The verify crate mirrors proven algorithms by hand; drift between the mirror and the kernel source fails the build (scripts/verify_sync_check.py, per-function equivalence normalization) — a proof cannot silently stop covering its code as the kernel evolves; make verify/make kani/make miri and CI all run the sync check first.
  • State-machine extractions (mutex_model.rs) additionally require the state-transition table to change in the same commit as the kernel implementation.

§7Cadence

  • Every push: the triple-arch build smoke + the mirror sync + the full verify suite (1,184 tests) — within a per-commit budget.
  • Nightly: all 164 Kani harnesses, full Miri, the 4 SPIN models, the 8 loom scenarios — heavyweight jobs stay off the per-push path (so kernel commits are not painted red).
  • Before a proof-bearing change lands: make verify && make kani is run manually.

§8Survey pilots → landed

  • S-1 (the concurrency-primitive model-checking pilot, seL4 lineage): the SleepMutex extraction + the loom/Kani pair are in main (11c73f42/011a71c5/1d697ec2d/3b7b6f68); further extraction targets queue by incident density (the D-7 magazine, the D-11 GRQ claim, futex bucket nesting).
  • S-5 (typed timer-wheel slot ranges): landed as D-19 — six misuse classes became compile errors (evidence: six rustc rejections on the real tree + a same-test platform A/B).
  • S-2 (a typed binder transaction FSM) is a registered placeholder — the only exit from the placeholder zone is delivering measured evidence.
Instrument selection vs Linux: Linux has no Kani/loom/Miri counterpart, and SPIN corresponds to a compile-time subset of its lockdep — the difference here is that verification is moved to build/CI time rather than runtime sampling. Code: kernel/verify/ (34 harness files + spin/4 models + mutex_loom.rs); CI: .github/workflows/{kani,spin,loom,miri}.yml.