Safety Verification for Neural Networks Based on Set-Boundary Analysis

Zhen Liang, Dejin Ren, Wanwei Liu, Ji Wang, Wenjing Yang, Bai Xue

TL;DR

Researchers have developed a new "set-boundary" approach to verify the safety of neural networks by analyzing only the edges of input data sets rather than their entire volume. By leveraging topological properties like homeomorphism, this method significantly reduces computational overhead and produces much tighter safety guarantees, achieving speedups of over 90% in some cases.

What Problem Does This Paper Address?

As neural networks (NNs) are increasingly deployed in safety-critical systems like autonomous vehicles or airborne collision avoidance (e.g., ACAS Xu), we need rigorous mathematical proof that they won't produce dangerous outputs. This is the field of safety verification.

The standard approach involves "reachability analysis"—calculating the set of all possible outputs for a given set of inputs. However, NNs are large and non-linear, making exact calculation nearly impossible. Instead, researchers use "over-approximation," creating a "wrapper" around the possible outputs. The problem is the wrapping effect: as data moves through layers, approximation errors accumulate and the wrapper grows bloated and overly conservative. To fix this, researchers often partition the input set into tiny pieces, but this leads to an exponential explosion in computation time.

Methods

The authors propose a shift from a purely algebraic perspective to a topological one. Their core idea is based on the property of homeomorphism—a continuous, bijective mapping between spaces.

  1. Invertible NNs: For networks that are homeomorphisms (like Neural ODEs or i-ResNets), a fundamental topological rule applies: the boundary of the input set maps directly to the boundary of the output set. Therefore, if the output boundary is safe, the entire interior is guaranteed to be safe. The authors' Algorithm 1 extracts just the boundary of the input set for reachability analysis, ignoring the interior entirely.
  2. General (Non-Invertible) NNs: Most standard NNs aren't globally invertible. For these, the authors use Algorithm 2 to identify subsets of the input space where the network is locally homeomorphic. They then "abandon" these well-behaved interior subsets and only perform reachability computations on the remaining parts of the input set.
  3. Implementation: The method is designed to be "plug-and-play" with existing verification tools. They demonstrated this by integrating their boundary analysis with the CORA toolbox (for ODEs) and DeepZ (for feedforward networks).

Datasets

The paper evaluates the method using several benchmark models rather than traditional image datasets:

  • Neural ODEs: A 2D nonlinear spiral model and a complex 12-dimensional controlled cartpole system.
  • Feedforward NNs: Fully connected networks (labeled $N_3, N_4, N_5$) with 10 hidden layers and 100 neurons each, using Sigmoid and Tanh activation functions.
  • Input Sets: Defined as compact intervals/boxes (e.g., $[0, 1]^2$ or $[-1, 1]^2$).

Key Insights and Ideas

  • The Boundary is Enough: The most powerful insight is that for "well-behaved" (homeomorphic) functions, the safety of the whole set is determined entirely by its edges. This collapses the dimensionality of the verification problem.
  • Controlling the Wrapping Effect: Because the boundary represents a much smaller "volume" than the entire set, the accumulation of approximation errors (the wrapping effect) is drastically reduced. This results in much tighter, more useful safety bounds.
  • Local vs. Global: The authors show that you don't need a perfectly invertible network to benefit from topology. By carving out locally homeomorphic regions, they can still simplify the verification of standard, non-invertible networks.

Key Results

The experimental results demonstrate massive gains in both precision and efficiency:

  • Efficiency: In the 12D cartpole example, the set-boundary method was 67.1% faster than traditional whole-set analysis. For a 3D feedforward network ($N_4$), the computation time was reduced by a staggering 91.6%.
  • Precision: In several cases (shown in Figures 5 and 6), the traditional method returned "Unknown" (failed to prove safety) because its over-approximation was too bloated. The set-boundary method produced a much tighter fit, successfully proving the system was "Safe."
  • Partitioning: In one example, verifying the whole set required 10,000 partitions to reach a conclusion, while the boundary-based method required only 400.

Limitations and Future Work

  • Jacobian Dependency: To prove a region is homeomorphic, the authors currently calculate the determinant of the Jacobian matrix using interval arithmetic. This method is "coarse" and can be computationally expensive or imprecise.
  • ReLU Networks: The current Jacobian-based approach requires the network to be differentiable. This means it cannot be directly applied to networks using ReLU activation functions (which are non-differentiable at zero) without modification.
  • Open Mapping Theorem: The authors suggest that future work could use the "open mapping" property—a weaker condition than homeomorphism—which could allow this boundary analysis to be applied to an even broader class of neural networks.

Summary updated

Abstract

Neural networks (NNs) are increasingly applied in safety-critical systems such as autonomous vehicles. However, they are fragile and are often ill-behaved. Consequently, their behaviors should undergo rigorous guarantees before deployment in practice. In this paper, we propose a set-boundary reachability method to investigate the safety verification problem of NNs from a topological perspective. Given an NN with an input set and a safe set, the safety verification problem is to determine whether all outputs of the NN resulting from the input set fall within the safe set. In our method, the homeomorphism property of NNs is mainly exploited, which establishes a relationship mapping boundaries to boundaries. The exploitation of this property facilitates reachability computations via extracting subsets of the input set rather than the entire input set, thus controlling the wrapping effect in reachability analysis and facilitating the reduction of computation burdens for safety verification. The homeomorphism property exists in some widely used NNs such as invertible NNs. Notable representations are invertible residual networks (i-ResNets) and Neural ordinary differential equations (Neural ODEs). For these NNs, our set-boundary reachability method only needs to perform reachability analysis on the boundary of the input set. For NNs that do not feature this property with respect to the input set, we explore subsets of the input set for establishing the local homeomorphism property and then abandon these subsets for reachability computations. Finally, some examples demonstrate the performance of the proposed method.
BibTeX
@inproceedings{liang2023safety,
  author = {Zhen Liang and Dejin Ren and Wanwei Liu and Ji Wang and Wenjing Yang and Bai Xue},
  title = {{Safety Verification for Neural Networks Based on Set-Boundary Analysis}},
  booktitle = {TASE},
  year = {2023},
  doi = {10.1007/978-3-031-35257-7\_15},
}
Figure