Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes

2019/03/20 by Matt Jordan, Jordan, Matt, Justin Lewis +3 · 20 citations
Computer Science · Mathematics · #Advanced Malware Detection Techniques #Adversarial Robustness in Machine Learning #Adversarial system #Artificial intelligence #Ball (mathematics) #Business #Combinatorics #Computer science #Computer security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Geometry #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematics #Political science #Polytope #cs.CR #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1903.08778

published in arXiv (Cornell University) (Cornell University) · Code can be found here: https://github.com/revbucket/geometric-certificates

openalex publication_date 2019/03/20 · openalex created_date 2019/04/01 · arxiv created 2019/06/04 · arxiv updated 2019/06/05 · openalex updated_date 2026/07/28

Abstract

We propose a novel method for computing exact pointwise robustness of deep neural networks for all convex ℓ_p norms. Our algorithm, GeoCert, finds the largest ℓ_p ball centered at an input point x₀, within which the output class of a given neural network with ReLU nonlinearities remains unchanged. We relate the problem of computing pointwise robustness of these networks to that of computing the maximum norm ball with a fixed center that can be contained in a non-convex polytope. This is a challenging problem in general, however we show that there exists an efficient algorithm to compute this for polyhedral complices. Further we show that piecewise linear neural networks partition the input space into a polyhedral complex. Our algorithm has the ability to almost immediately output a nontrivial lower bound to the pointwise robustness which is iteratively improved until it ultimately becomes tight. We empirically show that our approach generates distance lower bounds that are tighter compared to prior work, under moderate time constraints.

Citations

• Adam: A Method for Stochastic Optimization
• Intriguing properties of neural networks
• Explaining and Harnessing Adversarial Examples
• Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation
• An approach to reachability analysis for feed-forward ReLU neural networks
• Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks
• Certified Defenses against Adversarial Examples
• Towards Fast Computation of Certified Robustness for ReLU Networks
• Efficient Formal Safety Analysis of Neural Networks
• Formal Verification of CNN-based Perception Systems

Cited by

• On ANN-enhanced positive invariance for nonlinear flat systems
• Adversarial Examples in Environment Perception for Automated Driving (Review)

Related

• Fast Geometric Projections for Local Robustness Certification
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• Robustness Against Adversarial Attacks via Learning Confined Adversarial Polytopes
• Fastened CROWN: Tightened Neural Network Robustness Certificates
• On Certifying Non-uniform Bound against Adversarial Attacks