  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.
