ソフトウェアのバグ摘出モデルとバグの収束性、テストの網羅性について

ソフトウェアから摘出されるバグの累積件数は、なぜ収束曲線を描くのだろうか? またバグの累積件数が収束曲線になるには、どのような条件が必要なのだろうか?
ソフトウェアの稼働後のバグ数は開発時の何と関係があるのだろうか? テストの網羅性とどのような関係があるのだろうか?
ソフトウェアの実行を簡単なモデルで表して、このような疑問への答えについて考えてみました。

目次

 

1.はじめに

ソフトウェアのテスト時や稼働後におけるバグ摘出過程の数理モデルとしては、ソフトウェア信頼度成長モデル等、いくつかのモデルが提案されています1)。これらのモデルを利用すると、ソフトウェア開発においてバグが収束傾向にあるかを判断する際に有益な情報を得ることができます。しかし、その一方で、現実のテスト工程では累積バグ数が指数型や遅延S字型等の曲線で近似されるような収束傾向にならない場合があります。例えば、ソフトウェア開発の現場では、テスト工程ではテストケースを作成して、これを1つずつ逐次実行してソフトウェアの検証を行っていますが、このテストの方法では累積バグ数は収束傾向の曲線を示さないで終了する場合があり、この場合はソフトウェア信頼度成長モデルの適用が困難になります。

ソフトウェア信頼度成長モデルでは、バグが収束するという現象は平均値関数の曲線の形状で表されており、平均値関数として指数型や遅延S字型等のモデルを選択できるようになっています。そのため、多様なバグの収束過程を様々な計算式で近似することができます1)。 また、Shanthikumarが提案したモデル1)は、マルコフ過程に基づいており、単位時間内にバグが1個発見される確率は、ある時刻でのソフトウェア内に存在するバグ数に比例するという仮定を設定しモデル化しており、バグ摘出過程において、時間の経過とともにバグが指数関数的に減少することは示されています。
ソフトウェア信頼度成長モデルやShanthikumarが提案したモデルはバグが発見される現象を表現していますが、ソフトウェアの実行方法と関係付けられてモデル化されているわけではないため、どのようなテストを行えばバグ摘出過程が収束傾向になるかなどが明確ではありません。 そのため本来収束傾向を示さない場合にもソフトウェア信頼度成長モデル等を適用してしまい、ソフトウェア開発の現場で混乱を与えていると考えられます。

以下では、上述した不明確な点を考慮してソフトウェアの実行をモデル化し、そのモデルからバグがどのように摘出されるか、またバグが全て摘出されるために必要な条件は何かなどについて記載します。

 

2.ソフトウェアの実行のモデル化


2.1 ソフトウェアの実行パスとバグ

一般にソフトウェアは複数の機能で構成されており、1つの機能には開始と終了を必ず定義できるとします。終了には、機能が正常に実行されて終わる場合と、何らかの誤りを通知して終わる場合がありますが、どちらも終了として考えます。この開始から終了までの間、複数のソフトウェアの命令が実行されます。この命令の系列を実行パスと呼ぶことにします。通常、ソフトウェアには多くの実行パスが含まれており、ソフトウェアに含まれる実行パスは数えることが可能であるとし、その総数を$N_{p}$とします。また、1つの実行パスに含まれる命令の系列を実行することを実行パスの実行と呼ぶことにします。

図1にソフトウェアのアルゴリズムの例と実行パスの例(赤の実線)を示します。また、ソフトウェアの動きを画面遷移として表した場合の実行パスの例を図2(赤の実線)に示します。

図1 実行パスの例1

図1 実行パスの例1

図2 実行パスの例2

図2 実行パスの例2

以下では、ソフトウェアのソースコードに含まれる欠陥をバグと呼ぶことにします。ソフトウェアに含まれるバグは、実行パスの中に含まれるとします。 ここでは、以下の説明を簡単にするために、次の4つの仮定を設定します。

  • (仮定1)1つの実行パスには1つのバグしか含まれていない。
  • (仮定2)バグは発見後直ちに修正され、実行パスはバグが含まれていない状態になる。
  • (仮定3)実行パスの総数は有限である。
  • (仮定4)実行パスを選択するときの確率は等確率である。

一般にバグは1つの実行パスに複数含まれている可能性がありますが、仮定1に示すように1つのみ含まれていると仮定しています。すなわちバグ数は”実行パスが正しく実行できなかった”数を表すことになります。 また、実行パスの実行回数$n$、$n \gt 0$ をカウントするとき、この実行回数には、1つのバグが正しく修正されたかを確認するために、たとえ複数回実行パスを実行したとしてもその回数は含まれないものとします。


2.2 ランダム実行モデルと逐次実行モデルについて


2.2.1 ランダム実行モデルの物理モデル

ランダム実行モデルは、実行パスをランダムに選択して実行するモデルのことです。このモデルでは1つの実行パスは繰り返し複数回実行されることになります。 ランダム実行モデルと同等の物理モデルの例を図3に示し、このモデルを使ってバグの摘出について説明します。

図3に示すように1つの箱Aがあり、その中に複数のボールがあるとします。ボールの色は白と黒があり、箱Aの中から1個ずつ取り出せるように箱Aには穴が開いています。箱Aの中は外からは見えないものとします。この箱Aが1つのソフトウェアを表し、箱Aの中のボールが実行パスを表しています。この箱Aの中のボールを1個取り出すことが1つの実行パスを実行することを表します。また、白のボールはバグが無い実行パスを、黒のボールはバグがある実行パスを表します。ボールはすべて同じ形状で均一に作られており、ボールを選択する確率は等確率であるとします。ボールは1度に1個取り出すものとします。また、箱Aの中から取り出されたボールの色が白のときはそのボールをそのまま箱Aの中に戻し(図3の①)、ボールの色が黒のときはそれを白のボールに変えて箱Aの中に戻します(図3の②)。この黒いボールを白いボールに変えることがバグの修正に相当します。このような動作を繰り返し実行すると、箱Aの中のボールの総数は変化しませんが、箱Aの中の黒のボールの数は減少し、箱Aから取り出された黒のボールの数は増加していくことになります。

このモデルは、利用者がソフトウェアを任意に実行していく場合や、テスト工程において機能の確認を行うためにランダムにソフトウェアを実行する場合等が該当します。 このモデルでバグを全て摘出するには、バグが収束するまで繰り返し実行パスを実行することが重要です。

図3 ランダム実行モデルの物理モデル

図3 ランダム実行モデルの物理モデル


2.2.2 逐次実行モデルの物理モデル

逐次実行モデルとは、実行パスの実行順を予め決めておき、その順に従い実行するモデルのことです。このモデルでは1つの実行パスは1回のみ実行されます。 逐次実行モデルの物理モデルを図4に示します。ランダム実行モデルの場合と異なり、ボールが入る箱(箱B)はボールが一列に並べて入る大きさで細長い形状をしています。この箱Bは図4のように横からボールを1個ずつ取り出すために穴が開いています。箱Bの中には白と黒のボールが入っていますが、どのような順序で入っているかは、箱の外からは見えないものとします。また箱Bの中からボールを1個ずつ順に取り出しますが(図4の①)、取り出したボールは箱Bには戻さず、別の箱Cに入れます。箱Bの中のボールが無くなるまで、この動作を繰り返します。

図4は、テスト工程において実行パスをテストケースの順に1回だけ実行していくモデルになっています。このモデルでは、全ての実行パスを実行することによって、全てのバグを摘出することができる点が特徴です。したがってテスト時においてはテストの網羅性が重要になります。

図4 逐次実行モデルの物理モデル

図4 逐次実行モデルの物理モデル

 

3.ソフトウェアの実行の数理モデル

ソフトウェアの実行とは、ソフトウェアの中に$N_{p}$個の実行パスが含まれているとき、$N_{p}$個の実行パスの中から1つの実行パスを選択して実行することです。このモデルとしてランダム実行モデルと逐次実行モデルの物理モデルを示しましたが、以下では数式を用いてこの2つのモデルのバグの摘出過程について説明します。


3.1 ランダム実行モデル

ソフトウェアの任意の実行パスを第$i$回目に実行した結果、バグが発見されたかどうかを確率変数$X_{i}$で表し、 \[ X_{i} = \begin{cases} 0 & (実行パスにバグが含まれていなかった場合) \\ 1 & (実行パスにバグが含まれていた場合) \end{cases} \] とします。

また、$X_{i}$の和$S_{n}$を以下のように定義します。 \[ S_{n} = X_{1} + X_{2} + X_{3} + \ldots + X_{n} \] この$S_{n}$は、$n$回目までの実行パスの実行の結果、発見されたバグの累積数を表しています。

$S_{n}=x$となる確率を$P(S_{n}=x)$、$S_{n}=x$となった後に$S_{n+1}=x+1$となる条件付確率を$P(S_{n+1}=x+1 | S_{n}=x)$ と表すことにします。ここで$P(S_{0}=0)=1$、$P(S_{0}=x)=0$とします。 また、$N_{p}$個の実行パスに含まれる全バグ数を$a$、$a \ll N_{p}$とすると、実行パスを$n$回選択して実行し、バグが$x$個 $(x \ge 0)$ 発見されたとき、$n+1$回目にバグを含む実行パスを選択する確率は、 \[ P(S_{n+1}=x+1 | S_{n}=x) = \frac{a-x}{N_{p}} \qquad \ldots \text{(3-1-1)} \] バグを含まない実行パスを選択する確率は、 \[ P(S_{n+1}=x | S_{n}=x) = 1- \frac{a-x}{N_{p}} \qquad \ldots \text{(3-1-2)} \] となります。 仮定1より、1回の実行によって1個のバグが摘出されるため、$n+1$回目にバグが$x+1$個になっている確率$S_{n+1}=x+1$は、実行パスを$n$回実行しバグが$x$個発見され、$n+1$回目にバグが1個発見される確率$P(S_{n+1}=x+1 | S_{n}=x)P(S_{n}=x)$と、実行パスを$n$回実行してバグが$x+1$個発見されて、$n+1$回目にバグが発見されないで$x+1$個のままとなっている確率$P(S_{n+1}=x+1 | S_{n}=x+1)P(S_{n}=x+1)$の和です。すなわち、 \[ P(S_{n+1}=x+1) = P(S_{n+1}=x+1 | S_{n}=x+1)P(S_{n}=x+1) \\\\ + P(S_{n+1}=x+1 | S_{n}=x)P(S_{n}=x) \qquad \ldots \text{(3-1-3)} \] \[ P(S_{n+1}=x+1) = (1- \frac{a-(x+1)}{N_{p}})P(S_{n}=x+1) + \frac{a-x}{N_{p}}P(S_{n}=x) \\\\ \qquad \ldots \text{(3-1-4)} \] 実行パスを$n$回選択して実行し、バグが$x$個発見される確率$P(S_{n}=x)$を、$P(S_{n}=x)=P_{x}(n)$のように書くことにすると、 \[ P_{x+1}(n+1) = (1- \frac{a-(x+1)}{N_{p}})P_{x+1}(n) + \frac{a-x}{N_{p}}P_{x}(n) \qquad \ldots \text{(3-1-5)} \] となります。ここで$P_{0}(0)=1$、$P_{x}(0)=0$です。 この式を変形すると、以下のように表すことができます。 \[ \frac{P_{x+1}(n+1) - P_{x+1}(n)}{1} = - \frac{a-(x+1)}{N_{p}}P_{x+1}(n) + \frac{a-x}{N_{p}}P_{x}(n) \] この式を解くために、 以下のように近似します。 \[ \frac{d}{dn}P_{x+1}(n) = - \frac{a-(x+1)}{N_{p}}P_{x+1}(n) + \frac{a-x}{N_{p}}P_{x}(n) \qquad \ldots \text{(3-1-6)} \]

この式(3-1-6)の微分方程式を解いて$P_{x}(n)$を求めるには、$P_{1}(n)$、$P_{2}(n)$、$P_{3}(n)$と順に解くことで、これらの解の規則性から一般解を導き出すことができます。

まず$P_{1}(n)$の解を得る前に、$P_{0}(n)$を得ておく必要があります。 $P_{0}(n)$は、バグがない実行パスを$n$回選択することであり、$P_{0}(0)=1$であることを考慮すると、 \[ P_{0}(n) = (1 - \frac{a}{N_{p}})^{n} \qquad \ldots \text{(3-1-7)} \] となりますが、微分方程式を簡単に解くために、式(3-1-7)を連続関数で近似することにします。

$e^{x}$はマクローリン展開すると、 \[ e^{x} = 1 + x + \frac{1}{2} x^{2} + \ldots \] であるため、 \[ e^{- \frac{a-x}{N_{p}}} = 1 - \frac{a-x}{N_{p}} + \frac{1}{2} ( \frac{a-x}{N_{p}} )^2 + \ldots \] になります。

$N_{p} \gg a-x$、$a \ge x$より、$0 \le \frac{a-x}{N_{p}} \ll 1$であるため、2次の項以降は無視すると、 \[ e^{- \frac{a-x}{N_{p}}} \approx 1 - \frac{a-x}{N_{p}} \] になります。これより$P_{0}(n)$は、 \[ P_{0}(n) = (1 - \frac{a}{N_{p}})^{n} \approx (e^{- \frac{a}{N_{p}}})^{n} = e^{- \frac{a}{N_{p}} n } \qquad \ldots \text{(3-1-8)} \] になります。これを用いると$P_{1}(n)$の微分方程式は、 \[ \frac{d}{dn}P_{1}(n) + \frac{a-1}{N_{p}}P_{1}(n) = \frac{a}{N_{p}} e^{- \frac{a}{N_{p}}n} \qquad \ldots \text{(3-1-9)} \] になります。 この微分方程式は、次の微分方程式、 \[ \frac{d}{dx}f + P(x)f = Q(x) \] の一般解、 \[ f = exp(- \int{P(x) dx}) \cdot \{ \int{Q(x) \cdot exp( \int{P(x) dx} ) dx} + C \} \] を用いて解くことができ、 \[ P_{1}(n) = a \cdot (1 - e^{- \frac{1}{N_{p}}n} ) \cdot (e^{- \frac{n}{N_{p}}})^{a-1} \qquad \ldots \text{(3-1-10)} \] を得ることができます。 同様の方法で、$P_{2}(n)$について解くと、 \[ P_{2}(n) = \frac{a \cdot (a-1)}{2} \cdot (e^{- \frac{n}{N_{p}}})^{a-2} \cdot (1 - e^{- \frac{n}{N_{p}}} )^{2} \qquad \ldots \text{(3-1-11)} \] $P_{3}(n)$については、 \[ P_{3}(n) = \frac{a \cdot (a-1) \cdot (a-2)}{3 \cdot 2} \cdot (e^{- \frac{n}{N_{p}}})^{a-3} \cdot (1 - e^{- \frac{n}{N_{p}}} )^{3} \qquad \ldots \text{(3-1-12)} \] を得ます。

以上のことから、$P_{x}(n)$は以下のようになります。

ランダム実行モデルの確率質量関数$P_{x}(n)$: \[ P_{x}(n) = {}_{a}C_{x} \cdot (1 - e^{- \frac{n}{N_{p}}} )^{x} \cdot (e^{- \frac{n}{N_{p}}})^{a-x} \qquad \ldots \text{(3-1-13)} \]

この式(3-1-13)は2項信頼性モデル1)の1つの特別な形式となっています。

ここで、$1-e^{- \frac{n}{N_{p}}} = p$ とおくと、 \[ P_{x}(n) = {}_{a}C_{x} \cdot p^{x} \cdot (1 - p)^{a-x} \] であり、これは二項分布の形式になっています。また$p$は$x$に依存していないことから、 \[ \sum_{x=0}^{a}P_{x}(n) = \sum_{x=0}^{a} {}_{a}C_{x} \cdot p^{x} \cdot (1 - p)^{a-x} = (p + (1-p))^a = 1 \] になります。


[平均と分散]

二項分布の平均、分散の式を用いて、$P_{x}(n)$の平均$\bar{x}$、分散$s^{2}$を計算すると以下のようになります。

ランダム実行モデルの平均$\bar{x}$: \[ \bar{x} = a \cdot p = a \cdot (1 - e^{- \frac{n}{N_{p}}}) \qquad \ldots \text{(3-1-14)} \] ランダム実行モデルの分散$s^{2}$: \[ s^{2} = a \cdot p \cdot (1-p) = a \cdot (1 - e^{- \frac{n}{N_{p}}}) \cdot e^{- \frac{n}{N_{p}}} \qquad \ldots \text{(3-1-15)} \]

$n \to \infty$のとき、$ \bar{x} \to a$、$ s^2 \to 0$となり収束することがわかります。


[網羅率]

ここで、式(3-1-14)の$a$を、$a = N_{p}$とした時について考えてみます。

式(3-1-14)から、 \[ \bar{x}_{N_{p}} = N_{p} \cdot (1 - e^{- \frac{n}{N_{p}}}) \] ここで、$\bar{x}_{N_{p}}$は、実行パスを$n$回選択して実行した時、1回以上実行された実行パスの累積数の平均を表しています。この式から、 \[ \frac{\bar{x}_{N_{p}}}{N_{p}} = (1 - e^{- \frac{n}{N_{p}}}) \qquad \ldots \text{(3-1-16)} \] を得ますが、この$\frac{\bar{x}_{N_{p}}}{N_{p}}$は実行パスの網羅率(カバレッジ)を表しています。

式(3-1-14)に式(3-1-16)を代入して式を変形すると、 \[ \frac{\bar{x}}{a} = \frac{\bar{x}_{N_{p}}}{N_{p}} = (1 - e^{- \frac{n}{N_{p}}}) \qquad \ldots \text{(3-1-17)} \] を得ることができ、この式から、 \[ \bar{x} = \frac{\bar{x}_{N_{p}}}{N_{p}} \cdot a \qquad \ldots \text{(3-1-18)} \] を得ることできます。

発見されたバグの累積数の平均$\bar{x}$は、実行パスの網羅率(カバレッジ)と全バグ数の積に比例していることがわかります。


[残存バグ数]

ソフトウェアに含まれる残存バグ数$Δ\bar{x}=a-\bar{x}$は以下のようになります。

ランダム実行モデルの残存バグ数$Δ\bar{x}$: \[ Δ\bar{x}=a-\bar{x} = a \cdot (1 - \frac{\bar{x}_{N_{p}}}{N_{p}} ) = a \cdot e^{- \frac{n}{N_{p}}} \qquad \ldots \text{(3-1-19)} \]


残存バグ数を減らすためには、網羅率$\frac{\bar{x}_{N_{p}}}{N_{p}}$を1に近づけることと、ソフトウェアに作り込む全バグ数$a$を減らすことが重要になります。網羅率$\frac{\bar{x}_{N_{p}}}{N_{p}}$は式(3-1-17)より、実行パスをランダムに実行する回数$n$をできるだけ大きくすることにより高めることができ、式(3-1-19)に示すように残存バグ数を減らすことができます。

 


3.2 逐次実行モデル

実行パスの実行順が予め決められており、その順序に従って1つずつ実行することを考ます。実行パスの実行によりバグが発見されれば直ちに修正し、確認のために再度実行しますが、これは3.1と同様に実行回数には含まないものとします。ランダム実行モデルと異なり、1度実行した実行パスは再度選択して実行されることはないため、実行順に従い1回実行されたら終了になります。

以下ではこの逐次実行モデルについての確率分布について考えてみます。

[考え方1]

$N_{p}$個の実行パスに含まれる全バグ数を$a$、$a \ll N_{p}$とし、実行パスを実行順に従い$n$回取り出して実行し、バグが$x$個 $(x \ge 0)$ 発見されたとき、$n+1$回目にバグを含む実行パスを選択する確率は、 \[ P(S_{n+1}=x+1 | S_{n}=x) = \frac{a-x}{N_{p}-n} \qquad \ldots \text{(3-2-1)} \] バグを含まない実行パスを選択する確率は、 \[ P(S_{n+1}=x | S_{n}=x) = 1- \frac{a-x}{N_{p}-n} \qquad \ldots \text{(3-2-2)} \] になります。ランダム実行モデルと異なり実行パスは1度実行されると再度実行されることはないため、分母が$N_{p}-n$になっています。
バグが摘出される時の確率の式は、ランダム実行モデルの節で述べた式(3-1-3)と同じであり、この式に式(3-2-1)と式(3-2-2)を適用します。 \[ P(S_{n+1}=x+1) = (1- \frac{a-(x+1)}{N_{p}-n})P(S_{n}=x+1) + \frac{a-x}{N_{p}-n}P(S_{n}=x) \\\\ \qquad \ldots \text{(3-2-3)} \] ランダム実行モデルの時と同様に、実行パスを$n$回実行して、バグが$x$個発見される確率$P(S_{n}=x)$を、$P(S_{n}=x)=P_{x}(n)$のように書くことにすると、 \[ P_{x+1}(n+1) = (1- \frac{a-(x+1)}{N_{p}-n})P_{x+1}(n) + \frac{a-x}{N_{p}-n}P_{x}(n) \qquad \ldots \text{(3-2-4)} \] となります。ここで$P_{0}(0)=1$、$n < x$の時の$P_{x}(n)=0$、$P_{-1}(n)=0$です。
この式(3-2-4)を順に解いていきます。
$x=-1$、$n=0$の時、式(3-2-4)は、 \[ P_{0}(1) = (1- \frac{a}{N_{p}})P_{0}(0) + \frac{a+1}{N_{p}}P_{-1}(0) \] \[ P_{0}(1) = (1- \frac{a}{N_{p}}) \] $x=-1$、$n=1$の時、式(3-2-4)は、 \[ P_{0}(2) = (1- \frac{a}{N_{p}-1})P_{0}(1) + \frac{a+1}{N_{p}-1}P_{-1}(1) \] \[ P_{0}(2) = \frac{ (N_{p}-a)(N_{p}-a-1)}{N_{p}(N_{p}-1)} \] $x=-1$、$n=2$の時、式(3-2-4)は、 \[ P_{0}(3) = (1- \frac{a}{N_{p}-2})P_{0}(2) + \frac{a+1}{N_{p}-2}P_{-1}(2) \] \[ P_{0}(3) = \frac{ (N_{p}-a)(N_{p}-a-1)(N_{p}-a-2)}{N_{p}(N_{p}-1)(N_{p}-2)} \] $x=0$、$n=0$の時、式(3-2-4)は、 \[ P_{1}(1) = (1- \frac{a-1}{N_{p}})P_{1}(0) + \frac{a}{N_{p}}P_{0}(0) \] \[ P_{1}(1) = \frac{a}{N_{p}} \] $x=0$、$n=1$の時、式(3-2-4)は、 \[ P_{1}(2) = (1- \frac{a-1}{N_{p}-1})P_{1}(1) + \frac{a}{N_{p}-1}P_{0}(1) \] \[ P_{1}(2) = \frac{ 2a(N_{p}-a)}{N_{p}(N_{p}-1)} \] $x=0$、$n=2$の時、式(3-2-4)は、 \[ P_{1}(3) = (1- \frac{a-1}{N_{p}-2})P_{1}(2) + \frac{a}{N_{p}-2}P_{0}(2) \] \[ P_{1}(3) = \frac{ 3a(N_{p}-a)(N_{p}-a-1)}{N_{p}(N_{p}-1)(N_{p}-2)} \] $x=0$、$n=3$の時、式(3-2-4)は、 \[ P_{1}(4) = (1- \frac{a-1}{N_{p}-3})P_{1}(3) + \frac{a}{N_{p}-3}P_{0}(3) \] \[ P_{1}(4) = \frac{ 4a(N_{p}-a)(N_{p}-a-1)(N_{p}-a-2)}{N_{p}(N_{p}-1)(N_{p}-2)(N_{p}-3)} \] $x=1$、$n=1$の時、式(3-2-4)は、 \[ P_{2}(2) = (1- \frac{a-2}{N_{p}-1})P_{2}(0) + \frac{a-1}{N_{p}-1}P_{1}(1) \] \[ P_{2}(2) = \frac{a(a-1)}{N_{p}(N_{p}-1)} \] $x=1$、$n=2$の時、式(3-2-4)は、 \[ P_{2}(3) = (1- \frac{a-2}{N_{p}-2})P_{2}(2) + \frac{a-1}{N_{p}-2}P_{1}(2) \] \[ P_{2}(3) = \frac{ 3a(a-1)(N_{p}-a)}{N_{p}(N_{p}-1)(N_{p}-2)} \] $x=1$、$n=3$の時、式(3-2-4)は、 \[ P_{2}(4) = (1- \frac{a-2}{N_{p}-3})P_{2}(3) + \frac{a-1}{N_{p}-3}P_{1}(3) \] \[ P_{2}(4) = \frac{ 6a(a-1)(N_{p}-a)(N_{p}-a-1)}{N_{p}(N_{p}-1)(N_{p}-2)(N_{p}-3)} \] $x=1$、$n=4$の時、式(3-2-4)は、 \[ P_{2}(5) = (1- \frac{a-2}{N_{p}-4})P_{2}(4) + \frac{a-1}{N_{p}-4}P_{1}(4) \] \[ P_{2}(5) = \frac{ 10a(a-1)(N_{p}-a)(N_{p}-a-1)(N_{p}-a-2)}{N_{p}(N_{p}-1)(N_{p}-2)(N_{p}-3)(N_{p}-4)} \] \[ P_{2}(5) = \frac{{}_{a}P_{2} \cdot {}_{N_{p}-a}P_{3} \cdot {}_{5}C_{2} }{{}_{N_{p}}P_{5}} \] 以上から一般解として、 \[ P_{x}(n) = \frac{{}_{a}P_{x} \cdot {}_{N_{p}-a}P_{n-x} \cdot {}_{n}C_{x} }{{}_{N_{p}}P_{n}} \] を得ることができます。 ここで、右辺の${}_{a}P_{x}$などの$P$は順列(Permutation)を表します。
また、以下の式を使うことで、 \[ {}_{N_{p}}P_{n} = n! \\\\ {}_{a}P_{x} = x! \cdot {}_{a}C_{x} \\\\ {}_{N_{p}-a}P_{n-x} = (n-x)! \cdot {}_{N_{p}-a}C_{n-x} \\\\ {}_{n}C_{x} = \frac{n!}{x! \cdot (n-x)!} \] $P_{x}(n)$の一般解は以下のようになり、超幾何分布の式を得ることができます。

逐次実行モデルの確率質量関数$P_{x}(n)$: \[ P_{x}(n) = \frac{{}_{N_{p}-a}C_{n-x} \cdot {}_{a}C_{x} }{ {}_{N_{p}}C_{n} } \qquad \ldots \text{(3-2-5)} \]

[考え方2]

$N_{p}$個の実行パスから$n$個の実行パスを選択する組み合わせ数は${}_{N_{p}}C_{n}$、$a$個のバグから$x$個のバグを抽出する組み合わせ数は${}_{a}C_{x}$、$N_{p}-a$個のバグのない実行パスからバグの無い$n-x$個を取り出す組み合わせ数は${}_{N_{p}-a}C_{n-x}$です。 $n$個の実行パスを実行して$x$個のバグが抽出される確率を$P_{x}(n)$とします。$N_{p}$個の中から$n$個の実行パスを選択し、その中に$n-x$個のバグがない実行パスと、$x$個のバグを含む実行パスがある組み合わせ数は、 \[ {}_{N_{p}-a}C_{n-x} \cdot {}_{a}C_{x} \qquad \ldots \text{(3-2-6)} \] \[ {}_{N_{p}}C_{n} \cdot P_{x}(n) \qquad \ldots \text{(3-2-7)} \] であり、式(3-2-6)と式(3-2-7)は等しくなるため、 \[ {}_{N_{p}-a}C_{n-x} \cdot {}_{a}C_{x} = {}_{N_{p}}C_{n} \cdot P_{x}(n) \] になります。 したがって、$P_{x}(n)$として、 \[ P_{x}(n) = \frac{ {}_{N_{p}-a}C_{n-x} \cdot {}_{a}C_{x} }{ {}_{N_{p}}C_{n} } \qquad \ldots \text{(3-2-8)} \] の超幾何分布の式を得ることができます。


[平均と分散]

超幾何分布を示す式(3-2-5)、式(3-2-8)から平均$\bar{x}$、分散$s^{2}$を計算すると以下のようになります。ここで$p$は、$p = \frac{a}{N_{p}}$です。

逐次実行モデルの平均$\bar{x}$: \[ \bar{x} = n \cdot p = \frac{a}{N_{p}}n \qquad \ldots \text{(3-2-9)} \] 逐次実行モデルの分散$s^{2}$: \[ s^{2} = \frac{ n \cdot p \cdot (1-p) \cdot (N_{p} - n) }{ N_{p} - 1 } = \frac{ n \cdot \frac{a}{N_{p}} \cdot (1 - \frac{a}{N_{p}}) \cdot (1 - \frac{n}{N_{p}}) }{ 1 - \frac{1}{N_{p}} } \qquad \ldots \text{(3-2-10)} \]

[網羅率]

式(3-2-9)から、 \[ \frac{\bar{x}}{a} = \frac{n}{N_{p}} \qquad \ldots \text{(3-2-11)} \] を得ることができます。逐次実行モデルの$\frac{n}{N_{p}}$は、実行パスの網羅率(カバレッジ)を表すため、 $n \to N_{p}$として網羅率を$\frac{n}{N_{p}} \to 1$にすることにより、$\bar{x} \to a$にすることができます。

式(3-2-10)から、分散$s^{2}$は$n=0$、$n=N_{p}$のとき分散は$0$です。 平均$\bar{x}$は、$\bar{x}=\frac{a}{N_{p}}n$なので、$n$が1つずつ時間の経過と共に増加するとき、$\bar{x}$は直線的に増加します。


[残存バグ数]

式(3-2-9)から、ソフトウェアに含まれる残存バグ数$Δ\bar{x}=a-\bar{x}$は以下のようになります。

逐次実行モデルの残存バグ数$Δ\bar{x}$: \[ Δ\bar{x}=a - \bar{x} = a \cdot (1 - \frac{n}{N_{p}}) \qquad \ldots \text{(3-2-12)} \]


残存バグ数を減らすためには、網羅率$\frac{n}{N_{p}}$を1に近づけることと、ソフトウェアに作り込む全バグ数$a$を減らすことが重要になります。


3.3 ランダム実行モデルの特徴

ランダム実行モデルでは、ソフトウェアの実行を何回も繰り返すことによってほとんどのバグを摘出することができます。

図3の箱Aから取り出された黒のボールの数について考えてみます。 箱Aの中のボールの総数が$N_{p}$であり、黒のボールの総数が$a$、ある時点までに取り出された黒のボールの数が$x$であるとすると、箱Aの中から黒のボールを取り出す確率は$\frac{a-x}{N_{p}}$であり、3.1で述べたように、確率質量関数は式(3-1-13)、黒のボールの累積数の平均は式(3-1-14)、分散は式(3-1-15)です。

図3($N_{p}=10$、$a=4$)の場合の実行結果の例を図5に示します。図5の赤の上限、下限の点線は、式(3-1-15)から求めた標準偏差$s$の2倍を、上限は式(3-1-14)から計算した平均に加算し、下限は式(3-1-14)から計算した平均から減算(負の数の場合は0)して表示しています。図5の赤の実線は、式(3-1-14)の平均を表しています。図5に示すように、実行回数が増加して累積数が一定の数値に収束してくると、上限と下限の幅は狭くなっています。これはバグの累積数の予測誤差が小さくなっていることを表しています。

図5の例に示すように、摘出されたバグを表す黒のボールの累積数は徐々に増加し収束しますが、全てのバグを摘出するには、収束するまで繰り返しボールの取り出しを行う必要があります。

図5 図3のランダム実行モデルの結果の例

図5 図3のランダム実行モデルの結果の例

図6の箱Dのように内部が複雑な形状をしている場合は、黒のボールの摘出漏れがある可能性があります。 箱はソフトウェアを表すため、箱の形状が複雑なことは、ソフトウェアの構造が複雑であることを表します。実行されていない実行パスがないことが重要であり、そのためにはソフトウェアの構造を十分考慮しておく必要があることがわかります。

図6 複雑な形状の箱の例

図6 複雑な形状の箱の例


3.4 逐次実行モデルの特徴

ランダム実行モデルではバグの摘出数とテストの実行回数をグラフにすると図5のように収束する曲線になりますが、逐次実行モデルでは平均的には式(3-2-9)に示すように直線になります。

図4の場合について、箱Bに入ってくる黒のボールの数について考えてみます。この場合は、累積バグ数の平均は式(3-2-9)、分散は式(3-2-10)です。

図4($N_{p}=10$、$a=4$)の場合の実行結果の例を図7に示します。 図7の上限、下限の点線は式(3-2-10)から求めた標準偏差$s$の2倍を、上限は式(3-2-9)から計算した平均に加算し、下限は式(3-2-9)から計算した平均から減算(負の数の場合は0)して表示しています。

逐次実行モデルの場合は、ランダム実行モデルのようにバグの収束が図5のようにグラフから把握できません。そのため、テストの網羅性が非常に重要になります。

図7 図4の逐次実行モデルの結果の例

図7 図4の逐次実行モデルの結果の例

図8の箱Eのように、途中でボールの抽出をやめた場合は、黒のボールの摘出漏れがある可能性があります。これは、実行パスを漏れなく実行することが重要であることを表しています。

また、図5と図7を比較してわかるように、ランダム実行モデルは逐次実行モデルと比較して、かなり実行パスの実行回数が多くなります。

同一のソフトウェア(実行パスの総数$N_{p}$、全バグ数$a$)についてランダム実行モデルと逐次実行モデルでテストを行う場合を考えます。ランダム実行モデルの実行パスの実行回数$n_{r}$、逐次実行モデルの実行パスの実行回数を$n_{s}$とすると、式(3-1-14)と式(3-2-9)から同一のバグ数$x_{n}$が摘出された時は、 \[ x_{n} = a \cdot (1 - e^{- \frac{n_{r}}{N_{p}}}) = \frac{n_{s}}{N_{p}}a \] となります。この式から以下の式が得られますが、 \[ (1 - e^{- \frac{n_{r}}{N_{p}}}) = \frac{n_{s}}{N_{p}} \] 右辺が$n_{s} \to N_{p}$のとき、網羅率$\frac{n_{s}}{N_{p}} \to 1$ですが、左辺が \[ (1 - e^{- \frac{n_{r}}{N_{p}}}) \to 1 \] となるのは、$n_{r} \to \infty$のときであり、明らかに$n_{s} \ll n_{r}$となり、ランダム実行モデルの方が逐次実行モデルよりも実行回数がかなり多くなることがわかります。

テストの効率性という観点からは、逐次実行モデルの方がランダム実行モデルよりもかなり効率が良いことは明らかです。

図8 途中でボールの摘出をやめた例

図8 途中でボールの摘出をやめた例


4.まとめ

ランダム実行モデル、逐次実行モデルから得られた結果について、概要を以下にまとめます。

  • ランダム実行モデルで実行パスを実行する場合、バグの累積数は指数曲線のように徐々に増加して収束する。バグを全て発見するためには、実行パスの漏れをなくし網羅率を1に近づけるか、バグの累積数が収束するまで、ランダムに実行パスを選択して実行しなければならない。この時、実行パスの漏れがないように、ソフトウェアの構造などを考慮して実行する必要がある。
  • 逐次実行モデルで実行パスを実行する場合、バグの累積数は直線的に徐々に増加する。バグを全て発見するためには、実行パスの漏れをなくし網羅率を1に近づけなければならない。
  • テストの効率性という観点からは、逐次実行モデルの方がランダム実行モデルよりも効率がかなり良い。
  • ランダム実行モデルは、実行パスのランダムな実行が前提となっている。そのためソフトウェアのランダムテストや稼働後におけるランダムな実行において、バグの発生をモデル化する際に利用することができる。
  • 逐次実行モデルは、テストケースを順に実行する場合などにおいて、バグの発生をモデル化する際に利用することができる。

上記のように、テスト工程でテストケースの順に従ってテストを実施する場合は、逐次実行モデルの適用が妥当だと考えます。但し、テスト工程でランダムテストなどを実施する場合は、ランダム実行モデルの適用が妥当だと考えます。また、ソフトウェアの稼働後に利用者がほぼランダムにソフトウェアを使う場合は、ランダム実行モデルで近似できる場合があると考えます。
バグの累積数が指数曲線のように収束するには、実行パスのランダム実行が重要な条件になります。
また、式(3-1-19)と式(3-2-12)で明らかなように、ソフトウェアの品質向上のためには、開発時に作り込まれるバグを少なくすること、テストやレビューなどの検証活動やプロジェクト開始当初の要件調整などで、網羅性が高くなるような活動を行うことが重要になります。


参考文献

1) 山田茂, 大寺浩志著:“ソフトウェアの信頼性 ~理論と実践的応用~”, ソフト・リサーチ・センター, (1990)



本ブログの記載内容に関する免責事項

  • 著者は、数学、特に確率統計の専門家ではありませんので、本ブログに記載した内容については厳密性の欠如や誤りが含まれているかもしれません。しかし、導出された結果については、著者の現場経験から概ね妥当であると考えており、そのためブログとして著者の考えをまとめました。「プライバシーポリシー及び免責事項」に記載していますが、本ブログの内容の利用により生じた損害に対して、いかなる理由であっても著者は一切の責任を負いませんので予めご了承ください。
  • 本ブログの内容は、予告なく変更・削除する場合がありますのでご了承ください。