通过凸包方法大幅提升小像素攻击的鲁棒性验证效率。
Tight Robustness Certification Through the Convex Hull of $\ell_0$ Attacks
- 用凸包逼近ℓ₀攻击空间，结合边界框与非对称ℓ₁多面体。
- 在高维下凸包体积接近目标多面体，验证更精确。
- 新方法使最先进ℓ₀验证器速度提升1.24x–7.07x，均值3.16x。
少量像素攻击通过修改图像中极少像素误导分类器，其扰动空间为ℓ₀球，不具备凸性，而现有局部鲁棒性验证器通常依赖线性边界传播，仅适用于凸扰动空间。本文发现ℓ₀球的凸包是其边界框与一个非对称缩放的ℓ₁型多面体的交集。随着输入维度增加，该凸包与多面体体积几乎相等。基于此，提出一种精确计算凸包上界的新线性边界传播方法，显著优于基于边界框或ℓ₁型多面体的传播。该方法将最先进的ℓ₀验证器在最具挑战性的鲁棒性基准测试中性能提升1.24倍至7.07倍，几何平均提升3.16倍。
原文摘要 · Abstract (English)
Few-pixel attacks mislead a classifier by modifying a few pixels of an image. Their perturbation space is an $\ell_0$-ball, which is not convex, unlike $\ell_p$-balls for $p\geq1$. However, existing local robustness verifiers typically scale by relying on linear bound propagation, which captures convex perturbation spaces. We show that the convex hull of an $\ell_0$-ball is the intersection of its bounding box and an asymmetrically scaled $\ell_1$-like polytope. The volumes of the convex hull and this polytope are nearly equal as the input dimension increases. We then show a linear bound propagation that precisely computes bounds over the convex hull and is significantly tighter than bound propagations over the bounding box or our $\ell_1$-like polytope. This bound propagation scales the state-of-the-art $\ell_0$ verifier on its most challenging robustness benchmarks by 1.24x-7.07x, with a geometric mean of 3.16.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。