A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance

By Adi Shamir, Itay Safran, Eyal Ronen, Orr Dunkelman. 2019

97 citations recorded by the source corpus.

The existence of adversarial examples in which an imperceptible change in the input can fool well trained neural networks was experimentally discovered by Szegedy et al in 2013, who called them "Intriguing properties of neural networks". Since then, this topic had become one of the hottest research areas within machine learning, but the ease with which we can switch between any two decisions in targeted attacks is still far from being understood, and in particular it is not clear which parameters determine the number of input coordinates we have to change in order to mislead the network. In this paper we develop a simple mathematical framework which enables us to think about this baffling phenomenon from a fresh perspective, turning it into a natural consequence of the geometry of $\mathbb{R}^n$ with the $L_0$ (Hamming) metric, which can be quantitatively analyzed. In particular, we explain why we should expect to find targeted adversarial examples with Hamming distance of roughly $m$ in arbitrarily deep neural networks which are designed to distinguish between $m$ input classes.

Subfields: Artificial Intelligence, Hardware and Architecture, Safety, Robustness & Interpretability, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Eric P. Xing
2. Haohan Wang
3. Bo Han
4. Gang Niu
5. Pengcheng Yin
6. Masashi Sugiyama
7. Li-zhen Cui
8. Xindi Wu

In Hardware and Architecture

1. Eric P. Xing
2. Masashi Sugiyama

In Safety, Robustness & Interpretability

1. Li-zhen Cui
2. Eric P. Xing
3. Xindi Wu
4. Xilie Xu
5. Mohan Kankanhalli
6. Bo Han
7. Haohan Wang
8. Pengcheng Yin

In Signal Processing

1. Eric P. Xing
2. Haohan Wang
3. Mohan Kankanhalli
4. Pengcheng Yin
5. Gang Niu
6. Masashi Sugiyama
7. Louis-philippe Morency
8. Amir Zadeh

Citations in the corpus

• Attacks Which Do Not Kill Training Make Adversarial Learning Stronger (2020, methodology): “There are also other ways to generate adversarial data, e.g., the fast gradient signed method [20, 10], the CW attack [18] and Hamming distance method [22].”
• High-Frequency Component Helps Explain the Generalization of Convolutional Neural Networks (2019, background): “, 2018), and many more from different model or algorithm perspectives (Kawaguchi et al., 2017; Mahloujifar et al., 2018; Bubeck et al., 2018; Shamir et al., 2019).”