Source-linked AI summary
RayS: A Ray Searching Method for Hard-label Adversarial Attack
Jinghui Chen, Quanquan Gu
TL;DR
Hard-label attacks are practical but difficult because they expose only prediction labels, and previous methods are limited under the widely used L∞ threat model. RayS reformulates closest-boundary search as discrete ray searching with a fast check, improving attack effectiveness and efficiency while also exposing possible falsely robust models. The paper notes that surrogate attack losses may not faithfully reflect the quality of intermediate examples.
Problem
Hard-label attacks need improved effectiveness and efficiency under the widely used L∞ threat model because they provide only prediction labels.
Method
RayS reformulates closest decision-boundary search as a discrete search over ray directions and uses a fast check to eliminate unnecessary searches.
Results
RayS is more effective and query-efficient than other hard-label attacks and can sanity-check models that may appear falsely robust.
Takeaways & Limitations
RayS can reveal robustness gaps that current white-box and black-box attacks may miss.
Takeaways & Limitations
Surrogate loss functions may not accurately reflect the quality or potential of intermediate examples near the clean input.
Abstract
from arXiv · showhide
Deep neural networks are vulnerable to adversarial attacks. Among different attack settings, the most challenging yet the most practical one is the hard-label setting where the attacker only has access to the hard-label output (prediction label) of the target model. Previous attempts are neither effective enough in terms of attack success rate nor efficient enough in terms of query complexity under the widely used $L_\infty$ norm threat model. In this paper, we present the Ray Searching attack (RayS), which greatly improves the hard-label attack effectiveness as well as efficiency. Unlike previous works, we reformulate the continuous problem of finding the closest decision boundary into a discrete problem that does not require any zeroth-order gradient estimation. In the meantime, all unnecessary searches are eliminated via a fast check step. This significantly reduces the number of queries needed for our hard-label attack. Moreover, interestingly, we found that the proposed RayS attack can also be used as a sanity check for possible "falsely robust" models. On several recently proposed defenses that claim to achieve the state-of-the-art robust accuracy, our attack method demonstrates that the current white-box/black-box attacks could still give a false sense of security and the robust accuracy drop between the most popular PGD attack and RayS attack could be as large as $28\%$. We believe that our proposed RayS attack could help identify falsely robust models that beat most white-box/black-box attacks.
1 INTRODUCTION
Deep neural networks are vulnerable to adversarial examples, motivating an arms race between attacks and defenses. The paper targets hard-label attacks, the most challenging and practical setting, by proposing RayS for effective and efficient L∞ attacks.
- Adversarial examples can cause state-of-the-art classifiers to make wrong predictions through imperceptible, specially designed perturbations.
- Attack settings differ by access: white-box attacks use model details, black-box attacks use soft-label outputs, and hard-label attacks use only prediction labels.
- Hard-label attacks are the most challenging yet practical setting because attackers receive only prediction labels and cannot observe subtle output changes away from decision boundaries.
- Prior hard-label methods mainly target L2, while L∞ threat models are widely used and existing extensions are insufficient for practical scenarios.
- The paper asks whether hard-label attacks can substantially improve over previous methods while providing practical attacks under the widely used L∞ threat model.
- RayS uses only hard-label outputs, reformulates closest-boundary search as a discrete ray-direction problem, and skips unnecessary searches with a fast check.
2 RELATED WORK
The related work spans white-box, black-box, and hard-label adversarial attacks. Prior methods use gradients, transferred or estimated information, random walks, transformations, or zeroth-order optimization to generate adversarial examples.
- White-box attacks: White-box work includes L-BFGS, FGSM, PGD, JSMA, DeepFool, and CW attacks using model information or gradient-based optimization.
- These approaches collectively frame adversarial generation around exploiting model information, estimating gradients, or searching near decision boundaries.
- Black-box attacks: Black-box attacks operate with limited logit information, using transferred gradients or zeroth-order methods instead of direct model gradients.
- Hard-label attacks: Hard-label research includes random walks near decision boundaries, hard-to-soft-label transformations, and zeroth-order optimization of directions toward short L2 boundary distances.
3 THE PROPOSED METHOD
RayS replaces gradient-based continuous search for the nearest decision boundary with discrete ray-direction search, using fast checks and hierarchical block updates to reduce unnecessary queries.
- Motivation: The hard-label restriction makes estimating decision-boundary gradients costly because radius evaluation requires binary search and finite-difference gradients require repeated evaluations.These constraints motivate direct search without gradient estimation.
- Discrete Ray Search: RayS restricts search directions from R^d to {−1, 1}^d, yielding 2^d possible directions that can be searched directly.The discrete formulation makes finite-query direct search possible.
- Naive Ray Search: The naive attack greedily flips one coordinate sign at a time and updates the best direction and radius when a lower decision-boundary radius is found.With enough queries, the returned direction is a local optimum under one-coordinate changes.
- Decision Boundary Radius Search: DBR-Search normalizes a candidate direction, performs a fast validity check at the current best radius, and binary-searches only when the direction may improve the result.The fast check eliminates searches whose radius cannot beat the current best.
- Hierarchical Search: The hierarchical variant flips signs in blocks to exploit spatial correlation, repeatedly refines block size, and eventually reduces to the naive search when blocks reach size 1.All experiments use the hierarchical algorithm, which empirically improves search efficiency.
- Design Characteristics: RayS has no hyperparameters beyond the maximum query count, unlike typical white-box and zeroth-order black-box attacks that require tuning several hyperparameters.The query budget is usually predefined by the problem setting.
4 EXPERIMENTS
The experiments compare RayS with hard-label, black-box, and white-box attacks across naturally trained and robust models. RayS is evaluated for attack effectiveness, query efficiency, and its ability to expose models that appear robust under conventional attacks.
- Naturally trained models: Experiments evaluate RayS against hard-label baselines on MNIST, CIFAR-10, and ImageNet, using naturally trained models and a maximum of 10000 queries.The hard-label baselines are OPT, SignOPT, and HSJA.
- Naturally trained models: RayS compares favorably with other hard-label attacks in attack performance and query efficiency under the L∞ threat model.The experiments use attack success and query-count comparisons across the three datasets.
- Robust models: The robust-model evaluation uses five CIFAR-10 defenses with WideResNet models, 1000 test images, and a maximum of 40000 queries.Comparisons include white-box PGD and CW attacks plus black-box SignHunter and Square attacks.
- Evaluation metrics: ADBD measures the average L∞ distance from test examples to their nearest decision boundaries and is applicable to hard-label attacks, unlike standard bounded-distortion reporting.The paper notes that ADBD captures information lost when hard-label attacks are considered only within a fixed perturbation radius.
- Robust models: Compared with other hard-label baselines, RayS improves robust accuracy by over 20% and reduces average decision boundary distance by 30%.These comparisons are reported for the selected robust models under the L∞ threat model.
- Robust models: On Sensible Adversarial Training, RayS yields 42.5% robust accuracy, 20% below PGD and 15% below CW, while RayS identifies weaker apparent robustness in several defenses.Across the five models, TRADES and Adversarial Training remain most robust under RayS; the reported metrics stabilize after around 10000 iterations.
5 DISCUSSIONS AND CONCLUSIONS
RayS improves hard-label attack effectiveness and efficiency by directly searching discrete ray directions with a fast check step. The discussion also explains why surrogate loss functions can misrepresent intermediate adversarial examples, motivating RayS as a sanity check for possibly falsely robust models.
- RayS uses hard-label outputs and outperforms other hard-label attacks in attack success rate and query efficiency.
- RayS can serve as a sanity check for models that appear robust to existing white-box and black-box attacks.
- Discrete boundary search and a fast check step improve effectiveness and eliminate unnecessary searches under the L∞ threat model.
- Attack performances often correlate with surrogate loss choices, with CrossEntropy-based and CW-loss-based attacks showing similar behavior in many cases.
- CrossEntropy may assign the same loss to intermediate examples whose potential to become valid adversarial examples differs substantially.