Sparse-RS: A Versatile Framework for Query-Efficient Sparse Black-Box Adversarial Attacks


  • Francesco Croce University of Tübingen
  • Maksym Andriushchenko EPFL
  • Naman D. Singh University of Tübingen
  • Nicolas Flammarion EPFL
  • Matthias Hein University of Tübingen



Machine Learning (ML), Computer Vision (CV)


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: L0-bounded perturbations, adversarial patches, and adversarial frames. The L0-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 20x20 adversarial patches and 2-pixel wide adversarial frames for 224x224 images. Finally, we show that Sparse-RS can be applied to generate targeted universal adversarial patches where it significantly outperforms the existing approaches. Our code is available at




How to Cite

Croce, F., Andriushchenko, M., Singh, N. D., Flammarion, N., & Hein, M. (2022). Sparse-RS: A Versatile Framework for Query-Efficient Sparse Black-Box Adversarial Attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 36(6), 6437-6445.



AAAI Technical Track on Machine Learning I