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

場では作業時間が限られていることが多く，優先して調査すべきコード片のみに検索結果を絞り込む技術が類似ソースコード片検索結果に対するクラスタリング技術を用いたフィルタリング手法
嶋利一真† a)井上克郎†（正員：フェロー）

石尾隆††（正員）必要である．
本研究は，NCDSearch の出力結果に対してフィルタリングを行うことで，バグを含まない類似ソースコー

A Clustering-Based Filtering Method for Similar Source Code Fragment Search
Kazumasa SHIMARI† a) , Nonmember, Takashi ISHIO†† , Member, andド片を検索結果から除去することを目指す．フィル
タリングには，Yamaguchi が提案したコード片のクラKatsuro INOUE† , Fellow

スタリング手法 [5] を応用する．この手法は，ソフト† 大阪大学大学院情報科学研究科，吹田市

Graduate School of Information Science and Technology, Osaka University, Suita-

ウェアの脆弱性の調査を行う際に，他のコード片と類shi, 565–0871 Japan似していない特異なコードを調査するべき候補として†† 奈良先端科学技術大学院大学先端科学技術研究科，生駒市

Graduate School of Science and Technology, Nara Institute of Science and Tech-取り出すというものである．本研究ではこの発想に基

nology, Ikoma-shi, 630–0192 Japanづき，検索によって得られた類似ソースコード片のうa) E-mail: k-simari@ist.osaka-u.ac.jp

ち，類似バグを含む可能性が高いものには類似するが，DOI:10.14923/transinfj.2020JDL8009

類似バグを含む可能性が低いものとは類似しないよう
あらまし

類似ソースコード片検索ツールの出力結果に対してクラスタリングを適用してコード片をグループ化し，正解の可能性が低いコード片を出力から除外するフィルタリングを提案する．バグを含む類似コード片のデータセットを用いて，提案手法の有用性を確認した．
キーワード

ソースコード検索，クラスタリング，フィルタリング，正規圧縮距離なソースコード片のみを調査対象として抽出する．

2. 提 案 手 法
提案手法は NCDSearch がクエリ q に対して検出した類似ソースコード片の集合 F に対するフィルタリングである．NCDSearch は正規圧縮距離 [6] を検索に使用しており，距離しきい値 th に対して各コード片f ∈ F とクエリの距離が d(q, f ) ≤ th を満たすようなコード片を対象ソースコードから検出する．
提案手法は，近傍探索を用いることでフィルタリン

1. ま え が き
ソフトウェア開発において，開発者はプロジェクト内でソースコードを再利用し，類似した複数の機能の実装に使用することがある．しかし，再利用元にバグが含まれていた場合，結果的にソースコード内の複数の場所に同一のバグができてしまうことがある [1]．そのため，ソフトウェアにバグが発見された場合，そのバグを含むソースコード片に類似したソースコード片グを実現する．具体的には，検索結果から得られたソースコード片をしきい値 d1 (d1 < th) によって，クエリに強く類似するものと，そうでないものに分類し，後者のグループはバグを含む可能性が低いと考える．このコード片の集合を F ′ として以下のように定義する．

F ′ = { f ′ ∈ F | d(q, f ′ ) > d1 }(1)F ′ に含まれるコード片のいずれかから距離 d2 以内にを検索し，修正することが重要となる [2]．
類似ソースコード片を検索するためのツールの一つ

あるコードは，たとえクエリと類似していても，特異として，我々の研究グループは NCDSearch（注 1）を開発なコードではないと考え，検索結果 R から以下のようしている．このツールは，クエリとして与えたソースにして除外する（クエリと完全一致するコードを R かコード片と検索対象ソースコードから順番に切り出さら除外しないように d2 < d1 とする）．

れたソースコード片を比較し，類似するソースコード片の位置（ファイル名と行番号）を全て検出する．既存のコードクローン検出ツール CCFinderX [3] 等と比較して，類似したバグを含むソースコード片の見逃しが少ないが，バグを含まないソースコード片も数多く検出される [4]．理想的には全ての検出結果を調査す
ればバグの修正も完全なものになるが，実際の開発現（注 1）：https://github.com/takashi-ishio/NCDSearch

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

R = { f ∈ F\F ′ | ∀ f ′ ∈ F ′ . d( f , f ′ ) > d2 }(2)

このようにして得られる R には，検索クエリとなったコード片と類似しており，かつ，バグを含んでいる可能性が低いコード片とは異なるようなコード片だけが含まれる． R に含まれるコード片をクエリに対する距
離 d(q, f ) の順番で出力したものが，提案手法の最終的な出力である．

No. 10 pp. 751–753 © 一般社団法人電子情報通信学会 2020751

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

3. 評 価 実 験らすほど見逃しの可能性が上がるため，再現率と削減提案手法が NCDSearch の検索結果を改善する度合率はトレードオフの関係にある．再現率を高く保ちないを，OSS におけるバグ修正事例のデータセット [7]

がら報告されるコード片の数を大きく減らすような手を用いて評価する．表 1 にデータセットの規模やバ法を高く評価するために，この調和平均を用いる．

グの数を示す．このデータセットは PostgreSQL，Git，

表 2 に調和平均 h に基づく提案手法の最良の結果とLinux において，一つの修正が複数の類似ソースコードベースラインの結果を示す．ベースライン (d1 = 0.50)

に対して行われた事例を集めたものである．クエリとの出力コード片の数は合計で 4,866 であり，その中にして与えられたコード片で検索を行い，同時に修正さは 88 個のバグが全て検出されている（再現率 1.000）．

れるべきコード片をどれだけ検出できるかを評価する．

提案手法は最良の場合で，出力結果を 80.6% 削減しな提案手法は d1 ，d2 の二つのパラメータをもつ．既存

がら，バグのうち 88.6% を出力結果に含んでいる．提研究の実験 [4] で使用したときの設定（th = 0.50）を

案手法は削減率が同程度のベースライン (d1 = 0.32) と使用し，提案手法で述べた d2 < d1 < th という関係を比較した場合に高い再現率を示しており，また，再現満たす範囲で d1 と d2 をそれぞれ 0.05 から 0.45 まで率で近い値をもつベースライン (d1 = 0.35) の場合と0.05 ずつ変化させ，フィルタリング結果 R を求める．

比べると，出力されるコード片の数を 1,176 から 942

また，評価のベースラインには，NCDSearch の結果にへと約 20% 削減している．したがって，ベースライ対して単純に距離のしきい値 d1 のみを用いてフィルンの手法で単純に距離のしきい値 d1 を変化させるよ

タリングした結果 R ′ = { f ∈ F | d(q, f ) ≤ d1 } を用いりも効率的な調査が可能である．

る．これは NCDSearch のしきい値 th を変化させた場提案手法へのパラメータの影響を図 1 に示す．各点合に相当する．ベースラインの結果は，d1 を 0.01 かの X 座標は提案手法及びベースラインにおける d1 でら 0.50 まで 0.01 ずつ変化させたものを用いる．ツーあり，Y 座標はそのときの調和平均 h である．提案手

ルの利用者が全クエリの実行結果を全て確認する場合を想定し，クエリごとに得られる R の和集合を提案手法の検索結果，クエリごとに得られる R ′ の和集合を

表 2 提案手法とベースラインのフィルタリングの精度
Table 2 Filtering accuracy of the proposed method and baseline.

ベースラインの検索結果とする．評価実験において使（注 2）

用した NCDSearch のバージョンは v0.3.5である．

評価に用いるのは以下の指標である．
適合率． コード片集合出力結果のコード片のうち，バグを含むコード片の割合．
再現率． バグを含むコード片のうち，検索結果に含適合率 再現率 削減率 調和平均
提案手法
( d1 = 0.35, d2 = 0.25)
ベースライン ( d1 = 0.30)
ベースライン ( d1 = 0.31)
ベースライン ( d1 = 0.32)
ベースライン ( d1 = 0.35)
ベースライン ( d1 = 0.50)

0.083

0.886

0.806

0.844

0.081
0.082
0.077
0.067
0.018

0.773
0.830
0.841
0.898
1.000

0.827
0.816
0.802
0.758
0.000

0.799
0.823
0.821
0.822
0.000

まれるものの割合．
削減率 r ． th = 0.50 での検索結果を基準としたソー|R′ ||R |スコード片の減少の割合（r = 1 − |F | または 1 − |F | ）．
この値が高いほど利用者が確認するコード片の数が少ない．
再現率と削減率の調和平均 h．

出力される結果を減

表 1 類似ソースコード片のデータセット
Table 1 Dataset for similar source code fragments.
プロジェクト

クエリ バグ

PostgreSQL
Git
Linux
合計

145345339841
88

ファイル数の中央値

行数の中央値

1,058
261
22,181
792,432

277,959
67,0286,931,715
241,074,652（注 2）：commitID:5b76c37193741edfd41fbd7b865d04194cb3ddfa

752

Fig. 1図 1 提案手法とベースラインの調和平均 hHarmonic mean of the proposed method and baseline.

レター

法については d2 として複数の値を使用しているため，それらの結果を全てプロットしている．この図から，謝辞

本 研 究 は 科 学 技 術 研 究 費 JP18H03221，

JP18KT0013，JP18H04094 の助成を受けて行われた

調和平均 h の値は安定してベースラインと同じ程度か，良い結果を示しており，提案手法はソースコード

文[1]

Oct. 2001.
[2]あたり平均で 1 秒未満であった．NCDSearch の実行

4. む す びpp.53–62, May 2017.
[3]

Proc. ICSME, pp.591–594, Sept. 2018.
[5]

トの事例に限られているため，新たな OSS の修正事

M. Li, X. Chen, X. Li, B. Ma, and P.M.B. Vitanyi, “The similaritymetric,” IEEE Trans. Inf. Theory, vol.50, no.12, pp.3250–3264,
Dec. 2004.

フィルタリングよりも再現率を高く保ちながら検索結実験で用いたデータセットは C 言語の 3 プロジェク

F. Yamaguchi, “Pattern-based vulnerability discovery,” Ph.D. Thesis, University of Göttingen, 2015.

[6]るフィルタリング手法を定義した．その結果，単純な果の個数を削減可能であることを示した．

T. Ishio, N. Maeda, K. Shibuya, and K. Inoue, “Cloned buggy
code detection in practice using normalized compression distance,”

Yamaguchi の脆弱性調査の手法を類似ソースコードド片とは異なるようなソースコード片だけを抽出す

T. Kamiya, AIST CCFinderX, http://www.ccfinder.net/ccfinderxos.html[4]

本 研 究 で は ，特 異 な コ ー ド に 注 目 す る と い う
検索に応用し，クエリから相対的に遠いソースコー

Y. Dang, D. Zhang, S. Ge, R. Huang, C. Chu, and T. Xie, “Transferring code-clone detection and analysis to practice,” Proc. ICSE,

時間はクエリ 1 回あたり平均で 8.5 分であり，それに比べて軽微なコストで出力結果を改善している．

A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler, “An empirical study of operating systems errors,” Proc. SOSP, pp.73–88,

検索結果の改善に有効であることが分かる．
なお，提案手法によるフィルタリングはクエリ 1 回

献[7]

J. Li and M.D. Ernst, “CBCD: Cloned buggy code detector,” Proc.
ICSE, pp.310–320, June 2012.

（2020 年 4 月 23 日受付，5 月 29 日再受付，6 月 22 日早期公開）

例や，NCDSearch を利用しているソフトウェア企業環
境 [4] での効果を調査することが今後の課題である．

753