Random Smoothing Might be Unable to Certify ${\ell }_{\infty }$ Robustness for High-Dimensional Images

Abstract

We show a hardness result for random smoothing to achieve certified adversarial robustness against attacks in the ${\ell }_p$ ball of radius $\epsilon$ when $p>2$. Although random smoothing has been well understood for the ${\ell }_2$ case using the Gaussian distribution, much remains unknown concerning the existence of a noise distribution that works for the case of $p>2$. This has been posed as an open problem by Cohen et al. (2019) and includes many significant paradigms such as the ${\ell }_{\infty }$ threat model. In this work, we show that any noise distribution $\mathcal{D}$ over ${\mathbb{R}}^d$ that provides ${\ell }_p$ robustness for all base classifiers with $p>2$ must satisfy $\mathbb{E}{\eta }_i^2=\Omega (d^{1-2/p}{\epsilon }^2(1-\delta )/{\delta }^2)$ for 99% of the features (pixels) of vector $\eta \sim \mathcal{D}$, where $\epsilon$ is the robust radius and $\delta$ is the score gap between the highest-scored class and the runner-up. Therefore, for high-dimensional images with pixel values bounded in $[0,255]$, the required noise will eventually dominate the useful information in the images, leading to trivial smoothed classifiers.

20 pages, 2 figures; Code is available at https://github.com/hongyanz/TRADES-smoothing

References in corpus (9)

• Certified Adversarial Robustness via Randomized Smoothing
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• Semidefinite relaxations for certifying robustness to adversarial examples
• Certified Adversarial Robustness with Additive Noise
• Unrestricted Adversarial Examples
• MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
• Wasserstein Adversarial Examples via Projected Sinkhorn Iterations
• Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing
• Design and Interpretation of Universal Adversarial Patches in Face Detection

Cited by in corpus (10)

• A Closer Look at Accuracy vs. Robustness
• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework
• Deep Partition Aggregation: Provable Defense against General Poisoning Attacks
• Adversarial robustness via robust low rank representations
• Higher-Order Certification for Randomized Smoothing
• Enhancing Certified Robustness via Smoothed Weighted Ensembling
• Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons
• Smoothed Inference for Adversarially-Trained Models
• Deterministic Certification to Adversarial Attacks via Bernstein Polynomial Approximation