Deductive Safety Verification for Cyber-Physical Systems

58 concepts57 papers2 proposals

When deploying autonomous systems into safety-critical environments—such as self-driving cars, commercial aircraft, or medical devices—relying on empirical performance is not enough. Standard software testing and simulation are fundamentally limited: they can identify the presence of bugs, but they cannot prove their total absence. In unstructured or dynamic real-world environments, an autonomous agent faces a near-infinite number of edge cases. A system might pass millions of simulation miles or test cases, yet still fail catastrophically when encountering a rare, unmodeled corner case.

To bridge the gap between observed performance and mathematical certainty, researchers use formal safety verification. Instead of executing a system on a finite set of test inputs, formal verification uses mathematical logic and constraint solvers to prove that a system's behavior will remain within safe operational boundaries under all possible initial conditions and environmental disturbances.

The Challenge of Hybrid Dynamics

The core difficulty in verifying autonomous systems is that they are cyber-physical systems (CPS). They merge discrete digital logic (software code, neural networks, and state machines) with continuous physical motion (velocity, friction, and gravity).

Testing a purely discrete system involves exploring a finite, albeit large, state space. Testing a purely continuous system can often be handled with traditional control theory. However, when the two interact, the system's trajectories become exceptionally complex. For example, an autonomous train's software makes discrete decisions to apply brakes based on continuous sensor readings of its current speed and distance to the next station.

As explained by André Platzer in Combining Deduction and Algebraic Constraints for Hybrid System Analysis, traditional numerical simulators fall into traps when trying to model these hybrid systems because they can only compute specific, fixed configurations. If you change the initial velocity slightly, you have to re-run the entire simulation.

Deductive verification solves this by using a proof calculus to establish safety symbolically. Instead of checking individual trajectories, it derives a generalized safety envelope. For instance, it can mathematically prove the exact symbolic condition—such as a required braking distance expressed as a function of current velocity and maximum deceleration—under which a collision is guaranteed to never occur.

Traditional Simulation:
Initial State A ───► Trajectory 1 ───► Safe
Initial State B ───► Trajectory 2 ───► Safe
Initial State C ───► ??? (Infinite un-tested states)

Deductive Verification:
Initial State Space ───► [ Symbolic Proof Calculus ] ───► Proven Safe Envelope

How It Works: Differential Dynamic Logic

To formally reason about continuous physical paths controlled by discrete software steps, researchers rely on specialized logics. A prominent framework is differential dynamic logic ($dL$), introduced by André Platzer in Real Analysis for Complex Systems.

Differential dynamic logic allows engineers to write formulas that simultaneously speak about computer programs and differential equations. A typical safety property in $dL$ takes the form:

$$\text{Initial Conditions} \implies [\text{Control Program}; \text{Physical Dynamics}] \text{Safety Metric}$$

This statement asserts: If the system starts in a valid initial state, then no matter how the discrete control program runs, and no matter how long the physical dynamics evolve according to its differential equations, the system will always satisfy the safety metric.

To prove these formulas without executing the system, verification tools like KeYmaera break down the system's behavior using deductive rules, as documented by Jan-David Quesel et al.. The process relies heavily on finding inductive invariants—mathematical properties that remain true before and after every single execution cycle of the controller and physical movement. If an invariant is true initially, remains true across every transition, and implies safety, the system is mathematically proven to be safe for an infinite time horizon.

Scaling to Modern Complexity

While deductive verification offers absolute guarantees, proving properties about high-dimensional systems or non-linear dynamics can be computationally heavy. Researchers use several key strategies to scale these methods to complex autonomous systems:

1. Automated Constraint Solving

Instead of manual mathematical proofs, modern verification frameworks encode system constraints into Satisfiability Modulo Theories (SMT) formulas. As shown by Marco Bozzano et al., complex validation tasks like model refinement and fault diagnosis can be unified into a single logical framework. This allows automated SMT solvers to exhaustively search for violations or confirm safety across all possible states.

2. Over-Approximation and Abstraction

When dealing with highly complex components like deep neural networks (DNNs), calculating exact physical boundaries is often impossible. To circumvent this, Yizhak Yisrael Elboher et al. demonstrate the power of over-approximation. By shrinking a large, non-linear network into a simplified, "abstract" version that bounds the original network's behavior, verification tools can prove safety properties orders of magnitude faster. If the simplified, broader envelope is proven safe, the real system is guaranteed to be safe as well.

▲ Continuous State Space
│      ┌──────────────────────────┐
│      │   Over-Approximated      │
│      │   Abstract Boundary      │
│      │   ┌──────────────────┐   │
│      │   │ Actual Non-linear│   │
│      │   │ System Behavior  │   │
│      │   └──────────────────┘   │
│      └──────────────────────────┘
│                                    ❌ Unsafe Region
└─────────────────────────────────────────────────────►

3. Workspace Partitioning

For complex sensor inputs like LiDAR data, systems can become highly non-linear. Xiaowu Sun et al. addressed this by partitioning a robot's workspace into localized regions where sensor data behaves linearly. This transforms a intractable non-linear verification problem into a series of solvable logic puzzles.

Composition and Real-World Applications

A major benefit of formal verification is its ability to handle interacting systems safely. In advanced driver-assistance architectures, separate features often control different physical dimensions—such as Lane Keeping (lateral control) and Adaptive Cruise Control (longitudinal control).

As highlighted by Xiangru Xu et al., verifying these features independently is insufficient because their physical dynamics interact. By utilizing Control Barrier Functions and contract-based designs, developers can establish mathematical guarantees that separate control systems will not conflict or force the vehicle into an unsafe state.

This mathematical verifiability provides a rigorous foundation for safety in high-stakes environments where human intervention is absent, as noted by Amika Singh et al.. Beyond autonomous vehicles and aerospace collision avoidance (Stefan Mitsch et al.), these methods are increasingly vital for regulatory approval in medical cyber-physical systems, such as proving that automated artificial pancreas systems will never violate critical physiological safety boundaries (Josephine Lamp et al.).

Key Foundational Work

A Model-Theoretic Approach to the Verification of Situated Reasoning Systems (1993) — contributed 1 concept elements to this direction.
Modelling and analysis of a collision avoidance protocol using Spin and Uppaal (1996) — contributed 1 concept elements to this direction.
A Reactive Mobile Robot Based on a Formal Theory of Action (1996) — 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_formal_safety_verification_deductive_ver_719bdc53,
  title = {formal safety verification (deductive verification)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-safety-verification-deductive-verification/rdr_719bdc53766549fd9dc3f6b382a96ee3},
  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_formal_safety_verification_deductive_ver_719bdc53_v1,
  title = {formal safety verification (deductive verification)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-safety-verification-deductive-verification/rdr_719bdc53766549fd9dc3f6b382a96ee3/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