Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers

Abstract

Strong theoretical guarantees of robustness can be given for ensembles of classifiers generated by input randomization. Specifically, an ${\ell }_2$ bounded adversary cannot alter the ensemble prediction generated by an additive isotropic Gaussian noise, where the radius for the adversary depends on both the variance of the distribution as well as the ensemble margin at the point of interest. We build on and considerably expand this work across broad classes of distributions. In particular, we offer adversarial robustness guarantees and associated algorithms for the discrete case where the adversary is ${\ell }_0$ bounded. Moreover, we exemplify how the guarantees can be tightened with specific assumptions about the function class of the classifier such as a decision tree. We empirically illustrate these results with and without functional restrictions across image and molecule datasets.

arXiv commentPublished in Advances in Neural Information Processing Systems (NeurIPS), 2019

References in corpus (15)

• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Certified Adversarial Robustness via Randomized Smoothing
• Certified Defenses against Adversarial Examples
• Efficient Neural Network Robustness Certification with General Activation Functions
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• An approach to reachability analysis for feed-forward ReLU neural networks
• Semidefinite relaxations for certifying robustness to adversarial examples
• Certified Adversarial Robustness with Additive Noise
• Provably Minimally-Distorted Adversarial Examples
• Training verified learners with learned verifiers
• Provable Robustness of ReLU networks via Maximization of Linear Regions
• Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation
• Towards Robust, Locally Linear Deep Networks
• Certified Robustness to Adversarial Word Substitutions

Cited by in corpus (23)

• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks
• On Certifying Robustness against Backdoor Attacks via Randomized Smoothing
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness
• Denoised Smoothing: A Provable Defense for Pretrained Classifiers
• How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications
• PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing
• Deep Partition Aggregation: Provable Defense against General Poisoning Attacks
• Backdoor Attacks to Graph Neural Networks
• Improved, Deterministic Smoothing for L_1 Certified Robustness
• Certifying Confidence via Randomized Smoothing
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More
• Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations
• Provable Robustness Against a Union of ${\ell }_0$ Adversarial Attacks
• Enhancing Certified Robustness via Smoothed Weighted Ensembling
• Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
• CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing
• A Game Theoretic Analysis of Additive Adversarial Attacks and Defenses
• Weight-Covariance Alignment for Adversarially Robust Neural Networks
• ANCER: Anisotropic Certification via Sample-wise Volume Maximization
• Hidden Cost of Randomized Smoothing
• Adversarial Data Encryption