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

Abstract

We propose a novel method for computing exact pointwise robustness of deep neural networks for all convex ${\ell }_p$ norms. Our algorithm, GeoCert, finds the largest ${\ell }_p$ ball centered at an input point $x_0$, 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.

arXiv commentCode can be found here: https://github.com/revbucket/geometric-certificates

References in corpus (11)

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

Cited by in corpus (11)

• Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks
• Globally-Robust Neural Networks
• Smoothed Geometry for Robust Attribution
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework
• Robust Models Are More Interpretable Because Attributions Look Normal
• NLP Verification: Towards a General Methodology for Certifying Robustness
• Computing Linear Restrictions of Neural Networks
• Adversarial Robustness Guarantees for Random Deep Neural Networks
• Fast Geometric Projections for Local Robustness Certification
• Relaxing Local Robustness
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams