BRUSLEATTACK: A QUERY-EFFICIENT SCORE- BASED BLACK-BOX SPARSE ADVERSARIAL ATTACK
Authors: Quoc Viet Vo
Ehsan Abbasnejad
Damith Ranasinghe
Venue: ICLR 2024 poster (2024)
Keywords: AI Safety
Trustworthy Machine Learning
Machine Learning Robustness
Adversarial Attacks
Primary area: societal considerations including fairness, safety, privacy

Abstract: We study the unique, less-well understood problem of generating sparse adversarial samples simply by observing the score-based replies to model queries. Sparse attacks aim to discover a minimum number—the $l_0$ bounded—perturbations to model inputs to craft adversarial examples and misguide model decisions. But, in contrast to query-based dense attack counterparts against black-box models, constructing sparse adversarial perturbations, even when models serve confidence score information to queries in a score-based setting, is non-trivial. Because, such an attack leads to: i) an NP-hard problem; and ii) a non-differentiable search space. We develop the BRUSLEATTACK—a new, faster (more query-efficient) algorithm formulation for the problem. We conduct extensive attack evaluations including an attack demonstration against a Machine Learning as a Service (MLaaS) offering exemplified by __Google Cloud Vision__ and robustness testing of adversarial training regimes and a recent defense against black-box attacks. The proposed attack scales to achieve state-of-the-art attack success rates and query efficiency on standard computer vision tasks such as ImageNet across different model architectures. Our artifacts and DIY attack samples are available on GitHub. Importantly, our work facilitates faster evaluation of model vulnerabilities and raises our vigilance on the safety, security and reliability of deployed systems.

Published as a conference paper at ICLR 2024
BRUSLEATTACK: A QUERY-EFFICIENT SCORE- BASED BLACK-BOX SPARSE ADVERSARIAL ATTACK
Viet Quoe Vo, Ehsan Abbasnejad, Damith C. Ranasinghe The University of Adelaide (viet. vo, ehsan. abbasne jad, damith www.aiinanniiinn. Badd de edu.
ABSTRACT
We study the unique, less-well understood problem of generating sparse adversar- ial samples simply by observing the score-bused replies to model queries. Sparse attacks aim discover a minimum number-the In caunded-perturbaan model inputs to craft adversarial examples and misguide model decisions. But, in contrast to query-based dense attack counterparts against black-box models, constructing sparse adversarial perturbations, even when models serve confidence score information to queries in a score- setting. non-trivial. Because, such attack leads to: i) NP-hard problem; and ii) non-differentiable search new, faster (more query efficient)
to
space. We develop the BRUSLEATTACK- Bayesian algorithm for the problem. We conduct extensive attack evaluations in- cluding an attack demonstration against a Machine Learning as Service (MLaaS) offering exemplified by Google Cloud Vision and robustness testing of adversar- ial training regimes and a recent defense against black-box attacks. The proposed attack scales achieve state-of-the-an attack success rates and query efficiency standard computer vision tasks such as ImageNet across different model ar- chitectures. Our artifacts and DIY attack samples are available on GitHub Im- portantly, our work facilitates, faster evaluation of model vulnerabilities and raises our vigilance on the safety, security and reliability of deployed systems.
INTRODUCTION
We are amidst an increasing prevalence of deep neural networks in real-world systems. So, our ability to understand the safety and security of neural networks is critical to our trust in machine intelligence. We have heightened awareness of adversarial attacks (Szegedy et al.! 2ra4)-craftin imperceptible perturbations in inputs to manipulate deep perception systems to produce erroneous decisions. In real-world applications such as machine learning as service (MLaaS) from Google Cloud Vision or Amazon Rekognition, the model is hidden from users. Only, access to model deci- sions (labels) or confidence scores are possible. Thus, crafting adversarial examples in black-box query-based interactions with model is both interesting and practical to consider.
Why Study Query-Based Sparse Attacks Under Score-Based Responses? Since confidence scores expose more information compared to model decisions, can expect fewer queries to elicit effective attacks and, consequently, the potential for developing attacks at scale under score-based settings. Various similarity measures-L, norms-are used quantitatively describe adversarial example perturbations. Particularly, l2 and Lo0 norm is used to quantify dense perturbations for attacks. In contrast, lo norm quantifies sparse perturbations aiming perturb a tiny portion of the input. While dense attacks are widely explored, the success of sparse-attacks, especially under score-based settings, has drawn much less attention and remains less understood (Croce et al. 2022). This leads to our lack of knowledge of model vulnerabilities to sparse perturbation regimes.
Why are Score-Based Sparse Attacks Hard? Constructing sparse perturbations is incredibly diffi- cult minimizing to norm leads to an NP-hard problem (Modas et al., 2019 Dong et al. (020) and a non-differentiable search space that is mixed (discrete and continuous) (Carlini & Wagner (017). Now, for given ly constraint number of pixels, need to search for both the optimal set of pixels to perturb in a source image and the pixel colors caass-flloa floats in [O, 1]. Solutions are harder, if we aim achieve both query efficiency and high altack success rate (ASR) for high resolution vision

---

Published as a conference paper at ICLR 2024
ResNet-50 (SIN)
Vision
Source image
ResNet-50
Transformer
Sparse Attack
Sparse Adversarial Example
Success
Predicted
Warplane"
Predicted as Target class
Query
Confidence
scores
Warplane
Model Query
Deep Learning
80 pixels
80 pixels
220 pixels
Model (MLaaS)
(0.16% sparsity)
(0.16% sparsity) (0.41% sparsity)
Figure 1: Targeted Attack. Malicious instances generated by BRUSLEATTACK with different perturbation budgets against three Deep Learning models on ImageNet. An image with ground-truth label Minibus misclassified as Warplane. Interestingly, in contrast to needing 220 pixels to mislead the Vision Trans- former, BRUSLEATTACK roquires only 80 perturbed pixels to fool ResNct-based models (more visuals in Appendix Rb. Evaluation against Google Cloud Vision is in Section and Appendix Q
tasks such as ImageNet. The only scalable attempt to the challenges, SPARSE-RS RS (Croce al. 2022 applies a stochastic search method to seek potential solutions.
Our Proposed Algorithm. We consider new formulation to cope with the problem and construct the new search
We propose a search for sparse adversarial example over an effective, lower dimensional search-space. contrast to the prior stochastic search and pixel selection method, we guide the search by prior knowledge learned from historical information of pixel manipulations (past experience) and informed selection of pixel level perturbations from our lower dimensional search space to tackle the resulting combinatorial optimization problem.
Contributions. Our efforts increase our understanding of less-well understood, hard, score-based, query attacks to generate sparse adversarial examples. Notably, only a few studies exist the robustness of vision Transformer (ViT) architectures to sparse perturbation regimes. This raises a critical concern over their reliable deployment in applications. Therefore, investigate the fragility of both CNNs and ViT' against sparse adversarial attacks. Figure demonstrates examples of our attack against models the ImageNet task while summarize main contributions below:
We formulate a new sparse attack-BRUs) BE JEATTACK-in the score-based setting. The algorithm exploits the knowledge of model output scores and our intuitions on: i) learning influential pixel information from historical pixel manipulations; and fi) informed selection of pixel perturbations based pixel dissimilarity between our search space prior and source image to accelerate the search for a sparse adversarial example.
As a afrst, investigate the robustness of ViT and compare its relative robustness with ResNet models on the nigh-resolution dataset Imagenet under score-based sparse settings.
We demonstrate the significant query efficiency our algorithm over the state-of-the-art counterpart in different datasets, against various deep learning models as well as defense mechanisms and Google Cloud Vision in terms of ASR & sparsity under 10K query budgets.
RELATED WORK
Non-Sparse (Dense) Attacks (12, (.). Extensive past works studied dense attacks in white-
box (Goodfellow al. 2014 Madry al., 2018 Carlini & Wagner 2017 Dong et al. 2018 8 Wong
et al. 2019 Xu et al. 2020) and black-box settings (Chen et al.] 2017 7 Tu et al. 2019 Liu et al.)
2019
Ilyas et al. 2019 Andriushchenko et al. 2020 Shukla et al. 2021 1 Vo et al. 2022b). Due to
non non-diiferentiable high-dimensional and mixed (continuous & discrete) search space encountered
in sparse settings, adopting these methods is non-trivial (see analysis in Appendix E) Recent work has explored sparse attacks in white-box settings (Papernot al.) 2016; Modas al. 2019: Croce
& Hein, 2019) Fan et al.) 2020; Dong et al.) 20200 Zhu et al. 20.11) Here we mainly review sparse attacks in black-box settings but compare with white-box sparse attack for interest in Section 4.2
2

---

Published as a conference paper at ICLR 2024
Decision-based Sparse Attacks (lo). Only few recent studies, POINTWISE (Schott et al. 2019) and SPARSEEVO (Vo et al. 2022a). have tackled the difficult problem of sparse attacks in decision- based settings. The fundamental difference between decision- based and score-based settings is the output information (labels vs scores) and the need for a target class image sample in decision- based algorithms. The label information hinders direct optimization from output information. So, decision-based sparse attacks rely on an image from target class (targeted attacks) and gradient- free methods. This leads different set of problem formulations. We study and demonstrate that sparse attacks formulated for decision-based settings do not lead to query- eeeey-efficient attacks in score-based settings in Section 4.2
Score-based Sparse Attacks (1)). A score-based setting seemingly provides more information than a decision-baset setting. But, the first attack formulations (Narodytska & Kasiviswanathan, 2017 Zhao et al. 2019, Croce & Hein 2019) suffer from prohibitive computational costs (low query efficiency) and do not scale to high-resolution datasets i.e. ImageNet. The recent SPARSE. random search algorithm in (Croce et al., 2022) reports the state-of-the-art, query-efficient, sparse attack and is a significant advance. But, large query budgets are still required to achieve low sparsity on high resolution tasks such as ImageNet in the more difficult targeted attacks.
PROPOSED METHOD
We focus on exploring adversarial attacks in the context of score-based and sparse settings. First, we present the general problem formulation for sparse adversarial attacks. Let x E [0, 1eexxxh be a normalized source image, where is the number of channels and w, h is the width and height of the image and y is its ground truth label-the source class. Let f(x) denote vector of all class probabilities--offte
ccore--from a victim model and f(r(=) denote the probability of class An attacker aims to search for an adversarial example ã E [0, 1] such that T can be misclassified by the victim model (untargeted setting) or classified as a target class Yurget (targeted setting). Formally, in targeted setting, for a given E, sparse attack aiming search for the best adversarial example xx can be formulated as a constrained combinatorial optimization problem:
x arg min (ff(),, Margee) s.t. | - Ello~ S B,
(1)
where loll is the to norm denoting the number of perturbed pixels, B denotes budget of perturbed pixels and L denotes the loss function of the victim model f's predictions. This loss may be different from the training loss and remains unknown to the attacker. In practice, we adopt the loss functions in (Croce et al. 2022), particularly cross-entropy loss in targeted settings and margin loss in untar- geted settings. The problem with Equation D the large search space as need search colors, float numbers in [0, 1]. for perturbing some optimal combination of pixels in the source image æ.
3.1 NEW PROBLEM FORMULATION TO FACILITATE A SOLUTION
Sparse attacks aim to search for the positions and color values of perturbed pixels; for a normalized image, the color value of each channel of RiX color value-can be a float number in [0, 1]. Consequently, the search space is enormous. Instead of searching in the mixed (discrete and continuous), nigh-dimensional search space, we consider turning the mixed search space problem into a dimensoimessional, discrete search space problem. Subsequently, we propose formulation that will aid the development of a new solution to the combinatorial search problem.
Proposed Lower Dimensional Search Space. We introduce simple but effective perturbation scheme. We uniformly sample, random, color image x' E {0, 1]exwxh 1hcchhh_which we call the synthetic color image-to define the color of perturbed pixels in the source image In this manner, each pixel is allowed to attain arbitrary values in [0, 1] for each color channel, but the dimensionality of the space is reduced to discrete space of size w X h. The resulting search space is eight times smaller than the perturbation scheme in SPARSE-RE RS (Croce et al. 2022) (see an analysis in Appendix H). Surprisingly, our proposal is incredibly effective, particularly high-resolution images such as ImageNet (we provide a comparative analysis with alternatives in Appendix [].
Search Problem Over the Lower Dimensional Space. Despite the lower-dimensional nature of the search space, a combinatorial search problem persists. As a remedy. we propose changing the problem of finding ã finding binary matrix u for selecting pixels to perturb in to construct an
3

---

Published as a conference paper at ICLR 2024
adversarial instance. To that end, we consider choosing a of pixels in the given image to be replaced by pixels from the synthetic color image x' E {0, 1 pxix These pixels are determined by binary matrix E 10,1] where Va = indicates pixel to be replaced. The adversarial image is then constructed as ă = uæx + (1 - u) where 1 denotes the matrix of all ones with di- mensions of u, and each element of corresponds one pixel of with channels. Consequently, manipulating each pixel of o corresponds to manipulating an element in u. Therefore, rather than solving Equation
[
we consider the equivalent alternative (proof shown in Appendix G):
u" arg min E(u)
s.t.
| S B,
(1 where E(u) = L(J(wa' + (1-1)) (1-u)a) )) Margat Although the problem in i combinatorial in nature and does not have polynomial time solution, the formulation facilitates the use of two simple intuitions to iteratively generate better solutions- sparse adversarial samples.
3.2
A BAYESTAN FRAMEWORK FOR THE to CONSTRAINED COMBINATORIAL SEARCH
Round
10
26
45
t 1-46
Pi
Perturbed Images
P
PI
P1
P1
P
255
P5
Loss
Bird
Bird
Bird
Dog
pialerier
portersuc
pankerice
posterice
pieleziar
proteniar
Dirichlet
probability densily over the simplex
pesteriar preterior ja or
A Sampling and Update illustration. The attack aims mislead a model into misclassi- fying a Bird image as Dog, Assuming that in round t - 1, an adversarial instance is classified as Bird and loss e = 1.8. We visualize three elements of posierior for simplicity. Let (PI.P2.P3 de- note three perturbed pixels with corresponding posterior parameters {a posterir .
Figure 2:
posterior .g posterior }. Assume
that in round f, two pixels P1.P2 remain while ps is replaced by pa because loss reduction is observed from 4.8 to 1.9. All {a (upuerrirr .a
posterior posterior posteriory are updated using Equation 6 but we visualize heen selected hefore, small in value learning to find better group of
at .44
{ar footerior oz2 postriorr 24 paserior). Since 04
posterice is new and has L + 45, while sampling
(and represented using colder colors). From perturbed pixels, a pasictior is updated. Because has a high influence on the model's prediction (represented using warmer colors). it is more likely to remain, while p2, p4 are more likely to be selected for replacement due to their lower impact the model decision. In round t 46, pixel Pa is replaced by ps because loss reduction is observed from 1.9 to 0.6. Now, the predicted label flipped from Bird Dog.
It is clear that some pixels impart more significant impact on the model decision than others. As such, given binary matrix u with a set of selected clements-rrpreseeniiee representing a candidate solution, we can expect some of these elements, altered, to be more likely result in an increase in the loss (()). Then, our assumption is that some selected elements must be hard to manipulate to reduce the loss, and as such, should be unaltered. Retaining these selected elements is more likely to circumvent a bad solution successfully. In other words, these selected elements may significantly influence the model's 's decision and are worth keeping. In contrast to a stochastic search for influential pixels, we consider learning the influence of each element based on the history of pixel manipulations.
The influence of these elements can be modeled probabilistically, with the more influential elements attaining higher probabilities. To this end, we consider categorical distribution parameterized by 0, because we aim to select multiple elements and this is equivalent to multiple draws of one of many possible categories. It then follows to consider Bayesian formulation learn O similar to Abbasnejad et al. (017). We adopt general Bayesian framework and design the new components and approximations needed to learn 9. We can expect a new solution, 2 (t), generated according to 0 to more likely outweigh the current solution and guide the future candidate solution towards pixel combination that more effectively minimizing the loss f(u). Next, we describe these components and defer the algorithm have designed, incorporating these components to Section 3.3
4

---

Published as a conference paper at ICLR 2024
Prior. In Bayesian statistics, the conjugate prior distribution of the categorical distribution is the Dirichlet distribution. Thus, we give 0 a prior distribution defined by a Dirichlet distribution with the concentration parameter as P(O; ax) == Dir(a).
Sampling ut) For > O, given solution-binary matrix (t-1)) O(0) we aim to: i) select and preserve highly influential selected elements (Equation B) and ii) draw new elements from unselected elements (Equation conditioned upon ((-11) jointly yield new solution u (Equation 5 Concretely, we can express this process follows:
and (t(t1) 0, respectively, to
(4) Cat(w @ u (1-1) =1,
(3)
qi
(()
9 B-b ~ Cat(q 00 (t-1) 0),
(6)
(4)
(f) [V (0) [V= 4 1
(5)
( E {0, 1-]xxxt, B denotes a total number of selected elements (a perturbation budget), Here U/ qi
b denotes the number of selected elements remaining unchanged, and V denotes logical OR operator.
Updating (()) (Using Our Proposed Likelihood). Finding the exact solution for the underlying parameters (+) of the categorical distribution in Equation3Jand Equation[4jto increase the likelihood of yielding a better solution for (t) in Equation is often intractable. Our approach is to find an estimate (()) by obtaining the expectation of the posterior distribution of the parameter, which is learned and updated over time through Bayesian inference. Notably, since the prior distribution of the parameter is a Dirichlet, which the conjugate prior of the categorical (i.e. distribution of u), the posterior of the parameter is also Dirichlet. Formally, at each step t O, updating the posterior and (tt) is formulated as follows:
= a iij $/ P(0 a u (t-1) gtt 1(t- Dir(a Pusteriir
posterior Pi
(6)
u ((() = ((t 10)))))))
(8)
where prror (0) is the initial concentration parameter, a Posterior aa) denotes the updated - 1. Here, 2 is
concentration parameter (illustration in Figure 2) and s!t) = ((a + 2n) + +))
small constant (i.e. 0.01) to ensure that the nominator and denominator are always non-zero (this smoothing technique is applied since the nominator and denominator can be zero when "never"
manipulated pixels are selected), a is the accumulation of altered pixel i, (i.e. u 0 and "/, (t-1) 1) when it leads to increase in the loss, i.e. g(t) > g(+-1), and n.
(t) is the accumulation
of selected pixel j.j in the mask (t). Formally,
(t) 0 and m!!)) can be updated follows:
if 8 2² ((-1) A u = 1 A 4 (-11
(9)
aid
otherwise
(1)
n
(t-1)
if otherwise
(1-1) u
ni
(1-1)
(10)
3.3 SPARSE ATTACK ALGORITHM FORMULATION WITH OUR BAYESIAN FRAMEWORK
Using the Bayesian framework for to constrained combinatorial search in Section 3.2 we devise our sparse attack (Algorithm D
illustrated in Figure 3 and discuss it detail as follows:
Initialization (Algorithm 2. Given a perturbation budget B and a zero-initialized matrix u. N first
solutions are generated by uniformly altering B elements of u to at random. The initial ()) is the solution incurring the lowest loss g(0), ((0) is the expectation of prior presented in Appendix M.3
Generation (Algorithm 3p. It is necessary here to balance exploration versus exploitation, in other optimization methods. Initially, to explore the search space, we aim to manipulate a large number of selected elements. When approaching an optimal solution, search for a solution in a region nearby a given solution and thus alter a small number of selected elements. Therefore, use the combination of power and step decay schedulers to regulate
aim at exploitation to
5

---

Published as a conference paper at ICLR 2024
Source Image
Synthetic Color Image x'
Dissimilarity Map M
Generation (Alp &
Black-box
S
Loss Computation
f
Dissimilarity Map Creation (Eq, 11)
glo
(Eq, 3.6, 12)
(Eq 21
(u gin)
(u (
Confidence score
Update (Agga
(0) (0))
gb
Initialization (Aigo.
(Eq
1. We aim to search for set of pixels to replace in the source image r by corresponding pixels in a synthetic color image x'. In the solution, binary matrix (+)) white and black colors denote replaced and non-replaced pixels of the source image, respectively. Instead of stochastic search, employ
Figure 3: BRUSLEATTACK algorithm (Algo.
Bayesian framework in [3.2 First, we aim to retain useful elements in the solution (*) by learning from historical pixel manipulations For this, we explore and learn the influence of selected elements by capturing it in the model 0 using our general Bayesian framework in (3.2 -darker colors illustrate the higher influence of selected elements (Algo. 4. Second, generate
pixel perturbations based on with the intuition that larger pixel dissimilarity between our search space x' and source image can possibly move the adversarial to the decision boundary faster and accelerate the search (Algo. 3)
Algorithm 1: BRUSLEATTACK
Input:
source image synthetic color image æ', source label y, target label Vargets model f query limit T, scheduler parameters m,, m2, initial changing rate λo
perturbation budget B, a number of initial samples N, concentration parameters o prior
Create Dissimilarity Map M using Equation 11
(0)
( ((0) <- INITIALIZATION(R;; a', V. Uurget; N₂ B)
t - 1, (0) 0, (0) + +u [0)
Calculate ((0) using arirr and Equation g
while < T and ()0)) + Yharger do
((t) + Am(t + mb))
(t) GENERATION(("") M, (1-1), 1110))
((9) + L(f(ul) + (1 (1) )x), Yhargor)
y(t) - arg max, f(rlu(()) x +1 )()))z))
u ((t)) 0(11), (t),, (!)) +- UPDATE (ul(t), e()) (t-1) g(t-1), aa))),))))))))))))))) ())
11
t 1+1
12 end while
13 return (0)
number of selected elements altered in round This scheduler formulated as (t m²),
where Åu is an initial changing rate, m., m2 are power and step decay parameters respectively. Concretely, we define a number of selected elements remaining unchanged as b [(1 B7.
Given a prior concentration parameter arior to generate a new solution in round t, we first find posterior in Equation 6 and estimate ((0) as in Equation 8 We then generate v.() and (( in Equation and Equation respectively. A new solution ()) can be then formed as in Equation 5 Nonetheless, the naive approach of sampling qr as in Equation is ineffective and achieves a low performance at low levels of sparsity as shown Appendix K When altering unselected elements that are equivalent to replacing non-perturbed pixels in the source image with their corresponding pixels from the synthetic color image, the adversarial instance moves away from the source image by distance. At a low sparsity level, since small fraction of unselected elements are altered, the adversarial instance able to take small steps toward the decision boundary between the source and employ
target class. To mitigate this problem (taking inspiration from (Brunner al.) 2019)) prior knowledge of the pixel dissimilarity between the source image and the synthetic color image. Our intuition is that larger pixel dissimilarities lead to larger steps. As such, it is possible that altering unselected elements with a large pixel dissimilarity moves the adversarial instance to the decision boundary faster and accelerates optimization. The pixel dissimilarity is captured by dissimilarity

---

Published as a conference paper at ICLR 2024
map M as follows:
M Ee | x'd
(11)
3
where e denotes a channel of a pixel. In practice, to incorporate M into the step of sampling q: Equation Dis is changed to the following:
an Cat(q g M, (t-1) = 0)
(12)
Update (Algorithm The generated solution (+) is associated with a loss ((0) given by the loss
function in Equation 2 This then used update postterior (Equation 6nd illustration in Figure 2 and the accepted solution as the following:
(1)
if el9 < ((-1))
(t)
(13)
(t-1) otherwise
EXPERIMENTS AND EVALUATIONS
Attacks and Datasets. For comprehensive evaluation of BRUSLEATTACK we compose of evalua- tion sets from CIFAR-10 (Krizhevsky et al.), STL-10 (Coates et al., 2 and ImageNet (Deng) jet al. (009). For CIFAR- 10 and STL-10, 0, we select 9,000 and 60,094 different pairs of the source image and target class respectively. For Ima TmageNet, we randomly select 200 correctly classified test images evenly distributed among 200 random classes from ImageNet. To reduce the compu- tational burden of the evaluation tasks in the targeted setting, five target classes randomly chosen for each image. For attacks against defended models with Adversarial Training, we randomly select 500 correctly classified test images evenly distributed among 500 random classes from ImageNet. We compare with the
SPARSE-RS (Croce et al.) 2022).
Models. For convolution based networks,
models based on ofate-of-the-ant architecture ResNet-(He (He et al. 2016) including ResNet18 achieving 95.28% test accuracy on CIFAR- 0,
R obtaining 83.5% test accuracy STI.1 0, pre-trained ResNet-50 (Marcel & Rodriguez 2010 with 76.15% Top-1 test accuracy, pre-trained Stylized ImageNet ResNet-50-ResNete 76. 72% Top-1 test accuracy (Geirhos et al. 2019) on ImageNet. For the attention- based network, we use pre-trained ViT-B/16 model achieving 77.91% % Top-1 test accuracy (Doso-) vitskiy et al. 2021 For robust ResNet-50 models we use adversarially pre-trained /2/ loc models (12-At and Tx AT) (Logan et al. 2019) with 57.9% and 62.42% clean test accuracy respectively.
(SIN~ a
Evaluation Metries. We define sparsity metric as the number of perturbed pixels divided by the total pixels of an image. To evaluate the performance of an attack, we use Attack Success Rate (ASR). A generated perturbation is successful if it can yield an adversarial example with sparsity below given sparsity threshold, then ASR is defined as the number of successful attacks over the entire evaluation set at different sparsity thresholds. We measure the robustness of a model by the accuracy of that model under attack at different query limits and sparsity levels.
4.1 ATTACK TRANSFORMERS & CONVOLUTIONAL. NETS
We carry out comprehensive experiments on ImageNet under the targeted setting to investigate sparse attacks against various Deep Learning models (standard ResNet-50, ResNet-50 (SIN) and ViT). The results for the targeted and untargeted setting are detailed in Appendix B Additional results on STL-10 and CIFAR-10 are provided in
Convolutional- Models. Figure 4a and 4p show that, at sparsity 0.4% (~= 224x224
200
BRUSLEATTACK achieves slightly higher ASR than SPARSE-RS while at sparsity 1.0% (N 224x224), ). our attack significantly outweighs SPARSE-RS at different queries. Particularly, from 2K to 6K queries, BRUSLEATTACK obtains about 10% higher ASR than SPARSE-RS. Interestingly, with small query budget of 6K queries, BRUSLEATTACK achieve ASR higher than 90%.
Attention-based Model. Figure 4 demonstrates that at sparsity of 0.4% BRUSLEATTACK achieves marginally higher ASR than SPARSE-RS whereas at sparsity of 1.0% our attack demonstrates

---

Published as a conference paper at ICLR 2024
a)
ResNet-50 50
b)
ResNet-50 (SIN)
VIT
d)
Model Robustness
100
100
ResNett50 (SIN)
20
Accuracy (%)
ResNet-50
75
ASR (16)
92
20
Sparse-RS
1.0%
20
Our Attack
15K 0K
8K 10K
3K
Queries
Queries
Queries
Queries
Figure 4: Targeted setting on ImageNet. a-c) ASR of BRUSLLFATTACK and SPARSE-RS against different models at sparsity levels of 0.4% (dashed lines) and 1.0% (solid lines); d) Accuracy of different models against BRUSLEATTACK at sparsity levels (0.4% dash, 1.0% solid; in-between sparsity levels in Appendix (
significantly better ASR than SPARSE-RS. At 1.0% sparsity and with query budgets above 2K, our method achieves roughly 10 % higher ASR than SPARSE-RS. Overall, our method consistently outperforms the SPARSE-RS in terms of ASR across different query budgets and sparsity levels.
The Robustness of Transformer versus CNN. Figure Fi demonstrates the robustness of ResNet- 50, ResNet-50 (SIN) and ViT models to adversarially sparse perturbation in the targeted settings. We observe that the performance of all three models degrades as expected. Although ResNet-50 (SIN) is more robust to several types of image corruptions than the standard ResNet-50 by far as shown in (Geirhos et al., 2019). it is as vulnerable its standard counterpart against sparse adversarial attacks. Interestingly, y, our results in Figure illustrate that ViT much less susceptible than ResNet family against ad adversarially sparse perturbation. At the sparsity of 0.4% and 1.0 %, the accuracy of ViT is pragmatically higher than both ResNet models under our attack across different queries. Interestingly, BRUSLEA merely requires small query budget of 4K to degrade the accuracy of both ResNet models to the same accuracy of ViT at 10K queries. These findings can be explained that ViT's receptive field spans over the whole image (Naseer et al., 202T) because some attention heads of ViT in the lower layers pay attention to the entire image (Paul & Chen (022). It is thus
capable of enhancing relationships between various regions of the image and is harder to be evaded than convolutional based models if a small subset of pixels is manipulated.
4.2
COMPARE WITH PRIOR DECISION- -BSEE AND ln ADAPTED ATTACK ALGORITIMM
In this section, we compare our method (10K queries) with baselines-SpAa SPA-SSS--AAAREEOOOO (Vo et al., 2022a). Pointwise (Schott
ResNet-50 50
100
Our Attack
et al. 2019) (both 20K queries) and PGD, (Croce & Hein 2019 Croce et al.) 2022 (white-box) in targeted settings.
75
ASR (96)
10K
PGD,
Figure 5 demonstrates that BRUSLEATTACK significantly out-
performs SPARSEEvO and PGD, For SPARSEEVO and Point- wise, this is expected because decision-based attacks and have only access to the hard label. For PGD,, it is surprised but un- derstandable since in the lo project step, PGD, has to identify the minimum number of pixels required for projecting such that the perturbed image remains adversarial but to the best of our knowledge. there is no effective projection method to iden- tify the pixels that can satisfy this projection constraint. Soly- ing lo projection problem also lead to another ha-hard prob- lem (Modas al. 2019 Dong et al. 2020) and hinders the adoption of dense attack algorithms to the lo constraint. More- over, the discrete nature of the In ball impedes its amenability to continuous optimization (Croce et al. 2022). Additional re- sults for lo adapted attacks on CIFAR-10 O are presented in Appendix
50
20K
25
SparseEvo Pointwise
0.0
0.2
0.4
0.6
0.8 1.0
Sparsity (%)
Figure 5: Targeted attacks the ImageNet task against ResNet-
50. ASR comparisons between BRUSLEATTACK and baselines:
i SPARSHEVO and POINTWISE (SOTA algorithms from decision-
based settings): ii) PGD, (whitebox).
4.3 ATTACK DEFENDED MODELS
BRUSLEATTACK versus SPARSE-RS. RS. In this section, we investigate the robustness of sparse attacks (with a budget of 5K queries) against adversarial training- based models using Projected Gradient Descent (PGD) proposed by (Madry et al. 2018 highly effective defense mechanisms against adversarial attacks (Athalye et al. 2018) and Random Noise Defense (RND) (Qin et al.) 2021 a recent defense method designed for black-hox attacks. The robustness of the attacks is measured by
8

---

Published as conference paper at ICLR 2024
the degraded accuracy of defended models under attacks at different sparsity levels. The stronger an attack is, the lower the accuracy of a defended model is. Table T shows that BRUSLEATTACK consistently outweighs SPARSE-RS RS against different defense methods and different sparsity levels. Additional results on CIFAR-10 10 0 provided in Appendix
Table 1: Robustness comparison (lower + is stronger) against undefended and defended models employing widely applied adversarial train regimes and the recent RND balckbox attack defence the Ima ImageNet task. Robustness measured by the degraded accuracy of models under attacks at different sparsity levels.
Spunity
Undetended Model
IT
le-AT
SPARSE- RS
BRU BLETTAK
SPARSE-RS
BR BRUSLEATIE LEATTCC
SPARSE-RS
DRUSLEAFTACE
SPARSE-RS
Bid HIUSLEAFIAN
24.0%
88.4%
0.08%
13.27
6.8%
26.8%
24.4%
79,25%
82.255
72.6%
0.12%
7.6%
2.6%
19.0%
18.4%
75.8%
73.8%
73.6%
61.0%
0.16%
5.2%
1.0%
16.6%
14.8%
71.4%
69.25%
64.8%
51.4%
12.2%
66.4%
Undefended and Defended Models. The results in Table [ shows the accuracy of undefended ver- sus defended models against sparse attacks across different sparsity levels. In particular, under BRUSLEATTACK and sparsity of 0.2%, the accuracy of ResNet-50 drops to 1% while -AT model able to obtain 11.8% However, l-AT model and RND strongly resist adversarially sparse pertur- bation and remains high accuracy around 66.4% and 42.6 % respectively. Therefore, AT model and RND more robust than Loc AT model to defense model against sparse attacks.
Clean Images
STOP
Adverserial Examples
Car
Flower
PizeTzuck
Vehicie
YLS1 1iSlipper Mushcoco www..noooppppppccoooo sign
Camera
Match
bud didin
STOP
Windox
ViPepper
kindow
Mindow
P.Plant Tandacape Material
Circle Jewel1ry
Querles
4861
Sparse-RS
BruSLeAttack
3312
>5000
>5000
3812
>5000
2901
>5000
>d000
1834
S89
.9
328
395
Figure 6: Demonstration sparse attacks against GCV in targeted settings with budget of SK queries and sparsity of 0.5% ~ 224x221 BRUSLEATTACK can yield adversarial examples for all clean images with less queries than SPARSE-RS while SPARSE-RS fails yield adversarial examples for Mushroom, Camera, Natch, & Building images. Illustration on GCV API (online platform) is shown in Appendix
250
4.4 ATTACK DEMONSTRATION AGAINST A REAL-WORLD SYSTEM
To illustrate the applicability and efficacy of BRUSL against real-world systems, we attack the Google Cloud Vision (GCV) provided by Google. Attacking GCV is considcrably challenging since 1) the classifier returns partial observations of predicted scores with varied length based on the input and 2) the scores are neither probabilities (softmax scores) nor logits (Myas et al. 2018 Guo et al.) 2019). To address these challenges, we employ the marginal loss between the top label and the target label and successfully demonstrate our attack against GCV. With budget of 5K queries and sparsity of 0.5%, BRUSLEATTACK can craft a sparse adversarial example of all given images mislead GCV whereas SPARSE-RS fails to attack four of them as shown in Figure 6
CONCLUSION
In this paper, we propose a novel sparse Btteck-BRUSLEAATACCK We demonstrate that when at- tacking different Deep Learning models including undefended and defended models and in different datasets, BRUSLEATTACK consistently achieves better performance than the state-of fotte-of-the-eee method in terms of ASR at different query budgets. Tremendously, in high-resolution dataset, our compre- hensive experiments show that BRUSLEATTACK is remarkably query-efficient and reaches higher ASR than the current fate--ofttheart sparse attack in score-based settings.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work is supported in part by Google Cloud Research Credits Program and partially supported by the Australian Research Council (DP240103278), The attack is named in honor of Bruce Lee, a childhood hero-ours is Query- Eerrc-Efficient Score-Basee Black- Box Adversarial Attack built upon our proposed Bayesian framework BRUSLEATTACK.
REFERENCES
Ehsan Abbasnejad, Anthony Dick, and Anton van den Hengel. Infinite variational autoencoder for semi-super learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5888-5897, 2017.
Maksym Andriushchenko. Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square At- tack: a query-efficient black-box adversarial attack via random search. European Conference on Computer Vision (ECCV), 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. International Conference on Machine Learning (ICML), 2018.
Thomas Brunner, Frederik Diehl, Michael Truong Le, and Alois Knoll. Guessing smart: Biased sampling for efficient black-box adversarial attacks. The IEEE International Conference Com- puter Vision (ICCV), 2019.
N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. IEEE Symposium on Security and Privacy, 2017.
J. Chen, M. I. Jordan, and M. J. Wainwright. Hopskipjumpattack: A query-efficient decision-based attack. IEEE Symposium on Security and Privacy (SSP), 2020.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order op- timization based black-box attacks to deep neural networks without training substitute models. ACM Workshop on Artificial Intelligence and Security (AlSec), pp. 15-26, 2017.
Adam Coates, Honglak Lee, and Andrew Y. Ng. TAnalysis of Single Layer Networks in Un- supervised Feature Learning. International Conference on Artificial Intelligence and Statis- fics(AISTATS), 2011.
Francesco Croce and Matthias Hein. Sparse and imperceivable adversarial attacks. International Conference on Computer Vision (ICCV), 2019.
Francesco Croce and Matthias Hein. Mind the box: 11-apgd for sparse adversarial attacks on image classifiers. International Conference on Machine Learning, 2021.
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flam- marion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: standardized adver- sarial robustness benchmark. arXiv preprint arXiv:20
2020.
Francesco Croce, Maksym Andriushchenko, Naman D. Singh, Nicolas Flammarion, and Matthias Hein. Sparse-RS: A Versatile Framework for Query-Efficieet Sparse Black-Box Adversarial At- tacks. Association for the Advancement of Artificial Intelligence (AAAI), 2022.
Deng, W. Dong, R. Socher, L.J. Li, K. Li, and I.. Fei-Fei. ImageNet: A large-scale hierarchical image database. Computer Vision and Pattern Recognition (enognnition(CVPR)... 2009.
X. Dong, Chen, J. Bao, C. Qin, L. Yuan, W. Zhang, N. Yu, and D. Chen. GreedyFool: Distortion- Aware Sparse Adversarial Attack. Neural Information Processing Systems (NeurIPS), 2020.
Y. Dong, F. Liao, T. Pang, H. Su, J. Zhu, X. Hu, and J. Li. Boosting adversarial attacks with mo- mentum. In 2018 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9185-9193, 2018.
10

---

Published as a conference paper at ICLR 2024
Y. Dong, X. Yang, Z. Deng, T. Pang. Z. Xiao, H. Su, and J. Zhu. Black-box detection of back- door attacks with limited information and data. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. International Conference Learning Recognitiion(CLLR) 2021.
Yanbo Fan, Baoyuan Wu, Tuanhui Li, Zhang Yong. Mingyang Li, Zhifeng Li, and Yujiu Yang. Sparse adversarial attack via perturbation factorization. European Conference Computer Vision (ECCV), 2020.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix Wichmann, and Wieland Brendel. Imagenet-trained cnns biased towards texture; increasing shape bias im- proves accuracy and robustness. International Conference on Learning Recognition(ICLR 2019.
lan J Goodfellow, Jonathan Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference Learning Recognition(ICLLR) 2014.
C. Guo, J.R. Gardner, Y. You, A. G. Wilson, and K.Q. Weinberger. Simple Black-box Adversarial Attacks, International Conference on Machine Learning (ICML), 2019.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. International Conference on Machine Learning (ICML), 2018.
Andrew Iyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. International Conference on Learning Recognifion(ICLRR) 2019.
Yulun Jiang, Chen Liu, Zhichao Huang, Mathieu Salzmann, and Sabine Süsstrunk. Towards stable and efficient adversarial training against l bounded adversarial attacks. In International Confer- ence on Machine Learning. PMLR, 2023.
A. Krizhevsky, V. Nair, and G. Hinton. Cifar-10 (canadian institute for advanced research). URL html
/tetp://www.r cs http://wwww..oo....oo.ooooo wtt.://tto..doarrrr//./////
Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. QEBA: Query-Efficient Boundary-Based Blackbox Attack. Computer Vision and Pattern Recognition (CVPR), 2020.
Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong. signsgd via zeroth-order oracle. In International Conference on Learning Representations, 2019.
Engstrom Logan, Ilyas Andrew, Salman Hadi, Santurkar Shibani, and Tsipras Dimitris. Robustness http://aaabbouuuteese....
(python library), 2019. URL httppss://g.cchu..cmoo/
Aleksandar Madry, Aleksander adnd Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning /ecognitiio(/CI.R) 2018.
S. Marcel and Y. Rodriguez. Torchvision the machine-vision package of torch. Proceedings of the 18th ACM International Conference on Multimedia, pp. 1485-1483 2010. URL https: 7/doi www.:org/10. / 1et..1115/11878
1874254
Apostolos Modas, Seyed-Mohsen Moosavi-Dezfee and Paseal Frossard. Sparsefool: few pixels make a big difference. Computer Vision and Pattern Recognition (CVPR), 2019.
Nina Narodytska and Shiva Kasiviswanathan. Simple Black-Boss Adversarial Attacks on Deep Neu- ral Networks. Computer Vision and Pattern Recognition( CVPR) workshop, 2017.
Muzammal Naseer, Kanchana Ranasinghe, Salman Hameed Khan, Munawar Hayat, Fahad Shahbaz Khan, and Ming- Yang. Intriguing properties of vision transformers. Neural Information Processing Systems (NeurIPS), 2021.
11

---

Published as a conference paper at ICLR 2024
N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami. The limitations of deep learning in adversarial settings. Security and Privacy, 2016 IEEE European Symposium, pp- 372-387, 2016.
Sayak Paul and Pin-Yu Chen. Vision transformers are robust learners. Association for the Advance- ment of Artificial Intelligence (AAAI), 2022.
Zeyu Qin, Yanbo Fan, Hongyuan Zha, and Baoyuan Wu. Random noise defense against query-based black-box attacks. Neural Information Processing Systems (NeurIPS), 2021.
Lukas Schott, Jonas Rauber, Matthias Bethge, and Wicland Brendel. Towards the first adversarially robust neural network model mnist. International Conference on Learning Recognition (CCL)))))) 2019.
R.R. Selvaraju, A. Das, R. Vedantam, M. Cogswell, D. Parikh, and D. Batra. Grad-CAM: Vi- sual Explanations from Deep Networks via Gradient-based Localization. The IEEE International Conference on Computer Vision (ICCV), 2017.
Satya Narayan Shukla, Anit Kumar Sahu, Devin Willmott, and Zico Kolter. Simple and efficient hard label black-box adversarial attacks in low query budget regimes. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery; Data Mining, 2021.
J. Su, D. V. Vargas, and K. Sakurai. One pixel attack for fooling deep neural networks. IEEE Trans- actions on Evolutionary Computation, 23:828-841, 2019, doi: 10.1 1011111...20099299000000
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. International Conference on Learning Recognition/ICLR), 2014. URL https:tts////c. /ttp:v/aaavviv//aa//aie org/ /ttos//111. 6199
Chun-Chen Tu, Paishun Ting, Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. AutoZOOM: Autoencoder-Basse Zeroth Order Optimization Method for Attacking Black-Bor Neural Networks. Association for the Advancement of Artificial Intelligence (AAAI), 2019.
Quoc Viet Vo, Ehsan Abbasnejad, and Damith C. Ranasinghe. Query efficient decision based sparse attacks against black-box deep learning models. International Conference on Learning Recogni- tion (ICLR), 2022a.
Quoe Viet Vo, Ehsan Abbasnejad, and Damith C. Ranasinghe. RamBoAttack: A robust query efficient deep neural network decision exploit. Network and Distributed Systems Security (NDSS) Symposium, 2022b.
Xingchen Wan, Vu Nguyen, Huong Ha, Binxin Ru, Cong Lu, and Michael A. Osborne. Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Daan Wierstra, Tom Schaul, Jan Peters, and Juergen Schmidhuber. Natural evolution strategies. In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), 2008
Eric Wong, Frank R. Schmidt, and J. Zico Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. In Proceedings of the 36th International Conference on Machine Learning ICML, 2019.
Qiuling Xu, Guanhong Tao, Siyuan Cheng, Lin Tan, and X. Zhang. Towards feature space adver- sarial attack. 2020.
Zhao, S. Liu, P. Chen, N. Hoang, K. Xu, B. Kailkhura, and X. Lin. On the design of black-box adversarial examples by leveraging gradient-free optimization and operator splitting method. In 2019 JEEF/CVF International Conference on Computer Vision (ICCV), 2019.
Mingkang Zhu, Tianlong Chen, and Zhang Wang. Sparse and Imperceptible Adversarial Attack via Homotopy Algorithm. International Conference on Machine Learning (ICML), 2021.
12

---

Published as a conference paper at ICLR 2024
OVERVIEW OF MATERIALS IN THE APPENDIX
We provide brief overview of the extensive set of additional experimental results and findings in the Appendices that follows. Notably, given the significant computational resource required to mount blackbox attacks against models and our extensive additional experiments, we have employed CIFAR-10 0 for the comparative studies. Importantly, our empirical results have already established the generalizability of our attack across CNN models, ViT models, three datasets and Google Cloud Vision.
1. A list of all notation used in the paper (Appendix Aj.
2. Evaluation of score-hased sparse attacks on ImageNet (targeted settings at sparsity levels between and including 0.4% and 1.0%; and untargeted settings) (Appendix (B)
3. Evaluation of score-based sparse attacks on STL-10 to demonstrate generalization (Ap-
pendix (
4. Evaluation of score-based sparse attacks on CIFAR-10 0 demonstrate generalization (Ap- pendix D)
5. Additional evaluation of attack algorithms adopted for sparse attacks (lo attacks) (Ap-
pendix H
6. Comparing BRUSLEATTACK and SPARSEEVO to supplement the results Figure (Ap-
pendix E.1
7. Demonstrating the impact of the Bayesian framework based search (Comparison with an adapted SPARSE-RS using our synthetic images. Notably, this addresses the feedback in the Meta Review) (Appendix E.2)
8. A Discussion Between BRUSLEATTACK (Adversarial Attack) and B3D (Black-box Back- door Detection) (Appendix E.6
9. Additional evaluation of score-based sparse attacks against state of the art robust models from Robustbench (Appendix IF)
Proof of the optimization reformulation (Appendix
11. An analysis of the search space reformulation and dimensionality reduction. (Appendix H).
12. An analysis of different generation schemes for synthetic images considered (Ap- pendix D]
13. Study of BRUSLEATTACK performance under different random seeds (Appendix (T.
14. An analysis of the effectiveness the dissimilarity map employed in our proposed attack algorithm (Appendix K).
15. Detailed information on the consistent set of hyper-parameters employed, initialization value for arior and computation resources used (Appendix L.
16. The notable performance invariance to hyper-parameter choices studies with CIFA-10 and ImageNet (Appendix[M)
17. Additional study of employing different schedulers (Appendix
18. Detailed implementation and pseudocodes of different components of BRUSLEATTACK (Appendix(0) O
19. Detailed information on the evaluation protocols BRUSLEATTACK (Appendix(P)
20. Visualizations sparse attack against Google Cloud Vision (Appendix Q
21. Additional visualizations of dissimilarity maps and sparse adversarial examples (Ap-
pendix R).
13

---

Published as a conference paper at ICLR 2024
A
NOTATION TABLE
In this section, we list all notations in Table to help the reader better understand the notations used in this paper.
Table 2: Notations used in the paper.
Notation
Description
Source image
Synthetic color image
Source class
Muurget f(x)
Target class
Softmax scores
LQG or eQ
Loss function
A budget of perturbed pixels
A number of selected elements remaining unchanged
u(t)
A binary matrix to determine perturbed and unperturbed pixels
((()
A binary matrix to determine perturbed pixels remaining unchanged
g(o)
A binary matrix to determine new pixels to be perturbed
prior
An initial concentration parameter
posterior
An updated concentration parameter
Parameter of Categorical distribution
Dir(a)
Dirichlet distribution
Cat(O) O)
Categorical distribution
Ao
An initial changing rate
mi
A power decay parameter
m2
A step decay parameter
M
Dissimilarity Map
w, h, c
Width, height and number of channels of an image
B SPARSE ATTACK EVALUATIONS ON IMAGENET
Table 3: ASR at different sparsity levels across different queries (higher is better). A comprehensive compar- ison among different attacks (SPARSE-RS and BRUSLEATTACKK) against various Deep Learning models ImageNet the targeted setting.
RpaNet-50
ResNet-50 (STN)
VIT BRUSLEATTACE
Query
SPARSE-RS RS
BRUSLEAFTACK SPARSE-RS RS BRUSLEATTACK SPARSE-RS
Sparsity = 0.4%
4000
49.9%
57.3%
40.5%
47.8%
21.5%
26.0%
65.5%
31.8%
37.3%
8000
74.1%
77.3%
63.3%
66.6%
39.6%
43.9%
10000
79.1%
82.7%
68.5%
70.9%
45.2%
49.0%
Sparsity 0.6%
4000
59.6%
75.1%
49.7%
66.2%
30.8%
40.7%
6000
74.0%
86.3%
65.6%
77.8%
43.7%
52.0%
8000
85.0%
90.3%
77.6%
83.4%
52.2%
61.0%
10000
90.9%
93.0%
84.3%
87.0%
61.7%
67.3%
Sparsity 0188%
4000
63.8%
84.3%
56.3%
76.7%
38.2%
49.4%
6000
79.2
90.6%
71.1%
87.0%
50.2%
63.4%
8000
87.9%
94.3%
81.9%
91.0%
60.0%
72.2%
10000
93.4%
96.4%.
89.6%
92.4%
69.6%
79.0%
Sparsity 1.0%
59.2%
43.1%
56.8%
6000
82.1
94.2%
75.6%
91.4%
56.1%
72.4%
8000
89.8%
96.8%
83.8%
94.0%%
65.6%
81.3%
91.0%
95.5%
74.3%
86.8%
14

---

Published as a conference paper at ICLR 2024
Targeted Settings. Table shows the detailed ASR results for sparse attacks on high-resolution dataset ImageNet the targeted settings shown Section 4.1 The results illustrate that the proposed method is consistently better than SPARSE-RS -RS across different sparsity levels from 0.4 %
to 1.0 %.
B)
ResNet-50
b) ResNet-50 (SIN)
VIT
d)
Model Robustness
120
Accuracy [%)
ResNet-50 (SIN)
ResNet-50
ASR (96)
Sparse-RS Our Attack
0.2%
26
18
0.04%
0K
IK
* Queries
0K
2
4K
SK
1K
4<
5K
1K
2K Queries
3K
Queries
Queries
Figure 7: a-c) Untargetted Setting. ASR versus the number of model queries against different Deep Learning models sparsity levels (0.4%. 1.0%); d) Accuracy versus the number of model queries for model robustness comparison against BRUSLEATTACK, in the untargeted setting and sparsity levels (0.04%
224x224
0.2% 224x224
Untargeted Settings. In this section, we verify the performance of sparse attacks against different Deep Learning models including ResNet-50, ResNet-50 (SIN) and ViT models in the untargeted setting up 5K query budget. use an evaluation set of 500 random pairs of an image and a target class to conduct this comprehensive experiment. Our results in Table I and Table show that BRUSLEATTACK is marginally better than SPARSE-RS across different sparsity levels when attacking against VIT. For ResNet-50 and ResNet-50 (SIN), lower sparsity or lower query limits, our proposed attack outperforms SPARSE-RE RS while at higher query budgets or higher sparsity levels, SPARSE-RA RS is able obtain slightly lower ASR than method. In general, BRUSLEATTACK consistently outperforms SPARSE-R RS and only needs 1K queries and sparsity of 0.2% (100 pixels) achieve above 90% ASR against both ResNet-50 and ResNet-50 (SIN).
Table 4: ASR different sparsity levels across different queries (higher is better). A comprehensive compari- son among different attacks (SPARSE-Re and BRUSLEATIACK) and various DL models on ImageNet in untargeted setting.
Query
R5
ResNet-
SPARSE-RS
BRUSLEATTACK SPARSE-RS BRUSLEATTACK SPARSE-RS
BRUSLEATTACK
Sparsity = 0.04%
1000
52.4%
$1.0%
55.4%
29.0%
31.2%
2000
58.4%
65.0%
59.2%
63.6%
36.2%
37.4%
3000
61.8%
68.4%
63.8%
67.0%
41.0%
41.2%
4000
65.4%
70.4%
68.2%
44.2%
44.4%
5000
66.4%
72.4%
66.6%
69.2%
46.4%
46.7%
Sparsity 0108%
1000
72.8%
77.4%
73.8%
75.8%
47.2%
50.6%
2000
80.4%
83.4%
57.6%
61.0%
3000
84.6%
89%
84.4%
87.0%
64.2%
67.8%
4000
85. 6%
90.4%
6%
88.2%
69.65 69.6%
72.6%
5000
86.8%
90.8%
87.0%
88.6%
72.6%
74.6%
Spunsity
0.16%
1000
87.0%
89.4%
87.6%
88.0%
64.8%
68.6%
2000
90.8%
95.2%
92.0%
94.0%
78.4%
81.4%
3000
93.4
95.6%
85.0%
86.4%
4000
94.4%
97.6%
96 25% 96.8%
97.0%
87.0%
89.2%
5000
94.8%
98.4%
97.4%
89.8%
90.0%
Spansity = 0.2%
TO00
88.6%
92.2%
90.2%
91.0%
71.2%
73.0%
2000
92.4%
96.6%
94.4%
95.0%
82.6%
84.4%
3000
94.4
97.8%
95.8 35.8%
96.4%
87.4%
89.8%
4000
95.2%
98.4%
97.2%
90.8%
91.0%
5000
95.4%
98.6%
98.2%
98.4%
92.2%
92.6%
Relative Robustness Comparison among Models. To compare the relative robustness different
models, we evaluate these models against our attack. Table Figure confirm observations
15

---

Published as a conference paper at ICLR 2024
about relative robustness of Re (SIN) the standard ResNet-550 in the targeted setting (pre- sented in Section 4.1). It turns out that ResNet-50 (SIN) is as vulnerable as the standard ResNet-50 even though it is robust against various types of image distortion. Interestingly, VIT is more robust than its convolutional counterparts under sparse attack. Particularly, at sparsity of 0.2% and 2K queries, while the accuracy of both ResNet-50 and ResNet-50 (SIN) is down about 5%, VIT is still able to remain ASR around 15%.
C SPARSE ATTACK EVALUATIONS ON STL10 10 (TARGETED SETTINGS)
We conduct more extensive experiments on STL-10 in the targeted setting with all correctly clas- sified images the evaluation set (60,094 sample pairs and image size 96). provides a comprehensive comparison for different attacks across different sparsity levels ranging from 0.1 1% (10 pixels) to 0.54% (50 pixels). Particularly, with only 50 pixels, BRUSLEATTACK needs solely 3000 queries to achieve ASR beyond 92% whereas SPARSE- RS only reaches ASR of 89.64%.
Table 5: ASR (higher is better) at different sparsity levels in targeted settings. A comprehensive comparison between SPARSE-RS RS and BRUSLEATTACK against ResNer9 on a full evaluation set from STL-10.
Methods
1=1000
Q=2000
Q=3000
Q=4000
Q=1000
Q=2000
Q=3000
Q=4000
Sparsity 0.222%
Sparsity 0..4%
SPARSE-RS RS
53.82%
61.65%
65.84%
68.0%
73.34%
81.47%
85.24%
87.49%
BRUSLEATTACK
57.69%
65.05%
68.8%
71.22%
78.21%
85.03%
88.31%
90.26%
Sparsity
0.33%
Sparsity
0.54%
SPARSE-KS RS
65.6%
74.0%
78.0%
80.65%
78.66%
86.31%
89.64%
91.61%
BRUSLEATTACK
70.27%
77.55%
81.16%
83.42%
83,29%
89.78%
92.55%
94.08%
D SPARSE ATTACK EVALUATIONS ON CIFAR-10 (TARGETED SETTINGS)
In this section, conduct extensive experiments in the targeted setting to investigate the robustness of sparse attacks on an evaluation set of 9,000 pairs an image and a target class from CIFAR- 10 (image size 32) Sparsity levels range from 1.0% (10 pixels) to 3.9% (40 pixels). Table 6 provides a comprehensive comparison of different attacks in the targeted setting. Particularly. with only 20 pixels (sparsity of 2.0 %). BRUSLEATTACK needs solely 500 queries to achieve ASR be- yond 90% whereas SPARSE-RS only reaches ASR of 89.21%. Additionally, with only 300 queries, BRUSLEATTACE is able reach above 95% of successfully crafting adversarial examples with solely 40 pixels. Overall, our attack consistently outperforms the SPARSERRS in terms of ASR and this confirms our observations on STL-10 and ImageNet.
Table 6: ASR (higher is better) at different sparsity thresholds in the targeted setting. A comprehensive com- parison among different attacks (SPARSE-RS RS and BRUSLEATTACK) against ResNet18 on an evaluation set of 9,000 pairs of image and a target class from CIFAR-10.
Methods
Q=100
20200
Q=300
Q=400
5=500
Sparsity = 1.0%
SPARSE-RS
36.22%
50.6%
58.17
62.59%
66 66.26%
BRUSLEATTACK
42.32%
54.73%
61.4%%
65.33%
68.21%
Sparsity 2.0%
SPARSE-RS
60.51%
76. 76.1%
83.13% 84.84%
86.89%
89.21%
BRUSLEATTACK
66.01%
79.19%
88.27%
90.24%
Sparsity = 2.9%
SPARSE-RS
71.29%
85.67% 88.22%
91.21%
94.28%
95.78%
BRUSLEATTACK
75.54%
92.91%
95.2%
96.59%
Sparsity = 3.9%
SPARSE-RS
75.91%
90.21%
94.78% 95.43%
96.97%
97.98%
BRUSLEATTACK
80.44%
91.24%
97.4%
98.48%
16

---

Published as a conference paper at ICLR 2024
E COMPARING BRUSLEATTACK WITH OTHER ATTACKS ADAPTED FOR SCORE-BASED SPARSE ATTACKS FOR ADDITIONAL BASELINES
E.1 ADDITIONAL EVALUATIONS WITH DECISION-BANE BASED SPARSE ATTACK METHODS
In this section, we carry out a comprchensive experiment on CIFAR-2 10 in the targeted setting (more difficult attack). In our experimental setup, the source image and target classes (1000 images distributed evenly in 10 different classes against target classes) compare BRUSLEATTACK (500 queries) with SPARSEEVO (2k queries) introduced in (Vo et al. 2022a). We compare ASR of different methods across different sparsity thresholds. The results in Figure demonstrate that our attack significantly outperforms SparseEvo. This is expected because EvorseEvo is decision based attack and has only access to predicted labels.
evaluation set of 9000 different pairs of
ResNet- 1eeeet118/IFFAR----
100
Our Attack
75
ASR (%)
500
PGD
50
0
2K
25
SparseEvo
HSIA
20K
0
2
4
Sparsity (%)
Figure Targeted attacks CIFAR-10 against ResNet-18. ASR comparisons between BRUSLEATTACK and baselines SPARSE-RS adapted Io-HSJA (decision- based settings); ii) PGD, (whitebox).
Alternative Loss. We acknowledge that Vo al.) (202aa) may point out an alternative fitness function based on output scores by replacing optimizing distortion with optimizing loss. However, they did not evaluate their attack method with an alternative fitness function in score-based setting. Employing this alternative fitness function may not obtain low sparsity level because minimizing Binary
the loss does not surely result in a reduction in the number of pixels. Additionally, Differential Recombination (BDR) in (Vo et al.] (222aa is designed for optimizing lo distortion not loss objective (i.e. alters perturbed pixels to non-perturbed pixels which is equivalent minimizing distortion). Hence, naively adapting SPARSEEVO (Vo et al. 2022a) to score-based settings may not work well.
To demonstrate that, conduct experiment CIFAR-10 using the same experimental setup (same evaluation set of 9000 image pairs and a query budget of 500) described above.
First approach, we adapted the attack method in (Vo et al. 2022a) to the score- based setting with an alternative fitness function for minimizing loss based on the output scores. We observed this attack always fails to yield an adversarial example with sparsity level below 50%.
Second approach, we adapted SPARSEEVO by employing the alternative fitness function, synthetic color image and slightly modifying BDR. Our results Table 7 show that the adapted SPARSEEVO can create sparse adversarial examples but is unable to achieve comparable performance to BRUSLEATTACK.
Overall, even with significant improvements, the sparse attack proposed (o et al. 2022a) with alternative fitness function does not achieve as good performance BRUSLEATTACK with low query budget.
Clarifying Differences Between BRUSLEATTACK and SPARSEEvO (Decision-Based Sparse Attack). No et al.] (2022a) develops an algorithms for a sparse attack but assumes a decision- based setting. We compared agianst the attack method and provided results in Figure 5 in the main
17

---

Published as a conference paper at ICLR 2024
Table 7: ASR comparison between proposal and SPARSEEVO (Altemative Loss) CIFAR-10.
Sparsity
Our Proposal
SPARSEEVO (Alterattive Loss)
1.0%
68.21%
54.78%
2.0%
90.24%
68.75%
2.9%
96.59%
74.0%
3.9%
98.48%
78.56%
article. Although both works aim to propose sparse attacks, key differences exist, as expected; explain these differences below:
While both works discuss how they reduce dimensionality (a dimensionality reduction scheme) leading to reduction in search space from C' x H x W to H x W, Vo et al. (2022a) neither propose a New Problem Formulation nor give proof of showing the equiv- alent between the original problem in Equation (1) and the New Problem Formulation in Equation (2) as we did in Section 3.1 and Appendix G
Our study and Vo et al. (2022a) propose similar terms binary matrix u versus binary vec- tor v as well an interpolation between æ and x'. However, binary vector æ in (Vo et al., (2022a) evolves to reduce the number of 1-bits while binary matrix u in our study maintains a number of 1-elements during searching for solution.
We can find a similar notion of employing a starting image (a pre-selected image from target class) in (Vo et al.) 2022a) or synthetic color image (pre-defined by randomly generating) in our study. However, is worth noting that applying a synthetic color image Vo et al. (2022a) does not work in the targeted setting. For instance, to the best of knowledge, there is no method can generate a synthetic color image that can be classified target class the method in (Vo et al. (022a) is not able employ synthetic color image to inialize a targeted attack. In contrast, employing a starting image as used in (Vo et al. (202a)) does not result in query-efficiency shown in Table especially at low sparsity levels.
Overall, although the score-based setting is less strict than the decision-based setting, our study is a simplified version of Vo al. (2022a).
Table 8: A comparison ASR between our proposal (Synthetic Color Image) and employing a starting image as in Vo et al. 2022a) on CIFAR- 10.
Sparsity
Our Proposal
Use starting image
1.0%
68.21%
62.68%
2.0%
90.24%
87.17%
2.9%
96.59%
94.37%
3.9%
98.48%
97.17%
E.2 IMPACT OF THE BAYESIAN FRAMEWORK BASED SEARCH (ADAPTED SPARSE-RS USING SYNTHETIC IMAGES)
In this section, we conduct an experiment on ImageNet and in targeted settings to compare the performance of our method and adapted SPARSE-RO RSS employing synthetic images. Specifically, we replace the update step in SPARSE-RS by fixing the colors to be changed to the ones in synthetic image. We employ the same evaluation dataset as discussed Section 4.2
The results in damossgde that adapted SPARSE-RS is less query-efficient than BRUSLEAT- TACK and even the original SPARSE-RS. In order words, the adapted SPARSE-RS does not benefit from space reduction by employing synthetic images. A possible reason is that the stochastic pixel selection scheme in SPARSE-RO RS does not leverage historical information on pixel manipulation to determine high and low-influnntial pixels for preservation replacement. Therefore, solely em- ploying synthetic images without our proposed learning framework based on historical information regarding pixel manipulation is not found to achieve high query efficiency.
18

---

Published as a conference paper at ICLR 2024
Tabbee 9: ASR different sparsity levels different query budgets (higher is better). A comprehensive comparison among different attacks (SPARSE-RE RS and BRUSLEATTACK against various Deep Learning mod- els on ImageNet in the targeted setting.
Query
SPARSE-RS
SPARSE- R$ (Synthetic Images)
BRUSLEATTACK
Sparsity 0.4%
4000
49.9%
49.2%
57.3%
6000
65.5%
63.5%
69.4%
8000
74.1%
73.6%
77.3%
10000
79.1%
79.3%
82.7%
Sparsity = 0.6%
4000
59.6%
58.7%
75.1%
6000
74.0%
73.8%
86.3%
8000
85.0%
85.0%
90.3%
10000
90.9%
90.0%
93.0%
Sparsity 0.8%
4000
65.8%
62.9%
84.3%
6000
79.2
78.7%
90.6%
8000
87.9%
87.7%
94.3%
10000
93.4%
92.9%
96.4%
Sparsity = 1.0%
4000
69.3%
67.3%
88.6%
6000
82.1
81.8%
94.2%
8000
89.8%
89.7%
96.8%
10000
94.3%
93.8%
97.7%
E.3 to ADAPTATIONS OF DENSE ATTACKS
Adapted Attacks (White-box). To place the blackbox attack results into context by using whitebox baseline and to provide a baseline for blackbox attack adaptations to lo, we explore strong white-box ly attack. We used PGD, (Croce & Hein, 2019] the attack adaptation of the well-known PGD (Madry et al.] (2018) attack. To this end. we compare BRUSLEATTACK with white-box adapted lo attack PGD, using the same evaluation from CIFAR- 10 as decision-based attacks.
The results in Figure X demonstrate that our attack significantly outperforms PGD, low sparsity threshold and is comparable to PGD, at high level of sparsity. Surprisingly, our method outweighs white-box. adapted lo attack PGDo- It is worth noting that there is no effective projection method to identify the pixels that can satisfy sparse constraint and solving the lo projection problem also en- counters an NP-hard problem. Additionally, the discrete nature of the ly ball impedes its amenability to continuous optimization (Croce al. 2022).
Adapted 4o Attacks (Decision-baseed, Black-bbx)), It is interesting to adapt l2 attacks such as HSJA (Chen al. 2020 QEBA (Li al. 2020), CMA-ES (Dong et al., 2020) method for face recog- nition tasks to 4n attacks. Consequently, we adopted the HSJA method to an lo constraint algorithm conduct a study. For 4H-HAA we follow the experiment settings and adapted 4o-HSJA in (Vo et al.) 2022a) and refer to (Vo et al. 2022a) for more details. Notably, the same approach could be adopted for QEBA (Li al.) 2020). The results Table TO below illustrate the average sparsity for 100 randomly selected source images, where each image was used to construct sparse adversarial sample for the different target classes on CIFAR- hence we conducted 900 pairs. The average sparsity across different query budgets higher than 90% even up 20K queries. Therefore, the ASR always 0% low levels of sparsity (i.e. 4%) (shown in Figure 8). These results confirm the findings in (Vo al. 2022a) and demonstrate that (S-HSJA (20K queries) is not able to achieve good sparsity (lower is better) when compared with attack method. Consequently, applying la projection to decision- baased dense attacks does not yield a strong sparse attack.
called 4--SJJ
attacks or used 900 source-image wwage-t--target-clleee
Similar to the problem of PGDo, adapted HSJA has determine projection that minimizes lo (the minimum number pixels) such that the projected instance is still adversarial. To the best of knowledge, method in decision-based setting is able to effectively determine which
19

---

Published as a conference paper at ICLR 2024
pixels can be selected to be projected such that the perturbed image does not cross the unknown decision boundary of the DNN model. Solving this projection problem may also lead to another NP-hard problem (Modas et al. 2019 Dong et al. 2020) and hinders the adoption of these dense attack algorithms to the lo constraint. Consequently, any adapted method, such as HSJA or other dense attacks, is not capable of providing an efficient method to solve the combinatorial optimization problem faced in sparse settings.
Table 10: Mcan sparsity at different queries for targeted setting. A sparsity comparison between Lu HS-HSJA on a set of 100 image pairs on CIFAR-10.
Queries
4000
8000
12000
16000
20000
To HSJA
93.66%
94.73%
95.88%
96.74%
96.74%
E.4 COMPARING BRUSLEATTACK WITH ENE-PIXEL ATTACK
In this section, we conduct an experiment to compare BRUSLFATTACK with the One-Pixel At- tack (uu et al. (2019). We conduct experiment with 1000 correctly classified images by ResNet18 on CIFARIO in untargeted settings (notably the easier attack, compared to targeted settings) using ResNet18 These images are evenly distributed across 10 different classes. We compare ASR be- tween our attack and One-Pixel at different budgets e.g. one, three and five perturbed pixels. For One-Pixel attack] we used the default setting with 1000 queries. To be fair, set the same query limits for our attack. The results in Table I1 show that our attack outperforms the One-Pixel attack across one, three and five perturbed pixels, even under the easier, untargeted attack setting.
Table 11: ASR comparison (higher is stronger) between One-Pixel and BRUSLEATTAN against ResNet18 on C F AR- 0.
Perturbed Pixels
One-Pixcl
BRUSLEATTACK
pixel
19.5%
27.9%
3 pixel
41.9%
69.9%
pixel
62.3%
86.4%
E.5 BAYESIAN OPTIMIZATION
We are interested in the application of Bayesian Optimization for nigh-dimensional, mix search space. Recently, (Wan et al., 202T) has introduced CASMOPOLITAN, a Bayesian Optimization for categorical and mixed search spaces, demonstrating that this method is efficient and better than other Bayesian Optimization methods in searching for adversarial examples in score-based settings. Therefore, we study and compare method with CASMOPOLITAN in the vision domain and the application of seeking sparse adversarial examples. We note that:
CASMOPOLITAN solves problem direetly by searching for altered pixel positions and the colors for these pixels. In the meanwhile, method aims address problem 2 which is reformulated to reduce the dimensionality and complexity of the search space significantly. In general, CASMOPOLITAN aims search for both color values and pixel positions, whilst BRUSLEATTACK only seeks pixel locations.
To handle high dimensional search space in an image task, CASMOPOLITAN employs different downssanping//usaapping techniques. It first downscales the image and searches over low-dimensional space, manipulates and then upscales the crafted examples. Un- like CASMOPOLITAN, our method-BB BRUULEEATACEE by downsampling the original search space but only seeks pixels in image (source im- age) and replaces them with corresponding pixels from a synthetic color image (a fixed and pre-defined image) (see Appendix H for our analysis of dimensionality reduction).
not reduce dimensionality
20

---

Published as a conference paper at ICLR 2024
CASMOPOLITAN is not designed to learn the impact of pixels on the model decisions but treats all pixels equally, whereas BRUSLEATTACK aims to explore the influence of pixels through the historical information of pixel manipulation.
R8sNet-18/ CIFAR-10
80
CASMOPOLITAN
Our Attack
60
ASR (%)
40
20
0
0
2
3
Sparsity (%)
Figure 9: Targeted attacks on CIFAR-10 with query budget of 250. ASR comparisons hetween
BRUSLEATTACK and CASMOPOLITAN (Bayesian Optimization).
We use the code provided in Wan et 2021) and follow their default settings. We evaluate both BRUSLEATTACK and CASMOPOLITAN on an evaluation set of 900 pairs of a source image and a target class from CIFAR-10 10 (100 correctly classified images distributed evenly in 10 different classes versus the 9 other classes as target classes for each image) with query budget of 250. The results in Figure D show that BRUSLEATTACK consistently and pragmatically outperforms CAS- MOPOLITAN across different sparsity levels. This is because:
The mixed search space in the vision domain, particularly in sparse adversarial attacks, is still extremely enormous even if downsampling to a lower dimensional search space. is because CASMOPOLITAN still needs to search for a color value for each channel of each pixel from large range of values (see Appendix H for our analysis of dimensionality reduction).
Searching in low-dimensional search space and upscaling back to the original search space may not provide an effective way yield a strong sparse adversarial perturbation. This is because manipulating pixels in a lower dimensional search space may not have the same influence on model decisions as manipulating pixels in the original search space. Additionally, some indirectly altered pixels stemming from upsampling techniques may not greatly impact the model decisions.
E.6 A DISCUSSION BETWEEN BRUSLEATTACK (ADVERSARIAL ATTACK) AND B3D (BLACK- BOX BACKDOOR DETECTION)
Natural Evolution Strategies (NES). A family of black-box optimization methods that learns a search distribution by employing an estimated gradient its distribution parameters Wierstra al. (2008); Dong et al. (0011). NES was adopted for score-based dense (12 and 1.o norms) attacks in Ilyas al. (2018) since they mainly adopted a Gaussian distribution for continuous variables. How- ever, solving the problem posed in sparse attacks involving both discrete and continuous variables leads to an NP-hard problem Modas et al. (2019): Dong al. 2020). Therefore, naively adopting
NES for sparse attacks is non-trivial.
The work B3D Dong et al. (202T), in a defense for a data poisoning attack or backdoor attack, proposed an algorithm to reverse-engineer the potential Trojan trigger used to activate the backdoor injected into a model. Although the method motivated by NES and operates in score-based setting involving both continuous and discrete variables, with sparse attack problem, they are designed for completely different threat models (backdoor attacks with data poisoning versus adver- sarial attacks). Therefore it is hard to make direct comparison. However, more qualitatively, there
21

---

Published as a conference paper at ICLR 2024
number of key differences between our approach and those relevant elements in Dong et al. 2021.
Method and Distribution differences: Dong et al. (2021) learns a search distribution deter- mined by its parameters through estimating the gradient on the parameters of this search distribution. In the meantime, our approach is to learn a search distribution through Bayesian learning. While Dong et al. (2021) employed Bernoulli distribution for work- ing with discrete variables, we used Categorical distribution to search discrete variables.
2. Search space (larger vs, smaller): B3D searches for a potential Torjan trigger in an enor- space it requires search for pixels' position and color. Our approach reduces the search space and only searches for pixels (pixels' position) to be altered so our search space is significantly lower than the search space used in Dong al. (2021) if the trigger size is the same as the number of perturbed pixels.
3. Perturbation pattern (square shape vs. any set of pixel distribution): Dong et al. 2021) aims to search for trigger which usually has a size of 1, 2 is a small square. In contrast, our attack aims to search for set of pixels that could be anywhere an image and the number of pixels could be varied tremendously (determined by desired sparsity). Thus, the combinatorial solutions in a sparse attack problem can be larger than the one in Dong et al. (202T) (even when we equate the trigger size to the number of perturbed pixels).
x 3 so the trigger shape
4. Query efficiency (is primary objective vs. not an objective): Our approach aims to search for a solution in a query-effciiency manner while it not clear how efficient the method to reverse-enginees trigger.
F EVALUATIONS AGAINST 12, lo ROBUST MODELS FROM ROBUSTBENCH AND 4 ROBUST MODELS
Table 12: A robustness comparison (lower | stronger) between SPARSE-RS and BRUSLEATTACK against undefended and defended models employing loc, la robust models on CIFAR-10. The atlack robustness measured by the degraded accuracy of models under attacks at different spansity levels.
Undefended Model
Loc Robust Model
1 Robust Model
Sparsity
SPARSE-RS
BRUSLEATTACK
SPARSE-RS RS
BRUSLEATTACK
SPARSE-RS
BRUSLEATTACK
0.39%
26.5%
24.2%
65.9%
65.0%
84.7%
84.2%
0.78%
7.8%
6.4%
48.1
46.0%
70.6%
68.3%
1.17%
2.5%
2.0%
38.1% 1%
35.1%
57.6%
54.3%
1.56%
0.6%
0.6%
28.8%
26.4%
44.4%
43.8%
12, loc Robust Models. To supplement our demonstration of sparse attacks (BRUSLEATTACK and
SPARSE-RS) against defended models on ImageNet in Section 4.3
we consider evaluations
against SoTA robust models from RobustBenct (Croce al. 2020 CIFAR-10, 0. We eval- uate the robustness of sparse attacks (BRUSLEATTACE) LEATTACK and SPARSE-RS) against the undefended model ResNet-18 and two pre-trained robust models as follows:
12 robust model:
This model is top-7 robust model (over 20 robust models) in the leaderboard of robustbench.
loc robust model: "Gowal2021 (Gooal2021Improv/iii 1mproving-70-16--60
100m". This model is a top-5 robust model (over 67 robust models) in the leaderboard of robustbench.
We use 1000 samples correctly classified by the pre-trained robust models and evenly distributed across 10 classes on CIFAR-10. We use a query budget of 500. We compare the accuracy of differ- ent models (undefended and defended models) under sparse attacks across range of Sparsity from 0.39% to 1.56%. Notably, defended models are usually evaluated in the untargeted setting to show their robustness. The range of sparsity in the untargeted setting is usually smaller than the range of sparsity used in the targeted setting. Thus, in this experiment, we use a smaller range of sparsity
22

---

Published as a conference paper at ICLR 2024
than the one used in the targeted setting. Our results in Table 12 show that BRUSLEATTACK out- performs SPARSE- RS when attacking undefended and defended models. The results on CIFAR-10 also confirm observations on ImageNet.
1 Robust Models. We also evaluate our attack method's robustness against 1 robust models. There two methods AA-II Croce & Hein (2021) and Fast-EG-1 Jiang et al. (2023) for training 4 robust models. Although Croce & Hein (021) and Jiang et al. (2023) illustrated their robustness
against attacks, Fast-EG-1 is the current state-of-the-art method (as shown in Diang et al. (2023). Therefore, we chose the 1 robust model trained by the Fast-EG-1 method for our experiment. In this experiment, we use 1000 images correctly classified by I1 pre-trained mode on CIFAR-10. These images are evenly distributed across ten classes. To keep consistency with previous evaluation, we also use a query budget of 500 and compare the accuracy of the robust model under sparse attacks. The results in Table show that our attack outperforms BRUSLEATTACK across different sparsity levels. Interestingly. 1 robust models are relatively more robust to sparse attacks then other adversarial training regimes in Table 12 this could be because lo bounded perturbations are enclosed in the 11-noo norm ball.
Table 13: A robustness comparison (lower is stronger) between SPARSE-RS and BRUSLEATTACK against undefended and defended models employing 4 robust models on CIFAR-10. The attack robustness is mea- sured by the degraded accuracy of models under attacks at different sparsity levels.
Undefended Model
4 1y-Rousst Model
Sparsity
SPARSE-RS BRUSLEATTACK
SPARSE-RS
BRUSLEATTACK
0.39%
26.5%
24.2%
86,6%
85.8%
0.78%
7.8%
6,4%
75.8%
74.8%
1.17%
2.5%
2.0%
68.5%
64.8%
1.56%
0.6%
0.6%
59.4%
55.9%
G REFORMULATE THE OPTIMIZATION PROBLEM
Solving the problem in Equaion I lead to an extremely large search space because of searching folors-floaat numbers in [0. fo-for for perturbing some pixels. To cope with this problem, reduce the search space by synthesizing a color image x' E {0, 1 that is used to define the color for perturbed pixels in the source image (see Appendix H). ii) employ a binary matrix T
E {0, 1 |exh to determine positions of perturbed pixels in æ.
When selecting pixel, the colors of all three-pixel channels are selected together. Formally, an adversarial instance & can be constructed as follows:
= (1 u)x uxx
(14)
Proof of The Problem Reformulation. Given source image E [0, 1]exwxh and synthetic color image x' E (0, exxxxh, (0,1xxxxxh, From Equation 14 we have the following:
a = (1 - u)x + ux
(1 u) x = ux'
uv (1 u)a (1 u.) a ux.
(1 u (i xx) uu 5.)
We consider two cases for each pixel here:
1. If unj = 0: then (1 - 42) Z2.j) = 0. thus ž1j Zi.j
2. If Wijj = 1: then wij(x1, - ir O. thus Tj.j o|{j
Therefore, manipulating binary vector is equivalent manipulating f according 14 Hence, optimizing v") is equivalent to optimizing L(f((1 u)x + ux'),y").
hhapss//gtthu..com//Rl /FastAdv...
23

---

Published as a conference paper at ICLR 2024
H ANALYSIS OF SEARCH SPACE REFORMULATION AND DIMENSIONALITY REDUCTION
Sparse attacks aim to search for the positions and color values of these perturbed pixels. For nor- malized image, the color value of each channel of a pixel-RGB color value-can can be a float number in [0, 1] the search space is enormous. The perturbation scheme proposed in (Croce et al. 2022 can be adapted to cope with this problem. This perturbation scheme limits the RGB values to a set {0, }) so pixel has eight possible color codes {000, 001, 010, 011, 100, 101, 110, 111} where each digit of a color code denotes a color value of a channel. This scheme may result in notice- able perturbations but does not alter the semantic content of the input. However, this perturbation scheme still results in a large search space because it grows rapidly with respect to the image size. To obtain more compact search space, we introduce simple but effective perturbation scheme. In this scheme, we uniformly sample at random a color image x' {0, 1 1 synthetic color image-to define the color of perturbed pixels in the source image æ. Additionally, we use binary matrix for selecting some perturbed pixels in z and apply the matrix to x' to extract color for these perturbed pixels as presented in Appendix G Because x' is generated once advance for each attack and has the same size æ, the search space is eight times smaller than using the perturbation scheme in (Croce et al. 2022). Surprisingly, our elegant proposal is shown to be incredibly effective, particularly in high-resolution images such as ImageNet
Synthetic color image. Our attack method does not optimize but pre-specify a synthetic color image x' by using our proposed random sampling strategy in our algorithm formulation. This synthetic image is generated once, dubbed a one-time synthetic color image, for each attack. We have chosen to generate it once rather than optimizing it because:
We aim to reduce the dimensionality of the search space to find and adversarial example. Choosing to optimize the color image would lead to a difficult combinatorial optimization problem.
Consider what we presented in Section 3.1
To solve the combinatorial optimization problem in Equation [1] we might search a color value for each channel of each pixel-a float number in [0,1] and this search space is enormous. For instance, if we need to perturb n pixels and the color scale is 2nh the search space is equivalent to C exxxxx>>>>>
To alleviate this problem, we reformulate problem in Equation [ and proposed a search over the subspace {0, 1]exuxh, However, the size of this search space is still large. To further reduce the search space, we construct a fixed search space-a pre-defined synthetic color image x' E {0, 1]cxwxh for each attack. The search space is now reduced to C" " It is generated by uniformly selecting the color value for each channel of each pixel from {0, 1J at random (as presented in Appendix H []
In addition, a pre-defined synthetic color image x'--a fixed search space- our Bayesian algorithm. If keeping optimizing the synthetic color image x', our Bayesian algorithm has to learn and explore a large number of parameters which is equivalent to Cexn C2mxexuxi and might not learn useful information fast enough to make the attack progress.
Perhaps, most interestingly, our attack demonstrates that solution for the combinatorial optimization problem in Equation [ can be found in a pre-defined and fixed subspace.
Searching for pixels' position and color concurrently. In general, changing the color of the pixels in searches led to significant increases in query budgets. In our approach, we aim to model the influence of each pixel bearing a specific color, probabilistically, and learn the probability model through the historical information collected from pixel manipulations. So, we chose not to first search for pixels' position and search for their color after knowing the position of pixels but we aim to do both simultancously. In other words, the solution found by our method is a set of pixels with their specific colors.
I DIFFERENT SCHEMES FOR GENERATING SYNTHETIC IMAGES
In this section, we analyze the impact of different schemes including different random distributions, maximizing dissimilarity and low color search space.
24

---

Published as a conference paper at ICLR 2024
Different random distributions. Since the synthetic color images randomly generated, can leverage Uniform or Gaussian distribution or our method, Because the input must be within [o. 1], we sample x' from 2400, 1] or (u, o²) where μ 0.5, 0.17. For method, uniformly sample at random a color image x' E {0. 1 1oxxxx In order words, each channel of a pixel receives binary value from Uniform distribution is better than Gaussian distribution but it is worse than our simple method. The experiment illustrates that different schemes of generating the synthetic color image random have different influences on the performance of BRUSLEATTACK and our proposal outweighs other common approaches across different sparsity levels. Particularly low query budgets (i.e. up to 300 queries) and low perturbation budgets (i.e. sparsity up to 3%), our proposal outperforms the other two by a large margin. Therefore, the empirical results show our proposed scheme more effective in obtaining good performance. Most interestingly, as pointed out by HSJA authors (Chen ict al. 2020), the question of how best to select an initialization method or in their case initial target image remains open-ended question worth investigating.
1. The results in Table T show that generating synthetic color image
Target setting. ASR (higher is better) at different sparsity thresholds in the targeted setting. A com- prehensive comparison among different strategies of synthetic color image generation to initialize BRUSLEAT- TACK attack against ResNet18 on CIFAR-10.
Table 14:
Methods
Q=100
Q=200
Q=300
Q=400
Q=500
Sparsity
1.0%
Uniform
32.18%
41.68%
48.09 %
52.38%
35.48%
Gaussian
21.29%
29.87%
35.0 %
38.72%
41.53%
Ours
42.32%
54.73%
61.49%
65.33%
68.21%
Sparsity = 2.0%
Uniform
54.04%
69.08%
76.48%
80.91%
83.76%
Gaussian
40.02%
55.17%
63.2
68.58%
72.28%
Ours
66.01%
79.19%
84.84%
88.27%
90.24%
Sparsity
2.9%
Uniform Gaussian Ours
65.82%
80.62%
87.84%
91.39%
93.38%
52.4%
69.91%
78.42
83.24%
86.39%
75.54%
88.22%
92.91%
95.2%
96.59%
Sparsity
3.9%
Uniform Gaussian
73.04%
86. 86.32%
92.33%
95.02%
96.34%
61.0%
77.26%
84.88
89.63%
91. 91.94%
Ours
80.44%
91.24%
95.43%
97.4%
98.48%
Maximizing dissimilarity. There may be different ways to implement your suggestion of gener- ating synthetic color image x' that maximize the dissimilarity between the original image x and a'. But to the best our knowledge, no effective method can generate a random color image x' that maximize its dissimilarity with æ.
Our approach to this suggestion is find the inverted color values of x by creating an inverted image Pinvent to explore color values different from æ. We then find the frequency of these color values (in each R. G. B channel) in Tinvent Finally, we generate a synthetic color image x' such that the more frequent color values (in R, G, B channels) in Winvent will appear more firequenll in s'. By employing the frequency information of color values in æ, we can create a synthetic color image x' that is more dissimilar to In practice, implementation is described as follow:
Yield the inverted image Zinven 1 ac Note that a E [0, 1 1exwxx
Create histogram of pixel colors (for each R, G, B channel) have their frequency in Pavert-
Then we randomly generate a synthetic color image based on the frequency of color values that allows us maximize the dissimilarity.
show that an approach of maximizing the dissimilarity (using frequency information) yields better performance low sparsity levels discussed in Appendix K How- ever, it does not result in better performance at high levels of sparsity if compared with our proposal.
The results Table 15
25

---

Published as a conference paper at ICLR 2024
Table 15:
ASR comparison between using synthetic color image uniformly generated at random (our pro- posal) and maximizing dissimilarity on CIFAR-10.
Sparsity
Proposal
Maximizing Dissimilarity
1.0%
68.21%
70.16%
2.0%
90.24%
90.75%
2.9%
96.59%
95.78%
3.9%
98.48%
97.85%
Low color search space. Instead of reducing the space from color codes to a fixed random one, we consider choosing between 2-4 random colors. That would allow us to search not only in the position space of the pixels but also in their color space without increasing search space significantly. The results in Table show that expanding color space leads to larger search space. Consequently, this approach may require more queries to search for a solution and results in low ASR, particularly with small query budget.
Table 16: ASR comparison between using fixed random color search space (our proposal) and two four random color search space on CIFAR-10.
Sparsity
Our Proposal
Two Random Colors
Four Random Colors
1.0%
68.21%
60.11%
57.9%
2.0%
90.24%
78. 12%
78.1% 1%
2.9%
96.59%
85,89%
90.67%
3.9%
98.48%
91.23%
95.28%
J BRUSLEATTACK UNDER DIFFERENT RANDOM SEEDS
is possible that the initial generated by uniformly selecting the color value for each channel of each pixel from {0, }} at random (as presented in Appendix H and Appendix G could impact perfor- mance. We investigate this using Monte Carlo experiments. To analyze if our attack is sensitive to our proposed initialization scheme. We run our attack 10 times with different random seeds for each source image and target class pair. This also generates 10 different synthetic color images (x') for each source image and target class pair. We chose evaluation set of 1000 source images (evenly distributed across 10 random classes) and used each one and our attack to flip the label to 9 different target classes. So conducted (1000 x 9 source- source-image-B poaage-tt-targe--e. generated 10 different for each pair) attacks (90K attacks) against ResNet18 on CIFAR-10, 100. We report the min, max, average and standard deviation ASR across the entire evaluation set different sparsity levels. The results in Table 17 show that our method is invariant to the initialization of æ'. Therefore, our initialization scheme does not affect the final performance of our attacks reported in the paper. Actually, the more complex task of optimizing x' and devising efficient algorithms to explore the high dimensional search space or the generation of better image synthesizing schemes (initialization schemes) to boost the attack performance leaves interesting works in the future.
pairs) x 10 (ten because
Table 17: ASR (Min, Mean, Max and Standard Deviation) of our attack methods across the entire evaluation set different sparsity levels with query budget of 500, with 10 different random seeds for each attack on CIFAR-10.
Sparsity 11(00 pixels)
ASR (Min)
ASR (Mean)
ASR (Max)
Standard Deviation
68.14 %
68.36 %
68.66%
0.35
2%-(20 pixels)
90.24%
90.76%
91.38%
0.48
2.9% pixels)
96.62%
96.71%
96.78%
0.11
349%(40 pixels)
98.17%
98.35%
98.49%
0.13
26

---

Published as a conference paper at ICLR 2024
K EFFECTIVENESS OF DISSIMILARITY MAP
In this section, we aim to investigate the impact of employing the dissimilarity map as our prior knowledge.
On CIFAR-10. Similarly, we conduct another experiment on an evaluation set which is composed of 1000 correctly classified images (from CIFAR- 10) evenly distributed in 10 classes and target classes per image. However, to reduce the burden of computation when studying query budget of 500. The results in Table 18 confirm observation ImageNet.
Table 18: ASR comparison between with and without using Dissimilarity Map on CIFAR-10.
Sparsity
With Dissimilarity Map
Without Dissimilarity Map
1.0%
68.21%
67.16%
2.0%
90.24%
89.42%
2.9%
96.59%
95.96%
3.9%
98.48%
97.92%
On ImageNet. We conduct a more comprehensive experiment in terms of query budget show more interesting results. In this experiment, we use the same evaluation set of 500 samples from ImageNet used in Section 4 and in the targeted setting. The results in Table 19 show that em- ploying prior knowledge of pixel dissimilarity benefits our attack, particularly at a low percentage of sparsity rather. At a high percentage of sparsity, BRUSLEATTACK adopting prior knowledge only achieves comparable performance to BRUSLEATTACK without prior knowledge. Notably, at a sparsity of 0.2%, BRUSLEATTACK is slightly worse than SPARSE-RS. Nonetheless, employing prior knowledge of pixel dissimilarity improve the performance of BRUSLEATTACK and makes consistently outweigh SPARSE-RS.
Table 19: ASR at different sparsity thresholds and queries (higher is better) for a targeted setting. A comparison between SPARSE-RS, BRUSLEATTACK (without Dissimilarity Map) and BRUSLEATTACK (with Dissimilarity Map) evaluation set of 500 pairs of image and target class ImageNet
Methods
Q=2000
Q=4000
Q=6000
Q=8000
Q=10000
Sparsity = 0.2%
SPARSE-RS
9.4%
20.6%
29.6 %
33.4%
38 73.4%
BRUSLEATTACK (without Dissimilarity Map)
8.8%
19.6%
27.4 %
34.4%
38.
BRUSLEATTACK
12%
23.6%
31.6%
36.6%
40.4%
Sparsity = 0.4%
SPARSE-RS
23.6%
48.4%
63.0%
72.6%
78.8%
BRUSLEATTACK (without Dissimilarity Map)
30.2%
53.4%
64.4%
73.0%
78.6%
BRUSLEATTACK
33,2%
54.2%
66.8%
76%
82.4%
Sparsity 0.6%
SPARSE-RS
29.6%
57.6%
73.2%
85.8%
92.0%
BRUSLEATTACK (without Dissimilarity Map)
43.6%
71.6%
85.0%
91.8%
94.6%
BRUSLEATTACK
45,4%
75.6%
87.4%
91.8%
94.6%
L HYPER-PARAMETERS INITIALIZATION AND COMPUTATION RESOURCES
All experiments in this study are performed on two RTX TITAN GPU (2 x 24GB) and four RTX A6000 GPU (4 x 48GB). We summarize all hyper-parameters used for BRUSLEATTACK on the evaluation sets from CIFAR-10.
STL-10 and ImageNet as shown in Table 20 Notably, only the initial changing rate An is adjusted for different resolution datasets i.e. STL-10 or ImageNet thus, method can be easily adopted for different vision tasks. Additionally, to realize attack, we randomly synthesize a color image x' for each attack. At initialization step, BRUSLEATTACK randomly creates 10 candidate solutions and choose the best.
27

---

Published as a conference paper at ICLR 2024
Table 20: Hyper-parametters setting in experiments
C-
STL-10
ImageNet
Parameters
Untargeted
Targeted
Untargeted
Targeted
Untargeted
Targeted
m11
0.24
0.24
0.24
0.24
1722
0.997
0.997
0.997
0.997
0.997
0.997
0.15
0.3
0.15
0.3
0.05
prior
1
M HYPER-PARAMETERS STUDY
In this section, we conduct comprehensive experiments to study the impacts and the choice of hyper-parameters used in our algorithm. The experiments in this section are mainly conducted on CIFAR-10. For Xo we conduct an additional experiment on ImageNet.
M.1 THE IMPACT OF mi, m2
In this experiment, we use the same evaluation set on CIFAR-10 mentioned above. To investigate
the impact of my, set m2 0.997 and change mi 0.2, 0.24, 0.28. Likewise, set
mh = 0.24 and change m2 = 0.993, 0.997, 0.999 to study m22 The results in Table 21 show that BRUSLEATTACK achieves the best results with m. 0.24 and m2 0.997.
Table 21: ASR of BRUSLEATTACK with different values of mı, m2 on CIFAR-1C.
Fixed my
0.997
Fixed m, = 0.24
Sparsity
0.2
mi 0.24
m² 0.28
1/2 0.993
m2 0.997
1/2
0,900
1,0%
67.32%
68.21%
67.48%
67.34%
68.21%
67.21%
2.0%
88.67%
90.24%
88 94%
89.64%
90.24%
89.12%
2.9%
95.37%
96.59%
95.54%
96.25%
96.59%
95.82%
3.9%
97.24%
98.48%
97.68%
97.59%
98.48%
96.21%
M.2 THE IMPACT OF Åo
On CIFAR-10. Similarly, conduct another experiment on the same evaluation set which is composed of 1000 correctly classified images (from CIFAR-10) as described above. We use the same query budget of 500. We my 0.24 and m2 0.997 and change Ào 0.15 to study the impact of Ag. Our results in Table 22 show that BRUSLEATTACK achieves the best results with
An = 0.15.
Table 22: ASR of BRUSLEATTACK with different values of Ag on CIPAR-10 1.0.
Sparsity
Ao = 0.1
Ao 0.15
λo 0.2
1.0%
68.05%
68.21%
68.12%
2.0%
89.38%
90.24%
88.33%
2.9%
96.15%
96.59%
95.56%
3,9%
98.16%
98.48%
97. 97.08%
On ImageNet. We use 500 random pairs of image and target class from ImageNet: more comprehensive experiment in terms of query budgets. Figure
targeted setting. We carry 10 shows that with different initial changing rates Ao. BRUSLEATTACK obtains the best results when λо is small such as 0.03 or 0.05. However, at small sparsity budget, Åo 0.03 often achieves lower ASR than Ä = 0.05 as shown in Table 23 because requires more queries to make changes and move towards a solution. Consequently, λo should not be too small. If increasing λu, BRUSLEATTACK reaches its highest ASR slower than using small Ag. Hence, the initial changing rate has impact on the overall performance of BRUSLEATTACK.
28

---

Published as a conference paper at ICLR 2024
100
Table 23: ASR different sparsity levels and queries (higher is better) in a targeted setting. A comparison between Àg 0.03 and X 0.05
75
ASR (%)
2. 0.03
on a set of 500 pairs of an image and a target class on ImageNet
80
20 - 0.05
20 0.07
25
An 0.1
Initial changing rate
Q=2000
Q=4000
Q=6000
Q=8000
Q=10000
Sparsity 0.2%
6K
0 0.03
10.2%
22.6%
29.2% %
35.6%
41.4%
Queries
Au = 0.05
12%
23.6%
31.6%
36.6%
40.4%
Figure 10:
ASR versus
Sparsity = 0.4%
model queries on ImageNet. BRUSLEATTACK against ResNet- 50 with sparsity of 1.0 % in targeted setting to show the im- pacts different syper-parameters on BRUSL.EATE ATTTACK.
Ao 0.03
31%
53.6%
65.6%
74,2%
80%
0.05
33.2%
54.2%
66.8%
76%
82.4%
Spursity 0.6%
0.03
45.4%
75.4%
84.6%
89.8%
92.8%
Ap 0.05
45.4%
75.6%
87.4%
91.8%
94.6%
M.3 THE CHOICE OF arrior
In this section, we discuss the choice of prior and provide an analysis on the convergence time.
arior (a; where E [1, In our proposal, we draw multiple pixels (equivalent to multiple elements in a binary matrix u) from the Categorical distribution (K categories) parameterized by 0 [0,, 022... ..., 0x]. When initializing an attack, we have no prior knowledge of the influence of each pixel that is higher or lower than other pixels on the model's decision so it sensible to assume all pixels have a similar influence. Consequently, all pixels should have the same chance to be selected for perturbation (to manipulated). To this end, the Categorical distribution where multiple pixels are drawn from should be a uniform distribution and 01 = 02
OOK- R
We note that Dirichlet distribution is the conjugate prior distribution of the Categorical dis- tribution. If the Categorical distribution is uniform distribution, Dirichlet distribution is also a uniform distribution. In probability and statisties, Dirichlet distribution (parameter- ized by a concentration vector a = [0,,02.... 02.... [rk] each ag represents the i-th element where K the total number of elements) is equivalent to a uniform distribution over all of the elements when a = = az.... ... ax] = [1. 1, 1]. In other words. there is no prior knowledge favoring one element over another. Therefore, we choose prior
Prior < 1 (a, < 1 where E k1,
We have aposterior = arior + (t) and (()) = (al)) +2)- So we have aposterior = arioor (a
(0))-
Because (a + =))(n(0) + =) < 1, we cannot choose ariior < to ensure that the parameters controlling the Dirichlet distribution are always positive Passterior > 0).
arior > 1 (a, 1 where i E k1, Since posterior prior + (a(t) + 2)/(n(() +
-1 and 0 < (a + (n + +) < 1, if arrior >> 1, in the first few iterations, a posterior almost remains unchanged so the algorithm will not converge. If prior > 1, the farther from 1 arior is, the more subtle the posterior changes. Now, the update (a + 2))(n(() + 2) needs more iterations (times) to significantly influence posterior In other words, the proposed method requires more time to learn the Dirichlet distribution (update posterior) Thus, the convergence time will be longer. Consequently, the larger ag is, the longer the convergence time is.
N BRUSLLATTACK WITH DIFFERENT SCHEDULERS
We carry out a comprehensive experiment to examine the impact of different schedulers including cosine annealing and step decay. In this experiment, we use the same evaluation set with 1000 images from CIFAR-10 evenly distributed in 10 classes and 9 target classes per image and we use the same query budget (500 queries). The results in Table 24 show the ASR at different sparsity levels. These results show that our proposed scheduler slightly outperforms all other schedulers. Based on the results, Step Decay or Cosine Annealing schedulers be good alternative.
29

---

Published as a conference paper at ICLR 2024
Table 24:
ASR comparison between using Power Step Decay (our proposal) and other schedulers
CIFAR-10.
Sparsity
Our Proposal
Step Decay
Cosine Annealing
1.0%
68.21%
68.11%
68.02%
2.0%
90.24%
89.34%
89.15%
2.9%
96.59%
96.12%
95.89%
3.9%
98.48%
98.26%
98.18%
O ALGORITHM PSEUDOCODES
Initialization. Eegorithmppresenee pseudo-code for attack initialization as presented in Section 3.3
Algorithm 2:
Initialization
Input: source image synthetic color image x' source label target label Vurrett
number of initial samples N. N.perturbation budget B, victim model fM
l -
for i N do Generate u' by uniformly enabling B bits of 0 random
+ L(fM(g(u'; x²)))""") if < then
u + u' L
end for return l
Generation. Algorithm presents pseudo-code for generating new data point as presented Sec- tion 33
Algorithm 3: Generation
Input: probability 0, bias map M, mask u, changing rate X
b + [(1 B}
01 ..... 0b Cat(u 0.u u 1)
Q1 UB-b Cat(q 0M, u = 0)
(1) [v (4) B-b (6)
return
Update. Algorithm presents pseudo-code for updating an accepted mask (a solution round f) and estimated (() as presented in Section 3.3 and illustrated Figure
P EVALUATION PROTOCOL
In this section, we present the evaluation protocol used in this paper.
1. In the targeted attack settings.
SparseRS (Croce et al. 2022) evaluation with ImageNet: Selected 500 source images. But each source image class was flipped to only one random target class using the attack. So that a total of 500 source-image-to-oo protocol may select the same target class attack in the 500 attacks conducted. Thus, this could lead to potential biases in the results because some classes may be casier to attack than others.
class attacks. This evaluation
30

---

Published as a conference paper at ICLR 2024
Algorithm 4: Update
Input: previous mask and ltssu(t-1), ((t-1), cuurenn mask and loss u ((0) ,saall constant 2, matrices al9), n2
(0) n1
Bi.jelliji )= increase by
if ((0) < ((t-1) then
u(t) f g())
else
u + ((t=1), + g(t-1) di.jEll (1(t-))) (aaa- increase by 1
end if
n+
10 Update a posterior using and Equation 6
Update using a nosterior and Equation g
12 return u, l 0 a.
To avoid the problem, in the targeted attack setting, we followed the evaluation pro- tocol used in (Vo et al. 2022a). Essentially, we flip the label of the source image several targeted classes, this can help address potential biases caused by relatively easier classes getting selected multiple times for a target class.
Our evaluation with ImageNet: We randomly selected 200 correctly classified source images evenly distributed among 200 random classes. But, in contrast to SparseRS, we selected 5 random target classes to attack for each source image. In total we did 200 targeted attacks.
1000 source-image-tov to-tagget class attacks on ImageNet. for
2. In the untargeted attack setting (attacks against defended models), we conducted 500 at- tacks (similar SparseRS). We randomly selected 500 correctly classified test images from 500 different classes for attacks.
3. Further, our unique and exhaustive testing with CIFAR-10 and STL-10 corroborates ImageNet results given the significant amount of resources it takes to attack the high- resolution Ima GeNe (224 x 224) models.
For STL-10 0 we conducted 60,093 attacks against each deep learning model (6,677 of all 10,000 images in the test set which are correctly classified versus 9 other classes as target classes for each source image). We used every single test set image in STL-10 -10 (96 x 96) in our attacks to mount the exhaustive evaluation where no image from the test set was left out.
For CIFAR-10 (32 32) we conducted 9,000 attacks against each deep learning model (1000 random images correctly classified versus the 9 other classes as target classes for each source image).
4. For evaluations against a real-world system (GCV) in the significantly more difficult tar- geted setting (not the untargeted setting), we provide new benchmarks for attack demonstra- tion because we provide a comparison between BRUSLEATTACK and the previous attack, SPARSE-RS. To make clear, we provide brief comparison as follows:
Other related past studies (dense attacks) (Ilass et al. 2018 Guo et al. 2019). showcase an attack against a real-world system but uses 10 attacks. While Ilyas et al. (2018) illustrated only successful example when carrying out attack against Google Could Vision.
Importantly, we did not simply use our method only, as in (Ilyas et al. 2018 2019) but demonstrated comparison between BRUSLEATTACK and SPARSE-RS. In practice, we used 10 samples for each attack, so there are 20 attacks.
2018 Guo et al.
In general, our evaluation protocol is much stronger than the used in previous studies. evalu- ate on three different datasets CIFAR-10, STL-10 (not evaluated in prior attacks) and ImageNet with Res ResNet-50 (SIN), Visitation Transformer (not evaluated in prior attacks).
31

---

Published as a conference paper at ICLR 2024
Q
VISUALIZATIONS OF ATTACK AGAINST GOOGLE CLOUD VISION
Table 25 and Figure 11 Table 26 and Figure 12 show our attack against real-world system Google
Cloud Vision API.
Table Demonstration sparse attacks against GCV in targeted settings. BRUSLEATTACK is to successfully yield adversarial instances for all five examples with less queries than SPARSE-RS. Especially, for the example of Mushroom, SPARSE-RE RS fails to attack GCV within budget of 5000 queries. Demonstration GCV API (online platform) is shown in Figure II
Examples
No Attack
Car
Flower
Fire Truck
Vehicle
Mushroom
Window
Yellow Pepper (99 Queries)
Window
Window
Landscape (490 Queries)
BRUSLEATTACK
(1 .8K Queries)
(328 Queries)
(1.83K Queries)
SPARSE-RS
Window
Yellow Pepper
Window (395 Queries)
Window
Mustrcom
(4.66K Queries)
(211 Queries)
(3.3K Queries)
5K Queries)
Fioee
Pagart
VHl Hrigel
Fiam
Fioes:
Neticle
F45
Vitiade
balita Velaade
Mil Velicde
Milic Venioe
Velbccae Strdk suttuc Hate
a) No Attack (Clean input)
b)
Our Attack
SparseRS
Figure demonstrates results for clean image attack) predicted by Google Cloud Vision (GCV). b)
shows the predictions from GCV adversarial examples crafted successfully by BRUSLEATTACK with less
than 3,000 queries and sparsity of 0.05 %. c) shows the results from GCV for adversarial examples crafted hy
SPARSE- RS with the same sparsity. But SPARSE-RS, needs more queries than BRUSI. successfully yield adversarial images fail to attack with query budget up to 5,000 shown in Table 25
32

---

Published as a conference paper at ICLR 2024
Table 26: Demonstration of sparse attacks against GCV in targeted settings. BRUSLEATTACK is able successfully yield adversarial instances for all five examples with less queries than SPARSE- Especially, the example of Mushroom, SPARSE-RS RS fails to attack GCV within a budget of 5000 queries. Demonstration on GCV API (online platform) is shown in Figure 12
STOP
Exumples
No Attack
Reflex Camera
Y.L. S1 Sper
Match
Iding
Stop Sign
Circle (3.8K Queries)
Flowering Plant (899 Queries)
Jewe 1lry (2.9K Queries)
Gas (983 Queries)
Material (2.77K Queries)
BRUSLEATTACK
Gas
Plowring Plant (988 Queries)
Font
Fixture
Font
SPARSE-RS
5K Queries)
(>5K Queries)
(>5K Queries)
5K Queries)
Orde
Dasiial Cames
35
Audio Rarimen
7%
Oitia
Fast
Flowering
Termett
Winch
70%
Weich Ancusney
Wapce Accevnrr
745
Sige
Fant
STOP
STOP
STOP
Traffe 22g
Matere Prozemmy
a) No Attack (Clean input)
b)
Our Attack
SparseRS
Figure 12: demonstrates results for clean image attack) predicted by Google Cloud Vision (GCV). b) shows the predictions from GCV adversarial examples crafted successfully by BRUSLEATTACK with less than 3,000 queries and sparsity 0.05 %. c) shows the results from GCV for adversarial examples crafted hy SPARSE- RS with the same sparsity. But SPARSE-RS need more queries than BRUSL.FATTA to successfully yield adversarial images fail to attack with query budget up to 5,000 shown in Table 25
33

---

Published as a conference paper at ICLR 2024
R VISUALIZATIONS OF SPARSE ADVERSARIAL EXAMPLES AND DISSIMILARITY MAPS
In this section, illustrate:
Sparse adversarial examples, sparse perturbation crafted by our methods versus salient gion produced by GradCAM method Selvaraju et al. (2017) or attention map produced by VIT model Dosovitskiy et al. (2021).
Sparse adversarial examples crafted by BRUSLEATTACK when attacking ResNer-50, ResNet-50 (SIN) and Vistion Transformer.
Dissimilarity Map produced from a pair of source and synthetic color images.
Figure 13 and illustrate sparse adversarial examples and spare perturbation of images from ImageNet in targeted and untargeted settings. In targeted settings, we use a query budget of 10K, while in untargeted settings, set query limit of 5K. We use GradCAM and Attention Map from VIT to demonstrate salient and attention regions. The sparse perturbation 5 the absolute difference between source images and their sparse adversarial. Formally, sparse perturbations be defined as x T
The results show that for ResNet-50, the solutions found do need to perturb salient regions an image to mislead the models (both targeted and untargeted attacks). Attacks with ViT models in untargeted settings also lead
similar observation. Interestingly, for some images c.g. snake or a goldfinch in Figure 13 we observe that a set of perturbed pixels yielded by our method is more concentrated in the attention region of ViT. This seems to indicate some adversarial solutions achieves their objective by degrading the performance of a VIT. This is perhaps not an unexpected observation, given the importance attention mechanisms to transformer models.
ResNet-50
Vision Transformer
Original Image
Sparse Advenaraal Exampla
Spanse Perturtation
GradCAM
Scatte Adversanal Exumple
Sporse Perlurbaton
Atlention Map
Preckded Terger
100 picels
Predecee as Targel
Goldftnch
Pretided Targer ca66 Chickadee
Prodoced os Target dasa Chickades
piels
Piedidtd
diaa Snail
100 pixels
cleaa Smail
100 pieels
Figure 13: Targeted Attack. Visualization of Adversarial examples crafted by BRUSLEATTACK with budget 10K queries. the image sparse perturbation, each pixel is zoomed in times (9x) to make them more visible.
34

---

Published as a conference paper at ICLR 2024
ResNet-50
Vision Transformer
Original Image
Sparss Adversaial Exampl
Sparse Porturbation
GradCAM
Sparse Adversaral Exomple
Sparse Perturbatin
Attention Map
Amphiiion
pleals
Goldfinch
Prediceed Spider web
Predicted os Rifle
Green mambe
Predicted Gross Snake
50 pinals
Predicted Grass Snake
50 plaess
Figure 14: Untargeted Attack. Visualization of Adversarial examples crafted by BRUSLEATTACK with budget of 5K queries. the image of sparse perturbation, each pixel is zoomed in times (9x) make them more visible.
Figure [3] and [6 demonstrate some examples adversarial examples yielded by BRUSLEATTACK when attacking different deep learning models (ResNet-50, ResNet-50 (SIN) and Vision Trans- former) in targeted settings produced using 10K query budget.
35

---

Published as a conference paper at ICLR 2024
ResNet-50 (SIN)
Vision Transformer
ResNet-50
Sparse Adversarial Example
Original image
Predicted as Target class Snail
60 pixels (0.12% sparsity)
70 pixels (0. (0.14% sparsity)
100 pixels (0.2% sparsity)
Sparse Adversarial Example
Original image
Predicted as Target class Traffic Light
20 pixels (0.04% sparsity)
20 pixels (0.04% sparsity)
20 pixels (0.04% sparsity)
Figure 15: Visualization of Adversarial examples crafted by BRUSLEATTACK with budget of 10K queries.
36

---

Published as a conference paper at ICLR 2024
ResNet-50 (SIN)
Vision Transformer
ResNet-50
Sparse Adversarial Example
Original image
Predicted Target class chickadee
60 pixels (0.12% sparsity)
50 pixels (0.1% sparsity)
120 pixels (0.24% sparsity)
Sparse Adversarial Example
Original image
Predicted as Target class Peke
100 pixels
100 pixels
100 pixels (0.2% sparsity)
(0.2% sparsity)
(0.2% sparsity)
Figure 16: Visualization of Adversarial examples crafted by BRUSLEATTACK with budget of 10K queries.
37

---

Published as a conference paper at ICLR 2024
Figure 17 iillsttrates some examples of Dissimilarity Map yielded by source image and synthetic color image.
Synthetic color image
Synthetic color space
Image
Dissimilarity Map
Source Image
Dissimilarity Map
M
M
Synthetic color image
Synthetic color space
Source Image
Dissimilarity Map
Source Image
Dissimilarity Map
M
M
Figure 17: Visualization of Dissimilarity Maps between source image and a synthetic color image.
38


Reviews:
[{"review_id": "5y2qxOJbar", "reviewer": "Reviewer_Xni7", "summary": "The paper proposes a new score-based blackbox adversarial attack under the sparse constraint (l_0 norm). Specifically, it first initial a random image to get the perturbation strength on every pixel. It then mix the random image with the original image using a learnable mask. By limiting the number of non-zero element in the mask under the l_0 norm constraint, it uses bayesian optimization to find the optimal position to generate an adversarial example on the sparsity constraint. The experiments show the proposed method could achieve a better attack success rate under different models, datasets and defensive models.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow. \n2. The paper provides some interesting findings regarding sparse adversarial attack.", "weaknesses": "1. The proposed optimization is only conducted on finding the optimal position given a random initialized image x'. In other words, the proposed method is heavily based on the quality of the initialized x' and it heavily affects the optimality condition of the proposed method. I believe a successful sparse attack should not only find the best position but also find the optimal perturbation for those spaces. \n2. The comparison with PGD_0 is not fair to me. The PGD_0 needs to find the minimum number of pixels to be perturbed where the proposed method only finds the best solution under certain threshold. I believe a fair comparison should let the proposed method also find the minimum number of pixels along with its optimal perturbation strength.\n3. The baseline included in the experiments are pretty weak. For example, some baselines like iteratively conducting one-pixel adversarial attack should be considered rather than just comparing with a decision-based attack. Also, some dense attack could easily be changed to handle the sparse attack. For example, selecting the largest perturbation in the l-2 norm attack or using a relaxed l-1 attack would also be viable baselines.\n4. Although the proposed method claims to largely improve the query efficiency, the number of query is still around in the same level with decision based attack. However, the score based attack should be much more query-efficient than decision-based attack in dense attack, where makes the score-based attack not attractive and impractical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "1KjuWzi9Ao", "reviewer": "Reviewer_kfkC", "summary": "The authors first highlight the problems related to generating strong sparse l0 norm attacks. The non differential search space makes the problem NP hard. To generate a stronger attack, the authors propose an iterative algorithm which aims to estimate a mask made up of zeros and ones to determine whether to take the pixel from the original image or from a synthetically generated random image. The authors provide an analysis on different sampling distributions considered to generate synthetic images. Once the synthetic image is generated, the authors propose to sample each value of the mask from a categorical distribution parameterized by a training parameter \\theta and conditioned on the difference between the original image and the synthetic image. Then the authors propose to estimate \\theta by initializing it as a Dirichlet prior parameterized by \\alpha_{i} for i \\in {0,k} and updating it by taking an expectation over the posterior distribution of \\theta conditioned on \\alpha_{i} and the mask of last time step. Continuing this iteratively, the authors approximate the mask with zeros and ones within the threat l0 threat model. The authors demonstrate that the proposed approach is faster when compared to [1], scales to larger datasets like Imagenet and achieves improved performance over existing methods.\n\n[1] Croce, Francesco et al. “Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks.” AAAI Conference on Artificial Intelligence (2020).", "questions": "It is not clear how the authors ensure that the attack follows the threat model. Could the authors clarify this. It would be nice if the authors can answer the concerns and questions raised in the weakness section", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "* The proposed algorithm seems interesting and innovative.\n* The results demonstrate significant improvements over prior works.\n* The proposed method shows improved performance on standard datasets like CIFAR10 and scales to larger scale datasets like Imagenet.", "weaknesses": "* I think the presentation of the paper needs improvement. For instance, in the introduction, it seems difficult to understand what authors are trying to say in “Our Proposed Algorithm” part. The authors should try to built a flow in the writing which can help them in explaining their method. Similarly the authors should not use long captions below the figures. This makes it difficult to follow what the authors are trying to convey. The functions GENERATION and INITIALIZATION in algorithm-1 should be defined properly.\n  \n* Since the authors only aim to generate the mask with 0’s and 1’s and thus replace the pixels values corresponding to mask of 1 from a synthetically generated random image, it is likely that the strength of the attack could be enhanced by adjusting the pixel values. Thus the proposed attack though performs better than existing methods, doesn't seem like an optimal attack and shows scope for improvement. It would be nice if the authors could share the effect of first running their proposed algorithm to find the pixels to be replaced and later changing the values of the pixels to make the attack stronger. Is it possible to enhance the strength of the attack by using this second step?\n\n* I think some of the design choices in the proposed algorithm need more discussion. For instance, the algorithm might be sensitive to the initial values of Dirichlet parameters \\alpha_{k}. Could the authors present some analysis on how the convergence time and attack success rate of the proposed method varies with the initial values of \\alpha_{k}. Further, does the algorithm converge to same set of values of \\alpha_{k} for different initial values?\n\nPost Rebuttal: I would like to thank the authors for providing a comprehensive rebuttal. The authors have tried to improve the clarity of this work and also addressed my concerns. Therefore, I increase my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "z0KEv6aFAe", "reviewer": "Reviewer_tLev", "summary": "This paper introduces a black-box attack method to generate sparse adversarial perturbations to fool the model. The method focuses on learning the masks representing the perturbed pixels and use Bayesian optimization to achieve it. Extensive experiments and comparison with the baseline demonstrate the effectiveness of the algorithm.", "questions": "In addition to the weakness part above, I have the following additional questions:\n\n1. In addition to the $l_2$ and $l_\\infty$ robust models, I suggest the authors try evaluating the attack perturbation for $l_1$ robust models, since $l_1$ norm ball the convex hull of the perturbations bounded by $l_0$ norms. Possible baselines include strong AA-$l_1$ [A] and efficient Fast-EG-$l_1$ [B].\n\n[A] Croce, Francesco, and Matthias Hein. \"Mind the box: $ l_1 $-APGD for sparse adversarial attacks on image classifiers.\" International Conference on Machine Learning. PMLR, 2021.\n\n[B] Jiang, Yulun, et al. \"Towards Stable and Efficient Adversarial Training against $ l_1 $ Bounded Adversarial Attacks.\" International Conference on Machine Learning. PMLR, 2023.\n\nThe current manuscript is a borderline paper, I will conduct another round of evaluation after the discussion with the authors.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The motivation is well-justified. The observation that interpolation with a real image and a synthetic image can generate sparse adversarial examples is interesting. The Bayesian optimization in this context is novel. The experiments comprehensively demonstrate the effectiveness of the algorithm.", "weaknesses": "Despite the strengths above, the paper has the following weaknesses:\n\n1. [Presentation] The notation of the paper is a bit confusing. I suggest the authors put a notation table in the appendix to facilitate the reader to better understand every notation in the paper. \n\n2. [Theorem] I did not understand why proof in Appendix G matters. The re-parameterization is straightforward.\n\n3. [Experiments] Regarding the efficiency of the algorithm, using the wall clock time may be a better choice than the number of queries. This is because the proposed algorithm may have a higher complexity per query.\n\n4. [Code] No sample code is provided, there is a reproduction concern.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "t4FRkcWb5v", "reviewer": "Reviewer_UEvH", "summary": "This paper studies score-based sparse adversarial attacks against deep learning models. The problem is challenging due to the combinatorial optimization problem and black-box setting. The paper introduces a novel attack algorithm by reducing the search space of adversarial attacks and proposes a probabilistic method to optimize the binary matrix. The extensive experiments demonstrate the query efficiency and effectiveness of attacking black-box models, including black-box APIs.", "questions": "- Can this method be extended to adversarial patch attack, which is a special case of $\\ell_0$ perturbations but is physically realizable.\n- Could you show some sparse adversarial examples? Are there any interesting observations on what pixels are most influential for changing the prediction?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The problem formulation is interesting and the method is solid.\n- The experiments demonstrate the effectiveness of the proposed method.", "weaknesses": "- Some technical details are unclear. For example, the authors have stated that they reduce the search space by introducing a synthetic color image. However, it is not clear how this approach can reduce the search space. Although the authors have provided detailed analyses in Appendix, they should provide some intuitions in the main paper to help understand the paper.\n- Learning a distribution of the optimization parameters seems to be a natural way. Natural evolution strategy is commonly adopted for score-based attacks by learning a search distribution, although the previous work adopts Gaussian distribution for $\\ell_2$ and $\\ell_\\infty$ norms. The authors are encourages to discuss with NES. Also, a recent work (\"Black-box Detection of Backdoor Attacks with Limited Information and Data\", ICCV 2021) also proposes a score-based method to optimize sparse perturbations, although it studies a different problem. More discussions and comparisons are needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)