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
| Instrument | Method | Proof target | Scale (current tree) | Cadence |
|---|---|---|---|---|
| make verify | mirror-sync check + property tests + unit tests | kernel algorithms mirrored into the host crate | 1,184 #[test] fns (incl. proptest! blocks) + 1,584 in-kernel cases | every push |
| make kani | symbolic execution — asserts and panic reachability for ALL inputs | core unsafe code and protocol invariants | 164 #[kani::proof] harnesses (34 files) | nightly CI |
| make spin | Promela model checking (state enumeration + LTL) | lock ordering / futex wait-wake / interrupt-preempt / sched enqueue-dequeue | 4 models, all PASS | nightly CI |
| loom | interleaving enumeration under a preemption bound | the SleepMutex handoff state machine | 8 scenarios (5 clean + 3 planted must-catch) | nightly CI |
| make miri | interpreted execution + UB detection | the whole verify mirror crate | with the 1,184 tests | nightly 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 withkani::assume, and asserts named invariantsINV-<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)
| Model | Properties checked | States | Verdict |
|---|---|---|---|
| lock_ordering | no 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) | 313 | PASS (errors: 0) |
| futex_wait_wake | LTL NoLostWakeup + NoPermanentSleep; INV-FUTEX-1 (the waiter sets INTERRUPTIBLE under the bucket lock before dropping it) | 3,220,543 | PASS (1.19 s) |
| interrupt_preempt | LTL HardirqBounded (0 ≤ depth ≤ 3) + PreemptNoUnderflow | 181 | PASS |
| sched_enqueue_dequeue | LTL NrRunningValid (0 ≤ nr_running ≤ 4) + NoPermanentStarvation; INV-SCHED-1..3 | 4,815 | PASS |
- 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 addsst.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.