Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming

Mahyar Fazlyab; Manfred Morari; George J. Pappas

Source-linked AI summary

Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming

Mahyar Fazlyab, Manfred Morari, George J. Pappas

arXiv:1903.01287v3Mar 4, 2019math.OCcs.LG

TL;DR

Neural-network safety verification must bound outputs under bounded input uncertainty despite nonlinear activations and difficult exact reachable sets. The paper abstracts activation properties with quadratic constraints and analyzes the resulting network using the S-procedure and semidefinite programming. In numerical comparisons, DeepSDP produced relatively tighter bounds than SDR, especially for deeper networks, while full neuron coupling created a scalability limitation.

Problem
Exact verification requires computing a difficult nonconvex output set, while over-approximations can introduce false positives whose rate depends on approximation tightness.
Method
The framework abstracts activation functions through quadratic constraints and uses the S-procedure to formulate verification as an SDP feasibility problem.
Results
DeepSDP produced relatively tighter bounds than SDR, especially for deeper networks, while LP relaxation bounds were considerably looser and had negligible running time.
Takeaways & Limitations
The framework supports safety verification and robustness analysis for general activation functions and can be adapted to reachable-set estimation and other analysis problems.
Takeaways & Limitations
Coupling all neurons can considerably reduce conservatism but is infeasible for even medium-sized networks because decision variables scale quadratically with neuron count.

Abstract

from arXiv · show

Certifying the safety or robustness of neural networks against input uncertainties and adversarial attacks is an emerging challenge in the area of safe machine learning and control. To provide such a guarantee, one must be able to bound the output of neural networks when their input changes within a bounded set. In this paper, we propose a semidefinite programming (SDP) framework to address this problem for feed-forward neural networks with general activation functions and input uncertainty sets. Our main idea is to abstract various properties of activation functions (e.g., monotonicity, bounded slope, bounded values, and repetition across layers) with the formalism of quadratic constraints. We then analyze the safety properties of the abstracted network via the S-procedure and semidefinite programming. Our framework spans the trade-off between conservatism and computational efficiency and applies to problems beyond safety verification. We evaluate the performance of our approach via numerical problem instances of various sizes.

I. INTRODUCTION

The paper motivates formal neural-network robustness guarantees and introduces an SDP framework that abstracts activations with quadratic constraints. It targets safety verification under bounded input uncertainty while balancing tightness, computational cost, and applicability.

Motivation: Neural networks are difficult to analyze formally and can be highly vulnerable to small adversarial or uncertain input perturbations.
Motivation: Existing attack-specific hardening methods are scalable but can produce false negatives, whereas safety-critical applications require guarantees for all bounded input variations.
Contributions: The proposed framework abstracts activation functions with quadratic constraints and converts verification into an SDP using the S-procedure.
Contributions: The framework captures bounded slope, bounded values, monotonicity, and repeated activations across layers, including cross-layer neuron coupling that can reduce conservatism.
Contributions: Users can include or exclude QC types to control the trade-off between computational complexity and conservatism.
Scope: The input-output QC characterization can also support sensitivity analysis, reachable-set estimation, probabilistic verification, Lipschitz bounds, and closed-loop stability analysis.

III. PROBLEM ABSTRACTION VIA QUADRATIC CONSTRAINTS

The paper represents input sets and nonlinearities with quadratic constraints, producing convex over-approximations suitable for SDP-based verification. This abstraction covers common uncertainty sets and safety specifications, including hyper-rectangles, polytopes, zonotopes, and ellipsoids.

Abstraction framework: Quadratic constraints provide an abstraction of sets and nonlinearities that can be converted into a semidefinite program.
Set abstraction: The set of matrices defining valid QCs for an input set is a convex cone, enabling convex combinations of valid quadratic constraints.
Set abstraction: Input sets can be over-approximated by intersections of quadratic inequalities, with the matrix defining the approximation appearing as an SDP decision variable.
Input sets: Hyper-rectangles satisfy QCs parameterized by diagonal nonnegative matrices, and the paper specializes this result to ℓ∞-norm perturbation sets.
Input and safety specifications: The framework also provides QC representations for polytopes, zonotopes, and ellipsoids, while safety sets may be represented or inner-approximated by finitely many quadratic inequalities.

C. Abstraction of Nonlinearities by Quadratic Constraints

The paper replaces nonlinear activation functions with quadratic constraints on pre- and post-activation values, capturing properties such as sector bounds, slope restrictions, monotonicity, and bounded values. These constraints provide a quadratically constrained over-approximation of activation graphs.

Core abstraction: Quadratic constraints abstract activation functions through relations between their pre- and post-activation values.The abstraction removes nonlinearities while retaining constraints they impose on signals.
QC definition: A QC includes a constant term, allowing affine constraints such as bounded nonlinearities to be represented.The paper interprets the QC as a constraint satisfied by the graph of the activation function.
QC definition: The activation graph is over-approximated by a set defined through quadratic inequalities.
Activation properties: Sector bounds constrain a nonlinearity between two lines, whereas slope restrictions bound the slopes of chords between pairs of points.The sector condition alone does not restrict the function's slope.
Activation properties: Common activation functions, including ReLU, sigmoid, tanh, leaky ReLU, and ELU, satisfy slope-restriction or sector-bounded conditions.
Repeated activations: Component-wise repeated activations inherit the scalar slope-restriction property, enabling vector-valued quadratic constraints.

3) Repeated Nonlinearities:

For repeated component-wise nonlinearities, the framework exploits the fact that the same scalar activation is applied across neurons. Coupling constraints between neurons can therefore refine the relaxation and reduce conservatism, while bounded-value constraints add further structure.

Repeated Nonlinearities: The repeated-nonlinearity construction is obtained by summing scalar slope-restriction conditions and then refining them with cross-neuron coupling.
Repeated Nonlinearities: Component-wise repetition allows quadratic constraints to capture relationships among distinct neurons rather than treating them independently.The repeated nonlinearity is represented as a vector of identical scalar activations.
Repeated Nonlinearities: Coupling all neurons through repeated-nonlinearity constraints can considerably reduce conservatism, especially in deep networks.The paper interprets layers as time indices in a dynamical-system analogy, with the same nonlinearity repeated across them.
Bounded Nonlinearities: Known lower and upper bounds on activation values yield additional quadratic constraints, and any QC valid for an over-approximating graph remains valid for the activation.
SDP integration: The resulting quadratic inequalities are encoded as QCs, with the abstraction matrix selected as a decision variable in the SDP.
Bounded Nonlinearities: Less conservative activation descriptions generally require case-by-case treatment to exploit nonlinearities' specific structure.

D. Quadratic Constraints for ReLU Activation Function

The ReLU analysis combines sector-boundary, inequality, and repeated-neuron constraints into global and locally tightened quadratic descriptions. Local pre-activation bounds identify fixed active or inactive neurons and provide additional multiplier freedom.

Global ReLU constraints: ReLU lies on the boundary of sector [0, 1], enabling an exact boundary constraint for each activation.For ReLU, α = 0 and β = 1.
Global ReLU constraints: The ReLU description combines a sector-boundary equality with inequalities that prune the sector boundaries to recover the ReLU function.
Global ReLU constraints: Cross-neuron constraints can be added for distinct indices, incorporating coupling among repeated ReLU activations.
Local ReLU constraints: Local classification assigns sectors [β, β], [α, β], and [α, α] to active, unknown, and inactive neurons, respectively.
Local ReLU constraints: Allowing unrestricted multipliers for neuron pairs with the same fixed status can tighten the local relaxation.
Local ReLU constraints: Local pre-activation bounds classify neurons as always active, always inactive, or uncertain over the input region.

E. Other Activation Functions

For activation functions beyond ReLU, the paper tightens graph over-approximations using multiple sector bounds or local input intervals. It then uses the S-procedure to formulate safety verification as an LMI feasibility problem solvable by convex optimization methods.

Other Activation Functions: Multiple sector bounds at different points can substantially improve over-approximations for nonlinearities such as tanh.Figure 3 contrasts a global intersection of sectors with a local polytope over an input interval.
Other Activation Functions: Element-wise input bounds provide tighter sector conditions for tanh on a restricted interval.
Other Activation Functions: Any quadratic constraint valid for a local graph over-approximation is also valid for the corresponding activation function.
SDP verification: The S-procedure converts quadratic constraints for inputs and activations into an LMI feasibility problem for checking set inclusion.The target inclusions are f(X) ⊆ S_y or X ⊆ S_x.
SDP verification: If the matrix inequality is feasible for valid input and activation-function constraints, the network's safety inclusion is certified.
SDP verification: Convexity of the constraint sets makes the LMI feasibility problem efficiently solvable with interior-point methods.

B. Multi-layer Neural Networks

The paper extends its QC-based SDP verification framework to multilayer networks by concatenating layer signals and exploiting repeated activation functions. The resulting LMI provides a multilayer safety-certification condition.

B. Multi-layer Neural Networks: Multilayer networks are represented by concatenating all pre- and post-activation signals into a compact vector representation.Entry selector matrices recover each layer's signal from the concatenated vector.
B. Multi-layer Neural Networks: The multilayer counterpart of the single-layer verification theorem is formulated as an LMI for networks with repeated activation functions.The theorem assumes QC descriptions for both the input set and activation function over the relevant domain.
B. Multi-layer Neural Networks: Feasibility of the multilayer LMI certifies that the input set lies in the safe preimage, equivalently that the network output lies in the specified safe set.Multiple safe-set inequalities are handled by imposing one LMI for each quadratic inequality.

V. OPTIMIZATION OVER THE ABSTRACTED NETWORK

DeepSDP turns the QC-based verification condition into an optimization framework for bounding reachable outputs and closed-loop reachable sets. It supports polyhedral and ellipsoidal over-approximations and neural-network-controlled systems.

V. OPTIMIZATION OVER THE ABSTRACTED NETWORK: DeepSDP incorporates the safety-verification LMI as a constraint in a convex optimization problem over QC and specification parameters.The objective is a convex function of the decision variables, and the framework is named DeepSDP.
A. Reachable Set Estimation: For a linear output bound c^T f(x) ≤ d, feasibility certifies d as an upper bound for every input in X.Optimizing d yields the tightest bound available within the chosen abstraction and parameterization.
A. Reachable Set Estimation: Optimizing separate output inequalities produces a polyhedral over-approximation of the reachable set f(X).The method minimizes each di for given facet normals ci while preserving f(X) ⊆ Sy.
A. Reachable Set Estimation: A reparameterized SDP can compute minimum-volume ellipsoidal over-approximations, with Schur complements restoring convexity.The direct formulation is nonconvex in the ellipsoid parameters because S depends nonaffinely on them.
B. Closed-Loop Reachability Analysis: The same LMI approach over-approximates one-step and closed-loop reachable sets for discrete-time LTI systems driven by neural-network controllers.The paper applies this approach to verify a model predictive controller approximated by a neural network.
VI. Numerical Experiments: Numerical experiments use MOSEK with CVX and ReLU networks, with interval bound propagation as a presolve step.Experiments were run on a 5-core computer with 8GB of RAM.

A. Computational Complexity

The computational study examines how QC choices affect decision-variable counts, tightness, and runtime. Experiments report tighter DeepSDP bounds for deeper networks and benefits from repeated nonlinearities.

1) Input Set:: For hyperrectangular input sets, nx quadratic constraints precisely characterize the set, while adding the remaining constraints did not tighten the relaxation numerically.The additional constraints number 2n^2−nx and encode pairwise coordinate relationships.
1) Input Set:: For polyhedral input sets, heuristics can remove sector constraints that are not tight by checking whether relevant hyperplane intersections lie inside the polytope.Figure 5 contrasts non-tight and tight sector bounds.
1) Input Set:: Ellipsoidal input sets require only one decision variable, the parameter µ.
2) Activation Functions:: Using all quadratic constraints yields O(n+n^2) decision variables, whereas ignoring repeated nonlinearities yields O(n).The experiments found no additional conservatism from removing repeated nonlinearities within a layer, while repetition across layers was sometimes effective for multilayer networks.
1) Number of Hidden Layers:: DeepSDP produced relatively tighter output-set bounds than the compared semidefinite relaxation, especially for deeper randomly generated networks.Figure 4 compares exact output sets with DeepSDP and the semidefinite relaxation of for networks with 1–4 hidden layers and 100 neurons per layer.
2) Activation Functions:: Including repeated nonlinearities made DeepSDP bounds tighter, especially for deep networks.The comparison uses a six-facet polytope for randomly generated networks with ten neurons per layer.
3) Comparison with Other Methods:: Across comparisons, MILP found the global solution but became rapidly slower with network size, DeepSDP was tighter than SDR for deeper networks, and LP was looser but negligible in runtime.The comparison used 100 random networks per layer size with 10 inputs, 1 output, and 1–5 hidden layers.

C. Verification of Approximate Model Predictive Control

The section verifies an approximate MPC controller by embedding output projection into a neural network and computing positively invariant sets with SDP-based reachable-set over-approximations.

Controller setup: The neural network approximates an MPC law, but may violate the original state and control constraints.The controller is trained offline to reduce online optimization burden, motivating formal constraint verification.
Controller setup: For box-constrained inputs, output projection onto U can be embedded as two additional ReLU layers.The resulting projected controller is represented as an augmented feed-forward network.
Invariant-set verification: A set E is positively invariant when every state starting in E remains in E, equivalently when fcl(E) ⊆ E.This property is used to validate state-constraint satisfaction for the closed-loop system.
Invariant-set verification: SDP over-approximates the one-step reachable set fcl(E) with a polytope P, and feasibility implies fcl(E) ⊆ P.The candidate set is E = {x | ∥x∥∞≤ϵ}; positive invariance follows when P ⊆ E.
Numerical experiment: The learned controller uses two inputs, one output, and hidden layers of 32 and 16 neurons, trained on 6284 uniformly chosen points from the control invariant set.Figure 9 compares the explicit MPC control law with its neural-network approximation.

APPENDIX

The appendix derives quadratic and matrix inequalities used to represent input-set constraints and activation-function properties, including slope restrictions for piecewise-linear activations.

Quadratic constraints: Box constraints x ≤ x ≤ x̄ are converted into n_x quadratic inequalities, then combined with nonnegative diagonal multipliers.This construction yields a quadratic constraint representation of the input set.
Slope restrictions: The appendix combines pairwise slope restrictions across coordinates using matrices E_ij = (e_i−e_j)(e_i−e_j)^⊤.Summing these pairwise constraints produces the desired aggregate inequality.
Piecewise-linear activation: For y = max(αx, βx), the coordinatewise relation is encoded by (y_i−αx_i)(y_i−βx_i) = 0 together with y_i ≥ βx_i and y_i ≥ αx_i.Weighted combinations of these equalities and inequalities produce a quadratic constraint for the piecewise-linear activation.
Piecewise-linear activation: The max activation is also treated as slope-restricted on [α, β], and the resulting coordinatewise constraints are summed to obtain the stated matrix inequality.The derivation combines the explicit max representation with the slope-restriction property.

E. Proof of Lemma 4

The proof establishes an SDP certificate by combining quadratic constraints for the input set and activation functions with the network’s affine relations.

Proof of Lemma 4: For x_1 = φ(W^0x_0 + b^0), the activation quadratic constraint applies to the pre- and post-activation pair.The proof uses this constraint together with an input-set quadratic constraint.
Proof of Lemma 4: If the combined matrix inequality holds for suitable input-set and activation multipliers, multiplying by the augmented network vector yields a valid quadratic bound.The proof applies left- and right-multiplication to derive the scalar inequality over all admissible inputs.
Proof of Lemma 4: Substituting x_0 = x and f(x) = W^1x_1 + b^1 converts the resulting inequality into the lemma’s desired input-output bound.The same argument is expressed for the network representation using x_0 = E_0x and f(x) = W^ℓE^ℓx + b^ℓ.
Numerical context: Figures 10 and 11 examine how hidden-neuron count and input perturbation size affect SDP over-approximation quality for ReLU networks.The plotted cases vary hidden-neuron counts, ℓ∞ perturbation radii, and network architecture while excluding repeated-nonlinearity constraints.