Decision-based Black-box Attack Against Vision Transformers via Patch-wise Adversarial Removal
Authors: Yucheng Shi
Yahong Han
Yu-an Tan
Xiaohui Kuang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Adversarial attack
Black-box attack
Decision-based attack
Vision transformer

Abstract: Vision transformers (ViTs) have demonstrated impressive performance and stronger adversarial robustness compared to Convolutional Neural Networks (CNNs). On the one hand, ViTs' focus on global interaction between individual patches reduces the local noise sensitivity of images. On the other hand, the neglect of noise sensitivity differences between image regions by existing decision-based attacks further compromises the efficiency of noise compression, especially for ViTs. Therefore, validating the black-box adversarial robustness of ViTs when the target model can only be queried still remains a challenging problem. In this paper, we theoretically analyze the limitations of existing decision-based attacks from the perspective of noise sensitivity difference between regions of the image, and propose a new decision-based black-box attack against ViTs, termed Patch-wise Adversarial Removal (PAR). PAR divides images into patches through a coarse-to-fine search process and compresses the noise on each patch separately. PAR records the noise magnitude and noise sensitivity of each patch and selects the patch with the highest query value for noise compression. In addition, PAR can be used as a noise initialization method for other decision-based attacks to improve the noise compression efficiency on both ViTs and CNNs without introducing additional calculations. Extensive experiments on three datasets demonstrate that PAR achieves a much lower noise magnitude with the same number of queries.

Decision-based Black-box Attack Against Vision Transformers via Patch-wise Adversarial Removal
Yucheng Shi, Yahong Han" College of Intelligence and Computing, and Tianjin Key Lab of Machine Learning Tianjin University. Tianjin, China Engineering Research Center of City Intelligence and Digital Governance Ministry of Education of the People's Republic of China (yucheng, yahong) @t ju. edu.cr. on.
Yu-an Tan
School of Cyberspace Science and Technology Beijing Institute of Technology, Beijing, China t tan2008@bit. en
Xiaohui Kuang
National Key Laboratory of Science and Technology Information System Security, Beijing, China siaohui_kuange 1 63. com
Abstract
Vision transformers (ViTs) have demonstrated impressive performance and stronger adversarial robustness compared Convolutional Neural Networks (CNNs). On the one hand, ViTs' focus on global interaction between individual patches reduces the local noise sensitivity of images. sensitivity differences between image regions by existing decision bocision-bbsedd attacks further compromises the efficiency of noise compression, especially for ViTs. Therefore, validating the black-box adversarial robustness of ViT's when the target model can only queried still remains challenging problem. In this paper, we theoretically analyze the limitations of existing decision baandd-addddeee attacks from the perspective of noise sensitivity difference between regions the image, and propose a new decision-based black-box attack against ViTs, termed Patch-wise Adversarial Removal (PAR). PAR divides images into patches through a coarse- to-fine search process and compresses the noise each patch separately. PAR records the noise magnitude and noise sensitivity of each patch and selects the patch with the highest query value for noise compression. In addition, PAR can be used as a noise initialization method for other decision-based attacks to improve the noise compression efficiency additional calculations. Extensive experiments on three datasets demonstrate that PAR achieves much lower noise magnitude with the same number of queries.
the other hand, the neglect of noise
both ViT' and CNNs without introducing
Introduction
Vision transformers (ViTs) 1 not only achieve significant performance improvement in a wide range of computer vision tasks 3 but also show stronger robustness against adversarial examples generated by different attack methods 5
g. The adversarial examples are generated by attackers
'Cooresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

5.0
5.0
4.5
2.5
4.0
0.0
Original Imaae
Boundary Heatmap
PAR Heatmap
Initial Noise 99.60
Boundary Noise f2 72.
PAR Noise f2 6Z
Figure 1:
Noises of Boundary Attack and our method PAR after 100 queries from the same initial noise. Heat maps visualize the noise magnitude of each patch. PAR removes noise in patches with low noise sensitivity, achieving significantly smaller noises than Boundary Attack.
to fool the target model by adding imperceptible noises to original data 9 of using non-overlapping patches in ViTs reduces the influence of adversarial examples with the same noise magnitude on the overall results [5].
10
The characteristic
According to the amount of information the attacker can obtain, adversarial attacks can be divided into white-box attacks and blx attacks 112. In the black-box scenario where the attacker can only obtain the hard labels output by the target model, adversarial attacks can be further divided into transfer-based methods [13 [4] and decision-based methods [15]. caunsfer-based methods use a substitute model to generate adversarial examples and transfer them to the target model taking advantage of the transferability [T6 17 [8]. Compared with transfer-based attacks, decision-bart
attacks face a more practical setting where a substitute model is not available. The only source of information for decision- based attacks is hard label obtained by querying the target model. In the image classification task, the decision- based attacks [15]
19 20 start from a random noise with large noise magnitude, randomly sample in the image input space, and gradually compress the adversarial noise under the premise of ensuring misclassification. The existing adversarial attacks against transformers are only white-box attacks (21 5 22 23 and transfer-based black-box attacks 24 (25. The characteristics of ViTs' patch-wise splitting of images reduce the impact of adversarial noise, leaving decision-based black-box attacks against ViTs an open problem (5).
The challenge of attacking VITs with decision-basee methods comes from their properties in noise sensitivity, which derive from the structural characteristics of ViTs. On the one hand, ViTs learn fewer low-level features and more transferable features than CNNs, resulting a much more noise needed to attack ViTs (21. In other words, the overall noise sensitivity of ViTs is low. Decision- based attacks against ViT' need to add random noise with much larger noise magnitude to find the initial adversarial examples. Larger initial noise makes it more difficult for the decision-based attacks to compress, i.e., to find the smallest adversarial noise under the same number of queries. On the other hand, ViTs split the image into multiple non-overlapping patches, which reduces the impact of noises on one single patch to the final classification results [5]. This leads to a notable difference in ViTs' noise sensitivity between different regions of an image, which is rarely considered by existing decision based methods. For example, the noise compression process of Boundary Attack
15 treats all pixels equally regardless of their noise sensitivity, as demonstrated Fig. [ which severely hinders the efficiency of noise compression. These two properties in noise sensitivity make it extremely difficult for existing decision- -based attacks to find adversarial examples with small noise magnitude against ViT'. Noise sensitivity directly reflects the black-box adversarial robustness of ViTs, which has not been well studied and unable to shed light on the mechanism of improving noise compression efficiency. Therefore, designing decision- based attacks against ViTs according to their noise sensitivity properties is an essential problem.
In this paper, we verify that noise sensitivity of ViTs varies significantly between different image regions. The limitation about the compression process of decision-based attacks represented by Boundary Attack is theoretically analyzed. Based on the relationship between ViTs' patch-wise sensitivity and noise compression success rate, we propose a new decision- based attack method Patch-wis biich Adversarial Removal (PAR). PAR splits the adversarial example into multiple patches and perform coarse-to-fe fine noise removal. Specifically, PAR maintains two masks to record the noise sensitivity and noise magnitude of each patch, respectively. Before querying the target ViTs, PAR locates the patch with the highest query value based on these two masks. As the search progresses, the size of each patch gets smaller while the measure of the noise sensitivity of the ViTs becomes

---

more accurate. PAR achieves a significant noise compression under a small number of queries, which can be used an initialization for other decision-basee attacks without additional computation.
We validate the effectiveness of PAR on three datasets: ImageNet-211 [26], ILSVRC-2012 (27). and Tiny-Imagenet [28]. We compare PAR with 7 state-of-the-ar decision-based attacks against 18 different target models, including 8 CNNs and 10 ViTs or bybrid models. Benefiting from the powerful redundant noise compression capability, the noise magnitude of all decision- attacks has been notably reduced after using PAR for noise initialization without increasing the query number.
2 Related Work
2.1 Robustness of Vision Transformer
The VìTs show stronger adversarial robustnes 29
Not only does fooling ViTs in the white-box scenario require larger noise magnitude (21], but it also difficult for existing transfer-based black- box attacks to transfer adversarial examples from CNNs to ViTs (24). Existing research mainly focuses on the white-box attacks and transfer-based black-box attacks against ViTs. However, this paper explores the decision-basee attack against black-box ViTs without substitute model.
2.2 Decision-based Attack
Decision-basee attacks do not rely on substitute models, but require an initial adversarial example that has already been misclassified as starting point. Boundary Attack (I5) starts from an gaussian noise and searches along two directions simultancously, namely source direction and spherical direction:
new x" + 6-
1
+
I
7) ~00,011
(I)
1
1
where x" is the adversarial example with smallest noise that already been found. and (a: x²) refer to the directions of spherical and source direction, respectively. ó and E are stepsizes of spherical and source direction. The Biased Boundary Attack (20) concentrates on low-frequency domain of input space to make the adversarial example more 'natural.. The Evolutionary Attack [19] reduces the dimension of sampling space by bilinear interpolation. Evolutionary attack performs better in tasks involving strong prior knowledge such as face recognition. HopSkipJumpAAtaae (30] estimates the gradient direction using binary information at the decision boundary. Customized Adversarial Boundary (CAB) [31 uses current noise to select the sensitive regions of images and customizes sampling distribution. SurFree Attack 32 is based on the geometrical mechanism to get the biggest distortion decrease for given direction to be explored. Sign-OPT attack 33 uses a zeroth order oracle to compute the sign of directional derivative of the attack objective.
Boundary Attack maintains two search directions according to Eqn. (.. The source direction is pointed the original image with small stepsize, which is responsible for noise compression. The spherical direction is random direction with large stepsize, which is used to perturb in the neighborhood of current adversarial example x and ensure that the updated adversarial example is still misclassified by the target model. It can be seen from Eqn. (T) that in the one-step update of the current adversarial example, the spherical direction rj follows the standard Gaussian distribution with the same dimensions as the original image. The source direction points to the opposite direction of the current adversarial noise. Both search directions show no preference for any region or pixel in the image. In other words, under a uniform initial random adversarial noise, the Boundary Attack performs noise compression with basically the same magnitude for all pixels. fact, the Boundary Attack does not make any distinction between different pixels in the image, and the noise compression of each pixel is proportional to its initial noise magnitude [3]].
3 Proposed Method
3.1 Notation
Suppose the target model be attacked: F : XN - YC, where represents the input space, N is the dimension (N Width Height x Channel for image data) and Y represents the
3

---

0.40
0.50
0.35
Original Image
Initial Noise f2 = 63. 38
Putch-wise Noise Sensitivity
Original
P(F() x)) F(X' + = R(0))
Patch-wise Noise Sensitivity
Figure 2: Illustrations of original images, initial random noises, and corresponding visualizations of patch-wise noise sensitivity.
classification space with C' categories. The goal of decision- attack can be expressed as:
|| - xllls s.l. F(x') # y and |So] S T, z'E
min
where æ represents the original image, refers to adversarial example, y is the label of æ, Sg the set of all adversarial examples generated to query the target model, 7 is the limit of query number. refers to the norm used to measure the noise magnitude including l, & and foe norm. this paper the Ez distance is calculated. In the process of decision-based attack, the attacker can only obtain the hard label F(x') output by the target model.
3.2 Noise Sensitivity VITs
Here we measure the noise sensitivity Sens of one patch in the image according to the maximum ratio the noise can be compressed under the current adversarial example on ViT:
Definition 1. Let x' be an adversarial example of VIT model F on the original image i.e. F(z') # F(x), and be the current adversarial noise =x' x. Let be a new adversarial noise compressed from z in rectangle patch with width of w, height of h, top left corner of sT, sC:
Zr.e Ki
if sr
Sr sr sr and se S 80 w, else,
ž(sr, sc, h w. K)ne
(3)
Fr.e:
where r and refer to the row and column index of one pixel in noise respectively. E [0.1] denotes the noise compression ratio. Define the noise sensitivity of rectangle patch as the minimum noise compression ratio Emin when F misclassifies + 2:
Sens(P. F. P, x', sr, sc, h, w) = Kminn 8.l.
F(x + 2(sr, se, h, Kmmnn) ) + F(x)
(4)
and ke' < KKmiin F(r + 2(rr, sc, h, w. x()) = F(x).
Sens measures the minimum amount of noise that is required for an adversarial example. A smaller Sens means that more noise be removed without changing the misclassification results, ie.. adding noise this patch has less impact on classification results. When = w 1, Sens measures the pixel-level noise sensitivity.
We use vision transformer 27 as the target model. To demonstrate the difference of patch-wise noise sensitivity in Fig. 2 we add initial Gaussian noise noise, we try to reduce the noise on each patch to evaluate the patch-wise noise sensitivity of the images on the target model. Since the size the original image 224 224 x 3, there are 14 14 patches. We use binary search to evaluate Sens each patch:
34 with patch size of 16 trained on ILSVRC-2012
original images until they are misclassified. After getting the initial
=
x. init R = x init Lraws 16+ I:(romm-t 1) 16, 16+ I:(eot+ 1)+16 = 0,
(5)
BS(L,R) = BBSL R)/2), if F(L++ R)/2) # y,
(6)
BS((L+ R)/2, R), F(L+ R)/2) y.
where row, col E [1, 14] refer to the row index and column index of one patch in the image, respectively. The heat map Fig. 2 shows the Sens on all x 14 patches. In the heat map, lighter color means lower Sens on one patch. indicates that any small noise compression on this

---

Upaate
Update
Initialize
Record
Success
Query
Initial Adversarial Example ninie
Current Adversarial Example x"
Noise Magnitude Mask M
Qhery
Black-Box Vision
Patch-wise removal
Transformer
ti Update
Initialize
Record
Fail
Initial Noise tnce
Current Noise z²
Noise Sensitivity Mask M5
Query Value Mask Me
The noise compression process of PAR. Based on the initial adversarial example, PAR records the noise magnitude of current adversarial example and the noise sensitivity from historical queries, respectively. After locating the patch with the highest query value (yellow circle) using the product of masks, the noise on the corresponding patch of current adversarial example removed and query the target ViT. If misclassified, PAR updates the noise magnitude mask. Otherwise the corresponding patch on the noise sensitivity mask set to zero.
Figure 3:
patch makes the target model outputs correct label. 0 indicates that the adversarial example remains misclassified even all noises on this patch are removed. Considering the attack process of Boundary Attack, the patch-wiss sensitivity of adversarial examples and the compression success probability within a patch of one single query have the following relationship:
Proposition 1. Assume x' is initial adversarial example generated by Boundary Attack against ViT F starting from original image x, F(x) * F(x'). For any < Ti, T1, S Height, 0 < 61, 02 w S W idth, if Sens(E F, x, x', F1, Fr,1i,, h, w) step by Boundary Attack is z', then ((F(2' + 2 F(x) + = =(x)) ((F + 2/2) + F(x) F(x) + +z') F(x)), where for = 1,2
SSnss(F. x, x' T2, C2 h, w), and the new noise added by one
0,
is r rr < + and a.cc w
else,
Proof Idea. The expectation of each pixel on the initial noise x' generated by Boundary Attack is equal, and the noise compression ratio after one-step Boundary Attack for each pixel is i.i.d. The possibility that the noise compression ratio patch. Since the probability that noise compression ratio on at least one pixel exceeds Sens increases monotonically w.r.t. the noise sensitivity the whole patch, the noise removal of high Sens patch is more likely to be the cause of misclassification failures.
least one pixel exceeds is also the same for any
The detailed proof of Proposition I is provided in the Supplementary Material A.2. Proposition indicates that during the noise compression process of Boundary Attack, patches with higher Sens are more likely to be the cause of query failure than regions with lower Sens. Obviously, the noise sensitivity of ViTs varies greatly different regions of the image. In the right part of Fig. 2 we compare the patch-wise sensitivity of original image (b) and the probability that noise compression ratio exceeding Sens on each patch P(F(x' + 2f)) # F(x) + F(x)) caused by one step of Boundary Attack. As can be seen that these two heat maps are basically consistent on patches, which verifies Proposition 1. can be seen from Fig. 2 that completely removing noises of many patches from inet does not affect the misclassification. However, the uniform compression of Boundary Attack usually keeps these redundant noises to the end. The magnitude of the whole block of redundant noise is considerable, especially for ViTs which require larger initial noise.
5

---

Algorithm/ Patch-wise Adversarial Removal
Input:
Target model F(x), noise magnitude limit т, original image x and label y Max querying number T' initial variance of gaussian distribution var Identity matrix / of the same dimension as x, initial and minimum patch size PS and PS min Output: Adversarial example x² with compressed noise
while F(xinit) = y do
ginit (0, var
zénit + Clipp,> + Gaa
50 J var var 22, T
Initialize MN and Ms according to Eqn. (8) and Eqn.
PS +- PSp, x² & nnst
while T do
Mo < My C Ms
if Σ MQ = 0 then
PS - PS/2, initialize MN and Ms according to Eqn.
8 and Eqn. (9)
PSP < PSmin then L break
11 Locate the highest value in query value mask
TOw" col' + argmazz (Mgaa(MMq)
qquery xx-- I, "Tou- PS- P 41oo 1) f- 0
yquery + Clipa, (= {=query + x if Fuxquery) # y then
L + guery, update MN
else
L Msrow ,cot- _cot
f-
T-T-1
3.3 Patch-wise Adversarial Removal
According to Proposition the Boundary Attack compresses the overall noise of x' together, whose noise compression rate depends on those patches with the highest Sens. Ideally, decision- based attack should firstly compresses regions with low Sens and high noise magnitude. the success rate of query and the magnitude of one-step noise compression can be guaranteed, and the efficiency of noise compression can be maximized with limited query numbers. On the one hand, the noise sensitivity of the target model to different regions of the initial noise cannot be directly obtained. On the other hand, using binary search similar in Fig. for one patch and perform grid search for all the patches consumes large quantity of queries. Therefore, we propose a new decision-based attack Patch-wise Adversarial Removal (PAR). PAR divides the initial noise into patches, probes their noise sensitivity and compresses the noise in patch-wise manner.
this way, both
As illustrated in Fig. 3 PAR guides the probe process by maintaining two masks that record the noise sensitivity of the target model and the noise magnitude of each mask, respectively. Since the detail of the ViT's is not available in the black-box attack setting, PAR does not assume the patch size of ViTs, but starts from a large patch size to conduct multiple rounds of coarse-to-fie finfine search.
Firstly, PAR initializes the noise sensitivity mask Ms and noise magnitude mask My. The shape of the two masks is PSp x PS. where PSp is a hyper parameter denotes the initial patch size of PAR. We the initial noise magnitude in & of each patch in iiii to initialize MN:
(row P) (row+ PSo Σ
Mx(row,col
Σ
(xrinit - zz.)²
(8)
where row and col indicate the row index and column index of MN, row, col [1, PSo). The noise sensitivity mask is binary. in Ms indicates that the corresponding patch in the adversarial noise remains a low noise sensitivity state, which may not have been queried or noise removal has been successfully carried out. 0 in Ms indicates that the previous noise compression process is failed. The initial value for each element in Mg is 1. Before each query to the target model, we use element-wise product obtain the query value mask Mq:
Ms Jrow,cols
MQ MN O Ms.
where J is unit matrix of all-ones.

---

Table 1: Median and average &g distance of adversarial perturbations Tiny-Imagener
Target
res-18
inc-v3
inc-res
nasnel
Methods
median
average
median
average
median
average
median
average
Initial
2.542
5.024
8.238
8.402
10.255
9,933
8.853
8.428
PAR
0.45
1.104
1.457
1.961
1,805
2.279
1.723
2.022
HSJA
0.959
2.762
3.479
4.576
5.053
5.603
4.226
5.237
PAR+HSJJ
0.396
1.067
1.392
1.899
1.793
2.236
1.668
1.992
BBA
0.23
0.787
1.091
1,669
1,565
2.041
1,361
1.815
PAR+BBA
0.142
0.605
0.723
1.25
1.126
1.59
0.948
1.463
Evo
0.522
1,518
2.043
2.971
2.892
3.516
2,411
3.448
PAR+Evo
0.294
0.882
1.183
1.701
1.662
2.01
1.532
1.835
Boundary
0.577
1.194
1.552
2.091
2.38
2.807
1.967
2.388
PAR+Boundary
0.296
0.813
1.034
1.457
1.478
1,852
1.425
1.773
Surfiree
0.143
0.653
0.627
1.233
1.126
1.772
0.963
1.639
PAR+SurFree
0.14
0.599
0.629
1.171
1.087
1.479
0.952
1.453
CAB
0.397
0.977
1.103
1.819
1.372
2.245
1.23
2.301
PAR+CAB
0.248
0.728
0.803
1.326
1.11
1.604
0.968
1.474
OPg
2.134
4,293
6.669
7.268
7.037
8,274
7.332
7.394
PAR+Sign-OPT
0.433
0.957
1.426
1.926
1.712
2.012
1.573
2.008
If patch does not contain noise or previous query is failed, there is no query value. We sort the values in Me in descending order, and remove the noise in the patch corresponding to the highest value in Mo. We input the updated adversarial examples æ-ueer into the target model to obtain the query result. guery still misclassifies the target model, it indicates that the noise sensitivity of this patch is low. In this case, we set x" as zuuery and update My. Otherwise, the noise sensitivity of the patch is high, and the corresponding element in noise sensitivity mask Mg is set to O.
If the sum of Mq is O, all patches under current patch size PS either have no noise, or the query has already been made. In this case, we halve the patch size and reinitialize My and Ms according to Eqn. (8) and Eqn. (9). The next round will conduct more fine-gras fine-grained query the patches where there are still noises. Since the noise on some patches have been removed in the previous rounds, the search process of PAR with gradually reduced patch size is much more efficient in terms of queries than using very small patch size at the beginning.
There are two exit conditions for the search process of PAR, either the max query number T is reached the minimum patch size PSmin has been reached. The PSmin is set for the efficiency of one-step noise compression. When the patch size is too small, the compressed noise magnitude after one step is not worthwhile even if the subsequent query succeeds. Algorithm I details PAR.
3.4 PAR as Noise Initialization Method
As an query-efficient rrcision-based attack, PAR can also be used as a noise initialization method for other decision-basee methods. PAR removes all possible blocks of noise larger than the minimum patch size PSmin leaving the remaining regions to seisiisensitive for ViTs. In this way, PAR greatly reduces the search space for subsequent noise compression. After initializing noises with PAR, decision-based attacks may concentrate each sampling the regions with higher noise sensitivity.
Experiments
4.1 Experiment Settings
We conduct experiments on three image classification datasets: ImageNet-21k (26] ILSVRC-2012
27], and Tiny-Imagenet (28) We pick 10000 images from the validation sets ImageNet-21k and ILSVRC-2012 that can be correctly classified by all target models for test. As for Tiny- Ting-Imagenet with 200 image categories, we choose 2000 images, 10 images for each category. 10 vision transformer models with different structures 34 are compared: vit-s32, vit-b16, vit-b32, r50-132, r50-s32, vit-large-patchle 1-t2h16-224, vit-tiny-patch16-22 16-224, vit-small--26-s32-222
1tt-tiny-patch1--2244 vit-small- patch16-224. We also include 8 CNNs as target models: resnet-18 18 (35), resnet- 101, inception v3 (36,,
7

---

Table 2: Median and average & distance of adversarial perturbations on ImageNet-2Ik:
Target
r26
f26_s32
li s16
vit s16
G 116
r 16
Methods
median
average
median
average
median
average
median
average
median
average
Initial
41.161
43.24
21.376
26.847
40.52
45.828
23,591
43,866
8,075
14.297
PAR
5.706
9.189
2.771
3,992
4.326
7.516
5.016
10.18
1.554
2.592
HSJA
20.356
25.011
8.06
13.444
16.369
25.268
14.434
25.535
4.367
8.373
PAR+HIIJA
4.752
7.781
2.388
3.719
3.644
6.688
4.517
9.093
1.522
2.51
BBA
5.849
9.069
1,643
3.125
3.692
6.422
5,423
10,875
1.263
2.315
PAR+BBA
3.899
6.953
0.982
2.21
2.098
4.547
3,456
7.816
0.921
1.759
Evo
8.195
12.047
4.133
6.253
5.223
9.82
7.847
15.358
3.093
3,924
PAR+Evo
4.091
7.122
2.055
3.284
2.427
5.236
4.041
8,576
1.487
2.223
Boundary
11.25
14.102
4.8
6.068
7.963
11.533
8.047
13.583
2,442
3.876
PAR+Boundary
4.762
8.073
2.145
3.34
3,535
5.888
4.604
8.795
1.296
2.307
Surfree
6.331
10.485
I,505
3,486
3.048
7.849
5.979
11.001
0,949
2.25
PAR+SurFree
4.078
6,989
1.224
2.589
2.183
4.603
4.015
7.959
1.008
1.912
CAB
4.214
8,034
1.966
3.978
2.364
10.554
3.646
12.058
1.121
2.084
PAR+CAB
1.963
4.879
1.012
1.824
1.244
3.484
1.752
6.145
0.694
1.423
Sign-OPT
30,581
36.062
19,56
22.152
29,566
38, 994
20.952
38,496
6,392
12,083
PAR+Sign-OPP
4.525
8.067
2.602
3.73
3.578
6.679
4.91
9.387
1.353
2.548
Table 3: Median and average bg distance of adversarial perturbations on ILSVRC-2012.
Target
res-101
dense
vgg- 19
senet
_26_s32
vit_s16
Methods
Mid
Avg
Mid
Avg
Mid
Avg
Mid
Avg
Mid
Avg
Mid
Avg
Initial
58.60
54.71
54.38
52.77
34.80
34.67
49.52
53.96
94.72
88.49
96.25
92.94
PAR
9.19
10.60
10.08
11.50
6.25
7.09
7.80
10.80
14.71
28.52
15.10
30.75
HSJA
33.13
36.29
30.22
32.58
17.75
20.85
29.38
34.69
63.67
63.81
65.81
67.41
PAR+HSIA
8.92
10.06
7.97
10.84
5.89
6.75
7.76
10.06
13.75
27.42
14.55
30.05
BBA
9.00
9.78
9.17
10.83
5.44
6.85
8.72
12.31
13.16
26.88
13.86
28.36
PAR+BBA
4.89
7.24
5.39
7.78
3.26
4.77
5.45
7.15
9.88
23.14
8.83
25.29
Evo
12.53
13.89
I1.91
13.59
8.71
11.28
9.94
12.11
23.83
34.28
24.21
37.96
PAR+Evo
6.83
8.34
5.71
8.46
4.88
5.87
5.51
7.94
11.80
24.79
11.50
27.54
Boundary
16,25
18.17
14.78
17.65
8,96
10.92
14.53
18.29
28.05
37.54
21.52
36.53
PAR+Boundary
7.29
9.19
6.98
9.60
4.82
5.90
6.71
8.60
11.62
25.68
11.09
27.81
SurFree
12.27
14.57
8.99
14.07
5.05
8.02
6.59
13.52
20.35
31.56
15.88
32.09
PAR+SurFree
6.08
7.88
5.54
8.22
3.31
4.88
4.91
7.26
10.11
23.90
9.79
26.32
CAB
11.20
19.52
9.29
19.02
3.95
9.07
9.54
22.14
18.84
38.26
18.69
44.85
PAR+CAB
4.73
6.86
4.05
7.76
2.51
4.29
3.81
7.05
7.07
22.60
6.19
24.96
Sign-OPT
50.18
47.92
32.71
46.63
28.38
30.25
44.37
47.59
83.99
81.34
83.47
83.78
PAR+Sign-OPT
9.16
9.63
10.02
11.14
4.37
6.43
6.80
9.63
13.16
28.23
14.23
28.78
inception-resned v2 (37, nasnet 338,
densenet-161
39
vgg
19-bn
40
senet-154
41
RTX 3090
GPU cards are used for calculation.
We compare 7 decision based attacks with our PAR under the black-box setting with limited query number: Boundary Attack [15], Biased Boundary Attack (BBA) [20], Evolutionary Attack (Evo) [1). HSJA 30 CAB 31, Sign-OPT [3 and SurFree 322 Stepsizes of spherical direction and source direction are 8n = 0.1, c = 0.003 for Boundary, BBA, Evo and CAB. For BBA (20]. we use the version that does not incorporate information from substitute model at each step for fair comparison. Noise magnitude limit - [0, 255). The initial and minimum patch size for ImageNet-2] lk and ILSVRC-2012 is set to 56 and 7, respectively. For patch size as 16 and 2, respectively. All datasets are under BSD 3-Clause License.
we set the initial and minimum
For evaluation criterion, we choose the median and average size of adversarial perturbation, as applied in NIPS 2018 Adversarial Vision Challenge (28]:
Adata
mid- = median((1e) - 2||2
X)), arg
Σ CL - -1:2/-2:11a E
(10)
Tdato
where Ndttt is the number of images in a dataset, x is an original image in the dataset X. x' the adversarial example found that is closest to æ. A smaller & distance indicates a better adversarial example. worth noting that adversarial examples are rounded before being input to the target model for more realistic black-box attack setting.
8

---

80.00
60.00
80.00
60.00
60.00
40.00
mid
40.00
40.00
20.00
20.00
20.00
0.00
0.00
0.00
0
1,000
2,000
3,000
1,000
2,000
3,000
0
1,000
2,000
3,000
(a) vit-small- -tt-smml--2---222224
(b) vit- www.s-mmaaalplllllom
(c) vit-tiny-patchlee
15.00
100.00
15.00
10.00
mid
10.00
50.00
5.00
5.00
0.00
0.00
0.00
0
1,000
2,000
3,000
1,000
2,000
3,000
0
1,000
2,000
3,000
(d) vil-large-patch6-225
(e)
vit-small--26-3322222222
(T)
vit-fnn--aachhl-2224--2222
Boundary
PAR+Boundayy
CAB
PAR+CAB
Evo
PAR+Evo
Figure 4: Median l distance of adversarial noise under different query number T.
Table 4: Targeted adversarial perturbations on ILSVRC-2012.
Initial
PAR
HISJA
BBA
Evo
Boundary
SurFrree
Mid 152. 39,821 92.183 67.728
69.397
52.584
57.808
Avg 154.797
40.792 93.767
70.01
69.039
51.272
55.378
4.2
Experimental Results
To verify the advantage of PAR over existing decision based attacks on VITs and CNNs, report the median and average adversarial perturbation on ImageNet-2II, ILSVRC-2012, and Finy-Imagenet in Table Table D and Table I respectively. The first row of three tables represents target models with different structures. We compare the average (Avg) and median (Mid) noise magnitude generated by PAR and other 6 attacks different target models. We also PAR the noise initialization for other decision- based attacks. The noise compressed by PAR is handed over to other decision- based attacks for further compression. can be seen that when PAR is used to initialize adversarial noise, the average and median noise magnitude drops significantly compared with only using the original decision-based attack. This verifies the strong noise compression ability of PAR. We also combine PAR with other decision-bur based attacks, and compare the query efficiency under total query numbers of 3000 in Fig. The target models are notated under each subfigure. There is noticeable drop in noise magnitude when initializing the noise with PAR.
Table compares the noise compression efficiency and the average query number of PAR under different initial patch sizes and minimum patch sizes. The compressed noise is handed over to Boundary Attack for further compress until 1000 queries. It can be seen that when the initial patch size is small, the average query number will be large, resulting in low query efficiency and less query number for subsequent decision-based attacks. A more reasonable strategy is to use large initial patch size and stop at a small minimum patch size.
We also extend PAR to targeted attack. We randomly choose an image of target class starting point and keep the adversarial examples target class. The target model is vit-small-r26-333 Targeted results are shown in Table The targeted noise of PAR is still significantly smaller than others.
by seven different attacks on ILS VRC-2012. The first row shows the original images. The second to eighth images of each row are the noises generated by each attack. PAR stops when the exit condition met. All other attacks perform 1000 queries on the target model for each adversarial example. The noises of PAR mainly concentrate on few patches instead of spreading over the entire image. The noise magnitude of other decision-bace attacks decrease significantly when PAR is used for noise initialization. PAR
Fig. 5 compares adversarial noises generated against vit-small--2--s32222

---

Table 5: Noise compression comparison different initial patch sizes and minimum patch sizes.
Initial Patch Size
I12
112
112
112
56
56
56
28
28
14
Minimum Patch Size
7
14.
28
56
14
28
14
7
Mid Noise
4.31
5.07
5.55
6.21
4.34
5.54
5.09
4.79
vgg- 19
Avg Noise
5.83
7.11
8.17
8.84
5.92
7.20
8.33
6.11
7.43
6.47
Avg Query Number
195.69
97.30
44.54
16.80
202.98
100.88
45.79
238.24
130,58
415.06
Mid Noise
8.76
9.32
9.54
10.35
8.62
9.17
9.67
9.01
9.88
9.17
vit s16
Avg Noise
17.24
19.08
19.96
17.08
19.69
17.43
19.16
17.90
Avg Query Number
249.34
122.81
49.53
17.04
247.01
120.93
49.90
289.67
153.07
448.60
PAR SurFrree
PAR
Eg Noise Magaitude
Original Image
PAR
Boundary
Boundary
SurFrre
CAB
CAB
PAR+CAB
11 11:60
CAB
15,280
PAR-Surhee
12320
Sertnee
17.330
PAR PAR-Buundary
(1:44)
Boundary
18,510
Mack
curty-ooated
New www.ooudland curly-conted. dog
Newfoundland
curfy-coated retriever
Newfoumlland dog
curlg-uoateed
PAR
16.870
retriever
PARtSurfaa
Surftee
PAR -Beundary
24.430
Bourday
30,340
brush kangaroo
Madagascar 1oll
lox
Madagasear Lill
Jeey lox
Modagescor sall
fox
Midagsscor
PAR
31,750
cod
PARICAB
17.180
CAB
30,580
PARt-Serhes
19:490
PAR-Boundary
conch
Jollyfish
noutilus
jellytish
naunilus
jellyfish
naunilus
Jellyfish
PAR
PAR+CAB
10.50
CAB
49
PAR Suc
22.25
SurFree
44.19
PAR-ikondary
32:72
Bousdary
cradle
brain
trilobite
brain coral
trilobite
brain coral
trilobite
brain cural
PARACAB
CAl
FAR-SuFiez
8:81
SuFFee
21.39
PAR Boondary
13.55
Boundary
16.15
snail
tray
PAR
17.41
Figure 5: Comparison of adversarial noises generated by PAR, Boundary, PAR+Boundar,, SurFree, PAR+SurFree, CAB, and PAR+CAB on ImageNet dataset. The labels and misclassificatio categories are noted under original images and adversarial noises. The rightmost column compares the noise magnitude of attacks in & norm. 1000 queries have been performed for each attack except for PAR.
proposed in this paper is only used for the study of adversarial machine learning and the robustness of ViT's, and does not target any real system. There is no potential negative impact. More experimental results on different target ViT and CNN structures are provided in the Supplementary Material A.3.
Conclusion
In this paper, explore decision-based adversarial attacks against Vision Transformers. In view of the huge difference the noise sensitivity between patches of ViTs, we propose Patch-wise Adversarial Removal achieve query-effciient noise compression. PAR maintains noise magnitude and noise sensitivity masks to probe and compress adversarial noises in patch-wise manner, and improve query efficiency through a coarse-to-fine search process on the patch size. Experiments three image classification datasets verify the feasibility and generalizability of PAR to improve the query efficiency with limited query number.
Acknowledgements
This work is supported by the National Natural Science Foundation of China (NSFC) (under Grant 61876130, 61932009) and the Open Foundation of Henan Key Laboratory of Cyberspace Situation Awareness (No HNTS2022028).
10

---

References
[1] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenbom, X. Zhai, T. Unterthiner, M. Dehghani, M. Min- derer, G. Heigold, S. Gelly et al., "An image is worth 16x16 words: Transformers for image recognition at scale," in ICLR, 2020.
[2] N. Carion, Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko, "End-to-end object detection with transformers," " in ECCV. Springer, 2020, pp. 213-229.
[3] R. Strudel, R. Garcia, I. Laptev, and C. Schmid, "Segmenter: Transformer for semantic segmentation." in ICCV, 2021, pp. 7262-7272.
[4] Z. Liu, J. Ning, Y. Cao, Y. Woi, Z. Zhang, S. Lin, and H. Hu, "Video swin transformer," arXiv preprint urXiv:2106. 13230. 2021.
[5] S. Bhojanapalli, A. Chakrabarti, D. Glasner, Li, T. Unterthiner, and Veit, "Understanding robustness of transformers for image classification," in ICCV, 2021, pp. 10231-10241.
[6] M. M. Naseer, K. Ranasinghe, S. H. Khan, M. Hayat, F, Shahbaz Khan, and M.-H. Yang, "Intriguing
properties of vision transformers," " Advances Neural Information Processing Systems, vol. 34, 2021.
[7] X. Mao, G. Qi, Y. Chen, X. Li, R. Duan, S. Ye, Y. Hc, and H. Xue, "Towards robust vision transformer," arXiv preprint arXiv:2105. 07926, 2021.
[8] A. Aldahdooh, W. Hamidouche, and O. Deforges, "Reveal of vision transformers robustness against adversarial attacks," arXiv preprint axxiv:206600.7.. 2021.
[9] C. Szegedy, W. Zaremba, I. Sutskever. J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus, "Intriguing properties of neural networks," in ICLR, 2013.
[10] A. Nguyen, Yosinski, and J. Clune, "Deep neural networks are easily fooled: High confidence predictions for unrecognizable images," in CVPR, 20155, pp. 427-436.
[1I] N. Akhtar, M. Jalwana, M. Bennamoun, and A. S. Mian, "Attack to fool and explain deep networks." IEEE Transactions on Puttern Analysis and Machine Intelligence, 2021.
[12] N. Papernot, P. D. McDaniel, I. J. Goodfellow, S. Jha, Z. B. Celik, and A. Swami, "Practical black-box attacks against machine learning," in AsiaCCS, 2017.
[13] Goodfellow, J. Shlens. and C. Szegedy. "Explaining and harnessing adversarial examples." ICLR. 2015.
[14] Y. Dong, T. Pang. H. Su, and J. Zhu, "Evading defenses to transferable adversarial examples by translation- invariant attacks," " in CVPR, 2019.
[15] J. R. Wieland Brendel and M. Bethge. "Decision based adversarial attacks: Reliable attacks against black-box machine learning models." in ICLR, 2018.
[16] A. Kurakin, I. Goodfellow, and Bengio, "Adversarial examples in the physical world," ICLR Workshop, 2017.
[17] Y. Dong, F. Liao, T. Pang, H. Su, X. Hu, J. Li, and J. Zhu, "Boosting adversarial attacks with momentum," CVPR, 2018.
[18] L. Wu, Z. Zhu, C. Tai et al., "Understanding and enhancing the transfcrability of adversarial examples," arXiv preprint /802.0970009775 2018.
[19] Y. Dong, H. Su, B. Wu, Z. Li, W. Liu, T. Zhang, and J. Zhu, "Efficient decision-based black-box adversarial attacks on face recognition," " CVPR, 2019.
[20] T. Brunner, F. Diehl, M. T. Lc, and A. Knoll, "Guessing smart: Biased sampling for efficient black-box adversarial attacks," in ICCV, 2019, pp. 4958-4966.
[21] R. Shao, Z. Shi, J. Yi, P.-Y. Chen, and C.-J. Hsieh, "On the adversarial robustness of visual transformers," " arXiv preprint arXiv:2 15670, 2021.
[22] Y. F. Fu, S. Wu, Y. Lin et al., "Patch-fool: Are vision transformers always robust against adversarial perturbations?" ICLR 2022, 2021.
[23] G. Lovisotto, N. Finnie, M. Munoz, C. K. Mummadi, and J. H. Metzen, "Give me your attention: Dot- product attention considered harmful for adversarial patch robustness." in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022, pp. 15 254-11 243.
[24] Z. Wei, J. Chen, M. Goldblum, Z. Wu, T. Goldstein, and Y.-G. Jiang. "Towards transferable adversarial attacks on vision transformers." arXiv preprint
2021.
[25] M. Naseer, K. Ranasinghe, S. Khan, F. S. Khan, and F. Porikli, "On improving adversarial transferability of vision transformers." arXiv preprint arXiv:2106 04169, 2021.
[26] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, "Imagenet: A large-scale hierarchical image database," in CVPR. IEEE, 2009, pp. 255.

---

[27] O. Russakovsky, J. Deng. H. Su, J. Krause, S. Satheesh, S. Ma. Z. Huang, A. Karpathy, A. Khosla, M. Bermstein al., "Imagenet large scale visual recognition challenge." International Journal Computer Vision, vol. 115, no. pp. 211-252, 2015.
[28] W. Brendel, J. Rauber, A. Kurakin, N. Papernot, B. Veliqi. M. Salathé, S. P. Mohanty, and M. Bethge, "Adversarial vision challenge," arXiv preprint a80iv:1808. 01976, 2018.
[29] S. Paul and P.-Y Chen, "Vision transformers are rohust learners," 2022.
[30] Chen, M. Jordan, and M. J. Wainwright, "Hopkiiiittssskppppppptaaaa A query-efficient docision-basee attack," in 2020 ieee sympositan on security and privacy (sp). IEEE, 2020, pp. 1277-1294.
[31] Y. Shi, Y. Han, and Q. Tian, "Polishing decision- based adversarial noise with customized sampling." in CVPR, 2020, pp. 1038-103..
[32] T. Maho, T. Furon, and E, Le Merrer, "Surfree: a fäst surrogate-fre black-box attack," in CVPR, 2021, pp. 10 10430-14439
[33] M. Cheng, S. Singh, P. H. Chen, P.-Y. Chen, S. Liu, and C.-J. Hsieh, "Sign-opt: A query-efficient hard-label adversarial attack," in ICLR, 2019.
[34] R. Wightman, "Pytorch image models,"
2019.
[35] K. He, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition," in CVPR, 2016, pp- 770-778.
[36] C. Szegedy, V. Vanhoucke, S. loffe, J. Shlens, and Z. Wojna, "Rethinking the inception architecture for computer vision," in CVPR, 2016, pp. 2818-2826
[37] C. Szegedy, S. loffe, V. Vanhoucke, and A. A. Alemi, "Inception-v4, inception-resnc and the impact of residual connections on learning." in AAAL, vol. 4, 2017, p. 12.
[38] B. Zoph. Vasudevan. J. Shlens, and Q. V. Le, "Learning transferable architectures scalable image recognition." in CVPR, 2018, pp. 8697-8710.
[39] G. Huang. Z. Liu, and K. Q. Weinberger. "Densely connected convolutional networks," CVPR, pp. 2261- 2269, 2017.
[40] K. Simonyan and A. Zisserman, "Very deep convolutional networks for large-scale image recognition," in ICLR, 2015.
[41] J. Hu, Shen, and G. Sun, "Squuerreannd-exiitttion networks," in CVPR, 2018, pp. 7132-7141.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
12

---

(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "tb77CKzC_Q7", "reviewer": "Reviewer_6GeV", "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.", "questions": "* How is proposition 1 reflected in algorithm 1?\n* 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?\n* 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.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The proposed method is simple and straightforward to implement and is general enough to be applied on multiple types of classification models.\n+ 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.\n\nWeaknesses:\n- 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.\n- 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\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mFqRJxDrFrT", "reviewer": "Reviewer_wgUm", "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.", "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n1. This paper is the first to target decision-based black-box attacks for ViTs.\n\n2. 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.\n\n3. This paper is clearly written with a coherent logical flow.\n\n\n**Weakness**\n1. 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.\n\n2. 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.\n\n3. The experimental results lack enough explanation and analysis:\n- For baseline methods, can they achieve worse query efficiency or larger perturbation distances on ViTs than those on CNNs under a similar model complexity?\n- Does the proposed method achieve a more notable improvements on ViTs than those on CNNs under a similar model complexity?\n- How does the final removal strategy correlate with the noise sensitivity?\n\n4. Missing reference:\n\n[1] \"Patch-Fool: Are Vision Transformers Always Robust Against Adversarial Perturbations?\", Y. Fu et al., ICLR 2022.\n\n[2] \"Give Me Your Attention: Dot-Product Attention Considered Harmful for Adversarial Patch Robustness\", G. Lovisotto et al., CVPR 2022.\n\n[3] \"Reveal of Vision Transformers Robustness against Adversarial Attacks\", A. Aldahdooh et al., arXiv 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DoCPBHdg_B-", "reviewer": "Reviewer_zV4y", "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.", "questions": "please see the weakness", "limitations": "please see the weakness", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n1.\tThis 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.\n2.\tThe narrative of the paper is clear and the proposed method is effective, which can reduce the noise magnitude a lot. \n3.\tThe 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.\n\n[Weaknesses]\n1.\tThe minimum patch size can be one to be added in Table 4, which can be the comparison in the per-pixel setting.\n2.\tThe experiment about time cost can be added to verify the superiority of the PAR.\n3.\tThis 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Privacy and Security (e.g., consent)"]}, "extra_text": {}}, {"review_id": "86BRbyGdRD0", "reviewer": "Reviewer_SDVz", "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.  ", "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?\n2. 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?\n", "limitations": "No potential negative societal impact ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This paper is well-written and easy to follow.  \n2. 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.\n3. The experiments are extensive, it compares with different state-of-the-art methods on different architectures and datasets. \nPAR can combine with other decision-based methods and improve the performance. \n\nWeaknesses: \n1. 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?\n2. 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? \n3. In Table 1, 2, 3，It seems that the performance of PAR itself is not better than the SOTA methods. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept