2011/08/30

テストの話

因果律を否定するバグ の話が意外に受けてて、そこから派生してテストについての色々興味深いコメントが読めておもしろい。

で、まあ、テストには再現性のあるデータを使おうねってのは一番基本のところで、それがなってなかったから今回の件がボーアバグになった、っていうのはあるんだけれど、では最初からseed固定にしていたら良かったのかというと、潜在的なテストアルゴリズムの問題 (特定の系列でヒープが爆発する) は残ったままだ。

今回はテストアルゴリズムの問題だったんだけど、以前にプロダクト本体で面倒なアルゴリズムバグに当たったことがある。データをbucketに分けて保存する。bucketの個数はあまり増えて欲しくないので上限を設けるが、総データ量はディスクの許す限りにおいて上限無し。で、最初は各bucketの容量を低く決めといて、bucketが増えすぎたらいくつかのbucketをマージして大きなbucketにして、っていうコードだった。その中で、どのbucketをマージするかを選択するアルゴリズムに問題があって、bucketの容量分布がある特定の条件を満たした時に、マージ候補がひとつも選ばれないことがあり、bucketの数が減らせない。 その場合はしばらく待ってリトライするんだけど、これまた特定の条件において、bucketの状態を変え得るプロセスがマージ終了を待つことになっていた。この二つの条件が合わさると、bucketの状態が変化するまでマージできない vs. bucketがマージされるまで状態を変えられない、というデッドロックになる。

このうち、「bucketの容量分布が特定の状態を満たした時」というのはかなり特異な条件で、このバグを開発者に話した時も「え、そんな偶然、現実に起きるのか?」と驚かれたのだが、実データで起きたんだから仕方ない。起き得ることは、いつかは起きるのだ。

で、こういう話だと、ランダムデータでテストしてもまず発見できない。ユニットテストでのテストカバレッジ100%にしても発見できない (この特定のデッドロック状態を検出してエラー出す、ってコードを入れてれば、その分岐が実行されないからわかったかもしれないけど、そもそもそういう状態が起き得るとわかってないからなあ)。

そういうわけで私は盲目的なランダムデータテストには消極的で、

1. ホワイトボックステストでは人為的に境界条件を突くデータを用意する
2. ブラックボックステストでは「Pという条件を満たす入力xに対して、出力yは条件Qを満たす」というふうに定式化した上で、P(x)を満たす範囲でxをできるだけ自動生成する

っていうのを目標にはしている。ただ、これでも上のbucketのようなケースが見つけられるかというと心許ない。

因果律を否定するバグの場合は別の厄介さがあった。問題のテストはinvarianceが必要十分条件であることを確認するテストだったのだ。つまり、

 「入力xがPという条件を満たすとき、その出力yは条件Qを満たす」

というテストではなく、

 「入力xがPという条件を満たさないとき、その出力yは条件Qを満たさない」

という命題をテストしていた。定義域が有限集合ならPとQを単に~Pと~Qに置き換えれば 同じ話になるんだけれど、定義域が無限集合の場合、後者のテストは前者のテストよりも難しい。 (逆関数が計算できるなら、対偶を使って、 「条件Qを満たす出力yを生成するような入力xは条件Pを満たす」ことを テストすれば良いのだが、自動的に逆関数が導けるような コードならそもそもこんなにテストに悩んでない。)

で、結局こういう例をちゃんとテストしようとするとサンプルによるテストじゃ無理で、 静的検証だろうなという気はしている。が、今動いてる、ばりばりに最適化がかかったLispコード にそのまま使えるような静的検証機は無いだろうしな。 何らかのメタ情報をマクロで仕込めるようにして、部分的に静的検証をかけるような 仕組みは作れるかもしれないが。

それともうひとつ、今のプロジェクトではテストに時間がかかりすぎるって悩みがある。 これはあるコードパスを通すための状態を直接作る手段が用意されてないってのが問題で。 ある低レイヤのコードパスを検証したいんだけど、そのパスを通るための状態 (共有メモリとディスク上の永続ファイルや一時ファイルの状態)を作り出すために、 結局一番上のレイヤからデータを送り込んでやらないとだめ、っていう面倒な話になってる。 そのためにいくつもプロセスを起動してネットワーク経由でデータをやりとりする羽目になってて、 オーバヘッドがバカにならない。

中間状態をダンプしておけば、という話もあるけど、チューニングによって中間状態の データ形式が結構頻繁に変わるんであんまり意味がない。 モジュール毎に、特定の状態を作り出すテスト用APIを地道に実装してゆくしか ないと思うんだけど、既に動いてるコードがあるからなあ。

Lispなのでマクロで助かってる面はある。コードウォーカーを書いて、 コード特定の場所でfailするように仕向けるようなテストを生成するのは簡単で、 異常系のテストなんかはそれでやってるんだけど。

Tags: Programming, Lisp