PICTの組み合わせ生成アルゴリズム
この説明では、前回の記事にある生成の前準備である、単独のすべてのペアの組み合わせができているものとします。
この説明は、前回の記事と同じPICTの開発者であるJacek Czerwonka氏が2006年に発表した論文「Pairwise Testing in Real World」からの引用です。
インデントが重要なので画像ファイルでアップしました。
以上です。
文章中判別しにくい文字については、前回の記事を参考にして原本を参照してください。
このアルゴリズムの説明で#が先頭にある文章は、PICTの原型ファイルの機能を考慮に入れたものと思われます。この説明は１つのテストケースを生成する場合の説明であり、テストケース全体を生成する場合を説明したものではありません。
また、PICTで生成条件値を指定することができますが、これはアルゴリズム中の「未対象組み合わせがある場合は」の処理で複数のスロットが候補にあがったときにどの候補を選択するのかに使われるのではないかと思われます。
それでは、また。
PICTで多数の値を制約で指定するとTC生成に膨大な時間がかかる理由
PICTでは、通常考えられるレベルの複雑さの制約を指定しても、テストケース（TC)生成時間にはそれほど影響しません。しかし、各パラメータが多くの値を持つ場合、制約条件、制約対象に多くのパラメータの値を記入した制約を多数指定すると、TC生成時間は膨大なものとなります。このとき、PICTは数百MB以上のメモリを占有し、ディスクとの間でスワップを繰り返し、実効処理速度は著しく低下します。
この理由は、PICTが制約を処理するアルゴリズムが、多数のパラメータが指定された場合、処理時間が急増する性質を持っているためと考えられます。 どうしてこのような性質を持っているのか、次に説明します。
以降の説明では、PICTの開発者であるJacek Czerwonka氏が2006年に発表した論文「Pairwise Testing in Real World」からの引用です。この論文は、Pairwise Testing のサイトの Research Papers のページの33番にあります。まず、PICTのテストケース生成プロセスについて説明し、次に制約に関して説明します。
PICTのテストケース生成プロセスは、主に（1）準備、（2）生成の2段階で構成されます。
準備段階では、PICTは生成段階で必要となるすべての情報を計算します。その中には、網羅するすべてのパラメータの組み合わせである、集合Pが含まれます。網羅する値の組み合わせは、それぞれパラメータ組み合わせ構成に反映されます。
たとえば、3種類のパラメータA、B、およびC（値の数はAとBがそれぞれ2つ、Cが3つ）が与えられた状態でペアワイズ生成を実行すると、AB、AC、およびBCの3種類のパラメータ組み合わせ構成が設定されます。各パラメータは、特定のパラメータの組み合わせに関係する予想値の組み合わせに対応した複数のスロットを持ちます（ABは4スロット、ACとBCは6スロット）（Figure 4を参照）。
各スロットは、未対象、網羅、除外のいずれかにマーキングされます。パラメータのすべての組み合わせにおいて、すべての未対象スロットが網羅する組み合わせの集合を構成します。仮にモデルに制約条件を定義したとすると、それらは一連の除外条件（最終的に出力を禁止する値の組み合わせ）に変換されます。次いで、パラメータ組み合わせ構成の対応スロットが除外にマーキングされ、網羅する組み合わせから外されます。こうした特定の組み合わせを満たすテストケースをアルゴリズムが生成すると、そのスロットは網羅となります。未対象スロットがなくなれば、アルゴリズムは終了します。
コア生成アルゴリズムは、グリーディヒューリスティック手法です。この手法は一回に1つのテストケースを作成して局所的に解を最適化します。
PICTは、制約条件を内部的に除外条件と呼ばれる組み合わせの集合に変換し、それらを使用してパラメータ組み合わせ構成の該当するスロットを除外としてマーキングします。実用上、この方法には以下に示す課題があります。
パラメータ組み合わせ構成において、組み合わせを除外として直接マーキングできない場合があります。Figure 10 の例では、3要素の除外条件を作成していますが、パラメータ組み合わせ構成は同時に2つのパラメータしか参照しません。言い換えれば、除外対象の組み合わせをマーキングするために使用可能なパラメータ組み合わせ構成ABCが存在しません。このような場合は、パラメータ組み合わせ構成ABCが新規に設定されます。該当する組み合わせは除外としてマーキングされ、残りは網羅としてマーキングされます。したがって、生成アルゴリズムは、実際にA:0、B:0、およびC:1の組み合わせを選択することなく、AB、AC、およびBCについて考えられるすべての組み合わせを網羅することになります。
以上までが引用です。
Figure 10 にあるように、制約に関係するパラメータの数が多くなると、全数組み合わせのため事前の組み合わせが膨大な数になる場合があります。特にパラメータに含まれる値が多い場合です。例えば、各パラメータが30個の値を持っている場合、1つの制約で制約条件と制約対象が合わせて4つのとき、新規に設定される組み合わせは30の4乗で810,000となります。こうした制約がいくつかあるだけで、それらを処理するために大量のメモリを必要とすると考えられます。
こうしたことからPICTでは、各パラメータが多くの値を持つ場合に、制約条件、制約対象に多くのパラメータの値を記入した制約を多数指定した場合、生成時間が極端に長くなると考えられます。
この他に、PICTでは1つの制約が制約条件、制約対象それぞれ1つの場合でも、多くの値を指定すると生成時間が極端に長くなる性質もあります（ユーザーズマニュアルの最後の例）。この場合は、当然のことですがメモリ量の増加は発生しません。少ないメモリ量で生成時間が極端に長くなる現象です。この現象の理由についてはまだわたしには不明です。
それでは、また。
PICTとJennyのテストケース数の比較
AllPairIIは、PICTとJennyの２つの生成エンジンをサポートしています。それでは２つのエンジンの生成するテストケー数（TC数）にはどの程度の違いがあるでしょうか。
ここでは、パラメータ数を5個で固定とし、各パラメータの値の数を3から10まで変化させた場合に生成したTC数を比較してみました。生成は最小テストケース生成で100回生成を行なった結果です。
表の見方：PICTとJennyの欄の”／”の左は最小数、右はデフォルト数。TC比率はPICTとJennyの結果をまとめて、より少ないTC数を、より多いデフォルト数で割って100をかけた値。
表の結果から、この条件では一部を除いてJennyの生成TC数がPICTより少ないことが分かります。値の数が3の場合のみPICTが少ない値となっています。AllPairIIは、２つのエンジンをサポートしているため、より少ないTC数を採用することができます。
TC比率は、２つのエンジンが生成したTC数から、より多いデフォルトのTC数に対して、最小テストケース生成で得られたより少ないTC数の割合を表しています。今回の条件では、おおよそ10%程度テストケース数を減らすことができています。
２つのエンジンをサポートすることで、さまざまな条件のもとでも常にどちらかより少ないTC数の結果を採用できるというメリットが生まれます。
それでは、また。
有名な IEEE の FTFI の表は信頼できるか？
障害がいくつの要因の組み合わせで発生しているかを示す例として、よく2004年 IEEEで発表された論文（Software Fault Interactions and Implications for Software Testing）の表（TABLE 1）が引用されます。
この表では、RAXからPOSIXまでは不完全なデータなので除くとして、残りの右側４つのデータは、数値の傾向が大きく異なる２つのグループに分けることができます。
２つの傾向は、Fig.1のグラフでよりはっきりと分かります。BrowserとSeverは、要因数（FTFI）の多い障害が多くを占めていますが、Med. DevicesとNASAのデータベースシステムは、要因数の少ない障害が多くを占めています。なぜこういう結果になったかというと、それぞれのソフトウェアが開発工程のどの段階でのデータなのかに違いがあるからです（TABLE 2）。
Medical DevicesはFielded productsとあり、市場出荷後のデータと考えられます。BrowserとServerはbeta releaseの段階のデータです。NASAのデータベースシステムは統合テストの段階のデータです。さらにソフトウェアのステップ数にも数千ステップから約200万ステップと大きな違いがあります。
こうした条件の違いを考慮に入れてデータを見ないと誤った解釈をする恐れがあります。
これらのデータから読み取れるのは、beta releaseの段階では、障害の要因数が１つより２つ以上のものが多いということです。これは、beta releaseのため一般公開直前の十分なテストを経た段階のデータであることを意味しています。このことは、私たちの経験からも一致するものです。また、NASAのデータベースシステムは、統合テストの段階のデータのため、障害の要因数が１つのものが最も多くなっています。これも私たちの経験と一致しています。
唯一、Medical Devicesは、市場出荷後にもかかわらず、障害の要因数が１つのものが最も多くなっています。おそらくこの製品は、市場で多くの障害を出したと思われます。
このようにデータの背景を知ることによって、より正確な知識を得ることができます。
この論文は Pairwise Testing のサイトの Reserch Pａperse の27番にあります。
それでは、また。
障害の半分近くはテスト仕様書以外から見つかっている
テストは、テスト仕様書に従って実施し、確認内容との相違があれば障害として登録します。しかし、現実には確認内容欄にすべての確認内容を記述することは、あまりにも記述量が多くなるため、当該テストで対象となっている事項に絞って確認内容を記述せざるを得ません。
テスト仕様書の確認内容との相違で見つけた障害と、それ以外の理由で見つけた障害の割合はどれくらいでしょうか。次のデータは私たちのチームが行なったある製品の総合テストで得られたデータです。
このデータからは、障害発見につながった理由のうち、半数近くがテスト仕様書以外の理由で占められています。このことは、テストとは、単にテスト仕様書どおりに行なえばよいというものではなく、テスト担当者がどれだけちょっとした不審な動作に気づき、障害発見に結びつけることができるかも重要であることを示しています。
理想的にはテスト仕様書の確認内容との相違で見つかる障害が多いほど、理想的なテスト仕様書と思われますが、一方では、テスト担当者がテスト仕様書に書かれた確認内容だけに注意を向けて、他の障害に気づいていないことが多いとも言えそうです。
みなさんも、こうしたメトリクスを取られてみてはいかがでしょうか。