日本ソフトウェア科学会第 35 回大会 (2018 年度) 講演論文集

コードクローン検出が用いる局所性鋭敏型ハッシュに与えるパラメータ決定手法
徳井 翔梧

吉田 則裕

崔 恩瀞

井上 克郎

コードクローンとは，ソースコード中に存在する互いに一致または類似した部分を持つコード片のことである．我々が提案したブロッククローン検出法では局所性鋭敏型ハッシュ(LSH) を用いることにより，従来の研究では困難であった意味的に類似するコードクローン対を検出できた．LSH とは，高次元なデータを確率的にハッシュ化し，近傍点を見つけるアルゴリズムである．しかし，LSH は検出漏れの可能性がある．本研究では，LSH の衝突確率とクローン検出の利用者が与えた類似度の閾値に対して一定の再現率を得るための，LSH に与えるパラメータ決定手法を提案する．更に，決定されたパラメータをブロッククローン検出法に適用し，異なる規模の 2 つのプロジェクトに対して実験を行うことで，本手法の有効性を示す．

A code clone is a code fragment that has identical or similar code fragments to it in the source code. Our
previous research developed a block code clone detector using Locality Sensitive Hashing (LSH) that could
detect not only syntactic clones but also semantic clones which had been diﬃcult to be detected. LSH isa near neighbor search algorithm that performs probabilistic hashing of high-dimensional data. However,
LSH-based detection is possible to miss several code clones. In this study, we propose an approach todetermine LSH parameters in order to obtain the constant recall when a collision probability of LSH and asimilarity threshold are given by a user. Finally, we apply this approach with the block code clone detector
to two projects. The result shows the eﬀectiveness of this approach.

ことは困難となる．そこで，コードクローンを自動的1 まえがきに検出するための手法が提案されている [10] [6]．

ソフトウェアの保守における問題のひとつとして，横井らは情報検索技術 [4] と局所性鋭敏型ハッシュコードクローンが指摘されている [6]．コードクロー(LSH) [2] を利用することによって，意味的に処理がンとは，ソースコード中に含まれる互いに一致または類似したコードブロック単位のコードクローンを検出類似した部分を持つコード片のことであり，コードクするブロッククローン検出法を提案した [7]．LSH とローン対をクローンペアと呼ぶ．一般的に，コードクは，高次元なベクトル集合を確率的にハッシュ化し，ローンの存在はソフトウェアの保守を困難にすると言類似度が高いベクトル対を高速に見つけるアルゴリ

われている．コードクローンに対する様々な保守や管ズムである．この検出法は，情報検索技術の一種で理の方法が提案されているが，ソースコードの規模ある TF-IDF (Term Frequency-Inverse Documentが大きくなるとソースコード中に含まれるコードクFrequency) 法 [4] を用いてコード片ごとに特徴ベクト

ローンも膨大な量となり，手作業でそれらを管理する

ルを生成し，局所性鋭敏型ハッシュ(LSH) の一種である FALCONN†1 [2] を用いてコサイン類似度が閾値A Determination Method of Locality Sensitive Hashing Parameters for Code Clone Detection
Shogo Tokui，Katsuro Inoue, 大 阪 大 学, OsakaUniversity.
Norihiro Yoshida, 名古屋大学, Nagoya University.
Eunjong Choi, 奈良先端科学技術大学院大学, Nara Institute of Science and Technology.

以上のベクトルペアの探索 (類似探索) を行い，コードクローンを検出する．ブロッククローン検出法では従来法において困難であった意味的に類似するコー†1 https://falconn-lib.org/

ドクローン対を検出することが可能である．ブロッ

STEP 1 構文解析を行い，抽象構文木を生成

ククローン検出法は，他の検出手法と比べて検出結STEP 2 抽象構文木からコードブロックと単語果の適合率や再現率が高い．また，大規模なプロジェクトに対して現実的な計算時間でコードクローン検出可能である．実際，ブロッククローン検出法を用
いて Linux Kernel 4.14 のコードクローン検出を行うと，20 分程度で検出が完了し，100MLOC においても 4 時間程度で検出可能であった．
しかし，現状のブロッククローン検出法は，LSHを抽出

STEP 3 TF-IDF 法により，ブロック単位の特徴ベクトルを計算

STEP 4 FALCONN を利用した類似探索を行い，コサイン類似度が閾値以上のクローンペアを検出

STEP 4 で用いる LSH ライブラリである FALCONN について，2. 2 節にて説明する．

における検出漏れが発生する問題がある [9]．つまり，類似度が閾値以上である検出されるべきクローンペ

2. 2 近似最近傍探索ライブラリ FALCONN

アが，LSH を用いた類似探索において検出されない

本節では，ブロッククローン検出法が用いる近似最可能性がある．本研究では，検出漏れをユーザーが指近傍探索ライブラリ FALCONN について述べる．

定する割合に抑え，かつ可能な限り高速に実行するた

Alexandr らは，大規模なベクトル集合の近似最近めの，FALCONN に与えるパラメータを決定する手傍探索問題を解くための手法として，理論的かつ実用法を提案する．

的な手法 FALCONN を開発した [2]．以降，LSH の定以降，2 章では，ブロッククローン検出その関連

義と cross-polytope LSH について述べ，FALCONN技術について述べる．3 章では，FALCONN のパラに実装されている LSH を利用した類似探索アルゴリメータの解析を行う．4 章では，FALCONN に与えズムについて説明する．

るパラメータ決定手法の提案を行う．5 章では，有効2. 2. 1 局所性鋭敏型ハッシュ(LSH)性の評価を行う．最後に 6 章では，まとめと今後の課LSH (Locality-Sensitive Hashing）とは，ハッシュ題について述べる．

関数を用いて類似度が高いベクトル対を高速に見つけるアルゴリズムである [1]．LSH はは，あるベクト2 ブロッククローン検出とその関連技術

ルと近似因数 c < 1 に対して，類似度が δ 以上のベ

本章では，ブロッククローン検出法と，ブロックククトルが存在するとき，類似度が cδ 以上のベクトルローン検出法が用いる LSH である FALCONN につをすべて返す，LSH のハッシュ関数は以下の 2 つのいて説明を行い，最後にブロッククローン検出法の問定義を満たす．

題点について述べる．

定義 1. S(x, y) > δ ⇒ P r(x, y) > P1
定義 2. S(x, y) < cδ ⇒ P r(x, y) < P2

2. 1 ブロッククローン検出法

類似度 S(x, y) が定義された d 次元空間上におい山中らは情報検索技術を利用して，意味的に処理がて，P r(x, y) は，2 つのベクトル x, y が同じハッシュ類似した関数単位でのコードクローンを検出する手法

値を取る確率を表す．LSH では，P r(x, y) を衝突確

[8] を提案した．しかし粒度が大きいため，小さい粒率と呼ぶ．P1 , P2 は P1 > P2 を満たす．LSH の１つ度のコードクローンが検出ができない問題があった．のハッシュ関数の時間計算量のオーダーは O(dnρ ) とそこで，横井らはコードブロック単位での検出法を提表される．d はベクトルの次元数，n はベクトル数を案し，精度を向上させることに成功した [7]．ここで，表す．ρ は P1 , P2 から算出される時間計算量の評価

コードブロックとは，if 文や for 文などの波括弧で囲基準であり，式 1 で表される値である [3]．
log(1/P1 )ρ=log(1/P2 )まれたコード片を指す．
ブロッククローン検出法は以下のステップで実行される．

(1)

2. 3 ブロッククローン検出法の問題点

2. 2. 2 cross-polytope LSH
FALCONN は，コサイン類似度のための LSH で

我々は先行研究において，LSH を用いるコードクあり，理論的に優れている cross-polytope LSH に基ローン検出法に対して，以下２つの問題点を指摘した

づく実用的なアルゴリズムである [2]．2 つのベクトル[9]．1 つ目は，ブロッククローン検出法の STEP4(類x, y に対して，コサイン類似度 C(x, y) は式 2 で求め似探索) にかかる時間が検出全体の約 90%を占めていられる．

る点である．2 つ目は，LSH を用いた類似探索におx·yC(x, y) =(2)∥x∥∥y∥
cross-polytope LSH における入力ベクトルのハッいて，約 10%の検出漏れが発生している点である．

シュ値は，単位球上にランダム回転した後のベクト3 FALCONN のパラメータの解析

ルが，含まれる区画のラベルである．FALCONN は，2. 3 節で述べた問題は，計算時間を短くするためランダム回転の処理に高速アダマール変換を用い，まに，ブロッククローン検出法の開発者が検出漏れが起た，前処理として次元圧縮をするなどしてメモリ削減こるような LSH のパラメータを選択していたことがや高速化を行っている．

原因として生じた．

cross-polytope LSH では，ランダム回転後にその本章では，コードクローン検出のための適切なパラ点が存在する単位球上の区画がそのベクトルのハッメータを選択するために，FALCONN のパラメータシュ値となる．cross-polytope LSH において，あるの解析を行う．FALCONN のパラメータには 11 個

類似度 δ に対して，C(x, y) > δ をみたす 2 つのベクのパラメータがある．ここではパラメータの中でも，

トル x, y の衝突確率は，単位球を T 個の区画に分割検出精度を表す衝突確率に関わる区画の分割数 T とする場合，式 3 で表される [2]．
11−δln=· ln T + Oδ (ln ln T )P r(x, y)1+δ
2. 2. 3 類似探索

ハッシュテーブル数 L について説明を述べる．

(3)
3. 1 区画の分割数 Tベクトル集合から，類似度が閾値 θ 以上のベクトル

パラメータ T と衝突確率，及び時間計算量の評価基対をすべて取得することを類似探索という．最も単純

準 ρ の関係を説明する．T とは，単位球を分割する区な類似探索アルゴリズムである，すべてのベクトル対画の数を表す．分割数 T に指定できる範囲は，ベクトの類似度を計算し，閾値以上のベクトルペアを取得すルの次元数以下の自然数である．FALCONN は 1024

る方法では，時間計算量は O(dn2 ) となる．しかし，次元に次元圧縮を行うため，T には 1 ≤ T ≤ 1024 のLSH を用いることによって，時間計算量を O(Ldnρ )整数を指定できる．とできる．LSH を用いた類似探索のアルゴリズム [1]は，以下の 3 つのステップで構成される．

STEP A ベクトルの集合から L 個のハッシュテーブルを作成

STEP B いずれかのハッシュテーブルで衝突するベクトル対を類似度が閾値以上のベクトル対の候補として抽出

STEP C STEP B で抽出したすべてのベクトル対の類似度を計算

LSH によって類似度が閾値以上のベクトル対の候補を絞ることにより，類似度を計算するベクトル対の数を減らす事ができる．

2. 2. 2 節の式 3 から，類似度 δ に対して，C(x, y) >
δ をみたす 2 つのベクトル x, y の cross-polytope LSHにおける衝突確率 P r(x, y) は T の対数に比例し，Tを増加させると衝突確率 P r(x, y) は減少する．
また，2. 2. 1 節の式 1 と 2. 2. 2 節の式 3 から，時間計算量の評価基準 ρ は式 4 と表せる．
1−δ· ln T + Oδ (ln ln T )1+δρ = c2 (1−δ)· ln T + Ocδ (ln ln T )2−c2 (1−δ)(4)

時間計算量の評価基準 ρ の値が小さいほど，時間計算量のオーダー O(Ldnρ ) は小さくなる．時間計算量の評価基準 ρ は，定数である近似因数 c < 1 と類似度 δ を除くと，分割数 T にのみ依存する．式 4 から，T が大きいほど，ρ は小さくなる．参考文献 [2]… , 𝑎𝑑 }… , 𝑏𝑑 }STEP A

STEP B𝑥1

類似度𝑥4𝑥60.95

ブロック

特徴ベクトルブロックA𝑥1

ブロックB𝑥4

STEP C…
計算量の評価基準
ρ は単調減少し，T → inf のとき
0.98
ρ → 17 となる．
0.96

80

100010000

0.94
3. 2 ハッシュテーブル数 L0.92
ハッシュテーブル数 L と衝突確率，及び計算時間0.9の関係を説明する．
FALCONN
では，あるベクトル
1101001000 10000
T
対が L 個のハッシュテーブルの少なくとも１個のハッシュテーブルで衝突するとき，そのベクトル対を類似が閾値 θ 以上のベクトル対の候補とみなす．式 3 の計算時間[s]100

衝突確率の 4 章を参照すると，分割数T を増加させると時間
160402000

図11020
ハッシュテーブル数 L30

ハッシュテーブル数 L と計算時間の関係

cross-polytope LSH の衝突確率 P r(x, y) を用いて，確率 P rL (x, y) と FALCONN の時間計算量 O(Ldnρ )FALCONN の衝突確率 P rL (x, y) は式 5 と表される．の一方が良くなる値にするとともう一方が悪くなる．

P rL = 1 − (1 − P r(x, y))L(5)大規模なプロジェクトに対してコードクローン検出す式 5 から，L 個のハッシュテーブルでの失敗確率ることを想定しているため，FALCONN の時間計算

1 − P rL (x, y) は式 6 と表せる．

量 O(Ldnρ ) の評価基準である ρ を可能な限り小さく

1 − P rL (x, y) = (1 − P r(x, y))L(6)する事を優先し，T は最大値である 1024 に決定する．

1 − P rL (x, y) とは，どのハッシュテーブルでも衝突そのとき衝突確率は小さくなるので，ハッシュテーブしない確率を表す．式 6 から，１つのハッシュテーブ

ル数 L で調整する．ハッシュテーブル数 L を決定す

ルでの失敗確率 1 − P r(x, y) に対して，ハッシュテーる手法を 4 章で説明する．

ブル数 L を増加させると，L 個のハッシュテーブルでの失敗確率 1 − P rL (x, y) は減少する．すなわち，4 FALCONN のパラメータ決定手法

ハッシュテーブル数 L を増加させると，FALCONN

本章では，類似度の閾値 θ と目標再現率 R を入力の衝突確率 P rL (x, y) が増加する．
また，L と計算時間の関係を調べるために，ハッとして，R 類似探索を行うための FALCONN に与えるパラメータを決定する手法を提案する．

シュテーブル数 L のみ変化させて類似探索の時間を計測した．1 ≤ L ≤ 30 の範囲を 1 ずつ変化させて計4. 1 再現率と R 類似探索の定義

測した，実験結果のグラフを図 1 に示す．図 1 のグ

本節では，再現率と R 類似探索の定義を行う．

ラフより，L を増加させると計算時間は線形に増加する．よって，FALCONN の時間計算量は O(Ldnρ )と表せる．

まず，再現率 r の定義を行う．再現率 r は式 7 で与えられる．

|SLSH |(7)|Sall |類似度が閾値 θ 以上であるすべてのベクトル対のr=

3. 3 解析結果に対する考察集合を Sall ，LSH を用いた類似探索によって検出し本節では，3. 1 節と 3. 2 節での解析結果から考察たベクトル対の集合を SLSH とする．LSH を用いたを行う．分割数 T を増加させると，FALCONN の時類似探索では，2. 2. 3 節の STEP C で類似度の計算間計算量 O(Ldnρ ) の評価指標 ρ を減少できるが，1を行い，類似度が閾値 θ 以上のベクトル対を求める

つのハッシュテーブルにおける衝突確率 P r(x, y) もため，包含関係 SLSH ⊂ Sall を常に満たす．

減少する．ハッシュテーブル数 L を増加させると，次に，R 類似探索の定義を行う．目標再現率 R にFALCONN の衝突確率 P rL (x, y) は増加できるが，対して，R 以上の再現率を満たし，可能な限り少なFALCONN の計算時間が線形に増加する．

い計算時間で実行される類似探索を，R 類似探索と分割数 T とハッシュテーブル数 L はいずれも，衝突定義する．R 類似探索となるためのパラメータ決定手法について 4. 2 節で述べる．

4. 2 R 類似探索となるための FALCONN に与よって，再現率の期待値 Erecall は，式 11 で表される．
E
Erecall == P rL (x, y)(11)|Sall |
式 8 と式 11 から，式 12 が導ける．よって，再現率の期待値が目標再現率 R 以上となる．

Erecall ≥ Rえるパラメータ決定(12)

本節では，3 章で解析した区画の分割数 T とハッシュテーブル数 L の決定手法を述べる．
分割数 T は，3. 3 節より，時間計算量のオーダー
ρ5 評価実験O(Ldn ) の評価指標である ρ に影響を与える．類似探本章では，本手法をブロッククローン検出法に適用索の計算時間を可能な限り小さくするために，時間計し，4. 2 節で決定したパラメータと，FALCONN の算量の評価指標 ρ を可能な限り小さくする T = 1024に決定する．このとき衝突確率が減少するため，再現デフォルトのパラメータとでの比較を行い，本手法の有効性の評価を行う †2 ．

率 R 以上をみたすようにハッシュテーブル数 L を調

異なる規模の 2 つの C プロジェクトである Post-整する．

greSQL 10.1 と Linux Kernel 4.14 に対して，ブロッ以下のステップでハッシュテーブル数 L を決定する．

ククローン検出法でコードクローン検出を行い，類似STEP I 式 3 と T = 1024 から，類似度が閾値 θ

探索の処理時間と類似探索の再現率を調べる．対象のの 2 点の衝突確率 P r(x, y) を計算

プロジェクトの情報を表 1 に示す．

STEP II 式 5 と目標再現率 R に対し，式 8 をみたす最小値に決定

ここでは，ブロッククローン検出法のコサイン類似度の閾値 θ は，デフォルトである 0.9 とし，目標再現

P rL (x, y) ≥ R(8)率 R を 0.99 とした．このとき，本手法により決定さSTEP I で計算する P r(x, y) の値は，T = 1024 よりれた FALCONN に与えるパラメータを表 2 に示す．

式 9 で求められる．

デフォルトは，FALCONN のデフォルトのパラメー

P r(x, y) = 10241−θ−Oθ (1)1+θ(9)タを表す．FALCONN に与えるパラメータは他にもこのとき，3. 2 節の式 6 からハッシュテーブル数並列化のためのパラメータなどがあるが，それらのパL を増加させると計算時間が線形に増加するため，ラメータは，並列化をしないなどの統一を行った．

STEP II では，式 8 をみたす範囲でハッシュテーブ評価実験の結果を表 3 に示す．2 つのプロジェクル数 L を最小の値に決定する．

トについて，目標再現率 0.99 のために決定したパラSTEP II の式 8 は以下の定理 1 に従う．

メータが再現率 0.99 を満たすことが確認できた．ま定理 1. ある目標再現率 R に対して，FALCONN のた，FALCONN のデフォルトのパラメータよりも高衝突確率 P rL (x, y) が式 8 を成り立たせるとき，再速に処理が完了した．そのため，本手法で決定したパ現率の期待値は R 以上となる．

ラメータは R 類似探索の条件を満たす．

Proof. 2. 2. 3 節より，P rL (x, y) は L 個のハッシュ

FALCONN のデフォルトのパラメータのとき，再テーブルに対する衝突確率を表し，ある１つの類似現率が１となったことから，時間をかけて処理するパペアが検出できる確率と言える，|Sall | 個のベクトルラメータにしていると考えられる．また 2 章で，ブ対は，それぞれ確率 P rL (x, y) で衝突するから，衝突ロッククローン検出法において検出漏れがあったことする衝突するベクトル対の数は二項分布に従う．よっを述べたが，それは検出時間を削減するために検出漏て，検出できるベクトル対の数の期待値 E は式 10 でれが起こるパラメータに変更したためであると考え求められる．

E = |Sall | × P rL (x, y)(10)†2 CPU Intel Xeon 2.80GHz 4core，メモリ 32.0GB，
OS Windows 10 64bit. Java 仮想マシンのスタック
領域 1GB，ヒープ領域 15GB

表1

表2

対象プロジェクト

プロジェクト

行数

コードブロックの数

単語の数

クローンペアの数

PostgreSQL

1,138,235

24,788

11,937

8,291

Linux Kernel

17,474,091

424,236

78,675

117,490

ローンペアの特徴に関する調査

FALCONN に与えるパラメータ

PostgreSQLLinux Kernel• 任意の目標再現率や閾値における速度と再現率

デフォルト

本手法T21024

L104T

321024

L104の評価• 他のコードクローン検出法に対する有効性の評価
謝辞 本研究は JSPS 科研費 25220003，16K16034，15H06344 の助成を受けた．
参 考 文 献

表3

実験結果

デフォルト

PostgreSQLLinux Kernel

本手法

計算時間

5m 2s

10s

再現率

1.0000.998

6h 45m 10s

20m 6s1.0000.998

計算時間
再現率

られる．実験結果から，本手法によって決定したパラメータで R 類似探索を行えることが確認できたため，本手法の有効性が確認できた．

6 まとめと今後の課題
本研究では，ブロッククローン検出法が用いる LSHのパラメータの解析を行い，R 類似探索を行うためのパラメータ決定手法を提案した．そして，本手法をブロッククローン検出法に適用し，２つの異なる規模のプロジェクトに対してコードクローン検出を行った．
その結果，デフォルトのパラメータより短時間で，目標再現率 R 以上となることを確認した．
今後の課題として，以下が挙げられる．

• BigCloneBench [5] を用いて，検出漏れとなるク[ 1 ] Alexandr, A. and Piotr, I.: Near-Optimal Hashing Algorithms for Approximate Nearest Neighborin High Dimensions, Foundations of Computer Science, Vol. 51, No. 1(2006), pp. 117–122.
[ 2 ] Alexandr, A., Piotr, I., Thijs, L., Ilya, R., andLudwig, S.: Practical and Optimal LSH for AngularDistance, Proc. of NIPS 2015, 2015, pp. 1225–1233.
[ 3 ] Alexandr, A., Thijs, L., Ilya, R., and Erik, W.:
Optimal hashing-based time-space trade-oﬀs for approximate near neighbors, Proc. of SODA 2017,2017, pp. 47–66.
[ 4 ] Baeza-Yates, R. and Ribeiro-Neto, B.: Modern
Information Retrieval: The Concepts and Technology behind Search, Addison-Wesley, 2011.
[ 5 ] Jeﬀrey, S., F, I. J., Iman, K., K, R. C., and Mamun, M. M.: Towards a big data curated benchmarkof inter-project code clones, Proc. of ICSME, 2014,
pp. 476–480.
[ 6 ] 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.
[ 7 ] 横井一輝, 崔恩瀞, 吉田則裕, 井上克郎: 情報検索技術に基づくブロッククローン検出, 電子情報通信学会技術研究報告, Vol. 117, No. 136(2017), pp. 109–116.
[ 8 ] 山中裕樹, 崔恩瀞, 吉田則裕, 井上克郎: 情報検索技術に基づく高速な関数クローン検出, 情報処理学会論文
誌, Vol. 55, No. 10(2014), pp. 2245–2255.
[ 9 ] 徳井翔梧, 吉田則裕, 崔恩瀞, 井上克郎: 局所性鋭敏型ハッシュを用いたコードクローン検出のためのパラメータ決定手法, Vol. 117, No. 477, 2018, pp. 57–62.
[10] 肥後芳樹, 楠本真二, 井上克郎.: コードクローン検出とその関連技術, 電子情報通信学会論文誌 D, Vol. 91,
No. 6(2008), pp. 1465–1481.