Are adversarial examples inevitable?

Ali Shafahi; W. Ronny Huang; Christoph Studer; Soheil Feizi; Tom Goldstein

Source-linked AI summary

Are adversarial examples inevitable?

Ali Shafahi, W. Ronny Huang, Christoph Studer, Soheil Feizi, Tom Goldstein

arXiv:1809.02104v3Sep 6, 2018cs.LGcs.CVstat.ML

TL;DR

Defenses against adversarial attacks are often broken, raising whether such attacks are inevitable. The paper uses high-dimensional geometry to derive susceptibility bounds and finds unavoidable adversarial examples for broad problem classes, while experiments examine the roles of data distribution and dimensionality.

Problem
Repeatedly broken defenses leave open whether adversarial attacks are inevitable and motivate fundamental analysis of classifier robustness.
Method
The paper applies isoperimetric inequalities and related geometric analysis to derive robustness bounds for classifiers across data distributions and dimensions.
Results
The paper identifies broad problem classes where adversarial examples cannot be avoided and derives limits depending on data distribution and dimensionality.
Takeaways & Limitations
For complex image classes, classifier susceptibility is linked primarily to the data distribution rather than dimensionality alone.
Takeaways & Limitations
Exact real-world image distributions and the resulting fundamental limits of adversarial training are impossible to know for specific datasets.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper asks whether adversarial attacks are inevitable after defenses are repeatedly broken, and develops theoretical bounds on classifier susceptibility. It identifies unavoidable adversarial examples for broad problem classes and examines how norms, data distribution, and dimensionality affect robustness.

Repeatedly broken defenses motivate the question of whether adversarial attacks are inevitable.
Adversarial examples cannot be avoided for a broad class of problems.
The analysis considers multiple perturbation norms, including ℓ∞, ℓp, and sparse ℓ0 attacks.The choice of norm can dramatically affect theoretical guarantees for adversarial-example existence.
If each image class occupies more than 1/2 exp(−πϵ2) of the unit hypercube, some image has an ℓ2 adversarial perturbation of norm at most ϵ.The example assumes n-dimensional images with pixels scaled between 0 and 1.
Experiments argue that data distribution, rather than dimensionality, is the primary cause of adversarial susceptibility in the examined real datasets.The paper presents an example image class with no fundamental link between dimensionality and robustness.

2 PROBLEM SETUP

The paper formalizes classification over spheres or hypercubes using class densities and a discrete classifier. It defines adversarial examples as nearby points assigned a different class and considers several norm-based perturbation metrics, including sparse changes.

The setup classifies points in a sphere or hypercube into m object classes represented by probability density functions.
The classifier is a discrete function that partitions the input space into measurable regions, one for each class label.It assigns labels but does not provide confidence levels.
An ϵ-adversarial example exists when a point from class c has a point within distance ϵ that the classifier assigns a different label.
The analysis measures perturbations with ℓp distances, including ℓ∞, ℓ2, and ℓ1 norms.The ℓ∞ metric limits the absolute change to each pixel, while ℓ2 and ℓ1 attacks are less restrictive.
Sparse adversarial examples use d0, where ∥x − ˆx∥0 ≤ ϵ limits changes to at most ϵ pixels.

3 THE SIMPLE CASE: ADVERSARIAL EXAMPLES ON THE UNIT SPHERE

The paper uses isoperimetric inequalities on the sphere to show that sufficiently large class regions place most points near a class boundary. Consequently, either points are misclassified or admit small adversarial perturbations, with guarantees applying across several distance metrics.

Geometric setup: Isoperimetric inequalities show that any sufficiently large subset of the sphere has an expansion at least as large as that of a half sphere.The bound is independent of the shape of the class boundary.
Geometric setup: In high dimensions, nearly all points in a non-small class region can be reached from that region by a short ε jump.This follows from the expansion bounds for half spheres.
Theorem 1: For a random class sample, either the classifier misclassifies it or it admits an ε-adversarial example in geodesic distance.The theorem applies to classifiers partitioning the sphere into measurable class regions and depends on class density and labeled-region size.
Theorem 1: Safe points are exactly those correctly classified points outside the ε-expansion of the classifier's class region.The probability of safe points is bounded using the class density supremum and normalized measure of the safe set.
Metric dependence: The guarantee is not specific to geodesic distance: any geodesic adversarial example is also adversarial under the ℓ∞ and ℓ2 metrics.The bound remains valid for all three metrics, although the appropriate ε changes with the norm.

4 WHAT ABOUT THE UNIT CUBE?

The analysis extends from spherical data to images in the unit hypercube using algebraic isoperimetric inequalities. It guarantees adversarial examples for distributions that are not excessively concentrated, while revealing substantially weaker guarantees for ℓ∞ attacks.

Motivation: The sphere proof does not apply directly to real-world images, whose pixels typically lie inside the high-dimensional cube [0, 1]^n.The cube is not confined to a surface, unlike the sphere.
Geometric setup: Algebraic isoperimetric inequalities provide lower bounds on ε-expansions in the cube without specifying the minimizing shape.Geometric isoperimetric inequalities do not exist for the cube in the same form.
Theorem 2: For cube-distributed classes that are not excessively concentrated, most data samples admit adversarial examples under ℓp-norm perturbations.Theorem 2 considers class densities on [0, 1]^n and classifier partitions of the hypercube.
Norm dependence: For ℓ2 attacks, choosing ε = O(√n) is reasonable relative to the cube's ℓ2 diameter, and the resulting guarantee can be strong.A similarly strong bound is stated for ℓ1 attacks, whose cube diameter is n.
Norm dependence: The ℓ∞ guarantee can become vacuous for large n when ε < 1, although tighter bounds help when the labeled class fraction is sufficiently small.For the refined bound to be meaningful, ε must be roughly the class fraction or smaller; ImageNet has at least one class with fc < 10^-3.
Norm dependence: Under ℓ∞ attacks, adversarial-example guarantees are much stronger on the sphere than on the cube, and the cube weakness is close to inherent.Constructed sets nearly match the weaker bound, making the result relatively tight.

5 WHAT ABOUT SPARSE ADVERSARIAL EXAMPLES?

The paper extends its analysis to sparse adversarial examples under the ℓ0-norm, where perturbations modify only a limited number of pixels. A separate bound is needed because the general theorem becomes loose for small p and fails for p = 0.

Sparse adversarial examples modify only a small number of image pixels, potentially as few as one.Under the ℓ0 metric, the perturbation size counts changed pixels.
Theorem 2 is fairly tight for p = 1 or 2 but becomes loose for small p and fails completely when p = 0.The paper therefore introduces a different bound for sparse attacks.
The cube is analyzed using an isoperimetric inequality designed to provide tighter guarantees for small p, including p = 0.The proof follows prior work on the cube and extends the method to arbitrary p.
Theorem 3 gives a sparse-adversarial-example result analogous to Theorem 2 for a random point drawn from a class distribution.The theorem presents the p = 0 case, with extensions to other small p described as straightforward.
With the stated probability, either the sampled point is misclassified or it can be perturbed into another class by modifying at most ϵ pixels.The perturbed point remains inside the unit hypercube.

6 WHAT IF WE JUST SHOW THAT ADVERSARIAL EXAMPLES EXIST?

The paper also studies guarantees that adversarial examples exist for at least some points, rather than bounding their probability across a class. This yields tighter existence conditions under suitable support and class-volume assumptions.

Tighter bounds are possible when the analysis only requires adversarial examples for some data points in a class.This removes the need to bound the probability of the event.
Theorem 4 gives a condition ensuring that some point with positive class probability admits an ϵ-adversarial example.The condition is stated for a class occupying a fraction fc < 1 of the cube.
For ℓ2 perturbations, the existence bound becomes active when the class support is sufficiently large relative to exp(−πϵ2).The bound is active whenever the support volume exceeds 1/(2e^πn), including supports containing a hypercube with side length at least e^−π ≈ 0.043.
An active bound does not by itself imply that adversarial examples occur at a small perturbation size.The paper explicitly distinguishes non-vacuity from practical small-ϵ vulnerability.

7 DISCUSSION: CAN WE ESCAPE FUNDAMENTAL BOUNDS?

The theoretical guarantees have several escape routes, including extreme class densities, abstention, dimensionality reduction, and computational difficulty. These routes can limit the guarantees or prevent attacks in practice without eliminating adversarial examples theoretically.

The guarantees can be escaped when class density functions take extremely large values, corresponding to exponentially large Uc.The paper treats the dependence of Uc on dimensionality separately.
Low-dimensional data manifolds may have measure-zero support and infinite density, requiring separate treatment of the theoretical arguments.The paper discusses expanding such manifolds with bounded uniform pixel noise to obtain positive volume.
A classifier allowed to return “I don’t know” can avoid some existence guarantees because its labeled region may be very small.An adversary could still degrade performance by perturbing images into the abstention class.
Feature squeezing may improve robustness if reducing dimensionality does not substantially increase Uc or reduce accuracy.The paper lists auto-encoders, JPEG encoding, and quantization as possible implementations.
Computational hardness can prevent attacks in practice even when adversarial examples still exist.Possible sources include local flatness, obscurity of the classifier function, and other computational difficulties.

8 EXPERIMENTS & EFFECT OF DIMENSIONALITY

Experiments test how dimensionality and data complexity relate to adversarial susceptibility. They show that dimensionality alone does not determine fundamental robustness: training effects and the data distribution, especially image complexity, are central.

Dimensionality and training: High-dimensional classifiers are often perceived as more susceptible, but the experiments separate dimensionality effects from properties of the data distribution.The study uses big MNIST, formed by replacing each pixel with a b × b identical array.
Dimensionality and training: For naturally trained classifiers, increased dimensionality is associated with lower robustness, but this relationship reflects weaknesses of training rather than a fundamental dimensionality limit.Theorem 5 says the fundamental limits for big MNIST do not depend non-trivially on dimensionality.
Dimensionality and training: Theorem 5 states that scaling MNIST images by factor b scales the adversarial perturbation radius by b while preserving the susceptibility probability.The result applies across classifiers on the original and b-MNIST distributions.
Dimensionality and training: Fooling big MNIST is therefore equally hard or easy as fooling original MNIST when perturbation size is scaled to match resolution.For 56 × 56 versus 28 × 28 images, the required ℓ2 perturbation is predicted to be twice as large.
Adversarial training: Adversarially trained classifiers exhibit susceptibility curves predicted by Theorems 2 and 5, including phase-transition behavior near a critical ϵ.The 112×112 curve is twice as wide as the 56×56 curve, which is twice as wide as the 28×28 curve.
Image complexity: CIFAR-10 is far more susceptible than similarly dimensional big MNIST because its higher image complexity lowers the concentration bound Uc.The compared datasets have dimensions 3072 and 3136 and both contain 10 classes.

9 SO...ARE ADVERSARIAL EXAMPLES INEVITABLE?

Adversarial-example inevitability is ill-posed: robustness has unavoidable limits that depend on the dataset, adversary strength, and perturbation metric. Exact limits for real-world image distributions remain unknowable, and complex high-dimensional classes may be less robust than intuition suggests.

Any classification problem has a fundamental robustness limit that no classifier can escape.
These limits depend on dataset properties, adversary strength, and the metric used to measure perturbations.
Exact properties of real-world image distributions and the resulting limits of adversarial training cannot be known.
Complex image classes in high-dimensional spaces may face robustness limits worse than intuition suggests.

A PROOF OF LEMMA 3

The proof of Lemma 3 transfers Gaussian isoperimetric results to the unit cube through a mapping between Gaussian and uniform variables, then applies inequalities to derive the needed bound.

The proof begins with a tight Gaussian isoperimetric inequality and uses it to establish results for the cube.The cube results are obtained by mapping uniform cube variables to Gaussian vectors.
The standard Gaussian density and its cumulative distribution are defined for the proof's measure-theoretic setup.
A mapping Φ sends Gaussian vectors to uniform vectors in the unit cube while preserving the corresponding measure relationship.

B PROOF OF LEMMA 4

The proof of Lemma 4 combines Talagrand-style bounds with geometric expansion arguments to bound safe regions and derive adversarial-example guarantees for classifier regions.

The proof uses Talagrand's method, including induction on dimension, slicing, Markov bounds, and optimized constants.
For a classifier region covering at least half the cube, Lemma 3 bounds its perturbation expansion.
The derived bounds include 2πϵn^1/2−1/p∗ for Theorem 2 and 2Uc exp(−ϵ^2/n) for Theorem 3.
The safe region contains correctly classified points protected from perturbations, but its volume and class-distribution mass are bounded.

D PROOF OF THEOREM 4

The proof of Theorem 4 bounds the expansion of a class-support set using Lemma 3, then identifies conditions under which the guarantee of adversarial examples is non-vacuous and relates results across image resolutions.

If a class support expands beyond half the cube while occupying less than half, it must overlap other classes and contain adversarial examples.
For p > 0, the proof bounds support expansion by approximating Φ^-1(η) and substituting the approximation into Lemma 3.
The p = 0 case uses a separate bound from the proof of Lemma 3.
The resulting bound gives a non-vacuous adversarial-example guarantee when its stated condition holds.
Upsampling and downsampling constructions relate susceptibility bounds for high- and low-resolution MNIST classifiers.