コードクローン検出に必要な計算コストの削減を目的としたプログラム依存グラフ頂点集約法の提案
肥 後

芳

樹†

楠 本

真

二†

プログラム依存グラフを用いたコードクローン検出手法の長所は，非連続コードクローンを検出できる点である．しかし，連続コードクローンの検出能力は，行単位での検出や字句単位での検出など，他の検出技術に比べて劣っている．また，コードクローンの検出に高い計算コストを必要とし，実規
模ソフトウェアについては，適用が難しいという問題点もある．前者の問題については，著者らは，プログラム依存グラフに実行依存という新しい依存関係を導入し，実験により連続コードクローンの検出能力が向上していることを確認した．本論文では，後者の問題点を改善するために，実行依存つきプログラム依存グラフに対して頂点の集約を行う手法を提案する．提案手法を用いることにより，プログラム依存グラフの規模が小さくなるため，検出に必要な計算コストを抑えることができる．

Merging Nodes on Program Dependency Graphfor Reducing Computational Cost of Code Clone Detection
YOSHIKI H IGO† and S HINJI K USUMOTO†
The advantage of PDG-based code clone detection is that it has a good capability to detect non-contiguous
code clones meanwhile it is less suited to detect contiguous code clones than other detection techniques likeline-based or token-based. Also, it is unrealistic to apply it to practical size software because it requires highcomputational cost for detection. In order to resolve the former problem, the authors previously proposed to
add a new dependencey, execution dependency into PDG. We confirmed that the introduction of execution
dependency improved the detection capability by several case studies. The present paper focuses on the latter problem. We propose a method merging multiple nodes as a single node on PDGs. The merging reduces
the scale of PDGs, so that less compurational cost is required for detection.

ルを用いた自動的な検出が行なわれる8) ．

1. は じ め に

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

コードクローンとはソースコード中に存在する同一ドを入力として受け取り，その中に含まれるコードク

または類似したコード片を表す．コードクローンはコローンの位置情報を出力する．しかし，コードクロー

ピーアンドペーストや定型処理，プログラミング言語

ンの厳密で普遍的な定義は存在せず，各手法が独自にの制限などの理由によりソースコード中に作り込まれコードクローンの定義を持ち，その定義に基づいて検る3) ． 例えば，Kim らは，開発者は 1 時間あたり約 4出を行なう．そのため同じソースコードから検出を行

回のコード片単位でのコピーアンドペーストを行なっなった場合でも検出結果はツール毎に異なる．

11)ていると報告している ．

既存の検出手法は用いている技術により，行単位で近年，ソフトウェア開発や保守を支援するためにコーの検出，字句単位での検出，抽象構文木を用いた検出，

ドクローン情報を利用することが注目されており，こプログラム依存グラフを用いた検出，メトリクスを用

1),8),15)．

いた検出に大別される8) ．各検出技術は一長一短であしかし，コードクローンをソースコード中から手作

り，全ての面において他の検出技術よりも優れている業で見つけること，また見つけたコードクローンをドものはない4),5) ．コードクローン検出を行なう状況にキュメント等を用いて管理することは現実的ではない．

応じて，適切な検出技術を選択することが重要である．

そのため，コードクローン情報が必要な場合に，ツープログラム依存グラフを用いた検出の長所は，他のれまでにさまざまな利用方法が提案されている† 大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka
University

検出技術では検出することが難しい非連続コードク
ローンを検出できることである4),5),12),13) ．非連続コー
ドクローンとは，1 つのコードクローンを構成する要素（プログラムの文や式など）が必ずしもソースコー
ド上で連続していないコードクローンを指す．しかし，その一方で連続コードクローンの検出能力に関しては，他の検出技術に劣る．この問題を解決するために，著者らは，プログラム依存グラフに実行依存という新しい依存関係を導入することにより，連続コードクロー
ンの検出能力を高めた手法を提案した10) ．
また，プログラム依存グラフを用いた検出には，計算コストが高く実規模ソフトウェアに対しては適用が難しいという短所もある．本論文では，この問題を改善するための手法として，プログラム依存グラフにおいて，頂点を集約する方法を提案する．この提案手法
では，実行依存において到達可能な複数の頂点を 1 つ

1: String sample1(){2:
if(this.trueOrFalse()){
3:
if(null == this.getPath()){
4:
Project proj = this.getProject();
5:
this.setPath(proj.getBaseDir());
6:}
7:StringBuilder text = new StringBuilder();8:
text.append("String A");9:
text.append("String B");10:
text.append("String C");11:
text.append("String D");
12:
return text.toString();
13:}else{
14:
return "";
15:
}
16: }
(a) ソースコードに集約するため，実行依存をたどることによる計算コ<1>ストの増加を抑えることができる．また，頂点数が減るため，集約した頂点を基点とするプログラムスライ<2>

シングを行なう回数が減り，計算コストが削減できる．

2. 準

<3>

備

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

<14>

<4>

<5>

以降 PDG）とは，プログラム内の要素（文）の間に存<7>

在する依存関係を表す有向グラフである．PDG の頂
点はプログラムの要素であり，辺で結ばれた頂点に依<8>存関係があることを表す．以下に，PDG の 2 つの依<9>

存関係について説明する．
データ依存 文 s で変数 v を定義し，文 t で変数 v を<10>

参照しており，文 s から文 t への経路のうち，変<11>

数 v を再定義しないものがある場合，文 s から文

制御依存
データ依存

t にデータ依存があるという．

<12>

制御依存 文 s が条件文または繰り返し文の条件式で(b) PDGあり，文 s の条件判定の結果によって文 t を実行するか否かが直接決まる場合，文 s から文 t への

図1

ソースコードと PDG の例

制御依存関係があるという．
図 1 は，簡単な PDG の例を表している．if 文の条

数やリテラルはその型に変換されるため，利用し件式からその内部に存在している文へ制御依存があり，ている変数やリテラルが異なっていても，それら

また text などの変数の定義・参照を行なっている文のの型が同じであれば，同じハッシュ値を持つ．

間にはデータ依存があるのがわかる．以降，本論文でSTEP2 プログラムスライシングを行い，同型部分グ

は，説明のための PDG としてこの例を用いる．

ラフを検出する．スライス基点は，同じグループ

2.2 PDG を用いたコードクローン検出手順に属する頂点のペア (r1, r2) であり，2 つのスライ

PDG を用いたコードクローン検出手順7) のうち，本シングは同期して行なわれる．スライシングによ論文で関連する STEP1 と STEP2 について記述する．

り新たにたどった頂点のハッシュ値が等しい場合

STEP1 PDG の全ての頂点のハッシュ値を求め，ハッはそれらを同型部分グラフの頂点として加える．

シュ値が同じ頂点毎にグループを作成する．ハッスライシングが下記条件のいずれかを満たすとき，

シュは頂点が表すプログラム要素の構造に基づい新たにたどった頂点のペア (p1, p2) は同型部分グて計算される．ハッシュ値が計算される前に，変ラフに加えられず，スライシングを終了する．

1: void sample2(){2:while(this.goOrStop()){
3:
if(null == this.getPath()){
4:
Project proj = this.getProject();
5:
this.setPath(proj.getBaseDir());
6:}
7:StringBuilder text = new StringBuilder();8:
text.append("String A");9:
text.append("String B");10:
text.append("String C");11:
text.append("String D");
12:
System.out.println(text.toString());
13:
}
14: }

<1>

<2>

<3>

<4>

<5>
<7>

<8>

図 2 比較対象ソースコード<9>• (p1, p2) が異なるハッシュ値を持つ場合．

<10>
制御依存

• (p1, p2) のハッシュ値は等しいが，r1 のグラ<11>フ（または r2 のグラフ）がすでに p1（またを回避するための処理である．

データ依存
実行依存

は p2）を含んでいる場合．これは無限ループ• (p1, p2) のハッシュ値は等しいが，r1 のグラ

<14>

<12>
図3

実行依存を付加した PDG

フ（または r2 のグラフ）が p2（または p1）

プに n 個の頂点を含む場合は，n(n-1)/2 個のペアを含んでいる場合．2 つの同型部分グラフがに対して同型部分グラフの検出が行われる．実規

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

模ソフトウェアでは，1 つのグループに何百，何

この処理を同じグループに属する全ての頂点のペ千という頂点が含まれる場合があり，膨大なペア

アに対して行う．スライシング終了後に特定され数に対して検出処理を行わなければならない．

ているグラフのペア（2 つの同型部分グラフ）が• 頂点のペアから同型部分グラフを検出する事自体

コードクローンのペアである．

2.3 PDG を用いたコードクローン検出の問題点

が，NP 完全な難しい問題である．

2.4 改良手法の概要

PDG を用いたコードクローン検出は，連続コード

連続コードクローンの検出能力が低い問題を改善す

クローンの検出能力が低い．例えば，図 1(a) と図 2 かるため，著者らは PDG に新しい依存関係，実行依存

らコードクローン検出を行なう場合を考える．図 1(a)を導入することを提案した10) ．実行依存はプログラムの 2 行目から始まる if 文の内部の処理と，図 2 の 2 行

要素間の実行の順序を表す依存関係である．PDG 上

目から始まる while 文の内部の処理は，12 行目の文をの 2 つの頂点において，そのうちの 1 つの頂点（頂点除いて重複している．しかし，既存手法を用いてコーA とする）のプログラム要素が，他方の頂点のプログ

ドクローン検出を行なった場合は，3 行目から 5 行目

ラム要素（頂点 B とする）が実行された直後に実行までが 1 つのコードクローンとして検出され，7 行目

される可能性がある場合は，頂点 B から頂点 A に向から 11 行目までは異なるコードクローンとして検出

かって実行依存辺が引かれる．実行依存を導入するこされる．この理由は， 3 行目から始まる if 文の処理ととにより，データ依存や制御依存がない場合でもソー

7 行目から始まる変数 text に対する処理は，PDG 上

スコード上で隣接したプログラム要素をたどることがでは 2 行目の条件式の頂点を介して接続しているが，可能となり，連続コードクローンの検出能力が上がる．

図 1(a) と図 2 では，条件式が等しくないため，プロ

図 3 は，図 1(b) に実行依存を導入した PDG を表し

グラムスライシングがその頂点で止まるからである．

ている．実行依存を導入することにより，3 行目から

PDG を用いた検出では，計算コストが高いこともの if 文の処理と 7 行目からの変数 text に対する処理短所である．具体的には以下の 2 つの処理において高が PDG 上で直接接続されるため，3 行目から 11 行目

い計算コストを必要とする．

までが 1 つの連続コードクローンとして検出される．

• 同型部分グラフの検出は，同じグループに属する頂点の全てのペアに対して行われる．あるグルー

3. 提 案 手 法<1>

提案手法は，PDG の頂点数を削減することにより，<2>

コードクローン検出に必要な計算量を削減する．また，検出能力の向上も考慮に入れ，これまでの研究により

<3>

<14>

コードクローン検出に悪影響を与えるとされている
ソースコード上の繰り返し処理部分9) ，を削減の対象<4>とする．ソースコード上の繰り返し処理とは，図 1(a)の 8 行目から 11 行目のような，文単位で同様の処理を繰り返し行っている部分を指す．このような処理部

<5>
<7>

分から検出されるコードクローンは，人間が必要とす
るコードクローン情報となることはほとんどないこと<8,9,10,11>
制御依存

9)

がこれまでに示されている ．例えば，8 行目の頂点とデータ依存

10 行目の頂点から，フォワードスライスを用いて実行依存をたどることにより，8,9 行目と 10,11 行目が同一処理として検出されるが，そのようなコードクロー

実行依存

<12>

図 4 提案手法を用いて頂点集約を行なった PDG

ンを人間が必要とすることはないだろう．8 行目から

11 行目までの処理をそれぞれ異なる頂点とするので点となっている頂点の集合を dataf rom (p) とするはなく，まとめて 1 つの頂点として PDG を構築すると，頂点 m からのデータ依存辺を持つ頂点の集ことにより，上記のような必要の無いコードクローン合は以下の式により定義される．

の検出処理を抑えつつ，（PDG の頂点数が少なくなるため）計算コストも削減も実現することができる．
具体的には，提案手法では，下記の全ての条件を満

dataf rom (m) =∪dataf rom (p) ∩ P (2)p∈P

制御依存辺 条件 2 より，P に含まれる全ての頂点たす頂点群が 1 つの頂点として集約される．

は，同一の頂点からの制御依存辺を持つ．提案手

条件 1 文 s から文 t へ，実行依存辺のみをたどるこ

法では，頂点 m も同一の頂点からの制御依存辺とにより到達可能な経路 s,u1 ,u2 ,· · ·, uk , t（以降，をもつとする．頂点 p を終点とする制御依存辺の経路 R）が存在する．

始点となっている頂点の集合を controlto (p) とす

条件 2 経路 R に存在する全ての頂点（頂点 s と t を含む）は，実行依存の入力辺と出力辺を 1 つずつると，下記の式により定義される．

controlto (m) = controlto (s)(3)

持つ（if 文や while 文などの条件式，およびそれ

また，条件 2 より，P に含まれる頂点を始点とすらが終わった後の合流点を含まない）．

る制御依存辺は存在しない．提案手法では，頂点

条件 3 経路 R 上に存在する全ての頂点は同一ハッ
シュ値を持つ．

m を始点とする制御依存辺も存在しないとする．
よって，頂点 m を始点とする制御依存辺の終点

条件 4 経路 R を包含するいかなる経路も，条件 2 と3 を同時に満たさない．

となっている頂点の集合 controlf rom (m) は，下記の式により定義される．

経路 R に含まれる頂点群を 1 つに集約した頂点をcontrolf rom (m) = ∅(4)m とする．以降，頂点 m を始点・終点とする，データ

実行依存辺 頂点 m を終点・始点とする実行依存辺を依存辺，制御依存辺，実行依存辺について説明する．

もつ頂点の集合 executeto (m)，executef rom (m)データ依存辺 頂点 p を終点とするデータ依存辺の始は，それぞれ以下の式で定義される．

点となっている頂点の集合を datato (p)，経路 R

executeto (m) = executeto (s)(5)に含まれる頂点の集合を P とすると，集約されexecutef rom (m) = executef rom (t)(6)

た頂点 m へのデータ依存辺を持つ頂点の集合は以下の式により定義される．

datato (m) =∪datato (p) ∩ P

図 3 の PDG に対して，提案手法の頂点集約を行なった PDG を図 4 に示す．この例では，図 1(a) に表すソー

(1)

p∈P

同様に，頂点 p を始点とするデータ依存辺の終スコードの 8 行目から 11 行目までの 4 つ頂点が，集約に必要な 4 つの条件をすべて満たしているため，1つの頂点として集約が行われている．

提案手法の頂点集約を行うことにより，下記の 2 つドクローンの検出結果と正解集合を用いて再現率の計算コストを削減することができる．

を算出することにより，提案手法が検出結果に与• 集約した頂点がプログラムスライシング上に現れえた影響を調査した．

る場合，頂点をたどる計算コストを抑えることがこの実験では，Bellon らが作成したコードクローン

できる．例えば，図 1(a) と図 2 において，各ソーの正解集合を用いるため，正解集合の作成元となった

スコードの 7 行目の文をスライス基点としてス

4 つのソフトウェア（表 1）を用いた．以降，これら

ライシングを行なう場合，頂点を集約しない場合のソフトウェアは表 1 で示す省略名でよぶ．

は，8 行目から 11 行目までの頂点をたどるのに，また，この実験では，データ依存辺と制御依存辺か

PDG 上で 4 ホップを必要とするが，頂点集約をらなる従来の PDG を traditional，実行依存辺を追加し行うことにより，1 ホップでたどることができる．

た PDG を execution，提案手法を用いて頂点集約を行• 集約した頂点がスライス基点となる場合，集約しなった PDG を merged とよぶ．

ない場合に比べて頂点の総ペア数が減るため，行

4.1 コードクローンの正解集合

なうプログラムスライシングの数を削減すること

この実験では，2) で公開されているデータを検出すができる．例えば，頂点集約を行なわない場合は，べきコードクローン群とした．このコードクローン群

図 1(a) と図 2 では，各ソースコードの 8 行目からの情報は下記の手順で作成された．

11 行目に存在する計 8 個の文はすべて同一ハッ(1)

文献 4) の著者（Stefan Bellon）が検出対象ソフ

シュ値を持つため，8 C2 = 28 個のペアについて

トウェアを決め，6 人の研究者にコードクローン

スライシングが行なわれる．しかし，それらのペ検出を依頼（Bellon はコードクローン検出ツー

アのうちの多くは，ソースコード上で隣接した文ルの開発者ではないため，中立的な立場で検出であり，そのような頂点のペアを基点としてコー対象ソフトウェアを選んだといえる．
）．依頼さドクローンを検出する必要はないと著者は考える．

れた各研究者は，コードクローン検出ツールの一方頂点集約を行なった場合は，各ソースコード

開発者である．

の 8 行目から 11 行目の 4 つの頂点が 1 つに集約

(2)

各研究者は，自身が開発した検出ツールを用いされるため，同一ハッシュ値を持つ頂点数は 2 つて，対象ソフトウェアから重複コードを検出．所となり，そのペアに対してのみプログラムスライ

定のフォーマットを用いて，検出した重複コー

シングが行われることになる．

4. 適 用 実 験

ドの位置情報を Bellon に送付．

(3)

Bellon は各開発者から送られた重複コードの全ペア（325,935 個）のうちの 2%を乱数を用いて提案手法をコードクローン検出ツール Scorpio7),10)

選択し，それらが本当にコードクローンであるに追加実装し，提案した頂点集約法の効果を調査する

かを手作業により判定．ツールが検出した重複ため，実験を行なった．この実験では，頂点集約が計

コードがそのままコードクローンと判断される算コストの削減量とコードクローンの検出結果に与え場合もあるが，Bellon が必要に応じて重複コーた影響について，下記の項目を用いて評価した．

ドを加工して☆ コードクローンと判断した場合

計算コストの削減量 コードクローン検出に必要な計もある．また，コードクローンではないと判定

算コストを定量的に評価するため，頂点比較回数をされた重複コードもあった．この結果 4 つの対調査した．頂点比較回数とは，検出処理の STEP2

象ソフトウェアから 4,789 個のコードクローン

で同型部分グラフを検出するために，2 つのプロ
表 1 対象ソフトウェア

グラムスライシングを同時に実行し，たどった頂点のハッシュ値を比較した回数である．頂点比較回数が多いほど同型部分グラフの検出に必要なハッシュ値の比較回数が多いことになり，より高い計算コストが必要であったことがわかる．

ソフトウェア

省略名

行数

netbeans-javadoc
eclipse-ant
eclipse-jdtcore
j2sdk1.4.0-javax-swing

netbeans
ant
jdtcoreswing

14,36034,744
147,634
204,037

検出結果に与えた影響 コードクローン検出に与えた影響を定量的に評価するため，この実験では，Bel-lon らが作成したコードクローンの正解集合（検出すべきコードクローンの集合）2),4) を用いた．コー☆

ここでの加工とは，ツールが検出した重複コードから一部分を取り除くことや，重複コードの周辺コードもコードクローンに含めることを指す．

表2

各 PDG の規模と頂点比較回数の調査結果

データ依存

辺数
制御依存

実行依存

6,557
6,557
6,060

4,700
4,700
4,362

5,626
5,626
5,131

0
6,144
5,647

110,422,894
103,408,483
40,211,133

100.0%
93.6%
36.4%

traditional
execution
merged12,505
12,505
12,126

11,26911,26910,998

10,423
10,423
10,073012,37912,002

10,437,444
11,396,350
9,916,301

100.0%
109.2%
95.0%

jdtcoretraditional
execution
merged77,49377,49373,88591,617
91,61788,44364,70164,701
61,263

077,98074,595

1,424,793,100
1,480,543,317
1,048,732,585

100.0%
103.9%
73.6%

swing

traditional
execution
merged82,824
82,82478,78375,56075,55073,026

68,31068,31064,370078,11074,050528,247,797
533,917,155
409,070,104

100.0%
101.1%
77.4%

ソフトウェア

PDG

頂点数

netbeans

traditional
execution
mergedantのペアが抽出された☆ ．
以降，この実験では，ツールが検出した重複コードを

頂点比較回数
絶対値
増減率• 正解クローンの母集団が不明なため，適合率は算出できていない．

クローン候補，Bellon が抽出したコードクローンを正

4.3 計算コストの削減量に関する調査結果

解クローンと呼ぶ．なお，正解クローンは，Bellon に

表 2 に，頂点比較回数の調査結果を示す．この表のより以下の三種類に分類されている．

増減率は，tradtional PDG を基準とした，各 PDG の頂

Type1 空白やタブを除いて表面上全く同一なコード

点比較回数の割合を表している．execution PDG の場

クローンのペア，

Type2 変数名やメソッド名など，ユーザ定義の識別子が異なるコードクローンのペア，

Type3 Type1 や Type2 が許容する変更に加え，文単位や式単位で異なる部分が存在するコードクロー
ンのペア．

合，増減率は約 93∼109%であり，3 つのソフトウェア
で頂点比較回数が増加していた．一方，netbeans では
評点比較回数が減少してた．これは，execution PDG
が tradtional PDG に比べて効率よくコードクローンを検出できる場合があることを示している．

merged PDG の場合，増減率は約 36∼95%であり，Type1 と Type2 は連続コードクローンであり，Type3

全てのソフトウェアで頂点比較回数が削減されているは非連続コードクローンである．

ことが確認された．特に ant 以外の 3 つのソフトウェ

4.2 評 価 基 準

アは削減率が高い．頂点数や辺数は数%しか減少してこの実験では，クローン候補が正解クローンかどう

いないことを考慮すると，提案手法を使うことにより，かを good 値と ok 値を用いて判断し，再現率を算出す

検出のボトルネックとなっている部分を集約している

る．文献 4) と同様，good 値と ok 値の閾値として 0.7といえるだろう．

を用いた． good 値と ok 値，および再現率の定義は付

4.4 検出結果に与えた影響に関する調査録に示す．なお，この実験で用いた正解クローンは，

各 PDG を用いたコードクローンの検出結果を表 3

コードクローンの母集団（対象ソフトウェアに含まれに示す．クローン候補数については，merged PDG がるすべてのコードクローン）ではない．そのため，下traditional PDG や execution PDG に比べて多いソフト

記の点に留意されたい．

ウェアも少ないソフトウェアもあり，傾向はつかめな• 再現率の絶対値そのものは意味のある値ではな
い☆☆

．この値はあくまでも複数の検出結果を相対的に比較するためのものである．

かった．検出された正解クローン数については，jdt-

core においては，execution PDG の検出数が traditional
PDG に比べて非常に大きく，実行依存辺導入の効果がもっとも顕著に現われている．他のソフトウェアにつ☆

Bellon らの正解集合は Java 言語の 4 つのソフトウェアと C 言語の 4 つのソフトウェアに対して作成された．本論文ではこの
うち，Java 言語に対して作成された 2,207 個のコードクローンのペアを用いた．
☆☆
正解クローンの母集合を用いていないため，再現率の絶対値が検出能力を正しく表しているとは限らない．

いても，ほとんどの場合について微増している．swingの good 値を用いた評価の場合のみ，Type3 のコードクローンを 1 つ見落としてしまう場合があった．

merged PDG と execution PDG の正解クローンの検出数を比較すると，提案手法を用いることにより見落表3
正解クローン数
ソフトウェア

検出された正解クローン数

PDG

クローン
候補数

検出された正解クローン数
Type1
Type2
Type3
good
ok
good
ok
good
ok

Type1

Type2

Type3

netbeans

6

33

16

traditional
execution
merged18,236
18,636
10,657

2
2
2

5
5
5

8
9
10

21
22
22

8
8
8

ant

4

24

2

traditional
execution
merged

1,279
1,553
1,378

0
0
0

3
3
3

6
6
6

10
10
10

jdtcore

120

866

359

traditional
execution
merged150,750
248,488268,266

31
33
36

98
101
102

195
314
322

swing

145

595

37

traditional
execution
merged63,55867,636
31,114

31
31
31

54
55
56

71
72
72

再現率

good

ok

14
14
14

0.327
0.345
0.364

0.727
0.745
0.745

1
1
1

1
1
1

0.233
0.233
0.233

0.467
0.467
0.467

483
619
624

84
130
130

165
214
214

0.230
0.355
0.363

0.555
0.694
0.699

359
360
360

13
12
13

22
22
23

0.148
0.148
0.149

0.560
0.560
0.565

としてしまう場合は皆無であることがわかる．また，う．頂点数が削減されるため，プログラムスライシン

jdtcore 以外の 3 つのソフトウェアにおいても正解ク

グにおいて頂点をたどるコスト，またプログラムスラ

ローンの検出数が微増している．これは，連続した同イシングを行なう回数がそれぞれ削減できる．提案手

一処理部分全体をまとめてコードクローンとすること

法を検出ツール Scorpio7),10) に追加実装し，オープン

により，正解クローンとの good 値，ok 値が閾値を上

ソースのソフトウェアに対して実験を行なった．この回った（人間がコードクローンと判断する部分に近づ

実験により，必要なコードクローン情報をまったく減いた）場合があったことを示しており，提案手法は，らすこと無く，計算コストを最大で約 36%にまで削減

検出結果の再現率向上にも役立つといえる．

できることが確認された．今後は，実行依存辺だけで4.5 実験結果の妥当性について留意すべき点なく，他の要素に着目しさらに計算コストを削減する

本実験では，Bellon らが作成したコードクローンの手法を考案する予定である．また，近年，プログラム

正解集合を用いて提案手法の有効性について調査を行

依存グラフ以外の技術を用いた非連続コードクローン

なった．しかし，この正解集合は対象ソフトウェアにを検出する手法も提案されている6),14) ．これらの手法含まれるすべてのコードクローンではない．そのため，と本手法を用いた比較も行う予定である．

全ての正解クローンを対象にして同様の実験を行なっ

謝辞 本研究は一部，文部科学省「次世代 IT 基盤

た場合は，提案手法を用いることにより，検出されな構築のための研究開発」（研究開発領域名：ソフトウェ

くなってしまう正解クローンが現われる可能性がある．

ア構築状況の可視化技術の開発普及）の委託に基づい

また，全ての正解クローンが得られていないため，て行われた．また，日本学術振興会科学研究費補助金

提案手法を用いることによる適合率の変化については

基盤研究 (A)(課題番号：21240002) および (C)(課題番

調査ができていない．コードクローン検出手法の適合号：20500033)，文部科学省科学研究費補助金若手研

率とは，検出結果のどの程度が正解クローンなのかを

究 (B)(課題番号：22700031) の助成を得た．

表す指標であり，検出手法の能力を評価する上で非常に重要な尺度である．再現率と適合率の両方の変化を見ることにより初めて公正な評価となる．

5. お わ り に
本論文では，プログラム依存グラフを用いたコード
クローン検出に必要な計算コストの削減を目的とした
頂点集約手法を提案した．提案手法は，著者らがこれまでに提案している実行依存つきプログラム依存グラ
フ10) を拡張するものである．提案手法はプログラム依
存グラフの実行依存辺に着目し，辺の始点と終点が一定の条件を満たす場合は 1 つの頂点として集約を行な

参

考

文

献

1) : Clone Detection Literature, http://www.
cis.uab.edu/tairasr/clones/literature/.
2) : Detection of Software Clones, http://bauhaus-stuttgart.
de/clones/.
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 En-

gineering, 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) Gabel, M., Jiang, L. and Su, Z.: Scalable Detectionof Semantic Clones, Proc. of the 30th International
Conference on Software Engineering, pp. 321–330(2008).
7) 肥後芳樹, 楠本真二: 実規模ソフトウェアへの適用を目的としたプログラム依存グラフに基づくコー
ドクローン検出法, ソフトウェアエンジニアリン
グ最前線 2009（ソフトウェアエンジニアリング
シンポジウム 2009 予稿集）, pp. 97–104 (2009).
8) 肥後芳樹, 楠本真二, 井上克郎: コードクローン
検出とその関連技術, 電子情報通信学会論文誌 D,
Vol. J91-D, No. 6, pp. 1465–1481 (2008).
9) Higo, Y., Kamiya, T., Kusumoto, S. and Inoue, K.:
Method and Implementation for Investigating CodeClones in a Software System, Information and Software Technology, Vol. 49, No. 9-10, pp. 985–998(2007).
10) Higo, Y. and Kusumoto, S.: Significant and Scalable Code Clone Detection with Program Dependency Graph, Proc. of the 16th Working Conference
on Reverse Engineering, pp. 315–316 (2009).
11) Kim, M., Bergman, L., Lau, T. and Notkin, D.:
An Ethnographic Study of Copy and Paste Programming Practices in OOPL, Proc. of 2004 International
Symposium on Empirical Software Engineering, pp.
83–92 (2004).
12) Komondoor, R. and Horwitz, S.: SemanticsPreserving Procedure Extraction, Proc. of the 27th
ACM SIGPLAN-SIGACT on Principles of Programming Languages, pp. 155–169 (2000).
13) Krinke, J.: Identifying Similar Code with Program
Dependence Graphs, Proc. of the 8th Working Conference on Reverse Engineering, pp.301–309 (2001).
14) Roy, C. K. and Cordy, J. R.: NICAD: Accurate Detection of Near-Miss Intentional Clones Using Flexible Pretty-Printing and Code Normalization, Proc. of
the 16th Intenational Conference on Program Comprehension, pp. 172–181 (2008).
15) Roy, C. K. and Cordy, J. R.: A Survey on Software
Clone Detection Research, Technical report, Schoolof Computing, Queen’s University (2007).

付

録

p1.f2

p2.f1

p2.f2
p2

Clone Pair: p1, p2
Code Fragments in p1: p1.f1, p1.f2
Code Fragments in p2: p2.f1, p2.f2

図 5 good 値と ok 値の算出例

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

contain(f1 , f2 ) =|lines(f1 ) ∩ lines(f2 )|(7)|lines(f1 ) ∪ lines(f2 )||lines(f1 ) ∩ lines(f2 )|(8)|lines(f1 )|定義 3 2 つのクローンペア（p1 と p2 ）の good 値は以下の式で定義される．

good(p1 , p2 ) = min(overlap(p1 .f1 , p2 .f1 ),overlap(p1 .f2 , p2 .f2 )) (9)図 5 には 2 つのクローンペア（p1 と p2 ）が存在している．この場合，good 値は，

5 6
5good(p1 , p2 ) = min( , ) =8 88となる．good 値の閾値が 0.7 の場合， 58 ≤ 0.7 である
ため，2 つのクローンペアは一致しない．
定義 4 2 つのクローンペア（p1 と p2 ）の ok 値は以下の式で定義される．

ok(p1 , p2 ) =min(max(contain(p1 .f1 , p2 .f1 ),contain(p2 .f1 , p1 .f1 )),max(contain(p1 .f2 , p2 .f2 ),contain(p2 .f2 , p1 .f2 )))(10)

図 5 の例を用いた場合，ok 値は，

5 5
6 6
5
ok(p1 , p2 ) = min(max( , ), max( , )) =
6 7
6 8
6
となる．good 値の閾値が 0.7 の場合， 0.7 ≤ 65 であるため，2 つのクローンペアは一致する．
定義 5 コードクローンの正解集合を Sref s ，ok 値を用いてコードクローン検出結果 R から抽出した
正解クローンの集合を Sok (R)，good 値を用いた正解集合を Sgood (R) としたとき，R の再現率はそれぞれ以下の式で定義される．

|Sok (R)||Sref s ||Sgood (R)|
Recallgood (R) =|Sref s |Recallok (R) =定義 1 2 つのコード片（f1 と f2 ）の重なりの程度を以下の式で定義する．なお，lines(f ) はコード片
f に含まれる行の集合を表す．

overlap(f1 , f2 ) =

p1
p1.f1

(11)
(12)