Certified Robustness of Nearest Neighbors against Data Poisoning Attacks
Authors: Jinyuan Jia
Xiaoyu Cao
Neil Zhenqiang Gong
Venue:  (2021)

Abstract: Data poisoning attacks aim to corrupt a machine learning model via modifying, adding, and/or removing some carefully selected training examples, such that the corrupted model predicts any or attacker-chosen incorrect labels for testing examples. The key idea of state-of-the-art certified defenses against data poisoning attacks is to create a \emph{majority vote} mechanism to predict the label of a testing example. Moreover, each voter is a base classifier trained on a subset of the training dataset. Nearest neighbor algorithms such as $k$ nearest neighbors (kNN) and radius nearest neighbors (rNN) have  intrinsic majority vote mechanisms. In this work, we show that the intrinsic majority vote mechanisms in kNN and rNN already provide certified robustness guarantees against general data poisoning attacks. Moreover, our empirical evaluation results on MNIST and CIFAR10 show that the intrinsic certified robustness guarantees of kNN and rNN outperform those provided by state-of-the-art certified defenses. 

Under review as a conference paper at ICLR 2021
CERTIFIED ROBUSTNESS OF NEAREST NEIGHBORS AGAINST DATA POISONING ATTACKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Data poisoning attacks aim to corrupt machine learning model via modifying, adding, and/or removing some carefully selected training examples, such that the corrupted model predicts any or attacker-chosen incorrect labels for testing examples. The key idea of state-of-the-art certified defenses against data poisoning attacks is to create a majority vote mechanism to predict the label of a testing example. Moreover, each voter is base classifier trained on a subset of the training dataset. Nearest neighbor algorithms such as k nearest neighbors (kNN) and radius nearest neighbors (rNN) have intrinsic majority vote mechanisms. In this work, we show that the intrinsic majority vote mechanisms in kNN and rNN already provide certified robustness guarantees against general data poisoning attacks. Moreover, our empirical evaluation results on MNIST and CIFAR 10 show that the intrinsic certified robustness guarantees of kNN and rNN outperform those provided by state-of sile-off-her tt-the-art art certified defenses.
INTRODUCTION
Data poisoning attacks (Barreno et al. 2006 Nelson et al. 2008 Biggio et al., 2012: 2013a Xiao
et al. 2015b; Steinhardt et al., 2017| Shafahi al.) 2018) aim to corrupt the training phase of machine learning system via carefully poisoning its training dataset including modifying, adding, and/or removing some training examples. The corrupted model predicts incorrect labels for testing examples. Data poisoning attacks pose severe security concerns to machine learning in critical application domains such autonomous driving (Gu al. (017). cybersecurity (Rubinstein et al. |009) (Suciu et al. 2018 Chen et al. (0117). and healthcare analytics (Mozaffari-
et al. 2014). Unlike adversarial examples (Szegedy et al., 2014, Goodfellow et al. 20144] Carlini & Wagner 2017
which add perturbation to each testing example to induce misclassification data poisoning attacks corrupt the model such that misclassifies many clean testing examples.
Multiple certifiably robust learning algorithms (Ma et al. 2019: Rosenfeld et al., 2020: Levine & Feizi 2020 Jia et al. (020)) against data poisoning attacks were recently developed. learning algorithm is certifiably robust against data poisoning attacks if it can learn a classifier on a training dataset that achieves a certified accuracy on a testing dataset when the number of poisoned training examples is more than threshold (called poisoning size). The certified accuracy of a learning algorithm is lower bound of the accuracy of its learnt classifier no matter how an attacker poisons ofte--of-hhe-att the-art certifiably robust learning algorithms (Levine & Feizi 2020 Jia et al., 2020) is to create majority vote mechanism to predict the label of a testing example. In particular, each voter votes label for a testing example and the final predicted label is the majority vote among multiple voters. For instance, Deep Partition Aggregation (DPA) (Levine & Feizi 2020) divides the training dataset into disjoint partitions and learns a base classifier (i.e., a voter) on each partition. Bagging (Jia et al. (020) also learns multiple base classifiers (i.e., voters), but each of them is learnt on random subsample of the training dataset. We denote by a and b the labels with the largest and second largest number of votes, respectively. Moreover, Sa and sy respectively are the number of votes for labels a and when there are no corrupted voters. The corrupted voters change their votes from a to b in the worst-case scenario. Therefore, the majority vote result (i.e., the predicted label for a testing example) remains to be a when the number of corrupted voters is no larger than S
the training examples with the given poisoning size. The key idea of state-of-
[ 1. In other words, the number of corrupted voters that a majority vote mechanism can tolerate depends on the gap s - Sy between the largest and the second largest number of votes.

---

Under review as a conference paper at ICLR 2021
training example
testing example
poisoned example
0
D
2
2
?
without attack
individual certification
joint certification
Figure 1: An example to illustrate individual certification vs. joint certification. Suppose rNN correctly classities the two testing examples without attack. An attacker can poison 3 training examples. The attacker can make rNN misclassify each testing example individually. However, the attacker cannot make rNN misclassify both testing examples jointly.
However, of-te-of-the-art certifiably robust learning algorithms achieve suboptimal certified accuracies due to two key limitations. First, each poisoned training example leads to multiple corrupted voters in the worse-case scenarios. In particular, modifying training example corrupts two voters (i.e., two base classifiers) in DPA (Levine & Feizi 2020) and corrupts the voters whose training subsamples include the modified training example in bagging (Jia et al. 2020). Therefore, given the same gap Sa Sb between the largest and the second largest number of votes, the majority vote result is robust against small number of poisoned training examples. Second, they only certify robustness for each testing example individually because it is hard to quantify how poisoned training examples corrupt the voters for different testing examples jointly. Suppose the classifier learnt by learning algorithm can correctly classify testing inputs X1 and X2. An attacker can poison e training examples such that the learnt classifier misclassifies X1 xrx2, but the attacker cannot poison training examples such that both x and X2 are misclassified. When the poisoning size is existing certifiably robust learning algorithms would produce a certified accuracy of for the two testing examples. However, the certified accuracy can be 1/2 if we consider them jointly.
k nearest neighbors (kNN) and radius nearest neighbors (rNN) (Fix & Hodges 1951 I, Cover & Hart 1967) have intrinsic majority vote mechanisms. Specifically, given testing example, kNN (or rNN) predicts its label via taking a majority vote among the labels of its nearest neighbors (or neighbors within radius r) in the training dataset. Our major contribution in this work is that we show the intrinsic majority vote mechanisms in kNN and rNN make them certifiably robust against data poisoning attacks. Moreover, kNN and rNN address the limitations of tatte-ffthee-rt certifiably robust learning algorithms. Specifically, each poisoned training example leads to only one corrupted voter in the worse-case scenario in KNN and rNN. Therefore, given the same gap Sa Sb. the majority vote result (i.e., predicted label for a testing example) is robust against more poisoned training examples in KNN and rNN. Furthermore, testing examples. Figure [ iillusrraes an example of individual certification and joint certification with two testing examples in rNN. When we treat the two testing examples individually, an attacker can poison 3 training examples such that rNN misclassifies each of them. However, when we treat them jointly, an attacker cannot poison training examples to misclassify both of them. We propose such joint certification to derive better certified accuracy for rNN. Specifically, we design methods to group testing examples in a testing dataset such that we can perform joint certification for each group of testing examples.
show that rNN enables joint certification of multiple
We evaluate our methods on MNIST and CIFARIO datasets. We use & distance metric to calculate nearest neighbors. First, methods substantially outperform state-of-the-ar certifiably robust learning algorithms. For instance, when an attacker can arbitrarily poison 1,000 training examples on MNIST, the certified accuracy of rNN with = is 40.8% and 33.5% higher than those of DPA (evine& & Feizi| (220)) and bagging (Jia et al., 2020), respectively. Second, our joint certification improves certified accuracy. For instance, our joint certification improves the certified accuracy of rNN by 15.1% % when an attacker can arbitrarily poison 1,000 training examples on MNIST.
In summary, we make the following contributions:
2

---

Under review as a conference paper at ICLR 2021
We derive the intrinsic certified robustness guarantees of kNN and rNN against data poison- ing attacks.
We propose joint certification of multiple testing examples to derive a better certified robustness guarantee for rNN. rNN is the first method that supports joint certification of multiple testing examples against data poisoning attacks.
We evaluate our methods and compare them with oftte-of-thearr on MNIST and CIFARIO.
2 PROBLEM SETUP
Learning setting:
Assuming we have a training dataset Der with training examples. We denote by M a learning algorithm. Moreover, we denote by .M x) the label predicted for testing input by a classifier learnt by M on the training dataset Dtr- For instance, given training dataset Der and a testing input x, kNN finds the k training examples in D,, that are the closest to x as the nearest neighbors, while INN finds the training examples in Dtr whose distances the nearest neighbors. The distance between a training input and a testing input can be measured by any distance metric. Then, kNN and rNN use majority vote among the nearest neighbors to predict the label x. Specifically, each nearest neighbor is a voter and votes its label for the testing input x; and the label with the largest number of votes is the final predicted label for x.
no larger than as
Data poisoning attacks: We consider data poisoning attacks (Rubinstein et al. 2009: Biggio et al. 2012. Xiao al., 2015a] [i et al. 2016 MuñozzGonzzlee et al. 2017 Jagielski al. 2018) that aim to poison (i.e., modify, add, and/or remove) some carefully selected training examples in D., such that the corrupted classifier has a low accuracy for testing examples indiscriminately. For simplicity, we use Dřr to denote the poisoned training dataset. Moreover, we define the poisoning size e as the minimal number of modified/aldded/emnvve training examples that can turn Dar into D We use ((Dtr,e) e) to denote the set of poisoned training datasets whose poisoning sizes are at most e. Formally, we define ((D,,, e) as follows:
S(D e) {Di, (i D - |D n Do-l Se,,
where (ix,, |D+l - Dir n Darl is the poisoning size of Dū,-. Note that modifying a training example is equivalent to removing training example and adding new one. Given training dataset Der and poisoning size e, an attacker aims to craft poisoned training dataset Dt, minimize the testing accuracy of the classifier learnt by algorithm M on Di,..
Certified accuracy: Given training dataset Der and learning algorithm M, we use certified accu- racy on testing dataset Die {(x;, b-) to measure the algorithm's 's performance. Specifically, we denote certified accuracy at poisoning size e as CA((e) and formally define it as follows:
EOGIWEDDI L(M(D) xx) = vt)
CA(e)
min E(Drs()
(2)
DDeel
where T is the indicator function and M(Di,, x;) is the label predicted for a testing input x; by the classifier learnt by the algorithm M on the poisoned training dataset D CA((e) is the least testing accuracy on Die that the learning algorithm M can achieve no matter how an attacker poisons the training examples when the poisoning size is at most Our goal is to derive lower bounds of C'((e) for learning algorithms KNN and rNN.
3 CERTIFIED ACCURACY OF KNN AND RNN
We first derive a lower bound of the certified accuracy via individual certification, which treats testing examples in Die individually. Then, we derive a better lower bound of the certified accuracy for rNN via joint certification, which treats testing examples jointly.
3.1 INDIVIDUAL CERTIFICATION
Given a poisoning size at most e, our idea is to certify whether the predicted label stays unchanged not for each testing input individually. If the predicted label of a testing input stays unchanged
3

---

Under review as a conference paper at ICLR 2021
and it matches with the testing input's true label, then kNN INN certifiably correctly classifies the testing imput when the poisoning size is at most e. Therefore, we can obtain a lower bound of the certified accuracy poisoning size the fraction of testing inputs in Dre which kNN or rNN certifiably correctly classifies. Next, we first discuss how to certify whether the predicted label stays unchanged not for each testing input individually. Then, we show our lower bound of the certified accuracy at poisoning size e.
(i.e.,
Certifying the predicted label of testing input: Our goal is to certify that M(Drr, x) M(D x) for a testing input x when the poisoning size is no larger than a threshold. Given a training dataset Der (or a poisoned training dataset Di,)) and a testing input x, we use (V,,,,, (or (DD x)) to denote the set of nearest neighbors of x in Der (or Diy)) for kNN or INN. We note that there may exist ties when determining the nearest neighbors for kNN, i.e. multiple training examples may have the same distance to the testing input. Usually, kNN breaks such ties uniformly at random. However, such random ties breaking method introduces randomness, i.e., the difference of nearest neighbors before and after poisoned training examples (i.e...((D)) x) vs. (N x)) depends on the randomness in breaking tics. Such randomness makes it challenging to certify the robustness of the predicted label against poisoned training examples. To address the challenge, we propose to define a deterministic ranking of training examples and break ties via choosing the training examples with larger ranks. Moreover, such ranking between clean training examples does not depend on poisoned ones. For instance, we can use a cryptographic hash function (e.g., SHA-1) that is very unlikely to have collisions to hash each training example based on its input feature vector and label, and then we rank the training examples based on their hash values.
We use 81 denote the number of votes in (Der, x) for label 1, i.e., the number of nearest neighbors in N (Dtr.))) x) whose labels are l. Formally, we have si = Exx, (.)...( I(y, = I), where / = 1, 2, ..... and I is an indicator function. kNN or rNN essentially predicts the label of the testing input x as the label with the largest number of votes, i.e., MM(D,,, x) = arg max .e) 81- Suppose a and are the labels with the largest and second largest number of votes, i.e., Sa and s, are the largest and second largest ones among {81, ... .. respectively. We note that there may exist ties when comparing the labels based on their votes. We define deterministic ranking of labels in 21, , e} and take the label with the largest rank when such ties happen. In the worse-case scenario, each poisoned training example leads to one corrupted voter in kNN or rNN, which changes its vote from label a to label b. Therefore, KNN rNN still predicts label for the testing input when the number of poisoned training examples is no more than 8a- - 1 (without considering the ties breaking). Formally, we have the following theorem:
2
Theorem 1. Assuming we have a training datasel Dtr, a testing input x, and nearest neighbor algorithm M (i.e., KNN or rNN). a and b respectively are the two labels with the largest and second largest number of votes among the nearest neighbors N x) of x in Dir. Moreover, Sa and ss are the number of votes for a and b, respectively. Then, we have the following:
M(D,, x) = a, VD E S(Dor.)).e 8a S + I(a b
(3)
2
Proof. When an attacker poisons at most training examples, the number of changed nearest neighbors in (Dtr,, is at most e. We denote by st (xxx
x) 1(1 = v;) the number of votes for label I among the nearest neighbors (Dr,,, x) in the poisoned training dataset, where 1= =1,2,-. ... C. Then, we have 81 e S si S 81 + e for each 1 = 1,2, ... ,. Therefore, when e < 55.5% +.=00)) 11,, we have S -s; 2 8a 15-85 8t, --e > 0i < and s s 2 8a 12--5, 86 2-e 2 0 if a > b. Thus, the nearest neighbor algorithm still predicts label a for x in both cases based on our way of breaking ties, i.e., we have M(D x) = a when < -. s.. Ma>b)) 1.
Deriving a lower bound of CA(e): KNN or rNN certifiably correctly classifies a testing input x it correctly predicts its label before attacks and the predicted label stays unchanged after an attacker poisons the training dataset. Therefore, the fraction of testing inputs that kNN or rNN certifiably correctly classifies is a lower bound of CA(e).. Formally, we have the following theorem:
Theorem 2 (Individual Certification). Assuming have a training dataset Dtr, testing dataset p and a nearest neighbor algorithm M (i.e., kNN or rNN). a; and b; respectively are the two labels with the largest and second largest number of votes among the nearest neighbors
DIC. = {xx, yc) Di>
4

---

Under review as a conference paper at ICLR 2021
(D xi) of in Dtr- Moreover, So; and Sb; the number of votes for a, and b, respectively. Then, we have the following lower bound of CA(e):
CA(e) E(x.9))EDr. T(; vi)
T(e ((ese)))
(4)
[Dtel
where of [ -b, +I(a)3b1) 1.
Proof. See Appendix A
3.2 JOINT CERTIFICATION
We derive better lower bound of the certified accuracy via jointly considering multiple testing examples. Our intuition is that, given group of testing examples and poisoning size an attacker may not be able to make learning algorithm misclassify all the testing examples jointly even if it can make the learning algorithm misclassify each of them individually. In particular, rNN enables such joint certification. It is challenging to perform joint certification for kNN because of the complex interactions between the nearest neighbors of different testing examples (see proof of Theorem for specific reasons). Next, we first derive lower bound of C'A(e) on a group of testing examples for rNN. Then, we derive lower bound of CA(e)) on the testing dataset Dte via dividing it into groups. Finally, we discuss different strategies to divide the testing dataset into groups, which may lead to different lower bounds of CA(e).
Deriving a lower bound of CA(e) for group of testing examples: Suppose we have a group of testing examples which have different predicted labels in rNN. Our key intuition is that when an attacker can poison e training examples, the attacker can only decrease the total votes for the testing examples' predicted labels by at most in rNN, the testing examples' predicted labels are different. We denote by lf a group of testing examples with different predicted labels and by m its size, i.e., m [2]. The next theorem shows lower bound of CA(e) on the testing examples in U for rNN.
Theorem 3. Assuming have a training dataset Dtr- the learning algorithm rNN, and a group of m testing examples l = {(x,, y with different predicted labels. at and by respectively are the two labels with the largest and second largest number of votes among the nearest neighbors (Drr x:) of x; in Dtr- Moreover, Sa, and Sb, are the number of votes for og and bú, respectively. Without loss of generality, we assume the following:
(sa, -.,-),,)- I[a1 = y1) 2 ($u, sb,) I[ay =y2)
sb..) I[am = vm).
(5)
Then, the certified accuracy at poisoning size of rNN for U has lower bound CA(e) > where is the solution the following optimization problem:
2-1
[2
m
W = arg min w' w/ 22221
S.L.
max(se. - Sb. - - I(a; > b.). I(a, = =y1)= S
(6)
Proof. When an attacker can poison at most training examples, the attacker can add at most e new nearest neighbors and remove e existing ones in (Drr,, 1rr,,x, x:) (equivalent to modifying training
examples) in the worst-case scenario. We denote by 85, and si respectively the number of votes for labels a; and b, among the nearest neighbors ND; x;). First, we have st S 8b; + e for Vi (1,2,.... m] since at most e new nearest neighbors are added. Second, we have s, 2 Sa, -4; in rNN, where is the number of removed nearest neighbors in (D(rr,, x;) whose true labels are a, Note that KNN does not support joint certification because s 2 Sa, E; does not hold for kNN.
Next, we derive the minimal value of e; such that rNN misclassifies x,, In particular, we consider two cases. If a, * yi, i.c., x; is misclassified by rNN without attack, then we have e, = 0. If a; = yt. x; is misclassified by rNN when st < st if a, < b; and st < $6 if a, b, after attack, which means
e; > Sa, Sb, + II(a, b.). Since e; > 0, we have e; max(sa; sh, + I(a; > 6;). 0). Combining the two cases, we have the following lower bound for e; that makes rNN misclassify remove at most e training examples and the group of testing examples have different predicted labels, i.c..
x; 2 max(sa, Sb. c + I(a: > b:). I(a, y1). Moreover, since the attacker
a # aj V (1,2, ,m) and * j, have Dme es S We note that the lower bound of
5

---

Under review as a conference paper at ICLR 2021
e, is non-increasing as i increases based on Equation (5). Therefore, in the worst-case scenario, the attacker can make rNN misclassify the last m w + testing inputs whose corresponding &, sum to be at most Formally, w is the solution to the optimization problem in Equation ( Therefore, the certified accuracy at poisoning size e is at least 10
[T
[
Deriving a lower bound of CA(e) for testing dataset: Based on Theorem 3 we can derive lower bound of C(e) for a testing dataset via dividing it into disjoint groups, each of which includes testing examples with different predicted labels in rNN, Formally, we have the following theorem:
Theorem 4 (Joint Certification). Given testing dataset Die. divide it into X disjoint groups. i.e., U1 U2, ... ,U,, where the testing examples in each group have different predicted labels in rNN. Then, we have the following lower bound of CA(e):
Σj=1 My U4
CA(e)= 2
Σ5=1 U,
where byy is the lower bound of the certified accuracy poisoning size group Uj. which we can obtain by invoking Theorem
Proof. See Appendix
B
Strategies of grouping testing examples: Our Theorem_iis applicable to any way of dividing the testing examples Die to disjoint groups once the testing examples each group have different predicted labels in rNN. Therefore, a natural question is how to group the testing examples in Dte to maximize our lower bound of certified accuracy. For instance, a naive method is to randomly divide the testing examples into disjoint groups, each of which includes at most (the number of classes) testing examples with different predicted labels. We call such method Random Division (RD). However, RD achieves suboptimal performance because it does not consider the certified robustness of each individual testing example. In particular, some testing examples can or cannot be certifiably correctly classified no matter which groups they belong to. However, if group them with other testing examples, the certified accuracy may be degraded because each group can have at most e testing examples. For instance, if testing example cannot be certifiably correctly classified no matter which group it belongs to, then adding it to a group would exclude another testing example from the group, which may degrade the certified accuracy for the group.
Therefore, we propose to isolate these testing examples and divide the remaining testing examples into disjoint groups. We call such method Isolation and Division (ISLAND). Specifically, we first divide the testing dataset Dic into three disjoint parts which we denote as Dic Die- and D Du contains the testing examples that cannot be certifiably correctly classified at poisoning size no matter which group they belong to. Based our proof of Theorem 3 testing example (x,, y:) that satisfies (sa, Sb. - e + I(a;; > b.)) I(a; = y4) I 0 cannot be certifiably correctly classified at poisoning size matter which group belongs to. Therefore, D% includes such testing examples.
testing example (xx, V:) that satisfies e S [ -9, +[(a,>b.) 1
Moreover, based on Theorem
can be certifiably correctly classified at poisoning size e. Therefore, D/c includes such testing examples. Each testing example in Dh or DJ, forms group by itself. D3 includes the remaining testing examples, which we further divide into groups. Our method of dividing D into groups inspired by the proof of Theorem 3 In particular, we form a group of testing examples as follows: for each label / E 21,
ej. we find the testing example that has the largest value of (sz, Sb. - + I(a, > b.)) I(a,- = t) and we skip the label there is no remaining testing example whose predicted label is l. We apply the procedure to recursively group the testing examples in Dj
until no testing examples are left.
4 EVALUATION
Datasets: We evaluate our methods on MNIST and CIFARIO. We use the popular histogram of oriented gradients (HOG)) Dalal & Triggs 2005) method to extract features for each example, which
Public implementation: htwp:///tttttteeeeoooodeeeeeeeee

---

Under review as a conference paper at ICLR 2021
DPA
DP1
Baggza
Hagdza
cortiaatee ESAND
sorti ELADO
190
(a) MNIST
(b) CIFARIO
(c) MNIST
(d) CIFARIO
Figure 2: (a)-(b comparing kNN and NNN with ofate-of-the-art methods. (c)-d) comparing
individual certification with joint certification for rNN.
Eed0
10:20
Palnaag far
Tranclip Sbx
(a) MNIST
(b) CIFARIO
(c) MNIST
(d) CIFARIO
Figure 3: Impact of k ((a)-b)) and r ((c)-d)) on the certified accuracy of KNN and rNN.
we found improves certified accuracy. Note that previous work (Jia et al. 2020) used a pre-trained model to extract features via transfer learning. However, the pre-trained model may also be poisoned and thus we don't 't use it. We didn't t find ties in determining nearest neighbors for kNN in our experiments. We rank the labels as 21, 10] to break ties for labels.
Parameter settings: While any distance metric is applicable, we use & in our experiments for both kNN and rNN. Unless otherwise mentioned, we adopt the following settings: k = 5, 000 for both MNIST and CIFARIO 10 in KNN; and r = 4 for MNIST and r = 20 for CIFARIO in rNN, considering the different feature dimensions of MNIST and CIFARIO. By default, we use the ISLAND grouping method in the joint certification for rNN.
Comparing with DPA (Levine& & Feizi 2020) and bagging (Jia et al., 2020 Figure 2a and
Figure 2b show the comparison results of DPA, bagging, kNN, and rNN. DPA divides training dataset into ( disjoint partitions and learns a base classifier on each of them. Then, DPA takes a majority vote among the base classifiers to predict the label of a testing example. Bagging learns N base classifiers, each of which is learnt on a random subsample with & training examples of the training dataset. Moreover, bagging's ' certified accuracy is correct with a confidence level 1 a. All the compared methods have tradeoffs between accuracy under no attacks (i.e.. C'A(O)) and robustness against attacks. Therefore, attacks (i.e., similar C())) In particular, we use the default ls for KNN, and we adjust r for rNN, ç for DPA, and E for bagging. The searched parameters are as follows: r 4, 5, 500, and & 27 for MNIST; and r = 21, Ç 900, and g
set their parameters such that they have similar accuracy under no
400 for CIFARIO. Note that we set N 1, 000 and 0.001 for bagging following (Jia et al. 2020
We have the following observations. First, both KNN and rNN outperform DPA and bagging. The superior performance of kNN and rNN stems from two reasons: 1) each poisoned training example corrupts multiple voters for DPA and bagging, while it only corrupts one voter for kNN and rNN, which means that, given the same gap between the largest and second largest number of votes, KNN and rNN can tolerate more poisoned training examples; and 2) rNN enables joint certification that improves the certified accuracy. Second, rNN achieves better certified accuracy than kNN when the poisoning size is large. The reason is that rNN supports joint certification.
Comparing individual certification with joint certification: Figure 2c and Figure 2d compare individual certification and joint certification (with the RD and ISLAND grouping methods) for rNN. Our empirical results validate that joint certification improves the certified accuracy upon individual certification. Moreover, our ISLAND grouping method outperforms the RD method.
Impact of l and r: Figure 3 shows the impact of k and r on the certified accuracy of kNN and rNN, respectively. As the results show, k and achieve tradeoffs between accuracy under no attacks (i.c., CA(O)) and robustness. Specifically, when or r is smaller, the accuracy under no attacks, i... C. CO), is larger, but the certified accuracy decreases more quickly as the poisoning size e increases.
7

---

Under review as a conference paper at ICLR 2021
5
RELATED WORK
Data poisoning attacks have been proposed against various learning algorithms such as Bayes classifier (Nelson et al., 2008). SVM (Biggio et al. 2012), clustering (Biggio et al. 2013b] (0144)
collaborative filtering (Li et al. 2016). regression models (Xiao et al. 2015a Mei & Zhu 2015b
Jagielski et al.) 2018), LDA (Mei & Zhu 2015a), neural networks (Muñoz- (Muñoz-González González et al.
2017
Shafahi et al. | /uciuu al. [0188] Demontis et al.) 2019 Zhu et al.
2019
Huang et al. 2020).
and others (Rubinstein et al. 2009 Vuurens et al. 2011).
To mitigate data poisoning attacks, many empirical defenses (Cretu et al. 2008 Rubinstein et al. 2009: Barreno et al., 2010 Biggio et al. 201T, Feng et al.) Jagiellkk et al.
2018 Tran et al.
2018) have been proposed. [Steinhardt et al. (2017) derived upper bound of the loss function for data
poisoning attacks when the model is learnt using examples in a feasible set. However, these defenses
lack certified robustness guarantees. Recently, several certified defenses (Ma al. 2019 Rosenfeld
iet al. 2020 Levine & Feizi 2020; Jia et al.) 2020) were proposed to defend against data poisoning
attacks. These defenses provide certified accuracies for a testing dataset either probabilistiially (Ma)
iet al. [219;; Jia et al., (200) or deterministically (Rosenfeld et al. [0200] Levine & Feizi| 2020). All
these defenses except (Ma et al. 2019) create majority vote mechanisms to predict the label of a
testing example. In particular, a voter is a base classifier learnt on perturbed version of the training
dataset in randomized smoothing based defenses (Rosenfeld et al. 2020). while a voter is a base
classifier learnt on subset of the trainig dataset in DPA (Levine & Feizi (020) and bagging (Jia) et al. 2020). Ma et al. (2019) showed that a differentially private learning algorithm achieves certified accuracy against data poisoning attacks. They also train multiple differentially private classifiers, but they are not used to predict the label of a testing example via majority vote. Instead, their average accuracy is used estimate the certified accuracy. kNN and rNN have intrinsic majority vote mechanisms and we show that they provide deterministic certified accuracies against data poisoning attacks. Moreover, rNN enables joint certification. We note that DPA (Levine & Feizi 2020) proposed to use hash function to assign training examples into partitions, which is different from our use of hash function. In particular, we use hash function rank training examples. Moreover, both DPA and our work rank the labels to break ties when comparing them with respect to their votes.
A line of works (Wilson 1972 Guyon et al. 1996 Peri et al./ 2019 Bahri et al., 2020) leveraged nearest neighbors to clean a training dataset. For instance, Wilson 1972) proposed to remove a training example whose label is not the same as the majority vote among the labels of its nearest neighbors. [Peri et al. (2019) proposed to remove training example whose label is not the mode amongst labels of its k nearest neighbors in the feature space. [Bahri et al. (2020) combined KNN with intermediate layer of a preliminary deep neural network model to filter suspiciously-labeled training examples. Another line of works (Gao et al. 2018 Reeve & Kabán 2019) studied the resistance of nearest neighbors random noisy labels. For instance, Gao et al. (2018) analyzed the resistance of kNN to asymmetric label noise and introduced a Robust KNN to deal with noisy labels. |Reeve& & Kabán (2019) further analyzed the Robust kNN proposed by (Gao al., 2018) in the setting with unknown asymmetric label noise. kNN and its variants have also been used to defend against adversarial examples (Wang et al.) 2018 Sitawarin & Wagner 201 Papernot & McDaniel 2018; Sitawarin & Wagner 2019b Dubey et al. 2019] Yang et al. 2020 Cohen et al. 2020). For instance, Wang et al. (2018) analyzed the robustness of nearest neighbors to adversarial examples and
proposed a more robust --narrest neighbor. Several works (Amsaleg et al.) [017]] Wang et al. 2018
2019; Yang et al.) 2020) proposed adversarial examples to nearest neighbors, e.g., Wang et al. (019
proposed adversarial examples against l-nearest neighbor. These works are orthogonal to ours we focus on analyzing the certified robustness of kNN and rNN against general data poisoning attacks.
6 CONCLUSION AND FUTURE WORK
In this work, we derive the certified robustness of nearest neighbor algorithms, including kNN and rNN, against data poisoning attacks. Moreover, we derive a better lower bound of certified accuracy for rNN via jointly certifying multiple testing examples. Our evaluation results show that 1) both kNN and rNN outperform state-of-the-an of-the-art certified defenses against data poisoning attacks, and 2) joint certification outperforms individual certification. Interesting future work includes 1) extending joint certification to other learning algorithms, 2) improving joint certification via new grouping methods, and 3) improving certified accuracy of kNN and rNN via new distance metrics.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Laurent Amsaleg, James Bailey, Dominique Barbe, Sarah Erfani, Michael E Houle, Vinh Nguyen, and Miloš Radovanović. The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality. In 2017 IEEE Workshop on Information Forensics and Security (WIFS), pp. 1-6. IEEE, 2017.
Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. ICML, 2020.
Marco Barreno, Blaine Nelson, Russell Sears, Anthony D Joseph, and Doug Tygar. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pp. 16-25, 2006.
Marco Barreno, Blaine Nelson, Anthony D Joseph, and J Doug Tygar. The security of machine learning. Machine Learning. 81 81(2):121-14, 2010.
Battista Biggio, Igino Corona, Giorgio Fumera, Giorgio Giacinto, and Fabio Roli. Bagging classifiers for fighting poisoning attacks in adversarial classification tasks. In International workshop on multiple classifier systems, pp. 350-359. Springer, 2011.
Battista Biggio, B Nelson, and P Laskov. Poisoning attacks against support vector machines. In ICML, pp. 1807-1814, 2012.
Battista Biggio, Giorgio Fumera, and Fabio Roli. Security evaluation of pattern classifiers under attack. IEEE transactions on knowledge and data engineering, (6(4):984-990) 2013a.
Battista Biggio, Ignazio Pillai, Samuel Rota Bulò, Davide Ariu, Marcello Pelillo, and Fabio Roli. Is data clustering in adversarial settings secure? In Proceedings of the 2013 ACM workshop on Artificial intelligence and security, pp. 87-98, 2013b.
Battista Biggio, Konrad Rieck, Davide Ariu, Christian Wressnegger, Igino Corona, Giorgio Giacinto, and Fabio Roli. Poisoning behavioral malware clustering. In Proceedings of the 2014 workshop on artificial intelligent and security workshop, pp. 27-36, 2014.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE S&P, pp. 39-57. IEEE, 2017.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv: 2017.
Gilad Cohen, Guillermo Sapiro, and Raja Giryes. Detecting adversarial samples using influence functions and nearest neighbors. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14453-14462, 2020.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1):21-27, 1967.
Gabriela F Cretu, Angelos Stavrou, Michael E Locasto, Salvatore Stolfo, and Angelos D Keromytis. Casting out demons: Sanitizing training data for anomaly sensors. In 2008 IEEE Symposium Security and Privacy, pp. 81-95. IEEE, 2008.
Navneet Dalal and Bill Triggs. Histograms oriented gradients for human detection. In 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR'05) volume 1, pp. 886-893. IEEE, 2005.
Ambra Demontis, Marco Melis, Maura Pintor, Matthew Jagielski, Battista Biggio, Alina Oprea, Cristina Nita-Rotaru and Fabio Roli. Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks. In USENIX Security Symposium, pp. 321-338, 2019.
Abhimanyu Dubey, Laurens van der Maaten, Zeki Yalniz, Yixuan Li, and Dhruv Mahajan. Defense against adversarial images using web-scale nearest-neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8767-8776, 2019.
Jiashi Feng, Huan Xu, Shie Mannor, and Shuicheng Yan. Robust logistic regression and classification. In Advances in neural information processing systems, pp. 253-261, 2014.

---

Under review as a conference paper at ICLR 2021
Evelyn Fix and JL Hodges. Discriminatory analysis: Nonparametric discrimination, consistency properties. Report No. 4, USAF School of Aviation Medicine, Randolph Field, Texas, Feb, 1951.
Wei Gao, Xin-Yi Niu, and Zhi-Hua Zhou. On the consistency of exact and approximate nearest neighbor with noisy data. Arxiv, abv/1607.07526, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 1xXi::411.66772 2014.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv:1708.0000 2017.
Isabelle Guyon, Nada Matic, Vladimir Vapnik, et al. Discovering informative patterns and data cleaning. In Proceedings of the 3rd International Conference Knowledge Discovery and Data Mining, 1996.
W Ronny Huang. Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. Metapoison: Practical general-purpose clean-label data poisoning. arXiv preprint arXiv:2004.00222 2020.
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 19-35. IEEE, 2018.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. arXiv preprint arXiv:2008.04449) 2020.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks. arXiv preprint arXiv:2006. 14768, 2020.
Bo Li. Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. Data poisoning attacks factorization- based collaborative filtering. In NeurlPS, pp. 1885-1893, 2016.
Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially- priviat learners: Attacks and defenses. In International Joint Conference on Artificial Intelligence, 2019.
Shike Mei and Xiaojin Zhu. The security of latent dirichlet allocation. In Artificial Intelligence and Statistics, pp. 681-689, 2015a.
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. In AAAI, pp. 2871-2877, 201
Mehran Mozaffari- Mozaffari-Kermani, Susmita Sur- Sur-Kolay Kolay, Anand Raghunathan, and Niraj K Jha. Systematic poisoning attacks and defenses for machine learning in healtheare. IEEE journal of biomedical and health informatics, (96):1893-1905 2014.
Luis Muñoz-González, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli. Towards poisoning deep learning algorithms with back- mack-gradient optimization. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 27-38, 2017.
Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles Sutton, J Doug Tygar, and Kai Xia. Exploiting machine learning to subvert your spam filter. LEET, 8:1-9, 2008.
Nicolas Papernot and Patrick McDaniel. Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint arXiv: 1803 04765, 2018 8.
Neehar Peri, Neal Gupta, W Ronny Huang, Liam Fowl, Chen Zhu, Soheil Feizi, Tom Goldstein, and John P Dickerson. Deep k-nn defense against clean-label data poisoning attacks. arXiv, pp. 1909 2019.
Henry WJ Reeve and Ata Kabán. Fast rates for a knn classifier robust to unknown asymmetric label noise. arXiv preprint arXiv: (we.11906644444 2019.
10

---

Under review as a conference paper at ICLR 2021
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J Zico Kolter. Certified robustness to label-flipping attacks via randomized smoothing. In ICML, 2020.
Benjamin IP Rubinstein, Blaine Nelson, Ling Huang, Anthony D Joseph, Shing-hon Lau, Satish Rao, Nina Taft, and J Doug Tygar. Antidote: understanding and defending against poisoning of anomaly detectors. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement, pp- 1-14, 2009.
Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks neural networks. In NeurlPS, pp. 6103-6113, 2018.
Chawin Sitawarin and David Wagner. Defending against adversarial examples with k-nearest neighbor. arXiv preprint arXiv:1906.0995 09525, 2019a.
Chawin Sitawarin and David Wagner. On the robustness of deep k-nearest neighbors. In 2019 IEEE Security and Privacy Workshops (SPW), pp. 1-7. IEEE, 2019b.
Jacob Steinhardt, Pang Wei Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In Advances neural information processing systems, pp. 35 3517-3529, 2017.
Octavian Suciu, Radu Marginean, Yigitcan Kaya, Hal Daume III, and Tudor Dumitras. When does machine learning FAIL? generalized transferability for evasion and poisoning attacks. In USENIX Security Symposium, pp. 1299-1316, 2018
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems, pp. 4000-8010, 2018.
Jeroen Vuurens, Arjen P de Vries, and Carsten Eickhoff. How much spam can you take? an analysis of crowdsourcing results to increase accuracy. In Proc. ACM SIGIR Workshop on Crowdsourcing for Information Retrieval (CIR') (1), pp. 21-26, 2011.
Lu Wang, Xuanqing Liu, Jinfeng Yi, Zhi-Hua Zhou, and Cho-Jui Hsieh. Evaluating the robustness of nearest neighbor classifiers: primal-dual perspective. arXiv preprint arX6v:1906. 03972, 2019.
Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighhors to adversarial examples. In International Conference on Machine Learning, pp. 5133-5142, 2018.
Dennis L Wilson. Asymptotic properties of nearest neighbor rules using edited data. IEEE Transac- fions on Systems, Man, and Cybernetics, (3):408-421, 1972.
Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is feature selection secure against training data poisoning? In /CML, pp. 1689-1698, 2015a.
Huang Xiao, Battista Biggio, Blaine Nelson, Han Xiao, Claudia Eckert, and Fabio Roli, Support vector machines under adversarial label contamination. Neurocomputing, 160:53 62, 2015b.
Yuo-Yuan Yang, Cyrus Rashtchian, Yizhen Wang, and Kamalika Chaudhuri. Robustness for non- parametric classification: A generic attack and defense. In International Conference Artificial Intelligence and Statistics, pp. 941-951, 2020.
Chen Zhu, Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks on deep neural nets. In ICML, pp. 7614-7623, 2019.
11

---

Under review as a conference paper at ICLR 2021
A PROOF OF THEOREM 2
Proof. We have the following:
Eix.deDD. I(M(D x;)= = y²)
CA(c)
min D (SD
|Deel
2 (X..)ED.. (.S(,.)) L(M(Di,, (MM x;) = 1/)
(9)
Deel
EXx.nED, I(a; = 41) minpp, I(M a:)
(10)
Deel
ExX.nEDD [aa y4 [[e S et)
(11)
DDel
where the last step is based on applying Theorem to testing input x,,
B PROOF OF THEOREM 4
Proof. We have the following:
EI.,DED.. I(M(D,, x,) = y1))
CA(e)=
min (i,ES(D
(12)
10ee
E E(x,n)E I(M x,) = =b)
min (i.tt()
(13)
1 min ES(D.)) Σ E(x.wee I(M(( = 9)
(14)
Σラ=1 Ub
1= Hy 14g1
(15)
ΣE= [4
where we have Equation [5) from (4) based on applying Theorem group Uy.
12


Reviews:
[{"review_id": "l9EXtJhbJYF", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The paper studies robustness of k-NN and r-NN against data poisoning attacks. The main message of the paper is that k-NN and r-NN are automatically resilient against attacks. Furthermore, by grouping test examples based their predicted labels. Data points with different predictions are grouped together, and then better certification guarantee can be derived. Experimental results demonstrate that k-NN and r-NN are indeed self-robust against data poisoning attacks.\n\nThe theoretical angle proposed in this paper is interesting. However, I have a high-level question regarding the paper. Is the goal of the paper simply providing theoretical robustness guarantee of k-NN? I do not see any new defense mechanisms developed in this paper. The grouping idea is only intended to prove the theoretical results. If so, I feel like contribution of the paper is not significant enough. Besides that, how does the result in this paper compare to the following one? I hope the authors could clarify the concern.\nAnalyzing the robustness of nearest neighbors to adversarial examples\n\nSecondly, I think definition (1) is not explained well. Does modification, addition and deletion counts equally as a single operation? The authors seem to point toward that modification is equivalent to one-time addition plus on-time deletion. This makes me wondering if modification counts as two operations? Furthermore, does the training data allow repetitions of any data point? For example, if the attacker simply adds the same point that exists in the clean training data multiple times? Does that count as poisoning? In definition (1), the dataset is considered a set, thus repetitions will be absorbed as a single item, which leads to D*=D. However, repetitions definitely matter for k-NN, and could be potentially exploited by the attacker. Therefore, I hope the authors could provide a more clear definition of the defining poisoning size.\n\nIn the beginning of section 3.1, a data point is certifiably correct only when the predicted label stays unchanged before and after attack, and it matches the true label. I am wondering does this requirement rule out the test examples that are originally misclassified? There are indeed cases where due to the attack, some test examples become correctly classified, while originally they are not. In this case, I am not sure how to interpret the robustness because the attacker is conversely helping the k-NN. This makes wonder if certification is a correct way to define robustness. Throughout the paper, there is no discussion regarding the ground-truth underlying data distribution, which I think is important for the definition of robustness. Ideally, a robust classifier should maintain high accuracy over the underlying data distribution even with attack. There is little reason to care too much about the certification for a particular data point, since that point appears with probability 0. I wonder if the authors can discuss this point.\n\nThe theoretical results in this paper are very interesting, but it lacks a nice and intuitive explanation before the proof. For example, why grouping can give us a better certification rate? What is the intuition behind that? The explanation is not given enough space in this paper. I only see a few sentences before Theorem 3, and that does not support my understanding a lot. In Figure 1, I sort of see why multiple data points cannot be jointly certified. In my understanding, it is because the point 0 and 2 are somewhat far from each other, thus the attacker cannot place enough poisoning points within the overlapping neighborhood of the two points such that their labels are changed simultaneously. However, if they are close enough, then the attacker can modify some neighbors of point 2 while adding new points to the overlapping area, which leads to a successful attack. Therefore, it is not easy to distill the distinction between individual certification and joint certification from this example. This example also does not help understanding of later theorems. I am wondering if the authors could design a more informative example?\n\nIn the experiments, I think it will be helpful to also draw the theoretical lower bound for the individual and joint certification, so that readers can see whether the analysis is tight or not. Apart from that, what is the data poisoning attack algorithm used to evaluate the robustness?\n\nOverall, I believe the paper is not written clearly, and there is a huge space for improvement.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fN-3VkcNXZh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "The paper studies the robustness of kNN and rNN to poisoning attacks. They try to achieve certified bounds on the robustness of rNN and kNN algorithms, against poisoning attacks. They claim to achieve certified upper bounds on the effect of poisoning attacks on overall accuracy. The techniques used are very simple. Their first theorem which is about the robustness of individual test examples states that if the number of poison points are smaller than half the distance between the number of neighbors with label that has highest vote and the number neighbors with label that has second highest vote, then poisoning is not effective. Then they try to extend this result to overall accuracy of scheme. Their Theorem 3 tries to achieve such a bound but I think this theorem is not correct (I mentioned the issue with this Theorem in the comments bellow). Then they have some experiments that uses this Theorem to achieve certified bounds for the case of  MNIST and CIFAR10.\n\nTheir experimental results show that they can achieve better certified bounds compared to some previous certified defense papers. But their results are extremely dependent on the correctness of Theorem 3 and it is necessary for authors to rewrite the proof and theorem itself.  \n\nEven if the authors fix their theorem, I still don't find the theoretical contribution of this paper significant. But their experiments and certified bounds could be interesting enough for paper to be accepted. \n\n\nComments to Authors:\n\n- I think there is a problem in the  proof of Theorem 3. It is mentioned that a_i's are different. But b_is are not necessarily different and they could all be the same label. Then the attacker can potentially flip all of them to b_i.\n\n-In page 4, it is mentioned that for breaking the ties in kNN we can use ranking of training examples. How would that exactly work?\n\n-The claim on being the first certified poisoning defense on overall accuracy is not correct. The work of Steinhardt et al (2017) also studies provable defenses for overall accuracy. It is crucial for this paper to compare their result with Steinhart et al (2017). \n\npage 1: worse-case -> worst-case\npage 2: \n\npage 3: The formal definition o S(D_tr,e) is inconsistent with what is described in text.\n\nPage 4: The notation is not very clear. s_l is the number of votes for class l and for instance x. It is better to use something like s_l(x). Similarly, a_i and b_i are better to be a_i(x) and b_i(x).\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "UK6HHtyxGdc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "Existence of much stronger results:\nI don't get why majority voting is claimed to be the \"state-of-the-art\" technique. If I'm understanding it correctly, the majority vote technique can only handle a number of corruption points up to O(K), K being the number of voters. Furthermore, since the voters more or less split the dataset, in order to maintain the accuracy of each voter, the number of voters can't be too large, and is usually O(1). Therefore, this majority vote approach can only handle O(1) number of corruption. \n\nMore specifically, for the case of kNN, the certified accuracy (Theorem 2, ) becomes vacuous as soon as the number of corrupted points $e$ becomes greater than $k$.\n\nOn the other hand, there are techniques developed from the robust statistics community that can be robust against an $\\epsilon$-fraction of corruption points, that is, if there are a total of $N$ training points, it allows $\\epsilon N$ number of points to be corrupted. For example, Sever [1], a recently developed robust supervised learning algorithm, guarantees $O(\\sqrt{\\epsilon})$ generalization error under $\\epsilon$-fraction of arbitrary corruption. Such a guarantee is much stronger than the ones majority voting approaches are able to achieve. \n\nThus, I'm having trouble appreciating the contribution of this paper given the existence of much stronger results.\n\nRelevance to the field:\nWhile prior approaches like DPA also suffers from the same weak/trivial guarantee, they are at least meta-algorithms that allows one to plug in any base learners depending on the application. The method developed in this paper, however, only works on kNN. And let's be honest, not many modern ML applications use kNN with the slightest chance. So I don't see much empirical value nor any significant theoretical contribution. \n\n[1] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart. Sever: A Robust Meta-Algorithm for Stochastic Optimization. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MlWoMfTIJg8", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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:**\nFirst, the paper identifies k-Nearest Neighbor (kNN) and radius Nearest Neighbor (rNN) to be naturally effective baseline certified defenses against data poisoning attack. It is easy to see that kNN and rNN are resistant to poison attacks, since to flip the prediction of a test example, one would need to insert/delete enough examples to change the majority vote. Second, the paper proposes a joint certificate that further improves certified accuracy for rNN. Specifically, it uses the fact that for any given poison removal budget, it can only decrease the vote for a single label. Even though the idea is simple, the experimental result is quite impressive significantly outperforming the previous more sophisticated certified defense methods.\n\n**Strength:**\n- The approach is easy to implement and understand\n- Despite its simplicity, the approach performs significantly better compared to previous methods. This should be the new standard baseline for all certified poisoned defense papers.\n\n**Weakness:**\n- The technical novelty is not very strong, since it is obvious that kNN is naturally robust to poisoning. The proposed joint certification helps compensate for the technical deficiencies. However, I expect more ways to improve this lower bound than what is presented here. For example, another natural way to improve the joint certification is to consider how the added poison cannot influence two test examples concurrently when they are far enough apart. \n- Even though joint certification can improve certified accuracy, in practice, individual certification may be more important compared to joint certification, since users of the system probably want certifications as individual queries come in.\n- Since kNN/rNN are not used as frequently in practical settings, the proposed solution may not be as useful to systems that require the use of neural networks. However, I am also aware that none of the existing defenses work well enough for any practical setting.\n\n\n**Recommendation**\nEven though the technical novelty is limited, I recommend acceptance due to the simplicity of the approach and its impressive performance compared to previous methods. I think this paper will become a new standard baseline for future certified poisoned defense papers. \n\n**Update**\nAfter reading reviewer2's comment, I realize that there is literature proving much stronger results that I was unaware of. I still think these results should be used as a standard baseline for certified poisoning defense, but due to the lack of novelty, I have to downgrade my score. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BeP6Z_DBeL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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 studies to train a certifiable robust model against data poisoning attacks using nearest neighbors. The paper studies the voting mechanism in the nearest neighbor models, and presents a relationship between the poisoning instances and the difference between the majority votes and the second majority votes. Such a relationship will result in a guarantee on the lower bound of a training model's accuracy, which is referred to as Certified Accuracy (CA). The theoretical results are neat. The experiments are conducted on MNIST and CIFAR, and results show better CA than previous approaches of DPA and Bagging.\n\nMy main concern is the limitation of the applicable machine learning models, which seems restricted to only kNN and rNN models --- they may not yield the best performance on most interesting tasks. For example, from Fig 2 and 3, we can see that even when poisoning size e=0, the accuracy (which should be identical to CA) is far below the SOTA on the corresponding MNIST and CIFAR tasks.\n\nAlso, the lower bound is established with respect to s_a - s_b - e <= k-e. Therefore, to be able to handle larger poisoning size e, one has to employ a larger k (in the kNN case) or larger r (in the rNN case). Such choices of hyperparameter typically hinder the accuracy on the clean dataset. It is not clear how such a restriction can be mitigated in a practical setup.\n\nDue to the above concern, I'm borderline on work.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Some reviewers expressed concerns on soundness of the theory in the paper. Specifically, theorem 3 does not seem to be correct.  There are other concerns such as the significance of the theoretical contributions, little empirical value and existence of much stronger results. Unfortunately the authors did not provide responses to the concerns raised by the reviewers. 


Decision: Reject