Event-based formalization of safety-critical operating system standards: An experience report on ARINC 653 using Event-B

Yongwang Zhao, Zhibin Yang, David Sanán, Yang Liu

Abstract

Standards play the key role in safety-critical systems. Errors in standards could mislead system developer's understanding and introduce bugs into system implementations. In this paper, we present an Event-B formalization and verification for the ARINC 653 standard, which provides a standardized interface between safety-critical real-time operating systems and application software, as well as a set of functionalities aimed to improve the safety and certification process of such safety-critical systems. The formalization is a complete model of ARINC 653, and provides a necessary foundation for the formal development and verification of ARINC 653 compliant operating systems and applications. Six hidden errors were discovered from the verification using the Event-B formal reasoning approach.

Introduction: The High Stakes of Avionics Software

In safety-critical avionics, software failure is not merely an inconvenience; it can lead to catastrophic loss of life and equipment. To manage the immense complexity of modern flight systems, the industry relies on Integrated Modular Avionics (IMA). This architecture allows multiple applications—ranging from non-critical entertainment systems to vital navigation and fuel management modules—to share the same hardware resources.

The cornerstone of this architecture is the ARINC 653 standard, which defines the interface between application software and the underlying Real-Time Operating System (RTOS). It ensures strict partitioning, preventing a bug in one application from crashing the entire system. However, ARINC 653 is traditionally documented using natural language and pseudo-code, which are inherently prone to ambiguity.

Figure 1: The ARINC 653 architecture showing software components within partitions interacting with hardware via the APEX interface and Partitioning OS.

Methodology: Correctness by Construction

To address the risks of ambiguity, researchers employed the Event-B formal method. Event-B is a mathematical approach used to build systems that are "correct by construction." Unlike traditional testing, which checks specific scenarios, formal verification mathematically proves that a system will behave correctly under all possible conditions.

The Refinement Strategy

Modeling an entire operating system standard in one go is practically impossible. Instead, the team used a refinement strategy. They began with a highly abstract model focusing on top-level partition switching and incrementally added layers of detail. Each layer (or "refinement") introduced new functionalities such as process states, timing constraints, inter-partition communication, and health monitoring.

Figure 2: Mapping the ARINC 653 Table of Contents to a series of Event-B Machines and Contexts through formalization and refinement.

Translating APEX Services

A significant technical hurdle was the "semantic gap" between the sequential pseudo-code of the APEX (Application Executive) services and the event-based logic of Event-B. The researchers developed a semi-automatic algorithm to translate these services into a "guard-action" style. In this paradigm, an action (e.g., switching a process state) can only occur if a specific set of mathematical conditions, known as guards, are met.

Key Insights: Bridging the Semantic Gap

The transition from sequential "Do A, then B" descriptions to event-based "If X is true, do A" logic forced the modelers to account for every possible system state at every micro-second. This rigorous scrutiny revealed that many "obvious" behaviors in the standard were actually underspecified.

To ensure safety, the authors extracted 27 core safety invariants directly from the ARINC 653 text. For example, one invariant states: "If a partition is not in NORMAL mode, none of its processes should be in the Running state." Using the Rodin platform, they generated 1,791 "proof obligations"—mathematical hurdles the model had to clear to prove it never violated these invariants. While 83% of these proofs were automated, 17% required expert human intervention, highlighting the continued need for domain expertise in formal methods.

Results: Uncovering Critical Flaws

The formalization process was highly successful, uncovering six significant errors in the latest version of the ARINC 653 standard (Part 1, Version 3). These included three logic errors and three omissions:

  • Incomplete Specifications for Aperiodic Processes: The standard lacked critical transition rules for tasks that do not run on a fixed schedule when the system moves between different modes.
  • The RESUME Logic Bug: A flaw in process management could incorrectly move a suspended process to a "Ready" state even if its required delay timer had not yet expired.
  • Message Loss in Queuing: In inter-partition communication, a process waiting to send a message could time out and lose the message entirely because the standard failed to define buffer handling during that specific window.
  • Buffer Overflow in RECEIVE_BUFFER: The standard did not explicitly require removing a message from the queue after it was read, potentially leading to a permanently "full" buffer and system deadlock.

Conclusion and Future Work

This research demonstrates that even mature, industry-standard specifications can harbor subtle but dangerous logic errors. By providing the most complete formal model of ARINC 653 to date, the authors have created a benchmark for future OS development.

Looking forward, the team aims to address liveness properties—guaranteeing that "good things" (like a process eventually receiving CPU time) will actually happen, rather than just ensuring "bad things" don't. Additionally, as the aviation industry moves toward multicore processors, the complexity of formalization will increase, requiring new techniques to handle true concurrency. The ultimate goal remains the automatic generation of proven-correct C or Ada code directly from these formal models.

Summary updated

Abstract

Standards play the key role in safety-critical systems. Errors in standards could mislead system developer's understanding and introduce bugs into system implementations. In this paper, we present an Event-B formalization and verification for the ARINC 653 standard, which provides a standardized interface between safety-critical real-time operating systems and application software, as well as a set of functionalities aimed to improve the safety and certification process of such safety-critical systems. The formalization is a complete model of ARINC 653, and provides a necessary foundation for the formal development and verification of ARINC 653 compliant operating systems and applications. Three hidden errors and three cases of incomplete specification were discovered from the verification using the Event-B formal reasoning approach.
BibTeX
@inproceedings{zhao2015event,
  author = {Yongwang Zhao and Zhibin Yang and David Sanán and Yang Liu},
  title = {{Event-based formalization of safety-critical operating system standards: An experience report on ARINC 653 using Event-B}},
  booktitle = {ISSRE},
  year = {2015},
  url = {https://openreview.net/forum?id=tsXwV_X_q1},
}
Figure