情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

情報検索技術に基づく高速な関数クローン検出
山中 裕樹1

崔 恩瀞1,a)吉田 則裕2,b)

井上 克郎1,c)

受付日 2014年1月7日, 採録日 2014年6月17日

概要：ソフトウェア保守における問題の 1 つとしてコードクローン（ソースコード中に存在する同一または類似した部分を持つコード片）が指摘されている．これまでの研究において様々なコードクローン検出手法が提案されてきたが，多くの手法がプログラムの構造的な類似性のみに着目している．また，プログ
ラムの意味的な処理の類似性に着目した手法では，検出時間に膨大な時間がかかるという問題点がある．
そこで本研究では，情報検索技術を利用した関数クローン（関数単位のコードクローン）の検出手法を提案する．関数単位のコードクローンは処理の内容がまとまっているため，コード片単位のコードクローンに比べてライブラリ化などの集約の対象になりやすいと考えられる．本手法では，ソースコード中の識別
子や予約語に利用される単語に対して重み付けを行うことによって，関数を特徴ベクトルに変換する．そして，特徴ベクトル間の類似度を求めることによって関数クローンの検出を行う．評価実験では，既存のコードクローン検出手法と比較を行い，高速に高い精度で検出を行うことができた．
キーワード：コードクローン，ソフトウェア保守，情報検索

A High Speed Function Clone Detection
Based on Information Retrieval Techniques
Yuki Yamanaka1

Eunjong Choi1,a)Norihiro Yoshida2,b)Katsuro Inoue1,c)Received: January 7, 2014, Accepted: June 17, 2014

Abstract: A code clone (i.e., code fragment that has identical or similar fragment to it in the source code)is one of the major problems for software maintenance. So far, a lot of approaches have been developed on
the detection of code clones. Several of them focus on semantic similarities based on control and data flow
analyses, however they lack the scalability for large-scale source code. In this study, we propose an approachto detect function clones using information retrieval techniques. The proposed approach generates a feature
vector for each function based on the occurrence of identifiers and reserved keywords, and then performs
clustering of generated vectors. Finally, a set of functions corresponding to vectors in each cluster is detected
as a set of semantic clones. As a case study, we applied the proposed approach to open source softwaresystems. The result shows that the proposed approach is able to perform faster and more precise detection offunction clones compared to the existing approach based on the similarity between abstract memory states.
Keywords: code clone, software maintenance, information retrieval

1. まえがき
ソフトウェア保守における問題の 1 つとしてコードク
1
2
a)
b)
c)

大阪大学
Osaka University, Suita, Osaka 565–0871, Japan
名古屋大学
Nagoya University, Nagoya, Aichi 464–8601, Japanejchoi@ist.osaka-u.ac.jp
yoshida@ertl.jp
inoue@ist.osaka-u.ac.jp

c 2014 Information Processing Society of Japan

ローンが指摘されている [1], [2], [3]．コードクローンとは，
ソースコード中に存在する同一または類似した部分を持つ
コード片のことであり，コピーアンドペーストなどの様々な理由により生成される [1], [3]．一般的に，コードクロー
ンの存在はソフトウェアの保守を困難にするといわれている．たとえば，あるコード片を編集する場合，対応するすべてのコードクローンに対しても一貫した編集が必要となる可能性がある．コードクローンを検出することによっ2245

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)て，一貫した編集がなされておらず，不具合を引き起こす
危険性があるコード片を検出することが可能である．また，
コードクローン中の共通処理に対して，親クラスへの引き

2. コードクローン検出手法
本章では，本研究で提案する関数クローン検出手法の概上げやライブラリ化といった集約を行うことによって，ソ要について説明する．コードクローンには，以下の 4 つのフトウェアの保守性や可読性を向上させることが可能となタイプが存在する [2], [9]．

る [4], [5]．

タイプ 1：空白の有無，レイアウト，コメントの有無など

これまでに様々なコードクローン検出手法が提案されてきたが，その多くの手法がプログラムの構造的な類似性のみに着目している [6]．そのため，同一の処理を実装しているにもかかわらず，for 文と while 文の違いなど構文上の実装が異なる場合はコードクローンとして検出することができる手法は少ない．また，プログラム依存グラフを用いた手法など，構文上の実装に依存せずに，処理内容が類似している部分をコードクローンとして検出する手法もいくつか提案されているが，検出時間に膨大な時間がかかるという問題点がある [7], [8], [9]．
そこで本研究では，情報検索技術を利用することによっの違いを除き完全に一致するコードクローン
タイプ 2：タイプ 1 の違い加えて，変数名などのユーザ定
義名，変数の型などが異なるコードクローン
タイプ 3：タイプ 2 の違いに加えて，文の挿入や削除，変更などが行われたコードクローン
タイプ 4：類似した処理を実行するが，構文上の実装が異なるコードクローンタイプ 4 のコードクローンとして，以下のものがあげられる．

• 条件分岐処理や繰返し処理などの制御構造の実装が異なる（図 3，図 5 参照）．

て，意味的に処理が類似した関数クローン（関数単位の• 中間媒介変数の利用の有無が存在している（図 4 参照）．

コードクローン）を検出する手法を提案する．情報検索と• 文の並べ替えが発生している（図 6 参照）．

は，大量のデータ群から目的に合致したものを取り出すこ本研究では，情報検索技術を利用し，上記のすべてのタとであり，自然言語で書かれた文書の処理などに利用されイプの関数クローンを高速に検出することが目的である．

る [10]．コード片単位で検出を行う場合，構文の不完全な本手法では，入力されたソースコード中のワードに基づ部分で終了するコード片など，集約を行うことが困難でいて各関数を特徴ベクトルに変換する．ここでワードとあるコードクローンが多く検出されることがある [11]．一は，以下の 2 つを対象とする．

方，関数単位のコードクローンは処理の内容がまとまっているため，開発者にとって集約の対象になりやすいコード
クローンを検出できると考えられる．

• 変数や関数などに付けられた識別子名を構成する単語• 条件文や繰返し文などの構文に利用される予約語
そして，特徴ベクトル間の類似度を求めることによってク

本手法では，情報検索技術を用いて，ソースコード中のローンペア（互いに処理が類似した関数クローンの対）の識別子や予約語に用いられる単語に対して重み付けを行

集合をリストとして出力する．また，類似度の計算の直前

うことによって，各関数を特徴ベクトルに変換する．そしに LSH（Locality-Sensitive Hashing）アルゴリズム [12] をて，特徴ベクトル間の類似度を計算することによって関数用いて特徴ベクトルのクラスタリングを行うことにより，クローンの検出を行う．

検出の高速化を図っている．もし，全関数の特徴ベクトル

評価実験では，意味的な類似性に基づく関数クローン
検出ツールの 1 つである MeCC [9] と比較実験を行った．

MeCC は，大域変数，仮引数，局所変数が関数終了時点で間の類似度を計算する場合，ソースコードの規模が大きくなると検出時間が膨大になってしまうと考えられる．
本手法の概要を図 1 に示す．本手法は，主に以下の 4 つ取りうる値を静的解析により推定し，それらの値が類似しのステップから構成される．

た関数対を関数クローンとして検出する．比較実験の結STEP1：ソースコード中の各関数からワードの抽出を果，本手法の方がより高い精度で高速な検出を行うことができた．また，ほぼ同一の処理を実装しているにもかかわ

行う．

STEP2：STEP1 で抽出したワードに重み付けを行うこと

らず，条件分岐処理や繰返し処理の実装が異なる関数クによって，各関数の特徴ベクトルを計算する．

ローンや，文が並べ替えられている関数クローンを検出す

STEP3：LSH アルゴリズム [12] を用いて，STEP2 で求ることができた．
以降，2 章では，本研究で提案する関数クローン検出手

めた特徴ベクトルのクラスタリングを行う．

STEP4：STEP3 で求めたクラスタにおいて，特徴ベクト法について述べる．3 章では，本手法の評価実験について

ル間の類似度の計算を行い，関数クローンを検出する．

述べる．4 章では，評価実験の考察について述べる．5 章

以降の節で，それぞれのステップの詳細について説明する．

では，本研究の関連研究について述べる．最後に，6 章でまとめと今後の課題について述べる．

2.1 STEP1：ワードの抽出
まず最初に，ソースコードの各関数に含まれる識別子や

c 2014 Information Processing Society of Japan


2246

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

図 1

検出手法の概要

Fig. 1 Overview of our detection approach.

予約語から，ワードの抽出を行う．識別子名が複数の単語現頻度）と idf 値（ソースコード全体のワードの希少さ）から構成される場合，以下の方法でワード単位に分割する．

の積で与えられる．ワード x の重み wx の計算式を以下に• ハイフンやアンダースコアなどの区切り記号（デリミ示す．

タ）による分割

• 識別子名中の大文字になっているアルファベットによ

tfx =関数中のワード x の出現回数
関数中に出現する全ワードの出現回数の合計

る分割
たとえば，“value of item” という識別子はアンダーバーで分割し，“value”・“of”・“item” という 3 つのワードに分割できる．また，“itemValue” という識別子も大文字で分

idfx = log

全関数の数
ワード x が出現する関数の数

wx = tfx idfx

割し，“item”・“value” という 2 つのワードに分割できる．

本手法では，全関数中の各ワードに対して重みを計算し，さらに，2 文字以下の識別子名に対しては，それらをまとそれらを特徴量として用いることによって特徴ベクトルをめて 1 つのワードとして扱う．この理由は，繰返し文など求める．したがって，各関数の特徴ベクトルの次元はソーによく利用される “i” や “j” といった意味情報が込められ

スコード中に存在する全ワードの数となる．

ない変数をすべて同一のものとして扱うためである．このように識別子の情報を利用することによって，各関数が実装する機能を表すことができると考えられる．
また，条件文に用いられる “if” や “switch”，繰返し文に用いられる “for” や “while” といった予約語もワードとして扱う．

2.3 STEP3：特徴ベクトルのクラスタリング
このステップでは，STEP2 で計算した各関数の特徴ベク
トルに対してクラスタリングを行うことによって，クロー
ンペアと成りうる候補を絞ることを目的とする．
ここでは，近似最近傍探索アルゴリズムの一種である

LSH アルゴリズム [12] を用いて特徴ベクトルのクラスタリ
2.2 STEP2：特徴ベクトルの計算ングを行う．LSH アルゴリズムは，(p1 , p2 , r, c)-Sensitive

次に，STEP1 で抽出したワードに重み付けを行うこと

Hashing と (r, c)-Approximate Neighbor を用いたクラスによって，各関数を特徴ベクトルに変換する．ここでは，タリング手法である．このアルゴリズムを利用すること

TF-IDF 法 [10] を利用して各ワードの重みを計算し，そのによって，クエリとして 1 つの特徴ベクトルを与えると，値を特徴量として利用する．TF-IDF 法は情報検索におい特徴ベクトル集合からそのクエリと近似した特徴ベクトて文書の類似性の判定などに利用されており，計算コスト

ル集合のクラスタを取得することができる．(p1 , p2 , r, c)-

が小さいため大規模なソースコードにも適用できると考えSensitive Hashing と (r, c)-Approximate Neighbor の定義られる．TF-IDF 法による値は tf 値（関数中のワードの出を以下に示す．

c 2014 Information Processing Society of Japan


2247

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)(p1 , p2 , r, c)-Sensitive Hashing

TF-IDF 法の計算式から分かるように，特徴量はつねに正実 数 p1 , p2 (0 ≤ p1 , p2 ≤ 1)，実数 r(0 < r)，実数の値となるため，コサイン類似度は 0 から 1 の範囲となる．

c(1 < c)，R 空間に対するベクトル集合 V 上の任意

もし，コサイン類似度が閾値以上であれば，その関数の対の点 vi ，vj が与えられたとき，

if D(vi , vj ) < r then P rob[h(vi ) = h(vj )] > p1

はクローンペアであると判定する．

d

3. 評価実験

if D(vi , vj ) > cr then P rob[h(vi ) = h(vj )] < p2を満たすハッシュ関数 h を (p1 , p2 , r, c)-Sensitive Hash-

ing と呼ぶ．ここで，D は Rd 上の距離関数，P rob は

本章では，2 章で述べた関数クローン検出手法の評価実験について述べる．本実験で適用の対象としたオープン
ソースソフトウェアプロジェクトを表 1 に示す．

条件式が真となる確率を表している．

(r, c)-Approximate Neighbor

なお，本実験では結果の信頼性を重視するため，関数ク
ローンとして検出する類似度の閾値を 0.9 とし，E2LSH が

Rd 空間に対するベクトル集合 V 上の任意の点（クエ

自動決定したパラメータ（表 A·1）のみを用いて関数クリ）v が与えられたとき，ローンの検出を行った．
また，Java 言語における setter や getter などの比較的小U = {u ∈ V |D(v, u) ≤ cr}

さい関数を検出の対象から除外するため，他の研究 [14], [15]で定義される V の部分集合 U をクエリ v に対すると同様に 30 トークン以上の関数を対象に実験を行った．

(r, c)-Approximate Neighbor と呼ぶ．ここで，c と r

以降，3.1 節では，コーパスを用いた本手法の検出精度のの定義は (p1 , p2 , r, c)-Sensitive Hashing で利用した定評価について述べる．3.2 節では，既存手法との比較実験

義と共通である．

について述べる．最後に 3.3 節で，本手法で検出できた関Rd 空 間 に 対 す る 特 徴 ベ ク ト ル 集 合 V が 与 え ら れ ，(p1 , p2 , r, c)-Sensitive Hashing を用いた関数の族 hl,k (1 ≤l ≤ L, 1 ≤ k ≤ K) からなる関数 Hl が以下の式で与えられ数クローンの実例を示す．

3.1 コーパスを用いた検出精度の評価

たとき，最初に，Tempero らのコーパス [16]*7 を用いた評価実験

Hl = (hl,1 (v), hl,2 (v), . . . , hl,K (v)) ∈ RK
V 上の任意の点 v に対して L 個の K 次元のベクトルが得られる．LSH アルゴリズムでは，これらのベクトルをそれ
ぞれハッシュテーブルの鍵とすることで高速に近傍点を求めることができる．なお，本手法では LSH アルゴリズムの実装である E2LSH [13]*1 を利用している．
特徴ベクトルの次元を d，特徴ベクトル集合の大きさをn，確率に関するパラメータを ρ = logp2 p1 としたとき，
LSH のクラスタリングの時間計算量は O(dnρ log n) と表される．一方，全関数に対して特徴ベクトル間の類似度を計算する場合の時間計算量は O(dn2 ) となる．したがって，について述べる．このコーパスは，コードクローン検出
ツール CMCD [17] の出力結果と著者らの目視による判断に基づいて作成されている．Bellon らのベンチマーク*8 ではタイプ 3 までのコード片単位のコードクローンを対象としているが，Tempero らのコーパスではタイプ 1 からタイプ 4 のメソッド単位のコードクローンを対象としている．
そのため，本研究では Temepro らのコーパスを用いて評価実験を行った．
本実験では 2 つの Java プロジェクト（Apache Ant，Ar-

goUML）に対して検出精度の評価を行った．これらの Java
プロジェクトは，他のコードクローン検出手法の評価実験

本ステップであらかじめクラスタリングを行い，クローン

表 1

ペアと成り得る候補を絞ることによって，検出時間にかか

適用プロジェクト

Table 1 Target projects.

る計算コストを削減できると考えられる．

2.4 STEP4：特徴ベクトルの類似度の計算

プロジェクト名

バージョン

言語

規模

Apache Ant*2

1.8.4

Java

109 KLOC

ArgoUML*3

0.34

Java

192 KLOC

最後に，STEP3 で求めた各クラスタ中の関数の対に対

Python*4

2.5.1

C/C++

435 KLOC

して，コサイン類似度を用いてクローンペアであるか否か

Apache HTTPD*52.2.14C/C++

343 KLOCの判定を行う．コサイン類似度は多次元ベクトルの類似度

PostgreSQL*6

8.5.1

C/C++

937 KLOCを測定するものであり，次元が d である 2 つの特徴ベクトル a, b 間の類似度は以下の式で表すことができる．

sim(a, b) = cos(a, b) = di=1 ai bid2
i=1 ai*1

http://www.mit.edu/∼andoni/LSH/

c 2014 Information Processing Society of Japan




d
2
i=1 bi

*2
*3
*4
*5
*6
*7
*8

http://ant.apache.org/
http://argouml.tigris.org/
http://www.python.org/
http://httpd.apache.org/
http://www.postgresql.org/
http://www.qualitascorpus.com/clones/
http://softwareclones.org/

2248

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

表 2

コーパスを用いた検出精度

Table 2 Evaluation of detection accuracy based on the corpus.
クローンペア数

適合率

再現率

タイプ 1

タイプ 2

タイプ 3

タイプ 4

Apache Ant

474

92.2%

62.3%

56

139

220

22

ArgoUML

880

96.4%

52.7%

222

219

371

33

でも一般的に利用されており，自動生成コードが存在していないことが知られている．また，本実験では手作業でクローンペアの各タイプの分類を行っており，複数のプロジェクトに対して適用するコストが大きいと考えたため，
この 2 つのプロジェクトに対してのみ適用を行った．
結果を表 2 の適合率と再現率に示す．適合率は，全検出結果に対してコーパスで正解集合と判定されているクロー
ンペアの割合を表している．再現率は，コーパス中のクローンペアに対して本手法によって検出されたクローンペ
アの割合を表している．実験の対象とした 2 つのプロジェクトに対して再現率は 60%前後であるが，適合率は 90%を超えており，誤検出をほとんど含まず関数クローンを検出することができた．Bellon らが行ったタイプ 1〜3 を対象としたコードクローン検出ツールの比較評価 [18] によると，各ツールの再現率は 8%〜46%である．比較評価の方法が異なるため，単純に再現率を比較することはできないが，本手法の 60%前後の再現率から，実用的な検出結果が得られることが期待できる．

図 2

さらに，表 2 には正解集合と判定したクローンペアを手作業で各タイプに分類した結果を示している．この表から分かるように，本手法を用いることによって，すべてのタ

MeCC の概要

Fig. 2 Overview of MeCC.

高い類似度から順に ADDR の対応付けを行う．
最後に，以下の式を用いて，メモリ M EMA と M EMB

イプの関数クローンを検出することができた．

の類似度の計算を行う．

3.2 既存手法との比較

sim(M EMA , M EMB ) =次に，既存手法との比較実験について述べる．本実験で2 × SU M (simaddr )|M EMA | + |M EMB |は，関数クローン検出ツールの 1 つである MeCC [9] との

ここで，SU M (simaddr ) は，2 つの関数間で対応する ADDR

比較を行った．MeCC では，静的解析を行うことによっの類似度の合計値を意味する．そして，これらの類似度がて，ソースコード中の各関数が終了した時点における抽象

閾値以上であれば，コードクローンとして検出を行う．

的なメモリの状態の予測を行う．そして，メモリの状態が本手法で MeCC を比較の対象とした主な理由は，他の類似した関数をコードクローンとして検出する．ここでメ検出手法に比べて，高い精度でタイプ 3 とタイプ 4 の関

モリとは，ADDR（大域変数，仮引数，局所変数などの関数クローンを数多く検出できることを評価実験で示してい数で利用されている変数）と GV（ADDR が取りうる値のるためである．また，大規模なプロジェクトに対しても，集合）の組の集合で表される．メモリの状態の類似度の計

実時間で検出することが可能である．さらに，検出結果を算例を図 2 に示す．この例では，2 つの関数 Function A

ウェブサイト上*9 で公開しているため，比較対象として選と Function B のメモリ M EMA と M EMB の類似度を求

択した．

めている．
まず最初に，以下の式を用いて 2 つの関数中の ADDR の全組合せに対して類似度を計算する．

2 × |GVX ∩ GVY |simaddr (ADDRX , ADDRY ) =|GVX | + |GVY |MeCC は C 言語が対象であるため，その評価実験で利用している 3 つの C プロジェクト（Python，Apach HTTPD，PostgreSQL）に対して比較を行った．以降，検出精度と検出時間の比較について述べる．

3.2.1 検出精度の比較
検出精度の比較では，3 つのプロジェクトに対する適用

ここで GVX と GVY は，それぞれ，ADDRX と ADDRYが取り得る値の集合を意味する．次に，貪欲法を用いて，

c 2014 Information Processing Society of Japan

*9

http://ropas.snu.ac.kr/mecc/

2249

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

表 3

MeCC との検出精度と検出クローンセット数の比較

Table 3 Comparison of accuracy and the number of detected clone sets with MeCC.
誤検出の割合

本手法

MeCC

タイプ 2

タイプ 3

タイプ 4

21

Python

6.5%

19

103

159

Apache HTTPD

4.6%

71

100

190

11

PostgreSQL

5.3%

57

230

341

17

合計

5.4%

147

433

690

59
13

Python

14.7%

3

127

82

Apache HTTPD

12.5%

2

84

71

10

PostgreSQL

16.9%

9

120

88

14

合計

15.0%

14

331

241

37

表 4 再現性の評価

表 5 Roy らのベンチマークを用いた比較

Table 4 Evaluation of recall.

Table 5 Comparison of accuracy using benchmark created by
Roy et al.

30 トークン以上

全関数

Python

97.5%

61.2%

タイプ 1

タイプ 2

タイプ 3

タイプ 4

Apache HTTPD

62.3%

40.0%

ベンチマーク3

4

5

4

PostgreSQL

88.1%

72.7%

本手法

3

2

5

4

合計

86.5%

66.2%

MeCC

3

4

4

4

結果を手作業で正解集合と誤検出に分類し，その割合を比較した．さらに，正解と判断した関数クローンをタイプ 1からタイプ 4 に分類し，タイプごとの検出数を比較した．
なお，MeCC ではクローンセット（互いに類似した関数ク
ローンの集合）単位でタイプの分類を行っている．そのため，本実験においても，クローンペアをクローンセット単位に変換し分類を行っている．
本手法と MeCC における，検出精度とタイプごとの検出
クローンセット数の比較を表 3 に示す．MeCC の検出結
果は，文献 [9] の表 2 および表 3 より抜粋した*10 ．MeCC
では全検出結果に対して，10%以上の誤検出を含んでいるが，本手法では誤検出の割合が 10%未満であった．また，クローンセットの検出数においても，MeCC よりも多くの関数クローンを検出することができた．特に，タイプ 1，
タイプ 3，タイプ 4 の検出はすべてのプロジェクトにおいて MeCC を上回っていることを確認することができた．
また，本実験では MeCC に対する本手法の再現性について評価を行った．再現性とは，MeCC と本手法で検出できた関数クローンの和集合に対する，本手法の検出数の割合を示している．この指標は文献 [18] でも用いられている．
結果を表 4 に示す．なお，本手法では 30 トークン以上の関数のみを対象としている．そのため，MeCC の全検出結果に対する再現性と，30 トークンでフィルタリングした場
合について評価を行った．その結果，全検出結果に対して再現性は約 50%前後であるが，30 トークン以上のより大きな関数では 62%〜98%と高い再現性を示すことを確認す
*10

正解集合
タイプ 1

各表には，MeCC のオプションとして Similarity = 80%およびMinEntry = 50 を指定したときの検出結果が掲載されている．
各オプションについては文献 [9] を参照されたい．

c 2014 Information Processing Society of Japan

ることができた．
さらに，Roy らのベンチマーク [2] を用いて，タイプごとの検出精度の評価を行った．このベンチマークでは，タイプ 1 からタイプ 4 までの合計 16 個の関数単位のクローンペアが用意されており，文献 [9] の評価実験でも利用されている．
表 5 は，ベンチマークで用意されているクローンペアのタイプごとの個数と，本手法で検出することができたクローンペアのタイプごとの個数を示している．結果として，全体で 16 個中 14 個のクローンペアを検出することができた．また，タイプ 1，タイプ 3，タイプ 4 において，本手法を用いてすべてのクローンペアを検出することができた．MeCC は，if 文が挿入されたタイプ 3 のクローンペアを検出することができなかった．これは，if 文が挿入されたことにより，その直後に存在するメソッド呼出し文が実行される条件が変化したためであると考えられる．本手法
は，if 文が追加されても，出現する変数名が変化しなかったため，検出することができたと考えられる．
一方で，タイプ 2 では，2 つのクローンペアの検出を行うことができなかった．これらのクローンペアは，元の変数
名が 1 文字のアルファベットに省略されており，意味を持たない変数名に変換されていたため，本手法ではコードク
ローンとして検出することができなかったと考えられる．

3.2.2 検出時間の比較
検出時間の比較では，MeCC の評価実験で利用された
ワークステーションと同様の環境（OS: Ubuntu 64-bit，CPU: Intel Xeon 2.40 GHz，RAM: 8.0 GB）で本手法を実行し，3 つのプロジェクトに対する検出時間を測定した．

2250

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

表 6 検出時間の比較

Table 6 Comparison of detection time.
本手法
パラメータ

パラメータ

MeCC

計算あり

計算なし

Python4 m 39 s

2 m 13 s

65 m 26 s

Apache HTTPD

4 m 30 s

1 m 43 s

310 m 34 s

PostgreSQL

8 m 51 s

4 m 39 s

428 m 32 s(a) server/conﬁg.c（中間媒介変数を利用した実装）(a) ant/util/ConcatFileInputStream.java（if 文を用いた条件分岐処理）(b) server/conﬁg.c（中間媒介変数を利用しない実装）
図4

中間媒介変数の利用が異なるタイプ 4 の関数クローン（Apache

HTTPD）
Fig. 4 Type-4 function clones with and without a temporalvariable.

(b) ant/util/ConcatResourceInputStream.java
図3（三項演算子を用いた条件分岐処理）
条件分岐処理が異なるタイプ 4 の関数クローン（Apache Ant）

Fig. 3 Type-4 function clones with diﬀerent conditional statements.

結果を表 6 に示す．表中のパラメータ計算とは，特徴ベ
クトルのクラスタリングで利用している E 2 LSH に対するものである．E 2 LSH は LSH のパラメータを自動的に決定する機能を持つ．この機能はデータセットの中からいく
つかのデータをランダムに選択し，その値の傾向を見て適
当なパラメータを自動的に設定する．したがって，1 つの適用対象に対してパラメータの値を一度計算すれば，その(a) Modules/expat/xmlparse.c（for 文を用いた繰返し処理）

後の検出においてもその値を再利用することが可能であると考えられる．
結果として，パラメータ計算を行う場合において，9 分以
下で関数クローンを検出できることを確認できた．また，
パラメータ計算を行わない場合においてはすべてのプロ
ジェクトに対して 5 分以下で関数クローンを検出することができた．一方，MeCC では静的解析に膨大な時間がかかるため，検出時間が長くなる傾向がある．本手法では，関数を特徴ベクトルに変換し，あらかじめ LSH アルゴリズムを用いたクラスタリングを行っている．そのため，MeCC
よりも本手法の方が高速に検出を行うことができたと考えられる．

c 2014 Information Processing Society of Japan(b) Modules/expat/xmlparse.c（do-while 文を用いた繰返し処理）
図 5

繰返し処理が異なるタイプ 4 の関数クローン（Python）

Fig. 5 Type-4 function clones with diﬀerent implementationsof iterative processing.

2251

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

3.3 関数クローンの実例

図 3 は，条件分岐処理が置き換わっている例である．

本手法では文の並べ替え，中間変数の利用の有無，if 文

図 3 (a) では if-else 文を用いて標準出力と標準エラー出力と三項演算子を用いた条件分岐処理の置き換え，for 文との条件分岐処理を実装しているが，図 3 (b) では三項演算

while 文を用いた繰返し処理の置き換えなどの違いが存在子を用いて条件分岐処理を実装している．

する関数クローンを検出することができた．図 3，図 4，

図 4 は，中間媒介変数の利用の有無が存在する関数ク

図 5，図 6 に本手法で検出した関数クローンの例を示す．

ローンである．図 4 (a) では 9 行目で変数 df を新たに定義

これらは，MeCC では検出することができなかった関数ク

し，それを 10〜12 行目で中間媒介変数として利用していローンである．なお，図中では 2 つの関数の差異を色付ける．一方，図 4 (b) では中間媒介変数を利用せずに実装をして表現している．

行っている．
図 5 は，繰返し処理が置き換わっている例である．図 5 (a)では for 文を用いて繰返し処理を実装しているが，図 5 (b)では while 文を用いてほぼ同一の繰返し処理を実装している．さらに，図 5 (a) では 4〜5 行目で例外の判定が行われているのに対して，図 5 (b) で行われていない．このような文の挿入の有無はバグを含んでいる可能性があると考えられる．
図 6 は，文の並べ替えが発生している例である．図 6 (a)の最初の if 文（赤色のコード片）と 2 番目の if 文（青色のコード片）が図 6 (b) では入れ替わっている．

4. 考察
4.1 本手法の有用性
3 章では，コーパスを用いた評価実験と MeCC との比較実験を行い，高い適合率で検出を行うことができた．3.3 節
では，本手法で検出したタイプ 4 の関数クローンの実例を示した．プログラム依存グラフを用いた検出手法では，
図 6 のような関数は依存グラフそのものが異なってしまう(a) Modules/collectionsmodule.c

ため，検出することができない可能性が高い．一方，本手法では関数を特徴ベクトルに変換するため，文が並べ替えられている関数クローンの検出は容易であるといえる．
また，検出時間の評価では，3 つの C プロジェクトに対して適用し，MeCC より高速に検出を行うことができた．
本手法では特徴ベクトルに対して LSH アルゴリズムを用いたクラスタリングをあらかじめ行っている．そのため，アルゴリズムの時間計算量から，ソースコードの規模に対してほぼ比例に近い時間で検出時間が増えていくと考えられる．評価実験からもソースコードのサイズと検出時間に線形的な関係がある結果が得られた．したがって，100 万行を超える他の大規模ソースコードに対しても十分適用することが可能であると考えられる．
表 7 は，3 つの C プロジェクトに対して不具合を引き起
表 7 不具合を引き起こす可能性があるクローンセットの検出数

Table 7 Number of clone sets including exploitable bug.

(b) Modules/collectionsmodule.c
図 6

文の並べ替えが存在するタイプ 4 の関数クローン（Python）

Fig. 6 Type-4 function clones with reordered statements.

c 2014 Information Processing Society of Japan


本手法

MeCC

Python25

23

Apache HTTPD

35

27

PostgreSQL

53

20

2252

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

ことができるため，それら設定が実験結果に影響している可能性がある．同一の検出オプションを設定できることが望ましいが，本手法と MeCC は異なる検出オプションを持つため困難である．たとえば，本手法では小規模の関数を検出しないためにトークン数の指定し，MeCC ではメモリ（3.2 節参照）の最小サイズ（MinEntry）を指定するが，
図 7 本手法で検出できなかった関数クローン

Fig. 7 Function clones that our approach is not capable of de-

トークン数とメモリのサイズを換算することは難しい．

5. 関連研究tecting.

構文の類似性に着目した手法として，トークンベースのこす危険性があるクローンセットの数を手作業で調査した検出手法や，抽象構文木（ソースコードの構文構造を木構

結果を示している．ここで不具合とは，図 5 (b) のように，造で表したグラフ）を用いた検出手法が存在する．トー

特定の値の場合における条件分岐が欠如していることが原

クンベースの検出手法では，ソースコードをトークン列

因で例外が起きる可能性がある関数クローンを意味していに変換し，共通トークン列をコードクローンとして検出る．MeCC と比較すると，本手法の方がより多くの不具合

する [14], [19]．また，抽象構文木を用いた検出手法では，の候補を検出することができている．これらは，リファク

ソースコードを抽象構文木に変換し，類似した部分木をタリングによって 1 つに集約することによって，その後のコードクローンとして検出する [3], [15]．これらの手法で一貫した修正漏れや不具合の発生を防ぐことができること

は，高速にコードクローンの検出を行うことができるが，ができると考えられる．
また，本手法では字句解析を行い，識別子と予約語の判定を行うだけで，関数を特徴ベクトルに変換することがで

3.3 節で示したタイプ 4 のコードクローンの検出を行うことが困難である．

Yuan らは，類似したトークンを持つメソッドやクラス

きる．したがって，C 言語や Java 言語だけでなく，他のをコードクローンとして検出するツール CMCD [17] を開プログラミング言語についても容易に本手法を適用するこ発している．このツールは，タイプ 4 のコードクローンとができると考えられる．さらに，コンパイルができないを検出することが可能であり，本研究の評価実験で利用

ソースコードに対しても関数クローンの検出を行うことがした Tempero らのコーパス [16] を作成する際に利用され可能である．

ている．しかし，CMCD は定量的な評価が行われておら一方で，本手法ではタイプ 2 のコードクローンを検出でず，ツールも公開されていないため，本研究で提案した手きない場合がある．図 7 は，MeCC などの他の手法で検法と比較することが困難である．そのため，本研究では，出することができたが，本手法で検出できなかった関数ク

検出精度と検出時間について定量的に評価が行われている

ローンの実例である．この例では，変数名の識別子名が 1

MeCC [9] と比較実験を行った．

文字のアルファベット（変数名の頭文字）に置換されていまた，プログラムの処理の類似性に着目した手法として，る．このように，意味を持たない変数名に修正されたタイプログラム依存グラフ（プログラム内の要素間に存在する

プ 2 の関数クローンは，本手法では検出することができな

依存関係を表した有効グラフ）を用いた検出手法が存在す

い．トークンベースなどの既存検出ツールとの併用や，略る．この手法では，ソースコードからプログラム依存グラ語を考慮したワード抽出部分の改善など，さらに手法の改フを構築し，類似した部分グラフを探索することによっ良を行っていく必要がある．

て，タイプ 4 のコードクローンを検出することが可能である [7], [8]．しかし，プログラム依存グラフの比較の計算コ

4.2 評価実験の妥当性
本手法の実装は，現在 Java 言語と C 言語にのみ対応している．そのため，2 つの Java プロジェクトと 3 つの C プ

ストが高く，検出に時間がかかってしまうという問題点がある．また，プログラム言語ごとにプログラム依存グラフを構築する機構を用意する必要性がある．

ロジェクトにのみに対して比較を行うことによって本手法

Marcus らは，クエリとして与えられたソースファイルの有用性を示している．今後，他の言語で実装された多くと類似した部分を，LSI（Latent Semantic Indexing）[10]のプロジェクトに対して適用し，一般性を示す必要がある．

を用いてソースコード全体から検索する手法を提案していまた，評価実験では手作業でコードクローンの判定やタる [20]．彼らが提案する手法はクエリを与える必要がある

イプの分類を行っている．しかし，コーパスを用いた評価ため，本研究の提案手法とは目的が異なる．しかし，提案実験も行っているため一部の検出精度においては信頼でき手法においても LSI を利用し識別子間の潜在的意味を解ると考えられる．

析することで，再現性を向上させることができる可能性が本手法と MeCC はそれぞれ検出オプションを設定する

c 2014 Information Processing Society of Japan


ある．

2253

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

我々の研究グループでは，トークン列が等価なファイル[6]を高速に検出ツール FCFinder を開発を行った [21]．本研
究では，識別子の類似性に着目し，関数単位のコードク[7]

ローンを検出する手法を提案した．本研究が提案する手法
は，2 つの関数に含まれるトークン列が異なっていても，[8]

識別子の集合が類似していれば，それら関数は関数クローンとして検出される．
[9]

6. まとめと今後の課題
本研究では，情報検索技術を利用した関数クローン検出[10]

手法の提案を行った．本手法では，ソースコード中の各ワードに対して重み付けを行い，それらを特徴量として各関数の特徴ベクトルを計算する．そして，特徴ベクトル間[11]の類似度を計算することによって，タイプ 4 の関数クローンの検出を行う．また，LSH アルゴリズムを用いてあらか
じめ特徴ベクトルのクラスタリングを行うことによって，[12]

高速な関数クローンの検出を実現した．
評価実験では，2 つの Java プロジェクトと 3 つの C プ[13]

ロジェクトに対して適用を行い，高い精度で関数クローンを検出することができた．さらに，既存手法である MeCC

[14]との比較を行い，検出数，検出精度，検出時間の観点からも本手法が有益であることを確認することができた．
今後の課題として，以下があげられる．

[15]• LSI や LDA（Latent Dirichlet Allocation）[22] を用いた手法と検出精度と検出時間の観点から比較を行う必
要がある．

[16]

• 類義語や同位語の関係を用いたワードのクラスタリン[17]

グなどを行うことによって，リネームが行われた場合[18]のコードクローンの検出精度を向上させる．

• 他の大規模プロジェクトに対して適用し，本手法の有用性を評価する必要がある．さらに，MeCC 以外の他

[19]のツールとの比較を行う必要がある．
謝辞 本研究は JSPS 科研費 26730036，25220003 の助成を得たものである．

[20]

参考文献

[21]

[1]

[2]

[3]

[4]

[5]

肥後芳樹，楠本真二，井上克郎：コードクローン検出とその関連技術，電子情報通信学会論文誌，Vol.J91-D, No.6,
pp.1465–1481 (2008).
Roy, C.K., Cordy, J.R. and Koschke, R.: Comparisonand evaluation of code clone detection techniques andtools: A qualitative approach, Science of Computer Programming, Vol.74, No.7, pp.470–495 (2009).
Baxter, I.D., Yahin, A., Moura, L., Sant’Anna, M. andBier, L.: Clone detection using abstract syntax trees,
Proc. ICSM ’98, pp.368–377 (1998).
Fowler, M.: Refactoring: Improving the design of existing code, Addison-Wesley Longman Publishing Co., Inc.
(1999).
肥後芳樹，神谷年洋，楠本真二，井上克郎：コードクローンを対象としたリファクタリング支援環境，電子情報通信学会論文誌，Vol.88, No.2, pp.186–195 (2005).

c 2014 Information Processing Society of Japan


[22]

付

Rattan, D., Bhatia, R. and Singh, M.: Software clone detection: A systematic review, Information and Software
Technology, Vol.55, pp.1165–1199 (2013).
肥後芳樹，楠本真二：プログラム依存グラフを用いたコー
ドクローン検出法の改善と評価，情報処理学会論文誌，Vol.51, No.12, pp.2149–2168 (2010).
Komondoor, R. and Horwitz, S.: Using slicing to identify duplication in source code, Proc. SAS ’01, pp.40–56(2001).
Kim, H., Jung, Y., Kim, S. and Yi, K.: MeCC: Memory comparison-based clone detector, Proc. ICSE ’11,
pp.301–310 (2011).
Baeza-Yates, R. and Ribeiro-Neto, B.: Modern information retrieval: The concepts and technology behind Search (2nd Edition), Addison-Wesley Professional(2011).
Yamanaka, Y., Choi, E., Yoshida, N., Inoue, K. andSano, T.: Applying clone change notification system
into an industrial development process, Proc. ICPC ’13,
pp.199–206 (2013).
Indyk, P. and Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality,
Proc. STOC ’98, pp.604–613 (1998).
Andoni, A. and Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Comm. ACM, Vol.51, No.1, pp.117–122 (2008).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder:
A multilinguistic token-based code clone detection system for large scale source code, IEEE Trans. Software
Engineering, Vol.28, No.7, pp.654–670 (2002).
Jiang, L., Misherghi, G., Su, Z. and Glondu, S.:
DECKARD: Scalable and accurate tree-based detectionof code clones, Proc. ICSE ’07, pp.96–105 (2007).
Tempero, E.D.: Towards a curated collection of code
clones, Proc. IWSC ’13, pp.53–59 (2013).
Yuan, Y. and Guo, Y.: CMCD: Count matrix based code
clone detection, Proc. APSEC ’11, pp.250–257 (2011).
Bellon, S., Koschke, R., Antoniol, G., Krinke, J. andMerlo, E.: Comparison and evaluation of clone detection tools, IEEE Trans. Software Engineering, Vol.33,
No.9, pp.577–591 (2007).
Li, Z., Lu, S., Myagmar, S. and Zhou, Y.: CP-Miner:
Finding copy-paste and related bugs in large-scale software code, IEEE Trans. Software Engineering, Vol.32,
No.3, pp.176–192 (2006).
Marcus, A. and Maletic, J.I.: Identification of high-level
concept clones in source code, Proc. ASE ’01, pp.107–
114 (2001).
佐々木裕介，山本哲男，早瀬康裕，井上克郎：大規模ソフ
トウェアシステムを対象としたファイルクローンの検出，
電子情報通信学会論文誌，Vol.J94-D, No.8, pp.1423–1433(2011).
Blei, D.M., Ng, A.Y. and Jordan, M.I.: Latent dirichlet
allocation, The Journal of Machine Learning Research,
Vol.3, pp.993–1022 (2003).

録

3 章において E2LSH が自動決定したパラメータを表 A·1に示す．各パラメータの詳細は，E2LSH のマニュアル（http://www.mit.edu/∼andoni/LSH/manual.pdf ）を参照
されたい．

2254

情報処理学会論文誌

Vol.55 No.10 2245–2255 (Oct. 2014)

表 A·1 E2LSH のパラメータ

井上 克郎 （フェロー）

Table A·1 E2LSH parameters.
プロジェクト名kmL

Apache Ant

12

14

91

ArgoUML

12

14

91

昭和 59 年大阪大学大学院基礎工学研
究科博士後期課程修了（工学博士）．
同年，大阪大学基礎工学部情報工学科

Python

16

22

231

助手．昭和 59〜61 年，ハワイ大学マ

Apache HTTPD

16

22

231

ノア校コンピュータサイエンス学科助

PostgreSQL

16

22

231

教授．平成 3 年大阪大学基礎工学部助教授．平成 7 年同学部教授．平成 14 年大阪大学大学院情山中 裕樹

報科学研究科教授．平成 23 年 8 月より大阪大学大学院情平成 24 年大阪大学基礎工学部情報科

ローンやコード検索等のプログラム分析や再利用技術の研学科卒業．平成 26 年大阪大学院情報究に従事．

報科学研究科研究科長．ソフトウェア工学，特にコードク

科学研究科博士前期課程修了．現在，
株式会社日立製作所に勤務．在学中，
コードクローン管理に関する研究に従事．

崔 恩瀞 （学生会員）
平成 24 年大阪大学大学院情報科学研
究科博士前期課程修了．現在，大阪大学大学院情報科学研究科博士後期課
程 3 年．コードクローン管理やリファ
クタリング支援手法に関する研究に従事．

吉田 則裕 （正会員）
平成 16 年九州工業大学情報工学部知能情報工学科卒業．平成 21 年大阪大学大学院情報科学研究科博士後期課
程修了．同年日本学術振興会特別研究員（PD）．平成 22 年奈良先端科学技
術大学院大学情報科学研究科助教．平成 26 年より名古屋大学大学院情報科学研究科附属組込みシステム研究センター准教授．博士（情報科学）．コード
クローン分析手法やリファクタリング支援手法に関する研究に従事．

c 2014 Information Processing Society of Japan

2255