Completing the Adaptive Evaluation of Adversarial-Example Defenses: the Open Exercises of Tramèr, Carlini, Brendel and Mądry (2020)

Tramèr, Carlini, Brendel and Mądry (2020) systematically re-evaluated thirteen recently published adversarial-example defenses from ICLR, ICML and NeurIPS, circumvented all of them with carefully hand-designed adaptive attacks, and closed each section of their study with explicit 'exercises for the reader' — open empirical and methodological questions that their evaluation leaves unanswered. The open core includes: whether statistical logit-based detection (the Odds are Odd test) resists logit-matching attacks when instantiated with adversarially trained classifiers; whether adversarial examples can be constructed that succeed with near-100% probability over the internal randomness of stochastic, high-variance defenses such as the GBZ generative classifier, without making sampling deterministic; whether differentiable approximations of non-differentiable defense components (k-WTA, USVT) exist that let direct gradient descent succeed and remove the need for BPDA; whether a different, more consistent loss can drive the majority-vote ensembles (error-correcting output codes, EMPIR) below the accuracy targets the source left open with a single untargeted restart; how detection should be combined with adversarial training; how many steps each attack needs until convergence, how sensitive the results are to the attack's hyper-parameters, and which attacks profit most from repetitions; and whether the two-check 'Turning a Weakness into a Strength' detector can be defeated with a feature adversary instead of the source's special-purpose interpolation attack, and whether it would have been more robust had it applied standard PGD (taking the sign of the gradient). No published resolution of these exercises is known to date: adjacent results break the detectors only on standard classifiers, treat stochastic pre-processing rather than high-variance generative classifiers, or improve one ensemble's training, leaving the exercises themselves open. The source poses these as a family of defense-specific exercises sharing one objective rather than a single question. The seven numbered exercises below pose the questions, and the sub-questions grouped under one number are conjunctive. Where a sub-question poses alternative branches joined by 'or', settling either branch settles that sub-question, whereas branches joined by 'and' are jointly required.

Background

Adversarial examples are inputs to machine-learning classifiers that have been modified by small, often imperceptible perturbations — conventionally bounded in the $\ell_\infty$ or $\ell_2$ norm, e.g. $\epsilon=8/255$ on CIFAR-10 — and that cause confident misclassification. A defense is any mechanism intended to make a classifier robust to such perturbations or to detect adversarial inputs before they are used. A defense evaluation is credible only under an adaptive attack: an attack designed with full knowledge of the defense and tailored to its specific mechanism, as opposed to generic attacks such as PGD (projected gradient descent, an iterative first-order method that maximizes the loss within the allowed perturbation ball). After several waves of proposed defenses were broken by stronger attacks, Tramèr, Carlini, Brendel and Mądry (2020) performed a detailed re-evaluation of thirteen recent defenses, documenting for each one the full process of developing the adaptive attack that circumvents it. They broke all thirteen and concluded that credible adaptive attacks must be hand-designed per defense: automated attack ensembles such as AutoAttack (Croce and Hein, 2020) only partially succeeded on two of the four defenses it overlaps with, and cannot be directly applied to detector-based defenses.

The defenses and attack tools that appear in the open questions are the following. The Odds are Odd detector (Roth, Kilcher and Hofmann, 2019) is a statistical test that flags an input as adversarial when the change of the classifier's logits (the per-class scores before the softmax) under randomly sampled noise deviates from clean-input behavior; it was broken by a logit-matching attack — PGD minimizing $\|z(x')-z(x_t)\|_2^2$, i.e. pushing the logits of an adversarial input onto those of a benign example $x_t$ of a different class — combined with EOT (expectation over transformation), which averages the attack objective over the defense's random noise so the crafted example is robust to that noise. Generative classifiers (Li, Bradshaw and Sharma, 2019) model the joint distribution of labels and inputs with variational autoencoders; the 'GBZ' variant scores each class with a loss aggregated over $K$ randomly sampled latent vectors, which makes inference stochastic and the class scores high-variance (the MNIST version misclassifies even clean inputs 5–10% of the time). k-WTA replaces standard activations with a $k$-winners-take-all rule that keeps only the top $k$ activations per layer; BPDA (backward pass differentiable approximation) backpropagates through such non-differentiable components by substituting the gradient of a smooth surrogate. Further analyzed defenses include majority-vote ensembles built from error-correcting output codes and diversity-regularized ensembles, a stochastic Mixup-interpolation inference procedure, matrix-estimation pre-processings that reconstruct the input before classification (ME-Net with USVT, the universal singular value thresholding estimator), the sparse-Fourier defense's iterative hard thresholding (IHT) pre-processing, and a defense that adversarially trains a bank of per-class detectors (one per class, each trained to recognize benign inputs of its class and reject perturbed inputs of other classes). A further detector-based defense (Hu et al., 2019, 'Turning a Weakness into a Strength') rejects an input when either its class probabilities change too much under small Gaussian noise or the number of PGD steps required to turn it into an adversarial example (the defense's #Steps check) is too large; the source evades it with a special-purpose attack that binary-searches an interpolation $x_\alpha=\alpha\cdot x'+(1-\alpha)\cdot x$ between the clean input $x$ and a high-confidence adversarial example $x'$.

Each section of the source paper ends with 'exercises for the reader': concrete open questions the authors deliberately left unanswered, and which their own conclusions suggest require defense-specific, manually designed attacks or training modifications rather than off-the-shelf tools. The exercises enumerated in the Problem Statement, taken together with the shared objective of deciding whether the analyzed defenses can be broken completely or hardened into genuine robustness, constitute the open problem; each exercise is separately bounded.

Problem Statement

The problem is the set of open exercises left by Tramèr, Carlini, Brendel and Mądry's (2020) re-evaluation, which share one objective: determine whether the analyzed defenses can be completely broken by stronger adaptive attacks, or whether some hardened instantiation of them is genuinely robust. The concrete questions, under the threat models of the original defenses (adaptive white-box attackers respecting the stated norm bounds, e.g. $\ell_\infty$ with $\epsilon=0.3$ on MNIST and $\epsilon=8/255$ on CIFAR-10), are:

1. Robust-classifier instantiation of statistical detection. How effective is the Odds are Odd noise-based logit test when the base classifier is adversarially trained, given that cross-class logit matching is known to be hard for robust models? Is there a better adaptive attack for this combined defense?

2. Reliable attacks on stochastic, high-variance defenses. Do there exist adversarial examples for the GBZ generative-classifier MNIST model (Li, Bradshaw and Sharma, 2019) that succeed with probability close to 100% over the classifier's internal randomness, without making the latent sampling deterministic — noting that the model itself has a 5–10% misclassification rate on clean inputs, so the answer may be a tight upper bound rather than a construction? Do some of the attacks described in the source — for example the feature-adversary attacks that match the model's internal representations to those of a benign input of another class, so that downstream statistics such as softmax outputs match as well — translate to other generative classifiers, such as the robust MNIST VAE-based classifier of Schott et al. (2019) and the disentangling-based VAE defenses of Willetts et al. (2019)?

3. Differentiable approximations and alternative implementations of defense pre-processing. Instead of performing a black-box attack, is there a smooth, differentiable approximation of k-WTA that allows direct gradient descent to succeed? Increasing the sparsity ratio $\gamma$ reduces the fluctuations in the network activations: is it possible to transfer adversarial examples from a less-sparse k-WTA model to the sparser model, analogous to a prior attack on Stochastic Activation Pruning? The sparse-Fourier defense's IHT pre-processing is differentiable — at each iteration of IHT the inner computation is a floating-point value: can the defense be broken if it is artificially made non-differentiable, e.g. by quantizing the output of IHT? And since one option for making models robust to $\ell_0$-attacks is to train a model against $\ell_1$-attacks, is there an approach that is specifically aimed at the $\ell_0$ norm? For ME-Net, why does training on randomly masked and reconstructed inputs lead to a base classifier with low yet non-trivial robustness — or can that base classifier be attacked with a stronger attack? And is there a differentiable version of USVT so as to remove the need for BPDA in the attack?

4. Loss design for majority-vote and ensemble defenses (error-correcting output codes and EMPIR, an ensemble of models trained at mixed numerical precision of weights and activations whose prediction is the majority vote of its members). For the error-correcting-code defense, is there a different loss function for PGD, so that an untargeted attack with a single restart reduces the model's accuracy below 5%, or are multi-targeted, multi-restart strategies unavoidable? If that defense returned the class only when all codeword bits agreed (and rejected the input otherwise), which would clearly reduce classifier accuracy, would it increase robustness? For EMPIR, where the source's deliberately simple — and inconsistent — averaged-probability loss already reduces the accuracy to 1.5%, can a stronger (probably consistent) loss function reduce the accuracy to 0%, and can it do so at $\epsilon=4/255$? Attacking each of the mixed-precision models individually, are they all similarly robust, or is one harder to attack than the others — and if the robustness of the models differs, how might a more consistent loss function look that attacks the full defense?

5. Training modifications when combining detection with adversarial training. Would adversarially training all detectors for each input (not just the negative-class ones) produce substantially higher robustness than observed — given that the source's multi-targeted attack (a targeted attack run separately for every target class, retaining the best adversarial example) reduced the ensemble-of-detectors defense's robust accuracy from 30% to 11% (integrated classifier) and from 55% to 37% (its generative-classifier variant) at 5% false positive rate, but not to zero? Conversely, can the accuracy of the defense be reduced further by better attacks, especially for the generative classifier? Are there other defenses that can be attacked by formulating an untargeted attack as a series of multiple targeted attacks?

6. Evaluation methodology. The optimal step size and the necessary number of iterations differ substantially between attacks and also between defenses: comparing a few attacks on the diversity-regularized ensemble (e.g. PGD, C&W, the Brendel–Bethge attack, as well as some score- and decision-based attacks), how many steps does each attack need until convergence, and how sensitive are the results to the attack's hyper-parameters (e.g. the step size)? Since repeating attacks a few times can substantially lower model accuracy, which attacks can profit most from repetitions? For the stochastic Mixup-Inference defense, how much more can the model's accuracy be reduced using more attack repetitions, and can EOT — which the source's evaluation did not need to use — be used to reduce the accuracy further?

7. The 'Turning a Weakness into a Strength' detector (Hu et al., 2019). Can this defense be defeated with a feature adversary, instead of the special-purpose interpolation attack constructed in the source? And if the defense had applied standard PGD, taking the sign of the gradient before the gradient steps (including inside its #Steps check), would it be more robust?

References

1. Florian Tramèr, Nicholas Carlini, Wieland Brendel, Aleksander Mądry. On Adaptive Attacks to Adversarial Example Defenses. NeurIPS 2020; arXiv:2002.08347, DOI 10.48550/arXiv.2002.08347. https://arxiv.org/abs/2002.08347
2. Kevin Roth, Yannic Kilcher, Thomas Hofmann. The Odds are Odd: A Statistical Test for Detecting Adversarial Examples. ICML 2019; arXiv:1902.04818. https://arxiv.org/abs/1902.04818
3. Hossein Hosseini, Sreeram Kannan, Radha Poovendran. Are Odds Really Odd? Bypassing Statistical Detection of Adversarial Examples. arXiv:1907.12138. https://arxiv.org/abs/1907.12138
4. Yingzhen Li, John Bradshaw, Yash Sharma. Are Generative Classifiers More Robust to Adversarial Attacks? ICML 2019; arXiv:1802.06552. https://arxiv.org/abs/1802.06552
5. Kaleel Mahmood, Deniz Gurevin, Marten van Dijk, Phuong Ha Nguyen. Beware the Black-Box: on the Robustness of Recent Defenses to Adversarial Examples. Entropy 23(10):1359, 2021; arXiv:2006.10876, DOI 10.3390/e23101359. https://arxiv.org/abs/2006.10876
6. Marco Maggipinto, Matteo Terzi, Gian Antonio Susto. β-Variational Classifiers Under Attack. IFAC-PapersOnLine 53(2):7903-7908, 2020; arXiv:2008.09010, DOI 10.1016/j.ifacol.2020.12.1979. https://arxiv.org/abs/2008.09010
7. Yue Gao, Ilia Shumailov, Kassem Fawaz, Nicolas Papernot. On the Limitations of Stochastic Pre-processing Defenses. NeurIPS 2022; arXiv:2206.09491. https://arxiv.org/abs/2206.09491
8. Thomas Philippon, Christian Gagné. Improved Robustness Against Adaptive Attacks With Ensembles and Error-Correcting Output Codes. arXiv:2303.02322. https://arxiv.org/abs/2303.02322
9. Francesco Croce, Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks (AutoAttack). ICML 2020; arXiv:2003.01690. https://arxiv.org/abs/2003.01690
10. Shengyuan Hu, Tao Yu, Chuan Guo, Wei-Lun Chao, Kilian Q. Weinberger. A New Defense Against Adversarial Images: Turning a Weakness into a Strength. NeurIPS 2019, pp. 1633–1644.
11. Lukas Schott, Jonas Rauber, Matthias Bethge, Wieland Brendel. Towards the First Adversarially Robust Neural Network Model on MNIST. ICLR 2019.
12. Matthew Willetts, Alexander Camuto, Stephen Roberts, Chris Holmes. Disentangling Improves VAEs' Robustness to Adversarial Attacks. 2019.