Abstract
Neural networks (NNs) playing the role of controllers have demonstrated impressive empirical performances on challenging control problems. However, the potential adoption of NN controllers in real-life applications also gives rise to a growing concern over the safety of these neural-network controlled systems (NNCSs), especially when used in safety-critical applications. In this work, we present POLAR-Express, an efficient and precise formal reachability analysis tool for verifying the safety of NNCSs. POLAR-Express uses Taylor model arithmetic to propagate Taylor models (TMs) across a neural network layer-by-layer to compute an overapproximation of the neural-network function. It can be applied to analyze any feed-forward neural network with continuous activation functions. We also present a novel approach to propagate TMs more efficiently and precisely across ReLU activation functions. In addition, POLAR-Express provides parallel computation support for the layer-by-layer propagation of TMs, thus significantly improving the efficiency and scalability over its earlier prototype POLAR. Across the comparison with six other state-of-the-art tools on a diverse set of benchmarks, POLAR-Express achieves the best verification efficiency and tightness in the reachable set analysis.
Introduction: The Challenge of Verifying NNCS
Neural networks (NNs) are increasingly used as controllers in autonomous vehicles, robotics, and aerospace. However, their non-linear, "black-box" nature makes it difficult to prove they will always behave safely.
Reachability analysis is the formal method used to solve this. It asks: "Given a set of possible starting positions, can the system ever enter an 'unsafe' state (like a collision) within a certain timeframe?" The challenge is that both the neural network and the physical system (the "plant") are non-linear. When you loop them together, errors in approximating their behavior tend to grow exponentially—a phenomenon known as the "wrapping effect"—leading to "loose" results that are too vague to prove safety.
Methodology
POLAR-Express builds on the earlier POLAR prototype but introduces several key technical innovations to improve precision and scalability. The tool analyzes the closed-loop system by propagating state sets through the plant and the controller.
Key Technical Innovations
- Taylor Model (TM) Propagation: It represents sets of states as Taylor models—a combination of a polynomial and an error interval. It propagates these models through the neural network layer-by-layer.
- Bernstein Over-approximation for ReLU: Standard Taylor models struggle with ReLUs because they are non-differentiable at zero. POLAR-Express exploits the fact that ReLUs are convex, using Bernstein polynomials to create a tighter "sandwich" around the ReLU function, significantly reducing approximation error.
- Symbolic Remainders (SR): To combat the wrapping effect, the tool tracks linear transformations symbolically. Instead of immediately collapsing errors into a simple interval at each layer, it maintains dependency information, performing the final interval evaluation only at the end of the process.
- Parallel Computation: The tool implements multi-threading for layer-by-layer propagation, allowing it to scale to large neural networks and high-dimensional systems.
Experimental Evaluation
The authors evaluated POLAR-Express against six other state-of-the-art tools (including NNV, Verisig 2.0, and CORA) using a diverse suite of benchmarks ranging from standard control tasks to complex 12-dimensional drone dynamics (QUAD20).
Key Results
- Superior Tightness: In almost all benchmarks, POLAR-Express produced the tightest "flowpipes" (the set of reachable states), often succeeding where other tools produced bounds so large they were useless.
- Speedups: On ReLU-based systems, POLAR-Express was ~4x faster than the original POLAR tool while providing tighter bounds.
- Scalability: POLAR-Express was the only tool able to efficiently verify the 12-dimensional QUAD20 system. Other tools either timed out, crashed, or failed due to soundness issues.
- Accuracy Preservation: The authors developed a selection method that chooses between Taylor and Bernstein approximations based on which preserves accuracy better through the entire composition, rather than just at a single layer.
Conclusion and Future Work
POLAR-Express represents a state-of-the-art advancement in safety verification for NNCSs. While it handles 12 dimensions well, future work will focus on further improving scalability for even higher-dimensional systems where polynomial expressions become computationally expensive. The authors also plan to explore more efficient ways to handle large control time-steps and long time horizons.
Summary updated