Modeling and analysis of hybrid systems

This thesis discusses the modeling and analysis of hybrid systems. Hybrid modeling is an appropriate modeling framework for embedded systems and other real-world applications bridging the gap between continuous dynamical systems and discrete event systems. First, this thesis presents the hybrid systems modeling language and toolkit CHARON. In the following, this thesis then addresses the analysis of hybrid systems using model checking techniques. The goal of a reachability analysis is to either be able to discover bugs in a hybrid system model or to be able to guarantee that the model is safe with respect to a certain property. This thesis presents algorithms and tools for reachability analysis of hybrid systems by combining the notion of counter-example guided predicate abstraction with recent techniques for approximating the set of reachable states of linear systems using polyhedra. Predicate abstraction has emerged to be a powerful technique for extracting finite-state models from infinite-state discrete programs. Given a hybrid system and a set of predicates, the finite discrete quotient represented by this abstraction is considered. The tool performs an on-the-fly exploration of the abstract system. The success of this scheme crucially depends on the choice of the predicates used for abstraction. Such predicates are identified automatically by analyzing spurious counter-examples generated by the search in the abstract state-space. The basic techniques for guided search in the abstract state-space and techniques to discover new predicates, that will rule out closely related spurious counter-examples, are presented. Additionally, the completeness of the abstraction-based verification strategy is addressed, and it is shown that predicate abstraction of hybrid systems can be used to prove bounded safety. The thesis then describes the integration of the verifier into the overall CHARON framework, and also discusses a variety of case studies that have been verified using this framework. The case studies presented here include, amongst others, a simple thermostat controller, Fischer\u27s mutual exclusion protocol, a navigational obstacle avoidance protocol, and an automotive adaptive cruise controller. The thesis concludes with a brief overview of ongoing work and possible future research directions