Universal Adversarial Perturbations

Seyed-Mohsen Moosavi-DezfooliAlhussein FawziOmar FawziPascal Frossard

article2016CVPR2,860 citations

Reveals that deep neural networks can be systematically fooled on nearly all natural images using a single, image-agnostic perturbation vector that transfers across different model architectures.

Listen

The article addresses the vulnerability of modern image classifiers to small, fixed changes in input. State-of-the-art deep networks achieve high accuracy on natural images yet can be misled by tiny alterations that are nearly invisible to people. This matters because such networks are now deployed in real environments where an adversary could exploit any consistent weakness.

The work set out to determine whether a single perturbation vector exists that fools a given classifier on most natural images while remaining small in norm. The authors developed an iterative algorithm that starts with a zero vector and repeatedly adds the smallest change needed to push each successive training image across the decision boundary, projecting the result back onto a ball of allowed radius after every step.

Experiments on six well-known architectures trained on ImageNet show that the resulting vectors achieve fooling rates between 78 percent and 93 percent on held-out validation images. The same vectors also transfer across networks, with some fooling more than half the images of unrelated models. Visual inspection confirms the perturbations remain quasi-imperceptible, and even vectors computed from only five hundred images retain substantial effectiveness.

These results indicate that the decision boundaries of current networks contain large geometric correlations; a low-dimensional subspace captures the normals to the boundary near most natural images. Consequently, a single direction in that subspace can move many points into wrong classes. The finding implies that current robustness claims based on per-image perturbations may understate practical risk, since an adversary needs only one vector rather than a new optimization for each input.

Fine-tuning a network on images augmented with several such vectors lowers the fooling rate modestly but does not eliminate the vulnerability. The authors therefore recommend further geometric analysis of decision boundaries and the design of training procedures that explicitly penalize shared directions across many points. The main limitations are the restriction to image classification on ImageNet-scale data and the lack of a theoretical bound on the minimal size of a universal perturbation; results should be treated as empirical evidence rather than a complete characterization.

arXiv: 1610.08401LTS4/universal
Cover for Universal Adversarial Perturbations

Abstract

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.

Table of Contents

  • 1 Introduction
  • 2 Universal perturbations
  • 3 Universal perturbations for deep nets
  • 4 Explaining the vulnerability to universal perturbations
  • 5 Conclusions
  • References
  • A Appendix

Knowls

  1. Knowl 1 — Definition of Universal Adversarial Perturbation

    definition

    Let μ\mu denote a probability distribution of natural images in Rd\mathbb{R}^d, and let k^:Rd{1,,K}\hat{k}: \mathbb{R}^d \to \{1, \dots, K\} be a classification model mapping an input image xRdx \in \mathbb{R}^d to an estimated class label k^(x)\hat{k}(x).

    A vector vRdv \in \mathbb{R}^d is defined as a universal adversarial perturbation for classifier k^\hat{k} and distribution μ\mu if it satisfies two conditions:

    1. vpξ\|v\|_p \le \xi
    2. Pxμ(k^(x+v)k^(x))1δ\mathbb{P}_{x \sim \mu}\left(\hat{k}(x + v) \neq \hat{k}(x)\right) \ge 1 - \delta

    where p[1,]p \in [1, \infty] defines the p\ell_p norm metric, ξ>0\xi > 0 restricts the magnitude of the perturbation to preserve quasi-imperceptibility to human observers, and δ(0,1)\delta \in (0, 1) parameterizes the minimum required fooling rate 1δ1 - \delta over all images drawn from μ\mu.

  2. Knowl 2 — Universal Adversarial Perturbation Computation Algorithm

    algorithm

    Given a sample dataset X={x1,,xm}RdX = \{x_1, \dots, x_m\} \subset \mathbb{R}^d drawn from image distribution μ\mu, a classifier k^\hat{k}, an p\ell_p perturbation budget ξ\xi, and an error parameter δ\delta, the algorithm iteratively constructs a single image-agnostic perturbation vector vRdv \in \mathbb{R}^d.

    The perturbation is initialized to v=0v = 0. In each epoch over the training set XX, the algorithm evaluates whether the current perturbed image xi+vx_i + v changes the prediction of k^\hat{k}. If k^(xi+v)=k^(xi)\hat{k}(x_i + v) = \hat{k}(x_i), it computes the minimal Euclidean perturbation Δvi\Delta v_i sending xi+vx_i + v across the decision boundary: Δvi=argminrr2subject tok^(xi+v+r)k^(xi)\Delta v_i = \arg\min_r \|r\|_2 \quad \text{subject to} \quad \hat{k}(x_i + v + r) \neq \hat{k}(x_i)

    The accumulated perturbation is then projected onto the p\ell_p ball of radius ξ\xi centered at the origin: vPp,ξ(v+Δvi)v \leftarrow \mathcal{P}_{p, \xi}(v + \Delta v_i) where Pp,ξ(u)=argminuuu2 subject to upξ\mathcal{P}_{p,\xi}(u) = \arg\min_{u'} \|u - u'\|_2 \text{ subject to } \|u'\|_p \le \xi.

    Multiple passes over XX are performed until the empirical fooling rate on the perturbed set Xv={x1+v,,xm+v}X_v = \{x_1 + v, \dots, x_m + v\} satisfies Err(Xv)=1mi=1mIk^(xi+v)k^(xi)1δ\text{Err}(X_v) = \frac{1}{m} \sum_{i=1}^m \mathbb{I}_{\hat{k}(x_i + v) \neq \hat{k}(x_i)} \ge 1 - \delta.

    Input: Dataset X={x1,,xm}X = \{x_1, \dots, x_m\}, classifier k^\hat{k}, norm constraint ξ\xi, target fooling tolerance δ\delta, norm parameter pp
    Output: Universal perturbation vector vv
    Initialize v0v \leftarrow 0
    while Err(Xv)<1δ\text{Err}(X_v) < 1 - \delta do
        for each datapoint xiXx_i \in X do
            if k^(xi+v)=k^(xi)\hat{k}(x_i + v) = \hat{k}(x_i) then
                Compute minimal perturbation Δviargminrr2 s.t. k^(xi+v+r)k^(xi)\Delta v_i \leftarrow \arg\min_r \|r\|_2 \text{ s.t. } \hat{k}(x_i + v + r) \neq \hat{k}(x_i)
                vPp,ξ(v+Δvi)v \leftarrow \mathcal{P}_{p,\xi}(v + \Delta v_i)
            end if
        end for
    end while
    return vv

    The minimal perturbation Δvi\Delta v_i per sample is computed using efficient boundary-seeking algorithms such as DeepFool.

  3. Knowl 3 — Fooling Rates of Universal Perturbations on Deep Neural Networks

    data/table

    Universal perturbations computed using an iterative projection algorithm on a training subset XX of 10,000 images from the ILSVRC 2012 training dataset achieve high fooling rates on both the training sample XX and the unseen 50,000-image ILSVRC 2012 validation set across multiple deep convolutional architectures.

    Evaluation is conducted under both 2\ell_2 constraint (with ξ=2000\xi = 2000) and \ell_\infty constraint (with ξ=10\xi = 10). For scale, average natural image norms on the validation set are x25×104\|x\|_2 \approx 5 \times 10^4 and x250\|x\|_\infty \approx 250.

    Norm Dataset CaffeNet VGG-F VGG-16 VGG-19 GoogLeNet ResNet-152
    2\ell_2 XX 85.4% 85.9% 90.7% 86.9% 82.9% 89.7%
    2\ell_2 Val. 85.6% 87.0% 90.3% 84.5% 82.0% 88.5%
    \ell_\infty XX 93.1% 93.8% 78.5% 77.8% 80.8% 85.4%
    \ell_\infty Val. 93.3% 93.7% 78.3% 77.8% 78.9% 84.0%

    For CaffeNet and VGG-F, adding a single quasi-imperceptible perturbation with 10\ell_\infty \le 10 misclassifies over 93% of unseen validation images. For VGG-16, VGG-19, GoogLeNet, and ResNet-152, the universal perturbations fool between 77.8% and 90.3% of the validation set.

  4. Knowl 4 — Cross-Model Transferability of Universal Perturbations

    data/table

    Universal adversarial perturbations computed for one deep neural network architecture generalize across distinct network architectures on the ImageNet benchmark, exhibiting cross-model universality.

    The matrix below shows fooling rates on the 50,000-image ILSVRC 2012 validation set when universal perturbations (generated with \ell_\infty bound ξ=10\xi = 10) computed for the architecture in each row are evaluated on the architecture in each column:

    Source Architecture VGG-F CaffeNet GoogLeNet VGG-16 VGG-19 ResNet-152
    VGG-F 93.7% 71.8% 48.4% 42.1% 42.1% 47.4%
    CaffeNet 74.0% 93.3% 47.7% 39.9% 39.9% 48.0%
    GoogLeNet 46.2% 43.8% 78.9% 39.2% 39.8% 45.5%
    VGG-16 63.4% 55.8% 56.5% 78.3% 73.1% 63.4%
    VGG-19 64.0% 57.2% 53.6% 73.5% 77.8% 58.0%
    ResNet-152 46.3% 46.3% 50.5% 47.0% 45.5% 84.0%

    Perturbations generated on VGG-19 fool more than 53% of images on all other architectures tested, including architecturally divergent models such as GoogLeNet (53.6%) and ResNet-152 (58.0%). This demonstrates that universal perturbations are doubly universal: image-agnostic and network-agnostic.

  5. Knowl 5 — Geometric Correlation and Low-Dimensional Normal Subspace of Decision Boundaries

    model/method

    The existence of universal perturbations is explained by high geometric correlations among the normal vectors to the decision boundary across natural image regions.

    Let r(xi)=argminrr2 s.t. k^(xi+r)k^(xi)r(x_i) = \arg\min_r \|r\|_2 \text{ s.t. } \hat{k}(x_i + r) \neq \hat{k}(x_i) denote the minimum adversarial perturbation vector for image xix_i, which is orthogonal to the decision boundary at xi+r(xi)x_i + r(x_i). The matrix collecting normalized decision boundary normals across nn validation images is: N=[r(x1)r(x1)2,,r(xn)r(xn)2]Rd×nN = \left[ \frac{r(x_1)}{\|r(x_1)\|_2}, \dots, \frac{r(x_n)}{\|r(x_n)\|_2} \right] \in \mathbb{R}^{d \times n}

    Singular value decomposition of NN on deep classifiers (such as CaffeNet) demonstrates that singular values decay rapidly compared to a matrix whose columns are sampled uniformly at random from the unit sphere. This indicates that decision boundary normal vectors across distinct natural images live in a shared low-dimensional subspace SRd\mathcal{S} \subset \mathbb{R}^d of dimension ddd' \ll d.

    A random vector of norm ξ=2000\xi = 2000 drawn uniformly from the 100-dimensional leading singular subspace of NN achieves a fooling rate of approximately 38% on unseen images, substantially exceeding the 10% fooling rate obtained from random isotropic vectors on the sphere of radius ξ=2000\xi = 2000 in Rd\mathbb{R}^d.

  6. Knowl 6 — Generalization of Universal Perturbations from Small Image Subsets

    empirical result

    Universal adversarial perturbations require only small sample sets XX to generalize across large unseen validation datasets.

    Evaluating the fooling rate on the 50,000-image ILSVRC 2012 validation set for GoogLeNet as a function of the size m=Xm = |X| of the training subset yields:

    • For m=500m = 500 training images (an average of 0.5 images per class across 1,000 ImageNet classes), the universal perturbation achieves a validation fooling rate exceeding 30%.
    • For m=1000m = 1000 training images, the validation fooling rate reaches approximately 36%.
    • For m=2000m = 2000 training images, the validation fooling rate reaches approximately 48%.
    • For m=4000m = 4000 training images, the validation fooling rate reaches approximately 68%.

    This sample efficiency confirms that universal directions of vulnerability are shared widely across the data distribution rather than overfitting to specific training exemplars.

  7. Knowl 7 — Comparative Vulnerability of Universal Against Alternative Perturbations

    empirical result

    Evaluating fooling rates on the ImageNet validation set across varying 2\ell_2 perturbation norms reveals fundamental differences between universal perturbations and alternative perturbation strategies:

    • The universal perturbation computed via iterative boundary projection reaches an 85% fooling rate at 2\ell_2 norm ξ=2000\xi = 2000, and exceeds 90% at ξ=3000\xi = 3000.
    • Adversarial perturbations computed for a single randomly selected image (via DeepFool or Fast Gradient Sign) achieve fooling rates below 35% at ξ=2000\xi = 2000 when applied globally to other images.
    • The sum of sample-specific adversarial perturbations across a dataset achieves lower fooling rates than universal perturbations at small perturbation norms.
    • Uniform random noise vectors sampled on the sphere of radius ξ=2000\xi = 2000 fool only 10% of images. The theoretical 2\ell_2 norm required for random noise to fool a classifier behaves as Θ(dr2)2×104\Theta(\sqrt{d}\|r\|_2) \approx 2 \times 10^4 (where dd is the input dimension and r2\|r\|_2 is the distance to the boundary), which is an order of magnitude larger than ξ=2000\xi = 2000.
    • The ImageNet dataset mean bias achieves negligible fooling capability across norm scales.
  8. Knowl 8 — Dominant Target Label Topology under Universal Perturbations

    empirical result

    Under universal adversarial perturbations, classification errors are not distributed uniformly across target classes, but instead map into a small set of dominant labels.

    Constructing a directed graph G=(V,E)G = (V, E), where vertices VV correspond to classification classes and a directed edge iji \to j indicates that the majority of images belonging to class ii are misclassified as class jj when perturbed, reveals a disconnected topology consisting of disjoint star-like connected components. Within each connected component, dozens of disparate source classes map directly to a single shared dominant label (such as 'great grey owl', 'digital clock', 'pillow', or 'quilt').

    These dominant labels represent large, expansive regions in the classifier's partitioning of the high-dimensional input space into which images are systematically projected by the universal perturbation vector.

  9. Knowl 9 — Diversity of Universal Perturbations

    empirical result

    Universal adversarial perturbations satisfying norm bound vpξ\|v\|_p \le \xi and fooling requirements are non-unique.

    Applying the iterative projection algorithm with different random permutations of the training dataset XX generates distinct universal perturbation vectors for the same network architecture (such as GoogLeNet with p=,ξ=10p = \infty, \xi = 10).

    The normalized inner product between any pair of distinct generated universal perturbation vectors va,vbv_a, v_b satisfies: va,vbva2vb20.1\frac{|\langle v_a, v_b \rangle|}{\|v_a\|_2 \|v_b\|_2} \le 0.1

    This indicates that multiple nearly orthogonal directions in input space can independently serve as effective universal perturbations with comparable fooling performance.

  10. Knowl 10 — Limitation of Adversarial Fine-Tuning Against Universal Perturbations

    limitation

    Fine-tuning deep neural networks on universally perturbed training samples provides limited robustness and does not immunize models against newly generated universal perturbations.

    Fine-tuning a VGG-F network for 5 epochs on a modified dataset—where 50% of the training samples are augmented with adaptive universal perturbations x+αvx + \alpha v sampled from a pre-computed pool of 10 universal vectors (with α\alpha being the smallest scaling factor causing misclassification)—reduces the validation fooling rate against the original perturbations from 93.7% to 76.2%.

    However, re-running the universal perturbation generation algorithm on the fine-tuned model (with p=,ξ=10p = \infty, \xi = 10) produces a new universal perturbation that achieves an 80.0% validation fooling rate. Iterating this fine-tuning and re-generation cycle multiple times fails to improve robustness beyond the ~76% fooling rate threshold.

Coverage note — None was omitted; all primary contributions—including the formal definition, iterative algorithm, empirical fooling rates across models, cross-model transferability, sample efficiency, normal vector subspace analysis, comparative baselines, dominant label graph topology, perturbation diversity, and defense fine-tuning limitations—are covered.

References

  1. 1.O. Bastani, Y. Ioannou, L. Lampropoulos, D. Vytiniotis, A. Nori, and A. Criminisi. Measuring neural net robustness with constraints. In Neural Information Processing Systems (NIPS), 2016.
  2. 2.K. Chatfield, K. Simonyan, A. Vedaldi, and A. Zisserman. Return of the devil in the details: Delving deep into convolutional nets. In British Machine Vision Conference, 2014.
  3. 3.A. Fawzi, O. Fawzi, and P. Frossard. Analysis of classifiers’ robustness to adversarial perturbations. CoRR, abs/1502.02590, 2015.
  4. 4.A. Fawzi, S. Moosavi-Dezfooli, and P. Frossard. Robustness of classifiers: from adversarial to random noise. In Neural Information Processing Systems (NIPS), 2016.
  5. 5.I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015.
  6. 6.K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  7. 7.R. Huang, B. Xu, D. Schuurmans, and C. Szepesvári. Learning with a strong adversary. CoRR, abs/1511.03034, 2015.
  8. 8.Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell. Caffe: Convolutional architecture for fast feature embedding. In ACM International Conference on Multimedia (MM), pages 675–678, 2014.
  9. 9.A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems (NIPS), pages 1097–1105, 2012.
  10. 10.Q. V. Le, W. Y. Zou, S. Y. Yeung, and A. Y. Ng. Learning hierarchical invariant spatio-temporal features for action recognition with independent subspace analysis. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, pages 3361–3368. IEEE, 2011.
  11. 11.S.-M. Moosavi-Dezfooli, A. Fawzi, and P. Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  12. 12.A. Nguyen, J. Yosinski, and J. Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 427–436, 2015.
  13. 13.E. Rodner, M. Simon, R. Fisher, and J. Denzler. Fine-grained recognition in the noisy wild: Sensitivity analysis of convolutional neural networks approaches. In British Machine Vision Conference (BMVC), 2016.
  14. 14.A. Rozsa, E. M. Rudd, and T. E. Boult. Adversarial diversity and hard positive generation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 2016.
  15. 15.O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. Berg, and L. Fei-Fei. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211–252, 2015.
  16. 16.S. Sabour, Y. Cao, F. Faghri, and D. J. Fleet. Adversarial manipulation of deep representations. In International Conference on Learning Representations (ICLR), 2016.
  17. 17.K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations (ICLR), 2014.
  18. 18.C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
  19. 19.C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR), 2014.
  20. 20.P. Tabacof and E. Valle. Exploring the space of adversarial images. IEEE International Joint Conference on Neural Networks, 2016.
  21. 21.Y. Taigman, M. Yang, M. Ranzato, and L. Wolf. Deepface: Closing the gap to human-level performance in face verification. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1701–1708, 2014.

Citation

MLA
Moosavi-Dezfooli, S.-M., et al. “Universal Adversarial Perturbations”. arXiv, 2016, http://arxiv.org/abs/1610.08401v3.
APA
Moosavi-Dezfooli, S.-M., Fawzi, A., Fawzi, O., & Frossard, P. (2016). Universal adversarial perturbations. arXiv. http://arxiv.org/abs/1610.08401v3
Chicago
Moosavi-Dezfooli, S.-M., A. Fawzi, O. Fawzi, and P. Frossard. 2016. “Universal Adversarial Perturbations”. arXiv. http://arxiv.org/abs/1610.08401v3.
Harvard
Moosavi-Dezfooli, S.-M. et al. (2016) “Universal adversarial perturbations”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1610.08401v3.
Vancouver
1. Moosavi-Dezfooli S-M, Fawzi A, Fawzi O, Frossard P (2016) Universal adversarial perturbations. arXiv

BibTeX

@article{moosavidezfooli2016universal,
  title = {Universal adversarial perturbations},
  author = {Moosavi-Dezfooli, Seyed-Mohsen and Fawzi, Alhussein and Fawzi, Omar and Frossard, Pascal},
  year = {2016},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1610.08401v3},
  eprint = {1610.08401}
}
Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: IEEE