サーベイ論文
コードクローン検出とその関連技術
肥後 芳樹†

楠本 真二†

井上 克郎†A Survey of Code Clone Detection and Its Related Techniques
Yoshiki HIGO† , Shinji KUSUMOTO† , and Katsuro INOUE†

あらまし 近年，コードクローンを対象とした研究が活発に行われている．コードクローンとは，ソースコー
ド中に存在する互いに一致または類似したコード片を指す．コードクローン情報を適切に利用することによって，ソフトウェア保守を効果的にかつ効率的に行うことが可能である．本論文では，現在注目を集めているコードク
ローンの検出とその関連技術に関して，これまでの研究成果を紹介する．
キーワード

コードクローン，ソフトウェア保守，可視化，リファクタリング

1. ま え が きて，コードクローン検出技術を用いてソフトウェア保

コードクローンとは，ソースコード中に存在する

ドクローンに関する研究を始めようとしている方など

互いに一致または類似したコード片を指す．一般的にが，コードクローンに関する研究成果を学んでいただ

コードクローンの存在は，ソフトウェアの保守を困難ければ幸いである．

守プロセスを改善しようとしている方，これからコーにするといわれている．例えば，あるコード片中にバ

以降，2. では，コードクローンの発生理由とその分グが存在した場合，そのコード片のすべてのコードク類について言及し，3. では，コードクローンの検出技

ローンに対して，同様のバグの存在が疑われる．対象

術とその比較について述べる．4. では，コードクロー

ソフトウェアが大きい場合，チェックすべき箇所が膨ン情報の可視化について研究成果を紹介する．5. で大な数になってしまうこと，及び人間がすべての重複は，コードクローンを一つの関数などにまとめる（以部分を認識しておくことは現実的ではないため，ツー

降，コードクローンの集約と呼ぶ）方法について触れ，

ルを用いた自動的なコードクローン検出が行われる．

6. では，集約に向いていないコードクローンの管理方

近年，ソフトウェアの分析手法としてコードクロー法について述べる．最後に 7. で本論文をまとめる．

ン検出技術が注目を集めている．ソフトウェア工学の著名な会議である ICSE（International Conference

2. コードクローン

on Software Engineering）の 2007 年度大会では，ソ

コードクローンは，ソフトウェアの保守性を悪化さフトウェア保守やテスト，アスペクト指向プログラミ

せる一つの要因であると考えられている．門田らは，ングなどと並んで，コードクローン専門のセッション

COBOL で記述されたソフトウェアに対してコードクが設けられていたことからも，その関心の高さをうか

ローンとソースファイルの改版数の関係を調査していがうことができる [1]．

る [2]．その調査では，全体の 80%以上がコードクロー

現在，コードクローンに関する様々な研究が行われンになっているソースファイルや，200 行以上のコーており，その情報を効率的に収集することは難しい．

ドクローンを含むソースファイルは他のソースファイ

そこで，本論文では，現在までのコードクローンに関

ルに比べ，改版数が多くなる傾向であることが報告さする研究成果を体系的にまとめる．本論文を参考にしれている．
その一方で，コードクローンを用いた開発が望まし†

大阪大学大学院情報科学研究科，豊中市

い場合もあるとの報告もされている．例えば，Kapser

Graduate School of Information Science and Technology,

らは，ハードウェアドライバを作成する場合は，既存

Osaka University, 1–3 Machikaneyama-cho, Toyonaka-shi,
560–8531 Japan

電子情報通信学会論文誌 D Vol. J91–Dのドライバからのコピーアンドペーストが有効である
c （社）電子情報通信学会 2008
No. 6 pp. 1465–1481 

1465

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6と述べている [3]．
コードクローンを把握するための方法としては，•

コードクローン情報の文書化を行うことで変更の一貫性を保つ，•

コードクローンを自動で検出する，用のコード部分に重複した処理が存在する傾向が強い．
［偶

然］

偶然に，開発者が同一のコードを書いてしまう場合もあるが，大きなコードクローンになる可能性は低い．

2. 2 定義の二つがある [4]．しかし，コードクローン情報の文

これまでに，様々なコードクローン検出手法が提案書化には，すべてのコードクローンに対する情報を常されており，それらはどれも異なったコードクローンに最新に保つことに非常に手間がかかるため，現実的の定義をもつ．つまり，コードクローンの厳密で普遍には困難である．そこで，これまでに様々なコードク的な定義は存在しない．

ローン検出手法が提案されている．

Bellon は，コードクローン間の違いの度合に基づき，それらを三つに分類している [8], [9]．以下に各分

2. 1 発 生 理 由
コードクローンがソースコード中に生成される原因
として，下記の項目が挙げられる [5]〜[7]．

類の概要を示す．
（タイプ 1）［既存コードのコピーアンドペーストによる再利用］

空白やタブの有無，括弧の位置などのコーディング

近年のソフトウェア設計手法を利用すれば，構造化スタイルを除いて，完全に一致するコードクローンをや再利用可能な設計が可能である．しかし，一から指す．

コードを書くよりも既存コードを流用して部分的な変（タイプ 2）

更を加える方が信頼性が高いということもあり，実際

変数名や関数名などのユーザ定義名，また変数の型にはコピーアンドペーストによる既存コードの再利用などの一部の予約語のみが異なるコードクローンをが多く存在する．

指す．

［定 型 処 理］（タイプ 3）

定義上簡単で頻繁に用いられる処理はコードクロー

タイプ 2 における変更に加えて，文の挿入や削除，ンになる傾向がある．例えば，給与税の計算や，キュー

変更が行われたコードクローンを指す．

の挿入処理，データ構造アクセス処理などがそうで

3. コードクローン検出技術

ある．
［プログラミング言語における適切な機能の欠如］

本章では，これまでに提案されているコードクロー

抽象データ型や，ローカル変数を用いることができ

ン検出技術を紹介する．既存の検出技術は，コードク

ない場合には，同じようなアルゴリズムをもつ処理を

ローンをどの単位で検出するのかによって，大まかに繰り返し書かなくてはならない場合がある．

以下の五つに分類することができる．
行単位の検出ない場合に，特定のコード片を意図的に繰り返し記述

•
•
•
•

することにより，パフォーマンスの改善を図ることが•メトリックスやフィンガープリントなど，その［パフォーマンス改善］
リアルタイムシステムなど時間制約のあるシステム
において，インライン展開などの機能が提供されていある．
［コード生成ツールの生成コード］
コード生成ツールにおいて，類似した処理を目的と字句単位の検出
抽象構文木を用いた検出プログラム依存グラフを用いた検出

他の技術を用いた検出各分類に属する検出技術がどの単位でコードクロー
ンを検出するのかを図 1 に表す．また，Bellon の分

したコードの生成には，識別子名等の違いはあろうと

類 [8], [9] を用いて，各検出技術がどのようなコードク

も，あらかじめ決められたコードをベースにして自動ローンを検出できるかを表 1 にまとめる．

的に生成されるため，類似したコードが生成される．
［複数のプラットホームに対応したコード］
複数の OS（Linux，FreeBSD，HP-UX や AIX な以降，3. 1〜3. 5 では各分類に属する検出技術を紹介し，3. 6 では検出技術の比較について述べ，3. 7 では検出に影響を与える要因について論ずる．

ど）や CPU（i386 系，amd64 系，alpha や sparc64

3. 1 行単位の検出など）に対応したソフトウェアは，各プラットホーム

ソースコードを行単位で比較することにより重複コー

1466

サーベイ論文／コードクローン検出とその関連技術(a) 行単位の検出(b) 字句単位の検出(c) 抽象構文木を用いた検出(d) プログラム依存グラフを用いた検出(d) メトリックスを用いた検出

図 1 コードクローン検出の前処理
Fig. 1 preprocesses of code clone detection.
表 1 コードクローン検出技術とコードクローンタイプ
Table 1 Code clone detection techniques and code clone types.
検出技術の分類

行単位の検出字句単位の検出

抽象構文木を用いた検出プログラム依存グラフ
を用いた検出メトリックスを用いた検出

検出手法
Johnson の手法 [10]Ducasse らの手法 [11], [12]Baker の手法 [13]〜[15]Wettel ら手法 [16]Prechelt らの手法 [17]〜[19]Kamiya らの手法 [6]Li らの手法 [20]Basit らの手法 [21]Baxter らの手法 [5]Koschke らの手法 [22]Jiang らの手法 [23]Wahler らの手法 [24]Komondoor らの手法 [25]Krinke の手法 [26]Mayrand らの手法 [27]Kontogiannis らの手法 [28], [29]検出可能なコードクローン
タイプ 1 タイプ 2 タイプ 3
































（注 1）








対応言語
不特定多数
不特定多数
不明
不特定多数
C/C++，Java，C#,Scheme
C/C++，Java，COBOL など
C/C++
Java
C/C++，Java，Ada，C#など
C
C,JavaXML で表現されたソースコード
C/C++，Scheme
C
C/C++
C

ドを特定するのが行単位の検出手法である（図 1 (a)）．

を提案している [10]〜[12]．この手法では，各行に含行単位の検出手法では，しきい値以上連続して重複しまれる空白やタブが取り除かれた後，すべての行を比ている行がコードクローンとして検出される．この検較して重複した行を検出している．各行に対して行わ出技術は，他の検出技術に比べ検出速度が高速である

れる処理は，空白とタブの削除のみであるため，不特という特徴をもつが，同じ処理を行っているコードで定多数のプログラミング言語に対して適用することがあってもコーディングスタイルの違う場合はコードク
ローンとして検出できないという弱点をもつ．

Johnson や Ducasse らは，比較的単純な検出手法（注 1）：Ueda らの手法 [30] を併用することによってタイプ 3 のコードクローンも検出することが可能．Kamiya らの手法のみを用いる場合
は，タイプ 1 とタイプ 2 のコードクローンのみを検出できる．

1467

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6可能である．

Baker は Parameterized-Matching を用いた手法を提案している [13]〜[15]．この手法では，比較が行われる前に，各行に含まれるユーザ定義名部分が特殊文字に置き換えられるため，ユーザ定義名が異なっていてもコードクローンとして検出することができる．すべてのユーザ定義名が同一の特殊文字に置き換えられるのではなく，同一変数を使用している部分が，同一特殊文字に置換される．これにより，誤検出を減らすこ(a) 変換前のソースコード（Java）（注 2）とに成功している．行単位での比較には，接尾辞木

検索アルゴリズム [31] が用いられているため，線形時間でコードクローンを検出することができる．

Wettel らは，行単位でコードクローンを検出した
後，近接するコードクローンを一つにまとめる手法を提案している [16]．この処理を行うことにより，小さいコードクローンを大きな一つのコードクローンとしてとらえることができる．つまり，コピーアンドペー
スト後に文の挿入や削除が行われた部分を一つのコー
ドクローンとして検出することができる．

(b) JPlag が変換したトークン列
Fig. 2図 2 JPlag のトークン変換
Tokens transformation on JPlag.

3. 2 字句単位の検出
字句単位のコードクローン検出では，検出の前処理となど広く用いられている複数のプログラミング言語にしてソースコードは字句の列に変換される（図 1 (b)）．

対応している．現在，同氏による後継機 CCFinderX のしきい値以上連続して一致している字句の部分列が開発も進められている [32]．

コードクローンとして検出される．字句単位のコード

Ueda らは，検出ツール CCFinder のフロントエン

クローン検出は，行単位の検出のように検出結果が

ドである Gemini を改良し，CCFinder が検出したタイ

コーディングスタイルに依存することはない．また，

プ 1 及びタイプ 2 のコードクローンからタイプ 3 のソースコードを検出用の中間表現に変換する必要もな

コードクローン情報を生成している [30]．しきい値よ

いため，高速にコードクローンを検出できるという利りも近くに存在するタイプ 1 及びタイプ 2 のコードク点もある．

ローンをつなぎ合わせ，タイプ 3 のコードクローン情Prechelt らは，剽窃の特定を目的としたコードクロー
ン検出ツール JPlag を開発している [17]〜 [19]．JPlag

情報は，Gemini の散布図（注 4）などに反映される．

は，C/C++，C#，Java，Scheme に対応しており，入力されたソースコードは JPlag 独自のトークン列に変換される．図 2 は，JPlag によるソースコード変換の例である（注 3）．メソッドの開始は BEGINMETHOD，変数の宣言は VARDEF などのように，ソースコード

報としている．生成されたタイプ 3 のコードクローン

Li らは，頻出系列マイニング（注 5）アルゴリズム [33]を用いた検出手法を提案し，検出ツール CP-Miner を開発している [20]．この手法では，まず，ソースコー
ドに対して字句解析及び構文解析が行われ，ユーザ定
義名は特殊文字に置換される．その後，文ごとにハッが JPlag 独自のトークン列に変換されているのが分か

シュ値に置き換えられる．つまり，用いている変数名

る．コードクローンは，貪欲法を用いることによってが異なっていても同一構造をもつ文であれば，同一変換後のトークン列から検出される．

ハッシュ値をもつことになる．この操作を行うことにKamiya らは，接尾辞木検索アルゴリズム [31] を用より，文の並びはハッシュ値の列に変換される．このいた検出手法を提案し，検出ツール CCFinder を開発している [6]．検出処理の前に，ユーザ定義名を特殊文字に置き換えるという言語依存の処理を必要とするにもかかわらず，C/C++，Java，COBOL，FORTRAN
1468（注 2）：Suﬃx Tree
（注 3）：図 2 は文献 [18] で用いられている例である．
（注 4）：Gemini の散布図については，4. を参照されたい．
（注 5）：Frequent Sequence Mining

サーベイ論文／コードクローン検出とその関連技術列に対して，頻出系列マイニングを適用することによを提案したのは Baxter らである [5]．抽象構文木を用

り，コードクローンを検出している．頻出系列マイニ

いた検出では，部分木の対が同一構造になっているか

ングでは，頻出系列は必ずしも連続している必要はなを調査するのであるが，すべての部分木の対を調査い．例えば，系列 abdec には，部分系列 abc が一つ含することは実用的ではない．そのため，各部分木からまれているとして検出される．このため，タイプ 3 のハッシュ値を生成し，ハッシュ値が同一の部分木の対

コードクローンも検出することができる．

のみを比較している．部分木の構造を細部まで忠実に

Basit らは，接尾辞配列（注 6）アルゴリズム [34] を用いた検出手法を提案し，検出ツール Clone Miner を開発している [21]．このツールは，CCFinder と同様，検考慮したハッシュ関数ではなく，細部の構造を無視す

出処理の前にユーザ定義名を特殊文字に置き換える処

工夫により，大規模ソフトウェアからでも高速にタイ理を行う．Clone Miner は接尾辞配列アルゴリズムを

プ 1 とタイプ 2 のコードクローンを検出することが可

るハッシュ関数を用いているため，ある程度構造が異なる部分木も同一ハッシュ値をもつことになる．この用いてコードクローンを検出した後，頻出集合マイニ能である．また，Baxter らは，提案手法に基づき，商ング（注 7）アルゴリズム [35] を用いて，同時に出現する用のコードクローン検出ツール CloneDR を開発してコードクローンの集合を特定している．現在の実装でいる [36]．このツールは，非常に多くのプログラミン

は，コードクローンの集合は一つのファイル内に含まグ言語に対応しており，コードクローンの位置情報だ

れなければならないという制限があるが，拡張するこけでなく，それらを一つの関数としてまとめる場合のとにより，例えば，複数のクラスにまたがる類似部分

ひな形も出力する．

を検出することができるであろう．

Koschke らは，抽象構文木を直列表現に変換した後，3. 3 抽象構文木を用いた検出

接尾辞木アルゴリズムを用いてコードクローン検出を

抽象構文木を用いた検出では，検出の前処理として行う手法を提案している [22]．接尾辞木アルゴリズム

ソースコードに対して構文解析を行い，抽象構文木がを使用しているため，高速にコードクローン検出を行構築される（図 1 (c)）．抽象構文木上の同形の部分木

うことが可能である．

がコードクローンとして検出される．抽象構文木を用

Jiang らは，抽象構文木の各部分木を配列表現に変いたコードクローン検出は，字句単位の検出と同様

換し，局所感度ハッシュ（注 8）アルゴリズム [37] を用いに，検出結果がコーディングスタイルに依存することて，類似配列を求めることによりコードクローンを検はない．コードクローンの検出処理を行う前に，抽象出する手法を提案している [23]．局所感度ハッシュア

構文木を構築する必要があるため，行単位や字句単位

ルゴリズムでは，ある程度配列に違いがあっても同じの検出に比べて，検出に必要な時間的及び空間的なコ

ハッシュ値を割り当てることができる，そのため，タストは高くなるが，実用的な検出法として知られていイプ 3 のコードクローンも検出することが可能である．

る．更に，プログラムの構造から構築した抽象構文木
上での一致部分がコードクローンになるため，ある関Wahler らは，XML で表現された抽象構文木から
コードクローンを検出する手法を提案している [24]．

数定義の終わりから次の関数定義の先頭までの類似部

ソースコードを XML に変換する技術は既に多くのプ

分や，文の途中からの類似部分など，プログラムの構

ログラミング言語で開発されており [38]〜[42]，XML造を無視した類似部分は検出されないこともこの手法からコードクローン検出を行うことは，個々のプログの特徴である．このような類似部分がコードクローン

ラミング言語のソースコードをそのまま検出対象にすとして検出されないことは一概に良い悪いとはいえな

るよりは，言語依存の処理を行う部分が少なくて済む

い．例えば，プログラム全体におけるコードクローン

ため，効率的にツールの開発を行うことができるであの割合を算出したい場合は，このようなコードクロー

ろう．Wahler の手法では，文単位で頻出集合マイニン

ンも見つけるべきであるかもしれない．しかし，検出

グアルゴリズムを用いることによって，コードクロー

したコードクローンを一つの関数や手続きにまとめる

ン検出を行っている．

ことを目的としている場合では，プログラムの構造を無視したコードクローンは一つにまとめることは難し
いので，検出する意味がないと思われる．
最初に抽象構文木を用いたコードクローン検出手法（注 6）：Suﬃx Array（注 7）：Frequent Itemsets Mining（注 8）：Locality Sensitive Hashing1469

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6(a) コード片 1

図 4 巻き付きコードクローン
Fig. 4 Intertwined code clone.

アに対して適用することは現実的ではない．

Komondoor らは，ソースコード中の文をプログラ(b) コード片 2

ム依存グラフのノードとする検出手法を提案してい図 3 順序入れ換わりコードクローン
Fig. 3 Reordered code clone.

その種類に応じて分類する．その後，同種の文の対にる [25]．この手法では，まず，ソースコード中の文を対して，フォワードプログラムスライスとバックワー

3. 4 プログラム依存グラフを用いた検出

ドプログラムスライスの両方を用いて，同一のグラフ

プログラム依存グラフを用いた検出では，検出の構造が作成されるかを検査する．しきい値以上の大き前処理としてソースコードに対して意味解析を行い，さの同一構造のグラフが構築された場合は，そのグラソースコードの要素間（文や式など）の依存関係が抽フに含まれる文がコードクローンであるとしている．

出され，要素を頂点，依存関係を有向辺とするグラフ

Krinke は，変数や演算子などの字句をノードとする（プログラム依存グラフ）が構築される（図 1 (d)）．グプログラム依存グラフからコードクローンを検出する

ラフ上の同形の部分グラフがコードクローンとして手法を提案している [26]．字句を単位とした場合，文検出される．プログラム依存グラフを用いた検出のを単位とする場合よりもノードの数が増えるため，す

長所は，順序入れ換わりコードクローン（注 9）や巻き付

べての部分グラフを調査するには非常に高い計算コス

きコードクローン（注 10）など，他の技術では検出するこトを必要とする．そのため，しきい値を用いて部分グとのできないコードクローンを検出できることであラフを構築する範囲を制限している．初期ノードからる．図 3 は，順序入れ換わりコードクローンの例を

しきい値以上離れているノードについては，部分グラ表している（注 11）．この例では，図 3 (a) の  で始まフの調査を行わない．

る行と図 3 (b) の  で始まる行がコードクローンになっている．図 3 (a) の一つ目の代入文に対応するの

3. 5 メトリックスやフィンガープリントなどその他の技術を用いた検出は，図 3 (b) では，二つ目の代入文である．このようプログラムのモジュール（ファイルや，クラス，メにソースコード上で順序が入れ換わっていても意味的

ソッドなど）に対してメトリックスを計測し，その値に同一であるコード片はコードクローンとして検出すの一致または近似の度合を検査することによって，そることが可能である．また，図 4 は，巻き付きコードのモジュール単位でのコードクローンを検出する手法

クローンを表している．この図でも， で始まる行と で始まる行がコードクローンになっている．このよ（図 1 (e)）．メトリックス値が近似していればコード

うに互いに巻き付き合っているコードクローンは，意

クローンとして判定されるため，タイプ 3 のコードク

が，メトリックスを用いたコードクローン検出である

味的な処理を考慮しなければ検出することはできない．
しかし，プログラム依存グラフの構築には高い計算コストを必要とするため，この技術を大規模ソフトウェ
1470（注 9）：reordered code clone（注 10）：intertwined code clone（注 11）：図 3 と図 4 は文献 [25] で用いられている例である．

サーベイ論文／コードクローン検出とその関連技術ローンも検出することが可能である．しかし，サイズことができる．

の小さいモジュールの場合はメトリックス値に差ができいモジュールの場合はその内部の一部分が類似して

Krsul らは，メトリックスを用いてプログラムの作者を特定する手法（注 12）を提案している [47]．用いているメトリックスは，大まかに以下の 3 種類に分類する

いてもコードクローンとして判定されない，という問ことができる．

ないため誤検出の可能性が高くなり，及びサイズの大題点がある．

Mayrand らは関数に対して 21 種類のメトリックスを計測することによってコードクローンを検出する手法を提案している [27]．この手法では，ユーザ定義
名やコーディングスタイル，制御文などに関するメト
リックスを用いて，関数単位で 8 段階の類似度を定義
している．

•

インデントやコメントなど，プログラムのレイアウトに関するメトリックス．

•

識別子名の長さや大文字の使用頻度など，プロ

グラミングスタイルに関するメトリックス．

•関数の長さやマクロの使用頻度など，プログラ

ムの構造に関するメトリックス．
この手法の適用実験は，大学の職員や学生など 29 人

Kontogiannis らは抽象構文木の部分木（ソースコー

が作成した 88 個のプログラムを対象として行われ，ド中の文や式，またはそれらを含むブロック）に対しそのうちの約 7 割について正しく作者を特定することて 5 種類のメトリックスを計測することによってコーができた．

ドクローンを検出する手法を提案している [28], [29]．
計測された各部分木のメトリックスは，ユークリッド
距離を用いて評価される．しきい値よりも短い距離に位置する部分木がコードクローンとして検出される．

3. 6 手法の比較
本節では，これまでに行われている検出手法の比較について，その概要と結果を述べる．

3. 6. 1 Bellon らによる比較

また，プログラムの剽窃を検出することやプログ

これまでに最も大規模な検出手法の比較実験を行ってラムの作者を特定することなどを目的とした，フィン

いるのは，Bellon らであろう．Bellon らは，Baker の

ガープリントやバースマークを用いた手法も多数存在

手法 [15]，Baxter らの手法 [5]，Kamiya らの手法 [6]，Krinke の手法 [26]，Mayrand らの手法 [27]，そしてDucasse らの手法 [11] の六つを比較している [9]．

する．フィンガープリントとは，プログラムに埋め込まれる著作権などに関する情報のことであり，バース
マークとは，プログラムにおける固有の特徴を意味す

この実験では，ツールを用いてコードクローン検出

る．ソフトウェアが改変されてしまっても，これらのを行ったのはそのツールの開発者若しくはそのツール

値自体は変わらないため，プログラムの剽窃を発見すを熟知している人物であり，その検出結果が Bellon

ることができる．これらの技術は，コードクローン検に集められた．Bellon は集まった約 32 万のコード片

出とは独立に研究されてきている．

のペアのうち，2%のソースコードを閲覧し，それがAiken は，プログラムの剽窃を検出するインター
ネットサービスを行っている [43]．その Web ページに本当にコードクローンであるかを判断した．Bellon がは，フィンガープリント技術 [44] を用いているとの記合（注 13）が，コードクローンの正解集合として用いられ述があるが，詳しい検出手法は公表されていない．

た（注 14）．

コードクローンであると判断したコード片のペアの集

Ottenstein は，プログラム中で用いられている識別

コードクローンの検出対象は，C 言語または Java子と演算子の種類及び出現回数をバースマークとして言語で記述された，約 11,000 行〜235,000 行の八つの用いる手法を提案している [45]．非常に単純な手法でオープンソースソフトウェアである．また，対象プロあるが，大学生が作成した小規模のプログラムから，グラムに対して各タイプのコードクローンを埋め込み，学生間のコピーを検出することに成功している．

Wise は，貪欲法を用いたプログラムの剽窃を検出する手法を提案している [46]．この手法は検出の前処理として，対象プログラムを特殊な字句の列に変換す
る．変換を行うことにより，for 文と while 文間の類
似のような，コピーアンドペースト後の簡単な修正により発生してしまったと思われる重複部分を特定する（注 12）：Authorship analysis（注 13）：Bellon は，ツールが検出したコード片そのものをコードクロー
ンとしたわけではない．必要に応じて，その中の一部分のみをコードク
ローンとしたり，前後のコードと合わせてコードクローンとするなどの処理を行った．
（注 14）：Bellon はコードクローン検出ツールの開発者ではないため，
Bellon が作成したコードクローンの正解集合はすべての検出ツールに対して中立である，と文献 [9] は主張している．

1471

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6

各ツールが検出することができるかの調査も行った．
実 験 の 結 果 ，Baker の 手 法 ，Ducasse ら の 手 法 ，Kamiya らの手法は，検出結果が類似しており，また，再現率が高いことが分かった．一方，Baxter らの手法，Mayrand らの手法は適合率が高かった．Krinkeの手法は，タイプ 3 のコードクローン検出以外では，
うまく機能していないことが分かった．
ツールによって検出されたかなり数のコードクロー

表 2 Burd らの比較：各手法により検出されたコードク
ローンの数，適合率，再現率
Table 2 Comparison by Burd et al.: the numbers ofcode clones, precisions, and recalls of eachdetection technique.
検出手法
Kamiya らの手法 [6]Baxter らの手法 [5]Mayrand らの手法 [27]Prechelt らの手法 [18]Aiken の手法 [43]検出数 適合率 再現率 F 値
1,12872
72 72.0
84
100
9 16.5278
63
19 29.2
131
82
12 20.9120
73
10 17.6

ンが，Bellon によって棄却された．例えば，Baxter
らの手法によって検出されたコードクローンの 24%，
表 2 は，その結果を表している．この表から分かる

Krinke の手法によって検出されたコードクローンの77%が，Bellon によって棄却された．

ように，Kamiya らの手法 [6] は他の手法に比べ，多埋め込まれたコードクローンの多くは，ツールにくのコードクローンを検出しており，検出したコード

よって検出されることはなかった．各ツールは 24〜

クローンの約 2/3 は正しくコードクローンであった．

46%の埋め込まれたコードクローンの検出にとどまっ

その一方で，Baxter らの手法 [5] は，他の手法に比べていた．

あまりコードクローンを検出できてはいないが，検出

また，Bellon らは，各ツールの性能面についても言（注 15）

及している．Baker の手法と Kamiya らの手法はされたコードクローンは，すべて正しくコードクロー
ンであるという結果であった．

効率的にコードクローンを検出していたと述べている．

検出されるコードクローンは検出ツールの設定に

例えば，postgresql（約 23,5000 行）から，Baker の手

よっても異なる．例えば，Kamiya らの手法であれば，

法は約 12 秒（メモリ使用量は約 62 MByte），Kamiya

検出するコードクローンの最小の長さや，プログラム

らの手法は約 40 秒（メモリ使用量は約 47 MByte）で中の変数名や関数名の違いを考慮するかどうかを，利検出を完了した．最も短時間でコードクローン検出を用者が設定することができる．つまり，同じ手法を用行っていたのは，Mayrand らの手法である．この手いて検出を行った場合でも，その適合率と再現率は検法は各対象の検出処理をすべて 4 秒未満で完了した．

出の設定によって異なる．Burd らの調査はこの点を一方，Baxter らの手法と Krinke の手法はコードク考慮していない．より正確なツールの比較を行うため

ローン検出に長い時間を必要とした．Baxter らの手法には，様々な設定でコードクローンを検出し分析を行は，snns（約 115,000 行）からのコードクローン検出

う調査が必要である．

に約 3 時間（メモリ使用量は 380 MByte）を要した．

3. 6. 3 Rysselberghe らによる比較
Rysselberghe らは，行単位の検出技術，字句単位のKrinke の手法 [26] は postgresql（約 235,000 行）からのコードクローン検出に失敗し，cook（約 80,000

検出技術及びメトリックスを用いた検出技術を比較し行）からのコードクローン検出に 245 時間（メモリ使ている [49]．ツールではなく，検出手法の比較を行う

用量は 12 MByte），snns（約 115,000）からのコード

ために，既存ツールを用いるのではなく，手法ごとにクローン検出に 63 時間（メモリ使用量は 64 MByte）

新たにツールを作成して，そのツールを用いて実験をを要した．

行っている．行単位の検出ツールは，単に空白とタブ

3. 6. 2 Burd らによる比較
Burd ら は ，Kamiya ら の 手 法 [6]，Baxter ら の
手 法 [5]，Mayrand ら の 手 法 [27]， Prechelt ら の 手
法 [18]，そして Aiken の手法 [43] の五つを比較している [48]．すべての手法により検出された各コードク
ローン（注 16）を，手作業で本当にコードクローンであるか調査を行い（注 17），コードクローンであると判定された集合をコードクローンの正解集合として，各検出手法の再現率，適合率を求めている．
1472

を取り除いて比較をするツール（以降，行単位の単純検出）と，ユーザ定義名を特殊文字に置換して比較するツール（以降，行単位のパラメータ化検出）を実装している．
（注 15）：文献 [9] の実験では，各ツールは異なったハードウェア環境でコードクローン検出を行っていることに注意されたい．
（注 16）：コードクローンの検出対象は，約 16,000 行の Java 言語で記述されたソフトウェアである．
（注 17）：Bellon らの比較（文献 [9]）と同様に，コードクローンである
かどうかの判断は，筆者らの主観により行われた．

サーベイ論文／コードクローン検出とその関連技術

行単位の単純比較は，全くプログラミング言語に依手法の違いによる検出精度の差はあまりなかったが，存しないため，コードクローン検出を行う準備が容易

横断的関心事による検出精度の差ははっきりと出ていであるという利点があると主張している．行単位のパ

た．具体的には，コードの長さが数個の字句のみからラメータ化検出，及び字句単位の検出は，各プログラ構成されている短い横断的関心事は，誤検出が非常にミング言語用に解析器を作成する必要があるが，単純多いため，検出精度が悪かった．

な処理しか行っていないため，それほどコストは高く

3. 7 検出結果に影響を与える要因の調査ないと述べている．その一方，メトリックスを用いた

Baker は，自身が開発したツール Dup を用いて，再検出を適用するためには，メトリックスを計測するた現率の視点からコードクローンの検出結果に影響をめに様々な情報をソースコードから取得しなければな

与える要因について調査を行っている [52]．Baker はらないため，解析器の作成に高いコストを要すると述

コードクローンの正解集合として，3. 6. 1 で述べた

べている．

Bellon が作成したコード片のペアの集合を用いている．

検出結果については，行単位の単純検出によって検調査項目 1：識別子の変更

出されるコードクローンは，行単位のパラメータ化検識別子を特殊文字に置き換えてコードクローン検出

出によって検出されるコードクローンの部分集合になを行うことにより，変数名や関数名が異なっていてもる場合が多い，つまりコードクローンには変数名の違

コードクローンとして検出をすることができるが，そいなどがしばしば存在する，と指摘している．また，の反面誤検出が増えてしまう．Baker の実験では，識行単位のパラメータ化検出と字句単位の検出には，あ別子の 50%以上が異なる場合はコードクローンとしてまり検出されるコードクローンに違いはなく，メト検出しないフィルタリングについて調査を行っている．

リックスを用いた検出は，誤検出が多いと述べている．

調査項目 2：Parameterized-Matching

また，Rysselberghe らは，検出したコードクロー

3. 1 で述べているように，Baker の手法は，同一変

ン を 集 約 す る と い う 視 点 か ら ，Ducasse ら の 手

数を使用している部分が，同一特殊文字に置換され法 [11]， Baker の手法 [14]，Mayrand らの手法 [27]，る．実験では，すべての識別子を同一の特殊文字に置Kontogiannis ら の 手 法 [28] を 比 較 し て い る [50]．

換した場合に再現率がどのように変化するかを調査しMayrand らの手法及び Kontogiannis らの手法は，一ている．

致または類似しているメソッドやメソッド内のブロッ

調査項目 3：ネストの深さ

クをコードクローンとして検出するため，Ducasse ら

コードクローンになっている部分の最終行は，先頭の手法や Baker の手法に比べ，検出されたコードク

行とネストの深さが同じか若しくはより深くなけれ

ローンは集約に適していると述べている．Ducasse らばならない，というのが Bellon らの主張である [9]．

の手法及び Baker の手法は，プログラムの構造は考慮

Baker はこのフィルタリングの有無についても調査をせず，単純に類似した行をコードクローンとして検出行った．

するため，検出されたコードクローンは集約には向い

調査項目 4：繰返し領域ていない場合が多いと述べている．しかし，Mayrand繰返し領域（注 18）のコードクローン（注 19）は，ツール

らの手法及び Kontogiannis らの手法は，メトリックにって検出されたコードクローンと一致しない傾向がスを用いた検出技術であるために，3. 5 の冒頭で述べ強い．なぜなら，繰り返し領域のコードクローンの出た問題点があり，検出されたすべてのコードクローン

力形式は，各ツールで大きく異なるためである．ツーが集約可能というわけではない．

ルの出力方式の違いのために，Bellon が作成した正解

3. 6. 4 Bruntink らによる比較集合と一致しないと思われるコードクローンについて

Bruntink らは，横断 的関心事を 実装した コードを検出する，という視点から，Kamiya らの手法 [6]，Baxter らの手法 [5]，そして Komondoor らの手法 [25]

調査を行った．
調査項目 5：その他の調査
Bellon が作成したコード片のペアの集合を，Dup がを比較している [51]．まず，対象システムを熟知している開発者が，手作業により 5 種類の横断的関心事を特定する．その後，各ツールによるコードクローン検
出結果と手作業による特定結果の比較を行っている．

（注 18）：Repetitive Regions：連続した代入文や，連続した if-else 文などを指す．
（注 19）：このコードクローンは，Bellon がツールの検出結果をもとに作成したコード片のペアの集合を指す．

1473

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6
表 3 Baker による再現率に関する調査の結果
Table 3 Results of Baker’s investigation on recall
factors.

害になるのは，調査の必要がないコードクローンの存

調査内容
C 言語
Java 言語
識別子の変更 48% → 56%
52% → 57%
P-Match56% → 63% 57%で変化なし
ネストの深さ 63% → 69%
57% → 65%
繰り返し領域 69% → 不明 65%で変化なし
その他
不明 → 70% 65%で変化なし

ンとは，ソフトウェア開発・保守を行う視点でコード在である [53]〜[56]．調査の必要がないコードクロー
クローン情報を扱う場合に特に対象とする必要がない
ものである．このようなコードクローンの存在は，調査を必要とするコードクローン情報を隠ぺいし，分析作業の非効率化を招いてしまう．実用的な可視化手法であるためには，調査の必要がないコードクローンの検出できなかったその他の原因について調査を行ってフィルタリングは必須であるといえる．

いる．例えば，Bellon は型名や予約語 super を特殊文

肥後らは，コードクローンの構造に着目したフィル

字への置換対象としているが Dup はしていないこと

タリング手法を提案している [53], [54]．彼らは，検出や，Bellon はコメント行を含めて 6 行以上がコードクされる調査の必要がないコードクローンの多くが，連ローンとしているが，Dup はコメント行はカウントし続した変数宣言やメソッド呼出し，switch 文の連続していないことなどである．その他の原因については，

た case エントリなど，繰り返し構造をもっているこ

文献 [52] を参照されたい．

とに着目し，コードクローンの非繰り返し度を表すメ

表 3 は，上記の調査項目を順に適用したときの再現

トリックス RNR を提案している．実験の結果，RNR

率の変化を表している．すべての項目を適用した場合，のしきい値として 0.5 が有効（注 21）であることが確認さ

つまり Dup により検出されたコードクローンのフィル

れている．

タリングを緩くした場合は，C 言語で 70%，Java 言
語で 65%まで再現率が上昇している．

Kapser らは，コードクローンと関数や構造体などのプログラムの要素の対応付けを行い，コードクロー

Baker は，ツール Dup が誤検出したコードクロー

ン含有率が 6 割以下の要素については，そのコードク（注 20）

ローンのフィルタリングを行うことが有効であると報ン

についてもその原因を調査している．その大きな原因として，Bellon は Java 言語の import 文や C告している [55]．また，対応付けにより，フィルタリ

言語のプリプロセッサ命令はコードクローンとしてングだけでなく，より理解しやすいコードクローン情

扱っていないが，Dup はそれらをコードクローンとし報が得られると主張している．

て検出したことや，Bellon は最終行のネストが先頭行

最も広く用いられている可視化手法は，散布図であのネストよりも浅いコード片はコードクローンにしてろう．詳細は異なるものの，これまでにいくつかの散いないが，Dup はそのようなコード片もコードクロー

布図が提案されている [11], [53], [56], [57]．図 5 (a) はンとして検出したことを挙げている．

Gemini（注 22）[53] の散布図のモデルを表している．散

本章では，これまでに提案されているコードクロー

布図では，水平軸と垂直軸に，対象プログラムの要素

ン検出技術，それらの比較報告，及び検出に影響を与が，出現順に配置される．そして，水平方向と垂直方

える要因の調査結果について述べたが，すべての面に向の要素が等しい場合に点が描画される．このモデル

おいて他の検出技術に勝っているものはない．例えば，

では，連続して 2 字句以上一致している部分をコードプログラム全体におけるコードクローンの割合を算クローンとして描画している．また，このモデルは，出したい場合は，他のツールよりも漏れなくコードク

上述したメトリックス RNR によるフィルタリングのローンを検出することのできる Kamiya らの手法 [6]

結果を反映している． で示された部分は，それをを用いる，集約を目的としたコードクローン検出を行含むコードクローンが RNR のしきい値以下，つまり，

う場合は，検出されたコードクローンに対して集約を調査の必要がない，と判断されたことを表している．

行いやすい Baxter らの手法 [5] を用いる，などのように，コードクローン情報を扱う状況に応じて，適切な検出技術を選択することが重要である．

4. コードクローンの分析及び可視化
コードクローンの分析及び可視化を行う上で最も障1474（注 20）：ここで誤検出されたコードクローンとは，ツール Dup によって検出されたが，Bellon の作成したコードクローンの集合には含まれていないコードクローンを指す．
（注 21）：繰り返し構造がコードクローン全体の半分以下であることを意味する．
（注 22）：Gemini は，文献 [6] で提案及び実装されているコードクローン
検出ツール CCFinder のフロントエンドである．

サーベイ論文／コードクローン検出とその関連技術(a) Polymetric View のモデル(a) 散布図のモデル(b) Polymetric View を用いた可視化の例

図 6 Polymetric View
Fig. 6 Polymetric View.

とにより，その条件を満たすコードクローン情報を得ることができる．Kapser らは，散布図はスケーラビ
リティが高くないため実用的ではない，と述べており，

CLICS は散布図を実装していない．また，このツールは上述したコードクローンとプログラムの要素の対応付けによるフィルタリング手法 [55] を実装している．

Rieger らは，Polymetric View [59] を用いたコード(b) 散布図を用いた可視化の例

クローン情報の可視化手法を提案している [56]．この

図 5 Gemini [53] の散布図
Fig. 5 Scatter plot of Gemini [53].

表現方法は，様々な粒度で抽象化されたコードクロー

調査の必要がないコードクローンを他のコードクロー

デルを表している．Polymetric View は，要素の位置

ンと異なって表示することにより，それらを除外して，や幅，高さなどと，要素のつなぐ辺の幅や色などがそ

効率的にコードクローンの分析作業を行うことができれぞれメトリックス値を表現しており，注目すべき箇る．また，図 5 (b) は，散布図を用いた可視化の例で所を一見して判断することができる．また，図 6 (b)ある．ひと目で，左上の部分に非常に多くのコードク

は，Polymetric View を用いた可視化の一例である．

ローンが存在していることが分かる．

ン情報を提供する．図 6 (a) は，Polymetric View のモ•

要素は，ソースファイルを表しており，要素のKapser らは，理解支援を目的としたツール CLICS

幅メトリックスはその要素内で閉じたコードクローンを開発している [58]．CLICS はソースファイルの構造の量，要素の高さメトリックスは，その要素が他の要やシステムのアーキテクチャをコードクローン情報を素の共有しているコードクローンの量を表している．

付与して表示する．CLICS はクエリ処理を実装しており，ユーザは興味のある特徴をクエリとして与えるこ•

辺は，その両端のソースファイル間で共有されているコードクローンの量を表している．
1475

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6

この可視化により，図 6 (b) 中のソースファイル A とクローンによって引き起こされる問題を軽減すること

B は，それぞれ内部で閉じたコードクローンと外部とができる．リファクタリングの先駆者 Fowler も，“重共有しているコードクローンを多く含んでおり，また複コードは最も優先して取り除くべき不吉な匂いの一両者は多くのコードクローンを共有していることが分つ”，と述べている [64]．また，Fowler は，文献 [64]かる．Rieger らも，コードクローン検出対象システムの中で，コードクローンの集約方法についても言及しが大きい場合には，非常に多くのコードクローンが検ている．例えば，ある一つのクラス内にコードクロー

出されてしまうため，フィルタリング機構が必要不可

ンが存在している場合は，重複部分を新たな内部メ

欠であると述べている．

ソッドとして抽出すればよく，同一クラスから派生しAdar らは，複数のバージョンからコードクローている複数のクラス間にコードクローンが存在していン を 検 出し て ，そ の 遷 移 の 様 子 を 表 示 す るツ ー ル

る場合は，重複部分を共通の基底クラスに引き上げる

GoftGUESS を開発している [60]．このツールを使うことによって，コードクローンを除去することが可能

ことによって，バージョンを通じて安定しているコーである，と述べている．

ドクローンや，異なる修正が加わった結果，コードク

Baxter らのツール CloneDr は，コードクローンをローンではなくなったものなど，コードクローンの状

検出すると同時に，そのコードクローンを集約するた態の変化を容易に知ることができる．

めのひな形も出力する [5]．このひな形を用いることにLivieri らは，複数のコンピュータ上でコードクロー

よって，集約を行うにはどのようにソースコードを修

ン検出を分散して行うことによって，大規模ソース

正すればよいのかを知ることができる．表 2 に示すよ

コード集合からの効率的なコードクローン検出及びうに，Baxter らの手法は他の手法に比べて適合率が可視化を行っている [61], [62]．このようなスケーラビ高いため，この支援はリファクタリングに非常に有効

リティの高い手法により，ソフトウェア内ではなくソであると思われる．

フトウェア間でのコードクローンを調査することが可

肥後らは，オブジェクト指向言語で記述されたソフ能となる．実際，Livieri らは，約 6,700 個（約 4 億

トウェアにおいて，コードクローン間の位置関係を行）のソフトウェア間での類似部分を特定することにメトリックスとして表現することにより，各コードク

成功している．また，Livieri らは，このような大規模ローンがどのように集約できるか予測する手法を提案

ソースコード集合からのコードクローン検出が，近年している [65]．肥後らは，まず Kamiya らの手法 [6] を問題になっている著作権違反に応用できる，と主張し用いてコードクローンを検出し，それに含まれるプロている．例えば，ソフトウェアライセンスの一つであグラムの構造的なまとまり（クラスやメソッド，ルーる GPL でライセンスされた著作物は，その派生著作

プなど）を抽出する．そして，抽出した構造的なコー物に対しても GPL でライセンスされなければならな

ドクローン間のクラス階層内における位置関係をメト

い．コードクローン検出を行うことにより，GPL でリックスを用いて表現する．このメトリックスを用いライセンスされたソフトウェアと他のライセンスをもることによって，各コードクローンが，文献 [64] の中

つソフトウェアが高い類似度であることが判明した場で紹介されているどの方法を用いて集約可能であるか合は，著作権違反の疑いを指摘することができる．

を予測する．また，各コードクローンがどの程度そのJohnson は HTML を用いたコードクローン情報の巡回手法を提案している [63]．HTML のハイパーリン

周囲のコードと強く結び付いているのかを計測する．

クを用いることによって，コードクローンを共有してに移動させることができるが，結合が強い場合は，移いるソースファイル間を自由に巡回することを可能に動させることは困難である．このような結合の度合もしている．

メトリックスとして提供することにより，どの程度容5. コードクローンの集約（注 23）

結合が低い場合は，容易にコードクローンを他の部分易に集約が行えるかを予測している．

Balazinska らは，メソッド単位のコードクローンにとは，互いにコードク

対する集約支援手法を提案している [66]．この手法でローンになっているコード片群を一つのモジュール

は，集約の際に重要な情報となるコードクローン間のコードクローンの集約（関数やメソッド，アスペクトなど）にまとめることである．コードクローンを集約することにより，コード1476（注 23）：merging code clones，unifying code clones

サーベイ論文／コードクローン検出とその関連技術違いを提供する．この違いを用いることによって，各ローンに比べ，リファクタリングを容易に行えるとい

コードクローンを集約するのか容易かどうかを判断

う結論であった．

することができる．また，肥後らの手法 [65] と同様に

上述のように，すべてのコードクローンが集約に向

コードクローンとその周囲との結合度も解析する．

いているわけではない．Toomim らは，あるコードク

Jarzabek は，従来のプログラミング言語の抽象化

ローンを修正すると，それと対応するすべてのコード

機構ではまとめることが難しい，複数のクラスにまクローンに対して，同様の修正を自動的に施すエディ

たがるような，大きい単位での類似部分を集約する

タを開発している [74]．Duala-Ekoko らも同時修正をためのフレームワーク XVCL を提案及び開発してい行うエディタを Eclipse のプラグインとして開発してる [67], [68]．XVCL を用いることによって，類似クラいる [75]．しかし，現段階では，これらのエディタは

ス群は，メタコンポーネントと呼ばれるモジュールにユーザの入力を，対応する各コードクローンに対して集約される．メタコンポーネントは，使用されている

そのまま反映させるため，タイプ 2 やタイプ 3 のコー

プログラミング言語による記述と，そのメタコンポー

ドクローンに対しては適用することができない．

ネントがどのようにコンパイル可能なクラスに展開さ泉田らは，CCFinder [6] のオプションを適切に設定れるかを記述した XVCL の命令文を含んでいる．実することによって，入力コード片と対象ソースコード

際に，XVCL を用いることによって，多くのコードク

間のコードクローンのみを高速に検出できると報告しローンを集約できたとの報告もされている [69], [70]．

ている [76]．適切に入力コード片を与えることによっ6. コードクローンの修正支援て，同時に修正すべき箇所を得ることができる．また，前章では，コードクローンの集約支援手法を紹介し報をソースコード中にコメントとして付加することにたが，すべてのコードクローンが集約可能あるいはす

よって，同時に修正すべき箇所を容易に特定することべきというわけではない．川口らや Kim らは，オーができると報告している [77]．

佐々木らも，CCFinder の検出したコードクローン情

プンソースソフトウェアの複数のバージョンに対して，Mann はコピーアンドペーストの履歴を保存する

コードクローンの出現と消失を調査し，次のことを報ことが有益であると主張している [78]．コピーアンド

告している [71], [72]．

ペーストの履歴をたどることにより，任意のコード片•あるバージョンでコードクローンになったが，の出自を知ることができ，またこれらは同時に修正す

その後異なった修正が加えられたことにより，コードべき候補となり得るとも述べている．開発者は 1 時間

クローンでなくなる場合がある．

に約 4 回のコード片単位でのコピーアンドペーストを•長期間存在するコードクローンは，プログラミ

行う [79]，及びコピーアンドペースト後に，各コード

ング言語に適切な抽象化機構が存在しないなど，集約片には異なった修正がしばしば加えられる [80]，とのを行わない理由が存在する．

報告もあることから，コピーアンドペーストの履歴を

Kapser らは，コードクローンを集約すべきではな

追うことにより，ソースコードのみを用いたコードク

い状況をいくつか紹介している [3]．例えば，新しいローン検出手法では検出することのできない，同時にハードウェアのドライバを作成する場合，既存のドラ修正すべき箇所を検出することができると考えられる．

イバから再利用可能な部分をコピーアンドペーストすることが有益であるとしている．既存の正しく動作し

7. む す びているドライバと，新しく作成しているドライバ間の本論文では，コードクローン検出とその関連技術に

コードクローン部分を集約することは，その際に不具ついて，これまでの研究成果をまとめた．コードク

合を混入してしまう危険があるため，そのような集約

ローン検出技術については，行単位の検出，字句単位は行うべきではないとしている．

の検出，抽象構文木を用いた検出，プログラム依存グ

Balazinska らは，コードクローン間の差異によって，ラフを用いた検出，メトリックスを用いた検出に分類

集約の困難さが異なると報告している [73]．Balazinska

し，分類ごとに提案されている手法を紹介した．また，らの実験結果では，コーディングスタイルなどの表面各提案手法につき，どのようなコードクローン（注 24）を的な違いのみを含むコードクローンは，利用している変数の型が違うなどの意味的な違いを含むコードク（注 24）：コードクローンの分類については，2. 2 を参照されたい．

1477

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6

検出することができるのかをまとめた．
関連技術については，コードクローン情報の分析とSept. 1994.
[11]

independent approach for detecting duplicated code,”

可視化，コードクローンの集約，コードクローンの修

Proc. International Conference on Software Mainte-

正支援に既存の研究成果を分類して紹介した．本論文で紹介した手法を適切に用いることよって，コードク

nance 99, pp.109–118, Aug. 1999.
[12]

Software Maintenance and Evolution: Research andることが可能であろう．

Practice, vol.18, no.1, pp.37–58, Jan. 2006.

本論文は，文部科学省リーディングプロジェ[13]

クト「e-Society 基盤ソフトウェアの総合開発」の委託に基づいて行われた研究，IJARC（マイクロソフト産学連携機構）第 3 回 CORE プロジェクト，文部科学省 科学研究費補助金 基盤研究（A）（ 課題番号：
17200001），及び若手研究（スタートアップ）（課題番
号：19800022）の助成を得て行われた研究をもとに作and Statistics, pp.49–57, March 1992.
[14]

Working Conference on Reverse Engineering, pp.86–
95, July 1995.
[15]“The 29th international conference on software engi-

1362, Oct. 1997.
[16]

C. Kapser and M.W. Godfrey, ““Cloning considered
Conference on Reverse Engineering, pp.19–28, Oct.

duplication fragments,” Proc. 7th International Symposium on Symbolic and Numeric Algorithms for Scientiﬁc Computing, pp.63–70, Sept. 2005.
[17]“Jplag - detecting software plagiarism,”[18]

L. Prechelt, G. Malpohl, and M. Phlippsen, “JPlag:

https://www.ipd.uni-karlsruhe.de/jplag/
Finding plagiarisms among a set of programs,” Tech-

2006.

nical Report, University of Karlsruhe, D-76128 Karl-

井上克郎，神谷年洋，楠本真二，“コードクローン検出法，” コンピュータソフトウェア，vol.18, no.5, pp.47–54,
Sept. 2001.

sruhe, Germany, March 2000.
[19]

Universal Computer Science, vol.8, no.11, pp.1016–

Bier, “Clone detection using abstract syntax trees,”nance 98, pp.368–377, March 1998.
[6]

1038, Nov. 2002.
[20]

software code,” IEEE Trans. Softw. Eng., vol.32,

A multilinguistic token-based code clone detection
Softw. Eng., vol.28, no.7, pp.654–670, July 2002.
[7]

no.3, pp.176–192, March 2006.
[21]

SOFT Symposium on the Foundations of Software

Matsumoto, and H. Kudo, “Software analysis by code
mation Systems, vol.XLV, no.3, pp.1–11, April 2005.
[8]

Engineering, pp.156–165, Sept. 2005.
[22]

S. Bellon, “Detection of software clones,” Technical

http://www.bauhaus-stuttgart.de/clones/[9]

Working Conference on Reverse Engineering, pp.253–
262, Oct. 2006.
[23]

tion of code clones,” Proc. 29th Intenational Confer-

E. Merlo, “Comparison and evaluation of clone devol.31, no.10, pp.804–818, Oct. 2007.
[10]

J.H. Johnson, “Substring matching for clone detection and change tracking,” Proc. International Conference on Software Maintenance 94, pp.120–126,

1478

L. Jiang, G. Misherghi, Z. Su, and S. Glondu,“DECKARD: Scalable and accurate tree-based detec-

S. Bellon, R. Koschke, G. Antoniol, J. Krinke, andtection tools,” IEEE Trans. Software Engineering,

R. Koschke, R. Falke, and P. Frenzel, “Clone detection using abstract syntax suﬃx trees,” Proc. 13th

Report, Institute for Software Technology, Universityof Stuttgart, 2003, available at

H.A. Basit and S. Jarzabek, “Detecting higher-level
similarity patterns in programs,” Proc. ACM SIG-

S. Uchida, A. Monden, N. Ohsugi, T. Kamiya, K.
clones in open source software,” J. Computer Infor-

Z. Li, S. Lu, S. Myagmar, and Y. Zhou, “CP-Miner:
Finding copy-paste and related bugs in large-scale

T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder:
system for large scale source code,” IEEE Trans.

L. Prechelt, G. Malpohl, and M. Philippsen, “Finding
plagiarisms among a set of programs with JPlag,” J.

I. Baxter, A. Yahin, L. Moura, M. Anna, and L.
Proc. International Conference on Software Mainte-

R. Wettel and R. Marinescu, “Archeology of code duplication: Recovering duplication chanins from small

門田暁人，佐藤慎一，神谷年洋，松本健一，“コードクロー

harmful” considered harmful,” Proc. 13th Working[5]

B.S. Baker, “Parameterized duplication in strings:
algorithms and an application to software mainte-献ンに基づくレガシーソフトウェアの品質の分析，” 情処学
論，vol.44, no.8, pp.2178–2187, Aug. 2003.

[4]“On ﬁnding duplication and near-

duplication in large software systems,” Proc. 2nd

neering,” http://web4.cs.ucl.ac.uk/icse07/[3]

B.S. Baker,

nance,” SIAM J. Comput., vol.26, no.5, pp.1343–

文[2]

B.S. Baker, “A program for identifying duplicatedcode,” Proc. 24th Symposium of Computing Science

成された．

[1]

S. Ducasse, O. Nierstrasz, and M. Rieger, “On the effectiveness of clone detection by string matching,” J.

ローン情報を，ソフトウェア開発・保守に有効に用い謝辞

S. Ducasse, M. Rieger, and S. Demeyer, “A language

ence on Software Engineering, pp.96–105, May 2007.
[24]

V. Wahler, D. Seipel, J.W.v. Gudenberg, and G.
Fischer, “Clone detection in source code by frequent
itemset techniques,” Proc. 4th IEEE International
Workshop on Source Code Analysis and Manipula-サーベイ論文／コードクローン検出とその関連技術[25]

tion, pp.128–135, Sept. 2004.

ﬁles as structured documents,” Proc. 10th IEEE In-

R. Komondoor and S. Horwitz, “Using slicing to iden-

ternational Workshop on Program Comprehension,
pp.289–292, June 2002.

tify duplication in source code,” Proc. 8th International Symposium on Static Analysis, pp.40–56, July
[26]

[42]

ing and visualizing prolog programs based on XML-J. Krinke, “Identifying similar code with program de-representations,” Proc. 13th International Workshop
on Logic Programming environments, Dec. 2003.

pendence graphs,” Proc. 8th Working Conference on
Reverse Engineering, pp.301–309, Oct. 2001.
[27]

[43]
[44]

ence, pp.76–85, June 2003.

Conference on Software Maintenance 96, pp.244–253,[45]

Bulletin, vol.8, no.4, pp.30–41, Dec. 1976.

and M. Bernstein, “Pattern matching for clone and

[29]

[46]

ing, vol.3, no.1-2, pp.77–108, June 1996.

ities in computer program and other texts,” Proc.
27th SIGCSE technical symposium on Computer Sci-

rics,” Proc. 4th Working Conference on Reverse En-

ence Education, pp.130–134, Feb. 1996.
[47]

cur., vol.16, no.3, pp.233–257, 1997.

Y. Ueda, T. Kamiya, S. Kusumoto, and K. Inoue,“On detection of gapped code clones using gap loca-

I. Krsul and E.H. Spaﬀord, “Authorship analysis:
Identifying the author of a prgoram,” Comput. Se-

gineering, pp.44–55, Oct. 1997.

[31]

M.J. Wise, “YAP3: Improved detection of similar-

K. Kontogiannis, “Evaluation experiments on the detection of programming patterns using software met-

[30]

K.J. Ottenstein, “An algorithmic approach to the detection and prevention of plagiarism,” ACM SIGCSE

K. Kontogiannis, R. Demori, E. Merlo, M. Galler,
concept detection,” Automated Software Engineer-

S. Schleimer, “Winnowing: Local algorithms for document ﬁngerprinting,” Proc. ACM SIGMOD Confer-software system using metrics,” Proc. International
Nov. 1996.

“Moss — A system for detecting software plagiarism,” http://theory.stanford.edu/˜aiken/moss/

J. Mayrand, C. Leblanc, and E. Merlo, “Experimenton the automatic detection of function clones in a

[28]

D. Seipel, M. Hopfner, and B. Heumesser, “Analyz-

2001.

[48]

E. Burd and J. Bailey, “Evaluating clone detection

tions,” Proc. 9th Asia-Paciﬁc Software Engineering

tools for use during preventative maintenance,” Proc.

Conference, pp.327–336, Dec. 2002.

2nd IEEE International Workshop on Source CodeAnalysis and Manipulation, pp.36–43, Oct. 2002.

D. Gusﬁeld, Algorithm on Strings, Trees, and Sequences, Campridge University Press, 1997.

[49]

F.V. Rysselberghe and S. Demeyer, “Evaluating[32]“CCFinderX,” http://www.ccﬁnder.net/

clone detection techniques,”[33]

X. Yan, J. Han, and R. Afshar, “CloSpan: Mining

Workshop on Evolution of Large Scale Intdustrial
Software Applications, Sept. 2003.

closed sequential patterns in large datasets,” Proc.
2003 SIAM International Conference on Data Min[34][50]ing, pp.166–177, May 2003.

detection techniques from a refactoring perspective,”Proc. 19th IEEE International Conference on Auto-analysis,” Proc. 2nd Workshop on Algorithms in

mated Software Engineering, pp.336–339, Sept. 2004.
[51]

Bioinformatics, vol.2542, pp.449–463, Sept. 2002.

Tourwe, “On the use of clone detection for identifying crosscutting concern code,” IEEE Trans. Software

Workshop on Frequent Itemset Mining Implementa-

Engineering, vol.31, no.10, pp.804–818, Oct. 2005.
[52]

pp.608–621, Sept. 2007.

“CloneDR,” http://www.semdesigns.com/Products/
Clone/[53]“Locality-sensitive hashing scheme based on p-stable

[38]

[54]

Y. Higo, T. Kamiya, S. Kusumoto, and K. Inoue,

tional Geometry, pp.253–262, June 2004.

“Method and implementation for investigating code

G.J. Badros, “JavaML: A markup language for Javaclones in a software system,” Information and Soft-source code,” Comput. Netw., vol.33, no.1-6, pp.159–

ware Technology, vol.49, no.9-10, pp.985–998, Sept.

177, 2000.
[39]

肥後芳樹，吉田則裕，楠本真二，井上克郎，“産学連携に基づいたコードクローン可視化手法の改良と実装，” 情処
学論，vol.48, no.2, pp.811–822, Feb. 2007.

M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni,
distributions,” Proc. 20th Symposium on Computa-

B.S. Baker, “Finding clones with dup: Analysis of anexperiment,” IEEE Trans. Softw. Eng., vol.33, no.9,

tions, Nov. 2003.

[37]

M. Bruntink, A. van Deursen, R. van Engelen, and T.

G. Grahne and J. Zhu, “Eﬃciently using preﬁxtrees in mining frequent itemsets,” Proc. IEEE ICDM

[36]

F. Rysselberghe and S. Demeyer, “Evaluating clone

M.I. Abouelhoda, S. Kurtz, and E. Ohlebusch, “Theenhanced suﬃx array and its applications to genome[35]

Proc. International

G. Fischer and J.W.v. Gudenberg, “Simplifying

2007.
[55]

C. Kapser and M.W. Godfrey, “Aiding comprehen-source code analysis by an XML representation,”sion of cloning through categorization,” Proc. 7th In-

Softwaretechnik Trends, vol.23, no.2, pp.49–50, May

ternational Workshop on Principles of Software Evo-

2003.
[40]

“JavaML,” http://www.badros.com/greg/JavaML/[41]

J. Maletic, M. Collard, and A. Marcus, “Source codelution, pp.85–94, Sept. 2004.
[56]

M. Rieger, S. Ducasse, and M. Lanza, “Insights into
system-wide code duplication,” Proc. 11th Work-1479

電子情報通信学会論文誌 2008/6 Vol. J91–D No. 6
Practice, vol.18, no.4, pp.267–292, July 2006.

ing Conference on Reverse Engineering, pp.100–109,[71]

Nov. 2004.

川口真司，松下 誠，井上克郎，“版管理システムを用いたクローン履歴分析手法の提案，” 信学論（D），vol.J89-D，no.10, pp.2279–2287, Oct. 2006.

[57]

植田泰士，神谷年洋，楠本真二，井上克郎，“開発保守支援を目指したコードクローン分析環境，” 信学論（D-I），[58]

C. Kapser and M.W. Godfrey, “Improved tool sup-“An empirical study of code clone genealogies,” Proc.

port for the investication of duplication in soft-

ACM SIGSOFT Symposium on the Foundations of

vol.86-D-I，no.12, pp.863–871, Dec. 2003.

[72]

Software Engineering, pp.187–196, Sept. 2005.

ware,” Proc. 21st International Conference on Soft[73]ware Maintenance, pp.305–314, Sept. 2005.
[59]

A

and K. Kontogiannis, “Measuring clone based reengineering opportunities,” Proc. 6th IEEE International

IEEE Trans. Softw. Eng., vol.29, no.9, pp.782–795,

Symposium on Software Metrics, pp.292–303, Nov.

E. Adar and M. Kim, “Visualization and explo-

1999.
[74]

duplicated code with linked editing,” Proc. IEEE

tional Conference on Software Engineering, pp.762–

Symposium on Visual Languages and Human-Centric

S. Livieri, Y. Higo, M. Matsushita, and K. Inoue,

Computing, pp.173–180, Sept. 2004.
[75]

clones in evolving software,” Proc. 29th Interna-

ization of open source program using distributed

tional Conference on Software Engineering, pp.158–

Conference on Software Engineering, pp.106–115,

167, May 2007.
[76]

S. Livieri, Y. Higo, M. Matsushita, and K. Inoue,“Analysis of the linux kernel evolution using code[77]

ware Repositories, pp.22.1–22.4, May 2007.
J.H. Johnson, “Navigating the textual redundancy

pp.868–870, Sept. 2004.
[78]

tre for Advanced Studies on Collaborative Research,
pp.7–16, Nov. 1996.
[64]
[65]

Z.A. Mann, “Three public enemies: Cut, copy, andpaste,” Computer, vol.39, no.7, pp.31–35, July 2006.

[79]

M. Kim, L. Bergman, T. Lau, and D. Notkin, “An

M. Fowlor, Refactoring: improving the design of ex-

ethnographic study of copy and paste programming

isting code, Addison Wesley, 1999.

practices in OOPL,” Proc. 2004 International Sym-

肥後芳樹，神谷年洋，楠本真二，井上克郎，“コードク

posium on Empirical Software Engineering, pp.83–92,

ローンを対象としたリファクタリング支援環境，” 信学論（D-I），vol.J88-D-I，no.2, pp.186–195, Feb. 2005.
[66]

佐々木亨，肥後芳樹，神谷年洋，楠本真二，井上克郎，“プログラム変更支援を目的としたコードクローン情報付加” 信学論（D-I），vol.87-D-I，no.9,
ツールの実装と評価，

clone coverage,” Proc. 4th Workshop on Mining Soft-Web in legacy source,” Proc. 1996 Conference of Cen-

泉田聡介，植田泰士，神谷年洋，楠本真二，井上克郎，“ソフトウェア保守のための類似コード検索ツール，” 信学論（D-I），vol.86-D-I，no.12, pp.906–908, Dec. 2003.

May 2007.

[63]

E. Duala-Ekoko and M.P. Robillard, “Tracking code

“Very-large scale code clone analysis and visualCCFinder: D-CCFinder,” Proc. 29th International[62]

M. Toomim, A. Begel, and S. Graham, “Managing

ration of code clones in context,” Proc. 29th Interna766, May 2007.
[61]

M. Balazinska, E. Merlo, M. Dagenais, B. Lagüe,lightweight visual approach to reverse engineering,”

M. Lanza and S. Ducasse, “Polymetric views:

Sept. 2003.
[60]

M. Kim, V. Sazawal, D. Notkin, and G.C. Murphy,

Aug. 2004.
[80]

M. Balint, T. Girba, and R. Marinescu, “How de-

M. Balazinska, E. Merlo, M. Dagenais, B. Lagüe, andvelopers copy,” Proc. 14th IEEE International Con-

K. Kontogiannis, “Advanced clone-analysis to sup-ference on Program Conprehension, pp.56–68, June

port object-oriented system refactoring,” Proc. 7th

2006.

IEEE International Working Conference on Reverse（平成 19 年 7 月 26 日受付，12 月 23 日再受付）

Engineering, pp.98–107, Nov. 2000.
[67]“XML-based variant conﬁguration language — Tech-[68]

S. Jarzabek, Eﬀective Software Maintenance andnology for Reuse,” http://xvcl.comp.nus.edu.sg/
Evolution: Reused-based Approach, CRC Press Taylor and Francis, 2007.
[69]

芳樹 （正員）S. Jarzabek and L. Shubiao, “Eliminating redun-

平 14 阪大・基礎工・情報中退．平 18 同

dancies with a “composition with adaptation” metaprogramming technique,” Proc. ESEC-FSE’03 Eu-

大大学院博士後期課程了，平 19 阪大・情報・コンピュータサイエンス・助教．博士

ropean Software Engineering Conference and ACM（情報科学）．コードクローン分析・リファ

SIGSOFT Symposium on the Foundations of Soft-

クタリングに関する研究に従事．情報処理学会，IEEE 各会員．

ware Engineering, pp.237–246, Sept. 2003.
[70]

肥後

S. Jarzabek and S. Li, “Unifying clones with a generative programming technique: A case study,” J.
Software Maintenance and Evolution: Research and1480

サーベイ論文／コードクローン検出とその関連技術

楠本

真二 （正員）昭 63 阪大・基礎工・情報卒．平 3 同大
学院博士課程中退．同年同大・基礎工・情報・助手．平 8 同大講師．平 11 同大助教
授．平 14 阪大・情報・コンピュータサイ
エンス・助教授．平 17 同学科教授．博士（工学）．ソフトウェアの生産性や品質の定量的評価，プロジェクト管理に関する研究に従事．情報処理学会，IEEE，JFPUG 各会員．

井上克郎 （正員）昭 54 阪大・基礎工・情報卒．昭 59 同大
大学院博士課程了．同年同大・基礎工・情報・助手．昭 59〜61 ハワイ大マノア校・情報工学科・助教授．平元阪大・基礎工・情報・講師．平 3 同学科・助教授．平 7 同学科・教授．博士（工学）．平 14 阪大・情報・コンピュータサイエンス・教授．ソフトウェア工学の研究に従事．情報処理学会，日本ソフトウェア科学会，IEEE，ACM，各会員．

1481