Bridging the Semantic Gap: Automating the Formal Verification of ARINC 653

TL;DR

In the world of safety-critical avionics, the ARINC 653 standard is the "law of the land" for Partitioning Operating Systems (POSs). However, law written in natural language is often ambiguous. This paper introduces a groundbreaking methodology that uses OWL2 Ontologies as a bridge to translate these informal requirements into Event-B formal specifications. Not only did this approach automate 99% of the mathematical proofs, but it also unmasked six hidden errors in the ARINC standard itself.

The "Vague Requirement" Problem

The complexity of modern OS kernels like seL4 famously required 20 person-years to verify. For POSs, the challenge is threefold:

1. Informality: Standards are a messy mix of natural language and loosely structured grammars.
2. Reusability: Formal models are often "one-offs" that can't be reused for system management or other OS implementations.
3. Efficiency: Manually writing formal proofs for 100+ pages of requirements is an industrial nightmare.

Earlier attempts to formalize ARINC 653 were either incomplete—focusing only on tiny subsets of services—or relied on manual translations that missed the forest for the trees.

Methodology: Ontology meets Refinement

The authors' core "Insight" is that we shouldn't translate natural language directly to math. Instead, we need an intermediate layer that understands the domain.

1. OWL-POS: The Domain Knowledge Layer

They created OWL-POS, the first-of-its-kind ontology for partitioning systems. It defines 67 classes (like Partition, Process, Semaphore) and 150 relations. By using Web Ontology Language (OWL2), they created a machine-readable "dictionary" of the OS's structure.

2. The Translation Pipeline (OWL2EB & APEX2EB)

The researchers developed two crucial mapping algorithms:

• OWL2EB: Automatically converts static ontology structures (classes, properties) into Event-B sets, constants, and axioms.
• APEX2EB: Parses the APEX service grammar (e.g., IF-THEN-ELSE) and generates discrete Event-B events.

Above: The workflow from informal standard to verified Event-B specification via the OWL-POS intermediate model.

3. Stepwise Refinement

Rather than modeling everything at once, they used Event-B refinement. They started with abstract partition modes and "zoomed in" layer by layer until they reached the 57 complex services required by ARINC 653 Part 1.

Breakthrough Results: Squashing Bugs in the Standard

During formal analysis in the RODIN environment, the system flagged contradictions. These weren't just coding bugs; they were specification errors in the ARINC 653 document.

• The Resume Glitch (E4): When resuming a delayed aperiodic process, the standard incorrectly suggested setting it to Ready even if the delay timer hadn't expired. This could cause a process to execute prematurely, potentially violating safety timing.
• Communication Errors (E5, E6): The SEND_QUEUING_MESSAGE service had a logic flaw where messages could be "lost" even when space became available.

The authors validated these findings in real-world code. For instance, the POK open-source POS was found to harbor the same RESUME service error (E4) identified by the formal model.

Above: Evidence of efficiency. Notice that 1653 out of 1672 proofs were "Automatically Proved," a drastic improvement over traditional manual methods.

Critical Insight: Why This Matters

The most profound takeaway is the 83% to 99% jump in automation. By explicitly defining the OS "World" through an ontology, the automated provers (like SMT solvers) had enough context to solve complex safety properties without human intervention.

Future Outlook: While this work focused on single-core POSs, the methodology is perfectly suited for the pending shift toward multi-core ARINC 653. As complexity grows, the only way to keep "safety-critical" truly safe is to move away from natural language documents toward these types of "executable, verifiable truths."

Conclusion

This work represents the most complete formalization of ARINC 653 to date. It proves that by using ontologies to bridge the gap between human language and formal logic, we can verify the infrastructure of our most critical systems—aircraft, cars, and satellites—at a fraction of the traditional cost.