TL;DR
This paper introduces SOCRaTeS, an automated approach to generate online test oracles for Simulink models of Cyber-Physical Systems (CPS). It addresses the challenge of verifying complex, continuous, and uncertain system behaviors by translating formal requirements into executable Simulink blocks that can detect failures early, quantify severity, and handle uncertainty, significantly reducing test execution time.
What Problem Does This Paper Address?
Developing Cyber-Physical Systems (CPS) involves complex Simulink models that require extensive testing. While automated test input generation is common, creating automated test oracles—mechanisms to verify if a model's output meets its requirements—remains a significant challenge. Existing approaches often struggle with:
- Online execution: The need to stop expensive simulations as soon as a failure is detected.
- Continuous behaviors: Handling time- and magnitude-continuous signals typical in CPS.
- Quantitative feedback: Providing a degree of satisfaction or failure, not just a binary pass/fail.
- Uncertainty: Dealing with models that have uncertain parameters or noisy inputs.
This paper aims to bridge this gap by providing a practical, automated solution for generating test oracles that meet these critical objectives for CPS development.
Methods
The core of the proposed solution, SOCRaTeS, involves several key components:
- Restricted Signals First-Order Logic (RFOL): A novel logic language designed to specify CPS requirements. RFOL is a fragment of Signal First-Order Logic (SFOL) that balances expressiveness for continuous signals with the ability to generate efficient, online test oracles. It defines a quantitative semantics to measure the degree of satisfaction or violation.
- Time and Interval Shifting: A procedure to rewrite RFOL formulas to handle temporal references (e.g., "at time t+2000s") in a way that allows for online checking. This involves shifting time intervals and signal references to ensure that all necessary data is available at the time of evaluation.
- RFOL to Simulink Translation: A set of rules and Simulink blocks that automatically translate RFOL formulas into executable Simulink models. These generated oracles run alongside the system model, checking its outputs in real-time.
- Quantitative Semantics: A defined "diff" function that assigns a fitness value between -1 and 1 to a requirement, indicating the degree of satisfaction (0 to 1) or violation (-1 to 0), with values closer to 1 or -1 indicating stronger satisfaction or more severe violation, respectively.
Datasets
The paper evaluates SOCRaTeS on 11 industrial case studies from the satellite (SatEx) and aerospace (Autopilot) domains, as well as other CPS applications. These case studies provided a total of 98 functional requirements. The SatEx model is highlighted as a complex example involving continuous behaviors, inputs with noise, and uncertain parameters.
Key Insights and Ideas
- Bridging the Logic-Model Gap: The paper demonstrates a practical way to translate formal logic-based requirements (RFOL) directly into executable Simulink blocks, making formal verification more accessible to engineers working with Simulink.
- Online Oracles for Expensive Simulations: The ability of the generated oracles to stop simulations early when a failure is detected is crucial for saving significant computational resources, especially for complex CPS models.
- Quantifying Failure Severity: Moving beyond binary pass/fail, the quantitative fitness measure provides valuable insights into how a system fails, aiding in debugging and risk assessment.
- Handling Uncertainty is Key: The approach's ability to incorporate and reason about uncertain parameters and noisy inputs is a critical step towards realistic CPS verification.
Key Results
- Expressiveness: RFOL was able to express all 98 functional requirements from the 11 industrial case studies without modification.
- Practicality: The effort to write RFOL requirements and generate Simulink oracles was found to be acceptable, with an average oracle generation time of 1.6ms per requirement.
- Time Savings: For large, computationally intensive models like SatEx and Autopilot, online oracles dramatically reduced test execution time.
- For Autopilot, an average time saving of 95.6% (approx. 1.5 minutes) was achieved.
- For SatEx, an average time saving of 96% (approx. 80 minutes) was achieved.
- When uncertainty was involved (SatEx with uncertainty), the time saving increased to 98% (approx. 163 minutes).
- Time Overhead: The generated oracles introduced a small time overhead, averaging 78% for Autopilot and 6% for SatEx, demonstrating the efficiency of the generated Simulink blocks.
Limitations and Future Work
- Limitations:
- The paper acknowledges that while RFOL is expressive, it is a fragment of SFOL and might not capture all possible complex temporal properties.
- The translation process assumes that the Simulink model and the generated oracle can be executed by the same Simulink solver.
- Future Work:
- The authors suggest extending RFOL to handle more complex temporal operators and potentially integrating it with other formalisms.
- Further exploration of different quantitative semantics for "diff" functions could provide more nuanced fitness measures.
- The paper hints at the potential for using these oracles for test case prioritization and selection.
Summary updated