Provably robust classification of adversarial examples with detection
Authors: Fatemeh Sheikholeslami
Ali Lotfi
J Zico Kolter
Venue: ICLR 2021 Poster (2021)
Keywords: Adversarial robustness
robust deep learning

Abstract: Adversarial attacks against deep networks can be defended against either by building robust classifiers or, by creating classifiers that can \emph{detect} the presence of adversarial perturbations.  Although it may intuitively seem easier to simply detect attacks rather than build a robust classifier, this has not bourne out in practice even empirically, as most detection methods have subsequently been broken by adaptive attacks, thus necessitating \emph{verifiable} performance for detection mechanisms.  In this paper, we propose a new method for jointly training a provably robust classifier and detector.  Specifically, we show that by introducing an additional "abstain/detection" into a classifier, we can modify existing certified defense mechanisms to allow the classifier to either robustly classify \emph{or} detect adversarial attacks.  We extend the common interval bound propagation (IBP) method for certified robustness under $\ell_\infty$ perturbations to account for our new robust objective, and show that the method outperforms traditional IBP used in isolation, especially for large perturbation sizes.  Specifically, tests on MNIST and CIFAR-10 datasets exhibit promising results, for example with provable robust error less than $63.63\%$ and $67.92\%$, for $55.6\%$ and $66.37\%$ natural error, for $\epsilon=8/255$ and $16/255$ on the CIFAR-10 dataset, respectively.


Published as a conference paper at ICLR 2021
PROVABLY ROBUST CLASSIFICATION OF ADVERSARIAL EXAMPLES WITH DETECTION
Fatemeh Sheikholeslami
Ali Lotfi Rezaabad
Bosch Center for Artificial Intelligence
The University of Texas at Austin Austin, TX alotf fi ferfffeutexxe @uttexa..dei
Pittsburgh, PA fatemeh. she khol lmmi @us. bwsch.ccc.....oo..ooo com
J. Zico Kolter
Bosch Center for Artificial Intelligence Carnegie Mellon University Pittsburgh. PA
Kolterrcss.. cmu. edu
ABSTRACT
Adversarial attacks against deep networks can be defended against either by build- ing robust classifiers or, by creating classifiers that can detect the presence of ad- versarial perturbations. Although may intuitively seem easier to simply detect attacks rather than build a robust classifier, this has not bourne out in practice even empirically, as most detection methods have subsequently been broken by adaptive attacks, thus necessitating verifiable performance for detection mecha- nisms. In this paper, we propose a new method for jointly training provably robust classifier and detector. Specifically, we show that by introducing addi- tional "abstain/detection" " into a classifier, we can modify existing certified defense mechanisms to allow the classifier either robustly classify or detect adversarial attacks. We extend the common interval bound propagation (IBP) method for cer- tified robustness under lo perturbations account for new robust objective, and show that the method outperforms traditional IBP used in isolation, especially for large perturbation sizes. Specifically, tests on MNIST and CIFAR-I0 datasets exhibit promising results, for example with provable robust error less than 63. 63.63% and 67. .9,,, for 55.6% and 66.37% natural error, for e = 8/255 and 16/255 on the CIFAR-10 10 dataset, respectively.
INTRODUCTION
Despite popularity and success of deep neural networks in many applications, their performance declines sharply in adversarial settings. Small adversarial perturbations are shown to greatly dete- riorate the performance of neural network classifiers, which creates a growing concern for utilizing them in safety critical application where robust performance is key. In adversarial training, different methods with varying levels of computational complexity aim at robustifying the network by finding such adversarial examples at each training steps and adding them to the training dataset. While such methods exhibit empirical robustness, they lack verifiable guarantees as it is not provable that a more rigorous adversary, e.g., one that does brute-force enumeration to compute adversarial perturbations, will not be able to cause the classifier to misclassify.
It is thus desirable to provably verify the performance of robust classifiers without restricting the ad- versarial perturbations by inexact solvers, while restraining perturbations to a class of admissible set, e.g.. within an f.x. norm-bounded ball. Progress has been made by 'complete methods' that use Sat- isfiability Modulo Theory (SMT) or Mixed-Integer Programming (MIP) to provide exact robustness bounds, however, such approaches are expensive, and difficult scale to large networks as exhaus- tive enumeration in the worst case is required (Tjeng et al., 2017; Ehlers, 2017; Xiao et al., 2018).
Work was done when the author was an intern at Bosch Center for Artificial Intelligence, Pittsburgh, PA.

---

Published as a conference paper at ICLR 2021
'Icomplete methods' on the other hand, proceed by computing a differential upper bound on the worst-case adversarial loss, and similarly for the verification violations, with lower computational complexity and improved scalability. Such upper bounds, if easy to compute, can be utilized during the training, and yield provably robust networks with tight bounds. In particular, bound propaga- tion via various methods such differentiable geometric abstractions (Mirman et al., 2018), convex polytope relaxation (Wong & Kolter, 2018), and more recently in (Salman et al., 2019; Balunovic & Vechev, 2020; Gowal et al., 2018; Zhang et al., 2020), together with other techniques such as semi- definite relaxation, (Fazlyab et al., 2019; Raghunathan et al., 2018), and dual solutions via additional verifier networks (Dvijotham et al., 2018) fall within this category. In particular, recent successful use of Interval Bound Propagation (IBP) as simple layer-by-layer bound propagation mechanism was shown to be very effective in Gowal et al. (2018), which despite its light computational com- plexity exhibits SOTA robustness verification. Additionally, combining IBP in forward bounding pass with linear relaxation based backward bounding pass (CROWN) Zhang et al. (2020) leads to improved robustness, although it can be up to 3-10 times slower.
Alternative to robust classification, detection of adversarial examples can also provide robust- ness against adversarial attacks, where suspicious inputs will be flagged and the classifier "re- jects/abstains" from assigning a label. There has been some work on detection of diitr---iittiittioonn examples Bitterwolf et al. (2020), however the situation in the literature the detection of adver- sarial examples is quite different from above. Most techniques that attempt to detect adversarial examples, either by training explicit classifiers to do so or by simply formulating "hand-tuned" de- tectors, still largely look to identify and exploit statistical properties of adversarial examples that appear in practice Smith & Gal (2018); Roth et al. (2019). However, to provide fair evalua- tion, a defense must be evaluated under attackers that attempt to fool both the classifier and the detector, while addressing particular characteristics of a given defense, e.g., gradient obfuscation, non non-differentabiiity, randomization, and simplifying the attacker's objective for increased efficiency. non-exhaustive list of recent detection methods entails randomization and sparsity- defenses (Xiao et al., 2019; Roth et al., 2019; Pang et al., 2019b), confidence and uncertainty- based detection (Smith & Gal, 2018; Stutz et al., 2020; Sheikholeslami et al., 2020), transformation- based defenses (Bafna al., 80;8; Yang et al., 2019), ensemble methods (Verma & Swami, 2019; Pang et al,, 2019a), generative adversarial training Yin et al. (2020), and many more. Unfortunately, existing defenses have largely proven to have poor performance against adaptive attacks (Athalye et al., 2018; Tramer et al., 2020), necessitating provable guarantees on detectors as well. Recently Laidlaw & Feizi (2019) have proposed joint training of classifier and detector, however it also does not provided any provable guarantees.
Our contribution. In this work, we propose new method for jointly training a provably robust classifier and detector. Specifically, by introducing an additional "abstain/detection" into classi- fier, we show that the existing certified defense mechanisms can be modified, and by building on the detection capability of the network, classifier can effectively choose to either robustly classify or detect adversarial attacks. We extend the wight- Interval Bound Propagation (IBP) method to account for our new robust objective, enabling verification of the network for provable performance guarantees. Our proposed robust training objective is also effectively upper bounded, enabling its incorporation into the training procedure leading to tight provably robust performance. While tight- ening of the bound propagation may be additionally possible for tighter verification, to the best of our knowledge, our approach is the first method to extend certification techniques by considering detection while providing provable verification. By stabilizing the training, as also used in simi- lar IBP-based methods, experiments on MNIST and CIFAR-I0 empirically show that the proposed method can successfully leverage its detection capability, and improves traditional IBP used in iso- lation, especially for large perturbation sizes.
2 BACKGROUND AND RELATED WORK
Let us consider an L-layer feed-forward neural network, trained for a K-class classification task. Given input x, it will pass through a sequential model, with hy denoting the mapping at layer recursively parameterized by
(1) where (.) is a monotonic activation function, zo denotes the input, and 2, E RK is the pre- activation unnormalized K-dimensional output vector (nz = K and (.) as identity operator),
Zi = (2 or (W 2-1 + bi), I 1. L W. E 1x by E Rd
2

---

Published as a conference paper at ICLR 2021
referred to as the logits. Robust classifiers can be obtained by minimizing the worst-case (adversar- ial) classification loss, formally trained by the following min-max optimization Madry et al. (2017)
minimize
max {(fo(x + +0). (x.D)~/D BEA.
(2)
where 0 denotes network parameters, vector fe(x) = zy is the logit output for input x, {()) is the misclassfication loss, e.g., (.em()) defined the cross-entropy loss, and A. denotes the set of permissible perturbations, e.g., for fe--nomm ball of radius giving A, := {6 | S c)- Although augmenting the training set with adversarial imputs, obtained by approximately solving the inner maximization in Eq. 2, empirically leads to improved adversarial robustness Madry et al. (2017); Shafahi et al. (2019); Wong et al. (2019); Zhang al. (2019), inexact solution of the inner maximization prevents such methods from providing provable guarantees. In critical applications however, provable verification classification accuracy against a given threat model is crucial.
2.1 PERFORMANCE VERIFICATION AND NETWORK RELAXATION
Given imput (x. y), classification network is considered verifiably robust if all of its perturbed variations, that is x + 5 for vg & A., are correctly classified as class y. Such verification can be effectively obtained by
p min 2 where,
Zz {z1 | = (1(2--1); 1=1, L, 20 x + 8, Ag E Ac)
21
where Cy. By e, for i = 1, 2.., K, # y, and e; is the standard 8hh canonical basis vector. If p Vi y. then the classifier is verifiably robust at point (x,y) as this guarantees that 2 S By vi + y for all admissible perturbations 5 E A..
The feasible set Zμ is generally nonconvex, rendering obtaining P; intractable. Any convex relax- ation of 2 however, will provide a lower bound on pf and can be alternatively used for verification. As outlined in Section 1, various relaxation techniques have been proposed in the literature. Specif- ically, IBP (Mirman et al., 2018; Gowal et al., 2018) proceeds by bounding the activation ž of each layer by propagating element wise bounding box using interval arithmetic for networks with monotonic activation functions. Despite its simplicity and relatively small computational complex- ity (computational requirements for bound propagation for given input using IBP is equal two forward passes of the input), it can provide tight bounds once the network is trained accordingly.
Specifically, starting from the input layer 2n. it can be bounded for the perturbation class ō E A, as e1, and 2₁ for the following layers can be bounded
Zo el and Zg
8 + 2 2 a (W,
Z1
2 2-11
(W, Z:
21-1 - 2
W,
W.
2
2
2
2
where is the element-wiss absolute-value operator. The verification problem over the relaxed
feasible set E,. = [2z. EL S Zr.i S Er,s), where 2,. C 2,, then easily solved as
pp min 2,,2,
cyiZt min "r,2, ΣL.W ZL,i- 2LEZG
2.2 ROBUST TRAINING OF VERIFIABLE NETWORKS
It has been shown that convex relaxation of 2, also provide tractable upper bound on the inner maximization in Eq. 2. While this holds for various relaxation techniques, focusing on the IBP let us define
IBP 0 (x, y) = [JBP J
IBP
where
J!BP = min cT,22. a, E,
(5)
with (0, é) implicitly influencing 2, (dropped for brevity), and upperbound the inner-max in Eq. 2
exp(ze) Σ, exp((2))
max
Crem (fo(x 5). S brem( JIBP (x. y). v), Exem exem(z, c) log
dEa.
By using this tractable upper bound of the robust optimization, network can now be trained by minimize
Σ
(1 xrent JBP (x, v),u) + (eo
(x.y)ED
3

---

Published as a conference paper at ICLR 2021
where y trades natural versus robust accuracy, and is scheduled through a ramp-down process to stabilize the training and tightening of IBP Gowal et al. (2018) (where = is selected therein).
3 VERIFIABLE CLASSIFICATION WITH DETECTION
In this paper, we propose a new method for jointly training provably robust classifier and detector. Specifically, let augment the classifier by introducing an additional "abstain/detection". This can be readily done by extending the K K-class classification task to a (K + 1)-class classification, with the (K + 1) class dedicated to the detection task, and the maximum weighted class is finally chosen as the classification output. The classifier is then trained such that adversarial examples, or ideally any other example that the network would misclassify, denoted by a, thus preventing incorrect classification.
classified in this abstain class,
Formally, the classifier can be denoted as in Eq. with the only difference that the final output is K + dimensional, i.e., 2 E RK+1, simply by substituting the last fully-connected weight matrix W of dimension n K with that of dimension nz x (K + 1), and similarly for b
3.1 VERIFICATION PROBLEM FOR CLASSIFICATION WITH ABSTAIN/DETECTION
is desirable to provably verify performance of the joint classification/deeectiin. In contrast to existing robust classifiers, however, on a perturbed image 6, the classification/detcctio task is considered successful if the input is classified either as the correct class y, or as the abstain class a; as both cases prevent misclassification of the adversarially perturbed input as wrong class. On clean natural images however, clasification/ddeection is considered successful only if it is classified as the correct class y, and abstaining considered misclassification.
In order to certify performance in adversarial settings, it is now sufficient to verify that the network satisfies the following for a given input pair (x, y) and d E A, and 1,., K i + y:: max [c,,. _
Vz E Z,, = zr. | (1
1, I., 2o = x + 8, Aō
A
(8)
where cy == ey e, and Ca := e, - e, a denotes the "abstain" class, and the dependence of 2, on (x, U. e, 0) is omitted for brevity. Verification can be done effectively by seeking a counterexample
min max(c], c. 2
If T 2 0 Vi # y. the specification is then satisfied and the performance is verified.
Similar to previous verification methods, to overcome the non-convexity of the optimization in Eq. 9, one can lower bound the problem by expanding the feasible set 2, S 2,, where 2,, is convex, as stated Theorem 1, and proved Appendix A.
Theorem 1: For any convex 2, s.1. Z, C 2r, Eq. 9 can be bounded by the convex relaxation
max min 0 ZE2,
(n.a, + (1 7) Cy.s) S min max (c,, ZE2z
T c,
(10)
Although Theorem holds for any convex relaxation of Zz. for IBP relaxation Gowal et al. (2018) it can be further simplified by substituting intervals through the last layer for tighter bounding, and solved analytically as follows.
Wi b thus not propagating the
Theorem 2: The optimization in Eq. can be lower-bounded by the conver optimization
Jx y) max min 05
(Wi +n w2) ZL-1 W3 w min max T 2, 2,, [I (11)
22-1E21-1
zEZ,
in which w == WIC,, W2 WI,Co,i- Cc,,), w3 bI (Co.i - Cy,,), W4 == b and convex set 21-1 is convex relaxation of Zt,1 the hidden values at L L-1. 1. Furthermore, J((x, y) can be analytically obtained as outlined in Alg.
Note that since lj is the dual variable, any selection within the feasible set serves (looser but valid) lower bound, while the maximization makes the bound tight; see Appendix A.2 and A.3 for proof and a step-by-step algorithm description. Similar to other convex relaxation based verification methods, in order for a networks to provide verifiable performance, one needs to incorporate bound propagation in training.
4

---

Published as a conference paper at ICLR 2021
Algorithm Solution for (x, 2) in Theorem 2
1: Input. Bounds layer L 1 1 8r. I, and weight matrix Wt
2: w1 W Cyy and W2 W L. (Ca. - Cy,t), wi bj, (Ca,, Cy.s), and W4 b Co.i
4: 41 [l o 2 11 (w = 41 (w2 (6-1) Up [lg Song
3: < = (i..... Smy, == /w and vector of indices s that sorts Ç i.e. Son I ...
where operators o and II, denote element-wise multiplication, and permutation according to indices s, respectively.
5: m = m
and M = mays J for j j= RL-1
6: for 0, Ssm Sem+is'' -15M-11 Sens: do Compute
7:
RL-1
g(n)
Σ j=1
(ounnttwwa (ū1.s + nūnj) + 1 lam 220 (ur, + m822)) ) + wa + wi
8: return max g(n) over the computed values.
TRAINING VERIFIABLE ROBUST CLASSIFICATION WITH DETECTION
In order train robust classifier with detection, let start by formalizing the objective of an adversarial attacker. Naturally, an adaptive attacker's objective is to craft perturbation 8 such that simultancously evades detection and causes misclassification. Formally, this can be tackled by seeking 5 such that loss corresponding to the winner of the two classes y and (higher logit leading to smaller cross-entropy loss) is maximized, i...
max min SEA
{ (exem
8), v): exem (fo(x a)
(12)
where Exeme( [z. c) denotes the cross cross-entropy loss for class c = and c = a, and = {,,2, ..., K, denotes the class index set with K + elements.
Let us now define
I, abstain
xx, y/; 0) = max min
{ (xxotr (fo(x + 8), v), bxnnt (So(x (((oxx+)),00 a)
(13)
SEA
in which the inner maximization is closely related to that of the adversarial objective in Eq. 12 with a small difference: loss terms Exentia and Exentky are defined as
exp(zy)
< and (x a) = - log exp(2:)
exp(2a)
Exenti, (z. v) = log Σ
Σ
exp(zi)
(EI)(a)
iET\
This small alteration to the cost, while not changing the minimization "winner" between the true class and rejection class in Eq. 12 and 13, i.e.,
2a S Ey By Zu
lsem (f + v) S Esem (x + 5),a) and (xomra(ff 6).9) S Exour (fo 6),a) lxem [fen(fo(x+ a) < Exaulfo (x 5), y) and (f 6), S (f + 6), v)
favorably influences the training process. That is since, for 8 such that, for instance 2n Zy. minimizing L Labstain (x, y; 0) during training reduces to minimizing &xemt Exent (fo(x + 8). y) which in turn leads to further increasing 2,, while decreasing the logit value =a; and similarly, increasing Zy while decreasing zy if 2y < Za- Intuitively however, the true objective of the classifier augmented with detection on adversarial examples is to increase both 2y and 2 while reducing 2j, Vj a, y; thus preventing any gap in between the boundary of the classes and y, which potentially lead to successful adaptive attacks. Hence, minimizing Eq. 12 would be in contrast with the true underlying objective, and Eq. 13 simply prevents the raised issue.
Upon defining n (x, y; 6) := (xam((f (ff(x), y) and Lrobuut (x, 0) := maxsEa exem (fe(x+ y), then define the overall training loss as
L I Terouust (x, y; 0) + A1 I, robust
(x, y; 0) Xa T (x, y/: 0),
(14)
5

---

Published as a conference paper at ICLR 2021
where Inatural y; 0) captures the misclassification loss of the natural (clean) examples, and Lrobust( y; () denotes that of adversarial examples without considering the rejection class, i.c., sim- ilar to that of Gowal al. (2018), and parameters (Y1, A₂) trade-off clean and adversarial accuracy. To train a robust classifier, we proceed by minimizing the overall loss Eq. 14, by first upperbounding Trohua (x, y: 0) and I. abbttin (x: y; 0).
4.1 UPPERBOUNDING THE TRAINING LOSS
Using Theorem 2, and restricting 0 < 7 1, let us now define "x, y), where trivially
(x.9)
max 0S9S95nS1
(w1 + mpw2) LL-1 + 1 w/ + w1 S (x
(15)
and can also be solved analytically similar to Theorem 2. By generalizing the findings in Wong & Kolter (2018); Mirman et al. (2018), we can upper bound the robust optimization problem using our dual problem in Eq. 15, according to the following Theorem, which we prove in Appendix A.4.
Theorem 3: For any data point (x. y), and e O, and for any S 5 S n S 1, the adversarial loss
I. L.bousin (x, y; 8) in Eq. 13 can be upper bounded by
Labutain
X. y; 0) I L Labutain
(x, y: 0) == Exentraa (- y). Exemt Jr Je y), a)
(16)
where (x, v) is (K + didiensssal vector, valued at index i as [Je,0 B)l = J, (x. v)
Note that maximization over 7) for obtaining J. (x, v) can be done either by bisection (concave mink..
maximization) or by following Alg. I and substituting
and M max
Remark 1. Setting 7 = 1) forces v which reduces J (x, y) in Eq. 15 that in Eq. i.e.
J|BP (x, v) J (x, y)) 1> 0- also bounding loss term Inntural (x y: 0) as
Lyobus (x, X, y: 0) I Lyobus (x, y: 0) == exem ( IBP (x, v).
(17)
Remark While setting = and vi = 1 gives tighter bounds, (and thus used for the verification counterpart in Theorem 2), strictly setting 2 < empirically yields better generalization of the network. This can be intuitively understood by rewriting W1 T W. (n)a., + (1- cy. which is a convex combination of the verification constraints for the correct and the abstain class. Thus 17 + 0 * will lead minimizing a combination of both terms, preventing gaps between the two classes. Also, higher values of ri increase the influence of the term corresponding to the abstain case, and vice versa, whose tuning can promote abstaining by considering how desirable such outcome is (or is not).
Utilizing upperbounds in Eq. 16 and Eq. 17, we can proceed to training the network by minimizing the tractable upperbound on the overall loss
min L min exem (-J (x, v), y) (- v). a) (f
(18)
Note that setting A = 0 and y = X2 and incorporation of a ramp-down process by parameter k as detailed in Section 5 reduces the training in Eq. 18 to that of Gowal et al. (2018) without detection.
Complexity. Since given IBP bounds on 1,, the solution to Eq. 16 is analytically available (that after sorting whose complexity is negligible in comparison with forward pass), computing Eg.. 18 imposes the same computational complexity as in IBP, which is twice the normal training procedure, as it requires propagating the upper and lower bounds via forward pass.
EXPERIMENTS
Empirical performance of the proposed robust classification with detection on MNIST-I0 10 and CIFAR- 10 datasets is reported in this section, and is compared with the state-of-the-art alternatives. The training procedure is stabilized as detailed next
!Code is at htt.ss///gghtib..oooooeeerrerrr/ wi it_
fication_

---

Published as a conference paper at ICLR 2021
5.1 STABILIZING THE TRAINING PROCEDURE
We incorporate the following mechanisms to stabilize the training procedure in tests, where the first two have been previously used in (Gowal ct al., 2018) and (Zhang et al., 2020) as well.
Ramp down of k: To stabilize the trade-off between nominal and verified accuracy, let us introduce parameter x in the overall loss by trading the natural and robust loss as
L = (1-k) (Lrotuss Xx, yi 0) + \₁
abstain robust (x, yr () + K A An (x, y: 0)
(19)
Robust loss
Natural loss
Setting & = 0.5 renders the optimization identical to that in Eq. 18. During the training however, we incorporate a ramp down procedure where k starts at value Kstart = 1, thus training the model to fit
the natural data, and slowly decreasing it to value Kead = 0.5, similar to that in Gowal et al. (2018).
Ramp up of e: It is very important during the training process to start at 0 and gradually increase it to imains while also setting érain larger than Elest can improve generalization.
Ramp down of y and fj: Setting 0 < !! and fj helps with better generalization. Furthermore, setting large 7 and f) promotes the abstain class in loss term Labuain by increasing the weight of w2 in Eq. 15. Thus, we can further stabilize the training process through ramp down procedure where these parameters start at 2 = 1atar and 1) = '/stnt, and are gradually reduced to 7 = Lnnd and ij = /Jend with Dend
Sun and Rend Qaant-
Furthermore, although the term Lioba(X (x, y; 0) could in theory be excluded from the training process, as the term Laaural (x, y; 0) prevents the degenerate solution of always classifying all images in the abstain class, it's inclusion empirically helps the stability of the training process.
5.2 EMPIRICAL RESULTS ON MNIST AND CIFARIO
The classification networks are identical to the large network in Gowal et al. (2018), also detailed in Table trained by minimizing the loss in Eq. 18 with the above stabilizing schemes. Selec- tion of parameters for each datasets is detailed in Appendix B. Since most recent detector networks have shown very low performance against adaptive attacks, and lack provable performance Tramer et al. (2020), we only compare the performance with other provable robust classification methods, while focusing on the different decomposition in the reported natural and robust accuracy among these two. As numbers in Table 1 suggest, the proposed detection/Clasificttion network shows improved robustness against other methods, including IBP in isolation (without the detection capa- bility), specially against larger perturbations in the CIFAR-10 dataset, which intuitively is pleasing: as larger perturbations are naturally more distinguishable, the detection capability of the network is successfully leveraged for improving the adversarial robustness. Let us now take a closer look the performance by focusing on the detection capability.
Effectiveness of the detection class. By nature, the proposed classification "adaptively chooses" between (robust) correct classification and detection of adversarial or difficult inputs during the training. This gives rise to two phenomena:
(1) In verifiably robust methods, natural image accuracy declines as robustness improves. In the pro- posed approach however, considerable number of misclassified natural inputs are in fact abstained which in certain applications is more favorable than assigning them to a wrong class, as classi- fiers without detection capability would: compare 30.5% abstain and 25.6% 'wrong-class misclassi- fication' (other than abstain and the correct class) in withedth-etttctoon with that of 53.7% 'wrong- class' misclassification in IBP on natural CIFAR-10 10 images in networks trained for e = 8/255.
(2) Regardless of the training procedure, the proposed classifier with detection can still be verified using verification in Eq. 4 to obtain its guaranteed robustness with only considering the correct class. Thus, comparing this verification percentage with that of Eq. 11 highlights the effectiveness of the abstain class in detecting perturbed images and increasing robustness: for instance, using method 76.07% maximum robust error successfully decreases to 63.63% by considering the detection capability, on CIFAR-10 trained for e = 8/255, compared to 69.92% in IBP without detection.
7

---

Published as a conference paper at ICLR 2021
dataset
atlack
method
standard err
verified err
Srgd-attac--suooo
IBP
2.12
8.47
6.78
TRP w/ dotection
4.34
5.98
4.15
0.3
Best recorded in literature
Crnis
(Gowal et 2018)
1.66
8.21
IBP-CROWN (Zhang et al,, 2020)
1.82
7,02
6.05
Xiso al. (2018)
2.67
MNIST
Miman ot al. (2019)
2.8
11.2
4.6
Balunovic Vechev (2020)
2.7
14.3
Wong Kolter (2018)
14.87
43.10
IPP
2.74
14,80
11.14
Sapt
11.29
0.4
Best recorded in literature
(Gowal 2018)
1.66
15.01
IBP-CROWN (Zhang et al. 2020)
2.17
12.06
9.47
38.34
55.21
ISP w/ detection
34,66
57.9
47.2
Best recorded in literature
Cue 2/255
(Gowal et 2018)
29.80 99.84
2.2/255
IBP-CROWN (Zhang et al., 2020)
28.48
46.03
40.28
Vechev (2020)
21.6
Miman et al. (2018)
38.0
47.8
Wong Kolter (2018)
31.72
46.11
Xiao al. (2018)
38.88
54.07
50.08
I8P
33.69
69 92
63.17
CIFAR-10 10
Best recorded in literature
Fiest 8/255
(Gowal 2018)
8.8/205
IBP-CROWN (Zhang et al,, 2020)
54.02
66,
65,42
Mirman et (2019)
43.8
72.8
65.3
Balumovic Vechev (2020)
48.3
72.5
Xiso al. (2018)
59.55
79.73
73.22
Wong Kolter (2018)
IBP
68.97
78.12
76.66
Flot 16/255
detection
66.37
67.92
16.7/255
Best recorded in literature
IBP-CROWN (Zhang et al., 2020)
66.06
76.80
75.23
Table 1: The verified, standard (clean), and PGD attack errors for models trained on MNIST and CIFAR- 10. IBP with detection is compared with IBP (without detection capability) emphasize the cessful utilization the detection capability of the network increasing verifiable as well as empirical performance. For more detailed decomposition of the standard and robust error terms see Fig. 1.
As reported in Zhang et al. (2020), achieving the 68 444 IBP verified error requires extra PGD adversarial training loss, without which the verified error 72.91% (LP/MIP verified) or 73.52% (IBP verified), thus our result should compared 73.52%.
Best reported numbers for IBP are computed using mixed integer programming (MIP), which are strictly smaller than IBP veified error rates, see table 3 and in Gowal et al. (2018). For fair comparison, we report IBP verified error rates from table 3 therein.
** Best reported results from the literature may different network architectures, and empirical PGD erorr rate may have been computed under different settings, e.g., number of steps and restarts.
*** Number in the IBP rows in this table are the best between (Zhang ct al., 2020) and our experiments. while results from (Gowal et al., 2018) are reported under best literature record for IBP.
It important note that unlike robust classification, the proposed joint classificatonn/detettinn does successfully leverage the detection capability decrease the verified error rate rejecting some adversar- examples, which makes direct comparison these values difficult. However since there exists no other verifiable detection scheme, such comparison is made here to show the effect of successful detection; see Figure I for a detailed discussion on this.
See Fig. for decomposition of the performance metrics of the proposed network CIFAR-10 dataset, demonstrating the effectiveness of the abstain class in detecting "difficult" natural images while also increasing the robustness certificate over adversarial inputs.
5.3 NATURAL VERSUS ADVERSARIAL ERROR TRADEOFF
Reporting single point in the Pareto Frontier reported in Table gives limited understanding on how different methods trade off natural versus robust error. To address this, a more detailed study on this trade-off in based robust classification with and without detection is discissed here.
In order to get the best performance for IBP-based robust training without detection (that λ = 0), and since it is not known whether varying Kend X2 will lead to a better performance, have
8

---

Published as conference paper at ICLR 2021
12
Detection IBP IBP Detection
16/255 robust class, wi detection
conrect class.
abstain
miscussification
robust class,
nen-veriffed
Accuracy on natural (clean) images
Verified accuracy adversarial images
Figure 1: Decomposition of accuracy and verified accuracy CIFAR-10 dataste: the detection capability of the network can increase robustness by adaptively abstaining on adversarial inputs while also abstaining on some natural images rather than misclassifying them.
0.75
0.80
0.70
robust error
0.75
robust error
0.80
0.65
0.75
robust
0.60
0.60
0.70
0.55
0.55
0.60
0.50
0.55
0.60
natural error
natural error
natural error
IBP IA, 0), varying
IBP (A, 0), varying Kand
w/ detection (A, 1), varying A
(a) CIFAR-10, 8/255
CIFAR-10. 12/255
(c) CIFAR-I0, 16/255
Figure 2: Naural versus robust етгоr tradeoff for IBP (A₁ 0) and IBP-witt-detection (Λ₁ > 0) on CIFAR-10 dataset for various perturbation sizes = 8/255, 12 12/255, 16/25 /55 Lower curve is better. IBP-with-detection is effectively utilizing its detection capability to adaptively trade natural
and robust performance, leading to improved certified robustness against adversarial perturbations.
trained the classification networks in two ways: (1) setting find and varying A2 E [o, 3). and (2) setting 2 = 1 and varying Kend E [0, 0.5). to get multiple set points along the Pareto Frontier.
Similarly, for Sug-wwith-deteetion-beeee classification, we have set Kend = 0.5 À = 0.6, 0.8. 1.0 for MNIST and A 1.0 for CIFAR-10, and varied A2 E 4] to get various points along the frontier. The network trained for various e values, with other training parameters as stated Appendix B.
Results are plotted in Fig. 2 and 3 (presented in the Appendix due to space limitation). As shown, the classifier enhanced with detection capability is better able to trade natural and robust accuracy, thus attaining higher robustness by trading small decrease in natural accuracy. This together with the fact that the natural accuracy decrease is also partly handled by abstaining of such natural im- ages that would have been misclassified (as of the original K classes) otherwise, demonstrates the effective utilization of the detection capability in the proposed method. It is important to note that IBP w/detection allows us obtain additional regions this Pareto frontier that traditional- robust-classifiers without detection cannot obtain, and could potentially provide additional gain to what is achievable by other various improvement techniques such as tighter relaxation and bound propagation methods.
CONCLUSION
We proposed a new method for jointly training a provably robust classifier and detector. By intro- ducing additional "abstain/detection" into a classifier, we have proposed verification scheme for classifiers with detection under adversarial settings, and shown that such networks can be efficiently trained be extending the common IBP relaxation techniques. The effectiveness of the proposed de- tection scheme with provable guarantees versus SOTA robust verifiable classification methods is corroborated by empirical tests MNIST and CIFAR-10, specially against large perturbations.

---

Published as a conference paper at ICLR 2021
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses adversarial examples. Proceedings of Machine Learning Research, pp. 274-283, PMLR, 10-15 Jul 2018.
Mitali Bafna, Jack Murtagh, and Nikhil Vyas. Thwarting adversarial examples: An Ig-robust sparse Fourier transform. In Advances in Neural Information Processing Systems, pp. 10075-10085, 2018.
Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2020.
Julian Bitterwolf, Alexander Meinke, and Matthias Hein. Certifiably adversarially robust detection of out-of-distribution data. In Advances in Neural Information Processing Systems, volume 33, pp. 16085-160955 2020.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI, volume 1, pp. 550-559, 2018.
Ruediger Ehlers. Formal verification of piece-wiss wise linear feed-forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269-286. Springer, 2017.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems 32, pp. 11427-11438 2019.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint (tti::1810.127777 2018.
Cassidy Laidlaw and Soheil Feizi. Playing it safe: Adversarial robustness with an abstain option. arXiv preprint arXiv:1911.1122 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. ICLR, 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3578-3586, 2018.
Matthew Mirman, Gagandeep Singh, and Martin Vechev. A provable defense for deep residual networks. arXiv preprint arXiv: 1903. 12519, 2019.
Tianyu Pang, Kun Xu, Chao Du Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity. In International Conference on Machine Learning, pp. 4970-4979, 2019a.
Tianyu Pang. Kun Xu, and Jun Zhu. Mixup inference: Better exploiting mixup to defend adversarial attacks. In International Conference on Learning Representations, 2019b.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. ICLR, 2018
Kevin Roth, Yannic Kilcher, and Thomas Hofmann. The odds are odd: A statistical test for detecting adversarial examples. In International Conference on Machine Learning, pp. 5498 0008-55077700 2019.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. Advances in Neural Information Processing Systems 32, pp. 9835-9846, 2019.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In Advances in Neural Information Processing Systems, pp. 3358-3369, 2019.
10

---

Published as a conference paper at ICLR 2021
Fatemeh Sheikholeslami, Swayambhoo Jain, and Georgios B Giannakis. Minimum uncertainty based detection of adversaries in deep neural networks. In Information Theory and Applications Workshop (ITA). IEEE, 2020.
Lewis Smith and Yarin Gal. Understanding measures of uncertainty for adversarial example detec- 08533, 2018.
tion. arXiv preprini
David Stutz, Matthias Hein, and Bernt Schiele. Confidence-calirraie adversarial training: Gener- alizing unseen attacks. International Conference on Machine Learning, 2020.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. ICLR, 2017.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint arXiv:2002.083347, 2020.
Gunjan Verma and Ananthram Swami. Error correcting output codes improve probability estimation and adversarial robustness of deep neural networks. In Advances Neural Information Process- ing Systems, pp. $643-8653. 2019.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. volume 80 of Proceedings of Machine Learning Research, pp. 5295- PMLR, 10-15 Jul 2018.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2019.
Chang Xiao, Peilin Zhong, and Changxi Zheng. Resisting adversarial attacks by k-winners-takk-all.
arXiv preprint arXiv: 1905 10510, 2019.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Mahi Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. In International Conference on Learning Representations, 2018.
Yuzhe Yang, Guo Zhang, Dina Katabi, and Zhi Xu. Mc-net: Towards effective adversarial robustness with matrix estimation. In International Conference on Machine Learning, pp. 7025-7034, 2019.
Xuwang Yin, Soheil Kolouri, and Gustavo Rohde. Gat Generative adversarial training for ad-
versarial example detection and robust classification. In International Conference on Learning Representations, 2020.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, 2019.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference Learning Representations, 2020.

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 PROOF OF THEOREM 1
Since z & trivially holds that
min z
max max(Cy) -0 S min zE2r.
m 2)
(20)
The lower bound is now a convex minimization, which can be rewritten as
min zE2,
max 2, c
min T2
t.
2 ST 2
Defining the slack variables 1/a 2 0 and fl 0 for the inequality constraints, the Lagrangian can be written as
[(T, 2, Bay M1) = r + na (C -) mo (,,
and minimizing C(T, 2, Nay myy) with respect to the primal variable yields Tha + fly = 1. Defining ?) = 1/a Nu and using the fact that the dual maximization always serves as lower bound on the primal we get
max OS 2EL
min
(n.o. + (1- cy.))
S
min xEZ
max CI, 2]
A.2 PROOF THEOREM 2
Following on the statement of Theorem I and by substituting WI PL, we get
max 0S
min = E2
(1 (nc,,t(11 cy.)))
(WT.ZI--tb) S
min 2E21
maxfc, y. c[,z] (21)
which can be reordered
max 0S Eg
min
(w) + m722)) 21,-1 +1 w/
(22)
where W1 := W.C,, W2 = WL(Cu, - Cy.s), Wy == by. (ca.i - Cy.s). and wa = by, Cy. which
then equals
max 05
(wi + mwr)) 2 + r) W's + w4
(23)
where minimization w.r.t ZL-1 solved by the (this is under the setting for most networks with positive activations, and thus lower bound z is always non-negative)
2 1ls
if
( mwll) S 0
(24)
2
ils
(m) + mowees 2 0
and can be rewritten as
Σ
wi [1
(uunstnee, 101162-115 +1 1wi, tnwn, 200 201 tn wes (25)
USA$1
and can be rewritten as
( (en ZL-1 + mol2 o 11 + (wn +ww (wi 2z-1 w2 Zr 11g
max 05551
1=1
+ W3 w/
(26)
where "o" denotes the elementwise multiplication. Thus, due the concavity of the dual, optimal 7 can be found by evaluationg the objective in between the break points which are given by Ç := (G,,.., Sar.--S-r-. Srz-zl with its j-th element defined Gj := -w1./W2.j-
12

---

Published as a conference paper at ICLR 2021
To do this, let to denote the n2 az-ary tuple of indices that sorts Ç. That is
= (. == (C) := IGm, Sany. s.t. Sa1
Song.-1
with operator (.) denoting the permutation of its arguments according to such that Ci = So, Vi, and Ç is sorted in the increasing order
We can also rewrite the problem by summing over the indices in the sorting set instead, as
R4-1
max 0SAS1
Σ
[eenstre Sot o 2 + n/w o Zb-11a, +
o Z + w2 Z 2L-118;
j=1
+ 17 Wy + w4.
(27)
Now let us define u, == [1o(w1 z1,-)), in IIg(w1 ZL-1), u2 ll z1.-1) 02 IIg (w2 o 1L-1), we get
n2-1
Σ
( (nss and wa.s 20) (n22t) and wa.., <0> (#i.) + nū2.s)
max 0S5S1
j=1
1 { fn2zs and waing 203 or (rSs and waing flo (Mis + muzs)
+ W3 + W4.
(28)
In order to break the objective of maximization into piece-wise linear programming subproblems, let us first identify the (indices of) Ca, values that fall the feasible set S v S by
min and
M
max SapS1
2op20
The overall maximization can now be reduced to piece-wise subproblems over sets &o S 1) S Eutz for < M as
nz Σ
max
(nSt and w2.s, 20) (1125 and w2.sg <0) (ūI, nu22))
max(0.E.>$5 (1,
j=1
1
(n25) and wa,n, 203 or (nss, and wa,e, 201} (uis m22,))
+ 17 W3 + w/.
(29)
Since each of these subproblems are maximized at the boundaries of the feasible sets, the overall maximization essentially reduces to evaluation of the following objective function at (M m 3)
points 7) = 0, Ems Sm+1s' ... SM-1.
[(mr (ū1,j muu25)) touz, 203 (uI + mle.)) )
((1) = Σ J=1
+ W3 wa
Values g(n) can be efficiently computed by a forward cumulative sum and forward-backward cumulative sum of u, and un and ūg thus imposing the overall complexity which is dominated by the sorting at O( log(nL-1)) in an efficient implementation.
A.3 DESCRIPTION OF ALGORITHM 1
Here a step-by-step walk-through for Algorithm 1, with insight on how these steps performed.
1. Form vectors w1 and w2, which are the last layer values wi W W.Gyi W2
W WC(Ca, Cy,)) Wa bJ (Ca.i Cys), and wa bā Cy.i.
13

---

Published as a conference paper at ICLR 2021
2. Define < (ns....nn.!
ww//wy and get the vector of indices that sorts it, i.e,
Se, S ... S Seng-1
3. Form the element-wiss product of (W1, w2) with (Zt-1- ZL 1)), and sort them according to the index set s.
( ū = [w,(w) ož, 1), u2 == (w oz U2 == (
4. Get the lowest and highest indexes (m, M) such that the sorted Ç vector value at those indices are in the feasible set, between 0 and I.
5. Iterate over the feasible values of 0, Sam Somp11" San 11 snnr 1 and compute the corresponding objective values
カ6-1
((n)
Σ
(1un.) 5o) (ū1, + nu22))) + [wr tu2, (11 m222)
f=1
17 Wg + w1
6. Return the maximum value of g(7) over the evaluated points.
A.4 PROOF OF THEOREM 3
Let us start by splitting the feasible set into disjoint sets of
2 = (21-1 2L-1,a 2 21,,,,), and 2% == (21-11 21-1,a < 11-1,
where
2 = 22-1=2%-1 U 24-1, and 2/ n 2 -0
Proof is carried out by considering z 24_1 and z E 2 - separately.
Restricting 2 we have (remi + 8),1)
< la &xe (fo 8), a) which leads to
I absttain X, y: 0) max min { (fxent; (fo(x + 5). exon (f + 5).
(30)
SEA
<
Exentia (ZL, s.t. 21 W W1 bt
(31)
21.-1
Loss function a is the cross entropy loss defined on the K-dimensional vector [zr,1, _r., and class y, and thus following Wong & Kolter (2018) given its transnational invariance equals
max Exomt, (ZL, = max a - 2,, s.t. Φy = WT, 11, + by (32) 21-1122
21.-1E2
with 1 denoting the (K + -)ddimensional vector of all ones. Given the invariance of Exenti with respect to 21,a, it can finally be upperbounded by taking the upperbound for all indices where i = 1,.... K # a, and lowerbound at index = y. Note that for i = y. value [z] - 2L 11: = O,
and lower bound other entries .... K, of a, y can be obtained by
L LL max 21,s 2L,0 m1T}
max(c_], c2,22)
(33)
< min max max(cc), [c CT, ) S -J((x.)) - -J (x, 2.
(34)
where the first equality holds since 2 (21-1 2L-1,a 21,11.9 for 2 second inequality is due to Theorrm 2, and third inequality is given by Eq. 15.
Thus, for z E By the loss term is now upperbounded by
I robuust (x, y: 0) < Ementral (-Je
where
0 if
i a.
[ Je,0(x y)};
J (x,y)
(35)
otherwise.
14

---

Published as a conference paper at ICLR 2021
Network layers
Conv 64 3
Conv 64 3 x + 1
Conv 128 3 +
Conv 128 x 3 +
Conv 128 3
Fully Conn. 512
# hidden 230K
# params. 17M
Table 2: Network architecture. Similar to the Large network used in (Gowal et al., 2018)
Similarly, it can be shown that for Thus, for E 2g,-1 the loss term is now upperbounded by
L Lobbust (x, 0) S Exxaatt (-Je, (x,
The equality of by (x,,))),,,))) (-Je,)a--Je,x,,,, ()) trivially follows from the fact that [J, y)li 0 for i a, y.
(-Je,,
Thus, since ÊL-1 = - U 2 the proof is complete.
B APPENDIX: EXPERIMENT SET UP
Training parameters and schedules are similar to (Gowal et al., 2018) and (Zhang et al., 2020), and outlined in detail here. For training the classifier network with architecture given in Table 2, for both datasets, Adam optimizer with learning rate of 5 x 10-4 is used. Unless stated differently, which after a warm-up perio,d is ramped down to value Kend 0.5. Value of during the training is also simultaneously scheduled by linear ramp-up, starting at O, and ramped up to the final value of Grain reported in Tabel 1, and networks are trained with single NVIDIA Tesla V100S GPU.
scheduled by a linear ramp-down process. starting
For MNIST, the network is trained in 100 epochs with batchsize of 100 (total of 60K steps). A warm up period epochs (2K steps) used (normal classification training with no robust loss), followed up by a ramp-up duration of 18 epochs (10K steps), and the learning rate is decayed x10 at epochs 25 and 42. No data augmentation used. Furthermore, fixed selection of rj 0.9 and 7 0.1 during training is used for this dataset with no ramp-down. Reported numbers in Table corresponds to and λ 0.6 and A2 1 for 0.4 respectively.
and X2 for 0.3,
For CIFAR1O, the network is trained in 3200 epochs with batchsize of 1600 (total of 100K steps). A warm up period of 320 epochs (10K steps) is used (normal classification training with robust loss), followed up by ramp-up duration of 1600 epochs (50K steps), and the learning rate is decayed x x10 at epochs 2600 and 3040 (60k and 90K steps). Random translations and flips. and normalization of each image channel (using the channel statistics from the train set) is used during training. Furthermore, during training for all values we have selected 7 1.0 and Nmd = 0.9. Additionally, Nond 0.1 used during training, with 7 = 0.1 for ε = 2/255 (no ramp down), N 0.3 for e = 8/255, N = 0.4 for = 12/255, and 17 17 0.5 for 16/255. The intuition behind these parameters selection lies in Remark 2, as large v values promote the abstain option more, so for large e, we start with larger 7 as well. Reported numbers Tabel correspond to \ for all values, and À2 = 3.0 for e = 2/255, X2 = 2.9 for = 8/255, and À = 3.1 for 16/255 to insure similar natural accuracy for fair comparison against other methods.
15

---

Published as a conference paper at ICLR 2021
0.11
0.2
IBP, Varying Host
IBP, Varying Hart
IPP, Varying A:
IBP, Verying As
Varying
Az= Varying
rebuse a7o-
A1mB Verying A:
amr-
Aymo B, Varying 2:
0.14
0.28
Ap=1. Varying A
Ag Varying
0.77
0.39
0.52
0.00
085
0.02
0.00
0.2
0.04
0.08
0.08
0.2
natural
natural
(a) MNIST 0.3
(h) MNIST =
Figure 3: Naural versus robust eπror tradeoff for IBP (Λ1 0) and IBP-with-detectton (A1 0) on MNIST dataset for various perturbation sizes e = 0.3 and e = 0.4. Points closer to the origin are better. -ettddet-ettttt is effectively utilizing its detection capability to adaptively trade natural and robust performance, leading to improved certified robustness against adversarial perturbations.
B. PARETO FRONTIER FOR MNIST DATASET
B.2 EMPIRICAL ATTACK SUCCESS RATE USING PGD ATTACKS
In order to obtain empirical attack success on the trained networks, adversarial perturbations are sought by solving
max REA.
max Zr,a max Zr.a Eyla.y
(36)
This attack is indeed an adaptive attack as aims at cireumventing the detection while trying to cause misclassification (Tramer et al., 2020). Perturbations sought by maximizing this objective using PGD with 200-steps for mnist and 500-steps for CIFAR- 10 Madry et al. (2017), with 10 random restarts. It is interesting note that the achieved attack success rate in Table 1 is well below the verified robust error, further implying the effectiveness of incorporation the detection mechanism the true robustness of the system against practical adaptive PGD attacks are considerably stronger in comparison to robust classification without detection.
16


Reviews:
[{"review_id": "i4E_W_D9Usw", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary: \n\nIn this paper, the authors propose an additional \"abstain/detection\" loss term into training, so that the classifier can either robustly classify or detect an adversarial attack. They extend the interval bound propagation method for certified robustness under L_infity perturbations (a simple bounding in changes of the weight after each NN layer application, using a box constraint). Hyperparameters in the objective trade-off between clean and adversarial accuracy. \n\n##########################################################################\n\nReasons for score: \n \nOverall, I think the paper is borderline. I like the idea of adding an \"abstain\" error term in the loss during training, and I like that the authors have derived some (simple) bounds on the min-max formulations. They show some benefit of addition of abstain/detection in the training. However, my major concern is that if these results could also be obtained without adding these losses in the objective, but by simply comparing \"closeness\" or confusion in the class labels from the classifier, and abstaining from classification as a post-processing step instead. What is the benefit of adding this to the training? \n \n##########################################################################\n\nPros: \n\nThe authors are trying to break the loop of adversarial training and subsequent adaptive attacks, by developing \"provably robust\" methods.\n\nThe idea of incorporating an \"abstain\" loss term at the training stage, and trading it off with the true error in classification is interesting. They further modify the loss slightly to exclude true and abstain classes (perhaps, driven by experiments). \n\nThey obtain (simple) convex upper bounds on the loss functions and minimize these. \n\n##########################################################################\n\nCons: \n\n1. Choice of the loss functions: why the specific choice? Loss for misusing abstain class or mislabeling the true label could be something more general. \n\n2. Choice of hyperparameters: How does one select \\lamba_1 and \\lambda_2 in practice? The authors mention a few practical ways (also used by authors in related works), e.g., ramp down of \\kappa etc. Why are these good choices?\n\n3. Clarity in the writing: The paper is unclear at many places- for example, it is nowhere mentioned that the maximum weighted class is finally chosen, and the interval bounds are not propagated at this last layer. Algorithm 1 is explained nowhere in the paper, except in a psuedocode. \n\n4. Can similar benefits in adversarial robustness be obtained by post-processing an adversarially trained model?\n \n##########################################################################\n\nQuestions during rebuttal period: \n\n \nPlease address and clarify the cons above \n\n \n#########################################################################\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YgcSXc58qUv", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new defense method based on adding a reject class to a classifier trained for robust classification. The paper has merits, it is formally sound and it improves the SOA. However, my rating is not so high for the following reasons:\n\n- Only a short paragraph at the end is devoted to the natural-vs-robust error trade-off and the comparison is done only with IBP (another defense method of 2018). In my opinion this important trade-off is being neglected. What is the point of developing classifiers that are robust to AEs when they are not robust to other normal images (like those found in the test set)?\n- Adding a reject class may not seem fair. Particularly, the paper states (p.4) \"the classification/detection tasks is considered successful if the input is classified either as the correct class y or as the abstain class a; as both cases prevent misclassification of the adversarially perturbed input as a wrong class\". I do not agree with that; it should be considered successful only if the input is classified as the correct class y, period. The \"abstain\" class is just a reject option, which is not the same as the correct classification. One can always resort to rejection to improve the error rate in the non-rejected part of the dataset. When there is a reject option in the system the figure of merit should be the ratio between error and rejection rate, while in your case you are using only error as the figure of merit. What would be the error-reject trade-off curve of the base classifier in these same datasets? \n\nAlso, I could not understand the relative weights lambda 1 and 2 in Eq. 14. Are they correct? shouldn't there be a weight also for the first term Lrobust? Likewise in Eq. 18 you state that for lambda1=0 the training reduces to that of Gowal but the weight terms are different in Eqs. 18 and 7.\n\nMinor: \n- When referencing an equation you should capitalise the first letter E. \n- \"plotted in 2\"\n- \"network can increase robust\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "T1D_1ORLowe", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to train networks that can map a possibly $\\ell_\\infty$-perturbed input to its class provably or map this input to the “abstain class” provably. This is achieved by training on the IBP output boxes together with a new loss function. The method diverts from the classical setting in which the classifier needs to be robust, by allowing the classifier to abstain. While this is an interesting idea, the paper seems to be rushed and not carefully written. The notation could be improved and presentation could be simplified. It seems as if the results from related work (Balunovic et. al. [3] and Mirman et. al. [4]) are missing in Table 1 and thus are not compared against. Further, some questions remain open after reading the paper:\n\nQuestions:\n- Would the idea to have an explicit “abstain” together with the loss function work also for randomized smoothing [1]? How would the results look like?\n- Have you tried to use certification methods using tighter relaxations like k-ReLU[2]?\n- In Equation 8: Is this here for all $i$?\n- How would your method perform when using COLT [3]?\n\nComments:\n- in equation 3, it seems to me as if the second ‘+’ for $\\underline{z}_l$ should be a ‘-’, similar for $\\overline{z}_l$\n- in equation 6: $\\ell_{\\text{xent}}$ should be defined before used\n\nThe comparison in the evaluation is not complete, questions remain open after reading the paper and evaluation is missing, hence this is a reject for me. \n\n\n[1] Cohen et. al.: 'Certified Adversarial Robustness via Randomized Smoothing'. http://proceedings.mlr.press/v97/cohen19c/cohen19c.pdf\n\n[2] Singh et. al.: 'Beyond the Single Neuron Convex Barrier for Neural Network Certification'. http://papers.nips.cc/paper/9646-beyond-the-single-neuron-convex-barrier-for-neural-network-certification.pdf\n\n[3] Balunovic et. al.: 'Adversarial Training and Provable Defenses: Bridging the Gap'. https://openreview.net/pdf?id=SJxSDxrKDr\n\n[4] Mirman et. al.: 'A Provable Defense for Deep Residual Networks'. https://arxiv.org/pdf/1903.12519.pdf\n\n######################\n\nAfter reading the author's response: While i still think that extending the experimental evaluation along the axes described above would improve this work, i decided to raise my score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "NFmWJwr9LP4", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThis paper deals with the problem of bounding the amount of errors that a model can make when attacked by an adversary limited to small perturbation of an input image. Similarly to previous paper, it proposes to extend the classifier with a detector to identify adversarial examples. As opposed to previous papers, the authors suggest to perform formal verification to prove that the samples are either robustly classified or abstained on (as opposed to testing the classifier + detector adversarially which would have left open the question of whether or not the attack against the pair was done in an adequate way). The method used for this is based on the simple IBP algorithm but the authors propose a proper encoding of the max(abstain_logit, gt_logit). They also follow the IBP strategy of using the bound resulting from verification as part of the training objective in order to encourage the network to behave properly.\nExperimental results are reported on MNIST and CIFAR-10, and shows that there are scenarios in which the behaviour caused by this algorithm might be desirable.The experimental protocol for training network with the proposed method is described in significant amount of details and it should be possible to reproduce experimental results based on the description.\n\nThe crux of the paper lies in redefining the way accuracy should be computed in the case of an abstain option and adjusting verification and robust training methodologies for it. The accuracy is computed in the following way:\n* For natural images, the prediction is considered correct only if the output is the correct class.\n* For perturbed image, the prediction can be either the correct class OR the abstain class.\nThis might be sensible, but unless I'm mistaken, this could lead to degenerate cases where the network could achieve a verified error of 0 while having a standard error of 100% (see below). It's regrettable that we lose the property of the verified error rate being an upper bound on the standard error rate.\n\nIf I'm not mistaken, the results in Table 1 are hard to evaluate because the methods proposed by the authors is the only one that considers an abstain class, which gives it leeway to \"cheat\". A pathological example of this would be a network always outputting \"abstain\". If I understand correctly, it would be classified as having 0% verified error, while having 100% standard error. A moderate version of this is what can be observed for all the pairs (except CIFAR10-eps=16) : standard error goes up compared to IBP while verified error goes down. \nFigure 1. is however quite helpful in showing that there might be some benefit in the proposed approach if the goal of an application leans more towards \"Never making bad predicitions\" rather than \"Always making good predicitions\".\n\nComments:\n- I am not entirely sure of the premise of the papers that \"adversarial examples is something that we can defend against\". I am not convinced that people are worried about an attacker crafting attacks to fool their classifier. The problem is that we want our classifiers to be robust to small perturbation, because that's a desirable property and adversarial examples is a sign that this property is not met. \n\nThere might be some potential extension to this paper in the direction of OOD detection. Out of Distribution examples tend to make the classifier perform poorly. There is also a glut of methods that claims to be able to detect out of distribution examples without any formal guarantees so I would encourage the authors to look in that direction for extensions to their work.\n\nOpinion: The paper is quite interesting to read, and as far as I can tell is the first one to apply verification methods to the detection of adversarial examples. This is a welcome contribution as opposed to all the methods that claim to detect attacks but can not provide any guarantees.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of certified adversarial robustness when the classifier has a reject option (realized here as an additional class) where the certification is done by adapting IBP-techniques to this particular problem setting.

Pro: As previous approaches to adversarial robustness with reject option have often be shown to be non-robust as one could circumvent both detector and classifier simultaneously with an adaptive attack, the idea to do this instead with a certified approach is interesting and could potentially initiate more research in this direction.

Con: 
- The approach seems to some extent trade-off robust error with normal error which seems in particular true for MNIST where a stronger loss in normal error is less acceptable. 

Comments:
- One reviewer mentioned that such a certified approach could be interesting for OOD detection. This has been done recently in:
Julian Bitterwolf, Alexander Meinke, Matthias Hein
Certifiably Adversarially Robust Detection of Out-of-Distribution Data, NeurIPS 2020
which should be cited in the present paper.
- While the empirical PGD-attacks done in this paper are strong, sometimes PGD fails due to gradient obfuscation, I would thus recommend to use additionally a black box attack or the recent AutoAttack.

Decision: Accept (Poster)