  We study the most practical problem setup for evaluating adversarial
robustness of a machine learning system with limited access: the hard-label
black-box attack setting for generating adversarial examples, where limited
model queries are allowed and only the decision is provided to a queried data
input. Several algorithms have been proposed for this problem but they
typically require huge amount (>20,000) of queries for attacking one example.
Among them, one of the state-of-the-art approaches (Cheng et al., 2019) showed
that hard-label attack can be modeled as an optimization problem where the
objective function can be evaluated by binary search with additional model
queries, thereby a zeroth order optimization algorithm can be applied. In this
paper, we adopt the same optimization formulation but propose to directly
estimate the sign of gradient at any direction instead of the gradient itself,
which enjoys the benefit of single query. Using this single query oracle for
retrieving sign of directional derivative, we develop a novel query-efficient
Sign-OPT approach for hard-label black-box attack. We provide a convergence
analysis of the new algorithm and conduct experiments on several models on
MNIST, CIFAR-10 and ImageNet. We find that Sign-OPT attack consistently
requires 5X to 10X fewer queries when compared to the current state-of-the-art
approaches, and usually converges to an adversarial example with smaller
perturbation.
