  We propose a versatile framework based on random search, Sparse-RS, for
score-based sparse targeted and untargeted attacks in the black-box setting.
Sparse-RS does not rely on substitute models and achieves state-of-the-art
success rate and query efficiency for multiple sparse attack models:
$l_0$-bounded perturbations, adversarial patches, and adversarial frames. The
$l_0$-version of untargeted Sparse-RS outperforms all black-box and even all
white-box attacks for different models on MNIST, CIFAR-10, and ImageNet.
Moreover, our untargeted Sparse-RS achieves very high success rates even for
the challenging settings of $20\times20$ adversarial patches and $2$-pixel wide
adversarial frames for $224\times224$ images. Finally, we show that Sparse-RS
can be applied to generate targeted universal adversarial patches where it
significantly outperforms the existing approaches. The code of our framework is
available at https://github.com/fra31/sparse-rs.
