Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new method for performing hard-label black-box attacks, similar to the HopSkipJump Attack but modified with the observation that the gradient direction is not always the best direction to move in when trying to minimize mean attack distortion. Instead, under some assumptions about the decision boundary, the paper derives an update direction based on an optimal tangent point on the semi-circle around the current attack iterate. The paper then implements the corresponding algorithm and shows that it indeed lowers mean distortion on the CIFAR-10 and ImageNet datasets at a variety of query budgets. 
main_review: The proposed method seems reasonable and to my knowledge the given proofs are correct. I am not an expert in geometry, however, so I can't judge the technical depth or novelty of the theoretical contributions. On the empirical side, the evaluation seems solid (modulo some concerns listed below) and the method does improve on competing hard-label attack algorithms, which lends some credence to the approach. My main comments and questions are below:

Presentation/Clarity:

- L48: The paper claims that "although Rahmati et al. claimed that GeoDA is grounded on the geometric properties of DNNs, it assumes that the decision boundary of DNNs is flat in the vicinity of data samples"---however, isn't this flatness assumption also made by the proposed hemisphere attack as well? I think the authors should either better distinguish their method from GeoDA or just remove the corresponding claim from the paper.
- Fig. 1: What is the motivation for the oddly-shaped decision boundary? In particular, what purpose does the upper decision boundary line serve? In my opinion this figure should be as simple as possible since it is the reader's first introduction to the main idea, so any lines that can be removed should be removed.
- Proof of Theorem 1: Any assumptions made in the proof of Theorem 1 (in particular, Assumption B.1 in the appendix) should be stated in the main text (and explained in intuitive terms if possible) rather than in the proof itself.
- I thought the layout of the paper was good, but local readability is hindered a bit by some grammatical/spelling/phrasing issues (e.g., missing articles, missing pluralizations, tense agreement, etc). These did not affect my score but I think the clarity of the paper could be improved with some proofreading.
- The legend of Figure 5 is too small/hard to read
- Again minor and did not affect my score, but the entire paper is typeset in an incorrect font (you probably have a stray \usepackage in the LaTeX source). 


Experimental:
- Rather than just the average l2 distortion, I think the paper should also show the distribution of l2 distortions across test images---i.e., is it the case that the l2 distortions found by the semi-circle attack are uniformly better, or is it just the other attacks "fail" on some images leading to very high mean distortions?
- The paper mentions that HSJA was re-implemented in PyTorch for consistency which is reasonable, but as a sanity check the appendix should include a comparison of the re-implemented HSJA and the original HSJA codebase on the same models (since it's a black-box attack, it should be easy to use a PyTorch model [or any arbitrary function] in fact) in conjunction with the original code.
- I like the ablation studies that the authors performed in Figure 5! In Figure 5c it seems like decreasing the batch size monotonically improves the performance of the attack, up to the smallest shown batch size. Did the authors try lowering the batch size even further, e.g., to 15 or 10? It would be interesting to see at what point the stability from batching outweighs the redundant queries.

limitations_and_societal_impact: Yes, the authors dedicate an entire appendix section to discussing social impact, and also have a detailed limitations section (in the Appendix). If space permits it would be nice to see some of these discussed in the main paper.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The paper proposes Tangent Attack, a decision based adversarial attack which can be seen as an improvement of HopSkipJumpAttack [6]: it progressively reduces the norm of the adversarial perturbations according to a method inspired by the geometry of the decision boundary in the input space. This allows to achieve adversarial points with lower distortion than HSJA with the same amount of queries of the classifiers, i.e. better query efficiency.
main_review: Strengths
- The motivation of the method and the geometric approach are simple and reasonable.

- The improvement upon HSJA is consistent across models and datasets.

Weaknesses
- The main concern is about the experimental evaluation: the authors cite many related works (QEBA, SurFree, GeoDA) which are improvements of HSJA, as acknowledged, but do not include them in the experimental comparison. Since all those methods outperform HSJA, Tangent Attack needs to be compared to them, especially given that its improvement over HSJA is often not large.

- Similarly, for the $\ell_\infty$-threat model RayS should be included.

Other comments
- The template, especially the font, seems to be not the original one.

- The target classes for targeted attacks are usually sampled randomly, not as the next one.

Overall, the method is quite reasonable and well presented, but the experimental evaluation not sufficient.
limitations_and_societal_impact: I think both are sufficiently discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes a new type of hard-label attacking method. Hard-label attacking methods only allow access of the top-1 predicted labels. This method is based on geometric properties, i.e., tangent points to reduce the l2 distortion after attacks. The method is shown to be superior compared with the existing hard-label attacking methods. The authors also studied the performance under four different defense frameworks, all of which prove the superiority of the proposed method. 


   


main_review: Main concerns:

1. There is something wrong with the fonts and the styles. The authors should have a look and made corrections. 

2.  Although the author claims it is hyperparameter-free, $r$ is still one of the hyper-parameter (although empirically set in the article). If one wants to use the method on other datasets, should the value of $r$ change?


----
## Post-Rebuttal Update
----
I thank the authors for responding to my questions. I will go through others' comments and make discussions but currently, I will keep my score. 
limitations_and_societal_impact: No analysis has been made. 

----
## Post-Rebuttal Update
----

Limitation and Societal Impact are addressed in Appendiex.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors proposed a new geometric-based method for query-efficient hard-label black-box attacks. The proposed method relies on the observation that the minimum l2 distortion can be obtained by searching a boundary point along a tangent line of a virtual hemisphere. The authors offered a closed-form solution for computing the optimal tangent point and provided a formal proof of its correctness. Lastly, the authors evaluated the proposed approach through extensive experiments.
main_review: 1. This paper proposed a geometric-based method to compute the optimal perturbation direction. However, it seems that the authors assume the decision boundary is a hyperplane H and the gradient direction u is known. This raises my two concerns. First, H can be seen as a hyperplane only when we are considering a very small local region. Yet it is not clear whether the actual radius used in the algorithm is small enough such that this assumption holds. Second, the algorithm can only obtain an estimated gradient and using that could lead to very wrong results in computing the optimal tangent direction (as this gradient estimation is well-known to be not precise even using large B). As a motivation for the proposed method, these two assumptions sound ok but the authors might want to further verify the actual conditions in the experiments to make them more convincing.

2. Another downside is that the proposed method will need to tune extra parameters like r compared to other baselines. The authors might also want to show an ablation study on r.

3. In the experiments part, the authors only consider the L2 norm threat model. I think there is no obstacle here to also apply the proposed method in Linf norm settings? (correct me if I miss something here). It would be more comprehensive to also see the Linf norm experiments and compare them with SOTA methods like HSJA/RayS. Especially for the defended models, as they are not trained in the L2 threat model, which makes the results less representative.

4.  Also in the experiments (especially CIFAR10), the advantages of the proposed method are marginal or even non-exist compared with other baselines when the number of queries is sufficient. Here the author only considered 10K as the maximum query number. It is better to show whether the proposed method still holds up the position with maximum of 20k or 50k queries. It would also be nice to have some plots instead of tables to show this one.

=====after rebuttal=========
I thank the authors for their detailed responses. And I appreciate all the extra experiments conducted by the authors. Yet I feel that the proposed method is not better than RayS or QEBA-S on different settings (in R2's comments). And comparing to HSJA, the advantages get vanished when the maximum query number is large or dealing with defended Linf norm models. Therefore, I will keep my score unchanged.

limitations_and_societal_impact: see above, societal impact not applicable
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper discovers that searching the optimal tangent point of a virtual hemisphere could help find minimal adversarial distortion; therefore, this paper proposes an effective method of hard-label attack
main_review: Pros. 

1 The paper is well-written and well-organized. In particular, I like the related work part, which is well-organized. 

2 The experiments on standard models and defensive models exhibit the efficacy of the proposal. 

Comments. 

I have a question about the assumption of the low-curvature smooth surface. 
It is well known that traditional adversarial training techniques such as AT and TRADES have the undesirable issue of robust overfitting. 
When robust overfitting occurs, the decision boundary becomes more and more curved [1]. Would the overfitted model severely violate the assumption that will weaken the efficacy of the proposal? 
Authors may try the friendly adversarial training [2], where it used curriculum training techniques to elude the issue of robust overfitting. 

[1] Geometry-aware instance-reweighed adversarial training, in ICLR 2021. 

[2] Attacks which do not kill training make adversarial learning stronger, in ICML 2020.

######################## post rebuttal ######################
I have read the author(s)' response and other reviewers' comments. I maintain my scores. Thanks. 
limitations_and_societal_impact: n/a
review_title: null

Meta-review: The paper proposes a slightly novel approach for black-box adversarial attacks, with extensive sets of experiments that seem to confirm some performance benefits compared to the related work. This one should be better positioned (e.g., targeted vs non-targeted attack settings), and the active discussion with the reviewers should help in clarifying the true benefits of the proposal in the revision of the manuscript towards any eventual publication. 
Decision: Accept (Poster)