オブジェクト指向プログラミング言語に対応した コードクローン検出技法の提案と実験 神谷年洋†　楠本真二† 　井上克郎†‡ †大阪大学大学院基礎工学研究科 ‡奈良先端科学技術大学院大学情報科学研究科

研究の背景 ソフトウェア保守 ソフトウェア保守 開発済みのソフトウェアを何らかの理由によって，変更・修正する作業． 修正のための保守 研究の背景　ソフトウェア保守　 ソフトウェア保守 開発済みのソフトウェアを何らかの理由によって，変更・修正する作業． 修正のための保守 フィールドバグの修正 改訂のための保守 環境変化に対する機能追加・変更（バージョンアップ） 予防のための保守 将来トラブルにつながりそうな箇所に対する対応

コードクローン ソースコード中に類似したコード片があるとき、それらをコードクローンと呼ぶ

クローンが引き起こす問題 クローンはソフトウェア保守を困難にする クローンにフォールトが存在する場合、すべてのクローンについて修正を行わなければならない 機能追加も同様 設計品質の劣化 [1] 大規模なソースコードからクローンを効率よく検出する方法が必要 [1]G. V. Subramaniam, “Object Model Resurrection - An Object Oriented Maintenance Activity”, Proc. 22nd IEEE Int'l Conf. Softw. Eng.(ICSE), pp. 324-333, Jun. 2000.

既存のクローン検出手法 Bakerの手法[2] 行単位でソースコードを比較してクローンを検出する →基本的に入力ソースファイルの記述言語を問わない Baxterらの手法[3] C言語のソースファイルを入力，構文解析して，解析木(の部分木)を比較する [2] B. S. Baker: “On finding Duplication and Near-Duplication in Large Software System,” Proc. Second IEEE Working Conf. Reverse Eng., pp. 86-95, Tronto, Canada (Jul., 1995). [3] I. D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier: “Clone Detection Using Abstract Syntax Trees,” Proc. of ICSM ’98, pp. 368-377, Bethesda, Maryland (Nov., 1998).

既存の手法の問題点 オブジェクト指向プログラミング言語への対応 オブジェクト指向プログラミング言語では，クラスのスコープルール，名前空間，汎用型などにより，複雑な名前が用いられる クローンを選択する手法 テーブルの初期化など，検出しても意味がないクローンがある

提案するクローン検出手法 ソースコードを字句解析してトークンの列に直してからクローン検出を行う 文法知識に基づいたコード変形 クラススコープや名前空間による複雑な名前の正規化を行う 初期化テーブルを取り除く モジュールの区切りを認識する 言語依存部分を取り替えることで，さまざまなプログラミング言語に対応

クローン検出手順 (1)ソースコードを入力し，トークンの列にする (2)変形ルールにより，トークン列を変形する (3)パラメータ置換を行う (4)マッチングアルゴリズムによりクローンを検出する (5)クローンの位置(ファイル，行)を出力する

例題コード 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. }

ステップ(1)：ソースコードを入力し，トークンの列にする

ステップ(2)：変形ルールにより，トークン列を変形する

ステップ(3)：パラメータ置換を行う

ステップ(4)： マッチングアルゴリズムにより，クローンを検出

ステップ(4)： マッチングアルゴリズムにより，クローンを検出

ステップ(5)：クローンの位置を出力する 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. }

変形ルールを用いない場合 4-6行目と 13-15行目， 8-10行目と 17-19行目 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. } 9. System.out.println("sum = " + sum); 10. } 11. static void goo(String [] a) throws RESyntaxException { 12. RE exp = new RE("[0-9,]+"); 13. int sum = 0; 14. for (int i = 0; i < a.length; ++i) { 15. if (exp.match(a[i])) 16. sum += parseNumber(exp.getParen(0)); 17. } 18. System.out.println("sum = " + sum); 19. } 変形ルールを用いなかった場合には，行3と行12，行7と行16が異なった行であると判定されるため，検出されるクローンはいずれも3行以下のクローンになります．

Java向けの変形ルール RJ1：パッケージ名除去 ( PackageName ‘.’ )+ ClassName → ClassName RJ2:Callee挿入 NDotOrNew NClassName ‘(‘ → NDotOrNew CalleeIdentifier ‘.’ NClassName ‘(‘ RJ3:テーブル初期化除去 '=' '{' InitalizationList, '}' → '=' '{' UniqueIdentifier '}‘ ']' '{' InitalizationList, '}' → ']' '{' UniqueIdentifier '}’ RJ4:モジュールの分離 トップレベルの定義や宣言の終わりにUniqueIdentifier を挿入する RJ5:可視性キーワードの除去 protected, public，synchronizedなどのキーワードを取り除く RJ6:コンパウンド・ブロックの処理 if (…), else, while (…) の直後が単文なら{}を補う

クローン検出ツール CCFinder 提案したコードクローン検出手法を実装した 言語依存部分と非依存部分を分離することにより、複数のプログラミング言語に対応 言語非依存部分(C++，7000行) マッチングアルゴリズム，分割，出力のフォーマット，… 言語依存部分(C++, 5000行) 言語に対応した変形ルール(Java，C/C++，COBOL，etc) 動作環境 Windows95/98/NT/2000 UNIX(一部)

最適化 Suffix-treeによるO(n)のマッチングアルゴリズム 入力ソースファイルの大きさをｎとして 「文の最初のトークンだけがクローンの開始位置となることができる」制約によりメモリ使用量を削減 大規模なソースファイルには分割して処理を行う etc

適用例#1 JDKのライブラリ JDK（Java Development Kit） 1.2.2（サンプルとデモプログラムを除く） 入力ファイルは164８個，約50万行 ツールの実行には，Pentium III 650MHzおよび1GBのRAMを持つPCで約3分を要した

JDKのクローン散布図 両軸はソースファイルを辞書順に並べたもの 20行以上のクローンを図示 多くのクローンが密集している（A) 最長のクローン（B） B A

クローンが密集している部分（A） src/javax/swing/plaf/multi/*.javaの29のファイル いくつかはクラス名を除いてまったく同じクラスの定義を含んでいた コード生成ツールによって生成された 31| */ 32| public class MultiButtonUI extends ButtonUI { 33|   160| public static ComponentUI createUI(JComponent a) { 161| ComponentUI mui = new MultiButtonUI(); 162| return MultiLookAndFeel.createUIs(mui, 163| ((MultiButtonUI) mui).uis, 164| a); 165| }

最長のクローン（B） 最長のクローン（349行） src/java/util/Arrays.javaの18の“sort”メソッド シグネチャ（引数の型と数）が異なる アルゴリズムは同一

変形ルールの評価 変形／置換なしでは発見されるクローンは半減する 次に，変形ルールの効果を定量的に評価するため， 変形ルールを用いた場合と，用いない場合で，検出されるクローンを比較しました． 下のグラフは，JDKのライブラリから検出したクローンの長さのヒストグラムです． 水色の棒は変形ルールを適用した場合， 赤色の棒は変形ルールを適用しない場合です． 適用しない場合には，検出されるクローンが半減することが分かります． また，変形ルールを適用した場合には80前後の長さであると判定されるクローンが 適用しない場合にはより短くなってしまうことも分かります．

適用例#2 FreeBSD, Linux, NetBSDの比較 3つのOSの比較 FreeBSD 4.0 (C 220万行) Linux 2.4.0 (C 240万行) NetBSD 1.5 （C 260万行) FreeBSDとNetBSDは同じソースコードから，Linuxは異なるソースコード 実行には108分を要した

FreeBSD, Linux, NetBSDのクローン散布図

FreeBSDとLinuxのクローン ドライバ部分に多くのクローン「ファイル」が存在する 共通のソースから分岐したソースファイル 名前が付け替えられたソースファイル あるソースファイルを複数のファイルに分割している →

まとめ 主な結果 オブジェクト指向プログラミング言語向けのコードクローン検出手法を提案した 提案する手法を幾つかのコードに適用し，コードクローンの検出を確認した 今後の課題 構文によるクローン選別 クローン除去

システム構成 4種類の変形部 Java C++ COBOL プレーンテキスト ソースファイル 字句解析部 変形部 検出部 整形部 クローン トークン列 変形部 変形されたトークン列 変形されたトークン列から変形前のトークン列へのマッピング 検出部 トークン列上でのクローン 整形部 クローン

マッチングの計算量 単純な方法(前述した、行列を作る方法；O(n2))では，多くのメモリが必要となる． 例： 100万行のソースコード、1行平均3トークンと仮定すると 行列の大きさは３ｘ106行x3x106列＝9x1012セル(9兆、9T)

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

クローン検出のその他の応用 DNA配列 GENEバンク→類推→ソースコードバンク？ 自然言語のテキストからクローン検出 …とにかくストリングで表現できるものであれば何でも

コードクローンの除去、予防 クローン除去 クローンをまとめるマクロを生成するツールを用いる[1, 2] クローン予防 モジュールと機能の対照表を作ってレビューする[6]

クローンによるソースコード評価 クローンをまとめることにより削減できるソースコードの割合[1] 機能が重複して実装されている割合、回数[6] クローンの分布 クローンが多く含まれるモジュール？ クローンクラス(同値類)の広がり フォールトとクローンの統計的な関係？

pb x pa A B p x y x+y

大学の演習(1) Pascal風言語で書かれたコードをCASLに変換するコンパイラ Ｃ言語で開発 教科書,指導書を参考にして作成 課題１：構文チェッカ, 課題２：意味チェッカ, 課題3：コンパイラ，の順に作成 課題2と課題3では直前の課題で作成したプログラムを拡張 27人分のソースコード（P1～P27）を利用 次に、実験の概要について説明します。 データはある年度の情報科学演習Dにおいて作成されたプログラムを収集 しました。 この演習では、Pascal風言語で書かれたコードをCASLに変換するコンパイラをC言語で開発します。 教科書、指導書を参考にして作成していき、課題１では構文チェッカを，課題2では意味チェッカを課題3ではコンパイラの順に作成していきます。 課題２では課題1の課題3では課題2で作成されたプログラムを拡張していきます。 27人のソースコードをP１」からP27として入力データとします。 そしてDupSに適用し一致するコード片を検出した後、結果を分析します。

大学の演習(2) P1, P2, P3, P4, P5 P1 P2 P3 P4 P5

大学の演習(3) 一致割合の集計 プログラム内一致 ＝（プログラム内で一致する箇所 に含まれる総行数） ÷（プログラムの総行数） プログラム内一致　 ＝（プログラム内で一致する箇所 　　　に含まれる総行数） 　÷（プログラムの総行数） プログラム間一致　 ＝（プログラム間で一致する箇所 　　　に含まれる総行数） 　÷（プログラムの総行数） 拡張時に変更されない割合 ＝（課題2のプログラムにおいて、 　　　課題3のプログラムと一致 　　　する箇所に含まれる総行数） 　　÷（課題2プログラムの総行数） 　DupSの出力結果についてまとめます。 表の見方ですが、まず＜縦に＞27個のプログラムが並びます。そして次がプログラム内一致の割合、次にプログラム間一致の割合、そして課題2で作成された意味チェッカーが課題3への拡張時に利用される割合となります。 プログラム内一致、プログラム間、拡張時に利用される割合とは、こちらで定義してありますが、P14を例に直感的に説明していきますと、P１４において内部で重複する割合が１５％となり、他のプログラムと一致する割合が１１％でなり、課題2で作成したプログラムが、課題3で60%利用されていると見ていきます。 大まかな目安としてだしてある平均とくらべると、平均よりP１４の方が課題2の利用率が高いことが分かります。 一致割合の集計

大学の演習(4) 拡張時における利用割合による分析 関数単位の利用のされ方による分類 拡張時の利用度が高いP17（71%）と低いP5（39%）について調査 P17では課題2で作成したプログラムを関数単位でうまく利用している　　　　　 →　課題2における設計がしっかりしていたと評価できる P5では何らかの理由で大幅な作り変えが行われた　　　　　　　　　　　　　　　　　 →　原因を調査し対処方法を指導に盛り込む 課題2から課題3に拡張する時際の、利用度が高いP17と利用度の低いP5 について調べた結果です。 P17とP５について、その課題2のプログラムの関数について、そのまま利用された関数、修正されて利用された関数、全く再利用されていない関数にわけて集計し円グラフにしました。 P17では６４％の関数がそのまま課題3で使用されました。 これより、P17では課題2で作成したプログラムを関数単位でうまく利用していることが言え、課題2における設計がしっかりしていたと評価できます。 またP22では、６９％の関数が利用されず、何らかの理由で作り変えが行われたと思われ、原因を調査し対処方法を指導に盛り込む事が考えられます。