Second-Order Provable Defenses against Adversarial Attacks

Modern neural networks achieve high accuracy on tasks such as image classification and speech recognition, but are known to be brittle to small, adversarially chosen perturbations of their inputs [46]. A classifier which correctly classifies an image $\mathbf{x}$, can be fooled by an adversary to misclassify an adversarial example $\mathbf{x}+\delta$, such that $\mathbf{x}+\delta$ is indistinguishable from $\mathbf{x}$ to a human. Adversarial examples can also fool systems when they are printed out on a paper and photographed with a smart phone [23]. Even in a black box threat model, where the adversary has no access to the model parameters, attackers could target autonomous vehicles by using stickers or paint to create an adversarial stop sign that the vehicle would interpret as a ‘yield’ or another sign [36]. This trend is worrisome and suggests that adversarial vulnerabilities need to be appropriately addressed before neural networks can be deployed in security critical applications.

In this work, we propose a new approach for developing provable defenses against $\ell_{2}$-bounded adversarial attacks as well as computing robustness certifications of pre-trained deep networks with differentiable activations. In contrast to the existing certificates [55, 50] that use the first-order information (upper and lower bounds on the slope), our approach is based on the second-order information (upper and lower bounds on curvature values i.e. eigenvalues of the Hessian). Our approach is based on two key theoretically-justified steps: First, in Theorems 1 and 2, we show that if the eigenvalues of the Hessian of the network (curvatures of the network) are bounded (globally or locally), we can efficiently compute a robustness certificate and develop a defense method against $\ell_{2}$-bounded adversarial attacks using convex optimization. Second, in Theorem 4, we derive a computationally-efficient differentiable bound on the curvature (eigenvalues of the Hessian) of a deep network. We derive this bound by explicitly characterizing the Hessian of a deep network in Lemma 1.

Although the problem of finding the closest adversarial example to a given point for deep nets leads to a non-convex optimization problem, our proposed Curvature-based Robustness Certificate (CRC), under some verifiable conditions, is able to compute points on the decision boundary that are provably closest to the input. That is, it provides the tightest certificate in those cases. For example, for a 2,3,4 layer networks trained on MNIST, we can find provably closest adversarial points for 44.17%, 22.59%, 19.53% cases, respectively (Table 2). To the best of our knowledge, our method is the first approach that can efficiently compute provably closest adversarial examples for a significant fraction of examples in non-trivial neural networks.

We note that un-regularized networks, specially deep ones, can obtain large curvature bounds which can lead to small robustness certificates. However, by using the derived curvature bound as a regularizer during training, we significantly decrease curvature values of the network, with little or no decrease in its performance (Table 5(b), Figure 1). Using this technique, our method significantly outperforms interval-bound propagation (IBP) [57, 52] and achieves state of the art certified accuracy (Tables 3 and 4). In particular, our method achieves certified robust accuracy 69.79%, 57.78% and 53.19% while IBP-based methods achieve 44.96%, 44.74% and 44.66% on 2,3 and 4 layer networks, respectively, on the MNIST-dataset (similar results for Fashion-MNIST).

Other recent works (e.g. Moosavi Dezfooli et al. [34], Qin et al. [38]) empirically show that using an estimate of curvature at inputs as a regularizer leads to empirical robustness on par with the adversarial training. In this work, however, we use a bound on the absolute value of curvature (and not an estimate) as a regularizer and show that it results in high certified robustness. Moreover, previous works have tried to certify robustness by bounding the Lipschitz constant of the neural network [46, 37, 56, 1, 20]. Our approach, however, is based on bounding the Lipschitz constant of the gradient which in turn leads to bound on the eigenvalues of the Hessian of deep neural networks.

In summary, we make the following contributions:

• •

  We derive a closed-form expression for the Hessian of a deep network with differentiable activation functions (Lemma 1) and derive bounds on the curvature using this closed-form formula (Theorems 3 and 4).

• •

  We develop computationally efficient methods for both the robustness certification as well as the adversarial attack problems (Theorems 1 and 2).

• •

  We provide verifiable conditions under which our method is able to compute points on the decision boundary that are provably closest to the input. Empirically, we show that this condition holds for a significant fraction of examples (Table 2).

• •

  We show that using our proposed curvature bounds as a regularizer during training leads to improved certified accuracy on 2,3 and 4 layer networks (on the MNIST and Fashion-MNIST datasets) compared to IBP-based adversarial training [51, 57] (Tables 3 and 4). Our robustness certificate (CRC) outperforms CROWN’s certificate [55] significantly when trained with our regularizer (Table 5(b)).

To the best of our knowledge, this is the first work that (a) demonstrates the utility of second-order information for provable robustness, (b) derives a framework to find the exact robustness certificates in the $l_{2}$ norm and the exact worst case adversarial perturbation in an $l_{2}$ ball of given a radius under some conditions, and (c) derives an exact closed form expression for the Hessian and bounds on the curvature values using the same.

In the last couple of years, several empirical defenses have been proposed for training classifiers to be robust against adversarial perturbations [30, 42, 58, 35, 24, 32, 59] Although these defenses robustify classifiers to particular types of attacks, they can be still vulnerable against stronger attacks [3, 7, 47, 2]. For example, [3] showed most of the empirical defenses proposed in ICLR 2018 can be broken by developing tailored attacks for each of them.

To end the cycle between defenses and attacks, a line of work on certified defenses has gained attention where the goal is to train classifiers whose predictions are provably robust within some given region [21, 22, 15, 8, 9, 29, 12, 17, 5, 48, 51, 49, 52, 40, 39, 13, 14, 11, 44, 19, 18, 31, 55, 50, 57]. These methods, however, do not scale to large and practical networks used in solving modern machine learning problems. Another line of defense work focuses on randomized smoothing where the prediction is robust within some region around the input with a user-chosen probability [28, 6, 26, 27, 10, 41]. Although these methods can scale to large networks, certifying robustness with probability close to 1 often requires generating a large number of noisy samples around the input which leads to high inference-time computational complexity. We discuss existing works in more details in Appendix A.

Consider a fully connected neural network with $L$ layers and $N_{I}$ neurons in the $I^{th}$ layer ($L\geq 2$ and $I\in$ $[L]$) for a multi-label classification problem with $C$ classes ($N_{L}=C$). The corresponding function of the neural network is $\mathbf{z}^{(L)}:\mathbf{R}^{D}\to\mathbf{R}^{C}$ where $D$ is the dimension of the input. For an input $\mathbf{x}$, we use $\mathbf{z}^{(I)}(\mathbf{x})\in\mathbf{R}^{N_{I}}$ and $\mathbf{a}^{(I)}(\mathbf{x})\in\mathbf{R}^{N_{I}}$ to denote the input (before applying the activation function) and output (after applying the activation function) of neurons in the $I^{th}$ hidden layer of the network, respectively. To simplify notation and when no confusion arises, we make the dependency of $\mathbf{z}^{(I)}$ and $\mathbf{a}^{(I)}$ to $\mathbf{x}$ implicit. We define $\mathbf{a}^{(0)}(\mathbf{x})=\mathbf{x}$ and $N_{0}=D$.

With a fully connected architecture, each $\mathbf{z}^{(I)}$ and $\mathbf{a}^{(I)}$ is computed using a transformation matrix $\mathbf{W}^{(I)}\in R^{N_{I}\times N_{I-1}}$, the bias vector $\mathbf{b}^{(I)}\in R^{N_{I}}$ and an activation function $\sigma(.)$ as follows:

We use $(\mathbf{z}^{(L)}_{i}-\mathbf{z}^{(L)}_{j})(\mathbf{x})$ as a shorthand for $\mathbf{z}^{(L)}_{i}(\mathbf{x})-\mathbf{z}^{(L)}_{j}(\mathbf{x})$.

We use $[p]$ to denote the set $\{1,\dotsc,p\}$ and $[p,q],\ p\leq q$ to denote the set $\{p,p+1,\dotsc,q\}$. We use small letters $i,j,k$ etc to denote the index over a vector or rows of a matrix and capital letters $I,J$ to denote the index over layers of network. The element in the $i^{th}$ position of a vector $\mathbf{v}$ is given by $\mathbf{v}_{i}$, the vector in the $i^{th}$ row of a matrix $\mathbf{A}$ is $\mathbf{A}_{i}$ while the element in the $i^{th}$ row and $j^{th}$ column of $\mathbf{A}$ is $\mathbf{A}_{i,j}$. We use $\|\mathbf{v}\|$ and $\|\mathbf{A}\|$ to denote the 2-norm and the operator 2-norm of the vector $\mathbf{v}$ and the matrix $\mathbf{A}$, respectively. We use $\left|\mathbf{v}\right|$ and $\left|\mathbf{A}\right|$ to denote the vector and matrix constructed by taking the elementwise absolute values. We use $\lambda_{max}(\mathbf{A})$ and $\lambda_{min}(\mathbf{A})$ to denote the largest and smallest eigenvalues of a symmetric matrix $\mathbf{A}$. We use $diag(\mathbf{v})$ to denote the diagonal matrix constructed by placing each element of $\mathbf{v}$ along the diagonal. We use $\odot$ to denote the Hadamard Product, $\mathbf{I}$ to denote the identity matrix. We use $\preccurlyeq$ and $\succcurlyeq$ to denote Linear Matrix Inequalities (LMIs) such that given two symmetric matrices $\mathbf{A}$ and $\mathbf{B}$ where $\mathbf{A}\succcurlyeq\mathbf{B}$ means $\mathbf{A}-\mathbf{B}$ Positive Semi-Definite (PSD).

Consider an input $\mathbf{x}^{(0)}$ with true label $y$ and attack target $t$. In the certificate problem, our goal is to find a lower bound of minimum $l_{2}$ distance between $\mathbf{x}^{(0)}$ and decision boundary $f(\mathbf{x})=0$ where $f(\mathbf{x})=(\mathbf{z}^{(L)}_{y}-\mathbf{z}^{(L)}_{t})(\mathbf{x})$. The problem for solving the exact distance (primal) can be written as:

However, solving the above problem can be hard in general. Using the minimax theorem (primal $\geq$ dual), we can write the dual of the above problem as follows:

From the theory of duality, we know that $d_{cert}(\eta)$ for each value of $\eta$ gives a lower bound on the exact certification value (the primal solution) $p^{*}_{cert}$. However, since $f$ is non-convex, solving $d_{cert}(\eta)$ for every $\eta$ can be difficult. In the next section, we will prove that the curvature of the function $f$ is bounded globally:

In this case, we have the following theorem ($d^{*}_{cert}$ is defined in Table 1):

Below, we briefly outline the proof while the full proof is presented in Appendix E.1. The Hessian of the objective function of the dual $d_{cert}(\eta)$, i.e the function inside the $\min_{\mathbf{x}}$ is given by:

From equation (3), we know that the eigenvalues of $\mathbf{I}+\eta\nabla^{2}_{\mathbf{x}}f$ are bounded between $(1+\eta m,1+\eta M)$ if $\eta\geq 0$, and in $(1+\eta M,1+\eta m)$ if $\eta\leq 0$. In both cases, we can see that for $-1/M\leq\eta\leq-1/m$, all eigenvalues will be non-negative, making the objective function convex. When $\mathbf{x}^{(cert)}$ satisfies $f(\mathbf{x}^{(cert)})=0$, we have $d^{*}_{cert}=1/2\|\mathbf{x}^{(cert)}-\mathbf{x}^{(0)}\|^{2}$. Using the duality theorem we have $d^{*}_{cert}\leq p^{*}_{cert}$ and from the definition of $p^{*}_{cert}$, we have $p^{*}_{cert}\leq d^{*}_{cert}$. Combining the two inequalities, we get $p^{*}_{cert}=d^{*}_{cert}$.

Next, we consider the attack problem. The goal here is to find an adversarial example inside an $l_{2}$ ball of radius $\rho$ such that $f(\mathbf{x})$ is minimized. Using similar arguments, we can get the following theorem for the attack problem ($p^{*}_{attack}$, $d^{*}_{attack}$ and $d_{attack}$ are defined in Table 1):

The proof is presented in Appendix E.2. We note that both Theorems 1 and 2 hold for any non-convex function with continuous gradients. Thus they can also be of interest in problems such as optimization of neural nets.

Using Theorems 1 and 2, we have the following definitions for certification and attack optimizations:

A direct implication of Theorems 1 and 2 is that the tightness of our robustness certificate crucially depends on the tightness of our curvature bounds, $m$ and $M$. If $m$ and $M$ are very large compared to the true eigenvalue bounds of the Hessian of the network, the resulting robustness certificate will be vacuous. In Table 5(b) (and Figure 1), we show that by adding the derived bound as a regularization term during the training, we can significantly decrease curvature bounds of the network, with little or no decrease in its performance. This leads to high robustness certifications against adversarial attacks.

In this section, we provide a computationally efficient approach to compute the curvature bounds for neural networks with differentiable activation functions. To the best of our knowledge, there is no prior work on finding provable bounds on the curvature values of deep neural networks.

Since the term $\mathbf{B}^{(I)}$ in Lemma 1 is the Jacobian of $\mathbf{z}^{(I)}$ with respect to $\mathbf{x}$, $\|\mathbf{B}^{(I)}\|$, it is equal to the lipschitz constant of the neural network constructed from the first $I$ layers of the original network. Finding tight bounds on the lipschitz constant is an active area of research [16, 50, 43] and the product of the operator norm of weight matrices is known to be a loose bound on the lipschitz constant for deep networks. Since we use the same product to compute the bound for $\|\mathbf{B}^{(I)}\|$ in Theorem 4, the resulting curvature bound is likely to be loose for very deep networks.

In Figure 1, we observe the same trend: as the depth of the network increases, the upper bound $K_{ub}$ computed using Theorem 4 becomes significantly larger than the lower bound $K_{lb}$ (computed by taking the maximum of the largest eigenvalue of the Hessian across all test images with label $y$ and the second largest logit $t$, then averaging across different $(y,t)$). However, by regularizing the network to have small curvature during training, the bound becomes significantly tighter. Interestingly, using curvature regularization, even with this loose curvature bound for deep nets, we achieve significantly higher robust accuracy than the current state of the art methods while enjoying significantly higher standard accuracy as well (see Tables 3 and 4).

To regularize the network to have small curvature values, we penalize the curvature bound $K$ during training. To compute the gradient of $K$ with respect to the network weights, note that using Theorem 4, we can compute $K$ using absolute value, matrix multiplications, and operator norm. Since the gradient of operator norm does not exist in standard libraries, we created a new layer where the gradient of $\|\mathbf{W}^{(I)}\|$ i.e $\nabla_{\mathbf{W}^{(I)}}\|\mathbf{W}^{(I)}\|$ is given by:

Note that $\|\mathbf{W}^{(I)}\|$, $\mathbf{u}^{(I)}$ and $\mathbf{v}^{(I)}$ can be computed using power iteration. Since the network weights do not change significantly during a single training step, we can use the singular vectors $\mathbf{u}^{(I)}$ and $\mathbf{v}^{(I)}$ computed in the previous training step to update $\mathbf{W}^{(I)}$ using one iteration of power method. This approach to compute the gradient of the largest singular value of a matrix has also been used in previous published work [33]. Thus, the per-sample loss for training with curvature regularization is given by:

where $\ell$ denotes the cross entropy loss, $y$ is the true label of the input $\mathbf{x}^{(0)}$, $t$ is the attack target and $\gamma$ is the regularization coefficient for penalizing large curvature values. Similar to the adversarial training, in CRT, we use $\mathbf{x}^{(attack)}$ instead of $\mathbf{x}^{(0)}$ in equation (7).

The certified robust accuracy means the fraction of correctly classified test samples whose robustness certificates (computed using CRC) are greater than a pre-specified radius $\rho$. Unless otherwise specified, we use the class with the second largest logit as the attack target (i.e. the class $t$). The notation ($L\times[1024]$, activation) denotes a neural network with $L$ layers with the specified activation, ($\gamma=c$) denotes standard training with $\gamma$ set to $c$, while (CRT, $c$) denotes CRT training with $\gamma=c$. Certificates are computed over 150 randomly chosen correctly classified images. We use a single NVIDIA GeForce RTX 2080 Ti GPU.

In this paper, we develop computationally-efficient convex relaxations for robustness certification and adversarial attack problems given the classifier has a bounded curvature. We also show that this convex relaxation is tight under some general verifiable conditions. To be able to use proposed certification and attack convex optimizations, we derive global curvature bounds for deep networks with differentiable activation functions. This result is a consequence of a closed-form expression that we derive for the Hessian of a deep network. Adversarial training using our attack method coupled with curvature regularization results in a significantly higher certified robust accuracy than the existing provable defense methods. Our proposed curvature-based robustness certificate significantly outperforms the CROWN certificate when trained with our regularizer. Scaling up our proposed curvature-based robustness certification and training methods as well as further tightening the derived curvature bounds are among interesting directions for the future work.

Appendix