Query-Efficient Hard-label Black-box Attack: An Optimization-based Approach

By Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, Cho-Jui Hsieh. International Conference on Learning Representations, 2018

383 citations recorded by the source corpus.

We study the problem of attacking a machine learning model in the hard-label black-box setting, where no model information is revealed except that the attacker can make queries to probe the corresponding hard-label decisions. This is a very challenging problem since the direct extension of state-of-the-art white-box attacks (e.g., CW or PGD) to the hard-label black-box setting will require minimizing a non-continuous step function, which is combinatorial and cannot be solved by a gradient-based optimizer. The only current approach is based on random walk on the boundary, which requires lots of queries and lacks convergence guarantees. We propose a novel way to formulate the hard-label black-box attack as a real-valued optimization problem which is usually continuous and can be solved by any zeroth order optimization algorithm. For example, using the Randomized Gradient-Free method, we are able to bound the number of iterations needed for our algorithm to achieve stationary points. We demonstrate that our proposed method outperforms the previous random walk approach to attacking convolutional neural networks on MNIST, CIFAR, and ImageNet datasets. More interestingly, we show that the proposed algorithm can also be used to attack other discrete and non-continuous machine learning models, such as Gradient Boosting Decision Trees (GBDT).

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/b862efa06baea0b032214675eb3c3645d5d69d46

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Benchmarking Adversarial Robustness on Image Classification (2020, methodology): “An optimization-based method [9] formulates this problem as a continuous optimization problem and estimates the gradient to solve it.”
A Survey of Black-Box Adversarial Attacks on Computer Vision Models (2019, methodology): “[13] Opt-Attack Oct 2018 Bhagoji et al.”
Boosting Decision-Based Black-Box Adversarial Attacks with Random Sign Flip (2020, methodology): “[12] reformulated the original problem to a continuous version and applied zeroth order optimization.”
Advances in adversarial attacks and defenses in computer vision: A survey (2021, methodology): “[83] also claimed a query efficient attack, altering the optimization objective of their previous work [84] that performed a binary search to estimate the gradient of the target model using query results.”
Efficient Decision-Based Black-Box Adversarial Attacks on Face Recognition (2019, methodology): “We perform dodging attack and impersonation attack by Boundary, Optimization, NES-LO and the proposed Evolutionary method against SphereFace, CosFace, and ArcFace, respectively.”
Simple Black-box Adversarial Attacks (2019, methodology): “To date, the average number of queries performed by the best known black-box attacks remains high despite a large amount of recent work in this area (Chen et al., 2017; Brendel et al., 2017; Cheng et al., 2018; Guo et al., 2018; Tu et al., 2018; Ilyas et al., 2018a).”
Is Robustness the Cost of Accuracy? - A Comprehensive Study on the Robustness of 18 Deep Image Classification Models (2018, background): “Since transfer attack is widely used in the black-box setting [31,32,33,34,35,36], where an adversary has no access to the explicit knowledge of the target models, this experiment can provide some evidence on networks’ black-box robustness.”
HopSkipJumpAttack: A Query-Efficient Decision-Based Attack (2019, methodology): “Recent years have witnessed a flurry of research on the design of new algorithms for generating adversarial examples [1–16].”
Universal Decision-Based Black-Box Perturbations: Breaking Security-Through-Obscurity Defenses (2018, methodology): “Algorithm 2 RGF for universal hard-label black-box attack (See also Cheng et al. [2018]) Input: Hard-label model f , original image label pairs {(x1, y1), .”
Square Attack: a query-efficient black-box adversarial attack via random search (2019, background): “A more restrictive scenario, considered by decision-based attacks [9,16,27,11,13], is when the attacker can query only the decision of the classifier, but not the predicted scores.”