Efficient Formal Safety Analysis of Neural Networks
By Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, Suman Sekhar Jana. 2018
458 citations recorded by the source corpus.
Neural networks are increasingly deployed in real-world safety-critical domains such as autonomous driving, aircraft collision avoidance, and malware detection. However, these networks have been shown to often mispredict on inputs with minor adversarial or even accidental perturbations. Consequences of such errors can be disastrous and even potentially fatal as shown by the recent Tesla autopilot crash. Thus, there is an urgent need for formal analysis systems that can rigorously check neural networks for violations of different safety properties such as robustness against adversarial perturbations within a certain L-norm of a given image. An effective safety analysis system for a neural network must be able to either ensure that a safety property is satisfied by the network or find a counterexample, i.e., an input for which the network will violate the property. Unfortunately, most existing techniques for performing such analysis struggle to scale beyond very small networks and the ones that can scale to larger networks suffer from high false positives and cannot produce concrete counterexamples in case of a property violation. In this paper, we present a new efficient approach for rigorously checking different safety properties of neural networks that significantly outperforms existing approaches by multiple orders of magnitude. Our approach can check different safety properties and find concrete counterexamples for networks that are 10x larger than the ones supported by existing analysis techniques. We believe that our approach to estimating tight output bounds of a network for a given input range can also help improve the explainability of neural networks and guide the training process of more robust neural networks.
Subfields: Artificial Intelligence, Safety, Robustness & Interpretability, Program Analysis & Verification
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Safety, Robustness & Interpretability
In Program Analysis & Verification
- Huan Zhang
- Cho-Jui Hsieh
- Suman Sekhar Jana
- Shiqi Wang
- Zico Kolter
- Christopher Lazarus
- Bo Li
- Ahmed Abdou
Citations in the corpus
- Certified Adversarial Robustness via Randomized Smoothing (2019, background): “Instead, a panoply of practical solutions have been proposed in the literature (Wong & Kolter, 2018; Wang et al., 2018a;b; Raghunathan et al., 2018a;b; Wong et al., 2018; Dvijotham et al., 2018b;a; Croce et al., 2018; Gehr et al., 2018; Mirman et al., 2018; Singh et al., 2018; Gowal et al., 2018;…”
- Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers (2019, background): “On the bright side, these methods are more scalable and efficient which makes some of them useful for building certified defenses [38, 35, 36, 27, 28, 39, 10, 9, 7, 13, 26, 30, 15, 37, 40].”
- A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks (2019, methodology): “…gives a theoretical hardness proof based on a reduction from the set-cover problem; Neurify (Wang et al., 2018b) combines the relaxed bound with a branch-and-bound search to give concrete instances of adversarial example if they exist, and also uses the bound for training (Wang et al., 2018a).”
- Algorithms for Verifying Deep Neural Networks (2019, methodology): “Repre-sentative methods for search and reachability include ReluVal [23], Neurify [24], DLV [25], Fast-Lin [26], Fast-Lip [26], CROWN [27], nnenum [28], and VeriNet [29].”
- Software Engineering for AI-Based Systems: A Survey (2021, background): “Five papers focus on formal model analysis with different goals: analysis of safety and scalability in models for autonomous vehicles [183], quantitative analysis for systems based on recurrent neural networks [49], improvement and certification of robustness for ML models [220], and approaches for ”
- MixTrain: Scalable Training of Formally Robust Neural Networks (2018, methodology): “Here we utilize symbolic interval propagation [27] as the main method for verifiably robust training in this paper.”
- Interpretable and Trustworthy Deepfake Detection via Dynamic Prototypes (2021, background): “The importance of safety verification, especially in critical domains such as healthcare or autonomous driving, was highlighted when the discovery of adversarial attacks [57, 22] prompted many lines of work in robust verification in ML [32, 28, 23, 25, 68, 10, 39].”
- Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations (2020, background): “Convex relaxation of non-linear units in neural networks enables an efficient analysis of the outer bounds for a neural network [79, 86, 66, 13, 78, 76, 57, 67].”
- Towards Stable and Efficient Training of Verifiably Robust Neural Networks (2019, methodology): “Since the bound propagation process of a convex adversarial polytope is too expensive, several methods were proposed to improve its efficiency, like Cauchy projection (Wong et al., 2018) and dynamic mixed training (Wang et al., 2018a).”
- Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification (2021, methodology): “based method was proposed to better exploit the network structure using LP-based incomplete verifier for bounding and ReLU splits for branching [8, 40, 23, 5].”
- Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond (2020, background): “Many other works have independently discovered similar algorithms [7, 30, 37, 46, 53, 39, 45] in either primal or dual space which we refer to as linear relaxation based perturbation analysis (LiRPA).”
- Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes (2019, background): “An equivalent formulation of this problem is providing overestimations on the range of neural nets, for which interval arithmetic has been shown useful [23, 24].”