Data to 13 Oct 2026

Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks

arXiv 2012.03765 ↗First posted 7 Dec 2020cs.CR cs.LGcited by 60

Not on the map. Why?

Cited by 22 in LLM safety and security, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

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.

Key facts. Cited by 60 papers in the map (data through 13 Oct 2026). First posted on arXiv 7 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 4; 2022: 13; 2023: 18; 2024: 10; 2025: 10; 2026: 5.

60 papers.

Sort:

By area:

2024PoisonedRAG: Knowledge Corruption Attacks to Retrieval-Augmented Generation of Large Language Modelscited by 265
2021Adversarial Unlearning of Backdoors via Implicit Hypergradientcited by 164
2021Rethinking the Backdoor Attacks' Triggers: A Frequency Perspectivecited by 161
2022Training Data Influence Analysis and Estimation: A Surveycited by 134
2022Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoningcited by 93
2023Detecting Backdoors in Pre-trained Encoderscited by 55
2023Shared Adversarial Unlearning: Backdoor Mitigation by Unlearning Shared Adversarial Examplescited by 43
2022PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learningcited by 34
2023Elijah: Eliminating Backdoors Injected in Diffusion Models via Distribution Shiftcited by 31
2022FLCert: Provably Secure Federated Learning against Poisoning Attackscited by 30
2023BadRL: Sparse Targeted Backdoor Attack Against Reinforcement Learningcited by 30
2022CorruptEncoder: Data Poisoning based Backdoor Attacks to Contrastive Learningcited by 29

38 more

2023BackdoorBox: A Python Toolbox for Backdoor Learningcited by 26
2021Certifying Robustness to Programmable Data Bias in Decision Treescited by 21
2022BagFlip: A Certified Defense against Data Poisoningcited by 19
2022On Collective Robustness of Bagging Against Data Poisoningcited by 16
2023TextGuard: Provable Defense against Backdoor Attacks on Text Classificationcited by 16
2023Defenses in Adversarial Machine Learning: A Surveycited by 14
2022Backdoor Vulnerabilities in Normally Trained Deep Learning Modelscited by 13
2023CBD: A Certified Backdoor Detector Based on Local Dominant Probabilitycited by 13
2024LOTUS: Evasive and Resilient Backdoor Attacks through Sub-Partitioningcited by 13
2022Lethal Dose Conjecture on Data Poisoningcited by 12
2022Unraveling the Connections between Privacy and Certified Robustness in Federated Learning Against Poisoning Attackscited by 12
2024Dialectical Alignment: Resolving the Tension of 3H and Security Threats of LLMscited by 11
2023Temporal Robustness against Data Poisoningcited by 10
2023PORE: Provably Robust Recommender Systems against Data Poisoning Attackscited by 10
2024Mutual Information Guided Backdoor Mitigation for Pre-trained Encoderscited by 8
2022Reducing Certified Regression to Certified Classification for General Poisoning Attackscited by 7
2023Certifying the Fairness of KNN in the Presence of Dataset Biascited by 7
2021Incompatibility Clustering as a Defense Against Backdoor Poisoning Attackscited by 5
2023PECAN: A Deterministic Certified Defense Against Backdoor Attackscited by 5
2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
2025CtrlRAG: Black-box Document Poisoning Attacks for Retrieval-Augmented Generation of Large Language Modelscited by 5
2022DECK: Model Hardening for Defending Pervasive Backdoorscited by 4
2022Pre-trained Encoders in Self-Supervised Learning Improve Secure and Privacy-preserving Supervised Learningcited by 4
2024Mudjacking: Patching Backdoor Vulnerabilities in Foundation Modelscited by 4
2025Cert-SSBD: Certified Backdoor Defense with Sample-Specific Smoothing Noisescited by 4
2024FCert: Certifiably Robust Few-Shot Classification in the Era of Foundation Modelscited by 3
2024FullCert: Deterministic End-to-End Certification for Training and Inference of Neural Networkscited by 2
2025Evading Data Provenance in Deep Neural Networkscited by 2
2023Pick your Poison: Undetectability versus Robustness in Data Poisoning Attackscited by 1
2023On Practical Aspects of Aggregation Defenses against Data Poisoning Attackscited by 1
2023Systematic Testing of the Data-Poisoning Robustness of KNNcited by 1
2023Attacking Byzantine Robust Aggregation in High Dimensionscited by 1
2025Backdoor Detection through Replicated Execution of Outsourced Trainingcited by 1
2025CUBA: Controlled Untargeted Backdoor Attack against Deep Neural Networkscited by 1
2026Analyzing Fairness of Neural Network Prediction via Counterfactual Dataset Generationcited by 1
2023Geometric Algorithms for k-NN Poisoningcited by 0
2023Mendata: A Framework to Purify Manipulated Training Datacited by 0
2024A general approach to enhance the survivability of backdoor attacks by decision path couplingcited by 0

50 most cited of 60 All 60 (JSON)