Reachability of Neural Networks via Semidefinite Programming

  • Neural networks
  • Convex optimization

Neural networks are increasingly used as controllers, but a network trained to imitate a good controller comes with no guarantee: a small change in its input can produce an unexpected output. Before such a controller can be trusted in a safety-critical system, we need to know every state the closed-loop system can reach from a set of initial conditions. Computing this set exactly is intractable, but it can be over-approximated by a semidefinite program (SDP). In this project, I implemented Reach-SDP for networks of any depth and width, studied how its accuracy and cost depend on its design choices, and implemented the probabilistic counterpart that bounds the output of a network whose input is random.

Quadratic constraints for ReLU networks

The difficulty is the activation function. A ReLU neuron \(y = \max(0, x)\) is described exactly by the constraints

\[y \ge 0, \qquad y \ge x, \qquad y\,(y - x) = 0,\]

and any two neurons \(i\) and \(j\) also satisfy \((y_j - y_i)^2 \le (y_j - y_i)(x_j - x_i)\), because the ReLU is slope-restricted between \(0\) and \(1\). A weighted sum of these constraints, with nonnegative weights for the inequalities, is a single quadratic constraint that holds for every input and output of the layer:

\[\begin{bmatrix} x \\ y \\ 1 \end{bmatrix}^{\!\top} \begin{bmatrix} 0 & T & -\nu \\ T & -2T & \nu + \eta \\ -\nu^\top & \nu^\top + \eta^\top & 0 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} \ge 0, \qquad T = \sum_i \lambda_i e_i e_i^\top + \sum_{i<j} \lambda_{ij} (e_i - e_j)(e_i - e_j)^\top ,\]

with \(\nu, \eta \ge 0\) and \(\lambda_{ij} \ge 0\). The input set and the candidate output set are written as quadratic inequalities in the same way. If a weighted sum of the input and network constraints implies the output inequality (the S-procedure), the output set is guaranteed to contain every output. This condition is a linear matrix inequality in the weights, so the tightest output set of a given shape is found by an SDP.

Closed-loop reachability

For a linear system \(x_{t+1} = A x_t + B\,\pi(x_t)\) in feedback with a ReLU network \(\pi\), Reach-SDP computes an over-approximation of the reachable set one step at a time: the set at step \(t\) is the input set of the SDP for step \(t + 1\). The output set is a polytope with given facet directions \(a_i\), and each SDP finds the smallest offset \(b_i\) such that \(a_i^\top x_{t+1} \le b_i\) for every reachable state. My implementation works with any linear system and any number and size of hidden layers. It builds the network constraint from one block per layer, as in Fazlyab, Morari and Pappas (2021), so the cross terms \(\lambda_{ij}\) couple only neurons of the same layer.

The example is a double integrator with a network of two hidden layers (\(15\) and \(10\) neurons) trained to imitate a model predictive controller, starting from the square of half-width \(0.25\) around \((1, 1)\).

Box over-approximations of the reachable sets of the double integrator
Reachable sets over-approximated by boxes, for \(5\) steps, with \(144\) sampled initial states and their trajectories.
Octagon over-approximations of the reachable sets of the double integrator
The same sets over-approximated by octagons (axis-aligned and diagonal facets).

Every sampled state lies inside its bound at every step, as the theory guarantees. The first step is exact: the box has the same width as the true reachable set. After that, the box bounds stop shrinking even though the true sets do. The reason is not the SDP but the wrapping effect: the true set is a thin diagonal sliver, and wrapping it in a box at every step adds empty corners that are propagated and grow at the next step. Adding the four diagonal facets removes most of this, at about twice the cost:

StepTrue setBoxOctagon
10.986 × 0.4900.986 × 0.4910.986 × 0.491
21.093 × 0.3591.107 × 0.4591.093 × 0.372
30.732 × 0.4621.099 × 0.4930.738 × 0.462
40.347 × 0.3071.110 × 0.4940.390 × 0.311
50.121 × 0.1451.120 × 0.4980.206 × 0.164

Width × height of the true reachable set (from dense sampling) and of its over-approximations.

I also compared three structures of the network constraint: cross terms between all pairs of neurons (as in the original Reach-SDP), cross terms only within each layer (my implementation), and no cross terms. For the double integrator and for a quadrotor with two hidden layers of \(32\) neurons, all three gave exactly the same bounds, while the solver time grew with the number of multipliers:

Cross termsDouble integrator (5 steps)Quadrotor (2 steps)
All pairs of neurons1.23 s73.5 s
Within each layer0.50 s23.6 s
None0.26 s2.1 s

MOSEK solver time, with the same bounds in every case.

Probabilistic reachability

If the input of a network is random rather than bounded, a worst-case bound may be unnecessarily conservative, or impossible when the input distribution is unbounded. Fazlyab, Morari and Pappas instead propagate a confidence region: if \(x\) lies in an ellipsoid \(\mathcal{E}_p\) with probability at least \(p\) (for a Gaussian input, \(\mathcal{E}_p\) is given by the \(\chi^2\) quantile; with only the mean and covariance known, by Chebyshev’s inequality), then any set containing \(f(\mathcal{E}_p)\) contains the output \(f(x)\) with probability at least \(p\). The smallest such ellipsoid \(\{y : \lVert A y + b \rVert \le 1\}\) is found with the same quadratic constraints, by an SDP that maximizes \(\log\det A\).

I reproduced the experiment of the paper: networks with \(2\) inputs, one hidden layer of \(n_1 \in \{10, 30, 50\}\) neurons and \(2\) outputs, with random weights, and a Gaussian input with mean \((1, 1)\) and covariance \(\mathrm{diag}(1, 2)\).

Output confidence ellipsoid for a network with 10 hidden neurons
Output confidence ellipsoid for a network with 30 hidden neurons
Output confidence ellipsoid for a network with 50 hidden neurons

Gray: outputs for \(10^4\) random inputs. Blue: the image of the \(95\%\) input confidence ellipsoid. Red: the \(95\%\) output confidence ellipsoid computed by the SDP.

The estimated ellipsoids are valid: they contain \(99.70\%\), \(99.96\%\) and \(99.94\%\) of the samples, more than the required \(95\%\). They are also conservative, as in the paper, because a single ellipsoid must cover the whole image of the input ellipsoid, which is far from elliptical.

Verification by partitioning the input

The same SDP can answer a safety question: which inputs in the square \([0, 1]^2\) can drive a network (one hidden layer of \(5\) neurons) into an unsafe region of its output space? A single ellipsoid around the whole output set would be far too conservative, so I split the input square into \(40 \times 40\) cells, enclosed each cell in an ellipse, and computed a guaranteed output ellipsoid for each cell. A cell is certified safe if its output ellipsoid does not touch the unsafe set.

Input cells certified safe or possibly unsafe, and their output ellipsoids
The input square (bottom) and the output ellipsoids of its \(1600\) cells (top), with the unsafe set in gray.

Of the \(1600\) cells, \(231\) truly map into the unsafe set (checked by dense sampling of each cell). The SDP flagged all of them, plus only \(8\) false alarms, and every output it bounded stayed inside its ellipsoid. For comparison, I also tried a much cheaper heuristic that propagates the mean and covariance of each cell through the network, as a Kalman filter would, by linearizing each ReLU. It flagged \(37\) false alarms, and in \(31\) cells some outputs fell outside its ellipse, so unlike the SDP it gives no guarantee.

Takeaways

  • Quadratic constraints turn a hard question about a nonlinear network into a convex program whose answer is a guaranteed bound.
  • The SDP itself can be tight (the first step of the double integrator is exact); in a multi-step analysis, most of the conservatism comes from the shape of the sets, and better facet directions help far more than richer multipliers.
  • The cross terms between neurons did not tighten any of the bounds I computed, but made the SDPs up to \(35\) times slower.

Citation

This project is based on the following papers:

H. Hu, M. Fazlyab, M. Morari, and G. J. Pappas. “Reach-SDP: Reachability analysis of closed-loop systems with neural network controllers via semidefinite programming.” IEEE Conference on Decision and Control (CDC), pp. 5929–5934, 2020.

@inproceedings{hu2020reach,
  title={Reach-SDP: Reachability analysis of closed-loop systems with neural network controllers via semidefinite programming},
  author={Hu, Haimin and Fazlyab, Mahyar and Morari, Manfred and Pappas, George J},
  booktitle={2020 59th IEEE Conference on Decision and Control (CDC)},
  pages={5929--5934},
  year={2020},
  organization={IEEE}
}

M. Fazlyab, M. Morari, and G. J. Pappas. “Probabilistic verification and reachability analysis of neural networks via semidefinite programming.” IEEE Conference on Decision and Control (CDC), pp. 2726–2731, 2019.

@inproceedings{fazlyab2019probabilistic,
  title={Probabilistic verification and reachability analysis of neural networks via semidefinite programming},
  author={Fazlyab, Mahyar and Morari, Manfred and Pappas, George J},
  booktitle={2019 IEEE 58th Conference on Decision and Control (CDC)},
  pages={2726--2731},
  year={2019},
  organization={IEEE}
}

← All projects