2020-06-06

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

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

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

他にも2因子に限定しないカバリングアレイという抽象概念がありますが、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

仕組み

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

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

組み合わせ
  • ペア
ブラウザ 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

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

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

格納条件

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

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

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

  • ブラウザ
  • 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: It makes combinations covering pairs for pairwise testing.It makes combinations covering pairs for pairwise testing. - GitHub - walkframe/covertable: It makes combinations covering pairs for pairwise testing.https://github.com/walkframe/covertable

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

そのため Python と TypeScript で2実装あります。 このブログを見ている人は 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)は必ず因子よりも小さくなるようにしてください。 例えば、3因子しかないのに3因子間網羅をしても 総当たりと変わりません。

フィルタ

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

  • 前条件に当たる 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

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

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

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

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

Tolerance

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

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

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

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

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

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

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

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

Sorter

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

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

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

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

hash はペアと seed (オプション) によって 順番を決定します。 この sorter は オプションとして seeduse_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: It makes combinations covering pairs for pairwise testing.It makes combinations covering pairs for pairwise testing. - GitHub - walkframe/covertable: It makes combinations covering pairs for pairwise testing.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://docs.microsoft.com/ja-jp/archive/msdn-magazine/2009/december/test-run-pairwise-testing-with-qict