Source-linked AI summary
Subspace Attack: Exploiting Promising Subspaces for Query-Efficient Black-box Attacks
Ziang Yan, Yiwen Guo, Changshui Zhang
TL;DR
Black-box attacks can require many costly queries because the victim’s gradients are difficult to estimate. This paper restricts gradient-estimation search to promising subspaces spanned by reference-model gradients. On CIFAR-10, the method reduces query counts versus Bandits-TD and outperforms the compared attacks in query efficiency and success rates.
Problem
Black-box gradient-estimation attacks can require many victim queries, making them costly and potentially suspicious to the classification system.
Source: §1 · p. 1Method
The subspace attack uses gradients from a few reference models as search directions for black-box gradient estimation.
Source: §6 · p. 8Results
On CIFAR-10, mean query counts fall by a factor of 1.5 to 2.1 and median query counts by 2.1 to 4.4 versus Bandits-TD, while the method also outperforms NES and Bandits-TD in success rates.
Source: §5.2 · p. 7Takeaways & Limitations
The method reports strong results even when reference models are trained on a small, inadequate dataset disjoint from the victim models’ training data.
Source: §6 · pp. 8–9The approach treats prior gradients as basis vectors on the premise that they are almost surely linearly independent.
Source: §4.1 · p. 4
Abstract
from arXiv · showhide
Unlike the white-box counterparts that are widely studied and readily accessible, adversarial examples in black-box settings are generally more Herculean on account of the difficulty of estimating gradients. Many methods achieve the task by issuing numerous queries to target classification systems, which makes the whole procedure costly and suspicious to the systems. In this paper, we aim at reducing the query complexity of black-box attacks in this category. We propose to exploit gradients of a few reference models which arguably span some promising search subspaces. Experimental results show that, in comparison with the state-of-the-arts, our method can gain up to 2x and 4x reductions in the requisite mean and medium numbers of queries with much lower failure rates even if the reference models are trained on a small and inadequate dataset disjoint to the one for training the victim model. Code and models for reproducing our results will be made publicly available.
1 Introduction
Black-box attacks are more practical when little about the target model is exposed, but estimating its gradients can require costly, suspiciously numerous queries. The paper uses gradients from reference models to search promising subspaces, aiming to reduce queries while retaining lower failure rates.
1 Introduction
- High query complexity makes gradient-estimation attacks costly and potentially suspicious to the target classification system.These attacks issue queries to approach the victim’s input gradient.Source: §1 · p. 1
- Black-box attacks generally require little information beyond the target’s confidence scores, whereas white-box attacks use access to critical information such as architecture and learned parameters.White-box methods can use forward and backward passes to craft adversarial examples.Source: §1 · p. 1
- The paper proposes using gradients from a few reference models as heuristic search directions in lower-dimensional subspaces to reduce black-box query complexity.The authors report query reductions and lower failure rates, including when reference models use a small dataset disjoint from the victim’s training data.Source: §1 · p. 2
2 Related Work
Prior black-box approaches either exploit transferability or estimate the victim’s gradient through queries. The proposed method uses reference-model gradients as search directions for gradient estimation, connecting the two approaches.
2 Related Work
- Transfer-only attacks can have high failure rates, while query-based gradient estimation can require tens of thousands of queries on natural images.Transfer-based work includes substitute models trained using victim-labeled queries [27] [28] and ensembles [22]; query-based methods include finite differences and NES [13].Source: §2 · p. 2
- Black-box attacks based on transferability exploit examples crafted on one model that can also fool another, but such attacks can suffer high failure rates.Papernot et al. train a substitute model using a dataset labeled by querying the victim [27] [28].Source: §2 · p. 2
- The method bridges transfer-based and query-based attacks by using reference-model gradients as heuristic directions for finite-difference estimation.The paper characterizes this as more query-efficient than recent query-based attacks.Source: §2 · p. 2
3 Motivations
The authors investigate whether black-box attacks can search lower-dimensional subspaces rather than the full image space. Their experiments motivate replacing random directions with reference-model gradients as more promising search directions.
3 Motivations
- The motivation is that natural images may have a lower intrinsic dimension than their pixel count because some pixels or directions are less predictive of image labels.The authors relate this hypothesis to discriminative components and suppressed irrelevant variations in classification models.Source: §3 · pp. 2–3
- The initial experiment estimates gradients and attacks within m orthogonal random directions, using bandit optimization and PGD.The search direction is sampled from a Gaussian distribution, and each optimization step uses two victim queries to calculate the directional estimate.Source: §3 · p. 3
- At m = 2000, random-subspace attacks approach a ∼10% failure rate, comparable to optimization in the original n = 3072-dimensional image space.For m > 500, failure rate and mean and median query counts barely change; the experiment uses 1,000 CIFAR-10 test images and a 2,000-query cap.Source: §3 · p. 3
- Reference-model gradients are proposed as more principled basis vectors because gradients from substitute models can transfer, while here they serve only as priors.The basis can be adaptive: prior gradients may be recalculated at each iterative-attack step, and other zeroth-order optimizers are left for future exploration.Source: §3 · pp. 3–4
- Prior-gradient subspaces have lower failure rates and better align with precise WRN gradients than random-direction subspaces.Figure 2 compares failure rates and mean squared projection residuals; it adds prior gradients from deep to shallow models.Source: §3 · p. 4, Figure 2 · p. 4
4 Our Subspace Attack
The subspace attack uses reference-model input-gradients to guide black-box search, while addressing the cost of computing many gradients and the risk that the chosen subspace is poorly aligned. It uses coordinate descent for efficiency and drop-out/layer gradients to broaden the search priors.
4 Our Subspace Attack
- The subspace attack uses reference-model input-gradients as search directions, but many models are costly to load and compute, and attacks restricted to their subspaces may fail.The paper names this method the subspace attack and summarizes it in Algorithm 1.Source: §4 · p. 4
4.1 Coordinate Descent for Efficiency
- Coordinate descent updates along one or several basis directions, reducing the need to compute prior gradients for every reference model at each step.The authors report that one prior gradient suffices in experiments.Source: §4.1 · pp. 4–5
4.2 Drop-out/layer for Exploration
- Drop-out/layer gradients broaden the search priors by temporarily removing hidden units or residual blocks from reference models.The motivation is to reduce failure from imperfect alignment when only a few, potentially inadequate, reference models are available; random added vectors did not help much in the authors’ experiments.Source: §4.2 · p. 5
5 Experiments
The experiments compare the subspace attack with prior black-box methods on CIFAR-10 and ImageNet and examine reference-model data, dropout, and model selection. The attack reduces query counts and failure rates in the reported comparisons, while reference-model training scale and search policy affect performance.
5 Experiments
- The experiments evaluate untargeted and targeted ℓ∞ attacks on CIFAR-10 and ImageNet, using failure rate and mean and median queries of successful attacks.The untargeted and targeted query limits are 10,000 and 50,000, respectively.Source: §5 · p. 6, §5.1 · p. 6
5.1 Experimental Setup
- Reference models are trained from scratch on CIFAR-10.1’s 2,000 images, while experiments also use CIFAR-10 and ImageNet victim models with different architectures.CIFAR-10 experiments include WRN, GDAS, and PyramidNet+ShakeDrop; ImageNet experiments include Inception-v3, PNAS-Net, and SENet.Source: §5.1 · pp. 6–7
5.2 Comparison with The State-of-the-arts
- On CIFAR-10, the method reduces mean queries by 1.5–2.1× and median queries by 2.1–4.4× versus Bandits-TD; it also outperforms state of the arts on ImageNet with little overhead.The CIFAR-10 comparison covers three victim models; the ImageNet experiments use 1,000 validation images.Source: Table 1 · p. 6, §5.2 · p. 7
5.3 Dropout Ratios and Training Scales
- Adding 8,000 training images cuts query counts by over 2× without dropout and lowers failure rates; dropout also lowers failure rates across reference training sets.With shared reference and victim training data, the method averages 59 queries and succeeds on 98.6% of test images without dropout.Source: §5.3 · pp. 7–8, Table 2 · p. 8
5.4 Choice of Reference Models and Prior Gradients
- Increasing the number of reference models improves both query efficiency and success rates.The reference models are trained on CIFAR-10.1, and the maximum dropout ratio is 0.5.Source: §5.4 · p. 8, Table 3 · p. 8
- The coordinate-descent-flavored policy gives a sensible efficiency-effectiveness trade-off: full-subspace gradient descent barely changes query counts or failure rates while significantly increasing runtime.The reported gradient-descent results are 389/62 mean/median queries and a 0.3% failure rate.Source: §5.4 · p. 8
6 Conclusion
The conclusion presents subspace attack as a way to reduce black-box query complexity by restricting gradient-estimation directions to subspaces spanned by reference-model input gradients. It reports strong results on CIFAR-10 and ImageNet, including against models with searched architectures and winning models.
6 Conclusion
- The method restricts gradient-estimation search directions to promising subspaces spanned by input-gradients from a few reference models.It uses coordinate-descent-flavored optimization and dropout to address potential issues and trade off query complexity against failure rate.Source: §6 · p. 8
- Experiments on CIFAR-10 and ImageNet show large-margin improvements over state-of-the-art methods, even with reference models trained on a small, inadequate, disjoint dataset.Source: §6 · pp. 8–9
- The evaluation includes winning models such as PyramidNet+ShakeDrop+AutoAugment and SENet, as well as models with neural-architecture-search-designed architectures such as GDAS and PNAS.Source: §6 · p. 9
1 Results for Targeted Attacks
The targeted-attack results report lower query complexity and failure rates for the proposed method on CIFAR-10, and a low failure rate for its ImageNet test. The section also notes that mean and median query counts can differ substantially because query requirements vary across images.
1 Results for Targeted Attacks
- Targeted attacks count as successful only when the victim predicts the sampled target class, unlike untargeted attacks, which require any prediction different from ground truth.Source: §1 · p. 11
- On CIFAR-10 targeted attacks, the method reduces query complexity and failure rates across all victim models; ImageNet ℓ∞ targeted attacks have a 0.8% failure rate with 7,695/3,200 mean/median queries.The CIFAR-10 comparison uses an ℓ∞ perturbation limit of ϵ = 8/255; the ImageNet PGD step size and perturbation limit match the untargeted experiments.Source: §1 · pp. 11–12, Table 1 · p. 11
- Query requirements vary dramatically across images, motivating additional sample statistics beyond mean and median in future comparisons.Source: §1 · p. 12
2 Attack Models Guarded via Ensemble Adversarial Training
The method is evaluated against an Inception-v3 victim trained with ensemble adversarial training. It outperforms NES and Bandits-TD in query efficiency and failure rate despite using naturally trained reference models.
2 Attack Models Guarded via Ensemble Adversarial Training
- Against the ensemble-adversarially-trained victim, the subspace attack outperforms NES and Bandits-TD in query efficiency and failure rate despite naturally trained reference models.The victim is a pre-trained Inception-v3 model trained with Step-LL examples generated on an ensemble of four models.Source: §2 · p. 12
- The evaluation uses an officially released Inception-v3 victim trained with Step-LL examples generated on an ensemble of four models.Source: §2 · p. 12
- The experiment tests whether the method remains effective on a victim model guarded via ensemble adversarial training, a setting criticized as problematic for transfer-based attacks.Source: §2 · p. 12
3 Results for ℓ2 Attacks
For targeted ℓ2 attacks on CIFAR-10, the method outperforms competitive methods in query efficiency and failure rates. The evaluation uses a 4.6 perturbation budget and a 50,000-query limit.
3 Results for ℓ2 Attacks
- 69 mean queries and 34 median queries for Ours, versus 206 mean and 140 median queries for Bandits-TD; both report a 0.0% failure rate.The reported comparison also shows Ours outperforming all competitive methods by large margins in query efficiency and failure rates.Source: §3 · pp. 12–13
- The targeted ℓ2 CIFAR-10 evaluation uses 1,000 images, a ConvNet victim, and a perturbation budget of ϵ = 4.6.ZOO and AutoZOOM results are cited from prior work; the passage notes they did not enforce a strict maximum perturbation budget.Source: §3 · p. 12
- The query limit for the targeted experiments is 50,000.Source: §3 · p. 13