ソースコードの同時修正支援における関数クローン検出ツールの有効性調査

Presentation on theme: "ソースコードの同時修正支援における関数クローン検出ツールの有効性調査"— Presentation transcript:

1 ソースコードの同時修正支援における関数クローン検出ツールの有効性調査
井上研究室 沼田 聖也 ソースコードの同時修正支援における関数クローン検出ツールの有効性調査という題目で，井上研究室の沼田が発表いたします．

2 コードクローン ソースコードのコピーアンドペーストによって生じる，同一あるいは類似した部分を持つコード片
ソフトウェアの保守を困難にする大きな要因 クローンペア クローンセット コードクローンとは，ソースコードのコピーアンドペーストによって生じる，同一あるいは類似した部分を持つコード片のことを言います．このコードクローンの存在はソフトウェアの保守を困難にする大きな要因とされています．図のように，互いにコードクローンになるコード片の対のことをクローンペアと呼び，同じコードクローンの集合のことをクローンセットと呼びます． コードクローン

3 コードクローンの分類[1] 分類 定義 タイプ1 空白，コメントの有無，レイアウトなどの違いを除いて完全に一致する． タイプ2
タイプ1の違いに加えて，変数名などのユーザ定義名，関数の型などが異なる． タイプ3 タイプ2の違いに加えて，文の挿入や削除，変更などが行われている． タイプ4 類似した処理を実行するが，構文上の実装が異なる． コードクローンに対して普遍的な定義は存在しません．本研究ではコードクローンを以下の4つのタイプに分類します． タイプ１のコードクローンは，空白，コメントの有無，レイアウト等の違いを除いて完全に一致するものであり，タイプ2のコードクローンは，タイプ1の違いに加えて，変数名などのユーザ定義名，関数の型などが異なるものであり，タイプ3のコードクローンは，タイプ2の違いに加えて，文の挿入や削除，変更などが行われているものであり，タイプ4のコードクローンは，類似した処理を実行するが，構文上の実装が異なるものと定義されます．タイプ1とタイプ2のコードクローンを検出することができるツールは多く存在しますが，それに加えてタイプ3，タイプ4のコードクローンを検出することができるツールはあまり多くありません． [1] Roy et, al., Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach, Science of Computer Programming, 2009

4 関数クローン検出ツールの検出アルゴリズム[2]
STEP1：各関数からワードの抽出 STEP2: ワードに対して重みを計算し特徴ベクトルの計算 STEP3: 各関数の特徴ベクトルをクラスタリング STEP4: 特徴ベクトル間の類似度を計算 STEP1 関数A STEP2 STEP3 STEP4 ワード 個数 xxx 3 yyy 2 ・・・ 類似度 関数対 クローン 0.95 関数A 関数B 　　✔ 0.70 関数C 関数D 関数E 0.90 　　✔　 　・・・ 関数A 関数A 関数B 関数B 関数C 関数D 関数E 関数クローン検出ツールの検出アルゴリズムを簡単に説明します．4つのステップに分かれており，まずSTEP1で，各関数からワードの抽出を行います．ワードとは，変数や関数につけられた識別子名と条件文や繰返し文等の構文に利用される予約語のことを言います．STEP2でワードに対して重みを計算し特徴ベクトルの計算を行い，STEP3で各関数の特徴ベクトルのクラスタリングを行い，STEP4で特徴ベクトル間の類似度を計算します．関数クローン検出ツールはこの検出方法により，タイプ1からタイプ4の全タイプの関数単位のコードクローンを検出することができます． ワード 個数 xxx 3 yyy 2 ・・・ ソースコード 関数B ワードリスト 特徴ベクトル クラスタ クローン検出 [2]山中裕樹, 崔恩瀞, 吉田則裕, 井上克郎. 情報検索技術に基づく高速な関数クローン検出.情報処理学会論文誌, Vol. 55, No. 10, pp. 2245–2255, 2014.

5 研究背景と目的 開発者はコードクローンに対して同時修正の必要があるかを確認しなければならない．
例えば，コード片にバグが見つかった場合，コードクローンにもバグがある可能性が高い． 関数クローン検出ツールはソースコードの同時修正における有効性の調査はされていない． 同時修正するべきコードクローンを検出できるかどうかどうかという観点で有効性を調査した． 研究の背景と目的を説明します．開発者はコードクローンに対して同時修正の必要があるかを確認しなければなりません．例えば，あるコード片にバグが見つかった場合，そのコードクローンにもバグがある可能性が高くなります．しかし，この確認を手作業で行うのは困難であるため，開発者を支援するためにコードクローン検出ツールが利用されます．関数クローン検出ツールは，検出時間等の性能の評価はされていますが，ソースコードの同時修正における有効性の調査はされていません．よって，全タイプのコードクローンを検出できる関数クローン検出ツールに対して，同時修正するべきコードクローンを検出できるかどうかという観点からその有効性を調査しました．

6 研究概要 評価1：Late Propagationに基づく評価 評価2：バグを含むコードクローン検出における評価
この一貫性を破壊する編集を検出できるかを調査した 評価2：バグを含むコードクローン検出における評価 あるコード片にバグが見つかった時にそのバグを含むコードクローンも同時修正するべきである そのようなコードクローンを検出できるかを調査した 本研究では，関数クローン検出ツールのソースコードの同時修正支援における有効性を調査するために，2つの評価を行いました． 1つ目の評価では，late propgationに基づく評価を行いました．Late propagationを引き起こす一貫性を破壊する編集はのちに一貫性を回復する編集が行われることから，本来同時修正するべきものになります．よって，この一貫性を破壊する編集を検出できるかを調査しました． 2つ目の評価では，バグを含むコードクローン検出における評価を行いました．この評価では，あるコード片にバグが見つかった時にそのバグを含むコードクローンも同時修正するべきであるため， そのようなコードクローンを検出できるかを調査しました． 今回の発表では，時間の関係上1つ目の調査に関しては，概略を述べ，主に2つ目の調査の説明を行います．

7 Late Propagation(LP)とは[3]
　クローンペアに対して，一貫性を破壊する編集が行 われた後に一貫性を回復する編集が行われる現象 一貫性を破壊する編集 一貫性を回復する編集 クローンペア クローンペア 編集 (編集) (編集) 編集 Late propagationとはクローンペアに対して，一貫性を破壊する編集が行われた後に一貫性を回復する編集が行われる現象のことを言います．このlate propagationでは，最終的に一貫性を回復する編集がなされるため，本来一貫性を破壊する編集は同時修正されるべきものであると考えられます． フェーズ1 フェーズ2 フェーズ3 最終的に一貫性を回復するため，本来一貫性を破壊する編集は同時修正されるべきである [3] Liliane Barbour, Foutse Khomh, and Ying Zou. An empirical study of faults in late propagation clone genealogies. Journal of Software: Evolution and Process, Vol. 25, No. 11, pp. 1139–1165, 2013.

8 評価1：LPに基づく評価の調査概要 調査対象は2000年1月から2015年12月までのantプロジェクトを利用した．
antプロジェクトに対してどれくらいLPを検出することができるかを調査した． 結果としてタイプ3，4のコードクローンを含む12個のLPを検出することができた． Late propagationに基づく評価の調査概要を説明します．調査対象として2000年1月から2015年12月までのantプロジェクトを利用しました．そして，antプロジェクトに対してどれくらいlate propagationを検出することができるかを調査しました．その結果，タイプ3，4のコードクローンを含む12個のlate propagationを検出することができました．

9 評価2：バグを含むコードクローン検出における評価
Liらが用いた評価セットを利用した[4]． この評価セットには，バグを含むコード片とそのバグと同じバグを含むコードクローンが事例として収録されている． Git，PostgreSQL，Linux Kernelの3つのプロジェクトに含まれる58個のコードクローンを対象とする． 評価の指標とするために，トークン列の等価性に基づくコードクローン検出ツールであるCCFinder[5]でも検出を行った． 2つ目のバグの同時修正における評価では，評価セットとして，Liらが用いた評価セットを利用しました．この評価セットには，バグを含むコード片とそのバグと同じバグを含むコードクローンが例として挙げられており，それらのコミットIDも与えられています．Git，PostgreSQL，Linux kernelの3つのプロジェクトを対象とし，全58個のコードクローンに対して検出を行った．評価の指標とするためにトークン列の等価性に基づくコードクローン検出ツールとして，多くの研究で利用され実績を持つ，CCFinderでも検出を行いました． [4] Jingyue Li and Michael D Ernst. CBCD: Cloned buggy code detector. In Proceedings of the 34th International Conference on Software Engineering, pp. 310–320, 2012. [5]Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: A multilinguistic token-based code clone detection system for large scale source code, IEEE Trans. Softw. Eng., Vol.28, No.1, pp.654–670 (2002).

10 評価2：調査手順 対象の3つのプロジェクトのgitリポジトリから，全ての事例のコミットのスナップショットを取得する．
関数クローン検出ツール，CCFinderそれぞれでコードクローン検出を行う． バグを含むコード片をクエリとして与えて，Liらの見つけたバグ事例を含むコードクローンを検出できるかを調べた． CCFinderの最小一致トークン数はLiらの実験に合わせて10とした． 検出結果に対して評価を行う． 調査の手順としては，まず，対象の3つのシステムのgitリポジトリから，全ての事例のコミットのスナップショットを取得します．続いて，関数クローン検出ツール，CCFinderそれぞれでコードクローン検出を行いました．その際，バグを含むコード片をクエリとして与えて，バグ事例を含むコードクローンを検出できるかを調べました．また，CCFinderの最小一致トークン数はLiらの実験に合わせて10としました．そして，検出結果に対して評価を行いました．

11 評価2：評価指標 再現率 適合率 F値 バグ事例を含むコードクローンの集合からツールが検出できたコードクローンの割合．ツールの網羅性を表す．
ツールが検出したコードクローンの中で，バグ事例を含むコードクローンの割合．ツールの正確性を表す． F値 再現率と適合率の調和平均．これが高いと，総合的に良いツールであると判断できる． 評価指標として，再現率，適合率，F値というものを用いました．再現率とは，バグ事例を含むコードクローンの集合から検出できたコードクローンの割合のことであり，ツールの網羅性を表します． 適合率とは，検出したコードクローンの中でバグ事例を含むコードクローンの割合のことであり，ツールの正確性を表します．F値とは，再現率と適合率の調和平均のことであり，これが高いと，総合的に良いツールであると判断できます．

12 評価2：評価結果 再現率はCCFinderの方がやや高い． 適合率とF値は関数クローン検出ツールの方が高い． 関数クローン検出ツール
バグ事例を含む コードクローン数 58 コードクローン検出数 41 449 バグ事例を含むコードクローン検出数 24 31 再現率 0.41 0.53 適合率 0.59 0.07 F値 0.48 0.12 評価結果は以下の表のようになりました．関数クローン検出ツールはバグを含むコード片に対して41個のコードクローンを検出し，その中でバグ事例を含むコードクローンの数は24個となりました．CCFinderはバグを含むコード片に対して449個のコードクローンを検出し，その中でバグ事例を含むコードクローンの数は31個となりました．その結果，関数クローン検出ツールは，再現率0.41，適合率0.59，F値0.48となり，CCFinderは再現率0.53，適合率0.07，F値0.12となりました．再現率に関してはCCFinderの方がやや高くなり，適合率とF値は関数クローン検出ツールの方が高くなりました． 再現率はCCFinderの方がやや高い． 適合率とF値は関数クローン検出ツールの方が高い．

13 評価２：結果の分析 片方のツールのみでしか検出できない例もある．
関数のごく1部がコードクローンである場合，CCFinderでのみ検出できるものがある． CCFinderはタイプ1とタイプ2を検出できるが，関数クローン検出ツールは全タイプを検出できる． 関数クローン検出ツールは評価結果も良い結果を示し，CCFinderで検出できない例も検出できた． 両ツールの和集合を取った場合の性能も調べた． 検出結果を見ると，どちらかのツールのみが検出できる例も存在することが分かりました．たとえば，関数の中のごく1部がコードクローンである場合，関数クローン検出ツールでは検出できないがCCFinderでのみ検出できるという例がありました．また，CCFinderはタイプ1とタイプ2のコードクローンを検出できるのに対して，関数クローン検出ツールは全タイプのコードクローンを検出できるため，タイプ3とタイプ4のコードクローンに関しては関数クローン検出ツールのみで検出できました．関数クローン検出ツールは，再現率こそCCFinderに比べてやや低めとなりましたが，適合率とF値は高い値となり良い結果を示し，またCCFinderでは検出できないタイプ３，4のコードクローンも検出することができたということから，ソースコードの同時修正支援において有効に働くと考えられます．片方のツールのみでしか検出できない例もあるということから，両ツールの和集合を取った場合の性能も調べてみました．

14 評価2：両ツールを組み合わせた性能 両ツールの和集合を取ると再現率が上がった． しかし，2つのツールを使うことによりコストは上がってしまう．
0.71 適合率 0.11 F値 0.19 両ツールの和集合を取ると再現率が上がった． しかし，2つのツールを使うことによりコストは上がってしまう． コストを気にしないのであれば，両者を併用することでより多くの同時修正すべきコードクローンを見つけることができる． 両ツールを組み合わせると，各ツールを単体で利用した時よりも再現率が上がることが分かりました．しかし，やはり2つのツールを使うためコストは上がってしまいます．よって，コストを気にしないのであれば，両者を併用すればより多くの同時修正すべきコードクローンを見つけることができると考えます．

15 評価2:CCFinderの設定が与える影響について
本研究では，Liらの調査[4]に合わせて最小一致トークン数を10に設定した． 開発者が，バグ事例ごとに適切に設定することができれば，適合率とF値は上昇すると考えられる． しかし，コードクローン分析に詳しい開発者でなければ，適切な設定は難しいと考えられる． 今後の課題として，開発者にCCFinderを使ってもらう評価が必要と考えられる． 本研究では，Liらの調査に合わせて最小一致トークン数を10に設定しました．開発者が，最小一致トークン数をバグ事例毎に適切に設定することができれば，適合率が上昇し，F値も上昇すると考えられます．しかし，コードクローン分析に詳しい開発者でなければ，適切な設定は難しいと考えられます．今後の課題として，開発者に最小一致トークン数をバグ事例ごとに設定してもらいながらCCFinerを使ってもらう評価が必要になると考えられます． [4] Jingyue Li and Michael D Ernst. CBCD: Cloned buggy code detector. In Proceedings of the 34th International Conference on Software Engineering, pp. 310–320, 2012.

16 まとめと今後の課題 まとめ 今後の課題 関数クローン検出ツールのソースコードの同時修正支援における有効性を2つの評価で調査した．
1つ目の評価では，関数クローン検出ツールでLPを検出できるか調査を行い，検出することができた． 2つ目の評価では，バグを含むコードクローンの検出性能の調査を行った． 今後の課題 LPの検出をantプロジェクト以外のプロジェクトにも適用する． 他のツールでもLPを検出して，その性能を比較する． 本研究では，関数クローン検出ツールのソースコードの同時修正支援における有効性を調査するために2つの評価を行いました．1つ目の評価では，関数クローン検出ツールでLPを検出できるか調査を行い，結果としてLPを検出することができました．2つ目の評価では，バグを含むコードクローンの検出性能の調査を行いました．今後の課題としては，LPの検出をantプロジェクト以外のプロジェクトにも適用してみることや，他のツールでもLPを検出して，その性能を比較することが考えられます．