summaries: This paper proposes a unified alternating projected gradient descent-ascent (APGDA) attack by considering the min-max operation for adversarial attack settings. The proposed method can be applied in generating model ensemble attacks, universal adversarial attacks, and robust attacks over data transformations. Extensive results show that the proposed method can achieve better attack performances for these three applications. This paper proposed a APGDA attack method, in which the model ensemble attack, universal attack, and robust attack are unified. The authors proved their APGDA's superiority in theory, ${i.e.}$, convergence rate and strong attacking ability. All of the mentioned tasks (ensemble attack, universal attack, robust attack) are investigated through experiments. The paper provides a general min-max framework to formulate several popular problems in the literature including Ensemble attack over multiple models, Universal Perturbation over multiple examples, and adversarial attack over data transformations. For each case, a standard first-order approach converging to a stationary point of the problem is provided. The effectiveness of the min-max approach compared to the standard empirical risk minimization has been demonstrated by extensive experiments.   This paper adapts the min-max problem proposed for multi-domain robust optimization [45] to the problem of generating adversarial attacks. They show how several adversarial attacks scenarios can be formulated using this min-max, for example they show that this min-max formulation can be used to find successful attacks against an ensemble of models. They also show how this min-max can also be used to train robust models against multiple $\ell_p$ attacks. They show experimentally that the approach outperforms several baseline in several setting. The work proposes a min-max framework APGDA that can take in different models related to adversarial robustness. APGDA can generate model ensemble attack, universal attack over multiple images, and robust attack over data transformations. They perform experiments to evaluate their method.
abstractText: The worst-case training principle that minimizes the maximal adversarial loss, also known as adversarial training (AT), has shown to be a state-of-the-art approach for enhancing adversarial robustness. Nevertheless, min-max optimization beyond the purpose of AT has not been rigorously explored in the adversarial context. In this paper, we show how a general framework of min-max optimization over multiple domains can be leveraged to advance the design of different types of adversarial attacks. In particular, given a set of risk sources, minimizing the worst-case attack loss can be reformulated as a min-max problem by introducing domain weights that are maximized over the probability simplex of the domain set. We showcase this unified framework in three attack generation problems – attacking model ensembles, devising universal perturbation under multiple inputs, and crafting attacks resilient to data transformations. Extensive experiments demonstrate that our approach leads to substantial attack improvement over the existing heuristic strategies as well as robustness improvement over state-of-the-art defense methods trained to be robust against multiple perturbation types. Furthermore, we find that the self-adjusted domain weights learned from our min-max framework can provide a holistic tool to explain the difficulty level of attack across domains. Code is available at https://github.com/wangjksjtu/minmax-adv.
authors.name: Jingkang Wang
authors.name: Tianyun Zhang
authors.name: Sijia Liu
authors.name: Pin-Yu Chen
authors.name: Jiacen Xu
authors.name: Makan Fardad
authors.name: Bo Li
references.authors: M. Andriushchenko F. Croce N. Flammarion M. Hein
references.title: Square attack: A query-efficient black-box adversarial attack via random search
references.venue: ECCV (23), volume 12368 of Lecture Notes in Computer Science, pages 484–501. Springer
references.authors: A. Araujo R. Pinot B. Negrevergne L. Meunier Y. Chevaleyre F. Yger J. Atif
references.title: Robust neural networks using randomized adversarial training
references.venue: arXiv preprint arXiv:1903.10219
references.authors: A. Athalye N. Carlini D. Wagner
references.title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples
references.venue: arXiv preprint arXiv:1802.00420
references.authors: A. Athalye L. Engstrom A. Ilyas K. Kwok
references.title: Synthesizing robust adversarial examples
references.venue: ICML, volume 80 of Proceedings of Machine Learning Research, pages 284–293. PMLR
references.authors: A. Athalye L. Engstrom A. Ilyas K. Kwok
references.title: Synthesizing robust adversarial examples
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: A. Athalye I. Sutskever
references.title: Synthesizing robust adversarial examples
references.venue: ICML
references.authors: A.J. Bose G. Gidel H. Berard A. Cianflone P. Vincent S. Lacoste-Julien W.L. Hamilton
references.title: Adversarial example games
references.venue: NeurIPS
references.authors: S. Boyd L. Vandenberghe
references.title: Convex optimization
references.venue: Cambridge university press
references.authors: W. Brendel J. Rauber M. Bethge
references.title: Decision-based adversarial attacks: Reliable attacks against black-box machine learning models
references.venue: arXiv preprint arXiv:1712.04248
references.authors: T.B. Brown D. Mané A. Roy M. Abadi J. Gilmer
references.title: Adversarial patch
references.venue: CoRR, abs/1712.09665
references.authors: N. Carlini A. Athalye N. Papernot W. Brendel J. Rauber D. Tsipras I.J. Goodfellow A. Madry A. Kurakin
references.title: On evaluating adversarial robustness
references.venue: CoRR, abs/1902.06705
references.authors: N. Carlini P. Mishra T. Vaidya Y. Zhang M. Sherr C. Shields D. Wagner W. Zhou
references.title: Hidden voice commands
references.venue: USENIX Security Symposium, pages 513–530
references.authors: N. Carlini D. Wagner
references.title: Towards evaluating the robustness of neural networks
references.venue: Security and Privacy (SP), 2017 IEEE Symposium on, pages 39–57. IEEE
references.authors: N. Carlini D.A. Wagner
references.title: Audio adversarial examples: Targeted attacks on speech-to-text
references.venue: IEEE Symposium on Security and Privacy Workshops, pages 1–7. IEEE Computer Society
references.authors: H. Chen H. Zhang P.-Y. Chen J. Yi C.-J. Hsieh
references.title: Attacking visual language grounding with adversarial examples: A case study on neural image captioning
references.venue: Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, volume 1, pages 2587–2597
references.authors: J.M. Cohen E. Rosenfeld J.Z. Kolter
references.title: Certified adversarial robustness via randomized smoothing
references.venue: ICML, volume 97 of Proceedings of Machine Learning Research, pages 1310– 1320. PMLR
references.authors: F. Croce M. Hein
references.title: Provable robustness against all adversarial lp-perturbations for p 1
references.venue: arXiv preprint arXiv:1905.11213
references.authors: F. Croce M. Hein
references.title: Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks
references.venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 2206–2216. PMLR
references.authors: Y. Dong F. Liao T. Pang H. Su J. Zhu X. Hu J. Li
references.title: Boosting adversarial attacks with momentum
references.venue: CVPR, pages 9185–9193. IEEE Computer Society
references.authors: K. Eykholt I. Evtimov E. Fernandes B. Li A. Rahmati C. Xiao A. Prakash T. Kohno D. Song
references.title: Robust physical-world attacks on deep learning visual classification
references.venue: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1625–1634
references.authors: K. Eykholt I. Evtimov E. Fernandes B. Li A. Rahmati C. Xiao A. Prakash T. Kohno D. Song
references.title: Robust physical-world attacks on deep learning visual classification
references.venue: CVPR, pages 1625–1634. IEEE Computer Society
references.authors: I. Goodfellow J. Shlens C. Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: 2015 ICLR, arXiv preprint arXiv:1412.6572
references.authors: I.J. Goodfellow J. Shlens C. Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: arXiv preprint arXiv:1412.6572
references.authors: K. He X. Zhang S. Ren J. Sun
references.title: Deep residual learning for image recognition
references.venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770– 778
references.authors: M. Hein M. Andriushchenko
references.title: Formal guarantees on the robustness of a classifier against adversarial manipulation
references.venue: Advances in Neural Information Processing Systems, pages 2266– 2276
references.authors: S. Huang N. Papernot I.J. Goodfellow Y. Duan P. Abbeel
references.title: Adversarial attacks on neural network policies
references.venue: ICLR (Workshop). OpenReview.net
references.authors: R. Jia P. Liang
references.title: Adversarial examples for evaluating reading comprehension systems
references.venue: EMNLP, pages 2021–2031. Association for Computational Linguistics
references.authors: D. Kang Y. Sun D. Hendrycks T. Brown J. Steinhardt
references.title: Testing robustness against unforeseen adversaries
references.venue: arXiv preprint arXiv:1908.08016
references.authors: H. Karimi J. Nutini M. Schmidt
references.title: Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition
references.venue: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795–811. Springer
references.authors: Y. Lecun L. Bottou Y. Bengio P. Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: Q. Lei L. Wu P.-Y. Chen A.G. Dimakis I.S. Dhillon M. Witbrock
references.title: Discrete adversarial attacks and submodular optimization with applications to text classification
references.venue: SysML
references.authors: T. Lin C. Jin M.I. Jordan
references.title: On gradient descent ascent for nonconvex-concave minimax problems
references.venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 6083– 6093. PMLR
references.authors: Y. Lin Z. Hong Y. Liao M. Shih M. Liu M. Sun
references.title: Tactics of adversarial attack on deep reinforcement learning agents
references.venue: IJCAI, pages 3756–3762. ijcai.org
references.authors: J. Liu W. Zhang N. Yu
references.title: CAAD 2018: Iterative ensemble adversarial attack
references.venue: CoRR, abs/1811.03456
references.authors: S. Liu S. Lu X. Chen Y. Feng K. Xu A. Al-Dujaili M. Hong U. Obelilly
references.title: Min-max optimization without gradients: Convergence and applications to adversarial ML
references.venue: CoRR, abs/1909.13806
references.authors: Y. Liu X. Chen C. Liu D. Song
references.title: Delving into transferable adversarial examples and black-box attacks
references.venue: ICLR. OpenReview.net
references.authors: S. Lu R. Singh X. Chen Y. Chen
references.title: and M
references.venue: Hong. Understand the dynamics of GANs via primal-dual optimization
references.authors: S. Lu I. Tsaknakis M. Hong
references.title: Block alternating optimization for non-convex min-max problems: Algorithms and applications in signal processing and communications. 2018
references.authors: S. Lu I. Tsaknakis M. Hong
references.title: Block alternating optimization for non-convex min-max problems: algorithms and applications in signal processing and communications
references.venue: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
references.authors: A. Madry A. Makelov L. Schmidt D. Tsipras A. Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: arXiv preprint arXiv:1706.06083
references.authors: P. Maini E. Wong J.Z. Kolter
references.title: Adversarial robustness against the union of multiple perturbation models
references.venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 6640–6650. PMLR
references.authors: D. Meng H. Chen
references.title: Magnet: a two-pronged defense against adversarial examples
references.venue: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 135–147. ACM
references.authors: J.H. Metzen M.C. Kumar T. Brox V. Fischer
references.title: Universal adversarial perturbations against semantic image segmentation
references.venue: ICCV, pages 2774–2783. IEEE Computer Society
references.authors: S.-M. Moosavi-Dezfooli A. Fawzi O. Fawzi P. Frossard
references.title: Universal adversarial perturbations
references.venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 86–94
references.authors: S.M. Moosavi Dezfooli A. Fawzi P. Frossard
references.title: Deepfool: a simple and accurate method to fool deep neural networks
references.venue: Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), number EPFL-CONF-218057
references.authors: M. Nouiehed M. Sanjabi J.D. Lee M. Razaviyayn
references.title: Solving a class of non-convex min-max games using iterative first order methods
references.venue: arXiv preprint arXiv:1902.08297
references.authors: N. Papernot P. McDaniel I. Goodfellow S. Jha Z.B. Celik A. Swami
references.title: Practical black-box attacks against machine learning
references.venue: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pages 506–519. ACM
references.authors: N. Papernot P. McDaniel S. Jha M. Fredrikson Z.B. Celik A. Swami
references.title: The limitations of deep learning in adversarial settings
references.venue: Security and Privacy (EuroS&P), 2016 IEEE European Symposium on, pages 372–387. IEEE
references.authors: N. Parikh S. Boyd
references.title: et al
references.venue: Proximal algorithms. Foundations and Trends R in Optimization, 1(3):127–239
references.authors: Q. Qian S. Zhu J. Tang R. Jin B. Sun H. Li
references.title: Robust optimization over multiple domains
references.venue: CoRR, abs/1805.07588
references.authors: H. Rafique M. Liu Q. Lin T. Yang
references.title: Non-convex min-max optimization: Provable algorithms and applications in machine learning
references.venue: arXiv preprint arXiv:1810.02060
references.authors: J. Rauber W. Brendel
references.title: and M
references.venue: Bethge. Foolbox v0.8.0: A python toolbox to benchmark the robustness of machine learning models. CoRR, abs/1707.04131
references.authors: L. Rice E. Wong J.Z. Kolter
references.title: Overfitting in adversarially robust deep learning
references.venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 8093–8104. PMLR
references.authors: J. Rony L.G. Hafemann L.S. Oliveira I.B. Ayed R. Sabourin E. Granger
references.title: Decoupling direction and norm for efficient gradient-based L2 adversarial attacks and defenses
references.venue: CVPR, pages 4322–4330. Computer Vision Foundation / IEEE
references.authors: L. Schott J. Rauber M. Bethge W. Brendel
references.title: Towards the first adversarially robust neural network model on MNIST
references.venue: ICLR (Poster). OpenReview.net
references.authors: A. Shafahi M. Najibi Z. Xu J.P. Dickerson L.S. Davis T. Goldstein
references.title: Universal adversarial training
references.venue: CoRR, abs/1811.11304
references.authors: F. Sheikholeslami A. Lotfi J.Z. Kolter
references.title: Provably robust classification of adversarial examples with detection
references.venue: ICLR. OpenReview.net
references.authors: K. Simonyan A. Zisserman
references.title: Very deep convolutional networks for large-scale image recognition
references.venue: ICLR
references.authors: A. Sinha H. Namkoong J. Duchi
references.title: Certifying some distributional robustness with principled adversarial training
references.authors: L.N. Smith
references.title: A disciplined approach to neural network hyper-parameters: Part 1 - learning rate
references.venue: batch size, momentum, and weight decay. CoRR, abs/1803.09820
references.authors: J.T. Springenberg A. Dosovitskiy T. Brox M.A. Riedmiller
references.title: Striving for simplicity: The all convolutional net
references.venue: ICLR (Workshop)
references.authors: D. Su H. Zhang H. Chen J. Yi P.-Y. Chen Y. Gao
references.title: Is robustness the cost of accuracy?–a comprehensive study on the robustness of 18 deep image classification models
references.venue: Proceedings of the European Conference on Computer Vision (ECCV), pages 631–648
references.authors: C. Szegedy W. Liu Y. Jia P. Sermanet S.E. Reed D. Anguelov D. Erhan V. Vanhoucke A. Rabinovich
references.title: Going deeper with convolutions
references.venue: CVPR, pages 1–9. IEEE Computer Society
references.authors: C. Szegedy W. Zaremba I. Sutskever J. Bruna D. Erhan I. Goodfellow R. Fergus
references.title: Intriguing properties of neural networks
references.venue: arXiv preprint arXiv:1312.6199
references.authors: F. Tramèr D. Boneh
references.title: Adversarial training and robustness for multiple perturbations
references.venue: arXiv preprint arXiv:1904.13000
references.authors: F. Tramèr A. Kurakin N. Papernot I. Goodfellow D. Boneh P. McDaniel
references.title: Ensemble adversarial training: Attacks and defenses
references.venue: 2018 ICLR, arXiv preprint arXiv:1705.07204
references.authors: F. Tramèr N. Papernot I. Goodfellow D. Boneh P. McDaniel
references.title: The space of transferable adversarial examples
references.venue: arXiv preprint arXiv:1704.03453
references.authors: E. Wong L. Rice J.Z. Kolter
references.title: Fast is better than free: Revisiting adversarial training
references.venue: ICLR. OpenReview.net
references.authors: C. Xiao B. Li J.-Y. Zhu W. He M. Liu D. Song
references.title: Generating adversarial examples with adversarial networks
references.venue: arXiv preprint arXiv:1801.02610
references.authors: C. Xiao J.-Y. Zhu B. Li W. He M. Liu D. Song
references.title: Spatially transformed adversarial examples
references.venue: International Conference on Learning Representations
references.authors: C. Xie J. Wang Z. Zhang Z. Ren A. Yuille
references.title: Mitigating adversarial effects through randomization
references.venue: arXiv preprint arXiv:1711.01991
references.authors: K. Xu S. Liu P. Zhao P.-Y. Chen H. Zhang Q. Fan D. Erdogmus Y. Wang X. Lin
references.title: Structured adversarial attack: Towards general implementation and better interpretability
references.venue: International Conference on Learning Representations
references.authors: K. Xu G. Zhang S. Liu Q. Fan M. Sun H. Chen P. Chen Y. Wang X. Lin
references.title: Adversarial t-shirt! evading person detectors in a physical world
references.venue: ECCV (5), volume 12350 of Lecture Notes in Computer Science, pages 665–681. Springer
references.authors: W. Xu D. Evans Y. Qi
references.title: Feature squeezing: Detecting adversarial examples in deep neural networks
references.venue: NDSS. The Internet Society
references.authors: S. Zagoruyko N. Komodakis
references.title: Wide residual networks
references.venue: BMVC. BMVA Press
references.authors: H. Zhang Y. Yu J. Jiao E.P. Xing L.E. Ghaoui M.I. Jordan
references.title: Theoretically principled trade-off between robustness and accuracy
references.venue: arXiv preprint arXiv:1901.08573
references.authors: Z. Zhao D. Dua S. Singh
references.title: Generating natural adversarial examples
references.venue: ICLR. OpenReview.net
sections.heading: 1 Introduction
sections.text: Training a machine learning model that is capable of assuring its worst-case performance against possible adversaries given a specified threat model is a fundamental and challenging problem, especially for deep neural networks (DNNs) [64, 22, 13, 69, 70]. A common practice to train an adversarially robust model is based on a specific form of min-max training, known as adversarial training (AT) [22, 40], where the minimization step learns model weights under the adversarial loss constructed at the maximization step in an alternative training fashion. In practice, AT has achieved the state-of-the-art defense performance against `p-norm-ball input perturbations [3].
  Although the min-max principle is widely used in AT and its variants [40, 59, 76, 65], few work has studied its power in attack generation. Thus, we ask: Beyond AT, can other types of min-max formulation and optimization techniques advance the research in adversarial attack generation? In this paper, we give an affirmative answer corroborated by the substantial performance gain and the ability of self-learned risk interpretation using our proposed min-max framework on several tasks for adversarial attack.
  ⇤Equal contributions.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  We demonstrate the utility of a general formulation for minimizing the maximal loss induced from a set of risk sources (domains). Our considered min-max formulation is fundamentally different from AT, as our maximization step is taken over the probability simplex of the set of domains. Moreover, we show that many problem setups in adversarial attacks can in fact be reformulated under this general min-max framework, including attacking model ensembles [66, 34], devising universal perturbation to input samples [44] and data transformations [6, 10]. However, current methods for solving these tasks often rely on simple heuristics (e.g., uniform averaging), resulting in significant performance drops when comparing to our proposed min-max optimization framework.
  Contributions ¨ With the aid of min-max optimization, we propose a unified alternating onestep projected gradient descent-ascent (APGDA) attack method, which can readily be specified to generate model ensemble attack, universal attack over multiple images, and robust attack over data transformations. ≠ In theory, we show that APGDA has an O(1/T ) convergence rate, where T is the number of iterations. In practice, we show that APGDA obtains 17.48%, 35.21% and 9.39% improvement on average compared with conventional min-only PGD attack methods on CIFAR-10. Æ More importantly, we demonstrate that by tracking the learnable weighting factors associated with multiple domains, our method can provide tools for self-adjusted importance assessment on the mixed learning tasks. Ø Finally, we adapt the idea of the domain weights into a defense setting [65], where multiple `p-norm perturbations are generated, and achieve superior performance as well as intepretability.
sections.heading: 1.1 Related work
sections.text: Recent studies have identified that DNNs are highly vulnerable to adversarial manipulations in various applications [64, 12, 27, 33, 26, 14, 77, 20, 15, 31], thus leading to an arms race between adversarial attacks [13, 3, 23, 48, 45, 72, 1, 18] and defenses [40, 59, 76, 65, 42, 71, 74, 68, 53, 16]. One intriguing property of adversarial examples is the transferability across multiple domains [36, 67, 47, 62], which indicates a more challenging yet promising research direction – devising universal adversarial perturbations over model ensembles [66, 34], input samples [44, 43, 56] and data transformations [3, 6, 10].
  Besides, many recent works started to produce physical realizable perturbations that expose real world threats. The most popular approach [4, 21], as known as Expectation Over Transformation (EOT), is to train the attack under different data transformation (e.g., different view angles and distances). However, current approaches suffer from a significant performance loss for resting on the uniform averaging strategy or heuristic weighting schemes [34, 56]. We will compare these works with our min-max method in Sec. 4. As a natural extension following min-max attack, we study the generalized AT under multiple perturbations [65, 2, 28, 17]. Finally, our min-max framework is adapted and inspired by previous literature on robust optimization over multiple domains [50, 51, 38, 37].
  To our best knowledge, only few works leverage min-max principle for adversarial attack generation while the idea of producing the worst-case example across multiple domains is quite natural. Specifically, [7] considered the non-interactive blackbox adversary setting and proposed a framework that models the crafting of adversarial examples as a min-max game between a generator of attacks and a classifier. [57] introduced a min-max based adaptive attacker’s objective to craft perturbation so that it simultaneously evades detection and causes misclassification. Inspired by our work, the min-max formulation has also been extended to zero-order blackbox attacks [35] and physically realizable attacks [73, Adversarial T-shirt]. We hope our unified formulation can stimulate further research on applying min-max principle and interpretable domain weights in more attack generation tasks that involve in evading multiple systems.
sections.heading: 2 Min-Max Across Domains
sections.text: Consider K loss functions {Fi(v)} (each of which is defined on a learning domain), the problem of robust learning over K domains can be formulated as [50, 51, 38]
  minimize v2V maximize w2P
  P K
  i=1 wiFi(v), (1)
  where v and w are optimization variables, V is a constraint set, and P denotes the probability simplex P = {w |1Tw = 1, wi 2 [0, 1], 8i}. Since the inner maximization problem in (1) is a linear function
  of w over the probabilistic simplex, problem (1) is thus equivalent to minimize
  v2V maximize i2[K] Fi(v), (2)
  where [K] denotes the integer set {1, 2, . . . ,K}.
  Benefit and Challenge from (1). Compared to multi-task learning in a finite-sum formulation which minimizes K losses on average, problem (1) provides consistently robust worst-case performance across all domains. This can be explained from the epigraph form of (2),
  minimize v2V,t t, subject to Fi(v)  t, i 2 [K], (3) where t is an epigraph variable [8] that provides the t-level robustness at each domain.
  In computation, the inner maximization problem of (1) always returns the one-hot value of w, namely, w = ei, where ei is the ith standard basis vector, and i = argmaxi{Fi(v)}. However, this one-hot coding reduces the generalizability to other domains and induces instability of the learning procedure in practice. Such an issue is often mitigated by introducing a strongly concave regularizer in the inner maximization step to strike a balance between the average and the worst-case performance [38, 50].
  Regularized Formulation. Following [50], we penalize the distance between the worst-case loss and the average loss over K domains. This yields
  minimize v2V maximize w2P
  P K
  i=1 wiFi(v) 2 kw 1/Kk 2 2, (4)
  where > 0 is a regularization parameter. As ! 0, problem (4) is equivalent to (1). By contrast, it becomes the finite-sum problem when ! 1 since w ! 1/K. In this sense, the trainable w provides an essential indicator on the importance level of each domain. The larger the weight is, the more important the domain is. We call w domain weights in this paper.
sections.heading: 3 Min-Max Power in Attack Design
sections.text: To the best of our knowledge, few work has studied the power of min-max in attack generation. In this section, we demonstrate how the unified min-max framework (4) fits into various attack settings. With the help of domain weights, our solution yields better empirical performance and explainability. Finally, we present the min-max algorithm with convergence analysis to craft robust perturbations against multiple domains.
sections.heading: 3.1 A Unified Framework for Robust Adversarial Attacks
sections.text: The general goal of adversarial attack is to craft an adversarial example x0 = x0 + 2 Rd to mislead the prediction of machine learning (ML) or deep learning (DL) systems, where x0 denotes the natural example with the true label t0, and is known as adversarial perturbation, commonly subject to `p-norm (p 2 {0, 1, 2,1}) constraint X := { | k kp  ✏, x0 + 2 [0, 1]d} for a given small number ✏. Here the `p norm enforces the similarity between x0 and x0, and the input space of ML/DL systems is normalized to [0, 1]d.
  Ensemble Attack over Multiple Models. Consider K ML/DL models {Mi}Ki=1, the goal is to find robust adversarial examples that can fool all K models simultaneously. In this case, the notion of ‘domain’ in (4) is specified as ‘model’, and the objective function Fi in (4) signifies the attack loss f( ;x0, y0,Mi) given the natural input (x0, y0) and the model Mi. Thus, problem (4) becomes
  minimize 2X maximize w2P
  P K
  i=1 wif( ;x0, y0,Mi) 2 kw 1/Kk 2 2, (5)
  where w encodes the difficulty level of attacking each model.
  Universal Perturbation over Multiple Examples. Consider K natural examples {(xi, yi)}Ki=1 and a single model M, our goal is to find the universal perturbation so that all the corrupted K examples can fool M. In this case, the notion of ‘domain’ in (4) is specified as ‘example’, and problem (4) becomes
  minimize 2X maximize w2P
  P K
  i=1 wif( ;xi, yi,M) 2 kw 1/Kk 2 2, (6)
  where different from (5), w encodes the difficulty level of attacking each example.
  Adversarial Attack over Data Transformations. Consider K categories of data transformation {pi}, e.g., rotation, lightening, and translation, our goal is to find the adversarial attack that is robust to data transformations. Such an attack setting is commonly applied to generate physical adversarial examples [5, 20]. Here the notion of ‘domain’ in (4) is specified as ‘data transformer’, and problem (4) becomes
  minimize 2X maximize w2P
  P K
  i=1 wiEt⇠pi [f(t(x0 + ); y0,M)] 2 kw 1/Kk 2 2, (7)
  where Et⇠pi [f(t(x0+ ); y0,M)] denotes the attack loss under the distribution of data transformation pi, and w encodes the difficulty level of attacking each type of transformed example x0. We remark that if w = 1/K, then problem (7) reduces to the existing expectation of transformation (EOT) setup used for physical attack generation [5].
  Benefits of Min-Max Attack Generation with Learnable Domain Weights w: We can interpret (5)-(7) as finding the robust adversarial attack against the worst-case environment that an adversary encounters, e.g., multiple victim models, data samples, and input transformations. The proposed min-max design of adversarial attacks leads to two main benefits. First, compared to the heuristic weighting strategy (e.g., clipping thresholds on the importance of individual attack losses [56]), our proposal is free of supervised manual adjustment on domain weights. Even by carefully tuning the heuristic weighting strategy, we find that our approach with self-adjusted w consistently outperforms the clipping strategy in [56] (see Table 2). Second, the learned domain weights can be used to assess the model robustness when facing different types of adversary. We refer readers to Figure 1c and
  Figure 6 for more details.
sections.heading: 3.2 Min-Max Algorithm for Adversarial Attack Generation
sections.text: Algorithm 1 APGDA to solve problem (4) 1: Input: given w(0) and (0). 2: for t = 1, 2, . . . , T do 3: outer min.: fixing w = w(t 1), call
  PGD (8) to update (t) 4: inner max.: fixing = (t), update w(t) with projected gradient ascent (9) 5: end for
  We propose the alternating projected gradient descent-ascent (APGDA) method (Algorithm 1) to solve problem (4). For ease of presentation, we write problems (5), (6), (7) into the general form minimize
  2X maximize w2P
  PK i=1 wiFi( ) 2 kw 1/Kk 2 2,
  where Fi denotes the ith individual attack loss. We show that at each iteration, APGDA takes only one-step PGD for outer minimization and one-step projected gradient ascent for inner maximization.
  Outer Minimization Considering w = w(t 1) and F ( ) := P K
  i=1 w (t 1) i
  Fi( ) in (4), we perform one-step PGD to update at iteration t,
  (t) = projX (t 1) ↵r F ( (t 1)) , (8)
  where proj(·) denotes the Euclidean projection operator, i.e., projX (a) = argminx2X kx ak22 at the point a, ↵ > 0 is a given learning rate, and r denotes the first-order gradient w.r.t. . If p = 1, then the projection function becomes the clip function. In Proposition 1, we derive the solution of projX (a) under different `p norms for p 2 {0, 1, 2}. Proposition 1. Given a point a 2 Rd and a constraint set X = { |k kp  ✏, č   ĉ}, the Euclidean projection ⇤ = projX (a) has a closed-form solution when p 2 {0, 1, 2}, where the specific form is given by Appendix A.
  Inner Maximization By fixing = (t) and letting (w) := P K
  i=1 wiFi( (t)) 2 kw 1/Kk 2 2
  in problem (4), we then perform one-step PGD (w.r.t. ) to update w,
  w(t) = projP ⇣ w(t 1) + rw (w
  (t 1))| {z } b
  ⌘ = (b µ1)+ , (9)
  where > 0 is a given learning rate, rw (w) = (t) (w 1/K), and (t) := [F1( (t)), . . . , FK( (t))]T . In (9), the second equality holds due to the closed-form of projection operation onto the probabilistic simplex P [49], where (x)+ = max{0, x}, and µ is the root of the equation 1T (b µ1)+ = 1. Since 1T (b mini{bi}1 + 1/K)+ 1T1/K = 1, and 1T (b maxi{bi}1 + 1/K)+  1T1/K = 1, the root µ exists within the interval [mini{bi} 1/K,maxi{bi} 1/K] and can be found via the bisection method [8].
  Convergence Analysis We remark that APGDA follows the gradient primal-dual optimization framework [37], and thus enjoys the same optimization guarantees. Theorem 1. Suppose that in problem (4) Fi( ) has L-Lipschitz continuous gradients, and X is a convex compact set. Given learning rates ↵ 
  1 L and < 1 , then the sequence { (t),w(t)}T t=1
  generated by Algorithm 1 converges to a first-order stationary point 2 in rate O 1 T .
  Proof : Note that the objective function of problem (4) is strongly concave w.r.t. w with parameter , and has -Lipschitz continuous gradients. Moreover, we have kwk2  1 due to w 2 P . Using these facts and Theorem 1 in [37] or [39] completes the proof. ⇤
sections.heading: 4 Experiments on Adversarial Exploration
sections.text: In this section, we first evaluate the proposed min-max optimization strategy on three attack tasks. We show that our approach leads to substantial improvement compared with state-of-the-art attack methods such as average ensemble PGD [34] and EOT [3, 10, 5]. We also demonstrate the effectiveness of learnable domain weights in guiding the adversary’s exploration over multiple domains.
sections.heading: 4.1 Experimental setup
sections.text: We thoroughly evaluate our algorithm on MNIST and CIFAR-10. A set of diverse image classifiers (denoted from Model A to Model H) are trained, including multi-layer perceptron (MLP), All-CNNs [61], LeNet [30], LeNetV2, VGG16 [58], ResNet50 [24], Wide-ResNet [40, 75] and GoogLeNet [63]. The details about model architectures and training process are provided in Appendix D.1. Note that problem formulations (5)-(7) are applicable to both untargeted and targeted attack. Here we focus on the former setting and use C&W loss function [13, 40] with a confidence parameter  = 50. The adversarial examples are generated by 20-step PGD/APGDA unless otherwise stated (e.g., 50 steps for ensemble attacks). APGDA algorithm is relatively robust and will not be affected largely by the choices of hyperparameters (↵, , ). Apart from absolute attack success rate (ASR), we also report the relative improvement or degradationon the worse-case performance in experiments: Lift("). The details of crafting adversarial examples are available in Appendix D.2.
sections.heading: 4.2 Ensemble Attack over Multiple Models
sections.text: We craft adversarial examples against an ensemble of known classifiers. Recent work [34] proposed an average ensemble PGD attack, which assumed equal importance among different models, namely, wi = 1/K in problem (5). Throughout this task, we measure the attack performance via ASRall - the attack success rate (ASR) of fooling model ensembles simultaneously. Compared to the average PGD attack, our approach results in 40.79% and 17.48% ASRall improvement averaged over different `p-norm constraints on MNIST and CIFAR-10, respectively. In what follows, we provide more detailed results and analysis.
  In Table 1 and Table 3, we show that AMGDA significantly outperforms average PGD in ASRall. Taking `1-attack on MNIST as an example, our min-max attack leads to a 90.16% ASRall, which
  2The stationarity is measured by the `2 norm of gradient of the objective in (4) w.r.t. ( ,w).
  largely outperforms 48.17%. The reason is that Model C, D are more difficult to attack, which can be observed from their higher test accuracy on adversarial examples. As a result, although the adversarial examples crafted by assigning equal weights over multiple models are able to attack {A, B} well, they achieve a much lower ASR in {C, D}. By contrast, APGDA automatically handles the worst case {C, D} by slightly sacrificing the performance on {A, B}: 31.47% averaged ASR improvement on {C, D} versus 0.86% degradation on {A, B}. The choices of ↵, , for all experiments and more results on CIFAR-10 are provided in Appendix D.2 and Appendix E.
  Effectiveness of learnable domain weights:
  Figure 1 depicts the ASR of four models under average/min-max attacks as well as the distribution of domain weights during attack generation. For average PGD (Figure 1a), Model C and D are attacked insufficiently, leading to relatively low ASR and thus weak ensemble performance. By contrast, APGDA (Figure 1b) will encode the difficulty level to attack different models based on the current attack loss. It dynamically adjusts the weight wi as shown in Figure 1c. For
  instance, the weight for Model D is first raised to 0.45 because D is difficult to attack initially. Then it decreases to 0.3 once Model D encounters the sufficient attack power and the corresponding attack performance is no longer improved. It is worth noticing that APGDA is highly efficient because wi converges after a small number of iterations. Figure 1c also shows wc > wd > wa > wb – indicating a decrease in model robustness for C, D, A and B, which is exactly verified by AccC > AccD > AccA > AccB in the last row of Table 1 (`1-norm). As the perturbation radius ✏ varies, we also observe that the ASR of min-max strategy is consistently better or on part with the average strategy (see Figure 2).
  Comparison with stronger heuristic baselines Apart from average strategy, we compare minmax framework with stronger heuristic weighting scheme in Table 2 (MNIST) and Table 4 (CIFAR10). Specifically, with the prior knowledge of robustness of given models (C > D > A > B), we devised several heuristic baselines including: (a) wc+d: average PGD on models C and D only; (b) wa+c+d: average PGD on models A, C and D only; (c) wclip: clipped version of C&W loss (threshold = 40) to balance model weights in optimization as suggested in [56]; (d) wprior: larger weights on the more robust models, wprior = [wA, wB , wC , wD] = [0.2, 0.1, 0.4, 0.3]; (e) wstatic: the converged mean weights of min-max (APGDA) ensemble attack. For `2 (✏ = 3.0) and `1 (✏ = 0.2) attacks, wstatic = [wA, wB , wC , wD] are [0.209, 0.046, 0.495, 0.250] and [0.080, 0.076, 0.541, 0.303], respectively. Table 2 shows that our approach achieve substantial improvement over baselines consistently. Moreover, we highlight that the use of learnable w avoids supervised manual adjustment on
  the heuristic weights or the choice of clipping threshold. Also, we show that even adopting converged min-max weights statically leads to a huge performance drop on attacking model ensembles, which again verifies the power of dynamically optimizing domain weights during attack generation process.
sections.heading: 4.3 Multi-Image Universal Perturbation
sections.text: We evaluate APGDA in universal perturbation on MNIST and CIFAR-10, where 10,000 test images are randomly divided into equal-size groups (K images per group) for universal perturbation. We measure two types of ASR (%), ASRavg and ASRall. Here the former represents the ASR averaged over all images in all groups, and the latter signifies the ASR averaged over all groups but a successful attack is counted under a more restricted condition: images within each group must be successfully attacked simultaneously by universal perturbation. In Table 5, we compare the proposed min-max strategy with the averaging strategy on the attack performance of generated universal perturbations. APGDA always achieves higher ASRall for different values of K. When K = 5, our approach achieves 42.63% and 35.21% improvement over the averaging strategy under MNIST and CIFAR-10. The universal perturbation generated from APGDA can successfully attack ‘hard’ images (on which the average-based PGD attack fails) by self-adjusting domain weights, and thus leads to a higher ASRall.
  Interpreting “image robustness” with domain weights w: The min-max universal perturbation also offers interpretability of “image robustness” by associating domain weights with image visualization. Figure 6 shows an example in which the large domain weight corresponds to the MNIST letter with clear appearance (e.g., bold letter). To empirically verify the robustness of image, we report two metrics to measure the difficulty of attacking single image: dist. (C&W `2) denotes the the minimum distortion of successfully attacking images using C&W (`2) attack; ✏min (`1) denotes the minimum perturbation magnitude for `1-PGD attack.
sections.heading: 4.4 Robust Attack over Data Transformations
sections.text: EOT [5] achieves state-of-the-art performance in producing adversarial examples robust to data transformations. From (7), we could derive EOT as a special case when the weights satisfy wi = 1/K (average case). For each input sample (ori), we transform the image under a series of functions, e.g., flipping horizontally (flh) or vertically (flv), adjusting brightness (bri), performing gamma correction
  (gam) and cropping (crop), and group each image with its transformed variants. Similar to universal perturbation, ASRall is reported to measure the ASR over groups of transformed images (each group is successfully attacked signifies successfully attacking an example under all transformers). In Table 7, compared to EOT, our approach leads to 9.39% averaged lift in ASRall over given models on CIFAR-10 by optimizing the weights for various transformations. We leave the the results under randomness (e.g., flipping images randomly w.p. 0.8; randomly clipping the images at specific range) in Appendix E
sections.heading: 5 Extension: Understanding Defense over Multiple Perturbation Domains
sections.text: In this section, we show that the min-max principle can also be used to gain more insights in generalized adversarial training (AT) from a defender’s perspective. Different from promoting robustness of adversarial examples against the worst-case attacking environment (Sec. 3), the generalized AT promotes model’s robustness against the worst-case defending environment, given by the existence of multiple `p attacks [65]. Our approach obtains better performance than prior works [65, 41] and interpretability by introducing the trainable domain weights.
sections.heading: 5.1 Adversarial Training under Mixed Types of Adversarial Attacks
sections.text: Conventional AT is restricted to a single type of norm-ball constrained adversarial attack [40]. For example, AT under `1 attack yields:
  minimize ✓ E(x,y)2D maximize k k1✏ ftr(✓, ;x, y), (10)
  where ✓ 2 Rn denotes model parameters, denotes ✏-tolerant `1 attack, and ftr(✓, ;x, y) is the training loss under perturbed examples {(x+ , y)}. However, there possibly exist blind attacking spots across multiple types of adversarial attacks so that AT under one attack would not be strong enough against another attack [2]. Thus, an interesting question is how to generalize AT under multiple types of adversarial attacks [65]. One possible way is to use the finite-sum formulation in the inner maximization problem of (10), namely, maximize{ i2Xi} 1 K P K
  i=1 ftr(✓, i;x, y), where i 2 Xi is the ith type of adversarial perturbation defined on Xi, e.g., different `p attacks.
  Since we can map ‘attack type’ to ‘domain’ considered in (1), AT can be generalized against the strongest adversarial attack across K attack types in order to avoid blind attacking spots:
  minimize ✓ E(x,y)2D maximize i2[K] maximize i2Xi ftr(✓, i;x, y). (11)
  In Lemma 1, we show that problem (11) can be equivalently transformed into the min-max form. Lemma 1. Problem (11) is equivalent to:
  minimize ✓ E(x,y)2D maximize w2P,{ i2Xi}
  KX
  i=1
  wiftr(✓, i;x, y), (12)
  where w 2 RK represent domain weights, and P has been defined in (1).
  The proof of Lemma 1 is provided in Appendix B. Similar to (4), a strongly concave regularizer /2kw 1/Kk22 can be added into the inner maximization problem of (12) for boosting the stability of the learning procedure and striking a balance between the max and the average attack performance:
  minimize ✓ E(x,y)2D maximize w2P,{ i2Xi} (✓,w, { i})
  (✓,w, { i}) := P K i=1 wiftr(✓, i;x, y) 2 kw 1/Kk 2 2
  (13)
  Algorithm 2 AMPGD to solve problem (13) 1: Input: given ✓(0), w(0), (0) and K > 0. 2: for t = 1, 2, . . . , T do 3: given w(t 1) and (t 1), perform SGD to
  update ✓(t)
  4: given ✓(t), perform R-step PGD to update w(t) and (t) 5: end for We propose the alternating multi-step projected gradient descent (AMPGD) method (Algorithm 2) to solve problem (13). Since AMPGD also follows the min-max principles, we defer more details of this algorithm in Appendix C. We finally remark that our formulation of generalized AT under multiple perturbations covers prior work [65] as special cases ( = 0 for max case and = 1 for average case).
sections.heading: 5.2 Generalized AT vs. Multiple `p Attacks
sections.text: Compared to vanilla AT, we show the generalized AT scheme produces model robust to multiple types of perturbation, thus leads to stronger “overall robustness”. We present experimental results of generalized AT following [41] to achieve simultaneous robustness to `1, `2, and `1 perturbations on the MNIST and CIFAR-10 datasets. To the best of our knowledge, MSD proposed in [41] is the state-of-the-art defense against multiple types of `p attacks. Specifically, we adopted the same architectures as [41] four layer convolutional networks on MNIST and the pre-activation version of the ResNet18 [24]. The perturbation radius ✏ for (`1, `2, `1) balls is set as (0.3, 2.0, 10) and (0.03, 0.5, 12) on MNIST and CIFAR-10 following [41]. Apart from the evaluation `p PGD attacks, we also incorporate the state-of-the-art AutoAttack [18] for a more comprehensive evaluation under mixed `p perturbations.
  The adversarial accuracy results are reported (higher the better). As shown in Table 8 and 9, our approach outperforms the state-of-the-art defense MSD consistently (4⇠6% and 2% improvements on MNIST and CIFAR-10). Compared to MSD that deploys an approximate arg max operation to select the steepest-descent (worst-case) universal perturbation, we leverage the domain weights to self-adjust the strengthens of diverse `p attacks. Thus, we believe that this helps gain supplementary robustness from individual attacks.
  Effectiveness of Domain Weights: Figure 3 shows the robust accuracy curves of MSD and AMPGD on MNIST. As we can see, the proposed AMPGD can quickly adjust the defense strengths to focus on more difficult adversaries - the gap of robust accuracy between three attacks is much smaller. Therefore, it achieves better results by avoiding the trade-off that biases one particular perturbation model at the cost of the others. In Figure 4, we offer deeper insights on how the domain weights work as the strengths of adversary vary. Specifically, we consider two perturbation models on MNIST: `2 and `1. During the training, we fix the ✏ for `1 attack during training as 0.2, and change the ✏ for `2 from 1.0 to 4.0. As shown in Figure 4, the domain weight w increases when the `2-attack becomes stronger i.e., ✏(`2) increases, which is consistent with min-max spirit – defending the strongest attack.
sections.heading: 5.3 Additional Discussions
sections.text: More parameters to tune for min-max? Our min-max approaches (APGDA and AMPGD) introduce two more hyperparameters - and . However, our proposal performs reasonably well by choosing the learning rate ↵ same as standard PGD and using a large range of regularization coefficient 2 [0, 10]; see Fig. A5 in Appendix. For the learning rate to update domain weights, we found 1/T is usually a very good practice, where T is the total number of attack iterations.
  Time complexity of inner maximization? Our proposal achieves significant improvements at a low cost of extra computation. Specifically, (1) our APGDA attack is 1.31⇥ slower than the average PGD; (2) our AMPGD defense is 1.15⇥ slower than average or max AT [65].
  How efficient is the APGDA (Algorithm 1) for solving problem (4)? We remark that the minmax attack generation setup obeys the nonconvex + strongly concave optimization form. Our proposed APGDA is a single-loop algorithm, which is known to achieve a nearly optimal convergence rate for nonconvex-strongly concave min-max optimization [32, Table 1]. Furthermore, as our solution gives a natural extension from the commonly-used PGD attack algorithm by incorporating the inner maximization step (9), it is easy to implement based on existing frameworks.
  Clarification on contributions: Our contribution is not to propose a new or more efficient optimization approach for solving min-max optimization problems. Instead, we focus on introducing this formulation to the attack design domain, which has not been studied systematically before. We believe this work is the first solid step to explore the power of min-max principle in the attack design and achieve superior performance on multiple attack tasks.
sections.heading: 6 Conclusion
sections.text: In this paper, we revisit the strength of min-max optimization in the context of adversarial attack generation. Beyond adversarial training (AT), we show that many attack generation problems can be re-formulated in our unified min-max framework, where the maximization is taken over the probability simplex of the set of domains. Experiments show our min-max attack leads to significant improvements on three tasks. Importantly, we demonstrate the self-adjusted domain weights not only stabilize the training procedure but also provides a holistic tool to interpret the risk of different domain sources. Our min-max principle also helps understand the generalized AT against multiple adversarial attacks. Our approach results in superior performance as well as intepretability.
  Broader Impacts
  Our work provides a unified framework in design of adversarial examples and robust defenses. The generated adversarial examples can be used to evaluate the robustness of state-of-the-art deep learning vision systems. In spite of different kinds of adversaries, the proposed defense solves one for all by taking into account adversaries’ diversity. Our work is a beneficial supplement to building trustworthy AI systems, in particular for safety-critical AI applications, such as autonomous vehicles and camera surveillance. We do not see negative impacts of our work on its ethical aspects and future societal consequences.
sections.heading: Acknowledgement
sections.text: We sincerely thank the anonymous reviewers for their insightful suggestions and feedback. This work is partially supported by the NSF grant No.1910100, NSF CNS 20-46726 CAR, NSF CAREER CMMI-1750531, NSF ECCS-1609916, and the Amazon Research Award. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.
title: Adversarial Attack Generation Empowered by Min-Max Optimization