$σ$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples
This work addresses the challenge of assessing adversarial vulnerabilities in deep networks for security-critical applications, offering a more efficient and effective sparse attack method, though it is incremental as it builds on prior sparse attack research.
The paper tackles the problem of evaluating adversarial robustness under sparse ℓ₀-norm attacks by proposing σ-zero, a novel gradient-based method that uses a differentiable approximation and adaptive projection, achieving higher success rates, smaller perturbations, and greater efficiency than existing sparse attacks on datasets like MNIST, CIFAR10, and ImageNet.
Evaluating the adversarial robustness of deep networks to gradient-based attacks is challenging. While most attacks consider $\ell_2$- and $\ell_\infty$-norm constraints to craft input perturbations, only a few investigate sparse $\ell_1$- and $\ell_0$-norm attacks. In particular, $\ell_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 $\ell_2$- and $\ell_\infty$-norm attacks. In this work, we propose a novel $\ell_0$-norm attack, called $σ$-zero, which leverages a differentiable approximation of the $\ell_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 $σ$\texttt{-zero} finds minimum $\ell_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.