Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes the use of an evolutionary algorithm to construct decision-based black-box adversarial examples with L0 or sparsity constraints against image classifiers such as CNNs and Image Transformers. The algorithm uses an L2 distance constraint to check the fitness of a solution, and employs several tricks such as differential recombination and mutation to improve the quality of the solution. The experimental results demonstrate that the attack is more effective than the current SOTA sparse attacks, and is almost as effective as white-box attacks given enough queries.
main_review: ***Strengths***
- The paper is largely clear and well-written.
- The experimental results are solid, and experiments are carried out on vision datasets and models of interest.
- The attack is both sparse and effective.
***Weaknesses***
- The main issue with this paper is the lack of an intuitive explanation as to why this attack is better at finding sparse and effective adversarial examples than previous work. I would have liked to see a more detailed algorithmic comparison with previous work.

summary_of_the_review: Overall this is a solid paper that makes a reasonable contribution to a problem of some interest to the community.

+++++++++++++++++++++++++++++++++
Having read the rebuttal, I retain my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a novel sparse attack method called SparseEvo. Based on evolution algorithm, the SparseEvo searchs a sparse adversarial perturbation in limited query budget. It can significantly reduce the queries compared with the SOTA method, i.e., Pointwise. The paper also conduct the first vulnerability evaluation of a ViT on ImageNet in a decision-based and $l_0$ norm constrained setting.
main_review: - The proposed methods are well-motivated and novel. The paper is easy to follow for an adequately prepared reader. Prior work is sufficiently discussed.
- The experiments are convincing and the experiment results show the effectiveness of the proposed attack.
- The amount of detail is good, it seems sufficient to reproduce results.
summary_of_the_review: Overall, I think this paper is a good one.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a black-box decision-based spare attack based on the evolution algorithm (called SparseEvo).  The authors test their method on two types of classification models and two popular vision datasets: ResNet (CIFAR10 and ImageNet) and Vision Transformer (ImageNet).  Through the comparison with Pointwise attack (for efficiency and sparsity) and PGD0 (for success rate), SparseEvo achieves good performance in both success rate and efficiency.
main_review: Pros:

1. The experimental performance is really good in terms of it being a decision-based sparse attack. 
2. Using the L2/L1 distance as the fitness function and using an evolution algorithm instead of some estimated gradients to generate adversarial examples is novel.

Cons:

1. The comparison with the pointwise attack in the targeted attack experiments is somehow unfair. SparseEvo relies on a random target image to generate the adversary while the pointwise attack doesn't. It would be better to find a way to let the pointwise attack leverage the target image or adapt another black-box attack for doing the sparse attacks.
2. I am wondering what's the image size used in the ImageNet experiments? Since you only reduce the search space by a factor of the # channels (typically 3). So I am wondering how the scalability of SparseEvo is against the big images.
summary_of_the_review: This paper proposes a novel black-box decision-based space adversarial attack method based on the evolution algorithm. The basic idea is to use the L2/L1 distance with the original image as the fitness function to adjust the current images towards the target images. The experimental results are good. I am only concerned a little bit about the comparison in the targeted attack since it is somehow unfair (see in the Main Review).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an evolution-based algorithm to conduct a sparse attack against convolutional deep neural networks and vision transformers. The evaluation results show that the proposed method requires fewer model queries than the state-of-the-art sparse attack Pointwise for both untargeted and targeted attacks.
main_review: Strengths:
The paper shows promising experimental results for the method. As a paper proposing a blackbox method, it also shows comparison with a white-box attack to showcase its superiority (my concerns are described in the weakness part below).

Weaknesses:
1. The experiment section can be more comprehensive. The submission only compares with one paper on decision-based sparse attack, and that work only shows experiments on MNIST dataset, not ImageNet. (a) The comparison on ImageNet shown in this submission is not fair (the PointWise method sparsity is always 1, which means it basically fails to create any sparsity): if the comparison were to be made, the submission can instead make some minimal adjustments to the baseline method to make it not completely useless. (b) There are many other decision-based attacks on ImageNet. Although most of them are showing results in L-2 metrics (e.g., BA, HSJA, QEBA, NLBA, PSBA, SignOPT, etc.) and some of them show L-\infty metrics (e.g., RayS), many of them can be easily adapted to L-0 case with projections based on my experience. The submission can try to compare with these stronger baselines on ImageNet to showcase its method performance.
2. The paper can discuss its relationship/difference with the existing literature more clearly. For example, using evolutionary methods for decision-based attacks is not an invention by this submission: the paper “Efficient Decision-based Black-box Adversarial Attacks on Face Recognition” has proposed one in 2019. Also, as mentioned above, though many existing decision-based attack papers did not show results on L-0 metrics, they can be adapted easily, thus very related with this paper. The paper should consider a more detailed discussion on its related works and justify its novelty in terms of the proposed method.

Questions: 
On the second plot in Figure 6, for the two solid curves, the red curve (SpaEvo (ViT)) even goes lower than the black curve (PGDl0 (ViT)) both at the beginning and the end. Is there an explanation for this observation? Are you using different images for different curves so that the white-box attack PGD is not the upper bound of the attack performance in this plot? Or is the PGD not optimized properly? The “Untargeted-ImageNet” plot in Figure 5(b) is also weird in a similar sense.

summary_of_the_review: The paper shows good experimental results, but there are some concerns about the experimental part (whether it's fair and valid). Also, the novelty of the method and the relationship with the literature are not discussed in detail.
review_title: null

Meta-review: This paper introduces a technique to generate L0 adversarial examples in
a black-box manner. The reviews are largely positive, with the reviewers
especially commenting on the paper being well written and clearly explaining
the method. The main drawbacks raised by the reviewers is that the method
is not clearly compared to some prior work, but in the rebuttal the authors
provide many of these numbers. On the whole this is a useful and interesting
attack that would be worth accepting.
Decision: Accept (Poster)