# Progressive-Scale Boundary Blackbox Attack via Projective Gradient Estimation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 51 references that are in the map.
- First posted on arXiv 10 Jun 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [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)
- [Feature Pyramid Networks for Object Detection](https://mlsanity.com/paper/1612.03144/) (2016)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Progressive Growing of GANs for Improved Quality, Stability, and Variation](https://mlsanity.com/paper/1710.10196/) (2017)
- [Aggregated Residual Transformations for Deep Neural Networks](https://mlsanity.com/paper/1611.05431/) (2016)
- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [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)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [A Fourier Perspective on Model Robustness in Computer Vision](https://mlsanity.com/paper/1906.08988/) (2019)
- [Efficient Decision-based Black-box Adversarial Attacks on Face Recognition](https://mlsanity.com/paper/1904.04433/) (2019)
- [The Space of Transferable Adversarial Examples](https://mlsanity.com/paper/1704.03453/) (2017)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [Improving Black-box Adversarial Attacks with a Transfer-based Prior](https://mlsanity.com/paper/1906.06919/) (2019)
- [Sign-OPT: A Query-Efficient Hard-label Adversarial Attack](https://mlsanity.com/paper/1909.10773/) (2019)
- [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)
- [A Unified Multi-scale Deep Convolutional Neural Network for Fast Object Detection](https://mlsanity.com/paper/1607.07155/) (2016)

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

- [Fingerprinting Deep Neural Networks Globally via Universal Adversarial Perturbations](https://mlsanity.com/paper/2202.08602/) (2022)
- [Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2206.07912/) (2022)
- [Query Efficient Decision Based Sparse Attacks Against Black-Box Deep Learning Models](https://mlsanity.com/paper/2202.00091/) (2022)
- [TPC: Transformation-Specific Smoothing for Point Cloud Models](https://mlsanity.com/paper/2201.12733/) (2022)
- [SoK: Pitfalls in Evaluating Black-Box Attacks](https://mlsanity.com/paper/2310.17534/) (2023)
- [Beyond Vulnerabilities: A Survey of Adversarial Attacks as Both Threats and Defenses in Computer Vision Systems](https://mlsanity.com/paper/2508.01845/) (2025)
- [BadPart: Unified Black-box Adversarial Patch Attacks against Pixel-wise Regression Tasks](https://mlsanity.com/paper/2404.00924/) (2024)
- [Boosting Decision-Based Black-Box Adversarial Attack with Gradient Priors](https://mlsanity.com/paper/2310.19038/) (2023)

## Abstract (arXiv)

Boundary based blackbox attack has been recognized as practical and effective, given that an attacker only needs to access the final model prediction. However, the query efficiency of it is in general high especially for high dimensional image data. In this paper, we show that such efficiency highly depends on the scale at which the attack is applied, and attacking at the optimal scale significantly improves the efficiency. In particular, we propose a theoretical framework to analyze and show three key characteristics to improve the query efficiency. We prove that there exists an optimal scale for projective gradient estimation. Our framework also explains the satisfactory performance achieved by existing boundary black-box attacks. Based on our theoretical framework, we propose Progressive-Scale enabled projective Boundary Attack (PSBA) to improve the query efficiency via progressive scaling techniques. In particular, we employ Progressive-GAN to optimize the scale of projections, which we call PSBA-PGAN. We evaluate our approach on both spatial and frequency scales. Extensive experiments on MNIST, CIFAR-10, CelebA, and ImageNet against different models including a real-world face recognition API show that PSBA-PGAN significantly outperforms existing baseline attacks in terms of query efficiency and attack success rate. We also observe relatively stable optimal scales for different models and datasets. The code is publicly available at https://github.com/AI-secure/PSBA.