ADBA:Approximation Decision Boundary Approach for Black-Box Adversarial Attacks

Feiyang Wang, Xingquan Zuo, Hai Huang, Gang ChenarXiv 2024 · DOI · arXiv

Introduction

Adversarial attacks—tiny, intentional perturbations that fool machine learning models—pose a significant security threat. In real-world "black-box" scenarios, attackers often only have access to a model's final hard-label output (e.g., "Cat" or "Dog") rather than internal gradients or probability scores. Current decision-based attacks typically rely on random search and query-intensive techniques like binary search to find the exact distance to a decision boundary. This process is highly inefficient, often exhausting query budgets before a successful perturbation is found.

The Approximation Decision Boundary Approach (ADBA) addresses this by ditching the requirement for precise boundary calculations. By utilizing a statistical median-search strategy (ADBA-md), the algorithm can compare perturbation directions in significantly fewer queries, achieving higher success rates with 30-50% fewer queries than current state-of-the-art methods.

Methodology: Approximating the Boundary

ADBA shifts the focus from calculating the exact boundary to approximating it just enough to make a directional decision.

  1. Approximation Decision Boundary (ADB): Instead of high-precision calculations (e.g., 0.001), ADBA uses a rough estimate. If direction A is adversarial at this estimate and direction B is not, the algorithm immediately identifies A as the superior direction without further queries.
  2. ADBA-md (Median-Search): By analyzing the probability distribution of decision boundaries across various models, the authors discovered that using the median value of this distribution as the approximation point maximizes the likelihood of differentiating two directions. This provides the most "bits" of information per query.
  3. Query Efficiency: While standard binary search might require ~10 queries for accuracy, the ADBA-md approach requires only 4 queries on average to determine which of two directions is superior.

Experimental Results

The researchers evaluated ADBA against leading attacks (OPT, SignOPT, HSJA, and RayS) using ImageNet, MNIST, and CIFAR-10 datasets across six diverse architectures: VGG19, ResNet50, Inception-V3, ViT-B32, DenseNet161, and EfficientNet-B0.

Attack success rate vs. query count for various model architectures. ADBA and ADBA-md show significantly faster convergence and higher success rates in low-query regimes compared to baseline methods.

As shown in the performance curves above, ADBA variants maintain a ~90% success rate even with a tight budget of 1,000 queries, while competing methods often drop below 30%. Across all ImageNet models, ADBA-md achieved a success rate of over 99.3% within a 10,000-query budget.

Quantitative comparison of attack performance across models. ADBA-md consistently requires the fewest average and median queries (shown in parentheses) to achieve high success rates.

On the VGG19 model, ADBA-md required an average of 197.6 queries, compared to 470.1 for the previous state-of-the-art, RayS. Overall, ADBA-md reduced the average query count by 30-40% and the median query count by approximately 50% across the board.

Key Insights

  • Precision vs. Progress: In the early stages of an attack, exact boundary knowledge is unnecessary. ADBA treats the boundary as a stochastic variable, prioritizing directional progress over measurement precision.
  • Architecture Agnosticism: Surprisingly, the statistical distribution of decision boundaries is remarkably consistent across different neural network architectures, from CNNs to Vision Transformers. This allows the "median" discovered on one model to work effectively on others without recalibration.

Conclusion and Future Work

ADBA demonstrates that statistical approximation can drastically improve the efficiency of black-box adversarial attacks. While this study focused on $l_\infty$ norm constraints and untargeted attacks, future research may explore how these statistical distributions behave under different distance metrics (like $l_2$ norms) and how the logic applies to targeted attacks. Additionally, as attacks become more query-efficient, defensive strategies may need to evolve to detect the specific statistical patterns associated with median-search queries.

Summary updated

Abstract

Many machine learning models are susceptible to adversarial attacks, with decision-based black-box attacks representing the most critical threat in real-world applications. These attacks are extremely stealthy, generating adversarial examples using hard labels obtained from the target machine learning model. This is typically realized by optimizing perturbation directions, guided by decision boundaries identified through query-intensive exact search, significantly limiting the attack success rate. This paper introduces a novel approach using the Approximation Decision Boundary (ADB) to efficiently and accurately compare perturbation directions without precisely determining decision boundaries. The effectiveness of our ADB approach (ADBA) hinges on promptly identifying suitable ADB, ensuring reliable differentiation of all perturbation directions. For this purpose, we analyze the probability distribution of decision boundaries, confirming that using the distribution's median value as ADB can effectively distinguish different perturbation directions, giving rise to the development of the ADBA-md algorithm. ADBA-md only requires four queries on average to differentiate any pair of perturbation directions, which is highly query-efficient. Extensive experiments on six well-known image classifiers clearly demonstrate the superiority of ADBA and ADBA-md over multiple state-of-the-art black-box attacks. The source code is available at https://github.com/BUPTAIOC/ADBA.
BibTeX
@misc{wang2024adba,
  author = {Feiyang Wang and Xingquan Zuo and Hai Huang and Gang Chen},
  title = {{ADBA:Approximation Decision Boundary Approach for Black-Box Adversarial Attacks}},
  year = {2024},
  eprint = {2406.04998},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.04998},
}
Figure