handout.dvi

Size: px

Start display at page:

Download "handout.dvi"

さあしゃももき
5 years ago
Views:

1 ichiro (formal verification, formal methods) [3] 2 theorem prover proof assistant PVSIsabell/HOLCoq Kripke M ϕ M ϕ M = ϕ model checker M ϕ M ϕ M M ϕ state explosion 1

2 1.1 ( ) P, NP, [5] NASA *1 specification modal logic formula Kripke Kripke model 1.2 SPIN model checkermcrl2prismuppaal 2 LTLCTLCTL K 2.1 syntax AP p AP atomic formula 2.1 ( ) p AP = p ϕ = ϕ ϕ ψ = ϕ ψ, ϕ ψ, ϕ ψ,,, *1 2

3 ϕ ϕ ϕ ψ ϕ ψ ϕ ψ ϕ ψ ϕ ψ ϕ ψ 2.2 ϕ ψ ξ (ϕ ψ) ξ ϕ (ψ ξ) semantics *2 ϕ p AP AP V 2.3 AP V AP AP {, } 2.4 AP V AP V = ϕ V = ϕ ϕ V V = p (p AP) p V V = ϕ V = ϕ V = ϕ ψ V = ϕ V = ψ V = ϕ ψ V = ϕ V = ψ V = ϕ ψ V = ϕ V = ψ 2.5 V = ϕ ϕ ψ ϕ ψ 2.6 = = 2.2 (ϕ ψ) ξ ϕ (ψ ξ) 2.7 AP ϕ ψ V AP V V = ϕ V = ψ. *2 syntax semantics 3

4 3 K LTLCTLCTL K K,,, ϕ ϕ ϕ ϕ ϕ modal logic C.I. Lewis C.H. Langford S. Kripke 3.1 syntax AP 3.1 (K- ) K- p AP = p K- ϕ K- = ϕ K- ϕ ψ K- = ϕ ψ, ϕ ψ, ϕ ψ K- ϕ K- = ϕ K- new!!,,,, ϕ ϕ 3.2 Kripke Kripke semantics Kripke ϕ 3.2 (Kripke ) Kripke Kripke frame 2 F = (S, R) S S s S state possible world R S R accessibility relation 3.3 (Kripke ) AP Kripke Kripke model 3 M = (S, R, V ) (S, R) Kripke 4

5 V V : S AP {, } V valuation function 3.4 R S S R S S. R s 1 s 2 (s 1, s 2 ) R s 1 s 2 s 1 s 2 (s 1, s 2 ) R s 1 Rs 2 p AP s S V (s, p) =, p s 2.3 Kripke M = (S, R, V ) V 2.4 K- 3.5 AP Kripke M = (S, R, V ) M, s = ϕ M, s = ϕ ϕ Kripke M s M, s = p (p AP) M, s = ϕ M, s = ϕ ψ M, s = ϕ ψ M, s = ϕ ψ M, s = ϕ V (s, p) = M, s = ϕ M, s = ϕ M, s = ψ M, s = ϕ M, s = ψ M, s = ϕ M, s = ψ srs s M, s = ϕ ϕ s s ϕ 3.6 K- ϕ Kripke F = (S, R) valid V : S AP {, } s S (S, R, V ), s = ϕ F = ϕ 3.7 S = {a, b, c}r = {(a, a), (b, b), (c, c), (a, b), (b, c)} p p 3.3 Kripke Kripke F = (S, R) ϕ Kripke (...) 5

6 (T) ϕ ϕ (4) ϕ ϕ (D) ϕ ϕ (B) ϕ ϕ (5) ϕ ϕ ϕ ϕ ϕ ϕ 3.8 T4DB5 T ϕ ϕ ϕ T p p (p q) (p q) axiom scheme 3.9 Kripke F F F T ϕ F = ϕ ϕ Kripke 3.10 Kripke F = (S, R) 1. T F 2. 4 F 3. D F 4. B F 5. 5 F R reflexive R transitive R serial R symmetric R Euclidean 3.11 S 2 R 1. R s S srs 2. R s, s, s S srs s Rs = srs 3. R s S srs s S 4. R s, s S srs = s Rs 6

7 5. R s, s, s S srs srs = s Rs 6. R preorder 7. R order R srs s Rs = s = s 8. R equivalence relation 3.12 p p Kripke 3.13 Kripke p p, p p, p p, p p ϕ ϕ epistemic logic ϕ ϕ T (4) ϕ ϕ (5 ) ϕ ϕ 4 positive introspection 5 negative introspection 3.15 Muddy children puzzle 4 Kripke Kripke R srs s s Kripke s S R Kripke 4.1 reactive concurrent component 7

8 λ Kripke 2 Kripke Kripke s 0 Rs 1, s 1 Rs 2,..., s n Rs 0 s 2 s, s srs srs non-determinism 2 S 1 S 2 S 1 S 2 S 1 S (Microwave) [2, Fig. 4.3] AP = {Start, Close, Heat, Error} open door Start Close Heat Error Start Close Heat Error start oven close door open door reset Start Close Heat Error Start Close Heat Error Start Close Heat Error open door close door start oven done warm up start cooking Start Close Heat Error Start Close Heat Error 8

9 5 LTLCTLCTL LTLCTLCTL CTL LTL CTL CTL CTL compuational tree logic LTL linear temporal logic 5.1 CTL syntax K 1 *3 CTL path quantifiers Eϕ there Exists Aϕ for All Xϕ next time Fϕ in the Futhre temporal operatorsgϕ Globally ϕuψ ψ ϕuntil ϕrψ ϕ ψ, Release 2 CTL (CTL ) CTL p AP = p ϕ, ψ = ϕ, ϕ ψ ϕ = Eϕ,Aϕ ϕ = ϕ ϕ, ψ = ϕ, ϕ ψ,xϕ,fϕ,gϕ, ϕuψ, ϕrψ 5.2 mutually inductive 5.2 CTL semantics CTL K Kripke Kripke M, s = ϕ Kripke M, π = ϕ 5.3 ( ) Kripke F = (S, R) π = s 0, s 1,... *3 2 9

10 s i s i+1 (s i, s i+1 ) R, for i = 0, 1,... π = s 0, s 1,... s i suffix π i π i = s i, s i+1, Kripke M = (S, R, V ) s S ϕ M, s = ϕ π ϕ M, π = ϕ 1 π i 1 CTL semantics M, s = p (p AP) M, s = ϕ M, s = ϕ ψ M, s = Eϕ M, s = Aϕ V (s, p) = M, s = ϕ M, s = ϕ M, s = ψ s π M, π = ϕ s π M, π = ϕ M, π = ϕ (ϕ ) π s M, s = ϕ M, π = ϕ M, π = ϕ ψ M, π = Xϕ M, π = Fϕ M, π = Gϕ M, π = ϕuψ M, π = ϕrψ M, π = ϕ M, π = ϕ M, π = ψ M, π 1 = ϕ k 0 M, π k = ϕ k 0 M, π k = ϕ k 0 M, π k = ψ i [0, k 1] M, π i = ϕ k 0 M, π k = ψ j [0, k 1] M, π j = ϕ 5.5 ϕ ψ Kripke M s M, s = ϕ M, s = ψ. ϕ ψ Kripke M π M, π = ϕ M, π = ψ. 10

11 ϕ = ψ 5.6 ϕrψ = ( ϕu ψ) Fϕ = TrueUϕ Gϕ = F ϕ Aϕ = E ϕ True p AP p p 5.3 CTL LTL CTL LTL CTL CTL X,F,G,U,R A,E (CTL ) CTL p AP = p ϕ, ψ = ϕ, ϕ ψ ϕ = Eϕ,Aϕ ϕ, ψ = Xϕ,Fϕ,Gϕ, ϕuψ, ϕrψ 5.8 CTL p AP = p ϕ, ψ = ϕ, ϕ ψ ϕ, ψ = AXϕ, EXϕ, AFϕ, EFϕ, AGϕ, EGϕ, A(ϕUψ),E(ϕUψ),A(ϕRψ),E(ϕRψ) CTL 10 AX, EX,..., A( R ), E( R ) CTL CTL 5.9 CTL 10 EX,EG,EU 3 CTL ϕ, ψ AXϕ = EX ϕ EFϕ = E(TrueUϕ) AGϕ = EF ϕ AFϕ = EG ϕ A(ϕUψ) = E( ψu( ϕ ψ)) EG ψ A(ϕRψ) = E( ϕu ψ) E(ϕRψ) = A( ϕu ψ) True

12 2 CTL M, s 0 = EFϕ M, s 0 = AFϕ M, s 0 = EGϕ M, s 0 = AGϕ 5.10 EFϕ,AFϕ,EGϕ,AGϕ semantics CTL EF(Start Ready)Start Ready AG(Req AFAck) acknowledgment AG(AFDeviceEnabled) DeviceEnabled AG(EFRestart) LTLlinear temporal logic LTL CTL 5.12 (LTL ) LTL p AP = p ϕ, ψ = ϕ, ϕ ψ,xϕ,fϕ,gϕ, ϕuψ, ϕrψ LTL ϕ Aϕ 6 CTL Kripke M = (S, R, V ) ϕ ϕ s {s S M, s = ϕ} CTL Kripke M 4.2 ϕ AG(Start AFHeat) 12

13 {s M, s = ϕ} OK! AP Kripke M = (S, R, V ) 3.3 S CTL ϕ p (p AP), ϕ, ϕ ψ, EXϕ, E(ϕUψ), EGϕ. ϕ S ϕ := {s S M, s = ϕ} ϕ = p AP S p V Kripke S p = {s S V (s, p) = }. ϕ = ψ χ *4 S ψ χ = S ψ S χ ϕ = ψ S ψ = S \ S ψ ϕ = EXψ ψ S EXψ = {s S (s, s ) R s S ψ s } ϕ = E(ψUχ) χ s S χ R ψ S E(ψUχ) 3 ϕ = EGψ CheckEU \ 6.4 CheckEU S E(ψUχ) *4 ϕ ϕ S ψ S χ 13

14 3 S ψ S χ S E(ψUχ) procedure CheckEU (S ψ, S χ ) T := S χ ; S E(ψUχ) := S χ ; while T do choose s T; T := T \ {s}; for all t such that R(t, s) do if t S E(ψUχ) and t S ψ then end if; end for all; end while; end procedure; S E(ψUχ) := S E(ψUχ) {t}; T := T {t}; 6.1 S EGψ M, s = EGψ π = s, s 1, s 2,... s i = ψ i [1, ) M = (S, R, V ) S 6.2 π S EGψ 6.5 Kripke Kripke = F = (S, R) strongly connected component F *5 C = (S, R ) C strongly connected s, s S s s C s 0, s 1,..., s m S such that s = s 0, (s 0, s 1 ) R,..., (s m 1, s m ) R, s m = s. 0 C maximal C C C C = C C *5 (S, R) S S R R (S, R ) 14

C non-trivial S 1 R = 4 http://en.wikipedia.org/wiki/strongly connected components R S ψ R ψ R ψ := R (S ψ S ψ ). 6.7 M, s = EGψ 2 1. s S ψ. 2. (S ψ, R ψ ) C s C t (S ψ, R ψ ) Proof.

15 C non-trivial S 1 R = 4 connected components R S ψ R ψ R ψ := R (S ψ S ψ ). 6.7 M, s = EGψ 2 1. s S ψ. 2. (S ψ, R ψ ) C s C t (S ψ, R ψ ) Proof.sketch[= ] M, s = EGψ s S ψ π π 6.2 π π π π = π 0 π 1, π 0 π 1 s π 1 s π 1 π 1 S π 1 S *6 C 6.9 C π 0 s C [ =] s t π 0 C t t π 1 π 0 π 1 π := π 0 π ω 1 s S ψ 6.7 S EGψ CheckEG 5 6 CTL *6 S R S 15

16 6.8 CTL O( ϕ ( S + R )) 5 S ψ S EGψ procedure CheckEG(S ψ ) SCC := {S ψ }; // Tarjan [1] T := C SCC {s s C}; S EGψ := T; while T do choose s T; T := T \ {s}; for all t S ψ such that R(t, s) do if t S E(ψUχ) then end if; end for all; end while; end procedure; S E(ψUχ) := S E(ψUχ) {t}; T := T {t}; C C C C 2. Kripke F = (S, R) S 2 = s = s C s, s C = Kripke M = (S, R, V ) s 0 M, s 0 = AG(Start AFHeat) 1. EX,EG,EU fairness 6.10 = 16

17 fairness constraint fair 7.1 tokena tokenb token returned token obtained tokena tokenb token obrained token returned tokena tokenb tokena A M = (S, R, V ) Kripke M fairness constraint *7 FC PS 2. M π = s 0, s 1,... inf(π) inf(π) := {s S i 0 s = s i } inf(π) π 3. M π = s 0, s 1,... FC fair P FC inf(π) P. 7.3 FC = { {s, s }, {s } } ( ) s s ( ) s { {s, s } i 0 si {s, s } } CTL CTLLTL semantics 7.4 ( ) Kripke M = (S, R, V ) FC ϕ M FC M, s = FC ϕ M, π = FC ϕ *7 17

18 M, s = FC p (p AP) M, s = FC Eϕ M, s = FC Aϕ V (s, p) = s fair π s fair π M, π = FC ϕ s fair π M, π = FC ϕ ϕ p,eϕ,aϕ 1 CTL Kripke M = (S, R, V ) FC CTL ϕ FC ϕ s {s S M, s = FC ϕ} CTL S ϕ := {s S M, s = FC ϕ} S ψ S EGψ 6.1 FC 7.5 M = (S, R, V ) Kripke FC Kripke (S, R) C fair P i FC C P i 7.6 M, s = FC EGψ 2 1. s S ψ M, s = FC ψ. 2. (S ψ, R ψ ) fair C s C t (S ψ, R ψ ) Proof. 6.7 S ψ S EGψ CheckEG 5 2 SCC := {S ψ fair } ϕ = ψ χ, ψ,exψ,e(ψuχ) S ϕ EGTrue Fair Fair := EGTrue, True M, s = FC Fair s fair π M, s = FC True s 2. p AP M, s = FC p M, s = p Fair 3. M, s = FC EXψ M, s = EX(ψ Fair) 18

19 4. M, s = FC E(ψUχ) M, s = E(ψU(χ Fair)) Proof. 34 ψ, χ CTL M, s = ϕ FC = { s s = Start Close Error } 8 LTL CTL LTL CTL symbolic model checking 9 [4] [2] [1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, [2] E.M. Clarke, O. Grumberg, and D.A. Peled. Model Checking. MIT Press, [3] Rance Cleaveland. THERE AND BACK AGAIN: Lessons learned on the way to the market. Invited talk at ETAPS 2007, [4].., [5] Revised in

20 10 notes for myself muddy children puzzle: common knowledge: at least one dirty child in a round: all the children are asked, their answers heard by all children. prove: a child who sees k dirty children says Yes I know at in round k, but no earlier. 20

21 p, q, r 1. p (q p) 2. (p (q r)) ((p q) (p r)) CTL A(ϕRψ) = E( ϕu ψ) 11.5 AP = {p, q, r} Kripke {s s = EF((p r) (p q)) } ϕ ψ (ϕ ψ) (ψ ϕ) ϕ ψ V (s 4, p) =, V (s 4, q) = V (s 4, r) = 21

( ) P, P P, P (negation, NOT) P ( ) P, Q, P Q, P Q 3, P Q (logical product, AND) P Q ( ) P, Q, P Q, P Q, P Q (logical sum, OR) P Q ( ) P, Q, P Q, ( P

( ) P, P P, P (negation, NOT) P ( ) P, Q, P Q, P Q 3, P Q (logical product, AND) P Q ( ) P, Q, P Q, P Q, P Q (logical sum, OR) P Q ( ) P, Q, P Q, ( P Advent Calendar 2018 @Fukuso Sutaro,,, ( ) Davidson, 5, 1 (quantification) (open sentence) 1,,,,,, 1 1 (propositional logic) (truth value) (proposition) (sentence) 2 (2-valued logic) 2, true false (truth