Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work considers an important problem of generating adversarial examples to attack a black-box model. The paper proposes a new approach to consider an adversarial example as a result of a sequence of pixel changes from a benign instance. Therefore, the adversarial generation problem can be considered as a bandit problem, and thus we can leverage Bayesian optimization to search for an instance that maximize the changes on the loss function through a sequence of pixel changes. The evaluation is comprehensive, and demonstrates that fewer number of black-box queries are needed to achieve a higher attack success rate.

I pretty much enjoy this work. The only concern is that I'm not so sure why the speed of CorrAttack is much faster than BayesOpt and Bayes-Attack. It seems that the main reason is because the work defines a block structure (as in Sec 4.1), so that the number of blocks is much smaller than the number of raw pixels. Such a hierarchical structure can naturally lead to a hierarchical search procedure as discussed in Sec 4.3. Is this the main reason why speed is fast? Such an idea doesn't seem to be unique to the bandit setup, is a similar idea also applicable to previous work such as BayesOpt and Bayes-Attack? I hope such an issue can be discussed more in the revision.
review_title: Nice work on the path toward black-box adversarial attacks

final_score: rating: 6: Marginally above acceptance threshold
review_content: **Summary:**
The paper proposes a new approach for generating black-box adversarial attacks based on slowly-varying contextual bandits. The proposed approach achieved query efficiency and success rate which are not too far away from the current state of the art.

**Pros:**
- High query efficiency and success rate (although not state-of-the-art, see Cons below).
- Better runtime than other Bayesian optimization methods (but it’s unclear to me how effective the Bayesian optimization approach is in the first place, see Cons below).
- The paper is clearly written.

**Cons:**
- My main concern is the list of competitors in Table 1 which does not include [SignHunter (ICLR’20)](https://openreview.net/pdf?id=SygW0TEFwH) or [Square Attack (ECCV’20)](https://arxiv.org/pdf/1912.00049.pdf). In particular, they obtain the following average number of queries for untargeted attacks on ImageNet for eps=0.05 (taken from Table 2 from the [Square Attack paper](https://arxiv.org/pdf/1912.00049.pdf)):
| Method |  VGG | ResNet-50 |
| ------------- |-----------------------:| -----:|
| SignHunter | 95 | 129 |
| Square Attack | **31** | **73** |
| CorrAttack-Flip | 130 | 150 |
- Another related concern that I have is whether the proposed Bayesian optimization approach really helps. CorrAttack-Flip resembles a lot the SignHunter approach which doesn’t rely on taking the optimal action and instead selects actions in some predefined (but to some extent, arbitrary) order. Moreover, updates of SignHunter are similar in spirit: they also suggest to flip eps to -eps and vice versa, although they rely not on squares but on horizontal stripes (due to flattening of the image tensor). Thus, I would be very interested to see an ablation study for the success rate and query efficiency of (1) CorrAttack-Flip vs (2) CorrAttack-Flip with a **random selection of actions**. In other words, does the proposed Bayesian optimization framework really help, and if so, what is the margin? Related to this, there is an ablation study in Table 7 about the importance of PCA features, but the shown improvement is very minor and I am not sure if it’s statistically significant.


**Minor suggestions**
- It would be good to include at least a short discussion why you selected the expected improvement acquisition function and not other alternatives.
- Page 4: “where d is the image pixels” -> “where d is the **number** of image pixels”
- Implementation of the time-varying property: for completeness, it would be also good to provide an ablation study that would justify the choice out of the two alternatives you mentioned.
- All entries in Table 4 are based only on 10 samples. I’m not sure what kind of conclusion we can draw from an comparison which is made only based on 10 samples.

**Score:**
My current score is 4/10 but I would be willing to raise it if my second concern (mentioned in **Cons**) is resolved.

-----

**Update:**
After the rebuttal, I update my score to 6/10 (see the justifications below).

review_title: Interesting modeling approach but some competing approaches are omitted and it's unclear how much Bayesian Optimization really helps

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes to use time-varying contextual bandits in order to improve the query efficiency of score-based adversarial black-box attacks.The effectiveness is demonstrated on various classifiers for ImageNet and compared against several baseline methods.

The improvements over the baseline methods seem significant, although I have one question: in Algorithm 1, what is the actual value for m used in the experiments? The appendix indicates that m=0.03n, however, the value for n isn’t given as far as I can see. This is an important detail because it determines the number of queries that CorrAttack needs to perform upfront. Is it correct that, depending the actual value of m, some of the baseline methods may actually be more efficient than CorrAttack if the attacker only wants to compute a single adversarial example?

Another question: the original ZOO paper (Chen et al., 2017) reports more than 90% attack success rate with a maximum of 1,500 queries per sample against Inception-v3, which is higher success rate and lower number of queries than reported in this paper. Did you use the same hyper parameters as in the original work?

Minor observations:
p.2: “searches over a much limited action space models the reward” -> something is missing here
p.2: “the substitute model requires a lot of training data” -> this is a bit casual
p.2: “the dimension of the embedding space is still in the thousands” -> this depends on the particular model under consideration; suggest to generalise this statement
p.3.: “score-based attack” -> “score-based attacks”
p.4.: last paragraph before Section 4.1: the specific context of images ia introduced a bit abruptly; it will be good to make more clear which parts of the paper apply to classifiers in general, and which ones only to the image domain.
p.4: “d is the image pixels” -> “d is the number of image pixels”
p.4.: “we also find that the” -> “that” should be omitted 
p.5: what is “EI”?
p.8: “find the action the large award” -> something’s missing in this sentence
p.8: last paragraph: what is meant by the “embedding from the transfer-based attack”? The very last sentence about adversarial training doesn’t make much sense to me; in particular, defending against white-box attacks should also work against CorrAttack; on the other hand, the objective of adversarial training usually isn’t to defend just against one specific attack, but to make the model robust against worst-case examples within e.g. an l-p-ball, regardless of what attack algorithm may be used to construct such examples.

review_title: Improves over existing methods in terms of query efficiency - not clear to me yet by how much

final_score: rating: 6: Marginally above acceptance threshold
review_content: 




This paper proposes a new black-box attack that assumes access to loss-oracle of the target model. The attack exploits temporal and spatial correlation of block-wise pixel perturbations in a Bayesian optimization framework to achieve query efficiency.

Pros:
- Overall, I enjoyed reading this paper. It is one of the few papers that employ scalable GP regression in black-box attacks. It also provides a novel formulation of how the action space of perturbation should be searched by optimizing a surrogate reward function over a low-dimensional space comprising image block location and a PCA-based feature.
- The proposition combines several aspects of different attacks from the literature in one framework: sign flips, Bayesian optimization, hierarchical blocking, and exploitation of temporal- and spatial-correlation in natural images.

Cons:
- I have highlighted my remarks below and hope the authors address them.



Comments/Questions:
- Fig 1: I appreciate the authors' attempt to motivate contextual bandits and slow varying property, but making this conclusion based on one image of one dataset (ImageNet) and one architecture (ResNet50) is not sufficient. Is this observation consistent over *multiple* images of *multiple* datasets and across *multiple* architectures?
- Table 1: NAttack achieves 100% on VGG16 and DenseNet. It is not highlighted in bold.
- Table 3: query limit "1000" -> "10,000"?
- Page 2, Paragraph 2: What is the distinction between BayesOpt and Bayes-Attack. Most of the discussion is around BayesOpt.
- Page 2, Sec 2, Paragraph 2: Reference of AutoZOOM is missing.
- Page 2, Sec 2: The context in which NES and CMA-ES are presented gives the impression that they are adversarial attacks, please rephrase to indicate they are gradient-free optimization techniques.
- Eq. 9 : the notation is not clear. Is $e_{ijk}$ of the same dimensionality as $\nabla_{x_t}l(x_t,y)$?. The definition of $e_{ijk}$ does not imply that.
- It seems that most of the computational gains that CorrAttack has over BayeOpt and BayesAttack is due to the use of **scalable** GP regression (GPytorch) - not to mention the low-dimensionality of its GP. To highlight the benefits of the other aspects of CorrAttack, I think all (BayesOpt, BayesAttack, and CorrAttack) should employ the same GP tool
- Fig 3: Are the rewards across different block sizes comparable? If so, the plot suggests that using smaller blocks yields **faster** convergence to **better** rewards which in turn does not justify the hierarchical bayesian optimization search of Sec 4.3.  
- PCA formulation: please elaborate on how PCA is employed to compute a single feature per block. In particular, is PCA performed for each block (pixel-level PCA) or over all the pixels of the image?
- Just as the authors compared the Bayesian aspect of the attack to Bayesian attacks (BayesOpt, Bayes-Attack), it would have been great if the authors could contrast the "flip" aspect of the attack with flip-based attacks---e.g., SignHunter & SIMBA ---that the authors mention in Sec 2.
- Ablation Studies: I appreciate the study but I think it lacks supporting evidence of "hierarchical vs non-hierarchical attack" and "small (one-pixel) block vs 32-pixel block"
review_title: A black-box attack combining many aspects of previous attacks in one framework. Some experimental revisions are needed.

Meta-review: The paper presents a new Bayesian optimization method based on the Gaussian process bandits framework for black-box adversarial attacks. The method achieves good performance in the experiments, which was appreciated by all the reviewers.

At the same time, the presentation of the method is quite confusing, which currently precludes acceptance of the paper. In particular, during the discussion phase the reviewers were not able to decipher the algorithm based on the description presented in the paper. It is not clear how the problem is modeled as a bandit problem, what the loss function $\ell$ is minimized and why minimizing it makes sense (assuming, e.g., that $\ell$ it the hinge loss as suggested and the initial prediction is good with a large margin, that is, the loss is zero, equation 6 never changes $x_t$ when the procedure is started from $x$). This connection, since it is the fundamental contribution of the paper, should be much better explained. Once the problem is set up to estimate (maximize?) the reward, it is changed to calculating the difference in the minimization (cf. equation 11), which is again unmotivated. (Other standard aspects of the algorithm should also be explained properly, e.g., the stopping condition of Algorithm 1)

Unfortunately, the paper is written in a mathematically very imprecise manner. As an example, consider equation (6), where $B_p$ and the projection operator are not defined, and while these can be guessed, a projection of the argmin seems to be missing as well in the end (otherwise nothing guarantees that $x_T$, which is the final outcome of the algorithm, remains in the $L_p$ ball). Another example is the $Discrete\ Approximate\ CorrAttack_{Flip}$ paragraph which requires that every coordinate of $x$ should be changed by  $\pm\epsilon$. It is also not clear what "dividing the image into several blocks" means in Section 4.1 (e.g., are these overlapping, do they cover the whole image, etc., not to mention that previously $x$ was a general input, not necessarily an image). It is also unlikely that the stopping condition in Algorithm 1 would use the exact same $\epsilon$ for the acquisition function as the perturbation radius for adversarial examples, etc. While some of these inaccuracies and unclear definitions are also mentioned in the reviews, unfortunately there are more in the paper.

The authors are encouraged to resubmit the paper to the next venue after significantly improving and cleaning up the presentation.


Decision: Reject