The one-pixel lie, read closely

Take an image a network classifies correctly and confidently. Compute a specific, tiny perturbation — every pixel changed by at most a few values out of 255, far below what an eye can register — add it, and the same network now reports a different class with higher confidence than it had for the right answer. The picture still plainly shows a panda. The model is certain it is a gibbon. This is an adversarial example: an input built specifically to fool a model, and the reason security researchers stopped trusting “the model is 99% sure” as if it meant anything.

Szegedy and colleagues had reported these in 2013 and found something stranger still: the same perturbed image fools different models, trained on different subsets of the data, with different architectures. A bug that reproduces that precisely across independent systems is not a bug — it is telling you something about the function all those systems learned. The 2015 paper is the explanation, and it is refreshingly deflationary.

The intuitive story — the one most people reached for — blames complexity. Deep nets are wildly nonlinear function approximators with millions of parameters; surely they carve out pathological little pockets in input space, over-fit islands where the label flips, and the attack just finds them. Under that theory adversarial examples are rare, fragile accidents of over-training.

The paper's counter-argument is that if that were true, the examples would not transfer — two different models would over-fit to different pockets. They do transfer, reliably. So the vulnerability must live in something the models share. And the thing modern nets share, the authors point out, is that they are built to behave linearly on purpose: ReLUs are piecewise-linear, LSTMs and maxout units are designed to keep gradients flowing by staying close to linear, and we deliberately tune them to operate in their non-saturating regime. A model that is locally linear almost everywhere is easy to optimise — and, it turns out, easy to attack.

Here is the whole method. You have a trained model and a correctly-classified input x with true label y. You want the smallest change that raises the loss the most. If you constrain the change so no single coordinate moves by more than ε (the max-norm constraint, ‖η‖∞ ≤ ε — the formalisation of “imperceptible per pixel”), the loss-maximising step is to move every coordinate by exactly ε in the direction of its gradient's sign:

It is called fast because there is no iteration: one gradient, one sign, done. For a linear model — logistic regression is the cleanest case — the loss gradient with respect to the input is (σ(w·x + b) − y)·w, so the sign is just the sign of each weight (flipped if the point is on the wrong side). The site runs the TypeScript below; the Python and C++ are line-for-line translations.

def sigmoid(z):
    return 1 / (1 + math.exp(-z))

# Fast gradient sign method. For binary cross-entropy the gradient of the loss
# w.r.t. the INPUT is dJ/dx = (sigma(w.x + b) - y) * w, so the max-norm-bounded
# step that most increases the loss is eta = eps * sign((p - y) * w).
def fgsm(w, b, x, y, eps):
    p = sigmoid(dot(w, x) + b)
    s = sign(p - y)                       # push the loss up
    return [xi + eps * s * sign(wi)       # ||eta||_inf = eps, invisible per-pixel
            for xi, wi in zip(x, w)]

This is the part a skim misses, and the reason the linear explanation bites. Forget the network for a second and look at a single linear score, z = w·x + b. Apply the FGSM perturbation η = ε·sign(w). How much does the score move?

# Worst-case change in the linear score z = w.x + b under eta = eps * sign(w):
#   dz = w . eta = eps * sum(|w_i|) = eps * m * n
# with m = mean|w_i| and n = the input dimension. The per-pixel change is only
# eps, but the SCORE moves by eps*m*n -- and that grows with n.
def activation_shift(w, eps):
    return eps * sum(abs(wi) for wi in w)

The perturbation's size, measured the way we constrained it, never grows: every coordinate moved by ε, so ‖η‖∞ = ε no matter how many coordinates there are. But the score moves by ε·Σ|wᵢ| = ε·m·n, where m is the average weight magnitude and n is the number of inputs. That last factor is the whole paper: the damage grows with the dimension. A perturbation that is invisible on any one pixel becomes overwhelming once you have enough pixels to spread it across.

We can draw exactly that. Fix the budget ε = 0.25 (the paper's MNIST setting) and the mean weight m = 0.1, then sweep the input dimension from a single feature up to 784 — the size of a 28×28 MNIST image — and plot the worst-case score shift ε·m·n against a fixed decision margin (how much the score must move to flip the prediction). Holding m fixed is the honest way to isolate the effect: any rise in the curve is dimensionality alone, not a luckier draw of weights.

Now the same attack on a model you can see. We train the site's own logistic regression from scratch — full-batch gradient descent, zero init — on two seeded Gaussian blobs, then hit every point with FGSM and sweep the budget ε from 0 upward. At ε = 0 nothing is perturbed, so we read off the clean accuracy (100%). As ε grows, each point slides ε toward the boundary along the weight's sign, and accuracy falls off a cliff.

In two dimensions the effect is modest — you have to nudge visibly to do damage. That is the point of Fig 1: on a real image with hundreds of dimensions, the same attack needs a per-pixel ε far too small to see. The paper reports exactly that on real classifiers, and the numbers are worth sitting with.

The paper's second half is constructive: if the attack is one clean gradient step, you can train against it. Mix adversarial examples into the training set (or, more elegantly, add an FGSM term to the loss so every batch is attacked as it's learned) and the model learns to resist. On MNIST the authors take a maxout network from 0.94% clean test error to 0.84% — adversarial training evenhelped ordinary accuracy — and its error rate on adversarial examples falls from 89.4% to 17.9%.

The transferability the paper opened with returns here as a warning. Because the attack only needs sign(w), and independently trained models learn similar linear responses, an attacker who cannot see your model can craft examples on their own and expect them to carry over — a black-box attack for free. Linearity is what makes the fooling cheap, the confidence high, and the exploit portable.

• Find the crossover dimension analytically. Our curve passes the margin near n = 407 for ε·m = 0.025. The crossing is just n = margin / (ε·m) — a clean knob relating perturbation budget, weight scale, and how many features it takes before a model is attackable at all.
• Iterate the step. Replace the single FGSM step with a few small ones projected back into the ε-ball and re-run Fig 2. The accuracy cliff should arrive at a smaller ε — the gap between one-shot and iterative is exactly the gap the caveat warns about.
• Attack a nonlinear model on the site. The neural-net page trains a real MLP in your browser; its input-space gradient is a backprop away. Pointing FGSM at it would show whether the linear story survives one hidden layer — the paper bets it mostly does.

The classifier in Fig 2 is the same one on the logistic-regression page. Train it, read off its weights, and picture sign(w) as an arrow: an adversarial example is nothing more than a step of length ε along that arrow, taken on every axis at once. In two dimensions you can see it. In a million, you can't — and that is the whole vulnerability.