クローン検出ツールを用いたソフトウェアシステムの類似度調査
山本 哲男 †

松下 誠 †

神谷 年洋 ‡

井上 克郎 †

† 大阪大学大学院基礎工学研究科〒 560-8531 大阪府豊中市待兼山町 1-3

Phone: 06-6850-6571

Fax: 06-6850-6574‡ 科学技術振興事業団 若手個人研究推進事業
E-mail: t-yamamt@ics.es.osaka-u.ac.jp

二つのソフトウェアシステムが与えられた時，そのシステムの間の違いはどれぐらいあるのか，客観的に知ることは重要である．しかしながら，二つのシステムのからそれらの相違点を定量的な値を計算することは容易ではなかった．
本稿では，クローン検出ツール CCFinder を用いたソフトウェアシステム間の類似度メトリクス CSR(Corresponding

Source-line Ratio) を提案する．類似度 CSR を種々の OS に適用した．また，それらの類似度からクラスタ分析を行い樹状図を作成し，CSR が OS の分類を正しく行えているか検証を行った．さらに，CSR と開発期間の相関を求め，高い相関があることが分かった．
コードクローン，ソフトウェアメトリクス，類似度

Similarity Metric CSR Using Code Clone Detection Tool
Tetsuo Yamamoto† Makoto Matsushita† Toshihiro Kamiya‡ Katsuro Inoue†† Graduate School of Engineering Science, Osaka University
1-3 Machikaneyama, Toyonaka,
Osaka 560-8531, Japan
Phone: 06-6850-6571

Fax: 06-6850-6574‡ PRESTO, Japan Science and Technology Corporation
E-mail: t-yamamt@ics.es.osaka-u.ac.jp

It is important to know a differrence between two software systems objectively. However, it is hard to compute a quantitative difference from these systems. In this paper, we propose a similarity metric CSR(Corresponding Source-line Ratio)
using code clone detection tool CCFinder. We apply CSR to many OSes, and construct an OS genealogy using cluster
analysis. As a result, we can classify OSes using CSR. We also find out that there is a high correlation between CSR anddevelopment period.
Code Clone, Software Metrics, Similarity

1 はじめに二つのソフトウェアシステムが与えられた時，そのシステムの間の違いはどれぐらいあるのか，客観P

Q
R

的に知ることは重要である．いくつかあるシステムのバージョンの間の相違の度合を調べることによって，システムの保守の様子や進化の度合を知ることができる．さらにシステムを改変する際の有益な指針にもなる．例えば，プログラムの大幅な改変を行うよ

図 1: 対応

りも，新たに作り直す方がコストが安くなる場合がある．
システムの改変時にドキュメントが作成されていれば，それを手がかりにして，相違点を知ることは可能であろうが，定量的な値を得ることは容易ではな

いて議論する．4 節では，UNIX OS への適用について述べ，5 節で，そのデータに基づいたクラスタ解析を行なう．6 節で考察し，参考文献との比較を行なう．

2 類似度メトリクス

かった．システムが小規模で，全体の構造を人間が容

本節では，ソースプログラムとして与えられた易に把握できる場合は，そのシステムの個々の構成

二つのソフトウェアシステムの類似度メトリクス

要素について定量的な値を調べ，システム全体の値

CSR(Corresponding Source-line Ratio) を提案する．二とすることができよう．しかし，構造が複雑になり，つのソフトウェアシステムの類似度メトリクスには，数百，数千にも及ぶファイルから構成されるシステ

多くの要素が考えられる．たとえば，ファイルの数

ムでは，何らかの機械的な処理により，自動的に求めや行数，ファイル名の違いなどである．以降，我々がることが必須となる．

提案する類似度メトリクス CSR の形式的な定義を行

本研究では，ソースプログラムとして与えられた二つのソフトウェアシステムの類似度メトリクス

い，それを求めるための具体的な方法を説明する．

2.1 類似度の定義

CSR(Corresponding Source-line Ratio) を提案する．本

一つのファイルや複数のファイルから構成される

稿では，CSR の形式的な定義を与え，それを求める

ソフトウェアシステムの間の関係を定義するために，ための現実的な方法を示す．そして，実際に CSR をファイルやソフトウェアシステムを抽象的にあらわ

種々の UNIX 系 OS のいくつかの版に適用した結果

す “ プロダクト” を用いる．ここでは簡単化のためにを示す．

プロダクトは，その要素の集合と考え，P = {p1 , …

さらに，得られた CSR を元にして，クラスタ分析, pm } と書く．いま P をファイルとすると，各 pi はを行い OS のバージョンを分類し，バージョンの樹状

ファイルの各行，P をソフトウェアシステムとすると，図を作成した．その結果，ここで提案する CSR を類

ソフトウェアシステムを構成する各ファイルとなる．

似度メトリクスとしてを用いた樹状図は，UNIX の開

二つのプロダクト P = {p1 , …, pm }, Q = {q1 , …

発者が示した系譜図にほぼ対応することが分かった．

, qn } に対し，対応 R ⊆ P × Q が得られるとする．

また，他のいくつかのメトリクス（名前が一致する

今，P と Q の R に対する類似度 S(0 ≤ S ≤ 1) をファイル数の割合，対応が取れるファイル数の割合など） を類似度として用いてクラスタ分析を行った結果との比較を行った．さらに，二つのバージョンの間

次のように定義する．

S(P, Q) ≡|{pi |(pi , qj ) ∈ R)}| + |{qi |(pi , qj ) ∈ R)}|
|P | + |Q|の CSR と開発期間の間に相関のあることも分かった．

これは，図 1 のように対応 R に含まれる P , Q の以下，2 節では，類似度メトリクス CSR を定義す

要素数を P と Q の総要素数で割ったものである．Rる．3 節では，CSR を現実的に求めるための方法につに関係しない P , Q の要素が増えることによって S は

下がる．R = φ では，S = 0 となる．また，P と Qが同じものの時，∀i(pi , qi ) ∈ R となり S = 1 となる．

2.2 類似度の適用方法と CSR定義した類似度を実際のソフトウェアシステムやファイルに適用する方法を考える．

1. P , Q をファイルとし，pi , qi をそのファイルの中の行とする．R は，ファイルの差分抽出ツール diffにより与えられる関係とすると，S をファイル間の類似度を定義し計算で求めることができる．

2. P , Q をソフトウェアシステムとし，pi , qi をそのソフトウェアシステムを構成するファイルとする．

R を同じファイル名を持つファイルの対応とする．こ3 CSR の求め方
本節では，前節で定義した類似度メトリクス CSRを求めるための対応 R の具体的な求め方にについて説明する．さらに，与えられた二つのソフトウェア
システムから類似度を計算するアルゴリズムについて述べる．

3.1 アプローチ
すべてのファイルのすべての行に対しての対応を求めるためには，各行に対してその行と同じ行が存在するかどうか調べればよい．
このようなコードの重複を求めるための手法はすでにいくつか存在する．

の場合，容易にシステム間の類似度を計算できるが，クローン検出ツール CCFinder[2] は，複数のソー

名前を変更した場合や名前は同じだがファイルの中

スコードを入力としてコードクローンを出力するツー

身を変更した場合などは，類似度は直感的な値とはルである．CCFinder はソースコードをプログラミン

異なってしまう．また，ファイルの大きさにかかわら

グ言語の文法に沿ってトークン列に変換する．そのず均等な重みで類似度を計算するため，直感に合わ際，複数のソースも一つのトークン列に連結される．

ない場合もある．たとえば，小さな多数のファイル

また, ソースコード中の空白とコメントは生成されるのみが対応にあり，少数の大きなファイルが対応してプログラムの機能に影響しないので無視される．さいない場合，高い類似度になってしまう．

らに，実用的に意味のあるクローンのみを検出する

3. P , Q をソフトウェアシステムとし，pi , qi をそために，そのトークン列の変換を行う．これは，パラのソフトウェアシステムを構成するファイルとする．

メータ置き換え（名前が異なっても等価にする）な

R をファイル同士の類似度が最も高いファイルへのどである．そして，そのトークン列を比較し，ソー対応とする．こうした場合，ファイル名の考えや中スコードが一致しているかどうか調べる．一致した

身の変更には対応できる．しかし，ファイルの大き部分トークン列をコードクローンと呼ぶ．

さが反映されない．また，すべての組み合わせでファUNIX の diff コマンドは，二つのファイルの各行

イル間の類似度を求めなければならず，大きな手間に対して発見アルゴリズム LCS[3, 4] を利用して，そがかかる．

のファイル間の行単位の差分を求める．この差分は，4. P , Q をソフトウェアシステムとし，pi , qi を P ,一方のファイルからもう一方のファイルを生成可能

Q それぞれの各ファイルの各行とする．直感的にはなファイルとなっている．diff コマンドの特徴は構文

各ファイルを連結したファイルの各行を考える．何ら

解析などを必要とせず差分の計算が行えるところにかの方法で各行の対応 R が与えられたとする．類似ある．

度は，ファイル名やファイルの大きさに影響されず，

ここで，CCFinder と diff を用いて，対応を求め

直感的に近い値が得られることが期待される．本稿でる．まず CCfinder を用いてコードクローンを検出すは，この方法を用いたソフトウェアシステム間の類似

る．検出されたクローンを持つファイル間に対して度メトリクスを CSR(Corresponding Source-line Ratio)diff を実行する．CCfinder と diff によって同一行とと呼ぶ．

判断された行の間に対応があるものとする．2 種類の以降では，どのようにして，R を決め，CSR を求めるかを詳しく述べる．

ツールを組み合わせることで，類似度の正確性を向上させる．

3.2 アルゴリズム

加えることにより，同一行と判断できる行が増加す

CSR を求めるためのアルゴリズムを以下に示す．

る．そのため，類似度はより正確に類似をあらわす値

入力：二つのソフトウェアシステム P と Qとなると考える．後節で述べる適用実験の結果，対出力：P と Q の類似度 CSR (0 ≤ S ≤ 1)

応をもつ行は一割程度増加する．
また，diff だけを用いた対応の抽出の場合，ディレ

Step1: 前処理生成されるプログラムの機能に影響を与えない部分を取り除く．この処理は，用いられている
プログラミング言語によって異なる．たとえば，

C 言語で記述されたファイルの場合，コメント部分，空行をすべて取り除く．これにより，diffを実行した時の類似度の精度を向上させる．

Step2: CCFinder の実行

クトリ構造を保ったまま二つのソフトウェアシステ
ムを入力とする場合と，一つのソフトウェアシステ
ムのすべてのファイルの全行を巨大な一つのファイルにまとめたのを入力にする場合の二種類が考えられる．前者の場合，二つのソフトウェアシステムの間で同一の構造を持つ必要があり，ファイル名の変更やディレクトリ構造の変化に追従できない問題が生じる．後者の場合，結合するファイルの順番に問題が生与えられた二つのソフトウェアシステムを入力

じる．diff で利用しているアルゴリズムでは，文字列として CCFinder を実行させる．実行させる際のの入れ替えに対応できないためである．つまり，ファオプションとして，最低一致トークン数を 20 とイル A，B が存在するとき，A，B と結合したファイ

する．最低一致トークン数とは，出力すべき一

ルと B，A と結合したファイルに対して，diff を実行

致するトークン列の長さの最低値を表す．

したとき，これらの二つのファイルは同一と判断できない．そのため，CCfinder と diff を組み合わせて

Step3: diff の実行対応を求める方法を採用している．

CCFinder の実行の結果，一つでもクローンペア
がみつかったペアのファイルにすべてに対してdiff を実行する．
Step4: 対応の抽出

4 適用
本節では，類似度メトリクス CSR を，実際のソフ
トウェアシステムに適用する．適用するソフトウェア

CCFinder で検出されたクローンのトークン列かシステムとして，最近の UNIX 系 OS を用いた．

ら，実際のファイルの一致している行同士を求

4.1 適用するシステム

める．さらに，diff で求まった差分情報から一致適用するソフトウェアシステムは，BSD 系 UNIXしている行同士を計算する．CCFinder か diff ので あ る 4.4-BSD Lite，4.4-BSD Lite2 と ，こ れ ら

どちらかで一致している判断された行同士に関から派生した OS である FreeBSD[8]，NetBSD[9]，係を定義する．

OpenBSD[6] である．FreeBSD，NetBSD，OpenBSD

Step5: CSR の計算
CSR の定義より計算する．ただし，二つのソフ
トウェアシステムの全行数は前処理後の行数を用いる．

はオープンソースとして開発が現在も進められている．この三つの OS からは，4.4-BSD Lite 以降にリリースされたバージョンから現在までのバージョン
までの中から主要なバージョンを選びだした．その結果，FreeBSD は 6 バージョン，NetBSD は 6 バー

対応を求めるにあたって，CCFinder だけでなく，ジョン，OpenBSD は 9 バージョンを選び出した．適

diff も用いる理由は対応の正確性の向上である．C 言語

用した OS は総数 23 個となる．これらの各 OS に対のプリプロセッサ命令（#include 行など）は CCFinder

し，すべての組み合わせを考えて類似度 CSR を計測

では除外される．そのため，diff を用いた差分情報をした．

表 1: 各 OS のファイル数と行数
FreeBSD
バージョン
ファイル数
行数
NetBSD
バージョン
ファイル数
行数
OpenBSD
バージョン
ファイル数
行数

2.0
891
2288682.0.5
1018
2750162.1
1062
2972082.2
1196
3692563.02142
6360051.0
2317
4530261.1
3091
6057901.2
4082
822312

1.3
5386
1029147

1.4
7002
13782742.0
4200
8989422.1
4987
1007525

2.2
5245
1066355

2.3
5314
10791634.0
2569
8785902.4
55071129371

4.4BSD
バージョン
ファイル数
行数

1.5
7394
1518371
2.5
5815
12328582.6
6074
1329293

2.7
6298
1438496Lite
1676
317594

Lite2
1931
4113732.86414
1478035

表 2: 類似度一覧（一部）FreeBSD 2.0

FreeBSD 2.0.5

FreeBSD 2.1

FreeBSD 2.2

FreeBSD 3.0

FreeBSD 4.0

4.4BSD-Lite

4.4BSD-Lite2

NetBSD 1.0

NetBSD 1.1

NetBSD 1.2

NetBSD 1.3

1.000
0.833
0.794
0.550
0.315
0.212
0.419
0.290
0.440
0.334
0.255
0.205

0.833
1.000
0.943
0.665
0.392
0.264
0.377
0.266
0.429
0.348
0.269
0.227

0.794
0.943
1.000
0.706
0.421
0.286
0.362
0.258
0.411
0.336
0.265
0.225

0.550
0.665
0.706
1.000
0.603
0.405
0.226
0.179
0.291
0.254
0.225
0.201

0.315
0.392
0.421
0.603
1.000
0.639
0.138
0.133
0.220
0.193
0.190
0.208

0.212
0.264
0.286
0.405
0.639
1.000
0.101
0.100
0.140
0.152
0.158
0.179

0.419
0.377
0.362
0.226
0.138
0.101
1.000
0.651
0.540
0.421
0.331
0.259

0.290
0.266
0.258
0.179
0.133
0.100
0.651
1.000
0.450
0.431
0.436
0.366

0.440
0.429
0.411
0.291
0.220
0.140
0.540
0.450
1.000
0.691
0.553
0.445

0.334
0.348
0.336
0.254
0.193
0.152
0.421
0.431
0.691
1.000
0.783
0.622

0.255
0.269
0.265
0.225
0.190
0.158
0.331
0.436
0.553
0.783
1.000
0.769

0.205
0.227
0.225
0.201
0.208
0.179
0.259
0.366
0.445
0.622
0.769
1.000

FreeBSD 2.0
FreeBSD 2.0.5
FreeBSD 2.1
FreeBSD 2.2
FreeBSD 3.0
FreeBSD 4.0
4.4BSD-Lite
4.4BSD-Lite2
NetBSD 1.0
NetBSD 1.1
NetBSD 1.2
NetBSD 1.3

3 節の類似度を計測するアルゴリズムの Step1: の言語依存部分の処理は，以下の通りである．

• 計測対象は OS のカーネル部分のみとし，カーネルを生成するのに必要なファイルだけを取り出す．

• 対象言語は C 言語のみとし，拡張子が .c .h のファイルのみを計測対象とする．

• コメントと空行は全て消去する．

4.2 適用結果

を図 2 に示す．自分自身を除くと，最も類似度が高いバージョンは 0.706 の FreeBSD 2.1 である．次期バージョンである FreeBSD 3.0 との類似度は 0.603 であり，これは三番目に近い値となっている．二番目の類
似度は FreeBSD 2.0.5 の 0.665 である．FreeBSD 3.0
で，大幅な変更が加えられていることが読みとれる．
表 1 のファイル数と行数の変化を見ると，ファイル数
は約 1.8 倍増加し，行数は約 1.7 倍増加しており，それ以前の変更量とは異なることが分かる．

FreeBSD と NetBSD の間の CSR を図 3 に示す．
FreeBSD 2.0 から FreeBSD 2.2 までは，NetBSD 1.0 と各 OS の総ファイル数と行数を表 1 に示す．この最も類似度が高く，NetBSD のバージョンが上がるに

表の値は，Step1: を行った後の結果に測定した値でつれ類似度は減少していく．しかしながら，FreeBSDある．類似度を計測した値の一部を表 2 に示す．

3.0，FreeBSD 4.0 に関しては NetBSD 1.3 と類似度が

表 2 の FreeBSD だけに注目すると，各バージョン

他の NetBSD のバージョンと比べ高くなっている．あの中で，最も類似度が高い値を持つのはそのバージョ

るバージョンを基準に考え，比較するバージョンをンの前後のどちらかである．リリースした時期により上げていくと類似度の変化は減少する．FreeBSD と前のバージョンか後のバージョンのどちらかになる．

NetBSD という基本的に異なる開発（開発者や開発ポ

たとえば，FreeBSD 2.2 と他のバージョンとの CSRリシー）で行われている場合，類似度が上がる原因



4.4BSD Lite(1994/03)

 !

NetBSD 1.0(1994/10)

 

 
 

FreeBSD 2.0(1994/11)

 

4.4BSD Lite2(1995/06)

FreeBSD 2.0.5(1995/06)

   

FreeBSD 2.011995/11)
NetBSD 1.1(1995/11)

 

NetBSD 1.2(1996/10)

 

FreeBSD 2.2(1997/03)

 


OpenBSD 2.0(1996/10)
OpenBSD 2.1(1997/06)
OpenBSD 2.2(1997/12)

NetBSD 1.3(1998/01)"$#&%'%)(+*-, .'/10"2#3%'%)(+*-,.'/0)/54"2#3%'%)(+*-, .'/6"2#3%'%)(+*7, .8/5.

"$#&%'%)(+*-, 9'/10"$#&%8%)(+*7, :)/0

OpenBSD 2.3(1998/05)
OpenBSD 2.4(1996/12)

FreeBSD 3.0(1998/10)
NetBSD 1.4(1999/05)

OpenBSD 2.5(1999/05)
OpenBSD 2.6(1999/12)
OpenBSD 2.7(2000/06)
OpenBSD 2.8(2000/12)

図 2: FreeBSD 2.2 との CSR
FreeBSD 4.0(200/03)
NetBSD 1.5(2000/12) 

#$ %&
#$ %&
#$ %&
#$ %&








図 4: BSD 系 UNIX 派生図


 


1

  


 
 !

"

図 3: FreeBSD と NetBSD の CSR
としては，他方の OS にある機能を追加するために，

0.5

0FreeBSD 2.0
FreeBSD 2.0.5
FreeBSD 2.1
FreeBSD 2.2
FreeBSD 3.0
FreeBSD 4.0
4.4BSD Lite
4.4BSD Lite2
NetBSD 1.0
NetBSD 1.1
NerBSD 1.2
OpenBSD 2.0
OpenBSD 2.1
OpenBSD 2.2
OpenBSD 2.3
OpenBSD 2.4
OpenBSD 2.5
OpenBSD 2.6
OpenBSD 2.7
OpenBSD 2.8
NetBSD 1.3
NetBSD 1.4
NetBSD 1.5

ソースコードをコピーした場合や，両方の OS に同一
ファイル取り込んだ場合が考えられる．
図 4 に BSD 系 UNIX の派生ツリーを示す [7]．この

図 5: 類似度 CSR を用いた樹状図
る．作成した樹状図と OS の系譜図を比較し，似てい図は，FreeBSD，NetBSD．OpenBSD といった OS がる点，異なる点についての議論を行う．

どのように派生し，いつリリースされたかをあらわし

5.1 樹状図ている．FreeBSD 3.0，NetBSD 1.3 は，共に 4.4BSD

Lite2 を取り込んだ最初のバージョンであることを示している．つまり，FreeBSD，NetrBSD に取り込まれた 4.4BSD Lite2 のソースコードの行が対応し，類似度が増加した．
これらのことから，CSR がソフトウェアシステムの類似度を正しく表しているといえる．

類似度 CSR を各個体間の距離として，クラスタ分析を行う．クラスタ間の距離には平均距離を用い計算する．クラスタ分析を行い，その結果から得られた
樹状図を図 5 に示す．横軸は結合距離を表している．
図 5 から，FreeBSD，NetBSD，OpenBSD がどのように分類できるか考える．最も大きな分類としては，最終的なクラスタ統合が行われている部分で，5 分析
本節では，4 節で適用して得られた類似度 CSR を元にして，クラスタ分析を用いてバージョンを分類
し，バージョンの樹状図（デンドログラム）を作成す

FreeBSD と NetBSD + OpenBSD という分類である．
類似度 CSR を用いたクラスタ分析による分類が正し
く OS の種類の分類を反映している．
次に，NetBSD と OpenBSD の分類を見てみる．

1

0.5

0

FreeBSD 2.0
FreeBSD 2.0.5
FreeBSD 2.1
FreeBSD 2.2
FreeBSD 3.0
FreeBSD 4.0
4.4BSD Lite
4.4BSD Lite2
NetBSD 1.0
NetBSD 1.1
NerBSD 1.2
OpenBSD 2.0
OpenBSD 2.1
OpenBSD 2.2
OpenBSD 2.3
OpenBSD 2.4
OpenBSD 2.5
OpenBSD 2.6
OpenBSD 2.7
OpenBSD 2.8
NetBSD 1.3
NetBSD 1.4
NetBSD 1.5

表 3: FreeBSD 4.0 と Linux 2.2.15 の類似度

CSR

ファイル数の類似度

0.031

0

表 4: バージョン間のリリース間隔（ヶ月）
FreeBSD 2.0
FreeBSD 2.0.5
FreeBSD 2.1
FreeBSD 2.2
FreeBSD 3.0
FreeBSD 4.0

図 6: 一致したファイル数を用いた樹状図
1

0.5

2.0
0
7
12
28
47
64

2.0.5
7
0
5
21
40
57

2.1
12
5
0
16
35
52

2.2
28
21
16
0
19
36

3.0
47
40
35
19
0
17

4.0
64
57
52
36
17
0

0

FreeBSD 2.0
FreeBSD 2.0.5
FreeBSD 2.1
FreeBSD 2.2
FreeBSD 3.0
FreeBSD 4.0
4.4BSD Lite
4.4BSD Lite2
NetBSD 1.0
NetBSD 1.1
NerBSD 1.2
OpenBSD 2.0
OpenBSD 2.1
OpenBSD 2.2
OpenBSD 2.3
OpenBSD 2.4
OpenBSD 2.5
OpenBSD 2.6
OpenBSD 2.7
OpenBSD 2.8
NetBSD 1.3
NetBSD 1.4
NetBSD 1.5にそれぞれ示す．共に図 5 と同様の結果が得られることが分かる．この理由は，これらの OS すべてがBSD 系由来のファイル構造，ファイル名を持つためだと考えられる．ファイル名命名規則やファイルの階層構造が決まったポリシーで開発が行われている
場合は，単純にファイル名を用いた分析も可能であることがいえる．
さらに．由来が異なる二つの OS であり同時期に

図 7: 同一ファイル名を用いた樹状図

OpenBSD 2.0 を除いたすべての OpenBSD のバージョンが統合され，NetBSD 1.1 と統合されている．

OpenBSD 2.0 に関しても NetBSD 1.2 と統合された
後，NetBSD 1.1 に統合されている．図 4 から分かる
ように，OpenBSD は NetBSD 1.1 から派生してできた OS である．樹状図でも，OpenBSD が NetBSD 1.1から派生していることを示している．また，図 4 から NetBSD 1.2 と OpenBSD 2.0 は同時期にリリースされたバージョンであり，また，OpenBSD 2.0 は最リリースされた FreeBSD 4.0 と Linux2.2.15 の類似度を計算した．計算する類似度は CSR と全ファイル数のうちのディレクトリ名を含んだファイル名が一致するファイル数の割合である．結果を表 3 に示す．ファイル数の割合は 0 であり，一つも同一のファイル名がみつからかった．しかし，CSR の値は，0.031 となった．異なる開発形態では，ファイル数の割合だけでは，必ずしも類似度を表せるとは限らないと考えら
れる．

6 考察

初のバージョンであることも分かる．これらの原因か

CSR は類似度を表す値であるが，CSR を計算する

ら NetBSD 1.2 と OpenBSD が高い類似度を示した．

過程で各行の対応を求めている．この各行の対応を

5.2 他の類似度用いると，実際にファイルのどの行が他のファイルのCSR による類似度の有効性を調べるため，各個体

行と同じであるか知ることが可能である．CSR の値

間の距離を CSR 以外の類似度を用いてクラスタ分析

だけでなく，これらの対応する行の情報も得ることを行った．用いた類似度は，全ファイル数のうちのが出来，類似度を用いソフトウェアシステムを参照，

CCFinder でクローンが検出されたファイル数の割合

改変する場合に役に立つ．

と，全ファイル数のうちのディレクトリ名を含んだ

図 4 に示したリリース時期と類似度との間に相関

ファイル名が一致するファイル数の割合である．これがあるかどうか計算をした．FreeBSD のリリース間

ら二つの類似度を用いて作成した樹状図を図 6，図 7

隔を計算した結果を表 4 に示す．CSR とリリース間隔

の相関は，-0.973 であった．表 1 の行数の単純な増減

検証，類似度と再利用プログラミングとの関係の計

数とリリース間隔との相関は，0.528 であった．CSR測などが挙げられる．

とリリース間隔との間には強い負の相関があることがわかる．また，行数の増減数より CSR がリリース間隔との相関が高い．このことから，ある二つのバージョンの類似度を計測することで，そのリリース間
隔を知ることが可能である．CSR は，言い換えるとソースコードの変更していない部分の割合を示しているため，相関が高いということは，開発が滞りな

参考文献[1] Baxter, I. D., Yahin, A., Moura, L., Sant’Anna, M.
and Bier, L.: Clone Detection Using Abstract Syntax Trees, Proceedings; International Conference
on Software Maintenance (Koshgoftaar, T. M. andBennett, K.(eds.)), IEEE Computer Society Press,
pp. 368–378 (1998).

く一定に行われているといえる．
類似度を求める研究としてさまざまな研究がある．

[2] 神谷年洋, 楠本真二, 井上克郎: ”コードクローン検

Baxter らは AST を利用したクローン検出手法を提案

出における新手法の提案及び評価実験”, 電子情報している [1]．しかしながら，類似度を求める定義は

通信学会技術研究報告、SS2000-42〜52, Vol. 100,

あるが，その値をどのように用いるかや実際にシス

No. 570, pp. 41–48 (2001).

テムに適用した結果などなく，定量的な評価を行って[3] Miller, W. and Myers, E. W.: A File Compari-はいない．また，[5] では，提案した類似度を実際のson Program, Software- Practice and Experience,

ソフトウェアに適用し，類似度が妥当であるか検討

Vol. 15, No. 11, pp. 1025–1040 (1985).

しているが，対象ソースコードが COBOL であり，提案する類似度も他のプログラミング言語に対応することが難しいといった問題がある．

[4] Myers, E. W.: An O(N D) difference algorithm andits variations, Algorithmica, Vol. 1, pp. 251–256(1986).

7 まとめ
本稿では，ソースプログラムとして与えられた二つのソフトウェアシステムの類似度メトリクス[5] 長橋賢児: ”類似度に基づくソフトウェア品質の評価”, 情報処理学会研究報告 2000-SE-126,

Vol. 2000, No. 25, pp. 65–72 (2000).

CSR(Corresponding Source-line Ratio) を提案した．
具体的には，類似度 CSR はクローン検出ツール[6] OpenBSD: . “http://www.openbsd.org/”.

CCFinder と diff コマンドを用い計算される．そし[7] Schneider,

W.:

The

UNIX

sys-

て，実際に CSR を FreeBSD，NetBSD，OpenBSD と

tem

tree:

Research

and

BSD.

いった種々の UNIX OS のいくつかのバージョンに適“ftp://ftp.freebsd.org/pub/FreeBSD/branches/-

用した．適用結果から，類似度 CSR は二つのソフト

current/src/share/misc/bsd-family-tree”.

familyウェアシステム間の類似性を正しくあらわしていると考えることが出来る．さらに，得られた類似度 CSRを元にして，クラスタ分析を行い，各 OS のバージョンを分類し，バージョンの樹状図を作成した．その結果，提案する CSR を類似度としてを用いた樹状図
は，OS の分類を派生通りにあらわしていることがが分かった．また，二つのバージョンの間の CSR と開発期間の間に強い相関があることも分かった．
今後の課題としては，さらなる類似度の妥当性の[8] The FreeBSD Project: . “http://www.freebsd.org/”.
[9] The

NetBSDFoundation“http://www.netbsd.org/”.

Inc.:.