情報処理学会研究報告
IPSJ SIG Technical Report

LSH アルゴリズムを利用した類似ソースコードの検索
川満 直弘1,a)

石尾 隆1,b)

井上 克郎1,c)

概要：本研究では，再利用されたコードの出自を調べるための方法として，与えられたソースファイルに対し，類似するソースファイルを高速に検索する手法を提案する．内容が同一のものだけでなく類似するものを含めて出力することで，再利用の際に変更が加えられているソースファイルにも対応する．また，大量のソースファイルの中から検索を行うため，locality-sensitive hashing を利用することにより，高速な検索を可能にする．この手法によって，再利用したコードの出自を知ることが可能になる．
C 言語で記述された再利用されているライブラリを対象にケーススタディを行った．対象の中にはプロジェクト独自の変更が加えられ，再利用元ファイルと一致しなくなっているものも含まれていた．その結果，92%の精度で 200 プロジェクトの中から再利用元のソースファイルを検出することができた．また，4ファイルを使用し検索の実行時間を測定したところ，各ファイルについて 1 秒以内で検索を完了した．

1. はじめにンを検出する手法を提案した [12]．この手法では再利用元のリポジトリを用意しなければならない．

ソフトウェアの開発において，他プロジェクトで開発し本研究では，与えられたソースファイルに対し，類似すたソフトウェアの再利用が頻繁に行われている．プロジェ

るソースコードを高速に検索する手法を提案する．検索の

クト独自の変更が必要な場合やコンパイル手順を簡単に高速化のために，locality-sensitive hashing[7] を利用する．

したい場合には，再利用元プロジェクトのソースコードを提案手法では，まず検索の対象となるソースファイルをコピーして取り込む，という方法で再利用が行われる．こデータベースに登録する．この際，LSH アルゴリズムを利のような再利用には利点がある一方，再利用したコードに用するために，ソースファイルを MinHash[2] の値からな含まれる不具合を取り込んでしまう虞がある．再利用したるベクトルに変換する．検索を行う際には，同様に対象のコードを管理するためには再利用したコードがどのプロ

ソースファイルをベクトルに変換し，そのベクトルを用い

ジェクト，バージョンのものなのかに関する情報が必要でて検索を行う．

ある．しかしながら，すべてのプロジェクトにおいてその手法の評価のために，2 ケースを利用して手法の妥当性

ような情報が記録されているわけではないことが判明してを評価した．さらにケーススタディとして実際に再利用さいる [20]．

れたコードに対し手法を適用し，記録されている再利用元

再利用したソースファイルに対し，もしファイルの内容が一致するものが他のプロジェクトに存在するならば，そが検出できるか評価を行った．また，手法に要する時間についても評価した．

のプロジェクトに由来する可能性があるといえる．しかし，以降，2 章では関連研究について述べる．3 章では本研再利用の際にコードに変更が加えられることがあり，その究での提案手法について述べ，4 章では本研究においての場合にはソースファイルが単純に一致するかどうかを判定

実装について述べる．5 章では行ったケーススタディにつする，という方法では不十分である．出自を求める既存研

いて述べ，6 章で妥当性への脅威について述べる．最後に，究として，Inoue ら [8] は Ichi Tracker というシステムを提7 章を本研究のまとめとする．

案した．このシステムは，コード片をクエリとし，コード
検索エンジンを利用して検索を行う．また，我々のグルー
プでは，リポジトリ中のソースコードを対象に，バージョ
1

a)
b)
c)

大阪大学大学院情報科学研究科
Osaka University, Suita, Osaka 565-0871, Japann-kawamt@ist.osaka-u.ac.jp
ishio@ist.osaka-u.ac.jp
inoue@ist.osaka-u.ac.jp

c 2016 Information Processing Society of Japan⃝

2. 関連研究2.1 ソースコードの再利用
開発者はソフトウェアを開発する際に，他プロジェクトで開発したソフトウェアを再利用しながら開発を行っている．

Heinemann ら [6] はオープンソースの Java のプロジェクト
を対象に調査を行い，バイナリでの再利用である black-box

1情報処理学会研究報告
IPSJ SIG Technical Reportreuse がソースコードの再利用である whilte-box reuse よ時，どのプロジェクトのコードか，どの程度クエリの内容

り優勢であったことを報告した．また，Rubin ら [18] は企を含んでいるか，などの情報が得られる．

業内において，開発したソフトウェアから新しい製品の開我々の研究グループ [12] ではリポジトリに含まれている発に利用するために，再利用を行っていることを報告してソースコードについて，バージョンを推定する手法を提案いる．

した．ソースコードの類似度として最長共通部分列に基づ再利用をすることによって開発のコストを抑え，ソフト

いた類似度 [11] を使用し，もっとも類似度の高いものがウェアを効率的に開発することが可能になる．再利用され再利用元であるという仮定に基づいてバージョンを提示したコンポーネントはそうでないものより不具合が少ないこた．この手法には入力として再利用を行ったリポジトリととが Mohagheghi らによって報告されている [15]．

その再利用元のリポジトリが必要なため，再利用元が不明

開発者が再利用を行う際にプロジェクト独自の変更が必要な場合は利用することができない．

な場合，ソースコードを開発中のプロジェクトに取り込む，という方法がとられることがある．例えば，v8monkey*1 で

2.2 Locality-Sensitive Hashing による検索

は，APNG(Animated Portable Network Graphics) フォー

本研究ではソースファイルの再利用を検出するという問

マットに対応するための修正を libpng*2 のライブラリに加

題を，クエリとして与えられたファイルに類似したソース

えている．

ファイルを見つける問題の一種ととらえる．大量な検索対

ソースコードの再利用は有用である一方，バグやセキュ

象に対する高速化のために locality-sensitive hashing(以下リティに関する脆弱性を抱えているものを使用しないよ

LSH とも表記) を用いる．LSH は近似最近傍検索や，クラう，開発者は注意しなければならない．Xia ら [20] はオースタリングに用いられるアルゴリズムである [7]．

プンソースのライブラリのコードを再利用しているプロ

LSH には複数の適用例がある．Manku ら [14] は，Web

ジェクトについて，使用しているライブラリが脆弱性をでのクローリングにおいて，内容がほぼ重複している Web

抱える可能性のあるバージョンであるかどうかを調査しページを検出するための手法を提案した．Das ら [3] は，た．その結果，調査対象としたプロジェクトのうち，zlib

Google News のために協調フィルタリングを使用し，ユーを利用しているプロジェクトでは 31.1%，libcurl を利用しザの行動から記事を推薦する手法を提案した．Brinza ら [1]ているプロジェクトでは 85.7%，libpng を利用しているプは，ゲノムワイド関連解析において遺伝子座のクラスタリ

ロジェクトでは 92%のプロジェクトが，脆弱性を抱える可ングのために利用した．Jing ら [10] は，画像検索のために能性のあるバージョンを利用していることが判明した．さLSH を利用している．

らに，18.7%のプロジェクトには使用したライブラリにつLSH はソースコードにおいても利用されている．Jiang

いて，どのバージョンを利用したかに関する情報が残ってら [9] らは，類似する部分木を高速に検出する手法をソースいなかった．加えて，4.9%のプロジェクトではディレクト

コードに用いることでクローンの検出を実現しているが，リ名が変更されたり，再利用したソースコードに他のソー部分木の特徴ベクトルに対しクラスタリングを行うためにスコードが混ぜられ，管理することが難しい状態になってLSH を利用した．山中ら [21] は TF-IDF 法を特徴量とし，いることが判明した．このような管理のされていないプロ

クラスタリングを行ってタイプ 4 の関数クローン検出の手ジェクトに対して，再利用元を特定することは有用である法を提案したが，高速な検出を行うために特徴ベクトルのと考えられる．

クラスタリングに LSH を利用している．

ソフトウェアの再利用の検知は，バイナリを対象としたものやソースコードを対象としたものがある．バイナリを

3. 提案手法

対象としたものとして，Davies ら [4], [5] は Java のバイナ

本研究では，検索のクエリとして与えられたソースファ

リから，クラス中のシグネチャを利用する手法を提案した．

イルに対し，大量のソースファイルの中からソースコードSæbjørnsen ら [19] は実行ファイルのバイナリからのコーの内容がクエリに類似するものを検索する手法を提案す

ドクローン検出手法を提案した．Qiu ら [17] は，バイナリ

る．LSH を用いることにより，高速な検索を可能にする．

からライブラリの関数を特定する手法を提案した．

本手法ではさらに，検索された結果に対して類似度の推

Inoue ら [8] は，Ichi Tracker というシステムを提案した．

定値を提示する．この推定値は効率的に求めることができ，

これは，コードの断片などをクエリとし，そのコード片の検索結果に含まれる各ソースファイルについて，推定値でクローンを含むソースコードをコード検索エンジンを使用はあるがクエリとの類似度を個別に知ることができる．

して検索する．システムの出力として見つかったクローン

まず本手法で用いるソースファイル間の類似度を定義

とともに，各クローンについてそのクローンの最終変更日

し，LSH について説明したのち，提案手法と詳細について*1*2

https://github.com/zpao/v8monkey
http://www.libpng.org/pub/png/libpng.html

c 2016 Information Processing Society of Japan
⃝

説明する．

2

情報処理学会研究報告
IPSJ SIG Technical Report

3.1 ソースファイル間の類似度の定義

1

r=4, b=120
r=8, b=120
r=16, b=120

本研究で用いるソースファイル間の類似度は，n-gram とJaccard 係数を利用した類似度である．この類似度を用いる利点として，関数単位の並べ替えなどの影響を過度に受けないという利点がある．また，TF-IDF 法のように，類似度を求める対象の 2 ファイル以外は類似度に影響することはない．具体的な計算方法は，以下のステップからなる．

(1) ソースファイルの字句分割

0.8
0.6
0.4
0.2
0

ソースファイル s からコメントを取り除き，字句の列に

0

0.2

0.4

0.6

0.8

1

p

分割し，Ts を得る．コメントを取り除くことで，コメント量の大小や，コメントの違いが類似度に影響を与えること

図 1 同じバケットに入る確率を防ぐ．ソースファイル t にも同様の操作を行い，字句列

Fig. 1 Probabilities of mapping to the same bucket

Tt を得る．
(2) 字句列からの n-gram の抽出1 である．類似度として Jaccard 係数を用いる場合，F と字句列 Ts から長さ n の部分文字列を取り出すことにより，n-gram の多重集合 Ms へ変換する．

して MinHash が利用可能である．

MinHash は，集合間の類似度を高速に推定する手法であ

たとえば，n = 3 のとき，要素列 e1 , e2 , e3 , ..., em に対しる．集合中の各要素についてハッシュ値を求め，その中のて得られる n-gram は，{{($, $, e1 ), ($, e1 , e2 ), (e1 , e2 , e3 ),最小値を求める．同様の操作を別の集合に対しても行った(e2 , e3 , e4 ), ..., (em−1 , em , $), (em , $, $)}} となる．ただし，時，それら 2 つの最小値が一致する確率は，2 つの集合に要素$は要素列の先頭および末尾の要素に付加するダミー

対する Jaccard 係数に等しい．

の要素である．先頭及び末尾にダミーの要素を付加するこ

文献 [13] の方法を用いて LSH を構成する．2 集合につとによって，列のすべての要素が n 個の n-gram に含まれいて考える．ハッシュ関数を r × b 個用意し，各集合につる．同様にして，字句列 Tt から多重集合 Mt を得る．

いて r 次元の MinHash の値からなるベクトルを b 個求め(3) n-gram の多重集合からの集合への変換

る．2 集合間において，各ハッシュ関数に対応するベクト多重集合 Ms の各要素に番号を付加することによって集ル同士を比較する．この時，2 集合間での MinHash の値が合に Ss に変換する．各要素に付加する番号は，ある要素一致する確率，すなわち Jaccard 係数を p とすると，b 個

e について，変換前の多重集合に要素 e が k 個含まれていのベクトルのうち 1 つ以上のベクトルが一致する確率は，る場合，各要素に 1 から k の値が付加される．

1 − (1 − pr )b で表される．これらのベクトルをハッシュ

たとえば，要素 a, b, c からなる多重集合 {{a, a, b, b, b,

テーブルのキーとし，ベクトルが一致した場合に同じバc}} をこの手法により集合に変換した場合，得られる集合

ケットに入っていると扱うことにより，類似度 p の要素同は {(1, a), (2, a), (1, b), (2, b), (3, b), (1, c)} となる．

士が確率 1 − (1 − pr )b で同じバケットに入る，ということ同様にして，多重集合 Mt から集合 St を得る．ただし，を実現する．

付加する番号は Ms に依存せず，Ms と Mt に同じ要素が

図 1 に，実際にパラメータの値を与えた際の 1 − (1 − pr )b

含まれていたとしても，Mt から St に変換する過程で付加のグラフを示す．パラメータは b = 120 であり，r についする番号は 1 から順に与える．

ては r = 4, r = 8, r = 16 の 3 通りである．図に示すとお(4) 集合に対する Jaccard 係数の算出

り，パラメータを調整することで，同じバケットに入る確

ソースファイル s, t の類似度を，集合 Ss と St を用いて率を調整することができる．

以下の式で算出する．

Jaccard(Ss , St ) =|Ss ∩ St ||Ss ∪ St |3.3 LSH を利用したソースファイルの検索提案手法は，データベース上で LSH を利用した検索を行う．データベースを用いることにより，検索対象のファ

3.2 Locality-Sensitive Hashing
locality-sensitive hashing は類似検索に利用される手法

イル数が大きく，必要なデータすべてを主記憶に収めることができない場合にも対応する．

の一つである [7]．本研究では，以下の式で表される関係

手法は 2 つのステップからなる．登録ステップでは複数が成り立つハッシュ関数の族 F を利用して LSH を構成すのソースファイルを入力し，データベースに登録する．検る [16]．

索ステップでは，クエリとなるソースファイル q を与え，

Prh∈F [h(x) = h(y)] = sim(x, y)

検索結果である類似ファイルの集合と，それぞれの結果の

ただし，sim(x, y) は x, y 間の類似度であり，0 ≤ sim(x, y) ≤ファイルとソースファイル q との類似度の推定値を出力

c 2016 Information Processing Society of Japan⃝3

情報処理学会研究報告
IPSJ SIG Technical Report

する．

0.18

3.3.1 検索対象のデータベースへの登録

r=2, b=120
r=4, b=120
r=8, b=120

0.16

このステップでは，検索の対象となるソースファイルを

0.14
0.12

入力とし，データベースに登録する．

0.1

まず LSH を構成する MinHash において使用するハッ0.08

シュ関数を R × B 個用意する．R, B は LSH の検索パラ

0.06

メータ r, b の上限となる．用意するハッシュ関数は番号

0.04
0.02

の付加された n-gram からハッシュ値への関数であり，そ0

れらを hi とする．ただし，1 ≤ i ≤ R × B である．次に

0

0.2

0.4

0.6

0.8

1

p

検索の対象となるソースファイルをデータベースに登録するが，登録する情報はソースファイル 1 件に対し，各

図 2

ハッシュ関数から求められる MinHash の値もデータベー

Fig. 2 MSEs of the estimator when b = 120

b = 120 の場合の推定量の平均二乗誤差スに登録する．hi を用いてソースファイルから MinHash

L(p) = (p ) (1 − p )r xの値を求める関数を mi と表す．ソースファイル f に対

r b−x

( )
b
x

し，番号の付加された n-gram を g ，ソースファイルから番号の付加された n-gram の集合への関数を G とすると，で表される．したがって，類似度 p に対する最尤推定量 p̂

mi (f ) = ming∈G(f ) hi (g) である．mi を利用し，ソース

は，0 ≤ p ≤ 1 であることを踏まえると，√

ファイル f に対し，m1 (f ), m2 (f ), ... , mR×B (f ) を同時p̂ = rに登録する．
この登録した MinHash の値を利用して LSH を構成し検索を行うため，検索の高速化のためにインデックスを作成する．R 個の MinHash の値を一組とし，B 組それぞれに対してインデックスを作成する．すなわち，(m1 (f ), m2 (f ),... , mR (f )) を 1 組としてインデックス I1 ，(mR+1 (f ),mR+2 (f ), ... , mR×2 (f )) を 1 組としてインデックス I2 ，というようにインデックスを構成し，合計 B 組のインデックスを構成する．

3.3.2 類似ソースファイルの検索
このステップでは，与えられたソースファイルに類似するソースファイルを，データベースから検索する．検索には，クエリとなるソースファイルに加え，LSH のパラメー
タ 1 ≤ r ≤ R, 1 ≤ b ≤ B を与える．与えられたソースファ
イルに対して MinHash の値を求め，その値から検索を行う．1 ≤ i ≤ b について，インデックス Ii を用いて，

xbとなる．ここに示す通り，類似度の推定値がとりうる値は，

x ≥ 1 の場合，b 通りに限定される．r = 1 の場合は推定値としてとりうる値の間隔は等しく，MinHash を用いてJaccard 係数を推定する方法そのものである．一方，r > 1の場合，推定値のとりうる値の間隔は 1 に近づくにつれ狭
くなり，1 に近いほど細かく，0 に近いほど粗くなる．
推定量の偏り B(p̂)，分散 V ar(p̂)，平均二乗誤差 M SE(p̂)
はB(p̂) =

b
∑

√
r

x=0

( )
x r x
b
(p ) (1 − pr )b−x
−p
b
x

√ )2
( )
x
r x
r b−x br
V ar(p̂) =(p ) (1 − p )
b
x
x=0
( b √
( ) )2∑ xbr(pr )x (1 − pr )b−x
−
b
x
b (
∑

x=0

M SE(p̂) = V ar(p̂) + (B(p̂))2Si (q) = {f |∀j ∈ [1, r].mj+R×(i−1) (q) = mj+R×(i−1) (f )}となる．
な る Si を 求 め る ．こ の 集 合 Si の 和 集 合 ，す な わ ち

例として図 2 にパラメータが b = 120 であり，r = 2, r =1≤i≤b Si (q) が検索の結果，つまりクエリと類似するソー

4, r = 8 の場合の推定量の平均二乗誤差について p の値を∪スファイルの集合である．
また，検索結果に含まれるそれぞれのソースファイルに対して，クエリとの類似度の推定値を併せて出力する．類
似度は最尤推定を用いて推定する．
検索結果中のある類似ソースファイルについて，集合

S1 , S2 , ..., Sb 中の x 個の集合に含まれているとする．類似度が p で表される時，r 次元のベクトルについて x 個のベクトルが一致し，b − x 個不一致となる確率，p に対する尤
度関数 L(p) は

c 2016 Information Processing Society of Japan⃝

変えながら図示した．横軸は p の値であり，縦軸は平均二乗誤差である．p の値が 1 付近に近づくと平均二乗誤差が0 に近づくことを示している．

4. 実装
4.1 類似度について手法の対象を C 言語のソースファイルとし，類似度で用いる n-gram の n の値として，n = 3 とした．
異なるファイル間での類似度と，同じファイルの別バー

4情報処理学会研究報告
IPSJ SIG Technical Report号，t1 , t2 , t3 は n-gram の要素，つまり字句に対する Java

表 1 データセット

Table 1 Datasetの hashCode メソッドの値，ai , bi はそれぞれハッシュ関数

パッケージ

バージョン#1

バージョン#2

ごとに用意する定数である．演算は 64bit で行われ，演算

original-awk

2012-12-20

2011-08-10

中のオーバーフローは下位 64bit が残される．ai は 64bit

mgcv

1.8-4

1.7-12seaview

4.3.1

4.5.3.1

乱数と 1 とのビット論理和をとることによって，bi は 64bit

fglrx-installer

8.960

15.200fglrx-installer-updates

15.2008.960

foreign

0.8.620.8.48

20140604

20120128

libhdhomerun

乱数によって用意した．

5. ケーススタディ
5.1 検索結果および類似度の推定値の評価

r-cran-eco

3.1-4

3.1-6

実際の検索において，クエリに対する類似度の高いもの

r-cran-xml

3.6-2

3.98-1.1

が検索の結果に表れ，類似度の低いものが結果に表れない

rt-tests

0.89

0.83

ということを確認するために，libpng および libcurl に対して実験を行った．

100

ンの c ファイル，h ファイルをデータセットとし，実験を行った．具体的には，git rev-list --all --objects

50

4e+04

Frequency

150

libpng のリポジトリ *3 中に含まれる，すべてのリビジョによって得られたリストの中から，.c ファイルおよび.h
0

0e+00

Frequency

8e+04

5.1.1 libpng の png.c

0.0

0.2

0.4

0.6

0.8

1.0

0.0

Similarity

0.2

0.4

0.6

0.8

1.0

Similarity

図 3 類似度の分布

Fig. 3 Distributions of similarity

ファイルを対象とした．対象のファイル数は 20977 である．libpng に含まれ，v1.6.0 のタグがついているコミッ
トのファイル png.c をクエリとして検索を行った．検索のパラメータは，r = 8, b = 120 である．
検索の結果に表れたファイル数は 716 であり，これはジョン間での類似度の違いについて調査した．調査には

データセット全体の 3.4%である．検索の結果に表れなかっUbuntu の apt で手に入るソースコード，10 パッケージ，

たものの中での類似度の最高値は 0.482 である．また，検505 ファイルを対象とした．表 1 に示す各パッケージの 2索に表れたものの中で類似度の最低値は 0.598 である．

バージョンの orig.tar.gz から得たソースコードを利用した．

図 4 に，検索結果中のファイルとクエリ間の類似度につ対象となったファイルすべての組み合わせの間で類似度いて，推定値と実際の値との関連を示す．x 軸は類似度のを求めた結果を図 3 に類似度に対する頻度として示す．左

推定値，y 軸は実際の類似度を表す．

図はパッケージが異なり，かつファイル名も異なるファイ

5.1.2 libcurl の url.c

ル間での類似度を表しており，右図は同一パッケージ，同

libcurl のリポジトリ *4 に含まれる，すべてのリビジョ

一パス，同一ファイル名であり別の tar ファイル，つまりンの c ファイル，h ファイルをデータセットとし，実験をバージョンが異なるファイル間の類似度を表している．左行った．対象のファイル数は 23273 である．libcurl に含ま

図には 113735 件の類似度が含まれており，右図には 245

れ，curl-7 47 0 のタグがついているコミットの url.c を件の類似度が含まれている．ただし，右図中で 101 件につクエリとして検索を行った．

いて，類似度が 1.0 であった．この結果より，3-gram を

検索の結果に表れたファイル数は 374 ファイルであり，使用した類似度は二つのファイルが同一ファイルの別バー

これはデータセット全体の 1.6%である．検索の結果に表ジョンか否かの判別に有効と考えられる．

れなかったものの中での類似度の最高値は 0.578 である．
また，検索に表れたものの中での類似度の最低値は 0.572

4.2 ハッシュ関数についてである．

提案手法では番号の付加された n-gram に対するハッシュ関数を複数用意する必要がある．今回は，簡便な方法

5.2 ファイルの出自検索能力の評価

として以下のような実装を行った．
番号の付加された 3-gram(num, t1 , t2 , t3 ) に対するハッ類似度の推定値を用いて再利用元のプロジェクト，ファイル，バージョンを特定することができるかケーススタ

シュ関数 hi によるハッシュ値は，ディを行った．ケーススタディの対象は，v8monkey*5 中(((num × 65537) + t1 ) × 65537 + t2 ) × 65537 + t3 ) × ai + bi

*3*4によって求める．ただし，num は 3-gram に付加された番

c 2016 Information Processing Society of Japan⃝*5

git://git.code.sf.net/p/libpng/code
https://github.com/bagder/curl.git
https://github.com/zpao/v8monkey.git

5情報処理学会研究報告
IPSJ SIG Technical Report
表 2

分類の結果

1.0

Table 2 Categorized results

●
●
●
●
●●
●
●
●
●
●
●
●
●
●

基準 1

●
●
●
●
●
●
●
●
●
●
●
●
●
●

0.9

基準 2 を満たす
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●● ●
●●●
●
●
●
●●●
●●●● ●

0.8

●●
●
●●
●

基準 2 を満たさない
計

●

満たす

満たさない

計

177

10

187

5

5

10

182

15

197

●
●●
●
●
●●
●
●
●●
●

0.7

●
● ●

●
●
●
●

●
●●
●
●

とした．

●

●
●
●

検索の結果，すべての結果について再利用元の該当する

●

0.6

●
●
●
●
●

バージョンのファイルが検索結果に表れた．クエリ 197 件に対し，検索結果に表れたファイルの数の合計は，120001●件であった．各クエリで検索結果に表れるファイル数は，
0.5

最低 167 件，最高 1031 件，平均 609 件であった．検索結
0.5

0.6

0.7

0.8

0.9

1.0

果には libpng のファイル以外に，libpng を利用している 3
プロジェクト計 97 件含まれていた．
さらに，各クエリについて，類似度の推定値が検索結果

図 4

png.c をクエリとした際の類似度の推定値と実際の類似度

Fig. 4 Estimated values of similarity and actual value of similarity when the query is png.cに表れる類似度の推定値の中での最高値になるかどうかを調査した．結果の理解のために，2 つの基準から結果を 4つに分類した．

に含まれる libpng のソースコードである．v8monkey には

基準 1 再利用元のバージョンの類似度の推定値が，検索複数のコミットメッセージに，libpng のどのバージョン

結果に表れる類似度の推定値の中での最高値になるに更新したかが記録されており，複数のソースコードに

基準 2 検索結果に表れたファイルの中で，再利用元のバー

Animated Portable Network Graphics フォーマットに対ジョンの類似度の真の値が，検索結果に表れた類似度応するためと思われる変更が行われている．

の真の値の中での最高値になる

検索の対象として，libpng プロジェクトを含む 200 プロ

基準 2 の対象が検索結果に表れたファイルに限られている

ジェクトのリポジトリを用意した．これらのプロジェクトのは，時間の制約上データベースすべてのファイルに対しは，GitHub において 2016 年 1 月 31 日に”lib language:c”

197 件のクエリとの類似度の真の値を求めることができなというクエリを用いて検索を行い，その検索結果の上位

いためである．この分類結果を表 2 に示す．

200 件のリポジトリを同年 2 月 1 日に得たものである．

クエリとなる対象の 197 件のうち 182 件は基準 1 を満実験の手順として，まず検索対象のプロジェクト中の，たす，つまりクエリと記録されている再利用元との類似度

履歴中に含まれるすべての.c ファイルおよび.h ファイルをの推定値が，検索結果に表れる類似度の推定値の最高値とデータベースに登録した．登録された件数は 567113 件で等しくなった．基準 1 を満たすクエリについて，各クエリある．次に v8monkey のコミットのうち libpng のどのバーの検索結果中で類似度の推定値が最高値をとるファイル数

ジョンにアップデートしたかが明記されているコミットをは，最低 1 件，最高 56 件，平均 11 件であった．さらに，列挙した．この条件を満たすコミットは計 14 件見つかっ

基準 1 を満たすクエリの各検索結果に含まれる類似度の推た．それらのコミットで新たに加えられた，もしくは変更

定値が最高値をとるファイルを対象に，コメント，フォー

されたファイルのうち，modules/libimg/png 以下に含まマットの違いを無視して重複を取り除いた数を求めた．たれるファイルをクエリとし，検索を行った．ただし，以下

だし，重複の検出には md5 チェックサムを用いた．そののファイルについては評価対象から除外した．

結果，重複を取り除いたファイル数は，最低 1 件，最高 18• コメントのみからなるソースファイル．

件，平均 2.3 件となった．

• mozpngconf.h．このファイルは libpng に存在しない

基準 1 を満たさない 15 件のクエリについては，検索結ファイルであり，v8monkey の開発者が追加したもの

果ごとに類似度の推定値を降順に並べたとすると，記録さと思われる．

れているバージョンの順位は，2 位から 14 位，平均して対象となったファイルは，18 ファイル，延べ 197 件であ

5.3 位であった．

る．このうちの 57 件については，再利用元のファイルと内

基準 2 を満たしたクエリは 197 件中 187 件であった．残容が一致し，それ以外の 140 件は再利用元とファイルの内りの 10 件は，再利用元のバージョンとクエリとの類似度

容が一致しなかった．検索のパラメータは，r = 8, b = 120

が真の値でも最高値をとらないものである．したがって，

c 2016 Information Processing Society of Japan⃝6

情報処理学会研究報告
IPSJ SIG Technical Report
表 3

検索クエリとして用いるソースファイル

ベクトル

検索結果

の一致数

の件数

0

0

525

27,513

1,590

51,254

LOC

サイズ

[B]

0

mozpngconf.h

1

pngwrite.c

14,842503

2pngwtran.c

26,355453

572

17,2793

pngrtran.c41,179818

4,296

147,369

●

600

ファイル名

●
●
●

500

ID

700

Table 3 Source files as search queries

類似度に真の値ではなく推定値を用いたことによる影響の

200

300

400

●

大きさは，基準 2 を満たす 187 件中のクエリのうち基準 1100●を満たさない 10 件，5.3%であると考えられる．

●

●

0

1

2

3

4

5

6

7

8

9

10 11 12 13 14 15

5.3 パフォーマンスの評価
提案手法のパフォーマンスについて評価した．実行環境の CPU は，Intel(R) Xeon(R) CPU E5-2620 が 2 プロセッ

図 5 データベースからの検索の実行時間

Fig. 5 Execution time of searching from the database

サであり，メモリは 64GB，OS は Windows(R) 7 Profes-

sional である．また，データベースや検索クエリのファイ

す．横軸は ID を，縦軸は実行時間をミリ秒で表している．

ルはすべて SSD に保存されている．

ここで，ID は 4 で除した値が表 3 に示す ID を，剰余がそ評価に使用するデータベースは，5.2 と同様である．

5.3.1 登録に対する評価のクエリが何番目に検索が行われたかを示す．例えば，IDが 4 の倍数になっているものはキャッシュをクリアしてかデータベースは 200 プロジェクトから合計 567113 件のら最初に検索された場合の結果を示しており，剰余が 3 でファイルを登録したものである．登録のために Git のリポある場合は他の 3 クエリを検索した後に該当するクエリをジトリから一度すべてのファイルを取り出してディレクト

検索した場合の結果を示している．

リに保存し，その後データベースへの登録を行った．取り出したファイルすべてをディレクトリから登録するために要した時間は 230 分であった．

6. 妥当性への脅威
本研究の実装では 64bit のハッシュ長を用い，ハッシュ5.3.2 検索に対する評価

関数の振る舞いが完全にランダムにふるまうことを仮定

検 索 の ク エ リ と し て ，v8monkey の コ ミ ッ トのし，その上でハッシュ値の衝突する確率が非常に低いとしmod-て衝突した場合の影響を考慮していない．しかしながら，

ules/libimg/png 以下に含まれている 4 ファイルを使用し実際に衝突が発生したのか，また衝突が発生していた場合

た．表 3 にそれらについて示す．検索に使用するベクトルの結果への影響についての検証をしていない．また，ハッのデータベース中で一致する数が多いほど実行時間がかかシュ関数の偏りがケーススタディの結果に影響を与えた可ることが予想されるため，その数が固まらないように 5.2

能性がある．

3a04be0690dﬀ135ec42784557fedbf6c572cd22で用いたクエリの中から選定した．また，ベクトルの一致ケーススタディで検索のクエリとして用いたプロジェク

数が 5.2 で用いたクエリの中で最大になるものを含めた．

トは，1 プロジェクトのみである．このため，他のプロジェ検索を行った際にデータベースの内容の一部を OS がメ

クトや，他の言語が利用されているプロジェクトに対し，

モリにキャッシュするため，後続のクエリの速度が先行す

この手法を適用した場合の有効性は本ケーススタディで確るクエリの検索の影響を受ける．このことを考慮し，4 つ認した有効性とは異なる可能性がある．

のファイルの検索の順序を全通り，つまり 4! = 24 通りの

5.2 で結果を分類するために設けた基準 2 において時間

順序で検索を行い，その実行時間を測定した．24 通りのの制約上，類似度を求める対象を検索結果に表れたファイ

それぞれの検索の間で OS のキャッシュをクリアし，同一ルのみに限定した．しかしながら，検索結果に表れなかっファイルの検索がキャッシュに影響されないようにした．

たファイルの中に，クエリとの類似度が検索結果に表れた

まず検索クエリとなるソースファイルをディスクから読
み出し，MinHash のベクトルに変換するまでの時間について集計した．その結果，中央値は ID0 から 3 までそれぞれ

47ms, 94ms, 63ms, 219ms であった．
次に，データベースからの検索にかかる時間を図 5 に示

c 2016 Information Processing Society of Japan⃝

ファイル以上になるものが存在する可能性がある．

7. まとめ本研究では，検索のクエリとして与えられたソースコー
ドのファイルに対し，大量のソースコードのファイルの中

7

情報処理学会研究報告
IPSJ SIG Technical Reportからソースコードの内容がクエリに類似するものを検索す[9]る手法を提案した．locality-sensitive hashing を用いることにより，高速な検索を実現した．ケーススタディでは，
別コミットに含まれるファイルを合わせた延べ 197 ファイ
ルを対象とし検索を行い，そのうちの全 197 件について，[10]

コミットメッセージに記録されていた再利用元を検索することができた．また，その中でも 182 件については記録されていた再利用元の類似度の推定値が，検索結果中の推定[11]

値の最高値となった．さらに，検索時間については 1 件につき 1 秒以内で検索を完了した．
提案手法は，検索のために 1 つのソースファイルを指定して検索を行う必要がある．今後の課題としては，プロ[12]

ジェクト全体のソースコードを与え，その中から再利用とそうでないものを判別することがあげられる．また，提案手法では 1 つのファイルについての情報しか利用していな
いが，入力として複数ファイルを与え，それらの情報を合[13]

わせて利用することで手法の精度の向上が期待できる．
謝辞 本研究は JSPS 科研費 25220003 の助成を受けた
ものです．

[14]

参考文献
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Brinza, D., Schultz, M., Tesler, G. and Bafna, V.:
RAPID detection of gene-gene interactions in genomewide association studies, Bioinformatics, Vol. 26, No. 22,
pp. 2856–2862 (2010).
Broder, A. Z.: On the resemblance and containment of
documents, Compression and Complexity of Sequences
1997. Proceedings, pp. 21–29 (1997).
Das, A. S., Datar, M., Garg, A. and Rajaram, S.: Google
News Personalization: Scalable Online Collaborative Filtering, Proceedings of the 16th International Conferenceon World Wide Web, WWW ’07, New York, NY, USA,ACM, pp. 271–280 (2007).
Davies, J., German, D. M., Godfrey, M. W. and Hindle,
A.: Software Bertillonage: Finding the Provenance of an
Entity, Proceedings of the 8th Working Conference on
Mining Software Repositories, pp. 183–192 (2011).
Davies, J., German, D. M., Godfrey, M. W. and Hindle,
A.: Software Bertillonage: Determining the provenanceof software development artifacts, Empirical Software
Engineering, Vol. 18, pp. 1195–1237 (2013).
Heinemann, L., Deissenboeck, F., Gleirscher, M., Hummel, B. and Irlbeck, M.: On the Extent and Nature of
Software Reuse in Open Source Java Projects, Proceedings of the 12th International Conference on Software
Reuse, Lecture Notes in Computer Science, Vol. 6727,
pp. 207–222 (2011).
Indyk, P. and Motwani, R.: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,
Proceedings of the Thirtieth Annual ACM Symposiumon Theory of Computing, STOC ’98, New York, NY,
USA, ACM, pp. 604–613 (1998).
Inoue, K., Sasaki, Y., Xia, P. and Manabe, Y.: Where
does this code come from and where does it go? – Integrated code history tracker for open source systems–, Proceedings of the 34th International Conference on
Software Engineering, pp. 331–341 (2012).

c 2016 Information Processing Society of Japan
⃝

[15]

[16]

[17]

[18]

[19]

[20]

[21]

Jiang, L., Misherghi, G., Su, Z. and Glondu, S.:
DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones, Proceedings of the 29th International Conference on Software Engineering, ICSE ’07,
Washington, DC, USA, IEEE Computer Society, pp. 96–
105 (2007).
Jing, Y. and Baluja, S.: VisualRank: Applying PageRank to Large-Scale Image Search, Pattern Analysis andMachine Intelligence, IEEE Transactions on, Vol. 30,
No. 11, pp. 1877–1890 (2008).
Kanda, T., Ishio, T. and Inoue, K.: Extraction of product evolution tree from source code of product variants,
Proceedings of the 17th International Software Product Line Conference, Tokyo, Japan, ACM, pp. 141–150(2013).
Kawamitsu, N., Ishio, T., Kanda, T., Kula, R. G., De
Roover, C. and Inoue, K.: Identifying Source Code Reuse
across Repositories using LCS-based Source Code Similarity, Proceedings of the 14th International Working
Conference on Source Code Analysis and Manipulation,
pp. 305–314 (2014).
Leskovec, J., Rajaraman, A. and Ullman, J. D.: Miningof Massive Datasets, chapter 3, Cambridge University
Press (2014).
Manku, G. S., Jain, A. and Das Sarma, A.: Detecting
Near-duplicates for Web Crawling, Proceedings of the
16th International Conference on World Wide Web,
WWW ’07, New York, NY, USA, ACM, pp. 141–150(2007).
Mohagheghi, P., Conradi, R., Killi, O. M. and Schwarz,
H.: An empirical study of software reuse vs. defectdensity and stability, Proceedings of the 26th International Conference on Software Engineering, pp. 282–291(2004).
Moses S., C.: Similarity Estimation Techniques from
Rounding Algorithms, Proceedings of the Thiry-fourth
Annual ACM Symposium on Theory of Computing,
STOC ’02, New York, NY, USA, ACM, pp. 380–388(2002).
Qiu, J., Su, X. and Ma, P.: Library Functions Identification in Binary Code by Using Graph Isomorphism Testings, Proceedings of the 22nd IEEE International Conference on Software Analysis, Evolution, and Reengineering, pp. 261–270 (2015).
Rubin, J., Czarnecki, K. and Chechik, M.: Managing
Cloned Variants: A Framework and Experience, Proceedings of the 17th International Software ProductLine Conference, pp. 101–110 (2013).
Sæbjørnsen, A., Willcock, J., Panas, T., Quinlan, D. and
Su, Z.: Detecting Code Clones in Binary Executables,
Proceedings of the 18th ACM International Symposium
on Software Testing and Analysis, ACM, pp. 117–128(2009).
Xia, P., Matsushita, M., Yoshida, N. and Inoue, K.:
Studying Reuse of Out-dated Third-party Code in Open
Source Projects, JSSST Computer Software, Vol. 30,
No. 4, pp. 98–104 (2013).
山中裕樹， 崔恩瀞，吉田則裕，井上克郎：情報検索技術に基づく高速な関数クローン検出，情報処理学会論文誌，Vol. 55, No. 10, pp. 2245–2255 (2014).

8