# Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks

arXiv: https://arxiv.org/abs/2012.03765 · HTML: https://mlsanity.com/paper/2012.03765/

## Key facts

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

## Built on by (most cited first, 30 of 60)

- [PoisonedRAG: Knowledge Corruption Attacks to Retrieval-Augmented Generation of Large Language Models](https://mlsanity.com/paper/2402.07867/) (2024)
- [Adversarial Unlearning of Backdoors via Implicit Hypergradient](https://mlsanity.com/paper/2110.03735/) (2021)
- [Rethinking the Backdoor Attacks' Triggers: A Frequency Perspective](https://mlsanity.com/paper/2104.03413/) (2021)
- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning](https://mlsanity.com/paper/2205.01992/) (2022)
- [Detecting Backdoors in Pre-trained Encoders](https://mlsanity.com/paper/2303.15180/) (2023)
- [Shared Adversarial Unlearning: Backdoor Mitigation by Unlearning Shared Adversarial Examples](https://mlsanity.com/paper/2307.10562/) (2023)
- [PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learning](https://mlsanity.com/paper/2205.06401/) (2022)
- [Elijah: Eliminating Backdoors Injected in Diffusion Models via Distribution Shift](https://mlsanity.com/paper/2312.00050/) (2023)
- [FLCert: Provably Secure Federated Learning against Poisoning Attacks](https://mlsanity.com/paper/2210.00584/) (2022)
- [BadRL: Sparse Targeted Backdoor Attack Against Reinforcement Learning](https://mlsanity.com/paper/2312.12585/) (2023)
- [CorruptEncoder: Data Poisoning based Backdoor Attacks to Contrastive Learning](https://mlsanity.com/paper/2211.08229/) (2022)
- [BackdoorBox: A Python Toolbox for Backdoor Learning](https://mlsanity.com/paper/2302.01762/) (2023)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [BagFlip: A Certified Defense against Data Poisoning](https://mlsanity.com/paper/2205.13634/) (2022)
- [On Collective Robustness of Bagging Against Data Poisoning](https://mlsanity.com/paper/2205.13176/) (2022)
- [TextGuard: Provable Defense against Backdoor Attacks on Text Classification](https://mlsanity.com/paper/2311.11225/) (2023)
- [Defenses in Adversarial Machine Learning: A Survey](https://mlsanity.com/paper/2312.08890/) (2023)
- [Backdoor Vulnerabilities in Normally Trained Deep Learning Models](https://mlsanity.com/paper/2211.15929/) (2022)
- [CBD: A Certified Backdoor Detector Based on Local Dominant Probability](https://mlsanity.com/paper/2310.17498/) (2023)
- [LOTUS: Evasive and Resilient Backdoor Attacks through Sub-Partitioning](https://mlsanity.com/paper/2403.17188/) (2024)
- [Lethal Dose Conjecture on Data Poisoning](https://mlsanity.com/paper/2208.03309/) (2022)
- [Unraveling the Connections between Privacy and Certified Robustness in Federated Learning Against Poisoning Attacks](https://mlsanity.com/paper/2209.04030/) (2022)
- [Dialectical Alignment: Resolving the Tension of 3H and Security Threats of LLMs](https://mlsanity.com/paper/2404.00486/) (2024)
- [Temporal Robustness against Data Poisoning](https://mlsanity.com/paper/2302.03684/) (2023)
- [PORE: Provably Robust Recommender Systems against Data Poisoning Attacks](https://mlsanity.com/paper/2303.14601/) (2023)
- [Mutual Information Guided Backdoor Mitigation for Pre-trained Encoders](https://mlsanity.com/paper/2406.03508/) (2024)
- [Reducing Certified Regression to Certified Classification for General Poisoning Attacks](https://mlsanity.com/paper/2208.13904/) (2022)
- [Certifying the Fairness of KNN in the Presence of Dataset Bias](https://mlsanity.com/paper/2307.08722/) (2023)
- [Incompatibility Clustering as a Defense Against Backdoor Poisoning Attacks](https://mlsanity.com/paper/2105.03692/) (2021)

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