[Paper] Improving the Convergence Rate of Ray Search Optimization for Query-Efficient Hard-Label Attacks

Source: arXiv - 2512.21241v1

Overview

Hard‑label black‑box adversarial attacks—where an attacker only sees the final class label—are notoriously query‑hungry, limiting their use in real‑world security testing. This paper introduces ARS‑OPT and its surrogate‑enhanced variant PARS‑OPT, momentum‑driven algorithms that dramatically speed up the search for the optimal “ray” direction (the perturbation direction that yields the smallest ℓ₂ distortion) while keeping the number of model queries low.

Key Contributions

• Momentum‑based ray search (ARS‑OPT): Adapts Nesterov’s Accelerated Gradient ideas to hard‑label settings, estimating gradients toward a future ray direction for more precise updates.
• Theoretical convergence analysis: Proves faster and more stable convergence under standard smoothness assumptions, offering formal guarantees missing in many black‑box attack papers.
• Surrogate‑model prior integration (PARS‑OPT): Leverages a lightweight, data‑driven prior to bias gradient estimates, further cutting query counts.
• Comprehensive empirical validation: Outperforms 13 recent hard‑label attack baselines on ImageNet and CIFAR‑10, achieving up to 3×–5× reduction in median queries for comparable ℓ₂ distortion.
• Open‑source implementation: Authors release code and pretrained surrogate models, facilitating reproducibility and downstream research.

Methodology

1. Ray‑based formulation:

   • The attack searches for a scalar λ and a direction v (‖v‖₂ = 1) such that the perturbed image x + λv crosses the decision boundary. The goal is to minimize λ (i.e., the ℓ₂ norm of the perturbation).

2. Momentum‑driven gradient estimation:

   • Traditional Ray Search Optimization (RSO) samples random directions around the current ray and uses binary search to approximate the boundary, which yields noisy gradient estimates.
   • ARS‑OPT keeps a momentum vector mₜ that accumulates past direction updates. At iteration t it predicts a future ray vₜ⁺ = vₜ + β·mₜ (β is a momentum coefficient) and samples perturbations around vₜ⁺ instead of vₜ. This “look‑ahead” reduces variance and aligns updates with the true descent direction.

3. Surrogate‑model prior (PARS‑OPT):

   • A small, inexpensive model (e.g., a shallow CNN trained on the same dataset) provides a prior distribution over promising directions.
   • The prior is combined with the momentum‑adjusted samples via importance weighting, biasing the gradient estimate toward regions where the surrogate predicts higher loss.

4. Optimization loop:

   • For each query‑budget step:
     a. Sample k directions around the look‑ahead ray.
     b. Perform a binary search along each sampled direction to locate the boundary (requires only label checks).
     c. Estimate the gradient from the boundary distances, apply momentum update, and adjust the ray direction.

5. Stopping criteria:

   • The algorithm stops when the ℓ₂ norm of the perturbation falls below a target threshold or when the query budget is exhausted.

Results & Findings

• Query efficiency: Both ARS‑OPT and PARS‑OPT cut the median query count by roughly 70 %–80 % compared to the strongest prior art.
• Stability: The variance of query counts across runs drops dramatically (standard deviation reduced by ~60 %), indicating more predictable attack performance.
• Distortion quality: For a fixed query budget, the ℓ₂ distortion achieved by PARS‑OPT is consistently lower than baselines, confirming that faster convergence does not sacrifice attack strength.
• Ablation: Removing momentum or the surrogate prior each degrades performance, confirming the complementary role of both components.

Practical Implications

• Security testing pipelines: Penetration‑testing tools can now incorporate hard‑label attacks that finish within a few thousand queries—well within rate‑limit thresholds of many commercial APIs (e.g., cloud vision services).
• Adversarial robustness evaluation: Researchers can more efficiently benchmark defenses under realistic query budgets, leading to tighter security guarantees.
• Model hardening: The momentum‑based gradient estimate can be repurposed as a gradient‑free sensitivity metric, helping developers identify vulnerable regions without full white‑box access.
• Resource‑constrained environments: Since PARS‑OPT only needs a lightweight surrogate (often a few MB), it can run on edge devices to assess on‑device model robustness without heavy compute.

Limitations & Future Work

• Assumption of smooth decision boundaries: The convergence proofs rely on locally Lipschitz‑smooth boundaries; highly non‑smooth classifiers may still cause erratic behavior.
• Surrogate quality dependence: While the surrogate model is cheap, a poorly trained prior can misguide the search, leading to slower convergence.
• Extension to ℓ∞ or perceptual metrics: The current formulation focuses on ℓ₂ perturbations; adapting the momentum‑based ray search to other norms or perceptual distances remains open.
• Defensive countermeasures: Future work could explore how gradient‑masking or randomized smoothing defenses affect the momentum dynamics and whether adaptive query strategies can bypass them.

Bottom line: By marrying Nesterov‑style momentum with a data‑driven prior, ARS‑OPT and PARS‑OPT set a new standard for query‑efficient hard‑label attacks, making black‑box adversarial testing more practical for developers and security engineers alike.

Authors

• Xinjie Xu
• Shuyu Cheng
• Dongwei Xu
• Qi Xuan
• Chen Ma

Paper Information

• arXiv ID: 2512.21241v1
• Categories: cs.LG, cs.AI, cs.CR, cs.CV
• Published: December 24, 2025
• PDF: Download PDF