Tight Robustness Certification through the Convex Hull of $\ell_0$ Attacks

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.

Key Contributions

Geometric characterization of the convex hull of an ℓ₀-ball as the intersection of its bounding box and an asymmetrically scaled ℓ₁-like polytope
Linear bound propagation that precisely computes bounds over this convex hull, provably tighter than bounding-box or ℓ₁-polytope propagations
3.16x geometric mean speedup (up to 7.07x) over the state-of-the-art ℓ₀ verifier on its hardest benchmarks

🛡️ Threat Analysis

Input Manipulation Attack

Directly addresses certified robustness against few-pixel (ℓ₀-ball) adversarial input manipulation attacks; proposes a tighter linear bound propagation over the convex hull of ℓ₀-perturbation spaces — a defense technique against adversarial examples at inference time.