Certified Robustness to Adversarial Label-Flipping Attacks via Randomized Smoothing
Authors: Elan Rosenfeld
Ezra Winston
Pradeep Ravikumar
J. Zico Kolter
Venue:  (2020)
Keywords: Adversarial Robustness
Label Flipping Attack
Data Poisoning Attack

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 classifiers 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.

Under review as a conference paper at ICLR 2020
CERTIFIED ROBUSTNESS TO ADVERSARIAL LABEL- FLIPPING ATTACKS VIA RANDOMIZED SMOOTHING
Anonymous authors Paper under double-blind review
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 lever- ages randomized smoothing, a technique that has previously been used to guar- antee test-time robustness to adversarial manipulation of the input to 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 the multi-class case, providing what we believe to be the first multi-class classification algorithm that is certifiably robust to label-flippngg attacks.
INTRODUCTION
Modern classifiers, despite their widespread empirical success, are known to be susceptible to adver- sarial attacks. In this paper, we are specifically concerned with so-called "data ptiata-possonngg attacks (formally, causative attacks [Barreno et al. 2006 Paaperntt et al. 2018)). where the attacker manip- ulates some aspects of the training data in order cause the learning algorithm to output a faulty classifier. Work in this area includes label-flipping attacks (Xiao et al.) (012)). where the labels of a training set can be adversarially manipulated to decrease performance
the trained classifier; general data poisoning, where both the training inputs and labels can be manipulated (Steinhardt ct al. 2017); and backdoor attacks (Chen et al., 2017; Tran et al. 2018). where the training set is corrupted so cause the classifier to deviate from its expected behavior when triggered by spe- cific 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 ro- bust classifiers, relatively little work has been done on building classifiers that are certifiably robust targeted data poisoning attacks.
In this work, we propose a strategy for building classifiers that are certifiably robust against label- flipping attacks. particular, we propose a pointwise certified defense-by bb this we mean that with each prediction, the classifier includes a certification guarantecing that its prediction would not be different had 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 data poisoning attacks.

---

Under review as a conference paper at ICLR 2020
Our approach leverages randomized smoothing (Cohen et al. 2019), technique that has previously been used to guarantee test-time robustness to adversarial manipulation of the input to a deep net- work. 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 classifter. Specifically, by randomizing over the labels during this training process, we obtain an overall clas- sification 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 linear caast-squarss classi- fier over the output of 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-flippigg attacks, even for linear classifiers.
We evaluate our proposed classifier several benchmark datasets common to the data poisoning literature. Specifically, we demonstrate that our randomized classifier is able to achieve 75.7% cer- tified accuracy on MNIST 1/7 even when the number of allowed label flips would drive standard, undefended classifier to less than 50%. Similar results experiments on the Dogfish binary classi- fication 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 reasonably competitive non-robust accuracy (e.g., 94.5% on MNIST compared to 99.1 1 % for the undefended classifier).
2 RELATED WORK
Data-poisoning attacks A data-ppisoniig atlack (Muñoz González et al.) 2017 Yang et al. 2017) 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 perfor- mance. The adversary is assumed have perfect knowledge of the learning algorithm, so security by design-as opposed to obscurity-is is the only viable defense against such attacks. The adversary also typically assumed 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 al. 2015), SVMs (Biggio et al., 2011: Xiao et al.) 2012), linear regression (Liu let al., (017). and PCA (Rubinstein et al.) 2009). to name a few. Some attacks can even achieve success with "clean-labe label" attacks, inserting innocuous, poisoned yet "correctly" labeled training examples but causing the classifier to perform poorly (Shafahi et al. 20188 Zhu et al. 2019). For an overview of data poisoning attacks and defenses machine learning, see Biggio et al. (2014).
Label-flipping attacks A flbel-fiipping 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 devel- oped (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 achieve, both theoretically and empir- ically (Xiao et al.] 2012 Biggio et al. [011]. 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 al. 2018).
Certified defenses For a review on robustness to random noise, we refer the reader to Rousseeuw & Leroy (1987)-0ul focus is on adversarial noise, 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 al. 2017 Prasad et al. 2018 Shen & Sanghavi 2019), that the
2

---

Under review as a conference paper at ICLR 2020
expected loss the test distribution is bounded (Klivans 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) 2013]; others require limited effects of outliers (Steinhardt et al. 2017). As mentioned above, all of these methods fail provide guarantees for individual test points. Additionally, most of these statistical guarantees are not meaningful when applied to deep, non-linear architectures.
corruption vector (Bhatia et al.
Randomized smoothing Since the discovery of adversarial examples (Szegedy et al. 2013: Good-
fellow al., 2015), the research community has been investigating techniques for increasing the bustness of deep networks to adversarial perturbations. After a series of heuristic defenses (eetzen
al. 2017 Feinman et al. 2017), followed by attacks breaking them (Athalye al. 2018 Carlini
& Wagner 2017), Tocus 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 an imput x is the class assigned the most probability when
perturbed with noise from some distribution ll and passed through f- That is, g(x)) arg max, Pp + <) = 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. (0188) and was popularized by Cohen et al. (2019), who derived tight robustness guarantee. Followup 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. (2199)
A GENERAL VIEW OF RANDOMIZED SMOOTHING
We begin by presenting a general viewpoint of randomized smoothing. Under our notation, random- ized smoothing constructs an operator G(u, o) that maps binary-valued function ffluctifinnttionn @ X - {0, 1} and a smoothing measure μ X - Rt, with fx ((r)dr = 1, to the expected value of & under (that is, G represents the "vote" of ø weighted by μ1) For example, é could be binary image classifier and j could be some small, random pixel noise applied to the to-be-classified image. We also define "hard threshold" version g(u, の) that returns the most probable output (the majority vote winner). Formally,
G(H, Φ) = -Emnp(((t)] u(z))(z)dz and g(u.0) = I[G(, Φ) 2 1/2), (1)
where 1f.} is the indicator function. Intuitively, for two smoothing measures p. x - R. that very similar, we would expect that for most o even though (n, Φ) and G(p, の) may not be equal, the threshold function y should satisfy g(2, Φ) = ((p,)) d). Further, the degree to which and p can differ while still preserving this property should increase as G(H, Φ) approaches either or 1, because this increases the "margin" with which the function o is O or I respectively over the measure J.. More formally, we define a general randomized smoothing guarantee as follows.
Definition 1. Let μ : X + R+ be a smoothing measure over X, with fx p(x)dx 1. Then randomized smoothing robustness guarantee is a specification of a distance measure d(p, p) and function f [0, + R., such that for all Φ X + {0, 1} and all measures p: X + R4 of a given
form,
g(p, () = g(1 whenever d(p, p) S f(G())))
For brevity, will sometimes use p in place of G(u,, Φ). 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 con- crete examples of how it can be applied to achieve certified guarantees against adversarial attacks.
For 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.
3

---

Under review as a conference paper at ICLR 2020
The randomized smoothing guarantee of Cohen et al. (2019) uses the smoothing mea- sures μ = (zy, I)), a Gaussian around the point Vo to be classified, and = N N( + 6, I), a
Example 1.
Gaussian around 2o perturbed by 6. They prove that (2) holds for all classifiers we define
118112 -
d(u, p) = σ
v 2 P), f(p) = (
(3)
where KL.(.) denotes KL divergence and क 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 Lee et al. (2019) uses the factorized smoothing measure in d dimensions Pa,K (x) II; 1i.1/MaKK5i (X,),, defined with respect to parameters [0, 1), K N. and base input z E {O...., K}, where
ifx: = =%;
(x,),(()))
1-a K
ifx, E (0.... K), X; #2.
with xi being the 8th dimension of x. Pa.K is similarly defined for a perturbed input z'. They guarantee that (2) holds if we define
d(p. (0.p))++>> r def | z|lo, f(p) Kaa.K, 1 1p))..
(4)
In words, the smoothing distribution is such that each dimension is independently perturbed to one of the other K values uniformly random with probability 1 a. F combinatorial function; KP)) is defined as the maximum number of dimensions- out of d total by which Ma, and Pa,K can differ such that a set with measure p under Ha. is guaranteed to have measure at least 2 under Pa.K. Lee et al. 2019) prove that this value is independent of and z'.
Finally, concurrent work has considered 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 μ., p. we have the generic randomized smoothing robustness certificate, ensuring that (2) holds with defi- nitions
d(p, p) = KL(p ll 1), f(p) = - log 1og(4p(1- (o((4p(1-p)) -p)).
(5)
Randomized smoothing in practice For most classifiers, the expectation G(Ju, Φ) cannot be com- puted 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 high- probability bound on G(u, o) for certification. More precisely, this bound should be lower bound on G(p, Φ) when the hard prediction g(1, Φ) 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.
4 LABEL-FLIPPING ROBUSTNESS
We now present the main contribution of this paper, technique for using randomized smoothing to provide certified robustness against label-flippigg attacks. Specifically, we first propose 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 lincar least- squares 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 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.
4

---

Under review as a conference paper at ICLR 2020
Algorithm Randomized smoothing for label-flipping robustness
Input: feature mapping h Rd > I noise parameter q; training set ( y/) E Rdx x (0, 13)2
(with potentially adversarial labels); additional inputs predict {x, E Rdm 1. Pre-compute matrix M
1z=1
M x X XT)
(6)
b Tmax X xxx x 2n amiin
where X = h( and À = (1 + q)
(XTX)
for j I.... do
1. Compute vector a² = Mh(x,))
2. Compute optimal Chernoff parameter t via Newton's method
1" - -rag min
1/2+
Σ m1
log(a + (1 11--)1 g)e" g)e tae)) +
Σ 2:3/=
log((1 ge ge=)
and let p² max(1 B 1/2) where B₁r- is the Chernoff bound evaluated at |6*).
Output: Prediction 3, 1 {t* 2 0} and certification that prediction will remain constant for up to r training label flips. where
1og(4p* (1 p²))
(8)
2(1 2q) log
1-1
(or a larger number of flips using the exact method of Lf et (2019)
end for
However, there is no requirement that the function & be classifier at all; the theory holds for any binary function. Instead of treating & as trained classifier, we consider & to be an arbitrary learning algorithm which takes input training dataset {z,, 31 v= E (X' x {0, 1})" and an additional example Tn++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, consider test time outputs to be 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 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 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, Y/2 E {0. 1)" which differ on precisely labels. Let (resp. p) be the distribution resulting from independently flipping each the labels in Y, (resp. Y2) with probability q. It is clear that as r increases. d(p, p) should also increase. In fact, it is simple to show (see Appendix B.3 for derivation) that the exact KI. divergence between these two distributions
1 (19 q
KL(p p) KL l1 Ht) r(1 2q) log
(9)
q
Plugging in the robustness guarantee
5 we have that g(u, Φ)) g( so long as
log(4p( p))
(10)
2(1 - (2)) log
-
This implies that for any test point, as long as (TO) is satisfied, g's prediction (the majority vote weighted by the smoothing distribution) will not change if an adversary corrupts the training set
Note that our algorithm does not actually require access to the test data to do the necessary precomputation. We present it here such merely give an intuitive idea of the procedure.
5

---

Under review as a conference paper at ICLR 2020
from Y1 to Y2, or indeed to any other training set that differs at most r labels. We can tune the noise hyperparameter q to achieve the largest possible upper bound in (TO); more noise will likely decrease the margin of the majority vote p. but will also decrease the divergence.
Computing tight bound This approach has a simple closed form, but the bound is not tight. We can derive tight bound via a combinatorial approach as in Lee al. (2019). By precomputing the quantities 1, (r) from Equation (4) for each r, we can simply compare G(u, Φ) to each of these and thereby certify robustness to the highest possible number of label flips. This computation can be expensive, but it provides significantly tighter robustness guarantee. certifying approximately twice as many label flips for given bound on G(n, () (See Figure 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.
4.1 EFFICIENT IPPEEMENTAION VIA LEAST SQUARES CLASSIFIERS
There may appear to be one major impracticality of the algorithm proposed in the previous section, considered naively: treating the function & as an entire would require that train multiple classifiers, over multiple random draws of the labels y, all to make a prediction on 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 in line with the cost of classifying single example. The full procedure, with all the parts described below, can be found in Algorithm
process
Linear least-squares classification The fundamental simplifying assumption we make in this work is to restrict the "training" process done by the classifier e to done via a linear least- squares solve. Given the training set ( W we assume that there exists some feature mapping h Rd + R (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 2imn (i.e. independent of the training labels, which are presumed to be potentially poisoned). This may seem to be strong assumption, but similar assumptions are commonly made when using pre-trained models or in the meta-learning setting, and the transfcrabillit 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((11n)) E R be the training point features and let y V1.n E f0, 1)" l
be the labels. Our training process consists of finding the least- squst-squarss fit the training data, i.c., we find parameters e R via the normal equation _ = x)* X and then we make a prediction on the new example via the linear function 11(2++1) 1 Although it may seem odd fit 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 straightforward. Specifically, letting
a= x (x"x) M(Cn+1)",
(11)
the prediction ((I++1) can be equivalently given by a (this is effectively just the kernel rep- resentation of the linear classifier). Thus, we can simply compute a one time and then randomly sample many different sets of labels in order to build standard randomized smoothing bound. Further, we can pre-compute just the X (xTx) term and reuse it for each test point.
l2 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 '2 regularized version of least-squares. This is common tool for solving systems with ill-conditioned or random design matrices (Hsu et al. 2014,, Suggala et al. [0088). Luckily, there still exists a pre-computable closed-form solution this problem, whereby we solve
x x + h(
(12)
The other parts of our algorithm remain unchanged. Following results in Suggala et al. (2018). we set the regularization parameter À + q)
X X) where à² y X.30 is estimate d²k 2n

---

Under review as a conference paper at ICLR 2020
of the variance Dicker 2014) and kc()) 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 the linear struc- ture of this prediction, we can forego sampling- based approach entirely and directly bound the tail probabilities using Chernoff bounds. Because the underlying binary prediction function & will out- put the label 1 for the test point whenever ot 2 1/2 and 0 otherwise, we can derive analytical upper bound on the probability that 9 predicts one label or the other via the Chernoff bound. By upper bounding the probability of the opposite prediction, we simultaneously derive lower bound on which can be plugged in to (I0) to determine the classifier's s robustness. Concretely, we can upper bound the probability that the classifier outputs the label 0 by
P(a" y S 1/2) S min 150
e/2
II
Ele
min 1>D
e/2
II qe t0. 2E) + (1 - q)e toa
(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 uncon- strained 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 's method. Note that in some cases, neither Chernoff upper bound will be less than 3. meaning we cannot determine the true value of g(U, Φ). In these cases, we simply define the classifie'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 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 deep network.
EXPERIMENTS
Following Koh & Liang 2017) and Steinharrtt 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-fliping attacks. For each dataset and each noise level 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 = oc (or 10% for MNIST) by letting y constant. A constant classifier would be infinitely robust, but it is not 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 sense of the scale of our certifi- cations, we also generated label-flipping attacks against the undefended binary MNIST and Dogfish models. Following previous work, the undefended models were implemented as convolutional neu- ral networks, trained on the clean data, with all but the top layer Trozen-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 I and 7, totalling 13007 training points and 2163 test points. We trained a simple convolutional neural network on the other eight MNIST digits to leam 50-dimensional feature embedding and then
7

---

Under review as a conference paper at ICLR 2020
Percenlage Training
Percentage Training
0.0
0.5
0.2
5.
D5
1,0
1,0
0.025
0.05
Certifee Acqursoy
Certified Acouracy
(=0.3,A 12291
-3327
0.45..A
13946
undelenndd
250
são
750
1000
1250
1500
1750
2000
50
100
150
200
250
300
350
400
Label Filps
Label Flips
(a) Binary MNIST (classes and 7)
(b) Full MNIST
Figure I: MNIST 1/7 (n 13007, left) and full MNIST (n = 60000, right) test set certified accuracy to adversarial training label flips as is varied. The hyperparameter controls a robust/non-robut accuracy trade-off. The solid lines represent certified accuracy, except the undefended classifier which represents our attack. The dashed lines of the same color are the overall non-robust accuracy of each classifier. The black dotted line is the performance of a constant classifier, assuming equal representation of the classes.
Percentage of Training
1.0
0.0001 A 1556
0-025. 1594
Cartified Accuracy
0.2.A
0.6
0.4
0.2
Label Flips
Figure 2: Dogfish (n 1800) test set certified accuracy to adversarial label flips as & is varied. The classifiers' certified accuracy curves cross each other further along the x-axis.
calculated Chernoff bounds for G(p, σ) as described in Section 4.1 Figure La displays the certified accuracy the test for varying probabilities g. As in prior work randomized smoothing, the noise parameter balances trade-off; as g increases, the required margin [G Φ) to certify 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 lb depicts the certified accuracy for the full MNIST bounds and optimization algorithm in the multi-class case. In addition to this being significantly more difficult classification task, our pre- pre-trdined classifier could not rely on features learned from other handwritten digits; instead, we used the features from network trained on the Omniglot dataset (Lake 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 large number of adversarial label flips. We observed that regularization did not make large difference for the multi-class case, possibly due to the inaccuracy of the residual term when calculating the noise estimate.
set. See Appendix B for derivations of the
See Figure in Appendix for the effect of b regularization the OLS solution. We note that at slight cost to non-robust accuracy, the regularization results in substantially higher certified accuracy almost all radii. A similar effect was observed for all datasets and at all values of q.
8

---

Under review as a conference paper at ICLR 2020
Percentage Training 6.6
1.0
A
0.025.2
Cartifed Accuracy
-.
0.1.A
0.6
consiont
0.4
0.2
150
200
250
350
Label Flips
Figure 3: IMDB Review Sentiment (n 25000) test set certified accuracy. The non-robust accuracy slightly decreases q increases; for q 0.01 the non-robust accuracy is 79.108%, while for q 0.25 it 78.732%.
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) the standard ImageNet training set but removed all images labeled as any kind of dog or fish. Our pre- trained feature embedder was therefore capable of extracting image features but had concept of features specific to either class. We used PCA to reduce the 2048 dimensional feature space to 1700 dimensions before solving, ensure the system results of our poisoning attack along with our certified defense. Under the undefended model, more than 50% of the test points be successfully attacked with more than 7 label flips, whereas model with attack. 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 at most 0.83%.
underdetermined. Figure 2 displays the
0.001 can certifiably correctly classify 67.83% of the test points under the same
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 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 IMDB Figure plots the result of randomized smoothing procedure 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 Word2 to all the words in each review and averaged them. This feature embedding is considerably noisier than that of an image dataset, as sentiment classification. Indeed, Steinharde et al. (2017) also found that the IMDB dataset was much more susceptible adversarial corruption than images when using bag-of-word tent with this observation, we found smaller levels of noise to result in larger certified accuracy. We expect significant improvements could made with a more refined choice of feature embedding.
of the words in review are irrelevant to
features. Consis-
We also observed that increasing g does not significantly decrease the non-robust accuracy. We believe this is because the limitation of these classifiers 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 as q increased, but the margin of G(p, Φ) decreased too rapidly to certify 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 informative for classification.

---

Under review as a conference paper at ICLR 2020
6 CONCLUSION
In this work we have presented certified defense against 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 adver- sary who wishes to degrade the classifier's ' accuracy on the test distribution as whole, and it brings the adversary's 's objective more in line with that of backdoor attacks and test-time adversarial pertur- bations. Leveraging randomized smoothing, a method originally developed for certifying robustness test-time perturbations, we presented classifier that can be certified robust to these pointwise tuin-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, result- ing in truly certifiably robust classifier. This algorithm results in the first multi-class classification algorithm that certifiably robust to label-flpping attacks.
There are several avenues for improvement to this line of work, perhaps the most immediate be- ing 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 cet al. 2018) to also allow for efficient learning with perturbed inputs or more flexible representa- tions. 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, also hope that our defense to this threat model will inspire the development of more powerful train-time attacks, against which future defenses be evaluated.
REFERENCES
Anonymous. A framework for robustness certification of smoothed classifiers using f-divergences. Submitted to ICLR 2020, 2019.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of se- curity: Circumventing defenses adversarial examples. In P Proceedings of the 35th International Conference on Machine Learning, ICML 2018, July 2018.
Marco Barreno, Blaine Nelson, Russell Sears, Anthony D. Joseph, and J. D. Tygar. Can machine learning secure? In Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, ASIACCS '06, pp. 16-25, New York, NY, USA, 2006. ACM. ISBN 1-59593-272-0. doi: 1 121111111811888888
Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding. In Proceedings of the 28th International Conference Neural Information Processing Systems Volume 1, NIPS' 15, pp. 721 Cambridge, MA, USA, 2015. MIT Press.
B. Biggio, G. Fumera, and F. Roli. Security evaluation of pattern classifiers under attack. IEEE Transactions on Knowledge and Data Engineering, 26(4):984 996,, April 2014. doi: 10.1 TKDE.201
Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial la- bel noise. In Chun-Nan Hsu and Wee Sun Lee (eds.), Proceedings of the Asian Conference on Machine Learning. volume 20 of Proceedings of Machine Learning Research, pp. 97-112, South Garden Hotels and Resorts, Taoyuan, Taiwain, 14-15 Nov 2011. PMLR.
Liefeng Bo, Xiaofeng Ren, and Dieter Fox. Kernel descriptors for visual recognition. J. D. Lafferty, C. K. I. Williams, J. Taylor,,ylor, R. S. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems 23, pp. 244-252. Curran Associates, Inc., 2010.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, AlSec 17, pp. 3-14, New York, NY, USA, 2017. ACM. ISBN 978-1 1-5003-5202-4, doi: 10.1145/3128572.314400
10

---

Under review as a conference paper at ICLR 2020
Ruidi Chen and Ioannis Ch. Paschalidis. A robust learning approach for regression models based on distributionally robust optimization. J. Mach. Learn. Res., 19(1):517-564, January 2018. ISSN 1532-4435.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprini arXiv:/712.05522 2017.
Yudong Chen, Constantine Caramanis, and Shie Mannor. Robust sparse regression under adver- sarial corruption. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 774-782, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Lee H. Dicker. Variance estimation in high-dimensional linear models. Biometrika, 101(2):29--884, 03 2014. ISSN 0006-3444. doi: 10. 00.1009//iomet/a00055.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Dar- rell. Decaf: A deep convolutional activation feature for generic visual recognition. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 3 International Conference on Machine Learning. volume 32 of Proceedings of Machine Learning Research, pp. 647-655, Bejing, China, 22-24 Jun 2014. PMLR.
Reuben Feinman, Ryan R. Curtin, Saurabh Shintre, and Andrew B. Gardner. Detecting adversarial samples from artifacts. arXiv preprint 0rXiv:1703.00411 2017.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2016.
Daniel Hsu, Sham M. Kakade, and Tong Zhang, Random design analysis of ridge regression. Found. Comput. Math., 14(3):569-600, June 2014. ISSN 1615-3375. doi: 10. 1000007/10000-004-9199999
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8571- 8580. Curran Associates, Inc., 2018.
Sushrut Karmalkar and Eric Price. Compressed sensing with adversarial sparse noise via 11 regres- sion. arXiv preprint arXiv: /tdv::/80..0 0809.08055, 2018.
Adam Klivans, Pravesh K. Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regres- sion. arXiv preprint arXiv:1803.00 032411, 2018.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' pp. 1885 1894. JMLR.org, 2017.
Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. arXiv preprint arXiv:1811.0074 2018.
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350062666, 2015. ISSN 0036-8075. doi: 10.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6(11):2278-233) Nov 1998. ISSN 0018-9219. doi: 10.1109/5.726791

---

Under review as a conference paper at ICLR 2020
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. arXiv preprint arXiv:1802.012: 2018.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S. Jaakkola. A stratified approach robust- ness for randomly smoothed classifiers, arXiv preprint arXiv:/906. 0404:044900 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin, Certified adversarial robustness with additive gaussian noise. arXiv preprint 180.01380,, 2018.
Chang Liu, Bo Li, Yevgeniy Vorobeychik, and Alina Oprea. Robust linear regression against training data poisoning. In AlSec 2017 Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, co-located with CCS 2017, AlSec 2017 - Proceedings the 10th ACM Workshop on Artificial Intelligence and Security, co-located with CCS 2017, pp. 91-102. Association for Computing Machinery, Inc, 11 2017. doi: 10. 10.1144/118857233444444
T. Liu and D. Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(3):447-46) March 2016. ISSN 0162-8828. doi: 10. 10111//T
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Amnual Meeting of the Association for Computational Linguistics: Human Language Technologies Volume I, HLT '11, pp. 142-150, Stroudsburg, PA, USA, 2011. Association for Computational Linguistics. ISBN 978-1-932432-87--.
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. In 5th International Conference on Learning Representations, ICLR 2017 Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Sebastian Mika. Kernel fisher discriminants, 2003.
Luis Muñoz González, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C. Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back-gradient optimization. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AlSec 17. pp. 27-38. New York, NY, USA, 2017. ACM. ISBN 978-1-4503-5202-44 doi: 10. 1145/3128572.3144000
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26, pp. 1196-1204. Curran Asso- ciates, Inc., 2013.
N. Papernot, P. McDaniel, A. Sinha, and M. P. Wellman. Sok: Security and privacy in machine learning. In 2018 IEEE European Symposium on Security and Privacy (EuroS P), pp. 399-414, April 2018.
doi: 10. 10. 0.0053..
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. pp. 2233-2241, 07 2017. doi: 10. 10.1109/CVPR.22017..40
Andrea Paudice, Luis
and Emil C. Lupu. Label sanitization against label flipping poisoning attacks. In Carlos Alzate, Anna Monreale, Haytham Assem, Albert Bifet, Teodora San- dra Buda, Bora Caglayan, Brett Drury, Eva Carcía-Martín, Ricard Gavaldà, Irena Koprinska, Ste- fan Kramer, Niklas Lavesson, Michael Madden, Ian Molloy, Maria-Irim Nicolac, and Mathieu Sinn (eds.), ECML PKDD 2018 Workshops, pp. 5-15, Cham, 2019. Springer International Pub- lishing.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust esti- mation via robust gradient estimation. arXiv preprint arXiv:1802.06453 2018
P.J. Rousseeuw and A.M. Leroy. Robust Regression and Outlier Detection. Wiley Series in Proba- bility and Statistics. Wiley, 1987. ISBN 9780471852339.
12

---

Under review as a conference paper at ICLR 2020
Benjamin I.P. Rubinstein, Blaine Nelson, Ling Huang. Anthony D. Joseph, Shing- hon Lau, Satish Rao, Nina Taft, and J. D. Tygar. Antidote: Understanding and defending against poisoning of anomaly detectors. In Proceedings of the 9th ACM SIGCOMM Conference Internet Measure- ment, IMC '09, pp. 1-14, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-77 777-600788-8-444. doi:
10.1145/164899.114443 1644895
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang. Huan Zhang, llya Razenshteyn. and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv: AKV::/990604584, 2019.
Ali Shafahi, W. Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 6103-6113, Curran Associates, Inc., 2018.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss min- imization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5739-5748, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Jacob Steinhardt, Pang Wei Koh, and Percy Liang. Certified defenses for data poisoning attacks. In Proceedings of the 3 International Conference on Neural Information Processing Systems, NIPS' 17, pp. 3520-3532, USA, 2017. Curran Associates Inc. ISBN 978-1-5108-6099
Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar, Connecting optimization and regulariza- tion paths. In S. Bengio, H. Wallach, Larochelle, Grauman, N. Cesa- BesacBiancch, and Garnett Curran Asso-
(eds.), Advances in Neural Information Processing Systems 31, pp. ciates, Inc., 2018
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2016
Rahim Taheri, Reza Javidan, Mohammad Shojafar, Zahra Pooranian, Ali Miri, and Mauro Conti. On defending against label flipping attacks on malware detection systems. arXiv preprint arXiv: 04473, 2019.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8000-8010. Curran Associates, Inc., 2018.
Han Xiao, Huang Xiao, and Claudia Eckert. Adversarial label flips attack on support vector ma- chines. In Proceedings of the 20th European Conference on Artificial Intelligence, ECAI' 12, pp. 870-875, Amsterdam, The Netherlands, The Netherlands, 2012. IOS Press. ISBN 097-0. doi: 10.3233/978- 1-1-191-199999999 109999999778777
Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Bckert, and Fabio Roli. Is feature selection secure against training data poisoning? In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceed- ings of Machine Learning Research, pp. 1689-1698. Lille, France, 07-09 Jul 2015. PMLR
Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen. Generative poisoning attack method against neural networks. arXiv preprini arXiv: 170.001340 2017.
Chih- Kuan Yeh, Joon Kim, Ian En-Hsu Yen, and Pradeep K Ravikumar, Representer point selection for explaining deep neural networks. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N.
and R. Gamett (eds.), Advances in Neural Information Processing Systems 31, pp. 9291-9301. Curran Associates, Inc., 2018
13

---

Under review as a conference paper at ICLR 2020
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Wein- berger (eds.), Advances in Neural Information Processing Systems 27, pp. 1320-3328 Curran Associates, Inc., 2014.
Chen Zhu, W. Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks on deep neural nets. In Kamalika Chaudhuri and Rus- lan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 Proceedings of Machine Learning Research, pp. 7614-7623, Long Beach, Califor- nia, USA, 09-15 Jun 2019. PMLR.
A GENERIC RANDOMIZED SMOOTHING ALGORITHM
Algorithm 2 Generic randomized smoothing procedure
Input: function & X' + {0, 1}, number of samples N, smoothing distribution failure proba- bility 8 > 0
for i ,,...,N N do
Sample 24 ~ and compute y; = =x;,,
end for Compute approximate smoothed output
N
6(H, Φ) = 1
Σ i=1
Vi 2 1/2
(14)
N
Compute bound G(p, ø) such that with probability 1 8
G(H,
{
G(u, d) 2 ((,
if ( =1 if g(u, =0
(15)
Output: Prediction δ(p, σ) and probability bound G(u, Φ), or abstention if ğ(n, Φ) and G(p, Φ) are on different sides of 1
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 class label y E {I,..., K). }. and we again seek some smoothed prediction such that the classifier's prediction on a new point will not change with some number flips of the labels in the training set.
B. RANDOMIZED SMOOTHING IN THE MULTI-CLASS CASE
We here extend our notation the case of more than two classes. Recall our original definition of G,
G(p, Φ) = (ex=((((x))
u(z))(r)dr
where o: 2 X' {0,1) 1). More generally, consider classifier X [K]. outputting the index of one of K classes. Under this formulation, for a given class E [K], we have
G(u, d. c) = Ex-=lld(x)] = - (())d
(16)
where (x) = (d(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(n, Φ) arg max Glu, c)..
(17)
14

---

Under review as a conference paper at ICLR 2020
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 multi- class setting finds some set of weights
(18) where Y E {0, 1]mX K is a binary matrix with each row equal to a one-hot encoding of the class label (note that the resulting 3 E R is now matrix, and we let B3 refer to the ith column). At prediction time, the predicted class of some new point Int1 is simply given by the prediction with the highest value, i.e.
-= (x"X) Y
gn+1 = arg max 3,
T h(#x+1).
(19)
{
Alternatiely, following the same logic as in the binary case, this same prediction can be written in terms of the a variable as
In+1 arg max a YY
(20)
where Y, denotes the ith column of Y,
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(a Y, Yz)
(21)
for all alternative classes 1.. By the Chernoff bound, we have that
log P(a"YY < YY) = log P(a" (Y, Y, 0)
(22)
K
min [SU
log E
e tay (0s {0))
y takes on three different distributions depending on if y, i, if y = or if y * and y, # Specifically, this variable can take on the terms +1, -1 with the associated probabilities
The random variable Y5=- Yu
1 1-q q q/(K 1)
y otherwise.
P(Y;: Yjp- +1)
1- q q/(K- 1)
y i',
P(Y;: Yjp- -1)
(23)
otherwise.
q(K - 22/(KK 1) y - =
P(Y; Y5x 0)
1 1- 1-29/ 1)
otherwise.
Combining these cases directly into the Chernoff bound gives
K
log P(a Y, < a Yz) S min
Σ log
(1 - g)e ta, +
+ K K-1 c la, +
250
K - 1
=i
Σ log
q la; + 11 K
K - 2
+ (1 - 9)e lay )
-
Σ
log
taj
+1 - 2
q
+ 9
tay
K-1
K K
(24)
Again, this problem convex in t, and so can be solved efficiently using Newton's 's method. And again since the reverse case can be computed via the same expression in an unconstrained fashion. Specificially, we can do this for every pair of classes and i', and return the i which gives the smallest lower bound for the worst-case choice of.
similarly optimize this
15

---

Under review as a conference paper at ICLR 2020
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 μ., P be defined as in Section 4 except that as in the previous secftion when label is flipped with probability q it is changed to of the other K 1 classes uniformly at random. Let 14; and Pj refer to the independent measures on each dimension which collectively make up the factorized distributions jr and p (i.e., μu(x) = I (z(z)), Further, let YJ be the tth element of Y1, meaning the "original" class which may or may not be flipped when sampling from μ. First noting that each dimension of the distributions μ and p are independent, we have
KL |l p))
KL(Ps ll mi)
E
KL(ps ms)
K
Pt(i)
Σ
pi(i) log
mi(l)
po(YF))
(:(Y2)
r
(x log
+ Px(( log
(T,
(1 q) log
1--9 q K-1
+ K -
9
log
K-T
1
Kq
(1 - (K(K - 1)
r
log
K
Plugging in the robustness guarantee 1 we have that g(U, Φ) g(p, Φ) so long as
log(4p(1 p))
(25)
2(1 R-1 ) log (1 (1-))(k-))
Setting K recovers the divergence term (9) and the bound 10
C DESCRIPTION OF LABEL-FLIPPING ATTACKS ON MNIST 1/7 AND DOGFISH
Due to the dearth of existing work on label-flipping attacks for deep networks, our attacks on MNIST and Dogfish were quite straightforward; expect significant improvements could be made to tighten this upper bound.
For Dogfish, we used pretrained Inception network (Szegedy al. 2016) 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 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 E, 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 (017)) the influence of flipping the label of training point
16

---

Under review as a conference paper at ICLR 2020
(2, to = (z. the loss at the test point Stest is:
dz -c.)---z)___ V VeL(Ziost 0) d0 d0c,a-.-z
de
de
Ve 0) 11 (VoL(zT,0) V
For logistic regression, these values can easily be computed in closed form.
D ADDITIONAL PLOTS
Percentage of Training Set
1.0
0.8
Certified Accuracy
0.4
q 3.A 12291
0.2
q 0.4,A 13237
q 0-0,AAA-
0.0
250
500
750
1000
1250
1500
1750
Label Flips
Figure 4: MNIST 1/7 test set certified accuracy with and without &g regularization in the computation of a. Note that the unregularized solution achieves almost 100% non-robust accuracy, but certifies significantly lower robustness. This implies that the "training" process is not robust enough to label noise, hence the lower margin by the ensemble. In comparison, the regularized solution achieves significantly higher margins, at a slight cost in overall accuracy.
Minimum Margin
Certify Robustness at Flips
Number of Label Flips Certifially Robust at p = 1 10
1.0
250
KL-Divergence Dual
Discrete
200
Label Flips
160
0.6
KL-Div Div-Dierreeze Dual Upper Bound Upper Bound (Tight)
0.5
Figure 5: Left: Required margin p certify given number of label flips using the generic KL bound (TO) versus the tight discrete bound (4). Right: The same comparison, but inverted, showing the certifialle robustness for given margin. The tight bound certifies robustness approximately twice as many label flips.
17


Reviews:
[{"review_id": "SJeyIIenFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper leverages the randomized smoothing technique, on labels of images during training, to counter the adversarial label-flipping attack. The authors proposed a strategy to build classifiers that are certifiably robust against a strong variant of label-flipping attack that can target each test example independently. The resulting classifier can make a prediction and includes certification for each test point. On a simple binary classification problem, the proposed defensive significantly improves accuracy towards the label-flipping attack. I have the following questions about this work:\n\n1. Can the authors provide training and testing CPU time and memory consumption, and compare them with the training without defense?\n\n2. Can the authors generalize the proposed adversarial defense to the multi-class classification problem?\n\n3. Can the authors also test the algorithms on the MNIST and CIFAR10 dataset with multiple different selected pairs?\n\n4. Besides randomized smoothing on the input images, recently Wang et al showed that randomize the deep nets can\nalso improve the deep nets and they gave it a nice theoretical intepretation. Here is the reference: Bao Wang, Binjie Yuan, Zuoqiang Shi, Stanley J. Osher. ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies, arXiv:1811.10745, NeurIPS, 2019\n\nOverall, this paper studies an interesting and important certified adversarial defense against label-flipping attack problems with a focus on certification on each test data, but more experimental verification is needed. Please address the above questions in rebuttal.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Hklgwt92Yr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary.\n\nThe 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.\n\nThe authors use randomized smoothing on a binary linear classifier with logistic loss and deduce a radius of certification that is a function of the probability of flipping labels in the training data and the probabilistic separation p.\n\n\nMajor concerns.\n\n1) I find the application of certification to data poisoning type adversarial attacks rather limited and is not of a major interest to the verification/certification community. Certification arose as a major issue since models implemented in practice can be fooled if subjected to noise at testing time. However, the proposed certification is on the flip rate of the labels in the training data. Since this is fixed, certification in this context is not of a major interest. The only potential relevance of such a problem is upon training models in a federated approach (online learning) even then, one can argue that the portion of the data that the adversary has access to is a small portion to the complete dataset. It feels to be that certification was somehow forced into data poisoning type of adversarial attacks although they jointly do not make much sense.\n\n\n\n While I do appreciate the work from authors, I am not convinced that certification in this context makes significant sense and has interest to only small group of researchers.\n\n\n2) There are some serious limitation in the work specifically that the bounds are derived for a binary classifier. While the authors did indeed discuss the multi-class case, there are no experiments beyond the binary classification. The dataset sets where the sentiment analysis of IMDB, MNIST1/7 and the dog fish classes from ImageNet. Experiments on multi-class case is essential here for practical reasons.\n\n3) May the authors clarify some few things in the experiments for me.\n\nIf I understand Figures 1,2,3 correctly, then what the authors do is that they train networks over different number of label flipping (shown as a percentage on the top of the figure). Then for each test example, they compute the maximum radius given in Eq 10 for multiple qs. If the number of flipping in the dataset is less than r (less than the maximum radius per sample) then the sample is certified.\n\n\tQuestion. I do not understand why is an example considered certifiable when it is both correctly classified and unaffected under at least r flips? In page 7 of the experiments section, the authors say \"we plot the fraction of the test set that was both correctly classified and certified to not change under at least r flips\".\n\n\tQuestion. Can the authors comment on the expected performance of the network upon comparing certified accuracy with networks having q as probability flip rate and when the training data flip rate percentage is exactly q. Will the certified accuracy for q that matches the flip rate in the dataset be better than the ones with q that does not match the training flip rate. For instance, in Figure 1, note that the percentage in the flip rate of the training dataset ranges from 0 to 14%, however the certified accuracy was for q that ranges from 30 to 47.5. Will the certified accuracy at a given percentage of the data be the highest for q that match the flip rate? \n\n\n\tQuestion. Since the classifier is linear (since features are fixed), can the authors comment perhaps on the relation between p and q?\n\n\n\n\n\nMinor comments.\n\n1) The authors need to define what p is. The authors can correct me if I'm wrong, p is a lower bound on the separation of the probability for some class, i.e.  Prop(f(x) = 1) >= p. This is similar to Cohen et al. 19. This was not defined and come as a surprise in Eq 3.\n\n2) Moreover, in the work of Cohen et al. the smoothed classifier g is smoothed in probability which is unlike definition 1. Perhaps definition 1 fits more the framework of Lecuyer et al 19 as they showed that if an algorithm A is differentially private (probability distribution do not change much under database perturbations), the expectation over the algorithm is also differentially private.\n\n3) In the solution to the ridge regression, \\alpha is a function of the tested sample, e.g. eq 11. This can be confusing and I advise authors to consider adding a superscript \\alpha^j indicating that this is a function of the test sample j. Similarly, in the algorithm \\alpha in Eq 7 and bullet point 1.\n\n4) In example 3, the paper cited is a concurrent submission to ICLR20 and not 19.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkenaNa6tH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis 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. \n\nThe authors provide a succinct summary of current research concerning randomized smoothing. The novelty in this paper is that it considers randomized smoothing defenses for data poisoning (label flipping) attacks, as opposed to perturbation based attacks. While the paper was an enjoyable read, I recommend rejecting the paper due to the following shortcomings that:\n\n(1) The paper is essentially studying (a variant of) linear regression. This was really not obvious from the title or the abstract. It meant that as a reader, I had high expectations but was let down upon reading section 4.1.\n\n(2) What prior work exists for data poisoning attacks against linear regression or logistic regression? How does the contribution in this paper fit in that context?  Adding some discussion along these lines to the paper seems necessary.\n\n(3) There is no explanation why the authors chose the specific datasets that they studied.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop a certified defense for label-flipping attacks (where an adversary can flip labels of a small number of training set samples) based on the randomized smoothing technique developed for certified defenses to adversarial perturbations of the input. The framework applies to least-squares classifiers acting on pretrained features learned by a deep network. The authors show that the resulting framework can obtain significant improvements in certified accuracy against targeted label flipping attacks for each test example.

While the paper makes some interesting contributions, the reviewers had the following shared concerns regarding the paper:
1) Reality of threat model: The threat model assumes that the adversary has access to the model and all of the training data (so as to choose which labels to flip), which is very unlikely in practice. 
2) Limitation to least squares on pre-trained features: The only practical instantiation of the framework presented in the paper is on least squares classifiers acting on pre-trained features learned by a deep network.

In the rebuttal phase, the authors clarified some of the more minor concerns raised by the reviewers, but the above concerns remained.

Overall, I feel that this paper is borderline - If the authors extend the applicability of the framework (for example relaxing the restriction on pre-training the deep features) and motivating the threat model more strongly, this could be an interesting paper.
Decision: Reject