Formal Verification of Neural Network Controlled Autonomous Systems

Xiaowu Sun, Haitham Khedr, Yasser Shoukry

Abstract

As autonomous systems like drones and self-driving cars increasingly rely on Deep Neural Networks (DNNs) for processing high-dimensional sensor data such as LiDAR, ensuring their safety becomes a critical challenge. Traditional simulation-based testing cannot guarantee the absence of fatal corner cases. This paper introduces a formal verification framework that bridges the gap between continuous robot dynamics and discrete logical proofs. By partitioning the workspace into "imaging-adapted sets" where LiDAR sensing behaves linearly, we transform the complex verification problem into a solvable finite state abstraction. Using Satisfiability Modulo Convex (SMC) solvers enhanced with reachability-based pruning, we demonstrate the ability to verify safety properties for neural network controllers with up to 702 neurons in complex environments.

Introduction

The deployment of AI in physical machines necessitates rigorous safety guarantees. Unlike digital assistants, a single failure in an autonomous vehicle can lead to catastrophic collisions. Formal verification aims to mathematically prove that a system will never enter an unsafe state. However, verifying Neural Network (NN) controlled systems is hindered by three primary factors: non-linear sensing, the black-box nature of DNNs, and the state explosion problem when combining continuous physics with complex neural logic.

Figure 1: Closed-loop system architecture showing the interaction between the robot, LiDAR preprocessing, and the neural network controller.

Methodology

The proposed framework employs a multi-stage pipeline to compute a "safe set" of initial positions from which the robot is guaranteed to avoid obstacles.

1. Workspace Partitioning

The environment is divided into "imaging-adapted sets" using computational geometry. Within these regions, the relationship between the robot's position and the LiDAR output is guaranteed to be affine (linear). This linearization is crucial as it allows the complex sensing process to be handled by standard verification tools.

2. Finite State Abstraction and SMC Encoding

The continuous state space is discretized into a finite set of abstract states. To determine the feasibility of transitions between these states, the system uses Satisfiability Modulo Convex (SMC) encoding. The NN is treated as a series of logical switches (ReLUs). A Boolean SAT solver identifies potential paths through the network, while a convex solver verifies if these paths are physically reachable given the robot's dynamics and the linear constraints of the current workspace partition.

Figure 4: The complete verification pipeline, from workspace partitioning to the computation of safe states using finite state abstraction and SMC.

3. Reachability-Based Pruning

To combat the exponential complexity of ReLU combinations ($2^M$ for $M$ neurons), a pre-processing step prunes "impossible" activation patterns for specific regions. This drastically reduces the search space; for instance, in a 32-neuron network, the number of feasible internal states was reduced from billions to just 11 within a test region.

Experimental Evaluation

The framework was evaluated using numerical simulations of autonomous robots in environments with varying polytopic obstacles.

  • Scalability: The partitioning algorithm handled complex setups with 298 laser angles and 12 obstacle vertices in less than 1.5 minutes.
  • Verification Performance: The system successfully verified transitions for networks ranging from 22 to 702 neurons. The reachability-based pruning provided an order-of-magnitude speedup in transition feasibility checks.
  • Complexity Handling: While the framework scales well with network width, increased depth (more hidden layers) was found to significantly increase execution time due to a higher volume of counterexamples.

Conclusion and Future Work

This work provides a scalable approach to the formal verification of LiDAR-based autonomous systems. By leveraging the piecewise linear nature of LiDAR sensing, we enable the use of efficient SMC solvers for safety proofs. Future research will focus on addressing LiDAR uncertainty (sensor noise and beam thickness) and improving the maximality of the computed safe sets, as the current abstraction can be conservative.

Summary updated

BibTeX
@inproceedings{sun2019formal,
  author = {Xiaowu Sun and Haitham Khedr and Yasser Shoukry},
  title = {{Formal Verification of Neural Network Controlled Autonomous Systems}},
  booktitle = {HSCC},
  year = {2019},
  doi = {10.1145/3302504.3311802},
}
Figure