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:
- Formal Modeling: Creating a timed automata model of the real-time system.
- Formal Verification: Using a model checker (UPPAAL) to verify critical timing properties on the timed automata model.
- Code Synthesis: Generating implementation code from the verified model.
- 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.
- Timing Tolerance Identification: Determining a "timing tolerance" value ($\Delta$) based on measured deviations. This $\Delta$ represents the maximum acceptable delay.
- 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.
- Model Revision: Reflecting these code modifications back into the formal model by updating the guards.
- 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