Simple rectangular occlusions achieve high black-box attack success with few queries
The claim
STROKE can reliably fool diverse image classifiers using 1-2% area occlusions with low query counts
Published as: “STROKE: Simple Sparse Structural Occlusions for Black-Box Adversarial Attacks”
So what
The runtime efficiency enables large-scale robustness testing of vision models that would be impractical with slower patch-based black-box attacks.
The five-minute version
STROKE achieves very high untargeted attack success (up to 98.4% ASR) with low query counts and dramatically faster wall-clock time (0.22 s per image) compared to prior patch attacks. It uses a simple rectangular stroke parameterization and a greedy add-and-refine search, yielding strong performance across CNN and transformer models at 1-2% pixel coverage. Targeted attacks are competitive but not uniformly best, and the method requires confidence scores. The evidence comes from experiments on 500 ImageNet and CIFAR images with baselines IMPACT, Patch-RS, and TPA.
What they found 2
- STROKE reaches 98.4% attack success with 796 average queries in 0.22 seconds per image, far faster than baselines.
“In the ResNet-50 runtime comparison at the nominal 2% setting and 10k query limit (Tab. 2), STROKE reaches 98.4% ASR with 796 AQ in 0.22 s/image, compared with 22.53 s/image for IMPACT and 0.77 s/image for Patch-RS.”
- Refinement adds up to 20.6 percentage points to success at low coverage.
“As shown in Table 3, refinement improves ASR by 20.6 percentage points at the 1% coverage threshold and 3.8 points at 2%.”
What undercuts it the paper’s own results
- Targeted performance is not uniformly best across all settings in Tabs. 1 and 4, and richer occlusion primitives may improve targeted reliability under tight budgets.
- On ResNet-50, it remains competitive but trails the strongest baseline in some targeted configurations, consistent with the harder targeted search regime.
Stated limits 2
- STROKE is a score-based attack and assumes access to confidence scores or logits (Sec. 3.1).
- Targeted performance is not uniformly best across all settings in Tabs. 1 and 4, and richer occlusion primitives may improve targeted reliability under tight budgets.
What’s new here 4
- Introduces a stroke-based (oriented rectangular occlusion) primitive for black-box attacks, reducing the search space compared to arbitrary patches.
- Uses a lightweight greedy add-and-refine optimization instead of population-based evolutionary search.
- Demonstrates substantial wall-clock speedups (e.g., 0.22 s/image vs 22.53 s for IMPACT) while maintaining high success rates.
- Shows the approach works across both CNN and transformer architectures.
Artifacts & methods 7
- STROKEsystem
- stroke primitive (oriented rectangular occlusion)primitive
- ImageNet-1k validation subsetdataset
- CIFAR-10/100 test subsetsdataset
- IMPACT
- Patch-RS
- TPA