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.
- 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$).
- 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.
- 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.
- 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