Abstract
Evaluating the robustness of deep learning models against adversarial attacks is a notoriously slow process, often requiring hundreds of GPU hours. This paper introduces the Constraint Relaxation Attack (CR Attack), a novel framework that achieves up to a 38x speedup over the industry-standard AutoAttack. By temporarily "breaking the rules" of perturbation limits during the optimization process, CR Attack finds even stronger adversarial examples than current ensemble methods.
Introduction
Deep neural networks are famously vulnerable to adversarial examples—inputs with tiny, imperceptible perturbations designed to fool a model. To build secure AI, researchers use "robustness evaluations" to measure model resilience. The current gold standard, AutoAttack, is a highly reliable ensemble method but is computationally grueling. For instance, evaluating two top-tier models on CIFAR-10 can take nearly 300 hours on a high-end GPU. This "computational tax" significantly slows the research cycle for new defense mechanisms. CR Attack addresses this by maintaining rigorous evaluation standards while drastically reducing time and hardware requirements.
Methods: The Power of Relaxation
The core innovation is a strategy called Constraint Relaxation (CR). In standard attacks, algorithms search for a perturbation $\delta$ within a strict "budget" $\epsilon$. This often leads to the optimizer getting stuck in "local optima"—mathematical dead ends where the attack stops improving.
CR Attack employs a two-phase approach:
- Exploration Phase: The algorithm temporarily relaxes the budget, allowing the perturbation to expand to $\epsilon + \alpha$. This larger search space allows the optimizer to "jump over" defensive barriers and find effective attack directions invisible within the strict $\epsilon$ boundary.
- Refinement Phase: The algorithm then systematically tightens the constraint back to the original $\epsilon$ and halves the step size. This ensures the final adversarial example is valid while benefiting from the superior path found during the relaxed phase.
Crucially, CR Attack is parameter-free, requiring no manual tuning for different models or datasets, making it a drop-in replacement for existing tools.
Key Insights and Complementarity
Adversarially trained models often create "flat" or "jagged" loss landscapes within the $\epsilon$ boundary to trip up optimizers. By stepping outside that boundary, CR Attack renders many of these defensive "traps" ineffective. Through "Complementarity Analysis," the authors demonstrated that CR Attack identifies almost all vulnerabilities found by AutoAttack, plus additional weaknesses that AutoAttack misses entirely.
Results
The researchers evaluated CR Attack using 105 robust models from the RobustBench leaderboard across CIFAR-10, CIFAR-100, and ImageNet.
Key findings include:
- Superior Strength: CR Attack achieved a higher Attack Success Rate (ASR) than AutoAttack on 95 out of 105 models.
- Massive Speedup: On average, the method was 38.3x faster in forward propagation and 15.9x faster in backward propagation. On CIFAR-10, forward speedup reached 46x.
- Consistency: Ablation studies confirmed that the relaxation strategy is the primary driver of performance; removing the relaxation module caused significant drops in attack effectiveness across all models.
Conclusion and Future Work
CR Attack demonstrates that violating constraints early in the optimization process actually makes it easier to satisfy them effectively later. While highly effective as a standalone tool, integrating it into existing ensembles yielded only modest gains, suggesting its benefits are tied to its specific optimization strategy. Future work includes adapting relaxation for non-gradient-based attacks, exploring its use during adversarial training, and applying the technique to non-vision domains like Large Language Models (LLMs).
Summary updated