TL;DR
Gradient-guided Random Search (GRS) is a new, highly efficient attack for evaluating pixel-sparse ($\ell_0$) robustness. By treating the attack as a local search that "proposes with the gradient but accepts with the loss," GRS matches or outperforms the current ensemble standard (sparse-AutoAttack) while running up to 5 times faster.
What Problem Does This Paper Address?
Evaluating a model's robustness against a pixel-sparse adversary—one who can change at most $k$ pixels to any value—is notoriously difficult. Unlike $\ell_\infty$ or $\ell_2$ attacks where perturbations are small and continuous, a single pixel change in the $\ell_0$ threat model is "large" and the constraint set is non-convex.
Currently, the field relies on an ensemble called sparse-AutoAttack (sAA). This is because its individual members have distinct failure modes:
- sPGD (Sparse Projected Gradient Descent): Trusts first-order gradient magnitudes, which often collapse when the local curvature is high or the model uses "gradient masking."
- Sparse-RS (Random Search): Ignores gradients entirely, making it robust but incredibly slow to find adversarial examples when the gradient is informative.
The authors ask: Can we build a single attack that combines the best of both worlds—the efficiency of gradients and the reliability of random search?
Methods
The authors frame pixel-sparse attacks as a local search consisting of a proposal distribution (which pixels to change) and an acceptance rule (whether to keep the change). By analyzing Taylor bounds and measuring gradient reliability across various models, they derive five design rules for their new attack, GRS:
- Accept with the loss, never the gradient: Only move to a new state if the actual loss improves. This prevents the attack from being misled by poor first-order predictions.
- Tempered Add Ranking: Use the gradient to rank pixels to add, but sample from this ranking using a "temperature." This avoids over-relying on the very top-ranked pixels, which are often the most non-linear and unreliable.
- Cold Drop Ranking: When deciding which pixels to remove from the current set of $k$ changes, follow the gradient more closely. The authors found that the gradient is a much better predictor of a pixel's current contribution than its potential gain.
- Best-Response Fill: Set the value of a newly added pixel immediately to the corner of the allowed box based on the sign of the gradient.
- Tabu List: Maintain a list of recently proposed pixels and don't re-propose them until a move is accepted, ensuring better coverage of the image.
Datasets
The authors evaluated GRS across a wide range of configurations:
- CIFAR-10: 13 different configurations involving 12 models, including standard ResNets and various robust models from the RobustBench leaderboard ($\ell_\infty$ and $\ell_2$ robust).
- ImageNet: 5 models, including standard ResNet-50 and Vision Transformers (XCiT).
- Benchmarks: Compared against sAA (the ensemble), $\sigma$-zero, $PGD_0$, and GreedyPixel.
Key Insights and Ideas
- The Gradient Magnitude Paradox: On robustly trained models, the pixels with the largest gradient magnitudes are often the most non-linear. Trusting the "top-1" gradient prediction (as sPGD does) is frequently a recipe for failure.
- Asymmetry of Adding vs. Dropping: It is significantly easier for the gradient to tell you which pixel is currently helping the attack (to drop it) than to predict which new pixel will help the most (to add it). GRS exploits this by using a "colder" sampling for dropping pixels.
- Efficiency through "Hedging": By using a tempered proposal, GRS naturally slides between being a gradient attack (when gradients are reliable) and a random search (when gradients are masked), all within a single run.
Key Results
GRS proves to be both stronger and faster than the existing state-of-the-art:
- Performance: On 17 out of 18 main settings, GRS matched or beat the best single member of the sAA ensemble. It was within one point of the full sAA ensemble (or stronger) on 17 settings and significantly stronger on 8.
- Speed: On CIFAR-10, GRS is 3.7 to 5.0 times faster than the sAA ensemble.
- Compute Cost: GRS costs only 3 "units" (forward/backward passes) per iteration, compared to up to 7 units for the full sAA ensemble.
Limitations and Future Work
- White-box Requirement: GRS requires gradients. It cannot replace black-box attacks in scenarios where model weights or gradients are strictly unavailable.
- Piecewise Smoothness: The theoretical bounds assume the loss function is somewhat well-behaved. While it works well on ReLU networks, the authors note that these networks are only piecewise smooth, which can occasionally lead to sub-optimal measurements.
- Future Directions: The authors suggest that the principles of tempered proposals and greedy acceptance could be applied to other non-convex threat models beyond pixel-sparsity.
Summary updated