NTT ソフトウェアイノベーションセンタ 丹野 治門

Presentation on theme: "NTT ソフトウェアイノベーションセンタ 丹野 治門"— Presentation transcript:

1 NTT ソフトウェアイノベーションセンタ 丹野 治門
make test-zesti： A Symbolic Execution Solution for Improving Regression Testing NTT ソフトウェアイノベーションセンタ　丹野 治門

2 目的と貢献 目的 現状の問題点 提案 主な貢献点 ソフトウェアにおけるより多くのバグを見つけたい
開発者が作るテスト(○意味あるテスト，✕高コスト) 機械的に作るテスト(○低コスト, ✕無意味なものが多い) (例) パスカバレッジ向上を目指したSymbolic Execution 提案 開発者が作った(回帰テスト向け)テストケースを種にし て様々なバリエーションを生成 主な貢献点 OSSでしっかり評価，未知のバグを発見 ICSE'12 勉強会 2012/8/30

3 着眼点 Sensitive Operationsの周辺を徹底的にテスト するようにする
具体例：配列へのアクセス 回帰テスト用テストケース （開発者が作成） int v[100]; void f(int x){ if(x > 99){ x = 99; } v[x] = 0; この2つのテストケースでパスカバレッジ（分岐網羅）は100%だが・・・ TestCase01 x = 100 TestCase02 x = 50 x = -1のとき配列不正アクセスエラー Sensitive Operation周辺はバグが存在する可能性が高い！ ICSE'12 勉強会 2012/8/30

4 着眼点 Sensitive Operationsの周辺を徹底的にテスト するようにする
具体例：配列へのアクセス 回帰テスト用テストケース （開発者が作成） int v[100]; void f(int x){ if(x > 99){ x = 99; } v[x] = 0; この2つのテストケースでパスカバレッジ（分岐網羅）は100%だが・・・ TestCase01 x = 100 TestCase02 x = 50 x = -1のとき配列不正アクセスエラー！ 提案手法 TestCase03 x = -1 ICSE'12 勉強会 2012/8/30

5 手法 テスト実行と同時にSymbolic Executionを実施 「Symbolic Execution結果＋追加条件」で新規テスト生成
提案手法によるテストケース生成の一例 TestCase02 x = 50 int v[100]; void f(int x){ if(x > 99){ x = 99; } v[x] = 0; 入力変数： 　x = x0 パス条件： 　not(x0 > 99) テストケース 生成 TestCase03 x = -1 Symbolic Execution 境界値条件 　x0 > 0 && 　x0 <100 追加！ ICSE'12 勉強会 2012/8/30

6 評価 評価に用いたOSS(３つ) 評価結果 GNU Coreutils，libdwarf，readelf
合計58件(うち，52件は未知)のバグを検出 OSSコミュニティに報告，バグ改修も進んでいる 提案手法で発見したCoreutilsのバグ一覧 Min Depth バグに到達するまでの「条件分岐」の数 通常のSymbolic Executionでは時間がかかりすぎて発見しにくいバグ ICSE'12 勉強会 2012/8/30 Paul Dan Marinescu and Cristian Cadar “make test-zesti： A Symbolic Execution Solution for Improving Regression Testing” ICSE2012.　Table1より引用

7 NTT ソフトウェアイノベーションセンタ 張 暁晶
BALLERINA: Automatic Generation and Clustering of Efficient Random Unit Tests for Multithreaded Code NTT ソフトウェアイノベーションセンタ　張 暁晶

8 背景・目的・貢献 背景 目的 貢献 マルチスレッドを用いるソースコードの単体試験は、手間がかかる
テスト対象が持つオブジェクトを、複数のスレッドで触るような試験である このような単体試験を「ランダム生成」する従来手法では・・・ 生成された単体試験の実行が遅い 並行性バグをうまく見つけられない バグじゃないのにバグだという誤報（false alarm）が出る 目的 並行性バグをうまく見つけられるような単体試験をランダム生成する 貢献 並行性バグをうまく見つけられるような単体試験をランダム生成す る手法を提案 生成された単体試験でのfailureを、人手で点検する手間を軽減でき る「クラスタリング手法」も提案 評価：実際のバグ検出による効果確認 ICSE'12 勉強会 2012/8/30

9 →既存手法Randoop algorithm[1]を改造
手法概要1 単体試験のランダム生成： ２つのスレッドのみ用意する それぞれが、ランダムに選ばれたテスト対象のメソッドを1つだけ実行する 並行性バグにあたる確率を上げるために、上記のような「シンプルな」並行コー ドを、「より複雑な」シーケンシャルなランダム生成コードの後ろに追記する BALLERINAが生成した単体試験 シーケンシャルな ランダム生成コード →既存手法Randoop algorithm[1]を改造 並行実行する 2つのスレッド Adrian Nistor et al. “BALLERINA: Automatic Generation and Clustering of Efficient Random Unit Tests for Multithreaded Code”, In Proc. of ICSE 2012, pp , Figure 2 より [1] C. Pacheco, S. K. Lahiri, M. D. Ernst, and T. Ball, “Feedbackdirected random test generation,” in ICSE, 2007. ICSE'12 勉強会 2012/8/30

10 手法概要2 点検すべきfailureを絞り込むクラスタリング手法：
Test Oracleとして既存手法linearizability[2]を採用してい るので誤報が出る可能性がある 「似たような」バグレポートはたぶん、 全部誤報か全部本物のバグかだろう →バグレポートを下記２点によりクラスタリングする Failure発生時に実行していたメソッド Failureの種類 評価では、1個の本物のバグに対して、数百個の誤報が出る →非実用的 クラスタリングの導入後では誤報は3～4個にまで減った [2] S. Burckhardt, C. Dern, M. Musuvathi, and R. Tan, “Line-Up: A complete and automatic linearizability checker,” in PLDI, 2010. ICSE'12 勉強会 2012/8/30

11 評価 6件のOSSに含まれる14個の本物のバグで評価 提案手法は、既存ランダム生成手法より、 2～10倍速くバグを見つけた
Groovy, JDK, JFreeChart, Apache Log4j, Apache Lucene, Apache Pool 提案手法は、既存ランダム生成手法より、 2～10倍速くバグを見つけた クラスタリング手法により、点検すべきfailure の数を4～8倍減らした 未知のバグをさらに3件検出できた Apache Log4j, Apache Poolから ICSE'12 勉強会 2012/8/30

12 On-Demand Test Suite Reduction Dan Hao@Peking University
（株）NTTデータ 技術開発本部　朱峰 錦司

13 議 異 ！ り あ 裁判長！コードカバレッジを保っていても・・・バグ発見能力には疑いの余地があります！ 背景（１／２）
従来のテストケース削減手法は、コードカバ レッジを一定に保てれば減らしてよい、という ものが多い ﾁ ｮ ｼ ｬ 裁判長！コードカバレッジを保っていても・・・バグ発見能力には疑いの余地があります！ ICSE'12 勉強会 2012/8/30

14 背景（２／２） 2つの既存手法を試してみると… 20%以上の確率でバグ発見能力6割減 20%以上の確率でバグ発見能力4割減
※元論文P.2から抜粋 ICSE'12 勉強会 2012/8/30

15 テストケース削減によるバグ発見能力低下の実績データをもとに、この集合を線形計画法で発見する！
目的 バグ発見能力を一定に保ちながらテストケース を削減する手法の提案 全てのテストケースの集合 以下を満たす最小のテストケースの集合 ・バグ発見能力の低下は l% 以下 ・（統計学に頼るので）信頼度は c% テストケース削減によるバグ発見能力低下の実績データをもとに、この集合を線形計画法で発見する！ ICSE'12 勉強会 2012/8/30

16 手法概要（１／２） 実績データの作成 既存のソフトウェアをもとに、テストケースの削減と バグ発見能力の低下との相関を分析
信頼度は90%,95%,99%の3パターンに決め打ち ※元論文P.4から抜粋 テストケース数を4から2に減らすと、99%の確率で バグ発見能力は（最高で）83.3%減少してしまう ICSE'12 勉強会 2012/8/30

17 手法概要（２／２） 線形計画法の適用 モデル式の簡易化（省略） 2種類のモデル式を提案 local constraintsに基づく式
あるテストケースの部分集合において、q行目のソースコードをカバーするケースがもともとp_j個あった状態からq個に減少した際に… 線形計画法の適用 2種類のモデル式を提案 local constraintsに基づく式 global constraintsに基づく式 モデル式の簡易化（省略） 全ての行個別で不等式が成り立たたないといけない ※元論文P.5から抜粋 過去の実績では、テストケースをp_j個からq個に減らすとこれぐらい能力が落ちる ソースコード全体で成り立てばよい ※元論文P.5から抜粋 ICSE'12 勉強会 2012/8/30

18 評価 3つのシナリオで手法を評価 他手法との比較 テストケース削減効果は少ないが、バグ発見能力を維 持したい場合は非常に効果的 対象
実績データ 適用対象 結果 1 8つのCプログラム 1つのプログラムの半分 プログラムの残り半分 全てのプログラムにおいて、2つのモデル式の場合ともに、結果は妥当であった 2 1つのJavaプログラムの3リビジョン 前バージョン 後バージョン バージョン番号が近いほうがより結果は妥当であった 3 7つのCプログラム 6プログラム 残り1プログラム globalの場合のほうが削減効果は大きいが、localの場合のほうがバグ発見能力が高い ICSE'12 勉強会 2012/8/30