デバッグ支援のための グラフベース推薦システム

Presentation on theme: "デバッグ支援のための グラフベース推薦システム"— Presentation transcript:

1 デバッグ支援のための グラフベース推薦システム
九州工業大学　塩塚大 九州大学　鵜林尚靖

2 概要 DCG また、プロジェクトの初期段階でデータが十分に無い場合を想定し、既存のリポジトリを活用した方法を提案します。 推薦 生成 関心事
見たことない 例外に直面！ 例）同じ例外に関連した修正 例）APIの誤りやすい例 public class Property { public String readFile (String pathname) throws IOException { File file = new File(pathname); String val = null; FileReader fileReader = new FileReader(file) ; return val; val = br.readLine(); BufferedReader br = new BufferedReader(fileReader); } } public class Property { public String readFile (String pathname) throws IOException { String val = null; FileReader fileReader = new FileReader(file) ; File file = new File(pathname); BufferedReader br = new BufferedReader(fileReader); return val; val = br.readLine(); } } public class Property { public String readFile (String pathname) throws IOException { File file = new File(pathname); String val = null; FileReader fileReader = new FileReader(file) ; return val; val = br.readLine(); BufferedReader br = new BufferedReader(fileReader); } } プロジェクトＸＸＸの リポジトリ プロジェクトＸＸＸの リポジトリ APIの 使い方が間違ってる？！ プロジェクトＸＸＸの リポジトリ 推薦 生成 DCG 関心事 既存のリポジトリを活用！ 他プロジェクトを活用！ Debug Concern Graph 実行 生成 研究の概要を説明します。 デバッグをする際にはいろいろな問題に直面します。 例えば「見たことのない例外に直面して、修正方法が分からなかったり」あるいは「APIの正しい使い方が分からない」などです。 ここではそういった、頻繁に直面するような問題を関心事と呼んでいます。 本研究では、デバッグの際の知識・ノウハウを再利用することで、こういったよく起こる問題に応じた情報推薦をおこないます。 推薦を実現するために、テスト結果、プログラム要素、修正パターンを関連付けたデバッグ関心事グラフ（DCG）を提案します。 また、プロジェクトの初期段階でデータが十分に無い場合を想定し、既存のリポジトリを活用した方法を提案します。 ＴＤＤ（テスト駆動開発） デバッグのノウハウの収集 　・テスト結果の取得 　・関連したプログラム要素の取得 　・修正パターンの取得

3 発表の流れ １．問題意識 ２．DCG ３．ツールdcNavi ４．実験 ５．関連研究 ６．今後の課題 発表の流れはこのようになっています。
そして関連研究を紹介し、最後に今後の課題を述べます。

4 １．問題意識 例題シナリオ 例外 FileNotFoundException 発生！ A君：プログラミング初心者
readFileメソッド：ファイルから1行読み込みその値を返す 発生した問題：ファイルが存在しない場合のテストで例外FileNotFoundExceptionが発生 public class Property { public String readFile (String pathname) throws IOException { String val = null; File file = new File(pathname); FileReader fr = new FileReader(file) ; BufferedReader br = new BufferedReader(fr); val = br.readLine(); // 1行読み込む return val; } } public class PropertyTest extends TestCase { public void testReadFile () throws IOException { Property property = new Property(); assertEquals(“true”, property.readFile("property.txt")); } public void testReadFileFileNotExist () throws IOException { // property2.txt は存在しないファイル assertEquals(null, property.readFile(“property2.txt”)); デバッグの際に具体的にどういう問題に直面するのか説明します。 例題シナリオとして、プログラミング初心者のＡ君が、readFileメソッド、ファイルから１行読み込み読み込んだ値を返すプログラムを作成しているとします。 簡単にプログラムについて説明します。 このメソッドは引数で与えられたファイルのパスをもとに、File、FileReader、そしてBufferedReaderのオブジェクト を順に生成します。最後にBufferedReaderクラスのreadLineメソッドの実行で１行を読み込み、その値を返します。 このメソッドに対して、ファイルが存在する場合のテストは成功しました。 しかし、ファイルが存在しない場合のテストでは例外FileNotFoundExceptionが発生し、テストに失敗してしまいます。 例外 FileNotFoundException 発生！ テスト対象プログラム テストプログラム

5 デバッグの際にA君が困ったこと バグ情報の利用方法：
例外から察するにファイルが存在しない場合の処理が要求されているが、どこをどのように修正すべきか？ ライブラリ利用方法： ライブラリの使い方が間違っているのではないか？ テスト作成方法： 他にテストすべき項目はないのか？ 修正箇所： ソースコードのどこを特に注意して見直すべきか？ デバッグの際にＡ君が直面した問題を述べます。 さきほどの例ではFileNotFoundExceptionが発生しました。今までに見たことが無いような例外に直面した際に、 具体的な修正方法が分からない、という問題に直面することがあります。 次に、先ほどの例ではFile、FileReader、BufferedReaderといったライブラリを使いました。 使ったことが無いようなAPIやライブラリを使った際に、ほんとうにこの使い方で合っているのか、 間違った使い方をしているのではないか、と疑問に思うことがあります。 他の問題として、他にテストすべき項目は無いか分からない、あるいはソースコードのどこを見直すべきか分からない、 という問題に直面することがあります。

6 考えられる解決策 ⇒ デバッグ履歴の表現としてデバッグ関心事グラフ（ＤＣＧ）を提案 [解決策]
同様の例外に直面したときのソースコードを見つけ出し、あるライブラリ利用における誤りやすい例と、そのときの修正方法を提示するのが有効 [課題] 発生した例外/テスト結果の蓄積 ライブラリの利用に際し、どのような修正が頻繁に行われるのかの蓄積 ⇒　デバッグ履歴の表現としてデバッグ関心事グラフ（ＤＣＧ）を提案 考えられる解決策を述べます。 このような問題に対して、同じ例外に直面したときのソースコードを提示し、ライブラリ利用における誤りやすい例と、そのときの修正方法を提示するのが有効であると考えます。 これは、過去のデバッグで同じ例外に関連したソースコードなら、同じファイル操作のライブラリを使っている可能性があり、 つまり同じ問題に直面した可能性があり、その際の修正方法を参考にできるのではいかと考えたからです。 これを実現するためには、デバッグの際にどういった例外やテスト結果が発生したか、 そして、あるライブラリに関連して、どのような修正が頻繁に行われたか、という情報の蓄積が必要となります。 本研究では、これらを含めたデバッグ履歴の表現として、デバッグ関心事グラフ（ＤＣＧ)を提案します。

7 ２．DCG バグ修正パターン（全２７種） テスト成功 ⇒ デバッグ終了 テスト失敗 ⇒ デバッグ開始
下の図が先ほどのreadFileメソッドのテスト失敗から成功までに作られるDCG 説明の都合上、修正後テストに成功したとしている readFile のデバッグ ：クラス ：テスト結果 ：メソッド ：修正パターン diff-1 diff-2 バグ修正パターン（全２７種） MC-DAP: メソッド呼出しのパラメータの変更 SQ-AROB: メソッド呼出しの追加 MC-DM:同一オブジェクトに対する呼び出すメソッドの変更 BufferedReader File Property PropertyTest Property File PropertyTest FileReader 修正パターン*： メソッド呼出の追加 exist readFile testReadFileFileNotExist testReadFile readLine DCGについて説明します。 下の図が、先ほどのreadFileメソッドのテスト失敗から成功までに作られるDCGです。 ★ここでは説明の都合上、メソッド呼出しの追加という修正をした後、テストを再実行し成功したとしています。 DCGでは、テスト失敗をデバッグの開始ととらえ、その時点で関連していたクラス、メソッド、フィールドなどのプログラム要素を収集し、そして発生したテスト結果を保存します。 そして、なんらかの修正をした後、テストを再実行し成功したときを、デバッグの終了と判断します。 テスト失敗時点とテスト成功時点のファイルの編集の差分から、どういった修正をおこなったか、つまり修正パターンをもとめます。 修正パターンは、Toward an understanding of bug fix patternsという論文で提案されたものを使っています。 全部で２７種類あり、代表的なものに、メソッド呼出しのパラメータの変更、メソッド呼出しの追加、呼び出すメソッドの変更などがあります。 とくにこの３パターンが、プログラマが間違えやすいと知られているので、ＤＣＧでもこの３パターンの誤りを支援の対象とします。 後ほど説明しますが、情報推薦の際にはこの修正パターンを軸におこないます。 DCGを活用することで、ある例外が発生した際にどのような修正をしたか、 あるAPIを利用する際に、どういった誤りをおかしやすいか、といったことの取得が容易となります。 readFile テスト成功 assertEquals testReadFileFileNotExist テスト成功 ⇒ デバッグ終了 テスト失敗 例外：FileNotFound *Pan, K., et al.: Toward an understanding of bug fix patterns. Empirical Software Engineering, pp , 2009. テスト成功 テスト失敗 ⇒ デバッグ開始 readFileメソッドのテスト失敗から成功までに作られるDCG

8 ３．ツールdcNavi テスト結果：JUnitを利用 修正パターン：diff + ASTParser
統合開発環境Eclipseのプラグインとして作成 機能１．デバッグ活動を監視しDCGを自動生成 機能２．関連情報を推薦 機能３．既存のSVNなどのバージョン管理システムからDCGを生成 テスト結果：JUnitを利用 修正パターン：diff + ASTParser SQ-AROB: メソッド呼び出しの追加/削除 関連したメソッド、フィールド、クラス：Mylyn*を利用 Eclipse上でのファイル閲覧、編集、カーソル位置などを監視し作業（タスク）に関連した要素を記録． EclipseのプラグインとしてdcNaviというツールを作成しました。 本ツールは、１．デバッグ活動を監視しＤＣＧを自動生成、２．関連情報を推薦、３．既存のSVNなどのバージョン管理システムからのDCGを生成、の３機能を持ちます。 自動生成では、JUnitプラグインからテスト結果を取得し、修正パターンはUnix の diffとEclipseのASTParserから求めます。 修正パターンの求め方は、詳細は割愛しますが先ほど参照した論文で提案された方法をそのまま使っています。 関連したメソッド、フィールド、クラスはEclipseプラグインのMylynから求めます。 Mylynでは、Eclipse上での開発者のファイル参照、編集、カーソルの位置などを監視し、現在の作業に関連が強い要素を記録していきます。 以降では、機能２、および機能３について説明します。 *Kersten, M. and Murphy, G. C.: Mylar: a degree-of-interest model for IDEs. In AOSD 2005, pp , 2005.

9 推薦機能の利用例 テスト対象プログラム（再掲） 一般的なデバッグの流れ 支援範囲 テスト実行．例外FileNotFound発生
public class Property { public String readFile (String pathname) throws IOException { String val = null; File file = new File(pathname); FileReader fr = new FileReader(file) ; BufferedReader br = new BufferedReader(fr); val = br.readLine(); // 1行読み込む return val; } } テスト実行．例外FileNotFound発生 トレース実行などで例外箇所を特定 ⇒FileReaderを特定 FileReader()のドキュメントを読む 「FileNotFoundException - if the file does not exist, is a directory rather than a regular file, or for some other reason cannot be opened for reading.」 原因として引数のfileに問題があるのではと推測（原因推測） 具体的な修正方法を考え修正． テスト再実行し成功すれば終了． 失敗した場合4, 5を繰り返す． 先ほど例であげたプログラムに対し、どのような流れで推薦機能を利用するのか説明します。 まずステップ１は、テストを実行し例外FileNotFoundExceptionが発生した時点を表しています。 ステップ２では、トレース実行などで例外箇所を特定します。 ここではFileReaderを特定できたとします。 ステップ３では、例外の理由を知るためにFileReaderのドキュメントを参照したとします。 ドキュメントを読むと、「ファイルが存在しないかあるいはディレクトリか、それ以外の理由で開いて読めない」と書かれています。 ステップ４では、原因として引数のfileに問題があるのではないか、と推測します。 最後にステップ５では、具体的な修正方法を考え修正をおこないます。そしてテストを再実行し成功すれば終了です。 本ツールでは、ステップ４の「バグの原因推測」および５の「修正」を支援します。 先ほどのツール上で、例外を選択して右クリックすると、選択した例外に関連した修正が検索できます。 支援範囲

10 推薦結果を得るまでの過程 入力 推薦 （出力） readFileのデバッグ Q1. アルゴリズム calls 共通要素 関連性有り！
１）指定した例外から辿れる修正パターン見つける。 ２）複数ある場合は、グラフの要素間の類似度が高いものを優先 ３）他のテストにより作られたものを優先 ４）修正パターンを含むソースコードを順に推薦 ・・・ ・・・ ・・・ ・・・ 入力 calls ・・・ 共通要素 関連性有り！ テスト失敗 例外：FileNotFound readLine calls H1：readFileのデバッグ H2：JUnitTestRunMonitorのデバッグ プログラム要素間の類似度(H1, H2) = 　　共通要素数/ ((H1の総数 + H2の総数) / 2) 例）|H1| = 30, |H2| = 40, |H1∧H2| = 20 　　20 / (( )/2) = 0.57 例）|H1| = 30, |H2| = 40, |H1∧H2| = 30 　　30 / (( )/2) = 0.85 推薦結果を得るまでの過程を説明します。 推薦のアルゴリズムは簡単です。 まず、指定した例外から辿れる修正パターンを見つけます。 複数見つかった場合は、グラフの要素間の類似度が高いものを優先します。 要素間の類似度は、共通要素を多く含むほど高くなるとします。 例えば、どちらのグラフでもBufferedReaderのreadLineメソッドを含んでいる場合など、類似度が高くなります。 また、他のテストにより作られたものを優先します。最後に、見つかった修正パターンを含んでいるソースコードを順に推薦します。 修正パターン： メソッド呼出の追加 ・・・ 推薦 （出力） ・・・ ・・・ ・・・ JUnitTestRunMonitorのデバッグ

11 推薦結果の例 修正前 修正後 JUnitTestRunMonitorコンストラクタが推薦された if文追加パターン？
－ readFileメソッドと似たファイル操作をしている 　 － メソッド呼出し（SQ-AROB)追加が行われた 　 － 修正方法として、メソッド呼出しを追加すればいいと推測できる！　 if文追加パターン？ 修正箇所:メソッド呼出し追加（SQ-AROB) 推薦結果の例を紹介します。 推薦されたのはJUnitTestRunMonitorのコンストラクタです。readFileメソッドと似たファイル操作をしています。 修正後では、メソッド呼出しが追記されていることから、 具体的にこういった修正をおこなえばいいと推測できます。 ところで、今回は支援対象からは外したのですが、修正パターンにはif文に関するものもあります。 if文の追加や、条件の変更などの修正は、最も多いと知られています。 我々の経験からもそうなのですが、あえて今回はそれを支援対象から外しています。 というのも、if文に関する修正は頻繁に行われ過ぎるし、しかも付属する情報が少ないので、意味のある推薦がおこなえないと判断したからです。 実際にif文を除いても、今回のようにメソッドを捕捉し、推薦できることがあるので、とりあえずよしとしています。 今後、論理エラーなどにも対応したいと考えているので、この点は改善していくつもりです。 修正前 修正後

12 リポジトリからのDCG生成方法 プロジェクトAのSVN プロジェクトA のDCG 対象リポジトリ：SVN
※ 例外やテスト結果の取得は現状では未対応 public class Property { public String readFile (String pathname) throws IOException { File file = new File(pathname); String val = null; FileReader fileReader = new FileReader(file) ; BufferedReader br = new BufferedReader(fileReader); } } val = br.readLine(); return val; public class Property { public String readFile (String pathname) throws IOException { File file = new File(pathname); String val = null; FileReader fileReader = new FileReader(file) ; return val; val = br.readLine(); BufferedReader br = new BufferedReader(fileReader); } } public class Property { public String readFile (String pathname) throws IOException { File file = new File(pathname); String val = null; FileReader fileReader = new FileReader(file) ; BufferedReader br = new BufferedReader(fileReader); } } val = br.readLine(); return val; [取出し]バグ修正リビジョンRに関連したソースコード コミットログのキーワードで特定： 　 ”bug”, “fix”, “patch” 　⇒　テスト成功に対応 リビジョンT のデバッグ diff-1 リビジョンS のデバッグ diff-2 diff-1 リビジョンR のデバッグ diff-2 diff-1 diff-2 プロジェクトAのSVN diff-1 diff-2 関連したプログラム要素　＋　修正パターン diff-1 diff-2 オープンソースのリポジトリからの、DCG生成方法を説明します。 対象リポジトリはSVNです。 生成するDCGでは、関連したプログラム要素と修正パターンの２情報を持ち、現状では例外やテスト結果の情報は含んでいません。 今後対応していく予定です。 普通、SVNなどではテスト結果に関する情報は、保存されていないことが多いです。 代わりにコミットログが存在するので、そのログをもとにテスト失敗、成功を決定します。 テストに成功した時点を、コミットログのキーワード「bug, fix, patch」が含まれるリビジョンと判断し、失敗した時点をその直前のリビジョンと判断します。 この判別方法は、先ほど参照した修正パターンの論文で紹介された方法です。 成功のリビジョンでコミットされたファイルと、その直前のリビジョンのファイルから、差分を計算し、関連したプログラム要素と修正パターンを求めます。 プロジェクトA のDCG 依存する プロジェク 依存する プロジェク public class Property { public String readFile (String pathname) throws IOException { File file = new File(pathname); String val = null; BufferedReader br = new BufferedReader(fileReader); FileReader fileReader = new FileReader(file) ; } } return val; val = br.readLine(); 依存する最新の プロジェク public class Property { public String readFile (String pathname) throws IOException { String val = null; FileReader fileReader = new FileReader(file) ; File file = new File(pathname); BufferedReader br = new BufferedReader(fileReader); return val; val = br.readLine(); } } public class Property { public String readFile (String pathname) throws IOException { File file = new File(pathname); String val = null; BufferedReader br = new BufferedReader(fileReader); FileReader fileReader = new FileReader(file) ; } } return val; val = br.readLine(); [取出し]バグリビジョンRに関連したソースコード 　⇒　テスト失敗に対応

13 ４．実験 準備．リポジトリからのDCG生成 実験．推薦量/推薦時間/推薦の質の確認
Eclipseプラグインで、Mylynに関連した９つのオープンソース 実験．推薦量/推薦時間/推薦の質の確認 上記で生成したDCGを利用 [実施環境] CPU: Atom N280(1.66GHz), RAM:1GB, OS:Windows XP 実験をおこないました。 まず準備としてＤＣＧを生成します。 DCG生成時間の確認を目的とし、EclipseプラグインでMylynに関連した９つのオープンソースで実施しました。 これがオープンソースの一覧です。 下から４番目のEclipse上でMylynとプロジェクト管理ツールのRedmineを連携して使うためのプラグインや、一番下のsubversionをEclipseから使うためのプラグインがあります。 実験では、生成したDCGを利用して推薦量、推薦時間、および推薦の質を確認しました。 以降では順に詳細を述べていきます。

14 DCG生成結果 DCG生成時間の目安： 1000のバグ修正リビジョン ⇒ 80分
1000のバグ修正リビジョン ⇒　80分 DCG生成４０分、リポジトリからのファイルのエクスポート４０分 ＤＣＧ生成結果です。 だいたい１０００のバグ修正リビジョンにつき８０分程度かかりました。 内訳は、DCGの生成に４０分、リポジトリからのファイル取出しに４０分程度かかります。 例えば、mantisというプロジェクトでは、バグ修正リビジョン数が107で、DCG生成時間が７分弱、ファイルの取出しに７分弱 subversionのプロジェクトでは、バグリビジョン数が923で、DCG生成時間が40分程度、ファイルの取出しが45分ぐらいかかっています。

15 実験 例外情報無しで関連したプログラム要素の類似度で検索 推薦量/推薦時間を確認 推薦の質は修正パターンの一致/不一致で評価 推薦元データ
修正対象 推薦 生成したDCGを用いて推薦の実験をおこないました。 推薦方法は、先ほど紹介した例外からの検索です。 ただ、例外情報が今回は含まれていないので、関連したプログラム要素の類似度で検索します。 推薦元として使うデータは、自プロジェクトのDCGの4/5と、他の８プロジェクトのＤＣＧ全部です。 これに対して、自プロジェクトの残り1/5のＤＣＧに推薦をおこないます。 異なるプロジェクトのＤＣＧを混ぜて使うことで、一般的な誤りやドメインに特化した情報が集まるのではないかと考えました。 推薦の質は、修正対象が実際に行った修正方法、つまり修正パターンと、推薦されたものがおこなった修正パターンの一致/不一致で評価しました。 例えば、修正対象がメソッドＡのパラメータの変更という修正を行ったとき、 推薦されたものも同じようにメソッドＡのパラメータの変更という修正を行っていれば、修正方法が一致と評価します。 ＋ 自プロジェクトの 残りのＤＣＧの1/5 自プロジェクトの ＤＣＧの4/5 他の８プロジェクトの ＤＣＧ全部

16 結果 質の善し悪しはわかりませんが、これぐらいは推薦できることが分かりました。 推薦量/推薦時間ともに十分
修正候補一致度は９プロジェクト全体で平均１５．４％ 実験結果です。推薦量は、上限を３０個に設けて行った結果、平均１９個推薦できました。１個あたりの平均推薦時間は5.7ミリ秒でした。 十分な推薦量と、推薦速度であると言えます。 修正候補一致度は９プロジェクト全体で平均１５，４％でした。 たとえば、redmineでは、７０個の修正対象メソッドがあり、そのうち７個程度は、修正パターンの一致した推薦をおこなうことができました。 質の善し悪しはわかりませんが、これぐらいは推薦できることが分かりました。

17 ５．関連研究 [実行履歴＆クエリを使ったデバッグ] Debugging by Asking Questions About Program Output [Ko, A. J. ICSE2006] 問題コードの代わりに、実行履歴などの出力に対して質問を重ねていくことで問題箇所を絞り込んでいく方法を提案 [履歴活用のデバッグ] DebugAdvisor: A Recommender System for Debugging [Ashok, B., et al. FSE2009] バージョン管理，バグデータベース，デバッガログなど統合して類似バグが検索できるクエリ（fat query）を提案 本研究では、自プロジェクトの履歴 ＋ 他プロジェクトの履歴を活用した推薦を実現 ⇒　プロジェクトの初期段階（履歴が無い状態）でも利用可能 関連研究を２つ紹介します。 １つ目は、問題コードの代わりに、実行履歴などの出力に対して質問を重ねていくことで問題箇所を絞り込んでいく方法を提案しています。 ２つ目の、DebugAdvisorでは、バージョン管理，バグデータベース，デバッガログなど統合して類似バグが検索できるクエリ（fat query）を提案しています。 自プロジェクトの履歴を使って推薦を行うのに対し、本研究では他プロジェクトの履歴を活用した推薦をおこないました。

18 ６．今後の課題 推薦の質の向上 テスト実行結果を含めたDCGの生成 if文関連の修正パターンへの対応（論理エラー）
リポジトリからファイルを取出した際に依存するテストも実行 if文関連の修正パターンへの対応（論理エラー） 例）nullチェックパターン：どういった型のオブジェクトに対しチェックが必要なのか．チェック漏れが起こりやすいのか 実行履歴と組み合わせて活用 最後に、今後の課題を述べます。 テスト実行結果を含めた、リポジトリからのＤＣＧ生成方法を検討しています。 また、今回支援対象外であったif文関連の修正パターンについても、対応していきたいと考えています。 以上で発表を終わります。