Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The authors consider new attacks for generating adversarial samples against neural networks. In particular, they are interested in approximating gradient-based white-box attacks such as FGSM in a black-box setting by estimating gradients from queries to the classifier. They assume that the attacker is able to query, for any example x, the vector of probabilities p(x) corresponding to each class.

Given such query access it’s trivial to estimate the gradients of p using finite differences. As a consequence one can implement FGSM using these estimates assuming cross-entropy loss, as well as a logit-based loss. They consider both iterative and single-step FGSM attacks in the targeted (i.e. the adversary’s goal is to switch the example’s label to a specific alternative label) and un-targeted settings (any mislabelling is a success). They compare themselves to transfer black-box attacks, where the adversary trains a proxy model and generates the adversarial sample by running a white-box attack on that model.  For a number of target classifiers on both MNIST and CIFAR-10, they show that these attacks outperform the transfer-based attacks, and are comparable to white-box attacks, while maintaining low distortion on the attack samples. 

One drawback of estimating gradients using finite differences is that the number of queries required scales with the dimensionality of the examples, which can be prohibitive in the case of images. They therefore describe two practical approaches for query reduction — one based on random feature grouping, and the other on PCA (which requires access to training data). They once again demonstrate the effectiveness of these methods across a number of models and datasets, including models deploying adversarially trained defenses. 

Finally, they demonstrate compelling real-world deployment against Clarifai classification models designed to flag “Not Safe for Work” content. 

Overall, the paper provides a very thorough experimental examination of a practical black-box attack that can be deployed against real-world systems. While there are some similarities with Chen et al. with respect to utilizing finite-differences to estimate gradients, I believe the work is still valuable for its very thorough experimental verification, as well as the practicality of their methods. The authors may want to be more explicit about their claim in the Related Work section that the running time of their attack is “40x” less than that of Chen et al. While this is believable, there is no running time comparison in the body of the paper. 
review_title: A very thorough empirical examination of practical black-box attacks on NN classifiers. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
Quality: The paper studies an important problem given that public ML APIs are now becoming available. More specifically, the authors study black-box attacks based on gradient estimation. This means that adversaries have no access to the underlying model.

Clarity: The paper is clear and well-written. Some parts are a bit redundant, so more space of the main body of the paper could be devoted information provided in the appendix and would help with the flow (e.g., description of the models A, B, C; logit-based loss; etc.). This would also provide room for discussing the targeted attacks and the tranferability-based attacks.

Originality: While black-box attacks are of greater interest than withe-box attacks, I found the case considered here of modest interest. The assumption that the loss would be known, but not the gradient is relatively narrow. And why is not possible to compute the gradient exactly in this case? Also, it was not clear what how \delta can be chosen in practice to increase the performance of the attack. Could the authors comment on that?

Significance: The results in the paper are encouraging, but it is not clear whether the setting is realistic. The main weakness of this paper is that it does not state the assumptions made and under which conditions these attacks are valid. Those have to be deduced from the main text and not all are clear and many questions remain, making it difficult to see when such an attack is a risk and what is the actual experimental set-up. For example, what does it mean that attackers have access to the training set and when does that occur? Is it assumed that the API uses the adversarial example for training as well or not? How are the surrogate models trained and what are they trying to optimize and/or what do they match? In which situations do attackers have access to the loss, but not the gradient? How sensitive are the results to a loss mismatch? Finally, I do not understand the performance metric proposed by the authors. It is always possible to get an arbitrarily high success rate unless one fixes the distortion. What would be the success rate if the distortion was equal to the distortion of white-box attacks?  And how sensitive are the results to \epsilon (and how can it be chosen by an attacker in practice)?

review_title: About assumptions and metrics

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper generates adversarial examples using the fast gradient sign (FGS) and iterated fast gradient sign (IFGS) methods, but replacing the gradient computation with finite differences or another gradient approximation method. Since finite differences is expensive in high dimensions, the authors propose using directional derivatives based on random feature groupings or PCA. 

This paper would be much stronger if it surveyed a wider variety of gradient-free optimization methods. Notably, there's two important black-box optimization baselines that were not included: simultaneous perturbation stochastic approximation ( https://en.wikipedia.org/wiki/Simultaneous_perturbation_stochastic_approximation), which avoids computing the gradient explicitly, and evolutionary strategies ( https://blog.openai.com/evolution-strategies/ ), a similar method that uses several random directions to estimate a better descent direction.

The gradient approximation methods proposed in this paper may or may not be better than SPSA or ES. Without a direct comparison, it's hard to know.  Thus, the main contribution of this paper is in demonstrating that gradient approximation methods are sufficient for generating good adversarial attacks and applying those attacks to Clarifai models. That's interesting and useful to know, but is still a relatively small contribution, making this paper borderline. I lean towards rejection, since the paper proposes new methods without comparing to or even mentioning well-known alternatives.

REVISION: Thank you for your response! The additional material does strengthen the paper. There is now some discussion of how Chen et al. differs, and an explicit comparison to SPSA and PSO. I think there are some interesting results here, including attacks on Clarifai. However, the additional evaluations are not thorough. This is understandable (given the limited time frame), but unfortunate. SPSA is only evaluated on MNIST, and while the paper claims its distortion is greater, this is never shown explicitly (or was too difficult for me to find, even when searching through the revised paper). Chen et al. is only compared in terms of time, not on success rate, distortion, or number of queries. These timing results aren't necessarily comparable, since the experiments were done under different conditions. Overall, the new experiments and discussion are a step towards a thorough analysis of zero-order attacks, but they're not there yet. I've increased my rating from 4 to 5, but this is still below the bar for me.
review_title: Empirical study of standard adversarial attacks + basic gradient approximation methods

Meta-review: The paper explores an increasingly important questions, especially showing the attack on existing APIs. The update to the paper has also improved it, but the paper is still not yet as impactful as it could be and needs much more comprehensive analysis to correctly appreciate its benefits and role.
Decision: Reject