Degradation Attacks on Certifiably Robust Neural Networks
Authors: Klas Leino
Chi Zhang
Ravi Mangal
Matt Fredrikson
Bryan Parno
Corina Pasareanu
Venue: ICLR 2022 Submitted (2022)
Keywords: adversarial examples
certified defenses
degradation attacks

Abstract: Certifiably robust neural networks employ provable run-time defenses against adversarial examples by checking if the model is locally robust at the input under evaluation. We show through examples and experiments that these defenses are inherently over-cautious. Specifically, they flag inputs for which local robustness checks fail, but yet that are not adversarial; i.e., they are classified consistently with all valid inputs within a distance of $\epsilon$. As a result, while a norm-bounded adversary cannot change the classification of an input, it can use norm-bounded changes to degrade the utility of certifiably robust networks by forcing them to reject otherwise correctly classifiable inputs. We empirically demonstrate the efficacy of such attacks against state-of-the-art certifiable defenses.

Under review as a conference paper at ICLR 2022
DEGRADATION ATTACKS ON CERTIFIABLY ROBUST NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Certifiably robust neural networks employ provable run-time defenses against adversar- ial examples by checking if the model is locally robust the input under evaluation. We show through examples and experiments that these defenses are inherently over-cautioun Specifically, they flag inputs for which local robustness checks fail, but yet that are not adversarial; i.e., they are classified consistently with all valid inputs within a distance of 6. As a result, while norm-bounded adversary cannot change the classification of an input, it can use norm-bounded changes to degrade the utility of certifiably robust net- works by forcing them reject otherwise correctly classifiable inputs. We empirically demonstrate the efficacy of such attacks against state of-the-art certifiable defenses.
INTRODUCTION
An adversarial example for neural classifier is the result of applying small modifications correctly classified valid input such that the modified input is classified incorrectly. For neural classifiers trained in standard manner, it has been shown that adversarial examples are rampant (Szegedy et al.) 2014 Carlini & Waagner 2017). While training models in an adversarially-awan manner helps mitigate the issue to an extent, it does not solve the problem, as evidenced by the large gaps between the clean accuracy and verified robust accuracy" of models.
Certifiably robust classifiers (Weng et al. 2018 Wong al. 2018 Cohen et al. 2019 Leino 202
offer the most rigorous solution to the problem and provably protect models against adversarial attacks. These classifiers are constructed by composing a standard classifier with certified run-time defense. The defenses aim to detect adversarial examples during model evaluation, by checking if the model is e-locally robust at the evaluated imput. If the check fails, the input is flagged as (potentially) adversarial and the model rejects the input. However, rejection is not free of cost. Every time the model rejects input, a user of the model has to resort to some other process other than their presumed first choice (the defended model) to make a prediction, reducing model utility.
We show that existing certified run-time defenses are overly cautious and susceptible to erroneously flagging non-adversarial inputs adversarial. This over-cautiousness is inherent in the design of such defenses, and it is manifested even when the e-local robustness check is exact (i.e., the defense is complete). Not only does this lead to degradation in model utility because of unnecessary rejections, but it also exposes models to a new line of attack that we refer to as degradation altacks. We develop new attacks that are aimed at causing certifiably robust classifiers to reject inputs frequently, and we show that this is a significant problem in practice. For state-of of-thc-art certifiably robust models, such as GloRo Nets (einoo et al. 202T) and randomized smoothed models (Cohen et al. 2019), our attacks succeed on as many as 56% of the inputs where the model is already known to be robust. This is particularly distressing given the already considerable computational costs of training and defending certifiably robust models.
As concrete scenario, consider autonomous driving system that uses neural classifier for labeling road signs. It is unsafe for the classifier to misclassify adversarially perturbed road signs, and we want to prevent this at all costs. One simple strategy is for the classifier to always reject inputs and hand over decision decision-making making to the human driver. This is perfectly safe behavior, but this model has zero utility. Ideally, want the model to hand over control (i.c., the run-time defense should raise flag) only when the perturbed example is actually going to cause misclassificatti Our result implies that an adversary can cause the model to hand over control to the human driver even when perturbed input would not have
%% of test inputs where the model accurate and also locally robust

---

Under review as a conference paper at ICLR 2022
been misclassified. Although this does not happen for all the inputs (as in our simple example), it happens often enough that the adversary can cause a drastic and unnecessary reduction in model utility.
Degradation attacks are successful because certified run-time defenses do not account for the data manifold. An adversarial example is obtained by applying modifications to valid inputs. We formalize valid inputs by means of set M which is the support set of the underlying input distribution that characterizes the learning problem. Although the exact description of M is unknown, we know that both the training and test data used are in M. In order for model be free of adversarial examples, it only needs to be locally robust at every point in M. Certified defenses, however, try to enforce local robustness at all evaluated inputs, irrespective of whether the input belongs to M. An incorrectly flagged non-adversarial input is then an imput at which the local robustness check fails but if the model were not to reject the imput, it would be classified consistently with all valid inputs within an 6 distance. While norm-bounded adversary cannot change the classification of an input in the presence of a certified run-time defense, it can apply norm-bounded modifications to existing valid inputs (i.e., inputs in M) and force the model to reject otherwise correctly classifiable inputs, thereby degrading the model's 's utilityy.
As we discuss Section f defenders against degradation attacks have two options: they can use existing methods for constructing certifiably robust models but trained and validated with double the radius that the adversary is allowed for perturbations,, or they can develop new defense techniques that account for the fact that models only need to be locally robust at points in M. We evaluate the ramifications of the former option and leave the latter for future work.
To summarize, the main contributions of our work to as degradation attacks, that can force certifiably robust models (with either deterministic or stochastic defense mechanisms) to frequently and unnecessarily reject inputs: (2) we empirically demonstrate the severity of the problem for models using state-of-the-an certified defense mechanisms like GloRo Nets and Randomized Smoothing; (3) we make explicit the set, M, from which valid inputs are drawn, and this helps us explain that certified run-time defenses, based on checking e-local robustness, are susceptible to degradation attacks, as they enforce local robustness at all inputs and not just inputs in M; and (4) we discuss two possible defenses against degradation attacks, and evaluate the one based on doubling the radius enforced by certifiably robust models.
follows: (1) we describe new attacks, referred
The rest of this paper is organized as follows. In Section 2 we revisit definitions of adversarial robustness and sketch a general approach for certified defenses. In Section 3 we demonstrate how a certified defense can unnecessarily reject inputs; we present degradation attack algorithms to this end, and evaluate their efficacy. In Section [ we sketch two defenses against degradation attacks, and concretely evaluate one of these proposals. In Section 55] we describe the related work. Finally, we conclude in Section 6
2 REVISITING DEFINITIONS OF ADVERSARIAL ROBUSTNESS
neural classifier ERR + L a function from a d-dimensional real vector space, Rdd to a finite set of labels. L. The inputs to the classifier drawn from some distribution with support set M CR² In other words, the training and test sets are comprised of elements from M and their corresooningg labels. Though the description of M is not available to us, it plays key role in formalizing the notion of adversarial examples.
An adversarial example for neural classifier is the result of applying small modifications correctly classified valid input such that the modified input is classified incorrectly. Formally, an input is valid it belongs to M. Definition below, proposed by (Szegedy al. (2014), formalizes the notion of targeted adversarial example.
Definition 1 (Targeted Adversarial Example). Given neural classifier f ERd + L and an input E Rdd an imput x' x-r is an adversarial example with respect to a target label E L, Ep metric, and a fixed constant e R. if the solution to the the following optimization problem is such that 1r]lp Se:
Minimize ||r||p subject to f(z+r)=land x+r
Untargeted adversarial examples, simply adversarial examples, are defined similarly except that the constraint f fxx+r)= replaced with f(x++() +f())))
Szegedy et al. 2014) needs to be valid input, i.c., x E M, for x' to be an adversarial example. Making this requirement explicit and formal (via set M) is key step in the design of our degradation attacks.
As stated informally in (Carlini& & Wagner 2017
2

---

Under review as a conference paper at ICLR 2022
Algorithm 2.1: Prediction with certified run-time defense
Inputs: A model / / -> an imput æ' CR", attack bound CR, and distance metric Cy Output: A prediction /EL {T}
PredictwithDDeeense (f ,, ep);
if f is
robust at x' then
return ((x)
else
return
A classifier is protected from adversarial examples with respect to valid input if it is locally robust at æ. As stated in Definition 2 e-ball centered at c.
a classifier is locally robust at x, if its prediction does not change in an
Definition 2 (Local Robustness). A neural classifier EER LL (c.fp)-locally robust at x E
Va EER - Sc= -p f(x)=
The formal notions of validity and local robustness enable us to make the following key observation.
Observation A classifier is protected from all adversarial examples if locally robust at all points in M.
Certified run-time defenses. Classifiers, when composed with certified run-time defenses, guaranteed protection from adversarial examples. These defenses, briefly surveyed in Section detect adversarial examples during model evaluation (or run-time) by checking if the model is locally robust at the input being evaluated. Algorithm 2. describes the manner in which certified run-time defenses are deployed for protection.
The common assumption is that an adversary has white-box access to f as well as to valid inputs (denoted 2), and that the adversary may may not succeed in building adversarial examples (denoted x') that are e-close to z under the Ep metric. Given input z', certified run run-time defense helps decide whether r' is an adversarial example or not. As described by Predi Wi thDe fense (lines 1-5), the defense mechanism is first used to check if the model f' is locally robust at z' (line 2). If the check passes, then r' is guaranteed to not an adversarial example and the model prediction at x' returned as the label (line 3). However, if the check fails, then x' maybe an adversarial example, though it not guaranteed to be one. The model conservatively rejects the input, indicated here as returning the 1 label (line 5).
3 DEGRADATION ATTACKS
In this section, we describe our degradation attack algorithms and demonstrate their efficacy empirically, First, in Section 3.1 by means of an example, we demonstrate how certified defenses can lead to unnecessary rejections. Next, in Section 3.2 we describe our degradation attack algorithms against deterministic and stochastic certified defenses. Finally, Section 3.3
we evaluate our attacks empirically.
3.1 AN EXAMPLE OF A CERTIFIED DEFENSE FAILURE
Certified run-time defenses can erroneously flag non adversarial input as adversarial because they enforce local robustness at all inputs and not just inputs in M. Consider the example in Figure is valid input from M. Let us assume that none of the points in the gray region belong to M. binary classifier f R² - (W,CG assigns label W to all points in the white region (which includes x and x') and label G to all points in the gray region. x and x' apart and the radius for both the circles is The (c,42)- local robustness check includes white and gray points. However, s' is adversarial
will fail since the e-ball centered at x'
Figure 1: A flagged non-adversarial
example

---

Under review as a conference paper at ICLR 2022
Algorithm 3.1: Degradation attack algorithm
Inputs: A model f F T,, an imput at E M, attack bound R, and distance metric Ep Output: An attack input a' E
Degradationatten (f , fp):
d" = Attack(fxx22.f.
= Project(s, k.lp)
return
Algorithm 3.2: Smoothed projected gradient descent attack (SPGD)
Inputs: A model f f mapping inputs to logit outputs, loss function an input x an attack bound e E B, a distance metric Ep. step size 1), a number steps N, a number of samples n, noise parameter a
Output: An attack input a' ER.
SmoothedPgdAttack/ (f L, x, 1 n, n0
==== ==
for 0 S step < N do ( ~ (0,
= =' +
= Pro Pro
returm
input since it shares its label with all the e-close inputs in M. Consequently, the model rejection of x' is unnecessary and causes a degradation in model utility. This happens even the local check is precise and the bound tight
3.2 ALGORITIMMS
Algorithm 3.1 describes simple degradation attack against deterministic defense. Intuitively, given valid input æ (on which the classifier / is -locally robust, for some fixed e and distance metric fp), we want to find input x' such that ||x- |p S e and the classifier is not (e,Ep) -locally robust x'. The attack re- purposes existing white-bon box attack algorithms (like Carlini- Wagner (Carlini & Wagner 2017) and PGD (Madry al. 2018)) that search for adversarial examples. In particular, the attack invokes an off-the-shelf white-box attack algorithm, indicated by Attack, to find an adversarial example x" in ball of radius 2 centered at a (line 2). Next, x" is simply projected onto the e-sphere centered x (line 3). For f2, Pro ject is defined as x m-mifefe ||a"-= 11="=11p"" whereas for Ex we simply need to clip x".
Attacking stochastic defenses. Stochastic defenses, such as randomized smoothing, transform a base classifier into smoothed classifier by convolving the base classifier with Gaussian distribution. The smoothed classifier does not have an explicit representation, and to evaluate it on a single input, the base classifier needs evaluated on as many as 100,000 samples (Cohen al.) 2019). Moreover, the lack of explicit function representation precludes the use of off-the-shelf white-box attack algorithms that perform gradient descent the input space. While one could simply perform standard white-box attack on the base classifier, found it was more effective to implicitly attack the smoothed model by taking the average gradient over set of randomly generated samples at each gradient descent step. This gives us a "smoothed PGD" (SPGD) attack tailored for against stochastic defenses. Our SPGD procedure is given in Algorithm 3.2
Note that Algorithms 3.1 and 3.2 are only meant to proofs-of-concee for degradation attacks. As our empirical results in Section 3.3. demonstrate, even these simple algorithms can be highly effective in degrading model utility.
4

---

Under review as a conference paper at ICLR 2022
3.3 EVALUATING ATTACK EFFICACY
Our empirical evaluation is designed to measure the susceptibility of state-of-the-art robust models and certified run-time defenses to utility degradation attacks. For our experiments, we consider GloRo Nets (Leino et al. ) and randomized smoothed models (Cohen et al., 2019). These approaches lead to models with the best known verified robust accuracies (VRA), with respect to the &g metric, variety of popular image classification datasets like MNIST (LeCun et al. 2010), CIFAR-10 10 (Krizhessky 2009). and
ImageNet (Deng et al. 2009).
GloRo Nets incorporate global Lipschitz bound computation into the model architecture. The global Lipschitz bound is used implement the local robustness check input under evaluation. Morcover, these local robustness checks are backpropagated over during training to encourage learning of models with high degree of robustness. In contrast, randomized smoothing transforms base classifier into smoothed classifier by convolving the base classifier with a Gaussian distribution. The smoothed classifier typically demonstrates a much higher degree of robustness than the base classifier as long as the base classifier has been trained to classify well under Gaussian noise. The method uses statistical techniques to compute the local (certified) robustness radius R of the smoothed classifier at given input, so an (c,f2)-locce robustness check simply amounts to checking if the radius R at the evaluated input is greater than or not. Radius R is only probabilistically valid, so all the results for randomized smoothing this section are also probabilistic statements. However, this probabilistic nature of f is typically ignored when metrics like VRA are reported on randomized smoothing in the literature, and we do the same here.
We conducted two sets of experiments. In our first set of experiments, described in Section 3.3.1 we attack certifiably robust models at inputs in the test set using the approaches described in Section 3.2
This demonstrates the efficacy of our attack algorithms,, and gives a lower bound on the efficacy of degradation-sty -tylee attacks in general. Our second set of experiments, described in Section (3.32] measure the susceptibility of models degradation attacks assuming all- powerful adversary, i.e., an adversary that succeeds whenever the model is susceptible to degradation attack at inputs in the test set. This provides an upper bound on the efficacy of degradation attacks.
To measure the efficacy of degradation attacks on particular model with a certified run-time defense and dataset, we construct two subsets of the test set for the given dataset, that we refer as testR and te The former, testR, is the set of test inputs on which the model is certified to be (e,fl)-oocall robust. To construct te we simply apply the Hooal robustness check every input in the test set. If the check passes at an input x, it is added to test The latter, festA, is subset of test constructed using a robust at x but
degradation attack, such that for each input E A the model is certified (c,t,)-locall there exists an input x' in the e-ball centered at x such that the model cannot be certified (e, -locally robust at a'. Since the model is certified locally robust at x. we know that x and x' share the same label and x' is not an adversarial input (assuming that there exists other point of a different class label in M that is e-close to z'). Yet, the model would reject x' since the local robustness check fails at x'. Thus, testa represents the set of test inputs where the model is susceptible to degradation attacks. The ratio (eet I/pa represents the false positive rate of the certified run-time defense, i.e., the rate at which the certified defense erroneously causes the model reject inputs. We measure model susceptibility and attack efficacy in terms of the false positive rate. A value of one indicates that the model is susceptible to a degradation attack on all test inputs where it is certified locally robust, while value of zero indicates that model is safe from degradation attacks on all certifiably robust test inputs.
We train GloRo Nets using the publicly available a F For randomized smoothed models, we use the pre-trained models made available by the authors? 3) The GloRo Nets used in the evaluation are composed of convolution and fully-connected layers. For MNIST (c= 0.3), the model has two convolution layers and two dally-connected layers (2C2F), for MNIST (c= 1.58), the model is 4C3F, and for CIFAR- 10 (e (e=0.,,,), the model is 6C2F, For 100 the randomized smoothed model uses a 110-layer residual network as the base classifier, and for ImageNet, ResNer-50 model is used as the base classifier We implemented our attacks in Python, using TensorFlow and PyTorch. All our experiments were run on an NVIDIA TITAN RTX GPU with 24 GB of RAM, and a 4.2GHz Intel Core 17-7700K with 32 GB of RAM.
httppa///giichub.ccm//oooo
5

---

Under review as a conference paper at ICLR 2022
baseline VRA
folse positive rate
utility reduction
(%)
(%)
(%)
MNIST (6= 0.3)
95.0
6.0
5.7
MNIST (<= 1.58)
61.8
56.1
34.7
(1-AR-10(e-0.101
60.0
11.4
6.6
Table I: Lower bounds for false positive rates induced by degradation attacks against GloRo Nets. Models are trained and evaluated using the same e value.
baseline VRA
fulse positive rate
utility reduction
(%)
(%)
(%)
CI 0.5)
0.25
48.0
50.0
24.0
0.50
41.0
29.3
12.0
ImageNet (e=1.)
0.50
46.0
17.4
8.0
Table 2: Lower bounds for false positive rates induced by degradation attacks against Randomized Smoothing. Similarly to the evaluation Cohhen et al.) (2019) results are obtained on a sample 100 arbitrary test points, Randomized Smoothing is costly to evaluate.
3.3.1 LOWER BOUNDS ON ATTACK EFFICACY
To evaluate the efficacy of the attack algorithms presented in Section 3.2 and compute lower bounds on the efficacy of degradation attacks, we construct testa as follows. An input x E testn is added to testa a the attack algorithm succeeds in finding attack input x' in the e-ball at such that the model cannot be certified robust at x'. Table [ Nets, measured by performing presents lower bounds on degradation attack efficacy against GloRo degradation attack described in Algorithm 3.1] Table presents presentt lower bounds on degradation attack efficacy against Randomized Smoothing, measured by performing our SPGD degradation attack described Algorithm 3.2 We employ the same e values for GloRo Nets as used by Leino et al. (2021), and employ commonly used values for Randomized Smoothing that result in visually imperceptible perturbations.
We see that against both GloRo Nets and Randomized Smoothing our attacks decrease model utility to varying degrees. some cases the reduction in utility was substantial, with false positive rates 50% or more on MNIST (GloRo Net) and CIFAR-10 (Randomized Smoothing). Overall, false positive rates were higher when the robustness radius was relatively higher; e.g., the false positive rate on MNIST GloRo Nets increases from 6% to 56% when the radius increased from 0.3 to 1.58. This may be in part because at smaller radii, many points may be likely to be far more robust than required.
Despite the fact that explicit representation of smoothed models is not available even white-box attacker, we find that our SPGD attack was able to successfully degrade the utility of models defended by Randomized Smoothing. On smoothed models observe that models trained with a larger noise parameter a are less affected by false positives; however, this comes at the cost of a notable decrease in baseline utility.
In Appendix B we report the result of using off-the-shelf PGD with an c-bound as a degradation attack algorithm for attacking GloRo Net models. We also present a visualization of successful degradation attack inputs in the same section.
3.3.2 UPPER BOUNDS ON ATTACK EFFICACY
To compute upper bounds on the efficacy of degradation attacks, i.e., upper bounds the false positive rates, we construct test, as follows. We apply a (2c.E))-local robustness check at every input in testa- If this stronger check passes an input means that no matter how the adversary perturbs within the e-ball centered at x, the model is always loccllly robust at the perturbed input, and the certified defense (whether complete incomplete) cannot be forced unnecessarily reject the input as long it

---

Under review as a conference paper at ICLR 2022
2.54
L-03
1.5
0.5
64
03
14
64
(a)
(b)
(c)
(d)
Figure 2: Upper bounds for false positive rates on Gloro Nets
CHARR
imagehett
CIFAR- 10,
Imagehiet vary
25
100
C31
C31
03B
036
0336
(a)
(b)
(c)
(d)
Figure 3: Upper bounds for false positive rates on Randomized Smoothing
satisfies monotonicity property GloroNets and randomized smoothing are both monotonic in this sense (see Appendix A... However, if the (2e, flocal robustness check fails at x, then even though the model is certified -locally robust at there may exist an input x' in the e-ball at a: where the model cannot be certified (e.E,) plocclll robust and an adversary can force an unnecessary rejection. Therefore, if the stronger check fails at æ, we add it to testa.
Figures 2aland 26 show the false positive rates at different radii (i.e., e values) for GloRo Net models trained to be robust against the values indicated in the legend. The values of 0.3 and 1.58 for MNIST and 0.141 for CIFAR-10 are the same as the ones used for evaluating the lower bounds. Figure also reports results for models trained to be robust against twice these values. This is for the purpose of evaluating one of proposed defenses against degradation attacks (see Section 4.1).. We see that the false positive rates are quite high and consistently approach one as the radius increases. The models trained with higher values are more resilient to degradation attacks, but they pay the price of a lower VRA, specially at lower radius values (Figures 2cland 2d). By comparing the upper bounds the lower bounds obtained in Section 3 we see that our degradation attacks recover between 1/4 and 1/2 of the best possible degradation.
Interestingly the susceptibility degradation attacks does not appear to result from the GloRo Net's overapproximation of local robustness. Leino et al. (2021) report that the Lipschitz bounds on the MNIST models are far tighter than on the CIFAR-10 10 model, yet the CIFAR-I0 model is not more susceptible to degradation. As explained in Section 1 this is because the threat of degradation attacks arises intrinsically from any defense that filters based on local robustness at run-time, not because of the overapproximate nature of practical defenses.
Figures 3a| and 3bb show the false positive rates at different radii for each of the randomized smoothed models. Again, the false positive rates high and approach using larger a values unsurprisingly demonstrate more resilience to degradation attacks at the cost of a reduced VRA (Figures and where all points in text n also end up in testa; A; i.e., the model is susceptible to degradation attacks at all the points where it is certified locally robust.
increases. Models that are smoothed
and 3d). The sudden jumps in the false positive rate to one indicate the value
4 DEFENDING AGAINST DEGRADATION ATTACKS
In this section, we sketch two possible ways of defending against degradation attacks, and empirically evaluate the effectiveness of our first proposal.
WWe say that certification method cert: RR XR+ - bool is monotonic if, Va,ar ERd, - 0. cert(rre)) A I|-- o' l1p <e cert(s', ,e- 1|0-2/1lp)
7

---

Under review as a conference paper at ICLR 2022
4.1 DEFENSE VIA RADIUS DOUBLING
A simple strategy to defend against degradation attacks is to enforce local robustness, when training and validating certifiably robust models, using twice the radius that the norm-bounded adversary is allowed for adversarial and degradation attacks. This strategy is motivated by the intuition that if model is 2c robust a point æ in M, then no matter how the adversary perturbs z within the e-ball centered at æ, the model is always (el.p)-occall robust at the perturbed input, and an (c.fp))-ccal robustness defense is likely (or even guaranteed, the case of a complete defense) to not reject the input unnecessarily.
Training model for 2c-robustness is not guaranteed to help because of the frequently observed inverse relationship between accuracy and robustness. The model may be less accurate than the one trained for e-robustness, and may also reject more frequently, even on points in M. But validating the model against 2e is certainly helpful. The 2 BeA on validation data a lower bound on the accuracy one can expect on test data, in the face e-adversary capable of adversarial as well as degradation attacks. This also suggests that, when evaluating certified defenses, one ought to report not just e- VV,,, but also 2e- VRA. Validating against 2c can also help in configuring the certified run-time defense. In case the rejection rate is too high at a particular 2c, the certified defense can be configured to enforce local robustness at a smaller c value. This reduces vulnerability to degradation attacks at the cost of an increased vulnerability adversarial attacks.
We evaluate this defense strategy on GloRo Net models using the same architectures and datasets as in Section 3.3 However, re-train all the models using twice the values that we want defend against. Figure 2 summarizes the results. We see that training against 2e-robustness helps reduce the false positive rates compared the models trained against e-robustness. Moreover, this improvement is achieved without significantly affecting the VRA of the models. These results suggest that training against 2e-robustness can reduce the vulnerability to degradation attacks, but the false positive rates still remain concerning.
While smoothed models are not explicitly trained for a specific degree of robustness, and therefore this approach does not directly apply. the noise parameter, a. does allow one to control the trade-off between robustness and accuracy. Cohen et al. (2019) found that the best VRA is typically achieved when a s//22. Table [ shows that by increasing a beyond this point, one can obtain better resistance to degradation. show, increasing also negatively impacts utility.
However, as Figures 3c and 3d
4.2 DEFENSE VIA AN M M-MEMBERSHIP ORACLE
Certified run run-time defenses which rely on local robustness checks are susceptible to degradation attacks because these defenses are overly strong. i.c., they try enforce local robustness at all evaluated inputs. even though they only need to enforce local robustness at inputs in M. To 'fix' these certified defenses, instead of checking local robustness at the given input s', one could instead check if a' shares its label with all the inputs in M that are c-close to x'. If the check passes, then x' is guaranteed to be aon-adversarial input, but, more importantly, if the check fails then x' is guaranteed to be an adversarial input.
This fix works because an input x' is an adversarial example if and only if there exists some input E M that is e-close to a' and labeled differently from x'. To implement our proposed fix, we would need an explicit representation for M, or at least oracle for membership in M. A membership oracle may be used to search for members of M that are e-close to a given z'. While an exhaustive search for all such members is likely infeasible, we may allocate a fixed budget of computational resources to the oracle-based check. If, within the allocated budget, we find an input x E M such that x is c-close to x' but it has a different label, then we have detected an adversarial example and can reject x'. However, if the check fails to find such an æ within the budget, we can fall back to checking local robustness at x'. Practically, one could use an Out-of-Distribution (OOD) detector an M-membership oracle. Although OOD detectors can be imprecise and susceptible to adversarial attacks themselves (Schwag et al.) [2019] Bitterwolf et al. 2020), some recent developments (Chen al. 2020) look promising. We leave this for future work.
5 RELATED WORK
The discovery of adversarial examples has led an intense effort in recent years towards formalizing the problem, as well as designing new attack and defense mechanisms.
Formalizations. The presence of adversarial examples has been popularly formalized as the absence of local robustness in neural classifier. However, only constant functions are locally robust everywhere, so
8

---

Under review as a conference paper at ICLR 2022
this definition fails to capture the notion of a classifier free from adversarial examples. Leino et al. (202 l
propose the notion of global robustness for classifiers that are allowed to reject inputs. They define global
robustness having a margin (predicted as I or rejection) of sufficient width between classes. Their
observation is that checking points for e-local robustness corresponds to a margin of width 2e; i.e., there is a factor of two difference when referring global vs. local robustness. Moreover, Yang al.] (2020b) show that in natural image datasets, differently labeled images are indeed separated by a distance larger than twice the perturbation radii used in adversarial example experiments. These observations demonstrate that for real-world datasets, the support set of the input distribution is much smaller than the entire input space and inputs belonging to different classes are separated. different notion of global robustness is proposed by Ruan et al. (2019). They define a model to be globally robust if it is locally robust at every input in finite test set. None of these definitions capture the idea that, to be protected from adversarial examples, a model only needs to be locally robust at every input in the support set, M.
Adversarial attacks. Algorithms for constructing adversarial attacks can be divided in two major categories. White-box attacks assume that they have access to the model internals, i.e., the model architecture and weights. Their primary strategy is to perform gradient descent in the input space so as to find an input that maximizes the loss while satisfying the constraint of staying within the e-ball centered at the original input. Some popular and successful attack algorithms of this nature include the ones proposed by Goodffelow et al. (2015), Carlini & Wagner (2017). and Madry et al. (2018). Black-box attacks only assume query access to the model [Papemot et al. 2017). In other words, their threat model is weaker than the one assumed by white-box attacks. The degradation attacks proposed in this paper use adversarial attack algorithms as a sub-procedure and are agnostic to whether these algorithms are white-box or black-box.
Hcuristic and certified defenses. Heuristic defenses against adversarial examples do not provide any guarantees about their defensive capabilities. These include approaches that modify the training objectives, modify the neural classifier post-training, or embed run- un-time checks to flag adversarial examples during evaluation. The lack of guarantees suggests that these defenses can be broken and it has indeed been demonstrated (Athalye et al. 2018 Tramer et al. 2020) that a number of published defenses are breakable. In this paper, we focus on certified run-time defenses that are deployed during model evaluation and, if an example is adversarial, are guaranteed to flag it (though incomplete defenses can also report false positives). Such defenses check if the classifier is locally robust at the evaluated input. Guaranteed local robustness checks are implemented using variety of approaches that include constraint solving and formal methods (Huang et al. 2017]] Katz et al. [2117] Gehr et al. 20188; Singh et al. 2019), optimization (Bastani et al.. | Raghunathan al. [2088] WWong & Kolter 2018 TTjng et (019), Lipschitz
2016 Dvijotham al. 20188
hounds computation (Weng et al. (2018) Leino et al. [202)), and stochastic smoothing (Lecuyer et al. 2019)
Cohen et al. [2019] Yang et al.] (020a)). We show that such defenses are overly cautious and often flag even
non-adversarial inputs as adversarial.
The two algorithms (PREDICT and CERTIFY) from (Cohen al.. 2019) can both return ABSTAIN when the prediction (and the certified radius) can not be computed for the given input, due to the imprecision of the statistical analysis. This can be potentially exploited by an adversary who can force certifiably robust classifier to unnecessarily abstain as has been noted in (Cohen et al. 2019). Our attack is different (but similar in spirit) in that works in cases that CERTIFY does not abstain and is able to reliably compute the prediction and the certified radius R, but this radius may be smaller than the desired for inputs that are in fact -dverrrrra.....
6 CONCLUSION
In this paper, we have showed that certified run-time defenses against adversarial examples, based on local robustness checks, are inherently overcautious and can reduce model utility due to unnecessary input rejections. This is consequence of these defenses enforcing local robustness at all evaluated inputs even though local robustness only needs to be enforced at valid inputs, i.e., inputs in the support set, M, of the input distribution. An adversary can exploit this over-cautiousness: though they cannot change the classification of an input, they can apply norm-bounded modifications to valid inputs and force the model to reject otherwise correctly classifiable inputs. We have presented concrete degradation attacks of this nature that can be implemented using off-the-shelf white-box attack algorithms. Moreover, our empirical evaluation demonstrates that even state-of the certifiably robust models, like randomized smoothed models and GloRo Nets, are highly susceptible to utility degradation attacks.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We will make our attack code and experiment scripts available via GitHub, For all our experiments with randomized smoothed models, we directly use the pre-trained models made available by the authors of the paper at ht tps: httpt/tttthb.b//. com www/locuslall ab/ smoothing For the experiments with GloRo Nets, we trained the models using the publicly available code for training GloRo Nets at hhttts://gitae com/ hamm/klasllinn/gorro
ETHICS STATEMENT
Our work sheds light on existing vulnerabilities in state-of-the-art certifiably robust neural classifiers. These degradation attacks could be deployed by malicious entities to degrade the utility of deployed models. However, by putting this knowledge out in the public domain and making practitioners aware of the existence of degradation attacks, we hope that precautions can be taken to protect existing systems. Moreover, it highlights the need to harden future systems against such attacks.
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International conference on machine learning, pp. 274-283. PMLR, 2018.
Osbert Bastani, Yani Ioannou, Leonidas Lampropoulos, Dimitrios Vytiniotis, Aditya V. Nori, and Antonio Criminisi. Measuring neural robustness with constraints. In Proceedings the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pp. 26212629, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819,
Julian Bitterwolf, Alexander Meinke, and Matthias Hein. Certifiably adversarially robust detection of out-of-distributiin data. Advances in Neural Information Processing Systems, 33, 2020.
N. Carlini and Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 37, Los Alamitos, CA, USA, may 2017. IEEE Computer Society, doi: 10.1109//P.011..9. URL (ttpsttps: / /oo.. wtt.cccmpptrrroooo...toor///o/o.
2017..4 49
Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha. Robust out-of-distribution detection for neural networks. arXiv preprint arXiv:2003.09711 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Confer- ence Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320. PMLR, 09-15 Jun 2019. (tL/https:/ http:////occeeddeee
m press / v97 / cohenn 9c. html
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fe. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In Proceedings of the Thirty- Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-18), pp. 162-171, Corvallis, Oregon, 2018. AUAI Press.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018
IEEE Symposium on Security and Privacy (SP), pp. 3-18, 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015.
htRlhttp:://e org abs/ 412411240 6572
10

---

Under review as a conference paper at ICLR 2022
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference on Computer Aided Verification, pp. 3-29. Springer, 2017.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Yann LeCun, Corinna Cortes, and Chris Burges. Mnist handwritten digit database, 2010.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium on Security and Privacy (SP). pp. 656-672. IEEE, 2019.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference on Machine Learning (ICMI.). 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018.
Nicolas Paperot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communnicatinns security, pp. 506-519, 2017.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference Learning Representations, 2018. URL
forum? ?id Belld-yyy444 4ob-
Wenjie Ruan, Min Wu, Youcheng Sun, Xiaowei Huang, Daniel Kroening, and Marta Kwiatkowska. Global robustness evaluation of deep neural networks with provable guarantees for the hamming distance. In Proceedings of the International Joint Conferences Artificial Intelligence Organization, 7 2019. doi: (0.24963/jcaii.211993333 URL
International Joint Conference on Artificial Intelligence, IJCAI-19,
pp.
Vikash Sehwag, Arjun Nitin Bhagoji, Liwei Song, Chawin Sitawarin, Daniel Cullina, Mung Chiang, and Prateek Mittal. Analyzing the robustness of open-world machine leamnig. In Proceedings of the 12th
ACM Workshop on Artificial Intelligence and Security, pp. 105-116, 2019.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3(POPL), January 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Truck Proceedings, 2014. URL http:://aaxii/////////// org/ abs /13121116600 6199
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Leariing Representations, 2019. URL https ///ppenreview.ee net/ forum? dd=HGITdiRqt.m
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. Advances in Neural Information Processing Systems, 33, 2020.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5285. PMLR, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference Machine Learning, pp. 2286-5295.. PMLR, 2018.
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18. pp. 84108419, Red Hook, NY, USA, 2018. Curran Associates Inc.
11

---

Under review as a conference paper at ICLR 2022
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pp. 10693-10705. PMLR, 2020a.
Yao-
Yao-Yuan Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaudhuri. A closer look at accuracy vs. robustness. In NewrlPS, 2020b.
12

---

Under review as a conference paper at ICLR 2022
A
MONOTONICITY OF LOCAL ROBUSTNESS CERTIFIERS
Definition 4 (Monotonicity of local robustness certifiers). We say that certification method cert R x bool monotonic if
Ve,z' ER", C>.. cert(a,)) ~ cortt (c-)
Definition 5 (Fxact local robustness certifier). An exact certification method is one for which c - Va' E R.d RR.|| 2'11p < F(x)= = F(x') (in other words, certification equiva- lent to local robustness).
Lemma 6. All exact certification methods are monotonic.
Proof. This follows essentially from the triangle inequality. Let x E Rd and c > O, and suppose that cert(x,,). Thus, since cert exact, we have that Va' ERd ||1-~~=0/ x' x'Ix="nn - F(x)= F
Consider z' e Rd for which ||~'-z|| S. and let å == |||--x>' z'I). Now for x" e Rd assume || f -===" =e- Thus,
2 0+1||'=2"1|14 = ||===/|l
2 ||0-~"11
by the triangle inequality.
Thus, because we have cert(zze), we may conclude that F(z')= F(x) F(x"). This tells us that the classifier F' is (e-o)-locally robust æ', which, by completion gives cert(x',e-0),
Definition 7 (Lipschitz-based local robustness certifier), A Lipschitz-based certification method is one which, given an upper bound, Kgg(r,c) on the local Lipschitz constant of the margin fy ft at a Certifies point x, where Fxx)= =j. exactly when
Mex(((e))KKKKtte)) s fz(x). (f
Lemma All Lipschitz-buse certification methods are monotonic.
Proof: Let (x,( be upper bound on the Lipschitz constant of the function (((x))f((()) That is,
Kiy(z,e) is the maximum rate of change of fz(x) ((xx)=f(()) f((z) within an E, ball of radius e centered at a.
Let x E IRd and > 0, and suppose that cert(r,)), Consider E Rdd for which || -e/- =|| S e, and let
8= 1
We begin with the observation that the f, ball of radius centered at r-we will denote this as B(x, e) contains B(x', 6). This, too, follows essentially from the triangle inequality:
zE 6-6)
|| x Se- -= ||0-2'11
| Se
by the triangle inequality
Bzx e)
From this, conclude that Equation holld.
(iy(u,,)) Kiy(a' (x',e e-
(I)
With this in mind, we proceed as follows. Let j= F()); i.e. j is the class predicted by classifier at Since cert(æ, é) implies that the classifier is e-locally-robust at and x' B(r,e), we conclude that F(
Because assume that cert is Lipschitz-based (Definition we have Equation 2
Vi
(2)
note that the global I. ipschiizz constant is such bound
13

---

Under review as a conference paper at ICLR 2022
baseline VRA
folse positive rate
utility reduction
(%)
(%)
(%)
MNIST (==0.3)
95.0
6.1
5.9
MNIST (<= 1.58)
61.8
57.0
34.3
(e
60.0
11.2
6.6
Table 3: False positive rates induced by e-PGD degradation attack against GloRo Nets.
Figure 4: Visualizations of successful degradation attacks CIFAR-IO (e= 0.141).
Since 11-=x11 1<===11=0<< by the definition of Kij we have that
Viøj ((())=((xx))
2 (x-
2 -K
by Equation by Equation
2 (e-8)
This sufficient to conclude that we have cert(r', e 6-
GloRo Nets Lipschitz-based, therefore they monotonic by Lemma 8 Aside from the fact that condetermism/uunerttaa arises because of the need to sample to evaluate the smoothed function, Ran- domized Smoothing provides the exact robustness radius on the smoothed function. That is, in the infinite sample limit, Randomized Smoothing is an exact method, and therefore monotonic by Lemma 6 though practice this property only holds with high probability (i.e., the probability can be bounded from below). We note, however, that the robustness guarantees provided by Randomized Smoothing are analogously probabilistic.
B LOWER BOUNDS ON ATTACK EFFICACY (MORE RESULTS)
B. EFFICACY e-PG ATTACK
We evaluated the degradation attack efficacy of a simpler version of Algorithm 3.1 In this simpler algorithm, line 2 of Algorithm 3.1 replaced by a call to the PGD algorithm Madry et al. (2018) with an bound instead of a 2e bound. The attack input x" returned by e-bounded PGD is guaranteed to be within the e-ball centered v, so we no longer need to project x" as line 3, and directly return x" as the candidate degradation attack input.
Table 3 presents the results of using this simpler algorithm for degradation attacks against GloRo Net models. The models, datasets, and values the same used for evaluating the efficacy of Algorithm 3.1 The efficacy of an c-PGD attack similar to Algorithm 3.1 (presened in Table
B.2 VISUALIZATION OF SUCCESSFUL DEGRADATION ATTACK INPUTS
Figure 4 provides samples of inputs that constitute successful degradation attacks. In each pair of images, the original image is shown on the left and the perturbed image (the attack) is shown on the right. As expected, the pairs of images are visually indistinguishable; thus the adversary can be considered have successfully delivered an imperceptible attack.
C DEGRADATION ATTACKS AGAINST too DEFENSES
this section, we evaluate the efficacy degradation attacks against models defended with & certified defense. In particular, consider models trained and defended using the convex outer adversarial polytope
14

---

Under review as a conference paper at ICLR 2022
baseline VRA
folse positive rate
utility reduction
(%)
(%)
(%)
MNIST (c=0.1)
98.9
91.9
90.9
Table 4: Lower bounds for false positive rates induced by degradation attack against K.W.
baseline VRA
false positive rate
utility reduction
(%)
(%)
(%)
(NIST(<=0.1)
98.9
100.0
98.9
Table 5: Upper bounds for false positive rates induced by degradation attack against K.W
approach of Wong & Kolter (2188) that we refer to as KW. We compute lower and upper bounds in similar manner described in Section 3.3 using KW for the ) -llocal robustness check. For the lower bounds, the set testa is constructed using Algorithm 3.1 where Pr ject is implemented by clipping x".
Aable/repprtt the lower bounds, i.e., the efficacy of Algorithm 3.] against KWW Table 5 reports the upper bounds. We see that for defenses like KW are extremely susceptible to degradation attacks- the simple attack given by Algorithm [31 succeeds approximately 92% of the time, and the upper bounds indicate that it may be possible for more sophisticated adversary to succeed 100% of the time.
While striking, these results are not entirely unexpected, given the geometry of foc. space. Defenses based on robustness certification are susceptible to degradation attacks unless the underlying model is (2r, l,) )y)-ruuust. lo space, the volume contained by ball overlaps much more closely with [0,1] (the typical the domain for, e.g., image data), which intuitively means that the domain is "used up" much more quickly as the required robustness radius increases. By contrast, in high-dimensional Euclidean space, the radius can be as large as vd before it necessarily envelops the entire domain.
15


Reviews:
[{"review_id": "cBQGBnttbOM", "reviewer": "Reviewer_rHQj", "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": "I like the idea of.degradation attack on models. The problem setting is fairly intuitive. Since the learner only gets the AE at test-time instead of the original input, some information about the original input is already lost. As a result, the detection mechanism will have a tendency to overprotect.\n\nThe theoretical part of the paper is straightforward to understand. However, I find the discussion for the double-radius defense confusing. From Algorithm 2.1, it seems that a certified run-time defense will abstain at a radius. However, in Section 4.1, the models are said to be \"trained\" with parameter $2\\epsilon$. Does it mean that the models will abstain at radius $2\\epsilon$ during test-time? If yes, then it just opens a larger feasible set for degradation attack check. Could you please explain this more formally with helping lemma stating the guarantee of the defense mechanisms?\n\nMy other main worries about the paper are on the experiment results and design. Since the degradation attack phenomenon is quite easy to understand, I hope the experiments can clearly show the severity of such new threats. On top of the existing results, I hope the authors can address the following questions.\n\n1) What's the choice of your attack parameter $\\epsilon$? The choice now looks quite arbitrary. Please show degradation AE created at each $\\epsilon$ so that the readers know the visual similarity at the perturbation level.\n\n2) What's the gap between the lower and upper bound of the attack? Is there any pattern/conclusion we can find from the gap?\n\n3) How about the result for other $\\ell_p$ distances like $\\ell_{\\infty}$? \n\nAlso, is there a reason only showing the upperbound for GloRo in table and that for Randomized Smoothing in figure?", "summary_of_the_paper": "The paper considers a different perspective of attacks to certifiably robust ML models at test time -- the attacker can add imperceptible perturbation to force false positive of adversarial example (AE) detection, and thus lower the utility of the model/detection mechanism. It finds an empirical lower and upper bound to the degradation in performance, and validates the efficacy of such attacks against popular detection mechanisms.   ", "summary_of_the_review": "The idea of degradation attacks on certifiably robust AE detection is novel. However, the experiment setting is a bit too simplified. I recommend the authors to strengthen the experiment part so that the severity of the threat is better motivated. I'm giving a marginally below acceptance for now, but I'm willing to increase the score once my concerns are addressed.\n\n================================================================\n\nAfter viewing the author response, I'm raising my score to 6. The technical aspect is sound, and the author explained a relatively intuitive concept in a reasonable manner. Thanks for the clarification.", "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": "RcM-KhVipyH", "reviewer": "Reviewer_TyKj", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "While a number of concerns on clarity, the overall observation made by the authors is simple, useful, and evaluated thoroughly. It is, however, unclear whether the observation is novel under the current manuscript. See below for more details:\n\n- \"One need not assume that the inputs are scaled to be in $[0,1]^{d}$ , and hence we can drop the second optimisation constraint.\" This constraint is there because neural networks typically operate on bounded inputs, where there are no guarantees on inputs which do not follow the scaling rule the network uses for preprocessing. I assume the argument for why this can be dropped is this constraint is replaced by ensuring the adversarial belongs in the support set. Please confirm, and update the text s.t. this is explained explicitly. \n- While Figure 1 is clear, it would be useful if the motivation could be based on a practical example that could come up in practice, s.t. the practical application of the method presented in the paper is clear to the reader. \n- Can the authors clarify why Algorithm 3.1 is effective? First, clarify why simply applying an off-the-shelf white-box attack with epsilon bound would fail, then explain why projecting the perturbation from an off-the-shelf white-box attack with double the epsilon bound projected onto the epsilon sphere works. Will the projection step project onto a sphere for any valid Lp norm?\n- For attacking stochastic inputs, the authors should cite any attacks which have used a similar formulation. Many attacks against stochastic defences exist, most prominent is expectation over transformation (https://arxiv.org/abs/1707.07397). Evidence of a literature review should be provided. \n- Could the authors visualize random examples found by the attack algorithm which fool the local robustness check? \n-A much clearer, description integrating sections 3.3.1 and 3.3.2 is warranted. From what I can tell, $\\text{test}\\_{R}$ is the same in both sections. $\\text{test}\\_{A}$ is identified by the degradation attack algorithms presented in the earlier section in 3.3.1, and $\\text{test}\\_{A}$ is identified by modifying the local robustness check in 3.3.2? If this is incorrect, please clarify. Regardless, these sections should be integrated and presented more clearly. \n-The commentary on \"overapproximation\" requires an extended discussion, where the concepts are introduced in a less rushed manner. \n- \"A plot for the randomised smoothed models as compared to a table for the GloRo Nets is simply a reflection of the slightly different ways in which these models are evaluated.\" While emphasising the different ways these models are evaluated is appreciated, that by itself isn't a reason to present results in different ways. If by \"reflection\" the authors are implying they have to present results in different ways, then this should be explicitly clarified. If not, if the authors can compute the table computed for GloRo Nets for randomised smoothing, they should do so. Likewise, if the authors can make the plot made for randomised smoothing for GloRo Nets, they should do so. Comparing and contrasting the tables and/or the plots would also be informative to the reader. While I understand the subsequent text after this quote was intended to clarify this, it was insufficient. \n-\"However, we re-train all the models using twice the values that we want to defend against.\" Given the commentary prior to experiments, the authors should also evaluate without re-training all models using twice the values. \n-\"None of these definitions capture the idea that, to be protected from adversarial examples, a model only needs to be locally robust at every input in the support set, M.\" This makes the claim on novelty unclear. The formalization of the support set was only present in the presentation, it was not leveraged in neither the proposed attacks nor the proposed defenses (as sec. 4.2 leaves it to future work). What was actuated upon is the notion of \"$2\\epsilon$\", which, as the related work shows, a number of works have explored. The authors need to further clarify the contribution relative to the existing works from the perspective of the proposed algorithms evaluated in the work. \n", "summary_of_the_paper": "This work investigates an observation that certifiably robust neural networks flag inputs for which local robustness checks fail, but are classified consistently with all valid inputs within a distance of $\\epsilon$. The authors actuate this observation in an attack where norm-bounded changes degrade the utility of certifiably robust networks by forcing them to reject otherwise correctly classifiable inputs. ", "summary_of_the_review": "Since the novelty of the paper currently needs further clarification, I am providing a borderline rating, subject to the author's rebuttal. \n\nAFTER REBUTTAL: The author's rebuttal did not sufficiently convince me of the novelty of the contribution, and thus the paper remains borderline in my estimation. However, I will be raising my score. ", "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": "Axko-n5wN6", "reviewer": "Reviewer_YcnJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The presentation of the paper was generally clear and well laid out.\n\nHowever, there are potentially some issues, though I may have misunderstood and would welcome the authors’ responses to the comments below.\n\nThere is a statement (section 5) “we focus on certified runtime defences that are deployed during model evaluation and are guaranteed to detect adversarial examples”. I would contend that certifiable robustness processes are usually such that the certified robustness (CR) check (for radius epsilon) passing at x implies the classifier is epsilon-robust at x. But the converse is not necessarily true – as evidenced by the fact that different certified robustness approaches perform differently. Failure of the CR check at radius epsilon I am not sure guarantees the presence of an adversarial point in the epsilon ball. It simply means that there wasn’t appropriate evidence to guarantee there is no such point.\n\nGiven this, in section 3.2.2, it is stated that if a point x is 2*epsilon-robust, then every point within the epsilon ball around x is epsilon robust. This is true. But it is then said that “and so (the classifier) cannot be forced to unnecessarily reject the input”.  I am not sure of the latter statement, since (as argued above) the CR check may fail at that point, but that does not mean it is not epsilon robust at that point.\n\nSimilarly, the statement in 3.2.2 that “if the 2*epsilon CR check fails at x, then even though the model is epsilon robust at x, there exists an x’ in the epsilon ball at x where the model is not epsilon-robust” (paraphrasing a bit). But I would contend that failure of the 2*epsilon CR check does NOT mean that there is an adversarial example in the larger ball. It could still be 2*epsilon robust (and fail the check), and hence the paper’s conclusion is not true. \n\nIn the same vein, I have problems therefore in section 3.3.1 in say defining test_R. How do we determine the set of points on which the model is epsilon robust (according to Definition 2). We can find the set of points on which it is certified robust by our check, but this will presumably miss points at which the test fails even though it is robust. Is it this certified robust set instead which is meant here to be test_R? Also, if this is the case, this is not really establishing “A lower bound on attack efficacy” – it is actually evaluating the efficacy of the given attack. This establishes a lower bound on the fraction of test points which are vulnerable to degradation attacks. Other degradation attacks may fare worse. Hence I question the wording of the title of this section and the way it is presented.\n\nRegardless of the above discussion re the correctness of the approach, I have an issue with the phrasing of the basic claims of the paper. It is claimed (rightly) that an input point may be perturbed within the epsilon ball and no longer pass the robustness check, even though the original point did. So the perturbed point is then flagged as not-certifiable. It might be arguing semantics, but the system is really I would contend not flagging adversarial points, but just indicating if a given point is certifiably robust. In this case (the attack), it no longer is certifiably robust, and the system indicates this. The statement (section 5) that the system can “flag even non-adversarial inputs as adversarial” I feel then is a bit of a misrepresentation of what it is doing (And to call these perturbed points non-adversarial inputs also is a bit disingenuous. They are constructed to mislead the system and so, in any reasonable sense, are adversarial).\n\nAlso, some discussion in the paper I believe is warranted to address the fact that certified robustness is typically (e.g. in the case of Cohen et al) probabilistic, i.e. up to a certain confidence level (ignored also in the above arguments).\n\nIn the experiments, I think some comparison to say PGD would be valuable, i.e. investigate how successful (accidentally!) PGD (in an epsilon ball NOT 2* epsilon) is at finding degradation attacks at robust points. PGD will fail to find an adversarial example at such points of course, but checking whether the (failed) attack point is still certified robust would be an interesting measure to see how more efficient at finding such points the algorithms proposed in the paper are. Further, one could consider for the other points in the test set, how effective the proposed algorithms are at finding adversarial examples compared to vanilla PGD. i.e. do the proposed algorithms degrade efficacy of an adversarial attack on non-robust points?\n\nSome minor comments:\n-\tIt is worth noting that Cohen et al, for example, evaluates the arg max (label) for each noise-perturbed input, and then the counts of different classes go into the evaluation. Instead, in Algorithm 3.2 (line 5), it takes the average of the logits for each input in evaluating the loss. This approach to constructing the smoothed classifier is more akin to the approach of Lecuyer et al. Not necessarily an issue – as I am not sure that there would be a direct analog of the Cohen approach in determining the gradient. But worth highlighting.\n-\tThere is a slight abuse of notation in lines 4 and 5 of Algorithm 3.2. The decomposition of the noise vectors into n d dimensional vectors is obvious, but not explicitly stated in the definition\n-\tWhen it is stated in 3.3.1 that “assuming there exists no other point in M, except x, that is epsilon-close to x’” presumably this should say “.. point of a different class label ...” \n-\tIt would be good to show both lower and upper bounds on the same graphs (fig 2) so as to visually show how tight (or otherwise) they are\n-\tIs it not the case that the defense 4.2 is not really practical as membership of M is not really computable typically.\n", "summary_of_the_paper": "This paper presents a new line of attack, so-called degradation attacks, targeting the certified robustness of a model rather than directly targeting the classifier. They argue that in the case of certified robustness, a suitable norm-bounded adversary cannot change the classification of an input at which the output is robust, but can force the rejection of that input as potentially adversarial, thus degrading the utility of the system.", "summary_of_the_review": "Though the idea of the paper is interesting, and the basic attack techniques proposed seem effective, I had, besides some more semantic issues, some concerns with the correctness of the argument of the paper with respect to the upper bound determination. This means that I cannot accept the paper in its current form (unless of course the authors correct any misunderstanding on my behalf – which is very possible). \n\nEdit: The author revisions have addressed some of the main issues with the upper bound determination (including a discussion of monotonicity). Interestingly, the inclusion of the PGD attacks in the supplementary materials, as per my suggestion, seems to perform about as effectively as the proposed algorithms in the main paper. Given the improvements, I have increased my rating to reflect that and the fact that the underlying idea is interesting.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AB5kcZPpMU6", "reviewer": "Reviewer_akrY", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strength\n\n1. Experimental results show that randomized smoothing and GloRo have degraded verified rates under the proposed attacks.\n2. A customized defense is proposed and discussed.\n\nWeakness\n\n1. I doubt the practical usefulness of this degradation attack. In practice, verification is a plus for the model robustness evaluation. It is safe to trust the results if a sample is verified but a sample that cannot be verified does not necessarily mean we have to reject it. There are many other ways to measure the robustness and give confidence scores of the predictions. GloRo proposes to do the rejection mainly because they want to have global verified robustness with global Lipschitz constant but eventually it still serves for local robustness verification.\n2. I do not think the example in figure 1 makes sense. When the ground-truth robustness region of x' is already crossing the decision boundary, it is truly an adversarial example. Rejection is indeed the correct thing to do for deterministic verification methods like GloRo unless we can retrain the weights to reshape the decision boundary. Please note that over cautiousness is the intrinsic property for certifiable defenses and should be the correct thing to have. The local verified robustness should only focus on the samples belonging to the original input distribution (x belongs to M) while the verified robustness around other samples like perturbed ones that out of the distribution (x' not belongs to M) should not be encouraged. Otherwise, it will become an unnecessarily too difficult problem unless global verified robustness is required.\n3. The smoothed PGD attack has very limited novelty. A similar method is already proposed and also used for training to achieve better results over randomized smoothing alone. The attacks should at least discuss and evaluate over [A].\n4. The proposed attack should really be discussed and evaluated with other SOTA complete verifiers like alpha-beta-CROWN [B, C] (the winner of neural network verification competition this year) or incomplete ones like CROWN [D] and K&W [E], and certifiable training methods like CROWN-IBP [F] and IBP [G].\n\n[A] Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers, NeurIPS 2019\n\n[B] Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Verification, NeurIPS 2021\n\n[C] Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers, ICLR 2021\n\n[D] Efficient Neural Network Robustness Certification with General Activation Functions, NeurIPS 2018\n\n[E] Provable defenses against adversarial examples via the convex outer adversarial polytope, ICML 2018\n\n[F] Towards Stable and Efficient Training of Verifiably Robust Neural Networks, ICLR 2020\n\n[G] On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Model, ICCV 2019", "summary_of_the_paper": "This paper proposes a degradation attack on certifiable defenses GloRo and randomized smoothing aiming to find correct inputs within robustness region but hard to certify, causing rejections. The proposed attack is simple which is just a smoothed variance of PGD attack. Experimental results show that the two evaluated certification methods are susceptible to this attack.", "summary_of_the_review": "I recommend rejection due to lack of novelty and comprehensive evaluations over SOTA verification methods. Also, I am not very convinced by the motivation of the proposed methods.\n\n=== Post Rebuttal ===\nThank the authors for the extensive discussions. Some of my concerns have been clarified in the discussion and the revised submission. Some insights of the paper are quite interesting. However, I am still concerned about the novelty and SOTA evaluation of the proposed methods. Overall, I decided to increase my score to 5.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The work focuses on the observation that, given a certified epsilon-robust model and a certified clean input x, many inputs within the epsilon ball around x are themselves not epsilon-certifiable although they are correctly classified. The authors argue that an adversary can exploit this property to produce inputs which are correctly classified by the model yet are not certifiably robust. Reviewers agreed that the paper was overall well written, the methods were clear and overall evaluated thoroughly, and many felt that the main idea was interesting. There were some concerns regarding the significance of the contribution, the primary observation itself is arguably novel but somewhat obvious, and the proposed algorithm for finding non-certifiable points isn't a significant contribution when standard techniques like PGD are sufficient. Much of the reviewer discussion concerned whether or not the proposed attack made sense as a threat model. It is the AC's opinion that this discussion did not reach any meaningful conclusions. It is important to remember that the lp threat model is intended as an abstract toy game so that a formal theory of neural network certification can be developed under idealized settings. It is not intended to model any realistic security scenarios, and even more generalized notions of "imperceptible" or "subtle" attacks aren't realistic when for the bulk of applied settings real adversaries are not restricted to small perturbations in the first place [1]. The example provided by the authors regarding small perturbations of a stop sign isn't a relevant example when the adversary has more effective options, e.g. knocking over stop signs [1, Figure 3]. 

For the sake of discussion, one could consider whether or not a degradation attack would make sense under more general threat models such as content-preserving perturbations. An example discussed in [1] concerns adversaries uploading copyrighted content to public streaming services—this attacker defender game is being actively played in the wild where defenders produce statistical models which attempt to flag content as semantically matching existing copyrighted content in a private database, while attackers make large semantically-preserving modifications in order to evade statistical detection. An example attack would be cropping 20% of the boundary pixels of a movie and replacing the cropped portion with arbitrary adversarially constructed backgrounds. Epsilon perturbations are possible, but are almost a measure 0 subset of the full attacker action space. Suppose in the far future neural network certification advanced to the point where we could certify that a classifier was robust to all possible content-preserving perturbations of a specific movie. In this case the defender would be using the certification method on their private database of copyrighted content, they would not be running the certifier on any content uploaded by users. If a movie in the private database is certified, then we already know that an attacker cannot successfully upload an adversarial version of it, it would be unnecessary to certify whether or not user uploaded content could be further perturbed in a way to become adversarial. Perhaps degradation attacks could be possible as a training poisoning attack, but this seems a bit far-fetched when more traditional training poisoning attacks would be preferred. Given this, at least in this example the AC does not see how a degradation attack would make sense as a threat model. 

Given that the primary contribution of this work is a novel threat model for ML security, it is crucial that the authors rewrite their work to make more realistic assumptions of the capabilities of realistic adversaries. Starting with some of the examples discussed in [1] may be useful to the authors. Although the example of adversarial attacks on copyright detection classifiers doesn't seem to fit the degradation attack threat model, perhaps other scenarios would.

1. Gilmer et. al, Motivating the Rules of the Game for Adversarial Example Research, https://arxiv.org/pdf/1807.06732.pdf
Decision: Reject