Provable defenses against adversarial examples via the convex outer adversarial polytope

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 ${\ell }_{\infty }$ norm less than $\epsilon =0.1$), and code for all experiments in the paper is available at https://github.com/locuslab/convex_adversarial.

ICML final version

Cited by in corpus (307)

• Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning
• Theoretically Principled Trade-off between Robustness and Accuracy
• Fast is better than free: Revisiting adversarial training
• Adversarial Examples Are Not Bugs, They Are Features
• Robustness May Be at Odds with Accuracy
• Efficient Neural Network Robustness Certification with General Activation Functions
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• A General Framework for Adversarial Examples with Objectives
• Testing Deep Neural Networks
• Quantum noise protects quantum classifiers against adversaries
• Training robust neural networks using Lipschitz bounds
• Adversarial Training and Robustness for Multiple Perturbations
• A Game-Based Approximate Verification of Deep Neural Networks with Provable Guarantees
• Rademacher Complexity for Adversarially Robust Generalization
• RobustBench: a standardized adversarial robustness benchmark
• Do Adversarially Robust ImageNet Models Transfer Better?
• Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability
• Rethinking Softmax Cross-Entropy Loss for Adversarial Robustness
• Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
• Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
• Attacks Which Do Not Kill Training Make Adversarial Learning Stronger
• Improving the Generalization of Adversarial Training with Domain Adaptation
• Certified Defenses for Adversarial Patches
• Accurate, reliable and fast robustness evaluation
• Gotta Catch 'Em All: Using Honeypots to Catch Adversarial Attacks on Neural Networks
• Adversarial Robustness Against the Union of Multiple Perturbation Models
• Malware Makeover: Breaking ML-based Static Analysis by Modifying Executable Bytes
• Unlabeled Data Improves Adversarial Robustness
• MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
• On the (In)fidelity and Sensitivity for Explanations
• Improving the Transferability of Adversarial Examples with Resized-Diverse-Inputs, Diversity-Ensemble and Region Fitting
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers
• The Limitations of Adversarial Training and the Blind-Spot Attack
• Security and Privacy Issues in Deep Learning
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Fundamental Tradeoffs between Invariance and Sensitivity to Adversarial Perturbations
• A Survey of Safety and Trustworthiness of Deep Neural Networks: Verification, Testing, Adversarial Attack and Defence, and Interpretability
• Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspective
• Reachability Analysis of Neural Feedback Loops
• Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• Robust Reinforcement Learning on State Observations with Learned Optimal Adversary
• Diversity can be Transferred: Output Diversification for White- and Black-box Attacks
• Adversarial Examples - A Complete Characterisation of the Phenomenon
• NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks
• The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
• Understanding and Improving Fast Adversarial Training
• Indirect Adversarial Attacks via Poisoning Neighbors for Graph Convolutional Networks
• Branch and Bound for Piecewise Linear Neural Network Verification
• Arms Race in Adversarial Malware Detection: A Survey
• Towards Stable and Efficient Training of Verifiably Robust Neural Networks
• Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations
• Robustness Verification of Tree-based Models
• PatchGuard: A Provably Robust Defense against Adversarial Patches via Small Receptive Fields and Masking
• Denoised Smoothing: A Provable Defense for Pretrained Classifiers
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness
• On the Loss Landscape of Adversarial Training: Identifying Challenges and How to Overcome Them
• Robustness Verification for Transformers
• DNNV: A Framework for Deep Neural Network Verification
• Algorithms for Verifying Deep Neural Networks
• Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing
• Adversarial Distributional Training for Robust Deep Learning
• Geometry-aware Instance-reweighted Adversarial Training
• HYDRA: Pruning Adversarially Robust Neural Networks
• Curriculum Adversarial Training
• Randomized Smoothing of All Shapes and Sizes
• Globally-Robust Neural Networks
• Lipschitz constant estimation of Neural Networks via sparse polynomial optimization
• Opportunities and Challenges in Deep Learning Adversarial Robustness: A Survey
• Adversarial Robustness via Fisher-Rao Regularization
• Increasing the Confidence of Deep Neural Networks by Coverage Analysis
• Learning Security Classifiers with Verified Global Robustness Properties
• Interpolated Adversarial Training: Achieving Robust Neural Networks without Sacrificing Too Much Accuracy
• ADef: an Iterative Algorithm to Construct Adversarial Deformations
• Sensitivity analysis of Wasserstein distributionally robust optimization problems
• Harnessing the Vulnerability of Latent Layers in Adversarially Trained Models
• To be Robust or to be Fair: Towards Fairness in Adversarial Training
• Adversarial Risk Bounds via Function Transformation
• Adversarial Learning in Statistical Classification: A Comprehensive Review of Defenses Against Attacks
• Efficient Certified Defenses Against Patch Attacks on Image Classifiers
• A Survey of Black-Box Adversarial Attacks on Computer Vision Models
• Morphence: Moving Target Defense Against Adversarial Examples
• Towards Compact and Robust Deep Neural Networks
• Dual Manifold Adversarial Robustness: Defense against Lp and non-Lp Adversarial Attacks
• Exploiting Excessive Invariance caused by Norm-Bounded Adversarial Robustness
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier
• Improving Robustness of ML Classifiers against Realizable Evasion Attacks Using Conserved Features
• Adversarial Attacks, Regression, and Numerical Stability Regularization
• On Fast Adversarial Robustness Adaptation in Model-Agnostic Meta-Learning
• Verifying Individual Fairness in Machine Learning Models
• Improving adversarial robustness of deep neural networks by using semantic information
• Semialgebraic Optimization for Lipschitz Constants of ReLU Networks
• Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation
• PAC-learning in the presence of evasion adversaries
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition
• Adversarial Training with Voronoi Constraints
• Wasserstein Smoothing: Certified Robustness against Wasserstein Adversarial Attacks
• A Formalization of Robustness for Deep Neural Networks
• Towards Robust, Locally Linear Deep Networks
• Physically Realizable Adversarial Examples for LiDAR Object Detection
• ML-LOO: Detecting Adversarial Examples with Feature Attribution
• ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies
• Robust Deep Reinforcement Learning through Adversarial Loss
• A Provable Defense for Deep Residual Networks
• Resilient Cyberphysical Systems and their Application Drivers: A Technology Roadmap
• Learning to Confuse: Generating Training Time Adversarial Data with Auto-Encoder
• Exploring Memorization in Adversarial Training
• Towards Understanding the Adversarial Vulnerability of Skeleton-based Action Recognition
• Learning Lyapunov Functions for Piecewise Affine Systems with Neural Network Controllers
• Verification of Neural Network Control Policy Under Persistent Adversarial Perturbation
• Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspective
• ScaleCert: Scalable Certified Defense against Adversarial Patches with Sparse Superficial Layers
• Robustifying Models Against Adversarial Attacks by Langevin Dynamics
• An Analysis of Adversarial Attacks and Defenses on Autonomous Driving Models
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks
• Towards Verifying Robustness of Neural Networks Against Semantic Perturbations
• FR-Train: A Mutual Information-Based Approach to Fair and Robust Training
• Defending Against Physically Realizable Attacks on Image Classification
• Precise Tradeoffs in Adversarial Training for Linear Regression
• Deep Partition Aggregation: Provable Defense against General Poisoning Attacks
• A Research Agenda: Dynamic Models to Defend Against Correlated Attacks
• Bag of Tricks for Adversarial Training
• Enhancing Gradient-based Attacks with Symbolic Intervals
• Orthogonalizing Convolutional Layers with the Cayley Transform
• SoK: Machine Learning Governance
• Post-breach Recovery: Protection against White-box Adversarial Examples for Leaked DNN Models
• Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Them
• Kernel Distributionally Robust Optimization
• Neural Architecture Dilation for Adversarial Robustness
• Towards Large yet Imperceptible Adversarial Image Perturbations with Perceptual Color Distance
• Calibrated Surrogate Losses for Adversarially Robust Classification
• Efficient Adversarial Training with Transferable Adversarial Examples
• Scalable Verification of GNN-based Job Schedulers
• Towards Robust Deep Neural Networks
• Enhancing Certifiable Robustness via a Deep Model Ensemble
• Improved Image Wasserstein Attacks and Defenses
• Adversarial Token Attacks on Vision Transformers
• Certifying Confidence via Randomized Smoothing
• Adaptive Generation of Unrestricted Adversarial Inputs
• DSRNA: Differentiable Search of Robust Neural Architectures
• Cost-Aware Robust Tree Ensembles for Security Applications
• Improved, Deterministic Smoothing for L_1 Certified Robustness
• Towards neural networks that provably know when they don't know
• GhostImage: Remote Perception Attacks against Camera-based Image Classification Systems
• Universal Lipschitz Approximation in Bounded Depth Neural Networks
• Correctness Verification of Neural Networks
• Adversarial Robustness by Design through Analog Computing and Synthetic Gradients
• Bit Error Robustness for Energy-Efficient DNN Accelerators
• Lagrangian Decomposition for Neural Network Verification
• Invariance-inducing regularization using worst-case transformations suffices to boost accuracy and spatial robustness
• Safe Control with Neural Network Dynamic Models
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More
• Understanding Adversarial Robustness: The Trade-off between Minimum and Average Margin
• Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
• Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training
• Detecting Overfitting via Adversarial Examples
• Decentralized Inference with Graph Neural Networks in Wireless Communication Systems
• On the Certified Robustness for Ensemble Models and Beyond
• TSS: Transformation-Specific Smoothing for Robustness Certification
• Boosting the Certified Robustness of L-infinity Distance Nets
• Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?
• Fast Certified Robust Training with Short Warmup
• Robust Models Are More Interpretable Because Attributions Look Normal
• Refactoring Neural Networks for Verification
• Model-Based Domain Generalization
• ART: Abstraction Refinement-Guided Training for Provably Correct Neural Networks
• On Training Robust PDF Malware Classifiers
• Interpretable Graph Capsule Networks for Object Recognition
• Semantics Preserving Adversarial Learning
• Misleading Failures of Partial-input Baselines
• Improving Certified Robustness via Statistical Learning with Logical Reasoning
• SOAR: Second-Order Adversarial Regularization
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations
• Certifying Incremental Quadratic Constraints for Neural Networks via Convex Optimization
• Data-Dependent Randomized Smoothing
• Scaling the Convex Barrier with Sparse Dual Algorithms
• Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples
• Adversarial robustness via robust low rank representations
• Towards the Quantification of Safety Risks in Deep Neural Networks
• $n$-ML: Mitigating Adversarial Examples via Ensembles of Topologically Manipulated Classifiers
• Certified Adversarial Defenses Meet Out-of-Distribution Corruptions: Benchmarking Robustness and Simple Baselines
• Enhancing Certified Robustness via Smoothed Weighted Ensembling
• Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing
• Efficient Combinatorial Optimization for Word-level Adversarial Textual Attack
• Evaluating Robustness of Predictive Uncertainty Estimation: Are Dirichlet-based Models Reliable?
• Distributed generation of privacy preserving data with user customization
• Privacy Inference Attacks and Defenses in Cloud-based Deep Neural Network: A Survey
• DeepSearch: A Simple and Effective Blackbox Attack for Deep Neural Networks
• Robust Adversarial Learning via Sparsifying Front Ends
• Model-Based Robust Deep Learning: Generalizing to Natural, Out-of-Distribution Data
• ARDA: Automatic Relational Data Augmentation for Machine Learning
• NeuroDiff: Scalable Differential Verification of Neural Networks using Fine-Grained Approximation
• Sequential Randomized Smoothing for Adversarially Robust Speech Recognition
• CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing
• Adversarial Robustness with Non-uniform Perturbations
• Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds
• DetectorGuard: Provably Securing Object Detectors against Localized Patch Hiding Attacks
• Designing Adversarially Resilient Classifiers using Resilient Feature Engineering
• Understanding the Intrinsic Robustness of Image Distributions using Conditional Generative Models
• Where is the Bottleneck of Adversarial Learning with Unlabeled Data?
• Benchmarking adversarial attacks and defenses for time-series data
• Certifying Joint Adversarial Robustness for Model Ensembles
• A Review of Formal Methods applied to Machine Learning
• Most ReLU Networks Suffer from ${\ell }^2$ Adversarial Perturbations
• Neural Network Branch-and-Bound for Neural Network Verification
• On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming
• Adversarially Robust Learning for Security-Constrained Optimal Power Flow
• Policy Smoothing for Provably Robust Reinforcement Learning
• Understanding Catastrophic Overfitting in Adversarial Training
• Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons
• Learning Diverse-Structured Networks for Adversarial Robustness
• Bridging the Gap Between Adversarial Robustness and Optimization Bias
• ATRO: Adversarial Training with a Rejection Option
• Tight Second-Order Certificates for Randomized Smoothing
• Adversarial Robustness of Stabilized NeuralODEs Might be from Obfuscated Gradients
• Debona: Decoupled Boundary Network Analysis for Tighter Bounds and Faster Adversarial Robustness Proofs
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• Certifiable Robustness to Adversarial State Uncertainty in Deep Reinforcement Learning
• Statistically Robust Neural Network Classification
• Architecture Selection via the Trade-off Between Accuracy and Robustness
• Provable robustness against all adversarial $l_p$-perturbations for $p\ge 1$
• RecurJac: An Efficient Recursive Algorithm for Bounding Jacobian Matrix of Neural Networks and Its Applications
• Can Perceptual Guidance Lead to Semantically Explainable Adversarial Perturbations?
• Fundamental Tradeoffs in Distributionally Adversarial Training
• Reachability Analysis of Convolutional Neural Networks
• Adversarially Robust Learning with Unknown Perturbation Sets
• Smoothed Inference for Adversarially-Trained Models
• nn-dependability-kit: Engineering Neural Networks for Safety-Critical Autonomous Driving Systems
• Adversarial Robustness Guarantees for Random Deep Neural Networks
• Generating private data with user customization
• Connecting Lyapunov Control Theory to Adversarial Attacks
• Understanding and Diagnosing Vulnerability under Adversarial Attacks
• Provably Robust Metric Learning
• A Frequency Perspective of Adversarial Robustness
• Universal Approximation with Certified Networks
• Fast Geometric Projections for Local Robustness Certification
• Disentangled Deep Autoencoding Regularization for Robust Image Classification
• SOCRATES: Towards a Unified Platform for Neural Network Analysis
• Moving Target Defense for Deep Visual Sensing against Adversarial Examples
• Provably robust deep generative models
• Rethinking Empirical Evaluation of Adversarial Robustness Using First-Order Attack Methods
• Network Moments: Extensions and Sparse-Smooth Attacks
• Resilience from Diversity: Population-based approach to harden models against adversarial attacks
• On ${\ell }_p$-norm Robustness of Ensemble Stumps and Trees
• Topological Effects on Attacks Against Vertex Classification
• Adv-4-Adv: Thwarting Changing Adversarial Perturbations via Adversarial Domain Adaptation
• Safety-Aware Hardening of 3D Object Detection Neural Network Systems
• Model-Agnostic Meta-Attack: Towards Reliable Evaluation of Adversarial Robustness
• Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness
• Adversarial Attacks on ML Defense Models Competition
• Towards Evaluating and Training Verifiably Robust Neural Networks
• Domain Invariant Adversarial Learning
• A Study on the Uncertainty of Convolutional Layers in Deep Neural Networks
• Robust Implicit Networks via Non-Euclidean Contractions
• Adversarially Robust Kernel Smoothing
• A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustness
• BDD4BNN: A BDD-based Quantitative Analysis Framework for Binarized Neural Networks
• 10 Security and Privacy Problems in Large Foundation Models
• Neural Belief Reasoner
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise
• Extraction of Hierarchical Functional Connectivity Components in human brain using Adversarial Learning
• Learning Neural Models for Natural Language Processing in the Face of Distributional Shift
• On the Structural Sensitivity of Deep Convolutional Networks to the Directions of Fourier Basis Functions
• Hidden Cost of Randomized Smoothing
• Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness
• Robust Machine Learning via Privacy/Rate-Distortion Theory
• Nonparametric Learning of Two-Layer ReLU Residual Units
• A Sequential Framework Towards an Exact SDP Verification of Neural Networks
• Investigating the Robustness of Artificial Intelligent Algorithms with Mixture Experiments
• Robust Neural Networks inspired by Strong Stability Preserving Runge-Kutta methods
• Training Provably Robust Models by Polyhedral Envelope Regularization
• Recent Advances in Large Margin Learning
• Adaptive versus Standard Descent Methods and Robustness Against Adversarial Examples
• MadNet: Using a MAD Optimization for Defending Against Adversarial Attacks
• Intriguing Properties of Input-dependent Randomized Smoothing
• Subspace Adversarial Training
• Floating-Point Neural Networks Are Provably Robust Universal Approximators
• Training Efficiency and Robustness in Deep Learning
• Balancing Robustness and Sensitivity using Feature Contrastive Learning
• An Ensemble Approach Towards Adversarial Robustness
• Localized Uncertainty Attacks
• Constructing a provably adversarially-robust classifier from a high accuracy one
• Group-Structured Adversarial Training
• Built-in Elastic Transformations for Improved Robustness
• Leave-one-out Unfairness
• Identifying and Exploiting Structures for Reliable Deep Learning
• Learning Region of Attraction for Nonlinear Systems
• Improving Adversarial Robustness for Free with Snapshot Ensemble
• Expected Tight Bounds for Robust Training
• Calibrated Adversarial Training
• ε-weakened Robustness of Deep Neural Networks
• Extreme Value Preserving Networks
• Trust but Verify: Assigning Prediction Credibility by Counterfactual Constrained Learning
• Deterministic Certification to Adversarial Attacks via Bernstein Polynomial Approximation
• Achieving Adversarial Robustness Requires An Active Teacher
• Adaptive Verifiable Training Using Pairwise Class Similarity
• Learning Lyapunov Functions for Hybrid Systems
• Improving the Certified Robustness of Neural Networks via Consistency Regularization
• Improved Estimation of Concentration Under ${\ell }_p$-Norm Distance Metrics Using Half Spaces
• Deep Learning-Based Autonomous Driving Systems: A Survey of Attacks and Defenses
• Simpler Certified Radius Maximization by Propagating Covariances
• Understanding (Non-)Robust Feature Disentanglement and the Relationship Between Low- and High-Dimensional Adversarial Attacks
• Trace-Norm Adversarial Examples
• Semantics-Preserving Adversarial Training
• Notes on Margin Training and Margin p-Values for Deep Neural Network Classifiers