Source-linked AI summary
Simple Black-box Adversarial Attacks
Chuan Guo, Jacob R. Gardner, Yurong You, Andrew Gordon Wilson, Kilian Q. Weinberger
TL;DR
Black-box adversarial attacks are difficult because attackers have only query access and must control costly model queries. The paper proposes SimBA, which iteratively tests signed steps along sampled orthonormal directions using continuous confidence scores; it achieves highly efficient untargeted and targeted attacks and serves as a strong baseline, while its basis and step-size choices remain open for improvement.
Problem
Black-box attacks must construct imperceptible adversarial perturbations without gradients while minimizing costly queries, and query-efficient methods remain an open problem.
Method
SimBA repeatedly samples directions from an orthonormal basis and adds or subtracts small steps according to continuous-valued model confidence scores.
Results
SimBA and SimBA-DCT achieve similar success rates to state-of-the-art black-box attacks with an unprecedentedly low number of queries across untargeted and targeted settings.
Takeaways & Limitations
SimBA provides a simple, fast baseline for black-box adversarial-image research and applies to real-world services including Google Cloud Vision.
Takeaways & Limitations
The method’s efficiency may depend on orthonormal-basis selection and step-size adaptation, which the paper identifies as areas for further improvement.
Abstract
from arXiv · showhide
We propose an intriguingly simple method for the construction of adversarial images in the black-box setting. In constrast to the white-box scenario, constructing black-box adversarial images has the additional constraint on query budget, and efficient attacks remain an open problem to date. With only the mild assumption of continuous-valued confidence scores, our highly query-efficient algorithm utilizes the following simple iterative principle: we randomly sample a vector from a predefined orthonormal basis and either add or subtract it to the target image. Despite its simplicity, the proposed method can be used for both untargeted and targeted attacks -- resulting in previously unprecedented query efficiency in both settings. We demonstrate the efficacy and efficiency of our algorithm on several real world settings including the Google Cloud Vision API. We argue that our proposed algorithm should serve as a strong baseline for future black-box attacks, in particular because it is extremely fast and its implementation requires less than 20 lines of PyTorch code.
1. Introduction
Black-box attacks are query-constrained search problems because attackers lack model internals and queries may cost time or money. The paper introduces SimBA, which uses continuous confidence scores and simple orthonormal-direction updates to achieve highly efficient attacks.
- Black-box attackers access models through queries rather than complete internal knowledge, making query count an important efficiency metric.Queries to real-world services may incur significant time and monetary costs.
- Because adversarial examples often lie near decision boundaries, attack construction can be viewed as searching within a small volume around the target image.White-box attacks guide this search with gradients, whereas black-box attacks need another strategy.
- SimBA repeatedly samples directions from a predefined orthonormal basis, uses confidence scores to choose a sign, and adds or subtracts the direction.Each accepted update moves the image toward the decision boundary and away from the original image.
- SimBA achieves similar success rates to state-of-the-art black-box attacks while using an unprecedentedly low number of queries.Its implementation requires fewer than 20 lines of PyTorch code.
2. Background
The background formalizes adversarial robustness and distinguishes white-box from more realistic black-box attacks. It then frames attack construction as loss minimization under query and imperceptibility constraints, motivating SimBA’s query-efficient iterative procedure.
- A model is ρ-robust when correctly classified inputs retain their label throughout a perceptibility-defined neighborhood.The neighborhood is represented as a hypersphere around the original image under the chosen distance metric.
- Adversarial examples motivate finding perturbations that change a model’s decision while remaining within a small perceptibility radius.Prior work links such vulnerabilities to non-robust directions and high-dimensional input spaces.
- Untargeted attacks seek any incorrect class, whereas targeted attacks seek a chosen target class.The paper focuses its discussion on untargeted attacks while stating that its arguments also apply to targeted attacks.
- Adversarial perturbation can be formulated as constrained continuous loss minimization, using the probability of the correct class as an untargeted loss.For targeted attacks, a common loss instead maximizes the probability of the chosen target class.
- White-box attacks can use gradients, but black-box attackers must minimize queries while constructing an imperceptible perturbation from input-output access alone.This setting applies to public APIs such as Google Cloud Vision and Clarifai, where each query has time and monetary cost.
- SimBA’s pseudocode samples unused directions and accepts a ±ϵ update when it lowers the model’s confidence in the original class.The query budget limits the number of iterations, so convergence speed is central.
3. A Simple Black-box Attack
The attack searches for adversarial perturbations by testing random directions from efficient orthonormal bases and accepting the sign that lowers the model's confidence. Its query efficiency depends on basis choice and step size, with low-frequency DCT directions especially effective and perturbation norm tightly linked to the query budget.
- Attack algorithm: The method repeatedly samples an orthonormal direction and adds or subtracts a step to reduce the predicted probability of the current class.It first tests x + ϵq and tries x − ϵq only if the first step does not reduce ph(y | x).
- Attack algorithm: The only hyperparameters are the orthogonal search-vector set Q and step size ϵ.
- Search bases: The standard basis performs pixel-space L0 attacks by changing one color component of one randomly selected pixel per iteration.
- Search bases: The DCT basis retains a fraction r of the lowest-frequency directions to constrain perturbations to low-frequency space.The DCT is an orthonormal transformation from image signals to frequency coefficients.
- Step size and basis choice: 98% of low-frequency DCT directions are descending in one sign, compared with 73% of pixel-space directions.The average probability change is nearly linear in ϵ, with a steeper slope for DCT directions.
- Budget considerations: Tighter query limits can be met by increasing ϵ at the cost of a higher perturbation L2-norm, while reducing ϵ permits quadratically more queries at the same norm.After T iterations, the perturbation L2-norm is at most Tϵ for any orthonormal basis.
4. Experimental Evaluation
Experiments on ImageNet and Google Cloud Vision evaluate SimBA and SimBA-DCT across query efficiency, success rate, perturbation size, and model architectures. The methods generally achieve high success with fewer queries and lower L2 distortion, while low-frequency restriction creates a success-rate trade-off for some images.
- ImageNet results: Median query counts are 944 for SimBA and 582 for SimBA-DCT in untargeted attacks, while targeted attacks require median counts of 7,038 and 4,854, respectively.SimBA-DCT fails after 60,000 queries for approximately 2.5% of targeted images, whereas SimBA reaches 100% success.
- ImageNet results: Restricting SimBA-DCT to low-frequency DCT basis vectors accelerates descent for most images but can fail to find an adversarial perturbation for some images.The paper identifies selecting the right spectrum per image as a direction for improving query efficiency and success rate.
- ImageNet results: SimBA and SimBA-DCT achieve close to 100% success rates while requiring fewer queries and lower average L2 distortion than comparison methods on ImageNet.Table 1 evaluates query count, perturbation L2-norm, and success rate for untargeted and targeted attacks.
- ImageNet results: 3-4x fewer queries—1,665 for SimBA and 1,232 for SimBA-DCT—are required for untargeted attacks than by Bandits-TD, whose success rate is 80%.The comparison uses methods constrained to close to 100% success for the proposed attacks.
- Google Cloud Vision attack: SimBA reaches 70% success after 5,000 Google Cloud Vision API calls, compared with 25% for LFBA under the same query budget.The evaluation uses 50 random images and defines success using an L2-norm threshold based on a successful SimBA run.
5. Related Work
Prior work establishes that adversarial attacks extend across diverse tasks and that defenses against black-box query-based adversaries remain comparatively underexplored. Low-frequency attack directions can also circumvent some image-transformation defenses.
- Adversarial attacks have been demonstrated across image segmentation, object detection, speech recognition, and neural-network policies.
- Defenses against black-box adversaries with query access have received less study than defenses against white-box attacks.
- Low-frequency attack directions can successfully circumvent image-transformation defenses that quantize the decision boundary.
6. Discussion and Conclusion
The paper presents SimBA as a simple black-box attack guided by continuous-valued model outputs and positions it as a strong baseline. It identifies broader applicability and several directions for reducing query use.
- SimBA takes small iterative steps guided by continuous-valued model outputs and is proposed as a strong baseline for black-box adversarial-example research.
- Additional orthonormal-basis choices and adaptive step-size selection are identified as possible ways to reduce model queries.
- The method is conceptually suitable for tasks whose target models return continuous prediction scores, including speech recognition and policy networks.
S1. Experiment on CIFAR-10
On CIFAR-10, SimBA and SimBA-DCT remain efficient without hyperparameter tuning. Both achieve full success within 10,000 queries and require approximately 300 queries on average, while low-frequency DCT is less effective than on ImageNet.
- Both SimBA and SimBA-DCT remain efficient on CIFAR-10 without hyperparameter tuning.
- Low-frequency DCT is less effective on CIFAR-10 because of the reduced image dimensionality.
- 100% success rate is achieved by both methods within a maximum of 10,000 queries.
- Approximately 300 average queries are required by both methods, matching the median; SimBA-DCT performs slightly worse because of its heavier tail.
- The supplementary figure reports the distribution of queries required for successful targeted attacks over 1,000 CIFAR-10 target images.
S2. Additional image samples for attack on Google Cloud Vision
Additional Google Cloud Vision examples show that SimBA successfully removes the three highest-ranked original labels across ten random images.
- SimBA successfully removes the top three original labels for all 10 additional random Google Cloud Vision images.
- The supplementary figure contains additional adversarial images from Google Cloud Vision.