Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a new adversarial attack algorithm for finding the smallest perturbation necessary to fool a classifier under various $\ell_p$ norms. The algorithm is similar to DDN, but includes a few improvements, including using the logit margin loss instead of cross-entropy, using a more complex algorithm for updating the bound $\epsilon$, and not always projecting the adversarial example to the boundary. They evaluate the new attack, FMN, on a variety of classifiers on MNIST and CIFAR-10.

main_review: First, I would like to commend the authors on the clear presentation and extensive experiments in the paper. I found the paper easy to read, with the algorithm and experiments clearly organized and explained. The separation of the sample-level and dataset-level hyperparameter tuning was helpful to compare typical attack use (dataset-level tuning) and best-case performance. The authors were also clear about the relationship with prior work.

The novelty of FMN is somewhat limited, since it is quite similar to DDN. Accordingly, the results for FMN are quite similar to DDN, although they seem to generally improve on it slightly. The applicability of FMN to the $\ell_0$ and $\ell_1$ norms is useful. Since the differences between FMN and DDN are heuristics and the results empirical, it would improve the paper if an ablation study were done to show which changes between DDN and FMN actually lead to the improved performance of FMN. This could lead to more general insights about how to improve adversarial attacks.

Overall, while the paper is well-presented, the results are somewhat marginal and it is not clear which changes in FMN lead to the improved performance over DDN.

Potential typos/grammatical issues:
 * Line 72: should "and" be "added"?
 * Line 86: "being *q*" should be "*q* being"
 * Line 298: "much" should be "many"
limitations_and_societal_impact: Limitations and societal impact were adequately addressed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes a new adversarial attack called Fast Minimum Norm (FMN) attack. FNM retains the major advantages of DDN (Decoupled direction and norm attack) [1]. While DDN is specific to the l_{2} norm and cannot be easily extended to other norms, the authors show that FMN can be directly extended to other norms such as l_{0}, l_{1} and l_{\infty} norms. 

The authors conduct experiments using many different models and datasets and FMN outperforms previous attacks in terms of convergence speed. The minima found are either comparable or better across almost all tested scenarios. 

I agree with the author's assessment that it can be a very useful tool for adversarial robustness evaluation.

[1] J. Rony, L. G. Hafemann, L. S. Oliveira, I. B. Ayed, R. Sabourin, and E. Granger. Decoupling direction and norm for efficient gradient-based l2 adversarial attacks and defenses.
main_review: The authors propose a new adversarial attack called FMN which keeps the advantages of the previously proposed DDN, while also allowing threat models with norms other than l_{2}. 

This paper is clearly written and easy to understand.

Pros:

1. The experimental setup uses multiple different models and datasets (MNIST, CIFAR-10 and Imagenet). The evaluation is very comprehensive. 

2. FMN has the additional advantage that it does not require the starting point of the optimization to be an adversarial example. 

3. The proposed attack achieves smaller (or comparable) perturbation sizes with lesser computation time when compared to the existing state-of-the-art methods. It can be a very useful tool when carrying out robustness evaluations.

4. The proposed attack works well under different l_{p} norm threat models. Results are significantly better than the previous state of the art for the l_{0} and l_{1} threat models. 

Cons:

1. The authors should clarify why they use the median as a measure of robustness instead of the widely used mean. But I did not let this negatively affect my review because median has been used in a previous NeurIPS publication [1]. 

Overall, I believe it is a solid contribution and recommend acceptance. 


[1] W. Brendel, J. Rauber, M. Kümmerer, I. Ustyuzhaninov, and M. Bethge. Accurate, reliable and fast robustness evaluation. In Advances in Neural Information Processing Systems, pages 12861–12871, 2019.

limitations_and_societal_impact: Since the paper proposes a new adversarial attack that can be used to comprehensively test robustness of a neural network against many different threat models, I do not foresee any potential negative societal consequences of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an adversarial attack (FMN) that generates minimum-norm adversarial examples. The attack builds on the DDN attack but generalizes to $l_p$ norms beyond the $l_2$ norm that the DDN attack is specialized for.

- For the $l_0$, $l_1$ and $l_\infty$ norms, the attack has better performance: it has a consistently lower execution time per query, is more query efficient, and results in adversarial examples of comparable or smaller norm compared to the state-of-the-art.
- For the $l_2$ norm, the attack has comparable performance to the DDN attack: it has a slightly higher execution time per query, has comparable query efficiency, and results in adversarial examples of comparable norm compared to the state of the art (DDN).

In addition to the advantages in execution time and query efficiency, the method does not require adversarial starting points as some other methods do.
main_review: # Review Summary

## Strengths

- The paper has conducted a very thorough evaluation comparing the proposed attack to other attacks that are the state-of-the-art.
- The faster execution time for FMN means that it will be a useful tool for practitioners trying to estimate the minimum-norm attack on a classifier for a particular clean example.

## Areas of Improvement

- The experimental data provided does not substantiate the claim that FMN is more robust to the choice of hyperparameter.
  - The fact that FMN performs better when hyper-parameters are tuned at the dataset-level could simply mean that the best hyperparameter is the same across most of the samples (allowing, for example, the same hyperparameters to be applied to a test sample once hyperparameter tuning has been carried out on the training set), but does not mean that changing the hyperparameters at the dataset-level would not have a significant impact on attack performance.
  - Furthermore, for the $l_2$ and $l_\infty$ norms, the best alternative method (DDN and BB respectively) see a similar degradation in attack performance to FMN when comparing the sample-level and dataset-level hyperparameter tuning.
- As detailed in the section on originality, it is not clear what changes to the DDN algorithm enable FMN to generalize to norms other than $l_2$.
- As detailed in the section on clarity, this paper has some statements that are not supported by either references or any of the results presented, and would be greatly improved by clarifying these statements. One that I would like to highlight in particular is the claim in the abstract that "FMN significantly outperforms existing attacks in terms of convergence speed and computation time"; this is not borne out in the data for the $l_2$ norm. (The success of FMN on other norms is still valuable, and I'd rather this paper not overstate its contribution.)

---

# Originality

The presented FMN attack appears similar to the DDN attack [25] in many respects, such as the choice of how to decrease / increase $\epsilon$ and the projection and clipping step at the end of the for loop.

While there are differences in details that make for a substantially different algorithm (as identified at the end of Section 2), it would be helpful to understand which of the differences (if any) contribute to the performance improvement (e.g. via an ablation study). This is particularly important since DDN and FMN perform basically on par with each other on the $l_2$ examples shown. In addition, this paper claims in Line 44 that DDN "is specific to the $l_2$ norm and cannot be readily extended to other norms" --- is the issue that it is not possible to project $\delta_k$ onto an $\epsilon-k$ sphere in the appropriate norm, or is it simply that this leads to poor performance (perhaps this is what Lines 124-126)?

# Quality

This work presents thorough experimental results comparing FMN against state-of-the-art attacks, comparing the strength of the attacks as well as their runtime.

# Clarity

## Unsupported Statements

This work has some statements that are not supported by either references or any of the results presented. These statements should be clarified to avoid confusing readers with unsupported assertions, and ensure that the contributions of the paper can be clearly understood.

- Line 20: "all attacks make certain assumptions about the underlying geometry and properties of the optimization problem" -> Is there a reference to support this assertion? What assumptions are made about the geometry?
- Line 26: "most (attacks) ... are just small variations of the same technique, make similar underlying assumptions and thus tend to fail jointly" -> Is there a reference to support this assertion? In particular, which sets of attacks tend to fail jointly, and which are distinct?
- Line 39: "These attacks (like BB or FAB) ... may require an adversarial starting point" -> Do some of these attacks require an adversarial starting point, or do all of them require one sometimes?
- Line 50: "while finding equal or better optima" -> this phrasing suggests that FMN finds a successful adversarial attack of smaller norm on a per-sample basis (which _may_ be true; my objection is merely that the presented results do not demonstrate this); this paper should either show results to prove this, or emphasize that the claim is that the _average_ minimum norm found by FMN is smaller.
- Line 131: "initializing the attack from an adversarial point, which can greatly increase the convergence speed of the algorithm" -> while this may be true for other attacks (and makes intuitive sense), I could not find evidence in the paper to support the assertion that initializing attacks from an adversarial point increases convergence speed - much less "greatly".
- Line 160 + Footnote 1:
  - The footnote explains that FAB is not evaluated in the targeted case because it "implements a substantially different attack", but does not elaborate on why making a comparison to this different attack is not appropriate. It seems like the issue that this paper is alluding to is that the "targeted" FAB attack is actually a method to accelerate finding an untargeted adversarial example, and does not guarantee (despite the name) that the resulting adversarial example will be labelled as belonging to the target category by the classifier. If so, it would be very helpful to make this clear; a short explanation like "FAB does not support generating adversarial examples with a particular target label" should suffice.
- Line 234: "The reason may be that these robust models exhibit noisy gradients and flat regions around the clean input samples" -> M2, M3, M4 and C1, C2, C3 are all robust models - is there any evidence to suggest that some of them have noisier gradients / flatter regions around the clean input samples than others?

## Miscellaneous Issues

- Line 1: "Evaluating adversarial robustness amounts to finding the minimum perturbation needed to have an input sample misclassified" -> not necessarily; the robustness of defended models is often reported against attacks with a fixed budget; determining whether or not such an attack exists can be computationally less expensive than finding the minimum perturbation.
- Algorithm 1, Line 6: The variable $q$ is referenced here without being introduced (it is first introduced in Line 86)
- Algorithm 1, Line 14: normalizes $g$ by its $l_2$ norm, similar to DDN --- is this meant to be the $l_q$ norm or is it intended?
- Figure 2: It would be helpful to label which figures correspond to the M2 and C1 model.

## Suggestions

- Table 3: I'm finding it challenging to interpret the results presented in Table 3 as it relates to the efficiency of each attack. If the final perturbation size $\epsilon$ at Q=1000 is the same, then an attack with a smaller number of queries required to reach a perturbation size $\epsilon'$ within 10% of $d$ would be superior - but Table 1 shows that there _is_ significant variation in the value at Q=1000 itself. If Attack 1 makes slow but steady progress to a significantly smaller perturbation size at Q=1000, while Attack 2 makes quick progress, but plateauing at a larger perturbation size, most practitioners would probably prefer to select Attack 1. Personally, I find that the query-distortion curves already encapsulate this information well; if data in tabular form is still preferred, perhaps presenting the number of queries required by each attack to reach a perturbation size within 10% of _the best known value across all attacks_ would be better.
- While I appreciated the detailed experiments provided, providing all of the data in tabular form in the main body of the paper made it harder for me to understand. (I understand that a previous reviewer may have asked for all of the data). Summarizing the data (for example showing the ratio of average execution time of other attacks to that of FMN in a scatter plot) would make it easier for a reader to grasp the information.

# Additional Questions

- When an adversarial example has been previously found, it seems like the $\epsilon$-increase amount is selected such that the algorithm could test an $\epsilon$ value that is larger than the best known adversarial example. (In particular, we could have $\epsilon_{k+1} = \epsilon_{k-1}(1-\gamma_k)(1+\gamma_{k+1}) \leq \epsilon_{k-1}(1-\gamma_k)(1+\gamma_k) = \epsilon_{k-1}(1-\gamma_k^2) < \epsilon_{k-1}$, so we would have another $\epsilon$-increase if the true minimum value of $\epsilon$ is between $\epsilon_{k-1}(1-\gamma_k^2)$ and $\epsilon_{k-1}$.) This seems like it would waste queries; I am curious why a binary-search approach is not used instead.

---

# Updated Review

I am updating the score for this submission (6 -> 7) as the authors have effectively addressed my concerns (both in the "areas for improvement" and in "clarity") which were affecting my overall evaluation. Please see the commen thread below for specifics.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This papers present new white-box minimum-norm adversarial attacks adapted to the case of the $\ell_p$ balls for $p=0,1,2,\infty$. It extends the DDN attacks which only considered $\ell_2$ norms.
main_review: The experimental part is caried with much care and the paper is very well written and interesting to read. The main contribution of the paper is to extend a known technique that deal with $\ell_2$ constraints to deal with $\ell_p$ (for $p=0,1,2,\infty$). This contribution seems however not sufficiently original and motivated for such a conference as NeurIPS. I also found some unclear statements that I will now details.

- Extension to other norms. The main contribution of this paper is to extend a known technique DNN dealing with $\ell_2$ constraints to adversarial attacks that can deal with $\ell_p$ for $p=0,1,2,\infty$. Yet, it is not sufficiently motivated:
1) The motivation for using different norms is not sufficiently pointed out. 
2) Among the chosen norms, why choosing only the $\ell_p$ for $p=0,1,2,\infty$? There are several papers considering other norms as a way to "having an arsenal of diverse attacks that can be adapted to specifics defense [...]", see, e.g., Wasserstein balls [W2019] or group-lasso [Xu2018].
3) Can your algorithm adapt to other norms? If so, what are the experimental performances?
4) Looking only at $\ell_p$ type of neighborhood is very reminiscent of one of the claims of the authors that "most of them [adversarial attacks] are just small variations of the same technique, make similar assumptions [...]". Indeed, we can, for instance, understand this choice of the $\ell_p$ norms for a measure of perturbation as such a similar assumption shared by most of works.


- Line 25-27 "While it may seem that the number of attacks is already large, most of them are just small variations of the same technique, make similar underlying assumptions and thus tend to fail jointly".
This sentence is much too vague and unprecise:
1) Can you defend this negative statement with a better explanation or references? 
2) What type of "similar underlying assumptions" are you referring to? 
3) Your sentence might be understood as a claim of a causal link between the failure of the methods and the fact that they make the same underlying assumptions. Can you write more explicitly that this is an observation rather than an established causal link? Or if not provide refs, explanations or numerical evidences?
4) To what same technique are you referring? 
5) "Most of them" is an unprecised claim.


Some minor comments:
- Title: the title misleading let the reader believe that there is a great generality in the variety of different norms the paper deal with while it focuses only on the $\ell_p$ with $p=0,1,2,\infty$. So, could you either modify the title or explicit in the paper that your method is versatile to any norms?

- Line 96 "decayed with cosine annealing": It would be nice to add a reference.

- Line 127 FMN does not use the cross-entropy loss but rather the logit difference as the loss function $L$". Can you explain the rationale behind this difference with DNN?

[Xu 2018] Kaidi Xu, Sijia Liu, Pu Zhao, Pin-Yu Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmus, Yanzhi Wang, and
Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability

[W2019] Eric Wong, Frank R Schmidt, and J Zico Kolter. Wasserstein adversarial examples via projected sinkhorn
iterations.

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper proposes a fast minimum-norm (FMN) attack that works with different norm perturbation models and is robust to hyper-parameter choices. Some reviewers had concerns regarding the novelty of the work with respect to prior works (e.g. DDN). Authors clarified some of these concerns in the discussion period. Overall I think the paper makes good contributions. I suggest authors to take reviewers' suggestions into account in the final draft of their work.  
Decision: Accept (Poster)