Year: 2019

Abstract:
Adversarial attacks such as Gradient-based attacks, Fast Gradient Sign Method (FGSM) by Goodfellow et al. (2015) and DeepFool by Moosavi-Dezfooli et al. (2016) are input-dependent, small pixel-wise perturbations of images which fool state of the art neural networks into misclassifying images but are unlikely to fool any human. On the other hand a universal adversarial attack is an input-agnostic perturbation. The same perturbation is applied to all inputs and yet the neural network is fooled on a large fraction of the inputs. In this paper, we show that multiple known input-dependent pixel-wise perturbations share a common spectral property. Using this spectral property, we show that the top singular vector of input-dependent adversarial attack directions can be used as a very simple universal adversarial attack on neural networks. We evaluate the error rates and fooling rates of three universal attacks, SVD-Gradient, SVD-DeepFool and SVDFGSM, on state of the art neural networks. We show that these universal attack vectors can be computed using a small sample of test inputs. We establish our results both theoretically and empirically. On VGG19 and VGG16, the fooling rate of SVD-DeepFool and SVD-Gradient perturbations constructed from observing less than 0.2% of the validation set of ImageNet is as good as the universal attack of Moosavi-Dezfooli et al. (2017a). To prove our theoretical results, we use matrix concentration inequalities and spectral perturbation bounds. For completeness, we also discuss another recent approach to universal adversarial perturbations based on (p, q)-singular vectors, proposed independently by Khrulkov & Oseledets (2018), and point out the simplicity and efficiency of our universal attack as the key difference.

heading: 1 INTRODUCTION
text: Neural network models achieve state of the art results on several image classification tasks. However, these models are known to be vulnerable to adversarial attacks. Szegedy et al. (2013) show that small, pixel-wise changes that are almost imperceptible to the human eye can make neural network models grossly misclassify images. Regarding an image as a vector x in Rd, an adversarial, pixelwise perturbation gives a small perturbation vector v ∈ Rd to perturb x so that the network classifies x+v differently from x. Szegedy et al. (2013) find such a perturbation vector using box-constrained L-BFGS. Goodfellow et al. (2015) propose the Fast Gradient Sign Method (FGSM) as a faster approach to find such an adversarial perturbation. In subsequent work on FGSM, its iterative variant was introduced by Kurakin et al. (2017) and another version called Projected Gradient Descent (PGD) by Madry et al. (2018). In the works of Goodfellow et al. (2015) and Madry et al. (2018), the adversarial perturbations considered are from an `∞-ball around the input x - namely, each pixel value is perturbed by a quantity within [− ,+ ]. DeepFool by Moosavi-Dezfooli et al. (2016) gives a method to compute a minimal `2-norm perturbation to fool the input. To understand how adversarial attacks transfer across different models Tramer et al. (2017) also study model-agnostic perturbations using the direction of the difference between the intra-class means.
Universal adversarial perturbations are input-agnostic so that the same perturbation fools the trained model on a large fraction of test inputs. Recent work by Moosavi-Dezfooli et al. (2017a;b) on universal adversarial perturbations looks at the curvature of the decision boundary. Their universal attacks are more sophisticated than the simple and fast, gradient-based adversarial perturbations, and require significantly more computation. In Moosavi-Dezfooli et al. (2017b) the authors give
a theoretical analysis of existence of universal adversarial perturbations using directions in which the decision boundary has positive curvature. Khrulkov & Oseledets (2018) propose a different method to construct a universal adversarial perturbation. Their perturbation is based on computing the (p, q)-singular vectors of the Jacobian matrices of hidden layers of the network.
The above discussion raises an important question: are there any interesting properties shared by the input dependent adversarial attacks which can be exploited to come up with an easy to compute universal perturbation? Can one find such a universal perturbation using only a small fraction of test inputs and also ensure that a perturbation along this direction fools most test inputs? We answer both of these questions affirmatively in this paper. Furthermore, we show that our universal attack compares favourably with the universal attack in Moosavi-Dezfooli et al. (2017a).

heading: 2 SUMMARY OF OUR MAIN RESULTS
text: • Our first observation is that even though the adversarial attack directions are inputdependent, overall they have only a small number of dominant principal components. We show this for attacks based on the Gradient of the loss function, the FGSM attack and DeepFool, on a variety of architectures and datasets.
• Construct a matrix whose i-th row is an input dependent attack vector on the i-th test point. Our second observation is that a small pixel-wise perturbation in the direction of the top principal component of this matrix alone can be used as a universal attack. This simple algorithm gives us SVD-Gradient, SVD-FGSM and SVD-DeepFool perturbations.
• Our third observation is that the top principal component can be well-approximated from a very small sample of the test data, and small samples are good enough to obtain SVDUniversal perturbations comparable to that in Moosavi-Dezfooli et al. (2017a).
• We give a theoretical justification of this phenomenon using matrix concentration inequalities and spectral perturbation bounds. This observation holds across multiple inputdependent adversarial attack directions given by Gradient, FGSM and DeepFool.

heading: 3 DEFINITIONS AND THE PROBLEM FORMULATION
text: Assume that we have a distribution D on pairs of images and labels, with images coming from a set X . In the case of CIFAR-10 for example we can think of X to be a set of all 32 × 32 images with pixel values from [0, 1]. Let (X,Y ) be a sample from D and let f : X → [k], be a k-class classifier. The natural accuracy δ of the classifier f is defined to be
Pr(X,Y )∈D[f(X) = Y ].
We regard a deterministic adversary to be a function A : X → X . The error rate of A on the classifier f is defined to be Pr(X,Y )∈D[f(X +A(X)) 6= Y ]. WhenA is a distribution over functions, we get a randomized adversary. The norm of the perturbation applied to X is the norm of A(X) (we only consider `2 norm in this paper). In Moosavi-Dezfooli et al. (2017a;b) and in Khrulkov & Oseledets (2018) the authors consider the fooling rate of an adversary and not the error rate. Recall that f is said to be fooled on input x by the perturbation A(x) if f(x) 6= f(x+A(x)). And the fooling rate is defined to be the probability that f is fooled by choosing x at random. Note that
Pr(X,Y )∈D[f(X +A(X)) 6= Y ] = Pr(X,Y )[f(X +A(X)) 6= Y |f(X) = Y ] Pr(X,Y )[f(X) = Y ] + Pr(X,Y )[f(X +A(X)) 6= Y |f(X) 6= Y ] Pr(X,Y )[f(X) 6= Y ] ≤ Pr(X,Y )[f(X +A(X)) 6= Y |f(X) = Y ] + (1− δ).
So, if the natural accuracy of the classifier is high, the fooling rate is close to the error rate.
Pr(X,Y )[f(X +A(X)) 6= f(X)] ≥ Pr(X,Y )[f(X +A(X)) 6= Y ]− (1− δ).
The error rate of the adversary with zero perturbation is the error rate of the trained network, whereas the fooling rate of the adversary with zero perturbation is necessarily zero. However, small fooling rate does not necessarily imply small error rate, especially when the natural accuracy is not close to 100%. Note that existing models such as VGG16, VGG19, ResNet50 do not achieve natural accuracy greater than 0.8.

heading: 3.1 INPUT DEPENDENT ATTACKS
text: There are a number of input dependent attacks known and our generic algorithm can be used to produce a universal adversary from each of them. We demonstrate the effectiveness of our method by applying it to a few popular input dependent attacks, which we discuss below. Let L(θ, x, y) denote the loss function used to train the model. Here θ are the model parameters, x is the input and y is the class label.
In the Gradient attack the adversarial example produced on input x is
x′ = x+ ∇xL(θ, x, y).
In the FGSM attack proposed by Goodfellow et al. (2015) the adversarial example produced on input x is x′ = x+ sign (∇xL(θ, x, y)) . So the perturbed input is within an `∞ ball of radius about x.
DeepFool proposed by Moosavi-Dezfooli et al. (2016) is an iterative algorithm. At each stage of the iteration the region of space around the current perturbed input xt where the classifier outputs label f(xt) is approximated by a polyhedron Pt. xt is projected to the closest face of Pt. We stop at the smallest t for which f(x) 6= f(xt).

heading: 3.2 EXISTING UNIVERSAL ATTACKS
text: In Moosavi-Dezfooli et al. (2017a), the authors fix a budget , a bound on the allowed `2 norm of the attack1 and also the desired fooling rate. They pick a sample S of the training data. Starting with the zero perturbation v, the algorithm proceeds in stages as long as the fooling rate of the current perturbation vector v is less than the desired fooling rate on S. They run over x ∈ S, for which f(x) = f(x+ v). For each such x they find the smallest perturbation rx sending x to the boundary (using DeepFool) and v is updated to Π(v + rx) where Π is the projection onto the ball of radius .
In Khrulkov & Oseledets (2018) the authors consider the outputs fi(x) of the i-th hidden layer of a network on an input x. Denote by Ji(x) the matrix of partial derivatives ∂fi(x) ∂x evaluated at x. They pick a sample S of X of size m and compute for each x ∈ S, Ji(x). Stacking these in different rows of a matrix J , they use as their universal attack the vector argmax||Jv||q subject to ||v||p = 1. In Mopuri et al. (2017) the authors propose a universal attack which is completely data independent. It only depends upon the model architecture. Given a trained neural network with K hidden (convolution) layers, the authors start with a random image v and minimize Πi=Ki=1 ¯̀i(v), ||v||∞ ≤ . Here ¯̀ i(v) is the mean activation of layer i when the input is v. The authors show that the perturbation v achieving the minimum is a data agnostic attack and achieves a reasonable fooling rate.

heading: 4 UNIVERSAL ADVERSARIAL ATTACK USING A SMALL SAMPLE

heading: 4.1 SVD-UNIVERSAL ALGORITHM
text: Algorithm 1 gives the pseudocode to construct a universal attack for a given model. The output of the algorithm is a universal attack vector, and this depends upon the input dependent attack used.
It is the simplicity of the algorithm which we would like to emphasize. The algorithm samples a set of n images from the test set. We use the terms batch size and sample size interchangeably. For each of the sample points it computes an input-dependent attack direction. We stack these attack
1the authors consider other `p norms as well. We restrict ourselves to the `2-norm.
directions in a matrix, one for each of the sample points and return the top singular vector of the matrix of attack directions as our SVD-Universal.
Algorithm 1: SVD-Universal Algorithm Data: Network N , any input-dependent adversarial attack A, and n test samples. Result: A universal attack direction for network N
1 Obtain input-dependent perturbation vectors a1, ..., an based on A for the n test samples. 2 Normalize ai’s to get only the attack directions or unit vectors ui = ai/||ai||2, for i = 1 to n. 3 Form a matrix M whose rows are u1, u2, . . . , un. 4 Compute Singular Value Decomposition (SVD) of M as M = USV T , with V = [v1|v2| . . . |vn]. 5 Return the top right singular vector v1 as the universal attack vector.

heading: 4.2 ERROR RATES AND FOOLING RATES OF SVD-UNIVERSAL
text: We evaluate the fooling rate of SVD-Gradient, SVD-FGSM and SVD-DeepFool on the validation set of the ImageNet dataset on VGG16, VGG19 and ResNet50. We used off the shelf code available for these architectures. In these architectures pixel intensities of images are scaled down and images are normalized before they are deployed for use in classifiers. Our (unit) attack vectors are constructed using batch sizes of 64(0.13%), 128(0.26%)) and 1024(2%).
In Figure 1, we plot the fooling rate of v as a function of , in all the architectures, where v is obtained using a batch size of 64. The top left plot is the fooling rate of SVD-gradient, the top right that of SVD-FGSM and the bottom left that of SVD-DeepFool. We explain the bottom right plot in the next section. SVD-Gradient attack scaled to have norm 50 fools about 32% of the validation set of ImageNet on VGG19. Note that the average `2 norm of this validation set is 4502 and using the language of Moosavi-Dezfooli et al. (2017a), a perturbation with norm 50 is also quasi-imperceptible. We visualize the perturbed images in Figure 4 in Appendix A.1.
We plot the error rate of SVD-Universal for ImageNet on VGG19 in Figure 5, Appendix A.1, on different batch sizes. It is clear from the plots that SVD-Universal attacks obtained using batch size of 64 perform as well (and sometimes better) as attack vectors obtained using larger batch sizes.
In Appendix A.2 we plot the error rate of SVD-Universal attacks on CIFAR-10 trained on ResNet18. On ResNet18, the error rate of SVD-DeepFool obtained from 100 samples of the CIFAR-10 test data is 0.55 when it is scaled to norm 15 (0.23 of the average norm), see Figure 6. We notice that the SVD-Universal perturbations constructed with small batch sizes perform better.
The visualizations of our perturbations as images are given in Appendix B.
4.3 COMPARISON WITH MOOSAVI-DEZFOOLI ET AL. (2017A), KHRULKOV & OSELEDETS (2018)
In this section we compare our results with that reported in Moosavi-Dezfooli et al. (2017a) and Khrulkov & Oseledets (2018) on the validation set of Imagenet. The pixel intensities of the dataset used in the experiments of Moosavi-Dezfooli et al. (2017a) and Khrulkov & Oseledets (2018) are in the range [0, 255]. The average `2 norm of the validation set is 50,000 and the average `∞ norm is 250, Moosavi-Dezfooli et al. (2017a, Footnote, Page 4). The `2 norm of the universal perturbation used in Moosavi-Dezfooli et al. (2017a) is 1/25 of 50,000 = 2000. The `∞ norm of the universal perturbation used in Khrulkov & Oseledets (2018) is 1/25 of 250 = 10. The pixel intensities of the validation set of Imagenet used in our experiments is normalized and the average `2 norm of this normalized dataset is 450.
In (Khrulkov & Oseledets, 2018, Figure 9) the authors report that the universal perturbation of Moosavi-Dezfooli et al. (2017a) constructed from a batch size 64 and having `∞ norm 10 has a fooling rate of 0.14 on VGG19. A comparable perturbation in our model has `2 norm 1/25 of 450 = 18. Figure 1 shows that SVD-Gradient and SVD-DeepFool perturbation with norm 18 give a fooling rate of 0.13 on VGG19.
2https://github.com/pytorch/examples/tree/master/imagenet
To further compare our universal perturbations with that of Moosavi-Dezfooli et al. (2017a), the same 64 samples used to construct our SVD-Universal vectors were used to obtain the universal perturbation vector, M-DFFF, of Moosavi-Dezfooli et al. (2017a). This vector was scaled down to get a unit vector w in `2 norm. In Figure 1 (right bottom) we plot the fooling rate of M-DFFF w as a function of , in all the architectures. We observe trends similar to what was reported in Moosavi-Dezfooli et al. (2017a, Table 1) - the error rate achieved by M-DFFF on VGG16 is higher than that of M-DFFF on VGG19. Observe from this figure that on VGG19, the M-DFFF universal perturbation of `2 norm 18 gives a fooling rate of 0.13.
The plots in Figure 1 of the fooling rates of the four universal attacks on VGG16 and ResNet50 are are collated together in Figure 2. We also plot the error rate of these universal attacks on VGG16 and ResNet50. SVD-DeepFool and M-DFFF have comparable fooling and error rates for ImageNet on the two networks.
Khrulkov & Oseledets (2018) get a fooling rate of more than 0.4 using batch size of 64 and `∞ norm 10. At this norm their universal attack is stronger than both our attack and that of MoosaviDezfooli et al. (2017a). However Khrulkov & Oseledets (2018) do an extensive experimentation and determine which intermediate layer to attack and (p, q) are also optimized to maximize the fooling rate of their (p, q)-singular vector. However (p, q)-SVD computation is expensive and is known to be a hard problem, (Bhaskara & Vijayaraghavan, 2011; Bhattiprolu et al., 2019). We do no such optimization and use p = q = 2, our emphasis being on the simplicity of our SVD-Universal algorithm. We also observe a trend similar to what is reported by Khrulkov & Oseledets (2018) - the error rate of SVD-Universal attacks is higher on VGG16 and VGG19 than on ResNet50.
Figure 7 in Appendix A.2 compares the error rates of SVD-Universal attacks and M-DFFF constructed using samples of size 100 from the test data of CIFAR-10 on ResNet18. Error rates of SVD-DeepFool and M-DFFF are comparable - for this dataset, SVD-Gradient is not as good. When the norm of the perturbation is about 15 (0.23 of the average norm), the error rate of SVD-DeepFool fool is about 0.55.

heading: 5 THEORETICAL ANALYSIS OF OUR UNIVERSAL PERTURBATION
text: In this section, we attempt to provide a theoretical justification for the existence of universal adversarial perturbations. Let our data be given by a joint distribution D on feature vectors in Rd and corresponding true labels in [k] = {1, 2, . . . , k}. Let (X,Y ) denote a random sample from D. Let f : Rd → [k] be a given classifier, and for any x ∈ Rd, letA(x) be its adversarial perturbation given by a fixed adversarial attack A, e.g., FGSM, DeepFool. As in Moosavi-Dezfooli et al. (2017b), the fooling rate of this attack is given by Pr (f(X) 6= f(X +A(X))), where the probability is over the data distribution D. Define A = {x : f(x) 6= f(x + A(x)}. For any x ∈ A, assume that x + A(x) lies on the decision boundary, and let the hyperplane Hx = {x+ z ∈ Rd : 〈z,A(x)〉 = ‖A(x)‖22} be a local, linear approximation to the decision boundary at x +A(x). This holds for adversarial attacks such as DeepFool by Moosavi-Dezfooli et al. (2016) which try to find an adversarial perturbation A(x) such that x +A(x) is the nearest point to x on the decision boundary. Now consider the halfspace Sx = {x+z ∈ Rd : 〈z,A(x)〉 ≥ ‖A(x)‖22}. Note that x /∈ Sx and x+A(x) ∈ Sx. For simplicity of analysis, we assume that f(x) 6= f(x + z), for all x ∈ A and x + z ∈ Sx. This is a reasonable assumption in a small neighborhood of x, and is implied by the positive curvature of the decision boundary assumed in the analysis of Moosavi-Dezfooli et al. (2017b). In other words, we assume that if an adversarial perturbation such as A(x) fools the model at input x, then any perturbation z, where z has a sufficient projection along A(x), also fools the model at x, and this is a reasonable assumption in a small neighborhood of x.
Theorem 1. Given any joint data distributionD on features or inputs in Rd and true labels in [k], let (X,Y ) denote a random sample from D. For any x ∈ Rd, let A(x) be its adversarial perturbation by a fixed input-dependent adversarial attack A. Let
M = E [ A(X) ‖A(X)‖2 A(X)T ‖A(X)‖2 ] ∈ Rd×d,
and 0 ≤ λ ≤ 1 be the top eigenvalue of M and v ∈ Rd be the corresponding eigenvector (normalized to have unit `2 norm). Then under the assumption that f(x) 6= f(x + z), for all x ∈ A and x + z ∈ Sx, we have
Pr (f(X + u) 6= f(X)) ≥ Pr (f(X) 6= f(X +A(X)))− 1− λ 1− δ2 ,
where u = ±( /δ)v, where = max x ‖A(x)‖2.
Proof. Let µ(x) denote the induced probability density on features or inputs by the distribution D. Define A = {x : f(x) 6= f(x +A(x)} and G = {x : |〈A(x),v〉| ≥ δ ‖A(x)‖2}. Since λ is the top eigenvalue of M with v as its corresponding (unit) eigenvector,
λ = E [〈 A(X) ‖A(X)‖2 ,v 〉2]
= ∫ x∈G 〈 A(x) ‖A(x)‖2 ,v 〉2 µ(x)dx + ∫ x/∈G 〈 A(x) ‖A(x)‖2 ,v 〉2 µ(x)dx
≤ ∫ x∈G µ(x)dx + δ2 ∫ x/∈G µ(x)dx because ‖v‖2 = 1
= Pr (G) + δ2 (1− Pr (G)) = (1− δ2) Pr (G) + δ2.
Thus, Pr (G) ≥ (λ − δ2)/(1 − δ2), and equivalently, Pr (Gc) = 1 − Pr (G) ≤ (1 − λ)/(1 − δ2). Now for any x ∈ G, we have |〈A(x),v〉| ≥ δ ‖A(x)‖2. Letting = maxx ‖A(x)‖2, we get |〈A(x), ( /δ)v〉| ≥ ‖A(x)‖22. Thus, x ± ( /δ)v ∈ Sx, where Sx = {x + z ∈ Rd : 〈z,A(x)〉 ≥ ‖A(x)‖22}, and therefore, by our assumption stated before Theorem 1, we have f(x) 6= f(x + u), where u = ±( /δ)v. Putting all of this together, Pr (f(X + u) 6= f(X)) ≥ Pr (G ∩A) ≥ Pr (A)− Pr (A ∩Gc) ≥ Pr (A)− Pr (Gc), and therefore,
Pr (f(X + u) 6= f(X)) ≥ Pr (f(X) 6= f(X +A(X)))− 1− λ 1− δ2 ,
Theorem 1 shows that any norm-bounded, input-dependent, adversarial attack A can be converted into a universal attack u of comparable norm, without losing much in the fooling, if the top eigenvalue λ of M is close to 1. This universal attack direction lies in the one-dimensional span of the top eigenvector v of M . The proof of Theorem 1 can be easily generalized to the top SVD subspace of M and where the top few eigenvalues of M dominate its spectrum (note that tr (M) = 1).
Singular value drop We empirically verify our hypothesis about top eigenvalue (or the top few eigenvalues) dominating the spectrum ofM in Theorem 1. LetX1, X2, . . . , Xm bem i.i.d. samples of X drawn from the distribution D and consider the unnormalized, empirical analog of M as follows,
m∑ i=1 A(Xi) ‖A(Xi)‖2 A(Xi)T ‖A(Xi)‖2 .
Figure (3) shows how the singular values drop for the three input dependent attacks, Gradient, FGSM, and DeepFool on CIFAR-10 trained on ResNet18 on batch sizes 500 and 10,000. These plots indicate that the drop in singular values is a shared phenomenon across different input dependent attacks, and the trend is similar even when we look at a small number of input samples.
Our second contribution is finding a good approximation to the universal adversarial perturbation given by the top eigenvector v of M , using only a small sample X1, X2, . . . , Xm from the distributionD. Theorem 2 shows that we can efficiently pick such a small sample whose size is independent ofD, depends linearly on the intrinsic dimension ofM , and logarithmically on the feature dimension d.
Theorem 2. Given any joint data distribution D on features in Rd and true labels in [k], let (X,Y ) denote a random sample from D. For any x ∈ Rd, let A(x) denote the adversarial perturbation of x according a fixed input-dependent adversarial attack A. Let
M = E [ A(X) ‖A(X)‖2 A(X)T ‖A(X)‖2 ] ∈ Rd×d.
Let 0 ≤ λ = ‖M‖2 ≤ 1 denote the top eigenvalue of M and let v denote its corresponding eigenvector (normalized to have unit `2 norm). Let r = tr (M) / ‖M‖2 be the intrinsic dimension of M . LetX1, X2, . . . , Xm bem i.i.d. samples ofX drawn from the distributionD, and let λ̃ = ∥∥∥M̃∥∥∥ 2 be the top eigenvalue of the matrix M̃ ,
M̃ = 1
m m∑ i=1 A(Xi) ‖A(Xi)‖2 A(Xi)T ‖A(Xi)‖2 ,
and ṽ be the top eigenvector of M̃ .
Also suppose that there is a gap of at least γλ between the top eigenvalue λ and the second eigenvalue of M . Then for any 0 ≤ < γ and m = O( −2r log d), we get ‖v − ṽ‖2 ≤ /γ, with a constant probability. This probability can be boosted to 1 − δ by having an additional log(1/δ) in the O(·).
Proof. Take m = O( −2r log d). By the covariance estimation bound in Theorem 4 and Markov’s inequality, we get that ∥∥∥M − M̃∥∥∥ 2 ≤ λ, with a constant probability. Applying Theorem 5 due
to Weyl on eigenvalue perturbation, we get ∣∣∣λ− λ̃∣∣∣ ≤ λ. Moreover, if there is gap of at least γλ
between the first and the second eigenvalue of M with γ > , we can use the well-known Theorem 6 of Davis-Kahan to bound the difference between the corresponding eigenvectors as ‖v − ṽ‖2 ≤ /γ, with a constant probability. Please see Appendix D, and the book by Vershynin (2018) cited therein, for more details about the covariance estimation bound, Weyl’s theorem, and Davis-Kahan theorem.
The theoretical bounds are weaker than our empirical observations about the number of test samples needed for the universal attack. What we want to highlight is that the bound in Theorem 2 is independent of the support of underlying data distributionD and depends only on its dimensionality d. There is more room to tighten our analysis using additional properties of the data distribution as well as the spectral properties of M .

heading: 6 UNIVERSAL INVARIANT PERTURBATIONS AND FUTURE DIRECTIONS
text: Let x be an image for which the predicted label of a neural network classifier f is f(x). For highly accurate classifiers trained on data that already contains small rotation augmentations, one would
expect f(x+∆(x)) = f(x), where x+∆(x) is the image resulting from a small rotation applied to x. For an image x, we call I(x) an invariant perturbation for x, if f(x + I(x)) = f(x). Using this terminology we expect ∆(x) to be an invariant perturbation for x for classifiers trained on data that is inherently (or additionally) augmented with small rotations. A natural question is whether there are any universal invariant perturbations x + u that are invariant for most x. We show empirically that there are such universal invariant perturbations. By their very definition we would also expect that universal invariant perturbations will not be universal adversarial perturbations. We show this empirically by plotting the error rates of the top singular invariant perturbation of CIFAR-10 on ResNet18 in Figure 10, Appendix C. The error rate is below 0.2 even when the norm of the invariant perturbation is scaled up to 50. We give more empirical evidence of such invariant perturbations - we show that the principal angles between the subspace of the top 5 universal adversarial perturbations and the subspace of the top 5 universal invariant perturbations are all close to 90◦.
The empirical and theoretical results in this paper hold in greater generality than what we have presented. Our experiments indicate the existence of universal adversarial perturbations and universal invariant perturbations for datasets trained on equivariant networks. GCNN’s Cohen & Welling (2016) are among the more popular equivariant networks, and achieve state of the art on CIFAR-10. In Appendix C we give a peek into this work and show plots of the error rates of SVD-Universal on CIFAR-10 on GCNN’s. We also plot the singular values of CIFAR-10 on GCNN’s.
It is common to augment data with rotations and train neural networks, so they become equivariant to rotations and so an image and its rotation are classified the same. We believe that a study of how the subspaces of universal adversarial perturbations and universal invariant perturbations change as a model is trained to handle more and more rotations will be important. This is ongoing work.

heading: 7 CONCLUSION
text: We show how to use a small sample of input-dependent adversarial attack directions on test inputs to find a single universal adversarial perturbation that results in a large drop in the accuracy of state of the art neural network models. Our main observation is a spectral property shared by different attacks directions such as Gradients, FGSM, DeepFool. We give a theoretical justification for how this spectral property helps in using the top singular vector as a universal attack direction. We justify theoretically and empirically that such a perturbation can be computed using only a small sample of test inputs. Our empirical results also indicate that these universal perturbations are almost orthogonal to perturbations of inputs that these models are invariant to.

heading: APPENDIX A DATA SETS AND MODEL ARCHITECTURES USED
text: Data sets CIFAR-10 dataset consists of 60, 000 images of 32 × 32 size, divided into 10 classes. 40, 000 used for training, 10, 000 for validation and 10, 000 for testing. ImageNet dataset refers to ILSRVC 2012 dataset (Russakovsky et al., 2015) which consists of images of 224 × 224 size, divided into 1000 classes. We use the validation set of 50, 000 images for our testing purposes.
All experiments performed on neural network-based models were done using the validation set of ImageNet and test set of CIFAR-10 datasets.
Model Architectures For the ImageNet based experiments we use pre-trained networks of VGG16, VGG19 and ResNet50 architectures3. For the CIFAR-10 based experiments we use the ResNet18 architecture as in He et al. (2016).
3https://pytorch.org/docs/stable/torchvision/models.html
A.1 SVD-UNIVERSAL ON IMAGENET
Figure 4 shows that the images with SVD-DeepFool perturbations upto norm 100 are quasiimperceptible. Figure 5 shows the error rate of SVD-Universal on VGG19 calculated with varying sample size.
A.2 SVD-UNIVERSAL ON CIFAR-10
In this section we plot the error rates of SVD-Universal on CIFAR-10 trained on ResNet18.

heading: APPENDIX B VISUALIZING SVD-UNIVERSAL PERTURBATIONS
text: We visualize the top singular vectors for the Gradient, FGSM, DeepFool directions from ImageNet and CIFAR-10 in this section.

heading: APPENDIX C INVARIANT PERTURBATIONS
text: C.1 PRINCIPAL COMPONENTS OF ATTACK AND INVARIANT DIRECTIONS
To construct the matrix, we pick a batch of 100 images, and for each image x in our sample we compute the difference between x and its 2 degree rotation. We stack these (input dependent invariant directions) as rows of the matrix and compute the top singular (unit) vector w. We call w the universal invariant perturbation. Figure 10 shows the error rate of w as a function of on CIFAR-10. The curves are flat indicating that these directions are invariant perturbations.
Recall that for two subspaces V ,W , the first principal angle is defined as the minimum angle between two unit vectors v1 ∈ V , w1 ∈ W . The second principal angle is the minimum angle between unit vectors v2 ∈ V,w2 ∈ W , with v2 ⊥ v1 and w2 ⊥ w1. The other principal angles are defined similarly.

heading: APPENDIX D PROOF DETAILS
text: Theorem 5.6.1 (General covariance estimation) from Vershynin (2018) bounds the spectral norm of covariance matrix estimated from a small number of samples as follows. Theorem 3. Let X be a random vector in Rd, d ≥ 2. Assume that for some K ≥ 1, ‖X‖2 ≤
K ( E [ ‖X‖22 ])1/2 , almost surely. Let Σ = E [ XXT ] be the covariance matrix of X and Σm =
1 m ∑m i=1XiX T i be the estimated covariance fromm i.i.d. samplesX1, X2, . . . , Xm. Then for every positive integer m, we have
E [‖Σm − Σ‖2] ≤ C
(√ K2d log d
m + K2d log d m ) ‖Σ‖2 ,
for some positive constant C and ‖Σ‖2 being the spectral norm (or the top eigenvalue) of Σ.
Note that using m = O( −2d log d) we get E [‖Σm − Σ‖2] ≤ ‖Σ‖2. A tighter version of Theorem 5.6.1 appears as Remark 5.6.3, when the intrinsic dimension r = tr (Σ) / ‖Σ‖2 d. Theorem 4. Let X be a random vector in Rd, and d ≥ 2. Assume that for some K ≥ 1, ‖X‖2 ≤
K ( E [ ‖X‖22 ])1/2 , almost surely. Let Σ = E [ XXT ] be the covariance matrix of X and Σm =
1 m ∑m i=1XiX T i be the estimated covariance fromm i.i.d. samplesX1, X2, . . . , Xm. Then for every positive integer m, we have
E [‖Σm − Σ‖2] ≤ C
(√ K2r log d
m + K2r log d m ) ‖Σ‖2 ,
for some positive constant C and ‖Σ‖2 being the operator norm (or the top eigenvalue) of Σ.
Note that using m = O( −2r log d) we get E [‖Σm − Σ‖2] ≤ ‖Σ‖2. Theorem 4.5.3 (Weyl’s Inequality) from Vershynin (2018) upper bounds the difference between i-th eigenvalues of two symmetric matrices A and B using the spectral norm of A−B. Theorem 5. For any two symmetric matrices A and B in Rd×d, |λi(A)− λi(B)| ≤ ‖A−B‖2, where λi(A) and λi(B) are the i-th eigenvalues of A and B, respectively.
In other words, the spectral norm of matrix perturbation bounds the stability of its spectrum.
Here is a special case of Theorem 4.5.5 (Davis-Kahan Theorem) and its immediate corollary mentioned in Vershynin (2018). Theorem 6. Let A and B be symmetric matrices in Rd×d. Fix i ∈ [d] and assume that the largest eigenvalue of A is well-separated from the rest of the spectrum, that is, λ1(A) − λ2(A) ≥ δ > 0. Then the angle θ between the top eigenvectors v1(A) and v1(B) of A and B, respectively, satisfies sin θ ≤ 2 ‖A−B‖2 /δ. As an easy corollary, it implies that the top eigenvectors v1(A) and v1(B) are close to each other up to a sign, namely, there exists s ∈ {−1, 1} such that
‖v1(A)− s v1(B)‖2 ≤ 23/2 ‖A−B‖2
δ .

heading: APPENDIX E ERROR RATES OF CIFAR-10 ON GCNN’S
text: For a fair comparison, the GCNN configuration used for CIFAR-10 is the same as that of ResNet18, except that the operations going from one layer to the next are replaced by equivalent GCNN operations, as given in Cohen & Welling (2016).

heading: APPENDIX F TABLES REQUESTED BY REVIEWERS

Review summaries:
This paper presents a universal adversarial attack, which firstly conducts existing gradient-based attacks on the sample images and then applies SVD on the perturbations from those attacks. The universal attacks are the right singular vectors of the SVD.  The experiments are conducted on attacking VGG and ResNet. In addition, theoretical analysis is also provided in the paper.