Research map / Adversarial robustness and security / Certified and empirical robustness
$\sigma$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes σ-zero, a gradient-based minimum-ℓ0-norm adversarial attack using a differentiable ℓ0 approximation and an adaptive sparsity projection, evaluated on MNIST, CIFAR-10 and ImageNet robust models.
Problem
Finding minimum ℓ0-norm adversarial perturbations is NP-hard and non-differentiable; existing ℓ0 attacks trade off between accuracy and efficiency, which can overestimate DNN robustness.
Approach
Approximates the ℓ0 norm with a smooth term sum x_i^2/(x_i^2+σ) optimized by gradient descent, combined with an adaptive projection that zeroes small components with a sparsity threshold τ that is raised when the sample is already adversarial and lowered otherwise, removing the need for a trade-off hyperparameter or adversarial initialization.
Key results
- On CIFAR-10 C3, σ-zero reduces the median ℓ0 perturbation from 52 (FMN) to 32 features.
- On ImageNet I4, median ℓ0 is reduced from 58 (FMN) to 23 features; σ-zero reaches 100% ASR_∞ on all evaluated configurations.
- σ-zero is about 10x faster than BBadv on C4 and 100x faster on I3 on ImageNet.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use σ-zero instead of BB | attacking cnnddnshort · MNIST, cnnddnshort | ASR₍₂₄₎: 71.23 -> 83.79 | Helped |
| use σ-zero instead of BB | attacking cnntradesshort · MNIST, cnntradesshort | ASR₍₂₄₎: 56.53 -> 98.03 | Helped |
| use σ-zero instead of BBadv | attacking CIFAR-10 C1 · CIFAR-10, C1 | ASR₍₂₄₎: 65.96 -> 76.53 | Helped |
| use σ-zero instead of BBadv | attacking CIFAR-10 C3 · CIFAR-10, C3 | ASR₍₂₄₎: 36.47 -> 38.60 | Helped |
| use σ-zero instead of BBadv | attacking ImageNet I1 · ImageNet, I1 | ASR₍₂₄₎: 77.5 -> 82.6 | Helped |
| use σ-zero instead of BBadv | attacking ImageNet I3 · ImageNet, I3 | ASR₍₂₄₎: 64.7 -> 66.7 | Helped |
| add adaptive τ adjustment (ablation) | σ-zero on CIFAR-10 C10 · CIFAR-10, C10 | ASR₅₀: 71.66 -> 73.02 | Helped |
| add gradient normalization (ablation) | σ-zero on CIFAR-10 C10 · CIFAR-10, C10 | ASR₅₀: 39.76 -> 73.02 | Helped |
| add projection operator and adaptive τ adjustment (ablation) | σ-zero on CIFAR-10 C10 · CIFAR-10, C10 | ASR₅₀: 12.95 -> 73.02 | Helped |
| add adaptive τ adjustment (ablation) | σ-zero on CIFAR-10 C5 · CIFAR-10, C5 | ASR₅₀: 79.83 -> 82.92 | Helped |
| add gradient normalization (ablation) | σ-zero on CIFAR-10 C5 · CIFAR-10, C5 | ASR₅₀: 52.83 -> 82.92 | Helped |
| add projection operator and adaptive τ adjustment (ablation) | σ-zero on CIFAR-10 C5 · CIFAR-10, C5 | ASR₅₀: 23.78 -> 82.92 | Helped |
Surprising findings
- BB's ASR_∞ drops with input dimensionality because it often stops early due to initialization failures.
Limitations
- Relies on a smoothing hyperparameter and projection, though claimed robust to these choices
- Some ablation/hyperparameter settings differ across models (e.g., sigma=1 variant for C11/C12)
- Evaluated only on image classification with l_inf/l2-robust models
Experimental setup
Datasets: MNIST CIFAR-10 ImageNet
Benchmarks: MNIST CIFAR-10 ImageNet
Metrics: ASR_k median l0 norm runtime (s) queries VRAM
Baselines: SparseFool EAD PDPGD VFGA FMN BB BBadv PGD-l0 Sparse-RS Sparse-PGD
Builds on: Brendel & Bethge (BB) attack Fast Minimum Norm (FMN) attack PGD-l0 Sparse-RS
Closest papers by meaning
- Fast Minimum-norm Adversarial Attacks through Adaptive Norm Constraints (NeurIPS 2021 · similarity 0.93)
- Accurate, reliable and fast robustness evaluation (NeurIPS 2019 · similarity 0.90)
- SuperDeepFool: a new fast and accurate minimal adversarial attack (NeurIPS 2024 · similarity 0.90)
- Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations (ICML 2024 · similarity 0.89)
- Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack (ICML 2020 · similarity 0.89)
- Understanding and Improving Fast Adversarial Training against $l_0$ Bounded Perturbations (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.