Abstract
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.
Introduction
Adversarial attacks are essential tools for evaluating the robustness of deep neural networks. These attacks are generally categorized by the level of information available to the attacker: white-box (full model access), black-box (access to output probabilities), and hard-label (access only to the final predicted class).
Hard-label attacks represent the most realistic scenario but are inherently difficult because the discrete nature of the output prevents direct gradient computation. Previous methods often relied on zeroth-order optimization to estimate gradients, a process that is computationally expensive and frequently fails under the $L_\infty$ norm constraint. RayS addresses these limitations by reformulating the attack as a discrete search problem, significantly enhancing both efficiency and success rates.
Methodology
The core innovation of RayS is the transition from continuous gradient estimation to a discrete search along specific directions, or "rays."
- Ray Searching: Instead of estimating gradients, RayS explores directions from the original image toward the vertices of the $L_\infty$ perturbation hypercube. This targets the "corners" of the allowed space where $L_\infty$ attacks are most effective.
- Discrete Directional Search: The algorithm iteratively modifies the search direction by flipping signs of dimensions to find a ray that intersects the decision boundary as close to the original image as possible.
- Fast Check Step: To minimize queries, RayS employs a "fast check." If the model still correctly classifies the image at the current best distance along a new ray, the algorithm skips the expensive binary search for that direction.
- Hierarchical Search: RayS leverages spatial correlation in images by initially perturbing large blocks of pixels and progressively refining the search to individual pixels.
Experimental Evaluation
The authors evaluated RayS against state-of-the-art hard-label attacks (OPT, SignOPT, HSJA) across several benchmarks, including MNIST, CIFAR-10, and ImageNet (ResNet-50 and Inception V3).
Performance and Efficiency
RayS demonstrates superior performance in both success rate and query efficiency. For instance, on MNIST, RayS achieved a 100% success rate with a median of only 47 queries, significantly lower than HSJA's 154 queries. On high-resolution ImageNet models like Inception V3, RayS maintained a 98.9% success rate, while competing methods struggled to exceed 25% within the same query budget.
Exposing False Robustness
A significant finding of this work is the ability of RayS to act as a "sanity check" for robust models. Some defenses employ "gradient masking" or "obfuscated gradients" to fool gradient-based attacks like PGD, creating a false sense of security. Since RayS is gradient-free, it can bypass these defenses. In tests against the "Feature Scattering" defense, RayS reduced the robust accuracy from a reported 70.4% to 44.5%, a drop of over 25%.
Discussion and Conclusion
RayS provides a powerful and efficient tool for hard-label adversarial attacks, particularly under the $L_\infty$ norm. By avoiding noisy gradient estimations and utilizing a fast check step, it achieves unprecedented query efficiency. Furthermore, its ability to expose falsely robust models makes it an essential evaluation metric for future defensive techniques. While currently optimized for $L_\infty$, future work could explore adapting the ray searching logic to other norms like $L_2$.
Summary updated