Tight Robustness Certification Through the Convex Hull of ℓ₀ Attacks

A few pixel attack misleads a classifier by modifying a few pixels of an image. Its perturbation space is an $\ell0$-ball, which is not convex, unlike $\ellp$-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 $\ell0$-ball is the intersection of its bounding box and an asymmetrically scaled $\ell1$-like polytope. For single channel inputs, 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 $\ell1$-like polytope. This bound propagation scales the state-of-the-art $\ell0$ verifier on robustness benchmarks by 1.24x-7.07x, with geometric mean of 3.16.