This is the L4.verified git repository with formal specifications and proofs for the seL4 microkernel.
This repository is meant to be used as part of a Google repo setup. Instead of cloning it directly, please go to the following repository and follow the instructions there:
For setting up the theorem prover and other dependencies, please see the section Dependencies below.
Contributions to this repository are welcome.
CONTRIBUTING.md for details.
The repository is organised as follows.
spec: a number of different formal specifications of seL4
abstract: the functional abstract specification of seL4
sep-abstract: an abstract specification for a reduced version of seL4 that is configured as a separation kernel
haskell: Haskell model of the seL4 kernel, kept in sync with the C code
machine: the machine interface of these two specifications
cspec: the entry point for automatically translating the seL4 C code into Isabelle
capDL: a specification of seL4 that abstracts from memory content and concrete execution behaviour, modelling the protection state of the system in terms of capabilities. This specification corresponds to the capability distribution language capDL that can be used to initialise user-level systems on top of seL4.
take-grant: a formalisation of the classical take-grant security model, applied to seL4, but not connected to the code of seL4.
There are additional specifications that are not tracked in this repository, but are generated from other files:
proof: the seL4 proofs
invariant-abstract: invariants of the seL4 abstract specification
refine: refinement between abstract and design specifications
crefine: refinement between design specification and C semantics
access-control: integrity and authority confinement proofs
infoflow: confidentiality and intransitive non-interference proofs
asmrefine: Isabelle/HOL part of the seL4 binary verification
drefine: refinement between capDL and abstract specification
sep-capDL: a separation logic instance on capDL
capDL-api: separation logic specifications of selected seL4 APIs
lib: generic proof libraries, proof methods and tools. Among these, further libraries for fixed-size machine words, a formalisation of state monads with nondeterminism and exceptions, a generic verification condition generator for monads, a recursive invariant prover for these (
crunch), an abstract separation logic formalisation, a prototype of the Eisbach proof method language, a prototype
levityrefactoring tool, and others.
tools: larger, self-contained proof tools
asmrefine: the generic Isabelle/HOL part of the binary verification tool
c-parser: a parser from C into the Simpl language in Isabelle/HOL. Includes a C memory model.
autocorres: an automated, proof-producing abstraction tool from C into higher-level Isabelle/HOL functions, based on the C parser above
haskell-translator: a basic python script for converting the Haskell prototype of seL4 into the executable design specification in Isabelle/HOL.
misc: miscellaneous scripts and build tools
camkes: an initial formalisation of the CAmkES component platform on seL4. Work in progress.
sys-init: specification of a capDL-based, user-level system initialiser for seL4, with proof that the specification leads to correctly initialised systems.
Almost all proofs in this repository should work within 4GB of RAM. Proofs involving the C refinement, will usually need the 64bit mode of polyml and about 16GB of RAM.
The proofs distribute reasonably well over multiple cores, up to about 8 cores are useful.
The proofs in this repository use
Isabelle2018. A copy of Isabelle
is included in the repository setup.
The dependencies for installing Isabelle in this repository are
- Perl 5.x with
- Python 2.x
- LaTeX, for instance on Ubuntu 14.04
sudo apt-get install texlive-fonts-recommended texlive-latex-extra texlive-metapost texlive-bibtex-extra
- 32-bit C/C++ standard libraries on 64-bit platforms (optional)
For running the standalone version of the C Parser you will additionally need
- MLton ML compiler (package
For building the Haskell kernel model, the Haskell build tool stack is
required. The Haskell kernel
Makefile will use
stack to obtain appropriate
cabal-install. Note that this repository does not
contain the QEmu interface for actually running the model.
For running the C proofs, you need a working C preprocessor setup for the seL4 repository.
On Linux: the best way to make sure you have everything is to install the full build environment for seL4:
- seL4 development tool chain on Debian and Ubuntu
makeversion 3.81 or higher
You can get away with avoiding a full cross compiler setup form the above, but you will need at least these:
sudo apt-get install python-pip python-dev libxml2-utils sudo pip install sel4-deps
On MacOS: here it is harder to get a full cross-compiler setup going. For normal proof development, a full setup is not necessary, though. You mostly need a gcc-compatible C pre-processor and python. Try the following steps:
XCodefrom the AppStore and its command line tools. If you are running MacPorts, you have these already. Otherwise, after you have XCode installed, run
gcc --versionin a terminal window. If it reports a version, you're set. Otherwise it should pop up a window and prompt for installation of the command line tools.
- install the seL4 Python dependencies, for instance using
sudo easy_install sel4-deps.
easy_installis part of Python's
- install the
misc/scripts/cppwrapper for clang, by putting it in
~/bin, or somewhere else in your
After the repository is set up in Google repo, you should have following
directory structure, where
l4v is the repository you are currently looking
verification/ isabelle/ l4v/ seL4/
To set up Isabelle for use in
l4v/, assuming you have no previous
installation of Isabelle, run the following commands in the directory
mkdir -p ~/.isabelle/etc cp -i misc/etc/settings ~/.isabelle/etc/settings ./isabelle/bin/isabelle components -a ./isabelle/bin/isabelle jedit -bf ./isabelle/bin/isabelle build -bv HOL-Word
These commands perform the following steps:
- create an Isabelle user settings directory.
- install L4.verified Isabelle settings.
These settings initialise the Isabelle installation to use the standard
contribtools from the Munich Isabelle repository and set up paths such that multiple Isabelle repository installations can be used side by side without interfering with each other.
contribcomponents from the Munich repository. This includes Scala, a Java JDK, PolyML, and multiple external provers. You should download these, even if you have these tools previously installed elsewhere to make sure you have the right versions. Depending on your internet connection, this may take some time.
- compile and build the Isabelle PIDE jEdit interface.
- build basic Isabelle images, including
HOL-Wordto ensure that the installation works. This may take a few minutes.
Alternatively, it is possible to use the official Isabelle2018 release
bundle for your platform from the Isabelle website. In this case, the
installation steps above can be skipped, and you would replace the directory
verification/isabelle/ with a symbolic link to the Isabelle home directory
of the release version. Note that this is not recommended for development,
since Google repo will overwrite this link when you synchronise repositories
and Isabelle upgrades will have to be performed manually as development
Running the Proofs
If Isabelle is set up correctly, a full test for the proofs in this repository can be run with the command
from the directory
Not all of the proof sessions can be built directly with the
isabelle build command.
The seL4 verification proofs depend on Isabelle specifications that are
generated from the C source code and Haskell model.
Therefore, it's recommended to always build using the supplied makefiles,
which will ensure that these generated specs are up to date.
To do this, enter one level under the
l4v/ directory and run
For example, to build the C refinement proof session, do
cd l4v/proof make CRefine
As another example, to build the session for the Haskell model, do
cd l4v/spec make ExecSpec
HEAPS variable in the corresponding
Makefile for available targets.
Proof sessions that do not depend on generated inputs can be built directly with
./isabelle/bin/isabelle build -d . -v -b <session name>
from the directory
l4v/. For available sessions, see the corresponding
ROOT files in this repository. There is roughly one session corresponding to
each major directory in the repository.
For interactively exploring, say the invariant proof of the abstract specification with a pre-built logic image for the abstract specification, run
./isabelle/bin/isabelle jedit -d . -l ASpec
l4v/ and open one of the files in