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

本文提出一种用于攻击离散和非连续的机器学习模型的新方法，将难标记黑盒攻击转化为实值优化问题，并且在 MNIST，CIFAR 和 ImageNet 数据集上展示出比现有方法更优异的表现。