Extending concurrent separation logic to the hardware level to verify the xv6 OS kernel on RISC-V with AI agents
M. Frans Kaashoek, Nickolai Zeldovich
cs.LO
Sep 3, 2026 · v3
cs.OS
TL;DR
The Rocq-based MachCSL/xv6 verification was ported to Lean by an AI agent, exposing and fixing a boolean-semantics bug in Sail's Lean extraction.
Abstract
MachCSL is a framework for verifying system software, such as an OS kernel, on top of low-level semantics of a RISC-V computer, based on the Sail RISC-V semantics. The key idea behind MachCSL is to adapt concurrent separation logic, based on Iris, to reasoning about low-level hardware execution at the sub-instruction level: page-table translation, TLB, privilege levels, configuration registers, instruction fetch/decode/execute, traps and interrupts, DMA, shared memory, power failures, etc. Reasoning at this level of detail ensures that the system software correctly manages all of the hardware details. Verifying software at this low level of abstraction is tedious, but LLM-based agents are capable of reasoning about such low-level details. As a case study, we verify the xv6 OS kernel (6,657 lines of C and assembly code), which provides a traditional Unix system call interface (processes, file system, file descriptors, and preemptive scheduling) and has substantial internal concurrency (multi-core support with fine-grained locking, shared memory, interrupts, DMA, etc.). In the verification process, we uncovered 11 bugs in the xv6 implementation, as well as one bug in the Sail RISC-V semantics, and one bug in Sail's Lean extraction. The verification effort took us 102 days, including the time to develop the MachCSL framework. On top of the verified xv6 kernel, we prove a theorem about console-level behavior: e.g., if the user types echo hello world as input on the UART console, the only output the system can produce is hello world (if there are no crashes or other errors). This theorem covers both the kernel and the init, sh, echo, cat, grep, sync, and seccomp binaries in the initial file system image.
Problem
OS kernels must correctly manage low-level hardware such as page tables, TLBs, interrupts, DMA and multicore concurrency. Verifying kernels against detailed hardware semantics is tedious and rarely done end to end.
Approach
MachCSL adapts Iris-based concurrent separation logic to sub-instruction-level reasoning over the Sail RISC-V model, extended with models of shared memory, devices, DMA and power failures. LLM-based agents (Claude) were used to write specifications and proofs for the xv6 kernel and for user programs including init, sh, echo, cat, grep, sync and seccomp. The roughly 1.6M-line development was done in Rocq and later ported entirely to Lean by an agent.
Results
The development proves a console-level theorem: typing 'echo hello world' can only produce 'hello world' or an allowed error. It also yields kernel integrity, process isolation, crash safety and hardware safety. The work found 11 xv6 bugs, one Sail RISC-V model bug, and one Sail Lean-extraction bug (eager boolean evaluation), which was fixed in the Sail tool. The effort took 102 days.
| Bug | Component | Consequence |
|---|
| A/D writeback was a blind write | Sail model | One CPU could resuscitate a page-table entry another CPU cleared |
| Incorrect short-circuiting boolean semantics | Sail extraction | Wrong boolean operator semantics in the Lean CPU model |
| iput freed inode before dropping reference | fs | Racing iput and ialloc could orphan an on-disk inode |
| Overflowing nlink | fs | Unlinking an inode with too many links panicked |
Selected bugs found