# JMA: a General Algorithm to Craft Nearly Optimal Targeted Adversarial
Examples

Benedetta Tondi, , Wei Guo, Mauro Barni B. Tondi and M. Barni are from the
Department of Information Engineering and Mathematics, University of Siena,
53100 Siena, Italy. W. Guo is from the Department of Electrical and Electronic
Engineering, University of Cagliari, 09123 Cagliari, Italy. Corresponding
author: W. Guo (email<EMAIL_ADDRESS>
###### Abstract

Most of the approaches proposed so far to craft targeted adversarial examples
against Deep Learning classifiers are highly suboptimal and typically rely on
increasing the likelihood of the target class, thus implicitly focusing on
one-hot encoding settings. In this paper, we propose a more general,
theoretically sound, targeted attack that resorts to the minimization of a
Jacobian-induced MAhalanobis distance (JMA) term, taking into account the
effort (in the input space) required to move the latent space representation
of the input sample in a given direction. The minimization is solved by
exploiting the Wolfe duality theorem, reducing the problem to the solution of
a Non-Negative Least Square (NNLS) problem. The proposed algorithm provides an
optimal solution to a linearized version of the adversarial example problem
originally introduced by Szegedy et al. [1]. The experiments we carried out
confirm the generality of the proposed attack which is proven to be effective
under a wide variety of output encoding schemes. Noticeably, the JMA attack is
also effective in a multi-label classification scenario, being capable to
induce a targeted modification of up to half the labels in a complex
multilabel classification scenario with 20 labels, a capability that is out of
reach of all the attacks proposed so far. As a further advantage, the JMA
attack usually requires very few iterations, thus resulting more efficient
than existing methods.

###### Index Terms:

Adversarial Examples, Deep Learning Security, Adversarial Machine Learning,
Multi-Label Classification, Mahalanobis Distance, Non-Negative Least Square
Problems

††publicationid: pubid: 0000–0000/00$00.00 © 2021 IEEE

##  1 Introduction

Adversarial examples, namely, quasi-imperceptible perturbations capable to
induce an incorrect decision, are a serious threat to deep-learning
classifiers [1, 2]. Since the publication of the seminal work by Szegedy et
al. [1] in which the existence of adversarial examples was first observed, a
large number of gradient-based methods have been proposed to implement
adversarial attacks against Deep Neural Networks (DNNs) in white-box and
black-box scenarios. Most of the attacks proposed so far rely on greedy
algorithms that permit to find an effective adversarial example in a
reasonable amount of time [2, 3, 4, 5, 6, 7].

Most attacks create the adversarial examples by minimizing a cost function
subject to a constraint on the maximum perturbation introduced in the image.
Moreover, they focus on classifiers based on one-hot encoding. In this
setting, the final activation layer consists in the application of an
activation function (usually a softmax) and a normalization, mapping the last
layer outputs, called logits, into a probability vector, associating a
probability value to each class. The loss function corresponds to the
categorical cross entropy. As a consequence, in the targeted case, adversarial
examples focus on raising the probability value of the target class. This is
obviously the best strategy with one-hot encoding in the presence of a softmax
function, however, this strategy is no more optimal in the presence of output
encoding schemes based on channel coding, and in the case of multi-label
classification.

A more flexible attack working at the logits level has been proposed by
Carlini and Wagner [7]. The attack works by decreasing the difference between
the largest logit and the logit of the target class (in the targeted case).
Working at the logits level allows to avoid vanishing gradient problems [8],
hence Carlini and Wagner method often yields better performance compared to
methods that directly minimize the loss term. However, working on two logits
at a time, without considering the effect of the perturbation on the other
logits, is clearly suboptimum in general, with the consequence that the
approach in [7] often results in a greedy, lengthy, iterative minimization
process. The problem is more evident when the attacker aims at attacking a DNN
adopting different encoding mechanisms, like Error Correction Output Coding
(ECOC) [9], and also multi-label DNNs. In this case, all the logits have to be
modified simultaneously.

Crafting adversarial examples for networks adopting a generic output encoding
scheme, and for multi-label classification, is a very challenging task, that,
to the best of our knowledge, has not been given much attention, with the
exception of some scattered works proposing suboptimum approaches [10, 11].
From the attacker side, the difficulties of applying an optimal attack in this
case are due to the fact that the labels are not mutually exclusive (like in
the one- hot case), and decreasing or increasing the network output in
correspondence of some nodes may change the values taken by the other nodes in
an unpredictable way.

To overcome the above drawbacks, we introduce a new, theoretically sound,
targeted adversarial attack, named Jacobian-induced Mahalanobis distance
Attack (JMA). JMA solves the original formulation of the adversarial example
problem introduced by Szegedy et al. [1], which aims at minimizing the
strength of the adversarial perturbation subject to the constraint that the
image is classified as belonging to the target class. The solution is found
via a two-step procedure: i) given a target point in the output space, the
optimum perturbation moving the input sample to the target point is first
determined, under a linear assumption on the effect of the distortion on the
model output; ii) then, the target point that minimizes the perturbation
introduced by the attack is determined by minimizing the Mahalanobis distance
induced by the Jacobian matrix of the network input-output function. By
exploiting the Wolfe duality theorem, we reduce the problem to the solution of
a Non-Negative Least Square (NNLS) problem, that can be efficiently solved
numerically. The optimal perturbation derived in this way is then applied to
the input image. Ideally, the JMA attack should produce the desired
adversarial image in just one-shot. However, due to the local optimality of
the proposed approach, in practice, it is sometimes necessary to carry out
some iterations to obtain a valid adversarial example, recomputing the
Jacobian matrix every time.

The experiments we carried out confirm that the proposed attack is more
efficient than state-of-the-art attacks from a computational perspective,
requiring a much lower number of iterations to carry out the attack. State-of-
the-art attacks are also outperformed in terms of distortion and attack
success rate. The effectiveness of the proposed adversarial attack method is
particularly evident when it is used to attack networks adopting Error
Correction Output Coding (ECOC) [9] and in multi-label classification
scenarios, where the JMA attack is capable to simultaneously change in a
desired way up to 10 out of 20 labels of the output label vector, a capability
which is out of reach of the algorithms proposed so far. We also verified that
the method has a very good behavior in the one-hot encoding scenario, where it
achieves performance that are comparable to the state-of-the-art with a
significant reduction of the computing time. In summary, the main
contributions of the paper are:

  * •

We introduce a new targeted adversarial attack, named Jacobian-induced
Mahalanobis distance Attack (JMA). The attack resorts to the minimization of a
Jacobian-induced MAhalanobis distance (JMA) term, with the Jacobian matrix
taking into account the effort (in the input space) required to move the
latent space representation of the input sample in a given direction. In
theory, the algorithm is one-shot.

  * •

We solve the constrained minimization of the Mahalanobis distance by
exploiting the Wolfe duality theorem, reducing the problem to the solution of
a non-negative least square (NNLS) problem, that can be solved numerically.

  * •

We validate the new attack considering several datasets (CIFAR-10, GTSRB,
MNIST, VOC2012) and networks adopting different encoding schemes, namely the
ECOC scheme, multi-label classification, and also one-hot encoding. Our
experiments confirm that the proposed attack is very general and can work in
all these cases, being very efficient, often requiring only very few
iterations to attack the image.

  * •

We compare JMA against several state-of-the-art methods, showing that the
proposed attack is more efficient and requires a much lower number of
iterations. In the cases of ECOC and multi-label classification, it also
achieves lower distortion and higher attack success rate. In particular, in
the multi-label classification scenario, the proposed attack is capable to
change up to half labels of the sample output vector, even when the number of
labels increases.

The rest of the paper is organized as follows: in Section 2, we provide the
main formalism and describe the various classification frameworks addressed in
the paper. In Section 3, we review the most relevant adversarial attacks
introduced so far, with particular attention to the attacks against DNNs
adopting with output channel encoding. Then, in Section 4, we present the JMA
adversarial attack. The experimental methodology and setting are described in
Section 5. Sections 6 and 7 report and discuss the results of the experiments.
The papers ends in Section 8 with our final conclusions.

##  2 Background and Notation

In this section, we review the main output encoding schemes for DNN
classifiers.

Let $x\in\mathbb{R}^{m}$ denote the input of the network, and $y(x)$ (or
simply $y$) the class $x$ belongs to. We indicate with $l$ the number of
classes. To classify $x$, the neural network first maps $x$ into a reduced
dimensional space $\mathbb{R}^{n}$ ($n<m$). Every class is associated to an
output label column vector $c_{k}=(c_{k1},c_{k2},...,c_{kn})^{T}$. Let
$f(x):\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ be a column vector indicating
the end-to-end neural network function, and $f_{i}(x)$ the $i$-th element of
the vector. Classification in favour of one of the $l$ classes is obtained by
applying a function $\phi$ to $f(x)$, the exact form of $\phi$ depending on
the output encoding scheme used by the network. In the following, we denote by
$z=(z_{1},z_{2},...,z_{n})^{T}$ the vector with the logit values, that is, the
values of the network nodes before the final activation function, which is
responsible to map the output of the penultimate layer of the network into the
[0,1] (sometimes [-1, 1]) range. Given an image $x$, the notation $f^{-j}(x)$
is used to refer to the internal model representation at layer $L-j$ ($L$
being the total number of layers of the network). With this notation,
$z(x)=f^{-1}(x)$.

###  2.1 One-hot encoding

In the case of networks adopting the one-hot encoding scheme, the number of
output nodes corresponds to the number of classes ($l=n$), and $c_{k}$ is a
binary vector with all 0’s except for position $k$, where it takes value 1. In
this case, the length of $z$ is $l$, and the logits are directly mapped onto
the output nodes through a softmax function as follows:

$f_{k}(x)=\frac{\exp(z_{k})}{\sum_{i=1}^{l}\exp(z_{i})},$ (1)

for $k=1,..,l$. This allows to interpret $f_{k}(x)$ as the probability
assigned to class $k$, and the final prediction is made by letting
$\phi(x)={\arg\max}_{k}\hskip 2.84544ptf_{k}(x)$.

Typically, in the one-hot encoding case, training is carried out by minimizing
the categorical cross-entropy loss defined as
$\mathcal{L}(x,y)=-\sum_{i=1}^{l}c_{yi}\log(f_{i}(x))=-\log f_{y}(x)$111We
remind that $y$ denotes the class sample $x$ belongs to..

###  2.2 Error-correction-output-coding (ECOC)

Sometimes the output classes are encoded by using the codewords of a channel
code. In this way, error correction can be applied to recover from incorrect
network behaviors. In this case, the network output dimension $n$ corresponds
to the length of the codewords and $c_{k}$ is the codeword associated to the
$k$-th output class. The number of classes is typically less than $2^{n}$
($l<2^{n}$). An example of the use of channel coding to define the class label
vectors is given in [12] (ECOC). The use of ECOC has also been proposed as a
way to improve the robustness against adversarial attacks in a white-box
setting [9]. The rationale is the following: while with classifiers based on
standard one-hot encoding the attacker can induce an error by modifying one
single logit (the one associated to the target class), the final decision of
the ECOC classifier depends on multiple logits in a complicated manner, and
hence it is supposedly more difficult to attack.

Formally, with ECOC, a distinct codeword $c_{k}$ is assigned to every output
class. Let $C=\\{c_{1},c_{2},\cdots,c_{l}\\}$ define the codebook, that is,
the matrix of codewords. Each element of $C$ can take values in $\\{-1,1\\}$.
To compute the output of the network the logits are mapped into the $[-1,1]$
range by means of an activation function $\sigma()$, that is $f(x)=\sigma(z)$,
where $\sigma()$ is applied element-wise to the logits. A common choice for
$\sigma()$ is the $\tanh$ function. To make the final decision, the
probability of class $k$ is first computed:

$p_{k}(x)=\frac{\max(f(x)^{T}c_{k},0)}{\sum_{i=1}^{l}\max(f(x)^{T}c_{i},0)},$
(2)

where $f(x)^{T}c_{k}$ is the inner product between $f(x)$ and $c_{k}$. Since
$c_{ij}$’s take values in $\\{-1,1\\}$, the max is necessary to avoid negative
probabilities. Then, the model’s final prediction is given by
$\phi(x)={\arg\max}_{k}\hskip 2.84544ptp_{k}(x)$. Note that Eq. (2) reduces to
Eq. (1) in the case of one-hot encoding, when ${C}=\mathbf{I}_{l}$ and where
$\mathbf{I}_{l}$ is the identity $l\times l$ matrix.

In the ECOC case, training is usually carried out by minimizing the hinge loss
function, defined as
$\mathcal{L}(x,y)=\sum_{i=1}^{n}\max(1-c_{yi}f_{i}(x),0)$.

###  2.3 Multi-label classification

In this paper, we refer to multi-label classification as a scenario wherein
the classifier is asked to decide about the presence of absence within the
image of $n$ image characteristics or features. For example, the classifier
may be asked to detect the presence of $n$ possible classes of objects, or
decide about $n$ binary attributes (like indoor/outdoor, night/day,
sunny/rainy). The presence/absence of the looked-for features is encoded by
the $n$ outputs of the network (see, for instance, [13, 14]). In general, the
number of possible outputs is $l=2^{n}$, and each output is encoded in a
matrix $C$ having size $n\times 2^{n}$. In fact, it is possible that some
labels’ combinations are not feasible. In such a case, $C$ contains only the
allowed combinations, somewhat playing the same role of channel coding. In
this paper, by multi-label classification, we indicate a situation where all
combinations of labels are possible.

In the case of multi-label classification, given the logit vector $z$, the
activation function $\sigma()$ is applied element-wise to the components of
$z$, and the prediction on each label component is made component-wise.
Assuming that $c_{k}\in\\{0,1\\}^{n}$ for any $k$, and that the logistic
function is applied to the logits, decoding corresponds to 0.5-thresholding
each output score independently222If $c_{k}\in\\{-1,1\\}^{n}$, the tanh
activation is applied followed by 0-thresholding..

For the loss function, a common choice is the binary cross-entropy loss
$\mathcal{L}(x,y)=-\sum_{i=1}^{n}(c_{yi}\log(f_{i}(x))+(1-c_{yi})\log(1-f_{i}(x)))$.

##  3 Adversarial attacks against DNNs

The vulnerability of deep neural networks (DNNs) to adversarial samples has
been first pointed out by Szegedy et al. in [1]. When the goal of the attacker
is to induce a generic misclassification, we talk about an untargeted attack.
When the misclassification is in favor of a specific class, we say that the
attack is a targeted one. According to [1], the generation of a targeted
adversarial example can be formally described as

$\begin{aligned} &\textrm{minimize}\quad||\delta||_{2}\\\
&\textrm{s.t.}\quad\phi(x+\delta)=t\neq\phi(x)\\\ &\textrm{and}\quad
x+\delta\in[0,1]^{m}\end{aligned},$ (3)

where $||\delta||_{2}$ denotes the $l_{2}$ norm of the perturbation $\delta$,
and $t$ is the target class of the attack. The same formulation holds for the
untargeted case, with the first constraint replaced by
$\phi(x+\delta)\neq\phi(x)$. The constraint $x+\delta\in[0,1]^{m}$ makes sure
that the resulting adversarial example is a valid input.

###  3.1 Basic adversarial attacks

Solving the minimization in (3) is generally hard, then the adversarial
examples are determined by solving the simplified problem described below:

$\displaystyle\min_{\delta}$ $\displaystyle\hskip
5.69046pt\mathcal{L}({x+\delta},t)+\lambda\cdot\left\|\delta\right\|_{2}^{2}$
(4) s.t. $\displaystyle\hskip 5.69046ptx+\delta\in[0,1]^{m}$

where $\mathcal{L}({x+\delta},t)$ is the loss function under the target class
$t$, and $\lambda$ is a parameter balancing the importance of the two terms.
The problem in (4) can be solved by the box-constraint L-BFGS method [1].
Specifically, a line search is carried out to find the value of $\lambda>0$
for which the solution of (4) satisfies the adversarial condition, that is
$\phi(x+\delta)=t$. Usually, the categorical cross entropy loss is considered.
From (4), it is immediate to see that, in the one-hot case, when the
categorical cross entropy loss is considered, only the target class
contributes to the loss term, and then the attack only cares about increasing
$f_{t}(x)$, regardless of the other scores, all the more that, due to the
presence of the softmax, this also implies decreasing the other outputs.

To reduce the complexity of the L-BFGS attack, several suboptimal solutions
have been proposed, that consider the problem - equivalent to (4) - of
minimizing the loss function $\mathcal{L}$ subject to a constraint on the
perturbation $\delta$. The Fast Sign Gradient Method (FGSM) method [2] obtains
an adversarial perturbation in a computationally efficient way by considering
the sign of the gradient of the output with respect to the input image. The
FGSM attack is a one-step attack whose strength can be modulated only by
increasing the value of the term multiplying the gradient sign. In [4], an
iterative version of FGSM is introduced by applying FGSM multiple times, with
a smaller step size, each time by recomputing the gradient. This method is
often referred to as I-FGSM, or Basic Iterative Method (BIM). Another attack
similar to the FGSM attack is the projected gradient descent (PGD) attack [5],
that can be regarded to as a multi-step extension of the FGSM attack where the
clip operation performed by BIM on the gradient (to force the solution to stay
in the [0,1] range) is replaced by the gradient projection.

Other gradient-based attacks are the Jacobian-based Saliency Map Attack (JSMA)
[3] and the DeepFool attack [6]. JSMA [3] consists of a greedy iterative
procedure which relies on forward propagation to compute, at each iteration, a
saliency map, indicating the pixels that contribute most to the
classification. In such attack, the Jacobian matrix of the network function is
used to compute the forward derivative and build the saliency map. A variant
of this attack, called Maximal JSMA, has been proposed in [15]. DeepFool [6]
is an efficient iterative attack that considers the minimal perturbation with
respect to a linearized classifier. In this way, the current version of the
adversarial example is projected onto the separating affine hyperplane at each
iteration, until the classification boundary is crossed.

The above gradient-based methods often fail due to the gradient vanishing
problem [7]. A solution to overcome this issue has been proposed in [16],
where the values of the logits are scaled by a temperature parameter. However,
this approach lacks flexibility and the suitable distillation temperature
parameter strongly depends on the network. A more flexible and efficient
method working at the logits level has been proposed by Carlini and Wagner
(C&W) [7]. In the C&W attack the loss term is replaced by a properly designed
function depending on the difference between the logit of the target class and
the largest among the logits of the other classes (since the logits do not sum
one, two logits at a time must be considered). The perturbation is kept in the
valid range by properly modifying the objective function. In this way, the
following unconstrained problem is considered and solved (for the case of
$L_{2}$ distortion metric):

$\displaystyle\min_{w}$ $\displaystyle\hskip 5.69046pt||\delta(w)||_{2}^{2}+$
$\displaystyle\lambda\cdot\max(\max_{i\neq
t}z_{i}(x+\delta(w))-z_{t}(x+\delta(w)),-\kappa),$ (5)

where $\delta(w)=1/2(\tanh(w)+1)-x$ is the distortion introduced in the image,
and the constant parameter $\kappa>0$ is used to encourage the attack to
generate a high confidence attacked image. Since logits are more sensitive to
modifications of the input than the probability values obtained after the
softmax activation C&W attack is less sensitive to vanishing gradient
problems. However, we notice that, by considering only two logits at time, and
neglecting the effect of the perturbation on the other logits, this approach
is particularly suited to the one-hot case and is highly suboptimum when other
output encoding schemes are used.

###  3.2 Attacks against DNNs with output encoding

The adversarial attack algorithms described so far focus on models based on
one-hot encoding. This is a favorable scenario for the attacker, who only
needs to focus on increasing the output score (or logit) of the target class
$t$. This is not the case with DNNs based on different output encoding
schemes. The simplest examples are multi-label classifiers. From the
attacker’s side, the difficulties of carrying out the attack in this case are
due to the fact that the labels are not mutually exclusive, and decreasing or
increasing the network output in correspondence of some nodes may change the
values taken by the other nodes in an unpredictable way. In addition, the
attacker may want to modify more than one output label in a desired way. For
instance, he may want to induce the classifier to interpret a daylight image
showing a car driving in the rain, as a night image of a car driving with no
rain. This prevents the application of the basic adversarial algorithms
described in the previous section.

The problem of crafting adversarial examples against multi-label classifiers
has been addressed in [10], where the C&W and the DeepFool attacks have been
extended to work in a multi-label setting. The extension of C&W attack,
referred to as ML-C&W, works as follows: for every output node, a hinge loss
term similar to the one in Eq. (3.1) is considered in the minimization. More
specifically, the following term is added to the minimization:
$\sum_{i=0}^{n}\max(0,\gamma-c_{ti}\cdot z_{i}(x+\delta))$, where $c_{t}$ is
the target label vector and $\gamma$ is a confidence parameter. Note that the
extension implicitly assumes that decoding is carried out element-wise. This
is not true when all labels’ combinations are possible and with schemes
adopting output channel coding. However, by working at the logits level, the
C&W attack is general and can also be extended to work with different output
encoding schemes (as discussed below).

An extension of the DeepFool attack, referred to as ML-DF, has also been
proposed in [10]. Instead of targeting an objective function minimizing the
distortion, the method looks for the minimum perturbation that allows to enter
the target region under a linear assumption on the model behavior. ML-DF works
at the output score level, and hence is more prone to the vanishing gradient
problem than ML-C&W. Given the threshold vector
${\rho}=({\rho}_{1},{\rho}_{2},..,{\rho}_{l})^{T}$ for the score level output
($\rho_{i}=0.5$ when $f_{i}\in[0,1]$, $0$ when $f_{i}\in[-1,1]$), a vector
with the distance to the boundary is derived and used to compute the
perturbation. The perturbation obtained in this way is applied to the image.
ML-DF applies the above procedure iteratively until the attack succeeds or a
maximum number of iterations is reached. ML-DF is a greedy method and often
leads to very large distortions; Moreover, the performance obtained are always
inferior with respect to ML-C&W [10, 11].

Inspired by ML-DF, another approach to implement an adversarial attack in the
multi-label case, named Multi-Label Attack via Linear programming (MLA-LP),
has been proposed in [11]. By assuming that the loss changes are linear for
small distortions, a simplified formulation of the attack is solved to
minimize the $L_{\infty}$ distortion introduced in the image subject to a
constraint on the loss value, requiring that the final loss is lower than the
threshold value. Thanks to the adoption of the $L_{\infty}$ distortion, the
problem can be easily transformed into a linear programming problem, for which
several solvers exist. Similarly to ML-DF, MLA-LP works at the final score
output level. By considering the loss function instead of the model output
function, MLA-LP tends to modify less the confidences of non-attacked labels
with respect to ML-DF, with a lower distortion for the resulting attacked
image.

When the output coding scheme is based on ECOC, an adversarial attack can be
carried out by extending to this setting the C&W method. Specifically, the C&W
attack can be applied at the probability level, exploiting the specific
mapping of the logits to probabilities. In particular, C&W attack can be used
to attack networks adopting ECOC output encoding by replacing the logit terms
$z_{i}(x)$ with $f(x)^{T}c_{i}$, that is, by considering the loss term
$\max(\max_{i\neq t}f(x+\delta(w))^{T}c_{i}-f(x+\delta(w))^{T}c_{t},-\kappa)$.

In the case of an ECOC-based network, adversarial examples can also be
obtained by using the attack described in [17] (in the following, this method
is referred to as ECOC attack). Such an attack incorporates within the
minimization problem the ECOC decoding procedure. Formally, the optimization
problem solved in [17] is defined as:

$\displaystyle\min_{\delta}$ $\displaystyle\hskip
5.69046pt\left(||\delta||_{2}^{2}-\lambda\cdot\min_{i}(c_{ti}\cdot
z_{i}(x+\delta),\eta)\right),$ (6)

where $\eta$ is a constant parameter setting a confidence threshold for the
attack.

Although not specialized for this case, ML-C&W can also be used to attack
ECOC-based networks. Instead, ML-DeepFool and MLA-LP, that work at the score
output level and requires knowledge of the threshold vector $\rho$, cannot be
extended to the case of networks adopting an output encoding scheme like ECOC.
In fact, the threshold vector $\rho$ is not available in the ECOC case since
the decision is made after the correlations are computed. A straightforward,
highly suboptimum, way to apply these methods to the ECOC case is by setting
$\rho=(0,0,...,0)^{T}$, as if all the codewords were possible, and performing
the decoding element-wise.

####  3.2.1 The LOTS attack

A completely different kind of attack, which can be applied to any network
regardless of the output encoding scheme is the Layerwise Origin-Target
Synthesis (LOTS) attack [18]. LOTS generates the adversarial example by
modifying the input sample so that its representation in the feature space is
as similar as possible to that of a given target sample. Formally, given the
internal representation $f^{-j}(x)$ of an image $x$ at layer $L-j$ and a
target internal representation $f^{-j}(x_{t})$, LOTS attempts to minimize the
term:

$||f^{-j}(x^{t})-f^{-j}(x)||^{2}.$ (7)

At each iteration, the algorithm updates the input sample as

$x^{(i)}=x^{(i-1)}-\frac{\nu^{-j}(x,x^{t})}{\max_{x}(|\nu^{-j}(x,x^{t})|)}$
(8)

where
$\nu^{-j}(x,x^{t})=\nabla_{x}\left(||f^{-j}(x^{t})-f^{-j}(x)||^{2}\right)$,
and $|\cdot|$ is applied element-wise, until the Euclidean distance between
$f^{-l}(x)$ and the target is smaller than a predefined threshold. The final
perturbed image $x^{adv}$ obtained in this way has an internal representation
at layer $L-j$ that mimics that of the target sample $x^{t}$. In the LOTS
algorithm, the target point $x^{t}$ is any point belonging to the target class
of the attack. We observe that in general such $x^{t}$ may not be available,
e.g. in the multilabel case when the attacker targets an arbitrary labels’
combination.

When applied to the logits level ($f^{-1}$), LOTS simultaneously modifies all
the logits. However, by focusing on the minimization of the Euclidean loss,
the distortion introduced in the input space is not controlled.

####  3.2.2 JMA and prior art

Below we discuss the relationship and advantages of JMA with respect to the
state-of-the-art attacks described above.

In contrast to LOTS [18], JMA defines the target point in the feature space
that minimizes perturbation necessary to move the feature representation of
the input sample to the target point. It does so, by relying on the
Mahalanobis distance induced by the Jacobian matrix of the neural network
function so to take into account the different effort, in terms of input
perturbation, required to move the sample in different directions.

The ML-DF and MLA-LP methods [10, 11] are also based on the Jacobian matrix.
However, in [10], the Jacobian matrix is used to implement a greedy algorithm,
while in [11] is used to solve a suboptimum formulation of the attack. In our
case, instead, we are able to solve the original formulation of the attack by
Szegedy et al. under a first-order approximation. With such an approximation,
in fact, the solution of the attack problem can be reduced to the solution of
a constrained quadratic programming problem (where the objective function is a
Mahalanobis distance term induced by the Jacobian). Moreover, our algorithm is
a general one and can work either at the output level or at the logits level,
regardless of the output encoding scheme used by the network.

##  4 The JMA attack

As mentioned in the introduction, to avoid vanishing gradient problems, we
look for a method that can be applied at the logits level. As we said, while
modifying one or two logits at a time allows to carry out a close-to-optimal
adversarial attack in the one-hot encoding case [7], in the more general case
of DNNs based on output encoding, this approach is highly suboptimum. In this
scenario, in addition to considering all the logits simultaneously, as done in
the ML-C&W attack, the correlation among the logits and the effort required in
the input space to move the input sample in a given direction (in the logit or
feature space) must be considered. The JMA attack tackles the above problems
and finds the optimal adversarial image, by solving the optimization problem
in Eq. (3), under a first-order approximation of the behavior of the network
function.

In the following, we look at the output of the neural network function $f$
333For ease of notation, in the following, we consider directly the model
output $f(x)$, however the same the arguments cam be applied at the logit
level. as a generic point in $\mathbb{R}^{n}$. According to Eq. (3), the
optimum target point for the attacker corresponds to the point in the target
decision region that can be reached by introducing the minimal perturbation in
the image $x$. Such a point is not necessarily the point in the target
decision region closest to the current output point $f(x)$ in the Euclidean
norm, since evaluating the distance in the output space does not take into
account the effort necessary to move the input sample into the desired output
point. Let $x_{0}$ be the to-be-attacked image and let us denote with $\delta$
the perturbation applied by the attacker. Let $r=f(x_{0})+d$. The goal of the
attacker is to determine the displacement $d$, in such a way that $r$ lies
inside the decision region of the target class, and for which the Euclidean
norm of the perturbation $\delta(d)$ necessary to reach $r$ is minimum, that
is:

$\displaystyle\min_{d:\phi(f(x_{0})+d)=t}\left[\min_{\begin{subarray}{c}\delta:f(x_{0}+\delta)-f(x_{0})=d\\\
x_{0}+\delta\in[0,1]^{m}\end{subarray}}\hskip
5.69046pt||\delta(d)||_{2}\right].$ (9)

Without loss of generality, we will assume that all the label codewords have
the same norm, and that $\phi()$ applies a minimum distance decoding rule. In
this case, forcing $\phi(f(x_{0})+d)=t$ is equivalent to impose the following
conditions:

$r^{T}c_{t}\geq r^{T}c_{i},\quad i=1,2\dots l,$ (10)

that can be rewritten as a function of $d$ as

$d^{T}(c_{i}-c_{t})\leq g_{ti},\quad i=1,2\dots l,$ (11)

where $g_{ti}=(f(x_{0})^{T}c_{t}-f(x_{0})^{T}c_{i})$, and hence the
optimization problem in Eq. (9) can be rewritten as:

$\displaystyle\min_{\begin{subarray}{c}d:d^{T}(c_{i}-c_{t})\leq g_{ti}\\\
\forall
i,i=1,\cdots,l\end{subarray}}\bigg{[}\min_{\delta:f(x_{0}+\delta)-f(x_{0})=d}\hskip
5.69046pt||\delta(d)||_{2}\bigg{]}.$ (12)

Note that we neglected the constraint $x_{0}+\delta\in[0,1]^{m}$, trusting
that if $\delta$ is small the constraint is always satisfied. We will then
reconsider the effect of this constraint at the end of our derivation in
Section 4.1.

Under the assumption that the input perturbation is small (which should always
be the case with adversarial examples), we can consider a first order
approximation of the effect of the perturbation $\delta$ on the network
output:

$f(x_{0}+\delta)\simeq f(x_{0})+J_{x_{0}}\delta,$ (13)

where $J_{x_{0}}$ denotes the Jacobian matrix of $f$ in $x_{0}$444$f$ can
describe the output of the network or the logits (strictly speaking, in the
latter case, $f$ should be replaced by $f^{-1}$):

$J_{x}=\nabla_{x}f(x)|_{x_{0}}=\left[\frac{\partial f_{i}(x_{0})}{\partial
x_{j}}\right]_{i=1,\cdots,n,j=1,\cdots m}.$ (14)

We now show that, under the first order approximation in Eq. (13), we can
solve the minimization in Eq. (12), by applying the following two steps: i) we
first determine the optimum perturbation moving the input sample to a given
target point $r$; ii) then, we find the optimum target point $r^{*}$ by
solving a constrained quadratic programming problem. Addressing i) corresponds
to solving the following problem:

$\displaystyle\delta^{*}(d)=\arg\min_{\delta:f(x+\delta)-f(x_{0})=d}||\delta||_{2},$
(15)

that, under the linear approximation, becomes555To keep the notation light,
here and in the sequel, we omit the subscript of the Jacobian matrix.

$\displaystyle\delta^{*}(d)=\arg\min_{\delta:d=J\delta}\|\delta\|_{2},$ (16)

that corresponds to finding the minimum norm solution of the system of linear
equations $d=J\delta$. The solution of the above problem is given by the
following proposition.

######  Proposition 1.

Given that $n<m$, under the assumption that $J$ has full rank, the solution of
the minimization in Eq. (16) is:

$\displaystyle{\delta}^{*}(d)=J^{T}(JJ^{T})^{-1}d.$ (17)

###### Proof.

Eq. (16) can be rewritten as the solution of the following non-negative least-
squares problem:

$\displaystyle\min_{\delta}\|J\delta-d||_{2}^{2}=\min_{\delta}\left\\{\delta^{T}(J^{T}J)\delta-2\delta^{T}J^{T}d+d^{T}d\right\\}.$
(18)

In fact, since $(J^{T}J)$ is positive definite, the to-be-minimized function
in the right-hand side of the equation is (strictly) convex and thus admits a
minimum. If $J$ has full rank, the solution of the above problem is unique and
is given by [19]:

$\delta^{*}=J^{T}(JJ^{T})^{-1}d,$ (19)

which satisfies $J\delta^{*}=d$ (and hence $\|J\delta^{*}-d||_{2}^{2}=0$),
thus also corresponding to the minimum norm solution in (16). ∎

From Proposition 1, we can express the norm of the optimum perturbation as
follows

$\displaystyle||\delta^{*}(d)||^{2}=$
$\displaystyle\delta^{*T}\delta^{*}=(J^{T}{(JJ^{T})}^{-1}d)^{T}(J^{T}{(JJ^{T})}^{-1}d)$
$\displaystyle=$ $\displaystyle
d^{T}(J^{T}{(JJ^{T})}^{-1})^{T}(J^{T}{(JJ^{T})}^{-1}d)$ $\displaystyle=$
$\displaystyle d^{T}{{(JJ^{T})}^{-1}}d,$ (20)

where in the last equality we have exploited the symmetry of $(JJ^{T})^{-1}$
(being the inverse of a symmetric matrix $(JJ^{T})$), and then
${((JJ^{T})^{-1})}^{T}=(JJ^{T})^{-1}$.

Given the above, the optimal target point $r^{*}$, and hence the optimal
distance term $d^{*}$, is determined by solving the following minimization:

$\displaystyle\min_{d:d^{T}(c_{i}-c_{t})\leq g_{ti},\forall i\neq t}$
$\displaystyle\hskip 5.69046ptd^{T}{{(JJ^{T})}^{-1}}d.$ (21)

Note that the above formulation corresponds to minimizing the Mahalanobis
distance induced by the Jacobian matrix, between the current output of the
network and the target point. The above formulation has a very intuitive
meaning, which is illustrated in Fig. 1. The term $d^{T}{{(JJ^{T})}^{-1}}d$
allows to take into account the effort required in the pixel domain to move
along a given direction in the output domain.

Figure 1: Illustration of the intuition behind the formulation in (21). While
$r^{\prime}$ is the point in the target region closest to $f(x_{0})$ in the
Euclidean norm, $r^{*}$ is the point that can be reached with the minimum
distortion in the input space.

To solve (21), we find convenient to rewrite it as follows:

$\displaystyle\min_{d:Ad\leq b}\frac{1}{2}d^{T}{{(JJ^{T})}^{-1}}d,$ (22)

where $A=[(c_{1}-c_{t})^{T}\dots(c_{l}-c_{t})^{T}]$ has size $(l-1)\times n$,
and $b$ is an $l$-long vector defined as $b_{i}=g_{ti}$. We observe that when
$l>n+1$ the system is overdetermined.

######  Theorem 1.

Problem (22) (and hence (21)) has a unique solution given by:

$d^{*}=-(JJ^{T})(A^{T}\lambda^{*}),$ (23)

where

$\lambda^{*}=\arg\min_{\lambda}\hskip
5.69046pt\frac{1}{2}{\lambda}^{T}A(JJ^{T})A^{T}\lambda+b^{T}\lambda,\quad\lambda\geq
0,$ (24)

and then

$\delta^{*}=J^{T}(JJ^{T})^{-1}d^{*}=-J^{T}(A^{T}\lambda^{*}).$ (25)

###### Proof.

The optimal solution of the quadratic problem in (22) can be obtained by
solving the easier Wolfe dual problem [20] defined as:

$\displaystyle\max_{d,\lambda}\hskip 5.69046pt$
$\displaystyle\frac{1}{2}d^{T}{{(JJ^{T})}^{-1}}d+\lambda^{T}(Ad-b)$ s.t.
$\displaystyle{{(JJ^{T})}^{-1}}d+A^{T}\lambda=0$ $\displaystyle\lambda\geq 0,$
(26)

where $\lambda$ is a column vector with $k-1$ entries. By rewriting the
objective function as
$-\frac{1}{2}d^{T}{{(JJ^{T})}^{-1}}d+d^{T}({{(JJ^{T})}^{-1}}d+A^{T}\lambda)-b^{T}\lambda$
and after some algebra, the optimization problem can be rephrased as:

$\displaystyle\min_{d,\lambda}\hskip 5.69046pt$
$\displaystyle\frac{1}{2}d^{T}{{(JJ^{T})}^{-1}}d+b^{T}\lambda$ s.t.
$\displaystyle{{(JJ^{T})}^{-1}}d+A^{T}\lambda=0$ $\displaystyle\lambda\geq 0.$
(27)

Solving the equality constraint yields $d^{*}$ in (23) as a function of
$\lambda$. By substituting $d^{*}$ in the objective function and exploiting
the symmetry of $(JJ^{T})$ we obtain (24). ∎

The problem in (24) is a NNLS problem [20, 19], for which several numerical
solvers exist [21], many of them belonging to the class of active set methods,
see for instance [22, 23]. In particular, an easy-to-implement algorithm,
whose complexity grows linearly with the number of label vectors, named
Sequential Coordinate-Wise algorithm, has been proposed in [24].

Note that in the multi-label case, the number of label vectors grows
exponentially with $n$ (since $l=2^{n}$). However, in this case, the problem
can be significantly simplified, as discussed in Section 4.2.

###  4.1 Iterative formulation of JMA

In principle, JMA should produce an adversarial example in one-shot. In
practice, however, this is not always the case, due to the fact that the
linear assumption of $f$ holds only in a small neighborhood of the input $x$,
hence the assumption may not be met when the distortion necessary to attack
the image becomes larger. In order to mitigate this problem, we consider the
following iterative version of JMA:

  * •

When $\delta^{*}$ does not bring $x$ into the target region, that is,
$\phi(x+\delta^{*})\neq t$, we update the input in the direction given by the
perturbation considering a small step $\epsilon$, thus remaining in the close
vicinity of $x$.

  * •

When the target class is reached, a binary search is performed between the
perturbed sample $x+\delta^{*}$ and the original input $x$, and the
adversarial example resulting in the smallest perturbation is taken as the
final output of the attack.

Finally, in practice, after that the optimal perturbation $\delta^{*}$ is
superimposed to $x$, a clipping operation is performed to be sure that the
solution remains in the $[0,1]^{m}$ range. Regarding the full rank of the
Jacobian, this assumption has been verified experimentally and discussed in
Section 5.4.

The iterative JMA attack resulting from the application of the above steps is
described in Algorithm 1. In the algorithm, the maximum number of iterations
(updates) is set to $n_{it,max}$.

Algorithm 1 Iterative Jacobian-induced MAhalanobis distance (JMA) attack

0: max no. of iterations $n_{it,max}$, to be attacked image $x$, target class
$t$ (target label vector $c_{t}$), updating step size $\epsilon$

0: adversarial example $x^{adv}$

1: for $i\in[1,n_{it,max}]$ do

2: calculate $f(x)$

3: calculate the Jacobian matrix by backward propagation: $J=\nabla_{x}f(x)$

4: calculate matrix $A$ and vector $b$

5: calculate $\lambda^{*}$ in Eq.(24) via the sequential Coordinate-Wise
algorithm in [24]

6: calculate adversarial perturbation: $\delta^{*}=-J^{T}(A^{T}\lambda^{*})$.

7: $x=x+\delta^{*}$

8: $x=\text{clip}(x,0,1)$

9: if $\phi(f(x))=t$ then

10: while $\phi(f(x))=t$ do

11: do binary search between $x$ and $x-\delta^{*}$

12: $x=\text{clip}(x,0,1)$

13: end while

14: return $x^{adv}$

15: else

16: $x=(x-\delta^{*})+\epsilon\frac{\delta^{*}}{||\delta^{*}||}$

17: end if

18: end for

###  4.2 Simplified formulation for the multi-label case

In most cases, the number of classes $l$, determining the number of rows of
matrix $A$ in Eq. (22), is limited. For multi-label classification, however,
all labels’ combinations are possible, and $l=2^{n}$. Therefore, the size of
$A$ increases exponentially slowing down the attack. Luckily, in this case,
the minimization problem can be significantly simplified by properly
rephrasing the constraint in (10). Specifically, since all the codeword
combinations are possible, the constraint forcing the solution to lye in the
desired region can be rewritten element-wise as follows:

$f_{j}\cdot c_{tj}\geq 0,\quad j=1,2\dots n.$ (28)

By rewriting (28) as a function of $d$, we get

$d_{j}\cdot c_{tj}\geq-f_{j}(x_{0})\cdot c_{tj},\quad j=1,2\dots n.$ (29)

that can be rewritten in the form $Md\leq e$, where $e$ is a $n$-length vector
with elements $e_{j}=f(x_{0})_{j}\cdot c_{tj}$ and $M$ is an $n\times n$
diagonal matrix with diagonal elements $M_{jj}=-c_{tj}$. Then, the
minimization problem has the same form of (22), with $M$ and $e$ replacing $A$
and $b$, and Proposition 1 remains valid, with the difference that the scalar
vector $\lambda$ has now dimension $n$. Therefore, the NNLS problem can be
solved by means of the sequential Coordinate-Wise algorithm in [24] with
complexity $O(n)$ instead of $O(2^{n})$ as in the original formulation.

##  5 Experimental Setting

To evaluate the performance of JMA, we have run several experiments addressing
different classification scenarios, including ECOC-based classification [9]
and multi-label classification. Although less significant for our study, we
have also run some experiments in the one-hot encoding scenario. In all the
cases, the JMA attack is applied at the logits level.

We implemented the JMA attack by using Python 3.6.9 via the Keras 2.3.1 API.
We run the experiments by using an NVIDIA GeForce RTX 2080 Ti GPU. The code,
as well as the trained models and all the information for the reproducibility
of the experiments are publicly available at https://github.com/guowei-
cn/JMA–A-General-Close-to-Optimal-Targeted-Adversarial-Attack-with-Improved-
Efficiency.git.

In the following sections, we describe the classification tasks considered in
the experiments, present the evaluation methodology and comparison analysis,
and detail the experimental setting.

###  5.1 Classification networks and settings

####  5.1.1 One-hot encoding

To assess the performance of JMA attack in the one-hot encoding scenario, we
considered traffic sign classification on the German Traffic Sign Recognition
Benchmark (GTSRB) dataset [25], with a VGG16 architecture. The error rate of
the trained models on clean images is 0.005.

####  5.1.2 ECOC-based classifier

We considered the ECOC framework for three image classification tasks, namely
MNIST classification [26], CIFAR-10 classification [27], and GTSRB
classification [25]. We implemented the ECOC scheme considering an ensemble of
networks, each one outputting one bit666According to [9], resorting to an
ensemble of networks permits to achieve better robustness against attacks..
The number of branches $h$ of the ensemble is $h=10$ for MNIST and CIFAR-10,
and $h=16$ for GTSRB. We used Hadamard codewords as suggested in [9]. We
considered an Hadamard code with $n=16$ for MNIST and CIFAR-10. For the GTSRB
case, we set $l=32$, by selecting the classes with more examples, and used an
Hadamart code with $n=32$. Following the original ECOC design, we considered
the VGG16 architecture [28] as baseline, with the first 6 convolutional layers
shared by all the networks of the ensemble (shared bottom), and the remaining
10 layers (the last 8 convolutional layers and the 2 fully connected layers)
that have been trained separately for each ensemble branch. The weights of the
Image-Net pre-trained model are used for the shared bottom.

####  5.1.3 Multi-label classification

For the multi-label experiments, we considered the model architecture adopted
in [10] that is, a standard InceptionV3 [29]. The categorical hinge loss was
used to train the model, with a standard Adam optimizer with lr=$10^{-4}$ and
batch size 64.

TABLE I: Types of objects in the VOC2012 dataset. Category | Object name
---|---
Person | person
Animal | bird, cat, cow, dog, horse, sheep
Vehicle | aeroplane, bicycle, boat, bus, car, motorbike, train
Indoor | bottle, chair, dining table, potted plant, sofa, tv/monitor

The model was trained on the VOC2012 dataset [30], which is a benchmark
dataset adopted in several multi-class classification works [14, 31]. This
dataset has been used to train models to recognize object inside scenes.
Specifically, the 11,530 images of the dataset contain objects from 20
possible object classes, see Table I (the objects are classified into four
categories). Then, $n=20$ and the number of possible label vectors is
$2^{n}\approx 10^{6}$. All datasets are split into training, validation, and
testing subsets, with proportion 6:2:2. The performance of the network in this
case are measured in terms of mean average precision (mAP), that is, the mean
of the average precision (AP) for all the classes, where AP is a measure of
the area under the precision-recall curve. According to our experiments, the
mAP of our model is 0.93, which is aligned with [10].

###  5.2 Comparison with the state-of-the-art

We have compared the performance of JMA with those of the most relevant state-
of-the-art attacks for each classification scenario. In all the cases, we used
the codes made available by the authors in their repositories.

For the multi-label case, we considered ML-C&W [10], MLA-LP [11] and LOTS [18]
(we have not considered ML-DF as its performance are always inferior to
ML-C&W, see [10, 11]). As described in Section 3, LOTS can be applied to any
internal layer of the network. In our experiments, for a fair comparison, we
have applied LOTS at the logits layer. By following [18], for every target
label vector, we randomly selected 20 images with that label vector, and
averaged the logits to get the target output vector (for target label vectors
for which the total number of images available is lower than 20, we used all
the images). We stress that, in the way it works, LOTS can not target an
arbitrary labels’ combination, since examples for that combination may not be
available.

For the case of ECOC classification, the comparison is carried out against
C&W, which is also the attack considered in [9], and [17] (ECOC Attack)
specialized to work with the ECOC model [17]. Although suboptimal in this
case, we also considered ML-C&W and MLA-LP, by applying the latter as
discussed in Section 3.2. However, given the complexity of the attack in the
ECOC scenario and the high sub-optimality of MLA-LP, the performance of this
algorithm are extremely poor, and no image can be attacked by using this
method. Finally, the performance of LOTS attack are also assessed. In this
case, the target output vectors are computed by averaging on 50 images (when
the number of available images is lower than 50, we averaged all of them).

For the one-hot encoding scenario, we considered the original C&W algorithm
[7], which is one of the best performing white-box attack working at the
logits level.

###  5.3 Evaluation methodology

To test the attacks in the various scenarios, we proceeded as follows: we
randomly picked 200 images from the test set (among those that are correctly
classified by the network model); then, for each image, we randomly picked a
target label vector, different from the true label vector.

For multi-label classification, in principle, there can be - and in fact there
are - combinations of labels that are not represented in the training set. it
is also possible that some of these combinations do not correspond to valid
label vectors, as some labels may not be simultaneously 1 (or 0). Since LOTS
requires the availability of samples belonging to the target label vector, for
ease of comparison, in our experiments, we considered label vectors that
appear in the training set as target label vectors. For the other methods,
some tests have also been carried out in the more challenging case where the
target label vectors correspond to randomly chosen target vectors. Such target
vectors are obtained by randomly changing a prescribed number of bits in the
label vector of the to-be-attacked image.

An attack is considered successful only when the predicted label vector and
the target label vector coincide. If only a subset of the labels can be
modified by the attack, and the target label vector is not reached, we mark
this as a failure. We measured the performance of the attacks in terms of
Attack Success Rate (ASR), namely, the percentage of generated adversarial
examples that are assigned to the target class. To measure the quality of the
adversarial image, we considered the Peak Signal-Noise Ratio (PSNR),
characterizing the distortion introduced by the attack. The PSNR is evaluated
as $20\log_{10}(255\cdot\sqrt{H\times W}/||\delta||_{2})$, where $H\times W$
is the size of the image777Given that the attacks are multi-step and
iterative, and different iterations are necessary for the various algorithms,
we can not use $\epsilon$ as an indication of the distortion.. For the tests
with random choice of the target vector (for a prescribed number of flipped
labels), we also report the average percentage of labels/bits successfully
modified by the attack, indicated as bASR.

The computational complexity is measured by providing the average number of
iterations required by the attack, and the time - in seconds - necessary to
run it. In the following, we let $n_{it}$ denote the number of iterations
necessary to run an attack, or the number of attack updates. The average
number of iterations is denoted by $\bar{n}_{it}$.

###  5.4 Setting the Attack Parameters

The tunable parameters of JMA are the maximum number of iterations
(${n}_{it,max}$) and the step size $\epsilon$. The iteration parameter takes
also into account the number of ’for’ loops and the number of steps of the
binary search in the final iteration (see Algorithm 1), the total number of
updates of JMA, then, is ${n}_{it}=(v-1)+n_{bs}$, where $v$ is the number of
’for’ loops of the algorithm ($v<{n}_{it,max}$, see Algorithm 1) and $n_{bs}$
is the number of steps of the binary search. $n_{bs}$ is set to 6 in our the
experiments.

For C&W, ML-C&W and ECOC attack, the parameters are the initial $\lambda$, the
number of steps of the binary search $n_{bs}$, and the maximum number of
iterations $n_{it,max}$. All these attacks carry out a binary search over the
parameters $\lambda$ at every iteration to find the best value. Then,
$n_{it,max}$ provides a constraint on $n_{bs}\cdot b$, where $b$ is the number
of iterations of the optimization algorithm. As for their setting, we consider
$n_{bs}=5$ and $10$, and various values of $\lambda$.

Finally, for MLA-LP and LOTS, the only parameter is the maximum number of
iterations $n_{it,max}$ allowed in the gradient descent. In our experiments,
we considered various values of $n_{it,max}$. For MLA-LP, we set
$n_{it,max}=100$ for the multi-label classification case, and raised it up to
$3000$ in the ECOC case when the attack is more difficult. For LOTS, we set
$n_{it,max}=2000$, namely the maximum number considered in [18], maximizing
the chances to find an adversarial example. Given that the time complexity of
LOTS is limited compared to the other comparison methods, in fact, the time
complexity of the attack remains small also for large values of $n_{it,max}$.
We have verified experimentally that LOTS converges within 1000 iterations 92%
of the times888Convergence is determined by checking whether the new loss
value is close enough to the average loss value of the last 10 iterations.,
validating the soundness of our choice. For ML-C&W, we set $n_{it,max}=1000$
as default value, and in most of the cases results are reported for the
setting $(\lambda,n_{bs},n_{it,max})=(0.01,10,1000)$, that resulted in the
highest ASR. Finally, for JMA, we generally got no benefit by increasing the
number of iterations beyond 200, since most of the time JMA converges in few
iterations, and 200 is more than enough to get and adversarial image in all
the cases.

For sake of simplicity and comparison, the confidence parameter is set to 0
for all the attack methods. To avoid that the an attack gets stuck with some
images (e.g. in the multi-label case when many labels have to be changed), we
set a limit on the running time of the attack, and considered the attack
unsuccessful when an adversarial example could not be generated in less than 1
hour.

Regarding JMA, we found experimentally that, the assumption made in the
theoretical analysis that the Jacobian matrix has full rank always holds when
the number of iterations of the attack remains small. However, when the number
of iterations increases it occasionally happens that the rank of the Jacobian
matrix is not full. In this case, an adversarial perturbation can not be
found, resulting in a failure of the attack.

##  6 Results

The results we obtained in the various classification settings are reported
and discussed in this section. In all the tables, $\bar{n}_{it}$ refers to the
average number of iterations/updating of the attack, averaged on the
successful attacks. The attack parameters we report are
$(\lambda,n_{bs},n_{it,max})$ for C&W, ML-C&W and ECOC attack, and
$(\epsilon,n_{it,max})$ for JMA.

###  6.1 One-hot encoding

As we said, the main advantage of JMA with respect to state of the art methods
is obtained for classifiers that do not adopt one-hot encoding. In such a
scenario, in fact, focusing only on the target logit or final score, and
ignoring the others, as done by the most common adversarial attacks, is
approximately optimal. Nevertheless, we verified that the JMA method is also
effective in the one-hot encoding scenario. Table II reports the results we
got on the GTSRB dataset. We see that JMA achieves a much higher ASR compared
to C&W, getting close to 1, yet with a lower PSNR. This is likely due to the
fact that JMA tends to modify all the output scores, while C&W directly
focuses on raising the target output, which is an effective strategy when the
one-hot scheme is adopted for the encoding. In addition, JMA can obtain an
adversarial image in a much smaller number of iterations, requiring only very
few seconds (2.45 sec in the best setting) to attack an image thus resulting
much faster than C&W attack.

TABLE II: Results of the attacks against an one-hot encoding classifier for the GTSRB dataset. | Parameters | ASR | PSNR | $\bar{n}_{it}$ | Time(s)
---|---|---|---|---|---
JMA | ( 0.01, 200) | 0.45 | 43.16 | 66.49 | 9.82
(0.05, 200) | 0.81 | 37.88 | 50.65 | 7.44
(0.1, 200) | 0.88 | 36.86 | 38.00 | 5.66
(0.2, 200) | 0.94 | 35.76 | 29.63 | 4.41
(0.6,200) | 0.98 | 33.67 | 16.20 | 2.46
C&W | (1e-4,5, 100) | 0.19 | 46.65 | 85.95 | 45.06
(1e-4,5,200) | 0.33 | 45.24 | 171.88 | 90.11
(1e-2,5,500 ) | 0.55 | 42.36 | 443.18 | 233.45
(1e-1,10,2000) | 0.75 | 41.14 | 1661.11 | 875.35
(1e-1,10,5000) | 0.82 | 41.02 | 3577.5 | 1884.59

###  6.2 ECOC-based classifiers

The results we got for ECOC-based classification on GTSRB, CIFAR-10, and MNIST
are reported in Tables III-V. We can see that, in all the cases, JMA achieves
a much higher ASR for a similar PSNR, with a significantly lower computational
complexity.

In the case of GTSRB (Table III), the JMA attack achieves ASR=0.98 at
PSNR=38.08dB with a total average number of iterations $\bar{n}_{it}=29.15$
and attack time of $9.41$ sec. This represents a dramatic improvement with
respect to the other methods. In the case of ECOC attack, for instance, the
best result is ASR=0.93, reached for a similar distortion (PSNR=37.24dB), with
$\bar{n}_{it}$ larger than 1000 ($\bar{n}_{it}=1089.03$), which is two orders
of magnitude larger than JMA. We also see that the C&W method fails in this
case, with the ASR being about 0.30 for comparable PSNR values. We remind that
the C&W method is not designed to work in the ECOC case (the results are
aligned with those reported in [9, 17]), and when applied to the ECOC
classification scenario it looses part of its effectiveness (see discussion in
Section 3). ML-C&W is more effective, however it can only achieve ASR=0.78
with a significantly lower PSNR (30.13dB) and at the price of a larger
complexity. A very poor behavior of the attack is observed for LOTS and in
particular MLA-LP, that is never able to attack the test images,
notwithstanding the large value of $n_{it,max}$. Since this method implements
a greedy approach, it is not surprising that it fails in the complex ECOC
classification scenario (more in general, the performance of MLA-LP are poor
whenever the attack aims at changing several bits/labels - see the results on
multi-label classification).

For CIFAR-10 (Table IV), JMA achieves ASR = 1 with a PSNR of about 40dB, with
very low complexity. C&W attack achieves a much lower ASR for a similar PSNR,
with higher complexity. The ECOC attack can achieve ASR = 0.99 with
PSNR=37.27dB in the setting with $n_{it,max}=2000$, in which case the
computational complexity of the algorithm is high ($\bar{n}_{it}=1347.42$ for
an average attack time of $557.86$ sec). Regarding LOTS, it can achieve ASR =
1, yet with a lower PSNR (35.79 dB). The results we got with LOTS confirm the
lower complexity of this method with respect to ECOC attack and C&W. We also
observe that, in this case, ML-C&W have poorer performance than C&W, with only
56% of the images that can be attacked with a lower PSNR, and with a very high
computational cost. Finally, as before, MLA-LP is not able to attack the image
in almost all the cases (ASR = 0.04).

The effectiveness of JMA is also verified in the MNIST case (see Table V). As
it is always the case when attacking MNIST, the PSNR of the attacked images is
lower since, unavoidably, the attacker has to modify more the image (this is
particulary true in the targeted attack scenario). In this case, JMA reaches
ASR = 1 with PSNR = 23.30 dB, while the ASR of ECOC attack (in the best
possible setting) and LOTS is respectively 0.73 and 0.78 for a similar PSNR.
The computational time is higher for LOTS and much higher for the ECOC attack.
Both C&W and ML-C&W have poor performance and the ASR is lower than 0.52 for a
PSNR similar to that obtained by JMA.

Fig. 2 reports some examples of images (successfully) attacked with the
various methods for the three tasks.

---
Figure 2: Examples of attacked images in the ECOC classification case. The
attacker’s goal is to cause a misclassification from ‘cat’ to ‘airplane’
(CIFAR-10), from speed limitation ‘80kph’ to ‘30kph’ (GTSRB), and from digit
‘1’ to ‘3’ (MNIST). The corresponding PSNR and time required for the attack
are also provided for each case. TABLE III: Results against ECOC-based
classification on the GTSRB dataset.

| Parameters | ASR | PSNR | ${\scriptsize\bar{n}_{it}}$ | Time(s)
---|---|---|---|---|---
JMA | (0.05, 200) | 0.93 | 39.12 | 58.46 | 18.14
(0.1, 200) | 0.98 | 38.08 | 29.15 | 9.41
(0.2, 200) | 0.99 | 36.98 | 25.30 | 8.27
C&W | (1e-4,5,100) | 0.08 | 49.38 | 65.69 | 51.31
(1e-4,5,200) | 0.11 | 48.02 | 97.73 | 97.67
(1e-4,5,500) | 0.12 | 47.42 | 148.33 | 235.76
(1e-2,5,500) | 0.21 | 42.12 | 194.19 | 221.63
(1e-1,10,2000) | 0.31 | 39.77 | 782.29 | 1453.85
ECOC attack | (1e-4,5,100) | 0.35 | 43.42 | 71.22 | 87.87
(1e-4,5,200) | 0.40 | 44.18 | 109.90 | 305.28
(1e-4,5,500) | 0.43 | 44.45 | 175.67 | 332.88
(1e-2,5,500) | 0.61 | 40.64 | 309.03 | 501.80
(1e-1,10,2000) | 0.93 | 37.24 | 1089.03 | 2312.64
ML-CW | (0.01, 10, 1000) | 0.78 | 30.13 | 111.02 | 2973.17
LOTS | $n_{it,max}=2000$ | 0.40 | 39.21 | 395.33 | 97.52
MLA-LP | $n_{it,max}=1000$ | 0 | NA | NA | NA ($>$ 3600)

TABLE IV: Results against ECOC-based classification on CIFAR-10 dataset.

| Parameters | ASR | PSNR | $\bar{n}_{it}$ | Time(s)
---|---|---|---|---|---
JMA | (0.05, 200) | 1.00 | 39.39 | 14.78 | 3.14
(0.1, 200) | 1.00 | 38.79 | 6.88 | 1.92
(0.5, 200) | 1.00 | 38.20 | 6.10 | 1.20
C&W | (1e-4,5,100) | 0.49 | 40.82 | 40.76 | 23.20
(1e-4,5,500) | 0.60 | 41.42 | 119.45 | 68.49
(1e-4,10,200) | 0.90 | 37.41 | 83.97 | 48.15
(1e-4,10,500) | 0.96 | 37.62 | 187.96 | 107.78
(1e-1,10,2000) | 0.99 | 37.87 | 593.09 | 340.09
ECOC attack | (1e-4,5,100) | 0.65 | 39.11 | 83.08 | 50.36
(1e-4,5,500) | 0.92 | 38.56 | 337.53 | 180.37
(1e-4,10,200) | 0.93 | 37.78 | 176.85 | 252.89
(1e-4,10,500) | 0.95 | 37.33 | 383.74 | 557.86
(1e-1,10,2000) | 0.99 | 37.27 | 1347.42 | 2173.31
ML-CW | (0.01, 10, 1000) | 0.565 | 29.86 | 49.57 | 1409.02
LOTS | $n_{it,max}=2000$ | 1.00 | 35.79 | 38.85 | 8.61
MLA-LP | $n_{it,max}=1000$ | 0.04 | 39.39 | 5 | 7.04

TABLE V: Results against ECOC-based classification on MNIST dataset.

| Parameters | ASR | PSNR | $\bar{n}_{it}$ | Time(s)
---|---|---|---|---|---
JMA | (0.05,200) | 0.95 | 24.08 | 48.61 | 196.55
(0.1,200) | 0.96 | 23.87 | 31.60 | 136.07
(0.2,200) | 1.00 | 23.40 | 16.92 | 62.36
(0.5,200) | 1.00 | 22.34 | 12.04 | 45.53
(1,200) | 1.00 | 20.32 | 8.69 | 33.58
C&W | (1e-3,10,100) | 0.01 | 26.64 | 53.00 | 48.96
(1e-3,10,200) | 0.11 | 22.17 | 93.82 | 85.91
(1e-3,10,500) | 0.37 | 20.78 | 176.81 | 163.32
(1e-3,10,1000) | 0.42 | 20.87 | 328.05 | 327.64
(1e-1,10,2000) | 0.52 | 20.59 | 910.73 | 841.25
ECOC attack | (1e-3,10,100) | 0.18 | 21.11 | 92.28 | 131.46
(1e-3,10,200) | 0.38 | 21.32 | 181.63 | 259.54
(1e-3,10,500) | 0.59 | 21.58 | 488.73 | 697.33
(1e-3,10,1000) | 0.69 | 21.87 | 967.56 | 1387.41
(1e-1,10,2000) | 0.73 | 22.24 | 1921.29 | 2754.74
ML-CW | (0.01, 10, 1000) | 0.64 | 18.47 | 297.53 | 1679.72
LOTS | $n_{it,max}=2000$ | 0.78 | 23.66 | 242.23 | 600.14
MLA-LP | $n_{it,max}=1000$ | 0.00 | NA | NA | NA (1079 s)
MLA-LP | $n_{it,max}=3000$ | 0.00 | NA | NA | NA ($>$3600 s)

###  6.3 Multi-label classification

Table VI. shows the results we got in the case of multi-label classification
when the target label vector is chosen randomly among those contained in the
training dataset.

The average number of labels targeted by the attacks is 2.1999Most of the
images in the VOC2012 dataset contains one or very few labeled objects, hence
the label vectors have few 1’s and choosing the target label from the training
dataset results in few bit changes. We see that both JMA and ML-C&W attack get
ASR = 1. However, JMA has an advantage over ML-C&W both in terms of PSNR
(around 3dB) and, above all, in terms of computational complexity, being
approximately 64 times faster than ML-C&W. In contrast to what one would
expect, LOTS achieves much worse performance, with ASR = 0.66 and a lower
PSNR. However, the average bASR is $0.979$, that confirms that the method has
some effectiveness. We believe that the reason for the not so good results of
LOTS relies on the construction of the target vector performed by the method.
In fact, compared to multi-class classification where images belonging to the
same class have similar content, e.g. images showing the same traffic sign, in
the multi-label classification case, images sharing the same label vector may
be very different from each other, and the differences between them grow with
the amount of categories included in the label vector. For instance, an image
of a crowded city street and an image with footballers on a soccer field are
both instances of the people category, with the ’people’ label equal to 1. As
LOTS chooses the target output vector by averaging the logits of the target
images, the resulting target vector might not be plausible when the logits of
the target images are significantly different. Finally, the performance of
MLA-LP are also poor, with a much lower ASR w.r.t. JMA and ML-C&W. Moreover,
the computational cost of the attack is very high. These results are not in
contrast with the results reported in [11] for the same dataset, given that in
[11] the method is validated for target attacks that change only one bit of
the original label vector, while the average number of bits changed in our
experiments is larger than 2.

Tables VII through IX show the results in a challenging scenario where the
target vector labels are not chosen from the training/test set but are
obtained by randomly changing a certain number of bits of the label vector of
the to-be-attacked image. Specifically, Tables VII, VIII and IX correspond to
attacks inducing respectively 5, 10 and 20 bit errors (in the latter case all
the bits should be changed). The results are reported for JMA, ML-C&W and MLA-
LP. As we said LOTS can not be applied in this case, since this method
requires the availability of a number of samples corresponding to the target
label vector - that, in principle, in this case may not even correspond to a
plausible image.

Looking at the results in Table VII, we see that in the 5 bit case JMA can
achieve ASR = 0.95 (bASR = 0.99), which is 5% higher than ML-CW with an
average attack time with is approximately 6 times lower, while MLA-LP is
totally ineffective (ASR = 0).

For the case of 10 bit and 20 bit errors, we also report the results with
larger $n_{it,max}$ for both JMA and ML-C&W. In fact, achieving a successful
attack in the case where half of the bits and, even worse, all the bits are
changed is extremely hard, and more iterations are necessary. From Table VIII
we see that, in the 10 bit case, JMA can still achieve an ASR close to 0.90,
at the price of a longer time necessary to run the attack, with an average
number of iterations $\bar{n}_{it}$ that goes above 240. The C&W attack
achieves a lower ASR with a bit larger PSNR when $n_{it,max}$ is raised to
5000, with a very large computational cost. Fig. 3 shows some examples of
images successfully attacked by JMA in the 10-bit error case, when half of the
labels are modified.

As shown in Table IX, the ASR drops in the 20 bit case, namely, for an attack
that tries to modify all the 20 components of the label vector. Arguably, this
represents a limit and extremely challenging scenario. We see that, by
increasing $n_{it,max}$ to 2000, the JMA attack is successful 26% of the
times, at the price of a high computational cost, while ML-C&W is never
successful. Moreover, it is interesting to observe that JMA can achieve a bASR
of 0.68, meaning that almost 70% of the labels are modified by the attack,
while the bASR for ML-C&W is below 0.1. Not surprisingly, the PSNR is low in
this case.

---
Figure 3: Examples of JMA attacked images for which the attack can
successfully flip 10 targeted bits of the label vector in the multi-label
(VOC2012) classification task. For the car: the original image has label
vector ( ’car’=1 , ‘person’ =0, ‘cat’ = 0, ‘cow’ = 0, ‘dog’ = 0, ‘sheep’ = 0,
‘bike’ = 0, ‘chair’ = 0, ‘potted plant’ = 0, ‘monitor’ = 0, ’aeroplane’ = 0,
‘bird’ = 0, ‘horse’ =0, ‘boat’ = 0, ‘dining table’ = 0, ’train’ = 0,…..),
while the JMA attacked image is classified as ( ’car’=0 , ‘person’ =1, ‘cat’ =
1, ‘cow’ = 1, ‘dog’ = 1, ‘sheep’ = 1, ‘bike’ = 1, ‘chair’ = 1, ‘potted plant’
= 1, ‘monitor’ = 1, ’aeroplane’ = 0, ‘bird’ = 0, ‘horse’ =0, ‘boat’ = 0,
‘dining table’ = 0, ’train’ = 0,…..). For the airplane: the original image has
label vector ( ’car’=0 , ‘person’ =0, ‘cat’ = 0, ‘cow’ = 0, ‘dog’ = 0, ‘sheep’
= 0, ‘bike’ = 0, ‘chair’ = 0, ‘potted plant’ = 0, ‘monitor’ = 0, ’aeroplane’ =
1, ‘bird’ = 0, ‘horse’ =0, ‘boat’ = 0, ‘dining table’ = 0, ’train’ = 0,…..),
while the label vector of the JMA attacked image is ( ’car’=0 , ‘person’ =1,
‘cat’ = 1, ‘cow’ = 1, ‘dog’ = 0, ‘sheep’ = 0, ‘bike’ = 0, ‘chair’ = 0, ‘potted
plant’ = 1, ‘monitor’ = 1, ’aeroplane’ = 0, ‘bird’ = 0, ‘horse’ =1, ‘boat’ =
1, ‘dining table’ = 1, ’train’ = 0,…..). The corresponding PSNR value is also
reported.  TABLE VI: Results of the attacks against multi-label classification
on the VOC2012 dataset. On the average the attacks are asked to flip 2.1
labels.

| Parameters | ASR | bASR | PSNR | $\bar{n}_{it}$ | Time(s)
---|---|---|---|---|---|---
JMA | (0.05,200) | 1.00 | 1.0000 | 56.54 | 29.94 | 25.97
(0.1,200) | 1.00 | 1.0000 | 55.78 | 17.50 | 15.39
(0.5,200) | 1.00 | 1.0000 | 49.66 | 7.51 | 7.32
(1,200) | 1.00 | 1.0000 | 44.86 | 6.42 | 6.45
ML-C&W | (0.01, 10, 1000) | 1.00 | 1.0000 | 52.03 | 180.93 | 469.90
LOTS | 2000 | 0.66 | 0.9787 | 50.91 | 437.20 | 268.16
MLA-LP | 100 | 0.58 | 0.9560 | 51.17 | 50.44 | 1361.29

TABLE VII: Results for VOC2012 classification with random choice of the target
label vector (5 bits out of 20 are flipped).

---
| Parameters | ASR | bASR | PSNR | $\bar{n}_{it}$ | Time(s)
JMA | (0.05,200) | 0.49 | 0.9032 | 49.18 | 129.85 | 139.31
(0.1,200) | 0.82 | 0.9687 | 47.48 | 110.21 | 106.98
(0.2,200) | 0.95 | 0.9942 | 45.26 | 87.96 | 79.05
ML-C&W | (0.01, 10, 1000) | 0.90 | 0.9883 | 45.29 | 113.35 | 420.21
MLA-LP | 100 | 0 | 0.4264 | NA | NA | NA

TABLE VIII: Results for VOC2012 classification with random choice of the
target label vector (10 bits out of 20 are flipped).

| Parameters | ASR | bASR | PSNR | $\bar{n}_{it}$ | Time(s)
---|---|---|---|---|---|---
JMA | (0.05,200) | 0.01 | 0.5714 | 48.16 | 161.00 | 157.41
(0.1,200) | 0.06 | 0.6700 | 45.62 | 163.84 | 156.04
(0.2,200) | 0.23 | 0.8112 | 42.77 | 163.40 | 162.63
(0.5,200) | 0.31 | 0.8842 | 35.60 | 161.36 | 158.88
(0.1, 500) | 0.56 | 0.8892 | 43.61 | 312.42 | 397.42
(0.5, 500) | 0.88 | 0.9805 | 35.66 | 245.24 | 278.02
ML-C&W | (0.01, 10, 1000) | 0.295 | 0.8697 | 45.09 | 270.17 | 498.63
(0.01, 10, 2000) | 0.4186 | 0.9156 | 44.46 | 451.78 | 939.53
(0.1, 10, 2000) | 0.475 | 0.9147 | 44.73 | 433.75 | 934.58
(0.5, 10, 2000) | 0.475 | 0.9147 | 44.78 | 430.96 | 908.92
(0.1, 10, 3000) | 0.575 | 0.9331 | 44.81 | 581.53 | 1461.05
(0.1, 10, 5000) | 0.72 | 0.9557 | 44.74 | 775.97 | 2183.79
MLA-LP | 100 | 0 | 0.5167 | NA | NA | NA

TABLE IX: Results for VOC2012 classification with random choice of the target
label vector. Case of 20 bit errors (all labels are changed by the attack).

| Parameters | ASR | bASR | PSNR | $\bar{n}_{it}$ | Time(s)
---|---|---|---|---|---|---
JMA | (0.05,200) | 0 | 0.1109 | NA | NA | NA
(0.1,200) | 0 | 0.1276 | NA | NA | NA
(0.2,200) | 0 | 0.1475 | NA | NA | NA
(0.5,200) | 0 | 0.1845 | NA | NA | NA
(0.5,500) | 0 | 0.3288 | NA | NA | NA
(0.5,1000) | 0.03 | 0.5068 | 30.86 | 938.16 | 980.82
(0.5,2000) | 0.26 | 0.6795 | 29.43 | 1484.34 | 1677.49
ML-C&W | (0.01, 10, 1000) | 0 | 0.0659 | NA | NA | NA
(0.5, 10, 2000) | 0 | 0.0882 | NA | NA | NA

##  7 Discussion

Our experiments showed that JMA requires a small number of iterations to find
an adversarial example, much smaller than the other algorithms, and gets an
ASR that is generally higher (in some cases, much higher) for a similar
distortion. It is worth stressing that the number of updates $\bar{n}_{it}$
reported in the tables takes into account also the steps of the binary search
carried out at the end of the iterations (see Section 5.4). Specifically,
$it=(v-1)+n_{bs}$, where $v$ is the number of ’for’ loops, that is, the number
of image updates (see Algorithm 1), and $n_{bs}$ is set equal to $6$. Then,
the $\bar{n}_{it}$ values reported in the various tables reveal that JMA can
indeed find an adversarial image in one shot in many cases, see for instance
Table IV for CIFAR-10 ECOC classification and Table VI for the multi-label
classification where $\bar{n}_{it}$ is lower than 7 for the attack settings
with larger $\epsilon$101010Note that, even when a one-shot attack is
possible, a perturbation applied to the image with a weak strength $\epsilon$
may not result in an adversarial image, thus requiring that more iterations
are run.. This confirms a-posteriori the validity of one of the most basic
assumptions underlying our approach, namely the local linear behavior, that,
when it holds, allows to perform the attack in one-shot. When the linear
approximation does not hold in the close vicinity of the initial point, and
possibly of other points obtained after the updating, the perturbation is
added with a small $\epsilon$ in order to change the initial point, and the
Jacobian is recomputed (see Algorithm 1). By inspecting the tables (see for
instance Table II), we can see that, when this happens, it is often preferable
to use a not-too-small $\epsilon$ so that the point is moved farther from the
initial point, where the behavior of the local function can be closer to
linear, instead of remaining in the vicinity of the initial point where the
local approximation may still be not satisfied. Doing so, a high ASR can be
achieved with a reduced number of iterations and a similar PSNR.

##  8 Conclusions

We have proposed a general, nearly optimal, targeted attack, that can solve
the original formulation of the adversarial attack by Szegedy et al. under a
first order approximation of the network function. The method resorts to the
minimization of a Mahalanobis distance term, which depends on the Jacobian
matrix taking into account the effort necessary to move the output
representation of the image in a given direction. By exploiting the Wolfe
duality, the minimization problem is reduced to a non-negative least square
(NNLS) problem, that can be solved numerically. The experiments show that the
JMA attack is effective against a wide variety of DNNs adopting different
output encoding schemes, including networks using error correction output
encoding (ECOC) and multi-label classification, outperforming existing attacks
in terms of larger attack success rate, lower distortion and lower complexity.
In particular, in the multi-label case, our experiments show that JMA is
capable to simultaneously change up to 10 (random) labels of the output label
vector for VOC2012 classification with a very high ASR (and, in some cases, it
can also change all the 20 output labels), a capability that is completely out
of reach of the attacks proposed so far. JMA remains effective also in the
case of one-hot encoding, where it has much reduced computational complexity
with respect to the C&W attack.

Future work will focus on exploiting the JMA attack in a black-box attack
scenario, to develop powerful targeted attacks with certain transferability
properties. Exploiting the proposed attack for adversarial training, to
increase robustness of general classification models against targeted attacks,
is also another interesting research direction.

## Acknowledgment

This work has been partially supported by the Italian Ministry of University
and Research under contract PRIN 2017 2017Z595XS-001 (PREMIER project).

## References

  * [1] 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.
  * [2] I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” _arXiv preprint arXiv:1412.6572_ , 2014.
  * [3] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami, “The limitations of deep learning in adversarial settings,” in _2016 IEEE European symposium on security and privacy (EuroS &P)_. IEEE, 2016, pp. 372–387.
  * [4] A. Kurakin, I. Goodfellow, and S. Bengio, “Adversarial examples in the physical world,” _arXiv preprint arXiv:1607.02533_ , 2016.
  * [5] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” _arXiv preprint arXiv:1706.06083_ , 2017.
  * [6] S.-M. Moosavi-Dezfooli, A. Fawzi, and P. Frossard, “Deepfool: a simple and accurate method to fool deep neural networks,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2574–2582.
  * [7] N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in _2017 ieee symposium on security and privacy (sp)_. IEEE, 2017, pp. 39–57.
  * [8] S. Hochreiter, Y. Bengio, P. Frasconi, J. Schmidhuber _et al._ , “Gradient flow in recurrent nets: the difficulty of learning long-term dependencies,” 2001\.
  * [9] G. Verma and A. Swami, “Error correcting output codes improve probability estimation and adversarial robustness of deep neural networks,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 8646–8656.
  * [10] Q. Song, H. Jin, X. Huang, and X. Hu, “Multi-label adversarial perturbations,” in _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 2018, pp. 1242–1247.
  * [11] N. Zhou, W. Luo, X. Lin, P. Xu, and Z. Zhang, “Generating multi-label adversarial examples by linear programming,” in _2020 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2020, pp. 1–8.
  * [12] T. G. Dietterich and G. Bakiri, “Solving multiclass learning problems via error-correcting output codes,” _Journal of artificial intelligence research_ , vol. 2, pp. 263–286, 1994.
  * [13] K. Chatfield, K. Simonyan, A. Vedaldi, and A. Zisserman, “Return of the devil in the details: Delving deep into convolutional nets,” _arXiv preprint arXiv:1405.3531_ , 2014.
  * [14] J. Wang, Y. Yang, J. Mao, Z. Huang, C. Huang, and W. Xu, “Cnn-rnn: A unified framework for multi-label image classification,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2285–2294.
  * [15] R. Wiyatno and A. Xu, “Maximal jacobian-based saliency map attack,” _arXiv preprint arXiv:1808.07945_ , 2018.
  * [16] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami, “Distillation as a defense to adversarial perturbations against deep neural networks,” in _2016 IEEE symposium on security and privacy (SP)_. IEEE, 2016, pp. 582–597.
  * [17] B. Zhang, B. Tondi, X. Lv, and M. Barni, “Challenging the adversarial robustness of dnns based on error-correcting output codes,” _Security and Communication Networks_ , vol. 2020, 2020.
  * [18] A. Rozsa, M. Günther, and T. E. Boult, “Lots about attacking deep features,” in _2017 IEEE International Joint Conference on Biometrics (IJCB)_. IEEE, 2017, pp. 168–176.
  * [19] S. Boyd, S. P. Boyd, and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [20] D. P. Bertsekas, “Nonlinear programming,” _Journal of the Operational Research Society_ , vol. 48, no. 3, pp. 334–334, 1997.
  * [21] R. Fletcher, _Practical methods of optimization_. John Wiley & Sons, 2013.
  * [22] C. L. Lawson and R. J. Hanson, _Solving least squares problems_. SIAM, 1995.
  * [23] J. Myre, E. Frahm, D. Lilja, and M. Saar, “Tnt-nn: A fast active set method for solving large non-negative least squares problems,” _Procedia Computer Science_ , vol. 108, pp. 755–764, 2017, international Conference on Computational Science, ICCS 2017, 12-14 June 2017, Zurich, Switzerland. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1877050917307858
  * [24] V. Franc, V. Hlaváč, and M. Navara, “Sequential coordinate-wise algorithm for the non-negative least squares problem,” in _Computer Analysis of Images and Patterns_ , A. Gagalowicz and W. Philips, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 407–414.
  * [25] J. Stallkamp, M. Schlipsing, J. Salmen, and C. Igel, “Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition,” _Neural networks_ , vol. 32, pp. 323–332, 2012.
  * [26] Y. LeCun, “The mnist database of handwritten digits,” _http://yann. lecun. com/exdb/mnist/_ , 1998.
  * [27] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * [28] [Online]. Available: https://tensorflow.google.cn/api_docs/python/tf/keras/applications/VGG16
  * [29] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2818–2826.
  * [30] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. (2012) The pascal visual object classes challenge 2012 (voc2012) results. [Online]. Available: http://www.pascal-network.org/challenges/VOC/voc2012/workshop/index.html
  * [31] K. Chatfield, K. Simonyan, A. Vedaldi, and A. Zisserman, “Return of the devil in the details: Delving deep into convolutional nets,” in _British Machine Vision Conference, BMVC 2014, Nottingham, UK, September 1-5, 2014_ , M. F. Valstar, A. P. French, and T. P. Pridmore, Eds. BMVA Press, 2014.

|  Benedetta Tondi received the master degree (cum laude) in electronics and
communications engineering, and the Ph.D. degree in information engineering
and mathematical sciences, from the University of Siena, Siena, Italy, in 2012
and 2016, respectively. She is currently an Assistant Professor with the
Department of Information Engineering and Mathematics, University of Siena.
She teaches the course of Information Theory and Fundamentals of
Telecommunications. She is part of the IEEE Young Professionals and IEEE
Signal Processing Society, and a Member of the National Inter-University
Consortium for Telecommunications. Recently, she is working on machine
learning and deep learning applications for digital forensics and counter-
forensics, and on the security of machine learning techniques. Her research
interests include application of information-theoretic methods and game theory
concepts to forensics and counter-forensics analysis and more in general to
multimedia security, and on adversarial signal processing. She is recipient of
the Best Student Paper Award at the IEEE International Workshop on Information
Forensics and Security (WIFS) 2014, the Best Paper Award at the IEEE
International Workshop on Information Forensics and Security (WIFS) 2015 and
at the The Ninth International Conferences on Advances in Multimedia (MMEDIA)
2017. She is winner of the 2017 GTTI PhD Award for the best PhD Theses
defended at an Italian University in the areas of Communications Technologies
(Signal Processing, Digital Communications, Networking). From January 2019,
she is also a Member of the Information Forensics and Security Technical
Committee of the IEEE Signal Processing Society. She has been member of the
organizing committee of several ACM and IEEE workshops and conferences. She
was the technical program co-chair of ACM IH&MMSEC 22. She currently serves as
an Associate Editor for the Journal Frontiers in Signal Processing, IEEE
Transactions on Information Forensics and Security and the IEEE Signal
Processing Letters.
---|---
|  Wei Guo Wei Guo received his M.Eng. degree in Department of Computer and
Information Security from Guilin University of Electronic Technology (GUET) in
2018, focusing on applied cryptography of IoT environment. He received a Ph.D.
degree from the Department of Information Engineering and Mathematics of
University of Siena (UNISI), Siena, ITALY, in 2023. His Ph.D. research focuses
on Security Concerns in Deep Neural Networks under the supervision of Prof.
Mauro Barni. Now, he is still focusing on the AI safety and security topic,
and working as a PostDoc researcher in University of Cagliari, supervised by
Prof. Battista Biggio.
---|---
|  Mauro Barni (M’92-SM’06-F’12) graduated in electronic engineering at the
University of Florence in 1991. He received the PhD in Informatics and
Telecommunications in October 1995. Mauro Barni is full professor at the
University of Siena, where he funded the Visual Information Processing and
Protection group (VIPP). In the last two decades he has been studying the
application of image and signal processing for security applications. His
current research interests include multimedia forensics, adversarial machine
learning and DNN watermarking. He has published about 350 papers in
international journals and conference proceedings. He has been the Editor in
Chief of the IEEE Transactions on Information Forensics and Security for the
years 2015-2017. He was the funding editor of the EURASIP Journal on
Information Security. He has been the chairman of the IEEE Information
Forensic and Security Technical Committee (IFS-TC). He was the technical
program chair of ICASSP 2014. He was appointed DL of the IEEE SPS for the
years 2013-2014. He is the recipient of the Individual Technical Achievement
Award of EURASIP for 2016. He is a fellow member of the IEEE and the AAIA, and
a member of EURASIP.
---|---