Share
Embed
形式手法について調べてみた
開発でよくある仕様不備についてなにか打ち手はないかと模索していたとき、形式手法に出会いました。形式手法とはなにか、形式手法に期待される効果などをまとめました。
Hodaka Suzuki
March 07, 2019
Transcript
64 slides
-
@hoddy3190 Mar. 7th 2019 Android Test Night #6 形式手法について調べてみた Let’s
Try Formal Methods -
鈴木穂高(Hodaka Suzuki) Twitter @hoddy3190 • 2014年DeNA新卒入社 • アプリゲーム開発・運用(2014/08 〜 2018/10)
◦ サーバー、クライアント、マスター管理ツール、インフラ 整備、マネジメントなど ◦ パフォチューが好き • テスト技術チーム - SWET(2018/10 〜) ◦ Android ◦ 形式手法 -
目次 • 動機 • 形式手法とは • モデル検査とは • 形式手法適用のシミュレーション •
メリデメ等 • まとめ -
用途 • 記述に不具合がないことを数学的に証明し保証 • 厳密な言語を用いることで仕様を明確化 • 記述中に隠れている不具合を開発早期に発見 • 正しいシステムだけを系統的に開発 ※一番最後の用途は、Correctness
by Constrution (CxC)と呼ばれ、 実現は不可能に近いと言われている -
代表的な手法 • 形式仕様記述 ◦ 矛盾がなく論理的に正しい仕様を作成する • モデル検査 ◦ プログラムの状態をモデル化することで プログラムが正しいことを検証する
• 定理証明 ◦ 法則や説明に基づき、理論的に性質が 成り立つことを示していく -
代表的な記述言語/ツール • 形式仕様記述 ◦ 例: VDM++/Event-B/Z etc. • モデル検査 ◦
例: Alloy/Promela/TLA+ etc. • 定理証明 ◦ 例: Coq/Isabelle etc. -
変数a * 変数bの結果は常に9未満である 1から3までの任意の値をとる 変数a 表明 1から3までの任意の値をとる 検査 1. aとbの取りうるすべての組み合わせを探索する
2. 表明に反する組み合わせ(反例)の有無をチェックする 3. 反例があれば表示する 変数b -
Promelaでの例 inline Choose(n) { if :: n = 1 ::
n = 2 :: n = 3 fi } active proctype P() { int a = 0, b = 0 Choose(a) Choose(b) assert(a * b < 9) } -
Promelaでの例 inline Choose(n) { if :: n = 1 ::
n = 2 :: n = 3 fi } active proctype P() { int a = 0, b = 0 Choose(a) Choose(b) assert(a * b < 9) } a、bの値をセットする -
Promelaでの例 inline Choose(n) { if :: n = 1 ::
n = 2 :: n = 3 fi } active proctype P() { int a = 0, b = 0 Choose(a) Choose(b) assert(a * b < 9) } 普通のif文とは異なり、::に続く3つの処理のうちの 1つが非決定的に実行されるという意味 -
Promelaでの例 inline Choose(n) { if :: n = 1 ::
n = 2 :: n = 3 fi } active proctype P() { int a = 0, b = 0 Choose(a) Choose(b) assert(a * b < 9) } a、bが満たすべき条件を記述する(表明) -
Promelaでの例 Spinで検査 $ spin -a -o2 ./sample.pml $ gcc -o pan
pan.c $ ./pan -E -c0 -e $ spin -p -t1 sample.pml # 結果出力 Spinはモデル検査ツール。Homebrewでインストール可能。 -
Promelaでの例 結果 using statement merging 1: proc 0 (P:1) a.pml:5 (state
3) [a = 3] 2: proc 0 (P:1) a.pml:5 (state 9) [b = 3] spin: a.pml:13, Error: assertion violated spin: text of failed assertion: assert(((a*b)<9)) 2: proc 0 (P:1) a.pml:13 (state 13) [assert(((a*b)<9))] spin: trail ends after 2 steps #processes: 1 2: proc 0 (P:1) a.pml:14 (state 14) <valid end state> 1 process created -
Promelaでの例 結果 using statement merging 1: proc 0 (P:1) a.pml:5 (state
3) [a = 3] 2: proc 0 (P:1) a.pml:5 (state 9) [b = 3] spin: a.pml:13, Error: assertion violated spin: text of failed assertion: assert(((a*b)<9)) 2: proc 0 (P:1) a.pml:13 (state 13) [assert(((a*b)<9))] spin: trail ends after 2 steps #processes: 1 2: proc 0 (P:1) a.pml:14 (state 14) <valid end state> 1 process created (a, b) = (1, 1), (1, 2) …, (3, 2), (3, 3) と すべての組み合わせを探索した上で、 a = 3, b = 3 のときが反例であると表示される -
PlusCalでの例 ---- MODULE button ---- EXTENDS TLC (* --algorithm button
variables pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== -
PlusCalでの例 ---- MODULE button ---- EXTENDS TLC (* --algorithm button
variables pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== 状態を変数で定義 -
PlusCalでの例 ---- MODULE button ---- EXTENDS TLC (* --algorithm button
variables pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== ボタンが押されているかいないか -
PlusCalでの例 ---- MODULE button ---- EXTENDS TLC (* --algorithm button
variables pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== ログイン中か否か(説明の便宜上、TRUE固定にしてある) -
PlusCalでの例 ---- MODULE button ---- EXTENDS TLC (* --algorithm button
variables pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== ボタンの初期状態は、押されている場合もあれば 押されていない場合もある(ランダム) -
PlusCalでの例 ---- MODULE button ---- EXTENDS TLC (* --algorithm button
variables pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== ログイン中であればボタンを押した状態にする -
PlusCalでの例 ---- MODULE button ---- EXTENDS TLC (* --algorithm button
variables pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== 表明を常に満たせないようにすることで、 システムが取りうる全状態を反例として抽出できる -
PlusCalでの例 TLCで検査 $ pcal button.tla $ tlc button.tla -continue -dfid 100
-dump log $ cat log.dump -
PlusCalでの例 TLCで検査 $ pcal button.tla $ tlc button.tla -continue -dfid 100
-dump log $ cat log.dump pcalコマンドでPlusCalをTLA+に変換 -
PlusCalでの例 TLCで検査 $ pcal button.tla $ tlc button.tla -continue -dfid 100
-dump log $ cat log.dump tlcコマンドで検査 -
PlusCalでの例 TLCで検査 $ pcal button.tla $ tlc button.tla -continue -dfid 100
-dump log $ cat log.dump 結果出力 -
PlusCalでの例 結果 State 1: /\ logined = TRUE /\ pc =
"Lbl_1" /\ pushed = FALSE State 2: /\ logined = TRUE /\ pc = "Lbl_1" /\ pushed = TRUE -
State 1: /\ logined = TRUE /\ pc = "Lbl_1"
/\ pushed = FALSE State 2: /\ logined = TRUE /\ pc = "Lbl_1" /\ pushed = TRUE assert FALSEに至る直前の状態の全パターン PlusCalでの例 結果 -
State 1: /\ logined = TRUE /\ pc = "Lbl_1"
/\ pushed = FALSE State 2: /\ logined = TRUE /\ pc = "Lbl_1" /\ pushed = TRUE ログイン中かつすでにボタンは押された状態 PlusCalでの例 結果 -
---- MODULE button ---- EXTENDS TLC (* --algorithm button variables
pushed \in BOOLEAN, logined = TRUE; begin if logined = TRUE then pushed := TRUE; end if; assert FALSE; end algorithm; *) ==== 押された状態のボタンを押す?? PlusCalでの例 結果 -
---- MODULE button ---- EXTENDS TLC (* --algorithm button variables
pushed \in BOOLEAN, logined \in BOOLEAN, enabled \in BOOLEAN; begin NotEnded: either \* push await logined /\ ~pushed /\ ~enabled; pushed := TRUE; or \* unpush await logined /\ pushed /\ ~enabled; pushed := FALSE; or \* lock await ~enabled /\ ~logined; enabled := TRUE; or \* unlock await enabled /\ logined; enabled := FALSE; or \* login/logout logined := ~logined; end either; End: skip; end algorithm; *) ==== PlusCalでの例 -
---- MODULE button ---- EXTENDS TLC (* --algorithm button variables
pushed \in BOOLEAN, logined \in BOOLEAN, enabled \in BOOLEAN; begin NotEnded: either \* push await logined /\ ~pushed /\ ~enabled; pushed := TRUE; or \* unpush await logined /\ pushed /\ ~enabled; pushed := FALSE; or \* lock await ~enabled /\ ~logined; enabled := TRUE; or \* unlock await enabled /\ logined; enabled := FALSE; or \* login/logout logined := ~logined; end either; End: skip; end algorithm; *) ==== PlusCalでの例 ボタンが押せる状態になっているか否か -
• いいねボタンを設置してください ◦ 投稿にいいねは1回のみ押せます ◦ ログインしているユーザーしかいいねを押せません ◦ 押された状態のボタンを押すとボタンはもとに戻る ◦ ログインしていない場合、ボタンは押せない状態になる
仕様不備発見 モデル化する過程を通して、 「押せない状態」の存在に気づけた NEW