# Training-Time Attacks against k-Nearest Neighbors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 15 Aug 2022.

## Builds on (most cited first, 7 of 7)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [Data Poisoning Attacks on Factorization-Based Collaborative Filtering](https://mlsanity.com/paper/1608.08182/) (2016)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [When are Non-Parametric Methods Robust?](https://mlsanity.com/paper/2003.06121/) (2020)
- [Data Poisoning Attacks on Neighborhood-based Recommender Systems](https://mlsanity.com/paper/1912.04109/) (2019)

## Abstract (arXiv)

Nearest neighbor-based methods are commonly used for classification tasks and as subroutines of other data-analysis methods. An attacker with the capability of inserting their own data points into the training set can manipulate the inferred nearest neighbor structure. We distill this goal to the task of performing a training-set data insertion attack against k-Nearest Neighbor classification (kNN). We prove that computing an optimal training-time (a.k.a. poisoning) attack against kNN classification is NP-Hard, even when k = 1 and the attacker can insert only a single data point. We provide an anytime algorithm to perform such an attack, and a greedy algorithm for general k and attacker budget. We provide theoretical bounds and empirically demonstrate the effectiveness and practicality of our methods on synthetic and real-world datasets. Empirically, we find that kNN is vulnerable in practice and that dimensionality reduction is an effective defense. We conclude with a discussion of open problems illuminated by our analysis.