論ソフトウェア基礎・応用論文特集

文

主要処理に着目したメソッド単位のコードクローン検出
長瀬

義大†

石原

知也†

楊

嘉晨†

肥後

芳樹†

井垣

宏†

楠本

真二†

堀田

圭佑†

Method-Based Clone Detection Focused on Core Processes
Yoshihiro NAGASE† , Tomoya ISHIHARA† , Jiachen YANG† , Keisuke HOTTA† ,Yoshiki HIGO† , Hiroshi IGAKI† , and Shinji KUSUMOTO†

あらまし ソフトウェア開発において，多くのソフトウェアで頻繁に利用される機能をまとめたライブラリの利用は，ソフトウェアの信頼性や開発効率の向上に有用である．そのようなライブラリに含めるべき機能を特定するためには，大規模なプロジェクト群に存在するコードクローンを検出することが有益であると考えられる．
そのため，このようなコードクローンを高速に検出することを目的としたメソッド単位の検出手法が提案されている．しかし既存手法では，プログラムの主要処理が同じメソッドであっても副次処理が異なるためにコードク
ローンとして検出されない場合がある．そこで，副次処理に関するコードを除去した上でメソッド単位のコード
クローン検出を行う手法を提案する．この手法により，メソッドの主要処理が同じであれば，たとえその中に存在している副次処理が異なっていても一つのライブラリ化候補として検出することが可能になる．
キーワード

コードクローン，ライブラリ作成，大規模データセット，ソフトウェア保守

1. ま え が き的とした手法として，ファイル単位のコードクローン

ソフトウェア開発において，ライブラリの利用はソ

クローン検出手法 [1], [4]〜[8] が提案されている．

検出手法 [2], [3]，並びにスケーラブルな細粒度コード

フトウェアの信頼性や開発効率の向上に有用である．

ファイル単位のコードクローン（以降ファイルク

これは，開発したいプログラムの機能が既にライブラローン）検出手法 [2], [3] では，ソースコードをファイリに含まれている場合，開発者がその機能を実装する

ル単位で比較することによりファイルクローンの検出必要がないためである．

を行う．しかしこれらの手法では，ファイル単位でし開発者がこのようなライブラリの恩恵を受けるため

か比較を行わないため，ファイルの一部のみがコードには，必要とする機能がライブラリに含まれている必クローンである場合には検出することができない．

要がある．そのためには，頻繁に利用される機能をラ

スケーラブルな細粒度コードクローン検出手法

イブラリ化しておく必要がある．ライブラリ化すべき[1], [4]〜[8] では，大規模なデータセットから細粒度で機能を特定するためにコードクローン検出手法は有益

コードクローン検出を行う．これらの手法はファイルであると考えられる．

クローン検出手法では検出できない，ファイルの一部

コードクローンとは，ソースコード中に存在する同のみのクローンを検出することが可能であるが，速度一，あるいは類似したコード片のことである．ソース

面でファイルベースの手法に劣っている．また，細粒

コードの再利用などの理由により，複数のソフトウェ

度な検出手法では検出単位が細かすぎるため，機能のアにまたがるコードクローンが多数存在することが示

一部のみを含むコードクローンを多く検出してしまう．

されている [1]．現在，このような複数のソフトウェア

そのため，ファイルベースの手法，細粒度な手法ともにまたがるコードクローンを高速に検出することを目にライブラリの作成に利用するには不十分である．
これに対し石原らは，複数のソフトウェアからライ†

大阪大学大学院情報科学研究科，吹田市
Graduate School of Information Science and Technology,
Osaka University, Suita-shi, 565–0871 Japan

電子情報通信学会論文誌

ブラリ化の候補を高速に検出することを目的とした，メソッド単位の検出手法を提案している [9]．この手法

c 一般社団法人電子情報通信学会 2013
D Vol. J96–D No. 11 pp. 2669–2680 

2669

電子情報通信学会論文誌 2013/11 Vol. J96–D No. 11

では，メソッドを単位として検出を行うため，コード

うに特定の機能をもったプログラムをまとめたものでクローン情報から簡単にライブラリ化を行うことがである．開発者はライブラリ化されたプログラムを使用

きる．また，メソッドからハッシュ値を算出し，そのすることで必要な機能を新しく実装する必要がなくな

ハッシュ値を用いて検出を行うため，巨大なデータセッ

り，開発コストを小さくすることができる．また，ラトに対しても十分高速に実行することが可能である．

イブラリ化されたプログラムは既存のソフトウェアにしかしこのメソッド単位の手法では，プログラムのおいて繰り返し検証されているため，開発者は信頼性目的とする機能が同じであってもエラー処理などの副の高いプログラムを使用できる．

次的な処理が異なるために，検出されないコードク

ライブラリ化されたプログラムを使用する際に，開ローンが存在する．プログラムには，目的とする機能

発者はそのプログラムのもつ機能に注目する．開発者を実現するための実装（主要処理）と排除しても目的の必要とする機能をもつプログラムを使用しなければ，とする機能実現に影響を及ぼさない主要処理以外の実ライブラリの恩恵を享受できないからである．ここで，装（副次処理）の 2 種類が含まれている．そのため，先の定義により，プログラムの機能を実装しているのメソッド単位のコードクローン検出手法において副次は主要処理である．このことから，ライブラリ化され処理の影響を排除することができれば，ライブラリ化たプログラムで重要なのは主要処理であり，副次処理の候補となるメソッドを主要処理のみに着目して検出はライブラリの便益とは直接関係がないことが分かる．

することが可能となる．そこで本研究では，メソッド

よって，ライブラリ化の判断をする際にはプログラム

単位のコードクローン検出に副次処理の除去を追加しの主要処理にのみ注目し，副次処理は考慮する必要が

コードクローン検出を行うことで，ライブラリ化候補ないと考えられる．

の特定を目指す．この手法により，メソッドの主要処理が同じであれば，たとえその中に存在している副次処理が異なっていても一つのライブラリ化候補として検出することが可能になる．

2. 主要処理と副次処理
2. 1 定義3. 主要処理のみを考慮したメソッド単位のコードクローン検出3. 1 既存研究におけるメソッド単位のコードクロー
ン検出
石原らは，開発者による共通処理のライブラリ化の支援を目的として，複数のソフトウェアを対象とした主要処理とはプログラムの目的とする機能を実装しメソッド単位のコードクローン検出手法を提案した [9]．

た処理であり，副次処理とは排除しても目的とする機

石原らの手法の概要を図 1 に示す．また，各 STEP

能実現に影響を及ぼさない主要処理以外の処理である．

の概要を以下に示す．

副次処理はプログラムの耐故障性を向上させるために

STEP1（メソッドの切り出し） 与えられたソース利用されることが多い [10]．その性質から，副次処理

ファイルからメソッドを切り出す．メソッドの切り出が主要処理に直接影響を与えることは少ないと考えら

しは，ソースファイルから作成した抽象構文木上で実れる．プログラムの全ての処理は主要処理か副次処理現する．抽象構文木を作成することで，改行や空白ののいずれかに属する．

違いなどが吸収される．

副次処理としてよく利用される処理の一例として，

STEP2（正規化） STEP1 で切り出されたメソッド

例外処理やロギング処理が挙げられる．例外処理とはプログラムの実行過程で発生する意図しない状況に陥ったときの処理である．例えば，意図しない引数が渡された場合の例外処理は副次処理と考えられる．ロ
ギング処理はプログラムの実行過程を時系列で記録に残すための処理である．主に障害発生時にプログラムの入出力や処理の経緯を確認するために用いられるが，通常主要処理に影響をあたえることはない．

2. 2 ライブラリ化における主要処理と副次処理
ライブラリとは，他のプログラムから利用できるよ
2670

Fig. 1図 1 石原らの手法の概要
An overview of the existing method.

論文／主要処理に着目したメソッド単位のコードクローン検出(a) exception throwing,try-catch,logging(b) throws clause,exception throwing,logging(c) throws clause,exception throwing,try-catch(d) throws clause,try-catch(e) throws clause,System.err.println(f) throws clause

図2

副次処理のみが異なるメソッドの例
Fig. 2 Motivating example.

に対して正規化を行う．行う正規化は，変数名，リテ

return 文や簡単な代入文のみで構成されているため，

ラル，メソッド宣言部のメソッド名の特殊文字列への大量にコードクローンとして検出されるおそれがある．

置換，及び，修飾子，アノテーション，コメント文のこのようなコードクローンは処理が簡単に記述でき削除である．

るためライブラリ化する価値が小さく，コードクロー

STEP3（フィルタリング） ソースファイルにはセッンとしての検出は不要である．そこで，このようなメターやゲッター等の処理が単純であり，かつ，短いメ

ソッドはハッシュ値の計算を行わないようにフィルタソッドが多く存在する．このようなメソッドは多くがリングを行う．

2671

電子情報通信学会論文誌 2013/11 Vol. J96–D No. 11

Fig. 3図 3 提案手法の概要
An overview of the proposed method.

STEP4（ハッシュ値の計算） STEP3 を通過した各副次処理が異なるために検出されないコードクロー

メソッドに対してハッシュ値を算出する．具体的には，ンが存在する．副次処理を除去することで検出可能なメソッドを一つの文字列とみなしその文字列に対してコードクローンの例を図 2 に示す．これらのメソッ

ハッシュ値の計算を行う．等しい記述をもつメソッド

ドは実際のオープンソースプロジェクトに存在していはハッシュ値が等しくなるため，ハッシュ値が等しい

るメソッドである．これらのメソッドの違いは，各メ

メソッド同士はコードクローンの関係にある．ハッシュ

ソッドにおいてハイライトで示している副次処理のみ値の算出には MD5 [11] を用いており，算出されたハッであり，副次処理は異なるが主要処理は等しい．そのシュ値はメソッドごとにデータベースに格納する．

ため，ライブラリ化を行う候補を特定する際には，こSTEP5（ハッシュ値によるグループ化） STEP4 でれらのメソッドを一つの候補として検出すべきである．

算出されたハッシュ値の等しいメソッドをグループ化

しかし石原らの手法では単純な正規化しか行わないたする．等しいハッシュ値をもつメソッドは等しい記述

め，これらをコードクローンとして検出することがでをもつ．そのため，ハッシュ値が等しいメソッドをグきない．そこで，副次処理に関するコードを除去した

ループ化することで，互いにコードクローンであるメ

上でメソッド単位のコードクローン検出を行う．

ソッド同士が一つのグループを構成する．これにより，
コードクローンの関係にあるメソッドがどれか判別できるようになる．

3. 3 既存研究の改善案
本研究では石原らの手法をもとに副次処理の除去を行うメソッド単位のコードクローン検出手法を提案す

また，石原らは 13,000 以上のソフトウェアからなるる．そのため提案手法は石原らの手法と等しく，対象

UCI source code data sets [2], [12] に対し手法を適用とするソースファイル群を入力として受け取り，検出した．その結果，ファイル単位の検出手法では見つけされたコードクローンの情報を出力として返す．本手

ることのできない約 1,160,00 のメソッド単位のコード法の概要を図 3 に示す．

クローンを検出した．更に，検出されたコードクロー

本研究では，正規化処理を行う前に副次処理の除去

ンの内，多くのソフトウェアに含まれている 100 のを行う．副次処理の除去は抽象構文木を利用して行う．

コードクローンを調査した結果，56%のコードクロー

石原らの手法ではメソッドの切り出しに抽象構文木をンがライブラリ化に有用であったと報告している．

使用しており，メソッドごとに抽象構文木が存在する．

3. 2 既存研究の問題

このとき，メソッド内の各処理は全て抽象構文木にお石原らの手法を用いることで大規模なデータセット

けるノードとして表現される．そのため，副次処理とからライブラリ化の候補を特定することができる．し判断された処理を表す抽象構文木上のノードを削除すかし，石原らの手法では，主要処理が同じであってもることでメソッド内にある副次処理の除去を実現でき

2672

論文／主要処理に着目したメソッド単位のコードクローン検出(a) 除去前のコード(c) 除去前の抽象構文木

Fig. 4(b) 除去後のコード(d) throw 文，throws 節を除去(e) 空になった if 文を除去

図 4 throw 文，throws 節の除去例
An example of removing a statement throwing an exception and a throws
clause.

る．提案手法は石原らの手法で使用されている抽象構
文木を使っているため，検出時間に大きな影響を与えずに副次処理の除去を行うことが可能である．

4. 副次処理に対する予備調査
4. 1 調査の概要

図 4，5 に Java 言語における副次処理除去の例を

本研究では，副次処理としてよく利用される処理示す．図 4 では，throw 文と throws 節を副次処理とにはどのような処理があるかについて予備調査を行っ判断し，除去を行っている．図 4(c)〜図 4(e) に抽象

た．調査方法は，一つのオープンソースプロジェクト

構文木上での除去の流れを示す．ここで，抽象構文木にある全てのメソッドを著者が目で確認し，プログラの各ノードは図 4(a) の各行と対応している．まず，ムの各処理を主要処理か副次処理のいずれかに分類

図 4(c) から throw 文と throws 節に対応するノード

するというものである．対象となるプロジェクト名はが除去される（図 4(d)）．このノードの除去により，if

jNetStream，ファイル数は 218，総メソッド数は 749

文を表すノードから子ノードがなくなるために除去をである．ソースコードは全て Java 言語で記述されて行い（図 4(e)），除去後のコードとなる．

いる．

図 5 では，try 文を副次処理と判断し，除去を行っている．図 5(c)〜図 5(e) に抽象構文木上での除去の4. 2 調 査 結 果
調査の結果，以下に示す処理が副次処理に分類さ流れを示す．ここで，抽象構文木の各ノードは図 5(a)れた．

の各行と対応している．まず，図 5(c) から副次処理•

throw 文として catch 節内部のノードが除去される（図 5(d)）．

•

try〜catch〜finally と catch 節内部の処理

次に，try 文を表すノードの親ノード（ノード a）を•throws 節

try 節及び finally 節の各子ノードの新しい親ノード•

return null
assert 文として設定する（図 5(e)）．その後，try 文に対応す•るノードの除去を行い（図 5(f)），除去後のコードと•Logger クラスに含まれるメソッド呼び出し

なる．

•

標準出力への出力•

標準エラー出力への出力2673

電子情報通信学会論文誌 2013/11 Vol. J96–D No. 11(a) 除去前のコード(b) 除去後のコード(c) 除去前の抽象構文木(d) catch 節内部を除去(e) 親ノードの変更(f) try〜catch〜finally 文を除去

Fig. 5•図 5 try〜catch〜ﬁnally 文の除去例
An example of removeing try-catch-ﬁnally.

System.exit() メソッド

本研究では，上記の処理をライブラリ化を考慮する
際に除去すべき副次処理と判断した．

5. 副次処理除去の精度の評価
5. 1 実験の概要

本実験の被験者はコンピュータサイエンスを専攻している大学院生 4 名である．各被験者にはそれぞれ 10のメソッドを提示し，合計 40 のメソッドに対して副次処理除去の精度を調査した．

5. 2 実 験 結 果
被験者によって選択された 40 のメソッドに含まれ本実験では，提案手法の適用により，開発者が副次る副次処理と，本手法によって除去された処理がどの処理として記述した処理をどの程度除去できているか程度一致するかを調査した．このとき，一つのメソッを調査する．本実験ではまず被験者となる開発者に，

ドに複数の副次処理が存在した場合は，副次処理ごと

自身が過去に開発したプログラムに存在するメソッドに調査を行った．本手法の副次処理除去により，被験を提示し，副次処理として記述した箇所を選択しても者が副次処理として記述した 30 の処理の内，25 の副らう．その後，各メソッドに対し本手法の副次処理除

次処理を除去することができた．適合率は 78.1%，再去を適用し，除去された箇所と被験者が副次処理とし現率は 83.3%である．

て提示した箇所を比較することで，除去の適合率と再現率を調査する．

2674

被験者が副次処理として記述したが，除去できなかった例を図 6 に示す．このメソッドにおいて，被験論文／主要処理に着目したメソッド単位のコードクローン検出

Table 1

表 1 実験対象の構成
An overview of the target data set.
ファイル数
ソフトウェア数
メソッド数
総行数
全容量

2,072,490
13,193
19,416,603
361,663,992
30.6GByte

を行うことで，石原らが用いたデータセットと等しい
図 6 副次処理の除去に失敗したメソッド
Fig. 6 An example of false negative.

データセットを用いることができる．本実験における実験対象の構成を表 1 に示す．本実験は CPU 数 2，
計 8 コア（2.27GHz），メモリ 32GByte の環境で行い，検出結果を格納するデータベースは SSD 上に作者はハイライトされた箇所を副次処理として記述して成した．また，追加した除去処理の影響のみを調査すいる．本来であれば，対象プログラムの開発者であるるため，石原らの手法と提案手法においてフィルタリ

被験者がプログラムの目的とする機能に直接影響しな

ング処理条件を 30 トークン以下のメソッドを除去す

いと判断している処理は副次処理に分類されるべきでるように統一した．

ある．しかし本手法では予備調査の結果に基づき除去

本実験おいて，クローンセットに含まれるメソッドの対象となる処理を選択していたため，setAttributeが分布しているソフトウェアの数を NoS(the Numberを用いたメッセージ送信を副次処理とみなしていない．

Of Software system) と定義する．ここで，クローン

そのため，この処理を副次処理として除去することがセットとは互いにコードクローン関係にあるメソッド

できなかった．このように除去できなかった処理またの集合のことである．多くのソフトウェアで使用されは誤って除去してしまった処理が発生した原因は，全ているメソッドは，クローンセットとして検出されたての場合において予備調査の結果と被験者との間で副ときに NoS の値が大きくなる．したがって，NoS の次処理の判断基準が異なることによるものだった．

値が大きいクローンセットはライブラリ化すべきであ

6. 石原らの手法との比較ると考えられる．

6. 1 実験の準備て代入が行われたフィールド数を算出し，その最大値提案手法の有用性を示すために以下の三つの項目を調査する．

また，クローンセットに含まれる各メソッドに対しを NAF(the Number of Assignment Fields) として定義する．また，クローンセットに含まれるメソッド

調査項目 A 副次処理の除去を行う場合と行わない場に返り値が存在する場合，NAF 値に 1 を加算する．

合で，検出されるコードクローンにどの程度違いがあ

NAF 値が 2 以上のクローンセットは，メソッドの呼るかび出し元に対して複数の値を返さなければならないた

調査項目 B 提案手法と石原らの手法でライブラリ化

め，メソッド単体で抽出することが難しい．それに対の候補となるコードクローンにどの程度違いがあるか

して，NAF が 0 若しくは 1 の場合は，メソッド単位

調査項目 C 副次処理の除去を行う場合と行わない場で抽出することが可能であり，容易にライブラリ化を合で検出時間がどの程度異なるか行うことができると考えられる．

本研究では実験対象として，石原らが実験に用いた”UCI source code data sets” [2], [12] を用いた．ま6. 2 調査項目 A：副次処理除去の有無による検出
結果の比較

た，石原らと同様にデータセット内で trunk，tags，

副次処理の除去によりハッシュ値が変化したメソッ

branches を同時に含むソフトウェアは trunk 内のソードがどの程度存在するかを調査した．調査結果を表 2

スファイルのみを，バージョンの異なる同一のソフトに示す．ここで，調査したメソッドは副次処理を含んウェアは最新バージョンのソフトウェアのみを検出対だ状態でトークン数 30 以上のメソッドである．

象とし，ソースコード自動生成ツールによって生成この結果より，約 45%のメソッドが何らかの副次処されたファイルを検出対象から除外した．前述の処理理を行っていることが分かる．また，副次処理の除去
2675

電子情報通信学会論文誌 2013/11 Vol. J96–D No. 11
表 2 副次処理除去によるメソッドへの影響
Table 2 Impact on methods by removing errorhandling.
ハッシュ値が変化したメソッド数
ハッシュ値が変化しなかったメソッド数

3,403,104(45.8%)
4,022,793(54.2%)

表 3 副次処理除去によるクローンセットへの影響
Table 3 Impact on clonesets by removing errorhandling.
新たに検出されたクローンセット数
要素数が増えたクローンセット数消失したクローンセット数

16,82019,93869,218により，プログラムの主要処理は同じであるが副次処きかどうかを判断した．ライブラリ化の判断を行う際理の異なるメソッド群を，一つのクローンセットとしは主要処理にのみ注目した．すなわち，ライブラリ化て検出できるようになった．これにより，82,639 のメ

する上でどの副次処理を含めるべきかについては考慮

ソッドが新たにコードクローンとして検出された．

していない．この作業を繰り返し，最終的に 100 のク

また，石原らの手法によって検出された全てのク

ローンセットに対してライブラリ化の判断を行った．

ローンセットからメソッドを一つずつ選択し，そのメライブラリ化を判断する際，自動生成されたメソッ

ソッドが提案手法の検出結果に含まれるどのクローン

ドやコンストラクタ，メインメソッドから構成される

セットに分類されているかを調査した．これによって，クローンセットは判断の対象から除外した．本研究で石原らの手法では異なるクローンセットに含まれていは実験に使用したデータセットから自動生成された

たが提案手法では共通のクローンセットに含まれるよ

ソースファイルを除いているが完全ではなく，自動生

うになったメソッドや，そもそも石原らの手法では検成されたメソッドがコードクローンとして検出されて出されていなかったクローンセットがどの程度存在すいる．しかし，自動生成されたメソッドは同じツール

るかを確認できる．調査結果を表 3 に示す．

を使うことで再現できるため，ライブラリ化の効果はこの結果より，石原らの手法では検出できなかった

小さい．コンストラクタは通常インスタンスの初期化

が，提案手法では検出できたクローンセットが 16,820を行うといった用途で使用されるため，コンストラク

存在したことが分かる．このことから，提案手法は石タのみを見てライブラリ化の判断を行ってもライブラ

原らの手法では見過ごされていたライブラリ化の候補

リ化の効果を十分に得られない．メインメソッドはソとなるメソッドを検出できるといえる．また，石原ら

フトウェアごとに独自のものが必要とされるため，ラの手法では複数に分かれて検出されるが提案手法ではイブラリ化の効果が小さい．このように，いずれの場

一つのクローンセットに統合されるクローンセットが合もライブラリ化することの利点が小さいため，ライ

19,938 存在した．このことから，副次処理を除去す

ブラリ化の判断を行っていない．

ることで，石原らの手法では分割されていた多くのク

図 7 は，ライブラリ化の判断を行ったクローンセッ

ローンセットが提案手法によって統合されたと考えら

トの NoS 値の変化を表している．ライブラリ化の判断を行ったクローンセットを調査項目 A と同様の方法，

れる．
ここで，石原らの手法では検出されていたが提案手

すなわち，石原らの手法の検出結果から一つメソッド

法では検出されなくなったクローンセットが 69,218を選択し，そのメソッドが提案手法の検出結果のどの存在する．これは副次処理を除去したためにメソッド

クローンセットに分類されているかを調べて比較した．

のトークン数が減少し，フィルタリングを通過しなく

図 7 の縦軸は NoS 値，横軸はライブラリ化の判断をなったためである．

行ったクローンセットを示す．グラフ上の色の濃い部

6. 3 調査項目 B：ライブラリ化の候補となるコー
ドクローンの違い

分は，提案手法によって増加した NoS 値を示している．図 7 より，調査したクローンセットのうち 39%の提案手法と石原らの手法で検出されたコードクロー

クローンセットは石原らの手法から NoS 値が増加しンにどの程度違いがあるかの調査を行った．しかし，ていることが分かる．中には，NoS 値が 2 倍以上に検出されるクローンセットの数が膨大になるため，全なったクローンセットも存在した．このことから提案てのクローンセットを分析することは現実的に困難で手法は，既存手法では発見できなかった多くのソフト

ある．そこで，提案手法によって検出された NAF 値がウェアにまたがって存在する処理を発見していること

1 以下のクローンセットを NoS 値で降順にソートし，が分かる．

上位のクローンセットから一つずつライブラリ化すべ
2676

本実験では，石原らと同様に，ライブラリ化の判断

論文／主要処理に着目したメソッド単位のコードクローン検出

図 7 調査した 100 クローンセットの NoS 値の変化
Fig. 7 Change in the NoS value of 100 clone sets.

(a) sunFig. 8(b) BasicQuery

図 8 ライブラリ化すべきと判断したコードクローンの例
An instance of method cloneset suite for library building.

(a) jbootcat

Fig. 9(b) YAWL

図 9 ライブラリ化すべきでないと判断したコードクローンの例
An instance of method cloneset don’t suite for library building.

を行った 100 のコードクローンの発生原因を以下の三るが，これは発生原因に重複があるためである．本実

つに分類した．

験では石原らと同様に汎用的な処理を行うメソッドに•

抽象クラスの継承，インターフェイスの実装分類されたクローンセットを除く，65 のクローンセッ•

ソースコードの流用

トをライブラリ化すべきであると判断した．石原らの•汎用的な処理を行うメソッド

手法で検出したクローンセットに対して同様の調査を

その結果を表 4 に示す．ここで合計が 100 を超えてい行ったところ，調査した 100 クローンセットのうち 622677

電子情報通信学会論文誌 2013/11 Vol. J96–D No. 11
表 4 クローンセットの分類結果
Table 4 Classiﬁcation of the clonesets.
抽象クラスの継承，インターフェイスの実装
要素数が増えたクローンセット数
汎用的な処理を行うメソッド

表5 解析時間
Table 5 Analyzing time.
17
64
35

のクローンセットがライブラリ化すべきであると判断された．石原らの手法の調査対象と提案手法の調査対

処理内容
メソッドの切り出し
副次処理の除去
正規化
フィルタリング
ハッシュ値の計算
ハッシュ値によるグループ化
合計

除去あり

除去なし

1 時間 29 分

1 時間 28 分

21 分
1 時間 50 分

23 分
1 時間 51 分

象では，NoS 値の増加によって 10 のクローンセット
が入れ替わっており，そのうち三つが新たにライブラ

グ条件を通過できないメソッドが発生し，対象となるリ化すべきであると判断された．この結果から，提案

メソッド数が減少したためである．実験結果より，作手法は石原らの手法では下位に存在したライブラリ化成したツールでは，約 360,000,000 行のソースコード

すべきコードクローンを上位に位置づけることができに対し 2 時間以内で検出を行うことができ，実用的なるといえる．

時間で実行可能であるといえる．

図 8 にライブラリ化すべきであると判断したメ
ソッドの一例を示す．この二つのメソッドは，ともに7. 妥当性への脅威

JTable のソートを実行するメソッドであり，ハイライ

7. 1 副次処理の判断基準に関してトされた箇所のロギング処理のみが異なっている．こ本研究では，除去すべき副次処理を 4. で記述したのメソッドを含むクローンセットは，96 のソフトウェ

予備調査をもとに判断している．しかし，5. の実験結

アにまたがって存在する．このような処理は，今後も果から分かるように，どの処理を副次処理とみなすか

多くのソフトウェアで行われる可能性があるため，ラは判断する人によって異なる．そのため，本研究で対イブラリ化を行うべきであると判断した．

象とした副次処理を変更することで結果が変わる可能また，ライブラリ化には適していないと判断した性がある．

コードクローンの一例を図 9 に示す．この二つのメ

また，本研究では副次処理の除去後にフィルタリン

ソッドはユーザ定義名と文字列リテラルのみが異なる

グ処理を行っているため，副次処理の除去後にフィルためコードクローンとして検出されている．このようタリング条件を満たすようになったメソッドは検出対なメソッドを含むコードクローンは多くのソフトウェ

象から除外される．そのため，副次処理の基準が変わアに存在するが，処理が単純であり，かつ，ソフトウェ

れば，副次処理の除去後にフィルタリング条件を満た

アごとに異なる目的で用いられる可能性が高いためラすメソッドも変化する．これにより，検出対象となるイブラリ化には適さない．

メソッドが変化し，結果が変わる可能性がある．

6. 4 調査項目 C：実行時間

7. 2 ハッシュ値の衝突に関して作成したツールを対象のデータセットに適用した結提案手法では二つのメソッドがコードクローンで果，副次処理の除去を行う場合は 1 時間 50 分，行わ

あるかの判定にハッシュ値を使用している．そのためない場合は 1 時間 51 分をそれぞれ要した．表 5 に各

コードクローン検出の際に文字列が異なるにもかか処理に要した時間を示す．

わらずハッシュ値が偶然一致するハッシュ値の衝突が副次処理の除去を行う場合と行わない場合での実行

起こった場合，本来コードクローンでないメソッドが時間を比較すると，除去を行う場合ではメソッドの切

コードクローンとして検出されるおそれがある．しかり出しからハッシュ値の計算までの処理にわずかに時し，本研究ではハッシュ値の計算に 128bit の MD5 ア

間がかかっている．これは，副次処理の除去を追加しルゴリズムを使用しているため衝突確率は極めて低いているためであるが，時間の増加はわずかであり，こと考えられる．また本研究では，同じハッシュ値をもの処理にはほとんど時間がかかっていない．また，ハッつメソッド全てについて，副次処理の除去と正規化処

シュ値のグループ化に要する時間が減少している．こ理を行った後の文字列が一致するかどうかを調べるプ

れは，提案手法では副次処理の除去後にフィルタリン

ログラムを作成し，ハッシュ値の衝突がなかったこと

グを行っているため，副次処理除去後にフィルタリン

を確認した．ただし，より多くのソフトウェアに対し2678

論文／主要処理に着目したメソッド単位のコードクローン検出

提案手法を適用した場合，ハッシュ値の衝突が起こる
可能性がある．

on Software Maintenance, pp.283–292, Sept. 2011.
[3]

佐々木裕介，山本哲男，早瀬康裕，井上克郎，“大規模ソフトウェアシステムを対象としたファイルクローンの検出，” 信学論（D），vol.J94-D, no.8, pp.1423–1433, Aug.
2011.

[4]

J.R. Cordy and C.K. Roy, “Debcheck:7. 3 正規化，フィルタリングに関して
本研究は石原らの手法をもとにしており，以下の正規化処理を行っている．

•

変数名，リテラル，メソッド宣言部のメソッド

tems,” Proc. 19th International Conference on Pro-

名は特殊文字列に置換する．

•

Eﬃcient

checking for open source code clones in software sysgram Comprehension, pp.217–218, June 2011.

修飾子，アノテーション，コメント文は削除[5]

Y. Higo, K. Tanaka, and S. Kusumoto, “Toward iden-

する．

tifying inter-project clone sets for building useful li-

しかし，型名の正規化の有無やフィルタリングを行う

braries,” Proc. 4th International Workshop on Soft-

トークン数の変更等により，本研究では検出できていware Clones, pp.87–88, May 2010.
[6]ないコードクローンを検出できる可能性がある．

B. Hummel, E. Jürgens, L. Heinemann, and M.
Conradt, “Index-based code clone detection: incremental, distributed, scalable,” Proc. 26th Interna-

8. む す びtional Conference on Software Maintenance, pp.1–9,
2010.

本論文では，副次処理のみが異なるメソッド群を一[7]

R. Koschke, “Large-scale inter-system clone detec-

つのライブラリ化候補として検出することを目的としtion using suﬃx trees,” Proc. 16th European Con-て，副次処理の除去を追加したメソッド単位のコード

ference on Software Maintenance and Reengineering,

クローン検出手法を提案し，評価を行った．今後の課

pp.309–318, March 2012.
[8]

題として，

•

W. Shang, B. Adams, and A.E. Hassan, “An experience report on scaling tools for mining software

主要処理や副次処理の分類に関して更に詳しい

repositories using mapreduce,” Proc. 25th Interna-調査を行い，除去対象となる処理を変えることでどの

tional Conference on Automated Software Engineering, pp.275–284, Sept. 2010.

程度違いがあるか調査•[9]石原知也，堀田圭佑，肥後芳樹，井垣 宏，楠本真二，“大規模なソフトウェア群を対象とするメソッド単位でのコー” 情処学論，vol.54, no.2, pp.835–844,
ドクローン検出，Feb. 2013.

[10]

C. Fu and B.G. Ryder, “Navigating error recovery

本研究とは異なる正規化やフィルタリング処理を行った場合に，検出されるコードクローンにどの程度違いがあるかの調査•対象となるファイルを Java 以外にも拡張し，言code in java applications,” Proc. OOPSLA work-

語によって検出されるコードクローンに違いがあるか

shop on Eclipse Technology eXchange, pp.40–44, Oct.
2005.

の調査
[11]

等が挙げられる．

RFC 1321 (Informational), April 1992. Updated by

謝辞 本研究は，日本学術振興会科学研究費補助金
基盤研究 (S)（課題番号：25220003），挑戦的萌芽研究（課題番号：24650011），及び文部科学省科学研究費補助金若手研究 (A)（課題番号：24680002），独立行政法人情報処理推進機構 技術本部 ソフトウェア高信

R. Rivest, “The md5 message-digest algorithm,”
RFC 6151. http://www.ietf.org/rfc/rfc1321.txt[12]

C. Lopes, S. Bajracharya, J. Ossher, and P. Baldi,“Uci source code data sets”. http://www.ics.uci.edu/
lopes/datasets/（平成 25 年 2 月 6 日受付，6 月 4 日再受付）

頼化センター（SEC: Software Reliability Enhance-

ment Center）が実施した「2012 年度ソフトウェア工学分野の先導的研究支援事業」の支援を受けた．
文
[1]

献

肥後芳樹，リビエリシモネ，松下 誠，井上克郎，“大規模ソースコードを対象としたコードクローンの検出と可” 情処学論，vol.48, no.11, pp.3510–3519, Nov.
視化，
2007.

[2]

長瀬 義大
平成 23 年大阪大学基礎工学部情報科学科卒業．平成 25 年同大学大学院情報科学研究科博士前期課程修了．在学時，コード
クローン分析に関する研究に従事．

J. Ossher, H. Sajnani, and C. Lopes, “File cloningin open source java projects: The good, the bad,and the ugly,” Proc. 27th International Conference2679電子情報通信学会論文誌 2013/11 Vol. J96–D No. 11

石原

知也

楠本 真二

平成 24 年大阪大学基礎工学部情報科学科卒業．現在，同大学大学院情報科学研究科博士前期課程在学中．コードクローン分

昭和 63 年大阪大学基礎工学部卒業．平
成 3 年同大学大学院博士課程中退．同年同大学基礎工学部助手．平成 8 年同講師．平

析に関する研究に従事．

成 11 年同助教授．平成 14 年同大学大学
院情報科学研究科助教授．平成 17 年同教授．博士（工学）．ソフトウェアの生産性や楊品質の定量的評価に関する研究に従事．情報処理学会，IEEE，
IFPUG 各会員．

嘉晨

平成 23 年中国上海交通大学軟件学院軟件工程專業卒業．平成 25 年大阪大学大学
院情報科学研究科博士前期課程修了．現
在，同研究科博士後期課程在学中．コード
クローン分析に関する研究に従事．

堀田圭佑

平成 22 年大阪大学基礎工学部情報科学科卒業．平成 24 年同大学大学院情報科学研究科博士前期課程修了．現在，同研究科博士後期課程在学中．日本学術振興会特別研究員 DC．コードクローン分析に関する研究に従事．IEEE，情報処理学会各会員．

肥後

芳樹

（正員）

平成 14 年大阪大学基礎工学部情報科学科中退．平成 18 年同大学大学院博士後期課程修了．平成 19 年同大学院情報科学研
究科コンピュータサイエンス専攻助教．博士（情報科学）．ソースコード分析，特にコードクローン分析やリファクタリング支援に関する研究に従事．情報処理学会，日本ソフトウェア科学会，IEEE 各会員．

井垣

宏

（正員）

平成 12 年神戸大学工学部電気電子工学科卒業．平 14 年奈良先端科学技術大学院
大学情報科学研究科博士前期課程修了．平成 17 年同大学院博士後期課程修了．同年
同大学院特任助手．平成 18 年南山大学数理情報学部講師．平成 19 年神戸大学大学
院工学研究科特命助教．平成 22 年東京工科大学コンピュータ
サイエンス学部助教．平成 23 年大阪大学大学院情報科学研究科特任准教授．博士（工学）．ソフトウェア工学教育，サービス
指向アーキテクチャ，ホームネットワークシステム，Web サー
ビス，ソフトウェアプロセス等の研究に従事．IEEE，ACM，
IPSJ 各会員

2680（正員：シニア会員）