Abstract: We propose a versatile framework based on random search, \texttt{Sparse-RS}, for score-based sparse targeted and untargeted attacks in the black-box setting. \texttt{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 \texttt{Sparse-RS} outperforms all black-box and even all white-box attacks for different models on MNIST, CIFAR-10, and ImageNet. Moreover, our untargeted \texttt{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 \texttt{Sparse-RS} can be applied to generate targeted universal adversarial patches where it significantly outperforms the existing approaches.