Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack

Francesco Croce, Matthias Hein

Introduction

To trust neural networks in safety-critical applications, we must rigorously evaluate their robustness against adversarial examples—inputs specifically crafted to trick a model. Currently, the field relies heavily on two types of attacks: fixed-budget attacks like Projected Gradient Descent (PGD) and minimal-distortion attacks like DeepFool or Carlini-Wagner (CW).

Both approaches have significant drawbacks. Fixed-budget attacks check if a model can be fooled within a specific "distance" (e.g., an $\epsilon$-ball), requiring researchers to run the attack multiple times for every possible $\epsilon$ to get a full picture of robustness. Minimal-distortion attacks try to find the closest possible adversarial point but are often slow or produce low-quality results. Furthermore, many models exhibit "gradient masking," where the model's gradients become useless for optimization, giving a false sense of security against standard attacks.

To address these issues, researchers have introduced the Fast Adaptive Boundary (FAB) attack, a white-box adversarial method that finds the smallest possible change needed to fool a neural network quickly and reliably.

How the FAB Attack Works

FAB is an iterative white-box attack designed for $l_1, l_2,$ and $l_\infty$ norms. Crucially, FAB is parameter-free, meaning it requires no step-size tuning. It uses the geometric properties of the model's decision surface to determine how far to move, making it ready to use off-the-shelf for any new architecture.

Its core logic relies on three main components:

  1. Projection onto the Decision Boundary: At each step, the algorithm creates a local linear approximation of the model. It then solves a convex optimization problem to project the current point onto the intersection of the decision boundary and the valid input space (e.g., valid image pixel values).
  2. Biased Gradient Step: Unlike previous methods that search for any boundary, FAB uses a "biased" step that pulls the search toward the original image ($x_{orig}$). This ensures the attack stays focused on finding the minimal distortion.
  3. Backward Step & Final Search: If the algorithm finds an adversarial point, it performs a "backward step" to move closer to the original image, followed by a modified binary search to pinpoint the exact boundary.
Diagram illustrating the biased gradient step in the FAB attack, pulling the projection towards the original image to minimize distortion.

Key Advantages

  • Scaling Invariance: FAB is mathematically invariant to the scaling of the model's outputs (logits). Many proposed "defenses" simply squash or stretch logits to break gradient-based attacks. FAB ignores this "masking" and finds the true boundary.
  • Efficiency via "One-and-Done": Because FAB finds the minimal distance to the boundary, a single run provides the "robust accuracy" for every possible threshold $\epsilon$. PGD, by contrast, requires a fresh set of restarts for every $\epsilon$ value tested.

Experimental Results

The researchers evaluated FAB on standard benchmarks including MNIST, CIFAR-10, and Restricted ImageNet, testing against both "plain" models and models specifically trained to be robust (Adversarial Training).

Superior Performance and Speed: In head-to-head comparisons, FAB-100 (100 restarts) achieved the lowest robust accuracy (indicating it is the strongest attack) across $l_1, l_2,$ and $l_\infty$ norms, frequently outperforming specialized attacks like CW or EAD. Furthermore, FAB-10 is significantly faster than PGD-100 while maintaining comparable or better attack strength. On CIFAR-10, FAB-10 was roughly 25x faster than the equivalent PGD evaluation across multiple thresholds.

Table comparing the robust accuracy of various attacks across different norms. FAB-100 consistently achieves the best performance.

Breaking Defenses: The authors also demonstrated that FAB could break a recently proposed defense that claimed high robustness. While PGD was fooled by the defense's logit scaling, FAB bypassed this masking and reduced the model's robust accuracy to near 0%.

Limitations and Future Work

While highly effective, FAB has a few limitations:

  • Computational Cost of Jacobians: The standard FAB attack requires computing the Jacobian matrix (gradients for all classes), which is memory-intensive for datasets with many classes (like the full 1,000-class ImageNet). To mitigate this, the authors propose a "targeted" version of FAB that only looks at the top-$k$ classes for large-scale datasets.
  • White-Box Only: As a gradient-based method, FAB requires full access to the model's internals and cannot be used in "black-box" scenarios where only the final prediction is visible.

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,...
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