社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

複数コードクローン検出結果の比較・表示法
松島 一樹†

井上 克郎†† 大阪大学大学院情報科学研究科 〒560–0871 大阪府吹田市山田丘 1–5
E-mail: †{k-matusm,inoue}@ist.osaka-u.ac.jp
あらまし

コードクローンを自動的に検出するための様々な手法が提案されてきており，コードクローン検出ツールとして実装されてきた．しかし，同一のソースコード集合に対してであっても，コードクローン検出ツールごとの特性や検出パラメータによって検出されるコードクローンは大きく変化することが既存研究から明らかとなっている．
そこで本研究では，同一ソースコード集合を対象とした複数のコードクローン検出結果に対してクローンペア間の対応に注目し，定性的・定量的な評価を容易にする比較・表示法を提案する．
キーワード

コードクローン，ソフトウェア保守

A Method for Comparison and Visualization of Code Clone Detection Results
Kazuki MATSUSHIMA† and Katsuro INOUE†† Graduate School of Information Science and Technology, Osaka University 1–5, Yamadaoka, Suita,Osaka, 560–0871, Japan
E-mail: †{k-matusm,inoue}@ist.osaka-u.ac.jp
Abstract Many techniques for automatic code clone detection have been proposed and implemented as clone
detection in the past. However, existing studies show that the result of code clone detection changes drasticallyin accordance with the tool and its detection parameters. In this study, we propose a method for comparison andvisualization of code clone detection results focused on the correspondence of clone pairs.
Key words code clone, software maintenance1. ま え が き

きた [2] [9]．一方 Bellon ら [3] や Wang ら [4] の研究から，同一のソースコード集合に対してであっても，コードクローン検

コードクローンとは，ソースコード中に存在する「全く同一出ツールごとの特性や検出パラメータによって検出されるコーのコード片」もしくは「類似したコード片」のことである．コー

ドクローンは大きく変化することが明らかになっている．そのドクローンの発生原因として，主に既存のソースコードのコため，様々なコードクローン検出ツールやパラメータでコードピー・アンド・ペーストによる再利用や，コード生成ツールにクローン検出を行い，得られた結果の共通部分や差異を知るこよる自動生成が挙げられる [1]．もし，欠陥が含まれたコード片とは重要である．にコードクローンが存在する場合，それらすべてにも欠陥が含

しかし，これらの研究を始めとしてコードクローン検出結果まれている可能性が高い．開発者はすべてのコードクローンにはベンチマークに対する再現率や適合率といった基準で比較さ対して修正を行うか検討する必要があり，欠陥の修正に大きなれてきたが，含まれているコードクローンの共通部分や差異とコストが必要となる．そのため，コードクローンはソフトウェいった基準での比較は行われていなかった．

ア開発の保守工程における大きな問題の 1 つとして指摘されている．
開発者がコードクローンの管理や修正を行うことで，潜在的な欠陥の増大の抑制やソースコード量の削減につながり，ソフ

そこで，本研究では同一ソースコード集合を対象とした複数のコードクローン検出結果に対してクローンペア間の対応に注目し，定性的・定量的な評価を容易にする比較・表示法を提案する．

トウェアの保守性を高く保つことができる．そのため，開発者また，提案手法を実際のソフトウェアに適用し，コードクローがコードクローンに関する情報を認識することは重要である.

ン検出結果を比較することで重要なコードクローンを発見できコードクローンを自動的に検出するための様々な手法が開発るかについて実験を行った．

されてきており，コードクローン検出ツールとして実装されて—1—ことが既存研究から明らかになっている．

Bellon らは論文 [3] において，CCFinder のデフォルトパラメータと調整したパラメータで検出されるコードクローンの正解集合に対する適合率と再現率を比較した．その結果，調整したパラメータはデフォルトパラメータと比べ，再現率が変化しないまま適合率が 3 倍以上向上していた．
また，Wang らは論文 [4] において，6 つのコードクローン検出結果を行単位で比較した．その結果，ある 1 つのコードクローン検出ツールで検出されたコードクローンの多くはほかのコードクローン検出ツールでは検出されないものであった．ま図 1 GemX の散布図

た，全コードクローン検出ツールで共通して得られるコードクローンは 10 % 程度であった．

以降，2 章では，本研究の背景としてコードクローンと主な検出手法，コードクローン分析における問題について述べる．

3 章では，提案手法について述べる．4 章では，提案手法の適用実験について述べる．最後に，5 章では，まとめについて述べる．

このように，ただ 1 つのコードクローン検出結果だけでは着目すべきコードクローンが含まれていない可能性がある．着目すべきコード片がコードクローン検出結果に含まれていなければ，開発者がソースコードに対する適切な保守を行うことは困難である．

2. 2. 3 コードクローン検出結果の可視化手法

2. 背景

2. 1 コードクローン
コードクローンとは，ソースコード中に存在する「全く同一のコード片」もしくは「類似したコード片」のことである．コー
ドクローンは，主に既存のソースコードのコピー・アンド・ペーストによる再利用やコード生成ツールによる自動生成によって生じる．一般的に互いにコードクローンとなる 2 つのコード片の組をクローンペアと呼び，コードクローンの同値類をクローンセットと呼ぶ [6]．

2. 2 コードクローン検出と分析
2. 2. 1 主なコードクローン検出手法
コードクローンを自動的に検出するための様々な手法が提案されている [2] [9]．主な手法として，テキストベースの検出やトークンベースの検出などが提案されている．

2. 2. 2 コードクローン分析における問題
開発者はコードクローン検出結果を分析することで，コードクローンに対して保守作業を検討する．
保守作業の例として以下の 2 つが挙げられる [2]．
集約
クローンセット中のコード片と同様の処理を実装するサブルーチンを作り，各コード片をそのサブルーチンの呼び出し文に置き換えることである．集約により，コードクローンの数とソースコード量を削減する．
同時修正あるコード片を修正する際に，そのコード片のコードクローンに対しても一貫した修正を行うことである．
このように，コードクローン検出結果を分析しコードクローンに対して保守作業を行うことで，ソフトウェアの品質を向上させることができる．しかし，同一のソースコード集合に対してであっても，コードクローン検出ツールごとの特性や検出パコードクローン検出結果を可視化する既存の手法として，クローン散布図が挙げられる．クローン散布図とは，ソースコード中のどの位置にコードクローンが存在するかをプロットした図である [10]．

CCFinderX（注 1） に付属するコードクローン分析ツール GemX
で実際に用いられるクローン散布図を図 1 に示す．この図では，左上角を原点として，横軸・縦軸共にソースコードのトークン列を表す．そして，両軸の対応するトークンが一致している場合に点が描画されている．また，描画される点は左上角から右下角への対角線を軸として線対称となっている．クローン
散布図を見ることで，ソースコード中のどの位置に，どの程度の大きさのコードクローンが存在しているかを容易に理解することができる．

3. 提 案 手 法
本章では，提案手法の処理概要とその各ステップの詳細について述べる．
まず，提案手法の処理概要を図 2 に示す．
提案手法は図 2 に示すように，4 つのステップで処理が行われる．
（ 1 ） 対象プロジェクトからコードクローンを検出（ 2 ） コードクローン検出ツールから出力されたコードク
ローン検出結果を共通フォーマットへ変換（ 3 ） 同じ部分を指すクローンペア同士の対応付け（ 4 ） 比較結果を可視化し，開発者に提示
以降の節でそれぞれについて詳細を述べる．

3. 1 ステップ 1: コードクローン検出
まず，対象プロジェクトに対してコードクローン検出を行う．
開発者は，使用するコードクローン検出ツールとそのパラメータの組を複数設定することができる．そして，入力されたパララメータによって検出されるコードクローンは大きく変化する（注 1）：http://www.ccﬁnder.net/ccﬁnderxos-j.html

—2—

(1)

(2)

コードクローン
検出結果の正規化

対象プロジェクト
コードクローン
検出結果

検出パラメータ(3)

コードクローン
検出ツール

クローンペアの対応付け(4) 比較結果の提示

検出パラメータ
コードクローン
検出結果の正規化
コードクローン
検出結果

図 2 提案手法の概要図

メータを開発者が指定したコードクローン検出ツールに引き渡
for each q in r’ dofor each p in r do
ok_max=ok(p, mapped[p])good_max=good(p, mapped[p])ok=ok(p, q)
good=good(p, q)
if better thenmapped[p]=q
end ifend forend forし，コードクローン検出を行う．提案手法で対応しているコードクローン検出ツールは，CCFinderX，NiCad [5]，CCVolti [7]，CCFinderSW [8] の 4 つである．
3. 2 ステップ 2: コードクローン検出結果の正規化
ステップ 2 ではコードクローン検出ツールから出力されたコードクローン検出結果を共通フォーマットへ変換する．
コード片は一般的に，<ファイル，開始位置，終了位置> の3 つの要素から定義される．しかし，これらの出力形式はコードクローン検出ツールにより様々である．例えば CCFinderX

図 3 r から r ′ へのクローンペアマッピングのアルゴリズム

であれば <ファイル ID，開始トークン番号，終了トークン番号> を用いて出力される．一方，NiCad であれば，<ファイルパス，開始行番号，終了行番号> を用いて出力される．

コードクローン検出ツールの空行や改行の扱いの違いにより，同じ部分を指しているクローンペアであってもコード片の範囲

そこで，提案手法では比較を簡単にするために，各コードクがずれることがある．ok 値と good 値に基づいてマッピングをローン検出結果を共通フォーマットと呼ぶ <ファイル ID，開行うことで，範囲がずれているコード片で構成されたクローン

始行番号，終了行番号> の 3 つ組の列に変換する．

ペア同士も対応していると判定することが可能となる．

以降，コード片 f のファイル ID を f id，開始行番号を b，以降，コード片 f に対して，lines(f ) が f に含まれるソー

終了行番号を e とし，それぞれ f.f id，f.b，f.e のように表す．

スコード行の集合を表し，|lines(f )| が lines(f ) の要素数，つ更に，コード片 f1 ，f2 に対して次のような順序関係を定まり f の行数を表す．
まず，good 値と ok 値を求めるために用いられる関数 overlap

める.．

f1 < f2 ⇔(f1 .f id < f2 .f id)∨
(f1 .f id = f2 .f id ∧ f1 .b < f2 .b)∨(f1 .f id = f2 .f id ∧ f1 .b = f2 .b ∧ f1 .e < f2 .e)と contained の定義を以下に示す．

overlap と contained の定義
任意のコード片 f1 ，f2 に対してoverlap(f1 , f2 ) =|lines(f1 ) ∩ lines(f2 )||lines(f1 ) ∪ lines(f2 )|contained(f1 , f2 ) =|lines(f1 ) ∩ lines(f2 )||lines(f1 )|そして，任意のクローンペア p を構成する 2 つのコード片

f1 ，f2 について，常に p.f1 < p.f2 が成り立つものとする．この順序関係が成り立たないクローンペアについては，条件を満たすように f1 と f2 の入れ替えを行う．
ステップ 1 により，すべてのコードクローン検出結果を正規化し，統一された形式で扱うことが可能になる．

3. 3 ステップ 3: クローンペアの対応付け



overlap は 2 つのコード片同士の重複度を表し，containedは f1 に対する f2 の包含度を表す．
次に good 値と ok 値の定義を以下に示す．

ステップ 3 では複数の検出結果間でクローンペア同士の対応付け（クローンペアマッピング）を行う．
対応するクローンペアの判定には，クローンペアを構成するコード片の完全一致ではなく ok 値と good 値に基づいて行
う [3]．

—3—
good 値と ok 値の定義

r₁

任意のクローンペア p1 ，p2 に対して

p₂

ok=0.5good=0.6

p₁

good(p1 , p2 ) = min(overlap(p1 .f1 , p2 .f1 ),ok=0.8
good=0.8

overlap(p1 .f2 , p2 .f2 ))ok=0.9
good=0.9

ok(p1 , p2 ) = min(max(contained(p1 .f1 , p2 .f1 ),contained(p2 .f1 , p1 .f1 ))q₂

ok=0.8
good=0.9max(contained(p1 .f2 , p2 .f2 ),contained(p2 .f2 , p1 .f2 ))q₁r₂

図 4 クローンペアマッピングの例

good 値は 2 つのクローンペアを構成するコード片同士の重複度を表し，ok 値は 2 つのクローンペアを構成するコード片同(a)士の包含度を表す．
(c)

そして，2 つのコードクローン検出結果 r から r′ へのクローンペアマッピングのアルゴリズムを図 3 に示す．図中の better(b)は以下の条件を満たすときに真となる．

better =(good ≥ t ∧ good > good_max)∨(d)(good = good_max ∧ ok > ok_max)∨(ok ≥ t ∧ ok_max < t)提案手法では，better 中の閾値 t として論文 [3] で用いられ

図 5 提案手法の散布図の例

た値 0.7 を使用している．
これらをもとに，2 つのコードクローン検出結果 r1 と r2 のクローンペアマッピングを以下の手順で行う．

(ⅰ)（ A ） r1 から r2 へのクローンペアマッピングを行う．
（ B ） r2 から r1 へのクローンペアマッピングを行う．

(ⅱ)（ C ） 手順（A）と手順（B）で得られたクローンペア同士の対応関係の和集合を r1 と r2 のクローンペアマッピングとする．
以降，この手順でマッピングされたクローンペアのことをマッ(ⅲ)

チしたクローンペアと呼ぶ．
図 4 を例にマッチしたクローンペアを求める．
まず，手順（A）に従って r1 から r2 へのクローンペアをマッピングを行う．ok 値と good 値から，p1 と q1 を，p2 と q2 を図 6 マッチしたクローンペアリストの例それぞれマッピングする．
次に，手順（B）に従って r2 から r1 へのクローンペアをマッピングを行う．ok 値と good 値から，q1 に p1 を，q2 と p1 をそれぞれマッピングする．
最後に，手順（C）に従って r1 と r2 のクローンペア同士の対応関係の和集合を求める．
以上より，p1 には q1 と q2 が，p2 には q2 が，q1 には p1が，q2 には p1 がマッチする．

3. 4 ステップ 4: 比較結果の提示
最後に比較結果を可視化し，開発者に提示する．
第 2. 2. 3 節において，既存のコードクローン検出結果の可視化手法としてクローン散布図について述べた．
このクローン散布図をもとに提案手法では，各点をミスマッチ率に応じて彩色して描画することで，複数のコードクローン検出結果の差を可視化する．提案手法で出力される散布図を図5 に示す．
ミスマッチ率とは，あるコードクローン検出結果 r を基準として，r と異なるコードクローン検出結果 r′ との差を表す値であり，その定義を以下に示す．


ミスマッチ率の定義

r に含まれる，ファイル s1 と s2 との間のクローンペアの集合を Pall (r, s1 , s2 ) とする．そのうち r′ に含まれるクローンペアとマッチしているものの集合を Pmatch (r, r ′ , s1 , s2 )とする．
このとき，ミスマッチ率 m(r, r ′ , s1 , s2 ) はm(r, r′ , s1 , s2 ) = 1 −|Pmatch (r, r′ , s1 , s2 )||Pall (r, s1 , s2 )|—4—210
211
212
213

230
231
232
233
234
235
236
237
238
239
240
241
242
243

String checkMarginsMessage = pageSetupPanel.recalculate();if ( checkMarginsMessage != null ){JOptionPane.showMessageDialog(⋮略⋮
PageRanges pr = ( PageRanges )PrinterDialog.this.attributes.get( PageRanges.class );try{pr = mergeRanges( pr );PrinterDialog.this.attributes.add( pr );}catch ( PrintException e ){e.printStackTrace();
JOptionPane.showMessageDialog( PrinterDialog.this, jEdit.getProperty("print-error.message", newString[]{e.getMessage()} ), jEdit.getProperty( "print-error.title" ), JOptionPane.ERROR_MESSAGE );return;}

図 7 バグを含んでいる jEdit のコード片

表 1 CCFinderX

この定義から，提案手法の散布図における，コードクローン検出結果 r を基準としたときの点 (s1 , s2 ) における色を以下の手

Minimum Clone Length: 50

順で決定する．

Minimum TKS: 12（ 1 ） |Pall (r, s1 , s2 )| = 0 ならば白色 (図 5 中（a））．

表 2 NiCad（ 2 ） m(r, r ′ , s1 , s2 ) = 0 ならば緑色（b）．

granularity: blocks rename: blind（ 3 ） m(r, r ′ , s1 , s2 ) = 1 のときを赤色として，0 に近づく

threshold: 0.3

につれて黄色へと変化するように色を選ぶ（c, d）．
このようにミスマッチ率に応じて彩色することで，開発者は複数のコードクローン検出結果の差を直感的に把握することがﬁlter: none

minsize: 10

abstract: none

maxsize: 2,500

normalize: nonetransform: none

できる．
また，開発者はどのようなクローンペアがマッチしたかリストで確認することが可能である．提案手法で出力されるマッチしたクローンペアリストの例を図 6 に示す．
リストには，基準となるコードクローン検出結果の現在選択中の点に含まれているクローンペアの一覧が表示される（図 6中（ⅰ））．
また，それぞれの子要素にはマッチしたクローンペアがコー
ドクローン検出結果ごとに表示される（ⅱ）．図の例では，基準に含まれる clone pair [1] に対して，コードクローン検出結果 CCFinderX_default に含まれるクローンペア 1 個と，NiCad_default に含まれるクローンペア 1 個がマッチしていることがわかる．
更に，Value ノードを展開することで，各クローンペアを構成するコード片の範囲を確認することも可能である（ⅲ）．図の例では，CCMkbl.java の 130 行目から 156 行目のコード片と CCCheckin.java の 132 行目から 157 行目のコード片がNiCad_default の clone pair [1] を構成していることがわかる．

4. 適 用 実 験
本章では提案手法を用いた適用実験について述べる．
適用実験では，提案手法を用いることで重要なコードクローンを発見できるかについて調査した．具体的には，オープンソースソフトウェア jEdit において実際に修正されたバグを含んだコード片のコードクローンを複数のコードクローン検出結果を比較することで発見する．
対象となったコード片を図 7 に示す．このコード片はファイル PrinterDialog.java に含まれていた．以降，このコード片をコード片 A と呼ぶ．
適用実験で用いた jEdit の詳細を以下に示す．

•プログラミング言語: Java•

リビジョン: r24577•LOC: 113,826 行

また，コードクローン検出結果として CCFinderX と NiCadのそれぞれのデフォルトパラメータで得られたものを用いた．
それぞれのデフォルトパラメータの詳細を表 1 と表 2 に示す．
まず，CCFinderX のコードクローン検出結果について調査した．
図 8 に CCFinderX のコードクローン検出結果を基準としたミスマッチ率の散布図の一部を示す．中央黒枠で囲まれた部分が点 (PrinterDialog.java，PrinterDialog.java) である．クロー
ンペアリスト（図 9）を確認すると，この点にはクローンペアが 20 個含まれていて，そのうち NiCad で検出されたクローンペアとマッチしたものは 2 つであった．また，コード片 A を含むクローンペアは CCFinderX で 1 個検出された（図 9 中—5—

図 8 CCFinderX の検出結果を基準としたミスマッチ率の散布図の一部⋮略図 10 NiCad の検出結果を基準としたミスマッチ率の散布図の一部

5. まとめと今後の課題
本研究では，複数のコードクローン検出結果間でクローンペア同士の対応付けを行うクローンペアマッピングを定義した．
また，ミスマッチ率を定義することでそれらの差を可視化する手法を提案した．
そして，提案手法を実際のソフトウェアに適用し 2 つのコー
ドクローン検出結果を比較したところ，一方だけでは検出でき⋮略なかった重要なコードクローンを発見できることを確認した．
今後の課題として，他のコードクローン検出結果のクローンペアとマッチしないクローンペアの中から重要なものを優先的

図 9 CCFinderX の検出結果における点 (PrinterDialog.java, Prin-terDialog.java) のクローンペアリストに開発者に提示することが挙げられる．
謝辞 本研究は JSPS 科研費 18H04094 の助成を受けた．
文青枠部分）が，これとマッチするクローンペアは NiCad では検出されていないことがわかった．
同様に，点 (PrinterDialog.java, PrinterDialog.java) と同じ列，または同じ行にある点についても調査したが，コード片 Aを含むクローンペアは存在しなかった．
次に，NiCad のコードクローン検出結果について調査した．
図 10 に NiCad のコードクローン検出結果を基準としたミスマッチ率の散布図の一部を示す．図 8 と同様に，中央黒枠で囲まれた部分が点 (PrinterDialog.java, PrinterDialog.java) である．この点は緑色で表示されていることから，すべて CCFind-erX で検出されたクローンペアとマッチしており，コード片 Aの新たなコードクローンは含まれていない．
同様に，(PrinterDialog.java, PrinterDialog.java) と同じ列，または同じ行にある点についても調査したが，すべてクローンペアの存在しない点であった．
これらの調査からコード片 A を含むコードクローンは，NiCad のデフォルトパラメータでは検出できないことが明らかとなった．また，CCFinderX で検出されたコードクローンは，実際にリビジョン r24577 から r24578 への更新においてコード片 A と同時に修正されていた．
よって，提案手法により 2 つのコードクローン検出結果と比較することで，重要なコードクローンを見逃すことなくより正確な分析を行うことが可能となった．

献[1] 井上 克郎, 神谷 年洋, 楠本 真二. コードクローン検出法. コン
ピュータソフトウェア, Vol. 18, No. 5, pp. 47–54, 2001.
[2] 肥後 芳樹, 楠本 真二, 井上 克郎. コードクローン検出とその関連技術. 電子情報通信学会論文誌, Vol. J91-D, No. 6, pp.
1465–1481, 2008.
[3] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and E. Merlo.
Comparison and evaluation of clone detection tools. TSE,Vol. 31, No. 10, pp. 804–818, 2007.
[4] T. Wang, M. Harman, Y. Jia, and J. Krinke. Searching forbetter conﬁgurations: a rigorous approach to clone evaluation. In Proc. ESEC/FSE 2013, pp. 455–465, Aug. 2013.
[5] C. K. Roy and J. R. Cordy. NICAD: Accurate Detection ofNear-Miss Intentional Clones Using Flexible Pretty-Printing
and Code Normalization. In Proc. ICPC 2008, pp. 172-181,2008.
[6] T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: a multilinguistic token-based code clone detection system for large
scale source code. TSE, Vol. 28, No. 1, pp. 654–670, 2002.
[7] 横井 一輝, 崔 恩瀞, 吉田 則裕, 井上 克郎. 情報検索技術に基づく
細粒度ブロッククローン検出. コンピュータ ソフトウェア, Vol.
35, No. 4, pp. 16-36, 2018.
[8] Y. Semura, N. Yoshida, E. Choi, and K. Inoue. CCFinderSW: Clone Detection Tool with Flexible Multilingual Tokenization. In Proc. APSEC 2017, pp. 654-659, 2017.
[9] C. K. Roy, J. R. Cordy, and R. Koschke. Comparison andevaluation of code clone detection techniques and tools: A
qualitative approach. Science of Computer Programming,Vol. 74, No. 7, pp. 470–495, 2009.
[10] Y. Ueda, Y. Higo, T. Kamiya, S. Kusumoto, and K. Inoue.
Gemini: Code Clone Analysis Tool. In Proc. ISESE2002,Vol. 2, pp. 31-32, 2002.

—6—