Mind the box: l1-APGD for sparse adversarial attacks on image classifiers

Francesco Croce, Matthias Hein

Abstract

We show that when taking into account also the image domain $[0,1]^d$, established $l_1$-projected gradient descent (PGD) attacks are suboptimal as they do not consider that the effective threat model is the intersection of the $l_1$-ball and $[0,1]^d$. We study the expected sparsity of the steepest descent step for this effective threat model and show that the exact projection onto this set is computationally feasible and yields better performance. Moreover, we propose an adaptive form of PGD which is highly effective even with a small budget of iterations. Our resulting $l_1$-APGD is a strong white-box attack showing that prior works overestimated their $l_1$-robustness. Using $l_1$-APGD for adversarial training we get a robust classifier with SOTA $l_1$-robustness. Finally, we combine $l_1$-APGD and an adaptation of the Square Attack to $l_1$ into $l_1$-AutoAttack, an ensemble of attacks which reliably assesses adversarial robustness for the threat model of $l_1$-ball intersected with $[0,1]^d$.

Introduction

Adversarial machine learning usually focuses on $l_\infty$ (small changes to all pixels) or $l_2$ (small Euclidean distance) perturbations. $l_1$-perturbations are unique because they are sparse: they allow for large changes to a very small number of pixels. However, a major flaw exists in current $l_1$ Projected Gradient Descent (PGD) attacks. In image classification, an adversarial example must satisfy two constraints simultaneously: it must be within an $l_1$-distance $\epsilon$ of the original image, and every pixel value must remain within the valid range $[0, 1]^d$ (the "box" constraint).

The Geometry of Sparse Attacks

Previous attacks often treated these constraints separately—typically projecting onto the $l_1$-ball and then simply "clipping" the values to $[0, 1]$. This paper proves that this approximation is suboptimal; it "hides" parts of the valid search space, making the attacks weaker. Clipping an $l_1$-projected image to the box actually reduces the $l_1$ distance to the original image, meaning the attacker isn't using their full budget $\epsilon$.

Extracted figure from page 2 of Mind the box: l1-APGD for sparse adversarial attacks on image classifiers

Methodology: $l_1$-APGD

The authors introduce several mathematical and algorithmic innovations to "mind the box":

  • Exact Projection onto the Intersection: They derive an $O(d \log d)$ algorithm to project a point exactly onto the intersection of the $l_1$-ball and the $[0, 1]^d$ box. This is computationally as efficient as standard projection but yields much stronger attacks.
  • Box-Aware Steepest Descent: They prove that with box constraints, the "steepest" direction involves a specific number of coordinates ($k$) depending on proximity to boundaries, rather than just a single coordinate.
  • Adaptive PGD ($l_1$-APGD): This version is parameter-free, automatically adjusting step size and update sparsity. It employs a "multi-$\epsilon$" strategy, starting with a larger budget to find high-loss regions before narrowing down to the target $\epsilon$.

Experimental Results

Evaluating on benchmarks like CIFAR-10 and ImageNet, $l_1$-APGD consistently outperforms previous standards like SLIDE or EAD. The exact projection is shown to be critical for maximizing loss and minimizing robust accuracy.

Comparison of $l_1$-APGD variants against baselines. The left plot shows loss maximization, while the right plot shows robust accuracy over iterations. Solid lines represent the exact projection $P_S$, while dashed lines represent the suboptimal $l_1$+clipping approach.

By using $l_1$-APGD inside the adversarial training loop, the authors produced a model with 60.3% robust accuracy at $\epsilon=12$ on CIFAR-10, a massive improvement over previous models that typically hovered below 10% or required much more complex setups.

Conclusion

By correctly accounting for the intersection of the $l_1$-ball and the image box, $l_1$-APGD provides a more accurate assessment of model robustness. The proposed $l_1$-AutoAttack ensemble serves as a new "gold standard" for evaluating sparse adversarial robustness, showing that many prior works significantly overestimated their models' resilience.

Summary updated

Abstract

We show that when taking into account also the image domain $[0,1]^d$, established $l_1$-projected gradient descent (PGD) attacks are suboptimal as they do not consider that the effective threat model is the intersection of the $l_1$-ball and $[0,1]^d$. We study the expected sparsity of the steepest descent step for this effective threat model and show that the exact projection onto this set is computationally feasible and yields better performance. Moreover, we propose an adaptive form of PGD which is highly effective even with a small budget of iterations. Our resulting $l_1$-APGD is a strong white-box attack showing that prior works overestimated their $l_1$-robustness. Using $l_1$-APGD for adversarial training we get a robust classifier with SOTA $l_1$-robustness. Finally, we combine $l_1$-APGD and an adaptation of the Square Attack to $l_1$ into $l_1$-AutoAttack, an ensemble of attacks which reliably assesses adversarial robustness for the threat model of $l_1$-ball intersected with $[0,1]^d$.
BibTeX
@inproceedings{croce2021mind,
  author = {Francesco Croce and Matthias Hein},
  title = {{Mind the box: l1-APGD for sparse adversarial attacks on image classifiers}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=9zGtMJ8rdC},
}

Loading related content...

Figure