Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack

Francesco Croce, Matthias Hein

Abstract

The evaluation of robustness against adversarial manipulation of neural networks-based classifiers is mainly tested with empirical attacks as methods for the exact computation, even when available, do not scale to large networks. We propose in this paper a new white-box adversarial attack wrt the $l_p$-norms for $p \in \{1,2,\infty\}$ aiming at finding the minimal perturbation necessary to change the class of a given input. It has an intuitive geometric meaning, yields quickly high quality results, minimizes the size of the perturbation (so that it returns the robust accuracy at every threshold with a single run). It performs better or similar to state-of-the-art attacks which are partially specialized to one $l_p$-norm, and is robust to the phenomenon of gradient masking.

Introduction

Deep learning models are notoriously fragile; small, imperceptible changes to an input, known as adversarial examples, can cause them to fail. To build safer models, researchers must accurately measure "robustness"—the minimum perturbation magnitude required to flip a model's prediction.

Current evaluation methods typically fall into two categories: exact solvers, which are computationally prohibitive for large networks, and empirical attacks like Projected Gradient Descent (PGD). However, PGD suffers from several drawbacks: it is highly sensitive to hyperparameter tuning (e.g., step size), inefficient for calculating accuracy across multiple thresholds ($\epsilon$), and susceptible to "gradient masking," where defenses hide gradients to give a false sense of security. The Fast Adaptive Boundary (FAB) attack addresses these issues by directly targeting the decision boundary.

The Fast Adaptive Boundary (FAB) Attack

The FAB-attack is an iterative algorithm that treats the neural network as a collection of local linear approximations. Its core logic follows three main steps:

  1. Linearization and Projection: At each iteration, the classifier is linearized to identify the nearest decision hyperplane. The current point is then projected onto the intersection of this hyperplane and the valid input space using an efficient $O(d \log d)$ algorithm.
  2. Biased Gradient Step: Unlike previous boundary attacks like DeepFool, FAB introduces a "bias" toward the original image. It takes a convex combination of the projection of the current point and the projection of the original point. This ensures the attack stays "tight" to the original input, minimizing the final perturbation size.
  3. Backward Step and Final Search: Upon finding an adversarial point, the algorithm performs a "backward step" toward the original image followed by a modified binary search to pinpoint the exact decision flip.
Geometric illustration of the FAB attack iteration

Crucially, the attack is scaling invariant. By utilizing the geometry of the decision boundary rather than the magnitude of the loss gradient, it remains effective regardless of logit scaling or constant shifts.

Experimental Evaluation

The authors evaluated the FAB-attack on MNIST, CIFAR-10, and Restricted ImageNet, testing both standard and adversarially trained models.

Key Insights

  • Single Run Efficiency: Because FAB seeks the minimal perturbation, a single run provides the robust accuracy for every possible threshold $\epsilon$. This significantly improves research productivity compared to PGD.
  • Immunity to Gradient Masking: FAB is robust to defenses that flatten or noise the loss surface. By focusing on the difference between class outputs (logits), it can find vulnerabilities where gradient-based methods like PGD fail.
  • Parameter-Free Reliability: FAB does not require manual step-size tuning, making it a reliable "off-the-shelf" tool across different architectures.

Results

In aggregated benchmarks, FAB-100 (100 restarts) consistently achieved the lowest robust accuracy (indicating the strongest attack) compared to state-of-the-art methods like PGD, Carlini-Wagner (CW), and DeepFool. Notably, FAB-10 often outperformed PGD-100 while being faster.

FAB breaking a defense where PGD fails

As shown in the table above, FAB successfully broke a defense that claimed ~31% robustness, where PGD failed catastrophically, revealing the true robust accuracy to be a mere 0.3%.

Conclusion

The FAB-attack provides a fast, parameter-free, and reliable method for evaluating adversarial robustness. While it faces computational challenges regarding Jacobian calculations for datasets with many classes (like ImageNet), the proposed "targeted" version mitigates this. Future research may explore using FAB's geometric approach for adversarial training to develop more robust models.

Summary updated

Abstract

The evaluation of robustness against adversarial manipulation of neural networks-based classifiers is mainly tested with empirical attacks as methods for the exact computation, even when available, do not scale to large networks. We propose in this paper a new white-box adversarial attack wrt the $l_p$-norms for $p \in \{1,2,\infty\}$ aiming at finding the minimal perturbation necessary to change the class of a given input. It has an intuitive geometric meaning, yields quickly high quality results, minimizes the size of the perturbation (so that it returns the robust accuracy at every threshold with a single run). It performs better or similar to state-of-the-art attacks which are partially specialized to one $l_p$-norm, and is robust to the phenomenon of gradient masking.
BibTeX
@inproceedings{croce2020minimally,
  author = {Francesco Croce and Matthias Hein},
  title = {{Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=juYt5BN3ERR},
}
Figure