2020-06-06

意外と簡単！ペアワイズツールを作ったので大まかな仕組みを解説するよ

テストケースを作ったことがある方はわかると思いますが、単純に総当たりで作るととんでもない組み合わせになってしまうことがあります。

そこで、２因子間の組み合わせのみを網羅することでテストケース数を劇的に減らせます。 2因子間網羅のツールではペアワイズ(オールペア法)と直交表が有名ですが、ここではペアワイズについて解説していきます。

他にも２因子に限定しないカバリングアレイという抽象概念がありますが、２因子に限定したペアワイズのほうが有名ですね。この記事では断りがない限りペアワイズについての解説となります。

info

プログラムを動かした CPU は 2.7 GHz Intel Core i5 です。

用語

因子

テストしたいパラメータのことです。

例えば、「ブラウザ」「端末」の組み合わせでテストケースを作りたいという場合、因子数は 2 となります。

水準

特定の因子内に含まれる値のことです。

例えば、「FireFox」「Chrome」「Edge」のブラウザで表示チェックをしたいという場合、ブラウザの水準数は 3 となります。

因子

水準

ブラウザ

水準数: 3
- FireFox
- Chrome
- Edge

OS

水準数: 4
- iOS
- Android
- Windows
- Linux

端末

水準数: 3
- Windows phone
- iPhone
- Pixel

2因子間網羅とは全因子から 2つを選択し、それらを組み合わせたペアを満たすことです。

今回であれば以下の合計で 33 個が満たすべきペアの個数です。

ブラウザ(水準数:3) x OS(水準数:4) = 12
ブラウザ(水準数:3) x 端末(水準数:3) = 9
OS(水準数:4) x 端末(水準数:3) = 12

仕組み

端的にいうと「すべてのペアを順番に敷き詰める」だけです。

すべてのペアとは先程の２因子間における水準の組み合わせ(直積)の和です。

組み合わせ

ペア

ブラウザ x OS

3 x 4 = 12
- FireFox x iOS
- Chrome x iOS
- Edge x iOS
- FireFox x Android
- Chrome x Android
- Edge x Android
- FireFox x Windows
- Chrome x Windows
- Edge x Windows
- FireFox x Linux
- Chrome x Linux
- Edge x Linux

ブラウザ x 端末

3 x 3 = 9
- FireFox x Windows phone
- Chrome x Windows phone
- Edge x Windows phone
- FireFox x iPhone
- Chrome x iPhone
- Edge x iPhone
- FireFox x Pixel
- Chrome x Pixel
- Edge x Pixel

端末 x OS

3 x 4 = 12
- Windows phone x iOS
- iPhone x iOS
- Pixel x iOS
- Windows phone x Android
- iPhone x Android
- Pixel x Android
- Windows phone x Windows
- iPhone x Windows
- Pixel x Windows
- Windows phone x Linux
- iPhone x Linux
- Pixel x Linux

これらのペアを適切な列に格納し、列が全て埋まったらその行が１つのテストケースとなります。すべての列が埋まった行はもう格納できないので新しい行を用意し、次はそれがペアの格納対象になります。

上記をすべてのペアが格納し終わるまで繰り返します。大まかに言えばこれだけですが、細かいルールがあるので以下ではそれについて説明していきます。

格納条件

ペアはいつでも格納できるわけではありません。

格納対象列に異なる要素が格納されている場合、そのペアは行には格納できません。

例えば、行が下記のように格納されている場合、(端末 列が未格納)

ブラウザ
OS
端末

FireFox
iOS

端末を列に持つペアのうち、ブラウザが FireFox か OSが iOS のものが格納可能なペアとなります。

格納可否
ペア
ブラウザ
OS
端末

o
(FireFox, Windows phone)
Firefox == FireFox
Windows phone

o
(FireFox, iPhone)
Firefox == FireFox
iPhone

o
(Firefox, Pixel)
Firefox == FireFox
Pixel

x
(Chrome, Windows phone)
Firefox != Chrome
Windows phone

x
(Chrome, iPhone)
Firefox != Chrome
iPhone

x
(Chrome, Pixel)
Firefox != Chrome
Pixel

x
(Edge, Windows phone)
Firefox != Edge
Windows phone

x
(Edge, iPhone)
Firefox != Edge
iPhone

x
(Edge, Pixel)
Firefox != Edge
Pixel

o
(iOS, Windows phone)
iOS == iOS
Windows phone

o
(iOS, iPhone)
iOS == iOS
iPhone

o
(iOS, Pixel)
iOS == iOS
Pixel

x
(Android, Windows phone)
iOS != Android
Windows phone

x
(Android, iPhone)
iOS != Android
iPhone

x
(Android, Pixel)
iOS != Android
Pixel

x
(Windows, Windows phone)
iOS != Windows
Windows phone

x
(Windows, iPhone)
iOS != Windows
iPhone

x
(Windows, Pixel)
iOS != Windows
Pixel

x
(Linux, Windows phone)
iOS != Linux
Windows phone

x
(Linux, iPhone)
iOS != Linux
iPhone

x
(Linux, Pixel)
iOS != Linux
Pixel

補完

未格納のペアが少なくなってくると、行が空いていても格納できるペアがないという事態に高確率で遭遇します。

こういう時は適当な値を空いている列に格納してあげるのです。

例えば未格納ペアがない状態で現在の行が次のような状態だとします。

ブラウザ
OS
端末

Chrome
Android

端末の列が空なので以下のうち適当のものを入れてあげればよいです。

Windows phone
iPhone
Pixel

制約条件

このように簡単な仕組みでできているため、ペアワイズは制約条件によるフィルタをかけやすいのです。

先程の組み合わせに違和感を感じていた方もいると思います。例えば Pixel x iOS のような組み合わせはありえませんね。 (ほかにもありえない組み合わせはいっぱいありますが、スルーで)

ペアワイズではこのような組み合わせをもつテストケースの除外が容易に実装できます。実際、ほとんどのペアワイズツールでは制約条件を指定できるはずです。(ちゃんとは調査してない)

covertable

covertable というライブラリを自作しました。 GitHub - walkframe/covertable: makes combinations for testing.makes combinations for testing. Contribute to walkframe/covertable development by creating an account on GitHub.https://github.com/walkframe/covertable

本当は TypeScript (JS) だけあればよかったんですが、あんまり実装に慣れていなかったのでまずPython で作ってから移植しました。

そのため Python と TypeScript で２実装あります。このブログを見ている人は Python 使いの人が多いと思うので、 Python ライブラリの方のみ解説します。とはいえ、npm の方も使い方は概ね同じです。

TypeScript版の詳しい使い方については typescript/README を見てください。

ソースコードが公開されているペアワイズツールは PICT を始めいくつかありますが、ソースコードが複雑で読む気がしなかったので完全なオリジナル実装となりました。

使い方

まずいちばん簡単な例

>>> import covertable

>>> browser = ['FireFox', 'Chrome', 'Edge']
>>> os = ['iOS', 'Android', 'Windows', 'Linux']
>>> machine = ['Windows phone', 'iPhone', 'Pixel']

# リスト型だと出力の内側もリスト型
>>> covertable.make([browser, os, machine])
[
  ['Edge', 'Windows', 'Pixel'],
  ['FireFox', 'Android', 'Windows phone'],
  ['Edge', 'Linux', 'Pixel'],
  ['Chrome', 'iOS', 'Pixel'],
  ['Edge', 'Android', 'iPhone'],
  ['Chrome', 'Android', 'Pixel'],
  ['Chrome', 'Linux', 'Windows phone'],
  ['Edge', 'Windows', 'Windows phone'],
  ['FireFox', 'Linux', 'iPhone'],
  ['Chrome', 'iOS', 'iPhone'],
  ['Chrome', 'Windows', 'iPhone'],
  ['FireFox', 'Windows', 'Pixel'],
  ['FireFox', 'iOS', 'Windows phone'],
  ['Edge', 'iOS', 'Windows phone']
]

# 辞書型だと出力の内側も辞書型
>>> covertable.make({'browser': browser, 'os': os, 'machine': machine})
[
  {'os': 'Windows', 'machine': 'Pixel', 'browser': 'Edge'},
  {'os': 'Android', 'machine': 'Windows phone', 'browser': 'FireFox'},
  {'os': 'Linux', 'machine': 'Pixel', 'browser': 'Edge'},
  {'browser': 'Chrome', 'os': 'iOS', 'machine': 'Pixel'},
  {'os': 'Android', 'machine': 'iPhone', 'browser': 'Edge'},
  {'browser': 'Chrome', 'os': 'Android', 'machine': 'Pixel'},
  {'browser': 'Chrome', 'os': 'Linux', 'machine': 'Windows phone'},
  {'browser': 'Edge', 'machine': 'Windows phone', 'os': 'Windows'},
  {'os': 'Linux', 'machine': 'iPhone', 'browser': 'FireFox'},
  {'os': 'iOS', 'machine': 'iPhone', 'browser': 'Chrome'},
  {'browser': 'Chrome', 'os': 'Windows', 'machine': 'iPhone'},
  {'browser': 'FireFox', 'os': 'Windows', 'machine': 'Pixel'},
  {'os': 'iOS', 'machine': 'Windows phone', 'browser': 'FireFox'},
  {'browser': 'Edge', 'os': 'iOS', 'machine': 'Windows phone'}
]

info

covertable はペアワイズもできますが、3因子間網羅も可能なカバリングアレイのツールでもあります。
make 関数の length キーワード引数が網羅する因子数を意味します。省略した場合は自動的に 2 となります。
この値(length)は必ず因子よりも小さくなるようにしてください。例えば、３因子しかないのに３因子間網羅をしても総当たりと変わりません。

フィルタ

フィルタは前述した制約条件で、 covertable では以下の２種類があります

前条件に当たる pre_filter
後条件に当たる post_filter

呼び出されるタイミングは違いますが使い方は全く同じです。

いずれのフィルタも 行 を辞書として第一引数に受け取り、各列の値に応じて真偽値を返すことで登録可否を決定できます。拒否する場合は False を返します。

>>> covertable.make(
...     {'browser': browser, 'os': os, 'machine': machine},
...     pre_filter=lambda row: not(row['os'] == 'Android' and row['machine'] != 'Pixel'),
...     post_filter=lambda row: not(row['os'] == 'iOS' and row['machine'] != 'iPhone'),
... )
[
  {'os': 'Windows', 'machine': 'Pixel', 'browser': 'FireFox'},
  {'os': 'Linux', 'machine': 'Pixel', 'browser': 'Edge'},
  {'browser': 'Edge', 'machine': 'iPhone', 'os': 'iOS'},
  {'browser': 'Edge', 'machine': 'Windows phone', 'os': 'Linux'},
  {'os': 'Android', 'machine': 'Pixel', 'browser': 'FireFox'},
  {'os': 'Linux', 'machine': 'iPhone', 'browser': 'FireFox'},
  {'browser': 'Chrome', 'os': 'Windows', 'machine': 'iPhone'},
  {'browser': 'Edge', 'os': 'Windows', 'machine': 'Windows phone'},
  {'browser': 'Chrome', 'os': 'Linux', 'machine': 'Windows phone'}
]

pre_filter は値を格納する前にフィルタを行い、条件に合わなければ別のペアか妥当な値で補完します。
post_filter は値を格納してテストケースが出来上がった後にフィルタを行い、条件に合わないケースを削除します。
- filter() 関数で除外しているのとほぼ同じです。

その性質より、同じ条件のフィルタでも post_filter のほうが最終的に出来上がるテストケースは少なくなります。必要に応じて使い分けてください。

warning

pre_filter ですべての組み合わせを弾くような(ありえない)フィルタを入力すると例外が発生するようになっているので注意してください

>>> covertable.make(
...     {'browser': browser, 'os': os, 'machine': machine},
...     # browser が ['FireFox', 'Chrome', 'Edge'] にならないことはないので全部弾かれてしまうはず
...     pre_filter=lambda row: row['browser'] not in ['FireFox', 'Chrome', 'Edge']
... )
Traceback (most recent call last):
  File "<stdin>", line 3, in <module>
  File "/venv/lib/python3.7/site-packages/covertable/main.py", line 113, in make
    row.complement()
  File "/venv/lib/python3.7/site-packages/covertable/main.py", line 64, in complement
    raise InvalidCondition(InvalidCondition.message)
covertable.exceptions.InvalidCondition: It will never meet the condition

Criterion

格納基準です。現状 simple と greedy の２つがあります。 1系 の covertable では sorter のなかに greedy が含まれていましたが、オプションを分割して criterion オプションが誕生しました。

名前の通り greedy は 貪欲 な格納基準で、処理中の行に対して未格納ペアを最も消費するようなペアを採用します。 simple は格納可能なペアであれば何でも採用するため greedy よりもかなり高速です。

大抵の場合 greedy のほうが出力されるケース数は少なくなりますが、必ずしも simple よりも少なくなるとは限りません。因子に含まれる水準が少ないと greedy による効果は小さくなる傾向にあります。

info

全ペアの順番を総当たりすれば確実に最小のテストケースが得られそうですが未格納ペア長の階乗の計算量になってしまうの採用しませんでした。
先程のケースでも 33! で 8683317618811886495518194401280000000 回のループが発生してしまいます。

Tolerance

tolerance は greedy criterion にわたすオプションであり、ここでは許容範囲という意味で使っています。

結論から言うとこの数値を上げると出力する件数が大きくなる代わりに実行時間が小さくなります。

このオプションが登場した経緯をお話します。興味ない方は次のセクションまで飛ばしてください。

2.0.0 のリリースによって covertable はかなり高速化しました。というか 1系の greedy はおそすぎましたね...

アルゴリズム改善の結果も含まれますが、最大の要因は 未格納ペアの最大消化数の上限を設定した ことです。今まで greedy はすべての未格納ペアを最も消化するペアを探して最後までループしていましたが、未格納ペアの最大消化数には上限は 格納可能な要素数 * 現在の行に格納されている要素数 で求められます。この数に達した瞬間に、そのペアを最大としてループを抜けるようにしたことで同じ結果を得つつ、処理を高速化できました。

しかし、まだ高速化の余地があります。 格納可能な要素数 * 現在の行に格納されている要素数 より基準を下げることで数倍から10倍程度の高速化を見込めます。

この基準を下げる数値が tolerance です。大きければ大きいほど基準が下がるため高速化されるというわけです。

詳しくはこちらを参照ください。

Sorter

格納を試行する順番は最終的に出来上がるケースを左右する重要なものです。そこで covertable はこの順番をユーザが制御できるように Sorter を外部から渡せるようにしています。単なる関数なのでユーザが自作することもできます。

バージョン 2.0 の現在は hash と random の2種類があります。

info

sequential sorter は 2.0 で削除されました。
TypeScript版だと生成するペア数が膨大になってしまうためです。

random は試行する順番をランダムで決定します。毎回異なった結果を得たい場合はこちらを採用すると良いでしょう。

hash はペアと seed (オプション) によって順番を決定します。この sorter はオプションとして seed と use_cache (default: True)を受け取ります。

seed はペアをハッシュ化するためのソルトのようなものです。 hash sorter は受け取った因子数、要素数が同じであれば、毎回同じ数のケースを作成できますが、それが絶対に最小のケースとは限りません。自分好みのケースを作るような seed の値を自分で指定することができるのです。

use_cache はハッシュ化した結果をメモリ内に保存するかどうかを選択します。 hash sorter が利用するハッシュ関数は md5 なのでそこまで大きな負荷にはなりませんが、キャッシュを利用することで多少の高速化が見込めます。 Python版だと約10%ほど高速化されます。 TypeScript版は v2.1.0 にて予めソート(以降プリソートという)するような実装に変更したためキャッシュを保つ必要がなくなりました。

info

Python版でも同じように実装したいところですが、Pythonの set は順序を保たないためプリソートは実装しませんでした。
代わりに dict でプリソートしてみたところ、setを使って都度ソートする既存実装よりも遅くなりました。多分集合演算がビルトインで実行できないのが処理時間に影響していると思われます。

10^100 のテストケースだと 60MB ほどのメモリを消費します。メモリの使用量を抑えたい場合はこのオプションを OFF にしてください。

covertable で作られる結果(最小)を総当たり数と比較してみます。

水準数^因子数
条件
最小ケース数
総当り数
時間

3^4
デフォルト
9
81
0.0006s

3^13
greedy, hash(seed:1084)
17
1594323
0.03s

4^15 3^17 2^29
greedy, hash(seed:19)
34
145398897491341278707712
7.47s

4^1 3^39 2^35
greedy, hash(seed:14)
26
28297461724253869811171328
14.70s

2^100
simple, hash(seed:6)
12
1267650600228229401496703205376
0.63s

10^20
greedy, hash(seed:1139)
195
100000000000000000000
14.48s

結果だけを見れば他の製品に引けを取らない感じになっていると思います。

どう作ったか

ループのネストが深くなるとぼくのような鳥頭ではとてもプログラムを理解できないので、できるだけシンプルな構造になるように工夫しました。

まず、全ての要素に一意な連番を振ります。 (内部では convert_factors_to_serials という関数で作成)

例えば以下のような要素があったら

factors = [
  ['FireFox', 'Chrome', 'Edge'],
  ['iOS', 'Android', 'Windows', 'Linux'],
  ['Windows phone', 'iPhone', 'Pixel'],
]

以下のような連番に差し替わり、内部的にはこの数値で管理されます。

serials = [
  [0, 1, 2],
  [3, 4, 5, 6],
  [7, 8, 9],
]

これにより、ペアを構成する値が必ず一意になるので、ペアのみを set で管理できるようになります。(未格納ペアという)

また、番号により要素がどの因子に属しているかも自動的に判定されるので混ざることはありません。 (内部では make_incompleted という関数で作成)

info

例えば、 Firefox x iOS のペアは (0, 3) のタプルで表せます。
また、 0 ~ 2 がブラウザ、 3 ~ 6 が OS、 7 ~ 10 が端末を意味するということを別のマッピング(parents)で管理しています。

その後は未格納ペアから順にペアを取り出し格納可否を判定、可能であれば行に値を格納した後に未格納ペアから当該ペアを削除します。(これで格納済判定となります)

上記を未格納ペアがなくなるまで繰り返します。

以上がプログラムの概要です。

メインのソースコードは 150行ほどしかないので簡単に読めると思います。

スターまってるぜ〜

GitHub - walkframe/covertable: makes combinations for testing.makes combinations for testing. Contribute to walkframe/covertable development by creating an account on GitHub.https://github.com/walkframe/covertable

参考

『Pairwise法（All-Pairs法）のヒューリスティックアルゴリズムを試してみる』PICTが採用しているPairwise法（All-Pairs法）のヒューリスティックアルゴリズムについては2009年10月09日の記事で説明しました。今回は…https://ameblo.jp/pictmaster/entry-10377792413.html 『フリーな直交表ツール PictMaster を使用した場合のPairwise法との比較』PictMasterは直交表方式とPairwise方式の両方式の組み合わせ生成をサポートした日本国内では事実上唯一のフリーでオープンソースなテストツールです。…https://ameblo.jp/pictmaster/entry-12254427995.html テストの実行: QICT によるペアワイズテストhttps://learn.microsoft.com/ja-jp/archive/msdn-magazine/2009/december/test-run-pairwise-testing-with-qict