VOL. J103-D NO. 7
JULY 2020
本PDFの扱いは、電子情報通信学会著作権規定に従うこと。
なお、本PDFは研究教育目的（非営利）に限り、著者が第三者に直接配布することができる。著者以外からの配布は禁じられている。

論文

軽量な類似度計算によるプロジェクト間のソースファイル集合の再利
用検出
伊藤

薫† a)

石尾

隆†,††

神田

哲也†

井上

克郎†

Source File Set Reuse Detection between Projects with Lightweight Similarity Calculation
Kaoru ITO†a) , Takashi ISHIO†,†† , Tetsuya KANDA† , and Katsuro INOUE†

あらまし ソフトウェア開発の現場において，オープンソースソフトウェアのソースコードをコピーして再利用することが一般的に行われている．ソフトウェアの再利用は，独自に開発した場合と比べて品質を向上させる
が，プロジェクトの開発期間が長くなるにつれ，どこから，どのバージョンをコピーしたのかという情報が失われてしまうことがある．そこで本研究では，分析対象ソフトウェアのソースファイルと再利用したライブラリの版管理システムのリポジトリの内容を比較し，再利用したバージョンを自動的に検出する手法を提案する．具体的には，局所性鋭敏ハッシュ(LSH) を用いた高速なファイル単位での類似度計算を導入し，ファイル単位の類似度の合計をライブラリのバージョン単位での類似度とし，最も類似度の高いバージョンを再利用元として検出する．再利用情報が記録されているオープンソースソフトウェアをデータセットとして提案手法を適用した結果，99.3%の割合で利用しているライブラリのバージョンを正しく検出することを確認した．
キーワード

b-bit MinHash，オープンソースソフトウェア，再利用分析，ソフトウェアリポジトリマイニング

1. ま え が きライブラリである zlib をコピーしたのち，独自のマク

ソフトウェア開発の現場において，オープンソー

いる．また，Google が開発するスマートフォン用 OS

ロを使用するよう zconf.h ファイルに記述を追加してスソフトウェア（Open Source Software，以降 OSS）

である Android のバージョン 8.0.0 は画像ファイルをを再利用することが一般的に行われている [1]．OSS

扱うライブラリである libpng を再利用しており，ファの再利用は，独自に開発した場合と比べて品質や信頼イルの一つ pngpread.c にバグ修正のパッチを適用し性の向上，機能の開発期間の短縮などの効果をもたらた状態で使用している．

す [2]．

再利用したライブラリのバージョン番号は，ソフト

ソフトウェア開発者は，しばしば，OSS として作らウェアの保守において重要な情報である．再利用した

れたライブラリのソースファイルを再利用して自身のライブラリに含まれる脆弱性や欠陥の影響を回避する

ソフトウェアに取り込む．ソースファイルは，常にそために，開発者はライブラリを新しいバージョンに更のまま使われるわけではなく，例えば Mozilla が開発新するか，修正パッチを適用しなければならない [3]．

している Gecko Engine では，ファイル圧縮に関する

脆弱性や欠陥の報告において，その影響範囲はバー†††

ジョン番号によって記述されることから，影響の有無
大阪大学大学院情報科学研究科，吹田市
Graduate School of Information Science and Technology, Os-を把握し適切な更新作業を実施するために，正しい

aka University, 1–5 Yamadaoka, Suita-shi, 565–0871 Japan

バージョン番号を把握することが必要となる．

奈良先端科学技術大学院大学先端科学技術研究科，生駒市
Graduate School of Science and Technology, Nara Institute

しかしながら，プロジェクトの開発期間が長くなる

of Science and Technology, 8916–5 Takayama-cho, Ikoma-

につれ，ソフトウェアをどこから再利用したのか，ソフshi, 630–0192 Japan

トウェアのどのバージョンを再利用したのかという情a) E-mail: ito-k@ist.osaka-u.ac.jp
DOI:10.14923/transinfj.2019JDP7077

542

電子情報通信学会論文誌報が失われてしまうことがある [4]．全てのソースファc 一般社団法人電子情報通信学会 2020
D Vol. J103–D No. 7 pp. 542–554 

論文／軽量な類似度計算によるプロジェクト間のソースファイル集合の再利用検出

イルについて内容を比較すると高コストだが，ソース

以降，2. では研究の背景について述べ，3. では提ファイルに編集が加えられていなければ，SHA-1 な案手法を詳しく説明する．4. では提案手法の評価を行

どのハッシュ値を各ソースファイルに対して計算する

い，5. で妥当性への脅威について述べる．最後に，6.

ことで，ソフトウェア中のソースファイルと一致する

でまとめを述べる．

ソースファイルをもつライブラリのバージョンを簡単に検出できる．しかし，先に紹介した例のように編集

2. 背

景

が加わっている場合には，単純な同一性の判定だけで

2. 1 起 源 分 析はバージョン情報を復元することができない．

起源分析とは，ソフトウェア内に存在するソース

本研究では，分析対象ソフトウェアのソースファイ

コードから，その作成に使われた（コピー元となった）

ル集合とライブラリのバージョンごとのファイル集合

他のソフトウェアやライブラリなどの起源を分析するとの間の類似度を比較することで，分析対象のソフト手法である．コピーされたソースコードは，編集されウェアが利用しているライブラリのバージョンを検出ていなければその起源を辿ることは容易いが，その後する手法を提案する．本手法は，既存手法 [5] で用いたそれぞれのソフトウェアに合わせて手を加える場合がファイル間の類似度の考え方をファイル集合に拡張し，あり，ソースファイルの類似性に着目した分析が行わ

ファイル集合間で最も似ているファイルの組におけるれている．

類似度の合計を集合間の類似度とすることで，ファイル

プロジェクト間でのソースファイルの再利用を検出集合全体として最も類似するライブラリのバージョン

するために，コードクローン検出と呼ばれる互いに同一つを自動的に検出する．また，局所性鋭敏ハッシュ

一または類似するコード片の組を検出する手法が適用（Locality Sensitive Hashing，以降 LSH）の一つでされている．German らは，複数のオープンソースプ

ある b-bit MinHash 法を用いたファイル比較により，ロジェクト間のコードクローンについて調査し，互いファイル間の類似度の高速な計算を実現する．この手にどの程度コードクローンをもつのか分析することで，法を用いれば，ソフトウェア開発者は再利用したライ

そのコードクローンの起源となるプロジェクトを特定

ブラリの更新が必要かどうか，ソースコードからバーした [7]．Inoue らは，インターネット上の OSS 中か

ジョン番号を高速に復元し，判断できるようになる．

ら，対象とするコード片に対するコードクローンを検本論文は著者らの発表内容 [6] を拡張したものであ出し，それらを時系列に並べることでその利用の変遷

る．発表 [6] では b-bit MinHash による類似度の推定を表示する Ichi Tracker を提案した [8]．また，Sasaki

値を真の類似度の計算の枝刈りのためだけに使用してらは，動作に影響のないコメントや空白を削除した場

いたが，本論文では類似度の推定値をそのまま合算す合のコードクローンに着目し，BSD 系 OS の一種でることでバージョンの検出に用いる．また，ライブラ

ある FreeBSD で利用されている OSS 同士でどのよ

リの名称はディレクトリ名等から判断ができる状況をうにソースコードが再利用されているか調査した [9]．

想定し，既存手法 [5] との比較実験を追加した．本論

Lopes らは，版管理システムの一種である Git のオン

文の貢献は以下のとおりである．

ラインホスティングサービスである GitHub 上で管理•

b-bit MinHash による類似度の推定値を直接合されているオープンソースプロジェクトについて，プ

算することでソースファイル集合の再利用元を高速かロジェクト間でどのくらい同一のソースファイルが使

つ正確に検出する手法を提案した．

われているか，どのようにコードクローンが分布して•提案手法が実用的であることをオープンソース

いるか分析した [10]．

ソフトウェアにおける実際の再利用の事例を用いた評

ソースファイルに含まれるバグや脆弱性の問題を調価実験で確認した．ソフトウェアの全てのバージョン

査するためには，ソフトウェアだけでなく，どのバーについてライブラリのどのバージョンを再利用していジョンを使っているかまで特定することが必要であるかを調べる場合，平均で 104 秒程度の処理時間で，る．そこで Kawamitsu らは，分析対象のソフトウェ

99.3%の割合で再利用しているライブラリのバージョ

アとライブラリのリポジトリを入力として，ソフトンを正しく判定することができた．従来手法 [5] では

ウェアのリビジョンごとにソースファイルがどのライ

最大で数時間の計算が必要であったが，それを大幅にブラリのバージョンから再利用されているか最長一致

短縮し，同時に正確さも向上している．

部分列を元に分析する手法を提案した [5]．Ito らは，543

電子情報通信学会論文誌 2020/7 Vol. J103–D No. 7

GNU/Linux OS の一種である Debian が公開していを高速に求める MinHash 法 [17], [18] が提案されているパッケージ集合をデータベース化し，入力されたる．Jaccard 係数は集合間の類似性を計測する指標でソースファイルと最も類似するソースファイルを検索あり，以下の式で表される．

するウェブサービスを提案した [11]．これらの手法はJ(S1 , S2 ) =ファイルごとに再利用元の候補となるバージョンを報|S1 ∩ S2 ||S1 ∪ S2 |告するが，複数のバージョンに同一のファイルが含まれることもあるため，ソフトウェアが再利用したライ

ここで S1 , S2 は，それぞれファイルの内容を表現しブラリ全体としてのバージョンは使用者が判断しなけた集合である．MinHash 法は，任意のハッシュ関数

ればならない．

hi が与えられたとき，以下のように集合 S からハッ

著者らは，入力をファイル単位からソースファイルの集合へと拡張し，データベース中から最も多く類似

シュ値が最小である要素を取り出す関数 mi (S) を使用する．

するソースファイルを含む OSS を検索する手法を提mi (S) = min hi (s)s∈S

案した [6]．Jewmaidang らは，ソフトウェアのリポジ
トリとライブラリのリポジトリを比較することで，ソフトウェアが利用しているライブラリのバージョンの変遷を可視化した [12]．

2. 2 類似度計算の高速化手法
起源分析においては，ファイル同士の類似度を高速に計算することが重要となる．Kawamitsu ら [5] は類似度としてファイル同士の最長一致部分列の長さを使用しているが，その計算には両方のファイルの長さの積に比例した時間が必要であり，様々な最適化を行った状態でも，合計数千万行のリポジトリの組の分析に最大で 4 時間程度かかることを報告している．

二つの集合 S1 , S2 に対して mi (S1 ), mi (S2 ) を計算す
ると，mi (S1 ) = mi (S2 ) となる確率が J(S1 , S2 ) に一致する．そのため，複数のハッシュ関数を用意すれば，
これらのハッシュ値の一致割合から，Jaccard 係数の推定値を求めることができる．

MinHash 法を省メモリで実現する方法として b-bit
MinHash 法 [19] が提案されている．この手法では，
MinHash 法で計算したハッシュ値 mi (S) の下位 b
ビットのみをハッシュ値として用いる．例えば b = 1のとき，b-bit MinHash 法のハッシュ関数 bi (f ) は以下の式で表される．

類似度の計算を高速化する方法として，ソフトウェ

bi (S) = LSB(mi (S))

アから類似したコード片の組を検出するコードクロー
ン検出技術では，比較すべき候補を事前に効率良く絞り込む手法が適用されている．Jiang らは，ソースコードから作成した木構造の断片について，LSH を用いてクラスタリングすることで高速にコードクローンを検出する手法を提案した [13] また，横井らは，ソー

ここでの LSB は Least Significant Bit を表す．
二つの集合 S1 , S2 に対して bi (S1 ) と bi (S2 ) が一致する確率 P (S1 , S2 ) は，集合間の Jaccard 係数と，偶然ハッシュ値の下位 b ビットが一致する確率の和となスコードから作成した TF-IDF ベクトルについて，る．ハッシュ値の下位 b ビットが偶然一致する確率はcross-polytope LSH を用いてクラスタリングし，コー

12bであるので，P (S1 , S2 ) は以下の式で表される．

ドブロック単位でのコードクローンを検出する手法を提案した [14]．Sajnani らは，転置インデクスを使ってP (S1 , S2 ) =



1
1
+
1
−
× J(S1 , S2 )2b2b比較すべき候補を絞ることで，効率的にコードクロー
ンを検出する SourcererCC を提案した [15]．しかし，最も時間計算量，空間計算量ともに少なくなるのがこれらの手法は，互いに類似したソースコード片が少

b = 1 のときであり，k 個のハッシュ関数を用いても kないことを仮定したものであり，起源分析のように，ビットの記憶域で済む．P (S1 , S2 ) の近似値として，k多数の類似ファイルから最も類似したファイルを選択

個のハッシュ値の一致割合 Po (S1 , S2 ) を用いて，前述のしたいという目的には適さない．

2. 3 b-bit MinHash 法を用いた類似度計算
類似度の計算そのものを高速化する手法として，類似度の一つである Jaccard 係数 [16] には，その推定値
544

式を変形した以下の式により集合 S1 , S2 間の Jaccard
係数の推定値 Je (S1 , S2 ) を計算することが可能である．


1
Je (S1 , S2 ) = Po (S1 , S2 ) −×2
2

論文／軽量な類似度計算によるプロジェクト間のソースファイル集合の再利用検出1
XOR(bi (S1 ), bi (S2 ))k i=1kPo (S1 , S2 ) = 1 −比較したいソースファイルをそれぞれ k ビットの列に変換すれば，ファイル間の相互の比較はそれらのビット
列の XOR 演算によって高速に実行することができる．

3. 提 案 手 法
ブラリから再利用したファイルを格納しているディレ
クトリ DQ とそのライブラリの版管理システムのリポ
ジトリ L を入力とし，DQ に再利用されているライ
ブラリのバージョン rQ と，ディレクトリ内のファイ
ル q ∈ DQ それぞれに最も類似したライブラリのバー
ジョン r[q] を出力する．入力をディレクトリとしたのは，再利用したライブラリのファイル群が一つのディレクトリにまとめて配置されることが多いためである．
再利用されたバージョンの情報を DQ 全体に対して一つ出力すると同時にファイルごとにも個別情報を出力するのは，全体としては古いバージョンのライブラリを利用している場合でも，例えば特定のファイルだけがセキュリティパッチの適用で新しいバージョンのものに差し替えられているといった状況を提示できるよ
うにするためである．なお，ここでのバージョンとは，開発者がライブラリを対外的に公開する，版管理シス
テムの中でタグと呼ばれるラベルが紐づけられている
リビジョンのことである．
提案手法は，DQ に含まれるソースファイルと，ライブラリの各バージョン v ∈ L に含まれるファイル群を比較し，最も類似したファイルを含むようなバー
ジョンを特定する．具体的には，ファイル間の類似度

sim(q, f ) が与えられたとき，ライブラリのあるバー
ジョン v に対する入力ファイル群の類似度の合計値

SQ (v) が最大となるような v を求める．入力ファイルの一つ q に対して，バージョン v の中で最も類似しているファイルの類似度 S(q, v) は，以下の式で定義される．ただし，ファイル間の類似度は，あるしきい
値 θ 以上の値の場合のみ記録し，θ 未満の場合は 0 とする．

Smax (q, v) =りである．

SQ (v) =S(q, v)q∈Dq

つまり，SQ (v) は S(q, v) を合計することで，DQ に提案手法は，分析対象のソフトウェアにおいてライ⎧⎨Smax (q, v),
S(q, v) =⎩0,の集合である．このとき，SQ (v) の定義は以下のとお

使われているファイルのどれだけの内容が v に由来するものかを表す．
図 1 に提案手法の動作例を示す．この図は，Query

DQ として与えられた 5 個のファイルに対して，Library L の三つのバージョンのうちどれを再利用したのか特定しようとした場合を示している．図 1(a) はDQ と L のある一つのバージョンとを比較する際の動作例を示している．DQ に含まれる全てのソースファ
イルについて，Smax (q, v) を計算する．この例では類似度のしきい値を θ = 0.8 としているため，Q.c では

Smax (q, v) = 0.0 となる．そのため，全体での類似度
は SQ (v) = 2.6 となる．この手順を L の全てのバー
ジョンにおいて行った結果が図 1(b) である．SQ (v) が最大となるのは，Version 2.0 のときであり，これをDQ が再利用しているライブラリのバージョンであると出力する．また，それぞれのソースファイルごとに，最も類似度が高いソースファイルが含まれるライブラ
リのバージョンも個別に出力する．この出力結果の場
合，DQ はライブラリ L の Version 2.0 を再利用している可能性が高いが，R.c という 1 ファイルのみ異なるバージョンが混ざった状態であることが判断できる．
この情報から，開発者はライブラリの更新やパッチの適用などの活動を行うことができるようになる．

SQ (v) を計算するためには，入力されたディレクト
リ DQ と，ライブラリ L に所属するファイルの総当たり比較が必要となる．そこで，本研究では高速化のために b-bit MinHash 法を用いた類似度計算を採用す
る．以降，本手法でのファイル間での類似度の定義と，具体的な計算手順を示す．

3. 1 ソースファイル間の類似度計算
本研究では，ソースファイルをそれぞれ字句の tri-gram 多重集合とみなし，それらの類似度として Jacif Smax (q, v) ≥ θcard 係数の推定値を b-bit MinHash 法で計算する．あotherwise

るソースファイルの字句集合を f とし，その trigrammax sim(q, f )f ∈Files(v)

ここで Files(v) は，バージョン v に含まれるファイル

多重集合を τ (f ) とすると，trigram 多重集合を用いたファイル f1 とファイル f2 との間の Jaccard 係数

Jτ (f1 , f2 ) は以下の式で定義される．
545

電子情報通信学会論文誌 2020/7 Vol. J103–D No. 7

図 1 提案手法の動作例

Jτ (f1 , f2 ) =|τ (f1 ) ∩ τ (f2 )||τ (f1 ) ∪ τ (f2 )|τ (f ) = {ti , ti+1 , ti+2 |1 ≤ i ≤ |f | + 2}
ただし，ti , ti+1 , ti+2  は f 中の連続する三つの字句の組である．τ (f ) を構築する際，f は先頭と末尾に空要素を二つずつ加えることで，全ての τ (f ) の要素はhi (τ, n) = SHA1(τ ) × n × ri
ここで SHA1(τ ) は trigram τ を構成する三つのトークンを連結したバイト列に対する SHA-1 ハッシュ値であり，ri は xorshift [20] による擬似乱数（ただし最小ビットは 1 に固定したもの）である．n と ri で SHA-1
ハッシュの順序を並べ替え，τ (f ) の全要素に対して少なくとも一つの空でない字句をもつ組になるように最小となる値を保存し，得られたハッシュ値の下位 b

する．字句解析はプログラミング言語ごとに異なるが，ビットを得る．

本論文の実験対象となる C 言語用の解析では，コメン

b-bit MinHash 法 に よって 得 ら れ る 類 似 度

トと空白は削除するが，プリプロセッサのための指令

sim(f1 , f2 ) は推定値であり，Jτ (f1 , f2 ) に対して二（例えば #include など）はそれぞれ個別のトークン

項分布する [19]．その分散は Jτ (f1 , f2 ) に応じて変化として保持するようにした．なお，識別子などは特にし，Jτ (f1 , f2 ) がより高いほど小さくなり，1 のとき 0正規化等を行わず，そのまま保持している．これらのになる．言い換えると，ある二つのソースコード間の情報はバージョンの特定に有用であることが報告されJτ (f1 , f2 ) と sim(f1 , f2 ) の差分は 0 を中心とした二ているためである [5]．
しかしながら，正確に Jτ (f1 , f2 ) を計算する場合，
あらかじめ集合ごとに要素を特定の順序で整列して項分布となり，Jτ (f1 , f2 ) が大きいほどその差分も小さい．このことから，十分な要素数をもつソースファ
イル集合同士であれば，Jτ (f1 , f2 ) を定義どおりに計おいたとして，τ (f1 ), τ (f2 ) の大きさの和に比例した算した場合と比べても，十分正確に類似度の合計値を時間が必要となる．そこで，これを軽量に計算する

求めることが期待できる．

ため，本研究では b-bit MinHash 法を用いて類似度を計算する．b = 1 とし，ハッシュ関数を k 個用いる
ことで，k ビットのビットベクトルに対する XOR 演
算を行うだけで，ファイル f1 , f2 の組に対する類似度

sim(f1 , f2 ) = Je (τ (f1 ), τ (f2 )) を求める．
本研究では具体的なハッシュ関数の実装として，τ (f )における trigram τ の n 回目の出現に対して，以下の関数を適用する．（注 1）（注 1）：実装は https://github.com/NAIST-SE/CodeHash で公開
している．

546

図 2 に定義どおりに Jτ (f1 , f2 ) を計算する具体例を，
図 3 に b-bit MinHash 法を用いて類似度の推定値を計算する具体例を示す．図 2 中の  A, B, C  は連続する字句の組を表し， は空要素を表す．また， A,

B, C u となっている要素は，その集合に固有の要素= 0.579 が得られる．
である．ここから Jτ (a, b) = 1119
図 3 は 10 個のハッシュ関数を用いて b-bit MinHash
法を適用した場合を示す．それぞれのソースコードの trigram 多重集合に対して 10 個のハッシュ関数 biを適用し，図に示すようなハッシュ値の列が得られた

論文／軽量な類似度計算によるプロジェクト間のソースファイル集合の再利用検出

Algorithm 1 再利用しているライブラリのバージョンの検出

0.021 の誤差が生じているが，実際の適用ではハッシュ

入力
DQ : 解析対象ソフトウェアのあるバージョンでの再利用ラ
イブラリが含まれるディレクトリ
L : ソフトウェアが利用しているライブラリのリポジトリ
θ, m : 類似度のしきい値
出力rQ : DQ 中のソースファイルに最も類似する L のバージョンr[q] : DQ 中のソースファイル q に最も類似するファイルをもつ L のバージョン
1: Initialize S(q, v) ← 0 for all possible q ∈ DQ and v ∈ L
2: for v ∈ L do3:
for f ∈ Files(v) do
4:
for q ∈ DQ do
5:
if f is same file extension to q then6:
if SHA1(f ) = SHA1(q) then7:
S(q, v) ← 1.0
8:
else
min(|τ (q)|,|τ (f )|)9:
if max(|τ(q)|,|τ (f )|) ≥ θ then10:
if sim(q, f ) ≥ θ − m then11:
if sim(q, f ) ≥ S(q, v) then12:S(q, v) ← sim(q, f )13:
end if14:
end if15:
end if16:
end if17:
end if18:
end for19:
end for
20: end for
21: rQ ← arg max
S(q, v)関数の個数を増やすことで，より正確に類似度を計算

22:

図2

図3

正確な Jτ (f1 , f2 ) の具体例

b-bit MinHash を用いた類似度計算例とすると，一致しているハッシュ値は八つあるので，
8
sim(a, b) = ( 10
− 12 ) × 2 = 0.6 となる．この例では

する．

v∈L

q∈Dq

r[q] ← arg max S(q, v) for each q ∈ DQv∈L

3. 2 再利用元バージョンの特定
Algorithm 1 に提案手法の疑似コードを示す．入力

で 6 行目でファイルの内容が完全一致するかどうかをは再利用元ライブラリのバージョンを調査したいファ

SHA-1 ハッシュによって確認する．ファイルが完全一イル集合 DQ ，そのソフトウェアが再利用しているラ

致していれば，字句解析などを一切行うことなく，類イブラリのリポジトリ L である．似ていないファイ

似度を 1.0 とする．完全一致でないファイルに対してルの類似度がノイズとして加わることを防ぐため，類は，9 行目で trigram 多重集合の大きさの比較を行い，似度がしきい値 θ 以上のファイルの組だけを扱う．ま大きさがあまりに異なる（類似度が決してしきい値 θた，b-bit MinHash 法の誤差を許容する範囲として mを超えない）ファイルについては比較を行わないようを導入している．加えて，計算コストを削減するたにする．この条件式は，二つの集合の大きさの比がしめに，ソフトウェアとライブラリそれぞれに含まれる

きい値 θ よりも小さい場合，Jaccard 係数が以下のよファイルについて，事前に b-bit MinHash 法のためのうに θ を上回ることがないことを利用している．

ハッシュ列やファイルの SHA-1 ハッシュ値を計算しておく．
アルゴリズムは 2 行目から 20 行目までが，ライブ
ラリ L の全てのバージョン v ∈ L に含まれるファJτ (q, f ) ≤min(|τ (q)|, |τ (f )|)<θ
max(|τ (q)|, |τ (f )|)類似度がしきい値 θ を超える可能性があるファイルのイル f について，入力されたファイル q ∈ DQ と比組に対してのみ，10 行目で b-bit MinHash 法による較するループ構造となっている．計算を高速化するた類似度の計算を行う．sim(q, f ) は Jaccard 係数を中め，まず 5 行目でファイルが同一の拡張子をもつ（同心として二項分布するため，sim(q, f ) が θ を超えな

一のプログラミング言語である）ことを確認し，次いいソースファイル間であっても，Jτ (q, f ) は θ を超え547

電子情報通信学会論文誌 2020/7 Vol. J103–D No. 7ている場合がある．そこで，マージン m だけしきいと，規模が異なること，開発コミュニティが異なるこ

値を引き下げることで，類似しているソースファイルとを基準として選択した．五つのソフトウェアは全ての組合せが見落とされないようにする．

libpng と zlib を利用しており，合計で 13 組の再利用

類似度の計算が完了すると，アルゴリズムの 21 行

関係が含まれている．

目でバージョンごとに類似度の合計を行い，最も類似

表 2 にこれらのソフトウェア及びプロジェクトの開度の合計値が高かったライブラリのバージョンを出力

発状況の情報を示す．ID が 1 から 8 のプロジェクト

rQ として特定する．また，22 行目で，DQ に含まれはライブラリを利用しているソフトウェアで，ID がたファイル q それぞれに対して最も類似しているファ

9 から 12 のプロジェクトはライブラリである．全て

イルを保有するバージョン r[q] を求める．なお，同一のプロジェクトは分散版管理システムの Git で管理さのファイルを含むライブラリのバージョンが複数存在れており，表中のリポジトリ URL からクローンした．

する場合があるが，rQ の出力では，類似度が最大の

android は機能部位単位で Git リポジトリを分けて管候補が複数ある場合には最新のバージョンを報告する．

理しているため，元になったライブラリに対応するリr[q] の候補が複数ある場合，その中に rQ が含まれてポジトリを実験対象としている．コミット数はリポジいる場合は rQ を使用し，そうでない場合は最新版をトリをクローンした時点での最新のリビジョンまでを報告する．

数えたもので，LOC は最新のリビジョンでの総ソー

4. 評

スコード行数 (Lines of Code) である．バージョン数

価

はタグとして付けられたバージョンの個数である．同

本研究では提案手法の妥当性を以下の基準で評価

一リビジョンに複数のバージョンが紐づけられているする．

（同一内容のソースコードが複数のバージョンとしてリ（ 1 ） ライブラリのバージョンを検出する正確さ

リースされた）場合は，それらをまとめて一つのバー（ 2 ） ライブラリのバージョン検出に要する時間

ジョンとして扱う．

ファイ ル 単 位 で 再 利 用 元 の バ ー ジョン を 検 出 す る

4. 2 実 験 方 法

Kawamitsu らの手法 [5] を基準としてみた場合，提提案手法を Java で実装し，表 1 のソフトウェア・ラ

案手法の特徴は，再利用されたファイル集合全体でイブラリの組に対して実行する．実験対象ソフトウェの類似度をもとにバージョンを検出すること，b-bit

アの各バージョンに対して，ライブラリから再利用し

MinHash 法による高速な類似度の計算を導入したこ

たファイルを格納しているディレクトリ (DQ ) をディとの 2 点にある．そこで，正確な Jaccard 係数の計算

レクトリ名に基づいて特定し，ライブラリのリポジトを用いてファイル単位で再利用元バージョンを検出す

リ (L) と合わせて実装プログラムに与えて，バージョる場合を基準として，ファイル集合全体での類似度を

ン番号を取得する．提案手法における類似度のしきいもとにバージョンを検出する効果と，Jaccard 係数を値は，θ = 0.9，m = 0.1 とし，b-bit MinHash 法の

b-bit MinHash 法で計算した効果を計測する．

ビット数とハッシュ関数の個数は b = 1，k = 2048 と4. 1 実 験 対 象

した．

実験対象として五つのソフトウェアと四つのライブ検出結果の正確さは，実験対象ソフトウェアの各

ラリのプロジェクトを使用する．表 1 にこれらのソフ

バージョンに対して，検出結果がソフトウェア側の記

トウェアと利用されているライブラリの組合せを示す．

録と一致した割合によって求める．ソフトウェア側の実験対象ソフトウェアは，再利用ライブラリのバー

記録は，リポジトリ中のコミットメッセージやドキュジョンを記録していること，長期間保守されているこ

メントファイルの中に記録されていた再利用ライブラ
リのバージョン番号を手作業で検出したものである．

表1

実験対象のソフトウェア・ライブラリの組合せ
ソフトウェアandroid
apitrace
fs2opengecko-dev
v8monkey548

libpng






curl


ogg




zlib






この手作業での分析では，ライブラリからコピーされたファイルは利用せず，実験対象ソフトウェアで作成された記録のみを用いてバージョンの検出を行った．
バージョン番号の識別には Git リポジトリにおけるタグを用いたが，gecko-dev と ogg の組においては，再利用しているバージョンの記録に ogg 側の Subversion

論文／軽量な類似度計算によるプロジェクト間のソースファイル集合の再利用検出
表2
ID
1
2
3
4
5
6
7
8
9
10
11
12

リポジトリ名android(libpng)
android(curl)android(ogg)android(zlib)
apitrace
fs2opengecko-dev
v8monkey
libpng
curl
ogg
zlib

実験対象のソフトウェア・ライブラリを格納するリポジトリ

リポジトリ URL
https://android.googlesource.com/platform/external/libpng
https://android.googlesource.com/platform/external/curl
https://android.googlesource.com/platform/external/libogg
https://android.googlesource.com/platform/external/zlib
https://github.com/apitrace/apitrace.git
https://github.com/scp-fs2open/fs2open.github.com.git
https://github.com/mozilla/gecko-dev.git
https://github.com/zpao/v8monkey.git
git://git.code.sf.net/p/libpng/code
https://github.com/curl/curl.git
https://github.com/xiph/ogg.git
https://github.com/madler/zlib.git

表3
ソフトウェアandroid(libpng)
android(curl)android(ogg)android(zlib)
apitrace
fs2opengecko-dev
v8monkey全体

ライブラリ
libpng
curl
ogg
zlib
libpngzlib
libpngzlib
libpngogg
zlib
libpngzlib

期間
2008/10-2018/4
2010/3-2018/6
2012/6-2017/10
2008/10-2018/1
2008/7-2018/2
2002/1-2018/3
1998/3-2018/4
2007/3-2012/2
2009/4-2018/3
1999/12-2018/7
2000/9-2018/4
2011/9-2017/1

コミット数
378
205
21
259
4264
16526
634881
87432
5956
23312
497
419

LOC
88401
2085303283
38057
41355877658518053155
660421887744
1960983830
35609

バージョン数
46
22
9
35
9
319
98
72
1557
179
11
72

提案手法の実行結果

ソフトウェアのバージョン数
46
22
9
35
9
9
293
293
98
98
98
72
72
1,154

記録と
一致する数
46 100.0%
1986.4%
9 100.0%
35 100.0%888.9%
9 100.0%
293 100.0%
293 100.0%
98 100.0%
94
95.9%
98 100.0%
72 100.0%
72 100.0%
1,146
99.3%

記録と
一致しない数
0
0.0%
3
13.6%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
0
0.0%
3
0.3%

記録なし
0
0
0
0
1
0
0
0
0
4
0
0
0
5

0.0%
0.0%
0.0%
0.0%
11.1%
0.0%
0.0%
0.0%
0.0%
4.1%
0.0%
0.0%
0.0%
0.4%

リポジトリのリビジョン番号が使用されていたため，112.16.7.el7uek.x86 64，CPU は Intel Xeon E5-2690

それらを手作業で Git リポジトリのバージョン番号に

v4，RAM は DDR4-2400 ECC Memory 512 GB，ス

読み替えた．
ファイル単位で再利用元バージョンを検出する場合

トレージは SAS 接続の 1TB のもの，Java の実行環
境は OpenJDK 8 である．時間の計測は，Java のシと比較するため，提案手法のファイル単位での出力

ステムメソッドの一つである nanoTime メソッドの呼(r[q]) についても，ファイル単位でソフトウェア側のび出しを実装プログラム中に記述することで行う．ま

記録との一致率から正確さを求める．Kawamitsu らた，マルチスレッド処理は使用せず，単一のスレッドの手法 [5] に従ってファイル単位で最も類似したライで処理を行う．

ブラリのバージョンが複数検出された場合は，ソフト

b-bit MinHash 法がもたらす効果を評価するため，ウェア側の記録に該当するバージョンを含むとき記録

評価実験では Jaccard 係数を b-bit MinHash 法を用と一致するとみなす．提案手法は，既存手法と比べる

いて近似計算した場合と，ファイルの内容から正確にと，ファイル集合全体での集計結果を用いて，特定の計算した場合の 2 通りを実行する．

1 バージョンだけに候補を絞った出力を行っているとみなすことができるため，出力されるバージョン数も比較を行う．

4. 3 提案手法の正確さ
表 3 にソフトウェアのバージョンごとの正確さを計測した結果を示す．fs2open のバージョン数が表 2 の提案手法の実行時性能の評価は，実装プログラム

バージョン数と異なる値だが，これは一部のバージョをそれぞれ 10 回ずつ実行し，その実行時間を計測すンでライブラリが利用されていなかったためである．

ることで行う．入力されたソースファイル群の読み込

検出結果と記録はソフトウェアごとでは 86.4%から

みと比較に大きな時間を要するため，ソフトウェアの100.0%が，全体では 99.3%が一致し，ソフトウェア

読み込み，ライブラリの読み込み，ソースファイルのとライブラリの組のうち，13 組中 10 組については検比較のステップと全体での時間を分けて記録する．計

出結果と記録が全て一致した．記録と一致しなかった測に用いる計算機環境の OS は Oracle Linux 4.1.12-

android における curl 再利用の三つのバージョンにつ549電子情報通信学会論文誌 2020/7 Vol. J103–D No. 7

いては，再利用したライブラリのドキュメントファイ

個別のバージョンが一致する場合はただ一つ，一致しルと検出結果のバージョンが一致したことから，ソフない場合でも二つのバージョンだけに絞り込んでおり，

トウェア側の記録が間違っている可能性がある．また，それでも正確さで既存手法を上回っていることから，再利用したバージョンの記録がない場合についても，

既存手法よりも簡潔な出力で，正確さを達成している．

apitrace の 1 例ではライブラリのドキュメントファイ

表 5 に，提案手法におけるファイル単位での検出結ルに記述されているバージョン情報と提案手法の検出

果がソフトウェア全体の検出結果と異なったファイル

結果が一致している．これらのことから，提案手法はの数を示す．表中のファイル数の列は，ソフトウェア

再利用しているライブラリのバージョンを高い精度で中のライブラリのディレクトリに含まれるソースファ検出することが可能である．

イルの数を全てのバージョンで足し合わせた値である．

表 4 に提案手法の全てのファイルに対して求めた全提案手法は 1.61%のファイルに対して，ファイル集合

体での正確さを示す．既存手法，すなわち最も類似し全体でのバージョンとは異なるバージョンを出力した．

たファイルを選択する方式の正確さは 94.7%であり，それらのファイルを目視で分析したところ，以下のよ提案手法は 95.6%でそれを上回った．また，既存手法

うな事例が含まれていた．

ではファイルごとの情報だけでは単独のバージョンに•利用しているライブラリの新しいバージョンで絞り込むことはできず，最頻値で 4 バージョン，中央は削除されたファイル．新しいバージョンのライブラ

値で 23 バージョン，最大で 1612 バージョンを列挙しリを上書きコピーした結果，ライブラリ側で削除された．提案手法は，全体での結果と各ファイルについてたファイルだけが上書きされずに残ったと考えられる．

•
表4
ソフトウェアandroid

apitrace
fs2opengecko-dev
v8monkey

ファイル単位での正確さ
ライブラリ
libpng
curl
ogg
zlib
libpngzlib
libpngzlib
libpngogg
zlib
libpng
zlib

全体

提案手法
100.0%
86.4%
100.0%
100.0%
90.7%
100.0%
100.0%
100.0%
100.0%
96.3%
100.0%
100.0%
100.0%
95.6%

表5

android(libpng)
android(curl)android(ogg)android(zlib)

libpng
curl
ogg
zlib
libpngzlib
libpngzlib
libpngogg
zlib
libpngzlib

gecko-dev
v8monkey

全体

550

リの新しいバージョンとして検出された．

•

ソフトウェア側で独自に変更を加えたファイル．

例えば条件式の中で関数を呼ぶのではなく変数に代入してから条件式で参照するなどのコーディングスタイ
ルの統一を実施したものがあった．変更内容が，他のバージョンの内容と偶然類似していた場合に，異なるバージョンとして報告された．
提案手法は全体として最も類似したバージョンを報告するため，そのバージョンを基準に差分を分析することで，これらの影響を迅速に把握することができた．

ソフトウェア全体とファイル単体での検出結果の違い

ライブラリ

fs2open

自に適用したファイル．そのファイルのみ，ライブラ

既存手法
98.4%
86.4%
100.0%
99.6%
90.7%
100.0%
100.0%
100.0%
95.4%
95.5%
100.0%
86.4%
100.0%
94.7%

ソフトウェアapitrace

ライブラリ側でバグや脆弱性の修正版応がリリースされる前に，修正パッチをソフトウェア側で独バージョン数

ファイル数

46
22
9
35
9
9
319
319
98
98
98
72
72
1,206

3,211
13,137
63
2,960
194
240
6,446
6,445
2,520
536
2,646
1,586
1,756
41,740

不一致数
50
273
0
11
0
0
0
0
116
4
1
215
0
670

1.56%
2.08%
0.00%
0.37%
0.00%
0.00%
0.00%
0.00%
4.60%
0.75%
0.04%
13.56%
0.00%
1.61%

バージョン
あたりの不一致数
1.09
1.56%
12.41
2.08%
0
0.00%
0.31
0.37%
0
0.00%
0
0.00%
0
0.00%
0
0.00%
1.18
4.60%
0.04
0.75%
0.01
0.04%
2.99
13.56%
0
0.00%
0.56
1.61%

論文／軽量な類似度計算によるプロジェクト間のソースファイル集合の再利用検出

これはファイル単位で検出を行っていた既存手法では

ソースファイルの読み込みに要した時間，ライブラリ

実施できなかった分析である．

のソースファイルの読み込みに要した時間，比較に要図 4 に，提案手法（b-bit MinHash 法）で計算したした時間を示す．三つの段階以外にも出力の集計等の類似度と，正確な Jaccard 係数の誤差の分布を示す．

処理が含まれるため，三つの段階の合計時間は全体の左端の箱ひげ図が提案手法の実行中に計算された全て合計時間とは一致しない．ソフトウェアの読み込み時の類似度の値の誤差の分布である．b-bit MinHash 法

間は実装の都合上全てのバージョンを読み込んだ時間

はファイルの内容が同一（Jaccard 係数 1）であるとである．読み込み時間はバージョン数と全バージョン

き差分は原理的に 0 となるので，ばらつきは非常に小を通してのユニークなファイル数が多いほど増大する．

さい．中央の箱ひげ図がこれらの類似度をファイル集

表 2 を見るとバージョン数はライブラリの方が多い傾

合ごとに合計したときの誤差であり，最大でも 0.52 で向にあるため，ソフトウェアよりもライブラリの方がある．右端の箱ひげ図のようにファイルの個数で正規読み込み時間が長くなる傾向にある．

化すると，最大で 0.006 と，ソフトウェア全体の類似

表 6 の「比較回数」の列は，提案手法における類度に対する比率としては極めて小さな誤差であり，実似度の計算回数（Algorithm 1 における 10 行目の実際に本実験ではバージョンの検出には影響せず，提案行回数）を示している．類似度の計算回数は最大で手法は Jaccard 係数を正確に計算した場合と同一の結

6.7 × 108 回行われているにもかかわらず比較時間は果を出力した．

平均で 11 秒程度である．これは，提案手法における4. 4 提案手法の実行時性能類似度の計算が一度のビット演算と算術演算だけであ表 6 に提案手法の実行時間を計測した結果を示す．

り，時間計算量が O(1) となっているためである．
表 6 の右から 3 列目に，b-bit MinHash 法を利用し左から全体での実行時間と，実験対象ソフトウェアのなかった場合（Jaccard 係数を直接計算した場合）の実行時間全体を 100%としたときの提案手法の実行時間を示す．ソフトウェア及びライブラリ読み込みに要する時間はどちらの方法でも変わらず，実行時間の短縮は比較に要する計算時間の差によるものである．また，右から 4 列目に，正確に Jaccard 係数を計算した場合の全体の実行時間を示す．これらから，比較回数が少ないものについては実行時間の短縮の効果が小さいが，平均でも 24.2%の実行時間で計算を完了できるようになったことが分かる．ライブラリが ogg の場合はほとんど改善がみられないが，これは ogg がJaccard 係数を計算したとしてもほとんど時間がかからないほど小規模で比較回数が少なく，読み込みにか
図4

1 ビット MinHash 値と Jaccard 係数の誤差の分布

表6
ソフトウェアandroid

apitrace
fs2opengecko

v8monkey
平均

ライブラリ

libpng
curl
ogg
zlib
libpngzlib
libpngzlib
libpngogg
zlib
libpngzlib

かる時間の方が支配的なためである．

提案手法の実行時間

実行時間
全体 t1 [ms]ソフトウェア
読み込み [ms]ライブラリ
読み込み [ms]比較 [ms]

比較回数

242,371
95,864981
7,250
214,5446,156
279,272
9,045
235,119
9,988
17,526
231,638
12,141
104,761

4,571
9,064
601
2,275
1,480
928
2,012
1,335
12,740
9,593
10,507
7,603
6,007
5,286

223,418
45,515357
4,342
212,289
5,147
210,973
5,064
208,702
312
4,946
214,594
5,048
87,747

14,381
41,287
22
632
773
80
66,286
2,645
13,675
82
2,072
9,440
1,085
11,727

2.2 ×108
6.7 ×108
3.2 ×103
1.2 ×107
1.5 ×107
1.0 ×106
5.0 ×108
2.8 ×107
1.8 ×108
3.1 ×104
2.7 ×107
1.7 ×107
1.2 ×108
1.4 ×108

類似度を正確に計算する場合との比較
正確に計算した場合のt1 /t2
実行時間全体 t2 [ms]4,170,739
5.8%
3,220,414
3.0%
1,044
94.0%
105,303
6.9%
545,570
39.3%
16,602
37.1%
11,871,778
2.4%
300,693
3.0%
4,294,906
5.5%
10,47895.3%
278,0526.3%
3,000,782
7.7%
178,727
6.8%
2,153,468
24.1%

使用メモリサイズ [MB]Jaccardb-bit
係数
MinHash944.464.32
226.96
3.12
1.51
0.01
24.47
0.36
946.01
4.34
23.69
0.35
945.39
4.33
22.99
0.34
958.16
4.40
23.08
0.34
1.71
0.01
22.30
0.33
950.124.36
391.602.05

551

電子情報通信学会論文誌 2020/7 Vol. J103–D No. 7

表 6 の右端の 2 列は，Jaccard 係数を計算する場

出してしまう可能性がある．多数決を採用する場合で合の集合表現を構築する際のメモリ使用量と b-bit

は，再利用したファイルの過半数に対して編集した結MinHash 法を使用した場合のメモリ使用量の概算値

果，実際に再利用したバージョンとの類似度が低下すである．Jaccard 係数を計算する場合は 1 ファイル

ると，他のファイルの類似度の値にかかわらず誤ったの 1 要素ごとに 64 ビット整数を一つ使用する，b-bit

バージョンを検出してしまう．類似度の集計方法の違

MinHash の場合は 1 ファイルに対し 2048 ビット使用

いが結果に影響する可能性はあるが，評価実験ではこするとみなし，Java のデータ構造によるオーバーヘッのような状況は発生しなかった．ライブラリの再利用

ドを無視して算出した値である．結果として，メモリに際してファイルの修正は基本的には軽微であり，表の使用量は Jaccard 係数を計算する場合の 1%未満と5 に示したとおり，全てのファイルのうち 1.61%以外

なり，大規模なライブラリのリポジトリに対する解析はソフトウェア全体の検出結果のバージョンと最も類でも，通常の計算機で十分に取り扱うことができると似していた．

5. 2 実験対象の妥当性考えられる．
上記の結果から，提案手法は既存手法よりも高速か

実験対象のソフトウェアには，利用ライブラリのつ省メモリである．また，ライブラリの読み込みにはバージョンを適切に記録しているものだけを使用して時間がかかるが，b-bit MinHash の計算結果をキャッいる．そのため，評価実験の結果には，それらのソフ

シュとして保管しておけばその影響は小さくすること

トウェアの特徴が影響している可能性がある．ただし，が可能である．提案手法を使用して，様々なプロジェ

対象ソフトウェアは異なるコミュニティで開発されてクトに対して自動でライブラリの利用状況を監視するいるものを選択したため，開発者の再利用方法に関すようなシステムの構築も十分可能であると考えている．

る偏りの影響は少ないと考える．

5. 妥当性への脅威

実験対象の再利用状況を確認すると，ライブラリに含まれる全てのソースファイルを再利用する場合がほ5. 1 ファイル集合の再利用バージョン判定

とんどだった．libpng については Android のみテスト

本研究ではソフトウェア全体での再利用バージョンに使われるソースファイルなどは再利用していなかっを決定する際，ファイル単位の類似度を合計する方法

た．このようなライブラリの一部分のみを再利用するを用いた．本研究で用いた b-bit MinHash 法で計算し場合としては以下のものが考えられる．

た類似度は，文献 [19] によると誤差が 0 を中心に二項（ 1 ） ライブラリ内の一部のファイルのみが再利用

分布するため，類似度を合計することで，十分にファされた場合．例えばテストファイルの除去が行われる

イル数が多い場合には正負の誤差が相殺され，平均でなど．

0 に近づくことを期待した．評価実験においても，図（ 2 ） ファイルごとに異なるバージョンのライブラ

4 に示したように誤差を小さく抑えることができた．

リからの再利用が行われた場合．例えば修正パッチをファイル単位の類似度を集計する方法はこれに限最新版から取り込んだ場合など．

定されているわけではなく，例えばファイル単位での（ 3 ） あるファイルの一部分のみが再利用された場バージョンの多数決を取るという方法も考えられる．

合．例えば特定の関数内のアルゴリズムだけが流用さこの二つの類似度の集計方法は，類似度が以下の条件

れる場合など．

を満たす場合に，異なる結果を出力する．

|S(q, v1 ) > S(q, v2 )| > |S(q, v1 ) < S(q, v2 )|SQ (v1 ) < SQ (v2 )一つ目の場合については，本手法は再利用バージョンの判定にしきい値を超えるような類似度をもつソースファイルを用いるので，改変が大きくない限り再利用バージョンの検出は可能である．二つ目の場合につこのような状況は，ライブラリの再利用方法によって，いては，提案手法の章で述べたように，ファイル単位v1 ，v2 のどちらが正解の場合にも起こり得る．類似での再利用バージョンも出力するため，開発者はそれ度の合計を採用する場合では，再利用したファイルのぞれのファイルについて対応方法を検討することが可

一つを大幅に編集した結果，その類似度の差が支配的能である．加えて，この事例は 4. 3 に挙げたとおり，になり，実際に再利用したバージョンの過半数のファ実験対象としたソフトウェアについても一部のファイイルが完全一致であっても，間違ったバージョンを検ルについて確認されており，提案手法によって簡単に

552

論文／軽量な類似度計算によるプロジェクト間のソースファイル集合の再利用検出確認できている．三つ目の場合については，入力され[5]たディレクトリ中の全てのファイルについて S(q, v) がRoover, and K. Inoue, “Identifying source code reuseacross repositories using LCS-based source code simi-

しきい値を下回るのであれば提案手法で検出すること

larity,” Proc. the 2014 IEEE 14th Int. Working Conf.

ができない．しかし，そもそも提案手法の適用対象は

on Source Code Analysis and Manipulation, pp.305–

再利用したライブラリのみが含まれるディレクトリであるため考慮しない．このような場合はコードクロー

314, Sept. 2014.
[6]

T. Ishio, Y. Sakaguchi, K. Ito, and K. Inoue, “Source
file set search for clone-and-own reuse analysis,”ン検出手法など，異なる分析手法を用いる必要がある．

6. む す び

N. Kawamitsu, T. Ishio, T. Kanda, R.G. Kula, C.D.

Proc. the 2017 IEEE/ACM 14th Int. Conf. on Mining
Software Repositories, pp.257–268, May 2017.
[7]

G. Antoniol, “Code siblings:

本研究ではソフトウェアのファイル集合とライブラ

Proc. the 2009 6th IEEE Int. Working Conf. on Min-アが再利用しているライブラリのバージョンを検出

ing Software Repositories, pp.81–90, May 2009.
[8]

Integrated code history tracker for open source sys-

体としてどのバージョンを再利用しているかを検出し，tems,” Proc. the 34th Int. Conf. on Software Engi-

個別にどのファイルが変更されているかを分析可能と

neering, pp.331–341, June 2012.
[9]

Proc. the 7th IEEE Working Conf. on Mining Soft-

案手法を用いることで，ソフトウェア開発者は再利用

ware Repositories, pp.102–105, May 2010.
[10]

C.V. Lopes, P. Maj, P. Martins, V. Saini, D. Yang,
J. Zitny, H. Sajnani, and J. Vitek, “Déjàvu: A map

定することができ，その情報を用いてライブラリの更of code duplicates on GitHub,” Proc. ACM Program.

新などについて判断を下すことができるようになる．
今後の課題として，再利用されたファイルに施され

Y. Sasaki, T. Yamamoto, Y. Hayase, and K. Inoue,“Finding file clones in FreeBSD ports collection,”

存手法よりも高速かつ省メモリな計算を達成した．提しているライブラリのバージョンを非常に高精度に特K. Inoue, Y. Sasaki, P. Xia, and Y. Manabe, “Where
does this code come from and where does it go?—

ファイル集合で合計することで，99.3%の正確さで全した．また，b-bit MinHash 法を採用することで，既Technical and legal

implications of copying code between applications,”

リのリポジトリを入力として，分析対象のソフトウェする手法を提案した．ファイル単位の類似度をソース

D.M. German, M. Di Penta, Y.-G. Gueheneuc, andLang., vol.1, no.OOPSLA, pp.84:1–84:28, Oct. 2017.
[11]

K. Ito, T. Ishio, and K. Inoue, “Web-service for

た修正を，自動的に既知のパッチ等と照合し，再利用

finding cloned files using b-bit minwise hashing,”

されたファイルを効果的に分析する手法の確立が挙げ

Proc. the 2017 IEEE 11th Int. Workshop on Software

られる．また，あるソフトウェアに使用されている全

Clones, pp.1–2, Feb. 2017.
[12]

K. Jewmaidang, T. Ishio, A. Ihara, K. Matsumoto,てのソースファイルから，再利用ライブラリを自動的

and P. Leelaprute, “Extraction of library updateに検出する技術への拡張も，今後の課題である．

history using source code reuse detection,” IEICE
Trans. Inf. & Syst., vol.101-D, no.3, pp.799–802,

謝 辞 本 研 究 は 科 学 技 術 研 究 費 JP18H04094，

JP18H03221，JP19K20239 の助成を受けて行われた．
文

March 2018.
[13]

献“Deckard: Scalable and accurate tree-based detection[1]

C. Ebert, “Open source software in industry,” IEEE

[2]

P. Mohagheghi, R. Conradi, O.M. Killi, and H.

of code clones,” Proc. the 29th Int. Conf. on Software

Software, vol.25, pp.52–53, May 2008.
[14]

defect-density and stability,” Proc. the 26th Int.
Conf. on Software Engineering, pp.282–292, May[15]tion to big-code,” Proc. the 38th Int. Conf. on Soft-L. Constantin, “Developers often unwittingly usethatcontainflaws,”

ware Engineering, pp.1157–1168, May 2016.

iTWorld.com.

https://www.itworld.com/article/2936575/software-[16]

50, 1912.

inherited-from-buggy-components.html.
P. Xia, M. Matsushita, N. Yoshida, and K. Inoue,[17]

A. Broder, “On the resemblance and containment of
documents,” Proc. the Compression and Complexity“Studying reuse of out-dated third-party code inof Sequences 1997, pp.21–29, June 1997.

open source projects,” Computer Software, vol.30,
no.4, pp.98–104, 2013.

P. Jaccard, “The distribution of the flora in thealpine zone.1,” New Phytologist, vol.11, no.2, pp.37–

applications-have-on-average-24-vulnerabilities[4]H. Sajnani, V. Saini, J. Svajlenko, C.K. Roy, andC.V. Lopes, “SourcererCC: Scaling code clone detec-

2004.
components

Engineering, pp.96–105, May 2007.
横井一輝，崔 恩™ ，吉田則裕，井上克郎，“情報検索技” コンピュータ
術に基づく細粒度ブロッククローン検出，
ソフトウェア，vol.35, no.4, pp.16–36, 2018.

Schwarz, “An empirical study of software reuse vs.

[3]

L. Jiang, G. Misherghi, Z. Su, and S. Glondu,[18]

M.S. Charikar, “Similarity estimation techniques553電子情報通信学会論文誌 2020/7 Vol. J103–D No. 7
from rounding algorithms,” Proc. the 34th Annual
ACM Symposium on Theory of Computing, pp.380–
388, May 2002.
[19]

P. Li and C. König, “b-bit minwise hashing,” Proc.
the 19th Int. Conf. on World Wide Web, pp.671–680,
April 2010.

[20]

G. Marsaglia, “Xorshift RNGs,” Journal of Statistical Software, vol.8, no.14, pp.1–6, 2003.

（2019 年 10 月 2 日受付，2020 年 2 月 6 日再受付，
3 月 27 日早期公開）

伊藤薫2016 兵庫県立大学工学部卒，2018 大阪
大学大学院情報科学研究科博士前期課程了．

現在大阪大学大学院情報科学研究科博士後期課程に在学中．ソフトウェアの再利用分
析に関する研究に従事．

石尾

隆

（正員）

2003 大阪大学大学院基礎工学研究科博
士前期課程了．2006 同大学大学院情報科
学研究科博士後期課程了．同年日本学術振興会特別研究員 (PD)．2007 大阪大学大学
院情報科学研究科助教．2017 奈良先端科
学技術大学院大学情報科学研究科准教授．
2018 同大学先端科学研究科准教授．博士（情報科学）．プログ

ラム解析，プログラム理解に関する研究に従事．

神田哲也

2016 大阪大学大学院情報科学研究科博士後期課程了．同年奈良先端科学技術大学
院大学博士研究員．2017 大阪大学大学院
情報科学研究科特任助教．2018 より同研究科助教．博士（情報科学）．ソフトウェ
ア進化，ソースコード解析に関する研究に
従事．

井上

克郎

（正員：フェロー）1984 大阪大学大学院基礎工学研究科博士後期課程了（工学博士）．同年大阪大学
基礎工学部情報工学科助手．1984〜1986，

ハワイ大学マノア校コンピュータサイエン
ス学科助教授．1991 大阪大学基礎工学部
助教授．1995 同学部教授．2002 より大阪大学大学院情報科学研究科教授．ソフトウェア工学，特にコー
ドクローンやコード検索等のプログラム分析や再利用技術の研究に従事．本会フェロー．

554