Rely-guarantee Reasoning about Concurrent Memory Management: Correctness, Safety and Security

Yongwang Zhao, David SanánarXiv 2023 · DOI · arXiv

TL;DR

This paper presents the first formal specification and mechanized proof of correctness, safety, and security for a real-world concurrent memory management system (Zephyr RTOS buddy allocator). By extending the PiCore rely-guarantee framework, the authors not only verify the system's properties but also uncover critical bugs in the original C implementation.

What Problem Does This Paper Address?

Verifying concurrent operating system (OS) kernels is notoriously difficult, especially for dynamic memory management. Errors in this area can lead to system crashes or security vulnerabilities. While formal verification of sequential OS kernels is common, handling the complexities of concurrent memory management—where multiple threads can simultaneously access and modify shared data structures—poses significant challenges. Existing work often simplifies concurrency or focuses on less complex memory management algorithms. This paper tackles the problem of formally verifying a realistic, concurrent buddy memory allocator, ensuring its functional correctness, safety (e.g., no memory leaks or overlaps), and security (integrity of allocated memory).

Methods

The core of this work lies in the application and extension of the PiCore rely-guarantee framework. PiCore is a two-level, event-based framework designed for specifying and verifying concurrent reactive systems.

  • Fine-grained Formal Specification: The authors developed a detailed formal specification of Zephyr's buddy memory management in Isabelle/HOL, closely mirroring the C code to facilitate validation. This includes formalizing complex data structures like quad trees and bitmaps.
  • Rely-Guarantee Reasoning: This technique is used to decompose the verification problem. Each component (e.g., memory services) is specified with rely (environment assumptions) and guarantee (component's own behavior) conditions.
  • Compositional Verification: PiCore's compositional nature allows the verification of the entire system by verifying individual event systems and then composing their proofs.
  • Extension for Integrity: To address security properties like memory integrity (preventing one thread from altering another's allocated memory), the authors extended PiCore with a compositional reasoning approach for state-event based integrity. This involves defining integrity in terms of fine-grained semantics and observable equivalence.
  • State-Event Information-Flow Security (IFS): The security verification leverages concepts from state-event IFS, which is crucial for analyzing security in OS kernels where events (like interrupts and kernel services) play a significant role.

Datasets

Not discussed in the paper. The work focuses on formal verification of an existing software system (Zephyr RTOS) rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Formalizing Real-World Concurrency is Hard: The paper highlights the significant effort required to formally model and verify the intricate concurrency and data structures of a production-ready OS component like Zephyr's memory manager. The complexity of the buddy allocator's multi-level structure and its interaction with concurrent threads is a major challenge.
  • Rely-Guarantee is Powerful for Concurrent Systems: The success in applying and extending PiCore demonstrates the effectiveness of rely-guarantee reasoning for handling the complexities of concurrent memory management, allowing for compositional proofs.
  • Bugs Lurk in Complex Concurrent Code: The formal verification process uncovered three critical bugs in Zephyr's C implementation, underscoring the difficulty of manual code review for concurrent systems and the value of formal methods in finding subtle errors. Two of these bugs were critical and have been fixed.
  • Security Verification Requires Specialized Techniques: The need to extend PiCore for integrity verification, particularly for state-event based IFS in concurrent OS kernels, shows that standard verification techniques may not be sufficient for robust security guarantees in such environments.

Key Results

  • First Formal Specification and Proof: The paper presents the first formal specification and mechanized proof of correctness, safety, and security for a concurrent buddy memory allocation system in a realistic OS (Zephyr).
  • Verification of Critical Properties: The authors formally verified functional correctness, safety (via invariants), and security (memory separation and integrity) of the Zephyr memory management.
  • Identification of Bugs: Three bugs were found in the Zephyr C code:
  • An incorrect block split leading to external fragmentation.
  • An incorrect return code handling in k_mem_pool_alloc for FOREVER mode.
  • A non-termination issue in k_mem_pool_alloc when requesting a size larger than max_sz.
  • High Assurance Level: The work aims for and provides a specification that aligns with the highest evaluation assurance level (EAL 7) of Common Criteria, enabling code-to-spec review.
  • Verification Effort: The formalization and verification required approximately 34,000 lines of specification and proof (LOSP), with the security proof taking about 4 person-months.

Limitations and Future Work

  • Low-Level Design Specification: The verification is at the low-level design specification level, not directly at the source code level. While this is suitable for EAL 7, direct source code verification would be more comprehensive.
  • Scalability and Automation: The work is labor-intensive, and while Isabelle/HOL offers some automation, further improvements in proof automation for concurrent OS kernels are needed.
  • Confidentiality: The current PiCore framework only supports integrity. Extending it to support confidentiality is a key area for future work.
  • Verification of Other Modules: The authors plan to verify other Zephyr modules, which may be simpler due to less complex data structures.
  • More Expressive Language: Replacing PiCore's imperative language with a more expressive one and integrating a verification condition generator (VCG) could reduce verification costs.
  • Horizontal Verification: Exploring horizontal verification techniques to compose state of different OS kernel modules with minimal changes to the functional specification and proof is also planned.

Summary updated

BibTeX
@misc{zhao2023rely,
  author = {Yongwang Zhao and David Sanán},
  title = {{Rely-guarantee Reasoning about Concurrent Memory Management: Correctness, Safety and Security}},
  year = {2023},
  eprint = {2309.09997},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.09997},
}
Figure