Automated Discovery of Adaptive Attacks on Adversarial Defenses

Chengyuan Yao, Pavol Bielik, Petar Tsankov, Martin T. Vechev

Introduction

Evaluating the robustness of AI models against adversarial examples is a persistent challenge. Traditionally, this process involves a "cat-and-mouse" game where human experts manually design custom attacks to bypass specific defenses. While effective, this manual approach is slow, expensive, and limited by human creativity. This paper introduces Adaptive AutoAttack ($A^3$), a framework that automates the discovery of effective "adaptive" attacks by formalizing expert techniques into a searchable grammar.

Comparison of attack methodologies: (a) manual handcrafted attacks, (b) fixed ensemble attacks, and (c) the proposed automated adaptive attack search.

The Challenge of Evaluating Robustness

Adversarial defenses aim to make neural networks resistant to maliciously perturbed inputs. However, a defense that appears robust against standard, "fixed" attacks often crumbles when faced with an adaptive attack specifically tailored to exploit its unique inner workings. Current evaluation methods generally fall into two categories:

  1. Manual Expert Analysis: Highly effective but slow and limited by the expert's intuition.
  2. Fixed Ensembles (e.g., AutoAttack): Automated and fast, but often fail against defenses using non-standard components like randomization or non-differentiable layers because the attacks are not tailored to the specific defense mechanism.

$A^3$ bridges this gap by automating the "expert" process of tailoring an attack to a specific model.

Adaptive AutoAttack ($A^3$)

The core contribution of $A^3$ is the formalization of an Attack Search Space and an efficient algorithm to navigate it.

The Search Space

Adaptive attacks are decomposed into three reusable building blocks:

  • Attack Algorithms & Parameters: A library of backbone attacks (e.g., PGD, APGD, FAB) with tunable hyperparameters such as steps and step size.
  • Network Transformations: Techniques to create "surrogate" models that are easier to attack. This includes BPDA (Backward Pass Differentiable Approximation) for handling non-differentiable layers and Layer Removal to strip away obfuscation layers like redundant softmax or JPEG compression.
  • Loss Functions: A grammar for defining success metrics, including targeted vs. untargeted losses operating on logits or probabilities.

The Search Algorithm

To efficiently navigate this vast space without exhaustive search, $A^3$ employs:

  • Greedy Search: Sequentially builds a sequence of attacks, focusing on samples that remain unbroken by previous attempts.
  • Tree of Parzen Estimators (TPE): A Bayesian optimization approach to tune attack hyperparameters.
  • Successive Halving (SHA): A strategy to quickly discard ineffective attack candidates by testing them on small data subsets before full evaluation.

Experimental Results

The researchers evaluated $A^3$ on 24 adversarial defenses for the CIFAR-10 dataset, categorized by perturbation budgets and defense types (Blocks A, B, and C).

Performance of $A^3$ compared to AutoAttack (AA) across 24 defenses. $A^3$ often finds lower robust accuracy (higher attack success) and offers significant speed-ups.

Key Findings

  • Superior Attack Strength: $A^3$ outperformed the state-of-the-art AutoAttack on 10 out of 24 models. In these instances, it discovered 3.0% to 50.8% more adversarial examples, proving these models were significantly less robust than previously believed.
  • Improved Efficiency: For the 14 models where it did not find stronger attacks, $A^3$ was typically 2x faster than AutoAttack, as it could quickly identify the most effective strategy and terminate the search.
  • Breaking "Unbreakable" Defenses: $A^3$ successfully re-discovered (and sometimes improved) manual attacks for complex defenses like JPEG compression and "Reverse Sigmoid," which previously required weeks of human effort to develop.

Conclusion

By modularizing the components of adaptive attacks, $A^3$ transforms the creative process of attack design into a systematic optimization problem. While limited by the predefined building blocks in its library, $A^3$ represents a significant step toward more reliable and automated robustness evaluation. Future work may involve meta-learning to further accelerate the search process by leveraging experience from previous evaluations of similar models.

Summary updated

Abstract

Reliable evaluation of adversarial defenses is a challenging task, currently limited to an expert who manually crafts attacks that exploit the defense’s inner workings, or to approaches based on ensemble of fixed attacks, none of which may be effective for the specific defense at hand. Our key observation is that adaptive attacks are composed from a set of reusable building blocks that can be formalized in a search space and used to automatically discover attacks for unknown defenses. We evaluated our approach on 24 adversarial defenses and show that it outperforms AutoAttack, the current state-of-the-art tool for reliable evaluation of adversarial defenses: our tool discovered significantly stronger attacks by producing 3.0%-50.8% additional adversarial examples for 10 models, while obtaining attacks with slightly stronger or similar strength for the remaining models.
BibTeX
@inproceedings{yao2021automated,
  author = {Chengyuan Yao and Pavol Bielik and Petar Tsankov and Martin T. Vechev},
  title = {{Automated Discovery of Adaptive Attacks on Adversarial Defenses}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=y5RkbSryJ2},
}
Figure