General Cutting Planes for Bound-Propagation-Based Neural Network Verification

Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, J. Zico Kolter

Abstract

Bound propagation methods, when combined with branch and bound, are among the most effective methods to formally verify properties of deep neural networks such as correctness, robustness, and safety. However, existing works cannot handle the general form of cutting plane constraints widely accepted in traditional solvers, which are crucial for strengthening verifiers with tightened convex relaxations. In this paper, we generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints, including those involving relaxed integer variables that do not appear in existing bound propagation formulations. Our generalized bound propagation method, GCP-CROWN, opens up the opportunity to apply general cutting plane methods for neural network verification while benefiting from the efficiency and GPU acceleration of bound propagation methods. Experiments demonstrate that our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark compared to the best tool in VNN-COMP 2021, and also noticeably outperforms state-of-the-art verifiers on a wide range of benchmarks. GCP-CROWN is part of the $\alpha,\!\beta$-CROWN verifier, the VNN-COMP 2022 winner.

Introduction

Formally verifying that a neural network is safe or robust (e.g., ensuring a self-driving car will not make a catastrophic error) is an NP-complete problem. Researchers typically tackle this using convex relaxations, wrapping non-linear ReLU neurons in simpler linear envelopes.

Historically, two main approaches have dominated:

  1. Bound Propagation (e.g., CROWN): Extremely fast and GPU-accelerated, but often uses "weak" relaxations that fail on hard instances where neurons have complex dependencies.
  2. Mixed-Integer Programming (MIP): Uses powerful "cutting planes" (extra linear constraints) to tighten the relaxation. This is much more powerful but relies on slow, CPU-bound solvers that do not scale well to large networks.

GCP-CROWN bridges this gap by bringing the "brain" of MIP (strong cuts) to the "brawn" of bound propagation (GPU speed).

Methodology: The GCP-CROWN Framework

The core contribution is a generalized bound propagation rule. Unlike previous methods that only handled simple "split" constraints, GCP-CROWN can propagate bounds through arbitrary linear constraints. Crucially, it can handle constraints involving the binary integer variables ($z$) that represent the state of ReLU neurons—something previous bound propagation frameworks ignored.

The GCP-CROWN architecture utilizes a parallel "Branch-and-Cut" approach, combining CPU-based MIP solvers with GPU-accelerated bound propagation.

Parallel "Branch-and-Cut" Architecture

The system runs two processes in parallel to maximize efficiency:

  • CPU side: An off-the-shelf MIP solver (e.g., CPLEX) generates high-quality cutting planes for the problem root.
  • GPU side: The GCP-CROWN verifier performs a Branch-and-Bound (BaB) search, fetching these strong cuts on-the-fly to tighten its bounds and prune the search tree.

Experimental Evaluation

The authors evaluated GCP-CROWN on several standard verification benchmarks, including oval20, oval21, and cifar10-resnet.

Running time comparison on CIFAR-10 Base, Wide, and Deep benchmarks. GCP-CROWN (green line) consistently reaches 100% solved instances faster than competing methods.

Key Results:

  • Benchmark Breakthroughs: GCP-CROWN was the first verifier to completely solve the oval20 benchmark without any timeouts.
  • Doubling Performance: On the oval21 benchmark, it verified twice as many instances as the previous best tool from VNN-COMP 2021.
  • Verified Accuracy: On SDP-FO models, GCP-CROWN significantly closed the gap between "verified accuracy" and empirical "upper bounds" (PGD attacks), outperforming all existing baselines.
  • Competition Success: This technology was a core component of the $\alpha,\beta$-CROWN verifier, which won the VNN-COMP 2022 competition.

Key Insights and Discussion

  • The Power of Global Cuts: The most effective cutting planes often involve variables across multiple layers. Traditional verifiers usually only look at adjacent layers, missing these complex correlations.
  • Integer Variables Matter: By including ReLU indicator variables ($z$) in the bound propagation, GCP-CROWN can use "Gomory cuts" and other classical optimization tricks that were previously off-limits.
  • Asynchronous Synergy: Because the MIP solver and the bound propagator run in parallel, the verifier doesn't have to wait for the "perfect" cut. It can start branching immediately and get "smarter" as the MIP solver provides better constraints over time.

Limitations and Future Work

While highly effective, the current derivation is specifically tailored for piece-wise linear ReLU networks. Extending this to other non-linearities is a key area for future research. Additionally, while the method currently uses generic MIP solvers, developing specialized cut generators for neural network structures could lead to even greater speedups. Finally, as the underlying problem is NP-complete, certain pathological networks may still remain beyond the reach of current time limits.

Summary updated

Abstract

Bound propagation methods, when combined with branch and bound, are among the most effective methods to formally verify properties of deep neural networks such as correctness, robustness, and safety. However, existing works cannot handle the general form of cutting plane constraints widely accepted in traditional solvers, which are crucial for strengthening verifiers with tightened convex relaxations. In this paper, we generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints, including those involving relaxed integer variables that do not appear in existing bound propagation formulations. Our generalized bound propagation method, GCP-CROWN, opens up the opportunity to apply general cutting plane methods for neural network verification while benefiting from the efficiency and GPU acceleration of bound propagation methods. As a case study, we investigate the use of cutting planes generated by off-the-shelf mixed integer programming (MIP) solver. We find that MIP solvers can generate high-quality cutting planes for strengthening bound-propagation-based verifiers using our new formulation. Since the branching-focused bound propagation procedure and the cutting-plane-focused MIP solver can run in parallel utilizing different types of hardware (GPUs and CPUs), their combination can quickly explore a large number of branches with strong cutting planes, leading to strong verification performance. Experiments demonstrate that our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark compared to the best tool in VNN-COMP 2021, and also noticeably outperforms state-of-the-art verifiers on a wide range of benchmarks. GCP-CROWN is part of the $\alpha,\!\beta$-CROWN verifier, the VNN-COMP 2022 winner. Code is available at http://PaperCode.cc/GCP-CROWN
BibTeX
@inproceedings{zhang2022general,
  author = {Huan Zhang and Shiqi Wang and Kaidi Xu and Linyi Li and Bo Li and Suman Jana and Cho-Jui Hsieh and J. Zico Kolter},
  title = {{General Cutting Planes for Bound-Propagation-Based Neural Network Verification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=5haAJAcofjc},
}
Figure