When does gradient estimation improve black-box adversarial attacks?

Enoal Gesny, Eva Giboulot, Teddy FuronWIFS 2024 · DOI

This paper delves into the effectiveness of gradient estimation in black-box adversarial attacks, a crucial area for understanding and defending against malicious manipulations of machine learning models. The authors provide a theoretical framework to determine when and why gradient estimation truly benefits these attacks, offering a more nuanced understanding beyond empirical observations.

TL;DR

This paper theoretically analyzes when gradient estimation improves black-box adversarial attacks, like SurFree. It reveals that gradient estimation is beneficial only when the query budget for estimation is sufficiently large compared to the search overhead, offering a clear condition for its effectiveness and providing a method to optimize query allocation.

What Problem Does This Paper Address?

Adversarial attacks aim to subtly alter input data (like images) so that a machine learning model misclassifies them. Black-box attacks are particularly challenging because the attacker has limited knowledge of the target model, often only being able to query it and observe its output class. Existing methods like SurFree achieve good results by cleverly searching for adversarial examples without using gradient information. However, more recent approaches like CGBA attempt to reintroduce gradient estimation, claiming improved performance. The core problem this paper addresses is to theoretically understand when this gradient estimation actually provides a significant advantage over gradient-free methods, and under what conditions it might be a waste of valuable queries.

Methods

The paper introduces a theoretical framework to analyze the performance of two black-box attack strategies: SurFree (gradient-free) and CGBA (which incorporates gradient estimation).

  • SurFree Analysis: The authors analyze SurFree's iterative process, which involves restricting the search for adversarial examples to random 2D planes. They derive expressions for the distortion of adversarial examples at each iteration and the convergence rate.
  • Gradient Estimation: For CGBA, the paper focuses on how gradient estimation is used to approximate the normal vector to the classifier's decision boundary. They analyze the quality of this estimation based on the number of queries used.
  • Theoretical Comparison: The core contribution lies in deriving conditions under which CGBA's gradient estimation leads to a faster convergence rate (i.e., lower distortion with fewer queries) compared to SurFree. This involves comparing their expected distortion rates.
  • Optimal Query Allocation: A key outcome is the derivation of an optimal query allocation strategy for CGBA, specifically determining the minimum number of queries needed for gradient estimation to outperform SurFree, given a fixed search overhead.

Datasets

The paper uses the following datasets for evaluation:

  • MNIST: A subset of 100 correctly classified images from the test set, using a pre-trained CNN with two linear layers to align with theoretical assumptions.
  • ImageNet: A subset of 100 correctly classified images from the 2012 validation set, using a pre-trained ResNet18. For ImageNet, the attacks are performed in the DCT domain, focusing on the 50% lowest frequencies per 8x8 block, a common practice for large-dimensional spaces.

Key Insights and Ideas

  • Gradient Estimation is Not Always Better: The most significant insight is that gradient estimation is not universally beneficial. It only provides an advantage when the number of queries dedicated to estimation is sufficiently large relative to the overhead of the search process.
  • The Query Budget is Key: The paper quantifies this relationship, showing that if the estimation query budget is too small, the attacker might be better off relying solely on SurFree's gradient-free approach.
  • Optimizing for Efficiency: The authors provide a formula to calculate the optimal number of queries for gradient estimation to ensure CGBA outperforms SurFree, offering a practical guideline for designing more efficient black-box attacks.
  • Theoretical Guarantees: The paper moves beyond empirical results by providing theoretical expressions for distortion rates and convergence, offering a deeper understanding of the underlying mechanisms.
  • Hyperplane Assumption Robustness: While the theoretical analysis relies on the decision boundary being a hyperplane, the experimental results suggest that this approximation holds reasonably well even for non-linear classifiers like those used with ImageNet.

Key Results

  • CGBA Outperforms SurFree Under Optimal Conditions: When the number of estimation queries (Q) is sufficiently large compared to the search overhead (k), CGBA consistently achieves lower distortion than SurFree for the same number of total queries.
  • Optimal Q Formula: Proposition 6 provides a formula for the optimal Q*(k) that balances estimation and search costs for CGBA to be more efficient than SurFree.
  • Experimental Validation: Simulations and experiments on MNIST and ImageNet confirm the theoretical findings, showing CGBA's faster convergence and lower distortion under favorable query budget conditions. For instance, on ImageNet, CGBA with a constant Q=5 outperforms SurFree by a significant margin (6-15%) for low target distortions.
  • Impact of Query Allocation: While the theoretical analysis suggests that the specific allocation schedule (constant, increasing, or decreasing Q) has less impact on the final distortion for hyperplane-like boundaries, experiments show that an increasing schedule can lead to slightly lower distortion in some cases.

Limitations and Future Work

  • Hyperplane Assumption: The theoretical analysis relies on the assumption that the classifier's decision boundary is a hyperplane. While experiments show some robustness, this assumption might limit the applicability of the theoretical guarantees to more complex, non-linear boundaries.
  • Query Budget Constraints: The paper focuses on optimizing the query budget for gradient estimation. However, real-world scenarios might have even stricter query limits, which could further challenge the effectiveness of gradient-based methods.
  • Future Work: The authors suggest exploring the impact of the query allocation schedule more deeply, especially for non-linear classifiers. Further research could also investigate how to adapt these findings to other types of black-box attacks or different model architectures.

Summary updated

BibTeX
@inproceedings{gesny2024when,
  author = {Enoal Gesny and Eva Giboulot and Teddy Furon},
  title = {{When does gradient estimation improve black-box adversarial attacks?}},
  booktitle = {WIFS},
  year = {2024},
  doi = {10.1109/wifs61860.2024.10810691},
}
Figure