Adversarial Robustness

Adversarial robustness is the study of making ML models resistant to imperceptible input perturbations that flip predictions, and of mounting such attacks.

ML models are surprisingly brittle: tiny perturbations can flip the prediction while leaving the human-perceived label unchanged.

Intuition

In high-dimensional input space, decision boundaries sit close to almost every data point. A nudge of a few pixels in a carefully chosen direction (the gradient) is enough to cross the boundary even though the image still looks the same to a human. Robustness is about forcing the boundary to back away from the data.

Why study adversaries if inputs look identical?

To be a good defender you have to be a good attacker. The same optimization procedure produces both.

See also Adversarial Machine Learning for the broader field. Reference: Adversarial Robustness, Theory and Practice by Zico Kolter and Aleksander Madry.

Why ML is Not Naturally Robust

Standard ML assumes train and test data are i.i.d. from the same distribution. That breaks under:

• Model misspecification: true process is not in the model family
• Measurement error / dirty data
• Adversarial manipulation: the focus of this note

Toy example (non-robust mean): estimating $\mu$ from $X_1,\dots ,X_n\sim \mathcal{N}(\mu ,1)$ with the sample mean $\hat{\mu }=\frac{1}{n}\sum X_i$. A single outlier at $\approx 100n+\mu$ can shift $\hat{\mu }$ by $>100$. Robust alternatives: prune outliers, or use the median (a robust statistic with bounded influence of any single sample).

One poisoned sample can drag the mean arbitrarily far, so an attacker who owns even a single data point owns the estimator. The median can’t be pulled past the middle of the sorted samples, no matter how large the outlier, which is what “bounded influence” buys you.

Adversarial Example

Given trained model $f_{\theta }$ and test input $x$, an adversarial example $x^{\prime }$ satisfies:

1. $x\approx x^{\prime }$: same true label according to a human
2. $f_{\theta }(x)\ne f_{\theta }(x^{\prime })$: the model is fooled

Human perception is hard to encode, so we use ${\ell }_p$-distance as a proxy: $\Vert x-x^{\prime }{\Vert }_p\le \epsilon$. Most common are $p=0$ (sparse perturbations), $p=2$, and $p=\infty$ (pixel-level bounded).

Geometric picture

The ${\ell }_{\infty }$ ball is a hypercube: every pixel is free to wiggle up to $\epsilon$ independently. The ${\ell }_2$ ball is a sphere: a total “energy” budget you can concentrate in a few pixels or spread across many. ${\ell }_0$ says “change at most $k$ pixels, but to anything you want” (sticker attacks).

Other distances: Wasserstein, translations, rotations, resizing.

Attack Taxonomy

• White-box vs black-box: does the attacker know $\theta$?
• Targeted vs untargeted: force a specific wrong label $c$, or any wrong label?

Attacker: Fast Gradient Sign Method (FGSM)

FGSM crafts $x^{\prime }=x+\delta$ with $\Vert \delta {\Vert }_{\infty }\le \epsilon$ via a single gradient step: ${\delta }^{\prime }=\arg {\max }_{\Vert \delta {\Vert }_{\infty }\le \epsilon }\ell (x+\delta ,y,\theta )$

It takes the biggest linear step that stays in the ${\ell }_{\infty }$ ball: ${\delta }^{\ast }=\epsilon \cdot \text{sign}({\nabla }_{\delta }\ell (x+\delta ,y,\theta ))$

One step, one gradient computation. Fast, sometimes surprisingly effective.

Linearize the loss, then push every pixel by exactly $\epsilon$ in whichever direction raises the loss. Sign-of-gradient is the ${\ell }_{\infty }$-optimal direction because, under the cube constraint, each coordinate’s contribution is maximized independently at $\pm \epsilon$.

Projected Gradient Descent (PGD)

Multi-step FGSM, the de facto strongest first-order attack.

${\delta }^{(t+1)}={\text{Proj}}_{\Vert \cdot {\Vert }_{\infty }\le \epsilon }\left({\delta }^{(t)}+\eta \cdot \text{sign}({\nabla }_{\delta }\ell (x+{\delta }^{(t)},y,\theta ))\right)$

Project back into the ${\ell }_{\infty }$ ball at each step (clip each coordinate to $[-\epsilon ,\epsilon ]$).

FGSM assumes the loss is linear; real losses curve, so one step undershoots. PGD just runs many small FGSM steps and snaps back to the ball after each, climbing the loss surface while staying inside the allowed budget.

Untargeted vs Targeted

$\text{Untargeted: }{\max }_{\delta }\ell (x+\delta ,y,\theta )\text{s.t. }\Vert \delta {\Vert }_{\infty }\le \epsilon$ $\text{Targeted to }c:{\max }_{\delta }[\ell (x+\delta ,y,\theta )-\ell (x+\delta ,c,\theta )]\text{s.t. }\Vert \delta {\Vert }_{\infty }\le \epsilon$

Defense: Adversarial Training (Madry et al.)

Instead of minimizing expected loss, minimize robust expected loss: ${\min }_{\theta }{\mathbb{E}}_{(x,y)\sim p}\left[{\max }_{\Vert \delta {\Vert }_{\infty }\le \epsilon }\ell (x+\delta ,y,\theta )\right]$

This is a saddle-point (min-max) problem. To be a good defender you have to be a good attacker.

Intuition

Instead of training on the clean point $x$, train on the worst point inside its $\epsilon$-ball. You’re flattening the loss landscape around each training example, so no small perturbation can find a loss spike. The inner max finds the worst nearby example; the outer min teaches the model to handle it.

Training loop:

1. Sample minibatch $B$
2. For each $(x_i,y_i)\in B$, run PGD to compute ${\delta }_i^{\ast }=\arg {\max }_{\Vert {\delta }_i{\Vert }_{\infty }\le \epsilon }\ell (x_i+{\delta }_i,y_i,\theta )$
3. Gradient step: $\theta \leftarrow \theta -\frac{\eta }{|B|}{\sum }_i{\nabla }_{\theta }\ell (x_i+{\delta }_i^{\ast },y_i,\theta )$
4. Repeat

Expensive, each training step now runs a PGD inner loop.

The State of Play

Attacks remain more effective than defenses. A famous result: 7 out of 9 defenses submitted to ICLR 2018 were broken within a day of being accepted. Certified defenses (randomized smoothing, interval bound propagation) give provable but usually weak guarantees.

Backdoor Attacks

A different threat model: the attacker modifies the training data to plant a trigger. At test time, inputs containing the trigger are misclassified; clean inputs behave normally. Related to data poisoning.

Slides from CS480 lec16.

Related

• Adversarial Machine Learning
• Gradient Descent
• Neural Network
• Differential Privacy