Towards Fast Computation of Certified Robustness for ReLU Networks

Abstract

Verifying the robustness property of a general Rectified Linear Unit (ReLU) network is an NP-complete problem [Katz, Barrett, Dill, Julian and Kochenderfer CAV17]. Although finding the exact minimum adversarial distortion is hard, giving a certified lower bound of the minimum distortion is possible. Current available methods of computing such a bound are either time-consuming or delivering low quality bounds that are too loose to be useful. In this paper, we exploit the special structure of ReLU networks and provide two computationally efficient algorithms Fast-Lin and Fast-Lip that are able to certify non-trivial lower bounds of minimum distortions, by bounding the ReLU units with appropriate linear functions Fast-Lin, or by bounding the local Lipschitz constant Fast-Lip. Experiments show that (1) our proposed methods deliver bounds close to (the gap is 2-3X) exact minimum distortion found by Reluplex in small MNIST networks while our algorithms are more than 10,000 times faster; (2) our methods deliver similar quality of bounds (the gap is within 35% and usually around 10%; sometimes our bounds are even better) for larger networks compared to the methods based on solving linear programming problems but our algorithms are 33-14,000 times faster; (3) our method is capable of solving large MNIST and CIFAR networks up to 7 layers with more than 10,000 neurons within tens of seconds on a single CPU core. In addition, we show that, in fact, there is no polynomial time algorithm that can approximately find the minimum ${\ell }_1$ adversarial distortion of a ReLU network with a $0.99\ln n$ approximation ratio unless $\mathsf{NP}$=$\mathsf{P}$, where $n$ is the number of neurons in the network.

Tsui-Wei Weng and Huan Zhang contributed equally

References in corpus (20)

• Ensemble Adversarial Training: Attacks and Defenses
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Delving into Transferable Adversarial Examples and Black-box Attacks
• Adversarial Machine Learning at Scale
• Certifying Some Distributional Robustness with Principled Adversarial Training
• Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods
• Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation
• Adversarial Examples for Evaluating Reading Comprehension Systems
• An approach to reachability analysis for feed-forward ReLU neural networks
• Houdini: Fooling Deep Structured Prediction Models
• Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach
• MagNet and "Efficient Defenses Against Adversarial Attacks" are Not Robust to Adversarial Examples
• Adversarial Examples for Semantic Segmentation and Object Detection
• Adversarial Example Defenses: Ensembles of Weak Defenses are not Strong
• EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples
• Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study
• Towards Robust Neural Networks via Random Self-ensemble
• Attacking Visual Language Grounding with Adversarial Examples: A Case Study on Neural Image Captioning
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• Maximum Resilience of Artificial Neural Networks

Cited by in corpus (38)

• Adversarial Sample Detection for Deep Neural Network through Model Mutation Testing
• ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
• Verification for Machine Learning, Autonomy, and Neural Networks Survey
• Adversarial Machine Learning -- Industry Perspectives
• Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks
• Open- and Closed-Loop Neural Network Verification using Polynomial Zonotopes
• DNNV: A Framework for Deep Neural Network Verification
• Exactly Computing the Local Lipschitz Constant of ReLU Networks
• Towards Understanding Fast Adversarial Training
• Adversarial Learning in Statistical Classification: A Comprehensive Review of Defenses Against Attacks
• Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes
• A Statistical Approach to Assessing Neural Network Robustness
• Resilient Cyberphysical Systems and their Application Drivers: A Technology Roadmap
• Membership Leakage in Label-Only Exposures
• Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming
• CAQL: Continuous Action Q-Learning
• Verification of deep probabilistic models
• Reachability Analysis for Feed-Forward Neural Networks using Face Lattices
• DSRNA: Differentiable Search of Robust Neural Architectures
• On Certifying Non-uniform Bound against Adversarial Attacks
• Better the Devil you Know: An Analysis of Evasion Attacks using Out-of-Distribution Adversarial Examples
• On Training Robust PDF Malware Classifiers
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• Certifying Incremental Quadratic Constraints for Neural Networks via Convex Optimization
• Robustness Certificates Against Adversarial Examples for ReLU Networks
• RobOT: Robustness-Oriented Testing for Deep Learning Systems
• Certifying Neural Network Robustness to Random Input Noise from Samples
• Accelerating Robustness Verification of Deep Neural Networks Guided by Target Labels
• Quantitative Projection Coverage for Testing ML-enabled Autonomous Systems
• Insta-RS: Instance-wise Randomized Smoothing for Improved Robustness and Accuracy
• Non-Stochastic Information Theory
• Robusta: Robust AutoML for Feature Selection via Reinforcement Learning
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
• Position Paper: Towards Transparent Machine Learning
• Expected Tight Bounds for Robust Training
• Towards adversarial robustness with 01 loss neural networks
• Notes on Margin Training and Margin p-Values for Deep Neural Network Classifiers
• Neural Network Repair with Reachability Analysis