# Query Efficient Decision Based Sparse Attacks Against Black-Box Deep Learning Models

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 42 references that are in the map.
- First posted on arXiv 31 Jan 2022.

## Builds on (most cited first, 30 of 35)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Stand-Alone Self-Attention in Vision Models](https://mlsanity.com/paper/1906.05909/) (2019)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models](https://mlsanity.com/paper/1712.04248/) (2017)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [On the Relationship between Self-Attention and Convolutional Layers](https://mlsanity.com/paper/1911.03584/) (2019)
- [Simple Black-box Adversarial Attacks](https://mlsanity.com/paper/1905.07121/) (2019)
- [Understanding Robustness of Transformers for Image Classification](https://mlsanity.com/paper/2103.14586/) (2021)
- [DeepDriving: Learning Affordance for Direct Perception in Autonomous Driving](https://mlsanity.com/paper/1505.00256/) (2015)
- [Efficient Decision-based Black-box Adversarial Attacks on Face Recognition](https://mlsanity.com/paper/1904.04433/) (2019)
- [Sign-OPT: A Query-Efficient Hard-label Adversarial Attack](https://mlsanity.com/paper/1909.10773/) (2019)
- [Towards the first adversarially robust neural network model on MNIST](https://mlsanity.com/paper/1805.09190/) (2018)
- [QEBA: Query-Efficient Boundary-Based Blackbox Attack](https://mlsanity.com/paper/2005.14137/) (2020)
- [RayS: A Ray Searching Method for Hard-label Adversarial Attack](https://mlsanity.com/paper/2006.12792/) (2020)
- [Sparse and Imperceivable Adversarial Attacks](https://mlsanity.com/paper/1909.05040/) (2019)
- [SparseFool: a few pixels make a big difference](https://mlsanity.com/paper/1811.02248/) (2018)
- [GenAttack: Practical Black-box Attacks with Gradient-Free Optimization](https://mlsanity.com/paper/1805.11090/) (2018)
- [Structured Adversarial Attack: Towards General Implementation and Better Interpretability](https://mlsanity.com/paper/1808.01664/) (2018)
- [GreedyFool: Distortion-Aware Sparse Adversarial Attack](https://mlsanity.com/paper/2010.13773/) (2020)
- [Hybrid Batch Attacks: Finding Black-box Adversarial Examples with Limited Queries](https://mlsanity.com/paper/1908.07000/) (2019)

## Built on by (most cited first, 13 of 13)

- [Universal Adversarial Examples in Remote Sensing: Methodology and Benchmark](https://mlsanity.com/paper/2202.07054/) (2022)
- [Efficient Decision-based Black-box Patch Attacks on Video Recognition](https://mlsanity.com/paper/2303.11917/) (2023)
- [Speech Robust Bench: A Robustness Benchmark For Speech Recognition](https://mlsanity.com/paper/2403.07937/) (2024)
- [Query-Efficient Decision-based Black-Box Patch Attack](https://mlsanity.com/paper/2307.00477/) (2023)
- [BruSLeAttack: A Query-Efficient Score-Based Black-Box Sparse Adversarial Attack](https://mlsanity.com/paper/2404.05311/) (2024)
- [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)
- [Bayesian Learning with Information Gain Provably Bounds Risk for a Robust Adversarial Defense](https://mlsanity.com/paper/2212.02003/) (2022)
- [MalPurifier: Enhancing Android Malware Detection with Adversarial Purification against Evasion Attacks](https://mlsanity.com/paper/2312.06423/) (2023)
- [On the Adversarial Vulnerabilities of Transfer Learning in Remote Sensing](https://mlsanity.com/paper/2501.11462/) (2025)
- [Random Logit Scaling: Defending Deep Neural Networks Against Black-Box Score-Based Adversarial Example Attacks](https://mlsanity.com/paper/2607.14921/) (2026)
- [Decision-BADGE: Decision-based Adversarial Batch Attack with Directional Gradient Estimation](https://mlsanity.com/paper/2303.04980/) (2023)
- [SegPAR: Class-Centric Decision-Based Sparse Attack for Semantic Segmentation](https://mlsanity.com/paper/2608.11285/) (2026)

## Abstract (arXiv)

Despite our best efforts, deep learning models remain highly vulnerable to even tiny adversarial perturbations applied to the inputs. The ability to extract information from solely the output of a machine learning model to craft adversarial perturbations to black-box models is a practical threat against real-world systems, such as autonomous cars or machine learning models exposed as a service (MLaaS). Of particular interest are sparse attacks. The realization of sparse attacks in black-box models demonstrates that machine learning models are more vulnerable than we believe. Because these attacks aim to minimize the number of perturbed pixels measured by l_0 norm-required to mislead a model by solely observing the decision (the predicted label) returned to a model query; the so-called decision-based attack setting. But, such an attack leads to an NP-hard optimization problem. We develop an evolution-based algorithm-SparseEvo-for the problem and evaluate against both convolutional deep neural networks and vision transformers. Notably, vision transformers are yet to be investigated under a decision-based attack setting. SparseEvo requires significantly fewer model queries than the state-of-the-art sparse attack Pointwise for both untargeted and targeted attacks. The attack algorithm, although conceptually simple, is also competitive with only a limited query budget against the state-of-the-art gradient-based whitebox attacks in standard computer vision tasks such as ImageNet. Importantly, the query efficient SparseEvo, along with decision-based attacks, in general, raise new questions regarding the safety of deployed systems and poses new directions to study and understand the robustness of machine learning models.