Vol. 0

情報処理学会論文誌

No. 0

1959

大規模ソースコードを対象としたコードクローンの検出と可視化
肥 後 芳 樹†松 下
誠†

リビエリ シモネ†
井 上 克 郎†コンピュータハードウェアが安価になり，分散処理方式はソフトウェア分析のための現実的な選択肢の 1 つとして用いられるようになった．本論文では，超大規模ソースコードからコードクローンの検出，および可視化を行うシステム D-CCFinder について述べる．D-CCFinder は 80 台のコンピュータを用いた分散型コードクローン検出システムであり，検出されたコードクローン情報は散布図などを用いて可視化される．D-CCFinder は約 4 億行のソースコードから 2 日余りでコードクローン情報を収集し，頻出するコードを容易に特定することができた．

A Code Clone Detection and Visualization for Large-Scale Source Code
Yoshiki Higo,† Simone Livieri,† Makoto Matsushita†
and Katsuro Inoue†
The increasing performance-price ratio of computer hardware makes possible to explore a
distributed approach at code clone analysis. This paper presents D-CCFinder, a distributed
approach at large-scale code clone analysis. D-CCFinder has been implemented with 80 PC
workstations in our student laboratory, and a vast collection of open source software with
about 400 million lines in total has been analyzed with it in about 2 days. The result has
been visualized as a scatter plot, which showed the presence of frequently used code as easy
recognizable patterns.

用事例が報告されているが1),6),12),15),16) ，それらは単

1. は じ め に一または少数のソフトウェア内でのコードクローンの近年，ソフトウェア分析手法としてコードクローン状態を調査しており，大量のソフトウェア間における検出が注目を集めている13),18) ．コードクローンとは，

コードクローン分析は行われていない．

ソースコード中のある一部分（コード片）のうち，他のしかし，近年，GNU プロジェクト9) や Jakarta プ

コード片と同一または類似しているものを指す．コー

ロジェクト11) に代表されるように多くのオープンソー

ドクローンはコピーアンドペーストなどのさまざまな

スソフトウェアが開発されており，その一部は他のソ理由によりソースコード中に作りこまれる．あるコー

フトウェアでも用いられているとの指摘もされている

ド片にバグが含まれていた場合，そのコード片のコー

ことから3) ，大量のソフトウェア間における利用関係

ドクローンすべてについて修正の是非を考慮しなけれを調査することにより，頻繁に再利用されているコー

ばならない．このようなことから，コードクローンはドの特定など，有益な情報を取得できるであろう．

ソフトウェアの保守を困難にしている要因の１つであオープンソースソフトウェアに限らず，企業の開発ると指摘されている．そのため，コードクローン検出部門など，組織規模でコードクローン分析を適用するを行うことは，効率的にソフトウェア保守を行うためことにより，組織自体のソフトウェア開発プロセスをに有効であるといえる．また，コードクローン検出を改善することができるとも思われる．たとえば，或る行うことにより，単純な重複部分の調査だけではなく，組織が過去に開発したすべてのソフトウェアからコー

14),20)

ソフトウェアの進化を追うこともできる．

ドクローンを検出することにより，その組織で繰り返

これまでに多くのコードクローン検出法とその適し実装されているコードを特定することができる．そのようなコードを社内ライブラリとしてまとめること† 大阪大学大学院情報科学研究科
Graduate School of Information and Science Technology, Osaka University

により，今後のソフトウェア開発をより効率的に行えるであろう．
1

情報処理学会論文誌

2

1959

しかし，既存の検出法はどれも単一または少数のソ• 提案した検出手法をオープンソースターゲットに

フトウェアからのコードクローン検出を目的として提適用することにより，ソフトウェア間にどのよう案されているものであり，そのまま大量のソフトウェ

なコードクローンが存在しているのかを特定する

ア群に対して適用することはスケーラビリティの面かことができた．現時点では，可視化により際立っら難しい．既存手法の中では，字句単位の検出手法をた部分に存在するコードクローンを特定したにと12)実装しているツール CCFinder

どまっている．

が，他の手法に比べスケーラビリティが高いことが知られているが4) ，一以上の 2 点から，本論文はソフトウェア分析を分散度に検出を行うことができる規模の上限は約 500 万行

処理環境を用いて行うことの有用性を示しているといである ．そこで本論文では，大量のソフトウェア群

える．

☆

から短時間でコードクローンを検出するための方法と，以降，2 節では D-CCFinder の分散処理モデルを定検出したコードクローンの可視化について述べる．

義し，3 節ではその実装について述べる．4 節ではオー

本論文では，コードクローン検出対象として，オー

プンソースターゲットへの適用について述べ，5 節でプンソースオペレーティングシステム FreeBSD8) 用はその結果に対する考察を行う．6 節では関連研究にのソフトウェア集合 Ports システムに含まれている，

ついて触れ，最後に 7 節では，まとめと今後の課題にC 言語で記述された約 4 億行のソースコード（以降，ついて述べる．

オープンソースターゲット）を用いた．この規模は，

CCFinder の検出可能である限界を遥かに超えており，
単一のコンピュータ上で一度に検出を行うことは不可能である．そこで，分散処理方式を用いて，検出対象

2. 超大規模ソースコードを対象としたコード
クローン検出手法
2.1 検 出 対 象を小さく分割し，各コンピュータに入力として与える．

本論文でのコードクローン検出対象は，オープン

各コンピュータ上で CCFinder を実行し，割り当てら

ソースオペレーティングシステム FreeBSD 用のソフ

れたソースファイルに含まれるコードクローンを検出

トウェア集合 Ports システムに含まれているソースファする．このように対象を小さく分割することにより，

イル（オープンソースターゲット）であり，各ソース

CCFinder を用いて短時間でコードクローンを検出す

ファイルは 1 つのプロジェクトに属している．すべて

ることができる．分割したすべてのタスクを単一コンのプロジェクトは，zip, emacs, apache, windowmaker

ピュータ上で逐次実行した場合も同じ結果を得ることなど，一意に特定可能な名前を持っている．また，本はできるが，すべての検出処理を完了するには 45 日

論文では検出対象を C 言語で記述されたソースコードを要すると予測されに限定しているが，Java や COBOL などの CCFinder☆☆

，現実的ではない．

提案手法を分散型アプリケーション Distributed-

CCFinder（以降，D-CCFinder）として実装した．D-自体が扱えるプログラミング言語であれば，同様に適用可能である．

CCFinder を大阪大学基礎工学部情報科学科の学生演

共通の特徴を持ったプロジェクトは同じカテゴリに習室のコンピュータ 80 台上で実行し，オープンソー

所属している．たとえば，emacs や vim，gedit など

スターゲット内に含まれるコードクローンを検出したは editors カテゴリに所属している☆☆☆ ．

ところ，約 2 日で検出を完了することができた．

ユニットは，全ファイル集合を或るサイズ以下で分本研究の成果は以下の通りである．

割した要素であり，1 つのユニットに含まれるソース• 単一あるいは少数のソフトウェアに対する分析手

ファイルは単一プロジェクトからなる場合と複数プロ法であったコードクローン検出を分散処理技術をジェクトからなる場合がある．また，ユニットのサイ用いることによって応用し，大量のソフトウェア

ズは，使用するコンピュータの性能によって変えるべ

群から短時間でコードクローンを検出する手法を

きである．

提案した．
☆
☆☆

任意の 2 つのユニットで指定されるファイル集合間の対応をピースといい，これが各コンピュータ上で実

CPU:Xeon 2.8GHz, Memory: 4GB を用いた場合
CCFinder の検出規模の上限である 500 万行で 4 億行を区切った場合，80 個に分割される．これを 2.3 節のモデルに当てはめると， 1
2 × 80 × (80 + 1) = 3240 個のタスクが存在することになる．また，これまでの経験から 500 万行からのコードク
ローン検出には約 20 分を要すると想定し，総検出時間を計算すると 20 分 ×3240 = 64800 分 = 45 日 となる．

行される CCFinder への入力となる．もし，ユニット
サイズよりも大きなソースファイルが存在した場合は，☆☆☆

各プロジェクトをカテゴリ分けしたのは Ports システムの管理者であり，著者らが行ったわけではない．

Vol. 0

大規模ソースコードを対象としたコードクローンの検出と可視化

No. 0

3

piece

u
ni
t
i

CCFinderinput

unit jtarget

unit

i + 1

i

・・・・・・・・・・・・・・・

fileproject

i - 1

1

zip

categoryemacs

archivers

・・・

gedit

n

j

・・・・・・・

vim

editors・・・・・

apachewww’s

図 1 プロジェクト，カテゴリ，ターゲット，ユニット，ピース間の関係
Fig. 1 Relation between project, category, target, unit, and piece

そのファイル単体で１つのユニットを構成する．そのを実行することにより，コードクローンを検出する．

ため，サイズの大きなピースが存在することになる．

図 2 は D-CCFinder の分散処理モデルを表してい大きすぎるサイズのために CCFinder の実行が失敗しる．検出対象の規模は nu とする．n は分割数であてしまった場合でも，ファイルを分割して小さなピー

り，u はユニットのサイズを表している．このとき，スを作成することは行わない．図 1 はプロジェクト，

任意のピースは (i, j) で表すことができる（ただし，カテゴリ，ユニット，ピース間の関係を表している．

1 ≤ i, j ≤ n）．ピース (i, j) に含まれるコードクロー

2.2 検出結果の表示

ンはピース (j, i) に含まれるコードクローンと等価でコードクローンには，コメントを除く部分がまったあるため，後者については検出を行わない．これによく同一の exact クローンと，変数名や関数名などのり，CCFinder を用いてコードクローンを検出しなけ

ユーザ定義名が異なる parameterized クローンの二種ればならないピースの数は n(n + 1)/2 となる．なお，

類があるが2) ，本研究ではこの両方を検出する．

ピース内でのコードクローン検出がプロジェクト内の検出対象の規模が非常に大きいため，大量のコード

コードクローン検出を含む場合があるが☆ ，本論文でクローンが検出されることが予測できる．そのため，はプロジェクト間のコードクローンを検出することがコードクローンの状態を容易に把握するためには，検目的であるため，プロジェクト内のコードクローンは

出結果の抽象化を行う必要がある．提案手法では，コー検出しない．

ドクローン検出後に，ファイル，プロジェクト，カテゴ

D-CCFinder は，既存の CCFinder を複数のコン

リの各レベルで抽象化を行う．たとえば，各ファイル

ピュータで実行することにより，コードクローン検間，各プロジェクト間，カテゴリ間の重複の度合いや，出を行う．各ピースの演算（コードクローン検出）は単にコードクローンを共有しているかどうかといった

他のピースの演算結果にまったく依存しないため，タ

抽象化も行う．

スクの割り当て処理は単純に行える．まだ一度も調べ

2.3 分散処理モデルていないピースをアイドル状態のコンピュータに割り既存の検出法はどれも単一若しくは少数のソフト

当て，検出結果を回収するだけでよい．

ウェアからのコードクローン検出を目的として提案されており，そのまま大量のソフトウェア群に対して適用することはスケーラビリティの面から難しい．このため，検出対象を小さなユニットに分割してその組み合わせからピースを作成し，ピース単位で CCFinder☆

ピース (i, i) や (i, i − 1) など，分散処理モデルにおいて主対角線上またはそれに近い位置に存在するピースでは，その垂直方向のユニットと水平方向のユニットに含まれるファイルが同一プロジェクトのものである場合がある．

情報処理学会論文誌

4

1959

79 slavesmasterClone

Indexer

D-CCFindersource files

Coverage

Image

Analyzer

Generator

code clone data

scatter plot

coverage data
heatmapunits
図 3 D-CCFinder の処理の流れ
Fig. 3 Process Overview for Code Clone Analysis using D-CCFinder

は 100Mbps のネットワークで結ばれている．検出対

target

unit

1

2

・・・・・

3

・・・・・

i

j

・・・・・

n-1

n

セス可能なファイルシステム上に存在し，各マシンは

1

non-computed pieces

2

・
・・
・・

がマスター，残りの 79 台がスレーブである．

・・
・
same

i

・
・・
・
・

(j,i)

→

piece

clones

図 3 に示すように，D-CCFinder には対象ソースファ
イルに前処理を行うユーテリティ，検出結果を集約するプログラム，および検出結果から散布図などを生成

・・
・

task

するジェネレータが統合されている．

j

(i,j)

・・
・・
・

Indexer 検出対象ソースファイルを走査し，ファイ
・・
・

n
1
n

NFS 経由でアクセスする．D-CCFinder は大学の演習室のコンピュータ 80 台を用いて実装されており，1 台

3

t
a
r
g
e
t

象ソースファイルと検出結果はすべてのマシンがアク

ルサイズ，行数，プロジェクト名，カテゴリ名などの情報を収集する．また，ユニットの境界を決computed pieces

定する．
マスターノード スレーブノード上の CCFinder の

図 2 D-CCFinder の分散処理モデル
Fig. 2 Distributed Processing Model of D-CCFinder

実行状態を監視する．アイドル状態のスレーブ
ノードを発見した場合は，ユニット境界情報から，

CCFinder の入力ファイル（そのユニットに含まれているソースファイルのパスのリスト）を生成

3. D-CCFinder

し，スレーブノードにタスクを割り当てる．もしD-CCFinder はマスタースレーブ型のシステムであり，各スレーブマシン上で CCFinder が実行される．マ

割り当てが失敗した場合は，そのタスクは他のス
レーブに割り当てられる．

スターは，スレーブの実行状態を監視し，タスクを割

スレーブノード マスターノードから与えられた入力

り当てる．マスター・スレーブ間の通信は，Java RMI

ファイルを用いてコードクローン検出処理を行う．

を用いて行われる．表 1 はマスターと各スレーブマ

検出対象ファイルはスレーブノードのローカル

シンの性能を表している，またマスター・スレーブ間
表 1 マスター・スレーブノードの性能
Table 1 Spec. of the Master and Slave Nodes

CPU
メモリ
オペレーティングシステム
利用可能 HDD 領域

Pentium IV 3GHz
1 GBytes
FreeBSD 5.3-STABLE
40 ∼ 50 GBytes

表 2 オープンソースターゲットのサイズ
Table 2 Characteristics of the open source target
カテゴリ数
プロジェクト数.c ファイル数
総行数
総容量

45
6,658
754,552
403,625,067
10.8 GBytes

Vol. 0

大規模ソースコードを対象としたコードクローンの検出と可視化

No. 0

5

ファイルシステムにコピーされ，その後コードク

含まれる場合は，それらの間で非常に多くのコードク

ローン検出が行われる． 検出処理完了後もローカローンが検出されることが予測される．

ルファイルシステム上のコピーは削除されず，次また，コードクローンの状態を定量的に表すために回以降の検出処理のキャッシュとして利用される．

メトリックス Coverage(M0 , M1 ) を定義する．このClone Coverage Analyzer D-CCFinder の出力

メトリックスは，2 つのモジュール M0 と M1 がどのから，ファイル，プロジェクト，およびカテゴリ

程度類似しているかを表すものであり，次式を用いてレベルのコードクローンカバレッジを算出する．

表現される．

Image Generator Clone Coverage Analyzer がCoverage(M0 , M1 ) =生成した定量データから，散布図やヒートマップ

LOC(CM1 (M0 )) + LOC(CM0 (M1 ))LOC(M0 ) + LOC(M1 )を生成する．

4. 実

験

4.1 概

要

ただし:

M0 , M1 : ファイル，プロジェクト，またはカテゴリ，
CM1 (M0 ): M0 の中で，M1 とコードクローンである

本論文での実験対象は，オープンソースオペレー
ティングシステム FreeBSD8) 用のソフトウェアの集部分，

LOC(x): x の行数．

合である Ports システムに含まれているソースファイ

4.2 結ル（オープンソースターゲット）である．表 2 に対象

最小一致字句数☆ を 50，ユニットサイズを 15MBytes☆☆ にソースファイルの規模，表 3 にカテゴリを示す．

果

設定し，D-CCFinder を実行した．実行されたタスクの

オープンソースターゲットは同じプロジェクトの複総数は，269,745 個である．図 4 は全体の散布図を表し

数のバージョンを含んでいる場合がある．たとえばている．この散布図では，1 ピクセルあたり 200x200

Apache web server の場合は，1.3，2.0, 2.1, 2.2 の 4ファイルを表している．200x200 ファイル間で 1 つでつのバージョンが含まれている．これは，古いバージョもコードクローンが存在する場合は，点を描画していンを必要としているユーザやシステムとの下位互換性

る．ファイルレベルでの Coverage(M0 , M1 ) の平均を保つためである．このように，複数のバージョンがは 4%であり，もしこのような縮退を行っていない場

表 3 オープンソースターゲットのカテゴリ一覧
Table 3 Categories in the open source target

Index

Name

Index

Name

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

accessibility
arabicarchivers
astro
audio
benchmarks
biologycad
commsconverters
databases
deskutils
devel
dns
editors
emulators
ﬁnanceftp
graphics
irc
java
lang
mail

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

math
mbone
misc
multimedia
net-imnet-mgmt
net-p2p
net
news
palm
polishprint
sciencesecurityshellssysutils
textprocwwwx11-clocks
x11-fmx11-fonts
x11

合は，これより遥かに点の少ない散布図になると思われる．
図 4 の特徴的な部分を枠で囲んでいる．これらの部分に対して，より詳細に調査を行った．

A この部分のコードクローンは php4 と php5 のソー
スコードが流用されていることを表している．図から読み取れるように，さまざまなカテゴリのプ
ロジェクトに流用されている．

B この部分には X11 関係の 4 つのカテゴリが存在しており，それらの間で多くのコードクローンが検出された．その多くは X Window System の中心☆

最小一致字句数とは，CCFinder がコードクローンを検出する際に用いる閾値である．CCFinder はこの値以上の字句を持つコー
ドクローンを検出する．著者らはこれまでの経験から，新規でコードクローン検出を行う際の閾値として 30 を用いているが，今回の実験対象は同じソフトウェアの複数のバージョンを含む
ことを考慮し 50 とした．
☆☆
ユニットサイズが大きいほどタスク数が減るため，大きいほうがよいのであるが，演習室のマシンスペックを考慮した結果，この値を用いた．実際に，ユニットサイズをこれよりも大きい値にして D-CCFinder を実行したところ，同じソフトウェアの異なるバージョン部分のピースなど，非常に多くのコードクローンを含んでいる部分において，メモリ不足により CCFinder の実行に失敗してしまい，正常にすべてのピースの検出処理を終えることができなかった．

情報処理学会論文誌

6

audio

1959

E

databases

D

devel

A
editors
graphics

lang
mail
mbone
multimedia
net
security
textprocwwwB
x11

textprocwwwsecurity

net

mail
mbone
multimedia

langgraphics

editors

databases

audio

devel

C

x11

図 4 オープンソースターゲット全体の散布図
Fig. 4 Scatter Plot of Inter-Project Code Clone Coverage for the open source Target

的な処理を行っている部分からのコピーであった．

ルを流用しているのは納得できる結果である．

C imake は make に代表されるビルドツールの一種

E カテゴリ audio 内に存在するマルチメディアフレー

であり，X Window System の一部となっている

ムワーク gstreamer とその複数のプラグインが多ソフトウェアである．このソフトウェア自体はカ数の同一ファイルを所持していた．

テゴリ devel に属しているが，X11 関係のソフト

上記のコードクローンを所有しているファイルに対ウェアの多くがこのコピーを所持していた．

して Coverage(M0 , M1 ) を計測したところ，ほとんD カテゴリ devel の大部分で一様なパターンが現わ

どが 100%であった．つまり，これらのファイルはあるれていた．これはソフトウェア binutils のコード

一部ではなく，ファイル全体がコードクローンになっの流用によるものである．binutils はリンカやアていることを表している．すでに述べたように図 4 のセンブラなどその他オブジェクトファイルやアー

1 ドットは 200x200 ファイルを表しているため，特定カイブを扱うためのソフトウェアツール群であり，の 2 つのプロジェクト間でのみコードクローンになっカテゴリ devel に属するソフトウェアがこのツーている部分を発見することは難しい．

Vol. 0No. 0

大規模ソースコードを対象としたコードクローンの検出と可視化

7

これはカテゴリ devel 内に複数バージョンのプロ
ジェクト gcc が存在しているためであり，このコードはカテゴリ lang に含まれるプロジェクトでも流用されていた．

J カテゴリ x11-fonts の値が 46%と最も高い数値であった．このカテゴリに属しているソフトウェア
は少数であり，X Window System からのコードの流用が多く（7 箇所）行われていたため，このような高い数値になっていた．

5. 考

察

5.1 分散環境下での分析について
表 4 に示すように，80 台のコンピュータ上で D-

CCFinder を実行した結果，約 51 時間でコードクロー
ン検出を完了することができた．理論上は，80 台のコ
図5

オープンソースターゲット全体のカテゴリレベルでのヒート
マップ
Fig. 5 Color heatmap for the code clone coverage of theopen source target (category view)

ンピュータを用いることにより 12 時間で検出が完了するはずであるが，実際にはネットワークトラフィッ
クやマスター・スレーブ間の同期，CCFinder の出力の後処理などのため 51 時間を要した．この検出速度

図 5 はカテゴリレベルでの Coverage(M0 , M1 ) のは単一のコンピュータ上で行った場合の約 20 倍であヒートマップを表している．この図から，主対角線上，る．現在，各コンピュータは 100BASE のスイッチでつまりカテゴリ内のカバレッジがカテゴリ間のカバ接続されているので，ギガビットスイッチなど，高速

レッジに比べ高いことが分かる．異なるカテゴリ間のなネットワーク環境を導入することにより，検出速度場合は，Coverage(M0 , M1 ) の値が 25%を超えていの向上が見込まれる．

る箇所は少ない．次に，図 5 の特徴的な部分にどのよ

現在の実装では，Clone Coverage Analyzer と Im-

うなコードクローンが存在していたのかを示す．

age Generator は著者らの研究室内のワークステーショ

F カテゴリ database の値が 41%と非常に高かった．

ン☆ 上で実行される．単一のワークステーションで実これには 2 つの理由がある．１つめの理由はこの行されるため，これらの処理を完了するためには長いカテゴリに属するいくつかのソフトウェアは，複時間を必要としている．しかし，コードクローンの検数バージョンのソースコードが存在したこと，2

出処理と同様に，これらの計算をスレーブノードに分

つめの理由は，ruby や php など異なるプログラ

割して割り当てることにより，処理速度の向上を図る

ミング言語向けにデータベースドライバが提供さことができる．

れている点であった．前者の理由により，ファイ

D-CCFinder をクラスタ計算機やグリッド計算機7)ルの一部分のコードクローンが多く存在し，後者で実現することも可能であろう．クラスタ計算機で実の理由により，ファイル全体のコードクローンが現する場合は，ネットワークの遅延などが減少し，全多く存在した．

表 4 Time elapsed
Table 4 実行時間

G カテゴリ devel の値が 38%であった．このカテゴ
リにはプロジェクト binutils や gcc の複数のバー
ジョンが含まれており，Coverage(M0 , M1 ) の値を押し上げていた．

H カテゴリ ftp と converters の間の値が 37%であった．これらのカテゴリに含まれる複数のソフトウェ
アがプロジェクト php4 と php5 のソースコードを流用しているため，Coverage(M0 , M1 ) の値がIndexer
D-CCFinder

22 分
51 時間

散布図
Clone Coverage Analyzer
Image Generator

23 時間
4 時間

ヒートマップ
Clone Coverage Analyzer
Image Generator

70 時間
2分

高くなっていた．

I カテゴリ lang と devel の間の値が 28%であった．

☆

CPU:Xeon 2.8GHz, Memory: 4GB

情報処理学会論文誌

8体の効率の向上が期待される．グリッド計算機では，大量の入出力データの効率的な分配・回収方法を実現する必要があろう．

1959

かもしれない．
また，散布図自体をより正確に生成する必要がある．
現在の生成方法では，速度とサイズを重視しているた

5.2 CCFinder について

め，精度が悪い（1 ピクセルが 200x200 ファイルを表CCFinder は，広く使われている実用的なツールでしている）．このため，対象全体の状態を大まかに把ある．本論文では，単純な分散処理モデルを用いるこ

握することができるが，小さなプロジェクト間のコーとによって，単一コンピュータ用のアプリケーション

ドクローンの状態を把握することはできなかった．

である CCFinder を用いて，大規模ソフトウェアから短時間でコードクローンを検出することに成功した．
しかし，単一コンピュータ用のアプリケーションを用いることに起因する問題点も存在した．

6. 関 連 研 究
超大規模ソースコードからのコードクローン検出の発想は，メガソフトウェアエンジニアリング10) からの

D-CCFinder 実行前は，コードクローン検出対象ソーものである．メガソウトウェアエンジニアリングとは，スファイルは，ある１つのマシン☆ 上にのみ存在する

既存のソフトウェア分析技術を，広く組織全体やオー（このマシンを以降，データノードと呼ぶ）．各スレー

プンソースのソフトウェア群に対して適用することでブノード上で CCFinder が実行されるため，各ピースある．既存のソフトウェア技術は本来，個々のソフトからコードクローンを検出する前に，必要なファイウェアに対して適用するものであるが，組織規模で適ルをスレーブノードに転送する必要がある．スレーブ

用することにより，組織自体のソフトウェア開発プロ

ノードが 79 台あり，これらすべてが必要なファイルをセスを改善することができる．たとえば，組織（企業

データノードから取得するため，データノードのネッ

や企業内の開発部門）で過去に開発されたすべてのソ

トワークトラフィックが非常に大きく，D-CCFinder のフトウェアからコードクローンを検出することにより，ボトルネックになっている．特に，各スレーブノード

その組織で繰り返し実装されている頻出コードを特定がローカルストレージにキャッシュを持っていない検することができる．そのようなコードを社内ライブラ

出処理の開始直後は，データノードのネットワークト

リとしてまとめることにより，今後のソフトウェア開

ラフィックは最大になる．

発をより効率的に行うことができると思われる．コン

現在の実装では，タスクの割り当ては単純にアイド

ピュータハードウェアの値下がりと，パフォーマンス

ル状態のノードに対して行っている．しかし，どのスの向上により，メガソフトウェアエンジニアリングは

レーブノードがどのファイルをキャッシュとして持つか

現実に可能になってきている．

を管理することにより，ソースファイルの総転送量がさまざまなコードクローン検出手法が提案されてい減少し，より短時間で検出処理を完了できるであろう．

る．Baxter らは抽象構文木を用いた検出手法を提案

5.3 散布図についてしており1) ，Ducasse らは行単位での検出ツールを作

散布図による可視化により，大量のソフトウェア間成している6) . またプログラム依存グラフを用いた検に含まれるコードクローンを容易に特定することがで出手法も提案されている15) ．

きた．仮にそれらのソフトウェアの開発者がこのコー

著者らはこれまでにも CCFinder を用いてコードク

ドクローンの存在をもっと早くに把握していた場合は，ローン検出を行ってきており，このツールに関する知ライブラリなどのより再利用しやすい形でまとめられ識を持っているため，本実験でも CCFinder を用いた．

ていたかもしれない．

CCFinder はこれまでに提案されている検出手法の中今回の対象には，同一プロジェクトの複数のバージョでもスケーラビリティが高く，本実験の目的にあったンが存在していたため，それらの間で大量のコードクツールである．また，ﬁngerprint 技術16) を用いたコー

ローンが検出されており，他のコードクローン情報をドクローン検出も高いスケーラビリティを実現できる隠している（目立たないようにしている）と思われる

ため，超大規模からのコードクローン検出に向いてい部分があった．複数バージョンが存在しているプロジェ

ると考えられる．

クトについては，最新バージョンのみを使うなどの工

オープンソースソフトウェアに対してのコードク

夫をすることによって，より興味深い結果が得られる

ローン検出・分析は既に行われている5),19) ．しかし，それらは 1 つのプロジェクト内のコードクローン検出☆

このマシンは著者らの研究室内にあるネットワーク接続ストレージ（Network Attached Storage）である．

にとどまっており，本研究のように大量のソフトウェ
ア群からコードクローン検出を行ってはいない．

Vol.0No.0

大規模ソースコードを対象としたコードクローンの検出と可視化

7. ま と め
本論文では，超大規模から短時間でコードクローンを検出する手法を提案した．提案手法を分散システム

D-CCFinder として実装し，オープンソースオペレー
ティングシステム FreeBSD 用のソフトウェア集合である Ports システムに含まれるソースファイルに対して適用した．約 4 億行の C 言語で記述されたソース
コードから 51 時間でコードクローン検出を完了することができ，散布図やヒートマップを用いて大まかに
コードクローンの状態を把握することができた．
著者らは，このような大規模ソースコードからのコードクローン検出が，近年問題になってきている著
作権違反に応用できると考えている17) ．たとえば，ソフトウェアライセンスの 1 つである GPL でライセンスされた著作物は，その派生著作物に対しても GPL
でライセンスされなければならない．コードクローン
検出および可視化を行うことにより，GPL でライセンスされたソフトウェアと他のライセンスを持つソフ
トウェアが高い類似度であることが判明した場合は，著作権違反の疑いを指摘することができる．このように，或るソフトウェアと過去に開発されたソフトウェ
アや外部で開発されたソフトウェア間のコードクロー
ンを調査することによって，そのソフトウェアに著作権違反のコードが存在しているかどうかを調査することができる．
本論文は，ソフトウェア分析を分散環境で行うことの有用性を示している．D-CCFinder は超大規模ソー
スコードからコードクローン検出を行うための，単純で実用的なシステムであり，既存のネットワーク環境
を用いて実装されている．
現在の D-CCFinder はプロトタイプシステムであり，5 節で述べたように多くの課題を残している．また，今後は，CCFinder ではなく，ﬁngerprint 技術を用いてコードクローン検出を行うことも検討しており，よりパフォーマンスの向上が見込まれる．
謝辞 大学の演習室を利用するにあたり協力していただいた大阪大学 大学院基礎工学研究科の田島滋人
氏，ならびに情報科学研究科の小泉文弘氏に感謝する．
本研究は一部，文部科学省リーディングプロジェクト「e-Society 基盤ソフトウェアの総合開発」の委託に基づいて行われた．また，日本学術振興会 科学研究費補助金 基盤研究 (A)(課題番号:17200001) および萌芽研究 (No.18650006) の助成を得た．

参

考

9

文

献

1) Baxter, I.D., Yahin, A., Moura, L., Anna, M.
and Bier, L.: Clone Detection Using Abstract
Syntax Trees, Proc. of International Conference on Software Maintenance ’98, Bethesda,
Maryland, pp.368–377 (1998).
2) Bellon, S. and Koschke, R.: A Comparison ofAutomatic Techniques for the Detection of Duplicated Code, Technical report, Institute forSoftware Technology, University of Stuttgart(2003).
3) Brown, A.W. and Booch, G.: Reusing OpenSource Software and Practices: The Impact ofOpen-Source on Commercial Vendors, Proc. ofthe 7th International Conference on Software
Reuse, Lecture Notes in Computer Science,
Vol.2319, Austin, Texas, Springer, pp.123–136(2002).
4) Burd, E. and Bailey, J.: Evaluating Clone
Detection Tools for Use during Preventative
Maintenance, Proc. of the 2nd IEEE International Workshop on Source Code Analysis andManipulation, pp.36–43 (2002).
5) Casazza, G., Antoniol, G., Villano, U., Merlo,
E. and Penta, M.D.: Identifying clones in theLinux kernel, Proc. of the First IEEE International Workshop on Source Code Analysis andManipulation, Florence, Italy, IEEE Computer
Society Press, pp.92–100 (2001).
6) Ducasse, S., Rieger, M. and Demeyer, S.: A
Language Independent Approach for Detecting Duplicated Code, Proc. of the International
Conference on Software Maintenance ’99, Oxford, England, pp.109–118 (1999).
7) Foster, I.: What is the Grid? A Three Point
Checklist (2002). available at http://www-fp.mcs.anl.gov/∼foster/Articles/WhatIsTheGrid.pdf.
8) FreeBSD Project: http://www.freebsd.org/.
9) GNU Project: http://www.gnu.org/.
10) Inoue, K., Garg, P., Iida, H., Matsumoto,K. and Torii, K.: Mega Software Engineering, Proc. of the 6th International PROFES(Product Focused Software Process Improvement) Conference, Oulu, Finland, pp.399–413(2005).
11) Jakarta Project: http://jakarta.apache.
org/.
12) Kamiya, T., Kusumoto, S. and Inoue, K.:
CCFinder: A multi-linguistic token-based code
clone detection system for large scale source
code, IEEE Transactions on Software Engineering, Vol.28, No.7, pp.654–670 (2002).
13) Kapser, C. and Godfrey, M.: Improved Tool

10

情報処理学会論文誌

Support for the Investigation of Duplication in
Software, Proc. of the 21st International Conference on Software Maintenance, Budapest,
Hungary, pp.25–30 (2005).
14) Kim, M., Sazawal, V., Notkin, D. and Murphy, G. C.: An empirical study of code clone
genealogies, Proc. of the 10th European software engineering conference, Lisbon, Portugal,
pp.187–196 (2005).
15) Krinke, J.: Identifying Similar Code with Program Dependence Graphs, Proc. of the 8th
Working Conference on Reverse Engineering,
Suttgart, Germany, pp.301–309 (2001).
16) Li, Z., Lu, S., Myagmar, S. and Zhou, Y.: CPMiner: Finding Copy-Paste and Related Bugs
in Large-Scale Software Code, IEEE Transaction on Software Engineering, Vol.32, No.3, pp.
176–192 (2006).
17) Livieri, S., Higo, Y., Matsushita, M. and Inoue, K.: Very-Large Scale Code Clone Analysis and Visualization of Open Source Programs
Using Distributed CCFinder: D-CCFinder,
Proc. of the 29th International Conference on
Software Engineering, Minneapolis, Minnesota,
pp.106–115 (2007).
18) Rajapakse, D.C. and Jarzabek, S.: An Investigation of Cloning in Web Applications, Proc.
of the 5th International Conference on Web
Engineering, Lecture Notes in Computer Science, Sydney, Australia, Springer, pp.252–262(2005).
19) Uchida, S., Monden, A., Ohsugi, N., Kamiya,T., Matsumoto, K. and Kudo, H.: Software
Analysis by Code Clones in Open Source Software, The Journal of Computer Information
Systems, Vol.XLV, No.3, pp.1–11 (2005).
20) Yamamoto, T., Matsushita, M., Kamiya, T.
and Inoue, K.: Measuring Similarity of Large
Software Systems Based on Source Code Correspondence, Proc. of the 6th International
PROFES (Product Focused Software Process
Improvement) Conference, Oulu, Finland, pp.
530–544 (2005).

1959

肥後 芳樹（正会員）
平成 14 阪大基礎工情報中退．平成 18 同大大学院博士後期課程修了．
現在同大情報科学研究科コンピュー
タサイエンス専攻助教．博士（情報科学）．ソースコード分析，特にコー
ドクローン分析やリファクタリング支援に関する研究に従事．電子情報通信学会，IEEE 各会員．

リビエリシモネ
平成 15 伊パドヴァ大学工学部コン
ピュータ工学科卒．現在大阪大学情報科学研究科博士後期課程に在学．
アスペクト指向プログラミングや
コードクローン分析の研究に従事．

松下誠（正会員）

平成 5 年大阪大学基礎工学部情報工学科卒業．平成 10 年同大学大学
院博士後期課程修了．同年同大学基礎工学部情報工学科助手．平成 14年大阪大学大学院情報科学研究科コンピュータサイエンス専攻助手．平成 17 年同専攻助教授．平成 19 年同専攻准教授．博士（工学）．ソフ
トウェア開発環境，リポジトリマイニングの研究に従事．日本ソフトウェア科学会，ACM 各会員．

井上 克郎（正会員）
昭和 54 年大阪大学基礎工学部情報工学科卒業．昭和 59 年同大学大学院博士課程修了．同年同大学基礎
工学部情報工学科助手．昭和 59〜61
年ハワイ大学マノア校情報工学科助教授．平成元年大阪大学基礎工学部情報工学科講師．

(平成 ? 年 ? 月 ? 日受付)

平成 3 年同学科助教授．平成 7 年同学科教授．平成(平成 ? 年 ? 月 ? 日採録)

14 年大阪大学大学院情報科学研究科コンピュータサ
イエンス専攻教授．工学博士．ソフトウェア工学の研究に従事．日本ソフトウェア科学会，電子情報通信学会，IEEE，ACM 各会員．