Game による検証 (µ 計算の場合)

µ計算(様相µ計算)は時相を含む論理に基づく検証や合成の基本的な形式化理論であり、

モデル検査などでもちられているCTL(計算木論理)を包含する体系である。モデル検査 は、モデル(M)とプロパティ(P)の間の充足性Game(P に対してMを充足することを示 そうとするPlayerIと、逆のPlayer2の間のGame)として形式化できる。M, P がラベル付 遷移システム(LTS)としてモデル化できる場合は、直積(M ⊗P)をGameのArenaとし て計算してMとPの間のGameとして形式化できることが知られている。

ここではプロパティ(P)が様相論理で記述される場合のモデル検査、特にµ計算における モデル検査のGameの理論による解法の概要をStaring[27, 25]による形式化に沿って示す。

最初にµ計算の文法と意味を定義する。

µ計算における式とは、P ropを命題定数、Actをアクション、V arを変数の集合である とするとき以下の文法にて定義される、

F :=tt|f f |P rop | ¬P rop|V ar |F ∨F |F ∧F | hActiF |[Act]F |µV ar.F |νV ar.F 式は遷移システムにより解釈される。ここで遷移システムとはM =hS,{R_a}a∈Act, σiに より構成され、Sは状態の集合、R_a =S×Sは遷移関係σ :P rop → P(S)は命題定数に 対してこれが成立する状態の集合を割り当てる関数であるとする(ここでP(S)はSの集 合の集合=べき集合2^Sを意味する)。

値割り当て → P は変数に対して状態の集合を割り当てる関数である。

遷移システムM と変数への値割り当てV :V ar → P(S)に対して式ψが真となる状態 の集合をkψk^M_V を以下のように定義する

kttk^M_V =S , kf fk^M_V ={}

kpk^M_V =σ(p) , k¬pk^M_V =S−σ(p) kXk^M_V = V(X)

khaiαk^M_V = {s:∃s⁰.R_a(s, s⁰)∧s⁰ ∈ kαk^M_V } k[a]αk^M_V = {s:∀s⁰.R_a(s, s⁰)∧s⁰ ∈ kαk^M_V } kµX.α(X)k^MV = ∩

{S⁰ ⊂S :kαk^M_V[S0/X] ⊂S⁰} kνX.α(X)k^MV = ∪

{S⁰ ⊂S :S⁰ ⊂ kαk^M_V[S0/X]}

ここでV [S/X]とは値割付V においてq 6=Xの場合はV [S/X] (q) = V(q) q =Xの場 合はV [S/X] (X) = Sであるものを示す。

そしてs∈ kαk^M(sにおいてはMを鑑みるとαは真であるというほどの意味)の代わり にM, s|=αと記述することとする

µ計算におけるモデル検査問題とは、与えられたαと有限遷移システムMおよび状態 s₀において、M, s₀ |=αであるかどうかを決定する処理である。

また以降では演算[],hiに現れるActの部分集合の簡易表現として、−KによりAct−K

（Kの補集合)を表すものとする。特別なケースとして−はAct− ∅=Actを表す。

µ計算によるプロパティ例

safety 悪い状態に陥らないことを示す。悪い状態のcomplementがΦであるとすると νZ.Φ∧[−]Z

としてあらわせる。悪いアクションが発生しないという見方をするならば、

νZ.[K] ff∧[−]Z としてあらわせる。

liveness ある良い性質がいつかは成立することを示す。Φを良い良い状態を表すとすると µZ.Φ∨(h−itt∧[−]Z)

またアクションに着目すると

µZ.h−itt∧[−K]Z

組み合わせ safetyとlivenessを組み合わせたプロパティもある、たとえばaが発生する場 合は、いつかはbが発生する

νZ.[a] (µY.h−itt∧[−b]Y)∧[−]Z としてあらわせる

モデル検査ゲーム

µ計算のモデル検査をGameで解く手法を紹介する。

V を値割付、Eをプロセス、Φをµ計算の式であるとしたとき、Gv(E,Φ)をモデル検査 ゲーム¹と定義する。

Gv(E,Φ)では、PlayerIが、Eが値付けV に対してΦを充足しないことを証明しようと し、PlayerIIは逆を行うGameを実行する。

Gv(E,Φ)のplayは有限あるいは無限の(E₀,Φ₀)...(E_n,Φ_n)..列であり、Φ_i ∈Sub(Φ), E_i ∈ P(E₀)である。

いま仮にplay列が(E₀,Φ₀)...(E_j,Φ_j)であるとして次の可能な手番moveはΦ_jの形式に 依存して決定される。

¶ ³

Gameのルール

• Φ_j = Ψ₁∧Ψ₂ならば、PlayerIがΨ_i を選択する。すなわちE_j+1 =E_j,Φ_j+1 =P si_i

• Φ_j = Ψ₁∨Ψ₂ならば、PlayerIIがΨ_i を選択する。すなわちE_j+1 =E_j,Φ_j+1 = Ψ_i

• Φ_j = [K] Ψならば、PlayerIがE_j →^a E_j+1を選択し、Φ_j+1 = Ψとする

• P hi_j =hKiΨならば、PlayerIIがE_j →^a E_j+1を選択し、Φ_j+1 = Ψとする

• Φ_j =σZならばΦ_j+1 =Z, E_j+1 =E_j

• Φ_j =ZかつΦ₀においてZに関連する部分式がσZ.ΨならばΦ_j+1 = Ψ, E_j+1 =E_j

µ ´

¶ ³

Player Iの勝利条件

1. 有限のplayが(E₀,Φ₀)...(E_n,Φ_n)であり、Φ_n= ffあるいはΦ_n =Z(ZはΦ₀の中 で束縛されないかつE_n∈/V(Z))

2. 有限のplayが(E₀,Φ₀)...(E_n,Φ_n)であり、   Φ_n = hKiΨかつ{F : E →^a F ∧a∈K}=∅

3. 無限のplayが(E₀,Φ₀)...(E_n,Φ_n)...であり、infinitely oftenに展開される変数χ_i の中で最外郭のものがνχ.Ψという形式をとる場合

µ ´

¶ ³

Player IIの勝利条件

1. 有限のplayが(E₀,Φ₀)...(E_n,Φ_n)であり、Φ_n= ttあるいはΦ_n =Z(ZはΦ₀の中 で束縛されないかつE_n∈V(Z))

2. 有限のplayが(E₀,Φ₀)...(E_n,Φ_n)であり、   Φ_n = [K] Ψかつ{F : E →^a F ∧a∈K}=∅

3. 無限のplayが(E₀,Φ₀)...(E_n,Φ_n)...であり、infinitely oftenに展開される変数χ_i の中で最外郭のものがµχ.Ψという形式をとる場合

µ ´

playが無限の場合はinfinitely oftenに展開される「最外郭の不動点」により勝者が決まる。

最小不動点の場合はPlayerIが、最大不動点の場合にはPlayerIIが勝利する。最外郭とは式 のsubsumption関係（部分式の関係）により定義される。たとえばσχ₁σχ₂..σχ_nΦ(χ₁, .., χ_n) であるとするとinfinitely oftenに展開されるχ_aの中で他のchi_iをsubsume するもっとも 大きいchi_jが存在するはずで、これを最外郭と定義する。

例

D→^a D⁰, D⁰ →^a D⁰, D →^b D⁰⁰ であり、Ψが

µY.νZ.[a] ((hbitt∨Y)∧Z)

であるとすると、DとD⁰は性質Ψを充足しない、つまりPlayerIはG(D⁰,Ψ)において、勝 利戦略を持つことになる、これを以下に示す。

(D⁰,Ψ)(D⁰, νZ.[a] ((hbitt∨Y)∧Z))(D⁰,[a] ((hbitt∨Y)∧Z)) (D,(hbitt∨Y)∧Z)

ここでPlayerIは(hbitt∨Y)を選択する。

...(D,hbitt∨Y)

ここでPlayerIIが(D,hbitt)を選択すれば即自負けになるので、(D, Y)を選択する、play は続き、

(D, Y)(D, νZ.[a] ((hbitt∨Y)∧Z))(D,[a] ((hbitt∨Y)∧Z)) (D⁰,(hbitt∨Y)∧Z)

ここでPlayerIは(D⁰, Z)を選択する

...(D⁰, Z)(D⁰,[a] ((hbitt∨Y)∧Z))...

以上のように、繰り返しが得られて、Z、Y はそれぞれinfinitely oftenに出現するが、Y はZをsubsumeし、Y は最小不動点と関連するからPlayerIが勝つ。すなわちPlayerIは 以下のメモリなしの必勝戦略を持ちえる。

• (D,(hbitt∨Y)∧Z)の場合には(D,hbitt∨Y)を選択する

• (D⁰,(hbitt∨Y)∧Z)の場合には(D⁰, Y)を選択する