情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

多粒度コードクローンの検出と評価
幸 佑亮1

肥後 芳樹1,a)

楠本 真二1

受付日 2017年8月2日, 採録日 2018年1月15日

概要：コードクローンはソフトウェアの保守性を低下させる原因の 1 つとされており，コードクローンがソフトウェア中にどの程度存在しているか，およびどこに存在しているかを理解することはソフトウェア
保守の観点から重要である．そのため，これまでに多くのコードクローン検出手法が提案され，自動的にコードクローンを検出するツールが開発されている．既存のコードクローン検出手法は，ファイル単位やコード片単位など単一の粒度でコードクローンを検出する．一般的に，検出の粒度が粗いほど検出時間は短くなるが，検出可能なコードクローンは少なくなる．一方，検出対象の粒度が細かいほど検出可能な
コードクローンは多くなるが，検出時間は長くなる．そこで本論文では，より多くのコードクローンをより短時間で検出することを目的として，粗粒度から細粒度へ段階的にコードクローンを検出する手法を提案する．段階的にコードクローンを検出する過程において，ある粒度でコードクローンとして検出された
コードをそれよりも細粒度なコードクローンの検出対象から除外することで，細粒度な検出手法と比較してより高速に検出できる．また，粗粒度な検出手法と比較してより多くのコードクローンを検出できる．
提案手法をコードクローン検出ツール Decrescendo として実装し，複数のオープンソースソフトウェアに適用した．そして，提案手法を粗粒度な検出手法および細粒度な検出手法と比較して評価を行った．実験の結果より，細粒度な（コード片単位の）検出手法と比較して，多粒度な検出手法が約 10∼20 倍高速に
コードクローンを検出できることを示した．また，粗粒度な（メソッド単位の）検出手法と比較して，多粒度な検出手法が約 10∼30 倍のコードクローンを検出した．この検出数は細粒度な（コード片単位の）検出手法とほぼ同数であった．
キーワード：コードクローン，ソースコード解析，大規模実験

Detection and Evaluation of Multi-grained Code Clones
Yusuke Yuki1

Yoshiki Higo1,a)Shinji Kusumoto1

Received: August 2, 2017, Accepted: January 15, 2018

Abstract: The presence of code clones is one of the factors that makes software maintenance more diﬃcult.
Understanding the number of code clones and their distribution is helpful for developers. Before now, various
kinds of code clone detection techniques and tools have been proposed and developed. Existing techniques
detect code clones with a single granularity such as ﬁle, method, or code fragment. Coarser granularity
detection requires shorter time, but it ﬁnds the smaller number of code clones. In this paper, we propose amulti-grained clone detection technique, which detects a larger number of code clones with short time. In
the proposed technique, ﬁrstly coarse grained detection is performed. Detected coarse-grained code clones
are eliminated from the target of ﬁner-grained clone detections. Such a multi-grained detection is eﬀective toshorten detection time and detects a large number of code clones as well as ﬁne-grained detection techniques.
The proposed technique has been implemented by a tool, Decrescendo. Decrescendo has been applied toa large set of open source software to compare it with existing detection techniques. As a result, the proposed technique ﬁnished detection 10∼ times shorter than ﬁne-grained techniques. The proposed techniquedetected code clones 10∼30 times more than coarse-grained techniques. The number of code clones detectedby the proposed technique is approximately the same as ﬁne-grained techniques.
Keywords: code clone, source code analysis, large-scale experiment1a)

1. はじめに大阪大学大学院情報科学研究科コンピュータサイエンス専攻
Graduate School of Information Science and Technology,
Osaka University, Suita, Osaka 565–0871, Japanhigo@ist.osaka-u.ac.jp

c 2018 Information Processing Society of Japan

コードクローン（以下，クローン）とは，ソースコード
中に存在する互いに同一，あるいは類似したコード片であ1192情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

図 1

各検出手法の特徴

Fig. 1 Characteristics of each detection technique.

る．クローンの主な発生要因はコピーアンドペーストであ

抽象構文木で表現した場合の頂点数はソースコード中る [10], [11], [16], [19]．一般的に，クローンはソフトウェのクラス数，メソッド数，ブロック数と比較して多い．

アの保守性を低下させる原因になるとされている．たとえ

そのため，粗粒度な検出手法と比較して細粒度な検出ば，あるコード片にバグが存在した場合，そのクローンに手法は検出時間が長い．

対しても同様のバグが存在する可能性があり，同様の変更

検出可能なクローンの数 検出の粒度が粗いほど，検出可を検討する必要がある．そのため，クローンがソフトウェ

能なクローンの数が少なく，検出の粒度が細かいほど，

ア中にどの程度存在しているか，およびどこに存在してい検出可能なクローンの数が多い．粗粒度な検出手法はるかを理解することはソフトウェア保守の観点から重要でファイル単位，メソッド単位，もしくはブロック単位あり，これまでに多くのクローン検出ツールが提案されてでクローンを検出するが，それらの内部の一部のみがいる．

類似しているコード片をクローンとして検出できな

近年，単一のソフトウェアのみでなく，複数のソフト

い．そのため，細粒度な検出手法と比較して粗粒度なウェアからなる大規模なソースコードの集合に対してク

検出手法は検出可能なクローンの数が少ない．一方でローン検出ツールを適用し，ライブラリの候補や修正漏れ

細粒度な検出法は，大きな重複コードを小さな単位でを検出する研究が行われている [17]．複数のソフトウェア

検出してしまうという課題がある．たとえば，ファイに存在する同一の処理をライブラリ化することは開発効率

ル全体が重複している場合であっても，メソッド単位の向上の観点から有益であり，先行研究においてそのようのクローン検出法を使った場合は，ファイル全体が 1なクローンの存在が確認されている．

つのクローンとしては検出されず，そのファイル内に既存のクローン検出手法は，ファイル単位やコード片単位など単一の粒度でのみクローンを検出している．既存のクローン検出手法は，大きく分けて以下の 2 つの検出手法含まれているメソッドが複数のクローンとして検出されてしまう．
つまり，粗粒度な検出手法は「小さい重複コードを検出に分類できる [20]．

できない」というデメリットがあり，細粒度な検出手法は粗粒度な検出手法 類似したクラス・メソッド・ブロック「検出に長い時間を必要とする」および「大きな重複コードをクローンとして検出する手法．

を小さい単位のクローンとして検出してしまう」というデ

細粒度な検出手法 任意のコード片をクローンとして検出メリットがある．本論文では，粗粒度な検出手法と細粒度する手法．細粒度な検出手法はクラス・メソッド・ブ

な検出手法のデメリットを低減させるために，粗粒度から

ロックの一部が類似するコード片をクローンとして検細粒度へ段階的に（多粒度で）クローンを検出する手法を出できる．

提案する．具体的にはファイル単位・メソッド単位・コー

これらの手法は以下の一長一短な特徴を持つ．ファイル

ド片単位の順にクローンを検出する．段階的にクローンを単位，メソッド単位，ブロック単位，およびコード片単位検出する過程において，ある粒度でクローンとして検出さの検出手法の特徴を図 1 にあげる．

れたコードをそれよりも細粒度なクローンの検出対象から検出に要する時間 検出の粒度が粗いほど検出時間が短く，除外していくことで，細粒度な検出手法と比較してより高検出の粒度が細かいほど検出時間が長い．ソースコー
ドの行数，ソースコード中の字句数，ソースコードを

c 2018 Information Processing Society of Japan

速に検出できる．
また，粗粒度で検出できるクローンは粗粒度で検出する

1193

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

ことにより，大きな重複コードが小さい単位のクローンとして検出されることを防げる．たとえば，ファイル全体が重複コードになっている場合には，複数のメソッド単位のクローンとして検出するのではなく，1 つのファイル単位のクローンとして検出する．これによって，検出されるク
ローンの数が不必要に多くならなくなる．また，提案手法
は細粒度でも検出を行うため小さい重複コードも検出可能である．このように，提案手法は粗粒度な検出手法や細粒度な検出手法と比較してより適切な粒度でクローンを検出できる．
提案手法をクローン検出ツール Decrescendo として実装し，複数のオープンソースソフトウェアに適用した．そ

図 2

ファイルのハッシュ値に基づいたクラスタリング

Fig. 2 Clustering based on ﬁle hash.

して，提案手法を粗粒度な検出手法および細粒度な検出手法と比較した．
本論文の貢献は以下のとおりである．

• 粗粒度から細粒度へ段階的に（多粒度で）クローンを検出する手法を提案した．

• 細粒度な検出手法と比較して多粒度な検出手法が高速にクローンを検出できること，および粗粒度な検出手法と比較して多粒度な検出手法がクローンの検出数が多いことを示した．

• 細粒度な検出手法および細粒度な検出手法と比較して，多粒度な検出手法が分析しやすいクローンの検出
結果を生成できることを示した．
以降，2 章では本研究の位置づけについて述べる．3 章
では提案手法について述べる．4 章では実装したツールの図 3

本研究の位置づけ

Fig. 3 Relatioship between this research and existing ones.

詳細について述べる．5 章では評価実験について述べる．

6 章では実験の妥当性について述べる．最後に，7 章で本

これにより，検出した各クローンの粒度が明らかになり，論文をまとめる．

先行研究よりも分析しやすいクローンの検出結果を生成で

2. 本研究の位置づけ

きる．
既存のクローン検出手法と本論文で提案する多粒度な検コード片単位のクローン検出を行う前にファイルのハッ出手法の位置づけを図 3 に示す．粗粒度な検出手法（ファシュ値に基づいたクラスタリングを行う，という Choi ら

イル単位・メソッド単位・ブロック単位の検出手法）は，検の先行研究がある [3]．このクラスタリングはコード片単出に要する時間が短く，検出されるクローンの数が少ない．

位のクローン検出時間を短縮することが目的である．ファ

一方，細粒度な検出手法（コード片単位の検出手法）は，検イルのハッシュ値に基づいたクラスタリングの例を図 2 に出時間が長く，検出数が多い．そこで，本論文で提案する示す．ファイル中の数値はハッシュ値を表しており，ファ多粒度な検出手法は，検出時間を短く，かつ検出数を多く

イル外の枠はハッシュ値が等しいファイルのグループをすることを目的とする．また，本論文の提案手法は，ファ表す．クラスタリング後，各グループから 1 つのファイル

イル単位のクローンに加えて，メソッド単位のクローンもを選択する．そして，選択されたファイルの集合に対して検出する．13,000 個のソフトウェア群に存在するメソッド

コード片単位のクローン検出を行う．

集合のうち約 49%がメソッドクローンであったという研究

本論文の提案手法は，コード片単位のクローン検出を行報告がある [17]．複数のソフトウェア間にメソッドクロー

う前にファイル単位およびメソッド単位のクローン検出をンが多数存在するため，メソッド単位の検出の後にコード行うことにより，先行研究に比べてより短い時間でコード

片単位の検出を行うことで，コード片単位の検出に要する片単位のクローン検出を行うことができる*1 ．さらに，本

時間的コストが大幅に改善されることが見込める．

提案手法は検出した各クローンに粒度の情報を付加する．
*1

本研究ではブロック単位のクローン検出は行わない．その理由については 3 章を参照されたい．

c 2018 Information Processing Society of Japan

Kodhai らは，メソッドクローンの検出を効率的に行う手法を提案している [8]．彼らの手法では，メソッドクロー
ンの検出を行う前に，各メソッドに対してメトリクス計測

1194

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

を行い，メトリクス値が同じか類似しているメソッドのみに対してメソッドの各行を比較する処理を行うというものである．この前処理によってクローン検出が短時間で終わることが期待されているが，前処理の有無による検出時間の比較はなされていない．Deepali らはソースコードではなくバイトコードからメトリクスを計測し，十分にメトリ
クス値が近いクラスについて，そのソースコードを詳細に比較することによりクローンを検出する方法を提案している [4]．こちらについてもメトリクス計測を導入することによる検出速度改善については評価されていない．これらどちらの研究も，計算に時間を要するコード片単位の検出の対象となるソースコードを減らすという点では本研究と類似している．しかし，これらの研究では，重複コードをできるだけ大きな単位として検出するということは達成されておらず，その点で本研究とは異なる．

3. 提案手法
提案手法は対象ソースコードに対して粗粒度から細粒度へ段階的に（多粒度で）クローンを検出する．具体的には
ファイル単位，メソッド単位，コード片単位の順にクローンを検出する．段階的に検出する過程において，ある粒度

図 4

提案手法の概要

Fig. 4 Overview of the proposed technique.

でクローンとして検出されたコードをそれよりも細粒度なクローンの検出対象から除外していく．以降，ファイル単位のクローンをファイルクローン，メソッド単位のクローンをメソッドクローン，コード片単位のクローンをコード
片クローンと呼ぶ．
現在のところ，提案手法ではブロック単位でのクローン検出を行わない．その理由は以下の 2 つである．

• ブロックの大きさはメソッドよりも小さく，ブロック単位の検出を導入することによる高速化が限定的であるため．

• コードクローンは 1 つのブロック内で閉じているとは限らないため，検出の処理が煩雑になるため．

図 5 後処理の例

Fig. 5 Example of the post processing.

ローン検出処理により以下の 3 つのメソッドがクローンとして検出されている．

3.1 検出手順• methodB1，methodB2，methodD2

図 4 に提案手法の概要を示す．段階的にクローンを検出

このあと除外したファイルに対するメソッドクローンする過程において，ファイル単位の検出でクローンとしての検出漏れを防ぐための後処理が行われる．具体的には，検出されたファイルを，次のメソッド単位の検出の入力か

メソッドクローン methodD2 が存在している D.java はら除外する．図 4 では，ファイル単位の検出において，以F.java とファイルクローンであるため，F.java に含まれ下の 2 つのファイルクローングループが検出されている．

る methodF2 もこのメソッドクローングループに加える• A.java，C.java，E.java（図 5）．結果として，以下の 4 つのメソッドが 1 つのメ• D.java，F.java

ソッドクローングループとして検出される．

次のメソッド単位の検出では各ファイルクローングルー
プから 1 つのファイルを選ぶ（各グループ内の他のファイ
ルはメソッドクローンの検出対象から除外する）．

• methodB1，methodB2，methodD2，methodF2
次のコード片単位の検出では，各メソッドクローング
ループから 1 つのメソッドを選び，メソッドクローンと選択されたファイルとファイルクローンになっていない

なっていないメソッドとともにコード片クローン検出処理

ファイル内に存在しているメソッドに対してメソッドクが適用される．コード片クローン検出後はメソッドクロー

ローンの検出処理が適用される．この例では，メソッドク

ン検出後の後処理と同様に，除外したメソッド内に含まれc 2018 Information Processing Society of Japan


1195

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

4. 実装
ここでは，著者らが実装した多粒度クローン検出ツール

Decrescendo について述べる．なお，このツールにおいて，メソッドクローン検出部分は著者らの既存研究 [17] と同一であり，提案手法のファイルクローン検出部分は既存
研究 [17] の検出法をファイル単位に変更したものである．
コード片クローン検出については Suﬃx-Tree アルゴリズム
および Smith-Waterman アルゴリズムを用いて実装した．
どちらのアルゴリズムもクローン検出において有用なことが示されている [6], [18]．なお，本研究におけるコード片
単位のクローン検出は，各メソッドの内部のコードのみを対象として行っている．つまり，あるファイル内の 2 つの連続したメソッドが他のファイル内の 2 つの連続したファ
イルと重複コードになっていた場合，それらは 1 つのコー
ド片単位のクローンではなく，各メソッドをコード片とす
る 2 つのクローンとして検出される．

Decrescendo の入力は以下のとおりである．
図 6 単粒度におけるクローン検出例

Fig. 6 Example of single granularity detections.

• Java ソースファイル群• 最小クローン長• 最大ギャップ率

るコード片クローンの検出漏れを防ぐための後処理が行われる．

最小クローン長は検出するクローンの最小の大きさを指定するためのものである．最小クローン長に小さな値を指定すればより多くのクローンを検出できるが，検出結果に3.2 多粒度クローンの提示方法
提案手法を利用することにより，重複コードをできるだ

は多くの誤検出が混じる．大きな値を指定すれば誤検出を減らせるが見逃すクローンも増えてしまう．

け大きい単位のクローンとして検出できる．例を図 6 にあ最大ギャップ率とは，Smith-Waterman アルゴリズムをげる．この例ではメソッド単位のみで検出した場合，3 つ

利用する場合にのみ指定する値であり，クローンとして許のファイルからは以下の 2 つのメソッドクローングループ

容するギャップ（不一致部分）の割合を表す．最大ギャッが検出される．

プ率を大きくすればより多くのクローンを検出できるが検• methodD1，methodF1

出結果には多くの誤検出が含まれてしまう．小さい値を設• methodB1，methodB2，methodD2，methodF2

定すれば誤検出を減らせるが見逃してしまうクローンが増

この検出結果からは，D.java と F.java がファイルクロー

えてしまう．

ンとなっていることが分かりにくい．
ファイル単位のみで検出した場合，以下のファイルク
ローングループが検出される．

出力はクローンペアの位置情報，粒度（ファイル・メソッ
ド・コード片），およびタイプ（Type-1・Type-2・Type-3）である．クローンのタイプを図 7 を用いて説明する．たと• D.java，F.java

えば，コピーアンドペーストしただけのコードであれば，この結果からは，B.java が D.java および F.java とメソッ

コピー元とコピー先のコード片は完全に同一な Type-1 ク

ドクローンを共有していることが分からない．
多粒度で検出することで以下のクローングループが検出される．

• D.java，F.java

ローンとなる．変数名を変更した場合には字句単位の差異が生じ，Type-2 クローンとなる．文の追加・削除・変更を行った場合には字句単位よりも大きな差異（ギャップ）が生じ，Type-3 クローンとなる．

• methodB1，methodB2，methodD2，methodF2検出するクローンのタイプは以下のとおりである．

このように，多粒度で検出を行うことにより，小さいク• ファイル単位およびメソッド単位では，Type-1 およ

ローンを見逃すことなく，重複コードはできるだけ大きなクローンとして検出できる．

び Type-2 のクローンが検出される．

• Suﬃx-Tree アルゴリズムを用いてコード片クローンの検出を行った場合は，Type-1 および Type-2 のクローンが検出される．

c 2018 Information Processing Society of Japan

1196

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

ルに含まれる字句数が最小クローン長に満たない場
合，検出対象から除外する．このフィルタリングを行うことによりクローンが検出されることのないファイルに対するこれ以降の処理を省くことができる．

STEP-3（ファイルハッシュ値の計算） 各ファイルに対してハッシュ値を算出する．現在の実装ではハッシュ値の計算に MD5 を利用している．

STEP-4（ファイルグループの生成と出力） ハッシュ値が同じファイルでグループを作る．2 つ以上のファイルを含むグループがファイルクローンとして検出さ図 7クローンのタイプ

Fig. 7 Clone types.

れる．
ファイルクローンの検出の後は，メソッドクローンの検出を行う．

• Smith-Waterman アルゴリズムを用いてコード片ク

STEP-5（メソッドの切り出し） STEP-4 において生成ローンを検出した場合は，Type-1，Type-2，およびされた各グループからファイルを 1 つ無作為に選択すType-3 のクローンが検出される．

る．ファイルが 1 つだけ含まれるグループも対象であ

コード片単位の検出手法を 2 通りの手法で実装した理る．選択された各ファイルに含まれるメソッドを抽出

由は，細粒度な検出手法のうち，Type-2 までのクローンする．図 4 では，A.java，B.java，および D.java が選を検出する手法と Type-3 までのクローンを検出する手法

択されている．

のどちらに対しても，多粒度な検出手法が検出時間と検出

STEP-6（メソッドフィルタリング） メソッドに含まれ数の面で有用かどうかを評価するためである．Type-2 まる字句数が最小クローン長に満たない場合，検出対象でのクローンを検出する手法の中で Suﬃx-Tree アルゴリ

から除外する．このフィルタリングを行うことにより，ズムを採用した理由は，Suﬃx-Tree アルゴリズムが用いらクローンが検出されることのないメソッドに対するこれているクローン検出ツールが代表的な字句単位の検出れ以降の処理を省くことができる．

ツールであり，様々な企業や研究で採用されているためで

STEP-7（メソッドハッシュ値の計算） 各メソッドに対ある [1], [7], [14]．Type-3 までのクローンを検出する手法

してハッシュ値を計算する．ハッシュ値が等しいメの中で Smith-Waterman アルゴリズムを採用した理由は，

ソッドがメソッドクローンとなる．ファイルハッシュ

Smith-Waterman アルゴリズムが応用されているクローンと同じく MD5 を用いて計算する．

検出ツールがその他の Type-3 クローン検出ツールと比較して，高速に検出可能なためである [18]．

STEP-8（メソッドグループの生成） ハッシュ値が同じメソッドでグループを作る．2 つ以上のメソッドをまた，提案手法はその性質上，Type-3 のファイルクロー

含むグループがメソッドクローンとして検出される．

ンやメソッドクローンは検出できない．対象ソースコード

図 4 では，methodB1，methodB2，および methodD2

中に Type-3 のファイルクローンやメソッドクローンに該がメソッドクローンとして検出されている．

当する重複コードが存在した場合には，より細粒度なク

STEP-9（メソッドクローン検出の後処理と出力）ローンとして検出される．

STEP-4 で選択されなかったファイル（図 4 における以降，本章では Decrescendo の処理の流れを説明する．

C.java，E.java，および F.java）に含まれるメソッドク

必要に応じて図 4 を参照されたい．Decrescendo の最初のローンをとりこぼさないための処理を行う．具体的に処理はファイルクローンの検出である．

は，STEP-5 で選択されたファイルから STEP-8 にお

STEP-1（ファイルの正規化） 入力として与えられた各

いてメソッドクローンが検出された場合には，STEP-5

Java ファイルに対して以下に示す正規化を行う．

で選択されなかったファイルにもそのメソッドクロー• インデント，改行，コメント，import 文，修飾子をンが存在しているとする．図 4 では，この処理により，削除• 識別子名およびリテラルを特殊文字に置換
この処理によって，2 つのファイル間でコーディング

STEP-8 で検出されたメソッドクローンに，methodF2が加えられている．
メソッドクローンを検出した後は，コード片クローンのスタイルが異なる場合や識別子名またはリテラルが異検出を行う．

なる場合でも，その 2 つのファイルをクローンとして

STEP-10（コード片クローンの検出） STEP-8 において検出可能になる．

STEP-2（ファイルフィルタリング） 正規化後のファイc 2018 Information Processing Society of Japan

生成された各グループからメソッドを 1 つ無作為に選択する．メソッドが 1 つだけ含まれるグループも対象

1197

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

表 1

である．選択された各メソッドに対して，Suﬃx-Tree

対象ソフトウェアもしくは Smith-Waterman アルゴリズムを用いること

Table 1 Target software.

により，それらに含まれるコード片クローンを検出す

ソフトウェア数

る *2 ．

ファイル数
メソッド数

STEP-11（コード片クローン検出の後処理と出力）

LOC

STEP-5 で選択されなかったファイルや STEP-10 で84
66,724
628,219
11,545,556

選択されなかったメソッドに含まれるコード片クロー
ンをとりこぼさないための処理を行う．処理内容は

5.4 実験対象
表 1 に対象ソフトウェアの概要を示す．対象ソフトウェ

STEP-9 と同様である．
なお，Decrescendo は，設定によって各粒度における検出のオン・オフを切り替えることができる．

5. 実験
5.1 準備アは Apache Software Foundation のリポジトリ*3 から取得
した 2013/10/31 時点の 84 個のソフトウェアである．バージョンが異なる同一ソフトウェア間からのクローン検出を避けるために trunk 以下のファイルのみを検出対象とする．これらのソフトウェアを対象とした理由は，著者らのDecrescendo を複数のオープンソースソフトウェアに対先行研究 [5] において利用されたデータセットであり，テして適用し，多粒度な検出手法と粗粒度な検出手法およ

ストコードと自動生成コードが取り除かれているためであび細粒度な検出手法と比較した．今回の実験では，最小クる．テストコードと自動生成コードは流用の特定や複数のローン長を 50 字句，最大ギャップ率を 0.3 としている．こソフトウェアに存在する共通処理のライブラリ化に対してれらの値は先行研究 [2], [13] を参考にしている．なお，文は有用でなく，クローンとして検出する必要性がない．

献 [15] には，Decrescendo を他のソフトウェア群に対して適用した結果（Smith-Waterman アルゴリズムを用いた場

5.5 項目 1 の調査
表 2 にクローンの検出結果を示す．各粒度の ◦ はその粒合のみ）が記載されている．

度の検出が行われたことを表す．検出 ID は，本節の以降で5.2 調査項目
本実験の調査項目を以下に示す．
項目 1

粗粒度な検出手法および細粒度な検出手法と比較して，多粒度な検出手法は検出時間が短いか．
項目 2

粗粒度な検出手法および細粒度な検出手法と比較して，多粒度な検出手法は検出されるクローンの数がどの検出について言及しているのかを簡潔に表すための記号である．ST および SW はそれぞれ Suﬃx-Tree アルゴリ
ズム，Smith-Waterman アルゴリズムを表す．なお，Suﬃx-

Tree アルゴリズムを用いた場合と Smith-Waterman を用いた場合で同様の傾向が得られたので，ここでは Suﬃx-Tree
アルゴリズムを用いた場合のみを述べる．
ファイル単位，メソッド単位で検出した場合（検出 A，多いか．
粗粒度な検出手法および細粒度な検出手法と比較

検出 B）と全粒度で検出した場合（検出 H）を比較する

して，多粒度な検出手法は分析しやすいクローンの検と，全粒度で検出した場合は検出時間が長かった（7.3 秒，

出結果を生成できるか．

32.8 秒 →3,094.6 秒）．また，コード片単位で検出した場

項目 3

これらの項目を調査するために，各粒度における検出のオ合（検出 C）と全粒度で検出した場合（検出 H）を比較す

ン・オフを切り替えたすべての場合において，Decrescendo

ると，全粒度で検出した場合は検出速度が大幅に向上しを実行した．コード片単位の検出を行う場合，Suﬃx-Tree

た（62,569.0 秒 →3,094.6 秒）．表 3 に各処理に要した時間

アルゴリズムと Smith-Waterman アルゴリズムを用いた 2を示す．全粒度で検出した場合は，STEP-5 から STEP-7

通りにおいて，Decrescendo を実行した．

（メソッドクローンの検出）に要する時間が若干短くなっ

5.3 実験環境出されたファイルが除外され，メソッド単位の検出時の入た（31.7 秒 →24.0 秒）．これはファイルクローンとして検本実験で用いた計算機の CPU は 2.9 GHz Intel Xeon

力ファイル数が減少したためである．

CPU（16 プロセッサ）であり，メモリサイズは 352 GB で最も注目すべきは，STEP-10（コード片クローンの検出）ある．また，実験対象のソフトウェアや検出結果を出力すに要した時間である．この処理が最も実行時間が減少してるためのデータベースはすべて SSD 上に配置した．

いる（62,508.9 秒 →2,980.0 秒）．全粒度で検出した場合に実行時間が約 1/20 倍になっている．どちらの場合も検出*2

本論文では Suﬃx-Tree アルゴリズムを用いたクローン検出および Smith-Waterman アルゴリズムを用いたクローン検出の手順は記述しない．それらは文献 [6], [18] のクローン検出の手順と同様である．

c 2018 Information Processing Society of Japan

時間の大半を STEP-10 に要しているため，重複ファイルと重複メソッドを除外することが Suﬃx-Tree アルゴリズ*3

http://svn.apache.org/viewvc/

1198

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

表 2

クローンの検出結果

Table 2 Clone detection results.
検出 ID

粒度
ファイル

検出時間 [s]検出されたクローンペア数

メソッド

コード片 ST

コード片 SW

ファイル

メソッド

コード片

合計

A

◦

-

-

-

11,029--11,029

7.3

B

-

◦

-

-

-

49,446-49,446

32.8

C

-

-

◦

-

-

-

1,637,597

1,637,597

62,569.0

D

-

-

-

◦

-

-

446,442446,442

130,367.1

E

◦

◦

-

-

11,02944,168-55,197

32.3

F

◦

-

◦

-

11,029-1,632,319

1,644,348

46,183.2

G

-

◦

◦

-

-

49,446

1,588,151

1,637,597

1,885.7

H

◦

◦

◦

-

11,02944,168

1,588,151

1,643,348

3,094.6

I

◦

-

-

◦

11,029-441,164

452,193

109,717.1

J

-

◦

-

◦

-

49,446396,996446,442

13,013.6

K

◦

◦

-

◦

11,02944,168396,996452,193

13,036.7

表 3 各処理に要した時間（Suﬃx-Tree アルゴリズム）

ソッドクローンが検出される [9], [12], [17]．そのような場

Table 3 Detection time (Suﬃx-Tree algorithm).

合において，多粒度な検出手法はコード片クローンを検出

全粒度 [s]

コード片 [s]STEP-1 から STEP-3

6.7

6.4

STEP-4

4.0-

STEP-5 から STEP-7

24.0

31.7

STEP-8 および STEP-9

1.2-

STEP-102,980.0

62,508.9

STEP-11

68.5

16.6

処理

するための時間を短縮することに有効であるといえる．

5.6 項目 2 の調査
項目 2 についても，Suﬃx-Tree アルゴリズムを用いた場
合と Smith-Waterman アルゴリズムを用いた場合で同様の傾向であったため，Suﬃx-Tree アルゴリズムを用いた場合のみについて述べる．
ファイル単位およびメソッド単位で検出した場合（検出ムを用いたマッチング処理に要する時間を短縮し，結果

A，検出 B）と全粒度で検出した場合（検出 H）を比較すとして検出速度の向上に有効であることが分かる．また，ると，全粒度で検出した場合は検出数が多かった（11,029

STEP-11 に要した時間を時間を比較すると，全粒度で検出個，49,446 個 →1,643,348 個）．また，コード片単位で検出した場合は後処理を行うため実行時間が長くなっている．

した場合（検出 C）と全粒度で検出した場合（検出 H）をしかし，その差は全体の検出時間と比較するとわずかな時比較すると，検出数にあまり変化はなかった（1,637,597 個間である．

→1,643,348 個）．

さらに，ファイルおよびコード片単位で検出した場合（検表 2 には，直感とは反した検出結果になっている数値が出 F）と全粒度で検出した場合（検出 H）を比較すると，メある．たとえば，検出 C において検出されたクローンペ

ソッドクローンを除外してコード片クローンの検出を行う

ア数は検出 H において検出されたクローンペア数よりもことが有効であることが分かる（46,183.2 秒 →3,094.6 秒）．

少ない．この理由は，4 章において記述しているコード片

なお，表 3 のコード片の列には，STEP-1 から STEP-3単位のクローン検出の実装方針によるものである．コード

および STEP-5 から STEP-7 についての実行時間も含まれ片単位のクローンは各メソッド内でのみ検出処理が行われている．これらの処理には，コード片単位のクローン検出る．そのため，たとえ重複しているコードでもそれを含むのみを行う場合には必要のないものも含まれている．ツー

メソッドが最小クローン長よりも小さい場合には，それら

ルの実装上の都合により，コード片単位の検出の場合もそは検出されない．一方で多粒度での検出の場合は，そのよのような処理を行っているが，検出時間全体に対してこれ

うなメソッドであっても，それを含むファイル全体が重複らの処理に必要な時間は非常に短いため，問題はないと著していればクローンとして検出される．この理由により，者らは考えている．

多粒度による検出数が細粒度による検出数よりも多くなる

項目 1 の結論
これらの結果から多粒度な検出手法は粗粒度な検出手法場合が存在する．
項目 2 の結論よりも検出時間が長いという結論を得た．しかし，細粒度

粗粒度な検出手法と比較して多粒度な検出手法は検出数な検出手法と比較して，多粒度な検出手法が高速にクローが多いということを示した．また，多粒度な検出手法は細ンを検出できることを示した．大規模なソースコードの集粒度な検出手法と同等数のクローンを検出することを示

合に対してクローン検出を行う場合，多量のファイル・メ

した．

c 2018 Information Processing Society of Japan

1199

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

図 8

分析しやすい検出結果の例

Fig. 8 Example of preferable clones.

5.7 項目 3 の調査行うため，これら 2 つのクラスはファイルクローンである

粗粒度な検出手法および細粒度な検出手法と比較して，ことが明らかになり，より容易にリファクタリングが可能

多粒度な検出手法が分析しやすいクローンの検出結果を生かどうかを判断できる．多粒度な検出手法によって，5,278成した例を以下に 3 つ示す．

1 つ目の例を図 8 (a) に示す．メソッド単位のみで検出

個のメソッドクローンペアが 2,345 個のファイルクローン
ペアとして検出されたことを確認した．

した場合，write，read，getFields メソッドがそれぞれ異な

2 つ目の例を図 8 (b) に示す．メソッド単位のみやコード

るクローンペアとして検出されていた．メソッドクローン

片単位のみで検出した場合，getName，getIfcName，get-

ペアを 1 つ 1 つ確認することで，これらのクラス内のすべ

Service メソッドはクローンとして検出されなかった．こてのメソッドがクローンになっており，2 つのクラスを 1の理由は，2 つのクラス内の全メソッドが最小クローン長

つのクラスに集約するリファクタリングが可能であると判未満のメソッドであったためである．しかし，メソッド単断できる．しかし，複数のメソッドクローンペアとしてこ位の検出に加えてファイル単位でも検出を行うことで，これら 2 つのクラスの重複が検出されるため，リファクタリ

れら 2 つのクラスがクローンとして検出された．これらのングが可能かどうかの判断に時間を要する．多粒度な検出クラスがファイルクローンとして検出されたことで，2 つ手法では，メソッド単位の検出前にファイル単位の検出をのクラスを 1 つのクラスに集約するリファクタリングがで

c 2018 Information Processing Society of Japan


1200

情報処理学会論文誌

Vol.59 No.4 1192–1202 (Apr. 2018)

きる可能性がある．そのため，メソッド単位のみのクロー

出手法を粗粒度な検出手法および細粒度な検出手法と比較

ン検出では気づくことができないリファクタリングが可能した．

となる．多粒度な検出手法によって，8,684 個のファイルク

比較の結果，以下の項目を示した．

ローンがこのようなケースで検出されたことを確認した．

• 細粒度な検出手法と比較して，多粒度な検出手法が高3 つ目の例を図 8 (c) に示す．ファイル単位のみで検出した場合，2 つのクラスはクローンとして検出されなかった．

速にクローンを検出できる．

• 粗粒度な検出手法と比較して，多粒度な検出手法がク

しかし，メソッド単位のクローン検出を行うことで，get-

ローンの検出数が多い．

ColumnValues メソッドが検出された．DatabaseSelectAc-• 粗粒度な検出手法および細粒度な検出手法と比較しtion と DatabaseDeleteAction クラスは DatabaseAction クて，多粒度な検出手法が分析しやすいクローンの検出

ラスを継承しており，getColumnValues メソッドに対して結果を生成できる．

メソッド引き上げリファクタリングができる可能性がある．

今後はまず，被験者実験を行い多粒度な検出手法が生成以上のことから，多粒度な検出手法は，単一の粒度でした検出結果の分析のしやすさをさらに評価する予定であは気づくことができないリファクタリングが可能となる．

る．検出において内部クラスを考慮するなどのさらにより

ファイル，メソッド，コード片クローンに対して適用でき

良い検出が行えるよう拡張することも考えられる．また，るリファクタリングは異なるため，検出されたクローンのJava 以外の言語への拡張やその他のクローン検出ツールと粒度が明確になることで，どのリファクタリングを適用での比較を行う予定である．さらには，より大規模なソース

きるかどうかをより容易に判断できる．

コードの集合に対して適用し，ライブラリの候補となるク

多数のクローンが検出されたため，すべてのクローンをローンや修正漏れの発見も試みる．

確認はできてはいないが，目視で確認した範囲では，多粒謝辞 本研究は，科学研究費補助金基盤研究（S）（課題番

度による検出が不利になると思われるクローンはなかった．

号：25220003）および基盤研究（B）（課題番号：17H01725）

項目 3 の結論の助成を得て行われた．

粗粒度な検出手法および細粒度な検出手法と比較して，多粒度な検出手法が分析しやすいクローンの検出結果を生

参考文献

成できることを示した．

[1]

6. 実験結果の妥当性について
対象ソフトウェア 本論文では，Java で記述された 84 個

[2]のソフトウェアを対象にしている．しかし，他のソフ
トウェアに対して実装したツールを実行した場合，本論文で得られた結果と異なる可能性がある．

[3]

ハッシュ値の衝突 本論文では，ファイル，メソッド，文を構成する文字列からハッシュ値を算出している*4 ．
ハッシュ値の衝突が発生した場合，誤ったクローン[4]が検出される可能性がある．しかし，本論文では 128
ビットのハッシュ値を出力する MD5 を用いており，
ハッシュ値の衝突の可能性は十分に低い．

[5]

正規化の方法 本論文では，3 章で述べた正規化を行っている．正規化により，Type-2 クローンの検出が可能になるが，誤検出も増える．現時点では，正規化により[6]

どの程度の誤検出が増えるのかは確認できていない．

7. おわりに[7]

本論文では，粗粒度から細粒度へ段階的に（多粒度で）クローンを検出する手法を提案した．また，提案手法をク
ローン検出ツール Decrescendo として実装し，複数のオー
プンソースソフトウェアに適用した．そして，多粒度な検*4文を構成する文字列から算出したハッシュ値は，Smith-Waterman
アルゴリズムで利用している．

c 2018 Information Processing Society of Japan[8]

Barbour, L., Khomh, F. and Zou, Y.: An empirical studyof faults in late propagation clone genealogies, Journal of Software: Evolution and Process, Vol.25, No.11,
pp.1139–1165 (2013).
Bellon, S., Koschke, R., Antoniol, G., Krinke, J. andMerlo, E.: Comparison and evaluation of clone detection
tools, IEEE Trans. Softw. Eng., Vol.33, No.9, pp.577–
591 (2007).
Choi, E., Yoshida, N., Higo, Y. and Inoue, K.: Proposing
and Evaluating Clone Detection Approaches with Preprocessing Input Source Files, IEICE Trans. Information and Systems, Vol.98, No.2, pp.325–333 (2015).
Deepali, Gupta, A. and Batra, C.: Hybrid approach for
Detecting Code Clone by Metric and Token based comparison, International Journal of Advanced Research in
Computer Science, Vol.7, No.6, pp.297–302 (2016).
Higo, Y. and Kusumoto, S.: How Should We Measure
Functional Sameness from Program Source Code? An
Exploratory Study on Java Methods, Proc. 22nd International Symposium on the Foundations of Software
Engineering, pp.294–305 (2014).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: A
multilinguistic token-based code clone detection system
for large scale source code, IEEE Trans. Softw. Eng.,
Vol.28, No.7, pp.654–670 (2002).
Kim, M., Sazawal, V., Notkin, D. and Murphy, G.: An
empirical study of code clone genealogies, Proc. ACM
SIGSOFT Software Engineering Notes, Vol.30, No.5,
pp.187–196 (2005).
Kodhai, E., Kanmani, S., Kamatchi, A., Radhika, R. andSaranya, B.V.: Detection of Type-1 and Type-2 CodeClones Using Textual Analysis and Metrics, Proc. 2010
International Conference on Recent Trends in Information, Telecommunication and Computing, pp.241–243

1201

情報処理学会論文誌

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Vol.59 No.4 1192–1202 (Apr. 2018)(2010).
Ossher, J., Sajnani, H. and Lopes, C.: File cloning inopen source java projects: The good, the bad, and theugly, Proc. 27th International Conference on Software
Maintenance, pp.283–292 (2011).
Rattan, D., Bhatia, R. and Singh, M.: Software clone detection: A systematic review, Information and Software
Technology, Vol.55, No.7, pp.1165–1199 (2013).
Roy, C.K., Cordy, J.R. and Koschke, R.: Comparisonand evaluation of code clone detection techniques andtools: A qualitative approach, Science of Computer Programming, Vol.74, No.7, pp.470–495 (2009).
Sasaki, Y., Yamamoto, T., Hayase, Y. and Inoue, K.:
Finding ﬁle clones in FreeBSD ports collection, Proc. 7th
Working Conference on Mining Software Repositories,
pp.102–105 (2010).
Svajlenko, J. and Roy, C.K.: Evaluating clone detection tools with BigCloneBench, Proc. 31st International
Conference on Software Maintenance and Evolution,
pp.131–140 (2015).
Weissgerber, P. and Diehl, S.: Identifying refactorings
from source-code changes, Proc. 21st IEEE/ACM International Conference on Automated Software Engineering, pp.231–240 (2006).
幸 佑亮，肥後芳樹，楠本真二：多粒度コードクローン検出手法の提案，電子情報通信学会技術研究報告，Vol.116,
No.277, pp.73–78 (2016).
神谷年洋，肥後芳樹，吉田則裕：コードクローン検出技術の展開，コンピュータソフトウェア，Vol.28, No.3,
pp.29–42 (2011).
石原知也，堀田圭佑，肥後芳樹，井垣 宏，楠本真二：
大規模なソフトウェア群を対象とするメソッド単位でのコードクローン検出，情報処理学会論文誌，Vol.54, No.2,
pp.835–844 (2013).
村上寛明，堀田圭佑，肥後芳樹，井垣 宏，楠本真二：Smithwaterman アルゴリズムを利用したギャップを含むコー
ドクローン検出，情報処理学会論文誌，Vol.55, No.2,
pp.981–993 (2014).
肥後芳樹，楠本真二，井上克郎：コードクローン検出とその関連技術，電子情報通信学会論文誌 D，Vol.91, No.6,
pp.1465–1481 (2008).
堀田圭佑，楊 嘉晨，肥後芳樹，楠本真二：粗粒度なコー
ドクローン検出手法の精度に関する調査，情報処理学会
論文誌，Vol.56, No.2, pp.580–592 (2015).

肥後 芳樹 （正会員）
2002 年大阪大学基礎工学部情報科学科中退．2006 年同大学大学院博士後期課程修了．2007 年同大学院情報科
学研究科コンピュータサイエンス専攻
助教．2015 年同准教授．博士（情報科学）．ソースコード分析，特にコー
ドクローン分析，リファクタリング支援およびソフトウェ
アリポジトリマイニングに関する研究に従事．電子情報通信学会，日本ソフトウェア科学会，IEEE 各会員．

楠本 真二 （正会員）
1988 年 大 阪 大 学 基 礎 工 学 部 卒 業 ．
1991 年同大学大学院博士課程中退．
同年同大学基礎工学部助手．1996 年
同講師．1999 年同助教授．2002 年同大学大学院情報科学研究科助教授．

2005 年同教授．博士（工学）．ソフト
ウェアの生産性や品質の定量的評価に関する研究に従事．
電子情報通信学会，IEEE，IFPUG 各会員．

幸 佑亮
2015 年大阪大学基礎工学部情報科学科中退．2017 年同大学大学院博士前期課程修了．在学時，コードクローン
分析やリポジトリマイニングに関する研究に従事．

c 2018 Information Processing Society of Japan

1202