258 Adversarial Robustness: Attacks and Defenses

The discovery that deep neural networks can be reliably fooled by imperceptible input perturbations ranks among the most unsettling findings in modern machine learning. Szegedy et al. (2014) showed that adding structured noise — invisible to human observers — causes state-of-the-art image classifiers to misclassify inputs with near-total confidence. The phenomenon is not a curiosity: it exposes a fundamental gap between the geometry of learned decision boundaries and the geometry humans use to perceive similarity. Understanding, attacking, and defending against adversarial examples has grown into one of the most active research areas in AI safety.

258.1 1. Adversarial Examples and the Threat Model

Let $f: \mathcal{X} \to \mathcal{Y}$ be a classifier mapping inputs $x \in \mathbb{R}^d$ to class labels. An adversarial example is a point $x_{\text{adv}}$ satisfying two conditions simultaneously: (i) $x_{\text{adv}}$ is close to a natural input $x$ under some distance metric, and (ii) $f(x_{\text{adv}}) \neq f(x)$.

The threat model formalizes attacker capability via an $\ell_p$ ball of radius $\varepsilon$. The attacker solves

\[\max_{\delta} \; L(\theta, x + \delta, y) \quad \text{subject to} \quad \|\delta\|_p \leq \varepsilon\]

where $L$ is the training loss, $\theta$ are model parameters, and $y$ is the true label. The three most common norms are $\ell_\infty$ (every coordinate perturbed by at most $\varepsilon$), $\ell_2$ (Euclidean distance bounded), and $\ell_1$ (total absolute perturbation bounded). The $\ell_\infty$ threat model is most studied because it admits efficient first-order attacks and because the constant per-pixel budget maps naturally to image pixel values.

Szegedy et al. (2014) demonstrated that adversarial examples transfer across models: an example crafted to fool one network also fools independently trained networks with high probability. This transferability implies that adversarial vulnerability is not a quirk of a specific architecture but reflects the geometry of the underlying learning problem.

258.2 2. FGSM: The Fast Gradient Sign Method

Goodfellow et al. (2015) introduced the Fast Gradient Sign Method (FGSM) as both an attack and an explanation for why adversarial examples exist. The core insight is a linearization argument. Expand the loss around $x$:

\[L(\theta, x + \delta, y) \approx L(\theta, x, y) + \delta^\top \nabla_x L(\theta, x, y)\]

To maximize this linear approximation subject to $\|\delta\|_\infty \leq \varepsilon$, the optimal perturbation assigns each coordinate of $\delta$ to $+\varepsilon$ if the corresponding gradient is positive and $-\varepsilon$ if negative. This gives the sign gradient:

\[x_{\text{adv}} = x + \varepsilon \cdot \operatorname{sign}\!\bigl(\nabla_x L(\theta, x, y)\bigr)\]

Each pixel shifts by exactly $\varepsilon$ in the direction that increases loss. The total $\ell_\infty$ norm of the perturbation is $\varepsilon$, and every coordinate of the perturbation is at the boundary of the constraint set. The key observation from Goodfellow et al. (2015) is that even though each individual perturbation is tiny, the inner product $\delta^\top g$ (where $g = \nabla_x L$) accumulates across $d$ dimensions: in expectation it scales as $\varepsilon \mathbb{E}[|g_i|] \cdot d$, explaining why high-dimensional models are particularly susceptible.

The following implementation runs on CPU using a small convolutional network trained on MNIST. The code trains a minimal model, then evaluates accuracy under FGSM at several values of $\varepsilon$.

import torch
import torch.nn as nn
import torch.optim as optim
from torchvision import datasets, transforms
from torch.utils.data import DataLoader

torch.manual_seed(0)

transform = transforms.Compose([transforms.ToTensor()])
train_data = datasets.MNIST("data", train=True, download=True, transform=transform)
test_data = datasets.MNIST("data", train=False, download=True, transform=transform)
train_loader = DataLoader(train_data, batch_size=256, shuffle=True)
test_loader = DataLoader(test_data, batch_size=512, shuffle=False)

class SmallCNN(nn.Module):
    def __init__(self):
        super().__init__()
        self.net = nn.Sequential(
            nn.Conv2d(1, 16, 3, padding=1), nn.ReLU(),
            nn.MaxPool2d(2),
            nn.Conv2d(16, 32, 3, padding=1), nn.ReLU(),
            nn.MaxPool2d(2),
            nn.Flatten(),
            nn.Linear(32 * 7 * 7, 128), nn.ReLU(),
            nn.Linear(128, 10),
        )
    def forward(self, x):
        return self.net(x)

model = SmallCNN()
optimizer = optim.Adam(model.parameters(), lr=1e-3)
criterion = nn.CrossEntropyLoss()

for epoch in range(3):
    model.train()
    for x, y in train_loader:
        optimizer.zero_grad()
        criterion(model(x), y).backward()
        optimizer.step()

def fgsm_attack(model, x, y, eps):
    x_adv = x.clone().detach().requires_grad_(True)
    loss = criterion(model(x_adv), y)
    loss.backward()
    return (x_adv + eps * x_adv.grad.sign()).clamp(0, 1).detach()

def evaluate(model, loader, eps=0.0):
    model.eval()
    correct = total = 0
    for x, y in loader:
        if eps > 0:
            x = fgsm_attack(model, x, y, eps)
        with torch.no_grad():
            pred = model(x).argmax(1)
        correct += (pred == y).sum().item()
        total += len(y)
    return correct / total

print(f"Clean accuracy:       {evaluate(model, test_loader):.3f}")
for eps in [0.05, 0.10, 0.20, 0.30]:
    print(f"FGSM eps={eps:.2f} accuracy: {evaluate(model, test_loader, eps):.3f}")

On a standard laptop this script trains in under a minute and typically shows clean accuracy above 0.98 dropping to below 0.20 at $\varepsilon = 0.30$, illustrating the dramatic effect of FGSM even at modest perturbation budgets.

258.3 3. PGD: Projected Gradient Descent

FGSM takes a single gradient step. Madry et al. (2018) showed that stronger attacks result from iterating gradient steps while projecting back into the constraint set after each step. The Projected Gradient Descent (PGD) attack initializes $x^0$ uniformly at random within $B_\varepsilon(x)$ and iterates:

\[x^{t+1} = \Pi_{B_\varepsilon(x)}\!\Bigl(x^t + \alpha \cdot \operatorname{sign}\!\bigl(\nabla_{x^t} L(\theta, x^t, y)\bigr)\Bigr)\]

Here $\alpha$ is the step size, $T$ is the number of steps, and $\Pi_{B_\varepsilon(x)}$ denotes projection onto the $\ell_\infty$ ball of radius $\varepsilon$ centered at $x$. For $\ell_\infty$, projection is coordinate-wise clipping: $\Pi_{B_\varepsilon(x)}(z)_i = x_i + \operatorname{clip}(z_i - x_i, -\varepsilon, \varepsilon)$. Additionally the projected point must stay within the valid input domain $[0,1]^d$.

Madry et al. (2018) argue that PGD with random restarts constitutes a universal first-order attack: under reasonable assumptions about the loss landscape, it finds the worst-case perturbation accessible via first-order optimization. Empirically, defenses that withstand PGD-$T$ for large $T$ are far more reliable than those that merely withstand FGSM.

The saddle-point framing clarifies the connection to training. Robust classification solves

\[\min_\theta \; \mathbb{E}_{(x,y) \sim \mathcal{D}}\!\left[\max_{\|\delta\|_p \leq \varepsilon} L(\theta, x + \delta, y)\right]\]

The inner maximization is the attack; the outer minimization is standard ERM on the worst-case loss. PGD approximates the inner maximization during training, which motivates PGD adversarial training.

258.4 4. Adversarial Training

The simplest defense is to include adversarial examples in the training set. FGSM adversarial training (Goodfellow et al., 2015) augments each minibatch:

\[\theta \leftarrow \theta - \eta \nabla_\theta \frac{1}{n}\sum_{i=1}^n L\!\bigl(\theta,\, x_i + \varepsilon \cdot \operatorname{sign}(\nabla_{x_i} L(\theta, x_i, y_i)),\, y_i\bigr)\]

This is inexpensive: one extra forward-backward pass per batch. It improves robustness against FGSM attacks but provides only marginal protection against PGD.

PGD adversarial training (Madry et al., 2018) runs the full $T$-step attack inside each training iteration. This is the gold standard empirical defense, but is computationally expensive: with $T = 7$ and $\alpha = 2\varepsilon / T$, each training step requires $T + 1$ gradient computations instead of one, giving a factor of roughly $T$-to-$20\times$ slowdown depending on implementation.

A consistent empirical finding is that adversarial training improves worst-case (adversarial) accuracy at the cost of roughly 1–5% clean accuracy on CIFAR-10. This robustness–accuracy tradeoff has been studied theoretically by Tsipras et al. (2019), who show that when the Bayes-optimal boundary for natural and adversarial distributions differ, any classifier must sacrifice some natural accuracy to be adversarially robust.

The following code implements a simplified adversarial training loop using FGSM on the same MNIST model, then evaluates the resulting robustness improvement.

model_adv = SmallCNN()
optimizer_adv = optim.Adam(model_adv.parameters(), lr=1e-3)
eps_train = 0.20

for epoch in range(5):
    model_adv.train()
    for x, y in train_loader:
        x_adv = fgsm_attack(model_adv, x, y, eps_train)
        optimizer_adv.zero_grad()
        loss = 0.5 * criterion(model_adv(x), y) + 0.5 * criterion(model_adv(x_adv), y)
        loss.backward()
        optimizer_adv.step()

print("=== Standard model ===")
print(f"  Clean:         {evaluate(model, test_loader):.3f}")
print(f"  FGSM eps=0.20: {evaluate(model, test_loader, 0.20):.3f}")

print("=== Adversarially trained model ===")
print(f"  Clean:         {evaluate(model_adv, test_loader):.3f}")
print(f"  FGSM eps=0.20: {evaluate(model_adv, test_loader, 0.20):.3f}")

The mixed loss weights each natural and adversarial example equally. Running this shows the adversarially trained model retains near-original clean accuracy while substantially increasing FGSM accuracy, demonstrating the core benefit of data augmentation with adversarial inputs.

258.5 5. Certified Defenses: Provable Robustness

Empirical robustness — running attacks and checking whether they succeed — cannot prove a model is robust. A stronger attacker, or a different attack algorithm, may succeed where PGD fails. Certified defenses provide mathematical guarantees: for a given input $x$ and radius $\varepsilon$, they prove that no perturbation $\|\delta\|_\infty \leq \varepsilon$ can change the predicted label.

258.5.1 5.1 The Convex Outer Adversarial Polytope

Wong and Kolter (2018) introduced a certification method based on LP relaxation of the ReLU polytope. Consider a network with ReLU activations. The set of all activations reachable from inputs in $B_\varepsilon(x)$ is generally non-convex (due to ReLU). Wong and Kolter construct a convex outer relaxation: a polytope that contains the true activation set but is efficiently computable.

For each ReLU unit $z = \max(0, \hat{z})$ where $\hat{z}$ is the pre-activation, the relaxation replaces the non-convex constraint with the tightest convex envelope on the interval $[\ell, u]$ (pre-activation lower and upper bounds). When $\ell < 0 < u$ (the “unstable” case), the ReLU is replaced by the triangle relaxation:

\[z \geq 0, \quad z \geq \hat{z}, \quad z \leq \frac{u(\hat{z} - \ell)}{u - \ell}\]

When $u \leq 0$, $z = 0$; when $\ell \geq 0$, $z = \hat{z}$. Propagating these bounds through the network via interval arithmetic (with tightening at each layer) yields lower bounds $\ell^{(k)}$ and upper bounds $u^{(k)}$ on each activation in layer $k$.

The dual of the LP relaxation yields a certificate: if the certified lower bound on the margin $f_y(x) - \max_{j \neq y} f_j(x)$ is positive under all perturbations in the relaxed polytope, then the true network is provably correct at $x$ for all $\|\delta\|_\infty \leq \varepsilon$. Minimizing the upper bound on the worst-case loss (the convex outer bound) during training gives provably robust networks that trade clean accuracy for certified robustness guarantees.

Concretely, the Wong-Kolter training objective adds an adversarial regularizer derived from the dual LP:

\[\mathcal{L}_{\text{cert}}(\theta, x, y) = \kappa \cdot L(\theta, x, y) + (1-\kappa) \cdot L_{\text{ub}}(\theta, x, y, \varepsilon)\]

where $L_{\text{ub}}$ is the upper bound on worst-case loss computable from the dual certificate, and $\kappa$ interpolates between natural and certified training.

258.5.2 5.2 Randomized Smoothing

Cohen et al. (2019) introduced randomized smoothing, which certifies robustness for arbitrary base classifiers using statistical testing. Given a base classifier $f$, the smoothed classifier is

\[g(x) = \arg\max_c \; \Pr_{\varepsilon \sim \mathcal{N}(0, \sigma^2 I)}\!\bigl[f(x + \varepsilon) = c\bigr]\]

Cohen et al. (2019) prove that if class $A$ is returned by $g$ with probability $\bar{p}_A > 1/2$, then $g$ certifiably predicts $A$ for all perturbations within $\ell_2$ radius

\[r = \sigma \cdot \Phi^{-1}(\bar{p}_A)\]

where $\Phi^{-1}$ is the inverse standard normal CDF. The probability $\bar{p}_A$ is estimated via Monte Carlo: sample $n$ Gaussian noisy versions of $x$, count the plurality vote, and apply a one-sided confidence interval (Clopper-Pearson) to lower-bound $\bar{p}_A$.

Randomized smoothing scales to ImageNet-sized models and large $\ell_2$ radii because certification requires only forward passes through $f$. The tradeoff is that larger $\sigma$ increases the certified radius but degrades clean accuracy by blurring the input. The certified accuracy at radius $r$ — the fraction of test inputs that are both correctly classified and certified at radius $r$ — has improved substantially with better base classifiers and training procedures (Salman et al., 2020).

258.6 6. The Adaptive Attack Problem and the State of Empirical Defenses

A recurring failure mode in the adversarial robustness literature is defenses that are broken by adaptive attacks — attacks specifically designed with knowledge of the defense. Obfuscated gradients (Athalye et al., 2018) are the canonical example: defenses that make gradients uninformative (via non-differentiable preprocessing, stochastic components, or gradient masking) appear robust against naive attacks but are circumvented by differentiable approximations, expectation over transformations (EOT), or backward-pass differentiable approximations (BPDA).

The lesson is that security cannot be measured by evaluating a fixed attack on a fixed defense. Carlini et al. (2019) provide evaluation guidelines emphasizing that a defense must withstand attack algorithms that are adaptive to the specific defense mechanism, with multiple random restarts and sufficient attack iterations. Robustness benchmarks such as RobustBench (Croce et al., 2021) address this by maintaining a standardized leaderboard at robust-ml.org where models are evaluated with AutoAttack, an ensemble of parameter-free attacks.

The current state of the field as of 2025 is: (i) PGD adversarial training remains the dominant empirical defense with certified variants (TRADES, AWP) providing incremental improvements; (ii) certified defenses via LP relaxation or randomized smoothing provide the only mathematically rigorous guarantees, but certified accuracy is still substantially below natural accuracy at perturbation radii where practical attacks succeed; (iii) diffusion-based purification has emerged as a strong empirical defense by projecting adversarial inputs back toward the natural data manifold before classification.

258.7 7. Adversarial Perturbations as Covariate Shift

A statistical perspective interprets adversarial examples as inputs from a shifted distribution. Let $p(x, y)$ be the natural data distribution with marginal $p(x)$. Adversarial examples lie in regions where the model assigns high confidence but the input $x_{\text{adv}}$ has low probability under $p(x)$: the attacker moves the input away from the support of training data while staying within $B_\varepsilon(x)$.

Under the covariate shift model $q(x, y) = q(x) \cdot p(y|x)$, the marginal $q(x)$ differs from $p(x)$ in ways that concentrate probability mass near decision boundaries. Detectors based on input likelihood (Liang et al., 2018) or density estimation can flag anomalous inputs before they reach the classifier. However, Carlini and Wagner (2017) showed that most input-space detectors can be circumvented by including the detector in the attack objective, again emphasizing the importance of adaptive evaluation.

The saddle-point training objective from Section 3 has a distributional interpretation: it optimizes expected loss under the worst-case distribution over $B_\varepsilon(x)$, making the model robust to any covariate shift within that ball. This connects adversarial robustness to distributionally robust optimization (DRO), where the inner maximization is replaced by a broader divergence constraint. The $\phi$-divergence DRO literature (Ben-Tal et al., 2013) generalizes PGD training to non-$\ell_p$ uncertainty sets.

258.8 References

Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2014). Intriguing properties of neural networks. International Conference on Learning Representations (ICLR). https://arxiv.org/abs/1312.6199
Goodfellow, I. J., Shlens, J., and Szegedy, C. (2015). Explaining and harnessing adversarial examples. International Conference on Learning Representations (ICLR). https://arxiv.org/abs/1412.6572
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2018). Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations (ICLR). https://arxiv.org/abs/1706.06083
Wong, E. and Kolter, J. Z. (2018). Provable defenses against adversarial examples via the convex outer adversarial polytope. International Conference on Machine Learning (ICML). https://arxiv.org/abs/1711.00851
Cohen, J., Rosenfeld, E., and Kolter, J. Z. (2019). Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning (ICML). https://arxiv.org/abs/1902.02918
Athalye, A., Carlini, N., and Wagner, D. (2018). Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. International Conference on Machine Learning (ICML). https://arxiv.org/abs/1802.00420
Carlini, N., Athalye, A., Papernot, N., Brendel, W., Rauber, J., Fawzi, A., Goodfellow, I., Madry, A., and Lyu, C. (2019). On evaluating adversarial robustness. https://arxiv.org/abs/1902.06705
Croce, F., Andriushchenko, M., Sehwag, V., Debenedetti, E., Flammarion, N., Chiang, P.-Y., Mitliagkas, I., and Hein, M. (2021). RobustBench: a standardized adversarial robustness benchmark. NeurIPS Datasets and Benchmarks. https://arxiv.org/abs/2010.09670
Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. (2019). Robustness may be at odds with accuracy. International Conference on Learning Representations (ICLR). https://arxiv.org/abs/1805.12152
Salman, H., Li, J., Razenshteyn, I., Zhang, P., Zhang, H., Bubeck, S., and Yang, G. (2020). Provably robust deep learning via adversarially trained smoothed classifiers. Advances in Neural Information Processing Systems (NeurIPS). https://arxiv.org/abs/1906.04584

# Adversarial Robustness: Attacks and Defenses {#sec-adversarial-robustness} The discovery that deep neural networks can be reliably fooled by imperceptible input perturbations ranks among the most unsettling findings in modern machine learning. Szegedy et al. (2014) showed that adding structured noise --- invisible to human observers --- causes state-of-the-art image classifiers to misclassify inputs with near-total confidence. The phenomenon is not a curiosity: it exposes a fundamental gap between the geometry of learned decision boundaries and the geometry humans use to perceive similarity. Understanding, attacking, and defending against adversarial examples has grown into one of the most active research areas in AI safety. ## 1. Adversarial Examples and the Threat Model Let $f: \mathcal{X} \to \mathcal{Y}$ be a classifier mapping inputs $x \in \mathbb{R}^d$ to class labels. An **adversarial example** is a point $x_{\text{adv}}$ satisfying two conditions simultaneously: (i) $x_{\text{adv}}$ is close to a natural input $x$ under some distance metric, and (ii) $f(x_{\text{adv}}) \neq f(x)$. The threat model formalizes attacker capability via an $\ell_p$ ball of radius $\varepsilon$. The attacker solves $$\max_{\delta} \; L(\theta, x + \delta, y) \quad \text{subject to} \quad \|\delta\|_p \leq \varepsilon$$ where $L$ is the training loss, $\theta$ are model parameters, and $y$ is the true label. The three most common norms are $\ell_\infty$ (every coordinate perturbed by at most $\varepsilon$), $\ell_2$ (Euclidean distance bounded), and $\ell_1$ (total absolute perturbation bounded). The $\ell_\infty$ threat model is most studied because it admits efficient first-order attacks and because the constant per-pixel budget maps naturally to image pixel values. Szegedy et al. (2014) demonstrated that adversarial examples transfer across models: an example crafted to fool one network also fools independently trained networks with high probability. This transferability implies that adversarial vulnerability is not a quirk of a specific architecture but reflects the geometry of the underlying learning problem. ## 2. FGSM: The Fast Gradient Sign Method Goodfellow et al. (2015) introduced the **Fast Gradient Sign Method (FGSM)** as both an attack and an explanation for why adversarial examples exist. The core insight is a linearization argument. Expand the loss around $x$: $$L(\theta, x + \delta, y) \approx L(\theta, x, y) + \delta^\top \nabla_x L(\theta, x, y)$$ To maximize this linear approximation subject to $\|\delta\|_\infty \leq \varepsilon$, the optimal perturbation assigns each coordinate of $\delta$ to $+\varepsilon$ if the corresponding gradient is positive and $-\varepsilon$ if negative. This gives the **sign gradient**: $$x_{\text{adv}} = x + \varepsilon \cdot \operatorname{sign}\!\bigl(\nabla_x L(\theta, x, y)\bigr)$$ Each pixel shifts by exactly $\varepsilon$ in the direction that increases loss. The total $\ell_\infty$ norm of the perturbation is $\varepsilon$, and every coordinate of the perturbation is at the boundary of the constraint set. The key observation from Goodfellow et al. (2015) is that even though each individual perturbation is tiny, the inner product $\delta^\top g$ (where $g = \nabla_x L$) accumulates across $d$ dimensions: in expectation it scales as $\varepsilon \mathbb{E}[|g_i|] \cdot d$, explaining why high-dimensional models are particularly susceptible. The following implementation runs on CPU using a small convolutional network trained on MNIST. The code trains a minimal model, then evaluates accuracy under FGSM at several values of $\varepsilon$. ```python import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader torch.manual_seed(0) transform = transforms.Compose([transforms.ToTensor()]) train_data = datasets.MNIST("data", train=True, download=True, transform=transform) test_data = datasets.MNIST("data", train=False, download=True, transform=transform) train_loader = DataLoader(train_data, batch_size=256, shuffle=True) test_loader = DataLoader(test_data, batch_size=512, shuffle=False) class SmallCNN(nn.Module): def __init__(self): super().__init__() self.net = nn.Sequential( nn.Conv2d(1, 16, 3, padding=1), nn.ReLU(), nn.MaxPool2d(2), nn.Conv2d(16, 32, 3, padding=1), nn.ReLU(), nn.MaxPool2d(2), nn.Flatten(), nn.Linear(32 * 7 * 7, 128), nn.ReLU(), nn.Linear(128, 10), ) def forward(self, x): return self.net(x) model = SmallCNN() optimizer = optim.Adam(model.parameters(), lr=1e-3) criterion = nn.CrossEntropyLoss() for epoch in range(3): model.train() for x, y in train_loader: optimizer.zero_grad() criterion(model(x), y).backward() optimizer.step() def fgsm_attack(model, x, y, eps): x_adv = x.clone().detach().requires_grad_(True) loss = criterion(model(x_adv), y) loss.backward() return (x_adv + eps * x_adv.grad.sign()).clamp(0, 1).detach() def evaluate(model, loader, eps=0.0): model.eval() correct = total = 0 for x, y in loader: if eps > 0: x = fgsm_attack(model, x, y, eps) with torch.no_grad(): pred = model(x).argmax(1) correct += (pred == y).sum().item() total += len(y) return correct / total print(f"Clean accuracy: {evaluate(model, test_loader):.3f}") for eps in [0.05, 0.10, 0.20, 0.30]: print(f"FGSM eps={eps:.2f} accuracy: {evaluate(model, test_loader, eps):.3f}") ``` On a standard laptop this script trains in under a minute and typically shows clean accuracy above 0.98 dropping to below 0.20 at $\varepsilon = 0.30$, illustrating the dramatic effect of FGSM even at modest perturbation budgets. ## 3. PGD: Projected Gradient Descent FGSM takes a single gradient step. Madry et al. (2018) showed that stronger attacks result from iterating gradient steps while projecting back into the constraint set after each step. The **Projected Gradient Descent (PGD)** attack initializes $x^0$ uniformly at random within $B_\varepsilon(x)$ and iterates: $$x^{t+1} = \Pi_{B_\varepsilon(x)}\!\Bigl(x^t + \alpha \cdot \operatorname{sign}\!\bigl(\nabla_{x^t} L(\theta, x^t, y)\bigr)\Bigr)$$ Here $\alpha$ is the step size, $T$ is the number of steps, and $\Pi_{B_\varepsilon(x)}$ denotes projection onto the $\ell_\infty$ ball of radius $\varepsilon$ centered at $x$. For $\ell_\infty$, projection is coordinate-wise clipping: $\Pi_{B_\varepsilon(x)}(z)_i = x_i + \operatorname{clip}(z_i - x_i, -\varepsilon, \varepsilon)$. Additionally the projected point must stay within the valid input domain $[0,1]^d$. Madry et al. (2018) argue that PGD with random restarts constitutes a **universal first-order attack**: under reasonable assumptions about the loss landscape, it finds the worst-case perturbation accessible via first-order optimization. Empirically, defenses that withstand PGD-$T$ for large $T$ are far more reliable than those that merely withstand FGSM. The saddle-point framing clarifies the connection to training. Robust classification solves $$\min_\theta \; \mathbb{E}_{(x,y) \sim \mathcal{D}}\!\left[\max_{\|\delta\|_p \leq \varepsilon} L(\theta, x + \delta, y)\right]$$ The inner maximization is the attack; the outer minimization is standard ERM on the worst-case loss. PGD approximates the inner maximization during training, which motivates PGD adversarial training. ## 4. Adversarial Training The simplest defense is to include adversarial examples in the training set. **FGSM adversarial training** (Goodfellow et al., 2015) augments each minibatch: $$\theta \leftarrow \theta - \eta \nabla_\theta \frac{1}{n}\sum_{i=1}^n L\!\bigl(\theta,\, x_i + \varepsilon \cdot \operatorname{sign}(\nabla_{x_i} L(\theta, x_i, y_i)),\, y_i\bigr)$$ This is inexpensive: one extra forward-backward pass per batch. It improves robustness against FGSM attacks but provides only marginal protection against PGD. **PGD adversarial training** (Madry et al., 2018) runs the full $T$-step attack inside each training iteration. This is the gold standard empirical defense, but is computationally expensive: with $T = 7$ and $\alpha = 2\varepsilon / T$, each training step requires $T + 1$ gradient computations instead of one, giving a factor of roughly $T$-to-$20\times$ slowdown depending on implementation. A consistent empirical finding is that adversarial training improves worst-case (adversarial) accuracy at the cost of roughly 1--5% clean accuracy on CIFAR-10. This **robustness--accuracy tradeoff** has been studied theoretically by Tsipras et al. (2019), who show that when the Bayes-optimal boundary for natural and adversarial distributions differ, any classifier must sacrifice some natural accuracy to be adversarially robust. The following code implements a simplified adversarial training loop using FGSM on the same MNIST model, then evaluates the resulting robustness improvement. ```python model_adv = SmallCNN() optimizer_adv = optim.Adam(model_adv.parameters(), lr=1e-3) eps_train = 0.20 for epoch in range(5): model_adv.train() for x, y in train_loader: x_adv = fgsm_attack(model_adv, x, y, eps_train) optimizer_adv.zero_grad() loss = 0.5 * criterion(model_adv(x), y) + 0.5 * criterion(model_adv(x_adv), y) loss.backward() optimizer_adv.step() print("=== Standard model ===") print(f" Clean: {evaluate(model, test_loader):.3f}") print(f" FGSM eps=0.20: {evaluate(model, test_loader, 0.20):.3f}") print("=== Adversarially trained model ===") print(f" Clean: {evaluate(model_adv, test_loader):.3f}") print(f" FGSM eps=0.20: {evaluate(model_adv, test_loader, 0.20):.3f}") ``` The mixed loss weights each natural and adversarial example equally. Running this shows the adversarially trained model retains near-original clean accuracy while substantially increasing FGSM accuracy, demonstrating the core benefit of data augmentation with adversarial inputs. ## 5. Certified Defenses: Provable Robustness Empirical robustness --- running attacks and checking whether they succeed --- cannot prove a model is robust. A stronger attacker, or a different attack algorithm, may succeed where PGD fails. **Certified defenses** provide mathematical guarantees: for a given input $x$ and radius $\varepsilon$, they prove that no perturbation $\|\delta\|_\infty \leq \varepsilon$ can change the predicted label. ### 5.1 The Convex Outer Adversarial Polytope Wong and Kolter (2018) introduced a certification method based on **LP relaxation of the ReLU polytope**. Consider a network with ReLU activations. The set of all activations reachable from inputs in $B_\varepsilon(x)$ is generally non-convex (due to ReLU). Wong and Kolter construct a **convex outer relaxation**: a polytope that contains the true activation set but is efficiently computable. For each ReLU unit $z = \max(0, \hat{z})$ where $\hat{z}$ is the pre-activation, the relaxation replaces the non-convex constraint with the tightest convex envelope on the interval $[\ell, u]$ (pre-activation lower and upper bounds). When $\ell < 0 < u$ (the "unstable" case), the ReLU is replaced by the triangle relaxation: $$z \geq 0, \quad z \geq \hat{z}, \quad z \leq \frac{u(\hat{z} - \ell)}{u - \ell}$$ When $u \leq 0$, $z = 0$; when $\ell \geq 0$, $z = \hat{z}$. Propagating these bounds through the network via interval arithmetic (with tightening at each layer) yields lower bounds $\ell^{(k)}$ and upper bounds $u^{(k)}$ on each activation in layer $k$. The dual of the LP relaxation yields a **certificate**: if the certified lower bound on the margin $f_y(x) - \max_{j \neq y} f_j(x)$ is positive under all perturbations in the relaxed polytope, then the true network is provably correct at $x$ for all $\|\delta\|_\infty \leq \varepsilon$. Minimizing the upper bound on the worst-case loss (the convex outer bound) during training gives **provably robust networks** that trade clean accuracy for certified robustness guarantees. Concretely, the Wong-Kolter training objective adds an adversarial regularizer derived from the dual LP: $$\mathcal{L}_{\text{cert}}(\theta, x, y) = \kappa \cdot L(\theta, x, y) + (1-\kappa) \cdot L_{\text{ub}}(\theta, x, y, \varepsilon)$$ where $L_{\text{ub}}$ is the upper bound on worst-case loss computable from the dual certificate, and $\kappa$ interpolates between natural and certified training. ### 5.2 Randomized Smoothing Cohen et al. (2019) introduced **randomized smoothing**, which certifies robustness for arbitrary base classifiers using statistical testing. Given a base classifier $f$, the smoothed classifier is $$g(x) = \arg\max_c \; \Pr_{\varepsilon \sim \mathcal{N}(0, \sigma^2 I)}\!\bigl[f(x + \varepsilon) = c\bigr]$$ Cohen et al. (2019) prove that if class $A$ is returned by $g$ with probability $\bar{p}_A > 1/2$, then $g$ certifiably predicts $A$ for all perturbations within $\ell_2$ radius $$r = \sigma \cdot \Phi^{-1}(\bar{p}_A)$$ where $\Phi^{-1}$ is the inverse standard normal CDF. The probability $\bar{p}_A$ is estimated via Monte Carlo: sample $n$ Gaussian noisy versions of $x$, count the plurality vote, and apply a one-sided confidence interval (Clopper-Pearson) to lower-bound $\bar{p}_A$. Randomized smoothing scales to ImageNet-sized models and large $\ell_2$ radii because certification requires only forward passes through $f$. The tradeoff is that larger $\sigma$ increases the certified radius but degrades clean accuracy by blurring the input. The certified accuracy at radius $r$ --- the fraction of test inputs that are both correctly classified and certified at radius $r$ --- has improved substantially with better base classifiers and training procedures (Salman et al., 2020). ## 6. The Adaptive Attack Problem and the State of Empirical Defenses A recurring failure mode in the adversarial robustness literature is defenses that are broken by **adaptive attacks** --- attacks specifically designed with knowledge of the defense. Obfuscated gradients (Athalye et al., 2018) are the canonical example: defenses that make gradients uninformative (via non-differentiable preprocessing, stochastic components, or gradient masking) appear robust against naive attacks but are circumvented by differentiable approximations, expectation over transformations (EOT), or backward-pass differentiable approximations (BPDA). The lesson is that security cannot be measured by evaluating a fixed attack on a fixed defense. Carlini et al. (2019) provide evaluation guidelines emphasizing that a defense must withstand attack algorithms that are adaptive to the specific defense mechanism, with multiple random restarts and sufficient attack iterations. Robustness benchmarks such as RobustBench (Croce et al., 2021) address this by maintaining a standardized leaderboard at robust-ml.org where models are evaluated with AutoAttack, an ensemble of parameter-free attacks. The current state of the field as of 2025 is: (i) PGD adversarial training remains the dominant empirical defense with certified variants (TRADES, AWP) providing incremental improvements; (ii) certified defenses via LP relaxation or randomized smoothing provide the only mathematically rigorous guarantees, but certified accuracy is still substantially below natural accuracy at perturbation radii where practical attacks succeed; (iii) diffusion-based purification has emerged as a strong empirical defense by projecting adversarial inputs back toward the natural data manifold before classification. ## 7. Adversarial Perturbations as Covariate Shift A statistical perspective interprets adversarial examples as inputs from a shifted distribution. Let $p(x, y)$ be the natural data distribution with marginal $p(x)$. Adversarial examples lie in regions where the model assigns high confidence but the input $x_{\text{adv}}$ has low probability under $p(x)$: the attacker moves the input away from the support of training data while staying within $B_\varepsilon(x)$. Under the covariate shift model $q(x, y) = q(x) \cdot p(y|x)$, the marginal $q(x)$ differs from $p(x)$ in ways that concentrate probability mass near decision boundaries. Detectors based on input likelihood (Liang et al., 2018) or density estimation can flag anomalous inputs before they reach the classifier. However, Carlini and Wagner (2017) showed that most input-space detectors can be circumvented by including the detector in the attack objective, again emphasizing the importance of adaptive evaluation. The saddle-point training objective from Section 3 has a distributional interpretation: it optimizes expected loss under the worst-case distribution over $B_\varepsilon(x)$, making the model robust to any covariate shift within that ball. This connects adversarial robustness to distributionally robust optimization (DRO), where the inner maximization is replaced by a broader divergence constraint. The $\phi$-divergence DRO literature (Ben-Tal et al., 2013) generalizes PGD training to non-$\ell_p$ uncertainty sets. ## References 1. Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2014). Intriguing properties of neural networks. *International Conference on Learning Representations (ICLR)*. https://arxiv.org/abs/1312.6199 2. Goodfellow, I. J., Shlens, J., and Szegedy, C. (2015). Explaining and harnessing adversarial examples. *International Conference on Learning Representations (ICLR)*. https://arxiv.org/abs/1412.6572 3. Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2018). Towards deep learning models resistant to adversarial attacks. *International Conference on Learning Representations (ICLR)*. https://arxiv.org/abs/1706.06083 4. Wong, E. and Kolter, J. Z. (2018). Provable defenses against adversarial examples via the convex outer adversarial polytope. *International Conference on Machine Learning (ICML)*. https://arxiv.org/abs/1711.00851 5. Cohen, J., Rosenfeld, E., and Kolter, J. Z. (2019). Certified adversarial robustness via randomized smoothing. *International Conference on Machine Learning (ICML)*. https://arxiv.org/abs/1902.02918 6. Athalye, A., Carlini, N., and Wagner, D. (2018). Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. *International Conference on Machine Learning (ICML)*. https://arxiv.org/abs/1802.00420 7. Carlini, N., Athalye, A., Papernot, N., Brendel, W., Rauber, J., Fawzi, A., Goodfellow, I., Madry, A., and Lyu, C. (2019). On evaluating adversarial robustness. https://arxiv.org/abs/1902.06705 8. Croce, F., Andriushchenko, M., Sehwag, V., Debenedetti, E., Flammarion, N., Chiang, P.-Y., Mitliagkas, I., and Hein, M. (2021). RobustBench: a standardized adversarial robustness benchmark. *NeurIPS Datasets and Benchmarks*. https://arxiv.org/abs/2010.09670 9. Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. (2019). Robustness may be at odds with accuracy. *International Conference on Learning Representations (ICLR)*. https://arxiv.org/abs/1805.12152 10. Salman, H., Li, J., Razenshteyn, I., Zhang, P., Zhang, H., Bubeck, S., and Yang, G. (2020). Provably robust deep learning via adversarially trained smoothed classifiers. *Advances in Neural Information Processing Systems (NeurIPS)*. https://arxiv.org/abs/1906.04584