Adversarial Training and Robustness for Multiple Perturbations

Florian Tramèr; Dan Boneh

Source-linked AI summary

Adversarial Training and Robustness for Multiple Perturbations

Florian Tramèr, Dan Boneh

arXiv:1904.13000v2Apr 30, 2019cs.LGcs.CRstat.ML

TL;DR

The paper asks whether adversarial defenses can provide robustness to multiple perturbation types despite single-type guarantees and observed vulnerability trade-offs. It combines formal analysis with multi-perturbation training and an efficient ℓ1 attack, finding trade-offs, noncompetitive robustness, and gradient masking on MNIST.

Problem
Existing defenses are usually tailored to one perturbation type, leaving robustness to other attacks limited or unguaranteed, so the paper studies simultaneous robustness.
Method
The paper proves trade-offs in a simple statistical setting, introduces avg and max multi-perturbation training, and develops the Sparse ℓ1-Descent attack.
Results
Multi-perturbation models are not competitive with individually trained models; on MNIST, first-order training against ℓ1, ℓ2, and ℓ∞ attacks achieves 52% accuracy under gradient-free evaluation.
Takeaways & Limitations
The results indicate that extending adversarial robustness to multiple perturbation types remains difficult and that robustness to a union can be insufficient against affine compositions.
Takeaways & Limitations
Better multi-ℓp robustness may require costly gradient-free attacks or certified defenses, while current training strategies scale linearly with the number of perturbation types.

Abstract

from arXiv · show

Defenses against adversarial examples, such as adversarial training, are typically tailored to a single perturbation type (e.g., small $\ell_\infty$-noise). For other perturbations, these defenses offer no guarantees and, at times, even increase the model's vulnerability. Our aim is to understand the reasons underlying this robustness trade-off, and to train models that are simultaneously robust to multiple perturbation types. We prove that a trade-off in robustness to different types of $\ell_p$-bounded and spatial perturbations must exist in a natural and simple statistical setting. We corroborate our formal analysis by demonstrating similar robustness trade-offs on MNIST and CIFAR10. Building upon new multi-perturbation adversarial training schemes, and a novel efficient attack for finding $\ell_1$-bounded adversarial examples, we show that no model trained against multiple attacks achieves robustness competitive with that of models trained on each attack individually. In particular, we uncover a pernicious gradient-masking phenomenon on MNIST, which causes adversarial training with first-order $\ell_\infty, \ell_1$ and $\ell_2$ adversaries to achieve merely $50\%$ accuracy. Our results question the viability and computational scalability of extending adversarial robustness, and adversarial training, to multiple perturbation types.

1 Introduction

The paper studies whether models can be robust to multiple perturbation types, finding both theoretically necessary trade-offs and empirical costs, failures, and open challenges.

Motivation: Known defenses are tailored to one perturbation type and typically provide no guarantees against other attacks.
Motivation: The paper asks whether adversarial robustness to different perturbation types can be achieved simultaneously.
Formal analysis: The formal analysis defines mutually exclusive perturbations and shows that ℓ∞ versus ℓ1, and ℓ∞ versus rotations and translations, require different features.
Methods: The proposed multi-perturbation strategies train on all adversarial examples or only the worst example for each input.The avg strategy minimizes average error across perturbation types, while max targets the worst perturbation type.
Empirical results: 5-10% additional error is usually observed for models robust to multiple perturbations compared with models trained against each attack individually.
Empirical results: 52% accuracy on gradient-free attacks exposes gradient masking after first-order training against MNIST ℓ1, ℓ2, and ℓ∞ attacks.The models resist ℓ∞ attacks while giving the illusion of robustness to ℓ1 and ℓ2 attacks.

2 Theoretical Limits to Multi-perturbation Robustness

The paper formalizes unavoidable robustness trade-offs between multiple perturbation types and extends the analysis from norm-bounded noise to spatial and affine combinations.

Small ℓ∞ and ℓ1 perturbations: Robustness depends on the perturbation type because different perturbations target different features.The analysis contrasts a feature robust to small ℓ∞ noise with features vulnerable to ℓ∞ but useful against ℓ1 attacks.
Small ℓ∞ and ℓ1 perturbations: No classifier can achieve non-trivial average robustness against both the specified ℓ∞ and ℓ1 perturbations.The theorem’s bound is no better than the constant classifier, which has Radv(f; S∞) = Radv(f; S1) = 1/2.
Dual norms: For dual norms ℓp and ℓq with 1/p + 1/q = 1 and p < 2, the more robust feature reverses between the two norms.The perturbation required to flip the non-robust features has ℓp norm Θ(d^p) = o(1), while feature x0 is more robust under the dual ℓq norm.
Spatial and affine perturbations: The trade-off also holds between ℓ∞ noise and rotation-translation attacks, and affine combinations can exceed the strength of a union of attacks.For linear classifiers, robustness to a union of ℓp perturbations implies robustness to affine adversaries, whereas combining ℓ∞ and spatial perturbations can yield a stronger attack.
Spatial and affine perturbations: For linear classifiers, robustness to a union of ℓp perturbations equals robustness to the corresponding affine adversary.The equality is stated as Rmax_adv(f; Sp, Sq) = Radv(f; Saffine), and extends to models locally linear around data points.

3 New Attacks and Adversarial Training Schemes

The paper introduces multi-perturbation adversarial training strategies and SLIDE, an efficient alternative to the inefficient ℓ1 version of PGD.

Overview: The proposed evaluation combines theoretical results with empirical robustness studies on MNIST and CIFAR10.The schemes target the multi-perturbation risks defined in Equation (1), alongside a novel ℓ1 attack.
Multi-perturbation adversarial training: Multi-attack training replaces the single attack approximation with attacks Ai for each perturbation set Si.This construction yields training strategies corresponding to average and worst-case multi-perturbation risks.
Multi-perturbation adversarial training: The max strategy trains on the strongest adversarial example among all attacks for each input.It selects k* = arg maxk L(f(Ak(x)), y).
Multi-perturbation adversarial training: The avg strategy simultaneously trains on adversarial examples generated by all attacks.It replaces the maximum in the empirical adversarial risk with an average over the attack losses.
The SLIDE attack: The ℓ1 version of PGD is inefficient because each iteration updates only one perturbation coordinate.SLIDE instead updates many coordinates using a percentile threshold on gradient magnitudes and controls update sparsity.

4 Experiments

Experiments on MNIST and CIFAR10 evaluate multi-perturbation adversarial training, revealing robustness trade-offs, gradient masking, and gaps between achievable and optimal robustness.

Training and evaluation setup: MNIST and CIFAR10 experiments compare models trained on individual perturbations with models trained using average- and worst-case multi-perturbation strategies.The evaluation covers ℓp attacks and rotation-translation attacks, using gradient-based, decision-based, and spatial attacks.
Robustness trade-offs: Multi-perturbation models achieve higher combined accuracy than single-perturbation models but fail to attain the optimal error rates.On MNIST, this pattern appears for both unions of ℓp attacks and unions of ℓ∞ and rotation-translation attacks; CIFAR10 shows the same qualitative result.
Gradient masking on MNIST: 52% accuracy under gradient-free attacks exposes gradient masking in MNIST models trained against first-order ℓ1, ℓ2, and ℓ∞ attacks.These models resist ℓ∞ attacks while creating an illusion of robustness to ℓ1 and ℓ2 attacks; thresholding masks gradients for the latter norms.
Gradient masking on MNIST: Adv1 and Adv2 appear genuinely robust to their respective ℓ1 and ℓ2 perturbations despite converging to sub-optimal local minima of first-order training objectives.Their minima generalize better to stronger attacks than the lower-training-loss solution found by Adv∞ under gradient masking.
Generalization and combined attacks: CIFAR10 multi-perturbation models reach 100% training accuracy, indicating an increased adversarial generalization gap.The authors suggest these models may rely more on memorization because they fail to find features robust to both attacks.
Generalization and combined attacks: Affine combinations of ℓp perturbations are no stronger than their union, whereas combining ℓ∞ and rotation-translation attacks produces a stronger attack.Thus, robustness to a union of perturbations can remain insufficient against more complex combinations.

5 Discussion and Open Problems

Multi-perturbation adversarial training narrows but does not close the robustness gap, while gradient masking and computational cost remain open challenges.

Multi-perturbation defenses fail to achieve robustness competitive with training against individual attack types, although they narrow the gap.
For most data points, models are either robust to all perturbation types or none, suggesting that some examples are inherently easier to classify robustly.
First-order training against multiple ℓp-attacks suffers from gradient masking on MNIST.
Training cost scales linearly with the number of perturbation types, and reducing this dependency may be difficult for perturbation sets with near-empty intersection.
Related corruption studies also find that different classifiers excel under different corruption forms, leaving multi-perturbation robustness unresolved.

A Experimental Setup

The experiments train MNIST CNNs and CIFAR10 wide ResNets with attack-specific iteration budgets and a random-perturbation strategy for rotation-translations.

MNIST uses a CNN trained for 10 epochs with Adam, learning-rate decay, and weaker adversaries during the first epoch.PGD uses 40 iterations for ℓ∞ and 100 iterations for ℓ1 and ℓ2.
Rotation-translation training uses the attack from [11], selecting the worst of 10 randomly chosen transformations.
CIFAR10 uses a wide ResNet trained for 80k gradient-descent steps with batch size 128, momentum, weight decay, and scheduled learning-rate decay.

B Performance of the Sparse ℓ1-Descent Attack

SLIDE improves ℓ1 attack optimization by using denser gradient updates, outperforming standard PGD and Frank-Wolfe under suitable settings while requiring care with sparsity randomization.

Keeping q constant during training causes overfitting and failure to achieve general robustness, so q is sampled randomly from 80% to 99.5%.Training also increased the attack from 10 to 20 iterations because 10 iterations were insufficient for a strong attack.
Denser updates improve SLIDE because the ℓ1 steepest-descent vector is too sparse, updating only one perturbation index per iteration.
Frank-Wolfe's linearly decreasing step size O(1/k) may underperform on non-convex objectives by overemphasizing early steps.
SLIDE varies gradient-update sparsity through q and compares its loss evolution with steepest-descent PGD and Frank-Wolfe over up to 1,000 steps.The comparison is performed on undefended MNIST and CIFAR10 models.
For appropriate q, SLIDE vastly outperforms PGD and Frank-Wolfe on the evaluated undefended models.

C Breakdown of ℓp-Attacks on Adversarially Trained Models

The attack breakdown reveals that first-order evaluation can overstate robustness of adversarially trained MNIST models, especially when thresholding masks gradients for other norms.

Tables 4 and 5 report per-model accuracy against individual attacks, worst attacks within each perturbation type, and the union of all attacks.
Table 4 evaluates MNIST models with PGD, BAPP, SLIDE, EAD, Pointwise Attack, C&W, and Boundary Attack across ℓ∞, ℓ1, and ℓ2 perturbations.
Table 5 evaluates CIFAR10 models with PGD for ℓ∞ and SLIDE, EAD, and Pointwise Attack for ℓ1.
On MNIST, thresholding produces flat loss regions for ℓ∞ attacks but leaves first-order ℓ1 and ℓ2 attacks without information about which pixels to perturb.
Decision-based attacks bypass this masking and find adversarial examples in directions orthogonal to those explored by PGD.
Models trained against individual ℓ1 or ℓ2 attacks are empirically robust to their corresponding attacks, but Adv∞ can appear more robust to ℓ2-PGD because of gradient masking.
Thresholding filters help ℓ∞ robustness while masking gradients for ℓ1 and ℓ2 attacks in models trained against all three norms.

E Examples of Affine Combinations of Perturbations

Affine combinations interpolate between perturbation types, and the paper analyzes how rotation-translation attacks can transform feature distributions in ways that expose robustness trade-offs.

Examples: Figure 4 interpolates between ℓ1, ℓ∞, and rotation-translation attacks, including combinations of two attack types.The first column contains clean images; later images linearly interpolate between attacks, with red examples misclassified by a model trained against both types.
Statistical construction: An ℓ∞ perturbation can transform H_y into H_−y, while an ℓ1 perturbation changes G_y through the distinguished feature x_0.The construction uses r∞ = [0, −2yη, …, −2yη] and r1 = [−2x_0, 0, …, 0].
Robustness trade-off: The classifier’s accuracies against the two specific perturbations sum to one, so worst-case robustness is bounded by this trade-off.The paper explicitly states Pr[f(x + r∞) = y] + Pr[f(x + r1) = y] = 1 and identifies these perturbations as specific bounded attacks.
Rotation-translation attacks: A rotation-translation adversary randomly permutes x_0 among N positions, producing a distribution close to the hybrid distribution Z_y.The proof bounds the total-variation distance by O(1/√N) after applying the Gaussian-mixture lemma.
Composed attacks: Applying a rotation-translation adversary and its inverse in sequence yields a valid adversary that moves x_0 among at most N positions.The construction first maps samples toward Z_y and then maps them toward the opposite-label distribution.

G.1 Numerical Estimates for the Robustness Trade-off in Theorem 2

The numerical analysis compares robustness to individual and combined perturbation sets, showing that nonlinear models can be robust to a union of ℓ∞ and ℓ1 attacks even when affine combinations remain more damaging.

Individual attacks: For d ≥ 200, α = 2, and N = 49, distinct classifiers achieve adversarial risk below 10% against ℓ∞ and rotation-translation attacks.The classifiers are distinct, and the stated rotation-translation setting corresponds, for example, to translations by ±3 pixels.
Union versus affine combinations: For d ≥ 200, a nonlinear classifier achieves R_adv(g; S∞, S1) ≤ 35%, while every classifier has R_adv(f; S_affine) ≥ 50%.The result uses ℓ∞ budget ϵ = 3η/2 = 3/d and ℓ1 budget ϵ = 3.
Affine attack mechanism: The affine adversary can map samples from the task distribution to G_0,0, where x is independent of y and no classifier exceeds 50% accuracy.This establishes the 50% affine-robustness barrier for the specified construction.
Classifier structure: The robust classifier for S∞ ∪ S1 must be nonlinear, with nonlinearity introduced through applying sign to x_0.The sign operation limits the effect of ℓ1 perturbations on x_0 and forces budget onto the other features.
Accuracy calculation: For the stated classifier construction, the natural accuracy calculation is approximately 99%.The estimate combines the probability p0 = 1 − Φ(−2) ≈ 0.977 with the Gaussian feature-sum terms.
Linear-model comparison: A linear classifier can resist each perturbation in the union while an affine combination of them changes its decision.The constructed input cannot be successfully attacked by either the rotation-translation or ℓ∞ adversary, but the affine adversary flips the label.