Towards Fast Computation of Certified Robustness for ReLU Networks
By Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane S. Boning, Inderjit S. Dhillon, Luca Daniel. 2018
755 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, 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
- Percy Liang
- Cho-Jui Hsieh
- Sergey Levine
- Mohit Bansal
- J. Kolter
- Matthias Hein
- Jianfeng Gao
- Yoshua Bengio
In Electrical and Electronic Engineering
- Huan Zhang
- Matthias Hein
- Cho-Jui Hsieh
- J. Kolter
- A. Dimakis
- Maksym Andriushchenko
- Sven Gowal
- Percy Liang
In Safety, Robustness & Interpretability
- Huan Zhang
- Matthias Hein
- Cho-Jui Hsieh
- J. Kolter
- Suman Sekhar Jana
- Bo Li
- Francesco Croce
- Percy Liang
In Program Analysis & Verification
- Huan Zhang
- Matthias Hein
- Suman Sekhar Jana
- Shiqi Wang
- Cho-Jui Hsieh
- Pushmeet Kohli
- J. Kolter
- Gagandeep Singh
Citations in the corpus
- Certified Adversarial Robustness via Randomized Smoothing (2019, methodology): “…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, methodology): “Note that concurrent work of Weng et al. [40] uses similar linear relaxation method as ours but it alone struggles to solve such problems as shown in Table 6.”
- On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, positive): “To this aim, we resort to enforcing the Lipschitz continuity of the model w.r.t. its input: indeed, a long-standing research trend [82, 72, 45, 46, 80, 29] has pointed out that such a property favors generalization capabilities and robustness to adversarial attacks.”
- Adversarial examples from computational constraints (2018, background): “Perhaps the most significant developments have been related to training models with provable robustness guarantees (Dvijotham et al., 2018; Wong and Kolter, 2018; Weng et al., 2018; Xiao et al., 2018), however, currently all the methods for such training are either extremely slow or the certified bo”
- 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].”
- Semidefinite relaxations for certifying robustness to adversarial examples (2018, background): “2 which forms the basis for several existing works on scalable certification [9, 10, 28, 29].”
- CAQL: Continuous Action Q-Learning (2019, background): “Furthermore, (cid:96) j , u j are interval bounds for the outputs of the neurons in layer j for j ≥ 2 , and computing them can be done via interval arithmetic or other propagation methods (Weng et al., 2018) from the initial action space bounds (see Appendix C for details).”
- Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks (2019, methodology): “Using Lipschitz bounds in the context of adversarial robustness and safety verification has also been addressed in several works [39, 31, 38].”
- Algorithms for Verifying Deep Neural Networks (2019, methodology): “FastLip [41] estimates the local Lipschitz constant, which is equivalent to what Certify computes in (84).”
- Certified Adversarial Robustness with Additive Noise (2018, methodology): “On the other hand, many works have focused on providing provable/certified robustness of deep neural networks [11, 12, 13, 14, 15, 16, 17].”
- Lipschitz-Certifiable Training with a Tight Outer Bound (2020, background): “In contrast, the layer-wise bound propagation approach calculates the upper bounds on the worst case error through relaxation on the layer-wise operations and forward propagation for the perturbation set that can be made of (cid:96) ∞ - or (cid:96) 2 -balls [13, 44, 36, 25, 32, 37].”
- Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond (2020, methodology): “Our framework is a superset of many existing works [48, 53, 46, 23, 36], and our automatic perturbation analysis algorithm is analogous to automatic differentiation.”
- Efficient Neural Network Robustness Certification with General Activation Functions (2018, methodology): “In particular, we show that the state-of-the-art Fast-Lin algorithm is a special case under the CROWN framework and that the adaptive selections of approximation bounds allow CROWN to achieve a tighter (larger) certified lower bound (see Section 4).”
- Globally-Robust Neural Networks (2021, methodology): “Unfortunately, current training methods do not produce models with sufficiently small global bounds for this to succeed (Weng et al., 2018a).”
- A Review of Single-Source Deep Unsupervised Visual Domain Adaptation (2020, background): “Due to the wide success of deep neural networks and their unexpected vulnerability of adversarial examples, there has been much attention placed on evaluating and quantifying the robustness of neural networks [220, 221].”