Implicit and Explicit Proof Management in KeYmaera X

Stefan Mitsch

TL;DR

KeYmaera X is a theorem prover for hybrid systems that prioritizes a "bare minimum" trusted core to ensure mathematical soundness. This paper introduces proof management techniques—like lemmas, parametric proofs, and delayed substitutions—that provide user convenience and modularity without increasing the complexity (and risk) of the underlying safety-critical code.

What Problem Does This Paper Address?

Verifying hybrid systems—systems that combine discrete logic (like software) with continuous dynamics (like physics)—is notoriously difficult. To ensure these systems are safe, researchers use theorem provers. However, there is a fundamental tension in theorem prover design:

  1. Soundness: You want the "trusted core" of the software to be as small as possible (LCF-style) so it can be verified easily.
  2. Usability: A tiny core is often "dumb." It lacks the high-level features users need, such as the ability to use lemmas, define reusable components, or hide irrelevant details during a complex proof.

If you add these features directly into the core, the core becomes bloated and prone to bugs. This paper addresses how to build these "creature comforts" on top of a minimal core using a technique called uniform substitution.

Methods

The author leverages the Uniform Substitution (US) calculus of KeYmaera X. US allows a prover to replace abstract symbols (predicates, functions, or programs) with concrete ones globally across a proof. The paper introduces several key management layers:

  • Delayed Proof Composition: Instead of merging proof steps immediately, the system keeps track of "loosely connected" sub-proofs. This allows different branches of a proof to maintain different levels of abstraction until the very end.
  • Parametric Proofs: Users can start a proof using "uninterpreted" symbols (e.g., an unknown loop invariant $J(x)$). They can make progress on the proof and only define what $J(x)$ actually is once they understand the system better.
  • Explicit Lemma Management: A framework for structuring proofs into reusable lemmas that can be searched and applied via the UI, even if the lemma's syntax doesn't perfectly match the current goal (resolved via substitution).
  • Implicit Sub-proofs (Hiding): A technique to temporarily "hide" formulas to reduce cognitive load. Because this is handled by the management layer rather than the core, it avoids the risk of "forgetting" a formula in an unsound way.

Datasets

As a theoretical and systems-oriented paper, it does not use traditional training datasets. Instead, the methods are evaluated and illustrated using:

  • Hybrid Program Examples: Specifically, a model involving exponential decay and control guards to demonstrate modular lemma application.
  • KeYmaera X User Interface: The paper discusses how these features are surfaced to the user through the "Defs" menu and lemma search dialogs.

Key Insights and Ideas

  • The "Aha" Moment for Abstraction: By delaying the application of uniform substitutions, the prover allows users to explore a system's properties interactively. You don't need to know the exact math of your controller to start proving that some controller could work.
  • Soundness via Management: Features like "hiding" formulas are notoriously difficult to implement safely in a prover's core. By treating "hiding" as a management tactic that simply filters what the user sees while keeping the full state in the background, the system remains 100% trustworthy.
  • Unification as a Bridge: The paper suggests that the gap between a general lemma and a specific proof goal can be bridged by "unification"—finding the right substitutions to make the two match.

Key Results

  • Modular Proof Construction: The paper successfully demonstrates a complex proof structured into separate, reusable lemmas (e.g., "Exponential decay" and "Unsatisfied control guard") that are combined into a main theorem.
  • Enhanced UI: The implementation of a "using" notation in proof scripts, which allows users to focus tactics on specific subsets of formulas.
  • Trustworthy Flexibility: The system achieves "proof convenience" (the feel of a high-level automated tool) while maintaining the "LCF-style" rigor (the mathematical certainty of a tiny core).

Limitations and Future Work

  • Automated Unification: Currently, applying a lemma often requires the user to manually specify substitutions if the symbols don't match. The author identifies the automation of these unification steps as a primary goal for future work.
  • Syntactic Bridging: Further work is needed to help the system automatically bridge more complex syntactic differences between a lemma's conclusion and the target subgoal.
  • Broader Proof Techniques: The author intends to explore how uniform substitution can be exploited for even more advanced proof management features beyond those presented here.

Summary updated

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 (without making such sub-proofs explicit to the user) 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. We illustrate our approach with several useful proof techniques and discuss their presentation on the KeYmaera X user interface.
BibTeX
@inproceedings{mitsch2021implicit,
  author = {Stefan Mitsch},
  title = {{Implicit and Explicit Proof Management in KeYmaera X}},
  booktitle = {F-IDE@NFM},
  year = {2021},
  url = {https://openreview.net/forum?id=UWYLRGSHRD},
}

Loading related content...

Figure