Automatically Proving Microkernels Free from Privilege Escalation from their Executable
This provides a low-cost, high-confidence verification solution for kernel security, addressing a critical need in computer systems, though it is incremental as it builds on prior formal verification efforts.
The authors tackled the problem of proving operating system microkernels free from privilege escalation by developing a fully-automated method that works directly on executable code, requiring only 58 lines of annotation and less than 10 minutes of computation to find a vulnerability in one version and verify security in another.
Operating system kernels are the security keystone of most computer systems, as they provide the core protection mechanisms. Kernels are in particular responsible for their own security, i.e. they must prevent untrusted user tasks from reaching their level of privilege. We demonstrate that proving such absence of privilege escalation is a pre-requisite for any definitive security proof of the kernel. While prior OS kernel formal verifications were performed either on source code or crafted kernels, with manual or semi-automated methods requiring significant human efforts in annotations or proofs, we show that it is possible to compute such kernel security proofs using fully-automated methods and starting from the executable code of an existing microkernel with no modification, thus formally verifying absence of privilege escalation with high confidence for a low cost. We applied our method on two embedded microkernels, including the industrial kernel AnonymOS: with only 58 lines of annotation and less than 10 minutes of computation, our method finds a vulnerability in a first (buggy) version of AnonymOS and verifies absence of privilege escalation in a second (secure) version.