Aha! Adaptive History-driven Attack for Decision-based Black-box Models

Jie Li, Rongrong Ji, Peixian Chen, Baochang Zhang, Xiaopeng Hong, Ruixin Zhang, Shaoxin Li, Jilin Li, Feiyue Huang, Yongjian Wu

Introduction

In the field of adversarial machine learning, black-box attacks represent a critical security challenge. Unlike white-box attacks where the model's internal parameters are known, black-box attackers only have access to model outputs. The most restrictive and realistic scenario is the decision-based attack, where only the final predicted label (e.g., "Dog" vs. "Cat") is available, without confidence scores.

Traditional decision-based methods, such as the Boundary Attack, often rely on random sampling to find adversarial perturbations. This approach is notoriously inefficient, requiring thousands of queries that can be easily detected by security systems. The Adaptive History-driven Attack (AHA) addresses this by leveraging information from previous queries to guide the search process more effectively.

Methodology

AHA introduces three key innovations to improve query efficiency:

1. History-driven Direction

Instead of treating each query as an independent random event, AHA maintains a running "mean direction" ($\mu$) based on historical successes and failures. Successful directions are added to the mean, while failed directions (those that cross back into the correct classification) are subtracted. This historical prior transforms a random walk into a guided search, exploiting the observation that decision boundaries in deep networks are often locally flat.

2. Coefficient Adaptive Adjusting

Standard attacks often use the "1/5th success rule" to adjust step sizes. AHA replaces this binary feedback loop with a more granular approach. It calculates the ratio of the actual reduction in perturbation to the expected reduction. This allows the attack to adaptively accelerate when the path is clear and decelerate when approaching complex boundary regions.

3. Subspace Sampling

To mitigate the "curse of dimensionality" in high-resolution images, AHA performs its search in a lower-dimensional subspace (typically 1/16th of the original image size). The resulting noise is upscaled using bilinear interpolation, focusing the attack on low-frequency features that are more likely to influence the model's decision.

Experimental Evaluation

The researchers evaluated AHA across several benchmarks, including ImageNet (tested against VGG-16, ResNet50, and Inception-V3), CelebA (tested against CosFace and ArcFace), and CIFAR-10. They also conducted real-world tests against the commercial MEGVII Face++ API to prove practical viability.

Results and Discussion

AHA consistently outperforms state-of-the-art methods like HSJA, QEBA, and Evolutionary Attack in both perturbation magnitude and success rate.

Perturbation Efficiency

On ImageNet, AHA achieved between 24.3% and 27.6% lower $L_2$ perturbation magnitudes compared to the next best method within the same query budget. As shown in Figure 1, the AHA method reduces the $L_2$ norm faster and more significantly than competing approaches on the ResNet50 model.

L2 perturbation reduction for ResNet50

Attack Success Rate

The efficiency of AHA is particularly evident in challenging models like Inception-V3. While the Evolutionary Attack reached a 64% success rate, AHA achieved a 91% success rate within the same query limit.

ASR vs Queries for Inception-V3

Furthermore, AHA proved robust against common defenses such as JPEG compression and adversarial training. In real-world tests on the Face++ API, AHA generated adversarial faces with 24.9% smaller perturbations than baselines, making the changes significantly harder for a human to detect.

Conclusion

The AHA attack demonstrates that "failures are data." By learning from every query, AHA significantly reduces the query budget required for successful black-box attacks. Future work may explore "adaptive subspace" methods that dynamically adjust the search dimensionality to further optimize long-term performance.

Summary updated

Abstract

The decision-based black-box attack means to craft adversarial examples with only the top-1 label of the victim model available. A common practice is to start from a large perturbation and then iteratively reduce it with a deterministic direction and a random one while keeping it adversarial. The limited information obtained from each query and inefficient direction sampling impede attack efficiency, making it hard to obtain a small enough perturbation within a limited number of queries. To tackle this problem, we propose a novel attack method termed Adaptive History-driven Attack (AHA) which gathers information from all historical queries as the prior for current sampling. Moreover, to balance between the deterministic direction and the random one, we dynamically adjust the coefficient according to the ratio of the actual magnitude reduction to the expected one. Such a strategy improves the success rate of queries during optimization, letting adversarial examples move swiftly along the decision boundary. Our method can also integrate with subspace optimization like dimension reduction to further improve efficiency. Extensive experiments on both ImageNet and CelebA datasets demonstrate that our method achieves at least 24.3% lower magnitude of perturbation on average with the same number of queries. Finally, we prove the practical potential of our method by evaluating it on popular defense methods and a real-world system provided by MEGVII Face++.
BibTeX
@inproceedings{li2021aha,
  author = {Jie Li and Rongrong Ji and Peixian Chen and Baochang Zhang and Xiaopeng Hong and Ruixin Zhang and Shaoxin Li and Jilin Li and Feiyue Huang and Yongjian Wu},
  title = {{Aha! Adaptive History-driven Attack for Decision-based Black-box Models}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2021},
  doi = {10.1109/iccv48922.2021.01586},
}
Figure