Vol.2017-SE-195 No.17
2017/3/12

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

ソースファイル群の類似性を用いたソフトウェア再利用元の検索
坂口 雄亮1,a)

石尾 隆1,b)

伊藤 薫1,c)

井上 克郎1,d)

概要：本研究では，開発中ソフトウェアが再利用するソフトウェアとそのバージョンを特定する手法を提案する．ソフトウェアはソースファイルの集合とみなし，その各ソースファイルについて類似するソース
ファイルを既存の高速検索手法を用いて，大量のソフトウェアのソースファイルから検索する．そして，与えられたソフトウェアがもつソースファイルの集合と類似度がより高いものが上位になるように，検索結果から得られたソフトウェア群の順位付けを行う．この操作によって，再利用したソフトウェアとそのバージョンを知ることが可能になる．実験として，Mozilla Firefox と Android が再利用するソフトウェア
72 件に対して手法を適用した．その結果，手法が出力するソフトウェア集合の中に再利用元が含まれるものが 71 件，その集合を絞り込んだ集合の中に再利用元が含まれるものが 66 件であった．その 66 件について，再利用元の順位が 1 位であるものは 50 件であった．

1. はじめにソフトウェア開発において，既存のソースコードを再利

ソフトウェアとバージョンの情報が必要になる．しかし，多くのプロジェクトにおいてそのような情報が記録されていないことが判明している [3]．

用することが盛んに行われており，ソフトウェアに必要な

ソースファイルが一致するかどうかの単純な判定は容易

機能を開発するコストの削減に役立っている．再利用可能であるが，実際には再利用後にソースコードの変更が加なソースコードとしてはオープンソースソフトウェアがえられることがあるため不十分であり，ソースファイル

活用されている．コードを再利用することによって，機能の内容によって再利用元を検索する必要がある．ソース

を開発するコストを大幅に削減することが出来る．オープ

ファイルに基づいて再利用元を検索する既存手法として，

ンソースソフトウェアは，多くのユーザによって使用されKawamitsu ら [4] は，リポジトリ内の最も類似したファイているため，安全性が比較的高いというメリットがあるこ

ルのリビジョンを再利用元のバージョンとして識別するとから，企業の製品開発にも利用されるようになっていコード比較手法を提案した．この手法は，あらかじめ再利

る [1]，[2]．

用元ライブラリのリポジトリを用意しなければならない．

ソースコードの再利用の行われ方は様々あるが，C 言語

また彼らは，locality-sensitive hashing[5] を用いた類似ファ

でのソフトウェア開発では，既存のソフトウェアのソース

イルの高速検索手法を提案した [6]．これは，検索のクエリ

コードをコピーして取り込むという方法で再利用が行われとして与えられたソースコードのファイルに対し，大量のる．コピーして取り込むと，開発中のソフトウェアに合わ

ソースコードのファイルの中からソースコードの内容がクせた変更が容易になるというメリットがある一方，再利用

エリに類似するものを高速に検索する．1 つのファイルにしたソースコードに含まれる脆弱性を取り込んでしまうおついての正確性や有効性について述べられているが，入力それがある．そのような場合，ソフトウェアの更新を速やとして複数ファイルを与え，それらの情報を合わせて利用かに行わなければいけないが，更新された部分と独自に変することが課題とされている．

更した部分が競合する可能性があるため，再利用している

本研究では，複数ファイルの検索結果であるソースファ
イル群を利用して，開発中ソフトウェアが再利用してい

1

a)
b)
c)
d)

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

c 2017 Information Processing Society of Japan⃝るソフトウェアの再利用元を自動的に推定する手法を提案する．提案手法では，開発中ソフトウェアのソースファ
イルを入力とする．まず，各ソースファイルについて，

locality-sensitive hashing を用いた検索手法を適用し，大量

1

Vol.2017-SE-195 No.17
2017/3/12

情報処理学会研究報告
IPSJ SIG Technical Reportのソフトウェアのソースファイルから成るデータベースかれることになり，それに対する修正を手元のソースコード

ら類似するファイルを検索する．データベースは，フリーにも適用すべきである．脆弱性が含まれたコードを再利用なオペレーションシステムである Debian GNU/Linux がしているのかを確認するためには，再利用しているソフト採用してきたほぼすべてのパッケージで構築されている．

ウェアを管理する必要がある．

検索後，各入力ソースファイルの類似ファイル群をデータ

しかし，多くのプロジェクトにおいて，再利用している

ベースに登録されているソフトウェア毎にまとめ，ソフト

オープンソースソフトウェアの管理がなされていないこと

ウェア集合を得る．そして，入力ソースファイル集合によがわかっている．Xia ら [3] は，オープンソースライブラ

り近いものが上位となるようなソフトウェア間の半順序関

リを再利用しているプロジェクトについて，そのライブラ係を用いて順位付けられた再利用元ソフトウェアリストをリが脆弱性の含まれるソースコードを保有しているバー

得る．

ジョンであるかどうかを調査した．その結果，zlib につい

手法の評価のために，Mozilla Firefox と Android のソーて，45 プロジェクト中 14 プロジェクト（31.1%）が脆弱

スコードに再利用されているソフトウェアを対象として手性のあるバージョンを使用していることがわかった．同様

法の妥当性を評価した．

に，libcurl については，28 プロジェクト中 24 プロジェク

以降，第 2 章では，本研究の背景について述べる．第 3ト（85.7%），libpng については，50 プロジェクト中 46 プ

章で提案手法について説明し，第 4 章で手法の評価を述べ

ロジェクト (92%) であった．また，計 123 プロジェクトる．第 5 章では妥当性への脅威について述べ，最後に第 6中 27 プロジェクト (22%) で，ライブラリのソースコード

章で，まとめと今後の課題を記述する．

を再利用後に編集しており，23 プロジェクト（18.7%）で

2. 背景
2.1 ソースコードの再利用

は，再利用しているライブラリのバージョンに関する情報が残っていなかった．さらに，6 プロジェクト（4.9%）で，ディレクトリ名や他のライブラリのソースコードが含まれソフトウェア開発者は，既存のソフトウェアのソースており，管理が容易ではなかった．このように，再利用しコードを再利用してソフトウェアを開発する [1]．ソースているソフトウェアの管理について，そのソフトウェア名

コードの再利用は，機能を開発するコストを大幅に抑えるやバージョンなどの再利用元を推定することは有用である

ため，ソフトウェア開発の効率化につながる．Rubin ら [7]と考えられる．

は，企業内での新規ソフトウェア開発において，既存のソ
フトウェアの再利用が行われていることを報告している．

Mohagheghi ら [8] は，再利用されたコンポーネントはそうでないものと比べて安全性が高いと報告している．

2.3 起源分析
本研究では，再利用元の特定に関する研究として，起源分析が上げられる．起源分析とは，ソースコードの起源を再利用のされ方として，ソフトウェアの機能を開発する

複数のソフトウェアから特定する技術で，ソースコード

際に，新しく開発するのではなく，その機能を持つオープの類似性を用いるため，コードクローン検出の一部と言ンソースソフトウェア (以下 OSS とも表記) が一般的に利える．コードクローンとは，ソースコード中に存在する同用される．その際に，再利用したコードを開発中のソフト

一または類似した部分を持つコード片のことであり，既ウェアに合うように独自の変更が加えられることがある．

存コードのコピーアンドペーストによる再利用等が原因

Java プロジェクトでの OSS の利用は，バイナリファイルで生じる．コードクローン検出技術の例として，Kamiyaの再利用が一般的である. また，新たにソフトウェアを開ら [10] は，ファイル間の類似したコード片を検出するため発する際には，既存ソフトウェアを全て再利用し，細かなに，CCFineder を提案した．また，Sasaki ら [11] が提案し改変が加えられ類似したソフトウェアが開発する派生開た FCFinder は，プロジェクト間でのファイルクローンを発，ソフトウェアプロダクトで全体に共通するコア資産と高速に検出する．

独自性を持つ機能部品に分割し，これらを組み合わせてソ起源分析では，Inoue ら [12] は，Ichi tracker という名

フトウェアが開発するソフトウェアプロダクトラインエン

前のツールを提案した．これは，インターネット上の様々

ジニアリング [9] もソースコードの再利用と言える．

なリポジトリ間で，特定のソースファイルの類似ファイルを検索し，コード断片との類似度でクラスタリングを行

2.2 オープンソースソフトウェアの管理状況

う．そして，ソースファイルを時系列順に並べることによ

OSS は安全性が高いとは言え，再利用したソースコード

りソースコードの再利用の経緯を可視化する．このツールにバグやセキュリティに関する脆弱性が発見されることもでは，1 つのファイルについて注目している．Kawamitsu

ある．脆弱性が公開されると開発者は，脆弱性の含まれたら [4] は，リポジトリに含まれているソースコードについコードを再利用しているのかを確認する必要がある．再利て，ライブラリのバージョンを推定する手法を提案した．

用している場合，開発者のソフトウェアにも脆弱性が含ま

ソースコードの類似度として最長共通部分列に基づいた類

c 2017 Information Processing Society of Japan⃝2

Vol.2017-SE-195 No.17
2017/3/12

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

似度 [9] を用いて，最も類似度の高いソースコードが再利
1.0

用元であるという仮定に基づきバージョンを提示した．この手法はあらかじめ再利用を行ったソフトウェアのリポジ

本研究では，類似ソースファイルの検出に，川満ら [6] のlocality-sensitive hashing(以下 LSH とも表記) アルゴリズ
ムを利用した高速検索手法を用いる．この手法では，検索のクエリとして与えられたソースファイルに対し，データ
ベース中のソースファイルからソースコードの内容がクエ

0.8
0.6
0.4

2.4 LSH アルゴリズムを利用した高速検索手法

0.2

明である場合は利用することが出来ない．

ベクトルが1つ以上一致する確率

トリと再利用元のリポジトリが必要なため，再利用元が不実際の類似度ではなく，類似度の推定値を計算することで0.0

リに類似するものを検索する．LSH を用いることにより，0.0

高速な検索を可能にしている．

0.2

0.4

0.6

0.8

1.0

真の類似度p2.4.1 ソースファイル間の類似度
図 1

ソースファイル f1 , f2 の類似度は，各ファイルの 3-gram

LSH のパラメータ集合間の Jaccard 係数を利用し以下のように定義される．

Jaccard 係数は，2 つの集合間の類似度であり，文字列間の類似度を計算する手法としてよく利用される．

|3-grams(f1 ) ∩ 3-grams(f2 )|sim(f1 , f2 ) =|3-grams(f1 ) ∪ 3-grams(f2 )|ただし，3-gram(f ) は，ソースファイル f から抽出された

3-gram の多重集合である．多重集合の要素は，ソースコー
ドからコメント，空白行を除いたものから得た字句列から
長さ 3 の部分文字列である．

2.4.2 Locality-Sensitive Hashing
クエリのソースファイルとデータベース中の大量のソー
スファイルの間の Jaccard 係数を求めるには，膨大な時間がかかってしまう．川満らの手法では，文献 [13] の方法を用いて LSH を構成した．各ソースファイルについて，

3-gram の多重集合に r × b 個のハッシュ関数を用いて，r次元の MinHash の値からなるベクトルを b 個求める．そして，クエリのソースファイルとデータベース中のソース
ファイル間の対応するベクトルを比較し，ベクトルが 1 つでも一致したものを出力する．この時，類似度を p とすると，b 個のベクトルのうち 1 つ以上のベクトルが一致する
確率は，1 − (1 − pr )b となる．パラメータ b, r を調整する
ことで，出力するソースファイルを調整することが出来る．
類似度 p に対する最尤推定量 p̂ は，ベクトルが一致した個数を x とすると，√p̂ = rxb

利用する．

3. 提案手法
本研究では，開発中ソフトウェアが再利用しているソフ
トウェアの再利用元を推定する手法を提案する．既存の様々なソフトウェアが蓄えられたデータベースが存在する
ことを前提とし，入力として開発中のソフトウェアのソー
スファイル集合が与えられると，その入力ソースファイル集合と類似するソースファイルを持つソフトウェア群をデータベースから抽出し，類似度の順に並べ替えたリストを出力する．
提案手法は，以下の 3 つのステップから構成される．

( 1 ) 開発中ソフトウェアのソースファイル集合を入力し，各ソースファイルをクエリとして川満らの手法 [6] を用いて，類似するソースファイル集合を得る．

( 2 ) 類似ソースファイル集合を，それらを保有するソフト
ウェア毎にまとめ再利用元候補ソフトウェア集合を得る．

( 3 ) 再利用元候補ソフトウェア集合の各ソフトウェアに順位付けを行い，再利用元ソフトウェアリストを出力する．

3.1 類似ソースファイルの検索入力された開発中ソフトウェアのソースファイル集合の拡張子を調べて，検索対象となるソースファイル集合となる．また，類似度 p がある程度低いと，x = 0 となり，

F = {f1 , f2 , ..., fn } を得る．そして，川満らの手法を用い類似度の推定値が 0 になる特性を持つ．川満らの手法では，64bit 長のハッシュ値を使用し，LSH のパラメータはて，F 中の各ソースファイルをクエリとして検索を行う．
ˆ が0
F 中のあるファイル fi に対し，類似度の推定値 sim

b = 120, r = 8 を利用した．その時の 1 − (1 − pr )b のグラより大きい，すなわち，真の類似度 sim がある程度大きい

フを図 1 に示す．本手法においても，同様のパラメータを類似ソースファイル集合 F̃ (fi ) を抽出する．

c 2017 Information Processing Society of Japan⃝3

Vol.2017-SE-195 No.17
2017/3/12

情報処理学会研究報告
IPSJ SIG Technical Report( 1 ) 候補ソフトウェア集合 SW に順序関係を定義し，半順

表 1 手法行列の例
候補ソフトウェア

序集合を得る

入力ソースファイル

S1

S2

S3

S4

S5

S6

f1

0.8

0

0.95

0.85

0

0.85

f2

0.8

0

0.9

0.85

0

0.95

f3

0

0

1.0

0.9

0

0.9

f4

0

1.0

0

0

1.0

0

f5

0

0.9

0

0

0.8

0

( 2 ) 有力ソフトウェアを抽出し，集合 F との距離を設定し順位付ける( 3 ) その他の候補ソフトウェアをトポロジカルソートをして順位付けしリストを出力する

3.3.1 順序関係
候補ソフトウェア集合 SW に以下のような順序関係を定

本手法では，検索を行い類似するソースファイルを得た

義し，候補ソフトウェア間に順序を付け，候補ソフトウェ

あとに，真の類似度 sim を計算する．本研究では，真のアの半順序集合 SWpo を得る．

類似度 sim による閾値を 0.8 とし，それ未満のものは類似

定義. 候補ソフトウェア Sa , Sb において，すべての入力

ソースファイルとみなさず集合 F̃ (fi ) に含めない．また，

ソースファイルについて Sa よりも Sb のほうが類似度が高あるソースファイル fi の検索結果において，同じソフト

いソースファイルを保有するとき，すなわち任意の i につウェアが持つ類似ソースファイルが複数ある場合，類似度

いて Sa [i] ≤ Sb [i] が成り立つとき，Sb は Sa よりも，再利が最も高いソースファイルをそのソフトウェアから再利用用しているソフトウェアの再利用元である可能性が高いとしたソースファイルとみなして F̃ (fi )) に含める．同一のし，Sa ≤ Sb と表す．

類似度のソースファイルが複数ある場合は，ソースファイ

表 1 から得られる候補ソフトウェア集合 S

ル名がアルファベット順で先頭のものを F̃ (fi ) に含める．

{S1 , S2 , ..., S6 } に，順序関係を定義すると，S1 ≤ S1 , S1 ≤=S3 , S1 ≤ S4 , S1 ≤ S6 , S2 ≤ S2 , S3 ≤ S3 , S4 ≤ S3 , S4 ≤3.2 候補ソフトウェア集合の取得抽出された各類似ソースファイルは，それを保有するソフトウェアがただ 1 つ存在する．本手法ではそのS4 , S4 ≤ S6 , S5 ≤ S2 , S5 ≤ S5 , S6 ≤ S6 という順序関係を持つ候補ソフトウェアの半順序集合 SWpo が得られる．

3.3.2 有力ソフトウェアの順位付け

ようなソフトウェアを候補ソフトウェアと呼ぶ．集合

候補ソフトウェアの半順序集合 SWpo 内のどの候補ソフ

F̃ (fi ) の各類似ソースファイルから候補ソフトウェア集合

トウェアよりも小さくない候補ソフトウェアは，他の候補

SW = {S1 , S2 , ..., Sm } を得る．

ソフトウェアよりも再利用元ソフトウェアである可能性が集合 F̃ (fi ) 内のある類似ソースファイル f からは，入力高いと言える．本手法では，このような候補ソフトウェア

ソースファイル fi と類似度 sim(fi , f ) で類似しており，候を「有力ソフトウェア」と呼ぶ．定義した順序関係では，

補ソフトウェア Sj が保有しているという 3 つの情報が得

有力ソフトウェア間の順序はつかない．そのため，有力ソられる．そこで，入力ソースファイル fi を行，候補ソフ

フトウェア S と入力ソースファイル集合 F 間の距離を距

トウェア Sj を列，成分を類似度 sim(fi , f ) とするような離関数を使って求め，その長さで順位を付ける．本研究でn × m 行列 M を作る．行番号 i は，入力ソースファイル fiは距離関数として，以下のようなマンハッタン距離を採用の番号，列番号 j は，候補ソフトウェア Sj の番号である．

する．

ただし，f ∈ F̃ (fi ) ∧ f ∈ Sj となるような類似ソースファ
イル f がない場合，行列の成分となる類似度を 0 とする．
この行列から各候補ソフトウェア
Sj は，行列の() j 列目の列ベクトルを得て，Sj = M1j , M2j , ..., Mnj と表す．表

1 に，入力ソースファイル 5 つ，候補ソフトウェア 6 つで構成される行列の例を示す．入力ソースファイル f1 の類
似ソースファイルのうち，候補ソフトウェア S1 が保有すd(x, y) =n∑|xi − yi |i=1

入力ソースファイル集合 F の各要素はソースファイルであるため，類似度ベクトル Fsim を求める．入力ソースファ
イル fi 自身との類似度であるため，類似度 sim(fi , fi ) = 1
である．よって，Fsim の全てのベクトルの大きさは 1 である．有力ソフトウェア S と入力ソースファイル集合 F 間るものの類似度は 0.8 と読むことができる．

の距離 d(Sj , Fsim ) は，上の式に当てはめると，n∑d(Sj , Fsim ) =|Sj (i) − 1|

3.3 候補ソフトウェアの順位付けとなる．距離関数からわかるように，入力ソースファイル

i=1

類似するソースファイルを 1 つでも持てば候補ソフトとの類似度が高いほど，また，類似ソースファイルを多くウェアとなる．そのため，候補ソフトウェア集合 SW は，持つほど，距離 d(Sj , F ) は短くなる．よって，有力ソフト

非常に大きくなる可能性があり，そこから再利用元ソフト
ウェアを見つけ出すことは困難である．そこで，本手法では以下の手順により，候補ソフトウェアを絞り込み集合 Fに類似しているように順位付けを行う．

c 2017 Information Processing Society of Japan⃝

ウェアにおいては，距離が短い順に順位を付ける．ただし距離が同じ場合は，入力によるものとする．
例の半順序集合 SWpo における有力ソフトウェアは，

4Vol.2017-SE-195 No.17
2017/3/12

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

有力ソフトウェアの順位付け後の行列
候補ソフトウェア

S2

S3

S6

S2

○ ○ ○

S1

S4

S5

f1

0.95

0.85

0

0.8

0.85

0

f2

0.9

0.95

0

0.8

0.85

0

f3

1.0

0.9

0

0

0.9

0

f4

0

0

1.0

0

0

1.0

f5

0

0

0.9

0

0

0.8

入力ソースファイル

S3

S6

S5

S4

S1

図 2

S2 , S3 , S6 である．各有力ソフトウェアと集合 F との距離

有向非巡回グラフの例

は，それぞれ 3.1，2.15，2.3 となる．有力ソフトウェアを
表 3

距離が短い S3 , S6 , S2 の順に 1 位，2 位，3 位と順位を付け

トポロジカルソート後の行列

る．k 位である候補ソフトウェアが k 列目となるように列

候補ソフトウェアを入れ替えた行列を表 2 に示す．順位が確定した有力ソフ

入力ソースファイル

トウェア名には○印を付けており，残りの候補ソフトウェ

S
S
S
S
○ ○ ○
○
○
○
S3

S6

2

4

5

1

f1

0.95

0.85

0

0.85

0

0.8

アは順位がついていない．

f2

0.9

0.95

0

0.85

0

0.8

3.3.3 トポロジカルソート

f3

1.0

0.9

0

0.9

0

0

本手法では，ソフトウェアの再利用元を順位付けて出力

f4

0

0

1.0

0

1.0

0

することを目的としている．再利用元が有力ソフトウェア

f5

0

0

0.9

0

0.8

0

でない可能性もあるため，残りの候補ソフトウェアも順位をつける．残りの候補ソフトウェアについては，半順序集

順に選択しそれぞれ 4 位，5 位と順位付ける．そして DAG

合 SWpo の各要素を半順序関係に矛盾しないように並べ替からノード S4 , S5 とそのノードへの入力辺を削除し，再びえて順位付ける．そこで本手法では，トポロジカルソート

極大元を選ぶ．残ったノード S1 が極大元であるので選択を利用する．

し，6 位と順位付ける．有力ソフトウェアの順位付けと同半順序集合は，Sa ≤ Sb のとき，Sa から Sb に向かう辺を様に k 位である候補ソフトウェアが k 列目となるように列つくることで有向グラフとみなすことができる．ただし，を入れ替え，すべてのソフトウェアの順位が確定した行列

反射律 Sa ≤ Sa と，反対称律 Sa ≤ Sb かつ Sb ≤ Sa を満を表 3 に示す．

たすような辺はつくらない．また，Sa ≤ Sb かつ Sb ≤ Sc

手法では最後に例のような候補ソフトウェアを順位付けのとき推移律である Sa ≤ Sc を満たすような辺もつくらな

並べ替えた行列をリストとして出力する．リストを先頭かい．反射律と反対称律を満たす辺が存在しないということ

ら見ることでソフトウェアの再利用元を推定することが出は，グラフ上では閉路が存在しない，すなわちグラフが 有

来る．この例では，入力ソースファイル f1 , f2 ., f3 の再利

向非巡回グラフ であることに対応する．

用元はソフトウェア S3 ，入力ソースファイル f4 , f5 の再利

半順序集合を表現した 有向非巡回グラフ に対してトポ
ロジカルソートを適用する．半順序関係にトポロジカル
ソートを使用し得られる解は，半順序関係の順序を満たす

用元はソフトウェア S2 であると推定することが出来る．

4. 実験

ような全順序の 1 つに相当する．有力ソフトウェアは有向

手法が出力する候補ソフトウェアリストと有力ソフト

非巡回グラフにおいて，出力辺が 0 であるノードで極大元ウェアから再利用元ソフトウェアを推定できるか確認するにあたる．有力ソフトウェアを除く候補ソフトウェアの半ために，提案手法を Java で実装して実験を行った．対象

順序集合 SWpo に以下の手順でトポロジカルソートを行い

言語は C/C++，Java とした．本節では，はじめにデータ

順位付ける．

ベースに登録するソフトウェアおよびファイルについて説( 1 ) DAG の極大元であるノードをすべて選択

明する．そして，Mozilla Firefox が再利用しているソフト( 2 ) 選択したノードを選択した順に順位付け

ウェア 20 個と，Android が再利用しているソフトウェア( 3 ) DAG から選択したノードとそのノードへの入力辺を52 個をデータセットとして実験を行い評価した．本稿では削除( 4 ) DAG にノードが残っていれば 1. へ戻る

スペースの都合上，データセットの説明は省略するが，ソフトウェアのリストは [14] に収録している．

例の半順序集合 SWpo から生成された有力ソフトウェア
を含む DAG を図 2 に示す．有力ソフトウェアであるノー4.1 データベース

ドは◎で囲っており極大元であることがわかる．有力ソフ

データベースに登録するデータセットとして，フリーなトウェアを除く DAG の極大元は，S4 と S5 であり，このオペレーションシステムである Debian GNU/Linux が使

c 2017 Information Processing Society of Japan⃝5

Vol.2017-SE-195 No.17
2017/3/12

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

用しているアーカイブのスナップショット *1 を利用する．
てのパッケージのソースコードが含まれている．本研究100

このアーカイブには 2005 年以来の使用してきたほぼすべ

す．アクセスした日付は，2016 年 8 月 19 日である．本手

50

では，1 パッケージを再利用元ソフトウェアの 1 つとみな

パターンにマッチしたもののみをダウンロードした．

20

法では独自の変更が加えられていない，“*.orig.*” という

10

ダウンロードしたデータセットは，33,496 種類のパッケージを含んでおり，パッケージの総数は 188,212 である．
イルは拡張子が，.c，.h，.cpp，.hpp であるもの，Java は.java

5

データベースに登録するファイルは，C/C++のソースファの総数は，50,903,100 ファイル（18,569,351,349 LOC）で2であるものを対象とした．登録対象となるソースファイルのソースファイルは，46,699,686 ファイル (17,722,308,883

LOC) である．また，Java のソースファイルは，4,203,414

1ある．LOC は，コメントや空白のみの行も含む．C/C++
FirefoxAndroid

ファイル (847,042,466 LOC) である．登録したファイルの合計ファイルサイズは，約 566GB である．

図 3 正解ソフトウェアの順位

なお，検索クエリとなる Firefox 自身とその関連プロジェ
クトは検索から除外した．

では全ての正解ソフトウェアが候補ソフトウェアリストに含まれた．また，正解ソフトウェアが有力ソフトウェアで4.2 評価方法

ある結果となったものは 52 件中 49 件（94.2%）であった．

実験は，対象プロジェクトが再利用しているソフトウェ

結果より，Firefox，Android 共に正解ソフトウェアが候

アのうち，バージョン番号がわかっているものについて行

補ソフトウェアリストに含まれていた．これより，利用しう．そのようなソフトウェアを入力ソフトウェアと呼ぶ．

ているソフトウェアの情報がわからなくとも手法を用いる入力ソフトウェアに対応するデータベース内の同名同バー

ことで，データベースに再利用元であるソフトウェアがあジョンのソフトウェアを正解ソフトウェアとする．ただし，れば高い確率でそれが含まれるソフトウェアのリストを得

正解ソフトウェアとなるものがデータベースにないようなることが可能であると言える．さらに，ほとんどの正解ソ入力ソフトウェアは用いない．入力ソフトウェアに手法をフトウェアが有力ソフトウェアであるという結果から，有適用し，以下の項目について調査し，評価と考察を行う．

力ソフトウェアから再利用元であるソフトウェアを推定す• 正解ソフトウェアが出力された候補ソフトウェアリスることが可能であると言える．

トに含まれているか．含まれているなら，正解ソフト

Firefox と Android における正解ソフトウェアの順位のウェアが有力ソフトウェアとして識別されているか．

箱ひげ図を図 3 に示す．図 3 より，ほとんどの正解ソフト• 正解ソフトウェアが有力ソフトウェアであるものにつウェアは 5 位以内である．よって，手法を用いることで有いて，正解ソフトウェアを第何位に出力したか．

力ソフトウェアの上位にあるソフトウェアが再利用元と推定することが可能であると言える．多くの 1 位ではないソ

4.3 評価結果

フトウェアは，同距離を同順位としてみなすと 1 位であっ

入力ソフトウェアに対する正解ソフトウェアが，出力さた．つまり，距離が同じソフトウェアが多くある（多くのれた候補ソフトウェアリストに含まれるかどうか，さらに場合，入力ソフトウェアが持つファイルと同内容のファイ

有力ソフトウェアであるかどうかについて調べる．結果よルをもつソフトウェアが多数ある) 状態であり，これらにり再利用しているソフトウェアの再利用元の推定を行える

ついては再利用元を推定することは難しい可能性がある．

かどうかを評価することができる．手法は入力ソフトウェ

これはソフトウェア再利用時，ソースコードに独自の変更

ア単位に適用している．Firefox では，正解ソフトウェアがを加えない場合に多く起こると考えられる．

候補ソフトウェアリストに含まれる結果となるものは，20提案手法で用いた順序関係について評価を行う．順序関件中 19 件 (95%) であった．また，正解ソフトウェアが有力係を用いると絞り込まれた有力ソフトウェアから再利用元

ソフトウェアであるのは 17 件（85%) であった．Androidを推定することが容易になると考えられる．また複数のソ
フトウェアを入力し順序関係を用いず距離のみを用いて順*1

http://snapshot.debian.org/

c 2017 Information Processing Society of Japan⃝

序付けた場合，ソースファイル数の少ないソフトウェアの6

Vol.2017-SE-195 No.17
2017/3/12

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

表 4 入力ソフトウェアをまとめた場合の各ソフトウェア数

有力ソフトウェア数

5969

598

5000

候補ソフトウェア数1000

表 5 順序関係の有無による正解ソフトウェアの順位
ソフトウェア名 順序関係なし 順序関係あり

1

5

10

50

100

500

cairo

候補ソフトウェア数

有力ソフトウェア数

入力ソフトウェア単位の場合の各ソフトウェア数

130graphite2

572

222

gtest*

1177

1855

hunspell

3963

558

libav

643

264

libevent

461

160

libﬃ

341

123

libjpeg-turbo

579

223

libopus*

269

1004

libpng2642

481

libsoundtouch

2620

479

libvorbis

657

268

nspr

99

35

nss

17

8

3495

521

snappy図 4359

stlport

228

78

zlib*

1042

1653

再利用元はリストの下位になるが，順序関係を用いること

次に，順序関係の有無による正解ソフトウェアの順位にで有力ソフトウェアとしてリストの上位になると考えられ

ついて調べる．全てのソフトウェアをまとめた入力に対しる．そこで候補ソフトウェア数と有力ソフトウェア数の比て，順序関係の有無によって得られる 2 つのリスト中の 17較を行い推定することが容易になるか調査する．また複数

つの正解ソフトウェアの順位を表 5 に示す．ソフトウェアのソフトウェアを入力し，順序関係の有無による正解ソフ

名に “*” がついているものは，入力ソフトウェアをまとめ

トウェアの順位の変動を調べる．

て入力した場合の出力では正解ソフトウェアが有力ソフト

Firefox の入力ソフトウェアに対する正解ソフトウェア

ウェアとならなかったものである．入力ソフトウェアをまが有力ソフトウェアとなった 17 件に対して評価を行う．

とめた場合の出力でも正解ソフトウェアが有力ソフトウェ

入力ソフトウェア単位で手法を適用する場合と入力ソフト

アものは，14 件であった．その 14 件に対し，正解ソフト

ウェア 17 件全てをまとめて手法を適用する場合を考える．

ウェアの順位は全て上がっていることが確認できる．しか前者については，候補ソフトウェア数と有力ソフトウェア

し，順位が 50 位以内に入るものは 2 件という結果であっ数の比較のみ行う．入力ソフトウェア単位の場合の 候補た．これは距離関数の定義より，多くの類似ソースファイ

ソフトウェア数と有力ソフトウェア数は，箱ひげ図で示す

ルを持てば距離が短くなり，より上位になるという性質かと図 4 のようになる．入力ソフトウェア 17 件をまとめた

ら複数ソフトウェアのソースファイルをもつソフトウェア

場合の候補ソフトウェア数と有力ソフトウェア数は，表 4が上位に位置しているためである．正解ソフトウェアが有に示す．図 4 より，順序関係を用いることで候補数を大幅

力ソフトウェアにならなかった gtest，libopus，zlib は，特に削減できることがわかる．また表 4 より，全てのソフト

定のソフトウェアが再利用元ソフトウェアのソースファイ

ウェアをまとめて手法を適用した場合，有力ソフトウェア

ルを完全に含んでおり，そのソフトウェアが上位に提示さ数が個別の適用結果の合計よりも多い結果となったが候補れていた．以上のことから，順序関係を用いることで再利ソフトウェア数の約 10%であり，比較的少数の候補だけ

用元候補の絞り込みは可能であるが，入力に含まれるソフを抽出していると評価することができる．入力ソフトウェ

トウェアの数が増えるほど有力ソフトウェアとなる精度がア単位の有力ソフトウェア数の合計よりも多くなった理由

落ち，順位の上昇率が減る可能性がある．

としては，2 つ以上の入力ソフトウェアのソースファイルを持つソフトウェアが有力ソフトウェアとなったと推定できる．

c 2017 Information Processing Society of Japan⃝5. 妥当性への脅威
本研究の実験において，プロジェクトが再利用してい7

Vol.2017-SE-195 No.17
2017/3/12

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

るソフトウェアの正解として Debian GNU/Linux のパッケージとして配布されているソフトウェアを利用した．各
ソフトウェアの公式なリリースの配布ではなく，Debian[3]

GNU/Linux プロジェクトによる再配布という形であり，
ソフトウェアの名前，バージョン番号が情報が正しくない
可能性がある．

[4]

本研究の実験において，入力ソフトウェアのバージョン
番号は各プロジェクトのバージョン番号が記述されている
コミットログやファイルの情報を利用した．背景でも述べているように，再利用しているソフトウェアの管理は正しく行われていないという報告があるため，実際のバージョン番号と記述されているバージョン番号が異なる可能性が

[5]

ある．

6. まとめと今後の課題
本研究では，開発中ソフトウェアが再利用しているソフ[6]

トウェアの再利用元を推定する手法を提案した．開発中ソ
フトウェアのソースファイル集合を与えると，入力ソース[7]

ファイル集合と類似するソースファイルを持つソフトウェ
アを類似する順に並べ替たリストを表示する．この類似順に並んだソフトウェアリストを見ることで，どのソフト[8]

ウェアを再利用したのか推定することが可能となる．提案
手法を用いて実験を行い，プロジェクトが再利用するソフ
トウェア 72 件の内，71 件で再利用元を含むリストを出力[9]した．また，手法では再利用元である可能性が高いソフト
ウェアを絞りこんでおり，絞り込んだソフトウェアの中に再利用元が含まれるものは 66 件であった．そのうち順位
が第 1 位のもの 50 件であり，再利用元を推定することが[10]可能であることを確認した．
今後の課題として，再利用元である可能性が高いソフト
ウェアの絞り込みを類似度による順序関係を用いたが，ソフトウェア全体が持つファイルの総数などによる絞り込み[11]を用いることで精度の向上が期待できる．さらに，絞り込み得られた有力ソフトウェアのよりよい順位付けを提案す[12]ることができれば，複数ソフトウェアを入力した場合の順位の向上が期待できる．また，再利用元の特定を行った後，どの程度ソースファイルを再利用し変更したのか，独自に新しいソースファイルをどの程度追加したかなどの調査を行うことが容易になると考えられる．
謝辞

本研究は JSPS 科研費（課題番号 JP25220003，

[13]
[14]

IEEE Software, Vol. 25, pp. 52–53 (online), DOI:
doi.ieeecomputersociety.org/10.1109/MS.2008.67(2008).
Xia, P., Matsushita, M., Yoshida, N. and Inoue, K.:
Studying Reuse of Out-dated Third-party Code in Open
Source Projects, Computer Software, Vol. 30, No. 4, pp.
98–104 (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 2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation, SCAM ’14, Washington, DC,
USA, IEEE Computer Society, pp. 305–314 (online),
DOI: 10.1109/SCAM.2014.17 (2014).
Indyk, P. and Motwani, R.: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, New
York, NY, USA, ACM, pp. 604–613 (online), DOI:
10.1145/276698.276876 (1998).
川満直弘，石尾 隆，井上克郎：LSH アルゴリズムを利用した類似ソースコードの検索，Vol. 2016-SE-191 (2016).
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).
Mohagheghi, P., Conradi, R., Killi, O. and Schwarz, H.:
An empirical study of software reuse vs. defect-density
and stability, Proceedings of the 26th International Conference on Software Engineering, pp. 282–291 (online),
DOI: 10.1109/ICSE.2004.1317450 (2004).
Kanda, T., Ishio, T. and Inoue, K.: Extraction of product evolution tree from source code of product variants,
Proceedings of the 17th International Software ProductLine Conference, Tokyo, Japan, ACM, pp. 141–150 (online), DOI: 10.1145/2491627.2491637 (2013).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder:
A Multilinguistic Token-based Code Clone Detection
System for Large Scale Source Code, IEEE Trans.
Softw. Eng., Vol. 28, No. 7, pp. 654–670 (online), DOI:
10.1109/TSE.2002.1019480 (2002).
Sasaki, Y., Yamamoto, T., Hayase, Y. and Inoue, K.:
Finding file clones in FreeBSD Ports Collection, MSR(2010).
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 IEEE/ACM International Conference on Software Engineering, pp. 331–341 (online),
DOI: 10.1109/ICSE.2012.6227181 (2012).
Leskovec, J., Rajaraman, A. and Ullman, J.: Mining ofMassive Datasets, Cambridge University Press (2011).
坂口雄亮：ソースファイル群の類似性を用いたソフトウェ
ア再利用元の推定，修士論文，大阪大学 (2017).

JP26280021）の助成を受けたものです．
参考文献
[1]

[2]

Dubinsky, Y., Rubin, J., Berger, T., Duszynski, S.,
Becker, M. and Czarnecki, K.: An Exploratory Studyof Cloning in Industrial Software Product Lines, Proceedings of the 17th European Conference on Software
Maintenance and Reengineering, pp. 25–34 (2013).
Ebert, C.:
Open Source Software in Industry,c 2017 Information Processing Society of Japan⃝

8