A survey on formal specification and verification of separation kernels

Yongwang Zhao, Zhibin Yang, Dianfu MaFrontiers of Computer Science 2017 · DOI

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 growing importance of these methods for ensuring the correctness of separation kernels and provides a comprehensive overview of existing research, identifying key challenges and future directions.

What Problem Does This Paper Address?

Separation kernels are fundamental to building secure and reliable systems by enforcing spatial and temporal isolation between different software components. In safety- and security-critical domains like avionics and defense, the correctness of these kernels is paramount. However, ensuring this correctness is a significant challenge due to the complexity of these systems and the stringent assurance requirements (e.g., Common Criteria EAL 7, DO-178B Level A). While formal methods offer a rigorous approach to proving correctness, there's a lack of a consolidated overview of how they are applied specifically to separation kernels. This paper aims to fill that gap by surveying the state-of-the-art in formal specification and verification of separation kernels, providing a valuable resource for researchers and practitioners.

Methods

The paper categorizes the research into three main areas:

  • Formalization of Security Policies and Properties: This involves defining security requirements and properties (like data separation, information flow security, temporal separation, and fault isolation) using formal languages and logic. Examples include the MILS security policies and the Separation Kernel Protection Profile (SKPP).
  • Formal Specification and Models of Separation Kernels: This focuses on creating abstract models of separation kernels that capture their essential functionalities and behavior. Techniques like Z notation, B Method, and Circus are employed to develop these models.
  • Formal Verification of Separation Kernels: This is the core of the paper, detailing how the formal specifications and models are used to prove the correctness of separation kernels. The primary approaches discussed are:
  • Theorem Proving: This is the dominant technique, used to mathematically prove properties about the system. Tools like ACL2, PVS, Isabelle/HOL, and HOL4 are frequently mentioned.
  • Model Checking: While less common for spatial separation properties due to state-space explosion, it's used for temporal separation properties, especially with timed automata and tools like UPPAAL and Spin.

The paper also discusses the relationship between different security properties and compares theorem proving with model checking for verification.

Datasets

Not discussed in the paper. The paper focuses on surveying existing research and methodologies rather than introducing new datasets or benchmarks.

Key Insights and Ideas

  • The Growing Need for Formal Verification: The paper strongly emphasizes that for safety and security-critical systems, formal verification is not just desirable but often a requirement to achieve high assurance levels.
  • Dominance of Theorem Proving for Spatial Separation: For properties like data separation and information flow security, theorem proving is the go-to method due to its ability to handle complex logical reasoning and its suitability for small, well-defined systems like separation kernels.
  • Model Checking's Role in Temporal Separation: Temporal separation, dealing with time-based properties, is more amenable to model checking techniques, particularly those involving timed automata.
  • The "NEAT" Properties: The paper highlights the importance of properties like Non-bypassable, Evaluatable, Always-invoked, and Tamper-proof (NEAT) as foundational for separation kernels.
  • seL4 as a Benchmark: The formal verification of the seL4 microkernel is presented as a significant achievement, demonstrating the feasibility of fully formal verification on a substantial codebase and finding numerous bugs.
  • The Challenge of Automation: While formal methods are powerful, the lack of full automation in theorem proving remains a bottleneck, driving research into more automated approaches.

Key Results

The paper doesn't present new experimental results but rather synthesizes findings from numerous existing research works. Key qualitative findings include:

  • Numerous separation kernels (e.g., INTEGRITY-178B, PikeOS, seL4) have undergone formal specification and/or verification.
  • Formal methods have successfully identified bugs in separation kernels, even in highly scrutinized systems.
  • The application of formal methods has led to increased confidence in the correctness of these critical components.
  • The paper provides a detailed comparison of various approaches, formal languages, and tools used in the field.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Formal Comparison of Properties: While the paper categorizes properties, a deeper, formal comparison of their relationships and implications is needed.
  • Formal Model for Separation Kernels: The need for a standardized, comprehensive formal model for separation kernels is highlighted.
  • Efforts on Fully Formal Verification: The paper advocates for extending fully formal verification to the source code level, as demonstrated by seL4, to achieve the highest assurance.
  • Automation in Verification: There's a strong call for increased automation in formal verification, particularly for spatial separation properties, to make these techniques more scalable and accessible.
  • Temporal Separation Verification: The paper suggests that more research is needed to improve theorem-proving approaches for temporal separation, as model checking faces scalability issues.
  • Relationship between Spatial and Temporal Separation: The complex relationship between spatial and temporal separation needs further study.

Summary updated

BibTeX
@article{zhao2017survey,
  author = {Yongwang Zhao and Zhibin Yang and Dianfu Ma},
  title = {{A survey on formal specification and verification of separation kernels}},
  journal = {Frontiers of Computer Science},
  year = {2017},
  doi = {10.1007/s11704-016-4226-2},
}
Figure