■SPINについて
・SPINは、モデル検査ツールの1つ
・プロセス単位で手続き的にモデルを記述
<<モデル検査ツール>>
有限状態モデル+対象システムが満たすべき性質
↓
モデル検査ツール
↓
成り立つ?成り立たないとき反例
シュミレーション
モデル検査の例:SPIN,SMV,LTSA,UPPAAL、Java Path Finder
SPINは、
・デッドロック検証
・PLTL式検証のほか、
・表明(アサーション)や、ループ進行性のパラメタをいれて、検証できる
・progress
・never
・assert(ブール式)
■モデル検査で扱う「システムの性質」とは?
・到達可能性
→ある状態に到達する
・安全性
→デッドロックにならないなど
望ましくない状態に陥らない
・活性
→望ましい状態にかならず到達する
・公平性
→ある状態が無限回起こる
ただし、モデル検査ツールすべてが、上記の性質を扱うわけではない。
■性質を表現するには?
SPINの場合
・PLTL(線形時相論理)を使う
[] p (つねにPが成り立つ)
<>pいつかPが成り立つ
pUq qがいつか成立し、それまでPがなりたつ
+
否定、and、or
・安全性
→同時にクリティカルセクションに入らない
・活性
→飢餓状態(スタベーション)は発生しない
ずっと待たされることはない
いつかは、クリティカルセクションに入れる
■性質の記述パターン
・なかなか、表現がわからないので、
・表現のパターンがある(CTLもある)
http://patterns.projects.cis.ksu.edu/
→スコープ(対象とする範囲を定めたもの)が大事
・パターン(大きく2種類)
Occurenceパターン(おきる・おきない:発生を記述)
Orderパターン(順序を表現)
■SPINに話を戻し、しくみは?
Promelaで記述したシステムモデル
↓
Xspin
↓
spinが検証用プログラム生成
↓
コンパイル、実行
■SPINのモデル構成要素
おおきく、4つ
(1)記号定数定義
mtype={変数1,変数2};
(2)大域変数定義
chan toS
(chan => チャネルを示す)
(3)プロセス定義
proctype →本文
(4)init文
init{
プロセス生成
■文の中身
・データ型
・代入文
変数=値
・制御構造(ガード文)
goto
if
do
・メッセージの送受信
出力チャンネル名!値1
入力チャンネル名?値1
chan チャンネル名=[バッファサイズ] of {型の並び}
バッファサイズ0だと同期、1以上の数を指定し、非同期にできる
マニュアル
・日本語
http://www.asahi-net.or.jp/~hs7m-kwgc/spin/Man/Manual_japanese.html
・Reference manual
http://spinroot.com/spin/Man/promela.html
■Xspinのちょーかんたんな使い方
・File→Openで読み込むか、ファイルをエディットする
・Run→SetSimulationParametersをチェック
・でてきたパネルで、Start
・以下のようにウィンドウが3つでてきて、実行
■デッドロックの確認
・Run→Set Verification Option
・そうすると、ダイアログが出てくるので、Run
・デッドロックがあると、errorsというのがでてきて、Suggested Actionダイアログが出る
・Run Guided Sumilationをクリック
・出てきた画面(3つ)のうち、左上のダイアログ「Run」をクリック
→右側にシーケンスがでる
■PLTLを使う
・Run→LTL Property Managerを選択
・Formulaに、式を書く
[] a && b && c
・aの条件式を、Symbol Definitionに書く
#define a x <5
・generateをクリック
・Run Varificationをクリック
・新しく出てきたダイアログで、Runをクリック
※参考「いつかは、~にもどる」
[](!(a && b && c) → [](<> a && b && c))