Proving memory separation in a microkernel by code level verification

Abstract—Often, an integrated mixed-criticality system is built in an environment which provides separation functionality for available on-board resources. In this paper we treat such an envi-ronment: the PikeOS separation kernel – a commercial real-time embedded operating system. PikeOS allows applications with different safety and security levels to run on the same hardware. Obviously, a mixed-criticality system built on PikeOS relies on the correct implementation of the separation mechanisms. In the context of the Verisoft XT [1] and TECOM [2] projects we apply deductive formal software verification to the PikeOS separation mechanisms in order to validate this security requirement. In this work we consider formal verification of a kernel memory manager which is one of the crucial components of the separation functionality. The verification of the memory manager is carried out on the level of the source code using the VCC tool developed by Microsoft Research. Furthermore, we present the overall correctness arguments needed to prove the intended separation property, describe the necessary functional correctness properties of PikeOS, and explain how to formulate these properties in a modular way to be used by VCC. In doing so we demonstrate how a proof of a non-functional system requirement can be conducted based on results from formal verification on the lowest possible level of human-written artefacts, that is the source code level. Keywords-deductive verification; microkernel; memory separa-tion I