# Is Certifying $\ell_{p}$ Robustness Still Worthwhile?

Ravi Mangal  Klas Leino  Zifan Wang  Kai Hu  Weicheng Yu  Corina Păsăreanu
Anupam Datta  Matt Fredrikson

###### Abstract

Since the discovery of adversarial examples a decade ago, the topic of machine
learning models’ resistance to being manipulated by malicious input
perturbations—a property generally known as adversarial robustness—has
garnered significant attention. Over the years, researchers have developed
myriad attacks that exploit the ubiquity of adversarial examples, as well as
defenses that aim to guard against the security vulnerabilities posed by such
attacks. Of particular interest to this paper are defenses that provide
provable guarantees against the class of $\ell_{p}$-bounded attacks. Certified
defenses have made significant progress, taking robustness certification from
toy models and datasets to large-scale problems like ImageNet classification.
While this is undoubtedly an interesting academic problem, as the field has
matured, its impact in practice remains unclear, thus we find it useful to
revisit the motivation for continuing this line of research. There are three
layers to this inquiry, which we address in this paper: (1) why do we care
about robustness research? (2) why do we care about the $\ell_{p}$-bounded
threat model? And (3) why do we care about certification as opposed to
empirical defenses? In brief, we take the position that local robustness
certification indeed confers practical value to the field of machine learning.
We focus especially on the latter two questions from above. With respect to
the first of the two, we argue that the $\ell_{p}$-bounded threat model acts
as a minimal requirement for safe application of models in security-critical
domains, while at the same time, evidence has mounted suggesting that local
robustness may lead to downstream external benefits not immediately related to
robustness. As for the second, we argue that (i) certification provides a
resolution to the cat-and-mouse game of adversarial attacks; and furthermore,
that (ii) perhaps contrary to popular belief, there may not exist a
fundamental trade-off between accuracy, robustness, and certifiability, while
moreover, certified training techniques constitute a particularly promising
way for learning robust models.

Machine Learning, ICML

##  1 Introduction

The discovery of adversarial examples (Szegedy et al., 2013)—slightly
perturbed versions of natural inputs that can fool well-trained, highly-
performant classifiers into misclassification—marked a significant moment in
the history of deep learning, alerting us to the brittleness of these methods.
In the ensuing decade, there has been intense research on theoretically
understanding the underlying reasons for the existence of such adversarial
examples (Vardi et al., 2022; Frei et al., 2023), though a full understanding
remains out of reach. At the same time, we have witnessed a cat-and-mouse game
between attackers and defenders: attackers propose ever stronger attacks that
exploit this vulnerability while defenders present techniques for safeguarding
models against such attacks.111A conservative estimate suggests that the
number of papers on arXiv related to adversarial robustness is likely to
exceed 8,000 by the year 2024 (car, ). The attacks studied in the literature
typically assume _norm-bounded adversaries_ , i.e., adversaries that are
restricted to input perturbations within a bounded $\ell_{p}$ ball while the
general goal of the defenses is to ensure that models are locally robust,
i.e., not susceptible to adversarial perturbations (formally written in Def.
2.1), at all in-distribution points.

Table 1: Summary of our viewpoints. Section 3: Why do we care about robustness research? | a) The absence of robustness leads to security issues.
---|---
b) Robustness is necessary for conceptual soundness.
c) Scaling does not ensure robustness.
d) Robustness can improve system-level safety.
Section 4: Why do we care about $\ell_{p}$ robustness? | a) $\ell_{p}$ robustness is the bedrock for non-$\ell_{p}$ robustness.
b) Semantic similarity cannot be formalized.
c) $\ell_{p}$ robustness leads to other desirable model properties.
Section 5: Why do we care about certification? | a) Clarification on useful notions of certification.
b) Certifying robustness is a way to escape the cat-and-mouse game
via post-training and inference-time formal guarantees.
c) There is no theoretical trade-off between accuracy,
robustness, and certifiability via Lipschitzness.

The massive body of research on adversarial attacks and defenses has been
guided by some basic underlying assumptions:

  1. 1

Adversarially robust models are desirable.

  2. 2

Norm-bounded adversaries are worth studying.

  3. 3

Certified defenses, if feasible, can end the cat-and-mouse game between
attackers and defenders.

Though the extensive use of these assumptions in the literature might suggest
a universal consensus amongst the community about their validity, we find it
useful to revisit these assumptions, particularly in light of the fact that
impact of this research in practice is unclear—models continue to be
susceptible to adversarial examples yet practitioners are willing to deploy
these models in production systems, and certified defenses are not widely
adopted. While the problems posed by the existence of adversarial examples are
technically challenging and academically interesting, might it be the case
that they are of limited practical relevance and not worthy of the resources
invested by the academic community?

Consider assumption 1. While robustness may seem like an obviously desirable
property given the existence of adversarial examples, the situation is more
nuanced in practice. Machine learning models are rarely used in isolation;
instead, they are typically deployed as components of larger systems, for
instance, as the perception module in a cyber-physical system, or as the
recommendation module in a socio-technical system. Does robustness of the
model enable safe, secure and correct behavior of the larger system? The
usefulness of model robustness as a desirable property hinges on the answer to
this relatively unexplored question. On the other hand, concerns about 2,
i.e., a threat model that only allows norm-bounded adversaries have been
repeatedly raised in the literature (Gilmer et al., 2018; Hendrycks et al.,
2021b). Such a threat model is simultaneously too weak, since it artificially
constraints the adversary in a way that real-world adversaries are not
constrained, and too strong, since it allows adversaries to arbitrarily
perturb inputs in an $\ell_{p}$ ball which requires adversaries to have
complete control over the inputs to the model. We engage with both these
assumptions in this paper (Sections 3 and 4, respectively) and argue for their
validity.

The last assumption, 3, just like the first assumption, seems obviously valid
at face value; after all, by definition, a certified defense ought to protect
against any norm-bounded adversary. Indeed, if a model is certified
$\epsilon$-locally robust at a point $x$ (with respect to some $\ell_{p}$
norm), no $\epsilon$-bounded perturbation of $x$ can affect the model output
and thus, the model is protected from any norm-bounded adversary at $x$.
However, this is only a _local_ guarantee. What is the guarantee provided by a
certified defense on the global model behavior? While we believe that the
community is aware of the nature of the global guarantee, a precise
formalization of the guarantee has been lacking in the literature. We provide
such a definition in Section 5.2. At the same time, the notion of certified
defense itself can be ambiguous and can mean different things in different
contexts. Certified defense may refer to training the model such that the
worst-case loss of the model is minimized (Wong et al., 2018; Gowal et al.,
2018a; Leino et al., 2021). It may also refer to evaluating the percentage of
points in the test dataset where the trained model is accurate as well as
certifiably robust (giving an estimate of the model accuracy on unseen data in
the presence of an adversary) (Zhang et al., 2018; Wang et al., 2021; Katz et
al., 2019; Brix et al., 2023). Finally, it may refer to an inference-time
certified check for robustness, with the model abstaining from prediction
whenever the check fails (Leino et al., 2022b; Mangal & Pasareanu, 2022;
Tramer, 2022). We clarify the different notions of certifications that apply
at different stages of a model’s lifecycle and the nature of the guarantee
afforded by certification (Section 5.1).

Assumption 3 also touches upon the _feasibility_ of certified defenses. There
is a belief in some quarters of the community that there might be a
fundamental trade-off between accuracy and robustness (Fawzi et al., 2018;
Tsipras et al., 2019; Zhang et al., 2019a). At the same time, local robustness
certification is known to be NP-complete (Katz et al., 2017). We clarify that,
in theory, under mild and realistic distributional assumptions about
separability of differently labeled samples, there is no trade-off between
accuracy, robustness, and efficient certifiability of a model, building upon
the results of (Yang et al., 2020b; Leino, 2023). Moreover, we argue for the
position that incorporating Lipschitz-based certifiers into the training
procedures might be the most promising approach for achieving accurate,
robust, and efficiently certifiable models (Section 5.3).

(a)

(b)

(c)

Figure 1: (a) An adversarial example found in a vision classifier that fools
the model’s prediction (Szegedy et al., 2013). (b) An adversarial audio
example that fools an Automatic Speech Recognition (ASR) model (Hussain et
al., 2021). (c) An example of adversarial suffix jailbreaks aligned LLMs, e.g.
ChatGPT, to elicit harmful outputs (Zou et al., 2023).

##  2 Review of Adversarial Robustness

###  2.1 What Are Adversarial Examples?

Adversarial examples are input instances that are carefully crafted to cause a
machine learning model, especially deep neural networks, to make a mistake in
its prediction. While these perturbations are typically undetectable to the
human eyes in visual contexts, they can lead the model to produce outputs that
are substantially different from the expected predictions. One classic
adversarial example (Fig.1(a)) found by Szegedy et al. (Szegedy et al., 2013)
is that the prediction of an image classifier is easily steered from Panda to
Gibbon when adversarial noise is added to the benign input.

Adversarial examples extend beyond mere images; they permeate nearly every
genre of deep models and data formats. In sentiment analysis for text input,
by swapping specific words with their synonymous counterparts, the adversary
is able to toggle the sentiment prediction (Tsai et al., 2019; Hou et al.,
2023). Similarly, Fig.1(b) shows that by adding adversarial wavelets that are
indistinguishable by human ears to an audio input, the output transcript of an
Automatic Speech Recognition (ASR) model will be manipulated into Cancel my
meeting, whereas it sounds like What is the time? to humans (Hussain et al.,
2021). Although learning theory-based analysis tends to blame the
generalization gap between the training data and all unseen data (including
the adversarial ones) just to the capacity of the model and the suboptimal
optimization (Neyshabur et al., 2017), however, it is worth noting that even
large models have been shown to have remarkable abilities for zero-shot
learning (Kojima et al., 2022), they still fail inevertibly against
adversarial examples. Recent research has shown that even Large Language
Models (LLMs) and large multimodal models, extensively trained with copious
human feedback to align their responses with human ethics and regulations, can
succumb to adversarial manipulations (Maus et al., 2023; Carlini et al., 2023;
Zou et al., 2023; Wei et al., 2023). In Fig.1(c), we use the example presented
by Zou et al. (2023) where the gibberish-style suffix generated by an attacker
aids to break the aforementioned safety guardrail of
ChatGPT222https://chat.openai.com/.

Figure 2: A simplified taxonomy of certification methods based on a full
taxonomy from Li et al. (Li et al., 2023) and recent works that have not been
included yet (Shi et al., 2023; Hu et al., 2023b).

The vulnerability to adversarial examples was initially seen primarily as a
security concern in the machine learning systems, i.e. a bug in the learned
system. However, numerous subsequent studies have highlighted a more profound
issue: failing at adversarial examples is a sign that these networks exhibit
behaviors vastly different from humans (Ilyas et al., 2019; Gavrikov et al.,
2023; Wang, 2023). For instance, while humans identify an image based on its
foreground object and label it as ”Panda” in Fig.1(a), deep learning models
aren’t necessarily constrained to this logic. Towards that end, adversarial
perturbations to those unrelated (i.e. non-robust) features in the input
“hijack” the predictions.

###  2.2 Norm-bounded Adversaries

Unless otherwise specified, we consistently use the terms “model” or “network”
to refer to a “classifier” in this paper. While it is worth noting that
adversarial robustness is a pertinent property of regression models or other
models generating continuous outputs, the precise definition of robustness
tends to vary in each case, contingent upon the specific application of said
continuous output. In contrast, adversarial robustness for classifiers is
consistently defined across publications, as the integer output is universally
interpreted as the category of the input. Moreover, insights from research on
robust classifiers often shed a light on robustness in regressions and related
tasks. Since this paper aims to present perspectives on robustness
certification to a broad research audience, we can focus the discussion on
deep neural network classifiers without loss of generality.

A major line of robustness research focuses on $\ell_{p}$-norm-bounded
adversaries, which is also the focal point of this work. The original
motivation to constrain the perturbations to the input within a small
$\ell_{p}$-ball is to ensure the perturbation is imperceptible to humans.
While this section provides the foundations for $\ell_{p}$-norm constraints
used in the broad adversarial robustness research, Section 4 underpins the
motivation and value of studying this type of adversary, along with a
discussion of the impact of methods motivated by $\ell_{p}$ balls on other
types of adversaries.

In practice, these adversaries search norm-bounded perturbations that turn a
given sample into an adversarial example. Fast Gradient Sign Method
(Goodfellow et al., 2015) was first proposed to find $\ell_{\infty}$-bounded
perturbations. As a more generic and iterative method, Projected Gradient
Descend (PGD) (Madry et al., 2018) is a well-known baseline attack for all
$\ell_{p}$-norm-bounded setup. Follow-up studies (Carlini & Wagner, 2017;
Uesato et al., 2018) proposed to use better optimization methods and different
losses to find higher quality adversarial examples. Auto-attack (Croce & Hein,
2020b), an ensemble of the FAB attack (Croce & Hein, 2020a), the Square Attack
(Andriushchenko et al., 2020) and two PGD attack variants, is widely used to
benchmark the robustness of state-of-the-art robust classifiers (Croce et al.,
2020).

Formally, let $F$ be a neural network that takes an input $x\in X$ and
predicts an integer class $y=F(x),y\in[m]$. The $\ell_{p}$ norm of a vector
$x$ is denoted as $\|x\|_{p}$. Thus, this so-called norm-bounded adversary is
crafting a nearby point $x^{\prime}$ within a $\ell_{p}$-ball of a radius
$\epsilon$, often referred to as the budget of the adversary, centered at $x$.
Common choices of $p$ include $1,2$ and $\infty$. The goal of the defender is
therefore to improve the _local robustness_ (Def. 2.1) of the model at all
relevant inputs.

######  Definition 2.1 ($\epsilon$-Local Robustness).

A model $F:X\rightarrow[m]$ is $\epsilon$-locally robust at $x$ with respect
to norm, $\|\cdot\|_{p}$, if

$\displaystyle\forall x^{\prime}\in X,||x^{\prime}-x||_{p}\leq\epsilon\implies
F(x^{\prime})=F(x).$

###  2.3 Defending Against Adversarial Examples

Models trained to minimize the standar loss functions, e.g. cross entropy, are
generally not robust to adversarial examples. Goodfellow et al. (Goodfellow et
al., 2015) first included adversarial examples into training to defend against
attacks. Two seminar works that become the foundation of _adversarial
training_ includes PGD training (Madry et al., 2018) and TRADES (Zhang et al.,
2019b). Since then, methods for training robust models have been of central
interest to the machine learning community. Probably hundreds or more methods
have been developed since then from many different perspectives, to name a
few, metric learning (Mao et al., 2019; Pang et al., 2019a; Zhou & Patel,
2022), self-supervised learning (Chen et al., 2020; Naseer et al., 2020),
ensemble learning (Tramèr et al., 2017; Pang et al., 2019b) and data
augmentation (Rebuffi et al., 2021; Wang et al., 2023; Hendrycks et al.,
2020).

Adversarial training offers only an empirical robustness guarantee against the
specific attack method used during evaluation. It’s likely that the empirical
robust accuracy (ERA) — which represents the percentage of data points deemed
both correct and robust against the best available attack at testing — serves
merely as an upper-bound for the true robustness of the data. Consequently,
ERA is contingent upon the time of assessment and is specific to a particular
attack or a defined set of attacks. In safety-critical domains especially, a
stronger (or formal) guarantee of robustness is preferred. One solution to
this cat-and-mouse game is to train a model capable of _certifying_ the _local
robustness_ of its predictions within a small neighborhood in the input
space—the main focus of this paper.

Formally, given a classifier $F:X\rightarrow[m]$, an $\epsilon$-bounded local
robustness certifier $C^{F}_{\epsilon}:X\rightarrow\\{0,1\\}$ is a function
that returns a booleen output to indicate if $F$ is locally robust at $x$. A
_sound_ cetifier (Def. 2.2) is therefore free of false positive.

######  Definition 2.2 (Soundness of Certification).

For a classifier $F:X\rightarrow[m]$, a certifier
$C^{F}_{\epsilon}:X\rightarrow\\{0,1\\}$ is sound if $\forall x\in X$,

$\displaystyle C^{F}_{\epsilon}(x)=1\implies F\text{ is $\epsilon$-locally
robust at }x.$

Hereafter, whenever we refer to a certifier, we assume it is sound unless
stated otherwise.

Certifiers can be classified as either _complete_ or _incomplete_ based on the
outcome when $C^{F}_{\epsilon}(x)=0$. Specifically, a _complete_ certifier is
one where an adversarial example is identified through its algorithmic design.
Conversely, a certifier is deemed _incomplete_ if it concludes with
$C^{F}_{\epsilon}(x)=0$ either due to the discovery of an adversarial example
or because it is unable to prove local robustness before reaching a
predetermined termination condition. Therefore, it is important to note that
if $C^{F}_{\epsilon}$ is incomplete, $C^{F}_{\epsilon}(x)=0$ does not imply
that an adversarial example necessarily exists within the $\epsilon$-ball.

(a)

(b)

Figure 3: An illustration of conceptual soundness. (a) Models make predictions
on two inputs and model 2 is clearly wrong for the cat image. (b) Each model’s
internal logic for image predictions is summarized. Model 1 accurately uses
the subject (i.e. the dog), whereas model 2 mistakenly focuses on the tennis
ball, associating it with the dog class. We say in this case model 1 is
conceptuall sound and model 2 is not.

Complete certification is an NP-complete problem for deep neural networks
(Katz et al., 2017). Due to the high computational cost, existing complete
certification methods (Pulina & Tacchella, 2010; Tjeng et al., 2017; Katz et
al., 2017; Wang et al., 2018; Bunel et al., 2020) have difficulty in scaling
to modern networks (Li et al., 2023). Incomplete certifiers can be categorised
into probabilistic and deterministic methods. Probabilistic methods provide
local robustness guarantees with a probability333An acceptable probability is
usually no lower than 99.9% to participate in a public leaderboard
(https://sokcertifiedrobustness.github.io/leaderboard/)., meaning that there
could exist false positive claims. Existing probabilistic methods (Cohen et
al., 2019; Yang et al., 2020a; Jeong et al., 2021; Carlini et al., 2022) add
random noise to smooth classifiers and rely on Monte Carlo sampling to provide
robustness bounds. As a result, these methods require extensive sampling
during the certification process and are thus very expensive; for instance,
they are typically evaluated on a 1% subset of the ImageNet validation set for
timing concerns (Cohen et al., 2019; Carlini et al., 2022; Xiao et al., 2022).
There are a great number of deterministic categories and here we include a few
examples, e.g. internal bound propagation methods (Gowal et al., 2018b;
Morawiecki et al., 2019), linear relaxation methods (Weng et al., 2018; Salman
et al., 2019; Singh et al., 2019; Dvijotham et al., 2018), solving a semi-
definite programming (Dathathri et al., 2020; Fazlyab et al., 2020;
Raghunathan et al., 2018), and using the global Lipschitz bounded networks
(Trockman & Kolter, 2021; Leino et al., 2021; Araujo et al., 2023). A summary
and comparison of certification method is shown in Fig. 2

##  3 Why do we care about robustness research?

In general, the concerns around robustness are uncontroversial, as it is
widely recognized that adversarial examples pose a security vulnerability. For
completeness, we begin with an overview of the common justifications that
ubiquitously motivate the robustness literature. Although it is less
universally acknowledged, in addition to its relation to security, robustness
can be viewed more generally with respect to model quality, as a path to
_conceptual soundness_ —the tendency of a model to use high-level features
that are recognized by humans as appropriate for explaining its inferences. We
also contend with the objection that, despite the importance of robustness as
a model property, _robustness research_ may be redundant from the perspective
of _scaling laws_ , which perhaps suggest that data and model capacity are
sufficient for fixing any model shortcomings. Finally, we discuss some recent
observations from the formal safety analysis of vision-based cyber-physical
systems suggesting that improved robustness of perception models can translate
into improved overall safety of the system in a formally provable sense.

#### Lack of Robustness Is A Security Issue

Clearly, adversarial examples negatively impact the reliability of neural
networks that are vulnerable to them—and constitute a security concern in
safety-critical machine learning systems—as they lead to unexpected erroneous
behavior on seemingly benign inputs. Numerous examples, as listed by Carlini
et al. (2019), have shown that it is possible to generate physical adversarial
examples, e.g. eyeglasses (Sharif et al., 2016, 2017) and T-shirts (Xu et al.,
2020) that fool facial recognition systems, patches that make autonomous
vehicles recognize stop signs as speed limit signs (Eykholt et al., 2018), web
content that causes an ad-blocker to consider an advertisement as neutral
content (Tramèr et al., 2018), etc.

As AI systems get more powerful, their potential misuse can pose a significant
threat, as they can be deliberately employed to instigate widespread damage
(Hendrycks et al., 2023). Modern large models are trained to align with
ethical behaviors (Ziegler et al., 2019; Hendrycks et al., 2021a; Ouyang et
al., 2022) so they reject following harmful instructions, e.g., providing
instructions on creating bio-weapons. However, recent research has shown that
the current aligned models are de-facto not adversarially aligned (Maus et
al., 2023; Carlini et al., 2023; Zou et al., 2023; Wei et al., 2023).
Automated methods are able to break the guardrails and instruct large models
to generate harmful contents for the adversary’s own benefit as is shown in
Fig. 1(c).

#### Robustness Is Necessary for Conceptual Soundness

Consider the thought experiment originally set up by Leino (Leino, 2022) as
illustrated in Fig. 3. Two models in Fig. 3(a) perform image classification,
yet model 2 erroneously categorizes a cat image as a dog. Suppose we are able
to “talk” to the models to discover the most important input features they
rely on to make their predictions. An explanation like the circled features in
Fig. 3(b) would reveal that the error in model 2 arises because it detects a
tennis ball and associates it with the dog class. While tennis balls might be
linked with dogs in the training data, they are not the deciding factor to any
human for distinguishing between cats and dogs. Put differently, a tennis ball
is _not_ a sound concept for classifying cats and dogs. Thus, we will say that
model 2 is not _conceptually sound_. By contrast, model 1 uses appropriate
features to form its internal logic, and can therefore be considered
_conceptually sound_. This quality is essential for trustworthiness in any
machine learning model, even if they perform well otherwise.

Upon closer inspection, it becomes clear that the existence of adversarial
examples in a network must constitute a violation of conceptual soundness. The
adversarial perturbation, which is semantically meaningless by construction,
is nonetheless causally relevant to changing the model’s prediction, as
witnessed by the anomalous prediction it induces. Thus, these adversarial
perturbations can be thought of as corresponding to some ill-conceived concept
that the network erroneously encodes and employs.

#### Scaling Itself Does Not Resolve Lack of Robustness

Arguably, the so-called “renaissance” of machine learning has been driven
first and foremost by the dramatic scaling of model capacity and training set
sizes. Supported conceptually by PAC theories, and empirically by the
impressive and continuous progress made in the last decade, many remain
bullish on the prospect that the power of scaling is far from reaching its
limits. It might seem logical to assume that the absence of adversarial
robustness stems from an insufficiently large training set, which fails to
allow the model to generalize to corner cases, including adversarial examples.
One might hypothesize that by simply enhancing the model’s performance and
generalization, the problem of adversarial susceptibility would dissipate as
both models and dataset sizes scale up.

Counter arguments towards this over-optimistic opinion are two-fold. From a
theoretical perspective, it is often hard to nail down what precisely is
entailed by a training “distribution,” however, it more clear that adversarial
examples are, almost by design, off-manifold points that can not be easily
sampled from distributions of natural inputs. Therefore, it is unclear that
scaling laws driving generalization have meaningful bearing on adversarial
robustness. On the empirical side, evidence from experiments on the current
largest classification models (and generative models) indicate that
adversarial examples still persist, especially when developers rely solely on
the standard training techniques.

#### Robustness Can Improve System-level Safety

Recent works (Calinescu et al., 2022; Păsăreanu et al., 2023) on proving
safety of vision-based cyber-physical systems have observed that higher
accuracy of the models used for vision-based perception can lead to stronger
formal safety guarantees for the overall system. It has also been observed
that, in practice, models trained in a robustness-aware manner show a
correlation between accuracy and robustness (Calinescu et al., 2022)—the model
tends to be more accurate on points where it is locally-robust. These two
observations suggest that improving the robustness of the classifier used for
perception can have a direct impact on the safety of the overall system.

##  4 Why do we care about $\ell_{p}$ robustness?

Constraining adversarial perturbations within a small $\ell_{p}$-ball around a
benign input is inspired by the spirit of perceptual similarity. Often, humans
cannot detect these minuscule changes, so it is desirable for deep models to
emulate this human trait. In other words, if the perturbations are noticeable
to humans and they change the semantic meaning of the input, it wouldn’t be
reasonable to expect the model’s outputs to remain unchanged. Besides this
intuitive motivation, there are a number of other reasons in favor of
researching $\ell_{p}$ robustness.

####  $\ell_{p}$ Robustness Is the Bedrock for Non-$\ell_{p}$ Robustness

An $\ell_{p}$-ball is not the only set that can represent semantic
similarities. For example, in visual object detection, rotations and
translations of objects often do not change what humans would label them with;
however, the rotation set of an image cannot be represented by a
$\ell_{p}$-ball. Similarly, in classifying text data, some gibberish strings
do not directly fit into the $\ell_{p}$-ball of the input. However, methods
developed for $\ell_{p}$ robustness also help to formulate the definitions in
these non-$\ell_{p}$ setups. For example, while the set of rotations of an
image is not an $\ell_{p}$-ball, research works attempt to parameterize the
rotation matrix and bound the corresponding parameters in a $\ell_{p}$-ball
(Wang et al., 2022a; Yang et al., 2023), which also applies to other general
matrix-defined transformations (Dumont et al., 2018; Hao et al., 2022;
Balunovic et al., 2019; Wu et al., 2023; Hsiung et al., 2023). Moreover,
recent findings show that the improved $\ell_{p}$ robustness can lead to the
improved robustness for non-$\ell_{p}$ robustness (Mao et al., 2019; Lin et
al., 2020).

#### General Semantic Similarity Cannot Be Formally Specified and Certified

Specifying the (perceptual) similarity between inputs as $\ell_{p}$ distances
is the cornerstone to develop formal verification tools towards ending the
cat-and-mouse game between attackers and defenders. Arguably, the general
notion of semantic similarity between any two images cannot be specified in a
formal way that can be used for certifying robustness. It is perhaps possible
for image-based searching or contrast learning to use a second deep model to
measure the similarity between pairs of inputs. In this case, the semantic
similarity is not specified but determined with the opaque (and probably not
reliable) inner workings of the judging model. In the worst case, the
adversary can just fool the classifier and the similarity model at the same
time and any certification relying on such judging model is always unsound
(i.e. the certifier may return false negative results).

####  $\ell_{p}$ Robustness Connects to Other ML Fields

Besides adversarial robustness, $\ell_{p}$ robustness can lead to many other
desirable properties such as out-of-distribution robustness (Bitterwolf et
al., 2020; Setlur et al., 2022), improved transfer learning (Deng et al.,
2021; Salman et al., 2020), and increased interpretability and trustworthiness
of the model’s prediction (Wang, 2023; Wang et al., 2022b; Etmann et al.,
2019; Tsipras et al., 2019) as well as help with generalization (Xie et al.,
2020), understanding memorization of training points (Leino et al., 2022a),
learn invertible functions (Behrmann et al., 2019) and build stable GANs
(Zhong et al., 2020).

##  5 Why do we care about certification?

Figure 4: An illustration of the differences between training empirical robust
models and certifiably robust models. AutoAttack (Croce & Hein, 2020b) is a
set of attacks commonly used to report the empirical robust accuracy. Of
particularly note, the process of the certifying robustness is adversary-free,
therefore, the model is guaranteed to be robust at certified points with
future (i.e. unknown) attacks.

Given the arguments in previous sections demonstrating that robustness
research is important and $\ell_{p}$ norm-bounded adversaries represent a
theoretically and practically useful threat model, certification seems
desirable to guarantee protection against such adversaries. However, we
clarify in Section 5.1 that the notion of certification depends on the context
and means different things at different stages of the learning pipeline.
Nevertheless, at each of these stages, certification can yield formal
guarantees that can help escape from the cat-and-mouse game between attackers
and defenders. The nature of these guarantees is made precise in Section 5.2.
Furthermore, in theory, there is no fundamental trade-off between accuracy,
robustness, and efficient certifiability—under mild distributional
assumptions, there always exists a Lipschitz-bounded function that is
perfectly accurate and robust (Section 5.3). We therefore argue that certified
training that incorporates Lipchitz-based certification offers a promising
path towards learning this theoretically feasible and desirable function.

###  5.1 Notions of Certification

Prior to making an argument supporting the utility of robustness
certification, it is worth distinguishing between three particular settings in
which certification may be applied, which correspond to three stages of the
learning pipeline: training, evaluation (post-training, pre-deployment), and
inference (post-deployment). Certification methods may apply to more than one
stage, but not all methods are practically applicable to every stage.
Unsurprisingly, the value of certification depends on the context(s) it can be
applied to. In the remainder of Section 5.1, we will provide a brief overview
of the important distinctions between _certified training_ , _post-training
certification_ , and _inference-time certification_ , allowing us to frame our
discussion of utility accordingly.

#### Certified Training

Certified training refers to any training method that directly or indirectly
incorporates robustness certification into its training objective. Typically,
this involves incorporating a sound certification procedure into the model’s
loss function, however many approaches simply employ heuristics that make
certification with some sound procedure easier. Certified training is
generally used in conjunction with a certification procedure that is applied
post-training and/or at inference time; however, within this paradigm, the
certification procedure may assume control over the structure and parameters
of the model. Generally speaking, not all certification procedures are
amenable to certified training, as training requires differentiability, and
sufficient performance and parallelizability to be practically run over
thousands of batches throughout training.

#### Post-training Certification

Post training certification applies a certification procedure to a validation
dataset in order to estimate the Verified Robust Accuracy (VRA), i.e., the
fraction of points on which the model is both correct _and_ certifiably
robust. Post-training certification can be applied either post hoc (i.e.,
assuming we have no control over the model that must be certified), or in
conjunction with certified training. In the latter case, incomplete certifiers
that would otherwise provide loose robustness guarantees may (and indeed, do)
become highly practical, particularly because of their superior speed (Gowal
et al., 2018a; Leino et al., 2021). Moreover, while post-training
certification does not necessitate “real-time” performance, complete
methods—exponential by nature—may be intractable, harming the measured VRA
whenever the procedure fails to terminate.

#### Inference-time Certification

Inference-time certification provides additional security for an ML-based
system during deployment by using a certification procedure to produces a
point-wise robustness certificate to accompany each prediction. The
certificate can be handled by the system in various ways, e.g., by rejecting
inputs that cannot be certified, or by flagging them for human involvement.
Like post-training certification, inference-time certification can be applied
post hoc, or in conjunction with certified training. Typically, methods
capable of post-training certification can also be applied at inference time;
however, in deployment settings, performance (in terms of speed) is often
indispensable, thus “real-time” methods are typically required.

We contend that _certification is primarily useful within the certified-
training paradigm_. While post hoc certification is an interesting research
problem, the inability to apply tailored regularization to the model being
certified kneecaps our ability to leverage highly efficient (but incomplete
and potentially loose) certification procedures, which have the speed to make
inference-time certification practical. Meanwhile, complete certification is
known to be NP-complete on general networks (Katz et al., 2017), severely
limiting the application of complete post hoc methods in practice, especially
at inference time. For a sense of scale, state-of-the-art post hoc
certification techniques can require as much as _five minutes_ per instance to
be able to terminate on up to 80% of instances on a small, adversarially
trained ResNet architecture (Bak et al., 2021). Moreover, where comparable,
the VRAs reported for top certified training procedures substantially surpass
those recorded for post hoc certification of adversarially trained
networks.444See (Li et al., 2023) for an overview of state-of-the-art VRA for
various datasets, $\ell_{p}$ norms, and perturbation budgets. These can be
compared to VRA numbers reported in the VNN-COMP neural network verification
competition (Bak et al., 2021). Notably, VNN-COMP only evaluates against
$\ell_{\infty}$ perturbations, which can be analyzed by IBP techniques; no
post hoc certification method has recorded nontrivial results for $\ell_{2}$
perturbations on adversarially trained models of the scale presented in VNN-
COMP.

On the other hand, as we will discuss in Section 5.3, tailored certified
training techniques are a promising avenue for achieving _higher_ VRA with
real-time certification procedures. Overall, these considerations suggest that
efforts that focus only on post-training robustness certification are overly
narrow.

###  5.2 Empirical vs Certified Defenses: Escaping the cat-and-mouse game

In this section, we discuss the reasons for preferring certified defenses over
empirical ones in the post-training and post-deployment (i.e., inference-time)
phases of the model lifecycle. An oft-cited reason in the robustness
literature in the favor of certified defenses is that they help escape the
cat-and-mouse game between norm-bounded adversaries and defenders—
certification ensures that no norm-bounded adversary can successfully attack
the model. Indeed, if a model is certified $\epsilon$-locally robust at a
point $x$ (with respect to some $\ell_{p}$ norm), no $\epsilon$-bounded
perturbation of $x$ can affect the model output and the model is protected
from any norm-bounded adversary at $x$. This, however, is a _local_ guarantee.
We find that the nature of the _global_ guarantee granted by certification is
often left unspecified in the literature. In addition, as discussed in Section
5.1, the notion of certification itself can mean different things depending on
the context. We clarify and formally express the guarantees realized via
certification here.

#### Post-training Certification

The goal of post-training certification is to _measure_ the percentage of
points in a held-out dataset where the model is both accurate and certified as
$\epsilon$-locally robust. This percentage, usually referred to as the
empirical Verified Robust Accuracy ($\overline{\texttt{VRA}}$), can help
estimate the model accuracy on unseen data in the presence of any norm-bounded
adversary. $\overline{\texttt{VRA}}$ on a dataset $d$ with $n$ labeled
$(x_{i},y_{i})$ pairs is defined as

$\overline{\texttt{VRA}}(F,d):=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}_{F(x_{i})=y_{i}\wedge
C^{F}_{\epsilon}(x)=1}.$

where $C^{F}_{\epsilon}$ is a complete or incomplete certifier.

The corresponding definition of Verified Robust Accuracy (VRA), in
expectation, with respect to a distribution $\mathcal{D}$ is

$\texttt{VRA}(F,\mathcal{D}):=\underset{x\sim\mathcal{D}}{\mathbb{E}}[\mathbbm{1}_{F(x)=F^{*}(x)\wedge
C^{F}_{\epsilon}(x)=1}]$

Theorem 5.3 formally states the relationship between VRA of the model on the
non-perturbed distribution $\mathcal{D}$ and its accuracy
(Acc555$\texttt{Acc}(F,\mathcal{D}):=\underset{x\sim\mathcal{D}}{\mathbb{E}}[\mathbbm{1}_{F(x)=F^{*}(x)}]$)
with respect to all possible perturbations of $\mathcal{D}$ (see Def. 5.1)
that can be the result of a norm-bounded adversary.

######  Definition 5.1 (Perturbations of a Distribution).

Let $\mathcal{D}$ be a distribution over $X$,
$B_{\epsilon}:=\\{v~{}|~{}||v||_{p}\leq\epsilon\\}$ be the ball of norm
$\epsilon$-bounded vectors, and
$\Delta_{\epsilon}:=\\{\Delta~{}|~{}\texttt{supp}(\Delta)\subseteq
B_{\epsilon}\\}$ be the set of all distributions whose support is in
$B_{\epsilon}$. Then the set $\texttt{Per}_{\epsilon}({\mathcal{D}})$ of
perturbed distributions with respect to $\mathcal{D}$ that are the result of
any norm-bounded adversary is defined as:

$\displaystyle\texttt{Per}_{\epsilon}(\mathcal{D}):=\\{x\sim\mathcal{D};\delta\sim\texttt{Adv}(x);$
$\displaystyle\text{return }(x+\delta)~{}|$ $\displaystyle\texttt{Adv}\in
X\rightarrow\Delta_{\epsilon}\\}$

Adv represents a norm-bounded adversary that maps each input to a perturbation
distribution (for a deterministic adversary, this is a Dirac delta
distribution) from $\Delta_{\epsilon}$.

Theorem 5.3 uses the notion of a distribution $\mathcal{D}$ being
$\epsilon$-separable with respect to a classifier $F:X\rightarrow[m]$.
Intuitively, if any pair of points in the support of $\mathcal{D}$ (denoted as
$\texttt{supp}(\mathcal{D})$) are assigned different labels by $F$, then, for
$\mathcal{D}$ to be $\epsilon$-separable, the points should be at least
$2\epsilon$ apart. Def. 5.2 states this formally.

######  Definition 5.2 ($\epsilon$-Separability).

Let $F:X\rightarrow[m]$ be a classifier and $\mathcal{D}$ be a distribution
over $X$. Then $\mathcal{D}$ is $\epsilon$-separable with respect to $F$ if,

$\forall x,x^{\prime}\in\texttt{supp}(\mathcal{D}).~{}F(x)\neq
F(x^{\prime})\implies||x-x^{\prime}||_{p}\geq 2\epsilon$

######  Theorem 5.3 (Post-training Certification).

Let $F:X\rightarrow[m]$ be a classifier, $F^{*}:X\rightarrow[m]$ be the
corresponding ground-truth labeling function, and $\mathcal{D}$ be an
$\epsilon$-separable distribution over $X$ wrt $F^{*}$ from which unperturbed
inputs for the classification task are drawn. If $\forall
x\in\texttt{supp}(\mathcal{D}),F^{*}(x)\text{ is }\epsilon\text{-locally
robust}$, then

$\forall\mathcal{D}^{\prime}\in\texttt{Per}_{\epsilon}(\mathcal{D}).~{}\texttt{VRA}(F,\mathcal{D})\leq\texttt{Acc}(F,\mathcal{D}^{\prime})$

###### Proof.

Let $\mathcal{D^{\prime}}$ be an arbitrary distribution from
$\texttt{Per}_{\epsilon}(\mathcal{D})$.

$\displaystyle\texttt{Acc}(F,\mathcal{D^{\prime}})$
$\displaystyle=\underset{x\sim\mathcal{D^{\prime}}}{\mathbb{E}}[\mathbbm{1}_{F(x)=F^{*}(x)}]$
$\displaystyle=\underset{x\sim\mathcal{D},\delta\sim\texttt{Adv}(x)}{\mathbb{E}}[\mathbbm{1}_{F(x+\delta)=F^{*}(x+\delta)}]~{}(\text{Definition
of }\mathcal{D^{\prime}})$
$\displaystyle=\underset{x\sim\mathcal{D},\delta\sim\texttt{Adv}(x)}{\mathbb{E}}[\mathbbm{1}_{F(x+\delta)=F^{*}(x)}]~{}(F^{*}\text{
is locally robust})$
$\displaystyle\geq\underset{x\sim\mathcal{D}}{\mathbb{E}}[\underset{\delta\in
B_{\epsilon}}{\min}[\mathbbm{1}_{F(x+\delta)=F^{*}(x)}]]~{}(\text{Worst-case
perturbation})$
$\displaystyle\geq\underset{x\sim\mathcal{D}}{\mathbb{E}}[\mathbbm{1}_{F(x)=F^{*}(x)\wedge
C^{F}_{\epsilon}(x)=1}]$ $\displaystyle=\texttt{VRA}(F,\mathcal{D})$

∎

Theorem 5.3 states that the VRA of the model gives a lower bound on the
expected accuracy in the presence of a norm-bounded adversary. No matter how
the adversary perturbs the samples, the accuracy of the model can never be
worse than the VRA on the original distribution. This result holds under a
mild assumption about the data distribution $\mathcal{D}$ and the ground-truth
labeling function $F^{*}$. The assumption states that every pair of points in
the support of $\mathcal{D}$ with different ground-truth labels are separated
by at least $2\epsilon$ and furthermore, the ground-truth labeling function is
$\epsilon$-locally robust at every such point in the support of $\mathcal{D}$.
The $\epsilon$-separability assumption is empirically well-motivated (Yang et
al., 2020b); in fact, if this assumption is not true, then there is always an
inherent trade-off between robustness and accuracy of the model. The second
part of the assumption is a basic motivation for aiming to learn robust
classifiers and is feasible due to the $\epsilon$-separability of
$\mathcal{D}$.

In contrast, when using empirical defenses, one measures the percentage of
points in the held-out dataset where the model is accurate and not susceptible
to misclassification subjected to a _fixed_ set of attacks, often referred to
as the Empirical Robust Accuracy of the model ($\overline{\texttt{ERA}}$).
However, $\overline{\texttt{ERA}}$ and its corresponding version in
expectation, i.e., ERA, can only guarantee model accuracy with respect to the
fixed set of attacks considered but not with respect to any norm-bounded
adversary.

Note that the theorem relates VRA with the accuracy of the model on perturbed
samples but we are only able to measure $\overline{\texttt{VRA}}$. However,
$\overline{\texttt{VRA}}$ and VRA are related via standard statistical results
such as Hoeffding’s Inequality.

#### Inference-time Certification

A model with inference-time certification takes the following form,

$F^{\bot}(x)~{}:=~{}\text{if }(C^{F}_{\epsilon}(x)=1)\text{ then }F(x)\text{
else }\bot$

where $F$ is the model and $C^{F}_{\epsilon}$ is the local robustness
certification procedure. Consider the case where $C^{F}_{\epsilon}$ returns 1,
i.e., the model is certified $\epsilon$-locally robust at $x$. In this case,
even if $x$ is an adversarially perturbed input, we are guaranteed that the
model prediction at $x$ is the same as the original unperturbed input. In this
sense, no matter how the norm-bounded adversary generated the perturbed input
$x$, the certification guarantees that the model is unaffected by the
adversarial intervention whenever the check passes666A failure of the check
does not come with any guarantee, and can, in fact, be exploited by an
adversary to degrade model utility (Leino et al., 2022b). In contrast, an
empirical check of $\epsilon$-local robustness or any other inference-time
empirical defense based on “purifying” or modifying the input before the model
accesses it (Croce et al., 2022; Frosio & Kautz, 2023) cannot guarantee that
the model prediction is unaffected by an adversary. Theorem 5.4 formally
expresses this guarantee.

######  Theorem 5.4 (Inference-time Certification).

Given a model $F^{\bot}$ with inference-time certification, the following
holds $\forall x\in X$,

$F^{\bot}(x)\neq\bot\implies x\text{ is not an adversarial example}.$

###### Proof.

Assume $F^{\bot}(x)\neq\bot$. Then, by definition of $F^{\bot}$ and
$C^{F}_{\epsilon}$, $\forall x^{\prime}\in
X.||x-x^{\prime}||_{p}\leq\epsilon\implies F(x)=F(x^{\prime})$. Since our
adversary is norm-bounded, the original unperturbed input $x^{\prime\prime}$
has to satisfy the property that $||x^{\prime\prime}-x||_{p}\leq\epsilon$.
Therefore, it follows that $F(x)=F(x^{\prime\prime})$, i.e., $x$ is classified
in the same way as the original input and is therefore not an adversarial
example. ∎

Note that inference-time certification requires the certifier to be highly
efficient. While techniques based on smoothing and sampling, constraint
solving, linear relaxations, and semi-definite programming are too expensive
to be used at inference-time, Lipschitz-based certifiers are ideally suited
for this purpose since the global Lipschitz constant of the model can be
calculated offline.

###  5.3 Accuracy, Robustness, and Certification

While robustness certification can resolve the cat-and-mouse game played
between norm-bounded attackers and defenders, one may contend that it is
unclear at what cost this comes. Statements made consistently throughout the
literature over the years (Fawzi et al., 2018; Tsipras et al., 2019; Zhang et
al., 2019a) suggest that a common belief is that accuracy, robustness, and
sound certification are in conflict with one another, such that an inherent
trade-off is induced. However, in this section we present an alternate view.
First, under reasonable distributional assumptions, there is no conflict
between accuracy and local robustness. Moreover, a recent result (Leino, 2023)
shows that within the certified training paradigm, we can hope to steer the
model towards one that is not only accurate and robust, but also efficient to
certify (via a Lipschitz check), provided our hypothesis class has sufficient
capacity (Leino, 2023). Finally, in light of these observations, we argue that
Lipschitz-based certified training may be the most effective path forward for
learning high-performance robust models, and thus merits further research
attention.

#### Accuracy and Robustness

Much of the literature references, directly or implicitly, a robustness-
accuracy trade-off (Fawzi et al., 2018; Tsipras et al., 2019; Zhang et al.,
2019a). Tsipras et al. (2019) formalize this notion, showing a theoretical
trade-off between “standard” and robust accuracy in a simple Gaussian setting.
However, it is not clear that the distributional assumptions of Tsipras et al.
(Tsipras et al., 2019) are reasonable in any situation where we would hope for
robustness. Notably, under these distributional assumptions, the data are not
separable. This seems clearly problematic, as two in-distribution (natural)
points may be arbitrarily close to one another (even identical), but have
different ground-truth labels; while implicit in the notion of robustness—even
the most general notion of “semantic” robustness—is the assumption that the
ground truth is robust. After all, adversarial examples are meant to cause
misclassifications, not arbitrary alternations between equally valid labels.

Yang et al. (2020b) have argued that $\epsilon$-separability (Definition 5.2)
is a more reasonable assumption in the context of robustness. Crucially,
$\epsilon$-separability ensures that adversarial examples with respect to the
ground truth are not within the support of the distribution. This is a natural
requirement, which holds empirically on standard datasets (Yang et al.,
2020b); and it is clear that under this distributional assumption, no
accuracy-robustness trade-off exists.

#### On the Incompleteness of Efficient Certification

State-of-the-art (in terms of maximum $\overline{\texttt{VRA}}$ achieved)
certification procedures are _incomplete_ , using certified training
techniques to amplify the effectiveness of efficient robustness checks. As
discussed in Section 5.1, the fact that complete certification is NP-complete
leaves little hope that complete procedures will ever be practical on the
large-scale neural networks used in many real-world applications. This raises
the natural question: _at some point, won’t the incompleteness of leading
approaches compromise the model’s performance?_ If so, one may have to contend
with whether or not the strong guarantees robustness provides are worthwhile.

Note that there are two concerns here. The first is that a model may be
robust, but not all points will be certifiable, causing us to underestimate
its robust performance, and falsely flag robust points at inference time. The
second is that when using an incomplete certification as part of a certified
training procedure, the learned model will become over-regularized damaging
its true robustness (certified or not) and accuracy.

While both of these are valid concerns, when we consider the context of
certified training, the picture becomes less bleak. When the certifier has
control over the model’s parameters during training, it is pertinent to ask
not whether _all_ functions within the hypothesis class can be tightly
certified (corresponding to completeness), but rather, whether it is possible
to learn a function that (1) is robust on the distribution of interest, and
(2) can be tightly certified. Perhaps surprisingly, a result of Leino (2023)
shows that for any $\epsilon$-separated data distribution, there always exists
a function that achieves both of these goals, using a simple Lipschitz check
to _tightly_ decide the robustness all points. This function has the property
that the exact distance to the decision boundary (i.e., the robustness radius)
is always equal to $\nicefrac{{\Delta}}{{K}}$, where $\Delta$ is the minimum
margin between the logit value of the predicted class and any other logit
value, and $K$ is the function’s global Lipschitz constant, which is (on this
function) everywhere the same as its local Lipschitz constant. This means it
can be trivially certified at inference time using a bound on the global
Lipschitz constant.

The existence of such an “ideally robust” function does not directly suggest
that it is easy, or even practical, to learn such a function, however. In
fact, Leino points to the fact that approximating this ideally robust function
using the standard piece-wise linear hypothesis class requires excess capacity
beyond what would be required to learn a boundary that is technically robust
(but not certifiable)—and this is in addition to the practical challenges
around training dynamics and Lipschitz estimation. Nonetheless, we believe
that the existence of the ideally robust function should inspire hope that
Lipschitz-based certified training has a great deal of potential to minimize
the trade-off between accuracy, robustness, and efficient certification.
Indeed, even now, certified training approaches based on global Lipschitz-
based certification have emerged thus far as the clear leaders for state-of-
the-art $\overline{\texttt{VRA}}$ (Hu et al., 2023a).

#### The Power of Lipschitz-controlled Training

As discussed, the limitations which may lead to a trade-off between accuracy,
robustness, and certification are not as fundamental as one might initially
believe. Let us discuss this point further, as it relates to the motivation
for studying robustness certification.

Specifically, we would like to draw more attention to the recent success and
progress of Lipschitz-based certification. Within just the last few years, the
state-of-the-art deterministic VRA, led by Lipschitz based methods, e.g.,
(Leino et al., 2021; Trockman & Kolter, 2021; Hu et al., 2023b, a; Singla &
Feizi, 2021), has increased by a factor of over 50% on benchmark datasets like
CIFAR-10; and certification has become possible on large datasets (like
ImageNet) and architectures (like deep ResNets) (Hu et al., 2023b). Figure 5
illustrates this progress, specifically in terms of closing the gap between
accuracy and verified robust accuracy. There is a strong empirical and
theoretical basis for believing that these strides should hope to continue; we
therefore contend that it is worth exploring further in this direction to
build on the tremendous progress.

Figure 5: The gap between the reported SOTA $\overline{\texttt{Acc}}$ and SOTA
$\overline{\texttt{VRA}}$ (measured locally in a $\ell_{2}$-ball with
$\epsilon=36/255$) on several vision datasets.

#### A Way Forward for Robustness via Lipschitz-based Methods

Although the power of Lipschitz-based certification is supported
theoretically, and has thus far been borne out empirically, our bullishness on
this approach’s future prospects deserves closer examination. A series of
studies find, either empirically or theoretically, that robust models require
more capacity (Schmidt et al., 2018; Bubeck et al., 2021; Li & Li, 2023; Wang
et al., 2023; Altstidl et al., 2023), particularly in the context of
certification. However, for certifiable models, especially those certified
using Lipschitz-based methods, increasing the model capacity is not trivial.

To obtain satisfactory certification performance using Lipschitz-based
training methods, it is crucial to design network architectures with easy-to-
compute and tight Lipschitz bounds. This is a challenge in and of itself, but
it also specifically complicates capacity-scaling.

One common approach to adding capacity is by adding depth to the network, but
this is challenging for Lipschitz-based methods, as the bound for the entire
network is typically computed as a product of the layer-wise Lipschitz bounds,
meaning that any looseness compounds multiplicatively with each layer.
Furthermore, deep models typically use residual architectures, but a naive
bound on the Lipschitz constant of residual blocks is unfortunately loose (Hu
et al., 2023b). Hu et al. (2023b) proposed using a linear residual branch so
that the Lipschitz bound for the residual block can be tight, showing that
this method can obtain non-trivial deterministic certification on ImageNet.
However, linear residual blocks are less expressive than non-linear residual
blocks.

The requirement for Lipschitzness, also renders traditional attention-based
architectures as out-of-scope since they do not have a Lipschitz bound.
Although some work (Kim et al., 2021; Xu et al., 2023) proposes to modify the
attention mechanism to make it Lipschitz, so far attention-based mechanisms
have not been shown to outperform basic ResNet architectures (Hu et al.,
2023b). Nonetheless, exploring transformer-like building blocks with tight
Lipschitz bounds remains an interesting research direction. Models using such
blocks may benefit from the high capacity from Transformer-like deign, and
bridge the gap between VRA and standard accuracy (Acc) for visual models.
Additionally, “Lipschitz transformers” could open the door for providing
certain security guarantees for LLMs, which have recently gained massive
attention from the machine learning community as well as the general public.

##  6 Conclusion

Though a tremendous amount of research has been produced over the last decade
on adversarial robustness with respect to norm-bounded adversaries, the impact
of this research in practice remains unclear. In light of this situation, we
revisit some basic underlying motivations driving this research and argue for
theo position that robustness research with respect to norm-bounded
adversaries, particularly research on certified defenses, continues to be
practically worthwhile and technically challenging. We clarify that
certification can mean different things at different stages of learning
pipeline and formalize the guarantees granted by certification at these
different stages. With this, we hope to bring clarity and structure to the
ongoing, almost decade-long, conversation on certified robustness, and provide
insight as to which directions remain fruitful. We also clarify that, under
realistic distributional assumptions, there is no inherent trade-off between
accuracy, robustness, and efficient certifiability, suggesting that certified
models stand a hopeful chance of being able to satisfy the many requirements
that would be necessary for adoption into real-world applications. Finally, to
this end, we propose specifically that certified training incorporating
Lipschitz-based certification may offer the most promising path towards
learning an ideal function that is accurate, robust, and certifiable.

## References

  * (1) https://nicholas.carlini.com/writing/2019/all-adversarial-example-papers.html.
  * Altstidl et al. (2023) Altstidl, T., Dobre, D., Eskofier, B., Gidel, G., and Schwinn, L.  Raising the bar for certified adversarial robustness with diffusion models.  _arXiv preprint arXiv:2305.10388_ , 2023.
  * Andriushchenko et al. (2020) Andriushchenko, M., Croce, F., Flammarion, N., and Hein, M.  Square attack: a query-efficient black-box adversarial attack via random search.  In _European conference on computer vision_ , pp. 484–501. Springer, 2020.
  * Araujo et al. (2023) Araujo, A., Havens, A. J., Delattre, B., Allauzen, A., and Hu, B.  A unified algebraic perspective on lipschitz neural networks.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=k71IGLC8cfc.
  * Bak et al. (2021) Bak, S., Liu, C., and Johnson, T.  The second international verification of neural networks competition (vnn-comp 2021): Summary and results.  _arXiv preprint arXiv:2109.00498_ , 2021.
  * Balunovic et al. (2019) Balunovic, M., Baader, M., Singh, G., Gehr, T., and Vechev, M.  Certifying geometric robustness of neural networks.  In _Advances in Neural Information Processing Systems 32_. 2019.
  * Behrmann et al. (2019) Behrmann, J., Grathwohl, W., Chen, R. T., Duvenaud, D., and Jacobsen, J.-H.  Invertible residual networks.  In _International conference on machine learning_ , pp. 573–582. PMLR, 2019.
  * Bitterwolf et al. (2020) Bitterwolf, J., Meinke, A., and Hein, M.  Certifiably adversarially robust detection of out-of-distribution data.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 16085–16095. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/b90c46963248e6d7aab1e0f429743ca0-Paper.pdf.
  * Brix et al. (2023) Brix, C., Müller, M. N., Bak, S., Johnson, T. T., and Liu, C.  First three years of the international verification of neural networks competition (vnn-comp).  _International Journal on Software Tools for Technology Transfer_ , pp. 1–11, 2023.
  * Bubeck et al. (2021) Bubeck, S., Li, Y., and Nagaraj, D. M.  A law of robustness for two-layers neural networks.  In _Conference on Learning Theory_ , pp. 804–820. PMLR, 2021.
  * Bunel et al. (2020) Bunel, R., Mudigonda, P., Turkaslan, I., Torr, P., Lu, J., and Kohli, P.  Branch and bound for piecewise linear neural network verification.  _Journal of Machine Learning Research_ , 21(2020), 2020.
  * Calinescu et al. (2022) Calinescu, R., Imrie, C., Mangal, R., Rodrigues, G. N., Păsăreanu, C., Santana, M. A., and Vázquez, G.  Discrete-event controller synthesis for autonomous systems with deep-learning perception components.  _arXiv preprint arXiv:2202.03360_ , 2022.
  * Carlini & Wagner (2017) Carlini, N. and Wagner, D.  Towards evaluating the robustness of neural networks.  In _2017 ieee symposium on security and privacy (sp)_ , pp. 39–57. Ieee, 2017.
  * Carlini et al. (2019) Carlini, N., Athalye, A., Papernot, N., Brendel, W., Rauber, J., Tsipras, D., Goodfellow, I., Madry, A., and Kurakin, A.  On evaluating adversarial robustness.  _arXiv preprint arXiv:1902.06705_ , 2019.
  * Carlini et al. (2022) Carlini, N., Tramer, F., Kolter, J. Z., et al.  (certified!!) adversarial robustness for free!  _arXiv preprint arXiv:2206.10550_ , 2022.
  * Carlini et al. (2023) Carlini, N., Nasr, M., Choquette-Choo, C. A., Jagielski, M., Gao, I., Awadalla, A., Koh, P. W., Ippolito, D., Lee, K., Tramer, F., et al.  Are aligned neural networks adversarially aligned?  _arXiv preprint arXiv:2306.15447_ , 2023.
  * Chen et al. (2020) Chen, T., Liu, S., Chang, S., Cheng, Y., Amini, L., and Wang, Z.  Adversarial robustness: From self-supervised pre-training to fine-tuning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 699–708, 2020.
  * Cohen et al. (2019) Cohen, J., Rosenfeld, E., and Kolter, Z.  Certified adversarial robustness via randomized smoothing.  In _international conference on machine learning_ , pp. 1310–1320. PMLR, 2019.
  * Croce & Hein (2020a) Croce, F. and Hein, M.  Minimally distorted adversarial examples with a fast adaptive boundary attack.  In _International Conference on Machine Learning_ , pp. 2196–2205. PMLR, 2020a.
  * Croce & Hein (2020b) Croce, F. and Hein, M.  Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.  In _International conference on machine learning_ , pp. 2206–2216. PMLR, 2020b.
  * Croce et al. (2020) Croce, F., Andriushchenko, M., Sehwag, V., Debenedetti, E., Flammarion, N., Chiang, M., Mittal, P., and Hein, M.  Robustbench: a standardized adversarial robustness benchmark.  _arXiv preprint arXiv:2010.09670_ , 2020.
  * Croce et al. (2022) Croce, F., Gowal, S., Brunner, T., Shelhamer, E., Hein, M., and Cemgil, T.  Evaluating the adversarial robustness of adaptive test-time defenses.  In _International Conference on Machine Learning_ , pp. 4421–4435. PMLR, 2022.
  * Dathathri et al. (2020) Dathathri, S., Dvijotham, K., Kurakin, A., Raghunathan, A., Uesato, J., Bunel, R. R., Shankar, S., Steinhardt, J., Goodfellow, I., Liang, P. S., et al.  Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming.  _Advances in Neural Information Processing Systems_ , 33:5318–5331, 2020.
  * Deng et al. (2021) Deng, Z., Zhang, L., Vodrahalli, K., Kawaguchi, K., and Zou, J. Y.  Adversarial training helps transfer learning via better representations.  _Advances in Neural Information Processing Systems_ , 34:25179–25191, 2021.
  * Dumont et al. (2018) Dumont, B., Maggio, S., and Montalvo, P.  Robustness of rotation-equivariant networks to adversarial perturbations.  _arXiv preprint arXiv:1802.06627_ , 2018.
  * Dvijotham et al. (2018) Dvijotham, K., Stanforth, R., Gowal, S., Mann, T. A., and Kohli, P.  A dual approach to scalable verification of deep networks.  In _UAI_ , volume 1, pp. 3, 2018.
  * Etmann et al. (2019) Etmann, C., Lunz, S., Maass, P., and Schönlieb, C.-B.  On the connection between adversarial robustness and saliency map interpretability.  In _International Conference on Machine Learning_ , 2019.  URL https://api.semanticscholar.org/CorpusID:150374025.
  * Eykholt et al. (2018) Eykholt, K., Evtimov, I., Fernandes, E., Li, B., Rahmati, A., Xiao, C., Prakash, A., Kohno, T., and Song, D.  Robust physical-world attacks on deep learning visual classification.  In _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 1625–1634, 2018.  doi: 10.1109/CVPR.2018.00175.
  * Fawzi et al. (2018) Fawzi, A., Fawzi, O., and Frossard, P.  Analysis of classifiers’ robustness to adversarial perturbations.  _Machine learning_ , 107(3):481–508, 2018.
  * Fazlyab et al. (2020) Fazlyab, M., Morari, M., and Pappas, G. J.  Safety verification and robustness analysis of neural networks via quadratic constraints and semidefinite programming.  _IEEE Transactions on Automatic Control_ , 67(1):1–15, 2020.
  * Frei et al. (2023) Frei, S., Vardi, G., Bartlett, P. L., and Srebro, N.  The double-edged sword of implicit bias: Generalization vs. robustness in relu networks.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Frosio & Kautz (2023) Frosio, I. and Kautz, J.  The best defense is a good offense: Adversarial augmentation against adversarial attacks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 4067–4076, 2023.
  * Gavrikov et al. (2023) Gavrikov, P., Keuper, J., and Keuper, M.  An extended study of human-like behavior under adversarial training.  _2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , pp. 2361–2368, 2023.  URL https://api.semanticscholar.org/CorpusID:257663581.
  * Gilmer et al. (2018) Gilmer, J., Adams, R. P., Goodfellow, I., Andersen, D., and Dahl, G. E.  Motivating the rules of the game for adversarial example research.  _arXiv preprint arXiv:1807.06732_ , 2018.
  * Goodfellow et al. (2015) Goodfellow, I., Shlens, J., and Szegedy, C.  Explaining and harnessing adversarial examples.  In _International Conference on Learning Representations_ , 2015.  URL http://arxiv.org/abs/1412.6572.
  * Gowal et al. (2018a) Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T., and Kohli, P.  On the effectiveness of interval bound propagation for training verifiably robust models.  _arXiv preprint arXiv:1810.12715_ , 2018a.
  * Gowal et al. (2018b) Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelović, R., Mann, T. A., and Kohli, P.  On the effectiveness of interval bound propagation for training verifiably robust models.  _ArXiv_ , abs/1810.12715, 2018b.  URL https://api.semanticscholar.org/CorpusID:53112003.
  * Hao et al. (2022) Hao, Z., Ying, C., Dong, Y., Su, H., Song, J., and Zhu, J.  Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing.  In _International Conference on Machine Learning_ , pp. 8465–8483. PMLR, 2022.
  * Hendrycks et al. (2020) Hendrycks, D., Mu, N., Cubuk, E. D., Zoph, B., Gilmer, J., and Lakshminarayanan, B.  AugMix: A simple data processing method to improve robustness and uncertainty.  _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2020.
  * Hendrycks et al. (2021a) Hendrycks, D., Burns, C., Basart, S., Critch, A., Li, J., Song, D., and Steinhardt, J.  Aligning ai with shared human values.  _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2021a.
  * Hendrycks et al. (2021b) Hendrycks, D., Carlini, N., Schulman, J., and Steinhardt, J.  Unsolved problems in ml safety.  _arXiv preprint arXiv:2109.13916_ , 2021b.
  * Hendrycks et al. (2023) Hendrycks, D., Mazeika, M., and Woodside, T.  An overview of catastrophic ai risks.  _arXiv preprint arXiv:2306.12001_ , 2023.
  * Hou et al. (2023) Hou, B., Jia, J., Zhang, Y., Zhang, G., Zhang, Y., Liu, S., and Chang, S.  Textgrad: Advancing robustness evaluation in NLP by gradient-driven optimization.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=5tKXUZil3X.
  * Hsiung et al. (2023) Hsiung, L., Tsai, Y.-Y., Chen, P.-Y., and Ho, T.-Y.  Towards Compositional Adversarial Robustness: Generalizing Adversarial Training to Composite Semantic Perturbations.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR_. IEEE, June 2023.
  * Hu et al. (2023a) Hu, K., Leino, K., Wang, Z., and Fredrikson, M.  A recipe for improved certifiable robustness: Capacity and data.  _arXiv preprint arXiv:2310.02513_ , 2023a.
  * Hu et al. (2023b) Hu, K., Zou, A., Wang, Z., Leino, K., and Fredrikson, M.  Scaling in depth: Unlocking robustness certification on imagenet.  _arXiv preprint arXiv:2301.12549_ , 2023b.
  * Hussain et al. (2021) Hussain, S., Neekhara, P., Dubnov, S., McAuley, J., and Koushanfar, F.  $\\{$WaveGuard$\\}$: Understanding and mitigating audio adversarial examples.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pp. 2273–2290, 2021.
  * Ilyas et al. (2019) Ilyas, A., Santurkar, S., Tsipras, D., Engstrom, L., Tran, B., and Madry, A.  Adversarial examples are not bugs, they are features.  _Advances in neural information processing systems_ , 32, 2019.
  * Jeong et al. (2021) Jeong, J., Park, S., Kim, M., Lee, H.-C., Kim, D.-G., and Shin, J.  Smoothmix: Training confidence-calibrated smoothed classifiers for certified robustness.  _Advances in Neural Information Processing Systems_ , 34:30153–30168, 2021.
  * Katz et al. (2017) Katz, G., Barrett, C., Dill, D. L., Julian, K., and Kochenderfer, M. J.  Reluplex: An efficient smt solver for verifying deep neural networks.  In _Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I 30_ , pp. 97–117. Springer, 2017.
  * Katz et al. (2019) Katz, G., Huang, D. A., Ibeling, D., Julian, K., Lazarus, C., Lim, R., Shah, P., Thakoor, S., Wu, H., Zeljić, A., et al.  The marabou framework for verification and analysis of deep neural networks.  In _Computer Aided Verification: 31st International Conference, CAV 2019, New York City, NY, USA, July 15-18, 2019, Proceedings, Part I 31_ , pp. 443–452. Springer, 2019.
  * Kim et al. (2021) Kim, H., Papamakarios, G., and Mnih, A.  The lipschitz constant of self-attention.  In _International Conference on Machine Learning_ , pp. 5562–5571. PMLR, 2021.
  * Kojima et al. (2022) Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y.  Large language models are zero-shot reasoners.  In _Advances in Neural Information Processing Systems_ , volume 35, pp. 22199–22213, 2022.
  * Leino (2022) Leino, K.  Identifying, analyzing, and addressing weaknesses in deep networks: Foundations for conceptually sound neural networks, 2022.
  * Leino (2023) Leino, K.  Limitations of piecewise linearity for efficient robustness certification, 2023.
  * Leino et al. (2021) Leino, K., Wang, Z., and Fredrikson, M.  Globally-robust neural networks.  In _International Conference on Machine Learning_ , pp. 6212–6222. PMLR, 2021.
  * Leino et al. (2022a) Leino, K., Helland, J., Vijaykumar, S., Sinha, A., VanHoudnos, N., and Fredrikson, M.  Robust features can leak instances and their properties, 2022a.
  * Leino et al. (2022b) Leino, K., Zhang, C., Mangal, R., Fredrikson, M., Parno, B., and Pasareanu, C.  Degradation attacks on certifiably robust neural networks.  _Transactions on Machine Learning Research_ , 2022b.  ISSN 2835-8856.  URL https://openreview.net/forum?id=P0XO5ZE98j.
  * Li & Li (2023) Li, B. and Li, Y.  Why clean generalization and robust overfitting both happen in adversarial training.  _arXiv preprint arXiv:2306.01271_ , 2023.
  * Li et al. (2023) Li, L., Xie, T., and Li, B.  Sok: Certified robustness for deep neural networks.  In _2023 IEEE Symposium on Security and Privacy (SP)_ , pp. 1289–1310. IEEE, 2023.
  * Lin et al. (2020) Lin, W.-A., Lau, C. P., Levine, A., Chellappa, R., and Feizi, S.  Dual manifold adversarial robustness: Defense against lp and non-lp adversarial attacks.  _Advances in Neural Information Processing Systems_ , 33:3487–3498, 2020.
  * Madry et al. (2018) Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=rJzIBfZAb.
  * Mangal & Pasareanu (2022) Mangal, R. and Pasareanu, C. S.  A cascade of checkers for run-time certification of local robustness.  In Isac, O., Ivanov, R., Katz, G., Narodytska, N., and Nenzi, L. (eds.), _Software Verification and Formal Methods for ML-Enabled Autonomous Systems - 5th International Workshop, FoMLAS 2022, and 15th International Workshop, NSV 2022, Haifa, Israel, July 31 - August 1, and August 11, 2022, Proceedings_ , volume 13466 of _Lecture Notes in Computer Science_ , pp. 15–28. Springer, 2022.  doi: 10.1007/978-3-031-21222-2“˙2.  URL https://doi.org/10.1007/978-3-031-21222-2_2.
  * Mao et al. (2019) Mao, C., Zhong, Z., Yang, J., Vondrick, C., and Ray, B.  Metric learning for adversarial robustness.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/c24cd76e1ce41366a4bbe8a49b02a028-Paper.pdf.
  * Maus et al. (2023) Maus, N., Chao, P., Wong, E., and Gardner, J.  Adversarial prompting for black box foundation models.  _arXiv preprint arXiv:2302.04237_ , 2023.
  * Morawiecki et al. (2019) Morawiecki, P., Spurek, P., Śmieja, M., and Tabor, J.  Fast and stable interval bounds propagation for training verifiably robust models.  _arXiv preprint arXiv:1906.00628_ , 2019.
  * Naseer et al. (2020) Naseer, M., Khan, S., Hayat, M., Khan, F. S., and Porikli, F.  A self-supervised approach for adversarial robustness.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 262–271, 2020.
  * Neyshabur et al. (2017) Neyshabur, B., Bhojanapalli, S., Mcallester, D., and Srebro, N.  Exploring generalization in deep learning.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/10ce03a1ed01077e3e289f3e53c72813-Paper.pdf.
  * Ouyang et al. (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Pang et al. (2019a) Pang, T., Xu, K., Dong, Y., Du, C., Chen, N., and Zhu, J.  Rethinking softmax cross-entropy loss for adversarial robustness.  _arXiv preprint arXiv:1905.10626_ , 2019a.
  * Pang et al. (2019b) Pang, T., Xu, K., Du, C., Chen, N., and Zhu, J.  Improving adversarial robustness via promoting ensemble diversity.  In _International Conference on Machine Learning_ , pp. 4970–4979. PMLR, 2019b.
  * Păsăreanu et al. (2023) Păsăreanu, C. S., Mangal, R., Gopinath, D., Getir Yaman, S., Imrie, C., Calinescu, R., and Yu, H.  Closed-loop analysis of vision-based autonomous systems: A case study.  In _International Conference on Computer Aided Verification_ , pp. 289–303. Springer, 2023.
  * Pulina & Tacchella (2010) Pulina, L. and Tacchella, A.  An abstraction-refinement approach to verification of artificial neural networks.  In _Computer Aided Verification: 22nd International Conference, CAV 2010, Edinburgh, UK, July 15-19, 2010. Proceedings 22_ , pp. 243–257. Springer, 2010.
  * Raghunathan et al. (2018) Raghunathan, A., Steinhardt, J., and Liang, P.  Certified defenses against adversarial examples.  In _International Conference on Learning Representations_ , 2018.
  * Rebuffi et al. (2021) Rebuffi, S.-A., Gowal, S., Calian, D. A., Stimberg, F., Wiles, O., and Mann, T.  Fixing data augmentation to improve adversarial robustness.  _arXiv preprint arXiv:2103.01946_ , 2021.
  * Salman et al. (2019) Salman, H., Yang, G., Zhang, H., Hsieh, C.-J., and Zhang, P.  A convex relaxation barrier to tight robustness verification of neural networks.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Salman et al. (2020) Salman, H., Ilyas, A., Engstrom, L., Kapoor, A., and Madry, A.  Do adversarially robust imagenet models transfer better?  _Advances in Neural Information Processing Systems_ , 33:3533–3545, 2020.
  * Schmidt et al. (2018) Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A.  Adversarially robust generalization requires more data.  _Advances in neural information processing systems_ , 31, 2018.
  * Setlur et al. (2022) Setlur, A., Eysenbach, B., Smith, V., and Levine, S.  Adversarial unlearning: Reducing confidence along adversarial directions.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=cJ006qBE8Uv.
  * Sharif et al. (2016) Sharif, M., Bhagavatula, S., Bauer, L., and Reiter, M. K.  Accessorize to a crime: Real and stealthy attacks on state-of-the-art face recognition.  In _Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security_ , October 2016.  doi: 10.1145/2976749.2978392.  URL https://www.ece.cmu.edu/~lbauer/papers/2016/ccs2016-face-recognition.pdf.
  * Sharif et al. (2017) Sharif, M., Bhagavatula, S., Bauer, L., and Reiter, M. K.  Adversarial Generative Nets: Neural network attacks on state-of-the-art face recognition.  arXiv preprint 1801.00349, December 2017.  URL https://arxiv.org/abs/1801.00349.
  * Shi et al. (2023) Shi, Z., Jin, Q., Kolter, J. Z., Jana, S., Hsieh, C.-J., and Zhang, H.  Formal verification for neural networks with general nonlinearities via branch-and-bound.  _2nd Workshop on Formal Verification of Machine Learning (WFVML 2023)_ , 2023.
  * Singh et al. (2019) Singh, G., Gehr, T., Püschel, M., and Vechev, M.  An abstract domain for certifying neural networks.  _Proceedings of the ACM on Programming Languages_ , 3(POPL):1–30, 2019.
  * Singla & Feizi (2021) Singla, S. and Feizi, S.  Skew orthogonal convolutions.  In Meila, M. and Zhang, T. (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 9756–9766. PMLR, 18–24 Jul 2021.
  * Szegedy et al. (2013) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Tjeng et al. (2017) Tjeng, V., Xiao, K., and Tedrake, R.  Evaluating robustness of neural networks with mixed integer programming.  _arXiv preprint arXiv:1711.07356_ , 2017.
  * Tramer (2022) Tramer, F.  Detecting adversarial examples is (Nearly) as hard as classifying them.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 21692–21702. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/tramer22a.html.
  * Tramèr et al. (2017) Tramèr, F., Kurakin, A., Papernot, N., Goodfellow, I., Boneh, D., and McDaniel, P.  Ensemble adversarial training: Attacks and defenses.  _arXiv preprint arXiv:1705.07204_ , 2017.
  * Tramèr et al. (2018) Tramèr, F., Dupré, P., Rusak, G., Pellegrino, G., and Boneh, D.  Adversarial: Perceptual ad blocking meets adversarial machine learning.  _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , 2018.  URL https://api.semanticscholar.org/CorpusID:67855958.
  * Trockman & Kolter (2021) Trockman, A. and Kolter, J. Z.  Orthogonalizing convolutional layers with the cayley transform.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Tsai et al. (2019) Tsai, Y.-T., Yang, M.-C., and Chen, H.-Y.  Adversarial attack on sentiment classification.  In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pp. 233–240, Florence, Italy, August 2019. Association for Computational Linguistics.  doi: 10.18653/v1/W19-4824.  URL https://aclanthology.org/W19-4824.
  * Tsipras et al. (2019) Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A.  Robustness may be at odds with accuracy.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=SyxAb30cY7.
  * Uesato et al. (2018) Uesato, J., O’Donoghue, B., Kohli, P., and van den Oord, A.  Adversarial risk and the dangers of evaluating against weak attacks.  In Dy, J. and Krause, A. (eds.), _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pp. 5025–5034. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/uesato18a.html.
  * Vardi et al. (2022) Vardi, G., Yehudai, G., and Shamir, O.  Gradient methods provably converge to non-robust networks.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=XDZhagjfMP.
  * Wang et al. (2022a) Wang, R., Yang, Y., and Tao, D.  Art-point: Improving rotation robustness of point cloud classifiers via adversarial rotation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 14371–14380, 2022a.
  * Wang et al. (2018) Wang, S., Pei, K., Whitehouse, J., Yang, J., and Jana, S.  Efficient formal safety analysis of neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Wang et al. (2021) Wang, S., Zhang, H., Xu, K., Lin, X., Jana, S., Hsieh, C.-J., and Kolter, J. Z.  Beta-CROWN: Efficient bound propagation with per-neuron split constraints for neural network robustness verification.  In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=ahYIlRBeCFw.
  * Wang (2023) Wang, Z.  On the Feature Alignment of Deep Vision Models: Explainability and Robustness Connected At Hip.  9 2023.  doi: 10.1184/R1/24026334.v1.  URL https://kilthub.cmu.edu/articles/thesis/On_the_Feature_Alignment_of_Deep_Vision_Models_Explainability_and_Robustness_Connected_At_Hip/24026334.
  * Wang et al. (2022b) Wang, Z., Fredrikson, M., and Datta, A.  Robust models are more interpretable because attributions look normal.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 22625–22651. PMLR, 17–23 Jul 2022b.  URL https://proceedings.mlr.press/v162/wang22e.html.
  * Wang et al. (2023) Wang, Z., Pang, T., Du, C., Lin, M., Liu, W., and Yan, S.  Better diffusion models further improve adversarial training.  In _International Conference on Machine Learning (ICML)_ , 2023.
  * Wei et al. (2023) Wei, A., Haghtalab, N., and Steinhardt, J.  Jailbroken: How does llm safety training fail?  _arXiv preprint arXiv:2307.02483_ , 2023.
  * Weng et al. (2018) Weng, L., Zhang, H., Chen, H., Song, Z., Hsieh, C.-J., Daniel, L., Boning, D., and Dhillon, I.  Towards fast computation of certified robustness for relu networks.  In _International Conference on Machine Learning_ , pp. 5276–5285. PMLR, 2018.
  * Wong et al. (2018) Wong, E., Schmidt, F., Metzen, J. H., and Kolter, J. Z.  Scaling provable adversarial defenses.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Wu et al. (2023) Wu, H., Tagomori, T., Robey, A., Yang, F., Matni, N., Pappas, G., Hassani, H., Pasareanu, C., and Barrett, C.  Toward certified robustness against real-world distribution shifts.  In _2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)_ , pp. 537–553. IEEE, 2023.
  * Xiao et al. (2022) Xiao, C., Chen, Z., Jin, K., Wang, J., Nie, W., Liu, M., Anandkumar, A., Li, B., and Song, D.  Densepure: Understanding diffusion models for adversarial robustness.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Xie et al. (2020) Xie, C., Tan, M., Gong, B., Wang, J., Yuille, A., and Le, Q. V.  Adversarial examples improve image recognition.  _arXiv preprint arXiv:1911.09665_ , 2020.
  * Xu et al. (2020) Xu, K., Zhang, G., Liu, S., Fan, Q., Sun, M., Chen, H., Chen, P.-Y., Wang, Y., and Lin, X.  Adversarial t-shirt! evading person detectors in a physical world.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part V 16_ , pp. 665–681. Springer, 2020.
  * Xu et al. (2023) Xu, X., Li, L., Cheng, Y., Mukherjee, S., Awadallah, A. H., and Li, B.  Certifiably robust transformers with 1-lipschitz self-attention, 2023.  URL https://openreview.net/forum?id=hzG72qB0XQ.
  * Yang et al. (2020a) Yang, G., Duan, T., Hu, J. E., Salman, H., Razenshteyn, I. P., and Li, J.  Randomized smoothing of all shapes and sizes.  2020a.
  * Yang et al. (2023) Yang, R., Laurel, J., Misailovic, S., and Singh, G.  Provable defense against geometric transformations.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=ThXqBsRI-cY.
  * Yang et al. (2020b) Yang, Y.-Y., Rashtchian, C., Zhang, H., Salakhutdinov, R. R., and Chaudhuri, K.  A closer look at accuracy vs. robustness.  _Advances in neural information processing systems_ , 33:8588–8601, 2020b.
  * Zhang et al. (2018) Zhang, H., Weng, T.-W., Chen, P.-Y., Hsieh, C.-J., and Daniel, L.  Efficient neural network robustness certification with general activation functions.  _Advances in neural information processing systems_ , 31, 2018.
  * Zhang et al. (2019a) Zhang, H., Yu, Y., Jiao, J., Xing, E., El Ghaoui, L., and Jordan, M.  Theoretically principled trade-off between robustness and accuracy.  In _International conference on machine learning_ , pp. 7472–7482. PMLR, 2019a.
  * Zhang et al. (2019b) Zhang, H., Yu, Y., Jiao, J., Xing, E. P., Ghaoui, L. E., and Jordan, M. I.  Theoretically principled trade-off between robustness and accuracy.  _ArXiv_ , abs/1901.08573, 2019b.  URL https://api.semanticscholar.org/CorpusID:59222747.
  * Zhong et al. (2020) Zhong, J., Liu, X., and Hsieh, C.-J.  Improving the speed and quality of gan by adversarial training.  _arXiv preprint arXiv:2008.03364_ , 2020.
  * Zhou & Patel (2022) Zhou, M. and Patel, V. M.  Enhancing adversarial robustness for deep metric learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 15325–15334, 2022.
  * Ziegler et al. (2019) Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G.  Fine-tuning language models from human preferences.  _arXiv preprint arXiv:1909.08593_ , 2019.
  * Zou et al. (2023) Zou, A., Wang, Z., Kolter, J. Z., and Fredrikson, M.  Universal and transferable adversarial attacks on aligned language models.  _arXiv preprint arXiv:2307.15043_ , 2023.