Introduction
Verifying the safety of cyber-physical systems (CPS)—such as autonomous vehicles, medical robotics, and drones—requires rigorous formal methods. These systems are characterized by the interaction between discrete control logic and continuous physical dynamics. Differential Dynamic Logic (dL) has emerged as a leading framework for specifying and proving the safety of these hybrid systems. However, even when a safety property is successfully proven, the underlying models often suffer from "modeling bugs" that diminish their utility. These include vacuity, where a property holds only due to contradictory assumptions, and over-specification, where unnecessary constraints make the model brittle and difficult to adapt to new environments.
To address these challenges, this paper introduces the Usage-Aware Sequent Calculus (UAPC). UAPC is a novel proof-based technique designed to track exactly how constraints are utilized within a safety proof, providing a transparent mechanism for simplifying and generalizing complex models without compromising their formal guarantees.
The UAPC Framework
UAPC extends the standard dL proof calculus by performing a fine-grained dataflow analysis during the proof process. Rather than treating a proof as a binary certificate of truth, UAPC treats it as a map of dependencies. The framework operates through several key mechanisms:
Atoms and Labeling
Every fundamental unit of a formula—such as a specific inequality ($x > 100$) or a differential equation—is treated as an "atom" and assigned a unique label. This allows the calculus to track the lifecycle of individual constraints as they are transformed through logical rules.
Mutation Tracking
As the proof progresses, UAPC tracks three distinct "mutation levels" for each label, organized in a lattice structure:
- Identity (
id): The constraint is critical to the proof's success and must remain exactly as written. - Generalize (
G): The constraint is used, but its specific bounds could be relaxed (e.g., changing a strict inequality to a non-strict one) without breaking the proof. - Remove (
R): The constraint was never invoked during the proof and can be safely deleted from the model.
Label Fusing and Variants
When different parts of a model are logically linked during a proof, UAPC "fuses" their labels to ensure consistent mutation. The authors also propose two variants: UAPC+, a more efficient sequential version for practical implementation, and UAPCdiag, which is specifically designed to diagnose whether intermediate lemmas (or "cuts") contribute meaningfully to the final proof or merely add complexity.
Theoretical Insights
UAPC represents a shift from quantitative resource tracking (common in Linear Logic) to qualitative tracking. While Linear Logic tracks how many times a resource is used, UAPC tracks how it is used. This is essential for mathematical proofs where a single physical constant might be referenced multiple times but only one specific instance determines the safety boundary.
The authors provide formal proofs for the Soundness of UAPC, ensuring that any simplified model suggested by the calculus is guaranteed to remain safe. They also establish Completeness, demonstrating that UAPC can analyze any valid dL proof.
Case Study: The Parachute Model
The effectiveness of UAPC was evaluated using a Parachute Model, which describes a skydiver’s descent. This model involves complex Ordinary Differential Equations (ODEs) for air resistance and discrete control logic for parachute deployment. By applying UAPC to the safety proof of this model, the researchers identified significant redundancies:
- Redundancy Detection: UAPC revealed that a specific safety check regarding velocity ($v - gT > -\sqrt{g/r_{op}}$) and a distance constraint ($x > 100$) were entirely unnecessary for the formal safety guarantee.
- Model Relaxation: The system suggested a "mutated" version of the model where complex constraints were replaced with
true, effectively removing them. This resulted in a more general model that is easier to verify and more robust to environmental changes. - Computational Efficiency: Unlike traditional mutation testing, which requires re-running proofs for every possible change, UAPC uses the existing proof to guide its analysis, avoiding the combinatorial explosion of search spaces.
Conclusion and Future Work
UAPC provides a powerful diagnostic tool for formal verification, moving beyond "black box" provers to offer actionable insights into model structure. While the current framework treats differential equations as largely immutable, future work aims to extend mutation capabilities to the physics themselves, allowing for the generalization of ODEs. Additionally, ongoing efforts are focused on integrating UAPC into industry-standard provers like KeYmaera X to automate the "cleanup" of complex, messy proofs in industrial CPS applications.
Summary updated