Neural Policy Safety Verification via Predicate Abstraction: CEGAR

Marcel Vinzent, Siddhant Sharma, Jörg HoffmannAAAI 2023 · DOI

Introduction

As neural networks (NNs) are increasingly deployed in safety-critical control systems, such as robotics and logistics, the need for formal safety guarantees becomes paramount. The safety verification problem asks whether a system, starting from a defined initial set of states, can ever reach a "forbidden" unsafe region under the control of a neural policy. Traditional methods like Bounded Model Checking (BMC) often suffer from "formula explosion" as they attempt to analyze entire execution paths simultaneously. This paper presents an automated approach to safety verification by extending Counterexample-Guided Abstraction Refinement (CEGAR) to Policy Predicate Abstraction (PPA).

Policy Predicate Abstraction and the CEGAR Loop

PPA simplifies the state space by using logical conditions, or predicates, to group states with similar behaviors. Unlike BMC, PPA focuses on local transitions, significantly reducing the complexity for SMT solvers. However, manually defining these predicates is labor-intensive. The authors automate this process using a CEGAR loop:

  1. Abstraction: Construct a simplified model using a set of predicates.
  2. Verification: Check the abstract model for paths to unsafe states.
  3. Refinement: If an unsafe path is found, determine if it is "real" or "spurious." Spurious paths, caused by an over-simplified abstraction, are used to generate new predicates that refine the model.
Comparison of standard (STD) and policy-induced (POL) transitions. In POL, a transition only occurs if the neural network policy selects the corresponding action.

Addressing Policy-Induced Spuriousness

A key innovation of this work is identifying and resolving spurious transitions unique to neural policies. In standard abstraction, a transition is spurious if it violates the underlying system physics. In PPA, a transition can also be spurious if the NN policy would never actually select that action in the given state. The authors propose two refinement strategies:

  • Concretization Exclusion (CE): Directly excludes the spurious transition from the abstract model.
  • Witness Splitting (WS): Refines the abstraction by splitting the abstract state into smaller regions where the policy's decision is consistent.

Empirical results indicate that Witness Splitting (WS) is the more robust and scalable refinement method.

Experimental Results and Performance

The proposed tool was evaluated on planning benchmarks including Blocksworld, SlidingTiles, and Transport, using policies trained via Q-learning. Notably, this tool was the only one capable of formally proving safety; state-of-the-art model checkers like nuXmv either timed out or could only identify unsafe paths.

Verification time vs. percentage of maximal predicates for different NN sizes. The plot illustrates the scalability and the point where state-space explosion begins to impact performance.

The inclusion of a Hamming distance heuristic further accelerated the search for counterexamples, making the tool orders of magnitude faster than general-purpose competitors on benchmarks like "Transport."

Conclusion and Future Work

By automating predicate generation within a CEGAR framework, this work significantly advances the state-of-the-art in neural policy verification. While currently limited to discrete state spaces and box-constraint predicates, future extensions could include continuous control systems and more complex decision boundaries, such as those found in Graph Neural Networks.

Summary updated

BibTeX
@inproceedings{vinzent2023neural,
  author = {Marcel Vinzent and Siddhant Sharma and Jörg Hoffmann},
  title = {{Neural Policy Safety Verification via Predicate Abstraction: CEGAR}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i12.26772},
}
Figure