ZDD
を用いた組合せテストケースの列挙索引化に関する
実験と考察
Experiments and Considerations on
Enumerating Combinatorial Test Cases Using ZDDs
大畑 翔平
1∗湊 真一
2Shohei Ohata
1Shin-ichi Minato
21
北海道大学 工学部
1
School of Engineering, Hokkaido University
2
北海道大学 大学院情報科学研究科
2
Graduate School of Information Science and Technology, Hokkaido University
Abstract: In software development, testing is an essential task to ensure the correctness of the products. However, it is not practical in terms of computational cost to explore all the combinato-rial states of a program. Combinatocombinato-rial test cases are considered as a good subset of test patterns to find out failures as many as possible. In this paper, we propose an efficient method of enumer-ating all sets of combinatorial test cases. Enumerenumer-ating the sets of test cases enables us to analyze mathematically in detail, and to search combinatorial test cases more quickly when restriction is added to them. The number of possible combinatorial test cases is enormous, so we use ZDDs which can suppress and express a set of combinations. We can generate all sets of combinatorial test cases at once using ZDDs, without visiting each test case one by one. We present the two methods for generate a ZDD representing all possible sets of test cases, and to generate a ZDD representing all the sets of test cases with the minimum size. Our experimental results show that we can enumerate both in a few minutes if the memory capacity is not shorted.
1
はじめに
ソフトウェア開発において，意図したように動作す るかどうかを確かめるために不具合を検出するソフト ウェアテストは不可欠である．しかし， そのテストに 要する時間はソフトウェア内の変数 (k 種類) と変数が 取り得る値の種類 (v 種類) に応じて指数的に増大する ため，実用的な規模の例題では全ての内部状態をテスト することは困難である．そこで限られた時間内に，で きるだけ多くの不具合を発見できるようにテスト方法 を工夫する必要がある．すなわち，与えられたテスト 回数でより多くの不具合を発見できること，または与 えられた不具合の集合をより少ないテスト回数で発見 できることが求められる．一般に，ソフトウェアの不 具合は，ソフトウェア内の全ての変数ではなく，一部の 少数の変数の値に依存して発生する例が多いことが知 ∗連絡先： 北海道大学 工学部 情報エレクトロニクス学科 大規模知識処理研究室 〒 060–8628 札幌市北区北 13 条西 8 丁目 E-mail: [email protected] られている [2]．このようにしておこる不具合を発見す るために，ある一定の個数の変数の組に着目し，それ らの変数に入る値の組合せを網羅できるようなテスト を集めたものは「組合せテストケース」と呼ばれてい る．一般に，組合せテストケースの条件を満たすテス ト集合は複数通り存在するが，その中でなるべくテス ト数が少ない解を得ることができれば，ソフトウェア の不具合の多くをカバーする効率の良いテスト手法と なるため従来より多くの研究が行われている [3, 5, 4] 本研究では，組合せテストケースの全列挙及びテス ト数が最小の組合せテストケースの全列挙を行う手法 について実験と考察を行う．ソフトウェアのテストに おいては，実用的には最小に近い組合せテストケース が一つ求まれば十分であり，解を全列挙することに直 接必要性はない．しかし，全ての解を列挙することで， より詳細な数学的性質を解析することが可能となる． 例えば，その数がわかることで，ランダムにテストを 選んだときに組合せテストケースとなる確率が得られ る．その確率がわかると他の組合せテストケースをを 人工知能学会研究会資料 SIG-FPAI-B509-03求める手法において，ランダムに選ぶときに比べてど れくらい優位性があるか検証することができる．また， 全ての解を網羅して索引化しておくことで，ある特定 のテストがソフトウェアの制約で実行不可能な場合に， その代用となるテストを素早く提供することができる ようになる． 一方で，解を全列挙するときは，解を一つ求めるより も計算時間が増大する．そのため，組合せテストケー スの列挙ができる変数の数や変数の取り得る値の種類 には限りがあり，例題の規模が大きくなると全列挙で きないという問題がある．本研究では，組合せテスト ケースの全列挙だけではなく，テスト数が最小の組合 せテストケースについてのみの列挙を行い，その数を数 え上げを行う方法を提案し，実験と考察を加えた．更 に本研究では，組合せ集合を効率よく圧縮し，表現で きる ZDD というデータ構造を用いて，組合せテスト ケースを一つづつ探索せずにまとめて列挙できる方法 について述べる．
2
準備
2.1
組合せテストケース
ソフトウェアにおいて，その内部の変数の数が k 個 あるとして，各変数に入る値が v 種類であるとき，各 変数に一つずつ値が入った状態を一つのテストケース と呼び，テストケースの総数は vk通り存在する．例え ば，k = 3，v = 2 のとき，テストケースは表 1 のよう 全部で 8 通りとなる．k = 4, v = 2 のときであれば，テ ストの数は 16 種類存在する．また，テストケースに含 まれる変数の値を k 桁の v 進数とみなして数値に変換 したものをテスト ID と呼び，テスト i のように表記す ることとする．一つのテスト集合は，vk通りの中から 一部を選んだテストケースを組合せたものである．例 えば，表 2 は k = 3, v = 2 の場合に，テスト 0,3,5,6 を選んだものである．この例において， どの 2 変数の ペアを取り出しても，00,01,10,11 の 4 通りの値の組み 合わせたものが出現している．このようなテスト集合 のことをペアワイズテスト集合と呼ぶ．更に 2 変数で はなく 3 変数の組み合わせを取り出したときに，000, 001, 010, . . . , 111 の 8 通りの値の組合せが全て出現す るようなテスト集合を求める問題も考えられる．一般 に t 個の変数の組について vt通りの全ての値の組合せ が出現するテスト集合を求めることは，組合せテスト ケース生成問題と呼ばれている．組合せテストケース を使うことで，t 個以下のの変数によって生じる不具合 などを検出することができる． 表 1: k = 3, v = 3 のテストケース一覧 テスト ID 変数 0 変数 1 変数 2 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 表 2: (t, k, v) = (2, 3, 2) の場合の組合せテストケース の例 テスト ID 変数 0 変数 1 変数 2 0 0 0 0 3 0 1 1 5 1 0 1 6 1 1 02.2
ZDD
ZDD （Zero-suppressed Binary Decision Diagram; ゼロサプレス型二分決定グラフ）[1] は，図 1(a) に示 すような非巡回有向グラフによる組合せ集合の表現方 法である．これは，図 1(b) の場合分け二分木を圧縮す ることにより得られる．この場合分け二分木では，各 分岐節点の 1-枝と 0-枝は，その節点にラベル付けされ たアイテムを選ぶかどうかの場合分けを表し，葉の値 (1/0) はその葉に対応する組合せが集合に属するかどう かを示している．場合分け二分木から ZDD を得るた めの圧縮を行う際には，まず場合分けするアイテムの 順序を固定し，以下の 2 つの圧縮規則を可能な限り適 用する． (a) （冗長節点の削除） 1-枝が 0 の値を持つ葉を指 している場合に，この節点を取り除き，0-枝の行 き先に直結させる． (b) （等価節点の共有）等価な節点（アイテム名が同 じで，0-枝同士，1-枝同士の行き先が同じ）を共 有する． これにより「既約」な形が得られ，組合せ集合をコンパ クトかつ一意に表せることが知られている．ZDD によ るデータ圧縮率は, 組合せ集合の性質にも依存するが, 例題によっては数十倍∼数百倍以上もの圧縮率が得ら れる場合がある． ZDD はデータを圧縮できるだけでなく，2 つの組合せ 集合の間の集合演算を高速に実行できるという重要な特 長がある．2 つの既約な ZDD F , G を入力とし，F と G
(a) ZDD (b) 場合分け二分木 図 1: ZDD と場合分け二分木
の間の集合演算，例えば共通集合 (intersection)，和集合 (union)，差集合 (set difference)，直積集合 (join または product) 等の演算を行い，その結果を表す既約な ZDD
H を直接生成するアルゴリズムが知られている．演算
の一例として，F = {{a}, {a, b}}, G = {{a, b}, {c}}
とすると，F と G の共通集合は{{a, b}}, 和集合は
{{a}, {a, b}, {c}}, 直積集合は {{a, b}, {a, c}, {a, b, c}}
となる．これらの演算に必要な計算時間は，演算結果 の ZDD の節点数に依存して決まり，ZDD の圧縮率が 高ければ高速に集合演算を実行できる．このような集 合演算を多段階に実行することにより，任意の組合せ 集合を表す ZDD を構築することができる．また得ら れた ZDD に対して制約条件を与えて解を絞り込むこ とができる．
3
提案手法
3.1
テスト集合の ZDD での表し方
我々は以下のような方法でテストケースの集合を ZDD で表すこととする． • テスト ID を ZDD のアイテム ID に対応付ける． • 一つのテスト集合 (テストケースの集合) を，複 数個のテスト ID の組合せとして表現する． • 複数個のテスト集合の集まりを，組合せ集合とし て 1 つの ZDD で表現する． 例えば，図 1 の (a) であれば，ZDD のアイテム a，b，c がテストケース 0,1,2 にそれぞれ対応し，ZDD が表す 組合せ集合が{{テスト 0}, {テスト 0, テスト 1}, {テス ト 0, テスト 2}}というテスト集合の集合に対応してい る．なお，我々が使用している ZDD 処理系では ZDD はアイテム番号が約 65000 個までしか扱えないが，本 手法では vk種類のアイテムを割り当てる必要があるた め，k が 15 程度までの範囲で使用することを想定して いる。3.2
テスト集合を列挙する ZDD の構築
組合せテストケースを全列挙する ZDD 構築アルゴリ ズムの擬似コードを Algorithm1 に示す．まず，ある特 定の t 個の変数の組 x に着目し，その変数の組が取り得 る全ての値がカバーされるようなテスト集合 Pxを表す ZDD を生成する．Pxは，kCt通りの変数の組 x それぞ れについて順々に生成されるが，その時点までの共通集 合を表現する ZDD として F を用意し，F ← (F ∩ Px) の演算を繰り返すことで，最終的に残った F が組合せテ ストケースとなるテスト集合を列挙した ZDD となる． Pxを生成する際には，t 個の変数の組が特定の値の 組合せ y を持つような全てのテスト集合を生成すると いう処理を，vt通りの値の組合せ y に対して順次繰り 返し，それらの直積演算を行うことによって，望みの Pxを生成している． Algorithm 1 construct_zdd(t, k, v) 1: ZDD F ← 「全ての組合せ集合」2: for all x←「k 個の中から t 個選んだ変数の組」do
3: ZDD Px← {{}} //（直積演算の単位元） 4: for all y ←「変数の組 x が取り得る値の組合 せ」do 5: Px← (Px×「組合せ y を含む全てのテスト 集合」) 6: end for 7: F ← (F ∩ Px) // （F と Pxの共通集合） 8: end for
3.3
テスト数が最小の場合の列挙手法
組合せテストケースの条件を満たすようなテスト集 合は，膨大な個数存在するため，それらを全列挙する ことは，ZDD 技法によって圧縮したとしても，やや大 きな規模の例題では使用記憶量や計算時間が大きくな り過ぎる．本研究では，全列挙ができない規模の例題 に対して，テストケース数が最小となるテスト集合だ けに絞って列挙することを試みた． 素朴な方法としては，全ての組合せテストケースを 列挙する ZDD を構築してから，その ZDD を探索して テストケース数が最小のものを選び出せば良い．しか し全列挙の ZDD を生成してから候補を削る方法では， 途中の計算コストを節約することができない．一般的 な傾向として，アルゴリズムの途中で出現する Pxの ZDD は比較的小さいサイズに収まっているが，それらの共通集合 F を求めるところで爆発的に ZDD のサイ ズが増大する．そこで，Pxの段階で最小テスト数の候 補に絞り込むことで，ZDD サイズの増大を抑えること ができる． 疑似コードを Algorithm2 に示す．Algorithm1 と同 様の方法で ZDD Pxを構築した後，Pxからあるアイ テム数 c より多い組合せを除いた組合せを Px′として， F と Px′の共通集合を取っていくことで，テストケー ス数を制限した組合せテストケースを表す ZDD が得 られるようになる． ところで，最小テスト数の候補を ZDD 演算で絞り 込むためには，テスト数の最小値を知っている必要が あるが，事前には最小値はわからない．組合せテスト ケースとなるためには少なくとも vt個のテスト数は必 要である．そこで本手法では，自明な下限であるテス ト数 c = vtを与えて実行し，列挙結果が空集合になっ た場合は c を 1 つずつ増やして同じ処理を繰り返すと いう方法を取っている．最初に空集合でなくなったと きの ZDD が，テスト数が最小の組合せテストケースを 列挙・索引化したものとなる． Algorithm 2 construct_minimum_zdd(t, k, v) 1: for c = vt...vk do 2: ZDD F ← 「全ての組合せ集合」 3: for all x←「k 個の中から t 個選んだ変数の組」 do 4: ZDD Px← {{}} //（直積演算の単位元） 5: for all y← 「変数の組 x が取り得る値の組 合せ」 do 6: Px ← (Px×「組合せ y を含む全てのテ スト集合」) 7: end for 8: ZDD Px′←「Pxの中で c 個のアイテムから なる組合せを集めた集合」 9: F ← (F ∩ Px′) // （F と Px′の共通集合） 10: end for 11: if F ̸= ∅ then 12: 列挙終了 13: end if 14: end for
4
実験と考察
実験に使用した計算機は CPU : Intel(R) Core(TM) i7-4910MQ @ 2.90GHz， メモリ : 32GB で，OS は openSUSE Leap 42.2 である． 表 3，表 4 は各 (t, k, v) について，組合せテスト数， ZDD の構築時間，ZDD の節点数を表したものである． 表 3: 各 (t, k, v) における組合せテストケースの全列挙 (t, k, v) 組合せテスト ZDD の ZDD の ケース数 構築時間 (秒) 節点数 (2, 3, 2) 35 < 0.01 29 (2, 4, 2) 27535 < 0.01 695 (2, 5, 2) 3820986857 0.01 43070 (2, 6, 2) 1.8× 1019 57.23 5680898 (2, 7, 2) (mem out) – – (3, 4, 2) 743 < 0.01 224 (3, 5, 2) 432265849 0.7 172574 (3, 6, 2) (mem out) – – (2, 3, 3) 10323979 < 0.01 6557 (2, 4, 3) (mem out) – – (2, 3, 4) 1.5× 1018 8.82 6203329 (2, 3, 5) (mem out) – –
4.1
全ての組合せテストケースの列挙・索
引化
実験環境で全列挙できた組合せテストケースは表 3 のようになった．(t, k, v) = (2, 6, 2) の例では，1019通 りを超えるような膨大な個数の組合せテストケースを， 現実的なサイズの ZDD で全列挙して索引化すること ができた．他にもいくつかの例題で，膨大な個数の組 合せテストケースを列挙できている． 変数の数が 7 より大きくなると，ZDD のサイズがメ モリ容量を超過してしまい，組合せテストケースの列 挙・索引化ができなかった．例えば k = 7, v = 2 のと きには，vk= 128 となり，テストケース集合の探索空 間は 2128通りとなるため，ZDD 技法による圧縮を行っ ても全列挙・索引化は困難であると考えられる．4.2
テスト数が最小の組合せテストケース
の列挙・索引化
テスト数が最小の組合せテストケースを列挙した結 果を表 4 のように示す．テスト数が最小の解だけに絞 ることで，ZDD 節点数が数十∼数百分の 1 に減ってお り，全列挙の ZDD 構築ができなかった k≥ 7 の場合で も，いくつかの例題で列挙・索引化ができるようになっ た．また，全ての組合せテストケースを列挙する場合 よりもテスト数が最小の組合せテストケースだけを列 挙する方が，数十倍以上高速に列挙・索引化できる例 が示された．この結果から，共通集合演算を行う前に， テスト数を制限することにより候補数を減らし，ZDD の共通集合演算を行う際の計算コスト増大を大幅に抑 えることができたと評価できる．一方で，vkが 512 を表 4: テスト数が最小の組合せテストケースの全列挙 (t, k, v) 組合せテスト ZDD の ZDD の ケース数 構築時間 (秒) 節点数 (2, 3, 2) 2 < 0.01 8 (2, 4, 2) 16 < 0.01 44 (2, 5, 2) 2896 < 0.01 2013 (2, 6, 2) 19200 0.06 10644 (2, 7, 2) 120960 1.07 52407 (2, 8, 2) 645120 18.11 208915 (2, 9, 2) 2580480 213.74 757128 (2, 10, 2) (mem out) – – (3, 4, 2) 2 < 0.01 16 (3, 5, 2) 16 0.03 124 (3, 6, 2) 19120 0.62 26946 (3, 7, 2) 67200 9.35 120612 (3, 8, 2) 295680 145.51 626286 (3, 9, 2) (mem out) – – (4, 5, 2) 2 0.25 32 (4, 6, 2) 64 68.11 684 (4, 7, 2) 2688 1356.12 39468 (4, 8, 2) (mem out) – – (5, 6, 2) (mem out) – – (2, 3, 3) 12 < 0.01 6 (2, 4, 3) 72 0.10 378 (2, 5, 3) 233280 88.71 473088 (2, 6, 3) (mem out) – – (2, 3, 4) 576 25.44 1376 (2, 4, 4) 6912 308.56 30272 (2, 5, 4) (mem out) – – 超える規模の例題では，最小テスト数に絞ったとして も記憶あふれのために ZDD を構築できなかった．
5
おわりに
本稿では，ZDD を用いてテスト集合の中から組合せ テストケースになっているものだけを残し，組合せテ ストケースの全列挙を行う方法，および，テスト数が 最小となる組合せテストケースの列挙を高速に行う手 法を提案した．実験の結果，膨大な個数存在する組合 せテストケースを ZDD により全列挙し索引化できる ことを示した．また現実的なメモリ容量で実行可能な 範囲を明らかにした． 今後の課題として，組合せテストケースを全列挙・索 引化した中から，別途与えた制約を満たす解だけを高 速に取り出す方法の開発などが挙げられる．また，今 回列挙できた (t, k, v) の範囲を広げる方法として，解 の対称性などを考慮することで，ZDD サイズの増大を 抑えて，より効率的に列挙する手法の検討を行いたい． 謝辞 本研究の一部は JSPS 科研費基盤 (S) 15H05711 の助 成による．参考文献
[1] Minato, S.: Zero-Suppressed BDDs for Set Ma-nipulation in Combinatorial Problems, In
Pro-ceedings of 30th ACM/IEEE Design Automation Conference (DAC’93), pp. 272–277 (1993)
[2] Kuhn, D. R., Wallace, D. R., Gallo, A. M.: ware Fault Interactions and Implications for Soft-ware Testing, IEEE Transactions on SoftSoft-ware
Engineering, Vol. 30, No. 6, pp. 418–421 (2004)
[3] Torres-Jimenez, J., Izquierdo-Marquez, I.: Sur-vey of Covering Arrays, In Proceedings of
15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2013), pp. 20–27 (2013) [4] 土屋達弘, 菊野亨: ペアワイズテスト : ソフトウェ アテストの効率化を求めて, 電子情報通信学会論 文誌 D, Vol. J90-D, No. 10, pp. 2663–2674 (2007) [5] 兼行大将, 番原睦則, 宋剛秀, 田村直之, 井上克巳: 組合せテストケース生成問題に対する制約解集合 プログラミングの適用, 2015 年度 人工知能学会全 国大会（第 29 回）論文集, 2H5-OS-03b-5, pp. 1–4 (2015)
