Year: 2019

Abstract:
This paper considers label-flipping attacks, a type of data poisoning attack where an adversary relabels a small number of examples in a training set in order to degrade the performance of the resulting classifier. In this work, we propose a strategy to build linear classifiers based on deep features that are certifiably robust against a strong variant of label-flipping, where the adversary can target each test example independently. In other words, for each test point, our classifier makes a prediction and includes a certification that its prediction would be the same had some number of training labels been changed adversarially. Our approach leverages randomized smoothing, a technique that has previously been used to guarantee test-time robustness to adversarial manipulation of the input to a classifier. Further, we obtain these certified bounds with no additional runtime cost over standard classification. On the Dogfish binary classification task from ImageNet, in the face of an adversary who is allowed to flip 10 labels to individually target each test point, the baseline undefended classifier achieves no more than 29.3% accuracy; we obtain a classifier that maintains 64.2% certified accuracy against the same adversary. We generalize our results to the multi-class case, providing what we believe to be the first multi-class classification algorithm that is certifiably robust to label-flipping attacks.

heading: 1 INTRODUCTION
text: 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. Work in this area includes 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 when triggered by a specific pattern, without causing a noticeable drop in overall accuracy. However, unlike the alternative “test-time” adversarial setting, where reasonably effective defenses exist to build adversarially robust classifiers, relatively little work has been done on building classifiers that are certifiably robust to targeted data poisoning attacks.
In this work, we propose a strategy for building classifiers that are certifiably robust against labelflipping attacks. In particular, we propose a pointwise certified defense—by this we mean that with each prediction, the classifier includes a certification guaranteeing that its prediction would not be different had it been trained on data with some number of labels flipped. Existing works on certified defenses make statistical guarantees over the entire test set, but they make no guarantees as to the robustness of a prediction on any particular test point. Thus, while these algorithms provide general robustness to any single corruption, 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 specifically target each test point individually. This motivates a defense that can certify each of its individual predictions, as we present here. To the best of our knowledge, this work represents the first pointwise certified defense to data poisoning attacks.
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 be robust (i.e., to not change its prediction) when some number of labels are adversarially manipulated in the training set. Although a naive implementation of this approach would not be computationally feasible, we show that by using a linear least-squares classifier over the output of a pre-trained network, we can obtain these certified bounds with no additional runtime cost over standard classification—and we again emphasize that this is the first such certified defense against pointwise label-flipping attacks, even for linear classifiers.
We evaluate our proposed classifier on several benchmark datasets common to the data poisoning literature. Specifically, we demonstrate that our randomized classifier is able to achieve 75.7% certified accuracy on MNIST 1/7 even when the number of allowed label flips would drive a standard, undefended classifier to less than 50%. Similar results in experiments on the Dogfish binary classification challenge from ImageNet and IMDB review sentiment database validate our technique for more challenging datasets, and we further experiment on the full MNIST dataset to demonstrate its effectiveness for multi-class classification. On top of this, our classifier maintains a reasonably competitive non-robust accuracy (e.g., 94.5% on MNIST compared to 99.1% for the undefended classifier).

heading: 2 RELATED WORK
text: Data-poisoning attacks A data-poisoning attack (Muñoz González et al., 2017; Yang et al., 2017) is an attack whereby an adversary corrupts some portion of a training set or adds new inputs, with the goal of degrading the performance of the learned model. The attack can be targeted to cause poor performance on a specific test example or can instead simply reduce the overall test performance. 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 innocuous, poisoned yet “correctly” labeled training examples but causing the classifier to perform poorly (Shafahi et al., 2018; Zhu et al., 2019). 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 some of the training labels. The number of allowed changes could be an exact number or a percentage of the total labels. The classifier is then trained on the corrupted training set, with no knowledge of which labels have been tampered with.
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).
Certified defenses For a review on robustness to random noise, we refer the reader to Rousseeuw & Leroy (1987)—our focus is on adversarial noise, a much more challenging problem. 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 (Liu et al., 2017; 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 train and test distributions: 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, most of these statistical guarantees are not meaningful when applied to deep, non-linear architectures.
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 robustness of deep networks to adversarial perturbations. After a series of heuristic defenses (Metzen et al., 2017; Feinman et al., 2017), followed by attacks breaking them (Athalye et al., 2018; Carlini & Wagner, 2017), focus began to shift towards the development of provable robustness.
One approach which has gained popularity in recent work is randomized smoothing. Rather than certifying the original classifier f , randomized smoothing defines a new classifier g whose prediction at an input x is the class assigned the most probability when x is perturbed with noise from some distribution µ and passed through f . That is, g(x) = arg maxc P ∼µ(f(x + ) = c). This new classifier g is then certified as robust, ideally without sacrificing too much accuracy compared to f . The original formulation was presented by Lecuyer et al. (2018) and borrowed ideas from differential privacy. The above definition is due to Li et al. (2018) and was popularized by Cohen et al. (2019), who derived a tight robustness guarantee. Follow-up work has focused on optimizing the training procedure of f (Salman et al., 2019) and extending the analysis to other types of distributions (Lee et al., 2019). For more details, we refer the reader to Cohen et al. (2019).

heading: 3 A GENERAL VIEW OF RANDOMIZED SMOOTHING
text: We begin by presenting a general viewpoint of randomized smoothing. Under our notation, randomized smoothing constructs an operator G(µ, φ) that maps a binary-valued 1 function φ : X → {0, 1} and a smoothing measure µ : X → R+, with ∫ X µ(x)dx = 1, to the expected value of φ under µ (that is, G represents the “vote” of φ weighted by µ). For example, φ could be a binary image classifier and µ could be some small, random pixel noise applied to the to-be-classified image. We also define a “hard threshold” version g(µ, φ) that returns the most probable output (the majority vote winner). Formally,
G(µ, φ) = Ex∼µ[φ(x)] = ∫ X µ(x)φ(x)dx and g(µ, φ) = 1{G(µ, φ) ≥ 1/2}, (1)
where 1{·} is the indicator function. Intuitively, for two smoothing measures µ, ρ : X → R+ that are very similar, we would expect that for most φ, even though G(µ, φ) and G(ρ, φ) may not be equal, the threshold function g should satisfy g(µ, φ) = g(ρ, φ). Further, the degree to which µ and ρ can differ while still preserving this property should increase as G(µ, φ) approaches either 0 or 1, because this increases the “margin” with which the function φ is 0 or 1 respectively over the measure µ. More formally, we define a general randomized smoothing guarantee as follows.
Definition 1. Let µ : X → R+ be a smoothing measure over X , with ∫ X µ(x)dx = 1. Then a randomized smoothing robustness guarantee is a specification of a distance measure d(µ, ρ) and a function f : [0, 1]→ R+ such that for all φ : X → {0, 1} and all measures ρ : X → R+ of a given form,
g(ρ, φ) = g(µ, φ) whenever d(µ, ρ) ≤ f(G(µ, φ)). (2)
For brevity, we will sometimes use p in place of G(µ, φ), representing the probability with which the majority class wins the vote (this is analogous to pA in Cohen et al. (2019)).
Instantiations of randomized smoothing This definition is rather abstract, so we highlight concrete examples of how it can be applied to achieve certified guarantees against adversarial attacks.
1For simplicity, we present the methodology here in terms of binary-valued functions, which will correspond eventually to binary classification problems. The extension to the multiclass setting requires additional notation, and thus is deferred to the appendix.
Example 1. The randomized smoothing guarantee of Cohen et al. (2019) uses the smoothing measures µ = N (x0, σ2I), a Gaussian around the point x0 to be classified, and ρ = N (x0 + δ, σ2I), a Gaussian around x0 perturbed by δ. They prove that (2) holds for all classifiers φ if we define
d(µ, ρ) = 1
σ ‖δ‖2 ≡
√ 2KL(µ ‖ ρ), f(p) = |Φ−1(p)|, (3)
where KL(·) denotes KL divergence and Φ−1 denotes the inverse CDF of the Gaussian distribution.
Although this previous work focused on the case of randomized smoothing of continuous data via Gaussian noise, this is by no means a requirement of the approach. For instance, Lee et al. (2019) considers an alternative approach for dealing with discrete variables. Example 2. The randomized smoothing guarantee of Lee et al. (2019) uses the factorized smoothing measure in d dimensions µα,K(x) = Πdi=1µα,K,i(xi), defined with respect to parameters α ∈ [0, 1],K ∈ N, and a base input z ∈ {0, . . . ,K}d, where
µα,K,i(xi) = { α, if xi = zi 1−α K , if xi ∈ {0, . . . ,K}, xi 6= zi,
with xi being the ith dimension of x. ρα,K is similarly defined for a perturbed input z′. They guarantee that (2) holds if we define
d(µ, ρ) = r def = ‖z′ − z‖0, f(p) = Fα,K,d(max(p, 1− p)). (4)
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 − α. F is a combinatorial function; Fα,K,d(p) is defined as the maximum number of dimensions—out of d total—by which µα,K and ρα,K can differ such that a set with measure p under µα,K is guaranteed to have measure at least 12 under ρα,K . Lee et al. (2019) prove that this value is independent of z and z′.
Finally, concurrent work has considered a more general form of randomized smoothing that doesn’t require strict assumptions on the distributions but is still able to provide similar guarantees. Example 3 (Generic bound from Anonymous (2019)). Given any two smoothing distributions µ, ρ, we have the generic randomized smoothing robustness certificate, ensuring that (2) holds with definitions
d(µ, ρ) = KL(ρ ‖ µ), f(p) = −1 2 log(4p(1− p)). (5)
Randomized smoothing in practice For most classifiers, the expectationG(µ, φ) cannot be computed exactly, and so we must resort to Monte Carlo approximation. In this “standard” form of randomized smoothing, we draw multiple random samples from µ and use these to construct a highprobability bound on G(µ, φ) for certification. More precisely, this bound should be a lower bound onG(µ, φ) when the hard prediction g(µ, φ) = 1 and an upper bound otherwise; this ensures in both cases that we underestimate the true certified robustness for 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 g.

heading: 4 LABEL-FLIPPING ROBUSTNESS
text: We now present the main contribution of this paper, a technique for using randomized smoothing to provide certified robustness against label-flipping attacks. Specifically, we first propose a generic strategy for applying randomized smoothing to certify a prediction function against pointwise label flipping attacks. We show how this general approach can be made tractable using linear leastsquares classification combined with pre-trained deep features, and we use the Chernoff inequality to analytically bound the relevant probabilities for the randomized smoothing procedure. 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.
To motivate the approach, we note that in prior work, randomized smoothing was applied at test time with the function φ : X → {0, 1} being a (potentially deep) classifier that we wish to smooth.
Algorithm 1 Randomized smoothing for label-flipping robustness
Input: feature mapping h : Rd → Rk; noise parameter q; training set {(xi, yi) ∈ Rd×{0, 1}}ni=1 (with potentially adversarial labels); additional inputs to predict {xj ∈ Rd}mj=1 1. Pre-compute matrix M
M = X ( XTX + λI )−1 (6)
whereX ≡ h(x1:n) and λ = (1 + q) σ̂ 2k 2n σmax(X TX) σmin(XTX) for j = 1, . . . ,m do 1. Compute vector αj = Mh(xj)T 2. Compute optimal Chernoff parameter t via Newton’s method
t? = arg min t t/2 + ∑ i:yi=1 log(q + (1− q)e−tα j i ) + ∑ i:yi=0 log((1− q) + qe−tα j i )  (7) and let p? = max(1−B|t?|, 1/2) where B|t?| is the Chernoff bound (13) evaluated at |t?|. Output: Prediction ŷj = 1 {t? ≥ 0} and certification that prediction will remain constant for up to r training label flips, where
r =  log(4p?(1− p?)) 2(1− 2q) log ( q
1−q
)  (8)
(or a larger number of flips using the exact method of Lee et al. (2019)). end for
However, there is no requirement that the function φ be a classifier at all; the theory holds for any binary-valued function. Instead of treating φ as a trained classifier, we consider φ to be an arbitrary learning algorithm which takes as input a training dataset {xi, yi}ni=1 ∈ (X × {0, 1})n and an additional example 2 xn+1 without a corresponding label, which we aim to predict. In other words, the combined goal of φ 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). When applying randomized smoothing in this setting, we randomize over the labels in the training set, rather than over the test-time input to be classified. Analogous to previous applications of randomized smoothing, if the majority vote of the classifiers trained with these randomly sampled labels has a large margin, it will confer a degree of adversarial robustness to some number of adversarially corrupted labels.
To formalize this intuition, consider two different assignments of n training labels Y1, Y2 ∈ {0, 1}n which differ on precisely r labels. Let µ (resp. ρ) be the distribution resulting from independently flipping each of the labels in Y1 (resp. Y2) with probability q. It is clear that as r increases, d(µ, ρ) should also increase. In fact, it is simple to show (see Appendix B.3 for derivation) that the exact KL divergence between these two distributions is
KL(µ ‖ ρ) = KL(ρ ‖ µ) = r(1− 2q) log (
1− q q
) . (9)
Plugging in the robustness guarantee (5), we have that g(µ, φ) = g(ρ, φ) so long as
r ≤ log(4p(1− p)) 2(1− 2q) log (
q 1−q ) , (10) This implies that for any test point, as long as (10) is satisfied, g’s prediction (the majority vote weighted by the smoothing distribution) will not change if an adversary corrupts the training set
2Note that our algorithm does not actually 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.
from Y1 to Y2, 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 (10); more noise will likely decrease the margin of the majority vote p, but 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 quantitiesF−11−q,1,n(r) from Equation (4) for each r, we can simply compareG(µ, φ) to each of these and thereby certify robustness to the highest possible number of label flips. This computation 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 5 in Appendix D). We make use of this tighter bound in our experiments, but we emphasize that meaningful results can be achieved even with the looser bound, which is orders of magnitude cheaper to compute.

heading: 4.1 EFFICIENT IMPLEMENTATION VIA LEAST SQUARES CLASSIFIERS
text: There may appear to be one major impracticality of the algorithm proposed in the previous section, if considered naively: treating the function φ 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 cost of classifying a single example. The full procedure, with all the parts described below, can be found in Algorithm 1.
Linear least-squares classification The fundamental simplifying assumption we make in this work is to restrict the “training” process done by the classifier φ to be done via a linear leastsquares solve. Given the training set {xi, yi}ni=1, we assume that there exists some feature mapping h : Rd → Rk (where k < n), which typically would consist of a deep network pre-trained on a similar task, or possibly trained in an unsupervised fashion on x1:n (i.e. independent of the training labels, which are presumed to be potentially poisoned). This may seem to be a strong assumption, but similar assumptions are commonly made when using pre-trained models or in the meta-learning setting, and the transferability of pre-trained features is well documented (Donahue et al., 2014; Bo et al., 2010; Yosinski et al., 2014). Given this feature mapping, let X = h(x1:n) ∈ Rn×k be the training point features and let y = y1:n ∈ {0, 1}n be the labels. Our training process consists of finding the least-squares fit to the training data, i.e., we find parameters β̂ ∈ Rk via the normal equation β̂ = ( XTX )−1 XTy and then we make a prediction on the new example via the linear
function h(xn+1)β̂. Although it may seem odd to fit a classification task with least-squares loss, binary classification with linear regression is known to be equivalent to Fisher’s linear discriminant (Mika, 2003) and often works quite well in practice.
The real advantage of the least-squares approach in this setting is that it reduces the prediction to a linear function of y, and thus randomizing over the labels is straightforward. Specifically, letting
α = X ( XTX )−1 h(xn+1) T , (11)
the prediction h(xn+1)β̂ can be equivalently given by αTy (this is effectively just the kernel representation of the linear classifier). Thus, we can simply compute α 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 theX ( XTX )−1 term and reuse it for each test point.
`2 regularization for better conditioning Unfortunately, it is unlikely to be the case that the training points are well-behaved for linear regression in the feature space. To address this, we instead solve an `2 regularized version of least-squares. This is a common tool for solving systems with ill-conditioned or random design matrices (Hsu et al., 2014; Suggala et al., 2018). Luckily, there still exists a pre-computable closed-form solution to this problem, whereby we solve
α = X(XTX + λI)−1h(xn+1) T . (12)
The other parts of our algorithm remain unchanged. Following results in Suggala et al. (2018), we set the regularization parameter λ = (1 + q) σ̂
2k 2n κ(X TX) where σ̂2 = ‖y−Xβ̂OLS‖ 2 2 n−k is an estimate
of the variance (Dicker, 2014) and κ(·) is the condition number equal to the ratio of the largest and smallest singular values. The (1 + q) term is to help account for the variance caused by label flips.
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 φ will output the label 1 for the test point whenever αTy ≥ 1/2 and 0 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 (10) to determine the classifier’s robustness. Concretely, we can upper bound the probability that the classifier outputs the label 0 by
P (αTy ≤ 1/2) ≤ min t>0
{ et/2
n∏ i=1 E[e−tαiyi ]
} = min
t>0
{ et/2
n∏ i=1
qe−tαi(1−yi) + (1− q)e−tαiyi } .
(13) Conversely, the probability that the classifier outputs the label 1 has the analogous upper bound which is the same as (13) 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 (13) 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 12 , 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 sampling whatsoever. Instead, the prediction 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 with a deep network.

heading: 5 EXPERIMENTS
text: 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 the full MNIST dataset; to the best of our knowledge, this is the first multi-class classification algorithm with certified robustness to label-flipping attacks. 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.
Because the above are binary classification tasks, one could technically achieve a certified accuracy of 50% at r = ∞ (or 10% for MNIST) by letting g be constant. A constant classifier would be infinitely robust, but it is not a very meaningful baseline. However, we include the accuracy of such a classifier in our plots (black dotted line) as a reference.
To properly justify the need for such certified defenses, and to get a sense of the scale of our certifications, we also 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 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 contains the details of our attack implementations.
Results on MNIST The MNIST 1/7 dataset (LeCun et al., 1998) consists of just the classes 1 and 7, totalling 13007 training points and 2163 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 1a 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(µ, φ)− 12 | 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 1b 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 pre-trained classifier could not rely on features learned from other handwritten digits; instead, we used the features from a network trained on the Omniglot dataset (Lake et al., 2015), as the task of classifying handwritten characters is quite similar. Despite the lack of fine-tuned features, our algorithm still achieves significant certified accuracy under a large number of adversarial label flips. We observed that regularization did not make a large difference for the multi-class case, possibly due to the inaccuracy of the residual term when calculating the noise estimate.
See Figure 4 in Appendix D for the effect of `2 regularization on the OLS solution. We note that at a slight cost to non-robust accuracy, the regularization results in substantially higher certified accuracy at almost all radii. A similar effect was observed for all our datasets and at all values of q.
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 as any kind of dog or fish. Our pretrained feature embedder was therefore capable of extracting image features but had no concept of features specific to either class. We used PCA to reduce the 2048 dimensional feature space to 1700 dimensions before solving, to ensure the system was not underdetermined. Figure 2 displays the results of our poisoning attack along with our certified defense. Under the undefended model, more than 50% of the test points can be successfully attacked with no more than 7 label flips, whereas our model with q = 0.001 can certifiably correctly classify 67.83% of the test points under the same attack. It would take more than three times as many flips for each test point individually to push our model to less than 50% certified accuracy, at which point the undefended classifier would be reduced to at most 0.83%.
Because the predictions on the test points can be changed by flipping such a small fraction of the training set, high values of q reduce the randomized 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 were necessary to achieve high 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.
Results on IMDB Figure 3 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 observation, we found smaller levels of noise to result in larger certified accuracy. We expect significant improvements could be made with a more refined choice of feature embedding.
We also observed that increasing q does not significantly decrease the non-robust accuracy. We believe this is because the limitation of these classifiers is not the label noise, but rather the difficulty in classifying the imperfect feature embeddings with linear regression. Thus, the sign of t? was frequently correct and remained on the same side of 0 as q increased, but the margin of G(µ, φ) decreased too rapidly to certify a large number of flips. This was similarly observed in the case of full MNIST, where the pre-trained features came from a network trained on the Omniglot dataset and therefore were not as informative for classification.

heading: 6 CONCLUSION
text: In this work we have presented a certified defense against a strong class of adversarial label-flipping attacks where an adversary can flip labels to cause a misclassification on each test point separately. This contrasts with previous data poisoning settings, which have typically only considered an adversary who wishes to degrade the classifier’s accuracy on the test distribution as a whole, and it brings the adversary’s objective more in line with that of backdoor attacks and test-time adversarial perturbations. Leveraging randomized smoothing, a method originally developed for certifying robustness to test-time perturbations, we presented a classifier that can be certified robust to these pointwise train-time attacks. We then 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 algorithm results in the first multi-class classification algorithm that is certifiably robust to label-flipping attacks.
There are several avenues for improvement to this line of work, perhaps the most immediate being the method for learning the input features. For example, rather than considering fixed features generated by a pre-trained deep network, extensions could leverage neural tangent kernels (Jacot et al., 2018) to also allow for efficient learning with perturbed inputs or more flexible representations. Using this or other approaches, the analysis could be extended to other types of smoothing distributions applied to the training data, such as randomizing over the input features to provide robustness to more general data poisoning attacks. Conversely, we also hope that our defense to this threat model will inspire the development of more powerful train-time attacks, against which future defenses can be evaluated.

heading: A GENERIC RANDOMIZED SMOOTHING ALGORITHM
text: Algorithm 2 Generic randomized smoothing procedure Input: function φ : X → {0, 1}, number of samples N , smoothing distribution µ, failure probability δ > 0 for i = 1, . . . , N do
Sample xi ∼ µ and compute yi = φ(xi) end for Compute approximate smoothed output
ĝ(µ, φ) = 1
{ 1
N N∑ i=1 yi ≥ 1/2
} (14)
Compute bound Ĝ(µ, φ) such that with probability 1− δ
Ĝ(µ, φ) { ≤ G(µ, φ) if ĝ(µ, φ) = 1 ≥ G(µ, φ) if ĝ(µ, φ) = 0 (15)
Output: Prediction ĝ(µ, φ) and probability bound Ĝ(µ, φ), or abstention if ĝ(µ, φ) and Ĝ(µ, φ) are on different sides of 12 .

heading: B THE MULTI-CLASS SETTING
text: 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 ∈ {1, . . . ,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.
B.1 RANDOMIZED SMOOTHING IN THE MULTI-CLASS CASE
We here extend our notation to the case of more than two classes. Recall our original definition of G,
G(µ, φ) = Ex∼µ[φ(x)] = ∫ X µ(x)φ(x)dx,
where φ : X → {0, 1}. More generally, consider a classifier φ : X → [K], outputting the index of one of K classes. Under this formulation, for a given class c ∈ [K], we have
G(µ, φ, c) = Ex∼µ[φc(x)] = ∫ X µ(x)φc(x)dx, (16)
where φc(x) = 1 {φ(x) = c} is the indicator function for if φ(x) outputs the class c. In this case, the hard threshold g is evaluated by returning the class with the highest probability. That is,
g(µ, φ) = arg max c G(µ, φ, c). (17)
B.2 LINEARIZATION AND CHERNOFF BOUND APPROACH FOR THE MULTICLASS 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 multiclass setting finds some set of weights
β̂ = ( XTX )−1 XTY (18)
where Y ∈ {0, 1}n×K is a binary matrix with each row equal to a one-hot encoding of the class label (note that the resulting β̂ ∈ Rk×K is now a matrix, and we let β̂i refer to the ith column). At prediction time, the predicted class of some new point xn+1 is simply given by the prediction with the highest value, i.e.,
ŷn+1 = arg max i
β̂i T h(xn+1). (19)
Alternatively, following the same logic as in the binary case, this same prediction can be written in terms of the α variable as
ŷn+1 = arg max i
αTYi (20)
where Yi denotes the ith column of Yi.
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
P (αTYi < α TYi′) (21)
for all alternative classes i′. By the Chernoff bound, we have that
logP (αTYi < α TYi′) = logP (α T (Yi − Yi′) ≤ 0)
≤ min t>0  n∑ j=1 logE [ e−tαj(Yji−Yji′ ) ] . (22) The random variable Yji − Yji′ takes on three different distributions depending on if yj = i, if yj = i
′, or if yj 6= i and yj 6= i′. Specifically, this variable can take on the terms +1, 0,−1 with the associated probabilities
P (Yji − Yji′ = +1) = {
1− q if yj = i, q/(K − 1) otherwise.
P (Yji − Yji′ = −1) = { 1− q if yj = i′, q/(K − 1) otherwise.
P (Yji − Yji′ = 0) = { q(K − 2)/(K − 1) if yj = i or yj = i′, 1− 2q/(K − 1) otherwise.
(23)
Combining these cases directly into the Chernoff bound gives
logP (αTYi < α TYi′) ≤ min
t>0 { ∑ j:yj=i log ( (1− q)e−tαj + qK − 2 K − 1 + q K − 1 etαj ) +
∑ j:yj=i′ log ( q K − 1 e−tαj + q K − 2 K − 1 + (1− q)etαj ) +
∑ j:yj 6=i,yj 6=i′ log ( q K − 1 e−tαj + 1− 2 q K − 1 + q K − 1 etαj )} .
(24) 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. Specificially, we can do this for every pair of classes i and i′, and return the i which gives the smallest lower bound for the worst-case choice of i′.
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 µ, ρ be defined as in Section 4, except that as in the previous secftion when a label is flipped with probability q it is changed to one of the other K − 1 classes uniformly at random. Let µi and ρi refer to the independent measures on each dimension which collectively make up the factorized distributions µ and ρ (i.e., µ(x) = ∏d i=1 µi(x)). Further, let Y i 1 be the i
th element of Y1, meaning it is the “original” class which may or may not be flipped when sampling from µ. First noting that each dimension of the distributions µ and ρ are independent, we have
KL(ρ ‖ µ) = n∑ i=1 KL(ρi ‖ µi)
= ∑
i:ρi 6=µi
KL(ρi ‖ µi)
= r  K∑ j=1 ρi(j) log ( ρi(j) µi(j) ) = r ( ρi(Y i 1 ) log ( ρi(Y i 1 )
µi(Y i1 )
) + ρi(Y i 2 ) log ( ρi(Y i 2 )
µi(Y i2 ) )) = r ( (1− q) log ( 1− q q
K−1
) + q
K − 1 log ( q K−1 1− q ))
= r ( 1− Kq
K − 1
) log ( (1− q)(K − 1)
q
)
Plugging in the robustness guarantee (5), we have that g(µ, φ) = g(ρ, φ) so long as
r ≤ log(4p(1− p)) 2(1− KqK−1 ) log ( q (1−q)(K−1) ) . (25) Setting K = 2 recovers the divergence term (9) and the bound (10).

heading: C DESCRIPTION OF LABEL-FLIPPING ATTACKS ON MNIST 1/7 AND DOGFISH
text: 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 pretrained 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 MNIST we implemented two similar attacks and kept the best attack for each test point. The first attack simply ordered training labels by their `2 distance from the test point in feature space, as a proxy for influence. We then tried flipping these one at a time until the prediction changed, and we also tried the reverse. The second attack was essentially the same as the Dogfish attack, ordering the test points by influence. To calculate influence we again assumed a frozen feature map; specifically, using the same notation as Koh & Liang (2017), the influence of flipping the label of a training point
z = (x, y) to z− = (x, 1− y) on the loss at the test point ztest is:
dL(ztest, θ̂ ,z−,−z)
d = ∇θL(ztest, θ̂)T dθ̂ ,z−,−z d
≈ −∇θL(ztest, θ̂)TH−1θ̂ ( ∇θL(z−, θ̂)−∇θL(z, θ̂) ) For logistic regression, these values can easily be computed in closed form.

heading: D ADDITIONAL PLOTS

Review summaries:
The paper investigates data poisoning type of attack. In such attacks, an adversary can alter/flip the labels of some of the training examples. The paper proposed a new approach towards certified robustness against this type of attack. In particular, the new classifier will output a prediction along with a certificate in which the prediction would not change if certain number of labels in the training data were flipped.

This paper proposes a certifiable defense against data poisoning attacks by using a randomized smoothing approach. An adversary in such a setting is permitted to flip any r labels from a dataset of size n. The smoothing procedure (stated roughly) is to train on a dataset with "noisy" or "smoothed" labels, obtained by flipping each label with some probability q. The authors obtain a lower bound on r in terms of q. Directly using this technique requires training multiple classifiers on multiple noisy datasets. To show that this method is useful, the authors study the effectiveness of this model against a classifier that performs linear regression on a pre-trained feature extractor.