16
特集●ソフトウェア工学の基礎

情報検索技術に基づく細粒度ブロッククローン検出
横井 一輝

崔 恩瀞 吉田 則裕

井上 克郎

本研究では情報検索技術を利用したブロッククローン (コードブロック単位のコードクローン) の検出手法を提案する．既存研究において関数単位でコードクローンを検出する手法を提案したが，この手法は検出粒度が大きいため検出漏れが起きるという問題点があった．この問題を解決するために，本手法では，ソースコード中の識別子や予約語に利用される単語に対して重み付けを行い，コードブロックから変換された特徴ベクトル間の類似度を求め，ブロッ
ク単位でクローンの検出を行う．この手法は，クラスタリングの手法や特徴ベクトルのデータ構造の工夫を行うこと
により．既存手法と比較して，より小さい粒度でコードクローンを検出することができ，かつ検出時間とメモリ使用量を削減できるという利点がある．また評価実験では，既存のコードクローン検出手法と比較を行い，高速に高い精度で検出を行うことができた．

In this paper, we propose an approach for detecting block clones (i.e., block-level code clones) using information retrieval techniques. In the previous study, we have presented an approach for detecting function
clones. However, the previous approach misses a number of code clones because it only identifies coarsegrained code clones (i.e., function clones). To mitigate this problem, this study proposes an approach that
detects block clones by generating feature vectors for code blocks based on the occurrence of identifiers andreserved keywords and then performing clustering of the generated vectors. Also, we improve a clustering
method and a data structure of feature vectors in the proposed approach. It leads not only the detection offine-grained code clones but also less detection time and low memory consumption, compared to the previous
approach. As a case study, we compared the proposed approach with the existing code clone approaches
and then confirmed the eﬀectiveness of the proposed approach.

に，コードクローンの存在はソフトウェアの保守を困

1 まえがき難にすると言われている．コードクローンに対するソフトウェアの保守における問題のひとつとして，様々な保守や管理の方法が提案されているが，ソース

コードクローンが指摘されている [4]．コードクロー

コードの規模が大きくなるとソースコード中に含まンとは，ソースコード中に含まれる互いに一致またはれるコードクローンも膨大な量となり，手作業でそれ類似した部分を持つコード片のことであり，一般的らを管理することは困難となる．そこで，コードク
ローンを自動的に検出することを目的とした様々なFine-grained Block Clone Detection Based on Information Retrieval Techniques.
Kazuki Yokoi, Katsuro Inoue, 大阪大学大学院情報科学研究科, Graduate School of Information Science andTechnology, Osaka University.
Eunjong Choi, 奈良先端科学技術大学院大学先端科学技術研究科, Graduate School of Science and Technology,
Nara Institute of Science and Technology.
Norihiro Yoshida, 名古屋大学大学院情報学研究科, Graduate School of Informatics, Nagoya University.
コンピュータソフトウェア, Vol.35, No.4 (2018), pp.16–36.
[研究論文] 2018 年 1 月 17 日受付.

コードクローン検出手法が提案されている [11] [23]．
山中らは TF-IDF [3] と LSH [14] を利用することによって，意味的に処理が類似した関数単位のコードク
ローンを検出する手法 (関数クローン検出法) を提案した [32]．コード片単位で検出を行う場合，構文の不完全な部分で終了するコード片など，集約を行うことが困難なコードクローンが多く検出されることがある [33]．一方，関数クローンは処理の内容がまとまっているため，開発者にとって集約の対象になりやすいVol. 35 No. 4 Nov. 201817

コードクローンを検出できる．山中らの手法では，情したアルゴリズムである [18]．また，cross-polytope

報検索技術の一種である TF-IDF [3] を用いて，ソーLSH は TF-IDF を用いた特徴ベクトルのクラスタリ

スコード中の識別子や予約語に利用される単語に対ングに適したアルゴリズムである [2]．これらを組みして重み付けを行う．そして，重み付けに基づいて各合わせた手法を用いることで少ないメモリで高速なク関数を特徴ベクトルに変換し，特徴ベクトル間の類似

ラスタリングが可能となった．2 点目は，特徴ベクト度を計算することによって，関数クローンの検出を行

ルを表現するデータ構造の変更である．TF-IDF をう．また，近似最近傍探索アルゴリズムの一種である

用いた特徴ベクトルが疎 (ほとんどの要素が 0) であ

LSH (Locality-Sensitive Hashing) [14] を用いて，特る性質に着目し，0 以外の要素のみを保持するデータ

徴ベクトルをクラスタリングすることにより，検出の構造として実装した．これにより，メモリ使用量や入高速化を行っている．しかし，山中らの手法では検出出力時間の削減を実現した．上記の工夫を行うこと

粒度が関数単位のため，長い関数内の一部にコードク

で，山中らの関数クローン検出手法より検出粒度が小ローンが含まれた場合，検出漏れが生じる可能性があ

さいにもかかわらず，より高速な検出を実現し，さらる．このような検出漏れを減らすためには，関数単位に大規模な検出対象に対しても適用可能となった．

より小さい粒度で構文上のまとまりがあるコードク

評価実験では，関数クローン検出法 [32] と，字句ローンの検出を行うべきである．

単位のコードクローン検出ツールである CCFinderX

そこで，本研究ではコードブロック単位のコードク[16] の，2 つの手法を検出精度と検出時間の観点から

ローン (ブロッククローン) を検出する手法を提案す比較を行った．3 つの C 言語のプロジェクトに対しる．関数単位より小さい粒度であるコードブロック単て適用した結果，本手法が総合的に高い精度でより多位で検出を行うことで，関数単位では検出できなかっくのコードクローンを検出することができた．また，

たようなコードクローンが検出でき，検出精度が向上

本手法は関数クローン検出法や CCFinderX と比較する．本研究ではコードブロックを，関数と，関数内して高速にコードクローンを検出することができた．

部の if，for，while 文などの中括弧で囲まれた部分とまた，スケーラビリティの評価を行い，1KLOC から定義する．本手法では，まずソースコードに対して構10MLOC までの検出対象において線形的に検出時間

文解析を行い，コードブロックの抽出を行う．そのが増加することを確認した．

後，抽出した各コードブロックに対して TF-IDF を

以降，2 章では，コードクローンと関数クローン検用いて特徴ベクトルに変換し，特徴ベクトル間の類似

出法について述べる．3 章では，本研究で提案するブ度を計算することでブロッククローンの検出を行う．

ロッククローン検出法について述べる．4 章では，本また本手法でも山中らの手法と同様，LSH を用いた手法の評価実験について述べる．5 章では，本研究の特徴ベクトルのクラスタリングを行い，検出の高速化

考察について述べる．6 章では，関連研究について述を行う．

べる．最後に，7 章でまとめと今後の課題について述

しかし，関数単位より小さい粒度で検出を行うため，

べる．

検出時間とメモリ使用量が増大する問題が発生する．
この問題に対応するため，以下の 2 点の工夫を行った．

2 コードクローン

1 点目は，クラスタリング手法の LSH の変更である．

本章では，本研究の背景としてコードクローン，おLSH は様々な応用手法が研究されており，本研究でよび山中らの関数クローン検出法と，その問題点に

は提案手法に適した LSH の検討を行った．その結果，ついて述べる．Roy らはコードクローンの定義としmulti-probe LSH [21] と cross-polytope LSH [2] [30]て，コードクローン間の違いの度合いに基づき以下のを組み合わせた手法 [2] を用いて特徴ベクトルのクラ

4 つのタイプに分類している [26]．

スタリングを行うことを選択した．multi-probe LSH
は，従来の LSH が抱えるメモリ使用量の問題点を改良

タイプ 1

空白やタブの有無，コーディングスタ

イル，コメントの有無などの違いを除き完全に一コンピュータソフトウェア

18
致するコードクローン.
タイプ 2

タイプ 1 の違いに加えて，変数名などのユーザー定義名，変数の型などが異なるコード
クローン.
タイプ 3

タイプ 2 の違いに加えて，文の挿入や削除，変更などが行われているコードクローン．
タイプ 4

類似した処理を実行するが，構文上の図1

長い関数内の一部にコードクローンを含む例

実装が異なるコードクローン．
タイプ 4 のコードクローン間の差異として以下が挙げられる．

• 条件分岐処理や繰り返し処理などの制御構造の実装が異なる．

• 中間媒介変数の利用の有無が存在している．
• 文の並び替えが発生している．

ローンになっている場合に検出することができない．
例えば図 1 のように，長い関数内の一部にコードク
ローンが含まれる場合，検出漏れが生じる可能性がある．

2 つ目は，メモリ使用量が多いという問題点である．関数を特徴ベクトルに変換する方法として関数
クローン検出法は TF-IDF を用いているが，TF-IDF

2. 1 関数クローン検出法

では全関数で出現したワードの種類数が次元数とな

山中らは TF-IDF と LSH を利用することによっるため，特徴ベクトルの次元数が非常に大きくなる傾て，意味的に処理が類似した関数クローンを検出する

向にある．特徴ベクトルは各関数に 1 個ずつ与える手法を提案した [32]．コード片単位でコードクローン

ため，次元数の大きい特徴ベクトルを多数保持するこの検出を行う場合，構文の不完全な部分で終了するとになり，メモリ使用量が大きくなる．また，高速

コード片など，集約を行うことが困難であるコードクに検出を行うために LSH を用いてクラスタリングをローンが多く検出される恐れがある [33]．一方，関数行っているが，LSH は精度を上げるとメモリ使用量

クローンは処理の内容がまとまっているため，開発者が大きくなる特徴がある．よって，大規模プロジェク

にとって集約の対象になりやすいコードクローンがト (Linux Kernel など) に対してコードクローンの検検出できる．また関数クローン検出法は，タイプ 1 か出を行う場合，メモリ不足で検出を完了できない恐れらタイプ 4 までのコードクローンを検出可能である．

がある．

この手法は，まず，入力されたソースコード中のワー
ド (例：予約語，識別子名) に基づいて各関数を特徴

3 提案する検出手法

ベクトルに変換する．そして，特徴ベクトル間の類似

2. 2 節で述べた 2 つの問題点を踏まえ，新たなコー度を求めることによってクローンペア (互いに処理がドクローン検出法の必要性が考えられる．そこで，本類似したクローンの対) の集合をリストとして出力す研究では関数単位より検出粒度を小さくした，コーる．また，類似度の計算の直前に LSH [14] を利用し，ドブロック単位のコードクローン検出法 (ブロックク

特徴ベクトルのクラスタリングを行うことによって，ローン検出法) を提案する．ブロッククローン検出法

検出の高速化を行っている．

では，関数クローン単位では検出できなかったコード
クローンの検出が可能になる．例えば図 1 のように，

2. 2 関数クローン検出法の問題点

長い関数内の一部にコードクローンが含まれる場合

関数クローン検出法に対して以下の 2 つの問題点

も，提案手法では検出が可能である．また，字句単位が挙げられる．

の検出より処理の内容がまとまっているため，開発者

1 つ目は，関数単位の検出による問題点である．こにとって集約などの保守作業の対象となりやすい．以の手法は，関数全体ではなく，一部のみがコードク上の観点から本手法には有用性があると考えられる．

Vol. 35 No. 4 Nov. 2018

図219

提案手法の概要

本研究では，2. 1 節で説明した山中らの関数クローン検出法をもとに，タイプ 1 からタイプ 4 すべてに対応したブロッククローン検出法を提案する．本手法の概要を図 2 に示す．本手法は主に以下の 5 つのステップで実行される．

• 特徴ベクトルをクラスタリングする手法の選択と実装• 特徴ベクトルを表現するデータ構造の選択と実装
主な相違点はコードクローンの検出粒度を小さくした点である．本手法では関数単位だけでなく，関数

ソースコードから抽象構文木を生成し，内のコードブロック単位の両方のコードクローンを生成した抽象構文木からコードブロック (3. 1. 1検出する．検出粒度を関数より小さくすることで，検節参照) を取り出す．

出精度の向上を実現した (4. 1 節参照)．しかし，検出

STEP 1

STEP 2

STEP 1 で抽出した各コードブロック

から，ワード (3. 1. 2 節参照) の抽出を行う．

STEP 3

TF-IDF を利用し，STEP 2 で抽出したワードに重み付けを行い，各コードブロックを特徴ベクトルに変換する．

粒度を小さくすると検出対象数が増加し，それに伴い検出時間とメモリ使用量が増大する問題が新たに発生する．この問題に対処するため，さらに 2 つの変更を適用した．
まず，特徴ベクトルのクラスタリングを行う LSH

LSH を利用し，STEP 3 で求めた各を変更した．関数クローン検出法でも LSH を用いて

コードブロックに対する特徴ベクトルのクラス

特徴ベクトルのクラスタリングが行われており，こタリングを行う．

れにより高速な検出を実現している．しかし，近年

STEP 4

STEP 4 で求めたコードブロックの各

LSH は様々な応用手法が研究されており，関数クロー

クラスタの中で，特徴ベクトル間の類似度の計算

ン検出法では LSH の応用手法の検討まではされていを行い，ブロッククローン (3. 1. 3 節参照) を検ない．また，LSH によるクラスタリングが占める時出する．

間の割合が大きく無視できないため [31]，本手法に適STEP 5

本手法と関数クローン検出法の相違点は，以下の 3点である．

• コードクローンの検出粒度した LSH の検討を行った．その結果，multi-probe

LSH [21] と cross-polytope LSH [2] [30] の 2 つの既存手法を組み合わせる手法 [2] に変更した．multi-probeコンピュータソフトウェア

20

LSH とは，空間計算量の改良を行った LSH である．
また，cross-polytope LSH とは，角度距離に基づいてハッシュ化を行う LSH である．角度距離に基づいた cross-polytope LSH は TF-IDF を用いた特徴ベク
トルのクラスタリングが高速に行える．multi-probe

LSH を cross-polytope LSH に組み合わせることで，
図3より少ない空間計算量でより高速にクラスタリングが可能となることが示されている [2]．

入れ子構造において親子関係にある
コードブロック

さらに，特徴ベクトルを表現するデータ構造を変更

ただし，後に ‘{ }’ が現れない単文の命令文はコードした．特徴ベクトルは，検出対象数の増加に伴いベクブロックとしてのまとまりがないため検出対象としなトルの次元が高次元になる性質があり，次元が高次元

い．また図 3 の Block A に対する Block B や Blockになるほどメモリ使用量とベクトルの計算時間が増

C のように，入れ子構造における親を持つコードブ

大する．関数クローン検出法では，特徴ベクトルのロックを検出可能であり，検出対象を再帰的に探索すべての要素の値を保持するデータ構造をしている．

する．

関数単位の検出では問題がないが，検出粒度を小さくしコードブロック単位で検出を行うには，上記の高次元の問題が無視できなくなる．そこで，本手法のよう

3. 1. 2 ワード
本手法では以下の条件 2-1，2-2 のいずれかを満たすものをワードとして定義する．

に TF-IDF を用いた特徴ベクトルでは，ほとんどの

条件 2-1

予約語

要素が 0 である疎なベクトルとなる性質に着目し，非条件 2-2

識別子名を構成する単語

0 要素のみを保持するデータ構造を選択した．データ

識別子名が複数の単語から構成される場合，以下の構造を疎なベクトルとして実装することで，メモリ使用量や計算時間，さらに入出力時間の削減を行った．
以上の変更により，関数クローン検出法と比較して検出粒度は小さくなったにもかかわらず，より高速な検出を実現し，さらに大規模な検出対象に対しても適用可能となった．

方法でワード単位に分割する．

• ハイフンやアンダースコアなどの区切り記号による分割• 識別子名中の大文字になっているアルファベッ
トによる分割また，2 文字以下の識別子は，それらをまとめて同一のメタワードとして扱う．例えば，繰り返し文などで

3. 1 用語の定義

よく利用される i や j といった変数は，意味情報が込

3. 1. 1 コードブロック

められていない変数として扱うためである．さらに，

本研究では，プログラミング言語において，複数の条件分岐に用いられる if や while，繰り返しに用いら

命令文を一括りにまとめたものをコードブロックとれる for や while などの予約語もワードとして扱う．

いう．多くのプログラミング言語では，コードブロッ

なお，各ワードの大文字と小文字による区別はつけ

クを入れ子構造にすることができ，変数のスコープとず，同一のワードとして扱う．

しての意味を持つことがある．

3. 1. 3 ブロッククローン

本手法では，以下の 2 つの条件のいずれかを満た本手法におけるブロッククローンについて説明すすコードブロックを検出対象とする．対象言語は Cる．最初にブロッククローンペアについて定義する．

言語と Java 言語とする．

本手法では，以下の条件 3-1，3-2 の両方を満たすコー

条件 1-1関数の ‘{ }’ で囲まれた範囲

条件 1-2

if，else，for，while，do-while，switch

文の ‘{ }’ で囲まれた範囲

ドブロック対を，ブロッククローンペアと呼ぶ．
条件 3-1

コードブロック間の類似度が閾値以上

sim(CB1 , CB2 ) ≥ p(0 ≤ p ≤ 1)

Vol. 35 No. 4 Nov. 201821

文木から関数 (3. 1. 1 節の条件 1-1 を満たすコードブ
ロック) の部分木を取り出し，コードブロックとして抽出する．そして，取り出した部分木から，コード
ブロック (3. 1. 1 節の条件 1-2 を満たすコードブロック) の部分木を取り出し，関数の内側に存在するコードブロックを抽出する．コードブロックの抽出後，各
図4

条件 3-2

極大コードブロックペアと重複した
コードブロックペア

入れ子構造において，CB1 が CB2 の親でなく，かつ CB2 が CB1 の親でない

コードブロック内に含まれるワードの抽出を行う．

3. 3 特徴ベクトルの計算
特徴ベクトルの計算では，ワードに対し TF-IDF

次に極大ブロッククローンについて定義する．CB1 ，[3] を利用して重みを計算し，その値を特徴量として

CB2 がブロッククローンペアであり，かつ CB1 ，CB2

各コードブロックを特徴ベクトルに変換する．よっそれぞれを真に包含する如何なるコードブロックもて，各コードブロックの特徴ベクトルの次元数はソーブロッククローンペアでないとき，CB1 ，CB2 を極

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

大ブロッククローンと呼ぶ．本手法では，極大ブロッ法では，tf 値はコードブロック中のワードの出現頻度

ククローンをブロッククローンと定義する．条件 3-2を，idf 値はソースコード中のワードの希少さを表しで示したように，ブロッククローンペアはコードブている．tf 値は式 (1)，idf 値は式 (2) で与えられる．

ロック間に入れ子構造における親子関係がないこと

ni,jtf i,j = ∑が条件である．コードブロック間に入れ子構造におk∈bj

ける親子関係が存在する場合，一方のコードブロッ

idf i = log

クが他方を包含していることを示している．例えば，

nk,j

|F |
|{f : f ∋ wi }|

(1)

(2)

図 3 のコードブロック A と B は親子関係が存在し，ここでは，ni,j はコードブロック bj 内におけるワー

包含関係にあるためブロッククローンペアでない．

ド wi の出現回数，

∑

k∈bj

nk,j はコードブロック bj

また，極大ブロッククローンをブロッククローンとにおける全ワードの出現回数の和，|F | は全関数の数，定義するとは，言い換えるとそれぞれ入れ子関係にあ|{f : f ∋ wi }| はワード wi が出現する関数の数を示

るコードブロックの類似度が閾値以上の場合，最も外

している．

側のコードブロックペアをブロッククローンとする関数クローン検出法と比較して，tf 値の求め方をという意味である．例えば，図 4 のコードブロック

コードブロック単位に変更したが，idf 値の求め方はA と C，B と D それぞれの類似度が閾値以上となる

コードブロック単位に変更せず関数単位のままであ場合，最も外側のコードブロック A と C をブロックる．なぜなら，コードブロック単位で idf 値を求める

クローンとする．

とワードの重み付けに偏りが生じてしまうからである．あるワードがいくつのコードブロックに含まれる

3. 2 コードブロックとワードの抽出

かは出現場所によって異なる．例えば，図 3 の関数

本手法でのコードブロックとワードの抽出につい内の変数 a はブロック A と B の 2 個のコードブロッて説明する．最初にソースコードに対して構文解析

クに含まれるが，変数 b はブロック A のみにしか含を行い，抽象構文木を生成する．本手法では，構文解
析には ANTLR v4 †1 を利用する．次に生成した抽まれない．そのため，ソースコード中の出現回数は同

象構文木に対して深さ優先探索で検索する．抽象構

なってしまう．idf 値はワードの希少性に基づいて重じにもかかわらず，出現するコードブロックの数が異み付けを行っているため，偏りを無くすために関数単†1 http://www.antlr.org/

位で求めた．

コンピュータソフトウェア

22

また，TF-IDF を用いた特徴ベクトルは，非常に高次元かつ疎となる特性がある．そのため，非 0 要素

出法ではユークリッド空間に対する LSH を実装した
E2LSH [1] †2 を用いてクラスタリングを行い検出ののみを保持する疎ベクトルとして実装することでメ高速化を実現しているが，他の LSH の検討までは行

モリ使用量の効率を改善した．さらに，特徴ベクトル

われていない [32]．そこで本研究では，本手法によりの外部記憶装置への入出力処理の時間を高速化した．

適した LSH の検討を行った．
一般的に LSH を用いて大規模のデータセットを高3. 4 特徴ベクトルのクラスタリング

い精度で求めようとすると，メモリ使用量が非常に大特徴ベクトルのクラスタリングとして，近似最近傍きくなるという問題点がある [18] [21]. そこで，メモリ探索の一種である LSH [14] を用いた．LSH とは，高使用量を改良するため multi-probe LSH [21] という次元なデータを確率的にハッシュ化し，近似的に近傍手法が提案されている．LSH のアルゴリズムは，空点を見つけるアルゴリズムである．クローンペアと間的に距離が近い 2 点が同じハッシュ値になる確率

なる特徴ベクトルは近傍点で表されるため，LSH をが高くなるようなハッシュ関数を用い，同じハッシュ用いてクラスタリングすることで類似した特徴ベク

値を取る点を同じバケットに入れることで近傍点の検トルを高速に絞り込むことができ，クローン検出の高索を行う．しかし LSH は確率的手法であるため，近速化を実現している．

い 2 点が偶然に別のバケットに入る可能性が存在す

最 初 に ，LSH の 一 般 的 な 説 明 を 述 べ る ．LSHる．従来の LSH では複数のハッシュテーブルを用いは，(c, r)-Approximate Nearest Neighbor (ANN) と，ることで確率的な誤差を少なくし精度を上げている．

(r, cr, p1 , p2 )-sensitive hash を 用 い て 表 さ れ る ．

そのため，大規模なデータセットに対してはより多数(c, r)-ANN とは，近似最近傍探索の問題定義であのハッシュテーブルが必要となり，LSH のメモリ使り，(r, cr, p1 , p2 )-sensitive hash とは，空間的に距離用量の増大につながっている．multi-probe LSH は，が近い点が同じハッシュ値を取る確率が高くなる確率

ある点が入るバケットだけでなく，空間的に距離が近的ハッシュ関数である．(c, r)-ANN と，(r, cr, p1 , p2 )-いバケット群も調べるという手法である．これによsensitive hash の定義を以下に示す．

り，少ないハッシュテーブルでも偶然別のバケットにd

R 上に距離関数 D を定義する．

入った点の見落としを防いでいる．実際に，192 次元

実数 c > 1，実数 r > 0，任意のクのデータセットに対して同じ再現率 (0.90) を得るたd

エリ q ∈ R が与えられたとき，p ∈ R を q のめに，従来の LSH は 49 個のハッシュテーブルが必

正解最近傍点とし，D(p, q) < r ならば，要だったのに対し，multi-probe LSH は 3 個のハッ(c, r)-ANN
d

′

{ ′

′

P = p ∈ R : D(p , q) < cr
d

d

}

′

で定義される R の部分集合 P を求める問題を(c, r)-ANN と呼ぶ．
(r, cr, p1 , p2 )-sensitive hash

シュテーブルで検索時間をほぼ落とさずに達成したという結果が示されている [21]．
本手法では，TF-IDF を用いた特徴ベクトルに対し，任意の点 p, q ∈コサイン類似度によって類似したベクトルの検索を行

d

うが (3. 5 節参照)，これらは情報検索の分野でよく用• if D(p, q) < r then Pr[h(p) = h(q)] ≥ p1

いられる手法であり，上記のようなベクトル空間に対• if D(p, q) > cr then Pr[h(p) = h(q)] ≤ p2

する LSH がいくつかある．その中で，角度距離に基を満たすハッシュ関数 h を (r, cr, p1 , p2 )-sensitive

づいてハッシュ化を行う cross-polytope LSH [2] [30]hash と呼ぶ．Pr は条件式が真となる確率を表し

が，理論的に保証されており計算時間の観点から実用

R が与えられたとき，ている．
ここでは一般的な LSH で用いられる定義を示し的な手法として提案されている．cross-polytope LSH
は，実用性の面で優れているとして既に提案されていたが，上記のハッシュ関数 h を変更するなど様々な

LSH の応用手法が提案されている．関数クローン検†2 http://www.mit.edu/∼andoni/LSH/

Vol. 35 No. 4 Nov. 201823

た hyperplane LSH [6] と比較し，1.2 倍から 4.0 倍高

比較対象として選び評価した．4. 4 節の検出時間とス

速に同じ精度で検索できるという結果が示されておケーラビリティの評価では，本手法の有用性を確認す

り，さらに TF-IDF を用いた特徴ベクトルの場合はるため，上記の 2 つに加えて，抽象構文木を用いた検少なくとも 3 倍高速になるという結果も示されてい出法の Deckard [15]，プログラム依存グラフを用いた

る [2]．

検出法の Scorpio [9] [10] の 2 つを比較対象として追Andoni らは multi-probe LSH を cross-polytope

加して評価した．さらに 4. 7 節では，同じコードブ

LSH に組み合わせた手法 [2] を提案しており，このロック単位の検出手法として，粗粒度なコードクロー
ン検出法 [13] を対象とした比較実験も行った †4 ．な

2 つの LSH を組み合わせた手法を本研究では選択した．なお，2 つの手法の組み合わせの実装として
FALCONN [2] †3 ライブラリを利用した．

おブロッククローンを検出する閾値は，本実験では関数クローン検出法の論文に基づき，0.9 と設定し検出を行った [32]．

4. 1 節の評価実験においては，検出結果が正しく

3. 5 特徴ベクトルの類似度の計算
本手法ではコサイン類似度を用いてクローンペアの

コードクローンであるか目視で判断するだけでなく，判定を行う．コサイン類似度は多次元ベクトルの類似

実際に保守対象となり得るかコードクローンの研究者

度を表す尺度であり，次元が V である 2 つの特徴ベ
クトル ⃗a, ⃗b 間の類似度は以下の式 (3) で与えられる．

にアンケートを行うことで検出精度を評価した．し

∑|V |
ab
i=1 i i√∑sim(⃗a, ⃗b) = cos(⃗a, ⃗b) = √∑なく，ソフトウェアを保守管理するという観点から実

|V |
a2
i=1 i

たがって，単にコード片が外見上類似しているだけで際に有用なコードクローンの評価方法となっている．
|V |
b2
i=1 i

検出されたコードクローンがどの程度保守の対象にな(3)

るのかは実際の開発で利用する際に非常に重要とな

TF-IDF の計算式より，特徴量は常に正の値を取る

る．既存の研究ではあまり評価されていなかったが，ため，コサイン類似度は 0 から 1 の範囲となる．コ

本研究ではこの面についても評価した．

サイン類似度が閾値以上であれば，それら 2 つのコードブロックはクローンペアであると判定する．閾値
は実行時の引数によって与えられる．

4. 1 関数クローン検出法と CCFinderXとの比較
本節では関数クローン検出法と CCFinderX の 2 つ

4 評価実験

の既存手法との比較実験について述べる．コードク

本章では，本研究で提案したブロッククローン検出

ローンに対する保守作業として，集約や同時修正が挙法の評価実験について述べる．評価実験では，検出精げられる．そのため，今回は集約または同時修正の保度，検出時間，スケーラビリティの 3 つの観点から，本†4 本実験において，本手法では最小一致トークン数を30，類似度を 0.9 に，関数クローン検出法では最小一致トークン数を 30，類似度を 0.9 に，CCFinderXでは最小一致トークン数を 50，最小トークンタイプ
数は 12 に，Deckard では最小一致トークン数を 50，
類似度を 0.85，トークンストライドを 2 に，Scorpio
では最小一致ノード数を 7 に，粗粒度なコードク
ローン検出法では最小一致トークン数を 50 と設定した．本手法と関数クローン検出法の各パラメータは既存研究で信頼性が高いと示された値を採用した [32].
CCFinderX，Deckard の各パラメータは既存の実験で実際に用いられた値を採用した [27]. Scorpio のパラメータは既存研究を参考に設定した [10]．粗粒度な
コードクローン検出法のパラメータは CCFinderX を参考に設定した．

手法と既存手法の比較を行い評価した．また，保守対象とならないコードクローンと，コードクローンに対する保守作業の調査も行った．最後にブロッククローンの実例を示し，本手法の特徴について考察する．

4. 1 節の本手法と既存手法の検出精度の評価では，本手法の拡張元であり検出粒度が異なる関数クローン検出法と，高速かつスケーラビリティの高い字句単位の検出法の中で代表的である CCFinderX [16] を†3 https://falconn-lib.org/

コンピュータソフトウェア

24

表1

検出対象プロジェクト

プロジェクトバージョン

Apache HTTPD†5
PostgreSQL†6
Python†7
表2

検出手法

本手法

言語

規模

2.2.14C/C++

343 KLOC

8.5.1

C/C++

937 KLOC

2.5.1

C/C++

435 KLOC

検出精度の評価

検出対象

適合率

再現率

F値

Apache HTTPD

0.90

0.74

0.81

PostgreSQL

0.57

0.87

0.69

Python

0.90

0.53

0.67

合計

0.68

0.70

0.69

Apache HTTPD

0.87

0.53

0.66

関数クローン

PostgreSQL

0.83

0.74

0.78

検出法

Python

0.30

0.21

0.25

合計

0.67

0.47

0.55

Apache HTTPD

0.70

0.55

0.62

PostgreSQL

0.13

0.33

0.19

Python

0.87

0.63

0.73

合計

0.57

0.52

0.54

CCFinderX

守対象となるコードクローンを検出できるかというクローンかの判断を行い，ベンチマークを作成．

観点で検出精度を評価した．本実験では，対象プロ

なお，ベンチマークに客観性を持たせるため，アン

ジェクトから作成したベンチマークに対する検出精

ケートにより第三者にコードクローンの判断を依頼

度と検出時間の観点から比較を行う．本実験で検出した．アンケートの概要を以下に示す．

対象としたプロジェクトの一覧を表 1 に示す．

調査対象

以下の 3 名に依頼

4. 1. 1 ベンチマークの作成方法• コードクローンの研究者 1 名

ベンチマークの作成は以下の 3 ステップで行った．

• コードクローンの研究に従事している大学

1. 表 1 のプロジェクトに対し，本手法，関数ク
ローン検出法，CCFinderX の 3 つの手法でコー
ドクローンを検出．

2. 各手法が各プロジェクトから検出したクローン

院生 2 名
質問内容

集約または同時修正の保守対象とな

るか
回答方式

二択 (はい/いいえ)

ペアから，30 個のクローンペアをランダムサン

上記の質問を，検出結果からサンプリングした 270 個

プリングし，合計 270 個のクローンペア集合をのクローンペアに対して行った．そして，過半数で作成．

ある 2 人以上が保守対象と回答したクローンペアを

3. 2 で作成した 270 個のクローンペアに対し，目正解とし，本実験で用いる正解クローンペア集合と視で集約または同時修正の保守対象となるコード

してベンチマークを作成した．これはアンケートの†5 http://httpd.apache.org/†6 http://www.postgresql.org/†7 http://www.python.org/

結果が個人の判断に依存しないようにするためである. 本実験では，各プロジェクトの正解クローンペア
数は，Apache HTTPD が 74 個，PostgreSQL が 46

Vol. 35 No. 4 Nov. 2018
個，Python が 62 個となった．

25

CCFinderX より低い再現率となった．3 つのすべて

4. 1. 2 比較結果のプロジェクトの合計では，再現率は 0.70 であり，

本節では，関数クローン検出法と CCFinderX との関数クローン検出法と CCFinderX より再現率が高い

比較実験の結果について述べる．本実験では，ベンチことが確認できた．

マークを用いた検出精度と検出時間の観点から比較

Python において再現率が低くなった原因として，を行った．検出精度の指標として，適合率，再現率，Python にタイプ 2 のコードクローンが多く含まれる

F 値の 3 つの指標を用いた．本実験における 3 つのことが確認できた (表 5 参照)．表 5 は，検出対象ご指標を表 2 に示す．それぞれの手法と比較して，最とのタイプ別の正解クローン数を示している．本手も高い値を太字で示している．

法は識別子名に基づいて検出を行うため，識別子名の適合率

変更を伴うタイプ 2 のコードクローンの検出は不得

適合率とは，検出結果に対して真に正しかった割合

手である．

を指し，正確性に関する指標として用いられる．本F値

実験では，各 30 個ずつランダムサンプリングしたク

F 値とは，適合率と再現率の総合的な評価として用

ローンペア集合に対して，アンケートにて保守対象

いられ，適合率と再現率の調和平均によって求めらとなるコードクローンと判断されたクローンペアのれる．

割合によって適合率を求めた．今回は過半数である 2

本手法では，Apache HTTPD において F 値が 0.81

人以上がコードクローンと判断した場合を正解としであり，関数クローン検出法や CCFinderX より高いている．

F 値が得られた．PostgreSQL においては F 値が 0.69

本手法では，Apache HTTPD と Python においであり，CCFinderX よりは高い F 値が得られたが，て，関数クローン検出法や CCFinderX より高い適関数クローン検出法より低い F 値となった．また，合率が得られた．また，PostgreSQL においては，

Python においては F 値が 0.67 であり，関数クロー

CCFinderX よりは高い適合率が得られたが，関数クン検出法よりは高い F 値が得られたが，CCFinderX

ローン検出法より低い適合率となった．3 つのすべてより低い F 値となった．3 つのすべてのプロジェクのプロジェクトの合計では適合率は 0.68 であり，関トの合計の F 値は 0.69 であり，関数クローン検出法

数クローン検出法と同程度の適合率，CCFinderX よと CCFinderX より F 値が高いことが確認できた．

り高い適合率であることが確認できた．

検出時間

本手法が PostgreSQL において適合率が低くなっ

検出時間の比較では，表 1 の 3 つのプロジェクトた原因として，出力処理の連続，同じ識別子の多用，に対する検出時間を測定した．本実験の実行環境は，

2 文字以下の変数の多用，if 文の連続のクローンが多

CPU Intel Xeon 2.80GHz 4core，メモリ 16GB，ハー数あることが確認できた．

ドディスクドライブ，OS Windows 10 64bit である．

再現率

検出時間の比較結果を表 3 に示す．本手法では，検再現率とは，正解集合に対して実際に検出された割

出対象すべてのプロジェクトに対して 3 分以下でコー合を指し，網羅性に関する指標として用いられる．本ドクローンを検出できた．また，関数クローン検出法

実験では，アンケートによって作成したベンチマークに対して 3∼4 割程度，CCFinderX に対して 4∼8 割の正解集合に対し，各手法が検出したクローンペアの程度と，他の手法よりも短時間で検出することが確認

割合によって再現率を求める．

できた．

本手法では，Apache HTTPD，PostgreSQL において，関数クローン検出法や CCFinderX より高い

4. 1. 3 ベンチマークに含まれたコードクローンのタイプ

再現率が得られた．また，Python においては，関

本節では，ベンチマークにおいて保守対象と回答さ数クローン検出法よりは高い再現率が得られたが，れたコードクローンのタイプ別の個数について説明コンピュータソフトウェア

26

表3

検出時間の比較

検出対象

本手法

関数クローン検出法

CCFinderX

Apache HTTPD

1m 39s

4m 7s

2m 1s

PostgreSQL

2m 27s

8m 47s

5m 30sPython

1m 15s

3m 33s

3m 10sする．4. 1. 1 節で実施した，各ツールの検出結果から

続」，「同じ識別子の多用」，「出力処理の連続」が原因

サンプリングしたコードクローンに対するアンケー

として確認できた．特に「2 文字以下の変数の多用」

トにて，保守対象と回答したコードクローンのタイプと「同じ識別子の多用」は，本手法の識別子名に基づ(タイプ 1 からタイプ 4) の調査を各回答者に行った．

いた検出に起因する．本手法では 2 文字以下の変数

その結果に基づき，各手法が検出した正解クローン

を同一のメタワードに置換している．そのため，2 文のタイプ別の個数と誤検出数を表 4 に示す．今回は，字以下の変数が多用されている場合，同一のワードが保守対象と回答された検出を正解クローン，保守対象

頻出していると判断し，誤検出の原因となる．また，と回答されなかった検出を誤検出とする．なお，回答

一般的によく使用される識別子名の場合，処理内容が者によって回答が異なる場合，第 1 著者が最終的な異なっていても同じ識別子名が用いられる傾向があ判断を行った．

る点も，誤検出の原因になる．

これより，本手法と関数クローン検出法が実際にタ関数クローン検出法では「ツールの不具合」が原因

イプ 1 から 4 まで検出可能であることが確認できた．

として多く確認できた．これは C 言語のマクロの処

また，CCFinderX はタイプ 1 と 2 が検出可能であり，理が適切に行われていない点に起因する．本手法ではタイプ 3 と 4 は検出できないことが確認できた．表 4

マクロの処理を適切に行えているため，ツールの不具は各ツールの検出結果から 90 個ずつ抽出した結果の合を原因とした誤検出は今回出現しなかった．また，内訳であり，各タイプの検出数は母集団 (各ツールの処理の内容は異なるが，二重の繰り返し構文の構造を検出結果) に含まれる絶対数ではないことに注意され内部に持つ関数も誤検出として見られた．

たい．例えば，表 4 において，CCFinderX のタイプ

CCFinderX では case 節やコードの断片，if 文や代

1 より本手法のタイプ 1 の数が多いが，CCFinderX

入文の連続の原因による誤検出の例が目立ち，これらと比べて本手法がより多くのタイプ 1 を検出結果には Higo らの指摘と同様の結果が得られた [12]．本手含んでいることを表していない．

法ではコードブロック単位での検出を行うため，case
節やコードの断片といった保守作業の対象となりに

4. 2 保守対象と判定されなかったコードクローンの調査
本節では，4. 1 節で実施したアンケートにて，ツー

くい誤検出は今回出現しなかった．
また，太字で表記した「if 文の連続」は 3 つの手法で共通して確認できた．

ルによって検出されたが保守対象とならないと回答されたコードクローンについて説明する．今回はアン

4. 3 コードクローンに対する保守作業の調査

ケートにて，3 人中 1 人以下が保守対象となると回答

本節では，コードクローンと実際に適用する保守作

した検出を誤検出とする．本手法，関数クローン検出業の関連性について，本手法，関数クローン検出法，法，CCFinderX の 3 つの手法にて誤検出した 88 個

CCFinderX の 3 つの手法との比較を行う．今回は，のコードクローンを調査し，原因を考察した．その結

4. 1 節で実施したアンケートにて 3 人中 2 人以上が保果を表 6 に示す．今回は複数回出現した原因を手法

守対象となると判定したコードクローンに対し，どのごとに掲載している．

ような保守作業を適用できるかについて以下のアン

本手法では「2 文字以下の変数の多用」，「if 文の連

ケートを行った．

Vol. 35 No. 4 Nov. 2018表427

ベンチマークに含まれたコードクローンのタイプ別内訳

検出手法

T1

T2

T3

T4

誤検出

合計

本手法

9

34

27

1

19

90

関数クローン検出法

5

29

25

1

30

90

CCFinderX

4

47

0

0

39

90

表5

ベンチマークに含まれたコードクローンの内訳 (検出対象ごと)

Apache HTTPD

PostgreSQL

Python

検出手法

T1

T2

T3

T4

T1

T2

T3

T4

T1

T2

T3

T4

本手法

4

14

8

1

4

10

3

0

1

10

16

0

関数クローン検出法

1

14

11

0

3

12

10

0

1

3

4

1

CCFinderX

2

19

0

0

2

2

0

0

0

26

0

0

表6

保守対象と判定されなかったコードクローン

本手法

関数クローン検出法

CCFinderX2 文字以下の変数の多用

if 文の連続case 節の断片

if 文の連続同じ識別子の多用

if 文の連続出力処理の連続

処理内容が異なる繰り返し構文の入れ子構造

コードの断片同じ識別子の多用

ツールの不具合

代入文の連続調査対象

4. 1 節で実施したアンケートと同様

いても集約のみの対象と判断されたクローンペアは 0

質問内容

どのような保守作業の対象となるか個であった．

回答方式

三択 (複数回答可)関数クローン検出法と比較して，保守作業の割合は• 集約同じであるが，保守対象となる検出数が増加してい• 同時修正る．関数単位の検出法では集約の対象となりやすい• その他 (自由回答形式)

点が長所として挙げられている．本手法では検出粒結果を手法ごとに分けて図 5 に示す．なお，回答者

度をコードブロック単位に小さくしたが，関数単位によって異なる保守作業が適用された場合，両方の保の検出と保守作業の割合は変わらず，さらに保守作

守作業を適用できることとする．また，その他の保守業の対象となりやすい傾向にあることが確認できた．

対象と判断されたクローンペアについては，回答者とまた CCFinderX と比較して，同時修正の対象数は同

相談し同時修正の対象に含めた．

程度であるが，集約と同時修正両方の対象数は増加し本手法では 90 個中 71 個のクローンペアが保守対ている．字句単位の検出法では集約を行うことが困象と判断された．その内，36 個が同時修正の対象，35

難なクローンが多く検出される点が指摘されていた．

個が集約と同時修正の対象となった．関数クローン

本手法では処理内容にまとまりを持ったコードブロッ

検出法では 90 個中 60 個のクローンペアが保守対象

ク単位の検出を行うため，字句単位の検出法より集と判断された．その内，29 個が同時修正の対象，31

約の対象となりやすい傾向にあることが確認できた．

個が集約と同時修正の対象となった．CCFinderX で

以上より字句単位の検出法より集約の対象となりやは 90 個中 51 個のクローンペアが保守対象と判断さすく，また関数単位の検出法より保守作業の対象となれた．その内，35 個が同時修正の対象，16 個が集約りやすいと言える．

と同時修正の対象となった．また，いずれの手法におコンピュータソフトウェア

28

プ領域を 15GB と設定して実行した．
検出時間の評価結果を表 7 に示す．これにより，10MLOC 規模の検出対象に対して CCFinderX は検出に約 2 時間かかり，関数クローン検出法ではメモ
リ不足で終了したのに対し，本手法では約 30 分で検出可能であることが確認できた．また，1KLOC から

10MLOC の検出規模に応じて線形的に検出時間が増加することも確認できた．
図5

ベンチマークに含まれたコードクローン
に対する保守作業

表 7 より，本手法は関数クローン検出法や CCFind-

erX より高速に検出できることが確認できた．また，
10MLOC 規模のプロジェクトに対して約 30 分で検出できることも確認できた．特徴ベクトルの次元を d，特徴ベクトル集合の大きさを n とした時，クローン検
出にかかる時間は O(dn2 ) である．しかし，LSH を用いてクラスタリングを行うことで，クローン検出時間
は O(dnρ+1 ) となる．ρ は LSH の鋭敏性を示す値で，LSH に適切なパラメータを与えることで，ρ ≤ 0.2 に
図6

本手法のタイプ別の保守作業抑えることができる [2]．よって O(dnρ+1 ) < O(dn2 )となり，時間計算量は少なくなる．関数クローン検出

さらに，本手法においてタイプ別に適用される保守法と比較して本手法は検出粒度を下げているため n

作業の調査を行った．結果を図 6 に示す．これより，が大きくなるが，LSH を用いることで検出にかかるタイプ 1 は集約と同時修正のどちらの対象にもなり

時間計算量の増加を抑えている．さらに，LSH の実

やすく，タイプが上がるにつれて集約の対象にはなり装に用いた FALCONN は高速に LSH を計算できるにくいことが分かった．

ように実装されたツールであり，クラスタリングを行
うツールの変更が検出の高速化の主な要因であると

4. 4 検出時間とスケーラビリティの評価考えられる．また，特徴ベクトルを表現するデータ構

本節では，提案手法の検出規模ごとの検出時間と造を疎ベクトルとして実装したことにより入出力時

スケーラビリティの評価について述べる．検出対象間の短縮につながった．入出力時間が検出全体で占の規模の指標にはコメントや空行を除いた LOC を用いることとした．LOC の計測には cloc †8 を用いめる割合も大きいため，特徴ベクトルのデータ構造の変更も検出の高速化に貢献している．

た．検出対象は，IJaDataset 2.0 †9 からランダムに

また表 7 より，検出規模に応じて線形的に検出時ファイルを選択し，表 7 に示した LOC ごとのサブ間が増加することも確認できた．これに関しては，本セットシステムを作成した．IJaDataset とは，2 万以

手法や関数クローン検出法ではコードブロック，関数

上の Java プロジェクトから成る，365MLOC のビッの抽出，CCFinderX では字句の抽出にかかる時間の

グデータセットである．本実験の実行環境は，CPU割合が全ステップ中で多いため，検出規模に応じて線Intel Xeon 2.80GHz 4core，メモリ 32GB，ソリッド

形的に時間が増加すると考えられる．CCFinderX は

ステートドライブ，OS Windows 10 64bit である．

字句の抽出にかかる時間が長いため，本手法の方が高

また，Java 仮想マシンのスタック領域を 1GB，ヒー

速に検出することができた．

†8 http://cloc.sourceforge.net†9 http://secold.org/projects/seclone

さらに，関数クローン検出法では 10MLOC の検出
中にヒープ領域不足で検出を終了した．ヒープ領域不Vol. 35 No. 4 Nov. 2018
表729

検出規模ごとの検出時間

LOC

本手法

CCFinderX関数クローン検出法

1K

1s

4s

11s

10K

2s

8s

15s

100K

16s

1m 18s

2m 25s1M

3m 1s

12m 24s

20m 4s10M

29m 9s2h 4m 55s

メモリ不足で停止

足は特徴ベクトルの生成中に起こった．これは，特徴

図 9 は，ファイルの出力処理を行うタイプ 4 のブベクトルを疎ベクトルとして実装していないことによロッククローンである．どちらもファイルの入出力

る，メモリ使用効率の悪さが原因として考えられる．

関連の処理を行う関数だが，図 9 (b) の 364 から 366

さらに，抽象構文木を用いた検出法の Deckard と，行目にて個別の処理を行うため，関数クローン検出法

我々の知る限り，プログラム依存グラフに基づくクでは検出できなかった．

ローン検出ツールの中で唯一公開されている Scorpio

また，字句単位の検出である CCFinderX では，図 7の 2 つの手法を 10MLOC の検出規模で実験した．そのコードクローンを検出することができる．図 8 はの結果，7 日間経過しても検出が完了しなかった．そ文の挿入が行われていない部分の検出はできるが，そのため現実的な時間内での検出は完了しないとしてれではコード断片のクローンとなってしまう．よっ

実験を終了した．このことより，抽象構文木を用いたて集約などの保守対象となりづらい．図 9 はタイプ 4

検出法やプログラム依存グラフを用いた検出法と比のクローンであり，CCFinderX はタイプ 2 のクロー

較しても，本手法はスケーラビリティの観点から優位ンまでしか対応していないため検出することができ性があると言える．

ない．さらに，Deckard では，図 7 のコードクロー
ンを検出することができるが，図 8，図 9 は検出する

4. 5 ブロッククローンの実例ことができなかった．なお，唯一公開されているプロ

本節では，4. 1 節で実施したアンケートにて保守対

グラム依存グラフに基づく検出ツールである Scorpio

象のコードクローンと回答されたクローンペアの中は，C 言語に対応していないため適用できなかった．

から，本手法が検出したブロッククローンの実例を示

ブロッククローンの実例より，関数単位より検出粒

す．破線で囲まれたコード片がブロッククローンを度を小さくすることで，関数単位では検出できない表している．

が本手法で検出できるクローンを示すことができた．

図 7 は同じ関数内に存在するタイプ 1 のブロック

また，コードブロック単位でまとまっているため，集クローンである．関数クローン検出法では関数単位約などの保守対象となりやすいことも実例から確認の検出のため，同じ関数内でコピーアンドペースト

できた．また，実際に本手法はタイプ 1 から 4 の検を行うことで発生したコードクローンを検出できな出に対応しており，さらに他の手法では検出できな

かった．

かったコードクローンの検出も可能であった．以上

図 8 は，図 8 (a) の 708 行目と 712 行目に文の挿の観点から本手法の有用性が確認できた．

入が行われたタイプ 3 のブロッククローンである．関
数単位では，図 8 (a) の 697 から 699 行目，719 から 723 行目のコード片に対応する部分が図 8 (b) にない．よって，関数単位では類似していないため関数
クローン検出法では検出できなかった．

4. 6 関数クローン検出法と CCFinderX と比較したときの本手法の特徴
評価実験の結果から，本手法が関数クローン検出法
や CCFinderX より優れた点は以下の点であると考えコンピュータソフトウェア

30ɩɫɯśɏſɏɏƀɏɏſɏɏ ƋƀɩɫɰśƇ
ɩɬɥśɏɏ Śɩɬɨśɏ ɏ ƋŚɩɬɩśɩɬɪśſſ ʰɏɏſĺŞʴ ƀƀŠʰɏƀƇɩɬɫśŚɩɬɬśƈɩɬɭśŵƋŞŞŞ  śƀƋŵɩɬɮśſŞʴŞʴƀƇɩɬɯśɏɏɏ ʰŞʴŞʴŚɩɬɰśƇɩɭɥś ʰſɏ ɏ Ƌƀſſ ƋƀŞʴʫƀŚɩɭɨśʰŞʴŚɩɭɩśŞʴʰŞʴ ʰɥŚɩɭɪśƈſƀŚɩɭɫśŞʴŞʴ ʰɥŚɩɭɬśƈɩɭɭśſŞʴŞʴƀƇɩɭɮśɏɏɏ ʰŞʴŞʴŚɩɭɯśƇɩɭɰś ʰſɏ ɏ Ƌƀſſ ƋƀŞʴʫƀŚɩɮɥśʰŞʴŚɩɮɨśŞʴʰŞʴ ʰɥŚɩɮɩśƈſƀŚɩɮɪśŞʴŞʴ ʰɥŚɩɮɫśƈɩɮɬśŞʴŞʴ ʰɥŚɩɮɭśŞʴʰɥŚɩɮɮśɩɮɯśɏɏſĺŞʴ ƀŚɩɮɰśƈ

Apache HTTPD: /srclib/apr-util/misc/apr rmm.cɭɰɥśɏ ſ  Ƌř  ƋƀɭɰɨśƇ
ɭɰɩśƋřƋɏŚɭɰɪśɏɏ řŚɭɰɫś  ƋŚɭɰɬś Ś
ɭɰɭś
ɭɰɮś
Ś
ɭɰɯś
ſɏſřĺřĺƀƀɭɰɰśŚɮɥɥś ʰɏ ſřƀŚɮɥɨśſ ʰʰƀɮɥɩśŚɮɥɪśɏ ʰɏſƀŚɮɥɫśʰɥŚɮɥɬśſ ʰɥŚ ʳŚʫʫƀƇɮɥɭś ʰɏ ſƋʫʫƀŚɮɥɮśſſ ƀƀƇɮɥɯśʰɨŚɮɥɰśƋɏ ʰſ ƀŚ
ɮɨɥś
ƈ
ɮɨɨś
ſſ ƀƀƇɮɨɩśʰɨŚɮɨɪśƋɏ ʰſ ƀŚ
ɮɨɫś
ƈ
ɮɨɬś

ɮɨɭś
Ƌɏ ʰ ŚɮɨɮśɏʫʫŚ
ɮɨɯś
ƈ
ɮɨɰś
ſŠ ƀƇɮɩɥśɏ ſƀŚɮɩɨśɏ  ſƀŚɮɩɩśŚ
ɮɩɪś
ƈ
ɮɩɫś
Śɮɩɬśƈ

(a) Python: /Modules/stropmodule.c
図 7 同じ関数内に存在するブロック
クローン (タイプ 1)

られる．

• 保守対象となりにくいブロックの一部をコードクローンとして検出することがなく，また関数よりも小さい単位の検出が可能であるため，字句単位の手法や関数クローン検出手法と比べて，保守(集約や同時修正) 対象のコードクローンを多く検出可能．

• 字句単位の手法や関数クローン検出手法だけでなく，抽象構文木やプログラム依存グラフを用いた手法と比べてもスケーラビリティが高いことから，大規模なソースコード集合に対して適用ɩɪɥɯśɏ ſ  ƋƀɩɪɥɰśƇɩɪɨɥś
Ƌʰɏɏ  ſƀřƋɏŚɩɪɨɨś
ɏɏ řʰɏ ɏ ſƀŚɩɪɨɩś
  ƋŚɩɪɨɪś
ɩɪɨɫś
 ʰɏ ſřƀŚɩɪɨɬś
ſ ʰʰƀɩɪɨɭś
Śɩɪɨɮś
ɏ ʰɏſƀŚɩɪɨɯś
ſ ʰɥŚ ʳŚʫʫƀƇɩɪɨɰś ʰɏ ſƋʫʫƀŚɩɪɩɥś
ſſ ƀƀƇɩɪɩɨś
Ƌɏ ʰſ ƀŚɩɪɩɩś
ƈɩɪɩɪś
ſſ ƀƀƇɩɪɩɫś
Ƌɏ ʰſ ƀŚɩɪɩɬś
ƈɩɪɩɭś
ɩɪɩɮś
Ƌɏ ʰ Śɩɪɩɯś
ɏʫʫŚɩɪɩɰś
ƈɩɪɪɥś
ɩɪɪɨśƈŚ(b) Python: /Objects/stringobject.c
図8文の挿入が行われたブロック
クローン (タイプ 3)

可能.
これらの点から，大規模なソースコード集合に対して，保守対象のコードクローンを検出する場合に最も適していると考えられる．

4. 7 粗粒度なコードクローン検出法と比較したときの本手法の特徴

一方で評価実験の結果から，短い変数名が多く出現

同じコードブロック単位の検出手法として，粗粒度するなど，変数名に処理内容が反映されてないソース

なコードクローン検出法 [13] を対象として比較実験をコードに対して本手法は不向きであり，そのような行った．粗粒度なコードクローン検出法とは，タイプ

ソースコードに対しては他の手法の利用を検討すべ

1 と 2 のブロック単位のコードクローンを検出する手きである．また，時間が十分にあり，かつ 100 万行法である．本節ではその実験結果について述べる．

未満のソースコード集合が対象であれば，本手法に加最初に，粗粒度なコードクローン検出法の検出精度

えて抽象構文木やプログラム依存グラフを用いた手を比較した．本実験では，4. 1. 1 節で作成したベンチ法の利用も合わせて検討すべきである．

マークを用いて適合率，再現率，F 値を求めた．ここVol. 35 No. 4 Nov. 2018

31

認できた．
また，粗粒度なコードクローン検出法の検出時間も求めた．実験の結果を表 9 に示す．これにより粗粒度なコードクローン検出法は高速に検出ができることが確認できた．粗粒度なコードクローン検出法は，各コードブロックに対して，正規化後 (変数名の置換(a) Apache HTTPD:/srclib/apr/file io/unix/readwrite.cなど) の文字列からハッシュ値を求め，同じハッシュ
値を持つコードブロックをコードクローンとして検出する．ハッシュ値を用いた比較を行うことで，文字列を用いた比較を行う場合と比べて，小さいコストで2 つのブロックの比較を行うことができる [13]．
次に，粗粒度なコードクローン検出法が検出した
コードクローンのタイプ別の個数について調査した．
本実験では，CCFinderX が検出したクローンペア集
合に対して，4. 1. 3 節のアンケートにより得られた
コードクローンのタイプ情報を基に，タイプ別の個数を検出対象ごとに算出した．結果を表 10 に示す．
これにより，粗粒度なコードクローン検出法はタイ(b) Apache HTTPD:/srclib/apr/file io/unix/readwrite.c
図9

ファイルの出力処理を行うブロック
クローン (タイプ 4)

プ 2 のクローンのみ検出することが分かった．検出法の理論上ではタイプ 1 のコードクローンも検出可能であるが，今回はタイプ 1 のコードクローンは確認できなかった．これは，元々検出対象となっている

CCFinderX が検出したコードクローンにタイプ 1 のでは，ベンチマークにて保守対象と判定されたクロー

コードクローンが少なかったことが原因として挙げ

ンペアを正解クローン，判定されなかったクローンペられる．

アを誤検出と定義する．また，粗粒度なコードクロー

さらに，粗粒度なコードクローン検出法の検出規模

ン検出法が検出したクローンペアを検出クローンとごとの検出時間とスケーラビリティについても述べ定義する．適合率は，検出クローンの中から，正解クる．本実験では 4. 4 節と同一のデータセットを用いローンと一致した集合と誤検出と一致した集合の和て実験を行った．実験の結果を表 11 に示す．これに集合の内，正解クローンと一致した集合の割合によっより，検出規模に比例して線形的に検出時間が増加すて求める．再現率は，正解クローン集合の内，検出クることも確認できた．これは，検出時間においてファローンの中で正解クローンと一致した集合の割合にイル読み込みとコードブロックの抽出に最も時間をよって求める．F 値は適合率と再現率の調和平均に占めていることが原因として挙げられる．

よって求める．実験の結果，粗粒度なコードクローン

最後に，粗粒度なコードクローン検出法の検出し検出法の検出精度は表 8 のとおりとなった．粗粒度

たコードクローンに対する保守作業の調査を行った．

なクローン検出法はタイプ 1 と 2 のコードクローン

本実験では，CCFinderX が検出したクローンペア集

しか検出しないため，保守対象となりやすく適合率は合に対して，4. 3 節のアンケートにより得られた保守高い値となった．しかし，タイプ 3 や 4 を検出する

作業の調査結果をもとに，実際に適用される保守作業ことができず検出数が少ないため再現率は低い値との割合と，保守対象と判定されなかった原因を求めなり，総合的な評価の F 値は低い値となることが確た．実際に適用される保守作業は，同時修正の対象とコンピュータソフトウェア

32
表8

粗粒度なコードクローン検出法の検出精度の評価

検出手法

検出対象

適合率

再現率

F値

Apache HTTPD

0.91

0.14

0.24

粗粒度クローン

PostgreSQL

0.87

0.28

0.43

検出法

Python

0.95

0.32

0.48

合計

0.91

0.24

0.38

Apache HTTPD

0.90

0.74

0.81

PostgreSQL

0.57

0.87

0.69

Python

0.90

0.53

0.67

合計

0.68

0.70

0.69

本手法

表9

表 10

粗粒度なコードクローン検出法の検出時間

検出対象

粗粒度クローン検出法

本手法

Apache HTTPD

8s

1m 39sPostgreSQL

16s

2m 27sPython8s

1m 15s

粗粒度なコードクローン検出法の検出したコードクローンのタイプ別内訳

検出対象

T1

T2

T1, T2 合計

Apache HTTPD

0

4

4

PostgreSQL

0

1

1

Python

0

13

13

合計

0

18

18

表 11

粗粒度なコードクローン検出法の検出規模ごとの検出時間

LOC

粗粒度クローン検出法

本手法

1K

0s

1s

10K

1s

2s

100K

8s

16s

1M

1m 15s3m 1s

10M

12m 38s

29m 9sなるクローンペアが 15，集約と同時修正の対象となの正確性と網羅性の総合評価でも高い点において本るクローンペアが 3 となった．また，保守対象と判手法の方が優れている．ただし，粗粒度なコードク

定されなかった原因として，出力処理の連続，代入文

ローン検出法はコードブロック単位の検出を行うたの連続，単調な関数呼び出しの 3 例が挙げられた．

め，トークン単位の検出法である CCFinderX で確認

以上の結果から，タイプ 1 や 2 だけでなく，3 と 4されたようなコード片の断片を検出することはなく，のコードクローンも検出可能で網羅性が高く，検出検出の正確性が高くなっている．また，タイプ 1 と 2

Vol. 35 No. 4 Nov. 2018のコードクローンのみを検出するため，高速な検出が33

プにかかる時間を詳細に調査する必要がある．

可能となっている．今回の評価実験から，本手法の補

また本研究では我々が作成したコードクローンベン

完的な検出方法として粗粒度なコードクローン検出

チマークを対象に検出精度の評価実験を行ったが，他法の利用も検討できる．

にも大規模なベンチマーク [29] も提案されている．このような他のベンチマークに対しても本手法の有用性

5 考察が確認できるのか評価する必要がある．さらに今回比5. 1 本手法の拡張性較を行っていない手法との比較も行い，本手法の検出

本手法の実装は，現在 C 言語と Java 言語にのみ対結果の特徴についてより詳細に分析する必要もある．

応している．しかし，本手法では ANTLR を用いて構文解析を行っており，ANTLR にて構文解析を行

6 関連研究

うための文法ファイルが 100 種類以上用意されてい構文の類似性に着目した手法として，字句単位の検ることから，他の言語への拡張が容易に可能である．

出手法や，抽象構文木 (ソースコードの構文構造を木構造で表したグラフ) を用いた検出手法が存在する．

5. 2 評価実験の妥当性

字句単位の検出手法では，ソースコードをトークン列

適合率，再現率，F 値で示される検出精度に関しに変換し，共通トークン列をコードクローンとしてて，本実験では 3 つの C 言語のプロジェクトに対し検出する [16] [20]．また，抽象構文木を用いた検出手て関数クローン検出法と CCFinderX との比較を行う

法では，ソースコードを抽象構文木に変換し，類似ことによって，本手法の有用性を示した．しかし，今した部分木をコードクローンとして検出する [15] [4]．

後は他の言語で実装されたプロジェクトに対して適本研究では，提案手法と字句単位の検出ツールである

用したり，他のツールとの比較を行ったりするなど，

CCFinderX と比較し，提案手法が適合率や再現率，一般性を示す必要性がある．

スケーラビリティにおいて優れていることを確認しまた，本実験で用いたパラメータの値によって実験た．また，スケーラビリティの実験において，抽象構

結果は変わってくる．特に CCFinderX の実験結果は

文木を用いた検出ツールである Deckard が 10MLOC

最小一致トークン数の値が影響している可能性があのソースコード集合を対象とした実験において現実的るが，最小一致トークン数を下げると再現率は上昇すな時間で検出処理を終えることができなかったこと，るが適合率が低下する．

および Deckard が検出できないが提案手法が検出で特徴ベクトルの計算方法として本手法では TF-IDF

きるコードクローンの実例を確認した．

を用いているが，他にも LSI (Latent Semantic In-

また，プログラムの処理の類似性に着目した手法とdexing) [3] や，LDA (Latent Dirichlet Allocation) [5]して，プログラム依存グラフ (プログラム内の要素間など次元圧縮を行い計算時間の短縮を行った手法がに存在する依存関係を表した有効グラフ) を用いた検ある．またワードの共起頻度に基づいて次元圧縮を出手法が存在する．この手法では，ソースコードから行うことで，ワードの類義性も計算可能となる．これプログラム依存グラフを構築し，類似した部分グラフ

らと TF-IDF を比較することで，検出速度と検出精を探索することによって，タイプ 3 や 4 のコードク度の観点から比較を行う必要がある．

ローンを検出することが可能である [9] [10] [19]．しかそして，LSI や LDA を用いて特徴ベクトルを計算

し，プログラム依存グラフの比較の計算コストが高する場合，特徴ベクトルの生成や類似度の計算にかかく，検出に時間がかかってしまうという問題点がある時間が変化する．たとえば，次元圧縮を行うため特る．また，プログラム言語ごとにプログラム依存グラ

徴ベクトル生成に時間が増加するが，次元削減によりフを構築する機構を用意する必要性がある．本研究

類似度計算の時間が減少するなどが考えられる．しでは，プログラム依存グラフを用いた検出ツールであたがって，LSI や LDA などを用いた場合に各ステッる Scorpio [9] [10] が 10MLOC のソースコード集合を

34

コンピュータソフトウェア

対象とした実験において現実的な時間で検出処理を

約語の集合が類似していれば，それらブロックはブ終えることができなかったことを確認した．

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

LCS (Longest Common Subsequence) アルゴリ

Duala-Ekoko らは，クローン領域を抽象的に記述

ズムを利用した検出手法として NiCad が存在する

し，バージョン間でのクローンの移動を追跡し管理す[24] [25]．NiCad は，ソースコードの各行を要素とする手法を提案している [8]．ソフトウェアの開発過程る列に対して LCS アルゴリズムを適用して，固有においてコードクローンの変更管理を行う場合，ソーの行の割合が閾値以下であればコードクローンとしスコードの編集により行情報は変更されるため，従来て検出する．閾値未満であれば，固有の行を許容すの行情報を用いたクローン領域の記述方法ではコード

るため，タイプ 3 のコードクローンを検出することクローンを追跡できない．そこで彼らは，クローン領ができる．NiCad は文献により実装方法に差異があ

域を抽象的に記述する手法を提案した．彼らの提案手り，またチューニングにより検出速度が大きく異なる

法はコードクローン追跡のための手法であり，コード[7] [24] [25]．今後，本研究が提案する手法と比較を行

クローン検出を目的とする本研究とは目的が異なる．

う必要があるが，各実装に応じたチューニングを適切

彼らの手法では，構文，構造，語彙の情報を組み合わに行いながら，比較実験を行う必要があると考えらせてクローン領域を抽象的に記述することでクローンれる．

追跡を可能にしている．しかし，本手法はクローン追山中らのツール [32] 以外の関数クローン検出ツール

跡の必要性がないためファイルと行の情報で記述されとして MeCC [17] がある．MeCC は，記号実行を行たクローン領域をコードブロックとして扱っている．

うことによって，ソースコード中の各関数が終了した時点における抽象的なメモリの状態の予測を行う．そ7 まとめと今後の課題

して，メモリの状態が類似した関数をコードクローン

本研究では，TF-IDF と LSH を利用したブロック

として検出する．山中らの論文 [32] において，山中ら

クローン検出手法の提案を行った．本手法では，構文の関数クローン検出ツールの方が MeCC より正確に解析を行いコードブロックの抽出を行い，コードブ

関数クローンを検出できることが確認されている．本

ロック中の識別子や予約語に利用されている単語か論文の実験では，山中らの関数クローン検出ツールとらワードを抽出する．そして，TF-IDF を利用して各比較して，提案手法の方が適合率や再現率，スケーラ

ワードに対する重みを計算し，その重みを特徴量としビリティにおいて優れている点が多いことを示した．

て各コードブロックを特徴ベクトルに変換する．そMarcus らは，クエリとして与えられたソースファの後，特徴ベクトル間の類似度を計算することによっ

イルと類似した部分を，LSI (Latent Semantic In-て，意味的に処理が類似したブロッククローンの検

dexing) [3] を用いてソースコード全体から検索する手出を行う．また，multi-probe LSH を cross-polytope法を提案している [22]．彼らが提案する手法はクエリ

LSH に組み合わせた手法を用いてあらかじめ特徴ベを与える必要があるため，本研究の提案手法とは目的

クトルのクラスタリングを行うことによって，高速なが異なる．しかし，提案手法においても LSI を利用

ブロッククローンの検出を実現した．

し識別子間の潜在的意味を解析することで，再現性を向上させることができる可能性がある．

評価実験では，3 つの C プロジェクトに対し，検出精度と検出時間の観点から，関数クローン検出法と我々の研究グループでは，トークン列が等価なファ

CCFinderX の 2 つの手法と比較を行った．比較した

イルを高速に検出するツール FCFinder の開発を行っ結果，本手法が高い精度かつ高速にコードクローンをた [28]．本研究では，識別子や予約語の類似性に着目検出することが確認できた．また，スケーラビリティ

し，ブロック単位のコードクローンを検出する手法をの評価では，1KLOC から 10MLOC の検出規模に応提案した．本研究が提案する手法は，2 つのブロック

じて，線形的に検出時間が増加することを確認できた.

に含まれるトークン列が異なっていても，識別子や予今後の課題として，5. 2 節にて述べたように以下がVol. 35 No. 4 Nov. 2018
挙げられる．

• 今回は特徴ベクトルの計算に TF-IDF を用いたが，LSI (Latent Semantic Indexing) [3] や，LDA(Latent Dirichlet Allocation) [5] といった次元圧
縮を行う手法がある．これら次元圧縮を用いた手法との比較を行う必要がある．

• LSI や LDA などを用いた場合，検出の各ステッ
プにかかる時間を詳細に調査する必要がある．

• 他の大規模プロジェクトに対して適用し，本手法の有用性を評価する必要がある．さらに，他の検出手法との比較を行う必要がある．
謝辞

本研究に対して，様々なご協力をいただいた日

本電気株式会社前田直人氏，渋谷健介氏，大阪大学石津卓也氏，沼田聖也氏 (現新日鉄住金ソリューションズ株式会社)，徳井翔梧氏に深く感謝する．本研究は JSPS
科研費 JP25220003，JP18H04094，JP16K16034 の助成を受けた．

参 考 文 献[ 1 ] Andoni, A. and Indyk, P.: Near-optimal hashingalgorithms for approximate nearest neighbor in highdimensions, Proc. of the FOCS, 2006, pp. 459–468.
[ 2 ] Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I., and Schmidt, L.: Practical and Optimal
LSH for Angular Distance, Proc. of NIPS, 2015,
pp. 1225–1233.
[ 3 ] Baeza-Yates, R. and Ribeiro-Neto, B.: Modern
information retrieval: The concepts and technology
behind search, Addison-Wesley, 2011.
[ 4 ] Baxter, I. D., Yahin, A., Moura, L., Anna, M. S.,
and Bier, L.: Clone detection using abstract syntax
trees, Proc. of ICSM, 1998, pp. 368–377.
[ 5 ] Blei, D. M., Ng, A. Y., and Jordan, M. I.: Latent dirichlet allocation, Journal of machine Learning research, Vol. 3, No. Jan (2003), pp. 993–1022.
[ 6 ] Charikar, M. S.: Similarity estimation techniques from rounding algorithms, Proc. of STOC,
2002, pp. 380–388.
[ 7 ] Cordy, J. R. and Roy, C. K.: Tuning Research Tools for Scalability and Performance: The
NiCad Experience, Science of Computer Programming, Vol. 79 (2014), pp. 158–171.
[ 8 ] Duala-Ekoko, E. and Robillard, M. P.: Clone
Region Descriptors: Representing and Tracking
Duplication in Source Code, ACM Transactions
on Software Engineering and Methodology, Vol. 20,
No. 1 (2010), pp. 3:1–3:31.

35[ 9 ] 肥後芳樹, 楠本真二: プログラム依存グラフを用いたコードクローン検出法の改善と評価, 情報処理学会論文誌, Vol. 51, No. 12 (2010), pp. 2149–2168.
[10] Higo, Y. and Kusumoto, S.: Enhancing Qualityof Code Clone Detection with Program Dependency
Graph, Proc. of WCRE, 2009, pp. 315–316.
[11] 肥後芳樹, 楠本真二, 井上克郎: コードクローン検出とその関連技術, 電子情報通信学会論文誌, Vol. J91-D,
No. 6 (2008), pp. 1465–1481.
[12] Higo, Y., Kamiya, T., Kusumoto, S., and Inoue,K.: Method and implementation for investigatingcode clones in a software system, Information and
Software Technology, Vol. 49, No. 9 (2007), pp. 985–
998.
[13] 堀田圭佑, 楊嘉晨, 肥後芳樹, 楠本真二: 粗粒度な
コードクローン検出手法の精度に関する調査, 情報処理学会論文誌, Vol. 56, No. 2 (2015), pp. 580–592.
[14] Indyk, P. and Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality, Proc. of STOC, 1998, pp. 604–613.
[15] Jiang, L., Misherghi, G., Su, Z., and Glondu, S.:
DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones, Proc. of ICSE, 2007, pp. 96–
105.
[16] Kamiya, T., Kusumoto, S., and Inoue, K.:
CCFinder: a multilinguistic token-based code clone
detection system for large scale source code, IEEE
Transactions on Software Engineering, Vol. 28,
No. 7 (2002), pp. 654–670.
[17] Kim, H., Jung, Y., Kim, S., and Yi, K.: MeCC:
memory comparison-based clone detector, Proc. of
ICSE, 2011, pp. 301–310.
[18] 古賀久志: ハッシュを用いた類似検索技術とその応用, 電子情報通信学会基礎・境界ソサイエティ Fundamentals Review, Vol. 7, No. 3 (2014), pp. 256–268.
[19] Komondoor, R. and Horwitz, S.: Using slicing
to identify duplication in source code, Proc. of SAS,
2001, pp. 40–56.
[20] Li, Z., Lu, S., Myagmar, S., and Zhou, Y.: CPMiner: finding copy-paste and related bugs in largescale software code, IEEE Transactions on Software
Engineering, Vol. 32, No. 3 (2006), pp. 176–192.
[21] Lv, Q., Josephson, W., Wang, Z., Charikar, M.,
and Li, K.: Multi-probe LSH: eﬃcient indexing forhigh-dimensional similarity search, Proc. of VLDB,
2007, pp. 950–961.
[22] Marcus, A. and Maletic, J. I.: Identification ofhigh-level concept clones in source code, Proc. ofASE, 2001, pp. 107–114.
[23] Rattan, D., Bhatia, R., and Singh, M.: Software clone detection: A systematic review, Information and Software Technology, Vol. 55, No. 7(2013), pp. 1165–1199.
[24] Roy, C. K. and Cordy, J. R.: An Empirical Studyof Function Clones in Open Source Software, Proc.
of WCRE, 2008, pp. 81–90.
[25] Roy, C. K. and Cordy, J. R.: NICAD: Accurate Detection of Near-Miss Intentional Clones Us-

コンピュータソフトウェア

36

ing Flexible Pretty-Printing and Code Normalization, Proc. of ICPC, 2008, pp. 172–181.
[26] Roy, C. K., Cordy, J. R., and Koschke, R.: Comparison and evaluation of code clone detection techniques and tools: A qualitative approach, Scienceof Computer Programming, Vol. 74, No. 7 (2009),
pp. 470–495.
[27] Sajnani, H., Saini, V., Svajlenko, J., Roy, C. K.,
and Lopes, C. V.: SourcererCC: Scaling code
clone detection to big-code, Proc. of ICSE, 2016,
pp. 1157–1168.
[28] 佐々木裕介, 山本哲男, 早瀬康裕, 井上克郎: 大規
模ソフトウェアシステムを対象としたファイルクロー
ンの検出, 電子情報通信学会論文誌, Vol. J94-D, No. 8(2011), pp. 1423–1433.
[29] Svajlenko, J., Islam, J. F., Keivanloo, I., Roy,C. K., and Mia, M. M.: Towards a Big Data Curated
Benchmark of Inter-project Code Clones, Proc. of
ICSME, 2014, pp. 476–480.
[30] Terasawa, K. and Tanaka, Y.: Spherical LSH
for Approximate Nearest Neighbor Search on Unit
Hypersphere, Proc. of WADS, 2007, pp. 27–38.
[31] 徳井翔梧, 吉田則裕, 崔恩瀞, 井上克郎: 局所性鋭敏型
ハッシュを用いたコードクローン検出のためのパラメー
タ決定手法, 電子情報通信学会技術研究報告, Vol. 117,
No. 477, 2018, pp. 57–62.
[32] 山中裕樹, 崔恩瀞, 吉田則裕, 井上克郎: 情報検索技術に基づく高速な関数クローン検出, 情報処理学会論文
誌, Vol. 55, No. 10 (2014), pp. 2245–2255.
[33] Yamanaka, Y., Choi, E., Yoshida, N., Inoue,K., and Sano, T.: Applying clone change notification system into an industrial development process,Proc. of ICPC, 2013, pp. 199–206.

崔恩瀞

2015 年大阪大学大学院情報科学研究科博士後期課程修了．同年同大学大学院国際公共政策研究科助教．2016
年奈良先端科学技術大学院大学情報科学研究科助教．2018 年より同大学先端科学技術研究科助教 (改組による)．博士 (情報科学)．コードク
ローン管理やリファクタリング支援手法に関する研
究に従事．
吉田則裕

2004 年九州工業大学情報工学部知能情報工学科卒業．2009 年大阪大学大学院情報科学研究科博士後期課程修了．同年日本学術振興会特別研究員(PD)．2010 年奈良先端科学技術大学院大学情報科学研究科助教．2014 年名古屋大学大学院情報科学研究科附属組込みシステム研究センター准教授．2017 年
より同大学大学院情報学研究科附属組込みシステム
研究センター准教授 (改組による)．博士 (情報科学)．
コードクローン分析手法やリファクタリング支援手法に関する研究に従事．
井上克郎

横井一輝

1984 年大阪大学大学院基礎工学研究2017 年大阪大学基礎工学部情報科学科博士後期課程修了 (工学博士)．同科卒業．現在，大阪大学大学院情報年大阪大学基礎工学部情報工学科助科学研究科博士前期課程 2 年．コー

手．1984 年〜1986 年，ハワイ大学

ドクローン検出手法の研究に従事．

マノア校コンピュータサイエンス学科助教授．1991
年大阪大学基礎工学部助教授．1995 年同学部教授．

2002 年より大阪大学大学院情報科学研究科教授．ソフトウェア工学，特にコードクローンやコード検索などのプログラム分析や再利用技術の研究に従事．