# Systematic Testing of the Data-Poisoning Robustness of KNN

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 27 of its 64 references that are in the map.
- First posted on arXiv 17 Jul 2023.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

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

- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [Stronger Data Poisoning Attacks Break Data Sanitization Defenses](https://mlsanity.com/paper/1811.00741/) (2018)
- [Transferable Clean-Label Poisoning Attacks on Deep Neural Nets](https://mlsanity.com/paper/1905.05897/) (2019)
- [RAB: Provable Robustness Against Backdoor Attacks](https://mlsanity.com/paper/2003.08904/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Is feature selection secure against training data poisoning?](https://mlsanity.com/paper/1804.07933/) (2018)
- [Technical Report: When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attacks](https://mlsanity.com/paper/1803.06975/) (2018)
- [Data Poisoning against Differentially-Private Learners: Attacks and Defenses](https://mlsanity.com/paper/1903.09860/) (2019)
- [Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2012.03765/) (2020)
- [Deep k-NN for Noisy Labels](https://mlsanity.com/paper/2004.12289/) (2020)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [ReluDiff: Differential Verification of Deep Neural Networks](https://mlsanity.com/paper/2001.03662/) (2020)
- [NeuroDiff: Scalable Differential Verification of Neural Networks using Fine-Grained Approximation](https://mlsanity.com/paper/2009.09943/) (2020)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [Support Vector Machines under Adversarial Label Contamination](https://mlsanity.com/paper/2206.00352/) (2022)
- [Poisoning Behavioral Malware Clustering](https://mlsanity.com/paper/1811.09985/) (2018)
- [DiffRNN: Differential Verification of Recurrent Neural Networks](https://mlsanity.com/paper/2007.10135/) (2020)
- [Modular Verification of Interrupt-Driven Software](https://mlsanity.com/paper/1709.10078/) (2017)
- [Certifying Data-Bias Robustness in Linear Regression](https://mlsanity.com/paper/2206.03575/) (2022)
- [Flow-Sensitive Composition of Thread-Modular Abstract Interpretation](https://mlsanity.com/paper/1709.10116/) (2017)
- [Abstract Interpretation under Speculative Execution](https://mlsanity.com/paper/1904.11170/) (2019)

## Built on by (most cited first, 1 of 1)

- [Emotionally Numb or Empathetic? Evaluating How LLMs Feel Using EmotionBench](https://mlsanity.com/paper/2308.03656/) (2023)

## Abstract (arXiv)

Data poisoning aims to compromise a machine learning based software component by contaminating its training set to change its prediction results for test inputs. Existing methods for deciding data-poisoning robustness have either poor accuracy or long running time and, more importantly, they can only certify some of the truly-robust cases, but remain inconclusive when certification fails. In other words, they cannot falsify the truly-non-robust cases. To overcome this limitation, we propose a systematic testing based method, which can falsify as well as certify data-poisoning robustness for a widely used supervised-learning technique named k-nearest neighbors (KNN). Our method is faster and more accurate than the baseline enumeration method, due to a novel over-approximate analysis in the abstract domain, to quickly narrow down the search space, and systematic testing in the concrete domain, to find the actual violations. We have evaluated our method on a set of supervised-learning datasets. Our results show that the method significantly outperforms state-of-the-art techniques, and can decide data-poisoning robustness of KNN prediction results for most of the test inputs.