Title: UNIVERSAL ADVERSARIAL ATTACK USING VERY FEW TEST EXAMPLES

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 SVD-FGSM, 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.

1. INTRODUCTION:

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 R d , an adversarial, pixelwise perturbation gives a small perturbation vector v ∈ R d 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) .

2. SUMMARY OF OUR MAIN RESULTS:

• 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 SVD-Universal 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.

3. DEFINITIONS AND THE PROBLEM FORMULATION:

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)) = Y ].

When A 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) = 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)) = Y ] = Pr (X,Y ) [f (X + A(X)) = Y |f (X) = Y ] Pr (X,Y ) [f (X) = Y ] + Pr (X,Y ) [f (X + A(X)) = Y |f (X) = Y ] Pr (X,Y ) [f (X) = Y ] ≤ Pr (X,Y ) [f (X + A(X)) = 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)) = f (X)] ≥ Pr (X,Y ) [f (X + A(X)) = 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.

3.1. INPUT DEPENDENT ATTACKS:

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 + ∇ x L(θ, x, y).

In the FGSM attack proposed by Goodfellow et al. (2015) the adversarial example produced on input

x is x = x + sign (∇ x L(θ, 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 x t where the classifier outputs label f (x t ) is approximated by a polyhedron P t . x t is projected to the closest face of P t . We stop at the smallest t for which f (x) = f (x t ).

3.2. EXISTING UNIVERSAL ATTACKS:

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 r x sending x to the boundary (using DeepFool) and v is updated to Π(v + r x ) where Π is the projection onto the ball of radius .

In Khrulkov & Oseledets (2018) the authors consider the outputs f i (x) of the i-th hidden layer of a network on an input x. Denote by J i (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, J i (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=K i=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.

4. UNIVERSAL ADVERSARIAL ATTACK USING A SMALL SAMPLE:



4.1. SVD-UNIVERSAL ALGORITHM:

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 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 Obtain input-dependent perturbation vectors a 1 , ..., a n based on A for the n test samples. Normalize a i 's to get only the attack directions or unit vectors

u i = a i /||a i || 2 , for i = 1 to n. Form a matrix M whose rows are u 1 , u 2 , . . . , u n . Compute Singular Value Decomposition (SVD) of M as M = U SV T , with V = [v 1 |v 2 | . . . |v n ].

Return the top right singular vector v 1 as the universal attack vector.

4.2. ERROR RATES AND FOOLING RATES OF SVD-UNIVERSAL:

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. 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. 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 Moosavi-Dezfooli 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. 2017b), the fooling rate of this attack is given by Pr (f (X) = f (X + A(X))), where the probability is over the data distribution D.

VGG16 ResNet50:

Define A = {x : f (x) = f (x + A(x)}.

For any x ∈ A, assume that x + A(x) lies on the decision boundary, and let the hyperplane

EQUATION

2 } 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

S x = {x + z ∈ R d : z, A(x) ≥ A(x) 2 2 }. Note that x / ∈ S x and x + A(x) ∈ S x .

For simplicity of analysis, we assume that f (x) = f (x + z), for all x ∈ A and x + z ∈ S x . 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 distribution D on features or inputs in R d and true labels in [k], let (X, Y ) denote a random sample from D. For any x ∈ R d , let A(x) be its adversarial perturbation by a fixed input-dependent adversarial attack A. Let and 0 ≤ λ ≤ 1 be the top eigenvalue of M and v ∈ R d be the corresponding eigenvector (normalized to have unit 2 norm). Then under the assumption that f (x) = f (x + z), for all x ∈ A and x + z ∈ S x , we have

Pr (f (X + u) = f (X)) ≥ Pr (f (X) = 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) = 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 (G c ) = 1 -Pr (G) ≤ (1 -λ)/(1 -δ 2 ). Now for any x ∈ G, we have | A(x), v | ≥ δ A(x) 2 . Letting = max x A(x) 2 , we get | A(x), ( /δ)v | ≥ A(x) 2 2 . Thus, x ± ( /δ)v ∈ S x , where S x = {x + z ∈ R d : z, A(x) ≥ A(x)

2 2 }, and therefore, by our assumption stated before Theorem 1, we have f (x) = f (x + u), where u = ±( /δ)v. Putting all of this together,

Pr (f (X + u) = f (X)) ≥ Pr (G ∩ A) ≥ Pr (A) -Pr (A ∩ G c ) ≥ Pr (A) -Pr (G c

), and therefore,

Pr (f (X + u) = f (X)) ≥ Pr (f (X) = 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 of M in Theorem 1. Let X 1 , X 2 , . . . , X m be m 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(X i ) A(X i ) 2 A(X i ) T A(X i ) 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 X 1 , X 2 , . . . , X m from the distribution D. Theorem 2 shows that we can efficiently pick such a small sample whose size is independent of D, depends linearly on the intrinsic dimension of M , and logarithmically on the feature dimension d. 

= E A(X) A(X) 2 A(X) T A(X) 2 ∈ R d×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 . Let X 1 , X 2 , . . . , X m be m i.i.d. samples of X drawn from the distribution D, and let λ = M 2 be the top eigenvalue of the matrix M ,

M = 1 m m i=1 A(X i ) A(X i ) 2 A(X i ) T A(X i ) 2 ,

and ṽ 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( -2 r log d), we get 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( -2 r 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ṽ 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 distribution D 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 .

6. UNIVERSAL INVARIANT PERTURBATIONS AND FUTURE DIRECTIONS:

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.

7. CONCLUSION:

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. 

:

the authors consider other p norms as well. We restrict ourselves to the

2-norm.

https://github.com/pytorch/examples/tree/master/imagenet

https://pytorch.org/docs/stable/torchvision/models.html

Figures and Tables:

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.

Figure 1: On ImageNet validation, VGG16 vs VGG19 vs ResNet50: fooling rate vs. norm of perturbation. Attacks constructed using 64 samples. (top left) SVD-Gradient (top right) SVD-FGSM (bottom left) SVD-DeepFool and (bottom right) M-DFFF universal.

Figure 2: On ImageNet validation, (top left): VGG16: error rate (bottom left) VGG16: fooling rate (top right) ResNet50: error rate, (bottom right) ResNet50: fooling rate, vs. norm of perturbation along top singular vector of attack directions on 64 samples.

Figure 3: On CIFAR-10, ResNet18, Singular values of attack directions over a sample of (left) 500 and (right) 10,000 test points.

Figure 5: On ImageNet validation, error rate, VGG19: error rate vs. norm of perturbation along top singular vector of attack directions on 64/128/1024 sample, (top left) Gradient (top right) FGSM (bottom) DeepFool

Figure 6: On CIFAR-10, ResNet18: error rate vs. norm of perturbation along top singular vector of attack directions on 100/500/10000 sample, (top left) Gradient (top right) FGSM (bottom) DeepFool

Figure 7: On CIFAR-10, ResNet18: error rate vs. norm of perturbation along top singular vector of attack directions on 100 samples.

Figure 11: On CIFAR-10, GCNN: error rate vs. norm of perturbation along top singular vector of attack directions on 100/500/10000 samples, (top left) Gradient (top right) FGSM (bottom) Deep-Fool

Peer review (iclr2020):
This paper presents an observation that one can use the top singular vector of a matrix consisting of adversarial perturbation (Gradient attack, FGSM attack, or DeepFool) vectors of a subset of data as a universal attack (applying the same perturbation to all inputs and fools a large fraction of inputs). The paper gives a theoretical justification of their method using matrix concentration inequalities and spectral perturbation bounds. Strengths: - A simple and effective technique to fool a large fraction of examples leveraging the observation that only a small number of dominant principal components exist for input-dependent attack directions. - Clean theoretical justification of the performance of the proposed methodology. - I also like the observation and the generality, simplicity, and theoretical proof of the proposed universal attack algorithm SVD-Universal. Weaknesses: - Performance seems to be inferior to previous methods e.g. Khrulkov & Oseledets 2018. The paper does not give a comparison between SVD-Universal and (p,q)-SVD. - Although the author gives a justification of why they do not compare with (p,q)-SVD, I still like to see a comparison between the two methods such that we can have a better idea about what is the potential performance loss by using the SVD-Universal when compared with (p,q)-SVD. - It is not clear to me how the authors build the matrix corresponding to the universal invariant perturbations in sec 6.