• Non ci sono risultati.

# Formal Methods Module II: Model Checking Ch. 09: Timed and Hybrid Systems

N/A
N/A
Protected

Condividi "Formal Methods Module II: Model Checking Ch. 09: Timed and Hybrid Systems"

Copied!
173
0
0

Testo completo

(1)

## Formal Methods Module II: Model Checking Ch. 09: Timed and Hybrid Systems

### Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2021/

Teaching assistant:Giuseppe Spallitta– giuseppe.spallitta@unitn.it

### M.S. in Computer Science, Mathematics, & Artificial Intelligence Systems Academic year 2020-2021

last update: Thursday 27thMay, 2021, 13:27

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti, M. Di Natale, P. Pandya, M. Pistore, M. Roveri, C. Tinelli, and S.Tonetta, who detain its copyright. Some exampes displayed in these slides are taken from [Clarke, Grunberg & Peled, “Model Checking”, MIT Press], and their copyright is

detained by the authors. All the other material is copyrighted by Roberto Sebastiani. Every commercial use of this material is strictly forbidden by the copyright laws without the authorization of the authors. No copy of these slides can be

displayed in public without containing this copyright notice.

(2)

1

2

3

4

5

6

2 / 101

(3)

1

2

3

4

5

6

(4)

4 / 101

(5)

(6)

6 / 101

(7)

(8)

6 / 101

(9)

(10)

1

2

3

4

5

6

7 / 101

(11)

1

2

3

4

5

6

(12)

9 / 101

(13)

(14)

10 / 101

(15)

(16)

1

2

+

a l1

l2

12 / 101

(17)

## Timed Automata

1

2

+

### Invariants: (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N set of clock comparisons against integers bounds ensure progress

(x ≥ 4) (y ≤ 2) a

y := 0 l1

l2

(18)

## Timed Automata

1

2

+

### Invariants : (x ./ C) s.t. ./ ∈ {≤, <, ≥, >}, C ∈ N set of clock comparisons against integers bounds ensure progress

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

12 / 101

(19)

## Timed Automata: States and Transitions

i

1

2

2

i

a j

0

0

1

a 2

1

a 2

1

1

a 2

2

1

a 2

1

a 2

2

i

δ i

1

2 1

1

3 1

1

### )

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

(20)

## Timed Automata: Formal Syntax

0

0

X

0

0

### : target location

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

14 / 101

(21)

## Clock constraints and clock interpretations

### A state for a timed automaton is a pair hl, νi, where l is a location and ν is a clock interpretation

(x ≥ 4) (y ≤ 2) a

y := 0 l1

(x ≤ 5)

l2

(x > 4) (y ≤ 3)

(22)

k

k

16 / 101

(23)

0

1

1

2

(24)

A def

0

0

0

+

18 / 101

(25)

(26)

1.2

19 / 101

(27)

1.2

a 0

1.2+a

0

(28)

1.2

a 0

1.2+a

0

19 / 101

(29)

push push

click

3.5

push

3.14

push

3

2.86

click

(30)

21 / 101

(31)

1def

1

01

1

1

1

1

1

2def

2

02

2

2

2

2

2

1

2def

1

2

01

02

1

2

1

2

1

1

2

2

1

2

1

2

(32)

1

def

2def

23 / 101

(33)

(34)

2

2

25 / 101

(35)

(36)

1

2

3

4

5

6

27 / 101

(37)

1

2

3

4

5

6

(38)

F

F

A

29 / 101

(39)

A

(40)

31 / 101

(41)

(42)

A

+

A

33 / 101

(43)

A

A

A

0

1.2 0

a 1

0.7 1

b

2

A

0

1.2+a

1

0.7+b

2

A

0

a 1

b 2

(44)

A

A

35 / 101

(45)

F

F

(46)

## Stable Quotient: Intuitive example

A

1

2

3

4

1

2

3

4

### = 3min

All executions with distinct values of δi are bisimilar

37 / 101

(47)

1

2

3

4

5

6

(48)

x

x

0

0

0

0

0

x

0

x

0

y

0

0

0

x

0

39 / 101

(49)

## Conditions: C1 + C2 + C3

Cx

x y

Cy

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν0(x )c

### or

bν(x)c, bν0(x )c ≥ Cx

C2:

0

x

0

y

### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν0(x)) ≤ fr(ν0(y))

C3:

0

x

### ,

fr(ν(x)) = 0 iff fr(ν0(x)) = 0

(50)

## Conditions: C1 + C2 + C3

Cx

x y

Cy

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν0(x )c

### or

bν(x)c, bν0(x )c ≥ Cx

C2:

0

x

0

y

### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν0(x)) ≤ fr(ν0(y))

C3:

0

x

### ,

fr(ν(x)) = 0 iff fr(ν0(x)) = 0

40 / 101

(51)

## Conditions: C1 + C2 + C3

Cx

x y

Cy

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν0(x )c

### or

bν(x)c, bν0(x )c ≥ Cx

C2:

0

x

0

y

### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν0(x)) ≤ fr(ν0(y))

C3:

0

x

### ,

fr(ν(x)) = 0 iff fr(ν0(x)) = 0

(52)

## Conditions: C1 + C2 + C3

Cx

x y

Cy

1 2 3 4

1 2 3

0

C1:

### For every clock x , either

bν(x)c = bν0(x )c

### or

bν(x)c, bν0(x )c ≥ Cx

C2:

0

x

0

y

### ,

fr(ν(x)) ≤ fr(ν(y)) iff fr(ν0(x)) ≤ fr(ν0(y))

C3:

0

x

### ,

fr(ν(x)) = 0 iff fr(ν0(x)) = 0

40 / 101

(53)

Cx

x y

Cy

1 2 3 4

1 2 3

0

0

i

i

i

i

j

i

j

i

j

xi

(54)

42 / 101

(55)

a 0

0

0

0

0

0

0

a 0

0

+

0

+

0

(56)

x

y

44 / 101

(57)

x

y

(58)

x

y

44 / 101

(59)

x

y

(60)

x

y

44 / 101

(61)

x

y

(62)

x

y

44 / 101

(63)

x

y

(64)

x

y

44 / 101

(65)

x

y

(66)

x

y

44 / 101

(67)

x

y

(68)

x

y

44 / 101

(69)

x

y

(70)

x

y

44 / 101

(71)

x

y

(72)

x

y

44 / 101

(73)

k

x ∈X

x

def

x

x

y

2

(74)

F

F

F

46 / 101

(75)

(76)

x

48 / 101

(77)

1

2

3

4

5

6

(78)

i

i

j

x y

50 / 101

(79)

def

0

0

0def

0

a 0

def

0

def

0

(80)

def

0

0

0

def

def

def

52 / 101

(81)

=⇒ Final!

def

(82)

=⇒ Final!

ϕ

def

53 / 101

(83)

## Zone Automata: Symbolic Transitions (cont.)

### Intersection with invariant φ: values allowed

to enter the location

=⇒ Final!

ϕ φ

def

(84)

=⇒ Final!

def

53 / 101

(85)

=⇒ Final!

def

(86)

## Zone Automata: Symbolic Transitions (cont.)

### Projection to infinity: values allowed to enter the location, after waiting unbounded time Intersection with invariant φ: values allowed

to enter the location, after waiting a legal amount of time

=⇒ Final!

φ

def

53 / 101

(87)

=⇒ Final!

def

(88)

## Zone Automata: Symbolic Transitions (cont.)

### Intersection with guard ψ: values allowed to

enter the location, after waiting a legal amount of time, from which the switch can be shot

=⇒ Final!

ψ

def

53 / 101

(89)

=⇒ Final!

def

(90)

=⇒ Final!

def

53 / 101

(91)

=⇒ Final!

def

(92)

=⇒ Final!

def

53 / 101

(93)

## Example: Zone Automata, Symbolic Transitions

### Initial zone: (x ≥ 0) ∧ (x ≤ 2) ∧

(y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

def

=⇒ Final!

(94)

## Example: Zone Automata, Symbolic Transitions

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

def

=⇒ Final!

ϕ

54 / 101

(95)

## Example: Zone Automata, Symbolic Transitions

### (y ≥ 0) ∧ (y ≤ 3) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with invariant φ : (y ≥ 1) ∧ (y ≤ 5)

=⇒ (x ≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2)

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

def

=⇒ Final!

ϕ φ

(96)

## Example: Zone Automata, Symbolic Transitions

### Projection to infinity:

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

def

=⇒ Final!

54 / 101

(97)

def

=⇒ Final!

(98)

## Example: Zone Automata, Symbolic Transitions

### Intersection with invariant φ: (y ≥ 1) ∧ (y ≤ 5)

=⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

def

=⇒ Final!

φ

54 / 101

(99)

def

=⇒ Final!

(100)

## Example: Zone Automata, Symbolic Transitions

### =⇒ (x ≥ 0) ∧ (y ≥ 1) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2) Intersection with guard ψ : (y ≥ 4)

=⇒ (y ≥ 4) ∧ (y ≤ 5) ∧ (y − x ≥ −1) ∧ (y − x ≤ 2)

def

=⇒ Final!

ψ

54 / 101

(101)

def

=⇒ Final!

(102)

## Example: Zone Automata, Symbolic Transitions

def

### = {y := 0}

=⇒ (x ≥ 2) ∧ (x ≤ 6) ∧ (y ≥ 0) ∧ (y ≤ 0)

=⇒ Final!

54 / 101

(103)

def

=⇒ Final!

(104)

def

=⇒ Final!

54 / 101

(105)

def

def

0

0

0

(106)

F

def

0

i

i

0

F

0

0

56 / 101

(107)

(108)

## Difference-bound matrices, DBMs

0def

i

i

0

1

2

1

2

1

2

### ≥ 0)

(x0− x1≤ 0) ∧(x0− x2<0) ∧(x1− x0<2) ∧(x2− x0<1) ∧(x2− x1≤ 0)

58 / 101

(109)

## Difference-bound matrices, DBMs

0def

i

i

0

1

2

1

2

1

2

### ≥ 0)

(x0− x1≤ 0) ∧(x0− x2<0) ∧(x1− x0<2) ∧(x2− x0<1) ∧(x2− x1≤ 0)

(110)

0def

i

i

0

1

2

1

2

1

2

0

1

0

2

1

0

2

0

2

1

58 / 101

(111)

0def

i

i

0

1

2

1

2

1

2

(x0− x1≤ 0)

0− x2<0)

1

0

2

0

2− x1≤ 0)

(112)

i

j

i

k

1

k

j

2

1

2

1

2

59 / 101

(113)

(114)

61 / 101

(115)

(116)

63 / 101

(117)

## Outline

1

2

3

4

5

6

### Exercises

Riferimenti

Documenti correlati

3 Symbolic Reachability for Timed Systems Making the state space finite.. Region automata

5 Symbolic Reachability for Hybrid Systems Multi-Rate and Rectangular Hybrid Automata Linear Hybrid

=⇒ Substantially, add one initial state, move labels from states to incoming edges, set fair states as accepting states.. The Main Problem of M.C.: State

=⇒ It is reasonable enough to assume the protocol suitable under the condition that each user is infinitely often outside the restroom.. Such a condition is called

Various techniques: Bounded Model Checking (BMC), K-induction, Interpolant-based, IC3/PDR,..... SAT-based Bounded Model Checking

satisfiability of the Boolean formulas is checked by a SAT solver can manage complex formulae on several 100K variables returns satisfying assignment (i.e., a counter-example)

Different approaches, such as the introduction of noise in hybrid automata [9] and the use of approx- imated semantics (ε-semantics [5]), have been proposed with the aim of

The derivative design approach to be eﬀective in the industry development process has to be sup- ported by methodologies and tools that allow evaluation of “oﬀ the shelf”