  K-Nearest Neighbor (kNN)-based deep learning methods have been applied to
many applications due to their simplicity and geometric interpretability.
However, the robustness of kNN-based classification models has not been
thoroughly explored and kNN attack strategies are underdeveloped. In this
paper, we propose an Adversarial Soft kNN (ASK) loss to both design more
effective kNN attack strategies and to develop better defenses against them.
Our ASK loss approach has two advantages. First, ASK loss can better
approximate the kNN's probability of classification error than objectives
proposed in previous works. Second, the ASK loss is interpretable: it preserves
the mutual information between the perturbed input and the in-class-reference
data. We use the ASK loss to generate a novel attack method called the
ASK-Attack (ASK-Atk), which shows superior attack efficiency and accuracy
degradation relative to previous kNN attacks. Based on the ASK-Atk, we then
derive an ASK-\underline{Def}ense (ASK-Def) method that optimizes the
worst-case training loss induced by ASK-Atk. Experiments on CIFAR-10 (ImageNet)
show that (i) ASK-Atk achieves $\geq 13\%$ ($\geq 13\%$) improvement in attack
success rate over previous kNN attacks, and (ii) ASK-Def outperforms the
conventional adversarial training method by $\geq 6.9\%$ ($\geq 3.5\%$) in
terms of robustness improvement.
