Formal Specification and Verification of Separation Kernels: An Overview

Yongwang ZhaoarXiv 2015 · arXiv

TL;DR

This paper surveys the landscape of formal specification and verification techniques for separation kernels, crucial components in safety- and security-critical systems. It highlights the challenges in ensuring their correctness and provides a structured overview of existing research, aiming to guide future development and verification efforts.

What Problem Does This Paper Address?

Separation kernels are the bedrock of systems requiring high assurance, like those in avionics or defense. They ensure that different software components (partitions) can coexist on the same hardware without interfering with each other, either spatially (memory access) or temporally (CPU time), and that information flows only through explicitly defined channels. The critical nature of these systems means that even minor bugs in the separation kernel can have catastrophic consequences. However, formally proving the correctness of these complex software components is a significant challenge. This paper addresses the need for a comprehensive overview of the state-of-the-art in formally specifying and verifying these kernels, identifying common approaches, properties, and the tools used, to help researchers and practitioners navigate this complex field.

Methods

The paper categorizes research on separation kernels into three main areas:

  • Formalization of Security Policies and Properties: This involves defining precisely what a separation kernel should do, using formal languages to express security policies (like MILS and SKPP) and properties (data separation, information flow security, temporal separation, fault isolation).
  • Formal Specification and Models of Separation Kernels: This focuses on creating abstract models of separation kernels that capture their essential behavior and can be used as a basis for verification. Techniques like Z notation, B Method, and state machines are employed.
  • Formal Verification of Separation Kernels: This is the core of the work, where researchers use formal methods (theorem proving, model checking) to mathematically prove that the kernel's implementation adheres to its formal specification and security properties.

The paper also discusses different types of kernels (security kernels, partitioning kernels, hypervisors) and compares their functionalities and verification approaches.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "NEAT" Properties: Separation kernels are often evaluated against four key properties: Non-bypassable, Evaluatable, Always-invoked, and Tamper-proof. These provide a framework for understanding the desired security guarantees.
  • Spatial vs. Temporal Separation: The paper clearly distinguishes between spatial separation (data and fault isolation) and temporal separation (time partitioning), noting that different verification techniques are often applied to each.
  • Theorem Proving Dominance for Spatial Properties: For spatial separation properties like data separation and information flow security, theorem proving is the predominant approach. This is attributed to the need for full formal verification and the suitability of theorem provers for complex logical reasoning.
  • Model Checking for Temporal Properties: Temporal separation, on the other hand, often leverages model checking. This is because temporal properties are more naturally expressed in temporal logics and model checkers can handle the time-based aspects more effectively.
  • The seL4 Success Story: The formal verification of the seL4 microkernel is highlighted as a significant achievement, demonstrating the feasibility and benefits of fully formal verification, even for substantial codebases.
  • The Importance of Formal Specification: The paper emphasizes that a well-defined formal specification is a prerequisite for effective verification, acting as a guide for both development and proof.

Key Results

The paper presents a comprehensive survey of numerous research efforts in formally specifying and verifying separation kernels. While specific quantitative results are not aggregated into a single table, the survey details various projects that have:

  • Formalized security policies and properties: Including MILS, SKPP, and specific properties like data separation, information flow security, and temporal separation.
  • Developed formal models: Using languages like Z, B, PVS, and state machines for kernels like MASK, ED, PikeOS, and INTEGRITY-178B.
  • Achieved formal verification: Demonstrating correctness for specific kernels and properties using tools like Isabelle/HOL, ACL2, PVS, Spin, and VCC. For instance, the seL4 verification found numerous bugs and involved extensive proof efforts.

The survey highlights that many commercial separation kernels have undergone formal analysis or certification, with some reaching high assurance levels (e.g., EAL 6+).

Limitations and Future Work

  • Complexity of Full Formal Verification: While fully formal verification of source code is ideal, it remains a significant undertaking, often requiring substantial effort and specialized tools. The paper notes that many verification efforts focus on abstract models rather than the entire source code.
  • Automation Challenges: The degree of automation in formal verification is a key limitation. While theorem provers are powerful, they often require significant manual effort. Model checking offers more automation but struggles with the state-space explosion for complex systems.
  • Interplay of Properties: The relationship between different security properties (spatial and temporal separation, fault isolation) is complex and requires further study.
  • Formal Verification of Temporal Separation: The paper suggests that more research is needed to improve theorem-proving approaches for temporal separation, as current methods often face limitations with complex scheduling configurations.
  • Future Work: The authors suggest future work should focus on formal comparison of correctness properties, developing formal models for separation kernels, and advancing efforts in fully formal verification, particularly on source code levels. They also advocate for formal development methods like B and Z for creating new separation kernels.

Summary updated

BibTeX
@misc{zhao2015formal,
  author = {Yongwang Zhao},
  title = {{Formal Specification and Verification of Separation Kernels: An Overview}},
  year = {2015},
  eprint = {1508.07066},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1508.07066},
}

Loading related content...

Figure