Title: UNIVERSAL ATTACKS ON EQUIVARIANT NETWORKS

Abstract: Adversarial attacks on neural networks perturb the input at test time in order to fool trained and deployed neural network models. Most attacks such as gradientbased Fast Gradient Sign Method (FGSM) by Goodfellow et al. (2015) and Deep-Fool by Moosavi-Dezfooli et al. (2016) are input-dependent, small, pixel-wise perturbations, and they give different attack directions for different inputs. On the other hand, universal adversarial attacks are input-agnostic and the same attack works for most inputs. Translation or rotation-equivariant neural network models provide one approach to prevent universal attacks based on simple geometric transformations. In this paper, we observe an interesting spectral property shared by all of the above input-dependent, pixel-wise adversarial attacks on translation and rotation-equivariant networks. We exploit this property to get a single universal attack direction that fools the model on most inputs. Moreover, we show how to compute this universal attack direction using principal components of the existing input-dependent attacks on a very small sample of test inputs. We complement our empirical results by a theoretical justification, using matrix concentration inequalities and spectral perturbation bounds. We also empirically observe that the top few principal adversarial attack directions are nearly orthogonal to the top few principal invariant directions.

1. INTRODUCTION:

Neural network-based models achieve state of the art results on several speech and visual recognition tasks but these models are known to be vulnerable to various adversarial attacks. Szegedy et al. (2013) show that small, pixel-wise changes that are almost imperceptible to the human eye can make neural networks models grossly misclassify. They try to maximize the prediction error of a given model by finding a small pixel-wise perturbation 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 given by x = x + sign (∇ x J(θ, x, y)), where x denotes the input, y denotes the class label, θ denotes the model parameters, and J(θ, x, y) denotes the loss function used to train the model.

In subsequent work on FGSM, its iterative variant called Projected Gradient Descent (PGD) was introduced by Kurakin et al. (2017) ; also see Madry et al. (2018) . Goodfellow et al. (2015) and Madry et al. (2018) study adversarial perturbations from the ∞ -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 the minimal 2 -norm perturbation. Broadly, all the above-mentioned adversarial attacks give directions to perturb any given test input in a way that is model-dependent and input-dependent. Tramer et al. (2017) also mention model-agnostic perturbations using the direction of the difference between the intra-class means, in an attempt to understand how adversarial attacks transfer across different models.

Universal adversarial attacks are input-agnostic so that the same perturbation or input transformation fools the trained model on most or nearly all test inputs. Recent work by Moosavi-Dezfooli et al. (2016; 2017) on universal adversarial attacks looks at the curvature of the decision boundary. Their universal attacks or perturbations are more sophisticated than the simple and fast, gradient-based adversarial perturbations, and require significantly more computation. Moosavi-Dezfooli et al. (2017) give a theoretical analysis of existence of universal adversarial attacks using directions in which the decision boundary has positive curvature.

Geometric transformations such as rotations, translations are simple input transformations that are model-agnostic and input-agnostic. Geometric transformations of input at test time are also possible natural attacks; see Dumont et al. (2018) , Gilmer et al. (2018) . One way to counter such attacks is to use neural network models that are translation and rotation-equivariant by construction. Standard Convolutional Neural Networks (StdCNNs) are translation-equivariant but not equivariant with respect to other spatial symmetries such as rotations, reflections etc. Variants of CNNs to achieve rotation-equivariance and other symmetries have received much attention recently, notably, Harmonic Networks (H-Nets) by Worrall et al. (2016) , cyclic slicing and pooling by Dieleman et al. (2016) , Tranformation-Invariant Pooling (TI-Pooling) by Laptev et al. (2016) , Group-equivariant Convolutional Neural Networks (GCNNs) by Cohen & Welling (2016) , Steerable CNNs by Cohen & Welling (2017) , Deep Rotation Equivariant Networks (DREN) by Li et al. (2017) , Rotation Equivariant Vector Field Networks (RotEqNet) by Marcos et al. (2017) , Polar Transformer Networks (PTN) by Esteves et al. (2018) . Among these, GCNNs are based on steerable filters, have a solid theoretical justification Kondor & Trivedi (2018) , and achieve nearly state of the art results on MNIST-rot1 and CIFAR10 as reported in Esteves et al. (2018) . However, both StdCNNs and GCNNs do require rotation augmentation at training time to be robust to rotations.

The above discussion raises an important question: are there any interesting properties shared by translation and rotation-equivariant neural network models that can be exploited to come up with simple universal attacks? Can one find a universal attack direction using only a small fraction of test inputs but that fools the trained model on most test inputs? We answer both of these questions affirmatively in this paper.

2. SUMMARY OF OUR RESULTS:

In this paper, we mostly study StdCNNs and GCNNs, which are translation-equivariant and rotationequivariant, respectively. Some of our experiments also include Fully Connected NNs and RotE-qNets.

• Our first observation is that even though the adversarial attack directions based on gradients, FGSM and DeepFool for StdCNN and GCNN models are input-dependent, overall they have only a small number of dominant principal components. For example, the top 5 (or 5/784 ≈ 0.64%) principal components of the gradient directions on all test inputs contain around 10% of the total spectrum for StdCNNs, GCNNs as well as RotEqNets trained on MNIST, Fashion MNIST. For CIFAR10 the top 5 (or 5/3072 ≈ 0.16%) principal components of the gradient directions contain ≈ 1% of the total spectrum and this goes upto 3% when train and test augmented with a larger range of random rotations. • Our second observation is that a small pixel-wise perturbation in the direction of the top principal component alone can be used as a universal attack to fool these models on around 80-90% test inputs for MNIST and Fashion MNIST, and around 60-70% test inputs for CIFAR10. And our universal attack becomes better as we train these models with larger rotations. • Our third observation is that the top principal component can be well-approximated using only 1% sample of FGSM or DeepFool attack directions on the test data, and this approximation can still give a small pixel-wise perturbation to fool the model on around 80% of test inputs for MNIST and Fashion MNIST, and around 60% of test inputs for CIFAR10. We give a theoretical justification of this phenomenon using matrix concentration inequalities and spectral perturbation bounds. An interesting aspect of our empirical study is that these observations hold across multiple input-dependent attacks (gradient, FGSM, Deep-Fool) and the choice of equivariant neural network models (StdCNNs, GCNNs).

3. PRINCIPAL COMPONENTS OF ATTACK AND INVARIANT DIRECTIONS:

We take a StdCNN or GCNN network as given in Table 2 and train it with 60,000 samples for MNIST and Fashion MNIST, and 50,000 samples for CIFAR10 training data augmented with random rotations in the range [-180 • , +180 • ]. We have also performed some of the experiments for NN (fully connected neural networks) and RotEqNet. We then use the gradient (similarly FGSM, DeepFool) directions obtained for this trained model on the 10,000 test inputs (which are also augmented with random rotations in the range [-180 • , +180 • ]). We form a matrix whose rows are unit vectors along these 10,000 gradient (similarly FGSM, DeepFool) directions and obtain its Singular Value Decomposition (SVD). For gradients, we observe, as in Figure ( 1), that the top 5 or less than 1% in number of the squared singular values of this matrix add up to more than 10% of the overall sum of squared singular values. This is irrespective of whether the trained model is NN, StdCNN, GCNN or RotEqNet. For MNIST, Figures (18a) , ( 2a), (3a), and (17a) show how the sigular values drop when we consider gradient, FGSM, DeepFool directions for NNs, StdCNNs, GCNNs, RotEqNets, respectively. For Fashion MNIST, Figures (21a), (19a) and (20a) show how the sigular values drop when we consider gradient, FGSM, DeepFool directions for NNs, StdCNNs, GCNNs, respectively. For CIFAR10, Figures (4a) and (5a) show how the sigular values drop when we consider gradient, FGSM, DeepFool directions for StdCNNs and GCNNs, respectively. These indicate that the drop in singular values is a common phenomenon for the different attacks and different translation and rotation-equivariant neural network models we consider.

We next consider the principal components of invariant directions. For this, the MNIST/Fashion MNIST/CIFAR10 test data is augmented with random rotations in the range [-180 • , +180 • ], and we look at the difference vectors between such images and their small 2 • rotations. For NN, StdCNN, GCNN or RotEqNet trained with rotation augmentation, we expect the difference between a small rotation of an image and the image itself to be along the invariant subspace tangent to the level sets of the loss function. We take the principal components of these difference or invariant directions, and observe that the top 5 singular vectors of the adversarial directions are nearly orthogonal to the top 5 singular vectors of the invariant directions, i.e., their average dot product is roughtly less than 0. 1 shows deeper analysis using principal angles between subspaces that the two 5-dimensional SVD subspaces of adversarial directions and invariant directions, respectively, have nearly 90 • principal angles.

The intensity maps of top singular vectors for the gradient, FGSM, DeepFool directions for NNs, StdCNNs, GCNNs and RotEqNets also have interesting structure as seen in Figures ( 36)-( 54). As we have already observed, these are nearly orthogonal to the invariant directions which lead to steerable filters similar to Figure (35) . We believe this underlying structure is useful and of independent interest.

4. UNIVERSAL ADVERSARIAL ATTACK USING A SMALL SAMPLE:

We now plot the fooling rate or the fraction of test inputs that the trained model misclassifies, when we perturb all of them using the top singular vector of gradient direction scaled by that denotes the norm of perturbation. In Figures ( 6)-( 9) we plot these fooling rate to show that we can fool 80-90% of test inputs using the same small-norm universal adversarial attack for MNIST dataset.

In Figures ( 10)-( 13) we plot these fooling rate to show that we can fool 60-70% of test inputs using M-DFFF we take the perturbation got by their method, scale it to a unit vector and apply to the test set with varying norm of perturbation to plot the fooling rate.

Figures ( 14)-( 16) and ( 30)-( 34) show how the fooling rate of our adversarial attack gets better when the training is augmented with larger rotations. distribution given by probability density µ(x) at each point x ∈ X. Let a x be an adversarial perturbation direction for each x, respectively. Note that a x could be obtained by any of the several available methods such as the Fast Gradient Sign Method (FGSM), the Kurakin attack, DeepFool or by finding the nearest point on the decision boundary etc. Two important questions are: (a) Why does there exist a universal vector or direction that works as an adversarial perturbation for many or most data points simultaneously? (b) Can we compute such a universal adversarial perturbation by looking only at a small subsample of the data?

Given any method that obtains adversarial perturbations for individual data points, if the matrix of these adversarial perturbation directions taken over all data points satisfies a certain property, then we show that the top singular vectors of this matrix are good candidates for universal adversarial perturbations that make many points to be misclassified simultaneously.

Theorem 1. Let X ⊆ R d be any given input data with the underlying probability density µ(x) at x ∈ X. Let a x denote an adversarial perturbation vector at point x ∈ X. Let 0 ≤ λ ≤ 1 be the top eigenvalue of the matrix M ∈ R d×d defined as

M = E a x a x 2 a T x a x 2 ,

and let v be its corresponding eigenvector. Then

Pr ({x : | a x , v | ≥ δ a x 2 }) ≥ λ -δ 2 1 -δ 2 .

In particular, plugging in δ = λ/2 we get

Pr x : | a x , v | ≥ λ 2 a x 2 ≥ λ 2 . Proof. Define S = {x : | a x , v | ≥ δ a x 2 } ⊆ X. Since λ is the top eigenvalue of M with v as its corresponding eigenvector, λ = X a x a x 2 , v 2 µ(x)dx = x∈S a x a x 2 , v 2 µ(x)dx + x / ∈S a x a x 2 , v 2 µ(x)dx ≤ x∈S µ(x)dx + δ 2 x / ∈S µ(x)dx because v 2 = 1 = Pr (S) + δ 2 (1 -Pr (S)) = (1 -δ 2 ) Pr (S) + δ 2 .

This implies that Pr (S) ≥ (λ -δ 2 )/(1 -δ 2 ).

Observe that tr (M ) = 1. Theorem 1 implies that as the top eigenvalue λ dominates the spectrum, its eigenvector v get more aligned with the adversarial perturbations directions a x / a x 2 for most points x ∈ X. This means that v is a potential candidate for a universal adversarial perturbation. More generally, Theorem 1 works for any of the top eigenvalues of M and their corresponding eigenvectors, and thus, gives a subspace spanned by multiple orthogonal directions all of which are potential candidates for being universal adversarial perturbations that fool a given classifier on many input examples. Now let's consider the second question of finding a good approximation to our candidate universal adversarial perturbation or the top eigenvector v of M using only a small subsample of X. Theorem 2 shows that only a small sample of size independent of |X| but depending only on the dimension d of the data and the spectral properties of the matrix M suffices.

Theorem 2. Let X ⊆ R d be any given input data with the underlying probability density µ(x) at x ∈ X. Let a x denote an adversarial perturbation vector at point x ∈ X. Let 0 ≤ λ ≤ 1 be the top eigenvalue of the matrix M ∈ R d×d defined as

M = E a x a x 2 a T x a x 2 ,

and let v be its corresponding eigenvector. Let x 1 , x 2 , . . . , x m be a i.i.d. sample of m points from X drawn from the distribution defined by probability density µ, and let λ be the top eigenvalue of the matrix M ,

M = 1 m m i=1 a xi a xi 2 a T xi a xi 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 d 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. Using matrix Bernstein inequality from Tropp (2015) , we get that for m = O( -2 d log d),

we have that the spectral or the operator norm M -M 2 ≤ λ, with a constant probability. Now we can use results about spectral perturbation bounds from Bhatia (1997) . By Weyl's theorem, this implies λ -λ ≤ λ. If there is gap of at least γλ between the first and the second eigenvalue of M with γ > , then by Davis-Kahan theorem we get that vṽ 2 ≤ /(γ -), with a constant probability. 

:

http://www.iro.umontreal.ca/ lisa/twiki/bin/view.cgi/Public/MnistVariations

CONCLUSIONWe show how to use a small sample of input-dependent adversarial attack directions on test inputs to find a single universal attack direction that fools translation and rotation-equivariant models such as CNNs and GCNNs on a large fraction of test inputs. Our main observation is a spectral property shared by different attacks directions such as gradients, FGSM, DeepFool on these models. We give a theoretical justification for how this spectral property helps in using the top singular vector as a universal attack direction computed using only a small sample of test inputs.

http://www.iro.umontreal.ca/ lisa/twiki/bin/view.cgi/Public/MnistVariations

https://github.com/zalandoresearch/fashion-mnist

https://www.cs.toronto.edu/ kriz/cifar.html

Figures and Tables:

Figure 1: Fraction of the total spectrum contained in top 5 squared singular values of gradient directions for 10,000 test inputs, when train and test augmented with random rotations in [-x • , x • ] range for NN, StdCNN, GCNN and RotEqNet, respectively. (left) MNIST (center) Fashion MNIST (below) CIFAR10

Figure 6: On MNIST, StdCNN: fooling rate vs. norm of perturbation along top singular vector of attack directions on 100/500/10000 sample, (left) gradients (center) FGSM (right) DeepFool

Figure 15: On MNIST, fooling rate of our universal attack using top singular vector of 100 test point gradients, for GCNN train-augmented with random rotations in range [-θ • , θ • ] (left) test unrotated, (right) test-augmented with the same range of rotations as the training set.

Figure 16: On CIFAR10, fooling rate of our universal attack using top singular vector of 100 test point gradients, for StdCNN train-augmented with random rotations in range [-θ • , θ • ] (left) test unrotated, (right) test-augmented with the same range of rotations as the training set.

Figure 19: On Fashion MNIST, Principal components of adversarial and invariant directions for StdCNN

Figure 31: On MNIST, fooling rate of our universal attack using top singular vector of 10000 test point gradients, for GCNN train-augmented with random rotations in range [-θ • , θ • ] (left) test unrotated, (right) test-augmented with the same range of rotations as the training set.

Figure 32: On CIFAR10, fooling rate of our universal attack using top singular vector of 10000 test point gradients, for StdCNN train-augmented with random rotations in range [-θ • , θ • ] (left) test unrotated, (right) test-augmented with the same range of rotations as the training set.

Figure 33: On CIFAR10, fooling rate of our universal attack using top singular vector of 100 test point gradients, for GCNN train-augmented with random rotations in range [-θ • , θ • ] (left) test unrotated, (right) test-augmented with the same range of rotations as the training set.

Figure 34: On CIFAR10, fooling rate of our universal attack using top singular vector of 10000 test point gradients, for GCNN train-augmented with random rotations in range [-θ • , θ • ] (left) test unrotated, (right) test-augmented with the same range of rotations as the training set.

Figure 35: On MNIST, Top 5 SVD vectors from image difference

Figure 38: On MNIST, Top 5 SVD vectors from DeepFool in StdCNN with rotation augmentations

Figure 45: On MNIST, Top 5 SVD vectors from FGSM in RotEqNet with rotation augmentations

Subspace angles between Top 5 SVD vectors from gradients of test points for each network and invariant directions (small 2 • rotations) respectively.

Table content: <table><tr><td>Dataset</td><td>Model</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td>MNIST</td><td>StdCNN</td><td colspan="5">89.82170934 88.06580815 84.76831292 81.22444162 78.85267548</td></tr><tr><td>MNIST</td><td>GCNN</td><td colspan="5">89.06822425 88.27986252 87.45134508 84.26710498 68.77651938</td></tr><tr><td>MNIST</td><td colspan="6">RotEqNet 89.75561818 88.88988678 85.60567329 82.28177397 68.96832307</td></tr><tr><td>MNIST</td><td>NN</td><td colspan="5">89.9915157 88.78972167 88.5374161 86.56321357 70.12080709</td></tr><tr><td colspan="2">Fashion MNIST StdCNN</td><td colspan="5">89.21807572 79.28255649 77.29202168 70.53545269 63.20996031</td></tr><tr><td colspan="2">Fashion MNIST GCNN</td><td colspan="5">88.90127175 87.92549838 73.42571367 70.55420976 69.19559671</td></tr><tr><td colspan="2">Fashion MNIST NN</td><td colspan="5">89.9895849 87.71857462 87.5599056 84.38550172 58.77045895</td></tr><tr><td>CIFAR10</td><td>StdCNN</td><td colspan="5">89.97432038 89.91897569 89.84706226 89.71168446 89.56515156</td></tr><tr><td>CIFAR10</td><td>GCNN</td><td colspan="5">89.99666115 89.82916528 89.71339735 89.59987204 88.90306292</td></tr></table>

Peer review (iclr2019):
 The authors made an interesting observation: There*s an important common subspace of Gradient/FGSM/Deepfool attacks among all examples. Therefore, they propose to use top SVD components of the directions to conduct universal attack. This is an interesting finding but also not surprising; we know the gradient of loss function w.r.t input can be used for interpretability, and in MNIST examples they usually reveals some rough shape of the class. This is also observed in Figure 8-13 in this paper, and thus it makes sense that the gradient directions share a common subspace. Therefore I think this observation itself is not significant enough. Using this for universal attack is interesting, however the experiments are not that convincing: 1. To show this is a good way for universal attack, I think the authors should compare with previous work in (Moosavi-Dezfooli et al). 2. All the experiments are on MNIST. How about cifar/ImageNet?