# How Adversarial Attacks Can Disrupt
Seemingly Stable Accurate Classifiers

Oliver J. Sutton1 ,  Qinghua Zhou1 ,  Ivan Y. Tyukin1 ,  Alexander N. Gorban2
,  Alexander Bastounis2 and  Desmond J. Higham3 1Department of Mathematics,
King’s College London, WC2R 2LS  2School of Computing and Mathematical
Sciences, University of Leicester, LE1 7RH  3School of Mathematics, University
of Edinburgh, EH9 3FD<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Adversarial attacks dramatically change the output of an otherwise accurate
learning system using a seemingly inconsequential modification to a piece of
input data. Paradoxically, empirical evidence indicates that even systems
which are robust to large random perturbations of the input data remain
susceptible to small, easily constructed, adversarial perturbations of their
inputs. Here, we show that this may be seen as a fundamental feature of
classifiers working with high dimensional input data. We introduce a simple
generic and generalisable framework for which key behaviours observed in
practical systems arise with high probability—notably the simultaneous
susceptibility of the (otherwise accurate) model to easily constructed
adversarial attacks, and robustness to random perturbations of the input data.
We confirm that the same phenomena are directly observed in practical neural
networks trained on standard image classification problems, where even large
additive random noise fails to trigger the adversarial instability of the
network. A surprising takeaway is that even small margins separating a
classifier’s decision surface from training and testing data can hide
adversarial susceptibility from being detected using randomly sampled
perturbations. Counterintuitively, using additive noise during training or
testing is therefore inefficient for eradicating or detecting adversarial
examples, and more demanding adversarial training is required.

##  1\. Introduction

Adversarial attacks aim to slightly modify a piece of input data in such a way
as to significantly change the output of a model. As such, they exploit
sensitivities and instabilities in neural networks. Recent work [2] has shown
that such instabilities are somewhat inevitable, even in relatively small
networks consisting of just two layers where the number of neurons is linear
in the input data dimension. On top of this, there exist simple algorithms
enabling a malicious attacker to produce adversarial perturbations quite
easily in many cases [3]. It is remarkable, therefore, that these same
instabilities are rarely triggered by random perturbations to the input data –
even when these random perturbations may be much larger than destabilising
adversarial perturbations.

(a) Cumulative histogram of sizes of successful adversarial attacks.

(b) Sizes of successful random perturbations.

Figure 1. Histograms showing the fraction of images which were misclassified
after either (a) an adversarial attack (as the fraction of ordinarily
correctly classified images) or (b) a random perturbation of different sizes
(as the fraction of images which were susceptible to adversarial attacks),
measured as the maximum absolute change to an individual pixel channel (the
$\ell^{\infty}$ norm). For adversarial attacks, this represents the smallest
misclassifying attack in the adversarial direction, while for the random
perturbations we record the smallest $\ell^{\infty}$ norm among all
misclassifying perturbations. The random perturbations applied to each image
were normalised to have Euclidean norm equal to a fixed multiple of the
Euclidean norm of the smallest successful adversarial attack for that image,
shown on the horizontal axis of panel (b). Examples are shown at the size of
their respective perturbation norms.

This ‘paradox of apparent stability’ is demonstrated in Figure 1 for a
standard convolutional neural network trained on CIFAR-10 images [11].
Although the majority of images in both the training and test data sets are
susceptible to small adversarial attacks (Panel (a)), random perturbations
even an order of magnitude larger mostly fail to cause the images to be
misclassified (Panel (b)). These experiments are discussed in detail in
Section 2.

Several explanations for the causes of adversarial examples have been proposed
in the literature. An early work on the subject [5] suggested that adversarial
images simply live in regions of the data space to which the data distribution
assigns low probability. A variant of this idea, discussed in [9], suggests
that adversarial attacks perturb inputs in a way that moves them in an
orthogonal direction to the local data manifold. This results in adversarial
images which exist in a region of data space where no training data could have
been sampled, and the decision surfaces of the network are therefore
relatively pathological. Other suggested mechanisms include the dimpled
manifold hypothesis [15], boundary tilting [18], and the existence of
uncountably large families of special distributions for which instabilities
are expected [2]. However, none of these frameworks rigorously account for and
explain the paradoxical simultaneous robustness of these classifiers to random
perturbations whose size could be several times larger than that of the
adversarial ones.

Here, we suggest a resolution to the paradox rooted in ideas from the
concentration effects of high dimensional probability distributions. We study
the phenomenon in the context of a binary classification problem, and the
simple, realistic framework we introduce captures the key features of the
paradox which are observed in practice (precise definitions of these terms are
given in Section 3):

Accuracy:

The classifier correctly labels non-perturbed data.

Apparent stability:

There is a vanishingly small probability that a sampled data point will be
misclassified after a large random perturbation is applied to it.

Vulnerability:

Yet, with high probability any sampled data point is susceptible to a very
small adversarial perturbation that changes the predicted class.

Computability:

The optimal destabilizing perturbation can be computed from knowledge of the
loss function gradient.

A further important feature of the framework that we introduce is that it can
easily be studied at various levels of generality, revealing that the
phenomena we observe are not merely contrived artefacts. We first present the
model in the case of two data distributions supported in $n$-dimensional balls
with a linear classifier in Section 3. This simplified setting allows us to
present results which distil the fundamental origins of the paradox without
unnecessary technical details. We repeat the analysis in a general setting
where data are sampled from two arbitrary distributions and a classifier with
a nonlinear decision surface is deployed in Section E.

Our results reveal a tension between different notions of what it means for a
classifier to be stable, a subtlety which is rarely discussed in practice. A
problem may be _deterministically unstable_ in the sense that there exists a
small, destabilising perturbation, while the fact that this instability is
extremely unlikely to be triggered by random noise in the data renders the
problem _probabilistically stable_. This is a dangerous situation for a
performance-critical classifier: even though the performance appears excellent
at test time, adversarial instabilities lurk awaiting an unscrupulous attacker
and cannot be detected at random. We discuss this concept and further
practical implications of our results in Section 4.

## Notation

We use the following notation throughout:

  * •

$x\cdot y$ denotes the inner product of $x,y\in\mathbb{R}^{n}$ and
$\|x\|=\sqrt{x\cdot y}$ denotes the Euclidean norm,

  * •

$\mathbb{B}^{n}_{r}(c)=\\{x\in\mathbb{R}^{n}\,:\,\|x-c\|\leq r\\}$ denotes the
the Euclidean ball in $\mathbb{R}^{n}$ with radius $r>0$ centered at
$c\in\mathbb{R}^{n}$, and we use the abbreviation
$\mathbb{B}^{n}=\mathbb{B}^{n}_{1}(0)$,

  * •

$V^{n}=\frac{\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2}+1)}$ denotes the
$n$-dimensional volume of $\mathbb{B}^{n}$, and
$V^{n}_{\operatorname{cap}}(r,h)$ denotes the volume of the cap with height
$h$ of the $n$-dimensional ball of radius $r$, i.e. the volume of the set
$\\{x\in\mathbb{R}^{n}\,:\,\|x\|<r\text{ and }x_{1}>1-h\\}$, where
$x_{1}=x\cdot\mathbf{e}_{1}$ and
$\mathbf{e}_{1}=(1,0,\dots,0)^{\top}\in\mathbb{R}^{n}$.

  * •

For a set $S\subset\mathbb{R}^{n}$, we use $\mathcal{U}(S)$ to denote the
uniform distribution on $S$, and $\mathbb{I}_{S}:S\to\\{0,1\\}$ to denote the
indicator function of $S$, such that $\mathcal{I}_{S}(x)=1$ for $x\in S$ and 0
otherwise.

##  2\. The paradox of apparent stability demonstrated on CIFAR-10

The phenomenon of simultaneous susceptibility to adversarial attacks and
robustness to random noise can be clearly demonstrated using the CIFAR-10
image classification dataset [11]. To present it in the simple setting of a
binary classification problem, we split the 10 classes of the CIFAR-10 dataset
into 45 binary classification problems. A separate network (each with an
identical convolutional structure in the form of a truncated VGG network [16])
was trained using Tensorflow [1] for each of these problems, and each point in
the training and test set was assessed for its susceptibility to adversarial
examples using a gradient-based attack algorithm. On images which were
susceptible to an adversarial attack with Euclidean norm $\delta$, we applied
2000 randomly sampled perturbations with Euclidean norm $\epsilon$ which were
set to be 1, 2, 5, and 10 times the size of $\delta$ to detect the sensitivity
of the network to random perturbations around these images. The full
experimental set up is described in Section A of the supplementary material.

The central phenomenon is illustrated in Figure 1: while the networks were
easily fooled by relatively small adversarial perturbations which appear to
make little perceptual difference to the image, they were remarkably robust to
randomly sampled perturbations. Here we demonstrate this in the broadly
representative case of the ‘aeroplane-vs-cat’ binary classification problem.
Comparing the inset examples on Figures 1(a) and 1(b), it is difficult to spot
the modification made by the adversarial perturbation, and it is nearly
equally difficult to make out the aeroplane in the randomly perturbed image.
Note that, since the original images have pixel channel values in $[0,1]$, a
perturbation with $\ell^{\infty}$ norm greater than 1 represents a drastic
change to the contents of the image, yet one which was rarely able to cause
the network to misclassify its input. Further details of the experimental
setup and full results for this and the remaining classification problems are
explored in Section B of the supplementary material.

We also provide the results of experiments incorporating additive random noise
to data at training time to assess the impact this may have on adversarial
susceptibility (described in Sections A.4 and B.4). The conclusion we draw
from these experiments is that training with even large random perturbations
does not seem to significantly decrease the susceptibility to adversarial
attacks, and is responsible for a large drop in accuracy.

##  3\. An illustrative theoretical model

This puzzle can be understood via a simple yet reasonably generic model
problem which captures the main features of the phenomenon. In this section,
we focus on the case of two data distributions satisfying a mild non-
degeneracy requirement (Definition 1) which are supported on balls and
classified using a linear discriminant. A significantly more general version
of this model is analysed in Section E of the supplementary material, with
fewer constraints on the distributions and a classifier which is permitted to
use a more general nonlinear decision surface. The results and conclusions
remain largely qualitatively similar. In particular, the simultaneous co-
existence of the high accuracy, the typicality of data susceptible to
adversarial attacks, and the rarity of destabilising random perturbations with
bounded $\ell^{2}$ norm all extend to the more general model with nonlinear
decision boundary (see Theorems 13, 15, 18 and Corollaries 14, 16, 19 in the
Supplementary materials).

We recall the definition of a data distribution satisfying the Smeared
Absolute Continuity (SmAC) property [6], which essentially just prevents it
from having pathological concentration points. We note that if the growth
property is satisfied with $A=1$, then the distribution is simply the uniform
distribution on the ball $\mathbb{B}^{n}_{r}(c)$.

######  Definition 1 (Smeared Absolute Continuity (SmAC) [6]).

A distribution $\mathcal{D}$ on $\mathcal{R}^{n}$ is said to satisfy the
_smeared absolute continuity condition_ if it possesses a density
$p:\mathbb{R}^{n}\to\mathbb{R}_{\geq 0}$ and there exists a centre point
$c\in\mathbb{R}^{n}$ and radius $r>0$ such that $p(x)>0$ only for points $x$
in the ball $\mathbb{B}^{n}_{r}(c)$, and there exists a constant growth
parameter $A>0$ such that

$\displaystyle\sup_{x\in\mathbb{B}^{n}_{r}(c)}p(x)\leq\frac{A^{n}}{V^{n}r^{n}}.$

Suppose that two classes of data are each sampled from data distributions
$\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ on $\mathbb{R}^{n}$ satisfying the
SmAC property. For simplicity, we suppose that these distributions each have
radius 1 and centres given by $c_{0}=-\epsilon\mathbf{e}_{1}$ and
$c_{1}=\epsilon\mathbf{e}_{1}$ respectively. We further suppose that both
distributions satisfy the growth bound with the same parameter $A$. For
brevity, we also define the combined distribution $\mathcal{D}_{\epsilon}$
which samples a point from $\mathcal{D}_{0}$ with label 0 with probability
$\frac{1}{2}$, and samples a point from $\mathcal{D}_{1}$ with label 1 with
probability $\frac{1}{2}$. The geometry of this setup is illustrated in Figure
2.

$1$$1$$\epsilon$$\epsilon$ Figure 2. Two unit balls with centres separated by
distance $2\epsilon$, and the decision surface of the classifier $f$ (dashed).

The classification function $f:\mathbb{R}^{n}\to\\{0,1\\}$ with the highest
accuracy which can be defined for this data model without further knowledge of
the distributions is given by the simple linear separator

(1) $\displaystyle f(x)=\begin{cases}0&\text{ if }x_{1}<0,\\\ 1&\text{
otherwise}.\end{cases}$

This classifier does not necessarily return the correct label in all cases
since, for $\epsilon\in(0,1)$, the two data classes overlap.

The first property of this simple model is that misclassified points are rare
in the high dimensional setting, despite the fact that the two balls from
which points are sampled have only a small separation between their centres.
More precisely, the probability that this classifier is correct converges
exponentially to 1 as the data dimension grows. This result is proven in
Section C.1 of the supplementary material.

######  Theorem 2 (The classifier is accurate).

For any $\epsilon>0$, the probability that the classifier applies the correct
label to a randomly sampled data point grows exponentially to 1 with dimension
$n$, specifically

$\displaystyle P((x,\ell)\sim\mathcal{D}_{\epsilon}:f(x)=\ell)\geq
1-\frac{1}{2}A^{n}(1-\epsilon^{2})^{\frac{n}{2}}.$

(a) Accuracy of the classifier (Theorem 2)

(b) Destabilisation probability (Theorem 4)

Figure 3. Comparison of the theoretical bounds in Theorems 2 and 4 against
empirical results computed using 10,000 data points sampled from
$\mathcal{D}_{\epsilon}$, with $\epsilon=0.05$, and 10,000 perturbations
sampled from $\mathcal{U}(\mathbb{B}^{n}_{\delta})$ for various values of
$\delta$. We see that, even for perturbations 50 times larger than the
separation distance between the balls (i.e. $\delta=2.5$), the probability of
randomly sampling a perturbation which changes the classification of a random
data point is very small in high dimensions.

The sharpness of this result is verified empirically in Figure 3(a), computed
for $A=1$. We observe that by $n=10,000$, the probability of sampling a point
which will be misclassified is virtually 0. To put this and the following
results into context, the $32\times 32\times 3$ images used in CIFAR-10 have
3,072 attributes, while the size of $256\times 256\times 3$ commonly used for
the images in ImageNet have 196,608 attributes, placing them firmly within the
range of dimensionalities where the effects described here are active.

On the other hand, even accurately classified points in this model are still
close to the decision surface since the ball centres are only separated by
distance $\epsilon$. Because of this, for any $\delta>\epsilon$, there are
points sampled from each class which are susceptible to an adversarial attack
$s\in\mathbb{R}^{n}$ with $\|s\|\leq\delta$ which causes $f$ to predict the
wrong class. Moreover, in high dimensions, data points sampled from such a
distribution concentrate at distance $\epsilon$ from this decision surface,
meaning that the probability of sampling a point which is susceptible to an
adversarial attack is high. This may be encapsulated in the following result,
which is proven in Section C.2 of the supplementary material.

######  Theorem 3 (Susceptible data points are typical).

For any $\epsilon\geq 0$ and $\delta\in[\epsilon,1+\epsilon]$, the probability
that a randomly sampled data point is susceptible to an adversarial attack
with Euclidean norm $\delta$ grows exponentially to 1 with the dimension $n$,
specifically

$\displaystyle P\big{(}(x,\ell)$
$\displaystyle\sim\mathcal{D}_{\epsilon}\,:\,\text{there exists
}s\in\mathbb{B}^{n}_{\delta}\text{ such that }f(x+s)\neq\ell\big{)}$
$\displaystyle\geq 1-\frac{1}{2}A^{n}(1-(\delta-\epsilon)^{2})^{\frac{n}{2}}.$

Although this susceptibility may therefore be viewed as typical in high
dimensions, however, the probability of detecting it by sampling random
perturbations of data points is paradoxically very small, as shown by the
following result which is proven in Section C.3 of the supplementary material.

######  Theorem 4 (Destabilising perturbations are rare).

For any $\delta>\epsilon\geq 0$, the probability that a randomly selected
perturbation with Euclidean norm $\delta$ causes a randomly sampled data point
to be misclassified is bounded from above as:

$\displaystyle
P\big{(}(x,\ell)\sim\mathcal{D}_{\epsilon},s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})$
$\displaystyle\,:\,f(x+s)\neq\ell\big{)}\leq
A^{n}\Big{(}1-\Big{(}\frac{\epsilon}{1+\delta}\Big{)}^{2}\Big{)}^{\frac{n}{2}}.$

In particular, when $\delta$ is independent of dimension $n$, this probability
converges to 0 exponentially with $n$.

This probability bound is compared against empirically sampled data in Figure
3(b). While the bound is not particularly sharp in low dimensions, it
accurately describes the key phenomenon which is the convergence of the
probability to 0 in high dimensions. This phenomenon is startlingly
persistent, even when the magnitude of the sampled perturbations is 50 times
greater than the distance between the centres of the spheres (when
$\delta=2.5$).

We note that some care needs to be taken when considering perturbations with
fixed $\ell^{\infty}$ norms. The corresponding $\ell^{2}$ norm of these
perturbations scales as $\sqrt{n}$, affecting convergence to $0$ of the
probability of destabilisation (see Theorem 4).

A further aspect of this model problem is that successful adversarial attacks
are universal in high dimensions. We define the _destabilisation margin_ to be
the distance by which a destabilising perturbation pushes a data point across
the decision threshold of the classifier (1). This is measured by the
functions $d_{\ell}:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}$
associated with each class $\ell=0,1$, where, for a data point $x$ and a
perturbation $s$,

$\displaystyle d_{0}(x,s)=\max\\{x_{1}+s_{1},0\\},$

and

$\displaystyle d_{1}(x,s)=\max\\{-x_{1}-s_{1},0\\}.$

The following result then holds, as proven in Section C.4 of the supplementary
material.

######  Theorem 5 (Universality of adversarial attacks).

Let $\epsilon\geq 0$ and suppose that $x,z\sim\mathcal{D}_{\epsilon}$ are
independently sampled points with the same class label $\ell$. For any
$\gamma\in(0,1]$, the probability that $x$ is destabilised by all
perturbations $s\in\mathbb{R}^{n}$ which destabilise $z$ with destabilisation
margin $d_{\ell}(z,s)>\gamma$ converges exponentially to 1 as the dimension
$n$ increases. Specifically, for $\ell\in\\{0,1\\}$ and $z\in\mathbb{R}^{n}$,
let $S_{z}=\\{s\in\mathbb{R}^{n}\,:\,d_{\ell}(z,s)>\gamma\\}$. Then,

$\displaystyle P(x,z$
$\displaystyle\sim\mathcal{D}_{\ell}\,:\,f(x+s)\neq\ell\text{ for all }s\in
S_{z})\geq
1-A^{2n}\Big{[}1-\Big{(}1-\frac{1}{2}\Big{(}1-\frac{\gamma^{2}}{4}\Big{)}^{\frac{n}{2}}\Big{)}^{2}\Big{]}.$

The anatomy of this bound is slightly obfuscated at first glance by the
presence of the distribution growth parameter $A$. In the case when $A=1$,
which implies that both distributions are uniform, the lower bound takes the
simpler form $(1-\frac{1}{2}(1-\frac{\gamma^{2}}{4})^{\frac{n}{2}})^{2}.$ When
$n$ is large, we may expect that the term
$\frac{1}{2}(1-\frac{\gamma^{2}}{4})^{\frac{n}{2}}$ is close to zero since
$\gamma\in(0,1]$, and the simplified bound is therefore close to 1. The value
inside the square brackets of the general bound may therefore be expected to
be close to 0, implying that the complete lower bound is close to 1 for
sufficiently large $n$, even if $A$ is large.

The dependence of the bound in Theorem 5 on the margin $\gamma$ by which the
perturbation destabilises $z$ is an interesting feature. Roughly speaking, the
result suggests that in low dimensions only severe perturbations which push
points a long way past the decision threshold may be regarded as universal in
the sense of having a high probability of destabilising other sampled points.
As the dimension $n$ increases, however, perturbations which produce smaller
and smaller margins on individual points become universal in the sense that
they have a constant probability of destabilising other sampled points.

Common algorithms for constructing adversarial attacks work by perturbing the
target input in such a way as to increase an appropriate loss function.
Gradient-based methods for this, such as the Fast Gradient Sign Method [5],
compute the gradient of the loss function with respect to the components of
the input, evaluated at the target input with its true class. Perturbing the
input in the direction of this gradient therefore moves it in the direction of
steepest ascent of the loss function locally, thereby representing a good
candidate for an adversarial direction. The minimal scaling to be applied to
this adversarial direction, required to form the final adversarial input, can
then be determined via a line search in the adversarial direction.

In the case of this model setup, such an algorithm (with a standard choice of
loss function) will successfully provide the optimal direction for an
adversarial attack: the most direct path to move the input along in order to
cross the decision surface. To show this, we first observe that the classifier
$f$ in (1) can be equivalently defined as $f(x)=H(g(x))$, where
$H:\mathbb{R}\to\\{0,1\\}$ denotes the (piecewise constant) Heaviside
function, and the linear function $g(x)=\mathbf{e}_{1}\cdot x-\frac{1}{2}$. To
construct gradient-based attacks, we use a differentiable version $\tilde{f}$
of $f$ constructed as $\tilde{f}(x)=\sigma(g(x))$, where
$\sigma:\mathbb{R}\to(0,1)$ is a continuously differentiable version of the
Heaviside function which is monotonically increasing with
$\sigma(0)=\frac{1}{2}$. An example of such a function is the standard sigmoid
function. Then, the following result, proved in Section C.5 of the
supplementary material, shows that gradient-based attacks on this classifier
will always return the optimal attack direction.

######  Theorem 6 (Gradient-based methods find the optimal adversarial
attack).

Let $L:\mathbb{R}_{>0}\to\mathbb{R}$ denote any differentiable, monotonically
increasing loss function. For any $(x,\ell)\sim\mathcal{D}_{\epsilon}$, the
gradient of the loss $L(|\tilde{f}(x)-\ell|)$ with respect to the components
of $x$ corresponds to a positive multiple of the optimal attack direction
$(1-2\ell)\mathbf{e}_{1}$.

###  3.1. Generalisations

Despite its simplicity, the model presented above covers a variety of
settings, including data sampled from many common distributions such as
uniform distributions and truncated Gaussian distributions. The model may also
be directly generalised to cover an even wider range of settings. In Section
E, we present analogous results for classifiers with non-flat decision
surfaces separating two general distributions. As corollaries of these
results, we obtain variants of the theorems presented above for the more
general case when $r\neq 1$.

Further generalised scenarios in which our results may be applied are depicted
in Figure 4. Panel $a$ simply shows the original setup, with the red dashed
line showing the decision surface of the classifier $f$.

Panel $b$ visualises a more general case in which the data from only one class
is supported in a ball and satisfies the SmAC property, while the other data
class belongs to some different class of distributions. A more general non-
flat decision boundary is depicted as a green dashed line in this case, which
we suppose may be sufficiently well approximated _locally_ by a hyperplane
(depicted as a red dashed line). All results derived above (corresponding to
the case of panel $a$) apply here for samples drawn from $\mathcal{D}_{1}$.

Panel $c$ shows the general setting in which both classes are sampled from
non-SmAC distributions. However, if there is a subdomain $\hat{D}$ near the
decision surface within which one distribution is locally SmAC and the
decision boundary in that domain is sufficiently well approximated locally by
a hyperplane, then the problem can be considered as a local version of case
$b$.

Figure 4. Different scenarios to which the simple two ball model may be
generalised.

##  4\. Discussion and relation to prior work

###  4.1. Existence of adversarial examples

Since the seminal work [17] reporting the discovery of adversarial examples in
deep neural networks, the topic of adversarial examples as well as their
origins and the mechanisms behind their occurrence have been the focus of
significant attention in theoretical and computational machine learning
communities. One hypothesis, expressed in [17] was that the existence of the
adversarial examples could be attributed to the inherent instabilities – i.e.,
large Jacobian norms leading to large Lipschitz constants for the
classification maps. Theorems 3, 4 (see also Theorems 10 and 11 in Section D
of the supplementary material) show that whilst the later mechanism may indeed
constitute a feasible route for adversarial examples to occur, our presented
framework reveals a simple and under-explored pathway for adversarial data to
emerge naturally in systems without large Jacobian norms.

###  4.2. Fragility of adversarial examples

An interesting additional property of adversarial examples has been
empirically observed in [12, 7]. It has been found that the capability of
adversarial examples to fool the classifiers they have been designed for could
be hindered by perturbations and transformations which are naturally present
in real-world environments. Here we show and prove (Theorems 4 and 11) that in
the vicinity of the target images, adversarial examples may indeed occupy sets
whose Lebesgue measure is exponentially small. Hence, the addition of a small
but appropriate perturbation to an example of that type will have the
capability to make it non-adversarial.

###  4.3. Universality of adversarial examples

Another striking feature of adversarial examples is their potential
universality. The phenomenon has first been reported in [13] and since then
observed in a wide range of tasks and architectures [3]. Several explanations
justifying the existence of universal adversarial examples have been proposed
in the literature. This includes the view that universal perturbations may
exploit correlated lower-dimensional structures in the classifier’s decision
boundaries. It has been less clear how to explain the simultaneous existence,
fragility, typicality, and universality of adversarial perturbations. Theorems
3, 4, and 5 show that the combination of these correlations with the high
dimensionality of data may explain the co-existence of the typicality of
adversarial examples, their fragility, and at the same time universality.

###  4.4. Typicality of adversarial examples

Several works have presented feasible mechanisms explaining the potential
typicality and prevalence of adversarial data. In [14], [19] the authors
exploited concentration of measure arguments to conclude that small
destabilising perturbations can be typical in high dimensional settings. These
arguments, however, do not explain the simultaneous rarity of destabilising
random perturbations and the typicality of adversarial examples (see Fig. 6
and the discussion below). The connection of these two phenomena is a key
feature of our framework.

###  4.5. Notions of stability

Our present work reveals a new unexplored relationship between stability and
the existence of adversarial data. We show that the ubiquitous presence of
adversarial data perturbations which destabilise the classifier is not
contradictory to the robustness of the classifier to random perturbations of
the data. If we view the former as a form of _deterministic instability_ (i.e.
there exist destabilising perturbations), and the latter as a form of
_probabilistic stability_ (destabilising perturbations are unlikely to be
sampled at random), it becomes apparent that the probabilistic stability is in
fact masking the underlying instability. Since these two notions of stability
are clearly not equivalent, it is imperative to understand the distinctions
between the two. To clarify this intriguing relationship, let us first recall
two relevant definitions of stability (cf. [8]).

######  Definition 7 ($\epsilon$-stability).

The classification map $f:\mathbb{R}^{n}\rightarrow\\{0,1\\}$ is
$\epsilon$-stable at $x$ if

$f(x+s)=f(x)\ \text{ for all }\ s\in\mathbb{B}_{\epsilon}^{n}.$

######  Definition 8 ($\epsilon$-stability with confidence $\upsilon$).

Let $\mu$ be a probability distribution on $\mathbb{B}_{\epsilon}^{n}$. The
classification map $f:\mathbb{R}^{n}\rightarrow\\{0,1\\}$ is $\epsilon$-stable
at $x$ with confidence $\upsilon$ w.r.t. the distribution $\mu$ if

$P(s\sim\mu\,:\,f(x+s)=f(x))\geq\upsilon.$

Figure 5. Adversarial susceptibility of seemingly stable classifiers. Points
$x$ and $y$ are in the $\Delta$ thickening of disc intersecting the ball
$\mathcal{D}_{1}$ along one of its largest equators. For $n$ sufficiently
large, most points sampled from $\mathcal{U}(D_{1})$ belong to this domain.
Both $x$ and $y$ are $(\epsilon-\Delta)$-stable. At the same time, they are
also $\delta$-stable with confidence $\upsilon\eqsim 1$.

At the core of the phenomenon explored in Theorems 3 and 4 is the fact that a
“typical” point $x$ is $\delta$-stable with confidence $\upsilon$ with respect
to perturbations sampled from $\mathcal{U}(\mathbb{B}^{n}_{\delta})$, where
$\upsilon$ approaches $1$ exponentially in $n$. This makes the finding of
adversarial perturbations by adding random samples
$s\sim\mathcal{U}(\mathbb{B}_{\delta}^{n})$ difficult and unlikely.

At the same time, for $n$ sufficiently large, typical points are located in
some $\Delta<\epsilon$ vicinity of the equators of the $n$-dimensional unit
balls supporting $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$. This implies that
these typical points are $\epsilon-\Delta$-stable in the sense of Definition
7. This is visualised in the diagram shown in Figure 5. In the absence of the
margin $\epsilon$ separating the centres of $\mathcal{D}_{0}$ and
$\mathcal{D}_{1}$, there is no room to “hide” adversarial examples among
random perturbations. This leads to an intriguing observation:

> The existence and prevalence of adversarial examples, which are undetectable
> via random perturbations, can sometimes be facilitated and even induced, by
> $\epsilon^{\prime}$-stability (for some appropriately chosen
> $\epsilon^{\prime}$) of “typical” data samples.

Figure 6. The empirical probability of sampling a point and perturbation of
size $\delta$ such that the perturbed data point is misclassified, under the
two hemispheres model with $\epsilon=0$. This empirical data was computed by
sampling 10,000 points from the hemisphere distribution and 10,000
perturbations from $\mathcal{U}(\mathbb{B}^{n}_{\delta})$.

To illustrate the practical consequences of this, we investigated a model in
which two data classes were sampled from complementary half-balls separated by
margin $\epsilon\geq 0$ (see Section D of the supplementary material). This
choice of model is motivated by its ability to represent two separable classes
without any margin or overlap. Figure 6 shows the results of numerical
experiments computing the frequency with which sampled data was misclassified
after random perturbations of the form
$s\sim\mathcal{U}(\mathbb{B}_{\delta}^{n})$ when $\epsilon=0$, for different
values of $\delta$ and $n$. This demonstrates that in the absence of margins
(which is an admissible case in the setup adopted in [14]) the probability of
registering misclassifications due to random perturbation is significant and
does not change much with dimension.

##  5\. Conclusion

Our new framework for studying the paradox of apparent stability in
classification problems allows for rigorous probabilistic bounds that are
consistent with empirical observations concerning vulnerability to worst-case
(Theorem 3), random (Theorem 4), universal (Theorem 5) and computable (Theorem
6) attacks. The results are generic in the sense that they deal with small
perturbations under which any smooth and accurate classifier will behave like
the optimal linear classifier (1). As illustrated in Figure 4 and Section 3.1,
the setup can be generalised to cover to broad range of input distributions
and classification boundaries. We envisage that the results will also extend
readily to comparable multiclass problems. In addition to quantifying
vulnerabilities, our analysis also raises new issues concerning the most
relevant and useful notions of stability in classification.

The overlapping unit ball model that we used, and the two hemispheres model in
Section D of the supplementary material, are closely tied to the use of the
Euclidean norm. We note that there are several applications where spherical
input data arises naturally, including remote sensing, climate change
modeling, global ionospheric prediction and environmental governance, [4]. It
would of course be of interest to establish the extent to which these results
can be extended to other choices of norm and input domain. We also note that
more customised results could be investigated for specific classification
tools by exploiting further information, for example, about the architecture,
training regime and level of floating point accuracy.

## Acknowledgements

O.J.S., Q.Z., I.Y.T. and A.N.G. are grateful for financial support by the UKRI
and EPSRC (UKRI Turing AI Fellowship ARaISE EP/V025295/1). I.Y.T. is also
grateful for support from the UKRI Trustworthy Autonomous Systems Node in
Verifiability EP/V026801/1. D.J.H. and A.B. were supported by EPSRC grant
EP/V046527/1.

## References

  * Abadi et al. [2015] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  URL https://www.tensorflow.org/.  Software available from tensorflow.org.
  * Bastounis et al. [2021] A. Bastounis, A. C. Hansen, and V. Vlačić.  The mathematics of adversarial attacks in AI–why deep learning is unstable despite the existence of stable neural networks.  _arXiv preprint arXiv:2109.06098_ , 2021.
  * Chaubey et al. [2020] A. Chaubey, N. Agrawal, K. Barnwal, K. K. Guliani, and P. Mehta.  Universal adversarial perturbations: A survey.  _arXiv preprint arXiv:2005.08087_ , 2020.
  * Feng et al. [2021] H. Feng, S. Huang, and D.-X. Zhou.  Generalization analysis of CNNs for classification on spheres.  _IEEE Transactions on Neural Networks and Learning Systems_ , pages 1–14, 2021.  doi: 10.1109/TNNLS.2021.3134675.
  * Goodfellow et al. [2015] I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  In Y. Bengio and Y. LeCun, editors, _3rd International Conference on Learning Representations, San Diego, CA_ , 2015.  URL http://arxiv.org/abs/1412.6572.
  * Gorban et al. [2018] A. Gorban, A. Golubkov, B. Grechuk, E. Mirkes, and I. Tyukin.  Correction of AI systems by linear discriminants: Probabilistic foundations.  _Information Sciences_ , 466:303–322, 2018.  ISSN 0020-0255.  doi: https://doi.org/10.1016/j.ins.2018.07.040.  URL https://www.sciencedirect.com/science/article/pii/S0020025518305607.
  * Gupta et al. [2020] K. D. Gupta, D. Dasgupta, and Z. Akhtar.  Applicability issues of evasion-based adversarial attacks and mitigation techniques.  In _2020 IEEE Symposium Series on Computational Intelligence (SSCI)_ , pages 1506–1515. IEEE, 2020.
  * Huang et al. [2022] P. Huang, Y. Yang, M. Liu, F. Jia, F. Ma, and J. Zhang.  $\epsilon$-weakened robustness of deep neural networks.  In _Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis_ , pages 126–138, 2022.
  * Khoury and Hadfield-Menell [2018] M. Khoury and D. Hadfield-Menell.  On the geometry of adversarial examples.  _arXiv preprint arXiv:1811.00525_ , 2018.
  * King’s College London [2022] King’s College London.  King’s Computational Research, Engineering and Technology Environment (CREATE), 2022.  URL https://doi.org/10.18742/rnvf-m076.
  * Krizhevsky [2009] A. Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * Kurakin et al. [2018] A. Kurakin, I. J. Goodfellow, and S. Bengio.  Adversarial examples in the physical world.  In _Artificial intelligence safety and security_ , pages 99–112. Chapman and Hall/CRC, 2018.
  * Moosavi-Dezfooli et al. [2017] S.-M. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard.  Universal adversarial perturbations.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1765–1773, 2017.
  * Shafahi et al. [2019] A. Shafahi, W. Huang, C. Studer, S. Feizi, and T. Goldstein.  Are adversarial examples inevitable?  _International Conference on Learning Representations, New Orleans, USA_ , 2019.
  * Shamir et al. [2021] A. Shamir, O. Melamed, and O. BenShmuel.  The dimpled manifold model of adversarial examples in machine learning.  _arXiv preprint arXiv:2106.10151_ , 2021.
  * Simonyan and Zisserman [2015] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition, 2015\.
  * Szegedy et al. [2013] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Tanay and Griffin [2016] T. Tanay and L. Griffin.  A boundary tilting persepective on the phenomenon of adversarial examples.  _arXiv preprint arXiv:1608.07690_ , 2016.
  * Tyukin et al. [2020] I. Y. Tyukin, D. J. Higham, and A. N. Gorban.  On adversarial examples and stealth attacks in artificial intelligence systems.  In _2020 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–6. IEEE, 2020.

## SUPPLEMENTARY MATERIAL

##  Appendix A Experimental setup

To present the phenomenon in a simple setting, we arranged the 10 classes of
the CIFAR-10 dataset into 45 binary classification problems.

###  A.1. Network architecture

Convolutional neural networks were trained on each of these problems, using
the same architecture and training regime for each problem. In each case we
used a simplification of the VGG architecture [16] adapted to the $32\times
32\times 3$ resolution of the CIFAR-10 images, the details of which are given
in Table 1. The English names associated with each of the 10 classes are
provided in Table 2.

For each pair-wise binary classification problem, the classes were assigned
the labels 0 and 1, for compatibility with a standard sigmoid function on the
output node of the network. A mean square error loss function was used to
train the network in Tensorflow [1] using stochastic gradient descent for 100
epochs with Nesterov momentum parameter 0.9 and an initial learning rate of
0.1, which was halved every 20 epochs. Dropout was used on the convolutional
layers during training, with a parameter of 0.4.

For the binary classification problem of distinguishing class $i$ from class
$j$, we denote the training set by $\mathcal{X}_{i,j}$, and the test set by
$\mathcal{Y}_{i,j}$. The subsets of training and test images which were
correctly classified by the network are then denoted by
$\mathcal{X}^{\operatorname{corr}}_{i,j}\subset\mathcal{X}_{i,j}$ and
$\mathcal{Y}^{\operatorname{corr}}_{i,j}\subset\mathcal{Y}_{i,j}$
respectively.

We are therefore able to compute the training and test accuracy of the network
for the binary classification problem involving class $i$ and class $j$ as the
percentages

(2) $\displaystyle
100\frac{\operatorname{card}(\mathcal{X}^{\operatorname{corr}}_{i,j})}{\operatorname{card}(\mathcal{X}_{i,j})}\,\text{
and
}\,100\frac{\operatorname{card}(\mathcal{X}^{\operatorname{corr}}_{i,j})}{\operatorname{card}(\mathcal{X}_{i,j})},$

respectively, where we use $\operatorname{card}$ to denote the cardinality of
a set.

Layer | Size | Output channels | Number of trainable parameters
---|---|---|---
Conv-1 | $3\times 3$ | 64 | 1,792
Conv-2 | $3\times 3$ | 64 | 36,928
Max pooling | $2\times 2$ |  |
Conv-3 | $3\times 3$ | 128 | 73,856
Conv-4 | $3\times 3$ | 128 | 147,584
Max pooling | $2\times 2$ |  |
Conv-5 | $3\times 3$ | 256 | 295,168
Conv-6 | $3\times 3$ | 256 | 590,080
Dense |  | 512 | 131,584
Dense |  | 1 | 513
Table 1. Architecture used for the CIFAR-10 binary classification problems. All convolutional layers do not pad their output, meaning that the output shape of Conv-6 is $1\times 1\times 256$, and are followed by a leaky ReLU activation function with leakiness parameter 0.1. The final dense layer has a standard sigmoid activation function. Index | Name
---|---
0 | Aeroplane
1 | Automobile
2 | Bird
3 | Cat
4 | Deer
5 | Dog
6 | Frog
7 | Horse
8 | Ship
9 | Truck
Table 2. Class names associated with each class index.

###  A.2. Adversarial attacks

To investigate the susceptibility of the networks to adversarial attacks, we
used a standard gradient-based algorithm on a loss function, which can be
viewed as an Euclidean version of the Fast Gradient Sign Method (FGSM)
introduced in [5]. Specifically, if $L(x,y,N)$ denotes the mean square error
loss function evaluated on the neural network $N$ at the target image $x$ with
label $\ell$, we compute the adversarial attack direction as

$\displaystyle a(x)=\frac{\nabla_{x}L(x,\ell,N)}{\|\nabla_{x}L(x,\ell,N)\|},$

where $\|\cdot\|$ denotes the Euclidean norm. We then tested 100 equally-
spaced scalings $\epsilon\in[0,5]$ to determine the smallest value such that
$|\ell-N(x+\epsilon a(x))|>\frac{1}{2}$. This value of $\epsilon$ therefore
gives the Euclidean norm of the smallest perturbation (among those tested) in
the direction of $a(x)$ such that the network therefore predicts the wrong
class for the attacked image. The value of $\epsilon$ therefore provides an
upper bound on the minimal Euclidean distance of the image $x$ from the
decision surface of the neural network $N$.

For the class $i$ vs class $j$ binary classification problem, we use
$\mathcal{X}_{i,j}^{\operatorname{adv}}\subset\mathcal{X}^{\operatorname{corr}}_{i,j}$
to denote the set of training images
$x\in\mathcal{X}^{\operatorname{corr}}_{i,j}$ such that $x$ was correctly
classified by the network, but $x+\epsilon a(x)$ was misclassified for at
least one of our tested values of $\epsilon$. The equivalent subset of the
test set is denoted by
$\mathcal{Y}_{i,j}^{\operatorname{adv}}\subset\mathcal{Y}^{\operatorname{corr}}_{i,j}$.
We may then define the _adversarial susceptibility_ of the network for the
training and test sets as the percentages

(3) $\displaystyle
100\frac{\operatorname{card}(\mathcal{X}_{i,j}^{\operatorname{adv}})}{\operatorname{card}(\mathcal{X}^{\operatorname{corr}}_{i,j})},\,\text{
and
}\,100\frac{\operatorname{card}(\mathcal{Y}_{i,j}^{\operatorname{adv}})}{\operatorname{card}(\mathcal{Y}^{\operatorname{corr}}_{i,j})},$

respectively, where we use $\operatorname{card}$ to denote the cardinality of
a set.

The results of these experiments are reported in Section B.2.

###  A.3. Random perturbations

To assess the effect on the network of random perturbations to the images, we
sampled a set $P$ of 2000 random perturbations from a uniform distribution on
the $d$-dimensional ball with Euclidean norm $\leq 1$, where $d=3,072$ denotes
the number of individual attributes of a $32\times 32\times 3$ CIFAR-10 image.
Then, for each pair $i,j$ of classes, we performed the following experiment.
For each image $x$ in the subsets $\mathcal{X}_{i,j}^{\operatorname{adv}}$ and
$\mathcal{Y}_{i,j}^{\operatorname{adv}}$ of the training and test sets which
were susceptible to an adversarial attack, we constructed the perturbed image
$x+\delta\epsilon s$ for each $s\in P$, where $\epsilon$ denotes the Euclidean
norm of the smallest successful adversarial attack on $x$, scaled by each
value of $\delta\in\\{1,2,5,10\\}$ sequentially. In other words, we evaluated
the network on an image which was perturbed by a random perturbation with
Euclidean norm scaled by a fixed multiple of that of the (known successful)
adversarial attack.

For the class $i$ vs class $j$ binary classification problem, we define the
set
$\mathcal{X}^{\operatorname{rand},\delta}_{i,j}\subset\mathcal{X}^{\operatorname{adv}}_{i,j}$
as the set of images which were susceptible to one or more random
perturbations with scaling factor $\delta$, as described above. The set
$\mathcal{Y}^{\operatorname{rand},\delta}_{i,j}\subset\mathcal{Y}^{\operatorname{adv}}_{i,j}$
is defined analogously on the test set of images.

This enables us to define the _random perturbation susceptibility_ of each
network for the training and test sets as the percentages

(4) $\displaystyle
100\frac{\operatorname{card}(\mathcal{X}_{i,j}^{\operatorname{rand},\delta})}{\operatorname{card}(\mathcal{X}^{\operatorname{adv}}_{i,j})},\,\text{
and
}\,100\frac{\operatorname{card}(\mathcal{Y}_{i,j}^{\operatorname{rand},\delta})}{\operatorname{card}(\mathcal{Y}^{\operatorname{adv}}_{i,j})},$

respectively for each tested value of $\delta$, where we use
$\operatorname{card}$ to denote the cardinality of a set.

The results of these experiments are reported in Section B.3.

###  A.4. Training with random perturbations

We explored the effect of applying additive random noise to images during
training on adversarial robustness. To do this we inserted a layer at the
beginning of the network architecture described in Table 1 which sampled noise
from a prescribed distribution independently for each input and added it to
the input. The precise random perturbation added to each image is therefore
different each time the image is presented to the network during training. The
random perturbation layer is only active during training, so does not affect
how the trained network is assessed at test time. We experimented with noise
sampled uniformly from the cube $[-a,a]^{n}$ (i.e. with maximum
$\ell^{\infty}$ norm $a>0$ and with noise sampled from the ball
$\mathbb{B}^{n}_{b}$ (i.e. with maximum Euclidean norm $b>0$), with
$a\in\\{0.1,0.5,1.0\\}$, $b\in\\{3.2,16,32\\}$, where $n=32\times 32\times
3=3072$ is the dimension of a CIFAR-10 image. These values of $a$ and $b$ were
selected to ensure that for each pair of $a$ and $b$ values the samples from
each distribution would have approximately the same Euclidean norm on average.
This enables us to observe whether the sampling distribution makes a
significant impact on the results, independently of the magnitude. Each
network was otherwise trained exactly as described in Section A.1. We report
the results of these experiments in Section B.4.

##  Appendix B Discussion of experimental results

We now discuss the results of the experiments outlined in Section A. These
results were computed using the CREATE HPC facilities at King’s College London
[10].

###  B.1. Network performance

The training and test accuracy of the networks trained on each of the binary
classification problems is shown in Table 3. The mean accuracy on the training
set of the networks trained for all of the binary classification problems was
99.57% (standard deviation 0.24), with a minimum of 98.74%. In comparison, the
mean accuracy on the test set was 94.09% (standard deviation 3.78), with a
minimum of 82.6%. These figures indicate that the networks were generally
quite capable to learning these binary classification problems, despite the
fact they were trained using the same regime for only 100 training epochs
each, and no specific tweaks were applied to improve the performance of any
network.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 | 99.88, 96.45 | 99.31, 91.70 | 99.40, 95.20 | 99.36, 94.65 | 99.67, 95.45 | 99.25, 96.05 | 99.49, 96.45 | 99.73, 94.10 | 99.77, 95.40
1 |  | 99.67, 96.65 | 99.46, 95.95 | 99.78, 98.10 | 99.75, 97.55 | 99.17, 96.85 | 99.91, 98.80 | 99.72, 96.85 | 99.77, 93.65
2 |  |  | 99.08, 85.20 | 99.70, 87.25 | 99.35, 87.05 | 99.68, 91.05 | 99.63, 92.90 | 99.58, 95.30 | 99.42, 95.80
3 |  |  |  | 98.74, 86.70 | 99.77, 82.60 | 99.09, 88.80 | 99.68, 91.35 | 99.53, 96.05 | 99.47, 95.05
4 |  |  |  |  | 99.59, 90.60 | 99.84, 94.90 | 99.78, 90.30 | 99.58, 97.20 | 99.42, 96.75
5 |  |  |  |  |  | 99.79, 93.95 | 99.72, 90.40 | 99.60, 96.85 | 99.41, 96.05
6 |  |  |  |  |  |  | 99.85, 96.70 | 99.40, 97.10 | 99.72, 97.20
7 |  |  |  |  |  |  |  | 99.70, 97.65 | 99.85, 97.60
8 |  |  |  |  |  |  |  |  | 99.78, 95.80

Table 3. Accuracy of the networks on the binary classification problems,
reported in the form ‘train accuracy, test accuracy’, where accuracy is
calculated as the percentage of images which were correctly classified. The
row and column headers indicate the classes used in each binary classification
problem.

###  B.2. Adversarial attacks

We report the adversarial susceptibility of each network (as defined in
Section A.2) in Table 4. On average over all the binary classification
problems, 85.0% of the training images were susceptible to an adversarial
attack (standard deviation 9.71) with a minimum of 70.28%, while the average
on the test set was 79.48% (standard deviation 7.91) with a minimum of 69.82%.
We note that both minima were attained on the same task ‘frog-vs-ship’
(6-vs-8). In the vast majority of the binary classification problems, over 80%
of images in the training and test sets could be adversarially attacked in
such a way that they would be misclassified by the network. This demonstrates
the susceptibility of all of the networks to adversarial attacks, implying
that the decision surface in each case passes close to most of the points in
the training and test sets.

To measure just how close the decision surface passes to each data point, we
also explore the sizes of the computed adversarial perturbations measured in
several norms. In Table 5 we show the mean and standard deviations over each
training and test set of the Euclidean norms of the smallest computed
adversarial attack on each image. Similarly, Table 6 shows the mean and
standard deviations over each training and test set of the $\ell^{1}$ norms of
the adversarial attacks, while Table 7 shows the same information for the
$\ell^{\infty}$ norms.

The summary statistics reported in these tables are broken down in violin
plots for a representative sample of the binary classification problems
(selected, for simplicity, as the ‘$i$-vs-$(i+1)$’ problems). These show an
approximation of the distribution of the Euclidean norms (Figure 7),
$\ell^{\infty}$ norms (Figure 8) and $\ell^{1}$ norms (Figure 9) of
adversarial attacks. In each case, this is the distribution across the whole
training or test set of the norm of the smallest misclassifying adversarial
attack found for each image using the algorithm described in Section A.2. It
is clear from these plots that for the majority of the adversarial attacks the
largest change to any individual pixel value is comparatively small: the
$\ell^{\infty}$ norm is less than 0.2 for most of the images across all tasks.
The $\ell^{1}$ norms, on the other hand, compute the sum of the absolute value
of all changes to all pixels, so are expected to be a much larger value.
Scaling these $\ell^{1}$ norms by the number of pixel channels ($32\times
32\times 3=3,072$), we obtain the mean absolute change to a single pixel.
Taking 100 as a representative maximum value for the $\ell^{1}$ norm across
the majority of cases, we can therefore observe that this would correspond to
a mean absolute change of approximately 0.03. Comparing this value to a
similarly representative value of less than 0.5 for the $\ell^{\infty}$ norm
of the adversarial attack, it is clear that this implies that the attacks are
typically very localised since most of the change must be focused in just a
few pixels.

The plots also indicate that the networks trained on certain tasks (such as
‘bird-vs-cat’ (2-vs-3) and ‘cat-vs-deer’ (3-vs-4) seem to be much more
susceptible to small adversarial attacks. We mean this in the sense that while
the overall attack susceptibility (Table 4) is quite typical, the attacks
themselves on these classes appear to have much smaller norms.

The conclusion from these experiments is that most points in all of the
training and test sets lie very close to the decision surface of the neural
network, implying that the networks are susceptible to small perturbations to
most of their training and test data.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 | 88.33, 86.88 | 95.69, 96.24 | 86.74, 86.08 | 95.19, 94.35 | 85.27, 83.97 | 83.43, 81.68 | 89.47, 88.02 | 92.78, 91.87 | 74.23, 73.69
1 |  | 86.25, 86.08 | 84.52, 83.79 | 93.59, 92.92 | 89.94, 88.83 | 85.23, 85.91 | 97.17, 97.17 | 89.62, 88.80 | 87.85, 88.04
2 |  |  | 91.88, 89.96 | 99.54, 99.66 | 96.93, 96.50 | 96.75, 96.05 | 92.97, 93.16 | 85.14, 83.89 | 92.73, 92.75
3 |  |  |  | 93.85, 92.85 | 99.86, 99.82 | 98.49, 98.65 | 98.95, 98.63 | 91.93, 92.04 | 78.84, 78.12
4 |  |  |  |  | 98.97, 98.34 | 98.99, 98.79 | 99.77, 99.56 | 80.96, 80.45 | 90.02, 90.08
5 |  |  |  |  |  | 96.19, 95.48 | 99.61, 99.61 | 84.14, 83.32 | 72.53, 71.63
6 |  |  |  |  |  |  | 98.63, 98.76 | 70.28, 69.82 | 87.35, 88.22
7 |  |  |  |  |  |  |  | 82.60, 83.56 | 96.85, 96.82
8 |  |  |  |  |  |  |  |  | 79.41, 78.03

Table 4. Susceptibility of the networks to adversarial attacks, reported in
the form ‘train susceptibility, test susceptibility’, where susceptibility is
calculated as in (3) as the percentage of images from the training set and
test set which were misclassified after an adversarial attack using the
algorithm described in Section A.2. The row and column headers indicate the
classes used in each binary classification problem.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 train | 1.25 (0.92) | 0.76 (0.60) | 1.19 (0.86) | 0.96 (0.84) | 1.32 (0.94) | 1.21 (0.83) | 1.24 (0.92) | 0.84 (0.81) | 1.20 (1.01)
test | 1.25 (0.94) | 0.79 (0.66) | 1.21 (0.92) | 0.97 (0.81) | 1.36 (0.97) | 1.24 (0.83) | 1.26 (0.94) | 0.83 (0.83) | 1.25 (1.03)
1 train |  | 1.32 (0.93) | 1.00 (0.58) | 1.13 (0.82) | 1.27 (0.71) | 0.96 (0.63) | 1.50 (0.92) | 1.08 (0.86) | 0.75 (0.74)
test |  | 1.35 (0.96) | 1.00 (0.58) | 1.14 (0.86) | 1.28 (0.70) | 0.99 (0.62) | 1.47 (0.91) | 1.06 (0.87) | 0.74 (0.75)
2 train |  |  | 0.40 (0.31) | 0.48 (0.37) | 0.64 (0.53) | 0.56 (0.45) | 0.86 (0.70) | 1.05 (0.72) | 1.21 (0.89)
test |  |  | 0.37 (0.32) | 0.47 (0.41) | 0.63 (0.58) | 0.57 (0.51) | 0.86 (0.75) | 1.06 (0.75) | 1.22 (0.90)
3 train |  |  |  | 0.47 (0.41) | 0.40 (0.26) | 0.74 (0.55) | 0.58 (0.45) | 1.27 (0.87) | 0.72 (0.45)
test |  |  |  | 0.44 (0.40) | 0.35 (0.31) | 0.73 (0.58) | 0.57 (0.46) | 1.29 (0.89) | 0.72 (0.46)
4 train |  |  |  |  | 0.68 (0.50) | 0.54 (0.40) | 0.65 (0.44) | 1.17 (0.90) | 1.03 (0.75)
test |  |  |  |  | 0.67 (0.53) | 0.53 (0.43) | 0.63 (0.50) | 1.21 (0.91) | 1.07 (0.76)
5 train |  |  |  |  |  | 0.75 (0.58) | 0.73 (0.50) | 1.33 (0.90) | 0.94 (0.68)
test |  |  |  |  |  | 0.77 (0.59) | 0.70 (0.53) | 1.32 (0.90) | 0.98 (0.71)
6 train |  |  |  |  |  |  | 0.82 (0.49) | 1.38 (1.06) | 0.94 (0.56)
test |  |  |  |  |  |  | 0.83 (0.51) | 1.42 (1.08) | 0.97 (0.58)
7 train |  |  |  |  |  |  |  | 1.39 (0.93) | 1.05 (0.69)
test |  |  |  |  |  |  |  | 1.41 (0.97) | 1.05 (0.66)
8 train |  |  |  |  |  |  |  |  | 1.14 (1.02)
test |  |  |  |  |  |  |  |  | 1.13 (1.05)

Table 5. Means and standard deviations of the Euclidean norms norms of the
smallest successful adversarial attack on each image in the training and test
set, reported in the form ‘mean (standard deviation)’. The numbers in the row
and column headers indicate the classes used in each binary classification
problem. The ‘train’ row shows the values computed over the training set,
while the ‘test’ row shows the values computed over the test set.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 train | 43.58 (31.63) | 24.81 (19.52) | 40.77 (30.04) | 32.93 (29.12) | 43.40 (31.07) | 40.08 (27.55) | 43.21 (32.21) | 27.75 (26.27) | 41.17 (34.03)
test | 43.75 (32.53) | 25.80 (21.35) | 41.29 (31.76) | 33.23 (28.07) | 44.58 (31.90) | 41.01 (27.42) | 43.99 (32.61) | 27.31 (26.69) | 42.73 (35.09)
1 train |  | 43.67 (30.41) | 31.26 (18.66) | 37.92 (26.88) | 41.80 (23.68) | 30.91 (20.83) | 50.20 (30.37) | 36.27 (28.58) | 23.48 (22.71)
test |  | 44.62 (31.28) | 31.42 (18.83) | 38.38 (28.13) | 42.21 (23.44) | 31.85 (20.46) | 49.17 (29.95) | 35.49 (28.86) | 23.24 (23.52)
2 train |  |  | 13.21 (10.15) | 15.77 (12.02) | 20.75 (17.32) | 18.44 (14.49) | 28.16 (23.22) | 34.41 (23.75) | 39.90 (29.16)
test |  |  | 12.27 (10.59) | 15.37 (13.53) | 20.27 (18.76) | 19.03 (16.61) | 28.24 (24.51) | 34.76 (24.91) | 40.46 (29.26)
3 train |  |  |  | 15.75 (13.50) | 12.88 (8.26) | 23.30 (17.50) | 19.21 (14.39) | 43.05 (29.57) | 23.97 (15.48)
test |  |  |  | 14.86 (13.22) | 11.22 (9.67) | 23.05 (18.58) | 18.90 (15.04) | 43.74 (30.26) | 24.07 (15.69)
4 train |  |  |  |  | 23.18 (17.02) | 18.52 (13.60) | 19.96 (13.64) | 38.80 (30.40) | 33.26 (23.93)
test |  |  |  |  | 22.81 (18.14) | 18.22 (14.59) | 19.39 (15.33) | 40.01 (30.97) | 34.66 (24.06)
5 train |  |  |  |  |  | 23.89 (18.77) | 23.76 (15.43) | 45.22 (30.63) | 30.60 (22.05)
test |  |  |  |  |  | 24.53 (19.03) | 22.78 (16.78) | 45.22 (30.79) | 31.86 (23.00)
6 train |  |  |  |  |  |  | 27.77 (16.80) | 46.02 (35.74) | 30.55 (18.78)
test |  |  |  |  |  |  | 27.97 (17.57) | 47.44 (36.49) | 31.66 (19.39)
7 train |  |  |  |  |  |  |  | 47.05 (31.64) | 35.33 (22.86)
test |  |  |  |  |  |  |  | 47.78 (33.38) | 35.27 (22.17)
8 train |  |  |  |  |  |  |  |  | 38.53 (34.28)
test |  |  |  |  |  |  |  |  | 38.29 (35.17)

Table 6. Means and standard deviations of the $\ell^{1}$ norms of the
successful adversarial attacks on each training and test set, reported in the
form ‘mean (standard deviation)’. The numbers in the row and column headers
indicate the classes used in each binary classification problem. The ‘train’
row shows the values computed over the training set, while the ‘test’ row
shows the values computed over the test set.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 train | 0.14 (0.11) | 0.09 (0.08) | 0.13 (0.09) | 0.11 (0.10) | 0.16 (0.12) | 0.14 (0.10) | 0.14 (0.11) | 0.10 (0.10) | 0.14 (0.12)
test | 0.14 (0.11) | 0.10 (0.09) | 0.13 (0.10) | 0.12 (0.10) | 0.17 (0.13) | 0.14 (0.10) | 0.15 (0.12) | 0.10 (0.10) | 0.14 (0.12)
1 train |  | 0.16 (0.12) | 0.13 (0.08) | 0.13 (0.10) | 0.15 (0.09) | 0.11 (0.07) | 0.18 (0.12) | 0.13 (0.11) | 0.10 (0.10)
test |  | 0.16 (0.13) | 0.13 (0.08) | 0.13 (0.11) | 0.16 (0.09) | 0.11 (0.07) | 0.18 (0.12) | 0.13 (0.11) | 0.09 (0.10)
2 train |  |  | 0.05 (0.04) | 0.06 (0.04) | 0.08 (0.07) | 0.07 (0.06) | 0.11 (0.10) | 0.13 (0.09) | 0.15 (0.12)
test |  |  | 0.04 (0.04) | 0.05 (0.05) | 0.08 (0.07) | 0.07 (0.06) | 0.11 (0.11) | 0.13 (0.10) | 0.15 (0.12)
3 train |  |  |  | 0.05 (0.05) | 0.06 (0.04) | 0.10 (0.07) | 0.08 (0.06) | 0.15 (0.11) | 0.09 (0.06)
test |  |  |  | 0.05 (0.05) | 0.05 (0.05) | 0.10 (0.08) | 0.07 (0.07) | 0.15 (0.11) | 0.09 (0.06)
4 train |  |  |  |  | 0.08 (0.06) | 0.06 (0.05) | 0.09 (0.07) | 0.15 (0.11) | 0.13 (0.10)
test |  |  |  |  | 0.07 (0.06) | 0.06 (0.06) | 0.09 (0.07) | 0.15 (0.11) | 0.13 (0.10)
5 train |  |  |  |  |  | 0.10 (0.08) | 0.10 (0.08) | 0.15 (0.11) | 0.12 (0.09)
test |  |  |  |  |  | 0.10 (0.08) | 0.10 (0.08) | 0.15 (0.11) | 0.12 (0.10)
6 train |  |  |  |  |  |  | 0.10 (0.06) | 0.17 (0.13) | 0.11 (0.07)
test |  |  |  |  |  |  | 0.10 (0.06) | 0.17 (0.14) | 0.12 (0.07)
7 train |  |  |  |  |  |  |  | 0.16 (0.11) | 0.13 (0.09)
test |  |  |  |  |  |  |  | 0.16 (0.12) | 0.13 (0.08)
8 train |  |  |  |  |  |  |  |  | 0.15 (0.14)
test |  |  |  |  |  |  |  |  | 0.15 (0.15)

Table 7. Means and standard deviations of the $\ell^{\infty}$ norms of the
smallest successful adversarial attack on each image in the training and test
set, reported in the form ‘mean (standard deviation)’. The numbers in the row
and column headers indicate the classes used in each binary classification
problem. The ‘train’ row shows the values computed over the training set,
while the ‘test’ row shows the values computed over the test set. Figure 7.
The distribution of the Euclidean norms of the successful adversarial attacks
found for each image using the algorithm in Section A.2, shown for a
representative sample of the binary classification problems. The plotted
distributions were fitted to the data using a standard Kernel Density
Estimation algorithm and therefore only provide an approximation of the true
empirical distribution. Figure 8. The distribution of the $\ell^{\infty}$
norms of the successful adversarial attacks found for each image using the
algorithm in Section A.2, shown for a representative sample of the binary
classification problems. The plotted distributions were fitted to the data
using a standard Kernel Density Estimation algorithm and therefore only
provide an approximation of the true empirical distribution. Figure 9. The
distribution of the $\ell^{1}$ norms of the successful adversarial attacks
found for each image using the algorithm in Section A.2, shown for a
representative sample of the binary classification problems. The plotted
distributions were fitted to the data using a standard Kernel Density
Estimation algorithm and therefore only provide an approximation of the true
empirical distribution.

###  B.3. Random perturbations

To explore whether the sensitivities discovered in Section B.2 could be
triggered by random perturbations to the input data, we used the approach
outlined in Section A.3. We report the random perturbation susceptibility of
each network (as defined in Section A.3) in Table 8 for $\delta=1$, Table 9
for $\delta=2$, Table 10 for $\delta=5$, and Table 11 for $\delta=10$.

The remarkable story shown by this data is that the networks are almost
universally insensitive to random perturbations to the images, even when those
perturbations become quite drastic. This puzzling feature is demonstrated in
Figures 10 and 11, where we show examples from the ‘aeroplane-vs-cat’ binary
classification problem (0-vs-3), of images of a cat and an aeroplane (original
image in panel (a)) which were correctly classified by the network, alongside
the same image after an adversarial attack which successfully changed the
network’s predicted class in panel (b). This adversarial attack makes only a
small change to the image (the largest change to any single pixel channel is
0.19 for the cat and 0.05 for the aeroplane). When the image is perturbed
using a large random perturbation, as shown in panel (c), however, the network
still produces the correct classification. For comparison, in panel (d) we
show a random perturbation which caused the network to misclassify the image.
Both of these random perturbations were obtained using $\delta=10$ as in
Section A.3 and therefore have similar norms. To the human eye, however, there
is no significant difference between the two randomly perturbed images, or
between the original image and the adversarially attacked image. Even in these
cases where a random perturbation was found which caused a misclassification,
it is to be noted that only a small fraction of the 2,000 sampled random
perturbations did so (0.0415% for the cat and 0.002% for the aeroplane).

The data from Tables 8–11 shows that as the scale of the random perturbations
increases (as controlled by $\delta$), so too does the probability of causing
a perturbed image to be misclassified. In itself, this observation is
unsurprising, but the data in Table 10 shows that, even when the random
perturbations are scaled to be 5 times larger than the known adversarial
attack (measured in the Euclidean norm, corresponding to $\delta=5$),
typically fewer than 5% of images were misclassified after applying any of the
random perturbations.

In Figures 12–14 we show the distributions of the smallest random perturbation
found to cause an image to be misclassified, as measured in the Euclidean,
$\ell^{\infty}$ and $\ell^{1}$ norms respectively, for $\delta=10$ on a
representative sample of the binary classification problems (the
‘$i$-vs-$(i+1)$’ problems, as studied in Section B.2, cf. Figures 7–9). Recall
that the random perturbations were sampled from a ball with Euclidean norm
less than or equal to $1$ (although high dimensional concentration phenomena
ensure that the all of the random perturbations have Euclidean norm very close
to 1), and were scaled by $\delta$ times the Euclidean norm of the smallest
successful adversarial attack when used to attack each image. This explains
the underlying similarity between these distributions and those in Figures
7–9, which show the size distributions of the adversarial attacks. However, it
is readily apparent here once again that significantly larger random
perturbations are required as compared to adversarial perturbations. This is
visible (and shown in more detail for the ‘cat-vs-aeroplane’ problem (0-vs-3)
in Figure 15 from the fact that the random perturbation distributions appear
to have much thicker tails than those for the adversarial perturbations; if
simply a fixed fraction of all random perturbations were successful in causing
an image to be misclassified then the distributions would shrink by a constant
factor along their length.

Together, this evidence indicates that the decision surface does not pass
close to the image in all directions, but rather only in one or a few specific
adversarial directions.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 | 0, 0.06 | 0, 0.06 | 0, 0.06 | 0, 0.11 | 0, 0.12 | 0.01, 0 | 0.01, 0.12 | 0.10, 0.12 | 0.01, 0
1 |  | 0, 0.06 | 0, 0 | 0.01, 0.11 | 0, 0 | 0.04, 0.06 | 0, 0 | 0, 0.06 | 0.01, 0
2 |  |  | 0, 0.26 | 0.01, 0.06 | 0, 0.12 | 0, 0 | 0, 0 | 0, 0.06 | 0, 0
3 |  |  |  | 0.04, 0.12 | 0, 0.18 | 0, 0 | 0, 0.06 | 0, 0 | 0, 0
4 |  |  |  |  | 0, 0.06 | 0, 0.05 | 0, 0 | 0, 0.06 | 0.02, 0.06
5 |  |  |  |  |  | 0, 0.06 | 0, 0.06 | 0, 0 | 0, 0
6 |  |  |  |  |  |  | 0, 0 | 0, 0 | 0.01, 0.06
7 |  |  |  |  |  |  |  | 0, 0 | 0, 0
8 |  |  |  |  |  |  |  |  | 0.05, 0

Table 8. Susceptibility of the networks to random perturbations, as described
in Section A.3 for $\delta=1$. This is reported in the form ‘train
susceptibility, test susceptibility’, where susceptibility is calculated as in
(4) as the percentage of adversarially attackable images from each set which
were misclassified after applying any of the 2,000 random perturbations. The
row and column headers indicate the classes used in each binary classification
problem. Here, we use 0 without any trailing decimal places to indicate a
value which was actually zero, and not simply rounded to zero when rounding to
two decimal places.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 | 0.17, 0.42 | 0.02, 0.06 | 0, 0.06 | 0.07, 0.17 | 0.04, 0.31 | 0.01, 0 | 0.04, 0.29 | 1.11, 1.33 | 0.89, 0.78
1 |  | 0.02, 0.06 | 0.01, 0 | 0.03, 0.27 | 0, 0 | 0.05, 0.06 | 0, 0 | 0.59, 0.81 | 0.06, 0.36
2 |  |  | 0.02, 0.26 | 0.02, 0.12 | 0.06, 0.24 | 0.07, 0.06 | 0.01, 0.12 | 0, 0.19 | 0, 0
3 |  |  |  | 0.11, 0.31 | 0.01, 0.24 | 0.01, 0 | 0, 0.06 | 0.01, 0 | 0, 0
4 |  |  |  |  | 0, 0.17 | 0.03, 0.05 | 0, 0.06 | 0.05, 0.06 | 0.03, 0.11
5 |  |  |  |  |  | 0.03, 0.06 | 0, 0.11 | 0.01, 0 | 0.03, 0.07
6 |  |  |  |  |  |  | 0, 0 | 0.03, 0 | 0.01, 0.06
7 |  |  |  |  |  |  |  | 0, 0 | 0.04, 0
8 |  |  |  |  |  |  |  |  | 0.97, 1.47

Table 9. Susceptibility of the networks to random perturbations, as described
in Section A.3 for $\delta=2$. This is reported in the form ‘train
susceptibility, test susceptibility’, where susceptibility is calculated as in
(4) as the percentage of adversarially attackable images from each set which
were misclassified after applying any of the 2,000 random perturbations. The
row and column headers indicate the classes used in each binary classification
problem. Here, we use 0 without any trailing decimal places to indicate a
value which was actually zero, and not simply rounded to zero when rounding to
two decimal places.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 | 9.67, 10.56 | 1.55, 2.38 | 3.87, 4.58 | 9.94, 10.30 | 4.06, 4.93 | 1.75, 1.85 | 7.52, 8.42 | 8.93, 9.43 | 14.85, 16.57
1 |  | 7.61, 7.33 | 0.58, 0.25 | 5.99, 6.20 | 1.04, 1.27 | 1.11, 1.14 | 3.67, 3.12 | 11.06, 11.57 | 0.53, 0.75
2 |  |  | 0.12, 0.85 | 0.27, 0.40 | 0.61, 1.31 | 2.02, 2.46 | 1.65, 1.56 | 0.32, 0.56 | 2.30, 2.14
3 |  |  |  | 0.53, 0.99 | 0.25, 1.03 | 0.63, 0.63 | 0.23, 0.33 | 2.42, 2.94 | 0.34, 0.40
4 |  |  |  |  | 0.11, 0.56 | 0.44, 0.59 | 0.18, 0.56 | 3.46, 3.39 | 3.83, 3.96
5 |  |  |  |  |  | 2.97, 4.91 | 0.11, 0.33 | 2.36, 2.66 | 9.51, 9.74
6 |  |  |  |  |  |  | 0, 0.10 | 2.86, 3.24 | 0.07, 0.23
7 |  |  |  |  |  |  |  | 2.65, 2.57 | 1.40, 1.48
8 |  |  |  |  |  |  |  |  | 10.37, 10.37

Table 10. Susceptibility of the networks to random perturbations, as described
in Section A.3 for $\delta=5$. This is reported in the form ‘train
susceptibility, test susceptibility’, where susceptibility is calculated as in
(4) as the percentage of adversarially attackable images from each set which
were misclassified after applying any of the 2,000 random perturbations. The
row and column headers indicate the classes used in each binary classification
problem. Here, we use 0 without any trailing decimal places to indicate a
value which was actually zero, and not simply rounded to zero when rounding to
two decimal places.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 | 41.49, 40.57 | 14.02, 16.71 | 29.34, 32.15 | 47.37, 49.55 | 27.49, 30.07 | 27.92, 28.11 | 50.40, 52.41 | 41.44, 42.16 | 50.82, 49.72
1 |  | 41.82, 42.67 | 29.38, 28.98 | 27.18, 28.96 | 41.01, 43.16 | 15.90, 17.79 | 30.90, 29.43 | 36.98, 36.92 | 29.42, 31.09
2 |  |  | 4.76, 6.78 | 16.74, 18.75 | 9.12, 10.48 | 34.10, 34.42 | 22.70, 23.11 | 19.20, 20.08 | 32.67, 31.80
3 |  |  |  | 5.54, 6.58 | 9.57, 11.04 | 19.86, 19.24 | 6.99, 8.49 | 28.58, 29.07 | 26.54, 28.01
4 |  |  |  |  | 5.59, 6.40 | 14.37, 14.77 | 3.87, 4.73 | 38.19, 39.58 | 31.07, 33.56
5 |  |  |  |  |  | 43.20, 42.81 | 6.99, 9.00 | 22.66, 23.23 | 56.10, 58.79
6 |  |  |  |  |  |  | 16.45, 16.70 | 26.87, 30.53 | 8.64, 8.92
7 |  |  |  |  |  |  |  | 42.90, 44.36 | 26.44, 26.14
8 |  |  |  |  |  |  |  |  | 45.04, 45.08

Table 11. Susceptibility of the networks to random perturbations, as described
in Section A.3 for $\delta=10$. This is reported in the form ‘train
susceptibility, test susceptibility’, where susceptibility is calculated as in
(4) as the percentage of adversarially attackable images from each set which
were misclassified after applying any of the 2,000 random perturbations. The
row and column headers indicate the classes used in each binary classification
problem.

(a) Original

(b) Misclassified adversarially attacked cat (attack
$\ell^{1}$ norm: 67.98,
Euclidean norm: 1.94,
$\ell^{\infty}$ norm: 0.19)

(c) Correctly classified randomly perturbed cat ($\delta=10$, perturbation
$\ell^{1}$ norm: 856.28,
Euclidean norm: 19.41,
$\ell^{\infty}$ norm: 1.83)

(d) Misclassified randomly perturbed cat ($\delta=10$, perturbation
$\ell^{1}$ norm: 860.64,
Euclidean norm: 19.41,
$\ell^{\infty}$ norm: 1.65)

Figure 10. An example of an adversarially attacked image of a cat, taken from
the ‘cat-vs-aeroplane’ binary classification problem (0-vs-3), alongside
examples of large random perturbations to the same image which did and did not
cause the network to misclassify the image. Of the 2,000 sampled random
perturbations, 83 (0.0415%) caused this image to be misclassified. Components
of the modified image which were outside the range $[0,1]$ have been clipped
into the range for plotting, although not for the classification.

(a) Original

(b) Misclassified adversarially attacked aeroplane (attack
$\ell^{1}$ norm: 13.53,
Euclidean norm: 0.39,
$\ell^{\infty}$ norm: 0.05)

(c) Correctly classified randomly perturbed aeroplane ($\delta=10$,
perturbation
$\ell^{1}$ norm: 172.99,
Euclidean norm: 3.92,
$\ell^{\infty}$ norm: 0.37)

(d) Misclassified randomly perturbed aeroplane ($\delta=10$, perturbation
$\ell^{1}$ norm: 174.23,
Euclidean norm: 3.92,
$\ell^{\infty}$ norm: 0.32)

Figure 11. An example of an adversarially attacked image of an aeroplane,
taken from the ‘cat-vs-aeroplane’ binary classification problem (0-vs-3),
alongside examples of large random perturbations to the same image which did
and did not cause the network to misclassify the image. Of the 2,000 sampled
random perturbations, 4 (0.002%) caused this image to be misclassified.
Components of the modified image which were outside the range $[0,1]$ have
been clipped into the range for plotting, although not for the classification.
Figure 12. The distribution over all images in
$\mathcal{X}^{\operatorname{rand},10}_{i,j}$ (from the training set, defined
in Section A.3) and $\mathcal{Y}^{\operatorname{rand},10}_{i,j}$ (from the
test set, defined in Section A.3) of the smallest Euclidean norm of a random
perturbation which caused the network to misclassify the image. Black dashed
lines indicate the size of the largest adversarial attack required on each
data set (see Figure 7 for a plot of the full distribution of adversarial
attacks). The plotted distributions were fitted to the data using a standard
Kernel Density Estimation algorithm and therefore only provides an
approximation of the true empirical distribution. Table 11 shows that the
distributions for problems ‘2-vs-3’, ‘3-vs-4’ and ‘4-vs-5’ were constructed
with fewer data points than the remaining distributions as these networks were
less susceptible to random perturbations. Figure 13. The distribution over all
images in $\mathcal{X}^{\operatorname{rand},10}_{i,j}$ (from the training set,
defined in Section A.3) and $\mathcal{Y}^{\operatorname{rand},10}_{i,j}$ (from
the test set, defined in Section A.3) of the smallest $\ell^{\infty}$ norm of
a random perturbation which caused the network to misclassify the image. Black
dashed lines indicate the size of the largest adversarial attack required on
each data set (see Figure 8 for a plot of the full distribution of adversarial
attacks). The plotted distributions were fitted to the data using a standard
Kernel Density Estimation algorithm and therefore only provide an
approximation of the true empirical distribution. Table 11 shows that the
distributions for problems ‘2-vs-3’, ‘3-vs-4’ and ‘4-vs-5’ were constructed
with fewer data points than the remaining distributions as these networks were
less susceptible to random perturbations. Figure 14. The distribution over all
images in $\mathcal{X}^{\operatorname{rand},10}_{i,j}$ (from the training set,
defined in Section A.3) and $\mathcal{Y}^{\operatorname{rand},10}_{i,j}$ (from
the test set, defined in Section A.3) of the smallest $\ell^{1}$ norm of a
random perturbation which caused the network to misclassify the image. Black
dashed lines indicate the size of the largest adversarial attack required on
each data set (see Figure 9 for a plot of the full distribution of adversarial
attacks). The plotted distributions were fitted to the data using a standard
Kernel Density Estimation algorithm and therefore only provide an
approximation of the true empirical distribution. Table 11 shows that the
distributions for problems ‘2-vs-3’, ‘3-vs-4’ and ‘4-vs-5’ were constructed
with fewer data points than the remaining distributions as these networks were
less susceptible to random perturbations. Figure 15. A direct comparison of
the size distributions over all attackable images in the training and test
sets of the smallest successful adversarial attack and smallest misclassifying
random perturbation for the ‘cat-vs-aeroplane’ problem (0-vs-3), as measured
in various norms. The plotted distributions were fitted to the data using a
standard Kernel Density Estimation algorithm and therefore only provide an
approximation of the true empirical distribution.

###  B.4. Training with random perturbations

For brevity, we only report the results of these experiments for the
representative subset of ‘class $i$-vs-class $i+1$’ binary classification
problems. These are given in Tables 12, 14 and 16 for random perturbations
sampled uniformly from the cube $[-a,a]^{n}$ with $a\in\\{0.1,0.5,1.0\\}$
respectively, and Tables 13, 15 and 17 for noise sampled uniformly from the
ball $\mathbb{B}^{n}_{b}$ with $b\in\\{3.2,16,32\\}$ respectively (see Section
A.4 for details of the experimental setup). These results are also plotted
against the size of the sampled perturbations in Figures 16 and 17 for
perturbations sampled from the cube and ball respectively. From these results,
it is clear that additive random noise has little impact on the adversarial
susceptibility of the networks, and large perturbations cause the networks’
accuracy to decrease.

It should be stressed that additive noise sampled from the cube $[-1,1]$ (the
largest cube we tested) represents a significant modification to an image
where each pixel value is in $[0,1]$. We also recall that the adversarial
susceptibility is only calculated as the fraction of correctly classified
images which are susceptible to adversarial attacks, meaning that the drop in
accuracy of the classifier is implicitly decreasing the pool of images which
were tested for adversarial attacks. Interestingly, the average norm of the
successful adversarial attacks does seem to increase with the size of the
random perturbations applied during training. However, this could once again
be due to the observed drop in accuracy: training and test points which were
near the decision boundary of the original classifier trained without
perturbations would be those which were susceptible to the smallest
adversarial attacks. These would also be the points which would be most likely
to be misclassified by the less accurate classifiers trained with randomly
perturbed data, so would not be included when the adversarial attacks were
computed. Consequently, while large additive random noise may eliminate some
of the smallest adversarial attacks, it does so at the expense of a
significant drop in accuracy.

|  | 0 vs 1 | 1 vs 2 | 2 vs 3 | 3 vs 4 | 4 vs 5 | 5 vs 6 | 6 vs 7 | 7 vs 8 | 8 vs 9
---|---|---|---|---|---|---|---|---|---|---
Accuracy | train | 99.85 | 99.39 | 96.93 | 98.85 | 98.71 | 98.29 | 99.87 | 99.57 | 99.33
| test | 96.40 | 96.60 | 82.45 | 85.90 | 87.45 | 92.45 | 96.35 | 98.05 | 94.75
Adv. susceptibility | train | 87.85 | 95.14 | 90.49 | 99.96 | 99.46 | 98.67 | 98.87 | 84.85 | 95.94
| test | 85.63 | 95.19 | 90.12 | 99.88 | 99.43 | 98.86 | 98.75 | 85.06 | 95.30
Adv. attack $\ell^{1}$ norm | train | 23.14 (35.17) | 19.11 (27.94) | 10.78 (17.35) | 11.94 (16.84) | 13.57 (18.69) | 19.38 (26.04) | 14.23 (19.03) | 20.55 (33.22) | 22.12 (32.41)
| test | 23.33 (36.73) | 19.75 (29.04) | 10.42 (17.82) | 11.92 (18.32) | 12.66 (18.25) | 20.58 (27.78) | 14.39 (19.51) | 20.68 (33.56) | 22.46 (33.46)
Adv. attack $\ell^{2}$ norm | train | 0.68 (1.04) | 0.57 (0.83) | 0.32 (0.52) | 0.34 (0.47) | 0.40 (0.56) | 0.59 (0.79) | 0.42 (0.55) | 0.60 (0.96) | 0.64 (0.94)
| test | 0.69 (1.08) | 0.59 (0.87) | 0.31 (0.54) | 0.34 (0.51) | 0.38 (0.54) | 0.63 (0.84) | 0.42 (0.57) | 0.60 (0.97) | 0.65 (0.97)
Adv. attack $\ell^{\infty}$ norm | train | 0.07 (0.12) | 0.06 (0.09) | 0.03 (0.06) | 0.04 (0.05) | 0.04 (0.06) | 0.08 (0.11) | 0.05 (0.06) | 0.07 (0.11) | 0.08 (0.11)
| test | 0.08 (0.12) | 0.06 (0.10) | 0.03 (0.06) | 0.04 (0.06) | 0.04 (0.06) | 0.08 (0.11) | 0.05 (0.06) | 0.07 (0.11) | 0.08 (0.12)

Table 12. Performance results when images are randomly perturbed during
training using additive random noise sampled from the cube $[-a,a]^{n}$ with
$a=0.1$. The abbreviation ‘Adv.’ should be read as ‘Adversarial’. The
quantities computed are defined in Section A. The norms of the adversarial
attacks are reported in the form ‘mean (standard deviation)’, calculated by
averaging over all of the correctly classified and adversarially susceptible
images in each of the training and test sets.

|  | 0 vs 1 | 1 vs 2 | 2 vs 3 | 3 vs 4 | 4 vs 5 | 5 vs 6 | 6 vs 7 | 7 vs 8 | 8 vs 9
---|---|---|---|---|---|---|---|---|---|---
Accuracy | train | 99.83 | 99.69 | 95.33 | 99.02 | 99.39 | 99.45 | 99.82 | 98.64 | 99.45
| test | 96.10 | 96.90 | 84.20 | 86.25 | 89.05 | 92.80 | 96.80 | 97.15 | 95.05
Adv. susceptibility | train | 90.03 | 91.64 | 92.53 | 99.95 | 99.59 | 99.03 | 98.04 | 94.83 | 96.92
| test | 88.29 | 91.12 | 92.58 | 100.00 | 99.38 | 98.81 | 97.99 | 94.96 | 96.79
Adv. attack $\ell^{1}$ norm | train | 25.16 (36.97) | 18.58 (27.80) | 9.94 (17.17) | 11.45 (16.26) | 11.95 (16.51) | 17.81 (24.96) | 14.97 (20.01) | 22.23 (33.69) | 22.58 (32.08)
| test | 25.23 (37.82) | 18.71 (28.24) | 9.69 (16.88) | 11.55 (18.15) | 11.25 (16.89) | 18.76 (25.94) | 15.12 (21.37) | 22.50 (34.12) | 23.19 (33.62)
Adv. attack $\ell^{2}$ norm | train | 0.74 (1.10) | 0.56 (0.83) | 0.30 (0.53) | 0.32 (0.46) | 0.35 (0.49) | 0.56 (0.78) | 0.44 (0.59) | 0.65 (0.99) | 0.65 (0.93)
| test | 0.74 (1.12) | 0.56 (0.84) | 0.30 (0.52) | 0.33 (0.51) | 0.33 (0.50) | 0.58 (0.80) | 0.44 (0.62) | 0.66 (1.00) | 0.67 (0.98)
Adv. attack $\ell^{\infty}$ norm | train | 0.08 (0.13) | 0.06 (0.10) | 0.04 (0.07) | 0.03 (0.05) | 0.04 (0.06) | 0.07 (0.11) | 0.05 (0.07) | 0.07 (0.12) | 0.08 (0.11)
| test | 0.08 (0.13) | 0.06 (0.10) | 0.04 (0.07) | 0.03 (0.06) | 0.04 (0.06) | 0.08 (0.11) | 0.05 (0.07) | 0.07 (0.12) | 0.08 (0.12)

Table 13. Performance results when images are randomly perturbed during
training using additive random noise sampled from the ball
$\mathbb{B}^{n}_{b}$ with $b=3.2$. The abbreviation ‘Adv.’ should be read as
‘Adversarial’. The quantities computed are defined in Section A. The norms of
the adversarial attacks are reported in the form ‘mean (standard deviation)’,
calculated by averaging over all of the correctly classified and adversarially
susceptible images in each of the training and test sets.

|  | 0 vs 1 | 1 vs 2 | 2 vs 3 | 3 vs 4 | 4 vs 5 | 5 vs 6 | 6 vs 7 | 7 vs 8 | 8 vs 9
---|---|---|---|---|---|---|---|---|---|---
Accuracy | train | 92.82 | 94.43 | 91.57 | 92.89 | 95.75 | 94.60 | 98.96 | 97.50 | 89.54
| test | 89.50 | 92.05 | 81.50 | 82.80 | 86.95 | 88.80 | 94.65 | 95.40 | 85.35
Adv. susceptibility | train | 76.02 | 98.56 | 98.21 | 99.26 | 98.55 | 94.27 | 99.20 | 95.57 | 83.88
| test | 74.36 | 98.32 | 97.98 | 99.03 | 98.45 | 93.24 | 99.26 | 95.07 | 83.54
Adv. attack $\ell^{1}$ norm | train | 35.56 (50.17) | 21.88 (33.12) | 24.70 (34.77) | 22.03 (33.51) | 28.38 (35.91) | 28.85 (37.80) | 22.88 (29.34) | 27.83 (39.89) | 45.61 (55.12)
| test | 35.17 (50.80) | 21.82 (32.95) | 25.02 (36.26) | 21.81 (33.94) | 27.13 (35.90) | 29.06 (38.87) | 23.70 (31.22) | 27.50 (39.63) | 45.39 (54.85)
Adv. attack $\ell^{2}$ norm | train | 1.01 (1.44) | 0.65 (0.98) | 0.70 (1.00) | 0.61 (0.91) | 0.82 (1.04) | 0.87 (1.13) | 0.67 (0.85) | 0.78 (1.11) | 1.27 (1.53)
| test | 1.01 (1.47) | 0.65 (0.98) | 0.71 (1.04) | 0.60 (0.93) | 0.78 (1.04) | 0.88 (1.17) | 0.69 (0.91) | 0.77 (1.10) | 1.27 (1.53)
Adv. attack $\ell^{\infty}$ norm | train | 0.10 (0.15) | 0.07 (0.11) | 0.07 (0.10) | 0.06 (0.09) | 0.08 (0.11) | 0.10 (0.13) | 0.07 (0.09) | 0.08 (0.12) | 0.13 (0.17)
| test | 0.11 (0.16) | 0.07 (0.11) | 0.07 (0.11) | 0.06 (0.09) | 0.08 (0.11) | 0.10 (0.13) | 0.07 (0.10) | 0.08 (0.12) | 0.13 (0.17)

Table 14. Performance results when images are randomly perturbed during
training using additive random noise sampled from the cube $[-a,a]^{n}$ with
$a=0.5$. The abbreviation ‘Adv.’ should be read as ‘Adversarial’. The
quantities computed are defined in Section A. The norms of the adversarial
attacks are reported in the form ‘mean (standard deviation)’, calculated by
averaging over all of the correctly classified and adversarially susceptible
images in each of the training and test sets.

|  | 0 vs 1 | 1 vs 2 | 2 vs 3 | 3 vs 4 | 4 vs 5 | 5 vs 6 | 6 vs 7 | 7 vs 8 | 8 vs 9
---|---|---|---|---|---|---|---|---|---|---
Accuracy | train | 95.08 | 96.21 | 88.05 | 93.85 | 96.42 | 90.75 | 98.97 | 97.06 | 89.75
| test | 91.10 | 94.40 | 78.30 | 82.30 | 85.45 | 85.65 | 94.95 | 95.50 | 85.45
Adv. susceptibility | train | 79.44 | 97.78 | 93.16 | 99.38 | 99.16 | 92.32 | 99.36 | 96.46 | 85.86
| test | 77.22 | 97.72 | 92.40 | 99.45 | 99.06 | 90.37 | 99.53 | 96.07 | 85.08
Adv. attack $\ell^{1}$ norm | train | 34.08 (47.83) | 25.09 (36.56) | 32.75 (41.78) | 20.49 (31.84) | 26.35 (34.00) | 33.95 (41.52) | 24.59 (31.05) | 30.17 (42.56) | 47.84 (56.68)
| test | 32.84 (46.83) | 24.62 (36.20) | 32.60 (42.07) | 20.69 (33.00) | 25.62 (34.86) | 33.66 (42.43) | 25.21 (32.42) | 29.99 (42.89) | 46.48 (55.40)
Adv. attack $\ell^{2}$ norm | train | 0.99 (1.40) | 0.74 (1.07) | 0.93 (1.19) | 0.56 (0.87) | 0.76 (0.98) | 1.02 (1.24) | 0.71 (0.89) | 0.83 (1.17) | 1.33 (1.57)
| test | 0.97 (1.39) | 0.73 (1.06) | 0.93 (1.20) | 0.57 (0.90) | 0.74 (1.00) | 1.01 (1.26) | 0.73 (0.93) | 0.83 (1.17) | 1.29 (1.54)
Adv. attack $\ell^{\infty}$ norm | train | 0.10 (0.15) | 0.08 (0.11) | 0.10 (0.13) | 0.06 (0.09) | 0.08 (0.10) | 0.12 (0.14) | 0.07 (0.09) | 0.09 (0.12) | 0.14 (0.17)
| test | 0.10 (0.15) | 0.07 (0.11) | 0.09 (0.13) | 0.06 (0.09) | 0.07 (0.10) | 0.11 (0.14) | 0.07 (0.10) | 0.08 (0.12) | 0.13 (0.16)

Table 15. Performance results when images are randomly perturbed during
training using additive random noise sampled from the ball
$\mathbb{B}^{n}_{b}$ with $b=16$. The abbreviation ‘Adv.’ should be read as
‘Adversarial’. The quantities computed are defined in Section A. The norms of
the adversarial attacks are reported in the form ‘mean (standard deviation)’,
calculated by averaging over all of the correctly classified and adversarially
susceptible images in each of the training and test sets.

|  | 0 vs 1 | 1 vs 2 | 2 vs 3 | 3 vs 4 | 4 vs 5 | 5 vs 6 | 6 vs 7 | 7 vs 8 | 8 vs 9
---|---|---|---|---|---|---|---|---|---|---
Accuracy | train | 85.65 | 89.84 | 82.44 | 85.20 | 85.20 | 90.75 | 93.56 | 94.50 | 76.09
| test | 84.00 | 88.40 | 76.40 | 80.40 | 81.30 | 87.75 | 91.15 | 92.45 | 74.60
Adv. susceptibility | train | 75.66 | 98.90 | 93.92 | 97.79 | 93.96 | 97.41 | 98.57 | 96.96 | 61.51
| test | 74.40 | 98.81 | 92.41 | 98.07 | 93.97 | 97.26 | 98.08 | 97.13 | 61.93
Adv. attack $\ell^{1}$ norm | train | 47.29 (60.24) | 22.74 (35.90) | 38.53 (49.56) | 25.62 (41.16) | 46.07 (52.80) | 26.32 (39.04) | 39.02 (45.31) | 31.71 (44.80) | 55.25 (68.60)
| test | 45.52 (58.87) | 22.06 (35.82) | 38.01 (49.77) | 25.61 (41.41) | 45.18 (52.78) | 27.85 (41.27) | 39.61 (46.00) | 31.00 (44.60) | 54.28 (67.73)
Adv. attack $\ell^{2}$ norm | train | 1.29 (1.64) | 0.66 (1.04) | 1.06 (1.36) | 0.67 (1.08) | 1.29 (1.48) | 0.77 (1.14) | 1.12 (1.30) | 0.86 (1.21) | 1.44 (1.78)
| test | 1.25 (1.61) | 0.64 (1.03) | 1.05 (1.36) | 0.67 (1.08) | 1.26 (1.47) | 0.82 (1.21) | 1.13 (1.31) | 0.84 (1.21) | 1.41 (1.76)
Adv. attack $\ell^{\infty}$ norm | train | 0.12 (0.15) | 0.07 (0.11) | 0.10 (0.13) | 0.06 (0.10) | 0.13 (0.15) | 0.08 (0.12) | 0.11 (0.13) | 0.08 (0.12) | 0.13 (0.16)
| test | 0.11 (0.15) | 0.06 (0.10) | 0.10 (0.13) | 0.06 (0.10) | 0.12 (0.15) | 0.08 (0.13) | 0.11 (0.13) | 0.08 (0.12) | 0.12 (0.16)

Table 16. Performance results when images are randomly perturbed during
training using additive random noise sampled from the cube $[-a,a]^{n}$ with
$a=1$. The abbreviation ‘Adv.’ should be read as ‘Adversarial’. The quantities
computed are defined in Section A. The norms of the adversarial attacks are
reported in the form ‘mean (standard deviation)’, calculated by averaging over
all of the correctly classified and adversarially susceptible images in each
of the training and test sets.

|  | 0 vs 1 | 1 vs 2 | 2 vs 3 | 3 vs 4 | 4 vs 5 | 5 vs 6 | 6 vs 7 | 7 vs 8 | 8 vs 9
---|---|---|---|---|---|---|---|---|---|---
Accuracy | train | 86.82 | 91.61 | 84.19 | 85.79 | 84.17 | 90.45 | 94.29 | 93.40 | 80.22
| test | 84.55 | 89.85 | 78.55 | 80.25 | 80.80 | 88.10 | 91.35 | 91.20 | 77.25
Adv. susceptibility | train | 72.14 | 98.50 | 94.35 | 98.18 | 92.23 | 97.63 | 98.26 | 98.73 | 68.44
| test | 71.08 | 98.16 | 93.19 | 98.32 | 92.51 | 97.73 | 98.14 | 98.85 | 68.41
Adv. attack $\ell^{1}$ norm | train | 43.25 (58.85) | 25.08 (38.16) | 34.84 (47.12) | 25.38 (40.59) | 48.40 (54.21) | 25.85 (39.18) | 38.47 (45.03) | 29.10 (42.32) | 53.87 (66.98)
| test | 42.76 (58.44) | 24.30 (37.83) | 34.82 (48.19) | 25.47 (40.99) | 46.92 (53.64) | 27.88 (42.30) | 39.74 (46.60) | 28.83 (42.06) | 54.82 (67.20)
Adv. attack $\ell^{2}$ norm | train | 1.18 (1.61) | 0.72 (1.09) | 0.95 (1.28) | 0.67 (1.06) | 1.36 (1.52) | 0.75 (1.12) | 1.10 (1.29) | 0.78 (1.13) | 1.41 (1.75)
| test | 1.18 (1.61) | 0.69 (1.07) | 0.95 (1.31) | 0.67 (1.07) | 1.32 (1.50) | 0.81 (1.22) | 1.13 (1.33) | 0.77 (1.13) | 1.43 (1.76)
Adv. attack $\ell^{\infty}$ norm | train | 0.11 (0.15) | 0.07 (0.11) | 0.09 (0.12) | 0.06 (0.09) | 0.13 (0.16) | 0.07 (0.11) | 0.10 (0.13) | 0.07 (0.11) | 0.13 (0.16)
| test | 0.11 (0.16) | 0.07 (0.11) | 0.09 (0.13) | 0.06 (0.09) | 0.13 (0.15) | 0.08 (0.12) | 0.11 (0.13) | 0.07 (0.11) | 0.13 (0.16)

Table 17. Performance results when images are randomly perturbed during
training using additive random noise sampled from the ball
$\mathbb{B}^{n}_{b}$ with $b=32$. The abbreviation ‘Adv.’ should be read as
‘Adversarial’. The quantities computed are defined in Section A. The norms of
the adversarial attacks are reported in the form ‘mean (standard deviation)’,
calculated by averaging over all of the correctly classified and adversarially
susceptible images in each of the training and test sets. Figure 16. Plots
showing how the performance of the network is affected by various magnitudes
of random perturbations added to the images during training. This figure shows
the results for random perturbations sampled from the cube $[-a,a]^{n}$ for
$a\in\\{0,0.1,0.5,1\\}$. This visualises the results in in Tables 12, 14 and
16 compared to the previous data computed with no random perturbations
(corresponding to $a=0$). The data is plotted as separate lines for the
training and test sets. ‘Susceptibility’ here refers to the adversarial
susceptibility reported in the tables, and ‘Attack mean $\ell_{p}$’ indicates
the mean across each data set of the $\ell^{p}$ norm of the smallest
adversarial perturbation affecting each image. The perturbation size plotted
on the $x$ axis is the size of $a$. Figure 17. Plots showing how the
performance of the network is affected by various magnitudes of random
perturbations added to the images during training. This figure shows the
results for random perturbations sampled from the ball $\mathbb{B}^{n}_{b}$
for $b\in\\{0,3.2,16,32\\}$. This visualises the results in in Tables 12, 14
and 16 compared to the previous data computed with no random perturbations
(corresponding to $b=0$). The data is plotted as separate lines for the
training and test sets. ‘Susceptibility’ here refers to the adversarial
susceptibility reported in the tables, and ‘Attack mean $\ell_{p}$’ indicates
the mean across each data set of the $\ell^{p}$ norm of the smallest
adversarial perturbation affecting each image. The perturbation size plotted
on the $x$ axis is the size of $a$.

##  Appendix C Proofs of main theorems

###  C.1. Proof of Theorem 2

Expanding the probability using the definition of the distribution
$\mathcal{D}_{\epsilon}$, and the definition of the classifier $f$, we have

$\displaystyle P((x,\ell)\sim\mathcal{D}_{\epsilon}\,:\,f(x)=\ell)$
$\displaystyle=\frac{1}{2}P(x\sim\mathcal{D}_{0}\,:\,f(x)=0)+\frac{1}{2}P(x\sim\mathcal{D}_{1}\,:\,f(x)=1)$

The factor of $\frac{1}{2}$ is due to the fact that samples with either label
are sampled with equal probability. Negating these two probabilities and
expressing them as integrals using the densities $p_{0}$ and $p_{1}$
associated with $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ respectively (the
existence of these densities is a requirement of the SmAC property), we have

$\displaystyle P((x,\ell)\sim\mathcal{D}_{\epsilon}\,:\,f(x)=\ell)$
$\displaystyle=1-\frac{1}{2}\int_{D_{0}}\mathbb{I}_{\\{x_{1}>0\\}}p_{0}(x)dx-\frac{1}{2}\int_{D_{1}}\mathbb{I}_{\\{x_{1}<0\\}}p_{1}(x)dx.$

The bound on the density $p$ provided by the SmAC property in Definition 1
(recalling that $r=1$ for both distributions) therefore implies that

$\displaystyle P((x,\ell)\sim\mathcal{D}_{\epsilon}\,:\,f(x)=\ell)$
$\displaystyle\geq
1-\frac{A^{n}}{2V^{n}}\Big{(}\int_{D_{0}}\mathbb{I}_{\\{x_{1}>0\\}}dx+\int_{D_{1}}\mathbb{I}_{\\{x_{1}<0\\}}dx\Big{)}.$

By symmetry, the two integrals have the same value, so we only compute the
first. Since $\epsilon>0$, this corresponds to the volume of a section of a
ball which is smaller than a hemisphere, we may write it as

$\displaystyle\int_{D_{0}}\mathbb{I}_{\\{x_{1}>0\\}}dx=V^{n}_{\operatorname{cap}}(1,1-\epsilon).$

Enveloping the spherical cap in a hemisphere shows the following lemma.

######  Lemma 9 (Spherical cap volume bound).

Let $n$ be a positive integer, and $r\geq h>0$. Then,

$\displaystyle
V^{n}_{\operatorname{cap}}(r,h)\leq\frac{1}{2}V^{n}r^{n}\Big{(}1-\Big{(}1-\frac{h}{r}\Big{)}^{2}\Big{)}^{\frac{n}{2}}.$

This implies that

$\displaystyle
V^{n}_{\operatorname{cap}}(1,1-\epsilon)\leq\frac{1}{2}V^{n}(1-\epsilon^{2})^{\frac{n}{2}},$

and the result therefore follows.

###  C.2. Proof of Theorem 3

Using the definition of the classification function $f$ and conditioning on
the class label, we may rewrite the probability in question as

$\displaystyle P\big{(}(x,\ell)\sim\mathcal{D}_{\epsilon}\,:\,\text{there
exists }s\in\mathbb{B}^{n}_{\delta}\text{ such that }f(x+s)\neq\ell\big{)}$
$\displaystyle=\frac{1}{2}P(x\sim\mathcal{U}(D_{0})\,:\,x_{1}>-\delta)+\frac{1}{2}P(x\sim\mathcal{U}(D_{1})\,:\,x_{1}<\delta).$

Symmetry implies that these two probabilities have the same value, so we only
need to compute the first one. Negating the probability and expanding it as an
integral using the density $p_{0}$ of $\mathcal{D}_{0}$, we find that

$\displaystyle
P(x\sim\mathcal{U}(D_{0})\,:\,x_{1}>-\delta)=1-\int_{D_{0}}\mathbb{I}_{\\{x_{1}<-\delta\\}}p_{0}(x)dx.$

The bound on the density provided by the SmAC property (Definition 1)
therefore implies that

$\displaystyle P(x\sim\mathcal{U}(D_{0})\,:\,x_{1}>-\delta)\geq
1-\frac{A^{n}}{V^{n}}\int_{D_{0}}\mathbb{I}_{\\{x_{1}<-\delta\\}}dx.$

Since this integral corresponds to the volume of a spherical cap with height
smaller than its radius (due to the fact that $1>\delta>\epsilon>0$), we may
apply Lemma 9 to show that

$\displaystyle\int_{D_{0}}\mathbb{I}_{\\{x_{1}<-\delta\\}}dx$
$\displaystyle=V^{n}_{\operatorname{cap}}(1,1-(\epsilon-\delta))$
$\displaystyle\leq\frac{1}{2}V^{n}(1-(\delta-\epsilon)^{2})^{\frac{n}{2}},$

and the result therefore follows.

###  C.3. Proof of Theorem 4

To prove Theorem 4, we begin by expanding the probability by conditioning on
the label value, finding

$\displaystyle
P((x,\ell)\sim\mathcal{D}_{\epsilon},s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,f(x+s)\neq\ell)$
$\displaystyle\qquad=\frac{1}{2}P(x\sim\mathcal{U}(D_{0}),s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,x_{1}+s_{1}>0)$
$\displaystyle\qquad\qquad+\frac{1}{2}P(x\sim\mathcal{U}(D_{1}),s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,x_{1}+s_{1}<0).$

The symmetry here implies that these two probabilities are equal, so we
proceed by only bounding the first. Expanding this as an integral using the
density $p_{0}$ of $\mathcal{D}_{0}$ and the fact that $s$ is sampled from a
uniform distribution, we observe that

$\displaystyle
P(x\sim\mathcal{U}(D_{0}),s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,x_{1}+s_{1}>0)$
$\displaystyle\qquad=\frac{1}{V^{n}\delta^{n}}\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}ds\,p_{0}(x)\,dx.$

The bound on the density provided by the SmAC property (Definition 1)
therefore implies that

$\displaystyle
P(x\sim\mathcal{U}(D_{0}),s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,x_{1}+s_{1}>0)$
$\displaystyle\qquad\leq\frac{A^{n}}{(V^{n})^{2}\delta^{n}}\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}dsdx.$

For each fixed value of $x$, the inner integral is just computing the volume
of a section of a ball with radius $\delta$. When $x_{1}>0$, this volume is at
least a hemisphere, while when $x_{1}<0$ this volume is less than a
hemisphere. On the other hand, for fixed $s$, the integral over $x$ is also
calculating the volume of a section of the unit ball. Since the volume of the
ball concentrates in high dimensions about its equator, a section which is
smaller than a hemisphere may be expected to have small volume, while a
section larger than a hemisphere may be expected to have large volume. This is
the intuition we apply here by splitting the integral into two parts: one for
$x_{1}<-t$ and one for $x_{1}\geq-t$ for some arbitrary $t\in[0,\epsilon]$. In
the first part, we will be able to obtain ‘smallness’ in our bound from the
fact that we are integrating $s$ over just a spherical cap, while in the
second case we are integrating $x$ over a spherical cap. We write this
splitting as

(5)
$\displaystyle\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}dsdx$
$\displaystyle\qquad=\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{x_{1}<-t\\}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}dsdx$
$\displaystyle\qquad\quad+\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{x_{1}>-t\\}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}dsdx.$

The first term of this splitting may be bounded above by extending the
indicator function over $s$ to all those points with $s_{1}>t$ (since
$-x_{1}>t$), which enables us to separate the integrals to find that

$\displaystyle\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{x_{1}<-t\\}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}dsdx$
$\displaystyle\leq\int_{D_{0}}\mathbb{I}_{\\{x_{1}<-t\\}}dx\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{s_{1}>t\\}}ds.$

These integrals may be expressed as volumes in the form

$\displaystyle\int_{D_{0}}\mathbb{I}_{\\{x_{1}<-t\\}}dx\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{s_{1}>t\\}}ds$
$\displaystyle=(V^{n}-V^{n}_{\operatorname{cap}}(1,1-(\epsilon-t)))V^{n}_{\operatorname{cap}}(\delta,\delta-t),$

and Lemma 9 and the fact that the volume of a spherical cap is non-negative
implies that

$\displaystyle\int_{D_{0}}\mathbb{I}_{\\{x_{1}<-t\\}}dx\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{s_{1}>t\\}}ds\leq\frac{1}{2}(V^{n})^{2}\delta^{n}\Big{(}1-\Big{(}\frac{t}{\delta}\Big{)}^{2}\Big{)}^{\frac{n}{2}}.$

Returning to the second integral in (5), we may similarly bound the indicator
function over $s$ from above by simply the constant $1$. This implies that

$\displaystyle\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{x_{1}>-t\\}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}dsdx\leq\int_{D_{0}}\mathbb{I}_{\\{x_{1}>-t\\}}dx\int_{\mathbb{B}^{n}_{\delta}}ds$
$\displaystyle=V^{n}_{\operatorname{cap}}(1,1-(\epsilon-t))V^{n}\delta^{n},$

and Lemma 9 consequently provides

$\displaystyle\int_{D_{0}}\int_{\mathbb{B}^{n}_{\delta}}\mathbb{I}_{\\{x_{1}>-t\\}}\mathbb{I}_{\\{s_{1}>-x_{1}\\}}dsdx$
$\displaystyle\qquad\qquad\leq\frac{1}{2}(V^{n})^{2}\delta^{n}(1-(\epsilon-t)^{2})^{\frac{n}{2}}.$

Combining these bounds and using the fact that $t\in[0,\epsilon]$ was
arbitrary, we find that

$\displaystyle
P((x,\ell)\sim\mathcal{D}_{\epsilon},s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,f(x+s)\neq\ell)$
$\displaystyle\leq\frac{1}{2}A^{n}\inf_{t\in[0,\epsilon]}\Big{[}\Big{(}1-\Big{(}\frac{t}{\delta}\Big{)}^{2}\Big{)}^{\frac{n}{2}}+(1-(\epsilon-t)^{2})^{\frac{n}{2}}\Big{]},$

and the theorem follows by noting that, for
$t=\frac{\epsilon\delta}{1+\delta}$, the two terms inside the infimum are
equal (this choice of $t$ is valid since $\frac{\delta}{1+\delta}\in[0,1]$ for
$\delta\geq 0$).

###  C.4. Proof of Theorem 5

Since the statement and setup are symmetric with respect to the class label
$\ell$, we focus only on the class $0$ and the statement for class $1$ follows
analogously. In this case, the statement that

$f(x+s)\neq\ell\text{ for all }s\in\mathbb{R}^{n}\text{ such that
}d_{\ell}(z,s)>\gamma,$

is implied by the condition that $z_{1}<x_{1}+\gamma$, and therefore

$\displaystyle P(x,z\sim\mathcal{U}(D_{0})\,:\,f(x+s)\neq 0\text{ for all
}s\in\mathbb{R}^{n}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\text{ such that
}d_{0}(z,s)>\gamma)$ $\displaystyle\qquad\qquad\qquad\geq
P(x,z\sim\mathcal{U}(D_{0})\,:\,z_{1}<x_{1}+\gamma).$

Negating this probability and expressing this probability as an integral using
the density $p_{0}$ of $\mathcal{D}_{0}$, we find that

$\displaystyle P(x,z\sim\mathcal{U}(D_{0}):z_{1}<x_{1}+\gamma)$
$\displaystyle\qquad\qquad=1-\int_{D_{0}}\int_{D_{0}}\mathbb{I}_{\\{z_{1}>x_{1}+\gamma\\}}p_{0}(z)\
dz\ p_{0}(x)\ dx,$

and therefore, using the bound on the density provided by Definition 1 with
$r=1$, we obtain the lower bound

$\displaystyle P(x,z\sim\mathcal{U}(D_{0}):z_{1}<x_{1}+\gamma)$
$\displaystyle\qquad\geq
1-A^{2n}+\Big{(}\frac{A^{n}}{V^{n}}\Big{)}^{2}\int_{D_{0}}\int_{D_{0}}\mathbb{I}_{\\{z_{1}<x_{1}+\gamma\\}}dzdx,$

Introducing $t\in[0,\gamma]$, we may split the integral over $x$ as

$\displaystyle\int_{D_{0}}\int_{D_{0}}$
$\displaystyle\mathbb{I}_{\\{z_{1}<x_{1}+\gamma\\}}dzdx$
$\displaystyle=\int_{D_{0}}\mathbb{I}_{\\{x_{1}<-\epsilon-t\\}}\int_{D_{0}}\mathbb{I}_{\\{z_{1}<x_{1}+\gamma\\}}dzdx$
$\displaystyle\qquad+\int_{D_{0}}\mathbb{I}_{\\{x_{1}>-\epsilon-t\\}}\int_{D_{0}}\mathbb{I}_{\\{z_{1}<x_{1}+\gamma\\}}dzdx.$

The first term on the right hand side of this is trivially greater than or
equal to zero. For the second term, we observe that the condition
$x_{1}>-\epsilon-t$ implies that the set of $z\in D_{0}$ such that
$z_{1}<x_{1}+\gamma$ is greater than a hemisphere. We may express the integral
over $z$ in the form

$\displaystyle\int_{D_{0}}\mathbb{I}_{\\{z_{1}<x_{1}+\gamma\\}}dz$
$\displaystyle=V^{n}-V^{n}_{\operatorname{cap}}(1,1-(x_{1}+\gamma+\epsilon))$
$\displaystyle\geq
V^{n}\Big{(}1-\frac{1}{2}(1-(\gamma-t)^{2})^{\frac{n}{2}}\Big{)},$

where the lower bound is due to Lemma 9 and the bound on $x_{1}$. We therefore
find that

$\displaystyle\int_{D_{0}}\mathbb{I}_{\\{x_{1}>-\epsilon-t\\}}\int_{D_{0}}\mathbb{I}_{\\{z_{1}<x_{1}+\gamma\\}}dzdx$
$\displaystyle\geq
V^{n}\int_{D_{0}}\mathbb{I}_{\\{x_{1}>-\epsilon-t\\}}dx\Big{(}1-\frac{1}{2}(1-(\gamma-t)^{2})^{\frac{n}{2}}\Big{)},$

and, since the integral over $x$ is now just the volume of a ball missing a
spherical cap, arguing as above shows that

$\displaystyle\int_{D_{0}}\mathbb{I}_{\\{x_{1}>-\epsilon-t\\}}dx$
$\displaystyle=V^{n}-V^{n}_{\operatorname{cap}}(1,1-t)$ $\displaystyle\geq
V^{n}\Big{(}1-\frac{1}{2}(1-t^{2})^{\frac{n}{2}}\Big{)},$

since $t\in[0,\gamma]$. Consequently, because $t$ was arbitrary, we conclude
that

$\displaystyle P(x,z\sim\mathcal{U}(D_{0}):x_{1}>z_{1}-\gamma)$
$\displaystyle\qquad\geq
1-A^{2n}\Big{[}1-\inf_{t\in[0,\gamma]}\Big{(}1-\frac{1}{2}(1-(\gamma-t)^{2})^{\frac{n}{2}}\Big{)}\cdot$
$\displaystyle\hskip
120.00018pt\cdot\Big{(}1-\frac{1}{2}(1-t^{2})^{\frac{n}{2}}\Big{)}\Big{]},$

and the theorem follows by observing that the two terms in the infimum are
balanced for $t=\frac{\gamma}{2}$.

###  C.5. Proof of Theorem 6

When $\ell=0$, we have $|\tilde{f}(x)-\ell|=\sigma(g(x))$, since
$\sigma(t)\in(0,1)$ for $t\in\mathbb{R}$. In this case, the attack may
therefore be computed as

$\displaystyle\textbf{e}_{1}\sigma^{\prime}(g(x))L^{\prime}(\sigma(g(x))),$

since $g^{\prime}(x)=\textbf{e}_{1}$. Since
$\sigma^{\prime}(t),L^{\prime}(t)>0$ by assumption for all $t\in\mathbb{R}$,
this is a positive multiple of $\mathbf{e}_{1}$ as required. Analogously, when
$\ell=1$ we have $|\tilde{f}(x)-\ell|=1-\sigma(g(x))$, and we therefore obtain
a negative mutiple of $\mathbf{e}_{1}$ and the result follows.

##  Appendix D The two half-balls model

Let $n>0$ be an integer indicating the dimension of the space from which data
are sampled, let $\epsilon\geq 0$, and suppose that data are sampled from two
classes with binary labels $\\{0,1\\}$. Data of class $0$ are sampled
uniformly from the half-ball
$D_{0}=\\{x\in\mathbb{R}^{n}\,:\,x+\epsilon\,\mathbf{e}_{1}\in
H^{-}\mathbb{B}^{n}\\}$, where
$\mathbf{e}_{1}=(1,0,\dots,0)^{\top}\in\mathbb{R}$, while data from class $1$
are sampled uniformly from the half-ball
$D_{1}=\\{x\in\mathbb{R}^{n}\,:\,x-\epsilon\,\mathbf{e}_{1}\in
H^{+}\mathbb{B}^{n}\\}$. Here, we use the notation
$H^{-}\mathbb{B}^{n}=\\{x\in\mathbb{B}^{n}\,:\,x\cdot\mathbf{e}_{1}<0\\}$ and
$H^{+}\mathbb{B}^{n}=\\{x\in\mathbb{B}^{n}\,:\,x\cdot\mathbf{e}_{1}>0\\}$. The
two half-balls $D_{0}$, $D_{1}$ from which data points are sampled are
separated by a margin of $2\epsilon$, and any pair of data points $x,y$
sampled with opposite classes therefore satisfy $\|x-y\|\geq 2\epsilon$. We
denote the combined distribution by
$\mathcal{D}_{\epsilon}=\mathcal{U}(D_{0}\cup D_{1})$.

A classification function which produces the correct labels for this data can
be defined by

$f(x)=\begin{cases}0&\text{ if }x_{1}<0,\\\ 1&\text{ otherwise}.\end{cases}$

Data points sampled from both classes are separated from the decision surface
of this classifier by distance at least $\epsilon$. On the other hand, for any
$\delta>\epsilon$, there are clearly points, sampled from near the boundary of
each class such that there exist destabilising perturbations
$s\in\mathbb{R}^{n}$ with $\|s\|\leq\delta$ and $f(x+s)\neq f(x)$. Moreover,
in high dimensions, data points sampled from such a distribution concentrate
close to this decision surface, meaning that the probability of sampling a
point which is susceptible to an adversarial attack is high, as encapsulated
in the following result.

######  Theorem 10 (Susceptible data points are typical).

Let $\delta>\epsilon>0$. Then,

$\displaystyle P\big{(}x$
$\displaystyle\sim\mathcal{D}_{\epsilon}\,:\,\text{there exists
}s\in\mathbb{R}^{n}$ $\displaystyle\text{ with }\|s\|\leq\delta\text{ such
that }f(x+s)\neq f(x)\big{)}$ $\displaystyle\geq
1-(1-(\delta-\epsilon)^{2})^{n/2}.$

Although this susceptibility may be viewed as typical in high dimensions,
however, the probability of detecting it by sampling random perturbations of
data points is paradoxically very unlikely when $\epsilon>0$, as shown by the
following result.

######  Theorem 11 (Destabilising perturbations are rare).

Let $\delta>\epsilon>0$. Then,

$\displaystyle
P\big{(}x\sim\mathcal{D}_{\epsilon},s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,f(x+s)\neq
f(x)\big{)}$
$\displaystyle\qquad\qquad\qquad\leq\frac{1}{4}\Big{(}1-\Big{(}\frac{\epsilon}{\delta}\Big{)}^{2}\Big{)}^{n/2}.$

###  D.1. Proof of Theorem 10

Using the definition of the classification function $f$, we may rewrite the
probability in question as

$\displaystyle P\big{(}x$
$\displaystyle\sim\mathcal{D}_{\epsilon}\,:\,\text{there exists
}s\in\mathbb{R}^{n}\text{ with }\|s\|\leq\delta$ $\displaystyle\text{ such
that }f(x+s)\neq
f(x)\big{)}=P(x\sim\mathcal{D}_{\epsilon}\,:\,|x_{1}|<\delta).$

Expanding the probability as an integral, and using the fact that
$\mathcal{D}_{\epsilon}$ is a uniform distribution over two disjoint half-
balls and therefore has density $(V^{n})^{-1}$, we may further express this as

$\displaystyle P(x\sim\mathcal{D}_{\epsilon}\,:\,|x_{1}|<\delta)$
$\displaystyle=\frac{1}{V^{n}}\Big{(}\int_{D_{0}}\mathbb{I}_{\\{x\,:\,-\delta<x_{1}<-\epsilon\\}}dx$
$\displaystyle\qquad+\int_{D_{1}}\mathbb{I}_{\\{x\,:\,\epsilon<x_{1}<\delta\\}}dx\Big{)},$

and the remaining problem is to compute the two remaining integrals, the
values of which are equal by symmetry. We may express the set $\\{x\in
D_{1}\,:\,\epsilon<x_{1}<\delta\\}$, which geometrically represents the slab
of the half-ball $D_{1}$ within $\delta-\epsilon$ distance of its planar face,
as the complement of a spherical cap, implying

$\displaystyle\int_{D_{1}}\mathbb{I}_{\\{x\,:\,\epsilon<x_{1}<\delta\\}}dx=\frac{1}{2}V^{n}-V^{n}_{\operatorname{cap}}(1,1-(\delta-\epsilon)),$

and therefore

$\displaystyle
P(x\sim\mathcal{D}_{\epsilon}\,:\,|x_{1}|<\delta)=1-\frac{2V^{n}_{\operatorname{cap}}(1,1-(\delta-\epsilon))}{V^{n}}.$

We may further estimate this from below, to show the exponential behaviour of
this quantity with respect to $n$, by enveloping the spherical cap within a
small half-ball. The Pythagorean theorem implies that

$\displaystyle\\{x\in D_{1}\,:\,\epsilon<x_{1}<\delta\\}\subset G$

where

$\displaystyle G=\\{x\in\mathbb{R}^{n}\,:\,x_{1}>\epsilon\text{ and
}\|x-\epsilon\,\mathbf{e}_{1}\|^{2}\leq 1-(\delta-\epsilon)^{2}\\},$

and therefore

$\displaystyle\frac{2V^{n}_{\operatorname{cap}}(1,1-(\delta-\epsilon))}{V^{n}}\leq(1-(\delta-\epsilon)^{2})^{n/2},$

which proves the theorem.

###  D.2. Proof of Theorem 11

Since $D_{0}$ and $D_{1}$ are disjoint half-balls of a unit ball, it follows
that the density associated with $\mathcal{D}_{\epsilon}$ is simply
$(V^{n})^{-1}$, while the density associated with
$\mathcal{U}(\mathbb{B}^{n}_{\delta})$ is $(\delta^{n}V^{n})^{-1}$. Writing
the probability as an integral with this density, we therefore find that

$\displaystyle
P\big{(}x\sim\mathcal{D}_{\epsilon},s\sim\mathcal{U}(\mathbb{B}^{n}_{\delta})\,:\,f(x+s)\neq
f(x)\big{)}$
$\displaystyle\qquad=\frac{1}{\delta^{n}(V^{n})^{2}}\Big{(}\int_{D_{0}}\int_{\mathcal{B}^{n}_{\delta}}\mathbb{I}_{\\{x,s\,:\,s_{1}>-x_{1}\\}}dsdx$
$\displaystyle\qquad\qquad\qquad\qquad+\int_{D_{1}}\int_{\mathcal{B}^{n}_{\delta}}\mathbb{I}_{\\{x,s\,:\,s_{1}<-x_{1}\\}}dsdx\Big{)}.$

Since the values of these two integrals are equal by symmetry, we proceed by
only estimating the first. For $x\in D_{0}$, we have $x_{1}<-\epsilon$, and
therefore

$\displaystyle\int_{D_{0}}\int_{\mathcal{B}^{n}_{\delta}}\mathbb{I}_{\\{x,s\,:\,s_{1}>-x_{1}\\}}dsdx$
$\displaystyle\leq\int_{D_{0}}dx\int_{\mathcal{B}^{n}_{\delta}}\mathbb{I}_{\\{s\,:\,s_{1}>\epsilon\\}}ds$
$\displaystyle=\frac{1}{2}V^{n}\int_{\mathcal{B}^{n}_{\delta}}\mathbb{I}_{\\{s\,:\,s_{1}>\epsilon\\}}ds.$

The remaining integral over $s$ now takes the form of the volume of a
spherical cap, which we may bound by enveloping the cap in a small half-ball.
Arguing as in the proof of Theorem 10, it follows that

$\displaystyle\int_{\mathcal{B}^{n}_{\delta}}\mathbb{I}_{\\{s\,:\,s_{1}>\epsilon\\}}ds$
$\displaystyle=V^{n}_{\operatorname{cap}}(\delta,(\delta^{2}-\epsilon^{2})^{1/2})$
$\displaystyle\leq\frac{1}{2}\delta^{n}V^{n}\Big{(}1-\Big{(}\frac{\epsilon}{\delta}\Big{)}^{2}\Big{)}^{n/2}.$

The result therefore follows by combining the components above.

Figure 18. Comparing the upper bound from Theorem 11 against empirically
computed probabilities for data sampled from uniform distributions in two
half-balls with offset $\epsilon$, and perturbations sampled uniformly from a
ball with radius delta. We see that, even for comparatively large
perturbations (e.g. $\delta=0.5$, $\epsilon=0.01$), the probability of
randomly sampling a perturbation which changes the classification of a random
data point is very small.

##  Appendix E Generalising the theoretical model

We now show that the simple case presented in Section 3 extends to the more
general cases demonstrated in Figure 4, in which the classification surface is
not assumed to be flat, and the data are sampled from more general
distributions. To demonstrate that these abstract results are true
generalisations of the results show in Section 3, we derive corollaries to
each result for a general SmAC distribution with a flat decision surface.
These corollaries are therefore directly comparable with the results in
Section 3 for specific indicated values of the parameters.

Let $\nu,w\in\mathbb{R}^{n}$ with $\|\nu\|=1$, and define the plane

$\displaystyle\pi=\\{x\in\mathbb{R}^{n}\,:\,(x-w)\cdot\nu=0\\}\subset\mathbb{R}^{n},$

which passes through $w$ and is normal to the vector $\nu$. Denote by
$\Pi:\mathbb{R}^{n}\to\pi$ the orthogonal projection operator onto $\pi$ in
the Euclidean inner product, given by

$\displaystyle\Pi x=x-((x-w)\cdot\nu)\nu.$

Let $\phi:\pi\to\mathbb{R}$ be continuous, and define the surface

$\displaystyle S=\\{x\in\mathbb{R}^{n}\,:\,x-\phi(\Pi
x)\nu\in\pi\\}\subset\mathbb{R}^{n}.$

A projector $\Gamma:\mathbb{R}^{n}\to S$ onto the surface $S$ (along the
vector $\nu$) can be defined by

$\displaystyle\Gamma x=\Pi x+\phi(\Pi x)\nu.$

######  Remark 12 (Generalisation to other decision surfaces).

This can be generalised to incorporate other ‘wiggly’ decision surfaces. For
instance, if $S$ cannot be expressed as a modification of a hyperplane in its
normal direction, one could instead consider the surfaces defined by the upper
and lower graphs of $S$ with respect to $\pi$, i.e. if $S$ is given by a
multi-valued function, one could instead just take the maximum or minimum
values, and where necessary work with a Lipschitz extension of these surfaces.
Our results below will extend to this case, albeit with some additional
looseness reflecting the ‘uncertainty’ this imposes on the location of the
decision surface of the classifier. Alternatively, the constructions above may
be applied piecewise locally, splitting the surface $S$ up into regions where
the model adopted here can be applied directly. We do not strive for such
generality here, though, in order to present the main ideas in a simple
framework.

We also introduce the signed directed distance functions
$d_{\pi}:\mathbb{R}^{n}\to\mathbb{R}$ measuring the signed distance from a
point $x$ to the plane $\pi$ along the normal vector $\nu$, given by

$\displaystyle d_{\pi}(x)=(x-\Pi x)\cdot\nu=(x-w)\cdot\nu,$

and $d_{S}:\mathbb{R}^{n}\to\mathbb{R}$ measuring the signed distance from a
point $x$ to the surface $S$ along the vector $\nu$, given by

$\displaystyle d_{S}(x)$ $\displaystyle=(x-\Gamma(x))\cdot\nu=(x-\Pi
x)\cdot\nu-\phi(\Pi x)$ $\displaystyle=d_{\pi}(x)-\phi(\Pi x).$

Finally, we can define the distance from a point $x$ to the surface $S$ by

$\displaystyle\sigma(x)=\inf_{\hat{y}\in S}\|x-\hat{y}\|,$

noting the trivial inequality

(6) $\displaystyle\sigma(x)\leq|d_{S}(x)|,$

for any $x\in\mathbb{R}^{n}$, since $d_{S}$ only measures distance to $S$ in
the direction of $\nu$ while $\sigma$ measures the shortest distance to $S$
over all directions.

With these constructions, we can define a binary classifier with decision
surface $S$ as the function $f:\mathbb{R}^{n}\to\\{0,1\\}$ given by

$\displaystyle f(x)=\begin{cases}0&\text{ if }d_{S}(x)\leq 0,\\\ 1&\text{
otherwise}.\end{cases}$

To show how our previous results extend into this more general case, suppose
that data points of class $0$ are sampled from a distribution $\mathcal{D}$ on
$\mathbb{R}^{n}$, and that data points of class $1$ are sampled from the
distribution $\mathcal{D}^{\prime}$ on $\mathbb{R}^{n}$. In the interests of
simplicity, we only study the behaviour of the classifier on the class $0$, as
the result for the class $1$ is, in some sense, symmetric. We study this more
general model in parallel with the results of Section 3.

We first observe that the accuracy of the classifier may be controlled in an
analogous way to the simple case in Section 3. The supremum in this result
(and the suprema and infima in subsequent results) is simply present to ensure
an optimal balancing for the two terms; a valid (though possibly sub-optimal)
result may be obtained by selecting any value of $\alpha\geq 0$. The first
term appearing on the right hand side controls how far the surface $S$ may be
expected to deviate from the plane $\pi$ (and is therefore simply 1 in the
case when $\phi\equiv 0$ and so $S=\pi$; in this case the optimal balancing of
the terms will be obtained when $\alpha=0$). The second term, on the other
hand, estimates the probability that a point is correctly classified by the
plane placed parallel to $\pi$, but offset by distance $\alpha$ to account for
the variability of $\phi$. If the distribution $\mathcal{D}$ is just the
uniform distribution in a ball with centre at distance $\epsilon<0$ from the
plane $\pi$, therefore, this recovers the result of Theorem 2 for a single
class.

######  Theorem 13 (Accuracy of the classifier $f$).

Suppose that a point $x$ is sampled with class $0$. Then, the probability that
the classifier $f$ correctly classifies $x$ is at least

$\displaystyle P(x\sim\mathcal{D}\,:\,f(x)=0)$
$\displaystyle\qquad\geq\sup_{\alpha\geq
0}\big{[}P(x\sim\mathcal{D}\,:\,|\phi(\Pi x)|\leq\alpha)$
$\displaystyle\qquad\qquad\qquad-P(x\sim\mathcal{D}\,:\,d_{\pi}(x)>-\alpha)\big{]}.$

We demonstrate this result in the setting of a linear classifier with a
distribution $\mathcal{E}$ which satisfies the SmAC condition of Definition 1
with radius $r>0$ and centre $c$ such that $d_{\pi}(c)=-\eta$ for some
$\eta\in[0,r)$. Then, Theorem 13 takes the following form, from which we
obtain Theorem 2 when $r=1$ and $\eta=\epsilon$.

######  Corollary 14 (Accuracy for SmAC distributions).

Suppose that points with label 0 are sampled from the distribution
$\mathcal{E}$, and suppose that $\phi\equiv 0$. Then, the probability that the
classifier $f$ accurately classifies points of class $0$ is at least

$\displaystyle P(x\sim\mathcal{E}\,:\,f(x)=0)\geq
1-\frac{1}{2}A^{n}\Big{(}1-\Big{(}\frac{\eta}{r}\Big{)}^{2}\Big{)}^{\frac{n}{2}}.$

We may also prove the susceptibility result of Theorem 3 in our abstract
setting. The probability of sampling a data point which is susceptible to an
adversarial attack of size $\delta$ may be bounded from below as in the
following result. The form of this result is similar to that of Theorem 13,
although we note the crucial difference in the second term.

######  Theorem 15 (Susceptibility to adversarial perturbations).

Suppose that points with label 0 are sampled from the distribution
$\mathcal{D}$. Then, for any $\delta>0$, the probability that a point sampled
at random from the class $0$ is susceptible to an adversarial attack with
Euclidean norm $\delta$ is at least

$\displaystyle P(x\sim\mathcal{D}\,:\,\text{ there exists
}s\in\mathbb{B}^{n}_{\delta}\text{ with }f(x+s)\neq 0)$
$\displaystyle\qquad\geq\sup_{\alpha\geq
0}\big{[}P(x\sim\mathcal{D}\,:\,|\phi(\Pi x)|\leq\alpha)$
$\displaystyle\qquad\qquad\qquad-P(x\sim\mathcal{D}\,:\,d_{\pi}(x)\leq\alpha-\delta)\big{]}.$

When applied to the SmAC distribution $\mathcal{E}$, this result takes the
following form, from which we obtain Theorem 3.

######  Corollary 16 (Susceptibility for SmAC distributions).

Suppose that points with label 0 are sampled from the distribution
$\mathcal{E}$, and suppose that $\phi\equiv 0$. Then, for any
$\delta\in[\eta,r]$, the probability that a point sampled at random from the
class $0$ is susceptible to an adversarial attack with Euclidean norm $\delta$
is at least

$\displaystyle P(x\sim\mathcal{E}\,:\,\text{ there exists
}s\in\mathbb{B}^{n}_{\delta}\text{ with }f(x+s)\neq 0)$
$\displaystyle\qquad\geq
1-\frac{1}{2}A^{n}\Big{(}1-\Big{(}\frac{\delta-\eta}{r}\Big{)}^{2}\Big{)}^{\frac{n}{2}}.$

We also show a generalised version of Theorem 4, which bounds the probability
of sampling a random perturbation which is adversarial for $f$. For this
result, we assume that the surface $S$ has some regularity, in the sense that
the function $\phi$ is Lipschitz with constant $L>0$; i.e. for any
$\hat{x},\hat{y}\in\pi$ we have $|\phi(\hat{x})-\phi(\hat{y})|\leq
L\|\hat{x}-\hat{y}\|$. Geometrically, this defines a cone of points around any
$x\in\mathbb{R}^{n}$ in which $f$ is guaranteed to be constant. This property
is particularly useful to us here because it allows us to prove the following
lower bound on $\sigma$ by $d_{S}$ in Section E.3.

######  Lemma 17 (Lipschitz regularity gives control of $\sigma$).

Suppose that $\phi$ is Lipschitz with parameter $L$. Then, for any
$x\in\mathbb{R}^{n}$,

(7) $\displaystyle\sigma(x)\geq|d_{S}(x)|\sin\theta,$

where $\theta=\arctan(L^{-1})$.

This allows us to prove the following result, indicating that destabilising
random perturbations may be expected to be rare.

######  Theorem 18 (Probability of sampling misclassifying random
perturbations).

Suppose that points with label 0 are sampled from the distribution
$\mathcal{D}$. Then, for any $\delta>0$, the probability that a point sampled
at random from the class $0$ will be misclassified after the application of a
perturbation randomly sampled uniformly from $\mathbb{B}^{n}_{\delta}$ is
bounded by

$\displaystyle P(x\sim\mathcal{D},s\sim\mathbb{B}^{n}_{\delta}\,:\,f(x+s)\neq
0)$ $\displaystyle\,\leq\inf_{\begin{subarray}{c}\alpha,\gamma\geq 0\\\ t\in
T(L)\end{subarray}}\Big{[}P(x\sim\mathcal{D}\,:\,|\phi(\Pi x)|\geq\alpha)$
$\displaystyle\qquad\qquad\quad+P\Big{(}x\sim\mathcal{D}\,:\,d_{\pi}(x)\geq-\alpha-\frac{t}{\sin\theta}\Big{)}$
$\displaystyle\qquad\qquad\quad+\Delta(L)\frac{1}{2}\Big{(}1-\Big{(}\frac{t}{\delta}-L\Big{)}^{2}\Big{)}^{\frac{n}{2}}\cdot$
$\displaystyle\qquad\qquad\qquad\quad\cdot\big{(}P(x\sim\mathcal{D}\,:\,d_{\pi}(x)\leq\gamma-t)$
$\displaystyle\qquad\qquad\qquad\qquad\quad+P(x\sim\mathcal{D}\,:\,|\phi(\Pi
x)|>\gamma)\big{)}\Big{]},$

where $\Delta(L)=1$ for $L\leq 1$ and 0 for $L>1$, and the set
$T(L)=[\min\\{L,1\\}\delta,\delta]$.

We also show this result for the SmAC distribution $\mathcal{E}$, from which
Theorem 4 follows when $r=1$ and $\eta=\epsilon$. In this case, we have $L=0$
and so $\theta=\frac{\pi}{2}$ and therefore $\sin\theta=1$, and the result of
Theorem 18 produces the following corollary.

######  Corollary 19 (Destabilising random perturbations are rare for SmAC
distributions).

Suppose that points with label 0 are sampled from the distribution
$\mathcal{E}$, and suppose that $\phi\equiv 0$. Then, for any
$\delta\in[\eta,r]$, the probability that a point sampled a random from the
class $0$ is misclassified after the application of a perturbation sampled
uniformly from the ball $\mathbb{B}^{n}_{\delta}$ is bounded by

$\displaystyle P(x\sim\mathcal{E},s\sim\mathbb{B}^{n}_{\delta}\,:\,f(x+s)\neq
0)\leq
A^{n}\Big{(}1-\Big{(}\frac{\eta}{r+\delta}\Big{)}^{2}\Big{)}^{\frac{n}{2}}.$

###  E.1. Proof of Theorem 13 and Corollary 14

####  E.1.1. Proof of Theorem 13

We can measure the accuracy of the classifier for class $0$ as

$\displaystyle\operatorname{acc}_{0}(f)=P(x\sim\mathcal{D}\,:\,f(x)=0)=P(x\sim\mathcal{D}\,:\,d_{S}(x)\leq
0).$

For any $t\in\mathbb{R}$, the condition that $d_{S}(t)\leq t$ can be rewritten
as

$\displaystyle d_{\pi}(x)-\phi(\Pi x)\leq t,$

which is implied by the condition that

$\displaystyle d_{\pi}(x)+|\phi(\Pi x)|\leq t.$

Introducing the event $A(\alpha)$, for any $\alpha\geq 0$, which occurs when a
point $x\sim\mathcal{D}$ is such that $|\phi(\Pi x)|\leq\alpha$, and the event
$B(\beta)$, for any $\beta\in\mathbb{R}$, which occurs when $x$ is such that
$d_{\pi}(x)\leq\beta$, we find that

(8) $\displaystyle A(\alpha)\wedge B(t-\alpha)\quad\Rightarrow\quad
d_{\pi}(x)+|\phi(\Pi x)|\leq t.$

Putting these pieces together, we find that

$\displaystyle\operatorname{acc}_{0}(f)\geq
P(x\sim\mathcal{D}\,:\,d_{\pi}(x)+|\phi(\Pi x)|\leq 0)$ $\displaystyle\geq
P(x\sim\mathcal{D}\,:\,A(\alpha)\wedge B(-\alpha)).$

Negating this event and applying the union bound, we therefore find that

$\displaystyle\operatorname{acc}_{0}(f)$ $\displaystyle\geq
P(x\sim\mathcal{D}\,:\,|\phi(\Pi x)|\leq\alpha)$
$\displaystyle\qquad-P(x\sim\mathcal{D}\,:\,d_{\pi}(x)>-\alpha).$

Since $\alpha\geq 0$ was arbitrary, it therefore follows that

$\displaystyle\operatorname{acc}_{0}(f)\geq\sup_{\alpha\geq 0}\big{[}$
$\displaystyle P(x\sim\mathcal{D}\,:\,|\phi(\Pi x)|\leq\alpha)$
$\displaystyle\,-P(x\sim\mathcal{D}\,:\,d_{\pi}(x)>-\alpha)\big{]}.$

####  E.1.2. Proof of Corollary 14

Since $\phi\equiv 0$ in this case, it follows that

$\displaystyle P(x\sim\mathcal{E}\,:\,|\phi(x)|\leq\alpha)=1,$

for all $\alpha\geq 0$. We may therefore take $\alpha=0$ in the second term of
Theorem 13, and we proceed by bounding

$\displaystyle P(x\sim\mathcal{E}\,:\,d_{\pi}(x)\geq 0)$

from above.

Recalling the bound on the density $p$ of $\mathcal{E}$ in Definition 1, we
have

$\displaystyle P(x\sim\mathcal{E}\,:\,d_{\pi}(x)\geq
0)\leq\frac{A^{n}}{V^{n}r^{n}}\int_{\mathbb{B}^{n}_{r}(c)}\mathbb{I}_{\\{x\,:\,d_{\pi}(x)\geq
0\\}}dx,$

and the definition of $d_{\pi}$ implies that this is

$\displaystyle\int_{\mathbb{B}^{n}_{r}(c)}\mathbb{I}_{\\{x\,:\,d_{\pi}(x)\geq
0\\}}dx=\int_{\mathbb{B}^{n}_{r}(c)}\mathbb{I}_{\\{x\,:\,(x-w)\cdot\nu\geq
0\\}}dx,$

which is zero for $(w-c)\cdot\nu>r$ and simply a spherical cap otherwise. Note
that the assumption that $d_{\pi}(c)=-\eta$ for some $\eta>0$ implies that
this spherical cap is less than half the ball $\mathbb{B}^{n}_{r}(c)$.
Therefore, Lemma 9 implies that

$\displaystyle P(x\sim\mathcal{E}\,:\,f(x)=0)\geq
1-\frac{1}{2}A^{n}\Big{(}1-\Big{(}\frac{\eta}{r}\Big{)}^{2}\Big{)}^{\frac{n}{2}}$

###  E.2. Proof of Theorem 15 and Corollary 16

####  E.2.1. Proof of Theorem 15