Programming SHOT BARへようこそ。
完全なテストは不可能だ
といってしまった手前、現実的なテストについて考えて見ましょう。
なお、今回は数学側への分岐だった
メソッドは写像だ側の概念も含んでいます。
伏線回収だと思って読んでいただけると幸いです。
完全なテストのテストケース数
システムに対して完全な仕様書があると想定します。
こういう場合はこう動く、ということが明確に規定されているとします。
すると、テストというのは、実装が想定する動きと同じかを検証する行為ですから、
システムを関数Fで、仕様を関数Gで表現すると、
F(x) = G(x)
であることを、全てのxについて確認することになります。
ここで、xの取りうるパターン数が、そのままテストケース数になることになります。
今、入力xがn bitの情報量だとします。
すると、テストケース数は2n となります。
入力bit数に対して、検証は指数関数時間を要することになるわけです。
（ということはテストはNP困難ということに…？）
さて、ここで、入力が数種類あったとします。
システムに画面が5つあると想像してみてください。
互いの画面が連携しないのであれば、個別にテストすればいいわけです。
（している場合は、それも入力の一部としてテストを要する）
各画面での入力x1 ～ x5 が n1 ～ n5 bitの情報量だとすると、
テストケース数は
2n1 + 2n2 + ... + 2n5
となります。
つまり、完全なテストにおいては画面数の増加は、テストケースの増加にそれほど強く作用しない。
テストケース数にもっともインパクトを与えるのは、入力される情報量ということになります。
ホワイトボックステストでテストケースを削る
さて、ここまでは、完全なテスト、つまり、取りうる状態全てを仕様と
つき合わせて検証することを考察してきました。
しかし、入力される情報量に対して指数関数的にケース数が増えるため、
現実的には完全網羅してのテストは現実的ではありません。
そのため、バグを効率よく検出する工夫を凝らして実用的な手間で品質を確保しようとするわけです。
完全なテストの場合、テストケース数に一番インパクトを与えているのは、入力の情報量でした。
入力がint値ひとつであれば32 bitの情報量を持ちますから、約40億のテストケースを要します。
int値ふたつだと1600京であることは「完全なテストは不可能だ」の稿で述べたとおりです。
ところが、プログラムの内部ではこの40億のパターン個別に関心を持っているわけではなく、
このパターンを内部でたかだか数パターンに分類して処理を行っていることが殆どです。
例えば、負の数の場合、0、正の数の場合といった、3パターンに分けてロジックを書くことがあるわけです。
たいてい、バグというのはこの分類のどこかがバグるとその範囲全てでバグるか、もしくは境界近辺のみバグります。
このそれぞれのパターンをサンプリングしてテストすることで効率よくバグを検出することが出来ます。
これはいわゆるホワイトボックステストと呼ばれるものですが、
内部での分類の仕方を正確に把握していないと、網羅することが出来ない場合があります。
40億パターンから数パターンまで劇的に削るわけですから、このサンプリングの仕方が
テストケースの量と質（つまり、バグを取りこぼさないこと）に強く影響することになります。
ホワイトボックステスト下でテストケース数に作用するものは？
さて、bit数から劇的にパターン数を削りましたが、入力を複数とる場合、
個々の値を数パターンに絞ったところで、やはりそのパターンの組み合わせだけテストする必要があります。
例えば、int値を10個引数にとるメソッドがあるとして、
それぞれの値が内部でそれぞれふたつに分類されていたとしましょう。
その場合、
210 = 1024
と、1024パターンのテストが必要になるわけです。
もちろん、ふたつに分類というのは最小のケースでしょうから、
最低でも 2引数の数 以上のテストケース数となります。
このことから、テストケース数は
Σ 2 Fiの引数の数
よりも大きいぐらいであることがわかります。
入力引数の数を一定以下に抑えることで、多項式時間でのテストが可能となるわけですね。
(上記の考察を踏まえると、構文解析木からメソッド数および、その引数の数を集計することで
step数などからテストケース数を推定するよりもよほど意味のある推計ができるように思います。
もちろん、入力とは引数のみではなく、参照するインスタンスフィールドなども含むので正確な推計は
やはり難しいものになるとは思われますが。)
サンプリングの難しさ
int値がふたつあるだけで組み合わせが1600京にも上るわけですが、
テストケースを作成するということは、この1600京というパターン数をたかだか数パターンに集約し、
それでいてかつ、1600京の空間に潜む可能性のあるバグを取り漏らさないようにするということです。
これがテストの難しさであり、バグを完全に取り除いてソフトウェアを出荷することが
いかに難しく、非現実的かということです。
ソフトウェアテストとはこの不可能問題に対していかに近似解を提示するかという難問なのです。
投稿日時 : 2007年10月24日 22:21