Tight Robustness Certification Through the Convex Hull of ℓ₀ Attacks

Abstract Few-pixel attacks mislead a classifier by modifying a few pixels of an image. Their perturbation space is an ℓ₀-ball, which is not convex, unlike ℓₚ-balls for p ≥ 1. 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 ℓ₀-ball is the intersection of its bounding box and an asymmetrically scaled ℓ₁-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 ℓ₁-like polytope. This bound propagation scales the state-of-the-art ℓ₀ verifier on its most challenging robustness benchmarks by 1.24x-7.07x, with a geometric mean of 3.16.