情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)

ギャップを含むクローンセットの検出と評価
土居 真之1,a)

肥後 芳樹1,b)

楠本 真二1,c)

受付日 2020年03月13日, 採録日 2020年00月00日

概要：これまでに多数のクローン検出手法が提案されている．検出手法には互いに類似するコード片のペアであるクローンペア形式で出力する手法と互いに類似するコード片の集合であるクローンセット形式で出力する手法がある．どちらの形式で出力すべきかはクローン情報の用途によって異なるため，クローンの検出は両方の形式で出力できることが好ましい．しかし多くの既存検出手法では文の挿入や削除といったギャップを含むクローンはクローンペアの形式でしか出力できない．さらにクローンセットを検出できる手法は検出の精度やスケーラビリティの面で課題が残る．本研究では極大クリーク列挙アルゴリズムを利用してクローンペア形式で表されたクローンの情報からクローンセットを検出する手法を提案する．提案手法ではコード片を頂点，2 つのコード片がクローンペアであることを辺とみなしたグラフを作成した
ときに極大クリークを 1 つのクローンセットとみなす．実験では提案手法を実装したツールを 5 つのオー
プンソースソフトウェアに対して適用した．提案手法と検出の精度に課題がある既存手法に対して同じクローンペア情報を与えたところ，全ての対象ソフトウェアに対して提案手法の方が多くのクローンセットを検出しており，既存手法で検出されるクローンセットが提案手法では細かく分割されていることが確認できた．また，提案手法はクローンペア情報から数秒でクローンセットを高速に検出できた．
キーワード：ギャップを含むクローン，クローンセット，クリーク

Detection and Evaluation of Gapped Clone Sets
Masayuki Doi1,a)Yoshiki Higo1,b)

Shinji Kusumoto1,c)Received: March 13, 2020, Accepted: xx 00, 2020

Abstract: Many clone detection techniques have been proposed before now. There are two output formats
of clone detection results. One is the clone pair format, which is a pair of code fragments that are similar toeach other. The other is the clone set format, which is a set of code fragments that are similar to one another.
The clone pair format is better in some situations while the clone set format is better in other situations.
Hence, clone detection techniques should be able to output in both formats. However, most of the existingclone detection techniques that are capable of detecting gapped clones, which contains some gaps such as insertions and/or deletions of statements, can detect only clone pairs. In addition, in the case of the techniquesthat can detect clone sets, there is another problem that their detection accuracy is low and their scalability
is poor. In this paper, we propose a new approach to obtain clone sets from detected clone pairs by using
the maximum clique enumeration algorithm. Our proposed approach constructs a graph whose vertices arecode fragments of the clone pairs and whose edges are clone pair relationships. Thereafter, maximal cliquein the graph are detected as clone sets. We applied our proposed approach to ﬁve open source software. We
gave the same clone pairs to the proposed approach and an existing one, which has an issue in detection
accuracy. The proposed approach detected more clone sets for all the target software, which means that theclone sets detected by the existing approach were ﬁnely devided by the proposed approach. In addition, ourproposed approach could detect clone sets from clone pairs for each project in several seconds.
Keywords: gapped clone，clone set，cliquec 1959 Information Processing Society of Japan⃝0

情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)

1. はじめに
コードクローン (以下，クローン) とは，ソースコード
中に存在する互いに同一，あるいは類似したコード片であType-3 含有するコード片の組のうち少なくとも 1 つが Type-3 のクローンペアであり，残りの全ての組がType-1 もしくは Type-2 のクローンペアであるコード片の集合．

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

また Type-3 のクローンペアやクローンセットはギャップ

ある [17], [19]．クローンは保守性の低下 [13], [15], [23] やを含むクローンペアやクローンセットとも表現される [26]．

バグの伝播 [10], [16], [28] といったソフトウェアに悪影響

以降，本論文ではギャップを含むクローンペアおよびギャッを与えるとされている．したがって，クローンの検出はリプを含むクローンセットを総称してギャップを含むクローン

ファクタリング [14], [25] やデバッグ [7], [8] といった様々と呼ぶ．既存研究ではギャップを含むクローンがそうでなな場面に利用されている．

いクローンよりも多く存在すると報告されている [18], [21]．

クローンを表す用語としてクローンペアとクローンセッ
トがある [9]*1 ．クローンペアは互いに類似したコード片のしたがってギャップを含むクローンは最も検出の必要があるクローンである．

組（ペア）を表す．クローンセットは互いに類似したコーギャップを含むクローンを検出可能な検出器も多数開発

ド片の集合（セット）を表す．クローンセット内に存在すされている．しかしこれらの検出器の多くはクローンペア

るコード片の任意のペアはクローンペアである．これまでの検出のみ可能であり，クローンセットの検出が可能な検に多数のクローン検出器が開発されている [17]．検出器は出器は限られている．例えば，SourcererCC [20] は大規模対象のソースコードからクローンペア形式もしくはクロー

なソフトウェアに対してギャップを含むクローンのペア

ンセット形式で検出したクローンを出力する．どちらの形を検出できるが，クローンセットの検出はできない．一方式で出力すべきかはクローン情報の用途によって異なる．

CCFinder [9] は suﬃx tree アルゴリズム [6] により高速に

例えばソースコードの重複度の算出や，ある箇所からバグ

クローンセットを検出するが，ギャップを含むクローンはが見つかりその類似箇所の確認 [10] を行う場合はクロー検出できない．iClones [5] は suﬃx tree アルゴリズムをンペア形式の出力で十分であるが，類似するコード片の集拡張してギャップを含むクローンセットを検出するが，検約 [25], [27] や，類似するコード片のライブラリへの抽出 [9]出には膨大なメモリを必要とし，ギャップが大きいクロー

やコードの一貫性チェック [11] を行う場合にはクローン

ンは検出できない．NiCAD[4] はクローンセット形式でク

セット形式で出力する必要である．

ローンを検出できるが，NiCAD が出力するクローンセッ

クローンペアは，その 2 つのコード片の間の類似度に応

トにはその中に存在するコード片の組がクローンペアとじて，以下の三種類に分類できる [3]．

なっていない場合がある．例えば，あるクローンセットにType-1 空白やタブの有無，括弧の位置などのコーディ

コード片 ABC が含まれており，コード片 A とコード片 B

ングスタイルに依存する箇所を除いて，完全に一致すがギャップを含むクローンペアおよびコード片 B とコード

るコード片の組．

片 C がギャップを含むクローンペアであっても，コード片Type-2 変数名や関数名などのユーザ定義名，また変数

A とコード片 C がクローンペアとはなっていない場合がの型など一部の予約語のみが異なるコード片の組．

ある．このため，NiCAD が検出するクローンセットは本

Type-3 文の挿入や削除，変更が行われたコード片の組．

節で述べたクローンセットの定義には厳密には従っていな

また，上記の分類を利用して，クローンセットも以下の三い． 以上のことから，著者らは高速に定義通りにギャッ

種類に分類できる．

プを含むクローンセットを検出する手法が必要であると考Type-1 含有するコード片の全ての組が Type-1 のクローえた．現在，ギャップを含むクローンを検出可能／不可能

ンペアであるコード片の集合．

の違いにかかわらず多くの検出器がクローンペア形式のみ

Type-2 含有するコード片の組のうち少なくとも 1 つでの出力を行うという現状から，本研究ではクローンペア

が Type-2 のクローンペアであり，残りの全ての組がからクローンセットを生成する手法を提案する．提案手法

Type-1 のクローンペアであるコード片の集合．

は特定の検出ツールに依存しているわけではない． 提案
手法はクローンペアを入力とすることで，任意の既存検出

1

a)
b)
c)
*1

大阪大学 大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka University, Suita, 565-0971, Japan
m-doi@ist.osaka-u.ac.jp
higo@ist.osaka-u.ac.jp
kusumoto@ist.osaka-u.ac.jp
文献 [9] ではクローンセットではなくクローンクラスという名称が用いられているが，近年はクローンクラスという名称よりもク
ローンセットという名称が多く用いられるようになっているた
め，本論文でもクローンセットという名称を用いる．

c 1959 Information Processing Society of Japan⃝

器のポストプロセスとしてクローンセットを得る．ギャッ
プを含むクローンペアを出力する検出器の検出結果を入力することで，本研究の目的であるギャップを含むクローン
セットの抽出を可能にしている．
本研究では極大クリーク列挙アルゴリズムを利用して，クローンペアからクローンセットを検出する手法を提案

1

情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)

する．提案手法は，検出されたクローンペアのコード片を

tomcat/bdcp/bdcp2/datasources/PoolKeys.java

無向グラフの頂点，クローンペアの関係をそれらの頂点間

65 @Override
66 public int hashCode() {67
final int prime = 31;
68
int result = 1;
69
result = prime * result + ((dataSourceName == null) ? 0 : dataSourceNam…
70
result = prime * result + ((userName == null) ? 0 : userName.hashCode());
71
return result;A
72 }の辺として表現し，その無向グラフ内に存在している極大
クリークを列挙する．列挙された各極大クリークがクローンセットである．極大クリーク列挙アルゴリズムを利用することにより，含有する全てのコード片がクローンペアとなっているクローンセットを検出できる．

5 つのオープンソースソフトウェアに提案手法を適用した結果，ギャップを含まないクローンセットと比較して平均 3.0 倍多くのギャップを含むクローンセットが検出できた．さらに提案手法は各プロジェクトのクローンペアから

tomcat/util/descriptor/web/TaglibDescriptorImpl.java
42 @Override
43 public int hashCode() {44
final int prime = 31;
45
int result = 1;
46
result = prime * result47+ ((location == null) ? 0 : location.hashCode());
48
result = prime * result + ((uri == null) ? 0 : uri.hashCode());
49
return result;
50 }B

tomcat/util/descriptor/web/MessageDestinationRef.java

提案手法で見つけたクローンセットを修正した．その修正

94 @Override
95 public int hashCode() {96
final int prime = 31;
97
int result = super.hashCode();98
result = prime * result + ((link == null) ? 0 : link.hashCode());
99
result = prime * result + ((usage == null) ? 0 : usage.hashCode());
100
return result;
101 }をプルリクエストで開発者に提案したところ，7 個のプル

tomcat/util/descriptor/web/ContextResourceLink.java

リクエストのうち 2 個がマージされた．

84 @Override
85 public int hashCode() {86
final int prime = 31;
87
int result = super.hashCode();88
result = prime * result + ((factory == null) ? 0 : factory.hashCode());
89
result = prime * result + ((global == null) ? 0 : global.hashCode());
90
return result;D
91 }のうち，C に含まれる任意の頂点をつなぐ辺が存在する場
合に，C をクリークと呼ぶ．すなわち，クリーク C は完全グラフとなる G の誘導部分グラフである．クリークは密な構造を表す最も基礎的な構造である．G の任意のクリーク
において，自身を除く任意のクリークの部分集合ではない
ようなものを，極大クリークと呼ぶ．G に存在する全ての極大クリークを検出することを極大クリーク列挙と呼ぶ．
極大クリーク列挙はデータマイニング [1], [2] や Web マイ
ニング [12] といった様々な研究に利用されている．
極大クリーク列挙の例を図 1 に示す．図 1(a) は NiCAD

tomcat/util/descriptor/web/ContextEbj.java
116 @Override
117 public int hashCode() {118
final int prime = 31;
119
int result = super.hashCode();120
result = prime * result + ((home == null) ? 0 : home.hashCode());
121
result = prime * result + ((link == null) ? 0 : link.hashCode());
122
result = prime * result + ((remote == null) ? 0 : remote.hashCode());
123
return result;124 }114 @Override
115 public int hashCode() {116
final int prime = 31;
117
int result = super.hashCode();118
result = prime * result + ((home == null) ? 0 : home.hashCode());
119
result = prime * result + ((link == null) ? 0 : link.hashCode());
120
result = prime * result + ((remote == null) ? 0 : remote.hashCode());
121
return result;
122 }

A
-2
Typ
e

Type-3

-3

p
Ty

e-3
Typ

C

(b) 構築されたグラフ

存検出器のポストプロセスとして利用できる． 提案手法

ンペアが検出されている状況では，各コード片を表す頂点

c 1959 Information Processing Society of Japan⃝

Type-2

B

D

Type-3
Ty
p

e3

Ty

Type-3

C

-3
pe

C

D

F

Type-3
Ty
p

e3

p
Ty

3
e-

Type-3Type-1

例えば，コード片 C1 とコード片 C2 ，コード片 C2 とコー
ド片 C3 ，コード片 C3 とコード片 C1 という 3 つのクローAType-2

在する極大クリークを検出するというアプローチを取る．

D

Type-2

提案する．提案手法は，クローンペアを検出する任意の既れらの頂点間の辺とする無向グラフを構築し，グラフに存E

e-3

ローンペアの情報からクローンセットを検出する手法を

3
e-

Ty
p

本研究では極大クリーク列挙アルゴリズムを用いてク

e -1

e-3

B Type3. 提案手法p
Tyが列挙されたことを示している．

FpTyの中から 2 つの極大クリーク {A, B, C, D} と {C, D, E, F }クローンペアのコード片を頂点，クローンペアの関係をそF(a) hashCode メソッド

あり，極大クリーク列挙アルゴリズムを利用することで，そローンセットを検出可能である．提案手法は，検出されたE

tomcat/util/descriptor/web/ContextLocalEbj.java

が 1 つのクローンセットとして検出した 6 つのコード片では全てのタイプ（Type-1，Type-2，および Type-3）のクC-3

無向グラフ G の頂点集合 V (G) の部分集合 C ⊆ V (G)Type

2. 極大クリーク列挙

Type-2

オープンソースソフトウェアに対して提案手法を適用し，Type-3

クローンセットを 130 ミリ秒以下で検出できた．また他のE(c) 検出された極大クリーク
図 1

極大クリーク列挙の例

2

情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)

Step-1：隣接リストの生成
入力として与えられたクローンペアを基に隣接リストを
ギャップを含むクローンペアを検出可能な検出器生成する．隣接リストとはグラフを表すデータ構造の 1 つで，各頂点について直接辺で繋がっている頂点集合をリス

ファイル群

ト構造で表現している．図 2 には隣接リストの例を記載さStep-0 クローンペアの検出れている．図 2 の隣接リストは図 1(b) のグラフを表して(A, B)(A, C)(A, D)(B, C)(B, D)(C, D)(C, E)(C, F)(D, E)(D, F)

いる．図 2 では，Step-0 の結果として，コード片 A を含む
クローンペアとして AB ，AC ，AD が存在するため，頂点A の隣接リストには頂点 B ，C ，D が含まれる．

クローンペア
Step-1 隣接リストの作成
A{B, C, D}

D{A, B, C, E, F}

B{A, C, D}

E{C, D, F}

C{A, B, D, E, F}

F{C, D, E}

Step-2：極大クリーク列挙
このステップでは Step-1 で生成された隣接リストを基に極大クリーク列挙を行う．2 章で述べたように，クリー

隣接リスト
Step-2 極大クリーク列挙
提案手法

A

D

C

F

B

C

D

E

ク内の任意の頂点間に辺が存在する．提案手法におけるグラフの辺はクローンペアであることを示すため，クリーク
内に存在するコード片は同じクリーク内に存在する他の全てのコード片とクローンペアとなっている．したがって極極大クリーク
Step-3 クローンセットに変換

大クリーク列挙により得られるクリークは，互いに類似したコード片の集合であるクローンセットとなる．

Step-3：クローンセットに変換{A, B, C, D}{C, D, E, F}
クローンセット図 2 提案手法の概要

Fig. 2 An overview of the proposed technique.

はそれぞれ 2 つのクローンペアで共有されており，頂点

C1 C2 C3 からなるグラフはクリークを成している．このアプローチを取ることにより，クローンペア情報からクロー

極大クリーク列挙により得られたクリークからクローン
セットに変換する．極大クリークとクローンセットは一対一に対応しており，図 2 の場合，2 つのクローンセットが得られる．

3.1 提案手法によるクローンセット検出と NiCAD 方式
によるクローンセット検出の違い

ンセット情報を得るという問題を，無向グラフにおける極図 1 を用いて，提案手法によるクローンセット検出と大クリーク列挙の問題として解くことができる．なお，全

NiCAD によるクローン検出の是非について述べる．図 1てのクリークを列挙するのではなく，極大クリークのみをでは，6 つの Java メソッドが記載されており，提案手法を列挙する目的は，最大限大きなクローンセットを検出するためである．例えば，4 つのコード片 C4 C5 C6 C7 からなる
クローンセットが検出される場合は，それらの部分集合であるクローンセット C4 C5 C6 や C4 C6 C7 は検出されない．
提案手法の概要を図 2 に示す．提案手法は入力としてクローンペアを受け取り，クローンペアから形成されるク
ローンセットを生成する．提案手法はクローンペアを必要とするため，提案手法を利用するためには，図]2 にあるよ
うに，既存のギャップを含むクローンペアを検出可能な検出器を利用してクローンペアを検出しておく必要がある．

Step-1 隣接リストの生成
Step-2 極大クリーク列挙
Step-3 クローンセットに変換
以降それぞれのステップについて説明する．

利用すると，{A, B, C, D} と {C, D, E, F } の 2 つのクローンセットが検出されるのに対して，NiCAD を利用すると{A, B, C, D, E, F } の 1 つのクローンセットが検出される．
類似するコード片の集約 [25], [27] や類似するコード片のライブラリへの抽出 [9] を行う場合を考える．このような場合は，対象となる複数のコード片は，そのプロジェクト内もしくは外部のライブラリ内に単一のコード片としてまとめられる．複数のコード片を 1 つにまとめるためには，それらは互いに一定以上類似している必要がある．例えば，{A, B, C, D} と {C, D, E, F } は，その内部のコード片の全ての組がクローンペアであることから，一定以上の類似度があることが保証されている．一方，{A, B, C, D, E, F }では，コード片 A とコード片 F はクローンペアを成していないため，それらの間には十分な類似度が存在しておらず，それらを単一のコード片としてまとめるのは難しいことを示唆している．よって，{A, B, C, D} や {C, D, E, F }c 1959 Information Processing Society of Japan⃝3

情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)の方が，まとめる対象となるコード片の集合としては適切といえる．この場合，{A, B, C, D} を単一のコード片としてまとめると，{C, D, E, F } を単一のコード片としてまとめることはできなくなってしまう．このような場合，どちらのクローンセットを優先してまとめるのか，もしくはどり，そのグラフに存在する極大クリークを出力する．

4. 実験
本章では，提案手法を評価するために行った実験について述べる．

ちらもまとめないのかは開発者が判断する必要がある．
コードの一貫性チェック [11] を行う場合にはどちらのクローンセットも有益であると著者らは考える．例えば，{A, B, C, D} に含まれる各コード片は，ハッシュ値を得る

4.1 調査項目
この実験では下記の項目で提案手法を評価した．
クローンセット数

提案手法を利用することにより，既存ための変数 (result) の初期値が 0 であり，result へと足のクローン検出器で検出されたクローンペアから，し込まれる回数が 2 回であるという特徴を持つ．これらギャップを含むクローンセットがどの程度生成されるの共通の処理において，用いられている変数名の整合性やのかを調査した．

フォーマットやコードコメントの統一性チェックを行う

実行時間とメモリ使用量提案手法を利用してクローンペ

場合には提案手法を利用する方が望ましい．NiCAD 方式

アからクローンセットを得るのに要した時間およびメでは必ずしもコード片間に十分な類似度が無いために，一モリ使用量を調査した．

貫性をチェックする必要が無いコード片が含まれてしまう可能性が，提案手法を利用した場合に比べて高くなって

4.2 対象プロジェクト

しまう．一方，NiCAD 方式が役に立つ場合もある．例え実験には 5 つのプロジェクトを用いた．表 1 に対象のプば，{A, B, C, D, E, F } のクローンセットを開発者が見たロジェクトを示す．なお，クローン検出を行う前にテスト際に，コード片 A とコード片 B の int result = 1; は

コードは削除した．

int result = super.hashCode(); に変更した方がよい，と思うかもしれない．多くのコード片を提示し，その中の多数派と少数派の記述方法が明らかになることで，潜在的な不具合を発見するきっかけとなる場合がある．

4.3 検出器
提案手法の入力であるクローンペアの検出には NiCAD [4]を用いた．検出単位はメソッド単位とし，類似度の閾値はソースコードの重複度の算出や，ある箇所からバグが見

デフォルトの 0.30 とした．検出するクローンの最小の大き

つかりその類似箇所の確認 [10] を行う場合はクローンペア

さはデフォルトの 10 行を用いた．また，この実験では比があれば十分なため，提案手法や NiCAD によるクローン

較のために iClones も用いた．iClones は検出するクロー

セットの生成は必要ない．

ンの最小の大きさを字句数で指定するため，NiCAD と完全に同じ値を指定することはできないが，今回は Java の3.2 実装プロジェクトが対象ということもあり，一行あたり平均で提案手法ではクローンペアの情報を入力として受け取る

5 つの字句が含まれると想定し，50 字句を検出する最小のために，クローンの検出器が出力したクローンペアの検出結クローンの大きさとした．NiCAD も iClones もその他の果ファイルを読み込む必要がある．本研究では NiCAD [4]設定は全てデフォルトの値を用いた．

のクローンペアの出力結果を読み込めるように実装した．

NiCAD は検出したクローンペアとクローンセットをそれ

4.4 クローンセット数の調査

ぞれ別のファイルに出力する．本研究ではこのうち，ク

提案手法が検出したクローンセット数を NiCAD が検出

ローンペアのファイルを利用した．NiCAD 以外の検出器したクローンセット数と比較した．その結果を表 2 に示に対しても検出結果を読み込む処理を実装することで提案

す．表 2(a) より，どのプロジェクトにおいても，NiCAD

手法を適用できる．

の検出したクローンセットが分解されて，極大クリークか

極大クリーク列挙を行うためにはコード片と頂点番号と表 1の紐づけが必要である．そのため検出結果に含まれる全てのコード片に ID をつける．NiCAD の検出結果に含まれる全てのコード片に pcid と呼ばれる ID が既に割り振られているため，本研究ではこの pcid を頂点番号とした．
また，本研究では Makino らが提案した極大クリーク列
挙のアルゴリズム [29] を実装しているツールの MACE [22]を用いた．MACE はグラフの隣接リストを入力に受け取c 1959 Information Processing Society of Japan⃝

対象のプロジェクト

Table 1 Target projects.
プロジェクトコミット ID

ファイル数

行数

Eclipse.jdt.core6958b52...

3,232

734,119Guava

c15cd80...

1,818

407,870

JFreeChart

d03e68a...

637

219,187

RxJava166c529...

850

174,085

Tomcatcc48d0d...

1,855

465,2274

情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)

表 2 検出されたクローンセット数

Table 2 The number of detected clone sets.
(a) 全クローンセット
プロジェクト名

NiCAD

Eclipse.jdt.core
Guava

提案手法 (%)
合計

Type-3Type-1 および Type-2

1,036

1,510

1,283 (84.97%)

227 (15.03%)

1,206

1,306

402 (30.78%)

904 (69.22%)

JFreeChart

244

2,685

2,625 (97.77%)

60 ( 2.23%)

RxJava314478

382 (79.92%)

96 (20.08%)

Tomcat399

477

396 (83.02%)

81 (16.98%)(b) 要素数が 3 以上のクローンセット
プロジェクト名

NiCAD

Eclipse.jdt.core

300

検出したクローンセット数 (%)
合計

Type-3Type-1 および Type-2529

497 (93.95%)

32 ( 7.05%)

Guava

207

328

289 (88.11%)

39 (11.89%)

JFreeChart

90

2,502

2,487 (99.40%)

15 ( 0.60%)

RxJava118

234

223 (95.30%)

11 ( 4.70%)

Tomcat99

131

121 (92.24%)

10 ( 7.76%)

らなるクローンセットが生成されていることがわかる．しType-3 クローンセットの割合が非常に高くなっており，特かし，それらの数の比はプロジェクトによって大きく異なに JFreeChart ではその割合が 99.40%にもなっていること

る．Guava では，NiCAD は 1,206 のクローンセットを検がわかる．この結果より，Type-1 および Type-2 のクロー出したのに対して，提案手法では 1,306 のクローンセット

ンセットに比べて Type-3 のクローンセットが多く存在しを検出した．つまり，平均では NiCAD が検出した単一のていることがわかる．

クローンセットから 1.08 の極大クリークをなすクローン
セットが生成されたことがわかる．一方，JFreeChart で

4.5 実行時間とメモリ使用量の調査

は，平均で NiCAD が検出した単一のクローンセットから

NiCAD と提案手法を用いたクローンセット検出および11.08 の極大クリークをなすクローンセットが生成された．

iClones を用いたクローンセット検出の実行時間とメモリ提案手法を利用した場合に，JFreeChart から最も多くのType-3 クローンセットが検出された要因は JFreeChart から検出されたクローンペアに equals() メソッドが多く含まれていたためである．equals() メソッドは引数のオブジェクトが自身のクラスと等しいかの比較を行うメソッド

表 3 提案手法と iClone の実行時間とメモリ使用量

Table 3 Execution time and memory usage of the proposed
technqiue and iClones(a) 実行時間（提案手法の括弧内の数値は極大クリーク検出時間）である．そのためクラスによって処理が異なり，equals()

プロジェクトメソッドのクローンペアはギャップが含まれている場合が多い．一方で Guava から最も多くの Type-1 および Type-2

NiCAD + 提案手法

iClones

NiCAD

提案手法

Eclipse.jdt.core

105.6s

4.9s (98ms)

17.2s

Guava

48.9s

3.0s (61ms)

7.1s

クローンセットが検出された要因は，共通処理がパッケー

JFreeChart

16.8s

3.3s (130ms)

2.2s

ジ間に多く存在するためである．Guava は Java のプログ

RxJava22.4s

1.8s (48ms)

2.7s

Tomcat48.1s

1.8s (44ms)

4.0s

All projects

256.8s7.7s (215ms)

34.1s

ラミングで共通して使われるユーティリティライブラリ
である．android パッケージと android パッケージ以外のパッケージとで共通する処理が多いため，ギャップを含ま(b) メモリ使用量ないクローンペアが多数検出された．

NiCAD + 提案手法

プロジェクトiClones

NiCAD

提案手法

Eclipse.jdt.core

74.1MB

3801.0MB4155.3MB

Guava

73.8MB

938.7MB2079.1MB

JFreeChart

72.8MB

1292.6MB

1020.1MB

RxJava72.5MB

649.1MB1252.1MB

ることがわかる．また，表 2(b) より，要素数が 3 以上のTomcat72.3MB

564.1MB1891.9MB

クローンセットの場合だと，全てのプロジェクトにおいてAll projects

76.2MB

6918.1MB

9719.7MB

また，提案手法については，検出されたクローンセット
が Type-3 とそうでないもので分類をした．表 2(a) より，
全クローンセットを対象とした場合，Guava を除く 4 つのプロジェクトにおいて Type-3 クローンの数が過半数であc 1959 Information Processing Society of Japan⃝5

情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)

使用量を調査した．調査結果を表 3 に示す．表 3(a) より，

法は問題なく動作するが，対象プロジェクトが小さい場合

NiCAD によるクローンの検出は iClones のクローンの検でも非常に多くのクローンペアが検出された場合には，提出に比べて長い時間を必要としていることがわかる．これ

案手法は実行に長い時間を必要とする，およびメモリが大は，NiCAD が少ないメモリ使用量でクローン検出を行う量に必要である，という課題が存在する．クローンペアか実装の工夫をしているためである．提案手法の実行時間は

ら構築したグラフが密である場合には，本研究で利用した対象が大きい場合であっても数秒である．提案手法の実行

Makino-Uno アルゴリズムではなく，密グラフからの極大

時間のうち，大半の時間はテキストファイルからクローン

クローン列挙が得意な Tomita アルゴリズムを利用するこ

ペア情報を読み込みメモリ内にオブジェクトとして保存とで実行時間の短縮やメモリ使用量の改善ができる可能性する処理であり，極大クリーク列挙に必要であった時間はがある．

高々数百ミリ秒であった．
表 3(b) から，NiCAD のメモリ使用量は最も大きい対象の場合（All projects）であっても約 76MB であるのに対し

5. 妥当性への脅威
実験対象：外的妥当性て，iClones ではその 100 倍以上の約 9.7GB のメモリを使実験の対象には 5 つのプロジェクトに対して実験を行っ用している．iClones ほどではないが提案手法もメモリ使た．この 5 つのプロジェクトは検出されるクローンの評

用量が大きく，より大きなプロジェクトからクローンセッ

価によく用いられるプロジェクトであるが，他のオープン

トを検出する場合は大容量のメモリが必要である．このこ

ソースソフトウェアや企業のプロジェクトに対して同様のとから，ギャップを含むクローンセットの検出には未だメ結果になるとは限らない．

モリ使用量についての課題があるといえる．
対象プロジェクトから構築されたグラフの規模を表 4 に

検出器：内的妥当性示す．この表より，JFreeChart のグラフの平均次数が 25

実験では NiCAD が検出したクローンペアに対して提案を超えており，他の全てのプロジェクトの平均次数が 4 以下

手法を適用した．しかし NiCAD 以外の検出器で得られたであることを考慮すると，JFreeChart のグラフが極めて密クローンペアに対しても同様のクローンセットが得られる

であることがわかる．極大クリーク列挙には Makino-Unoとは限らない．

アルゴリズム [29] と Tomita アルゴリズム [24] の 2 つが存在する．検出対象が疎グラフである場合は前者の方が高速

6. あとがきであり，検出対象が密グラフである場合は後者の方が高速

本研究では，極大クリーク列挙アルゴリズムを用いるこであるという特徴を持つ [22]．本研究では Makino-Uno アとでクローンペアからクローンセットを検出する手法を提ルゴリズムを実装した MACE[22] というツールを利用し案した．提案手法は，クローンペアを検出する任意の既存たため，JFreeChart からの極大クリーク検出時間が他の検出器のポストプロセスとして利用できる． 実験では複数

どのプロジェクトよりも長くなったと考えられる．また，のオープンソースソフトウェアに適用し，全ての対象ソフ

Makino-Uno アルゴリズムは密なグラフからの極大クリー

トウェアから多数のギャップを含むクローンセットが検出

ク列挙が得意でないことから，JFreeChart に対する提案手された．また，提案手法によるクローンペアからクローン法のメモリ使用量が iClones よりも大きくなったと考えら

セットの検出時間は最も大きな対象ソフトウェアに対してれる．

も数秒で完了することも確認できた．今後の課題としては，

上述の通り，提案手法は対象プロジェクトの規模ではな

提案手法が検出したクローンセットと NiCAD が検出する

く，対象プロジェクトから検出されたクローンペアの数

クローンセットを有用性の点から比較することが挙げられ

や，クローンペアから作成されたグラフの密度に依存する．例えば，著者らが提案手法や NiCAD を用いてオープる．そのため，対象プロジェクトが非常に大きい場合でンソースソフトウェアからクローンセットを検出し，そのあっても検出されたクローンペアが少ない場合には提案手

クローンセットを目視確認することにより，修正が必要と思われるコード片を見つけ，実際に修正を行いそれをプル

表 4 対象プロジェクトのグラフ規模

リクエストにより開発者にフィードバックすることによる

Table 4 Graph size of the target projects

評価を検討している．

プロジェクト

頂点数

辺数

最大次数

平均次数

Eclipse.jdt.core

3,738

19,060

90

3.71

Guava

3,265

5,991

26

2.90

JFreeChart

1,004

9,949

59

25.24

RxJava

1,159

3,004

24

3.70

Tomcat

1,169

1,810

15

2.77

c 1959 Information Processing Society of Japan
⃝

謝辞 本研究は，科学研究費補助金基盤研究 (B)(課題番
号：20H04166) の助成を得て行われた．
参考文献
[1]

Agrawal, R., Mannila, H., Srikant, R., Toivonen, H.,
Verkamo, A. I. et al.: Fast discovery of association

6

情報処理学会論文誌

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Vol.0 No.0 0–8 (??? 1959)

rules., Advances in knowledge discovery and data mining, Vol. 12, No. 1, pp. 307–328 (1996).
Agrawal, R., Srikant, R. et al.: Fast algorithms for mining association rules, Proc. 20th int. conf. very large
data bases, VLDB, Vol. 1215, pp. 487–499 (1994).
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).
Cordy, J. R. and Roy, C. K.: The NiCad clone detector,
2011 IEEE 19th International Conference on Program
Comprehension, IEEE, pp. 219–220 (2011).
Göde, N. and Koschke, R.: Incremental clone detection,2009 13th European Conference on Software Maintenance and Reengineering, IEEE, pp. 219–228 (2009).
Gusﬁeld, D.: Algorithms on stings, trees, and sequences: Computer science and computational biology,
Acm Sigact News, Vol. 28, No. 4, pp. 41–60 (1997).
Jiang, L., Su, Z. and Chiu, E.: Context-based detectionof clone-related bugs, Proceedings of the the 6th joint
meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, ACM, pp. 55–64 (2007).
Juergens, E., Deissenboeck, F., Hummel, B. and Wagner,
S.: Do code clones matter?, 2009 IEEE 31st International Conference on Software Engineering, IEEE, pp.
485–495 (2009).
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, H., Jung, Y., Kim, S. and Yi, K.: MeCC: memory comparison-based clone detector, 2011 33rd International Conference on Software Engineering, IEEE, pp.
301–310 (2011).
Krinke, J.: A study of consistent and inconsistentchanges to code clones, Proceedings of the 14th working
conference on reverse engineering, IEEE, pp. 170–178(2007).
Kumar, R., Raghavan, P., Rajagopalan, S. and Tomkins,
A.: Trawling the web for emerging cyber-communities,
Computer networks, Vol. 31, No. 11-16, pp. 1481–1493(1999).
Lozano, A. and Wermelinger, M.: Assessing the eﬀect ofclones on changeability, 2008 IEEE International Conference on Software Maintenance, IEEE, pp. 227–236(2008).
McIntosh, S., Poehlmann, M., Juergens, E., Mockus, A.,
Adams, B., Hassan, A. E., Haupt, B. and Wagner, C.:
Collecting and leveraging a benchmark of build systemclones to aid in quality assessments, Companion proceedings of the 36th international conference on software
engineering, ACM, pp. 145–154 (2014).
Mondal, M., Rahman, M. S., Saha, R. K., Roy, C. K.,
Krinke, J. and Schneider, K. A.: An empirical studyof the impacts of clones in software maintenance, 2011
IEEE 19th International Conference on Program Comprehension, IEEE, pp. 242–245 (2011).
Rahman, F., Bird, C. and Devanbu, P.: Clones: Whatis that smell?, Empirical Software Engineering, Vol. 17,
No. 4-5, pp. 503–530 (2012).
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. and Cordy, J. R.: Near-miss function clones

c 1959 Information Processing Society of Japan
⃝

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

in open source software: an empirical study, Journalof Software Maintenance and Evolution: Research andPractice, Vol. 22, No. 3, pp. 165–189 (2010).
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).
Sajnani, H., Saini, V., Svajlenko, J., Roy, C. K. andLopes, C. V.: SourcererCC: Scaling code clone detection
to big-code, Proceedings of the 38th International Conference on Software Engineering, pp. 1157–1168 (2016).
Svajlenko, J., Islam, J. F., Keivanloo, I., Roy, C. K. andMia, M. M.: Towards a big data curated benchmark ofinter-project code clones, 2014 IEEE International Conference on Software Maintenance and Evolution, IEEE,
pp. 476–480 (2014).
Takeaki, U.: Implementation issues of clique enumeration algorithm, Special issue: Theoretical computer science and discrete mathematics, Progress in Informatics, Vol. 9, pp. 25–30 (2012).
Thummalapenta, S., Cerulo, L., Aversano, L. and
Di Penta, M.: An empirical study on the maintenanceof source code clones, Empirical Software Engineering,Vol. 15, No. 1, pp. 1–34 (2010).
Tomita, E., Tanaka, A. and Takahashi, H.: The worstcase time complexity for generating all maximal cliquesand computational experiments, Theoretical computerscience, Vol. 363, No. 1, pp. 28–42 (2006).
Tsantalis, N., Mazinanian, D. and Rostami, S.: Clone
refactoring with lambda expressions, Proceedings of the39th International Conference on Software Engineering, IEEE, pp. 60–70 (2017).
Ueda, Y., Kamiya, T., Kusumoto, S. and Inoue, K.:
On detection of gapped code clones using gap locations,Ninth Asia-Paciﬁc Software Engineering Conference,
2002., IEEE, pp. 327–336 (2002).
Yoshida, N., Ishizu, T., Edwards III, B. and Inoue, K.:
How slim will my system be? estimating refactored code
size by merging clones, Proceedings of the 26th Conference on Program Comprehension, pp. 352–360 (2018).
Zhang, T. and Kim, M.: Automated transplantation anddiﬀerential testing for clones, Proceedings of the 39th International Conference on Software Engineering, IEEE,
pp. 665–676 (2017).
宇野毅明： 大規模グラフに対する高速クリーク列挙アル
ゴリズム，Vol. 103, No. 31, 一般社団法人電子情報通信学会，pp. 55–62 (2003).

土居 真之
平成 30 年大阪大学基礎工学部情報科学科卒業．令和 2 年同大学大学院情報科学研究科卒業．在学時，コードク
ローン検出の研究に従事．

7

情報処理学会論文誌

Vol.0 No.0 0–8 (??? 1959)

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

楠本 真二 （正会員）
昭和 63 年大阪大学基礎工学部情報工学科卒業．平成 3 年同大学大学院博士課程中退．同年同大学基礎工学部助手．平成 8 年同講師．平成 11 年同助教授．平成 14 年同大学大学院情報科
学研究科助教授．平成 17 年同教授．
博士（工学）．ソフトウェアの生産性や品質の定量的評
価，プロジェクト管理に関する研究に従事．IPSJ，IEICE，

JSSST，IEEE，JFPUG，PM 学会，SEA，各会員．

c 1959 Information Processing Society of Japan⃝

8