Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposed a method to trace the strong adversarial attacks (specifically PGD). The insight is PGD attack is likely to leave a trace and trigger the local linearity of the network. They then introduced the ARC to capture the SAE, resulting in a detector that can identify the informed attacks and uninformed attacks. Experiments including ImageNet showed the effectiveness.
strengths_and_weaknesses: 
Strength:
1. It studies very extremely limited settings for the defender, which is novel and interesting. 
2. The paper presents a host of visualization to support the intuitions and conclusions. 

Comment:
1. My major concern is that ARC is not effective under a lot of scenarios (including FGSM, small $\epsilon$, and transfer-based attacks ). It is also possible for PGD attacks to bypass the detector by reducing the number of steps. It cannot work with a robust model (adv training). I am not sure if ARC is a valid trace method. 

After rebuttal, I am willing to improve the score to 5, but my concern about the method still exists. 
questions: NA
limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new and interesting method to detect PGD-like adversarial perturbations. The insight is to leverage the fact that PGD-like adversarial attacks will trigger local linearity of the input sample. To quantitatively measure the local linearity, the authors propose to use the Sequel Attack Effect (SAE) to continue the attack with BIM and then measure linearity with Adversarial Response Characteristics (ARC). SVM-based models are then trained and used for the detection of informed/uninformed attack detections.
strengths_and_weaknesses: Strength
- The proposed method is very interesting and novel, providing great contributions to understanding and detecting PGD-like adversarial attacks and defense.
- The investigated topic is important and useful.
- Extensive empirical results on CIFAR-10 and ImageNet well illustrate the effectiveness of the proposed method and support the claims.
- The paper is well-written and easy to follow. Provided figures clearly show the insights of the method.

Weakness
- The method is only limited to PGD-like adversarial perturbations, unable to other popular attacks like C&W as discussed in the paper.
- The importance of limited training data for adversarial detection should be better motivated in introduction.
questions: - I understand the main contribution here is for detection with limited amount of training data. I wonder how well the performance of the proposed method would be given sufficient training data compared to other SOTA detection methods?
- A minor question: why use T=48 in line 100? It would be better to give a brief explanation for special numbers.
limitations: Limitations and societal impact are comprehensively discussed in the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a detection defense against adversarial examples generated by untargeted PGD-like attacks. This defense relies on the assumption that such adversarial examples trigger distinguishable patterns of linearity along a local trace defined by the BIM attack, which maximizes the cross-entropy loss that regards the least-likely label as the ground truth. The linearity pattern is characterized by the ARC feature, a vector reduced from the jacobian matrices along the BIM trace. Extensive qualitative and quantitive results on CIFAR10 and ImageNet (ResNet and SwinT) demonstrate the distinguishability of the ARC feature over benign inputs and adversarial examples generated by PGD-like attacks. This characterization is then used to detect PGD-like attacks and infer their parameters. The overall defense is effective against non-adaptive (unaware of the defense) PGD-like attacks, and outperforms another detection defense that does not require too much data to collect statistics. Finally, some interesting observations are discussed, such as linearity enforced by adversarial training.
strengths_and_weaknesses: Before heading to the detailed comments, I would like to note *neutrally* that the proposed defense is similar in spirit to some previous detection defenses that rely on the adversarial example's higher robustness against benign noise [1] and adversarial perturbation [2], which were later broken by [3]. *This similarity leads to both pros and cons, detailed below.*

[1] The Odds are Odd: A Statistical Test for Detecting Adversarial Examples. Roth et al. ICML 2019.

[2] A New Defense Against Adversarial Images: Turning a Weakness into a Strength. Hu et al. NeurIPS 2019.

[3] On Adaptive Attacks to Adversarial Example Defenses. Tramèr et al. NeurIPS 2020.

### Originality

**Strengths (major)**
* The proposed characterization of adversarial examples is novel and only requires a tiny set of training data, which seems to be less discussed in the literature.
* The proposed ARC feature is novel and explicitly characterizes a well-defined property (local linearity) of adversarial examples. I believe this is more sophisticated than previously explored properties such as robustness to benign noise [1] and adversarial perturbation [2].
* The idea of using BIM attacks to characterize the trace of untargeted PGD-like attacks is insightful. The proposed defense can detect perturbed-but-unsuccessful inputs, which seemed not to be covered by previous defenses [1, 2].

**Weaknesses (minor)**
* **Discuss similar defenses.** It is suggested to discuss [1, 2] and potentially other similar defenses with more details on the underlying properties. For example, how the property explored in this work is different and superior to those explored by previous defenses.
* **Discuss local linearity.** Since this work relies on the local linearity of adversarial examples, it is suggested to include more discussion about newer work in this direction to solidify the underlying assumption.

### Quality

**Strengths (major)**
* The proposed characterization of adversarial examples is technically sound and well supported by experimental results on CIFAR-10 (ResNet) and ImageNet (ResNet and SwinT). It can effectively distinguish between benign inputs and adversarial examples generated by PGD-like attacks with different parameters.
* The ablation study demonstrates the defense's non-sensitivity to non-PGD-like attacks, but the pros and cons are adequately justified.

**Weaknesses (major)**

* **Some assumptions are too strong.** This paper made some strong assumptions that may not always hold. For example, at L81 the authors assume that the input's ground-truth label is simply the least-likely one. While this is likely to hold for vanilla attacks, a slightly smarter attacker could simply make the ground-truth label anywhere between the most-likely and least-likely label to break this assumption. It is unclear how the original characterization performs in this case. For example, is it possible that the linearity goes down at the first few steps (given an incorrect guess of ground truth) before heading up in those cases?

* **The proposed defense may not be lightweight**. Since the proposed defense requires several steps of BIM attacks at the inference stage to obtain the input's ARC feature, the defended model's inference of each input would now include overheads (both efficiency and memory) of several backward passes. While other defenses require auxiliary models (thus argued as not lightweight in this paper), those defenses do not involve backward passes and thus may be more efficient than the proposed defense. This weakness is partially supported by the authors' inability to evaluate all ImageNet data. It is suggested to include some empirical results to resolve or clarify this weakness.

* **Insufficient discussion of adversarial robustness.** Since this paper claims to propose a defense against adversarial examples, I find it hard to be convinced that the proposed defense would come with much robustness against adaptive attacks. I understand that the authors have discussed the hardness of adaptive attacks to some extent and left them for future study (L123-134), but the current discussion is rather limited, even from the perspective of *published* adaptive attacks on similar defenses. *I am outlining my comments below but will be open on this point if the meta-reviewer deemed the following discussion as beyond the scope or outweighed by the strengths of the proposed characterization approach (in a non-adversarial setting).*
  * At L123-134, the authors discussed an adaptive attack that is computationally prohibitive on ImageNet. However, it is unclear if the same claim holds for the smaller CIFAR-10, which is also a dataset evaluated in this paper. **Please discuss the computational cost of this adaptive attack on CIFAR-10 and if it is still prohibitive.**
  * If I understand correctly, the adaptive attack must reach a point whose BIM-trace is equally non-linear (or has the same linearity pattern) as that of a benign input. **However, the current defense cannot prevent the existence of such points, so it is still possible to find them.** This is similar to previously broken defenses that expect adversarial inputs to have unique patterns in terms of robustness to benign noise [1] and adversarial perturbation [2]. Therefore, I believe discussing their *existing* adaptive attacks from [3] would significantly strengthen this paper. In particular, it is suggested to discuss the following two *published* adaptive attacks.
    * Logit matching (Section 5.2 of [3]). If the PGD attacker now aims to reach a point whose logit is sufficiently close to an unperturbed image from a different class, can the proposed characterization still distinguish between benign inputs and such adversarial examples?
    * Interpolation between the adversarial and benign examples (Section 5.13 of [3]). If the attacker moves the adversarial example generated by PGD towards the original benign input by interpolation, can the proposed characterization still distinguish between the original benign input and the adversarial example moved towards it?


### Clarity

**Strengths (major)**
* The overall presentation is good. I appreciate the clear demonstration in Figure 1.
* The summarized conditions in Section 4.2 is good.

**Weaknesses (minor)**
* The setting discussed at L24-26 comes out without any context, making it hard to understand why it is important and hard to achieve. It is suggested to motivate this setting with some related work and emphasize it more throughout the paper.
* Similarly, at L59 I can see that the setting is extremely limited, but what are the strong "cues" and why are they hard to solve?

### Significance

I appreciate the great effort in characterizing the trace of PGD-like attacks and the extensive experiments; this paper might inspire some work in that direction. However, my biggest concern about this work is its robustness as a defense against adversarial examples, given my experience of the commonly acknowledged importance of evaluating adaptive attacks in the adversarial example defense literature. That being said, I am open to discussion on this point.
questions: My current score is based on the strengths of the proposed characterization method and the expected fix of minor weaknesses noted above. I am willing to raise my score if the following major concerns are adequately clarified or justified.
* [Quality-Weakness-1] What if the least-likely label is not the ground truth label?
* [Quality-Weakness-2] Discuss if the defense is indeed lightweight compared with previous defenses requiring auxiliary models.
* [Quality-Weakness-3.1] Discuss the computational cost of the proposed adaptive attack on CIFAR-10.
* [Quality-Weakness-3.2] Discuss the two adaptive attacks mentioned above.

I am open to decrease the significance of the last question if the meta-reviewer deemed it as beyond scope or outweighed by the strengths of the proposed characterization method in a non-adversarial setting.
limitations: Since this paper claims to propose a defense, its main limitation is the lack of a sufficient discussion of adaptive attacks. Although the authors have provided some discussion at L123-134, I find it hard to be convinced that a more thorough evaluation is not necessary. It is strongly recommended to at least evaluate published adaptive attacks (that break previous similar defenses) on the proposed defense.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors propose a new detection method to detect PGD-like attacks. The detection method is based on the analysis of local linearity between benign samples and adversarial samples. The authors also introduce ARC and SAE to measure the local linearity. The experimental results indicate that this method can successfully detect PGD-like attacks on various datasets and model architectures.
strengths_and_weaknesses: I think using gradients to detect AEs is interesting, and there are few works focusing on this point. However, there are some weaknesses.

1. The design of adaptive attack is not convincing. To minimize the Fro-norm of S_*(x+r), the attacker only needs to adopt an additional loss term to minimize the difference between the gradients of AEs and clean data.
2. There are five requirements for SAE to be consistently triggered. It seems that breaking requirements (III), (IV) and (V) are very easy. The threat model is too strict for me. The victim needs to have perfect knowledge of the attacker. 
3. As a detection method, its premier requirement is fast and cannot influence the performance (e.g., the predicting speed and accuracy) of the classifier. This detection is too slow to use in practice. 
4. The DR in Table 2 is very low, even for the baseline (t1).
5. For ImageNet, the perturbation size is usually very small, i.e., 4./255 or less. So, the results in Table 3 indicate that this detection method cannot efficiently detect AEs for ImageNet.
6. The baseline method is only NSS, which is not enough. Although the proposed method is data-undemanding, I think a victim can freely gather as much as clean data to train a detector. It should not be a problem to compare your method with other previous works.
questions: 1. The authors claim that this method is only sensitive to PGD-like attacks. Is it because that only PGD-like attacks can trigger the local linearity? If a PGD-like attack does not trigger it, can the detection still sensitive to this attack?
2. In Figure 5, what is the reason that NSS is a better detection method on ResNet-152?
limitations: The authors have addressed the limitations. I appreciate it.
review_title: null

Meta-review: metareview: This paper observes that "PGD-like" attack algorithms have characteristics that
allow one to detect an input has been attacked. While I agree that it is
interesting PGD-like attacks have detectable properties, I agree with the
reviewers that designing attck-specific defenses has limited utility. The
authors already show that FGSM and similar attacks are not detected with this
approach, and this makes me worry that adaptive attacks will also not be
easy to detect. And so while making an observation about how PGD works is
interesting, it is not yet sufficient and will likely not form the basis of
a strong defense.

confidence: Certain
Decision: Reject