Year: 2018

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 DeepFool 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.

heading: 1 INTRODUCTION
text: 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 (∇xJ(θ, 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.

heading: 2 SUMMARY OF OUR RESULTS
text: 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 RotEqNets.
• 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, DeepFool) and the choice of equivariant neural network models (StdCNNs, GCNNs).

heading: 3 PRINCIPAL COMPONENTS OF ATTACK AND INVARIANT DIRECTIONS
text: 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
1http://www.iro.umontreal.ca/ lisa/twiki/bin/view.cgi/Public/MnistVariations
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. Figures (18b), (2b), (3b), (17b) indicate that this property is shared by NNs, StdCNNs, GCNNs and RotEqNets for MNIST, and also holds when we look at a smaller sample of only 500 test points instead of all 10,000 test points. Similarly Figures (21b), (19b) and (20b) indicate that this property is shared by NNs, StdCNNs, GCNNs for Fashion MNIST. And Figures (4b), (5b) indicate that this property is shared by StdCNNs and GCNNs for CIFAR10. Table 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.

heading: 4 UNIVERSAL ADVERSARIAL ATTACK USING A SMALL SAMPLE
text: 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
the same small-norm universal adversarial attack for CIFAR10 dataset. Moreover, if we pick a small sample of 100 random test points (about 1% of test data) and take their gradients, their top singular vector also gives a good universal adversarial attack direction with a comparable fooling rate, namely, simultaneously fooling the model on roughly 80% of test points using the same smallnorm perturbation for MNIST dataset and roughly 60% for CIFAR10 datset.
Please see Figures (22)-(29) in the appendix for additional experiments.
Figures (7), (9) for MNIST and (11), (13) for CIFAR10 show that a simple approach using the top singular vector of the gradient directions on a small sample gives a universal adversarial attack comparable to Moosavi-Dezfooli et al. (2017) which we denote in the plots as M-DFFF. For applying
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.

heading: 5 ANALYSIS OF UNIVERSAL ADVERSARIAL PERTURBATIONS
text: In this section, we attempt to provide a theoretical justification for the existence of universal adversarial perturbations. Assume that our data is in d dimensions X ⊆ Rd with an underlying
distribution given by probability density µ(x) at each point x ∈ X . Let ax be an adversarial perturbation direction for each x, respectively. Note that ax 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 ⊆ Rd be any given input data with the underlying probability density µ(x) at x ∈ X . Let ax denote an adversarial perturbation vector at point x ∈ X . Let 0 ≤ λ ≤ 1 be the top eigenvalue of the matrix M ∈ Rd×d defined as
M = E [ ax ‖ax‖2 aTx ‖ax‖2 ] ,
and let v be its corresponding eigenvector. Then
Pr ({x : |〈ax,v〉| ≥ δ ‖ax‖2}) ≥ λ− δ2
1− δ2 .
In particular, plugging in δ = √ λ/2 we get
Pr ({ x : |〈ax,v〉| ≥ √ λ
2 ‖ax‖2
}) ≥ λ
2 .
Proof. Define S = {x : |〈ax,v〉| ≥ δ ‖ax‖2} ⊆ X . Since λ is the top eigenvalue of M with v as its corresponding eigenvector,
λ = ∫ X 〈 ax ‖ax‖2 ,v 〉2 µ(x)dx
= ∫ x∈S 〈 ax ‖ax‖2 ,v 〉2 µ(x)dx+ ∫ x/∈S 〈 ax ‖ax‖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 ax/ ‖ax‖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 ofM using only a small subsample ofX . 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 ⊆ Rd be any given input data with the underlying probability density µ(x) at x ∈ X . Let ax denote an adversarial perturbation vector at point x ∈ X . Let 0 ≤ λ ≤ 1 be the top eigenvalue of the matrix M ∈ Rd×d defined as
M = E [ ax ‖ax‖2 aTx ‖ax‖2 ] ,
and let v be its corresponding eigenvector. Let x1,x2, . . . ,xm 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 axi ‖axi‖2 aTxi ‖axi‖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( −2d 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. Using matrix Bernstein inequality from Tropp (2015), we get that for m = O( −2d 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 − ṽ‖2 ≤ /(γ − ), with a constant probability.

heading: 6 CONCLUSION
text: We 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.

heading: A DETAILS OF EXPERIMENTS
text: All experiments performed on neural network-based models were done using MNIST, Fashion MNIST and CIFAR10 datasets with appropriate augmentations applied to the train/validation/test set.
Data sets MNIST2 dataset consists of 70, 000 images of 28 × 28 size, divided into 10 classes. 55, 000 used for training, 5, 000 for validation and 10, 000 for testing. Fashion MNIST3 dataset consists of 70, 000 images of 28× 28 size, divided into 10 classes. 55, 000 used for training, 5, 000 for validation and 10, 000 for testing. CIFAR104 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.
2http://www.iro.umontreal.ca/ lisa/twiki/bin/view.cgi/Public/MnistVariations 3https://github.com/zalandoresearch/fashion-mnist 4https://www.cs.toronto.edu/ kriz/cifar.html
Model Architectures For the MNIST and Fashion MNIST based experiments we use the 7 layer architecture of GCNN similar to Cohen & Welling (2016). The StdCNN architecture is similar to the GCNN except that the operations are as per CNNs. Refer to Table 2 for details. RotEqNet architecture is as given in Marcos et al. (2017). The NN architecture is a 2 layer fully connected with 784-50 neurons in the layers with dropout. For the CIFAR10 based experiments we use the ResNet18 architecture as in He et al. (2016) and it’s equivalent in GCNN as given in Cohen & Welling (2016). Input training data was augmented with random cropping and random horizontal flips, apart from the specific range of rotation augmentation as needed.

Review summaries:
The paper presents some interesting observations related to the connection between the universal adversarial attacks on CNNs and spectral properties. While most of the results are empirical, the authors present two theorems to justify some of the observations. However, the paper is poorly written and very hard to read. Rather than providing too many plots/results in the main paper (maybe use supplementary matl.), the empirical results should be better explained to help the readers. Similarly, the implications of the theorems are not really clear and bit hand-wavy.