Certified Robustness to Adversarial Examples with Differential Privacy

An ML model can be viewed as a function mapping inputs – typically a vector of numerical feature values – to an output (a label for multiclass classification and a real number for regression). Focusing on multiclass classification, we define a model as a function $f\colon\mathbb{R}^{n}\rightarrow\mathcal{K}$ that maps $n$-dimensional inputs to a label in the set $\mathcal{K}=\{1,\ldots,K\}$ of all possible labels. Such models typically map an input $x$ to a vector of scores $y(x)=(y_{1}(x),\dotsc,y_{K}(x))$, such that $y_{k}(x)\in[0,1]$ and $\sum_{k=1}^{K}y_{k}(x)=1$. These scores are interpreted as a probability distribution over the labels, and the model returns the label with highest probability, i.e., $f(x)=\arg\max_{k\in\mathcal{K}}y_{k}(x)$. We denote the function that maps input $x$ to $y$ as $Q$ and call it the scoring function; we denote the function that gives the ultimate prediction for input $x$ as $f$ and call it the prediction procedure.

It is natural to constrain the amount of change an attacker is allowed to make to the input, and often this is measured by the $p$-norm of the change, denoted by $\|\alpha\|_{p}$. For $1\leq p<\infty$, the $p$-norm of $\alpha$ is defined by $\|\alpha\|_{p}=(\sum_{i=1}^{n}|\alpha_{i}|^{p})^{1/p}$; for $p=\infty$, it is $\|\alpha\|_{\infty}=\max_{i}|\alpha_{i}|$. Also commonly used is the $0$-norm (which is technically not a norm): $\|\alpha\|_{0}=|\{i:\alpha_{i}\neq 0\}|$. A small $0$-norm attack is permitted to arbitrarily change a few entries of the input; for example, an attack on the image recognition system for self-driving cars based on putting a sticker in the field of vision is such an attack [19]. Small $p$-norm attacks for larger values of $p$ (including $p=\infty$) require the changes to the pixels to be small in an aggregate sense, but the changes may be spread out over many or all features. A change in the lighting condition of an image may correspond to such an attack [34, 50]. The latter attacks are generally considered more powerful, as they can easily remain invisible to human observers. Other attacks that are not amenable to norm bounding exist [67, 54, 66], but this paper deals exclusively with norm-bounded attacks.

Let $B_{p}(r):=\{\alpha\in\mathbb{R}^{n}:\|\alpha\|_{p}\leq r\}$ be the $p$-norm ball of radius $r$. For a given classification model, $f$, and a fixed input, $x\in\mathbb{R}^{n}$, an attacker is able to craft a successful adversarial example of size $L$ for a given $p$-norm if they find $\alpha\in B_{p}(L)$ such that $f(x+\alpha)\neq f(x)$. The attacker thus tries to find a small change to $x$ that will change the predicted label.

Next, given an input, we must establish a definition for insensitivity to small changes to the input. We say a model $f$ is insensitive, or robust, to attacks of $p$-norm $L$ on a given input $x$ if $f(x)=f(x+\alpha)$ for all $\alpha\in B_{p}(L)$. If $f$ is a multiclass classification model based on label scores (as in §II-A), this is equivalent to:

where $k:=f(x)$. A small change in the input does not alter the scores so much as to change the predicted label.

DP is concerned with whether the output of a computation over a database can reveal information about individual records in the database. To prevent such information leakage, randomness is introduced into the computation to hide details of individual records.

A randomized algorithm $A$ that takes as input a database $d$ and outputs a value in a space $O$ is said to satisfy $(\epsilon,\delta)$-DP with respect to a metric $\rho$ over databases if, for any databases $d$ and $d^{\prime}$ with $\rho(d,d^{\prime})\leq 1$, and for any subset of possible outputs $S\subseteq O$, we have

Here, $\epsilon>0$ and $\delta\in[0,1]$ are parameters that quantify the strength of the privacy guarantee. In the standard DP definition, the metric $\rho$ is the Hamming metric, which simply counts the number of entries that differ in the two databases. For small $\epsilon$ and $\delta$, the standard $(\epsilon,\delta)$-DP guarantee implies that changing a single entry in the database cannot change the output distribution very much. DP also applies to general metrics $\rho$ [8], including $p$-norms relevant to norm-based adversarial examples.

Our approach relies on two key properties of DP. First is the well-known post-processing property: any computation applied to the output of an $(\epsilon,\delta)$-DP algorithm remains $(\epsilon,\delta)$-DP. Second is the expected output stability property, a rather obvious but not previously enunciated property that we prove in Lemma 1: the expected value of an $(\epsilon,\delta)$-DP algorithm with bounded output is not sensitive to small changes in the input.

The intuition behind using DP to provide robustness to adversarial examples is to create a DP scoring function such that, given an input example, the predictions are DP with regards to the features of the input (e.g. the pixels of an image). In this setting, we can derive stability bounds for the expected output of the DP function using Lemma 1. The bounds, combined with Equation (1), give a rigorous condition (or certification) for robustness to adversarial examples.

Formally, regard the feature values (e.g., pixels) of an input $x$ as the records in a database, and consider a randomized scoring function $A$ that, on input $x$, outputs scores $(y_{1}(x),\dotsc,y_{K}(x))$ (with $y_{k}(x)\in[0,1]$ and $\sum_{k=1}^{K}y_{k}(x)=1$). We say that $A$ is an ($\epsilon,\delta)$-pixel-level differentially private (or ($\epsilon,\delta$)-PixelDP ) function if it satisfies $(\epsilon,\delta)$-DP (for a given metric). This is formally equivalent to the standard definition of DP, but we use this terminology to emphasize the context in which we apply the definition, which is fundamentally different than the context in which DP is traditionally applied in ML (see §VI for distinction).

Lemma 1 directly implies bounds on the expected outcome on an $(\epsilon,\delta)$-PixelDP scoring function:

Our approach is to transform a model’s scoring function into a randomized $(\epsilon,\delta)$-PixelDP scoring function, $A(x)$, and then have the model’s prediction procedure, $f$, use A’s expected output over the DP noise, $\mathbb{E}(A(x))$, as the label probability vector from which to pick the $\arg\max$. I.e., $f(x)=\arg\max_{k\in\mathcal{K}}\mathbb{E}(A_{k}(x))$. We prove that a model constructed this way allows the following robustness certification to adversarial examples:

The preceding certification test is exact regardless of the value of the $\delta$ parameter of differential privacy: there is no failure probability in this test. The test applies only to attacks of $p$-norm size of $1$, however all preceding results generalize to attacks of $p$-norm size $L$, i.e., when $\|\alpha\|_{p}\leq L$, by applying group privacy [18]. The next section shows how to apply group privacy (§III-B) and generalize the certification test to make it practical (§III-D).

PixelDP is a certified defense against $p$-norm bounded adversarial example attacks built on the preceding DP-robustness connection. Fig. 1(a) shows an example PixelDP DNN architecture for multi-class image classification. The original architecture is shown in blue; the changes introduced to make it PixelDP are shown in red. Denote $Q$ the original DNN’s scoring function; it is a deterministic map from images $x$ to a probability distribution over the $K$ labels $Q(x)=(y_{1}(x),\dotsc,y_{K}(x))$. The vulnerability to adversarial examples stems from the unbounded sensitivity of $Q$ with respect to $p$-norm changes in the input. Making the DNN $(\epsilon,\delta)$-PixelDP involves adding calibrated noise to turn $Q$ into an $(\epsilon,\delta)$-DP randomized function $A_{Q}$; the expected output of that function will have bounded sensitivity to $p$-norm changes in the input. We achieve this by introducing a noise layer (shown in red in Fig. 1(a)) that adds zero-mean noise to the output of the layer preceding it (layer1 in Fig. 1(a)). The noise is drawn from a Laplace or Gaussian distribution and its standard deviation is proportional to: (1) $L$, the $p$-norm attack bound for which we are constructing the network and (2) $\Delta$, the sensitivity of the pre-noise computation (the grey box in Fig. 1(a)) with respect to $p$-norm input changes.

Training an $(\epsilon,\delta)$-PixelDP network is similar to training the original network: we use the original loss and optimizer, such as stochastic gradient descent. The major difference is that we alter the pre-noise computation to constrain its sensitivity with regards to $p$-norm input changes. Denote $Q(x)=h(g(x))$, where $g$ is the pre-noise computation and $h$ is the subsequent computation that produces $Q(x)$ in the original network. We leverage known techniques, reviewed in §III-C, to transform $g$ into another function, $\tilde{g}$, that has a fixed sensitivity ($\Delta$) to $p$-norm input changes. We then add the noise layer to the output of $\tilde{g}$, with a standard deviation scaled by $\Delta$ and $L$ to ensure $(\epsilon,\delta)$-PixelDP for $p$-norm changes of size $L$. Denote the resulting scoring function of the PixelDP network: $A_{Q}(x)=h(\tilde{g}(x)+noise(\Delta,L,\epsilon,\delta))$, where $noise(.)$ is the function implementing the Laplace/Gaussian draw. Assuming that the noise layer is placed such that $h$ only processes the DP output of $\tilde{g}(x)$ without accessing $x$ again (i.e., no skip layers exist from pre-noise to post-noise computation), the post-processing property of DP ensures that $A_{Q}(x)$ also satisfies $(\epsilon,\delta)$-PixelDP for $p$-norm changes of size $L$.

Prediction on the $(\epsilon,\delta)$-PixelDP scoring function, $A_{Q}(x)$, affords the robustness certification in Proposition 1 if the prediction procedure uses the expected scores, $\mathbb{E}(A_{Q}(x))$, to select the winning label for any input $x$. Unfortunately, due to the potentially complex nature of the post-noise computation, $h$, we cannot compute this output expectation analytically. We therefore resort to Monte Carlo methods to estimate it at prediction time and develop an approximate version of the robustness certification in Proposition 1 that uses standard techniques from probability theory to account for the estimation error (§III-D). Specifically, given input $x$, PixelDP’s prediction procedure invokes $A_{Q}(x)$ multiple times with new draws of the noise layer. It then averages the results for each label, thereby computing an estimation $\hat{\mathbb{E}}(A_{Q}(x))$ of the expected score $\mathbb{E}(A_{Q}(x))$. It then computes an $\eta$-confidence interval for $\hat{\mathbb{E}}(A_{Q}(x))$ that holds with probability $\eta$. Finally, it integrates this confidence interval into the stability bound for the expectation of a DP computation (Lemma 1) to obtain $\eta$-confidence upper and lower bounds on the change an adversary can make to the average score of any label with a $p$-norm input change of size up to $L$. Fig. 1(b) illustrates the upper and lower bounds applied to the average score of each label by the PixelDP prediction procedure. If the lower bound for the label with the top average score is strictly greater than the upper bound for every other label, then, with probability $\eta$, the PixelDP network’s prediction for input $x$ is robust to arbitrary attacks of $p$-norm size $L$. The failure probability of this robustness certification, $1-\eta$, can be made arbitrarily small by increasing the number of invocations of $A_{Q}(x)$.

One can use PixelDP’s certification check in two ways: (1) one can decide only to actuate on predictions that are deemed robust to attacks of a particular size; or (2) one can compute, on a test set, a lower bound of a PixelDP network’s accuracy under $p$-norm bounded attack, independent of how the attack is implemented. This bound, called certified accuracy, will hold no matter how effective future generations of the attack are.

The remainder of this section details the noise layer, training, and certified prediction procedures. To simplify notation, we will henceforth use $A$ instead of $A_{Q}$.

The noise layer enforces $(\epsilon,\delta)$-PixelDP by inserting noise inside the DNN using one of two well-known DP mechanisms: the Laplacian and Gaussian mechanisms. Both rely upon the sensitivity of the pre-noise layers (function $g$). The sensitivity of a function $g$ is defined as the maximum change in output that can be produced by a change in the input, given some distance metrics for the input and output ($p$-norm and $q$-norm, respectively):

Assuming we can compute the sensitivity of the pre-noise layers (addressed shortly), the noise layer leverages the Laplace and Gaussian mechanisms as follows. On every invocation of the network on an input $x$ (whether for training or prediction) the noise layer computes $g(x)+Z$, where the coordinates $Z=(Z_{1},\dotsc,Z_{m})$ are independent random variables from a noise distribution defined by the function $noise(\Delta,L,\epsilon,\delta)$.

• •

  Laplacian mechanism: $noise(\Delta,L,\epsilon,\delta)$ uses the Laplace distribution with mean zero and standard deviation $\sigma=\sqrt{2}\Delta_{p,1}L/\epsilon$; it gives $(\epsilon,0)$-DP.

• •

  Gaussian mechanism: $noise(\Delta,L,\epsilon,\delta)$ uses the Gaussian distribution with mean zero and standard deviation $\sigma=\sqrt{2\ln(\frac{1.25}{\delta})}\Delta_{p,2}L/\epsilon$; it gives $(\epsilon,\delta)$-DP for $\epsilon\leq 1$.

Here, $L$ denotes the $p$-norm size of the attack against which the PixelDP network provides $(\epsilon,\delta)$-DP; we call it the construction attack bound. The noise formulas show that for a fixed noise standard deviation $\sigma$, the guarantee degrades gracefully: attacks twice as big halve the $\epsilon$ in the DP guarantee ($L\leftarrow 2L\Rightarrow\epsilon\leftarrow 2\epsilon$). This property is often referred as group privacy in the DP literature [18].

Computing the sensitivity of the pre-noise function $g$ depends on where we choose to place the noise layer in the DNN. Because the post-processing property of DP carries the $(\epsilon,\delta)$-PixelDP guarantee from the noise layer through the end of the network, a DNN designer has great flexibility in placing the noise layer anywhere in the DNN, as long as no skip connection exists from pre-noise to post-noise layers. We discuss here several options for noise layer placement and how to compute sensitivity for each. Our methods are not closely tied to particular network architectures and can therefore be applied on a wide variety of networks.

For linear layers, which consist of a linear operator with matrix form $W\in\mathbb{R}^{m,n}$, the sensitivity is the matrix norm, defined as: $\|W\|_{p,q}=\sup_{x:\|x\|_{p}\leq 1}\|Wx\|_{q}$. Indeed, the definition and linearity of $W$ directly imply that $\frac{\|Wx\|_{q}}{\|x\|_{p}}\leq\|W\|_{p,q}$, which means that: $\Delta_{p,q}=\|W\|_{p,q}$. We use the following matrix norms [64]: $\|W\|_{1,1}$ is the maximum $1$-norm of $W$’s columns; $\|W\|_{1,2}$ is the maximum $2$-norm of $W$’s columns; and $\|W\|_{2,2}$ is the maximum singular value of $W$. For $\infty$-norm attacks, we need to bound $\|W\|_{\infty,1}$ or $\|W\|_{\infty,2}$, as our DP mechanisms require $q\in\{1,2\}$. However, tight bounds are computationally hard, so we currently use the following bounds: $\sqrt{n}\|W\|_{2,2}$ or $\sqrt{m}\|W\|_{\infty,\infty}$ where $\|W\|_{\infty,\infty}$ is the maximum $1$-norm of $W$’s rows. While these bounds are suboptimal and lead to results that are not as good as for $1$-norm or $2$-norm attacks, they allow us to include $\infty$-norm attacks in our frameworks. We leave the study of better approximate bounds to future work.

For a convolution layer, which is linear but usually not expressed in matrix form, we reshape the input (e.g. the image) as an $\mathbb{R}^{nd_{in}}$ vector, where $n$ is the input size (e.g. number of pixels) and $d_{in}$ the number of input channels (e.g. $3$ for the RGB channels of an image). We write the convolution as an $\mathbb{R}^{nd_{out}\times nd_{in}}$ matrix where each column has all filter maps corresponding to a given input channel, and zero values. This way, a “column” of a convolution consists of all coefficients in the kernel that correspond to a single input channel. Reshaping the input does not change sensitivity.

This approach has two advantages. First, the auto-encoder can be developed independently of the DNN, separating the concerns of learning a good PixelDP model and a good predictive DNN. Second, PixelDP auto-encoders are much smaller than predictive DNNs, and are thus much faster to train. We leverage this property to train the first certified model for the large ImageNet dataset, using an auto-encoder and the pre-trained Inception-v3 model, a substantial relief in terms of experimental work (§IV-A).

The soundness of PixelDP’s certifications rely only on enforcing DP at prediction time. Theoretically, one could remove the noise layer during training. However, doing so results in near-zero certified accuracy in our experience. Unfortunately, training with noise anywhere except in the image itself raises a new challenge: left unchecked the training procedure will scale up the sensitivity of the pre-noise layers, voiding the DP guarantees.

To avoid this, we alter the pre-noise computation to keep its sensitivity constant (e.g. $\Delta_{p,q}\leq 1$) during training. The specific technique we use depends on the type of sensitivity we need to bound, i.e. on the values of $p$ and $q$. For $\Delta_{1,1}$, $\Delta_{1,2}$, or $\Delta_{\infty,\infty}$, we normalize the columns, or rows, of linear layers and use the regular optimization process with fixed noise variance. For $\Delta_{2,2}$, we run the projection step described in [12] after each gradient step from the stochastic gradient descent (SGD). This makes the pre-noise layers Parseval tight frames, enforcing $\Delta_{2,2}=1$. For the pre-noise layers, we thus alternate between an SGD step with fixed noise variance and a projection step. Subsequent layers from the original DNN are left unchanged.

It is important to note that during training, we optimize for a single draw of noise to predict the true label for a training example $x$. We estimate $\mathbb{E}(A(x))$ using multiple draws of noise only at prediction time. We can interpret this as pushing the DNN to increase the margin between the expected score for the true label versus others. Recall from Equation (4) that the bounds on predicted outputs give robustness only when the true label has a large enough margin compared to other labels. By pushing the DNN to give high scores to the true label $k$ at points around $x$ likely under the noise distribution, we increase $\mathbb{E}(A_{k}(x))$ and decrease $\mathbb{E}(A_{i\neq k}(x))$.

For a given input $x$, the prediction procedure in a traditional DNN chooses the $\arg\max$ label based on the score vector obtained from a single execution of the DNN’s deterministic scoring function, $Q(x)$. In a PixelDP network, the prediction procedure differs in two ways. First, it chooses the $\arg\max$ label based on a Monte Carlo estimation of the expected value of the randomized DNN’s scoring function, $\mathbb{\hat{E}}(A(x))$. This estimation is obtained by invoking $A(x)$ multiple times with independent draws in the noise layer. Denote $a_{k,n}(x)$ the $n^{th}$ draw from the distribution of the randomized function $A$ on the $k^{th}$ label, given $x$ (so $a_{k,n}(x)\sim A_{k}(x)$). In Lemma 1 we replace $\mathbb{E}(A_{k}(x))$ with $\mathbb{\hat{E}}(A_{k}(x))=\frac{1}{n}\sum_{n}a_{k,n}(x)$, where $n$ is the number of invocations of $A(x)$. We compute $\eta$-confidence error bounds to account for the estimation error in our robustness bounds, treating each label’s score as a random variable in $[0,1]$. We use Hoeffding’s inequality [25] or Empirical Bernstein bounds [39] to bound the error in $\mathbb{\hat{E}}(A(x))$. We then apply a union bound so that the bounds for each label are all valid together. For instance, using Hoeffding’s inequality, with probability $\eta$, $\mathbb{\hat{E}}^{lb}(A(x))\triangleq\mathbb{\hat{E}}(A(x))-\sqrt{\frac{1}{2n}ln(\frac{2k}{1-\eta})}\leq\mathbb{E}(A(x))\leq\mathbb{\hat{E}}(A(x))+\sqrt{\frac{1}{2n}ln(\frac{2k}{1-\eta})}\triangleq\mathbb{\hat{E}}^{ub}(A(x))$.

Second, PixelDP returns not only the prediction for $x$ ($\arg\max(\mathbb{\hat{E}}(A(x)))$) but also a robustness size certificate for that prediction. To compute the certificate, we extend Proposition 1 to account for the measurement error:

The proof is similar to the one for Proposition 1 and is detailed in Appendix A-A. Note that the DP bounds are not probabilistic even for $\delta>0$; the failure probability $1-\eta$ comes from the Monte Carlo estimate and can be made arbitrarily small with more invocations of $A(x)$.

Thus far, we have described PixelDP certificates as binary with respect to a fixed attack bound, $L$: we either meet or do not meet a robustness check for $L$. In fact, our formalism allows for a more nuanced certificate, which gives the maximum attack size $L_{max}$ (measured in $p$-norm) against which the prediction on input $x$ is guaranteed to be robust: no attack within this size from $x$ will be able to change the highest probability. $L_{max}$ can differ for different inputs. We compute the robustness size certificate for input $x$ as follows. Recall from III-B that the DP mechanisms have a noise standard deviation $\sigma$ that grows in $\frac{\Delta_{p,q}L}{\epsilon}$. For a given $\sigma$ used at prediction time, we solve for the maximum $L$ for which the robustness condition in Proposition 2 checks out:

The prediction on $x$ is robust to attacks up to $L_{max}$, so we award a robustness size certificate of $L_{max}$ for $x$.

We envision two ways of using robustness size certifications. First, when it makes sense to only take actions on the subset of robust predictions (e.g., a human can intervene for the rest), an application can use PixelDP’s certified robustness on each prediction. Second, when all points must be classified, PixelDP gives a lower bound on the accuracy under attack. Like in regular ML, the testing set is used as a proxy for the accuracy on new examples. We can certify the minimum accuracy under attacks up to a threshold size T, that we call the prediction robustness threshold. T is an inference-time parameter that can differ from the construction attack bound parameter, L, that is used to configure the standard deviation of the DP noise. In this setting the certification is computed only on the testing set, and is not required for each prediction. We only need the highest probability label, which requires fewer noise draws. §IV-E shows that in practice a few hundred draws are sufficient to retain a large fraction of the certified predictions, while a few dozen are needed for simple predictions.

Table II shows the PixelDP configurations we used for the $1$-norm and $2$-norm defenses. The code is available at https://github.com/columbia/pixeldp. Since most of this section focuses on models with $2$-norm attack bounds, we detail only those configurations here.

ImageNet: We use as baseline a pre-trained version of Inception-v3 [55] available in Tensorflow [22]. To make it PixelDP, we use the autoencoder approach from §III-B, which does not require a full retraining of Inception and was instrumental in our support of ImageNet. The encoder has three convolutional layers and tied encoder/decoder weights. The convolution kernels are $10\times 10\times 32$, $8\times 8\times 32$, and $5\times 5\times 64$, with stride $2$. We make the autoencoder PixelDP by adding the DP noise after the first convolution. We then stack the baseline Inception-v3 on the PixelDP autoencoder and fine-tune it for $20k$ steps, keeping the autoencoder weights constant.

CIFAR-10, CIFAR-100, SVHN: We use the same baseline architecture, a state-of-the-art Residual Network (ResNet) [70]. Specifically we use the Tensorflow implementation of a 28-10 wide ResNet [57], with the default parameters. To make it PixelDP, we slightly alter the architecture to remove the image standardization step. This step makes sensitivity input dependent, which is harder to deal with in PixelDP. Interestingly, removing this step also increases the baseline’s own accuracy for all three datasets. In this section, we therefore report the accuracy of the changed networks as baselines.

MNIST: We train a Convolutional Neural Network (CNN) with two $5\times 5$ convolutions (stride $2$, $32$ and $64$ filters) followed by a $1024$ nodes fully connected layer.

1. 1.

   Conventional accuracy $\frac{\sum_{i=1}^{n}isCorrect(x_{i})}{n}$, where $n$ is the testing set size and $isCorrect(x_{i})$ denotes a function returning 1 if the prediction on test sample $x_{i}$ returns the correct label, and 0 otherwise.

2. 2.

   Certified accuracy
   $\frac{\sum_{i=1}^{n}(isCorrect(x_{i})\&robustSize(scores,\epsilon,\delta,L)\geq T)}{n}$, where $robustSize(scores,\epsilon,\delta,L)$ returns the certified robustness size, which is then compared to the prediction robustness threshold T.

3. 3.

   Precision on certified examples $\frac{\sum_{i=1}^{n}(isCorrect(x_{i})\&robustSize(p_{i},\epsilon,\delta,L)\geq T))}{\sum_{i=1}^{n}robustSize(p_{i},\epsilon,\delta,L)\geq T)}$.

For $T=0$ all predictions are robust, so certified accuracy is equivalent to conventional accuracy. Each time we report $L$ or $T$, we use a $[0,1]$ pixel range.

For our evaluation, we use the state-of-the art attack from Carlini and Wagner [7], that we run for $9$ iterations of binary search, $100$ gradient steps without early stopping (which we empirically validated to be sufficient), and learning rate $0.01$. We also adapt the attack to our specific defense following [2]: since PixelDP adds noise to the DNN, attacks based on optimization may fail due to the high variance of gradients, which would not be a sign of the absence of adversarial examples, but merely of them being harder to find. We address this concern by averaging the gradients over $20$ noise draws at each gradient step. Appendix §A-C contains more details about the attack, including sanity checks and another attack we ran similar to the one used in [37].

Second, we compare with another approach for certified robustness against $\infty$-norm attacks [65], based on robust optimization. This method does not yet scale to the largest datasets (e.g. ImageNet), or the more complex DNNs (e.g. ResNet, Inception) both for computational reasons and because not all necessary layers are yet supported (e.g. BatchNorm). We thus use their largest released model/dataset, namely a CNN with two convolutions and a $100$ nodes fully connected layer for the SVHN dataset, and compare their robustness guarantees with our own networks’ robustness guarantees. We call this SVHN CNN model RobustOpt.

Q1: How does DP noise affect the conventional accuracy of our models? To answer, for each dataset we train up to four $(1.0,0.05)$-PixelDP DNN, for construction attack bound $L\in\{0.03,0.1,0.3,1\}$. Higher values of $L$ correspond to robustness against larger attacks and larger noise standard deviation $\sigma$.

Table III shows the conventional accuracy of these networks and highlights two parts of an answer to Q1. First, at fairly low but meaningful construction attack bound (e.g., $L=0.1$), all of our DNNs exhibit reasonable accuracy loss – even on ImageNet, a dataset on which no guarantees have been made to date! ImageNet: The Inception-v3 model stacked on the PixelDP auto-encoder has an accuracy of 68.3% for $L=0.1$, which is reasonable degradation compared to the baseline of 77.5% for the unprotected network. CIFAR-10: Accuracy goes from 95.5% without defense to 87% with the $L=0.1$ defense. For comparison, the Madry model has an accuracy of 87.3% on CIFAR-10. SVHN: our $L=0.1$ PixelDP network achieves 93.1% conventional accuracy, down from 96.3% for the unprotected network. For comparison, the $L=0.1$ RobustOpt network has an accuracy of 79.6%, although they use a smaller DNN due to the computationally intensive method.

Second, as expected, constructing the network for larger attacks (higher $L$) progressively degrades accuracy. ImageNet: Increasing $L$ to $0.3$ and then $1.0$ drops the accuracy to 57.7% and 37.7%, respectively. CIFAR-10: The ResNet with the least noise ($L=0.03$) reaches $93.3\%$ accuracy, close to the baseline of $95.5\%$; increasing noise levels ($L=(0.1,0.3,1.0)$) yields $87\%$, $70.9\%$, and $37.7\%$, respectively. Yet, as shown in §IV-D, PixelDP networks trained with fairly low $L$ values (such as $L=0.1$) already provide meaningful empirical protection against larger attacks.

Q2: What accuracy can PixelDP certify on a test set? Fig. 2 shows the certified robust accuracy bounds for ImageNet and CIFAR-10 models, trained with various values of the construction attack bound $L$. The certified accuracy is shown as a function of the prediction robustness threshold, $T$. We make two observations. First, PixelDP yields meaningful robust accuracy bounds even on large networks for ImageNet (see Fig. 2(a)), attesting the scalability of our approach. The $L=0.1$ network has a certified accuracy of 59% for attacks smaller than $0.09$ in $2$-norm. The $L=0.3$ network has a certified accuracy of 40% to attacks up to size $0.2$. To our knowledge, PixelDP is the first defense to yield DNNs with certified bounds on accuracy under $2$-norm attacks on datasets of ImageNet’s size and for large networks like Inception.

Second, PixelDP networks constructed for larger attacks (higher $L$, hence higher noise) tend to yield higher certified accuracy for high thresholds $T$. For example, the ResNet on CIFAR-10 (see Fig. 2(b)) constructed with $L=0.03$ has the highest robust accuracy up to $T=0.03$, but the ResNet constructed with $L=0.1$ becomes better past that threshold. Similarly, the $L=0.3$ ResNet has higher robust accuracy than the $L=0.1$ ResNet above the $0.14$ $2$-norm prediction robustness threshold.

We ran the same experiments on SVHN, CIFAR-100 and MNIST models but omit the graphs for space reasons. Our main conclusion – that adding more noise (higher $L$) hurts both conventional and low $T$ certified accuracy, but enhances the quality of its high $T$ predictions – holds in all cases. Appendix A-B discusses the impact of some design choices on robust accuracy, and Appendix A-D discusses PixelDP guarantees as compared with previous certified defenses for $\infty$-norm attacks. While PixelDP does not yet yield strong $\infty$-norm bounds, it provides meaningful certified accuracy bounds for $2$-norm attacks, including on much larger and more complex datasets and networks than those supported by previous approaches.

A standard method to evaluate the strength of a defense is to measure the conventional accuracy of a defended model on malicious samples obtained by running a state-of-the-art attack against samples in a held-out testing set [37]. We apply this method to answer three aspects of question Q3: (1) Can PixelDP help defend complex models on large datasets in practice? (2) How does PixelDP’s accuracy under attack compare to state-of-the-art defenses? (3) How does the accuracy under attack change for certified predictions?

Thus, for applications that can afford to not act on a minority of the predictions, PixelDP’s robust predictions under 2-norm attack are substantially more precise than Madry’s. For applications that need to act on every prediction, PixelDP offers on-par accuracy under 2-norm attack to Madry’s. Interestingly, although our defense is trained for $2$-norm attacks, the first conclusion still holds for $\infty$-norm attacks; the second (as we saw) does not.

Q4: What is PixelDP’s computational overhead? We evaluate overheads for training and prediction. PixelDP adds little overhead for training, as the only additions are a random noise tensor and sensitivity computations. On our GPU, the CIFAR-10 ResNet baseline takes on average $0.65s$ per training step. PixelDP versions take at most $0.66s$ per training step (1.5% overhead). This represents a significant benefit over adversarial training (e.g. Madry) that requires finding good adversarial attacks for each image in the mini-batch at each gradient step, and over robust optimization (e.g. RobustOpt) that requires solving a constrained optimization problem at each gradient step. The low training overhead is instrumental to our support of large models and datasets.

PixelDP impacts prediction more substantially, since it uses multiple noise draws to estimate the label scores. Making a prediction for a single image with $1$ noise draw takes $0.01s$ on average. Making $10$ draws brings it only to $0.02s$, but $100$ requires $0.13s$, and $1000$, $1.23s$. It is possible to use Hoeffding’s inequality [25] to bound the number of draws necessary to distinguish the highest score with probability at least $\eta$, given the difference between the top two scores $y_{max}-y_{second-max}$. Empirically, we found that $300$ draws were typically necessary to properly certify a prediction, implying a prediction time of $0.42s$ seconds, a $42\times$ overhead. This is parallelizable, but resource consumption is still substantial. To make simple predictions – distinguish the top label when we must make a prediction on all inputs – 25 draws are enough in practice, reducing the overhead to $3\times$.