Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers one important question: how to fairly compare the adversarial robustness between detection-based defenses and classification-based defenses. From the theoretical perspective, the authors show that: one can always (ideally) construct a robust classifier from a robust detector which has equivalent robustness, and vice versa. Based on this construction method, they are able to transfer the robustness between robust detectors and robust classifiers. Finally, they find that most existing detection defenses achieve suspiciously high robust performance compared with state-of-art robust classifiers, if they apply the proposed “transferring” criteria.
main_review: We summarize the Strengths and Weakness of this paper as following:

**Strengths**:
1. It is the first paper to attempt to unify the detection and robust classifier approaches.
2. The authors provide constructive steps to reduce the detector to classifier and vice versa.
3. The part about certified defense highlights the strictness of the theoretical results. 

**Weakness**:
1. In the paper, the authors prove that one can (theoretically) construct a robust (inefficient) classifier from a robust detector which has equivalent robustness (Theorem 4). However, the constructive steps provided in Theorem 4 can not be exactly solved in practice for most of the defense models (except for certified defenses). If it is extremely hard to figure out such a classifier, we still could not say: there exists such a feasible classifier with the same robustness as the detection model. Therefore, the robust accuracy reported by the constructed classifier could be unreasonably high (similar evidence can be found in Table 1). As a result, the construction process in Theorem 4 might give a false sense about the true robustness of the classifier, as well as the original detector. 
2. One possible direction is that: one could approximately solve the “inefficient” problem in Theorem 4, using gradient methods or black box optimization methods. Imagine that, one can approximately solve this problem, he/she can get such a classification model in practice, which will greatly improve the potential practical use of the proposed theorem. 
3. Based on the discussion above, we also hesitate about the practical importance of the experimental results in Table 1. The correctness of the theorems needs verification of the irrelevance of computational complexity in reduction, which is not provided. And the arguments of suspicious high performance of detection defenses are based on adaptive attacks instead of their theorems. Therefore, as said in Section 3, Interpreting our reduction, “does not mean that the defense’s claims is wrong”, the experiment results shown in table 1, which is based on the theorems, can not be used to make any conclusion about the performance of existing detection defenses.
4. Since most of the results of this paper are based on norm-based attacks. Are the results valid for other types of attacks, such as spatial attacks and so on?

**Other comments or remarks**
A typo in theorem 4 proof: in the second and third bullets, x should be $\hat{x}$.


summary_of_the_review: Overall the paper considers an interesting problem and tries to unify the detection and classifier defenses. However, the theorem is only correct without considering the computational complexity and poses another question about the relation between robust classifier training and computational complexity. Also, the experiment part should include approximate results of the reduction steps to verify the feasibility of the theorems in practice.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Adversarial examples are test time attacks in which the input is modified by up to distance \eps (under some metric) and the goal of adversarially robust learning is to have high (generalized) accuracy even under such attacks. One way to make predictions is to always output a label. Another way is to “abstain/detect” when the learner thinks the input is not clean and is perturbed with. The way we evaluate the performance in the detection model is to count detected perturbed inputs as “correctly classified”.

The paper asks a very natural question: is it easier to learn when detection/abstain is allowed or not? The main result of the paper is very clean: For any metric d, and any eps, the existence of a learner that achieves accuracy c under detection model under 2\eps perturbations is (information theoretically) equivalent to the existence of a classifier in the no-detection model with accuracy c and eps perturbation.

The proof is “constructive” but it is not “efficiently constructive”. Namely, given a classifier in either of the two settings above, the paper shows a rather simple (but smart) way of constructing another classifier (with the parameters stated above) in the other model.

The paper then takes this connection to revisit the results of quite a few papers from the literature in which they have claimed defenses that use detection as their key idea. The paper observes that the bounds that (many) of those papers claim would imply classifiers with no detection/abstain that beat the state of the art adversarially robust classifiers. The paper cautiously claims that this indicates that the defenses of those papers are not actually secure, but rather “not broken” under simple attacks tried by the authors.
main_review: Please list both the strengths and weaknesses of the paper. When discussing weaknesses, please provide concrete, actionable feedback on the paper.

On the positive side: the connection between detection and classification is a very natural question that deserves attention. The paper proves a simple, but very nice theorem that as far as I know was not proved before. The connection between “testing” and “decoding” is not completely new in coding theory, and the paper also mentions this, but observing this phenomenon in the context of robust learning, as far as I know, is new. Also, I like the fact that the paper uses this connection to study the implications of results already claimed in the literature.

On the down side, the fact that the theorem of the paper is proved using information theoretic (rather than computationally efficient) reductions, limits the ways one can benefit from such a connection. In particular:
1. It is not completely fair to question previous works’ claimed results on robustness using detection, because those papers did not claim “certified results” or “information theoretic” results, but rather “hardness” of breaking their schemes. Since the reductions in this paper are not computationally feasible, one cannot conclude that those schemes were indeed not secure *computationally*.
2. Most, if not all, settings in which robust learning is a hot topic, one already knows the existence of a “robust” ground truck function. In particular, for image classification, it is the assumption that humans are robust to small \eps perturbations, and the goal is to find such classifiers automatically. In such contexts, the results of this paper become obsolete, because the reductions exist trivially. This further limits the applicability of the results.

Other comments:

Page 2: “To the author's knowledge, there is no known way of leveraging computational inefficiency to build more robust models. ”

The (cited) paper by Garg et al seems to exactly show the possibility that computational efficiency could be leveraged to achieve robustness.

The two papers “Garg et al. (2020) and Bubeck et al. (2018) are actually quite different, in how they deal with the role of computational efficiency” One deals with poly-time learning and the other deals with poly-time attacking. I think it's the latter that is more directly related to this work’s message.

Following up on the issue (2) mentioned above, one might say that the result of the paper still applies even if the ground truth is *not* robust to eps perturbations. But then in that case, it brings up another issue: the definition used in this paper would *not* imply that an *adversarial example* is actually misclassified. This issue is discussed in some previous work such as “Revisiting Adversarial Risk” Suggala et al (AISTA’19) and “Adversarial Risk and Robustness: General Definitions...” Diochnos et al (NeurIPS’18).

summary_of_the_review: The paper proves a natural theoretical result that is at the heart of robust learning. The result is information theoretic, but I still find it quite natural.

I think one should be very cautious to not overly interpret the implications of this paper, but I think the mere theoretical observation that testing and decoding in the context of adversarial learning are equivalent has a merit, that at least puts this paper on the border for ICLR.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper showcases the vulnerability of existing adversarial detection algorithms. Multiple existing detection-based defense algorithms are considered and have shown theoretically that the robustness claimed by those algorithms might not be the same as claimed in the corresponding papers. 
main_review: While the idea is interesting and needs some attention; however, considering only the attacker is intelligent is somewhat wrong or misleading in both this and existing papers referred. If the defense can be broken using a new adaptive attack using the knowledge of the defense, then the defender must also have the same knowledge to modify the defense to carefully check the limit of defense.

Another interesting question is why the attacker needs to generate an attack if he/she can assume all knowledge of the defense and the target model? Why not simply modify the decision? Therefore, before showcasing the defenses are not working it is expected to consider this and adaptive defense or give the same freedom to the defender as well.

The claims made in the paper are not empirically tested, they are mainly based on the assumptions of the authors or one selected paper. It will be great if the authors can showcase that actually, the defenses are not working.

What do the authors mean by the " the evaluation is inefficient" on page 7? Please refer to some string defenses:

[1] Detection based defense against adversarial examples from the steganalysis point of view. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 4825-4834).
[2] DAMAD: Database, Attack, and Model Agnostic Adversarial Perturbation Detector, In IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2021.
[3] Image Transformation based Defense Against Adversarial Perturbation on Deep Learning Models, In IEEE Transactions on Dependable and Secure Computing (TDSC), 2021, vol. 18, no. 5, pp. 2106-2121.

Similarly again the term "worst-case robust attack" is not clear? It seems like the paper is based on some pre-assumptions that the detector can not work. Please clarify?

Next sentence on page 7: " if this detector defense's robustness claims were correct -- ". not clean what the author meant and downgrade take the credit of the defense work?

Most of the assumptions are based on one work only: Rebuffi et al. 2021. I feel the authors need to revisit the paper and literature thoroughly not only a few papers which showcase that existing defenses do not work or depend on the robsutness paper. 

summary_of_the_review: The paper is based on assumptions and findings of one single paper most of the time. Without explicit showcase that the existing defense will not work, the analysis seems misleading and unfair to the parts of the defenders as well. 

The authors believe that the existing defenses do not resemble the "worst-case attack". Please generate such an attack and showcase without explicitly touching the defenses that defense is not working.

In my knowledge the true and fair concept to both attacker and defender needs to be there to make serious progress in the field, else this can be just another paper reflecting the singularities of the defenses.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This submission connects the areas of adversarial training and adversarial robust detection. Generally speaking, I think the conclusions in the submitted paper can provide beneficial insights for the community, and avoid overclaims in future adversarial detection research.
main_review: Strength:
This work connects the areas of adversarial training and adversarial detection and the writing is easy to follow. It is of great significance to the future development of adversarial detection research.

Weakness：
The construction of equivalent classifiers and detectors in Theorem 4 and 5 are interesting. However, I have concerns about theorem 4 that epsilon-robust detection implies inefficient epsilon/2-robust classification. For one thing, it lacks a practical and efficient solution to find a perturbed input that is classified differently; for another, the claim is not necessary in practice, for example, if the input is rejected by an adversarial detection, practitioners can simply add random noise on the input until the new input is not rejected. And by the way, compared to the analysis of robust detection of robust classifying, considering adaptive attacks towards adversarial classification and adversarial detection simultaneously is more important. 

The title of this submission seems inappropriate. It’s widely acknowledged the success rate of adversarial detection far outweighs the success rate of adversarial classifying in previous studies. To be specific, since a large amount of high dimensional images within an epsilon ball, classifying all images is a difficult task for neural networks with limited capacity. By contrast, the detection task just has to tell the difference between adversarial examples and natural examples. Hence, the findings in this submission are not convincing that detecting adversarial examples is as hard as classifying them. Similar difficulties should be indicated by similar success rates, otherwise, it will give the public misunderstanding.

A modest proposal: avoid using the paragraphing abstract and delete '\emph{}' and '---' in the open review submission page.

summary_of_the_review: In general, I think this submission can provide beneficial insights and evaluations for the field of adversarial detection. However, it lacks practical solutions, which implies limited contributions. I hope my concerns about Theorem 4 and 5 can be considered (or pointed out my misunderstanding) in the discussion stage. Though I cannot recommend acceptance at this stage, I will increase my score if my concerns are solved properly.
review_title: null

Meta-review: The paper investigates a very interesting problem of the connections between adversarial detection and adversarial classification. Theoretically, the authors show that one can always (ideally) construct a robust classifier from a robust detector that has equivalent robustness, and vice versa. This theorem is only correct without considering the computational complexity. However, the authors did not provide any approximate results of the reduction steps to verify the feasibility of the theorems in practice, which is the main concern of all reviewers. So we can say the paper is a reminder to the community we need to be careful about the detection results but did not provide any evidence to say they are overclaimed (only a conjecture based on the theorem in the paper) which greatly limits the contribution of the paper. Due to the competitiveness of ICLR, I cannot recommend accepting it.
Decision: Reject