Differential Dynamic Logic for Hybrid Systems

Table of Contents
  1. Overview
  2. Syntax
  3. Verification
  4. Differential Invariants, Variants, and Cuts
  5. Details and Extensions
  6. Abstract
  7. Selected Publications
Download or
WebstartKeYmaera

Overview

Differential dynamic logic (dL) [27,25] is a logic for specifying and verifying hybrid systems [27,25]. The logic dL can be used to specify correctness properties for hybrid systems given operationally as hybrid programs [27,25]. These correctness properties can be verified using the dL verification calculus. The logic dL and its verification calculus are the basis of the deductive verification tool KeYmaera for hybrid systems [20]. In addition, the hybrid systems and correctness properties formulated in dL can even include symbolic parameters, which can be free or quantified to discover the required parametric safety constraints.

The basic idea for dL formulas is to have formulas of the form [α]φ to specify that the hybrid system α always remains within region φ, i.e., all states reachable by following the transitions of hybrid system α statisfy the formula φ. Dually, the dL formula <α>φ expresses that the hybrid system α is able to reach region φ, i.e., there is a state reachable by following the transitions of hybrid system α that statisfies the formula φ. In either case, the hybrid system α is given as a full operational model in terms of a hybrid program. Using other propositional connectives, one can state the following dL formula

φ -> [α]ψ
which expresses that, if hybrid program α initially starts in a state satisfying φ, then it always remains in the region characterised by ψ. For instance, the following dL formula expresses that for the state of a train controller train, the property z≤m always holds true when starting in a state where v2≤2b(m-z) is true:
v2≤2b(m-z) -> [train]z≤m
Here z is the position of the train, v the velocity of the train, b its braking power, and m the current end of its movement authority assigned to the train by the radio block controller (RBC).

Case Study: European Train Control System

In much the same way as finite automata can be represented as while-programs, or timed automata have a notation as real-time programs, we use a hybrid program notation for hybrid automata. Essentially, hybrid programs are what you get when you add continuous evolutions as a primitive operation to conventional discrete programs or, in fact, your favorite programming language.

Note: The proper typesetting of the name dL for differential dynamic logic is dℒ. In LaTeX, I use the following for typesetting dℒ:

\textsf{d{\kern-0.1em}$\mathcal{L}$}
\textsf{d{\kern-0.1em}$\mathscr{L}$}

Syntax

Note that the syntax of the differential dynamic logic dL given here uses slightly simplified notation in comparison to the full syntax in KeYmaera verification tool. The notation in KeYmaera uses more escaping of mathematical characters.

Operators and
Cheat
Sheet
Formulas of dL, with typical names φ and ψ, are defined by the following syntax
φ ::= \forall x φ Universal quantifier: for all real values of x, formula φ holds
\exists x φ Existential quantifier: for some real value of x, formula φ holds
[α] φAfter all runs of hybrid program α, formula φ holds (safety)
<α> φThere is at least one run of hybrid program α, after which formula φ holds (liveness)
Negation (not)
φ & ψConjunction (and)
φ | ψDisjunction (or)
φ -> ψImplication (implication)
φ <-> ψBiimplication (equivalence)
pred Real arithmetic predicate expression

The behaviour of the hybrid system α is specified as a hybrid program, which is, essentially, a program notation for hybrid systems.

Hybrid programs, with typical names α and β, are defined by the following syntax
α ::= α; βSequential composition following β after α has finished
α ++ βNondeterministic choice following either α or β
α* Nondeterministic repetition, repeating α arbitrarily often including 0 times
x:=t Discrete assignment/jump assigning the value of t to x
{x'=t,y'=s, H} Continuous evolution along differential equation system with terms t,s, optionally with evolution domain H. Systems of differential equations, differential-algebraic equations, and differential equations with disturbances are possible as well.
?H State assertion testing whether formula H is true in current state (otherwise abort)
where H is a formula of (possibly non-linear) real arithmetic.

Verification

Verifying correct functioning of hybrid systems amounts to proving validity of corresponding formulas in differential dynamic logic dL [27,25]. These dL formulas state the desired correctness properties of the hybrid systems under consideration, including safety, liveness, reactivity, and controllability properties. For showing that these systems operate as expected, André Platzer has devised a logical verification calculus [27,25].

Operators and
Rules

Case studies for using differential dynamic logic to verify complex physical systems include studies for the European Train Control System (ETCS) [16] and verification of collision avoidance in aircraft collision avoidance maneuvers [17]. But there are many more case studies.

Differential Invariants, Variants, and Cuts

Advanced verification technology for differential dynamic logics is further based on differential invariants [24,21] that define an induction principle for differential equations [7] Differential variants are a dual proof principle that can be used to prove liveness and progress properties of differential equations without having to solve them. Differential variants have been introduced in 2008 [24] and implemented in KeYmaera as well.

Details and Extensions

This page only shows the simplest version of a simple differential dynamic logic. For more details see this overview of logics for dynamical systems. Differential dynamic logic itself has been originally introduced in 2007 [27]. A hybrid-nominal version of differential dynamic logic has been published in 2006 at HyLo'06 [31].

Abstract

Hybrid systems are models for complex physical systems and are defined as dynamical systems with interacting discrete transitions and continuous evolutions along differential equations. With the goal of developing a theoretical and practical foundation for deductive verification of hybrid systems, we introduce a dynamic logic for hybrid programs, which is a program notation for hybrid systems. As a verification technique that is suitable for automation, we introduce a free variable proof calculus with a novel combination of real-valued free variables and Skolemisation for lifting quantifier elimination for real arithmetic to dynamic logic. The calculus is compositional, i.e., it reduces properties of hybrid programs to properties of their parts. Our main result proves that this calculus axiomatises the transition behaviour of hybrid systems completely relative to differential equations. In a case study with cooperating traffic agents of the European Train Control System, we further show that our calculus is well-suited for verifying realistic hybrid systems with parametric system dynamics.

Keywords: dynamic logic, differential equations, sequent calculus, axiomatisation, automated theorem proving, verification of hybrid systems

[25]

Selected Publications

The canonical references on this approach are [25,24,7,14]. Also see publications on hybrid systems logic and the publication reading guide.
  1. Sarah M. Loos, David Witmer, Peter Steenkiste and André Platzer.
    Efficiency analysis of formally verified adaptive cruise controllers.
    In Andreas Hegyi and Bart De Schutter, editors, 16th International IEEE Conference on Intelligent Transportation Systems, ITSC'13, The Hague, Netherlands, Proceedings, 2013. © IEEE
    [bib | pdf | doi | study | abstract]

  2. Stefan Mitsch, Khalil Ghorbal, and André Platzer.
    On provably safe obstacle avoidance for autonomous robotic ground vehicles.
    Robotics: Science and Systems, 2013.
    [bib | pdf | slides | study | eprint | talk | abstract]

  3. André Platzer.
    Dynamic logics of dynamical systems.
    arXiv 1205.4788, May 2012.
    [bib | pdf | arXiv | abstract]

  4. André Platzer.
    A differential operator approach to equational differential invariants.
    In Lennart Beringer and Amy Felty, editors, Interactive Theorem Proving, International Conference, ITP 2012, August 13-15, Princeton, USA, Proceedings, volume 7406 of LNCS, pages 28-48. Springer, 2012. © Springer-Verlag
    Invited paper.
    [bib | pdf | doi | slides | abstract]

  5. André Platzer.
    The structure of differential invariants and differential cut elimination.
    Logical Methods in Computer Science, 8(4), pages 1-38, 2012.
    [bib | pdf | doi | eprint | arXiv | abstract]

  6. André Platzer.
    Logics of dynamical systems.
    ACM/IEEE Symposium on Logic in Computer Science, LICS 2012, June 25–28, 2012, Dubrovnik, Croatia, pages 13-24. IEEE 2012. © IEEE
    Invited paper.
    [bib | pdf | doi | slides | abstract]

  7. André Platzer.
    The complete proof theory of hybrid systems.
    ACM/IEEE Symposium on Logic in Computer Science, LICS 2012, June 25–28, 2012, Dubrovnik, Croatia, pages 541-550. IEEE 2012. © IEEE
    [bib | pdf | doi | slides | TR | abstract]

  8. André Platzer.
    The Complete Proof Theory of Hybrid Systems.
    School of Computer Science, Carnegie Mellon University, CMU-CS-11-144, November 2011.
    [bib | pdf | LICS'12 | abstract]

  9. André Platzer.
    The Structure of Differential Invariants and Differential Cut Elimination.
    School of Computer Science, Carnegie Mellon University, CMU-CS-11-112, April 2011.
    [bib | pdf | arXiv | LMCS | abstract]

  10. André Platzer.
    Stochastic differential dynamic logic for stochastic hybrid programs.
    In Nikolaj Bjørner and Viorica Sofronie-Stokkermans, editors, International Conference on Automated Deduction, CADE'11, Wroclaw, Poland, Proceedings, volume 6803 of LNCS, pages 431-445. Springer, 2011. © Springer-Verlag
    [bib | pdf | doi | slides | TR | abstract]

  11. André Platzer.
    Logic and compositional verification of hybrid systems.
    In Ganesh Gopalakrishnan and Shaz Qadeer, editors, Computer Aided Verification, CAV 2011, Snowbird, UT, USA, Proceedings, volume 6806 of LNCS, pages 28-43. Springer, 2011. © Springer-Verlag
    Invited tutorial.
    [bib | pdf | doi | slides | abstract]

  12. André Platzer.
    Quantified differential invariants.
    In Emilio Frazzoli and Radu Grosu, editors, Proceedings of the 14th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2011, Chicago, USA, April 12-14, Pages 63-72. ACM, 2011. © ACM
    [bib | pdf | doi | slides | abstract]

  13. André Platzer.
    Quantified differential dynamic logic for distributed hybrid systems.
    In Anuj Dawar and Helmut Veith, editors, Computer Science Logic, 19th EACSL Annual Conference, CSL 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6247 of LNCS, pages 469-483. Springer, 2010. © Springer-Verlag
    [bib | pdf | doi | slides | TR | abstract]

  14. André Platzer.
    Logical Analysis of Hybrid Systems: Proving Theorems for Complex Dynamics.
    Springer, 2010. 426 p. ISBN 978-3-642-14508-7.
    [bib | book | eBook | doi | web]

  15. André Platzer.
    Differential dynamic logic: Automated theorem proving for hybrid systems.
    Künstliche Intelligenz, 24(1), pages 75-77, 2010. © Springer-Verlag
    Invited paper.
    [bib | doi | abstract]

  16. André Platzer and Jan-David Quesel.
    European Train Control System: A case study in formal verification.
    In Karin Breitman and Ana Cavalcanti, editors, 11th International Conference on Formal Engineering Methods, ICFEM, Rio de Janeiro, Brasil, Proceedings, volume 5885 of LNCS, pages 246-265. Springer, 2009. © Springer-Verlag
    [bib | pdf | doi | slides | study | TR | abstract]

  17. André Platzer and Edmund M. Clarke.
    Formal verification of curved flight collision avoidance maneuvers: A case study.
    In Ana Cavalcanti and Dennis Dams, editors, 16th International Symposium on Formal Methods, FM, Eindhoven, Netherlands, Proceedings, volume 5850 of LNCS, pages 547-562. Springer, 2009. © Springer-Verlag
    This paper was awarded the FM Best Paper Award.
    [bib | pdf | doi | slides | study | TR | abstract]

  18. André Platzer.
    Verification of cyberphysical transportation systems.
    IEEE Intelligent Systems, 24(4), pages 10-13, Jul/Aug, 2009. © IEEE.
    Invited paper.
    [bib | doi | abstract]

  19. André Platzer and Edmund M. Clarke.
    Computing differential invariants of hybrid systems as fixedpoints.
    Formal Methods in System Design, 35(1), pages 98-120, 2009. © Springer-Verlag
    Special issue for selected papers from CAV'08.
    [bib | pdf | doi | study | abstract]

  20. André Platzer and Jan-David Quesel.
    KeYmaera: A hybrid theorem prover for hybrid systems.
    In Alessandro Armando, Peter Baumgartner, and Gilles Dowek, editors, Automated Reasoning, Fourth International Joint Conference, IJCAR 2008, Sydney, Australia, Proceedings, volume 5195 of LNCS, pages 171-178. Springer, 2008. © Springer-Verlag
    [bib | pdf | doi | slides | tool | abstract]

  21. André Platzer.
    Differential Dynamic Logics: Automated Theorem Proving for Hybrid Systems.
    PhD Thesis, Department of Computing Science, University of Oldenburg, 2008.
    ACM Doctoral Dissertation Honorable Mention Award in 2009.
    Extended version appeared as book Logical Analysis of Hybrid Systems: Proving Theorems for Complex Dynamics, Springer, 2010.
    [bib | pdf | eprint | book | doi | web | abstract | slides]

  22. André Platzer and Edmund M. Clarke.
    Computing differential invariants of hybrid systems as fixedpoints.
    In Aarti Gupta and Sharad Malik, editors, Computer Aided Verification, CAV 2008, Princeton, USA, Proceedings, volume 5123 of LNCS, pages 176-189, Springer, 2008. © Springer-Verlag
    [bib | pdf | doi | slides | study | TR | abstract]

  23. André Platzer and Edmund M. Clarke.
    Computing Differential Invariants of Hybrid Systems as Fixedpoints.
    School of Computer Science, Carnegie Mellon University, CMU-CS-08-103, Feb, 2008.
    [bib | pdf | CAV'08 | abstract]

  24. André Platzer.
    Differential-algebraic dynamic logic for differential-algebraic programs.
    Journal of Logic and Computation, 20(1), pages 309-352, 2010. Advance Access published on November 18, 2008 by Oxford University Press.
    [bib | pdf | doi | study | abstract]

  25. André Platzer.
    Differential dynamic logic for hybrid systems.
    Journal of Automated Reasoning, 41(2), pages 143-189, 2008. © Springer-Verlag
    [bib | pdf | doi | study | abstract]

  26. André Platzer.
    Combining deduction and algebraic constraints for hybrid system analysis.
    In Bernhard Beckert, editor, 4th International Verification Workshop, VERIFY'07, Workshop at Conference on Automated Deduction (CADE), Bremen, Germany, CEUR Workshop Proceedings, 259:164-178, 2007.
    [bib | pdf | slides | abstract]

  27. André Platzer.
    Differential dynamic logic for verifying parametric hybrid systems.
    In Nicola Olivetti, editor, Automated Reasoning with Analytic Tableaux and Related Methods, International Conference, TABLEAUX 2007, Aix en Provence, France, July 3-6, 2007, Proceedings, volume 4548 of LNCS, pages 216-232. Springer, 2007. © Springer-Verlag
    This paper was awarded the TABLEAUX Best Paper Award.
    [bib | pdf | doi | slides | study | TR | abstract]

  28. André Platzer.
    A temporal dynamic logic for verifying hybrid system invariants.
    In Sergei Artemov and Anil Nerode, editors, Logical Foundations of Computer Science, International Symposium, LFCS 2007, New York, USA, Proceedings, volume 4514 of LNCS, pages 457-471. Springer, 2007. © Springer-Verlag
    [bib | pdf | doi | slides | study | TR | abstract]

  29. André Platzer.
    Differential logic for reasoning about hybrid systems.
    In Alberto Bemporad, Antonio Bicchi, and Giorgio Buttazzo, editors, Hybrid Systems: Computation and Control, 10th International Conference, HSCC 2007, Pisa, Italy, Proceedings, volume 4416 of LNCS, pages 746-749. Springer, 2007. © Springer-Verlag
    [bib | pdf | doi | poster | abstract]

  30. André Platzer.
    Differential logic for reasoning about hybrid systems.
    In Alberto Bemporad, Antonio Bicchi, and Giorgio Buttazzo, editors, Hybrid Systems: Computation and Control, 10th International Conference, HSCC 2007, Pisa, Italy, Proceedings, volume 4416 of LNCS, pages 746-749. Springer, 2007. © Springer-Verlag
    [bib | pdf | doi | poster | abstract]

  31. André Platzer.
    Towards a hybrid dynamic logic for hybrid dynamic systems.
    In Patrick Blackburn, Thomas Bolander, Torben Braüner, Valeria de Paiva, and Jørgen Villadsen, editors, Proc., International Workshop on Hybrid Logic, HyLo 2006, Seattle, USA, Electr. Notes Theor. Comput. Sci. 174(6):63-77, 2007.
    [bib | pdf | doi | slides | abstract]

For full details, please see my List of Publications.

There also is a verification tool implementation of dL in a theorem prover, which is called KeYmaera [20].