クローン検出ツールを用いた ソースコード分析ツールの試作 植田 泰士*，神谷年洋**，楠本真二*，井上克郎* 　 * 大阪大学 大学院基礎工学研究科 情報数理系専攻 ** 科学技術振興事業団 若手個人研究推進事業 2019/2/23 ソフトウェアサイエンス研究会

研究の背景(1/2) ソースコード中に類似したコード片があるとき、 それらをコードクローンという クローンペア クローンクラス 2019/2/23 ソフトウェアサイエンス研究会

研究の背景(2/2) コードクローンはソフトウェア保守を困難にする 我々の研究室ではコードクローン検出ツールCCFinderを開発している コードクローンにフォールトがあった場合、 すべてのコードクローンについて修正を 行わなければならない 我々の研究室ではコードクローン検出ツールCCFinderを開発している 検出結果はクローンペアの位置情報のみであり その結果を直感的に理解することは困難 2019/2/23 ソフトウェアサイエンス研究会

目的 CCFinderの検出結果を用いてソースコードを分析するGUIシステムの試作を行う プログラム演習に適用実験を行い システムの有効性を確認する 2019/2/23 ソフトウェアサイエンス研究会

CCFinderの特徴 ソースコードをトークン単位で直接比較することによりクローンを検出 数百万行規模のシステムにも実用時間で解析可能 ユーザー定義名の置き換え 実用的に意味のあるクローンのみを検出 名前空間の正規化 テーブル初期化部分を取り除く モジュールの区切りを認識する 2019/2/23 ソフトウェアサイエンス研究会

CCFinderの処理概要 ソースコード CCfinder 字句解析 トークン列 変換処理 変換後トークン列 検出処理 クローン情報 出力整形処理 クローンペア位置情報 2019/2/23 ソフトウェアサイエンス研究会

CCFinderの処理概要 1. static void foo() throws RESyntaxException { ソースコード 字句解析 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) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } トークン列 変換処理 変換後トークン列 検出処理 クローン情報 出力整形処理 クローンペア位置情報 2019/2/23 ソフトウェアサイエンス研究会

CCFinderの処理概要 ソースコード 字句解析 トークン列 変換処理 変換後トークン列 検出処理 クローン情報 出力整形処理 クローンペア位置情報 2019/2/23 ソフトウェアサイエンス研究会

CCFinderの処理概要 ソースコード 字句解析 トークン列 変換処理 変換後トークン列 検出処理 クローン情報 出力整形処理 クローンペア位置情報 2019/2/23 ソフトウェアサイエンス研究会

CCFinderの処理概要 1. static void foo() throws RESyntaxException { ソースコード 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) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } 字句解析 トークン列 変換処理 変換後トークン列 検出処理 クローン情報 出力整形処理 クローンペア位置情報 2019/2/23 ソフトウェアサイエンス研究会

CCFinderの出力 テキストベースのクローンペアの位置情報とソースコードだけから分析を行うのは困難 解析ファイル番号 #version: ccfinder 3.1 #langspec: JAVA #option: -b 30,1 #option: -k + #option: -r abcdfikmnprsv #option: -c wfg #begin{file description} 0 52 C:\Gemini.java 1 94 C:\GeneralManager.java : #end{file description} #begin{clone} 0 53,9 63,13 10 542,9 553,13 35 1 53,9 63,13 10 624,9 633,13 35 2 124,9 152,31 2 154,9 216,51 42 　　　　　　: #end{clone} テキストベースのクローンペアの位置情報とソースコードだけから分析を行うのは困難 解析ファイル番号 0番ファイルの53～63行目と 10番ファイルの542～553行目 がコードクローンとして検出 2019/2/23 ソフトウェアサイエンス研究会

分析ツールの構成 ユーザ ソースコード コードクローン検出部 クローンペア 管理部 クローンクラス 管理部 ソースコード管理部 クローン散布図 ソースコード コードクローン検出部 クローンペア 管理部 メトリクスグラフ クローンクラス 管理部 ソースコードビュー ユーザ ソースコード管理部 2019/2/23 ソフトウェアサイエンス研究会

分析ツールの機能 クローンペアの位置情報を散布図で表現 クローンクラスに関するソフトウェアメトリクスの算出とグラフ表示 類似率に基づくソート機能 指定クローンペア集合のソースコードを比較する クローンを持たないファイルを散布図から取り除く ズーム機能 クローンクラスに関するソフトウェアメトリクスの算出とグラフ表示 指定クローンクラスのソースコードを比較する フィルタリング機能 2019/2/23 ソフトウェアサイエンス研究会

クローン散布図表示機能(1/3) 原点は左上角 水平軸,垂直軸には共に同じ順で同じ要素を並べる 各座標で一致している部分に点をプロット コードクローンとなっている部分は直線として現れる 対角線は自己比較なので 一本の直線が引かれる 分布状態は対角線に線対称 実際のGUI上では行単位で描画するので対角線に平行でない直線も現れる 10 9 8 7 6 5 4 3 2 1 1, 2, 3, ・・・ : 行番号 A, B, C, ・・・ : トークン A B C X Y A B C ● X Y 2019/2/23 ソフトウェアサイエンス研究会

クローン散布図表示機能(2/3) 座標軸上に単純にファイル を並べる（辞書順等） f1 f2 f3 f4 f5 f6 ● クローンペアの分布が 散布図上で分散し どこに注目すべきなのか 判断が難しい 分布状態ができる限り 密集する順でファイルを 並べる必要がある 2019/2/23 ソフトウェアサイエンス研究会

クローン散布図表示機能(3/3) ファイル配置順のソート機能 あるファイルfの位置が確定すればその隣には,位置が未確定な残りのファイル集合から,fに対し最も類似率の高いファイルを並べる ソート基準はファイル間類似率 あるファイルが対象ファイルによっ てコードクローンでどれだけカバー されているか 先頭のファイルの決定，もしくは最も高い類似率でも0である場合には，残りの解析対象ファイル全体に関してコードクローンで占められるカバー率を用いる f1 f6 f3 f5 f2 f4 ● f1 f2 f3 f4 f5 f6 ● 2019/2/23 ソフトウェアサイエンス研究会

クローン散布図の表示例 2019/2/23 ソフトウェアサイエンス研究会

分析ツールの機能 クローンペアの位置情報を散布図で表現 クローンクラスに関するソフトウェアメトリクスの算出とグラフ表示 類似率に基づくソート機能 指定クローンペア集合のソースコードを比較する クローンを持たないファイルを散布図から取り除く ズーム機能 クローンクラスに関するソフトウェアメトリクスの算出とグラフ表示 指定クローンクラスのソースコードを比較する フィルタリング機能 2019/2/23 ソフトウェアサイエンス研究会

クローンクラスに関するメトリクス(1/2) LEN(C):クローンクラスC内の1コード片のトークン数 POP(C):クローンクラスC内の要素数 DFL(C):クローンクラスCを1サブルーチンに まとめた場合のコード減少量の予測値 　 =（再構築対象コードサイズ）-（再構築後コードサイズ） サブルーチン サブルーチンコールに置き換え DFL値 2019/2/23 ソフトウェアサイエンス研究会

RAD(a) = 2 RAD(b) = 3 RAD(c) = 0 RAD(d) = 1 クローンクラスに関するメトリクス(2/2) RAD(C):ファイルシステム内にクローンクラスC内の 要素がどれだけ分散しているか ディレクトリ ファイル コード片 b a c RAD(a) = 2 RAD(b) = 3 RAD(c) = 0 RAD(d) = 1 d d c b a b 2019/2/23 ソフトウェアサイエンス研究会

クローンクラス管理部の表示例 パラレルコーディネーショングラフ(多次元平行座標) 各メトリクス値の警戒範囲を指定することによりクローンクラスの選択を行う 2019/2/23 ソフトウェアサイエンス研究会

適用実験概要 大学のプログラム演習*において作成された プログラムのソースコードに適用 Pascal風言語ソースコードをCASLへ変換するコンパイラを作成 Ｃ言語で開発 課題１：構文チェッカ（Parser） 課題２：意味チェッカ（Checker） 課題３：コンパイラ（SPC） 課題1→2，2→3では積極的に再利用して拡張することが望まれる 計76人分(約38万行)のソースコードを利用 *受講対象は大阪大学基礎工学部情報科学科3年生 2019/2/23 ソフトウェアサイエンス研究会

適用結果-散布図(1/2) 類似プログラムの検出 A 1区切り：1個人 最小一致トークン数:30 各個人内で課題順に配置 ソートにより要分析領域は 大幅に縮小 容易に類似性を判断可能 Parser Checker SPC A A A B AB A B A B 2019/2/23 ソフトウェアサイエンス研究会

適用結果-散布図(2/2) 3課題を通した再利用性 (原点から順にParser,Checker,SPC) 課題1-2間:平均7.5%の再利用 課題2-3間:平均30.3%の再利用 課題1-2間での再利用が最も低い例 課題1-2間での再利用が最も高い例 2019/2/23 ソフトウェアサイエンス研究会

(原点から順にParser, Checker, SPC) 適用結果-メトリクスグラフ(1/2) DFL値が高いクローンクラスを持つ人物 拡張時にモジュール整理をほとんど行っていない者を特定 ほぼ同じ処理 の繰り返し ソースコード 全体へ分散 さらに分散 (原点から順にParser, Checker, SPC) 2019/2/23 ソフトウェアサイエンス研究会

適用結果-メトリクスグラフ(2/2) RAD,POP値が共に高いクローンクラス 多くの人に頻繁に使われたコードパターン (例) 構文解析部の「変数宣言の並び」と 「仮パラメータの並び」に関する処理のコードクローン 与えられた仕様の構文定義が全く同じであった 処理的意味が異なるので一概に1ルーチンに 再構築すべきであるとは言えない例 「変数宣言の並び」 =変数名の並び “:” 型 {変数名の並び “:” 型} 「仮パラメータの並び」=変数名の並び “:” 型 {変数名の並び “:” 型} 2019/2/23 ソフトウェアサイエンス研究会

まとめ ソースコード分析ツールを試作した 演習に適用する中で有効性を確認 クローン分析における散布図ソート機能の有効性 メトリクスグラフから特徴あるコード片集合を容易に抽出 2019/2/23 ソフトウェアサイエンス研究会

今後の課題 メトリクス値の散布図への反映 含んでいる構文によりクローンペア，クロー ンクラスを分類表示 コードクローンとバグとの相関 2019/2/23 ソフトウェアサイエンス研究会

参考：Suffix-treeによるマッチングアルゴリズム 以下の条件を満たす木 (1)木の葉は部分文字列の開始位置 (2)根から葉までラベルをたどると部分文字列になる (3)ひとつの節点から出る辺のラベルはすべて異なる文字で始まる →共通のパス＝クローン 2019/2/23 ソフトウェアサイエンス研究会

参考 : モジュール整理 拡張時にモジュール整理を的確に行った者と, ほとんど行っていない者 モジュール整理が的確に行えた例 ほぼ同じ処理 の繰り返し ほぼ同じ処理 の繰り返し ソースコード 全体へ分散 1サブルーチン に再構築 さらに分散 モジュール整理が的確に行えた例 モジュール整理が行えていない例 2019/2/23 ソフトウェアサイエンス研究会