t-wise testing 入門 - ::Eldesh a b = LEFT a

マイクロソフト製テストケース生成ツール PICT を同僚に教えてもらいました。そのツールと、それが実装しているテスト生成アルゴリズムを紹介しているペーパー Czerwonka, Pairwise testing in real world, 2006 を読んだので、PICT とそれが採用している生成アルゴリズムである t-wise strategy について簡単に紹介します。

t-wise testing strategy
- 例: モデル1
Constraint
Seeding
ランダムテスト(QuickCheck)との比較
感想

t-wise testing strategy

問題設定としては、「テスト対象のパラメータが幾つかと、それぞれのパラメータの取り得る値の(有限通りの)バリエーション(レベルと呼ぶ)が与えられたとき、良い組み合わせのテストケースを生成する」というものです。

ここでテストケースとは各パラメータに対応するレベルの集合のことをいい、パラメータとレベルとConstraint(後述)のことをまとめてモデルと呼びます。

当然全てのレベルのあらゆる組み合わせを生成(してテスト)すれば最も安心なワケですが、組み合わせ数が爆発しますので、実際的なシステムのテストには現実的ではありません。

良いテストケースが何かというのは難しい問題ですが、一般的には、よりバリエーションに富んだ(つまり一部のパラメータのレベルの組み合わせが冗長だったりしない)組み合わせを含みつつ、現実的な入力に対して十分小さい出力を生成出来ることが望ましいでしょう。

そこで PICT が採用しているテストケース生成戦略が、 t-wise strategy です。

これは、互いに異なる t 個のパラメータの全てのレベルの組み合わせが含まれるようにテストケースを生成するものです。

t=2 の場合は特に Pairwise testing (strategy) と呼ばれます。PICT のデフォルト設定も t=2 です。

例: モデル1

例えば、レベルa1,a2,a3を取るパラメータA、レベルb1,b2を取るパラメータB、レベルc1,c2と取るパラメータCを持つモデルを考えた場合、生成される組み合わせは以下の6通りになります。

ParamA	ParamB	ParamC
a1	b2	c2
a1	b1	c1
a3	b2	c1
a2	b1	c2
a2	b2	c1
a3	b1	c2

ParamA と ParamB だけを考えれば $\{a1,a2,a3\}\times{}\{b1,b2\}$ の6通り全てが出現していますし、ParamB と ParamC に注目すれば $\{b1,b2\}\times{}\{c1,c2\}$ の4通りが網羅されています。

3つのパラメータのあらゆる組み合わせを網羅するためには $3\times{}2\times{}2=12$ 通りになりますが、ここでは任意の二つのパラメータの組み合わせを尽くすように生成しているため6通りで済みます。このケースでは、例えば $\{a1,b2,c1\}$ という組み合わせは生成されていません。

上の例を PICT に与えるには以下のように記述します。

ParamA: a1, a2, a3
ParamB: b1, b2
ParamC: c1, c2

見たままです。

Constraint

任意のレベルの(pairwiseの)組み合わせを考えた場合、その中にシステムとして不正な入力が含まれてしまうことがあります。これをあらかじめ生成対象から排除するための組み合わせを指定する式を Constraint として与えることが出来ます。

例えば以下のような入力(モデル2)を PICT に与えると:

ParamA: a1, a2, a3
ParamB: b1, b2
ParamC: c1, c2
# constraint
IF [ParamA] = "a2" THEN [ParamB] <> "b2" ;

次のような出力になります。

ParamA	ParamB	ParamC
a3	b1	c1
a2	b1	c2
a2	b1	c1
a1	b2	c2
a3	b2	c1
a3	b2	c2
a1	b1	c1

$\{a2,b2\}$ を含む組み合わせが出力から除かれています。また $a2$ と $b2$ をそれぞれ含む(t=2の)組み合わせを網羅するために出力が冗長になり、7通りのテストケースが生成されています。

PICT では Constraint を(生成してからフィルタするのではなく)生成器側で(生成候補に排除マークを付けることで)考慮しており、効率的にテストケースを生成出来ます。

Seeding

(ランダムテストではなく) t-wise testing の場合でも、必要な条件を満たす組み合わせにはバリエーションがあり、そこからどれが選ばれるかは実装依存となります。

PICT ではこの選択は決定的に行われ、含んでいるべきレベルの集合($\subset{t{-}wise\ test}$) を与えることで、含んでいるべき組み合わせ(の族)を明示的に与えることが出来ます。

例えば、最初のモデル1に加えて以下のような seed を与えると:

# NOTE: 本物のファイルはタブ区切り
ParamA	ParamB	ParamC
a1      b1      c2

次のような出力が得られます。

ParamA	ParamB	ParamC
a1	b1	c2
a3	b2	c2
a2	b1	c2
a3	b1	c1
a1	b2	c1
a2	b2	c1

モデル1の出力では含まれていなかった $\{a1,b1,c2\}$ を含んでいます。

seed として一部のパラメータのみを指定することも出来、これによって

モデルの変更時の変更を小さくしたり、
変更しづらいパラメータの組み合わせの変更を抑えたり

することが出来ます。

ランダムテスト(QuickCheck)との比較

QuickCheckのようなランダムテスト系と異なり、

パラメータ(やレベル)の増加をほとんど気にしなくてもいい点、
どのような性質を持ったテストケースなのかが分かり易い点、
また実装と表現力次第ですが、constraintを好きなだけ与えることが出来る点*1
特定の組み合わせ(の族)を含むように指定することが簡単に出来る点

が優れていると思います。一方、以下のようなことは苦手です。

特定のレベルの出現確率を任意に調整する
t-wise strategy では組み合わせの冗長性を廃してテストケースを出来るだけ小さくするのが基本目標なので、出現確率分布を出力にナイーブに反映出来ません。
(ある範囲の)数値パラメータについて網羅的に生成(検査)する
組み合わせ爆発するため $[0, 2^{32})$ のようには指定出来ません。(0, 10, 100, 10000のように与える必要があります)