AGMアルゴリズムを用いた ギャップを含むコードクローン情報の生成

Presentation on theme: "AGMアルゴリズムを用いた ギャップを含むコードクローン情報の生成"— Presentation transcript:

1 AGMアルゴリズムを用いた ギャップを含むコードクローン情報の生成
肥後 芳樹，楠本 真二，井上 克郎 大阪大学 大学院情報科学研究科 {higo, kusumoto, 植田 泰士 宇宙航空研究開発機構 情報・計算工学センター

2 コードクローン コードクローンとは ソフトウェアの保守を困難にする ソースコード中に存在する一致または類似したコード片
コピーアンドペーストなどのさまざまな理由により生成される ソフトウェアの保守を困難にする あるコード片にバグがあると，そのコードクローン全てについて修正の検討を行う必要がある 機能を追加する場合も同様のことがいえる コピーアンドペースト コピーアンドペースト

3 コードクローンの分類 コードクローンは，違いの度合いにより３つに分類される[2]
タイプ１：空白やタブの有無，括弧の位置などのコーディングスタイルを除いて，完全に一致するコードクローン タイプ２：変数名や関数名などのユーザ定義名，または変数の型などの一部の予約語のみが異なるコードクローン タイプ３：コピーアンドペースト後に文の追加や削除，変更が行われたなどの結果により，ギャップ(不一致部分)を含むコードクローン さまざまなコードクローン検出手法が提案されているが，タイプ３のコードクローンを検出できるのは一部の手法のみ [2] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and E. Merlo, "Comparison and Evaluation of Clone Detection Tools", IEEE Transactions on Software Engineering, vol. 33, no. 9, pp , 2007

4

5 本研究の目的と概要 タイプ３のコードクローンを検出できない手法に対する後処理を行うことで，タイプ３のコードクローン情報を生成する手法を提案
興味深いコードクローンやバグを含んでいると思われるコードクローンを検出できると期待 手法の流れ 各ソースファイルのグラフを構築 タイプ１とタイプ２のコードクローンをノード，コードクローン間のギャップをエッジとするグラフを，ソースファイル毎に構築 頻出部分グラフの抽出 AGMアルゴリズムを利用し，1.で構築したグラフ集合に頻出する部分グラフ(タイプ３のコードクローン情報)を抽出 生成したタイプ３のコードクローン情報の出力 入力として与えられたコードクローン情報と同様のフォーマットで出力 タイプ３のコードクローンを検出できない手法に対する後処理を行うことで，タイプ３のコードクローン情報を生成する手法を提案 興味深いコードクローンやバグを含んでいると思われるコードクローンを検出できると期待 手法の流れ 各ソースファイルのグラフを構築 タイプ１とタイプ２のコードクローンをノード，コードクローン間のギャップをエッジとするグラフを，ソースファイル毎に構築 頻出部分グラフの抽出 AGMアルゴリズムを利用し，1.で構築したグラフ集合に頻出する部分グラフ(タイプ３のコードクローン情報)を抽出 生成したタイプ３のコードクローン情報の出力 入力として与えられたコードクローン情報と同様のフォーマットで出力

6 提案手法 -各ソースファイルのグラフを構築-
図中の数字は，クローンセットのIDを表す ファイル１ ファイル２ １ １ ２ ３ ３ ２ オーバーラップしている

7 提案手法 -各ソースファイルのグラフを構築-
図中の数字は，クローンセットのIDを表す ファイル１ ファイル２ ファイル１のグラフ １ １ １ ２ ３ ３ ２ オーバーラップしている

8 提案手法 -各ソースファイルのグラフを構築-
図中の数字は，クローンセットのIDを表す ファイル１ ファイル２ ファイル１のグラフ １ １ １ ２ ３ ３ ２ ２ オーバーラップしている

9 提案手法 -各ソースファイルのグラフを構築-
図中の数字は，クローンセットのIDを表す ファイル１ ファイル２ ファイル１のグラフ １ １ １ ２ ３ ３ ２ ２ ３ オーバーラップしている

10 提案手法 -各ソースファイルのグラフを構築-
図中の数字は，クローンセットのIDを表す ファイル１ ファイル２ ファイル１のグラフ １ ファイル２のグラフ １ ３ １ １ ２ ３ ３ ２ ２ ３ オーバーラップしている

11 AGMアルゴリズム -概要- (Apriori-based Graph Mining)
複数のラベル付きグラフに含まれる多頻度グラフを抽出するアルゴリズム [3] アルゴリズムの流れ 大きさがkの多頻度グラフから，大きさがk+1の多頻度グラフの候補を生成する条件を変えることにより，さまざまなグラフパターンを取り出すことが可能 連結グラフパターン，順序木パターン，グラフのパス 提案手法は，グラフのパスを抽出する条件を用いている [3] 猪口明博, 鷲尾隆, 元田浩, “多頻度グラフマイニング手法の一般化”, 人口知能学会論文誌, vol.19, no.5, pp , 2004年5月

12 実装 提案手法をコードクローン検出ツールCCFinderのポストプロセッサとして実装 生成の設定 右図は解析の流れを表す
GeminiはCCFinder付属のコードクローン分析ツール 生成の設定 タイプ１とタイプ２のコードクローンの最小の大きさ エッジを引く範囲 CCFinder Gemini ポストプロセッサ 従来の分析手順 ギャップを含むコードクローンの分析手順 タイプ１，タイプ２のコードクローンの分析が可能 タイプ１，タイプ２，およびタイプ3のコードクローンの分析が可能

13 適用実験 -概要- 4つのソフトウェアに適用し，検出されたすべてのタイプ３のソースコードを閲覧した 検出の設定
CCFinderは30字句以上のタイプ１・タイプ２のコードクローンを検出 コードクローン間の距離が30字句以内の場合に，それらに対応するノード間にエッジを引いた

14 適用実験 -検出例１(Canna)- 日本語の変換対象領域を縮小(左)・拡大(右)する処理

15 適用実験 -検出例１(Canna)- 縮小処理 縮小処理が可能かをチェックする処理 15

16 適用実験 -検出例２(Ant)- ディレクトリのcopy処理(左)とmove処理(右)のコード

17 適用実験 -検出例２(Ant)- move機能 move元のディレクトリを削除する処理

18 適用実験 -評価の方法(1/2)- 生成されたタイプ3のコードクローンが下記のどの基準に該当するのかを調査した クローンセット単位での調査
複数関数：同一クローンセット内のコードクローンが複数の関数にまたがっているもの 関数と関数の間にギャップが存在している 処理の一部が抜けているコードクローン，とは考えにくい オーバーラップ：同一クローンセット内のコードクローンがオーバーラップして存在しているもの コピーアンドペーストによる修正漏れとは考えにくい

19 クローンペアとクローンセット クローンペア クローンセット
互いに一致または類似しているコード片の対（ペア） クローンセット 互いに一致または類似しているコード片の集合（セット） 共にコードクローンを表す用語であるが，これらを使い分けることにより，よりスムーズに議論を行うことができる C1 C2 C3 C4 C5 クローンペア クローンセット (C1, C2) {C1, C2, C4} (C1, C4) {C3, C5} (C2, C4) (C3, C5)

20 適用実験 -評価の方法(1/2)- 調査の必要がない：ソフトウェア開発・保守を行う視点でコードクローンを扱う場合に特に対象とする必要のないもの 文献[3]で紹介されている8種類を対象とした 有益：以下の条件をすべて満たすもの 関数内にギャップが存在する オーバーラップしていない 調査の必要がないコードクローンに該当しない [3] Yoshiki Higo, Toshihiro Kamiya, Shinji Kusumoto, Katsuro Inoue, “Method and Implementation for Investigating Code Clones in a Software System”, Information and Software Technology, Vol.49, issues 9-10, pp , September, 2007

21 調査の必要がないコードクローン プログラミング言語の性質上どうしてもコードクローンになってしまう

22 適用実験 -評価結果- 有益と判定されたクローンセットは，全体の約25%～35% １つのクローンセットが複数の基準に該当する場合がある
複数の関数にまたがっているコードクローンがオーバーラップしている 「(1)複数関数」と「(2)オーバーラップ」 ２つギャップを含んでいるコードクローン．1つが関数の外側，もう１つが関数の内側 「(1)複数関数」と「(4)有益」

23 適用実験 -「(1)複数関数」について- 処理内容が類似した関数が連続して定義されていた それらの関数の中央のみが異なっている
ある関数の終了部分から，次の関数の開始部分までがタイプ3のコードクローンとして検出された 検出を防ぐには，各関数の位置情報が必要 ポストプロセッサでソースコードを解析 ctagsなどを利用？ 関数A 関数B 関数C タイプ３のクローン

24 適用実験 -「(2)オーバーラップ」について-
各ソフトウェア独自の頻出処理が存在 If-else文の各分岐先など，近くに存在 ２つの対策が考えられる 対策１：タイプ３のコードクローン情報を生成した後，位置を突き合わせることによりオーバーラップのチェックを行う 対策２：グラフ構築の際，同一クローンセットに含まれるコードクローンのノード間にはエッジを引かない 開始コード片と終了コード片が異なるクローンセットに含まれている場合は，タイプ３として出力 どちらも容易に行うことが可能 タイプ３のクローン

25 適用実験 -「(3)調査の必要がない」について-
調査の必要がないコードクローンは，プログラミング言語の性質上どうしても存在してしまう[3] 検出されてしまうのは当然 検出しないためには，ソースコードの構造の情報が必要 ポストプロセッサでソースコードを解析？ [3] Yoshiki Higo, Toshihiro Kamiya, Shinji Kusumoto, Katsuro Inoue, “Method and Implementation for Investigating Code Clones in a Software System”, Information and Software Technology, Vol.49, issues 9-10, pp , September, 2007

26 まとめ タイプ１とタイプ２のコードクローン情報からタイプ３のコードクローン情報の生成手法を提案した
コードクローン検出ツールの出力結果のみを用いるため，検出対象ソースファイルを直接解析する必要がない 用いる検出ツールが対応しているプログラミング言語であれば，どの言語であっても適用することが可能 検出ツールCCFinderのポストプロセッサとして実装し，４つのオープンソースソフトウェアに対して適用 約25%～35%が有益なコードクローン それ以外のコードクローンへの対策についての考察 今後の予定 検出の設定を変えての評価 CCFinder以外のツールも用いる 対策の実装と評価

27

28 AGMアルゴリズム –アルゴリズムの流れ- (Apriori-based Graph Mining)
２行目：大きさ 1 の多頻度グラフの候補が生成する ５-６行目：大きさ k の多頻度グラフの候補の出現回数を計算，閾値以上であれば，大きさ k の多頻度グラフとする ７行目：大きさ k の多頻度グラフを組み合わせて，大きさ k+1 の多頻度グラフの候補を生成する １０行目：全ての多頻度グラフが出力する Gは，グラフの集合 Fkは，大きさkの多頻度グラフの隣接行列の集合 Ckは，大きさkの多頻度グラフの候補隣接行列の集合

29 AGMアルゴリズム –アルゴリズムの流れ- (Apriori-based Graph Mining)
２行目：大きさ 1 の多頻度グラフの候補が生成する ５-６行目：大きさ k の多頻度グラフの候補の出現回数を計算，閾値以上であれば，大きさ k の多頻度グラフとする ７行目：大きさ k の多頻度グラフを組み合わせて，大きさ k+1 の多頻度グラフの候補を生成する １０行目：全ての多頻度グラフが出力する Gは，グラフの集合 Fkは，大きさkの多頻度グラフの隣接行列の集合 Ckは，大きさkの多頻度グラフの候補隣接行列の集合

30 AGMアルゴリズム –アルゴリズムの流れ- (Apriori-based Graph Mining)
２行目：大きさ 1 の多頻度グラフの候補が生成する ５-６行目：大きさ k の多頻度グラフの候補の出現回数を計算，閾値以上であれば，大きさ k の多頻度グラフとする ７行目：大きさ k の多頻度グラフを組み合わせて，大きさ k+1 の多頻度グラフの候補を生成する １０行目：全ての多頻度グラフが出力する Gは，グラフの集合 Fkは，大きさkの多頻度グラフの隣接行列の集合 Ckは，大きさkの多頻度グラフの候補隣接行列の集合

31 AGMアルゴリズム –アルゴリズムの流れ- (Apriori-based Graph Mining)
２行目：大きさ 1 の多頻度グラフの候補が生成する ５-６行目：大きさ k の多頻度グラフの候補の出現回数を計算，閾値以上であれば，大きさ k の多頻度グラフとする ７行目：大きさ k の多頻度グラフを組み合わせて，大きさ k+1 の多頻度グラフの候補を生成する １０行目：全ての多頻度グラフが出力する Gは，グラフの集合 Fkは，大きさkの多頻度グラフの隣接行列の集合 Ckは，大きさkの多頻度グラフの候補隣接行列の集合

32 AGMアルゴリズム –アルゴリズムの流れ- (Apriori-based Graph Mining)
２行目：大きさ 1 の多頻度グラフの候補が生成する ５-６行目：大きさ k の多頻度グラフの候補の出現回数を計算，閾値以上であれば，大きさ k の多頻度グラフとする ７行目：大きさ k の多頻度グラフを組み合わせて，大きさ k+1 の多頻度グラフの候補を生成する １０行目：全ての多頻度グラフが出力する （アルゴリズムの概要へ） Gは，グラフの集合 Fkは，大きさkの多頻度グラフの隣接行列の集合 Ckは，大きさkの多頻度グラフの候補隣接行列の集合

33

34 本研究の位置づけ CP-Minerなどの一部の検出手法はタイプ３のコードクローンを検出することができる
本稿は，タイプ３のコードクローンを検出することができない手法を拡張する 同じ対象からコードクローンを検出する場合でも，用いる検出手法によって検出されるコードクローンは異なる [4] 既存のタイプ３のコードクローンを検出する手法とは，異なるタイプ３のコードクローンを検出できると期待 [4] Elizabeth Burd, John Bailey, " Evaluating Clone Detection Tools for Use during Preventative Maintenance" ,Proc. 2nd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM) 2002, pp Montreal, Canada, Oct. 2002

35 コードクローン検出ツール: CCFinder 検出プロセス
Source files 字句解析 変換処理 トークン列 検出処理 変換後トークン列 クローン情報 出力整形処理 クローンペア位置情報 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) if (pat.match(a[i])) sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { RE exp = new RE("[0-9,]+"); int sum = 0; for (int i = 0; i < a.length; ++i) if (exp.match(a[i])) sum += parseNumber(exp.getParen(0)); System.out.println("sum = " + sum); 17. } 字句解析 変換処理 トークン列 検出処理 変換後トークン列 クローン情報 出力整形処理 字句解析 変換処理 トークン列 検出処理 変換後トークン列 クローン情報 出力整形処理 字句解析 変換処理 トークン列 検出処理 変換後トークン列 クローン情報 出力整形処理 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) if (pat.match(a[i])) sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { RE exp = new RE("[0-9,]+"); int sum = 0; for (int i = 0; i < a.length; ++i) if (exp.match(a[i])) sum += parseNumber(exp.getParen(0)); System.out.println("sum = " + sum); 17. }

36 コードクローンの定義 さまざまなにコードクローン検出手法が提案されている コードクローンの厳密で普遍的な定義は存在しない
行単位での比較による検出手法 字句(トークン)単位での比較による検出手法 抽象構文木(AST)を用いた検出手法 プログラム依存グラフ(PDG)を用いた検出手法 メトリクス値の比較による検出手法 コードクローンの厳密で普遍的な定義は存在しない どの手法も異なったコードクローンの定義をもつ 同じ対象からコードクローンを検出する場合でも，用いる検出手法によって検出されるコードクローンは異なる[1] [1] Elizabeth Burd, John Bailey, " Evaluating Clone Detection Tools for Use during Preventative Maintenance" ,Proc. 2nd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM) 2002, pp Montreal, Canada, Oct. 2002

37 巻き付き(intertwined)コードクローン
「♭♭」で始まる行と「♯♯」で始まる行がコードクローン

38