Adversarial vulnerability for any classifier

Alhussein Fawzi; Hamza Fawzi; Omar Fawzi

Source-linked AI summary

Adversarial vulnerability for any classifier

Alhussein Fawzi, Hamza Fawzi, Omar Fawzi

arXiv:1802.08686v2Feb 23, 2018cs.LGcs.CRcs.CVstat.ML

TL;DR

State-of-the-art classifiers can be fooled by small adversarial perturbations, motivating a theory of robustness under smooth generative models. The paper derives classifier-independent bounds and transferable perturbations, then shows that these bounds provide informative robustness baselines and constrain desirable generative-model properties.

Problem
Classifiers remain vulnerable to small, often imperceptible adversarial perturbations, while existing robustness techniques can fail under stronger attacks or more complex datasets.
Method
The paper analyzes arbitrary classifiers when data are generated by a smooth latent-to-image model, defining robustness both on and off the data manifold.
Results
The paper derives upper bounds on any classifier’s robustness, proves transferable perturbations, and finds that the bounds form informative baselines, including a 10% image-magnitude bound for a significant portion of CIFAR-10 points.
Takeaways & Limitations
Robust classifiers should have linear latent-space decision boundaries, while generative models may need low-dimensional or non-smooth structure to remain compatible with human robustness.
Takeaways & Limitations
The conclusions assume smooth generative modeling and indicate that higher latent dimensions can produce very small robustness bounds for more complex datasets.

Abstract

from arXiv · show

Despite achieving impressive performance, state-of-the-art classifiers remain highly vulnerable to small, imperceptible, adversarial perturbations. This vulnerability has proven empirically to be very intricate to address. In this paper, we study the phenomenon of adversarial perturbations under the assumption that the data is generated with a smooth generative model. We derive fundamental upper bounds on the robustness to perturbations of any classification function, and prove the existence of adversarial perturbations that transfer well across different classifiers with small risk. Our analysis of the robustness also provides insights onto key properties of generative models, such as their smoothness and dimensionality of latent space. We conclude with numerical experimental results showing that our bounds provide informative baselines to the maximal achievable robustness on several datasets.

1 Introduction

The paper studies adversarial vulnerability for classifiers under smooth generative models, establishing robustness limits, transferable perturbations, and implications for generative-model structure.

The analysis derives upper bounds on the robustness achievable by any classifier, especially when the latent space is high dimensional.These bounds provide baselines for maximal achievable robustness and indicate vulnerability to very small perturbations.
The analysis relates classifier robustness to the linearity of decision boundaries in the latent space.
The paper proves that adversarial perturbations can transfer across different classifiers with small risk.This provides theoretical support for earlier empirical observations of transferable perturbations.
For any classifier with in-distribution robustness r, a classifier can be constructed with unconstrained robustness r/2.
Experiments on CIFAR-10 and SVHN show that the theoretical bounds provide informative baselines for maximal achievable robustness.
The results suggest that natural-image distributions require low-dimensional or non-smooth generative models if humans are robust to small perturbations.

2 Related work

Related work established adversarial-robustness limits for restricted classifier families and under strong distributional assumptions, while this paper studies arbitrary classifiers under a smooth generative procedure.

Earlier results found perturbations of magnitude O(1/√d) for certain classifier families when robustness to random noise is fixed.
Prior work also derived robustness limits for simple classification families and studied adversarial perturbations under strong assumptions on the data distribution.
This paper instead derives robustness bounds for any classification function under a generative model mapping latent representations to images.
Proposed defenses include adversarial training, robust optimization, regularization, distillation, and stochastic networks, but some fail against more complex attacks or datasets.

3 Definitions and notations

The paper models natural images through a smooth generator and defines robustness by the minimum image-space distance needed to change a classifier’s decision, either along or beyond the data manifold.

The generative model maps latent vectors z ∈ R^d to images in R^m, with z sampled from a standard Gaussian distribution.The generated image is g(z), representing the modeled natural-image distribution.
In-distribution robustness measures the smallest perturbation that changes classification while keeping the perturbed image in the generator’s image.
Unconstrained robustness measures the smallest arbitrary image-space perturbation that changes classification without requiring the perturbed image to remain in the data distribution.
Unconstrained robustness is no greater than in-distribution robustness, expressed as r_unc(x) ≤ r_in(x).
The generator is assumed to satisfy a monotone invertible modulus-of-continuity condition, which is milder than Lipschitz continuity.
Smooth generators are commonly assessed by whether straight latent-space paths produce gradual semantic changes between endpoint images.

4 Analysis of the robustness to perturbations

Theorem 1 bounds the robustness of arbitrary classifiers under smooth generative models, showing that high-dimensional latent spaces permit small adversarial perturbations. The analysis also characterizes class-count effects, latent-space linearity, transferability, and approximate generators.

Upper bounds: Theorem 1 bounds the fraction of datapoints with robustness below η for any classification function, without restricting the classifier family.The bound follows from the Gaussian isoperimetric inequality.
Upper bounds: High latent dimension and generator smoothness imply that arbitrary classifiers are vulnerable to small adversarial perturbations.For Lipschitz generators, the relevant scale is controlled by the Lipschitz constant relative to typical image norms.
Dependence on classes: The upper-bound misclassification probability increases with the number of classes, making adversarial perturbations easier to find beyond binary classification.For approximately modeled distributions, the corresponding robustness bound decreases logarithmically as K grows.
Latent-space geometry: The robustness bound is attained when the classifier induces linearly separable regions in latent space, linking maximal robustness to latent-space linearity.With inequality-based smoothness, the bound is approached more closely when f ◦ g is linear.
In-distribution and unconstrained robustness: A nearest-neighbor modification preserves a classifier’s behavior, risk, and in-distribution robustness while achieving unconstrained robustness at least r/2.Thus, classification-agnostic limits for the two robustness notions are essentially the same.
Approximate generative models: When the true distribution is approximated by a smooth generative model in 1-Wasserstein distance, arbitrary classifiers still have small adversarial examples in expectation.The bound decreases with K and can approach zero under continuity of ω at 0, although only logarithmically.

5 Experimental evaluation

Experiments on SVHN and CIFAR-10 evaluate the theoretical robustness bounds against empirical robustness across generative and classifier settings. The bounds are informative baselines, especially in latent space, while image-space bounds can be conservative.

The SVHN experiments use a DCGAN with latent dimension d = 100 and evaluate several neural-network classifier architectures.Robustness estimates do not require ground-truth labels because they measure changes in estimated labels.
On SVHN, the latent-space upper bound is of the same order of magnitude as empirical robustness across tested classifiers.This suggests the isoperimetric inequality provides a reasonable baseline for best-classifier robustness in latent space.
On SVHN, the image-space bound predicts normalized robustness of 0.36, approximately one-third of the image norm, and remains non-vacuous.The theoretical prediction is one order of magnitude larger than empirical image-space estimates.
The SVHN comparison shows a large in-distribution versus unconstrained robustness gap for LeNet, while more complex classifiers produce smaller gaps.For ResNet-101, the multiplicative gap approaches 2, with in-distribution robustness 3.1 × 10^-2 and out-distribution robustness 1.4 × 10^-2.
For CIFAR-10, the bounds predict perturbations no larger than one-tenth of the image norm for 25% of datapoints.The experiment uses a DCGAN with d = 100 and state-of-the-art deep neural-network classifiers.

6 Discussion

The paper establishes a robustness ceiling for classifiers under smooth generative models and uses it as a benchmark for progress. It also links robustness to latent-space geometry while noting modeling assumptions and perceptibility limits.

No classifier can surpass the baseline robustness when the data distribution is approximable by a generative model mapping latent representations to images.
The bounds provide informative numerical baselines: on CIFAR-10, a perturbation with magnitude 10% that of an image can fool a significant portion of datapoints.Existing classifiers do not match the derived upper bound.
More robust classifiers should have linear decision boundaries in latent space, whereas multiple disconnected classification regions are more prone to small perturbations.
The analysis suggests that sufficiently high-dimensional, smooth generative models may conflict with the premise that human visual classifiers require large-norm perturbations to be fooled.The paper notes that current latent dimensions such as d = 100 do not create a contradiction, while higher dimensions might.
The derived results bound perturbation norm rather than human perceptibility, which is substantially harder to quantify.

A.1 Useful results

The appendix develops Gaussian-measure tools and applies them to latent preimages of classification regions. Gaussian isoperimetry converts latent-space neighborhoods into probability bounds that support robustness results.

Gaussian isoperimetric expansion lower-bounds the measure of an η-neighborhood: if ν_d(A) = Φ(a), then ν_d(Aη) ≥ Φ(a + η).
For each class, the proof maps image-space vulnerable regions back to latent space and enlarges competing class preimages by ω^-1(η).The smoothness mapping g transfers the resulting latent-space neighborhood bound back to image-space perturbation probabilities.
Disjoint latent class regions allow the individual Gaussian-measure lower bounds to be combined across classes.
The class-count-dependent robustness bound follows by substituting an explicit Gaussian CDF bound into the general result.
The appendix derives the unconstrained robustness construction by selecting a latent-generated class-changing point and using the triangle inequality to control image-space distance.
For two classifiers, intersecting their high-probability class regions and applying Gaussian isoperimetry yields latent perturbations that change both classifiers’ predictions.

A.5 Proof of Theorem 4

The proof bounds in-distribution robustness through latent-space class-changing distances, then extends the argument to approximate generative models using a Wasserstein coupling.

For δ = 0, latent robustness is bounded through the minimum latent displacement r_Z(z) that changes the classifier’s prediction.The image-space in-distribution robustness satisfies r_in(g(z)) ≤ ω(r_Z(z)).
Jensen’s inequality transfers the expected latent robustness bound through the generator’s smoothness function ω.
Under equiprobable classes, the Gaussian class-mass parameter becomes a(K) = Φ^-1(1 − 1/K), making the dependence on the number of classes explicit.
For an approximating generator within Wasserstein distance δ, a coupling constructs a nearby sample that is classified differently from the original sample.
The construction combines coupling distance with the classifier’s minimum changing perturbation, yielding the stated robustness relation for the approximate model.

B Toy example: tightness of Theorem 1

The checkerboard latent partition provides a toy case where vulnerability approaches one rapidly as perturbation size grows. Its behavior is substantially worse than the general theorem’s bound and illustrates the role of disconnected regions.

The checkerboard example partitions latent space into alternating unit-cell regions, with B1 defined by the parity of the summed coordinate floors.
1 − (1 − η)^d lower-bounds the probability that a point lies within η of the opposite checkerboard class.
The checkerboard fooling probability converges to 1 much faster as η increases than the general result in Theorem 1.
Many disconnected classification regions can therefore make a classifier substantially more vulnerable than a classifier linear in latent space.
Figure 3 compares the general Theorem 1 lower bound with the checkerboard Eq. 11 lower bound as functions of η.
The experiments use DCGAN-based generative models and multiple classifier architectures on SVHN and CIFAR-10.

C.2 Numerical evaluation of the upper bound

The numerical evaluation replaces the exact modulus of continuity with a high-probability version and incorporates its error into the robustness bound. It estimates the bound by optimizing latent-space image changes over sampled latent vectors, with δ selected for the best bound.

Probabilistic bound: The probabilistic modulus of continuity relaxes the requirement from all latent pairs to pairs satisfying the condition with high probability.The resulting bound explicitly accounts for the relaxation through an additive κ probability term.
Probabilistic bound: κ = 0 recovers Theorem 1 exactly, whereas κ > 0 adds κ to the probability bound in Eq. (13).
Numerical procedure: For a fixed target probability of 0.25, δ can be chosen to produce the best valid upper bound.The bound in Eq. (13) remains valid for every δ.
Numerical procedure: For each sampled z_i, gradient descent estimates the largest image-space change over latent points within Euclidean distance δ.The optimization computes sup over z′ satisfying ∥z_i−z′∥2≤δ of ∥g(z_i)−g(z′)∥.
Numerical procedure: Algorithm 1 samples z_i from N(0, I_d), estimates the empirical quantile α of the optimized values, and returns α as the numerical upper bound.The procedure uses the target probability after subtracting the theorem-based probability p_u(δ).
Illustration: Figure 4 shows generated SVHN images beside in-distribution perturbations that fool a ResNet-18 classifier, with estimated labels displayed above each image.