Tight Robustness Certification Through the Convex Hull of _0 Attacks

Abstract

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 p1. 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.

Reproductions