Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Them
Authors: Florian Tramer
Venue: ICLR 2022 Submitted (2022)
Keywords: Adversarial Examples
Detection
Hardness Reductions

Abstract: Making classifiers robust to adversarial examples is challenging. 
Thus, many defenses tackle the seemingly easier task of \emph{detecting} perturbed inputs.

We show a barrier towards this goal. We prove a general \emph{hardness reduction} between detection and classification of adversarial examples: given a robust detector for attacks at distance $\epsilon$ (in some metric), we show how to build a similarly robust (but inefficient) \emph{classifier} for attacks at distance $\epsilon/2$---and vice-versa.

Our reduction is computationally inefficient, and thus cannot be used to build practical classifiers. Instead, it is a useful sanity check to test whether empirical detection results imply something much stronger than the authors presumably anticipated.

To illustrate, we revisit $14$ empirical detector defenses published over the past years. For $12/14$ defenses, we show that the claimed detection results imply an inefficient classifier with robustness far beyond the state-of-the-art--- thus casting some doubts on the results' validity.

Finally, we show that our reduction applies in both directions: a robust classifier for attacks at distance $\epsilon/2$ implies an inefficient robust detector at distance $\epsilon$. Thus, we argue that robust classification and robust detection should be regarded as (near)-equivalent problems.

Under review as a conference paper at ICLR 2022
DETECTING ADVERSARIAL EXAMPLES Is (NEARLY) AS HARD AS CLASSIFYING THEM
Anonymous authors Paper under double-blind review
ABSTRACT
Making classifiers robust to adversarial examples challenging. Thus, many de- fenses tackle the seemingly easier task of detecting perturbed inputs.
We show barrier towards this goal. We prove general hardness reduction be- tween detection and classification of adversarial examples: given robust detector for attacks distance (in some metric), we show how to build similarly robust (but inefficient) classifier for attacks at distance c/2 s/2-and and vice-versa.
Our reduction is computationally inefficient, and thus cannot be used to build practical classifiers. Instead, it is a useful samity check to test whether empiri- cal detection results imply something much stronger than the authors presumably anticipated.
To illustrate, we revisit 14 empirical detector defenses published over the past years. For 12/14 defenses, we show that the claimed detection results imply an inefficient classifier with robustness far beyond the stte-offthhe-rr- thus casting some doubts on the results' validity.
Finally, we show that our reduction applies in both directions: robust classi- fier for attacks at distance e/2 implies an inefficient robust detector at distance Thus, we argue that robust classification and robust detection should be regarded (quarl--quivalent problems, if we disregard their computational complexity.
INTRODUCTION
Building models that are robust adversarial examples (Szegedy et al., 2014: Biggio al., 2013) is a major challenge and open-problem in machine learning. Due to the inherent difficulty in building robust classifiers, researchers have attempted to build techniques to least detect adversarial exam- ples, a weaker task that is largely considered easier than robust classification (Xu et al., 2018; Pang et al., 2021; Sheikholcslami et al., 2021).
Yet, evaluating the robustness of empirical detector defenses is challenging. This is in part due to those developed for robust classi-
a lack of strong evaluation guidelines and benchmarks fiers (Carlini et al., 2019; Croce et al., 2020)-as well as to lack of long-standing comparative baselines such as adversarial training (Madry et al., 2018).
To illustrate, consider the following (fictitious) claims about two defenses against adversarial exam- ples on CIFAR-10:
defense A is classifier that achieves robust accuracy of 90% under loo pertururrbass bounded by c = 4/255;
defense B also has a "rejection" option, and achieves robust accuracy of 90% under foo- perturbations bounded by 8/235 (we say that defense B is robust for some example if it classifies that example correctly, and either rejects/detects or correctly classifies all perturbed examples at distance e.)
Which of these two (empirical) claims are you more likely to believe to be correct?
Defense A claims much higher robustness than the current best result achieved with adversarial training (Madry et al., 2018; Rebuffi et al., 2021), the only empirical defense against adversarial examples that has stood the test of time. Indeed, the ofate-of-the-art l. robustness for 4/255

---

Under review as a conference paper at ICLR 2022
on CIFAR-10 (without external data) is 79% (Rebuffi et al., 2021). Thus, the claim of defense A would likely be met with some initial skepticism and heightened serutiny, as could be expected for such claimed breakthrough result.
The claim of defense B is harder to assess, due to a lack of long-standing baselines for robust detectors (many detection defenses have been shown to be broken (Carlini & Wagner, 2017: Tramer et al., 2020)). On one hand, detection of adversarial examples has largely been considered to be an easier task than classification (Xu al., 2018; Pang al., 2021; Sheikholeslami al., 2021). On the other hand, defense B claims robustness to perturbations that are twice as large as defense A (c= vs. E 4/255).
In this paper, we show that the claims of defenses A and B are, in fact, equivalent! (up to computa- tional efficiency.)
We prove a general hardness reduction between classification and detection of adversarial examples. Given a detector defense that achieves robust risk a for attacks distance (under any metric), we show how to build an explicit but inefficient classifier that achieves robust risk a for classifying attacks at distance e/ e/2. The reverse implication also holds: a classifier robust at distance c/2 implies an explicit but inefficient robust detector at distance e.
To the authors knowledge, there is no known way of leveraging computational inefficiency to build more robust models. We should thus be as "surprised" by the claim made by defense B as by the claim made by defense A.
Our reduction provides a way of assessing the plausibility of new robust detection claims, by con- trasting them with results from the more mature literature on robust classification. To illustrate, we revisit 14 published detection defenses across three datasets, and show that in 12/14 cases the de- fense's 's robust detection claims would imply an inefficient classifier with robustness far superior to the current state-of-the aftt Yet, none of these detection papers make the claim that their techniques should imply such a breakthrough in robust classification.
Using our reduction, it is obvious that many detection defenses are claiming much stronger robust- ness than we believe feasible with current techniques. And indeed, many of these defenses were later shown have overestimated their robustness (Carlini & Wagner, 2017: Tramèr et al., 2020).
Remarkably, we find that for certified defenses, the state-of-the-art results for provable robust clas- sification and detection perfectly match the results implied by our reduction. For example, Sheik- holeslami et al. (2021) recently proposed a certified detector on CIFAR-10 with provable robust error that within 3% of the provable error of the inefficient detector obtained by combining our result with the state-of-the -f-th-rrrt robust classifier of Zhang et al. (2020a).
In summary, we prove that giving classifiers access a detection option does not help robustness (or at least, not much). Our work provides, to our knowledge, the first example of a hardness reduction between different approaches for robust machine learning. As in the case of computational com- plexity, we believe that such reductions can be useful for identifying research questions or areas that are unlikely to bear fruit (bar a significant breakthrough) so that the majority of the community's efforts can be redirected elsewhere.
On a technical level, our reduction exposes a natural connection between robustness and error cor- recting codes, which may be of independent interest.
HARDNESS REDUCTIONS BETWEEN ROBUST CLASSIFIERS AND DETECTORS
In this section, we prove our main result: a reduction between robust detectors and robust classifiers, and vice-versa. We first introduce some useful notation and define the (robust) risk of classifiers with and without a detection option.
2.1 PRELIMINARIES
We consider a classification task with a distribution D over examples r E Rd with labels y e [C]. A classifier is function f Rdd - [C]. A detector is classifier with extra "rejection"
2

---

Under review as a conference paper at ICLR 2022
or "detection" option I, that indicates the absence of classification. We assume for simplicity
that classifiers and detectors are deterministic. Our results can easily be extended to randomized functions well. The binary indicator function (a) is 1 if and only if the predicate A is true.
We first define a classifier's risk, i.c., its classification error on unperturbed samples.
Definition (Risk). Let f: Rd + (CJULL be a classifier (optionally with a detection output L). The risk of f is the expected rate at which f fails correctly classify a sample:
R())
(r.a))~ [[(rw
E
Note that for detector, rejecting unperturbed example sampled from the distribution 'D is counted as an eπror.
For classifiers without a rejection option, define the robust risk as the risk on worst-case adver- sarial examples (Madry et al., 2018). Given an input x sampled from D, an adversarial example à constrained being within distance d(x, Ø) S c from x, where is some distance measure.
Definition (Robust risk). Let f: IR [C] be classifier. The robust risk distance is:
Radr(f) = (x.a)>>
max d(a,
(((())AU)
(2)
Thus, a sample (z, y) is robustly classified if and only if every point within distance c of (including itself) correctly classified as y.
For detector (a classifier with an extra detection/rejection output), we analogously define the robust risk with detection. The classifier now allowed reject adversarial examples.
Definition 3 (Robust risk with detection). Let f TRd - [C] U {1} be classifier with an extra detection output 1. The robust risk with detection at distance is:
Redv (f)
E d( (E.
((())) (())((.1)))
That is, a detector defense f is robust natural input x if and only if the defense classifies the natural input x correctly, and the defense either rejects or correctly classifies every perturbed input & within distance e from x. The requirement that the defense correctly classify natural examples eliminates pathological defenses that reject all inputs.
2.2 ROBUST DETECTION IMPLIES INEFFICIENT ROBUST CLASSIFICATION
We are now ready to introduce our main result, reduction from robust detector for adversarial examples at distance e, to an inefficient robust classifier at distance e/2. We later prove that this reduction also holds in the reverse direction, thereby demonstrating the equivalence between robust detection and classification-ug to computational hardness.
Theorem 4 (e-robust detection implies inefficient e/2-robust classification). Let d(.,.) ) an ar- bitrary metric. Let f be detector that achieves risk R(f) a, and robust risk with detection Re Redv- (f) = B. Then, we can construct an explicit (but inefficient) classifier g that achieves risk R(gg) S and robust risk Re12 (g) < B.
The classifier is constructed as follows on input x:
Run the detector model y + (xx) If the input is not rejected, i.e., y o 1, then output the label y that was predicted by the detector.
Otherwise, find an input within distance e/2 of x that not rejected, i.e., d(x, x²) S e/2 and f(x') + L. If such an input x' exists, oulput the label y + f(x'). Else, output a uniformly random label y E [C).
An intuitive illustration for our construction, and for the proof of the theorem (see below) in Figure 1.
3

---

Under review as a conference paper at ICLR 2022
8
6/2
Figure 1: Illustration of the construction of robust classifier from robust detector in Theorem 4. The outer blue circle represents all inputs at distance at most from the input x. For a detector f. the areas in green correspond to correctly classified inputs, and ratcheted gray areas correspond to rejected inputs. The detector f is thus robust on x up to distance e. The classifier classifies perturbed input é, at distance c/2 from x. by finding any input within distance c/2 from (the red dashed circle) that is not rejected by f. Such an input necessarily exists and is correctly labeled by f. The classifier g is thus robust on up to distance c/2.
Our construction be viewed as analog of minimum distance decoding in coding theory. We can view a clean data point sampled from D as a codeword, and an adversarial example è as a noisy message with certain number of errors (where the error magnitude measured using an arbitrary metric on I& rather than the Hamming distance that is typically used for error correcting codes). A standard result in coding theory states that if code can defect a errors, then it can correct a/2 errors. This result follows from a bball-packing" argument: if a errors can be detected, then any two valid codewords must be at least at distance a from each other, and therefore a errors can be corrected via minimum distance decoding.
Proof of Theorem 4. First, note that the natural accuracy our constructed classifier g is at least as high as that of the detector f, since always mimics the output of f whenever f does not reject an input sampled from D. Thus, R(g)= S R(f)= = a.
Now, for the sake of contradiction, consider an input (a., v) ~ D for which the constructed classifier g is not robust distance e/2. By construction, this means that there exists some input & at distance e/2 from such that è is misclassified. i.c., 9( ÿ # y. We will show that the detector is not robust with detection for æ either (for attacks at distance up to e).
By definition of the classifier g. if g ÿ + y then either:
The detector f also misclassifies â, i.e., ((:)
So ff is not robust with detection for x at distance c.
There exists an input x' within distance e/2 of x, such that the detector ff misclassifies z', i.e. f(x') = ÿ.
Note that by the triangular inequality, d(z, x²) < d(z, 2) + d(²,x²) s e/2+2/2222 c, and thus ff is not robust with detection for x at distance
The detector f rejects all inputs x' within distance c/2 of x (and thus g has output 9 by sampling label at random).
Since d(æ, .) < e/2, this implies that the detector also rejects the clean input æ, i...
f(x) 1, and thus is not robust with detection for
4

---

Under review as a conference paper at ICLR 2022
In summary, whenever the constructed classifier g fails to robustly classify input up to dis- tance c/2, the detector f also fails to robustly classify a with detection up to distance c. Taking expectations over the entire distribution D concludes the proof.
Note that the classifier g constructed in Theorem 4 is computationally inefficient. Indeed, the second step of the defense consists in finding a non-rejected input within some metric ball. If the original detector f is non-convex function (e.g.. deep neural network), then this step consists in solving an intractable non-convex optimization problem. Our reduction is thus typically not suitable for building a practical robust classifier. Instead, demonstrates the existence of an inefficient but explicir robust classifier. We discuss the implications of this result more thoroughly in Section 3.
corollary to our reduction is that many "information theoretic" results about robust classifiers can be directly extended to robust detectors. For example, Tsipras et al. (2019) prove that there exists formal tradeoff between classifier's s clean accuracy and robust aceuracy for certain natural tasks. Since their result applies to any classifier (including inefficient ones), combining their result with our reduction implics that a similar accuracy-rouusten Tsipras et al. (2019) show that for certain classification tasks and suitable choices of parameters a, B, c, any classifier which achieves risk R(g) I a must have robust risk at least (g) 2 B against lo perturbations bounded by By our reduction, this implies that any detector with risk at most R(f) & a must also have robust risk with detection at least R²/2 (f) 2 B against lo tx-perturbations bounded by e/2.
tradcoff exists for detectors. More precisely,
Similar arguments can be applied to show, for instance, that the increased data complexity of robust generalization from Schmidt al. (2018), the tradeoff between robustness to multiple perturba- tion types from Tramèr & Boneh (2019), also apply to robust detectors.
Our reduction does not apply for "computational" hardness results that have been shown for robust classification. For example, Garg et al. (2020) and Bubeck et al. (2018) show ("unnatural"" distri- butions where learning robust classifier is computationally assumptions. We cannot use Theorem 4 to conclude that learning a robust detector is hard for these distributions, since the existence of such a detector would only imply an inefficient robust classifier which does not contradict the results of Garg et al. (2020) or Bubeck et al. (2018).
under standard eryptographic
2.3 ROBUST CLASSIFICATION IMPLIES INEFFICIENT ROBUST DETECTION
similar argument as in Theorem can be used in the opposite direction, to show that a robust clas- sifier at distance e/2 implies inefficient robust detector at distance Taken together, Theorem and Theorem show that robust detection and classification are equivalent, up to a factor 2 in the norm bound and up computational constraints.
Theorem 5 (c/2 caabus--lassiffcattin implies inefficient e-robust detection). Let d(.,-) )) be arbi- trary metric. Let be defense that achieves robust risk Re/2 (f) B. Then, we can construct an explicit (but inefficient) defense f that achieves risk R() B and robust risk with detection &e S 3.
The defense is constructed as follows on inpus x:
Run the classifier y g(x)..
Find a perturbed input x' withing distance e/2 of x that is classified differently, i.e., ((x,x") S e/2 and g(x') # If such an imput x' exists, reject the input and oulput 1. Else, output the class y.
We provide the proof of Theorem 5 in Appendix A.
A main distinction between Theorem 4 and Theorem 5 is that the construction in Theorem pre- serves clean accuracy, but the construction in Theorem 5 does not. That is, the constructed robust detector in Theorem 5 has clean accuracy that equal to the robust classifier's robust accuracy.
The construction in Theorem 5 be efficiently (but approximately) instantiated by certifiably robust classifier (Wong & Kolter, 2018; Raghunathan et al., 2018). These defenses can certify that classifier's output is constant for all points within some distance of the input. For an adversarial
5

---

Under review as a conference paper at ICLR 2022
example è for g, the certification always fails and thus the constructed detector f will reject é. If robust and the certification succeeds, the detector f copies the output of g. However, a certified defense may fail to certify robust imput (a false negative), and thus the detector f may reject more inputs than with the "optimal" construction in Theorem 5. This reduction from a certified classifier to detector is implicit in (Wong & Kolter, 2018, Section 3.1).
3 WHAT ARE DETECTION DEFENSES CLAIMING?
We now survey 14 detection defenses, and consider the robust classification performance that these defenses implicitly claim (via Theorem 4). As we will see, 12/14 cases, the defenses' detection results imply an inefficient classifier with far better robust accuracy than the state-of-the-arr
Before presenting our experimental setup and the explicit results from the reduction, we first discuss how we believe these results should be interpreted.
Interpreting our reduction. Suppose that some detector defense claims robust accuracy that implies-vis via our reduction-and inefficient classifier with much higher robustness that the state-of- the-art (e.g., the defense A described in the introduction of this paper).
A first possible interpretation of our reduction is that this robust detector implies the existence of a robust classifier. This interpretation is rather weak however, since it is typically presumed that robust classification is possible, and that human perception is one concrete example of a robust classifier. The existence of robust classifier is thus typically already assumed to be true.
Our reduction yields a stronger result. It provides an explicit construction of an (inefficient) robust classifier from robust detector. The question then is whether we should expect the construction of inefficient robust classifiers to be easier than the construction of efficient ones. That is, do we expect that we can leverage computational inefficiency build more robust classifiers that the current state-of-thee-arl
We do not know of a positive answer to this question, and there is evidence to suggest that the answer may be negative.' For example, the work of Schmidt et al. (2018) proves that for synthetic classifi- cation task between Gaussian distributions, building more robust classifiers requires additional data regardless of the amount of computation power. Their results are corroborated by current state-of- the-art robust classifiers based on adversarial training (Madry et al., 2018), which do not appear to be limited by computational constraints. On CIFAR-10 10 for example, adversarial training achieves 100% robust training accuracy (Schmidt et al., 2018). Thus, it is unclear how computational ineffi- ciency could be leveraged to build more robust classifiers using existing techniques.
Candidate approaches could be to train much larger models (c.g., with an exponential number of parameters), or perform exhaustive architecture search to find more robust models. Yet, note that the robust classifier constructed in our reduction only uses its unbounded computational power inference time. That is, the classifier that is built in Theorem 4 uses a trained detector model as subroutine (which is presumed to be efficient), and then solves a non-convex optimization problem inference time. The classifier built in our reduction is thus presumably weaker than robust classifier that can be trained with unbounded computational power.
To summarize, when detector defense claims a certain robust accuracy, this implies the existence of a concretely instantiatable robust classifier with an inefficient inference procedure. If this inefficient classifier is much more robust than the current state-of-the tatt this does not necessarily mean that the defense's is claims is wrong. But given how challenging robust classification is proving to be, we have reason to be skeptical of such a major breakthrough (even for inefficient classifiers). To compound this, many proposed detection defenses are quite simple, and reject adversarial inputs based on some standard statistical test over a neural network's ' features. It would thus be particularly surprising if such simple techniques could yield robust classifiers, given that "simple" approaches to adversarial robustness (denoising, compression, randommess, etc.) are incffective (He et al., 2017).
'ome works have shown that for certain "unnatural distributions". computational inetficiency is necessary to build robust classifiers (Garg et al., 2020: Bubeck et al.. 2018). Yet. since we presume that the human perceptual system is robust to small perturbations natural data (e.g., such as CIFAR-10), there must exist. some efficient natural process achieve robustness such data.

---

Under review as a conference paper at ICLR 2022
As result, is not too surprising that number of the detector defenses that survey have already been broken by stronger attacks (Carlini & Wagner, 2017; Tramèr et al., 2020). Our reduction would have already suggested that such a break was likely to happen.
Experimental setup. We choose 14 detector defenses from the literature (see Table 1). Our se- lection of these defenses was partially motivated by a pragmatic consideration on the easiness of translating the defenses' claims into a bound on the robust risk with detection R der- Indeed, some defenses simply report a single AUC score for the detector's performance, from which we cannot derive useful bound on the robust risk. We thus focus on defenses that either directly report robust error akin to Definition 3, or that provide concrete pairs of false-positive and false-negative rates (e.g., full ROC curve). In the latter case, we compute a "best-effort" bound on the robust risk with detection 2 as:
de det (f) < FPR + FNR + R(f),
(4)
where FPR and FNR are the detector's s false- ciisse-psitivee and false-negative rates for a fixed detection threshold, and R(f) is the defense's standard risk (i.e., the test error on natural examples).
The above union bound in Equation (4) is quite pessimistic, as we may over-count examples that lead to multiple sources of errors (e.g., a natural input that is misclassified and erroneously detected). The true robustness claim made by these detector defenses might thus be stronger than what we obtain from bound. We encourage future detection papers to report their adversarial risk with detection, Rudv-der to facilitate direct comparisons with robust classifiers using our reduction.
The 14 detector defenses use three datasets: MNIST, CIFAR-I0 and ImageNet, and consider ad- versarial examples under the foe or &2 norms. Given a claim of robust detection at distance we contrast it to a sfate-of-the-art robust classification result for distance c/2:
On MNIST with foo attacks, we use the adversarially-tran trained TRADES classifier (Zhang et al., 2019) and measure robust error with the Square attack (Andriushchenko al., 2020).
On MNIST with lg attacks, we the adversarially pegrsarrilly-trrineed trained classifier from Tramèr & Boneh (2019) and measure robust error with PGD (Madry et al., 2018).
On CIFAR-10, for both loo and f2 attacks we use the adversarially-trainee classifier of Re- buffi et al. (2021) (trained without external data), and attack it using the APGD-CE attack from AutoAttack (Croce& & Hein, 2020).
For ImageNet, for both Loo and & attacks we use dddersariallly-raiine classifiers and PGD attacks from Engstrom al. (2019).
We also consider two certified defenses for lov attacks on CIFAR-10: the robust classifier of Zhang et al. (2020a), and recent certified detector of Sheikholeslami et al. (2021).
Results. As we can see from Table 1, most defenses claim detection performance that implies a far greater robust accuracy than our current best robust classifiers. To illustrate with a concrete exam- ple, the CIFAR-10 10 detector of Miller et al. (2019) claims to achieve robust accuracy with detection of 75% for l attacks with e = 2.9. Using Theorem 4, this implies an inefficient classifier with robust accuracy of 75% for & attacks with 2.9/2 1.45. Yet, the current state-of-the-att robust accuracy for such a perturbation budget is only 30% (Rebuffi et al., 2021). If this detector defense's robustness claim were correct, it would imply a remarkable breakthrough in robust classification.
Why do many of these defenses claim robust accuracies that appear "too good to be true"? A pri- mary reason is that the vast majority of the above detector defenses do not consider evaluations against adaptive attacks (Carlini et al., 2019; Athalye et al., 2018; Tramèr et al., 2020). That is, these defenses show that they can detect some fixed altacks, and thereafter conclude that the detec- tor is robust against all attacks. As in the case of robust classifiers, such an evaluation is clearly insufficient! Some defenses do evaluate against adaptive adversaries, but fail to build sufficiently strong attack to reliably approximate the worst-case robust risk. Because of the lack of strong comparative baseline, it is not always immediately clear that these results are overly strong.
2 Many detector defenses report performance against a set of fixed (non-adaptive) attacks. We interpret these results as being an approximation of the worst-case risk.
7

---

Under review as a conference paper at ICLR 2022
Table I: For each detector defense, compute (best-effort) bound the claimed robust risk with detection de using Equation (4), and report the complement (the robust accuracy with detection), 1
Re adv-der For each detector's robustness claim (at distance e), we report the state- of-the-art robust classification accuracy for attacks at distance e/2, denoted RT Detection defense claims that imply a higher robust classification accuracy than the current state-of-the-art are highlighted in red.
Dataset
Defense
Norm
c
1
R adv-det
R
Grosse et al. (2017)
660
0.5
2
98%
94%
MNIST
Ma et al. (2018)
bg
4.2
99%
72%
Raghuram al. (2021)
Eg
8.9
74%
0%
Yin et al. (2020)
82
1.7
90%
66%
Feinman al. (2017)
2.7
43%
36%
Miller et (2019)
2.9
75%
30%
Raghuram et al. (2021)
4.0
Z 56%
10%
CIFAR-10
Ma Liu (2019)
L00
4/255
96%
85%
Roth et al. (2019)
600
8/255
Z 66%
79%
Lee et al. (2018)
Lxo
20 20/255
81%
59%
Li et al. (2019)
80o
26 26/255
80%
44%
Xu et al. (2018)
8g
1.0
I
67%
54%
Ma & Liu (2019)
toc
2/255
68%
55%
ImageNet
Jha al. (2019)
too
2/253
30%
55%
Hendrycks & Gimpel (2017)
loc 10/255
N 76%
30%
Yu et al. (2019)
loo 26/255
Z
7%
5%
For example, the recent work of Raghuram et al. (2021, ICML Long Talk) builds a detector on MNIST with a FNR of < 5% FPR of < 20%, for adaptive & attacks bounded by 8.9. Yet. this perturbation bound is much larger than the average distance between an MNIST image and the nearest image from different class! Thus, an attack within this perturbation bound can trivially reduce the detector's accuracy to chance. On CIFAR-10, the same detector achieves 95% clean accuracy, and a FNR of < 19% a FPR of < 20% for adaptive &g attacks bounded by c 4. Using Equation (4), this yields a bound on the robust accuracy with detection of 1 Raav-a (f) >
1 (5% + 19% + 20%) = 56%. In contrast, the best robust classifier we are aware of for & attacks bounded by the adaptive attack considered this detector defense's 's evaluation is highly unlikely to be good approximation of worst-case attack, and this defense likely be broken by stronger attacks.
achieves robust accuracy of only 10% (Rebuffi et al., 2021). 1). In summary,
Certifiably robust detection and classification. In Table 2, we look the robust accuracy with detection, and standard robust accuracy achieved by certified defenses (for which the claimed ro- bustness numbers are necessarily mathematically correct).
We note that our reduction is not as meaningful in the case of certified defenses, since it is highly plausible that computational inefficiency can be leveraged to build better certified classifiers. In- deed, given any robust classifier (e.g., adversarially trained model), the classifier's 's robustness can always certified inefficiently (by enumerating over all points within an e-ball). Thus, the existence of inefficient classifier with higher certified robustness than the state-of-the-an is to be expected.
Nevertheless, we find that existing results for certified classifiers and detectors perfectly match what implied by reduction (up +2% error). For example, Zhang et al. (2020a) follow long line of results on robust classifiers and achieve 39% robust accuracy on CIFAR-10 --0 for perturbations of l -orm below 4/255. Together with Theorem this implies inefficient detector with 39% robust
8

---

Under review as a conference paper at ICLR 2022
Table 2:
Certified robust accuracy 1 Rt/2 for the defense of Zhang et al. (2020a), and certified idy robust accuracy with detection 1 Re det for the defense of Sheikholeslami et al. (2021).
1 - R dev.det
1 - RC/2
8/255
37%
39%
16 16/255
32%
33%
detection accuracy for perturbations of fo-moomm below 8/255. The recent work of Sheikholeslami al. (2021) nearly matches that bound (37% robust accuracy with detection), with a defense that has the advantage of being concretely efficient.
These results give additional credence our thesis: with current techniques, robust classification is indeed approximately twice as hard (in terms of the perturbation bounds covered) than robust detection.
Extensions and open problems. The main open problem raised by our work is of course whether it could be possible to show an efficient reduction between classification and detection of adversarial examples, but this seems implausible (at least with our minimum distance decoding approach).
Another interesting question whether a similar reduction can be shown for robustness to less "structured" perturbations than l balls and other metric spaces. For example, there has been a line of research on defending against adversarial patches (Brown et al., 2017), using empirical (Hayes, 2018; Naseer et al., 2019; Chou et al., 2020) and certifiable techniques (Chiang et al., 2020; Zhang et al., 2020b; Xiang et al., 2021). J. To use our result, we would have to define some metric to measure the size of adversarial patch's 's perturbation. Yet, the size of patch is typically defined by the number of contiguously perturbed pixels, which does not define a metric (in particular, it does not satisfy the triangular inequality which our reduction relies on).
Finally, similar hardness reductions might exist between other candidate approaches for building robust classifiers. For example, the question of whether (test-time) randomness can be leveraged to build more robust models is also intriguing .Empirical defenses that use randomness can be noto- riously hard evaluate (Athalye et al., 2018; Tramèr et al., 2020), so reduction similar ours might be useful in showing that we should not expect such approaches to bare fruit.
4 CONCLUSION
We have shown formal reductions between robust classification with, and without, a detection op- tion. Our results show that significant progress one of these two tasks implies similar progress on the other-unless computational inefficiency can somehow be leveraged to build more robust models. This raises the question on whether should spend our efforts on studying both of these tasks, or focus our efforts on single one.
On one hand, the two tasks represent different ways of tackling a common goal, and working on either task might result in new techniques or ideas that apply to the other task as well. On the other hand, our reductions show that unless we make progress on both tasks, work on one of the tasks can merely aim to match the robustness of our inefficient constructions, whilst improving their computational complexity.
We believe our reduction will serve as useful sanity-check when assessing the claims of future de- tector defenses. Detector defenses' robustness evaluations have received less stringent scrutiny than robust classifiers over the past years, perhaps in part due to lack of strong comparative baselines. Instead of having to wait until some detector defense's claims pass the test-of-time, we show that detection results be directly contrasted against moagsstnnding results for robust classification.
When applying this approach to past detector defenses, we find that many make robustness claims that imply significant breakthroughs in robust classification. We believe our reduction could have been useful in highlighting the suspiciously strong claims made by many of these ceseenes-beffone they were explicitly broken by stronger attacks.

---

Under review as a conference paper at ICLR 2022
Ethics statement. Our paper demonstrates fundamental barrier towards detecting against adver- sarial examples, under the assumption that our current techniques are insufficient to achieve strong (inefficient) robust classification. We do not however explicitly break any existing defenses (our results merely strongly suggest that many existing detector defenses' claims are suspiciously high). Our paper therefore cannot lead to any explicit harms, but aims to further understanding of the hardness of robust classification and detection.
Reproducibility statement. Our paper's contribution is mainly theoretical nature. Section is self-contained and clearly states our assumptions, results and proofs (except for the proof of Theorem in Appendix A). The experiments Section 3 use only public datasets and pre-trained models, with clearly indicates hyper-paramette for all attacks that evaluate.
REFERENCES
Maksym Andriushchenko. Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square at- tack: a query-efficient black-box adversarial attack via random search. In European Conference on Computer Vision, 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of se- curity: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, 2018.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smniić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Euro- pean Conference Machine Learning and Knowledge Discovery in Databases, pp. 387-402. Springer, 2013.
Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch. arXiv preprint arXiv: 1X12:1172 2017.
Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. Adversarial examples from cryp- 2018.
tographic pseudo-random generators. arXiv preprint
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In AlSec, pp. 3-14. ACM, 2017.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, and Aleksander Madry. On evaluating adversarial robustness. arXiv preprint arXhv:1902.06705. 2019.
Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Goldstein. Certified defenses for adversarial patches. arXiv preprint arXiv:2003.06633 2020.
Edward Chou, Florian Tramèr, and Giancarlo Pellegrino. Sentinet: Detecting physical attacks against deep learning systems. In Workshop on Deep Learning Security, 2020.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In ICML, 2020.
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adversarial robustness bench- mark. arXiv preprint arXiv:2010.00 096700, 2020.
Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019.
robustness.
Reuben Feinman, Ryan R Curtin, Saurabh Shintre, and Andrew B Gardner. Detecting adversarial samples from artifacts. arXiv preprint arXiv: /703.004 2017.
Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mahmoody Mohammad. Adversarially robust learning could leverage computational hardness. In Algorithmic Learning Theory, pp. 364-385. PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2022
Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick McDaniel. On the (statistical) detection adversarial examples. arXiv preprint arXiv: 2017.
Jamie Hayes. On visible adversarial perturbations & digital watermarking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 1597-1604, 2018.
Warren He, James Wei, Xinyun Chen, Nicholas Carlini, and Dawn Song. Adversarial example defenses: Ensembles of weak defenses are not strong. In USENIX Workshop on Offensive Tech- nologies, 2017.
Dan Hendrycks and Kevin Gimpel. Early methods for detecting adversarial images. In International Conference on Learning Representations, 2017.
Susmit Jha, Sunny Raj, Steven Lawrence Fernandes, Sumit Kumar Jha, Somesh Jha, Gunjan Verma, Brian Jalaian, and Ananthram Swami. Attribution-driven causal analysis for detection of adver- sarial examples. arXiv preprint arXiv:1903.0588 2019.
Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. simple unified framework for detecting out-of-distributin samples and adversarial attacks. In Advances in Neural Information Process- ing Systems, 2018.
Yingzhen Li, John Bradshaw, and Yash Sharma. Are generative classifiers more robust to adversarial attacks? In International Conference on Machine Learning, pp. 3804-3814. PMLR, 2019.
Shiqing Ma and Yingqi Liu. Nic: Detecting adversarial samples with neural network invariant checking. In Proceedings the 26th Network and Distributed System Security Symposium (NDSS 2019), 2019.
Xingjun Ma, Bo Li. Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In International Conference Learning Representations, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018
David Miller, Yujia Wang, and George Kesidis. When not to classify: Anomaly detection of attacks (ada) dnn classifiers test time. Neural computation, 31(8) 1670, 2019.
Muzammal Naseer, Salman Khan, and Fatih Porikli. Local gradients smoothing: Defense against localized adversarial attacks. In 2019 IEEE Winter Conference Applications of Computer Vision (WACV), pp. 1300-1307. IEEE, 2019.
Tianyu Pang. Huishuai Zhang. Di He, Yinpeng Dong, Hang Su, Wei Chen, Jun Zhu, and Tic- Kie-Yan Liu. Adversarial training with rectified rejection. arXiv preprint arXiv:2 /4785, 2021.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference Learning Representations, 2018.
Jayaram Raghuram, Varun Chandrasekaran, Somesh Jha, and Suman Banerjee. A general frame- work for detecting anomalous inputs to dnn classifiers. In International Conference Machine Learning. 2021.
Sylvestre-AIvee Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Tim- othy Mann. Fixing data augmentation to improve adversarial robustness. arXiv preprint arXiv:2103.01946, 2021.
Kevin Roth, Yannic Kilcher, and Thomas Hofmann. The odds are odd: A statistical test for detecting adversarial examples. In International Conference on Machine Learning. 2019.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar. and Aleksander Madry. Adver- sarially robust generalization requires more data. In Advances In Neural Information Processing Systems, pp. 5019-5031, 2018.
11

---

Under review as a conference paper at ICLR 2022
Fatemeh Sheikholeslami, Ali Lotfi, and J Zico Kolter. Provably robust classification of adversarial examples with detection. In International Conference on Learning Representations, 2021.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
Florian Tramèr and Dan Boneh. Adversarial training and robustness for multiple perturbations. In Advances In Neural Information Processing Systems, 2019.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry, On adaptive attacks to adversarial example defenses. In Conference Neural Information Processing Systems, 2020.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representa- tions, 2019.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5283-5292, 2018.
Chong Xiang, Arjun Nitin Bhagoji, Vikash Sehwag, and Prateek Mittal. Patchguard: A provably ousenss against adversarial patches via small receptive fields and masking. In 30th {USENIX) Security Symposium (!USENIX) Security 21), 2021.
Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Detecting adversarial examples in deep neural networks. In Network and Distributed System Security Symposium, 2018.
Xuwang Yin, Soheil Kolouri, and Gustavo K Rohde. Gat: Generative adversarial training for ad- versarial example detection and robust classification. In International Conference on Learning Representations, 2020.
Tao Yu, Shengyuan Hu, Chuan Guo, Wei-Lun Chao, and Kilian Weinherger. A new defense against adversarial images: Turning a weakness into a strength. In Advances in Neural Informa- fion Processing Systems, 2019.
Hongyang Zhang, Yaodong Yu. Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, 2019.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference Learning Representations, 2020a.
Zhanyuan Zhang, Benson Yuan, Michael McCoyd, and David Wagner. Clipped bagnet: Defending against sticker attacks with clipped bag-of-features. In 2020 IEEE Security and Privacy Work- shops (SPW), pp. 55-61, IEEE, 2020b.
12

---

Under review as a conference paper at ICLR 2022
A PROOF OF THEOREM 5.
We recall Theorem 5:
Theorem (e/2 coouss-clasificatioo implies inefficient e-robust detection). Let d(..)) be an arbi-
Irury metric. Let be defense thut achieves robust risk R (J) B. Then, we can construct an explicit (but inefficient) defense f that achieves risk R(f) S B and robust risk with detection Radv-ser S 3.
The defense is constructed as follows on input x::
Run the classifier y g(z).
Find a perturbed input x' withing distance e/2 of x. that classified differently, i.e., d(x,x') S 6/2 and g(x') * If such an input x' exists, reject the input and output I. E.Ese, output the class
Proof of Theorem 5. Note that for any input (2r for which the classifier g is robust distance e/2, no input x' above exists and so f(x) y. Thus, the risk of is at most the robust risk of so R(f) 3.
Now, consider an input (z, y) D for which f is not robust with detection at distance 6. That is, either f(x) + y, or there exists an input è at distance d(x;, .) S such that f(i) 0 {y. -3. We will show that the defense is not robust for either (for attacks at distance up to c/2.)
If f(x) # y, then by the same argument as above cannot be the case that g robust distance c/2 for
So let us consider the case where f(ø) = (y. By the definition of f. this means that for all x' at distance at most c/2 from å, we have g(x') = ÿ. But, note that there exists point x that is at distance at most e/2 from both and x. Since we must have g(x*) ) = ÿ. we conclude that is not robust at distance 2 for x.
Taking expectations over the distribution D concludes the proof.
13


Reviews:
[{"review_id": "lxldCBocsw", "reviewer": "Reviewer_hr6H", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "We summarize the Strengths and Weakness of this paper as following:\n\n**Strengths**:\n1. It is the first paper to attempt to unify the detection and robust classifier approaches.\n2. The authors provide constructive steps to reduce the detector to classifier and vice versa.\n3. The part about certified defense highlights the strictness of the theoretical results. \n\n**Weakness**:\n1. 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. \n2. 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. \n3. 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.\n4. 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?\n\n**Other comments or remarks**\nA typo in theorem 4 proof: in the second and third bullets, x should be $\\hat{x}$.\n\n", "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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "b4pIDiam8E", "reviewer": "Reviewer_Jyt1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Please list both the strengths and weaknesses of the paper. When discussing weaknesses, please provide concrete, actionable feedback on the paper.\n\nOn 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.\n\nOn 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:\n1. 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*.\n2. 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.\n\nOther comments:\n\nPage 2: “To the author's knowledge, there is no known way of leveraging computational inefficiency to build more robust models. ”\n\nThe (cited) paper by Garg et al seems to exactly show the possibility that computational efficiency could be leveraged to achieve robustness.\n\nThe 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.\n\nFollowing 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).\n", "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”.\n\nThe 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.\n\nThe 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.\n\nThe 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.", "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.\n\nI 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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "W5_32_mJ6Y3", "reviewer": "Reviewer_2ebX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThis 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.\n\nWeakness：\nThe 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. \n\nThe 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.\n\nA modest proposal: avoid using the paragraphing abstract and delete '\\emph{}' and '---' in the open review submission page.\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-AKwa3ObrRh", "reviewer": "Reviewer_RAPn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nAnother 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.\n\nThe 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.\n\nWhat do the authors mean by the \" the evaluation is inefficient\" on page 7? Please refer to some string defenses:\n\n[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).\n[2] DAMAD: Database, Attack, and Model Agnostic Adversarial Perturbation Detector, In IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2021.\n[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.\n\nSimilarly 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?\n\nNext 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?\n\nMost 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. \n", "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. ", "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. \n\nThe 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.\n\nIn 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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

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