Tight Robustness Certification Through the Convex Hull of ℓ0 Attacks

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