RED-Attack: Resource Efficient Decision based Attack for Machine Learning

Faiq Khalid, Hassan Ali, Muhammad Abdullah Hanif, Semeen Rehman, Rehan Ahmed, Muhammad ShafiquearXiv 2019 · arXiv

Introduction: The Vulnerability of Black-Box Models

Deep Neural Networks (DNNs) are notoriously susceptible to adversarial attacks—small, intentional perturbations designed to trick a model into misclassifying an image. While many powerful attacks are "white-box" (assuming full knowledge of the model's internal weights), real-world systems are often "black-boxes."

The most restrictive and realistic scenario is Threat Model III, where an attacker only receives the final classification label (e.g., "Stop Sign") without any probability scores or confidence levels. Existing decision-based attacks for this scenario are often "query-hungry," requiring tens of thousands of attempts to generate a single successful attack. RED-Attack (Resource Efficient Decision-based Attack) addresses this gap by generating imperceptible adversarial images using significantly fewer queries.

Overview of Threat Models I, II, and III. RED-Attack focuses on the most restrictive Threat Model III where only the class label is returned.

Methodology: Efficiency Through Optimization

RED-Attack employs a two-step methodology to minimize the number of queries while maximizing the "stealthiness" of the attack:

  1. Boundary Estimation: Instead of a random search, RED-Attack uses a half-interval search (similar to binary search). By iteratively finding the midpoint between a source image and a target image, it quickly identifies a sample right on the edge of the model's decision boundary.
  2. Adversarial Noise Optimization: Once on the boundary, the algorithm "polishes" the image to make the noise invisible to humans. It uses zeroth-order stochastic gradient estimation to find the best direction to move along the boundary. Crucially, it employs an adaptive hop size—starting with large jumps to find the general area of local minima and then halving the step size to fine-tune the perturbation.

Key Results: Superiority in the "Short-Run"

The researchers evaluated RED-Attack on standard benchmarks, including CIFAR-10 and the German Traffic Sign Recognition (GTSR) dataset. The results highlight a critical trade-off: while traditional attacks might eventually produce better results with an unlimited budget (e.g., 100,000 queries), RED-Attack is vastly superior in the "short run."

Visual comparison of adversarial images generated with 1k vs 10k queries. RED-Attack maintains high image quality even at low query counts.

When limited to just 1,000 queries, RED-Attack significantly outperformed standard decision-based attacks:

  • Perturbation Norm: Reduced by 96.1%, meaning the changes were much smaller.
  • Structural Similarity Index (SSIM): Improved by 71.7%, indicating the adversarial image looks much more like the original to the human eye.
  • Correlation Coefficient: Increased by 203%, proving the high fidelity of the generated images.

Conclusion

RED-Attack demonstrates that highly effective, imperceptible attacks can be launched against black-box models even with a very limited query budget. This efficiency makes such attacks a serious threat to real-time, resource-constrained systems like autonomous vehicles. The findings suggest that the machine learning community must prioritize developing new defense mechanisms specifically tailored for these efficient black-box scenarios.

Summary updated

Abstract

Due to data dependency and model leakage properties, Deep Neural Networks (DNNs) exhibit several security vulnerabilities. Several security attacks exploited them but most of them require the output probability vector. These attacks can be mitigated by concealing the output probability vector. To address this limitation, decision-based attacks have been proposed which can estimate the model but they require several thousand queries to generate a single untargeted attack image. However, in real-time attacks, resources and attack time are very crucial parameters. Therefore, in resource-constrained systems, e.g., autonomous vehicles where an untargeted attack can have a catastrophic effect, these attacks may not work efficiently. To address this limitation, we propose a resource efficient decision-based methodology which generates the imperceptible attack, i.e., the RED-Attack, for a given black-box model. The proposed methodology follows two main steps to generate the imperceptible attack, i.e., classification boundary estimation and adversarial noise optimization. Firstly, we propose a half-interval search-based algorithm for estimating a sample on the classification boundary using a target image and a randomly selected image from another class. Secondly, we propose an optimization algorithm which first, introduces a small perturbation in some randomly selected pixels of the estimated sample. Then to ensure imperceptibility, it optimizes the distance between the perturbed and target samples. For illustration, we evaluate it for CFAR-10 and German Traffic Sign Recognition (GTSR) using state-of-the-art networks.
BibTeX
@misc{khalid2019red,
  author = {Faiq Khalid and Hassan Ali and Muhammad Abdullah Hanif and Semeen Rehman and Rehan Ahmed and Muhammad Shafique},
  title = {{RED-Attack: Resource Efficient Decision based Attack for Machine Learning}},
  year = {2019},
  eprint = {1901.10258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.10258},
}
Figure