既存ソフトウェアの変更履歴を利用した
ソースコード修正支援手法の提案
田原靖太 松下誠 井上克郎
大阪大学大学院基礎工学研究科
研究の背景(1/3)
近年のソフトウェアの大規模化・複雑化
版管理システムの利用が拡大
過去の開発において版管理システムに蓄積され
てきた履歴を，今後の開発・保守作業に役立て
たい
2015/10/1
第136回 ソフトウェア工学研究会
2
研究の背景(2/3)
現状
既存のリポジトリに蓄積された情報を，以後の開
発に有効活用されているとはいえない
原因
既存の版管理システムを用いて，蓄積された情
報の中から，開発者が必要とする情報を選び出
すのが困難
2015/10/1
第136回 ソフトウェア工学研究会
3
研究の背景(3/3)
すでに保守段階に入っているソフトウェアに欠陥が発見
された！
リポジトリには，様々な修正の履歴が蓄積
過去のプロジェクトの中で今回と同様の欠陥の修正の履歴が
残っていれば，それを参照したい
しかし，実際にどのリポジトリの，どのファイルの履歴を
見てよいか見当がつかない
同様の箇所に対する修正の履歴をリポジトリから検索し
たい
2015/10/1
第136回 ソフトウェア工学研究会
4
既存のシステム
CVSSearch
版管理システムCVSのリポジトリから目的のソースコード
を検索するシステム
キーワードを入力とし，リポジトリへのコミット時のコメントを検索
することによるソースコードの取り出しが可能
問題点
リポジトリへのコミット時のコメントを検索 ソースコードの一部
コメントが貧弱なら，検索能力が低下
キーワードでの取り出し
2015/10/1
キーワードをいつもうまく書けるとは限らない
第136回 ソフトウェア工学研究会
分をそのまま用い
た検索システムが
欲しい
5
研究の目的
過去のプロジェクトにおける，プログラムの修正
に関する情報から，現在のソースコードに合った
ものを見つけたい
ソースコード修正支援手法の提案
2015/10/1
修正したいソースコード片を入力として，既存ソフト
ウェアのソースコード変更履歴を検索
検索結果を提示することにより，ソースコードの修正を
支援
第136回 ソフトウェア工学研究会
6
提案するソースコード修正支援手法
入力としたソースコード片と同様の箇所が過去にどのよう
に変更されたのかを検索
Step1．検索用データベースの作成
Step2．データベースの検索
Step3．検索結果の表示
2015/10/1
第136回 ソフトウェア工学研究会
7
Step1.検索用データベースの作成(1)
既存のリポジトリからソースコード変更履歴を取
り出し，検索用データベースに格納
検索時のコスト削減
各リビジョンにおいて，次のリビ
ジョンで変更された部分を抜き出
してデータベースに登録
リポジトリ
2015/10/1
変更部分
コード
第136回 ソフトウェア工学研究会
検索用
データベース
8
Step1.検索用データベースの作成(2)
各ファイルにつき，隣接する２つのリビジョンpから p+1
までの変更部分コードを次々と取得し，データベースに
登録
変更部分コードに付随する情報として以下のデータが登
録される
データベースの1レコード
ファイル名F
リビジョン番号p
リビジョン番号p+1
p+1のコミット日時
p+1に対するコメント
変更部分コードの集合
注） F，p，p+1を指定すればレコードが一意に定まる
2015/10/1
第136回 ソフトウェア工学研究会
9
Step2.データベースの検索(1)
検索の概要
利用者から入力されたソースコード片と，データベースの
中のソースコード部分との比較を行う
２つのコードの間に互いに類似している部分があれば，
そのコードをマッチしたコードとする
マッチしたコード
類似部分含む
データベース内
の変更部分
コード
2015/10/1
比較
第136回 ソフトウェア工学研究会
利用者から入力
されたコード
10
Step2.データベースの検索(2)
ソースコードの比較
基本方針
字句解析を行い，トークン列に変換して比較
空白，コメント，改行位置等を無視
識別子等を抽象化して比較
局所アラインメントによる類似部分の検出
２つの系列から類似する部分系列を抽出可能
2015/10/1
第136回 ソフトウェア工学研究会
11
Step2.データベースの検索(3)
トークン列への変換
変換の概要（C言語を想定）
2015/10/1
演算子，予約語等はそれぞれ区別したトーク
ンに変換
識別子・定数は，原則的に同一のトークンに
変換
ただし，標準ライブラリ関数名は区別したトー
クンに変換
（予約語，標準ライブラリ関数名を合わせて
『キートークン』と呼ぶ）
第136回 ソフトウェア工学研究会
12
Step2.データベースの検索(4)
局所アラインメント
局所アラインメントの例
S1= pqraxabxcstvq, S2= xyaxbacsnn
に対して
S1’= axabxcs
ギャップ
S2’= ax-bacs が得られる
局所アラインメントのスコア
n(match)
n(mismatch)
n(gap) として，
n(match) － n(mismatch) － n(gap) と定義
対応する位置が一致している個数
対応する位置が一致していない個数
‘－’の個数
2015/10/1
第136回 ソフトウェア工学研究会
13
Step2.データベースの検索(5)
類似性の判定
２トークン列のアラインメントのスコアで判定
スコアが閾値αを超える２トークン列を類似してい
るとみなす
αは入力トークンの個数Lに応じて次のように決
定（経験的に決定）
L<=30のとき α=0.6×L
L>30のとき
α=19 （一定）
2015/10/1
第136回 ソフトウェア工学研究会
14
Step2.データベースの検索(6)
検索効率の向上
局所アラインメントは時間計算量が大きい
2トークン列の長さの積に比例
トークン比較の効率化
利用者が，検索結果の中に必ず含まれていて欲しいキートーク
ン（特性キートークンと呼ぶ）を指定
指定がない場合は入力に最初に出現するキートークンが特性キートークン
になる
特性キートークンが含まれないデータベース内のコードは検索対
照から除外 ⇒ アラインメント回数の削減
データベースに字句解析済みのトークン列を登録するこ
とで，処理時間を短縮
2015/10/1
第136回 ソフトウェア工学研究会
15
Step2.データベースの検索(7)
ソースコード比較の実例
入力側コード
fp = fopen("file1.c", "r");
if ( fp == NULL ) {
message("error.");
return(-1);
}
2015/10/1
変換後
i = fopen( i
, i );
if ( i == i
){
i
(
i
);
return( i );
}
第136回 ソフトウェア工学研究会
16
Step2.データベースの検索(7)
ソースコード比較の実例
入力側コード
i = fopen( i
, i );
if ( i == i
){
i
(
i
);
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
マッチ
第136回 ソフトウェア工学研究会
スコア＝20
17
Step3.検索結果の表示
表示項目
入力とマッチしたコード片Cに関するデータ
1. 元のファイル名
2. Cが変更されたリビジョン（p, p+1）
3. 変更後リビジョンp+1がリポジトリに格納された時のコメント
4. Cと入力コード片とのアラインメントスコア
2015/10/1
上の1，2を選択すると，リポジトリにアクセスし，その
ファイルの該当するリビジョン間の差分を表示する
第136回 ソフトウェア工学研究会
18
ソースコード修正支援システム
提案した手法に基づくソースコード修正支
援システムの試作を行っている
対象言語
版管理システム
構成ツール
C言語
CVS
メイン部(CGI)
データベース作成ツール
字句解析ツール
トークン比較ツール
2015/10/1
第136回 ソフトウェア工学研究会
19
システムイメージ図
Webブラウザ
ソース
コード片
Web
サーバ
利用者
検索結果一覧・
差分
本システム
CGI（メイン部）
CVS
リポジトリ
データベース
作成ツール
検索用
データベース
2015/10/1
ソース
コード片
検索
結果
トークン
比較ツール
トークン
列
第136回 ソフトウェア工学研究会
字句解析ツール
20
適用例(1/3)
検索されるコード片の例
入力コード片
ptr = malloc(SIZE);
if (ptr== NULL) {
fprintf(stderr,
"cannot allocate memory.");
exit(1);
}
付随するファイル名，
リビジョン番号をもとに，
リポジトリにアクセスし，
差分を表示
2015/10/1
if (to_cat) {
int len = strlen (name) + 3;
int cextlen = strlen(COMPRESS_EXT);
to_name = (char *) malloc (len);
if (to_name == NULL)
gripe_alloc (len, "to_name");
strcpy (to_name, name);
if (strcmp(name + (len - (3 + cextlen)),
COMPRESS_EXT))
strcat (to_name, COMPRESS_EXT);
}
else
to_name = strdup (name);
第136回 ソフトウェア工学研究会
21
適用例(2/3)
（←変更前） 差分 （変更後→）
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
第136回 ソフトウェア工学研究会
22
適用例(3/3)
コメントの参照・・・バッファオーバフローを修正
差分の参照・・・mallocの引数の修正
与えた入力に対して，類似した部分の履歴を検
索できる
提示された差分と，それに関するコメントを参照
することで，利用者は過去に起こったエラーの事
例とその解決法を知ることができる
2015/10/1
第136回 ソフトウェア工学研究会
23
まとめ
ソースコード修正支援手法の提案
版管理システムに蓄積された履歴をデータベース化
ソースコード片によるデータベース検索
検索結果の表示
本手法によって，手元にあるソースコードから，
同様の部分の修正履歴を簡単に閲覧することが
可能になった
2015/10/1
第136回 ソフトウェア工学研究会
24
今後の課題
データベース作成部分の改良
より意味のある単位での差分の取り出し
実際の保守作業に適用することによる本手法の
有効性の評価
利用者が必要としているものを漏れなく取り出せる
か？
得られた結果のうち，実際に修正に利用できる割合
はどのくらいか？
より妥当な検索結果を得るためのアラインメント
スコア計算方法の改良
2015/10/1
第136回 ソフトウェア工学研究会
25
終
変更情報データベースの構築
あるソースファイルFの隣接する2つのリビジョン間
(p~p+1)に着目
pにおいて，p+1までに変更が行われた部分の集合をデータベー
スに登録
(F, p, p+1)の組と，変更部分の集合とを一対一で対応付け
ファイルFの履歴
A
変更
A’
B’
B
変更
リビジョンp
2015/10/1
リビジョンp+1
第136回 ソフトウェア工学研究会
27
変更情報データベースの構築
各ファイルにつき，各pから p+1までの変更部分コードを
次々と取得し，データベースに登録
その他にも以下のような情報が登録される
データベースの1レコード
ファイル名F
リビジョン番号p
リビジョン番号p+1
p+1のコミット日時
p+1に対するコメント
変更部分コードの集合
注） F，p，p+1を指定すればレコードが一意に定まる
2015/10/1
第136回 ソフトウェア工学研究会
28
スコアの閾値
スコアの式を前述したものに固定したとして
L<30のとき
α＝(0.6＊L) の整数部分
L>=30 のとき α＝18
α=L とすると，入力全体と完全に一致するもののみ
α=0.6＊Lのときは，検出部分のうち5分の4が一致している
2015/10/1
入力トークン数より大きい値にならないようにする
入力トークン数が大きいときに，閾値が大きくなり過ぎ
ないようにする
第136回 ソフトウェア工学研究会
29
検索時間の測定
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
第136回 ソフトウェア工学研究会
if
検索速度に
影響
30
検索時間の測定
特性キートークンが“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
第136回 ソフトウェア工学研究会
B
データベース
C
31
検索時間の評価
入力トークン数，データベースサイズが大きくな
れば，比例的に検索時間が大きくなる
通常の使用には支障ない
2015/10/1
データベース内での出現率の高いif, else等のキー
トークンが特性キートークンの場合，検索時間は大
特性キートークンがそれ以外の時は，多少入力サイ
ズが大きくても実用時間で検索可能
第136回 ソフトウェア工学研究会
32
適用例(2/5)
ファイル名と
リビジョン番号
入力
ptr = malloc(SIZE);
if (ptr== NULL) {
fprintf(stderr,
"cannot allocate memory.");
exit(1);
}
差分についての
コメント
システム
2015/10/1
第136回 ソフトウェア工学研究会
33
適用例(3/5)
変更前
変更後
入力とのマッチ部
分を強調表示
2015/10/1
第136回 ソフトウェア工学研究会
34
© Copyright 2024 ExpyDoc
