Formal Verification of Robustness Properties of Hybrid Control Systems

Cyber-physical systems (CPSs) consist of complex systems that combine control, computation and communication to achieve sophisticated functionalities as in autonomous driving in driverless cars and automated load balancing in smart grids. The safety criticality of these systems demands strong guarantees about their correct functioning. Formal verification is an area of computer science that deals with rigorous and automated methods for correctness analysis based on mathematical models of systems and correctness specifications. In this talk, we present an overview of our work on formal verification techniques for cyber-physical systems analysis using the framework of hybrid systems. Hybrid systems capture an important feature of CPSs, namely, mixed discrete-continuous behaviors that arise due to the interaction of complex digital control software (discrete elements) with physical systems (continuous elements). We will focus on the formal verification of a fundamental property in control design, namely, stability. Stability is a robustness property that capture notions such as small perturbations to the initial state or input to a system result in only small variations in the behavior of the system. We will present a novel algorithmic approach to stability analysis based on model-checking and abstraction-refinement techniques. We highlight the technical challenges in the development of an algorithmic framework for stability analysis owing to the robustness aspect. We will present experimental results using our tool AVERIST (Algorithmic VERifier for STability), that illustrate the practical benefits of the algorithmic approach as compared to well-known deductive methods for automated verification of stability based on Lyapunov functions.Finally, we will present some future research directions including automated design of hybrid control systems and formal analysis of hybrid systems in the presence of uncertainties