seL4: Formal Verification of an OS Kernel
PublishedProceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles
It appeared in a journal, conference or book, which normally review work before accepting it. Even so, one study is never the final word.
Abstract
Complete formal verification is the only known way to guarantee that a system is free of programming errors. We present our experience in performing the formal, machine-checked verification of the seL4 microkernel from an abstract specification down to its C implementation. We assume correctness of compiler, assembly code, and hardware, and we used a unique design approach that fuses formal and operating systems techniques. To our knowledge, this is the first formal proof of functional correctness of a complete, general-purpose operating-system kernel. Functional correctness means here that the implementation always strictly follows our high-level abstract specification of kernel behaviour. This encompasses traditional design and implementation safety properties such as the kernel will never crash, and it will never perform an unsafe operation. It also proves much more: we can predict precisely how the kernel will behave in every possible situation. seL4, a third-generation microkernel of L4 provenance, comprises 8,700 lines of C code and 600 lines of assembler. Its performance is comparable to other high-performance L4 kernels.
Research Analysis
Written by Kurz, not by the authors of the paper. The abstract above is the authors' own.
- Last revised
- Version
- 1.0
Overview
The kernel runs in the most privileged mode of the processor, so a bug in it can undermine everything above it. The usual answer is to shrink the privileged code: microkernels, separation kernels and small hypervisors all do this, and the exokernel pushes the same idea in another direction by exporting hardware safely and leaving management to libraries. The authors argue that with a truly small kernel one can go further and prove the absence of implementation bugs. seL4 is influenced by EROS and uses capabilities for authorization, memory allocation included; capabilities are one of the protection mechanisms surveyed in The Protection of Information in Computer Systems.
This SOSP 2009 paper from NICTA, UNSW, Open Kernel Labs and ANU reports a finished verification of seL4 for ARMv6 (Freescale i.MX31). Later verification work in the catalog, such as Verus and Atmosphere, takes a different route: proofs checked by an SMT-based verifier over Rust, not interactive proofs about C. TreeSLS is a microkernel that cites seL4 only as a capability kernel.
Worth knowing first: Hoare logic (pre- and postconditions), the idea of refinement between an abstract and a concrete state machine, and L4-style microkernels, where drivers run in user mode and everything talks through IPC.
Contribution
- A refinement proof from specification to C. Isabelle/HOL proves that the C implementation (MC) refines an executable specification (ME), which refines an abstract specification (MA), so MC refines MA by transitivity.
- A design process that fuses OS and formal methods. A Haskell prototype, linked with a QEMU-derived hardware simulator, is the shared artifact: OS developers run it, and it is translated automatically into the prover. The production kernel is then written by hand in C for performance.
- A formal semantics of a large subset of C99, with explicit proof obligations for pointer safety and a restricted subset (no address-of on locals, no function pointers, no goto, no unions).
- Kernel design for verifiability. An event-based kernel with a single stack and a mostly atomic API, interrupts handled by polling at a few preemption points, user-level drivers, user-level allocation policy with a capability derivation tree, and zombie capabilities that make object destruction preemptable.
- Cost and experience data for a project of this kind, including the cost of changing a verified kernel.
Methodology
The authors fix the property first: functional correctness, shown as forward-simulation refinement between state machines. Kernel transitions are specified at each layer; user behavior is fully non-deterministic, so the proof covers benign, buggy and malicious user programs. The abstract specification says what the kernel does (for example, scheduling picks any runnable thread or the idle thread); the executable specification says how (a priority-based round-robin scheduler, with the capability derivation tree as a doubly linked list). The C code is read into the prover through the C semantics, and the machine is modelled through a small interface of functions (Figure 6 in the paper) that are left as non-deterministic as possible.
The paper then describes what is and is not covered, categorizes the invariants (memory, typing, data structure, algorithmic), and reports effort per phase. Performance is measured as one-way IPC cycles on an i.MX31 (532 MHz ARM1136JF-S) with hot caches and the processor cycle counter, against OKL4 2.1 on the same board and a published XScale result.
Findings
- Size. Table 1: 8,700 lines of C, plus 600 lines of assembler; 5,700 lines of Haskell for the executable layer; abstract specification of 4,900 lines of Isabelle and executable specification of 13,000; the C code read into Isabelle is 15,000. The proofs are about 110,000 lines for the first refinement step and 55,000 for the second; with frameworks, libraries and generated proofs the total is 200,000 lines of Isabelle script. The proof covers over 150 invariants.
- Effort. About 20 person-years of proof in total, of which 9 went into language frameworks, tools and libraries and 11 were seL4-specific. The first refinement took 8 py, the second under 3 py. The design side cost about 2.2 py including the Haskell prototype, against about 6 py for Pistachio and 4 py estimated by SLOCCount, so the authors conclude the Haskell detour did not add cost. They estimate a repeat verification would take 6 py of proof, 8 py in total.
- What is guaranteed. The kernel never fails and always has defined behavior (assertions hold, no null or misaligned pointer access), all kernel calls terminate and return, and argument checking cannot be subverted from user level, as long as the assumptions hold. About 80 percent of the proof effort went into invariants.
- Bugs. 16 defects were found before verification started, then 144 more by verification, and 54 further code changes were made to ease the proof. The first refinement led to about 300 changes in the abstract and 200 in the executable specification, about half of them bug fixes.
- Performance. Optimized one-way IPC takes 224 cycles for seL4, against 206 for the hand-crafted assembly path of OKL4 2.1 on the same board and 151 cycles reported for XScale. The non-optimized C path of OKL4 took 756. The optimized seL4 path was not yet in the verified code base.
- Cost of change. A new batching system call took one day to implement and under a person-week of proof; adding interrupts, ARM page tables and address spaces took 1.5 to 2 py to re-verify; reply capabilities, under 5 percent of the code, took about 1 py (17 percent of the original proof effort).
Critical Analysis
The paper is unusually explicit about its limits, and that is its main strength. The theorems state correspondence between kernel entry and exit points. The authors assume the GCC compiler, the assembly code, the hardware, the boot and initialization code (about 1.2 kLOC), and the cache and TLB management done through the machine interface; the consistency of the in-kernel virtual memory window is argued only informally. The proof is for a uniprocessor kernel on ARMv6; the x86 port was done without proof, and the access-control proof is not yet connected to this one. The proof also shows the implementation matches the specification, not that the specification is what users need, as the authors themselves note.
What the paper does not claim: it does not discuss DMA, timing or worst-case latency, or covert channels, and says nothing about security properties beyond functional correctness. The 224-cycle IPC figure is one microbenchmark on one board, not a system benchmark.
Literature after the paper, known to me only by titles and venues checked in Crossref (I did not read these for this note): "Translation validation for a verified OS kernel" (PLDI 2013), whose title suggests work on the compiler assumption; "seL4: From General Purpose to a Proof of Information Flow Enforcement" (IEEE S&P 2013); "Timing Analysis of a Protected Operating System Kernel" (RTSS 2011); and the journal article "Comprehensive formal verification of an OS microkernel" (ACM TOCS 2014). The compiler assumption is also what Finding and Understanding Bugs in C Compilers tests empirically for wrong-code bugs. For cost comparisons, the Atmosphere paper in the catalog reports a proof-to-code ratio of 20:1 for seL4 and 3.32:1 for itself; that is its own computation, not a figure from this paper.
Further Research
- Verifying the assembly, the boot code and the compiler output, to remove the trusted base below C.
- A multi-core version of the kernel, which the authors leave for future work.
- Connecting the access-control model to the refinement proof, and proving further security properties on the abstract specification.
- Application-level verification that relies on the abstract kernel specification.
- Lowering proof cost for new kernels, for example with more automation or different languages and verifiers, as in the Verus line of work.
Full text
Discussion · 0
Sign in to join the discussionNo posts yet. Be the first to start the discussion.