原因結果グラフの「制約のテスト」 ONE制約

原因結果グラフの「制約のテスト」

原因結果グラフの「制約のテスト」　その2

の続きです。

==

「制約のテスト」を考える上で、どんなバグを検出できるか。まずはONE制約。4つのノード「A」「B」「C」「D」にONE制約がかかっている状態を例にしてみます。

4つのノードの必ず一つが真になるので、入力条件空間を平面で表現すると、以下のように4つの領域が隙間なく、境界線によって分割された状態が考えられます。

任意の入力条件は、4つの領域「A」「B」「C」「D」のいずれかに属することがわかる。これが ONE=(A B C D) が成立する状態です。では、成立しない状態とはどういう状態でしょう？

1. 領域「A」が領域「B」と一部分重なる場合



領域「A」と領域「B」を分割する境界がバグによって領域「B」側にシフトした場合、ONE=(A B C D)は成立しない。同様に領域「C」側にシフトした場合、領域「D」側にシフトした場合、を考えると以下の3通りの条件の組合せが考えられる。シフトする場合と同様、飛び地で領域が重なりあう場合も同じでしょう。



例えば、不等号「≦」「＜」の誤り、条件となる定数誤りなどがこのバグに該当する。また、何かのイベントがただ一つだけ生じるはずが、同時に2つのイベントが生じてしまうケースも。

そして、これは他の領域「B」「C」「D」についてもいえるので、同様に3つの条件の組合せが作れて、合計12通りが全部。



同じ条件の組合せが2つずつあるので、半分の6通りにまとまります。

2. 領域「A」の一部が欠落し、間隙が生じる場合

領域「A」と領域「C」を分割する境界がバグによって領域「A」側にシフトした場合、領域間に間隙ができてしまい、ONE=(A B C D)は成立しない。



これは、本来はAが真となるべき条件の組合せでAが偽となるパターンで、以下の通り。



先ほど同様、欠損は領域「B」「C」「D」にもありえるので、以下の3通りも考えられるが、結局は一つに集約。



例えば、不等号に「＝」をつけ忘れ、見逃したケースが存在するといった誤りがこのバグに該当する。状態を表すノードであれば、初期状態が未定義・不定値だったりする誤りもこのバグかな。

==

このことから、6+1＝7通りの組合せがありえないことを示せば、ONE=(A B C D) が成立することの必要条件となるだろう。

でも、実際にありえないことを確認するのって、難しいよなあ。。。