Towards Query Efficient Black-box Attacks: An Input-free Perspective

Yali Du, Meng Fang, Jinfeng Yi, Jun Cheng, Dacheng Tao

Abstract

Most black-box adversarial attacks are notoriously "query-hungry" because they struggle to maintain visual similarity to a specific source image. This paper introduces an input-free perspective, starting from a neutral gray image and using a "Region Attack" to drastically reduce the search space. By abandoning the traditional constraint of human-imperceptibility, the proposed method achieves a 100% success rate on ImageNet with an average of roughly 1,700 queries—orders of magnitude more efficient than traditional methods like ZOO.

1. Introduction

Adversarial attacks expose the vulnerabilities of Deep Neural Networks (DNNs) by slightly perturbing inputs to cause misclassification. In "black-box" scenarios, the attacker lacks knowledge of the model's architecture or weights and must rely on repeated queries to estimate gradients.

A major bottleneck in current research is the focus on making adversarial images look exactly like a specific original image (e.g., making a "cat" look like a "dog" while still appearing to be a "cat" to humans). This constraint forces the attacker to probe every pixel's role, leading to hundreds of thousands of queries. This paper argues that in many practical scenarios—such as bypassing a face ID system or simply breaking a classifier—visual similarity to a specific input is irrelevant. By adopting an input-free approach, attackers can find the most query-efficient path to a target classification.

Input-free perspective: generating a 'Stingray' adversarial example from a gray image compared to a ground-truth example.

2. Methodology: The Region Attack Framework

The authors propose the Region Attack framework, which optimizes for query efficiency through several key engineering choices:

  • Input-free Initialization: Instead of starting with a natural image, the process begins with a solid gray image (pixel values at 128). This "blank slate" prevents the optimization from getting stuck in the complex features of a natural image.
  • Region-based Perturbation (Tiling): To overcome the "curse of dimensionality," the method does not optimize every pixel independently. Instead, it perturbs a small region (e.g., 64x64) and tiles it to cover the entire input (e.g., 299x299). This exploits the translation-invariant nature of Convolutional Neural Networks (CNNs).
  • Natural Evolutionary Strategies (NES): Since gradients cannot be calculated directly, NES is used to estimate them by sampling noises and observing changes in the model's output scores.
  • Momentum-based SGD: A momentum term is incorporated into the gradient descent to stabilize the search direction and prevent oscillations caused by noisy gradient estimations.
The Region Attack framework: iterative optimization using tiled perturbations and NES gradient estimation to generate an adversarial example.

3. Experimental Evaluation

The researchers evaluated their approach using the ImageNet dataset, specifically targeting the InceptionV3 classifier. To demonstrate real-world applicability, they also tested the attack against commercial systems where the underlying model is completely unknown, including the Clarifai Food Detection API and the Baidu Animal Identification API.

4. Key Results and Insights

  • Massive Efficiency Gains: On InceptionV3, the Region Attack achieved a 100% success rate with an average of only 1,701 queries. In contrast, the baseline "ZOO" attack required over 111,000 queries to achieve similar results.
  • Real-World Success: The algorithm successfully fooled the Clarifai API (misclassifying a "vegetable" as an "apple" with 90% confidence) and the Baidu API (identifying a gray image as a "Purple heron") within a few thousand queries.
  • Neutrality as an Advantage: Starting from a gray image provides a significant advantage, as the optimizer does not have to "fight" against existing features to find the target class.
  • Dimensionality Reduction via Tiling: By repeating the adversarial pattern across the image, the attacker effectively "shouts" the target feature at the model, triggering the target classification much faster.

5. Conclusion and Limitations

While highly efficient, the Region Attack has notable limitations. The resulting images are clearly adversarial and would not bypass a human moderator, as they appear as gray squares covered in colorful textures. Additionally, the paper focuses on targeted attacks, and query efficiency still depends on the distance between the neutral gray image and the target class in the model's latent space. Future work may investigate how modern adversarial defenses, such as adversarial training or input transformation, affect these repeating adversarial patterns.

Summary updated

BibTeX
@inproceedings{du2018towards,
  author = {Yali Du and Meng Fang and Jinfeng Yi and Jun Cheng and Dacheng Tao},
  title = {{Towards Query Efficient Black-box Attacks: An Input-free Perspective}},
  booktitle = {AISec@CCS},
  year = {2018},
  url = {https://openreview.net/forum?id=XgWbT9KDNC},
}
Figure