An axiomatic approach to existence and liveness for differential equations

Yong Kiam Tan, André Platzer

TL;DR

This paper introduces a formal, axiomatic framework for proving that solutions to ordinary differential equations (ODEs) eventually reach a target region—a property known as liveness. By grounding these proofs in differential dynamic logic (dL), the authors provide a systematic way to decompose complex liveness properties into simpler safety properties, while simultaneously identifying and fixing several long-standing soundness errors in existing verification literature.

What Problem Does This Paper Address?

Verifying the behavior of hybrid systems—which combine discrete computer logic with continuous physical dynamics—is critical for safety-sensitive applications like autonomous vehicles or medical devices. While proving safety (that a system never enters a bad state) is relatively well-understood, proving liveness (that a system eventually reaches a good state) is significantly harder in a continuous setting.

Continuous systems face unique challenges that discrete systems do not:

  1. Finite-time blow-up: Nonlinear ODE solutions can approach infinity in a finite amount of time, "disappearing" before they ever reach their goal.
  2. Zeno behavior: A system might make an infinite number of discrete steps in a finite time.
  3. Asymptotic convergence: A solution might get closer and closer to a goal forever without ever actually touching it.

Previous attempts to create "proof rules" for ODE liveness often overlooked these subtleties, leading to "soundness errors" where a rule might claim a property is true when it actually isn't.

Methods

The authors utilize Differential Dynamic Logic (dL), a formal logic designed for specifying and verifying hybrid systems. Their core contribution is an axiomatic refinement approach. Instead of trying to prove liveness in one giant leap, they break the proof down into a chain of smaller steps.

Key techniques include:

  • Safety-to-Liveness Reduction: Using well-established ODE invariance (safety) axioms to prove that a solution cannot stay outside the goal region indefinitely.
  • Global Existence Proofs: Rather than assuming a solution exists forever, the authors treat "global existence" as a specific type of liveness property that must be proved (e.g., proving the solution can reach any arbitrary time $\tau$).
  • Topological Refinement: Incorporating topological properties (like whether a set is open, closed, or compact) into the proof rules to handle edge cases at the boundaries of goal regions.
  • Implementation: These methods were implemented as "tactics" in KeYmaera X, an interactive theorem prover for hybrid systems.

Datasets

Not discussed in the paper. As a theoretical work in formal methods, the paper evaluates its approach using mathematical examples and microbenchmarks rather than external datasets.

Key Insights and Ideas

  • Liveness is Conditional on Existence: You cannot prove a system reaches a goal without first proving the system continues to exist long enough to get there. Figure 2 illustrates a solution that "blows up" to infinity, though in that specific case, it luckily hits the goal first. Two views of an ODE solution approaching a blow-up point.

  • The Power of Invariance: The paper shows that almost all liveness arguments can be reconstructed by "refining" an initial existence property using safety properties. If you know a solution exists and you can prove it must leave its current domain, and the only way out is through the goal, you've proved liveness.

  • Correcting the Literature: The authors surveyed several prominent liveness proof rules from the past two decades and found that many were unsound. For instance, some rules failed if the goal region was not "compact" (closed and bounded). Figure 6 visualizes counterexamples where solutions "sneak out" of boundaries that previous rules thought were secure. Visualization of counterexamples showing how solutions can leave a domain without hitting the goal.
Two views of an ODE solution approaching a blow-up point.
Visualization of counterexamples showing how solutions can leave a domain without hitting the goal.

Key Results

  • Sound Proof Rules: The paper derives a library of "corrected" proof rules (summarized in Table 1) that are guaranteed to be mathematically sound because they are built directly from dL axioms.
  • Global Existence Axioms: The authors provide the first deductive approach for proving that nonlinear ODE solutions exist for all time, covering Lipschitz continuous systems and "trapped" solutions.
  • Practical Implementation: The implementation in KeYmaera X added roughly 1500 lines of code. Microbenchmarks (Table 2) show that while automated proofs are sometimes slower than manual ones, they significantly reduce the "tactic steps" a human user must perform (e.g., reducing 28 manual steps to 1 automated step for complex examples).

Limitations and Future Work

  • Computational Cost: Automated proof search for nonlinear systems can be computationally expensive, as it often requires invoking real arithmetic decision procedures.
  • User Insight: While the system is more automated, complex liveness proofs still often require "user insight" to choose the right "staging sets" or "variants" (functions that track progress toward a goal).
  • Expansion of Dynamics: The current work focuses on standard ODEs. Future work could extend these axiomatic refinements to more complex dynamics, such as differential inclusions (where the system's evolution isn't perfectly known) or differential games (where an adversary tries to prevent the system from reaching its goal).

Summary updated

Abstract

This article presents an axiomatic approach for deductive verification of existence and liveness for ordinary differential equations (ODEs) with differential dynamic logic (dL). The approach yields proofs that the solution of a given ODE exists long enough to reach a given target region without leaving a given evolution domain. Numerous subtleties complicate the generalization of discrete liveness verification techniques, such as loop variants, to the continuous setting. For example, ODE solutions may blow up in finite time or their progress towards the goal may converge to zero. These subtleties are handled in dL by successively refining ODE liveness properties using ODE invariance properties which have a complete axiomatization. This approach is widely applicable: several liveness arguments from the literature are surveyed and derived as special instances of axiomatic refinement in dL. These derivations also correct several soundness errors in the surveyed literature, which further highlights the subtlety of ODE liveness reasoning and the utility of an axiomatic approach. An important special case of this approach deduces (global) existence properties of ODEs, which are a fundamental part of every ODE liveness argument. Thus, all generalizations of existence properties and their proofs immediately lead to corresponding generalizations of ODE liveness arguments. Overall, the resulting library of common refinement steps enables both the sound development and justification of new ODE existence and of liveness proof rules from dL axioms. These insights are put into practice through an implementation of ODE liveness proofs in the KeYmaera X theorem prover for hybrid systems.
BibTeX
@inproceedings{tan2021axiomatic,
  author = {Yong Kiam Tan and André Platzer},
  title = {{An axiomatic approach to existence and liveness for differential equations}},
  booktitle = {Formal Aspects Comput},
  year = {2021},
  url = {https://openreview.net/forum?id=rMaWfn7YqtJ},
}

Loading related content...

Figure