Formalising a High-Performance Microkernel

These guys have made a prototype of an embedded OS microkernel in Haskell (which they then attached to an ARM CPU simulator so that it could execute programs), "verified the API design" by translating the Haskell implementation into Isabelle/HOL (a formal proof assistant), and then actually implemented the microkernel in C. Cool stuff!

Formalising a High-Performance Microkernel

Kevin Elphinstone, Gerwin Klein and Rafal Kolanski

Abstract

This paper argues that a pragmatic approach is needed for integrating design and formalisation of complex systems. We report on our approach to designing the seL4 operating system microkernel API and its formalisation in Isabelle/HOL. The formalisation consists of the systematic translation of significant parts of the functional programming language Haskell into Isabelle/HOL, including monad-based code. We give an account of the experience, decisions and outcomes in this translation as well as the technical problems we encountered together with our solutions. The longer-term goal is to demonstrate that formalisation and verification of a large, complex, OS-level code base is feasible with current tools and methods and is in the order of magnitude of traditional development cost.

Online Copy

Available as [PDF]