Year: 2021

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 . 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.

heading: 1 INTRODUCTION
text: An adversarial example for a neural classifier is the result of applying small modifications to a correctly classified valid input such that the modified input is classified incorrectly. For neural classifiers trained in a standard manner, it has been shown that adversarial examples are rampant (Szegedy et al., 2014; Carlini & Wagner, 2017). While training models in an adversarially-aware 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 accuracy1 of models.
Certifiably robust classifiers (Weng et al., 2018; Wong et al., 2018; Cohen et al., 2019; Leino et al., 2021) 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 a certified run-time defense. The defenses aim to detect adversarial examples during model evaluation, by checking if the model is -locally robust at the evaluated input. If the check fails, the input is flagged as (potentially) adversarial and the model rejects the input. However, a rejection is not free of cost. Every time the model rejects an 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 as adversarial. This over-cautiousness is inherent in the design of such defenses, and it is manifested even when the -local robustness check is exact (i.e., the defense is complete). Not only does this lead to a 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 attacks. 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-the-art certifiably robust models, such as GloRo Nets (Leino et al., 2021) 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 a concrete scenario, consider an autonomous driving system that uses a 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-making to the human driver. This is perfectly safe behavior, but this model has zero utility. Ideally, we want the model to hand over control (i.e., the run-time defense should raise a flag) only when the perturbed example is actually going to cause misclassification. Our result implies that an adversary can cause the model to hand over control to the human driver even when a perturbed input would not have
1% of test inputs where the model is accurate and also locally robust
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 a set M which is the support set of the underlying input distribution that characterizes the learning problem. Although the exact description ofM is unknown, we know that both the training and test data used are inM . In order for a model to 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 input at which the local robustness check fails but if the model were not to reject the input, it would be classified consistently with all valid inputs within an distance. While a 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 utility.
As we discuss in Section 4, 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 are as follows: (1) we describe new attacks, referred 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-art 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 -local robustness, are susceptible to degradation attacks, as they enforce local robustness at all inputs and not just inputs inM; and (4) we discuss two possible defenses against degradation attacks, and evaluate the one based on doubling the radius enforced by certifiably robust models.
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 4, we sketch two defenses against degradation attacks, and concretely evaluate one of these proposals. In Section 5, we describe the related work. Finally, we conclude in Section 6.

heading: 2 REVISITING DEFINITIONS OF ADVERSARIAL ROBUSTNESS
text: A neural classifier f∈Rd→L is a function from a d-dimensional real vector space, Rd, to a finite set of labels, L. The inputs to the classifier are drawn from some distribution with support setM⊆Rd. In other words, the training and test sets are comprised of elements fromM and their corresponding labels. Though the description of M is not available to us, it plays a key role in formalizing the notion of adversarial examples.
An adversarial example for a neural classifier is the result of applying small modifications to a correctly classified valid input such that the modified input is classified incorrectly. Formally, an input is valid if it belongs toM . Definition 1 below, proposed by Szegedy et al. (2014), formalizes the notion of a targeted adversarial example. Definition 1 (Targeted Adversarial Example). Given a neural classifier f∈Rd→L and an input x∈Rd, an input x′ :=x+r is an adversarial example with respect to a target label l∈L, `p metric, and a fixed constant ∈R if the solution r to the following optimization problem is such that ||r||p≤ :
Minimize ||r||p subject to f(x+r)=l and x+r∈ [0,1]d
Untargeted adversarial examples, or simply adversarial examples, are defined similarly except that the constraint f(x+r)=l is replaced with f(x+r) 6=f(x). As stated informally in (Carlini & Wagner, 2017; Szegedy et al., 2014) x needs to be a valid input, i.e., x∈M , for x′ to be an adversarial example. Making this requirement explicit and formal (via set M) is a key step in the design of our degradation attacks.
Algorithm 2.1: Prediction with a certified run-time defense
Inputs: A model f∈Rd→L, an input x′∈Rd, an attack bound ∈R, and a distance metric `p Output: A prediction l∈L ∪ {⊥}
1 PredictWithDefense(f , x′ , , `p): 2 if f is ( ,`p)−locally robust at x′ then 3 return f(x′) 4 else 5 return⊥
A classifier is protected from adversarial examples with respect to a valid input x if it is locally robust at x. As stated in Definition 2, a classifier is locally robust at x, if its prediction does not change in an -ball centered at x.
Definition 2 (Local Robustness). A neural classifier f∈Rd→L is ( ,`p)-locally robust at x∈Rd if,
∀x′∈Rd. ||x−x′||p≤ =⇒ f(x)=f(x′)
The formal notions of validity and local robustness enable us to make the following key observation.
Observation 3. A classifier is protected from all adversarial examples if it is locally robust at all points inM .
Certified run-time defenses. Classifiers, when composed with certified run-time defenses, are guaranteed protection from adversarial examples. These defenses, briefly surveyed in Section 5, detect adversarial examples during model evaluation (or run-time) by checking if the model is locally robust at the input being evaluated. Algorithm 2.1 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 x), and that the adversary may or may not succeed in building adversarial examples (denoted x′) that are -close to x under the `p metric. Given input x′, a certified run-time defense helps decide whether x′ is an adversarial example or not. As described by PredictWithDefense (lines 1-5), the defense mechanism is first used to check if the model f is locally robust at x′ (line 2). If the check passes, then x′ is guaranteed to not be an adversarial example and the model prediction at x′ is 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⊥ label (line 5).

heading: 3 DEGRADATION ATTACKS
text: 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, in Section 3.3, we evaluate our attacks empirically.

heading: 3.1 AN EXAMPLE OF A CERTIFIED DEFENSE FAILURE
text: Certified run-time defenses can erroneously flag a non-adversarial input as adversarial because they enforce local robustness at all inputs and not just inputs inM . Consider the example in Figure 1. x is a valid input fromM . Let us assume that none of the points in the gray region belong toM . A binary classifier f∈R2→{W,G} assigns labelW 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′ are apart and the radius for both the circles is . The ( , l2)local robustness check at x′ will fail since the -ball centered at x′ includes white and gray points. However, x′ is not an adversarial
Algorithm 3.1: Degradation attack algorithm
Inputs: A model f∈Rd→L, an input x∈M , an attack bound ∈R, and a distance metric `p Output: An attack input x′∈Rd
1 DegradationAttack(f , x , , `p): 2 x′′ := Attack(f,x,2 ,`p) 3 x′ := Project(x,x′′, ,`p) 4 return x′
Algorithm 3.2: Smoothed projected gradient descent attack (SPGD)
Inputs: A model f∈Rd→R|L| mapping inputs to logit outputs, a loss function L, an input x∈M , an attack bound ∈R, a distance metric `p, a step size η, a number of stepsN , a number of samples n, and a noise parameter σ Output: An attack input x′∈Rd
1 SmoothedPgdAttack(f , L , x , , `p , η , N , n , σ): 2 x′ :=x 3 for 0 ≤ step < N do 4 ζ ∼ N (0,σ)n×d
5 x′ :=x′+∇x′L ( 1 n ∑ if(x ′+ζi) ) 6 x′ := Project(x,x′, ,`p) 7 return x′
input since it shares its label with all the -close inputs inM . Consequently, the model rejection of x′ is unnecessary and causes a degradation in model utility. This happens even if the local check is precise and the bound is tight

heading: 3.2 ALGORITHMS
text: Algorithm 3.1 describes a simple degradation attack against a deterministic defense. Intuitively, given a valid input x (on which the classifier f is ( ,`p)-locally robust, for some fixed and distance metric `p), we want to find an input x′ such that ||x−x′||p≤ and the classifier f is not ( ,`p)-locally robust at x′. The attack re-purposes existing white-box attack algorithms (like Carlini-Wagner (Carlini & Wagner, 2017) and PGD (Madry et 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 a ball of radius 2 centered at x (line 2). Next, x′′ is simply projected onto the -sphere centered at x (line 3). For `2, Project is defined as x+min{ , ||x′′−x||p}· x ′′−x ||x′′−x||p , whereas for `∞ we simply need to clip x ′′.
Attacking stochastic defenses. Stochastic defenses, such as randomized smoothing, transform a base classifier into a smoothed classifier by convolving the base classifier with a Gaussian distribution. The smoothed classifier does not have an explicit representation, and to evaluate it on a single input, the base classifier needs to evaluated on as many as 100,000 samples (Cohen et al., 2019). Moreover, the lack of explicit function representation precludes the use of off-the-shelf white-box attack algorithms that perform gradient descent in the input space. While one could simply perform a standard white-box attack on the base classifier, we found it was more effective to implicitly attack the smoothed model by taking the average gradient over a set of randomly generated samples at each gradient descent step. This gives us a “smoothed PGD” (SPGD) attack tailored for use against stochastic defenses. Our SPGD procedure is given in Algorithm 3.2.
Note that Algorithms 3.1 and 3.2 are only meant to serve as proofs-of-concept for degradation attacks. As our empirical results in Section 3.3.1 demonstrate, even these simple algorithms can be highly effective in degrading model utility.

heading: 3.3 EVALUATING ATTACK EFFICACY
text: 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., 2021) 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 `2 metric, on a variety of popular image classification datasets like MNIST (LeCun et al., 2010), CIFAR-10 (Krizhevsky, 2009), and ImageNet (Deng et al., 2009).
GloRo Nets incorporate global Lipschitz bound computation into the model architecture. The global Lipschitz bound is used to implement the local robustness check at an input under evaluation. Moreover, these local robustness checks are backpropagated over during training to encourage learning of models with a high degree of robustness. In contrast, randomized smoothing transforms a base classifier into a 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 radiusR of the smoothed classifier at a given input, so an ( ,`2)-local robustness check simply amounts to checking if the radiusR at the evaluated input is greater than or not. RadiusR is only probabilistically valid, so all the results for randomized smoothing in this section are also probabilistic statements. However, this probabilistic nature ofR 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-style attacks in general. Our second set of experiments, described in Section 3.3.2, measure the susceptibility of models to degradation attacks assuming an all-powerful adversary, i.e., an adversary that succeeds whenever the model is susceptible to a 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 a particular model with a certified run-time defense and a dataset, we construct two subsets of the test set for the given dataset, that we refer to as testR and testA. The former, testR, is the set of test inputs on which the model is certified to be ( ,`p)-locally robust. To construct testR, we simply apply the ( ,`p)-local robustness check at every input in the test set. If the check passes at an input x, it is added to testR. The latter, testA, is a subset of testR, constructed using a degradation attack, such that for each input x∈ testA the model is certified ( ,`p)-locally robust at x but there exists an input x′ in the -ball centered at x such that the model cannot be certified ( ,`p)-locally robust at x′. 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 no other point of a different class label inM that is -close to x′). 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 |testA|/|testR| represents the false positive rate of the certified run-time defense, i.e., the rate at which the certified defense erroneously causes the model to 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 a 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 code2. 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 ( =0.3), the model has two convolution layers and two fully-connected layers (2C2F), for MNIST ( =1.58), the model is 4C3F, and for CIFAR-10 ( =0.141), the model is 6C2F. For CIFAR-10, the randomized smoothed model uses a 110-layer residual network as the base classifier, and for ImageNet, a ResNet-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 i7-7700K with 32 GB of RAM.
2https://github.com/klasleino/gloro 3https://github.com/locuslab/smoothing

heading: 3.3.1 LOWER BOUNDS ON ATTACK EFFICACY
text: 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∈ testR is added to testA if the attack algorithm succeeds in finding an attack input x′ in the -ball at x such that the model cannot be certified robust at x′. Table 1 presents lower bounds on degradation attack efficacy against GloRo Nets, measured by performing our degradation attack described in Algorithm 3.1. Table 2 presents lower bounds on degradation attack efficacy against Randomized Smoothing, measured by performing our SPGD degradation attack described in Algorithm 3.2. We employ the same 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. In some cases the reduction in utility was substantial, with false positive rates at 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 an explicit representation of smoothed models is not available even to a 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 we observe that models trained with a larger noise parameter σ 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 -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.

heading: 3.3.2 UPPER BOUNDS ON ATTACK EFFICACY
text: To compute upper bounds on the efficacy of degradation attacks, i.e., upper bounds on the false positive rates, we construct testA as follows. We apply a (2 ,`p)-local robustness check at every input in testR. If this stronger check passes at an input x, it means that no matter how the adversary perturbs x within the -ball centered at x, the model is always ( ,`p)-locally robust at the perturbed input, and the certified defense (whether complete or incomplete) cannot be forced to unnecessarily reject the input as long as it
satisfies a monotonicity property 4. GloroNets and randomized smoothing are both monotonic in this sense (see Appendix A). However, if the (2 ,`p)-local robustness check fails at x, then even though the model is certified ( ,`p)-locally robust at x, there may exist an input x′ in the -ball at x where the model cannot be certified ( ,`p)-locally robust and an adversary can force an unnecessary rejection. Therefore, if the stronger check fails at x, we add it to testA.
Figures 2a and 2b show the false positive rates at different radii (i.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 2 also reports results for models trained to be robust against twice these values. This is for the purpose of evaluating one of our 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 2c and 2d). By comparing the upper bounds to the lower bounds obtained in Section 3.3.1, we see that our degradation attacks recover between 1/4 and 1/2 of the best possible degradation.
Interestingly the susceptibility to 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 model, yet the CIFAR-10 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 3b show the false positive rates at different radii for each of the randomized smoothed models. Again, the false positive rates are high and approach one as increases. Models that are smoothed using larger σ values unsurprisingly demonstrate more resilience to degradation attacks at the cost of a reduced VRA (Figures 3c and 3d). The sudden jumps in the false positive rate to one indicate the value where all points in testR also end up in testA; i.e., the model is susceptible to degradation attacks at all the points where it is certified locally robust.

heading: 4 DEFENDING AGAINST DEGRADATION ATTACKS
text: In this section, we sketch two possible ways of defending against degradation attacks, and empirically evaluate the effectiveness of our first proposal.
4We say that a certification method cert :Rd×R+→bool is monotonic if, ∀x,x′∈Rd, >0 . cert(x, ) ∧ ||x− x′||p< =⇒ cert(x′, −||x−x′||p).

heading: 4.1 DEFENSE VIA RADIUS DOUBLING
text: 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 a model is 2 robust at a point x inM , then no matter how the adversary perturbs x within the -ball centered at x, the model is always ( ,`p)-locally robust at the perturbed input, and an ( ,`p)-local robustness defense is likely (or even guaranteed, in the case of a complete defense) to not reject the input unnecessarily.
Training a model for 2 -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 -robustness, and may also reject more frequently, even on points inM . But validating the model against 2 is certainly helpful. The 2 -VRA on validation data is a lower bound on the accuracy one can expect on test data, in the face an -adversary capable of adversarial as well as degradation attacks. This also suggests that, when evaluating certified defenses, one ought to report not just -VRA, but also 2 -VRA. Validating against 2 can also help in configuring the certified run-time defense. In case the rejection rate is too high at a particular 2 , the certified defense can be configured to enforce local robustness at a smaller value. This reduces vulnerability to degradation attacks at the cost of an increased vulnerability to adversarial attacks.
We evaluate this defense strategy on GloRo Net models using the same architectures and datasets as in Section 3.3. However, we re-train all the models using twice the values that we want to defend against. Figure 2 summarizes the results. We see that training against 2 -robustness helps reduce the false positive rates compared to the models trained against -robustness. Moreover, this improvement is achieved without significantly affecting the VRA of the models. These results suggest that training against 2 -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, σ, 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 σ≈ /2. Table 2 shows that by increasing σ beyond this point, one can obtain better resistance to degradation. However, as Figures 3c and 3d show, increasing σ also negatively impacts utility.

heading: 4.2 DEFENSE VIA AN M -MEMBERSHIP ORACLE
text: Certified run-time defenses which rely on local robustness checks are susceptible to degradation attacks because these defenses are overly strong, i.e., they try to enforce local robustness at all evaluated inputs, even though they only need to enforce local robustness at inputs inM . To ‘fix’ these certified defenses, instead of checking local robustness at the given input x′, one could instead check if x′ shares its label with all the inputs inM that are -close to x′. If the check passes, then x′ is guaranteed to be a non-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 x∈M that is -close to x′ and is labeled differently from x′. To implement our proposed fix, we would need an explicit representation forM , or at least an oracle for membership inM . A membership oracle may be used to search for members ofM that are -close to a given x′. 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∈M such that x is -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 xwithin the budget, we can fall back to checking local robustness at x′. Practically, one could use an Out-of-Distribution (OOD) detector as anM-membership oracle. Although OOD detectors can be imprecise and susceptible to adversarial attacks themselves (Sehwag et al., 2019; Bitterwolf et al., 2020), some recent developments (Chen et al., 2020) look promising. We leave this for future work.

heading: 5 RELATED WORK
text: The discovery of adversarial examples has led to 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 a neural classifier. However, only constant functions are locally robust everywhere, so
this definition fails to capture the notion of a classifier free from adversarial examples. Leino et al. (2021) propose the notion of global robustness for classifiers that are allowed to reject inputs. They define global robustness as having a margin (predicted as ⊥ or rejection) of sufficient width between classes. Their observation is that checking points for -local robustness corresponds to a margin of width 2 ; i.e., there is a factor of two difference when referring to global vs. local robustness. Moreover, Yang et 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. A 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 a 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 to 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 -ball centered at the original input. Some popular and successful attack algorithms of this nature include the ones proposed by Goodfellow et al. (2015), Carlini & Wagner (2017), and Madry et al. (2018). Black-box attacks only assume query access to the model (Papernot 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.
Heuristic 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-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 a variety of approaches that include constraint solving and formal methods (Huang et al., 2017; Katz et al., 2017; Gehr et al., 2018; Singh et al., 2019), optimization (Bastani et al., 2016; Dvijotham et al., 2018; Raghunathan et al., 2018; Wong & Kolter, 2018; Tjeng et al., 2019), Lipschitz bounds computation (Weng et al., 2018; Leino et al., 2021), and stochastic smoothing (Lecuyer et al., 2019; Cohen et al., 2019; Yang et al., 2020a). 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 et 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 a 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 it works in cases that CERTIFY does not abstain and is able to reliably compute the prediction and the certified radiusR, but this radius may be smaller than the desired for inputs that are in fact non-adversarial.

heading: 6 CONCLUSION
text: 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 a 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-art certifiably robust models, like randomized smoothed models and GloRo Nets, are highly susceptible to utility degradation attacks.
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 https://github.com/locuslab/smoothing. For the experiments with GloRo Nets, we trained the models using the publicly available code for training GloRo Nets at https://github. com/klasleino/gloro.
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.

heading: A MONOTONICITY OF LOCAL ROBUSTNESS CERTIFIERS
text: Definition 4 (Monotonicity of local robustness certifiers). We say that a certification method cert : Rd×R+→bool is monotonic if
∀x,x′∈Rd, >0 . cert(x, ) ∧( ||x−x′||p=δ)< =⇒ cert(x′, −δ)
Definition 5 (Exact local robustness certifier). An exact certification method is one for which cert(x, ) ⇐⇒ ∀x′ ∈ Rd.||x−x′||p ≤ =⇒ F(x) = F(x′) (in other words, certification is equivalent to local robustness).
Lemma 6. All exact certification methods are monotonic.
Proof. This follows essentially from the triangle inequality. Let x ∈ Rd and > 0, and suppose that cert(x, ). Thus, since cert is exact, we have that ∀x′∈Rd . ||x−x′||p≤ =⇒ F(x)=F(x′).
Consider x′∈Rd for which ||x′−x||≤ , and let δ= ||x−x′||. Now for x′′∈Rd, assume ||x′−x′′||≤ −δ. Thus,
≥ δ+||x′−x′′||+δ = ||x−x′||+||x′−x′′|| ≥ ||x−x′′|| by the triangle inequality.
Thus, because we have cert(x, ), we may conclude that F(x′)=F(x)=F(x′′). This tells us that the classifier F is ( −δ)-locally robust at x′, which, by completion gives us cert(x′, −δ).
Definition 7 (Lipschitz-based local robustness certifier). A Lipschitz-based certification method is one which, given an upper bound,Kij(x, ) on the local Lipschitz constant of the margin fj−fi at x,5 certifies a point x, where F(x)=j, exactly when
max i6=j
{ fi(x)+ Kij(x, ) } ≤ fj(x).
Lemma 8. All Lipschitz-based certification methods are monotonic.
Proof. Let Kij(x, ) be an upper bound on the Lipschitz constant of the function fj(x)−fi(x). That is, Kij(x, ) is the maximum rate of change of fj(x)−fi(x) within an `p ball of radius centered at x.
Let x∈Rd and > 0, and suppose that cert(x, ). Consider x′ ∈Rd for which ||x′−x|| ≤ , and let δ= ||x−x′||. We begin with the observation that the `p ball of radius centered at x—we will denote this asB(x, )— containsB(x′, −δ). This, too, follows essentially from the triangle inequality:
z∈B(x′, −δ) =⇒ ||x′−z||≤ −δ= −||x−x′|| =⇒ ||x−x′||+||x′−z||≤ =⇒ ||x−z||≤ by the triangle inequality =⇒ z∈B(x, )
From this, we conclude that Equation 1 holds.
Kij(x, )≥Kij(x′, −δ) (1)
With this in mind, we proceed as follows. Let j=F(x); i.e. j is the class predicted by the classifier at x. Since cert(x, ) implies that the classifier is -locally-robust at x, and x′∈B(x, ), we conclude that F(x′)=j.
Because we assume that cert is Lipschitz-based (Definition 7), we have Equation 2.
∀i 6=j . fj(x)−fi(x)≥ Kij(x, ) (2)
5note that the global Lipschitz constant is such a bound
Since ||x−x′||=δ< , by the definition ofKij we have that ∀i 6=j . fj(x′)−fi(x′) ≥ fj(x)−fi(x)−δKij(x, )
≥ Kij(x, )−δKij(x, )=( −δ)Kij(x, ) by Equation 2 ≥ ( −δ)Kij(x′, −δ) by Equation 1
This is sufficient to conclude that we have cert(x′, −δ).
GloRo Nets are Lipschitz-based, therefore they are monotonic by Lemma 8. Aside from the fact that nondetermism/uncertainty arises because of the need to sample to evaluate the smoothed function, Randomized 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 in 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.

heading: B LOWER BOUNDS ON ATTACK EFFICACY (MORE RESULTS)
text: B.1 EFFICACY OF -PGD 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 is replaced by a call to the PGD algorithm Madry et al. (2018) with an bound instead of a 2 bound. The attack input x′′ returned by an -bounded PGD is guaranteed to be within the -ball centered at x, so we no longer need to project x′′ as in 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 are the same as used for evaluating the efficacy of Algorithm 3.1. The efficacy of an -PGD attack is similar to Algorithm 3.1 (presented in Table 1).
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 to have successfully delivered an imperceptible attack.

heading: C DEGRADATION ATTACKS AGAINST `∞ DEFENSES
text: In this section, we evaluate the efficacy of degradation attacks against models defended with a `∞ certified defense. In particular, we consider models trained and defended using the convex outer adversarial polytope
approach of Wong & Kolter (2018), that we refer to as KW. We compute lower and upper bounds in a similar manner as described in Section 3.3, using KW for the ( ,`∞)-local robustness check. For the lower bounds, the set testA is constructed using Algorithm 3.1 where Project is implemented by clipping x′′.
Table 4 reports the lower bounds, i.e., the efficacy of Algorithm 3.1 against KW. Table 5 reports the upper bounds. We see that `∞ defenses like KW are extremely susceptible to degradation attacks—the simple attack given by Algorithm 3.1 succeeds approximately 92% of the time, and the upper bounds indicate that it may be possible for a more sophisticated adversary to succeed 100% of the time.
While striking, these results are not entirely unexpected, given the geometry of `∞ space. Defenses based on robustness certification are susceptible to degradation attacks unless the underlying model is (2 , `p)-robust. In `∞ space, the volume contained by a ball overlaps much more closely with [0,1]d (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 √ d before it necessarily envelops the entire domain.

Review summaries:
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.