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:
- Abstraction: Construct a simplified model using a set of predicates.
- Verification: Check the abstract model for paths to unsafe states.
- 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.
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.
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