TL;DR
D-BADGE introduces a practical method to generate Universal Adversarial Perturbations (UAPs)—a single noise pattern that fools a neural network on almost any input—in strict decision-based black-box settings where the attacker only observes top-1 predicted labels. By pooling binary decisions over mini-batches and measuring distance using a continuous, convex Hamming loss, the authors estimate pseudo-gradients via a momentum-accelerated SPSA algorithm. The resulting attack matches or exceeds white-box and score-based benchmarks while cutting generation time by roughly $3\times$ to $5\times$, successfully attacking both CNNs and Vision Transformers.
What Problem Does This Paper Address?
Universal Adversarial Perturbations (UAPs) are image-agnostic perturbations added to any input to cause misclassification. However, existing methods to generate UAPs typically assume either:
- White-box access (full access to model weights and backpropagation gradients), or
- Score-based black-box access (receiving continuous prediction probabilities or confidence scores for every query).
In realistic deployment settings (such as commercial vision APIs), attackers only receive a hard categorical label (a decision-based black-box environment). Crafting universal perturbations here is notoriously difficult because individual discrete labels discard probability distributions, leaving zeroth-order optimizers without reliable gradient magnitude or direction. Prior attempts (such as DUAttack) rely heavily on spatial diagonal perturbations that fool convolutional networks but fail on Vision Transformers (ViTs), whose patch-based tokenization and self-attention break such structured noise.
Methods
D-BADGE (Decision-Based Adversarial Batch Attack with Directional Gradient Estimation) overcomes the information bottleneck of discrete decisions through three main components:
- Batch-Level Decision Aggregation: Instead of updating the perturbation on individual images sequentially, the method queries a mini-batch of inputs ($B = 256$) simultaneously. Aggregating discrete Bernoulli outcomes across a batch produces an empirical distribution, restoring the continuous loss signal lost at the single-image level.
-
Continuous Hamming Loss ($L_H$): To measure divergence between batch predictions and ground-truth vectors, the authors adapt the discrete Hamming distance into a continuous loss function: $$L_H(y_1, y_2) = \frac{1}{N_{\text{cls}}} \sum_{i=1}^{N_{\text{cls}}} \max(0, y_{1,i} + y_{2,i} - 1)$$ The paper mathematically proves that $L_H$ is convex (via a positive semi-definite zero Hessian) and 1-Lipschitz continuous, ensuring stability when paired with stochastic gradient approximations. A inverted formulation ($L_H^{\text{target}}$) is also provided for targeted attacks.
-
SPSA with Adaptive Momentum (SPSA-AM): The framework uses Simultaneous Perturbation Stochastic Approximation (SPSA), sampling a random step vector $u \in \{\pm\delta\}$ and evaluating symmetrical perturbations ($p + u$ and $p - u$) on the batch. It computes directional pseudo-gradients and integrates Adam optimizer moments ($\beta_1 = 0.5, \beta_2 = 0.999$) to stabilize optimization trajectories.
x ──┬──> [+ (p - u)] ──> Victim ──> Binary Labels ──┐
│ ├──> Compute L_H ──> SPSA-AM ──> Update p
└───> [+ (p + u)] ──> Victim ──> Binary Labels ──┘
Datasets
The authors evaluated D-BADGE across standard computer vision benchmarks (no new datasets were introduced):
- CIFAR-10 & CIFAR-100: Evaluated against multiple architectures (ResNet18/20, VGG19, MobileNetV2, ResNeXt29, ViT-T, Swin-T).
- ImageNet-1k & ImageNet-12: Evaluated on large-scale vision tasks using ViT and Swin Transformer backbones.
- MNIST: Tested on a toy CNN for qualitative visual inspection across varying $l_\infty$ budgets.
Key Insights and Ideas
- Decisions act as a continuous proxy over batches: While single hard labels provide no loss gradient, collective categorical decisions across a batch measure distribution shift accurately enough to substitute for true confidence scores.
- ViTs require patch-aware noise: Unlike DUAttack’s fixed diagonal patterns, D-BADGE produces block/patch-aligned perturbation artifacts on ViTs, showing that zeroth-order batch estimation can autonomously adapt to transformer token structures.
- Architecture-family isolation: Perturbations transfer reliably within the same architectural paradigm (ASR $>40\%$ across CNNs; $>20\%$ across ViTs), but transfer poorly between CNNs and Transformers (averaging only $10.92\%$). Swin Transformer bridges this slightly ($16.02\%$), likely because its hierarchical windowed attention shares local inductive biases with convolutions.
Key Results
Under an $l_\infty = 10.0$ perturbation budget on CIFAR-10:
- Higher Attack Success Rate (ASR): On ResNet18, D-BADGE achieved $85.88\%$ ASR, outperforming the white-box DF-UAP ($73.99\%$) and the decision-based DUAttack ($85.10\%$). On MobileNetV2, it reached $88.06\%$ (vs. DUAttack’s $82.49\%$).
- Substantial Gains on Transformers: On ViT-T, D-BADGE reached $57.67\%$ ASR (DUAttack scored $36.19\%$). On Swin-T, it reached $65.70\%$ (DUAttack scored $42.66\%$).
- Training Time Efficiency: On ResNet18, D-BADGE required 6,541 seconds, compared to 28,852 seconds for DUAttack and 91,945 seconds for DF-UAP. Per image, empirical runtime was $\approx 0.13$s vs. DUAttack's $0.57$s.
- Large-Scale Models & Targeted Attacks: On ImageNet-1k, D-BADGE achieved $90.91\%$ (ViT) and $97.69\%$ (Swin-T) ASR. Targeted attacks on CIFAR-10 reached an average class accuracy of $70.03\%$ to $88.90\%$ across tested networks.
Limitations and Future Work
- Query Intensity: Although computationally faster per update, generating the UAP requires iterating over many batches with multiple queries per step, which is detectable under strict query-limiting firewalls.
- Data Assumption: The method assumes the attacker has access to IID training/evaluation data sampled from the target domain (i.e., not source-free or data-free).
- Vulnerability to Strong Ensembles: When evaluated against modern ensemble defenses (such as iGAT combined with ADT/DVERGE), D-BADGE's ASR plummeted below $5\%$, demonstrating that decision-based UAPs struggle against diversity-regularized defenses.
- Cross-Architecture Transferability: Attacking an unknown Transformer using a UAP trained on a CNN (and vice versa) remains largely ineffective. The authors note reducing overall query counts as their primary target for future work.
Summary updated