# Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attacks

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2018.

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

- [Improving Robustness using Generated Data](https://mlsanity.com/paper/2110.09468/) (2021)
- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Adversarial Attacks On Multi-Agent Communication](https://mlsanity.com/paper/2101.06560/) (2021)
- [Query-Efficient Black-box Adversarial Attacks Guided by a Transfer-based Prior](https://mlsanity.com/paper/2203.06560/) (2022)
- [A Review of Adversarial Attack and Defense for Classification Methods](https://mlsanity.com/paper/2111.09961/) (2021)
- [On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms](https://mlsanity.com/paper/2107.10110/) (2021)
- [QAIR: Practical Query-efficient Black-Box Attacks for Image Retrieval](https://mlsanity.com/paper/2103.02927/) (2021)
- [CGBA: Curvature-aware Geometric Black-box Attack](https://mlsanity.com/paper/2308.03163/) (2023)
- [Physical Adversarial Attacks For Camera-based Smart Systems: Current Trends, Categorization, Applications, Research Challenges, and Future Outlook](https://mlsanity.com/paper/2308.06173/) (2023)
- [A Survey of Robustness and Safety of 2D and 3D Deep Learning Models Against Adversarial Attacks](https://mlsanity.com/paper/2310.00633/) (2023)
- [Attacking deep networks with surrogate-based adversarial black-box methods is easy](https://mlsanity.com/paper/2203.08725/) (2022)
- [Decision-based Black-box Attack Against Vision Transformers via Patch-wise Adversarial Removal](https://mlsanity.com/paper/2112.03492/) (2021)
- [Attack as the Best Defense: Nullifying Image-to-image Translation GANs via Limit-aware Adversarial Attack](https://mlsanity.com/paper/2110.02516/) (2021)
- [Evading Black-box Classifiers Without Breaking Eggs](https://mlsanity.com/paper/2306.02895/) (2023)
- [Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks](https://mlsanity.com/paper/2111.07492/) (2021)
- [RamBoAttack: A Robust Query Efficient Deep Neural Network Decision Exploit](https://mlsanity.com/paper/2112.05282/) (2021)
- [Hard-label based Small Query Black-box Adversarial Attack](https://mlsanity.com/paper/2403.06014/) (2024)
- [Black-box Adversarial Attacks in Autonomous Vehicle Technology](https://mlsanity.com/paper/2101.06092/) (2021)
- [3DHacker: Spectrum-based Decision Boundary Generation for Hard-label 3D Point Cloud Attack](https://mlsanity.com/paper/2308.07546/) (2023)
- [Threatening Patch Attacks on Object Detection in Optical Remote Sensing Images](https://mlsanity.com/paper/2302.06060/) (2023)
- [BruSLeAttack: A Query-Efficient Score-Based Black-Box Sparse Adversarial Attack](https://mlsanity.com/paper/2404.05311/) (2024)
- [ADBA:Approximation Decision Boundary Approach for Black-Box Adversarial Attacks](https://mlsanity.com/paper/2406.04998/) (2024)
- [Black-box Optimization of LLM Outputs by Asking for Directions](https://mlsanity.com/paper/2510.16794/) (2025)
- [SoK: Pitfalls in Evaluating Black-Box Attacks](https://mlsanity.com/paper/2310.17534/) (2023)
- [Certifiable Black-Box Attacks with Randomized Adversarial Examples: Breaking Defenses with Provable Confidence](https://mlsanity.com/paper/2304.04343/) (2023)
- [The Adaptive Arms Race: Redefining Robustness in AI Security](https://mlsanity.com/paper/2312.13435/) (2023)
- [Universal Distributional Decision-based Black-box Adversarial Attack with Reinforcement Learning](https://mlsanity.com/paper/2211.08384/) (2022)
- [OMG-ATTACK: Self-Supervised On-Manifold Generation of Transferable Evasion Attacks](https://mlsanity.com/paper/2310.03707/) (2023)
- [NoPain: No-box Point Cloud Attack via Optimal Transport Singular Boundary](https://mlsanity.com/paper/2503.00063/) (2025)
- [GSBAK: top-K Geometric Score-based Black-box Attack](https://mlsanity.com/paper/2503.12827/) (2025)

## Abstract (arXiv)

We consider adversarial examples for image classification in the black-box decision-based setting. Here, an attacker cannot access confidence scores, but only the final label. Most attacks for this scenario are either unreliable or inefficient. Focusing on the latter, we show that a specific class of attacks, Boundary Attacks, can be reinterpreted as a biased sampling framework that gains efficiency from domain knowledge. We identify three such biases, image frequency, regional masks and surrogate gradients, and evaluate their performance against an ImageNet classifier. We show that the combination of these biases outperforms the state of the art by a wide margin. We also showcase an efficient way to attack the Google Cloud Vision API, where we craft convincing perturbations with just a few hundred queries. Finally, the methods we propose have also been found to work very well against strong defenses: Our targeted attack won second place in the NeurIPS 2018 Adversarial Vision Challenge.