ペアワイズ テストのアルゴリズムを実装して学ぼう

ペアワイズテストとは

さて、今回はペアワイズテストのアルゴリズムを学ぶべく
QICT によるペアワイズ テスト
を見ながら nodejsで node-qictというのを実装(というかほぼ写経)
してみました。
npmにもアップしたので、コマンドラインで実行したり、
いろいろなツールに組み込んだりできます。
ペアワイズは、組合せテストの技法の一つで
テストセットが多すぎる状況で、テストセット数を減らす方法です。
これは Pairwise Testingにから引用すると
"ほとんどの欠陥は最大でも2つの要因の相互作用によって引き起こされるという経験則に基づいています"。
ペアワイズで生成されたテストセットは、2つの要素のすべての組み合わせをカバーしています。
また、このあと今回qictで実装した内容を解説しますが、確率的な要因を組み合わせています。
さぁ　どのように上記を実現しているか、node-qictのソースを見ながらステップバイステップで見てみましょう。

入力ファイルフォーマット

とあるWebアプリを考えましょう

Parameter(因子)	Parameter Values(水準)
Switch	on,off
Browser	Chrome, Firefox, Opera, Lynx
OS	Windows, Mac, Linux
Membership	Member, Guest

上記のParameterとParameter Valuesのペアワイズを出力したい場合は
入力ファイルのフォーマット下記になります。

$ cat   __tests__/testData.txt
Switch: on, off
Browser: Chrome, Firefox, Opera, Lynx
OS: Windows, Mac, Linux
Membership: Member, Guest

つまり Parameters と　Parameter Valuesの区切り文字は ":"
Parameter Values内の区切り文字は","
というテキストファイルを用意しましょう。

インストール方法

コマンドラインでインストールする方法は
nodejsがインストールされている状態で
下記の方法でインストールできます

$ npm i -g qict

また、すぐにブラウザで試したい方は
GitHub Pages
で試してみてください

実装詳細

全体の流れとしては

• readFile(file) ファイルを読み込んで
• initialize()　全パラメータを初期化して
• testSets() テストセットを作り出す
  • while(this.unusedPairs.length > 0) 未使用のペアがなくなるまで
    • candidateSets = _candidateSets() 候補のテストセットを作り出し
    • - best = _best()
    • - ordering = _ordering(best)
    • - testSet = _testSet(best,ordering)
    • bestCandidate = _bestCandidate(candidateSets) 最優先のテストセットを選びます
    • _modifyUnused(bestCandidate)
• printResult(testSets) 結果を表示します

となってます

readFile(file) ファイルから読み込む

これは　単純で引数の"file"から

• readFileSyncを使って全部読み込んで
• 文字列にして
• trim()して
• this.contentsにぶちこみます。

それだけです。

  /**
   * readFile - store content from file
   * @param {string} file - target File
   */
  readFile(file){
    const fs = require('fs');
    this.contents = fs.readFileSync(file, 'utf8').trim();
  }

initialize() 全パラメータの初期化

このメソッドは前半と後半に分けられます。

前半 parameters、parameterValues、legalValues、parameterPositionsの内容を埋めます

• ステップ1: readFile(file)で読み込んだthis.contentsから1行ずつ処理します
• ステップ2: ":"で行を分割してペアを作成します
• ステップ3: pair[0]をthis.parametersにプッシュします
• ステップ4: ","でpair[1]を分割して配列を作成します
• ステップ5: ステップ４で分割したすべての値をthis.parameterValuesにプッシュします。
• ステップ6： legalValuesの作成(ちなみにlegalValuesは扱いやすいように数字に置き換えられます。)
• ステップ7: parameterPositions 11個のparameterValuesに対してそれぞれどのParameterに所属するか計算します

Switch: on, off
Browser: Chrome, Firefox, Opera, Lynx
OS: Windows, Mac, Linux
Membership: Member, Guest

を解析した結果各パラメータは下記のようになるはずです

    this.parameters = ["Switch","Browser","OS","Membership"];
    this.parameterValues = ["on","off","Chrome","Firefox","Opera","Lynx","Windows","Mac","Linux","Member","Guest"];
    this.legalValues = [
     [0,1],
     [2,3,4,5],
     [6,7,8],
     [9,10]
    ];
    this.parameterPositions = [
     0,0,
     1,1,1,1,
     2,2,2,
     3,3
    ];

後半　組み合わせを計算します

Parameter Valuesのすべての可能な組み合わせは下記のようなマトリックスになるはずです。

unusedPairs	on	off	Chrome	Firefox	Opera	Lynx	Windows	Mac	Linux	Member	Guest
on	0	0	1	1	1	1	1	1	1	1	1
off	0	0	1	1	1	1	1	1	1	1	1
Chrome	0	0	0	0	0	0	1	1	1	1	1
Firefox	0	0	0	0	0	0	1	1	1	1	1
Opera	0	0	0	0	0	0	1	1	1	1	1
Lynx	0	0	0	0	0	0	1	1	1	1	1
Windows	0	0	0	0	0	0	0	0	0	1	1
Mac	0	0	0	0	0	0	0	0	0	1	1
Linux	0	0	0	0	0	0	0	0	0	1	1
Member	0	0	0	0	0	0	0	0	0	0	0
Guest	0	0	0	0	0	0	0	0	0	0	0

これをunusedPairsという多次元配列で表現します
このマトリックスから一つ一つ数えてunusedCountsを計算しましょう。

	unusedCounts
on	9
off	9
Chrome	7
Firefox	7
Opera	7
Lynx	7
Windows	8
Mac	8
Linux	8
Member	9
Guest	9

_candidateSets() 候補のテストセットをthis.pool分作ります

この関数は下記の3つのステップで候補のテストセット

["on", "Chrome", "Windows", "Member" ]

上記のようなものを抽出します。

ステップ1:_best() 全parameterValuesから最優先のペアを選びます

parameterValuesの最適なペアを計算します
そのアルゴリズムは 2つのパラメータ値の未使用回数を合計し一番多いものを選択します
具体的には下記です

let weight = this.unusedCounts[pair[0]] + this.unusedCounts[pair[1]];

ステップ2: _ordering() 優先すべきParameterの順番を作る

ここでは考えやすくするために
ParameterValuesの0と9、つまり「on」と「Member」が選択されているとします。
this.ParameterPositions　を一回見直してみましょう

this.parameterPositions = [
"0",0,
1,1,1,1,
2,2,2,
"3",3
];

これから
"on"と"Member"sのParameterはそれぞれ"0"と"3"です
つまり　それらを優先すると
Parameterの優先すべき順番は [0,3,?,?]
後半の?と?はここではランダムに選択しましょう。
つまり
[0,3,1,2]
や
[0,3,2,1]
となるでしょう。

ステップ3: _testSet() テストセットを一つ作る

_best()で最優先のParameterValueは既に決定され、優先すべきorderingも確定済みです。
つまり今の状態を表すと testSetは下記のようになっています

	Selected Value
Switch	on
Browser	?
OS	?
Membership	Member

それではどうやって ?の部分 BrowserとOSを選択すればよいのでしょうか？
そのアルゴリズムは下記になります

全未確定のParameterValuesつまりここでは"Browser"と"OS"に関して下記のロジックをまわします

• ステップ1: まずは[候補のParameterValue,すでに決定済みのParameterValue]のペアを作ります
  • つまりこの場合最初のペアは順番的に ["Chrome","on"]となるでしょう
• ステップ2: このペアのunusedCountを調べます。orderingはランダムな順番になっているので["Chrome","on"],["on","Chrome"]両方チェックします。
• ステップ3: ステップ2の結果一番未使用数が多いParameter Valueが選択されます。

["Chrome","on"]と["on","Chrome"] の箇所を下記テーブルで太字にしてみました。

unusedPairs	on	off	Chrome	Firefox	Opera	Lynx	Windows	Mac	Linux	Member	Guest
on	0	0	1	1	1	1	1	1	1	1	1
off	0	0	1	1	1	1	1	1	1	1	1
Chrome	0	0	0	0	0	0	1	1	1	1	1
Firefox	0	0	0	0	0	0	1	1	1	1	1
Opera	0	0	0	0	0	0	1	1	1	1	1
Lynx	0	0	0	0	0	0	1	1	1	1	1
Windows	0	0	0	0	0	0	0	0	0	1	1
Mac	0	0	0	0	0	0	0	0	0	1	1
Linux	0	0	0	0	0	0	0	0	0	1	1
Member	0	0	0	0	0	0	0	0	0	0	0
Guest	0	0	0	0	0	0	0	0	0	0	0

_bestCandidate() 最適なテストセットを選ぶ

テストセット内のすべての未使用の組み合わせをカウントします。
例として

["on", "Chrome", "Windows", "Member" ]

が選ばれたとしましょう
このすべての組み合わせペアは下記になります

["on", "Chrome"]
["on", "Windows"]
["on", "Member"]
["Chrome", "Windows"]
["Chrome", "Member"]
["Windows", "Member"]

これら6つすべての未使用数をカウントし
一番多いものをbestCandidateとして選びます

_modifyUnused() unusedCountとunusedPairs,unusedPairsSearchの掃除

選択されたテストセットの全ペアの組み合わせ

["on", "Chrome"]
["on", "Windows"]
["on", "Member"]
["Chrome", "Windows"]
["Chrome", "Member"]
["Windows", "Member"]

に対して
- ステップ1: nusedCountをdecrementして
- ステップ2: unusedPairs から削除し
- ステップ3: unusedPairsSearch の該当箇所を "0"にセットします

これらを unusedPairsがなくなるまで繰り返します

• readFile(file) ファイルを読み込んで
• initialize()　全パラメータを初期化して
• testSets() テストセットを作り出す
  • while(this.unusedPairs.length > 0) 未使用のペアがなくなるまで
    • candidateSets = _candidateSets() 候補のテストセットを作り出し
    • - best = _best()
    • - ordering = _ordering(best)
    • - testSet = _testSet(best,ordering)
    • bestCandidate = _bestCandidate(candidateSets) 最優先のテストセットを選びます
    • _modifyUnused(bestCandidate)
• printResult(testSets) 結果を表示します

最後に結果を表示して終了します

最後に

さぁ　ちょっと長かったですが、
どのように実装しているか、わかりましたでしょうか？
ちなみにあらゆる方法と同じくこのペアワイズ方も銀の弾丸ではありません。
同値分割・境界値分析等、ランダム入力などの方法と同じく、適材適所で使いましょう。
またnode-qictはpull request大歓迎です
よろしくおねがいします