Non-evadable detection of adversarial examples from internal network statistics: existence, construction, and theoretical limits

Deep image classifiers are vulnerable to adversarial examples — inputs perturbed imperceptibly to cause misclassification — and a major line of defense proposes to detect manipulated inputs from statistical anomalies in the network's internal signals. Roth, Kilcher and Hofmann (ICML 2019) observed that logits of noisy adversarial inputs are biased toward the true class and built a statistical test achieving 99% true positive rate at 1% false positive rate on CIFAR-10. Hosseini, Kannan and Poovendran (2019) then showed that a white-box Logit Mimicry Attack, which makes adversarial logits statistically resemble benign ones, collapses this test and even detectors iteratively trained against adaptive attackers on ResNet-56/CIFAR-10, concluding that logit statistics are not a fundamental benign/adversarial distinction. The surviving open problem is whether any detector based on internal network statistics — alternative noise models, feature transforms, or richer representation statistics — can be made non-evadable against a fully informed adaptive attacker within practical distortion budgets, and whether this can be characterized theoretically. Later work sharpens but does not settle the question: generic adaptive attacks evade successive detector generations; Tramèr (ICML 2022) proved robust detection and robust classification equivalent up to computational efficiency and a factor of two in perturbation radius; Gluch and Goldwasser (2025) proved detection and mitigation equivalent for classification tasks and exhibited generative tasks where detection is provably impossible. The existence/impossibility question for classification remains open and is intertwined with adversarially robust classification itself.

Background

An adversarial example is an input to a machine-learning classifier obtained by adding a small, human-imperceptible perturbation to a legitimate input so that the classifier assigns a wrong label while the semantic content is unchanged. Attacks are usually formulated as constrained optimization: given a classifier $f$, a clean input $x$ with true label $y$, and a perturbation budget such as an $\ell_\infty$ bound $\|x'-x\|_\infty \le \epsilon$ (each pixel changed by at most $\epsilon$), find $x'$ with $f(x') \ne y$. Projected gradient descent (PGD) — repeatedly stepping along the gradient of the classifier's loss and projecting back into the allowed perturbation set — is the standard method for producing such inputs, and adversarial training, which minimizes the loss on PGD-generated inputs during learning, is the main known route to classifiers that remain correct under attack (Madry et al., 2017).

Because robust classification remains far from solved, a second defense paradigm is detection: a binary classifier (a detector) flags inputs believed to be adversarially manipulated. Many detectors rely on statistical regularities that appear to separate natural from adversarial inputs. A prominent instance is the statistical test of Roth, Kilcher and Hofmann (ICML 2019). The logits of a network — its pre-softmax outputs, one real-valued score per class — are stable under added random Gaussian noise for a natural input, whereas for an adversarial input the logit of the true class tends to rise under noise: the adversarial perturbation is 'overfitted' to the exact input and noise partially undoes it. Standardizing the expected logit changes against thresholds calibrated on benign data yields a test that reportedly detects 99% of adversarial inputs at a 1% false-positive rate on CIFAR-10 (true positive rate, TPR, is the fraction of adversarial inputs flagged; false positive rate, FPR, is the fraction of benign inputs wrongly flagged).

Hosseini, Kannan and Poovendran (2019) showed that this defense, and the detector class behind it, collapses under an adaptive attacker. In the white-box threat model, the attacker knows both the classifier and the detector (the security principle that the adversary is assumed to know the system). Their Logit Mimicry Attack (LMA) crafts targeted adversarial examples (inputs optimized to yield a specific wrong label, not merely any wrong label) whose clean and noise-averaged logits match the class-conditional logit profiles of benign images, so the test statistic sees nothing anomalous. On ResNet-56 (a 56-layer residual convolutional network) trained on CIFAR-10 (a standard benchmark of small, 32-by-32-pixel images in ten classes) with an $\ell_\infty$ budget of 8/255, LMA drives the TPR of the statistical test below 2.2% and of a stronger classifier-based detector below 1.6% at 5% FPR. A detector retrained on mimicry examples recovers to 62.7% TPR but falls to 1.7% under an attacker that jointly optimizes misclassification and detector evasion, and a detector iteratively retrained against successive adaptive attacks still reaches only 2.9% TPR at 5% FPR. The authors conclude that distinguishability of benign and adversarial logits is not a fundamental property of deep networks.

This exchange instantiates a longer empirical pattern: statistical detectors have repeatedly been broken by attackers who incorporate the defense into their own optimization (Carlini and Wagner, 2017, bypassed ten detection methods; Athalye, Carlini and Wagner, 2018, broke defenses that relied on obfuscated gradients), and adaptive-attack methodology became the de facto evaluation standard (Tramèr, Carlini, Brendel and Madry, NeurIPS 2020). What no participant settled is the structural question the pattern raises: is the collapse intrinsic — no internal statistic of a network can separate benign inputs from adversarial ones crafted by an attacker who optimizes against the detector — or an artifact of the particular statistics tried so far?

Problem Statement

Determine whether detection of adversarial examples from the internal statistics of a deep network can be non-evadable, by settling either of two linked forms of the question left open by the collapse of logit-statistical detection (Hosseini et al., 2019):

(1) Existence/construction. Under the white-box adaptive threat model — the attacker has full knowledge of the classifier and the detector and can jointly optimize input misclassification and detector evasion within a stated perturbation budget (e.g., $\ell_\infty$ or $\ell_2$ bounded distortion at practical magnitudes, such as 8/255 of the dynamic range on CIFAR-10) — exhibit a detector built from internal network statistics (logits under noise, alternative noise models, feature transforms, or richer statistics of intermediate representations) that maintains detection performance at least as strong as the benchmark established in the literature before the collapse (99% true positive rate at 1% false positive rate, as reported by Roth et al., ICML 2019) against all such attackers, or argue that none exists. The performance target is fixed by this benchmark and is not a free parameter of the answer. The existing negative evidence covers logits on one architecture and dataset and specific attack families, and later generic adaptive attacks (orthogonal projected gradient descent; statistical indistinguishability attacks) have evaded every tested successor detector.

(2) Impossibility/characterization. Establish a formal characterization: under an explicit threat model with stated attacker knowledge, computational resources, and perturbation-budget semantics at practical magnitudes — practical magnitudes being the standard CIFAR-10 threat-model budgets (for $\ell_\infty$, 8/255; Madry et al., 2017) — prove that no detector in a defined class of internal-statistic-based detectors is non-evadable, or prove existence (including by exhibiting conditions under which a detector computed from internal network statistics is certified non-evadable at such practical magnitudes, as distinct from the existing small-radius certified classifier-plus-detection constructions). The defined detector class must be broad enough to cover the internal-statistics paradigm as studied in the literature (logit-noise statistics, feature-space statistics, and richer intermediate-representation statistics); degenerate classes or unbounded perturbation budgets do not address the question. Any such characterization must engage the known barriers: robust detection and robust classification are equivalent up to computational efficiency and a factor of two in perturbation radius (Tramèr, 2022), and for classification tasks defense by detection is equivalent to defense by mitigation (Gluch and Goldwasser, 2025).

The two directions of the question are linked: a detector built from internal network statistics with a formal non-evadability guarantee — a certificate or proof holding against all white-box adaptive attackers within the stated threat model and at practical perturbation budgets — and, in the opposite direction, an impossibility theorem for a stated detector class and threat model satisfying the conditions above. A non-evadibility guarantee must hold against all white-box adaptive attackers within the stated threat model and at practical perturbation budgets; robustness demonstrated only against currently known attack families, however strong, does not constitute one.

References

1. Hossein Hosseini, Sreeram Kannan, Radha Poovendran, 'Are Odds Really Odd? Bypassing Statistical Detection of Adversarial Examples', 2019, arXiv:1907.12138, https://arxiv.org/abs/1907.12138
2. Kevin Roth, Yannic Kilcher, Thomas Hofmann, 'The Odds are Odd: A Statistical Test for Detecting Adversarial Examples', ICML 2019, PMLR 97:5498-5507, arXiv:1902.04818, https://proceedings.mlr.press/v97/roth19a.html
3. Nicholas Carlini, David Wagner, 'Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods', 2017, arXiv:1705.07263, https://arxiv.org/abs/1705.07263
4. Anish Athalye, Nicholas Carlini, David Wagner, 'Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples', ICML 2018, arXiv:1802.00420, https://arxiv.org/abs/1802.00420
5. Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, Adrian Vladu, 'Towards Deep Learning Models Resistant to Adversarial Attacks', 2017, arXiv:1706.06083, https://arxiv.org/abs/1706.06083
6. Florian Tramèr, Nicholas Carlini, Wieland Brendel, Aleksander Madry, 'On Adaptive Attacks to Adversarial Example Defenses', NeurIPS 2020, arXiv:2002.08347, https://arxiv.org/abs/2002.08347
7. Florian Tramèr, 'Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Them', ICML 2022, PMLR 162:21692-21702, arXiv:2107.11630, https://proceedings.mlr.press/v162/tramer22a.html
8. Qiuling Xu, Guanhong Tao, Siyuan Cheng, Xiangyu Zhang, 'Towards Feature Space Adversarial Attack', 2020, arXiv:2004.12385, https://arxiv.org/abs/2004.12385
9. Oliver Bryniarski, Nabeel Hingun, Pedro Pachuca, Vincent Wang, Nicholas Carlini, 'Evading Adversarial Example Detection Defenses with Orthogonal Projected Gradient Descent', ICLR 2022, arXiv:2106.15023, https://arxiv.org/abs/2106.15023
10. Yigitcan Kaya, Muhammad Bilal Zafar, Sergul Aydore, Nathalie Rauschmayr, Krishnaram Kenthapadi, 'Generating Distributional Adversarial Examples to Evade Statistical Detectors', ICML 2022, PMLR v162, https://proceedings.mlr.press/v162/kaya22a.html
11. Fatemeh Sheikholeslami, Ali Lotfi, J. Zico Kolter, 'Provably robust classification of adversarial examples with detection', ICLR 2021, OpenReview forum sRA5rLNpmQc, https://openreview.net/forum?id=sRA5rLNpmQc
12. Byunggill Joe, Jihun Hamm, Sung Ju Hwang, Sooel Son, Insik Shin, 'Learning to Separate Clusters of Adversarial Representations for Robust Adversarial Detection', 2020, arXiv:2012.03483, https://arxiv.org/abs/2012.03483
13. Tianyu Pang, Huishuai Zhang, Di He, Yinpeng Dong, Hang Su, Wei Chen, Jun Zhu, Tie-Yan Liu, 'Two Coupled Rejection Metrics Can Tell Adversarial Examples Apart', CVPR 2022, arXiv:2105.14785, doi:10.1109/CVPR52688.2022.01479, https://arxiv.org/abs/2105.14785
14. 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
15. Samuele Marro, Michele Lombardi, 'Computational Asymmetries in Robust Classification', ICML 2023, PMLR v202, arXiv:2306.14326, https://proceedings.mlr.press/v202/marro23a.html
16. Greg Gluch, Shafi Goldwasser, 'A Cryptographic Perspective on Mitigation vs. Detection in Machine Learning', 2025, arXiv:2504.20310, https://arxiv.org/abs/2504.20310
17. Nils Palumbo, Yang Guo, Xi Wu, Jiefeng Chen, Yingyu Liang, Somesh Jha, 'Two Heads are Actually Better than One: Towards Better Adversarial Robustness via Transduction and Rejection', ICML 2024, PMLR v235, arXiv:2305.17528, https://proceedings.mlr.press/v235/palumbo24a.html
18. Dipkamal Bhusal, Md Tanvirul Alam, Monish K. Veerabhadran, Michael Clifford, Sara Rampazzi, Nidhi Rastogi, 'PASA: Attack Agnostic Unsupervised Adversarial Detection using Prediction & Attribution Sensitivity Analysis', IEEE EuroS&P 2024, arXiv:2404.10789, doi:10.1109/EuroSP60621.2024.00010, https://arxiv.org/abs/2404.10789
19. Rohan Gupta, Erik Jenner, 'RL-Obfuscation: Can Language Models Learn to Evade Latent-Space Monitors?', 2025, arXiv:2506.14261, https://arxiv.org/abs/2506.14261