Source-linked AI summary
Parsimonious Black-Box Adversarial Attacks via Efficient Combinatorial Optimization
Seungyong Moon, Gaon An, Hyun Oh Song
TL;DR
Black-box adversarial attacks must find perturbations using only query access, making gradient-based optimization difficult and potentially query-intensive. This paper replaces gradient estimation with a discrete surrogate and reports state-of-the-art attack performance with substantially fewer queries on Cifar-10 and ImageNet.
Problem
Black-box attackers have only a zeroth-order loss oracle and must craft small-ℓ∞ perturbations without access to input gradients.
Method
The method formulates a discrete surrogate over perturbation vertices and optimizes selected pixel sets without estimating the gradient vector.
Results
The method achieves state-of-the-art attack success rates with significantly lower query counts across untargeted and targeted attacks on Cifar-10 and ImageNet.
Takeaways & Limitations
Avoiding gradient estimation removes update hyperparameters and supports parsimonious black-box attacks that terminate without excessive queries.
Takeaways & Limitations
The formulation is not generally submodular, and the approximation-bound proof assumes the set function is non-negative.
Abstract
from arXiv · showhide
Solving for adversarial examples with projected gradient descent has been demonstrated to be highly effective in fooling the neural network based classifiers. However, in the black-box setting, the attacker is limited only to the query access to the network and solving for a successful adversarial example becomes much more difficult. To this end, recent methods aim at estimating the true gradient signal based on the input queries but at the cost of excessive queries. We propose an efficient discrete surrogate to the optimization problem which does not require estimating the gradient and consequently becomes free of the first order update hyperparameters to tune. Our experiments on Cifar-10 and ImageNet show the state of the art black-box attack performance with significant reduction in the required queries compared to a number of recently proposed methods. The source code is available at https://github.com/snu-mllab/parsimonious-blackbox-attack.
1. Introduction
Black-box attacks must craft adversarial perturbations using only input queries and predictions, without model weights or gradients. The proposed discrete surrogate avoids gradient estimation and achieves strong attack performance with fewer queries on Cifar-10 and ImageNet.
- The attacker in black-box settings sees only input queries and model predictions, while the network weights remain hidden.
- The method uses a discrete surrogate that constructs perturbations without estimating the gradient vector, eliminating first-order update hyperparameters.
- On Cifar-10 and ImageNet, the method achieves state-of-the-art black-box attack performance with higher success rates and fewer function queries than recent baselines.
- In some Cifar-10 settings, the method reaches attack success rates comparable to white-box PGD while using more queries as a black-box attack.
2. Related works
Prior black-box attacks either transfer perturbations from substitute networks or estimate gradients through repeated queries. These approaches face transferability or query-efficiency challenges, motivating methods that avoid direct gradient estimation.
- Decision-only black-box attacks can require up to 1M queries per image, limiting practical applicability.
- Substitute-network attacks craft perturbations using surrogate gradients, but targeted adversarial noise often transfers poorly to the target network.
- Coordinate-wise numerical gradient estimation can require approximately half a million queries on moderate-sized images.
- Later gradient-estimation methods reduce queries through pixel grouping, momentum-like priors, or spatially regular data-dependent priors.
3. Methods
The method replaces gradient-based black-box optimization with a discrete search over ℓ∞-ball vertices, then uses local-search and acceleration techniques to reduce query costs.
- 3.1. Problem formulation: The attack optimizes a discrete surrogate over ℓ∞-ball vertices, motivated by the vertex solutions of the corresponding linear program.The surrogate assigns +ϵ or −ϵ perturbations across pixel locations.
- 3.1. Problem formulation: Gradient-free optimization removes the update hyperparameters required by gradient-estimation attacks and supports earlier termination.The surrogate maintains a set-based representation of perturbed pixels.
- 3.1. Problem formulation: The set formulation selects pixels receiving +ϵ perturbations while assigning −ϵ to the complement, but exact optimization is NP-hard and requires 2^|V| queries naively.Here V contains all pixel locations and S is the selected subset.
- 3.2. Approximate submodularity: Although the resulting set function is not generally submodular, local search alternates positive-gain insertions and deletions and achieves a 1/3-approximation for submodular functions.The paper develops bounds for approximately submodular objectives and obtains a local optimum from the procedure.
- 3.3. Local search optimization for black-box attack on approximately submodular functions: The resulting perturbation assigns +ϵ to selected pixels and −ϵ to the remaining pixels, producing targeted ImageNet adversarial examples.The ImageNet examples show original images above the corresponding perturbed images.
- 3.4. Acceleration with lazy evaluations: Lazy evaluation has the same worst-case function evaluations as standard greedy search but provides several orders of magnitude speedups in practice.The accelerated procedure reinserts elements when their upper bounds are no longer sufficient.
4. Implementation details
The method uses cross-entropy-only access and query-limiting choices, while hierarchical block processing and mini-batching reduce the cost of evaluating perturbations.
- The method assumes only cross-entropy loss access and fixes MAXITER to 1 to reduce unnecessary query counts.Initial block sizes are k = 4 for Cifar-10 and k = 32 for ImageNet.
- Initial marginal-gain calculations require O(|V| k^2) queries and can consume many queries before perturbation begins.
- Hierarchical processing applies accelerated local search from coarse large blocks to finer smaller blocks, with most attacks terminating early.The working set for finer grids is initialized from results on coarser grids.
- The ground set is partitioned into mini-batches, whose subsets are updated sequentially to avoid processing the entire ground set at once.The mini-batch size is fixed at 64 throughout the experiments.
5. Experiments
Experiments on Cifar-10 and ImageNet compare the proposed attack with NES, Bandits, and white-box PGD under untargeted and targeted ℓ∞ settings. Across these evaluations, the method achieves higher success rates with fewer queries and remains comparatively robust to hyperparameter changes.
- 5. Experiments: The evaluation compares NES and Bandits on untargeted and targeted attacks using success rate, average queries, and median queries under ℓ∞ threat models.Cifar-10 and ImageNet are evaluated, with white-box PGD included as an upper-bound experiment.
- 5.1. Experiments on Cifar-10: 10% higher success rate than Bandits with 33% fewer average queries on untargeted Cifar-10 attacks.On samples NES successfully fooled, the method used 53% fewer queries than Bandits and 91% fewer than NES.
- 5.2. Untargeted attacks on ImageNet: 4% higher success rate than Bandits with 30% fewer queries on untargeted ImageNet attacks.On samples NES successfully attacked, the method required 38% fewer average queries than Bandits.
- 5.3. Targeted attacks on ImageNet: Near-100% success rate with about 55% fewer queries than NES on targeted ImageNet attacks.The comparison used a maximum query budget of 100,000.
- 5.4. Untargeted attacks on ImageNet with smaller ϵ: As ϵ decreases on untargeted ImageNet attacks, the success-rate margin over Bandits grows to 10% while the query-efficiency lead remains.The experiments used ϵ ∈ {0.01, 0.03}.
- 5.5. Hyperparameter sensitivity: The proposed method maintains high success with low variance as its initial block size changes, whereas Bandits shows higher variance in success rate and average queries.The method sweeps only the initial block size k, while Bandits is evaluated across multiple hyperparameters.
6. Conclusion
The paper develops a discrete surrogate for black-box adversarial attacks, avoiding gradient estimation and update hyperparameters while reducing query costs.
- The method achieves state-of-the-art attack success rates at significantly lower average, median, and NES_success query counts for untargeted and targeted attacks.The conclusion reports this outcome across neural networks under the paper’s black-box attack settings.
A.1. Proof of Lemma 1
This appendix establishes properties of local-search solutions using local optimality and the submodularity index, culminating in a theorem comparing the local solution with an optimum.
- Local search returns a local optimum because any improving addition or deletion would contradict the algorithm’s termination condition.The proof considers both removing an element from the solution and adding an element outside it.
- The submodularity index measures the degree of submodularity and provides bounds used to relate marginal gains across nested sets.The appendix introduces monotonicity properties of the index and bounds degradation in submodularity.
- Theorem 2 compares the local-search solution S with an optimal solution C using inequalities derived from local optimality and the submodularity index.The proof applies lemmas to nested sets and combines the resulting inequalities.
B.1. Experiments on Cifar-10
The appendix lists hyperparameter settings for NES and Bandits across Cifar-10 and ImageNet, including untargeted, targeted, and smaller-perturbation experiments.
- NES and Bandits hyperparameters for untargeted attacks are separately specified on Cifar-10 and ImageNet.The settings are reported in Tables 5–8, with images normalized to [0, 1] for consistency across datasets.
- NES targeted ImageNet experiments tune momentum over β ∈ {0.5, 0.7, 0.9} and select β = 0.7 because it yields the lowest average queries.Other targeted-attack hyperparameters are taken from the original paper.
- Additional hyperparameter tables cover NES and Bandits untargeted attacks on ImageNet with smaller ϵ.These settings are provided separately from the standard perturbation experiments.
C. Tuning Bandits for targeted attack
The targeted Bandits attack is tuned over image and OCO learning rates, with the selected setting chosen for strong success rate and low query cost.
- The sweep varies image learning rate h over five values and OCO learning rate η over four values, evaluating attack success rate and average queries.Other hyperparameters remain as in the untargeted setting.
- Figures 8 and 9 report success rate and average queries, respectively, for the evaluated hyperparameter settings.
- The paper uses h = 0.001 and η = 1 because this setting gives the best success rate with low average queries.The selected values are reported for Table 3.
D. Additional plot on hyperparameter sensitivity analysis
Figure 10 evaluates success-rate robustness across hyperparameter settings and query limits. The method is less sensitive to hyperparameters than Bandits at every query limit.
- Query limits are shown on the x-axis, while average success rate is shown on the y-axis.
- Our method is less sensitive to hyperparameters than Bandits at every query limit.
- The plot reports mean and standard deviation of success rate across different hyperparameter settings for each attack method.