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