Training-Time Attacks against k-Nearest Neighbors
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 ($k$NN). We prove that computing an optimal training-time (a.k.a. poisoning) attack against $k$NN 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 $k$NN is vulnerable in practice and that dimensionality reduction is an effective defense. We conclude with a discussion of open problems illuminated by our analysis.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationDimensionality ReductionSimilar Papers 제목 키워드 기반
Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks
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 incorrec…
Data PoisoningDetecting 5G Narrowband Jammers with CNN, k-nearest Neighbors, and Support Vector Machines
5G cellular networks are particularly vulnerable against narrowband jammers that target specific control sub-channels in the radio signal. One mitigation approach is to detect such jamming attacks with an online observat…
Binary ClassificationClassificationPL-kNN: A Parameterless Nearest Neighbors Classifier
Demands for minimum parameter setup in machine learning models are desirable to avoid time-consuming optimization processes. The $k$-Nearest Neighbors is one of the most effective and straightforward models employed in n…
Stronger Data Poisoning Attacks Break Data Sanitization Defenses
Machine learning models trained on data from the outside world can be corrupted by data poisoning attacks that inject malicious points into the models' training sets. A common defense against these attacks is data saniti…
Data PoisoningSentiment AnalysisSentiment ClassificationSpam detectionImproving classifier decision boundaries using nearest neighbors
Neural networks are not learning optimal decision boundaries. We show that decision boundaries are situated in areas of low training data density. They are impacted by few training samples which can easily lead to overfi…