ソースコード流用の コードクローンメトリクスに基づく検出手法

Presentation on theme: "ソースコード流用の コードクローンメトリクスに基づく検出手法"— Presentation transcript:

1 ソースコード流用の コードクローンメトリクスに基づく検出手法
†奈良先端科学技術大学院大学 情報科学研究科 ‡大阪大学 大学院情報科学研究科 ○岡原聖† 　真鍋雄貴‡ 　山内寛己† 門田暁人† 　松本健一† 知能ソフトウェア工学研究会

2 出荷前にソースコード流用の有無を 検出する技術が必要とされている
背景 近年，オープンソースソフトウェア（OSS）を流用した ソフトウェア開発が増えている 開発コストの低減，高信頼性の確保 開発の外注等によりOSSのソースコードが意図せず 混入し，ライセンス違反を犯してしまうケースがある Microsoftが外注したWindows7へのUpgrade支援ツール[1] SCEIが開発したPS2ゲーム「ICO」のライブラリ[2] 近年，ソフトウェア開発の現場において開発コストの削減や， 高信頼性を確保する為に，オープンソースソフトウェアを流用して 開発を行うことがあります． そのとき，OSSのソースコードを用いるとき，そのライセンスに気をつける必要があります． しかし，現実には，開発委託先などでOSSのソースコードが混入し， 開発委託元が意図しないライセンス違反が起こるケースが報告されています． 具体的な，ライセンス違反の事例としては， 「つい2週間ほど前になりますが，Microsoftが開発を外注したWindows7への Upgrade支援ツールでGPL違反を犯した事例」や 「SCEの開発したPS２のゲームであるICOのライブラリの事例」があります． このようなライセンス違反対策の一つとして， 「出荷前にソースコード流用を検出し，流用かどうかを判断する技術」 が必要とされています 出荷前にソースコード流用の有無を 検出する技術が必要とされている [1]： “「USB版Windows 7」作成ツールにGPLコード　Microsoftが謝罪”, [2]： “PlayStation 2 Game ICO Violates the GPL”, 知能ソフトウェア工学研究会

3 ソースコード流用とコードクローン 流用したコードはコードクローン（以下クローン） として表れる コードクローン（重複するコード列）
コードの流用 本発表では，ソフトウェア間にまたがる類似または一致するコード列 （コードクローン）を用いて流用を検出します． ソースコード流用とクローンの関係ですが， たとえば，OSSのある機能を流用した場合， 流用元のOSSと，開発を行ったソフトウェアには同一または類似した コード片が存在することになるので， 流用したコードはコードクローンとして表れます． ですので，クローンの検出は流用検出に役立つことが期待されます． 流用先のソフトウェア 流用元のOSS コードクローン（重複するコード列） 知能ソフトウェア工学研究会

4 どの程度の量のクローンが検出されたならば 流用とみなせるかを明らかにする必要がある
ソースコード流用検出の難しさ クローンは独立に開発されたソフトウェア間でも 存在する 定型処理，偶然の一致など 流用の事実はない GUI生成の 定型処理 どの程度の量のクローンが検出されたならば 流用とみなせるかを明らかにする必要がある 　1．クローンの量を測るメトリクスが必要 　2．メトリクス値について流用とみなす基準値が必要 ただし，クローンは必ずしも流用ではない可能性があります． これはクローンの発生理由に定型処理や偶然の一致などが そんざいするため，独立に開発されたソフトウェア間でクローンが 検出されたとしても流用ではない可能性があります． 下の例のように，GUIなどはコードの自動生成ツールなどで， 生成されることがある為，単純にクローンを用いるだけでは， 流用を検出することは難しいと考えられます． そこで，どの程度の量のクローンが検出されたならば， 流用ありとみなせれるかを明らかにする必要があります． そのためには，まず，流用を検出するのに有効なクローンメトリクスが必要です． また，そのメトリクス値がどの程度であれば， 流用と判断できるかを示す基準値が必要だと考えられます． GUI生成の 定型処理 出荷するソフトウェア OSS コードクローン（重複するコード列） 知能ソフトウェア工学研究会

5 研究目的，アプローチ 研究目的 アプローチ クローンの量によりソースコード流用の有無を 判断する方法を確立する
任意の２つのソフトウェア間で，一方が他方のソースコードを 流用しているか否かを定量的に判断する アプローチ ２つのクローンメトリクスを提案する 最大クローン長 部分類似度 各メトリクスの流用と見なす基準値（閾値）を求める 多数のOSSを用いて実験的に求める そこで，本研究ではクローンの量により，ソースコード流用の有無を 判断する方法を確立することを目的とします．任意の2つのソフトウェア間で， 一方が他方のソースコードを流用しているか否かを定量的に判断します． アプローチとして， ２つのコードクローンメトリクス「最大クローン長」と，「部分類似度」を を提案します．また，各メトリクスについて，多数のOSSを題材として 流用と判断する基準値（閾値）を求めます． 次のスライドで，本発表で用いる，コードクローンの種類について説明します． 知能ソフトウェア工学研究会

6 本研究で用いるクローン 流用後に変数名や定数名などを 変更することがありえるため クローンの種類 Exact Clone 完全一致のクローン
Renamed Clone 変数名や空行の不一致を許容するクローン Gapped Clone コードの削除，追加を許容するクローン クローンには， 変数名，定数名など全てが完全に一致する Exact Clone, 変数名や空行の不一致を許可する Renamed Clone, Renamed Clone に加えて，コードの削除や追加のある Gapped Clone が存在します． 本発表では，Renamed Cloneをもちいます． これは，流用を行った後，変数名や定数名などを変更することが あり得る為です．その際に，コードの削除や追加もあると考えられますが， それについては，今後考えていきたいと思っています． 次に，Renamed Clone の検出方法について説明します． 流用後に変数名や定数名などを 変更することがありえるため 知能ソフトウェア工学研究会

7 Renamed Cloneの検出方法 トークン解析 プログラム言語の字句規則に従いトークンに分割する
トークン変換 変数(p)，定数(i)，型(t) 種類毎にトークンを置換する マッチング 一致する部分列をクローンとする ．．． ．．． ．．． ．．． クローンの扱いは行単位，トークン単位など検出手法によって異なりますが 本発表ではトークン単位のクローンを用いたので， トークン単位のクローンの検出手法について簡単に説明します． } x = b - c ; if ( while > ) n { y = ; x = y - z ; if ( x > ) n = 1 ; z = ; 知能ソフトウェア工学研究会

8 Renamed Cloneの検出方法 トークン解析 プログラム言語の字句規則に従いトークンに分割する
トークン変換 変数(p)，定数(i)，型(t) 種類毎にトークンを置換する マッチング 一致する部分列をクローンとする ．．． ．．． ．．． ．．． まず，プログラム言語の字句規則に従って，トークンとよばれる プログラミング言語の最小単位に分割します． } x = b - c ; if ( while > ) n { } x = b - c ; if ( while > ) n { y y = x - z ; if ( > ) n 1 = ; x = y - z ; if ( x > ) n = 1 ; z = ; 知能ソフトウェア工学研究会

9 Renamed Cloneの検出方法 トークン解析 プログラム言語の字句規則に従いトークンに分割する
トークン変換 変数(p)，定数(i)，型(t) 種類毎にトークンを置換する マッチング 一致する部分列をクローンとする ．．． ．．． ．．． ．．． 次に，分割したトークンを，変数，定数，型といった 種類ごとにトークンを置換します． } p = - ; if ( while > i ) { p = i - ; if ( > ) } x = b - c ; if ( while > ) n { } x = b - c ; if ( while > ) n { y y = x - z ; if ( > ) n 1 = ; x = y - z ; if ( x > ) n = 1 ; z = ; 知能ソフトウェア工学研究会

10 Renamed Cloneの検出方法 トークン解析 プログラム言語の字句規則に従いトークンに分割する
トークン変換 変数(p)，定数(i)，型(t) 種類毎にトークンを置換する マッチング 一致する部分列をクローンとする ．．． ．．． ．．． ．．． そして，一致する文字列を検出し，クローンとして扱います． 以上が，トークン単位でのRenamed Clone の検出方法です． 次のスライドから， 本発表で提案するクローンメトリクスについて説明していきます． } p = - i ; if ( while > ) { } p = - ; if ( while > i ) { p = i - ; if ( > ) p = i - ; if ( > ) } x = b - c ; if ( while > ) n { } x = b - c ; if ( while > ) n { y y = x - z ; if ( > ) n 1 = ; x = y - z ; if ( x > ) n = 1 ; z = ; 知能ソフトウェア工学研究会

11 流用検出のためのクローンメトリクス(1) 最大クローン長[3]
定義 検出されたクローンで最大のトークン数 最大クローン 最大クローン長 まず，一つ目のメトリクスである最大クローン長はソフトウェア間で 検出されるクローンのうちで，最もトークン数の多いクローン（最大クローン）の トークン数のことをいいます． この最大クローンの長さを，最大クローン長とよぶことにします． 最大クローン長と，流用の関係は １）異なるソフトウェア間で長いクローンが検出される可能性は低い為， 長いクローンが検出されると流用の疑いが高い． ２）クローンの発生理由の一つに「偶然の一致」が存在するため， 偶然一致するような短いクローンは流用の疑いが低いと考えられます． これらの関係は，既存研究で正しいことが分かっています． ファイル群 A ファイル群 B 最大クローン長と流用の関係 最大クローン長が大きい：流用の可能性は高い 最大クローン長が小さい：流用の可能性は低い [3]：岡原 聖, 真鍋 雄貴, 山内 寛己, 門田 暁人, 松本 健一, 井上 克郎, “コードクローンの長さに基づくプログラム盗用確率の実験的算出,” 信学技報, No.SS , pp.7-11, Oct 知能ソフトウェア工学研究会

12 流用検出のためのクローンメトリクス(2) 部分類似度
定義 最大クローンを含むファイルにのみ着目した類似度 算出式 ファイルの長さ ｜a｜ 2つめのメトリクスの「ソフトウェア間の部分類似度」について説明します． この類似度は，2つのソフトウェア間で「最大クローン」を含むファイル間の 類似度です． 算出方法は，ファイルの長さを足し合わせた値で， 最大クローン長を2倍した値を割ったモノです． メトリクスの特徴としては、ファイル全体が類似していなくとも 部分的な流用が存在すると類似度は高くなるというものです。 これら2つのメトリクスを用いた，流用の判断方法について 次のスライドから説明していきます． ファイルの長さ ｜b｜ 最大クローン長 　 MLCC ファイル全体を流用していなくとも， 部分的な流用が存在すると部分類似度は大きくなる ファイル群A ファイル群B 知能ソフトウェア工学研究会

13 流用の判断方法 閾値を超えるクローンを流用あり（流用なし）と 判断する 流用なし閾値 流用あり閾値 検出されるクローン は流用ではない
検出されるクローンは流用である 本発表では，2つの閾値を用いて流用の有無を判断します． まず，閾値を超えた場合，流用であると判断する流用あり閾値， もう一つは，閾値を下回った場合，流用ではないと判断する 流用なし閾値，以上の２つを提案します． これらの閾値は，理論的に求めることは不可能ですので， まず，多数のOSSを集め，人手により流用のあり（なし）を判断した 正解集合を作成します．その正解集合を用いて実験的に閾値を導出します． まず，これらの閾値を導出するために（閾値に）求められる要件を整理します． これらの閾値は理論的に求めることは不可能 1．多数のソフトウェアを集めて正解集合を作成する 2．正解集合を用いて実験的に閾値を求める 流用なし閾値 流用あり閾値 (例：最大クローン長) 知能ソフトウェア工学研究会

14 閾値の決定方法 閾値は必ず流用あり（流用なし）と判断できるもの：false-positiveなし 適合率 再現率
適合率，再現率を用いて閾値を導出 適合率 検出結果中に含まれる正検出の割合を示す指標 再現率 正解集合のうち，どの程度正検出できたかを示す指標 閾値を用いる場合，閾値を超えるクローンは必ず流用と判断できる必要， つまり false-positive なしの必要があります． これは，流用のないケースを流用ありと判断しない為です． そこで，閾値を導出する為に，適合率と再現率を用いることを考えました． 適合率とは，検出結果中に含まれる正検出数の割合のことで， 適合率が高いほど，流用が含まれていることになります． 再現率とは，正しい結果がどれだけ検出できているかを表す指標です． 特に，適合率が１ということは，検出結果すべてに流用があることを 示す為，適合率1をとるクローンメトリクスの値を閾値に用います． そのとき，多くの流用を検出する為に再現率が最も高い値をしようします． この適合率と再現率を用いて，実験的に，流用の閾値を導出します． 適合率が 1 かつ 再現率が最大値となる 各メトリクスの値を閾値とする 知能ソフトウェア工学研究会

15 閾値の導出実験 実験目的 実験環境 流用の判断基準となる閾値を， 多数のOSSを用いて実験的に導出する クローン検出ツール
CCFinderX[4] 実験対象のソフトウェア 50件のOSS ドメイン：Security, Audio, Game など 開発言語：C言語，C++ 実験の目的は，流用の判断基準となる閾値を， 多数のOSSを用いて実験的に導出することです． 実験環境としては，産総研の神谷博士によって開発された トークン単位に基づくクローン検出ツールCCFinderXをもちいました． 実験対象に，50件のOSSをもちいました． これらのOSSは多様なドメインからなり， 全てCまたはC++で開発されています． [4]： “CCFinderホームページ”, 知能ソフトウェア工学研究会

16 閾値の導出における実験手順 50件のOSSを用いて，正解集合を作成する OSSの全ての組合せにおいてクローンを検出する
プログラムの構造，コメント文，クローンの内容などから判断した OSSの全ての組合せにおいてクローンを検出する 最大クローン長，部分類似度を算出する 流用あり（流用なし）の適合率，再現率をそれぞれ算出する 組合わせの分類 組合せ件数 ソースコード流用ありの組合せ 121 ソースコード流用なしの組合せ 648 クローンのない組合せ 456 実験手順です． 1．はじめに，50件のOSSを用いて流用のあり，なしを区別した 正解集合を作成します．これは，プログラムの構造，コメント文， クローンの内容などから判断しました．その結果が下の表になります． この，流用ありの組合せと，流用なしの組合せを用いて 実験を行います． 2．次に，全OSSの組み合わせに対して，クローンを検出します． 3．検出したクローンから最大クローン長，部分類似度を算出します 4．そして，流用ありの適合率，再現率，また， 流用なしの適合率，再現率をそれぞれ算出します． 知能ソフトウェア工学研究会

17 閾値の導出結果 流用あり（最大クローン長） 流用あり閾値 知能ソフトウェア工学研究会
まず，最大クローン長をもちいた流用ありの適合率と再現率のグラフです． 前述しましたように，適合率１かつ再現率が最大のときを しようしますので，最大クローン長を用いた流用ありの 閾値は２７０になります． 流用あり閾値 知能ソフトウェア工学研究会

18 閾値の導出結果 流用なし（最大クローン長） 流用なし閾値 知能ソフトウェア工学研究会
最大クローン長をもちいた，流用なしの適合率と再現率のグラフです． このグラフから，最大クローン長を用いた流用なし閾値は５０になります． 流用なし閾値 知能ソフトウェア工学研究会

19 閾値の導出結果 流用あり（部分類似度） 流用あり閾値 知能ソフトウェア工学研究会 部分類似度を用いた流用ありの適合率，再現率のグラフです．
同様にして，部分類似度をもちいた流用あり閾値を求めると， その値は０．３０になります． 流用あり閾値 知能ソフトウェア工学研究会

20 閾値の導出結果 流用なし（部分類似度） 流用なし閾値 知能ソフトウェア工学研究会
最後に，部分類似度を用いた流用なしの適合率，再現率のグラフです． 部分類似度を用いた流用なし閾値は，決定できませんでした． これは，部分類似度が小さい値でも流用が存在した為です． 流用なし閾値 知能ソフトウェア工学研究会

21 2つのメトリクスを併用して流用を検出することで
閾値の導出結果 最大クローン長 流用あり 部分類似度 流用あり 最大クローン長流用なし 部分類似度 流用なし 検出できた件数 91 72 421 － 検出できなかった件数 30 49 227 総件数 121 648 流用あり閾値 両メトリクスとも半数以上の流用を検出できている 流用なし閾値 部分類似度の流用なし閾値を導出できなかった この表は流用あり（なし）が検出できた件数，出来なかった件数を表したものになります． 本データセットを用いた場合，流用ありの閾値はどちらのメトリクスを用いても， 半数以上の流用を検出できることがわかりました． また，繰り返しになりますが，流用なしの閾値は部分類似度を用いた場合では 流用なしの閾値を導出できませんでした． ここで，メトリクスを単独に使用するのではなく，2つのメトリクスを用いて流用を 検出することでより多くの流用を検出できるかどうかの追実験を行いました． 具体的にはクローン長で検出できない30件の流用を，部分類似度を用いて 検出しました． 2つのメトリクスを併用して流用を検出することで 検出割合が向上するかを確認する 知能ソフトウェア工学研究会

22 102件（約84%）をfalse-positiveなしで検出できた
追実験の結果 最大クローン長 流用あり 部分類似度 流用あり 最大クローン長流用なし 部分類似度 流用なし 検出できた件数 91 72 421 － 検出できなかった件数 30 49 227 総件数 121 648 結果 最大クローン長で検出できなかった30件の流用のうち， 11件を流用として検出できた 2つのメトリクスを用いて流用検出を行った場合， 一つのメトリクスで検出出来ない流用を11件ほど検出できました． 具体的には，作成した流用ありの正解集合121件中， 102件（約84%）をfalse-positiveなしで検出出来ました． 作成した流用あり正解集合121件のうち， 102件（約84%）をfalse-positiveなしで検出できた 知能ソフトウェア工学研究会

23 メトリクスを併用して検出できた流用 最大クローン長 59，部分類似度 0.32 ファイル長さ：141 ファイル長さ：223 /*
/* Splice in "list" into "head" */ static inline void glame_list_splice(struct glame_list_head *list, struct glame_list_head *head) { 　struct glame_list_head *first = list->next; 　if (first != list) { 　　struct glame_list_head *last = list->prev; 　　struct glame_list_head *at = head->next; 　　first->prev = head; 　　head->next = first; 　　last->next = at; 　　at->prev = last; 　} } /* * Splice in "list" into "head" */ static INLINE void list_splice(struct list_head *list, struct list_head *head) { 　struct list_head *first = list->next; 　if (first != list) { 　　struct list_head *last = list->prev; 　　struct list_head *at = head->next; 　　first->prev = head; 　　head->next = first; 　　last->next = at; 　　at->prev = last; 　} } 最大クローン長で検出できず，部分類似度を用いて 検出することが出来た例になります． ファイル規模が200程度で，必ず最大クローン長を下回るため， 最大クローン長で検出できないものです． そこで，部分類似度をもちいると，部分類似度は高い値を示した為， 検出することが出来ました． ファイル長さ：141 ファイル長さ：223 最大クローン長　59，部分類似度　0.32 知能ソフトウェア工学研究会

24 まとめ，今後の課題 まとめ ソースコード流用のクローンメトリクスを用いた 検出手法を提案した
最大クローン長と部分類似度の流用あり閾値， 流用なし閾値を導出した 流用あり閾値を用いて約84%の流用を false-positiveなしで検出できた 今後の課題 流用あり（流用なし）検出の精度向上を目指す 他のクローンメトリクスを調査する 本発表では，ソースコード流用のクローンメトリクスに基づく 検出手法を提案しました． 提案手法で用いる為の，最大クローン長，部分類似度の しきいちをどうしゅつしました． 閾値をもちいることで，約84％の流用をfalse-positiveなしで 検出できました． 今後の課題としては，検出の精度向上を目指していきたいと 考えています．具体的には他のクローンメトリクスを 調査してきます． 知能ソフトウェア工学研究会

25 知能ソフトウェア工学研究会 基本は読んで面白い，または，なるほど．と思わせること． まず，アブストで面白い，必要だと思わせかが必須．
テーマの選び方のところである程度勝負は決まっている． 　→運がからみますよということかな？ 知能ソフトウェア工学研究会

26 知能ソフトウェア工学研究会

27 関連研究 コードクローンを用いた手法：JPlag[4] Jplagの問題点 クローンに基づいた「ソースコード間の類似度」を用いる
ソースコードの一部分だけを利用する流用を， 流用ありと判断することが難しい クローン ファイル群 A ファイル群 B [4]： L. Prechelt, G. Malpohl, and M.Philippsen, “Finding Plagiarisms among a Set of Programs with JPlag,” J.Universal Computer Science, vol.8, no.11, pp , Nov 知能ソフトウェア工学研究会

28 関連研究 バースマークを用いた手法 バースマークの問題点
バースマークとは クラスの継承関係，クラスの出現回数，クラスの実行順序などのプログラムの特徴量 バースマークを併用して流用（盗用）の検出を行う バースマークの問題点 流用の検出を行う者（ＰＭ，品質管理実施者など）が 定性的に判断する必要がある 一意に決定することが困難である ソフトウェア全体での判断になる [5]：玉田 春昭, 神崎 雄一郎, 中村 匡秀, 門田 暁人, 松本 健一, ``Java クラスファイルからプログラム指紋を抽出する方法の提案'', 信学技報 情報セキュリティ研究会, Vol. ISEC , pp , July 2003. 知能ソフトウェア工学研究会

29 本研究の使用用途 ソフトウェアの開発委託元が， 開発委託先で流用を行っていないかの確認
学生の演習課題でコピーアンドペーストを 行っていないかの確認 民事裁判での証拠 裁判では互いの資料提出があるため，コードクローンを利用することは可能 学生の演習課題などでは，必ずしも全ての流用を検出する必要は無い →　大まかに把握することが出来たらよい． 知能ソフトウェア工学研究会

30 目安となる閾値が存在することで， 人手による判断を行うクローンを減少出来る
人手によるコスト ソフトウェア間でクローン検出を行うと， 多数のクローンが検出される コストが非常に高いことが予想される 目安となる閾値が存在することで， 人手による判断を行うクローンを減少出来る 知能ソフトウェア工学研究会

31 ソースコード流用による損害賠償 CAおよび1999年にCAが買収した米PLATINUM technology Internationalで勤務経験のあるプログラマや ソフトウエア開発者を雇用して盗用を行う 賠償内容） 約2億ドルの損害賠償および恒久的差し止めを求める（継続中） Mark ZuckerbergがConnectUの知的財産権およびコードを盗んでこの巨大人気ソーシャルネットワークを構築 賠償内容） 約6500万ドルの損害賠償を受け取る CA，DB管理ソフトのソースコード盗用などでRocket Softwareを提訴 CAに提訴されたIBM DB2用ツール作成のRocket，「時効」の主張通らず The AP Reveals Details of Facebook/ConnectU Settlement With Greatest Hack Ever 法律事務所の大ポカでFacebookのConnectUへの支払額が明らかに：$65M 知能ソフトウェア工学研究会

32 検出できなかった流用 最大クローン長 78，部分類似度 0.085 ファイル長さ：636 ファイル長さ：1191
if (size == 0) return NULL;　/* no allocation required */ /* Allocate combined header + user data storage. */ { register pointer new = malloc (sizeof (header) + size); /* address of header */ ((header *)new)->h.next = last_alloca_header; ((header *)new)->h.deep = depth; last_alloca_header = (header *)new; /* User storage begins just after header. */ return (pointer)((char *)new + sizeof(header)); } if (size == 0) 　return NULL;　/* No allocation required. */ /* Allocate combined header + user data storage. */ { register pointer new = malloc (sizeof (header) + size); 　/* Address of header. */ 　((header *) new)->h.next = last_alloca_header; 　((header *) new)->h.deep = depth; 　last_alloca_header = (header *) new; 　/* User storage begins just after header. */ 　return (pointer) ((char *) new + sizeof (header)); } ファイル長さ：636 ファイル長さ：1191 最大クローン長　78，部分類似度　0.085 知能ソフトウェア工学研究会

33 閾値の導出における実験手順 適合率と再現率から流用あり閾値を導出する 流用あり閾値 知能ソフトウェア工学研究会
5．そして最後に，閾値を導出します． 閾値は，「適合率1」かつ「適合率１のときの再現率の最大値」を とるメトリクスの値を取るので， この例では，230のメトリクスの値が流用あり閾値になります． 流用あり閾値 知能ソフトウェア工学研究会

34 閾値の導出における実験手順 適合率と再現率から流用なし閾値を導出する 流用なし閾値 知能ソフトウェア工学研究会
また，同様にして，流用なしの閾値を導出します． この例ですと，メトリクスの値　８０が流用なしの閾値になります． 以上の手順で，提案手法で用いる閾値を導出する実験を行います． 次のスライドから，実験結果を述べていきます． 流用なし閾値 知能ソフトウェア工学研究会

35 流用ありの判断方法 流用あり判断のフローチャート Start： Goal： Goal： ソースコードの組(a,b)を入力 True
TR-MLCC <MLCC(a,b) False True TR -PSim<PSim(a,b) False Goal： ソースコード流用あり Goal： 判断が困難 知能ソフトウェア工学研究会

36 流用なしの判断方法 流用なし判断のフローチャート Start： Goal： Goal： ソースコードの組(a,b)を入力 True
TNR-MLCC <MLCC(a,b) False True TNR -PSim<PSim(a,b) 次のスライドから，提案手法（フローチャート）で用いるTR，TNRを求める実験について，説明していきます． False Goal： ソースコード流用なし Goal： 判断が困難 知能ソフトウェア工学研究会

37 流用の判断方法 メトリクスの値＞TR ：流用あり メトリクスの値＜ TNR ：流用なし 90未満のクローンの 80%は流用を含まない
170を超えるクローンの 90%は流用を含む 知能ソフトウェア工学研究会

38 独立に開発された，異なるソフトウェア間で
クローンと流用の関係 クローンの発生理由 コピーアンドペースト 流用の発生理由 開発期間の短縮，など ，偶然の一致，定型処理など 独立に開発された，異なるソフトウェア間で クローンが検出されると流用の疑いあり クローンと流用の関係について整理します． クローンの発生理由には，コピアンドペースト，偶然の一致などがあります． 流用の発生理由は，開発期間の短縮， 流用の発生にはコピーアンドペーストが行われている可能性が高い． そのため，独立に開発された異なるソフトウェア間でクローンが 検出されると流用の疑いがあります． つまり，ソフトウェア間で検出されるクローンは流用の根拠として 期待できると考えられます． 次のスライドから，流用の検出に役立つと期待する クローンメトリクスについて説明していきます． ソフトウェア間で検出されるクローンは 流用の根拠として期待できる 知能ソフトウェア工学研究会

39 流用の判断方法 メトリクス値が一定値以上ならば流用と判断する 知能ソフトウェア工学研究会 本発表で提案する流用検出手法は，
クローンメトリクスがある一定値以上を 知能ソフトウェア工学研究会

40 実験（閾値の導出）：考察 目的 手順 最大クローン長と部分類似度の2つのメトリクスを用いた場合に，検出の割合が向上するかを確認する
最大クローン長を用いて検出できない30件の流用を， 部分類似度を用いて検出する 流用あり正解集合の何割が検出できたかを確認する 最大クローン長と，部分類似度のふたつのメトリクスを用いて 流用検出を行った場合に， 手順は，まず最大クローン長を用いて流用を検出し， 次に，最大クローン長で検出出来ない流用を部分類似度 を用いて検出します． その結果，何割の流用が検出出来たかを算出します． 知能ソフトウェア工学研究会

41 追実験の結果 結果 検出できなかった流用 作成した流用あり正解集合121件のうち，
最大クローン長で検出できなかった30件の流用のうち， 11件を流用として検出できた 検出できなかった流用 ソースコード規模と最大クローン長の差が大きい組 作成した流用あり正解集合121件のうち， 102件（約84%）をfalse-positiveなしで検出できた 2つのメトリクスを用いて流用検出を行った場合， 一つのメトリクスで検出出来ない流用を11件ほど検出できました． 具体的には，作成した流用ありの正解集合121件中， 102件（約84%）をfalse-positiveなしで検出出来ました． また，2つのメトリクスを用いて検出出来なかった流用は， ソースコード規模が大きいにもかかわらず， 最大クローン長が短い為，両メトリクスの閾値を下回りまったものです． そのため，ソースコード規模に影響されないクローンメトリクスを 用いる必要があると考えられます． ソースコード規模に影響されない クローンメトリクスを用いる（例：クローンの検出数） 知能ソフトウェア工学研究会

42 Renamed Cloneの検出方法 トークン解析 プログラム言語の字句規則に従いトークンに分割する
トークン変換 変数(p)，定数(i)，型(t) 種類毎にトークンを置換する マッチング 一致する部分列をクローンとする int func_add3 ( int x ) { int sub ; sub = x - 4 ; printf ( “hoge” ) ; char ch ; int add ; add = x + 3 ; return sub ; クローンは検出手法によって，検出手順は異なりますが， 本発表ではトークンベースの手法を用いたので， トークンベースの手法について簡単に説明します． 次に，本発表で着目したクローンメトリクスについて説明していきます． 知能ソフトウェア工学研究会

43 適合率1のとき，最も高い再現率をとる メトリクスの値を閾値TR とする
実験（閾値の導出）：手順 適合率と再現率から閾値を導出する 　-　メトリクスの値＞TR ：流用あり 5．そして最後に，閾値を導出します． 閾値は，適合率1の範囲はこの赤の斜線部分になり， この例では，230のメトリクスの値が閾値になります． 適合率1のとき，最も高い再現率をとる メトリクスの値を閾値TR とする 知能ソフトウェア工学研究会

44 流用検出のためのクローンメトリクス(2) 部分類似度
定義 最大クローンを含むファイルにのみ着目した類似度 ファイルの長さ 2つめのメトリクスの「ソフトウェア間の部分類似度」について説明します． この類似度は，2つのソフトウェア間で「最大クローン」を含むファイル間の 類似度です． 算出方法は，ファイルの長さを足し合わせた値で， 最大クローン長を2倍した値を割ったモノです． メトリクスの特徴としては、ファイル全体が類似していなくとも 部分的な流用が存在すると類似度は高くなるというものです。 これら2つのメトリクスを用いた，流用の判断方法について 次のスライドから説明していきます． 最大クローン長 最大クローン 特徴 ファイル全体を流用していなくとも， 部分的な流用が存在すると部分類似度は大きくなる ファイルA ファイルB 知能ソフトウェア工学研究会

45 関連研究 コードクローンを用いた手法：JPlag[4] Jplagの問題点 ソースコード間におけるクローンの含有率を用いる
ソースコードの一部分だけを利用する流用を， 流用ありと判断することが難しい クローン ファイル群 A ファイル群 B [4]： L. Prechelt, G. Malpohl, and M.Philippsen, “Finding Plagiarisms among a Set of Programs with JPlag,” J.Universal Computer Science, vol.8, no.11, pp , Nov 知能ソフトウェア工学研究会

46 閾値の決定方法 閾値を超えるクローンは必ず流用と判断できる （false-positiveなし） 適合率 再現率
適合率，再現率を用いて閾値を導出 適合率 検出結果中に含まれる正検出の割合を示す指標 再現率 正解集合のうち，どの程度正検出できたかを示す指標 閾値を用いる場合，閾値を超えるクローンは必ず流用と判断できる必要 （false-positiveなし）の必要があります． これは，流用のないケースを流用ありと判断しない為です． そこで，閾値を導出する為に，適合率と再現率を用いることを考えました． 適合率とは，検出結果中に含まれる正検出数の割合のことで， 適合率が高いほど，流用が含まれていることになります． 再現率とは，正しい結果がどれだけ拾えているかを表す指標です． 特に，適合率が１ということは，検出結果すべてに流用があることを 示す為，適合率1をとるクローンメトリクスの値を閾値に用います． そのとき，多くの流用を検出する為に再現率が最も高い値をしようします． この適合率と再現率を用いて，実験的に，流用の閾値を導出します． (適合率) = 1 かつ 再現率が最大値となる 各メトリクス値を閾値とする 知能ソフトウェア工学研究会