ソフトウェアの類似性の分析とその応用に関する研究 大学院情報科学研究科 コンピュータサイエンス専攻 井上研究室 川口真司 2005/12/21

ソフトウェアリポジトリ インターネット ネットワーク上の開発基盤サービス ソースコードや ドキュメントなどの 管理を行う 開発中に発見した バグの管理を行う ネットワーク上の開発基盤サービス 大量のソフトウェア (SourceForge: 約 10 万 プロジェクト) 版管理システム バグ追跡システム ソフトウェアリポジトリ 一般ユーザ 開発者 近年、ネットワーク上で開発基盤環境を提供するソフトウェアリポジトリが急速に普及しています。 ソフトウェアリポジトは、ネットワークを通じてソースコードなどを管理する版管理システムをはじめ、バグ管理システムや掲示板、メーリングリスト管理システムなどのサービスを提供します。 たとえば、オープンソース開発における最大のソフトウェアリポジトリである SourceForge では約10万プロジェクトに対してサービスを提供しています。 また、その有用性から、社内プロジェクトの管理のために社内用ソフトウェアリポジトリを導入する企業も増えています。 掲示板 ML管理システム インターネット ユーザの要望等を 受け付ける 開発者間で行われた 議論を保存 2005/12/21

ソフトウェアの持つ類似性 膨大な数の成果物 成果物がもつ類似性とその活用 これまでに作成された大量のソフトウェア 大規模なソフトウェアに含まれる大量のコンポーネント、ソースコード 成果物がもつ類似性とその活用 類似の定義、発見 類似の応用 ソフトウェア 付属ドキュメントを用いて ソースコードを用いて ソフトウェアライブラリ 派生ソフトウェアの分類 コンポーネント 継承関係、利用関係、ソースコード等を用いて コンポーネントライブラリ ソフトウェアクラスタリング コード片 コードクローンに関する研究 クローン削除作業の支援、リファクタリング 2005/12/21

ソフトウェアの類似性 GURU (Maarek ら [46]) Ugurel らの手法 [62] SMMT (山本ら [64]) Unix の各コマンドを、man を利用して分類 IR メソッドを利用 Ugurel らの手法 [62] ソフトウェアに付随するドキュメントを利用して分類 support vector machine (SVM) を利用 SMMT (山本ら [64]) ソースコードそのものを直接用いて分類 CCFinder を利用 ソフトウェアライブラリの構築 [46, 62] 派生ソフトウェア群の分類 [64] 4.4BSD Lite から派生した、FreeBSD, NetBSD, OpenBSD の各バージョン間の類似度を比較 2005/12/21

コンポーネントの類似性 継承関係から (Spanoudakis ら *) 利用関係から (SPARS **) コンポーネントのソースコードに機械学習手法を適用 LSA(潜在的意味解析手法) を用いて (Maletic ら [47]) 自己組織化マップを用いて (Chan ら [15]) コンポーネントライブラリの構築 (SPARS **) ソフトウェアクラスタリング [47] ひとつのソフトウェアを、いくつかのコンポーネント群に分割 * Giorgos Spanoudakis, Panos Constantopoulos, Measuring Similarity Between Software Artifacts 1994, Proc. of the 6th International Conference on Software Engineering and Knowledge Engineering - SEKE '94, Jurmala, Latvia, June 1994. ** Katsuro Inoue, Reishi Yokomori, Tetsuo Yamamoto, Makoto Matsushita, Shinji Kusumoto, “Ranking Significance of Software Components Based on Use Relations”, IEEE Transactions on Software Engineering, Vol.31, No.3, pp.213-225 (2005) 2005/12/21

コード片の類似性 コードクローン クローン削除作業の支援 字句解析ベース [5, 6, 7, 11, 20, 33, 39, 40, 43, 53, 55] CCFinder (神谷ら [33] ) CloneDr (Baxter ら [11] ) メトリクスベース [8, 9, 10, 32, 49, 51] メソッド単位でメトリクスを定義 (Balazinskaら [8, 9, 10]) クローン削除作業の支援 コードクローンは保守工程における重大な障害のひとつ ある部分に修正が必要 → その部分のクローン全ての修正を検討 コードクローン分析環境 Gemini (植田ら *) リファクタリング支援 (肥後ら **) * 植田 泰士, 神谷 年洋, 楠本 真二, 井上 克郎, "開発保守支援を目指したコードクローン分析環境", 電子情報通信学会論文誌 D-I, Vol. J86-D-I, No. 12, pp. 863-871 (2003-12). ** 肥後 芳樹, 植田 泰士, 神谷 年洋, 楠本 真二, 井上 克郎, "コードクローン解析に基づくリファクタリングの試み", 情報処理学会論文誌, no. 45, vol. 5, pp. 1357-1366 (2004-5). 2005/12/21

ソフトウェアの持つ類似性 膨大な数の成果物 成果物がもつ類似性とその活用 これまでに作成された大量のソフトウェア 大規模なソフトウェアに含まれる大量のコンポーネント、ソースコード 成果物がもつ類似性とその活用 類似の定義、発見 類似の応用 ソフトウェア 付属ドキュメントを用いて ソースコードを用いて ソフトウェアライブラリ 派生ソフトウェアの分類 コンポーネント 継承関係、利用関係、ソースコード等を用いて コンポーネントライブラリ ソフトウェアクラスタリング コード片 コードクローンに関する研究 クローン削除作業の支援、リファクタリング 2005/12/21

論文の構成 第1章: まえがき 第2章: MUDABlue: ソフトウェアシステム自動分類手法 [1-1, 1-2, 1-3, 1-4] 第3章: 版管理システムを用いたクローン履歴抽出手法 [1-5] 第4章: むすび 2005/12/21

MUDABlue: ソフトウェア自動分類システム [2章] ソフトウェアそのものの分類の重要性 大量のソフトウェア → 分類、整理が必要 ML の議論や、掲示板やバグ追跡情報も有用 既存のソフトウェアライブラリ構築手法は不十分 分類先はあらかじめ用意する必要あり 分類結果は排他的 ドキュメントに依存 2005/12/21

MUDABlue の構成 ソフトウェア自動分類部 分類結果提示ユーザインタフェース 大量のソフトウェアを自動的に分類する 潜在的意味解析手法 LSA に基づく手法 自然言語文書の類似性を計測する手法 分類結果提示ユーザインタフェース キーワード検索、ディレクトリ型検索の両方をサポート Unifiable Cluster Map 手法による描画 （下3枚は削除の方向）、問題点は前の部分で指摘することろがあるので、そこで。 MUDABlue が備える三つの特徴をババンと オリジナルの目的のスライドは手ぬるい 2005/12/21

提案手法の特徴 階層構造も自動的に作成 非排他的な分類 ソースコードのみを用いて分類 カテゴリの作成には、さまざまなライブラリ・アーキテクチャに関する深い知識が必要 日々新しいカテゴリが誕生 非排他的な分類 ソフトウェアの分類には、複数個の基準が存在 ソフトウェアの用途 利用しているライブラリ、依存アーキテクチャ、等々 ソースコードのみを用いて分類 既存手法はソフトウェアに付属するドキュメントに基づいて分類 ドキュメントの量や質（特に均一性）に大きく依存 2005/12/21

非排他的分類 regexp エディタ 表計算 MFC GTK ソフトウェア1 ソフトウェア3 エディタ 表計算 GUI (MFC) 正規表現サポート (regexp) 正規表現サポート (regexp) ソフトウェア2 ソフトウェア4 エディタ 表計算 GUI (GTK) GUI (GTK) 正規表現サポート (regexp) 2005/12/21

潜在的意味解析法 LSA Latent Semantic Analysis [41, 42] 自然言語で書かれた文書、単語の類似度を計測する ベクトル空間モデルに従った手法の一つ ベクトル空間モデルでは検出できない間接的な関連の抽出を可能にしている 2005/12/21

LSA の例 単語ベクトル 文書ベクトル 文書間、単語間の類似度は ベクトル間の角度の cos や、 相関係数によって表す 文書1 文書4 2 3 4 5 6 A B C D E F G H A B B F G G 文書2 文書5 A B C D E F G H H 単語頻度行列を 作成 文書3 文書6 B C C C D E G H LSA 1 0.3 0.7 0.9 0.4 0.2 2 1.0 1.4 0.6 0.1 3 1.5 2.3 -0.2 4 0.0 5 6 -0.1 A B C D E F G H 2005/12/21

LSA の効果 間接的に関連している文書間の類似度も高い 文書間の類似度がより鮮明になる 文書間の相関係数行列 LSA適用前 LSA適用後 1 2 3 4 5 6 1.0 0.2 -0.1 -0.3 -0.5 0.5 -0.9 -0.2 -0.4 0.3 1 2 3 4 5 6 1.0 0.9 -0.6 -0.5 -0.8 -0.7 LSA適用前 LSA適用後 2005/12/21

識別子による分類 ソースコード中の識別子は、その動作を表している window という識別子があるプログラム文の周辺は、なんらかの GUI に関する操作を行っている 識別子のうち特に類似しているものを結びつけて、それらをひとつのグループとみなして分類を行う ソフトウェア1 ソフトウェア3 エディタ 表計算 GUI (MFC) GUI (MFC) window menuBar cmdButton window MFC 2005/12/21

提案手法(1/2) Sof1 Soft4 Soft1 Soft4 Soft2 Soft5 Soft2 Soft5 Soft3 Soft6 A B B F J G G I J Soft2 Soft5 Soft2 Soft5 1.トークン 抽出 A B C D E F G H H J Soft3 Soft6 Soft3 Soft6 B C C C D E G H J 2.共起行列の作成 1 2 3 4 5 6 A B C D E F G H I J 1 2 3 4 5 6 A B C D E F G H 3.孤立トークン, 普遍トークンの 削除 2005/12/21

提案手法(2/2) 4.LSA 5.トークン間の類似度計測、 クラスタ分析 ClusterName1 7.クラスタ 6.ソフトウェア 3 4 5 6 A B C D E F G H 1 0.3 0.7 0.9 0.4 0.2 2 1.0 1.4 0.6 0.1 3 1.5 2.3 -0.2 4 0.0 5 6 -0.1 A B C D E F G H 4.LSA 5.トークン間の類似度計測、 クラスタ分析 1 2 3 1 2 3 A B C D ClusterName1 F G H 7.クラスタ タイトルの 作成 6.ソフトウェア クラスタの 作成 1 4 5 6 1 4 5 6 ClusterName2 2005/12/21

ケーススタディ 実験を通じて以下のことを示す MUDABlue システムの実際のカテゴリ描画 抽出したカテゴリの評価 テストデータ 抽出カテゴリの概要 既存手法との適合率、再現率の比較 テストデータ SourceForge から無作為に選んだ 6 つのジャンル boardgames, compilers, database, editor, videoconversion, xterm 以上の 6 ジャンルに含まれる C プログラム 41 個 計 164,102 個の識別子 孤立トークン、普遍トークンを除く 22,048 識別子を LSA の入力として利用 2005/12/21

分類結果 40 個のカテゴリ ライブラリ、アーキテクチャに関するカテゴリの内訳 SourceForge のカテゴリに合致するカテゴリ 18 GTK(2 カテゴリ) GUI ライブラリ win32(3 カテゴリ) Windows32 API yacc 構文解析ライブラリ SSL SSL 通信用ライブラリ regexp 正規表現用ライブラリ getopt コマンドラインオプション読み取り用ライブラリ JNI Java Native Interface Python/C Python インタプリタ拡張用インタフェース SourceForge のカテゴリに合致するカテゴリ 18 ライブラリ、アーキテクチャに関するカテゴリ 11 はずれのカテゴリ 2005/12/21

適合率、再現率の評価 MUDABlue は既存の研究に対して同程度の信頼性を保っている GURU Ugurel らの手法 IR メソッドを利用 Unix の各コマンドを、man を利用して分類 Ugurel らの手法 support vector machine (SVM) を利用 ソフトウェアに付随するドキュメントに対して SVM を適用 MUDABlue は既存の研究に対して同程度の信頼性を保っている We evaluated retrieved categories by precision and recall. For comparison, the result of GURU and Ugurel’s method are also plotted. These researches categorize exclusive way and uses given category set. So MUDABlue and these researches are different and this comparison is not GENNMITU, but we can say that MUDABlue has same accuracy with these researches. 2005/12/21

考察 適合率、再現率は既存研究と同程度の水準を保っている MUDABlue は前提知識の入力が必要ない 非排他的な分類の実現 今後の課題 ドキュメントに依存しない 非排他的な分類の実現 今後の課題 「その他」カテゴリを減らす 識別子を選別する部分の改善が必要 カテゴリタイトルをよりわかりやすく 分かりやすいものもあれば、分かりにくいものも ライブラリに基づくカテゴリには分かりやすいタイトルがつく傾向 カテゴリの粒度をより適正に 細粒度にすぎる傾向 2005/12/21

クローン履歴分析手法 [3章] 既存のクローン抽出手法 過去に exact にコピーされた時点の状態を見れば明白 版管理システムが持つ履歴情報 版管理システムは、これまでにおこわなわれた変更の履歴を全て保持 過去の任意の時点のプロダクトを取得可能 2005/12/21

コードクローン コードクローン（あるいは単にクローン） クローンペア クローンセット 類似文字列が存在するコード片 クローンの位置は (ファイル名、開始行番号、終了行番号) で指定 クローンペア クローンA-1 とクローンA-2 が類似文字列であるときに、これらをクローンペアとよぶ クローンセット クローンペア関係において推移関係が成り立つクローンの集合 Clone A-1 Clone A-3 Clone A-2 Clone B-2 Clone B-1 2005/12/21

履歴を考慮したクローン分析 過去にクローン関係にあったコード片の抽出 過去の時点でのクローン解析情報 現在のクローンは、過去のどのクローンに対応するか？ Clone A-3 追加 Clone A-3 Clone A-3 Clone A-1 Clone A-1 Clone A-1 Clone B-1 Clone B-1 Clone B-1 Clone A-4 Clone A-4, A-5 追加 Clone A-2 Clone A-2 Clone A-2 Clone B’-2 Clone B-5 Clone B’-2 Clone A-5 Clone B-2 Clone B-2 Clone B-2 Clone B’-1 Clone B-3 Clone B-4 Clone B’-3 Clone B’-1 Clone B’-3 Clone B-3, B-4, B-5 が編集 されて別クローンセットに Clone B’-3 削除 クローンセット B, B’ を 「分離クローンセット」と呼ぶ 2005/12/21

クローン履歴関係 （過去のコード片, 現在のコード片）のペア CCFinder によって発見されたクローンペア クローン履歴関係 ファイル1 ファイル1 挿入 Clone A Clone A Clone A クローン関係 ファイル2 ファイル2 CCFinder によって発見されたクローンペア Clone A Clone A ファイル3 削除 Clone B ファイル3 Clone B Clone B Vt-1 Vt 2005/12/21

クローン履歴関係抽出手法(1/2) 指定された期間 [0, t]、間隔Δt について期間 [0, t] を Δt ごとに分割、それぞれの時のファイルの状態をバージョン V0, V1, ..., Vt と表す 過去のプロダクトの取得には版管理システム (ex. cvs, subversion, ...) を用いる となりあうバージョン間について分析 V0, V1 をリポジトリから取得 V0, V1 間のクローン履歴関係を分析 Vt をリポジトリから取得 Vt-1, Vt 間を分析 ・・・ V0 V1 Vt-1 Vt 2005/12/21

クローン履歴関係抽出手法(2/2) 隣あうバージョン Vt-1, Vt について以下を行う クローン分析 クローン履歴関係分析 クローン分析には CCFinder を使用する クローンの行数、総行数に対する割合も計算 クローン履歴関係分析 HCt : バージョン間でクローン関係に変化のない履歴関係抽出 HAt: Vt において新規に追加されたクローンの履歴関係抽出 HTt: Vt において片方が削除されたクローンの履歴関係抽出 2005/12/21

2-1: クローン関係に変化のない履歴関係抽出 行番号 行番号 クローン 関係 ファイル1 ファイル1 7 Clone A 25 18 Clone A 31 HCt 37 クローン 履歴関係 43 Clone A ファイル2 ファイル2 HCt 22 22 Clone A 28 28 Clone A Vt の各クローンについて、Vt-1 の 「写像先」にクローンが存在す るかどうか検索 ファイル3 11 Clone B ファイル3 22 42 Clone B 48 写像先の決定には、編集操作による行番号のズレを考慮 Vt-1 Vt 2005/12/21

2-2: 追加されたクローンの履歴関係抽出 Vt-1 と 差分との間で CCFinder を適用 ファイル1 ファイル1 HAt Clone A Clone A クローン 履歴関係 Clone A HAt ファイル2 ファイル2 Clone A Clone A ファイル3 Clone B ファイル3 Clone B Vt-1 と 差分との間で CCFinder を適用 Vt-1 Vt 発見したクローンに対応する部分を履歴関係とする 2005/12/21

2-3:片方が削除されたクローン候補の抽出 Vt-1 において、対応がないクローンについて、 Vt との対応行とテキスト比較 クローン 関係 行番号 行番号 クローン 関係 ファイル1 ファイル1 Clone A Clone A クローン 履歴関係 Clone A ファイル2 ファイル2 Clone A Clone A Vt-1 において、対応がないクローンについて、 Vt との対応行とテキスト比較 ファイル3 Clone B ファイル3 Clone B Clone B HTt Vt-1 Vt 2005/12/21

提案手法の特徴 となりのバージョン同士でのつながり バージョン間の diff に対してのみクローン分析を適用 任意の二点間の分析を行うのはコストが大きい バージョン間の diff に対してのみクローン分析を適用 Vt-1, Vt 全体に対して CCFinder を適用するのはコストが大きい 各バージョンごとにクローン分析を適用 差分情報のみからクローン情報の類推を行わない 計算量を極力抑える 正確なクローン分析 2005/12/21

PostgreSQL のクローン履歴分析 分離クローンセットを漏れなく抽出できているかどうかの検証 クローン全体の履歴 PostgreSQL の src 部分を 2005/01/01 ~ 2005/06/30 の期間、一週間ごとに解析 クローンセット中のクローン数が減少している部分、時間に着目 その時間の差分を確認して、分離クローンセットか、縮退クローンセットかを目視で判定 分離クローンセットであれば、各クローンに正しくクローン履歴関係が抽出されているかどうかを検証 クローン全体の履歴 PostgreSQL の開発工程におけるクローンの増加量をグラフ化 1998年7月から2005年7月の6年分を一月区切りで解析 2005/12/21

縮退クローンセット 調査結果 全 24 クローンセットを調査 誤判定はなし 分岐クローンセット 4 本来は分岐クローンセットなのに、クローン減少と判定 クローンが削除されたクローンセット 5 価値のないクローンセット 15 全 24 クローンセットを調査 誤判定はなし 15箇所のクローンセットは、定数定義が連続している部分など無意味なクローン 2005/12/21

過去に関連のあったクローンセットの例 pgsql/src/backend/commands (SQL 文解釈・実行部の実装) pgsql/src/backend/commands/dbcommands.c 08/04 765 /* 766 * ALTER DATABASE name OWNER TO newowner 767 */ 768 void 769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 { 771 HeapTuple tuple; 772 Relation rel; ・・・ 792 /* 793 * If the new owner is the same as the existing owner, consider the 794 * command to have succeeded. This is to be consistent with other objects. 795 */ 796 if (datForm->datdba != newOwnerSysId) 797 { 798 Datum repl_val[Natts_pg_database]; 799 char repl_null[Natts_pg_database]; 800 char repl_repl[Natts_pg_database]; 801 Acl *newAcl; 802 Datum aclDatum; 803 bool isNull; 804 HeapTuple newtuple; 805 806 /* changing owner's database for someone else: must be superuser */ 807 /* note that the someone else need not have any permissions */ 808 if (!superuser()) 809 ereport(ERROR, 810 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 811 errmsg("must be superuser to change owner"))); 812 813 memset(repl_null, ' ', sizeof(repl_null)); 814 memset(repl_repl, ' ', sizeof(repl_repl)); 815 816 repl_repl[Anum_pg_database_datdba - 1] = 'r'; 817 repl_val[Anum_pg_database_datdba - 1] = Int32GetDatum(newOwnerSysId); 818 819 /* 820 * Determine the modified ACL for the new owner. This is only 821 * necessary when the ACL is non-null. 822 */ 823 aclDatum = heap_getattr(tuple, 824 Anum_pg_database_datacl, 825 RelationGetDescr(rel), pgsql/src/backend/commands/dbcommands.c 07/01 765 /* 766 * ALTER DATABASE name OWNER TO newowner 767 */ 768 void 769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 { 771 HeapTuple tuple, 772 newtuple; ・・・ 790 791 newtuple = heap_copytuple(tuple); 792 datForm = (Form_pg_database) GETSTRUCT(newtuple); 793 794 /* 795 * If the new owner is the same as the existing owner, consider the 796 * command to have succeeded. This is to be consistent with other objects. 797 */ 798 if (datForm->datdba != newOwnerSysId) 799 { 800 /* changing owner's database for someone else: must be superuser */ 801 /* note that the someone else need not have any permissions */ 802 if (!superuser()) 803 ereport(ERROR, 804 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 805 errmsg("must be superuser to change owner"))); 806 807 /* change owner */ 808 datForm->datdba = newOwnerSysId; 809 simple_heap_update(rel, &newtuple->t_self, newtuple); 810 CatalogUpdateIndexes(rel, newtuple); 811 } 812 813 systable_endscan(scan); 814 heap_close(rel, NoLock); 815 } pgsql/src/backend/commands (SQL 文解釈・実行部の実装) pgsql/src/backend/commands/aggregatecmds.c 07/01 291 /* 292 * Change aggregate owner 293 */ 294 void 295 AlterAggregateOwner(List *name, TypeName *basetype, AclId newOwnerSysId) 296 { 297 Oid basetypeOid; 298 Oid procOid; ・・・ 321 if (!HeapTupleIsValid(tup)) /* should not happen */ 322 elog(ERROR, "cache lookup failed for function %u", procOid); 323 procForm = (Form_pg_proc) GETSTRUCT(tup); 324 325 /* 326 * If the new owner is the same as the existing owner, consider the 327 * command to have succeeded. This is for dump restoration purposes. 328 */ 329 if (procForm->proowner != newOwnerSysId) 330 { 331 /* Otherwise, must be superuser to change object ownership */ 332 if (!superuser()) 333 ereport(ERROR, 334 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 335 errmsg("must be superuser to change owner"))); 336 337 /* Modify the owner --- okay to scribble on tup because it's a copy */ 338 procForm->proowner = newOwnerSysId; 339 340 simple_heap_update(rel, &tup->t_self, tup); 341 CatalogUpdateIndexes(rel, tup); 342 } 343 344 heap_close(rel, NoLock); 345 heap_freetuple(tup); 346 } aggregatecmds.c Clone A conversioncmds.c conversioncmds.c aggregatecmds.c Clone A Clone A Clone A opclasscmds.c Clone A opclasscmds.c operatorcmds.c opratorcmds.c Clone A Clone A Clone A tablecmds.c Clone B functioncmds.c functioncmds.c tablespace.c Clone A Clone A tablespace.c Clone B Clone B schemacmds.c schemacmds.c dbcommands.c Clone A dbcommands.c Clone B Clone A Clone B 2005/03/04 2005/04/01 2005/12/21

考察 分離クローンセットを漏れなく抽出できているかどうかの検証 クローン量の変遷グラフ 縮退クローンセットに的を絞って検証 過去に関係のあったクローンの例 実際に関連性が高い 手動で履歴を探索していくのは手間がかかる 分析を行うための対話的ユーザインタフェースの作成 クローン量の変遷グラフ PostgreSQL の開発工程ではクローン含有率は安定 → 良好な開発パターン ただし src/backend/command 以下では上昇傾向 →　危険な傾向 危険なパターン、良好なパターンの列挙 2005/12/21

関連研究 クローンの生存期間に着目した分析* (Kim ら) クローン履歴を利用したオリジン分析** （Godfrey ら） ある一定間隔ごとにクローン分析を行い、クローンの寿命を調査 クローンの生存期間によってクローンを分類 クローン分析にはCCFinderを用いる クローン履歴を利用したオリジン分析** （Godfrey ら） 関数が、過去のバージョンのどの関数に由来するものかを調べる 関数の統合、分割を半自動的に検出 クローン分析はメトリクスベース 対話的な分析 利用するメトリクスは分析者が決定 * M. Kim and D. Notkin: “Using a clone genealogy extractor for understanding and supporting evolution of code clones”, MSR 2005, Saint Louis, Missouri, pp. 17-21 (2005) ** M. W. Godfrey and L. Zou: “Using origin analysis to detect merging and splitting of source code entities”, IEEE Trans. Software Engineering, 31, 2, pp.166-181 (2005) 2005/12/21

むすび ソフトウェアリポジトリに存在する大量のソフトウェアから、類似性を抽出しソフトウェア開発への応用を行った ソフトウェア自動分類システム MUDABlue の構築 事前知識なしでカテゴリを自動的に抽出し、分類 SourceForge から得たソフトウェアの分類実験 クローン履歴抽出手法の提案 コードクローンの履歴を抽出する手法の提案 PostgreSQL からの履歴抽出 2005/12/21

2005/12/21

特異値分解 特異値分解は、行列の次元を削減する 高次元配列の次元削減を行うメリット b 誤差は最小二乗誤差になるようにする。 l データサイズ削減 同じ値の分布をする次元（相関の高い次元）から優先的に一つの次元に併合される b l a 2 次元データ (a, b) を 1 次元 データ (l) に削減する例 2005/12/21

行番号の調整 ft ft-1 ft ft-1 衝突時には対応行が一意でない 最小、最大の推定値両方を考慮 9 18 24 29 34 39 挿入 9 Clone A 15 15 18 18 18 削除 22 Clone A 24 22 31 29 31 衝突 34 Clone A 36 Clone A ft-1 行番号 衝突時には対応行が一意でない 最小、最大の推定値両方を考慮 2005/12/21

分析2: PostgreSQL 全体のコード量 だしてる値はパーセントじゃない・・・（パーセントのほうが直感的かも） クローン含有率は開発工程全体をとおして安定 src 以下が全体の8割を占めている 2005/12/21

分析2: PostgreSQL コア部分のコード量 2000年11月、utils 以下のクローン含有率 utils には文字コード変換用データの大量追加 commands 以下のクローン率は徐々に上昇 2005/12/21

2005/12/21

今後の研究方針 クローン以外のエンティティに対する、過去情報を考慮した類似度測定 開発進捗度を考慮したソフトウェア類似判定 過去の開発過程を考慮したコンポーネント分類 2005/12/21

ソースコードや ドキュメントなどの 管理を行う 開発中に発見した バグの管理を行う 版管理システム バグ追跡システム ソフトウェアリポジトリ 掲示板 ML管理システム ユーザの要望等を 受け付ける 開発者間で行われた 議論を保存 2005/12/21

クローン履歴の活用法 2.コード中に含まれるコード クローンの変化を分析 1.過去に同じクローンセットだった クローンセットの発見 Clone A-3 追加 Clone A-3 Clone A-3 Clone A-1 Clone A-1 Clone A-1 Clone B-1 Clone B-1 Clone B-1 Clone A-4 Clone A-4, A-5 追加 Clone A-2 Clone A-2 Clone A-2 Clone B’-2 Clone B-5 Clone B’-2 Clone A-5 Clone B-2 Clone B-2 Clone B-2 Clone B’-1 Clone B-3 Clone B-4 Clone B’-3 Clone B’-1 Clone B’-3 Clone B-3, B-4, B-5 が編集 されて別クローンセットに Clone B’-3 削除 1.過去に同じクローンセットだった クローンセットの発見 2005/12/21

クローン履歴 2. ひとつのクローンセットを クローン発生時期から分類 1.過去に同じクローンセットだった クローンセットの発見 Clone A-3 追加 Clone A-3 Clone A-3 Clone A-1 Clone A-1 Clone A-1 Clone B-1 Clone B-1 Clone B-1 Clone A-4 Clone A-4, A-5 追加 Clone A-2 Clone A-2 Clone A-2 Clone B’-2 Clone B-5 Clone B’-2 Clone A-5 Clone B-2 Clone B-2 Clone B-2 Clone B’-1 Clone B-3 Clone B-4 Clone B’-3 Clone B’-1 Clone B’-3 Clone B-3, B-4, B-5 が編集 されて別クローンセットに Clone B’-3 削除 1.過去に同じクローンセットだった クローンセットの発見 3.コード中に含まれるコード クローンの変化を分析 2005/12/21

1: クローン分析 Vt 全体を CCFinder で分析 クローン 関係 クローン 履歴関係 Vt-1 Vt Clone A ファイル1 ファイル1 Clone A Clone A クローン 履歴関係 Clone A Vt 全体を CCFinder で分析 ファイル2 ファイル2 Clone A Clone A ファイル3 Clone B ファイル3 Clone B Clone B Vt-1 Vt 2005/12/21

Step1: クローン分析 Vt 全体を CCFinder で分析 クローン 関係 クローン 履歴関係 Vt-1 Vt Clone A ファイル1 ファイル1 Clone A Clone A クローン 履歴関係 Clone A Vt 全体を CCFinder で分析 ファイル2 ファイル2 Clone A Clone A Clone B ファイル3 Clone B ファイル3 Clone B Clone B Vt-1 Vt 2005/12/21

Step2-1: 編集されていないクローンの 履歴関係抽出 行番号 行番号 クローン 関係 ファイル1 ファイル1 7 Clone A 25 18 Clone A 31 37 クローン 履歴関係 43 Clone A ファイル2 ファイル2 22 22 Clone A 28 28 Clone A 編集操作による行番号のズレを吸収 Clone B ファイル3 11 Clone B ファイル3 22 42 30 Clone B 48 36 Clone B Vt の各クローンについて、Vt-1 の対応する 行にクローンが存在するかどうか検索 Vt-1 Vt 2005/12/21

行番号の調整 ft ft-1 ft ft-1 衝突時には対応行が一意でない 最小、最大の推定値両方を考慮 9 18 24 29 34 39 挿入 9 Clone A 15 15 18 18 18 削除 22 Clone A 24 22 31 29 31 衝突 34 Clone A 36 Clone A ft-1 行番号 衝突時には対応行が一意でない 最小、最大の推定値両方を考慮 2005/12/21

Step2-2: 追加されたクローンの 履歴関係抽出 ファイル1 ファイル1 Clone A Clone A クローン 履歴関係 Clone A ファイル2 ファイル2 Clone A Clone A Clone B ファイル3 Clone B ファイル3 Clone B Clone B Vt-1 と 差分との間で CCFinder を適用 Vt-1 Vt 発見したクローンに対応する部分を履歴関係とする 2005/12/21

まとめと今後の課題 自動ソフトウェア分類システム MUDABlue の提案 事前知識なしでカテゴリを自動的に発見し、ソフトウェアをカテゴライズすることを示した 今後の課題 「その他」カテゴリを減らす 識別子を選別する部分の改善が必要 カテゴリタイトルをよりわかりやすく 分かりやすいものもあれば、分かりにくいものも ライブラリに基づくカテゴリには分かりやすいタイトルがつく傾向 カテゴリの粒度 生成カテゴリの粒度は細粒度にすぎる傾向 2005/12/21

まとめ コードクローンの履歴を抽出する手法の提案 PostgreSQL から抽出した履歴の例の提示 課題 となりのバージョンだけで分析できないクローン履歴の抽出 一度削除されてまた後で復活したクローン 活用方法の考察 分析用ユーザインタフェースの作成 2005/12/21

過去に関連のあったクローンセットの例 pgsql/src/backend/commands (SQL 文解釈・実行部の実装) pgsql/src/backend/commands/dbcommands.c 08/04 765 /* 766 * ALTER DATABASE name OWNER TO newowner 767 */ 768 void 769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 { 771 HeapTuple tuple; 772 Relation rel; ・・・ 792 /* 793 * If the new owner is the same as the existing owner, consider the 794 * command to have succeeded. This is to be consistent with other objects. 795 */ 796 if (datForm->datdba != newOwnerSysId) 797 { 798 Datum repl_val[Natts_pg_database]; 799 char repl_null[Natts_pg_database]; 800 char repl_repl[Natts_pg_database]; 801 Acl *newAcl; 802 Datum aclDatum; 803 bool isNull; 804 HeapTuple newtuple; 805 806 /* changing owner's database for someone else: must be superuser */ 807 /* note that the someone else need not have any permissions */ 808 if (!superuser()) 809 ereport(ERROR, 810 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 811 errmsg("must be superuser to change owner"))); 812 813 memset(repl_null, ' ', sizeof(repl_null)); 814 memset(repl_repl, ' ', sizeof(repl_repl)); 815 816 repl_repl[Anum_pg_database_datdba - 1] = 'r'; 817 repl_val[Anum_pg_database_datdba - 1] = Int32GetDatum(newOwnerSysId); 818 819 /* 820 * Determine the modified ACL for the new owner. This is only 821 * necessary when the ACL is non-null. 822 */ 823 aclDatum = heap_getattr(tuple, 824 Anum_pg_database_datacl, 825 RelationGetDescr(rel), pgsql/src/backend/commands/dbcommands.c 07/01 765 /* 766 * ALTER DATABASE name OWNER TO newowner 767 */ 768 void 769 AlterDatabaseOwner(const char *dbname, AclId newOwnerSysId) 770 { 771 HeapTuple tuple, 772 newtuple; ・・・ 790 791 newtuple = heap_copytuple(tuple); 792 datForm = (Form_pg_database) GETSTRUCT(newtuple); 793 794 /* 795 * If the new owner is the same as the existing owner, consider the 796 * command to have succeeded. This is to be consistent with other objects. 797 */ 798 if (datForm->datdba != newOwnerSysId) 799 { 800 /* changing owner's database for someone else: must be superuser */ 801 /* note that the someone else need not have any permissions */ 802 if (!superuser()) 803 ereport(ERROR, 804 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 805 errmsg("must be superuser to change owner"))); 806 807 /* change owner */ 808 datForm->datdba = newOwnerSysId; 809 simple_heap_update(rel, &newtuple->t_self, newtuple); 810 CatalogUpdateIndexes(rel, newtuple); 811 } 812 813 systable_endscan(scan); 814 heap_close(rel, NoLock); 815 } pgsql/src/backend/commands (SQL 文解釈・実行部の実装) pgsql/src/backend/commands/aggregatecmds.c 07/01 291 /* 292 * Change aggregate owner 293 */ 294 void 295 AlterAggregateOwner(List *name, TypeName *basetype, AclId newOwnerSysId) 296 { 297 Oid basetypeOid; 298 Oid procOid; ・・・ 321 if (!HeapTupleIsValid(tup)) /* should not happen */ 322 elog(ERROR, "cache lookup failed for function %u", procOid); 323 procForm = (Form_pg_proc) GETSTRUCT(tup); 324 325 /* 326 * If the new owner is the same as the existing owner, consider the 327 * command to have succeeded. This is for dump restoration purposes. 328 */ 329 if (procForm->proowner != newOwnerSysId) 330 { 331 /* Otherwise, must be superuser to change object ownership */ 332 if (!superuser()) 333 ereport(ERROR, 334 (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), 335 errmsg("must be superuser to change owner"))); 336 337 /* Modify the owner --- okay to scribble on tup because it's a copy */ 338 procForm->proowner = newOwnerSysId; 339 340 simple_heap_update(rel, &tup->t_self, tup); 341 CatalogUpdateIndexes(rel, tup); 342 } 343 344 heap_close(rel, NoLock); 345 heap_freetuple(tup); 346 } aggregatecmds.c Clone A conversioncmds.c conversioncmds.c aggregatecmds.c Clone A Clone A Clone A opclasscmds.c Clone A opclasscmds.c operatorcmds.c opratorcmds.c Clone A Clone A Clone A tablecmds.c Clone B functioncmds.c functioncmds.c tablespace.c Clone A Clone A tablespace.c Clone B Clone B schemacmds.c schemacmds.c dbcommands.c Clone A dbcommands.c Clone B Clone A Clone B 2004/07/01 2004/08/04 2005/12/21