A Spin-based model checking for the simple concurrent program on a preemptive RTOS

Chen-Kai Lin, Ching-Chun Huang, Bow-Yaw WangarXiv 2018 · OpenReview

TL;DR

This paper presents a novel approach to verifying the correctness of concurrent real-time operating system (RTOS) kernels. By adapting an existing proof framework to the Spin model checker, the authors enable automatic verification of critical properties like race condition, starvation, and deadlock freedom, significantly reducing the manual effort typically required.

What Problem Does This Paper Address?

Ensuring the correctness of concurrent programs, especially in real-time operating systems (RTOS), is notoriously difficult. Traditional methods like code review and testing often fail to uncover subtle race conditions, deadlocks, or starvation issues that arise from the complex interactions of asynchronous processes and preemptive scheduling. While formal proof methods exist, they demand extensive manual effort. This paper tackles the challenge of making the verification of concurrent RTOS programs more efficient and accessible by leveraging automated model checking.

Methods

The core of this work involves adapting an existing machine-assisted proof framework (eChronos) to the Spin model checker. The authors construct a detailed abstract model of a preemptive RTOS kernel, drawing inspiration from the Piko/RT kernel's design and the ARMv7-M architecture specification. This model incorporates key elements like preemptive scheduling, interrupt handling, and system calls. They then use Linear Temporal Logic (LTL) to formally specify properties related to race conditions, starvation, and deadlocks. Spin is employed to automatically verify these properties against the constructed model.

Datasets

Not discussed in the paper. The authors use a simulated model of a consumer/producer problem as a case study.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between manual, labor-intensive formal proofs and automated, yet potentially less expressive, model checking. By adapting an existing proof framework to Spin, they achieve the benefits of automated verification without sacrificing the ability to model complex RTOS behaviors.
  • ARMv7-M and Preemption Complexity: The paper highlights the intricate interplay of ARMv7-M architecture features (like exception handling and interrupt priorities) and preemptive scheduling, demonstrating how these can lead to subtle concurrency issues if not carefully managed.
  • Resource Intensive Verification: The verification process, while automated, is shown to be computationally intensive, requiring significant memory and time. This underscores the trade-off between the depth of verification and the computational resources needed.
  • The Power of Abstraction: The success of the approach hinges on creating an accurate yet manageable abstract model. The authors emphasize that an "elegant model" is key to representing real-world systems efficiently for verification.

Key Results

The authors successfully verified a simple concurrent program (consumer/producer) running on a simulated preemptive RTOS kernel. They demonstrated that under the specified conditions of preemptive scheduling and ARMv7-M mechanisms, the program would not suffer from race conditions, starvation, or deadlocks. The verification results, presented in Table 2, show significant state space exploration (billions of states) and substantial memory usage (hundreds of GB), with verification times ranging from 3.2 hours for safety properties to 10.4 hours for liveness properties.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Scalability and Cost: The cost in terms of time and memory for adding more processes to the model is prohibitively high. Future work could involve splitting the model into layers or using techniques to represent multiple processes with a limited number of abstract processes.
  • Model Homogeneity: Claiming the abstract model is truly homogeneous with the real-world system is challenging. Future work could focus on developing mechanisms to automatically extract PROMELA models from C source code.
  • Completeness of Verification: While the model's behavior is similar to the target system, it cannot be claimed to be totally correct. Further work involves adding more asserts, analyzing unreached statements, and applying test cases.
  • Specific Issues: The paper mentions ongoing efforts to address the idle thread problem and improve the handling of condition variables.

Summary updated

Abstract

We adapt an existing preemptive scheduling model of RTOS kernel by eChronos from machine-assisted proof to Spin-based model checker. The model we constructed can be automatically verified rather than formulating proofs by hand. Moreover, we look into the designs of a Linux-like real-time kernel--Piko/RT and the specification of ARMv7-M architecture to reconstruct the model, and use LTL to specify a simple concurrent programs--consumer/producer problem during the development stage of the kernel. We show that under the preemptive scheduling and the mechanism of ARMv7-M, the program will not suffer from race condition, starvation, and deadlock.
BibTeX
@misc{lin2018spin,
  author = {Chen-Kai Lin and Ching-Chun Huang and Bow-Yaw Wang},
  title = {{A Spin-based model checking for the simple concurrent program on a preemptive RTOS}},
  year = {2018},
  eprint = {1808.04239},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.04239},
}

Loading related content...

Figure