We propose a methodology for the automatic verification of safety properties of controllers based on dynamical systems, such as those typically used in avionics. In particular, our focus is on proving stability properties of software implementing linear and some non-linear controllers. We develop an abstract interpretation framework that follows closely the Lyapunov methods used in proofs at the model level and describe the corresponding abstract domains, which for linear systems consist of ellipsoidal constraints. These ellipsoidal domains provide abstractions for the values of state variables and must be combined with other domains that model the remaining variables in a program. Thus, the problem of automatically assigning the right type of abstract domain to each variable arises. We provide an algorithm that solves this classification problem in many practical cases and suggest how it could be generalized to more complicated cases. We then find a fixpoint by solving a matrix equation, which in the linear case is just the discrete Lyapunov equation. Contrary to most cases in software analysis, this fixpoint cannot be reached by the usual iterative method of propagating constraints until saturation and so numerical methods become essential. Finally, we illustrate our methodology with several examples.
The study of stability of controllers at the theoretical level is a very mature subject, especially for linear systems. Two techniques are available in that case: eigenvalue analysis and Lyapunov methods. While eigenvalue analysis is more straightforward, Lyapunov methods generalize better to non-linear cases @cite_5 . Thus, most recent work uses the latter. Lyapunov methods give way to the study of propagation of ellipsoids such as that presented in this paper.
@cite_5
2023285936
Introduction. Non-linear Differential Equations. Second-Order Systems. Approximate Analysis Methods. Lyapunov Stability. Input-Output Stability. Differential Geometric Methods. Appendices: Prevalence of Differential Equations with Unique Solutions, Proof of the Kalman-Yacubovitch Lemma and Proof of the Frobenius Theorem.