Data-Driven Safety Verification of Unknown Dynamical Systems

25 concepts20 papers1 proposal

Traditional control theory and formal verification rely on a elegant assumption: we possess a precise mathematical model of the system. If we know the differential equations $\dot{x} = f(x, u)$ governing a robot, or the exact transition probabilities of a Markov Decision Process, we can compute exactly where the system might travel (reachability analysis) or prove it will never enter an unsafe state (safety verification).

However, modern autonomous systems—such as self-driving cars governed by deep neural networks or complex cyber-physical systems—operate as black boxes. Their internal dynamics are either too complex to model symbolically or completely unknown.

To verify these systems, a new paradigm has emerged: data-driven safety verification. Instead of propagating equations forward in time, this approach uses observed trajectory data to construct rigorous, mathematically sound safety guarantees. But how do we extract absolute safety bounds from a finite, noisy set of observations?


The Fundamental Challenge: Bridging Data and Guarantees

If we simply simulate a black-box system from 1,000 random starting points, we gain some intuition about its behavior. But this is not verification. A rare disturbance or an unobserved corner case could still drive the system into a catastrophic failure state. As noted by Johannes Köhler et al. in State space models vs. multi-step predictors in predictive control: Are state space models complicating safe data-driven designs?, accounting for model uncertainty directly from data typically requires dense, mathematically rigorous reachability analysis to ensure the system remains within safe boundaries.

To turn finite observations into formal guarantees, researchers exploit structural assumptions about the system (such as bounded noise or continuity) and apply mathematical machinery to "bound" the unknown space between data points.


Geometric Bounding: Reachability Without Models

One way to guarantee safety is to compute an over-approximation of the reachable set—a geometric envelope that is guaranteed to contain all possible future states of the system.

How can we build this envelope without a model? Consider a linear system with unknown matrices $A$ and $B$, subject to bounded noise: $x_{k+1} = Ax_k + Bu_k + w_k$. While we do not know $A$ or $B$, we do possess a history of states and inputs.

[Collected Trajectory Data] ---> [Matrix Zonotope Optimization] ---> [Guaranteed Safe Envelope]

In Data-Driven Reachability Analysis Using Matrix Zonotopes, Amr Alanwar et al. demonstrate that by representing the unknown dynamics as a set of possible matrices consistent with the data, one can use matrix zonotopes (polytopes with central symmetry) to bound the system's future states. Because the noise is bounded, the true system is guaranteed to live inside this solution set.

For non-convex or nonlinear behaviors where simple envelopes fail, Z. Zhang et al. in Data-Driven Nonconvex Reachability Analysis Using Exact Multiplication introduced constrained polynomial zonotopes. This method tracks complex, twisting state spaces exactly from data without the loose over-approximations that make traditional methods overly conservative. Similarly, Alex Devonport et al. utilize polynomial expressions called Christoffel functions in Data-Driven Reachability Analysis with Christoffel Functions to estimate reachable sets from black-box simulations, providing a direct mathematical link between the number of samples taken and the confidence of the safety guarantee.


Data-Driven Certificates: Learning the Boundaries of Safety

Instead of tracking every possible path a system can take, we can search for a safety certificate—a mathematical function that acts as a barrier between safe and unsafe regions.

A classic example is a Barrier Certificate $B(x)$. If we can find a function where $B(x) \le 0$ in the safe initial states, and the derivative along the system's trajectories is always negative ($\dot{B}(x) \le 0$), the system can never cross into the unsafe region where $B(x) > 0$. But if the dynamics are a black box, we cannot analytically compute $\dot{B}(x)$.

  Unsafe Region [ B(x) > 0 ]
---------------------------------  <--- Barrier Certificate Boundary B(x) = 0
  Safe Region   [ B(x) <= 0 ]      (Evaluated via finite differences / data samples)

To solve this, Zhizhen Qin et al. show in Quantifying Safety of Learning-based Self-Driving Control Using Almost-Barrier Functions that these derivatives can be estimated using finite differences directly from sampled trajectory data. This allows control-theoretic safety analysis to be applied directly to deep-learning controllers.

When the system is stochastic, we must frame these guarantees probabilistically. In Data-Driven Safety Verification of Stochastic Systems via Barrier Certificates, Ali Salamati et al. combine barrier certificates with scenario-based optimization. By treating each observed trajectory as a "scenario," they solve an optimization problem that synthesizes a barrier certificate with a mathematically proven confidence level.

This idea of learning certificates directly from data has been extended to synthesize stability boundaries (Joris Kenanian et al. in Data driven stability analysis of black-box switched linear systems; Luke Rickard et al. in Data-driven certificate synthesis) and to shield reinforcement learning agents in real-time using neural Lyapunov shields (Zikang Xiong et al. in HiSaRL: A Hierarchical Framework for Safe Reinforcement Learning) or Control Lyapunov Barrier Functions (Desong Du et al. in Reinforcement Learning for Safe Robot Control using Control Lyapunov Barrier Functions).


The Kernel Trick: Embedding Dynamics in Hilbert Spaces

For highly nonlinear or stochastic systems, tracking geometric sets or fitting simple barrier functions becomes computationally intractable. How do we propagate probability distributions through a black box without computing impossible integrals?

The answer lies in Kernel Distribution Embeddings. Instead of trying to approximate a complex probability density function explicitly, we map the distribution into a high-dimensional Reproducing Kernel Hilbert Space (RKHS). In this space, a probability distribution is represented as a single point (an embedding).

Stochastic Trajectories ---> Map via Kernel Function ---> Single Point in RKHS 
                                                          (Linear algebraic operations 
                                                           replace complex integrals)

As pioneered by Adam Thorpe et al. in Model-Free Stochastic Reachability Using Kernel Distribution Embeddings, this embedding bypasses the need for an explicit system model. Because expectations of functions manifest as simple inner products in the RKHS, we can evaluate stochastic reachability using basic linear algebra on the data.

The authors expanded this framework in Learning Approximate Forward Reachable Sets Using Separating Kernels and State-based confidence bounds for data-driven stochastic reachability using Hilbert space embeddings, demonstrating that we can derive state- and input-dependent confidence bounds. If we have a lot of data in one region of the state space, our safety bounds shrink and become more precise; in unobserved regions, the bounds naturally expand to reflect our uncertainty.

This kernelization is highly versatile: Luca Bortolussi et al. demonstrate in Learning Model Checking and the Kernel Trick for Signal Temporal Logic on Stochastic Processes that even complex logical formulas (like Signal Temporal Logic) can be treated as points in a Hilbert space, allowing researchers to predict whether a black-box system will satisfy a complex temporal property without running costly new simulations.


Statistical Rigor: Conformal Inference and PAC Bounds

When deploying a system into the real world, we must quantify exactly how confident we are in our data-driven bounds. What happens if the environment changes slightly after we collect our data?

To handle this, Navid Hashemi et al. introduced Conformal Inference to reachability analysis in Data-Driven Reachability Analysis of Stochastic Dynamical Systems with Conformal Inference. Conformal inference is a distribution-free statistical framework. By using a neural network surrogate to predict future states and calibrating its errors on a small holdout dataset, they can output a prediction region that is guaranteed to contain the true future state with a user-specified probability (e.g., $99\%$).

Crucially, the authors extended this in Statistical Reachability Analysis of Stochastic Cyber-Physical Systems Under Distribution Shift to account for distribution shift—ensuring that if the system's behavior drifts over time, the safety bounds automatically adjust to remain valid.

In a similar vein of statistical rigor, Chaitanya Agarwal et al. developed Probably Approximately Correct (PAC) frameworks in PAC statistical model checking of mean payoff in discrete- and continuous-time MDP to bound long-run rewards and safety metrics for unknown Markov Decision Processes, proving that formal verification can be achieved purely through observation.


Summary

Data-driven safety verification changes the fundamental question of formal methods. It shifts the goal from "How do we analyze this differential equation?" to "How do we rigorously bound what we haven't seen using what we have seen?"

Whether by bounding states geometrically with matrix zonotopes, synthesizing barrier certificates via scenario optimization, embedding distributions into Hilbert spaces, or calibrating neural surrogates with conformal inference, these methods provide the mathematical bridge needed to safely deploy complex, black-box autonomous systems in an unpredictable world.

Key Foundational Work

Model-Free Stochastic Reachability Using Kernel Distribution Embeddings (2020) — contributed 1 concept elements to this direction.
Data driven stability analysis of black-box switched linear systems (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_model_free_reachability_analysis_b58c61df,
  title = {model-free reachability analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/model-free-reachability-analysis/rdr_b58c61df97674c2897d3d24aa5dd1180},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_model_free_reachability_analysis_b58c61df_v1,
  title = {model-free reachability analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/model-free-reachability-analysis/rdr_b58c61df97674c2897d3d24aa5dd1180/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake