Evaluating model testing and model checking for finding requirements violations in Simulink models

Shiva Nejati, Khouloud Gaaloul, Claudio Menghi, Lionel C. Briand, Stephen Foster, David Wolfe

TL;DR

This paper presents an empirical study comparing model testing (MT) and model checking (MC) for finding requirement violations in industrial Simulink models. The authors found that while MC is faster at proving correctness, MT is more effective at discovering violations, especially in complex models. They conclude that combining both approaches offers the most comprehensive verification strategy.

What Problem Does This Paper Address?

Cyber-Physical Systems (CPS) are increasingly complex, and ensuring their reliability is paramount. Simulink is a widely used tool for modeling these systems, but verifying their correctness against functional safety requirements is challenging. Two primary approaches exist: model testing (executing models with sampled inputs to find failures) and model checking (exhaustively verifying models against formal properties). However, industrial Simulink models often involve continuous dynamics, hybrid systems, and non-algebraic functions, which can make traditional model checking difficult or impossible. This paper addresses the need for a systematic comparison of MT and MC on realistic industrial CPS models to understand their respective strengths, weaknesses, and how they can be best combined.

Methods

The authors developed an industrial Simulink model benchmark from a major aerospace and defense company. They then applied two main verification techniques:

  • Model Testing (MT): They employed a search-based testing framework using a Hill Climbing algorithm. This algorithm iteratively refines test inputs to find those that violate requirements. Fitness functions for the search were derived from Signal Temporal Logic (STL) specifications using a robustness metric.
  • Model Checking (MC): They used QVTrace, a commercial SMT-based model checker for Simulink. QVTrace translates Simulink models and requirements into a format suitable for Satisfiability Modulo Theories (SMT) solvers. The paper also discusses the limitations of MC, particularly its difficulty with continuous and hybrid systems, and the use of Bounded Model Checking (BMC) when exhaustive verification fails.

Datasets

The paper introduces a novel industrial Simulink model benchmark developed by a major aerospace and defense company. This benchmark consists of eleven Simulink models representative of CPS behavioral models in the aerospace and defense sector. Each model is accompanied by natural language requirements and intentionally introduced faults that violate these requirements. The authors also provide this benchmark, along with their STL translations and implementation details, as a replication package online.

Key Insights and Ideas

  • Complementarity is Key: The most significant insight is that model testing and model checking are not competing but complementary techniques. MT excels at finding violations, especially in complex models where MC struggles, while MC is efficient at proving correctness when applicable.
  • Industrial Models Pose Challenges for MC: Real-world industrial Simulink models, particularly those with continuous dynamics, non-algebraic functions, and machine learning components, often prove too complex for current SMT-based model checkers. This leads to inapplicability or reliance on bounded verification.
  • MT Scales Better, But is Slower: Model testing, due to its black-box nature, scales better to larger and more complex models. However, it is computationally expensive, requiring numerous model simulations.
  • The Value of a Robust Benchmark: The use of a realistic, industry-provided benchmark was crucial for drawing meaningful conclusions about the practical effectiveness of these verification techniques.

Key Results

  • Violation Discovery: Out of 92 requirements, MT identified 40 violations, while MC found only 23. Notably, all violations found by MC were also found by MT. MT discovered 17 violations that MC could not.
  • Correctness Proofs: MC was able to exhaustively prove correctness for 41 requirements.
  • Combined Power: Together, MT and MC were able to either prove or find violations for 81 out of 92 requirements, leaving only 11 inconclusive.
  • Performance: MC was significantly faster when it could conclusively prove or violate a requirement (average 0.63s for proving, 2.19s for violating) compared to MT (average 5.8min per run). However, MC's performance degraded significantly for complex models like Autopilot.
  • BMC Limitations: For requirements where exhaustive MC failed, BMC could only verify up to a certain bound, and MT often found violations beyond these bounds.

Limitations and Future Work

  • MC Inapplicability: The paper highlights that MC may fail to analyze certain CPS Simulink models, especially those with continuous dynamics, due to complexity. Simplifications to make models amenable to MC can be costly and may compromise analysis precision.
  • MT Efficiency: While effective, MT is computationally expensive. The authors suggest parallelization and exploring more efficient search heuristics and surrogate models to improve its performance.
  • Search Heuristic Guidance: There's a need for more research to understand which search heuristics are best suited for different types of models in MT, and how to provide engineers with better guidance on selecting and using them.
  • Future Work: The authors suggest further empirical research to compare MT and MC in different contexts to better identify their strengths and limitations. They also propose combining MC and MT as the most effective approach for Simulink verification, suggesting starting with MC and then using MT for models or requirements that MC cannot handle.

Summary updated

BibTeX
@inproceedings{nejati2019evaluating,
  author = {Shiva Nejati and Khouloud Gaaloul and Claudio Menghi and Lionel C. Briand and Stephen Foster and David Wolfe},
  title = {{Evaluating model testing and model checking for finding requirements violations in Simulink models}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2019},
  doi = {10.1145/3338906.3340444},
}
Figure