わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

mutation testing

はじめに

JCKBSE 2012で座長をさせてもらった最初の発表で,最初の質疑がよく聞き取れなかったとはいえ,大要は「mutation testingによって,どんなメリットがあるのか」だったと思います.いわば「そもそも論」です.
私自身も,きっかけは思い出せないものの,mutation testingという手法を知ったのは,今年になってからです.
実は,今回の予稿集の中に,発表を直接聞いたのと別で,mutation testingを取り上げた論文が入っており,そちらに,mutation testingの「そもそも論」が分かりやすく書かれていました.本エントリで自分なりに解説してみます.

先に,参考にしたものを

発表・質疑を聞かせてもらったのは,次の文献です.

  • M. Papadakis and N. Malevris: Killing mutants effectively - a search based approach, Proc. JCKBSE 2012, pp.217-226, doi:10.3323/978-1-61499-094-9-217.

読んで感銘を受けたのは,次の文献です.

  • R. Lacanienta, S. Takada, H. Tanno, X. Zhang and T. Hoshino: A mutation test based approach to evaluating test suites for Web applications, Proc. JCKBSE 2012, pp.227-236, doi:10.3323/978-1-61499-094-9-227.

残念ながら,Lacanienta et al.の件の発表は,聞くことができませんでした.というのも,私が座長をしていたのと同じ時間帯のセッションで,別室で発表されていたからです*1.セッション内での発表順は,Papadakis and Malevrisは1番目,Lacanienta et al.は4番目だったので,mutation testingの応用に関心のある聴講者は,まあ両方を聞けたわけです*2
なお,Webから読むのだと,次の2点がまとまっていると思います.

前提

mutation testingをするのにも,いくつか前提があります.
まず,「テスト」のできる,ソースコードがあることです.そして「テスト」そのものも,用意しておきます.ひと揃いのプログラムには通常,多数のテストからなります.そういったテストの集まりを,「テストスイート」と呼びます.
テスト実行の仕方は,古典的なやり方でも,TDD (Test Driven Development)のものでも,差支えなさそうです.結局のところ,ソフトウェアテストを実行できる環境があればよいということです.あとで示しますが,出力の比較ができれば十分なので,テストの「正解」は必要としません.
従来のテストとの違いは,次の点でしょう.ソースコードを自由に改変できることを仮定します.
といってもソフトウェアのライセンスの問題ではありません.テストを実行する環境で---会社・組織などの中でプライベートに---「オリジナルのソースコード」と「改変されたソースコード」を保持でき,それぞれに対して,あらかじめ用意したテストスイートの,各テストが実行できればいいのです.

mutation testingの目的

ここで,mutation testingの目的を,明確にしておきたいと思います.
テストスイートの「良さ」を知ったり,テストスイートを改善したりするのに,mutation testingが有用ですよ,ということです.
「良さ」は「網羅性(coverage)」,すなわちプログラムコードのすべての処理にわたってテストできているか,というのと同一視できます.
その一方で,mutation testingのプロセスでは,ソースコードを改変するとはいえ,ソースコードをより良くするよう,書き換えるというのは意図していません.
もちろん,テストスイートを改善することで,ソースコードも改善しやすくなるというのは,ここで指摘しておいても問題にならないでしょう.

mutationとmutant

やっと具体的な話になります.
これまで何度か書いてきたmutationですが,日本語にするなら「突然変異」です.ちなみに,遺伝アルゴリズムとは一切関係がありません.
実際の作業や,論文の記述では,mutantのほうが多く出現します.mutantも日本語にするなら,「突然変異体」です.mutantとは,オリジナルのソースコードの1か所だけを意図的に変更したソースコードをいいます.
どこをどんなのに変更したらいいかは,十分に研究成果があるので,それを取捨選択すればいいでしょう.具体的な変更の仕方は,mutant operatorと呼ばれます.
Wikipediaでは,オリジナルのソースコードの「a && b」を「a || b」に変更するというのが例示されています.Lacanienta et al.には,オリジナルでは関数呼び出ししているけれども,その文を取り除く,というmutant operatorも書かれていました.
「どこ」「どんなのに」のペアは,ソースコードが与えられれば,機械的に求められます.なので「自動生成できる」と言ってもよさそうなのですが,mutation testingの応用(というかJCKBSE 2012に収録された2つの論文)では,テストスイートの生成(generation)に主眼を置くようでして,自動生成という言葉はそっちの目的で使われています.

killed/unkilled mutatnt

テストスイートのテストを一つ選んで*3,オリジナルのソースコード(プログラム)で実行し,出力を得ます.同じテストを,mutantのソースコード(プログラム)で実行し,出力を得ます.そして,2つの出力を比較します.
あるテストで,出力が異なっていたら,違いが判明したという意味合いからか,そのmutantはkilledと呼ばれます.よく「killed mutant」と書かれます.
killedの否定,すなわちテストスイートに属するどのテストでも,オリジナルとmutantとで出力が同じとき,そのmutantはunkilledと呼ばれます.これも「unkilled mutant」と書かれます.
unkilled mutantがあったとき,テストスイートが不十分である---網羅性が完璧ではない---という可能性,すなわちテストスイートへの改善の余地が考えられます.

図示1

手順の概要を,図にしました.

equivalent/non-equivalent mutatnt

オリジナルに対してある変更をしたとき,どんなテストでも出力が一致するような,ソースコードもあり得ます.Lacanienta et al.では

int x = y;
if (z < y)

というオリジナルに対して,「z < y」を「z < x」と変更するようなmutantを例示していいます.Wikipediaでは

int index = 0;
...
index++;
...
if (index == 10)

がオリジナル,「==」を「>=」に変更したものをmutantとしています.
そのようなmutantを,equivalentといいます.「equivalent mutant」とも書かれます.そしてequivalentでなければ,「non-equivalent mutant」,あるいはnon-equivalentといいます.
このように,killedとunkilled,equivalentをnon-equivalentという,2種類のペアが定義されました.
さてなのですが…「今ある」テストスイートで,オリジナルとmutantとで結果がすべて同じというとき,それがunkilled mutantなのかequivalent mutantなのか,識別できるのかが,気になります.
その識別ですが,Wikipediaでは「one of biggest obstacles」,要は「ムズい」と書いていました.JCKBSE 2012の2つの論文にも,その識別方法について記載はありません.
さしあたりは,ソースコードの目視,でしょうか.例えば,オリジナルとmutantの間で差分をとって見比べるのです.

少し脱線

情報セキュリティを学んだ人への情報提供として,少し脱線をします.
原始的な方法でソフトウェアテストを行い,結果が期待するものであることを目視で確認するのは,ディジタル署名の署名文復元法に似た面があります.
署名文復元法では「正しく復元できた」かどうかに判定が必要で,しばしば計算機のみでは困難になります.
そして,ディジタル署名の認証子照合法に対応するテスト手法が,今回のmutation testingにおける,一つのテストのオリジナルとmutantとの実行になります.あらかじめセッティングをして実施すれば,テスト実行も,出力の比較(照合)も,計算機がやってくれるのです.
equivalent mutantは,授業では取り上げませんでしたが,ミラー・ラビン素数判定法をかいくぐるけれども,実は合成数という,カーマイケル数のようなものです.
unkilled mutantは擬素数ですね.equivalent mutantでなければ,テストを増やすことで,合成数と判定できるのです.

図示2

4種類のmutantの関係を図にしてみます.ベン図でも描けますが,テープ図にするのが分かりやすいように思います.

細長い長方形をテープに見立てて,これがmutant全体の集合です.具体的にどんなのになるかは,ソースコードと,mutant operatorに依存します.
そしてそのmutant全体を,killedかunkilledか,そしてequivalentかnon-equivalentかで分けることができます.
定義から,equivalentならばunkilledであり,対偶をとると,killedならばnon-equivalentになります.

スコア

mutantを,「killed mutant」「unkilled mutant」「equivalent mutant」「non-equivalent mutant」にうまく識別・分類できたとき,mutation scoreが,次の式で算出できます.
mutation score = killed mutantの数 / non-equivalent mutantの数
言葉にすると,次のようになります.equivalent mutantはスコアの対象外とした上で,すべての(non-equivalentな)mutantを分母,killed mutantを分子とした割合を,mutation scoreとします.
mutation scoreは,高ければ高いほうがよいのです.より多くのmutantをkillできるからです.といったわけで,このmutation scoreが,網羅性の指標となります.
mutation scoreの最大値は1です.これは,non-equivalent mutantとkilled mutantの数が等しい,すなわち,non-equivalentならば必ずkilledである,という状態のときに該当します.
mutation scoreが1に満たないとき,unkilled mutantとオリジナルとの違いを比べて,テストケースを充実させればいい,となります.

まとめ,そしてmutation testingを学ぶ意義

これまでの内容をまとめますと,次のようになります.

  • mutation testingは,テストスイートの質を数量化し改良する手法です.副次的な効果として,ソースコードの質を高めることもできます.
  • オリジナルとmutationとで,すべてのテストの結果が同じとき,「テストスイートが不十分」という可能性と,「テストスイートを充実させても異なる結果にはできない」という可能性があります.後者を取り除いて,「結果が同じになるmutantの数」を「全てのmutantの数」で割った値が,スコアとなります.

そして,ソフトウェア開発やテストに必ずしも関わらない者が,mutation testingから何を学べばいいかというと,次の2点でしょう.

  • 「より良くしたい対象」と,「実際の活動の適用対象」は,違うことがあります.
    • JCKBSEのセッションで,おそらく質疑がスムーズにいかなかったのは,発表者はテストスイートに関心を持っていたけれど,そこで手法を聞いた質問者は,mutantsによってソースコードそのものが改良できると考えてしまったのではないか,と思っています.
    • 教育で,「子どもたちに学力をつけさせたい」と願っても,主に見たり批判したりするのは「教科書・書籍」「授業報告」,すなわち教える側の活動になりがちです.
  • 内部を変えても結果が変わらないときに,外から観測する者は何を考えればよいか,というのにも配慮したいものです.
    • 4種類のmutantの定義を聞けば,その中のunkilledとequivalentとの区別が,重要な問題であるように思えます.それはそれとして(区別は何らかの方法でできるとして),equivalentを除外し,比率を算出することで指標づくりや改善に活用されています.
    • 言い換えると,未解決な部分があるからといって,全体を否定するわけにはいかないのです.

(リリース:Mon Aug 27 21:58:16 2012ごろ.帰りのアテネ国際空港にて,ドバイ行きの飛行機を待ちながら)

(最終更新:2013-02-21 早朝)

*1:あの日,誰だったかに,「○○先生は,私がsession chairするのの裏(でsession chair)なのですよね.あ,いや,私のほうが裏なのですが」と言って,笑いをとったものです.

*2:政治的配慮でそのように分かれたのでなかったことを,祈るのみです.

*3:実際には,順番にテストしていきます.