Semidefinite relaxations for certifying robustness to adversarial examples

Introduction

Many state-of-the-art classifiers have been shown to fail catastrophically in the presence of small imperceptible but adversarial perturbations. Since the discovery of such adversarial examples , numerous defenses have been proposed in attempt to build classifiers that are robust to adversarial examples. However, defenses are routinely broken by new attackers who adapt to the proposed defense, leading to an arms race. For example, distillation was proposed but shown to be ineffective . A proposed defense based on transformations of test inputs was broken in only five days . Recently, seven defenses published at ICLR 2018 fell to the attacks of Athalye et al. .

A recent body of work aims to break this arms race by training classifiers that are certifiably robust to all attacks within a fixed attack model . These approaches construct a convex relaxation for computing an upper bound on the worst-case loss over all valid attacks—this upper bound serves as a certificate of robustness. In this work, we propose a new convex relaxation based on semidefinite programming (SDP) that is significantly tighter than previous relaxations based on linear programming (LP) and handles arbitrary number of layers (unlike the formulation in , which was restricted to two). We summarize the properties of our relaxation as follows:

1. Our new SDP relaxation reasons jointly about intermediate activations and captures interactions that the LP relaxation cannot. Theoretically, we prove that there is a square root dimension gap between the LP relaxation and our proposed SDP relaxation for neural networks with random weights.

3. Furthermore, training a network to minimize the optimum of particular relaxation produces networks for which the respective relaxation provides good robustness certificates . Notably and surprisingly, on such networks, our relaxation provides tighter certificates than even the relaxation that was optimized for during training.

Certification methods which evaluate the performance of a given network against all possible attacks roughly fall into two categories. The first category leverages convex optimization and our work adds to this family. Convex relaxations are useful for various reasons. Wong and Kolter , Raghunathan et al. exploited the theory of duality to train certifiably robust networks on MNIST. In recent work, Dvijotham et al. , Wong et al. extended this approach to train bigger networks with improved certified error and on larger datasets. Solving a convex relaxation for certification typically involves standard techniques from convex optimization. This enables scalable certification by providing valid upper bounds at every step in the optimization .

The second category draws techniques from formal verification such as SMT , which aim to provide tight certificates for any network using discrete optimization. These techniques, while providing tight certificates on arbitrary networks, are often very slow and worst-case exponential in network size. In prior work, certification would take up to several hours or longer for a single example even for a small network with around 100 hidden units . However, in concurrent work, Tjeng and Tedrake impressively scaled up exact verification through careful preprocessing and efficient pruning that dramatically reduces the search space. In particular, they concurrently obtain non-trivial certificates of robustness on a moderately-sized network trained using the adversarial training objective of on MNIST at perturbation level $\epsilon=0.1$.

Setup

Our main contribution is a semidefinite relaxation of an optimization objective that arises in certification of neural networks against adversarial examples. In this section, we set up relevant notation and present the optimization objective that will be the focus of the rest of the paper.

Multi-layer ReLU networks for classification.

Attack model and certificate of robustness.

Optimization objective.

Semidefinite relaxations

In this section, we present our approach to obtaining a computationally tractable upper bound to the solution of the optimization problem described in (2).

The source of the non-convexity in (2) is the ReLU constraints. Consider a ReLU constraint of the form $z=\max(x,0)$. The key observation is that this constraint can be expressed equivalently as the following three linear and quadratic constraints between $z$ and $x$: (i) $z(z-x)=0$, (ii) $z\geq x$, and (iii) $z\geq 0$. Constraint (i) ensures that $z$ is equal to either $x$ or and constraints (ii) and (iii) together then ensure that $z$ is at least as large as both. This reformulation allows us to replace the non-linear ReLU constraints of the optimization problem in 2 with linear and quadratic constraints, turning it into a quadratically constrained quadratic program (QCQP). We first show how this QCQP can be relaxed to a semidefinite program (SDP) for networks with one hidden layer. The relaxation for multiple layers is a straightforward extension and is presented in Section 5.

1 Relaxation for one hidden layer

We use the key insight that the ReLU constraints can be written as linear and quadratic constraints, allowing us to embed these constraints into a QCQP. We can also express the input constraint $l_{j}\leq x_{j}\leq u_{j}$ as a quadratic constraint, which will be useful later. In particular, $l_{j}\leq x_{j}\leq u_{j}$ if and only if $(x_{j}-l_{j})(x_{j}-u_{j})\leq 0$, thereby yielding the quadratic constraint $x_{j}^{2}\leq(l_{j}+u_{j})x_{j}-l_{j}u_{j}$. This gives us the final QCQP below:

We now relax the non-convex QCQP (3) to a convex SDP. The basic idea is to introduce a new set of variables representing all linear and quadratic monomials in $x$ and $z$; the constraints in (3) can then be written as linear functions of these new variables.

In particular, let v\stackrel{{\scriptstyle\rm def}}{{=}}\left[\begin{array}[]{c}1\\ x\\ z\end{array}\right]. We define a matrix $P\stackrel{{\scriptstyle\rm def}}{{=}}vv^{\top}$ and use symbolic indexing $P[\mathsf{\cdot}]$ to index the elements of $P$, i.e P=\left[\begin{array}[]{c c c}P[\mathsf{1}]&P[\mathsf{x^{\top}}]&P[\mathsf{z^{\top}}]\\ P[\mathsf{x}]&P[\mathsf{xx^{\top}}]&P[\mathsf{xz^{\top}}]\\ P[\mathsf{z}]&P[\mathsf{zx^{\top}}]&P[\mathsf{zz^{\top}}]\end{array}\right].

The SDP relaxation of (3) can be written in terms of the matrix $P$ as follows.

Analysis of the relaxation

Before extending the SDP relaxation defined in (4) to multiple layers, we will provide some geometric intuition for the SDP relaxation.

First consider the simple case where $m=d=1$ and $W=c=1$, so that the problem is to maximize $z$ subject to $z=\text{ReLU}(x)$ and $l\leq x\leq u$. In this case, the SDP relaxation of (4) is as follows:

Input constraints. The input constraint $P[\mathsf{x^{2}}]\leq(l+u)P[\mathsf{x}]-lu$ equivalently imposes $\|\vec{x}\|^{2}\leq(l+u)(\vec{x}\cdot\vec{{e}})-lu$. Geometrically, this constrains vector $\vec{x}$ on a sphere with center at $\frac{1}{2}(l+u)\vec{{e}}$ and radius $\frac{1}{2}(l-u)$. Notice that this implicitly bounds the norm of $\vec{x}$. This is illustrated in Figure 1(a) where the green circle represents the space of feasible vectors $\vec{x}$, projected onto the plane containing $\vec{{e}}$ and $\vec{x}$.

ReLU constraints. The constraint on the quadratic terms $(P[\mathsf{z^{2}}]=P[\mathsf{zx}])$ is the core of the SDP. It says that the vector $\vec{z}$ is perpendicular to $\vec{z}-\vec{x}$. We can visualize $\vec{z}$ on the plane containing $\vec{x}$ and $\vec{{e}}$ in Figure 1(a); the component of $\vec{z}$ perpendicular to this plane is not relevant to the SDP, because it’s neither constrained nor appears in the objective. The feasible $\vec{z}$ trace out a circle with $\frac{1}{2}\vec{x}$ as the center (because the angle inscribed in a semicircle is a right angle). The linear constraints restrict $\vec{z}$ to the arc that has a larger projection on $\vec{{e}}$ than $\vec{x}$, and is positive.

Remarks. This geometric picture allows us to make the following important observation about the objective value \max~{}\big{(}\vec{z}\cdot\vec{{e}}\big{)} of the SDP relaxation. The largest value that $\vec{z}\cdot\vec{{e}}$ can take depends on the angle $\theta$ that $\vec{x}$ makes with $\vec{{e}}$. In particular, as $\theta$ decreases, the relaxation becomes tighter and as the vector deviates from $\vec{{e}}$, the relaxation gets looser. Figure 1(b) provides an illustration. For large $\theta$, the radius of the circle that $\vec{z}$ traces increases, allowing $\vec{z}\cdot\vec{{e}}$ to take large values.

That leads to the natural question: For a fixed input value $\vec{x}\cdot\vec{{e}}$ (corresponding to $x$), what controls $\theta$? Since $\vec{x}\cdot\vec{{e}}=\|\vec{x}\|\cos\theta$, as the norm of $\vec{x}$ increases, $\theta$ increases. Hence a constraint that forces $\|\vec{x}\|$ to be close to $\vec{x}\cdot\vec{{e}}$ will cause the output $\vec{z}\cdot\vec{{e}}$ to take smaller values. Porting this intuition into the matrix interpretation, this suggests that constraints forcing $P[\mathsf{x^{2}}]=\|\vec{x}\|^{2}$ to be small lead to tighter relaxations.

2 Comparison with linear programming relaxation

In the LP relaxation, we replace the ReLU constraints at hidden node $j$ with a convex outer envelope as illustrated in Figure 2(a). The envelope is lower bounded by the linear constraints $z\geq Wx$ and $z\geq 0$. In order to construct the upper bounding linear constraints, we compute the extreme points $s=\min\limits_{l\leq x\leq u}Wx$ and $t=\max\limits_{l\leq x\leq u}Wx$ and construct lines that connect $(s,~{}\text{ReLU}(s))$ and $(t,~{}\text{ReLU}(t))$. The final LP for the neural network is then written by constructing the convex envelopes for each ReLU unit and optimizing over this set as follows:

From Figure 2(a), we see that for a single ReLU unit taken in isolation, the LP is tighter than the SDP. However, when we have multiple units, the SDP is tighter than the LP. We illustrate this with a simple example in $2$ dimensions with $2$ hidden nodes (See Figure 2(b)).

Simple example to compare the LP and SDP.

Consider a two dimensional example with input $x=[x_{1},x_{2}]$ and lower and upper bounds $l=[-\epsilon,-\epsilon]$ and $u=[\epsilon,\epsilon]$, respectively. The hidden layer activations $z_{1}$ and $z_{2}$ are related to the input as $z_{1}=\text{ReLU}(x_{1}+x_{2})$ and $z_{2}=\text{ReLU}(x_{1}-x_{2})$. The objective is to maximize $z_{1}+z_{2}$.

The LP constrains $z_{1}$ and $z_{2}$ independently. To see this, let us set the input $x$ to a fixed value and look at the feasible values of $z_{1}$ and $z_{2}$. In the LP, the convex outer envelope that bounds $z_{1}$ only depends on the input $x$ and the bounds $l$ and $u$ and is independent of the value of $z_{2}$. Similarly, the outer envelope of $z_{2}$ does not depend on the value of $z_{1}$, and the feasible set for $(z_{1},z_{2})$ is simply the product of the individual feasible sets.

In contrast, the SDP has constraints that couple $z_{1}$ and $z_{2}$. As a result, the feasible set of $(z_{1},z_{2})$ is a strict subset of the product of the individual feasible sets. Figure 2(b) plots the LP and SDP feasible sets $[z_{1},z_{2}]$ for $x=[\frac{\epsilon}{2},\frac{\epsilon}{2}]$. Recall from the geometric observations (Section 4.1) that the arc of $\vec{z_{1}}$ depends on the configuration of $\vec{x_{1}}+\vec{x_{2}}$, while that of $\vec{z_{2}}$ depends on $\vec{x_{1}}-\vec{x_{2}}$. Since the vectors $\vec{x_{1}}+\vec{x_{2}}$ and $\vec{x_{1}}-\vec{x_{2}}$ are dependent, the feasible sets of $\vec{z_{1}}$ and $\vec{z_{2}}$ are also dependent on each other. An alternative way to see this is from the matrix constraint that $P\succeq 0$ in 4. This matrix constraint does not factor into terms that decouple the entries $P[\mathsf{z_{1}}]$ and $P[\mathsf{z_{2}}]$, hence $z_{1}$ and $z_{2}$ cannot vary independently.

When we reason about the relaxation over all feasible points $x$, the joint reasoning of the SDP allows it to achieve a better objective value. Figure 2(c) plots the feasible sets $[z_{1},z_{2}]$ over all valid $x$ where the optimal value of the SDP, $f_{\text{SDP}}$, is less than that of the LP, $f_{\text{LP}}$.

We can extend the preceding example to exhibit a dimension-dependent gap between the LP and the SDP for random weight matrices. In particular, for a random network with $m$ hidden nodes and input dimension $d$, with high probability, $f_{\text{LP}}=\Theta(md)$ while $f_{\text{SDP}}=\Theta(m\sqrt{d}+d\sqrt{m})$. More formally:

Suppose that the weight matrix $W\in\mathbf{R}^{m\times d}$ is generated randomly by sampling each element $W_{ij}$ uniformly and independently from $\{-1,+1\}$. Also let the output vector $c$ be the all-$1$s vector, $\mathbf{1}$. Take $\bar{x}=0$ and $\epsilon=1$. Then, for some universal constant $\gamma$,

Multi-layer networks

The SDP relaxation to evaluate robustness for multi-layer networks is a straightforward generalization of the relaxation presented for one hidden layer in Section 3.1.

2 Bounds on intermediate activations

From the geometric interpretation of Section 4.1, we made the important observation that adding constraints that keep $P[\mathsf{x^{2}}]$ small aid in obtaining tighter relaxations. For the multi-layer case, since the activations at layer $i-1$ act as input to the next layer $i$, adding constraints that restrict $P[\mathsf{(x^{i}_{j})^{2}}]$ will lead to a tighter relaxation for the overall objective. The SDP automatically obtains some bound on $P[\mathsf{(x^{i}_{j})^{2}}]$ from the bounds on the input, hence the SDP solution is well-defined and finite even without these bounds. However, we can tighten the bound on $P[\mathsf{(x^{i}_{j})^{2}}]$ by relating it to the linear monomial $P[\mathsf{(x^{i}_{j})}]$ via bounds on the value of the activation $x^{i}_{j}$. One simple way to obtain bounds on activations $x^{i}_{j}$ is to treat each hidden unit separately, using simple interval arithmetic to obtain

where $([M]_{+})_{ij}=\max(M_{ij},0)$ and $([M]_{-})_{ij}=\min(M_{ij},0)$.

In our experiments on real networks (Section 6), we observe that these simple bounds are sufficient to obtain good certificates. However tighter bounds could potentially lead to tighter certificates.

Experiments

In this section, we evaluate the performance of our certificate (7) on neural networks trained using different robust training procedures, and compare against other certificates in the literature.

We consider feedforward networks that are trained on the MNIST dataset of handwritten digits using three different robust training procedures.

1. Grad-NN. We use the two-layer network with $500$ hidden nodes from , obtained by using an SDP-based bound on the gradient of the network (different from the SDP presented here) as a regularizer. We obtained the weights of this network from the authors of .

2. LP-NN. We use a two-layer network with $500$ hidden nodes (matching that of Grad-NN) trained via the LP-based robust training procedure of . The authors of provided the weights.

3. PGD-NN. We consider a fully-connected network with four layers containing $200,100$ and $50$ hidden nodes (i.e., the architecture is 784-200-100-50-10). We train this network using adversarial training against the strong PGD attack . We train to minimize a weighted combination of the regular cross entropy loss and adversarial loss. We tuned the hyperparameters based on the performance of the PGD attack on a holdout set. The stepsize of the PGD attack was set to $0.1$, number of iterations to $40$, perturbation size $\epsilon=0.3$ and weight on adversarial loss to $\frac{1}{3}$.

The training procedures for SDP-NN and LP-NN yield certificates of robustness (described in their corresponding papers), but the training procedure of PGD-NN does not. Note that all the networks are “foreign networks” to our SDP, as their training procedures do not incorporate the SDP relaxation.

Certification procedures.

Recall from Section 2 that an upper bound on the maximum incorrect margin can be used to obtain certificates. We consider certificates from three different upper bounds.

1. SDP-cert. This is the certificate we propose in this work. This uses the SDP upper bound that we defined in Section 5. The exact optimization problem is presented in (7) and the bounds on intermediate activations are obtained using the interval arithmetic procedure presented in (8).

2. LP-cert. This uses the upper bound based on the LP relaxation discussed in Section 4.2 which forms the basis for several existing works on scalable certification . The LP uses layer-wise bounds for intermediate nodes, similar to $l_{i},u_{i}$ in our SDP formulation (7). For Grad-NN and LP-NN with a single hidden layer, the layerwise bounds can be computed exactly using interval arithmetic. For the four-layer PGD-NN, in order to have a fair comparison with SDP-cert, we use the same procedure (interval arithmetic) (8).

3. Grad-cert. We use the upper bound proposed in . This upper bound is based on the maximum norm of the gradient of the network predictions and only holds for two-layer networks.

Table 1 presents the performance of the three different certification procedures on the three networks. For each certification method and network, we evaluate the associated upper bounds on the same $1000$ random test points and report the fraction of points that were not certified. Computing the exact worst-case adversarial error is not computationally tractable. Therefore, to provide a comparison, we also compute a lower bound on the adversarial error—the error obtained by the PGD attack.

Performance of proposed SDP-cert.

SDP-cert provides non-vacuous certificates for all networks considered. In particular, we can certify that the four layer PGD-NN has an error of at most $18\%$ at $\epsilon=0.1$. To compare, a lower bound on the robust error (PGD attack error) is $9\%$. On the two-layer networks, SDP-cert improves the previously-known bounds. For example, it certifies that Grad-NN has an error of at most $20\%$ compared to the previously known $35\%$. Similarly, SDP-cert improves the bound for LP-NN from $22\%$ to $20\%$.

The gap between the lower bound (PGD) and upper bound (SDP) is because of points that cannot be misclassified by PGD but are also not certified by the SDP. In order to further investigate these points, we look at the margins obtained by the PGD attack to estimate the robustness of different points. Formally, let $x_{\text{PGD}}$ be the adversarial example generated by the PGD attack on clean input $\bar{x}$ with true label $\bar{y}$. We compute $\min\limits_{y\neq\bar{y}}[f(x_{\text{PGD}})_{\bar{y}}-f(x_{\text{PGD}})_{y}]$, the margin of the closest incorrect class. A small value indicates that the $x_{\text{PGD}}$ was close to being misclassified. Figure 3 shows the histograms of the above PGD margin. The examples which are not certified by the SDP have much smaller margins than those examples that are certified: the average PGD margin is 1.2 on points that are not certified and 4.5 on points that are certified. From Figure 3, we see that a large number of the SDP uncertified points have very small margin, suggesting that these points might be misclassified by stronger attacks.

Remark.

As discussed in Section 5, we could consider a version of the SDP that does not include the constraints relating linear and quadratic terms at the intermediate layers of the network. Empirically, such an SDP produces vacuous certificates ($>90\%$ error). Therefore, these constraints at intermediate layers play a significant role in improving the empirical performance of the SDP relaxation.

Comparison with other certification approaches.

From Table 1, we observe that SDP-cert consistently performs better than both LP-cert and Grad-cert for all three networks.

Grad-cert and LP-cert provide vacuous ($>90\%$ error) certificates on networks that are not trained to minimize these certificates. This is because these certificates are tight only under some special cases that can be enforced by training. For example, LP-cert is tight when the ReLU units do not switch linear regions . While a typical input causes only $20\%$ of the hidden units of LP-NN to switch regions, $75\%$ of the hidden units of Grad-NN switch on a typical input. Grad-cert bounds the gradient uniformly across the entire input space. This makes the bound loose on arbitrary networks that could have a small gradient only on the data distribution of interest.

Comparison to concurrent work [26].

A variety of robust MNIST networks are certified by Tjeng and Tedrake . On Grad-NN, their certified error is $30\%$ which is looser than our SDP certified error ($20\%$). They also consider the CNN counterparts of LP-NN and PGD-NN, trained using the procedures of and . The certified errors are $4.4\%$ and $7.2\%$ respectively. This reduction in the errors is due to the CNN architecture. Further discussion on applying our SDP to CNNs appears in Section 7.

Optimization setup.

We use the YALMIP toolbox with MOSEK as a backend to solve the different convex programs that arise in these certification procedures. On a 4-core CPU, the average SDP computation took around $25$ minutes and the LP around $5$ minutes per example.

Discussion

In this work, we focused on fully connected feedforward networks for computational efficiency. In principle, our proposed SDP can be directly used to certify convolutional neural networks (CNNs); unrolling the convolution would result in a (large) feedforward network. Naively, current off-the-shelf solvers cannot handle the SDP formulation of such large networks. Robust training on CNNs leads to better error rates: for example, adversarial training against the PGD adversary on a four-layer feedforward network has error $9\%$ against the PGD attack, while a four-layer CNN trained using a similar procedure has error less than $3\%$ . An immediate open question is whether the network in , which has so far withstood many different attacks, is truly robust on MNIST. We are hopeful that we can scale up our SDP to answer this question, perhaps borrowing ideas from work on highly scalable SDPs and explicitly exploiting the sparsity and structure induced by the CNN architecture.

Guarantees for the bounded norm attack model in general are sufficient but not necessary for robustness against adversaries in the real world. Many successful attacks involve inconspicious but clearly visible perturbations , or large but semantics-preserving perturbations in the case of natural language . These perturbations do not currently have well-defined mathematical models and present yet another layer of challenge. However, we believe that the mathematical ideas we develop for the bounded norm will be useful building blocks in the broader adversarial game.

All code, data and experiments for this paper are available on the Codalab platform at https://worksheets.codalab.org/worksheets/0x6933b8cdbbfd424584062cdf40865f30/.

Acknowledgements.

This work was partially supported by a Future of Life Institute Research Award and Open Philanthrophy Project Award. JS was supported by a Fannie & John Hertz Foundation Fellowship and an NSF Graduate Research Fellowship. We thank Eric Wong for providing relevant experimental results. We are also grateful to Moses Charikar, Zico Kolter and Eric Wong for several helpful discussions and anonymous reviewers for useful feedback.

References

Appendix A Proof of Proposition 1

We first lower bound the LP value $f_{\text{LP}}$, and then upper bound the SDP value $f_{\text{SDP}}$.

It suffices to exhibit a feasible solution for the constraints. Note that for a given hidden unit $i$, we have $s_{i}=-\|W_{i}\|_{1}$ and $t_{i}=\|W_{i}\|_{1}$. In particular, at $x=0$ a feasible value for $z_{i}$ is $\frac{1}{2}\|W_{i}\|_{2}$.

We start by exhibiting a general upper bound on $f_{\text{SDP}}$ implied by the constraints:

For any weight matrices $W$ and $c$, we have $f_{\text{SDP}}\leq\sqrt{d}\|W\|_{2}\|c\|_{2}$, where $\|W\|_{2}$ is the operator norm of $W$.

The proof of Lemma 1 is given later in this section. To apply the lemma, note that in our case $\|c\|_{2}=\sqrt{m}$, while $\|W\|_{2}\leq\gamma\cdot(\sqrt{m}+\sqrt{d}+\sqrt{\log(1/\delta)})$ with probability $1-\delta$, for some universal constant $\gamma$ (see Theorem 5.39 of ). Therefore, Lemma 1 yields the bound $f_{\text{SDP}}\leq\gamma\cdot\sqrt{md}\cdot(\sqrt{m}+\sqrt{d}+\sqrt{m+d})\leq 2\gamma\cdot(m\sqrt{d}+d\sqrt{m})$ with probability $1-\exp(-(m+d))$, as claimed.

A.1 Proof of Lemma 1

First note that since \left[\begin{array}[]{cc}P[\mathsf{1}]&P[\mathsf{z^{\top}}]\\ P[\mathsf{z}]&P[\mathsf{zz^{\top}}]\end{array}\right]\succeq 0, we have $P[\mathsf{z}]P[\mathsf{z}]^{\top}\preceq P[\mathsf{zz^{\top}}]$ by Schur complements, and in particular $\|P[\mathsf{z}]\|_{2}^{2}\leq\operatorname*{tr}P[\mathsf{zz^{\top}}]$ (by taking the trace of both sides).

Using this, and letting $\|\cdot\|_{*}$ denote the nuclear norm (sum of singular values), we have

Here (i) is Hölder’s inequality, and (iii) uses the fact that $P[\mathsf{x_{j}^{2}}]\leq 1$ for all $j$ (due to the constraints imposed by $l$ and $u$).

Solving for $\operatorname*{tr}P[\mathsf{zz^{\top}}]$, we obtain the bound $\operatorname*{tr}P[\mathsf{zz^{\top}}]\leq\|W\|_{2}^{2}d$. Plugging back into the preceding inequality, we obtain $c^{\top}P[\mathsf{z}]\leq\|c\|_{2}\|W\|_{2}\sqrt{d}$, as was to be shown.