Semidefinite relaxations for certifying robustness to adversarial examples

Abstract

Despite their impressive performance on diverse tasks, neural networks fail catastrophically in the presence of adversarial inputs---imperceptibly but adversarially perturbed versions of natural inputs. We have witnessed an arms race between defenders who attempt to train robust networks and attackers who try to construct adversarial examples. One promise of ending the arms race is developing certified defenses, ones which are provably robust against all attackers in some family. These certified defenses are based on convex relaxations which construct an upper bound on the worst case loss over all attackers in the family. Previous relaxations are loose on networks that are not trained against the respective relaxation. In this paper, we propose a new semidefinite relaxation for certifying robustness that applies to arbitrary ReLU networks. We show that our proposed relaxation is tighter than previous relaxations and produces meaningful robustness guarantees on three different "foreign networks" whose training objectives are agnostic to our proposed relaxation.

To appear at NIPS 2018

Cited by in corpus (98)

• Theoretically Principled Trade-off between Robustness and Accuracy
• Fast is better than free: Revisiting adversarial training
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• Rademacher Complexity for Adversarially Robust Generalization
• Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
• Unlabeled Data Improves Adversarial Robustness
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers
• Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers
• Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks
• Overfitting in adversarially robust deep learning
• The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
• Towards Stable and Efficient Training of Verifiably Robust Neural Networks
• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness
• Denoised Smoothing: A Provable Defense for Pretrained Classifiers
• Robustness Verification for Transformers
• Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing
• Randomized Smoothing of All Shapes and Sizes
• Efficient Exact Verification of Binarized Neural Networks
• Lipschitz constant estimation of Neural Networks via sparse polynomial optimization
• Learning Security Classifiers with Verified Global Robustness Properties
• Exactly Computing the Local Lipschitz Constant of ReLU Networks
• Towards Compact and Robust Deep Neural Networks
• Benchmarking Adversarial Robustness
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework
• Dual Manifold Adversarial Robustness: Defense against Lp and non-Lp Adversarial Attacks
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• Verifying Individual Fairness in Machine Learning Models
• Semialgebraic Optimization for Lipschitz Constants of ReLU Networks
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition
• Random Smoothing Might be Unable to Certify ${\ell }_{\infty }$ Robustness for High-Dimensional Images
• Resilient Cyberphysical Systems and their Application Drivers: A Technology Roadmap
• ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies
• Domain adaptation under structural causal models
• Learning Lyapunov Functions for Piecewise Affine Systems with Neural Network Controllers
• Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming
• Towards Verifying Robustness of Neural Networks Against Semantic Perturbations
• Utility is in the Eye of the User: A Critique of NLP Leaderboards
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks
• Defending Against Physically Realizable Attacks on Image Classification
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Enhancing Certifiable Robustness via a Deep Model Ensemble
• Incorporating Unlabeled Data into Distributionally Robust Learning
• Calibrated Surrogate Losses for Adversarially Robust Classification
• On Certifying Non-uniform Bound against Adversarial Attacks
• Improved, Deterministic Smoothing for L_1 Certified Robustness
• Certifying Confidence via Randomized Smoothing
• Fine-grained Synthesis of Unrestricted Adversarial Examples
• Adversarial Feature Augmentation and Normalization for Visual Recognition
• Lagrangian Decomposition for Neural Network Verification
• Jacobian Adversarially Regularized Networks for Robustness
• Understanding Adversarial Robustness: The Trade-off between Minimum and Average Margin
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More
• Second-Order Provable Defenses against Adversarial Attacks
• TSS: Transformation-Specific Smoothing for Robustness Certification
• Fast Certified Robust Training with Short Warmup
• Reach-SDP: Reachability Analysis of Closed-Loop Systems with Neural Network Controllers via Semidefinite Programming
• Detection Defense Against Adversarial Attacks with Saliency Map
• On Training Robust PDF Malware Classifiers
• Adversarial robustness via robust low rank representations
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations
• Towards the Quantification of Safety Risks in Deep Neural Networks
• Enhancing Certified Robustness via Smoothed Weighted Ensembling
• A Comprehensive Evaluation Framework for Deep Model Robustness
• Scaling the Convex Barrier with Sparse Dual Algorithms
• Certifying Incremental Quadratic Constraints for Neural Networks via Convex Optimization
• $n$-ML: Mitigating Adversarial Examples via Ensembles of Topologically Manipulated Classifiers
• Adversarial Robustness with Non-uniform Perturbations
• Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
• Robust Adversarial Learning via Sparsifying Front Ends
• Detection as Regression: Certified Object Detection by Median Smoothing
• Semialgebraic Representation of Monotone Deep Equilibrium Models and Applications to Certification
• Tight Second-Order Certificates for Randomized Smoothing
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• Policy Smoothing for Provably Robust Reinforcement Learning
• Auditing AI models for Verified Deployment under Semantic Specifications
• Certifying Neural Network Robustness to Random Input Noise from Samples
• Multi-stage Optimization based Adversarial Training
• Can Perceptual Guidance Lead to Semantically Explainable Adversarial Perturbations?
• Universal Approximation with Certified Networks
• What it Thinks is Important is Important: Robustness Transfers through Input Gradients
• ANCER: Anisotropic Certification via Sample-wise Volume Maximization
• Resilience from Diversity: Population-based approach to harden models against adversarial attacks
• A Sublevel Moment-SOS Hierarchy for Polynomial Optimization
• Domain Invariant Adversarial Learning
• Provably robust deep generative models
• A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
• ε-weakened Robustness of Deep Neural Networks
• Adversarial Robustness Across Representation Spaces
• Robust error bounds for quantised and pruned neural networks
• Training Provably Robust Models by Polyhedral Envelope Regularization
• Deterministic Certification to Adversarial Attacks via Bernstein Polynomial Approximation
• Robust Machine Learning via Privacy/Rate-Distortion Theory
• Skew Orthogonal Convolutions
• Regularized Training and Tight Certification for Randomized Smoothed Classifier with Provable Robustness
• A Sequential Framework Towards an Exact SDP Verification of Neural Networks
• Trace-Norm Adversarial Examples