PaperlayerView exact revision on arXiv

Source-linked AI summary

STROKE: Simple Sparse Structural Occlusions for Black-Box Adversarial Attacks

Ankit Gupta, Akshat Pandya, Paul Lin, Christoph Adami, Emily Dolson

arXiv:2610.32932v1cs.CVcs.CRcs.HC

TL;DR

Query-based black-box attacks face query costs and, under area constraints, must balance success and computational overhead. STROKE searches oriented rectangular occlusions with a greedy add-and-refine procedure. Across evaluated classifiers it achieves strong attack success and query efficiency, with substantial runtime advantages over the evaluated patch-based baselines.

  • Problem

    Query-only attacks must balance query efficiency and computational overhead under explicit perturbation-area budgets.

    Source: §1 · p. 2

  • Method

    STROKE represents perturbations as oriented rectangular occlusions and optimizes them with a greedy procedure that adds strokes and then refines existing ones.

    Source: §1 · p. 2

  • Results

    Across CNN and transformer classifiers on ImageNet-1k, STROKE achieves strong attack success and query efficiency at evaluated area settings, with substantial runtime advantages over evaluated patch-based baselines.

    Source: §1 · p. 3, §6 · p. 10

  • Takeaways & Limitations

    The results support simple structured occlusions as an efficient search space for black-box adversarial optimization.

    Source: §6 · p. 10

    STROKE assumes access to confidence scores or logits, and its targeted performance is not uniformly best across settings.

    Source: §5.3 · p. 9

Abstract

from arXiv · show

We introduce STROKE, a query-efficient score-based black-box adversarial attack that constructs perturbations from simple oriented rectangular occlusions. STROKE optimizes these perturbations through a lightweight greedy add-and-refine procedure. Across diverse image classifiers, STROKE achieves high attack success with low query counts at nominal 1--2\% area settings, showing favorable performance relative to existing patch-based attacks in several configurations. Matched comparisons further demonstrate substantial reductions in wall-clock attack time, while ablation studies examine the key design choices and effectiveness across structural primitives. These findings suggest that simple structural occlusions offer an effective and computationally efficient search space for black-box adversarial attacks.

1 Introduction

Query-only attacks must balance success, query cost, and computational overhead under explicit area budgets. STROKE uses oriented rectangular occlusions and greedy add-and-refine search, with favorable candidate-discovery efficiency and runtime in the evaluated comparisons.

1 Introduction

  • In query-only settings, each model evaluation incurs latency, monetary cost, and potential rate limits, making query efficiency a central challenge.Attackers may interact with deployed models through cloud APIs or locked-down inference services.Source: §1 · p. 2
  • Explicit area budgets require attacks to balance success rate, query efficiency, and computational overhead, while more expressive patch optimization can add substantial overhead.The cited motivation identifies evolutionary search over irregular, multi-component patches as one such approach.Source: §1 · p. 2
  • STROKE represents perturbations as simple oriented rectangular occlusions, creating a compact search space that remains expressive at the evaluated pixel-coverage settings.Strokes have controllable length, width, and location, with color optionally controlled.Source: §1 · p. 2
  • The two-stage search first adds strokes to reduce clean-prediction confidence or increase target-class confidence, then refines existing strokes while holding the rest fixed.This decomposition supports efficient batched optimization while maintaining a compact structural representation.Source: §1 · p. 2
  • At corresponding area settings and query limits, STROKE shows favorable candidate-discovery efficiency versus IMPACT and Patch-RS, with substantial wall-clock reductions in matched reruns.Candidate-discovery gains are particularly large on VGG-16 and ViT-B/16; performance is competitive on ResNet-50, including targeted attacks.Source: §1 · pp. 2–3
  • The evaluation spans CNNs and transformers, multiple coverage settings and query limits, CIFAR-10/100, and ablations of geometry, proposal budget, and occlusion color.The section frames these studies as an extensive empirical evaluation.Source: §1 · p. 3

2 Related Work

Related work spans adversarial robustness, query-based black-box attacks, sparse perturbations, and visible patch attacks. STROKE positions itself as a compact structural search with a favorable success–query–runtime trade-off across the evaluated classifiers.

2 Related Work

  • Adversarial examples motivate both stronger attacks and defenses, and sufficiently strong attacks are critical to robustness evaluation.Optimization-based C&W attacks revealed that several earlier defenses offered only illusory robustness.Source: §2 · p. 3
  • Score-based black-box attacks use confidence scores or logits, while decision-based attacks use only top-1 predictions; low-dimensional search directions can reduce query complexity.Prior approaches include zeroth-order optimization, randomized search, and decision-boundary search.Source: §2 · p. 3
  • Prior visible and sparse attacks include physical patches, digital spatially constrained perturbations, and methods controlling modified-pixel counts.Closest to STROKE are query-based methods for area-budgeted occlusions, including patch-style random search and multi-component compositions.Source: §2 · p. 3
  • STROKE combines oriented rectangular strokes with greedy add-and-refine search, distinguishing it from single-patch, irregular multi-component, and unrestricted sparse-pixel geometries.The methods are compared at corresponding nominal area settings and query limits; matched reruns assess computational efficiency.Source: §2 · p. 3

3 Method: STROKE

STROKE is a query-based black-box attack that composes filled, rotated rectangles and searches their parameters with greedy add-and-refine under perturbation-area control and bounded queries.

3.1 Threat Model and Budgeted Occlusion Setting

  • With query access, STROKE supports untargeted and targeted goals under union-mask coverage control; the ADD-to-REFINE transition follows coverage, and budgets count candidate-evaluation rounds.Source: §3.1 · p. 4

3.2 Stroke Parameterization

  • Each stroke is a filled, rotated rectangle parameterized by center, angle, length, width, and RGB color; ordered strokes compose into a union mask that sets coverage.Source: §3.2 · p. 4

3.3 Objectives for Untargeted and Targeted Attacks

  • Score-based queries guide untargeted attacks by lowering clean-class confidence and targeted attacks by raising target-class confidence, without gradient information.Source: §3.3 · p. 5

3.4 Greedy Add-and-Refine Search

  • ADD retains sampled strokes; REFINE replaces existing strokes after a coverage threshold or stroke limit, while targeted runs use independent random non-clean labels and top-1 match for success.Source: §3.4 · p. 5

3.5 Implementation Notes and Efficiency

  • Vectorized mask generation and masked overwrites keep each proposal lightweight, requiring a single forward pass per candidate evaluation.Source: §3.5 · p. 5

4 Experiments

The experiments evaluate STROKE under coverage-regulated black-box attack settings across image datasets and classifiers, using query-based metrics and comparisons with established attacks. Table 2 reports fewer queries and substantially lower runtime for STROKE than IMPACT and Patch-RS in its specified setting.

4.1 Datasets

  • ImageNet-1k evaluation uses 500 validation images, excluding pre-existing errors from reported success; CIFAR-10 and CIFAR-100 are also evaluated on 500 test images each.Target labels are sampled uniformly from classes other than the clean top-1 class.Source: §4.1 · p. 6

4.2 Models

  • ImageNet classifiers include ResNet-50, VGG-16, and ViT-B/16 for baseline comparisons, with additional CNN and transformer model sweeps.The sweep models are DenseNet-121, ConvNeXt-Base, DeiT-B, and Swin-B; experiments also include publicly available adversarially trained checkpoints.Source: §4.2 · p. 6

4.3 Attack Configuration and Budgets

  • STROKE is evaluated in targeted and untargeted settings at coverage thresholds of 1% and 2%, with candidate-query limits of 5,000 and 10,000.Main comparisons fix the proposal budget at 25; stroke length varies by attack setting and width by nominal coverage.Source: §4.3 · p. 6

4.4 Evaluation Metrics

  • Attack Success Rate measures success within the query limit, while Average Queries counts candidate-evaluation rounds until success and assigns the limit to failures.Table 1 compares query-based attacks at nominal 1% and 2% area settings, reporting ASR and AQ at 5k/10k queries.Source: §4.4 · p. 6, Table 1 · p. 7
  • In untargeted ResNet-50 attacks at nominal 2% coverage and a 10,000-round limit, STROKE achieves high success with fewer queries and substantially lower runtime than IMPACT and Patch-RS.Runtime is reported in seconds per evaluated image on an NVIDIA H200 GPU.Source: Table 2 · p. 7

4.5 Baselines

  • The baseline comparison includes IMPACT, Patch-RS, and TPA at corresponding nominal area settings and query limits; Figure 2 plots ASR against query budget for STROKE, IMPACT, and Patch-RS on ResNet-50.STROKE uses coverage-triggered refinement, while baselines use their reported perturbation-area constraints.Source: §4.5 · p. 7, Figure 2 · p. 8
  • Table 1 combines STROKE results with literature-reported IMPACT, Patch-RS, and TPA results, whereas Table 2 uses reproduced comparisons under a shared evaluation protocol.The reproduced comparisons use the same subset, hardware, batching, and query-accounting protocol; the literature-reported results are not fully matched reruns.Source: §4.5 · p. 7

5 Results

At the evaluated 1–2% area settings, STROKE shows strong success–query performance against patch-based baselines, with particularly large gains on VGG-16 and ViT-B/16. The results also cover targeted attacks, additional model architectures, ablations, CIFAR datasets, and stated limitations.

5.1 ImageNet-1k results

  • Figure 3 reports high ASR within a few thousand queries across three CNNs and three transformers at nominal 2% coverage.The models are ResNet50, DenseNet-121, ConvNeXt-B, ViT-B/16, Swin-B, and DeiT-B/16.Source: Figure 3 · p. 8, §5.1 · p. 8
  • At 1–2% area settings, STROKE achieves strong success–query performance relative to patch-based baselines, with the largest gains on VGG-16 and ViT-B/16.The comparison covers three ImageNet architectures.Source: §5.1 · p. 8
  • At 2% coverage and a 10k-query limit, STROKE reaches 98.4% ASR with 796 AQ in 0.22 s/image, versus 22.53 s/image for IMPACT and 0.77 s/image for Patch-RS.The runtime comparison is for ResNet-50.Source: §5.1 · p. 8
  • At nominal 1–2% coverage, targeted attacks show the largest gains on ViT-B/16 and VGG-16, while STROKE remains competitive but sometimes trails the strongest baseline on ResNet-50.The passage describes targeted search as a harder regime.Source: §5.1 · p. 8
  • Figure 4 ablations indicate that moderately sized strokes balance coverage and controllability, larger proposal budgets improve ASR with diminishing query returns, and multicolor strokes outperform fixed-color strokes.The ablations use a nominal 2% coverage threshold and a 10k-query limit.Source: §5.1 · p. 8, Figure 4 · p. 9
  • Refinement improves ASR by 20.6 percentage points at 1% coverage and 3.8 points at 2%.The comparison uses ImageNet ResNet-50, 18 × 2 strokes, and a 10k-query budget.Source: §5.1 · p. 9, Table 3 · p. 9

5.2 CIFAR-10/100 results

  • At a nominal 5% area and 5,000-query limit, STROKE is near-ceiling on CIFAR-10, strong on untargeted CIFAR-100, and can trail the strongest baseline on targeted CIFAR-100.The evaluation uses ResNet-50.Source: §5.2 · p. 9, Table 4 · p. 10

5.3 Limitations

  • STROKE assumes access to confidence scores or logits, and targeted performance is not uniformly best across the evaluated settings.The authors note that richer occlusion primitives may improve targeted reliability under tight budgets.Source: §5.3 · p. 9

6 Conclusion

The paper concludes that STROKE combines a simple structural parameterization with greedy add-and-refine search for coverage-regulated score-based black-box attacks. Its evaluations report strong success and query efficiency, runtime advantages over evaluated patch-based baselines, and a refinement contribution under tight budgets.

6 Conclusion

  • STROKE combines a simple structural parameterization with greedy add-and-refine search for coverage-regulated score-based black-box attacks.The reported evaluation spans CNN and transformer classifiers on ImageNet-1k, with additional CIFAR-10/100 experiments.Source: §6 · p. 10
  • Matched implementations show substantial runtime advantages over the evaluated patch-based baselines.An add-only ablation establishes a contribution from refinement under tight perturbation budgets.Source: §6 · p. 10
  • The authors identify hard-label feedback and more demanding physical conditions as directions for future work.Source: §6 · p. 10

Statement of Broader Impact

The broader-impact statement frames STROKE as a tool for evaluating image-classifier robustness and notes its potential misuse to induce incorrect predictions in deployed models.

Statement of Broader Impact

  • The authors position STROKE as a robustness-evaluation method and emphasize testing defenses before safety-critical deployment, while acknowledging possible misuse against deployed models.Source: Statement of Broader Impact · p. 10

A.1 Additional Experimental Details

This section provides additional implementation details and experimental configuration for reproducibility, following the main-paper evaluation protocol unless stated otherwise.

A.1 Additional Experimental Details

  • The supplementary implementation details follow the main-paper evaluation protocol unless an exception is stated.Source: §A.1 · p. 14

A.1.1 Hardware and Runtime Environment

Experiments used a single NVIDIA H200 GPU with PyTorch, batched model evaluation, and bfloat16 inference.

A.1.1 Hardware and Runtime Environment

  • All experiments ran on a single NVIDIA H200 GPU using PyTorch.Model evaluation used bfloat16 mixed precision to improve GPU throughput.Source: §A.1.1 · p. 14
  • Batched evaluation maximized throughput while counting each model forward pass for an image as one query.Source: §A.1.1 · p. 14
  • Mixed-precision bfloat16 inference was used during model evaluation to improve GPU throughput.Source: §A.1.1 · p. 14

A.1.2 Dataset Construction

The appendix describes STROKE’s evaluation setup and implementation, then reports additional architecture, ablation, defense, visualization, and transfer results. Across these studies, outcomes vary with stroke geometry, proposal budget, color, model, and evaluation setting.

A.1.2 Dataset Construction

  • Experiments used 500 clean-correct ImageNet validation images and 500 randomly sampled CIFAR-10/100 test images, with standard model-specific preprocessing.Evaluated architectures included ResNet-50, VGG-16, ViT-B/16, DenseNet-121, ConvNeXt-B, and Swin-B, with additional DeiT variants.Source: §A.1.2 · p. 14, §A.1.3 · p. 14, §A.2.1 · p. 15

A.1.4 Attack Hyperparameters

  • Unless otherwise specified, attacks used 5,000 or 10,000 candidate-evaluation rounds and 1% or 2% nominal coverage; implementation generated rotated rectangular masks and batched active images.Candidate proposals sampled rectangle parameters, including center, orientation, and color; unsuccessful runs in ablations count as using the full query budget.Source: §A.1.4 · p. 14, §A.1.5 · p. 14, §A.3 · p. 16

A.2.1 Additional Model Families

  • STROKE achieved near-perfect success rates with relatively few average queries across additional CNN and transformer models.Table 5 covers ImageNet at 2% nominal coverage and a 10k-query limit.Source: §A.2.1 · p. 15, Table 5 · p. 16

A.3.1 Occlusion Size

  • With proposal budget fixed at 25 and multicolor strokes, 18 × 2 rectangles had the highest success on both evaluated models, while 6 × 6 reduced ResNet-50 query efficiency.The authors report that moderately elongated strokes offer the best evaluated balance of coverage and controllability.Source: §A.3.1 · p. 16

A.3.2 Queries per Occlusion

  • Increasing the per-occlusion proposal budget from 25 to 50 marginally improved ASR but increased average queries, while reducing it to 10 lowered both ASR and efficiency.Multicolor strokes achieved higher ASR and lower average query counts than fixed white occlusions on both models.Source: §A.3.2 · p. 16, §A.3.3 · p. 16

A.3.4 Alternative Structural Primitives

  • Rectangular strokes had the highest ASR on ResNet-50, while elliptical alternatives achieved comparable success and favorable query efficiency, particularly on ViT-B/16.The appendix also reproduces Patch-RS results under 10k queries at 1% and 2% area constraints, reporting broad consistency with prior work.Source: §A.3.4 · p. 17, Table 6 · p. 17, §A.4 · p. 17

A.5 Performance on Adversarial Defenders

  • STROKE succeeded against the evaluated defended models, but PatchGuard reduced ASR and required substantially more queries; Grad-CAM maps often shifted away from the original object regions after attacks.The defense evaluation used ImageNet at 2% coverage and a 10k-query limit; the Grad-CAM study used ResNet50 under the same nominal setting.Source: §A.5 · p. 18, Table 9 · p. 18, §A.6.1 · p. 18

A.7.1 Cross-Model Transferability

  • Transfer was moderate between related CNNs and lower across CNN and transformer architectures; physical ASR was 46% for STROKE versus IMPACT’s 52%, compared with digital ASRs of 99% and 85%, respectively.The t-SNE visualization qualitatively showed more dispersed adversarial embeddings, and the discussion frames sparse occlusions as relevant to localized real-world artifacts.Source: §A.6.2 · pp. 19–20, §A.7.1 · p. 21, §A.7.2 · p. 21

Related papers

Loading 2610.32932v1…