Abstract: Separation kernels provide temporal/spatial separation and controlled information flow to their hosted applications. They are introduced to decouple the analysis of applications in partitions from the analysis of the kernel itself. More than 20 implementations of separation kernels have been developed and widely applied in critical domains, e.g., avionics/aerospace, military/defense, and medical devices. Formal methods are mandated by the security/safety certification of separation kernels and have been carried out since this concept emerged. However, this field lacks a survey to systematically study, compare, and analyze related work. On the other hand, high-assurance separation kernels by formal methods still face big challenges. In this paper, an analytical framework is first proposed to clarify the functionalities, implementations, properties and standards, and formal methods application of separation kernels. Based on the proposed analytical framework, a taxonomy is designed according to formal methods application, functionalities, and properties of separation kernels. Research works in the literature are then categorized and overviewed by the taxonomy. In accordance with the analytical framework, a comprehensive analysis and discussion of related work are presented. Finally, four challenges and their possible technical directions for future research are identified, e.g. specification bottleneck, multicore and concurrency, and automation of full formal verification.
The Role of Separation Kernels
In safety-critical and high-security domains—such as avionics, medical devices, and military systems—there is a fundamental requirement for absolute certainty that software components cannot interfere with one another. Separation Kernels (SKs) serve as the specialized software "bedrock" designed to enforce this isolation. By providing a controlled environment for partitions, they allow developers to analyze individual applications independently of the kernel itself.
However, achieving "high-assurance" status is an immense engineering challenge. While numerous implementations exist, the field has historically lacked a systematic method for comparing them or the formal methods (mathematical proofs of correctness) used to verify their security properties. As hardware shifts toward complex multicore architectures, the difficulty of proving these kernels correct is increasing exponentially.
A Unified Analytical Framework
To address the lack of standardization, this research establishes a meta-framework for analysis. This framework defines a reference architecture for separation kernels, distinguishing between "common" components required for basic functionality and "optional" components often needed for specific industrial certifications.
Key components identified include:
- Common Components: Partition management, communication, process management, and scheduling.
- Optional Components: Health monitoring and clock management.
- DIDT Properties: The core goals of an SK are categorized into four properties: Data Separation, Information Flow Security, Damage Limitation, and Temporal Separation.
The Implementation Landscape
The survey examines 20 major separation kernel implementations, categorized into industrial and academic projects. This landscape reveals a significant diversity in target architectures (ISA) and development scales.
Industrial kernels like PikeOS, VxWorks 653, and INTEGRITY-178B are widely deployed but often proprietary. In contrast, academic projects like seL4 and Muen have pioneered "end-to-end" verification, where proofs extend from abstract specifications down to the actual C source or binary code. Most verified kernels are intentionally kept small—typically under 10,000 lines of code (LOC)—to ensure the mathematical proofs remain tractable.
Formal Methods and Taxonomy
The research proposes a five-level taxonomy to group formal methods applications:
- Formal Specification and Modeling: Creating mathematical descriptions of the kernel.
- Formalization of Critical Properties: Defining what "security" means mathematically.
- Formal Verification: Proving that the model meets the properties.
- Code Abstraction: Deriving models from existing C or binary code.
- Code Synthesis: Automatically generating proven code from specifications.
Key Insights and the "Heroic" Effort
The survey highlights the massive human cost associated with formal verification. For instance, the information flow proof for the seL4 kernel required approximately 51 person-months of expert labor. There is a clear industrial trend toward using Isabelle/HOL as the preferred tool for large-scale verification, largely due to its powerful automation capabilities.
A significant finding is the "Hardware Interface Neglect": many abstract formal models omit hardware-level details like interrupts and MMU management. This is a critical gap, as the kernel's primary responsibility is the secure management of that very hardware.
Grand Challenges for Future Research
Four critical roadblocks must be addressed to advance the field:
- Specification Bottleneck: Writing formal specs remains a manual, error-prone process. Reusable, generic specifications are needed.
- Automation: We are still far from "push-button" verification; current methods require "heroic" manual proof engineering.
- The Multicore Elephant: Most verified kernels are currently uniprocessor. Proving correctness in multicore environments introduces concurrency issues (race conditions, deadlocks) that current methods struggle to handle at scale.
- Correct-by-Construction: Shifting from post-hoc verification to automated code generation from proven specifications could significantly reduce development costs.
Summary updated