Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations

Abstract

Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. ${\ell }_0$-norm adversarial perturbation characterizes an attack that arbitrarily modifies some features of an input such that a classifier makes an incorrect prediction for the perturbed input. ${\ell }_0$-norm adversarial perturbation is easy to interpret and can be implemented in the physical world. Therefore, certifying robustness of top-$k$ predictions against ${\ell }_0$-norm adversarial perturbation is important. However, existing studies either focused on certifying ${\ell }_0$-norm robustness of top-$1$ predictions or ${\ell }_2$-norm robustness of top-$k$ predictions. In this work, we aim to bridge the gap. Our approach is based on randomized smoothing, which builds a provably robust classifier from an arbitrary classifier via randomizing an input. Our major theoretical contribution is an almost tight ${\ell }_0$-norm certified robustness guarantee for top-$k$ predictions. We empirically evaluate our method on CIFAR10 and ImageNet. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2\% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.

Published as a conference paper at ICLR 2022

References in corpus (9)

• Certified Adversarial Robustness via Randomized Smoothing
• An approach to reachability analysis for feed-forward ReLU neural networks
• On Detecting Adversarial Perturbations
• MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
• On Certifying Robustness against Backdoor Attacks via Randomized Smoothing
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness
• Theoretical evidence for adversarial robustness through randomization
• Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework

Cited by in corpus (3)

• Multi-SpacePhish: Extending the Evasion-space of Adversarial Attacks against Phishing Website Detectors using Machine Learning
• PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier
• 10 Security and Privacy Problems in Large Foundation Models