Source-linked AI summary
Black-box Adversarial Attacks with Limited Queries and Information
Andrew Ilyas, Logan Engstrom, Anish Athalye, Jessy Lin
TL;DR
The paper asks whether black-box adversarial attacks remain possible when real systems limit queries and expose only partial or label-only information. It introduces attacks tailored to these three threat models and reports effectiveness against ImageNet and a targeted attack on Google Cloud Vision. The results suggest that classifiers remain vulnerable even with limited queries and information.
Problem
Standard black-box access assumes arbitrary queries and full class probabilities, whereas many real-world systems impose query, information, or label restrictions.
Method
The paper develops separate attacks for query-limited, partial-information, and label-only settings, including NES-based gradient estimation, target-image blending, and noise robustness.
Results
The methods are effective against an ImageNet classifier and enable a targeted black-box attack against the Google Cloud Vision API.
Takeaways & Limitations
Machine-learning systems remain vulnerable to black-box attacks despite limited queries and information.
Takeaways & Limitations
The label-only setting provides only an ordered list of inferred labels, and the paper generalizes the decision-only case where k = 1.
Abstract
from arXiv · showhide
Current neural network-based classifiers are susceptible to adversarial examples even in the black-box setting, where the attacker only has query access to the model. In practice, the threat model for real-world systems is often more restrictive than the typical black-box model where the adversary can observe the full output of the network on arbitrarily many chosen inputs. We define three realistic threat models that more accurately characterize many real-world classifiers: the query-limited setting, the partial-information setting, and the label-only setting. We develop new attacks that fool classifiers under these more restrictive threat models, where previous methods would be impractical or ineffective. We demonstrate that our methods are effective against an ImageNet classifier under our proposed threat models. We also demonstrate a targeted black-box attack against a commercial classifier, overcoming the challenges of limited query access, partial information, and other practical issues to break the Google Cloud Vision API.
1. Introduction
The paper narrows black-box threat models to realistic limits on queries, output information, and labels, then develops attacks that remain effective under those restrictions. It targets classifiers including ImageNet and Google Cloud Vision.
- Threat models: Real-world black-box systems may restrict query volume, output information, or available labels beyond standard query access.The paper defines query-limited, partial-information, and label-only settings to model these restrictions.
- Threat models: Prior targeted attacks can require millions of queries or depend on substitute-model transfer and coordinate-wise gradient estimation.These requirements make attacks impractical under commercial throughput, latency, rate, or monetary constraints.
- Proposed attacks: The paper applies Natural Evolutionary Strategies with projected gradient techniques to estimate gradients efficiently in the query-limited setting.The method avoids requiring a substitute network and is reported as 2-3 orders of magnitude more query-efficient than prior gradient-estimation methods.
- Proposed attacks: For partial information, the attack starts from a target-class image and alternates blending the original image with maximizing the target-class likelihood.It is designed to work even when only the top probability is visible.
- Proposed attacks: For label-only feedback, the method uses sorted labels and noise robustness as a proxy for classification score, succeeding even when k = 1.The paper also demonstrates a targeted attack against Google Cloud Vision despite its opaque label set, variable output length, and uninterpretable scores.
2. Approach
The approach develops query-efficient black-box attacks for query-limited, partial-information, and label-only settings. It combines NES-based gradient estimation with projected optimization and proxy scores derived from label rankings and noise robustness.
- Query-Limited Setting: NES estimates gradients through classifier queries, enabling derivative-free optimization with fewer queries than typical finite-difference methods.The method samples Gaussian noise around the current image and uses antithetic sampling for a variance-reduced estimate.
- Query-Limited Setting: In the query-limited setting, projected gradient descent uses the sign of the NES estimate within a fixed query budget.With query limit L, N queries estimate each gradient and the attack performs L/N projected-gradient steps.
- Partial-Information Setting: The partial-information attack starts from a target-class image and alternates shrinking ℓ∞ boxes with perturbations that maximize the target-class probability.Backtracking line search preserves the target class within the top-k while projected gradient descent finds each updated image.
- Label-Only Setting: The label-only setting receives only the top-k sorted labels, including the decision-only case when k = 1.The attack is designed to exploit additional ranking information when k > 1.
- Label-Only Setting: A discretized ranking score measures the adversarial label’s position, while robustness to random ℓ∞-bounded noise serves as a proxy for hidden softmax probability.The proxy score is estimated with Monte Carlo sampling and then optimized using the partial-information technique and an estimated gradient.
3. Evaluation
The evaluation measures targeted attack success and query efficiency under three restricted threat models, using ImageNet experiments and a Google Cloud Vision case study. The attacks succeed despite limited outputs and unknown labels, including forcing a skiing image to be labeled “dog.”
- ImageNet evaluation: The study evaluates targeted attacks under query-limited, partial-information, and label-only threat models.The ImageNet evaluation uses a pre-trained InceptionV3 classifier and restricts access according to each threat model.
- Evaluation metrics: Table 1 reports overall success rate and median query count for query-limited, partial-information, and label-only attacks.Results cover 1000 test images, or 100 for label-only, with randomly chosen targets and shared hyperparameters across images.
- ImageNet evaluation: 1000 randomly selected ImageNet test images receive randomly chosen target classes, with ℓ∞ perturbation limited to ϵ = 0.05.Attacks use fixed hyperparameters across images and stop upon success or a chosen query limit.
- Evaluation metrics: Success means the adversarial example is classified as the target class, while the evaluation also records the number of queries required.Any classification other than the target class counts as unsuccessful, making the task strictly harder than untargeted attack generation.
- Google Cloud Vision: The Google Cloud Vision attack addresses an unknown large label space, uninterpretable confidence scores, and an input-dependent list of returned labels.These properties make the system more restrictive than the typical black-box setting.
- Google Cloud Vision: Despite these restrictions, the partial-information attack constructs targeted adversarial examples against Google Cloud Vision.An image labeled with skiing-related classes is transformed into one that resembles the skiers but is classified as “dog.”
4. Related work
Prior black-box attacks use substitute networks or gradient estimation, but targeted transfer is unreliable and naive gradient estimation can require millions of queries. The paper positions its approach as addressing these practical constraints across more restrictive settings.
- Black-box attack approaches: Black-box attack research includes practical attacks on speech recognition, malware detection, and face recognition systems.The paper identifies substitute networks and gradient estimation as the main approaches used by current black-box attacks.
- Substitute networks: Substitute-network attacks train a model with target-model-labeled synthetic data, then generate white-box adversarial examples intended to transfer.Transfer can work across architectures or training datasets, but targeted transfer is especially difficult on large datasets such as ImageNet.
- Comparison with prior work: The authors report 94% success in the partial-information case and over 99% in the standard black-box setting.Their method requires many model queries but offers stronger guarantees that an adversarial example will be generated successfully.
- Gradient estimation: Naive zeroth-order gradient estimation for an ImageNet image can require 2 × 299 × 299 × 3 = 536406 queries.Coordinate-wise estimation is therefore not tractable without techniques that reduce the query burden.
- Alternative black-box methods: Local-search gradient estimation has produced targeted ImageNet attacks using only query access and a more constrained proxy-model setting.This work is concurrent with the Boundary Attack, which alternates boundary steps preserving adversarial classification with steps toward the original image.
- Alternative adversarial goals: Related work also evolves malicious PDFs toward benign classifications while preserving malicious behavior, whereas this paper targets multiway image classifiers under broader threat models.The paper characterizes its NES technique as closer to traditional gradient-based methods than to evolutionary algorithms.
5. Conclusion
The paper shows that classifiers remain vulnerable to black-box adversarial attacks under realistic limits on queries and information, including commercial systems.
- The authors define query-limited, partial-information, and label-only threat models for real-world black-box classifiers.
- New algorithms make attacks tractable under these restrictive threat models.
- The methods effectively attack an ImageNet classifier across the proposed threat models.
- The authors demonstrate targeted adversarial examples against the Google Cloud Vision API despite limited access and information.
- The results suggest that machine-learning systems remain vulnerable even with limited queries and information.