2.1 ATL 모델 체킹 문제
그림. 1. ATL formula의 semantics
Fig. 1. The semantics of ATL formula
ATL(Alternating-time Temporal Logic) 모델 체킹은 정형 검증(formal verification) 기법 중에 하나로서,
주어진 모델이 사용자가 검증하고자하는 property를 만족하는지를 자동적으로 검증하는 기술이다. ATL 모델체킹에서는 검증하고자 하는 시스템은
game structure(8,15)로 나타내고, property는 ATL formula(8)로 나타낸다. 이 절에서는 ATL 모델 체킹 문제에 대해 자세히 설명한다. 이 문제 정의는 ATL과 game structure에 대한 정의를 필요로
하기 때문에 ATL의 정의부터 설명하기로 한다.
ATL의 syntax는 아래와 같다. 여기서, Π는 atomic proposition들의 집합이며, Σ는 player들의 집합이다.
(1) 모든 atomic proposition p∈Π는 ATL formula이다.
(2) φ1과 φ2가 ATL formula이면, ¬φ1, φ1∨φ2, φ1∧φ2도 역시 ATL formula이다.
(3) A⊆Σ가 player들의 집합이고, φ1과 φ2가 ATL formula이면, ≪A≫Xφ1, ≪A≫Gφ1, ≪A≫Fφ1, ≪A≫φ1Uφ2도 ATL
formula이다.
ATL 모델 체킹에서 검증 대상 모델을 표현하는 game structure는 다음과 같이 S=(k, Q, Π, π, d, δ)로 나타낼 수 있다.
∙ k는 player의 개수이다. 그리고, 각각의 player들은 해당 숫자로 나타내며, player들의 집합인 Σ는 {1, 2, ..., k}가
된다.
∙ Q는 state들의 집합이며, intial state들의 집합은 Q0로 나타낸다.
∙ Π는 atomic proposition들의 집합이다.
∙ π: Q→2Π는 labeling 함수로서, 각각의 state q∈Q에서 true인 atomic proposition들의 집합 π(q)⊆2Π을 나타낸다.
∙ 각 player a∈{1, 2, ..., k}와 state q∈Q에 대해서, 자연수 da(q)≥1는 해당 player a가 state q에서 가능한
move의 개수를 의미한다.
∙ 각 state q∈Q와 move 벡터 (m1, m2, ..., mk)에 대해서, δ(q, m1, m2, ..., mk)는 각각의 player a들이
state q에서 move ma를 선택했을 때의 다음 state를 나타내며, 이러한 함수 δ를 transition function이라고 한다.
그림 1은 game structure에 기반한 ATL formula의 semantics를 정의한다. Game structure S=(k, Q, Π, π,
d, δ)와 state q∈Q, ATL formula φ가 주어졌을 때, 만약 game structure S의 state q에서 ATL formula
φ를 만족하는 경우, S, q ⊧φ라고 한다. 그리고, S가 명백한 경우, q ⊧φ로 표시할 수 있다. 그리고, S의 모든 initial state
q0∈Q0에 대해서, q0 ⊧φ인 경우, S ⊧φ라고 한다. 최종적으로, Game structure S=(k, Q, Π, π, d, δ)와 ATL
formula φ가 주어졌을 때, 주어진 S와 φ에 대해서 S ⊧φ인지를 검사하는 문제가 ATL 모델 체킹 문제이다.
2.2 ATL 모델 체킹 예제
그림 2는 본 논문에서 이용하는 ATL 모델 체킹 기법을 설명하기 위한 예제를 보여주고 있다. 이 예제에서는 두 개의 프로세스 px와 py가 존재한다. 프로세스
px는 Boolean 변수 x를 컨트롤하며, 프로세스 py는 Boolean 변수 y를 컨트롤한다. 즉, x의 값이 false인 경우, px는 (1)
x의 값을 그대로 유지하거나 (2) true로 변경할 수 있다. 하지만, x가 true인 경우에는 px가 x의 값을 변경할 수는 없고 true로 유지할
수밖에 없다. 비슷하게, y의 값이 false인 경우, py는 (1) y의 값을 그대로 유지하거나 (2) true로 변경할 수 있다. 하지만, y가
true인 경우에는 py가 y의 값을 변경할 수는 없고 true로 유지할 수밖에 없다.
그림. 2. ATL 모델 체킹 예제
Fig. 2. ATL model checking example
이 예제에서 ≪px≫F (x=true)라는 ATL formula를 생각해 보자. 이 ATL formula는 “px는 다른 player들이 어떤 수를
쓰더라도, 변수의 x의 값을 미래 어느 순간에는 true로 만들 수 있다”라는 property를 의미한다. 이 ATL formula는 intial
state인 q0에서 만족한다. 왜냐하면, state q0에서 프로세스 px가 변수 x의 값을 true로 변경하는 move를 선택하기만 하면, 프로세스
py가 어떤 move를 선택하건 간에 x의 값은 true가 되기 때문이다. 반면에 ≪py≫X (x=y)라는 ATL formula는 initial state
q0에서 만족하지 않는다. (참고로 이 formula는 “py는 다른 player들이 어떤 수를 선택하더라도, 모든 next state에서 x와 y의
값을 같게 만들 수 있다”라는 property를 의미한다.) 왜냐하면, state q0에서 (1) py가 y의 값을 유지하는 경우는 px가 x의 값을
true로 만들어서 x≠y를 만들 수 있고, (2) py가 y의 값을 변경하는 경우에는 px가 x의 값을 false로 유지할 수 있어서 x≠y를 만들
수 있기 때문이다. 즉, 위의 예제를 나타내는 game structure를 S라고 할 때, S⊨≪px≫F (x=true)이지만, S⊭≪py≫X (x=y)이다.