# Adversarial Ink: Componentwise Backward Error Attacks on Deep Learning

Lucas Beerens School of Mathematics and The Maxwell Institute for Mathematical
Sciences, University of Edinburgh, EH9 3F, UK Desmond J. Higham School of
Mathematics, University of Edinburgh, James Clerk Maxwell Building, Edinburgh,
UK

###### Abstract

Deep neural networks are capable of state-of-the-art performance in many
classification tasks. However, they are known to be vulnerable to adversarial
attacks—small perturbations to the input that lead to a change in
classification. We address this issue from the perspective of backward error
and condition number, concepts that have proved useful in numerical analysis.
To do this, we build on the work of Beuzeville et al. (2021). In particular,
we develop a new class of attack algorithms that use componentwise relative
perturbations. Such attacks are highly relevant in the case of handwritten
documents or printed texts where, for example, the classification of
signatures, postcodes, dates or numerical quantities may be altered by
changing only the ink consistency and not the background. This makes the
perturbed images look natural to the naked eye. Such “adversarial ink” attacks
therefore reveal a weakness that can have a serious impact on safety and
security. We illustrate the new attacks on real data and contrast them with
existing algorithms. We also study the use of a componentwise condition number
to quantify vulnerability.

##  1 Motivation

Over the past decade it has become clear that state of the art deep learning
image classification tools are susceptible to adversarial attacks—deliberately
constructed perturbations that are intended to go unnoticed by humans but
cause a change in the predicted class [11, 25]. This type of vulnerability is
of concern in high stakes application areas, including medical imaging,
transport, defence and finance [18]. Consequently there has been a great deal
of interest in the design of practical attack and defence strategies [2, 10,
17, 19, 21] and, more recently, in theoretical questions concerning the
existence and computability of adversarial perturbations [3, 7, 23, 27, 26].

From the perspective of applied and computational mathematics, the fundamental
question to be addressed here concerns well-posedness, or _conditioning_. In
particular, _backward error_ theory from numerical analysis is highly
pertinent. In [4], the authors used the concept of backward error to construct
a new form of adversarial attack algorithm. In this work, we build on this
idea by focusing on a special class of data perturbation. We develop attack
strategies based on _componentwise relative_ perturbations; for example, each
pixel may be perturbed by a small percentage of its original value. In
particular, this approach allows us to preserve the background of a document
and perturb only the ink levels in the text. We also test the corresponding
condition number as an indicator of vulnerability to attack.

To illustrate the main idea, Figure 1 part (a) shows a handwritten digit from
the MNIST data set [16], and parts (b) and (c) show adversarial attacks on a
trained network described in section 4. The original image (a) is correctly
classified as a 7 by the network. The perturbed images in (b) are (c) are both
classified as an 8. For (b) we attacked with the DeepFool algorithm [19],
which controls the Euclidean norm of the perturbation. Although the image
still has the appearance of a 7, we see that the background, where pixels had
a value of zero, is noticeably altered. For (c) we computed a componentwise
perturbation with the new Algorithm 4 from section 4 and we see that the
background is unchanged. The componentwise perturbation in part (c) is
compatible with a blotchy pen, imperfect paper, or inconsistent handwriting
pressure. Indeed, variations in line continuity, line quality and pen control
have been widely observed, and are listed among the twenty-one discriminating
elements of handwriting [12, 15]. Hence we argue that this type of
“adversarial ink” attack produces a more natural result than the perturbation
in part (b).

(a) Image from MNIST dataset [16], which is correctly classified as a 7 by a
neural network.

(b) Perturbed image using DeepFool [19]. The background is now smeared. This
image is classified as an 8.

(c) Perturbed image using Algorithm 4 from section 4. The background is
unchanged. This image is classified as an 8.

Figure 1: Image from MNIST and two adversarial attacks.

The manuscript is organized as follows. In section 2 we set up some notation
and introduce the concept of backward error. Section 3 describes the
adversarial attack algorithms in [4], and Section 4 extends these to the
componentwise setting. Computational results on the MNIST data set are
presented in Section 5; we show illustrative images, summarize the
perturbation sizes, consider untargeted attacks, compare against state-of-the-
art algorithms, summarize the most likely class changes, look at the use of a
condition number to indicate vulnerability to attack, test on different neural
networks, and report on black box attacks. Conclusions are given in Section 6.

##  2 Image Classification and Backward Error

We begin by considering a general image classifier, in the form of a map
$F:[0,1]^{n}\rightarrow\mathbb{R}^{c}$. Hence, we regard an image as a single
vector in $\mathbb{R}^{n}$. The $n$ components may correspond to individual
pixel intensities in the greyscale case, or red, green, and blue channel pixel
intensities in the colour case. Intensities are assumed to lie in $[0,1]$.
Each image is assigned to one of $c$ classes, according to the largest
component of $F(x)$. In practice, the output vector $y=F(x)\in\mathbb{R}^{c}$
may be passed through a softmax function, so that

$\frac{e^{y_{i}}}{\sum_{j=1}^{c}e^{y_{j}}}$

is viewed as the probability that $x$ belongs to class $i$. Since $x$ is
assigned to the most likely class, we do not need to include this final layer
when considering the classification results.

In numerical analysis, the concept of backward error deals with the following
question: given an approximate solution, what is the size of the smallest
perturbation to the input which makes this solution exact? In more detail,
suppose an approximation algorithm produces a function ${\widehat{H}}$,
instead of the desired function $H$. For an input $x$, when the algorithm
returns ${\widehat{H}}(x)=y+\Delta y$ instead of $y=H(x)$, we may ask for the
smallest $\Delta x$ such that $H(x+\Delta x)=y+\Delta y$. In many settings,
the size of $\Delta x$ (the backward error) is more relevant and more amenable
to analysis than the size of $\Delta y$ (the forward error) [5, 14]. For an
adversarial attack on a classifier, we may interpret $\Delta y$ as a _desired_
change in the output. Then a question of the same structure arises—what is the
smallest perturbation to the input that achieves the desired output? In this
setting, we require $\Delta x$ such that $F(x+\Delta x)=y+\Delta y$.

This approach was exploited in [4], leading to what we describe as Algorithms
1 and 2 in subsections 3.2 and 3.3.

##  3 Normwise Backward Error Attacks: Algorithms 1 and 2

###  3.1 Set-up

In the next two subsections, we describe the data perturbation approach from
[4]; leading to Algorithms 1 and 2. We cover this existing work in sufficient
detail that (a) there are well-defined algorithms that can be implemented in
practice, and (b) the new versions, Algorithms 3 and 4 in section 4, can be
introduced naturally and compared computationally.

We formulate all algorithms in terms of linearly-constrained linear least-
squares problems, for which high quality software is available. Letting
$\|\cdot\|_{2}$ denote the Euclidean norm, these problems have the form

$\min_{z}\|C_{1}z-k_{1}\|_{2},\quad\text{such
that}\quad\begin{cases}C_{2}z\leq k_{2},\\\ C_{3}z=k_{3},\end{cases}$ (1)

where the matrices $C_{1},C_{2},C_{3}$ and vectors $z,k_{1},k_{2},k_{3}$ have
appropriate dimensions and where vector equalities and inequalities are to be
interpreted in a componentwise sense. (More traditionally, the objective
function in (1) may be written
${\scriptstyle{{\frac{1}{2}}}}\|C_{1}z-k_{1}\|^{2}_{2}$, but, of course, the
factor ${\scriptstyle{{\frac{1}{2}}}}$ and the square may be ignored.) We also
assume for now that the Jacobian of the classification map is available; in
subsection 5.6 we test the use of a finite difference approximation to the
Jacobian.

###  3.2 Linearized Algorithm

We begin by measuring perturbations in the Euclidean norm. Given an image $x$
with $F(x)=y$ and a desired new output $\widehat{y}$, a suitable perturbation
may be expressed as

$\operatorname*{arg\,min}_{\Delta x}\\{\|\Delta x\|_{2}\,:\,F(x+\Delta
x)=\widehat{y}\\}.$ (2)

In general, this problem cannot be solved analytically. On the grounds that we
are looking for a small perturbation, it is reasonable to linearize, using
$F(x+\Delta x)-F(x)\approx\mathcal{A}\Delta x$, where
$\mathcal{A}\in\mathbb{R}^{c\times n}$ is the Jacobian of $F$ at $x$, and $F$
is assumed to be differentiable in a neighbourhood of $x$. The problem (2)
then reduces to

$\operatorname*{arg\,min}_{\Delta x}\left\\{\|\Delta
x\|_{2}\,:\,\mathcal{A}\Delta x=\widehat{y}-y\right\\}.$ (3)

For any fixed $\widehat{y}$ this is a minimum Euclidean norm linear system.
Typically $c\ll n$, so the system is underdetermined. Generically, a solution
for this fixed $\widehat{y}$ can be found by introducing the Moore-Penrose
inverse [28], $\mathcal{A}^{\dagger}$, to give

$\operatorname*{arg\,min}_{\Delta x}\left\\{\|\Delta x\|_{2}:\mathcal{A}\Delta
x=\widehat{y}-y\right\\}=\mathcal{A}^{\dagger}(\widehat{y}-y).$ (4)

Given the solution (4), we can use $\widehat{y}$ as an optimization variable.
In the targeted case, where we wish the perturbed image to be classified with
label $c_{0}$, we introduce the misclassification set

$\mathcal{S}:=\\{\widehat{y}\in\mathbb{R}^{c}\,:\,\widehat{y}_{c_{0}}=\max_{1\leq
i\leq c}\widehat{y}_{i}\\}.$ (5)

To compute an adversarial attack we then solve

$\operatorname*{arg\,min}_{\hat{y}\in\mathcal{S}}\|\mathcal{A}^{\dagger}(\hat{y}-y)\|_{2},$
(6)

and set $\Delta x=\mathcal{A}^{\dagger}(\widehat{y}-y)$.

We now show that the problem (5)–(6) has the form (1). The variable to be
optimized is $\widehat{y}$, so we will use $z=\hat{y}$ in (1). We may take
$C_{1}=C_{1}^{[1]}:=\mathcal{A}^{\dagger}$ and
$k_{1}=k_{1}^{[1]}:=\mathcal{A}^{\dagger}y$. The misclassification condition
is equivalent to

$\hat{y}-\begin{pmatrix}\widehat{y}_{c_{0}}\\\ \vdots\\\
\widehat{y}_{c_{0}}\end{pmatrix}\leq 0.$

In order to write this in matrix form, we define the matrix
$G\in\mathbb{R}^{c\times c}$ with

$G_{ij}=\begin{cases}1&\text{ if }j=c_{0},\\\ 0&\text{otherwise}.\end{cases}$
(7)

The misclassification condition may then be written

$(I-G)\hat{y}\leq 0.$

Hence we use $C_{2}=C_{2}^{[1]}:=I-G$ and $k_{2}=k_{2}^{[1]}=0$. There are no
equality conditions, so we set $C_{3}=C_{3}^{[1]}:=0$ and
$k_{3}=k_{3}^{[1]}:=0$.

This leads to Algorithm 1, as summarized in the displayed pseudocode listing.

Algorithm 1 Basic normwise attack, returning a perturbed image

1:procedure Attack($F,x,c_{0}$)

2: $out\leftarrow F(x)$

3: $jac\leftarrow$ Jacobian$(F,x)$

4: $pi\leftarrow$ PseudoInverse$(jac)$

5: $con\leftarrow$ Constraints$(c_{0})$

6: $obj\leftarrow$ Objective$(pi,out)$

7: $z\leftarrow$ OptimizationVariable

8: $prob\leftarrow$ Minimize$(z,obj,con)$

9: Solve$(prob)$

10: $\Delta y\leftarrow z.value-out$

11: $\Delta x\leftarrow pi\cdot\Delta y$

12: return Scale$(F,x,\Delta x,c_{0})$

13:end procedure

The final step of Algorithm 1 requires further explanation. We note that the
constrained linear least-squares problem is not guaranteed to produce a
perturbed image with values in $[0,1]$. For this reason, we prune the entries
using

$\operatorname{Prune}_{i}(x)=\begin{cases}0&\text{ if }x_{i}<0\\\ x_{i}&\text{
if }x_{i}\in[0,1]\\\ 1&\text{ if }x_{i}>1.\end{cases}$

We also note that the resulting $\Delta x$ might be unsuccessful; that is,
$F(x+\Delta x)$ might not correspond to class $c_{0}$. Hence, we regard
$\Delta x$ from (6) as a _direction_ in which to perturb, and take the
smallest increment that results in class $c_{0}$. So the Scale function in
Algorithm 1 is defined as

$\operatorname{Scale}(F,x,\Delta
x,c_{0}):=x+\min\\{a\in\mathbb{R}:\operatorname*{arg\,max}_{i}F(\operatorname{Prune}(x+a\,\Delta
x))_{i}=c_{0}\\}\,\Delta x.$ (8)

This minimisation is carried out by computing
$\operatorname*{arg\,max}_{i}F(\operatorname{Prune}(x+a\,\Delta x))_{i}$ over
a finely spaced range of $a$ values in $(0,\|x\|_{2}/\|\Delta x\|_{2}]$. If
there is no suitable value of $a$ in this range then we terminate and regard
the attack as unsuccessful. We use this range because for larger $a$ the norm
of the perturbation before pruning exceeds the norm of the image, at which
point it is reasonable to assume that the perturbation is too large to be of
interest.

###  3.3 Iterative Algorithm

An alternative approach was also proposed in [4]. This may be motivated by two
ideas.

  * •

Do not exploit the analytical solution of the linearized problem (4), and
proceed directly with numerical optimization. This allows us to build in
constraints that keep all pixel values in the range $[0,1]$.

  * •

Given that we have linearized the problem, take small steps and proceed
iteratively.

The algorithm uses a hyperparameter $\alpha$ indicating the step size for each
iteration. Again we will target some class $c_{0}$. We start with the
perturbation $\Delta x=0$ and update it with a small multiple of some new
$\delta x$ in every step. At every step we also have $x_{\text{new}}=x+\Delta
x$ and $y_{\text{new}}=F(x_{\text{new}})$. In each of these steps we solve

$\operatorname*{arg\,min}_{\delta x}\|\Delta x+\delta x\|_{2},$ (9)

under the misclassification condition $\widehat{y}\in\mathcal{S}$, the
condition that $\mathcal{A}\delta x=\widehat{y}-y_{\text{new}}$, and the
constraint that pixel values lie in the unit interval. Since we now have
constraints on both $\widehat{y}$ and $\delta x$, we treat them both as
optimization variables. Then we update $\Delta x$ and $x_{\text{new}}$ by
adding $\alpha\delta x$ to both. Finally $\mathcal{A}$ is recomputed before
moving on to the next iteration.

To see that we still have constrained linear least-squares problems of the
form (1), note that we must repeatedly solve (9) under the conditions that
$\mathcal{A}\delta x=\widehat{y}-y_{\text{new}}$ and
$\widehat{y}\in\mathcal{S}$. Since both $\delta x$ and $\widehat{y}$ need to
be optimized we use $z=\begin{bmatrix}\delta x\\\ \widehat{y}\end{bmatrix}$ in
(1). Thus we use $C_{1}=C_{1}^{[2]}:=\begin{bmatrix}I,0\end{bmatrix}$ and
$k_{1}=k_{1}^{[2]}:=-\Delta x$. For the inequality constraints we need to
consider the misclassification constraint and the pixel value bound
constraint. Keeping in mind that $z$ also includes $\delta x$ we obtain
$\begin{bmatrix}0,I-G\end{bmatrix}z\leq 0$, for $G$ in (7). Pixel values must
also lie in the unit interval. This constraint may be written as

$\begin{bmatrix}I&0\\\
-I&0\end{bmatrix}z\leq\begin{bmatrix}\mathbf{1}-x_{\text{new}}\\\
x_{\text{new}}\end{bmatrix},$

where $\mathbf{1}$ denotes a vector of $1$s. Combining the two inequality
conditions gives

$C_{2}=C_{2}^{[2]}:=\begin{bmatrix}0&I-G\\\ I&0\\\
-I&0\end{bmatrix}\quad\text{and}\quad k_{2}=k_{2}^{[2]}:=\begin{bmatrix}0\\\
\mathbf{1}-x_{\text{new}}\\\ x_{\text{new}}\end{bmatrix}.$

The required equality condition is $\mathcal{A}\delta
x=\widehat{y}-y_{\text{new}}$; that is,
$\begin{bmatrix}-\mathcal{A},I\end{bmatrix}z=y_{\text{new}}$. Therefore we
take $C_{3}=C_{3}^{[2]}:=\begin{bmatrix}-\mathcal{A},I\end{bmatrix}$ and
$k_{3}=k_{3}^{[2]}:=y_{\text{new}}$.

This leads to Algorithm 2, summarized in displayed the pseudocode. Here we
have a prescribed number of iterations, _num_. In Section 4 we examine the
performance in terms of the iteration number.

Algorithm 2 Iterative normwise attack, returning a perturbed image

1:procedure Attack($F,x,c_{0},\alpha,num$)

2: $out\leftarrow F(x)$

3: $\Delta x\leftarrow 0$

4: $newX\leftarrow x$

5: for $i=1$ to $num$ do

6: $jac\leftarrow$ Jacobian$(F,newX)$

7: $pi\leftarrow$ PseudoInverse$(jac)$

8: $con\leftarrow$ Constraints$(jac,newX,out,c_{0})$

9: $obj\leftarrow$ Objective$(\Delta x)$

10: $z\leftarrow$ OptimizationVariable

11: $prob\leftarrow$ Minimize$(z,obj,con)$

12: Solve$(prob)$

13: $\delta x\leftarrow z.value.delta$

14: $\Delta x\leftarrow\Delta x+\alpha\cdot\delta x$

15: $newX\leftarrow newX+\alpha\cdot\delta x$

16: $out\leftarrow F(newX)$

17: end for

18: return Scale$(F,x,\Delta x,c_{0})$

19:end procedure

##  4 Componentwise Backward Error Attacks: Algorithms 3 and 4

The minimum Euclidean norm perturbation in (2) was motivated by a normwise
concept of backward error. Based on the alternative componentwise backward
error viewpoint in [13, 14], instead of (2) we may consider the problem

$\operatorname*{arg\,min}_{\Delta x}\\{\epsilon:F(x+\Delta x)=\widehat{y},\ \
|\Delta x|\leq\epsilon f\\},$

for a given tolerance vector $f\geq 0\in\mathbb{R}^{n}$. Here, the absolute
value function $|\cdot|$ is applied to each component, so $|\Delta x|_{i}$ is
$|\Delta x_{i}|$. Unless otherwise indicated, we will use $f=|x|$. In this
case, changes are measured in a _relative componentwise_ sense, and, in
particular, a zero element of $x$ cannot be perturbed.

Using this type of constraint in an adversarial attack, after linearizing, a
componentwise version of (3) is given by

$\operatorname*{arg\,min}_{\Delta x}\\{\epsilon:\mathcal{A}\Delta
x=\widehat{y}-y,\quad|\Delta x|\leq\epsilon f\\}.$ (10)

We now write the constraint in a form that fits into the linear optimization
framework (1), using an idea from [13, Section 2]. We set $\Delta x=Dv$, where
$D=\operatorname{diag}(f)$ and $v$ is a vector. The relevant optimization
problem is

$\min\\{\epsilon:\mathcal{A}Dv=\widehat{y}-y,\quad|Dv|\leq\epsilon f,\quad
Dv=\Delta x\\}.$

Since $D=\operatorname{diag}(f)$, we know that the smallest such $\epsilon$
will always be equal to $\|v\|_{\infty}$. Hence the minimization problem can
be written

$\min\\{\|v\|_{\infty}:\mathcal{A}Dv=\widehat{y}-y\\}.$ (11)

In the absence of an analytical solution to (11), we will proceed with an
iterative algorithm, along the lines of Algorithm 2, using $v$ and $\delta v$
in place of $\Delta x$ and $\delta x$, respectively. Again we use
$x_{\text{new}}$ and $y_{\text{new}}$ to keep track of the perturbed image and
output during the iterative process. In each iteration of the algorithm we
compute

$\operatorname*{arg\,min}_{\delta v}\|v+\delta v\|_{\infty},$

under the conditions that $\widehat{y}-y_{\text{new}}=\mathcal{A}D\delta v$
and $\widehat{y}\in\mathcal{S}$. After each step we update $v\leftarrow
v+\alpha\delta v$, where $\alpha$ is a hyperparameter. Then we assign $\Delta
x=Dv$ and $x_{\text{new}}=x+\Delta x$. Finally we recompute $\mathcal{A}$.

To fit into the least-squares framework (1), we introduce a new variable
$u\in\mathbb{R}$. To minimize the infinity norm of $v+\delta v$, we may solve

$\min\\{|u|:|v+\delta v|\leq u\mathbf{1}\\}.$

Here, the constraint may be written as two separate linear inequality
constraints. We must also include $\delta v$ and $\hat{y}$ in the optimization
variable. We will write

$z=\begin{bmatrix}u\\\ \hat{y}\\\ \delta v\end{bmatrix}.$

We can now specify the required matrices in (1). Since the target function is
$|u|$, we use $C_{1}=C_{1}^{[3]}:=\begin{bmatrix}1,0,\ldots,0\end{bmatrix}$
and $k_{1}=k_{1}^{[3]}:=0$. There are five inequality constraints. Two are
$\delta v-u\mathbf{1}\leq-v$ and $-\delta v-u\mathbf{1}\leq v$ coming from the
infinity norm optimization. A third inequality constraint is
$\widehat{y}\in\mathcal{S}$, which we may write as $(I-G)\hat{y}\leq 0$.
Finally, to keep the pixel values of the perturbed image within the unit
interval we require

$\begin{bmatrix}0&\alpha D\\\ 0&-\alpha
D\end{bmatrix}z\leq\begin{bmatrix}\mathbf{1}-x_{\text{new}}\\\
x_{\text{new}}\end{bmatrix}.$

Combining these five constraints we obtain

$C_{2}=C_{2}^{[3]}:=\begin{bmatrix}-\mathbf{1}&0&I\\\ -\mathbf{1}&0&-I\\\
0&I-G&0\\\ 0&0&\alpha D\\\ 0&0&-\alpha D\end{bmatrix},$

and

$k_{2}=k_{2}^{[3]}:=\begin{bmatrix}-v\\\ v\\\ 0\\\
\mathbf{1}-x_{\text{new}}\\\ x_{\text{new}}\end{bmatrix}.$

There is also an equality constraint given by $\widehat{y}-\mathcal{A}D\delta
v=y_{\text{new}}$. This results in
$C_{3}=C_{3}^{[3]}:=\begin{bmatrix}0&I&-\mathcal{A}D\end{bmatrix}$ and
$k_{3}=k_{3}^{[3]}:=y_{\text{new}}$.

This leads to Algorithm 3, which is summarized in the displayed pseudocode.

Algorithm 3 Iterative componentwise attack, returning a perturbed image

1:procedure Attack($F,x,c_{0},\alpha,num,f$)

2: $out\leftarrow F(x)$

3: $v\leftarrow 0$

4: $\Delta x\leftarrow 0$

5: $newX\leftarrow x$

6: $D\leftarrow Diagonal(f)$

7: for $i=1$ to $num$ do

8: $jac\leftarrow$ Jacobian$(F,newX)$

9: $pi\leftarrow$ PseudoInverse$(jac)$

10: $con\leftarrow$ Constraints$(jac,v,out,D,c_{0})$

11: $obj\leftarrow$ Objective$(\Delta x)$

12: $z\leftarrow$ OptimizationVariable

13: $prob\leftarrow$ Minimize$(z,obj,con)$

14: Solve$(prob)$

15: $\delta v\leftarrow z.value.dv$

16: $v\leftarrow v+\alpha\cdot\delta v$

17: $\Delta x\leftarrow Dv$

18: $newX\leftarrow x+\alpha\cdot\Delta x$

19: $out\leftarrow F(newX)$

20: end for

21: return Scale$(F,x,\Delta x,c_{0})$

22:end procedure

One issue with Algorithm 3 is that the problem (11) encourages all components
of $v$ to achieve the maximum $\|v\|_{\infty}$. As we will see in section 4,
this may lead to perturbations that are very noticeable. We therefore consider
an alternative version where (11) is changed to

$\min\\{\|Dv\|_{2}:\mathcal{A}Dv=\widehat{y}-y\\}.$ (12)

Because $\Delta x=Dv$, we retain the masking effect where zero values in the
tolerance vector $f$ force the corresponding pixels to remain unperturbed. We
found that minimizing $\|Dv\|_{2}$ rather than $\|v\|_{\infty}$ produced
perturbations that appeared less obvious. We will refer to this version as
Algorithm 4. It differs from Algorithm 3 only in that $C_{1}^{[3]}$ is changed
to $\begin{bmatrix}0,0,D\end{bmatrix}$ and $k_{1}^{[3]}$ is changed to $-Dv$.

##  5 Computational Results

We implemented the algorithms in Python using PyTorch [22] and tested them in
a deep learning setting. For the constrained least-squares optimization, we
used the Splitting Conic Solver [20] from the CVXPY Python package [1, 6]. To
evaluate the Jacobian of the classification map, we used the PyTorch function
torch.autograd.functional.jacobian, which implements an efficient
backpropagation process.

We tested on the MNIST dataset of handwritten digits [16]. All images are
$28\times 28$ pixels in greyscale. They have a black background, corresponding
to a pixel value of zero, with white writing. Hence, choosing a tolerance
vector of $f=x$ in Algorithms 3 and 4 causes the background to remain
unperturbed. After applying the algorithms, we display results in the reverse
greyscale, so that the background appears white and the “ink” appears grey-
black, which we believe is a more realistic view. This dataset consists of
60,000 training images and 10,000 testing images. Following [4], the network
that we use has $784$ input nodes and a hidden layer of $100$ nodes followed
by the output layer of $10$ nodes. The layers are fully connected and the
first one has a $\tanh$ activation function, chosen because it is
differentiable. We consider different activation functions and network
architectures in subsection 5.5. All network training is done using the Adam
optimizer and a cross-entropy loss function. The accuracy of the trained
network on the test data is $97\%$.

###  5.1 Iterations

First we investigate how Algorithms 2, 3 and 4 perform with respect to the
iteration count. We use $\alpha=0.1$. After each iteration, using the Scale
function in (8) we take the smallest successful multiple of the direction
produced by the algorithm and record the resulting normwise perturbation size,
$\epsilon=\|\Delta x\|_{2}/\|x\|_{2}$. In other words, we record the
$\epsilon$ arising if we terminate at that iteration. Figure 2 shows results
for a single image. The horizontal axis gives the iteration count and the
vertical axis gives $\epsilon$. The curves, which are similar for other
images, indicate that we should use about 30 iterations to get optimal
performance; hence we use this value in subsequent experiments. We also note
that Algorithm 1 behaves in a similar way to the first step of Algorithm 2,
and hence Figure 2 shows that iterating can give a significant benefit.
Algorithm 3 produces larger relative two-norm perturbations that do not
decrease monotonically with respect to the iteration count. This is to be
expected, because the algorithm is optimizing $\|v\|_{\infty}$.

Figure 2: Performance per iteration for Algorithms 2, 3, and 4.

Next we show examples of the three iterative algorithms successfully attacking
images. We chose the first image from each digit class, “0”,“1”,“2”,…,“9”,
arising in the training set and systematically targeted each incorrect class.
Full results can be seen in the Supplementary Materials section. In Figure 3
we have picked out one example for attacked images in classes “5” to “9”. In
each case we show the perturbed, incorrectly classified, images from
Algorithms 2, 3 and 4. We also show the size of $\|\Delta x\|_{2}/\|x\|_{2}$.
We see that Algorithm 2 perturbs the background whereas, by construction,
Algorithms 3 and 4 do not. This leads to the background looking dirty or
smudgy using Algorithm 2. Whenever Algorithm 3 decides it can perturb the
pixels by some relative amount, due to the use of the infinity-norm it does
not matter how many pixels are perturbed by that relative amount. This leads
to large areas where the black is turned to grey, which is quite noticeable.
Algorithm 4 addresses this problem by optimising for the 2-norm, as shown in
(12). Overall, we see that Algorithm 4 produces images that may have arisen
naturally from a slight inconsistency in the ink delivery or the pen pressure.

Figure 3: Comparison of successful attacks created using Algorithms 2, 3, and
4, from left to right, with the relative 2-norm of the perturbation indicated.
Here the original $\rightarrow$ target examples are $5\rightarrow 9$,
$6\rightarrow 1$, $7\rightarrow 5$, $8\rightarrow 7$, and $9\rightarrow 3$.
Examples for digits 0 to 9 and all possible choices of target are shown in the
Supplementary Materials section.

In Figure 4 we return to the comparison of perturbation sizes. Here the
horizontal axis shows the relative 2-norm of the perturbation. The vertical
axis shows the proportion of attacks requiring at least that relative norm of
the perturbation to produce the desired classification. So a lower curve
indicates better performance. The figure is based on 100 images, resulting in
900 attacks. Algorithm 2 performs best according to this measure. The
iterations are seen to significantly improve the performance of these targeted
attacks—recall that Algorithm 1 does not iterate. Algorithm 3 performs quite
poorly, as is to be expected, since it does not directly control the 2-norm.
Algorithm 4, which accounts for the 2-norm while restricting to componentwise
attacks shows better performance in this regard.

Figure 4: Comparison between relative 2-norm performances of targeted versions
of Algorithms 1,2,3 and 4. The horizontal axis is the relative 2-norm of the
perturbation. The vertical axis is the proportion of attacks requiring at
least that relative norm of the perturbation to produce the desired
classification.

###  5.2 Untargeted Attacks

We now consider the scenario where it is sufficient for an attack to change
the classification to _any_ new class. We deal with this by targeting all new
classes individually and picking the smallest perturbation. We also compare
the algorithms with existing approaches designed for this untargeted case. In
Figure 5 we compare Algorithms 2 and 4 with DeepFool [19] and the $\ell_{2}$
version of projected gradient descent (PGD) [17], with the performance measure
used for Figure 4. The perturbations produced by DeepFool and PGD are scaled
in the same manner as that described for Algorithms 1, 2, 3, and 4. We see
that Algorithm 2 gives the best results. We suggest that this slight
improvement over Deepfool and PGD arises from (a) the use of $\widehat{y}$ as
an “outer” optimization variable and (b) the use of an iterative procedure to
improve the accuracy of the linearizations. These results confirm that
Algorithms 3 and 4 are building on a state-of-the-art methodology.

Figure 5: Comparison between the performances untargeted versions of of
Algorithm 2, Algorithm 4, DeepFool and PGD. Axes as for Figure 4.

###  5.3 Best Targets

Next, we look at the best targets for each class. To do this we attack 1000
images and save both the original image class and the new class of the
successful attack with smallest perturbation. We then record, for each
original class, the proportion of times that each possible new class arose as
the best target. Tables 1 and 2 show the best target proportions for
Algorithms 2 and 4, respectively. Corresponding results for Algorithms 1 and 3
are shown in the Supplementary Materials section: results for Algorithm 1 are
similar to those for Algorithm 2, and results for Algorithm 3 are similar to
those for Algorithm 4. The rows represent the classes of images that we
perturb, and the columns represent the target classes. So, for example, in
Table 1 we see that when images of the digit “0” were attacked with Algorithm
2, in 38% of the cases the smallest perturbation arose when the class was
changed to “5.” The highest proportion for each original class is highlighted
in bold. When comparing the results in Tables 1 and 2, we should keep in mind
that Algorithm 2 may take away ink from the digits and add ink to the
background, whereas Algorithm 4 may only take away ink. For the digit class
“3” it is notable that Algorithm 2 favours the target class “5”, with a
proportion of $0.57$, and the other significant target classes are “2” and
“8.” Algorithm 4 is less likely to perturb from class “3” into class “5” (the
proportion is 0.48) and target class “7” has become more frequent (0.10
compared with 0.04 in Algorithm 2). It is intuitively reasonable that
convincingly changing a 3 into a 5 or a 2 benefits from both addition and
removal of ink and changing a 3 into a 8 benefits from addition alone, both of
which are natural for Algorithm 2. Changing 3 into a 7 is more of a
subtractive process, which suits Algorithm 4. We also see that for class “1”,
Algorithm 2 favours target classes “3” and “7”, which are likely to require
addition of ink, whereas Algorithm 4 has a fairly even spread of
proportions—there is no obvious way to remove ink from a “1” in order to
approximate a different digit. Perhaps less obvious are the results for class
“9.” Here, Algorithm 2 prefers the target class “7”, with proportion $0.42$,
whereas Algorithm 4 prefers class “4”, with proportion $0.63$ and has class
“7” in second place with proportion $0.24$. We believe that this effect is
explained by the fact that there are two widely used versions of the written
digit 4. The version illustrated in the Supplementary Materials section is
close to the digit 9 with the upper portion of the loop removed.

| Alg. 2: best target class proportion
---|---
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
0 | 0.00 | 0.00 | 0.16 | 0.05 | 0.00 | 0.38 | 0.14 | 0.13 | 0.00 | 0.15
1 | 0.00 | 0.00 | 0.04 | 0.42 | 0.00 | 0.10 | 0.07 | 0.28 | 0.08 | 0.02
2 | 0.03 | 0.03 | 0.00 | 0.57 | 0.00 | 0.02 | 0.07 | 0.09 | 0.19 | 0.01
3 | 0.01 | 0.02 | 0.19 | 0.00 | 0.00 | 0.57 | 0.01 | 0.04 | 0.15 | 0.02
4 | 0.01 | 0.00 | 0.05 | 0.01 | 0.00 | 0.00 | 0.04 | 0.15 | 0.10 | 0.64
5 | 0.01 | 0.00 | 0.02 | 0.53 | 0.02 | 0.00 | 0.10 | 0.13 | 0.13 | 0.05
6 | 0.02 | 0.01 | 0.22 | 0.01 | 0.02 | 0.52 | 0.00 | 0.09 | 0.02 | 0.07
7 | 0.01 | 0.02 | 0.4 | 0.31 | 0.01 | 0.00 | 0.00 | 0.00 | 0.02 | 0.24
8 | 0.01 | 0.01 | 0.31 | 0.4 | 0.01 | 0.09 | 0.02 | 0.08 | 0.00 | 0.06
9 | 0.00 | 0.01 | 0.02 | 0.09 | 0.23 | 0.09 | 0.00 | 0.42 | 0.15 | 0.00
Table 1: Table of best target proportion for attacks made by Algorithm 2. The rows are the original classes and the columns are the target classes. | Alg. 4: best target class proportion
---|---
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
0 | 0.00 | 0.00 | 0.08 | 0.01 | 0.00 | 0.49 | 0.16 | 0.11 | 0.01 | 0.13
1 | 0.02 | 0.00 | 0.19 | 0.18 | 0.00 | 0.06 | 0.12 | 0.15 | 0.19 | 0.08
2 | 0.06 | 0.05 | 0.00 | 0.52 | 0.03 | 0.02 | 0.09 | 0.10 | 0.13 | 0.00
3 | 0.03 | 0.02 | 0.14 | 0.00 | 0.05 | 0.48 | 0.02 | 0.10 | 0.12 | 0.04
4 | 0.03 | 0.01 | 0.08 | 0.03 | 0.00 | 0.03 | 0.02 | 0.20 | 0.25 | 0.36
5 | 0.06 | 0.01 | 0.01 | 0.4 | 0.06 | 0.00 | 0.07 | 0.06 | 0.26 | 0.08
6 | 0.06 | 0.02 | 0.13 | 0.00 | 0.29 | 0.39 | 0.00 | 0.02 | 0.07 | 0.01
7 | 0.01 | 0.03 | 0.20 | 0.38 | 0.10 | 0.02 | 0.00 | 0.00 | 0.03 | 0.24
8 | 0.03 | 0.01 | 0.14 | 0.28 | 0.09 | 0.24 | 0.03 | 0.06 | 0.00 | 0.11
9 | 0.00 | 0.01 | 0.00 | 0.02 | 0.63 | 0.02 | 0.00 | 0.24 | 0.08 | 0.00
Table 2: Table of best target proportion for attacks made by Algorithm 4. The
rows are the original classes and the columns are the target classes.

###  5.4 Condition Numbers

The backward error concept discussed in Section 2 is traditionally accompanied
by a corresponding concept of conditioning (or well-posedness). A condition
number measures the worst-case sensitivity of the output to small changes in
the input and, by construction, the forward error is approximately bounded by
the product of a condition number and a backward error measure [8, 13, 14]. It
follows that when we use a neural network to classify an image, we may also
compute an appropriate condition number estimate in order to get a feel for
the sensitivity of the output to worst-case perturbations in the input, and
hence to adversarial attacks. We note, however, that in the experiments
reported so far, realistic attacks were very likely to exist for any input,
and hence we view the condition number as a possible means to quantify the
_relative_ sensitivity.

In the normwise case, if $\epsilon=\|\Delta x\|_{2}/\|x\|_{2}$ is small then

$\frac{\|F(x)-F(x+\Delta
x)\|_{2}}{\|F(x)\|_{2}}\approx\frac{\|\mathcal{A}\Delta
x\|_{2}}{\|F(x)\|_{2}}\lessapprox\frac{\|\mathcal{A}\|_{2}\|\|x\|_{2}}{\|F(x)\|_{2}}\epsilon=:\mu_{2}(x)\epsilon.$

Here, $\mu_{2}(x)$ may be viewed as a relative normwise condition number.

Similarly, under the constraint $|\Delta x|\leq\epsilon f$, where we recall
that $f$ is a nonnegative tolerance vector, we have

$\frac{\|F(x)-F(x+\Delta
x)\|_{\infty}}{\|F(x)\|_{\infty}}\approx\frac{\|\mathcal{A}\Delta
x\|_{\infty}}{\|F(x)\|_{\infty}}\lessapprox\frac{\||\mathcal{A}|\,f\|_{\infty}}{\|F(x)\|_{\infty}}\epsilon=:\mu_{\infty}(x)\epsilon;$

so $\mu_{\infty}(x)$ may be viewed as a relative componentwise condition
number.

For the normwise case, in Figure 6 we use a collection of 1000 test images
that are classified correctly. For each image we compute the best attack from
Algorithm 2. The figure scatter plots the attack perturbation size against the
normwise condition number, $\mu_{2}$. We see that a larger value of $\mu_{2}$
generally corresponds, albeit weakly, to a smaller perturbation. The
correlation coefficient is $-0.52$.

Figure 6: Scatter plot of relative normwise perturbation for Algorithm 2
against normwise condition number $\mu_{2}$ for 1000 images.

Figure 7 shows corresponding results for the componentwise condition number
$\mu_{\infty}$ with attacks from Algorithms 3 and 4. We compare this condition
number with the performances corresponding to these two attacks: the relative
infinity norm and relative 2-norm respectively. Here, the correlation
coefficients are $-0.33$ and $-0.34$ respectively, so the condition number is
less useful in this case. A possible explanation for this difference is that
perturbations are larger, and hence the linearizations are less accurate.

(a) Algorithm 3

(b) Algorithm 4

Figure 7: Scatter plot of relative componentwise perturbation and relative
2-norm respectively from Algorithms 3 and 4 against componentwise condition
number $\mu_{\infty}$ for 1000 images.

###  5.5 Architecture

So far we used a two layer network with a $\tanh$ activation function. Let us
call this Net1. We now consider two further networks. Net2 denotes the network
arising when $\tanh$ in Net1 is replaced with a rectified linear unit (ReLu).
We note that ReLu is not differentiable at the origin; this did not cause any
issues in our tests. After training, Net2 has an accuracy of $97$%. Net3 is a
convolutional neural network (CNN) [9] with two convolutional layers that
include ReLu and max pool. The first convolutional layer uses
Conv2d$(1,16,5,1,2)$ in PyTorch. The parameters correspond to the number of
input channels, number of output channels, the kernel size, the stride and the
padding, respectively. This is followed by ReLu and MaxPool with stride 2. The
second layer uses Conv2d$(16,32,5,1,2)$ and is again followed by ReLu and
Maxpool with stride 2. The final layer is a fully connected layer leading to
an output in $\mathbb{R}^{10}$. Net3 gave an accuracy of $99$%.

Figure 8 compares the performance of Algorithms 2 and 4 on these three
networks in attacking 100 images without target, using the same measure as
Figure 4. We see that for both algorithms changing to a ReLu has little
effect. Algorithm 2 finds it more difficult to attack Net3 than Net1 or Net2.
For Algorithm 4, this difference appears only in the tail of the graph; so in
moving to a more complex architecture, most images remain just as vulnerable
to componentwise attack.

Figure 8: Comparison between the normwise performances of Algorithms 2 and 4
for different networks. Axes as for Figure 4.

###  5.6 Black Box Attacks

In a black box setting, the attacker does not have access to the inner
workings of the network, and hence cannot directly evaluate the Jacobian.
However, with only input and output information it is, of course, possible to
approximate the Jacobian using finite differences. We tested the simple
Jacobian approximation

$\begin{bmatrix}\frac{F(x+h\cdot e_{1})-F(x)}{h}&\cdots&\frac{F(x+h\cdot
e_{n})-F(x)}{h}\end{bmatrix},$

where $e_{i}$ are the standard unit vectors and $h>0$ is a small parameter; we
used $h=10^{-3}$. Measuring the performance of Algorithms 2 and 4 on Net1 and
Net3 we found that results with the exact and approximate Jacobian were
essentially identical; see the Supplementary Materials. We conclude that these
attacks work equally well in a black box setting.

##  6 Conclusions

Our aim in this work was to show that it is feasible to construct
_componentwise_ adversarial attacks on image classification systems—here each
pixel is perturbed relative to a specified tolerance. In particular this
allows us to leave certain pixels unperturbed. We developed algorithms that
build on the normwise approach in [4] and make use of the concept of
componentwise backward error from [13]. Compared with state-of-the-art
normwise algorithms, when this new approach is applied to greyscale images
with a well-defined background it has the advantage that the background can be
left unchanged. In the context of physical writing or printing, such
“adversarial ink” is consistent with a blotchy pen, printer or photocopier.

We illustrated the performance of componentwise attacks on three neural
networks and in a black box setting. We also showed that the corresponding
concept of componentwise condition number has some relevance in signalling
vulnerability to attack.

Directions for future work include

  * •

testing the componentwise algorithms on further data sets, notably those
involving monochrome images of handwritten or printed text,

  * •

testing the componentwise algorithms on other image classification tools (note
that the algorithms described here do not rely on any specific form for the
classification map),

  * •

the use of object recognition [24] to identify background pixels so that the
choice of componentwise tolerance vector can be automated in complex images,

  * •

the construction of universal componentwise attacks, where the same
perturbation changes the classification of many images that have shared “non-
background” locations,

  * •

the construction of adversarial ink attacks on signatures, postcodes, dates,
cheques, or entire documents.

## Funding

LB was supported by the MAC-MIGS Centre for Doctoral Training under EPSRC
grant EP/S023291/1. DJH was supported by EPSRC grants EP/P020720/1 and
EP/V046527/1. We thank Oliver Sutton for suggesting the phrase adversarial
ink.

## References

  * [1] A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd, A rewriting system for convex optimization problems, Journal of Control and Decision, 5 (2018), pp. 42–60.
  * [2] N. Akhtar and A. Mian, Threat of adversarial attacks on deep learning in computer vision: A survey, IEEE Access, 6 (2018), pp. 14410–14430.
  * [3] 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:2109.06098 [cs.LG], (2021).
  * [4] T. Beuzeville, P. Boudier, A. Buttari, S. Gratton, T. Mary, and S. Pralet, Adversarial attacks via backward error analysis.  hal-03296180, version 3, Dec. 2021.
  * [5] R. M. Corless and N. Fillion, A Graduate Introduction To Numerical Methods: From The Viewpoint Of Backward Error Analysis, Springer, 2013.
  * [6] S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, Journal of Machine Learning Research, 17 (2016), pp. 1–5.
  * [7] A. Fawzi, O. Fawzi, and P. Frossard, Analysis of classifiers’ robustness to adversarial perturbations, Machine Learning, 107 (2018), pp. 481–508.
  * [8] G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, fourth ed., 2013.
  * [9] I. Goodfellow, Y. Bengio, and A. Courville, Deep learning, Adaptive computation and machine learning, The MIT Press, 2016.
  * [10] I. J. Goodfellow, P. D. McDaniel, and N. Papernot, Making machine learning robust against adversarial inputs, Commun. ACM, 61 (2018), pp. 56–66.
  * [11] I. J. Goodfellow, J. Shlens, and C. Szegedy, Explaining and harnessing adversarial examples, in 3rd International Conference on Learning Representations, San Diego, CA, Y. Bengio and Y. LeCun, eds., 2015.
  * [12] D. Harrison, T. M. Burkes, and D. P. Seiger, Handwriting examination: Meeting the challenges of science and the law, Forensic Science Communications, 11 (2009).
  * [13] D. J. Higham and N. J. Higham, Backward error and condition of structured linear systems, SIAM Journal on Matrix Analysis and Applications, 13 (1992), pp. 162–175.
  * [14] N. J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, second ed., 2002.
  * [15] R. A. Huber and A. M. Headrick, Handwriting Identification: Facts and Fundamentals, CRC Press, Boca Raton, FA, 1999.
  * [16] Y. LeCun and C. Cortes, MNIST handwritten digit database, (2010).
  * [17] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, Towards deep learning models resistant to adversarial attacks, in 6th International Conference on Learning Representations, Vancouver, BC, OpenReview.net, 2018.
  * [18] G. Marcus, Deep learning: A critical appraisal, arXiv:1801.00631 [cs.AI], (2018).
  * [19] S. Moosavi-Dezfooli, A. Fawzi, and P. Frossard, Deepfool: A simple and accurate method to fool deep neural networks, in 2016 IEEE Conference on Computer Vision and Pattern Recognition, NV, USA, IEEE Computer Society, 2016, pp. 2574–2582.
  * [20] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, Journal of Optimization Theory and Applications, 169 (2016), pp. 1042–1068.
  * [21] N. Papernot, P. D. McDaniel, I. J. Goodfellow, S. Jha, Z. B. Celik, and A. Swami, Practical black-box attacks against machine learning, in Proceedings of the ACM Conference on Computer and Communications Security, Abu Dhabi, UAE, R. Karri, O. Sinanoglu, A. Sadeghi, and X. Yi, eds., ACM, 2017, pp. 506–519.
  * [22] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, PyTorch: An imperative style, high-performance deep learning library, in Advances in Neural Information Processing Systems 32, Curran Associates, Inc., 2019, pp. 8024–8035.
  * [23] A. Shafahi, W. Huang, C. Studer, S. Feizi, and T. Goldstein, Are adversarial examples inevitable?, International Conference on Learning Representations, New Orleans, USA, (2019).
  * [24] S. Srivastava, A. V. Divekar, C. Anilkumar, I. Naik, V. Kulkarni, and V. Pattabiraman, Comparative analysis of deep learning image detection algorithms, J. Big Data, 8 (2021).
  * [25] 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).
  * [26] I. Y. Tyukin, D. J. Higham, A. Bastounis, E. Woldegeorgis, and A. N. Gorban, The feasibility and inevitability of stealth attacks, arXiv:2106.13997, (2021).
  * [27] 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, IEEE, 2020, pp. 1–6.
  * [28] G. Wang, Y. Wei, and S. Qiao, Generalized Inverses: Theory and Computations, Developments in Mathematics, 53, Springer Singapore, 1st ed. 2018\. ed., 2018.

##  7 Supplementary Material

In Figures 9, 10 and 11 we expand on Figure 3 by showing successful attacks
produced by Algorithms 2, 3 and 4, and the relative 2-norm of the
perturbation, on an example from each digit class and for all target classes.
Here, each image attacked is the first of its class arising in the data set.

Figure 9: Row one shows the results of adversarial attacks with Algorithm 2 on
an image from class 0. The original image is shown and then, from left to
right, we have targets 1,2,3,…,9. The numbers above the images indicate the
relative 2-norm of the perturbation. Rows two and three show this information
for Algorithms 3 and 4, respectively. This pattern then repeats for images
from classes 1,2 and 3.

Figure 10:  As in Figure 9, rows corresponds to Algorithms 2, 3 and 4 in turn
and columns indicate target class. In this case images are from classes 4,5,6
and 7.

Figure 11:  As in Figure 9, rows corresponds to Algorithms 2, 3 and 4 in turn
and columns indicate target class. In this case images are from classes 8 and
9.

Tables 3 and 4 are the analogues of Tables 1 and 2 corresponding to Algorithms
1 and 3, respectively.

| Alg. 1: best target class proportion
---|---
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
0 | 0.00 | 0.00 | 0.17 | 0.05 | 0.00 | 0.38 | 0.14 | 0.11 | 0.00 | 0.15
1 | 0.02 | 0.00 | 0.04 | 0.4 | 0.00 | 0.08 | 0.06 | 0.29 | 0.08 | 0.02
2 | 0.03 | 0.03 | 0.00 | 0.51 | 0.00 | 0.02 | 0.09 | 0.09 | 0.22 | 0.01
3 | 0.02 | 0.02 | 0.22 | 0.00 | 0.00 | 0.54 | 0.01 | 0.04 | 0.13 | 0.03
4 | 0.03 | 0.00 | 0.05 | 0.01 | 0.00 | 0.00 | 0.04 | 0.15 | 0.09 | 0.64
5 | 0.02 | 0.00 | 0.02 | 0.49 | 0.02 | 0.00 | 0.13 | 0.13 | 0.15 | 0.03
6 | 0.04 | 0.01 | 0.20 | 0.01 | 0.02 | 0.52 | 0.00 | 0.07 | 0.01 | 0.12
7 | 0.01 | 0.02 | 0.41 | 0.33 | 0.02 | 0.00 | 0.00 | 0.00 | 0.01 | 0.21
8 | 0.02 | 0.01 | 0.32 | 0.37 | 0.01 | 0.09 | 0.02 | 0.08 | 0.00 | 0.07
9 | 0.00 | 0.01 | 0.02 | 0.10 | 0.23 | 0.10 | 0.00 | 0.41 | 0.14 | 0.00
Table 3: Table of best target proportion for attacks made by Algorithm 1. The rows are the original classes and the columns are the target classes. | Alg. 3: best target class proportion
---|---
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
0 | 0.00 | 0.00 | 0.06 | 0.02 | 0.00 | 0.49 | 0.18 | 0.10 | 0.01 | 0.13
1 | 0.02 | 0.00 | 0.14 | 0.21 | 0.00 | 0.08 | 0.13 | 0.10 | 0.18 | 0.15
2 | 0.04 | 0.07 | 0.00 | 0.47 | 0.03 | 0.02 | 0.06 | 0.17 | 0.14 | 0.00
3 | 0.03 | 0.05 | 0.12 | 0.00 | 0.08 | 0.47 | 0.02 | 0.09 | 0.09 | 0.05
4 | 0.03 | 0.01 | 0.05 | 0.05 | 0.00 | 0.04 | 0.01 | 0.20 | 0.37 | 0.25
5 | 0.05 | 0.02 | 0.01 | 0.38 | 0.08 | 0.00 | 0.05 | 0.06 | 0.20 | 0.15
6 | 0.06 | 0.02 | 0.13 | 0.01 | 0.27 | 0.35 | 0.00 | 0.02 | 0.11 | 0.02
7 | 0.01 | 0.02 | 0.18 | 0.36 | 0.07 | 0.07 | 0.00 | 0.00 | 0.05 | 0.25
8 | 0.02 | 0.01 | 0.14 | 0.23 | 0.11 | 0.25 | 0.03 | 0.06 | 0.00 | 0.14
9 | 0.00 | 0.00 | 0.00 | 0.05 | 0.59 | 0.05 | 0.00 | 0.23 | 0.08 | 0.00
Table 4: Table of best target proportion for attacks made by Algorithm 3. The
rows are the original classes and the columns are the target classes.

Figure 12 shows the performance measures (as described for Figure 4) for exact
Jacobian and finite-difference (black box) versions of Algorithms 2 and 4 on
Net1 and Net3.

Figure 12: Comparison between the normwise performances of white box and black
box attacks for Algorithms 2 and 4 on three different neural networks. Axes as
for Figure 4.