Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new decision-based attack for vision transformers (ViTs) with improved query efficiency. In particular, it explicitly considers the difference in noice sensitivity of different patches and queries the low-sensitivity patch first. The evaluation results show the improved query efficiency and smaller perturbation distances over the baseline methods on top of various ViTs and CNNs.
strengths_and_weaknesses: **Strength**
1. This paper is the first to target decision-based black-box attacks for ViTs.

2. The proposed method is based on the observation of diverse noice sensitivity of different patches in ViTs with good soundness, which achieves much improved query efficiency over SOTA methods.

3. This paper is clearly written with a coherent logical flow.


**Weakness**
1. Although the motivation about the more diverse noice sensitivity in ViTs than CNNs makes sense, it lacks experimental verification or visualization. For example, whether the $\kappa$ in Eq.(3) and Fig.2 is more diverse in ViTs than those in CNNs? This could decide whether the proposed method is more customized for ViTs than CNNs, or it's generally applicable as a new attack method.

2. It's not clear whether the order of the proposed patch-wise adversarial removal has a high correlation with the noise sensitivity in ViTs. According to [1], "patch" is a special granularity that makes ViT less robust than CNNs, which could also partially explain the query efficiency of the proposed method.

3. The experimental results lack enough explanation and analysis:
- For baseline methods, can they achieve worse query efficiency or larger perturbation distances on ViTs than those on CNNs under a similar model complexity?
- Does the proposed method achieve a more notable improvements on ViTs than those on CNNs under a similar model complexity?
- How does the final removal strategy correlate with the noise sensitivity?

4. Missing reference:

[1] "Patch-Fool: Are Vision Transformers Always Robust Against Adversarial Perturbations?", Y. Fu et al., ICLR 2022.

[2] "Give Me Your Attention: Dot-Product Attention Considered Harmful for Adversarial Patch Robustness", G. Lovisotto et al., CVPR 2022.

[3] "Reveal of Vision Transformers Robustness against Adversarial Attacks", A. Aldahdooh et al., arXiv 2021.
questions: My questions are listed in the weakness part. I'm willing to adjust my scores if the concerns are properly addressed.
limitations: Although this paper targets adversarial attacks for ViTs, it can help the community better understand the behaviors of ViTs and build defense methods, thus it does not suffer from an obvious negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper addresses black-box adversarial attack in a decision-based manner, especially for ViT based classification models. Authors investigate the noise sensitivity of each region of the image, and propose an iterative patch based manner to gradually remove noises from patches with larger noises. Experiments are carried on multiple classification models with different datasets, show that the proposed method can work together with other attacks to reduce the noise.
strengths_and_weaknesses: Strengths:
+ The proposed method is simple and straightforward to implement and is general enough to be applied on multiple types of classification models.
+ The proposed method is effective to serve as an initialization for query-based adversarial attack, can prune out useless noises quickly according to Figure 4. The proposed method can generally boost other  decision-based attacks.

Weaknesses:
- The proposition 1 in the main paper seems to be wrong, and does not align with the line 39 in the appendix. This causes some confusion when reading the paper. Another confusion is that I am not sure how proposition 1 is used in Algorithm 1 and Figure 3. The definition of noise sensitivity in definition 1 and proposition 1 does not align with the Noise Sensitivity Mask $M_S$ in Figure 3, which is a binary matrix where 0 means possibly higher sensitivity. More discussion and clarification are required to address this issue.
- It's unclear how the proposed method correlates with ViTs, other than that both of them are somewhat related to patches. The proposed method works on both ViTs and traditional CNNs, with similar effectiveness. It's unclear if the "noise sensitivity" story only applies on the ViTs, or applies all the classification models. This weakens the statement in line 40 that "The characteristics of ViTs leaving decision-based black-box attacks against ViTs an open problem".
questions: * How is proposition 1 reflected in algorithm 1?
* In each step of the loop in algorithm 1, noises (z) in the whole patch is set to 0 and then check if the classification is correct. Is it the best strategy to eliminate all noises here? Is it possible to have some smoother version?
* When using PAR as initialization, what is the ratio of noises usually removed?
limitations: Authors adequately have addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work explores decision-based adversarial attacks against Vision Transformers. In view of the huge difference in the noise sensitivity between patches of  ViTs, the authors propose Patch-wise Adversarial Removal to achieve query-efficient noise compression. PAR maintains noise magnitude and noise sensitivity masks to probe and compress adversarial noises in a patch-wise manner, and improve query efficiency through a coarse-to-fine search process on the patch size. Extensive experiments on three datasets demonstrate that PAR achieves a much lower noise magnitude with the same number of queries.
strengths_and_weaknesses: [Strengths]
1.	This work maintains noise magnitude by using the noise sensitivity of the target model. They validate the effectiveness of PAR on three datasets and 18 different target models, and the experiments are extensive.
2.	The narrative of the paper is clear and the proposed method is effective, which can reduce the noise magnitude a lot. 
3.	The vision transformers models are based on patches. Noise sensitivity mask and noise magnitude mask can measure the importance of noise on different patches, and the idea is novel.

[Weaknesses]
1.	The minimum patch size can be one to be added in Table 4, which can be the comparison in the per-pixel setting.
2.	The experiment about time cost can be added to verify the superiority of the PAR.
3.	This method is to reduce the size of the adversarial noise, but in practical applications, reducing the number of queries is a more important goal that needs to be optimized.

questions: please see the weakness
limitations: please see the weakness
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a decision-based black-box attack against vision transformers. Previous decision-based black-box attacks do not consider the noise sensitivity difference among different regions in the images.  In this paper, the authors find that different patches in the images have different noise sensitivity, thus it proposes a new decision-based black-box attack via patch-wise adversarial removal (PAR). PAR divides images into patches through a coarse- to-fine search process, and gradually removes the noise in those patches with low noise sensitivity. Extensive experiments demonstrate that when PAR combined with other SOTA methods, it can obtain smaller noise magnitude under same query numbers.  
strengths_and_weaknesses: Strengths: 
1. This paper is well-written and easy to follow.  
2. The motivation of this paper makes sense and is novel to me. It is reasonable that different regions of the images would have different noise sensitivity. The proposed method is straightforward and effective.
3. The experiments are extensive, it compares with different state-of-the-art methods on different architectures and datasets. 
PAR can combine with other decision-based methods and improve the performance. 

Weaknesses: 
1. In Table 1, it seems that on inc-v3 the median noise of PAR+SurFree is not smaller than SurFree, however, the authors bolded the results, is it typos?
2. It seems that the improvements of PAR+SurFree are not significant when compared to SurFree in Table 1 on Tiny-ImageNet dataset, can the authors give some explanations? 
3. In Table 1, 2, 3，It seems that the performance of PAR itself is not better than the SOTA methods. 

questions: 1. For the noise sensitivity regions in the images, is it more related to the salient region or the background? Can we use the gradient magnitude to indicate the noise sensitivity regions as done in salient region detection?
2. As the attack process is from coarse to fine, though in the experiments it use the same query number, is the computational efficiency of the proposed method lower?

limitations: No potential negative societal impact
review_title: null

Meta-review: metareview: The paper proposed a new decision-based black box attack approach for ViTs. The reviewers appreciate the novelty, extensive experiments and clear writing and unanimously vote for acceptance. Authors' responses helped clarify reviewer concerns and new results, as well as analysis, were presented in the rebuttal. ACs suggest accepting the paper and would request authors to include suggested changes in the final version.
confidence: Certain
Decision: Accept