Neural Network Verification

Verification begins by defining a precondition on the input space (e.g., an L∞-norm ball of radius ε around a clean sample) and a postcondition on the output (e.g., the classifier must always predict the correct label). These properties are expressed in logics like Satisfiability Modulo Theories (SMT) or as linear constraints. The verifier then proves that for every input satisfying the precondition, the network's computation satisfies the postcondition. Common properties include local robustness, global fairness, and output reachability bounds.

Verification methods fall into two categories:

• Complete verifiers provide exact guarantees but are NP-complete, scaling poorly beyond a few thousand neurons. They use branch-and-bound with linear programming relaxations.
• Incomplete verifiers trade precision for scalability, computing guaranteed but conservative bounds. Techniques include interval bound propagation (IBP), abstract interpretation using zonotopes or polyhedra, and linear relaxation-based perturbation analysis (LiRPA). Incomplete methods can scale to large vision models but may return 'unknown' for challenging properties.

Bound propagation computes guaranteed upper and lower bounds on the output of each layer given bounded input perturbations. Starting with the input ε-ball, these bounds are propagated through affine transformations and activation functions. CROWN and its variants compute tight linear relaxations for ReLU, sigmoid, and tanh activations. α-CROWN optimizes these relaxations using gradient descent on the slope parameters, achieving state-of-the-art certified accuracy on benchmarks like CIFAR-10 and TinyImageNet.

Complete verification encodes the neural network as a set of mixed-integer linear programming (MILP) constraints. Each ReLU neuron introduces a binary variable representing its on/off state. The property negation is added as a constraint, and the solver searches for a counterexample. Tools like Marabou and Planet use specialized SMT solvers with theory lemmas for piecewise-linear functions. While exact, these methods face an exponential worst-case complexity in the number of unstable neurons, motivating BaB (Branch and Bound) strategies that split the input space recursively.

Standard training produces networks that are difficult to verify due to many unstable neurons. Certified training incorporates the verification loss directly into the optimization objective. Methods like IBP training minimize the worst-case loss over the abstract bounds rather than the empirical loss. COLT and SABR use tighter relaxations during training, balancing computational cost with bound tightness. Networks trained this way exhibit verifiably robust accuracy (VRA), a lower bound on true robust accuracy that can be formally guaranteed.

Randomized smoothing constructs a certifiably robust classifier from any base model by adding isotropic Gaussian noise to inputs and returning the most probable prediction under that noise distribution. The Neyman-Pearson lemma provides a tight certified radius as a function of the noise level and the margin between top class probabilities. Unlike bound propagation, smoothing is inherently scalable and applies to any architecture, including transformers. The trade-off is a reduction in standard accuracy and a certified radius that is probabilistic rather than deterministic.

The maximum allowable magnitude of a perturbation, typically defined by an Lp-norm bound (e.g., L∞ or L2), within which an adversary is constrained to operate. This epsilon-ball defines the threat model's scope. A common budget for image classifiers is an L∞-norm of 8/255, representing an imperceptible pixel change. For radio frequency signals, the budget might constrain power or spectral mask violations. Verification tools prove that no input within this budget can alter the output.

A formal characterization of an adversary's goals, knowledge, and capabilities, defining the specific security guarantees a defense must provide. Key dimensions include:

• White-box access: Adversary has full knowledge of model architecture and parameters
• Black-box access: Adversary can only query input-output pairs
• Perturbation constraints: Lp-norm bounds, patch attacks, or physical realizability
• Goal: Targeted misclassification vs. untargeted denial of service A verification method is only meaningful within a clearly defined threat model.