![1. ミュータントの生成
一般的なミューテーションテスト[1]の手法通り
? 演算子(+, -, *, /, !, ==, など）の置換
? Boolean値の反転
? 定数の置換
など 演算子の置換
int doubledDiff(int a, int b) { int doubledDiff(int a, int b) {
int c = a + b; int c = a - b;
int d = a – b; int d = a – b;
return c * d; } return c * d; }
プログラム ミュータント
11
[1] An analysis and survey of the development of mutation testing,
Yue Jia, Mark Harman(2010, IEEE Software Engineering)](https://image.slidesharecdn.com/120628-120627211342-phpapp01/85/Automated-Oracle-Creation-Support-or-How-I-Learned-to-Stop-Worrying-about-Fault-Propagation-and-Love-Mutation-Testing-slide-for-lab-seminor-Japanese-11-320.jpg)
![2. 変数へのランク付け(2/3)
killできるミュータント数順に変数を並べれば良いとも限らない
← 変数間に依存関係がある場合うまくいかない
例) retでkill出来るミュータントは必ずxでkillできる
x y ret
なるべく少ない個数の変数で，
プログラム 5 10 30
すべてのミュータントをkillしたい
ミュータント1 -9 10 -27
ミュータント2 6 10 30
ミュータント3 5 -8 30
集合被覆問題として解ける ミュータント4 -4 10 -20
貪欲法による近似解法[2]が有名 13
3kill 1kill 2kill](https://image.slidesharecdn.com/120628-120627211342-phpapp01/85/Automated-Oracle-Creation-Support-or-How-I-Learned-to-Stop-Worrying-about-Fault-Propagation-and-Love-Mutation-Testing-slide-for-lab-seminor-Japanese-13-320.jpg)
![実験設定(1/2)
テスト対象：
航空機器の実アプリケーション
Simulink(組み込みシステム向けの，モデル駆動開発ツール)
で作られたモデルから自動生成されたLustreコード
DWM1, 2: 商用コクピットシステムのウィンドウマネージャの一部
Vertmax, Latctl: フライトガイダンスシステムの一部
テストの入力(RQ3)：
カバレッジ基準を満たすテストケースを自動生成する既存手法[4]
を利用，以下の2つのカバレッジに対してそれぞれ10通りのテストス
イートを生成
ブランチカバレッジ 18
MC/DC(Modified Condition/DeCision)カバレッジ[3]](https://image.slidesharecdn.com/120628-120627211342-phpapp01/85/Automated-Oracle-Creation-Support-or-How-I-Learned-to-Stop-Worrying-about-Fault-Propagation-and-Love-Mutation-Testing-slide-for-lab-seminor-Japanese-18-320.jpg)
![参考文献
ミューテーションテスト
[1] An analysis and survey of the development of mutation testing,
Yue Jia, Mark Harman(2010, IEEE Software Engineering)
がとても詳しい．2010出版で，既に120披引用
マシンパワーの増加もあって，最近流行っている？
集合被覆問題の貪欲法による解法
[2] A Greedy Heuristic for the Set-Covering Problem
V. CHVATAL(1979, Mathematics of Operations Research)
有名な解法なので，ぐぐると日本語資料もたくさんある 34](https://image.slidesharecdn.com/120628-120627211342-phpapp01/85/Automated-Oracle-Creation-Support-or-How-I-Learned-to-Stop-Worrying-about-Fault-Propagation-and-Love-Mutation-Testing-slide-for-lab-seminor-Japanese-34-320.jpg)
![参考文献
MC/DCカバレッジ
[3] DO-178B, Software Considerations in Airborne Systems and
Equipment Certification
RTCA(Requirements and Technical Concepts for Aviation ), 1992
厳格なテストを必要とした航空業界の人々が提案
構造カバレッジメトリクスを満たすための，
モデル検査器を用いたテストケース自動生成
[4] Coverage Based Test-Case Generation using Model Checkers
Sanjai Rayaduragam, Mats P.E. Heimdahl, 2001,
35
IEEE Int’l Conf. on Engineering of Computer Based Systems](https://image.slidesharecdn.com/120628-120627211342-phpapp01/85/Automated-Oracle-Creation-Support-or-How-I-Learned-to-Stop-Worrying-about-Fault-Propagation-and-Love-Mutation-Testing-slide-for-lab-seminor-Japanese-35-320.jpg)
![著者(MATT STAATS)による関連研究
[5] “Programs, tests, and oracles: the foundations of
testing revisited” Matt Staats, Michael W. Whalen,
Mats P. E. Heimdahl (ICSE 2011, Distinguished Paper)
- テストオラクルも含めてテスティングの枠組みを再考しよう！
[6] “Better testing through oracle selection” Matt
Staats, Michael W. Whalen, Mats P. E. Heimdahl
(ICSE 2011(New Ideas and Emerging Results Track))
- テストオラクルの選択でテストの欠陥発見能力が変わること
を調べたよ！
36
発表論文は，上記２つの論文を元にしたもの](https://image.slidesharecdn.com/120628-120627211342-phpapp01/85/Automated-Oracle-Creation-Support-or-How-I-Learned-to-Stop-Worrying-about-Fault-Propagation-and-Love-Mutation-Testing-slide-for-lab-seminor-Japanese-36-320.jpg)
「Automated Oracle Creation Support, or: How I Learned to Stop Worrying about Fault Propagation and Love Mutation Testing」 slide for lab seminor (Japanese)
- 1. Automated Oracle Creation Support, or: How I Learned to Stop Worrying about Fault Propagation and Love Mutation Testing (ICSE2012) 輪講用資料 対象: コンピュータ科学専攻の修士?博士学生 （ソフトウェア工学専攻とは限らない） 1 発表時間: 25分 2012年 6月 28日
- 2. 発表論文 “Automated Oracle Creation Support, or: How I Learned to Stop Worrying about Fault Propagation and Love Mutation Testing” - テストオラクル（後述）の選択を自動化する By. Matt Staats (Korea Advanced Institute of Science & Technology) Gregory Gay, Mats P. E. Heimdahl (University of Minnesota) 34th International Conference on Software Engineering (ICSE 2012, Acceptance ratio: 21%) 2
- 3. テストとは テスト：実装の正しさを，実行して確かめること // x2 + |x| + 5を求める X=3とする int calc(int x) { int val = x * x; if (x > 0) { val += x; } else { val -= x; } return val + 5; } 正しいかわからないプログラム 3
- 4. テストオラクルとは オラクル オラクル：正しい振舞いを決めるもの 期待値オラクル // x2 + |x| + 5を求める X=3とする int calc(int x) { ? ここでのvalは9である int val = x * x; if (x > 0) { ↑本研究の対象 val += x; } else { ? この分岐は実行されない val -= x; } return val + 5; ? 出力は5以上である } 出力変数だけでなく，内部変数もオラクルに利用することで， 4 テストの結果が改善できる (Staats, 2011)
- 5. 論文概要 問題： ? オラクルの選択は重要だが，現状は出力変数のみ着目 ? 全ての内部変数に期待値を設定するのはコスト大 目的: テストオラクルの選択を自動化したい 解法: ミューテーションテストを応用して，各変数をランク付け， ランク上位の変数をテストオラクルとして利用 結果: ４つの実アプリケーションに適用 標準的なやり方と比べ最高145.8%の性能向上 5
- 6. 提案手法の使われ方 提案手法 プログラム ミュータント (1)ミュータ ント生成 (2)テストを実行 テスト入力 変数の有効性を調べる 変数の有効性 既存研究が ランキング 多く存在 (3)ランキングの上位から， - 少ない変数 必要そうな変数を選択 - 欠陥発見に役立つ オラクルの変数集合 {x, y,…} テスト実行者 入力に応じて， 6 変数に期待する値を設定 期待値オラクルの集合 {x=3, y=5,…}
- 7. 前提知識：ミューテーションテスト(1/2) テストの欠陥発見能力を知りたい テストの例） ２乗差を求めるメソッドdoubledDiff(a, b)のテスト テスト１ assertEqual( 1, doubledDiff(1, 0)); 成功 テスト2 int doubledDiff(int a, int b) { assertEqual( 成功 int c = a + b; 12, doubledDiff(4, 2)); int d = a – b; return c * d; } テスト3 成功 assertEqual( 5, doubledDiff(3, 2)); 7 どのテストが「良い」だろうか？
- 8. 前提知識：ミューテーションテスト(2/2) ミュータント：プログラムの一部を変換して欠陥を埋め込んだもの テスト１ ミュータント1 欠陥 assertEqual( int doubledDiff(int a, int b) { 成功 1, doubledDiff(1, 0)); int c = a - b; 成功 int d = a – b; テスト2 return c * d; } assertEqual( 失敗 ミュータント2 12, doubledDiff(4, 2)); 失敗 int doubledDiff(int a, int b) { テスト3 int c = a + b; 失敗 int d = a – b; assertEqual( 成功 return c / d; } 5, doubledDiff(3, 2)); 欠陥 8 テスト2が良い（欠陥発見能力が高い）とわかる
- 9. 提案手法の使われ方 提案手法 プログラム ミュータント (1)ミュータ ント生成 (2)テストを実行 テスト入力 変数の有効性を調べる 変数の有効性 ランキング (3)ランキングの上位から， 必要そうな変数を選択 オラクルの変数集合 テスト実行者 9
- 10. 提案手法概観 提案手法 プログラム ミュータント (1)ミュータ ント生成 (2)テストを実行 テスト入力 変数の有効性を調べる 変数の有効性 ランキング (3)ランキングの上位から， 変数を選択 オラクルの変数集合 テスト実行者 10
- 11. 1. ミュータントの生成 一般的なミューテーションテスト[1]の手法通り ? 演算子(+, -, *, /, !, ==, など）の置換 ? Boolean値の反転 ? 定数の置換 など 演算子の置換 int doubledDiff(int a, int b) { int doubledDiff(int a, int b) { int c = a + b; int c = a - b; int d = a – b; int d = a – b; return c * d; } return c * d; } プログラム ミュータント 11 [1] An analysis and survey of the development of mutation testing, Yue Jia, Mark Harman(2010, IEEE Software Engineering)
- 12. 2. 変数へのランク付け(1/3) 各ミュータントに対してテストを実行し， 変数の値を毎ステップ監視 プログラム 例）ある時点での変数の値 x y ret ミュータント1 プログラム 5 10 30 テスト ミュータント1 -9 10 -27 入力 ミュータント2 6 10 30 ミュータント2 ミュータント3 5 -8 30 ミュータント3 ミュータント4 -4 10 -20 ミュータント4 3kill 1kill 2kill 12 元のプログラムと違った値を示す変数はバグ検出に役立ちそう
- 13. 2. 変数へのランク付け(2/3) killできるミュータント数順に変数を並べれば良いとも限らない ← 変数間に依存関係がある場合うまくいかない 例) retでkill出来るミュータントは必ずxでkillできる x y ret なるべく少ない個数の変数で， プログラム 5 10 30 すべてのミュータントをkillしたい ミュータント1 -9 10 -27 ミュータント2 6 10 30 ミュータント3 5 -8 30 集合被覆問題として解ける ミュータント4 -4 10 -20 貪欲法による近似解法[2]が有名 13 3kill 1kill 2kill
- 14. 2. 変数へのランク付け(3/3) 貪欲法による変数へのランク付け アルゴリズム： 1. RankedVariableを空集合で初期化 2. UnkilledMutantsにすべてのミュータントを代入 3. UnkilledMutants中のmutantを最も多くkillできる 変数vを選択し，RankedVariableに加える 4. UnkilledMutantsが空になるまで，3を繰り返す RankedVariableに追加された順に，ランクが高いとする． 14
- 15. 3. 適切なオラクル数の見積り(1/2) 何個の変数をオラクルに使うべきか？ 多くの変数を使う ○ 欠陥発見に役立つ × 人間が期待値を設定するのが大変 最適な個数はわからない → 選択の基準を提供 15
- 16. 3. 適切なオラクル数の見積り(2/2) Fault finding effectiveness |その変数集合で ????できるミュータントの数| := |すべてのミュータントの数| オラクルに使う変数の数を1つ増やすと，effectivenessは上昇する その上昇度合が閾値以下になると，十分なオラクル数だと言える オラクルサイズとeffectivenessの関係（イメージ） 100 effectiveness 80 60 40 20 16 0 0 5 10 15 オラクルサイズ
- 17. 研究課題(RESEARCH QUESTION) ? RQ1: 提案手法は，オラクルデータの選択に関して， 標準のやり方と比べて実用上優れているだろうか？ ? RQ2: ミューテーションベースの手法は潜在的にどれ だけの最大効率を持つだろうか．また，実用上の効率 と最大効率はどの程度異なるだろうか？ ? RQ3: テストに対する入力の違いはどの程度，提案手 法の効率に影響するだろうか？ 17
- 18. 実験設定(1/2) テスト対象： 航空機器の実アプリケーション Simulink(組み込みシステム向けの，モデル駆動開発ツール) で作られたモデルから自動生成されたLustreコード DWM1, 2: 商用コクピットシステムのウィンドウマネージャの一部 Vertmax, Latctl: フライトガイダンスシステムの一部 テストの入力(RQ3)： カバレッジ基準を満たすテストケースを自動生成する既存手法[4] を利用，以下の2つのカバレッジに対してそれぞれ10通りのテストス イートを生成 ブランチカバレッジ 18 MC/DC(Modified Condition/DeCision)カバレッジ[3]
- 19. 実験設定(2/2) ミュータント： 250のミュータントを生成し，半分を訓練用，残りを評価用 オラクル生成方法(RQ1, RQ2): Random: 出力変数および内部変数からランダムにn個選択 Output-base: 出力変数をまずオラクルに加え， その後，内部変数からランダムに選択 Mutation-based: 提案手法 Idealized Mutation-based: 評価用のデータに提案手法を適用 生じるバグをあらかじめ知っている場合に相当する 19
- 20. 结果：４手法の性能比较 |その変数集合で ????できるミュータントの数| 縦軸： Fault finding effectiveness = |すべてのミュータントの数| 20 横軸: オラクル集合の変数の数
- 21. 考察: 提案手法のOUTPUT-BASEに対する性能改善率 RQ1: 提案手法は，オラクルデータの選択に関して，標準のや り方と比べて実用上すぐれているだろうか？ - 最大145.8%の性能向上，概して10-30%程度性能向上 - オラクルサイズ < 出力変数総数のとき，提案手法が優れており， オラクルサイズ == 出力変数総数のとき同じような性能を示し， その後提案手法が優位性を示す傾向 21 10%以上の性能向上
- 22. 考察: 提案手法のOUTPUT-BASEに対する性能改善率 RQ1: 提案手法は，オラクルデータの選択に関して，標準のや り方と比べて実用上すぐれているだろうか？ - 最大145.8%の性能向上，概して10-30%程度性能向上 - オラクルサイズ < 出力変数総数のとき，提案手法が優れており， オラクルサイズ == 出力変数総数のとき同じような性能を示し， その後提案手法が優位性を示す傾向 → 変数に優先付けをすることは役立つだろう 22
- 23. 結果と考察: 理想的な場合の提案手法への性能改善率 RQ2:ミューテーションベースの手法は潜在的にどれだけの最 大効率を持つだろうか．また，実用上の効率と最大効率はどの 程度異なるだろうか？ 理想的な場合のほうが高い欠陥発見能力 しかし，性能差はさほどではない すべて正の値 23 多くの値が20%以下
- 24. 考察：入力による違い RQ3: テストに対する入力の違いはどの程度，提案手法の効率 に影響するだろうか？ → 左右のグラフはどう違うか，ということ 80 100 MC/DCカバレッジの方が，欠陥発見能力が概ね高かった 一方で，グラフの形は概ね似ている 24 →入力による影響を受けない一般的な傾向と推測できる
- 27. 私見(2/2) △著者らの述べる，提案手法の使われ方がいまいちわからな かった．すでに実装があるなら，変数の期待値は機械的に設 定できるのでは． ×人間がオラクルを設定するならば，内部変数の値を設定す るのは，出力変数の値と比べて困難なのではないか． △実験の詳細が不明瞭，対象のコード例や，行数，変数の数 などを示して欲しい △テストの集合に対してオラクルになる変数集合がある， という問題設定がよくわからない．テストメソッドに対してオラク ルが存在するのが普通な気がする． 27
- 28. 以下，参考資料 28
- 29. 集合被覆問題(SET COVER PROBLEM) ある集合Uと，その部分集合の族 F = {Si} (i = 1, …, n) U = S1∪…∪Snのもと，Fの部分集合Cで， ?e∈U, e∈C かつ|C|が最小となるようなものを求める問題 最適解を求める問題はNP困難 ※族とは，集合を要素にもつ集合 ex. {{}, {1, 2}} 貪欲法による解法がよく知られている． まだ覆われていない要素を一番多く含むSiを選ぶという 作業を繰り返せば良い． 29 貪欲法の近似率はln|U| + 1
- 30. 2. 変数へのランク付け(2/3)補足 各変数vに対して，vがkillできるミュータントの集合をMｖとする M = M1∪…∪Mnとする M1,…Mnからなるべく少ない個数の集合を選び， その和集合Msubが ?m∈Mについて，m∈Msubとなってほしい →集合被覆問題 Mx = {m1, m2, m4} x y ret My = {m3} プログラム 5 10 30 Mret = {m1, m4} ミュータント1 -9 10 -27 ミュータント2 6 10 30 30 M = {m1, m2, m3, m4} ミュータント3 5 -8 30 ミュータント4 -4 10 -20 Mx とMyを選ぶと良い
- 31. MC/DC カバレッジ 用語定義： if ( (a == b) && (c == d) || (e == f) ) then condition decision MC/DCカバレッジを満たすとは，以下の1～3が成立すること 1. プログラムのすべてのentry/exit点が少なくとも一度は実行さ れている 2. すべてのconditionが取りうる値を少なくとも一度はとっている 3. それぞれのconditionが，自身を含むdecisionに独立に影響 することを示されている 3を確かめることにより，decisionも網羅できるので， 31 ブランチカバレッジ（すべての分岐先を実行）より強い制約
- 32. 结果(1/2) 32
- 33. 结果(2/2) 33
- 34. 参考文献 ミューテーションテスト [1] An analysis and survey of the development of mutation testing, Yue Jia, Mark Harman(2010, IEEE Software Engineering) がとても詳しい．2010出版で，既に120披引用 マシンパワーの増加もあって，最近流行っている？ 集合被覆問題の貪欲法による解法 [2] A Greedy Heuristic for the Set-Covering Problem V. CHVATAL(1979, Mathematics of Operations Research) 有名な解法なので，ぐぐると日本語資料もたくさんある 34
- 35. 参考文献 MC/DCカバレッジ [3] DO-178B, Software Considerations in Airborne Systems and Equipment Certification RTCA(Requirements and Technical Concepts for Aviation ), 1992 厳格なテストを必要とした航空業界の人々が提案 構造カバレッジメトリクスを満たすための， モデル検査器を用いたテストケース自動生成 [4] Coverage Based Test-Case Generation using Model Checkers Sanjai Rayaduragam, Mats P.E. Heimdahl, 2001, 35 IEEE Int’l Conf. on Engineering of Computer Based Systems
- 36. 著者(MATT STAATS)による関連研究 [5] “Programs, tests, and oracles: the foundations of testing revisited” Matt Staats, Michael W. Whalen, Mats P. E. Heimdahl (ICSE 2011, Distinguished Paper) - テストオラクルも含めてテスティングの枠組みを再考しよう！ [6] “Better testing through oracle selection” Matt Staats, Michael W. Whalen, Mats P. E. Heimdahl (ICSE 2011(New Ideas and Emerging Results Track)) - テストオラクルの選択でテストの欠陥発見能力が変わること を調べたよ！ 36 発表論文は，上記２つの論文を元にしたもの