Systematic Testing of the Data-Poisoning Robustness of KNN
On the map: LLM safety and security → Backdoor and data poisoning attacks
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.
Key facts. Cited by 1 paper in the map (data through 7 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.
Builds on
27 of 64 references.
References · 27
- 2017Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoningcited by 1,012
- 2018Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networkscited by 500
- 2018Spectral Signatures in Backdoor Attackscited by 457
- 2017Certified Defenses for Data Poisoning Attackscited by 288
- 2018Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learningcited by 219
- 2019Transferable Clean-Label Poisoning Attacks on Deep Neural Netscited by 129
- 2018Stronger Data Poisoning Attacks Break Data Sanitization Defensescited by 125
- 2020RAB: Provable Robustness Against Backdoor Attackscited by 115
- 2020Deep Partition Aggregation: Provable Defense against General Poisoning Attackscited by 112
- 2020Certified Robustness to Label-Flipping Attacks via Randomized Smoothingcited by 103
- 2020Intrinsic Certified Robustness of Bagging against Data Poisoning Attackscited by 90
- 2018Is feature selection secure against training data poisoning?cited by 88
15 more
- 2018Technical Report: When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attackscited by 78
- 2019Data Poisoning against Differentially-Private Learners: Attacks and Defensescited by 75
- 2020Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attackscited by 58
- 2020Deep k-NN for Noisy Labelscited by 55
- 2017Analyzing the Robustness of Nearest Neighbors to Adversarial Examplescited by 36
- 2020ReluDiff: Differential Verification of Deep Neural Networkscited by 29
- 2020NeuroDiff: Scalable Differential Verification of Neural Networks using Fine-Grained Approximationcited by 22
- 2021Certifying Robustness to Programmable Data Bias in Decision Treescited by 21
- 2022Support Vector Machines under Adversarial Label Contaminationcited by 15
- 2018Poisoning Behavioral Malware Clusteringcited by 14
- 2020DiffRNN: Differential Verification of Recurrent Neural Networkscited by 12
- 2017Modular Verification of Interrupt-Driven Softwarecited by 3
- 2022Certifying Data-Bias Robustness in Linear Regressioncited by 3
- 2017Flow-Sensitive Composition of Thread-Modular Abstract Interpretationcited by 2
- 2019Abstract Interpretation under Speculative Executioncited by 2
Built on by
Citing papers per year: 2023: 1.
1 paper.