{
  "id": "2402.01879",
  "version": "v2",
  "published": "2024-02-02T20:08:11.000Z",
  "updated": "2024-10-02T12:42:56.000Z",
  "title": "$σ$-zero: Gradient-based Optimization of $\\ell_0$-norm Adversarial Examples",
  "authors": [
    "Antonio Emanuele Cinà",
    "Francesco Villani",
    "Maura Pintor",
    "Lea Schönherr",
    "Battista Biggio",
    "Marcello Pelillo"
  ],
  "comment": "Code available at https://github.com/Cinofix/sigma-zero-adversarial-attack",
  "categories": [
    "cs.LG",
    "cs.CR",
    "cs.CV"
  ],
  "abstract": "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 $\\sigma$-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 $\\sigma$-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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2024-10-02T12:42:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "norm adversarial examples",
      "gradient-based optimization",
      "zero finds minimum",
      "norm attacks remain",
      "craft input perturbations"
    ],
    "tags": [
      "github project"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}