# Parsimonious Black-Box Adversarial Attacks via Efficient Combinatorial Optimization

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2019.

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

- [Black Box Adversarial Prompting for Foundation Models](https://mlsanity.com/paper/2302.04237/) (2023)
- [Random Noise Defense Against Query-Based Black-Box Attacks](https://mlsanity.com/paper/2104.11470/) (2021)
- [AdvRush: Searching for Adversarially Robust Neural Architectures](https://mlsanity.com/paper/2108.01289/) (2021)
- [ML Attack Models: Adversarial Attacks and Data Poisoning Attacks](https://mlsanity.com/paper/2112.02797/) (2021)
- [Attacks in Adversarial Machine Learning: A Systematic Survey from the Life-cycle Perspective](https://mlsanity.com/paper/2302.09457/) (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)
- [Efficient Combinatorial Optimization for Word-level Adversarial Textual Attack](https://mlsanity.com/paper/2109.02229/) (2021)
- [Saliency Attack: Towards Imperceptible Black-box Adversarial Attack](https://mlsanity.com/paper/2206.01898/) (2022)
- [Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks](https://mlsanity.com/paper/2111.07492/) (2021)
- [Stateful Defenses for Machine Learning Models Are Not Yet Secure Against Black-box Attacks](https://mlsanity.com/paper/2303.06280/) (2023)
- [DI-AA: An Interpretable White-box Attack for Fooling Deep Neural Networks](https://mlsanity.com/paper/2110.07305/) (2021)
- [On the Role of Generalization in Transferability of Adversarial Examples](https://mlsanity.com/paper/2206.09238/) (2022)
- [Machine Learning Robustness: A Primer](https://mlsanity.com/paper/2404.00897/) (2024)
- [ADBA:Approximation Decision Boundary Approach for Black-Box Adversarial Attacks](https://mlsanity.com/paper/2406.04998/) (2024)
- [Adversarial Robustness by Design through Analog Computing and Synthetic Gradients](https://mlsanity.com/paper/2101.02115/) (2021)
- [Meta-Learning the Search Distribution of Black-Box Random Search Based Adversarial Attacks](https://mlsanity.com/paper/2111.01714/) (2021)
- [Learnability Lock: Authorized Learnability Control Through Adversarial Invertible Transformations](https://mlsanity.com/paper/2202.03576/) (2022)
- [SpecRepair: Counter-Example Guided Safety Repair of Deep Neural Networks](https://mlsanity.com/paper/2106.01917/) (2021)
- [Threshold-adaptive Unsupervised Focal Loss for Domain Adaptation of Semantic Segmentation](https://mlsanity.com/paper/2208.10716/) (2022)
- [SoK: Pitfalls in Evaluating Black-Box Attacks](https://mlsanity.com/paper/2310.17534/) (2023)
- [Adversarial Scratches: Deployable Attacks to CNN Classifiers](https://mlsanity.com/paper/2204.09397/) (2022)
- [Certifiable Black-Box Attacks with Randomized Adversarial Examples: Breaking Defenses with Provable Confidence](https://mlsanity.com/paper/2304.04343/) (2023)
- [Guardians of Image Quality: Benchmarking Defenses Against Adversarial Attacks on Image Quality Metrics](https://mlsanity.com/paper/2408.01541/) (2024)
- [TRAP: Targeted Redirecting of Agentic Preferences](https://mlsanity.com/paper/2505.23518/) (2025)
- [EvoBA: An Evolution Strategy as a Strong Baseline forBlack-Box Adversarial Attacks](https://mlsanity.com/paper/2107.05754/) (2021)
- [Audit and Improve Robustness of Private Neural Networks on Encrypted Data](https://mlsanity.com/paper/2209.09996/) (2022)
- [Sparse-PGD: A Unified Framework for Sparse Adversarial Perturbations Generation](https://mlsanity.com/paper/2405.05075/) (2024)
- [Publishing Efficient On-device Models Increases Adversarial Vulnerability](https://mlsanity.com/paper/2212.13700/) (2022)
- [BadPart: Unified Black-box Adversarial Patch Attacks against Pixel-wise Regression Tasks](https://mlsanity.com/paper/2404.00924/) (2024)

## Abstract (arXiv)

Solving for adversarial examples with projected gradient descent has been demonstrated to be highly effective in fooling the neural network based classifiers. However, in the black-box setting, the attacker is limited only to the query access to the network and solving for a successful adversarial example becomes much more difficult. To this end, recent methods aim at estimating the true gradient signal based on the input queries but at the cost of excessive queries. We propose an efficient discrete surrogate to the optimization problem which does not require estimating the gradient and consequently becomes free of the first order update hyperparameters to tune. Our experiments on Cifar-10 and ImageNet show the state of the art black-box attack performance with significant reduction in the required queries compared to a number of recently proposed methods. The source code is available at https://github.com/snu-mllab/parsimonious-blackbox-attack.