# Projection & Probability-Driven Black-Box Attack

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2020.

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

- [Frequency Domain Model Augmentation for Adversarial Attack](https://mlsanity.com/paper/2207.05382/) (2022)
- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Probabilistic Margins for Instance Reweighting in Adversarial Training](https://mlsanity.com/paper/2106.07904/) (2021)
- [Adv-Attribute: Inconspicuous and Transferable Adversarial Attack on Face Recognition](https://mlsanity.com/paper/2210.06871/) (2022)
- [Attacks in Adversarial Machine Learning: A Systematic Survey from the Life-cycle Perspective](https://mlsanity.com/paper/2302.09457/) (2023)
- [Back in Black: A Comparative Evaluation of Recent State-Of-The-Art Black-Box Attacks](https://mlsanity.com/paper/2109.15031/) (2021)
- [Learning to Learn Transferable Attack](https://mlsanity.com/paper/2112.06658/) (2021)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Prior](https://mlsanity.com/paper/2405.19098/) (2024)
- [A Simple and Strong Baseline for Universal Targeted Attacks on Siamese Visual Tracking](https://mlsanity.com/paper/2105.02480/) (2021)
- [Progressive-Scale Boundary Blackbox Attack via Projective Gradient Estimation](https://mlsanity.com/paper/2106.06056/) (2021)
- [Rethinking Image-Scaling Attacks: The Interplay Between Vulnerabilities in Machine Learning Systems](https://mlsanity.com/paper/2104.08690/) (2021)
- [SoK: Pitfalls in Evaluating Black-Box Attacks](https://mlsanity.com/paper/2310.17534/) (2023)
- [General Adversarial Defense Against Black-box Attacks via Pixel Level and Feature Level Distribution Alignments](https://mlsanity.com/paper/2212.05387/) (2022)
- [Query Attack by Multi-Identity Surrogates](https://mlsanity.com/paper/2105.15010/) (2021)
- [GSBAK: top-K Geometric Score-based Black-box Attack](https://mlsanity.com/paper/2503.12827/) (2025)
- [Boosting Decision-Based Black-Box Adversarial Attack with Gradient Priors](https://mlsanity.com/paper/2310.19038/) (2023)
- [SEA: Shareable and Explainable Attribution for Query-based Black-box Attacks](https://mlsanity.com/paper/2308.11845/) (2023)
- [Resilience and Security of Deep Neural Networks Against Intentional and Unintentional Perturbations: Survey and Research Challenges](https://mlsanity.com/paper/2408.00193/) (2024)

## Abstract (arXiv)

Generating adversarial examples in a black-box setting retains a significant challenge with vast practical application prospects. In particular, existing black-box attacks suffer from the need for excessive queries, as it is non-trivial to find an appropriate direction to optimize in the high-dimensional space. In this paper, we propose Projection & Probability-driven Black-box Attack (PPBA) to tackle this problem by reducing the solution space and providing better optimization. For reducing the solution space, we first model the adversarial perturbation optimization problem as a process of recovering frequency-sparse perturbations with compressed sensing, under the setting that random noise in the low-frequency space is more likely to be adversarial. We then propose a simple method to construct a low-frequency constrained sensing matrix, which works as a plug-and-play projection matrix to reduce the dimensionality. Such a sensing matrix is shown to be flexible enough to be integrated into existing methods like NES and BanditsTD. For better optimization, we perform a random walk with a probability-driven strategy, which utilizes all queries over the whole progress to make full use of the sensing matrix for a less query budget. Extensive experiments show that our method requires at most 24% fewer queries with a higher attack success rate compared with state-of-the-art approaches. Finally, the attack method is evaluated on the real-world online service, i.e., Google Cloud Vision API, which further demonstrates our practical potentials.