Analyzing the robustness of neural networks against norm-bounded uncertainties and adversarial attacks has found many applications ranging from safety verification to robust training. In this paper, we propose a semidefinite programming (SDP) framework for safety verification and robustness analysis of neural networks with general activation functions. Our main idea is to abstract various properties of activation functions (e.g., monotonicity, bounded slope, bounded values, and repetition across layers) with the formalism of quadratic constraints. We then analyze the safety properties of the abstracted network via the S-procedure and semidefinite programming. Compared to other semidefinite relaxations proposed in the literature, our method is less conservative, especially for deep networks, with an order of magnitude reduction in computational complexity. Furthermore, our approach is applicable to any activation functions.
On the other hand, certification algorithms based on continuous optimization are more scalable but less accurate. A notable work in this category is reported in @cite_19 , where the authors propose a linear-programming (LP) relaxation of piece-wise linear networks and provide upper bounds on the worst-case loss using weak duality. The main advantage of this work is that the proposed algorithm solely relies on forward- and back-propagation operations on a modified network, and thus is easily integrable into existing learning algorithms. In @cite_12 , the authors propose an SDP relaxation of one-layer sigmoid-based neural networks based on bounding the worst-case loss with a first-order Taylor expansion. Finally, the closest work to the present work is @cite_20 , in which the authors propose a semidefinite relaxation (SDR) for certifying robustness of piece-wise linear multi-layer neural networks. This technique provides tighter bounds than that of @cite_19 , although it is less scalable.
@cite_19 @cite_20 @cite_12
2766462876 2892354372 2786163515
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 will be guaranteed to detect all adversarial examples, though it may flag some non-adversarial examples as well). The basic idea of the approach 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 toy 2D robust classification task, and on a simple convolutional architecture applied to MNIST, where we produce a classifier that provably has less than 8.4 test error for any adversarial attack with bounded @math norm less than @math . This represents the largest verified network that we are aware of, and we discuss future challenges in scaling the approach to much larger domains. Research on adversarial examples are evolved in arms race between defenders who attempt to train robust networks and attackers who try to prove them wrong. This has spurred interest in methods for certifying the robustness of a network. Methods based on combinatorial optimization compute the true robustness but do not yet scale. Methods based on convex relaxations scale better but can only yield non-vacuous bounds on networks trained with those relaxations. In this paper, we propose a new semidefinite relaxation that applies to ReLU networks with any number of layers. We show that it produces meaningful robustness guarantees across a spectrum of networks that were trained against other objectives, something previous convex relaxations are not able to achieve. While neural networks have achieved high accuracy on standard image classification benchmarks, their accuracy drops to nearly zero in the presence of small adversarial perturbations to test inputs. Defenses based on regularization and adversarial training have been proposed, but often followed by new, stronger attacks that defeat these defenses. Can we somehow end this arms race? In this work, we study this problem for neural networks with one hidden layer. We first propose a method based on a semidefinite relaxation that outputs a certificate that for a given network and test input, no attack can force the error to exceed a certain value. Second, as this certificate is differentiable, we jointly optimize it with the network parameters, providing an adaptive regularizer that encourages robustness against all attacks. On MNIST, our approach produces a network and a certificate that no attack that perturbs each pixel by at most = 0.1 can cause more than 35 test error.