Adversarial Examples

An adversarial example is an input that has been changed by a small, deliberately computed perturbation so that a trained model gets it wrong, although a person sees no difference, or no difference that matters, from the original. For image classification, changing every pixel by a few grey levels in the right direction can make a neural network that is accurate on its test set misclassify the image with high confidence. The phenomenon matters for two reasons. It is a security problem wherever a classifier’s decision has consequences and an adversary can touch the input, and it is a scientific one, since it shows that test-set accuracy says little about how a model behaves just off the data. This article covers why adversarial examples exist (the linear explanation), how the size of a perturbation is measured (threat models), the main attacks (FGSM, PGD, DeepFool, Carlini–Wagner, universal, physical and black-box attacks), the main defences (adversarial training and certified methods), why many defences that looked robust were not (gradient masking), how robustness is evaluated, and the trade-off between robustness and accuracy. Attacks are described here to explain the phenomenon and how defences are tested.

Definition

Given a classifier $c$, an image $x$ with true label $y$ and a distance $D$, an adversarial example is an $x'$ with $D(x, x') \le \varepsilon$ and $c(x') \ne y$ (Athalye, Carlini & Wagner, 2018, §2.2). The set of allowed $x'$, together with what the adversary knows about the model, is the threat model. For images, the distance is almost always an $L_p$ norm of the perturbation $\delta = x' - x$: $L_\infty$ bounds the change of every pixel (the CIFAR-10 evaluations cited below use $\varepsilon = 0.031$, which Athalye, Carlini and Wagner equate to 8/256 on images scaled to $[0, 1]$; 8/255 also rounds to 0.031), and $L_2$ bounds the total energy of the change. A targeted attack asks for a chosen wrong class, an untargeted one for any wrong class. A white-box adversary knows the architecture and weights; a black-box adversary can only query the model, sometimes receiving scores and sometimes only the top label.

Two related terms are distinct. Fooling images (Nguyen, Yosinski & Clune, 2015) are images unrecognizable to people, such as noise or regular patterns, that a network classifies with over 99% confidence; they are not small perturbations of real images. Natural adversarial examples, such as the ImageNet-A test set described in the ImageNet article, are unmodified photographs selected because classifiers get them wrong.

Intuition

A classifier is accurate if the points of each class mostly lie on the right side of its decision boundary. It is robust only if they also lie far from it, in every direction the threat model allows. An image has tens of thousands of pixels, so it has tens of thousands of directions in which to move. In high dimensions a random direction is nearly orthogonal to the normal of the decision boundary and hardly changes the score; the one direction that points straight at the boundary changes it a great deal. Adversarial examples are found by looking for that direction, usually with the gradient of the loss with respect to the input, the same quantity backpropagation computes for the weights.

The linear explanation, as the Deep Learning book (§7.13) summarizes Goodfellow, Shlens and Szegedy (2015), is that networks are built mostly from linear pieces and in some experiments behave almost linearly. If each input of a linear function $w^\top x$ changes by at most $\varepsilon$, the function can change by as much as $\varepsilon \lVert w \rVert_1$, which can be very large when $w$ is high-dimensional. Many small changes, each invisible, add up along the weight vector. The book also notes that purely linear models such as logistic regression cannot resist adversarial examples because they are forced to be linear, whereas networks can represent functions that are locally constant near the data.

Formal Definition

For a classifier with loss $\ell$, the adversarial (robust) loss at $(x, y)$ under an $L_p$ threat model of radius $\varepsilon$ is

$$\ell_\varepsilon(x, y) = \max_{\lVert \delta \rVert_p \le \varepsilon,\; x + \delta \in [0,1]^d} \ell(x + \delta, y),$$

and robust accuracy at $\varepsilon$ is the fraction of test images that are classified correctly for every allowed $\delta$. An attack finds a lower bound on the robust error (a perturbation that works); a certificate proves an upper bound (no perturbation within the radius works). The robust radius of $x$ is the smallest $\lVert \delta \rVert_p$ that changes the prediction; Moosavi-Dezfooli, Fawzi and Frossard (2016) call it the robustness of the classifier at $x$.

Adversarial training minimizes the expected adversarial loss instead of the ordinary one. In the form of Madry et al. (2018), as Athalye, Carlini and Wagner (2018, §5.1.1) write it,

$$\theta^\ast = \arg\min_\theta \; \mathbb{E}_{(x,y)} \Big[ \max_{\delta \in [-\varepsilon, \varepsilon]^N} \ell(x + \delta; y; F_\theta) \Big],$$

with the inner maximum approximated by an attack, usually projected gradient descent.

The linear case in closed form. For a binary linear classifier with score $f(x) = w^\top x + b$ and margin $m = s\,f(x)$, $s = \pm 1$ the true label, the worst $L_\infty$ perturbation of size $\varepsilon$ moves every pixel by $\varepsilon$ against $s \operatorname{sign}(w_j)$, so the worst margin is $m - \varepsilon \lVert w \rVert_1$ and the $L_\infty$ robust radius is $m / \lVert w \rVert_1$; inside the $[0, 1]$ box each pixel moves by $\min(\varepsilon, \text{room}_j)$ instead, which is still separable across pixels and solvable exactly (our derivation, which the example checks). Ignoring the box, the $L_2$ radius is $|f(x)| / \lVert w \rVert_2$, the distance to the hyperplane, which DeepFool’s closed form (Moosavi-Dezfooli et al., 2016, eq. 3) reaches by orthogonal projection. With the logistic loss the inner maximum of adversarial training is therefore $\log\big(1 + e^{-s f(x) + \varepsilon \lVert w \rVert_1}\big)$: robust training of a linear model adds an $L_1$ penalty on the weights inside the loss, a connection Wong and Kolter (2018, §2) attribute to Goodfellow et al. (2015).

History

Szegedy et al. (2014) reported the phenomenon for deep networks: according to the Deep Learning book’s summary, networks with human-level accuracy had a nearly 100% error rate on examples built by searching for a nearby input with a very different output. Several of the papers read for this article cite Biggio et al. (2013) alongside Szegedy et al. for the phenomenon. Goodfellow et al. (2015) proposed the linear explanation (Deep Learning book, §7.13) and, as Moosavi-Dezfooli et al. (2016) report, the fast gradient sign method; the Deep Learning book reproduces their GoogLeNet example: a panda classified as “panda” with 57.7% confidence becomes “gibbon” with 99.3% confidence after adding $0.007$ times the sign of the input gradient. Nguyen et al. (2015) produced fooling images with evolutionary algorithms and gradient ascent, and found that MNIST networks retrained to reject them could be fooled again by new ones. The years 2016 to 2018 added minimal-perturbation attacks (DeepFool), the optimization attack of Carlini and Wagner (2017), which Athalye, Carlini and Wagner (2018) list among the iterative attacks that became standard for evaluating defences, universal and physical perturbations, and black-box attacks, while many proposed defences were broken quickly; Wong and Kolter (2018) note that many ICLR 2018 defence papers were broken before the review period ended, citing Athalye, Carlini and Wagner (2018). Adversarial training, often with PGD (Madry et al., 2018), was in Cohen et al.’s (2019) words the most successful empirical defence to date, and certified defences that apply to trained networks, among them convex relaxations (Wong & Kolter, 2018) and randomized smoothing (Cohen et al., 2019, building on Lecuyer et al.), followed.

Attacks

FGSM

The fast gradient sign method of Goodfellow et al. (2015) takes one step of size $\varepsilon$ along the sign of the input gradient of the training loss $J$:

$$x' = x + \varepsilon \operatorname{sign}\big(\nabla_x J(\theta, x, y)\big),$$

as the Deep Learning book’s Figure 7.8 and Moosavi-Dezfooli et al. (2016, §4.1) state it. By Hölder’s inequality the sign is the best direction for an $L_\infty$ budget to first order: for a linear model it is the exact worst case, and for a network it is the worst case of the network’s linearization at $x$. It costs one gradient computation, but a single step can miss the worst case badly when the loss is curved; Moosavi-Dezfooli et al. report that FGSM’s perturbations were larger than DeepFool’s, by an order of magnitude on ILSVRC 2012.

PGD

Projected gradient descent iterates the step and projects back onto the threat set after each one: $x^{(k+1)} = P_S\big(x^{(k)} + \eta \nabla f(x^{(k)})\big)$, with the sign of the gradient for $L_\infty$ (Croce & Hein, 2020, §2), starting from $x$ or from a random point in the ball. It is the general projected gradient method applied to maximizing the loss over a box intersected with the ball. Croce and Hein call it the most popular method to test robustness, because it is cheap and works well in many cases, and identify two ways it fails: a fixed step size, and the cross-entropy loss, whose input gradient vanishes numerically once the predicted probability of the true class is close to 1, so that rescaling the logits of an otherwise identical classifier can defeat it (§4).

DeepFool and Carlini–Wagner

DeepFool (Moosavi-Dezfooli et al., 2016) looks for the smallest perturbation that changes the label, rather than the most damaging one of a given size. For an affine binary classifier this is the orthogonal projection onto the hyperplane, $r = -f(x)\, w / \lVert w \rVert_2^2$. For a general classifier DeepFool linearizes $f$ at the current point, takes that projection, and repeats until the label changes; in the multiclass case it projects onto the nearest of the linearized boundaries to the other classes. The final perturbation is multiplied by $1 + \eta$ with $\eta = 0.02$ to cross the boundary. The authors present it as a way to measure robustness, the average minimal perturbation over the test set, and reported smaller perturbations than FGSM on MNIST, CIFAR-10 and ILSVRC 2012 networks, and slightly smaller than Szegedy et al.’s method, which they ran on MNIST and CIFAR-10 only (Table 1); Cohen et al. (2019) used a DeepFool $L_2$ attack to bound the robust accuracy of an undefended network.

Carlini and Wagner (2017), whose paper was not read for this article, are described by the papers that use their attack. Athalye, Carlini and Wagner (2018, §2.5) use its Lagrangian relaxation for $L_2$ attacks. Croce and Hein (2020, eq. 5) give its margin loss, $-z_y + \max_{i \ne y} z_i$ on the logits $z$, which, unlike cross-entropy, has a direct interpretation in terms of the decision: if an adversarial example exists, its global maximum is positive. It is not invariant to rescaling the logits, and their own DLR loss divides this difference by a difference of logits so that it is invariant to both shifting and rescaling.

Universal perturbations

Moosavi-Dezfooli, Fawzi, Fawzi and Frossard (2017) found single, image-agnostic perturbations that fool a classifier on most natural images. Their algorithm runs through a set of images, adds the minimal DeepFool-style perturbation that fools each one not yet fooled, and projects the sum back onto an $L_p$ ball. Computed from 10,000 ILSVRC 2012 training images, an $L_\infty$ perturbation with $\xi = 10$ (against an average image $L_\infty$ norm of about 250) changed the label of more than 90% of validation images for CaffeNet and VGG-F; for CaffeNet, a universal perturbation of $L_2$ norm 2,000 fooled 85% of images while random vectors of the same norm fooled 10%. The perturbations also transferred: one computed for VGG-19 fooled every other network tested on more than 53% of images (Table 2). The authors explain the gap with random noise by correlations between the orientations of the decision boundary near different images; they note that the random perturbation needed to fool a point grows with the square root of the dimension times the minimal perturbation.

Physical perturbations and patches

A digital perturbation has to survive printing, viewing distance and angle, lighting and the camera before it matters physically. Athalye, Engstrom, Ilyas and Kwok (2018) introduced Expectation over Transformation (EOT): optimize the expected adversarial objective over a distribution of transformations (rescaling, rotation, lighting, noise, translation, and for 3D objects the rendering of the object at different poses). Their 1,000 two-dimensional examples were classified as the target class in 96.4% of random transformations on average (Table 1), and a 3D-printed turtle was classified as the randomly chosen target class, rifle, in 82% of the photographs taken of it. They also describe an adversarial patch, a small image patch that can be placed in any scene to cause a targeted misclassification, made by Brown et al. with EOT. Eykholt et al.’s Robust Physical Perturbations (2018) confined the perturbation to sticker-like regions on a road sign and optimized it over images of the sign at many distances and angles; the traffic sign recognition article gives their protocol and results.

Transfer and black-box attacks

Perturbations computed for one model often fool another, which Moosavi-Dezfooli et al. (2016) cite Szegedy et al. for and the universal-perturbation table above shows across architectures. A black-box adversary can exploit this by attacking a substitute network trained to imitate the target, or can estimate gradients from queries. Ilyas, Engstrom, Athalye and Lin (2018) cite work finding that substitute-network examples do not always transfer, especially for targeted attacks, and instead estimate the gradient from queries with natural evolution strategies, from the scores of Gaussian-perturbed copies of the image. Against an InceptionV3 ImageNet classifier with $L_\infty$ budget 0.05 and random target classes, their targeted attacks succeeded in 99.2% of cases with a median of 11,550 queries when all class probabilities were returned, 93.6% (median 49,624 queries) when only the top class’s probability was returned, and 90% (median $2.7 \times 10^6$ queries, on 100 images) when only the top label was returned (Table 1).

Defences and Their Evaluation

Adversarial training

The Deep Learning book credits training on adversarial examples, which can reduce the error on the original test set, to Szegedy et al. (2014) and Goodfellow et al. (2015), while Athalye, Carlini and Wagner (2018, §5.1.1) write that Goodfellow et al. originally proposed it. The book treats it as a regularizer that encourages the network to be locally constant around the training data. As Athalye, Carlini and Wagner describe it, Madry et al. (2018) solve the min–max problem above with a PGD inner maximization. Athalye, Carlini and Wagner (2018) could not reduce its claims and list it at 47% accuracy on CIFAR-10 at $L_\infty$ $\varepsilon = 0.031$ (Table 1); Croce and Hein (2020) describe it as one of the few approaches not defeated so far. It is expensive, since every training step runs an attack. TRADES (Zhang et al., 2019) decomposes the robust error into the natural error and a boundary error, the probability that a point is classified correctly but lies within $\varepsilon$ of the decision boundary, and minimizes a surrogate loss on clean predictions plus a term that penalizes the difference between the predictions on $x$ and on its adversarial version, weighted by $1/\lambda$. On CIFAR-10 at $\varepsilon = 0.031$ under a 20-step PGD attack, their Table 5 lists 87.30% natural and 47.04% robust accuracy for Madry et al.’s model and 84.92% and 56.61% for TRADES with $1/\lambda = 6$. The method was the basis of the winning entry of the NeurIPS 2018 Adversarial Vision Challenge. A related semi-supervised use, virtual adversarial training, makes the model’s own predicted labels stable under adversarial perturbations of unlabelled images (Deep Learning book, §7.13).

Gradient masking

Many defences stop gradient-based attacks from working without making the model robust. Athalye, Carlini and Wagner (2018) call this obfuscated gradients, a special case of gradient masking, and distinguish three kinds: shattered gradients from non-differentiable or numerically unstable operations, stochastic gradients from randomized defences, and vanishing or exploding gradients from defences that unroll an iterative procedure, such as projecting the input onto a generative model’s manifold. They give an attack for each: Backward Pass Differentiable Approximation (run the non-differentiable step forward, but replace it by a differentiable approximation, such as the identity, on the backward pass), EOT for randomness, and reparameterization. Of nine non-certified defences accepted at ICLR 2018, seven relied on obfuscated gradients; the abstract says the new attacks circumvented six completely and one partially, while the conclusion speaks of circumventing seven of nine. They list warning signs of masking: one-step attacks doing better than iterative ones, black-box attacks doing better than white-box ones, unbounded attacks not reaching 100% success, random sampling finding adversarial examples that gradient attacks miss, and success not increasing with the budget. Their recommendations are to state a precise threat model, make specific testable claims, release code and models, and evaluate against adaptive attacks, designed after the defence is fixed with full knowledge of it.

Evaluation: AutoAttack

Croce and Hein (2020) proposed a fixed protocol that needs no tuning per defence. AutoAttack combines two new PGD variants without a step-size parameter (APGD on the cross-entropy loss, and a targeted APGD on their scale-invariant DLR loss) with two existing attacks of a different kind: FAB, which minimizes the perturbation norm, and Square Attack, a score-based black-box random search. An image counts as broken if any of the four attacks succeeds. On 49 deterministic models from recent defence papers, AutoAttack’s robust accuracy was lower than the reported value in all but one case (§6), by more than 10% in 13 cases and more than 30% in 8; the introduction, counting over 50 classifiers including randomized defences, gives all except two, with the slightly more expensive AutoAttack+ better in all but one, and the abstract says all except one. The authors propose it as the minimal test for any new defence, not as the final word.

Certified defences

An empirical defence is only as good as the attacks tried against it. A certified defence proves, for each test image, that no perturbation within a radius changes the prediction. Exact verification with satisfiability or mixed-integer solvers is possible but, Cohen, Rosenfeld and Kolter (2019) note, had not been shown to scale beyond networks of about 100,000 activations.

Convex relaxations. Wong and Kolter (2018) bound the set of outputs reachable from an $L_\infty$ ball, the “adversarial polytope”, by a convex outer set. Given lower and upper bounds $\ell \le \hat z \le u$ on a ReLU’s input, they replace $z = \max(0, \hat z)$ by its convex hull, the triangle $z \ge 0$, $z \ge \hat z$, $-u \hat z + (u - \ell) z \le -u\ell$. If no point of the relaxed set changes the class, no real perturbation does. The resulting linear program has a dual that can be computed by a backward pass through a modified network, so the bound can be trained against. Their MNIST network ($\varepsilon = 0.1$) had 1.80% clean error and a certified robust error bound of 5.82%, where an ordinarily trained network reached 81.68% error under PGD (Table 1); training took about 5 hours for 100 epochs, two to three orders of magnitude more than ordinary training.

Randomized smoothing. Cohen, Rosenfeld and Kolter (2019) turn any base classifier $f$ into a smoothed classifier $g(x) = \arg\max_c P\big(f(x + \epsilon) = c\big)$ with $\epsilon \sim \mathcal{N}(0, \sigma^2 I)$. If the top class has probability at least $\underline{p_A}$ and every other class at most $\overline{p_B}$, then $g$ is constant within the $L_2$ radius

$$R = \frac{\sigma}{2}\Big(\Phi^{-1}(\underline{p_A}) - \Phi^{-1}(\overline{p_B})\Big),$$

where $\Phi^{-1}$ is the inverse standard normal CDF (Theorem 1), and the bound is tight when nothing else is known about $f$ (Theorem 2). The probabilities are estimated by Monte Carlo: their CERTIFY procedure guesses the top class from $n_0$ noisy samples, estimates a one-sided lower confidence bound on $p_A$ from $n$ further samples, sets $\overline{p_B} = 1 - \underline{p_A}$, and abstains unless the bound exceeds $1/2$; the certified radius is then $\sigma \Phi^{-1}(\underline{p_A})$, wrong with probability at most $\alpha$. Because all $n$ samples agreeing still give only $\underline{p_A} = \alpha^{1/n}$, large radii need many samples: by the authors’ estimate, certifying $4\sigma$ at 99.9% confidence would require about $10^5$. The base classifier is trained with Gaussian noise augmentation at the same $\sigma$. On ImageNet with a ResNet-50 base, they reported 49% approximate certified top-1 accuracy at $L_2$ radius 0.5 ($\sigma = 0.25$, 67% clean accuracy of the smoothed classifier), and 37% at radius 1.0 ($\sigma = 0.50$, 57% clean; Table 1), on a 500-image sample; they describe smoothing as the only certified approach shown feasible on full-resolution ImageNet at the time. For a linear base classifier, they show that $g = f$ and that the bound recovers the true radius $|w^\top x + b| / \lVert w \rVert_2$ (§3.1).

The robustness–accuracy trade-off

Robust models are usually less accurate on clean images. Zhang et al. (2019) construct an example where the Bayes-optimal classifier has 0% natural and 100% robust error while the all-one (constant) classifier has 50% of each, and cite Tsipras et al. (2019) for the statement that robustness can be at odds with accuracy without assumptions on the data distribution; Cohen et al. (2019) find that $\sigma$ controls such a trade-off for smoothing, which they relate to Tsipras et al.’s finding that adversarially trained networks with higher robust accuracy tend to have lower standard accuracy. The numbers above show the same: Madry et al.’s CIFAR-10 model is at 87% clean accuracy in Zhang et al.’s Table 5, where the ordinarily trained wide ResNet of Athalye, Carlini and Wagner (2018, §2.3) reaches 95%, and Cohen et al.’s smoothed ImageNet classifiers lose clean accuracy as $\sigma$ grows. Robustness to one threat model does not imply robustness to others: Athalye, Carlini and Wagner note, citing Sharma and Chen (2017), that training only on $L_\infty$ examples gives limited robustness under other distortion measures.

Examples

The code below works through the closed forms on a model small enough to solve exactly. It fits a logistic regression to synthetic $16 \times 16$ grayscale images in $[0, 1]$ of two classes: a bright disk (class 0) or a bright square of the same area (class 1), with radius 4–6 pixels, the centre jittered by up to 1.5 pixels, contrast 0.15–0.35 above a 0.5 background, and Gaussian noise of standard deviation 0.08. There are 2,000 training and 1,000 test images. Because the model is linear, every quantity has an exact value to check against. The script:

1. compares FGSM and PGD (a random start and 20 steps of $\varepsilon/4$) with the exact worst-case margin inside the $[0, 1]$ box, computes the exact $L_\infty$ radius of each test image and checks it from both sides, checks DeepFool against the exact $L_2$ radius, and tabulates accuracy under the exact attack and under random $\pm\varepsilon$ noise of the same $L_\infty$ size (20 draws);
2. renders new images (data seed 1) at 16, 32 and 64 pixels and refits the model at each resolution (the training scenes are the same at every size; the test scenes are not, because the noise drawn for the training images uses a size-dependent part of the random stream), and also evaluates the $16 \times 16$ model on its images upsampled by pixel replication, an identical classifier in more dimensions;
3. runs Cohen et al.’s CERTIFY ($\sigma = 0.25$, $n_0 = 100$, $\alpha = 0.001$, with a one-sided Clopper–Pearson bound, our choice of interval) on the first 500 test images for $n = 1{,}000$ and $10{,}000$, pushing every noisy image through the classifier, and compares it with the exact $L_2$ radius;
4. trains the model adversarially with the closed-form inner maximum $\log(1 + e^{-s f(x) + \varepsilon \lVert w \rVert_1})$ (no box during training, writing $w = u - v$ with $u, v \ge 0$ so that L-BFGS-B handles the $L_1$ term) and evaluates it with the exact box-constrained attack.

The output below comes from NumPy 2.3.5, SciPy 1.16.3 and scikit-learn 1.7.2, one data seed, on one thread; two runs gave identical output, and the script takes about 10 seconds.

import os
for v in ("OMP_NUM_THREADS", "OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS"):
    os.environ[v] = "1"                                   # fixed summation order
import numpy as np, scipy, sklearn
from scipy.optimize import minimize
from scipy.special import expit
from scipy.stats import beta, norm
from sklearn.linear_model import LogisticRegression

def render(n, size, rng):
    """Class 0: bright disk, class 1: bright square of equal area, on grey, in [0, 1]."""
    y = rng.integers(0, 2, n)
    s = size / 16                                         # geometry defined on a 16x16 grid
    r = rng.uniform(4, 6, n) * s                          # disk radius
    h = r * np.sqrt(np.pi) / 2                            # square half-side (same area)
    cx, cy = rng.uniform(-1.5, 1.5, (2, n)) * s + size / 2
    c = rng.uniform(0.15, 0.35, n)                        # contrast over the 0.5 background
    g = (np.arange(4 * size) + 0.5) / 4                   # 4x4 supersampling grid
    X, Y = np.meshgrid(g, g)
    out = np.empty((n, size, size))
    for i in range(n):
        if y[i] == 0:
            inside = (X - cx[i]) ** 2 + (Y - cy[i]) ** 2 <= r[i] ** 2
        else:
            inside = (abs(X - cx[i]) <= h[i]) & (abs(Y - cy[i]) <= h[i])
        out[i] = 0.5 + c[i] * inside.reshape(size, 4, size, 4).mean(axis=(1, 3))
    out += rng.normal(0, 0.08, out.shape)                 # sensor noise
    return np.clip(out, 0, 1).reshape(n, -1), y

def margin(X, y, w, b):                                   # > 0 when correctly classified
    return (2 * y - 1) * (X @ w + b)

def room(X, y, w):                                        # how far each pixel can move against the class
    return np.where(-(2 * y - 1)[:, None] * np.sign(w) > 0, 1 - X, X)

def exact_worst_margin(X, y, w, b, eps):
    """Margin after the best L_inf attack of size eps inside the [0, 1] box (closed form)."""
    return margin(X, y, w, b) - (np.abs(w) * np.minimum(eps, room(X, y, w))).sum(1)

def exact_linf_radius(X, y, w, b):
    """Smallest eps whose best attack reaches margin 0: the margin is piecewise linear in eps."""
    m, R = margin(X, y, w, b), room(X, y, w)
    order = np.argsort(R, 1)
    r = np.take_along_axis(R, order, 1)
    a = np.abs(w)[order]
    A = a.sum(1, keepdims=True)
    used = np.hstack([np.zeros((len(X), 1)), np.cumsum(a * r, 1)])   # pixels already at the box
    slope = np.hstack([A, A - np.cumsum(a, 1)])                      # weight of the others
    lo = np.hstack([np.zeros((len(X), 1)), r])
    hi = np.hstack([r, np.full((len(X), 1), np.inf)])
    with np.errstate(divide="ignore", invalid="ignore"):
        e = (m[:, None] - used) / slope
    ok = (slope > 1e-15) & (e >= lo) & (e <= hi)
    eps = np.where(ok.any(1), e[np.arange(len(X)), ok.argmax(1)], np.inf)
    return np.where(m <= 0, 0.0, eps)

def loss_grad_x(X, y, w, b):                              # d(logistic loss)/dx for each image
    s = 2 * y - 1
    return (-s * expit(-s * (X @ w + b)))[:, None] * w

def fgsm(X, y, w, b, eps):
    return np.clip(X + eps * np.sign(loss_grad_x(X, y, w, b)), 0, 1)

def pgd(X, y, w, b, eps, rng, steps=20):
    Z = np.clip(X + rng.uniform(-eps, eps, X.shape), 0, 1)           # random start
    for _ in range(steps):
        Z = Z + eps / 4 * np.sign(loss_grad_x(Z, y, w, b))
        Z = np.clip(np.clip(Z, X - eps, X + eps), 0, 1)              # project: ball, then box
    return Z

def fit_robust(X, y, eps, C=1.0):
    """Adversarial training of logistic regression: the inner max is closed form,
    loss = softplus(-s (w.x + b) + eps ||w||_1); solved with w = u - v, u, v >= 0."""
    s, d = 2 * y - 1, X.shape[1]
    def f(p):
        u, v, b = p[:d], p[d:2 * d], p[-1]
        w = u - v
        z = -s * (X @ w + b) + eps * (u + v).sum()
        g = expit(z)
        gw = -X.T @ (g * s) + w / C
        return (np.logaddexp(0, z).sum() + w @ w / (2 * C),
                np.concatenate([gw + eps * g.sum(), -gw + eps * g.sum(), [-(g * s).sum()]]))
    res = minimize(f, np.zeros(2 * d + 1), jac=True, method="L-BFGS-B",
                   bounds=[(0, None)] * (2 * d) + [(None, None)],
                   options={"maxiter": 20000, "ftol": 1e-14, "gtol": 1e-10})
    return res.x[:d] - res.x[d:2 * d], res.x[-1], res.success

print(f"numpy {np.__version__}, scipy {scipy.__version__}, scikit-learn {sklearn.__version__}")
rng = np.random.default_rng(0)
Xtr, ytr = render(2000, 16, rng)
Xte, yte = render(1000, 16, rng)
print(f"data: {Xtr.shape[1]} pixels, class-1 share train {ytr.mean():.3f} test {yte.mean():.3f}, "
      f"pixel range [{Xtr.min():.3f}, {Xtr.max():.3f}], clipped {np.mean((Xtr == 0) | (Xtr == 1)):.4f}")
clf = LogisticRegression(C=1.0, max_iter=5000).fit(Xtr, ytr)
w, b = clf.coef_[0], clf.intercept_[0]
m = margin(Xte, yte, w, b)
print(f"plain logistic regression: test accuracy {np.mean(m > 0):.3f}")

# 1. Attacks against the closed form
rng2 = np.random.default_rng(2)
grid = [0.005, 0.01, 0.02, 0.04, 0.08, 0.16]
d_fgsm = max(np.abs(margin(fgsm(Xte, yte, w, b, e), yte, w, b) - exact_worst_margin(Xte, yte, w, b, e)).max() for e in grid)
d_pgd = max(np.abs(margin(pgd(Xte, yte, w, b, e, rng2), yte, w, b) - exact_worst_margin(Xte, yte, w, b, e)).max() for e in grid)
print(f"max |margin - exact worst-case margin| over the eps grid: FGSM {d_fgsm:.1e}, PGD {d_pgd:.1e}")
eps_star = exact_linf_radius(Xte, yte, w, b)
c = m > 0
above = np.array([exact_worst_margin(Xte[i:i + 1], yte[i:i + 1], w, b, eps_star[i] * (1 + 1e-6))[0] < 0 for i in np.where(c)[0]])
below = np.array([exact_worst_margin(Xte[i:i + 1], yte[i:i + 1], w, b, eps_star[i] * (1 - 1e-6))[0] > 0 for i in np.where(c)[0]])
print(f"exact L_inf radius: flips just above it {above.mean():.3f}, holds just below it {below.mean():.3f}; "
      f"median {np.median(eps_star[c]):.4f} = {255 * np.median(eps_star[c]):.2f}/255")
f_te = Xte @ w + b
R2 = np.abs(f_te) / np.linalg.norm(w)                                # exact L2 radius (no box)
r_df = -(f_te / (w @ w))[:, None] * w * 1.02                          # DeepFool, binary linear case
print(f"DeepFool L2: max |norm/exact radius - 1.02| {np.abs(np.linalg.norm(r_df, axis=1) / R2 - 1.02).max():.1e}, "
      f"flips {np.mean(np.sign(Xte @ w + b) != np.sign((Xte + r_df) @ w + b)):.3f}")
print("eps     exact attack  random sign noise   (test accuracy)")
for e in [0.0] + grid:
    adv = np.mean(exact_worst_margin(Xte, yte, w, b, e) > 0)
    rnd = np.mean([np.mean(margin(np.clip(Xte + e * rng2.choice([-1, 1], Xte.shape), 0, 1), yte, w, b) > 0)
                   for _ in range(20)])
    print(f"{e:5.3f}   {adv:12.3f}  {rnd:17.3f}")

# 2. Resolution: the same scenes rendered at 16, 32 and 64 pixels
print("size  test acc  median eps* (refit)  median eps* (16x16 model, replicated)  ||w||1/||w||2  sqrt(d)")
for size in [16, 32, 64]:
    k = size // 16
    rs = np.random.default_rng(1)
    Xs, ys = render(2000, size, rs)
    Xst, yst = render(1000, size, rs)
    cs = LogisticRegression(C=1.0, max_iter=5000).fit(Xs, ys)
    ws, bs = cs.coef_[0], cs.intercept_[0]
    ok = margin(Xst, yst, ws, bs) > 0
    w_rep = np.kron(w.reshape(16, 16), np.ones((k, k))).ravel() / k ** 2   # identical classifier
    X_rep = np.kron(Xte.reshape(-1, 16, 16), np.ones((1, k, k))).reshape(len(Xte), -1)
    e_rep = exact_linf_radius(X_rep, yte, w_rep, b)
    print(f"{size:4d}  {ok.mean():8.3f}  {np.median(exact_linf_radius(Xst, yst, ws, bs)[ok]):19.5f}"
          f"  {np.median(e_rep[c]):37.5f}  {np.abs(ws).sum() / np.linalg.norm(ws):13.1f}  {np.sqrt(ws.size):7.0f}"
          f"   (replicated - 16x16: {np.abs(e_rep - eps_star)[c].max():.1e})")

# 3. Randomized smoothing (Cohen et al.'s CERTIFY) against the exact L2 radius
sigma, alpha, n0 = 0.25, 0.001, 100
Xs5, ys5, R5 = Xte[:500], yte[:500], R2[:500]
f_pred = (Xs5 @ w + b > 0).astype(int)
for n in [1000, 10000]:
    cert = np.zeros(500); pred = np.full(500, -1)
    for i in range(500):
        votes0 = ((Xs5[i] + sigma * rng2.standard_normal((n0, 256))) @ w + b > 0)
        cA = int(votes0.mean() > 0.5)                                 # selection sample
        votes = ((Xs5[i] + sigma * rng2.standard_normal((n, 256))) @ w + b > 0)
        k_A = int(np.sum(votes == cA))
        pA_low = beta.ppf(alpha, k_A, n - k_A + 1) if k_A > 0 else 0.0   # one-sided Clopper-Pearson
        if pA_low > 0.5:
            cert[i], pred[i] = sigma * norm.ppf(pA_low), cA
    done = pred >= 0
    right = done & (pred == ys5)
    print(f"n={n:5d}: abstain {np.mean(~done):.3f}, smoothed prediction != f(x) {np.sum(pred[done] != f_pred[done])}, "
          f"certified > exact radius {np.sum(cert[done] > R5[done] + 1e-12)}, median certified/exact {np.median(cert[right] / R5[right]):.3f}")
    for r in [0.05, 0.1, 0.2]:
        print(f"   radius {r:.2f}: certified accuracy {np.mean(right & (cert > r)):.3f}   exact robust accuracy "
              f"{np.mean((margin(Xs5, ys5, w, b) > 0) & (R5 > r)):.3f}")

# 4. Adversarial training with the closed-form inner maximum
print("train eps  clean  robust@0.005  robust@0.01  robust@0.02  nonzero weights  converged")
for et in [0.0, 0.005, 0.01, 0.02, 0.04]:
    wt, bt, conv = fit_robust(Xtr, ytr, et)
    er = exact_linf_radius(Xte, yte, wt, bt)
    print(f"{et:9.3f}  {np.mean(margin(Xte, yte, wt, bt) > 0):5.3f}  {np.mean(er > 0.005):12.3f}  {np.mean(er > 0.01):11.3f}"
          f"  {np.mean(er > 0.02):11.3f}  {np.sum(np.abs(wt) > 1e-8):15d}  {conv}")

Output:

numpy 2.3.5, scipy 1.16.3, scikit-learn 1.7.2
data: 256 pixels, class-1 share train 0.521 test 0.469, pixel range [0.132, 1.000], clipped 0.0013
plain logistic regression: test accuracy 0.887
max |margin - exact worst-case margin| over the eps grid: FGSM 2.3e-14, PGD 2.3e-14
exact L_inf radius: flips just above it 1.000, holds just below it 1.000; median 0.0107 = 2.74/255
DeepFool L2: max |norm/exact radius - 1.02| 2.2e-16, flips 1.000
eps     exact attack  random sign noise   (test accuracy)
0.000          0.887              0.887
0.005          0.718              0.887
0.010          0.475              0.888
0.020          0.095              0.883
0.040          0.000              0.869
0.080          0.000              0.826
0.160          0.000              0.735
size  test acc  median eps* (refit)  median eps* (16x16 model, replicated)  ||w||1/||w||2  sqrt(d)
  16     0.896              0.01063                                0.01073           12.3       16   (replicated - 16x16: 0.0e+00)
  32     0.984              0.00945                                0.01073           24.8       32   (replicated - 16x16: 6.9e-17)
  64     0.996              0.00915                                0.01073           49.5       64   (replicated - 16x16: 1.7e-16)
n= 1000: abstain 0.130, smoothed prediction != f(x) 0, certified > exact radius 1, median certified/exact 0.766
   radius 0.05: certified accuracy 0.624   exact robust accuracy 0.744
   radius 0.10: certified accuracy 0.414   exact robust accuracy 0.566
   radius 0.20: certified accuracy 0.096   exact robust accuracy 0.176
n=10000: abstain 0.082, smoothed prediction != f(x) 0, certified > exact radius 0, median certified/exact 0.922
   radius 0.05: certified accuracy 0.704   exact robust accuracy 0.744
   radius 0.10: certified accuracy 0.528   exact robust accuracy 0.566
   radius 0.20: certified accuracy 0.148   exact robust accuracy 0.176
train eps  clean  robust@0.005  robust@0.01  robust@0.02  nonzero weights  converged
    0.000  0.885         0.717        0.476        0.095              256  True
    0.005  0.878         0.761        0.616        0.293              114  True
    0.010  0.830         0.751        0.639        0.415               61  True
    0.020  0.571         0.548        0.514        0.467                8  True
    0.040  0.469         0.469        0.469        0.469                0  True

Attacks. FGSM and PGD reach the exact worst case to rounding error, because for a linear model the gradient’s sign is the same everywhere, so one clipped step already moves each pixel to the end of its allowed range; DeepFool likewise lands exactly 2% beyond the hyperplane. Half of the correctly classified test images change class when each pixel moves by less than 3 grey levels out of 255, and at 0.04 (about 10 grey levels) none survive. Random noise of the same size does almost nothing: even at 0.16, fifteen times the median radius, accuracy is still 0.735. This is the linear explanation in numbers. The attack lowers the margin by $\varepsilon \lVert w \rVert_1$, while random signs shift it by a sum whose standard deviation is about $\varepsilon \lVert w \rVert_2$ (ignoring the box), and $\lVert w \rVert_1 / \lVert w \rVert_2$ is 12.3 for the $16 \times 16$ model refitted in the resolution table below.

Resolution. The needed $\varepsilon$ did not fall with resolution in this example, except slightly after refitting. For the identical classifier on replicated pixels it is exactly unchanged, since each weight is divided by $k^2$ and $\lVert w \rVert_1$ stays the same; in our reading, the Deep Learning book’s argument that $\varepsilon \lVert w \rVert_1$ is large for high-dimensional $w$ needs weights that do not shrink as the dimension grows. After refitting on natively rendered images the median radius drops by about 14% from 16 to 64 pixels while accuracy rises to 0.996. What does grow with dimension is $\lVert w \rVert_1 / \lVert w \rVert_2$, close to doubling with each doubling of the side (it can be at most $\sqrt{d}$): at higher resolution, the worst-case direction is ever more effective compared with a random direction of the same per-pixel size, in our reading the $L_\infty$ counterpart of Moosavi-Dezfooli et al.’s (2017) statement that the random perturbation needed to fool a point grows like $\sqrt{d}$ times the minimal one.

Certification. For a linear model the exact radii above are certificates: no perturbation smaller than $\varepsilon^\ast$ can change the label, and none larger than it fails to. Randomized smoothing certifies smaller radii, as its guarantee must: with 10,000 samples the median certified radius is 92% of the exact one, with 1,000 samples 77%, and certified accuracy at each radius is correspondingly below the exact robust accuracy. The smoothed prediction agreed with the linear model wherever it did not abstain, as expected, since Cohen et al. show that smoothing a linear classifier leaves it unchanged. One certified radius out of 500 exceeded the exact one at $n = 1{,}000$, a failure the guarantee allows with probability $\alpha$ per image. The planned check that CERTIFY would abstain on 0.042 ± 0.03 of the images at $n = 10{,}000$ failed: it abstained on 0.082. The planned value was computed from the expected counts of the $n$ estimation samples and left out the $n_0 = 100$ selection step, in which near-boundary images can be assigned the wrong class and then abstain.

Adversarial training. The robust objective adds $\varepsilon \lVert w \rVert_1$ inside the loss, and the fits show the two consequences. Robust accuracy at the training budget rises above the ordinary model’s (0.761 against 0.717 at 0.005, 0.639 against 0.476 at 0.01, 0.467 against 0.095 at 0.02) while clean accuracy falls, slowly at first and then sharply. The $L_1$ term also makes the weights sparse, from 256 nonzero weights to 8 at $\varepsilon = 0.02$. At $\varepsilon = 0.04$ every weight is zero and the model predicts one class for every image, 0.469 accuracy, which is trivially robust: the degenerate end of the trade-off, like the all-one classifier in Zhang et al.’s example. In our reading, a linear model has no way to become locally flat around the data except by shrinking weights everywhere, which is the Deep Learning book’s point that networks, unlike linear models, can resist perturbations without giving up so much.

Common Misconceptions

• “Adversarial examples are rare points in pockets of input space.” For a linear model they exist next to almost every input, as the example shows, and universal perturbations show that one direction can serve for most images of a deep network. Athalye, Carlini and Wagner contrast the “blind spots” view of Szegedy et al. with Goodfellow et al.’s linear view.
• “A defence that defeats FGSM and PGD is robust.” Gradient-based attacks fail when gradients are masked; seven of nine non-certified ICLR 2018 defences relied on obfuscated gradients (Athalye, Carlini & Wagner, 2018). A defence needs an adaptive attack and a protocol such as AutoAttack, or a certificate.
• “Robustness to random noise implies robustness to adversarial noise.” Random noise of fifteen times the adversarial budget left most predictions unchanged in the example; the two can differ by a factor that grows with the square root of the dimension.
• “Black-box access protects a model.” Transfer from substitute models and query-based gradient estimation attack models without their weights (Ilyas et al., 2018); Athalye, Carlini and Wagner argue that a credible threat model grants at least knowledge of the architecture, the training algorithm and query access.
• “Adversarial examples need imperceptible pixel changes.” The $L_p$ ball is a convenient threat model, not the definition: stickers on a sign, 3D-printed textures and patches are visible but inconspicuous.

Where It Is Used

Adversarial robustness is evaluated for classifiers whose errors an adversary could exploit, such as traffic sign recognition and deepfake detection, and reported alongside other robustness tests; the mixup and CutMix article reports CutMix’s accuracy under an FGSM attack. Perturbations are used constructively too: personalized image generation describes Anti-DreamBooth, which adds adversarial perturbations to photos to degrade models fine-tuned on them. Adversarial training doubles as a regularizer and, as virtual adversarial training, as a semi-supervised method. Input gradients connect the subject to interpretability, where gradient maps and feature visualizations raise the same question of what small input changes do to a network.