Abstract
Deep neural networks perform well on real world data but are prone toadversarial perturbations: small changes in the input easily lead tomisclassification. In this work, we propose an attack methodology not only forcases where the perturbations are measured by $\ell_p$ norms, but in fact anyadversarial dissimilarity metric with a closed proximal form. This includes,but is not limited to, $\ell_1, \ell_2$, and $\ell_\infty$ perturbations; the$\ell_0$ counting "norm" (i.e. true sparseness); and the total variationseminorm, which is a (non$\ell_p$) convolutional dissimilarity measuring localpixel changes. Our approach is a natural extension of a recent adversarialattack method, and eliminates the differentiability requirement of the metric.We demonstrate our algorithm, ProxLogBarrier, on the MNIST, CIFAR10, andImageNet1k datasets. We consider undefended and defended models, and show thatour algorithm easily transfers to various datasets. We observe thatProxLogBarrier outperforms a host of modern adversarial attacks specialized forthe $\ell_0$ case. Moreover, by altering images in the total variationseminorm, we shed light on a new class of perturbations that exploitneighboring pixel information.
Quick Read (beta)
A principled approach for generating adversarial images under nonsmooth dissimilarity metrics
Abstract.
Deep neural networks perform well on real world data but are prone to adversarial perturbations: small changes in the input easily lead to misclassification. In this work, we propose an attack methodology not only for cases where the perturbations are measured by ${\mathrm{\ell}}_{p}$ norms, but in fact any adversarial dissimilarity metric with a closed proximal form. This includes, but is not limited to, ${\mathrm{\ell}}_{1},{\mathrm{\ell}}_{2}$, and ${\mathrm{\ell}}_{\mathrm{\infty}}$ perturbations; the ${\mathrm{\ell}}_{0}$ counting “norm” (i.e. true sparseness); and the total variation seminorm, which is a (non${\mathrm{\ell}}_{p}$) convolutional dissimilarity measuring local pixel changes. Our approach is a natural extension of a recent adversarial attack method, and eliminates the differentiability requirement of the metric. We demonstrate our algorithm, ProxLogBarrier, on the MNIST, CIFAR10, and ImageNet1k datasets. We consider undefended and defended models, and show that our algorithm easily transfers to various datasets. We observe that ProxLogBarrier outperforms a host of modern adversarial attacks specialized for the ${\mathrm{\ell}}_{0}$ case. Moreover, by altering images in the total variation seminorm, we shed light on a new class of perturbations that exploit neighboring pixel information.
1. Introduction
Deep neural networks (DNNs) have strong classification abilities on training and validation datasets. However, they are vulnerable to adversarial images, which are formally defined as imperceptibly small changes (in a given dissimilarity metric) to model input that lead to misclassification [33, 16]. This behavior could mean several things: the model is overfitting on some level; the model is underregularized; or this is simply due to complex nonlinearities in the model. This has lead to several lines of work in the deep learning community: the generation of adversarial images, defending against these adversarial attacks, and lastly determining which dissimilarity metric to consider.
Regarding the latter, it is not obvious what “imperceptibly small” means, and recent work has demonstrated adversarial image generation beyond ${\mathrm{\ell}}_{p}$ norms by considering deformations instead of perturbations [1]. There is also the problem of generating “realistic” attacks, such as through sparse attacks. For example these include small stickers on a road sign, which may tamper with autonomous vehicles [13]. The purpose of this work is adversarial image generation for a broad class of (possibly nondifferentiable) dissimilarity metrics for both undefended and defended networks. We do not make judgment regarding which metric is “best”; instead we are interested in an attack framework that works well for a broad class of metrics.
Adversarial attacks are often broadly categorized into one of two types: whitebox attacks, where the full structure of the neural network is provided to the attacker, including gradient information, or blackbox attacks, where the attacker is only given the model decision. One of the first proposed adversarial attacks is the Fast Gradient Signed Method (FGSM), which generates an adversarial image with respect to the ${\mathrm{\ell}}_{\mathrm{\infty}}$ norm, along with its iterative form, dubbed Iterative FGSM (IFGSM) [16, 19]. A similar iterative attack was also done with respect to the ${\mathrm{\ell}}_{2}$ norm. In their purest form, the above attacks perform gradient ascent on the training loss function subject to a norm constraint on the perturbation, either with one step in the case of FGSM, or multiple steps in the case of IFGSM, and their ${\mathrm{\ell}}_{2}$ norm equivalents. Apart from training loss maximization, attacks have been developed using loss functions that directly measure misclassification [8, 24]. Others have considered the ${\mathrm{\ell}}_{1}$ and ${\mathrm{\ell}}_{0}$ norms; these both induce sparsity in the perturbations [23]. In the blackbox setting, adversarial examples are generated using only model decisions, which is a much more expensive endeavor. However, blackbox methods often perform better, most notably by avoiding gradient obfuscation, since they take advantage of sampling properties near the decision boundary of the model. Notable examples of blackbox (decisionbased) attacks are the Boundary Attack [7] and the recent HopSkipJumpAttack [9].
The development of new and improved adversarial attacks has occurred in parallel with various defensive training regimes to provide robustness against adversarial perturbations. The task of training a robust network is twofold: models must be resistant to perturbations of a certain magnitude, while also maintaining classification ability on clean data. It has been argued that these two objectives are inherently “at odds” [34]. A popular method for training robust networks is adversarial training, where adversarial examples are added to the training data (see for example [21]).
Contributions
This paper introduces an attack methodology for not just ${\mathrm{\ell}}_{p}$ norms, but any adversarial dissimilarity metric with a closed proximal form. This includes, but is not limited to, ${\mathrm{\ell}}_{1}$, ${\mathrm{\ell}}_{2}$, ${\mathrm{\ell}}_{\mathrm{\infty}}$, the ${\mathrm{\ell}}_{0}$ counting “norm”, i.e. a true measurement of sparseness of the perturbation, and total variation, a non${\mathrm{\ell}}_{p}$ dissimilarity. Our approach adopts the relaxation structure of the recently proposed LogBarrier attack [15], which required differentiable metrics. We extend this work to include a broad class of nonsmooth (nondifferentiable) metrics. Our algorithm, ProxLogBarrier, uses the proximal gradient method for generating adversarial perturbations. We demonstrate our attack on MNIST, CIFAR10, and ImageNet1k datasets. ProxLogBarrier shows significant improvement over both the LogBarrier attack, and over the other attacks we considered. In particular, in the ${\mathrm{\ell}}_{0}$ case, we achieve stateoftheart results with respect to a suite of attacks typically used for this problem class. Finally, by using the total variation dissimiliarity, we shed light on a new class of imperceptible adversaries that incorporates neighboring pixel information, which can be viewed as an adversarial attack measured in a convolutional norm.
2. Background material
2.1. Adversarial attacks
Let $\mathcal{X}$ be the image space, and ${\mathrm{\Delta}}_{c}$ be the label space (the unitsimplex for $c$ classes). An imagelabel pair is defined by $(x,y)\in \mathcal{X}\times {\mathrm{\Delta}}_{c}$, with the image belonging to one of $c$ classes. The trained model is defined by $f:\mathcal{X}\to {\mathrm{\Delta}}_{c}$. An adversarial perturbation should be small with respect to a dissimilarity metric (henceforth simply called the metric) $m(\cdot ;x)$, e.g. $\parallel \cdot x{\parallel}_{\mathrm{\infty}}$. Formally, the optimal adversarial perturbation is the minimizer of the following optimization problem:
(1)  $\underset{u\in \mathcal{X}}{\mathrm{min}}m(u;x)\mathit{\hspace{1em}}\text{subject to}\mathit{\hspace{1em}}\text{argmax}f(u)\ne y.$ 
DNNs might be powerful classifiers, but that does not mean their decision boundaries are wellbehaved. Instead, researchers have popularized using the training loss, often the crossentropy loss, as a surrogate for the decision boundary: typically a model is trained until the loss is very low, which is often related to good classification performance. Thus, instead of solving (1), one can perform Projected Gradient Descent (PGD) on the crossentropy loss:
(2)  $$\underset{u\in \mathcal{X}}{\mathrm{max}}\mathcal{L}(u)\mathit{\hspace{1em}}\text{subject to}\mathit{\hspace{1em}}m(u;x)\le \epsilon ,$$ 
where $m(\cdot ;x)$ is typically taken to be either the ${\mathrm{\ell}}_{2}$ or ${\mathrm{\ell}}_{\mathrm{\infty}}$ norm, and $\epsilon $ defines the perturbation threshold of interest.
Some adversarial attack methods try to solve the problem posed in (1) without incorporating the loss function used to train the network. For example, Carlini & Wagner attack the logitlayer of a network and solve a different optimization problem, which depends on the choice of norm [8]. Regarding adversarial defense methods, they demonstrated how a significant number of prior defense methods fail because of “gradient obfuscation”, where gradients are small only locally to the image [2]. Another metric of adversarial dissimilarity is the ${\mathrm{\ell}}_{0}$ “norm”, which counts the number of total different pixels between the adversary and the clean image [23, 26]. This is of interest because an adversary might be required to also budget the number of allowed pixels to perturb, while still remaining “imperceptible” to the human eye. For example, the stickerattack [13] is a practical attack with realworld consequences, and does not interfere with every single part of the image.
2.2. Proximal gradient method
Our adversarial attack amounts to a proximal gradient method. Proximal algorithms are a driving force for nonsmooth optimization problems, and are receiving more attention in the deep learning community on a myriad of problems [3, 37, 22, 27]. For a full discussion on this topic, we suggest [6].
We consider the following framework for proximal algorithms, namely a composite minimization problem
(3)  $\underset{x\in \mathcal{E}}{\mathrm{min}}\mathrm{\Phi}(x):=f(x)+g(x)$ 
where $\mathcal{E}$ is a Euclidean space. We make the following assumptions:

•
$g$ is a nondegenerate, closed convex function over $\mathcal{E}$

•
$f$ is nondegenerate, closed function, with $\text{dom}(f)$ convex, and has $L$Lipschitz gradients over the interior of its domain

•
$\text{dom}(g)\subseteq \text{int}(\text{dom}(f))$

•
the solution set, $S$, is nonempty.
Generating a stationary point of (3) amounts to finding a fixed point of the following sequence:
(4)  ${x}^{(k+1)}={\text{Prox}}_{\tau}g({x}^{(k)}\tau \nabla f({x}^{(k)})),$ 
where $\tau >0$ is some step size, and ${\text{Prox}}_{\lambda}g(\cdot )$ is defined as
$${\text{Prox}}_{\lambda}g(x):=\underset{u\in \mathcal{E}}{\mathrm{arg}\mathrm{min}}g(u)+\frac{1}{2\lambda}{\parallel ux\parallel}_{2}^{2}.$$ 
Despite $f$ not being convex, there are still convergence properties we can get from a sequence of iterates generated in this way. The following theorem is a simplified version of what can be found in [6] (Section 10.3 with proof), and is the main motivation for our proposed method.
Theorem 1.
Given the assumptions on (3), let ${\mathrm{\{}{x}^{k}\mathrm{\}}}_{k\mathrm{\ge}\mathrm{0}}$ be the sequence generated by (4), with fixed step size $\tau \mathrm{\in}\mathrm{(}\frac{L}{\mathrm{2}}\mathrm{,}\mathrm{\infty}\mathrm{)}$. Then,

(1)
the sequence $\{\mathrm{\Phi}{({x}^{k}\}}_{k\ge 0}$ is nonincreasing. In addition, $$ if and only if ${x}^{k}$ is not a stationary point of (3);

(2)
$\tau \left({x}^{k}{\text{\mathit{P}\mathit{r}\mathit{o}\mathit{x}}}_{\frac{1}{\tau}}({x}^{k}\frac{1}{\tau}\nabla f({x}^{k}))\right)\to 0$ as $k\to \mathrm{\infty}$;

(3)
all limit points of the sequence ${\{{x}^{k}\}}_{k\ge 0}$ are stationary points of (3).
3. Our method: ProxLogBarrier
Following the previous theoretical ideas, we reformulate (1) in the following way:
(5)  $\underset{u\in \mathcal{X}}{\mathrm{min}}m(u;x)\mathit{\hspace{1em}}\text{s.t.}\mathit{\hspace{1em}}{z}_{\mathrm{max}}{z}_{y}>0.$ 
Here, $Z(\cdot )$ is the model output before the softmax layer that “projects” onto ${\mathrm{\Delta}}_{c}$, and so ${z}_{\mathrm{max}}:={\mathrm{max}}_{i\ne y}{[Z(u)]}_{i}$ and ${z}_{y}:={[Z(u)]}_{y}$. In other words, we want to perturb the clean image minimally in such a way that the model misclassifies it. This problem is difficult as the decision boundary has virtually no exploitable structure. Thus the problem can be relaxed using a logarithmic barrier, a technique often used in traditional optimization [25],
(6)  $\underset{u\in \mathcal{X}}{\mathrm{min}}m(u;x)\lambda \mathrm{log}({z}_{\mathrm{max}}{z}_{y}).$ 
This objective function now includes the constraint that enforces misclassification. In [15], (6) was originally solved via gradient descent, which necessarily assumes that $m(\cdot ;x)$ is at least differentiable. The assumption of differentiability is not a given, and may be impracticable. For example, consider the subgradient of ${\mathrm{\ell}}_{\mathrm{\infty}}$ for an element in ${\mathbb{R}}^{n}$;
$$\partial \parallel \cdot {\parallel}_{\mathrm{\infty}}(x)=\text{sign}({x}_{k}){e}_{k},$$ 
where $k:={\mathrm{arg}\mathrm{max}}_{i}\{{x}_{i}\}$, and ${\{{e}_{i}\}}_{i=1}^{n}$ are the standard basis vectors. At each subgradient step, very little information is obtained. Indeed, in the original LogBarrier paper, a smooth approximation of this norm was used to get around this issue. We shall see that this does not occur with our proposed ProxLogBarrier method.
For brevity, let $\phi (\cdot ):=\mathrm{log}(\cdot )$ and
$$F(u):=\left(\underset{i\ne y}{\mathrm{max}}Z(u)\right){[Z(u)]}_{y}.$$ 
The optimization problem (6) becomes
(7)  $\underset{u\in \mathcal{X}}{\mathrm{min}}m(u;x)+\lambda \phi (F(u)).$ 
One can draw several similarities between (7) and (3). As before, we have no guarantees of convexity on $\phi \circ F$, which is a representation of $f$ in the composite problem, but it is smooth provided $F(\cdot )\in \text{dom}(\phi )$ (that is, $F$ is smooth from a computational perspective). Our dissimilarity metric $m(u;x)$ represents $g$, as it usually has a closedform proximal operator. Thus, we simply turn to the proximal gradient method to solve the minimization problem in (7).
We iteratively find a minimizer for the problem; the attack is outlined in Algorithm 3. Due to the highly nonconvex nature of the decision boundary, we perform a backtracking step to ensure the proposed iterate is in fact adversarial. We remark that the adversarial attack problem is constrained by the imagespace, and thus requires a further projection step back onto the image space (pixels must be in the range [0,1]). In traditional nonconvex optimization, best practice is to also record the “best iterate”, as valleys are likely pervasive throughout the decision boundary. This way, even at some point our gradient sends our image faroff and is unable to return in the remaining iterations, we already have a better candidate. The algorithm begins with a misclassified image, and moves the iterates towards the original image by minimizing the dissimilarity metric. Misclassification is maintained by the log barrier function, which prevents the iterates from crossing the decision boundary. Refer to Figure 1. Contrast this with PGD based algorithms, which begin at or near the original image, and iterate away from the original image. {algorithm} \[email protected]@algorithmic \STATEInput: imagelabel pair $(x,y)$, trained model $f$, adversarial dissimilarity metric $m(\cdot ;x)$ \STATEIntialize hyperparameters: ${K}_{\text{inner}},K\in \mathbb{N}$, and $\mu ,h,{\lambda}_{0}>0,\beta \in (0,1)$. \STATEInitialize ${u}^{(0)}$ to be misclassified, ${w}^{(0)}:={u}^{(0)}$ \FOR$k=0,1,2,\mathrm{\dots},K$ \STATEEvery ${K}_{\text{inner}}$ iterations: $\lambda ={\lambda}_{0}{\beta}^{k}$ \STATE${y}^{(k)}={\text{Prox}}_{\mu m}\left({u}^{(k)}h\lambda \nabla \phi (F({u}^{(k)}))\right)$ \STATE${u}^{(k+1)}=\text{Project}({y}^{(k)};\mathcal{X})$ \STATEBacktrack along line between current and previous iterate until misclassified \IF$$ \STATE${w}^{(k+1)}={u}^{(k+1)}$ \ELSE\STATE${w}^{(k+1)}={w}^{(k)}$ \ENDIF\ENDFOR\STATEOutput: ${w}^{(K)}$
Proximal operators for ${\mathrm{\ell}}_{p}$ dissimilarities
To complete the algorithm, it remains to compute the proximal operator ${\text{Prox}}_{\mu m}(\cdot )$ for various choices of $m$. One can turn to [6] for complete derivations of the proximal operators for the adversarial metrics we are considering, namely ${\mathrm{\ell}}_{1},{\mathrm{\ell}}_{2},{\mathrm{\ell}}_{\mathrm{\infty}}$ norms, and the ${\mathrm{\ell}}_{0}$ cardinality function. Consider measuring the ${\mathrm{\ell}}_{\mathrm{\infty}}$ distance between the clean image and our desired adversarial perturbation:
$$m(u;x):={\parallel ux\parallel}_{\mathrm{\infty}}.$$ 
Due to the Moreau Decomposition Theorem [29], the proximal operator of this function relies on projecting onto the unit ${\mathrm{\ell}}_{1}$ ball:
${\text{Prox}}_{\mu \parallel \cdot x{\parallel}_{\mathrm{\infty}}}(z)$  $=x+{\text{Prox}}_{\mu \parallel \cdot {\parallel}_{\mathrm{\infty}}}(zx)$  
$=x+(zx)\mu {\text{Prox}}_{{\mathbb{B}}_{1}}((zx)/\mu )$  
$=z\mu {\text{Proj}}_{\parallel \cdot {\parallel}_{1}}((zx)/\mu ).$ 
We make use of the algorithm from [12] to perform the projection step, implemented over batches of vectors for efficiency. Similarly, one obtains the proximal operator for ${\mathrm{\ell}}_{1}$ and ${\mathrm{\ell}}_{2}$ via the same theorem,
${\text{Prox}}_{\mu \parallel \cdot x{\parallel}_{1}}(z)=x+{\mathcal{T}}_{\mu}(zx),$  
${\text{Prox}}_{\mu \parallel \cdot x{\parallel}_{2}}(z)=z\mu {\text{Proj}}_{\parallel \cdot {\parallel}_{2}}((zx)/\mu ),$ 
where ${\mathcal{T}}_{\mu}(s):=\text{sign}(s)\mathrm{max}\{s\mu ,0\}$ is the soft thresholding operator. In the case that one wants to minimize the number of perturbed pixels in the adversarial image, one can turn to the counting “norm”, called ${\mathrm{\ell}}_{0}$, which counts the number of nonzero entries in a vector. While this function is nonconvex, the proximal operator still has a closed form:
${P}_{\mu \parallel \cdot x{\parallel}_{0}}(z)$  $=x+{\mathscr{H}}_{\sqrt{2\mu}}(zx)$ 
where ${\mathscr{H}}_{\alpha}(s)=s{\mathrm{\U0001d7cf}}_{\{s>\alpha \}}(s)$ is a hardthresholding operator, and acts componentwise in the case of vector arguments.
Example of non${\mathrm{\ell}}_{p}$ dissimilarity: Total variation
We let $\mathcal{X}$ denote the image space, and for the time being assume the images are grayscale, and let $M$ denote the finitedifference operator on the gridspace defined by the image. Then $M:\mathcal{X}\to \mathcal{X}\times \mathcal{X}$, where
(8)  ${(Mv)}_{i,j}={\left(\begin{array}{c}\hfill {D}_{x}v\hfill \\ \hfill {D}_{y}v\hfill \end{array}\right)}_{i,j}:={\left(\begin{array}{c}\hfill {v}_{i+1,j}{v}_{i,j}\hfill \\ \hfill {v}_{i,j+1}{v}_{i,j}\hfill \end{array}\right)}_{i,j},$ 
where $(i,j)$ are the pixel indices of the image in rowcolumn notation. The anisotropic total variation seminorm is defined by
(9)  ${\parallel v\parallel}_{\text{TV}}:={\parallel Mv\parallel}_{1,1}={\displaystyle \sum _{i,j}}{({D}_{x}v)}_{i,j}+{({D}_{y}v)}_{i,j},$ 
where $\parallel \cdot {\parallel}_{1,1}$ is an induced matrix norm. Heuristically, this is a measure of large changes between neighboring pixels. In practice $Mv$ can be implemented via a convolution. In the case of color images, we aggregate the total variation for each channel. Total variation (TV) is not true norm, in that nonzero images $v$ can have zero TV. In what follows, we omit the distinction and write TVnorm to mean the total variation seminorm. Traditionally, TV has been used in the context of image denoising [30].
What does this mean in the context of adversarial perturbations? The TVnorm of the perturbation will be small when the perturbation has few jumps between pixels. That is, small TVnorm perturbations have locally flat regions. This is primarily because TVnorm is convolutional in nature: the finitedifference gradient operator incorporates neighboring pixel information. We note that this is not the first instance of TV being used as a disimillarity metric [35]; however our approach is quite different and is not derived from a flow. An outline for the proximal operator can be found in [6]; we use a standard package for efficient computation [4, 5]
4. Experimental methodology
Outline
We compare the ProxLogBarrier attack with several other adversarial attacks on MNIST [20], CIFAR10 [18], and ImageNet1k [11]. For MNIST, we use the network described in [26]; on CIFAR10, we use a ResNeXt network [36]; and for ImageNet1k, ResNet50 [17, 10]. We also consider defended models for the aforementioned networks. This is to further benchmark the attack capability of the ProxLogBarrier, and to reaffirm previous work in the area. For defended models, we consider Madrystyle adversarial training for CIFAR10 and MNIST [21]. On ImageNet1k, we use the recently proposed scaleable input gradient regularization for adversarial robustness [14]. We randomly select 1000 (test) images to evaluate performance on MNIST and CIFAR10, and 500 (test) images on ImageNet1k. We consider the same images on their defended counterparts. We note that for ImageNet1k, we consider the problem of Top5 misclassification, where the log barrier is with respect to the following constraint set
$$Z{[u]}_{(5)}Z{[u]}_{(y)}>0$$ 
where $(i)$ denotes the ${i}^{\text{th}}$ largest index.
We compare the ProxLogBarrier attack with a wide range of attack algorithms that are available through the FoolBox adversarial attack library [28]. For perturbations in ${\mathrm{\ell}}_{0}$, we compare against SparseFool [23], Jacobian Saliency Map Attack (JSMA) [26], and Pointwise [31] (this latter attack is blackbox). For ${\mathrm{\ell}}_{2}$ attacks, we consider CarliniWagner’s attack (CW) [8], Projected Gradient Descent (PGD) [19], DeepFool [24], and the original LogBarrier attack [15]. Finally, for ${\mathrm{\ell}}_{\mathrm{\infty}}$ norm perturbations, we consider PGD, DeepFool, and LogBarrier. All hyperparameters are left to their implementation defaults, with the exception of SparseFool, where we used the exact parameters indicated in the paper. We omit the OnePixel attack [32], as [23] showed that this attack is quite weak on MNIST, CIFAR10, and not tractable on ImageNet1k.
Implementation details for our algorithm
When optimizing for ${\mathrm{\ell}}_{2}$ based noise, we initialize the adversarial image with sufficiently large Gaussian noise; for ${\mathrm{\ell}}_{\mathrm{\infty}}$ and ${\mathrm{\ell}}_{0}$ based perturbations, we use uniform noise. For hyperparameters, we used ${\lambda}_{0}=0.1,\beta =0.75,h=0.1,\mu =1$, with $K=900,{K}_{\text{inner}}=30$. We observed some computational drawbacks for ImageNet1k: firstly, the proximal operator for the ${\mathrm{\ell}}_{0}$ norm is far too strict. We decided to use the ${\mathrm{\ell}}_{1}$ norm to induce sparseness in our adversarial perturbation (changing both the prox parameter and the step size to $0.5$). Other parameter changes for the ImageNet1k dataset are that for the proximal parameter in the ${\mathrm{\ell}}_{\mathrm{\infty}}$ case, we set $\mu =3$, and we used 2500 algorithm iterations. Finally, we found that using the softmax layer outputs helps with ImageNet1k attacks against both the defended and undefended network. For TVnorm, perturbations, we set the proximal parameter $\mu =5$, and $K=200$ with ${K}_{\text{inner}}=20$ (far less than before).
Reporting
For perturbations in ${\mathrm{\ell}}_{2}$ and ${\mathrm{\ell}}_{\mathrm{\infty}}$, we report the percent misclassification at various threshold levels that are somewhat standard [34]. Our choices for ${\mathrm{\ell}}_{0}$ distance thresholds were arbitrary, however we supplement with a median perturbation distances on all attack norms to mitigate cherrypicking. For attacks that were unable to successfully perturb at least half the sampled images, we do not report anything. If the attack was able to perturb more than half but not all, we add an asterisk to the median distance. We denote the defended models by “(D)” (recall that for MNIST and CIFAR10, we are using Madry’s adversarial training, and scaleable inputgradient regularization for Imagenet1k).
Perturbations in ${\mathbf{\ell}}_{\mathrm{\U0001d7ce}}$
Result for ${\mathrm{\ell}}_{0}$ perturbations are found in Table 1, with examples available in Figure 2 and Figure 3(b). Across all datasets considered, ProxLogBarrier outperforms all other attack methods, for both defended and undefended networks. It also appears immune to Madrystyle adversarial training on both MNIST and CIFAR10. This is entirely reasonable, for the Madrystyle adversarial training is targeted towards ${\mathrm{\ell}}_{\mathrm{\infty}}$ attacks. In contrast, on ImageNet1k, the defended model trained with inputgradient regularization performs significantly better than the undefended model, even though this defence is not aimed towards ${\mathrm{\ell}}_{0}$ attacks. Neither JSMA or Pointwise scale to networks on ImageNet1k. Pointwise exceeds at smaller images, since it takes less than 1000 iterations to cycle over every pixel and check if it can be zero’d out. We remark that SparseFool was unable to adversarially attack all images, whereas ProxLogBarrier always succeeded.
Perturbations in ${\mathbf{\ell}}_{\mathbf{\infty}}$
Results for ${\mathrm{\ell}}_{\mathrm{\infty}}$ perturbations are found in Table 2. Our attack stands out on MNIST, in both the defended and undefended case. On CIFAR10, our attack is best on the undefended network, and only slightly worse than PGD when adversarially defended. On ImageNet1k, our method suffers dramatically. This is likely due to very poor decision boundaries with respect to this norm ${\mathrm{\ell}}_{\mathrm{\infty}}$, as our method will necessarily be better when the boundaries are not muddled. PGD does not focus on the decision boundaries explicitly, thus has more room to find something adversarial quickly.
Perturbations in ${\mathbf{\ell}}_{\mathrm{\U0001d7d0}}$
Results for perturbations measured in Euclidean distance are found in Table 3. For MNIST and ImageNet1k, on both defended and undefended networks, our attack performs better than all other methods, both in median distance and at a given perturbation norm threshold. On CIFAR10, we are best on undefended but lose to CW in the defended case. However, the CW attack did not scale to ImageNet1k using the implementation in the FoolBox attack library.
Perturbations in the TVnorm
To our knowledge, there are no other TVnorm atacks against which to compare our methods. However, we present the median total variation across the data in question, and a handful of pictures for illustration. On MNIST, adversarial images with minimal total variation are often as expected: nearflat perturbations or very few pixels perturbed (see Figure 2(a)). For CIFAR10 and ImageNet1k, we have found that adversarial images with small TVnorm have an adversarial “tint” on the image: they appear nearly identical to the original, with a small color shift. When the adversary is not a tint, perturbations are highly localized or localized in several regions. See for example Figures 2(b) and 3(a).
Algorithm runtime
We strove to implement ProxLogBarrier so that it could be run in a reasonable amount of time. For that reason, ProxLogBarrier was implemented to work over a batch of images. Using one consumer grade GPU, we can comfortably attack several MNIST and CIFAR10 images simultaneously, but only one ImageNet1k image at a given time. We report our algorithm runtimes in Table 5. Algorithms implemented from the FoolBox repository were not written to take advantage of the GPU, hence we omit runtime comparisons. Heuristically speaking, PGD is one of the faster algorithms, whereas CW, SparseFool, and DeepFool are slower. We omit the computational complexity for minimizing total variation since the proximal operator is coded in C, and not Python.
We are not surprised that our attack in ${\mathrm{\ell}}_{0}$ takes longer than the other norms; this is likely due to the backtracking step to ensure misclassification of the iterate. On ImageNet1k, the ProxLogBarrier attack in the ${\mathrm{\ell}}_{\mathrm{\infty}}$ metric is quite slow due to the projection step onto the ${\mathrm{\ell}}_{1}$ ball, which is $\mathcal{O}(n\mathrm{log}(n))$, where $n$ is the input dimension size [12].
5. Conclusion
We have presented a concise framework for generating adversarial perturbations by incorporating the proximal gradient method. We have expanded upon the LogBarrier attack, which was originally only effective in ${\mathrm{\ell}}_{2}$ and ${\mathrm{\ell}}_{\mathrm{\infty}}$ norms, by addressing the ${\mathrm{\ell}}_{0}$ norm case and the total variation seminorm. Thus we have proposed a method unifying all three common perturbation scenarios. Our approach requires fewer hyperparameter tweaks than LogBarrier, and performs significantly better than many attack methods we compared against, both on defended and undefended models, and across all norm choices. We highlight that our method is, to our knowledge, the best choice for perturbations measured in ${\mathrm{\ell}}_{0}$, compared to all other methods available in FoolBox. We also perform better than all other attacks considered on the MNIST network with in the median distance and in commonly reported thresholds. The proximal gradient method points towards new forms of adversarial attacks, such as those measured in the TVnorm, provided the attack’s dissimilarity metric has a closed proximal form.
References
 [1] (2018) ADef: an iterative algorithm to construct adversarial deformations. CoRR abs/1804.07729. External Links: Link, 1804.07729 Cited by: §1.
 [2] (2018) Obfuscated gradients give a false sense of security: circumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 1015, 2018, pp. 274–283. External Links: Link Cited by: §2.1.
 [3] (2018) ProxQuant: quantized neural networks via proximal operators. CoRR abs/1810.00861. External Links: Link, 1810.00861 Cited by: §2.2.
 [4] (2011) Fast newtontype methods for total variation regularization.. In ICML, L. Getoor and T. Scheffer (Eds.), pp. 313–320. Cited by: §3.
 [5] (2018) Modular proximal optimization for multidimensional totalvariation regularization. Journal of Machine Learning Research 19 (56), pp. 1–82. External Links: Link Cited by: §3.
 [6] (2017) Firstorder methods in optimization. Cited by: §2.2, §2.2, §3, §3.
 [7] (2017) Decisionbased adversarial attacks: reliable attacks against blackbox machine learning models. arXiv preprint arXiv:1712.04248. Cited by: §1.
 [8] (2016) Towards evaluating the robustness of neural networks. CoRR abs/1608.04644. External Links: Link, 1608.04644 Cited by: §1, §2.1, §4.
 [9] (2019) Boundary attack++: queryefficient decisionbased adversarial attack. CoRR abs/1904.02144. External Links: Link, 1904.02144 Cited by: §1.
 [10] (2018) Analysis of dawnbench, a timetoaccuracy machine learning performance benchmark. CoRR abs/1806.01427. External Links: Link, 1806.01427 Cited by: §4.
 [11] (2009) ImageNet: A largescale hierarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 2025 June 2009, Miami, Florida, USA, pp. 248–255. External Links: Link, Document Cited by: §4.
 [12] (2008) Efficient projections onto the l1ball for learning in high dimensions. In Proceedings of the 25th International Conference on Machine Learning, ICML ’08, New York, NY, USA, pp. 272–279. External Links: ISBN 9781605582054, Link, Document Cited by: §3, §4.
 [13] (2017) Robust physicalworld attacks on deep learning models. arXiv preprint arXiv:1707.08945. Cited by: §1, §2.1.
 [14] (2019) Scaleable input gradient regularization for adversarial robustness. arXiv preprint arXiv:1905.11468. Cited by: §4.
 [15] (2019) The logbarrier adversarial attack: making effective use of decision boundary information. IEEE International Conference on Computer Vision (ICCV). Cited by: §1, §3, §4.
 [16] (2014) Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. Cited by: §1, §1.
 [17] (2016) Identity mappings in deep residual networks. In Computer Vision – ECCV 2016, B. Leibe, J. Matas, N. Sebe, and M. Welling (Eds.), Cham, pp. 630–645. Cited by: §4.
 [18] (2009) Learning multiple layers of features from tiny images. Cited by: §4.
 [19] (2016) Adversarial examples in the physical world. CoRR abs/1607.02533. External Links: Link, 1607.02533 Cited by: §1, §4.
 [20] (1999) Object recognition with gradientbased learning. In Shape, Contour and Grouping in Computer Vision, pp. 319. External Links: Link, Document Cited by: §4.
 [21] (2017) Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083. Cited by: §1, §4.
 [22] (2017) Learning proximal operators: using denoising networks for regularizing inverse imaging problems. CoRR abs/1704.03488. External Links: Link, 1704.03488 Cited by: §2.2.
 [23] (2018) SparseFool: a few pixels make a big difference. CoRR abs/1811.02248. External Links: Link, 1811.02248 Cited by: §1, §2.1, §4, footnote 1.
 [24] (2015) DeepFool: a simple and accurate method to fool deep neural networks. CoRR abs/1511.04599. External Links: Link, 1511.04599 Cited by: §1, §4.
 [25] (2006) Numerical optimization. Springer Science & Business Media. Cited by: §3.
 [26] (2015) The limitations of deep learning in adversarial settings. CoRR abs/1511.07528. External Links: Link, 1511.07528 Cited by: §2.1, §4, §4.
 [27] (201809–11 Apr) Catalyst for gradientbased nonconvex optimization. In Proceedings of the TwentyFirst International Conference on Artificial Intelligence and Statistics, A. Storkey and F. PerezCruz (Eds.), Proceedings of Machine Learning Research, Vol. 84, Playa Blanca, Lanzarote, Canary Islands, pp. 613–622. Cited by: §2.2.
 [28] (2017) Foolbox v0.8.0: A python toolbox to benchmark the robustness of machine learning models. CoRR abs/1707.04131. External Links: Link, 1707.04131 Cited by: §4.
 [29] (2009) Variational analysis. Vol. 317, Springer Science & Business Media. Cited by: §3.
 [30] (1992) Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena 60 (14), pp. 259–268. Cited by: §3.
 [31] (2018) Robust perception through analysis by synthesis. CoRR abs/1805.09190. External Links: Link, 1805.09190 Cited by: §4.
 [32] (2017) One pixel attack for fooling deep neural networks. CoRR abs/:1710.08864. Cited by: §4.
 [33] (2014) Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 1416, 2014, Conference Track Proceedings, External Links: Link Cited by: §1.
 [34] (2018) Robustness may be at odds with accuracy. arXiv preprint arXiv:1805.12152. Cited by: §1, §4.
 [35] (2018) Spatially transformed adversarial examples. CoRR abs/1801.02612. External Links: Link Cited by: §3.
 [36] (2016) Aggregated residual transformations for deep neural networks. CoRR abs/1611.05431. External Links: Link, 1611.05431 Cited by: §4.
 [37] (2019) ADMM attack: an enhanced adversarial attack for deep neural networks with undetectable distortions. In Proceedings of the 24th Asia and South Pacific Design Automation Conference, ASPDAC ’19, New York, NY, USA, pp. 499–505. External Links: ISBN 9781450360074, Link, Document Cited by: §2.2.