Abstraction Techniques for Symbolic Model Checking of Infinite-state Discrete and Continuous Systems - Institut Polytechnique de Paris Access content directly
Habilitation À Diriger Des Recherches Year : 2024

Abstraction Techniques for Symbolic Model Checking of Infinite-state Discrete and Continuous Systems

Abstract

The design of safety- and mission-critical software systems (used in, e.g., avionics, automotive, medical devices, . . . ) requires the development of automated tools, such as Model Checking, for analyzing all the possible executions and for determining if the system is correct. An existing problem is to extend model checking algorithms to analyze efficiently “expressive” systems that, for example, can have an infinite state space (e.g., software working on real or integer numbers) or mix discrete-time and continuous-time (e.g., control software interacting with the physical environment). In this habilitation thesis, we summarize some of the approaches the author contributed to for solving the verification problem for different families of infinite-state systems. First, we focus on the Verification Modulo Theory (VMT) problem, that is model checking infinite-state transition systems expressed with first-order theories. Then, we focus on the problem of verifying hybrid systems, where a discrete-time system interacts with a continuous-time system expressed with Ordinary Differential Equations (ODEs). In both cases, we consider the invariant and the liveness model checking problems. We first describe the symbolic algorithm IC3-IA that solves the VMT problem using abstraction to cope with the infinite-state space challenge. The algorithm is general enough to work for a wide set of first-order theories and addresses the challenge of exploring efficiently a space of exponentially large abstract transition systems (i.e., a Counter-Example Guided Abstraction Refinement loop). We also extend such invariant verification algorithms to prove liveness properties via a liveness-to-safety reduction. Then, we investigate the use of abstraction as a tool to obtain a purely discrete transition system to over-approximate a hybrid system expressed with non-linear ODEs (i.e., a reduction to a VMT problem). We first show how to efficiently model check qualitative abstractions (i.e., abstractions defined by the signs of a set of polynomials), tackling the exponential state-space explosion with similar ideas to IC3-IA, and then we show how to scale the computation of relational abstractions (i.e., an approximation of the continuous system’s trajectories) for non-linear dynamical systems exploiting the variables dependencies in the ODEs.
Fichier principal
Vignette du fichier
main.pdf (1.21 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

tel-04608760 , version 1 (11-06-2024)

Licence

Identifiers

  • HAL Id : tel-04608760 , version 1

Cite

Sergio Mover. Abstraction Techniques for Symbolic Model Checking of Infinite-state Discrete and Continuous Systems. Logic in Computer Science [cs.LO]. Institut Polytechnique de Paris, 2024. ⟨tel-04608760⟩
65 View
18 Download

Share

Gmail Mastodon Facebook X LinkedIn More