σ-zero: Gradient-based Optimization of ℓ0-norm Adversarial Examples

Evaluating the adversarial robustness of deep networks to gradient-based attacks is challenging. While most attacks consider ω 2 -and ω → -norm constraints to craft input perturbations, only a few investigate sparse ω 1 -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 adversarial robustness under these attacks could reveal weaknesses otherwise left untested with more conventional ω 2 -and ω → -norm attacks. In this work, we propose a novel ω 0 -norm attack, called ε-zero, which leverages a differentiable approximation of the ω 0 norm to facilitate gradient-based optimization, and an adaptive projection operator to dynamically adjust the trade-off between loss minimization and perturbation sparsity. Extensive evaluations using MNIST, CIFAR10, and ImageNet datasets, involving robust and non-robust models, show that ε-zero finds minimum ω 0 -norm adversarial examples without requiring any time-consuming hyperparameter tuning, and that it outperforms all competing sparse attacks in terms of success rate, perturbation size, and efficiency.