Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposed a DFO framework to generate black-box adversarial examples. By comparing with Parsimonious and Bandits, the proposed approach achieves lower query complexity and higher attack success rate (ASR).

I have two main concerns about the current version:

1)  Some important baselines might be missing. In addition to (Ilyas et al., 2018b) and (Moon et al., 2019), the methods built on zeroth-order optimization (namely, gradient estimation via function differences) were not compared. Examples include 
[1] There are No Bit Parts for Sign Bits in Black-Box Attacks
[2] AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks
[3] SIGNSGD VIA ZEROTH-ORDER ORACLE
 
2) In addition to attack success rate and query complexity, it might be useful to compare different attacks in terms of $\ell_p$ distortion, where $p \neq \infty$. This could provide a clearer picture on whether or not the query efficiency and the attack performance are at the cost of increasing the $\ell_1$ and $\ell_2$ distortion significantly.


########### Post-feedback ##############
Thanks for the response and the additional experiments to address my first question.  However, I am not satisfied with the response "But clearly our methods aim to reach the boundary of linf ball, so the distortion might be large" to the second question.

I am Okay with the design of $\ell_\infty$ attack. However, if the reduction in query complexity is at a large cost of perturbation power, e.g., measured by $\ell_2$ norm, then it is better to demonstrate this tradeoff. Furthermore, if the $\ell_2$ norm is constrained, will the proposed $\ell_\infty$ attack outperform the others? This is also not clear to me.

Thus, I decide to keep my score. 
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proposes a black box adversarial attacks to deep neural networks. The proposed approaches consist of tiling technique proposed by Ilyas et al (2018) and derivative free approaches. The proposed approaches have been applied to targeted and untargeted adversarial attacks against modern neural network architectures such as VGG16, ResNet50, and InceptionV3 trained on ImageNet and CIFAR10 datasets. Experimental results show higher attack success rate with a smaller number of queries. 

The experimental results look quite promising, i.e., revealing the vulnerability of the deep neural network against black-box adversarial attacks. A possible weakness in the experimental design is that the authors haven't apply any defense methodology to the classification models to be attacked. Yet the results are promising. 

From the viewpoint of technical soundness, the approach is a simple combination of the existing approaches. The tiling technique is used in Ilyas et al (2018) combined with a bandit approach. The current paper simply replaces the bandit with evolution strategies. The introduction of the evolution strategies is motivated by their good performance as a zeroth order optimization algorithm. 

A small novelty appears in a way to handle a bounded search space. The authors claim that many DFO algorithms are designed for unbounded real search space and need some constraint handling. The authors proposed two ways of transforming the bounded search space to the unbounded real search space. However, there must be existing approaches for this type fo constraint (rectangle constraint) in DFO settings. I can not list such approaches here as there are huge number of papers addressing the constraint of this type. There is not enough discussion in the paper why these two proposed approaches are promising. Formulation (2) makes the problem ill-posed and technically the optimal point may not exist. Formulation (3) with softmax representation makes the optimization problem noisy, hence it may annoy the optimizer. Nonetheless, I believe the combination of these constraint handling technique and evolutionary approaches are not new.

Some minor comments / questions below:

P5: How are the original images to be attacked selected for Fig 2? 

P6:  "we highlight that neural neural networks are not robust to l∞ tiled random noise. " Isn't it the contribution of (Ilyas et al., 2018b)? 

P7: What are the number of queries in Figure 3 and Table 1? Are they the number of queries spent until these algorithms found an adversarial example which is categorized to a wrong class for the first time?
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper proposed a new query efficient black-box attack algorithm using better evolution strategies. The authors also add tiling trick to make the attack even more efficient. The experimental results show that the proposed method achieves state-of-the-art attack efficiency in black-box setting.

The paper indeed presented slightly better results than the current state-of-the-art black-box attacks. It is clearly written and easy to follow, however, the paper itself does not bring much insightful information. 

The major components of the proposed method are two things: using better evolution strategies and using tiling trick. The tiling trick is not something new, it is introduced in (Ilyas et al., 2018) and also discussed in (Moon et al., 2019). The authors further empirically studied the best choice of tiling size. I appreciated that, but will not count it as a major contribution. In terms of better evolution strategies, the authors show that (1+1) and CMA-EA can achieve better attack result but it lacks intuition/explanations why these helps, what is the difference. It would be best if the authors could provide some theories to show the advantages of the proposed method, if not, at least the authors should give more intuition/explanation/demonstrative experiments to show the advantages.

Detailed comments:
- In section 3.2, is the form of the discretized problem a standard way to transform from continuous to discrete one? What is the intuition of using a and b? Have you considered using only one variable to do it?
- In section 3.3.2 what do you mean by “with or without softmax, the optimum is at infinity”? I hope the authors could further explain it.
- In eq (2), do you mean  max_{\tau} L(f(x + \epsilon tanh(\tau)), y) ?
- In section 3.3.1, the authors said (1+1)-ES and CMA-ES can be seen as an instantiation of NES. Can the authors further elaborate on this?
- Can the authors provide algorithm for DiagonalCMA?
- It is better to put the evolution strategy algorithms in the main paper and discuss it. 
- Can the authors also comment/compare the results with the following relevant paper?
Li, Yandong, et al. "NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks." ICML 2019.
Chen, Jinghui, Jinfeng Yi, and Quanquan Gu. "A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks." arXiv preprint arXiv:1811.10828 (2018).

-  In Table 1, why for Parsimonious and Bandit methods, # of tiles parts are missing? I think both of the baselines use tilting trick? And they should also run using the optimal tiling size? The result seems directly copied from the Parsimonious paper? It makes more sense to rerun it in your setting and environment cause the sampled data points may not be the same. Since CMA costs significantly more time, it makes a fair comparison to also report the attack time needed for each method.

- In Table 3, why did not compare with Bandit and Parsimonious attacks? 

======================
after the rebuttal

I thank the authors for their response but I still feel that there is a lot more to improve for this paper in terms of intuition and experiments. Therefore I decided to keep my score unchanged.  

review_title: Official Blind Review #3

Meta-review: This paper proposes a new black-box adversarial attack based on tiling and evolution strategies. While the experimental results look promising, the main concern of the reviewers is the novelty of the proposed algorithm, and many things need to be improved in terms of clarity and experiments. The paper does not gather sufficient support from the reviewers even after author response. I encourage the authors to improve this paper and resubmit to future conference.
Decision: Reject