「秘書問題」の参考文献として図書館から借りた本に、曲がりなりにはソフトウェアに関わっている筆者としては、読んどかないと気になって仕方なくなるに違いない、一際目を引く問題があったので、返却する前に一読した。
「ソフトウェアリリース問題」と呼ばれている、最適停止問題の１つだ。
単純化した概要をメモする。
問１：テストが未実施である、開発中のソフトウェアの全バグ数がBとし、n回目のテストで見つかるバグ数をX(n)とする。BとX(n)の確率分布は既知で、E(X(n))は単調減少とする。見つかったバグは、各回のテスト終了時にコスト0で直ちに直される（バグ修正のコストはテストのコストに含まれる）とする。テスト1回当たりの費用をCt、ソフトウェアリリース後に残されるバグ1件当たりのコストをCb、Ct<<Cbとする時、コストを最小にするには、何回テストしてリリースするのが最善か。
ソフトウェアの開発の仕事をしたことがある人なら１回は考えさせられたことがあるであろう、どこまでテストすればいいのかという問題である。「バグが0になるまでに決まってるだろ！」と思う人が居るかも知れないし、そのように上から言われてる人が居るかも知れない。筆者は過去にそんな理不尽な圧力を何度も目撃した。しかし、現実的にはバグが0であることを証明するのは不可能である。ごくごく一部の例外を除き、はるかに不可能であり、不可能オブ不可能ズであり、1秒でも考えるのが無駄なくらい十分に不可能なのである。バグが無いことが証明されてリリースされるソフトウェアなんて存在しないのであり、どれだけテストして修正しても、ソフトウェアにバグは必ず存在するのである。
現実社会できちんと真っ当なソフトウェア開発の仕事をする人にとっては、バグの数が何らかの確率モデルで仮定されることは至極当然であり、むしろ、そうしないと仕事にならない。
解１：n回テストした時のトータルコストC(n)はn*Ct + (B - ΣX(k))Cbであり、
C(n+1)-C(n) = Ct - X(n+1)Cb
であり、E(X(n+1))は単調減少なので、E(C(n+1)-C(n))は単調増加であり、どこかでテストのコストの平均が残バグのコストの平均を上回る。E(C(n+1)-C(n)) > 0を解くと、E(X(n+1)) < Ct/Cbなので、答えはE(X(n+1)) < Ct/Cbとなるnである。
問２：Bが平均λのポアソン分布に従い、X(n)がその時点のバグ数と確率pをパラメーターとする二項分布に従う時、問１の最適なnはいくらか。
ソフトウェアのバグ数は、ソフトウェアの規模に比例すると考えられることが多い。システムの規模が大きくなると単位コード量当たりの複雑さも増すので、比例するというのはおかしい、と考えるのも自然なことなのだが、現実にはソフトウェア開発の対価はコード量に比例して支払われることが多いため、ソフトウェアは冗長であってもなるべく単純に作られ、単位コード量当たりの複雑さは上がらないのである。コード量が減るように工夫して効率の良いコードを作ると逆に報酬が下がってしまうので、コードは最適化されずに単純で似たようなコードの積み重ねとなり、システムの複雑さがそのままコード量として表れるのである。
従って、ソフトウェアのバグ数が（規模×単位コード量当たりのバグ数）を平均とするポアソン分布に従うと仮定するのは、現実社会に居て違和感を感じない。
1回のシステムテストで見つかるバグの数は、1つ1つのバグについて確率pで見つかると考えると、バグ数×pを平均とする二項分布に従うと仮定するのは、至極妥当であろう。
解２：B(n)をn回目のテスト後のバグ数とすると、1回のテスト当たりに見つからずに残る割合の平均が(1-p)なので、B(n)は平均λ(1-p)nのポアソン分布に従う。X(n+1)の平均はB(n)*pなので、答えはE(X(n+1)) = λp(1-p)n < Ct/Cbとなるnである。
参考文献
「タイミングの数理 最適停止問題」穴太克則 著（朝倉書店）
例として、以下のような架空のプロジェクトがあるとして、具体的な数値をMaximaで計算してみる。
バグの総数: 1000
1回のテストで見つかる割合: 0.8
1回のテストの費用: 10
残バグ1つ当たりのリリース後の費用: 1000
の場合、λp(1-p)n = 1000 * 0.8 * 0.2n < 10/1000で、解くとn > 7.02となり、8回テストするのが最善である。この時のトータルコストは82.56となる。
(%i107) fpprintprec:4;これを、1回毎のテストを簡略化し、
(%i108) solve(1000 * 0.8 * 0.2^n = 10/1000, n), numer;
(%o108) [n=7.015]
(%i110) cost(n,p,Ct) := n*Ct + (1000-sum(1000*p*(1-p)^(k-1),k,1,n))*1000;
(%i111) makelist(cost(n, 0.8, 10), n, 5, 10);
(%o111) [370.0,124.0,82.8,82.56,90.51,100.1]
1回のテストで見つかる割合: 0.7
1回のテストの費用: 7
と変えられた場合は、1000 * 0.7 * 0.3n < 7/1000で、n > 9.56となり、10回テストするのが最善となる。この時のトータルコストは75.9となる。従って、バグの発見率が少し下がる程度でテストを簡略化できるなら、テストを簡略化して回数を増やす方が良い。
(%i112) solve(1000 * 0.7 * 0.3^n = 7/1000, n), numer;
(%o112) [n=9.562]
(%i113) makelist(cost(n, 0.7, 7), n, 7, 12);
(%o113) [267.7,121.6,82.68,75.9,78.77,84.53]
逆に、同じ例で、1回毎のテストに倍の費用をかけて発見漏れを半分にしようとすると、n > 4.65でテストの回数は5回と減るが、トータルコストは110と上がってしまう。
(%i127) solve(1000 * 0.9 * 0.1^n = 20/1000, n), numer;テストの費用が13くらいで発見漏れを半分にできると、トータルコストが75と下がる。
(%o127) [n=4.653]
(%i128) makelist(cost(n, 0.9, 20), n, 3, 7);
(%o128) [1060.,180.0,110.0,121.0,140.1]
(%i129) solve(1000 * 0.9 * 0.1^n = 13/1000, n), numer;こんなプロジェクトがあるかどうかは別にして、なかなか微妙なものである。
(%o129) [n=4.84]
(%i130) makelist(cost(n, 0.9, 13), n, 3, 7);
(%o130) [1039.,152.0,75.0,79.0,91.1]
コメント