STRUCTURED ADVERSARIAL ATTACK: TOWARDS GENERAL IMPLEMENTATION AND BETTER INTERPRETABILITY
Year: 2019

Abstract:
When generating adversarial examples to attack deep neural networks (DNNs), `p norm of the added perturbation is usually used to measure the similarity between original image and adversarial example. However, such adversarial attacks perturbing the raw input spaces may fail to capture structural information hidden in the input. This work develops a more general attack model, i.e., the structured attack (StrAttack), which explores group sparsity in adversarial perturbations by sliding a mask through images aiming for extracting key spatial structures. An ADMM (alternating direction method of multipliers)-based framework is proposed that can split the original problem into a sequence of analytically solvable subproblems and can be generalized to implement other attacking methods. Strong group sparsity is achieved in adversarial perturbations even with the same level of `p-norm distortion (p ∈ {1, 2,∞}) as the stateof-the-art attacks. We demonstrate the effectiveness of StrAttack by extensive experimental results on MNIST, CIFAR-10 and ImageNet. We also show that StrAttack provides better interpretability (i.e., better correspondence with discriminative image regions) through adversarial saliency map (Papernot et al., 2016b) and class activation map (Zhou et al., 2016). Our code is available at https://github.com/KaidiXu/StrAttack.

text: 1 INTRODUCTION
Deep learning achieves exceptional successes in domains such as image recognition (He et al., 2016; Geifman & ElYaniv, 2017), natural language processing (Hinton et al., 2012; Harwath et al., 2016), medical diagnostics (Chen et al., 2016; Shi et al., 2018) and advanced control (Silver et al., 2016; Fu et al., 2017). Recent studies (Szegedy et al., 2013; Goodfellow et al., 2014; Nguyen et al., 2015; Kurakin et al., 2016; Carlini & Wagner, 2017) show that DNNs are vulnerable to adversarial attacks implemented by generating adversarial examples, i.e., adding well-designed perturbations to original legal inputs. Delicately crafted adversarial examples can mislead a DNN to recognize them as any target image label, while the perturbations appears unnoticeable to human eyes. Adversarial attacks against ∗Equal contribution
DNNs not only exist in theoretical models but also pose potential security threats to the real world (Kurakin et al., 2016; Evtimov et al., 2017; Papernot et al., 2017). Several explanations are proposed to illustrate why there exist adversarial examples to DNNs based on hypotheses such as model linearity and data manifold (Goodfellow et al., 2014; Gilmer et al., 2018). However, little is known to their origins, and convincing explanations remain to be explored.
Besides achieving the goal of (targeted) mis-classification, an adversarial example should be as “similar” to the original legal input as possible to be stealthy. Currently, the similarity is measured by the `p norm (p = 0, 1, 2,∞) of the added perturbation (Szegedy et al., 2013; Carlini & Wagner, 2017; Chen et al., 2017b;a), i.e., `p norm is being minimized when generating adversarial example. However, measuring the similarity between the original image and its adversarial example by `p norm is neither necessary nor sufficient (Sharif et al., 2018). Besides, no single measure can be perfect for human perceptual similarity (Carlini & Wagner, 2017) and such adversarial attacks may fail to capture key information hidden in the input such as spatial structure or distribution. Spurred by that, this work implements a new attack model i.e., structured attack (StrAttack) that imposes group sparsity on adversarial perturbations by extracting structures from the inputs. As shown in Fig. 1, we find that StrAttack identifies minimally sufficient regions that make attacks successful, but without incurring extra pixel-level perturbation power. The major contributions are summarized as below.
• (Structure-driven attack) This work is the first attempt towards exploring group-wise sparse structures when implementing adversarial attacks, but without losing `p distortion performance when compared to state-of-the-art attacking methods.
• (Generality) We show that the proposed attack model covers many norm-ball based attacks such as C&W (Carlini & Wagner, 2017) and EAD (Chen et al., 2017a).
• (Efficient implementation) We develop an efficient algorithm to generate structured adversarial perturbations by leveraging the alternating direction method of multipliers (ADMM). We show that ADMM splits the original complex problem into subproblems, each of which can be solved analytically. Besides, we show that ADMM can further be used to refine an arbitrary adversarial attack under the fixed sparse structure.
• (Interpretability) The generated adversarial perturbations demonstrate clear correlations and interpretations between original and target images. With the aid of adversarial saliency map (Papernot et al., 2016b) and class activation map (Zhou et al., 2016), we show that the obtained group-sparse adversarial patterns better shed light on the mechanisms of adversarial perturbations to fool DNNs.
Related work Many works studied norm-ball constrained adversarial attacks. For example, FGM (Goodfellow et al., 2014) and IFGSM (Kurakin et al., 2017) attack methods were proposed to maximize the classification error subject to `∞-norm based distortion constraints. Moreover, L-BFGS (Szegedy et al., 2013) and C&W (Carlini & Wagner, 2017) attacks found an adversarial example by minimizing its `2-norm distortion. By contrast, JSMA (Papernot et al., 2016b) and one-pixel (Su et al., 2017) attacks attempted to generate adversarial examples by perturbing the minimum number of pixels, namely, minimizing the `0 norm of adversarial perturbations. Different from the above norm-ball constrained attacks, some works (Karmon et al., 2018; Brown et al., 2017) crafted adversarial examples by adding noise patches. However, the resulting adversarial perturbations are no longer imperceptible to humans. Here we argue that imperceptibility could be important since it helps us to understand how/why DNNs are vulnerable to adversarial attacks while perturbing natural examples just by indistinguished adversarial noise.
In the aforementioned norm-ball constrained adversarial attacks, two extremely opposite principles have been applied: C&W attack (or `∞ attacks) seeks the minimum image-level distortion but allows to modify all pixels; one-pixel attack only perturbs a few pixels but suffers a high pixel-level distortion. Both attacking principles might lead to a high noise visibility due to perturbing too many pixels or perturbing a few pixels too much. In this work, we wonder if there exists a more effective attack that can be as successful as existing attacks but achieves a tradeoff between the perturbation power and the number of perturbed pixels. We will show that the proposed StrAttack is able to identify sparse perturbed regions that make attacks successful, but without incurring extra pixel-level
perturbations. It is also worth mentioning that one-pixel attack has much lower attack success rate on ImageNet than C&W attack and StrAttack.
In addition to adversarial attacks, many defense works have been proposed. Examples include defensive distillation (Papernot et al., 2016c) that distills the original DNN and introduces temperature into the softmax layer, random mask (Anonymous, 2019) that modifies the DNN structures by randomly removing certain neurons before training, adversarial training through enlarging the training dataset with adversarial examples, and robust adversarial training (Madry et al., 2017; Sinha et al., 2018) through the min-max optimization. It is commonly known that the robust adversarial training method ensures the strongest defense performance against adversarial attacks on MNIST and CIFAR-10. In this work, we will evaluate the effectiveness of StrAttack to three defense methods, a) defensive distillation (Papernot et al., 2016c), b) adversarial training via data augmentation (Tramèr et al., 2018) and c) robust adversarial training (Madry et al., 2017).
Although the adversarial attack and defense have attracted an increasing amount of attention, the visual explanation on adversarial perturbations is less explored since the distortion power is minimized and the resulting adversarial effects become imperceptible to humans. The work (Dong et al., 2017) attempted to understand how the internal representations of DNNs are affected by adversarial examples. However, only an ensemble-based attack was considered, which fails to distinguish the effectiveness of different norm-ball constrained adversarial attacks. Unlike (Dong et al., 2017), we employ the interpretability tools, adversarial saliency map (ASM) (Papernot et al., 2016b) and class activation map (CAM) (Zhou et al., 2016) to measure the effectiveness of different attacks in terms of their interpretability. Here ASM provides sensitivity analysis for pixel-level perturbation’s impact on label classification, and CAM localizes class-specific image discriminative regions (Xiao et al., 2018). We will show that the sparse adversarial pattern obtained by StrAttack offers a great interpretability through ASM and CAM compared with other norm-ball constrained attacks.

heading: 2 STRUCTURED ATTACK: EXPLORE GROUP STRUCTURES FROM IMAGES
text: In the section, we introduce the concept of StrAttack, motivated by the question: ‘what possible structures could adversarial perturbations have to fool DNNs?’ Our idea is to divide an image into sub-groups of pixels and then penalize the corresponding group-wise sparsity. The resulting sparse groups encode minimally sufficient adversarial effects on local structures of natural images.
Let ∆ ∈ RW×H×C be an adversarial perturbation added to an original image X0, where W × H gives the spatial region, and C is the depth, e.g., C = 3 for RGB images. To characterize the local structures of ∆, we introduce a sliding maskM with stride S and size r × r × C. When S = 1, the mask moves one pixel at a time; When S = 2, the mask jumps 2 pixels at a time while sliding. By adjusting the stride S and the mask size r, different group splitting schemes can be obtained. If S < r, the resulting groups will contain overlapping pixels. By contrast, groups will become non-overlapped when S = r.
A sliding maskM finally divides ∆ into a set of groups {∆Gp,q} for p ∈ [P ] and q ∈ [Q], where P = (W − r)/S + 1, Q = (H − r)/S + 1, and [n] denotes the integer set {1, 2, . . . , n}. Given the groups {∆Gp,q}, the group sparsity can be characterized through the following sparsity-inducing function (Yuan & Lin, 2006; Bach et al., 2012; Liu et al., 2015), motivated by the problem of group Lasso (Yuan & Lin, 2006):
g(∆) = ∑P p=1 ∑Q q=1 ‖∆Gp,q‖2, (1)
where ∆Gp,q denotes the set of pixels of ∆ indexed by Gp,q , and ‖ · ‖2 is the `2 norm. We refer readers to Fig. A1 for an illustrative example of our concepts on groups and group sparsity.

heading: 3 STRUCTURED ADVERSARIAL ATTACK WITH ADMM
text: In this section, we start by proposing a general framework to generate prediction-evasive adversarial examples, where the adversary relies only on gradients of the loss function with respect to inputs of DNNs. Our model takes into account both commonly-used adversarial distortion metrics and the proposed group-sparsity regularization that encodes spatial structures in attacks. We show that the process of generating structured adversarial examples leads to an optimization problem that is
difficult to solve using the existing optimizers Adam (for C&W attack) and FISTA (for EAD attack) (Carlini & Wagner, 2017; Chen et al., 2017a). To circumvent this challenge, we develop an efficient optimization method via alternating direction method of multipliers (ADMM).
Given an original image x0 ∈ Rn, we aim to design the optimal adversarial perturbation δ ∈ Rn so that the adversarial example (x0 + δ) misleads DNNs trained on natural images. Throughout this paper, we use vector representations of the adversarial perturbation ∆ and the original image X0 without loss of generality. A well designed perturbation δ can be obtained by solving optimization problems of the following form,
minimize δ f(x0 + δ, t) + γD(δ) + τg(δ)
subject to (x0 + δ) ∈ [0, 1]n, ‖δ‖∞ ≤ , (2)
where f(x, t) denotes the loss function for crafting adversarial example given a target class t, D(δ) is a distortion function that controls the perceptual similarity between a natural image and a perturbed image, g(δ) = ∑P p=1 ∑Q q=1 ‖δGp,q‖2 is given by (1), and ‖ · ‖p signifies the `p norm. In problem (2), the ‘hard’ constraints ensure the validness of created adversarial examples with - tolerant perturbed pixel values. And the non-negative regularization parameters γ and τ place our emphasis on the distortion of an adversarial example (to an original image) and group sparsity of adversarial perturbation. Tuning the regularization parameters will be discussed in Appendix F.
Problem (2) gives a quite general formulation for design of adversarial examples. If we remove the group-sparsity regularizer g(δ) and the `∞ constraint, problem (2) becomes the same as the C&W attack (Carlini & Wagner, 2017). More specifically, if we further set the distortion function D(δ) to the form of `0, `2 or `∞ norm, then we obtain C&W `0, `2 or `∞ attack. If D(δ) is specified by the elastic-net regularizer, then problem (2) becomes the formulation of EAD attack (Chen et al., 2017a).
In this paper, we specify the loss function of problem (2) as below, which yields the best known performance of adversaries (Carlini & Wagner, 2017),
f(x0 + δ, t) = c ·max{max j 6=t Z(x0 + δ)j − Z(x0 + δ)t,−κ}, (3)
where Z(x)j is the jth element of logits Z(x), representing the output before the last softmax layer in DNNs, and κ is a confidence parameter that is usually set to zero if the attack transferability is not much cared. We choose D(δ) = ‖δ‖22 for a fair comparison with the C&W `2 adversarial attack. In this section, we assume that {Gp,q} are non-overlapping groups, i.e., Gp,q ∩ Gp′,q′ = ∅ for q 6= q′ or p 6= p′. The overlapping case will be studied in the next section. The presence of multiple non-smooth regularizers and ‘hard’ constraints make the existing optimizers Adam and FISTA (Carlini & Wagner, 2017; Chen et al., 2017a; Kingma & Ba, 2015; Beck & Teboulle, 2009) inefficient for solving problem (2). First, the subgradient of the objective function of problem (2) is difficult to obtain especially when {Gp,q} are overlapping groups. Second, it is impossible to compute the proximal operations required for FISTA with respect to all non-smooth regularizers and ‘hard’ constraints. Different from the existing work, we show that ADMM, a firstorder operator splitting method, helps us to split the original complex problem (2) into a sequence of subproblems, each of which can be solved analytically.
We reformulate problem (2) in a way that lends itself to the application of ADMM,
minimize δ,z,w,y
f(z + x0) + γD(δ) + τ ∑PQ i=1 ‖yDi‖2 + h(w)
subject to z = δ, z = y, z = w, (4)
where z, y and w are newly introduced variables, for ease of notation let D(q−1)P+p = Gp,q , and h(w) is an indicator function with respect to the constraints of problem (2),
h(w) = { 0 if (x0 + w) ∈ [0, 1]n, ‖w‖∞ ≤ , ∞ otherwise. (5)
ADMM is performed by minimizing the augmented Lagrangian of problem (4), L(z, δ,y,w,u,v, s) = f(z + x0) + γD(δ) + τ ∑PQ i=1 ‖yDi‖2 + h(w) + u
T (δ − z) +vT (y − z) + sT (w − z) + ρ
2 ‖δ − z‖22 + ρ2‖y − z‖ 2 2 + ρ 2 ‖w − z‖22,
(6)
where u, v and s are Lagrangian multipliers, and ρ > 0 is a given penalty parameter. ADMM splits all of optimization variables into two blocks and adopts the following iterative scheme,
{δk+1,wk+1,yk+1} = argmin δ,w,y L(δ, zk,w,y,uk,vk, sk), (7)
zk+1 = argmin z L(δk+1, z,wk+1,yk+1,uk,vk, sk), (8) u k+1 = uk + ρ(δk+1 − zk+1),
vk+1 = vk + ρ(yk+1 − zk+1), sk+1 = sk + ρ(wk+1 − zk+1),
(9)
where k is the iteration index, steps (7)-(8) are used for updating primal variables, and the last step (9) is known as the dual update step. We emphasize that the crucial property of the proposed ADMM approach is that, as we demonstrate in Proposition 1, the solution to problem (7) can be found in parallel and exactly.
Proposition 1 When D(δ) = ‖δ‖22, the solution to problem (7) is given by
δk+1 = ρρ+2γa, (10)
[wk+1]i = { min{1− [x0]i, } bi > min{1− [x0]i, } max{−[x0]i,− } bi < max{−[x0]i,− } bi otherwise, for i ∈ [n], (11)
[yk+1]Di = ( 1− τρ‖[c]Di‖2 ) + [c]Di , i ∈ [PQ], (12)
where a := zk − uk/ρ, b := zk − sk/ρ, c := zk − vk/ρ, (x)+ = x if x ≥ 0 and 0 otherwise, [x]i denotes the ith element of x, and [x]Di denotes the sub-vector of x indexed by Di.
Proof: See Appendix B.
It is clear from Proposition 1 that introducing auxiliary variables does not increase the computational complexity of ADMM since (10)-(12) can be solved in parallel. Moreover, if another distortion metric (different from D(δ) = ‖δ‖22) is used, then ADMM only changes at the δ-step (10). We next focus on the z-minimization step (8), which can be equivalently transformed into
minimize z
f(x0 + z) + ρ 2 ‖z− a′‖22 + ρ 2 ‖z− b′‖22 + ρ 2 ‖z− c′‖22, (13)
where a′ := δk+1 + uk/ρ, b′ := wk+1 + sk/ρ, and c′ := yk+1 + vk/ρ. We recall that attacks studied in this paper belongs to ‘first-order’ adversaries (Madry et al., 2017), which only have access to gradients of the loss function f . Spurred by that, we solve problem (13) via a linearization technique that is commonly used in stochastic/online ADMM (Ouyang et al., 2013; Suzuki, 2013; Liu et al., 2018) or linearized ADMM (Boyd et al., 2011; Liu et al., 2017). Specifically, we replace the function f with its first-order Taylor expansion at the point zk by adding a Bregman divergence term (ηk/2)‖z− zk‖22. As a result, problem (13) becomes
minimize z (∇f(zk + x0))T (z− zk) + ηk 2 ‖z− zk‖22 + ρ 2 ‖z− a′‖22
+ ρ 2 ‖z− b′‖22 + ρ 2 ‖z− c′‖22,
(14)
where 1/ηk > 0 is a given decaying parameter, e.g., ηk = α √ k for some α > 0, and the Bregman divergence term stabilizes the convergence of z-minimization step. It is clear that problem (14) yields a quadratic program with the closed-form solution
zk+1 = (1/ (ηk + 3ρ)) ( ηkz k + ρa + ρb + ρc−∇f(zk + x0) ) . (15)
In summary, the proposed ADMM algorithm alternatively updates (7)-(9), which yield closed-form solutions given by (10)-(12) and (15). The convergence of linearized ADMM for nonconvex optimization was recently proved by (Liu et al., 2017), and thus provides theoretical validity of our approach. Compared to the existing solver for generation of adversarial examples (Carlini & Wagner, 2017; Papernot et al., 2016b), our algorithm offers two main benefits, efficiency and generality. That is, the computations for every update step are efficiently carried out, and our approach can be applicable to a wide class of attack formulations.

heading: 4 OVERLAPPING GROUP AND REFINED STRATTACK
text: In this section, we generalize our proposed ADMM solution framework to the case of generating adversarial perturbations with overlapping group structures. We then turn to an attack refining model under fixed sparse structures. We will show that both extensions can be unified under the ADMM framework. In particular, the refined approach will allow us to gain deeper insights on the structural effects on adversarial perturbations.

heading: 4.1 OVERLAPPING GROUP STRUCTURE
text: We recall that groups {Di} (also denoted by {Gp,q}) studied in Sec. 3 could be overlapped with each other; see an example in Fig. A1. Therefore, {Di} is in general a cover rather than a partition of [n]. To address the challenge in coupled group variables, we introduce multiple copies of the variable y in problem (4), and achieve the following modification
minimize δ,z,w,{yi}
f(z + x0) + γD(δ) + τ ∑PQ i=1 ‖yi,Di‖2 + h(w)
subject to z = δ, z = w, z = yi, i ∈ [PQ], (16)
where compared to problem (4), there exist PQ variables yi ∈ Rn for i ∈ [PQ], and yi,Di denotes the subvector of yi with indices given by Di. It is clear from (16) that groups {Di} become nonoverlapped since each of them lies in a different copy yi. The ADMM algorithm for solving problem (16) maintains a similar procedure as (7)-(9) except y-step (12) and z-step (15); see Proposition 2.
Proposition 2 Given the same condition of Proposition 1, the ADMM solution to problem (16) involves the δ-step same as (10), the w-step same as (11), and two modified y- and z-steps, [ yk+1i ] Di = ( 1− τ ρ‖[ci]Di‖2 ) + [ci]Di[
yk+1i ] [n]/Di = [ci][n]/Di
, for i ∈ [PQ], (17)
zk+1 = (1/ (ηk + 2ρ+ PQρ)) ( ηkz k + ρa′ + ρb′ + ρ ∑PQ i=1 c ′ i −∇f(zk + x0) ) , (18)
where ci := zk − vki /ρ, vi is the Lagrangian multiplier associated with equality constraint yi = z, similar to (9) we obtain vk+1i = v k i +ρ(y
k+1−zk+1), [n]/Di denotes the difference of sets [n] and Di, a′ and b′ have been defined in (13), and c′i = y k+1 i + v k i /ρ.
Proof: See Appendix C.
We note that updating PQ variables {yi} is decomposed as shown in (17). However, the side effect is the need of PQ times more storage space than the y-step (12) when groups are non-overlapped.

heading: 4.2 REFINED STRATTACK UNDER FIXED SPARSE PATTERN
text: The approaches proposed in Sec. 3 and Sec. 4.1 help us to identify structured sparse patterns in adversarial perturbations. This section presents a method to refine structured attacks under fixed group sparse patterns. Let δ∗ denote the solution to problem (2) solved by the proposed ADMM method. We define a σ-sparse perturbation δ via δ∗,
δi = 0 if δ∗i ≤ σ, for any i ∈ [n], (19)
where a hard thresholding operator is applied to δ∗ with tolerance σ. Our refined model imposes the fixed σ-sparse structure (19) into problem (2). This leads to
minimize δ f(x0 + δ) + γD(δ) subject to (x0 + δ) ∈ [0, 1]n, ‖δ‖∞ ≤ δi = 0, if i ∈ Sσ,
(20)
where Sσ is defined by (19), i.e., Sσ := {j | δ∗j ≤ σ, j ∈ [n]}. Compared to problem (2), the groupsparse penalty function is eliminated as it has been known as a priori. With the priori knowledge of group sparsity, problem (20) is formulated to optimize and refine the non-zero groups, thus achieving better performance on highlighting and exploring the perturbation structure. Problem (20) can be solved using ADMM, and its solution is presented in Proposition 3.
Proposition 3 The ADMM solution to problem (20) is given by
[δk+1]i =  0 i ∈ Sσ min{1− [x0]i , } ρ 2γ+ρ ai > min{1− [x0]i , }, i /∈ Sσ max{− [x0]i ,− } ρ 2γ+ρ ai < max{− [x0]i ,− }, i /∈ Sσ ρ
2γ+ρ ai otherwise,
(21)
[zk+1]i = { 0 i ∈ Sσ 1/(ηk + ρ) [ ηk[z k]i + ρ[a ′]i − [∇f(zk + x0)]i ] i /∈ Sσ,
(22)
for i ∈ [n], where z = δ is the introduced auxiliary variable similar to (4), a := δk+1 − uk/ρ, a′ := δk+1+uk/ρ, uk+1 = uk+ ρ(δk+1− zk+1), and ρ and ηk have been defined in (6) and (14). The ADMM iterations can be initialized by δ∗, the known solution to problem (2).
Proof: See Appendix D.

heading: 5 EMPIRICAL PERFORMANCE OF STRATTACK
text: We evaluate the performance of the proposed StrAttack on three image classification datasets, MNIST (Lecun et al., 1998), CIFAR-10 (Krizhevsky & Hinton, 2009) and ImageNet (Deng et al., 2009). To make fair comparison with the C&W `2 attack (Carlini & Wagner, 2017), we use `2 norm as the distortion function D(δ) = ‖δ‖22. And we also compare with FGM (Goodfellow et al., 2014) and IFGSM `2 attacks (Kurakin et al., 2017) as a reference. We evaluate attack success rate (ASR)1 as well as `p distortion metrics for p ∈ {0, 1, 2,∞}. The detailed experiment setup is presented in Appendix F. Our code is available at https://github.com/KaidiXu/StrAttack.
For each attack method on MNIST or CIFAR-10, we choose 1000 original images from the test dataset as source and each image has 9 target labels. So a total of 9000 adversarial examples are generated for each attack method. On ImageNet, each attack method tries to craft 900 adverdarial examples with 100 random images from the test dataset and 9 random target labels for each image.
Fig. 2 compares adversarial examples generated by StrAttack and C&W attack on each dataset. We observe that the perturbation of the C&W attack has poor group sparsity, i.e., many non-zeros groups with small magnitudes. However, the ASR of the C&W attack is quite sensitive to these small perturbations. As applying a threshold to have the same `0 norm as our attack, we find that only 6.7% of adversarial examples generated from C&W attack remain valid. By contrast, StrAttack is able to highlight the most important group structures (local regions) of adversarial perturbations without attacking other pixels. For example, StrAttack misclassifies a natural image (4 in MNIST) as an incorrect label 3. That is because the pixels that appears in the structure of 3 are more significantly perturbed by our attack; see the top right plots of Fig. 2. Furthermore, the ‘goose-sorrel’ example shows that misclassification occurs when we just perturb a small number of non-sparse group regions on goose’s head, which is more consistent with human perception. We refer readers to Appendix G for more results.
By quatitatively analysis, we report `p norms and ASR in Table 1 for p ∈ {0, 1, 2,∞}. We show that StrAttack perturbs much fewer pixels (smaller `0 norm), but it is comparable to or even better than other attacks in terms of `1, `2, and `∞ norms. Specifically, the FGM attack yields the worst performance in both ASR and `p distortion. On MNIST and CIFAR-10, StrAttack outperforms other attacks in `0, `1 and `∞ distortion. On ImageNet, StrAttack outperforms C&W attack in `0 and `1 distortion. Since the C&W attacking loss directly penalizes the `2 norm, it often causes smaller `2 distortion than StrAttack. We also observe that the overlapping case leads to the adversarial perturbation of less sparsity (in terms of `0 norm) compared to the non-overlapping case. This is not surprising, since the sparsity of the overlapping region is controlled by at least two groups. However, compared to C&W attack, the use of overlapping groups in StrAttack still yields sparser perturbations. Unless specified otherwise, we focus on the case of non-overlapping groups to generate the most sparse adversarial perturbations. We highlight that although a so-called one-pixel attack (Su et al., 2017) also yields very small `0 norm, it is at the cost of very large `∞ distortion. Unlike one-pixel attack, StrAttack achieves the sparsity without losing the performance of `∞, `1 and `2 distortion.
Furthermore, we compare the performance of StrAttack with the C&W `∞ attack and IFGSM while attacking the robust model (Madry et al., 2017) on MNIST. We remark that all the considered attack
1The percentage of adversarial examples that successfully fool DNNs.
Original Image: 4Add perturbation Add perturbationTarget: 3 Target: 3
Original Image: gooseTarget: sorrel Target: sorrel
Original Image: horseTarget: airplane Target: airplane
0.04
0.1
methods are performed under the same `∞-norm based distortion constraint with an upper bound ∈ {0.1, 0.2, 0.3, 0.4}. Here we obtain a (refined) StrAttack subject to ‖δ‖∞ ≤ by solving problem (20) at γ = 0. In Table 2, we demonstrate the ASR and the number of perturbed pixels for various attacks over 5000 (untargeted) adversarial examples. The ASR define as the proportion of the final perturbation results less than given ∈ {0.1, 0.2, 0.3, 0.4} bound over number of test images. Here an successful attack is defined by an attack that can fool DNNs and meets the `∞ distortion constraint. As we can see, StrAttack can achieve the similar ASR compared to other attack methods, however, it perturbs a much less number of pixels. Next, we evaluate the performance of StrAttack against two defense mechanisms: defensive distillation (Papernot et al., 2016c) and adversarial training (Tramèr et al., 2018). We observe that StrAttack is able to break the two defense methods with 100% ASR. More details are provided in Appendix H.
Lastly, we evaluate the transferability of StrAttack from Inception V3 (Szegedy et al., 2016) to other network models including Inception V2, Inception V4 (Szegedy et al., 2017), ResNet 50, ResNet 152 (He et al., 2016), DenseNet 121 and DenseNet 161 (Huang et al., 2017). For comparison, we also present the transferbility of IFGSM and C&W. This experiment is performed under 1000 (target) adversarial examples on ImageNet2. It can be seen from in Table 3 that StrAttack yields the largest attack success rate while transferring to almost every network model.
2We follow the experiment setting in (Su et al., 2018), where the transferability is evaluated by the target class top-5 success rate at each transferred model.

heading: 6 STRATTACK OFFERS BETTER INTERPRETABILITY
text: In this section, we evaluate the effects of structured adversarial perturbations on image classification through adversarial saliency map (ASM) (Papernot et al., 2016b) and class activation map (CAM) (Zhou et al., 2016). Here we recall that ASM measures the impact of pixel-level perturbations on label classification, and CAM localizes class-specific image discriminative regions that we use to visually explain adversarial perturbations (Xiao et al., 2018). We will show that compared to C&W attack, StrAttack meets better interpretability in terms of (a) a higher ASM score and (b) a tighter connection with CAM, where the metric (a) implies interpretability at a micro-level, namely, perturbing pixels with largest impact on image classification, and the metric (b) demonstrates interpretability at a macro-level, namely, perturbations can be mapped to the most discriminative image regions localized by CAM.
Given an input image x0 and a target class t, let ASM(x0, t) ∈ Rd denote ASM scores for every pixel of x0 corresponding to t. We elaborate on the mathematical definition of ASM in Appendix E. Generally speaking, the ith element of ASM(x0, t), denoted by ASM(x0, t)[i], measures how much the classification score with respect to the target label t will increase and that with respect to the original label t0 will decrease if a perturbation is added to the pixel i. With the aid of ASM, we then define a Boolean map BASM ∈ Rd to encode the regions of x0 most sensitive to targeted adversarial attacks, where BASM(i) = 1 if ASM(x0, t) > ν, and 0 otherwise. Here ν is a given threshold to highlight the most sensitive pixels. we then define the interpretability score (IS) via ASM,
IS(δ) = ‖BASM ◦ δ‖2/‖δ‖2, (23)
where ◦ is the element-wise product. The rationale behind (23) is that IS(δ) → 1 if the sensitive region identified by ASM perfectly predicts the locations of adversarial perturbations. By contrast, if IS(δ)→ 0, then adversarial perturbations cannot be interpreted by ASM. In Fig. 3(a), we compare IS of our proposed attack with C&W attack versus the threshold ν, valued by different percentiles of ASM scores. We obsreve that our attack outperforms C&W attack in terms of IS, since the former is able to extract important local structures of images by penalizing the group sparsity of adversarial perturbations. It seems that our improvement is not significant. However, StrAttack just perturbs very few pixels to obtain this benefit, leading to perturbations with more semantic structure; see Fig. 3(b) for an illustrative example.
Besides ASM, we show that the effect of adversarial perturbations can be visually explained through the class-specific discriminative image regions localized by CAM (Zhou et al., 2016). In Fig. 3(c), we illustrate CAM and demonstrate the differences between our attack and C&W in terms of their connections to the most discriminative regions of x0 with label t0. We observe that the mechanism of StrAttack can be better interpreted from CAM: only a few adversarial perturbations are needed to suppress the feature of the original image with the true label. By replacing ASM with CAM, we can similarly compute IS in (23) averaged over 500 examples on ImageNet, yielding 0.65 for C&W attack and 0.77 for our attack. More examples of ASM and CAM can be viewed in Appendix E.
To better interpret the mechanism of adversarial examples, we study adversarial attacks on some complex images, where the objects of the original and target labels exist simultaneously as shown in Fig. 4. It can be visualized from CAM that both C&W attack and StrAttack yields similar adversarial effects on natural images: Adversarial perturbations are used to suppress the most discriminative
region with respect to the true label, and simultaneously promotes the discriminative region of the target label. The former principle is implied by the location of perturbed regions and C(x0, t0) in Fig. 4, and the latter can be seen fromC(xCW, t) orC(xStr, t) againstC(x0, t). However, compared to C&W attack, StrAttack perturbs much less but ‘right’ pixels which have better correspondence with class-specific discriminative image regions localized by CAM.

heading: 7 CONCLUSION
text: This work explores group-wise sparse structures when implementing adversarial attacks. Different from previous works that use `p norm to measure the similarity between an original image and an adversarial example, this work incorporates group-sparsity regularization into the problem formulation of generating adversarial examples and achieves strong group sparsity in the obtained adversarial perturbations. Leveraging ADMM, we develop an efficient implementation to generate structured adversarial perturbations, which can be further used to refine an arbitrary adversarial attack under fixed group sparse structures. The proposed ADMM framewrok is general enough for implementing many state-of-the-art attacks. We perform extensive experiments using MNIST, CIFAR-10 and ImageNet datasets, showing that our structured adversarial attack (StrAttack) is much stronger than the existing attacks and its better interpretability from group sparse structures aids in uncovering the origins of adversarial examples.

heading: ACKNOWLEDGEMENT
text: This work is supported by Air Force Research Laboratory FA8750-18-2-0058, and U.S. Office of Naval Research. Sijia Liu, Pin-Yu Chen, Huan Zhang and Quanfu Fan were supported by the MITIBM Watson Ai Lab, IBM Research.

heading: B PROOF OF PROPOSITION 1
text: We recall that the augmented Lagrangian function L(δ, z,w,y,u,v, s) is given by L(z, δ,y,w,u,v, s) =f(z + x0) + γD(δ) + τ ∑PQ i=1 ‖yDi‖2 + h(w) + uT (δ − z)
+ vT (y − z) + sT (w − z) + ρ 2 ‖δ − z‖22 + ρ 2 ‖y − z‖22 + ρ 2 ‖w − z‖22. (24)
Problem (7), to minimize L(δ, zk,w,y,uk,vk, sk), can be decomposed into three sub-problems:
minimize δ
γD(δ) + ρ
2 ‖δ − a‖22, (25)
minimize w
h(w) + ρ
2 ‖w − b‖22, (26)
minimize y τ PQ∑ i=1 ‖yDi‖2 + ρ 2 ‖y − c‖22, (27)
where a := zk − uk/ρ, b := zk − sk/ρ, and c := zk − vk/ρ.
δ-step Suppose D(δ) = ‖δ‖22, then the solution to problem (25) is easily acquired as below
δk+1 = ρ
ρ+ 2γ a (28)
w-step Based on the definition of h(w), problem (26) becomes
minimize w ‖w − b‖22 subject to (x0 + w) ∈ [0, 1]n, ‖w‖∞ ≤ .
(29)
Problem (29) is equivalent to
minimize wi (wi − ai)22 subject to −[x0]i ≤ wi ≤ 1− [x0]i, |wi| ≤
(30)
for i ∈ [n], where xi or [x]i represents the ith element of x, and 1 − [x0]i > 0 since [x0]i ∈ [0, 1]. Problem (30) then yields the solution
[wk+1]i = { min{1− [x0]i, } ai > min{1− [x0]i, } max{−[x0]i,− } ai < max{−[x0]i,− } ai otherwise.
(31)
y-step Problem (27) becomes
minimize y PQ∑ i=1 ‖yDi‖2 + ρ 2τ ‖y − c‖22, (32)
The solution is given by the proximal operator associated with the `2 norm with parameter τ/ρ (Parikh et al., 2014)
[yk+1]Di =
( 1− τ
ρ‖[c]Di‖2 ) + [c]Di , i ∈ [PQ], (33)
where recall that ∪i∈[PQ]Di = [n], and Di ∩ Dj = ∅ if i 6= j.

heading: C PROOF OF PROPOSITION 2
text: The augmented Lagrangian of problem (16) is given by L(z, δ,w, {yi},u,vi, s) =f(z + x0) + γD(δ) + h(w) + τ PQ∑ i=1 ‖yi,Di‖2 + uT (δ − z) + sT (w − z)
+ PQ∑ i=1 vTi (yi − z) + ρ 2 ‖δ − z‖22 + ρ 2 ‖w − z‖22 + ρ 2 PQ∑ i=1 ‖yi − z‖22,
(34)
where u, vi and s are the Lagrangian multipliers.
ADMM decomposes the optimization variables into two blocks and adopts the following iterative scheme,
{δk+1,wk+1,yk+1i } = argmin δ,w,{yi} L(zk, δ,w,yi,u k,vki , s k), (35)
zk+1 = argmin z L(z, δk+1,wk+1,yk+1i ,u k,vki , s k), (36) u k+1 = uk + ρ(δk+1 − zk+1), vk+1i = v k i + ρ(y k+1 i − zk+1), for i ∈ [PQ],
sk+1 = sk + ρ(wk+1 − zk+1), (37)
where k is the iteration index. Problem (35) can be split into three subproblems as shown below,
minimize δ
γD(δ) + ρ
2 ‖δ − a‖22, (38)
minimize w
h(w) + ρ
2 ‖w − b‖22, (39)
minimize yi
τ‖yi,Di‖2 + ρ
2 ‖yi − ci‖22, for i ∈ [PQ]. (40)
where a = zk − uk/ρ, b = zk − sk/ρ and ci = zk − vki /ρ. Each problem has a closed form solution. Note that the solutions to problem (38) and problem (39) are given (28) and (31).
yi-step Problem (40) can be rewritten as
minimize yi
τ‖yi,Di‖2 + ρ
2 ‖yi,Di − [ci]Di‖22 +
ρ 2 ‖yi,[n]/Di − [ci][n]/Di‖ 2 2, for i ∈ [PQ], (41)
which can be decomposed into
minimize yi,Di τ‖yi,Di‖2 + ρ 2‖yi,Di − [ci]Di‖ 2 2, for i ∈ [PQ], (42)
and
minimize yi,[n]/Di ‖yi,[n]/Di − [ci][n]/Di‖ 2 2, for i ∈ [PQ]. (43)
The solution to problem (42) can be obtained through the block soft thresholding operator (Parikh et al., 2014), [
yk+1i ] Di = ( 1− τ
ρ‖[ci]Di‖2 ) + [ci]Di , for i ∈ [PQ], (44)
The solution to problem (43) is given by,[ yk+1i ] [n]/Di = [ci][n]/Di , for i ∈ [PQ]. (45)
z-step Problem (36) can be simplified to
minimize z
f(x0 + z) + ρ
2 ‖z− a′‖22 +
ρ 2 ‖z− b′‖22 + ρ 2 PQ∑ i=1 ‖z− c′i‖22, (46)
where a′ := δk+1 + uk/ρ, b′ := wk+1 + sk/ρ, and c′i := y k+1 i + v k i /ρ. We solve problem (46) using the linearization technique (Suzuki, 2013; Liu et al., 2018; Boyd et al., 2011). More specifically, the function f is replaced with its first-order Taylor expansion at the point zk by adding a Bregman divergence term (ηk/2)‖z− zk‖22. As a result, problem (46) becomes
minimize z (∇f(zk + x0))T (z− zk) + ηk 2 ‖z− zk‖22 + ρ 2 ‖z− a′‖22
+ ρ
2 ‖z− b′‖22 +
ρ
2 PQ∑ i=1 ‖z− c′i‖22, (47)
whose solution is given by
zk+1 = ηkz
k + ρa′ + ρb′ + ρ ∑PQ i=1 c ′ i −∇f(zk + x0)
ηk + (2 + PQ)ρ . (48)

heading: D PROOF OF PROPOSITION 3
text: We start by converting problem (20) into the ADMM form
minimize δ,z f(x0 + z) + g(z) + γD(δ) + h(δ) + g(δ) subject to δ = z, (49)
where z and δ are optimization variables, g(δ) is an indicator function with respect to the constraint {δi = 0, if i ∈ Sσ}, and h(δ) is the other indicator function with respect to the other constraints (x0 + δ) ∈ [0, 1]n, ‖δ‖∞ ≤ . The augmented Lagrangian of problem (20) is given by
L(δ, z,u) =f(z + x0) + g(z) + γD(δ) + h(δ) + g(δ) + u T (δ − z) + ρ
2 ‖δ − z‖22, (50)
where u is the Lagrangian multiplier.
ADMM yields the following alternating steps
δk+1 = argmin δ L(δ, zk,uk) (51)
zk+1 = argmin z L(δk+1, z,uk) (52)
uk+1 = uk + ρ(δk+1 − zk+1). (53)
δ-step Suppose D(δ) = ‖δ‖22, problem (51) becomes minimize
δ γ‖δ‖22 + ρ 2‖δ − a‖ 2 2
subject to (x0 + δ) ∈ [0, 1]n, ‖δ‖∞ ≤ δi = 0, if i ∈ Sσ,
(54)
where a := zk − uk/ρ. Problem (54) can be decomposed elementwise
minimize δi 2γ+ρ ρ δ 2 i − 2aiδi + a2i = 2γ+ρ ρ
( δi − ρ2γ+ρai )2 subject to ([x0]i + δi) ∈ [0, 1], |δi| ≤
δi = 0, if i ∈ Sσ. (55)
The solution to problem (55) is then given by
[δk+1]i =  0 i ∈ Sσ min{1− [x0]i , } ρ 2γ+ρai > min{1− [x0]i , }, i /∈ Sσ max{− [x0]i ,− } ρ 2γ+ρai < max{− [x0]i ,− }, i /∈ Sσ ρ
2γ+ρai otherwise.
(56)
z-step Problem (52) yields
minimize z
f(x0 + z) + ρ
2 ‖z− a′‖22
subject to zi = 0, if i ∈ Sσ, (57)
where a′ = δk+1 + uk/ρ. We solve problem (57) using the linearization technique (Suzuki, 2013; Liu et al., 2018; Boyd et al., 2011),
minimize z (∇f(x0 + zk))T (z− zk) + ηk 2 ‖z− zk‖22 + ρ 2 ‖z− a′‖22
subject to zi = 0, if i ∈ Sσ, (58)
where ηk is a decaying parameter associated with the Bregman divergence term ‖z − zk‖22. In problems (57) and (58), only variables {zi} satisfying i /∈ Sσ are unknown. The solution to problem (58) is then given by
[zk+1]i = { 0 i ∈ Sσ ηk[z
k]i+ρ[a ′]i−[∇f(zk+x0)]i ηk+ρ i /∈ Sσ. (59)

heading: E ADVERSARIAL SALIENCY MAP (ASM) AND CLASS ACTIVATION
text: MAPPING (CAM)
ASM(x, t) ∈ Rd is defined by the forward derivative of a neural network given the input sample x and the target label t (Papernot et al., 2016b)
ASM(x, t)[i] =
{ 0 if ∂Z(x)t∂xi < 0 or ∑ j 6=t ∂Z(x)j ∂xi > 0(
∂Z(x)t ∂xi ) ∣∣∣∑j 6=t ∂Z(x)j∂xi ∣∣∣ otherwise, (60) where Z(x)j is the jth element of logits Z(x), representing the output before the last softmax layer in DNNs. If there exist many classes in a dataset (e.g., 1000 classes in ImageNet), then computing∑ j 6=t ∂Z(x)j ∂xi is intensive. To circumvent the scalability issue of ASM, we focus on the logit change with respect to the true label t0 and the target label t only. More specifically, we consider three quantities, ∂Z(x)t∂xi , − ∂Z(x)0 ∂xi , and ( ∂Z(x)t ∂xi
) ∣∣∣∑j 6=t ∂Z(x)j∂xi ∣∣∣, which correspond to a) promotion of the score of the target label t, b) suppression of the classification score of the true label t0, and c) a dual role on suppression and promotion. As a result, we modify (60) as
ASM(x, t)[i] =
{ 0 if ∂Z(x)t∂xi < 0 or ∂Z(x)t0 ∂xi > 0(
∂Z(x)t ∂xi ) ∣∣∣∂Z(x)t0∂xi ∣∣∣ otherwise. (61)
CAM allows us to visualize the perturbation of adversaries on predicted class scores given any pair of image and object label, and highlights the discriminative object regions detected by CNNs (Zhou et al., 2016). In Fig. A2, we show ASM and the discriminative regions identified by CAM on several ImageNet samples.
Original label: Komdo dragon Target label: tailed frog
Original label: titi Target label: gondola
Original label: stove Target label: ouzel
Original label: Africa elephant Target label: dining table
Original label: jeep Target label: ballon
Original label: photocopier Target label: accordion
(a) (b)
Figure A2: (a) Overlay ASM and BASM ◦ δ on top of image with the true and the target label. From left to right: original image, ASM (darker color represents larger value of ASM score), BASM ◦ δ under our attack, and BASM◦δ under C&W attack. Here ν in BASM is set by the 90th percentile of ASM scores. (b) From left to right: original image, CAM of original label, and perturbations with target label generated from the StrAttack and C&W attack, respectively.

heading: F EXPERIMENT SETUP AND PARAMETER SETTING
text: In this work, we consider targeted adversarial attacks since they are believed stronger than untargeted attacks. For targeted attacks, we have different methods to choose the target labels. The average case selects the target label randomly among all the labels that are not the correct label. The best case performs attacks using all incorrect labels, and report the target label that is the least difficult to attack. The worst case performs attacks using all incorrect labels, and report the target label which is the most difficult to attack.
In our experiments, two networks are trained for MNIST and CIFAR-10, respectively, and a pretrained network is utilized for ImageNet. The model architectures for MNIST and CIFAR-10 are the same, both with four convolutional layers, two max pooling layers, two fully connected layers and a softmax layer. It can achieve 99.5% and 80% accuracy on MNIST and CIFAR-10, respectively. For ImageNet, a pre-trained Inception v3 network (Szegedy et al., 2016) is applied which can achieve 96% top-5 accuracy. All experiments are conducted on machines with NVIDIA GTX 1080 TI GPUs.
The implementations of FGM and IFGM are based on the CleverHans package (Papernot et al., 2016a). The key distortion parameter is determined by a fine-grained grid search. For IFGM, we perform 10 FGM iterations and the distortion parameter ′ is set to /10 for effectiveness as shown in Tramèr et al. (2018). The implementation of the C&W attack is based on the opensource code provided by Carlini & Wagner (2017). The maximum iteration number is set to 1000 and it has 9 binary search steps.
In the StrAttack, the group size for MNIST and CIFAR-10 is 2 × 2 and its stride is set to 2 if the non-overlapping mask is used, otherwise the group size is 3 × 3 and stride is 2. The group size for ImageNet is 13 × 13 and its stride is set to 13. In ADMM, the parameter ρ achieves a trade-off between the convergence rate and the convergence value. A larger ρ could make ADMM converging faster but usually leads to perturbations with larger `p distortion values. A proper configuration of the parameters is suggested as follows: We set the penalty parameter ρ = 1, decaying parameter in (14) η1 = 5, τ = 2 and γ = 1. Moreover, we set c defined in (3) to 0.5 for MNIST, 0.25 for CIFAR-10, and 2.5 for ImageNet. Refined attack technique proposed in Sec. 4.2 is applied for all
experiments, we set σ is equal to 3% quantile value of non-zero perturbation in δ∗. We observe that 73% of δ∗ can be retrained to a σ-sparse perturbation successfully which proof the effective of our refined attack step.

heading: G SUPPLEMENTARY EXPERIMENTAL RESULTS
text: Original Image: 1
Original Image: 0Target: 2 Target: 2
Target: 3 Target: 3
C&W attack structured attack
Original Image: 4Target: 0 Target: 0
Target: 9Original Image: 7Target: 9
Original Image: 9 Target: 4Target: 4
Original Image: 5Target: 2 Target: 2
1e-5 0.3
Figure A3: C&W attack vs StrAttack on MNIST with grid size 2× 2.
Some random choice samples from MNIST (Fig. A3), CIFAR-10 (Fig. A4) and ImageNet (Fig. A5) compare StrAttack with C&W attack. For better sparse visual effect, we only show non-overlapping mask function results here. From these samples, we can discover a consistent phenomenon that our StrAttack is more interested in some particular regions, they usually appear on the objects or their edges in original images, distinctly seen in MNIST (Fig. A3) and ImageNet (Fig. A5).

heading: H STRATTACK AGAINST DEFENSIVE DISTILLATION AND ADVERSARIAL TRAINING
text: In this section, we present the performance of the StrAttack against defensive distillation (Papernot et al., 2016c) and adversarial training (Tramèr et al., 2018). In defensive distillation, we evaluate the
ship
Original Image:
airplane
Target:
automobile
Target:
automobile
airplane airplane
C&W attack structured attack
truckbird bird
catdeer deer
Figure A4: C&W attack vs StrAttack on CIFAR-10 with grid size 2× 2.
StrAttack for different temperature parameters on MNIST and CIFAR-10. We generate 9000 adversarial examples with 1000 randomly selected images from MNIST and CIFAR-10, respectively. The attack success rates of the StrAttack for different temperatures T are all 100%. The reason is that distillation at temperature T makes the logits approximately T times larger but does not change the relative values of logits. The StrAttack which works on the relative values of logits does not fail.
We further use the StrAttack to break DNNs training on adversarial examples (Tramèr et al., 2018) with their correct labels on MNIST. The StrAttack is performed on three neural networks: the first network is unprotected, the second is obtained by retraining with 9000 C&W adversarial examples, and the third network is retained with 9000 adversarial examples crafted by the StrAttack. The success rate and distortions on the three networks are shown in Table A1. The StrAttack can break all three networks with 100% success rate. However, adversarial training shows certain defense effects as an increase on the `1 or `2 distortion on the latter two networks over the unprotected network is observed.
Table A1: StrAttack against adversarial training on MNIST
Adversarial Best case Average case Worst case training ASR `1 `2 ASR `1 `2 ASR `1 `2 None 100 10.9 1.51 100 18.05 2.16 100 26.9 2.81 C&W 100 16.1 1.87 100 25.1 2.58 100 34.2 3.26
structured 100 15.6 1.86 100 25.1 2.61 100 34.6 3.31
wombat
Original Image:
black swan
Target:
television
Target:
television
boathouse boathouse
C&W attack structured attack
jellyfishminiature schnauzer miniature schnauzer
bramblingleaf beetle leaf beetle
flatwormEntleBucher EntleBucher
3e-4 3e-4
Figure A5: C&W attack vs StrAttack on ImageNet with grid size 13× 13.

Review summaries:
The paper proposes a method to find adversarial examples in which the changes are localized to small regions of the image. A group-sparsity objective is introduced for this purpose and it is combined with an l_p objective that was used in prior work to define proximity to the original example. ADMM is applied to maximize the defined objective. It is shown that adversarial examples in which all changes are concentrated in just few regions can be found with the proposed method.

The paper proposes a novel approach to generate adversarial examples based on structured sparsity principles. In particular the authors focus on the intuition that adversarial examples in computer vision might benefit from encoding information about the local structure of the data. To this end, lp *group* norms can be used in contrast to standard global lp norms when constraining or penalizing the optimization of the adversarial example. The authors propose an optimization strategy to address this problem. The authors evaluate the proposed approach on real data, comparing it against state-of-the-art competitors, which do not leverage the structured sparsity idea.