Source-linked AI summary
Universal adversarial perturbations
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, Pascal Frossard
TL;DR
The paper asks whether a single small, image-agnostic perturbation can fool state-of-the-art deep neural network classifiers on natural images, posing a potential security problem in hostile environments. It proposes an iterative algorithm for generating universal perturbations and finds that they generalize across images and network architectures, while relating their existence to correlations in decision-boundary geometry.
Problem
A single quasi-imperceptible, image-agnostic perturbation that fools natural images with high probability could be exploited to break classifiers in real-world hostile environments.
Method
The paper proposes an iterative algorithm for generating universal perturbations by solving optimization problems for training points during each pass.
Results
Universal perturbations fool natural images with high probability and generalize across both images and deep neural network architectures, making them doubly universal.
Takeaways & Limitations
The findings provide insights into deep neural network decision-boundary geometry by linking vulnerability to correlations between different boundary regions.
Takeaways & Limitations
Fine-tuning slightly increased validation-set error, possibly because of slight overfitting to the perturbed data.
Abstract
from arXiv · showhide
Given a state-of-the-art deep neural network classifier, we show the existence of a universal (image-agnostic) and very small perturbation vector that causes natural images to be misclassified with high probability. We propose a systematic algorithm for computing universal perturbations, and show that state-of-the-art deep neural networks are highly vulnerable to such perturbations, albeit being quasi-imperceptible to the human eye. We further empirically analyze these universal perturbations and show, in particular, that they generalize very well across neural networks. The surprising existence of universal perturbations reveals important geometric correlations among the high-dimensional decision boundary of classifiers. It further outlines potential security breaches with the existence of single directions in the input space that adversaries can possibly exploit to break a classifier on most natural images.
1. Introduction
The paper establishes that small, image-agnostic perturbations can fool state-of-the-art deep classifiers on natural images with high probability. It introduces an algorithm for finding them and shows that they generalize across images and network architectures, revealing correlations in decision-boundary geometry.
- Motivation: Universal perturbations are fixed, quasi-imperceptible vectors that change classifier labels for most natural images.Their image-agnostic nature makes them potentially exploitable in real-world environments.
- Contributions: The proposed algorithm constructs a universal perturbation by aggregating atomic vectors that move successive datapoints to the classifier’s decision boundary.Perturbing a new datapoint then requires only adding the learned vector, without solving a new optimization problem or computing gradients.
- Contributions: Universal perturbations computed from a small training set fool new images with high probability.This demonstrates a strong generalization property beyond the points used to compute the perturbation.
- Contributions: Universal perturbations generalize across deep neural networks as well as across images, making them doubly universal.The result covers both the data distribution and network architectures.
- Contributions: The paper links neural networks’ vulnerability to geometric correlations between different parts of their high-dimensional decision boundaries.This analysis is presented as an explanation of why single directions can affect many natural images.
2. Universal perturbations
The paper formalizes universal perturbations as small vectors that change classifier labels for most samples from an image distribution. Its iterative method aggregates minimal boundary-crossing perturbations, projects them onto a norm ball, and stops once the target empirical fooling rate is reached.
- 2. Universal perturbations: A universal perturbation v is sought that satisfies a small ℓp-norm bound while fooling most images sampled from distribution µ.The magnitude is controlled by ξ, while δ specifies the desired fooling-rate tolerance.
- Algorithm: The algorithm iteratively processes sampled images and computes a minimal perturbation Δv_i when the current universal vector does not fool x_i.Each atomic perturbation sends the currently perturbed point toward the classifier’s decision boundary before aggregation.
- Algorithm: After aggregation, the updated vector is projected onto the ℓp ball of radius ξ centered at zero.This projection preserves the prescribed perturbation-magnitude constraint.
- Stopping criterion: The algorithm repeats dataset passes until the empirical fooling rate on X_v exceeds the target threshold 1 − δ.The perturbed dataset is X_v = {x_1 + v, ..., x_m + v}.
- Computational considerations: A universal perturbation can often be computed from a set X much smaller than the full training set.The method solves at most m boundary-crossing optimization instances per pass, although the underlying problem may be nonconvex.
3. Universal perturbations for deep nets
Universal perturbations fool natural images across architectures, generalize from small training sets, and often redirect predictions toward dominant labels. Fine-tuning provides only mild robustness improvements and does not eliminate vulnerability.
- More than 90% of validation images are fooled for CaffeNet and VGG-F with p = ∞ and ξ = 10, while VGG, GoogLeNet, and ResNet approach 80%.The perturbations are evaluated on 50,000 ILSVRC 2012 validation images, which are not used to compute them.
- Generalization: More than 30% of validation images are fooled using a perturbation computed from only 500 training images, fewer than one image per ImageNet class.The method therefore generalizes to unseen images from a very small computation set.
- Cross-model universality: Over 53% fooling rates transfer from VGG-19 perturbations to every other tested architecture, demonstrating cross-model universality.Table 2 reports fooling rates by source architecture in rows and evaluated architecture in columns.
- Label topology: Universal perturbations often route images from multiple classes toward a few dominant labels, forming graph components whose edges mostly share one target.The directed graph links original class i to target class j when most images of class i are fooled into j.
- Perturbation diversity: Pairs of GoogLeNet universal perturbations generated from different shufflings have normalized inner products no greater than 0.1, indicating substantial diversity.The five perturbations use different random shufflings of the set X.
- Fine-tuning: A fine-tuned VGG-F reaches a 76.2% fooling ratio after one step and 80.0% after repetition, but repeated fine-tuning yields no further improvement.The procedure mildly improves robustness but does not fully immunize the network against small universal perturbations; it also causes a minor validation error increase.
4. Explaining the vulnerability to universal perturbations
Universal perturbations outperform random and other perturbations at small norms because decision-boundary normals exhibit strong geometric correlations concentrated in a low-dimensional subspace.
- Fooling-rate comparison: 85% fooling rate is achieved by Algorithm 1 at ℓ2 norm ξ = 2000, whereas random vectors of the same radius fool 10% of validation images.The gap indicates that the universal perturbation selects an effective direction rather than a random direction.
- Fooling-rate comparison: The large universal-versus-random gap suggests geometric correlations between different parts of the classifier’s decision boundary.If boundary orientations were uncorrelated, the best universal perturbation would have a norm comparable to a random perturbation.
- Boundary geometry: The matrix N is formed from normalized minimal adversarial perturbations, whose vectors are normal to the decision boundary near validation images.Each r(x) captures local decision-boundary geometry around a data point.
- Boundary geometry: N’s singular values decay quickly compared with random unit-sphere columns, confirming correlations and redundancies among decision-boundary normals.This pattern suggests a low-dimensional subspace S containing most normals near natural images.
- Generalization: The low-dimensional subspace S helps explain why universal perturbations generalize to new images after being computed from relatively few images.The same subspace is linked in the paper to the perturbations’ generalization properties.
- Generalization: Algorithm 1 chooses a specific direction in S to maximize fooling rate, unlike a random vector sampled from that subspace.This directional choice explains the gap between the random-subspace strategy and the proposed algorithm.
5. Conclusions
The paper establishes small universal perturbations, proposes an iterative construction method, and reports image- and network-level generalization. It attributes these effects to correlations among decision-boundary regions while leaving a theoretical analysis for future work.
- The paper shows that small universal perturbations can fool state-of-the-art classifiers on natural images.
- It proposes an iterative algorithm for generating universal perturbations and analyzes their properties.
- Universal perturbations generalize across classification models, producing doubly-universal perturbations that are image-agnostic and network-agnostic.
- The paper explains these perturbations through correlations between different regions of deep-network decision boundaries.
- A theoretical analysis of geometric correlations between different decision-boundary regions remains future work.
A. Appendix
The appendix supplements the experiments with original-image examples and a visualization of relations between original and perturbed labels.
- Figure 11 shows the original images corresponding to the experiment in Figure 3.
- Figure 12 visualizes the graph relating original and perturbed labels, with isolated nodes removed for readability.