Visible to the public Proving Abstractions of Dynamical Systems Through Numerical Simulations

TitleProving Abstractions of Dynamical Systems Through Numerical Simulations
Publication TypeConference Paper
Year of Publication2014
AuthorsMitra, Sayan
Conference NameProceedings of the 2014 Symposium and Bootcamp on the Science of Security
Conference LocationRaleigh, NC, USA
ISBN Number978-1-4503-2907-1
Keywordsabstraction, ACM CCS, adversary, CPS Technologies, cryptography, cyberphysical systems, Foundations, Mathematical Foundations of Cryptography, science of security, simulation, Static-Dynamic Analysis of Security Metrics for Cyber-Physical Systems, Systems Engineering, Validation and Verification, verification

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.

Citation KeyMitra:2014:PAD:2600176.2600188