Abstract
Hybrid systems theorem proving provides strong correctness guarantees about the interacting discrete and continuous dynamics of cyber-physical systems. The trustworthiness of proofs rests on the soundness of the proof calculus and its correct implementation in a theorem prover. Correctness is easier to achieve with a soundness-critical core that is stripped to the bare minimum, but, as a consequence, proof convenience has to be regained outside the soundness-critical core with proof management techniques. We present modeling and proof management techniques that are built on top of the soundness-critical core of KeYmaera X to enable expanding definitions, parametric proofs, lemmas, and other useful proof techniques in hybrid systems proofs. Our techniques steer the uniform substitution implementation of the differential dynamic logic proof calculus in KeYmaera X to allow users choose when and how in a proof abstract formulas, terms, or programs become expanded to their concrete definitions, and when and how lemmas and sub-proofs are combined to a full proof. The same techniques are exploited in implicit sub-proofs to provide proof features, such as temporarily hiding formulas, which are notoriously difficult to get right when implemented in the prover core, but become trustworthy as proof management techniques outside the core.
Introduction: The Soundness-Usability Trade-off
Verifying hybrid systems—which combine discrete software logic with continuous physical dynamics—is essential for safety-critical cyber-physical systems. However, theorem prover design faces a fundamental tension between soundness and usability. To ensure mathematical certainty, the "trusted core" of the software should be as small as possible (LCF-style). Yet, a minimal core often lacks the high-level features users need, such as lemma management, reusable components, or the ability to hide irrelevant details during complex proofs. Adding these features directly into the core risks bloating the software and introducing bugs. KeYmaera X addresses this by building "creature comforts" on top of a minimal core using a technique called uniform substitution.
Methods: Leveraging Uniform Substitution
The system leverages the Uniform Substitution (US) calculus, which allows the prover to replace abstract symbols (predicates, functions, or programs) with concrete ones globally across a proof. This enables several management layers:
- Delayed Proof Composition: Instead of merging proof steps immediately, the system tracks "loosely connected" sub-proofs, allowing different branches to maintain different levels of abstraction.
- Parametric Proofs: Users can begin proofs with uninterpreted symbols (e.g., an unknown loop invariant $J(x)$) and define them only after gaining a better understanding of the system.
- Explicit Lemma and Definition Management: A framework for structuring proofs into reusable lemmas. The UI provides a "Defs" menu to explicitly expand these abstract symbols when needed.
- Implicit Sub-proofs (Hiding): This technique temporarily hides formulas to reduce cognitive load. Because this is handled by the management layer rather than the core, it avoids the risk of unsoundly "forgetting" a formula.
Proof Construction and UI Integration
In KeYmaera X, the gap between a general lemma and a specific proof goal is bridged by unification—finding the right substitutions to make the two match. The user interface surfaces these management techniques through interactive tactics and hints. For example, applying a hint like Real Quantifier Elimination (QE) can close a proof branch by obtaining a provable state from a trusted solver and applying it to the remaining subgoal.
Key Insights and Results
By delaying the application of uniform substitutions, the prover allows users to explore system properties interactively without knowing the exact mathematics of a controller upfront. This approach achieves "proof convenience"—the feel of a high-level automated tool—while maintaining the mathematical rigor of a tiny, trustworthy core.
Key results include:
- Modular Construction: Successful demonstration of complex proofs structured into separate, reusable lemmas (e.g., exponential decay models).
- Enhanced UI: Implementation of "using" notation in proof scripts, allowing users to focus tactics on specific subsets of formulas.
- Trustworthy Flexibility: Features like formula hiding are implemented safely outside the core, ensuring 100% trustworthiness.
Conclusion and Future Work
While KeYmaera X significantly improves proof management, challenges remain in automating unification. Currently, applying a lemma often requires manual specification of substitutions if symbols do not match perfectly. Future work will focus on automating these unification steps and bridging more complex syntactic differences between lemmas and target subgoals to further enhance the prover's efficiency.
Summary updated