既存ソフトウェアの変更履歴を利用したソースコード修正支援システム 井上研究室 田原　靖太

研究の背景(1/3) 近年のソフトウェアの大規模化・複雑化 版管理システムの利用が拡大 ファイルの状態を「リポジトリ」に履歴として登録 新たな版（リビジョン）の登録の際にコメントを付加 過去の開発において版管理システムに蓄積されてきた履歴を，今後の開発・保守作業に役立てたい 近年のソフトウェアの大規模化，複雑化に伴いまして， 版管理システムと呼ばれるシステムを利用することが多くなっています． 版管理システムは，ファイルの状態をリポジトリと呼ばれるところに履歴として登録します． また，新たな版・リビジョンの登録の際にコメントを付け加えます 過去の開発において版管理システムに蓄積されてきた履歴を， 今後の開発や保守作業に役立てたいという要求が出てきています． 2019/4/28 平成13年度　修士論文発表会

研究の背景(2/3) 既存のリポジトリに蓄積された情報を，以後の開発に有効活用されているとはいえない 現状 既存のリポジトリに蓄積された情報を，以後の開発に有効活用されているとはいえない 原因 既存の版管理システムを用いて，蓄積された情報の中から，開発者が必要とする情報を選び出すのが困難 しかし，現状では，・・・ その原因として，・・・ であることが考えられます 2019/4/28 平成13年度　修士論文発表会

研究の背景(3/3) すでに保守段階に入っているソフトウェアに欠陥が発見された！ リポジトリには，様々な修正の履歴が蓄積 過去のプロジェクトの中で今回と同様の欠陥の修正の履歴が残っていれば，それを参照したい しかし，実際にどのリポジトリの，どのファイルの履歴を見てよいか見当がつかない 同様の箇所に対する修正の履歴をリポジトリから検索したい 例えば，保守段階に入っているソフトウェアに欠陥が発見された場合を考えます． このような時，リポジトリには，様々な修正の履歴が蓄積されているため， 過去のプロジェクトの中で今回と同様の欠陥の修正の履歴が 残っているかもしれない．それを利用したいと思うのですが， 2019/4/28 平成13年度　修士論文発表会

ソースコードの一部分をそのまま用いた検索システムが欲しい 既存のシステム CVSSearch 版管理システムCVSのリポジトリから目的のソースコードを検索するシステム キーワードを入力とし，リポジトリへの登録時のコメントを検索することによるソースコードの取り出しが可能 問題点 ソースコードの一部分をそのまま用いた検索システムが欲しい リポジトリへの登録時のコメントを検索 コメントが貧弱なら，検索能力が低下 キーワードでの取り出し キーワードをいつもうまく書けるとは限らない 2019/4/28 平成13年度　修士論文発表会

研究の目的 過去のプロジェクトにおける，プログラムの修正に関する情報から，現在のソースコードに合ったものを見つけたい ソースコード修正支援手法DIMの提案 修正したいソースコード片を入力として，既存ソフトウェアのソースコード変更履歴を検索 検索結果を提示することにより，ソースコードの修正を支援 DIMに基づくソースコード修正支援システムCoDSの試作 2019/4/28 平成13年度　修士論文発表会

ソースコード修正支援手法DIM １．変更情報データベースの構築 ２．変更情報データベースの検索 ３．検索結果の表示 2019/4/28 ＤＩＭは １ ２ ３ の3つから成り立っています． 以降，順を追って概要を説明します 2019/4/28 平成13年度　修士論文発表会

各リビジョンにおいて，次のリビジョンで変更された部分を抜き出してデータベースに登録 変更情報データベースの構築 既存のリポジトリからソースコード変更履歴を取り出し，新たな検索用データベースに格納 検索時のコスト削減が図れる 各リビジョンにおいて，次のリビジョンで変更された部分を抜き出してデータベースに登録 リポジトリ 検索用 データベース 変更部分 コード 2019/4/28 平成13年度　修士論文発表会

データベースの検索 利用者から入力されたソースコード片と，データベースの中のソースコード部分との比較を行う ２つのコードの間に互いに類似している部分があれば，そのコードをマッチしたコードとする マッチしたコード 類似部分含む データベース内 の変更部分 コード 利用者から入力 されたコード 比較 2019/4/28 平成13年度　修士論文発表会

ソースコードの比較 基本方針 トークン単位の比較⇒字句解析 トークンは抽象化して比較 局所アラインメントによる類似部分の検出 空白，コメント，改行位置等を無視 トークンは抽象化して比較 予約語，標準ライブラリ関数をキートークンとする 識別子・定数はキートークンを除きすべて同一視 局所アラインメントによる類似部分の検出 ２つの系列から類似する部分系列を抽出可能 2019/4/28 平成13年度　修士論文発表会

局所アラインメント 局所アラインメントの例 局所アラインメントのスコア S1= pqraxabxcstvq, S2= xyaxbacsnn に対して S1’= axabxcs S2’= ax-bacs　が得られる 局所アラインメントのスコア 対応する位置が一致している個数 n(match) 対応する位置が一致していない個数 n(mismatch) ‘－’の個数 n(gap)　　として， n(match) － n(mismatch) － n(gap) と定義 ギャップ ここでは時間の都合上アルゴリズムの詳細は省きますが， 例えば，次の2つの系列S1,S2に対して，次のような類似部分系列が抽出されます． このように，系列の途中にハイフンを挟んでいくことにより， 文字の対応する位置をあわせます． また，局所アラインメントのスコアを ＠＠個数から＠＠個数とハイフンの個数を引いたものと定義します 2019/4/28 平成13年度　修士論文発表会

類似性の判定 ２トークン列のアラインメントのスコアで判定 スコアが閾値αを超える２系列を類似しているとみなす αは入力トークンの個数Lに応じて次のように決定（経験的に決定） L<30のとき α=0.6×L L>=30のとき α=18 （一定） 2019/4/28 平成13年度　修士論文発表会

検索効率の向上 局所アラインメントは時間計算量が大きい トークン比較の効率化 2トークン列の長さの積に比例 トークン比較の効率化 検索結果の中に必ず含まれていて欲しいキートークン（特性キートークンと呼ぶ）を利用者が指定 指定がない場合は入力に最初に出現するキートークンが特性キートークンになる 特性キートークンが含まれないデータベース内のコードは検索対照から除外　⇒　アラインメント回数の削減 データベースに字句解析済みのトークン列を登録することで，処理時間を短縮 2019/4/28 平成13年度　修士論文発表会

赤字の部分が局所アラインメントの結果として検出される ソースコード比較の実例 入力側コード i (); } i = fopen( i , i ); if ( i == i ) { i ( i , i , i ); i ( i ); i ( i ); データベース側コード i = fopen( i , i ); if ( i == i ) { i ( i ); return( i ); } i = fopen( i , i ); if ( i == i ) { i ( i ); return( i ); } fp = fopen("file1.c", "r"); if ( fp == NULL ) { message("error."); return(-1); } i (); } i = fopen( i , i ); if ( i == i ) { i ( i , i , i ); i ( i ); i ( i ); 字句解析 特性キートークン 一致：25　不一致:1 ギャップ:4 赤字の部分が局所アラインメントの結果として検出される 入力トークン数＝27 ⇒閾値16 マッチ スコア＝20 2019/4/28 平成13年度　修士論文発表会

検索結果の表示 表示項目 入力とマッチしたコード片Cに関するデータ 元のファイル名 Cが変更されたリビジョン（p, p+1） リビジョンp+1がリポジトリに登録された時のコメント Cと入力コード片とのアラインメントスコア 上の1，2を選択すると，そのファイルの該当するリビジョン間の差分を表示する 2019/4/28 平成13年度　修士論文発表会

ソースコード修正支援システムCoDS DIMに基づくソースコード修正支援システムCoDSの試作を行った 対象言語 C言語 版管理システム CVS データベースマネージャ GDBM メイン部分(CoDS-Main)にCGIを使用し，Webインタフェースにより使用する 使用言語：Perl，約1000行 構成ツール データベース作成ツール(使用言語：Perl，約950行) 字句解析ツール（使用言語：Ｃ言語，約1500行） トークン比較ツール（使用言語：Ｃ言語，約450行） 2019/4/28 平成13年度　修士論文発表会

システム構成図 Web サーバ 利用者 CoDS CGI（CoDS-Main） Webブラウザ ソース コード片 検索結果一覧・ 差分 CVS リポジトリ CGI（CoDS-Main） データベース 作成ツール 検索 結果 ソース コード片 システムの構成はこの図のようになっています． 利用者はWebブラウザを通してCoDSを利用します． 利用者からソースコード片を入力として受け取り， DIMに基づく処理を行った後，検索結果一覧や差分等を 利用者に与えます． 検索用 データベース トークン 比較ツール トークン 列 字句解析ツール 2019/4/28 平成13年度　修士論文発表会

適用実験(1/5) 用いたデータ 検索用データベース：FreeBSDのCVSリポジトリの一部を用いた（約730個分のファイルから履歴情報を取得．レコード数約7500個） 入力として以下のコード片を与えた ptr = malloc(SIZE); if (ptr== NULL) { fprintf(stderr, "cannot allocate memory."); exit(1); } それでは、ここからは、本システムを用いた 適用実験について述べます。 このようなデータベースを用意し、 入力として次のようなコード片を与えました。 2019/4/28 平成13年度　修士論文発表会

適用実験(2/5) CoDS 入力 ptr = malloc(SIZE); if (ptr== NULL) { ファイル名と リビジョン番号 入力 ptr = malloc(SIZE); if (ptr== NULL) { fprintf(stderr, "cannot allocate memory."); exit(1); } 差分についての コメント この入力をCoDSに与えると，このように検索結果が一覧表示されます （実際には元のファイル別の一覧になる） この部分に，差分についてのコメントが表示されます， さらに，ファイル名・リビジョン番号を指定することで， CoDS 2019/4/28 平成13年度　修士論文発表会

適用実験(3/5) 変更前 変更後 入力とのマッチ部分を強調表示 2019/4/28 平成13年度 修士論文発表会 このように，該当するリビジョン間の差分を色付で表示します． この中の，赤い字の部分は入力としたコードとマッチした部分を示しています このようにして，入力としたソースコード片と類似した部分の過去の変更履歴を 閲覧することができます． 入力とのマッチ部分を強調表示 2019/4/28 平成13年度　修士論文発表会

適用実験(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 … 入力とマッチした部分の次のリビジョンまでの変更内容について， もう少し詳しく見ていきます． これは，ソースコードの差分と，それに関するコメントを 突き合わせることにより，バッファオーバランを修正したリビジョン間だったことが わかります． 2019/4/28 平成13年度　修士論文発表会

適用実験(5/5) コメントの参照・・・バッファオーバフローを修正 差分の参照・・・mallocの引数の修正 与えた入力に対して，類似した部分の履歴を検索できる 提示された差分と，それに関するコメントを参照することで，利用者は過去に起こったエラーの事例とその解決法を知ることができる 2019/4/28 平成13年度　修士論文発表会

まとめ ソースコード修正支援手法DIMの提案 DIMに基づく修正支援システムCoDSの試作 版管理システムに蓄積された履歴をデータベース化 ソースコード片によるデータベース検索 検索結果の表示 DIMに基づく修正支援システムCoDSの試作 2019/4/28 平成13年度　修士論文発表会

今後の課題 実際の保守作業に適用することによる本手法の有効性の評価 より妥当な検索結果を得るためのアラインメントスコア計算方法の改良 利用者が必要としているものを漏れなく取り出せるか？ 得られた結果のうち，実際に修正に利用できる割合はどのくらいか？ より妥当な検索結果を得るためのアラインメントスコア計算方法の改良 2019/4/28 平成13年度　修士論文発表会

終

変更情報データベースの構築 あるソースファイルFの隣接する2つのリビジョン間(p~p+1)に着目 A A’ B B’ 2019/4/28 平成13年度　修士論文発表会

変更情報データベースの構築 各ファイルにつき，各pから p+1までの変更部分コードを次々と取得し，データベースに登録 その他にも以下のような情報が登録される データベースの1レコード ファイル名F リビジョン番号p リビジョン番号p+1 p+1のコミット日時 p+1に対するコメント 変更部分コードの集合 注）　F，p，p+1を指定すればレコードが一意に定まる 2019/4/28 平成13年度　修士論文発表会

評価実験(計画) 評価項目 検索結果の妥当性 閾値の設定の妥当性 必要な情報をちゃんと取得できるか 結果のうち，意味的にも一致する割合はどれくらいか？ ⇒人間の目による主観的な評価がよい 閾値の設定の妥当性 閾値をいろいろ変えて，上の実験を行う ただし，ヒットしたリビジョン間で行われた修正が,現在望んでいるものなのかを判断するのは，利用者も，システム側も難しい 2019/4/28 平成13年度　修士論文発表会

スコアの式を前述したものに固定したとして L<30のとき α＝(0.6＊L)　の整数部分 L>=30 のとき α＝18 α=L とすると，入力全体と完全に一致するもののみ α=0.6＊Lのときは，検出部分のうち5分の4が一致している 入力トークン数より大きい値にならないようにする 入力トークン数が大きいときに，閾値が大きくなり過ぎないようにする 2019/4/28 平成13年度　修士論文発表会

適用例 提示された差分と，それに関するコメントを参照することで，過去に起こったエラーの事例とその解決法を知ることができる コメント参照・・・バッファオーバフローを直している 差分の参照・・・mallocの引数が間違っていた 得られた情報を自分が作業中のプログラムに反映できるかどうかの判断は利用者が行う 2019/4/28 平成13年度　修士論文発表会

検索時間の測定 FreeBSDのCVSリポジトリから取得した３つのデータベースA，B，Cと，入力X, Y, Zを用意 検索速度に影響 A データ取得 ファイル数 レコード数 格納トークン総数 A 151 1478 約66万9000 B 733 7466 約158万2000 C 371 3220 約321万1000 行数 トークン数 特性キートークン X 3 22 if Y 14 78 Z 53 290 検索速度に影響 2019/4/28 平成13年度　修士論文発表会

検索時間の測定 特性キートークンが“if”の入力 いずれのデータベースにおいても，”ｉｆ”を含むコード片の個数が他のキートークンに比べて多い ⇒アラインメント回数大⇒検索時間大 計測環境 CPU: Pentium4 2GHz RAM: 1GB OS: FreeBSD4.5-Stable Webサーバ: Apache1.3.22 2019/4/28 平成13年度　修士論文発表会

検索時間の評価 入力トークン数，データベースサイズが大きくなれば，比例的に検索時間が大きくなる 通常の使用には支障ない データベース内での出現率の高いif, else等のキートークンが特性キートークンの場合，検索時間は大 特性キートークンがそれ以外の時は，多少入力サイズが大きくても実用時間で検索可能 2019/4/28 平成13年度　修士論文発表会