POLAR: A Polynomial Arithmetic Framework for Verifying Neural-Network Controlled Systems
Preprint
Abstract
We propose POLAR, a \textbf{pol}ynomial \textbf{ar}ithmetic framework that leverages polynomial overapproximations with interval remainders for bounded-time reachability analysis of neural network-controlled systems (NNCSs). Compared with existing arithmetic approaches that use standard Taylor models, our framework uses a novel approach to iteratively overapproximate the neuron output ranges layer-by-layer with a combination of Bernstein polynomial interpolation for continuous activation functions and Taylor model arithmetic for the other operations. This approach can overcome the main drawback in the standard Taylor model arithmetic, i.e. its inability to handle functions that cannot be well approximated by Taylor polynomials, and significantly improve the accuracy and efficiency of reachable states computation for NNCSs. To further tighten the overapproximation, our method keeps the Taylor model remainders symbolic under the linear mappings when estimating the output range of a neural network. We show that POLAR can be seamlessly integrated with existing Taylor model flowpipe construction techniques, and demonstrate that POLAR significantly outperforms the current state-of-the-art techniques on a suite of benchmarks.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Verisig 2.0: Verification of Neural Network Controllers Using Taylor Model Preconditioning2021
- Verifying the Safety of Autonomous Systems with Neural Network ControllersACM Transactions on Embedded Computing Systems, 2020
- ReachNN*: A Tool for Reachability Analysis of Neural-Network Controlled Systems2020
- NNV: The Neural Network Verification Tool for Deep Neural Networks and Learning-Enabled Cyber-Physical Systems2020
- Reachability analysis for neural feedback systems using regressive polynomial rule inference2019
- On Taylor Model Based Integration of ODEsSIAM Journal on Numerical Analysis, 2007
- Nonlinear Control Synthesis by Convex OptimizationIEEE Transactions on Automatic Control, 2004
- Verified Integration of ODEs and Flows Using Differential Algebraic Methods on High-Order Taylor ModelsReliable Computing, 1998
- A theory of timed automataTheoretical Computer Science, 1994