Evaluating the adversarial robustness of deep networks to gradient-based attacks is challenging. While most attacks focus `2-norm and `1-norm constraints to craft input perturbations, only a few have investigated sparse `1-norm and `0-norm attacks. In particular, `0-norm attacks remain the least studied due to the inherent complexity of optimizing over a non-convex and non-differentiable constraint. However, evaluating the robustness of these attacks might unveil weaknesses otherwise left untested with conventional `2 and `1 attacks. In this work, we propose a novel `0-norm attack, called -zero, which leverages an ad-hoc differentiable approximation of the `0 norm to facilitate gradient-based optimization. Extensive evaluations on MNIST, CIFAR10, and ImageNet datasets, involving robust and non-robust models, show that -zero can find minimum `0-norm adversarial examples without requiring any time-consuming hyperparameter tuning, and that it outperforms all competing attacks in terms of success rate and scalability.
International Conference on Learning Representations (ICLR)
2025-04-24
2025-03-06