グラフマイニングアルゴリズムを用いた ギャップを含むクローン抽出手法の提案 井上研究室 藤野陽平 2007/2/27
コードクローン ソースコード中に存在する同一，もしくは類似したコード片を同一システム中に持つコード片 (以降単にクローンと呼ぶ) コピー&ペースト等により生成される ソフトウェア保守を困難にする バグ修正などコード変更をする際、全てのクローンに対して変更が必要 保守作業の手間が増大 クローンセット 2007/2/27
コードクローン検出ツールCCFinder クローンを対象とした保守支援ツール 検出ツール: CCFinder[1] 国内外の個人・組織に配布 配布先からのフィードバックを得ている [1] T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder: A multi-linguistic token-based code clone detection system for large scale source code”, IEEE Transactions on Software Engineering, 28(7):654-670, 2002. 2007/2/27
CCFinderの問題点 問題点・・ギャップを含むクローンが抽出できないので、効率的に分析ができない そうなるべきところが別々の短いクローンとして抽出される 目的・・CCFinderの出力を元に、ギャップを含むクローンを抽出する これらを１つのクローンとして抽出したい ギャップ 2007/2/27
提案手法 ギャップを含むクローンを抽出する CCFinderが見つけたコード片をグラフのノードとする グラフマイニングアルゴリズムを用いて、多頻度グラフパターン（ギャップを含むクローン）を抽出する 2007/2/27
AGM(Apriori-based Graph Mining)アルゴリズムの概要 グラフ１ グラフ２ １ １ １ ３ ２ ３ ５ ２ ４ ４ 頂点の数が1の多頻度グラフパターンを見つける [2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004. 2007/2/27
AGM(Apriori-based Graph Mining)アルゴリズムの概要 １ １ １ １ ２ １ ３ ・・・・・ ２ ４ １ ２ ３ ４ １ 見つかった多頻度グラフパターンを組み合わせて、頂点の数が1つ多い多頻度グラフパターンの候補を生成する [2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004. 2007/2/27
AGM(Apriori-based Graph Mining)アルゴリズムの概要 グラフ1 グラフ2 １ １ １ ３ ２ ３ ５ ２ ４ ４ 生成した候補が多頻度グラフパターンかを確認する [2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004. 2007/2/27
AGM(Apriori-based Graph Mining)アルゴリズムの概要 グラフ1 グラフ2 １ １ １ ３ ２ ３ ５ ２ ４ ４ これまでの操作を繰り返し、全ての多頻度グラフパターンを抽出する [2]猪口明博,鷲尾隆,元田浩:多頻度グラフマイニング手法の一般化.人工知能学会論文誌,vol19,No.5,pp. 368-378, 2004. 2007/2/27
ギャップを含むクローン抽出手順 CCFinderが出力するクローンの位置情報を元に、各クローンのコード片をノードとするグラフを作成する 作成したグラフ集合に対して、AGMアルゴリズムを適用して多頻度グラフパターンを抽出し、それをギャップを含むクローンとする ギャップを含むクローンの位置情報を出力する 2007/2/27
CCFinderが出力するクローンの位置情報からグラフを作成する ファイル１ ファイル２ ファイル２ １ １ １ ２ ３ ２ ２ ※図に書かれている数字は、何番目のクローンセットに含まれるコードクローンかを表す． オーバーラップしている 2007/2/27
CCFinderが出力するクローンの位置情報からグラフを作成する ファイル１ ファイル２ ファイル２ １ ファイル1に対するグラフ １ １ １ ２ ３ ２ ２ ※図に書かれている数字は、何番目のクローンセットに 含まれるコードクローンかを表す． 2007/2/27
CCFinderが出力するクローンの位置情報からグラフを作成する ファイル１ ファイル２ ファイル２ １ １ ファイル1に対するグラフ ファイル2に対するグラフ １ １ １ ２ ３ ２ ２ ※ノードに書かれている数字は、何番目のクローンセットに 含まれるコードクローンかを表す． 2007/2/27
CCFinderが出力するクローンの位置情報からグラフを作成する ファイル１ ファイル２ ファイル２ １ １ ファイル2に対するグラフ ファイル1に対するグラフ １ １ １ ２ ２ ３ ２ ２ ※ノードに書かれている数字は、何番目のクローンセットに 含まれるコードクローンかを表す． 2007/2/27
CCFinderが出力するクローンの位置情報からグラフを作成する ファイル１ ファイル１ ファイル２ ファイル２ １ １ ファイル2に対するグラフ ファイル1に対するグラフ １ １ １ １ ２ ２ ２ ２ ３ ２ ２ ※ノードに書かれている数字は、何番目のクローンセットに 含まれるコードクローンかを表す． 2007/2/27
CCFinderが出力するクローンの位置情報からグラフを作成する ファイル１ ファイル１ ファイル２ ファイル２ １ １ ファイル2に対するグラフ ファイル1に対するグラフ １ １ １ １ ２ ２ ３ ２ ２ ２ ３ ２ ２ ※２と３はオーバーラップしているのでエッジを引かない ※ノードに書かれている数字は、何番目のクローンセットに 含まれるコードクローンかを表す． 2007/2/27
多頻度グラフパターンを抽出し、それをギャップを含むクローンとする ファイル1に対するグラフ ファイル2に対するグラフ １ １ ３ ２ ２ ２ ５ ３ ３ 囲んだ部分がギャップを含むクローン 2007/2/27
抽出したギャップを含むクローンの位置情報を出力する ファイル1に対するグラフ ファイル2に対するグラフ ファイル１ ファイル２ １ １ ２ ２ ３ ３ 濃いオレンジの部分がギャップ 2007/2/27
ギャップを含むクローン抽出手順 （まとめ） 入力:ギャップを含まないクローンの位置情報 出力：ギャップを含むクローンの位置情報 ファイル１ ファイル２ ファイル１ ファイル１ ファイル２ ファイル２ １ １ １ １ ２ ２ ３ ２ ２ 2007/2/27
実験 目的: どのようなギャップを含むクローンが抽出されるか調査する 対象:Java，C言語で記述されたオープンソースソフトウェア Java: EJE,jasmin,javadjvu C : f2j CCFinderは30トークン以上のコードクローンを検出 グラフを構築するときに、メトリクスRNR[3]を用いる 検出する必要がないクローンのフィルタリングが可能 例：連続した変数宣言、switch文のcaseエントリなど 閾値として0.5を用いる 挿入・削除・変更といった編集が加えられているクローンとそうでないクローンに分類 [3]肥後芳樹,吉田則裕,楠本真二,井上克郎:産学連携に基づいたコードクローン可視化手法の改良と実装,情報処理学会論文誌,vol48,No.2,pp. 811-822, 2007. 2007/2/27
実験結果 EJE f2j jasmin javadjvu 編集が加えられたクローンセット数 4 7 内訳 挿入・削除 2 変更 3 1 編集が加えられていないクローンセット数 26 10 9 編集が加えられたクローンセット数の割合 80% 21% 41% 31% ソフトウェアによって編集が加えられたクローンセット数の割合の違いが大きい 編集が加えられていないクローンセットをフィルタリング出来るようにするなど改良の余地がある 2007/2/27
編集が加えられたクローンの例 クローンセット 文が挿入されている クローンセット CodeAttr init = new CodeAttr(); init.addInsn(new Insn(opc_aload_0)); init.addInsn(new Insn(opc_invokenonvirtual, new MethodCP("java/lang/Object", "<init>", "()V"))); init.addInsn(new Insn(opc_return)); // Actual code to print string CodeAttr doit = new CodeAttr(); // store refs in local variables doit.addInsn(new Insn(opc_getstatic, new FieldCP("java/lang/System", "out", "Ljava/io/PrintStream;"))); doit.addInsn(new Insn(opc_astore_1)); doit.addInsn(new Insn(opc_ldc, new StringCP(“Hello World”))); doit.addInsn(new Insn(opc_astore_2)); // Loop index in var reg 3 doit.addInsn(new Insn(opc_bipush, 5)); CodeAttr code = new CodeAttr(); // No operands code.addInsn(new Insn(opc_return)); // one arg operands code.addInsn(new Insn(opc_astore, 5)); // one arg arguments with wide operand code.addInsn(new Insn(opc_dstore, 256)); code.addInsn(new Insn(opc_istore, 2576)); // Add a label code.addInsn(new Label("First label")); // refer back to it code.addInsn(new Insn(opc_jsr, new Label("First label"))); // add another label code.addInsn(new Label("second_label")); // insn with CP argument code.addInsn(new Insn(opc_ldc_w, new StringCP("sdfsdf"))); 文が挿入されている クローンセット 緑太字：コードが変更された箇所 黒太字：コードが挿入された箇所 2007/2/27
編集が加えられていない クローンの例 2つのクローンがオーバラップしている ギャップを含むクローン ギャップを含むクローン public void reload( ) { Iterator iterator = reloadables.iterator(); while (iterator.hasNext()) { Reloadable reloadable = (Reloadable) iterator.next(); reloadable.reload(); } public void store( ) { Iterator iterator = storers.iterator(); Storer storer = (Storer) iterator.next(); storer.store(); public void addReloadable(Reloadable reloadable) { reloadables.addElement(reloadable); public void removeReloadable(Reloadable reloadable) { reloadables.removeElement(reloadable); 2つのクローンがオーバラップしている ギャップを含むクローン ギャップを含むクローン 2007/2/27
まとめと今後の課題 まとめ 今後の課題 グラフマイニングアルゴリズムを用いたギャップを含むクローン抽出手法を提案し、ツールを実装した オープンソースソフトウェアに対してどのようなギャップを含むクローンが抽出されるか調査した 今後の課題 編集されていないクローンのフィルタリング バグ検出手法としての有益性評価 2007/2/27
2007/2/27
2007/2/27
コピー＆ペーストによる再利用の 流れ 挿入 削除 変更 Exact クローン Parameterized クローン Gappedクローン コピー＆ペーストによる再利用の 流れ if(a = b){ a = a + 1; b = b*3;} コピー＆ペーストによる 再利用 識別子名の変更 if(a = b){ a = a + 1; b = b*3;} if(i = j){ i = i + 1; j = j*3;} 挿入 削除 変更 if(a = b){ b = b – 2; a = a + 1; b = b*3;} if(a = b){ b = b*3;} if(a = b){ a = a ++; b = b*3;} Exact クローン Parameterized クローン 2007/2/27 Gappedクローン
コピー＆ペーストによる再利用の 流れ Exactクローン Parameterizedクローン Gappedクローン コピー＆ペーストによる再利用の 流れ Exactクローン 完全に一致したコード片。ただし空白、改行、コメントなどの違いは考慮しない Parameterizedクローン 変数名、クラス名などのユーザ定義名の違いを除き一致しているコード片 Gappedクローン 構文的に一致しない不一致コード（ギャップ（Gap））を部分的に含むコード片 そしてコードクローンは以下の３つに分けることができます。 2007/2/27
実験１：結果 EJE f2j jasmin javadjvu 57 15 104 66 82 90 149 215 42 63 102 45 ファイル数 57 15 104 66 クローン セット数 82 90 149 215 Gapped クローン セット数 42 63 102 45 実行時間（s） 3.995 16.73 94.165 1518.60 2007/2/27
実験１：考察 クローンセット数が少なくても、ファイル数が多ければ実行時間がかかっている AGMアルゴリズムでは各ファイルごとにグラフを作成するため 1つのファイルにクローンが集中していると、実行時間が格段にかかってしまう グラフのサイズが大きくなると、頻度計算などで時間がかかってしまうため 2007/2/27
実験２ 抽出されたGappedクローンが有益かどうかを判断するために、抽出されたものに挿入・削除・変更といった編集が加えられているかどうかを人手で判定 メトリクス値RNRでフィルタリングして実験 値が小さいほど、繰り返し要素を多く含むクローン 連続した変数宣言などのクローンをフィルタリングすることで、より効率的に分析作業が可能 閾値として0.5を用いる 2007/2/27
RNR: クローン内の重複した処理の 少なさの度合い ∑ Tokensrepeated(C) RNR = 1 - C ∈ S ∑ S: クローンセット C: クローンセットの要素 Tokensall(C) C ∈ S Tokensall(C) : クローンC中の総トークン数 Tokensrepeated(C) : クローンC中の繰り返し部分のトークン数 8トークン RNRというのはこのような式で表されます． これは，クローンセットの各要素であるクローン中に 繰り返しでない部分が存在する割合の平均値をとっています． RNRが小さいほど，クローン中に繰り返しが多く存在する ことになります． 次にTokens allとTokens repeatedについて説明します． 例えば，このようなトークン列の場合， 全体で8トークンなので，Tokens all = 8となります． このトークン列の繰り返し部分に着目すると 4トークン分繰り返しが存在するので， Tokens repeated = 4となります Tokensall = 8 X A B A B A B Y Tokensrepeated = 4 4トークン 直前の繰り返し 2007/2/27
クローン位置情報のフォーマット フォーマット グループID.ファイルID 開始行,開始カラム,開始トークン 終了行,終了カラム,終了トークン 繰り返し処理でないトークン数 0 . 1 73 , 3 , 128 82 , 59 , 172 12 #begin{set}（１番目のクローンセット） 0.1 73,3,128 82,59,172 12 0.1 84,3,180 92,24,222 24 0.2 90,12,178 99,4,210 23 #end{set} #begin{set}（２番目のクローンセット） 0.2 101,3,215 122,14,252 24 0.3 71,3,114 87,29,167 20 #begin{set}（３番目のクローンセット） 0.1 89,5,194 101,26,252 45 0.2 112,7,243 142,29,289 22 ・・・・・・ 2007/2/27
オーダー AGMアルゴリズム グラフの平均ノード数が増えると指数関数的に増加 グラフ構築 O(n^2) 2007/2/27
CP-Miner[1] コピー＆ペーストによって生成されたコードの検出を目的として開発されたツール Clospan[2]と呼ばれるマイニングアルゴリズムを用いる コピー＆ペーストの後、数行の挿入や削除といった修正が加えられたコードも検出可能 検出対象言語はC,C++ [1] Zhen Li, Shan Lu, Suvda Myagmar, Yuanyuan Zhou , “CP-Miner: Finding Copy-Paste and Related Bugs in Large-Scale Software Code” , IEEE TSE, Vol.32, No.3 MARCH 2006 . [2] X. Yan, J. Han, and R. Afshar, “CloSpan: Mining Closed Sequential Patterns in Laegr Datasets”, Proc.SIAM Int’l Conf.Data Mining, May 2003. 2007/2/27