Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes
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.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Certified but Fooled! Breaking Certified Defences with Ghost Certificates
Certified defenses promise provable robustness guarantees. We study the malicious exploitation of probabilistic certification frameworks to better understand the limits of guarantee provisions. Now, the objective is to n…
Certifying Model Accuracy under Distribution Shifts
Certified robustness in machine learning has primarily focused on adversarial perturbations of the input with a fixed attack budget for each point in the data distribution. In this work, we present provable robustness gu…
modelProvable Robustness for Streaming Models with a Sliding Window
The literature on provable robustness in machine learning has primarily focused on static prediction problems, such as image classification, in which input samples are assumed to be independent and model performance is m…
Activity RecognitionHuman Activity Recognitionimage-classificationImage ClassificationProjected Randomized Smoothing for Certified Adversarial Robustness
Randomized smoothing is the current state-of-the-art method for producing provably robust classifiers. While randomized smoothing typically yields robust $\ell_2$-ball certificates, recent research has generalized provab…
Adversarial RobustnessThe Limitations of Adversarial Training and the Blind-Spot Attack
The adversarial training procedure proposed by Madry et al. (2018) is one of the most effective methods to defend against adversarial examples in deep neural networks (DNNs). In our paper, we shed some lights on the prac…
valid