Interval Temporal Logic Model Checking

(1)

Interval Temporal Logic Model Checking Angelo Montanari

Interval Temporal Logic Model Checking

Angelo Montanari

Dept. of Mathematics, Computer Science, and Physics University of Udine, Italy

Temporal Logics: Satisfiability Checking, Model Checking, and Synthesis

University of Udine, Udine (Italy) January 20, 2017

(2)

Model checking

Model checking: the desired properties of a system are checked against a model of it

I themodelis usually a (finite) state-transition system

I system properties are specified by atemporal logic(LTL, CTL, and the like)

Distinctive features of model checking:

I exaustivecheck of all the possible behaviours

I fully automaticprocess

I acounterexampleis produced for a violated property

(3)

Point-based vs. interval-based model checking

Model checking is usuallypoint-based:

I properties express requirements over points (snapshots) of a computation (states of the state-transition system)

I they are specified by means of point-based temporal logics such as LTL and CTL

Interval-basedproperties express conditions on computation stretches, e.g., actions with duration, accomplishments, and temporal aggregations, instead of on computation states A lot of work has been done oninterval temporal logic(ITL) satisfiability checking.

Little work has been done onITL model checking(Bozzelli,

Lomuscio, Michaliszyn, Molinari, Montanari, Murano, Perelli, Peron, Sala)

(4)

Outline of the talk

I the model checking problem for interval temporal logics

I complexity results: the general picture

I the case of the interval temporal logic AABBE

(5)

The modeling of the system: Kripke structures

v0

∅

v2

p₂ v1

p₁ p^v³₃

v1

p1

v2

p2

v3

p3 r1

r2

r3

u1 u2 u3

r2

r3

r1 r3

r1

r2

A finite Kripke structure

I HS formulas are interpreted over (finite) state-transition systems, whose states are labeled with sets of proposition letters (Kripke structures)

I An interval is atrace(finite path) in a Kripke structure

(6)

HS: the modal logic of Allen’s interval relations

The thirteenbinary ordering relationsbetween two intervals on a linear order form the set of Allen’s interval relations

They give rise to corresponding unary modalities over frames where intervals are primitive entities:

I HS featuresa modality for any Allen ordering relationbetween pairs of intervals (except for equality)

Allen rel. HS Definition Example

x y

v z

meets h_Ai [x,y]RA[v,z] ⇐⇒ yv before h_Li [x,^y]RL[v,^z] ⇐⇒ y<^v started-by h_Bi [x,^y]RB[v,^z] ⇐⇒ x^v∧_z<^y finished-by h_Ei [x,y]RE[v,z] ⇐⇒ yz∧_x<v contains h_Di [x,y]RD[v,z] ⇐⇒ x<v∧_z<y overlaps h_Oi [x,^y]RO[v,^z] ⇐⇒ x<^v<^y<^z

All modalities can be expressed by means ofh_Ai_,h_Bi_,h_Ei_{, and} their transposed modalities only

(7)

HS semantics and model checking

Truth of a formulaψover a traceρof a Kripke structureK (_AP_,W, δ, µ,w0)defined by induction on the complexity ofψ:

I K, ρ |^{p iff p} ∈T

w ∈states(_ρ)µ(w), for any letter p∈ AP (homogeneity assumption);

I negation, disjunction, and conjunction are standard;

I K, ρ | h^Aiψiff there is a traceρ⁰^{s.t. lst}(_ρ)fst(_ρ⁰)and K, ρ⁰ | ψ;

I K, ρ | h^Biψiff there is a prefixρ⁰^ofρ^s.t. K, ρ⁰ | ψ^;

I K, ρ | h^Eiψiff there is a suffixρ⁰^ofρ ^s.t.K, ρ⁰ | ψ^;

I the semantic clauses forh_Ai, h^Bi_{, and}h_Eiare similar

Model Checking

K | ψ ⇐⇒ for all initial tracesρ^ofK, it holds thatK, ρ | ψ Possibly infinitely many traces!

(8)

Remark: HS state semantics (HS

_st

)

I According to the given semantics, HS modalities allow oneto branch both in the past and in the future

ϕ1

h_Biϕ1

ϕ1

h_Eiϕ1

ϕ1

h_Aiϕ1

ϕ2

h_Aiϕ2

(9)

An example: the Kripke structure K

Sched

v0

∅

v2

p₂

v1

p₁ p^v³₃

v1

p1

v2

p2

v3

p3 r₁

r₂

r₃

u₁ u₂ u₃

r₂

r₃

r₁ r₃

r₁ r₂

(10)

A short account of K

Sched

KSched models the behaviour of aschedulerserving 3 processes which are continuously requesting the use of a common resource

Initial state: v0 (no process is served in that state)

In vi and vi thei-th processis served (pi holds in those states) The schedulercannot serve the same process twicein two successive rounds:

I process i is served in state v_i, then, after “some time”, a transition ui from vi to vi is taken; subsequently, process i cannot be served again immediately, as v_i is not directly reachable from v_i

I a transition r_j, with j,^{i, from v}i to v_j is then taken and process j is served

It can beeasily generalisedto an arbitrary number of processes

(11)

Some meaningful properties to be checked over K

Sched Validity of properties over all legal computation intervals can be forced by modality[E](they are suffixes of at least one initial trace) Property 1: in any computation interval of length at least 4, at least 2 processes are witnessed (YES/no process can be executed twice in a row)

KSched | [E] hEi³> →(χ(p₁, p2)^∨χ(p₁, p3)^∨χ(p₂, p3))_, whereχ(p, q) hEi hAi p ∧ hEi hAi q

Property 2: in any computation interval of length at least 11, process 3 is executed at least once (NO/the scheduler can postpone the execution of a process ad libitum)

KSched 6| [E](hEi¹⁰> → hEi hAi p3)

Property 3: in any computation interval of length at least 6, all processes are witnessed (NO/the scheduler should be forced to execute them in a strictly periodic manner, which is not the case)

KSched 6| [E](hEi⁵→(hEi hAi p₁∧ hEi hAi p₂∧ hEi hAi p₃))

(12)

Model checking: the key notion of BE

_k

-descriptor

I TheBE-nesting depthof an HS formulaψ^(NestBE(_ψ)) is the maximum degree of nesting of modalities B and E inψ

I Two tracesρândρ⁰of a Kripke structureK ârek-equivalentif and only ifK, ρ | ψîffK, ρ⁰ | ψfor all HS-formulasψ^with NestBE(_ψ)^≤k

We provide a suitable tree representation for a trace, called a BE_k-descriptor

TheBE_k-descriptorfor a traceρ ^v0v₁..^vm−1v_m, denoted BE_k(_ρ), is defined as follows:

(v0, {v1, ..,vm−1},vm)

. . . . . . . . . . . . BEk−1(ρS2)

. . . . . . . . . BEk−1(ρS1)

. . . . . . . . . . . .

. . . . . . . . . BEk−1(ρP2)

. . . . . . . . . BEk−1(ρP1)

. . . . . . . . .

←descriptor element

↑ρ^P1, ρ^P2, . . .^prefixes^ofρ ↑ρ^S1, ρ^S2, . . .^suffixesofρ

Remark: the descriptor does not feature sibling isomorphic subtrees

(13)

Model checking: the key notion of BE

_k

-descriptor

I TheBE-nesting depthof an HS formulaψ^(NestBE(_ψ)) is the maximum degree of nesting of modalities B and E inψ

I Two tracesρândρ⁰of a Kripke structureK ârek-equivalentif and only ifK, ρ | ψîffK, ρ⁰ | ψfor all HS-formulasψ^with NestBE(_ψ)^≤k

We provide a suitable tree representation for a trace, called a BE_k-descriptor

TheBE_k-descriptorfor a traceρ ^v0v₁..^vm−1v_m, denoted BE_k(_ρ), is defined as follows:

(v0, {v1, ..,vm−1},vm)

. . . . . . . . . . . . BEk−1(ρS2)

. . . . . . . . . BEk−1(ρS1)

. . . . . . . . . . . .

. . . . . . . . . BEk−1(ρP2)

. . . . . . . . . BEk−1(ρP1)

. . . . . . . . .

←descriptor element

↑ρ^P1, ρ^P2, . . .^prefixes^ofρ ↑ρ^S1, ρ^S2, . . .^suffixesofρ

Remark: the descriptor does not feature sibling isomorphic subtrees

(14)

An example of a BE

₂

-descriptor

v0

p ^vq¹

The BE2-descriptor for the traceρ ^v0v₁v₀⁴v₁ (for the sake of readability, only the subtrees for prefixes are displayed)

(v0, {v0, v1}, v1)

(v0, {}, v1) (v0, {v1}, v0)

(v0, {}, v1) (v0, {v0, v1}, v0)

(v0, {}, v1) (v0, {v1}, v0)

(v0, {v0, v1}, v0)

(v0, {}, v1) (v0, {v1}, v0)

(v0, {v0, v1}, v0)

Remark: the subtree to the left is associated with both prefixes v0v1v₀³and v0v1v₀⁴(there are no sibling isomorphic subtrees in the descriptor)

(15)

An example of a BE

₂

-descriptor

v0

p ^vq¹

The BE2-descriptor for the traceρ ^v0v₁v₀⁴v₁ (for the sake of readability, only the subtrees for prefixes are displayed)

(v0, {v0, v1}, v1)

(v0, {}, v1) (v0, {v1}, v0)

(v0, {}, v1) (v0, {v0, v1}, v0)

(v0, {}, v1) (v0, {v1}, v0)

(v0, {v0, v1}, v0)

(v0, {}, v1) (v0, {v1}, v0)

(v0, {v0, v1}, v0)

Remark: the subtree to the left is associated with both prefixes v0v1v₀³and v0v1v₀⁴(there are no sibling isomorphic subtrees in the descriptor)

(16)

Decidability of model checking for full HS

FACT 1:For any Kripke structureK and any BE-nesting depth k≥0, the number of different BE_k-descriptors isfinite(and thus at least one descriptor has to be associated with infinitely many traces)

FACT 2:Two tracesρ^andρ⁰of a Kripke structureK described by thesame BE_kdescriptorarek-equivalent

Theorem

The model checking problem for full HS on finite Kripke structures is decidable (with a non-elementary algorithm)

A. Molinari, A. Montanari, A. Murano, G. Perelli, and A. Peron, Checking Interval Properties of Computations, Acta Informatica, Special Issue: Temporal Representation and Reasoning (TIME’14), Vol. 56, n. 6-8, October 2016, pp. 587-619

What about lower bounds?

(17)

Decidability of model checking for full HS

Theorem

A. Molinari, A. Montanari, A. Murano, G. Perelli, and A. Peron, Checking Interval Properties of Computations, Acta Informatica, Special Issue: Temporal Representation and Reasoning (TIME’14), Vol. 56, n. 6-8, October 2016, pp. 587-619

(18)

Decidability of model checking for full HS

Theorem

A. Molinari, A. Montanari, A. Murano, G. Perelli, and A. Peron, Checking Interval Properties of Computations, Acta Informatica, Special Issue:

Temporal Representation and Reasoning (TIME’14), Vol. 56, n. 6-8, October 2016, pp. 587-619

(19)

Decidability of model checking for full HS

Theorem

A. Molinari, A. Montanari, A. Murano, G. Perelli, and A. Peron, Checking Interval Properties of Computations, Acta Informatica, Special Issue:

Temporal Representation and Reasoning (TIME’14), Vol. 56, n. 6-8, October 2016, pp. 587-619

(20)

The logic BE

Theorem

The model checking problem for BE, over finite Kripke structures, is EXPSPACE-hard

L. Bozzelli, A. Molinari, A. Montanari, A. Peron, and P. Sala, Interval Temporal Logic Model Checking: The Border Between Good and Bad HS Fragments, IJCAR 2016

Proof (sketch): a polynomial-timereduction from a domino-tiling problemfor grids with rows of single exponential length

I for an instance I of the problem, we build a Kripke structureK^I and a BE formulaϕ^I in polynomial time

I there is an initial trace ofKÎ satisfyingϕÎ iff there is a tiling of I I KI | ¬ϕÎ iff there exists no tiling of I

(21)

BE hardness: encoding of the domino-tiling problem

Instance of the tiling problem: (C, ∆,ⁿ,^dinit,^dfinal), with C a finite set of colors and∆ ⊆C×_C×_C×C a set of tuples (c_B,^cL,^cT,^cR)

d^k₀ d₁^k d₂^k d₂^kn−2 d₂^kn−1

d^j+1_i d^j_i d_i^j−1 d_i−1^j d_i+1^j

d₂⁰ d₁⁰

d⁰₀ d₂⁰n−2 d₂⁰n−1

dInit

dFin

d_i^j c_i^jL c^j_iR

c^j_iB c^j_iT

d^j−1_i c_i^j−1T

String (interval) encodingof the problem

d₀⁰ 0 · · · 00 d⁰₁ 1 · · · 00 · · · d₂⁰n−1 1 · · · 11 $ d¹₀ 0 · · · 00 d₁¹ 1 · · · 00 · · · d¹₂n−1 1 · · · 11 $ column 0 column 1 column 2ⁿ− 1 column 0 column 1 column 2ⁿ− 1

row 0 row 1

(22)

The complexity picture

AABE PSPACE-complete B PSPACE-complete

E PSPACE-complete AAEE PSPACE-complete AABB PSPACE-complete

AA P^NP^[^O⁽^log²ⁿ^)]

P^NP^[^O⁽^{log n}^)]-hard

A, A P^NP^[^O⁽^log²ⁿ^)]

P^NP^[^O⁽^{log n}^)]-hard

AB, AE P^NP^[^O⁽^log²ⁿ^)]

P^NP^[^O⁽^{log n}^)]-hard AAB P^NP-complete AAE P^NP-complete

AB P^NP-complete AE P^NP-complete

h_Bi coNP-complete h_Ei coNP-complete

Prop coNP-complete AABBE, AAEBE EXPSPACE

PSPACE-hard

BE nonELEMENTARY EXPSPACE-hard full HS nonELEMENTARY

EXPSPACE-hard

hardness hardness

hardness

hardness upper-bound

hardness

hardness hardness

hardness

upper-bound hardness

upper-bound

(23)

Three main gaps to fill

The picture shows that there three main gaps to fill:

I full HS and BE are in betweennonELEMENTARYand EXPSPACE

I AABBE,AAEBE,ABBE,AEBE,ABBE,and AEBE are in betweenEXPSPACEandPSPACE

I A,^A,^AA,AB, and AE are in betweenP^NP[O⁽^log²ⁿ⁾^]and P^NP[O⁽^{log n}⁾^]

(24)

The logic AABBE

Let us consider the case of the logic AABBE, which is obtained from full HS (AABBEE) by removing modalityh_Ei

A high-level account of the solution:

I we can restrict our attention toprefixes(Bk-descriptors suffice)

I the size of the tree representation of B_k-descriptors is larger than necessary (redundancy) and it prevents their efficient exploitation in model checking algorithms

I atrace representativecan be chosen to represent a (possibly infinite) set of traces with the same B_k-descriptor

I abound, which depends on both the number|_W| of states of the Kripke structure and the B-nesting depth k, can be given to the length of trace representatives

(25)

The logic AABBE

(26)

The logic AABBE

(27)

The logic AABBE

(28)

The logic AABBE

(29)

Prefix-bisimilarity

Definition (Prefix-bisimilarity)

Two tracesρ^andρ⁰^areh-prefix bisimilarif the following conditions inductively hold:

I for h^0:

fst(_ρ)fst(_ρ⁰), lst(_ρ)lst(_ρ⁰), and states(_ρ)states(_ρ⁰)

I for h>0:

ρândρ⁰are 0-prefix bisimilar and for each proper prefixνôfρ (resp., proper prefixν⁰ôfρ⁰), there exists a proper prefixν⁰ ôf ρ⁰(resp., proper prefixνofρ) such thatνandν⁰are

(h−₁)-prefix bisimilar

I h-prefix bisimilarity is anequivalence relationover the set of traces

I h-prefix bisimilaritypropagates downwards

(30)

h-prefix bisimilarity ⇒ h-equivalence

Proposition

Let h≥_{0, and}ρandρ⁰be two h-prefix bisimilar traces of a Kripke structureK. For each AABBE formulaψ, with B-nesting ofψ ^less than or equal to h, it holds that

K, ρ | ψ ⇐⇒ K , ρ⁰ | ψ

(31)

Induced trace

Definition (Induced trace)

Letρbe a trace of length n of a Kripke structureK^{. A}trace induced byρ^{is a trace}π^ofK such that there exists an increasing

sequence ofρ-positions i1 < . . . <ik, where i11, ik n, and π ρ(i₁)^{· · ·}_ρ(i_k)

ρ

π

₁ ₂ ₃ ₄ ₅

1 2 3 4 5 6 7 8 9 10

π = ρ(1)ρ(4)ρ(5)ρ(7)ρ(10)

Ifπis induced byρ ⇒fst(_π)fst(_ρ), lst(_π)lst(_ρ), and

|π| ≤ |ρ|

(32)

Prefix-skeleton sampling

Definition (Prefix-skeleton sampling)

Letρbe a trace of a Kripke structureK (_AP_,W, δ, µ,^w0). Given twoρ-positions i and j, with i ≤_{j, the}prefix-skeleton

samplingofρ(i,^j)is theminimal set P ofρ-positions in the interval [i,^j]satisfying:

I i,^j ∈_P;

I for each state w ∈ W occurring alongρ(i+1,^j−₁), the minimal position k ∈ [i+1,^j−₁]such thatρ(k)w is in P

i j

w1 w1 w1 w1 w2 w1 w3 w1 w2 w3 w1 w3

ρ(i, j)

P ={i, i + 1, i + 4, i + 6, j}

(33)

h-prefix sampling

Definition (h-prefix sampling)

For each h≥_{1, the}h-prefix sampling ofρ^{is the}minimal set Ph of ρ^-positionsinductively satisfying the following conditions:

I for h^{1: P}1is the prefix-skeleton sampling ofρ^;

I for h>^1:

I P_h⊇ Ph−1and

I for all pairs of consecutive positions i, j in Ph−1, the prefix-skeleton sampling ofρ(i, j)is in P_h

Proposition

The h-prefix sampling P_hof (any)ρis such that |_P_h| ≤ (^|W| +2)^h

(34)

A small model (trace) result

Given a traceρ, we can derive another traceρ⁰, induced byρand h-prefix bisimilar toρ, such that|ρ⁰| ≤ (^|W| +2)^h+2 as follows:

1. we first compute the (h+1)-prefix sampling P_h+1 ofρ^; 2. then, for all pairs of consecutiveρ-positions i,^{j in P}h+1, we

consider a trace induced byρ(i,^j), with no repeated

occurrences of any state, except at most the first and last ones (hence no longer than(^|W| +2));

3. ρ⁰is just the ordered concatenation of all these traces ρ^andρ⁰can be proved to be h-prefix bisimilar, and thus

ρ⁰is indistinguishable fromρwith respect to the fulfilment of any formulaψ, with B-nesting ofψ(abbreviated NestB(_ψ))≤_h By the previous bound on|_P_h|, it holds that|ρ⁰| ≤ (^|W| +2)^h+2

(35)

A small model (trace) result

1. we first compute the(h+1)-prefix sampling P_h+1 ofρ^;

2. then, for all pairs of consecutiveρ-positions i,^{j in P}h+1, we consider a trace induced byρ(i,^j), with no repeated

(36)

A small model (trace) result

1. we first compute the(h+1)-prefix sampling P_h+1 ofρ^; 2. then, for all pairs of consecutiveρ-positions i,^{j in P}h+1, we

(37)

A small model (trace) result

3. ρ⁰is just the ordered concatenation of all these traces

ρ^andρ⁰can be proved to be h-prefix bisimilar, and thus

(38)

A small model (trace) result

(39)

An EXPSPACE model checking algorithm for AABBE

Algorithm 1ModCheck(_K_{, ψ})

1: h ← NestB(_ψ)

2: u ← New(Unravelling(_K_{, w}₀_{, h})) _/w₀initial state ofK 3: while u.hasMoreTracks() do

4: _ρ⁰← u.getNextTrack()

5: if Check(K, h, ψ, ρ⁰) 0 then return 0: “K , ρ⁰6| ψ”/Counterexample found

X

return 1: “K | ψ” /Model checking OK

X

L. Bozzelli, A. Molinari, A. Montanari, A. Peron, and P. Sala, Interval Temporal Logic Model Checking Based on Track Bisimilarity and Prefix Sampling, ICTCS 2016

(40)

PSPACE-hardness of AABBE model checking

PSPACE-hardnessof the model checking problem for the fragment B (and thus for AABBE) can be proved by a reduction from the QBF problem

Theorem

The model checking problem for B, and thus for AABBE, over finite Kripke structures is PSPACE-hard

AABBE model checking is thus in between PSPACE and EXPSPACE (remind: BE model checking is EXPSPACE-hard)

A. Molinari, A. Montanari, A. Peron, and P. Sala, Model Checking Well-Behaved Fragments of HS: The (Almost) Final Picture, KR 2016

(41)

Latest developments

I Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison

I Model Checking Complex Systems against ITL Specifications with Regular Expressions