A wide range of defenses have been proposed to harden neural networks against adversarial attacks. However, a pattern has emerged in which the majority of adversarial defenses are quickly broken by new attacks.   Given the lack of success at generating robust defenses, we are led to ask a fundamental question:  Are adversarial attacks inevitable?
 This paper analyzes adversarial examples from a theoretical perspective, and identifies fundamental bounds on the susceptibility of a classifier to adversarial attacks.    We show that, for certain classes of problems, adversarial examples are inescapable.   Using experiments, we explore the implications of theoretical guarantees for real-world problems and discuss how factors such as dimensionality and image complexity limit a classifier's robustness against adversarial examples.

 A number of adversarial attacks on neural networks have been recently proposed. To counter these attacks, a number of authors have proposed a range of defenses. However, these defenses are often quickly broken by new and revised attacks. Given the lack of success at generating robust defenses, we are led to ask a fundamental question: Are adversarial attacks inevitable?In this paper, we identify a broad class of problems for which adversarial examples cannot be avoided. We also derive fundamental limits on the susceptibility of a classifier to adversarial attacks that depend on properties of the data distribution as well as the dimensionality of the dataset.Adversarial examples occur when a small perturbation to an image changes its class label. There are different ways of measuring what it means for a perturbation to be "small"; as such, our analysis considers a range of different norms. While the ∞ -norm is commonly used, adversarial examples can be crafted in any p -norm (see FIG0 ). We will see that the choice of norm can have a dramatic effect on the strength of theoretical guarantees for the existence of adversarial examples. Our analysis also extends to the 0 -norm, which yields "sparse" adversarial examples that only perturb a small subset of image pixels FIG2 ). BID19 on Resnet50 , along with the distance between the base image and the adversarial example, and the top class label. There are a number of ways to escape the guarantees of adversarial examples made by Theorems 1-4. One potential escape is for the class density functions to take on extremely large values (i.e., exponentially large U c ); the dependence of U c on n is addressed separately in Section 8.Unbounded density functions and low-dimensional data manifolds In practice, image datasets might lie on low-dimensional manifolds within the cube, and the support of these distributions could have measure zero, making the density function infinite (i.e., U c = ∞). The arguments above are still relevant (at least in theory) in this case; we can expand the data manifold by adding a uniform random noise to each image pixel of magnitude at most 1 . The expanded dataset has positive volume. Then, adversarial examples of this expanded dataset can be crafted with perturbations of size 2 . This method of expanding the manifold before crafting adversarial examples is often used in practice. BID39 proposed adding a small perturbation to step off the image manifold before crafting adversarial examples. This strategy is also used during adversarial training BID19 .Adding a "don't know" class The analysis above assumes the classifier assigns a label to every point in the cube. If a classifier has the ability to say "I don't know," rather than assign a label to every input, then the region of the cube that is assigned class labels might be very small, and adversarial examples could be escaped even if the other assumptions of Theorem 4 are satisfied. In this case, it would still be easy for the adversary to degrade classifier performance by perturbing images into the "don't know" class.Feature squeezing If decreasing the dimensionality of data does not lead to substantially increased values for U c (we see in Section 8 that this is a reasonable assumption) or loss in accuracy (a stronger assumption), measuring data in lower dimensions could increase robustness. This can be done via an auto-encoder BID22 BID30 , JPEG encoding BID9 , or quantization BID43 .Computational hardness It may be computationally hard to craft adversarial examples because of local flatness of the classification function, obscurity of the classifier function, or other computational difficulties. Computational hardness could prevent adversarial attacks in practice, even if adversarial examples still exist.
This paper identifies classes of problems for which adversarial examples are inescapable, and derives fundamental bounds on the susceptibility of any classifier to adversarial examples. 
{"src": "scitldr-AIC_train", "paper_id": "r1lWUoA9FQ"}