ソフトウェア変更間の関連抽出の ための差分集合構築手法

Presentation on theme: "ソフトウェア変更間の関連抽出の ための差分集合構築手法"— Presentation transcript:

1 ソフトウェア変更間の関連抽出の ための差分集合構築手法
今枝 誉明，市井 誠，早瀬 康裕，松下 誠，井上 克郎 大阪大学 大学院情報科学研究科 2007/02/02 2 月 ソフトウェアサイエンス研究会

2 背景 ソフトウェア開発・保守コストの増大 ソフトウェアを効率よく開発・管理したい ⇒ 版管理システムなどの活用
大規模化・複雑化・使用環境の変化 ソフトウェアを効率よく開発・管理したい ⇒ 版管理システムなどの活用 過去の開発情報を参考にすることで，開発・保守を 効率化 開発者が必要とする情報を的確に取得するのは困難 蓄積された情報は膨大 研究の背景としまして ～増大しています 2007/02/02 2 月 ソフトウェアサイエンス研究会

3 概要 版管理システムに蓄積された変更記録の間の関連を抽出する 発表構成 変更箇所に現れる単語に基づき，変更をグループ化する 版管理システム
問題点と本研究の目的 提案手法 適用事例 まとめと今後の課題 本研究では，～を目的として，～ための手法を提案します 2007/02/02 2 月 ソフトウェアサイエンス研究会

4 版管理システム (1/2) ソフトウェアを構成するファイル群に対して施された変更を記録するシステム 版管理システムを用いる利点
変更の記録はリポジトリと呼ばれるデータベースに蓄積される 版管理システムを用いる利点 誤った変更・削除を行っても，戻すことが出来る 他の開発者の行った変更を参照することが出来る そして開発者は，リポジトリにアクセスし，開発を進めていきます 2007/02/02 2 月 ソフトウェアサイエンス研究会

5 版管理システム (2/2) 版管理システムの特徴 リビジョン: 変更したファイルをコミットすることでリポジトリに作成される，ファイルの状態
チェック アウト C B A A B C 変更 せず A' B' 変更 変更 コミット 「～の欠陥を 修正した」 C B’ A’ リポジトリ 版管理システムの特徴 リビジョン: 変更したファイルをコミットすることでリポジトリに作成される，ファイルの状態 リビジョンには連続した番号 (リビジョン番号) が割り振られる コミットトランザクション: 一度にコミットされた，複数のファイルに対する変更 コミットログ: コミット時に付記出来る，変更理由等を記述した文章 ファイルの過去の状態はリビジョン番号により特定が可能になっています 2007/02/02 2 月 ソフトウェアサイエンス研究会

6 変更記録を参考にする際の問題点 ⇒ 変更を個別に見るだけでは誤解が生じうる 過去の変更を参考にする ↓
例) 「あの時の欠陥修正ではどのような変更を施したのだろう?」 ↓ 同時に参照すべき変更が存在することがある その変更の影響で，他の箇所が変更されていた その変更で欠陥を混入させてしまい，後に修正を行っていた ⇒ 変更を個別に見るだけでは誤解が生じうる 関連する変更を把握する必要がある 2007/02/02 2 月 ソフトウェアサイエンス研究会

7 目的と方針 関連する変更を抽出する ↑ 蓄積された変更を何らかの方法でグループ化する ある変更と同時にどんな変更がなされているか
ある変更が後に何処に影響を与えているか ↑ 蓄積された変更を何らかの方法でグループ化する コミットログや変更箇所中に出てくる単語に着目 本研究は，～を目的とするものです 変更作業を特徴付けて いるのでは? 識別子， コメント文等 変更理由等 2007/02/02 2 月 ソフトウェアサイエンス研究会

8 提案手法の概要と流れ 変更を，単語に着目してクラスタリングする 版管理システムのリポジトリから，コミットトランザクションを取り出す
版管理システムとして CVS† を対象とする 版管理システムのリポジトリから，コミットトランザクションを取り出す 潜在的意味解析手法 (LSA) によりトランザクション間の類似度を算出し，クラスタリングする † B. Berliner. "CVS II: Parallelizing Software Development". In Proc. of the USENIX Winter 1990 Tech. Conf. 2007/02/02 2 月 ソフトウェアサイエンス研究会

9 手順 1 コミットトランザクションの取り出し -if (0 <= value) {
トランザクション抽出 直前のリビジョンから削除された行 -if (0 <= value) { +if (0 <= value && value < 10) { …… 直前のリビジョンから追加された行 リポジトリ 変更情報 ・ ファイルのパス名 ・ リビジョン番号 ・ コミットした開発者 ・ コミットされた日時 ・ コミットログ ・ 変更内容 トランザクション (同時にコミット された変更群) の集合 2007/02/02 2 月 ソフトウェアサイエンス研究会

10 手順 2 トランザクションのクラスタリング LSA を用いて，トランザクション間の類似度を計算 クラスタリング (階層的クラスタリング手法)
トランザクションの集合 クラスタの集合 LSA を用いて，トランザクション間の類似度を計算 クラスタリング (階層的クラスタリング手法) クラスタ集合の中から，類似度が最大となるクラスタの組 C，D を求める C，D の類似度がある閾値以下ならば，クラスタリング終了 クラスタ C，D を統合し 1 つのクラスタとし，繰り返す LSA とは，文書群を行列にモデル化し，行列の操作を行うことで，文書間の類似度を測る手法です 詳しくは後述いたします 2007/02/02 2 月 ソフトウェアサイエンス研究会

11 潜在的意味解析 (LSA) LSA: Latent Semantic Analysis LSA の手順 本手法においては，
文書: トランザクション 単語: コミットログと変更内容 (差分) 中に出現する単語 LSA: Latent Semantic Analysis ベクトル空間モデルに基づく情報検索アルゴリズムの一種 LSA の手順 文書群をモデル化: 文書を，単語の出現回数を要素とするベクトルとして表現し，単語文書行列を作成する 行列操作: 特異値分解を用いてランクの削減を行う 文書 1 2 1 3 -0.3 0.4 2.1 3.2 0.2 0.6 1.6 2.2 0.7 0.5 2.8 2.5 -0.1 ベクトル (文書ベクトル) 間の cosine 尺度により， 文書間の類似度を求める 単語ベースであることの利点: 構文解析しなくていい，複数言語が混じっても問題ない LSA 適用 文書 2 文書 3 文書 4 単語 A 単語 B 単語 C 単語 D 2007/02/02 2 月 ソフトウェアサイエンス研究会

12 LSA の効果 文書間の類似度がより鮮明になる 間接的に関連している文書間の類似度も高くなる 文書間の類似度の変化 1.00 0.85
文書 文書 文書 文書 4 文書 文書 文書 文書 4 文書 1 1.00 0.85 0.50 0.00 0.43 0.27 0.63 文書 1 1.00 0.98 0.66 -0.00 0.80 0.19 0.74 文書 2 文書 2 文書 3 文書 3 文書 4 文書 4 LSA 適用前 LSA 適用後 2007/02/02 2 月 ソフトウェアサイエンス研究会

13 適用事例 本手法により関連のある変更群が抽出できるかを確認する
適用対象: ソフトウェア部品検索システム SPARS-J† のソースコードの変更履歴 開発期間 2003/03/03 – 2006/01/08 開発言語 C/C++ 総リビジョン数 2795 総トランザクション数 834 総ファイル数 345 528 クラスタは初期状態のまま (単一トランザクションのみ) † 横森，梅森，西，山本，松下，楠本，井上．”Java ソフトウェア部品検索システム SPARS-J”．電子通信情報学会論文誌 D-I, Vol.J87-D-I, No.12, 2004 2007/02/02 2 月 ソフトウェアサイエンス研究会

14 評価方針 クラスタ内に複数のトランザクションを含むもののみを評価対象とする
クラスタを，含まれるトランザクション間の関連により，以下のように分類 変更と欠陥修正 共通の目的 変更とリファクタリング 変更の影響が波及 その他 仕様変更，変更を戻した等 無関係 クラスタ内のトランザクションを同時に参照することが望ましいと考え，有用であると判断 「トランザクション間の関連」 含まれるトランザクション間に関連が *あれば* 良い (余計なのが混じっててもよしとする) 有用でないと判断 2007/02/02 2 月 ソフトウェアサイエンス研究会

15 適用結果 クラスタリング終了のための類似度閾値: 0.8 ⇒ 複数トランザクションからなるクラスタ数: 116
(クラスタ中の平均トランザクション数: 2.62) 計算時間: 約 11 分半 ● 欠陥の修正 33 (28.4%) 共通の目的 14 (12.1%) リファクタリング 10 (8.6%) 影響波及 2 (1.7%) その他 無関係 24 (20.7%) 計 116 (100%) 計 59 クラスタ (50.9%): 有用なクラスタを抽出できた ● 38a のクラスタ内の平均トランザクション数: 2.62 38d のそれ: 2.47 分類結果 2007/02/02 2 月 ソフトウェアサイエンス研究会

16 「欠陥の修正」分類のクラスタの一例 3 つのトランザクション からなるクラスタ (抜粋) 比較関数の欠陥修正に 関連のある変更集合を
データベース操作時に必 　　要な比較関数の定義 1. 変数 ai は u_int8_t 　　* 型と宣言 2. キャストを行うよう修正 3. キャストが間違っていたた 　　め更に修正 SPARS/src/DB/db_common.c (2004/08/25) +u_int8_t *ai; +ai = a->data + a->size – 1; 変更 … (省略) … SPARS/src/DB/db_common.c (2004/12/14) -ai = a->data + a->size – 1; +ai = (u_int8_t)a->data + a->size – 1; 比較関数の欠陥修正に 関連のある変更集合を 抽出できた SPARS/src/DB/db_common.c (2004/12/14) -ai = (u_int8_t)a->data + a->size – 1; +ai = (u_int8_t *)a->data + a->size – 1; 2007/02/02 2 月 ソフトウェアサイエンス研究会

17 「影響波及」分類のクラスタの一例 3 つのトランザク ションからなる クラスタ (抜粋) 先の変更が， その後の変更に 影響している例を
1. 関数定義の変更 2. それに伴う関数 プロトタイプ宣言 の変更 SPARS/src/DB/db_unresolved.c (2004/01/29) -void del_unresolvedrepository(char *keyname) { +void del_unresolvedrepository(char *key, CID_t id, char* name) { … (省略) … SPARS/src/DB/spars_global.h (2004/02/19) -void del_unresolvedrepository(char *keyname); +void del_unresolvedrepository(char *key, CID_t id, char* name); 先の変更が， その後の変更に 影響している例を 抽出できた SPARS/src/DB/db_unresolved.c (2003/05/10) … (省略) … 2007/02/02 2 月 ソフトウェアサイエンス研究会

18 特徴的な単語を抽出・クラスタをフィルタリングする必要がある
考察 関連のある変更群を含むクラスタを生成できた 主として，変更内容の似ているトランザクションがクラスタを形成していた そうでないクラスタも多数生成されてしまった 例) 個別のオプション追加 (usage，getopt 等が頻出) 共に単語に基づく手法であることに起因 特徴的な単語を抽出・クラスタをフィルタリングする必要がある version/root/keyword/memory/leak 2007/02/02 2 月 ソフトウェアサイエンス研究会

19 まとめと今後の課題 版管理システム中に蓄積された，関連する変更の集合を構築する手法を提案 実際のソフトウェアに対して適用 今後の課題
変更内容に出現する単語に着目 実際のソフトウェアに対して適用 単語に基づく手法の有効性・問題点を確認 今後の課題 単語の抽出・除去手法の確立 閾値決定方法の確立 定量的な評価 2007/02/02 2 月 ソフトウェアサイエンス研究会

20 終わり 2007/02/02 2 月 ソフトウェアサイエンス研究会

21 関連研究 変更履歴閲覧システム プログラム要素間の関連抽出システム
ViewVC [1]: Web ブラウザ上で，ファイルの各リビジョンの内容を表示する機能を持つ CREBASS [2]: リビジョン関係を考慮した関数クロスリファレンス機能を持つ プログラム要素間の関連抽出システム Zimmermann ら [3]: ソースコードの変更ルールの抽出を行い，変更点の予測や不完全な変更の検出を行う Gerardo ら [4]: 版管理システムと欠陥追跡システム内の情報を結び付け，ある変更要求に対して変更が必要となるファイルを特定する しかしこれらの研究では，関連する変更を利用者自身が探さねばならなかったり， また抽出されるものが，ファイルなどのプログラム要素間の関連であったりするため， 変更間の関連は分かりません． [1] [2] 中山，松下，井上．”関数の変更履歴と呼出し関係に基づいた開発履歴理解支援システム”．電子情報通信学会技術研究報告 Vol.104, No.47, 2004． [3] T. Zimmermann, P. Weissgerber, S. Diehl, and A. Zeller. “Mining Version Histories to Guide Software Changes”. ICSE’04. [4] G. Canfora and L. Cerulo. “Impact Analysis by Mining Software and Change Request Repositories”. METRICS’05. 2007/02/02 2 月 ソフトウェアサイエンス研究会

22 手順 1.1 変更情報の取り出し 変更情報 ・ ファイルのパス名 ・ リビジョン番号※ ・ コミットした開発者 ・ コミットされた日時
・ コミットログ ・ 変更内容 (差分) ※ 直前のリビジョンから 該当リビジョンへの変更 と考える CVS リポジトリ 各ファイルごとの 変更記録 2007/02/02 2 月 ソフトウェアサイエンス研究会

23 1 回のコミット作業によりリポジトリに登録された変更群
手順 1.2 コミットトランザクションの復元 トランザクションの 復元 変更情報の集合 コミットトランザクション ∥ 1 回のコミット作業によりリポジトリに登録された変更群 ※ 以下 3 つの条件を全て満たす 変更集合をコミットトランザクションと する† ・ コミットした開発者が同じ ・ コミットログが同じ ・ コミット日時の差が 200 秒以内 † T. Zimmermann and P. Weissgerber. “Preprocessing CVS Data for Fine-Grained Analysis”. MSR 2004. 2007/02/02 2 月 ソフトウェアサイエンス研究会

24 手順 2 (補足) 単語抽出の 2 種類の方法 以下の C(Da,w)，C(Dd,w) を定義 差分中に出現する単語を全て数える
C(Da, w): 単語 w が差分 D の全追加箇所に出現した回数 C(Dd, w): w が D の全削除箇所に出現した回数 差分中に出現する単語を全て数える D 中の w の出現数 c = C(Da, w) + C(Dd, w) 同じ単語が削除と追加で同じだけ出現したら相殺 D 中の w の出現数 c = | C(Da, w) – C(Dd, w) | ↓ トランザクション T 中の単語 w の出現数は，T に含まれる全ての差分中の w の出現数 c にログ中の ｗ の出現数を足し合わせたもの 適用の際，上記 1，2 それぞれの方法で試行した 2007/02/02 2 月 ソフトウェアサイエンス研究会

25 分類「その他」 仕様変更 マージ 変更を戻した HTML，CSS 等による見栄えの変更 ライセンス文字列の書き換え テストケース
2007/02/02 2 月 ソフトウェアサイエンス研究会

26 「共通の目的」分類のクラスタの一例 削除行・追加行における各単語の出現数の差をとる方法
2 つのトランザクション からなるクラスタ 1. データベースの項目にファ イルの mtime (更新時間) を新たに登録するよう変更 2. データベースからファイルの 更新時間も併せて取得する よう変更 SPARS/src/DB/spars_db.h (2003/04/15) +time_t mtime; SPARS/src/Register/regist.c (2003/04/15) -void regist(char *path) { +void regist(char *path, time_t mtime) { …(中略)… -put_fileinforepository(id, description); +put_fileinforepository(id, mtime, description); … (省略) … SPARS/src/Search/perform_search.c (2003/04/15) -get_fileinforepository(ci->file_id, &(ci->fileinfo)); +get_fileinforepository(ci->file_id, &(ci->mtime), &(ci->fileinfo)); … (省略) … 2007/02/02 2 月 ソフトウェアサイエンス研究会