Provable defenses against adversarial examples via the convex outer adversarial polytope

By J. Kolter, Eric Wong. 2017

1,630 citations recorded by the source corpus.

We propose a method to learn deep ReLU-based classifiers that are provably robust against norm-bounded adversarial perturbations (on the training data; for previously unseen examples, the approach will be guaranteed to detect all adversarial examples, though it may flag some non-adversarial examples as well). The basic idea of the approach is to consider a convex outer approximation of the set of activations reachable through a norm-bounded perturbation, and we develop a robust optimization procedure that minimizes the worst case loss over this outer region (via a linear program). Crucially, we show that the dual problem to this linear program can be represented itself as a deep network similar to the backpropagation network, leading to very efficient optimization approaches that produce guaranteed bounds on the robust loss. The end result is that by executing a few more forward and backward passes through a slightly modified version of the original network (though possibly with much larger batch sizes), we can learn a classifier that is provably robust to any norm-bounded adversarial attack. We illustrate the approach on a toy 2D robust classification task, and on a simple convolutional architecture applied to MNIST, where we produce a classifier that provably has less than 8.4% test error for any adversarial attack with bounded $\ell_\infty$ norm less than $\epsilon = 0.1$. This represents the largest verified network that we are aware of, and we discuss future challenges in scaling the approach to much larger domains.

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability

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

Citations in the corpus

Adversarial Examples Are Not Bugs, They Are Features (2019, background): “While there might exist such fundamental barriers to robustly classifying standard datasets, this model cannot fully explain the situation observed in practice, where one can train (reasonably) robust classifiers on standard datasets [Mad+18; RSL18; WK18; Xia+19; CRK19].”
Adversarial Training for High-Stakes Reliability (2022, methodology): “In addition, contractors took on average 44 minutes (95% CI: [31, 67]) to generate an adversarial example for +tool-assisted without tools, compared to an average of 26 minutes (95% CI: [24, 29]) with our rewrite tool.”
Certified Robustness to Adversarial Examples with Differential Privacy (2018, background): “Certified accuracy denotes the fraction of the testing set on which a certified model’s predictions are both correct and certified robust for a given prediction robustness threshold; it has become a standard metric to evaluate models trained with certified defenses [31], [50], [15].”
Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning (2017, background): “has also derived an extension of this formulation to nonlinear classifiers [100].”
Fundamental Tradeoffs between Invariance and Sensitivity to Adversarial Perturbations (2020, background): “The fact that excessive robustness generalizes (as provably evidenced by the model of Zhang et al. (2019)) points to a deeper issue: there must exist overly-robust and predictive features in the data—that are not aligned with human perception.”
Privacy Risks of Securing Machine Learning Models against Adversarial Examples (2019, methodology): “We consider the l∞-ball adversarial constraint throughout the paper, as it is widely adopted by most adversarial defense methods [16, 33, 34, 40, 50, 61, 66].”
Wasserstein Adversarial Examples via Projected Sinkhorn Iterations (2019, methodology): “∞ robust model We also run the attack on the model trained by Wong et al. (2018), which is guaranteed to be provably robust against (cid:96) ∞ perturbations with (cid:15) ≤ 0 .”
Stronger data poisoning attacks break data sanitization defenses (2018, background): “6). Designing models that are robust to such attacks, as well as coming up with more eective attacks, is an active area of research (Papernot et al., 2016c; Madry et al., 2017; Tramer et al., 2017; Wong and Kolter, 2018; Raghunathan et al., 2018; Sinha et al., 2018; Athalye et al., 2018; Papernot an”
A Rotation and a Translation Suffice: Fooling CNNs with Simple Transformations (2017, background): “Only recently, it has been demonstrated [20, 3, 16] that robust optimization approaches (also known as adversarial training) can reliably increase the resilience of neural network classifiers to a broad class of adversarial examples.”
Ensemble Adversarial Training: Attacks and Defenses (2017, background): “More-over, recent works by Sinha et al. (2018), Raghunathan et al. (2018) and Kolter & Wong (2017) even succeed in providing certiﬁable robustness for small perturbations on MNIST.”
Certified Adversarial Robustness via Randomized Smoothing (2019, methodology): “…to construct an ImageNet classifier that is provably robust 2Lecuyer et al. (2019) showed that randomized smoothing is more robust in `2 norm than the the `∞-robust classifier of Wong & Kolter (2018), but did not compare against the `2-robust classifier in the follow-up work Wong et al. (2018).”
Efficient Formal Safety Analysis of Neural Networks (2018, methodology): “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 [32, 26, 9].”
Training verified learners with learned verifiers (2018, methodology): “Compared to Kolter and Wong [16], our predictorverifier training (PVT) achieves lower error rates under normal and adversarial conditions, as well as better verifiable bounds, setting the state-of-the-art in verified robustness to adversarial attacks.”
Formal Security Analysis of Neural Networks using Symbolic Intervals (2018, background): “[24] transforms the verification problem into the convex optimization by relaxation and solving the dual problem.”
Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “Recently, researchers have proposed convex relaxations of the NP-hard veriﬁcation problem with some success [36, 55], though they may be diﬃcult to scale to large networks.”