Analysis of classifiers’ robustness to adversarial perturbations

By Alhussein Fawzi, Omar Fawzi, Pascal Frossard. 2015

386 citations recorded by the source corpus.

The goal of this paper is to analyze the intriguing instability of classifiers to adversarial perturbations (Szegedy et al., in: International conference on learning representations (ICLR), 2014). We provide a theoretical framework for analyzing the robustness of classifiers to adversarial perturbations, and show fundamental upper bounds on the robustness of classifiers. Specifically, we establish a general upper bound on the robustness of classifiers to adversarial perturbations, and then illustrate the obtained upper bound on two practical classes of classifiers, namely the linear and quadratic classifiers. In both cases, our upper bound depends on a distinguishability measure that captures the notion of difficulty of the classification task. Our results for both classes imply that in tasks involving small distinguishability, no classifier in the considered set will be robust to adversarial perturbations, even if a good accuracy is achieved. Our theoretical framework moreover suggests that the phenomenon of adversarial instability is due to the low flexibility of classifiers, compared to the difficulty of the classification task (captured mathematically by the distinguishability measure). We further show the existence of a clear distinction between the robustness of a classifier to random noise and its robustness to adversarial perturbations. Specifically, the former is shown to be larger than the latter by a factor that is proportional to $$\sqrt{d}$$d (with d being the signal dimension) for linear classifiers. This result gives a theoretical explanation for the discrepancy between the two robustness properties in high dimensional problems, which was empirically observed by Szegedy et al. in the context of neural networks. We finally show experimental results on controlled and real-world data that confirm the theoretical analysis and extend its spirit to more complex classification schemes.

Subfields: Artificial Intelligence, Safety Research, 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 Research

In Safety, Robustness & Interpretability

Citations in the corpus

Distillation as a Defense to Adversarial Perturbations Against Deep Neural Networks (2015, background): “We extend the definition of robustness introduced in [30] to the adversarial behavior of source-target class pair misclassification within the context of classifiers built using DNNs.”
Stochastic Activation Pruning for Robust Adversarial Defense (2018, background): “Robustness to adversarial attack has recently emerged as a serious topic in machine learning (Good-fellow et al., 2014; Kurakin et al., 2016; Papernot & McDaniel, 2016; Tramèr et al., 2017b; Fawzi et al., 2018).”
NO Need to Worry about Adversarial Examples in Object Detection in Autonomous Vehicles (2017, background): “In the past few years, researchers tried to explain why neural nets are susceptible to such examples despite their impressive success on random test datasets [6, 5, 2], suggested new methods to generate adversarial examples and measure NN robustness against them [4, 21, 16, 9, 17, 19, 13], and propo”
Parseval Networks: Improving Robustness to Adversarial Examples (2017, background): “Some authors argued that this sensitivity of deep networks to small changes in their inputs is because neural networks only learn the discriminative information sufficient to obtain good accuracy rather than capturing the true concepts defining the classes (Fawzi et al., 2015; Nguyen et al., 2015).”
Evasion and Hardening of Tree Ensemble Classifiers (2015, methodology): “We de-liberately do not limit the amount of information available for carrying out evasion.”
Countering Adversarial Images using Input Transformations (2018, neutral): “The robustness of machine learning models to adversarial examples depends both on the properties of the model ( i.e. , Lipschitzness) and on the nature of the problem considered, e.g. , on the input dimensionality and the Bayes error of the problem (Fawzi et al., 2015; 2016).”
DeepFool: A Simple and Accurate Method to Fool Deep Neural Networks (2015, methodology): “Similarly to the binary case, we first present the proposed approach for the linear case and then we generalize it to other classifiers.”
A Unified Gradient Regularization Family for Adversarial Examples (2015, methodology): “A recent theoretical study suggests there is a relationship between adversarial examples and Gaussian noise [6], we have used testing errors under Gaussian noise as a criterion to test whether our regularization technique improves the models’ robustness against perturbations.”
Stable and Fair Classification (2019, background): “Stability is a crucial consideration in classiﬁcation [10, 57, 12, 25], and has been investigated in several real-world applications, e.g., advice-giving agents [31, 69], recommendation systems [2, 1, 3], and judicial decision-making [66].”
Learning with a Strong Adversary (2015, background): “Since the appearance of Szegedy et al. (2013), increasing attention has been paid to the curious phenomenon of ‘adversarial perturbation’ in the deep learning community; see, for example (Good-fellow et al., 2014; Fawzi et al., 2015; Miyato et al., 2015; Nøkland, 2015; Tabacof & Valle, 2015).”
Measuring Neural Net Robustness with Constraints (2016, background): “Robustness has also been studied in more general contexts; [23] studies the connection between robustness and generalization, [2] establishes theoretical lower bounds on the robustness of linear and quadratic classifiers, and [4] seeks to improve robustness by promoting resiliance to deleting featur”
Robustness May Be at Odds with Accuracy (2018, background): “Due to the large body of related work, we will only focus on the most relevant studies here and defer the full discussion to Appendix F. Fawzi et al. (2018b) prove upper bounds on the robust of classiﬁers and exhibit a standard vs. robust accuracy trade-oﬀ for a speciﬁc classiﬁer families on a…”
Actionable Recourse in Linear Classification (2018, background): “These include: inverse classication, which aims to determine how the inputs to a prediction model can be manipulated to obtain a desired outcome [1, 8]; strategic classication, which considers the converse problem of training classiers that are robust to malicious manipulation [13, 17]; adversarial ”
The Space of Transferable Adversarial Examples (2017, background): “, most vision tasks, see [7]), the perturbation is likely adversarial.”
Robustness of classifiers: from adversarial to random noise (2016, background): “In [3], a formal relation between the robustness to random noise, and the worst-case robustness is established in the case of linear classifiers.”
Measuring the tendency of CNNs to Learn Surface Statistical Regularities (2017, background): “The sensitivity of high performance CNNs to adversarial examples casts serious doubt that these networks are actually learning high level abstract concepts [6, 27].”
Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey (2018, background): “Flatness of decision boundaries [69], large local curvature of the decision boundaries [70] and low flexibility of the networks [71] are some more examples of the viewpoints on the existence of adversarial examples that do not perfectly align with each other.”