# Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach

arXiv: https://arxiv.org/abs/1807.04457 · HTML: https://mlsanity.com/paper/1807.04457/

## Key facts

- Cited by 130 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2018.

## Built on by (most cited first, 30 of 130)

- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Adversarial Sticker: A Stealthy Attack Method in the Physical World](https://mlsanity.com/paper/2104.06728/) (2021)
- [A Survey of Attacks on Large Vision-Language Models: Resources, Advances, and Future Trends](https://mlsanity.com/paper/2407.07403/) (2024)
- [Gradient Cuff: Detecting Jailbreak Attacks on Large Language Models by Exploring Refusal Loss Landscapes](https://mlsanity.com/paper/2403.00867/) (2024)
- [Boosting the Transferability of Adversarial Attacks with Reverse Adversarial Perturbation](https://mlsanity.com/paper/2210.05968/) (2022)
- [Black Box Adversarial Prompting for Foundation Models](https://mlsanity.com/paper/2302.04237/) (2023)
- [Structure Invariant Transformation for better Adversarial Transferability](https://mlsanity.com/paper/2309.14700/) (2023)
- [Probabilistic Margins for Instance Reweighting in Adversarial Training](https://mlsanity.com/paper/2106.07904/) (2021)
- [Meta Gradient Adversarial Attack](https://mlsanity.com/paper/2108.04204/) (2021)
- [Adversarial Attacks On Multi-Agent Communication](https://mlsanity.com/paper/2101.06560/) (2021)
- [Triangle Attack: A Query-efficient Decision-based Adversarial Attack](https://mlsanity.com/paper/2112.06569/) (2021)
- [Adv-Attribute: Inconspicuous and Transferable Adversarial Attack on Face Recognition](https://mlsanity.com/paper/2210.06871/) (2022)
- [Robust Machine Learning Systems: Challenges, Current Trends, Perspectives, and the Road Ahead](https://mlsanity.com/paper/2101.02559/) (2021)
- [Zero-Shot Knowledge Distillation from a Decision-Based Black-Box Model](https://mlsanity.com/paper/2106.03310/) (2021)
- [A Review of Adversarial Attack and Defense for Classification Methods](https://mlsanity.com/paper/2111.09961/) (2021)
- [Generalizable Black-Box Adversarial Attack with Meta Learning](https://mlsanity.com/paper/2301.00364/) (2023)
- [On Discrete Prompt Optimization for Diffusion Models](https://mlsanity.com/paper/2407.01606/) (2024)
- [FrequencyLowCut Pooling -- Plug & Play against Catastrophic Overfitting](https://mlsanity.com/paper/2204.00491/) (2022)
- [Combating Adversaries with Anti-Adversaries](https://mlsanity.com/paper/2103.14347/) (2021)
- [Delving into Data: Effectively Substitute Training for Black-box Attack](https://mlsanity.com/paper/2104.12378/) (2021)
- [BASAR:Black-box Attack on Skeletal Action Recognition](https://mlsanity.com/paper/2103.05266/) (2021)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Black-box Adversarial Attacks on Commercial Speech Platforms with Minimal Information](https://mlsanity.com/paper/2110.09714/) (2021)
- [Adversarial Robustness against Multiple and Single lp-Threat Models via Quick Fine-Tuning of Robust Classifiers](https://mlsanity.com/paper/2105.12508/) (2021)
- [QAIR: Practical Query-efficient Black-Box Attacks for Image Retrieval](https://mlsanity.com/paper/2103.02927/) (2021)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [TextGrad: Advancing Robustness Evaluation in NLP by Gradient-Driven Optimization](https://mlsanity.com/paper/2212.09254/) (2022)
- [CGBA: Curvature-aware Geometric Black-box Attack](https://mlsanity.com/paper/2308.03163/) (2023)
- [StyleFool: Fooling Video Classification Systems via Style Transfer](https://mlsanity.com/paper/2203.16000/) (2022)
- [Attacks in Adversarial Machine Learning: A Systematic Survey from the Life-cycle Perspective](https://mlsanity.com/paper/2302.09457/) (2023)

## Abstract (arXiv)

We study the problem of attacking a machine learning model in the hard-label black-box setting, where no model information is revealed except that the attacker can make queries to probe the corresponding hard-label decisions. This is a very challenging problem since the direct extension of state-of-the-art white-box attacks (e.g., CW or PGD) to the hard-label black-box setting will require minimizing a non-continuous step function, which is combinatorial and cannot be solved by a gradient-based optimizer. The only current approach is based on random walk on the boundary, which requires lots of queries and lacks convergence guarantees. We propose a novel way to formulate the hard-label black-box attack as a real-valued optimization problem which is usually continuous and can be solved by any zeroth order optimization algorithm. For example, using the Randomized Gradient-Free method, we are able to bound the number of iterations needed for our algorithm to achieve stationary points. We demonstrate that our proposed method outperforms the previous random walk approach to attacking convolutional neural networks on MNIST, CIFAR, and ImageNet datasets. More interestingly, we show that the proposed algorithm can also be used to attack other discrete and non-continuous machine learning models, such as Gradient Boosting Decision Trees (GBDT).