Conformance Testing as Falsification for Cyber-Physical Systems

Houssam Abbas, Bardh Hoxha, Georgios Fainekos, Jyotirmoy V. Deshmukh, James Kapinski, Koichi UedaarXiv 2014 · OpenReview

TL;DR

This paper proposes a universal definition of conformance for Cyber-Physical Systems (CPS) as a quantifiable "distance" between system behaviors, rather than just checking against specifications. They introduce a method to detect non-conformant behavior by framing it as a falsification problem, leveraging existing tools to measure the degree of conformance.

What Problem Does This Paper Address?

In Model-Based Design (MBD) for CPS, engineers often develop multiple models of varying fidelity or transition from a model to its implementation. A critical challenge is ensuring that these different versions of the system are "conformant" – meaning they behave similarly. Existing methods often rely on formal verification against specifications, which can be insufficient if specifications are incomplete or if the implementation introduces subtle, unintended behaviors. The authors argue that conformance should be a measure of distance between system outputs, and they aim to provide a rigorous, computable way to assess this distance for complex, industrial-scale CPS.

Methods

The core of the paper is the introduction of a universal notion of conformance called (T, J, (τ, ε))-closeness. This metric quantifies the similarity between two system trajectories (outputs over time, potentially with mode changes) by considering differences in both time (τ) and space (ε) over a specified duration (T) and maximum number of jumps (J).

To implement this, they frame conformance testing as a falsification problem. This means they search for a specific input and initial condition that causes the two systems (Model and Implementation) to produce different outputs according to the (T, J, (τ, ε))-closeness metric. They leverage Metric Temporal Logic (MTL) to express this closeness property as a formula.

The actual falsification is performed using existing tools like S-TALIRO, which employs optimization techniques (e.g., Simulated Annealing) to find "falsifying trajectories" – those that violate the conformance property. The paper also proposes a method to measure the degree of conformance by finding the smallest (τ, ε) pair for which the systems are conformant, using a binary search on τ and ε combined with robustness analysis.

Datasets

The paper demonstrates its approach on three systems:

  • A fuel control (FC) system for an automotive application (used as a running example).
  • A SimuQuest Enginuity model of an engine.
  • A Mathworks Simulink model of an automatic transmission.

They also refer to a navigation benchmark (Nav0) for testing application-specific conformance notions. No new datasets were introduced; rather, existing models and benchmarks were used for evaluation.

Key Insights and Ideas

  • Conformance as Distance: The fundamental idea is shifting from "does it meet the spec?" to "how close is it to the original model/ideal behavior?". This is crucial because implementations often have subtle deviations not captured by formal specifications.
  • Universal Conformance Metric: (T, J, (τ, ε))-closeness provides a unified way to define similarity, accounting for both temporal and spatial deviations, and is applicable to various CPS models.
  • Falsification for Conformance: Framing conformance testing as falsification allows the use of powerful existing tools designed for finding counterexamples. This is more practical than trying to prove conformance directly.
  • Quantifiable Degree of Conformance: The ability to find the "best" (τ, ε) pair provides a quantitative measure of how conformant two systems are, enabling informed design trade-offs.
  • Monotonicity for Efficiency: The monotonic nature of the conformance metric with respect to τ and ε allows for efficient search algorithms (like binary search) to find optimal conformance parameters.

Key Results

The paper successfully demonstrates the application of their framework on several examples:

  • They show how to find the tightest (τ, ε) bounds for conformance for the fuel control system and the automatic transmission model. For instance, for the automatic transmission, they found it to be (104, Jм, (5e – 4, ε))-close with ε ∈ [4.8833, 4.8834].
  • They illustrate how their method can falsify application-dependent conformance notions, such as checking for mode convergence within a specific time bound (Example 7 on the Nav0 benchmark). In this case, 12 out of 15 generated implementations were found to be non-conformant.
  • The results show that their approach can detect subtle differences between models and implementations, even when they appear similar at a high level.

Limitations and Future Work

  • Observability: The approach assumes that the behavior (outputs) of both the model and the implementation are observable. For black-box testing of the implementation, this is a reasonable assumption, but it limits direct comparison of internal states.
  • Parameter Tuning: The choice of T, J, τ, and ε can be application-dependent and requires careful selection. While they propose a method to find optimal (τ, ε), the initial choice of T and J might still be heuristic.
  • Mode Switching: While their (T, J, (τ, ε))-closeness metric accounts for jumps (mode switches), the authors suggest future work to explicitly incorporate mode switching into the MTL formula for more nuanced analysis.
  • Time Domains: The paper mentions that future work could account for different time domains between the model and implementation trajectories more comprehensively.
  • Computational Cost: While they use existing tools, falsification can still be computationally intensive, especially for complex systems. The paper notes that the optimization algorithms used (like SA) are stochastic and may require multiple runs.

Summary updated

Abstract

In Model-Based Design of Cyber-Physical Systems (CPS), it is often desirable to develop several models of varying fidelity. Models of different fidelity levels can enable mathematical analysis of the model, control synthesis, faster simulation etc. Furthermore, when (automatically or manually) transitioning from a model to its implementation on an actual computational platform, then again two different versions of the same system are being developed. In all previous cases, it is necessary to define a rigorous notion of conformance between different models and between models and their implementations. This paper argues that conformance should be a measure of distance between systems. Albeit a range of theoretical distance notions exists, a way to compute such distances for industrial size systems and models has not been proposed yet. This paper addresses exactly this problem. A universal notion of conformance as closeness between systems is rigorously defined, and evidence is presented that this implies a number of other application-dependent conformance notions. An algorithm for detecting that two systems are not conformant is then proposed, which uses existing proven tools. A method is also proposed to measure the degree of conformance between two systems. The results are demonstrated on a range of models.
BibTeX
@misc{abbas2014conformance,
  author = {Houssam Abbas and Bardh Hoxha and Georgios Fainekos and Jyotirmoy V. Deshmukh and James Kapinski and Koichi Ueda},
  title = {{Conformance Testing as Falsification for Cyber-Physical Systems}},
  year = {2014},
  eprint = {1401.5200},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.5200},
}
Figure