Verification of Non-Linear Specifications for Neural Networks

Chongli Qin, Krishnamurthy (Dj) Dvijotham, Brendan O'Donoghue, Rudy Bunel, Robert Stanforth, Sven Gowal, Jonathan Uesato, Grzegorz Swirszcz, Pushmeet Kohli

Introduction

Neural networks are often criticized as "black boxes" because it is difficult to guarantee how they will behave on all possible inputs. To address this, researchers use formal verification to provide mathematical proofs that a network follows a specific "specification" or rule.

Until recently, most verification work focused on linear specifications, such as adversarial robustness (e.g., "does a tiny change in pixels change the output label?"). However, real-world safety often requires non-linear constraints, such as ensuring a robot's motion conserves energy or that a classifier's mistakes remain semantically logical. This paper introduces a framework to formally prove that neural networks satisfy these complex, non-linear requirements.

Methods: Convex-Relaxable Specifications

The core innovation is the introduction of convex-relaxable specifications. The researchers transform difficult non-linear verification problems into solvable convex optimization tasks by finding a "convex relaxation"—a simplified mathematical shape that is guaranteed to contain all possible behaviors of the original non-linear rule.

Key technical contributions include:

  • Softmax Relaxations: Methods to bound the non-linear softmax function using linear interpolations and tangential constraints, enabling the verification of properties involving probabilities.
  • Quadratic Relaxations: For physical properties like energy, the authors use McCormick envelopes and Semidefinite Programming (SDP) to "box in" quadratic terms.
  • Unified Framework: The approach allows verification to be performed by solving a single convex optimization problem that scales with the size of the network.

Experimental Setup

The method was evaluated across three distinct domains to demonstrate its versatility:

  1. CIFAR-10 (Semantic Consistency): Using WordNet to define logical distances between labels, ensuring the model doesn't make erratic jumps between unrelated categories (e.g., vehicle to animal) under perturbation.
  2. MNIST (Downstream Tasks): Verifying a network that predicts the sum of two handwritten digits to bound the total expected error.
  3. Mujoco Physics Engine (Pendulum): Training a model to predict a damped pendulum's next state while verifying it never violates the law of conservation of energy.

Key Results and Insights

The researchers found that verification is not just a pass/fail test but a powerful diagnostic tool. For example, in the pendulum experiment, a model verified to follow energy conservation maintained much better long-term prediction stability compared to an unverified model, which eventually oscillated wildly due to compounded physical violations.

Verification performance across semantic (CIFAR-10), downstream (Digit Sum), and physics (Pendulum) specifications.
  • Tightness of Bounds: For semantic consistency on CIFAR-10, the gap between the "provable" bound and the "best possible attack" was less than 0.9%, showing the relaxation is highly accurate.
  • Physics Consistency: On the pendulum task, the method proved energy consistency for approximately 70% of test points at moderate perturbation levels.
  • Scalability: Linear relaxations scaled effectively to networks with hundreds of thousands of parameters.

Limitations and Future Work

While promising, the approach has limitations. Quadratic relaxations using SDP scale quadratically with the number of inputs and outputs, making them difficult to apply to high-resolution images. Additionally, the method is "incomplete"; a failure to find a proof might simply mean the convex relaxation wasn't tight enough, rather than the model being broken. Future research will explore signomial relaxations to better handle products of probabilities in complex multi-step reasoning tasks.

Summary updated

BibTeX
@inproceedings{qin2019verification,
  author = {Chongli Qin and Krishnamurthy (Dj) Dvijotham and Brendan O'Donoghue and Rudy Bunel and Robert Stanforth and Sven Gowal and Jonathan Uesato and Grzegorz Swirszcz and Pushmeet Kohli},
  title = {{Verification of Non-Linear Specifications for Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=uIvHnxOUZ0},
}
Figure