2010/03/31

TDD ⇒ PDD

ダイクストラは、テストでバグの存在は示せるがバグのないことは示せないと言っていた。一方で、TDDはテストを重ねながらプログラミングをおこない、用意したテストが全部通ったらプログラム完成と言うアプローチだ。と誤解しやすいが実は単なる開発プロセスに対する提案である(10/2)。
欲しいのはバグはあるかも知れないが取りあえず動作する綺麗なコードではなく、まずバグのないコードだ。
この点を改善するにはどうするか。実は良いアイディアが浮かんだ。自動テストツールではなく、プログラム検証ツールを使用して正しいことを証明しながらプログラミングをおこなうPDD(Proof driven development)だ。
プログラムSの証明とは、Qを事前条件、Rを事後条件として、{Q} S {P}が恒真であることを示すことだ。たとえば、二つの整数x, yを与えられてxが大きい値になるように、値を入れ替えるプログラムを書きたいとする。つまり


main()
{
  int x, y;

  assert(x >= y);
}

と言うことだ。これは関数仕様になる。Qは無しつまりQ = { T }、R = { x >= y }である。このソースコードをプログラム検証ツールのCBMCに掛けると当然


Violated property:
  file proof0.c line 8 function main
  assertion x >= y
  FALSE

VERIFICATION FAILED

となり正しくないことが証明される。次にもともとxの方が大きい場合をQに設定して検証する。つまり以下のプログラムを検証する。ここで、__CPROVER_assume( );はCBMCで前提条件を設定するディレクティブである。

main()
{
  int x, y, tmp;
  __CPROVER_assume( x>=y ); // Q1

  assert(x >= y);
}

これは成功する。従って x >= y の時は何もしなくて良いことが証明された。次にこのQが否定された場合を考える。¬(x >= y) だから(x < y)だ。

main()
{
  int x, y;
  // __CPROVER_assume( x>=y ); // Q1
  __CPROVER_assume( x < y ); // Q2 = ¬Q1

  if (x < y) {

  }
  assert(x >= y);
}


これは失敗するのでif文の中を書いて


main()
{
  int x, y, tmp;

  if (x < y) {
    tmp = x;
    x = y;
    y = tmp;
  }
  assert(x >= y);
}

とすると

>cbmc proof0.c
file proof0.c: Parsing
proof0.c
Converting
Type-checking proof0
Generating GOTO Program
Function Pointer Removal
Starting Bounded Model Checking
size of program expression: 18 assignments
simple slicing removed 1 assignments
Generated 1 VCC(s), 1 remaining after simplification
Passing problem to propositional reduction
Running propositional reduction
Solving with MiniSAT2 without simplifier
761 variables, 2109 clauses
SAT checker: negated claim is UNSATISFIABLE, i.e., holds
Runtime decision procedure: 0.034s
VERIFICATION SUCCESSFUL

となって正しいことが証明された。(x >= y)∨(x < y)は恒真なのでQ= {T }となり仕様が満たされた。
ダイクストラの時代にはプログラム検証器が無かったので手で証明しなければならず実用にはならなかったが、今は検証器がある。現在この手法の体系化を進めている。プログラミングが終わった時に、使い古しのテストケースとバグがあるかも知れないコードを得るTDDよりはPDDの方が良いことは言うまでもない。しかもdivision by zeroの様な普通のテストではできない検証も可能である。

2010/03/04

モデル化のセンス

Use Caseモデルを作ろうとするとDFDのような数珠つなぎの絵を描いてしまう、なぜだろうか、と聞かれたのでしばらく考えていた。たまたまUML&FMと言う形式手法関係のIEEEのワークショップの資料を見ていたところ下図のような絵があった。

きっとMulti-viewのところの知識か何かが不足しているのでそのようなことになるのではないか。例えば、DFDの使い方には長けているので何でも本人は書けてしまうし良く理解できている。何でもExcelで書いてしまう人などこのタイプは多い。自分用のメモとしては良いかも知れないが、他の人には理解してもらえない。変てこな図を書いていても作るものは作っているのであれば、抽象化軸やアーキテクチャ軸は頭の中に存在しているのだろう。Multi-view軸のところには色々なタイやグラムが並んでいるが目的に応じて使い分けることをUMLは意図している。下の図のような状況をUMLはある程度回避できるが、意味的な厳密さが無いので十分ではないと言うのがUML&FMでは話題になっている。

アーキテクチャとViewと言えばKruchtenの4+1 Viewが有名だ。


上記の図はオリジナルの論文[1]に掲載されているものでRational Softwareの資料では多少変更されている。


RUPにおけるそれぞれのビューの説明は以下のようになっている。

ユース ケース ビュー: アーキテクチャ上重要な振る舞い、クラス、技術面でのリスクを含むユース ケースとシナリオが含まれます。ユース ケース モデルのサブセットです。

論理ビュー: 最も重要な設計クラスとそのクラスからパッケージとサブシステムへの編成、これらのパッケージとサブシステムからレイヤへの編成が含まれます。ユース ケースの実現も含まれます。設計モデルのサブセットです。

実装ビュー: 実装モデルと、モジュールの観点からのパッケージとレイヤへの編成の概要が含まれます。実装ビューのパッケージとモジュールへの、(論理ビューの) パッケージとクラスの割り当ても記述されます。実装モデルのサブセットです。上の図ではコンポーネントビューと表示されている。

プロセス ビュー: 関与するタスク (プロセスとスレッド)、そのタスクの相互作用と構成、タスクへの設計オブジェクトとクラスの割り当ての記述が含まれます。このビューは、システムにかなりの程度の並行性がある場合にのみ使用する必要があります。RUP では、設計モデルのサブセットです。

配置ビュー: ほとんどの典型的なプラットフォーム構成のさまざまな物理ノード、物理ノードへの (プロセス ビューの) タスクの割り当ての記述が含まれます。このビューは、システムが分散される場合にのみ使用する必要があります。配置モデルのサブセットです。

それぞれのビューに向いたダイヤグラムがあるのでそれを使い分ければ良いモデルになるだろう。と言えれば美しいが、実際はUMLに存在するほとんどのダイヤグラムは論理ビュー向きである。動的な表現のために、シーケンス図とか状態図があるがタスク構造を表現するには不十分で、プロセスビューを記述することはできない。それでヨーロッパではADLが作られた。タスク構造を表現するための図としては、Gommaの図などがUML以前からあったが今は忘れられている。その意味ではプロセスビューが重要になる組込システムをUMLでモデリングしろ言われてもできないのが当然で、論理ビューの記述だけして実装に入ってしまう人の方がむしろ疑問が残る。
4+1ViewではユースケースビューからプロセスViewを構築することになっているが、ユースケースモデルで描くシーケンス図等の動的仕様とタスク設計の間にはまだギャップがある。どちらかというとユースケースモデルよりもプロブレムフレーム[3]による要求分析の方が動的な要求を正確に獲得できる気がする。ちなみに[4]は親子で書いた論文でプロブレムフレームとAlloyをどう融合するのかと言う面白い論文である。
プロブレムフレーム⇒Concurrency⇒Gomaaの流れが動的なモデリング、つまり動的アーキテクチャ構築には必要だと思う。ここでConcurrency[5]はLTASの教科書である。
参考文献
[2] Hassan Gomaa, Software Design Methods for Concurrent and Real-Time Systems.




[3] Problem Frames: Analysing and Structuring Software Development Problems (Addison-Wesley, 2001)




[5] Concurrency: State Models and Java Programs



2010/02/26

ソースコードの論理構造

要求を構造化した要求木と言う考え方を2010年2月号のインタフェース誌で紹介した。
要求管理ツールなどで要求のトレーサビリティを管理する例はあるが、それは単なる関係ではなくて論理的関係である。このことを利用して知識ベース化しようと言う考え方である。
今月のインタフェース誌(2010年4月号)はこの続きで、要求木の一番下のソースコードとの関係をプログラム検証ツールCBMC ( Bounded Model Checking for ANSI-C )を利用してソースコードも論理式にしてしまって要求木に組み込んで見ようと言う試みである。

上の図でCが左のソースコードの論理式表現になる。Rがアサーションでソースコードが満たすべき仕様になる。要求木の図ではReq6とかReq7にあたる。
CBMCはソースコードを論理化するのが目的ではなくPolySpaceと同じようなソースコード検証をするためのツールである。PolySpaceに比べるとフリーのツールなので使いづらいが、同じソースコードに対して同じ箇所の問題を指摘してくれる。ただし、PolySpaceと違って指摘の仕方がちょっと分かりづらい。また、Bounded Model Checkingを使っているので無限ループになることを検出するのは無理だ。

参考文献
[1] A Tool for Checking ANSI-C Programs,
http://www.kroening.com/papers/tacas2004.pdf
[2] astah 6.1 で「要求モデル」が目指している姿 T

2010/02/23

Simics

エリクソンの基地局ソフトのデバッグのために開発されたシミュレーション用のツールSimicsを、ウィンドリバーのセミナーで見てきた。シミックスと読むらしい。

http://www.co-nss.co.jp/products/middleware/simics.html

バーチャテック・ジャパンと言うところが日本法人らしいがまだ日本語のホームページがない。英語のページに行くとホワイトペーパーがそろっている。ゾウムシのような虫の写真付きのホワイトペーパーがあった。スエーデンの虫だろうか?

ボードレベルのシミュレーションを行うことができる。システムLSIのシミュレーション等でサイクルアキュレートだと数ミリ秒分の実行で一晩かかったりするが、このツールはボードを仮想化してハードウェア部分のメモリとかバスのシミュレーションはやらないのでサクサクと動く。Windowsの時計のシミュレーションのデモを見たが実時間より早く動く。面白いのはログを取っておいて逆実行ができる。また、ハードが故障した状態を設定することもできる。通信で特定のデータだけ遅延やロストしたときどうなるかについて実験することもできる。
Windows上でLinux動かすデモでは、2コアのうち一つのコアのクロックを遅くしたときの実験とか、止めてしまったときの実験をしていた。
シミュレーションするためのハードのモデル化にどの程度手間がかかるのか分からないが、これがあればタスク設計の善し悪しの判定が楽になる。DML(Device Modeling Language)というC言語を拡張した言語でハードをモデル化する。eclipseベースのモデリング環境がある。このモデルがハードのスペックになるのでハード屋さんが作ってくれると更に楽だ。
Linuxのシミュレーションが出来る評価ライセンスがあるらしい。

6/7 追加: Virtutech(Simics等の製品ですね)はWindriverに買収されたそうです。

参考文献
[1]システムシミュレータSimicsを用いたLinux Super Pageの評価

2010/02/20

原因結果グラフ-2 MASK

結果グラフで A masks B とした場合の扱いは

1) A⇒¬B
2) Aが真ならBは未定義(三値論理の利用)
3) Aの真偽による場合分け

の三通りが考えられる。

1)の場合REQ制約の否定として表現できる。CEGTestの場合は、問い合わせ中だが、REQの否定を柔軟に利用できればMASKは要らなくなってしまう。 赤い四角で囲った部分を表現することが出来るので1)の意味でのMASKは特に必要ない。
青丸で囲んだところはちょっと怪しい。と言うか括弧で括るような、否定を取る優先順位を決めなければならない。そう言うことを考えなくても良いようにREQとMASKが定義してあると言うのは合理的かも知れない。ただし、最近FXの秋山氏の指摘で新たな謎が生まれた。MASKは結果側に付ける[1]と言うものである。もしそうなら原因結果グラフは結構簡単で使いやすいものになる気がする。この謎の裏にどんな合理性があるのか調べてみたい。


2)調べてみると三値論理には何種類もある[2]。マスクされた側をどう解釈するか(a.真か偽か決まらない状態、b.真でも偽でもない第三の状態、c.無意味)によって使用する論理系が変わる。VDMはaによって未定義を扱える。ただし、実装上の都合で一部変更して利用している[3]。用途によって結構自由に使って良い見たいな感じである。原因結果グラフを命題論理の範囲で扱うことを考えているので、各ノードは命題でなければならず、単に真偽が決まっていない状態とするのが話が難しくならなくて良いと思う。VDMの様な手直しをするかどうかはまた別の問題として考えれば良いだろう。三値論理を使うと、結果側に不定が現れる。結果側に現れる不定が妥当かどうか、ちゃんと解釈できるかどうかで使用する論理系を決めれば良いと思う。それで、幾つかやってみたが三値論理を使わなかった場合すなわち、1)の方法で真にも偽にもなり得るという結果に落ち着く。aの場合の真理表は以下のようになる。*が真偽が決まらない状態。赤いところをVDMでは*として扱う。


A B A∧B A∨B A⇒B ¬A
T T T T T F
T F F T F
T * * T *
F T F T T T
F F F F T
F * F * T
* T * T T *
* F F * *
* * * * *


3)“A masks B”をAが真の時はBを考慮しなくて良いというそのままの意味に解釈して。Aが真の時はBを含まない原因結果グラフを作ってしまう。これは、原因結果グラフ全体を表す論理式の真偽がどのような意味を持つのかに関わる問題と関係する。


参考文献
[1] http://en.wikipedia.org/wiki/Cause-effect_graph
[2]http://ja.wikipedia.org/wiki/3値論理





2010/02/16

原因結果グラフを利用した形式仕様記述

形式仕様記述というと述語論理から始まるが、命題論理でもやれることは多い。その一つが原因結果グラフである。これについては以前インタフェース誌[1]に書いたことがある。しかし、最近ニフィのK氏がCEGTestをリリースされたのだがどうも仕様が違う様なので悩んでいる。また、FXのA氏のツール(X-CEG)とも違う様だ。特にMASKの扱いが違う。それで本当はどうなのか少し整理しておきたい。インタフェース誌[1]に掲載した変換規則を以下に示す。元ネタは[2]である。EとOは要素数が3ヶ以上の時は論理式の形が変わる。それは[1]を参照。


原因結果グラフの本来の使い方はテストケースを絞り込むことであり、仕様を記述することではない。仕様記述としてはMC/DC等の手法を使って絞り込む前の論理式表現に興味がある。同じ文章から原因結果グラフを作っても人によって違うグラフが出来ることが多い。それは元の文章の解釈の違いを反映するが、論理式で表現すると論理的には等価であることが分かったりする。等価でなくても、どこが違うか明確化できて仕様の解釈のブレをなくすことが出来る。
取りあえず以下の3点が気になっている。

(1)まず原因から結果に向かう線の解釈だけれど、私は⇒(ならば)でなく⇔(同値)をディフォルトで使用していた。これは問題文に依存して決めるべき。例えば、料金表などでは同値関係にしないと別の条件でも同一料金になることを認めることになる。排他的に扱いたいかどうかで使い分ける必要があるだろう。
切符の払い戻しの場合、誤購入の時は必ず払い戻すのであれば
(誤購入)⇒(払い戻し)
となる。払い戻すのは電車が止まってしまった時にも行われるので
(払い戻し)⇒(誤購入)
は成立しない。と言うようなことを考察しないと決められないのだと思う。
一般的には、原因結果グラフの元になる文章はある特定の状況を表すフレーズなのでその範囲では、電車が止まってしまうことなどは想定しない場合が多いので
(誤購入)⇔(払い戻し)
として良い場合が多いように思う。つまり普通は、
(誤購入)⇒(払い戻し) または (誤購入)⇔(払い戻し)
だろう。逆向きになるのは原因が目的で、結果が実現方法の様な場合かも知れない。
別の見方としてこれは論理関係ではなく定義であると思った方が良い場合もある。結果を定義しているdefine文のようなものであり、結論を一つの素命題とするのではなく単なるラベルと考える。

(2)MASKは三値論理を使用するのが正しいかも知れない。しかし、その場合結果も不定になることがある。結果が不定でも良いのかは元の文章を書いた人に確認する必要がある。たぶん不定は意図していないのではないか。

(3)これが一番重要かも知れないけれど、原因結果グラフの論理式が真になると言うことがその仕様が矛盾無いと言うことを表す。形式仕様記述は全体が真になる範囲で分析をする。偽になるところは、あり得ないと元の文章を書いた人が言っているところだから分析の対象外にする。テストの場合は、全体の真偽はあまり考えないのか? 全体が偽になるところから選んだテストケースはハードが故障した場合とかユーザーのオペレーションミスのテストに対応するのか?


幾つか事例についてそれぞれのツールの結果を比較してみたい。長くなったので(2)と(3)はまた改めて。


参考文献
[1] 新・組み込みソフトへの数理的アプローチ(第6回)

原因結果グラフ――原因と結果の関係を木構造で表現する


[2]


2010/02/13

Watchdogの設計-2 リセットのモデル

WDTの動作モデルを作ってみる。基本的な動作を並列合成することで目的の状態マシンを生成することが出来れば、要求仕様を組み合わせてそれを満たす状態マシンを作ることが出来る。そのサンプルとしてマルチタスク下のWDTの挙動を利用する。

動作の合成
定周期タスクの動作は左図で表される。これをLTSAモデルにすると

CTask = (body->alive->CTask).

となる。WDTはCTaskがbody部分で無限ループになるかデッドロックになってフラグにaliveを書き込まないとシステムリセットを掛ける。リセット動作は

ResetProcess = (Allaction->ResetProcess|reset->shutdown->END).

と書くことが出来る。ここでAllactionは、

set Allaction = {body, alive}

のように定義しておく。CTaskとResetProcessを並列合成する。

||CTaskWithReset = (CTask||ResetProcess).

このようにすると以下のような状態マシンが生成される。
興味があるのはreset時のタスクの振る舞いなのでCTaskWithResetからbodyとalive, resetだけの振る舞いを抽出する。

||CTaskWithReset = (CTask||ResetProcess) @{body, alive, reset}.

そしてミニマイズすると
リセットによって終了する動作が生成される。つまり、アプリケーションとしてのタスクの動きCTaskとシステム動作であるreset処理を別々にモデル化できると言うことである。
ResetProcessにAllactionとしてアプリケーション処理が入っているところがちょっとダサイがこれを入れないとresetで終了しない。CTaskが動き続けてしまう以下のような動作モデルが生成されてしまう。
参考文献