Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks

Jinyuan JiaYupei LiuXiaoyu CaoNeil Zhenqiang Gong

article2022AAAI96 citations

Proves that the intrinsic majority voting mechanisms in standard nearest neighbor algorithms naturally provide certified defense guarantees against data poisoning and backdoor attacks that outperform existing specialized methods on MNIST and CIFAR-10.

Listen

Machine learning systems deployed in critical domains like cybersecurity and healthcare are increasingly vulnerable to data poisoning and backdoor attacks, where adversaries manipulate training datasets to corrupt model behavior. While recent defenses seek to provide certified robustness—guaranteeing a minimum model accuracy under bounded adversarial contamination—they rely on complex majority-voting ensembles that suffer from weak theoretical guarantees and certify inputs only on an isolated basis. The article demonstrates that classic nearest neighbor algorithms naturally possess certified robustness against both data poisoning and backdoor attacks, and introduces a novel framework to certify multiple predictions simultaneously.

The authors evaluate the intrinsic majority-vote mechanisms in k-nearest neighbors and radius nearest neighbors across standard benchmark datasets (MNIST and CIFAR-10) using empirical evaluations and theoretical proofs. To eliminate ambiguities in tie-breaking, the approach integrates deterministic hashing and systematic label-ranking schemes. Furthermore, the researchers formulate a joint certification technique—specifically enabled by radius nearest neighbors—that groups testing inputs to calculate stronger global accuracy guarantees than traditional individual evaluations allow.

The investigation yields several key findings: First, nearest neighbor methods substantially outperform leading certified defenses; under an attack modifying 1,000 training examples on MNIST, radius nearest neighbors achieved certified accuracies 22.9% and 40.8% higher than state-of-the-art ensemble baselines (bagging and deep partition aggregation, respectively). Second, each poisoned training example corrupts at most one nearest-neighbor voter in the worst case, compared to multiple corrupted voters in existing partition- or subsample-based defenses. Third, applying joint certification improves radius nearest neighbor certified accuracy by 15.1% under large-scale poisoning by accounting for collective attack constraints across distinct classes. Finally, combining nearest neighbor algorithms with self-supervised feature extraction (such as pre-trained CLIP representations) enhances certified performance by 43.0% under a 500-sample attack on CIFAR-10.

These findings indicate that organizations can establish simpler, provably secure machine learning baselines without training complex, compute-heavy ensemble models. A central practical trade-off exists when tuning neighborhood parameters: smaller neighborhood sizes or radii yield higher accuracy during normal operations but degrade faster under severe poisoning, whereas larger parameters ensure greater defensive resilience. For high-assurance deployments, organizations should leverage radius nearest neighbors combined with robust self-supervised feature extractors to maximize security against training pipeline tampering. Future work should focus on extending joint certification mechanisms to broader algorithmic architectures and exploring optimal distance metrics to further boost certified accuracy.

Duke University k-nearest neighbors recurrent neural networks base classifiers certified robustness data poisoning attacks backdoor attacks

arXiv: 2012.03765

Paper: BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain, Tianyu Gu et al. (2017). Introduces the foundational concept and threat model of backdoor and Trojan attacks via poisoned training data in neural networks, which the source establishes certified defense guarantees against.
Paper: Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning, Xinyun Chen et al. (2017). Formulates targeted backdoor data poisoning attacks against deep learning classifiers, motivating the source's pursuit of provable certification against such training pipeline tampering.
Paper: Poisoning Attacks against Support Vector Machines, Battista Biggio et al. (2012). Establishes foundational optimization-based data poisoning attacks on non-neural classifiers, providing the core threat model that the source aims to certifiably defend using nearest-neighbor algorithms.
Paper: Certified Adversarial Robustness via Randomized Smoothing, Jeremy M Cohen et al. (2019). Pioneers majority-voting-based certification frameworks for robustness guarantees, providing theoretical context for the ensemble-based certified defenses that the source critiques and surpasses.
Paper: Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks, Ali Shafahi et al. (2018). Demonstrates clean-label targeted data poisoning attacks on neural networks, highlighting the vulnerability of standard training pipelines that nearest neighbor certification resolves.
Paper: Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks, Kang Liu et al. (2018). Presents early post-training pruning defenses against neural network backdoors, serving as foundational background for the vulnerabilities inherent in standard models under data tampering.

Paper: Detecting Backdoors in Pre-trained Encoders, Shiwei Feng et al. (2023). Extends the protection of self-supervised representation encoders against backdoor attacks by introducing automated trigger inversion and detection directly on pre-trained embedding spaces.
Paper: Reconstructive Neuron Pruning for Backdoor Defense, Yige Li et al. (2023). Develops a fine-grained post-training neuron pruning defense to remove backdoors from deep neural networks, offering a complementary empirical mitigation strategy to certified non-parametric defenses.

Cover for Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks

Abstract

Data poisoning attacks and backdoor attacks aim to corrupt a machine learning classifier via modifying, adding, and/or removing some carefully selected training examples, such that the corrupted classifier makes incorrect predictions as the attacker desires. The key idea of state-of-the-art certified defenses against data poisoning attacks and backdoor 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. Classical simple learning 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 data poisoning attacks and backdoor attacks. Moreover, our 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. Our results serve as standard baselines for future certified defenses against data poisoning attacks and backdoor attacks.

Topics

k-nearest neighbors recurrent neural networks base classifiers svm malicious attack

Keywords

certified robustness data poisoning attacks backdoor attacks nearest neighbors robustness guarantees Robust kNN adversarial examples asymmetric label noise self-supervised learning support vector machines

Introduction
Problem Setup
Certified Accuracy of kNN and rNN
Individual Certification
Joint Certification
Evaluation
Related Work
Conclusion and Future Work
Acknowledgments
References

Knowls

Knowl 1 — Deterministic Individual Robustness Certificate for kNN and rNN
theoretical result
Let $D_{\text{tr}}$ be a clean training dataset with $n$ examples, and let $x$ be a testing input. Let $M$ be a $k$ -nearest neighbors ( $k\text{NN}$ ) or radius nearest neighbors ( $r\text{NN}$ ) classifier that determines the set of nearest neighbors $N(D_{\text{tr}}, x)$ . For each class label $l \in \{1, 2, \dots, c\}$ , the vote count is $s_l = \sum_{(x_j, y_j) \in N(D_{\text{tr}}, x)} \mathbb{I}(y_j = l)$ , where $\mathbb{I}$ is the indicator function. Let $a$ and $b$ denote the labels with the largest and second largest vote counts, respectively ( $s_a \ge s_b$ ). Ties among labels are broken by a fixed deterministic priority ordering on $\{1, \dots, c\}$ .

For any poisoned dataset $D^*_{\text{tr}}$ satisfying poisoning size $S(D_{\text{tr}}, D^*_{\text{tr}}) \le e$ with: $e \le \left\lceil \frac{s_a - s_b + \mathbb{I}(a > b)}{2} \right\rceil - 1$ the predicted label is certifiably invariant, i.e., $M(D^*_{\text{tr}}, x) = a$ .

Given a testing dataset $D_{\text{te}} = \{(x_i, y_i)\}_{i=1}^t$ , the certified accuracy $\text{CA}(e)$ under individual certification is lower-bounded by: $\text{CA}(e) \ge \frac{1}{|D_{\text{te}}|} \sum_{(x_i, y_i) \in D_{\text{te}}} \mathbb{I}(a_i = y_i) \cdot \mathbb{I}\left(e \le \left\lceil \frac{s_{a_i} - s_{b_i} + \mathbb{I}(a_i > b_i)}{2} \right\rceil - 1\right)$ where $a_i$ and $b_i$ are the top two predicted labels for testing sample $x_i$ with vote counts $s_{a_i}$ and $s_{b_i}$ .
Knowl 2 — Joint Robustness Certification of rNN over a Group with Distinct Predicted Labels
theoretical result
Let $D_{\text{tr}}$ be a training dataset, and let $M$ be a radius nearest neighbors ( $r\text{NN}$ ) classifier with radius $r$ . Let $U = \{(x_i, y_i)\}_{i=1}^m$ be a subset of testing examples such that all clean predicted labels $a_i = M(D_{\text{tr}}, x_i)$ are distinct ( $a_i \ne a_j$ for all $i \ne j$ ). For each $x_i$ , let $b_i$ be the label with the second highest vote count in $N(D_{\text{tr}}, x_i)$ , and let $s_{a_i}, s_{b_i}$ be the vote counts of $a_i, b_i$ . Assume without loss of generality that the examples in $U$ are indexed in descending order of margin: $(s_{a_1} - s_{b_1}) \cdot \mathbb{I}(a_1 = y_1) \ge (s_{a_2} - s_{b_2}) \cdot \mathbb{I}(a_2 = y_2) \ge \dots \ge (s_{a_m} - s_{b_m}) \cdot \mathbb{I}(a_m = y_m)$

At poisoning size $e$ , the certified accuracy of $r\text{NN}$ on group $U$ is lower-bounded by $\text{CA}(e) \ge \frac{w - 1}{|U|}$ , where $w$ is the optimal solution to the integer optimization problem: $w = \arg\min_{w' \ge 1} w' \quad \text{s.t.} \quad \sum_{i=w'}^m \max\left(s_{a_i} - s_{b_i} - e + \mathbb{I}(a_i > b_i), 0\right) \cdot \mathbb{I}(a_i = y_i) \le e$
Knowl 3 — Dataset-Level Certified Accuracy for rNN via Disjoint Grouping
theoretical result
Let $D_{\text{te}}$ be a testing dataset evaluated under radius nearest neighbors ( $r\text{NN}$ ). Suppose $D_{\text{te}}$ is partitioned into $\lambda$ disjoint groups $U_1, U_2, \dots, U_\lambda$ , such that within each group $U_j$ , no two testing examples have the same predicted label $M(D_{\text{tr}}, x)$ . The overall certified accuracy $\text{CA}(e)$ at poisoning size $e$ is lower-bounded by the weighted average of the group-level certified accuracy bounds: $\text{CA}(e) \ge \frac{\sum_{j=1}^\lambda \mu_j \cdot |U_j|}{\sum_{j=1}^\lambda |U_j|}$ where each $\mu_j$ is the certified accuracy lower bound for group $U_j$ at poisoning size $e$ computed by joint group certification.
Knowl 4 — ISLAND Grouping Algorithm for rNN Joint Certification
algorithm
The Isolation and Division (ISLAND) grouping algorithm partitions a testing dataset $D_{\text{te}}$ into disjoint groups $U_1, U_2, \dots, U_\lambda$ with distinct predicted classes to maximize the lower bound of certified accuracy at a given poisoning size $e$ .

It first separates $D_{\text{te}}$ into three disjoint subsets:
1. $D^0_{\text{te}}$ : Testing examples that cannot be certifiably correctly classified at poisoning size $e$ under any grouping, defined by $(s_{a_i} - s_{b_i} - e + \mathbb{I}(a_i > b_i)) \cdot \mathbb{I}(a_i = y_i) \le 0$ .
2. $D^1_{\text{te}}$ : Testing examples that are already certifiably correctly classified individually, satisfying $e \le \lceil \frac{s_{a_i} - s_{b_i} + \mathbb{I}(a_i > b_i)}{2} \rceil - 1$ .
3. $D^2_{\text{te}} = D_{\text{te}} \setminus (D^0_{\text{te}} \cup D^1_{\text{te}})$ : The remaining indeterminate testing examples.
Each example in $D^0_{\text{te}}$ and $D^1_{\text{te}}$ is placed into its own singleton group. Examples in $D^2_{\text{te}}$ are iteratively formed into multi-class groups by greedily selecting the candidate with the highest margin for each available label $l \in \{1, \dots, c\}$ .
Input: Testing dataset $D_\text{te}$ , poisoning size $e$ , number of classes $c$ , margin values $V_i = (s_{a_i} - s_{b_i} - e + \mathbb{I}(a_i > b_i)) \cdot \mathbb{I}(a_i = y_i)$
Output: Set of disjoint groups $\mathcal{U} = \{U_1, U_2, \dots, U_\lambda\}$
$\mathcal{U} \leftarrow \emptyset$
$D^0_\text{te} \leftarrow \{(x_i, y_i) \in D_\text{te} \mid V_i \le 0\}$
$D^1_\text{te} \leftarrow \{(x_i, y_i) \in D_\text{te} \mid e \le \lceil (s_{a_i} - s_{b_i} + \mathbb{I}(a_i > b_i))/2 \rceil - 1\}$
$D^2_\text{te} \leftarrow D_\text{te} \setminus (D^0_\text{te} \cup D^1_\text{te})$
for each $(x_i, y_i) \in D^0_\text{te} \cup D^1_\text{te}$ do
     $\mathcal{U} \leftarrow \mathcal{U} \cup \{\{(x_i, y_i)\}\ crosstalk$
end for
while $D^2_\text{te} \ne \emptyset$ do
     $U_\text{new} \leftarrow \emptyset$
    for $l = 1$ to $c$ do
         $C_l \leftarrow \{(x_i, y_i) \in D^2_\text{te} \mid a_i = l\}$
        if $C_l \ne \emptyset$ then
             $x^* \leftarrow \arg\max_{(x_i, y_i) \in C_l} V_i$
             $U_\text{new} \leftarrow U_\text{new} \cup \{x^*\}$
             $D^2_\text{te} \leftarrow D^2_\text{te} \setminus \{x^*\}$
        end if
    end for
     $\mathcal{U} \leftarrow \mathcal{U} \cup \{U_\text{new}\}$
end while
return $\mathcal{U}$
Knowl 5 — Deterministic Neighbor and Label Tie-Breaking
model/method
To eliminate the stochasticity that arises when nearest neighbors or label votes have identical distances or counts, deterministic tie-breaking rules are applied:
1. Nearest Neighbor Tie-Breaking: Each training sample $(x_i, y_i) \in D_{\text{tr}}$ is mapped to a unique deterministic priority rank. This is achieved by computing a collision-resistant cryptographic hash (such as SHA-1) of the sample's feature vector and label, and ranking training samples by their hash values. In $k\text{NN}$ , if multiple training examples have the same distance to a test point $x$ , the examples with higher deterministic ranks are selected as the $k$ nearest neighbors.
2. Label Tie-Breaking: A fixed deterministic ordering is imposed over all class labels $\{1, 2, \dots, c\}$ (e.g., $1 < 2 < \dots < c$ ). When two or more classes achieve the exact same highest vote count in the nearest neighbor neighborhood, the label with the highest deterministic priority rank is selected as the predicted label.
Knowl 6 — Poisoning Size and Certified Accuracy Formulations
definition
Let $D_{\text{tr}}$ be a clean training dataset and $D^*_{\text{tr}}$ be a poisoned training dataset resulting from adding, modifying, or removing training examples. The poisoning size $S(D_{\text{tr}}, D^*_{\text{tr}})$ is the minimal number of modified, added, or removed examples needed to transition $D_{\text{tr}}$ into $D^*_{\text{tr}}$ , defined as: $S(D_{\text{tr}}, D^*_{\text{tr}}) = \max\{|D^*_{\text{tr}}|, |D_{\text{tr}}|\} - |D^*_{\text{tr}} \cap D_{\text{tr}}|$

Given a testing dataset $D_{\text{te}} = \{(x_i, y_i)\}_{i=1}^t$ and a learning algorithm $M$ , the certified accuracy $\text{CA}(e)$ at poisoning size $e$ is the minimum test accuracy achieved on $D_{\text{te}}$ across all possible poisoned training datasets within distance $e$ : $\text{CA}(e) = \min_{D^*_{\text{tr}} : S(D_{\text{tr}}, D^*_{\text{tr}}) \le e} \frac{1}{|D_{\text{te}}|} \sum_{(x_i, y_i) \in D_{\text{te}}} \mathbb{I}\left(M(D^*_{\text{tr}}, x_i) = y_i\right)$
Knowl 7 — Asymmetry of Neighbor Replacement Preventing kNN Joint Certification
limitation
Joint certification across multiple test examples relies on bounding the sum of lost votes $\sum_{i=1}^m e_i \le e$ for distinct predicted classes $a_i \ne a_j$ , which requires that removing $e_i$ true-class neighbors guarantees $s^*_{a_i} \ge s_{a_i} - e_i$ .

In radius nearest neighbors ( $r\text{NN}$ ), the ball radius $r$ is fixed; hence, removing $e_i$ training examples inside the radius cannot introduce any new non-adversarial points into $N(D^*_{\text{tr}}, x_i)$ , ensuring $s^*_{a_i} \ge s_{a_i} - e_i$ .

In $k$ -nearest neighbors ( $k\text{NN}$ ), removing $e$ training examples changes the distance threshold of the $k$ -th neighbor, pulling formerly distant training examples into the top- $k$ set $N(D^*_{\text{tr}}, x_i)$ . Because these newly admitted examples can alter vote distributions unpredictably, the inequality $s^*_{a_i} \ge s_{a_i} - e_i$ does not hold for $k\text{NN}$ , preventing the application of joint certification.
Knowl 8 — Certified Accuracy Comparison of kNN and rNN against Bagging and DPA
empirical result
On the MNIST dataset with $\ell_1$ distance and HOG feature extraction, $k\text{NN}$ ( $k=5000$ ) and $r\text{NN}$ ( $r=4$ ) substantially outperform state-of-the-art certified defenses under data poisoning attacks:
- At a poisoning budget of $e = 1000$ modified/inserted/removed training examples, $r\text{NN}$ with ISLAND joint certification achieves a certified accuracy $22.9\%$ higher than Bagging ( $N=1000, \xi=20, \alpha=0.001$ ) and $40.8\%$ higher than Deep Partition Aggregation (DPA, $\zeta=2500$ ).
The certified robustness advantage is due to the voter corruption rate: a single poisoned training instance corrupts multiple sub-sampled base models in Bagging and two base partition models in DPA, whereas in $k\text{NN}$ and $r\text{NN}$ , each poisoned sample corrupts at most one neighbor voter.
Knowl 9 — Certified Robustness Enhancement via Pre-trained Self-Supervised Representations
empirical result
Extracting features using an uncorrupted self-supervised pre-trained model (CLIP, pre-trained on 400 million image-text pairs) significantly improves the certified poisoning accuracy of nearest neighbor classifiers on CIFAR-10 compared to standard HOG features.

When defending against data poisoning attacks with an attack budget of $e = 500$ poisoned training examples on CIFAR-10, $k\text{NN}$ ( $k=5000$ ) using CLIP representations achieves a certified accuracy $43.0\%$ higher than $k\text{NN}$ trained without self-supervised feature extraction.
Knowl 10 — Empirical Accuracy Gain of Joint Certification over Individual Certification
empirical result
Evaluating $r\text{NN}$ ( $r=4$ ) on MNIST under data poisoning attacks demonstrates that joint certification yields tighter certified accuracy lower bounds than individual certification:
- At poisoning size $e = 1000$ , joint certification using the ISLAND grouping strategy improves certified accuracy by $15.1\%$ over individual certification.
- The ISLAND grouping strategy strictly outperforms naive Random Division (RD) grouping across poisoning sizes because ISLAND isolates provably failed ( $D^0_{\text{te}}$ ) and individually verified ( $D^1_{\text{te}}$ ) samples, maximizing the margin utilization in multi-class groups for the remaining test examples ( $D^2_{\text{te}}$ ).

Coverage note — None was omitted; all key theoretical definitions, individual and joint certification bounds, the ISLAND grouping algorithm, the kNN limitation, and empirical findings were extracted.

References

1.
1. CLIP. "https://github.com/openai/CLIP". Accessed: 2021-08.
2.
1. HOG. "https://scikit-image.org/docs/dev/api/skimage.feature.html\#skimage.feature.hog". Accessed: 2021-08.
3.Amsaleg, L.; Bailey, J.; Barbe, D.; Erfani, S.; Houle, M. E.; Nguyen, V.; and Radovanović, M. 2017. The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality. In 2017 IEEE Workshop on Information Forensics and Security (WIFS), 1–6. IEEE.
4.Bagdasaryan, E.; Veit, A.; Hua, Y.; Estrin, D.; and Shmatikov, V. 2020. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, 2938–2948. PMLR.
5.Bahri, D.; Jiang, H.; and Gupta, M. 2020. Deep k-nn for noisy labels. In International Conference on Machine Learning, 540–550. PMLR.
6.Barreno, M.; Nelson, B.; Sears, R.; Joseph, A. D.; and Tygar, J. D. 2006. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, computer and communications security, 16–25.
7.Bhagoji, A. N.; Chakraborty, S.; Mittal, P.; and Calo, S. 2019. Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning, 634–643. PMLR.
8.Biggio, B.; Corona, I.; Fumera, G.; Giacinto, G.; and Roli, F. 2011. Bagging classifiers for fighting poisoning attacks in adversarial classification tasks. In International workshop on multiple classifier systems, 350–359. Springer.
9.Biggio, B.; Fumera, G.; and Roli, F. 2013. Security evaluation of pattern classifiers under attack. IEEE Transactions on Knowledge and Data Engineering, 26(4): 984–996.
10.Biggio, B.; Nelson, B.; and Laskov, P. 2012. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, 1467–1474.
11.Chen, T.; Kornblith, S.; Norouzi, M.; and Hinton, G. 2020. A simple framework for contrastive learning of visual representations. In International conference on machine learning, 1597–1607. PMLR.
12.Chen, X.; Liu, C.; Li, B.; Lu, K.; and Song, D. 2017. Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning. CoRR, abs/1712.05526.
13.Cover, T.; and Hart, P. 1967. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1): 21–27.
14.Dalal, N.; and Triggs, B. 2005. Histograms of oriented gradients for human detection. In 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR’05), volume 1, 886–893. Ieee.
15.Demontis, A.; Melis, M.; Pintor, M.; Jagielski, M.; Biggio, B.; Oprea, A.; Nita-Rotaru, C.; and Roli, F. 2019. Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks. In 28th USENIX security symposium, 321–338.
16.Diakonikolas, I.; Kamath, G.; Kane, D.; Li, J.; Steinhardt, J.; and Stewart, A. 2019. Sever: A robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning, 1596–1606. PMLR.
17.Fang, M.; Cao, X.; Jia, J.; and Gong, N. 2020. Local Model Poisoning Attacks to Byzantine-Robust Federated Learning. In 29th USENIX Security Symposium, 1605–1622.
18.Fang, M.; Gong, N. Z.; and Liu, J. 2020. Influence function based data poisoning attacks to top-n recommender systems. In Proceedings of The Web Conference 2020, 3019–3025.
19.Fang, M.; Yang, G.; Gong, N. Z.; and Liu, J. 2018. Poisoning attacks to graph-based recommender systems. In Proceedings of the 34th Annual Computer Security Applications Conference, 381–392.
20.Feng, J.; Xu, H.; Mannor, S.; and Yan, S. 2014. Robust logistic regression and classification. In Proceedings of the 27th International Conference on Neural Information Processing Systems-Volume 1, 253–261.
21.Fix, E.; and Hodges, J. 1951. Discriminatory Analysis: Nonparametric Discrimination, Consistency Properties. Report No. 4, USAF School of Aviation Medicine, Randolph Field, Texas, Feb.
22.Gao, W.; Niu, X.-Y.; and Zhou, Z.-H. 2016. On the Consistency of Exact and Approximate Nearest Neighbor with Noisy Data. ArXiv, abs/1607.07526.
23.Gu, T.; Liu, K.; Dolan-Gavitt, B.; and Garg, S. 2019. BadNets: Evaluating Backdooring Attacks on Deep Neural Networks. IEEE Access, 7: 47230–47244.
24.Guyon, I.; Matić, N.; and Vapnik, V. 1994. Discovering informative patterns and data cleaning. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, 145–156.
25.Hadsell, R.; Chopra, S.; and LeCun, Y. 2006. Dimensionality reduction by learning an invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, volume 2, 1735–1742. IEEE.
26.He, K.; Fan, H.; Wu, Y.; Xie, S.; and Girshick, R. 2020. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 9729–9738.
27.Jagielski, M.; Oprea, A.; Biggio, B.; Liu, C.; Nita-Rotaru, C.; and Li, B. 2018. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium on Security and Privacy, 19–35. IEEE.
28.Jia, J.; Cao, X.; and Gong, N. Z. 2021. Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 7961–7969.
29.Jia, J.; Liu, Y.; Cao, X.; and Gong, N. Z. 2022. Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks. CoRR, abs/2012.03765.
30.Jia, J.; Liu, Y.; and Gong, N. Z. 2022. BadEncoder: Backdoor Attacks to Pre-trained Encoders in Self-Supervised Learning. In IEEE Symposium on Security and Privacy, 346–362. IEEE.
31.Levine, A.; and Feizi, S. 2021. Deep Partition Aggregation: Provable Defenses against General Poisoning Attacks. In International Conference on Learning Representations.
32.Li, B.; Wang, Y.; Singh, A.; and Vorobeychik, Y. 2016. Data poisoning attacks on factorization-based collaborative filtering. In Proceedings of the 30th International Conference on Neural Information Processing Systems, 1893–1901.
33.Liu, K.; Dolan-Gavitt, B.; and Garg, S. 2018. Fine-pruning: Defending against backdooring attacks on deep neural networks. In International Symposium on Research in Attacks, Intrusions, and Defenses, 273–294. Springer.
34.Liu, Y.; Ma, S.; Aafer, Y.; Lee, W.-C.; Zhai, J.; Wang, W.; and Zhang, X. 2018. Trojaning Attack on Neural Networks. In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-221, 2018. The Internet Society.
35.Ma, Y.; Zhu, X.; and Hsu, J. 2019. Data poisoning against differentially-private learners: attacks and defenses. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 4732–4738.
36.Mozaffari-Kermani, M.; Sur-Kolay, S.; Raghunathan, A.; and Jha, N. K. 2014. Systematic poisoning attacks on and defenses for machine learning in healthcare. IEEE Journal of Biomedical and Health Informatics, 19(6): 1893–1905.
37.Muñoz-González, L.; Biggio, B.; Demontis, A.; Paudice, A.; Wongrassamee, V.; Lupu, E. C.; and Roli, F. 2017. Towards poisoning of deep learning algorithms with back-gradient optimization. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security.
38.Nelson, B.; Barreno, M.; Chi, F. J.; Joseph, A. D.; Rubinstein, B. I.; Saini, U.; Sutton, C. A.; Tygar, J. D.; and Xia, K. 2008. Exploiting Machine Learning to Subvert Your Spam Filter. LEET, 8: 1–9.
39.Peri, N.; Gupta, N.; Huang, W. R.; Fowl, L.; Zhu, C.; Feizi, S.; Goldstein, T.; and Dickerson, J. P. 2020. Deep k-nn defense against clean-label data poisoning attacks. In European Conference on Computer Vision, 55–70. Springer.
40.Radford, A.; Kim, J. W.; Hallacy, C.; Ramesh, A.; Goh, G.; Agarwal, S.; Sastry, G.; Askell, A.; Mishkin, P.; Clark, J.; et al. 2021. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, 8748–8763. PMLR.
41.Reeve, H.; and Kabán, A. 2019. Fast rates for a kNN classifier robust to unknown asymmetric label noise. In International Conference on Machine Learning, 5401–5409. PMLR.
42.Rosenfeld, E.; Winston, E.; Ravikumar, P.; and Kolter, Z. 2020. Certified robustness to label-flipping attacks via randomized smoothing. In International Conference on Machine Learning, 8230–8241. PMLR.
43.Rubinstein, B. I.; Nelson, B.; Huang, L.; Joseph, A. D.; Lau, S.-h.; Rao, S.; Taft, N.; and Tygar, J. D. 2009. Antidote: understanding and defending against poisoning of anomaly detectors. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, 1–14.
44.Shafahi, A.; Huang, W. R.; Najibi, M.; Suciu, O.; Studer, C.; Dumitras, T.; and Goldstein, T. 2018. Poison frogs! targeted clean-label poisoning attacks on neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 6106–6116.
45.Sitawarin, C.; and Wagner, D. 2019. On the robustness of deep k-nearest neighbors. In 2019 IEEE Security and Privacy Workshops, 1–7. IEEE.
46.Steinhardt, J.; Koh, P. W.; and Liang, P. 2017. Certified defenses for data poisoning attacks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, 3520–3532.
47.Suciu, O.; Marginean, R.; Kaya, Y.; Daume III, H.; and Dumitras, T. 2018. When does machine learning {FAIL}? generalized transferability for evasion and poisoning attacks. In 27th USENIX Security Symposium, 1299–1316.
48.Tran, B.; Li, J.; and Madry, A. 2018. Spectral signatures in backdoor attacks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 8011–8021.
49.Wang, B.; Cao, X.; Jia, J.; and Gong, N. Z. 2020. On Certifying Robustness against Backdoor Attacks via Randomized Smoothing. In CVPR 2020 Workshop on Adversarial Machine Learning in Computer Vision.
50.Wang, B.; Yao, Y.; Shan, S.; Li, H.; Viswanath, B.; Zheng, H.; and Zhao, B. Y. 2019a. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium on Security and Privacy, 707–723. IEEE.
51.Wang, L.; Liu, X.; Yi, J.; Zhou, Z.; and Hsieh, C. 2019b. Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspective. CoRR, abs/1906.03972.
52.Wang, Y.; Jha, S.; and Chaudhuri, K. 2018. Analyzing the robustness of nearest neighbors to adversarial examples. In International Conference on Machine Learning, 5133–5142. PMLR.
53.Weber, M.; Xu, X.; Karlas, B.; Zhang, C.; and Li, B. 2020. RAB: Provable Robustness Against Backdoor Attacks. CoRR, abs/2003.08904.
54.Wilson, D. L. 1972. Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems, Man, and Cybernetics, (3): 408–421.
55.Xiao, H.; Biggio, B.; Brown, G.; Fumera, G.; Eckert, C.; and Roli, F. 2015a. Is feature selection secure against training data poisoning? In international conference on machine learning, 1689–1698. PMLR.
56.Xiao, H.; Biggio, B.; Nelson, B.; Xiao, H.; Eckert, C.; and Roli, F. 2015b. Support vector machines under adversarial label contamination. Neurocomputing, 160: 53–62.
57.Yang, G.; Gong, N. Z.; and Cai, Y. 2017. Fake Co-visitation Injection Attacks to Recommender Systems. In 24th Annual Network and Distributed System Security Symposium, NDSS 2017, San Diego, California, USA, February, 2017. The Internet Society.
58.Yang, Y.-Y.; Rashtchian, C.; Wang, Y.; and Chaudhuri, K. 2020. Robustness for non-parametric classification: A generic attack and defense. In International Conference on Artificial Intelligence and Statistics, 941–951. PMLR.

Citation

MLA

Jia, J., et al. “Certified Robustness of Nearest Neighbors Against Data Poisoning and Backdoor Attacks”. arXiv, 2020, http://arxiv.org/abs/2012.03765v3.

APA

Jia, J., Liu, Y., Cao, X., & Gong, N. Z. (2020). Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks. arXiv. http://arxiv.org/abs/2012.03765v3

Chicago

Jia, J., Y. Liu, X. Cao, and N. Z. Gong. 2020. “Certified Robustness of Nearest Neighbors Against Data Poisoning and Backdoor Attacks”. arXiv. http://arxiv.org/abs/2012.03765v3.

Harvard

Jia, J. et al. (2020) “Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2012.03765v3.

Vancouver

1. Jia J, Liu Y, Cao X, Gong NZ (2020) Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks. arXiv

BibTeX

@article{jia2020certified,
  title = {Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks},
  author = {Jia, Jinyuan and Liu, Yupei and Cao, Xiaoyu and Gong, Neil Zhenqiang},
  year = {2020},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2012.03765v3},
  eprint = {2012.03765}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Deterministic Individual Robustness Certificate for kNN and rNN

Knowl 2 — Joint Robustness Certification of rNN over a Group with Distinct Predicted Labels

Knowl 3 — Dataset-Level Certified Accuracy for rNN via Disjoint Grouping

Knowl 4 — ISLAND Grouping Algorithm for rNN Joint Certification

Knowl 5 — Deterministic Neighbor and Label Tie-Breaking

Knowl 6 — Poisoning Size and Certified Accuracy Formulations

Knowl 7 — Asymmetry of Neighbor Replacement Preventing kNN Joint Certification

Knowl 8 — Certified Accuracy Comparison of kNN and rNN against Bagging and DPA

Knowl 9 — Certified Robustness Enhancement via Pre-trained Self-Supervised Representations

Knowl 10 — Empirical Accuracy Gain of Joint Certification over Individual Certification

References

Citation

BibTeX

Access the Paper