key: cord-0048945-4gn81b0i
authors: Kolčák, Juraj; Dubut, Jérémy; Hasuo, Ichiro; Katsumata, Shin-ya; Sprunger, David; Yamada, Akihisa
title: Relational Differential Dynamic Logic
date: 2020-03-13
journal: Tools and Algorithms for the Construction and Analysis of Systems
DOI: 10.1007/978-3-030-45190-5_11
sha: 0e58af3455a49efa4fbaee55ca4eafcdfafe9055
doc_id: 48945
cord_uid: 4gn81b0i

In the field of quality assurance of hybrid systems, Platzer’s differential dynamic logic (dL) is widely recognized as a deductive verification method with solid mathematical foundations and sophisticated tool support. Motivated by case studies provided by our industry partner, we study a relational extension of dL, aiming to formally prove statements such as “an earlier engagement of the emergency brake yields a smaller collision speed.” A main technical challenge is to combine two dynamics, so that the powerful inference rules of dL (such as the differential invariant rules) can be applied to such relational reasoning, yet in such a way that we relate two different time points. Our contributions are a semantical theory of time stretching, and the resulting synchronization rule that expresses time stretching by the syntactic operation of Lie derivative. We implemented this rule as an extension of KeYmaera X, by which we successfully verified relational properties of a few models taken from the automotive domain.

Hybrid Systems Cyber-physical systems (CPSs) have been studied as a subject in their own right for over a decade, but the rise of automated driving in the last few years has created a panoply of challenges in the quality assurance of these systems. In the foreseeable future, millions of cars will be driving on streets with unprecedented degrees of automation; ensuring the safety and reliability of these automated driving systems is a pressing social and economic challenge.

The hybridity of cyber-physical systems, the combination of continuous physical dynamics and discrete digital control, poses unique scientific challenges. To address these challenges, two communities have naturally joined forces: control theory whose traditional application domain is continuous dynamics and formal methods that have mainly focused on the analysis of software systems. This has been a fruitful cross-pollination: techniques from formal methods such as bisimilarity [9] and temporal logic specification [8] have been imported to control theory, and conversely, control theory notions such as Lyapunov functions have been used in formal methods [26] .

Deductive Verification of Hybrid Systems In the formal methods community, two major classes of techniques are model checking (usually automatabased and automatic) and deductive verification (based on logic and can be automated or interactive). Model checking techniques rely on exhaustive search in state spaces and therefore cannot be applied per se to hybrid systems with infinite state spaces. This has led to the active study of discrete abstraction of hybrid dynamics, see e.g. [9] ; or of bounded model checking, see [5] .

In contrast, nothing immediately rules out the use of the deductive approach for hybrid systems. Finitely many variables in logical formulas can represent infinitely many states, and proofs in suitably designed logics are valid even when the semantic domain is uncountable. That said, designing such a logic, proving the soundness of its rules, and showing that logics is actually useful in hybrid system verification is a difficult task.

Platzer's differential dynamic logic dL [21] is a remarkable success in this direction. Its syntax is systematic and intuitive, extending the classic formalism of dynamic logic [10] with differential equations as programs. Its proof rules encapsulate several essential proof principles about differential equations, including a differential invariant (DI) rule for universal properties and side deduction for existential properties. The logic dL has served as a general platform that accommodates a variety of techniques, including those which come from real algebraic geometry [22] . Furthermore, dL comes with sophisticated tool support: the latest tool KeYmaera X [15] comes with graphical interface for interactive proving and a number of automation heuristics.

Relational Reasoning on Hybrid Systems In this work, we introduce proof-based techniques for relational reasoning to the deductive verification of hybrid systems. Here, by relational reasoning we mean analyzing how changes in the system will affect the overall system behavior. One of the applications of such reasoning in our mind is to deduce the safety of a system by checking the most aggressive settings. To make such reduction sound, we need to verify that less aggressive versions result in less dangerous outcomes than the aggressive ones. As a simple example, consider the following case distilled from our collaboration with an industrial partner. Example 1 (leading example: collision speed). Consider two cars C and C, whose positions and velocities are real numbers denoted by x, x and v, v,

The two hatched areas designate the traveled distances (x = x = 1). We can compute the collision speeds (v = √ 2 and v = 2) via the closed-form solutions of the differential equations (1), concluding v ≤ v when x = x = 1. respectively. Their dynamics are governed by the following differential equations:

(1)

Both cars start at the same position at rest (x = x = 0 ∧ v = v = 0), and both drive towards a wall at position 1. We consider this question: which car is traveling faster when it hits the wall?

The second car, C, has strictly greater acceleration all the time, so we can imagine that C hits the wall harder. This hypothesis turns out to be correct, but we are more interested in how this claim could be proven.

A simple proof would be to solve the differential equation exactly and notice C has greater velocity at the end of its run. However, it is known that closed-form solutions are scarce for ODEs-we want a proof method that is more general.

Another possible argument is based on the relationship between the accelerations. Since the second car's acceleration is greater at every point in time, we might be tempted to conclude that the second car's velocity must always be greater than the first car's, based on the monotonicity of integration:

However, this reasoning has a flaw. C reaches the wall at an earlier point in time than C, and therefore C has more time to accelerate. In the end, we have to compare T 0 a(t) dt and T 0 a(t) dt where a(t) ≤ a(t) for all t ∈ [0, T ] but T > T , as depicted in figure 1.

Our solution, roughly stated, is to compare the two cars at the same points in space by reparametrizing time for one of the two cars. This parametrization is specially chosen to ensure the two cars pass through the same points in space at the same points in time.

Our current work is about a logical infrastructure needed to support this kind of relational reasoning comparing two different dynamics, based on dL. Our semantical theory, as well as the resulting syntactic extension of dL by what we call the synchronization rule, generalizes the kind of reasoning in Example 1 using the notion of time stretching.

Technical Contributions We make the following technical contributions.

1. Formulation of relational reasoning in dL. We find that relational properties are expressible in dL, using disjoint variables in a sequential composition. This representation, however, does not allow the use of the rich logical infrastructure of dL (such as the (DI) rule). 2. Time stretching, semantically and syntactically. To alleviate this difficulty, we first develop the theory of time stretching, so that we can compare two dynamics at different timepoints (cf. Example 1). Accommodating this semantical notion in dL and KeYmaera X is not possible per se. We introduce an indirect syntactic alternative, which turns out to be better suited in fact to many case studies (where we compare the two dynamics at the same "position," much like in Example 1). The resulting synchronization rule in dL has a clean presentation (Theorem 24), owing to the syntactic Lie derivative operator in dL. 3. Implementation and case studies. We implemented the new synchronization rule as an extension of KeYmaera X. We used it successfully for establishing nontrivial relational properties in case studies taken from the automotive domain.

Relational Reasoning in Practice We contend relational reasoning has practical significance based on our collaboration with an industry partner. Relational properties, especially with an aspect of monotonicity, abound in real-world examples. In particular, we have often encountered situations where we have a parametrized model M (p) and need to show a property of the form:

These properties occur especially in the context of product lines, where the same model can come in many slight variants. Example 1 is such a situation.

Relational statements (such as monotonicity) are easy to state and interpret. Intuitions about the direction of the change in a behavior of a system resulting from the change of a parameter are more often valid than intuitions about the amount of such a change. These kinds of simple statements are often used by engineers to establish the basic credibility of a model. Qualitative, relational properties also tend to be easier to prove than exact, quantitative properties.

Finally, monotonicity can serve as a powerful technique in test-case reduction. If a safety property is too complex to be deductively verified, one usually turns to testing. It is often still possible to establish a simple monotonicity property of the form (2). This can powerfully boost testing efforts: one can focus exclusively on establishing safety for the extreme case M (p max ).

Since this work is about its relational extension, the works we mentioned on dL are naturally relevant. We discuss other related works here.

Simulink (Mathworks, Inc.) is an industry standard in modeling hybrid systems, but unfortunately Simulink models do not come with rigorously defined semantics. Therefore, while integration with Simulink is highly desirable any quality assurance methods for hybrid systems, formal verification methods require some work to set up the semantics for Simulink models. The recent work [12] tackles this problem, identifying a fragment of Simulink, and devising a translator from Simulink models to dL programs. Their translation is ingenious, and their tool is capable of proving rather complicated properties when used in combination with KeYmaera X [15] .

Relational extensions of the Floyd-Hoare logic-which can be thought of as a discrete-time version of dL-have been energetically pursued especially in the context of differential privacy [4, 2, 3] .

In deductive verification of hybrid systems, an approach alternative to dL uses nonstandard analysis [23] and regards continuous dynamics as if they were discrete due to the existence of infinitesimal elements [24, 25] . The logic used in that framework is exactly the same as the classic Floyd-Hoare logic, and the soundness of the logic in the hybrid setting is shown by a model-theoretic result called the transfer principle. Its tool support has been pursued as well [11] . This is not the first time that relational reasoning-in a general sensehas been pursued in dL. Specifically, Loos and Platzer introduce the refinement primitive β ≤ α, which asserts a refinement relation between two hybrid dynamics, meaning the set of successor states of β is included in that of α [14] . This kind of relation is inspired by the software engineering paradigm of incremental modeling (supported by languages and tools such as Event-B [1, 6] ); the result is a rigorous deductive framework for refining an abstract model (with more nondeterminism) into a more concrete one (with less nondeterminism). In contrast, we compare one concrete model (not necessarily with nondeterminism) with another. Thus, our notion of relational reasoning builds more on relational extensions of the Floyd-Hoare logic [4,2,3] than on Event-B. Combining these two orthogonal kinds of relational extensions of dL is important future work.

Organization In Section 2, we recall some basics of differential dynamic logic dL: its syntax, semantics and some proof rules. Our main goal, relational reasoning, is formulated in Section 3, where we identify difficulties in doing so in the original dL. In Section 4 we introduce the semantical notion of time stretching, and turn its theory into the new synchronization rule. After introducing our implementation in Section 5, we describe our three case studies in Section 6.

The appendix containing omitted proofs and details, the source code and the artifact are found at http://group-mmm.org/rddl tacas 2020/.

We recall some of the basics of differential dynamic logic (dL). The interested reader is referred to [19, 20] for full details.

Definition 2 (language). We fix a set V of variables, denoted by x, y, . . . . The set of terms is defined by the following grammar:

where x ∈ V and n ∈ N. First-order formulas are defined by P, Q, . . . ::= e ≤ f | ¬P | P ∧ Q | ∀x. P A state is a function mapping each variable to a real number, ω : V → R. We denote the set of all states by R V . Given a state, each term has a valuation in the reals, and each formula has a valuation in Booleans defined by the usual induction. We denote these by e ω ∈ R and P ω ∈ {true, false}, respectively. The models of a first-order formula P are the states satisfying P ,

We use classical shorthands, including e = f := e ≤ f ∧ f ≤ e, P ∨ Q := ¬(¬P ∧ ¬Q), ∃x. P := ¬(∀x. ¬P ), and := 0 ≤ 0. We denote a vector (e 1 , . . . , e n ) of terms (or variables) by e when the length n is irrelevant or clear from the context.

We now introduce the syntax of hybrid programs.

Definition 3 (hybrid programs). The set HP(V) of hybrid programs over variables V is given by the following grammar:

We may also abbreviateẋ 1 = e 1 , . . . ,ẋ n = e n byẋ = e. Hybrid programs of the formẋ = e & Q are especially important in this work. We call such a program differential dynamics, whereẋ = e is its differential equation and the first-order formula Q is its evolution domain constraint. The intuitive meaning of such a program is that the values of the variables x evolve continuously in time according toẋ = e, as long as Q is satisfied at the current value of x. If we see differential dynamics as a continuous analog of loops, then Q plays the role of guard andẋ = e plays the role of body. 5 We writeẋ = e instead ofẋ = e & .

According to the Picard-Lindelöf theorem [13] , for each differential equatioṅ x = e and each state ω, there is a unique maximal solution ψ ω : [0, T ω ) → R V of the differential equation satisfying ψ ω (0) = ω.

Definition 5 (semantics of hybrid programs). The semantics of a hybrid program α is a relation − α → ⊆ R V × R V on states, defined by:

where ; denotes relation composition, and 6. − α * → = (− α →) * where * denotes the reflexive transitive closure.

Definition 6 (dL formulas). Modal formulas extend first-order formulas and are defined by the following grammar:

As usual, we write α ϕ to abbreviate ¬ α ¬ϕ. We will also call modal formulas "dL formulas" since these are the widest class of formulas in dL.

The Boolean valuation ϕ ω of a modal formula ϕ in a state ω is defined in the same way as for first-order formulas, with the addition of α ϕ ω = true if and only if ϕ ω = true for all ω such that ω − α → ω .

We take the sequent-calculus style proof system for dL, following [22] . It has judgments of the form Γ ϕ, where Γ is a set of modal formulas and ϕ is a single modal formula. One of the most fundamental axiom is

Some other rules of dL, such as the differential invariant rule (DI) that is central in many proofs, are introduced later in Definition 13.

Intuitively, we want a way to describe two dynamics that are executed in parallel, and compare their outputs. In terms of (nondeterministic) transition systems, parallel composition is available via tensor products.

Definition 7 (tensor product). Given two transition systems (S, R) and (S , R ), their tensor product (S × S , R ⊗ R ) is defined to be the transition system whose transition relation is given by

No extension of the dL syntax is needed to model tensor products: disjointness of the variables of the two systems suffices. From now on we split variables into two disjoint sets: V = V V. We denote variables in V by x, y, . . . and those in V by x, y, . . . . Terms in T ( V ), first-order formulas in Fml ( V ), and programs in HP( V ) are denoted by e, f , . . . , P , Q, . . . , and α, β, . . . , and similarly for the corresponding constructs with V.

An easy proof of the following fact can be found in the appendix.

Scenarios with two parallel differential dynamics are the main focus of this work. We formalize an assertion relating two dynamics using the following format. It is a syntactic counterpart of Proposition 8.

Definition 9 (relational differential dynamics). We call hybrid programs of the following form relational differential dynamics (RDD)

Now that we have ways to express separate systems evolving in parallel, we turn to the construction of proofs which reason about their relationships.

Example 10. Using RDD, the problem in Example 1 is expressed as

Let us prove, in KeYmaera X, the RDD sequent Γ C δ C ; δ C φ C . In KeYmaera X, the only applicable rule to this sequent turns it into Γ C δ C δ C φ C . We then explicitly "solve" the second dynamics, yielding the following goal:

where x and v in φ C are replaced by their explicit solutions with respect to the freshly introduced time variable t. Again differential invariant rules do not apply to (4), so one must solve the first dynamics, too, yielding

Since this goal is first order, the quantifier elimination, a central proof technique in KeYmaera X [18] , proves the goal.

The above example worked out since it admits explicit solutions expressible in dL. This is not always the case as the following example demonstrates.

Example 11. We consider two objects moving through fluids subjected to different kinds of drag. One object moves through a viscous fluid and is therefore subject to linear drag; its dynamics are δ F :

The other object moves through a less viscous fluid and is subject to turbulent drag; its dynamics are δ F := (ẋ = v,v = −v 2 ). Our goal is to show that the latter has higher speed when both objects reach a certain point in space (x = x = l).

The following functions v * , x * , v * and x * are solutions of the dynamics.

v

where v 0 etc. denote the initial values. Unfortunately, we cannot express exponentiations and logarithms in KeYmaera X, and thus the "solve" rule that we used in Example 10 cannot be applied here.

One obvious solution to this would be to add support for exponentiations and logarithms in KeYmaera X, but this would break the decidability of the underlying first order logic, which is a major feature of dL [18] . In fact, the same issue occurs even in standard use cases of KeYmaera X, and motivated the introduction of proof rules which do not demand explicit solutions to differential dynamics [20, 22] using the Lie derivative.

Definition 12 (formal Lie derivative in dL from [20, 22] ). The formal Lie derivative of a term f along dynamics δ ≡ (ẋ = e & Q) of dimension n is a dL term L δ f ∈ T (V) given by 6 L δ f := ∂ ∂x1 f · e 1 + · · · + ∂ ∂xn f · e n Definition 13 (proof rules from [20, 22] ). The following rules are sound:

, (∼, ) ∈ { (=, =), (>, ≥), (≥, ≥) }, and g is any term without division.

The differential invariant rule (DI) is the central rule for proving safety properties [20, 22] : it reduces a global property of the dynamics to local reasoning by means of Lie derivatives. The Darboux inequality rule (Dbx) is derived from real algebraic geometry; see e.g. [22] .

Example 14. Consider an example differential dynamics in one variable,ẋ = 2. Suppose we want to show that x ≥ 0 holds after following these dynamics for any amount of time, starting from x = 1. One way to do this is to show that (1) this predicate holds initially and (2) the time derivative of x is always nonnegative. These are precisely the two premises of the (DI) rule: to show the sequent x = 1 [ẋ = 2]x ≥ 0 (DI) requires us to prove (1) x = 1 x ≥ 0 and

Note that we give an initial condition x = 1 in the precedent of this sequent.

The intuitive explanation of the RDD construction of Definition 9 is a "serialization" of two dynamics. This construction however does not match the (DI) 6 It is easy to see that the derivative of a term t ∈ T (V) with respect to x ∈ V can be given as a dL term ∂ ∂x e ∈ T (V) such that ∂ ∂x e = ∂ ∂x e . The definition of ∂ ∂x e is inductive with respect to the term e. and (Dbx) rules, as they accept only one dynamics followed by a comparison. In order to make use of these rules in our relational reasoning, we introduce another proof method. It "synchronizes" two dynamics.

After some theoretical preparations we define the new rule and prove its soundness. We will illustrate the usefulness of this rule in Section 6, through some case studies that are inspired by our collaboration with the industry.

A key theoretical tool towards the soundness of our synchronization rule is called time stretching. Its idea is very similar to the technique of time-reparametrization for ODEs [7] . 

Proof. We haveρ(t) =K(t)·ψ(K(t)) =K(t)·f (ψ(K(t))) =K(t)·f (ρ(t)), where the first equality is by the definitions and the chain rule, the second equality is by the assumption onψ, and the last equality is by the definition of ρ.

Since the inverse of a time stretch function is another time stretch function, we obtain the following corollary of Lemma 17.

Then the function ψ : [0, K(T )) → R V , defined by ψ(s) := ρ(K −1 (s)), satisfiesψ(s) = f (ψ(s)) whenever 0 ≤ s < K(T ).

So far our time-stretch function K has been a semantical object. Here we introduce a syntactic way of reasoning via time-stretch functions. Since a desired time-stretch function is not necessarily expressible in dL, our syntactic reasoning uses an indirect method that exploits a pair of functions called a synchronizer. We will be eventually led to a syntactic reasoning rule (Sync) (Thm. 24).

Given a term g ∈ T (X) and a mapping ψ : [0, T ) → R X , we define g ψ :

Intuitively, g ψ (t) is the value of g at time t when we follow the dynamics whose solution is ψ.

Definition 19 (synchronizers). Let (δ, δ) be a pair of dynamics, (ω, ω) ∈ R V × R V be a pair of states, and ψ : [0, T ) → R V and ψ : [0, T ) → R V be the unique solutions of δ and δ from ω and ω, respectively. We say a pair of dL terms (g, g) ∈ T ( V ) × T ( V ) synchronizes (δ, δ) from (ω, ω) if the following hold.

g ψ (0) = g ψ (0) -The derivatives of g ψ and g ψ are both strictly positive.

The following lemma ensures that, for any synchronizer, a corresponding time stretch function exists.

Lemma 20. In the setting of Definition 19, let t ∈ [0, T ) and t ∈ [0, T ) be such that g ψ (t) = g ψ (t). Then the function K, defined by K(s) := g ψ −1 (g ψ (s)), is a time stretch function from [0, t] to [0, t]. Moreover we haveK(s) =ġ ψ (s) g ψ (K(s)) .

Proof. Since g ψ is strictly monotonic on [0, t], it has an inverse g ψ −1 defined from g ψ ([0, t]) to [0, t]. By assumption we have g ψ (0) = g ψ (0), and thus K(0) = g ψ −1 (g ψ (0)) = g ψ −1 (g ψ (0)) = 0. Also since g ψ (t) = g ψ (t), we see that

whose value is positive by assumptions on the derivatives of g ψ and g ψ .

We remark that time stretch functions we obtain in Lemma 20 are not necessarily expressible as a dL term, as exemplified by the following example. Now let g = x and g = x. Then g ψ (s) = log(1 + s), g ψ = g ψ −1 = id and thus K(s) = g ψ −1 (g ψ (s)) = log(1 + s). This is not rational and not expressible in dL.

Using the syntactic Lie derivative (Definition 12), we state a sound inference rule that does not need K to be represented explicitly. We note that there is strong support for Lie derivatives in the tool KeYmaera X, as a key syntactic operation behind the differential invariant (DI) rule (Definition 13).

Let δ := ẋ = e & Q and δ := ẋ = e & Q be two dynamics and let (g, g) ∈ T ( V ) × T ( V ) (which is supposed to be a synchronizer). We define the synchronized dynamics of (δ, δ) with respect to (g, g) as follows:

Lemma 23. Let (g, g) be a synchronizer of (δ, δ) from (ω 0 , ω 0 ). The following are equivalent, where the semantical transition relations are from Definition 5.

Proof. We first prove (1 ⇒ 2). In the proof of Lemma 20, we can observe thaṫ g ψ (s) = L δ g ψ(s) , and analogously,ġ ψ (s) = L δ g ψ(s) . Hence we obtaiṅ

where ρ : [0, t) → R V V is defined by ρ(s) := ψ(s), ψ(K(s)) . We note that K : [0, t] → [0, K(t)] is a time-stretch function, and that ψ is a solution ofẋ = e, that is,ψ(u) = e ψ(u) whenever 0 ≤ u < t = K(t). Combined with Lemma 17, we obtaiṅ ψ • K (s) =K(s) · e ψ(K(s)) =K(s) · e ρ(s) whenever 0 ≤ s < t.

Hence, with the fact that ψ is a solution ofẋ = e, we obtaiṅ ρ(s) = ψ (s),˙ ψ • K (s) = e ρ(s) ,K(s) · e ρ(s) = e, L δ g L δ g · e ρ(s) whenever 0 ≤ s < t. Here the last equality is from (6) . This concludes that ρ is a solution of the dynamics δ ⊗ (g,g) δ. It remains to prove that for all τ ∈ [0, t], Q ∧ Q ∧ L δ g > 0 ∧ L δ g > 0 ρ(τ ) is true. This is an easy consequence of item 1, and the fact that (g, g) is a synchronizer of (δ, δ) from (ω 0 , ω 0 ). For the direction (2 ⇒ 1), let (ξ, ξ) : [0, T ) → R V × R V be the unique solution of δ ⊗ (g,g) δ from (ω 0 , ω 0 ). Then there is t ∈ [0, T ) such that (ξ(t), ξ(t)) = (ω, ω). Let us prove that (ω, ω) ∈ g = g . The function h : s ∈ [0, T ) → g ξ(s) − g ξ(s) is equal to 0 at s = 0 and its derivative is given by:

Consequently, h is the constant function equal to 0, which implies that (ω, ω) ∈ g = g . By definition, ξ is a solution of δ, so ω 0 − δ → ω. Furthermore, by Corollary 18, ξ • K −1 is a solution of δ. Thus ω 0 − δ → ω and (ω 0 , ω 0 ) − δ; δ → (ω, ω).

The above lemma is a key observation in the current work. It allows us to turn the relational dynamics δ; δ-expressed as a sequential composition in dLinto a combined dynamics δ ⊗ (g,g) δ. Moreover, we can do so in a way that the two dynamics are synchronized in a reparametrized manner, as specified by (g, g) . Such combination of two dynamics is crucial in exploiting the logical infrastructure of dL and KeYmaera X-we emphasize again that the (DI) rule does not support invariant reasoning about the relationship between δ and δ, when the relational dynamics is expressed in the original form δ; δ.

The following is an incarnation of Lemma 23 as a proof rule. We assume that a postcondition is a conditional form E ⇒ ϕ; E is called an exit condition. By assuming that E implies g = g, we enforce the second condition (ω, ω) ∈ g = g in item 1 of Lemma 23. The first three premises are there to ensure that (g, g) is a synchronizer. Under these premises (the first four), the rule allows one to transform its conclusion (about δ; δ) into one about the combined dynamics δ ⊗ (g,g) δ, which is amenable to application of the (DI) rule, for example.

Theorem 24 (synchronization rule). The following inference rule is sound:

Recall the definition of δ ⊗ (g,g) δ (Definition 22), where time stretching for the second dynamics δ is expressed syntactically by Lie derivatives. We call the four premises Γ g = g, E g = g, Γ [ δ ]L δ g > 0, and Γ [ δ ]L δ g > 0 the synchronizability conditions. These obligations are usually easy to discharge. The last premise, which we call the synchronized formula, is typically the core remaining obligation.

Remark 25 (choice of (g, g)). In applying the (Sync) rule, one still has to find a suitable synchronizer (g, g). This turns out to be straightforward in many examples. In all the case studies in Section 6 and in Example 1, the exit condition E is of the form x = x = C where C is a constant. This suggests the use of g = x, g = x. Indeed, all our proofs use this choice of (g, g).

KeYmaera X [17] is an interactive theorem prover based on the sequent calculus formulation of dL. It is implemented in Scala, replacing its former system KeYmaera [16] . It has a web-based GUI environment, and a support of automated theorem proving using computer algebra systems such as Mathematica [27] .

For the formalization of case studies in Section 6, we extended KeYmaera X version 4.7 (available at [17] ) with the (Sync) rule. This extension of KeYmaera X, together with our proofs in case studies, are currently available at http:// group-mmm.org/rddl tacas 2020/.

The KeYmaera X implementation is structured in a flexible manner, from which we benefited. To add a rule to KeYmaera X, one has to implement a Scala program that take the conclusion of the rule and generate the premises of the rule as subgoals. The fact that any Scala program is allowed here enabled us to implement complex algorithms, such as inductive translation of formulas.

In implementing the (Sync) rule, the functions in KeYmaera X called helpers helped us, such as in the Lie derivative computation and the functionality to simplify formulas into equivalent ones. The bulk of our effort regarded the ⊗ (g,g) operator. There we did a bit more general than we stated in the paper: not only taking dynamics of formẋ = e & Q, we also allow sequences of dynamics possibly interleaved by guards and nondeterministic choices. This feature was utilized in the case study that will be described in Section 6.3.

We describe three case studies where we proved relational properties of hybrid dynamics. We did so formally in our extension of KeYmaera X described in Section 5. In all the examples, we apply the (Sync) rule as a main proof step, in conjunction with the existing rules in dL. Below, we describe our example systems and outline the important steps in the formal proofs.

In this section we apply the (Sync) rule to the running Example 1. For this example we consider two dynamics δ C := ẋ = v,v = a and δ C := (ẋ = v,v = a). Both dynamics represent a car with constant acceleration. Our claim is that if acceleration is larger in the first system, then the first car is necessarily faster than the second car after traveling the same distance l; formally,

where

We apply the (Sync) rule, where g := x and g := x. The first two synchronizability conditions are Γ x = x and x = l, x = l x = x, which are trivial. The last two synchronizability conditions are

which are proven using differential invariants (DI). The synchronized formula is

One might try to show the inequality v − v ≥ 0 by the differential invariant (DI) rule, but the Lie derivative of the term v − v is a − a · (v/v), which is not obviously nonnegative. Instead, a trickier expression a·(v 2 −v 2 0 )−a·(v 2 −v 2 0 ) = 0 turns out to be an invariant. Its Lie derivative is a · (2v) · a · (v/v) − a · (2v) · a, which is clearly 0, since we also know v > 0.

We do not have an intuitive explanation for this invariant, but it was found by a template-based search, like many other invariants in dL. By positing the existence of a polynomial invariant of a certain degree, we can find conditions on the coefficients by requiring its Lie derivative and initial value are zero. Solving these conditions for a second-degree invariant on the velocities in the system yielded the invariant above.

After finding our invariant, we additionally have to show the invariant entails our desired result, v ≤ v. This can be shown with a standard monotonicity property of modal logics: from φ ψ and Γ [α]φ, we can conclude Γ [α]ψ, where φ states the expression above is an invariant and the velocities are always greater than their initial value, and ψ is our goal: v ≤ v.

Here we continue Example 11, where we consider two dynamics

First, we establish the fact that the objects in this example always have positive velocity. We show this by the (Dbx) rule (Definition 13), where L δ F v = −v 2 and L δ F v = −v. This allows us to infer v > 0 and v > 0 hold at all times.

We apply the (Sync) rule along x = x, yielding the synchronized dynamicṡ

Note that the new evolution domain condition v > 0 allows us to rewrite v · (v/v) to v. The synchronizability conditions follow immediately from the fact that v > 0 and v > 0. For the synchronized formula, we apply the (DI) rule, so the desired inequality v ≥ v is reduced to v 2 ≤ v, that is, v ≤ 1. To this end, v > 0 tells us that the derivative of v, that is, −v 2 , is always negative, therefore v ≤ 1.

In this example, we consider two abstract models of cars. The first car is able to provide a high amount of constant acceleration a at low velocities, but at a certain velocity v cut the engine switches to a different mode and then provides a lesser, but still constant acceleration a cut . The second car is an abstracted version of the first, which ignores this mode change and provides the same constant amount of acceleration a at all velocities. Our aim in this example is to establish a safety envelope around the first car's behavior using the more simply stated second car's dynamics. Hence we show that the second car's velocity is greater than the first's at any position x = x = l. More formally, the behavior of the first car is expressed as a hybrid program α := ( δ 1 ; ?v = v cut ; δ 2 ) with two modes: δ 1 := (ẋ = v,v = a & v ≤ v cut ) and δ 2 := (ẋ = v,v = a cut ). The second car follows the simple dynamics δ := (ẋ = v,v = a). Our goal is to prove the sequent Γ α; δ (x = x = l ⇒ v ≤ v), where the initial conditions are given by

Technically, the (Sync) rule merges one differential dynamics with another, but the program the first car executes is a more complicated composition of dynamics and testing. However, it is possible to synchronize piecewise, first synchronizing δ with δ 1 until the first car changes modes, then synchronizing δ with δ 2 for the remainder of their runs. This slightly generalized synchronization procedure means that we can instead show

There are also now two sets of synchronizability conditions to satisfy, but both are again straightforward. Since δ 1 and δ are nearly identical (except for the evolution domain constraint), their synchronization δ 1 ⊗ (x,x) δ basically identifies the two dynamics. The synchronization of δ 2 and δ is exactly the synchronization performed above in Section 6.1, and proceeds in the same way.

In this paper, we present a relational extension of the differential dynamic logic based on time stretching of dynamics. This reparametrization enables us to enforce that comparisons between two systems occur when certain conditions are satisfied, for example when two cars are passing through the same position. While such reparametrizations can be thought of as stretching or compressing time for one of the dynamics, we also show they can be conducted by a transformation of the dynamics themselves, based on Lie derivatives. We call this process synchronizing the dynamics (Definition 19), and it leads us to a new dL proof rule, the (Sync) rule (Theorem 24). We implemented the new rule in the KeYmaera X tool and use our extension to demonstrate several nontrivial relational properties of dynamical systems.

In the future, we think it would be interesting to combine our relational logic with orthogonal relational extensions of dL [14] which focus on refinement relations with varying levels of nondeterminism. We also hinted in our last case study that it is possible to synchronize wider classes of hybrid programs than just two differential dynamics. We also think that the level of automated proof search available in KeYmaera X may enable the automatic detection of monotonic properties in product lines. This may be useful in industry both to provide sanity checks on formalized models of products, as well as enabling strong guarantees to be more easily obtained for those models.

Modeling in Event-B: System and Software Engineering

A relational logic for higher-order programs

Probabilistic Relational Reasoning via Metrics

Simple relational correctness proofs for static analyses and program transformations

Modelling and Refining Hybrid Systems in Event-B and Rodin

Ordinary Differential Equations with Applications

Formal Approaches to Software Testing and Runtime Verification, First Combined International Workshops, FATES 2006 and RV

Approximate Bisimulation: A Bridge Between Computer Science and Control Theory

Dynamic Logic

Exercises in Nonstandard Static Analysis of Hybrid Systems

Deductive Verification of Hybrid Control Systems Modeled in Simulink with KeYmaera X

Sur l'application de la méthode des approximations successives aux equations différentielles ordinaires du premier ordre

Differential Refinement Logic

The KeYmaera X Proof IDE -Concepts on Usability in Hybrid Systems Theorem Proving

KeYmaera homepage

Differential Dynamic Logic for Hybrid Systems

The Complete Proof Theory of Hybrid Systems

A Complete Uniform Substitution Calculus for Differential Dynamic Logic

Logical Foundations of Cyber-Physical Systems

Differential Equation Axiomatization: The Impressive Power of Differential Ghosts

Non-standard analysis

Programming with Infinitesimals: A While-Language for Hybrid System Modeling

Hyperstream processing systems: nonstandard modeling of continuous-time signals

Ranking and Repulsing Supermartingales for Reachability in Probabilistic Programs

), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use