  Despite a large amount of attention on adversarial examples, very few works
have demonstrated an effective defense against this threat. We examine Deep
k-Nearest Neighbor (DkNN), a proposed defense that combines k-Nearest Neighbor
(kNN) and deep learning to improve the model's robustness to adversarial
examples. It is challenging to evaluate the robustness of this scheme due to a
lack of efficient algorithm for attacking kNN classifiers with large k and
high-dimensional data. We propose a heuristic attack that allows us to use
gradient descent to find adversarial examples for kNN classifiers, and then
apply it to attack the DkNN defense as well. Results suggest that our attack is
moderately stronger than any naive attack on kNN and significantly outperforms
other attacks on DkNN.
