Article

Square Attack: A Query-Efficient Black-Box Adversarial Attack via Random Search

Authors:

Maksym Andriushchenko,

Francesco Croce,

Nicolas Flammarion,

Matthias HeinAuthors Info & Claims

Computer Vision – ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXIII

Pages 484 - 501

https://doi.org/10.1007/978-3-030-58592-1_29

Published: 23 August 2020 Publication History

Abstract

We propose the Square Attack, a score-based black-box

l_{2}

- and

l_{\infty}

-adversarial attack that does not rely on local gradient information and thus is not affected by gradient masking. Square Attack is based on a randomized search scheme which selects localized square-shaped updates at random positions so that at each iteration the perturbation is situated approximately at the boundary of the feasible set. Our method is significantly more query efficient and achieves a higher success rate compared to the state-of-the-art methods, especially in the untargeted setting. In particular, on ImageNet we improve the average query efficiency in the untargeted setting for various deep networks by a factor of at least 1.8 and up to 3 compared to the recent state-of-the-art

l_{\infty}

-attack of Al-Dujaili & O’Reilly (2020). Moreover, although our attack is black-box, it can also outperform gradient-based white-box attacks on the standard benchmarks achieving a new state-of-the-art in terms of the success rate. The code of our attack is available at https://github.com/max-andr/square-attack.

References

[1]

Akhtar N and Mian A Threat of adversarial attacks on deep learning in computer vision: a survey IEEE Access 2018 6 14410-14430

[2]

Al-Dujaili, A., O’Reilly, U.M.: There are no bit parts for sign bits in black-box attacks. In: ICLR (2020)

[3]

Alzantot, M., Sharma, Y., Chakraborty, S., Srivastava, M.: GenAttack: practical black-box attacks with gradient-free optimization. In: Genetic and Evolutionary Computation Conference (GECCO) (2019)

[4]

Athalye, A., Carlini, N., Wagner, D.A.: Obfuscated gradients give a false sense of security: circumventing defenses to adversarial examples. In: ICML (2018)

[5]

Bastani, O., Ioannou, Y., Lampropoulos, L., Vytiniotis, D., Nori, A., Criminisi, A.: Measuring neural net robustness with constraints. In: NeurIPS (2016)

[6]

Bhagoji AN, He W, Li B, and Song D Ferrari V, Hebert M, Sminchisescu C, and Weiss Y Practical black-box attacks on deep neural networks using efficient query mechanisms Computer Vision – ECCV 2018 2018 Cham Springer 158-174

Digital Library

[7]

Biggio B and Roli F Wild patterns: ten years after the rise of adversarial machine learning Pattern Recogn. 2018 84 317-331

Digital Library

[8]

Brendel, W., Rauber, J., Bethge, M.: Decision-based adversarial attacks: reliable attacks against black-box machine learning models. In: ICLR (2018)

[9]

Brunner, T., Diehl, F., Le, M.T., Knoll, A.: Guessing smart: biased sampling for efficient black-box adversarial attacks. In: ICCV (2019)

[10]

Carlini, N., Wagner, D.: Adversarial examples are not easily detected: bypassing ten detection methods. In: ACM Workshop on Artificial Intelligence and Security (2017)

[11]

Chen, J., Jordan, M.I., J., W.M.: HopSkipJumpAttack: a query-efficient decision-based attack (2019). arXiv preprint arXiv:1904.02144

[12]

Chen, P., Sharma, Y., Zhang, H., Yi, J., Hsieh, C.: EAD: elastic-net attacks to deep neural networks via adversarial examples. In: AAAI (2018)

[13]

Chen, P.Y., Zhang, H., Sharma, Y., Yi, J., Hsieh, C.J.: ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In: 10th ACM Workshop on Artificial Intelligence and Security - AISec 2017. ACM Press (2017)

[14]

Cheng, M., Le, T., Chen, P.Y., Yi, J., Zhang, H., Hsieh, C.J.: Query-efficient hard-label black-box attack: an optimization-based approach. In: ICLR (2019)

[15]

Cheng, S., Dong, Y., Pang, T., Su, H., Zhu, J.: Improving black-box adversarial attacks with a transfer-based prior. In: NeurIPS (2019)

[16]

Croce, F., Hein, M.: Sparse and imperceivable adversarial attacks. In: ICCV (2019)

[17]

Croce, F., Hein, M.: Minimally distorted adversarial examples with a fast adaptive boundary attack. In: ICML (2020)

[18]

Croce, F., Hein, M.: Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In: ICML (2020)

[19]

Davis D and Drusvyatskiy D Stochastic model-based minimization of weakly convex functions SIAM J. Optim. 2019 29 1 207-239

Digital Library

[20]

Du, J., Zhang, H., Zhou, J.T., Yang, Y., Feng, J.: Query-efficient meta attack to deep neural networks. In: ICLR (2020)

[21]

Duchi J, Jordan M, Wainwright M, and Wibisono A Optimal rates for zero-order convex optimization: the power of two function evaluations IEEE Trans. Inf. Theory 2015 61 5 2788-2806

Digital Library

[22]

Fawzi, A., Frossard, P.: Measuring the effect of nuisance variables on classifiers. In: British Machine Vision Conference (BMVC) (2016)

[23]

Gu, S., Rigazio, L.: Towards deep neural network architectures robust to adversarial examples. In: ICLR Workshop (2015)

[24]

Guo, C., Frank, J.S., Weinberger, K.Q.: Low frequency adversarial perturbation. In: UAI (2019)

[25]

Guo, C., Gardner, J.R., You, Y., Wilson, A.G., Weinberger, K.Q.: Simple black-box adversarial attacks. In: ICML (2019)

[26]

Haagerup U The best constants in the Khintchine inequality Studia Math. 1981 70 3 231-283

[27]

Ilyas, A., Engstrom, L., Athalye, A., Lin, J.: Black-box adversarial attacks with limited queries and information. In: ICML (2018)

[28]

Ilyas, A., Engstrom, L., Madry, A.: Prior convictions: black-box adversarial attacks with bandits and priors. In: ICLR (2019)

[29]

Ilyas, A., Santurkar, S., Tsipras, D., Engstrom, L., Tran, B., Madry, A.: Adversarial examples are not bugs, they are features. In: NeurIPS (2019)

[30]

Kannan, H., Kurakin, A., Goodfellow, I.: Adversarial logit pairing (2018). arXiv preprint arXiv:1803.06373

[31]

Li, Y., Li, L., Wang, L., Zhang, T., Gong, B.: NATTACK: learning the distributions of adversarial examples for an improved black-box attack on deep neural networks. In: ICML (2019)

[32]

Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A.: Towards deep learning models resistant to adversarial attacks. In: ICLR (2018)

[33]

Matyas J Random optimization Autom. Remote Control 1965 26 2 246-253

[34]

Meunier, L., Atif, J., Teytaud, O.: Yet another but more efficient black-box adversarial attack: tiling and evolution strategies (2019). arXiv preprint, arXiv:1910.02244

[35]

Mosbach, M., Andriushchenko, M., Trost, T., Hein, M., Klakow, D.: Logit pairing methods can fool gradient-based attacks. In: NeurIPS 2018 Workshop on Security in Machine Learning (2018)

[36]

Narodytska, N., Kasiviswanathan, S.: Simple black-box adversarial attacks on deep neural networks. In: CVPR Workshops (2017)

[37]

Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. Wiley, Hoboken (1983)

[38]

Nesterov Y and Spokoiny V Random gradient-free minimization of convex functions Found. Comput. Math. 2017 17 2 527-566

Digital Library

[39]

Papernot, N., McDaniel, P., Goodfellow, I.: Transferability in machine learning: from phenomena to black-box attacks using adversarial samples (2016). arXiv preprint arXiv:1605.07277

[40]

Papernot, N., McDaniel, P., Wu, X., Jha, S., Swami, A.: Distillation as a defense to adversarial perturbations against deep networks. In: IEEE Symposium on Security & Privacy (2016)

[41]

Rastrigin L The convergence of the random search method in the extremal control of a many parameter system Autom. Remote Control 1963 24 1337-1342

[42]

Schrack G and Choit M Optimized relative step size random searches Math. Program. 1976 10 230-244

Digital Library

[43]

Schumer M and Steiglitz K Adaptive step size random search IEEE Trans. Automat. Control 1968 13 3 270-276

[44]

Seungyong, M., Gaon, A., Hyun, O.S.: Parsimonious black-box adversarial attacks via efficient combinatorial optimization. In: ICML (2019)

[45]

Shukla, S.N., Sahu, A.K., Willmott, D., Kolter, Z.: Black-box adversarial attacks with Bayesian optimization (2019). arXiv preprint arXiv:1909.13857

[46]

Su J, Vargas D, and Sakurai K One pixel attack for fooling deep neural networks IEEE Trans. Evol. Comput. 2019 23 828-841

[47]

Suya, F., Chi, J., Evans, D., Tian, Y.: Hybrid batch attacks: finding black-box adversarial examples with limited queries (2019). arXiv preprint, arXiv:1908.07000

[48]

Tramèr, F., Boneh, D.: Adversarial training and robustness for multiple perturbations. In: NeurIPS (2019)

[49]

Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., Madry, A.: Robustness may be at odds with accuracy. In: ICLR (2019)

[50]

Tu, C.C., et al.: Autozoom: autoencoder-based zeroth order optimization method for attacking black-box neural networks. In: AAAI Conference on Artificial Intelligence (2019)

[51]

Uesato, J., O’Donoghue, B., Van den Oord, A., Kohli, P.: Adversarial risk and the dangers of evaluating against weak attacks. In: ICML (2018)

[52]

Yan, Z., Guo, Y., Zhang, C.: Subspace attack: exploiting promising subspaces for query-efficient black-box attacks. In: NeurIPS (2019)

[53]

Yin, D., Lopes, R.G., Shlens, J., Cubuk, E.D., Gilmer, J.: A Fourier perspective on model robustness in computer vision. In: NeurIPS (2019)

[54]

Zabinsky, Z.B.: Random search algorithms. In: Wiley Encyclopedia of Operations Research and Management Science (2010)

[55]

Zhang, H., Yu, Y., Jiao, J., Xing, E.P., Ghaoui, L.E., Jordan, M.I.: Theoretically principled trade-off between robustness and accuracy. In: ICML (2019)

[56]

Zheng, S., Song, Y., Leung, T., Goodfellow, I.J.: Improving the robustness of deep neural networks via stability training. In: CVPR (2016)

[57]

Zheng, T., Chen, C., Ren, K.: Distributionally adversarial attack. In: AAAI (2019)

Cited By

Badjie BCecílio JCasimiro A(2024)Adversarial Attacks and Countermeasures on Image Classification-based Deep Learning Models in Autonomous Driving Systems: A Systematic ReviewACM Computing Surveys10.1145/369162557:1(1-52)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3691625
Wang WWang CQi HYe MQian XWang PZhang YCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Sustainable Self-evolution Adversarial TrainingProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681077(9799-9808)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681077
Wang XChen KMa XChen ZChen JJiang YCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)AdvQDet: Detecting Query-Based Adversarial Attacks with Adversarial Contrastive Prompt TuningProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681032(6212-6221)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681032
Show More Cited By

Recommendations

Query-Efficient Black-Box Adversarial Attack with Random Pattern Noises
Information and Communications Security
Abstract
Adversarial examples are one of the largest vulnerability of deep neural networks. An attacker can deceive the classifiers easily with the malicious inputs (called adversarial examples), which perturbations are slightly added to benign inputs. ... $_{}$
PhantomSound: Black-Box, Query-Efficient Audio Adversarial Attack via Split-Second Phoneme Injection
RAID '23: Proceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses

In this paper, we propose PhantomSound, a query-efficient black-box attack toward voice assistants. Existing black-box adversarial attacks on voice assistants either apply substitution models or leverage the intermediate model output to estimate the ...
Black-box adversarial attacks on XSS attack detection model
Abstract
Cross-site scripting (XSS) has been extensively studied, although mitigating such attacks in web applications remains challenging. While there is an increasing number of XSS attack detection approaches designed based on machine learning and deep ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Computer Vision – ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXIII

Aug 2020

839 pages

ISBN:978-3-030-58591-4

DOI:10.1007/978-3-030-58592-1

Editors:
Andrea Vedaldi
University of Oxford, Oxford, UK
,
Horst Bischof
Graz University of Technology, Graz, Austria
,
Thomas Brox
University of Freiburg, Freiburg im Breisgau, Germany
,
Jan-Michael Frahm
University of North Carolina at Chapel Hill, Chapel Hill, NC, USA

© Springer Nature Switzerland AG 2020.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 August 2020

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

97
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Badjie BCecílio JCasimiro A(2024)Adversarial Attacks and Countermeasures on Image Classification-based Deep Learning Models in Autonomous Driving Systems: A Systematic ReviewACM Computing Surveys10.1145/369162557:1(1-52)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3691625
Wang WWang CQi HYe MQian XWang PZhang YCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Sustainable Self-evolution Adversarial TrainingProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681077(9799-9808)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681077
Wang XChen KMa XChen ZChen JJiang YCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)AdvQDet: Detecting Query-Based Adversarial Attacks with Adversarial Contrastive Prompt TuningProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681032(6212-6221)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681032
Tong HZhang XJin YLou JWu KChen XCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Balancing Generalization and Robustness in Adversarial Training via Steering through Clean and Adversarial Gradient DirectionsProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3680963(1014-1023)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3680963
Li YXie BGuo SYang YXiao B(2024)A Survey of Robustness and Safety of 2D and 3D Deep Learning Models against Adversarial AttacksACM Computing Surveys10.1145/363655156:6(1-37)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3636551
Chaalan TPang SKamruzzaman JGondal IZhang X(2024)The Path to Defence: A Roadmap to Characterising Data Poisoning Attacks on Victim ModelsACM Computing Surveys10.1145/362753656:7(1-39)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.1145/3627536
Jia XChen YMao XDuan RGu JZhang RXue HLiu YCao X(2024)Revisiting and Exploring Efficient Fast Adversarial Training via LAW: Lipschitz Regularization and Auto Weight AveragingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.342012819(8125-8139)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3420128
Eleftheriadis CSymeonidis AKatsaros P(2024)Adversarial robustness improvement for deep neural networksMachine Vision and Applications10.1007/s00138-024-01519-135:3Online publication date: 14-Mar-2024
https://dl.acm.org/doi/10.1007/s00138-024-01519-1
Li YYou SChen YLi Z(2024)Efficient Local Imperceptible Random Search for Black-Box Adversarial AttacksAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5612-4_28(325-336)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-5612-4_28
Wang ZWang HTian CJin Y(2024)Preventing Catastrophic Overfitting in Fast Adversarial Training: A Bi-level Optimization PerspectiveComputer Vision – ECCV 202410.1007/978-3-031-73390-1_9(144-160)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-73390-1_9
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents