All-pair法：組み合わせ試験の最前線「組み合わせテストについて」
土屋達弘，菊野亨 （大阪大学）

1

組み合わせテスト（Combinatorial Testing）
すべての k 個のパラメータについて，それらの値の組み合わせをすべてテストする手法
ペアワイズテスト，All-Pair法
k=22All-Pair法：テストケースの例
テストケースの例
因子（パラメータ） ３個
水準（値の種類） ３通り

テスト数

34 = 81
全数テスト

9Ａｌｌ-P air

P1P2P3P4

Test 10000

Test 21110

Test 32220

Test 40121

Test 51201

Test 62011

Test 70212

Test 81022

Test 921023

All-Pair法の背景
フォールトの多くは，少数のパラメータ値の組み合わせによって顕在化する
Kuhn等の研究
R.D.Kuhn et al. “Software Fault Interactions andImplications for Software Testing,” IEEE
Transactions on Software Engineering, 30(6), June
2004

4

All-Pair法の背景
FTFI (failure-triggering fault interaction)
フォールトに関係しているパラメータ数

FTFI

エキスパートシステム

組込み Netsc Apach
ape N. eOSDB

1

61

72

48

3982

66

29

42

68

236

1068*

31

47

28

25

3*na*

*

*

*

2

1919

54**

*

*

*

1

2

725*

*

*

*

*

206*

*

*

*

*

1

4

1,000〜10,000 LoC

100,000 LoC
5テストケース作成法
数学的な手法
手動でも構成可能
手順：
基本となる表(ビルディングブロック)を構成
2. 表を組み合わせて，因子数を増加
1.

コンピュータによる探索ツールの利用
6

数学的な手法 ・・・ ビルディングブロック
水準Vが素数の場合 (例．V = 3)
V+1の因子に対し，V*V個のテストでペアを網羅
IJ0001

テスト数

02

V*V

101112202122P=0

P=1

P=2

因子数（パラメータ数）V+1

P=37

数学的な手法・・・ビルディングブロック
ステップ１．P=Vの列をIの値に設定
P=0P=1P=2II

J000010

テスト数

020

V*V

101111121202212222

因子数（パラメータ数）V+1

P=38

ステップ2．P=0~V-1の列の各エントリーを以下の値に設定(I*P + J) % V
IJ

P=0P=1P=2000010

テスト数020

V*V101111121202212222

因子数（パラメータ数）V+1P=39(I*0 +J) % 3 (I*1 + J) % 3 (I*2 + J) % 3(I*P + J) % VIJ

P=0P=1P=2000010

テスト数

020V*V101111121202212222

因子数（パラメータ数）V+1

P=310(I*P + J) % V(I*0 +J) % 3 (I*1 + J) % 3 (I*2 + J) % 3IJ

P=0P=1P=20000001110

テスト数02220V*V

1001111111221200221122222

因子数（パラメータ数）V+1

P=311

(I*P + J) % V(I*0 +J) % 3 (I*1 + J) % 3 (I*2 + J) % 3

IJ

P=0

P=1

P=2

P=3000000011110

テスト数022220

V*V

100

1211

1

120

1

1220

1

12002

122

1

1022222102

因子数（パラメータ数）V+112

数学的な手法・・・表の組み合わせ基本となる表(ビルディングブロック)因子（パラメータ）
テスト

V+1個 (水準Vは素数)V*V個もっと多くの因子（パラメータ）が必要になったら？

表を２つ組み合わせて因子数を増やせる！

13

数学的な手法・・・表の組み合わせ
テスト数
s因子数 n×テスト数
s+s’-1テスト数s’
因子数 n*n’因子数 n’14

表の組み合わせ 9×940120120120121202010122011204000111222

網羅されている 網羅されている

まだ網羅されていない
15

表の組み合わせ

9×94012012012012120201012201120000111222012012012012120201401220112000011122201201201201212020101201201201212020101220112000011122201220112000011122201201201201212020101220112
00001
11222網羅！
16

表の組み合わせ

9×94012012012不要012120201012201120012012012000111222012012012012120201012201120012120201000111222012012012401212020101220112001220112000011122201201201201212020101220112000011122200011122217表の組み合わせ

9×94

テスト数
9+9-117足し算

012012012012120201012201120000111222012012012012120201120120120122011201212020100011122201201201240121202010122011201220112000011122201201201201212020101220112000011122200111222

因子数（パラメータ数）

4*4

16 掛け算18

テスト数の推移
4035

テスト数 302520
1510502550

75

100

因子数（パラメータ数）

必要なテストは因子数に対して対数的にしか増えない！
19

制約への対処
水準の異なる因子
パラメータによって値の数が異なる

禁則回避
組み合わせることのできない値

20

水準の異なる因子
ステップ１．水準毎に表を作成
２水準

3水準
012012012012120201012201120000111222010101100011010101100011010101101011011010011

まだ網羅されていない
21

水準の異なる因子
ステップ2．水準間を網羅
２水準

3水準
01201201201212020101220112001222000111222010101101010011010101101100011010101
1000110111010122

禁則回避
禁則を考慮して，関係のある因子を結合
２水準

03水準

0124水準

10 (0,0)
1 (1,0)2 (2,0)3 (0,1)

23テストケース作成法
数学的な手法
手動でも構成可能ツール (例．TConfig)

コンピュータによる探索ツールの利用24アルゴリズムの例
一度に表を作成
ヒルクライミング
シミュレイティッド・アニーリング
タブサーチ

１つずつテストを作成
遺伝アルゴリズム*
アントアルゴリズム**T. Shiba, T. Tsuchiya, T. Kikuno, “Using Artificial Life
Techniques to Generate Test Cases for Combinatorial
Testing,” COMPSAC 2004.
25例．遺伝アルゴリズム (GA)
テストケースを進化させてAll-Pairを網羅
染色体テストケース

交叉

132

123

1

13

1332

1323

12322212123

122

121

突然変異
1326

まとめ
All-Pair法のテスト作成法について説明
数学的な手法探索に基づく手法

性質
因子の数に対し，テストが対数的にしか増えない
既存のテスト手法と相補的な利用の可能性
27