  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).
