Towards Physical, Imperceptible Adversarial Attacks via Adversarial Programs
Authors: Itai Mesery
Dana Drachsler Cohen
Venue: ICLR 2022 Submitted (2022)
Keywords: Adversarial Attacks
Adversarial Patches
Adversarial Programs
Program Synthesis

Abstract: Adversarial examples were originally defined as imperceptible perturbations which cause a deep neural network to misclassify. However, the majority of imperceptible perturbation attacks require to perturb a large number of pixels across the image and are thus hard to execute in the physical world. Existing physical attacks rely on physical objects, such as patches/stickers or 3D-printed objects. Producing adversarial patches is arguably easier than 3D-printing but these attacks incur highly visible perturbations. This raises the question: is it possible to generate adversarial examples with imperceptible patches? In this work, we consider adversarial multi-patch attacks, where the goal is to compute a targeted attack consisting of up to K patches with minimal L2 distortion. Each patch is associated with dimensions, position, and perturbation parameters. We leverage ideas from program synthesis and numerical optimization to search in this large, discrete space and obtain attacks that are competitive with the C&W attack but have at least 3x and up to 10x fewer perturbed pixels. We evaluate our approach on MNIST, Fashion-MNIST, CIFAR-10, and ImageNet and obtain success rate of at least 92% and up to 100% with at most ten patches. For MNIST, Fashion-MNIST, and CIFAR-10, the average L2 distortion is greater than the average L2 distortion of the C&W attack by up to 1.2.

Under review as a conference paper at ICLR 2022
TOWARDS PHYSICAL, IMPERCEPTIBLE ADVERSARIAL ATTACKS VIA ADVERSARIAL PROGRAMS
Anonymous authors
Paper under double-blind review
ABSTRACT
Adversarial examples were originally defined as imperceptible perturbations which cause deep neural network to misclassify. However, the majority of im- perceptible perturbation attacks require to perturb large number of pixels across the image and are thus hard to execute in the physical world. Existing physical attacks rely on physical objects, such as patches/stickers or 3D-printed objects. Producing adversarial patches is arguably easier than 3D-printing but these at- tacks incur highly visible perturbations. This raises the question: is it possible to generate adversarial examples with imperceptible patches? In this work, we consider adversarial multi-patch attacks, where the goal is to compute a targeted attack consisting of up to K patches with minimal L2 distortion. Each patch is associated with dimensions, position, and perturbation parameters. We leverage ideas from program synthesis and numerical optimization search in this large, discrete space and obtain attacks that are competitive with the C&W attack but have at least 3x and up to 10x fewer perturbed pixels. We evaluate our approach on MNIST, Fashion-MNIs of at least 92% and up to 100% with most ten patches. For MNIST, Fashion- MNIST, and CIFAR-10 10, the average L2 distortion is greater than the average L. distortion the C& attack by up to 1.2.
CIFAR-10, 10, and ImageNet and obtain success rate
INTRODUCTION
Adversarial examples were originally defined imperceptible perturbations added correctly clas- sified inputs which cause deep neural network (DNN) to misclassify (Szegedy et al. [004 Good-| fellow al. 2015). Since then, many works have shown how to generate imperceptible adversarial examples (e.g., Carlini & Wagner (017);; Moosavi-Dezfooli et al. (2016); Madry et al. (218)). ) A
main motivation of this line of works to expose the level of vulnerability of DNN-based systems. However, these attacks often cannot be executed in the physical world, for example against DNNs used by autonomous vehicles (Lu et al. 2017). This gave rise to works that focus on physical at- tacks, executed by adding patches or stickers to objects cameras (Brown al. 2017 Eykholt (ct al. 2018 Li et al., (2019) or 3D--3iD-ee objects (Athalye et al.] 2018: Sharif et al. 2018 While 31D-printing enables the attacker to generate imperceptible adversarial examples, it not the for patch/sticker attacks. These attacks incur highly visible perturbations. However, in some settings (e.g.. traffic sign attacks), patch attacks are easier execute than 3D-printing attacks. This raises the question: is it possible to generate adversarial examples with imperceptible patches?
We consider new space of targeted attacks expressed as patch sequences. The patches we consider are of rectangular shape and uniformly perturb their associated pixels according to scale and shift factors. Given an input, a DNN, and a target label, the attacker's 's goal is to compute patch sequence resulting in a targeted ad adversarial example of minimum distance to the original input. That is, the attacker chooses the patches' position, dimensions, perturbation factors, and the number of patches such that the output of the patch sequence is an imperceptible adversarial example. Because the goal is to generate a sequence of patches, each is constrained by a structure, is natural to view each patch as program instruction and the overall problem as an instance of Syntax-guided Synthesis (SyGuS) (Alur et al. 2013),, where high-level requirement (e.g., computing an adversarial example) has to be implemented in given programming language (e.g., the patch sequence). A common challenge of SyGuS instances is looking for a solution (i.c., a program) in a discrete space. Unlike common SyGuS instances, our instructions (i.e., patches) are defined also continuous variables

---

Under review as a conference paper at ICLR 2022
Picat) 0.2% Pldoo)
Picatt 50.7% Pideal
Pidagl 0.2%
Pldog) 52.0% Pihorse) 7%,7%
Pihorse) 59.7%
Wharentula)
del Pimants)
Pitiger
Pilier 17.18
93.2%
Figure I: Examples of APSyn's 's attacks for CIFAR- (top) and ImageNet (bottom). Each triple con- sists of an image (left), the adversarial program (right), and the adversarial example returned by the program (middle). Programs are depicted as images showing the patches' position and dimensions; the legend shows the scale and shift factors of each patch, one per color channel.
(the perturbation factors). Thus, our setting is not easily amenable to standard SyGuS approaches, neither standard numerical optimization approaches (because of the discrete variables).
We propose APSyn, adversarial program synthesizer, compute patch sequences. APSyn builds on enumerative program synthesis which enumerates programs from the shortest to the longest until obtaining solution (Udupa et al. 2013). This approach guarantees to return the shortest solution among all solutions, which is desirable when aiming at simplifying the physical execution of the attack. While enumerative synthesis is useful, is sufficient by its own, there are infinitely many ways to instantiate a patch (up to computer representation), To search for the optimal patch pa- rameters, we leverage the loss proposed Carlini & Wagner (0117). To optimize this loss for patch sequences, we propose a gradient estimate for the discrete variables using zeroth order optimization. We further allow discrete variables take real values avoid skipping optimal solutions.
Our evaluation results for MNIST, Fashion-MNIST and CIFAR-I0 show that the success rate of APSyn at least 96%, when allowed up five patches. The L2 distortion of these attacks is on average greater by up to 1.2 than the C& W's L2 distortion, while the Lo distortion is smaller by least and up to 10x compared the C&W's attack. We further show that APSyn produces attacks which generalize better: at least 2.7x and up 23x more than the C&W attack. We believe higher generalization rate stems from the structure imposed on our attacks. For ImageNet, APSyn's 's success rate is 92% when allowed up ten patches. Figure I shows several attacks that APSyn synthesized along with visualizations the patch sequences.
To conclude, our main contributions are:
A new class of adversarial attacks consisting of multi-patch sequences.
An effective algorithm to compute multi-patch attacks combining enumerative synthesis
and numerical optimization. The latter relies on gradient estimation of the discrete factors. An extensive evaluation of our approach competitive with the C&W attack, in terms of the success rate and L2 distortion, but has significantly lower Lo distortion and is thus easier physically execute.
four datasets. Results show that attack is
ADVERSARIAL PROGRAMS
In this section, we provide the terms and notation used throughout the paper and define our problem.
We are given classifier N [0. 1]d -> (0. 1] mapping two-dimensional image to prob- ability vector over classes. We note that all our definitions extend to colored images by consid- ering each color channel separately. We assume white-box access to the classifier. We denote by class(NT (x))) the classification of input x by N, i.e., the index with the maximal probability. We are also given input with class c, which N classifies correctly, i.e, class (Nuss(N(x)) (x)) c, and target adversarial label t * c. The goal of the attack to compute an input which similar to x but is classified Commonly, this is phrased as constrained optimization, where the goal is compute
2

---

Under review as a conference paper at ICLR 2022
perturbation matrix M [0, ( such that the adversarial example x' = M is classified as (<lo))(N(z')) = t) and the p-norm of the perturbation matrix || l|p is minimal.
In this work, aim adding structure to adversarial attacks with the goal of obtaining attacks which are easier to physically exccute, are more explainable, and generalize better. We draw in- spiration from program synthesis where the goal is automatically generate a program over given programming language satisfying a set of requirements (Gulwani et al.] 2017). In particular, we view our problem an instance of Syntax-guided Synthesis (SyGuS) (Alur al. 2013), where the goal is to implement a high-level specification in given programming language, typically constrained and small. Having a program has various advantages: it can be used on other inputs, the implemen- tation can provide an alternative characterization of the user intent, or even provide a more efficient implementation than the user initially had. These applications are useful within our scope: our ad- versarial programs can be executed on other inputs in a negligible time and our programs expose the (almost imperceptible) shapes that cause the DNN to change its decision.
Ad Advesaaiall programs We introduce programming language for adversarial multi patch attacks. Our language consists of sequences of patch instructions from a family of patches I. Our patch family generalizes the perturbation matrices discussed before to scaling and shift perturbations rectangular masks. A rectangular mask is a tuple consisting of a starting and ending position p = (r", c², ct) capturing single rectangle in the input. A patch instruction (or simply, patch) la,B.p E I is associated with a mask scale factor a, and a shift factor B, and takes the form:
[a, = lambda v: (a + 3) if idr(v) Ep
where a, B R and E (fl.....d, d1 f1...., value in y a For value v with idx(v) = (Ta, G.) and mask = (r", c", re,,re ce, we say v's index is inside if r" ST < r" and e¹ S Co c.
.......d2)) ,22)). Given y E [o, 1]d.1xx xda, Ia,) maps every 8, if its index is inside the mask. Values outside the mask remain as are.
Problem definition Given network N, an input-outpon pair (r, c). a target class f, and a program length k, our goal is to compute a program P over with or fewer patches such that classifies P(x)) as l and P(x) ) is as close as possible to with respect to the L2 norm:
min [(( 1112
s.t.
P(x) [v(. (I))))) class (N((())) =t I...., In E EI k
Note that we allow patches overlap, which may lead to perturbation compositions.
Designing solution If we set aside the constraint that P a program over Z, a common approach solve the above constrained optimization by relaxing the attack constraint. For example, Carlini (arlle
& Wagnnr (2017) propose to relax it to a term which is then minimized along with the norm:
C(P)= = max(max N (P(x)) - N(P(=)).. 0) + A [|((x) x112 tft
papammer balancing the two optimization goals. If P(x) were differentiable, gradient descent could minimize this loss. If the size of I were relatively small, enumerative search would have been feasible. However, neither of these hold. We thus approach this search by combin- ing the two ideas. First, we introduce gradient estimation approach for the discrete variables, and then let Adam (Kingma & Ba 2015)) use it to minimize C(P). Second, to compute a shortest patch sequence and search more efficiently, we employ enumerative synthesis and gradually synthesize the adversarial program's 's patches. We explain these steps in the next two sections.
where
3 GRADIENT ESTIMATION OF THE PATCHES' DISCRETE PARAMETERS
In this section, we explain our approach to search for an optimal patch attack consisting of exactly patches from I. Unlike previous patch attacks, our approach jointly optimizes over all the patches' parameters position, dimensions, and perturbation factors. Since we allow patches to overlap, this optimization may lead complex patterns, despite the rectangular shape of the patches. Our
3

---

Under review as a conference paper at ICLR 2022
approach builds on the C&W attack, which minimizes the loss defined in the previous section. Since our attacks involve discrete variables, to numerically optimize this loss, we define "gradients" for these variables. The idea is to estimate the partial derivatives of the discrete variables using zeroth order optimization. We note that we do not claim that the partial derivatives exist, but rather that estimating them can guide the optimizer how to change discrete variable so that our loss decreases.
Gradient estimation Given a program P. an input x, and the target label t, the partial derivatives of the real-valued variables (the scale and shift parameters a, ,3) are computed usual. The partial derivative of a discrete variable wo is estimated by adapting the standard definition of the derivative. As first step. we estimate the derivative in each direction:
C(P)+ & aC(P)* lim Ow
[(P(w + + h)) C(P) = C(P(w w + 11) C(P).
h
The last step is obtained by replacing h with the closest discrete value to O. The notation Pfw - w + h| denotes the program identical to P except that w is increased by h. Similarly, ( = L(P) [(P(mv w + w 1])- These "derivatives" simulate the role of the gradient in optimization. If L(P) and L(P) are negative, then increasing w will decrease the loss and thus we define the gradient as L(P) If C(P) and C(P),, are positive, then decreasing wo will decrease the loss, and thus we define the gradient as C(P) w. If C(P) is negative and L(P) is positive, we define the gradient based on their magnitude; if C(P) tu is positive and ((P) is negative, the gradient is zero.
Optimization Using this estimatiin, we can minimize our loss using Adam (Kingma & Ba 2015) and Hill Climbing. Each optimization step begins with an optimization of the discrete variables followed by a standard, joint, Adam step for the continuous variables. For the discrete variables, we perform Hill Climbing and Adam. That is, for each discrete variable, we separately estimate its gradient and update the variable according to Adam's 's update steps. If the discrete variable is assigned an out-of-bounds value, its previous value is restored. We note that the optimizer has two optimization steps: Te for the continuous variables and na for the discrete variables. In practice, it is best that 7ı x 100- To reduce execution times, the optimization terminates if within T iterations, the loss has decreased by less than p%, where T and are hyper-parametert At the end, our adapted Adam optimizer returns a program with the optimized continuous and discrete parameters.
Real-value relaxation Although patches' position and dimensions are discrete variables, we ob- serve that it is better to allow them to take real values during optimization. This relaxation enables the optimizer variables would only take discrete values. With this relaxation, the discrete variables are rounded whenever P is invoked
small step sizes, and thereby reach solutions which may have been missed if the
input (as part of the optimization or when executing the attack).
4 APSYN: ADVERSARIAL PROGRAM SYNTHESIZER
In this section, we present APSyn, our system for synthesizing adversarial programs. APSyn aims at obtaining a minimal-sized patch sequence in order to compute the simplest attack. To this end, we employ a simple yet effective program synthesis approach called enumerative program synthesis, shown successful for many syntax- -gudxe synthesis instances. An enumerative synthesizer consid- ers programs of increasing size and checks whether they satisfy the specification. At each step, the synthesizer considers all programs of size k'. In our context, it is not feasible to consider every patch sequence of size k'. Instead, we search for useful programs of size k using the optimization described in the previous section. Since the optimization can return a local optimum, we invoke the optimizer multiple times with different initialization, and continue with the best solution. Algo- rithm shows the operation of APSyn. APSyn synthesizes the adversarial program patch-by-per patch.. At iteration i, it constructs the program P., by considering m patch candidates extend the previous program P:-1. For each candidate patch instruction I,. APSyn jointly optimizes over the variables in the extended program P.-1: as described in Section 3 The program P, is defined as the opti- mized program that has the best loss out of the m candidates and P 0 We note that it is possible to synthesize a full program from the beginning (instead of the enumerative search), but it requires many more iterations to converge successful adversarial program (see Section
'This is simplification, APSyn prefers program that generates an adversarial example over one with lower loss which does not generate an adversarial example.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1: APSyn (N, zr,
Input:
classifier N, an input z, target label t.
Output: An adversarial program over I.
Phest = po= = []: Lhestt 00
for i i; k; i do // Synthesize programs of increasing sizes
for j = 1: j S m; + + do // Consider m candidates
1 init()
P A-dammm--111 :: I,.N, 2, t)
if C(P) Lbbet then Lhast = L(P); Prest = P
P. =
Phest
return Poest
Initialization patch is initialized by sampling the dimensions (length and width) from uniform distribution and sampling values for a and / from Gaussian distributions. To initialize the starting position, we build on feature ablation. That is, APSyn considers every possible feasible starting position (i.e., one that together with the given dimensions fit within the image boundaries). For each possibility .c",,, it computes the potential decrease of the loss, we use that position in the new patch without any optimization. Overall, it initializes the starting position to the position minimizing C(P,-1 :: I_=_e".rr ".r""cc...a "=*,er"..c,.,, (z)))a))))) position and the patch's dimensions. To reduce the execution overhead of checking every possible
(z),,, where the ending position is inferred from the starting
starting position, we examine starting positions based on a stride typer-paramete.
5 EVALUATION
In this section, we evaluate APSyn. We implemented APSyn in Python using PyTorch. Our imple- mentation supports GPU parallelization. will be made available, for reproducibility, along with the experiments. Experiments with 1TB RAM and eight NVIDIA GeForce RTX 2080 Ti GPUs. Experiments ran for MNIST, Fashion-MNIST CIFAR-10, and ImageNet. Experiments were parallelized: between 4-7 APSyn's invocations on each GPU, depending on the dataset. For MNIST and Fashion-MNIST, we trained MnistNet models (186K parameters). For CIFAR-IO, we trained a ResNet-18 model (11.5M pa- rameters). For ImageNet, we imported a ResNeXI-50-32x44 model (25M parameters). We next provide the hyper-parameters. The scale and shift parameters were initialized by sampling from Gaussian distributions with mean 1 and 0 (respectively) and variance 0.3. Patch dimensions were sampled from a uniform distribution with range [5,15] (for ImageNet, [15,30], and the starting po- sition stride was 3 (for ImageNet, 10). The balancing factor À was 1 (for ImageNet, 0.05), the step sizes were 7) 0.01 (for ImageNet, 0.05) and π/ = 1 (for ImageNet, 2.5). The maximal number of iterations per optimization was 300 (for ImageNet, 400) and the stopping condition checked whether during the last 25 iterations (for ImageNet, 200) the loss has decreased by less than 0.5%.
on Ubuntu 18.04.5 OS on dual AMD EPYC 7742 server
Benchmarks and metrics For each dataset, our benchmark consists of three images for each class (for ImageNet, we focus on ten classes). In each experiment, we run APSyn for every image and every possible target class (for ImageNet, we focus on three target classes). total, our benchmarks consist of 270 attack specifications for each dataset (90 for ImageNet). We measure the success rate (fraction of programs that returned adversarial examples), Le distortion (L2 distance between the adversarial example and the input), and Lo distortion (Lu distance). We report execution time in minutes. We run every APSyn attack on all inputs in the test set whose label is c (the input's 's true label). We measure generalization rate (fraction of inputs for which the program returned adversarial examples) and generalization T-2 distortion (average La distortion on the test set). Execution times and all distortion metrics are reported only for successful attacks. As a baseline, we compare the C&W attack (on which we build our loss function), which is run in batches of 32 attacks.
Candidates We begin with studying the effect of the number of candidates (m) on the success rate, T.2 distortion and generalization rate. In this experiment, focus three datasets, and set the
5

---

Under review as a conference paper at ICLR 2022
100
3.0
Generalization Rat
8
success Rate
Distortion
95
2.5
2.0
90
Fashion-MNIST
CIFAR-10
1.5
85
6
10
2
4
10
10
# of candidates (m)
of candidates (m)
of candidates (m)
Figure 2: Effect number candidates on the success rate, L2 distortion, and generalization rate.
100
3000
k-7
LO Distortion
2000
kmm
CSW
50-
1000
MNIST
Feshion MNIST CITAR
MNIST
Fashian
Excecttio Time [m]
60-
Cen. Distortion
Generalization
10
-0
MNVSST
Fashior-MNIST
CIFAR-10
MNIST
Fashion MNIST
CIFAR-10
MNIIT
Fashion-MNIST
CIFAR-10
Figure 3: Effect number of patch instructions on APSyn's success rate, Le distortion, Lo distor- tion, execution time, generalization rate, and generalization L2 distortion on different datasets.
maximal number of instructions to k = 5. Figure shows the results as function of the number of candidates m (1, 5, 7, 10). As expected, as the number of candidates increases, the success rate increase and the L2 distortion decreases. However, the gain in adding more candidates is reduced as the number of candidates increases. From here on, we continue with m = candidates.
Program length We next study the effect of the maximal number of patches (k) on the success rate, Le distortion and the execution time of APSyn. Figure shows the results as a function of the maximal number of patches & E {1, 5, 7, 10}. As baseline, the figure also shows the results of the C&W attack. As expected, as the number patch instructions increases, the success rate increases, but with three patches APSyn usually obtains almost perfect success rate (similarly to C&W). The reason to include more than three patches mainly to reduce the L.2 distortion, as shown by the figure. Naturally, more patches is obtained for five patches. A unique feature of multi-pater mallti-pachh&a attacks is that in addition to minimizing the L2 distortion, they also attempt to reduce the La distortion, both by favoring fewer patches the attack and also by allowing overlapping patches. The figure shows how significant is the difference between the Ly distortion of APSyn and C&W. The lower La distortion may also indicate about the simplicity of physically executing our attacks compared to attacks with high Lu distortion. In terms of generalization, we see that the shorter the program the higher the generalization rate. This may be attributed to Occam's Razor: the simpler the attack the better its generalization rate. This also aligns with the very low generalization rate of the C&W attack, which can be viewed as a (very long) multi-patch attack. This encourages that multi mulli--ptthh attacks, which impose rigid structure on the attack can help design universal attacks. We leave this investigation to future work.
longer execution times. We observe that the best balance
ImageNet ImageNet attacks are naturally harder for APSyn and require more patches, candidates, and optimization iterations compared to the other datasets we consider. Naturally, this affects the ex- ecution time. Figure 4 shows the success rate, La and Lo distortion and execution time for different combinations of number of candidates and patches. Results show that the success rate significantly increases with the increase in the number of patches and candidates. Interestingly, the Lg distortion similar in all the combinations, while the Lp distortion decreases for more patches. This because attacks with ten patches often have more overlaps between patches than attacks with five patches.

---

Under review as a conference paper at ICLR 2022
15000
Execution Time [m]
Success Rate
80
Distortion
LO Distortion
(k.m)=(5.7)
(k.m)-(5.10)
20
10000
(k-m)-(7.7)
40
200
(km))((7.10)
5000
[km))=11077
20
(k.m)=(10,10)
Figure 4: APSyn's success rate, L2 and Lo distortion, and execution time for ImageNet.
100
Execution Time [m]
APSyn
Distortion
Success Rate
enumeration
2
50
(3.3)
(3:5) (5,3) (5.5)
13,3) (3.5)
(5.3) (5,5)
(3,3) (3.5) (5.3) (5,5)
(# patches, candidates)
(# patches, # candidates)
(# patches, # candidates)
Figure Comparison enumerative synthesis vs. full-program optimization.
Enumerative synthesis We next show the advantage using enumerative synthesis over the more common approach in continuous optimization, which optimizes over all variables from the begin- ning. Figure shows, for different numbers of patches and candidates (k, m), the success rate, L2 distortion, and execution time of both approaches. Results show that both approaches obtain simi- lar success rate and L2 distortion, however enumerative synthesis drastically reduces the execution time: up 3x. This is significant because APSyn's 's execution time is not negligible.
Examples of ad adversarial programs Lastly, Figure illustrates generates. For each image, the figure shows the adversarial examples of C& W and APSyn, and the differences between the adversarial examples and the input image. The pixels in the difference image range over [0, 1] in order to show whether the perturbation brightened or darkened the pixel (i.e., 0.5 corresponds to unperturbed pixel, 0 for maximal darkening, and for maximal brightening). The examples illustrate that APSyn's 's attacks are imperceptible, even though the L2 distortion is higher than C&W's. The examples also demonstrate that because our attacks are restricted patches, they provide an explanation to the exploitable regions. For example, in the bag example, APSyn creates patch which darkens the purse handle; in the digit six example, APSyn brightens the upper part using horizonal patch and darkens the lower part of the digit towards making it look like the digit five; similar pattern is observed in the digit nine example. We believe this opens new direction of explaining network robustness using programs. We leave this to future work. Another interesting property is that patches tend to concentrate in and around the main object. This may suggest that attacks can be directly executed physical objects. Lastly, the examples show that APSyn sometimes returns programs that are shorter than the maximal number patches k. This demonstrates the advantage of using enumerative synthesis which favors shorter solutions.
of the attacks that APSyn
RELATED WORK
Our work is mainly related to Carlini & Wagner (017)) and Brown et al. (2017). Carlini & Wagner (017) consider imperceptible attacks and propose several losses. While successful, is hard to physically execute this attack because it perturbs a very large number of pixels. On the other hand, Brown et al. (2117) consider an attack executed by a visible patch. Their attack looks for the optimal perturbation, given the patch position and dimensions. This work also aims at generating patches universal to scenes and robust to transformations. In this work, we show that it possible to enjoy both worlds by allowing multiple patches, each incurring small L2 distortion. Unlike Carlini & Wagner (2017), our attacks are defined over discrete variables. We show that by estimating the gradients of the discrete variables and by relaxing them to keep real values during optimization,

---

Under review as a conference paper at ICLR 2022
Original
CW Attack
CW Diff
Our Attack
Our Diff
Our Program
Pbi 100
#16) 50.0%
Lo Norm 551
HS3 42.1% 6
1. Norm 70
6
6
ML-35. 4.31
MS) 0.0%
P15: 0%
12 Norm -
RS) - 34
12 Norm
101 8201
RL34-44 4333
10-23, 8-39
PiDresdi 0.0% #1aagi 100.0%
PiDresst
Noem Lo Nort 667
PiDressi 45.1% RB:ogl - 30.0%
Morm L0 Norm 132
R(Sogl 40.4%
1L. 6.91
Pidoo)
Pidogl 7ts
Ridog)
Norm 1672
Nerm 198.
IEAz 61 6280
FAR 844 100
ESLE 8.7, 142)
Picat) 0.3% Pideee))
Picati - 51, 9% [[cwer]
12 Norm m 0.04
Picat) 47 5% (ideer)
Moem = 0:25
KSL AALL
1OL35 1OL3L- 8,00 BANL
(ttranbula) 103.0%
Plararfufal 30.3%
Morm = 150532
Mitaranulal 6.5%
LO Norm 5539
K11.4 21. 1.91
E33.7 1.37 8,5h
1-8 - 4.40
I-liat -8.201
Figure 6: Examples of the attacks APSyn generated compared to the C& attack.
the C&W loss is highly effective for producing adversarial examples even if the perturbation region constrained. Unlike Brown et al.] (2017), our work shows how to efficiently search for optimal position and dimensions of patches, which is crucial for minimizing distortion without reducing the success rate. We further build on program synthesis to search for attacks which minimize the number of patches. This allows APSyn to identify short and simple attacks and reduce execution times. Our attacks can be further optimized for universality by leveraging the ideas of Brown et al. (2017). We leave this for future work. Differently from both these works, our attacks have a rigid structure and restricted kind of perturbations. This forces APSyn to look for the most exploitable regions, which makes our attacks more explainable.
Digital Attacks Since the introduction of adversarial examples (Szegedy al. 2014 Goodfellow et al., 2015), many works have proposed adversarial attacks for various domains, perturbation kinds, and distortion metrics. A large body works focuses on digital attacks for images, which induce artificially crafted additive noise digital image before using it as input to DNN. Some no- table works include Carlini Wagner (2017 7): Moosavi- Dezfooli et al. (006); Modas et al. (2019); Papernot et al.] (2016); Moosavi- Dezfooli Dezfool
al. (201)); Madry al. (2018) These works focus on minimizing L2/ Loo distortion, which are differentialee functions, and are thus amenable to gradient-based optimization. Fewer works focus minimizing T.g distortion, which is discrete
8

---

Under review as a conference paper at ICLR 2022
metric, and thus requires different kind of optimization. For example, Su et al. (2019) employ differential evolution strategy. While successful for few pixels, our attempts to use it for multi-patch attacks suggest that this technique struggles to succeed when the number of perturbed pixels is large.
Laidlaw & Feizi (2019) compute functional attacks, a concept which is similar in spirit to our patch programs. However, their attacks may perturb a large portion of the image pixels.
Physical Attacks Digital attacks are generally harder to execute in realistic setting where an attacker has to manipulate physical objects. This has led to studying physical-world attacks. Ku- rakin et al. (2017) use cell-phone camera to photograph printed images of adversarial attacks and showed that they remain adversarial and are robust to the transformations and the noise resulting from the phone and camera processing. In contrast, Lu et al. (2017) use traffic sign images show that adversarial examples are less successful when viewed from different angles and distances. Sev- eral works propose use stickers and 3D-printed objects to execute adversarial attacks in realistic environment. Sharrif et al. (2018) propose a generative approach to generate 3D adversarial glasses to fool face recognition classifiers. Athalye et al. (2018) generate adversarial attacks using printed 2D images and 3D objects which are robust under synthetic image transformations. [Ekhhlt et al. (2018) rely on specially-
stickers on physical traffic signs to generate adversarial attacks that are robust for different distances and angles. This attack computes multiple stickers. whose position and dimensions are determined by first running their optimization on the entire region, but favoring sparse perturbations. Based on the resulted attack, stickers are positioned in the most vulnerable regions, and then the optimization runs again. In contrast, APSyn relies on enumerative synthesis to guarantee it computes a minimal patch sequence. [i ct al. (2019) generate robust adversarial attacks by placing stickers on camera lens. Jere et al. (2019) introduce scratch attacks for image captioning. Another approach to physical attacks assumes the adversary can change the network's 's behavior to respond to malicious objects (e.g.. trojan attacks Liu et al. (2018); Ji et al.] (2018) and poisoning attacks (Gu et al.] 2017)). Brrwn et al. (2017) introduce robust and universal attacks via adversarial patches. Karmon et al. (2018) propose smaller and less visible adversarial patches, but these are not universal. (Liu al.|||001 [01 Bai et al.) 202T) rely on GANs generate inconspicuous patches. (Liu et al. [019b]] Lee & Kolter 2019 Thys et al. 2019 Lang et al., 2021: Wu et al.) 2020; Xu et al., 2020 use different variations of adversarial patches to fool object detection models causing them to miss the target object. [Tu et al. (2020) generate printed 3D objects that fool LIDAR detectors. Liu
ctt al. (2020) generate realistic patches on grocery items using a bias-based approach. Lovisotto al. 1 generate short-lived localized adversarial attacks by utilizing an RGB projector and model- ing the three-way relationship between a surface, a projection and the camera- perreieeereeived image. In contrast, attacks rely optimization of patch sequences, which enable APSyn to reduce the L2 distortion to an imperceptible level. A key factor in the success of APSyn is the optimization of the patches' dimensions and position. While have not physically executed attack, we believe it can be combined with the above attacks to reduce their distortion.
Patch Attacks addition to the above patch attacks which have been designed for a physical setting, several other works showed successful patch attacks. Andriushchenko et al. (2020) rely on random search to generate attacks consisting of squares. Unlike our work, their attacks consist of a very large number of patches and their Ly distortion is very high. Yang al. (2020) rely rein- forcement learning to generate a visible texture- texture-based patch picked from a predetermined dictionary. Rao et al. (2020) generate visible patch attacks, and rely patch position. In contrast, our approach is to first to create minimal multi-patch attacks, where patches can overlap, and their position, dimensions, and perturbation factors are jointly optimized.
similar idea to ours to optimize the
CONCLUSION
We presented APSyn, a synthesizer of multi-patch attacks. APSyn searches for minimal sequence of patches that produces an adversarial example with a minimal Le distortion. Unlike previous patch/sticker attacks, APSyn optimizes over the patches' position and dimensions. To this end, we introduce a gradient estimate for the discrete variables and relax them to keep real values during the optimization. To further minimize the number of patches and improve execution times, APSyn employs enumerative synthesis. We evaluate APSyn on four datasets and show that it generates imperceptible attacks with few patches.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work introduces a new kind of adversarial attacks and thus has a potential negative impact. However, since our approach can pinpoint more exploitable regions and generate attacks in the form of short program, we believe it can help network designers understand vulnerability aspects of their networks. This can help them in improving the robustness of their network, e.g., using defenses.
REFERENCES
Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax- guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD 2013, Portland, OR, USA, October 20-23, 2013, pp. 1-8. IEEE, 2013.
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square at- tack: query-efficient black-box adversarial attack via random search. In ECCV, 2020.
Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssaan, Stockholm, Sweden, July 10- 15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 284-293. PMLR, 2018. URL http: http::/prrceeeiinggggg www.hnsssss.....mmm. m.r prw.s/pessseeo... http:/v0///aaaa htt../g...........e.////taaaaaaa
Bb. html
Tao Bai, Jinqi Luo, and Jun Zhao. Inconspicuous adversarial patches for fooling image recognition systems on mobile devices. arXiv preprint 2tti::2006.122022 2021.
Tom B. Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch. CoRR, abs/1712.009655, 2017. URL /wtp/v/aavvvvvva/ org/ wwwp/as/////ooooooo//.o///aaaeee /1222.11111 09665
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pp. 39-57. IEEE, 2017.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In 2018 IEEE Conference on Computer Vision and Par- tern Recognition, CVPR 2018, Salt Lake City, UT. USA, June 18-22, 2018, pp. 1625- 1634. Computer Vision Foundation / IEEE Computer Society, 2018. doi: 10.1 10.1109/ 2018,00175.
thecvf com/ content eet_eee________eeeeeeeeeeeeeeeee 2018/htm1/ Eykholt Robust Physicallysaaa World Attacks CVPR 2018 pwwpppppppp......
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA. USA, May 7-9, 2015, Conference Track Proceed- ings, 2015.
Tianyu Gu, Brendan Dolan-Gavite and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv:1708.06733. 2017.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Found. Trends Program. Lang., 4(1 4112):1-119, 2017. doi: 10.1561/250000000. URL httpps://dot htt////i..oooo/////// 10.g/10.151111
2500000010
Malhar Jere, Briland Hitaj, Gabriela F. Cretu-Ciocarlie, and Farinaz Koushanfar. Scratch that! an evolution-based adversarial attack against neural networks. ArXiv, abs/1912.02316. 2019.
Yujie Ji. Xinyang Zhang, Shouling Ji, Xiapu Luo, and Ting Wang. Model-reuse attacks deep learning systems. In Proceedings of the 2018 ACM SIGSAC conference on computer and commu- nications security, pp. 349-363, 2018.
Danny Karmon, Daniel Zoran, and Yoay Goldberg. Lavan: Localized and visible adversarial noise. In International Conference on Machine Learning, pp. 2507-2515. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2022
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015. Conference Track Proceedings, 2015.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017. URL https: //openreview. net/
Cassidy Laidlaw and Soheil Feizi, Functional adversarial attacks. In NeurlPS, 2019.
Dapeng Lang, Deyun Chen, Ran Shi, and Yongjun He. Attention-guided digital adversarial patches on visual detection. Security and Communication Networks, 2021, 2021.
Mark Lee and Zico Kolter. On physical adversarial patches for object detection. arXiv preprint arXiv: 1906. / 1897, 2019.
Juncheng Li, Frank R. Schmidt, and J. Zico Kolter. Adversarial camera stickers: A physical camera- based attack on deep learning systems. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 3896-3900 PMLR, 2019. URL http:::/prrceeeeengggg www.mm.....r.....mmmmmmmmmmmm..e secess/vv9// /wtp/////////1///// html
Machine Learning, ICML 2019, 9-15 June
Aishan Liu, Xianglong Liu, Jiaxin Fan, Yuqing Ma, Anlan Zhang, Huiyuan Xie, and Dacheng Tao. Perceptual-sensitive gan for generating adversarial patches. In Proceedings of the AAAI confer- ence on artificial intelligence, volume 33, pp. 1028-1035, 2019a.
Aishan Liu, Jiakai Wang, Xianglong Liu, Bowen Cao, Chongzhi Zhang, and Hang Yu. Bias-based universal adversarial patch attack for automatic check-out. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XIII 16, pp- 395-410 Springer, 2020.
Xin Liu, Huanrui Yang, Ziwei Liu, Linghao Song, Yiran Chen, and Hai Li. DPATCH: an adversarial patch attack on object detectors. In Huáscar Espinoza, Seán Ó hEigeartaigh, Xiaowei Huang, José Hernández-Orallo, and Mauricio Castillo-Effen (eds.), Workshop on Artificial Intelligence Safety 2019 co-located with the Thirty-Thirl AAAI Conference on Artificial Intelligence 2019 (AAAI-19), Honolulu, Hawaii, January 27, 2019, volume 2301 of CEUR Workshop Proceedings. CEUR-WS.org 2019b. URL hul.:tp::. ceur org Vol 2301 happppppppp...
Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen WennChhuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018. The In- temett Society, 2018 URL http: / wp. www.eneeeeeeiiiiee...m wrt.ty...rrono http//dass///e /wp content/ Lpploats/iiee/5550D1II 20t 03A-5 Liu paper. pdf
Giulio Lovisotto. Henry Turner, Ivo Sluganovic, Martin Strohmeier, and Ivan Martinovic. {SLAP): Improving physical adversarial examples with short-lived adversarial perturbations. In 30th (USENIX) Security Symposium (USENIIX) Security 21), 2021.
Jiajun Lu, Hussein Sibai, Evan Fabry, and David Forsyth. No need to worry about adversarial examples in object detection in autonomous vehicles. arXiv preprint 17Xiv 03550,, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htl.ttp:://eeeeeeeeee.ee [Forum2id=:J13f222
MnistNet. https: www.ke/gge...mmmaaaaaa///tttteee

---

Under review as a conference paper at ICLR 2022
Apostolos Modas, Seyed-Mohsen Moosavi-Dezfer and Pascal Frossard. Sparsefool: A few pixels make a big difference. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019. Long Beach, CA. USA. June 16-20, 2019, pp. 9087-9096. Com- puter Vision Foundation / IEER, 2019. doi: (t01////VR.2211..00999 7/openaccess thecv com/ comm/oootttttvtec CVPR 1 SparssFool.
URL http:
A Few Pixels Make Big Difference CVPR 2019 Balllpppppp___ saape..hmml
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 2574-2582. IEEE Computer Society, 2016. doi: 2..109//CVP.22016.222 11C9/CVPR. 282
UtLhttps: //oi: http://too..g...../o
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pp. 86 66-94. IEEE Computer Society, 2017, doi: 10.1100//VVP.2011..117 hRLhttps:: /wi./iiio./////// org 10. 1 2wt.099/V..22117770
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In 2016 IEEE European sympo- sium on security and privacy (EuroS&P), P), pp. 372-387. IEEE, 2016.
Sukrut Rao, David Stutz, and Bernt Schiele. Adversarial training against location-optimized adver- sarial patches. In ECCV Workshops, 2020.
Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K. Reiter. Adversarial generative nets: Neural network attacks on sfate-of-the the-art art face recognition. CoRR, hts/1801.00344 2018.
URL http::htta/piii// org/ abs /wt./1111..0 00349
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 23(5):828 841, 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan J. Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Simen Thys, Wiebe Van Ranst, and Toon Goedemé. Fooling automated surveillance cameras: ad- versarial patches to attack person detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 0-0, 2019.
James Tu, Mengye Ren, Sivabalan Manivasagam, Ming Liang, Bin Yang, Richard Du, Frank Cheng, and Raquel Urtasun. Physically realizable adversarial examples for lidar object detection. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13716- 13725, 2020.
Abhishek Udupa, Arun Raghavan, Jyotirmoy V. Deshmukh, Sela Mador-Haim, Milo M. K. Martin, and Rajeev Alur. TRANSIT: specifying protocols with concolic snippets. In Hans-Jurrgen Boehm and Cormac Flanagan (eds.), ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '1, Seattle, WA, USA, June 16-19, 2013, pp. 287-296. ACM, 2013.
Zuxuan Wu, Ser-Nam Lim, Larry S. Davis, and Tom Goldstein. Making an invisibility cloak: Real world adversarial attacks on object detectors. In ECCV, 2020.
Kaidi Xu, Gaoyuan Zhang, Sijia Liu, Quanfu Fan, Mengshu Sun, Hongge Chen, Pin-Yu Chen, Yanzhi Wang, and Xue Lin. Adversarial t-shirt! evading person detectors in a physical world. In ECCV, 2020.
Chenglin Yang, Adam Kortylewski, Cihang Xie. Yinzhi Cao, and Alan Loddon Yuille. Patchattack: A black-box texture- based attack with reinforcement learning. ArXiv, a0s622004.0582,, 2020.
12

---

Under review as a conference paper at ICLR 2022
1.00
Success Rate
0.75-
L2 Distortion
LO Distortion
1000
750
APSyn
w/o optimication
0.50-
500
0.25
250
MNIST
Fashion MNIST CIFAR 10
MNIST
Feshion MNIST
CIFAR
MN
Fashion MNIST CIFAR 10
Figure 7: Comparison of AP$yn with a baseline that does not perform optimization and baseline that does not perform adaptive optimization.
A APPENDIX
In this section, we study the effectiveness of our discrete optimization (via gradient estimation and adaptive optimization). To this end, compare APSyn to two baselines. The first baseline is identical to APSyn but does not optimize the discrete variables. That is, patches are added one- by-one, their parameters are initialized described in Section 4 (including
feature ablation approach for initializing patch position), and the continuous variables are optimized for the C&W loss with gradient descent. The second baseline is the same APSyn, but without our adaptive optimization of the discrete variables (employing Hill Climbing and Adam steps). That is, the second baseline jointly optimizes all variables (discrete and continuous), and the step size of all discrete variables is the same. In this experiment, we set the maximal number of patches to k = 5, 7. Figure shows the success rate, L2 distortion, and Lo
and the number candidates to distortion of all approaches. Results show that our discrete optimization enables APSyn to obtain higher success rate and significantly lower L2 and Lo distortion. That is, it improves both the success rate and the imperceptibility of the generated attacks. Results also show that our adaptive discrete optimization enables APSyn to obtain significantly lower Lo distortion, and also improve success rate and L2 distortion.
13


Reviews:
[{"review_id": "uJIDV4cL-L9", "reviewer": "Reviewer_tecw", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n(I) The paper proposes an approach for optimizing the patch location/dimension (while prior works usually fix the patch location/dimension for simplicity).\n\n(II) It is interesting to see the authors formulating the attack as a program synthesis problem (though I have concerns about the necessity of such a formulation; see weakness II below).\n\nWeaknesses:\n\n(I) The paper does not provide enough motivation and justification for its problem setup. It might be trivial to succeed in this attack \n1. The problem formulation does not have any constraint for the L_0 distortion (i.e., the sizes and the number of patches)! Therefore, the problem reduces to the global L_2 perturbation (e.g., the C&W attack) when the patch covers the entire image. As a result, there are existing solutions (e.g., functional adversarial attacks [1]) to this problem, which undermines the contributions of this paper. I would suggest the authors have both L_0 and L_2 constraints in the problem formulation and algorithm design. Also, I would appreciate it if the authors could clearly state the challenges of this problem, and discuss the problem/algorithm with relevant works [4,5] in more detail.\n\n2. The attack formulation does not fully capture the nature of physical attacks. The paper assumes that the patch attack is always physically realizable. This is not true; the perturbations within the patch can be too subtle/small to be realized (e.g., printed) in the physical world (Sharif et al. [2] defined the non-printability score). Since the paper does not evaluate the attack in the physical world setting, I would suggest the authors rephrase the problem as finding a balance between L_2 and L_0 attacks (instead of claiming the attack is physically realizable).\n\n3. The paper does not explain why it only considers pixel scaling and shifting within the patch. There can be a more imperceptible and more effective perturbation (compared to scaling and shifting) for the patch. Maybe the authors assume that scaling and shifting make the attack more physically realizable, but more justifications are necessary.\n\n4. The authors formulate the attack as a program synthesis problem; however, I find the core idea does not involve anything about problem synthesis. The core algorithm is to (1) initialize a random patch; (2) optimize over the pixel values and (discrete) patch locations; (3) depending on a certain condition, continue to add another patch or return the generated adversarial examples. The authors did not use any technique from program synthesis in their algorithm; therefore, I find such a formulation only adds unnecessary complexity to the paper, and I would suggest discarding this formulation.\n\n(II) The proposed method lacks novelty\n\n1. As discussed in weakness I.4, the authors do not adapt any technique from program synthesis in the proposed approach, though they formulate the problem as program synthesis.\n\n2. The problem of imperceptible patches is not new [4,5].\n\n3. The loss for the attack is from existing work (C&W attack).\n\n4. The estimation of gradients of discrete values looks straightforward; the evaluation (Figure 5) shows that this approach only improves the attack efficiency at the cost of a small drop in attack success rate. Also, the experiment does not have enough comparison with baselines (see weakness III) to demonstrate the effectiveness of the gradient estimation.\n\n(III) The experiment lacks a reasonable baseline comparison and a comprehensive ablation study. \n\n1. The attack performance comparison seems unfair. The paper compares APSyn with C&W, while C&W is designed for global perturbations. Therefore, it is unsurprising to see APSyn has a smaller L_0 distortion and a large L_2 perturbation(Figure 3). Moreover, there is a relevant paper that discusses patch location optimization [3]. Also, imperceptible patches are studied in prior works [4,5]. These papers should be a more reasonable baseline to compare with. \n\n2. There is another simple baseline for this approach: randomly pick the patch location/dimension and then use the C&W attack with an L_2 constraint to find the perturbations. This should be a baseline to show that the discrete value optimization for patch location/dimension is useful.\n\n3. Why did the experiment consider all 9 target classes for the 10-class CIFAR-10, MNIST, Fashion-MNIST datasets but only consider 3 target classes for ImageNet (Note that the authors consider 10 classes for ImageNet but only 3 *target* classes)? Is it because your approach is expensive for high-resolution images? Moreover, the experiment only considers *three* images for each dataset; its results may not be representative.\n\n4. For the experiment setup, the authors simply report the default hyperparameters (e.g., \\lambda, \\eta, scale, mean/std of Gaussian) without any justification. There is no ablation study. I suggest the author at least report the trade-off between attack success rate and attack time (balanced by the number of patches/candidates). \n\n(IV) Finally, though it is minor, the mathematical presentation can be improved. Here is an incomplete list of notation issues that I noticed:\n\n1. $m$ is used multiple times (as the mask and also the number of patch candidates)\n2. $\\lambda$ is used multiple times (in the formulation of adversarial programs, and in C&W attack as the balancing weight)\n3. In “adversarial programs”, there is an inconsistency between $I_{\\alpha,\\beta,p}$ and $I_{\\alpha,\\beta,m}$.\n\n[1] Laidlaw et al., “Functional Adversarial Attacks”, NeurIPS 2019.\n\n[2] Sharif et al., “Accessorize to a Crime: Real and Stealthy Attacks on State-of-the-Art Face Recognition”, CCS 2016.\n\n[3] Rao et al., “Adversarial Training against Location-Optimized Adversarial Patches”, ECCV  workshop 2020.\n\n[4] Liu et al., “Perceptualsensitive GAN for generating adversarial patches”, AAAI 2019.\n\n[5] Bai et al., “Inconspicuous adversarial patches for fooling image recognition systems on mobile devices”.\n", "summary_of_the_paper": "This paper proposes APSyn to generate a sequence of imperceptible adversarial patches for a physical and imperceptible attack against image classification models. This attack is a combination of physical patch attacks and conventional imperceptible perturbation attacks. In APSyn, the authors formulate the attack problem as adversarial program synthesis and use gradient-based optimization to search for the optimal solution (a method for estimating the gradient for discrete values is also proposed). The experiments on small subsets of the MNIST, Fashion-MNIST, CIFAR-10, and ImageNet demonstrate that the proposed approach can achieve smaller L_0 distortion and larger L_2 distortion compared to the C&W attack.", "summary_of_the_review": "Based on the three issues listed below, I would recommend rejecting this paper.\n\n1. The problem is not well motivated and justified (see weakness I), and it might be trivial to succeed in this attack (see weakness III.2). I would suggest reformulating the problem setup and algorithm (see the main review for detailed suggestions) and clearly stating the challenges of this problem.\n\n2. The proposed solution seems to be a very straightforward combination of several existing algorithms. The simplicity of the algorithm is not bad; however, I would encourage the authors to clearly state (1) why this problem is challenging; (2) why their proposed approach is non-trivial and novel; (3) how effective the proposed approach is (requires more baseline comparisons).\n\n3. The evaluation is incomprehensive, and the performance comparison chooses an unreasonable baseline (see weakness III). I would suggest adding more experimental comparisons with other baselines to demonstrate the effectiveness of the proposed approach (see the main review for detailed suggestions).\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "teZR7MgJiP", "reviewer": "Reviewer_xXLy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The idea of the paper is well motivated, and it is a natural direction to explore the possibility of imperceptible patches. The formulation of adversarial programs is neat and quite clever to get around the discrete nature of gradient. I do notice a couple of places where the reality is less optimal than the assumptions such as eta_c vs eta_d, these empirical values are sometimes physical constraints that researchers have to deal with. \nIn general, I like the evaluations shown in figure 2-figure 5, these results indicate the proposed method is effective.\n", "summary_of_the_paper": "This paper focuses on crafting imperceptible patches to fool image classifiers. The method leverages program synthesis and numerical optimization  and produces perturbations with a lot less perturbed pixels compared to baselines. The experiments on various image datasets demonstrate the effectiveness of the method.", "summary_of_the_review": "However, I have 2 minor concerns:\n1. The title of the paper boasts “physical”, and yet figure 6 indicates the experiments were mainly carried out digitally. What’s the real physical performance? I.e. how effective is the proposed method when deployed in the real physical world?\n2. This work mainly used l2 distance to measure distortion, but l2 distance sometimes could be flawed itself, how about measure the distance between 2 distributions? Would that change the results?\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bAA_O3hnDx7", "reviewer": "Reviewer_Uj1D", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This work frames the adversarial attack as a program synthesis problem, which is interesting. However, I don't think this problem setup is very well-motivated. Specifically, there might be simpler adaptions of existing adversarial attack algorithms that can achieve similar or better performance, while they do not require a computationally expensive program search process. I discuss the details as follows.\n\n1. I find that the confidences of the generated adversarial examples are all pretty low. Have you tried to generate adversarial examples that are highly confident in the target labels, e.g., >95%? What is the attack success rate of generating such strong adversarial examples, and what is the execution time? My concern is that this requirement could further slow down the program search process, and makes the proposed approach even much slower than the baseline adversarial attack algorithms.\n\n2. Is it necessary to search for patch positions? If the goal is to generate multi-patch adversarial examples, one simpler approach is to randomly generate several masks, and optimize the perturbations in the regions covered in the mask. Have you run this baseline?\n\n3. Is there any reason to build upon C&W, instead of some other adversarial attack algorithms, e.g., PGD? Have you tried existing L0 adversarial attacks, and does your algorithm perform better than these existing attacks?\n\n4. The authors demonstrate some generalization results, i.e., using the same program to generate perturbations for multiple images. While it is interesting to see some transferability, the current generalization rate is still pretty low, and is not competitive compared to prior works focusing on universal adversarial perturbations. Given that the approach still needs to generate one program per input image, in general the proposed approach is computationally expensive, and thus its usage is unclear.", "summary_of_the_paper": "This paper studies multi-patch adversarial attacks, where each perturbation is generated via a program. Since the program includes both discrete variables and continuous parameters, they design a gradient estimation scheme for optimizing the parameters, and a program search algorithm to search for programs with increasing lengths. On several image classification benchmarks, they demonstrate that their approach achieves decent attack success rates and low L2 distortion, which are comparable to the C&W attack. Meanwhile, their attack requires much lower L0 distortion.", "summary_of_the_review": "This work frames the adversarial attack as a program synthesis problem, which is interesting. However, I don't think this problem setup is very well-motivated. Specifically, there might be simpler adaptions of existing adversarial attack algorithms that can achieve similar or better performance, while they do not require a computationally expensive program search process.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FOrSvods4a", "reviewer": "Reviewer_3vSm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "1. This work is not novel as shape-based attacks are well-explored in the black-box setting [1-3]. The method proposed in this paper is very similar to Square Attack proposed in [1], except that it is done under the white-box setting rather than the original black-box. The related works section should mention and differentiate this paper from them.\n2. The evaluation is lacking in terms of compared attacks. How does it compare to the popular projected gradient descent (PGD) (originally introduced in [4]), and generally stronger white-box attacks such as [5-7]? The results are missing important comparisons here.\n3. The reviewer believes that introducing the patch-based attack as an application of SyGuS is detrimental to the contribution of the paper, for the reasons below:\n\t1. The adversarial programs are not actual computer programs as they are not Turing complete. They can simply be reduced to sequences of patches, or even sets of patches if order independent.\n\t2. SyGuS is not rigorously introduced in the paper, even the section introducing APSyn does not mention SyGuS and how APSyn is related. It is unclear why the authors chose to emphasize the patches as programs.\n\nSome other minor issues:\n* In the abstract, it was mentioned that “the average L2 distortion is greater than the average L2 distortion of the C&W attack by up to 1.2.” The reviewer is confused how a greater L2 distortion than the baseline is better. Perhaps you mean smaller?\n\nReferences:\n```\n[1]: Andriushchenko et al., Square Attack: a query-efficient black-box adversarial attack via random search, ECCV 2020. https://arxiv.org/abs/1912.00049\n[2]: Jere et al., Scratch that! An Evolution-based Adversarial Attack against Neural Networks. https://arxiv.org/pdf/1912.02316.pdf\n[3]: Yang et al., PatchAttack: A Black-box Texture-based Attack with Reinforcement Learning, ECCV 2020. https://link.springer.com/chapter/10.1007/978-3-030-58574-7_41\n[4]: Mary et al., Towards Deep Learning Models Resistant to Adversarial Attacks. https://arxiv.org/abs/1706.06083\n[5]: Croce et al., Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. ICML 2020. http://proceedings.mlr.press/v119/croce20b.html\n[6]: Yu et al., LAFEAT: Piercing Through Adversarial Defenses with Latent Features. CVPR 2021. https://openaccess.thecvf.com/content/CVPR2021/papers/Yu_LAFEAT_Piercing_Through_Adversarial_Defenses_With_Latent_Features_CVPR_2021_paper.pdf\n[7]: Tashiro et al., Diversity Can Be Transferred: Output Diversification for White- and Black-box Attacks. NeurIPS 2020.\n```", "summary_of_the_paper": "This paper proposes a white-box attack to generate rectangular patches of pixel color shifts as a means to generate adversarial examples for DNNs. As direct gradients for discrete parameters $w$ in a patch is not obtainable, the gradients are approximated with differences such as $L(w + 1) - L(w)$.\n", "summary_of_the_review": "The reviewer cannot recommend acceptance because this paper is lacking in novelty and empirical evaluation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "BMehO96Hb6u", "reviewer": "Reviewer_H5Ak", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Strengths**\n1. This paper is easy to follow and well organized.\n2. The proposed Adversarial Program Synthesizer (APSYN) is novel. This paper regards the generation of adversarial examples as a programming problem and designs an adversarial patch-based programming language to handle this issue. Experiments demonstrate the effectiveness of APSYN.\n3. Considering that each adversarial patch only scales or shifts a specific part of the input, the generated adversarial examples are more explainable compared to other white/black-box gradients-based attack algorithms.\n\n**Weakness**\n1. This paper aims to generate a kind of physical imperceptible patches. However, there is no evidence of the effect of placing these patches into the physical world. These patches are valid and imperceptible in the constraint of $\\ell_0$ or $\\ell_2$ norm but that doesn’t mean they are still valid in the physical world.\n2. Based on Section 3 and Section 4, the proposed APSYN algorithm utilizes zero-order optimization to update its weights. So it seems like the APSYN is a black-box attack algorithm. However, in Section 2 this paper \"assumes white-box access to the classifier\" and there are no actual gradients appearing in the algorithm description which is confusing.\n3. In terms of L2 distortion, the generated adversarial samples are larger than samples created by other attack algorithms (e.g., C&W).\n4. Missing some related physical world patch attack methods in the related work [1,2].\n\n[1] Wu, Zuxuan, et al. \"Making an invisibility cloak: Real world adversarial attacks on object detectors.\" European Conference on Computer Vision. Springer, Cham, 2020.\n\n[2] Xu, Kaidi, et al. \"Adversarial t-shirt! evading person detectors in a physical world.\" European Conference on Computer Vision. Springer, Cham, 2020.", "summary_of_the_paper": "The paper proposed a new adversarial perturbation by stacking imperceptible adversarial patches. Each adversarial patch could be regarded as a disturbance rectangle mask and contains learnable coordinates, scaling, and shifting factors. By applying an adversarial patch into the input sample (e.g., image), the values of input inside the mask will be scaled and shifted. These adversarial patches are stacked and generated by solving an adversarial program problem with zero-order optimization and numerical optimization.", "summary_of_the_review": "Generally, this paper proposed a novel programming-based adversarial perturbation and it is effective and competitive in various benchmarks. However, this paper aims to generate a physical imperceptible perturbation but doesn’t well-supported by experiential results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies physical "adversarial programs" that allow an attacker to control a machine learning model by placing transparent patches on top of an image. The reviewers are split on this paper: while some reviewers like the work, others are concerned about the practicality, novelty, or utility of the attack.

Starting with novelty, reviewers raise valid concerns about how this approach is similar to prior attacks that generate programs. The authors respond here, but the overall question remains unanswered and it is not clear which of the new pieces this paper introduces are responsible for the success. (Would prior techniques have sufficed? If not what part of prior methods makes this not the case?)

For utility, the paper does not make a clear case of why it would be easier for an adversary to place N~=5 patches on top of an image as compared to other physical attacks (see especially Li et al. 2019 as a paper that deserves more than a sentence of comparison---why is this approach easier?).

One final comment raised by many reviewers is the fact that the title and setup to this paper heavily lean on the "physical" component of the evaluation, and yet the paper does not demonstrate anything physical. The authors rebuttal that the word "towards" absolves them of responsibility for trying an attack in the real world does not convince me; either the paper should attempt this attack in the physical world (and say if it works or if it doesn't) or make it clear from the top that the attack is going to be digital from the start, but motivated by the physical world. Prior accepted papers that include physical world in the title (e.g., Kurakin et al., Athalye et al., Li et al.) don't solve the problem completely, but at least run experiments in the physical world.
Decision: Reject