ソフトウェアの品質を学びまくる2.0

旧ブログからゆっくり移行中です。http://blog.livedoor.jp/prjmng/

機械学習の分野でも注目される、メタモルフィックテスティングとは何か。


スポンサードリンク

 先日のJEITAのイベントで、メタモルフィックテスティング(Metamorphic Testing、MT)というものを知り、「誰かMetamorphic Testingの勉強会やりませんか?」とブログに書いたところ、ソフトウェアテスト・ヒストリアンの辰巳さんが資料をたくさん紹介してくださいました。ちなみに、一緒に勉強してくれる人は誰もいませんでした。

www.kzsuzuki.com

 ICSE MET'2017のサイトにも、MTについてのスライドがたくさん掲載されていたので、学んだところを紹介してみたいと思います。
 日本語の論文も無償で見られるものがいくつかあるのですが、どちらかといえばMTについての知識は前提として、それを機械学習にも応用してみたという内容なので、基本を学ぶには敷居が高そうです(論文だから当たり前か・・・)。

メタモルフィックテスティングの概要

 まず、Chris Murphy氏の『Applications of Metamorphic Testing』(ppt)が一番わかりやすいです。スライド終盤のサマリには、以下のようにあります。

  • MTは、既存のテストケースから新しいテストケースを生成する手法である。
  • テストオラクルのないアプリケーションにおいて、バグ検出の役に立つことがある。
  • ソフトウェアのメタモルフィックプロパティ(metamorphic property)に強く依存する。
  •  一つずつ、見ていきましょう。

    なぜテストケースを増やす必要があるのか。

     「新しいテストケースを生成する」理由は何でしょう。
     境界値分析や組み合わせテストといったテスト技法は、テスト空間を論理的に絞り込み、効率的にテストケースを減らすための技術でした。なぜあえて、テストケースを増やすのか。
     このスライドでは「だって、テストケースは多ければ多いほどいいだろう?」とあります。手動テスト中心のテスターが聞くと吐血しそうな意見ですね。

     たとえばこちらのICSTの論文『Metamorphic Model-based Testing of Autonomous Systems』(pdf)では、ドローンの飛行や障害物回避のシミュレーションプログラムにMTを応用した例が載っています。ドローンの出発地点と到着地点、その経路にある障害物には無数のパターンがあるので、ある特徴的なテストケースをいくつか通すだけでなく、そこから大量のテストケースを派生させて、プログラムの妥当性を検証することが有効なのですね。

    テストオラクルってなんだっけ?

     テストオラクル(Test Oracle)などという用語を使うのは、I/JSTQBで学んだ界隈の人だけだと思っていましたが、MTの文脈では当然のように使われている言葉です。
     ISTQB用語集に追加された日本語検索機能をさっそく使ってみましょう! 使い方は、湯本さんのnoteから!

    note.mu

    テストオラクル(test oracle)
    テスト対象のソフトウェアの実行結果と比較する期待結果のソース。オラクルは、実在する(ベンチマーク用の)システム、他のソフトウェア、ユーザマニュアル、個人の専門知識の場合があるが、コードであってはならない。

     テストオラクルがないというのはつまり、「どういう出力なら正しいのか」がよくわからない状況ということですね。

    メタモルフィックプロパティとは?

     「メタモルフィックプロパティ」(Metamorphic Properties)とは一言でいうと、対象とするソフトウェアが備えている「性質」のことです*1。MTでは、この性質から多くのテストケースを導出することを目的としています。

     それってプログラムの仕様そのもの、あるいはそれを変換した高位レベルテストケースのことでは、とも思いませんか? 一般的なテスト技法でテストケースの絞り込みを行わなければ、テストケースはいくらでも追加できそうなものです。
     たとえば、「12歳以上は料金1,000円」という仕様からは、入力である年齢を12歳、13歳、14歳、・・・とし、出力が「1,000円」となることを確認するテストケースがどんどん作れます。

     ですが、メタモルフィックプロパティはもっと別のものです。
     わたしは、「プログラムの仕様として定義するまでもない、自明な性質」と解釈しています。

    メタモルフィックプロパティの具体例

    数値リストから最小値を求めるプログラム

     抽象的な話になってきたので、先の資料から具体例を引用します。
     整数のリストの中から最小値を得る関数 findMinを、以下のように書くとします(バグがあります)。

     「2、1、4、3」というリストを入力にすると、期待値(つまり最小値)は「1」になる、というテストケースは、以下のように表現することができます。

    { {2, 1, 4, 3}, 1}

     さて、このプログラムが持つべきメタモルフィックプロパティには、どういうものが考えられるでしょうか。
     それはたとえば、「リスト内の数字を並び替えても、出力値(最小値)は同じになる」という性質です。このような性質は、おそらく外部仕様として明示されない、「自明な」性質ということができるでしょう。

     この性質に従ってテストケースを生成すると、

    { {4, 2, 3, 1}, 1}

    というテストケースが通らないことがわかり、バグを検出することができます。

    形式的な表現をしてみると

     少し形式的に表現してみましょう。
     プログラムfに対する元のテストケースを {x, f(x)} と表現します。

     元のテストケースの入力値を関数tに通すと、新しい入力値はt(x)、プログラムfからの出力値はf(t(x))となります。
     一方、元のテストケースの出力値を関数gに通すと、新しい出力値はg(f(x)) となります。
     プログラムfのメタモルフィックプロパティとは、すべての入力値xに対して、f(t(x))=g(f(x))を満たすような関数ペア(t, g)のこと。文字列だと全然わからないですね・・・。

     先のfindMinの例では、関数tは「リスト要素の並び替え」に相当します。出力値の方は変わらないことを期待しているので、関数gは恒等関数になるでしょう。入力に「リスト要素の並び替え」という操作を行っても、出力値は変わらないというのが、findMinのメタモルフィックプロパティです。

    一般的にはどんなプロパティがある?

     一般的に、どんなメタモルフィックプロパティがあるのでしょうか。P.22からその例が書かれています。
     元のテストケースが「要素a~fの総計がsになる」というものだったとして、

  • Permute: 並び替えを行っても総計はsと変わらない
  • Add: 各要素に定数を足すと、総計は s+定数*6 になる
  • Multiply: 各要素に定数を乗じると、総計は s*定数 になる
  • といったものがメタモルフィックプロパティとなります。これはだいぶ単純というか・・・数学以外には適用できそうにない、退屈な性質ですよね・・・。
     もう少し違うタイプとして、以下のようなものが紹介されています。

  • Noise-based: 出力に提供を与えないであろう入力(の変化)
  • Semantically Equivalent: 意味的に「同じ」入力。
  • Heuristic: 元に「近い」入力。
  • Statistical: 統計的に同じ性質を示す入力。
  • 数値計算分野以外での応用

     メタモルフィックプロパティが上で紹介したようなものばかりだと、MTは数値計算関連のプログラムにしか応用できないのではと思いますが、Zhi Quan Zhouさんの講演『Metamorphic Testing: Beyond Testing Numerical Computations』(pdf)によると、数値計算関連分野での適用は全体の4%でしかないそうです*2

     この講演で紹介された適用例は、プログラム難読化ツール*3
     難読化ツールのメタモルフィックプロパティには、たとえば以下のようなものがあります。

  • 同じソースコードを入力するといつでも、動作的に等価なプログラムが出力される。
  • 一つのソースコードに対し繰り返し難読化を何度かけても、動作的に等価なプログラムが出力される。
  •  こういったプロパティを利用して、一般的なテストでは必ずしも検出できないバグが、MTであれば検出できるという例を示しています。

     また、オンライン検索での例も紹介されています。一口にオンライン検索といっても、GoogleのようなWebサイトの検索、ホテルや飛行機の空き状況、商品、用語、地図など無数にありますが、これらに共通して言えそうなメタモルフィックプロパティがあります。

     まず一般的な(general)メタモルフィックプロパティとして、以下が考えられます。

    「AがBに包含されている」という関係が成立しているなら、
  • Aの結果はBの結果の部分集合になる
  • Aの結果の数は、Bの結果の数以下になる
  •  この2つ目のプロパティから導出できる具体的な(concrete)プロパティは、たとえば店舗検索において、

    検索する地域を絞ることで、ヒットする結果は絞る前より少なくなる

    というものが考えられます。このメタモルフィックプロパティを利用してテストケースを生成し、妥当性を確認することができます。

    まとめ

     引用した資料に明確に書かれているわけではないのですが、生成されるテストケースが常に「期待値付き」であることが非常に重要だと思います。いくら大量にテストケースを生成したとしても、それが期待値なしであればあまり役に立ちませんし、自動化もできません。

     テスト技法といえば、テストケースを合理的に選択することと思いがちでしたが、「とにかくたくさんのテストパターンが欲しい」「でもテストオラクルがない・・・」という状況において、有効だが数が少ないテストケースから、期待値付きのテストケースを大量に派生させる技術として、メタモルフィックテスティングが有望な技術だということがわかりました。

    *1:他の資料では、「メタモルフィック関係」(Metamorphic Relations、MR)という用語も出てきますが、どうやら同じものを指しているようです。

    *2:Chris Murphyさんの資料では、実際の応用分野として、生物情報学、機械学習、ネットワークシミュレーション、コンピュータグラフィックスなどがあるとのこと

    *3:クラッカーなどに重要なシステムの内部情報を与えることを防ぐためのプログラム。obfuscator。