Abstraction and Counterexample-Guided Refinement in Model Checking of Hybrid Systems

Edmund M. Clarke, Ansgar Fehnker, Zhi Han, Bruce H. Krogh, Joël Ouaknine, Olaf Stursberg, Michael TheobaldInt. J. Found. Comput. sci 2003 · DOI

TL;DR

This paper introduces a novel counterexample-guided abstraction refinement (CEGAR) technique for verifying safety properties of hybrid systems. By iteratively refining abstract models based on counterexamples, the method efficiently handles the complexity of infinite-state hybrid systems, offering significant advantages over existing approaches.

What Problem Does This Paper Address?

Hybrid systems, which combine continuous and discrete dynamics, are increasingly used in safety-critical applications like embedded controllers. However, verifying their properties is challenging due to their infinite state spaces. Traditional model checking struggles with this, and existing abstraction techniques often require global refinement when an abstraction is insufficient. This paper addresses the need for a more efficient and targeted refinement strategy for hybrid systems, specifically for verifying safety properties.

Methods

The core contribution is a counterexample-guided abstraction refinement (CEGAR) approach adapted for hybrid systems. The process involves:

  1. Initial Abstraction: Creating a simplified, finite-state abstract model of the hybrid system.
  2. Model Checking: Using standard model checking on the abstract model to check for safety properties.
  3. Counterexample Generation: If the property is violated, a counterexample (a path in the abstract model leading to an unsafe state) is generated.
  4. Validation: Determining if the abstract counterexample corresponds to a genuine behavior in the concrete hybrid system. This involves computing reachable states in the continuous state space.
  5. Refinement: If the counterexample is spurious (not a real system behavior), the abstract model is refined. This is done by "splitting" abstract states or "purging" spurious transitions, effectively adding more detail to the abstraction to exclude the false counterexample.

A key novelty is the flexible use of varying degrees of accuracy in computing successor states for validation and refinement. This allows for a trade-off between computational cost and precision, making the process more efficient. The paper also introduces specific techniques for state splitting and transition purging tailored for hybrid systems.

Datasets

Not discussed in the paper. The paper uses examples like the "MU-puzzle" and a car steering controller for illustration and experimental evaluation.

Key Insights and Ideas

  • CEGAR for Hybrid Systems: The paper successfully extends the CEGAR framework, which has proven effective for finite-state systems, to the more complex domain of hybrid systems.
  • Flexible Successor Computation: The ability to use over-approximations of successor states with varying accuracy is crucial. This allows for faster refutation of counterexamples when possible, and more precise refinement when necessary, balancing efficiency and correctness.
  • Targeted Refinement: Instead of globally refining the entire abstraction, the method focuses on refining specific parts of the abstract model that are implicated by a counterexample. This makes the process more efficient and scalable.
  • Spurious Counterexamples as Guides: The paper highlights how spurious counterexamples are not just noise but valuable information that directly guides the refinement process, leading to more accurate abstract models.
  • Fragment-Based Refinement: Considering fragments of counterexamples (shorter paths) can significantly speed up verification by potentially refuting a counterexample earlier and avoiding the introduction of new, complex counterexamples.

Key Results

  • The proposed INFINITE-STATE-CEGAR algorithm was implemented and tested on examples like a car steering controller and an adaptive cruise control system.
  • Experimental results showed significant speedups compared to existing methods. For the car steering example, one variant of the algorithm achieved a 9x speedup over a baseline approach.
  • For the adaptive cruise control system, the proposed method was considerably faster than CheckMate, with one variant achieving a 17x speedup and producing a more compact abstraction.
  • The method demonstrated its ability to handle non-linear dynamics, which are problematic for some other verification tools.

Limitations and Future Work

  • Termination Guarantee: The paper acknowledges that termination of the CEGAR algorithm cannot be guaranteed for all hybrid systems, as the number of states in the concrete model can be infinite, and a finite abstract model for verification might not always exist.
  • Heuristics for Refinement: The choice of which over-approximation technique to use and how to combine them involves heuristics, and finding optimal strategies can be challenging.
  • Future Work: The authors suggest that further research could explore more efficient methods for computing successor states and potentially develop more sophisticated heuristics for selecting refinement strategies. The paper also hints at the possibility of using under-approximations to prove the existence of counterexamples when over-approximations fail to refute spurious ones.

Summary updated

BibTeX
@article{clarke2003abstraction,
  author = {Edmund M. Clarke and Ansgar Fehnker and Zhi Han and Bruce H. Krogh and Joël Ouaknine and Olaf Stursberg and Michael Theobald},
  title = {{Abstraction and Counterexample-Guided Refinement in Model Checking of Hybrid Systems}},
  journal = {Int. J. Found. Comput. sci},
  year = {2003},
  doi = {10.1142/s012905410300190x},
}
Figure