RayS: A Ray Searching Method for Hard-label Adversarial Attack

Jinghui Chen, Quanquan Gu

TL;DR

RayS (Ray Searching) is a highly efficient "hard-label" adversarial attack that finds vulnerabilities in neural networks by searching along discrete ray directions rather than estimating noisy gradients. It is significantly faster than previous methods and serves as a powerful "sanity check" to expose models that appear robust to standard attacks but are actually fragile.

What Problem Does This Paper Address?

Adversarial attacks typically fall into three categories based on how much information the attacker has: white-box (full access to the model), black-box (access to prediction probabilities), and hard-label (access only to the final predicted class).

Hard-label attacks are the most realistic and challenging. Because you only get a "Yes/No" answer from the model (e.g., "Is this a cat?"), you can't easily calculate gradients to find the shortest path to a misclassification. Previous hard-label attacks tried to estimate these gradients using "zeroth-order optimization," which is incredibly query-intensive and often fails under the popular $L_\infty$ norm (where we limit the maximum change to any single pixel).

The authors identify a gap: existing hard-label attacks are either too slow or simply ineffective at breaking models defended against $L_\infty$ perturbations.

Methods

The core innovation of RayS is reformulating a continuous optimization problem into a discrete search problem.

  1. Ray Searching: Instead of wandering aimlessly around the decision boundary, RayS "shoots" rays from the original image toward the vertices of the $L_\infty$ perturbation hypercube (directions where every pixel is changed by either $+\epsilon$ or $-\epsilon$).
  2. Discrete Directional Search: It iteratively flips the signs of dimensions in the search direction to find a better "ray" that hits the decision boundary closer to the original image.
  3. Fast Check Step: Before performing an expensive binary search to find the exact boundary on a new ray, RayS performs a "fast check." If the model still predicts the correct label at the current best distance along the new ray, the algorithm immediately skips it, saving thousands of queries.
  4. Hierarchical Search: To exploit the fact that nearby pixels in images are often correlated, the algorithm starts by perturbing large blocks of pixels and gradually refines the search down to individual pixels.

Datasets

The authors evaluated RayS on three standard computer vision benchmarks:

  • MNIST: Handwritten digits.
  • CIFAR-10: Small color images of 10 different classes.
  • ImageNet: Large-scale, high-resolution images (specifically ResNet-50 and Inception V3 models).

They also tested the attack against several state-of-the-art "robust" models trained using techniques like Adversarial Training, TRADES, and Feature Scattering.

Key Insights and Ideas

  • The $L_\infty$ Geometry Advantage: The authors realized that the most effective $L_\infty$ attacks usually end up at the "corners" of the allowed perturbation space. By restricting their search to these discrete directions, they bypass the need for noisy gradient estimations entirely.
  • Exposing "False Robustness": One of the most striking findings is that some models that claim high "robust accuracy" against standard white-box attacks (like PGD) are actually vulnerable. These models often have "obfuscated gradients"—they make their gradients messy to fool gradient-based attacks, but the underlying decision boundary is still close. Because RayS doesn't use gradients, it cuts right through this "security by obscurity."
  • Hyperparameter-Free: Unlike many optimization-based attacks that require tuning step sizes or smoothing constants, RayS is remarkably stable and easy to deploy.

Key Results

  • Efficiency: On MNIST, RayS achieved a 100% attack success rate with a median of only 47 queries, compared to 154 for the previous state-of-the-art (HSJA) and over 2,600 for others.
  • Effectiveness: On ImageNet (Inception V3), RayS achieved a 98.9% success rate, while previous hard-label methods like HSJA and OPT struggled to stay above 25% within the same query budget.
  • The "Sanity Check": When testing "robust" models, RayS dropped the robust accuracy of some defenses significantly. For example, on the "Feature Scattering" defense, RayS reduced the robust accuracy from 70.4% (under PGD) to 44.5%. This 25%+ drop indicates that those models were not as robust as previously believed.

Limitations and Future Work

  • Norm Specificity: RayS is specifically optimized for the $L_\infty$ norm. While the logic of ray searching could be adapted, it might not be as naturally efficient for $L_2$ or $L_0$ attacks where the "corners" of the search space aren't as dominant.
  • Query Budget: While much faster than predecessors, it still requires hundreds or thousands of queries for complex images. In a real-world API-throttled environment, even fewer queries would be ideal.
  • Future Defense: The authors suggest that RayS should be used as a standard evaluation tool for any new defense to ensure the claimed robustness isn't just a result of gradient masking.

Summary updated

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.
BibTeX
@inproceedings{chen2020rays,
  author = {Jinghui Chen and Quanquan Gu},
  title = {{RayS: A Ray Searching Method for Hard-label Adversarial Attack}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  url = {https://openreview.net/forum?id=5wQFxt0bXu},
}

Loading related content...

Figure