Universal adversarial perturbations

Introduction

Can we find a single small image perturbation that fools a state-of-the-art deep neural network classifier on all natural images? We show in this paper the existence of such quasi-imperceptible universal perturbation vectors that lead to misclassify natural images with high probability. Specifically, by adding such a quasi-imperceptible perturbation to natural images, the label estimated by the deep neural network is changed with high probability (see Fig. 1). Such perturbations are dubbed universal, as they are image-agnostic. The existence of these perturbations is problematic when the classifier is deployed in real-world (and possibly hostile) environments, as they can be exploited by adversaries to break the classifier. Indeed, the perturbation process involves the mere addition of one very small perturbation to all natural images, and can be relatively straightforward to implement by adversaries in real-world environments, while being relatively difficult to detect as such perturbations are very small and thus do not significantly affect data distributions. The surprising existence of universal perturbations further reveals new insights on the topology of the decision boundaries of deep neural networks. We summarize the main contributions of this paper as follows:

We show the existence of universal image-agnostic perturbations for state-of-the-art deep neural networks.

We propose an algorithm for finding such perturbations. The algorithm seeks a universal perturbation for a set of training points, and proceeds by aggregating atomic perturbation vectors that send successive datapoints to the decision boundary of the classifier.

We show that universal perturbations have a remarkable generalization property, as perturbations computed for a rather small set of training points fool new images with high probability.

We show that such perturbations are not only universal across images, but also generalize well across deep neural networks. Such perturbations are therefore doubly universal, both with respect to the data and the network architectures.

We explain and analyze the high vulnerability of deep neural networks to universal perturbations by examining the geometric correlation between different parts of the decision boundary.

The robustness of image classifiers to structured and unstructured perturbations have recently attracted a lot of attention szegedy2013intriguing; sabour2016adversarial; tabacof2015exploring; fawzi2015a; nips2016_ours; nguyen2015; rodner2016; Rozsa_2016_CVPR_Workshops. Despite the impressive performance of deep neural network architectures on challenging visual classification benchmarks he2015deep; cv2; taigman2014deepface; le2011learning, these classifiers were shown to be highly vulnerable to perturbations. In szegedy2013intriguing, such networks are shown to be unstable to very small and often imperceptible additive adversarial perturbations. Such carefully crafted perturbations are either estimated by solving an optimization problem szegedy2013intriguing; moosavi2015deepfool; bastani2016measuring or through one step of gradient ascent goodfellow2014, and result in a perturbation that fools a specific data point. A fundamental property of these adversarial perturbations is their intrinsic dependence on datapoints: the perturbations are specifically crafted for each data point independently. As a result, the computation of an adversarial perturbation for a new data point requires solving a data-dependent optimization problem from scratch, which uses the full knowledge of the classification model. This is different from the universal perturbation considered in this paper, as we seek a single perturbation vector that fools the network on most natural images. Perturbing a new datapoint then only involves the mere addition of the universal perturbation to the image (and does not require solving an optimization problem/gradient computation). Finally, we emphasize that our notion of universal perturbation differs from the generalization of adversarial perturbations studied in szegedy2013intriguing, where perturbations computed on the MNIST task were shown to generalize well across different models. Instead, we examine the existence of universal perturbations that are common to most data points belonging to the data distribution.

Universal perturbations

The parameter $\xi$ controls the magnitude of the perturbation vector $v$, and $\delta$ quantifies the desired fooling rate for all images sampled from the distribution $\mu$.

Algorithm. Let $X=\{x_{1},\dots,x_{m}\}$ be a set of images sampled from the distribution $\mu$. Our proposed algorithm seeks a universal perturbation $v$, such that $\|v\|_{p}\leq\xi$, while fooling most data points in $X$. The algorithm proceeds iteratively over the data points in $X$ and gradually builds the universal perturbation, as illustrated in Fig. 2. At each iteration, the minimal perturbation $\Delta v_{i}$ that sends the current perturbed point, $x_{i}+v$, to the decision boundary of the classifier is computed, and aggregated to the current instance of the universal perturbation. In more details, provided the current universal perturbation $v$ does not fool data point $x_{i}$, we seek the extra perturbation $\Delta v_{i}$ with minimal norm that allows to fool data point $x_{i}$ by solving the following optimization problem:

Then, our update rule is given by $v\leftarrow\mathcal{P}_{p,\xi}(v+\Delta v_{i})$. Several passes on the data set $X$ are performed to improve the quality of the universal perturbation. The algorithm is terminated when the empirical “fooling rate” on the perturbed data set $X_{v}:=\{x_{1}+v,\dots,x_{m}+v\}$ exceeds the target threshold $1-\delta$. That is, we stop the algorithm whenever

The detailed algorithm is provided in Algorithm 1. Interestingly, in practice, the number of data points $m$ in $X$ need not be large to compute a universal perturbation that is valid for the whole distribution $\mu$. In particular, we can set $m$ to be much smaller than the number of training points (see Section 3).

The proposed algorithm involves solving at most $m$ instances of the optimization problem in Eq. (1) for each pass. While this optimization problem is not convex when $\hat{k}$ is a standard classifier (e.g., a deep neural network), several efficient approximate methods have been devised for solving this problem szegedy2013intriguing; moosavi2015deepfool; huang2015learning. We use in the following the approach in moosavi2015deepfool for its efficency. It should further be noticed that the objective of Algorithm 1 is not to find the smallest universal perturbation that fools most data points sampled from the distribution, but rather to find one such perturbation with sufficiently small norm. In particular, different random shufflings of the set $X$ naturally lead to a diverse set of universal perturbations $v$ satisfying the required constraints. The proposed algorithm can therefore be leveraged to generate multiple universal perturbations for a deep neural network (see next section for visual examples).

Universal perturbations for deep nets

We now analyze the robustness of state-of-the-art deep neural network classifiers to universal perturbations using Algorithm 1.

While the above universal perturbations are computed for a set $X$ of 10,000 images from the training set (i.e., in average $10$ images per class), we now examine the influence of the size of $X$ on the quality of the universal perturbation. We show in Fig. 6 the fooling rates obtained on the validation set for different sizes of $X$ for GoogLeNet. Note for example that with a set $X$ containing only $500$ images, we can fool more than $30\%$ of the images on the validation set. This result is significant when compared to the number of classes in ImageNet ($1000$), as it shows that we can fool a large set of unseen images, even when using a set $X$ containing less than one image per class! The universal perturbations computed using Algorithm 1 have therefore a remarkable generalization power over unseen data points, and can be computed on a very small set of training images.

Cross-model universality. While the computed perturbations are universal across unseen data points, we now examine their cross-model universality. That is, we study to which extent universal perturbations computed for a specific architecture (e.g., VGG-19) are also valid for another architecture (e.g., GoogLeNet). Table 2 displays a matrix summarizing the universality of such perturbations across six different architectures. For each architecture, we compute a universal perturbation and report the fooling ratios on all other architectures; we report these in the rows of Table 2. Observe that, for some architectures, the universal perturbations generalize very well across other architectures. For example, universal perturbations computed for the VGG-19 network have a fooling ratio above $53\%$ for all other tested architectures. This result shows that our universal perturbations are, to some extent, doubly-universal as they generalize well across data points and very different architectures. It should be noted that, in szegedy2013intriguing, adversarial perturbations were previously shown to generalize well, to some extent, across different neural networks on the MNIST problem. Our results are however different, as we show the generalizability of universal perturbations across different architectures on the ImageNet data set. This result shows that such perturbations are of practical relevance, as they generalize well across data points and architectures. In particular, in order to fool a new image on an unknown neural network, a simple addition of a universal perturbation computed on the VGG-19 architecture is likely to misclassify the data point.

Visualization of the effect of universal perturbations. To gain insights on the effect of universal perturbations on natural images, we now visualize the distribution of labels on the ImageNet validation set. Specifically, we build a directed graph $G=(V,E)$, whose vertices denote the labels, and directed edges $e=(i\rightarrow j)$ indicate that the majority of images of class $i$ are fooled into label $j$ when applying the universal perturbation. The existence of edges $i\rightarrow j$ therefore suggests that the preferred fooling label for images of class $i$ is $j$. We construct this graph for GoogLeNet, and visualize the full graph in the supp. material for space constraints. The visualization of this graph shows a very peculiar topology. In particular, the graph is a union of disjoint components, where all edges in one component mostly connect to one target label. See Fig. 7 for an illustration of two connected components. This visualization clearly shows the existence of several dominant labels, and that universal perturbations mostly make natural images classified with such labels. We hypothesize that these dominant labels occupy large regions in the image space, and therefore represent good candidate labels for fooling most natural images. Note that these dominant labels are automatically found by Algorithm 1, and are not imposed a priori in the computation of perturbations.

Fine-tuning with universal perturbations. We now examine the effect of fine-tuning the networks with perturbed images. We use the VGG-F architecture, and fine-tune the network based on a modified training set where universal perturbations are added to a fraction of (clean) training samples: for each training point, a universal perturbation is added with probability $0.5$, and the original sample is preserved with probability $0.5$. In this fine-tuning experiment, we use a slightly modified notion of universal perturbations, where the direction of the universal vector $v$ is fixed for all data points, while its magnitude is adaptive. That is, for each data point $x$, we consider the perturbed point $x+\alpha v$, where $\alpha$ is the smallest coefficient that fools the classifier. We observed that this feedbacking strategy is less prone to overfitting than the strategy where the universal perturbation is simply added to all training points. To account for the diversity of universal perturbations, we pre-compute a pool of $10$ different universal perturbations and add perturbations to the training samples randomly from this pool. The network is fine-tuned by performing $5$ extra epochs of training on the modified training set. To assess the effect of fine-tuning on the robustness of the network, we compute a new universal perturbation for the fine-tuned network (using Algorithm 1, with $p=\infty$ and $\xi=10$), and report the fooling rate of the network. After $5$ extra epochs, the fooling rate on the validation set is $76.2\%$, which shows an improvement with respect to the original network ($93.7\%$, see Table 1). This fine-tuning procedure moreover led to a minor increase in the error rate on the validation set, which might be due to a slight overfitting of the perturbed data. Despite this improvement, the fine-tuned network remains largely vulnerable to small universal perturbations. We therefore repeated the above procedure (i.e., computation of a pool of 10 universal perturbations for the fine-tuned network, fine-tuning of the new network based on the modified training set for $5$ extra epochs), and we obtained a new fooling ratio of $80.0\%$. In general, the repetition of this procedure for a fixed number of times did not yield any improvement over the $76.2\%$ fooling ratio obtained after one step of fine-tuning. Hence, while fine-tuning the network leads to a mild improvement in the robustness, we observed that this simple solution does not fully immune against small universal perturbations.

Explaining the vulnerability to universal perturbations

For each image $x$ in the validation set, we compute the adversarial perturbation vector $r(x)=\arg\min_{r}\|r\|_{2}\text{ s.t. }\hat{k}(x+r)\neq\hat{k}(x)$. It is easy to see that $r(x)$ is normal to the decision boundary of the classifier (at $x+r(x)$). The vector $r(x)$ hence captures the local geometry of the decision boundary in the region surrounding the data point $x$. To quantify the correlation between different regions of the decision boundary of the classifier, we define the matrix

of normal vectors to the decision boundary in the vicinity of $n$ data points in the validation set. For binary linear classifiers, the decision boundary is a hyperplane, and $N$ is of rank $1$, as all normal vectors are collinear. To capture more generally the correlations in the decision boundary of complex classifiers, we compute the singular values of the matrix $N$. The singular values of the matrix $N$, computed for the CaffeNet architecture are shown in Fig. 9. We further show in the same figure the singular values obtained when the columns of $N$ are sampled uniformly at random from the unit sphere. Observe that, while the latter singular values have a slow decay, the singular values of $N$ decay quickly, which confirms the existence of large correlations and redundancies in the decision boundary of deep networks. More precisely, this suggests the existence of a subspace $\mathcal{S}$ of low dimension $d^{\prime}$ (with $d^{\prime}\ll d$), that contains most normal vectors to the decision boundary in regions surrounding natural images. We hypothesize that the existence of universal perturbations fooling most natural images is partly due to the existence of such a low-dimensional subspace that captures the correlations among different regions of the decision boundary. In fact, this subspace “collects” normals to the decision boundary in different regions, and perturbations belonging to this subspace are therefore likely to fool datapoints. To verify this hypothesis, we choose a random vector of norm $\xi=2000$ belonging to the subspace $\mathcal{S}$ spanned by the first $100$ singular vectors, and compute its fooling ratio on a different set of images (i.e., a set of images that have not been used to compute the SVD). Such a perturbation can fool nearly $38\%$ of these images, thereby showing that a random direction in this well-sought subspace $\mathcal{S}$ significantly outperforms random perturbations (we recall that such perturbations can only fool $10\%$ of the data). Fig. 10 illustrates the subspace $\mathcal{S}$ that captures the correlations in the decision boundary. It should further be noted that the existence of this low dimensional subspace explains the surprising generalization properties of universal perturbations obtained in Fig. 6, where one can build relatively generalizable universal perturbations with very few images.

Unlike the above experiment, the proposed algorithm does not choose a random vector in this subspace, but rather chooses a specific direction in order to maximize the overall fooling rate. This explains the gap between the fooling rates obtained with the random vector strategy in $\mathcal{S}$ and Algorithm 1.

Conclusions

We showed the existence of small universal perturbations that can fool state-of-the-art classifiers on natural images. We proposed an iterative algorithm to generate universal perturbations, and highlighted several properties of such perturbations. In particular, we showed that universal perturbations generalize well across different classification models, resulting in doubly-universal perturbations (image-agnostic, network-agnostic). We further explained the existence of such perturbations with the correlation between different regions of the decision boundary. This provides insights on the geometry of the decision boundaries of deep neural networks, and contributes to a better understanding of such systems. A theoretical analysis of the geometric correlations between different parts of the decision boundary will be the subject of future research.

We gratefully acknowledge the support of NVIDIA Corporation with the donation of the Tesla K40 GPU used for this research.

References

Appendix A Appendix

Fig. 11 shows the original images corresponding to the experiment in Fig. . Fig. 12 visualizes the graph showing relations between original and perturbed labels (see Section for more details).