Query Complexity of Adversarial Attacks

Grzegorz Gluch, Rüdiger Urbanke
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:3723-3733, 2021.

Abstract

There are two main attack models considered in the adversarial robustness literature: black-box and white-box. We consider these threat models as two ends of a fine-grained spectrum, indexed by the number of queries the adversary can ask. Using this point of view we investigate how many queries the adversary needs to make to design an attack that is comparable to the best possible attack in the white-box model. We give a lower bound on that number of queries in terms of entropy of decision boundaries of the classifier. Using this result we analyze two classical learning algorithms on two synthetic tasks for which we prove meaningful security guarantees. The obtained bounds suggest that some learning algorithms are inherently more robust against query-bounded adversaries than others.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-gluch21a, title = {Query Complexity of Adversarial Attacks}, author = {Gluch, Grzegorz and Urbanke, R{\"u}diger}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {3723--3733}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/gluch21a/gluch21a.pdf}, url = {https://proceedings.mlr.press/v139/gluch21a.html}, abstract = {There are two main attack models considered in the adversarial robustness literature: black-box and white-box. We consider these threat models as two ends of a fine-grained spectrum, indexed by the number of queries the adversary can ask. Using this point of view we investigate how many queries the adversary needs to make to design an attack that is comparable to the best possible attack in the white-box model. We give a lower bound on that number of queries in terms of entropy of decision boundaries of the classifier. Using this result we analyze two classical learning algorithms on two synthetic tasks for which we prove meaningful security guarantees. The obtained bounds suggest that some learning algorithms are inherently more robust against query-bounded adversaries than others.} }
Endnote
%0 Conference Paper %T Query Complexity of Adversarial Attacks %A Grzegorz Gluch %A Rüdiger Urbanke %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-gluch21a %I PMLR %P 3723--3733 %U https://proceedings.mlr.press/v139/gluch21a.html %V 139 %X There are two main attack models considered in the adversarial robustness literature: black-box and white-box. We consider these threat models as two ends of a fine-grained spectrum, indexed by the number of queries the adversary can ask. Using this point of view we investigate how many queries the adversary needs to make to design an attack that is comparable to the best possible attack in the white-box model. We give a lower bound on that number of queries in terms of entropy of decision boundaries of the classifier. Using this result we analyze two classical learning algorithms on two synthetic tasks for which we prove meaningful security guarantees. The obtained bounds suggest that some learning algorithms are inherently more robust against query-bounded adversaries than others.
APA
Gluch, G. & Urbanke, R.. (2021). Query Complexity of Adversarial Attacks. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:3723-3733 Available from https://proceedings.mlr.press/v139/gluch21a.html.

Related Material