DECISION BOUNDARY ANALYSIS OF ADVERSARIAL EXAMPLES
Deep neural networks (DNNs) are vulnerable to adversarial examples, which are carefully crafted instances aiming to cause prediction errors for DNNs. Recent research on adversarial examples has examined local neighborhoods in the input space of DNN models. However, previous work has limited what regions to consider, focusing either on low-dimensional subspaces or small balls. In this paper, we argue that information from larger neighborhoods, such as from more directions and from greater distances, will better characterize the relationship between adversarial examples and the DNN models. First, we introduce an attack, OPT-MARGIN, which generates adversarial examples robust to small perturbations. These examples successfully evade a defense that only considers a small ball around an input instance. Second, we analyze a larger neighborhood around input instances by looking at properties of surrounding decision boundaries, namely the distances to the boundaries and the adjacent classes. We find that the boundaries around these adversarial examples do not resemble the boundaries around benign examples. Finally, we show that, under scrutiny of the surrounding decision boundaries, our OPTMARGIN examples do not convincingly mimic benign examples. Although our experiments are limited to a few specific attacks, we hope these findings will motivate new, more evasive attacks and ultimately, effective defenses.
Summary of paper:
The authors present a novel attack for generating adversarial examples, deemed OptMargin, in which the authors attack an ensemble of classifiers created by classifying at random L2 small perturbations. They compare this optimization method with two baselines in MNIST and CIFAR, and provide an analysis of the decision boundaries by their adversarial examples, the baselines and non-altered examples. 
Review summary:
I think this paper is interesting. The novelty of the attack is a bit dim, since it seems it's just the straightforward attack against the region cls defense. The authors fail to include the most standard baseline attack, namely FSGM. The authors also miss the most standard defense, training with adversarial examples. As well, the considered attacks are in L2 norm, and the distortion is measured in L2, while the defenses measure distortion in L_\infty (see detailed comments for the significance of this if considering white-box defenses). The provided analysis is insightful, though the authors mostly fail to explain how this analysis could provide further work with means to create new defenses or attacks.
If the authors add FSGM to the batch of experiments (especially section 4.1) and address some of the objections I will consider updating my score.
A more detailed review follows.
Detailed comments:
- I think the novelty of the attack is not very strong. The authors essentially develop an attack targeted to the region cls defense. Designing an attack for a specific defense is very well established in the literature, and the fact that the attack fools this specific defense is not surprising.
- I think the authors should make a claim on whether their proposed attack works only for defenses that are agnostic to the attack (such as PGD or region based), or for defenses that know this is a likely attack (see the following comment as well). If the authors want to make the second claim, training the network with adversarial examples coming from OptMargin is missing.
- The attacks are all based in L2, in the sense that the look for they measure perturbation in an L2 sense (as the paper evaluation does), while the defenses are all L_\infty based (since the region classifier method samples from a hypercube, and PGD uses an L_\infty perturbation limit). This is very problematic if the authors want to make claims about their attack being effective under defenses that know OptMargin is a possible attack.
- The simplest most standard baseline of all (FSGM) is missing. This is important to compare properly with previous work.
- The fact that the attack OptMargin is based in L2 perturbations makes it very susceptible to a defense that backprops through the attack. This and / or the defense of training to adversarial examples is an important experiment to assessing the limitations of the attack. 
- I think the authors rush to conclude that "a small ball around a given input distance can be misleading". Wether balls are in L2 or L_\infty, or another norm makes a big difference in defense and attacks, given that they are only equivalent to a multiplicative factor of sqrt(d) where d is the dimension of the space, and we are dealing with very high dimensional problems. I find the analysis made by the authors to be very simplistic.
- The analysis of section 4.1 is interesting, it was insightful and to the best of my knowledge novel. Again I would ask the authors to make these plots for FSGM. Since FSGM is known to be robust to small random perturbations, I would be surprised that for a majority of random directions, the adversarial examples are brought back to the original class.
- I think a bit more analysis is needed in section 4.2. Do the authors think that this distinguishability can lead to a defense that uses these statistics? If so, how?
- I think the analysis of section 5 is fairly trivial. Distinguishability in high dimensions is an easy problem (as any GAN experiment confirms, see for example Arjovsky & Bottou, ICLR 2017), so it's not surprising or particularly insightful that one can train a classifier to easily recognize the boundaries.
- Will the authors release code to reproduce all their experiments and methods?
Minor comments:
- The justification of why OptStrong is missing from Table2 (last three sentences of 3.3) should be summarized in the caption of table 2 (even just pointing to the text), otherwise a first reader will mistake this for the omission of a baseline.
- I think it's important to state in table 1 what is the amount of distortion noticeable by a human.
=========================================
After the rebuttal I've updated my score, due to the addition of FSGM added as a baseline and a few clarifications. I now understand more the claims of the paper, and their experiments towards them. I still think the novelty, significance of the claims and protocol are still perhaps borderline for publication (though I'm leaning towards acceptance), but I don't have a really high amount of experience in the field of adversarial examples in order to make my review with high confidence.