summaries: First, 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. 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. 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.
abstractText: 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 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.
references.authors: Laurent Amsaleg James Bailey Dominique Barbe Sarah Erfani Michael E Houle Vinh Nguyen Miloš Radovanović
references.title: The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality
references.venue: IEEE Workshop on Information Forensics and Security (WIFS),
references.authors: Dara Bahri Heinrich Jiang Maya Gupta
references.title: Deep k-nn for noisy labels
references.venue: In ICML,
references.authors: Marco Barreno Blaine Nelson Russell Sears Anthony D Joseph J Doug Tygar
references.title: Can machine learning be secure
references.venue: In Proceedings of the 2006 ACM Symposium on Information, computer and communications security,
references.authors: Marco Barreno Blaine Nelson Anthony D Joseph J Doug Tygar
references.title: The security of machine learning
references.venue: Machine Learning,
references.authors: Battista Biggio Igino Corona Giorgio Fumera Giorgio Giacinto Fabio Roli
references.title: Bagging classifiers for fighting poisoning attacks in adversarial classification tasks
references.venue: In International workshop on multiple classifier systems,
references.authors: Battista Biggio B Nelson P Laskov
references.title: Poisoning attacks against support vector machines
references.venue: In ICML, pp
references.authors: Battista Biggio Giorgio Fumera Fabio Roli
references.title: Security evaluation of pattern classifiers under attack
references.venue: IEEE transactions on knowledge and data engineering,
references.authors: Battista Biggio Ignazio Pillai Samuel Rota Bulò Davide Ariu Marcello Pelillo Fabio Roli
references.title: Is data clustering in adversarial settings secure
references.venue: In Proceedings of the 2013 ACM workshop on Artificial intelligence and security,
references.authors: Battista Biggio Konrad Rieck Davide Ariu Christian Wressnegger Igino Corona Giorgio Giacinto Fabio Roli
references.title: Poisoning behavioral malware clustering
references.venue: In Proceedings of the 2014 workshop on artificial intelligent and security workshop,
references.authors: Nicholas Carlini David Wagner
references.title: Towards evaluating the robustness of neural networks
references.venue: In IEEE S&P,
references.authors: Xinyun Chen Chang Liu Bo Li Kimberly Lu Dawn Song
references.title: Targeted backdoor attacks on deep learning systems using data poisoning
references.venue: arXiv preprint arXiv:1712.05526,
references.authors: Gilad Cohen Guillermo Sapiro Raja Giryes
references.title: Detecting adversarial samples using influence functions and nearest neighbors
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Thomas Cover Peter Hart
references.title: Nearest neighbor pattern classification
references.venue: IEEE transactions on information theory,
references.authors: Gabriela F Cretu Angelos Stavrou Michael E Locasto Salvatore J Stolfo Angelos D Keromytis
references.title: Casting out demons: Sanitizing training data for anomaly sensors
references.venue: IEEE Symposium on Security and Privacy,
references.authors: Navneet Dalal Bill Triggs
references.title: Histograms of oriented gradients for human detection
references.venue: IEEE computer society conference on computer vision and pattern recognition (CVPR’05),
references.authors: Ambra Demontis Marco Melis Maura Pintor Matthew Jagielski Battista Biggio Alina Oprea Cristina Nita-Rotaru Fabio Roli
references.title: Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks
references.venue: In USENIX Security Symposium,
references.authors: Abhimanyu Dubey Laurens van der Maaten Zeki Yalniz Yixuan Li Dhruv Mahajan
references.title: Defense against adversarial images using web-scale nearest-neighbor search
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Jiashi Feng Huan Xu Shie Mannor Shuicheng Yan
references.title: Robust logistic regression and classification
references.venue: In Advances in neural information processing systems,
references.authors: Evelyn Fix JL Hodges
references.title: Discriminatory analysis: Nonparametric discrimination, consistency properties
references.venue: Report No. 4, USAF School of Aviation
references.authors: Wei Gao Xin-Yi Niu Zhi-Hua Zhou
references.title: On the consistency of exact and approximate nearest neighbor with noisy data
references.authors: Ian J Goodfellow Jonathon Shlens Christian Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: arXiv preprint arXiv:1412.6572,
references.authors: Tianyu Gu Brendan Dolan-Gavitt Siddharth Garg
references.title: Badnets: Identifying vulnerabilities in the machine learning model supply chain
references.venue: arXiv preprint arXiv:1708.06733,
references.authors: Isabelle Guyon Nada Matic Vladimir Vapnik
references.title: Discovering informative patterns and data cleaning
references.venue: In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining,
references.authors: W Ronny Huang Jonas Geiping Liam Fowl Gavin Taylor Tom Goldstein
references.title: Metapoison: Practical general-purpose clean-label data poisoning
references.venue: arXiv preprint arXiv:2004.00225,
references.authors: Matthew Jagielski Alina Oprea Battista Biggio Chang Liu Cristina Nita-Rotaru Bo Li
references.title: Manipulating machine learning: Poisoning attacks and countermeasures for regression learning
references.venue: IEEE Symposium on Security and Privacy (SP),
references.authors: Jinyuan Jia Xiaoyu Cao Neil Zhenqiang Gong
references.title: Intrinsic certified robustness of bagging against data poisoning attacks
references.venue: arXiv preprint arXiv:2008.04495,
references.authors: Alexander Levine Soheil Feizi
references.title: Deep partition aggregation: Provable defense against general poisoning
references.venue: attacks. arXiv preprint arXiv:2006.14768,
references.authors: Bo Li Yining Wang Aarti Singh Yevgeniy Vorobeychik
references.title: Data poisoning attacks on factorizationbased collaborative filtering
references.venue: In NeurIPS,
references.authors: Yuzhe Ma Xiaojin Zhu Justin Hsu
references.title: Data poisoning against differentially-private learners: Attacks and defenses
references.venue: In International Joint Conference on Artificial Intelligence,
references.authors: Shike Mei Xiaojin Zhu
references.title: The security of latent dirichlet allocation
references.venue: In Artificial Intelligence and Statistics,
references.authors: Shike Mei Xiaojin Zhu
references.title: Using machine teaching to identify optimal training-set attacks on machine learners
references.venue: In AAAI,
references.authors: Mehran Mozaffari-Kermani Susmita Sur-Kolay Anand Raghunathan Niraj K Jha
references.title: Systematic poisoning attacks on and defenses for machine learning in healthcare
references.venue: IEEE journal of biomedical and health informatics,
references.authors: Luis Muñoz-González Battista Biggio Ambra Demontis Andrea Paudice Vasin Wongrassamee Emil C Lupu Fabio Roli
references.title: Towards poisoning of deep learning algorithms with back-gradient optimization
references.venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security,
references.authors: Blaine Nelson Marco Barreno Fuching Jack Chi Anthony D Joseph Benjamin IP Rubinstein Udam Saini Charles A Sutton J Doug Tygar Kai Xia
references.title: Exploiting machine learning to subvert your spam
references.venue: filter. LEET,
references.authors: Nicolas Papernot Patrick McDaniel
references.title: Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning
references.venue: arXiv preprint arXiv:1803.04765,
references.authors: Neehar Peri Neal Gupta W Ronny Huang Liam Fowl Chen Zhu Soheil Feizi Tom Goldstein John P Dickerson
references.title: Deep k-nn defense against clean-label data poisoning
references.authors: Henry WJ Reeve Ata Kabán
references.title: Fast rates for a knn classifier robust to unknown asymmetric label noise
references.authors: Elan Rosenfeld Ezra Winston Pradeep Ravikumar J Zico Kolter
references.title: Certified robustness to label-flipping attacks via randomized smoothing
references.venue: In ICML,
references.authors: Benjamin IP Rubinstein Blaine Nelson Ling Huang Anthony D Joseph Shing-hon Lau Satish Rao Nina Taft J Doug Tygar
references.title: Antidote: understanding and defending against poisoning of anomaly detectors
references.venue: In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement,
references.authors: Ali Shafahi W Ronny Huang Mahyar Najibi Octavian Suciu Christoph Studer Tudor Dumitras Tom Goldstein
references.title: Poison frogs! targeted clean-label poisoning attacks on neural networks
references.venue: In NeurIPS,
references.authors: Chawin Sitawarin David Wagner
references.title: Defending against adversarial examples with k-nearest neighbor
references.venue: arXiv preprint arXiv:1906.09525,
references.authors: Chawin Sitawarin David Wagner
references.title: On the robustness of deep k-nearest neighbors
references.venue: IEEE Security and Privacy Workshops (SPW),
references.authors: Jacob Steinhardt Pang Wei W Koh Percy S Liang
references.title: Certified defenses for data poisoning attacks
references.venue: In Advances in neural information processing systems,
references.authors: Octavian Suciu Radu Marginean Yigitcan Kaya Hal Daume III Tudor Dumitras
references.title: When does machine learning FAIL? generalized transferability for evasion and poisoning attacks
references.venue: In USENIX Security Symposium,
references.authors: Christian Szegedy Wojciech Zaremba Ilya Sutskever Joan Bruna Dumitru Erhan Ian Goodfellow Rob Fergus
references.title: Intriguing properties of neural networks
references.venue: In ICLR,
references.authors: Brandon Tran Jerry Li Aleksander Madry
references.title: Spectral signatures in backdoor attacks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Jeroen Vuurens Arjen P de Vries Carsten Eickhoff
references.title: How much spam can you take? an analysis of crowdsourcing results to increase accuracy
references.venue: In Proc. ACM SIGIR Workshop on Crowdsourcing for Information Retrieval
references.authors: Lu Wang Xuanqing Liu Jinfeng Yi Zhi-Hua Zhou Cho-Jui Hsieh
references.title: Evaluating the robustness of nearest neighbor classifiers: A primal-dual perspective
references.authors: Yizhen Wang Somesh Jha Kamalika Chaudhuri
references.title: Analyzing the robustness of nearest neighbors to adversarial examples
references.venue: In International Conference on Machine Learning,
references.authors: Dennis L Wilson
references.title: Asymptotic properties of nearest neighbor rules using edited data
references.venue: IEEE Transactions on Systems, Man, and Cybernetics,
references.authors: Huang Xiao Battista Biggio Gavin Brown Giorgio Fumera Claudia Eckert Fabio Roli
references.title: Is feature selection secure against training data poisoning
references.venue: In ICML,
references.authors: Huang Xiao Battista Biggio Blaine Nelson Han Xiao Claudia Eckert Fabio Roli
references.title: Support vector machines under adversarial label contamination
references.authors: Yao-Yuan Yang Cyrus Rashtchian Yizhen Wang Kamalika Chaudhuri
references.title: Robustness for nonparametric classification: A generic attack and defense
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Chen Zhu W Ronny Huang Hengduo Li Gavin Taylor Christoph Studer Tom Goldstein
references.title: Transferable clean-label poisoning attacks on deep neural nets
references.venue: In ICML,
sections.heading: 1 INTRODUCTION
sections.text: 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 et al., 2018) aim to corrupt the training phase of a 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 as autonomous driving (Gu et al., 2017), cybersecurity (Rubinstein et al., 2009; Suciu et al., 2018; Chen et al., 2017), and healthcare analytics (Mozaffari-Kermani et al., 2014). Unlike adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2014; Carlini & Wagner, 2017), which add perturbation to each testing example to induce misclassification, data poisoning attacks corrupt the model such that it misclassifies many clean testing examples.
  Multiple certifiably robust learning algorithms (Ma et al., 2019; Rosenfeld et al., 2020; Levine & Feizi, 2020; Jia et al., 2020) against data poisoning attacks were recently developed. A 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 no more than a threshold (called poisoning size). The certified accuracy of a learning algorithm is a lower bound of the accuracy of its learnt classifier no matter how an attacker poisons the training examples with the given poisoning size. The key idea of state-of-the-art certifiably robust learning algorithms (Levine & Feizi, 2020; Jia et al., 2020) is to create a majority vote mechanism to predict the label of a testing example. In particular, each voter votes a 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., 2020) also learns multiple base classifiers (i.e., voters), but each of them is learnt on a 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 sb respectively are the number of votes for labels a and b 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 d sa−sb2 e − 1. In other words, the number of corrupted voters that a majority vote mechanism can tolerate depends on the gap sa − sb between the largest and the second largest number of votes.
  However, state-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 a 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 a small number of poisoned training examples. Second, they can 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 a learning algorithm can correctly classify testing inputs x1 and x2. An attacker can poison e training examples such that the learnt classifier misclassifies x1 or x2, but the attacker cannot poison e training examples such that both x1 and x2 are misclassified. When the poisoning size is e, existing certifiably robust learning algorithms would produce a certified accuracy of 0 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; Cover & Hart, 1967) have intrinsic majority vote mechanisms. Specifically, given a testing example, kNN (or rNN) predicts its label via taking a majority vote among the labels of its k 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 state-of-the-art 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, we show that rNN enables joint certification of multiple testing examples. Figure 1 illustrates 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 3 training examples to misclassify both of them. We propose such joint certification to derive a 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.
  We evaluate our methods on MNIST and CIFAR10 datasets. We use `1 distance metric to calculate nearest neighbors. First, our methods substantially outperform state-of-the-art certifiably robust learning algorithms. For instance, when an attacker can arbitrarily poison 1,000 training examples on MNIST, the certified accuracy of rNN with r = 4 is 40.8% and 33.5% higher than those of DPA (Levine & Feizi, 2020) 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:
  • We derive the intrinsic certified robustness guarantees of kNN and rNN against data poisoning 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 state-of-the-art on MNIST and CIFAR10.
sections.heading: 2 PROBLEM SETUP
sections.text: Learning setting: Assuming we have a training dataset Dtr with n training examples. We denote by M a learning algorithm. Moreover, we denote byM(Dtr,x) the label predicted for a testing input x by a classifier learnt byM on the training dataset Dtr. For instance, given a training dataset Dtr and a testing input x, kNN finds the k training examples in Dtr that are the closest to x as the nearest neighbors, while rNN finds the training examples in Dtr whose distances to x are no larger than r as 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 of 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.
  Data poisoning attacks: We consider data poisoning attacks (Rubinstein et al., 2009; Biggio et al., 2012; Xiao et al., 2015a; Li et al., 2016; Muñoz-González et al., 2017; Jagielski et al., 2018) that aim to poison (i.e., modify, add, and/or remove) some carefully selected training examples in Dtr such that the corrupted classifier has a low accuracy for testing examples indiscriminately. For simplicity, we use D∗tr to denote the poisoned training dataset. Moreover, we define the poisoning size e as the minimal number of modified/added/removed training examples that can turn Dtr into D∗tr. We use S(Dtr, e) to denote the set of poisoned training datasets whose poisoning sizes are at most e. Formally, we define S(Dtr, e) as follows:
  S(Dtr, e) = {D∗tr|max{|D∗tr|, |Dtr|} − |D∗tr ∩Dtr| ≤ e}, (1)
  where max{|D∗tr|, |Dtr|} − |D∗tr ∩Dtr| is the poisoning size of D∗tr. Note that modifying a training example is equivalent to removing a training example and adding a new one. Given a training dataset Dtr and a poisoning size e, an attacker aims to craft a poisoned training dataset D∗tr to minimize the testing accuracy of the classifier learnt by algorithmM on D∗tr.
  Certified accuracy: Given a training dataset Dtr and a learning algorithmM, we use certified accuracy on a testing dataset Dte = {(xi, yi)}ti=1 to measure the algorithm’s performance. Specifically, we denote certified accuracy at poisoning size e as CA(e) and formally define it as follows:
  CA(e) = min D∗tr∈S(Dtr,e)
  ∑ (xi,yi)∈Dte I(M(D ∗ tr,xi) = yi)
  |Dte| , (2)
  where I is the indicator function andM(D∗tr,xi) is the label predicted for a testing input xi by the classifier learnt by the algorithmM on the poisoned training dataset D∗tr. CA(e) is the least testing accuracy on Dte that the learning algorithmM can achieve no matter how an attacker poisons the training examples when the poisoning size is at most e. Our goal is to derive lower bounds of CA(e) for learning algorithms kNN and rNN.
sections.heading: 3 CERTIFIED ACCURACY OF KNN AND RNN
sections.text: We first derive a lower bound of the certified accuracy via individual certification, which treats testing examples in Dte individually. Then, we derive a better lower bound of the certified accuracy for rNN via joint certification, which treats testing examples jointly.
sections.heading: 3.1 INDIVIDUAL CERTIFICATION
sections.text: Given a poisoning size at most e, our idea is to certify whether the predicted label stays unchanged or not for each testing input individually. If the predicted label of a testing input x stays unchanged
  (i.e.,M(Dtr,x) =M(D∗tr,x)) and it matches with the testing input’s true label, then kNN or rNN certifiably correctly classifies the testing input when the poisoning size is at most e. Therefore, we can obtain a lower bound of the certified accuracy at poisoning size e as the fraction of testing inputs in Dte which kNN or rNN certifiably correctly classifies. Next, we first discuss how to certify whether the predicted label stays unchanged or not for each testing input individually. Then, we show our lower bound of the certified accuracy at poisoning size e.
  Certifying the predicted label of a testing input: Our goal is to certify that M(Dtr,x) = M(D∗tr,x) for a testing input x when the poisoning size is no larger than a threshold. Given a training dataset Dtr (or a poisoned training dataset D∗tr) and a testing input x, we use N (Dtr,x) (or N (D∗tr,x)) to denote the set of nearest neighbors of x in Dtr (or D∗tr) for kNN or rNN. 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., N (Dtr,x) vs. N (D∗tr,x)) depends on the randomness in breaking ties. 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 sl to denote the number of votes in N (Dtr,x) for label l, i.e., the number of nearest neighbors in N (Dtr,x) whose labels are l. Formally, we have sl = ∑ (xj ,yj)∈N (Dtr,x) I(yj = l), where l = 1, 2, · · · , c 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.,M(Dtr,x) = argmaxl∈{1,2,··· ,c} sl. Suppose a and b are the labels with the largest and second largest number of votes, i.e., sa and sb are the largest and second largest ones among {s1, s2, · · · , sc}, respectively. We note that there may exist ties when comparing the labels based on their votes. We define a deterministic ranking of labels in {1, 2, · · · , c} 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 or rNN still predicts label a for the testing input x when the number of poisoned training examples is no more than d sa−sb2 e − 1 (without considering the ties breaking). Formally, we have the following theorem: Theorem 1. Assuming we have a training dataset Dtr, a testing input x, and a nearest neighbor algorithmM (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 (Dtr,x) of x in Dtr. Moreover, sa and sb are the number of votes for a and b, respectively. Then, we have the following:
  M(D∗tr,x) = a,∀D∗tr ∈ S(Dtr, e), e ≤ d sa − sb + I(a > b)
  2 e − 1. (3)
  Proof. When an attacker poisons at most e training examples, the number of changed nearest neighbors in N (Dtr,x) is at most e. We denote by s∗l = ∑ (xj ,yj)∈N (D∗tr,x)
  I(l = yj) the number of votes for label l among the nearest neighbors N (D∗tr,x) in the poisoned training dataset, where l = 1, 2, · · · , c. Then, we have sl − e ≤ s∗l ≤ sl + e for each l = 1, 2, · · · , c. Therefore, when e ≤ d sa−sb+I(a>b)2 e−1, we have s ∗ a−s∗b ≥ sa−sb−2·e > 0 if a < b and s∗a−s∗b ≥ sa−sb−2·e ≥ 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 haveM(D∗tr,x) = a when e ≤ d sa−sb+I(a>b) 2 e − 1.
  Deriving a lower bound of CA(e): kNN or rNN certifiably correctly classifies a testing input x if 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 we have a training dataset Dtr, a testing dataset Dte = {(xi, yi)}ti=1, and a nearest neighbor algorithmM (i.e., kNN or rNN). ai and bi respectively are the two labels with the largest and second largest number of votes among the nearest neighbors
  N (Dtr,xi) of xi in Dtr. Moreover, sai and sbi are the number of votes for ai and bi, respectively. Then, we have the following lower bound of CA(e):
  CA(e) ≥ ∑ (xi,yi)∈Dte I(ai = yi) · I(e ≤ e ∗ i )
  |Dte| , (4)
  where e∗i = d sai−sbi+I(ai>bi) 2 e − 1.
  Proof. See Appendix A.
sections.heading: 3.2 JOINT CERTIFICATION
sections.text: We derive a better lower bound of the certified accuracy via jointly considering multiple testing examples. Our intuition is that, given a group of testing examples and a poisoning size e, an attacker may not be able to make a 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 our proof of Theorem 3 for specific reasons). Next, we first derive a lower bound of CA(e) on a group of testing examples for rNN. Then, we derive a 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 a 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 e in rNN, as the testing examples’ predicted labels are different. We denote by U a group of testing examples with different predicted labels and by m its size, i.e., m = |U|. The next theorem shows a lower bound of CA(e) on the testing examples in U for rNN. Theorem 3. Assuming we have a training dataset Dtr, the learning algorithm rNN, and a group of m testing examples U = {(xi, yi)}mi=1 with different predicted labels. ai and bi respectively are the two labels with the largest and second largest number of votes among the nearest neighbors N (Dtr,xi) of xi in Dtr. Moreover, sai and sbi are the number of votes for ai and bi, respectively. Without loss of generality, we assume the following:
  (sa1 − sb1) · I(a1 = y1) ≥ (sa2 − sb2) · I(a2 = y2) ≥ · · · ≥ (sam − sbm) · I(am = ym). (5)
  Then, the certified accuracy at poisoning size e of rNN for U has a lower bound CA(e) ≥ w−1|U| , where w is the solution to the following optimization problem:
  w = argmin w′,w′≥1 w′ s.t. m∑ i=w′ max(sai − sbi − e+ I(ai > bi), 0) · I(ai = yi) ≤ e. (6)
  Proof. When an attacker can poison at most e training examples, the attacker can add at most e new nearest neighbors and remove e existing ones in N (Dtr,xi) (equivalent to modifying e training examples) in the worst-case scenario. We denote by s∗ai and s ∗ bi
  respectively the number of votes for labels ai and bi among the nearest neighbors N (D∗tr,xi). First, we have s∗bi ≤ sbi + e for ∀i ∈ {1, 2, · · · ,m} since at most e new nearest neighbors are added. Second, we have s∗ai ≥ sai−ei in rNN, where ei is the number of removed nearest neighbors in N (Dtr,xi) whose true labels are ai. Note that kNN does not support joint certification because s∗ai ≥ sai − ei does not hold for kNN. Next, we derive the minimal value of ei such that rNN misclassifies xi. In particular, we consider two cases. If ai 6= yi, i.e., xi is misclassified by rNN without attack, then we have ei = 0. If ai = yi, xi is misclassified by rNN when s∗ai ≤ s ∗ bi if ai < bi and s∗ai < s ∗ bi
  if ai > bi after attack, which means ei ≥ sai − sbi − e + I(ai > bi). Since ei ≥ 0, we have ei ≥ max(sai − sbi − e + I(ai > bi), 0). Combining the two cases, we have the following lower bound for ei that makes rNN misclassify xi: ei ≥ max(sai − sbi − e+ I(ai > bi), 0) · I(ai = yi). Moreover, since the attacker can remove at most e training examples and the group of testing examples have different predicted labels, i.e., ai 6= aj ∀i, j ∈ {1, 2, · · · ,m} and i 6= j, we have ∑m i=1 ei ≤ e. We note that the lower bound of
  ei 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 + 1 testing inputs whose corresponding ei sum to be at most e. Formally, w is the solution to the optimization problem in Equation (6). Therefore, the certified accuracy at poisoning size e is at least w−1|U| .
  Deriving a lower bound of CA(e) for a testing dataset: Based on Theorem 3, we can derive a lower bound of CA(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 a testing dataset Dte, we divide it into λ 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):
  CA(e) ≥ ∑λ j=1 µj · |Uj |∑λ j=1 |Uj | , (7)
  where µj is the lower bound of the certified accuracy at poisoning size e on group Uj , which we can obtain by invoking Theorem 3.
  Proof. See Appendix B.
  Strategies of grouping testing examples: Our Theorem 4 is applicable to any way of dividing the testing examples in Dte to disjoint groups once the testing examples in 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 c (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 we group them with other testing examples, the certified accuracy may be degraded because each group can have at most c testing examples. For instance, if a 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 Dte into three disjoint parts which we denote as D0te, D 1 te, and D 2 te. D 0 te contains the testing examples that cannot be certifiably correctly classified at poisoning size e no matter which group they belong to. Based on our proof of Theorem 3, a testing example (xi, yi) that satisfies (sai − sbi − e + I(ai > bi)) · I(ai = yi) ≤ 0 cannot be certifiably correctly classified at poisoning size e no matter which group it belongs to. Therefore, D0te includes such testing examples. Moreover, based on Theorem 1, a testing example (xi, yi) that satisfies e ≤ d sai−sbi+I(ai>bi) 2 e − 1 can be certifiably correctly classified at poisoning size e. Therefore, D1te includes such testing examples. Each testing example in D0te or D 1 te forms a group by itself. D 2 te includes the remaining testing examples, which we further divide into groups. Our method of dividing D2te into groups is inspired by the proof of Theorem 3. In particular, we form a group of testing examples as follows: for each label l ∈ {1, 2, · · · , c}, we find the testing example that has the largest value of (sai − sbi − e+ I(ai > bi)) · I(ai = l) and we skip the label if there is no remaining testing example whose predicted label is l. We apply the procedure to recursively group the testing examples in D2te until no testing examples are left.
sections.heading: 4 EVALUATION
sections.text: Datasets: We evaluate our methods on MNIST and CIFAR10. We use the popular histogram of oriented gradients (HOG)1 (Dalal & Triggs, 2005) method to extract features for each example, which
  1Public implementation: https://scikit-image.org/docs/dev/api/skimage.feature.html#skimage.feature.hog
  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 use it. We didn’t find ties in determining nearest neighbors for kNN in our experiments. We rank the labels as {1, 2, · · · , 10} to break ties for labels. Parameter settings: While any distance metric is applicable, we use `1 in our experiments for both kNN and rNN. Unless otherwise mentioned, we adopt the following settings: k = 5, 000 for both MNIST and CIFAR10 in kNN; and r = 4 for MNIST and r = 20 for CIFAR10 in rNN, considering the different feature dimensions of MNIST and CIFAR10. 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 a 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− α. All the compared methods have tradeoffs between accuracy under no attacks (i.e., CA(0)) and robustness against attacks. Therefore, we set their parameters such that they have similar accuracy under no attacks (i.e., similar CA(0)). In particular, we use the default k for kNN, and we adjust r for rNN, ζ for DPA, and ξ for bagging. The searched parameters are as follows: r = 4, ζ = 5, 500, and ξ = 27 for MNIST; and r = 21, ζ = 900, and ξ = 400 for CIFAR10. 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 k 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 r achieve tradeoffs between accuracy under no attacks (i.e., CA(0)) and robustness. Specifically, when k or r is smaller, the accuracy under no attacks, i.e., CA(0), is larger, but the certified accuracy decreases more quickly as the poisoning size e increases.
sections.heading: 5 RELATED WORK
sections.text: 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; 2014), 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 (Muñoz-González et al., 2017; Shafahi et al., 2018; Suciu et al., 2018; 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., 2011; Feng et al., 2014; Jagielski et al., 2018; Tran et al., 2018) have been proposed. Steinhardt et al. (2017) derived an 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 et al., 2019; Rosenfeld et 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 probabilistically (Ma et al., 2019; Jia et al., 2020) or deterministically (Rosenfeld et al., 2020; 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 a perturbed version of the training dataset in randomized smoothing based defenses (Rosenfeld et al., 2020), while a voter is a base classifier learnt on a subset of the trainig dataset in DPA (Levine & Feizi, 2020) 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 to 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 a hash function to assign training examples into partitions, which is different from our use of hash function. In particular, we use a hash function to 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 3 nearest neighbors. Peri et al. (2019) proposed to remove a 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 an intermediate layer of a preliminary deep neural network model to filter suspiciously-labeled training examples. Another line of works (Gao et al., 2018; Reeve & Kabán, 2019) studied the resistance of nearest neighbors to 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 & Kabán (2019) further analyzed the Robust kNN proposed by (Gao et 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, 2019a; 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 1-nearest neighbor. Several works (Amsaleg et al., 2017; Wang et al., 2018; 2019; Yang et al., 2020) proposed adversarial examples to nearest neighbors, e.g., Wang et al. (2019) proposed adversarial examples against 1-nearest neighbor. These works are orthogonal to ours as we focus on analyzing the certified robustness of kNN and rNN against general data poisoning attacks.
sections.heading: 6 CONCLUSION AND FUTURE WORK
sections.text: 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-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.
sections.heading: A PROOF OF THEOREM 2
sections.text: Proof. We have the following:
  CA(e) = min D∗tr∈S(Dtr,e)
  ∑ (xi,yi)∈Dte I(M(D ∗ tr,xi) = yi)
  |Dte| (8) ≥ ∑ (xi,yi)∈Dte minD∗tr∈S(Dtr,e) I(M(D ∗ tr,xi) = yi)
  |Dte| (9)
  =
  ∑ (xi,yi)∈Dte I(ai = yi)minD∗tr∈S(Dtr,e) I(M(D ∗ tr,xi) = ai)
  |Dte| (10)
  =
  ∑ (xi,yi)∈Dte I(ai = yi)I(e ≤ e ∗ i )
  |Dte| , (11)
  where the last step is based on applying Theorem 1 to testing input xi.
sections.heading: B PROOF OF THEOREM 4
sections.text: Proof. We have the following:
  CA(e) = min D∗tr∈S(Dtr,e)
  ∑ (xi,yi)∈Dte I(M(D ∗ tr,xi) = yi)
  |Dte| (12)
  = min D∗tr∈S(Dtr,e)
  ∑λ j=1 ∑ (xi,yi)∈Uj I(M(D
  ∗ tr,xi) = yi)∑λ
  j=1 |Uj | (13)
  ≥ ∑λ j=1 minD∗tr∈S(Dtr,e) ∑ (xi,yi)∈Uj I(M(D ∗ tr,xi) = yi)∑λ
  j=1 |Uj | (14)
  ≥ ∑λ j=1 µj · |Uj |∑λ j=1 |Uj | , (15)
  where we have Equation (15) from (14) based on applying Theorem 3 to group Uj .