情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

プログラム依存グラフを用いた増分的なコードクローン検出
肥後 芳樹1,a)

植田 泰士1,b)

西野 稔1,c)

楠本 真二1,d)

受付日 2011年6月14日, 採録日 2011年11月7日

概要：近年，増分的なコードクローン検出法が注目されている．増分的な検出法では，検出結果（もしくはその中間生成物）はデータベースに保存され，次回以降の検出に利用される．このため，同じファイル
群から何度もコードクローン検出を行う場合では，2 回目以降の検出時間を大幅に短縮することができる．
本論文では，プログラム依存グラフを用いた増分的な検出法を提案する．プログラム依存グラフを用いた検出は，行単位の検出などの他の検出法に比べて検出に長い時間を必要とするため，増分的な検出を行う
メリットは大きい．また，提案手法に基づいてツールを開発し，適用実験を行った．実験の結果，提案手法は，従来のプログラム依存グラフを用いた検出法とほぼ同じコードクローンを検出するが，検出時間は大幅に短くなっていることを確認した．
キーワード：コードクローン，プログラム依存グラフ

Incremental Code Clone Detection Using Program Dependency Graph
Yoshiki Higo1,a)Yasushi Ueda1,b)

Minoru Nishino1,c)Shinji Kusumoto1,d)Received: June 14, 2011, Accepted: November 7, 2011

Abstract: Incremental code clone detection attracts much attention in the last few years. In incremental
detections, code clone detection results (or their intermediate products) persist by using databases, and they
are used in next code clone detection. However, no incremental detection technique has been proposed for
PDG-based detection, which requires much more time to detect code clones than line- or token-based detection. In this paper, we propose a PDG-based incremental code clone detection technique for improving
practicality of PDG-based detection. A prototype tool has been developed based on the proposed method,and it has been applied to open source software. We conﬁrmed that detection time extremely shortened andits detection result is almost the same as one of an existing PDG-based detection technique.
Keywords: code clone, program dependency graph

1. はじめに

当部分に対して修正が加えられる．しかし，そのコードク
ローンがシステム中に存在した場合は，それらに対してもコードクローンの存在はソフトウェアの保守作業に悪影同様の修正を検討する必要がある．修正を行った保守管理

響を与える要因の 1 つであるといわれている．コードク

者が，コードクローンの存在に気づかなかった場合，シスローンとは，ソースコード中に存在する重複コードであテムには潜在的なバグが残ってしまう可能性がある．

り，コピーアンドペーストなどのさまざまな理由により生

このような，コードクローンに起因する問題を解決・軽成される [7]．バグが顕在化した場合，ソースコード中の該減するための 1 つの方法として，リファクタリングがあげられる．リファクタリングを行うことにより，コードク

1

a)
b)
c)
d)

大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology,
Osaka University, Suita, Osaka 565–0871, Japanhigo@ist.osaka-u.ac.jp
yss-ueda@ist.osaka-u.ac.jp
m-nisino@ist.osaka-u.ac.jp
kusumoto@ist.osaka-u.ac.jp

c 2012 Information Processing Society of Japan

ローン部分は 1 つの関数やメソッドにまとめられるため，
今後の修正作業により，その部分には不整合が起こらない．
これまでに，ソースコード中からコードクローンを自動的に検出するさまざまな手法が提案されている [1], [7]．既601

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

存の検出技術は，用いている技術により，行単位での検出，字句単位での検出，抽象構文木を用いた検出，プログラム

1: int fibonacci(int n){
2:

int value = -1;

3:

if (n <= 0) {依存グラフを用いた検出，メトリクスやフィンガプリント

4:などを用いた検出に大別される．これらの中で，抽象構文

5:木を用いた検出とプログラム依存グラフを用いた検出はリ

System.out.println("Illegal parameter");} else if (n == 1 || n == 2) {6:value = 1;7:

} else {ファクタリングに向いているといわれている [14]．しかし，

8:

これらの検出技術は，他の検出技術に比べ検出に必要な計

9:

}

10:

return value;

算量が高く，コードクローン情報が欲しいときに，瞬時にその情報を得ることが難しい．
また，近年，増分的なコードクローン検出*1 が注目を集

value = fibonacci(n - 2) +fibonacci(n - 1);

11: }(a) フィボナッチ数列を(b) 生成される PDG
計算するメソッド
図 1 PDG の例めている．増分的なコードクローン検出とは，検出結果とFig. 1 PDG example.

その中間生成物をデータベースなどに保管し，次回以降の検出時に利用する検出手法である．検出対象ファイルが前回の検出時から更新されていない場合は，そのファイル自身は解析されず，ファイルに関する必要な情報はデータのが存在する．
本研究では，上記の依存関係に加えて，実行依存も用いる．実行依存とは実行の順序を表す依存関係であり，要素ベースから取得される．このような枠組みを用いることにs5 が実行された直後に要素 s6 が実行される可能性がある

よって，同じファイル集合から何度も検出を行う場合は，場合，s5 から s6 へ実行依存エッジが引かれる．実行依存

2 回目以降の検出時間を大幅に短縮することができる．
増分的なコードクローン検出手法は，行単位での検出と字句単位での検出を行う手法がこれまでに提案されている [5], [9]．しかし，リファクタリングなどに有効な，抽象構文木を用いた検出やプログラム依存グラフを用いた検出はまだ提案されていない．また，これらの手法は，検出に必要な計算コストが高いため，増分的に検出を行うメリットは大きい．このような現在の状況をふまえ，本論文では，プログラム依存グラフを用いた増分的なコードクローン検出手法を提案する．

2. プログラム依存グラフ
プログラム依存グラフ（Program Dependency Graph，
以降 PDG）とは，ソースコード中の要素（文や条件節の式）間の依存関係を表現した有向グラフである．PDG のノードは要素，エッジは要素間の依存関係を表す．一般的な PDG では，依存関係は制御依存とデータ依存の 2 種類が存在する．本論文では，PDG はメソッド単位で構築されるものとする．
以下のすべての条件を満たすとき，要素 s1 と s2 の間には制御依存関係が存在する．

• s1 は条件節の式である．
• s1 の結果により，s2 が実行されるか否かが決定する．
また，以下のすべての条件を満たすとき，要素 s3 と s4の間にはデータ依存関係が存在する．

• s3 では，変数 v を定義している（変数 v に対して代入処理を行っている）．

• s4 では，変数 v を参照している．
• s3 から s4 への経路の中に，変数 v を再定義しないも*1を PDG に追加することにより，コードクローンの検出能力が高まることが確認されている [6]．
図 1 は，フィボナッチ数列の計算を行うプログラムとその PDG である．PDG のノードの数字は，その要素のソー
スコード中での位置（行番号）を表している．なお，<1>のノードは，メソッドの入り口ノードを表し，そのノードは便宜上，条件節の式と見なされる．また，n や out は，それぞれ仮引数や共有変数を表すノードである．

3. 提案手法
図 2 は提案手法の概観を表している．提案手法は解析処理と検出処理の 2 つからなる．解析処理では，ソースコードから PDG が構築され，その情報がデータベースに保存される．検出処理では，データベースから PDG の情報を取り出し，コードクローンの検出を行う．提案手法は，
コードクローン検出に必要な PDG の情報を再利用することにより，ファイル読み込み，ソースコード解析，およびPDG の構築に必要なコストを削減する．その結果，コー
ドクローン検出を行う場合に，より短時間で結果を得ることができる．つまり，提案手法は，多くの PDG 情報を再利用できる状況において有効である．提案手法が有効な状
況としては，たとえば下記のものがあげられる．

• 複数のリビジョンから順にコードクローンを検出する．
• 着目するファイルに関連するコードクローンのみを検出する．

5 章では，これらの状況を想定した提案手法の評価を行っている．
以降，本章では，3.1 節で提案手法で利用する種々の定義を行い，3.2 節では解析処理について説明する．その後，

3.3 節で検出処理について説明する．

Incremental Code Clone Detection

c 2012 Information Processing Society of Japan

602

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

図 3 1 つの PDG から生成されるエッジツリー

Fig. 3 Edge trees generated from a PDG.

その経路上に存在するすべてのノードを 1 度しかたどらないものである．
次に，エッジツリーという新しいデータ構造を定義する．
定義 5（エッジツリー） エッジツリーのノードは，プ
図 2 提案手法の概観

Fig. 2 Overview of the proposed method.

3.1 定義まず，プログラム依存グラフを定義する．
定義 1（プログラム依存グラフ） 本研究で用いるプロ
グラム依存グラフは連結グラフであるため，そのグラフ（g とする）を構成するエッジ集合として定義することができる．

ログラム依存グラフ g = {e1 , e2 , · · · , en } を構成するエッジであり，ツリーのエッジはグラフのエッジ間の隣接関係である．また，エッジツリーのノード数はグラフのエッジ数と等しい（グラフ中のすべてのエッジをノードとして持つ）．木であるため閉路は含まない．つまり，PDG が閉路を含む場合は，1 つのエッジツリーに，PDG エッジの隣接関係がすべて現れることはない．
図 3 はエッジツリーの簡単な例を表している．この図に示すように，1 つの PDG から複数のエッジツリーが生

g := {e1 , e2 , · · · , en }成されうる．図 3 はエッジ e1 を根とする 3 つのエッジツリーを表している．このように 1 つのエッジツリーがすべ

また，本論文では，エッジを下記のように定義する．
定義 2（エッジ） エッジ e の出発ノードを v1 ，到達ノードを v2 ，エッジの種類（データ・制御・実行）を t とすると，エッジ e は下記の式で表される．

e = (v1 , v2 , t)
次に，エッジの隣接関係を定義する．

ての隣接関係を表現しているわけではない．
次に，エッジツリーの集合を定義する．
定義 6（エッジツリーの集合） T REES(g) は，プログ
ラム依存グラフ g から生成されうるすべてのエッジツリーの集合である．
また，ここで，エッジツリー上の経路を定義する．
定義 7（エッジツリー上の経路） treepath(t, e) は，エッ定義 3（隣接関係） エッジ e1 = (v1 , v2 , t1 )，エッジ

ジツリー t において，根からノード e までの経路である．

e2 = (v3 , v4 , t2 ) とすると，これら 2 つのエッジの隣接関係

定義 4 と定義 7 を用いると，定理 1 は自明である．

は下記の式により定義される．

incident(e1 , e2 ):= (v1 = v3 ∧ v2 = v4 ) ∨ (v1 = v4 ∧ v2 = v3 )∨ (v2 = v4 ∧ v1 = v3 ) ∨ (v2 = v3 ∧ v1 = v4 )つまり，エッジ e1 と e2 が 1 つのノードを共有していれば，incident(e1 , e2 ) は真となる．
次に，隣接関係を用いてエッジ間の経路を定義する．
定義 4（エッジ間の経路） 連結グラフであるため*2 ，任意のエッジ ei とエッジ ej の間には経路が存在する．経路が複数存在する場合もあるため，エッジ ei と ej の間の経路集合を，P AT HS(ei , ej ) と表す．なお，ここでの経路
は閉路を含まないものとする．閉路を含まない経路とは，*2

厳密には，参照されていない引数があると孤立ノードが存在するが，そのような孤立ノードは無視する．

c 2012 Information Processing Society of Japan

定理 1 er をエッジツリー t の根とすると，下記の式が成り立つ．

treepath(t, e) ∈ P AT H(er , e)
また，連結グラフでは，P AT H(er , e) = φ はつねに真となる．つまり，あるエッジから他の任意のエッジへの経路が少なくとも 1 つ存在する．つまり，連結グラフからは少なくとも 1 つのエッジツリーが生成される．
次に，グラフエッジの同値関係を定義する．
定義 8（グラフエッジの同値関係） 2 つのエッジ e1 =(v1 , v2 , t1 ) と e2 = (v3 , v4 , t2 ) の同値関係は，下記の式で定義される．

e1 ≡ e2 := (t1 ≡ t2 ) ∧ (v1 ≡ v3 ) ∧ (v2 ≡ v4 )e1 と e2 の依存関係の種類が等しいとき t1 ≡ t2 は真とな
603

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

る．v1 ≡ v2 は，コードクローン検出の状況に応じた定義をすべきである．たとえば，完全に字面が等しいコード片のみをコードクローンとして検出したい場合は，ノード v1と v2 を表す文字列を直接比較すべきである．また，ある定義 12（出力されるクローンペア）

outputclonepair(s1 , s2 ) := clonepair(s1 , s2 )∧¬∃(s1 , s2 )(clonepair(s1 , s2 ) ∧ s1 ⊂ s1 ∧ s2 ⊂ s2 )程度の差違も許容して検出したい場合は，何らかの正規化提案手法では，outputclonepair を満たすクローンペアが処理を行った後に，比較すべきである．

出力される．

定義 8 を用いて，ツリーノード間の経路の同値関係を定

3.2 解析処理

義する．
定義 9（ツリーノード間の経路の同値関係） 2 つ の ツ

解析処理の入力と出力を以下に示す．

リ ー ノ ー ド 間 の 経 路 p1 = (e1 , e2 , · · · , en ) と p2 =入力 ソースファイル群(f1 , f2 , · · · , fm ) において，その同値関係は下記の式で定義

出力 更新されたソースファイル内のグラフエッジ群される．

図 2 の上部は解析処理の概要を表している．解析処理では，以下の手順で行われる．

p1 ≡ p2 := (|p1 | = |p2 |) ∧ ∀i(ei ≡ fi )1. 各ソースファイルの更新時刻と，前回解析処理を行っ

つまり，ツリーノード間の経路 p1 と p2 が同数のノードをた時刻と比較する．前回の解析処理時刻よりも新しい持ち，各ノードのペアが同値であれば，p1 と p2 は同値で更新時刻を持つファイルを更新されたファイルと呼ある．

ぶ．この比較により，更新されたファイル群を得る．

2. 解析モジュールは更新されたファイル群から PDG を次に，エッジツリーの同値関係を定義する．
定義 10（エッジツリーの同値関係） 2 つ の エ ッ ジ ツ
リー t1 ∈ T REES(g1 ) と t2 ∈ T REES(g2 ) において，その同値関係は下記の式で定義される．なお，グラフ g の構築し，それに含まれるエッジの情報をエッジデータ
ベースに保存する．
手順 2. では，すでにそのファイルの古いバージョンの情報が保存されている場合は，その情報を削除したのち，新エッジ数を |g| と表す．

しいバージョンの情報が追加される．

t1 ≡ t2:= (|g1 | = |g2 |) ∧ ∃(e1 , e2 , · · · , e|g1 | )∃(f1 , f2 , · · · , f|g2 | )⎛{ei } = g1 ∧
{wj }
∀k ⎝
1≤i≤|g1 |1≤j≤|g2 |⎞= g2 ∧ treepath(t1 , ek ) ≡ treepath(t2 , fk )⎠つまり，エッジツリー t1 と t2 はエッジの数が等しく，t1の任意のノードから根への経路と同値関係にある経路が t2に存在しており，かつ t2 の任意のノードから根への経路と同時関係にある経路が t1 に存在している場合に，同値となる．
上記の定義を用いることによって，クローンペアは次のように定義される．
定義 11（クローンペア） プログラム依存グラフ g1 とg2 上のサブグラフ s1 と s2 において，下記の式が真になる場合に，s1 と s2 はクローンペアとなる．

3.3 検出処理
検出処理の入力と出力を以下に示す．
入力 コードクローン検出対象ソースファイル名
出力 入力として与えられたファイルに関連するクローン
ペアの集合
図 2 の下部は検出処理の概要を表している．検出処理は下記の手順で行われる．

1. ユーザはコードクローンを検出したいファイルを指定
する．

2. 検出モジュールはそのファイル名をクエリとしてエッジデータベースに問い合わせる．

3. エッジデータベースは，クエリのファイル内に存在するエッジと等価なエッジ群を返す．

4. 検出モジュールは，エッジデータベースより返されたエッジ群から，クローンペアを構築しユーザに提示する．
検出処理を実現するためには，エッジ群からクローンペ

clonepair(s1 , s2 ) := (s1 ∩ s2 = φ)アを生成するアルゴリズムが必要である．まず，メソッド∧∃t1 ∃t2 (t1 ∈ T REES(s1 ) ∧ t2 ∈ T REES(s2 ) ∧ t1 ≡ t2 )を入力として，そのメソッドと関連のあるクローンペアの定義 11 のクローンペアの中には出力する必要のないもお，あるメソッドと関連のあるクローンペアとは，そのクのが含まれている．そのようなコードクローンを取り除い

ローンペアのコードクローンのうち少なくとも一方がそのた定義を以下に示す．

メソッド内に存在しているクローンペアである．

集合を出力するアルゴリズムを Algorithm 1 に示す．なアルゴリズムの主要な部分を説明する．

c 2012 Information Processing Society of Japan

604

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

Algorithm 1 detect (m)集合を引数として，アルゴリズム create を再起呼び出

Input: m: メソッド
Output: C: メソッド m に関連するクローンペアの集合
1: C ← φ
2: for all e1 such that e1 ∈ m do3:
for all e2 such that e2 ≡ e1 ∧ e2 = e1 do
4:
C ← C ∪ create(e1 , e2 , φ)5:
end for
6: end for7: return C

しする．

6 行目 5 行目の結果得られた，クローンペアを成すエッジの集合を S1 と S2 に加える．

4. 実装
提案手法をツールとして実装した．規模は約 10,000 行であり，PDG の構築に必要なソースコード解析には，著者らの研究グループで開発している MASU [13] を利用し1 行目 出力するクローンペアの集合を保存する変数 C を空集合で初期化する．

2 行目 入力として与えられたメソッド m に含まれるエッジを 1 つずつ取ってくる（このエッジを e1 とする）．

た．現在のところ，対象言語は Java のみであるが，ソースコードから PDG を構築するモジュールを実装すれば，他のプログラミング言語に対しても適用することができる．
また，データベースには SQLite を利用している．

なお，この処理は，メソッド ID を元にしたデータベースへの問合せで実現している．入力として与えられた

4.1 PDG ノードの同値関係

メソッドのソースコードが解析されるわけではない．

提案手法では，PDG ノードの同値関係については定義

3 行目 データベース検索を用いて，エッジ e1 と等価なしていないため，実装したツールでは，以下の定義を用い

エッジ（このエッジを e2 とする）を 1 つずつ取ってくる．

4 行目 エッジ e1 と e2 を引数として，アルゴリズム createを用いてクローンペア情報を構築し，C に加える．

Algorithm 2 create (e1 , e2 , U )Input: e1 , e2 : エッジのペア，U : すでにチェックしたエッジの集合
Output: (S1 , S2 ): u1 ∈ S1 かつ u2 ∈ S2 である outputclonepair
1: (S1 , S2 ) ← ({e1 }, {e2 })2: U ← U ∪ {e1 , e2 }3: for all ex such that incident(e1 , ex ) ∧ ex ∈ U do
4:
for all ey such that ex ≡ ey ∧ incident(e2 , ey ) ∧ ey ∈ U
do
5:(Sx , Sy ) ← create(ex , ey , U )6:(S1 , S2 ) ← (S1 ∩ Sx , S2 ∩ Sy )7:
end for
8: end for
9: return (S1 , S2 )ている．
定義 13（PDG ノードの同値関係） s1 と s2 をプログ
ラムの要素とし，v1 と v2 はそれらを表す PDG のノードとすると，同値関係は以下の式で定義される．

v1 ≡ v2 := normalize(s1 ) = normalize(s2 )normalize は正規化処理を行う関数であり，変数とリテラルを下記のルールで正規化を行う．
変数 変数ごとに特殊な字句が用意される．型が同じであっても違う変数は違う字句に置換される．
リテラル リテラルの型ごとに特殊な字句が用意される．
型が同じであれば，値が違っていても同じ字句に置換される．

4.2 データベース構成
ツールのデータベースには 5 つのテーブルが存在してい次にアルゴリズム create（Algorithm 2）を説明する．こる．表 1 にそれらを示す．解析処理で取得したエッジは，のアルゴリズムは，エッジのペアを入力として受け取り，

エッジテーブルに登録される．各エッジにつき，そのエッ

そのエッジを含むクローンペアを出力する．以下に create

ジを含むメソッド ID，そのハッシュ値，始点の頂点 ID，終アルゴリズムの主要名部分を説明する．

点の頂点 ID を登録する．検出処理では，このハッシュ値

1 行目 引数で与えられた与えられたエッジのペア（e1 とを用いてデータベースからの等価なエッジの取得処理が行e2 ）を出力するクローンペアの要素（S1 と S2 ）とする．

われる．実装したツールでは，ハッシュ値を求めるアルゴ

2 行目 引数で与えられた 2 つのエッジをチェック済み

リズムとして MD5 を用いている．定義 2 に示すように，

エッジ集合に加える．

本論文では，エッジ e は (v1 , v2 , t) で表現している．よっ3 行目 e1 と隣接関係にあり，またチェックされていなて，e のハッシュ値は v1 ，v2 ，および t を結合したバイト

いエッジを 1 つずつ取ってくる（このエッジを ex と列の MD5 値として求める．始点ノードと終点ノードは IDする）．

が登録される．これは，同一のノードを始点および終点と4 行目 e2 と隣接関係にあり，まだチェックされておらず，して持つエッジが複数あっても，データベースサイズを大ex と等価なエッジを 1 つずつ取ってくる（このエッジ

きくしないための工夫である．ノードの情報はノードテー

を ey とする）．

ブルに保存されており，ノード ID をキーとしてその情報

5 行目 ex ，ey ，およびこれまでにチェックしたエッジのc 2012 Information Processing Society of Japan

を取得できる．

605

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

表 1

データベースのテーブル一覧

Table 1 Tables in database.
テーブル名

登録内容

エッジ

メソッド ID，ハッシュ値，始点のノード ID，終点のノード ID

ノード

ノード ID，メソッド ID，開始位置，終了位置

ファイル

ファイル ID，ファイル名（ファイルへの絶対パス），更新時刻

メソッド

メソッド ID，メソッド名

対応関係

ファイル ID，メソッド ID

また，ファイルの情報を登録するためのテーブルがあり，行われている．近年，コードクローンの存在がどの程ファイル ID，ファイル名（ファイルの絶対パス），更新時

度ソフトウェア保守作業を阻害しているのかを調査す

刻が登録される．このテーブルを用いることにより，更新る試みが行われている [8], [11], [12]．また，コードク

されたファイルのファイル ID を取得する．

ローンの履歴情報を可視化する手法も提案されていファイルとメソッドの対応関係（どのファイルの中にどのメソッドが存在しているか）は，対応関係テーブルに保存される．一部のファイルが更新された場合には，ファイ

る [2]．このような研究では，増分的な検出法を用いる
ことによって，効率的に検出処理を行える．
項目 2

あるコード片からバグを検出した場合は，そのコー

ルテーブルと対応関係テーブルを用いて，更新されたファ

ド片とコードクローンになっている部分についても同イルにあるメソッドの ID を取得し，それを用いてエッジ様のバグがないかを調査することが望ましい．本項目

テーブルに登録されている更新されたファイルの古いエッではそのような状況を想定して，ある 1 つのファイル

ジ情報を削除する．

が指定されたときに，それとコードクローンになって

5. 評価
本章では，提案手法を評価するために行った実験についいる部分を検出するのに必要な時間を測定する．

5.1.1 項目 1 の評価
この項目の評価は下記の手順で行われた．

て述べる．この実験は以下の 2 つの実験からなる．

STEP1 最初のリビジョンをチェックアウトする．

実験 A

提案手法の検出速度を評価するための実験．効率

STEP2 最初のリビジョンからコードクローンを検出す的にコードクローンが検出できているのかどうかを確る．この STEP では，すべてのソースファイルに対し認する．

て解析処理と検出処理が実行される．

実験 B

提案手法の検出精度を評価するための実験．PDGを用いた検出法として，検出結果が適切であるかどうかを確認する．
なお，この実験は，下記に示す仕様のワークステーショ
ンを用いて行った：

CPU Intel Xeon E5405（quad-core, 2.0 GHz）
Memory 8 GB
OS Windows 7 Enterprise（64 bit）
実験対象は，Ant である．Ant を実験対象とした理由を下記に示す．

STEP3 次のリビジョンをチェックアウトする．
STEP4 STEP3 でチェックアウトしたリビジョンから
コードクローン検出を行う．この STEP では，アップ
デートされたファイルについてのみ解析処理が実行され，すべてのファイルに対して検出処理が実行される．

STEP5 もし次のリビジョンが存在すれば，STEP3 に戻る．
この評価では，STEP2 と STEP4 の合計時間を計測した．その結果，5,903 リビジョンから 15 時間 2 分でコー
ドクローン検出を完了できた．リビジョンごとの検出時間• Ant は Java 言語を用いて開発されている．現在のとを図 4 に示す．また，PDG を用いたコードクローン検出

ころ，提案手法を実装したツールが対応しているのは

ツール Scorpio [6] を利用して，増分的でない検出の時間をJava 言語のみである．

測定した．増分的でない検出では，STEP2 と STEP4 にお• Ant の最新リビジョンの規模が約 20 万行あり，またいて，そのリビジョンに含まれるすべてのソースファイル

開発期間も数年と実験対象規模として十分なため．

をから Scorpio を用いてコードクローン検出を行った．約3,300 リビジョンを 1 日で解析できたが，システムが大き5.1 実験 A：検出時間の評価
この実験では，下記の 2 つの項目について評価を行った．
項目 1

くなるに従って検出時間も長くなり，すべてのリビジョン
からの検出を終えるのに約 4 日半を要した．

Ant のすべてのリビジョンに対して順にコードク

すべてのリビジョンに対して，その前のリビジョンとのローン検出を行い，その時間を測定した．このような間で更新されたファイル数を調べたところ，平均値が 3.53，

検出処理は，コードクローンに関係する研究で頻繁に中央値が 1，最大値が 733 であった．つまり，多くのリビ

c 2012 Information Processing Society of Japan

606

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

図 4

Ant の各リビジョンからコードクローンを検出するのに必要な時間
Fig. 4 Elapsed time to detection for every revision.

表 2

項目 2 の実行時間たファイルが，左から n 番目の区域に入る．つまり，n 番

Table 2 Detection time in context 2.
処理
実行時間

STEP1
3 分 18 秒

STEP3目の区域の棒グラフの値は，検出時間が 500n ミリ秒以上

500(n + 1) ミリ秒未満であったファイルの数である．たと

平均値

中央値

最大値

2.9 秒

2.2 秒

12.8 秒えば，ラベルが 1 の区域は，検出時間が 500 ミリ秒以上 1
秒未満であったファイルの数を表している．この図より，多くのファイルに対する検出処理が数秒以内で終わっていることが分かる．つまり，ユーザは，着目しているファイルを検出対象として指定すると，その数秒後にはそのファイルに関連するコードクローン群を得ることができる．Scorpio を用いた場合には検出に数分を必要とするため，提案手法を用いることにより，検出の高速化が実現されていることが分かる．

図 5 各ファイルに対する検出時間の分布

Fig. 5 Frequency table of detection time for each file.

5.2 実験 B：検出精度の評価
検出精度の評価では，既存の PDG を用いた検出ツール
である Scorpio [6] と検出結果の比較を行った．この評価でジョンでは，少数のファイルのみが更新されており，残りも，実験 A の項目 1 と同様に，Ant の最新リビジョンを検の更新されていないファイルについてはエッジの情報が再出対象とした．比較対象として Scorpio を用いたのは以下利用されている．この再利用により，ファイル読み込み，の 2 つの理由のためである．

ソースコード解析，PDG 構築のコストが抑えられ，増分• Scorpio は提案手法と同じく実行依存付きの PDG を的でない検出との間で検出時間に差がでた．今回実験対象

用いて検出処理を行うため，同型部分グラフをコードとした Ant のように，リビジョン間での更新されたファイクローンとして検出する方法と，提案手法の検出法のル数が全ファイル数に対して非常に少ない場合には，大き差違を適切に比較することができる．

な速度向上を期待できる．

5.1.2 項目 2 の評価
項目 2 の評価は，Ant の最新リビジョン（リビジョン番
号：1,075,177，ファイル数：804，行数：203,580）に対して，下記の手順で行った．

• Scorpio は著者らの研究グループで開発されたツールであり，検出の設定方法を熟知しているため，提案手法となるべく同じ設定にして検出処理を行うことができる．
また，提案手法と Scorpio が検出したコードクローンがSTEP1 すべてのファイルに対して解析処理を実行．

一致するかどうかの判定には，Bellon らが提案した good

STEP2 各ファイルに対して検出処理を実行．

値と ok 値 [4] を用いた．good 値と ok 値の定義について

表 2 は，STEP1 と STEP2 に要した時間を表している．

は付録を参照されたい．good 値と ok はいずれも 2 つのク

STEP1 ではデータベースを作成するために，3 分 18 秒がローンペアのオーバラップの程度を 0%〜100%の割合で表必要であった．STEP2 では，単一ファイルに対する検出す指標である．これらの値を用いることにより，提案手法

処理は最大でも 12.8 秒であり，項目 2 の状況で実用的に利により検出されたクローンペアと Scorpio により検出され用可能な検出速度といえる．

たクローンペアのオーバラップの程度を計測し，閾値以上

図 5 は，各ファイルに対する検出時間のヒストグラムを表している．X 軸は，500 ミリ秒ごとに区切られており，検出時間が 500n ミリ秒以上 500(n + 1) ミリ秒未満であっc 2012 Information Processing Society of Japan

であれば，同一のクローンペアであると見なした．この実
験では，これらの値の閾値として 70%を用いた．

804 個のソースファイルから，提案手法は 831 個，Scorpio

607

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)50:

e = replyToList.elements();51:

while (e.hasMoreElements()) {52:

mailMessage.replyto(e.nextElement().toString());

53:

}

+

54:

e = toList.elements();+

55:

while (e.hasMoreElements()) {+56:

String to = e.nextElement().toString();

57:

try {

58:

mailMessage.to(to);+59:

atLeastOneRcptReached = true;

+

60:

+

61:

} catch (IOException ex) {badRecipient(to, ex);

62:
63:

}
}

++- 64:e = ccList.elements();++- 65:

while (e.hasMoreElements()) {++- 66:

String to = e.nextElement().toString();

67:

try {

68:

mailMessage.cc(to);++- 69:atLeastOneRcptReached = true;+- 70:} catch (IOException ex) {+- 71:

badRecipient(to, ex);

72:
73:

}
}

+ -74:

e = bccList.elements();+ -75:

while (e.hasMoreElements()) {+ -76:

String to = e.nextElement().toString();

77:

try {

78:

mailMessage.bcc(to);+ -79:

atLeastOneRcptReached = true;-80:} catch (IOException ex) {-81:

badRecipient(to, ex);

82:
83:

}
}

図 6 提案手法と Scorpio で一致しなかったコードクローンの例

Fig. 6 Mismatched code clone between the proposed method and Scorpio.
表 3

提案手法の再現率と適合率

Table 3 Precision and recall of the proposed method.
評価項目

good

ok

適合率

0.922

0.970

再現率

0.990

1.000

は 724 個のクローンペアを検出した．表 3 は，Scorpio が検出したクローンペアの集合を正解集合とした場合の，提案手法の適合率と再現率を表している．Scorpio が検出したクローンペアの集合を Sscorpio ，提案手法の検出結果 R に含まれるクローンペアの集合を S(R)，ok 値を用いて抽出した共通のクローンペアの集合を S(R) ∩ok Sscorpio ，good 値を用いて抽出したクローンペアの集合を S(R) ∩good Sscorpioとすると，再現率は下記の式で表される．

|S(R) ∩ok Sscorpio |,Recallok (R) :=|Sscorpio |c 2012 Information Processing Society of Japan

Recallgood (R) :=|S(R) ∩good Sscorpio ||Sscorpio |(1)

また，適合率は，下記の式で表される．

P recisionok (R) :=|S(R) ∩ok Sscorpio |,|S(R)|

P recisiongood (R) :=|S(R) ∩good Sscorpio ||S(R)|(2)

なお，|A| は集合 A に含まれるクローンペアの数を表す．
つまり，再現率は Scorpio が検出したクローンペアをどの程度提案手法も検出したのかを表し，適合率は提案手法が見つけたクローンペアのうちどの程度が Scorpio によっても検出されていたのかを表す．表 3 より，適合率と再現率
はともに 1 に近い値であり，提案手法の検出結果は Scorpioの検出結果と近いことが分かる．つまり，提案手法は従来の PDG を用いた検出法と検出結果がきわめて似ている．
実験 A と実験 B の結果より，提案手法は従来の PDG を

608

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

用いた検出法と検出結果はほとんど変わらないが，検出にのアルゴリズムにより，連続*4 および非連続コードクロー

必要な時間を大幅に短縮できているといえる．

ン*5 を高速に検出できるようになった．Hummel らの手法

図 6 は，提案手法と Scorpio で一致しなかったクロー

は非連続コードクローンを検出することができない．

ンペアの例である．行頭の “+” は，その要素が提案手法にGöde らは，接尾辞木を改良し，情報の追加や削除が容易

よって検出されたコードクローンに含まれてることを表し

な汎用接尾辞木というデータ構造を定義して，それを用いており，“-” は，その要素が Scorpio によって検出された

た字句単位のコードクローン検出手法を提案している [5]．

コードクローンに含まれていることを表している．たとえ

接尾辞木とは，文字列に対して定義される文字数と等しい

ば，64 行目は提案手法によって検出されたクローンペアの個数の葉を持つ木構造であり，根からそれぞれの葉 i への両方のコードクローンと，Scorpio によって検出されたク

経路が文字列の i 文字目から最後の文字までの部分文字列

ローンペアの片方のコードクローンに含まれている．64，（接尾部）に対応する．接尾辞木を用いることで，文字列65，66，69 行目は，提案手法によって検出されたクローン

中の繰返し部分を高速に検出することができる．コードク

ペアの両方のコードクローンに含まれている．その 2 つのローン検出においては，コードクローンがソースコード中

コードクローンは，PDG 上ではノードを共有してはいるの繰返し部分であることから，プログラム全体を 1 つの文が，エッジは共有していない．提案手法のクローンペアの字列として接尾辞木を構築し，検出を行う手法が用いられ定義では，2 つのコードクローンがノードを共有することている [3], [10]．汎用接尾辞木は，1 つの文字列ではなく文は禁止していないので，このようなコードクローンが検出字列の集合に対して定義され，根から葉への経路は各文字される．一方，Scorpio は，コードクローンがノードを共有

列における接尾部に対応する．各ファイルをそれぞれ 1 つすることを禁止している．このような定義の違いにより，の文字列として汎用接尾辞木を構築することにより，ファ

図 6 に示すような一致しないコードクローンを検出されイルの追加や削除が容易になり，増分的な検出が可能にな

る*3 ．

る一方，コードクローン検出の精度には影響を与えないこ

6. 関連研究
Hummel らは，各行の内容と位置情報を蓄積して，同内とを示している．

7. おわりに容の行を検索することでコードクローンを検出する手法

本論文では，PDG を用いた増分的なコードクローン検を提案し，検出ツール ConQAT に実装している [9]．この出手法を提案した．また，提案手法を実装したプロトタイ

手法では，まずソースコード中の各行に対して，変数名なプを紹介し，それを用いて行った実験についても述べた．

どに対する置換を行ったうえで，ハッシュ値を計算する．

この実験により，提案手法は，開発履歴の全リビジョンか

そして，そのハッシュ値とファイル名や行番号を組にしたらのコードクローン検出を想定した実験では，従来の約情報を蓄積する．ある行に対してコードクローンとなる行

14%の時間で検出を完了することができ，バグを発見したは，この情報をその行のハッシュ値を用いて検索すること

ファイルとのコードクローン検出を想定した実験では，平で，取得することができる．検出結果として出力するのは均 2.9 秒で検出処理を終えることができた．また，提案手

複数行からなるコードクローンであるが，それについては

法と増分的な検出法ではない従来手法との検出結果の比較

あるコード片の各行とコードクローンになる行の集合からでは，従来手法の検出結果を正解集合とした場合の，提案容易に構築することができる．提案手法は，Hummel らの手法の検出結果は再現率が 99%以上，適合率が 92%以上と手法と類似度が高い．異なる点は，データベースに登録すなり，提案手法は従来手法とほとんど結果が変わらないこる単位とその単位からコードクローンを構築する方法であとを示した．

る．Hummel らの手法では，プログラムは行単位でデータ

今後は，さらに検出時間を短縮するために手法を改良す

ベースに登録されており，その情報から連続した行をコーる予定である．現在は，コードクローンの検出は，対象ファドクローンとして検出する．一方，提案手法は，プログラ

イルを与えることで行っているが，メソッドを与えること

ムは PDG のエッジ単位でデータベースに登録されており，でも検出ができるように改良を行う．バグ修正などのソー

その情報から，同型な木構造を構築し，それをコードク

スコード変更では，1 つのソースファイル全体にわたってローンとして検出する．手法の枠組み（検出の流れ）は，改変が加えられる場合よりも，その中の一部のメソッドの

Hummel らが提案しているものと同様であり，その点につみが改変される場合が多いと著者らは考えている．メソッ

いては新規性はない．提案手法の新規性は，等価なエッジ

ド単位での検出を実現することによって，前回までの検出群から木構造を構築するアルゴリズムである．しかし，こ*3

ここでは，一致しないコードクローンを紹介したのみであり，どちらのコードクローンがより適切かという議論はしていない．

c 2012 Information Processing Society of Japan


*4

*5

contiguous code clones．フォーマットの違い（改行位置，空白やタブの有無など）や字句単位の違い（変数名やリテラルの違いなど）のみを含むコードクローンを指す．
non-contiguous code clones. 字句単位よりも大きな違い（対応する文がない，文の順序が異なるなど）を含むコードクローン．

609

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)

結果を再利用できる割合が増えるため，より高速に検出処

mated Software Engineering, pp.336–339 (2004).

理を行うことができる．
謝辞 本研究は一部，文部科学省「次世代 IT 基盤構築のための研究開発」（研究開発領域名：ソフトウェア構

付

録

定義 1

2 つのコード片（f1 と f2 ）の重なりの程度を以下

築状況の可視化技術の開発普及）の委託に基づいて行わの式で定義する．なお，elements(f ) はコード片 f にれた．また，日本学術振興会科学研究費補助金基盤研究含まれるプログラム要素の集合を表す．

（ A）（課題番号：21240002）および萌芽研究（課題番号：

overlap(f1 , f2 ) :=23650014），文部科学省科学研究費補助金若手研究（B）（課
題番号：22700031）の助成を得た．
定義 2
参考文献
[1]
[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Clone Detection Literature, available fromhttp://www.cis.uab.edu/tairasr/clones/literature/.
Adar, E. and Kim, M.: Visualization and Exploration of
Code Clones in Context, Proc. 29th International Conference on Software Engineering, pp.762–766 (2007).
Baker, B.S.: Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance,
SIAM Journal on Computing, Vol.26, No.5, pp.1343–
1362 (1997).
Bellon, S., Koschke, R., Antoniol, G., Krinke, J. andMerlo, E.: Comparison and Evaluation of Clone Detection Tools, IEEE Trans. Softw. Eng., Vol.31, No.10,
pp.804–818 (2007).
Göde, N. and Koschke, R.: Incremental Clone Detection,
Proc. 13th European Conference on Software Maintenace and Reengineering (2009).
肥後芳樹，楠本真二：プログラム依存グラフを用いたコー
ドクローン検出法の改善と評価，情報処理学会論文誌，Vol.51, No.12, pp.2149–2168 (2010).
肥後芳樹，楠本真二，井上克郎：コードクローン検出とその関連技術，電子情報通信学会論文誌 D，Vol.J91-D,
No.6, pp.1465–1481 (2008).
Hotta, K., Sano, Y., Higo, Y. and Kusumoto, S.: Is
Duplicate Code More Frequently Modiﬁed than Nonduplicate Code in Software Evolution?: An Emprical
Study on Open Source Software, Proc. 4th International
Joint ERCIM/IWPSE Symposium on Software Evolution, pp.73–82 (2010).
Hummel, B., Juergens, E., Heinemann, L. and Conradt,
M.: Index-Based Code Clone Detection: Incremental,
Distributed, Scalable, Proc. 26th IEEE International
Conference on Software Maintenance, pp.1–9 (2010).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: A
Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code, IEEE Trans. Softw.
Eng., Vol.28, No.7, pp.654–670 (2002).
Krinke, J.: Is Cloned Code more stable than Non-Cloned
Code?, Proc. 8th IEEE International Working Conference on Source Code Analysis and Manupulation,
pp.57–66 (2008).
Lozano, A. and Wermelinger, M.: Assessing the eﬀect ofclones on changeability, Proc. 24th International Conference on Software Maintenance, pp.227–236 (2008).
三宅達也，肥後芳樹，楠本真二，井上克郎：多言語対応
メトリクス計測プラグイン開発基盤 MASU の開発，電子情報通信学会論文誌 D，Vol.J92-D, No.9, pp.1518–1531(2009).
Rysselberghe, F. and Demeyer, S.: Evaluating Clone
Detection Techniques from a Refactoring Perspective,
Proc. 19th IEEE International Conference on Auto-c 2012 Information Processing Society of Japan|elements(f1 ) ∩ elements(f2 )||elements(f1 ) ∪ elements(f2 )|(A.1)

あるコード片（f1 ）が他のコード片（f2 ）に含まれている程度を以下の式で定義する．

contain(f1 , f2 ) :=定義 3

|elements(f1 ) ∩ elements(f2 )||elements(f1 )|(A.2)

2 つのクローンペア（p1 と p2 ）の good 値は以下の式で定義される．

good(p1 , p2 ) := min(overlap(p1 .f1 , p2 .f1 ),overlap(p1 .f2 , p2 .f2 ))(A.3)

図 A·1 には 2 つのクローンペア（p1 と p2 ）が存在している．この場合，good 値は，

good(p1 , p2 ) = min

5 6
,
8 8


=

5
8

となる．閾値が 0.7 の場合， 58 ≤ 0.7 であるため，2 つのクローンペアは一致しない．
定義 4

2 つのクローンペア（p1 と p2 ）の ok 値は以下の式で定義される．

ok(CP1 , CP2 ):= min(max(contained(CP1 .CF1 , CP2 .CF1 ),contained(CP2 .CF1 , CP1 .CF1 )),max(contained(CP1 .CF2 , CP2 .CF2 ),contained(CP2 .CF2 , CP1 .CF2 )))(A.4)

図 A·1 の例を用いた場合，ok 値は，






5
5 5
6 6
,
,
ok(p1 , p2 ) = min max
, max
=
6 7
6 8
6

図 A·1 good 値と ok 値の算出例

Fig. A·1 Sample calculation of good and ok values.

610

情報処理学会論文誌

Vol.53 No.2 601–611 (Feb. 2012)となる．閾値が 0.7 の場合，0.7 ≤ 56 であるため，2 つのクローンペアは一致する．

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

植田 泰士
平成 13 年大阪大学基礎工学部情報科学科卒業．平成 15 年同大学大学院博士前期課程修了．現在，宇宙航空研究開発機構所属．在学中，コードクロー
ン分析の研究に従事．

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

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

c 2012 Information Processing Society of Japan

611