Semidefinite relaxations for certifying robustness to adversarial examples

By Aditi Raghunathan, Jacob Steinhardt, Percy Liang. 2018

461 citations recorded by the source corpus.

Despite their impressive performance on diverse tasks, neural networks fail catastrophically in the presence of adversarial inputs—imperceptibly but adversarially perturbed versions of natural inputs. We have witnessed an arms race between defenders who attempt to train robust networks and attackers who try to construct adversarial examples. One promise of ending the arms race is developing certified defenses, ones which are provably robust against all attackers in some family. These certified defenses are based on convex relaxations which construct an upper bound on the worst case loss over all attackers in the family. Previous relaxations are loose on networks that are not trained against the respective relaxation. In this paper, we propose a new semidefinite relaxation for certifying robustness that applies to arbitrary ReLU networks. We show that our proposed relaxation is tighter than previous relaxations and produces meaningful robustness guarantees on three different foreign networks whose training objectives are agnostic to our proposed relaxation.

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Safety, Robustness & Interpretability

Citations in the corpus

Adversarial Training for High-Stakes Reliability (2022, methodology): “One existing technique in this vein is to use a semidefinite relaxation of the model [48].”
Adversarial Training for Free! (2019, background): “Recently, there has been a surge of certiﬁed defenses [Wong and Kolter, 2017, Wong et al., 2018, Raghunathan et al., 2018a,b, Wang et al., 2018].”
Wasserstein Adversarial Examples via Projected Sinkhorn Iterations (2019, methodology): “Veriﬁcation methods are now applicable to multi-layer neural networks using techniques ranging from semi-deﬁnite programming relaxations (Raghunathan et al., 2018), mixed integer linear programming (Tjeng et al., 2019), and duality (Dvijotham et al., 2018).”
Certified Adversarial Robustness via Randomized Smoothing (2019, methodology): “The latter approach has been found more effective (Wong & Kolter, 2018; Raghunathan et al., 2018a).”
Unlabeled Data Improves Adversarial Robustness (2019, background): “Other lines of work attain certified robustness, though often at a cost to empirical robustness compared to heuristics [36, 49, 37, 50, 17].”
Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers (2019, background): “On the bright side, these methods are more scalable and efficient which makes some of them useful for building certified defenses [38, 35, 36, 27, 28, 39, 10, 9, 7, 13, 26, 30, 15, 37, 40].”
Fast is better than free: Revisiting adversarial training (2020, methodology): “, 2017; Carlini & Wagner, 2017a), verification and provable defenses (Katz et al., 2017; Sinha et al., 2017; Wong & Kolter, 2017; Raghunathan et al., 2018), and various theoretically motivated heuristics (Xiao et al.”
Adversarial Robustness Against the Union of Multiple Perturbation Models (2019, methodology): “…methods to certify robustness properties of networks were developed, utilizing techniques such as SMT solvers [Katz et al., 2017], SDP relaxations [Raghunathan et al., 2018b], and mixed-integer linear programming [Tjeng et al., 2019], the last of which has recently been successfully scaled to…”
A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks (2019, background): “1 , and is used in Tjeng et al. (2019) and Raghunathan et al. (2018a).”
Lipschitz-Certifiable Training with a Tight Outer Bound (2020, methodology): “The dual relaxation approach formulates the veriﬁable training as a convex optimization and uses duality to build a relaxed bound of the optimization problem and to relieve the computational load [39, 40, 29, 7, 30].”
Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond (2020, methodology): “The neural network verification problem can also be solved via many other techniques, for example, semidefinite programming [8, 32], bounding local or global Lipschitz constant [14, 32, 55].”
Certifiable Robustness and Robust Training for Graph Convolutional Networks (2019, methodology): “For this work, specifically the class of methods based on convex relaxations are of relevance [18, 20].”
Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification (2021, methodology): “SDP based relaxations [28, 16, 14] typically produce tight bounds but with signiﬁcantly higher cost.”
Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, background): “In addition, many convex-relaxation approaches towards certiﬁable robustness may be recovered by this framework (Zico Kolter & Wong, 2017; Raghunathan et al., 2018; Zhang et al., 2018; Singh et al., 2019).”
Adversarial Attacks and Defenses in Images, Graphs and Text: A Review (2019, methodology): “There are also studies (Raghunathan et al., 2018b; Wong et al., 2018) that improved the efficiency and scalability of these algorithms.”
Rademacher Complexity for Adversarially Robust Generalization (2018, background): “Recently, a few approaches to designing surrogate adversarial loss have been developed, and SDP relaxation [44, 45] and LP relaxation [31, 54] are two major examples.”
Certifying LLM Safety against Adversarial Prompting (2023, unknown): “…propagation (Gowal et al., 2018; Huang et al., 2019; Dvijotham et al., 2018; Mirman et al., 2018), curvature bounds (Wong & Kolter, 2018; Raghunathan et al., 2018; Singla & Feizi, 2020; 2021) and randomized smoothing (Cohen et al., 2019; L´ecuyer et al., 2019; Li et al., 2019; Salman et…”