Universal Adversarial Training

Introduction

Deep neural networks (DNNs) are vulnerable to adversarial examples, in which small and often imperceptible perturbations change the class label of an image (Szegedy et al., 2013; Goodfellow, Shlens, and Szegedy, 2014; Nguyen, Yosinski, and Clune, 2015; Papernot et al., 2016). Many works have shown that these vulnerabilities can be exploited by showing real world attacks on face detection (Sharif et al., 2016), object detection (Wu et al., 2019), and copyright detection (Saadatpanah, Shafahi, and Goldstein, 2019).

Adversarial examples were originally formed by selecting a single example, and sneaking it into a different class using a small perturbation (Carlini and Wagner, 2017b). This is done most effectively using (potentially expensive) iterative optimization procedures (Dong et al., 2017; Madry et al., 2018; Athalye, Carlini, and Wagner, 2018).

Different from per-instance perturbation attacks, Moosavi-Dezfooli et al. (2017b, a) show there exists “universal” perturbations that can be added to any image to change its class label (fig. 1) with high probability. Universal perturbations empower attackers who cannot generate per-instance adversarial examples on the go, or who want to change the identity of an object to be selected later in the field. Also, universal perturbations have good cross-model transferability, which facilitates black-box attacks.

Among various methods for hardening networks to per-instance attacks, adversarial training (Madry et al., 2018) is known to dramatically increase robustness Athalye, Carlini, and Wagner (2018). In this process, adversarial examples are produced for each mini-batch during training, and injected into the training data. While effective at increasing robustness against small perturbations, it is not effective for larger perturbations which are often the case for universal perturbations. Also, the high cost of this process precludes its use on large and complex datasets.

This paper studies effective methods for producing and deflecting universal adversarial attacks. First, we pose the creation of universal perturbations as an optimization problem that can be effectively solved by stochastic gradient methods. This method dramatically reduces the time needed to produce attacks as compared to Moosavi-Dezfooli et al. (2017b). The efficiency of this formulation empowers us to consider universal adversarial training. We formulate the adversarial training problem as a min-max optimization where the minimization is over the network parameters and the maximization is over the universal perturbation. This problem can be solved quickly using alternating stochastic gradient methods with no inner loops, making it far more efficient than per-instance adversarial training with a strong adversary (which requires a PGD inner loop to generate adversarial perturbations). Prior to our work, it was argued that adversarial training on universal perturbations is infeasible because the inner optimization requires the generation of a universal perturbation from scratch using many expensive iterations (Perolat et al., 2018). We further improve the defense efficiency by providing a “low-cost” algorithm for defending against universal perturbations. Through experiments on CIFAR-10 and ImageNet, we show that this “low-cost” method works well in practice. Note, the approach first introduced here has been expanded on to create a range of “free” adversarial training strategies with the same cost as standard training (Shafahi et al., 2019).

Related work

Adversarial training, in which adversarial examples are injected into the dataset during training, is an effective method to learn a robust model resistant to per-instance attacks (Madry et al., 2018; Huang et al., 2015; Shaham, Yamada, and Negahban, 2015; Sinha, Namkoong, and Duchi, 2018). Robust models adversarially trained with FGSM can resist FGSM attacks (Kurakin, Goodfellow, and Bengio, 2017), but can be vulnerable to PGD attacks (Madry et al., 2018). Madry et al. (2018) suggest strong attacks are important, and they use the iterative PGD method in the inner loop for generating adversarial examples when optimizing the min-max problem. PGD adversarial training is effective but time-consuming when the perturbation is small. The cost of the inner PGD loop is high, although this can sometimes be replaced with neural models for attack generation (Baluja and Fischer, 2018; Poursaeed et al., 2018; Xiao et al., 2018). These robust models are adversarially trained to fend off per-instance perturbations and have not been designed for, or tested against, universal perturbations.

There has been very little work on defending against universal attacks. To the best of our knowledge, the only dedicated study is by Akhtar, Liu, and Mian (2018), who propose a perturbation rectifying network that pre-processes input images to remove the universal perturbation. The rectifying network is trained on universal perturbations that are built for the downstream classifier. While other methods of data sanitization exist (Samangouei, Kabkab, and Chellappa, 2018; Meng and Chen, 2017) , it has been shown (at least for per-instance adversarial examples) that this type of defense is easily subverted by an attacker who is aware that a defense network is being used (Carlini and Wagner, 2017a).

Two recent preprints (Perolat et al., 2018; Mummadi, Brox, and Metzen, 2018) model the problem of defending against universal perturbations as a two-player min-max game. However, unlike us, and similar to per-instance adversarial training, after each gradient descent iteration for updating the DNN parameters, they generate a universal adversarial example in an iterative fashion. Since the generation of universal adversarial perturbations can be very time-consuming, this makes their approach slow and prevents them from training the DNN parameters for many iterations.

Optimization for universal perturbation

Given a set of training samples $X=\{x_{i},i=1,\ldots,N\}$ and a network $f(w,\cdot)$ with frozen parameter $w$ that maps images onto labels, Moosavi-Dezfooli et al. (2017b) propose to find universal perturbations $\delta$ that satisfy,

Different from Moosavi-Dezfooli et al. (2017b), we consider the following optimization problem for building universal perturbations,

where $l(w,\cdot)$ represents the loss used for training DNNs. This simple formulation (2) searches for a universal perturbation that maximizes the training loss, and thus forces images into the wrong class.

The naive formulation (2) suffers from a potentially significant drawback; the cross-entropy loss is unbounded from above, and can be arbitrarily large when evaluated on a single image. In the worst-case, a perturbation that causes misclassification of just a single image can maximize (2) by forcing the average loss to infinity. To force the optimizer to find a perturbation that fools many instances, we propose a “clipped” version of the cross entropy loss,

We cap the loss function at $\beta$ to prevent any single image from dominating the objective in (2), and giving us a better surrogate of misclassification accuracy. In section 5, we investigate the effect of clipping with different $\beta$.

Our proposed method of universal attack using a clipped loss function has several advantages. It is based on a standard stochastic gradient method that comes with convergence guarantees when a decreasing learning rate is used (Bottou, Curtis, and Nocedal, 2018). Also, each iteration is based on a minibatch of samples instead of one instance, which accelerates computation on a GPU. Finally, each iteration requires a simple gradient update instead of the complex DeepFool inner loop; we empirically verify fast convergence and good performance of the proposed method (see section 5).

Universal adversarial training

We now consider training robust classifiers that are resistant to universal perturbations. Similar to Madry et al. (2018), we borrow ideas from robust optimization. We use robust optimization to build robust models that can resist universal perturbations. In particular, we consider universal adversarial training, and formulate this problem as a min-max optimization problem,

where $w$ represents the neural network weights, $X=\{x_{i},i=1,\ldots,N\}$ represents training samples, $\delta$ represents universal perturbation noise, and $l(\cdot)$ is the loss function. Here, unlike conventional adversarial training, our $\delta$ is a universal perturbation (or, more accurately, mini-batch universal). Previously, solving this optimization problem directly was deemed computationally infeasible due to the large cost associated with generating a universal perturbation (Perolat et al., 2018), but we show that eq. 4 is efficiently solvable by alternating stochastic gradient methods shown in algorithm 3. We show that unlike Madry et al. (2018), updating the universal perturbation only using a simple step is enough for building universally hardened networks. Each iteration alternatively updates the neural network weights $w$ using gradient descent, and then updates the universal perturbation $\delta$ using ascent.

We compare our formulation (4) and algorithm 3 with PGD-based adversarial training, which trains a robust model by optimizing the following min-max problem,

The standard formulation (5) searches for per-instance perturbed images $Z$, while our formulation in (4) maximizes using a universal perturbation $\delta$. Madry et al. (2018) solve (5) by a stochastic method. In each iteration, an adversarial example $z_{i}$ is generated for an input instance by the PGD iterative method, and the DNN parameter $w$ is updated once. Our formulation (algorithm 3) only maintains one single perturbation that is used and refined across all iterations. For this reason, we need only update $w$ and $\delta$ once per step (there is no expensive inner loop), and these updates accumulate for both $w$ and $\delta$ through training.

We consider different rules for updating $\delta$ during universal adversarial training,

and ADAM. We found that the FGSM update rule was most effective when combined with the SGD optimizer for updating DNN weights $w$.

We use fairly standard training parameters in our experiments. In our CIFAR experiments, we use $\epsilon=8$, batch-size of 128, and we train for 80,000 steps. For the optimizer, we use Momentum SGD with an initial learning rate of 0.1 which drops to 0.01 at iteration 40,000 and drops further down to 0.001 at iteration 60,000. One way to assess the update rule is to plot the model accuracy before and after the ascent step (i.e., the perturbation update). It is well-known that adversarial training is more effective when stronger attacks are used. In the extreme case of a do-nothing adversary, the adversarial training method degenerates to natural training. As illustrated in the supplementary, we see a gap between the accuracy curves plotted before and after gradient ascent. We find that the FGSM update rule leads to a larger gap, indicating a stronger adversary. Correspondingly, we find that the FGSM update rule yields networks that are more robust to attacks as compared to SGD update.

We evaluate the robustness of different models by applying algorithm 2 to find universal perturbations. We attack universally adversarial trained models (produced by eq. 4) using the FGSM universal update rule (uFGSM), or the SGD universal update rule (uSGD). We also consider robust models from per-instance adversarial training (eq. 5) with adversarial steps of the FGSM and PGD type.

Robust models adversarially trained with weaker attackers such as uSGD and (per-instance) FGSM are relatively vulnerable to universal perturbations, while robust models from (per-instance) PGD and uFGSM can resist universal perturbations. We plot the universal perturbations generated using algorithm 3 in fig. 4. When we visually compare the universal perturbations of robust models (fig. 4) and those of a naturally trained model (fig. 3), we can see a drastic change in structure. Similarly, even among hardened models, universal perturbations generated for weaker robust models have more geometric textures, as shown in fig. 4 (a,d).

While an $\epsilon$-bounded per-instance robust model is also robust against $\epsilon$-bounded universal attacks since the universal attack is a more constrained version of the per-instance attack, training robust per-instance models is only possible for small datasets like CIFAR and for small $\epsilon$. For larger datasets like ImageNet, we cannot train per-instance robust models with such large $\epsilon$’s common for universal attacks. However, we include the per-instance adversarially trained model as a candidate universally robust model for CIFAR-10 in our comparisons to allow comparisons in settings where it is possible to train per-instance robust models.

We apply the strongest attack to validation images of the natural model and various universal adversarially trained models using different update steps. The results are summarized in table 1. Our models become robust against universal perturbations and have higher accuracies on natural validation examples compared to per-instance adversarially trained models. Their robustness is even more if attacked with iDeepFool (93.29%). Compared to the per-instance FGSM trained model which has the same computational cost as ours, our universal model is more robust. Note that the PGD trained model is trained on a 7-step per-instance adversary and requires about $4\times$ more computation than ours.

Low-cost universal adversarial training

As shown in table 1, our proposed algorithm 3 was able to harden the CIFAR-10 classification network. This comes at the cost of doubling the training time. Adversarial training in general should have some cost since it requires the generation or update of the adversarial perturbation of the mini-batch before each minimization step on the network’s parameters. However, since universal perturbations are approximately image-agnostic, results should be fairly invariant to the order of updates. For this reason, we propose to compute the image gradient needed for the perturbation update during the same backward pass used to compute the parameter gradients. This results in a simultaneous update for network weights and the universal perturbation in algorithm 4, which backprops only once per iteration and produces approximately universally robust models at almost no cost in comparison to natural training. The “low-cost universal adversarially trained” model of CIFAR-10 is 86.1% robust against universal perturbations and has 93.5% accuracy on the clean validation examples. When compared to the original version in table 1, the robustness has only slightly decreased. However, the training time is cut by half. This is a huge improvement in efficiency, in particular for large datasets like ImageNet with long training times.

Universal perturbations for ImageNet

We compare the performance of our stochastic gradient method for eq. 2 and the iDeepFool method for eq. 1. We generate universal perturbations for Inception (Szegedy et al., 2016) and VGG (Simonyan and Zisserman, 2014) networks trained on ImageNet, and report the top-1 accuracy in table 2. Universal perturbations generated by both iDeepFool and our method fool networks and degrade the classification accuracy. Universal perturbations generated for the training samples generalize well and cause the accuracy of validation samples to drop. However, when given a fixed computation budget such as number of passes on the training data, our method outperforms iDeepFool by a large margin. Our stochastic gradient method generates the universal perturbations at a much faster pace than iDeepFool. About 20$\times$ faster on InceptionV1 and 6$\times$ on VGG16 (13$\times$ on average).

After verifying the effectiveness and efficiency of our proposed stochastic gradient methodUnless otherwise specified, we use the sign-of-gradient PGD for our stochastic gradient optimizer in algorithm 2., we use our algorithm 2 to generate universal perturbations for ResNet-V1 152 (He et al., 2016) and Inception-V3. Our attacks degrade the validation accuracy of ResNet-V1 152 and Inception-V3 from 76.8% and 78% to 16.4% and 20.1%, respectively. The final universal perturbations used for the results presented are illustrated in the supplementary.

The effect of clipping

Here, we analyze the effect of the “clipping” loss parameter $\beta$ in eq. 2. For this purpose, similar to our other ablations, we generate universal perturbations by solving eq. 2 using PGD for Inception-V3 on ImageNet. We run each experiment with 5 random subsets of training data. The accuracy reported is the classification accuracy on the entire validation set of ImageNet after adding the universal perturbation. The results are summarized in fig. 5. The results showcase the value of our proposed loss function for finding universal adversarial perturbations.

How much training data does the attack need?

As in Moosavi-Dezfooli et al. (2017b), we analyze how the number of training points ($|X|$) affects the strength of universal perturbations in fig. 6. We build $\delta$ using varying amounts of training data. For each experiment, we report the accuracy on the entire validation set after we add the perturbation $\delta$.

Universal adversarial training ImageNet

In this section, we analyze our robust models that are universal adversarially trained by solving the min-max problem (section 4) using algorithm 3. We use $\epsilon=10$ for ImageNet. Note that unlike CIFAR where we were able to train a per-instance PGD-7 robust model with $\epsilon=8$, for ImageNet, there exists no model which can resist per-instance non-targeted perturbations with such large $\epsilon$. For ImageNet, we again use fairly standard training parameters (90 epochs, batch-size 256).

Since our universal adversarial training algorithm (algorithm 3) is cheap, it scales to large datasets such as ImageNet. We first train an AlexNet model on ImageNet. We use the natural training hyper-parameters for universal adversarially training our AlexNet model. Also, we separately use our “low-cost universal training” algorithm to train a robust AlexNet with no overhead cost. We then attack the natural, universally trained, and no-cost universally trained versions of AlexNet using universal attacks.

As seen in fig. 7 (a), the AlexNet trained using our universal adversarial training algorithm (algorithm 3) is robust against universal attacks generated using both algorithm 1 and algorithm 2. The naturally trained AlexNet is susceptible to universal attacks. The final attacks generated for the robust and natural models are presented in fig. 7 (b,c,d). The universal perturbation generated for the robust AlexNet model has little structure compared to the universal perturbation built for the naturally trained AlexNet. This is similar to the trend we observed in fig. 3 and fig. 4 for the WRN models trained on CIFAR-10.

The accuracy of the universal perturbations on the validation examples are summarized in table 3. Similar to CIFAR-10, the low-cost version of universal adversarial training is robust but not as robust as the main method.

We also train a universally robust ResNet-101 ImageNet model. While a naturally trained ResNet-101 achieves only 7.23% accuracy on universal perturbations, our ResNet-101 achieves 74.43% top1 and 92.00% top5 accuracies.

Conclusion

We proposed using stochastic gradient methods and a “clipped” loss function as an effective universal attack that generates universal perturbations much faster than previous methods. To defend against universal perturbations, we proposed to train robust models by optimizing a min-max problem using alternating or simultaneous stochastic gradient methods. We show that this is possible using certain universal noise update rules that use “normalized” gradients. The simultaneous stochastic gradient method comes at almost no extra cost compared to natural training and has almost no additional cost compared to conventional training.

Goldstein and his students were supported by the DARPA GARD, DARPA QED for RML, and DAPRA YFA programs. Further support came from the AFOSR MURI program. Davis and his students were supported by the DARPA MediFor program under cooperative agreement FA87501620191, “Physical and Semantic Integrity Measures for Media Forensics”. Dickerson was supported by NSF CAREER Award IIS-1846237 and DARPA SI3-CMD Award S4761. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon.

References

Appendix A Training curves for UAT

In fig. 8, we present training curves for the CIFAR-10 universal adversarial training process on the WideResnet 32-10 architecture.

As seen in fig. 8, the gap before and after ascent is largest when the FGSM update rule for universal perturbations is used. Also, in fig. 9 we can see that the universal adversarially trained model that uses the FGSM update rule (uFGSM) for its maximization step yeilds the most robust model.

Appendix B Universal perturbations using different optimizers

We apply PGD (using the sign of the gradient) and ADAM in algorithm 3 to generate universal perturbations for these robust models, and show such perturbations in fig. 10.

Appendix C Universal perturbations for various ImageNet architectures

In fig. 11, we plot various universal perturbations found using our “clipped” loss attack. Changing the mini-batch size for generating the perturbations, sometimes causes the perturbations for the same architecture to look slightly different.

Appendix D Comparison with iDeepFool on other datasets

To ensure that our universal perturbation generation algorithm’s performance gain over iDeepFool is not only on ImageNet, we conduct experiments on the WRN 32-10 for CIFAR-10 and LeNet for MNIST. To generate the universal perturbations using both algorithms, we use 5000 training examples and do 10 passes over the data. For CIFAR-10, similar, to the main experiments in the paper, we use $\epsilon=8$. For MNIST, we use $\epsilon=76.5$. The accuracy on the validation images augmented with the universal perturbation are summarized in table 4.

Appendix E Visualizing attacks on robust models

Appendix F Defense Against per-instance attacks

We compare our universal adversarially trained model’s robustness with other hardened models against white-box attacks, where the (robust) models are fully revealed to the attackers. We attack the hardened and natural models using universal perturbations and per-instance perturbations (FGSM Goodfellow, Shlens, and Szegedy (2014), R-FGSM Tramèr et al. (2018), and a 20-step $l_{\infty}$-bounded PGD attack with step-size 2 (Madry et al., 2018)). We also report the performance of per-instance adversarially trained models which are trained with per-instance attacks such as FGSM, R-FGSM and PGD Madry et al. (2018). We use our original universal adversarial training algorithm to build a robust WideResnet (Zagoruyko and Komodakis, 2016) on CIFAR-10 (Krizhevsky and Hinton, 2009). The PGD per-instance adversarial training is done by training on adversarial examples that are built using $7$ steps of PGD following Madry et al. (2018), which makes it $4\times$ slower than the non-iterative adversarial training methods such as our universal adversarial training, FGSM, and R-FGSM adversarial training.

We summarize the CIFAR-10 results in table 5. The natural model, is vulnerable to universal and per-instance perturbations. Our robust model achieves best classification (i.elet@tokeneonedothighest robustness) accuracy against universal perturbation attacks. The 20-step PGD attack fools the natural, FGSM robust, and R-FGSM robust models almost every time. Interestingly, our model is relatively resistant to the PGD attack, though not as robust as the PGD-based robust model. This result is particularly interesting when we consider that our method is hardened using universal perturbations. While the computational cost of our method is similar to that of non-iterative per-instance adversarial training methods (FGSM, and RFGSM), our model is considerably more robust against the PGD attack that is known to be the strongest per-instance attack.

Transferability and black-box robustness

We study the transferability of our robust model in the black-box threat setting, in which we generate adversarial examples based on a source model and use them to attack a target model. We study the transferability of the adversarial 20-step PGD per-instance examples between various models with the WideResnet architecture that are trained on CIFAR-10: natural trained model, FGSM trained robust model, R-FGSM trained robust model, PGD trained robust model (Madry et al., 2018), and our robust model.

The results are summarized in table 6. By examining rows of table 6, both the PGD-based robust model and our robust model are fairly hardened to black-box attacks made for various source models. By examining columns of table 6, we can compare the transferability of the attacks made for various source models. In this metric, the attacks built for our robust model are the strongest in terms of transferability and can deteriorate the performance of both natural and other robust models. An adversary can enhance her black-box attack by first making her source model universally robust!