実規模ソフトウェアへの適用を目的としたプログラム依存グラフに基づくコードクローン検出法
肥 後 芳 樹†楠 本 真 二†

これまでにさまざまなコードクローン検出手法が提案されているが，全ての面において他の検出手法よりも優れているものはない．プログラム依存グラフを用いた検出の長所は非連続コードクローンを検出できることである．しかし，その反面，連続コードクローンについては，他の検出技術に比べて検出能力が低い．また，検出に必要な計算コストが高いため，実規模ソフトウェアに対しては適用が難しいという弱点もある．本論文では，実規模ソフトウェアに対して適用することを目的とした，プログラム依存グラフを用いたコードクローン検出手法を提案する．また，提案手法では，検出方法
そのものにも改良を行っており，既存の手法では検出できないコードクローンも検出可能である．提案した手法を複数のソフトウェアに対して適用し，その有効性を確認した．

Code Clone Detection with Program Dependency Graph for
Actual Software Systems
YOSHIKI H IGO† and S HINJI K USUMOTO†
At present, there are various kinds of code clone detection techniques. Each detection technique has merits and demerits, and none of them is superior to any other techniques in every way. PDG-based detection issuitable to detect non-continuous code clones meanwhile other detection techniques are not suited to detectthem. However, there is a tendency that it cannot detect continuous code clones unlike line-based or tokenbased techniques. Moreover, PDG-based detection is time-consuming, and it is difﬁcult to apply it to actual
software systems. This paper proposes a new PDG-based detection method, which can be applied to actual
software systems. Also, the proposed method improves a traditional detection algorithm, and it can detect
code clones that cannot be detected by existing PDG-based detection methods. We conﬁrmed the usefulnessof the proposed method by applying it to multiple real software systems.

1. は じ め にた場合でも検出結果はツール毎に異なる．
既存の検出手法は用いている技術により，行単位で近年，ソフトウェア工学の研究対象の 1 つとしてコーの検出，字句単位での検出，抽象構文木を用いた検出，

ドクローンが注目を集めており，これまでにコードクプログラム依存グラフを用いた検出，メトリクスを用ローンに関係するさまざまな研究がなされている1),10) ．

いた検出に大別される6) ．各検出技術は一長一短であコードクローンとは，ソースコード中に存在する同一り全ての面において他の技術よりも優れているものはまたは類似したコード片を表す．コードクローンは，ない4),5) ．コードクローン検出を行う状況に応じて，適コピーアンドペーストや定型処理などのさまざまな理

切な検出技術を選択することが重要である．

由によりソースコード中に作り込まれる3) ．

プログラム依存グラフ（Program Dependency Graph，

コードクローン検出ツールは，対象のソースコー

以降 PDG）を用いた検出の長所と短所を示す4),5),7),8) ．

ドを入力として受け取り，その中に含まれるコードク

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

ローンの位置情報を出力する．しかし，コードクロー

非連続コードクローンとは，1 つのコードクローンの厳密で普遍的な定義は存在せず，各手法が独自にンを構成する要素（プログラムの文や式など）がコードクローンの定義を持ち，その定義に基づいて検必ずしもソースコード上で連続していないコード出を行う．そのため同じソースコードから検出を行っクローンを指す．

† 大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka
University

短所 行単位，字句単位，および抽象構文木を用いた検出に比べると連続コードクローンの検出能力が劣る．また，検出に必要な計算コストが高いため，

実規模のソフトウェアに対しては適用が難しい．

は，同型部分グラフを探索するグラフが巨大であるか

本論文では、実規模ソフトウェアへの適用を目的とらである．このように手法ごとに高い計算コストが必した，計算コストを抑えた，PDG を用いたコードク

要な処理は異なる．用いる PDG に合わせて，適切なローン検出手法を提案する．また，提案手法は検出方計算コストを抑える工夫を行うことにより，PDG を用法そのものにも工夫を行っており，従来の PDG を用いた検出は実用的な手法になりうると著者らは考えた．

いた手法では検出できないコードクローンも検出可能である．

2. 関 連 研 究

3. プログラム依存グラフ
本節では，提案手法で用いる PDG の構築方法について述べる．提案手法では，まず制御フローグラフ

Komondoor らは初めて PDG を用いたコードクロー（Control Flow Graph, 以降 CFG）が構築され，それをン検出を行った7) ．彼らの手法では，ソースコード中の用いて PDG が構築される．以降，3.1 節と 3.2 節では文と条件式が PDG の頂点である．全ての頂点からハッそれぞれ，CFG と PDG の構築方法について説明する．

シュ値が算出され，ハッシュ値が等しい頂点が同じグ

3.1 制御フローグラフの構築

ループに分類される．グループ内の全ての頂点のペア

CFG はソースコードの表現方法の 1 つであり，プロから，それらを含む同型部分グラフが求められ，それグラムの開始から終了までの全ての実行経路を表す．

らがコードクローンとされる．同型部分グラフの特定

CFG はコンパイラ最適化やプログラム静的解析の分には主にバックワードスライスが用いられ，フォワー

野でしばしば用いられる．本論文では，CFG の頂点

ドスライスは，条件式の頂点が同型部分グラフに追加と辺は下記のとおりである．

された時のみ用いられる．文献 7) の実験では，PDG

頂点 文と条件節の式．例えば，図 1(a) では，文を用いた手法の高い検出能力が示されたが，約 11,000「System.out.println(i)」, 式「i < 10」,

行のソフトウェアからの検出に約 90 分を要するなど，「int i = 0」,「i++」が頂点となる．

その実用性の低さも顕著であった．

辺 要素 A の実行直後に要素 B が実行される可能性

Krinke は細粒度 PDG を用いたコードクローン検出がある場合，A の頂点から B の頂点へ辺を引く．

手法を提案している8) ．細粒度 PDG では，頂点は抽

本論文では，CFG は各メソッド（と各コンストラク

象構文木の頂点とほぼ 1 対 1 で対応しており，通常のタ）に対して作成される．CFG は，メソッド内の構造

PDG に比べて頂点数がはるかに多くなる．そのため，において，その内側から順に構築される．つまり，メ単純に検出処理を行った場合は，Komondoor らの手

ソッド内の最も深いブロック（ブロックとは，if 文や7)

法 に比べてさらに大きな計算コストを必要とする．

while 文などを表す）の CFG がまず構築され，それをこの問題に対処するため，Krinke は k-limited search

用いてその外側のブロックの CFG が構築される．内という手法を提案している．k-limited search では，同側のブロックの CFG を組み合わせてその外側のブロッ型部分グラフはスライス基点の k ホップ内でのみ探クの CFG を構築する処理は，外側のブロックがメソッ

索されるため計算コストを抑えることができる．しかドになるまで繰り返えされる．図 1(b) は図 1(a) に示

し，最も大きな同型部分グラフが特定されない可能性

すソースコードから構築される CFG を表している．

がある．Krinke の手法では，フォワードスライスが用

3.2 プログラム依存グラフの構築

いられており，計算コストを抑えるために，スライス

PDG は CFG を基にして，下記の方法で構築される．

基点となる頂点は条件式の頂点に限定されている．文

頂点の生成 1 つの CFG の頂点から 1 つの PDG の頂献 8) の実験では，k-limited search により計算コスト

点が生成される．つまり CFG と PDG の頂点数はを大幅に抑えれることが示された．k が 20 以下の場

完全に一致する．

合は，検出処理は数分以内で完了したが，k が 25 以

データ依存辺の生成 CFG において，変数を定義ま上の場合は，約 25,000 行のソフトウェアからの検出

たは変数に対して代入を行っている各頂点に対しに約 46 時間を要するなど，大きなコードクローンをて，その変数を参照している頂点を制御フローを検出するには，高い計算コストが必要であった．

たどりながら検出する．そして，PDG において，Komondoor らの手法7) が高い計算コストを必要とす
るのは，ハッシュ値の等しい頂点の全ての組み合わせ

定義している頂点から参照している頂点に向けて
データ依存辺を引く．

について同型部分グラフの検出を行っているからであ

制御依存辺の生成 条件式を表す頂点から，ソース

り，Krinke の手法8) が高い計算コストを必要とするのコード上においてその内部に存在するプログラム要素の頂点に対して制御依存辺を引く．

1: void sample(){2:for ( int i = 0 ; i < 10 ; i++ ) {3:
System.out.println(i);
4:
}
5: }
(a) ソースコード

図 1(c) は図 1(b) の CFG から構築される PDG である．

4. PDG を用いたコードクローン検出法
本節では，3 節で述べた PDG を用いてコードクロー
ンを検出する手法を提案する．提案手法は以下の 4 つ

i < 10 <2>

int i = 0; <2>の STEP からなる．

STEP1 PDG の全ての頂点のハッシュ値を求め，ハッjava.lang.System.out.println(i); <3>

シュ値が同じ頂点毎にグループを作成する．ハッシュは頂点が表すプログラム要素の構造に基づいて計算される．ハッシュ値が計算される前に，変i++ <2>数やリテラルはその型に変換されるため，利用している変数やリテラルが異なっていても，それら(b) 制御フローグラフの型が同じであり，そのプログラム要素の構造がcontrol dependency
data dependency
int i = 0; <2>

等しければ，それらは同じハッシュ値を持つ．

STEP2 同じグループに属する頂点のペア (r1,r2) を

i++ <2>含む同型部分グラフを検出する．同型部分グラフの検出にはフォワードスライスとバックワードス
i < 10 <2>

ライス11) の 2 つを用いる．スライス基点は r1 と

r2 であり，2 つのスライシングは同期して行われる．スライシングにより新たにたどった頂点の

java.lang.System.out.println(i); <3>

ハッシュ値が等しい場合はそれらを同型部分グラ
フの頂点として加える．スライシングが下記条件(c) プログラム依存グラフのいずれかを満たすとき，たどった頂点は同型部

図1

制御フローグラフとプログラム依存グラフの例

分グラフに加えられず，スライシングを終了する．

• 新たにたどった頂点のペア (p1, p2) が異なる

STEP4 同じグラフを持つクローンペアからクローン

ハッシュ値を持つ場合．

セットを形成する．例えば，2 つのクローンペア• (p1, p2) のハッシュ値は等しいが，r1 のグラ(s1, s2), (s2, s3) があった場合，クローンセット

フ（または r2 のグラフ）がすでに p1（または p2）を含んでいる場合（無限ループを回避{s1, s2, s3} が形成される.
4.1 フォワードスライスとバックワードスライスのするための処理）．

両方をコードクローン検出に用いる理由• (p1, p2) のハッシュ値は等しいが，r1 のグラ

2 節で紹介した先行研究は，フォワードスライスとフ（または r2 のグラフ）が p2（または p1）

バックワードスライスのどちらか 1 つしか用いていなを含んでいる場合（2 つの同型部分グラフがいのに対して，提案手法では両方を用いる．その理由

頂点を共有するの回避するための処理）．

は，バックワードスライスを用いて検出される一部のこの処理を同じグループに属する全ての頂点のペ同型部分グラフはフォワードスライスでは検出されず，アに対して行う．スライシング終了後に特定されまたその逆もあるからである．

ているグラフのペア（2 つの同型部分グラフ）が

図 2 と図 3 では，++で始まる 3 行と--で始まる 3 行

本手法において検出されるクローンペアである．

がクローンペアである．図 2 では，各同型部分グラフ

STEP3 クローンペア (s1, s2) が他のクローンペア

において 1 つの変数が 2 つの文で参照されている．そ(s1 , s2 ) に含まれている場合（s1 ⊆ s1 ∩ s2 ⊆のため，1 つの頂点から 2 つの頂点に向けてデータ依存

s2 ）, そのクローンペアを検出されたクローンペ

辺が存在する．例えば，コードクローン<1,3,5>☆ でアの集合から削除する．他のクローンペアに包含は，文<1> → 文<3>と文<1> → 文<5>の 2 つのデーされたクローンペアをユーザに対して提示する理

タ依存辺が存在する．この例のような場合，どの頂点由はなく，またこれらの存在は検出結果を肥大化させてしまうからである．

☆

1，3，5 行目のプログラム要素からなるコードクローン

++int b = a + 5; <3>

int c = a * 10; <5>

int d = 3; <11>

int e = d + 5; <13>

int f = d * 10; <15>++(a) ソースコード(b) プログラム依存グラフ

バックワードスライスでは特定できない同型部分グラフの例

図3

data depencency
int a = 2; <1>short b = 3; <3>

int c = a * b; <5>

int d = 4; <11>short e = 5; <13>

int f = d * e; <15>…

1: int a = 2;:++ 3: short b = 3;:++ 5: int c = a * b;::-- 11: int d = 4;:-- 13: short e = 5;:-- 15: int f = d + e;
:

…

図2

int a = 0; <1>…

(a) ソースコード

data depencency…

1: int a = 1;:++ 3: int b = a + 5;:++ 5: int c = a * 10;::-- 11: int d = 3;:-- 13: int e = d + 5;:-- 15: int f = d * 10;:(b) プログラム依存グラフ

フォワードスライスでは特定できない同型部分グラフの例

をスライス基点としてもバックワードスライスでは 3と return b;），それらがコピーアンドペーストにつの頂点からなる同型部分グラフを特定できないが，より生成されたわけではない．そこで，本論文では，フォワードスライスを用いることにより特定できる．

同じハッシュ値を持つ頂点数の閾値を設け，その閾値

図 3 では，各同型部分グラフにおいて，2 つの変数よりも多くの数の頂点数が同じハッシュ値を持つ場合

が 1 つの文で参照されている．そのため，2 つの頂点から，1 つの頂点に向けてデータ依存辺が存在する．例えば，コードクローン<1,3,5>では，文<1> → 文<5>は，それらはスライス基点としては用いない．

5. 適 用 実 験と文<3> → 文<5>の 2 つのデータ依存辺が存在する．

提案手法を Java 言語を用いて実装し2) ，適用実験を

この例のような場合，どの頂点をスライス基点として行った．この実験では，さまざまな規模のソフトウェ

もフォワードスライスでは 3 つの頂点からなる同型部

アを対象とした (表 1 参照)．この表では，「行数」は分グラフを特定できないが，バックワードスライスを空白行やコメント行を含んだ総行数，「頂点数」は実用いることにより特定できる．このように 2 つのスラ装したツールにおいて生成された PDG の頂点数を表

イスを用いることで，1 つのスライスでは特定できな

す．
「前処理時間」は，4 節の STEP1 を行うまでに必要い同型部分グラフを特定できるようになる．

な全ての処理，つまり，ソースコードの読み込み，意

4.2 計算コストの削減

味解析，そして PDG の構築に要した合計時間を表す．

PDG を用いたコードクローン検出の計算コストが高

また，この実験では，計算コスト削減手法の閾値としいのは 2 つの理由が考えられる．1 つ目の理由は，スて 50,100,200,300,500,1000 の 6 つを用い，5 つ以上のライス基点として使用される頂点のペア数が非常に多プログラム要素からなるコードクローンを検出した．

いことである．2 つ目の理由は，同型の部分グラフを

5.1 両方のスライスを用いた効果

特定することそのものが，NP 完全な，難しい問題でどちらか一方のスライスを用いた場合に検出されるあるためである．本論文では，理由 1 の側面から計算

コードクローンが，両方のスライスを用いて検出されコストを削減する手法を提案する．その理由は，理由

るコードクローンに対して，どの程度の網羅率がある

2 を改善することは容易ではなく，また，本論文で用のかを下記の式を用いて調査した．

いる PDG はメソッド単位で作成されるため，あまり

coverage(r1, r2) = 100×に巨大なグラフが作成されることはないためである．
検出処理の STEP2 において，n 個の頂点が同じハッ| S(r1) ∩ S(r2) |(1)| S(r1) |なお，各変数は下記のとおりとする．

シュ値を持つ場合，それらのペアをスライス基点とす

r1: 両方のスライスを用いた場合の検出結果

る組み合わせの数は n(n − 1)/2 となる．実規模ソフト

r2: どちらか一方のスライスを用いた場合の検出結果

ウェアの場合，同じハッシュ値を持つ頂点の数は，数千

S(r): 検出結果 r に含まれるプログラムの要素

あるいはそれ以上になる場合があり，全ての組み合わ調査結果を表 2 に示す．なお，JDK において閾値なせに対して同型部分グラフを特定する処理は非常に高しの場合は，両方のスライスを用いた検出処理が一晩い計算コストを必要とする．しかし，数千もの頂点がでは終了しなかったため，途中で処理を中断した．

同じハッシュ値を持つ理由は，それらがプログラムで

閾値 50 の場合では，網羅率は約 37% ∼ 61% と低く，頻繁に表れる処理であるからであり（例えば，変数宣両方のスライスを用いることにより，コードクローン

言 int i; と int j; や，リターン文 return a;として検出されるプログラム要素数が約 2 倍になっ

表1

ソフトウェア
XDocletFreeMind
JHotDraw
Ant
Tomcat
JDK

表2

ソフトウェア

XDocletFreeMind
JHotDraw
Ant
Tomcat
JDK

バージョン
1.2.3
8.1.0
7.1
1.7.1
6.0.181.6.0 13

対象ソフトウェア

行数
14,92738,52278,528
188,570
308,176
2,023,518

ファイル数
58
197
411
787
1,053
7,154

頂点数
3,936
13,726
29,504
52,333
94,234
518,710

前処理時間 (秒)
5.02
12.41
27.10
39.82
65.48
458.291 つのスライスを用いた検出結果の，2 つのスライスを用いた検出結果に対する網羅率用いたスライスフォワード
バックワードフォワード
バックワードフォワード
バックワードフォワード
バックワードフォワード
バックワードフォワード
バックワード閾値 50
48.34 %
55.51 %
40.78 %
55.74 %
61.50 %
50.55 %
45.61 %
51.01 %
47.32 %
53.18 %
37.19 %
51.86 %

2 つのスライスを用いた検出結果に対する網羅率
閾値 100閾値 200閾値 300閾値 500閾値 1,000
62.12 %
62.12 %
62.12 %
62.12 %
78.20 %
56.66 %
56.66 %
56.66 %
56.66 %
56.60 %
42.83 %
48.84 %
48.84 %
48.84 %
48.84 %
54.18 %
55.48 %
55.48 %
55.48 %
55.48 %
63.04 %
64.88 %
65.51 %
65.51 %
65.52 %
53.57 %
57.45 %
57.61 %
57.61 %
57.62 %
49.04 %
53.95 %
54.10 %
55.44 %
64.60 %
53.32 %
54.31 %
55.22 %
55.78 %
60.96 %
53.12 %
55.54 %
57.12 %
58.54 %
58.96 %
53.91 %
55.08 %
55.89 %
56.63 %
59.04 %
39.69 %
42.35 %
43.74 %
46.72 %
47.63 %
54.85 %
56.77 %
57.42 %
58.27 %
60.57 %

閾値なし
78.29 %
56.60 %
68.90 %
55.45 %
78.96 %
57.62 %
77.92 %
61.19 %
82.17 %
62.41 %-ていることがわかる．閾値が上がるにつれて網羅率もイスを用いることにより同型グラフの探索範囲が増加

上昇するが，閾値なしの場合でも網羅率は約 55% ∼したため，また，(2) それにより検出されるクローン

82%に留まっている．

ペアの数が増え，STEP3 （不必要なクローンペアの除閾値が低い場合に網羅率が低くなるのは，次の理由からである．例えば，バックワードスライスしか用いない場合は，PDG を逆順にたどることしかできないた去）および STEP4（クローンセットの形成）により多くの時間が必要になったため，である．

5.2 計算コスト削減手法の効果

め，逆順のみで同型部分グラフ上の全ての頂点をたど

計算コスト削減手法の効果について調査を行った．

ることができる頂点がスライス基点になっていない場

この調査では全てのコードクローン検出は両方のスラ

合は，網羅率は低くなってしまう．閾値を用いること

イスを用いて行った．表 4 は各閾値における，スライ

により，このような「すべての頂点を 1 つのスライスス基点として使用された頂点のペア数（括弧内の数値

のみでたどれる頂点」がスライス基点から除かれてしは閾値なしの場合に対する割合）を表している．このまい，網羅率が低くなってしまったと考えられる．ま表より，閾値なしの場合は，膨大な数のペアがスライた，閾値なしの場合でも網羅率が 100%になっていなス基点として使用されたことがわかる．閾値を用いる

いのは，4.1 節で紹介したような，そもそも 1 つのスラことにより，スライス基点になるペア数が閾値なしのイスのみでは完全に特定できない同型部分グラフが存場合に比べて，かなり削減されている．削減率は規模在したためである．閾値なしの場合の網羅率が約 55%の大きいソフトウェアほど大きく，例えば，JDK の閾∼ 82%ということは，残りの 18% ∼ 45%はそのよう

値 50 の場合は，閾値なしの場合に比べて約 0.01%のな同型部分グラフの頂点であったことを示している．

ペアのみがスライス基点として用いられている．このまた，表 3 は各スライスを用いた場合の検出時間を表している．ここでの検出時間は，4 節で説明した

頂点数の削減の効果が，表 3 において，検出時間の短縮というかたちで現れている．

STEP1 ∼ STEP4，つまり PDG 頂点のハッシュ値の計

次に，閾値を用いた場合に検出されるコードクロー

算から，クローンセットの検出までに要した時間であンは，閾値を用いない場合に対してどの程度の網羅率

る．表 3 より，両方のスライスを用いた場合は，1 つがあるのかを，式 (1) を用いて調査した．この調査でのスライスを用いた場合に比べて多くの時間を必要とは各変数は以下のものを用いた．

していることがわかる．この原因は，(1) 両方のスラ

r1: 閾値を用いない場合の検出結果

表 3 各スライスを用いた検出時間

ソフトウェア

用いたスライス
両方
フォワード
バックワード両方
フォワード
バックワード両方
フォワード
バックワード両方
フォワード
バックワード両方
フォワード
バックワード両方
フォワード
バックワードXDocletFreeMind

JHotDraw

Ant

Tomcat

JDK

表4

ソフトウェア

XDocletFreeMind
JHotDraw
Ant
Tomcat
JDK

閾値 50
1.04
0.39
0.33
1.97
1.05
0.57
22.39
2.10
1.43
8.39
2.68
3.02
31.50
5.68
5.52
1910.55
47.55
47.88

閾値 100
1.55
0.55
0.48
3.25
1.63
0.82
23.03
9.50
4.48
7.35
4.88
2.99
65.52
12.04
6.13
6288.34
189.5575.02

閾値 200
1.55
0.58
0.48
4.80
2.21
0.97
43.97
10.01
10.14
12.92
8.52
4.92
180.9014.64
9.44
9209.92
192.67102.45検出時間（秒）閾値 300閾値 500
1.56
1.54
0.62
0.55
0.50
0.51
4.75
4.56
1.91
1.78
1.03
1.41
158.85160.03
11.71
12.80
10.69
12.38
20.37
20.05
9.98
9.35
6.24
7.26
193.23213.71
14.87
21.96
9.16
16.81
9207.60
9496.63
219.37268.36105.42131.37

閾値 1,000
3.53
2.97
0.46
4.78
2.19
1.43
161.61
11.49
10.69
61.80
35.32
16.35
255.8326.89
26.30
9681.43325.11155.52

閾値なし
3.49
2.93
0.47
29.41
26.83
4.05
293.70144.3924.41
336.82312.9447.32
1407.271083.77146.06-

スライス基点として使用される頂点数（括弧内の数値は閾値なしの場合に対する割合）

閾値 50
12,878(5.03 %)
24,483(0.67 %)
80,140(0.53 %)
111,655(0.31 %)
200,853(0.17 %)
982,448(0.01 %)

スライス基点として使用される頂点数
閾値 200閾値 300閾値 500閾値 1,000
25,79525,79525,795
255,976(10.07 %)(10.07 %)(10.07 %)(100.00 %)130,150130,150130,150130,150(3.60 %)
(3.60 %)
(3.60 %)
(3.60 %)
298,116
371,290371,290371,290(1.99 %)
(2.48 %)
(2.48 %)
(2.48 %)
427,300
716,265
998,170
2,932,741(1.19 %)
(2.00 %)
(2.79 %)
(8.21 %)
619,853994,548
1,419,842
4,462,410(0.54 %)
(0.87 %)
(1.25 %)
(3.93 %)
3,963,608
4,991,945 8,408,394
14,108,189(0.07 %)
(0.09 %)
(0.15 %)
(0.25 %)

閾値 10025,795(10.07 %)61,684(1.70 %)
133,343(0.89 %)
205,290(0.57 %)
364,189(0.32 %)
2,106,308(0.03 %)

表5

ソフトウェア

XDocletFreeMind
JHotDraw
Ant
Tomcat閾値 50
98.01 %
91.17 %
96.37 %
91.48 %
90.60 %

閾値なし
255,976
3,610,991
14,916,211
35,699,966
113,311,371
5,543,539,373-

閾値なしの検出結果に対する網羅率

閾値なしの検出結果に対する網羅率
閾値 100閾値 200閾値 300閾値 50099.90 %
99.90 %
99.90 %
99.90 %
97.63 %
99.94 %
99.94 %
99.94 %
99.63 %
99.89 %
99.97 %
99.97 %
94.59 %
97.71 %
98.50 %
99.04 %
94.92 %
96.54 %
97.63 %
98.94 %

r2: 閾値を用いた場合の検出結果
S(r): 検出結果 r に含まれるプログラムの要素

閾値 1,000
100.00 %99.94 %
99.97 %
99.88 %
99.35 %

慮すると，この網羅率の値は非常に高いといえる．

5.3 他の手法との比較

表 5 は，各ソフトウェアと各閾値における網羅率を

既存の実用的な検出手法と比較して，どの程度検まとめたものである．閾値を用いた場合，最低でも約出されるコードクローンに違いがあるのかを調査し90%のプログラム要素がコードクローンとして検出さた．比較対象として，字句単位の検出ツールである

れていることがわかる．閾値を用いた場合のスライス

CCFinder を選択した．その理由は，(1)CCFinder は

基点数が用いなかった場合の高々数%だったことを考広く用いられているツールであること，(2) 実用性の

表6

ソフトウェア

XDocletFreeMind
JHotDraw
Ant
Tomcat
JDK

網羅率
C1
C2
C1
C2
C1
C2
C1
C2
C1
C2
C1
C2

ツール間における検出されるコードクローンの違い（網羅率 C1 と C2）

閾値 50
36.07 %
38.58 %
40.80 %
18.80 %
70.45 %
44.25 %
46.12 %
32.28 %
55.68 %
36.38 %
53.42 %
33.30 %

閾値 10035.46 %
38.71 %
41.56 %
20.23 %
71.19 %
46.17 %
45.36 %
32.69 %
55.93 %
38.35 %
53.56 %
35.54 %

閾値 20035.46 %
38.71 %
42.11 %
21.04 %
71.12 %
46.22 %
44.51 %
33.09 %
55.70 %
38.80 %
53.86 %
37.19 %

高いツールであり，この実験対象全てのソフトウェア

閾値 30035.46 %
38.71 %
42.11 %
21.04 %
71.07 %
46.22 %
44.48 %
33.36 %
55.55 %
39.11 %
53.73 %
37.27 %

閾値 50035.46 %
38.71 %
42.11 %
21.04 %
71.07 %
46.22 %
44.37 %
33.41 %
55.28 %
39.35 %
53.37 %
37.38 %

閾値 1,000
35.46 %
38.71 %
42.11 %
21.04 %
71.07 %
46.22 %
44.17 %
33.42 %
55.10 %
39.37 %
53.10 %
37.55 %

閾値なし
35.46 %
38.71 %
42.11 %
21.04 %
71.03 %
46.22 %
44.14 %
33.42 %
54.89 %
39.40 %-とを表している．一方，CCFinder の検出したコードを解析可能であること，の 2 つである．なお，この調クローンのうちの約 17% ∼ 38%が提案手法によって査では，CCFinder を用いて 30 字句以上のコードクも検出されているのがわかる．つまり，CCFinder のローンを検出した．紙面の都合上 CCFinder の実行時検出した 62% ∼ 83%は提案手法は検出できていない．

間の詳細については割愛するが，いずれのソフトウェ

提案手法と CCFinder はそれぞれ，他方が検出できなアに対しても提案手法よりも短時間でコードクローン

いコードクローンをある程度検出できている．

を検出した．なお，この調査でも，提案手法では両方

5.4 検出されたコードクローンの例のスライスを用いてコードクローン検出を行った．

検出されたコードクローンを 1 つ紹介する．図 5 は

CCFinder の検出できなかったコードクローンを提JHotDraw から検出されたコードクローンである．++

案手法がどの程度検出できたのかを調査するため，式で始まる行はコードクローンに含まれるプログラム要(1) と下記の変数を用いて網羅率 C1 を算出した．

素である．このクローンセットは，5 個のコードクロー

r1: 提案手法の検出結果ンからなり，全てが異なるクラスに存在していた．こ

r2: CCFinder の検出結果のコードクローンは，新しいフレーム（JFrame）を作

S(r): 検出結果 r に含まれるプログラムの行☆ ．

成，サイズや内部コンポーネントの設定，そして，表C1 の値が低いほど，提案手法は CCFinder が検出で示を行うという処理から成る．

きなかったコードクローンを検出できたこと意味する．

今後，同様の処理を実装する必要がある場合に，こまた，提案手法が検出できなかったコードクローンのコードクローンを参考にすることで，素早く実装ををどの程度 CCFinder が検出できたのかを調査するた

完了することができる．また，すでに 5 つ重複していめ，下記の変数を用いて網羅率 C2 を算出した．

るため，Template Method パターンなどを用いて，重r1: CCFinder の検出結果
r2: 提案手法の検出結果

複コードを共通化することも考えられる．
図 5 は，図 4(a) のコードクローンの PDG を表してS(r): 検出結果 r に含まれるプログラムの行．

いる．この図の頂点の識別子は，図 4(a) のプログラム

C2 の値が低いほど，CCFinder は提案手法が検出でき要素の識別子と対応している．このコードクローンはなかったコードクローンを検出できたことを意味する．

逐次処理のみから成るため，制御依存辺は存在しない．

表 6 は，網羅率 C1 と C2 の値をまとめたものであ

図 5 からわかるように，このコードクローンは，1 つる．この表より，提案手法が検出したコードクローン

スライスのみを用いた場合には，どの頂点をスライスのうちの約 37% ∼ 70%が CCFinder によっても検出さ基点とした場合でも他の全ての頂点をたどることはでれているのがわかる．つまり，残りの約 30% ∼ 63%はきない．つまり，これは両方のスライスを用いること提案手法よってのみ検出されたコードクローンであり，

によってはじめて検出されるコードクローンである．

提案手法を用いたコードクローン検出の価値があるこ☆

提案手法と CCFinder では検出されるコードクローンの単位が異なるため，直接比較することはできない．そのため，検出されたコードクローンが位置する行を用いて網羅率を計算した．

6. お わ り に
本論文では，PDG を用いたコードクローン検出手法を提案した．また提案手法を実装したツールを用い

cf.setStartConnector(ta.findConnector(
Geom.center(ta.getBounds()),cf));
cf.setEndConnector(tb.findConnector(
Geom.center(tb.getBounds()),cf));
a ++
b ++
c ++
d ++

Drawing drawing = new DefaultDrawing();:
JFrame f = new JFrame("My Drawing");f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setSize(400,300);

e ++
f ++
g ++

DrawingView view = new DefaultDrawingView();view.setDrawing(drawing);
f.getContentPane().add(view.getComponent());

i ++f.show();
:

++
++
++

:
Drawing drawing = new DefaultDrawing();:
JFrame f = new JFrame("UltraMini");f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setSize(600,300);

++
++
++

DrawingView view = new DefaultDrawingView();view.setDrawing(drawing);
f.getContentPane().add(view.getComponent());++

DrawingEditor editor = new DefaultDrawingEditor();editor.add(view);
editor.setTool(new SelectionTool());++(b) コードクローン 2(a) コードクローン 1
図4

JHotDraw から検出されたコードクローンĚĂƚĂĚĞƉĞŶĚĞŶĐǇ

Ă

Ğ

Ĩ

Ő

図5

ď
Đ

ŝ

Ě

図 4(a) のコードクローンの PDGてオープンソースソフトウェアに対して実験を行った．
実験により，提案手法の実規模ソフトウェアに対する有用性を確認することができた．
現在は，メソッド単位の PDG を用いてコードクロー
ンを検出しているが，今後は対象システム全体の PDG
からの検出を行う予定である．これにより，複数のメ
ソッドにまたがる処理を 1 つのコードクローンとして検出することが可能となり，より有益で興味深いコー
ドクローンの検出が見込まれる．また，複数のソフトウェア間でのコードクローン検出も予定している．著者らが知るかぎり PDG を用いてソフトウェア間のコー
ドクローンを検出している研究はない．Simone らは7,000 以上のシステムからコードクローンを検出し，検出されたコードクローンの分析を行っているが，彼らは字句単位でのコードクローンを検出しているため，非連続コードクローンは分析の対象外であった9) ．シ
ステム間の非連続コードクローンを検出し，分析することで新たな発見があると期待している．
謝辞 本研究は一部，文部科学省「次世代 IT 基盤構築のための研究開発」（研究開発領域名：ソフトウェ
ア構築状況の可視化技術の開発普及）の委託に基づいて行われた．また，文部科学省科学研究費補助金基盤
研究 (C)(課題番号:20500033) の助成を得た．

参

考

文

f.show();:

献1) : Clone Detection Literature, http://www.
cis.uab.edu/tairasr/clones/literature/.

2) : Scorpio, http://www-sdl.ist.osaka-u.
ac.jp/∼higo/cgi-bin/moin.cgi/scorpio-e/.
3) Baxter, I., Yahin, A., Moura, L., Anna, M. andBier, L.: Clone Detection Using Abstract Syntax
Trees, Proc. of International Conference on Software Maintenance 98, pp. 368–377 (1998).
4) Bellon, S., Koschke, R., Antoniol, G., Krinke, J.
and Merlo, E.: Comparison and Evaluation of Clone
Detection Tools, IEEE Transactions on Software Engineering, Vol. 31, No. 10, pp. 804–818 (2007).
5) Burd, E. and Bailey, J.: Evaluating Clone Detection Tools for Use during Preventative Maintenance,
Proc. of the 2nd IEEE International Workshop on
Source Code Analysis and Manipulation, pp. 36–43(2002).
6) 肥後芳樹, 楠本真二, 井上克郎: コードクローン
検出とその関連技術, 電子情報通信学会論文誌 D,
Vol. J91-D, No. 6, pp. 1465–1481 (2008).
7) Komondoor, R. and Horwitz, S.: SemanticsPreserving Procedure Extraction, Proc. of the 27th
ACM SIGPLAN-SIGACT on Principles of Programming Languages, pp. 155–169 (2000).
8) Krinke, J.: Identifying Similar Code with Program
Dependence Graphs, Proc. of the 8th Working Conference on Reverse Engineering, pp.301–309 (2001).
9) Livieri, S., Higo, Y., Matsushita, M. and Inoue, K.:
Very-Large Scale Code Clone Analysis and Visualization of Open Source Program Using Distributed
CCFinder: D-CCFinder, Proc. of the 29th International Conference on Software Engineering, pp.106–
115 (2007).
10) Roy, C. K. and Cordy, J. R.: A Survey on Software
Clone Detection Research, Technical report, Schoolof Computing, Queen’s University (2007).
11) 下村隆夫: プログラムスライシング技術と応用,
共立出版 (1995).