DECISION-BASED ADVERSARIAL ATTACKS: RELIABLE ATTACKS AGAINST BLACK-BOX MACHINE LEARNING MODELS
Many machine learning algorithms are vulnerable to almost imperceptible perturbations of their inputs. So far it was unclear how much risk adversarial perturbations carry for the safety of real-world machine learning applications because most methods used to generate such perturbations rely either on detailed model information (gradient-based attacks) or on confidence scores such as class probabilities (score-based attacks), neither of which are available in most real-world scenarios. In many such cases one currently needs to retreat to transfer-based attacks which rely on cumbersome substitute models, need access to the training data and can be defended against. Here we emphasise the importance of attacks which solely rely on the final model decision. Such decision-based attacks are (1) applicable to real-world black-box models such as autonomous cars, (2) need less knowledge and are easier to apply than transfer-based attacks and (3) are more robust to simple defences than gradient-or score-based attacks. Previous attacks in this category were limited to simple models or simple datasets. Here we introduce the Boundary Attack, a decision-based attack that starts from a large adversarial perturbation and then seeks to reduce the perturbation while staying adversarial. The attack is conceptually simple, requires close to no hyperparameter tuning, does not rely on substitute models and is competitive with the best gradient-based attacks in standard computer vision tasks like ImageNet. We apply the attack on two black-box algorithms from Clarifai.com. The Boundary Attack in particular and the class of decision-based attacks in general open new avenues to study the robustness of machine learning models and raise new questions regarding the safety of deployed machine learning systems. An implementation of the attack is available as part of Foolbox (https://github.com/bethgelab/foolbox).
This is a nice paper proposing a simple but effective heuristic for generating adversarial examples from class labels with no gradient information or class probabilities. Highly relevant prior work was overlooked and there is no theoretical analysis, but I think this paper still makes a valuable contribution worth sharing with a broader audience.
What this paper does well:
- Suggests a type of attack that hasn't been applied to image classifiers
- Proposes a simple heuristic method for performing this attack
- Evaluates the attack on both benchmark neural networks and a commercial system 
Problems and limitations:
1. No theoretical analysis. Under what conditions does the boundary attack succeed or fail? What geometry of the classification boundaries is necessary? How likely are those conditions to hold? Can we measure how well they hold on particular networks?
Since there is no theoretically analysis, the evidence for effectiveness is entirely empirical. That weakens the paper and suggests an important area of future work, but I think the empirical evidence is sufficient to show that there's something interesting going. Not a fatal flaw.
2. Poor framing. The paper frames the problem in terms of "machine learning models" in general (beginning with the first line of the abstract), but it only investigates image classification. There's no particular reason to believe that all machine learning algorithms will behave like convolutional neural network image classifiers. Thus, there's an implicit claim of generality that is not supported.
This is a presentation issue that is easily fixed. I suggest changing the title to reflect this, or at least revising the abstract and introduction to make the scope clearer.
A minor presentation quibble/suggestion: "adversarial" is used in this paper to refer to any class that differs from the true class of the instance to be disguised. But an image of a dalmation that's labeled as a dalmation isn't adversarial -- it's just a different image that's labeled correctly. The adversarial process is about constructing something that will be mislabeled, exploiting some kind of weakness that doesn't show up on a natural distribution of inputs. I suggest rewording some of the mentions of adversarial.
3. Ignorance of prior work. Finding deceptive inputs using only the classifier output has been done by Lowd and Meek (KDD 2005) for linear classifiers and Nelson et al. (AISTATS 2010, JMLR 2012) for convex-inducing classifiers. Both works include theoretical bounds on the number of queries required for near-optimal adversarial examples. Biggio et al. (ECML 2013) further propose training a surrogate classifier on similar training data, using the predictions of the target classifier to relabel the training data. In this way, decision information from the target model is used to help train a more similar surrogate, and then attacks can be transferred from the surrogate to the target.
Thus, "decision-based attacks" are not new, although the algorithm and experiments in this paper are. 
Overall, I think this paper makes a worthwhile contribution, but needs to revise the claims to match what's done in the paper and what's been done before.