Development for Verification Tool Guaranteeing Reliability of Rail Signal Control Protocol

(1)

Development for Verification Tool Guaranteeing Reliability

of Rail Signal Control Protocol

(2)

프 로 토 콜 검 정 을 위 한 Modal Mu-Calculus 표 현 식

1. Safety Check 식 (Deadlock 및 Livelock) :

νZ. (µY.A ∨( <-> tt ∧ [-]Y)) ∧ [-]Z 단, A={S

₀

}

2. State Reachability Check 식 :

νZ. (µY.A ∨( <action

₂

> tt ∧ [action

₁

]Y)) ∧ [-]Z 단, A={state}

3. Action Reachability Check 식 :

νZ. [action

₁

](µY. <action

₃

> tt ∧ [action

₂

]Y) ∧ [-]Z

프 로 토 콜 검 정 을 위 한 Modal Mu-Calculus 표 현 식

1. Safety Check 식 (Deadlock 및 Livelock) :

νZ. (µY.A ∨( <-> tt ∧ [-]Y)) ∧ [-]Z 단, A={S

₀

}

2. State Reachability Check 식 :

νZ. (µY.A ∨( <action

₂

> tt ∧ [action

₁

]Y)) ∧ [-]Z 단, A={state}

3. Action Reachability Check 식 :

νZ. [action

₁

](µY. <action

₃

> tt ∧ [action

₂

]Y) ∧ [-]Z

Modal M u-calculus

논 리 식

Max block, Min block

생 성

Edge-labeled directed Graph

생성

Bit-vector, Counter, M array 생 성

초 기 화 및 갱신 알고리

즘 적 용

CTC SCADA

그림 4.

S

0

S

2

S

4

S

3

S

5

a

5

S

1

a

8

a

4

a

3

a

2

a

1

a

6

a

7

S

1

: Ack_await S

3

: Resp_await S

5

: Ack_await S

0

: Idle

S

2

: T

1

=P

1

S

4

: T

2

=P

2

a

2

: ack a

4

: train_state_msg a

6

: operate_T

2

_timer a

8

: ack

a

1

: TCP_con_req a

3

: operate_T

1

_timer a

5

: ack

a

7

: SCADA_state_msg

(3)

Protocol Verification Tool

InitDeadlock &

Livelock

InitReachability State

InitReachability

Action Liveness Check Determinist Check

Initialize

Solve

Deadlock &

Livelock check

Reachability State check C.initialize

X.initialize B.graph

Reachability Action check

LTS file

Choice = ?

(4)

그림 6.

BitArray(X)

시 작

i<nbState? No

종 료 if(X[i][5]==0)?

set+=i Yes Yes

i++ No return set

그림 7. Livelock Check

Yes BitArray(X)

시작

i<nbState? No

종료 if( C[i][3]==1 &&

C[i][4]==1)?

return set Yes

i++

return set No

B i t A r r a y ( X )

시 작

i < n b S t a t e ? N o

종 료 i f ( X [ i ] [ 2 ] = = 1 & &

X [ i ] [ 4 ] = = 1 & &

X [ i ] [ 5 ] = = 1 ) ?

s e t + = i Y e s Y e s i + +

r e t u r n s e t N o

i f ( C [ i ] [ 3 ] = = 1 ) ?

s e t + = i Y e s N o

그림 9. Reachability Action Check부모듈의 procedure

BitArray(X)

시 작

i<nbState? N o

종 료 if(X[i][3]==1)?

Yes

i++ N o return set

set2+=i Yes

j<nbState?

if(C[j][1]==1 &&

!(s2->belong(j)))?

Yes

S e t 1 + = j Yes

j + +

N o

(5)

그림 10. Liveness

시작

s′==s

0

? No

Yes s=s′

LTS(L) choice User

s=s

0

Display allaction(begin=s, end=s′) s— allactionàs′

종료

그림 11. Determinist

시 작

LT S ( L )

O K : = t r u e , i , j : = 0

i < L . n b T r a n s ?

j < L . n b T r a n s ?

T r a n s [ i ] 와 T r a n s [ j ] 가 같 은 지 ?

j : = i + 1

j + +

r e t u r n O K 종 료

N o

Y e s

N o U s e r c h o i c e

O K : = f a l s e A c t i o n : = T r a n s [ j ]

S t a t e : = j i + +

B

1

≡min{X

1

= X

2

∨ X

³

X

2

= A X

3

= X

4

∧ X

⁵

X

4

= [-]X

1

X

5

= <->X

6

X

6

= tt}

B

2

≡max{X

7

= X

1

∧ X

⁸

X

8

= [-]X

7

}

X

₁

X

₈

X

₂

X

₃

X

₄

X

₅

X

₆

X

₇

[-]

∧ ∧

∧ [-] ∧

<->

∨ ∨

it-vector

( 14) .

(6)

X X

1

X

2

X

3

X

4

X

5

X

6

X

7

X

8

C X

3

X

4

S

0

1 1 1 1 1 1 1 1 S

0

0 0

S1 1 0 1 1 1 1 1 1 S

1

0 0

S2 1 0 1 1 1 1 1 1 S

2

0 0

S3 1 0 1 1 1 1 1 1 S

3

0 0

S4 1 0 1 1 1 1 1 1 S

4

0 0

S5 1 0 1 1 1 1 1 1 S

5

0 0

M[1]=< >

M[2]=< >

X X

1

X

2

X

3

X

4

X

5

X

6

X

7

X

8

C X

3

X

4

S

0

0 1 0 0 0 1 1 1 S

0

2 3

S

1

0 0 0 0 0 1 1 1 S

1

2 1

S

2

0 0 0 0 0 1 1 1 S

2

2 1

S

3

0 0 0 0 0 1 1 1 S

3

2 1

S

3

0 0 0 0 0 1 1 1 S

4

2 1

S

5

0 0 0 0 0 1 1 1 S

5

2 1

M[1]=<<S

0

,X

2

>, <S

0

,X

6

>, <S

1

,X

6

>, <S

2

,X

6

>, <S

3

,X

6

>, <S

4

,X

6

>, <S

5

,X

6

>>

M[2]=< >

입력 출력

type 2 LTS

Modal Mu-Calculus .

,

.

, (CTC) SCADA

type 2 .

.

(discrete time)

.

(7)