移動平均分析結果

ファイルの同時変更パターンと変更
差分の分析による
論理的結合関係の自動抽出
松村知子*，横森励士**，大杉直樹*，
川口真司***，松下誠***
*奈良先端科学技術大学院大学情報科学研究科
**南山大学数理情報学部情報通信学科
***大阪大学大学院情報科学研究科
2005年6月9日ソフトウェアシンポジウム2005 於富山国際会議場
1
レガシーソフトウェアの特徴


長年にわたる保守作業（機能変更，追加，
及びフォールト修正）によって，システム構
造が複雑化する
あるコード片の変更に対して，別のコード片
も同時に変更されなければいけない，といっ
た論理的結合関係が増加している
追加モジュール
Logical Coupling*
保守作業
追加関係
*H. Gall, M. Jazayeri, J. Krajewski: ”CVS Release History Data for Detecting Logical Couplings”, Proc. 6th
International Workshop on Principals of Software Evolution (IWPSE'03) pp.13-23, Sep. 2003. Helsinki, Finland
2
増加するLogical Couplingの問題点




設計ドキュメントに明記されていないものが多
いため，時間の経過や作業者の入れ替わりに
よって，潜在化する
システムに特化している
プログラムコードの構文解析のみでは，把握
できないものがある
Logical Couplingの例


関数Ａへの変更を，Aのコピー＆ペーストである関
数Ｂにも行わなければならない
テーブルXに追加をする場合，記号定数Yの値を
修正漏れや修正間違いによる
変更しなければならない
フォールト混入の危険性が増加する
3
Logical Couplingを用いた保守支援



結合関係を持つファイルは同じ変更者に
よって同時に変更されることが多い
構成管理システムの変更履歴から，同時変
更される頻度の高いファイルの組み合わせ
を抽出する
ファイル変更パターン
抽出されたパターンを用いて，コード変更時
の修正漏れ・システム構造の複雑化を検出
する
新たな変更
ファイル変更パターンを抽出
{A,B,C,D}{P,G,F}
{X,Y,Z}
同時変更ファイル
Dの変更漏れ？
{A,B,C}
{P,G,F,X}
複雑化？
4
ファイル変更パターンによる保守支援
の特長と問題点

特長





構成管理システムの変更履歴のみから抽出
プログラミング言語に応じた構文解析が不要で，大規
模なコードサイズにも対応可能
コードの更新に応じて動的な結合関係の更新が可能
すべてのファイルを対象にできる（.ini, .properties,
画像ファイルなど）
問題点

関連ないファイルの更新が同時に行われることがあり，
更新数が少ないと，結合関係を持たないパターンが多
く抽出される(＝抽出精度が悪化する)*
*A. T. T. Ying, G. C. Murphy: ” Predicting Source Code Changes by Mining Change History ”,
IEEE transactions on Software Engineering, pp.574-586, Vol.30, No.9, Sep. 2004.
5
関連研究

抽出精度を向上させるための従来手法



ファイル変更に関連する問題報告書中の単語
情報などを利用する*
粒度を構文要素レベル(関数・メソッドなど）まで
細分化する**
ファイル変更パターンを用いることの特長を
一部相殺している


追加のデータ収集が必要
構文解析が必要
*J. S. Shirabad, T. C. Lethbridge, S. Matwin : ” Mining the Maintenance History of a Legacy
Software System”, Proc. International Conference on Software Maintenance (ICSM'03) pp.95-104,
Sep. 2003. Amsterdam, The Netherlands
**Thomas Zimmermann, Peter Weißgerber, Stephan Diehl, Andreas Zeller: ” Mining Version
Histories to Guide Software Changes ”, Proc. 26th International Conference on Software
Engineering (ICSE'04) May, 2004 Edinburgh, Scotland, United Kingdom
6
本研究の目的


構成管理システムの変更履歴と各ファイル
の変更内容（差分）を用いて，論理的結合関
係を持つファイル変更パターンを高精度で抽
出する
提案する方法の特長


論理的結合関係の抽出に必要なデータは，構成
管理システム(CVSなど)から取得可能で，デー
タ収集のための追加工数が不要である
構文解析を行わないため，プログラミング言語を
意識する必要が無い
7
提案手法の流れ
同時に行われたと考えられる更新処理
構成管理システム
(CVS)リポジトリ
同時変更数が一
定以上のファイ
ル変更パターン
の抽出
Fileα, Fileβ, Fileγ, Fileδ
Fileθ, Fileη, Fileκ, Fileλ
Fileα, Fileγ, Fileε
Fileε, Fileζ
削除語
削除語削除語
追加語
追加語追加語
パターン毎に
同時変更時
の変更内容
から単語リス
トの生成
…
Fileα, Fileβ, Fileγ, Fileδ
Fileθ, Fileη, Fileκ, Fileλ
Fileα, Fileγ, Fileε
Fileε, Fileζ
単語リストを用いて，
トランザクション毎・ト
ランザクション間の結
合関係の強さ(結合
度)を判定
結合度に基いて
有効なファイル
変更パターンの
精選
有効なファイル
変更パターン
8
提案方法の手順(1)

変更履歴データから同時変更数が一定以上
のファイル変更パターンを取り出す
構成管理
システム
Trans.
変更日付
番号
1 2000/2/26 9:28:42
2 2000/2/27 9:42:12
3 2000/2/27 11:03:35
4 2000/2/28 1:30:28
5 2000/2/28 1:36:06
6 2000/2/28 1:37:14
7 2000/2/28 1:38:07
…
同時更新
データ
作成処理*
変更者
tomoko
tomoko
noriko
kohei
noriko
tomoko
kohei
トランザクション
データ
一定回数以上の
同時更新
パターン作成**
ファイル変更
パターン
変更ファ
ファイル1
ファイル2 ファイル3
ファイル4
ファイル5
ファイル6
… ファイル
パターン
同時更
ファイル
ファイル
ファイル
ファイル
イル数
支持度
番号
新回数
数
番号1 番号2 番号3 番号4
21
0
1
2
3
4
5
1
9 0.00438
4
564
583
584
590
263
21
22
1
23
24
25
0.00438 272
4 26 119
121
125
132
4 2 270 9 271
4 131 17 273 187
194
196
5 3
8 9 0.00438
14
121
0.00438
4
17
82
194
196
2 4 274 9 204
0.00438
4
2
8
17
196
2 5 208 9 275
3
584
588
590
1 6 82 10 0.00486
7
9 0.00438
3
583
584
590
・・・・・・・
*Thomas Zimmermann, Peter Weißgerber: ”Preprocessing CVS Data for Fine-Grained Analysis”, Proc.
International Workshop on Mining Software Repositories (MSR), Edinburgh, Scotland, UK, May 2004
**Apriori Algorithm使用：R. Agrawal, R. Srikant: ”Fast algorithm for mining association rules”, Proc. 20th
Very Large Data Bases Conference(VLDB), pp.487-499. Morgan Kaufmann, 1994
9
提案方法の手順 (2)

変更内容から単語リストを生成する
Fileα
Fileβ
Fileγ
Fileδ
削除語
削除語
削除語
削除語
追加語
追加語
追加語
追加語
削除語
削除語
削除語
削除語
追加語
追加語
追加語
追加語
FileαFileβ Fileγ Fileδ
トランザクション1
1.6
1.3
1.9
トランザクション
1.7
トランザクション2
1.8
トランザクション
1.2
差分情報
1.3
1.10
1.4
差分情報
1.4 1.11 1.5
14c14
さ
< #include "BzfString.h“
--ぶ
> #include <string>
ん
70c70
< BzfString SGIImageFile::getExtension()
じ
--> std::string SGIImageFile::getExtension()
10
提案方法の手順 (3)


トランザクション毎/トランザクション間の単
語リストの似ている度合い(類似度)を計算
し，結合関係の強さ(結合度)を判定する
類似的結合関係


1トランザクション内で，同時変更ファイルに共通
する内容の変更が行われる関係
連携的結合関係

異なるトランザクション間で，共通する内容の変
更が行われる関係
11
類似的結合関係の類似度
共通単語数
全ファイルに共通する変更単語数
類似度 =
同時更新ファイル群の最小変更単語数
最小単語数
File α
File β
File γ
File δ
トランザクション１
A
E
B
F
C
D
A
E
G
B
C
F
D
A
H
E
B
D
A
B
G H
E
F
C
C
D
4
4
= 1.00
H
1
3
= 0.33
L
3
3
= 1.00
S
1
2
= 0.50
トランザクション２
I
J
K
L
I
O
S
Q
R
O
J
N
L
I
J
M
L
I
J
R
O
U
Q
R
O
P
Q
12
連携的結合関係の類似度
共通単語数
各トランザクションに共通する変更単語数
類似度 =
File α
２つのトランザクションうち少ない変更単語数
File β
File γ
File δ
最小単語数
トランザクション３
A
B
L
M
C
D
E
F
N
O
G
H
I
J
K
0
= 0.00
10
Q
P
5
6
= 0.83
……
0
= 1.00
11
トランザクション４
L
X
N
M
Y
Z
a
O
b
P
c
V
R
L
W
M
S
N
T
O
P
5
6
= 0.83
13
提案方法の手順 (4)

計算された類似度から，有効なファイル変
更パターンを精選する


類似度N%以上の組み合わせがS個以上存在
するファイル変更パターンを，有効パターンとす
る
閾値N，Sはシステムの更新数やファイル数に基
いて，決定する
14
計測事例




提案方法を用いて，ファイル変更パターンを
精選する
精選後のファイル変更パターンから，論理
的結合関係を取り出す
計測対象：3つのオープンソースシステム
計測手段



CVS(構成管理システム)からの履歴抽出：
EASEプロジェクト*で開発しているEPMツール
の一部機能を使用
差分抽出：CVSのｄｉｆｆコマンドを使用
その他の処理は専用プログラムを作成して実施
*EASE (Empirical Approach to Software Engineering) Project, http://www.empirical.jp/project/index.html 15
結果～ファイル変更パターンの精選
計測対象プロジェクトの概要
トランザク
測定対象期間
ション数
測定開始日測定終了日
2709
6249
2003/7/10 2004/9/17
1562
1083
2000/2/22 2003/11/30
1796
7877
2000/3/5 2004/11/25
プロジェクト名ファイル数
Azureus
DooMLegacy
BZFlag
ファイル変更パターンの精選結果
プロジェクト名
Azureus
DooMLegacy
BZFlag
最小同時
更新回数
総パター
ン数
14
9
14
類似度80%以上の
組み合わせが8個以上
有効パターン数
類似的
239 連携的
合計（重複なし）
類似的
268 連携的
合計（重複なし）
類似的
292 連携的
合計（重複なし）
220
1
221
31
6
37
164
85
207
16
類似的結合関係例
全ファイ bzflag/src/
ルの共通 mediafile/I
単語数
mageFile.h
1
1
トランザク追加語
ション1
削除語
1
1
トランザク追加語
2
2
ション2
削除語
1
1
トランザク追加語
1
1
Index: bzflag/src/mediafile/ImageFile.h
0
0
diff ション3
-r1.2 -r1.3 削除語
トランザク
追加語
1
1
25c25
削除語
1
1
< ション4// static
BzfString getExtension();
2
2
--- トランザク追加語
削除語
1
1
> ション5// static
std::string getExtension();
トランザク追加語
13
13
ション6
削除語
0
0
Index: bzflag/src/mediafile/SGIImageFile.h
トランザク
追加語
5
5
diff -r1.2 -r1.3
ション7
削除語
5
5
23c23
1
1
< トランザク
static 追加語
BzfString
getExtension();
--- ション8
削除語
1
1
> トランザク
static 追加語
std::string
getExtension();
1
1
ション9
削除語
1
1
トランザク
追加語
1
Index: bzflag/src/mediafile/WaveAudioFile.h 1
1
1
diff ション10
-r1.2 -r1.3 削除語
23c23
<
-->
static BzfString
getExtension();
static std::string
getExtension();
bzflag/src/ bzflag/src/ bzflag/src/ bzflag/src/ 共通単語
mediafile/S mediafile/S mediafile/W mediafile/Wa 数/最小
GIImageFile. GIImageFile. aveAudioFile veAudioFile. 単語数
cxx
1h
1 .cxx
1h
1
1
1
1
1
1
1
2
2
2
2
1
2
1
3
1
1
1
1
1
1
1
0
0
0
0
0
Index: bzflag/src/mediafile/SGIImageFile.cxx
1
1
1
1
1
diff -r1.2 -r1.3
1
1
1
1
1
14c14
2 "BzfString.h"
2
2
2
1
< #include
1
1
1
1
1
--> #include
<string>
13
13
13
13
1
70c70
0
0
0
0
0
< BzfString
5 SGIImageFile::getExtension()
5
5
5
1
--5
5
5
5
1
> std::string SGIImageFile::getExtension()
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Index: bzflag/src/mediafile/WaveAudioFile.cxx
1
1
1
1
1
diff -r1.2 -r1.3
1
1
1
1
1
14d13
1
1
1
1
1
< #include "BzfString.h"
108c107
< BzfString WaveAudioFile::getExtension()
--> std::string WaveAudioFile::getExtension()
17
連携的結合関係例
トランザク
追加語/削除語トランザクショ追加語/削除語
ション番号① （ADD/DELETE）ン番号②
（ADD/DELETE）
共通単語数
トランザクショトランザクショ共通単語数/
ン①語数
ン②語数
最小単語数
6 ADD
15 ADD
5
6
37 0.83333333
7 ADD
8 DELETE
2
6
2
1
8 ADD
9 DELETE
2
19
2
1
9 18:27:41
ADD
2
7 = trepan 2
1
CommitDate = 2004/06/27 08:55:31
Owner
CommitDate = 2004/06/22
Owner = trepan 10 DELETE
Index: bzflag/include/Protocol.h
10 ADD
11 DELETE
3
9
3
1
Index: bzflag/include/Protocol.h
========================================================
========================================================
12 ADD
14 DELETE
12
13
34 0.92307692
RCS file: /cvsroot/bzflag/bzflag/include/Protocol.h,v
RCS file: /cvsroot/bzflag/bzflag/include/Protocol.h,v
15 ADD
12
13
37 0.92307692
retrieving revision 1.59
retrieving revision 1.58 12 ADD
retrieving revision 1.60
14 DELETE
19
19
34
1
retrieving revision 1.59 13 ADD
diff
-r1.59
-r1.60
diff -r1.58 -r1.59
13 ADD
15 ADD
19
19
37
1
82a83
110a111,112
14 ADD
15 DELETE
2
2
2
> const
uint16_t
MsgPlayerUpdateSmall
= 0x7073;
// 'ps‘1
> const uint16_t
WorldCodeWeapon = 0x7765;
// 'we‘
Index:
bzflag/include/version.h
14 DELETE
34
34
37
1
> const uint16_t
WorldCodeZone = 0x7A6e; 15 ADD
// 'zn‘
========================================================
121a124,125
RCS
file: /cvsroot/bzflag/bzflag/include/version.h,v
> const uint16_t
WorldCodeWeaponSize = 24; // basic
size,
revision 1.46
> const uint16_t
WorldCodeZoneSize = 34; // basicretrieving
size,
retrieving
revision 1.47
Index: bzflag/include/version.h
diff
-r1.46
========================================================-r1.47
29c29
RCS file: /cvsroot/bzflag/bzflag/include/version.h,v
< #define BZ_PROTO_VERSION
"1115“
retrieving revision 1.45
--retrieving revision 1.46
> #define BZ_PROTO_VERSION
"1116“
diff -r1.45 -r1.46
41c41
29c29
< #define BZ_REV
5
< #define BZ_PROTO_VERSION
"1114“
----> #define BZ_REV
6
> #define BZ_PROTO_VERSION
"1115“
41c41
< #define BZ_REV
4
--18
> #define BZ_REV
5
考察

共通単語に含まれる予約語やコメント中の
汎用的な単語(theやof)によって，類似度
が上がってしまう


単語の重み付け，もしくは取捨選択が必要
連携的結合関係において，１つのファイルの
変更・共通単語数が大きいと，他のファイル
の変更に全く関連が無くても，類似度が高く
なる
19
まとめ


構成管理システムから得られるファイルの
変更履歴や変更内容から，論理的結合関
係を持つファイル変更パターンを抽出する
方法を提案した
提案手法を３つのオープンソースに適用し，
いくつかの抽出された論理的結合関係を紹
介した
20
今後の課題

本手法により精選されたファイル変更パター
ンから論理的結合関係を抽出し，提案方法
を評価・改善する



変更内容の分類による結合関係の拡張
類似度計算方法の改良
具体的な閾値(最小同時変更回数や類似度な
ど)の決定方法の確立
21
End of Slide
22

Download Report