CLAD: Constrained Abstract Domain for Neural Network Verification

Neural network verification (NNV) formally verifies that a network satisfies a specified property for all inputs within a defined region. Modern NNV tools employ abstract domains to compute a sound over-approximation of the network's behavior from the given input region, thus the tightness of these abstractions essentially determines efficiency. A long line of increasingly precise domains has been developed, but they all describe the valid input region in the same restrictive way, e.g., an ${\ell }_p$-norm ball. A practical input region is rarely a simple ${\ell }_p$ ball, but rather a combination ${\ell }_p$ ball with additional constraints. Verifying a network over such a region with existing abstraction produces a loose over-approximation, which results in either failing to verify a property or spurious counterexamples. We introduce Constrained Lagrangian Abstract Domain (CLAD), a new abstract domain that computes a sound over-approximation of neural networks over input regions defined by a combination of convex constraints. CLAD propagates these constraints and tightens bounds over the true feasible region. However, bounding a neuron over the intersection of these constraints has no closed-form solution, so CLAD relaxes each constraint into the objective with a Lagrange multiplier and solves the resulting max-min problem with a projected primal-dual method, alternating a projected gradient step on the input with a multiplier update. CLAD thus supports any differentiable convex constraint through automatic differentiation. We evaluate CLAD on 1944 instances across four convolutional networks with motion-blur structured perturbations with halfspace or ${\ell }_2$-ball constraints. On standard unconstrained ${\ell }_{\infty }$ property, CLAD verifies as many instances as GCPCROWN at a similar runtime. On constrained properties, CLAD verifies 60% more instances than GCPCROWN on ${\ell }_2$-ball properties, and 22% more in total.