論 文
大規模ソフトウェアシステムを対象としたファイルクローンの検出佐々木裕介†

山本 哲男††

早瀬 康裕†††

井上 克郎†

File Clone Detection for a Large Scale Software System
Yusuke SASAKI† , Tetsuo YAMAMOTO†† , Yasuhiro HAYASE††† ,and Katsuro INOUE†

あらまし 大規模なソフトウェア群中にはソースコードの等しいファイル，ファイルクローンが大量に存在す
る．発注先から納品されたソフトウェア製品や，新たに導入しようとしているオープンソースソフトウェアのシステム群に含まれるファイルクローンについて調べることは，システムの整理及び再構築の際やシステム群の全体像を把握するときなどに有用となる．そこで我々は大量のソースコードから高速にファイルクローンを検出できるツール FCFinder を開発し，大規模なソフトウェアシステムであり既存研究で多くのファイルクローンの存在が予測されている，FreeBSD Ports Collection に適用した．結果として，ports の約 68%のファイルがファ
イルクローンとなっていることが明らかになった．本論文では，FCFinder で用いているファイルクローン検出
手法について説明し，FCFinder を様々なソフトウェア群に適用した結果について考察を行う．
キーワード

ファイルクローン，ハッシュ，べき乗則，オープンソースソフトウェア

する．

1. ま え が き

そこで我々は，より調査コストの低いファイル単位で大規模なソースコード群からなるソフトウェアシスのクローン，ファイルクローンを高速に検出するツー

テムではファイルの流用が頻繁に行われており，複数

ル FCFinder を開発した [4]．ここでは，コメントをのプロジェクトにまたがるコードクローンが大量に存除外するなどの正規化を行ったときにソースコードが在することが予測される [1]．発注先から納品されたソ等しくなるファイルの関係をファイルクローン関係とフトウェア製品や，新たに導入しようとしているオー

呼び，それぞれのファイルをファイルクローンと呼ぶ．

プンソースソフトウェアのシステム群に含まれるファファイルクローン関係は同値関係であり，その同値類

イルクローンについて調べることは，システムの整理となるファイル集合をファイルクローンセットと呼ぶ．

及び再構築の際やシステム群の全体像を把握するとき

ファイルクローンは既存のコードクローン検出ツールなどに有用となる．しかし，既存のコードクローン検

CCFinder [2] でも検出可能であるが，FCFinder は検出手法 [2], [3] はソースコードのミクロな部分に着目

出の対象をファイルクローンに限定しているため，よするものであり，大規模なソースコード群からなるソり高速にファイルクローンを検出できる．ファイルク

フトウェアシステム内にコードクローンがどの程度，ローンの分析結果は，どれくらいの規模で含まれているかを調査するにはコ•利用するシステム群の全体像を把握するストが高すぎる．また，発見した大量のコードクロー•

同様な修正が必要な箇所の発見を効率化するンをコード単位で整理・統合すると多大なコストを要•システムの整理や再構築の際の指標にする†††などの用途に用いることができる．例えば，新たに利大阪大学大学院情報科学研究科，吹田市
Graduate School of Information Science and Technology,

用しようとしているオープンソースソフトウェアのシ

Osaka University, Suita-shi, 565–0871 Japan

ステム群や発注先から納品されたソフトウェア製品な

日本大学工学部，郡山市
College of Engineering, Nihon University, Koriyama-shi,†††

どの一部で，

963–8642 Japan•

どのようにサブシステムの間に依存関係があり，筑波大学システム情報工学研究科，つくば市•

もし不具合が発見された場合には影響がどう波

Graduate School of Systems and Information Engineering,
University of Tsukuba, Tsukuba-shi, 305–8573 Japan

電子情報通信学会論文誌

及するかc （社）電子情報通信学会 2011
D Vol. J94–D No. 8 pp. 1423–1433 

1423

電子情報通信学会論文誌 2011/8 Vol. J94–D No. 8といった情報を事前に調査しておくことができる．また，あるファイルで問題が発覚した場合には，同じファ

2. 関 連 研 究

イルを探し修正する必要があるが，ファイルクローン

近年，ソースコード解析技術として，コピー&ペー

情報に基づいて修正するファイルを知ることができる．

ストや類似ソースコード，コードクローンの検出技術

更に，システムの整理や再構築を行う際には同じ部分

が注目を集めている．特にソースコードの流用に関すをまとめる作業（リファクタリング）を行うことがある情報は保守において重要であり，剽窃検出，関連バるが，そのための情報をファイルクローン分析の結果

グの発見など様々な用途で用いられている [3], [5], [6]．

から得ることができる．ファイルクローンはファイル

コードクローン検出手法として，トークンベースのであるため，コード片であるコードクローンに比べ分検出手法や関数を単位とした検出手法などが研究さ析結果に基づいてリンクによりファイルを代替し整理れており，そのためのツールもいくつか開発されていするなどの応用を行いやすい．

る [2], [7]．Mayrand らは 21 種類のメトリクスを用い，本研究ではファイルクローンに関する以下の問題を詳しく調べる．

類似した関数単位での検出を試みた [3]．ここでいうメトリクスとは，ソフトウェアの評価するための尺度でRQ1 ファイルクローンが大規模なソフトウェア群内あり [8]，特にソースコードから抽出される特徴に対すにどれくらい含まれているのかる数値を指す．また，彼らはオブジェクト指向のプロ

RQ2 それらのファイルクローン群はどのような性質

グラムに対する類似クラスの検出を行った [9]．

をもっているか

これらの研究では比較的大きさの限られたソフトウェ

本論文では，我々が開発した大規模なソースコード

アに対して解析を行っているが，Zhenmin らはより規からファイルクローンを検出できるツール FCFinder

模の大きいソースコードからコピー&ペーストを検出について説明した後，FreeBSD Ports Collection（以し，それに関するバグを発見するツール CP-Miner [6]降，ports と略記する）やそのソースコードアーカイを開発し，FreeBSD のソースコードに適用した．

ブ，Linux Kernel，Open Oﬃce などのソースコード

更に大規模なソースコードに対するコードクローを対象として行ったファイルクローンの調査についてン検出として，Livieri らは分散処理を用いたコード記述する．ports は port と呼ばれるファイル群（ここクローン検出ツール D-CCFinder を開発し，実験をではこれをプロジェクトと呼ぶ）の集まりであり，世の行った [1]．Livieri らの研究によって，大規模なソース中で利用されている多くのソフトウェアのソースコー

コード群からなるソフトウェアシステムでは，複数のドを利用している．また ports に含まれるプロジェク

プロジェクトにまたがってソースコードの等しいファト間では多くのファイル共有が行われていることがあ

イルが存在することが判明した．しかし我々の調べたるが，その定量的，定性的な性質は知られていないた

限りでは，大規模なソフトウェア群中からソースコー

め，解析対象としては非常に興味深い．更にファイルドの等しいファイルを検出するような研究は行われてクローンの調査を行うことにより，ports 内のプロジェいない．

クトでもし不具合が発見された場合に，他のプロジェ
クトに影響がどう波及するかを予測することもできる．

3. FCFinder

2. では関連研究として既存のコードクローンに関す

この章では，我々が大規模なソースコードを対象とる研究について取り上げる．3. では，開発したツール

したファイルクローンの検出を高速に行うために開発

FCFinder がどのように高速なファイルクローン検出

した，File Clone Finder（以下，FCFinder）についを実現しているかについて説明する．4. では，portsて説明する．

内部に含まれるファイルクローンの割合や，その度数

FCFinder は複数のプロジェクトのソースコード群

分布について調べた調査実験について記述する．5. で，を入力として受け取り，プロジェクト内のファイルク

本研究で対象とする問題についての考察を行った上で，ローン関係やプロジェクトをまたぐファイルクローン

我々の行った研究についてのまとめを行い，今後の課関係を検出し，ファイルクローンセットとしてデータ

題について述べることとする．

ベースへ出力する．データベースに出力したファイ
ルクローンセットに関する情報は，他のツールから呼び出して利用できるようになっている．処理の概要を

1424

論文／大規模ソフトウェアシステムを対象としたファイルクローンの検出

図 1 FCFinder
Fig. 1 FCFinder.

図 1 に示す．以下，図 1 に示す各フェーズを順に説明する．

3. 1. 3 MD5 Hash Calculation
正規化を終えた解析対象となるすべてのファイルそ3. 1 Analysis Phase

れぞれに対して，MD5 [10] によりハッシュ値を算出

3. 1. 1 Indexing

する．ファイルから算出されたハッシュ値は，データ

今回解析対象とする .c，.h ファイル及びプロジェ

ベースへ格納しておく．

クトを特定する．更に特定されたファイル群と各ファ

3. 2 Grouping Phase

イルが属しているプロジェクトをデータベースへ格納

このフェーズでは，3. 1. 2 で正規化した内容が同一する．

3. 1. 2 Tokenization

であるファイル集合を，ファイルクローンセットとしてグループ化する．

FCFinder はコメント文やインデントなど細かな変すべてのファイルの組合せについてファイル内容を更を無視するために，コメント文の削除及び字句解析

全比較すると時間がかかる．そこでファイル内容の全によりファイルを正規化する．このフェーズではまず比較はハッシュ値の一致するファイルのみに対して行

ファイル中のコメント文を削除し，その後に字句解析う．ハッシュ値が異なるファイルはそのファイル内容

によりソースコードをトークンへ切り分ける．ソースも必ず異なっているため，内容が同一であるファイル

コードをトークンへ切り分けることにより，インデン集合を検出する際には，ハッシュ値が異なるファイル

トなどの連続する空白や改行記号は，同一の空白記号同士の比較は不要となる．

へ置き換えられる．
またこのフェーズでトークン数が 15 より小さなファ
イルを取り除く．トークン数が 15 より小さなファイ

3. 2. 1 Hash Matching Check
ハッシュ値の同じファイルをグループ化する．

3. 2. 2 Exact Matching Check

ル 100 ファイルを ports から無作為に選出し調査を

3. 2. 1 で作成したグループを，3. 1. 2 で正規化し行った結果，変数宣言や関数宣言，マクロ定義，ファた内容が同一であるグループに分割する．分割によっ

イルのインクルードなどの処理しか記述されていなて作成されたグループを，ファイルクローンセットとかった．このため本ツールではトークン数が 15 よりしてデータベースに格納する．

小さなファイルをソースコードとしてあまり意味をもたないものと判断し，検出の対象外として解析対象から外している．

4. 実験

FCFinder を用いて，[1] の実験で用いられた，2007
年 9 月 6 日時点での ports のうち，拡張子が .c と .h1425

電子情報通信学会論文誌 2011/8 Vol. J94–D No. 8に対してファイルクローンの検出を行った．実験には及び .h ファイルの数とデータ量も記してある．なお，

CPU 2.50 GHz，メモリ 16 GByte を積んだ 64 bit マ

ファイル収集時の make conﬁg のデータはデフォルト

シンを利用した．ファイルクローンの検出で FCFinder

値である．また移転によりダウンロードできなかったが使用した最大メモリ量は 4 GByte 未満であった．

などの理由で入手が困難だったファイルは除外した．

4. 1 ソースコードの収集方法

4. 2 解析対象に対する事前調査

前述のように，本実験では ports を利用してソース

ファイルクローンの分析を行う前準備として，解析

コードの収集を行った．ports は，port と呼ばれる単対象に含まれているファイルについて簡単な考察を行位で，システムへのインストールやアンインストール

うために，ファイルサイズとプロジェクトごとのファを行う．この port に含まれるファイル群をここではイル数について度数分布を計測した．

プロジェクトと呼ぶ．プロジェクトは，カテゴリーに

図 3 はファイルごとのサイズを集計した度数分布

分けて管理されている．一般に，ports のプロジェク

グラフである．X 軸はファイルサイズ，Y 軸はファイトをインストールする際には，ソースコードのアーカ

ル数を示し，両対数軸をとっている（以降のグラフでイブをインターネット上の外部サイトから取得し，必は X 軸 Y 軸ともに対数軸をとっているものとする）．

要に応じてカスタマイズやコンパイルを行った上で，このグラフではサイズが増えるほどファイル数が線形

その全部または一部をシステムにインストールする．

に減少しており，べき乗則 [11], [12] と呼ばれる法則

そのため，異なったカスタマイズを行ったり，インスが成り立っている．どれくらいべき乗則に従っている

トールする部分が異なるなどといった理由で，複数のか確認するため，ファイルサイズの累積度数分布に対プロジェクトが同一のアーカイブを用いる場合が数多し線形回帰分析を行ったところ，自由度調整済み寄与く存在する．

率 R∗2 は 0.9024 となった（以降，自由度調整済み寄例えば図 2 に示すように，アーカイブ F に対する

与率 R∗2 は累積度数分布に対して計算したものとす

バイナリがプロジェクト F1，プロジェクト F2 として（注 1）．一般的にこの値は 0.8 程度あれば回帰モデル
る）

別々の場所に展開，利用されることがある．この場合，

F1，F2 に対して生成されるバイナリは別のものであることが多い．
本実験におけるソースコードの収集では，すべてのプロジェクトごとにソースコードのアーカイブを取得
し，個別に展開を行った．そのため，異なるプロジェ

Table 1

表 1 解析対象の構成
Mining target characteristics.

Number of ﬁles (.c, .h)
Number of projects
Number of categories
Total size

1,355,0987,209
45
11.2 GByte

クトのソースコードとして，同一のソースコードアー
カイブが多重に収集されている．
収集した時点での，カテゴリー数及びプロジェクト
数を表 1 に示す．表 1 には，収集の結果得られた .c

図 3 ファイルごとのサイズ度数分布
Fig. 3 File size distribution.

図 2 ソースコードアーカイブのダウンロード及び展開
Fig. 2 Source archives downloading and extracting.

1426

（注 1）
：自由度調整済み寄与率 R∗2 とは，あるデータについて線形回
帰分析を行ったとき，そのデータが回帰分析によって得られたモデルにどれくらい従っているかを示す数値であり，0 から 1 の値をとる [13] す
べてのデータが回帰モデルに従っていれば R∗2 は 1 になる．

論文／大規模ソフトウェアシステムを対象としたファイルクローンの検出に従っているといえる [14], [15]．そのため今回調査し用いているため，インストール時には異なるバイナリ

た ports におけるファイルサイズの度数分布は，高いが生成される．

割合でべき乗則に従っているといえる．

また図 4 C にはファイル数が 6,506 のプロジェクト

しかしその一方で，比較的ファイルサイズの値が大が 14 存在していた．これらはアーキテクチャごとにきい範囲で線形回帰モデルから外れている部分がいく用意された RTEMS OS のクロスコンパイラであり，

つか見つかった．例えば図 3 A の中でもサイズが約

多くのファイルを共有していた．これらのプロジェク

1.6 MByte であるファイル数は 59 という大きな数値

トは同じソースコードアーカイブを利用しているが，を示している．より詳しく調べてみたところ，サイズ

インストール時にはそれぞれソースコードに異なるカが約 1.6 MByte であるファイルはすべて互いにファイ

スタマイズを加えコンパイルしている．これらのこと

ルクローンとなっており，PHP5 の time zone に関すから，収集したソースコードの中には，多くのファイるファイルであった．

ルクローンが存在することが予測される．

図 4 はプロジェクトごとに .c，.h ファイル数を集

また，図 5 に示すのはプロジェクトごとのファイル

計した度数分布グラフである．X 軸 Y 軸ともにどち

サイズ合計を集計した度数分布グラフである．X 軸はらも対数軸であり，X 軸はプロジェクトごとに含まれそのプロジェクトが含んでいる .c，.h ファイルのサイている .c，.h ファイルの数を，Y 軸はプロジェクト数

ズ合計を表す．Y 軸はサイズの等しいプロジェクト数を示す．自由度調整済み寄与率 R∗2 を調べたところを表す．自由度調整済み寄与率 R∗2 は 0.8214 となっ

0.8868 となり，高い割合でべき乗則に従っていること

た．このことから，プロジェクトごとのファイルサイ

が分かった．

ズについてもべき乗則が成り立っていると考えられる．

しかしこのグラフについても X の値が大きい範囲

図 5 にも D のようにいくつか回帰モデルから外れで線形回帰モデルから大きく外れている部分がいくつている部分があるため，サイズが 50 MByte 以上のか見つかった．図 4 B では，ファイル数が 1,316 のプ

プロジェクトに対して詳細な調査を行った．表 2 はロジェクトが 59，ファイル数が 1,070 のプロジェクト

プロジェクトサイズが大きいものを，上から 10 プロ

が 61 存在していた．より詳細な調査を行ったところ，

ジェクト表示したものである．この表に示されていこれらのほとんどは PHP4/PHP5 の拡張ライブラリ

る emulators/xmame は emulators/xmess の後継プを生成するためのプロジェクトであり，互いに大量のロジェクトであり同一組織で作られている．このようファイルクローンを共有していた．図 4 B に含まれるに同じ組織で作成されたプロジェクトが順位の近い位

プロジェクトの具体例としては www/PHP5-tidy な

置に見つかるものが，ほかにもいくつか発見された．

どがある．これらのプロジェクトは同一のソースコー

このことから，対象とするファイル群の中には，同一

ドアーカイブを利用しているが，それぞれソースコー

組織によって作られたバージョンの異なるプロジェク

ドアーカイブに含まれるファイルのうち異なる部分をトなどが存在することが予測される．

図 4 プロジェクトごとに含まれるファイル数の度数分布
Fig. 4 Distribution of the number of ﬁles insideproject.

図 5 プロジェクトごとのサイズ度数分布
Fig. 5 Project size distribution.

1427

電子情報通信学会論文誌 2011/8 Vol. J94–D No. 8
表 2 プロジェクトサイズ上位 10 件
Table 2 Top 10 project sizes.
順位
1
2
3
4
5
5
5
5
9
9

project
palm/prc-tools
lang/nhc98
x11/xorg-clients
net/nxserver
net/vncx11/xorg-manpages
x11/xorg-libraries
devel/imake-6
emulators/xmess
emulators/xmame

project size (MByte)
93.8
89.4
72.0
66.0
64.1
64.1
64.1
64.1
61.1
61.1

4. 3 ファイルクローンの解析
我々はファイルクローンについての解析を行うため，

図 6 ファイルごとのサイズ度数分布（ファイルクローン
のみ）
Fig. 6 File size distribution. (ﬁle clones only)

FCFinder を用いてファイルクローンを検出した．ファ
イルクローン数は 915,409，ファイルクローン合計サ
イズは 7.6 GByte となった．これは全体の約 68%がファイルクローンであることを示している．ports ではプロジェクトの大部分が共通のファイルを利用しているためと考えられる．
また見つかったファイルクローンのうち，コメント
やインデントなどに違いのあるファイルの数は，全ファ
イルクローン中の 26.01%（238,154 ファイル）であった．具体的な事例としては以下のようなものがある．

•

cad/cider と cad/spice の間に，インデントの異なるファイルクローンが見つかった．

•

database/ﬁrebird-server と database/ﬁrebird-

図 7 ファイルごとのサイズ度数分布（ファイルクローン除く）
Fig. 7 File size distribution. (without ﬁle clones)

client の間に，異なるソースコード自動生成プログラ
ムにより生成されたファイルクローンが見つかった．

るが，こちらもグラフ全体の傾向はあまり変化がない．

cad/cider と cad/spice はともに回路・デバイスのシ

これらのことから，ファイルクローンについても一ミュレーションを行うソフトウェアである．Firebird

般的なソースコードと同じように，べき乗則という性はオープンソースのデータベースであり，見つかった質が成り立っていることが分かる．

ファイルクローンのコメント部分には，そのソース

ファイルクローンについてより詳しい解析を行うた

コードを生成したソースコード自動生成プログラムがめ，図 8，図 9 の二つの度数分布グラフを作成した．

記述されていた．

図 8 はファイルクローンセットごとにそのファイ

ファイルクローンが特殊なファイルサイズの分布を

ルクローンが全ソースコード中に登場する回数を集計

もっていないか確認するため，ファイルクローンのみ

した度数分布グラフである．X 軸は一つのファイルクを抽出しファイルサイズについての度数分布グラフをローンセット中に含まれるファイルクローン数を，Y

図 6 に構築した．この図 6 は，図 3 に比べあまり変軸はファイルクローンセット数を示す．

化はない．自由度調整済み寄与率を計算したところ全体として，ファイルクローン数が大きいファイル

0.9602 と上がっており，図 3 と比較するとよりべき

クローンセットほど数が少ないことが分かる．自由乗則に近づいた形となっている．

度調整済み寄与率 R∗2 は 0.8508 となり，ファイルク

次にファイルクローンのみを除外したファイルサイ

ローンセット当りのファイルクローン数についても高ズについての度数分布グラフを図 7 に示す．図 6 よい割合でべき乗則が成り立っていることが判明した．

り更に自由度調整済み寄与率が 0.9902 と上がっていしかし外れ値となっている部分がいくつか見られる．

1428

論文／大規模ソフトウェアシステムを対象としたファイルクローンの検出数も 2 倍になっていた．
図 9 は，プロジェクトごとに他のプロジェクトとファイルクローンをいくつ共有しているかを集計した
度数分布グラフである．X 軸は 1 プロジェクト当りに含まれる，他のプロジェクト内のファイルとファイル
クローン関係となっているファイルクローンセットの数を表す．Y 軸はプロジェクト数を表す．
図 9 の全体の特徴として，他プロジェクトと共有のあるファイルクローン（以下，共有されているファイ
ルクローン）数が多いプロジェクトほど，数が少ない
図8

1 ファイルクローンセット当りに含まれるファイル
クローン数の度数分布
Fig. 8 Distribution of population of ﬁle clone set.

ことが分かる．自由度調整済み寄与率 R∗2 は 0.8263となった．
図 9 H では，共有されているファイルクローン数が849 のプロジェクトが 56 見つかった．これらはマル
チメディアフレームワークである GStreamer 用プラ
グインのソースコードアーカイブをベースとして作成されたプロジェクトであり，PHP4/PHP5 と同様に大量のファイルを共通して利用していた．
更に図 9 I では，共有されているファイルクローン
が 1,304 のプロジェクトが 59，共有されているファイ
ルクローンが 1,055 のプロジェクトが 61 見つかった．
これらはすべて PHP4/PHP5 のソースコードアーカ
イブを利用しており，図 4 B 及び図 8 E と対応関係にあった．図 9 I に含まれるプロジェクトには 4. 2 で
図9

1 プロジェクト当りに含まれるファイルクローン数の度数分布
Fig. 9 Distribution of ﬁle clones in project.

述べた www/PHP5-tidy プロジェクトも含まれていた．www/PHP5-tidy プロジェクトの全ファイル数は

1,316 であったが，このうち共有されているファイル
図 8 E では図 4 B に対応するファイル群が見つかっ

クローン数は 1,304 であった．一部のファイルが共有た．例えばファイルクローン数が 59 であるファイル

されていないのは，同じソースコードアーカイブを利クローンセットの中には，www/PHP5-tidy に含まれ用していても，一部のファイルに修正を行っているた

るファイルが確認された．

めと考えられる．

図 8 F では，ファイルクローン数が 120 の部分だけ共有されているファイルクローン数が 5,000 以上

ファイルクローンセット数が 419 となっている．よりの図 9 J でも，共有されているファイルクローン数

詳しく調査してみたところ，これらのファイルクローが多いにもかかわらず，プロジェクト数が突出して多ンセットは 419 ファイルを一組として PHP4，PHP5

い部分がある．より詳細な調査を行ったところ，同

関連の 120 箇所のプロジェクトで利用されていた．こじ組織で作成されており，共有されているファイルク

れら 120 のプロジェクトのうち，61 が PHP4 をベー

ローン数が近いプロジェクトが複数見つかった．表 3スとしているプロジェクト，59 が PHP5 をベースとは，図 9 上の H に示す範囲のプロジェクトを共有さしたプロジェクトであった．

れているファイルクローン数が大きいものから順に加えて図 8 G に示すファイルクローン数が 240 であ表示したものである．例えば共有されているファイル

るファイルについて調査してみたところ，図 8 F に出

クローン数が 7,415 から 7,033 のプロジェクトには，現する PHP4/PHP5 関連の 419 ファイルとセットにOpenOﬃce.org に関連するものが集中している．ほなっていることが分かった．これらのファイルは 1 プ

かにも Mozilla.org のプロジェクトが集中している箇

ロジェクトにつき二つずつ含まれていたため，出現回

所や GDB 関連のプロジェクトが集中している箇所，
1429

電子情報通信学会論文誌 2011/8 Vol. J94–D No. 8
表3

共有されているファイルクローンの多いプロジェク
ト上位 10 件
Table 3 The number of ﬁle clone sets with otherprojects top 10.

順位
1
2
2
2
5
5
7
8
9
10

project
palm/prc-tools
lang/gfortranlang/gcc41-withgcjawt
lang/gcc41
editors/openoﬃce.org-1.1-devel
editors/openoﬃce.org-1.1
editors/ooo-build
editors/openoﬃce.org-2.0
editors/openoﬃce.org-1.0
editors/openoﬃce.org-2.0-devel# of ﬁle clones
9,332
7,500
7,500
7,500
7,415
7,415
7,232
7,062
7,051
7,033

表 4

ports で利用されているアーカイブ群に対するファイルクローン検出結果
Table 4 File clone detection for archive ﬁles used in
ports.
# of archives# of ﬁles# of ﬁle clones% of ﬁle clones

11,0201,313,187
563,547
42.91

トのうち gcc41 と gcc41-withgcjawt (java)，gcc42，

gfortran を示す．これらはおおよそ 7,000 のファイルク
ローン関係を有している．図 10 (b) は OpenOﬃce.orgの 3 プロジェクトを示しており，7,515 から 8,191のファイルクローン関係を有している．図 10 (c) では Thunderbird と Firefox，Firefox-devel，Seamon-key (integrated network tool)，XULRunner (application development kit) がおよそ 6,000 のファイル
クローン関係を有していることを示している．これらは異なるアーカイブをダウンロードして利用しているが，同じ組織内で管理されている．

4. 4 考察

図 10 から，多くのプロジェクトの間でファイルク
ローン関係をもつファイルが存在することが分かる．
また図 9 に示すとおり，プロジェクト間で共有されているファイルクローン数は大部分がべき乗則に従っているが，一部ファイルクローン数が大きく突出している部分が見受けられる．そこでファイルクローン数が突出している部分についてより詳細に調べたところ，
同じソースコードアーカイブがプロジェクトごとに何度も展開され，一部修正して利用されているケースがいくつか見つかった．

4. 4. 1 ports が利用しているソースコードアーカ
イブの分析•

Nodes show the projects.

•

Edges between projects show the number of file clone re-lations between two projects.

図 10 プロジェクト間のファイルクローン関係
Fig. 10 Project relations with ﬁle clones.

4. 1 で示したソースコードの収集方法では，見つかるファイルクローンが非常に多くなる．そこで我々は，各プロジェクトが必要に応じてダウンロードを行う対象であるソースコードアーカイブ（以降，単にアーカ
イブと呼ぶ）自体についても分析を行った（注 2）．取得さPHP 関連のプロジェクトが集中している箇所などがれたアーカイブ数は 11,020 で，その中に含まれるファ複数発見された．

イル数は総計 1,313,187 であった（表 4）．ファイル数

図 10 は図 9 H 中に含まれるプロジェクト間のファが非常に多いのは，前述の実験で収集したとき（表 1）

イルクローン共有関係を示している．各ノードはプロ

よりも ports のプロジェクト数が増えたためである．

ジェクトを，エッジはそれぞれのプロジェクトに含ま

表 4 によるとファイルクローンの割合が 42.91%とれているファイル間に存在している，ファイルクロー

非常に高くなっているが，これは同じソフトウェアのン関係の総計を示している．
図 10 (a) は GNU Compiler Collection プロジェク
1430

（注 2）
：この実験では 2010 年 11 月 4 日現在 ports で利用されているアーカイブ群を対象とした．

論文／大規模ソフトウェアシステムを対象としたファイルクローンの検出

アーカイブでも，プロジェクトによっては異なるバー

る，他のアーカイブ内のファイルとファイルクローン

ジョンをダウンロードするケースがあることが大きな関係となっているファイルクローンセットの数を表す．

要因として挙げられる．例えば，gcc についてはバー

Y 軸はアーカイブ数を表す．こちらも図 9 と比較する

ジョン 2.7.2 及び 4.1.0，4.4.2 のアーカイブが含まれと外れ値が非常に減っており，自由度調整済み寄与率ていた．なお，最も多くのファイルクローンを含んでも高い (R∗2 = 0.955)．

いたのは gcc 4.4.2 であった．

4. 4. 2 その他のソフトウェアシステムの分析

図 11 は，ファイルクローンセットごとにそのファ

また，検出されるファイルクローンが ports ほど多イルが全ソースコード中に登場する回数を集計した

くないと考えられる次のソフトウェアシステム群につ度数分布グラフである．X 軸は一つのファイルクロー

いてもファイルクローンの分析を行った．

ンセット中に含まれるファイルクローン数を，Y 軸は•Linux Kernel 2.6.35.7

ファイルクローンセット数を示す．図 8 と比較すると•OpenOﬃce 3.2.1

外れ値が非常に減っており，自由度調整済み寄与率もそれぞれの構成を表 5 に，ファイルクローン検出結果

高い (R∗2 = 0.9722)．

を表 6 に示す．表 5 の ﬁle types は，解析対象とした

図 12 は，アーカイブごとに他のアーカイブとファファイルの拡張子を示すものである．

イルクローンをいくつ共有しているかを集計した度数

表 6 のとおり，Linux Kernel 2.6.35.7 でも割合は分布グラフである．X 軸は 1 アーカイブ当りに含まれ少ないがファイルクローンが検出された．ファイルク
ローンセットごとにそのファイルが全ソースコード中に登場する回数を集計したところ，そのべき乗分布に対する自由度調整済み寄与率は 0.8414 となった．

OpenOﬃce 3.2.1 でもファイルクローンが検出された（表 6）．ファイルクローンセットごとにそのファイルが全ソースコード中に登場する回数を集計したとこ
ろ，そのべき乗分布に対する自由度調整済み寄与率は0.8301 となった．
これらの調査から，ports 以外のプロジェクトにもファイルクローンが含まれており，分布もべき乗則に従っていることが判明した．
図 11

1 ファイルクローンセット当りに含まれるファイル
クローン数の度数分布
Fig. 11 Distribution of population of ﬁle clone set.
(archives used in ports)

4. 4. 3 アーカイブ間で共有されているファイルク
ローン
また 4. 4. 1 の調査により，ports でダウンロードされたアーカイブ群について，異なるアーカイブ間で共有されているファイルクローンがいくつか見つかった．

(1) データの圧縮/展開を行うライブラリ zlib のファイルが Mozilla や Python などをはじめとする多Table 5表 5 解析対象の構成
The target characteristics.

software system
Linux Kernel 2.6.35.7
OpenOﬃce 3.2.1

図 12

1 アーカイブ当りに含まれるファイルクローン数の度数分布
Fig. 12 Distribution of ﬁle clones in archives.
(archives used in ports)

ﬁle types.c, .h.c, .h, .java# of ﬁles
26,2476,858

表 6 ファイルクローン検出結果
Table 6 File clone detection results.
software system
Linux Kernel 2.6.35.7
OpenOﬃce 3.2.1# of ﬁle clones
332
305% of ﬁle clones
1.26
4.45

1431

電子情報通信学会論文誌 2011/8 Vol. J94–D No. 8
表7 解析時間
Table 7 Analysis time.

くのアーカイブで利用されている．

(2) libpng や libjpeg といった画像処理ライブラ

StepIndexing
Tokenization
MD5 Hash Calculation
Hash Table Creation
Exact Matching CheckTotal

リのファイルが Mozilla や OpenCV などをはじめとする多くのアーカイブで利用されている．

(3) Mozilla の JavaScript 実 行 エ ン ジ ン で あ る
OSSP のソースコードが FreeSWITCH でも使われ
ている．

Time
9.42h
1.13h
6.61 h
17.16 h(4) Boehm GC というガーベッジコレクレターがMozilla や GCC，Kaﬀe など多くのアーカイブで利用されている．

(5) libﬃ のファイルが gcc や smalltalk などで利用されている．
これらの共有が起こっている理由として，例えば (1)ても約 3 倍の速度向上である．
解析速度に関して改善すべき点としては，データ
ベースのアクセス時間削減が挙げられる．データベー
スへのアクセス回数はキャッシュを有効に利用することで削ることができるが，使用できるキャッシュにはに関しては，Firefox などのウェブブラウザではプラ限りがある．FCFinder のキャッシュの利用の仕方にグインインストールの際に zlib を利用しており，また，は改善の余地があり，今後も速度向上が見込まれる．

Python ではデータ圧縮/展開の機能を提供するためにまた表 7 に示すように，今回の実験では Exact

zlib を用いているためであった．その他の共有も，シMatching に 6.61 時間を費やしているが，今のところ

ステムの一部の機能を実装するために他のシステムや

MD5 値の衝突は起こっていない．よって MD5 値のライブラリを利用していることが理由で起こっていた．

比較だけでも高い精度を出すことは可能だと予測され4. 4. 4 解 析 精 度るが，4. 4. 4 のような解析精度を維持するためには検出されるファイルクローンセットが正しいものでExact Matching は必須である．

あるかどうか，実際に検出されたファイルクローン
セットについて 50 セット確認を行ったが，すべて 1.

5. む す びにおいて定義したとおりのファイルクローンセットで

1. において述べた問題に対して得られた考察を述あった．
また CCFinder [2] が検出したファイルクローンのべる．
まず RQ1 について，今回対象とした ports には，

うち無作為に選んだ 50 個のファイルクローンの対にファイルクローン数 915,409（合計サイズ 7,6 GByte）

ついて FCFinder でも検出可能か調査したが，すべてが含まれていることが確認された．これは全体の約のクローンペアが検出できることを確認した．

68%であり，ソフトウェアパッケージ内に含まれるファ以上の調査では，FCFinder は再現率・適合率ともに 100%であることが確認された．しかしながらより厳密に解析精度を評価するには，今後もサンプル数を

イルのほとんどがファイルクローンであることを示している．

増やしていく必要がある．

RQ2 については以下のような結果が得られた．
• ports から検出されたファイルクローンのうち4. 4. 5 解 析 速 度

26.1%がコメントやインデントに違いの見られるもの

CCFinder では 10.8 GByte のソースコードを解析であった．

する場合，1CPU (2.8 GHz)，メモリ 2 GByte を積ん•

またファイルサイズの分布については，ファイ

だ PC で約 40 日を要し．また同じソースコードを D-

ルクローンのあるなしに関係なくべき乗則に従う傾向

CCFinder で解析するのに PC 80 台 (CPU 1.0 GHz)があることが分かった．

で約 51 時間かかっている [1]．

ファイルクローンはコードクローンに比べ，検出が今回の実験では，データベースアクセスも含めてす容易であり，応用も行いやすい．その一方でファイル

べての解析を 1CPU (2.50 GHz)，メモリ 4 GByte でクローンに関する研究はあまり行われてこなかったた

約 17.16 時間で終えている（表 7）．実行環境が異なる

め，今後はファイルクローンについてより詳しく研究ため厳密な比較は困難であるが，CCFinder と比較す

し，FCFinder を使った大規模パッケージの管理や品ると約 50 倍以上の速度である．D-CCFinder と比べ

質評価，FCFinder より使い勝手の良い検索システム1432

論文／大規模ソフトウェアシステムを対象としたファイルクローンの検出の開発といった応用につなげていきたい．
謝辞

氏に多くの有益なコメントを頂いた．本研究は一部，
文部科学省リーディングプロジェクト「e-Society 基
盤ソフトウェアの総合開発」の委託に基づいて行われた．また，日本学術振興会科学研究費補助金基盤研究（A）（課題番号：21240002）の助成を得た．
文[1]“Power-laws in a large object-oriented software system,” IEEE Trans. Softw. Eng., vol.33, no.10,

本論文の執筆中，Simone Livieri 氏，市井誠

献pp.687–708, 2007.
[13]

久米

均，飯塚悦功，入門統計的方法 2 回帰分析，岩波書店，1987.
[14] P. Louridas, D. Spinellis, and V. Vlachos, “Powerlaws in software,” ACM Trans. Softw. Eng.
Methodol., vol.18, no.1, pp.1–26, 2008.
[15]

M.E.J. Newman, “Power laws, pareto distributions
and Zipf’s law,” Contemporary Physics, vol.46,

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

pp.323–351, Dec. 2005.

“Very-large scale code clone analysis and visual-（平成 22 年 8 月 2 日受付，23 年 4 月 14 日再受付）

ization of open source programs using distributed
CCFinder: D-CCFinder,” 29th IEEE International
Conference on Software Engineering, pp.106–115,
Minneapolis, MN, 2007.
[2]

佐々木裕介

T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder:
A multilinguistic token-based code clone detection
Softw. Eng., vol.28, no.7, pp.654–670, 2002.

平 21 阪大・基礎工・情報卒．平 23 同大
大学院博士前期課程了．修士（情報工学）．
在学中ソフトウェア類似性に関する研究に

J. Mayrand, C. Leblanc, and E.M. Merlo, “Experi-従事．現在，富士通研究所に勤務．

system for large scale source code,” IEEE Trans.
[3]

ment on the automatic detection of function clones ina software system using metrics,” 12th IEEE International Conference on Software Maintenance, pp.244–
253, Monterey, CA, 1996.
[4]山本

Y. Sasaki, T. Yamamoto, Y. Hayase, and K. Inoue,

平 9 阪大・基礎工・情報卒．平 14 同大

Proc. 7th IEEE Working Conference on Mining Soft-

大学院博士課程了．同年科学技術振興機構研究員．平 16 立命館大学・情報理工学部
情報システム学科・講師．平 20 同大准教

R. Koschke, et.al, 3rd International Workshop on
Software Clones, Kaiserslautern, Germany, 2009.
http://www.informatik.uni-bremen.de/st/IWSC/

[6]

（正員）

“Finding ﬁle clones in FreeBSD ports collection,”ware Repositories, pp.102–105, ACM, May 2010.
[5]

哲男

Z. Li, S. Lu, S. Myagmar, and Y. Zhou, “CP-Miner:

授．平 23 日本大学・工学部情報工学科・准教授．博士（工学）．ソフトウェア開発支援
ツールの研究に従事．情報処理学会，IEEE 各会員．

Finding copy-paste and related bugs in large-scale
software code,” IEEE Trans. Softw. Eng., vol.32,

早瀬

no.3, pp.176–192, 2006.
[7]

S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and平 14 阪大・基礎工・情報卒．平 19 同大大学院博士課程了．同年同大特任助教．
平 22 東洋大学・総合情報学部・助教．平E. Merlo, “Comparison and evaluation of clone detection tools,” IEEE Trans. Softw. Eng., vol.33, no.9,
pp.577–591, 2007.
[8]

23 筑波大学・システム情報工学研究科・助教．オープンソースソフトウェア開発，ソフトウェア保守の研究に従事．博士（情報N.E. Fenton and S.L. Pﬂeeger, Software Metrics: A
Rigorous and Practical Approach, 2nd ed., Course
Technology PTR., 1998.

[9]

康弘

科学）．情報処理学会，IEEE Computer Society 各会員．

E. Merlo, G. Antoniol, M.D. Penta, and V.F.
Rollo, “Linear complexity object-oriented similar-

井上

ity for clone detection and software evolution analyses,” 20th IEEE International Conference on SoftR. Rivest, “The MD5 message-digest algorithm,”

報・助手．昭 59〜61 ハワイ大マノア校・情報工学科・助教授．平元阪大・基礎工・情報・講師．平 3 同学科・助教授．平 7 同

RFC 1321 (Informational), April 1992.
http://www.ietf.org/rfc/rfc1321.txt[11]

M. Mitzenmacher, “A brief history of generative
Internet Mathematics, vol.1, no.2, pp.226–251, 2003.

学科・教授．博士（工学）．平 14 阪大・情報・コンピュータサイエンス・教授．ソフトウェア工学の研究に従事．情報処理学会，日本ソフトウェア科学会，IEEE，ACM

G. Concas, M. Marchesi, S. Pinna, and N. Serra,

各会員．

models for power law and lognormal distributions,”[12]（正員：フェロー）昭 54 阪大・基礎工・情報卒．昭 59 同大
大学院博士課程了．同年同大・基礎工・情ware Maintenance, pp.412–416, Illinois, CA, 2004.
[10]

克郎

1433