Opportunistic Target Selection: Early Directional Commitment for Query-Efficient Black-Box Adversarial Attacks
Florent Tariolle, Florian Yger · 2026
Read Opportunistic Target Selection: Early Directional Commitment for Query-Efficient Black-Box Adversarial Attacks by Florent Tariolle, Florian Yger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25663.txt.
Introduction
Tariolle and Yger tackle class drift in black-box attacks, where perturbations wander without committing to one class. Their Opportunistic Target Selection wrapper flips untargeted attacks to targeted goals early, locking onto the class that currently leads. It needs no attack changes, no gradient access, and no advance target knowledge. Tested on three score-based attacks across five ImageNet classifiers, it nearly matches oracle performance on random-search attacks. Gains reach 27 points on ResNet-50, but it adds nothing for gradient-estimation or margin-loss attacks.
Catalog record
| CREATOR | Florent Tariolle, Florian Yger |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24869 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25663
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Opportunistic Target Selection: Early Directional Commitment for Query-Efficient Black-Box Adversarial Attacks Florent Tariolle, Florian Yger Abstract Résumé 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. We release our code at https://github.com/Tariolle/opportunistic-target-selection . keywords Adversarial attacks, black-box, query efficiency, class drift 1 Introduction Standard untargeted black-box attacks minimize the model’s confidence in the ground-truth class. This strategy, whether implemented as probability minimization in SimBA ( Guo et al., 2019 ) or cross-entropy loss in Square Attack ( Andriushchenko et al., 2020 ) , treats all non-true classes as interchangeable. The freed probability mass spreads across remaining classes without directional commitment ; the perturbation executes a random walk through the latent space, crossing class basins opportunistically rather than heading toward a specific decision boundary. This class drift directly impacts query efficiency. Each query spent exploring a class basin that will ultimately be abandoned is wasted. The harder the model is to attack, the more basins the perturbation traverses before settling, and the more pronounced the waste becomes. Targeted attacks eliminate drift by construction but require specifying a target class a priori , which is generally unavailable in a black-box setting. Margin-based losses ( Carlini and Wagner, 2017 ) offer a partial solution by implicitly tracking the nearest decision boundary, but not all attacks support them. SimBA operates on raw probabilities ; other attacks use cross-entropy for compatibility. For these methods, drift remains the main efficiency bottleneck. Opportunistic Target Selection bridges this gap with a two-phase strategy : 1. Exploration phase. The attack runs in untargeted mode for a short prefix of T iterations. 2. Exploitation phase. The attack switches to a targeted objective against the leading non-true class, and runs until misclassification or budget exhaustion. The switch timing T is not sensitive : ablations show that any T\in\{5,\ldots,500\} yields no statistically significant difference (Wilcoxon signed-rank tests, Section 8.1 ), because class rankings stabilize within the first few iterations for drift-prone attacks. This paper makes three contributions : 1. OTS as a margin-loss surrogate. By locking onto the leading non-true class early in the trajectory, OTS approximates the competitor term of margin loss for attacks that lack implicit target tracking. This explains both where OTS helps (probability-minimization and CE losses) and where it is redundant (margin loss, gradient estimation), revealing that the information needed to select an effective target is already latent in the attack’s trajectory after just a few iterations. 2. Empirical validation across five ImageNet classifiers and three attack methods (4,500 runs), showing that OTS provides near-oracle efficiency. Target selection is critical (random targeting is catastrophic), and a short exploration phase provides cheap insurance over the clean-image argmax. 3. A characterization of targeting neutrality on adversarially-trained models, where a bimodal difficulty distribution eliminates the medium-difficulty regime where directional commitment provides value. 2 Related Work Score-based black-box attacks access the full output probability vector but not gradients. SimBA ( Guo et al., 2019 ) iterates over an orthonormal basis, accepting perturbations that reduce the true-class probability. Square Attack ( Andriushchenko et al., 2020 ) uses random square patches with a shrinking schedule ; its default margin loss implicitly tracks the nearest decision boundary, but switching to cross-entropy loss removes this guidance and introduces drift. Gradient-estimation attacks such as Bandits ( Ilyas et al., 2019 ) incorporate data-dependent priors, providing built-in directionality analogous to margin loss. Decision-based attacks (SurFree ( Maho et al., 2021 ) , CGBA ( Gesny et al., 2024 ) ) operate with top-1 labels only ; we adopt the angular convergence framework of Gesny et al., 2024 in Section 6.3 . To our knowledge, no prior work has studied online target selection during a score-based attack’s trajectory ; existing targeted attacks assume the target class is specified before the attack begins. Adversarially-trained models ( Madry et al., 2018 ; Salman et al., 2020 ) , standardized via RobustBench ( Croce et al., 2021 ) , present a qualitatively different challenge ; Section 7 examines OTS in this regime. 3 Method 3.1 Notation Let f:\mathcal{X}\to\mathbb{R}^{K} denote a classifier mapping inputs to logits over K classes, and P(k|x)=\text{softmax}(f(x))_{k} the predicted probability of class k . Given a correctly-classified input x with true label y , the attacker seeks an adversarial example x^{\prime}=x+\delta such that \arg\max_{k}P(k|x^{\prime})\neq y and \|\delta\|_{\infty}\leq\epsilon . 3.2 Untargeted Loss and the Drift Problem Standard untargeted attacks minimize a loss that depends only on the true class : \mathcal{L}_{\text{untarg.}}(x^{\prime},y)=P(y|x^{\prime})\;\text{(SimBA)}\quad\text{or}\quad\log P(y|x^{\prime})\;\text{(CE)} (1) These objectives decrease P(y|x^{\prime}) without specifying where the freed probability mass should concentrate. We call this class drift . Margin loss avoids drift by construction : \mathcal{L}_{\text{margin}}(x^{\prime},y)=f_{y}(x^{\prime})-\max_{k\neq y}f_{k}(x^{\prime}) (2) where f_{k} denotes the logit for class k (as opposed to the probability-space objectives above) and \max_{k\neq y}f_{k}(x^{\prime}) dynamically identifies the nearest competitor. Square Attack’s default loss is of this form, explaining its strong untargeted performance. A targeted attack toward class t optimizes \mathcal{L}_{\text{targeted}}(x^{\prime},t)=-P(t|x^{\prime}) (SimBA) or \log P(t|x^{\prime}) (CE). Targeting eliminates drift but requires knowing t in advance. An oracle target, defined as the class the unconstrained untargeted attack eventually reaches, provides a trajectory-specific performance ceiling that no real attacker can achieve. 3.3 Opportunistic Target Selection Algorithm OTS discovers the target class online by observing which adversarial class the perturbation is naturally drifting toward. Fixed-iteration switch (recommended). The attack runs in untargeted mode for T iterations, then switches to a targeted objective against t=\arg\max_{k\neq y}P(k|x^{\prime}) . Ablations (Section 8.1 ) show that T\in\{5,\ldots,500\} all yield indistinguishable results, so any small T suffices. Rank-stability variant. A stability counter tracks the leading non-true class after each accepted perturbation step, switching only after the same class leads for S consecutive accepted steps (Algorithm 1 ). In practice, this provides no measurable advantage over the fixed switch (Section 8.1 ). We retain it for completeness. Algorithm 1 Opportunistic Target Selection (Rank-Stability Variant) 1: image x , true label y , attack A , threshold S 2: adversarial example x^{\prime} 3: x^{\prime}\leftarrow x ; t\leftarrow\bot ; c\leftarrow\bot ; s\leftarrow 0 4: while \arg\max_{k}P(k|x^{\prime})=y and budget remaining do 5: if t=\bot then 6: x^{\prime}\leftarrow A.\text{step}(x^{\prime},y) 7: \ell\leftarrow\arg\max_{k\neq y}P(k|x^{\prime}) 8: if \ell=c then s\leftarrow s+1 9: else c\leftarrow\ell ; s\leftarrow 1 10: end if 11: if s\geq S then t\leftarrow c 12: end if 13: else 14: x^{\prime}\leftarrow A.\text{step}(x^{\prime},t) 15: end if 16: end while 17: return