Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks

Francesco Croce; Maksym Andriushchenko; Naman D. Singh; Nicolas Flammarion; Matthias Hein

Source-linked AI summary

Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks

Francesco Croce, Maksym Andriushchenko, Naman D. Singh, Nicolas Flammarion, Matthias Hein

arXiv:2006.12834v3Jun 23, 2020cs.LGcs.CRcs.CVstat.ML

TL;DR

Sparse black-box attacks must operate without gradients or surrogate models while handling localized perturbations across several threat models. The paper proposes Sparse-RS, a random-search framework for score-based targeted and untargeted attacks. It reports state-of-the-art success rate and query efficiency across l0-perturbations, patches, and frames, including strong l0 results against black-box and white-box baselines.

Problem
Black-box sparse attacks lack broadly effective, query-efficient methods across l0-perturbations, adversarial patches, frames, and universal patch settings without surrogate models.
Method
Sparse-RS uses random search with specialized sampling to generate score-based targeted and untargeted attacks under sparse threat-model constraints.
Results
Sparse-RS achieves state-of-the-art success rate and query efficiency across l0-perturbations, adversarial patches, and adversarial frames, with l0-RS outperforming black-box and white-box attacks.
Takeaways & Limitations
Sparse-RS provides a versatile black-box framework for assessing robustness to localized and structured attacks beyond standard lp-threat models.
Takeaways & Limitations
The framework is evaluated in the score-based black-box setting and does not address decision-based attacks or settings with surrogate models.

Abstract

from arXiv · show

We propose a versatile framework based on random search, Sparse-RS, for score-based sparse targeted and untargeted attacks in the black-box setting. Sparse-RS does not rely on substitute models and achieves state-of-the-art success rate and query efficiency for multiple sparse attack models: $l_0$-bounded perturbations, adversarial patches, and adversarial frames. The $l_0$-version of untargeted Sparse-RS outperforms all black-box and even all white-box attacks for different models on MNIST, CIFAR-10, and ImageNet. Moreover, our untargeted Sparse-RS achieves very high success rates even for the challenging settings of $20\times20$ adversarial patches and $2$-pixel wide adversarial frames for $224\times224$ images. Finally, we show that Sparse-RS can be applied to generate targeted universal adversarial patches where it significantly outperforms the existing approaches. The code of our framework is available at https://github.com/fra31/sparse-rs.

1 Introduction

Sparse attacks modify only a small portion of an input, motivating black-box methods that efficiently handle localized perturbations without surrogate models. Sparse-RS uses random search for l0-perturbations, patches, and frames, with strong reported performance across these threat models.

Sparse attacks perturb few input components, allowing large visible changes while preserving semantic content and potentially enabling physical-world application.
Black-box score-based attacks access classifier scores but not network weights or input gradients, excluding both white-box and surrogate-model settings.
Random search is used to handle the complicated combinatorial constraints of sparse threat models through specialized sampling distributions.
Sparse-RS targets l0-perturbations, adversarial patches, and adversarial frames while avoiding surrogate models.
For l0-perturbations, Sparse-RS improves query efficiency and success rate over existing black-box attacks and reports higher success rates than state-of-the-art white-box attacks on standard and robust models.

2 Black-box adversarial attacks

Black-box adversarial attacks optimize perturbations under input-domain and threat-model constraints using only model queries. The paper frames targeted and untargeted attacks as constrained loss-minimization problems and positions random search as a suitable alternative to gradient estimation for sparse settings.

An untargeted attack seeks misclassification, whereas a targeted attack seeks classification into a chosen target class under domain and perturbation constraints.
Both attack goals can be formulated as minimizing a loss over perturbations satisfying the input-space and threat-model constraints.
A threat model is determined by the attack goal, the adversary’s knowledge level, and the allowed perturbation set.
Existing black-box methods include candidate sampling and finite-difference gradient estimation, but query costs can be high.
Random search is described as especially suitable for sparse attacks because their non-convex, combinatorial constraints are difficult for gradient-based methods.

3 Sparse-RS framework

Sparse-RS performs derivative-free optimization by sampling feasible sparse updates and retaining candidates that improve the objective. It jointly updates perturbed locations and values under a query budget, with attack-specific losses.

Random search samples an update from a distribution and accepts it when the objective decreases, while feasible constraints are enforced through candidate generation.
The framework takes a loss, original input, query limit, sparsity budget, and input-space constraints, and returns an approximate loss minimizer.
The algorithm iterates while the query budget remains and success has not been achieved, updating stored candidates when the loss improves.
Sparse-RS represents a sparse attack by perturbed locations M and inserted values Δ, then updates both through random sampling.
Sparse-RS exploits the perturbation budget and gradually shrinks candidate differences across iterations, while using margin loss for untargeted attacks and cross-entropy for targeted attacks.

4 Sparse-RS for l0-bounded attacks

Sparse-RS applies randomized updates to sparse perturbation locations and values, enabling query-efficient l0 attacks. Across ImageNet, CIFAR-10, MNIST, and theoretical analysis, l0-RS achieves strong attack performance and supports robustness evaluation.

Threat model and algorithm: l0-RS modifies up to k pixels or features, separating the perturbed locations from the values inserted at those locations.Pixel-based l0-RS initializes k locations and iteratively replaces subsets of them while resampling values.
ImageNet evaluation: On ImageNet, experiments compare k ∈ {50, 150} pixel perturbations under a 10,000-query limit on VGG-16-BN and ResNet-50.The evaluation measures success rate on initially correctly classified images.
ImageNet evaluation: At all sparsity levels, l0-RS outperforms PGD0, JSMA-CE with gradient estimation, and ADMM in success rate versus queries.Figure 2 reports the comparison for untargeted black-box pixel-based l0 attacks on ImageNet.
ImageNet evaluation: 100% success rate on VGG with k = 150 requires only 171 mean queries and 25 median queries for l0-RS.The second-best method is at least 30% worse in final success rate, while 50-pixel attacks reach almost 100% success with 0.1% of ImageNet pixels.
Robustness evaluation: On ImageNet, l0-RS outperforms all black-box and white-box l0 attacks in robust test error, while the analysis establishes sublinear expected queries for sufficiently large m − k.The theoretical analysis uses a binary classifier and notes that its result does not directly transfer to neural networks.
Robustness evaluation: l0-RS achieves the highest robust test error on CIFAR-10 for pixel and feature attacks, outperforming all white-box attacks at k = 24.The comparison uses adversarially trained PreAct ResNet-18 models.

5 Sparse-RS for adversarial patches

Sparse-RS adapts random search to optimize both patch content and location under black-box constraints. Patch-RS further specializes sampling and initialization for arbitrary-valued patches, improving performance over existing methods.

General algorithm for patches: Sparse-RS jointly optimizes patch location and content, checking one discrete update per iteration.Locations are sampled within a shrinking 2D l∞-ball, enabling progressively more local optimization.
General algorithm for patches: Sparse-RS integrates SignHunter and Square Attack for patch-content updates, yielding Sparse-RS + SH and Sparse-RS + SA.Both methods are state-of-the-art black-box optimizers for l∞ attacks.
Patch-RS: Patch-RS introduces patch-specific initialization and square-shaped updates whose size decreases before final single-channel refinement.These choices target patches whose pixels can change arbitrarily within [0, 1].
Patch-RS: An ablation study shows that Patch-RS’s initialization and channel-update modifications contribute to its improved performance.
Experiments: On ImageNet, Sparse-RS + SH, Sparse-RS + SA, and Patch-RS outperform existing methods for untargeted and targeted patch attacks.The evaluation uses VGG and ResNet, patch sizes of 20 × 20 and 40 × 40, and query limits of 10,000 and 50,000.

6 Universal adversarial patches

The paper targets universal patches that fool a black-box classifier into a chosen class across unseen images and random patch locations. Its methods outperform transfer-based and gradient-estimation baselines.

Targeted universal patches: The threat model requires a chosen target class across images from another class, with the patch applied at random locations.The goal is generalization to unseen images without a surrogate model.
Targeted universal patches: Algorithm 1 uses batches of 30 training images with randomly sampled patch locations, resampling both every 10k queries within a 100k-query budget.This stochastic random-search procedure optimizes the population loss over images and locations.
Experiments: Table 5 reports success rates for targeted universal 50 × 50 patches.
Experiments: Sparse-RS + SH, Sparse-RS + SA, and Patch-RS outperform transfer-based PGD and MI-FGSM attacks and gradient-estimation ZO-AdaMM by a large margin.The experiments use VGG, 10 random target classes, and three seeds for random-search methods.
Targeted universal patches: Figure 5 visualizes pairs of images carrying the same Patch-RS universal patch that changes predictions to the desired target class.

7 Conclusion

The conclusion presents Sparse-RS as a flexible random-search framework for multiple sparse black-box threat models. It highlights strong success rates and query efficiency, including universal patches without surrogate models.

Conclusion: Sparse-RS achieves state-of-the-art success rate and query efficiency for l0 perturbations, adversarial patches, and adversarial frames.
Conclusion: Sparse-RS generates universal adversarial patches without relying on surrogate models, extending sparse black-box attacks beyond standard lp threat models.
Conclusion: The framework’s appendix supplies additional results, implementation details, and analyses across l0 attacks, patches, frames, and universal attacks.It includes targeted ImageNet attacks, malware detection, image- and location-specific patches, and universal patches.
Conclusion: The paper organizes its results by targeted attacks, untargeted-attack statistics, and hyperparameters for l0-RS and competing methods.

A.1 Targeted attacks

Targeted l0 attacks on ImageNet are evaluated at k = 150, with l0-RS achieving high success using far fewer queries than competing methods. The section also describes targeted attack comparisons and specialized sparse-search variants for patches and frames.

Targeted l0 attacks: 90%/80% success for VGG/ResNet is reached by l0-RS after 20,000 queries, while other methods remain near 0% after 100,000 queries.The targeted setting uses k = 150 and evaluates success on ImageNet.
Targeted l0 attacks: l0-RS outperforms black- and white-box attacks in pixel space and is second only to PDPGD in feature space.On VGG in feature space, l0-RS achieves similar results to PDPGD.
Targeted l0 attacks: Targeted l0-RS examples are visualized for the k = 150 pixel-based attack.The corresponding query-efficiency curves compare l0-RS, PGD0, and JSMA-CE with gradient estimation.
Adversarial patches: Patch-RS refines patches with single-channel updates, complementing threat-model-specific initialization to improve success rate and query efficiency.The refinement occurs during the second half of iterations otherwise devoted to 1 × 1 updates.
Adversarial frames: Frame-RS uses a frame-specific sampling distribution because square updates from Sparse-RS + SA are strongly constrained by narrow frame widths.The alternative sampling design improves performance over Sparse-RS + SH and Sparse-RS + SA.

D.4 Experimental evaluation

The universal-attack evaluation trains targeted patches and frames through black-box random search over batches of images and varying locations. It compares these attacks with transfer-based and other black-box baselines, while testing generalization to unseen images and architectures.

Frame evaluation: Frame-RS achieves the best image-specific frame success rate and efficiency, at least 10% above the closest competitor across tested settings.Untargeted frames use width 2 and 10,000 queries; targeted frames use width 3 and 50,000 queries.
Universal-attack procedure: Targeted universal attacks resample training images and patch locations during optimization to promote generalization without surrogate models.The procedure uses a batch of 30 images, keeps locations fixed for 10,000 iterations, then resamples them; each iteration uses 30 classifier queries.
Baselines: The evaluation compares Sparse-RS variants with PGD, MI-FGSM, PGD with gradient estimation, and an adapted ZO-AdaMM baseline.The surrogate-model baselines optimize averaged gradients over randomly positioned patches, while the black-box baselines are integrated into the universal-attack scheme.
Transfer-based baselines: Transfer-based targeted universal attacks are effective on unseen images from the source model but do not generalize to the other architecture.Table 9 averages success over 10 target classes with VGG and ResNet used as source or target models.

E.4 Additional results

Targeted universal patches and frames are evaluated on held-out images and random patch placements across multiple target classes. The reported success rates therefore measure both target-class attainment and generalization beyond the training batch.

Evaluation protocol: Targeted universal patches are evaluated on 500 images at 100 random locations, while frames are evaluated on 5,000 unseen images.Results are averaged over 10 randomly chosen target classes using the same target-class set across methods.

F Theoretical analysis of l0-RS

The theoretical analysis shows that l0-RS can require a sublinear number of queries under a sufficiently large gap between candidate-set size and sparsity. The section also connects this result to empirical settings and studies robustness and initialization choices.

Proposition 4.1: l0-RS requires a sublinear number of queries when the gap m − k is sufficiently large, improving over naive linear-query gradient estimation.The proposition analyzes finding k weights among the m smallest weights of a linear model.
Proof strategy: The proof models each l0-RS iteration as replacing one currently selected feature with one feature outside the selected set, then querying whether the loss improves.For α(i) = 1/k, each iteration exchanges one element of M with one element of U \ M.
Empirical illustration: The expected-query analysis is illustrated for d = 150,528 and k = 150, corresponding to an ImageNet setting with 50 perturbed pixels.The conclusion depends on a sufficiently large gap m − k.
Ablation studies: Ablations examine random-seed robustness, sensitivity to αinit, and the piecewise-decaying schedule for α(i), focusing on l0-RS and Patch-RS.These methods are selected because their threat models require optimizing perturbation locations.

G.1 l0-bounded attacks

The ablations examine randomness, update-size scheduling, initialization, and design choices across l0 attacks and related sparse patch/frame variants. Results show stable performance across seeds, a useful αinit range, and benefits from decaying update sizes during optimization.

Random seeds: Success rates and query statistics remain stable across 10 random seeds for l0-RS on VGG and ResNet.The study reports mean and standard deviation at sparsity levels k ∈ {50, 100, 150}.
Initialization: αinit values from 0.1 to 0.4 provide a favorable tradeoff between success rate and query consumption.Success rates are close to 100% across tested values, with slight degradation at the largest values.
Patch updates: Patch-RS consistently outperforms the compared patch attacks across tested location-to-patch update ratios.Its effectiveness is also less affected by suboptimal ratios, indicating stability of the method.
Update scheduling: Constantly small update schedules retain high success rates but increase median queries, especially at larger sparsity levels.Larger constant update sizes instead produce worse success rates than the baseline.
Update scheduling: Decaying α(i) supports an initial exploration phase followed by more local optimization.The comparison identifies this schedule as important for balancing success rate and query efficiency.
Additional ablations: The ablation tables separately evaluate initialization, single-channel updates, update ratios, and targeted universal patch and frame success rates.These experiments extend the evaluation beyond the core l0-RS random-seed and schedule analyses.