Proving Abstractions of Dynamical Systems through Numerical Simulations

Sayan Mitra

Abstract

A key question that arises in rigorous analysis of cyberphysical systems under attack involves establishing whether or not the attacked system deviates significantly from the ideal allowed behavior. This is the problem of deciding whether or not the ideal system is an abstraction of the attacked system. A quantitative variation of this question can capture how much the attacked system deviates from the ideal. Thus, algorithms for deciding abstraction relations can help measure the effect of attacks on cyberphysical systems and to develop attack detection strategies. In this paper, we present a decision procedure for proving that one nonlinear dynamical system is a quantitative abstraction of another. Directly computing the reach sets of these nonlinear systems are undecidable in general and reach set over-approximations do not give a direct way for proving abstraction. Our procedure uses (possibly inaccurate) numerical simulations and a model annotation to compute tight approximations of the observable behaviors of the system and then uses these approximations to decide on abstraction. We show that the procedure is sound and that it is guaranteed to terminate under reasonable robustness assumptions.

Introduction

In Cyber-Physical Systems (CPS) such as autonomous vehicles or smart grids, security analysis requires understanding how physical behaviors change under adversarial conditions. Researchers often use abstractions—simplified models—to represent complex systems. If Model B is an abstraction of Model A, every behavior of A must be representable by B. However, for nonlinear dynamical systems governed by complex differential equations, proving this relationship is notoriously difficult because computing the exact "reach set" (the set of all possible states a system can reach) is generally undecidable.

Defining c-Abstraction

This paper introduces a formal, quantitative measure called c-abstraction. Instead of requiring identical behavior, the authors ask if every trace of a "concrete" system (e.g., a system under attack) stays within a distance c of some trace in an "abstract" (ideal) model. Formally, $A_1 \preceq_{c,T} A_2$ indicates that system $A_2$ is a $c$-abstraction of $A_1$ up to time $T$. This metric allows security analysts to quantify the impact of an attack based on how much it causes a system to deviate from its intended behavior.

The Static-Dynamic Analysis Framework

The proposed method bridges the gap between theoretical models and practical simulations through a "static-dynamic" approach:

  • Numerical Simulations: The procedure uses standard, potentially inaccurate numerical simulations as the foundation for the proof.
  • Discrepancy Functions: To account for the gap between a single simulation and the entire set of possible initial states, the authors use "discrepancy functions." These mathematical tools provide an upper bound on how much two trajectories will diverge over time based on their starting distance.
  • Pipes: By "bloating" simulation traces using these discrepancy functions, the algorithm creates "pipes"—sequences of polyhedral segments that represent sets of bounded trajectories.
Visualization of a 'pipe' representing a set of trajectories for a 2D nonlinear dynamical system.

Algorithm and Soundness

The core of the research is a semi-decision procedure (Algorithm 1). It partitions the set of initial states, runs simulations, and constructs pipes for both the concrete and abstract systems. It then checks for containment: are the pipes of the concrete system contained within the (slightly larger) pipes of the abstract system?

Key theoretical results include:

  • Soundness: If the algorithm returns "c-abstraction," the relationship is guaranteed to hold. If it returns a counter-example, the systems are definitively further than c apart.
  • Termination: The procedure is guaranteed to terminate as long as the systems are "robustly" similar or different—meaning they do not sit exactly on the boundary of the distance c.
  • Infinite Horizons: An extension (Algorithm 2) uses fixpoint iteration to compute over-approximations of reach sets for infinite time horizons.

Conclusion and Future Work

By shifting the focus from analytical solutions of ODEs to the "bloating" of numerical simulations, this framework provides a rigorous tool for CPS verification. While currently limited to autonomous, deterministic systems, the authors suggest future extensions to switched systems and hybrid models that combine continuous physics with discrete software logic, which are more representative of real-world industrial applications.

Summary updated

Abstract

A key question that arises in rigorous analysis of cyberphysical systems under attack involves establishing whether or not the attacked system deviates significantly from the ideal allowed behavior. This is the problem of deciding whether or not the ideal system is an abstraction of the attacked system. A quantitative variation of this question can capture how much the attacked system deviates from the ideal. Thus, algorithms for deciding abstraction relations can help measure the effect of attacks on cyberphysical systems and to develop attack detection strategies. In this paper, we present a decision procedure for proving that one nonlinear dynamical system is a quantitative abstraction of another. Directly computing the reach sets of these nonlinear systems are undecidable in general and reach set over-approximations do not give a direct way for proving abstraction. Our procedure uses (possibly inaccurate) numerical simulations and a model annotation to compute tight approximations of the observable behaviors of the system and then uses these approximations to decide on abstraction. We show that the procedure is sound and that it is guaranteed to terminate under reasonable robustness assumptions.
BibTeX
@misc{mitra2014proving,
  author = {Sayan Mitra},
  title = {{Proving Abstractions of Dynamical Systems through Numerical Simulations}},
  year = {2014},
  eprint = {1401.1313},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.1313},
}
Figure