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

Technical Summary: Opportunistic Target Selection for Query-Efficient Black-Box Adversarial Attacks

1. Problem Definition: Class Drift in Untargeted Attacks

Standard untargeted black-box adversarial attacks aim to minimize the model's confidence in the ground-truth class ($y$) without specifying a target class. Common implementations include minimizing the probability $P(y|x')$ (e.g., SimBA) or minimizing cross-entropy loss. The authors identify a critical inefficiency in this approach termed class drift.

In untargeted attacks, the "freed" probability mass is not directed toward a specific adversarial class. Instead, the perturbation executes a random walk through the latent feature space, traversing multiple class basins opportunistically. This lack of directional commitment results in wasted queries, particularly on difficult models where the perturbation must traverse many basins before settling on a decision boundary. While targeted attacks eliminate drift by definition, they require a priori knowledge of the target class, which is generally unavailable in black-box settings. Margin-based losses offer a partial solution by implicitly tracking the nearest decision boundary, but many popular score-based attacks (like SimBA or Square Attack with cross-entropy) do not support them or operate on raw probabilities where margin logic is not directly applicable.

2. Methodology: Opportunistic Target Selection (OTS)

The paper introduces Opportunistic Target Selection (OTS), a lightweight wrapper algorithm that converts an untargeted attack into a targeted one early in its trajectory without requiring gradient access or prior target knowledge.

Core Mechanism:
OTS operates in two phases:

1. Exploration Phase: The attack runs in standard untargeted mode for a short prefix of $T$ iterations (or until a stability condition is met). During this time, the algorithm observes the class rankings of the perturbed input.
2. Exploitation Phase: Once a "leading" non-true class (the class with the highest probability among $k \neq y$) is identified and stabilized, the attack locks onto this class as a fixed target. The objective switches to maximizing the probability of this specific target class ($P(t|x')$) for the remainder of the query budget.

Algorithmic Variants:

• Fixed-Iteration Switch: The attack switches targets after a fixed number of iterations $T$. Ablation studies show that any $T \in \{5, \dots, 500\}$ yields statistically indistinguishable results, as class rankings stabilize rapidly for drift-prone attacks.
• Rank-Stability Variant: A counter tracks the leading non-true class, switching only after the same class leads for $S$ consecutive accepted steps. While included for completeness, experiments show this offers no measurable advantage over the fixed switch.

Integration:
OTS is applied to three distinct attack families:

• SimBA: Switches from minimizing $P(y|x')$ to maximizing $P(t|x')$.
• Square Attack (Cross-Entropy): Deliberately uses cross-entropy loss (which induces drift) rather than the default margin loss to isolate OTS's effect.
• Bandits: A gradient-estimation attack that inherently possesses directionality.

3. Key Contributions

The paper makes three primary contributions:

1. OTS as a Margin-Loss Surrogate: The authors demonstrate that OTS approximates the "competitor term" of margin loss ($\max_{k \neq y} f_k(x')$) for attacks that lack implicit target tracking. By locking onto the leading non-true class early, OTS provides the directional commitment that margin loss offers, but without requiring access to logit values or dynamic re-calculation of the margin at every step.
2. Empirical Validation: Extensive experiments across five ImageNet classifiers (AlexNet, ResNet-18, VGG-16, ResNet-50, ViT-B/16) and three attack methods (4,500 runs) show that OTS achieves near-oracle efficiency. The authors highlight that random target selection is catastrophic, proving that the opportunistic selection of the currently leading class is the critical factor.
3. Characterization of Targeting Neutrality: The study identifies that OTS provides no benefit on adversarially-trained models. The authors attribute this to a bimodal difficulty distribution in robust models, where images are either easily attacked or completely infeasible, eliminating the "medium-difficulty" regime where directional commitment provides value.

4. Experimental Results

Performance on Standard Models:

• Success Rate: On ResNet-50, OTS increased the success rate of SimBA from 43% to 70% (+27 percentage points) and Square Attack (CE) from 81% to 94% (+13 percentage points). OTS performance closely tracks the "oracle" performance (where the target is chosen post-hoc based on the untargeted trajectory).
• Query Efficiency: OTS reduced the censored-mean iterations (penalizing failures) by 43% for SimBA and 29.5% for Square Attack on ResNet-50.
• Attack Specificity:
  • Beneficial: Attacks relying on probability minimization or cross-entropy loss (SimBA, Square Attack CE) show significant gains.
  • Redundant/Harmful: Gradient-estimation attacks (Bandits) and attacks using margin loss show no benefit or slight degradation. This confirms that OTS is only necessary when the attack lacks built-in directionality.

Perturbation Alignment:
Analysis of cosine similarity between perturbations and the oracle direction reveals that untargeted perturbations drift significantly (terminal similarity $\approx 0.17$), whereas OTS perturbations rapidly align with the oracle direction after the switch (similarity $\approx 0.86$).

Robust Models:
On adversarially-trained models (Salman2020Do R18/R50), OTS showed no statistically significant improvement over untargeted baselines. The authors interpret this as a consequence of the difficulty distribution: robust models compress the difficulty spectrum into two extremes (very easy or impossible), removing the "medium" difficulty zone where locking onto a specific target is advantageous.

5. Significance and Claims

The paper positions OTS not as a new attack algorithm, but as a universal wrapper that enhances query efficiency for specific classes of black-box attacks. Its significance lies in:

• Bridging the Gap: It provides the efficiency benefits of targeted attacks (directional commitment) without the requirement of a priori target knowledge.
• Theoretical Insight: It clarifies that the information required to select an effective target is latent in the attack's trajectory within the first few iterations.
• Practical Utility: It offers a simple, low-overhead modification (switching the objective function) that yields near-oracle performance on standard models, particularly for attacks that suffer from class drift.

The authors remain modest regarding generalizability, noting that the benefits may be reduced in low-class-count settings (e.g., CIFAR-10) where probability mass has less room to scatter, and that the behavior on robust models suggests targeting is ineffective when the difficulty distribution is bimodal.