Defending Against Adversarial Examples with K-Nearest Neighbor

Chawin SitawarinarXiv 2019 · arXiv

TL;DR

This paper proposes a novel defense against adversarial examples in neural networks by leveraging k-Nearest Neighbors (kNN) on intermediate network representations. This approach significantly improves robustness on standard datasets like MNIST and CIFAR-10, outperforming existing state-of-the-art methods, and also offers a path towards certifiable defenses.

What Problem Does This Paper Address?

Deep neural networks have achieved remarkable success across various domains, but they are notoriously vulnerable to adversarial examples. These are subtly perturbed inputs, imperceptible to humans, that can cause models to misclassify them with high confidence. While many defenses exist, they often involve complex architectural changes or training procedures, sometimes at the cost of significant accuracy degradation on clean data. The paper aims to find a more effective and potentially simpler way to defend against these attacks, particularly focusing on the $l_2$-norm perturbation setting.

Methods

The core idea is to move beyond traditional defenses that operate on the input space or the final output layer. Instead, the authors propose using a kNN classifier on the intermediate representations learned by a neural network.

Here's a breakdown of their approach:

  • Feature Extraction: A pre-trained neural network (acting as a feature extractor) transforms the input data into a higher-level representation.
  • kNN Classification: A kNN classifier is then applied to these extracted features, using the training data's representations as a reference. The classification is based on the majority vote of the k nearest neighbors in the representation space.
  • Heuristic Defense: This forms the primary defense mechanism. By performing the kNN search in a lower-dimensional, more abstract feature space, the defense aims to be more robust to small perturbations that might drastically alter the input space.
  • Certifiable Defense: A more rigorous defense is proposed using a 1-NN classifier on representations from a Lipschitz network. Lipschitz networks have a bounded output change for a bounded input change, which allows for mathematically proving a lower bound on the perturbation size required to change a classification. This provides a formal guarantee of robustness.

The authors explore various network architectures and training objectives (supervised, unsupervised, adversarial training) as feature extractors to find representations that are most amenable to this kNN-based defense.

Datasets

  • MNIST: Used extensively for training and evaluating both the heuristic and certifiable defenses.
  • CIFAR-10: Used to demonstrate the effectiveness of the approach on a more complex dataset.

The paper does not introduce new datasets but evaluates its methods on these standard benchmarks.

Key Insights and Ideas

  • kNN on Representations is Powerful: The most striking insight is that kNN, when applied to intermediate neural network representations rather than raw inputs, can be a surprisingly effective defense against adversarial examples. This suggests that the learned features themselves can be made more robust.
  • Bridging the Robustness-Accuracy Trade-off: The kNN approach appears to offer a better trade-off between adversarial robustness and clean accuracy compared to many existing methods. It can sometimes even improve accuracy while increasing robustness, especially when combined with adversarial training.
  • Unsupervised Features Can Be Robust: The paper shows that representations learned through unsupervised methods (like autoencoders and VAEs) can also yield robust kNN classifiers, suggesting that robustness isn't solely dependent on supervised labels.
  • Certifiable Defense with 1-NN: The development of a certifiable defense using 1-NN on Lipschitz networks provides a formal guarantee of robustness, which is a significant step beyond heuristic defenses.
  • Representation Choice Matters: The choice of network architecture and training objective significantly impacts the effectiveness of the kNN defense, highlighting the importance of learning good representations.

Key Results

  • MNIST Performance: The proposed kNN defense significantly surpasses state-of-the-art defenses on MNIST against $l_2$-perturbations. For example, their best model required an average perturbation norm of 3.07 to fool the classifier, outperforming the previous best by 0.77 with only a modest drop in clean accuracy.
  • CIFAR-10 Performance: The method also shows strong results on CIFAR-10, increasing the mean adversarial perturbation to 2.30.
  • Certifiable Defense Bounds: Their certifiable defense can guarantee that for 80% of test samples, classification cannot be changed by an $l_2$-perturbation of 0.5 or less. This bound is comparable to other schemes.
  • Adversarial Training Synergy: Combining adversarial training with the kNN defense further boosts robustness, often with better accuracy than adversarial training alone.

Limitations and Future Work

  • Scalability of kNN: While the paper uses efficient libraries like Faiss, exact kNN search can still be computationally intensive for very large datasets or very high-dimensional representations.
  • Certifiable Defense Bound Tightness: The authors acknowledge that the bound for their certifiable defense is a "naive lower bound" and could be improved. The case for $k > 1$ in the certifiable defense is also left as future work due to complexity.
  • Lipschitz Network Construction: Developing better Lipschitz and $l_2$-norm preserving networks is crucial for scaling the certifiable defense to larger datasets.
  • Attack Limitations: The paper notes that for some adversarially trained models ($l_\infty$-Adv), their gradient-based attack struggles due to gradient obfuscation, requiring a boundary-based attack for evaluation.
  • Representation Learning: The authors suggest that learning representations that explicitly encourage small local intrinsic dimension (LID) and low sensitivity could further enhance robustness.

Overall, this paper presents a compelling and practical approach to defending neural networks against adversarial attacks, offering both strong heuristic defenses and a promising path towards formal guarantees.

Summary updated

Abstract

Robustness is an increasingly important property of machine learning models as they become more and more prevalent. We propose a defense against adversarial examples based on a k-nearest neighbor (kNN) on the intermediate activation of neural networks. Our scheme surpasses state-of-the-art defenses on MNIST and CIFAR-10 against l2-perturbation by a significant margin. With our models, the mean perturbation norm required to fool our MNIST model is 3.07 and 2.30 on CIFAR-10. Additionally, we propose a simple certifiable lower bound on the l2-norm of the adversarial perturbation using a more specific version of our scheme, a 1-NN on representations learned by a Lipschitz network. Our model provides a nontrivial average lower bound of the perturbation norm, comparable to other schemes on MNIST with similar clean accuracy.
BibTeX
@misc{sitawarin2019defending,
  author = {Chawin Sitawarin},
  title = {{Defending Against Adversarial Examples with K-Nearest Neighbor}},
  year = {2019},
  eprint = {1906.09525},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.09525},
}
Figure