AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
By Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, Martin T. Vechev. 2018
1,008 citations recorded by the source corpus.
We present AI2, the first sound and scalable analyzer for deep neural networks. Based on overapproximation, AI2 can automatically prove safety properties (e.g., robustness) of realistic neural networks (e.g., convolutional neural networks). The key insight behind AI2 is to phrase reasoning about safety and robustness of neural networks in terms of classic abstract interpretation, enabling us to leverage decades of advances in that area. Concretely, we introduce abstract transformers that capture the behavior of fully connected and convolutional neural network layers with rectified linear unit activations (ReLU), as well as max pooling layers. This allows us to handle real-world neural networks, which are often built out of those types of layers. We present a complete implementation of AI2 together with an extensive evaluation on 20 neural networks. Our results demonstrate that: (i) AI2 is precise enough to prove useful specifications (e.g., robustness), (ii) AI2 can be used to certify the effectiveness of state-of-the-art defenses for neural networks, (iii) AI2 is significantly faster than existing analyzers based on symbolic analysis, which often take hours to verify simple fully connected networks, and (iv) AI2 can handle deep convolutional networks, which are beyond the reach of existing methods.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, 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 Computer Vision and Pattern Recognition
- Luc Van Gool
- Bernt Schiele
- Dacheng Tao
- Xiaogang Wang
- Andrew Zisserman
- Ming-Hsuan Yang
- Trevor Darrell
- Yi Yang
In Electrical and Electronic Engineering
- Cho-Jui Hsieh
- J. Kolter
- Huan Zhang
- Alexey Ignatiev
- Matthias Hein
- Prateek Mittal
- Eric Wong
- Suman Sekhar Jana
In Safety, Robustness & Interpretability
- Huan Zhang
- Cho-Jui Hsieh
- Matthias Hein
- J. Kolter
- Suman Sekhar Jana
- Eric Wong
- Shiqi Wang
- Pushmeet Kohli
In Program Analysis & Verification
- Suman Sekhar Jana
- Huan Zhang
- J. Kolter
- Eric Wong
- Shiqi Wang
- Cho-Jui Hsieh
- Clark W. Barrett
- Marta Z. Kwiatkowska
Citations in the corpus
- Privacy Risks of Securing Machine Learning Models against Adversarial Examples (2019, methodology): “[34] leverage the technique of abstract interpretation to compute the worse-case loss: an abstract domain (such as interval domain, zonotope domain [13]) is used to express the adversarial perturbation constraint Bε at the input layer, and by applying abstract transformers on it, the maximum verifie”
- Certified Adversarial Robustness via Randomized Smoothing (2019, background): “…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; Weng et al., 2018a; Zhang et al., 2018).”
- Efficient Formal Safety Analysis of Neural Networks (2018, background): “While these techniques tend to scale significantly better than solver-based approaches, they suffer from high false positive rates and struggle to find concrete counterexamples demonstrating violations of safety properties [42, 32, 13, 9].”
- Formal Security Analysis of Neural Networks using Symbolic Intervals (2018, background): “[14] leverages zonotopes for approximating each ReLU outputs.”
- On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models (2018, methodology): “Substantial progress has been made: from complete methods that use Satisfiability Modulo Theory (SMT) [14–16] or Mixed-Integer Programming (MIP) [13, 17, 18] to incomplete methods that rely on solving a convex relaxation of the verification problem [19–26].”
- 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].”
- DeepHunter: a coverage-guided fuzz testing framework for deep neural networks (2019, background): “A more recent work AI 2 [45] adopts abstract interpretation with well designed abstract domains to verify DNNs.”
- LEMNA: Explaining Deep Learning based Security Applications (2018, methodology): “Common approaches involve running forward propagation [17, 19, 32, 76] or backward propagation [3, 50, 53] in the network to infer important features.”
- Algorithms for Verifying Deep Neural Networks (2019, methodology): “Representative methods are ExactReach [6], MaxSens [7], NNV [8], SymBox [9], Ai2 [10], and ERAN [11]–[14].”
- Efficient Neural Network Robustness Certification with General Activation Functions (2018, positive): “A recent framework, AI2 [28], uses abstract transformations to zonotopes for proving robustness property for ReLU networks.”
- Overfitting in adversarially robust deep learning (2020, background): “…Zhang et al., 2019b), randomized smoothing (Cohen et al., 2019; Lecuyer et al., 2019; Salman et al., 2019a), distributional robustness (Sinha et al., 2017), abstract interpretations (Gehr et al., 2018; Mirman et al., 2018; Singh et al., 2018), and interval bound propagation (Gowal et al., 2018).”
- Neurosymbolic Programming (2021, background): “Over the last few years, there have been many efforts on algorithmic analysis of the safety and robustness of neural networks (Katz et al., 2017; Gehr et al., 2018; Anderson et al., 2019).”
- The Marabou Framework for Verification and Analysis of Deep Neural Networks (2019, methodology): “Several recent papers have proposed verification schemes that rely on DNNlevel reasoning [5,23].”