Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work presents an adversarial attack in the black-box setting where an adversary has access to only logit outputs from the target model. The proposed approach combines the ideas from transfer-based attacks and zeroth-order optimization methods for score-based attack methods. Experiments on multiple architectures show that the proposed approach is query efficient while achieving similar success rates compared to recent approaches.  
main_review: Positives:
1. The proposed approach is simple, effective, and query-efficient.
2. The literature review seems quite thorough and does an especially nice job of covering the related work in this domain. It would be good to discuss some recent Bayesian optimization approaches [1, 2] to make it a complete review.  
3. Experiments are well designed to show the effectiveness of the proposed framework on both untargeted and targeted attacks.
4. The paper is well written and easy to follow.

Concerns:
1. Although the experiments are well-designed, the authors use just one dataset to show the effectiveness of the approach. It would be interesting to see if the proposed approach achieves similar performance on other datasets e.g. CIFAR10.
2. It is hard to compare the performance of different approaches from Table 1 as they all are performing really well. For example, Simba-ODS performance is very close to that of GFCS. How is the value of epsilon been chosen as it significantly affects the performance of Simba-ODS? Is it possible to further tune this parameter to further improve the performance? It would be also interesting to see if the performance difference increase if you decrease the L2 norm bound to 5 which has been used in several prior work. 
3. The authors are missing a comparison to the SOTA method for score-based attacks [3]. it would be also good to compare with Bayes-attack approaches [1, 2] as they show similar properties as the proposed approach, i.e., successfully attack a large fraction of examples 
within a very low number of queries.
4. The authors are also missing a comparison to SOTA optimization-based methods for targeted attacks.
5. I have some concerns with the setting of the experiments. The surrogate models are trained on the same dataset and use the same loss function which is already a lot of information for the adversary to attack the target model. This setting should not be classified as the typical black-box setting.
6. Since the transfer attack using the surrogate models are easy for the setting considered here, it would be an interesting ablation to apply FGSM or PGD attack using the gradient of the surrogate model(s) and compare the attack success rates.
7. Based on the experiment in Section 4.2, the ODS is seldom used for untargeted attacks. The authors should provide ablation experiments such as GFCS - ODS to show the effect of ODS on the attack success rates.

References:
1. Ru, B., Cobb, Blaas, & Gal. (2019). BayesOpt Adversarial Attack. ICLR 2020.
2. Shukla, S. N., Sahu, A. K., Willmott, D., & Kolter, J. Z. (2019). Black-box adversarial attacks with bayesian optimization. arXiv preprint arXiv:1909.13857.
3. Maksym Andriushchenko, Francesco Croce, Nicolas Flam- marion, and Matthias Hein. Square attack: a query-efficient black-box adversarial attack via random search. In ECCV, 2020.
summary_of_the_review: Although there are several good things about the paper because of its simplicity and effectiveness, the authors should provide more experimental evidence to show the effectiveness of the proposed approach. There are also some concerns based on the setting of the experiment (pseudo-black-box setting).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a simple, yet effective adversarial attack in a black box scenario with available surrogates. The attack combines a classic gradient attack via an ensemble of surrogates and an ODS attack. 
main_review: The success of the proposed idea is surprising, while this effect is not explained by the experiments in the paper.
In particular, all attacks considered by the authors as competitors (SimBA++, SimbaODS, LeBA, P-RGF, ODS-RGF) directly assume, that surrogates are not precise enough to replace an initial model. 
So, the evaluation is incomplete. if we don't consider benchmarks that use gradient steps that are taken directly from surrogate models. 
As the authors demonstrate in Figure 3 we require only a small number of coimage steps, while most of the steps are taken directly from a surrogate model (or surrogate models).

The authors provide some explanation in Section 4.4 on why do we need local gradient information.
Common sense and previous work they cite (e.g. P-RGF) also make similar statements.
It would be interesting to consider the correlation between used surrogates and the victim model and quality of attack, as we can easly degrade the quality of a surrogate or maximize discrepancy between a surrogate model and a victim model by incorporating a specific term in the loss function.

The idea of ensembles for the performance improvement seems interesting (also we can try to apply something similar to bandits to select the best surrogate during the optimization?).
summary_of_the_review: The authors suggest an interesting effect but provide a little investigation of it.
The cause of this effect can be some specifics of used pairs surrogate-victim or more general effect related to the correlation of deep learning models trained on large datasets and on general transferability.

As I don't get from the paper, why this phenomenon occurs, I suggest starting a discussion to find out, if it is possible to improve the paper in this aspect. Now, this is the obstacle, that makes the paper below the acceptance threshold.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is devoted to the problem of generating adversarial examples to the predictions of machine learning models. That is, given an instance predicted by a target ML model one way, the paper aims at detecting another instance that is relatively close to the given one but such that the prediction of the model for the new instance is different. The paper proposes a novel adversarial attack algorithm, which behaves as twofold: (1) it tries to apply iterative ascent in the direction of the surrogate's loss gradient until it can and then (2) samples alternative directions from the coimage of the surrogate's local linearisation. The new approach is claimed to be a fast and practical attack as it significantly outperforms the competition in terms of the number of queries needed to generate adversarial examples successfully.
main_review: First of all, I should admit that I am no expert in this area and hence my assessment may be affected by the lack of expertise.

Language-wise the paper seems to be well written. The discussion flow is clear and easy to follow although there are a number of concepts that I am personally not familiar with, and so I believe it would help to define all the notation and the concepts studied (besides the basic definition of an adversarial attack) for a reader like me.

The algorithm proposed is well motivated and described. Related work seems to be properly analysed. Furthermore, although I am not familiar with the standard experimental setup in this area, I should say the results look good to me and the advantage of the proposed algorithm over the state of the art looks convincing.

My understanding is that despite the demonstrated practical efficiency of the proposed solution, it is not guaranteed to successfully find an adversarial example even if such an example exists, due to the limitations of the methods used. I wonder if the authors tried to compare their approach to the approaches based on formal methods for reasoning about the model behaviour. Also, it would help to mention this line of work in the related work.
summary_of_the_review: Overall, I find the paper to offer a solid contribution that may be interesting enough for the community working in the area of black-box adversarial attacks, if accepted to ICLR.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new simple black-box adversarial attack algorithm, which utilizes surrogate models. The algorithm attempts iterative ascent in the direction of the surrogate’s loss gradient, and when the attempt fails, the algorithm searches alternative directions by exploiting the surrogate’s Jacobian’s row space. The experiments show that the proposed algorithm produces very low query counts with low failure rates, compared to existing baselines.
main_review: [Pros]:
* The paper is well-motivated and easy to follow.
* The proposed algorithm is simple but achieves state-of-the-art performance.

[Cons]:
* The technical contribution is marginal.
* The empirical comparison is insufficient. 
* The result and discussion in Sec. 4.4 is digressed from the main statement.

The paper proposes a simple score-based black-box attack algorithm which achieves state-of-the art results. The simplicity and  effectiveness of the proposed algorithm is great for the research community. However, it seems that the novelty is technically marginal. Moreover, the empirical comparisons are not sufficient to show the advantage of the proposed method. 

* The proposed algorithm is a natural combination of two existing approaches. A previous study [1] utilized the surrogate’s loss gradient for improving SimBA. On the other hand, SimBA-ODS utilized the coimage of the surrogate’s local linearization for improving SimBA. The proposed algorithm is a simple switch algorithm of the above methods based on the update success, and thus the technical contribution is marginal. 

* The empirical comparison is insufficient, because the proposed algorithm was not compared with a variant, which only uses the surrogate’s loss gradient without the coimage of the surrogate’s local linearization (i.e., similar to [1]). Since the proposed algorithm is the combination of two existing approaches (i.e., gradient-based and coimage-based), the algorithm should be compared with both approaches. The right panel in Figure 3 implies that the variant will achieve very similar query efficiency with similar success rate, so the lack of the comparison is problematic. In addition, Figure 3 also suggests that the experiment setting in Sec. 4.1 and 4.2 is suitable for methods utilizing the surrogate’s loss gradient. To show the advantage of the combination of both existing approaches, the evaluation in more difficult settings (such as under small norm bound and on adversarially-trained robust models) is also important. Although the evaluation of targeted attacks in Sec. 4.3 is one of the difficult settings, the comparison and discussion only focus on query efficiency and do not explicitly shed light on the effect of the combination like Figure 3.

* The result in Sec. 4.4 is interesting, but it is not directly related to GFCS. Previous studies have already shown the importance of local gradient information, and GFCS combines two approaches which utilize local gradient information in a different way. It seems that Sec. 4.4 just focuses on input-specific priors and using surrogates, which are related to all local gradient-based methods and not specific to GFCS. How does Sec. 4.4 connect with the main contribution of GFCS? 

Minor comments
* the experiment setting for SimBA-PCA-gradients is not clear. What is a sample input set? Is it different from the test dataset? How many adversarial examples are generated per image? 
* SimBA-SVD is sometimes miswritten as SimBA-PCA.
* In the page 9, what is PGA?

[1] Jinghui Cai, Boyang Wang, Xiangfeng Wang, and Bo Jin. Accelerate Black-Box Attack with White-Box Prior Knowledge. IScIDE 2019.

-----Post rebuttal comments-----

After reading all rebuttals, I'm slightly inclined to accept, since most of my concerns are addressed.

While I raise the score, I'm still concerned about the structure and writing in terms of Sec 4.4. I don't think the current paper properly conveys the author's claim. For example, the first sentence in Sec 4.4 does not distinguish GFCS from other methods, so It seems that GFCS can be replaced with other methods. The authors also do not define "local information". The connection between Sec 4.4 and other parts is weak in the current paper, so the authors should improve the structure and writing when the paper is accepted.
summary_of_the_review: While the proposed black-box attacks show strong empirical performance, the technical contribution is marginal. Moreover, the empirical comparison is not enough to show the advantage of the proposed method.
review_title: null

Meta-review: The paper shows that the transfer attack is query efficient and the success rate can be kept high with the zeroth-order score-based attack as a backup.  Experiments show state-of-the-art results.

Pros: 
- Simple method based on a simple idea.
- State of the art performance.

Cons: 
- Proposal is a straightforward combination of two methods, and therefore technical contribution is marginal.
- The threat model is easy (surrogate can be trained on the same datasets and use the same loss function) and questionable.  Most of the experimental evidence shows that the research for this threat model is almost saturated (and the problem seems almost solved).

This paper got a borderline score with reviewer's concerns above.  I agree with the authors that the simplest method is best among those performing similarly, but the threat setting considered might be not very realistic as the authors admitted.  I see the proposed method a kind of egg of Columbus in a negative sense.  Namely, the authors found a shortcut to win a game that was created and adopted by the community.  Perhaps this paper would give an impact on the small community and would make the community change the game.  But to give an impact to a general audience, the authors should convince that there are some situations where the analyzed thread model is realistic and therefore the proposed method is really useful.  Or, the authors could adjust the thread model to be more realistic.  Serious discussion on the thread model would be a big plus to the marginal technical contributions.

After discussion with SAC, and PC, our conclusion is that this paper effectively tells the community that the benchmark they are using is too simple, which alone is worthwhile publishing because this may move the community forward (even if the community is small).
Decision: Accept (Poster)