Formally Verified C Code Generation from Hybrid Communicating Sequential Processes

Shuling Wang, Zekun Ji, Bohua Zhan, Xiong Xu, Qiang Gao, Naijun Zhan

TL;DR

This paper presents a method for automatically generating formally verified C code from hybrid systems modeled in HCSP. This is crucial for safety-critical cyber-physical systems, ensuring that the generated code accurately reflects the system's formal specification, bridging the gap between high-level models and executable code.

What Problem Does This Paper Address?

Developing safe and reliable cyber-physical systems (CPSs) is challenging due to their complexity and the need for formal verification. Model-Driven Development (MDD) offers a promising approach, but automatically generating verified code from formal hybrid system models remains a significant hurdle. Specifically, transforming models that combine continuous dynamics (like differential equations) with discrete events and communication into efficient, verifiable C code is difficult. Key challenges include accurately discretizing continuous behavior, handling interrupts from discrete events, and synchronizing concurrent processes in C using low-level primitives like mutexes, which differ from the high-level handshake model in HCSP.

Methods

The authors propose a code generation algorithm that transforms HCSP models into C code using POSIX pthreads for concurrency. The core of their approach involves:

  • Discretization of Continuous Dynamics: Ordinary Differential Equations (ODEs) are discretized using a 4-stage Runge-Kutta method to approximate continuous evolution.
  • Handling Interrupts: A mechanism is developed to handle discrete events that preempt continuous evolution.
  • Synchronization in C: HCSP's synchronized communication is translated into C using mutexes and condition variables. This involves introducing auxiliary variables and functions to manage thread states, local and global clocks, and channel synchronization.
  • Formal Verification: The correctness of the code generation is established through formal methods. They define a formal semantics for a subset of C with POSIX threads and build transition system models for both HCSP and generated C programs. An "approximate bisimulation" relation is used to prove that the generated C code behaves equivalently to the original HCSP model within specified time and value tolerances. This bisimulation is proven in two steps: HCSP to its discretized version, and then the discrete HCSP to the generated C code.

Datasets

Not discussed in the paper. The case study uses a model for an Automatic Cruise Control System (ACCS) from a previous work.

Key Insights and Ideas

  • Bridging the Abstraction Gap: The paper demonstrates a concrete method to bridge the significant gap between high-level, formally verified hybrid system models (HCSP) and low-level, executable C code.
  • Approximate Bisimulation for Verification: Using approximate bisimulation is key to proving correctness, acknowledging that discretization inherently introduces small errors that must be bounded.
  • Concurrency Translation Challenges: The paper highlights the fundamental difference between HCSP's synchronized communication and C's interleaving concurrency model, and how this requires careful translation using low-level synchronization primitives.
  • Robustness is Key: The concept of "robustly safe" HCSP processes is introduced, emphasizing that hybrid systems must tolerate small errors introduced by discretization to ensure predictable behavior.

Key Results

The paper presents a formal framework and an algorithm for generating C code from HCSP. They provide a detailed proof of correctness using approximate bisimulation. The approach is evaluated on a realistic Automatic Cruise Control System (ACCS) model. Simulations show that the generated C code's execution results are very close to the simulation of the original HCSP model, with a small average relative error (0.138%). This is contrasted with other code generation approaches where such formal guarantees are not provided.

Limitations and Future Work

  • Complexity of Robustness Analysis: The authors note that computing the robustly safe parameters (δ, ε) for HCSP processes can be challenging.
  • Code Length and Efficiency: The generated C code is longer and potentially less efficient than code generated directly from graphical models, though it offers formal correctness guarantees.
  • Future Work: The authors suggest applying their approach to more practical case studies in industry and exploring more advanced techniques for robustness analysis.

Summary updated

BibTeX
@inproceedings{wang2024formally,
  author = {Shuling Wang and Zekun Ji and Bohua Zhan and Xiong Xu and Qiang Gao and Naijun Zhan},
  title = {{Formally Verified C Code Generation from Hybrid Communicating Sequential Processes}},
  booktitle = {ICCPS},
  year = {2024},
  doi = {10.1109/iccps61052.2024.00018},
}

Loading related content...

Figure