Towards Million-Scale Adversarial Robustness Evaluation With Stronger Individual Attacks

Yong Xie, Weijie Zheng, Hanxun Huang, Guangnan Ye, Xingjun Ma

TL;DR

The authors introduce the Probability Margin Attack (PMA), a powerful new individual adversarial attack that operates in the probability space rather than the traditional logit space, achieving state-of-the-art white-box attack strength at a fraction of the cost of ensemble methods. To test model robustness at a realistic scale, they also introduce CC1M, a new million-scale dataset, revealing a massive "robustness gap" where top-tier models that look secure on small benchmarks fail drastically in large-scale evaluations.

What Problem Does This Paper Address?

Evaluating deep neural networks (DNNs) against adversarial perturbations—tiny, imperceptible changes to inputs that cause misclassification—is critical for safety-critical deployments. However, current evaluation methods face a harsh trade-off between efficiency and effectiveness:

  1. Strong Ensemble Attacks (like AutoAttack) combine multiple attack strategies to reliably find vulnerabilities, but they are computationally expensive and scale poorly.
  2. Individual Attacks (like Projected Gradient Descent, or PGD) are fast but often overestimate model robustness because they get trapped by gradient anomalies (e.g., obfuscated or imbalanced gradients).

Furthermore, standard robustness benchmarks are small (typically using the 50,000-image ImageNet-1k test set). This small scale fails to reflect real-world deployment conditions, leaving a major blind spot regarding how robust these models truly are when facing millions of diverse images.

Methods

The core innovation is the Probability Margin Loss (PML). Traditional margin losses calculate the difference between the logit of the correct class and the maximum logit of the incorrect classes ($z_{max} - z_y$). PMA shifts this calculation into the probability space ($p_{max} - p_y$).

By using probabilities (which include a softmax denominator), the loss function implicitly considers all logit directions simultaneously, opening up more diverse paths for generating adversarial examples. Mathematically, the gradient of PML acts as a dynamically weighted combination of both targeted and untargeted cross-entropy losses, making the attack highly adaptive.

The authors integrate this loss into a two-stage pipeline:

  • Stage 1 (Exploration): Alternates between maximizing the probability of the most competitive incorrect class ($p_{max}$) and suppressing the correct class ($p_y$).
  • Stage 2 (Exploitation): Attacks the full probability margin loss to maximize the final perturbation strength.

To evaluate unlabeled large-scale data, they define a Relative Robustness metric, which measures how often an attack changes a model's clean-image prediction, rather than relying on ground-truth labels.

Datasets

The paper evaluates models across standard benchmarks and a newly curated large-scale dataset:

  • Standard Benchmarks: CIFAR-10, CIFAR-100, and ImageNet-1k.
  • CC1M (New): A million-scale evaluation dataset derived from the Conceptual Captions 3 Million (CC3M) dataset. The authors filtered out broken URLs and noisy images, and applied Local Intrinsic Dimensionality (LID) combined with Median Absolute Deviation (MAD) to remove geometric outliers, leaving 1 million clean, semantically diverse images.

Key Insights and Ideas

  • The Power of the Softmax Denominator: Moving from logit space to probability space isn't just a mathematical re-framing; it prevents the attack from hyper-focusing on a single adversarial direction. It provides a regularization effect that naturally shifts focus to the most effective optimization path as the attack progresses.
  • The Million-Scale Robustness Gap: Model evaluation does not scale linearly. A model's defense mechanisms can hold up well against tens of thousands of images but collapse when exposed to a million images.
  • Ensemble Strength at Individual Speed: PMA achieves a level of attack success close to AutoAttack while requiring only 3% of its computation time, proving that individual attacks can be structurally optimized to match complex ensembles.

Key Results

  • Strongest Individual Attack: PMA consistently outperformed existing individual attacks (like standard PGD and Margin Decomposition) across 29 top-ranked models on the RobustBench leaderboard, reducing evaluated robust accuracy by up to 1.56%.
  • Competitive Ensembles (PMA+): By pairing PMA with a multi-targeted APGD attack (forming an ensemble called PMA+), the authors surpassed the gold-standard AutoAttack on several CIFAR-10 models while cutting execution time by 75%.
  • The CC1M Collapse: When evaluated on the million-scale CC1M dataset, the relative robustness of the top 5 ImageNet models dropped drastically from over 59% down to below 19%. This massive drop highlights that current models are far more vulnerable in large-scale deployments than standard benchmarks suggest.
Figure 1. Relative robustness evaluation on CC1M and ImageNet- 1k test set. x-axis: top-5 (on RobustBench leaderboard) defense models adversarially trained on ImageNet; y-axis: relative robust- ness. Left: The red and blue lines represent the relative robust- ness measured on CC1M and ImageNet-1k test set, respectively. Right:The red and blue bars represent the relative robustness mea- sured on CC1M by PGDce and our PMA, respectively.

Limitations and Future Work

While PMA+ is significantly faster than AutoAttack, it still demands notable computational time when scaled to millions of images, making it less ideal for rapid, iterative training loops. Additionally, the current formulation of PMA is strictly limited to white-box settings, where the attacker has full access to the model's gradients. The authors note that extending this probability-margin approach to black-box scenarios remains an open and challenging direction for future research.

Summary updated

Abstract

As deep learning models are increasingly deployed in safety-critical applications, evaluating their vulnerabilities to adversarial perturbations is essential for ensuring their reliability and trustworthiness. Over the past decade, a large number of white-box adversarial robustness evaluation methods (i.e., attacks) have been proposed, ranging from single-step to multi-step methods and from individual to ensemble methods. Despite these advances, challenges remain in conducting meaningful and comprehensive robustness evaluations, particularly when it comes to large-scale testing and ensuring evaluations reflect real-world adversarial risks. In this work, we focus on image classification models and propose a novel individual attack method, Probability Margin Attack (PMA), which defines the adversarial margin in the probability space rather than the logits space. We analyze the relationship between PMA and existing cross-entropy or logits-margin-based attacks, and show that PMA can outperform the current state-of-the-art individual methods. Building on PMA, we propose two types of ensemble attacks that balance effectiveness and efficiency. Furthermore, we create a million-scale dataset, CC1M, derived from the existing CC3M dataset, and use it to conduct the first million-scale white-box adversarial robustness evaluation of adversarially-trained ImageNet models. Our findings provide valuable insights into the robustness gaps between individual versus ensemble attacks and small-scale versus million-scale evaluations.
BibTeX
@inproceedings{xie2025towards,
  author = {Yong Xie and Weijie Zheng and Hanxun Huang and Guangnan Ye and Xingjun Ma},
  title = {{Towards Million-Scale Adversarial Robustness Evaluation With Stronger Individual Attacks}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2025},
  doi = {10.1109/cvpr52734.2025.02859},
}
Figure