Minimum-Norm Adversarial Examples on KNN and KNN-Based Models
This work addresses the robustness evaluation challenge for kNN-based models, which is incremental as it builds on prior attacks to provide a more efficient baseline.
The authors tackled the problem of evaluating robustness against adversarial examples for kNN classifiers and kNN-based models by proposing a gradient-based attack that outperforms existing methods with minimal computational overhead, achieving faster runtimes and improved performance on all tested models.
We study the robustness against adversarial examples of kNN classifiers and classifiers that combine kNN with neural networks. The main difficulty lies in the fact that finding an optimal attack on kNN is intractable for typical datasets. In this work, we propose a gradient-based attack on kNN and kNN-based defenses, inspired by the previous work by Sitawarin & Wagner [1]. We demonstrate that our attack outperforms their method on all of the models we tested with only a minimal increase in the computation time. The attack also beats the state-of-the-art attack [2] on kNN when k > 1 using less than 1% of its running time. We hope that this attack can be used as a new baseline for evaluating the robustness of kNN and its variants.