コードクローンの分布情報を用いた特徴抽出手法の提案

Presentation on theme: "コードクローンの分布情報を用いた特徴抽出手法の提案"— Presentation transcript:

1 コードクローンの分布情報を用いた特徴抽出手法の提案
　 大阪大学 大学院情報科学研究科 服部 剛之，肥後芳樹，楠本真二，井上克郎 コードクローンの分布情報を用いた特徴抽出手法の提案というタイトルで， 大阪大学大学院情報科学研究科の服部が発表を行わせていただきます．

2 コードクローン ソースコード中に存在する同一，もしくは類似したコード片を同一システム中に持つコード片 (以降単にクローンと呼ぶ)
コピーアンドペースト等により生成される ソフトウェア保守を困難にする コードの変更が必要な場合 バグ修正，機能追加 保守作業の手間が増大 クローンペア まず，始めにコードクローンとは，ソースコード中に存在する同一， もしくは類似したコード片を同一システム中に持つコード片のことを 指します．以降，単にクローンと呼びます． クローンは主にコピーアンドペーストなどによって生成されます． この図は，2つのファイル中にクローンが存在している例で， 色のついた部分はそれぞれお互いにクローンになっている ことを表しています． このように互いにクローンになっているのをまとめて1つの クローンセットと呼びます． 例えば，クローンが含まれている箇所に バグ修正や機能追加のようなコード変更を行う場合， すべてのクローンにおいてコード変更の検討を行うことが 必要になってきます． このようにクローンが存在すると保守作業の手間が増大します． ゆえに，クローンはソフトウェア保守を困難にする原因となっています． クローンセット

3 CCFinder，Gemini クローンを対象とした保守支援ツール 国内外の個人・組織に配布 検出ツール: CCFinder[1]
研究機関での利用 企業での商用ソフトウェア開発プロセスへの導入 配布先からのフィードバックを得ている 我々の研究室では，クローンを対象とした保守支援ツールとして， 検出ツールのCCFinder，分析環境のGeminiを開発しています． これらのツールは国内外の個人や組織に配布されており， 研究機関で用いられたり，企業での商用ソフトウェア開発プロセスに 導入されています． また，配布先からのフィードバックを得ています． [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): , 2002. [2] Y. Ueda, T. Kamiya, S. Kusumoto and K. Inoue, “Gemini: Maintenance Support Environment Based on Code Clone Analysis”, Proc. of the 8th IEEE International Symposium on Software Metrics, 67-76, 2002.

4 コードクローン検出ツール CCFinder
ソースコードをトークン単位で直接比較することによりコードクローンを検出 名前空間の正規化 ユーザ定義名の置き換え テーブル初期化部分の取り除き モジュールの区切りの認識 数百万行規模でも実用的な時間で解析可能 様々なプログラミング言語に対応

5 CCFinder（処理概要） 1. static void foo() throws RESyntaxException {
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. } 次にCCFinderの処理概要について簡単に説明します． まず，CCFinderは与えられたソースコードを字句解析し，トークン単位に分割します． 次に，変換処理を行います． 変換処理ではテーブル初期化部分の正規化，ユーザ定義の変数名，メソッド名の正規化などが行われます． そして，この変換後のトークン列に対してサフィックスツリーアルゴリズムを用いて一致部分の検出を行います． この例では，この赤の下線と青の下線の部分が一致部分として検出されました． そして，最後に検出した部分を実際のソースコードにマッピングさせます． CCFinderはこのような処理を行うことでソースコード中の類似部分を検出しています．

6 コードクローン分析環境 Gemini CCFinderの解析結果を読み込み，クローン情報を視覚的に表示
クローン散布図(スキャタープロット図) メトリクスグラフ CCFinderの解析結果はテキストファイルなので，このまま分析に用いるのは効率的ではない． Geminiを用いて分析をする． GeminiはCCFinderの解析結果ファイルを読み込みこれらの図を用いてコードクローンを視覚的に表示

7 クローン散布図 ファイルA ファイルB トークン列 a b c d e b c d f b ファイルA
次に　Geminiではクローンの位置情報を基にクローン散布図を作成します． クローン散布図を用いることによりユーザがクローンの分布状況を理解する手助けとなります． この図はクローン散布図の例です． 縦軸，横軸は共にソースファイルの並びを表しています． また，ファイル中のトークンも表示しています． この図で点がプロットされている箇所はトークンが一致した箇所を示しています． この図の対角線上では同じ位置のトークンを比較しているため， すべての点がプロットされることになります． また，点の分布は対角線に対して線対称となっています． クローンはある一定以上の長さを持った線分として出現 ファイルB クローン

8 フィードバックから得られた情報 クローン情報の利用法 問題点 調査すべきクローンをうまく特定したい リファクタリング支援
互いにクローンになっているものを1つにまとめる 設計情報との一貫性確認 設計上説明できるクローンであるか 問題点 検出されたクローンの数が多すぎてどれをみるべきかわからない 調査の必要がないクローン(定型処理など)が含まれている 調査すべきクローンをうまく特定したい フィードバックによって，クローン情報が リファクタリング支援や，設計情報との 一貫性の確認に用いられていることが わかりました． また，ツールから得られたクローン情報を利用する上での問題点として 次の2点がわかりました． 1点目は，検出されたクローンの数が多すぎて どれをみるべきかわからない，というものです． 2点目は，調査の関心がないクローン，例えば 定型処理のようなクローンが含まれているために， どのクローンから見ていけばいいのかわからない， というものです． これらの問題は，クローンの特徴を知ることができれば解決 できると考えられます．

9 目的とアプローチ 目的: クローン分析の効率化 アプローチ: メトリクスを用いてクローンを分類
クローンを特徴付けして分類し，分類に応じた対策方法を提示する アプローチ: メトリクスを用いてクローンを分類 以下のメトリクスを用いる RAD: クローン間の遠さの尺度 NIF: クローンが存在するファイルの数 本研究では，クローン分析を効率化するために， 調査の必要がないクローンをフィルタします． そこで，これらのメトリクスを用いて クローンを分類する手法を提案します． RADというのはクローン間の遠さの尺度， NIFというのはクローンが存在するファイルの数　を表しています． 次にこれらのメトリクスの詳細について説明します．

10 RAD: クローン間の遠さの尺度 RAD: 与えられたクローンセットの各要素を含むファイルから共通の親ディレクトリまでの距離の最大値 2 1
最大値を表しています． 例えば，左の図では， ファイルAとファイルBのどちらのファイルからも 共通の親ディレクトリまでの距離は1となるので， RADの値は1となります． 次に右の図の場合では， このクローンセットにおいて，全体の共通の親ディレクトリは，ここになります． よって，RADの値は，全体の共通の親ディレクトリまでの 距離の最大値である2となります． ファイルC ファイルA ファイルB は，クローンを表す ファイルA ファイルB

11 NIF: クローンが存在するファイルの数 NIF: 与えられたクローンセットの各要素を含むファイルの数 2 3 例：NIF = 2
ファイルC ファイルA 次にNIFというのは与えられたクローンセットの 各要素を含むファイルの数を表します． 例えば，左の図では，2つのファイルにクローンが 含まれているのでNIF = 2となります． 右の図では，3つのファイルにクローンが 含まれているのでNIF = 3となります． ファイルB 2 ファイルA ファイルB 3 は，クローンを表す

12 クローンの分布に着目した分類方法 RAD，NIFは，クローンの分布の特徴を表すメトリクス
値の高低により，クローンを4つに分類する RAD 高 vertical global RAD，NIFは，クローンの分布の特徴を表すメトリクスです． 本研究ではこれらのメトリクスの高低によりクローンを分類します． ここでは，図のように4つに 分類することにしました． 次にそれぞれの分類について説明します． local horizontal 低 低 高 NIF

13 分類: local クローンセットに含まれるクローンがディレクトリ階層上近い少数のファイルに存在する vertical global
RAD 高 vertical global 分類localでは， クローンセットに含まれるクローンがディレクトリ階層上近い 少数のファイルに存在しています． この図では，1つのファイル中に繰り返し存在するクローンを表しています． 例として，局所的な処理が繰り返されている場合が挙げられます． local horizontal 低 は，クローンを表す 低 高 NIF

14 分類: horizontal クローンセットに含まれるクローンがディレクトリ階層上近い多数のファイルに存在する vertical
RAD 高 vertical global 次に分類horizontalでは， クローンセットに含まれるクローンがディレクトリ階層上近い 多数のファイルに存在しています． この図では，1つのディレクトリ下のファイルにクローンが分散していることを表しています． 例として，ディレクトリ下のファイルがあるシステムの各機能の実装を担当している場合が 挙げられます． local horizontal 低 は，クローンを表す 低 高 NIF

15 分類: vertical クローンセットに含まれるクローンがディレクトリ階層上遠い少数のファイルに存在する vertical global
RAD 高 vertical global 次に分類verticalでは， クローンセットに含まれるクローンがディレクトリ階層上遠い 少数のファイルに存在しています． この図では，クローンが含まれているファイルこそ少ないものの， クローン間の位置関係が遠く離れている状態を表しています． local horizontal 低 低 高 NIF は，クローンを表す

16 分類: global クローンセットに含まれるクローンがディレクトリ階層上遠い多数のファイルに存在する vertical global
RAD 高 vertical global 最後に分類globalでは，クローンセットに含まれるクローンが ディレクトリ階層上遠い多数のファイルに存在しています． この図では，クローンがシステム広範囲に渡って存在している状態を表しています． local horizontal 低 低 高 NIF は，クローンを表す

17 適用実験 Ant 総ファイル数: 954個 総クローンセット数: 1643個
目的: RAD，NIFに着目して各分類に含まれるクローンの特徴を調べる Java，C，C++で書かれたオープンソースソフトウェアについて分類を行った CCFinderにより検出された30トークン以上のクローンセットを対象 人の手によって確認 Java(4つ): Ant，Webmail，httpunit，Art of Illusion C(2つ)　　: Small Device C Compiler，Sketch C++ (2つ): CppUnit，SWIG 総ファイル数: 2948個 総クローンセット数: 14874個 Ant 総ファイル数: 954個 総クローンセット数: 1643個 そして，RAD，NIFの分布に着目して各分類含まれるクローンの特徴を調べる ために以下のような実験を行いました． Java，C，C++(プラスプラス)で書かれたオープンソースソフトウェアについて 分類を行いました． 今回はCCFinderにより検出された30トークン以上のクローンセットを 調査対象としました．30トークン以上というのは，これまでの調査の経験に基づく値です． そして，各分類に含まれるクローンの特徴を人の手によって確認しました． 実験に用いたオープンソースソフトウェアは， Javaのプログラムはこれら4つ， Cのプログラムはこれら2つ， C++のプログラムはこれら2つです． これら8つのプログラムの総ファイル数は2948個， 30トークン以上の総クローンセット数は14874個でした． 今回時間の都合上，ここではAntに行った実験について 説明します．Antの規模は，ソースファイル数954個， 30トークン以上クローンセット数は1643個でした．

18 クローンの特徴を表す指標 クローンが含まれる関数の名前を用いて指標を定義する
クローンがどのような関数に存在するかで分類 same: 同じ名前の関数内に存在するクローン similar: 名前の似た関数内に存在するクローン 名前が似ている: 関数名の一部に共通した単語を持つ 例) addConfiguredInputMapper addConfiguredOutputMapper addConfiguredErrorMapper different: 名前が全く異なる関数内に存在するクローン クローンセットが各指標に該当するか調べることで分類の特徴を評価する 複数の指標に該当することを許す クローンが含まれる関数の名前を用いて same，similar，differentの3つの指標を定義しました． これらの指標はクローンがどのような関数に存在するかで 分類しています． sameというのは，同じ名前の関数内に存在するクローンを表します． 次にsimilarというのは，名前の似た関数内に存在するクローンを表しています． ここでいう名前の似た関数というのは，この例のように関数名の一部に 共通した単語を持つ関数とします． 最後にdifferentというのは，異なる関数内に存在するクローンを表しています． クローンセットが各指標に該当するか調べることで 分類したカテゴリを評価します． 1つのクローンセットが複数の指標に該当することを許します． 次にこの指標を用いた評価条件について説明します．

19 評価条件 RAD，NIFの高低の閾値はそれぞれの最大値の半分とした 各分類内でメトリクスRNRについて分割
分類に属するクローンの特徴を詳しく調査 RNRについては次のように分割した RNR低: 0 ≦ RNR ≦ 0.3 RNR中: 0.3 < RNR ≦ 0.7 RNR高: 0.7 < RNR ≦ 1 低 中 高 カテゴリ分けでのRAD，NIFの高低の閾値はそれぞれの 最大値の半分としました． また，RNRについては閾値を0.3，0.7として 低中高の3つに分割しました．

20 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トークン 直前の繰り返し

21 繰り返しの定義に対する説明 X A B A B A B Y  8トークン 正規表現のメタ文字“+”を用いて表す
X (A B)+ Y  4トークン コード片中の繰り返しの割合: 4 / 8 = 0.5

22 RNRに着目した特徴 RNRの低いクローンは単純なロジックのクローンであった(繰り返しの多いクローン) 全体が1つのクローン 直前の繰り返し
public static String getMethodAccess(int access_flags) { StringBuffer sb = new StringBuffer(); if (isPublic(access_flags)) { sb.append("public "); } else if (isPrivate(access_flags)) { sb.append("private "); } else if (isProtected(access_flags)) { sb.append("protected "); } if (isFinal(access_flags)) { sb.append("final "); if (isStatic(access_flags)) { sb.append("static "); if (isSynchronized(access_flags)) { sb.append("synchronized "); 全体が1つのクローン まず，どのカテゴリにも共通した特徴として， RNRの低いクローンは単純なロジックのクローンが 見られました． これがRNRの低いクローンの例です． 色のついた部分がCCFinderで検出された1つクローンを 表しています． このクローンを見ると同じ内容の命令が繰り返されて いることがわかります． ソースコード自体はfinalやstaticなどの属性を設定する命令となっています． 直前の繰り返し

23 Antでのクローンセットの分布 要素数が3以上のクローンセットについて調べた(検出されたクローンセットの約35%) vertical 33個
RAD 高 vertical 33個 global 7個 local 530個 horizontal 11個 低 低 高 NIF 要素数が3以上のクローンセットについて調べた(検出されたクローンセットの約35%) Antでのクローンセットの分布は図のようになります． このデータは，要素数が3以上のクローンセットについて 調べた分布です．これは全体のクローンセットに約35%にあたります． この図を見ると分類localに属するクローンセットが大部分を占めていることがわかります．

24 分類: local の結果 same，similarに該当するクローンが多い
あるデータ構造の要素に対して処理を行う各関数内にクローンが見られた 同じデータ構造を用いている カテゴリlocalでの各指標に該当するクローンの 割合はこのようになります． このグラフを見るとsame，similarに該当するクローンが多い ことがわかります． このカテゴリに属するクローンは，あるデータ構造の要素に対して処理を 行う各メソッド内に見られました． 同じデータ構造を用いているのでコードが似ていると言えます．

25 分類: localに属するクローンの例 同じクローンセットに含まれる関数の例として， getConstantEntry
public int getClassEntry(String className) { int index = -1; for (int i = 0; i < entries.size() && index == -1; ++i) { Object element = entries.elementAt(i); if (element instanceof ClassCPInfo) { ClassCPInfo classinfo = (ClassCPInfo) element; if (classinfo.getClassName().equals(className)) { index = i; } return index; 同じクローンセットに含まれる関数の例として， getConstantEntry getMethodRefEntry などが存在した これがカテゴリlocalに属するクローンの例です． 色のついた部分がクローンを表しています． このクローンが含まれるクローンセットでは， getConstantEntryやgetMethodEntryのような エントリを取得するメソッド内にクローン が見られました． このことから同じデータ構造を用いて いるのでコードが似ていることが言えます． クローンの内容はエントリから特定の要素を取り出すといった処理であり， 同じクローンセットに含まれる関数の例を見るとある要素を取得すると いった関数であるため，クローンとなっていると考えられます．

26 分類: horizontal の結果 sameに該当するクローンが多い 他のプログラムを実行する関数内にクローンが見られた
関数名は同じであるがシグネチャが異なる 次にカテゴリhorizontalでの各指標に該当するクローンの 割合はこのようになります． グラフを見るとsameに該当するクローンが多いことがわかります． このカテゴリに属するクローンは，例えば他のプログラムを実行する メソッドに見られました． 引数ごとに異なるメソッドとして実装されているといえます．

27 分類: horizontalに属するクローンの例
public void execute() throws BuildException { Commandline commandLine = new Commandline(); Project aProj = getProject(); int result = 0; if (getViewPath() == null) { setViewPath(aProj.getBaseDir().getPath()); } commandLine.setExecutable(getClearToolCommand()); commandLine.createArgument().setValue(COMMAND_CHECKIN); checkOptions(commandLine); if (!getFailOnErr()) { getProject().log("Ignoring any errors that occur for: " + getViewPathBasename(),Project.MSG_VERBOSE); result = run(commandLine); if (Execute.isFailure(result) && getFailOnErr()) { String msg = "Failed executing: " + commandLine.toString(); throw new BuildException(msg, getLocation()); 外部プログラムの各機能を呼び出す関数中に クローンが存在した これがカテゴリhorizontalに属するクローンの例です． 色のついた部分がクローンを表しています． このクローンが含まれるクローンセットでは， ある外部プログラムの各機能を呼び出すメソッド中にクローンが 見られました． そのクローンは，ある親クラスの11個の子クラスがそれぞれ同名のメソッドを定義していました．

28 分類: vertical の結果 differentに該当するクローンが多い 類似した構造のパッケージにクローンが見られた
割合はこのようになります． グラフを見るとdifferentに該当するクローンが多いことがわかります． このカテゴリに属するクローンは類似した構造のパッケージに見られました．

29 分類: vertical に属するクローンの例
while (classEnum.hasMoreElements()) { String className = (String) classEnum.nextElement(); log(" Class " + className + " affects:", Project.MSG_DEBUG); Hashtable affectedClasses = (Hashtable) affectedClassMap.get(className); Enumeration affectedClassEnum = affectedClasses.keys(); while (affectedClassEnum.hasMoreElements()) { String affectedClass = (String) 　 affectedClassEnum.nextElement(); ClassFileInfo info = (ClassFileInfo) affectedClasses.get(affectedClass); log(" " + affectedClass + " in " + info.absoluteFile.getPath(), } main testcases ant ant taskdefs taskdefs これがカテゴリverticalに見られたクローンの例です． この例では， 上位の階層で異なるパッケージに分けられているものの， それぞれのパッケージの階層がよく似た構造を 持ったファイル内にクローンが見られました． クローンとなっている箇所は要素を取り出して，それに関連する情報を取得するというものである．

30 分類: global の結果 differentに該当するクローンがほとんどである 定型処理に該当するクローンが見られた
割合はこのようになります． グラフを見るとdifferentに該当するクローンがほとんどであることがわかります． このカテゴリに属するクローンは定型処理ばかりでした．

31 分類: global に属するクローンの例 クローンが存在している関数は ストリームを閉じる処理を2回続けて 行う内容であった
} catch (IOException ioex) { throw new BuildException("Error while concatenating: " + ioex.getMessage(), ioex); } finally { if (reader != null) { try { reader.close(); } catch (IOException ignore) { // ignore } if (os != null) { os.close(); クローンが存在している関数は ストリームを閉じる処理を2回続けて 行う内容であった これがカテゴリglobalに属するクローンの例です． 色のついた部分がクローンを表しています． このクローンが含まれるクローンセットは， 2つのストリームを続けて閉じる処理で構成されていました． Antでは2つのストリームを同時に使うことが多く， Antにおける定型処理であると言えます．

32 考察 他のパッケージからのアドホックなコピーの恐れ 異なるソフトウェアでも，同じ分類に属するクローンに同じ特徴が見られた
ソフトウェアの記述言語を問わない メトリクス値に基づいてクローンの特徴を抽出可能 各分類の特徴を利用することでクローンをフィルタすることができる 例1) globalに属するクローンは定型処理であるので，リファクタリング対象にならない 例2) verticalに属するクローンは設計情報との一貫性を確認することが有益 他のパッケージからのアドホックなコピーの恐れ 例3) RNRが低いクローンは単純なロジックの繰り返しであるので利用しにくい 単純な代入文の連続など リファクタリングの対象にならない 先ほど，Antについて各カテゴリの特徴について説明しましたが， 異なるソフトウェアでも同じ特徴が見られました． このことからソフトウェアの記述言語を問わず， メトリクス値に基づいてクローンの特徴を抽出することが可能であるといえます． そして，各カテゴリの特徴を利用することでクローンをフィルタする ことが可能であると言えます． 1つ目の例として，カテゴリglobalに属するクローンは定型処理であるので， リファクタリングの対象からはずす事ができます． 2つ目の例として，カテゴリverticalに属するクローンは，他のパッケージからの アドホックなコピーの恐れが考えられ，設計情報との一貫性を 確認することが有益ではないかと開発者が判断できます． また，RNRの低いクローンは，繰り返しで構成された単純なロジックのクローン であるので，リファクタリングの対象からはずすことができます．

33 まとめと今後の課題 まとめ 今後の課題 コードクローン分析の効率化を支援するコードクローンの特徴抽出手法の提案と評価 分類の詳細化
ツールとしての実装 実際の開発現場での適用実験と評価 最後にまとめと今後の課題です． コードクローン分析を支援するコードクローンの 特徴抽出手法の提案と評価を行いました． 今後の課題として，分類の詳細化や ツールとしての実装，実際の開発現場で適用することが 挙げられます． 以上で発表を終わります． ありがとうございました．

34