९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

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

肥後 芳樹1

楠本 真二1

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

1. はじめにの向上の観点から有益であり，先行研究においてそのようなクローンの存在が確認されている．

コードクローン（以下，クローン）とは，ソースコード

既存のクローン検出手法は，ファイル単位やコード片単中に存在する互いに同一，あるいは類似したコード片であ位など単一の粒度でのみクローンを検出している．既存のる．クローンの主な発生要因はコピーアンドペーストであクローン検出手法は，大きく分けて以下の 2 つの検出手法

る [8], [9], [13], [16]．一般的に，クローンはソフトウェアに分類できる [17]．

の保守性を低下させる原因になるとされている．例えば，粗粒度な検出手法 類似したクラス・メソッド・ブロック

あるコード片にバグが存在した場合，そのクローンに対しをクローンとして検出する手法．

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

細粒度な検出手法 任意のコード片をクローンとして検出討する必要がある．そのため，クローンがソフトウェア中する手法．細粒度な検出手法はクラス・メソッド・ブにどの程度存在しているか，及びどこに存在しているかをロックの一部が類似するコード片をクローンとして検理解することはソフトウェア保守の観点から重要であり，出できる．

これまでに多くのクローン検出ツールが提案されている．

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

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

単位，メソッド単位，ブロック単位，およびコード片単位

ウェアからなる大規模なソースコードの集合に対してクの検出手法の特徴を図 1 に挙げる．

ローン検出ツールを適用し，ライブラリの候補や修正漏れ検出に要する時間 検出の粒度が粗いほど検出時間が短く，を検出する研究が行われている [14]．複数のソフトウェア

検出の粒度が細かいほど検出時間が長い．ソースコーに存在する同一の処理をライブラリ化することは開発効率

ドの行数，ソースコード中の字句数，ソースコードを

1

抽象構文木で表現した場合の頂点数はソースコード中大阪大学 大学院情報科学研究科 コンピュータサイエンス専攻〒 565-0871 大阪府吹田市山田丘 1-5©2017 Information Processing Society of Japan

のクラス数，メソッド数，ブロック数と比較して多い．

5

९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

検出に必要な時間長

短
メソッド単位

ファイル単位 

    







ブロック単位 

    





    









コード片単位     





 







多

少
検出されるクローンの数

図 1

各検出手法の特徴

そのため，粗粒度な検出手法と比較して細粒度な検出

A.javaB.javaC.javaD.javaE.javaF.java

手法は検出時間が長い．
検出可能なクローンの数

検出の粒度が粗いほど，検出可
ハッシュ値に基づくクラスタリング

能なクローンの数が少なく，検出の粒度が細かいほど，検出可能なクローンの数が多い．粗粒度な検出手法はA.javaC.javaE.javaB.javaD.javaF.java

ファイル単位，メソッド単位，もしくはブロック単位

7575

7575

7575

6047

1430

1430

でクローンを検出するが，それらの内部の一部のみがコード片クローン検出対象ファイルの選出

類似しているコード片をクローンとして検出できな
い．そのため，細粒度な検出手法と比較して粗粒度な

A.javaC.javaE.javaB.javaD.javaF.java

検出手法は検出可能なクローンの数が少ない．
本論文では，粗粒度な検出手法と細粒度な検出手法のデメリットを低減するために，粗粒度から細粒度へ段階的に

図 2

ファイルのハッシュ値に基づいたクラスタリング（多粒度で）クローンを検出する手法を提案する．具体的にはファイル単位・メソッド単位・コード片単位の順にクローンを検出する．段階的にクローンを検出する過程において，ある粒度でクローンとして検出されたコードをそれよりも細粒度なクローンの検出対象から除外していくこと
で，細粒度な検出手法と比較してより高速に検出できる．
また，粗粒度で検出できるクローンは粗粒度で検出することによって，より有益なクローンの検出結果となる．例
えば，複数のメソッド単位のクローンを 1 つのファイル単位のクローンとして検出できる．これによって，検出されるクローンの数が少なくなり，クローンの分析に要する時間を短縮できる．特にクローンの情報をリファクタリング
において利用する場合に有効であると著者らは考えている．また，提案手法は細粒度でも検出を行うためクローンの見逃しが粗粒度の検出に比べて少ない．このように，提案手法は粗粒度な検出手法や細粒度な検出手法と比較してより分析しやすいクローンの検出結果を生成できる．
提案手法をクローン検出ツール Decrescendo として実装し，複数のオープンソースソフトウェアに適用した．そして，提案手法を粗粒度な検出手法および細粒度な検出手法と比較した．

©2017 Information Processing Society of Japan

本論文の貢献は以下の通りである．

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

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

• 細粒度な検出手法および細粒度な検出手法と比較して，多粒度な検出手法が分析しやすいクローンの検出
結果を生成できることを示した．
以降，2 章では本研究の位置づけについて述べる．3 章
では提案手法について述べる．4 章では実装したツールの詳細について述べる．5 章では評価実験について述べる．6
章では実験の妥当性について述べる．最後に，7 章で本論文をまとめる．

2. 本研究の位置づけ
コード片単位のクローン検出を行う前にファイルのハッシュ値に基づいたクラスタリングを行う，という Choi らの先行研究がある [3]．このクラスタリングはコード片単6९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

コード片単位多入力
A.javaChoi ら
の研究

多粒度な
検出手法

C.javaA.javaB.javaC.javaD.javaE.javaF.javaファイル
クローン検出
D.java検
出数

B.javaE.javaF.javaブロック単位
メソッド単位
各ファイルクローングループにおいて1つのファイルのみを残し，他のファイルはメソッドクローンの検出対象から除外

ファイル単位
A.javaB.javaC.javaA.java

少
短

検出時間

図 3

メソッド
クローン検出長
D.javaE.javaF.java

本研究の位置づけ

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

methodA2

B.javamethodB1

B.javamethodB2

D.javamethodD1

D.javamethodD2

各メソッドクローングループにおいて1つのメソッドのみを残し，他のファイルはコード片クローンの検出対象から除外

イルのハッシュ値に基づいたクラスタリングの例を図 2 にA.java示す．ファイル中の数値はハッシュ値を表しており，ファイル外の枠はハッシュ値が等しいファイルのグループを表す．クラスタリング後，各グループから 1 つのファイルを選択する．そして，選択されたファイルの集合に対してク

methodA1

A.javamethodA1

A.javamethodA2

B.javamethodB1

B.javamethodB2

D.javamethodD1

D.java

コード片
クローン検出

A.javaB.javaD.javamethodD2
クローンの出力

出力

ファイルクローン {A.java, C.java, E.java}, {D.java, F.java}

ローン検出を行う．このクラスタリングは，ファイル単位

メソッドクローン {methodB1, methodB2, methodD2, methodF2}
コード片クローン {code in methodB1, code in methodD1, code in methodF1}のクローン検出と同一である．

図 4

本論文の提案手法は，ファイル単位のクローンに加えて，提案手法の概要

メソッド単位のクローンも除外する．これによって，既存研究より効果的にコード片単位のクローン検出時間を短縮できる．さらに，本提案手法は検出した各クローンに粒度の情報を付加する．これにより，検出した各クローンの粒    

  
 




度が明らかになり，先行研究よりも分析しやすいクローンの検出結果を生成できる．
既存のクローン検出手法と本論文で提案する多粒度な検ファイル  
クローン  


  






後処理で
追加



   
 
  






メソッド
クローン





出手法の位置づけを図 3 に示す．粗粒度な検出手法（ファイル単位・メソッド単位・ブロック単位の検出手法）は，

図 5

後処理の例

検出に要する時間が短く，検出されるクローンの数が少ない．一方，細粒度な検出手法（コード片単位の検出手法）

でクローンとして検出されたコードをそれよりも細粒度なは，検出時間が長く，検出数が多い．そこで，本論文で提クローンの検出対象から除外していく．以降，ファイル単

案する多粒度な検出手法は，検出時間を短く，かつ検出数位のクローンをファイルクローン，メソッド単位のクローを多くすることを目的とする．また，本論文の提案手法は，

ンをメソッドクローン，コード片単位のクローンをコード

ファイル単位のクローンに加えて，メソッド単位のクロー

片クローンと呼ぶ．

ンも検出する．13,000 個のソフトウェア群に存在するメ
ソッド集合のうち約 49%がメソッドクローンであったとい

現在のところ，提案手法ではブロック単位でのクローン検出を行わない．その理由は以下の 2 つである．

う研究報告がある [14]．複数のソフトウェア間にメソッド• ブロックの大きさはメソッドよりも小さく，ブロッククローンが多数存在するため，メソッド単位の検出の後に単位の検出を導入することによる高速化が限定的と考

コード片単位の検出を行うことで，コード片単位の検出にえたため．

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

3. 提案手法• コードクローンは 1 つのブロック内で閉じているとは限らないため，検出の処理が煩雑になりすぎてしまうと考えたため．

提案手法は対象ソースコードに対して粗粒度から細粒度へ段階的に（多粒度で）クローンを検出する．具体的には

3.1 検出手順

ファイル単位，メソッド単位，コード片単位の順にクロー

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

ンを検出する．段階的に検出する過程において，ある粒度する過程において，ファイル単位の検出でクローンとして©2017 Information Processing Society of Japan

7

९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

検出されたファイルを，次のメソッド単位の検出の入力から除外する．図 4 では，ファイル単位の検出において，以下の 2 つのファイルクローングループが検出されている．

• A.java, C.java, F.java

メソッド単位のみのクローン検出ではファイルFとファイルDがファイルクローンになっていることがわからない       







• D.java, E.java  
 




次のメソッド単位の検出では各ファイルクローングループ
から 1 つのファイルを選ぶ（各グループ内の他のファイル   
 
  


  


はメソッドクローンの検出対象から除外する）．
(a) メソッドクローンのみの検出選択されたファイルとファイルクローンになっていない
ファイル内に存在しているメソッドに対してメソッドク
ローンの検出処理が適用される．この例では，メソッドク
ローン検出処理により以下の 3 つのメソッドがクローンとして検出されている．

• methodB1, methodB2, methodD2

ファイル単位のクローン検出ではファイルBのメソッドがファイルDおよびファイルFのメソッドがクローンになっていることがわからない          

 




  
 




このあと除外したファイルに対するメソッドクローンの検出漏れを防ぐための後処理が行われる．具体的には，メソッ
ドクローン methodD2 が存在している D.java は F.java と  





ファイルクローンであるため，F.java に含まれる methodF2  


(b) ファイルクローンのみの検出

もこのメソッドクローングループに加える（図 5）
．結果と

図 6

して，以下の 4 つのメソッドが 1 つのメソッドクローング

単粒度におけるクローン検出例

ループとして検出される．

• methodB1, methodB2, methodD2, methodF2• D.java, F.java

次のコード片単位の検出では，各メソッドクローング• methodB1, methodB2, methodD2, methodF2

ループから 1 つのメソッドを選び，メソッドクローンとこのように，多粒度で検出を行うことにより，小さいク

なっていないメソッドと共にコード片クローン検出処理がローンを見逃すことなく，重複コードはできるだけ大きな適用される．コード片クローン検出後はメソッドクローン

クローンとして検出できる．

検出後の後処理と同様に，除外したメソッド内に含まれる

4. 実装

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

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

Decrescendo について述べる．なお，このツールにおい
3.2 より理解しやすい検出結果の出力て，メソッドクローン検出部分は著者らの既存研究 [14] と複数のクローンペアを 1 つのクローンペアとしてまとめ同一であり，提案手法のファイルクローン検出部分は既存て検出することでより理解しやすいクローンの検出結果を研究 [14] の検出法をファイル単位に変更したものである．

得ることができる．例を図 6 に挙げる．この例ではメソッ

コード片クローン検出については Suﬃx-Tree アルゴリズム

ド単位のみで検出した場合，3 つファイルからは以下の 2および Smith-Waterman アルゴリズムを用いて実装した．

つのメソッドクローングループが検出される．

どちらのアルゴリズムもクローン検出において有用なこと• methodD1, methodF1• methodB1, methodB2, methodD2, methodF2が示されている [5], [15]．

Decrescendo の入力は以下の通りである．

この検出結果からは，D.java と F.java がファイルクロー• Java ソースファイル群ンとなっていることがわかりづらい．

• 最小クローン長

ファイル単位のみで検出した場合，以下のファイルク
ローングループが検出される．

• D.java, F.java• 最大ギャップ率
最小クローン長は検出するクローンの最小の大きさを指定するためのものである．最小クローン長に小さな値を指この結果からは，B.java が D.java および F.java とメソッ

定すればより多くのクローンを検出できるが，検出結果にドクローンを共有していることがわからない．

は多くの誤検出が混じる．大きな値を指定すれば誤検出を多粒度で検出することで以下のクローングループが検出される．

減らせるが見逃すクローンも増えてしまう．
最大ギャップ率とは，Smith-Waterman アルゴリズムを利用する場合にのみ指定する値であり，クローンとして許©2017 Information Processing Society of Japan

8९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

して，高速に検出可能なためである [15]．

  

以降，本章では Decrescendo の処理の流れを説明する．

コピーアンドペーストによる再利用

必要に応じて図 4 を参照されたい． Decrescendo の最初の
変数名の変更処理はファイルクローンの検出である．

文の挿入







 







Type-1クローン

Type-2クローン

 






文の変更

文の削除
 








Type-3クローン

図 7

 



ギャップ

クローンのタイプ

STEP-1(ファイルの正規化) 入力として与えられた各Java ファイルに対して以下に示す正規化を行う．
• インデント，改行，コメント，import 文，修飾子を削除• 識別子名およびリテラルを特殊文字に置換
この処理によって，2 つのファイル間でコーディング
スタイルが異なる場合や識別子名またはリテラルが異なる場合でも，その 2 つのファイルをクローンとして容するギャップ（不一致部分）の割合を表す．最大ギャッ検出可能になる．

プ率を大きくすればより多くのクローンを検出できるが検STEP-2(ファイルフィルタリング) 正規化後のファイル

出結果には多くの誤検出が含まれてしまう．小さい値を設に含まれる字句数が最小クローン長に満たない場合，

定すれば誤検出を減らせるが見逃してしまうクローンが増検出対象から除外する．このフィルタリングを行うこえてしまう．

とによりクローンが検出されることのないファイルに出力はクローンペアの位置情報，粒度（ファイル・メソッ

対するこれ以降の処理を省くことができる．

ド・コード片），およびタイプ（Type-1・Type-2・Type-3）

STEP-3(ファイルハッシュ値の計算) 各ファイルに対しである．クローンのタイプを図 7 を用いて説明する．例てハッシュ値を算出する．ハッシュ値が等しいファイ

えば，コピーアンドペーストしただけのコードであれば，

ルがファイルクローンとなる．現在の実装ではハッ

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

シュ値の計算に MD5 を利用している．

ローンとなる．変数名を変更した場合には字句単位の差異

STEP-4(ファイルグループの生成と出力) ハッシュ値がが生じ，Type-2 クローンとなる．文の追加・削除・変更を同じファイルでグループを作る．2 つ以上のファイル行った場合には字句単位よりも大きな差異（ギャップ）がを含むグループがファイルクローンとして検出される．

生じ，Type-3 クローンとなる．

ファイルクローンの検出の後は，メソッドクローンの検出検出するクローンのタイプは以下の通りである．

を行う．

• ファイル単位およびメソッド単位では，Type-1 およSTEP-5(メソッドの切り出し) STEP-4 において生成さび Type-2 のクローンが検出される．

れた各グループからファイルを 1 つ無作為に選択す• Suﬃx-Tree アルゴリズムを用いてコード片クローンのる．ファイルが 1 つだけ含まれるグループも対象であ検出を行った場合は，Type-1 および Type-2 のクローる．選択された各ファイルに含まれるメソッドを抽出

ンが検出される．

する．図 4 では，A.java，B.java，および D.java が選• Smith-Waterman アルゴリズムを用いてコード片ク
ローンを検出した場合は，Type-1，Type-2，およびType-3 のクローンが検出される．

択されている．

STEP-6(メソッドフィルタリング) メソッドに含まれる字句数が最小クローン長に満たない場合，検出対象か

コード片単位の検出手法を 2 通りの手法で実装した理ら除外する．このフィルタリングを行うことにより，

由は，細粒度な検出手法のうち，Type-2 までのクローン

クローンが検出されることのないメソッドに対するこを検出する手法と Type-3 までのクローンを検出する手法

れ以降の処理を省くことができる．

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

STEP-7(メソッドハッシュ値の計算) 各メソッドに対し数の面で有用かどうかを評価するためである．Type-2 まてハッシュ値を計算する．ハッシュ値が等しいメソッ

でのクローンを検出する手法の中で Suﬃx-Tree アルゴリ

ドがメソッドクローンとなる．ファイルハッチュと同ズムを採用した理由は，Suﬃx-Tree アルゴリズムが用いらじく MD5 を用いて計算する．

れているクローン検出ツールが代表的な字句単位の検出

STEP-8(メソッドグループの生成) ハッシュ値が同じメ

ツールであり，様々な企業や研究で採用されているためでソッドでグループを作る．2 つ以上のメソッドを含む

ある [1], [6], [12]．Type-3 までのクローンを検出する手法

グループがメソッドクローンとして検出される．図 4の中で Smith-Waterman アルゴリズムを採用した理由は，

では，methodB1，methodB2，および methodD2 がメSmith-Waterman アルゴリズムが応用されているクローン

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

検出ツールがその他の Type-3 クローン検出ツールと比較©2017 Information Processing Society of Japan

9९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

STEP-9(メソッドクローン検出の後処理と出力)

項目 1 粗粒度な検出手法および細粒度な検出手法と比較

STEP-4 で選択されなかったファイル（図 4 における

して，多粒度な検出手法は検出時間が短いか．

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

項目 2 粗粒度な検出手法および細粒度な検出手法と比較

クローンを取りこぼさないための処理を行う．1 つのして，多粒度な検出手法は検出されるクローンの数が多いか．

グループを構成する各ファイルはその内部にメソッド
クローンを持つ．この性質を利用して，STEP-8 で検項目 3 粗粒度な検出手法および細粒度な検出手法と比較出されたメソッドクローンが 2 つ以上のファイルからして，多粒度な検出手法は分析しやすいクローンの検なるグループから選択されたメソッドである場合に出結果を生成できるか．

は，そのメソッドクローンが同じグループに含まれる

これらの項目を調査するために，各粒度における検出の他のファイルのメソッドに対しても存在しているとすオン・オフを切り替えた全ての場合において，Decrescendoる．図 4 では，この処理により，STEP-8 で検出されを実行した．コード片単位の検出を行う場合，Suﬃx-Tree

たメソッドクローンに，methodF2 が加えられている．

アルゴリズムと Smith-Waterman アルゴリズムを用いた 2

メソッドクローンを検出した後は，コード片クローンの検通りにおいて，Decrescendo を実行した．

出を行う．

STEP-10(コード片クローンの検出) STEP-8 に お い て

5.3 実験環境生成された各グループからメソッドを 1 つ無作為

本実験で用いた計算機の CPU は 2.9GHz Intel Xeonに選択する．メソッドが 1 つだけ含まれるグループもCPU（16 プロセッサ）であり，メモリサイズは 352GB で対象である．選択された各メソッドに対して，Suﬃx-ある．また，実験対象のソフトウェアや検出結果を出力す

Tree もしくは Smith-Waterman アルゴリズムを用いるためのデータベースはすべて SSD 上に配置した．

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

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

STEP11(コード片クローン検出の後処理と出力)
STEP-4 で選択されなかったファイルや STEP-10 でアは Apache Software Foundation のリポジトリ*2 から取得

選択されなかったメソッドに含まれるコード片クロー

した 2013/10/31 時点の 84 個のソフトウェアである．バー

ンを取りこぼさないための処理を行う．処理内容はジョンが異なる同一ソフトウェア間からのクローン検出

STEP-9 と同様である．

を避けるために trunk 以下のファイルのみを検出対象とす

なお，Decrescendo は，設定によって各粒度における検る．これらのソフトウェアを対象とした理由は，著者らの出のオン・オフを切り替えることができる．

先行研究 [4] において利用されたデータセットであり，テ5. 実験

ストコードと自動生成コードが取り除かれているためであ

5.1 準備

ソフトウェアに存在する共通処理のライブラリ化に対してる．テストコードと自動生成コードは流用の特定や複数のDecrescendo を複数のオープンソースソフトウェアに対は有用でなく，クローンとして検出する必要性がない．

して適用し，多粒度な検出手法と粗粒度な検出手法および細粒度な検出手法と比較した．今回の実験では，最小ク5.5 項目 1 の調査
表 2 にクローンの検出結果を示す．各粒度の ◦ はその粒ローン長を 50 字句，最大ギャップ率を 0.3 としている．これらの値は先行研究 [2][11] を参考にしている．

度の検出が行われたことを表す．検出 ID は，本節の以降でどの検出について言及しているのかを簡潔に表すための記号である．ST および SW はそれぞれ Suﬃx-Tree アルゴリ

5.2 調査項目

ズム，Smith-Waterman アルゴリズムを表す．なお，Suﬃx-

本実験の調査項目を以下に示す．

Tree アルゴリズムを用いた場合と Smith-Waterman を用い
表 1

対象ソフトウェア

84

ソフトウェア数
ファイル数

66,724

メソッド数628,219LOC*1た場合で同様の傾向が得られたので，ここでは Suﬃx-Tree

11,545,556

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

©2017 Information Processing Society of Japan

アルゴリズムを用いた場合のみを述べる．
ファイル単位，メソッド単位で検出した場合（検出 A，
検出 B）と全粒度で検出した場合（検出 H）を比較すると，全粒度で検出した場合は検出時間が長かった（7.3 秒，

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

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

10९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

表 2
検出 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

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

5.6 項目 2 の調査

ると，全粒度で検出した場合は検出速度が大幅に向上し項目 2 についても，Suﬃx-Tree アルゴリズムを用いた場

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

合と Smith-Waterman アルゴリズムを用いた場合で同様のを示す．全粒度で検出した場合は，STEP-5 から STEP-7傾向であったため，Suﬃx-Tree アルゴリズムを用いた場合（メソッドクローンの検出）に要する時間が若干短くなっのみについて述べる．

た（31.7 秒 →24.0 秒）．これはファイルクローンとして検ファイル単位およびメソッド単位で検出した場合（検出出されたファイルが除外され，メソッド単位の検出時の入A，検出 B）と全粒度で検出した場合（検出 H）を比較す

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

ると，全粒度で検出した場合は検出数が多かった（11,029

最も注目すべきは，STEP-10（コード片クローンの検出）

個，49,446 個 →1,643,348 個）．また，コード片単位で検出に要した時間である．この処理が最も実行時間が減少してした場合（検出 C）と全粒度で検出した場合（検出 H）をいる（62,508.9 秒 →2,980.0 秒）．全粒度で検出した場合に比較すると，検出数にあまり変化はなかった（1,637,597 個

実行時間が約 1/20 倍になっている．どちらの場合も検出→1,643,348 個）．

時間の大半を STEP-10 に要しているため，重複ファイル

項目 2 の結論と重複メソッドを除外することが Suﬃx-Tree アルゴリズ

粗粒度な検出手法と比較して多粒度な検出手法は検出数ムを用いたマッチング処理に要する時間を短縮し，結果が多いということを示した．また，多粒度な検出手法は細として検出速度の向上に有効であることが分かる．また，粒度な検出手法と同等数のクローンを検出することを示

STEP-11 に要した時間を時間を比較すると，全粒度で検出した．

した場合は後処理を行うため実行時間が長くなっている．
しかし，その差は全体の検出時間と比較すると僅かな時間である．
さらに，ファイルおよびコード片単位で検出した場合（検表 3

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

STEP-1 から STEP-3

全粒度 [s]

コード片 [s]6.76.4

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

STEP-44.0-

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

STEP-5 から STEP-7

24.0

31.7

ことが有効であることが分かる（46,183.2 秒 →3,094.6 秒）．
項目 1 の結論
これらの結果から多粒度な検出手法は粗粒度な検出手法

1.2-

STEP-10

STEP-8 および STEP-9

2,980.0

62,508.9

STEP-11

68.5

16.6

よりも検出時間が長いという結論を得た．しかし，細粒度な検出手法と比較して，多粒度な検出手法が高速にクロー

表 4

各処理に要した時間（Smith-Waterman アルゴリズム）

ンを検出できることを示した．大規模なソースコードの集処理

全粒度 [s]

コード片 [s]6.6合に対してクローン検出を行う場合，多量のファイル・メSTEP-1 から STEP-3

6.7

ソッドクローンが検出される [7], [10], [14]．そのような場

STEP-4

4.3-

STEP-5 から STEP-7

20.0

24.4

合において，多粒度な検出手法はコード片クローンを検出するための時間を短縮することに有効であるといえる．

©2017 Information Processing Society of Japan

2.3-

STEP-10

STEP-8 および STEP-9

12,988.8

130,328.5

STEP-11

12.8

5.5

11

९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)$$$--   !  !'$$$,+*
 
 %&,++'',+, $  +0% ) &#$$$,-*(($$$,-,

%& 
 %
&,--'',-.  )  3%&$  +0%&#$$$,/,(($$$,/. 
 4 " 5%&,//'',/0  4 " 53   4 " 5%&#$$$,11(($$$,2*(

ファイル
クローン

メソッド
クローン

メソッド
クローン

メソッド
クローン

$$$
--   !  !'$$$,+*
 
 %&,++'',+, $  +0% ) &#$$$,-*(($$$,-,

%& 
 %
&,--'',-.  )  3%&$  +0%&#$$$,/,(($$$,/. 
 4 " 5%&,//'',/0 4 " 53  4 " 5%&#$$$,11(($$$,2*((a) 複数のメソッドクローンを 1 つのファイルクローンとして検出した例
ファイル
クローン


%&       &&  
   &'   &(!
!
&)
&*  
    &+    
'"!
!
'#  
   '$   
'%
!

)(!

メソッド
クローン
ではない
メソッド
クローン
ではない
メソッド
クローン
ではない




%%         &%
    &&   &'!
!
&(
&)
     &*    
&+!
!
'"
    
'#    '$!
!

)(!



(b) メソッドクローンが検出されないファイルをファイルクローンとして検出した例###-3               (

ファイル
クローン
ではない

###
-/                 (######+,/
&'&'
$###%    &'&'
   $###%/3
    &'&'   $###%+,0
   !
0*
    !
+,1
     (0+
     (メソッド+,2
&'&'    4 

  &'&'0,

  &'&'    4 
クローン  &    # #  '&'"&
  &    # #  '&'"######+-1))1+))######+11)+.,)(c) ファイル内の一部のメソッドのみをメソッドクローンとして検出した例
図 8

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

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

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

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

のメソッドクローンペアが 2,345 個のファイルクローンペ

1 つ目の例を図 8(a) に示す．メソッド単位のみで検出しアとして検出されたことを確認した．

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

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

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

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

アを 1 つ 1 つ確認することで，これらのクラス内の全てのService メソッドはクローンとして検出されなかった．こメソッドがクローンになっており，2 つのクラスを 1 つのの理由は，2 つのクラス内の全メソッドが最小クローン長クラスに集約するリファクタリングが可能であると判断で未満のメソッドであったためである．しかし，メソッド単

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

れら 2 つのクラスがクローンとして検出された．これらのが可能かどうかの判断に時間を要する．多粒度な検出手法

クラスがファイルクローンとして検出されたことで，2 つでは，メソッド単位の検出前にファイル単位の検出を行うのクラスを 1 つのクラスに集約するリファクタリングがで©2017 Information Processing Society of Japan12

९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

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

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

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

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

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

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

• 細粒度な検出手法と比較して，多粒度な検出手法が高速にクローンを検出できる．

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

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

ローンの検出数が多い．

nValues メソッドが検出された．DatabaseSelectAction と• 細粒度な検出手法・細粒度な検出手法と比較して，多DatabaseDeleteAction クラスは DatabaseAction クラスを

粒度な検出手法が分析しやすいクローンの検出結果を継承しており，getColumnValues メソッドに対してメソッ生成できる．

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

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

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

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

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

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

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

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

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

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

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

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

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

参考文献

成できることを示した．

[1]

6. 実験結果の妥当性について
対象ソフトウェア

本論文では，Java で記述された 84 個

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

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

いる．正規化により，Type-2 クローンの検出が可能になるが，誤検出も増える．現時点では，正規化によりどの程度の誤検出が増えるのかは確認できていない．

[6]

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

©2017 Information Processing Society of Japan[8]

Barbour, L., Khomh, F. and Zou, Y.: An empirical studyof faults in late propagation clone genealogies, Journalof 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 Transactions on Software Engineering,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 Transactions on
Information and Systems, Vol. 98, No. 2, pp. 325–333(2015).
Higo, Y. and Kusumoto, S.: How Should We Measure
Functional Sameness from Program Source Code? An
Exploratory Study on Java Methods, Proc. of the 22ndInternational Symposium on the Foundations of Software Engineering, pp. 294–305 (2014).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: amultilinguistic token-based code clone detection system
for large scale source code, IEEE Transactions on Software Engineering, 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. of ACM
SIGSOFT Software Engineering Notes, Vol. 30, No. 5,
pp. 187–196 (2005).
Ossher, J., Sajnani, H. and Lopes, C.: File cloning inopen source java projects: The good, the bad, and theugly, Proc. of the 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).

13९ইॺक़ख़॔ग़থ४ॽ॔জথॢ३থএ४क़঒ 2017
IPSJ/SIGSE Software Engineering Symposium (SES2017)

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Roy, C. K., Cordy, J. R. and Koschke, R.: Comparison and evaluation of code clone detection techniques
and tools: 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. ofthe 7th Working Conference on Mining Software Repositories, pp. 102–105 (2010).
Svajlenko, J. and Roy, C. K.: Evaluating clone detection
tools with BigCloneBench, Proc. of the 31st International Conference on Software Maintenance and Evolution, pp. 131–140 (2015).
Weissgerber, P. and Diehl, S.: Identifying refactorings
from source-code changes, Proc. of the 21st IEEE/ACM
International Conference on Automated Software Engineering, pp. 231–240 (2006).
神谷， 肥後， 吉田：コードクローン検出技術の展
開，コンピュータソフトウェア，Vol. 28, No. 3, pp. 29–42(2011).
石原， 堀田， 肥後， 井垣， 楠本：大規模なソフ
トウェア群を対象とするメソッド単位でのコードクロー
ン検出，情報処理学会論文誌，Vol. 54, No. 2, pp. 835–844(2013).
村上， 堀田， 肥後， 井垣， 楠本：Smith-waterman
アルゴリズムを利用したギャップを含むコードクローン
検出，情報処理学会論文誌，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).

©2017 Information Processing Society of Japan

14