A Safety-Assured Development Approach for Real-Time Software

Eunkyoung Jee, Shaohui Wang, Jeong-Ki Kim, Jaewoo Lee, Oleg Sokolsky, Insup Lee

TL;DR

This paper introduces a novel approach to developing safety-critical real-time software, like pacemakers, by integrating formal modeling with measurement-based timing analysis. It bridges the gap between theoretical timing guarantees in formal models and their practical realization in actual code, ensuring that critical timing properties are maintained even with implementation delays.

What Problem Does This Paper Address?

Developing safety-critical real-time systems, such as medical devices or avionics, demands rigorous guarantees that the software will meet strict timing deadlines. Violating these timing properties can have catastrophic consequences, leading to system failure or even loss of life. While formal methods like timed automata and model checking can verify these timing properties on abstract models, ensuring these guarantees hold in the final, compiled code is a significant challenge. This is because real-world implementations introduce unavoidable delays (e.g., instruction execution time, communication overhead) that are often ignored in idealized formal models (like the synchrony hypothesis). The paper addresses this gap by proposing a method to systematically transfer timing assurances from a formal model to the implementation, even when the implementation deviates from the ideal.

Methods

The core of the paper's contribution is a safety-assured development approach that combines Model-Driven Development (MDD) with measurement-based timing analysis. The process involves:

  1. Formal Modeling: Creating a timed automata model of the real-time system.
  2. Formal Verification: Using a model checker (UPPAAL) to verify critical timing properties on the timed automata model.
  3. Code Synthesis: Generating implementation code from the verified model.
  4. Measurement-Based Timing Analysis: Executing the generated code on a target platform and measuring actual execution times. This step identifies timing deviations from the model's assumptions.
  5. Timing Tolerance Identification: Determining a "timing tolerance" value ($\Delta$) based on measured deviations. This $\Delta$ represents the maximum acceptable delay.
  6. Code Revision: Modifying the implementation code by adjusting guards (conditions) to incorporate the timing tolerance ($\Delta$), effectively "relaxing" them to account for real-world delays.
  7. Model Revision: Reflecting these code modifications back into the formal model by updating the guards.
  8. Re-verification: Re-running model checking on the modified model to ensure all properties are still satisfied. If not, the process iterates.

The authors demonstrate this approach using two code generation schemes: single-threaded and multi-threaded implementations of a VVI mode pacemaker.

Datasets

Not discussed in the paper. The "dataset" in this context is the system specification for a pacemaker provided by Boston Scientific [10] and the synthesized code from the timed automata model.

Key Insights and Ideas

  • Bridging the Model-Code Gap: The most significant insight is the practical methodology for bridging the gap between formal timing guarantees and real-world implementation delays. The concept of a "timing tolerance" ($\Delta$) is crucial here.
  • Iterative Refinement: The iterative process of analyzing code, revising it with timing tolerances, and then updating the model for re-verification is key to maintaining safety assurances.
  • Impact of Implementation Details: The paper highlights that even simple timing properties (like "event must occur within X time") can be violated in practice due to execution delays, necessitating explicit handling of these delays.
  • Two-Way Mapping: The importance of not just analyzing the code but also reflecting the code's behavior back into the formal model for re-verification is a critical aspect of ensuring the entire development process is safety-assured.
  • Single vs. Multi-threaded: While both approaches were tested, the multi-threaded approach showed more time uncertainty, though the proposed method could still be applied.

Key Results

The paper successfully applied its safety-assured development approach to a VVI mode pacemaker case study.

  • Single-Threaded: Initially, timing properties like PropLRI (Lower Rate Limit) and PropHRI (Hysteresis Rate Limit) were violated in the generated code. After identifying a timing tolerance ($\Delta$) of 2ms and applying it to the code (by adjusting guards), these properties were satisfied. Re-verification of the modified model confirmed that all properties remained satisfied.
  • Multi-Threaded: Similar violations were observed. Applying a timing tolerance of 2ms also resolved these violations, and the modified model passed re-verification.
  • PropVRP (Ventricular Refractory Period): This property, which requires a minimum time duration, was consistently satisfied in both code generation schemes without modification. This suggests that properties requiring minimum delays are less susceptible to implementation overhead.

Limitations and Future Work

  • Manual Model Revision: The process of reflecting code changes back to the model is currently manual. Automating this backward mapping would significantly improve scalability.
  • Timing Tolerance Value: While the approach successfully found a timing tolerance ($\Delta$), the paper acknowledges that in some worst-case scenarios, the smallest required $\Delta$ might exceed specification limits, indicating potential issues with the underlying code generation scheme itself.
  • Complexity of Timing Properties: The paper focused on two types of timing properties (greater-than-or-equal-to and less-than-or-equal-to). More complex timing properties might require further investigation.
  • Instrumentation Overhead: While the measured overhead didn't impact the specific properties in this case study, the authors note that reducing instrumentation overhead is desirable for tighter $\Delta$ values.
  • Scalability: Applying this approach to more complex real-time systems may require more automated tools for model synthesis and revision.
  • Future Work: The authors plan to conduct theoretical analysis, compare different code generation schemes, and construct assurance cases for the pacemaker software to further validate the methodology's impact. They also suggest exploring more rigorous timing analysis techniques (like WCET analysis) for finding more precise timing tolerances.

Summary updated

Abstract

Guaranteeing timing properties is an important issue as we develop safety-critical real-time systems such as cardiac pacemakers. We present a safety assured development approach of real-time software using a pacemaker as our case study. Following the model-driven development techniques, measurement-based timing analysis is used to guarantee timing properties in implementation as well as in the formal model. Formal specification with timed automata is checked with respect to timing properties by model checking technique and is transformed into implementation systematically. When timing properties may be violated in the implementation due to timing delay, it is suggested to measure the time deviation and reflect it to the code explicitly by modifying guards. The model is altered according to the modifications in the code. These changes of the code and the model are considered safe if all the properties are still satisfied by the modified model in re-performed model checking. We demonstrate how the suggested approach can be applied to single-threaded and multi-threaded versions of implementation. This approach can provide developers with a useful time-guaranteeing technique applicable to several code generation schemes without imposing many restrictions.
BibTeX
@inproceedings{jee2010safety,
  author = {Eunkyoung Jee and Shaohui Wang and Jeong-Ki Kim and Jaewoo Lee and Oleg Sokolsky and Insup Lee},
  title = {{A Safety-Assured Development Approach for Real-Time Software}},
  booktitle = {RTCSA},
  year = {2010},
  doi = {10.1109/rtcsa.2010.42},
}

Loading related content...

Figure