既存ソフトウェアの変更履歴を利用した
ソースコード修正支援システム
井上研究室
田原 靖太
研究の背景(1/3)
近年のソフトウェアの大規模化・複雑化
版管理システムの利用が拡大
ファイルの状態を「リポジトリ」に履歴として登録
新たな版（リビジョン）の登録の際にコメントを付加
過去の開発において版管理システムに蓄積され
てきた履歴を，今後の開発・保守作業に役立て
たい
2015/10/1
平成13年度 修士論文発表会
2
研究の背景(2/3)
現状
既存のリポジトリに蓄積された情報を，以後の開
発に有効活用されているとはいえない
原因
既存の版管理システムを用いて，蓄積された情
報の中から，開発者が必要とする情報を選び出
すのが困難
2015/10/1
平成13年度 修士論文発表会
3
研究の背景(3/3)
すでに保守段階に入っているソフトウェアに欠陥が発見
された！
リポジトリには，様々な修正の履歴が蓄積
過去のプロジェクトの中で今回と同様の欠陥の修正の履歴が
残っていれば，それを参照したい
しかし，実際にどのリポジトリの，どのファイルの履歴を
見てよいか見当がつかない
同様の箇所に対する修正の履歴をリポジトリから検索し
たい
2015/10/1
平成13年度 修士論文発表会
4
既存のシステム
CVSSearch
版管理システムCVSのリポジトリから目的のソースコード
を検索するシステム
キーワードを入力とし，リポジトリへの登録時のコメントを検索す
ることによるソースコードの取り出しが可能
問題点
リポジトリへの登録時のコメントを検索
コメントが貧弱なら，検索能力が低下
キーワードでの取り出し
2015/10/1
キーワードをいつもうまく書けるとは限らない
平成13年度 修士論文発表会
ソースコードの一部
分をそのまま用い
た検索システムが
欲しい
5
研究の目的
過去のプロジェクトにおける，プログラムの修正に関する
情報から，現在のソースコードに合ったものを見つけたい
ソースコード修正支援手法DIMの提案
修正したいソースコード片を入力として，既存ソフトウェアのソー
スコード変更履歴を検索
検索結果を提示することにより，ソースコードの修正を支援
DIMに基づくソースコード修正支援システムCoDSの試作
2015/10/1
平成13年度 修士論文発表会
6
ソースコード修正支援手法DIM
１．変更情報データベースの構築
２．変更情報データベースの検索
３．検索結果の表示
2015/10/1
平成13年度 修士論文発表会
7
変更情報データベースの構築
既存のリポジトリからソースコード変更履歴を取
り出し，新たな検索用データベースに格納
検索時のコスト削減が図れる
各リビジョンにおいて，次のリビ
ジョンで変更された部分を抜き出
してデータベースに登録
リポジトリ
2015/10/1
変更部分
コード
平成13年度 修士論文発表会
検索用
データベース
8
データベースの検索
利用者から入力されたソースコード片と，データベースの
中のソースコード部分との比較を行う
２つのコードの間に互いに類似している部分があれば，
そのコードをマッチしたコードとする
マッチしたコード
類似部分含む
データベース内
の変更部分
コード
2015/10/1
比較
平成13年度 修士論文発表会
利用者から入力
されたコード
9
ソースコードの比較
基本方針
トークン単位の比較⇒字句解析
空白，コメント，改行位置等を無視
トークンは抽象化して比較
予約語，標準ライブラリ関数をキートークンとする
識別子・定数はキートークンを除きすべて同一視
局所アラインメントによる類似部分の検出
２つの系列から類似する部分系列を抽出可能
2015/10/1
平成13年度 修士論文発表会
10
局所アラインメント
局所アラインメントの例
S1= pqraxabxcstvq, S2= xyaxbacsnn
に対して
S1’= axabxcs
ギャップ
S2’= ax-bacs が得られる
局所アラインメントのスコア
n(match)
n(mismatch)
n(gap) として，
n(match) － n(mismatch) － n(gap) と定義
対応する位置が一致している個数
対応する位置が一致していない個数
‘－’の個数
2015/10/1
平成13年度 修士論文発表会
11
類似性の判定
２トークン列のアラインメントのスコアで判定
スコアが閾値αを超える２系列を類似していると
みなす
αは入力トークンの個数Lに応じて次のように決
定（経験的に決定）
L<30のとき
α=0.6×L
L>=30のとき α=18 （一定）
2015/10/1
平成13年度 修士論文発表会
12
検索効率の向上
局所アラインメントは時間計算量が大きい
2トークン列の長さの積に比例
トークン比較の効率化
検索結果の中に必ず含まれていて欲しいキートークン（特性キー
トークンと呼ぶ）を利用者が指定
指定がない場合は入力に最初に出現するキートークンが特性キートークン
になる
特性キートークンが含まれないデータベース内のコードは検索対
照から除外 ⇒ アラインメント回数の削減
データベースに字句解析済みのトークン列を登録するこ
とで，処理時間を短縮
2015/10/1
平成13年度 修士論文発表会
13
ソースコード比較の実例
入力側コード
fp
i = fopen(
fopen("file1.c",
i
, "r");
i );
if ( fp
i == NULL
i ){
message("error.");
i
(
i
);
return(-1);
return(
i );
字句解析
}
データベース側コード
}
i ();
i = fopen( i , i );
if ( i == i ) {
i ( i , i , i );
i ( i );
特性キートークン
i ();
一致：25 不一致:1
}
ギャップ:4
赤字の部分が局所アラインメ
i ( i );
ントの結果として検出される
入力トークン数＝27
⇒閾値16
2015/10/1
マッチ
平成13年度 修士論文発表会
スコア＝20
14
検索結果の表示
表示項目
入力とマッチしたコード片Cに関するデータ
1. 元のファイル名
2. Cが変更されたリビジョン（p, p+1）
3. リビジョンp+1がリポジトリに登録された時のコメント
4. Cと入力コード片とのアラインメントスコア
2015/10/1
上の1，2を選択すると，そのファイルの該当するリビ
ジョン間の差分を表示する
平成13年度 修士論文発表会
15
ソースコード修正支援システムCoDS
DIMに基づくソースコード修正支援システムCoDSの試作
を行った
対象言語
C言語
版管理システム
CVS
データベースマネージャ GDBM
メイン部分(CoDS-Main)にCGIを使用し，Webインタフェースによ
り使用する
使用言語：Perl，約1000行
構成ツール
データベース作成ツール(使用言語：Perl，約950行)
字句解析ツール（使用言語：Ｃ言語，約1500行）
トークン比較ツール（使用言語：Ｃ言語，約450行）
2015/10/1
平成13年度 修士論文発表会
16
システム構成図
Webブラウザ
ソース
コード片
Web
サーバ
利用者
検索結果一覧・
差分
CVS
リポジトリ
データベース
作成ツール
検索用
データベース
2015/10/1
CoDS
CGI（CoDS-Main）
ソース
コード片
検索
結果
トークン
比較ツール
平成13年度 修士論文発表会
トークン
列
字句解析ツール
17
適用実験(1/5)
用いたデータ
検索用データベース：FreeBSDのCVSリポジトリの一部
を用いた（約730個分のファイルから履歴情報を取得．
レコード数約7500個）
入力として以下のコード片を与えた
ptr = malloc(SIZE);
if (ptr== NULL) {
fprintf(stderr,
"cannot allocate memory.");
exit(1);
}
2015/10/1
平成13年度 修士論文発表会
18
適用実験(2/5)
ファイル名と
リビジョン番号
入力
ptr = malloc(SIZE);
if (ptr== NULL) {
fprintf(stderr,
"cannot allocate memory.");
exit(1);
}
差分についての
コメント
CoDS
2015/10/1
平成13年度 修士論文発表会
19
適用実験(3/5)
変更前
変更後
入力とのマッチ部
分を強調表示
2015/10/1
平成13年度 修士論文発表会
20
適用実験(4/5)
（←変更前） 差分 （変更後→）
to_name = (char *) malloc(len);
if (to_name == NULL)
gripe_alloc (len, "to_name");
strcpy (to_name, name);
to_name = malloc (len+1);
if (to_name == NULL)
gripe_alloc (len+1, "to_name");
strcpy (to_name, name);
コメント
Even more buffer overflow fixes
Change CATMODE to 0644, because group man not used
Add immutable sbit to man binary, so if user even got man uid,
he can't replace man binary with fake one
…
2015/10/1
平成13年度 修士論文発表会
21
適用実験(5/5)
コメントの参照・・・バッファオーバフローを修正
差分の参照・・・mallocの引数の修正
与えた入力に対して，類似した部分の履歴を検
索できる
提示された差分と，それに関するコメントを参照
することで，利用者は過去に起こったエラーの事
例とその解決法を知ることができる
2015/10/1
平成13年度 修士論文発表会
22
まとめ
ソースコード修正支援手法DIMの提案
版管理システムに蓄積された履歴をデータベース化
ソースコード片によるデータベース検索
検索結果の表示
DIMに基づく修正支援システムCoDSの試作
2015/10/1
平成13年度 修士論文発表会
23
今後の課題
実際の保守作業に適用することによる本手法の
有効性の評価
利用者が必要としているものを漏れなく取り出せる
か？
得られた結果のうち，実際に修正に利用できる割合
はどのくらいか？
より妥当な検索結果を得るためのアラインメント
スコア計算方法の改良
2015/10/1
平成13年度 修士論文発表会
24
終
変更情報データベースの構築
あるソースファイルFの隣接する2つのリビジョン間
(p~p+1)に着目
pにおいて，p+1までに変更が行われた部分の集合をデータベー
スに登録
(F, p, p+1)の組と，変更部分の集合とを一対一で対応付け
ファイルFの履歴
変更
A
A’
B’
B
変更
リビジョンp
2015/10/1
リビジョンp+1
平成13年度 修士論文発表会
26
変更情報データベースの構築
各ファイルにつき，各pから p+1までの変更部分コードを
次々と取得し，データベースに登録
その他にも以下のような情報が登録される
データベースの1レコード
ファイル名F
リビジョン番号p
リビジョン番号p+1
p+1のコミット日時
p+1に対するコメント
変更部分コードの集合
注） F，p，p+1を指定すればレコードが一意に定まる
2015/10/1
平成13年度 修士論文発表会
27
評価実験(計画)
評価項目
検索結果の妥当性
必要な情報をちゃんと取得できるか
結果のうち，意味的にも一致する割合はどれくらいか？
⇒人間の目による主観的な評価がよい
閾値の設定の妥当性
閾値をいろいろ変えて，上の実験を行う
2015/10/1
ただし，ヒットしたリビジョン間で行われた修正が,現在
望んでいるものなのかを判断するのは，利用者も，シ
ステム側も難しい
平成13年度 修士論文発表会
28
スコアの式を前述したものに固定したとして
L<30のとき
α＝(0.6＊L) の整数部分
L>=30 のとき α＝18
α=L とすると，入力全体と完全に一致するもののみ
α=0.6＊Lのときは，検出部分のうち5分の4が一致している
2015/10/1
入力トークン数より大きい値にならないようにする
入力トークン数が大きいときに，閾値が大きくなり過ぎ
ないようにする
平成13年度 修士論文発表会
29
適用例
提示された差分と，それに関するコメントを参照
することで，過去に起こったエラーの事例とその
解決法を知ることができる
コメント参照・・・バッファオーバフローを直している
差分の参照・・・mallocの引数が間違っていた
得られた情報を自分が作業中のプログラムに反映できる
かどうかの判断は利用者が行う
2015/10/1
平成13年度 修士論文発表会
30
検索時間の測定
FreeBSDのCVSリポジトリから取得した３つのデータベー
スA，B，Cと，入力X, Y, Zを用意
データ取得
ファイル数
レコード数
A
151
1478
約66万9000
B
733
7466
約158万2000
C
371
3220
約321万1000
行数
2015/10/1
格納トークン総数
トークン数
X
3
Y
14
Z
53
特性キートークン
if
22
if
78
290
平成13年度 修士論文発表会
if
検索速度に
影響
31
検索時間の測定
特性キートークンが“if”の入力
いずれのデータベースにおいても，”ｉｆ”を含むコード
片の個数が他のキートークンに比べて多い
⇒アラインメント回数大⇒検索時間大
120
100
時 80
間
入力X
入力Y
入力Z
60
(
秒 40
)
計測環境
CPU:
Pentium4 2GHz
RAM:
1GB
OS:
FreeBSD4.5-Stable
Webサーバ: Apache1.3.22
20
0
A
2015/10/1
平成13年度 修士論文発表会
B
データベース
C
32
検索時間の評価
入力トークン数，データベースサイズが大きくな
れば，比例的に検索時間が大きくなる
通常の使用には支障ない
2015/10/1
データベース内での出現率の高いif, else等のキー
トークンが特性キートークンの場合，検索時間は大
特性キートークンがそれ以外の時は，多少入力サイ
ズが大きくても実用時間で検索可能
平成13年度 修士論文発表会
33
© Copyright 2024 ExpyDoc
