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

Slides:



Advertisements
Similar presentations
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 保守支援を目的とした コードクローン情報検索ツール.
Advertisements

XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
TF-IDF法とLSHアルゴリズムを用いた 関数単位のコードクローン検出法
AGMアルゴリズムを用いた ギャップを含むコードクローン情報の生成
Object Group ANalizer Graduate School of Information Science and Technology, Osaka University OGAN visualizes representative interactions between a pair.
コードクローンの長さに基づく プログラム盗用確率の実験的算出
研究の背景 コードクローン ソースコード中に存在する一致または類似したコード片
リファクタリングのための 変更波及解析を利用した テスト支援ツールの提案
川口真司 松下誠 井上克郎 大阪大学大学院情報科学研究科
プログラム実行履歴を用いたトランザクションファンクション抽出手法
プログラム実行時情報を用いたトランザクションファンクション抽出手法
大規模ソースコード集合を対象とした 類似関数集合群の抽出
ソースコードの変更履歴における メトリクス値の変化を用いた ソフトウェアの特性分析
ギャップを含むコードクローンの フィルタリング手法の提案
類似するコーディングパターンの 利用状況調査ツールの提案
Javaクラスの利用関係を用いた ソフトウェア部品のカテゴリ階層構築法
ソースコードの同時修正支援における関数クローン検出ツールの有効性調査
コードクローンに含まれるメソッド呼び出しの 変更度合の分析
コードクローンに含まれるメソッド呼び出しの 変更度合の調査
識別子の命名支援を目的とした動詞-目的語関係の辞書構築
識別子の共起関係に基づく類似コード検索法の提案と 欠陥検出への適用
ソードコードの編集に基づいた コードクローンの分類とその分析システム
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
クローンセットに対する主要編集者の分析法の提案と調査
重複コードと非重複コードにおける 修正頻度の比較
実行時情報に基づく OSカーネルのコンフィグ最小化
限られた保存領域を使用する Javaプログラムの実行トレース記録手法の 提案と評価
コードクローン検出ツールを用いた ソースコード分析システムの試作と プログラミング演習への適用
リファクタリング支援のための コードクローンに含まれる識別子の対応関係分析
ソースコードの特徴量を用いた機械学習による メソッド抽出リファクタリング推薦手法
オープンソース開発支援のための リビジョン情報と電子メールの検索システム
コードクローンの動作を比較するためのコードクローン周辺コードの解析
コードクローンに対する一貫性のない変更に起因する欠陥の検出
Token Comparison Approach to Detect Code Clone-related Bugs
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
プログラム理解におけるThin sliceの 統計的調査による有用性評価
バイトコードを単位とするJavaスライスシステムの試作
コードクローン編集者数に着目した開発履歴の分析
コードクローンのメトリクス値と 開発者の相関の調査
多様なプログラミング言語に対応可能な コードクローン検出ツール CCFinderSW
○ 後藤 祥1,吉田 則裕2 ,井岡 正和1 ,井上 克郎1 1大阪大学 2奈良先端科学技術大学院大学
ソフトウェア保守のための コードクローン情報検索ツール
コードクローンの理解支援を目的としたコードクローン周辺コードの解析
コードクローン分類の詳細化に基づく 集約パターンの提案と評価
コーディングパターンの あいまい検索の提案と実装
JAVAバイトコードにおける データ依存解析手法の提案と実装
JavaScriptを含んだHTML文書に対する データフロー解析を用いた構文検証手法の提案
コードクローン間の依存関係に基づく リファクタリング支援環境の実装
コードクローンの分布情報を用いた特徴抽出手法の提案
オブジェクトの協調動作を用いた オブジェクト指向プログラム実行履歴分割手法
プログラムスライスを用いた凝集度メトリクスに基づく 類似メソッド集約候補の順位付け手法
設計情報の再利用を目的とした UML図の自動推薦ツール
保守請負時を対象とした 労力見積のためのメトリクスの提案
コードクローン間の依存関係に基づく リファクタリング支援手法の提案と実現
アスペクト指向言語のための視点に応じた編集を可能にするツール
プログラムの差分記述を 容易に行うための レイヤー機構付きIDEの提案
クローン検出ツールを用いた ソフトウェアシステムの類似度調査
オープンソースソフトウェアに対する コーディングパターン分析の適用
メソッドの同時更新履歴を用いたクラスの機能別分類法
クラスタリングを用いた ベイズ学習モデルを動的に更新する ソフトウェア障害検知手法
欠陥検出を目的とした類似コード検索法 吉田則裕,石尾隆,松下誠,井上克郎 大阪大学 大学院情報科学研究科
ソフトウェア理解支援を目的とした 辞書の作成法
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
コードクローン解析に基づく デザインパターン適用候補の検出手法
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
メソッド抽出リファクタリングが 行われるメソッドの特徴調査
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
ベイジアンネットワークと クラスタリング手法を用いたWeb障害検知システムの開発
Presentation transcript:

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

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

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

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

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

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

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

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 = ; 知能ソフトウェア工学研究会

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 = ; 知能ソフトウェア工学研究会

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 = ; 知能ソフトウェア工学研究会

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

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

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

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

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

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

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

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

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

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

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

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なしで検出できた 知能ソフトウェア工学研究会

メトリクスを併用して検出できた流用 最大クローン長 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 知能ソフトウェア工学研究会

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

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

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

関連研究 コードクローンを用いた手法: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.1016-1038, Nov. 2002. 知能ソフトウェア工学研究会

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

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

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

ソースコード流用による損害賠償 CAおよび1999年にCAが買収した米PLATINUM technology Internationalで勤務経験のあるプログラマや ソフトウエア開発者を雇用して盗用を行う 賠償内容) 約2億ドルの損害賠償および恒久的差し止めを求める(継続中) Mark ZuckerbergがConnectUの知的財産権およびコードを盗んでこの巨大人気ソーシャルネットワークを構築 賠償内容) 約6500万ドルの損害賠償を受け取る CA,DB管理ソフトのソースコード盗用などでRocket Softwareを提訴 http://itpro.nikkeibp.co.jp/article/NEWS/20070803/278991/ CAに提訴されたIBM DB2用ツール作成のRocket,「時効」の主張通らず http://itpro.nikkeibp.co.jp/article/NEWS/20080922/315197/ The AP Reveals Details of Facebook/ConnectU Settlement With Greatest Hack Ever http://www.techcrunch.com/2009/02/11/the-ap-reveals-details-of-facebookconnectu-settlement-with-best-hack-ever/ 法律事務所の大ポカでFacebookのConnectUへの支払額が明らかに:$65M http://jp.techcrunch.com/archives/20090210law-firm-blunder-reveals-value-of-facebookconnectu-settlement-65-million/ 知能ソフトウェア工学研究会

検出できなかった流用 最大クローン長 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 知能ソフトウェア工学研究会

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

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

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

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

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

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

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

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

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

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 ; クローンは検出手法によって,検出手順は異なりますが, 本発表ではトークンベースの手法を用いたので, トークンベースの手法について簡単に説明します. 次に,本発表で着目したクローンメトリクスについて説明していきます. 知能ソフトウェア工学研究会

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

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

関連研究 コードクローンを用いた手法: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.1016-1038, Nov. 2002. 知能ソフトウェア工学研究会

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