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

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

cs.CVOct 23, 2026

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

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

Organizations: Department of Computer Science & Engineering Michigan State University · Coco Robotics · Program in Evolution, Ecology, & Behavior Michigan State University · Department of Physics & Astronomy Michigan State University ·

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Representative adversarial perturbations produced by different black-box attacks. STROKE produces sparse structural occlusions that visually resemble simple markings or scratches. We compare their attack success, query efficiency, and runtime against the evaluated patch-based methods at the evaluated nominal area settings. (see Tabs. 1 and 2 ).

Model	Method	Untargeted Attack (5k/10k)				Targeted Attack (5k/10k)
		1%		2%		1%		2%
		ASR	AQ	ASR	AQ	ASR	AQ	ASR	AQ
ResNet50	STROKE	90.0 / 92.8	1045 / 1469	96.8 / 98.4	700/ 796	20.2/31.8	4551/ 8183	27.2/43.0	4335/7544
	IMPACT	87.2/90.0	1236/1518	94.2/96.4	676 /1044	24.6 / 38.4	4379 /8239	38.4 / 57.8	4126 / 7148
	Patch-RS	82.4/88.2	1360/1990	89.8/93.6	982/1408	7.6/10.8	4790/9359	12.2/20.0	4711/8885
	TPA	38.0/51.0	3519/5705	51.0/57.0	2807/5091	4.3/7.6	4888/9730	7.8/15.4	4781/9479

Table 1: Comparison of query-based attacks at nominal 1% and 2% area settings. Each cell reports results at 5k/10k queries; ASR (%) is attack success rate and AQ is average queries. Higher ASR and lower AQ are better.

	STROKE (ours)			IMPACT			Patch-RS
	ASR $\uparrow$	AQ $\downarrow$	Time $\downarrow$	ASR $\uparrow$	AQ $\downarrow$	Time $\downarrow$	ASR $\uparrow$	AQ $\downarrow$	Time $\downarrow$
Results	98.4	796	0.22	95.8	839	22.53	92.4	1557	0.77

Table 2: Attack efficiency comparison for untargeted attacks on ResNet-50 with a 10,000-round query limit and nominal 2% coverage setting for STROKE. Runtime is measured on an NVIDIA H200 GPU and reported in seconds per evaluated image. STROKE achieves high attack success with fewer queries and substantially lower runtime than IMPACT and Patch-RS.

Figure 4: STROKE ablations at a nominal 2% coverage threshold and 10k-query limit (untargeted). ASR versus queries on ImageNet for ResNet-50 (top row) and ViT-B/16 (bottom row). We ablate (left) occlusion size ( $\ell$ x $w$ ) for POQB = 25, color = multi, (middle) queries per occlusion (POQB) for size = 24x2, color = multi, and (right) occlusion color mode for POQB = 25, size = 24x2.

Coverage threshold	ADD only	ADD+REFINE	Gain (pp)
1%	64.0	84.6	+20.6
2%	95.6	99.4	+3.8

Table 3: Effect of refinement on ImageNet (ResNet-50). Untargeted attack success rate (ASR, %) with

18\times 2

strokes and a 10k-query budget.

Method	Untargeted (CIFAR-10/100)		Targeted (CIFAR-10/100)
Method	AQ $\downarrow$	ASR (%) $\uparrow$	AQ $\downarrow$	ASR (%) $\uparrow$
STROKE (ours)	56.16 / 45.99	100.0 / 100.0	185.60 / 1551.00	100.0 / 80.8
IMPACT	113.98 / 72.81	99.2 / 99.3	1634.36 / 1556.17	92.7 / 90.1
Patch-RS	156.78 / 98.52	97.8 / 98.1	2155.47 / 2310.80	85.3 / 82.5

Table 4: Performance on CIFAR-10 and CIFAR-100 using ResNet-50. Results are reported under a query budget of 5,000 and a nominal coverage threshold of 5% for STROKE. ASR (%) denotes attack success rate and AQ is average number of queries. Higher ASR and lower AQ indicate better attack performance. Best values are in bold.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Model	ASR (%) $\uparrow$	AQ $\downarrow$
DenseNet-121	100.0	180
ConvNeXt-B	99.6	653
Swin-B	98.4	780
DeiT-B	99.8	592

Appendix

Table 5: Additional architecture evaluation for STROKE. Results on ImageNet at a nominal 2% coverage threshold and 10k-query limit (untargeted). We report attack success rate (ASR) and average queries (AQ).

	ResNet-50		ViT-B/16
Primitive	ASR	AQ	ASR	AQ
Rectangle ( $18\times 2$ )	99.4	798.5	96.8	1066.5
Circle ( $6.8\times 6.8$ )	96.8	741.9	96.6	744.3
Ellipse ( $9.6\times 4.8$ )	95.6	889.8	97.4	717.0
Ellipse ( $13.6\times 3.4$ )	95.2	795.0	97.6	756.1

Appendix

Table 6: Comparison of structural primitives. Untargeted ImageNet results (

N=500

) at a nominal 2% coverage setting and 10k-query limit. ASR is attack success rate (%) and AQ is average queries.

Occlusion Size (POQB=25, color=multi)
Setting	ResNet-50		ViT-B/16
Setting	ASR (%) $\uparrow$	AQ $\downarrow$	ASR (%) $\uparrow$	AQ $\downarrow$
24 $\times$ 2	98.4	796.1	95.2	1130.9
18 $\times$ 2	99.4	798.5	96.8	1066.5
6 $\times$ 6	93.0	1484.9	96.0	1151.0
Queries per Occlusion (size=24 $\times$ 2, color=multi)

Appendix

Table 7: Ablation summary for STROKE (untargeted). Results on ImageNet at a nominal 2% coverage threshold and 10k-query limit. We report attack success rate (ASR) and average queries (AQ), where unsuccessful runs are counted as using the full query budget. Best values within each ablation block are bolded.

Model	Method	1% Budget (10k)		2% Budget (10k)
Model	Method	ASR (%) $\uparrow$	AQ $\downarrow$	ASR (%) $\uparrow$	AQ $\downarrow$
ResNet50	Patch-RS	83.29	2406.2	92.43	1557.3
ViT-B/16	Patch-RS	82.09	3588.9	94.28	2915.2
DeiT-B	Patch-RS	83.05	4107.1	95.64	3606.5
DenseNet-121	Patch-RS	88.89	1990.9	96.48	1386.6

Appendix

Table 8: Reproduced and extended Patch-RS baseline results. We reproduce Patch-RS using the publicly available implementation under its original pixel-budgeted evaluation setting. Results are reported for a 10k query budget under both 1% and 2% perturbation area constraints.

Model	ASR (%) $\uparrow$	AQ $\downarrow$
AT-ResNet50-L2 ( $\epsilon=3.0$ )	100.0	381
AT-ResNet50-Linf ( $\epsilon=4/255$ )	100.0	243
BagNet17 + PatchGuard	55.2	4817

Appendix

Table 9: Performance of STROKE against adversarial defender models. Results are reported at a nominal 2% coverage threshold and 10k-query limit in the untargeted setting.

Figure 5: Grad-CAM visualizations for representative examples at the nominal 2% pixel-coverage threshold and 10k-query limit on ResNet50. Columns show the clean image, the corresponding Grad-CAM map, the adversarial image produced by STROKE, and the Grad-CAM map of the adversarial prediction. The attention regions often shift away from the original object regions after the attack.

Figure 6: t-SNE visualization of ResNet50 feature embeddings for clean images (top) and adversarial images generated by STROKE (bottom). Each point is rendered as a thumbnail of the corresponding image. Adversarial perturbations lead to a noticeable redistribution of samples in the embedding space compared to the clean inputs.

Figure 7: Transferability of adversarial examples generated by STROKE across different architectures. Rows correspond to the source model used to generate adversarial examples, and columns correspond to the target model used for evaluation. Each cell reports the attack success rate (ASR, %). Results are shown for (left) cross-model transfer among commonly used architectures, (middle) transfer within CNN-based models, and (right) transfer within transformer-based models at a nominal 2% coverage threshold and 10k-query limit.

Black-Box Adversarial Attacks

Black-box adversarial attacks study how inputs can fool AI systems when attackers cannot inspect model parameters or gradients.

See all 175 papers

Opportunistic Target Selection: Early Directional Commitment for Query-Efficient Black-Box Adversarial Attacks
May 25, 2026Florent Tariolle, Florian YgerAdversarial Attacks Black-Box Adversarial Attacks
INSA Rouen Normandy · LITIS
Reinforcement Learning Inspired Black-box Adversarial Attacks for Computer Vision
Sep 21, 2026Florian Krone, Elena Hoemann, Sven HallerbachAdversarial Attacks Adversarial Robustness
Institute for AI Safety and Security German Aerospace Center (DLR) Sankt Augustin, Germany
Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion
Oct 12, 2026Ali Javeri, Javad Hezareh, Radin Shahdaei +1Adversarial Robustness Adversarial Attacks
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

May 25, 2026J/K move · Enter open · S save

Opportunistic Target Selection: Early Directional Commitment for Query-Efficient Black-Box Adversarial Attacks

Florent Tariolle, Florian Yger

INSA Rouen Normandy · LITIS

Adversarial Attacks Black-Box Adversarial Attacks

Open paper AskPDF arXiv

Black-box adversarial attacks that minimize only the ground-truth confidence suffer from class drift: perturbations wander through the feature space without committing to a specific adversarial class, wasting queries on diffuse, undirected progress. We introduce Opportunistic Target Selection (OTS), a lightweight wrapper that switches an untargeted attack to a targeted objective early in its trajectory, locking onto whichever non-true class currently leads. OTS requires no architectural modification to the underlying attack, no gradient access, and no a priori target-class knowledge. We validate OTS on three score-based attacks (SimBA, Square Attack with cross-entropy loss, and Bandits) across five standard ImageNet classifiers (4,500 runs). On random-search attacks, OTS closely tracks oracle performance, with gains up to +27 pp in success rate and 43% relative reduction in censored-mean iterations on ResNet-50. On gradient-estimation attacks (Bandits) and attacks with margin loss, OTS is redundant, a negative result that reinforces our interpretation of OTS as a margin-loss surrogate. On adversarially-trained models, a bimodal difficulty distribution eliminates the regime where targeting helps.

Abstract

Black-Box Adversarial Attacks

Explore similar work

Opportunistic Target Selection: Early Directional Commitment for Query-Efficient Black-Box Adversarial Attacks

Reinforcement Learning Inspired Black-box Adversarial Attacks for Computer Vision

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion