Neural Network Verification

A verification procedure is sound if every property it certifies as true actually holds for the network. Unlike empirical testing, which samples a finite set of inputs, sound verification exhaustively covers an infinite input space.

• Returns either "property holds" or "unknown" (never false positives)
• Critical for safety systems where missed violations are unacceptable
• Achieved through over-approximation of the network's reachable set

A verification method is complete if it can certify every true property. In practice, exact verification is NP-complete for ReLU networks, forcing a trade-off.

• Complete methods: Exact but computationally expensive (SMT, MILP)
• Incomplete methods: Fast but conservative (abstract interpretation, bound propagation)
• Modern verifiers use branch-and-bound to balance soundness with tighter bounds

Properties are expressed in formal logic to define the input domain and expected output constraints. Common specifications include:

• Local robustness: For all inputs within an L∞ ball of radius ε, the classification remains unchanged
• Monotonicity: Increasing an input feature never decreases the output
• Reachability: The output never enters an unsafe region defined by linear constraints

Verifiers construct an over-approximation of the network's behavior using abstract domains (intervals, zonotopes, polyhedra). If the abstraction is too coarse to prove the property, the verifier refines it.

• Start with coarse bounds (e.g., interval arithmetic)
• Split input regions or neurons when verification fails
• Iterate until property is proven or a counterexample is found
• Forms the basis of Counterexample-Guided Abstraction Refinement (CEGAR)

Verification complexity scales exponentially with network depth and width. Current state-of-the-art verifiers handle networks with tens of thousands of neurons, but large vision models remain out of reach.

• α,β-CROWN won VNN-COMP 2023 using bound propagation with branch-and-bound
• GPU acceleration enables parallel verification of subdomains
• Ongoing research focuses on verification-aware training to produce networks that are easier to verify

Training procedures that optimize both accuracy and verifiability produce networks with certifiably robust properties. Unlike adversarial training, which defends against empirical attacks, verification-aware training provides mathematical guarantees.

• Loss functions incorporate the maximum verifiable perturbation radius
• Produces networks where certified accuracy closely matches standard accuracy
• Techniques include IBP (Interval Bound Propagation) and CROWN-IBP combined training

A maliciously perturbed input designed to cause a model to make a mistake while appearing unmodified to human observers. Verification tools aim to prove the absence of such examples within a defined Lp-norm ball.

• White-box attacks use full gradient access to craft perturbations.
• Physical attacks manifest as stickers or patches in the real world.
• Verification provides a formal guarantee that no such perturbation exists up to a bound.

A formal guarantee that a model's prediction remains constant for all inputs within a mathematically defined perturbation bound. Unlike empirical defenses, certification provides an ironclad proof of local invariance.

• Uses methods like abstract interpretation and SMT solvers.
• Provides a lower bound on the minimum adversarial distortion.
• Complements empirical attacks like PGD which can only find upper bounds.

A multi-step iterative variant of the Fast Gradient Sign Method that projects perturbations onto an Lp-norm ball. PGD serves as the standard empirical benchmark for robustness evaluation.

• Considered the strongest first-order adversary.
• Verification tools often use PGD to find counterexamples to claimed properties.
• If verification fails, the PGD adversary provides a concrete witness to the violation.

A probabilistic defense that constructs a certifiably robust classifier by adding Gaussian noise to inputs and aggregating predictions via majority vote. It provides a scalable alternative to deterministic verification.

• Certifies robustness under the L2 norm.
• Does not require access to model internals (black-box certification).
• Trades deterministic guarantees for probabilistic ones with high confidence.

A phenomenon where a defense provides a false sense of security by obscuring the model's gradients rather than removing the underlying vulnerability. Verification bypasses this by checking the logical property directly.

• Caused by shattered gradients or stochastic gradients.
• Defenses relying on gradient masking are trivially broken by adaptive attacks.
• Formal verification is immune to gradient masking because it does not rely on gradient descent.

A formal specification of an adversary's goals, knowledge, and capabilities used to evaluate security posture. Verification requires a precise threat model to define the input domain being verified.

• L∞ threat model: Bounded pixel-wise perturbation.
• Patch threat model: Unconstrained perturbation within a contiguous region.
• The threat model defines the specification that the verifier must prove or disprove.