Source-linked AI summary
SparseFool: a few pixels make a big difference
Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, Pascal Frossard
TL;DR
Sparse adversarial perturbations can fool deep networks, yet efficient methods for computing them while maintaining valid image values remain limited. The paper proposes SparseFool, a geometry-inspired attack that exploits decision-boundary curvature and controls sparsity. Evaluations report fast computation, efficient scaling to high-dimensional data, shared semantic information across images and networks, and only slight robustness gains from adversarial training.
Problem
Deep networks are vulnerable to sparse input alterations, but computing sparse perturbations efficiently while ensuring valid adversarial image values remains a research gap.
Method
SparseFool exploits low mean curvature of decision boundaries to compute geometry-inspired sparse perturbations with controllable sparsity.
Results
SparseFool computes sparse perturbations very fast, scales efficiently to high-dimensional data, and reveals shared semantic information across images and networks.
Takeaways & Limitations
Sparse attacks remain a vulnerability of deep networks, and adversarial training only slightly improves robustness against SparseFool perturbations.
Takeaways & Limitations
SparseFool may fail to converge when an ℓ1 perturbation moves the input away from the locally flat neighborhood of the decision boundary.
Abstract
from arXiv · showhide
Deep Neural Networks have achieved extraordinary results on image classification tasks, but have been shown to be vulnerable to attacks with carefully crafted perturbations of the input data. Although most attacks usually change values of many image's pixels, it has been shown that deep networks are also vulnerable to sparse alterations of the input. However, no computationally efficient method has been proposed to compute sparse perturbations. In this paper, we exploit the low mean curvature of the decision boundary, and propose SparseFool, a geometry inspired sparse attack that controls the sparsity of the perturbations. Extensive evaluations show that our approach computes sparse perturbations very fast, and scales efficiently to high dimensional data. We further analyze the transferability and the visual effects of the perturbations, and show the existence of shared semantic information across the images and the networks. Finally, we show that adversarial training can only slightly improve the robustness against sparse additive perturbations computed with SparseFool.
1. Introduction
Sparse perturbations expose an important vulnerability of deep networks, but existing approaches are computationally expensive and can produce invalid, perceptible pixel values. SparseFool addresses this gap with a geometry-inspired attack that is fast, scalable, sparsity-controllable, and designed to preserve valid image values.
- Motivation: Sparse perturbations can fool deep networks by altering only a small fraction of input pixels, motivating study beyond standard ℓ2 and ℓ∞ attacks.The paper gives examples including raindrops on a STOP sign and sparse flowers in a crop field.
- Challenges: ℓ0 minimization is NP-hard, while existing sparse methods are high-complexity and often concentrate high-magnitude, perceptible noise on a few pixels.Perturbed pixels may exceed the valid dynamic range of the image.
- SparseFool: SparseFool exploits low mean curvature of decision boundaries to compute sparse adversarial perturbations efficiently.The method is introduced as a geometry-inspired sparse attack.
- Evaluation: The attack scales efficiently to high-dimensional data and computes sparse perturbations faster than existing methods.These properties are reported through extensive evaluations.
- Analysis: SparseFool includes control over perturbation perceptibility while retaining sparsity and complexity levels.The paper also analyzes visual features affected by the attack and reports shared semantic information across images and networks.
- Robustness: Adversarial training slightly lowers vulnerability to sparse perturbations but does not yet produce more robust classifiers.This is presented as a conclusion of the paper’s evaluation.
2. Problem description
Sparse attacks seek to minimize the number of altered pixels, but ℓ0 optimization is difficult and prior ℓ1-based methods can violate valid pixel ranges. SparseFool addresses this by linearizing the decision boundary while enforcing box constraints.
- Sparse perturbation problem: Sparse perturbations minimize the number of altered pixels, corresponding to minimizing ∥r∥0, but this optimization is generally NP-hard.The common ℓ1 relaxation offers computational tractability but only approximates the sparse objective.
- Existing approach: DeepFool-inspired linearization enables efficient sparse perturbation computation through an ℓ1 projection onto an approximated decision boundary.ℓ1-DeepFool generalizes the projection procedure to p = 1 to approximate the ℓ0 solution.
- Validity constraints: Valid pixel ranges are essential because sparse attacks concentrate stronger noise on fewer pixels, making out-of-range values more consequential.Adversarial image values must remain within bounds such as [0, 255].
- Validity constraints: For VGG-16 on ImageNet, ℓ1-DeepFool achieved almost 100% fooling by altering 0.037% of pixels, but clipping reduced fooling rate to 13%.This demonstrates that post hoc clipping can substantially degrade sparse-attack success.
- SparseFool: SparseFool exploits low local mean curvature by approximating the decision boundary as an affine hyperplane and solving a box-constrained problem.The method combines geometric boundary linearization with constraints on the perturbed image values.
3. Sparse adversarial perturbations
SparseFool computes sparse adversarial perturbations by repeatedly linearizing the decision boundary, projecting along selected coordinates, and enforcing valid pixel bounds. Its parameter λ trades sparsity and fooling rate against convergence complexity, while local boundary curvature limits one-step convergence.
- Linearized problem solution: SparseFool projects toward one coordinate of the normal vector at a time and excludes directions whose coordinates have reached their extrema.This iterative restriction addresses cases where box-constrained readjustment prevents the projected point from remaining on the approximated hyperplane.
- Linearized problem solution: The algorithm enforces valid image values by applying a projection operator Q onto box constraints after each perturbation update.The bounds l and u can represent image dynamic ranges or more general constraints.
- Finding the point xB and the normal w: SparseFool estimates the boundary point with ℓ2-DeepFool, computes a local normal vector, and applies the linearized solver until the network label changes.Each iteration recomputes the local approximation from the current iterate.
- SparseFool: Local flatness can be lost when an ℓ1 update moves the datapoint away from its neighborhood, causing the expected one-step solution not to converge.SparseFool mitigates this issue by repeatedly re-estimating the boundary and normal vector.
- SparseFool: Values of λ near 1 produce sparser perturbations but lower fooling rates and higher complexity, whereas larger λ values converge faster with less sparsity.λ is the algorithm’s only parameter and can be adjusted according to the desired trade-off.
- SparseFool: SparseFool is an untargeted attack because each iteration uses the adversarial class closest in ℓ2 distance to the true class.The method can be transformed into a targeted attack by selecting the target class when estimating the adversarial example.
4. Experimental results
SparseFool is evaluated across MNIST, CIFAR-10, and ImageNet for fooling effectiveness, sparsity, speed, perceptibility, transferability, semantic patterns, and robustness to adversarial training. It achieves efficient sparse attacks that scale to high-dimensional data, while sparsity, perceptibility, and transferability depend on the setting.
- Experimental setup: SparseFool is evaluated on 10,000 MNIST images, 10,000 CIFAR-10 images, and 4,000 ImageNet validation images using fooling rate, median perturbation percentage, and average execution time.The comparisons include JSMA and one-pixel attack where computational cost permits.
- Overall performance: 2.9x sparser and 4.7x faster than JSMA on MNIST; on CIFAR-10, SparseFool is 2.4x sparser and 15.5x faster.JSMA becomes much slower with increasing input dimension, whereas SparseFool maintains low time complexity.
- Overall performance: 270x faster and requiring 2 orders of magnitude fewer network queries than one-pixel attack, while sacrificing some sparsity on CIFAR-10.SparseFool solves an ℓ1 problem on a linearized formulation rather than the original NP-hard ℓ0 problem.
- Overall performance: 0.21% of ImageNet pixels are perturbed on average, with 7 seconds per sample; random pixel selection achieves much lower fooling rates.JSMA and one-pixel attack are omitted from ImageNet because of their high computational cost.
- Perceptibility: After δ ≈25, sparsity and execution time remain nearly constant, while the fooling rate stays at 100%, enabling perceptibility control without sacrificing sparsity or complexity.The perturbation range is constrained around the original image values.
- Transferability and semantic information: Sparse perturbations transfer only partly across architectures, more readily from larger to smaller models, and concentrate around important image regions without a consistent feature-level pattern.On CIFAR-10, perturbations often target shared head features and regions associated with features of the fooling class.
5. Conclusion
The paper presents SparseFool as a fast, geometry-inspired sparse attack that scales to high-dimensional data while offering control over perturbation perceptibility. Its analyses identify shared image features, and adversarial training provides limited robustness against the attack.
- Conclusion: SparseFool computes sparse perturbations quickly, scales to high-dimensional data, and provides leverage over their sparsity.The method is presented as geometry inspired and also addresses validity of adversarial image values.
- Conclusion: A simple constraint-based method improves perturbation perceptibility while retaining sparsity and computational complexity.The bounds constrain perturbed values near the original image values.
- Conclusion: SparseFool sometimes alters features shared across different images, offering insight into the behavior and geometry of deep image classifiers.The paper also reports that adversarial training does not significantly improve robustness against SparseFool perturbations.
A. SparseFool adversarial examples
Supplementary examples show SparseFool adversarial perturbations on ImageNet, CIFAR-10, and MNIST at highly sparse, very sparse, and sparse levels. The figures label the fooling class and indicate how many pixels are perturbed.
- Supplementary examples: Figures 10–12 show ImageNet, CIFAR-10, and MNIST adversarial examples across highly sparse, very sparse, and sparse perturbation levels.For highly and very sparse cases, the noise is described as imperceptible or negligible because of its sparsity.
- ImageNet: The ImageNet examples display predicted labels above images, fooling labels below them, and perturbed-pixel counts in parentheses.These annotations support comparison across different sparsity levels.
- CIFAR-10 and MNIST: The CIFAR-10 and MNIST examples display fooling labels below each image and perturbed-pixel counts in parentheses.The annotations identify the attack outcome and perturbation size.
B. Controlling the perceptibility of the perturbations
SparseFool’s perturbation perceptibility can be controlled by constraining each perturbed image value to lie within ±δ of its original value. The figure contrasts unconstrained dynamic-range noise with noise restricted to ±10.
- Control mechanism: Perturbation perceptibility is controlled by constraining perturbed image values to lie ±δ around the original image values.This bounds the allowable change at each perturbed element.
- Figure comparison: Figure 13 compares original images with adversarial examples using the whole dynamic range or noise constrained to ±10 around image values.Predicted labels appear below original images, while fooling labels and perturbed-pixel percentages appear below adversarial examples.
C. The control parameter λ
This section examines how the control parameter λ affects SparseFool’s fooling rate, perturbation sparsity, and convergence across MNIST, CIFAR-10, and ImageNet networks.
- λ is evaluated for its effects on fooling rate, perturbation sparsity, and SparseFool convergence.
- Figure 14 presents λ’s effect on SparseFool for a LeNet model trained on MNIST.
- Figure 15 presents λ’s effect on SparseFool for different CIFAR-10 networks.
- Figure 16 presents λ’s effect on SparseFool for different ImageNet networks.
D. Adversarial examples compared to related methods
This section compares SparseFool adversarial examples with examples generated by JSMA and “One-pixel attack” on MNIST and CIFAR-10.
- SparseFool adversarial examples are compared with corresponding examples computed by JSMA and “One-pixel attack”.
- Figure 17 shows MNIST examples from SparseFool, “One pixel attack”, and JSMA in separate rows.
- Each example figure displays the fooling label below each image and the number of perturbed pixels in parentheses.
- Figure 18 shows CIFAR-10 examples from SparseFool, “One pixel attack”, and JSMA in separate rows.