论文标题
对K-Nearest邻居的训练时间攻击
Training-Time Attacks against k-Nearest Neighbors
论文作者
论文摘要
最近的基于邻居的方法通常用于分类任务，作为其他数据分析方法的子例程。具有将自己的数据点插入训练集的攻击者可以操纵推断的最近的邻居结构。我们将此目标提取到对$ k $ neart最邻居分类（$ k $ nn）进行训练集数据插入攻击的任务。我们证明，计算对$ k $ nn分类的最佳训练时间（又称中毒）攻击是NP-HARD，即使$ k = 1 $，并且攻击者只能插入一个数据点。我们提供任何时间算法来执行此类攻击，以及一般$ K $和攻击者预算的贪婪算法。我们提供理论界限，并从经验上证明我们方法对合成和现实数据集的有效性和实用性。从经验上讲，我们发现$ k $ nn在实践中很容易受到伤害，而降低维度是有效的防御。最后，我们讨论了我们的分析阐明的开放问题。
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.
