Certified Robustness to Label-Flipping Attacks via Randomized Smoothing

Introduction

Modern classifiers, despite their widespread empirical success, are known to be susceptible to adversarial attacks. In this paper, we are specifically concerned with so-called “data poisoning” attacks (formally, causative attacks [Barreno et al. 2006; Papernot et al. 2018]), where the attacker manipulates some aspects of the training data in order to cause the learning algorithm to output a faulty classifier. Automated machine-learning systems which rely on large, user-generated datasets—e.g. email spam filters, product recommendation engines, and fake review detectors—are particularly susceptible to such attacks. For example, by maliciously flagging legitimate emails as spam and mislabeling spam as innocuous, an adversary can trick a spam filter into mistakenly letting through a particular email.

Data poisoning attacks in the literature include label-flipping attacks (Xiao et al., 2012), where the labels of a training set can be adversarially manipulated to decrease performance of the trained classifier; general data poisoning, where both the training inputs and labels can be manipulated (Steinhardt et al., 2017); and backdoor attacks (Chen et al., 2017; Tran et al., 2018), where the training set is corrupted so as to cause the classifier to deviate from its expected behavior only when triggered by a specific pattern. However, unlike the alternative test-time adversarial setting, where reasonably effective provable defenses exist, comparatively little work has been done on building classifiers that are certifiably robust to targeted data poisoning attacks.

In this work we propose a framework for building classifiers that are certifiably robust to a given class of data poisoning attacks, such as label-flipping or backdoor attacks. In particular, we propose what we refer to as a pointwise certified defense—this means that with each prediction, the classifier includes a certificate guaranteeing that its prediction would not be different had it been trained on adversarially manipulated data up to some “radius of perturbation” (a formal definition is presented in Section 3). We then demonstrate a specific instantiation of this protocol, constructing linear classifiers that are pointwise-certifiably robust to label-flipping attacks; i.e., each prediction is certified robust against a certain number of training label flips.

Prior works on certified defenses make statistical guarantees over the entire test distribution, but they make no guarantees as to the robustness of a prediction on any particular test point; thus, a determined adversary could still cause a specific test point to be misclassified. We therefore consider the threat of a worst-case adversary that can make a training set perturbation to target each test point individually. This motivates a defense that can certify each of its individual predictions, as we present here. Compared to traditional robust classification, this framework is superior for a task such as determining who receives a coveted resource (a loan, parole, etc.), as it provides a guarantee for each individual, rather than at the population level. This work represents the first such pointwise certified defense to any type of data poisoning attack; we expect significant advances can be made on both attacks and defenses within this threat model.

Our approach leverages randomized smoothing (Cohen et al., 2019), a technique that has previously been used to guarantee test-time robustness to adversarial manipulation of the input to a deep network. However, where prior uses of randomized smoothing randomize over the input to the classifier for test-time guarantees, we instead randomize over the entire training procedure of the classifier. Specifically, by randomizing over the labels during this training process, we obtain an overall classification pipeline that is certified to not change its prediction when some number of labels are adversarially manipulated in the training set. Previous applications of randomized smoothing perform sampling to provide probabilistic bounds, due to the intractability of integrating the decision regions of a deep network. We instead derive an analytical bound, providing truly guaranteed robustness. Although a naive implementation of this approach would not be tractable, we show how to obtain these certified bounds with minimal additional runtime complexity over standard classification, suffering only a linear cost in the number of training points.

A further distinction of our approach is that the applicability of our robustness guarantees do not rely upon stringent model assumptions or the quality of the features. Existing work on robust linear classification or regression provides certificates that only hold under specific model assumptions, e.g., recovering the best-fit linear coefficients, which is most useful when the data exhibit a linear relationship in the feature space. In contrast, our classifier makes no assumptions about the separability of the data or quality of the features; this means our certificates remain valid when applying our classifier to arbitrary features, which in practice allows us to leverage advances in unsupervised feature learning (Le, 2013; Chen et al., 2020) and transfer learning (Donahue et al., 2014). We apply our classifier to pre-trained and unsupervised deep features to demonstrate its feasibility for classification of highly non-linear data such as ImageNet.

We evaluate our proposed classifier on several benchmark datasets common to the data poisoning literature. On the Dogfish binary classification challenge from ImageNet, our classifier maintains 81.3% certified accuracy in the face of an adversary who could reduce an undefended classifier to less than 1%. Additional experiments on MNIST and CIFAR10 demonstrate our algorithm’s effectiveness for multi-class classification. Moreover, our classifier maintains a reasonably competitive non-robust accuracy (e.g., 94.5% on MNIST 1/7 versus 99.1% for the undefended classifier).

Related Work

A data poisoning attack (Muñoz González et al., 2017; Yang et al., 2017) is an attack where an adversary corrupts some portion of the training set or adds new inputs, with the goal of degrading the performance of the learned model. The adversary is assumed to have perfect knowledge of the learning algorithm, so security by design—as opposed to obscurity—is the only viable defense against such attacks. The adversary is also typically assumed to have access to the training set and, in some cases, the test set.

Previous work has investigated attacks and defenses for data poisoning attacks applied to feature selection (Xiao et al., 2015), SVMs (Biggio et al., 2011; Xiao et al., 2012), linear regression (Liu et al., 2017), and PCA (Rubinstein et al., 2009), to name a few. Some attacks can even achieve success with “clean-label” attacks, inserting adversarially perturbed, seemingly correctly labeled training examples that cause the classifier to perform poorly (Shafahi et al., 2018; Zhu et al., 2019). Interestingly, our defense can also be viewed as (the first) certified defense to such attacks: perturbing an image such that the resulting features no longer match the label is theoretically equivalent to changing the label such that it no longer matches the image’s features. For an overview of data poisoning attacks and defenses in machine learning, see Biggio et al. (2014).

Label-flipping attacks

A label-flipping attack is a specific type of data poisoning attack where the adversary is restricted to changing the training labels. The classifier is then trained on the corrupted training set, with no knowledge of which labels have been tampered with. For example, an adversary could mislabel spam emails as innocuous, or flag real product reviews as fake.

Unlike random label noise, for which many robust learning algorithms have been successfully developed (Natarajan et al., 2013; Liu & Tao, 2016; Patrini et al., 2017), adversarial label-flipping attacks can be specifically targeted to exploit the structure of the learning algorithm, significantly degrading performance. Robustness to such attacks is therefore harder to achieve, both theoretically and empirically (Xiao et al., 2012; Biggio et al., 2011). A common defense technique is sanitization, whereby a defender attempts to identify and remove or relabel training points that may have had their labels corrupted (Paudice et al., 2019; Taheri et al., 2019). Unfortunately, recent work has demonstrated that this is often not enough against a sufficiently powerful adversary (Koh et al., 2018). Further, no existing defenses provide pointwise guarantees regarding their robustness.

Certified defenses

Existing works on certified defenses to adversarial data poisoning attacks typically focus on the regression case and provide broad statistical guarantees over the entire test distribution. A common approach to such certifications is to show that a particular algorithm recovers some close approximation to the best linear fit coefficients (Diakonikolas et al., 2019; Prasad et al., 2018; Shen & Sanghavi, 2019), or that the expected loss on the test distribution is bounded (Klivans et al., 2018; Chen & Paschalidis, 2018). These results generally rely on assumptions on the data distribution: some assume sparsity in the coefficients (Karmalkar & Price, 2018; Chen et al., 2013) or corruption vector (Bhatia et al., 2015); others require limited effects of outliers (Steinhardt et al., 2017). As mentioned above, all of these methods fail to provide guarantees for individual test points. Additionally, these statistical guarantees are not as meaningful when their model assumptions do not hold.

Randomized smoothing

Since the discovery of adversarial examples (Szegedy et al., 2013; Goodfellow et al., 2015), the research community has been investigating techniques for increasing the adversarial robustness of complex models such as deep networks. After a series of heuristic defenses, followed by attacks breaking them (Athalye et al., 2018; Carlini & Wagner, 2017), focus began to shift towards the development of provable robustness.

A General View of Randomized Smoothing

where $\mathbf{1}\{\cdot\}$ is the indicator function. Where it is clear from context, we will omit the arguments, writing simply $G$ or $g$. Intuitively, for two similar measures $\mu,\rho$, we would expect that for most $\phi$, even though $G(\mu,\phi)$ and $G(\rho,\phi)$ may not be equal, the threshold function $g$ should satisfy $g(\mu,\phi)=g(\rho,\phi)$. Further, the degree to which $\mu$ and $\rho$ can differ while still preserving this property should increase as $G(\mu,\phi)$ approaches either 0 or 1, because this increases the “margin” with which the function $\phi$ is 0 or 1 respectively over the measure $\mu$. More formally, we define a general randomized smoothing guarantee as follows:

Informally, (1) says that the majority vote winner of $\phi$ weighted by $\mu$ and $\rho$ will be the same, so long as $\mu$ and $\rho$ are “close enough” as a function of the margin with which the majority wins. We will sometimes use $p$ in place of $G(\mu,\phi)$, representing the fraction of the vote that the majority class receives (analogous to $p_{A}$ in Cohen et al. (2019)).

This definition is rather abstract, so we highlight concrete examples of how it can be applied to achieve certified guarantees against adversarial attacks.

The randomized smoothing guarantee of Cohen et al. (2019) uses the smoothing measures $\mu=\mathcal{N}(x_{0},\sigma^{2}I)$, a Gaussian aroound the point $x_{0}$ to be classified, and $\rho=\mathcal{N}(x_{0}+\delta,\sigma^{2}I)$, the same measure perturbed by $\delta$. They prove that (1) holds for all classifiers $\phi$ if we define

Although this work focused on the case of randomized smoothing of continuous data via Gaussian noise, this is by no means a requirement. Lee et al. (2019) consider an alternative approach for dealing with discrete variables.

with $\mathbf{x}_{i}$ being the $i^{th}$ dimension of $\mathbf{x}$. $\rho_{\alpha,K}$ is similarly defined for a perturbed input $\mathbf{z}^{\prime}$. They guarantee that (1) holds if we define

In words, the smoothing distribution is such that each dimension is independently perturbed to one of the other $K$ values uniformly at random with probability $1-\alpha$. $\mathcal{F}_{\alpha,K,d}(p)$ is a combinatorial function defined as the maximum number of dimensions—out of $d$ total—by which $\mu_{\alpha,K}$ and $\rho_{\alpha,K}$ can differ such that a set with measure $p$ under $\mu_{\alpha,K}$ is guaranteed to have measure at least $\frac{1}{2}$ under $\rho_{\alpha,K}$. Lee et al. (2019) prove that this value depends only on $\|\mathbf{z}^{\prime}-\mathbf{z}\|_{0}$.

Finally, Dvijotham et al. (2020) consider a more general form of randomized smoothing that doesn’t require strict assumptions on the distributions but is still able to provide similar guarantees.

Given any two smoothing distributions $\mu,\rho$, we have the generic randomized smoothing robustness certificate, ensuring that (1) holds with definitions

Randomized smoothing in practice

For deep classifiers, the expectation $G$ cannot be computed exactly, so we must resort to Monte Carlo approximation. This is done by drawing samples from $\mu$ and using these to construct a high-probability bound on $G$ for certification. More precisely, this bound should be a lower bound on $G$ when the hard prediction $g=1$ and an upper bound otherwise; this ensures in both cases that we under-certify the true robustness of the classifier $g$. The procedure is shown in Algorithm 2 in Appendix A. These estimates can then be plugged into a randomized smoothing robustness guarantee to provide a high probability certified robustness bound for the classifier.

Pointwise Data Poisoning Robustness

We now present the main contributions of this paper: we first describe a generic strategy for applying randomized smoothing to certify a prediction function against arbitrary classes of data poisoning attacks. We then propose a specific implementation of said strategy to certify a classifier against label-flipping attacks. We show how this approach can be made tractable using linear least-squares classification, and we use the Chernoff inequality to analytically bound the relevant probabilities for the randomized smoothing certificate. Notably, although we are employing a randomized approach, the final algorithm does not use any random sampling, but rather relies upon a convex optimization problem to compute the certified robustness.

We begin by noting that in prior work, randomized smoothing was applied at test time with the function $\phi:\mathcal{X}\to\{0,1\}$ being a (potentially deep) classifier that we wish to smooth. However, there is no requirement that the function $\phi$ be a classifier at all; the theory holds for any binary-valued function. Instead of treating $\phi$ as a trained classifier, we consider $\phi$ to be an arbitrary learning algorithm which takes as input a training dataset $\{x_{i},y_{i}\}_{i=1}^{n}\in(\mathcal{X}\times\{0,1\})^{n}$ and additional test points without corresponding labels, which we aim to predict.Note that our algorithm does not require access to the test data to do the necessary precomputation. We present it here as such merely to give an intuitive idea of the procedure. In other words, the combined goal of $\phi$ is to first train a classifier and then predict the label of the new example. Thus, we consider test time outputs to be a function of both the test time input and the training data that produced the classifier. This perspective allows us to reason about how changes to training data affect the classifier at test time, reminiscent of work on influence functions of deep neural networks (Koh & Liang, 2017; Yeh et al., 2018).

This immediately suggests our protocol for pointwise robustness to general data poisoning attacks: randomize over the elements of the input to which we desire certified robustness, rather than over the test-time input to be classified. For example, to induce robustness to backdoor attacks, we could randomly add noise to the training points and/or their labels. Analogous to previous applications of randomized smoothing, if the majority vote of the classifiers trained with these randomly perturbed inputs has a large margin, it will confer a degree of robustness within an appropriately-defined radius of adversarially perturbed training data (as defined in Equation 1).

Specific application to label-flipping robustness

To demonstrate the effectiveness of our proposed strategy, we now present a specific implementation, providing an algorithm for tractable linear classification which is pointwise-certifiably robust to label-flipping attacks. When applying randomized smoothing in this setting, we randomize over the labels in the training set as described above—a suitably large margin in the majority vote will therefore result in pointwise robustness to adversarial label flips. In this scenario, the adversarial “radius” is defined as number of labels on which two training sets differ.

Plugging in the robustness guarantee (3), we have that $g(\mu,\phi)=g(\rho,\phi)$ so long as

where $p=G(\mu,\phi)$. This implies that for any test point, as long as (5) is satisfied, $g$’s prediction (the majority vote weighted by the smoothing distribution) will not change if an adversary corrupts the training set from $Y_{1}$ to $Y_{2}$, or indeed to any other training set that differs on at most $r$ labels. We can tune the noise hyperparameter $q$ to achieve the largest possible upper bound in (5); more noise will likely decrease the margin of the majority vote $p$, but it will also decrease the divergence.

Computing a tight bound

This approach has a simple closed form, but the bound is not tight. We can derive a tight bound via a combinatorial approach as in Lee et al. (2019). By precomputing the quantities $\mathcal{F}^{-1}_{1-q,1,n}(r)$ from Equation (2) for each $r$, we can simply compare $p$ to each of these and thereby certify robustness to the highest possible number of label flips. This precomputation can be expensive, but it provides a significantly tighter robustness guarantee, certifying approximately twice as many label flips for a given bound on $G$ (See Figure E.3 in the Appendix).

1 Efficient implementation via least squares classifiers

There may appear to be one major impracticality of the algorithm proposed in the previous section, if considered naively: treating the function $\phi$ as an entire training-plus-single-prediction process would require that we train multiple classifiers, over multiple random draws of the labels $y$, all to make a prediction on a single example. In this section, we describe a sequence of tools we employ to restrict the architecture and training process in a manner that drastically reduces this cost, bringing it in line with the traditional cost of standard classification. The full procedure, with all the parts described below, can be found in Algorithm 1.

The real advantage of the least-squares approach is that it reduces the prediction to a linear function of $\mathbf{y}$, and thus randomizing over the labels is straightforward. Specifically, letting

the prediction $h(x_{n+1})\hat{\boldsymbol{\beta}}$ can be equivalently given by $\boldsymbol{\alpha}^{T}\mathbf{y}$ (this is effectively the kernel representation of the linear classifier). Thus, we can simply compute $\boldsymbol{\alpha}$ one time and then randomly sample many different sets of labels in order to build a standard randomized smoothing bound. Further, we can pre-compute just the $\mathbf{X}\left(\mathbf{X}^{T}\mathbf{X}\right)^{-1}$ term and reuse it for each test point.

The other parts of our algorithm remain unchanged. Following results in Suggala et al. (2018), we set the regularization parameter $\lambda=(1+q)\frac{\hat{\sigma}^{2}k}{2n}\kappa(\mathbf{X}^{T}\mathbf{X})$ for all our experiments, where $\hat{\sigma}^{2}=\frac{\|\mathbf{y}-\mathbf{X}\hat{\boldsymbol{\beta}}_{OLS}\|_{2}^{2}}{n-k}$ is an estimate of the variance (Dicker, 2014) and $\kappa(\cdot)$ is the condition number.

Efficient tail bounds via the Chernoff inequality

Even more compelling, due to the linear structure of this prediction, we can forego a sampling-based approach entirely and directly bound the tail probabilities using Chernoff bounds. Because the underlying binary prediction function $\phi$ will output the label $1$ for the test point whenever $\boldsymbol{\alpha}^{T}\mathbf{y}\geq 1/2$ and otherwise, we can derive an analytical upper bound on the probability that $g$ predicts one label or the other via the Chernoff bound. By upper bounding the probability of the opposite prediction, we simultaneously derive a lower bound on $p$ which can be plugged in to (5) to determine the classifier’s robustness. Concretely, we can upper bound the probability that the classifier outputs the label 0 by

Conversely, the probability that the classifier outputs the label 1 is upper bounded by (6) but evaluated at $-t$. Thus, we can solve the minimization problem unconstrained over $t$, and then let the sign of $t$ dictate which label to predict and the value of $t$ determine the bound. The objective (6) is log-convex in $t$ and can be easily solved by Newton’s method. Note that in some cases, neither Chernoff upper bound will be less than $1/2$, meaning we cannot determine the true value of $g$. In these cases, we simply define the classifier’s prediction to be determined by the sign of $t$. While we can’t guarantee that this classification will match the true majority vote, our algorithm will certify a robustness to 0 flips, so the guarantee is still valid. We avoid abstaining so as to assess our classifier’s non-robust accuracy.

The key property we emphasize is that, unlike previous randomized smoothing applications, the final algorithm involves no randomness whatsoever. Instead, the probabilities are bounded directly via the Chernoff bound, without any need for Monte Carlo approximation. Thus, the method is able to generate truly certifiable robust predictions using approximately the same complexity as traditional predictions.

Experiments

Following Koh & Liang (2017) and Steinhardt et al. (2017), we perform experiments on MNIST 1/7, the IMDB review sentiment dataset (Maas et al., 2011), and the Dogfish binary classification challenge taken from ImageNet. We run additional experiments on multi-class MNIST and CIFAR10. For each dataset and each noise level $q$ we report the certified test set accuracy at $r$ training label flips. That is, for each possible number of flips $r$, we plot the fraction of the test set that was both correctly classified and certified to not change under at least $r$ flips.

As mentioned, our classifier suffers an additional linear cost in the number of training points due to the kernel representation $\boldsymbol{\alpha}^{T}\mathbf{y}$. For most datasets there was no discernible difference in the time required to certify an input via our technique versus neural network classification. For larger training sets such as CIFAR10, especially when doing pairwise comparisons for the multi-class case, the algorithm is embarassingly parallel; this parallelism brings runtime back in line with standard classification.

For binary classification, one could technically achieve a certified accuracy of 50% at $r=\infty$ (or 10% for MNIST or CIFAR10) by letting $g$ be constant—a constant classifier would be infinitely robust. Though not a very meaningful baseline, we include the accuracy of such a classifier in our plots (black dotted line) as a reference. We also evaluated our classifier with $q=0$ (black dash-dot line); this cannot certify robustness, but it indicates the quality of the features.

To properly justify the need for such certified defenses, and to get a sense of the scale of our certifications, we generated label-flipping attacks against the undefended binary MNIST and Dogfish models. Following previous work, the undefended models were implemented as convolutional neural networks, trained on the clean data, with all but the top layer frozen—this is equivalent to multinomial logistic regression on the learned features. For each test point we recorded how many flips were required to change the network’s prediction. This number serves as an upper bound for the robustness of the network on that test point, but we note that our attacks were quite rudimentary and could almost certainly be improved upon to tighten this upper bound. Appendix C.1 contains the details of our attack implementations. Finally, we implemented attacks on our own defense to derive an empirical upper bound and found that it reasonably tracks our lower bound. Plots and details of this attack can be found in Appendix C.2.

In all plots, the solid lines represent certified accuracy (except for the undefended classifier, which is an upper bound), while the dashed lines of the same color are the overall non-robust accuracy of each classifier.

The MNIST 1/7 dataset (LeCun et al., 1998) consists of just the classes 1 and 7, totalling 13,007 training points and 2,163 test points. We trained a simple convolutional neural network on the other eight MNIST digits to learn a 50-dimensional feature embedding and then calculated Chernoff bounds for $G$ as described in Section 4.1. Figure 1(a) displays the certified accuracy on the test set for varying probabilities $q$. As in prior work on randomized smoothing, the noise parameter $q$ balances a trade-off; as $q$ increases, the required margin $|G-\frac{1}{2}|$ to certify a given number of flips decreases. On the other hand, this results in more noisy training labels, which reduces the margin and therefore results in lower robustness and often lower accuracy. Figure 1(b) depicts the certified accuracy for the full MNIST test set—see Appendix B for derivations of the bounds and optimization algorithm in the multi-class case. In addition to this being a significantly more difficult classification task, our classifier could not rely on features learned from other handwritten digits; instead, we extracted the top 30 components with ICA (Hyvarinen, 1999) independently of the labels. Despite the lack of fine-tuned features, our algorithm still achieves significant certified accuracy under a large number of adversarial label flips.

Results on CIFAR10

To further demonstrate the effectiveness of our classifier with unsupervised features, we used SimCLR (Chen et al., 2020) to learn unsupervised features for CIFAR10. We used PCA to reduce the features to 128 dimensions to reduce overfitting. Figure 2 shows the results: our classifier with $q=0.12$ achieves 50% certified accuracy up to 175 labels flips (recall there are ten classes, not two) and decays gracefully. Further, the classifier maintains better than random chance certified accuracy up to 427 label flips, which is approximately 1% of the training set.

Because the “votes” are changed by flipping so few labels, high values of $q$ reduce the models’ predictions to almost pure chance—this means we are unable to achieve the margins necessary to certify a large number of flips. We therefore found that smaller levels of noise achieved higher certified test accuracy. This suggests that the more susceptible the original, non-robust classifier is to label flips, the lower $q$ should be set for the corresponding randomized classifier.

For much smaller values of $q$, slight differences did not decrease the non-robust accuracy—they did however have a large effect on certified robustness. This indicates that the sign of $t^{\star}$ is relatively stable, but the margin of $G$ is much less so. This same pattern was observed with the IMDB and Dogfish datasets. We used a high-precision arithmetic library (Johansson et al., 2013) to achieve the necessary lower bounds, but the precision required for non-vacuous bounds grew extremely fast for $q<10^{-4}$; optimizing (6) quickly became too computationally expensive.

Results on Dogfish

The Dogfish dataset contains images from the ImageNet dog and fish synsets, 900 training points and 300 test points from each. We trained a ResNet-50 (He et al., 2016) on the standard ImageNet training set but removed all images labeled dog or fish. Our pre-trained network therefore learned meaningful image features but had no features specific to either class. We again used PCA to reduce the feature space dimensionality. Figure 3 displays the results of our poisoning attack along with our certified defense. Under the undefended model, more than 99% of the test points can be successfully attacked with no more than 23 label flips, whereas our model with $q=10^{-4}$ can certifiably correctly classify 81.3% of the test points under the same threat model. It would take more than four times as many flips—more than 5% of the training set—for each test point individually to reduce our classifier to less than 50% certified accuracy.

Here we observe the same pattern, where reducing $q$ does not have a large effect on non-robust accuracy but does increase robustness significantly. This provides further evidence for the hypothesis that more complex datasets/classifiers are more susceptible to attacks and should be smoothed with less label noise.

Figure E.2 in the Appendix shows our classifier’s performance with unsupervised features. Because Dogfish is such a small dataset ($n=1800$), deep unsupervised feature learning techniques were not feasible—we instead learned overcomplete features on 16x16 image patches using RICA (Le, 2013).

Results on IMDB

Figure 4 plots the result of our randomized smoothing procedure on the IMDB review sentiment dataset. This dataset contains 25,000 training examples and 25,000 test examples, evenly split between “positive” and “negative”. To extract the features we applied the Google News pre-trained Word2Vec to all the words in each review and averaged them. This feature embedding is considerably noisier than that of an image dataset, as most of the words in a review are irrelevant to sentiment classification. Indeed, Steinhardt et al. (2017) also found that the IMDB dataset was much more susceptible to adversarial corruption than images when using bag-of-words features. Consistent with this, we found smaller levels of noise resulted in larger certified accuracy. We expect significant improvements could be made with a more refined choice of feature embedding.

Conclusion

In this work we presented a unifying view of randomized smoothing, which borrows from the literature of differential privacy in order to provide black-box certificates of robustness. Based on the observation that this framework is applicable more broadly than just defenses to adversarial examples, we used it to derive a framework for certified defenses against arbitrary data poisoning attacks—we dub such defenses “pointwise” because they provide a certificate of robustness for each test point.

We next implemented this protocol as a specific classifier which is robust to a strong class of label-flipping attacks, where an adversary can flip labels to target each test point individually. This contrasts with previous data poisoning defenses which have typically only considered an adversary who wishes to degrade the classifier’s accuracy on the test distribution as a whole. Finally, we offered a tractable algorithm for evaluating this classifier which, despite being rooted in randomization, can be computed with no Monte Carlo sampling whatsoever, resulting in a truly certifiably robust classifier. This work represents the first classification algorithm that is pointwise-certifiably robust to any type of data poisoning attack; we anticipate many possible new directions within this framework.

A particular strength of this framework is when we specifically care about robustly classifying each input individually. Compared to traditional robust classification, this technique is superior for determining who receives a coveted resource (a loan, parole, etc.) or for making some other sensitive classification, as it provides a guarantee for each individual. Other works only ensure that they correctly classify some fraction $p$ of the population, which is often not acceptable as that still leaves the $1-p$ fraction who could be misclassified, with no indication of which ones belong to the test set.

There are several avenues for improvements to this line of work. Most immediately, our protocol could be implemented with other types of smoothing distributions applied to the training data, such as randomizing over the input data or features, to derive specific algorithms that are pointwise-certifiably robust to other types of data poisoning attacks. Additionally, the method for learning the input features in an unsupervised, semi-supervised, or self-supervised manner could be improved. Finally, we hope that our defense to this threat model will inspire the development of more powerful (e.g., pointwise) train-time attacks, against which future defenses can be evaluated.

Acknowledgements

We thank Guang-He Lee for sharing his code on discrete robustness certificates, Adarsh Prasad for several helpful sources on robust linear regression and classification, and Alnur Ali for pointing us to Dicker (2014) for help choosing the appropriate regularization term. We are grateful to Jeremy Cohen and Adarsh Prasad for helpful discussions and reviewing drafts of this work. E. R. and P. R. acknowledge the support of DARPA via HR00112020006.

References

Appendix A Generic Randomized Smoothing Algorithm

Appendix B The Multi-Class Setting

Although the notation and algorithms are slightly more complex, all the methods we have discussed in the main paper can be extended to the multi-class setting. In this case, we consider a class label $y\in\{1,\ldots,K\}$, and we again seek some smoothed prediction such that the classifier’s prediction on a new point will not change with some number $r$ flips of the labels in the training set.

We here extend our notation to the case of more than two classes. Recall our original definition of $G$,

where $\phi:\mathcal{X}\to\{0,1\}$. More generally, consider a classifier $\phi:\mathcal{X}\to[K]$, outputting the index of one of $K$ classes. Under this formulation, for a given class $c\in[K]$, we have

where $\phi_{c}(x)=\mathbf{1}\left\{\phi(x)=c\right\}$ is the indicator function for if $\phi(x)$ outputs the class $c$. In this case, the hard threshold $g$ is evaluated by returning the class with the highest probability. That is,

B.2 Linearization and Chernoff bound approach for the multi-class case

Using the same linearization approach as in the binary case, we can formulate an analogous approach which forgoes the need to actually perform random sampling at all and instead directly bounds the randomized classifier using the Chernoff bound.

Adopting the same notation as in the main text, the equivalent least-squares classifier for the multi-class setting finds some set of weights

Alternatively, following the same logic as in the binary case, this same prediction can be written in terms of the $\boldsymbol{\alpha}$ variable as

where $\mathbf{Y}_{i}$ denotes the $i$th column of $\mathbf{Y}_{i}$.

In our randomized smoothing setting, we again propose to flip the class of any label with probability $q$, selecting an alternative label uniformly at random from the remaining $K-1$ labels. Assuming that the predicted class label is $i$, we wish to bound the probability that

for all alternative classes $i^{\prime}$. By the Chernoff bound, we have that

The random variable $\mathbf{Y}_{ji}-\mathbf{Y}_{ji^{\prime}}$ takes on three different distributions depending on if $y_{j}=i$, if $y_{j}=i^{\prime}$, or if $y_{j}\neq i$ and $y_{j}\neq i^{\prime}$. Specifically, this variable can take on the terms $+1,0,-1$ with the associated probabilities

Combining these cases directly into the Chernoff bound gives

Again, this problem is convex in $t$, and so can be solved efficiently using Newton’s method. And again since the reverse case can be computed via the same expression we can similarly optimize this in an unconstrained fashion. Specifically, we can do this for every pair of classes $i$ and $i^{\prime}$, and return the $i$ which gives the smallest lower bound for the worst-case choice of $i^{\prime}$.

B.3 KL Divergence Bound

To compute actual certification radii, we will derive the KL divergence bound for the the case of $K$ classes. Let $\mu,\rho$ be defined as in Section 4, except that as in the previous section when a label is flipped with probability $q$ it is changed to one of the other $K-1$ classes uniformly at random. Let $\mu_{i}$ and $\rho_{i}$ refer to the independent measures on each dimension which collectively make up the factorized distributions $\mu$ and $\rho$ (i.e., $\mu(x)=\prod_{i=1}^{d}\mu_{i}(x)$). Further, let $Y_{1}^{i}$ be the $i^{th}$ element of $Y_{1}$, meaning it is the “original” label which may or may not be flipped when sampling from $\mu$. First noting that each dimension of the distributions $\mu$ and $\rho$ are independent, we have

Plugging in the robustness guarantee (3), we have that $g(\mu,\phi)=g(\rho,\phi)$ so long as

Setting $K=2$ recovers the divergence term (4) and the bound (5).

Appendix C Description of Label-Flipping Attacks

Due to the dearth of existing work on label-flipping attacks for deep networks, our attacks on MNIST and Dogfish were quite straightforward; we expect significant improvements could be made to tighten this upper bound.

For Dogfish, we used a pre-trained Inception network (Szegedy et al., 2016) to evaluate the influence of each training point with respect to the loss of each test point (Koh & Liang, 2017). As in prior work, we froze all but the top layer of the network for retraining. Once we obtained the most influential points, we flipped the first one and recomputed approximate influence using only the top layer for efficiency. After each flip, we recorded which points were classified differently and maintained for each test point the successful attack which required the fewest flips. When this was finished, we also tried the reverse of each attack to see if any of them could be achieved with even fewer flips.

For logistic regression these values can easily be computed in closed form.

C.2 Attacks on Our Classifier

Recall that our theoretical classifier outputs a prediction based on $P(\boldsymbol{\alpha}^{T}\mathbf{y}\geq 1/2)$, where the randomness is over the label flips of $\mathbf{y}$. More specifically, the classifier’s output is based on a weighted majority vote of “sub-classifiers”, each of which is a simple linear classifier which outputs $\mathbf{1}\{\boldsymbol{\alpha}^{T}\mathbf{\hat{y}}\geq 1/2\}$ for its own labels $\mathbf{\hat{y}}$. The sub-classifier’s vote is weighted by its probability under the smoothing distribution, which depends only on $\|\mathbf{y}-\mathbf{\hat{y}}\|_{0}$ (and is monotonically decreasing in this value). It is clear that the optimal attack to reduce $P(\boldsymbol{\alpha}^{T}\mathbf{y}\geq 1/2)$ is to flip the labels which will push the inner product $\boldsymbol{\alpha}^{T}\mathbf{y}$ as much as possible towards the incorrect label: flipping labels by their change to the inner product will add weight to the votes of the most overall number of incorrect sub-classifiers, pushing our smoothed classifier to be incorrect.

Here we make a subtle distinction: while this attack is optimal for the purpose of reducing $P(\boldsymbol{\alpha}^{T}\mathbf{y}\geq 1/2)$, it is not necessarily optimal against our classifier, even though this probability represents how our classifier (theoretically) makes a prediction. This is because in practice, we never actually compute $P(\boldsymbol{\alpha}^{T}\mathbf{y}\geq 1/2)$. Instead, recall from (6) that we use the Chernoff inequality to tightly bound this probability. Thus, while the attack described above is optimal for reducing the true probability (and therefore the theoretical robustness), it is technically possible that a different attack would cause a looser Chernoff bound, more effectively reducing our bound on the probability. In essence, our attack is optimal for modifying the LHS of (6), but not necessarily the RHS, which is ultimately how our classifier actually makes predictions.

With that said, the existence of an attack which causes the Chernoff bound to return a particularly sub-optimal bound seems debatable. So, while we present these results as an empirical upper bound, we believe it would not be inappropriate to also view them as an approximate lower bound. Of course, the actual lower bound returned by our classifier is still a genuinely guaranteed certificate. Figure 1(a) displays the result of our attack on MNIST 1/7, with the undefended classifier for comparison. Observe that the empirical upper bounds (dashed lines) track the guaranteed lower bounds (solid lines) reasonably closely. The gap is under 10% accuracy and shrinks as the noise $q$ decreases. Further, this empirical robust accuracy outperforms the undefended classifier’s empirical robust accuracy by an even larger margin. Figure 1(b) presents the same results on the Dogfish dataset. Our empirical attacks had very similar success rates for all values of $q$, so we only plot two values along with the undefended classifier. We again observe a tight correspondence between upper and lower bounds which gets tighter with smaller $q$.

Appendix D Additional Tables of Results

To supplement the line plots, for each dataset and noise parameter we present here precise certified test set accuracy at specific numbers of label flips. When available, for comparison we also provide the undefended classifier’s empirical accuracy when subjected to our label-flipping attack as detailed in Section C.1. For each number of label flips, the noise hyperparameter setting which results in the highest certified accuracy is in bold.

Appendix E Additional Plots