  We propose the Square Attack, a score-based black-box $l_2$- and
$l_\infty$-adversarial attack that does not rely on local gradient information
and thus is not affected by gradient masking. Square Attack is based on a
randomized search scheme which selects localized square-shaped updates at
random positions so that at each iteration the perturbation is situated
approximately at the boundary of the feasible set. Our method is significantly
more query efficient and achieves a higher success rate compared to the
state-of-the-art methods, especially in the untargeted setting. In particular,
on ImageNet we improve the average query efficiency in the untargeted setting
for various deep networks by a factor of at least $1.8$ and up to $3$ compared
to the recent state-of-the-art $l_\infty$-attack of Al-Dujaili & O'Reilly.
Moreover, although our attack is black-box, it can also outperform
gradient-based white-box attacks on the standard benchmarks achieving a new
state-of-the-art in terms of the success rate. The code of our attack is
available at https://github.com/max-andr/square-attack.
