Tight Robustness Certification through the Convex Hull of $\ell_0$ Attacks
This work addresses the challenge of efficiently verifying robustness for image classifiers against adversarial attacks with few-pixel modifications, representing an incremental improvement over prior methods.
The paper tackles the problem of certifying robustness against few-pixel attacks by developing a method that uses the convex hull of the ℓ₀-ball perturbation space, enabling tighter bounds than existing approaches. It achieves a geometric mean speedup of 3.16x on challenging benchmarks, with specific gains ranging from 1.24x to 7.07x.
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.