論 文
グラフマイニングアルゴリズムを用いたギャップを含むコードクロー
ン情報の生成肥後 芳樹†

宮崎 宏海†

楠本 真二†

井上 克郎†

Generating Gapped Code Clone Information using Graph Mining Algorithm
Yoshiki HIGO† , Hiromi MIYAZAKI† , Shinji KUSUMOTO† , and Katsuro INOUE†

あらまし これまでにさまざまなコードクローン検出手法が提案されているが，ギャップ (不一致部分) を含む
コードクローンを検出できる手法は少ない．本論文では，ギャップを含むコードクローンを検出できないコード
クローン検出手法の出力結果に対して後処理を行うことで，ギャップを含むコードクローン情報を生成する手法を提案する．提案手法は，グラフマイニングアルゴリズムの一つである AGM アルゴリズムを用いており，効率的にギャップを含むコードクローン情報を生成することができる．提案手法を検出ツール CCFinder のポストプ
ロセッサとして実装し，複数のオープンソースソフトウェアに対して適用したところ，多数の興味深いコードク
ローン情報を得ることができた．しかし，提示する必要がないと思われるコードクローンも生成してしまうことがあった．本論文では，この実験の結果について述べ，また，上記の問題に対する解決策についても考察する．
キーワード

コードクローン，グラフマイニングアルゴリズム，ソフトウェア保守な定義は存在せず，各手法は独自に異なったコードク

1. ま え が き

ローンの定義をもつ [5], [6]．そのため，同一ソフトウェ

近年，ソフトウェア開発および保守を困難にしている要因の一つとしてコードクローンが注目されている．
コードクローンとはソースコード中に存在する，他のコード片と同一または類似したコード片を指す言葉でアから検出処理を行った場合でも，用いる検出ツールが異なれば検出結果も異なる．

Bellon は，コードクローン間の違いの度合いに基づき，それらを以下の三つに分類している [7]．

ある [1]．コードクローンは，コピーアンドペーストやType1: 空白やタブの有無，括弧の位置などのコー

定型処理，パフォーマンス改善などのさまざまな理由

ディングスタイルを除いて，完全に一致するコードク

によりソースコード中に作りこまれる [2]〜[4]．一般的

ローンを指す．

に，コードクローンの存在により，ソフトウェア開発

Type2: 変数名や関数名などのユーザ定義名，定および保守が困難になるといわれている．例えば，あ数，または変数の型などの一部の予約語のみが異なる

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

コードクローンを指す．

ローン全てに対して同様の修正の是非を検討する必要

Type3: コピーアンドペースト後に文の追加や削がある．このような作業は，特に大規模ソフトウェア

除，変更が行われたなどの結果により，ギャップ (不一では非常に大きな手間を必要とする．したがって自動致部分) を含むコードクローンを指す．

的にコードクローンを検出し，その情報を用いること

図 1 は，コピーアンドペーストによる再利用の流れ

は，ソフトウェア開発および保守を行うにあたり，非を表している．単にコピーアンドペーストを行っただ

常に有効であるといえる．

けの再利用であれば，コピー元とコピー先は完全一致

これまでに，さまざまなコードクローン検出手法がクローンになる．コピーアンドペースト後に変数名な提案されているが，コードクローンの厳密で普遍的どの付け替えを行えば，名前変更クローンとなる．さらに，コピーしたコード片を文単位で変更した場合は，†大阪大学大学院情報科学研究科，吹田市
Graduate School of Information Science and Technology, Osaka University, Suita-shi, 565-0871, Japan

ギャップを含むコードクローンとなる．
本論文では，Type1 および Type2 のコードクロー

電子情報通信学会論文誌 X Vol. Jxx–X No. xx pp. 1–10

xxxx 年 xx 月

1

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

If (a > b) { b++; a=1;}

resued by ‘copy-andpaste’
コピーアンドペーストによるによる再利用
コピーアンドペースト
による再利用識別子の識別子の変更文の挿入
If (a > b)
{
b++;
a=1;
}

If (i > j)
{
j++;
i=0;
}

If (i > j){i = i / 2;
j++;
i=0;
}

完全一致クローン
完全一致クローン 名前変更
名前変更クローン
クローン
（タイプ１
タイプ１）
（タイプ２
タイプ２）
図1

文の変更

文の削除
If (i > j)
{
i=0;
}

If (i > j){
j = j + 1;
i=0;
}

ギャップを
ギャップを含むクローン
（タイプ３
タイプ３）

コピーアンドペーストによる再利用の流れ
Fig. 1 Reuse by copy and paste

ンの位置情報から，Type3 のコードクローンの位置情

Ueda の手法は，CCFinder が検出したコードクロー

報を生成する手法を提案する．提案手法は，グラフマンのペアのうち，ソースコード上で近くに存在するもイニングアルゴリズムの一つである AGM アルゴリズのを散布図上でつなぎ合わせることでギャップを含む

ムを用いている．この手法は特定のコードクローン検

コードクローンを分析する手法を提案している [8]．散出手法に依存しておらず，任意の既存手法に対して適

布図上でギャップを含むコードクローンを認識するこ用可能である．提案手法をコードクローン検出の後処とができるため，利用者が興味のある部分に存在する理として用いることにより，分析者はより有益なコー

コードクローンを容易に分析することができる．しかドクローンの位置情報を得ることができる．

し，ギャップを含むコードクローンをセット（集合）として検出することができない．コードクローンのセッ

2. 研究の動機トに対してはこれまで有用なメトリクスが提案されており，それらに基づいて分析することで着目すべき

これまでに提案されているコードクローン検出手法

コードクローンを容易に発見できるとの研究報告があのうち，Ueda ら手法 [8] や Li らの手法 [9] など，一部

る [11], [12]．よって，セットとしてコードクローンをの手法は Type3 のコードクローンを検出できるが，そ認識することは重要である．

の他の多くの手法は Type3 のコードクローンを検出

Li らは，シーケンシャルパターンマイニング（注 1）のできない．しかし，コピーアンドペースト後に修正漏一つである CloSpan アルゴリズム [13] を利用して，れが起こるという報告があり [10]，そのようなコード

ギャップを含むコードクローンを検出可能なツール

クローンは Type3 になりえるため，タイプ 3 のコー

CP-Miner を開発している [9]． CP-Miner はまず，対ドクローンを検出することはソフトウェア保守の観点

象プログラムに対して文単位でハッシュ化を行なう．

から重要である．検出するコードクローンの大きさのこれにより，対象プログラムは，数値のシーケンスに閾値を下げることにより，一つのギャップを含むコー変換される．このシーケンスに対して CloSpan アル

ドクローンを複数の完全一致クローンまたは名前変更

ゴリズムを適用することにより頻出するサブシーケ

クローンとしては検出することは可能であるが，分析ンスを検出し，それを元のプログラムと対応させるこ

者自らがそれら複数のコードクローンを一つのギャッ
プを含むコードクローンであると認識しなければならず，効率的に分析作業ができるとはいえない．
2（注 1）：シーケンシャルパターンマイニングとは，アイテムの発生順序を保った上で，頻出シーケンスを抽出する手法である．

論文／グラフマイニングアルゴリズムを用いたギャップを含むコードクローン情報の生成とにより，コードクローンを検出している．CloSpan

$

'
1)

Main(G,minsup){は，サブシーケンスが連続していなくても検出可能な

2)

C1 ←{ 大きさ 1 の多頻度グラフの候補の隣接行列 };アルゴリズムである．例えば，シーケンス agbch には

3)

k←1;

4)

サブシーケンス abc が一つ存在していると認識する

while(Ck =∅){|

5)

Count(G,Ck );ことができる．つまり，CloSpan アルゴリズムを利用

6)

Fk ← {ck ∈ Ck | sup(G(ck )) >= minsup};7)

することでギャップを含むコードクローンの検出が可Ck+1 ← Generate − Candidate(Fk );8)

能になっている．CloSpan のアルゴリズム自体は大き

9)

}

10)

returnなギャップを含んだサブシーケンスも検出可能である
が，CP-Miner では高速に検出処理を完了するために，ギャップの大きさが 3 以上の場合はサブシーケンスの11)k ← k + 1;}∪k{fk ∈ Fk | fk is canonical};&%

図 2 AGM アルゴリズムの概要
Fig. 2 Overview of AGM algorithm

検出を行なわない（つまり三つの文以上の大きさのギャップがある場合は，ギャップを含むコードクロー
ンとして検出されない）．
以上の既存研究を踏まえ，下記のような特徴を持つ
ギャップを含むコードクローンの検出手法が必要であると著者は考えた．

•

ギャップを含むコードクローンをペアとしてだ

けでなく，セットとして検出可能な手法．

•

短いギャップだけでなく，大きなギャップに対しても，それらを含むコードクローンをある程度高速に検出可能な手法．
この条件を満たす手法として，本論文では AGM ア
ルゴリズムを用いてギャップを含むコードクローンを検出する手法を提案する．提案手法ではまず，既存の検出ツールを用いて，完全一致クローンと名前変更クローンを検出する．そして，それらを頂点とするグラフをソースファイル毎に構築し，そのグラフ中に存在する頻出パターンを抽出する．ギャップを含むコード
クローンは，抽出された頻出パターンの各インスタン
スであり，ペアではなく，セットとして検出される．
また，グラフでは，大きなギャップも小さなギャップ
も 1 つの辺として同様に扱われているため，ギャップの大きさに依存せずにコードクローンが検出される．
しかし，グラフの集合から頻出パターンを抽出することは NP 完全として知られる部分グラフ同型同型であるため，膨大な計算コストを必要とする．この問題を改善するため，提案手法では，抽出するパターンに制限を加えることにより（パターンの制限は，AGM ア
ルゴリズムの文献 [14] にて提案されている方法で行なう），少ない計算コストで検出処理を行なう．

3. AGM アルゴリズム
AGM(Apriori-based Graph Mining) アルゴリズム
は，複数のラベル付きグラフに含まれる多頻度グラフ

パターンを効率的に抽出するアルゴリズムである [14]．

AGM アルゴリズムの概要を図 2 に示す．ここで Gはグラフの集合，Fk は大きさ k の多頻度グラフの隣接行列の集合，Ck は大きさ k の多頻度グラフの候補
隣接行列の集合を指す．大きさ k のグラフとは，k 個の頂点から構成されているグラフを意味する．また，minsup は，多頻度とするために最低限必要な出現回数を表す．

AGM アルゴリズムは，大きさが 1 の多頻度グラフ
パターンから，順にサイズの大きなグラフパターンを抽出していく．以下に AGM アルゴリズム (図 2) の大まかな流れを示す．

2 行目: 1×1 の隣接行列が頂点ラベルの数だけ生成され，C1 に代入される．

5-6 行目: 大きさが k である多頻度グラフパターンの候補の支持度を求め（注 2），支持度が minsup 以上であれば（注 3），Fk に加える．

7 行目: 大きさ k の多頻度グラフパターンを組み合わせて，大きさ k + 1 の多頻度グラフの候補を生成する．
この操作は Ck が空集合になるまで続けられる．

10 行目: 全ての多頻度グラフパターンが出力される．
大きさが k の多頻度グラフパターンから，大きさが k + 1 の多頻度グラフパターンの候補を生成する
際の条件を変えることにより，連結グラフパターン，
順序木パターン，グラフのパスなど，さまざまなグラ
フパターンを取り出すことが可能である．この手法を

B-AGM(Biased Apriori-based Graph Mining) と呼ぶ．詳細については文献 [14] を参照されたい．
提案手法では，グラフのパスを抽出する条件を用い（注 2）：Count(G, Ck ) は，グラフ集合 G 内でのグラフパターンの集
合 Ck に含まれる各パターンの出現数 (支持度) を計測する関数である．
（注 3）：sup(G(ck )) は，パターン ck の出現数 (支持度) を返す関数である．

3

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xxて，グラフの頂点を Type1 や Type2 のコードクロー

ソースファイル f1

ン，グラフの辺をコードクローン間のギャップとして，多頻度グラフパターンを抽出する．

4. 提 案 手 法
提案手法の入力と出力は以下のとおりである．

ソースファイル f2

ソースファイル fn

a3

a1・・・・・ by

b2
a2
c1

b1

入力: （既存のツールによって検出された）Type1

コードクローン検出対象ファイル: {f1, f2,・・・,fn}
クローンセットA: {a1, a2,・・・,ax}
クローンセットB: {b1, b2,・・・,bｙ}
クローンセットC: {c1, c2,・・・,cｚ}と Type2 のコードクローンの位置情報，
出力: 生成したギャップを含むコードクローンの位(a) 対象ファイル中のコードクローン

置情報．
なお，本論文では，コードクローンの位置情報は，

グラフ gf1(1) そのコードクローンを含むファイル，(2) コード
クローンの開始位置，(3) コードクローンの終了位置，

a1

グラフ gf2

a3

AAの三つの情報からなる．
提案手法は，以下の手順でギャップを含むコードク
ローンの位置情報を生成する．
手順 1: 各ソースファイルのグラフを構築，
手順 2: 多頻度サブグラフ（ギャップを含むコード

a2

A
B

b1

・・・・・

B

c1

by

B

C

対象ファイルから生成されたグラフ: {gf1, gf2,・・・,gfn}
ノードのラベル: {A, B, C}

クローン）の検出，(b) 生成されたグラフ

手順 3: 生成したコードクローンの位置情報の出力．
手順 1 では，入力として与えられた Type1 およびb2

グラフ gf3

Fig. 3図 3 グラフ構造の生成
Generating graphs from source code

Type2 のコードクローンの位置情報を元に，AGM ア
ルゴリズムの入力となるグラフ集合を構築する．手順

2 では，AGM アルゴリズムを用いて，手順 1 で構築

対して実行し，ソースファイル毎にグラフを構築する．

したグラフ集合に現れる多頻度サブグラフを検出する．

一部がオーバーラップしている場合や，あるコード最後に手順 3 では，手順 2 で検出した多頻度サブグラ

クローンが他のコードクローンを完全に包含している

フをギャップを含むコードクローンの情報として出力場合には，これら二つの頂点の間には辺を引かない．

する．以下，各手順の詳細を述べる．

このような部分は，コピーアンドペースト後の修正に

手順 1: 各ソースファイルのグラフを構築より発生したギャップを含むコードクローンであると入力として与えられた Type1 および Type2 のコーは考えにくいからである．また，二つのコードクロー

ドクローンの位置情報を元に（注 4），それらを頂点とす

ンがあまりに遠く離れている場合も，それらの頂点間るグラフをソースファイル毎に作成する．同一クローには辺を引かない．この場合も，コピーアンドペース

（注 5）

ンセット

に含まれるコードクローンから生成された頂点は同一ラベルをもつ．ある 2 つのコードクロー

ト後の修正により発生したコードクローンであるとは考えにくいからである．

ンがあり，それらがオーバーラップしていない場合は，

図 3 は，グラフ構築の例を表している．この例では，対応する頂点間に辺を引く．ファイル内における位置

n 個のコードクローン検出対象ファイル {f1 ,f2 ,· · ·,fn }が上位から下位のコードクローンに向けて辺が引かれから，三つのクローンセット A,B,C が検出されている．

る．この操作を全てのコードクローンの組み合わせにクローンセット A には x 個のコード片 {a1 ,a2 ,· · ·,ax }，クローンセット B には y 個のコード片 {b1 ,b2 ,· · ·,by }，（注 4）：手順 1 では，既存のツールによって検出された全てのコードク
ローンが用いられる．Type1 のみを検出可能なツールを用いた場合はType1 のコードクローンの位置情報のみが用いられ，Type1 と Type2の両方を検出可能なツールを用いた場合は，Type1 と Type2 のコードクローンの位置情報が用いられる．
（注 5）：クローンセットとは，互いに類似したコード片を全て含んだ集
合である．

4

クローンセット C には z 個のコード片 {c1 ,c2 ,· · ·,cz }が含まれている．図 3(b) は，生成されたグラフを表している．ファイル f1 では，三つのコード片 a1 ，a2 ，b1 が存在しているが，a2 と b1 はオーバーラップしているため，それらの頂点間には辺が引かれていない．

論文／グラフマイニングアルゴリズムを用いたギャップを含むコードクローン情報の生成

手順 2: 多頻度サブグラフの検出
手順 1 で構築したグラフ集合に対して AGM アル
ゴリズムを適用し，そのグラフ集合に現れる多頻度グ

用いて行えるようになる．

6. 適 用 実 験

ラフパターンを抽出する．具体的には，グラフ集合に

6. 1 概二回以上 (AGM アルゴリズムにおける最小支持度以提案手法を用いることにより，どのようなコードク

要上) 出現するパスをギャップを含むコードクローンのローンが検出されるかを調査するために適用実験をパターンとする．多頻度グラフパターンを求めた後，行った．この実験には，前節で述べたポストプロセッ

各パターンのインスタンスがグラフのどの部分に存在サを用いた．対象ソフトウェアは，C 言語で記述さするのかを求める．図 3 の場合では，ファイル f1 のれた Canna 3.6 と httpd 2.2.4，および Java 言語でパス a1 b1 とファイル f2 のパス a3 b2 がギャップを含む

記述された Ant 1.6.0 と JHotDraw 7.0.9 の四つであ

コードクローンとして検出される．

る．この実験では，CCFinder は字句以上のコードク

手順 3: 生成したコードクローンの位置情報の出力

ローンを検出するように設定し，コードクローン間の手順 2 で検出したギャップを含むコードクローンのギャップが 30 字句以内の場合に，それらに対応する頂位置情報を，入力として与えられたコードクローンの点間に辺を引くことにした．表 1 は，対象ソフトウェ

位置情報と同様のフォーマットで出力する．

アの規模を表している．なお，ギャップを含むコード

5. 実

装

クローン情報の生成に要した時間は，CCFinder の実行も含めて数分から十数分であった．

提案手法をコードクローン検出ツール CCFinder [3]提案手法を定量的に評価するために，以下の基準をのポストプロセッサとして実装した．CCFinder は，設け，各基準に該当するギャップを含むクローンセッ

検出したコードクローンの位置情報をテキスト形式で

トの数を調査した．

出力するツールであり，分析作業は付属の可視化ツー(1) 複数関数: 一つのコードクローンが複数の関数

ル Gemini [15] を用いて行う．CCFinder は，ソース

やメソッドにまたがっているクローンセットを指す．

コードの字句解析を行い，分割した字句単位で比較を一つの関数内に閉じたコードクローンは，ギャップ部行うことによりコードクローンを検出する．CCFinder

分（処理内容が異なる部分）が関数内にあり，そのよ

は Type １と Type2 のコードクローンを検出可能でうな処理の違いを含むコードクローンを検出することある．CCFinder を用いた従来の（つまり Type1 とは有益である．一方，複数の関数にまたがって存在しType 2 のコードクローンの）検出および分析手順はているコードクローンは，関数の外側にギャップが存

以下のとおりである．

在するため，そのようなコードクローンを検出する価（ 1 ） CCFinder を用いて（Type １と Type2 の）値はないと著者は考える．

コードクローンを検出，(2) オーバーラップ: 同一クローンセットに含まれ（ 2 ） Gemini を用いて検出されたコードクローン

るコードクローンがオーバーラップして存在しているの分析．

ことを指す．オーバーラップしているので，コピーア

一方，実装したポストプロセッサを用いた（Type3 のンドペーストにより生成されたとは考えにくい．その

コードクローンの）検出及び分析手順は以下のとおり

ため，このようなコードクローンを検出する価値はなである．

いと著者は考える．

（ 1 ） CCFinder を用いて（Type １と Type2 の）(3) 調査の必要がない: コードクローンの中には，

コードクローンを検出，（ 2 ） ポストプロセッサを用いて Type3 のコード
表 1 対象ソフトウェア
Table 1 Target software

クローン情報を生成，（ 3 ） Gemini を用いて生成されたコードクローンの分析．
このように，実装したポストプロセッサを用いることによって，Type1 とタイプ 2 に加えて Type3，つまりギャップを含むコードクローンの分析も Gemini を

名前
Canna
httpd
Ant
JHotDraw

ソフトウェア規模
バージョン 記述言語 ファイル数 総行数
3.6
C 言語
96
90,326
2.2.4
C 言語
760 409,489
1.6.0Java 言語627 180,844
7.0.9Java 言語
471
90,2145

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

ソフトウェア開発・保守を行う視点でそれらを扱う場

int i;

合に，対象とする必要が無いものが存在する．これ

d->nbytes = 0;
yc->kouhoCount = 0;らのコードクローンの多くは，連続した変数宣言や

if (yc->ys < yc->kEndp || yc->ye != yc->kEndp) {i = yc->curbun; /* とっとく */if (chikuji_subst_yomi(d) == -1) {makeGLineMessageFromString(d, jrKanjiError);
return TanMuhenkan(d);}if (RkwGoTo(yc->context, i) == -1) {(void)makeRkError(d, "文字列1", "文字列2");/* 文節の移動に失敗しました */return TanMuhenkan(d);}yc->curbun = i;}if ((yc->nbunsetsu = RkwEnlarge(yc->context)) <= 0) {(void)makeRkError(d, “文字列1”, “文字列2");/* 文節の拡大に失敗しました */return TanMuhenkan(d);}if (chikuji_restore_yomi(d) == NG) {return TanMuhenkan(d);}yc->status |= CHIKUJI_OVERWRAP;
makeKanjiStatusReturn(d, yc);return d->nbytes;

import 文，switch 文の連続した case エントリなど，
繰り返し構造をもつことがわかっている [12]．この実
験では，文献 [12] で紹介されている，繰り返し構造をもつコードクローンを，調査の必要がないコードク
ローンとした．

(4) 有益: この実験では，関数内にギャップを持ち，同一クローンセットに属する他の全てのコードクロー
ンともオーバーラップしておらず，文献 [12] で紹介されている繰り返し構造を持っていない場合に，そのギャップを含むコードクローンは検出を行う価値があると考え，有益とした．

6. 2 調 査 結 果
対象ソフトウェアから検出されたギャップを含むコー(a) コード片 1：変換対象領域の拡大処理

ドクローンのソースコードを全て閲覧し，各基準に該
int i;

当するクローンセットの数を計測した．表 2 に検出さd->nbytes = 0;
yc->kouhoCount = 0;
if (yc->ys < yc->kEndp || yc->ye != yc->kEndp) {i = yc->curbun;
if (chikuji_subst_yomi(d) == -1) {makeGLineMessageFromString(d, jrKanjiError);
return TanMuhenkan(d);}if (RkwGoTo(yc->context, i) == -1) {(void)makeRkError(d, "文字列1", "文字列2");/* 文節の縮小に失敗しました */return TanMuhenkan(d);}yc->curbun = i;}

れたギャップを含むクローンセットの総数および各基準に該当した個数を示す．なおこの調査は本論文の著者が行い，作業には約 40 人時を要した．この表から，各ソフトウェアから検出されたソフトウェアのうち，およそ 25%∼35%のギャップを含むクローンセットが有益であると判定されたことがわかる．
有益と判定されたギャップを含むコードクローンの例を示す．図 4 は Canna から検出されたコードクローンである（注 6）．コード片 1(図 4(a)) は日本語の変換処
理対象領域を拡大する処理を実装しており，コード片2(図 4(b)) は，その領域の縮小処理を実装している．
縮小処理のコード片には，さらに縮小可能かを判定する処理が含まれており，この部分が拡大処理とのギャップになっている (図 4(b) の行頭が G の部分)．ソース
コード中のコメントから，開発者はこの処理の正しさについて確信がないことがわかる．ギャップを含む
コードクローンを検出することにより，このような調査を行う必要がある部分を発見することができた．
全ての対象ソフトウェアからはかなりの数の，「(1)複数関数」，「(2) オーバーラップ」，「(3) 調査の必要が

G
G
G
G

if (RkwGetStat(yc->context, &stat) < 0 || stat.ylen == 1) {/* これ以上短くできるかどうか確認。要る？ */return NothingForGLine(d);}yc->nbunsetsu = RkwShorten(yc->context);
if (yc->nbunsetsu <= 0) { /* 0 ってことあんのかなあ？ */(void)makeRkError(d, “文字列1”, “文字列2");/* 文節の縮小に失敗しました */return TanMuhenkan(d);}if (chikuji_restore_yomi(d) == NG) {return TanMuhenkan(d);}yc->status |= CHIKUJI_OVERWRAP;
makeKanjiStatusReturn(d, yc);return d->nbytes;(b) コード片 2：変換対象領域の縮小処理

図 4 Canna から検出されたギャップを含むコードクローン
Fig. 4 A clone pair detected from Cannaない」，の基準に該当するクローンセットが検出されており，「(4) 有益」に該当するクローンセットの全体のコードクローンには，二つ以上のギャップが含まれに対する割合を下げていることがわかる．なお，一つていることがあり，このような場合は複数の基準に該当することがある．例えば，二つのギャップを含んで（注 6）：コード片 1 およびコード片 2 の文字列リテラル”文字列 1”および”文字列 2”は，実際にはもっと長い文字列であるが，ソースコードをよりわかりやすく掲載するために置換している．

6

いるコードクローンがあり，そのうちの一つが関数の外側，残りの一つが関数の内側にあった場合は，その論文／グラフマイニングアルゴリズムを用いたギャップを含むコードクローン情報の生成
表 2 検出されたギャップを含むクローンセットの内訳
Table 2 Classification of detected gapped code clones
ソフトウェア
Canna
httpd
Ant
JHotDraw

ギャップを含むクローンセットの数
合計 (1) 複数関数 (2) オーバーラップ (3) 調査の必要がない
208 130(62.5%)21(10.1%)20(9.6%)275 161(58.5%)29(10.5%)21(7.6%)113
73(64.6%)23(20.4%)
13(11.5%)
257 155(60.3%)
22(8.6%)22(8.6%)(4) 有益75(36.1%)
98(35.6%)30(26.5%)
87(33.9%)

コードクローンを含むクローンセットは，「(1) 複数関検出を防ぐことは可能であるが，検出対象ソフトウェ

数」と「(4) 有益」の両方の基準に該当する．

アのソースコード解析器を構築する必要があり，複数

7. 考

察

本節では，
「(1) 複数関数」，「(2) オーバーラップ」，「(3) 調査の必要がない」に該当するコードクローンが検出された原因を述べ，さらにそれらの検出を抑える対策について考察する．また，提案手法と，2. 節で紹介した CP-Miner [9] との間における検出されるコー
ドクローンの違いについても考察を行なう．

のプログラミング言語を対象とするような場合には，ポストプロセッサの実装に高いコストを必要とする．

ctags [16] などの既存のツールを用いて比較的容易に実装できるとも思われる．

7. 2 「(2) オーバーラップ」への対策
全ての対象ソフトウェアにおいて，検出されたク
ローンセットのうち約 10%はオーバーラップしたコー
ドクローンをもっていた．全ての対象ソフトウェアに

7. 1 「(1) 複数関数」への対策

は，独自の頻出する処理が存在しており，この部分か実験では，有益と判定されたクローンセットは，全らオーバーラップしたコードクローンが検出された．

体の約 25%∼35%であり，高い割合とはいえない．そ頻出する処理は，連続した if-else 文の各条件分岐先にの大きな原因は，「(1) 複数関数」に該当するクローン

存在しており，比較的互いに近い位置に存在していたセットが非常に多く検出されたことである．いずれのため，ギャップを含むコードクローンとして認識され対象ソフトウェアも，処理内容が類似した関数が多くてしまっていた．

定義されており，それらは連続した位置にあった．そ提案手法では，一つのファイル内に同じクローンれらの開始部分と終了部分が共通であり（完全一致ク

セットに含まれるコードクローンが三つ存在した場合，ローンもしくは名前変更クローンとなっており），中央

一番目と二番目をつないだコードクローンと二番目とのみが異なっているために，ある関数の終了部分から三番目をつないだコードクローンが一つのギャップを次の関数の開始部分までが一つのギャップを含むコー

含むクローンセットを構成し，それらは共に二番目のドクローンとして検出されていた．

コード片を含んでいるため，オーバーラップしている．

複数の関数にまたがるコードクローンの検出を防ぐには，各関数の開始位置および終了位置の情報を取得し，ギャップを含むコードクローンがそれを跨ぐかどうかを判定しなければならない．しかし，コードク

このようにして，オーバーラップしたコードクローンをもつクローンセットが多数検出された．
オーバーラップしたコードクローンの検出を防ぐ手
段は二つ考えられる．

ローン検出結果には対象ソースコードに含まれる関数

対策 1: ギャップを含むコードクローンを生成したの開始位置および終了位置の情報は含まれていないた

後，それらの位置からオーバーラップの判定を行う．

めに，ポストプロセッサ内で再度ソースコード解析を

ギャップを含むコードクローンを構成している完全一致

行わなければならない．

クローンおよび名前変更クローンの位置情報は，コー

ポストプロセッサでソースコード解析を行わない利点は，用いるコードクローン検出ツールが対応していドクローン検出ツールの出力結果から得られるため，
この処理は容易に行うことが可能である．

るプログラミング言語であれば，どの言語であっても対策 2: 提案手法の手順 2 において，同一クローン

ポストプロセッサを適用できることである．つまり，セットに含まれる頂点間には辺を引かないことにする．

ポストプロセッサ内でソースコード解析を行うことにこの処理も容易に行うことが可能である．

よって，「(1) 複数関数」に該当するクローンセットの対策 1 は，全てのオーバーラップしたコードクロー
7電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

ンの検出を抑える．それに対して，対策 2 は，開始複していれば，ギャップを含むコードクローンとして

コード片と終了コード片が異なるクローンセットに含検出可能である．

まれている場合は，ギャップを含むコードクローンとCP-Miner はギャップの大きさが一文もしくは二文

して出力を行う．このようなコードクローンは，巻きの場合のみギャップを含むコードクローンとして検出付きコードクローン [17] の一種であると考えられ，一可能である．CP-Miner が採用している CloSpan アル

概に検出する価値がないとはいえない．どちらの対策

ゴリズム自体は大きなギャップを含むサブシーケンスの方が有効であるかを調査するためには，更なる実験も検出可能であるが，そのような設定でギャップを含を行う必要がある．

むコードクローンの検出を行なうと，検出に必要な計

7. 3 「(3) 調査の必要がない」への対策

算量が膨大になってしまい，実規模ソフトウェアに対オーバーラップしたクローンセットと同様に，調査しては適用が難しい．それに対して提案手法では，小の必要がないクローンセットも全体の約 10%を占めてさなギャップも大きなギャップもグラフ上では同様にいた．本論文では，調査の必要がないコードクローン

扱われるため，大きなギャップを含むコードクローンとは，「 ソフトウェア開発・保守を行う視点でそれらも検出可能である．また，頻出パターンの検出の際にを扱う場合に特に対象とする必要が無いコードクロー

制限を設けることによって高速に検出を行なっているン」と定義しており，具体的には，連続した変数宣言

ため，実規模ソフトウェアに対しても適用可能である．

やメソッド呼出，switch 文の連続した case エントリな

最後に検出速度に関して比較する．CP-Miner はどの処理を行っているコードクローンである．著者らLinux カーネルから約 20 分でコードクローン検出をの過去の調査により，調査の必要がないコードクロー

行なうことができる [9]．一方，提案手法は，四つのンは，繰り返し構造をもつ傾向であることがわかって

ソフトウェアに対して数分から数十分で検出処理を行いる [12]．このようなコードクローンは，どのソフトなった．対象ソフトウェアの規模の違いを考慮するとウェアにも存在するため，或る程度検出されてしまう

CP-Miner の方が高速にコードクローン検出を行なっのは当然であるといえる．

ているといえるが，提案手法も実際に使うには問題のこのようなコードクローンを自動的に除去するためには，ソースコードの構造を調査しなければならない．例えば，どの部分が連続した変数の定義であるか，無い速度だと著者は考える．

8. ま と め

どの部分が switch 文の連続した case エントリである

本論文では，完全一致クローンと名前変更クロー

か，ということがわからなければこのようなコードク

ンのコードクローン情報からギャップを含むコードク

ローンの検出を抑えることはできない．しかし，コー

ローンの生成手法を提案した．提案手法は，コードク

ドクローン検出ツールの出力結果には，ソースコード

ローン検出ツールの出力結果のみを用いるため，コーの構造情報は含まれていないため，ポストプロセッサ

ドクローン検出対象ソースファイルを直接解析しない．

でソースコード解析を行う必要がある．7. 1 節でも述よって，利用するコードクローン検出ツールが対応しべたが，ポストプロセッサ内でソースコード解析を行ているプログラミング言語であれば，どの言語であっうことによって，「(1) 調査の必要がない」に該当するても適用することが可能である．

クローンセットの検出を防ぐことは可能であるが，検実際に提案手法を検出ツール CCFinder のポスト

出対象ソフトウェアのソースコード解析器を構築する

プロセッサとして実装し，どのようなギャップを含む

必要があり，適用にはより高いコストを必要とする．

コードクローン情報が生成されるのかを調査を行っ

7. 4 CP-Miner との比較た．C 言語あるいは Java 言語で記述された四つのソ提案手法では，ギャップの前後が Type1 クローンもフトウェアについて調査を行ったところ，生成結果のしくは Type2 クローンとして検出されなければ，そ

約 25%∼35%が有益なコードクローン情報であった．

の部分をギャップを含むコードクローンとして検出で残りのコードクローンは，なんらかの理由により，検きない．つまり，ギャップを含むコードクローンとし出する価値がないコードクローンであると思われた．

て検出されるためには，ギャップの前後にある程度以

また，これらの検出する価値がないと思われるコー

上の重複コードが存在していなければならない．それ

ドクローンの除去方法について考察した．今後は，考に対して，CP-Miner はギャップの前後が一文でも重察した除去方法の実装と，CCFinder 以外のコードク

8

論文／グラフマイニングアルゴリズムを用いたギャップを含むコードクローン情報の生成

ローン検出ツールを使ってギャップを含むコードクロー

national Symposium on Software Matrics, pp.67-76,
Jun 2002.

ン検出を行うことを予定している．
謝辞 本研究を行うにあたりご助力頂いた藤野陽平[12]

氏 (現 JR 東日本) に感謝する．本研究は一部，文部科学省「次世代 IT 基盤構築のための研究開発」（研[13]

究開発領域名：ソフトウェア構築状況の可視化技術

of 2003 SIAM International Conference on Data Min-の開発普及）の委託に基づいて行われた．また，日本学術振興会科学研究費補助金基盤研究 (A)(課題番

ing, pp.166-177, May 2003.
[14]

猪口明博，鷲尾隆，元田浩，“多頻度グラフマイニング手法の一般化，” 人工知能学会論文誌，vol.19，no.5，pp.368378，May 2004.

[15]

植田泰士，神谷年洋，楠本真二，井上克郎，“開発保守支援を目指したコードクローン分析環境，” 電子情報通信学
会論文誌，vol.86-D-I，no.12，pp.863-871，Dec. 2003.
“ctags,” http://ctags.sourceforge.net/.
R. Komondoor, and S. Horwitz, “Using Slicing to
Identify Duplication in Source Code,” Proc. of the

号:21240002)，および文部科学省科学研究費補助金基盤研究 (C)(課題番号:20500033) の助成を得た．
文
[1]

[2]

[3]

献

井上克郎，“エンピリカルソフトウェア工学の研究と実践―コードクローンを例に―，” EASE プロジェクトニュー
スレター，vol.4，pp.1-4，Dec. 2005.
I. Baxter, A. Yahin, L. Moura, M. Anna, and L. Bier,“Clone Detection Using Abstract Syntax Trees,”
Proc. of International Conference on Software Maintenance 98, pp.368-377, Mar. 1998.
T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder:

肥後芳樹，吉田則裕，楠本真二，井上克郎，“産学連携に基づいたコードクローン可視化手法の改良と実装，” 情報処理学会論文誌，vol.48，no.2，pp.811-822，Feb. 2007.
X. Yan, J. Han, and R. Afshar, “CloSpan: Mining
Closed Sequential Patterns in Large Datasets,” Proc.

[16]
[17]

8th International Symposium on Static Analysis,
pp.40-56, July 2001.

（平成 xx 年 xx 月 xx 日受付）

A Multilinguistic Token-Based Code Clone Detection
System for Large Scale Source Code,” IEEE Transactions on Software Engineering, vol.28, no.7, pp.654670, July 2002.
[4]

S. Uchida, A. Monden, N. Ohsugi, T. Kamiya, K. ichi
Matsumoto, and H. Kudo, “Software Analysis by
Code Clones in Open Source Software,” Journal ofComputer Information Systems, vol.XLV, no.3, pp.111, Apr. 2005.

[5]“Clone Detection Literature,” http://www.cis.uab.

[6]

edu/tairasr/clones/literature/.
肥後芳樹，楠本真二，井上克郎，“コードクローン検出と[7]

その関連技術，” 電子情報通信学会論文誌 D，vol.J91-D，no.6，pp.1465-1481，June 2008.
S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and
E. Merlo, “Comparison and Evaluation of Clone Detection Tools,” IEEE Transactions on Software Engi-

肥後 芳樹

（正員）

平 14 阪大・基礎工・情報中退．平 18
同大大学院博士後期課程修了，平成 19 阪
大・情報・コンピュータサイエンス・助教．
博士 (情報科学)．コードクローン分析・リ
ファクタリングに関する研究に従事．情報処理学会，IEEE 各会員．

宮崎 宏海
平 19 阪大・基礎工・情報卒．平 21 同大大学院博士前期課程修了．在学時，コー
ドクローンに関する研究に従事．

neering, vol.31, no.10, pp.804-818, Oct. 2007.
[8]

Y. Ueda, T. Kamiya, S. Kusumoto, and K. Inoue,“On Detection of Gapped Code Clones using Gap Locations,” Proc. of the 9th Asia-Pacific Software Engineering Conference, pp.327-336, Dec. 2002.

[9]

Z. Li, S. Lu, S. Myagmar, and Y. Zhou, “CP-Miner:
Finding Copy-Paste and Related Bugs in Large-Scale
Software Code,” IEEE Transactions on Software Engineering, vol.32, no.3, pp.176-192, Mar. 2006.

[10]

M. Balint, T. Girba, and R. Marinescu, “How Developers Copy,” Proc. of the 14th IEEE International Conference on Program Conprehension, pp.5668, June 2006.

[11]

Y. Ueda, T. Kamiya, S. Kusumoto, and K. Inoue,

楠本 真二

（正員）

昭 63 阪大・基礎工・情報卒．平 3 同大
学院博士課程中退．同年同大・基礎工・情報・助手．平 8 同大講師．平 11 同大助教
授．平 14 阪大・情報・コンピュータサイ
エンス・助教授．平 17 同学科教授．博士(工学)．ソフトウェアの生産性や品質の定量的評価，プロジェクト管理に関する研究に従事．情報処理学会，IEEE，JFPUG 各会員．

“Gemini: Maintenance Support Environment Basedon Code Clone Analysis,” Proc. of the 8th Inter-9電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

井上克郎 （正員：フェロー）

昭 54 阪大・基礎工・情報卒．昭 59 同大大学院博士課程了．同年同大・基礎工・情報・助手．昭 59〜昭 61 ハワイ大マノア
校・情報工学科・助教授．平 1 阪大・基礎
工・情報・講師．平 3 同学科・助教授．平 7
同学科・教授．博士 (工学)．平 14 阪大・情報・コンピュータサイエンス・教授．ソフトウェア工学の研究に従事．情報処理学会，日本ソフトウェア科学会，IEEE，ACM，
各会員．

10

Abstract At present, various kinds of code clone detection techniques have veen proposed. However,most of them cannot detect gapped code clones, which are ones that includes non-duplicated segments to its
correspondant code clones. In this paper, we propose a method generating gapped code clone informationfrom a detection result of existing code clone detection tools. The method adopts AGM (Apriori-baded
Graph Mining) algorithm to extract gapped code clone information eﬃciently. The method has alreadybeen implemented as a post-prosessor of CCFinder, which is a token-based code clone detection tool. We
applied the post-prosessor to four open source software systems, and got many interesting gapped code
clones. However, unattractive code clones have been generated too. In this paper, we describe the result of
the case study, and discuss the above problem.
Key words Code clone，Graph minging algorithm, Software maintenance