Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation

By Matthias Hein, Maksym Andriushchenko. 2017

553 citations recorded by the source corpus.

Recent work has shown that state-of-the-art classifiers are quite brittle, in the sense that a small adversarial change of an originally with high confidence correctly classified input leads to a wrong classification again with high confidence. This raises concerns that such classifiers are vulnerable to attacks and calls into question their usage in safety-critical systems. We show in this paper for the first time formal guarantees on the robustness of a classifier by giving instance-specific lower bounds on the norm of the input manipulation required to change the classifier decision. Based on this analysis we propose the Cross-Lipschitz regularization functional. We show that using this form of regularization in kernel methods resp. neural networks improves the robustness of the classifier without any loss in prediction performance.

Subfields: Artificial Intelligence, Hardware and Architecture, Safety, Robustness & Interpretability, Signal Processing

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 Hardware and Architecture

In Safety, Robustness & Interpretability

In Signal Processing

Citations in the corpus

mixup: Beyond Empirical Risk Minimization (2017, methodology): “Among the several methods aiming to solve this problem, some have proposed to penalize the norm of the Jacobian of the model to control its Lipschitz constant (Drucker & Le Cun, 1992; Cisse et al., 2017; Bartlett et al., 2017; Hein & Andriushchenko, 2017).”
Adversarial Training for Free! (2019, background): “Another popular defense strategy is to regularize the training loss using label smoothing, logit squeezing, or a Jacobian regularization [Shafahi et al., 2019a, Mosbach et al., 2018, Ross and Doshi-Velez, 2018, Hein and Andriushchenko, 2017, Jakubovitz and Giryes, 2018, Yu et al., 2018].”
Certified Adversarial Robustness via Randomized Smoothing (2019, background): “In theory, one could obtain a robustness guarantee via an upper bound on the local Lipschitz constant of the network (Hein & Andriushchenko, 2017), but computing this quantity is intractable for general neural networks.”
Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach (2018, methodology): “L j q is the Lipschitz constant of the function involving cross terms: f c ( x ) − f j ( x ) , hence we also call it cross Lipschitz constant following (Hein & Andriushchenko, 2017).”
Certified Defenses against Adversarial Examples (2018, background): “Hein & Andriushchenko (2017) show how to efficiently compute this bound for p = 2, as opposed to our work which focuses on `∞ and requires different techniques to achieve scalability.”
Towards Robust Neural Networks via Random Self-ensemble (2017, methodology): “In fact, it has been proved recently that Lipschitz constant can be used to measure the robustness of machine learning model [10].”
Adversarial Vulnerability of Neural Networks Increases With Input Dimension (2018, methodology): “Hein & Andriushchenko (2017) derived yet another gradient-based penalty –the cross-Lipschitz -penalty– by considering (and proving) formal guarantees on adversarial vulnerability itself, rather than adversarial damage.”
Towards the first adversarially robust neural network model on MNIST (2018, background): “The few veriﬁable defenses can only guarantee robustness within a small linear regime around the data points (Hein & Andriushchenko, 2017; Raghunathan et al., 2018).”
Toward Trustworthy AI Development: Mechanisms for Supporting Verifiable Claims (2020, background): “not generalizing well to unseen data [66] [67] [68]).”
Towards neural networks that provably know when they don't know (2019, positive): “Empirically, adversarial training (Madry et al., 2018) performs well and provably robust models have been developed (Hein & Andriushchenko, 2017; Wong & Kolter, 2018; Raghunathan et al., 2018; Mirman et al., 2018; Cohen et al., 2019).”
Why ReLU Networks Yield High-Confidence Predictions Far Away From the Training Data and How to Mitigate the Problem (2018, methodology): “Apart from methods which provide robustness guarantees for neural networks [14, 37, 31, 26] which give still only reasonable guarantees for small networks, up to our knowledge the only approach which has not been broken again [6, 5, 2] is adversarial training [25] using robust optimization technique”
Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks (2018, methodology): “Hein and Andriushchenko [12] focused on local Lipschitz constants of neural networks around each input.”
Scaling provable adversarial defenses (2018, background): “For example, Hein and Andriushchenko [2017] develop a formal bound for robustness to (cid:96) 2 perturbations in two-layer networks, and train a surrogate of their bounds.”
A Dual Approach to Scalable Verification of Deep Networks (2018, methodology): “This observation formed the basis for algorithms in [Raghunathan et al., 2018] and [Hein and Andriushchenko, 2017].”
Adversarial vulnerability for any classifier (2018, methodology): “Other works have recently studied procedures and algorithms to provably guarantee a certain level of robustness [22, 23, 24, 25, 26], and have been applied to small datasets (e.”
Semidefinite relaxations for certifying robustness to adversarial examples (2018, background): “[13] provide alternative bounds for `2 norm attacks based on the local gradient.”
Disentangling Adversarial Robustness and Generalization (2018, methodology): “Generalization: Research also includes independent benchmarks of attacks and defenses [13, 15, 5, 6, 85], their properties [57, 84], as well as theoretical questions [34, 42, 23, 99, 27, 88, 102, 104].”
Towards Fast Computation of Certified Robustness for ReLU Networks (2018, methodology): “A tighter bound was given by (Hein & Andriushchenko, 2017) using local Lipschitz constant on a network with one hidden layer, but their approach requires the network to be continuously-differentiable, and thus cannot be directly applied to ReLU networks.”