Formal Verification of Neural Certificates Done Dynamically

Thomas A. Henzinger, Konstantin Kueffner, Emily Yu · 2025

Read Formal Verification of Neural Certificates Done Dynamically by Thomas A. Henzinger, Konstantin Kueffner, Emily Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-11987.txt.

Introduction

Thomas Henzinger, Konstantin Kueffner, and Emily Yu move the checking of neural safety certificates from the lab to live runtime. Learning-based controllers for physical systems often carry a learned proof, such as a barrier function, that the system stays safe. Verifying that proof over the whole state space rarely scales.

Their monitor watches the running system and re-verifies the certificate on the fly, a short lookahead window at a time. It needs no access to the controller itself. A case study with ReLU-based barrier functions shows the checks keep pace with the system. The payoff is fast warning when a certificate is wrong or safety is about to break, at small cost.

Catalog record

CREATORThomas A. Henzinger, Konstantin Kueffner, Emily Yu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-11987

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Formal Verification of Neural Certificates Done Dynamically Thomas A. Henzinger, Konstantin Kueffner, Emily Yu Abstract Neural certificates have emerged as a powerful tool in cyber-physical systems control, providing witnesses of correctness. These certificates, such as barrier functions, often learned alongside control policies, once verified, serve as mathematical proofs of system safety. However, traditional formal verification of their defining conditions typically faces scalability challenges due to exhaustive state-space exploration. To address this challenge, we propose a lightweight runtime monitoring framework that integrates real-time verification and does not require access to the underlying control policy. Our monitor observes the system during deployment and performs on-the-fly verification of the certificate over a lookahead region to ensure safety within a finite prediction horizon. We instantiate this framework for ReLU-based control barrier functions and demonstrate its practical effectiveness in a case study. Our approach enables timely detection of safety violations and incorrect certificates with minimal overhead, providing an effective but lightweight alternative to the static verification of the certificates. 1 Introduction Forthcoming intelligent systems are increasingly integrated into industries and numerous application domains, including autonomous driving and medical image processing [ 2 , 4 ] . For example, deep reinforcement learning enables the automated synthesis of neural network controllers to address complex control tasks [ 16 ] . However, in these safety-critical domains, ensuring the safety and correctness of machine-learned components presents significant challenges. Neural networks often lack transparency and explainability, undermining their trustworthiness. Without formal safety guarantees, the reliability and operation of cyber-physical systems remain constrained, thereby affecting their deployment in practice. Certificate functions serve as mathematical proofs to establish the correctness of controllers. A certificate function [ 9 ] is a mathematical mapping from system states to real values, where the satisfaction of its defining conditions guarantees that a desired system property holds. Notable examples include Lyapunov functions [ 28 ] , used to prove stability with respect to a fixed point, and barrier functions [ 22 ] , which are employed to certify safety by characterizing forward-invariant sets. While the theory of Lyapunov functions has been extensively studied over the past several decades, recent advances leverage reinforcement learning to synthesize such certificates in the form of neural networks. A growing body of work in learning-based control explores the joint synthesis of both the certificate function and the control policy. We refer to [ 9 ] for a more comprehensive overview of learning-based control using certificates. Since certificate functions are often represented as neural networks, formal verification is typically employed to ensure their correctness. This gave rise to the learner-verifier framework [ 6 , 7 , 20 ] , which is a synthesis framework to obtain valid neural certificates. This framework follows the style of Counterexample-Guided Inductive Synthesis (CEGIS). It consists of two main components: the learner , which synthesizes both the control policy and the certificate function, and the verifier , which checks whether the certificate satisfies its formal defining conditions. If the verifier identifies a counterexample, it is incorporated into the training set to refine the neural networks. This iterative loop continues until the certificate is successfully verified or a predefined termination criterion, such as a timeout, is met. While formal verification offers correctness guarantees, it often suffers from scalability limitations due to its computational complexity, restricting its use in more complex control tasks. To overcome this challenge, runtime monitoring has emerged as a promising complementary approach. A runtime monitor is a lightweight software module that operates in parallel to the controlled system, issuing warnings upon detecting violations of specified properties or certificate defining conditions. The Simplex architecture [ 8 , 27 ] , for instance, employs a verified backup controller to override unsafe actions. Recent work has proposed a learner-monitor framework [ 32 ] , analogous to the learner-verifier paradigm, in which the monitor continuously collects counterexamples during execution and incorporates them into the training data to refine the learned models. Figure 1: Overview of our monitoring framework. At runtime, the monitor observes system states and computes an overapproximation of the reachable region using a local abstraction function. We do not assume access to the controller. A verifier checks whether the certificate remains valid in the lookahead region. If a violation is detected, a warning is issued and a fail-safe mechanism can be triggered. In this paper, we propose a general runtime monitoring framework that integrates partial static verification over a lookahead horizon to ensure the safety of the controlled systems, as illustrated in Fig. 1 . The framework is agnostic to the underlying controller and does not require access to future control inputs. At each time step, a monitor observes the system trajectory and uses a local abstraction function to over-approximate reachable states within the lookahead horizon. A certificate verifier then checks whether the safety certificate remains valid over this predicted region. If a violation is detected, the monitor issues a warning and can trigger a fail-safe response. Because our monitor detects violations ahead of time, the fail-safe mechanism is activated before leaving the certified region. We instantiate this general framework using a specific verifier for ReLU-based control barrier functions (CBFs), leveraging the piecewise linear structure of ReLU networks for efficient localized verification. Our case study on a satellite rendezvous task demonstrate that the monitor can detect certificate violations as well as ensuring runtime safety with minimal overhead. Overall, our contributions are as follows. 1. We introduce a general framework for online verification of certificates, which leverages a local abstraction function and a verifier as a sub-routine to enable local verification over a finite lookahead horizon. 2. We instantiate the framework for ReLU-based control barrier functions, and present a novel online verification algorithm that operates over neuron activation patterns. The algorithm adaptively constructs and verifies regions of the state space encountered at runtime, enabling fast detection of violations of safety as well as certificate defining conditions. To the best of our knowledge, this is the first runtime monitoring approach that performs formal, on-the-fly certificate verification for neural-based control. 2 Preliminaries We denote the set of natural number as \mathbb{N} and the set of real numbers as \mathbb{R} . Their positive counterparts are denoted as \mathbb{N}_{+} and \mathbb{R_{+}} respectively. Given a state space \mathcal{X}\subseteq\mathbb{R}^{m} and an action space \mathcal{U}\subseteq\mathbb{R}^{n} , we consider continuous-time, control-affine dynamical systems of the form \dot{x}=f(x)+g(x)u, where x\in\mathcal{X},u\in\mathcal{U},f:\mathbb{R}^{m}\to\mathbb{R}^{m} and g:\mathbb{R}^{m}\to\mathbb{R}^{m\times n} . A control policy \pi:\mathcal{X}\to\mathcal{U} defines a closed-loop system \mathcal{F}:\mathcal{X}\to\mathcal{X} with dynamics \displaystyle\quad\mathcal{F}(x)=f(x)+g(x)\pi(x). (1) The safe control problem requires that, under a given control policy, the system must never enter an unsafe state along any execution trace originating from an initial state. To prove that the process \mathcal{F} satisfies properties such as safety or reachability, we rely on certificates. A certificate is a function B\colon\mathcal{X}\to\mathbb{R} assigning a numerical value to each state. To be a valid certificate, this function B must satisfy some property dependent conditions over the state space. To prove safety, a barrier function is needed. Definition 1 (Control Barrier Function) Let \mathcal{X}_{0}\subseteq\mathcal{X} be the set of initial states, and let \mathcal{X}_{u}\subseteq\mathcal{X} be the unsafe states. A continuously differentiable function B:\mathcal{X}\to\mathbb{R} is called a control barrier function if the following conditions hold: 1. B(x)\geq 0 for all x\in\mathcal{X}_{0} ; 2. B(x)<0 for all

Read the complete text