Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: **Strengths**
1. This paper is easy to follow and well organized.
2. 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.
3. 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.

**Weakness**
1. 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.
2. 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.
3. In terms of L2 distortion, the generated adversarial samples are larger than samples created by other attack algorithms (e.g., C&W).
4. Missing some related physical world patch attack methods in the related work [1,2].

[1] Wu, Zuxuan, et al. "Making an invisibility cloak: Real world adversarial attacks on object detectors." European Conference on Computer Vision. Springer, Cham, 2020.

[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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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)$.

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.
2. 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.
3. 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:
	1. 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.
	2. 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.

Some other minor issues:
* 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?

References:
```
[1]: Andriushchenko et al., Square Attack: a query-efficient black-box adversarial attack via random search, ECCV 2020. https://arxiv.org/abs/1912.00049
[2]: Jere et al., Scratch that! An Evolution-based Adversarial Attack against Neural Networks. https://arxiv.org/pdf/1912.02316.pdf
[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
[4]: Mary et al., Towards Deep Learning Models Resistant to Adversarial Attacks. https://arxiv.org/abs/1706.06083
[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
[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
[7]: Tashiro et al., Diversity Can Be Transferred: Output Diversification for White- and Black-box Attacks. NeurIPS 2020.
```
summary_of_the_review: The reviewer cannot recommend acceptance because this paper is lacking in novelty and empirical evaluation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: Strengths:

(I) The paper proposes an approach for optimizing the patch location/dimension (while prior works usually fix the patch location/dimension for simplicity).

(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).

Weaknesses:

(I) The paper does not provide enough motivation and justification for its problem setup. It might be trivial to succeed in this attack 
1. 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.

2. 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).

3. 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.

4. 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.

(II) The proposed method lacks novelty

1. 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.

2. The problem of imperceptible patches is not new [4,5].

3. The loss for the attack is from existing work (C&W attack).

4. 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.

(III) The experiment lacks a reasonable baseline comparison and a comprehensive ablation study. 

1. 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. 

2. 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.

3. 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.

4. 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). 

(IV) Finally, though it is minor, the mathematical presentation can be improved. Here is an incomplete list of notation issues that I noticed:

1. $m$ is used multiple times (as the mask and also the number of patch candidates)
2. $\lambda$ is used multiple times (in the formulation of adversarial programs, and in C&W attack as the balancing weight)
3. In “adversarial programs”, there is an inconsistency between $I_{\alpha,\beta,p}$ and $I_{\alpha,\beta,m}$.

[1] Laidlaw et al., “Functional Adversarial Attacks”, NeurIPS 2019.

[2] Sharif et al., “Accessorize to a Crime: Real and Stealthy Attacks on State-of-the-Art Face Recognition”, CCS 2016.

[3] Rao et al., “Adversarial Training against Location-Optimized Adversarial Patches”, ECCV  workshop 2020.

[4] Liu et al., “Perceptualsensitive GAN for generating adversarial patches”, AAAI 2019.

[5] Bai et al., “Inconspicuous adversarial patches for fooling image recognition systems on mobile devices”.

summary_of_the_review: Based on the three issues listed below, I would recommend rejecting this paper.

1. 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.

2. 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).

3. 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).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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. 
In general, I like the evaluations shown in figure 2-figure 5, these results indicate the proposed method is effective.

summary_of_the_review: However, I have 2 minor concerns:
1. 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?
2. 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?
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

1. 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.

2. 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?

3. 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?

4. 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_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.
review_title: null

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