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.

翻译：少像素攻击通过修改图像的少量像素误导分类器。其扰动空间为$\ell_0$球，与$p\geq1$时的$\ell_p$球不同，该空间不具备凸性。然而，现有局部鲁棒性验证器通常依赖线性边界传播进行扩展，该方法仅适用于凸扰动空间。我们证明$\ell_0$球的凸包是其边界框与非对称缩放$\ell_1$类多面体的交集。随着输入维度增加，该凸包与多面体的体积近乎相等。进而提出一种线性边界传播方法，可精确计算凸包上的边界，其紧致度显著优于边界框或$\ell_1$类多面体上的边界传播。该边界传播方法在最具挑战性的鲁棒性基准测试中，将当前最优$\ell_0$验证器的性能提升了1.24倍至7.07倍，几何平均提升达3.16倍。