  The goal of a decision-based adversarial attack on a trained model is to
generate adversarial examples based solely on observing output labels returned
by the targeted model. We develop HopSkipJumpAttack, a family of algorithms
based on a novel estimate of the gradient direction using binary information at
the decision boundary. The proposed family includes both untargeted and
targeted attacks optimized for $\ell_2$ and $\ell_\infty$ similarity metrics
respectively. Theoretical analysis is provided for the proposed algorithms and
the gradient direction estimate. Experiments show HopSkipJumpAttack requires
significantly fewer model queries than Boundary Attack. It also achieves
competitive performance in attacking several widely-used defense mechanisms.
(HopSkipJumpAttack was named Boundary Attack++ in a previous version of the
preprint.)
