Provable defenses against adversarial examples via the convex outer adversarial polytope

2017/11/02 by Eric Wong, J. Zico Kolter, Wong, Eric +1 · 30 citations
Computer Science · #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1711.00851

openalex publication_date 2017/11/02 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28

Abstract

We propose a method to learn deep ReLU-based classifiers that are provably robust against norm-bounded adversarial perturbations on the training data. For previously unseen examples, the approach is guaranteed to detect all adversarial examples, though it may flag some non-adversarial examples as well. The basic idea is to consider a convex outer approximation of the set of activations reachable through a norm-bounded perturbation, and we develop a robust optimization procedure that minimizes the worst case loss over this outer region (via a linear program). Crucially, we show that the dual problem to this linear program can be represented itself as a deep network similar to the backpropagation network, leading to very efficient optimization approaches that produce guaranteed bounds on the robust loss. The end result is that by executing a few more forward and backward passes through a slightly modified version of the original network (though possibly with much larger batch sizes), we can learn a classifier that is provably robust to any norm-bounded adversarial attack. We illustrate the approach on a number of tasks to train classifiers with robust adversarial guarantees (e.g. for MNIST, we produce a convolutional classifier that provably has less than 5.8% test error for any adversarial attack with bounded ℓ_∞ norm less than ε= 0.1), and code for all experiments in the paper is available at https://github.com/locuslab/convex_adversarial.

Cited by

• Exact and Asymptotically Complete Robust Verifications of Neural Networks via Ising Solvers
• TrajSyn: Privacy-Preserving Dataset Distillation from Federated Model Trajectories for Server-Side Adversarial Training
• Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification
• Dual Randomized Smoothing: Beyond Global Noise Variance
• Faster Verified Explanations for Neural Networks
• Towards Trustworthy Wi-Fi CSI-based Sensing: Systematic Evaluation of Adversarial Robustness
• Lipschitz-aware Linearity Grafting for Certified Robustness
• Towards Strong Certified Defense with Universal Asymmetric Randomization
• Adversarial Attacks Leverage Interference Between Features in Superposition
• Tight Robustness Certificates and Wasserstein Distributional Attacks for Deep Neural Networks
• On the Adversarial Robustness of Learning-based Conformal Novelty Detection
• Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier
• Optimal Robust Recourse with L^p-Bounded Model Change
• Lipschitz-Based Robustness Certification for Recurrent Neural Networks via Convex Relaxation
• Randomized Smoothing Meets Vision-Language Models
• Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware\n Randomized Smoothing for Graphs, Images and More
• Robustifying Diffusion-Denoised Smoothing Against Covariate Shift
• Randomized Smoothing of All Shapes and Sizes
• Verifying Individual Fairness in Machine Learning Models
• Theoretically Principled Trade-off between Robustness and Accuracy
• Exploiting Excessive Invariance caused by Norm-Bounded Adversarial\n Robustness
• A Survey of Black-Box Adversarial Attacks on Computer Vision Models
• Improved Image Wasserstein Attacks and Defenses
• Adversarially Robust Learning with Unknown Perturbation Sets
• Adversarial Examples Are Not Bugs, They Are Features
• Towards Compact and Robust Deep Neural Networks
• Understanding Adversarial Robustness: The Trade-off between Minimum and Average Margin
• A Sequential Framework Towards an Exact SDP Verification of Neural Networks
• Towards neural networks that provably know when they don't know

Related

• Scaling provable adversarial defenses
• Opportunities and Challenges in Deep Learning Adversarial Robustness: A Survey
• Robustness Certificates Against Adversarial Examples for ReLU Networks
• Robustness Against Adversarial Attacks via Learning Confined Adversarial Polytopes
• Adversarial Training of Two-Layer Polynomial and ReLU Activation Networks via Convex Optimization