Source-linked AI summary
Structured Adversarial Attack: Towards General Implementation and Better Interpretability
Kaidi Xu, Sijia Liu, Pu Zhao, Pin-Yu Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmus, Yanzhi Wang, Xue Lin
TL;DR
Norm-based adversarial attacks may fail to capture spatial structure in perturbations. The paper introduces StrAttack, which uses group sparsity and an ADMM framework to generate structured attacks, reporting strong sparsity, broad attack compatibility, and improved interpretability across image datasets.
Problem
Norm-based similarity measures may be insufficient for human perceptual similarity and may fail to capture spatial structure in adversarial inputs.
Method
StrAttack applies group-sparsity regularization to sliding-mask image groups and uses ADMM to split attack generation into analytically solvable subproblems.
Results
The method achieves strong group sparsity at comparable ℓp distortion, generalizes across attacks, and shows better correspondence with discriminative regions using saliency and activation maps.
Takeaways & Limitations
Structured perturbations provide a more interpretable attack representation while retaining the distortion performance of state-of-the-art attacks.
Takeaways & Limitations
Overlapping groups require PQ times more storage than non-overlapping groups during the y-update.
Abstract
from arXiv · showhide
When generating adversarial examples to attack deep neural networks (DNNs), Lp 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 Lp norm distortion as the state-of-the-art attacks. We demonstrate the effectiveness of StrAttack by extensive experimental results onMNIST, 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).
1 INTRODUCTION
The paper argues that norm-based adversarial attacks may miss spatial structure and proposes structured perturbations that balance attack effectiveness, sparsity, and interpretability.
- ℓp norm measures perturbation similarity but may be neither necessary nor sufficient for human perceptual similarity or spatial structure.
- StrAttack explores group-wise sparse adversarial structures without losing ℓp distortion performance against state-of-the-art attacks.
- An ADMM framework generalizes implementation across norm-ball attacks and analytically solves decomposed subproblems.
- Existing attacks trade off image-level distortion against the number of perturbed pixels, potentially increasing noise visibility.
- Adversarial saliency maps and class activation maps are used to assess whether perturbations correspond to discriminative image regions.
2 STRUCTURED ATTACK: EXPLORE GROUP STRUCTURES FROM IMAGES
StrAttack divides perturbations into local pixel groups and penalizes group-wise activity so sparse groups encode minimally sufficient effects on image structures.
- StrAttack divides an image perturbation into pixel sub-groups and penalizes group-wise sparsity.
- A sliding mask with stride S and size r × r × C defines different group-splitting schemes.
- When S < r, groups overlap; when S = r, groups are non-overlapping.
- The mask partitions the perturbation into indexed groups whose sparsity is characterized using a group-Lasso-motivated function.
3 STRUCTURED ADVERSARIAL ATTACK WITH ADMM
The attack formulation combines adversarial loss, distortion, group sparsity, and pixel constraints, while ADMM decomposes the resulting difficult optimization into tractable updates.
- The general formulation combines attack loss, distortion control, group sparsity, and hard constraints on perturbed pixel values.
- Removing group sparsity and the ℓ∞ constraint recovers C&W variants, while an elastic-net distortion yields EAD.
- Multiple non-smooth regularizers and hard constraints make Adam and FISTA inefficient for solving the structured formulation.
- ADMM reformulates the problem with auxiliary variables and splits it into subproblems solved through alternating primal and dual updates.
- The ADMM solution for one update can be found exactly and in parallel, and changing the distortion metric affects only the corresponding distortion update.
2. As a result, problem (13) becomes
Linearized ADMM replaces the difficult z-update with a stabilized quadratic problem having a closed-form solution, supporting efficient and general attack updates.
- The Bregman divergence term stabilizes the z-minimization step through a decaying parameter η_k.
- The resulting z-subproblem is a quadratic program with a closed-form solution.
- The complete ADMM algorithm alternates updates with closed-form solutions and is described as efficient and applicable to a wide class of attack formulations.
4 OVERLAPPING GROUP AND REFINED STRATTACK
The paper extends StrAttack to overlapping group structures and to refinement under fixed sparse patterns, using ADMM to manage coupled variables and optimize identified nonzero groups.
- Overlapping group structure: Overlapping groups are handled by introducing multiple copies of the variable so each group becomes non-overlapped in its own copy.The modified formulation adds PQ variables y_i and equality constraints linking them to z.
- Overlapping group structure: The ADMM procedure retains the original δ- and w-steps while modifying the y- and z-steps for overlapping groups.Proposition 2 characterizes these modified updates under the same conditions as Proposition 1.
- Overlapping group structure: Updating the PQ copied variables decomposes across groups but requires PQ times more storage than the non-overlapping formulation.This is the stated computational side effect of the overlapping-group approach.
- Refined StrAttack under fixed sparse pattern: The refined attack first identifies structured sparse patterns from an ADMM solution and then imposes the resulting fixed σ-sparse structure on the attack problem.A hard-thresholding operator is applied to the initial perturbation to determine the sparse pattern.
- Refined StrAttack under fixed sparse pattern: With group sparsity treated as known, the refined model removes the group-sparse penalty and optimizes the nonzero groups using ADMM.The formulation is intended to improve highlighting and exploration of perturbation structure.
5 EMPIRICAL PERFORMANCE OF STRATTACK
StrAttack is evaluated on MNIST, CIFAR-10, and ImageNet against norm-based attacks using attack success and distortion metrics. It produces sparse perturbations, preserves competitive attack performance, and transfers effectively across ImageNet models.
- Experimental setup: StrAttack is evaluated on MNIST, CIFAR-10, and ImageNet, with ℓ2 distortion used for comparison against C&W and additional ℓp metrics reported.The reported metrics include ASR and ℓp distortion for p ∈ {0, 1, 2, ∞}.
- Attack effectiveness: 6.7% of C&W adversarial examples remain valid after thresholding to StrAttack’s ℓ0 norm, whereas StrAttack highlights localized group structures without perturbing other pixels.The examples include localized changes corresponding to discriminative image regions.
- Attack effectiveness: StrAttack perturbs fewer pixels while remaining comparable to or better than other attacks on ℓ1, ℓ2, and ℓ∞ distortion metrics.On MNIST and CIFAR-10 it outperforms other attacks in ℓ0, ℓ1, and ℓ∞ distortion; on ImageNet it outperforms C&W in ℓ0 and ℓ1 distortion.
- Robust-model evaluation: Under matched ℓ∞ constraints, StrAttack achieves similar ASR to other attacks while perturbing substantially fewer pixels.Against defensive distillation and adversarial training, StrAttack is reported to achieve 100% ASR.
- Transferability: StrAttack yields the largest transfer attack success rate while transferring to almost every evaluated ImageNet model.Transferability is evaluated from Inception V3 to six other network models using target-class top-5 success rate.
6 STRATTACK OFFERS BETTER INTERPRETABILITY
StrAttack produces adversarial perturbations that align more closely with discriminative image regions than C&W, as measured by ASM- and CAM-based interpretability analyses. It also achieves this correspondence while perturbing fewer, more semantically structured pixels.
- StrAttack outperforms C&W in ASM-based interpretability score across thresholds defined by ASM-score percentiles.The comparison varies ν from the 30th to the 90th percentile of ASM scores.
- StrAttack perturbs very few pixels while preserving stronger correspondence with sensitive image regions, producing more semantic structure than C&W.
- 0.77 versus 0.65: CAM-based interpretability score averaged over 500 ImageNet examples is higher for StrAttack than for C&W.
- CAM analysis indicates that StrAttack needs only a few perturbations to suppress features associated with the original class.
- On complex images containing both original and target objects, StrAttack perturbs fewer pixels with better correspondence to CAM-localized class-specific regions than C&W.
7 CONCLUSION
The paper presents StrAttack as a group-structured adversarial attack implemented through ADMM. Experiments across MNIST, CIFAR-10, and ImageNet report strong group sparsity, broad attack generality, and improved interpretability.
- StrAttack incorporates group-wise sparsity into adversarial perturbation generation and uses ADMM to implement structured attacks efficiently.
- The ADMM framework can implement many state-of-the-art attacks and refine arbitrary attacks under fixed group-sparse structures.
- Experiments on MNIST, CIFAR-10, and ImageNet report that StrAttack is stronger than existing attacks and more interpretable through group-sparse perturbations.
- Figure A1 illustrates how sliding-mask stride determines whether perturbation groups overlap or remain non-overlapping, with sparse and non-sparse groups shown separately.
B PROOF OF PROPOSITION 1
The proof develops ADMM decompositions for the structured attack and related constrained formulations. Each resulting subproblem is reduced to a tractable update, including proximal, thresholding, linearization, and constraint-handling steps.
- The y-step uses the proximal operator associated with the ℓ2 norm, while the group-sparsity update uses block soft thresholding.
- The augmented Lagrangian introduces auxiliary variables and Lagrange multipliers to separate attack objectives, sparsity terms, and constraints.
- ADMM splits the structured optimization into three subproblems, each with a closed-form solution.
- The z-step is solved with first-order linearization and a Bregman divergence term around the current iterate.
- The constrained updates enforce valid image values, bounded ℓ∞ perturbations, and zero perturbations on prescribed pixel sets.
- ASM measures target-score promotion and true-label suppression at each pixel, while CAM localizes class-specific discriminative regions for visual interpretation.
F EXPERIMENT SETUP AND PARAMETER SETTING
The experiments evaluate targeted attacks on MNIST, CIFAR-10, and ImageNet using different architectures, attack implementations, group settings, and refinement parameters. The refinement step retains most perturbation entries under a sparse threshold.
- Target labels are selected using average-, best-, or worst-case protocols over incorrect classes.
- MNIST and CIFAR-10 use four-convolutional-layer networks, while ImageNet uses a pretrained Inception v3 network.
- The baselines include CleverHans implementations of FGM and IFGM and open-source C&W with 1000 maximum iterations and 9 binary-search steps.
- StrAttack uses 2 × 2 groups for MNIST and CIFAR-10, with stride 2 for non-overlapping masks and 3 × 3 groups with stride 2 otherwise; ImageNet uses 13 × 13 groups with stride 13.
- 73% of the optimal perturbation δ∗ can be retained as a σ-sparse perturbation when σ is set to the 3% quantile of non-zero perturbation values.
G SUPPLEMENTARY EXPERIMENTAL RESULTS
Supplementary comparisons across MNIST, CIFAR-10, and ImageNet show that StrAttack focuses perturbations on selected spatial regions, often objects or their edges.
- Observed structure: StrAttack consistently concentrates perturbations on particular image regions rather than distributing them uniformly.These regions usually occur on objects or their edges, especially in MNIST and ImageNet examples.
H STRATTACK AGAINST DEFENSIVE DISTILLATION AND ADVERSARIAL TRAINING
StrAttack remains effective against defensive distillation and adversarial training. It achieves complete attack success in the reported settings, while adversarial training increases ℓ1 or ℓ2 distortion.
- Defensive distillation: StrAttack achieves 100% attack success across temperature parameters on MNIST and CIFAR-10 under defensive distillation.The attack operates on relative logit values, which distillation does not change.
- Adversarial training: StrAttack breaks unprotected and adversarially trained MNIST networks with a 100% success rate.The evaluated networks include models retrained with 9000 C&W adversarial examples and 9000 StrAttack adversarial examples.
- Adversarial training: Adversarial training increases ℓ1 or ℓ2 distortion for StrAttack relative to the unprotected network.The reported increase occurs for both networks trained on adversarial examples.