NIST IR 7308 日本語訳
英語タイトル : An Algorithm for Generating Very Large Covering Arrays日本語タイトル : 非常に大きな被覆配列を生成するためのアルゴリズム
公開日 : 2006-03-20
原文URL : https://csrc.nist.gov/pubs/ir/7308/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 21 / 21 ブロック
[要約] NIST IR 7308 は、非常に大きな被覆配列を生成するために、Paintball と呼ぶアルゴリズムを説明した覚書です。大規模システムの自動テストでは、相互作用の度合いが高い多数の変数に対してテストを作成する必要があり、被覆配列の問題は NP 困難であるため、決定的アルゴリズムは変数の数が多い場合にうまく機能しないとされています。Paintball は、ほかの被覆配列のアルゴリズムと異なり並列化できるため、既知のほかのアルゴリズムよりもはるかに多くの変数を扱うことができ、その代わりにテストケースの最適化を犠牲にしています。10 個以上の変数では、FireEye よりもおよそ 3% から 15% 多いテストを生成するとされ、このアルゴリズムは FireEye やほかのアルゴリズムを補完するものであり、置き換えるものではないかもしれないと述べています。
An Algorithm for Generating Very Large Covering Arrays
非常に大きな被覆配列を生成するためのアルゴリズム
D. Richard Kuhn
D. Richard Kuhn
One problem that must be solved for automated testing of large systems is producing tests for a large number of variables with a high degree of interaction. The problem of covering arrays is known to be NP-hard, so deterministic algorithms do not perform well for large numbers of variables. FireEye, which implements the In Parameter Order (IPO) algorithm, can handle a large number of variables, but its run time increases exponentially as the number of variables and interaction levels increase, and it is not clear if IPO can be parallelized. This note describes a algorithm – called Paintball – that can be parallelized, unlike other covering array algorithms, making it possible to handle a much larger number of variables than other known algorithms. The algorithm trades test case optimization for speed – it produces roughly 3% to 15% more tests (depending on run time allowed) than FireEye for 10 or more variables, but this ratio improves as the number of variables increases (see examples in Table 1). It thus complements but may not replace FireEye and other algorithms, which produce somewhat fewer tests. The significant advantage of the algorithm is that it can be distributed across any number of processors. For automated test generation this means that both test data generation and test oracle production can be run in parallel.
大規模システムの自動テストで解決しなければならない問題の 1 つは、相互作用の度合いが高い多数の変数に対してテストを作成することです。被覆配列の問題は NP 困難であることが知られており、そのため決定的アルゴリズムは変数の数が多い場合にうまく機能しません。In Parameter Order(IPO)アルゴリズムを実装した FireEye は多数の変数を扱えますが、変数の数と相互作用のレベルが増えるにつれて実行時間が指数関数的に増加し、IPO を並列化できるかどうかも明らかではありません。この覚書では、Paintball と呼ばれるアルゴリズムを説明します。このアルゴリズムは、ほかの被覆配列アルゴリズムとは異なり並列化できるため、既知のほかのアルゴリズムよりもはるかに多くの変数を扱うことができます。このアルゴリズムは、テストケースの最適化と引き換えに速度を得ています。10 個以上の変数では、FireEye よりもおよそ 3% から 15% 多いテストを(許容する実行時間によって)生成しますが、この比率は変数の数が増えるにつれて改善します(表 1 の例を参照)。したがって、このアルゴリズムは FireEye やほかのアルゴリズムを補完しますが、それらを置き換えない可能性があります。それらのアルゴリズムは、いくらか少ないテストを生成します。このアルゴリズムの大きな利点は、任意の数のプロセッサに分散できることです。自動テスト生成では、これはテストデータの生成とテストオラクルの作成の両方を並列に実行できることを意味します。
The algorithm is called Paintball because it is conceptually similar to firing paintballs at a wall, using a few tunable parameters, until it is completely covered. Although this would be absurdly inefficient for a small number of variables, it becomes effective for the large number of variables that must be handled for software testing. For k-way interaction and variables with v values each, the number of tests is ideally \(v^k\), if there were no duplication of combinations among tests, a condition that is not possible to obtain for realistic examples. Optimal algorithms produce some multiple of this number. Because the number of k-way combinations among n variables, \(\binom{n}{k}\), is very large for large n, randomly generated test cases can produce a high degree of coverage. The algorithm works as follows:
このアルゴリズムを Paintball と呼ぶのは、いくつかの調整可能なパラメータを使って、壁が完全に覆われるまでペイントボールを撃ち込むことに概念上似ているからです。変数の数が少ない場合には、これはばかげたほど非効率ですが、ソフトウェアテストで扱わなければならない多数の変数に対しては効果的になります。k-way の相互作用と、それぞれ v 個の値をとる変数について、テスト間で組合せの重複がなければ、テストの数は理想的には \(v^k\) です。これは現実的な例では実現できない条件です。最適なアルゴリズムは、この数の何倍かを生成します。n 個の変数の間の k-way の組合せの数 \(\binom{n}{k}\) は、n が大きいと非常に大きくなるため、ランダムに生成したテストケースで高い被覆率を得ることができます。アルゴリズムは次のように動作します。
1.Construct an \(\binom{n}{k}\) row by \(v^k\) column matrix M. Set all \(M_{i,j} = 0\).
1.\(\binom{n}{k}\) 行 \(v^k\) 列の行列 M を作ります。すべての \(M_{i,j} = 0\) とします。
2.Matrix M is indexed by the k-way combinations of n variables; i.e., M is an associative array of the possible combinations of n variables; each combination is associated with a row of \(v^k\) cells. M will be used as a checkbox to check whether combinations have been covered.
2.行列 M は、n 個の変数の k-way の組合せで索引付けされます。すなわち、M は n 個の変数の可能な組合せの連想配列であり、各組合せは \(v^k\) 個のセルからなる行に対応付けられます。M は、組合せが被覆されたかどうかを確かめるチェックボックスとして使います。
3.Repeat d times, where d is a pre-specified duplication factor: generate \(v^k\) tests with n random values per test, resulting in a \(dv^k\) by n test case matrix T. Each test generated (each row of T), up to a configurable parameter t, is checked to determine the number of new combinations covered. The test with the highest number of new combinations covered is used. The objective of this step is to minimize the duplication of combinations covered by tests.
3.あらかじめ指定した重複係数 d の回数だけ繰り返します。1 つのテストあたり n 個のランダムな値で \(v^k\) 個のテストを生成し、\(dv^k\) 行 n 列のテストケース行列 T を得ます。生成した各テスト(T の各行)について、設定可能なパラメータ t まで調べ、新たに被覆される組合せの数を求めます。新たに被覆される組合せの数が最も多いテストを使います。この手順の目的は、テストによって被覆される組合せの重複を最小にすることです。
4.Mark combinations covered by each generated test:
for each possible combination of variables, set \(M_{i,j} = 1\), where \(i =\) variable combination \(\langle v_1 v_2 \ldots v_m \rangle\) and \(j = \langle v_m \ldots v_2 v_1 \rangle_v\). For example, suppose the values of the current combination of variables are 2,0,3, and 0. Then \(j = 0302_4 = 50_{10}\). For variables with differing numbers of values, a similar procedure is used, with variables ordered by number of values.
4.生成した各テストによって被覆される組合せに印を付けます。
変数の可能な各組合せについて \(M_{i,j} = 1\) とします。ここで、\(i\) は変数の組合せ \(\langle v_1 v_2 \ldots v_m \rangle\) を表し、\(j = \langle v_m \ldots v_2 v_1 \rangle_v\) です。たとえば、現在の変数の組合せの値が 2、0、3、0 であるとします。このとき \(j = 0302_4 = 50_{10}\) です。値の数が異なる変数については、値の数の順に変数を並べて、同様の手順を使います。
5.Scan M and set c = number of combinations not covered. If c is less than an experience-based parameter for similar sized problems, then stop, else increase duplication factor: d := d+1 and repeat the algorithm until number of tests is minimum. This procedure generally covers 99.9% or more of the possible combinations.
5.M を走査し、c = 被覆されていない組合せの数とします。c が、同程度の規模の問題について経験的に定められたパラメータより小さければ停止します。そうでなければ重複係数を増やし、d := d+1 として、テストの数が最小になるまでアルゴリズムを繰り返します。この手順では、通常、可能な組合せの 99.9% 以上を被覆します。
6.Uncovered combinations may number from a few to 10,000 or more. These are written out as tests with one combination per test, with other variable values given as “don’t care” conditions. For example, for 4-way interactions, an uncovered test may be “- 3 - - 2 5 - - 3 - -“ (“-“ represents don’t care value).
6.被覆されない組合せは、数個から 10,000 個以上に及ぶことがあります。これらは、1 つのテストに 1 つの組合せを入れ、ほかの変数の値を「don’t care」の条件としたテストとして書き出します。たとえば 4-way の相互作用では、被覆されないテストは「- 3 - - 2 5 - - 3 - -」のようになります(「-」は don’t care の値を表します)。
7.Randomize the lines produced in step 6; i.e., for lines \(L_i\) in the output file, shuffle index i.
7.手順 6 で作成した行をランダムに並べ替えます。すなわち、出力ファイルの行 \(L_i\) について、索引 i をシャッフルします。
8.Reduce the tests for combinations not covered by combining them into test cases containing multiple combinations. Test cases are combined when their values for each variable are the same (i.e., \(T_{1i} = T_{2i}\), all i) or when one is a “don’t care” condition. For each line i in the file of uncovered combinations, compare line i with following lines j = i+p..(i+ p <n ? i+ p : n), where p is a lookahead parameter that is some fraction of the total lines in the file. If a line is found that can be combined with line i, merge the two and resume scanning with line i+1. If no line in i+1 .. p matches line i, write out line i and resume scanning with line i+1. This procedure can normally reduce 10,000 to 100,000 tests to a several hundred, with the final reduced tests containing less than 1% “don’t care” values.
8.被覆されない組合せのテストを、複数の組合せを含むテストケースにまとめて減らします。各変数について値が同じ(すなわち、すべての i について \(T_{1i} = T_{2i}\))か、または一方が「don’t care」の条件である場合、テストケースを統合します。被覆されない組合せのファイルの各行 i について、後続の行 j = i+p..(i+ p <n ? i+ p : n) と比較します。ここで p は、ファイルの全行数に対するある割合を表す先読みパラメータです。行 i と統合できる行が見つかれば、2 つを統合し、行 i+1 から走査を再開します。i+1 .. p にある行の中に行 i と統合できる行がなければ、行 i を書き出し、行 i+1 から走査を再開します。この手順では通常、10,000 から 100,000 個のテストを数百個に減らすことができ、最終的に減らしたテストに含まれる「don’t care」の値は 1% 未満になります。
Discussion: This procedure works because with many variables, each test case contains thousands of k-way combinations of variables. Another way of viewing the covering procedure is to think of each of the \(C = \binom{n}{k} \times v^k\) combinations that must be covered as a separate bin. If we throw C marbles into random bins, most bins will have at least one marble. Another set of C marbles covers more bins, and so on repeated d times, until nearly all contain one or more marbles. For example, with C=20, d=8, all C combinations are covered with 99.5% probability The number of combinations produced by the algorithm is d x C, and each random combination is assigned to one of the C bins, with the total number of randomly generated combinations proportional to \(C \ln C\). With suitable values of d, at least one combination is assigned to each bin with a very high probability. The efficiency of this approach is increased by minimizing the number of duplicate combinations in each new test in step 3
考察:この手順がうまくいくのは、変数が多いと、各テストケースに変数の k-way の組合せが数千個含まれるからです。この被覆の手順は、被覆しなければならない \(C = \binom{n}{k} \times v^k\) 個の組合せのそれぞれを別々の箱と考えると見ることもできます。C 個のビー玉をランダムな箱に投げ入れると、ほとんどの箱には少なくとも 1 個のビー玉が入ります。さらに C 個のビー玉からなる一組を投げ入れると、さらに多くの箱が埋まります。これを d 回繰り返すと、ほぼすべての箱に 1 個以上のビー玉が入ります。たとえば C=20、d=8 の場合、C 個の組合せすべてが 99.5% の確率で被覆されます。アルゴリズムが生成する組合せの数は d x C であり、ランダムな各組合せは C 個の箱の 1 つに割り当てられます。ランダムに生成される組合せの総数は \(C \ln C\) に比例します。d を適切な値にすれば、非常に高い確率で各箱に少なくとも 1 つの組合せが割り当てられます。手順 3 で新しい各テストに含まれる重複した組合せの数を最小にすることで、この方法の効率は高まります
Implementation notes: The algorithm can be distributed across any number of machines, but requires a common “checkbox” to record the combinations covered. For a large number of variables, a very large amount of disk storage would be required for the blackboard, roughly \(\frac{\left(\binom{n}{k} \times v^k\right)}{8}\) bytes. For 6-way combinations of 50 variables with 6 values each, this is approximately 9 gigabytes; large but fairly easy to implement on a cluster system. With lower interaction levels or fewer values per variable, a desktop PC is adequate for 100 variables or more. Alternatively, a disk based version of the program can be used, although this increases run time from a few minutes to hours.
実装上の注意:このアルゴリズムは任意の数のマシンに分散できますが、被覆された組合せを記録する共通の「チェックボックス」が必要です。変数の数が多いと、黒板にはおよそ \(\frac{\left(\binom{n}{k} \times v^k\right)}{8}\) バイトという非常に大量のディスク領域が必要になります。それぞれ 6 個の値をとる 50 個の変数の 6-way の組合せでは、これはおよそ 9 ギガバイトです。大きいですが、クラスタシステムではかなり容易に実装できます。相互作用のレベルが低いか、変数あたりの値が少なければ、100 個以上の変数でもデスクトップ PC で十分です。あるいは、ディスクベース版のプログラムを使うこともできますが、その場合は実行時間が数分から数時間に増えます。
Calculation of d in step 3. The occupancy problem in probability addresses the question of throwing m balls into n bins at random, or in this case, the number of combinations generated randomly to cover all possible combinations. For large m and n, the proportion of n bins covered is \(p = e^{-m/n}\). The algorithm is designed to cover a high percentage of bins, \(\frac{C - R}{C}\), where \(C = \binom{n}{k} v^k\) is the number of combinations to be covered, and R is the remaining set that is not covered, usually a few hundred to several thousand (see step 6). From this we can determine the duplication factor d (step 3) and an upper bound on the number of tests produced:
手順 3 における d の計算。確率論の占有問題では、m 個の球を n 個の箱にランダムに投げ入れる問題を扱います。この場合には、可能なすべての組合せを被覆するためにランダムに生成する組合せの数が問題となります。m と n が大きいとき、n 個の箱のうち被覆される割合は \(p = e^{-m/n}\) です。このアルゴリズムは、被覆される箱の割合 \(\frac{C - R}{C}\) が高くなるように設計されています。ここで \(C = \binom{n}{k} v^k\) は被覆すべき組合せの数、R は被覆されずに残る組合せの集合で、通常は数百から数千です(手順 6 を参照)。このことから、重複係数 d(手順 3)と、生成されるテスト数の上限を求めることができます。
\(d \cong \ln C - \ln R\) and
\(\#T = \textit{generated tests} \le (\ln C - \ln R)v^k\)
\(d \cong \ln C - \ln R\) および
\(\#T = \textit{generated tests} \le (\ln C - \ln R)v^k\)
In practice the best starting point for the duplication factor d seems to be \(\ln C - \ln R - 1\).
実際には、重複係数 d の開始点として最も適しているのは \(\ln C - \ln R - 1\) のようです。
Note from Table 1 that the difference between the number of tests produced by Paintball and FireEye declines as the number of variables increases, but this has not been tested above 50 variables because run times for FireEye become prohibitive (exceeding 24 hours) above this number. There may be relatively little difference for significantly higher numbers of variables.
表 1 から、Paintball と FireEye が生成するテストの数の差は変数の数が増えるにつれて小さくなることがわかります。ただし、50 個を超える変数では、FireEye の実行時間が法外な長さ(24 時間超)になるため、試験していません。変数の数がかなり多い場合には、差は比較的小さいかもしれません。
4-way Interactions, 4 to 8 value variables, single processor
4-way の相互作用、4〜8 値の変数、単一プロセッサ
| Num. of variables | PB2 tests | PB2 time | FE tests | FE time | PB2/FE tests |
|---|---|---|---|---|---|
| 4 value | |||||
| 10 | 771 | 3 | 684 | 1 | 112.7% |
| 20 | 1367 | 31 | 1123 | 62 | 121.7% |
| 30 | 1766 | 68 | 1486 | 570 | 118.8% |
| 40 | 2051 | 365 | 1718 | 2704 | 119.4% |
| 50 | 2260 | 300 | 1897 | 12958 | 119.1% |
| 60 | |||||
| 70 | 2504 | 4989 | 2144 | 42383 | 116.8% |
| 5 value | |||||
| 10 | 1906 | 6 | 1861 | 102.4% | |
| 20 | 3493 | 27 | 3019 | 115.7% | |
| 25 | 3987 | 158 | 3185 | 125.2% | |
| 30 | 4340 | 385 | 3749 | 115.8% | |
| 40 | 5026 | 699 | 4275 | 7041 | 117.6% |
| 50 | 5512 | 2084 | 4691 | 24352 | 117.5% |
| 6 value | |||||
| 10 | 3967 | 53 | 3858 | 57 | 102.8% |
| 7 value | |||||
| 10 | 7394 | 152 | 7155 | 134 | 103.3% |
| 8 value | |||||
| 10 | 12602 | 320 | 12173 | 288 | 103.5% |
| 変数の数 | PB2 のテスト数 | PB2 の時間 | FE のテスト数 | FE の時間 | PB2/FE のテスト数 |
|---|---|---|---|---|---|
| 4 値 | |||||
| 10 | 771 | 3 | 684 | 1 | 112.7% |
| 20 | 1367 | 31 | 1123 | 62 | 121.7% |
| 30 | 1766 | 68 | 1486 | 570 | 118.8% |
| 40 | 2051 | 365 | 1718 | 2704 | 119.4% |
| 50 | 2260 | 300 | 1897 | 12958 | 119.1% |
| 60 | |||||
| 70 | 2504 | 4989 | 2144 | 42383 | 116.8% |
| 5 値 | |||||
| 10 | 1906 | 6 | 1861 | 102.4% | |
| 20 | 3493 | 27 | 3019 | 115.7% | |
| 25 | 3987 | 158 | 3185 | 125.2% | |
| 30 | 4340 | 385 | 3749 | 115.8% | |
| 40 | 5026 | 699 | 4275 | 7041 | 117.6% |
| 50 | 5512 | 2084 | 4691 | 24352 | 117.5% |
| 6 値 | |||||
| 10 | 3967 | 53 | 3858 | 57 | 102.8% |
| 7 値 | |||||
| 10 | 7394 | 152 | 7155 | 134 | 103.3% |
| 8 値 | |||||
| 10 | 12602 | 320 | 12173 | 288 | 103.5% |
Table 1. Comparison of test generation for 4-way interactions
PB = paintball algorithm, #tests and time in seconds
FE = FireEye algorithm, #tests and time in seconds
表 1. 4-way の相互作用に対するテスト生成の比較
PB = paintball アルゴリズム、テスト数(#tests)と時間(秒)
FE = FireEye アルゴリズム、テスト数(#tests)と時間(秒)