Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a black-box attack where, by relying on segmentation priors, the perturbation is applied only in the salient region. This allows one to obtain reduce perceptibility with a limited number of queries and a small reduction in success rate. More specifically, once the salient region has been identified, a refining procedure is carried out to find small areas where the perturbation should be added. Experiments are performed on ImageNet and results are compared with those of some SOTA methods and their variants that work on saliency regions.
main_review: This work tackles an important problem, that is, developing an imperceptible black-box attack. However, there are two main issues concerning the technical approach and the experimental analysis.  

- From a technical point of view the search algorithm devised to refine perturbation is exceedingly naive. It is based on an iterative procedure that resembles quadtree analysis in image processing. The first split of the salient region generates four initial blocks, and a perturbation is added to them to find those that maximize the loss function. After finding the best block, it is further split and the procedure is repeated until the block is reduced to one pixel or no smaller blocks can achieve a better loss. Then, this same procedure is applied again to the second best block, etc. As it is described, this procedure has neither a theoretical nor an experimental justification. In addition, a similar idea but applied in a different context can be found in Guo et al. (2020) and saliency maps to add adversarial attacks are also explored in Sun et al. (2021). Overall, I feel that the contribution is not significant in terms of technical approach.

- The approach is not compared with other black-box attacks that also have the objective to make the perturbation imperceptible, see references below. In fact, experiments are carried out by modifying some SOTA approaches by including saliency regions and comparing them with the proposed solution (see Table 2). In my opinion this is too limited to validate the proposal. 

Typos: imperceptiblity, tunning

References
- Guo et al. Watch out! Motion is Blurring the Vision of Your Deep Neural Networks, NeurIPS 2020
- Sun et al. Generating facial expression adversarial examples based on saliency map, Image and Vision Computing 2021
- Wang et al. Perception Improvement for Free: Exploring Imperceptible Black-box Adversarial Attacks on Image Classification, arXiv 2020
- Liu et al. GreedyFool: Multi-Factor Imperceptibility and Its Application to Designing Black-box Adversarial Example Attacks, arXiv 2020
- Croce and Hein, Sparse and Imperceivable Adversarial Attacks, ICCV 2019
- Gragnaniello et al. Perceptual quality-preserving black-box attack against deep learning image classifiers, Pattern Recognition Letters 2021
- Li and Chen, Toward Visual Distortion in Black-Box Attacks, IEEE Transactions on Image Processing 2021


=========== Post rebuttal comments ===========

I appreciate that the authors better clarified their contribution and included a new comparison in the experimental section, hence I increase my score. However, I still believe that the paper needs much more comparisons with state-of-the-art and that the proposal should be better justified from a theoretical point of view. 
summary_of_the_review: In my opinion the technical novelty introduced in this paper is too limited and also its experimental validation should be improved by considering more relevant methods for comparison.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies how to reduce the perceptibility of the perturbations to the original images produced by black-box adversarial attacks (for the $\ell_\infty$-threat model). In particular, it proposes to use a prior based on segmentation techniques to localize the changes on the subject of the image and leave the background unaltered. Moreover, the Saliency Attack is introduced to further reduce the fraction of the original image which is modified to induce misclassification.
main_review: Strengths
- The proposed method is simple and achieves the goal of improving the imperceptibility of the perturbations: using the segmentation prior is effective for avoiding changes on the background, and the Saliency Attack attains better MAD score.

- Several ablation studies are presented to illustrate the proposed method.

Weaknesses
- The paper focuses on improving the imperceptibility of $\ell_\infty$-attacks with a fixed budget $\epsilon=0.05$, in practice reducing the number of pixels perturbed (a sort of minimization of the $\ell_0$-norm). However, I think that how visible the perturbations are is more a property of the threat model (set of feasible changes) rather than of the attack used: for example, using a smaller $\epsilon$ for the same attacks would increase their imperceptibility. Moreover, other $\ell_p$-norms (e.g. Square Attack has versions for $\ell_2$ and $\ell_1$ [A]), including $\ell_0$, or perceptual metrics like LPIPS [B] should be considered, since they produce more localized changes than $\ell_\infty$-attacks.

- There are a few works which aim at finding which areas of an image the attacker should perturb to have invisible changes, both with black- and white-box attacks [C, D]. In particular, [C] show that small perturbations in the $\ell_\infty$-norm are not necessary if limited to certain areas to the image to preserve imperceptibility.

- The presentation of the method in Algorithms 1 and 2 seems a bit confuse: first, $\delta$ is not defined. Second, the "Refine" function is called recursively on smaller blocks, but also repeatedly with smaller $k$ in Algorithm 2: is this correct? Also, in Line 9 $k$ is halved: shouldn't it be restarted from the original value when going over the next iteration of the loop in L4?

- From the images in Figure 4 it seems that for Parsimonious and Square Attack perturbations are sampled also on areas which are outside the mask given by the segmentation prior: are those candidates evaluated, spending queries of the total budget (although they can't change the current perturbations)?

[A] https://arxiv.org/abs/2103.01208
[B] https://arxiv.org/abs/2006.12655
[C] https://arxiv.org/abs/1909.05040
[D] https://arxiv.org/abs/2010.13773
summary_of_the_review: Overall, I think the proposed method is effective, but, especially given that the technical novelty is limited, it should be better positioned: if the main goal is imperceptibility of the perturbations it should be compared to other kinds of attacks beyond $\ell_\infty$ ones. Otherwise, the authors should better motivate why improving the $\ell_\infty$-attacks with such fixed threshold is relevant.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: There has been a lot of interest in improving the query efficiency of black-box attacks in the recent past. However, these techniques produce examples that a human in the loop can quickly identify. The authors propose using segmentation priors to improve the black-box attacks so that the perturbations are restricted to the salient regions of the image. In addition to this, they also present a technique that improves the imperceptibility without forgoing the query efficiency.
main_review: The paper proposes a few optimisations that can improve the imperceptibility of generated adversarial perturbations. They also demonstrate that some of the exiting black-box adversarial attacks can benefit from their optimisations. In addition to this, they also propose a search algorithm that can further narrow down the candidate regions for adversarial perturbations. They also demonstrate that adversarial examples generated by their technique have a higher success rate for evading detection mechanisms.
 
In the recent past, a richer class of gradient-free black-box techniques have been proposed in the literature. Why is the paper considering only two of those? For instance, why not consider techniques based on Bayesian optimisation. The same applies to methods for detecting adversarial examples. Why was Feature Squeezing chosen as a baseline to evaluate the success rate?

In addition to the above, the author(s) report the results only over a sample of 1000 images from ImageNet, why only such a small sample was considered, and I would also encourage the authors to evaluate over multiple samples & report the variance too.
summary_of_the_review: In general, I found the paper easy to follow. I also find the direction explored by the paper to be quite promising but found the experiments & the baselines chosen by the authors are lacking. I would encourage the authors to include a diverse set of baselines. For instance, I would also demonstrate how the optimization proposed in the paper improves gradient-free black-box adversarial example generation techniques other than the chosen few. Also, evaluate the evasion rate of adversarial examples generated by the proposed technique against a diverse set of detection mechanisms.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a method to generate imperceptible attack in black box attack scenario by generating local perturbation blocks in salient regions. It used salient object segmentation to obtain the salient region, then applied a tree search method to find smallest blocks within the salient region that can cause the maximal change in predicted class logits. Experiments on 1000 Imagenet examples are conducted, compared to several existing baselines, showing that the proposed method can improve achieve more imperceptible attacks (where imperceptibility is measured by metric MAD).
main_review: The topic of imperceptible black box is very interesting and not well studied, the ideas of generating perturbing blocks in salient regions are interesting, however, this paper can be improved with more sufficient justifications on motivations and experiments. Moreover, its technical contribution is not very high.

The motivation of generating the perturbed regions in the salient object region is not sufficiently justified: salient object can still be mostly a
smooth low frequency area, e.g., smooth human face/skin, and hence generating the perturbation in this area may not be reasonable. Moreover, it is not clear whether generating perturbation in salient object area makes more sense than generating perturbations in the non-smoothness, high frequency, or  heavy texture area. 

The experiment part is not totally convincing. 1) There is only one data set, which is 1000 images from ImageNet. However, what these images look like will affect the results a lot. For example, does most salient objects have heavy texture area? 2) Also, there is no comparison to the related method in approach of Zhang (2020). 3) I can not find the information of which classification network is used in the experiments. Are multiple networks used in the experiments?

This paper used an existing salient object segmentation approach, and so its major technical contribution is the tree based method to generate perturbation blocks, which is however a little straightforward and ad-hoc.
summary_of_the_review: Overall, I liked the idea of this paper, and enjoyed reading it. However, it needs better justification on motivations, as well as improvement on experiments.
review_title: null

Meta-review: In this paper, the authors propose to use segmentation priors for black-box attacks such that the perturbations are limited in the salient region. They also find that state-of-the-art black-box attacks equipped with segmentation priors can achieve much better imperceptibility performance with little reduction in query efficiency and success rate. Hence, the auithors propose the Saliency Attack, a new gradient-free black-box attack, that can further improve the imperceptibility by refining perturbations in the salient region.
The reviewers think that the proposed method is simple and important, and the authors have responded properly to some comments. 
However, the reviewers still are not satisfied with the experimental evaluation and comparisons, as the authors can only try to compare with other ideas and test more models in the future.
In summary, I think the manuscript at its current staus cannot be accepted.
Decision: Reject