# Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2020.

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

- [Jailbreaking Leading Safety-Aligned LLMs with Simple Adaptive Attacks](https://mlsanity.com/paper/2404.02151/) (2024)
- [On Guaranteed Optimal Robust Explanations for NLP Models](https://mlsanity.com/paper/2105.03640/) (2021)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Make Them Spill the Beans! Coercive Knowledge Extraction from (Production) LLMs](https://mlsanity.com/paper/2312.04782/) (2023)
- [Efficient Certified Defenses Against Patch Attacks on Image Classifiers](https://mlsanity.com/paper/2102.04154/) (2021)
- [ML Attack Models: Adversarial Attacks and Data Poisoning Attacks](https://mlsanity.com/paper/2112.02797/) (2021)
- [Adversarial Robustness against Multiple and Single lp-Threat Models via Quick Fine-Tuning of Robust Classifiers](https://mlsanity.com/paper/2105.12508/) (2021)
- [Give Me Your Attention: Dot-Product Attention Considered Harmful for Adversarial Patch Robustness](https://mlsanity.com/paper/2203.13639/) (2022)
- [Efficient Decision-based Black-box Patch Attacks on Video Recognition](https://mlsanity.com/paper/2303.11917/) (2023)
- [Transferable Adversarial Attacks on SAM and Its Downstream Models](https://mlsanity.com/paper/2410.20197/) (2024)
- [Meta Adversarial Training against Universal Patches](https://mlsanity.com/paper/2101.11453/) (2021)
- [Query-Efficient Decision-based Black-Box Patch Attack](https://mlsanity.com/paper/2307.00477/) (2023)
- [A Survey of Robustness and Safety of 2D and 3D Deep Learning Models Against Adversarial Attacks](https://mlsanity.com/paper/2310.00633/) (2023)
- [Adversarial Patch Attacks and Defences in Vision-Based Tasks: A Survey](https://mlsanity.com/paper/2206.08304/) (2022)
- [Scattering Model Guided Adversarial Examples for SAR Target Recognition: Attack and Defense](https://mlsanity.com/paper/2209.04779/) (2022)
- [EvadeDroid: A Practical Evasion Attack on Machine Learning for Black-box Android Malware Detection](https://mlsanity.com/paper/2110.03301/) (2021)
- [Towards Reliable Evaluation and Fast Training of Robust Semantic Segmentation Models](https://mlsanity.com/paper/2306.12941/) (2023)
- [Cross-Modality Attack Boosted by Gradient-Evolutionary Multiform Optimization](https://mlsanity.com/paper/2409.17977/) (2024)
- [Adversarial Token Attacks on Vision Transformers](https://mlsanity.com/paper/2110.04337/) (2021)
- [Transferable Sparse Adversarial Attack](https://mlsanity.com/paper/2105.14727/) (2021)
- [Towards Effective and Sparse Adversarial Attack on Spiking Neural Networks via Breaking Invisible Surrogate Gradients](https://mlsanity.com/paper/2503.03272/) (2025)
- [BruSLeAttack: A Query-Efficient Score-Based Black-Box Sparse Adversarial Attack](https://mlsanity.com/paper/2404.05311/) (2024)
- [Meta-Learning the Search Distribution of Black-Box Random Search Based Adversarial Attacks](https://mlsanity.com/paper/2111.01714/) (2021)
- [LogoStyleFool: Vitiating Video Recognition Systems via Logo Style Transfer](https://mlsanity.com/paper/2312.09935/) (2023)
- [σ-zero: Gradient-based Optimization of ℓ0-norm Adversarial Examples](https://mlsanity.com/paper/2402.01879/) (2024)
- [SoK: Pitfalls in Evaluating Black-Box Attacks](https://mlsanity.com/paper/2310.17534/) (2023)
- [GSE: Group-wise Sparse and Explainable Adversarial Attacks](https://mlsanity.com/paper/2311.17434/) (2023)
- [Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model](https://mlsanity.com/paper/2104.02189/) (2021)
- [Adversarial Scratches: Deployable Attacks to CNN Classifiers](https://mlsanity.com/paper/2204.09397/) (2022)
- [Patch of Invisibility: Naturalistic Physical Black-Box Adversarial Attacks on Object Detectors](https://mlsanity.com/paper/2303.04238/) (2023)

## Abstract (arXiv)

We propose a versatile framework based on random search, Sparse-RS, for score-based sparse targeted and untargeted attacks in the black-box setting. Sparse-RS does not rely on substitute models and achieves state-of-the-art success rate and query efficiency for multiple sparse attack models: l0-bounded perturbations, adversarial patches, and adversarial frames. The l0-version of untargeted Sparse-RS outperforms all black-box and even all white-box attacks for different models on MNIST, CIFAR-10, and ImageNet. Moreover, our untargeted Sparse-RS achieves very high success rates even for the challenging settings of 20×20 adversarial patches and 2-pixel wide adversarial frames for 224×224 images. Finally, we show that Sparse-RS can be applied to generate targeted universal adversarial patches where it significantly outperforms the existing approaches. The code of our framework is available at https://github.com/fra31/sparse-rs.