既存ソフトウェアの変更履歴を利用したソースコード修正支援手法の提案 田原靖太　松下誠　井上克郎 大阪大学大学院基礎工学研究科

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

研究の背景(2/3) 既存のリポジトリに蓄積された情報を，以後の開発に有効活用されているとはいえない 現状 既存のリポジトリに蓄積された情報を，以後の開発に有効活用されているとはいえない 原因 既存の版管理システムを用いて，蓄積された情報の中から，開発者が必要とする情報を選び出すのが困難 しかし，現状では，・・・ その原因として，・・・ であることが考えられます 2019/1/17 第136回　ソフトウェア工学研究会

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

ソースコードの一部分をそのまま用いた検索システムが欲しい 既存のシステム CVSSearch 版管理システムCVSのリポジトリから目的のソースコードを検索するシステム キーワードを入力とし，リポジトリへのコミット時のコメントを検索することによるソースコードの取り出しが可能 問題点 ソースコードの一部分をそのまま用いた検索システムが欲しい リポジトリへのコミット時のコメントを検索 コメントが貧弱なら，検索能力が低下 キーワードでの取り出し キーワードをいつもうまく書けるとは限らない 2019/1/17 第136回　ソフトウェア工学研究会

研究の目的 過去のプロジェクトにおける，プログラムの修正に関する情報から，現在のソースコードに合ったものを見つけたい ソースコード修正支援手法の提案 修正したいソースコード片を入力として，既存ソフトウェアのソースコード変更履歴を検索 検索結果を提示することにより，ソースコードの修正を支援 2019/1/17 第136回　ソフトウェア工学研究会

提案するソースコード修正支援手法 入力としたソースコード片と同様の箇所が過去にどのように変更されたのかを検索 Step1．検索用データベースの作成 Step2．データベースの検索 ＤＩＭは １ ２ ３ の3つから成り立っています． 以降，順を追って概要を説明します Step3．検索結果の表示 2019/1/17 第136回　ソフトウェア工学研究会

各リビジョンにおいて，次のリビジョンで変更された部分を抜き出してデータベースに登録 Step1.検索用データベースの作成(1) 既存のリポジトリからソースコード変更履歴を取り出し，検索用データベースに格納 検索時のコスト削減 各リビジョンにおいて，次のリビジョンで変更された部分を抜き出してデータベースに登録 リポジトリ 検索用 データベース 変更部分 コード 2019/1/17 第136回　ソフトウェア工学研究会

Step1.検索用データベースの作成(2) 各ファイルにつき，隣接する２つのリビジョンpから p+1 までの変更部分コードを次々と取得し，データベースに登録 変更部分コードに付随する情報として以下のデータが登録される データベースの1レコード ファイル名F リビジョン番号p リビジョン番号p+1 p+1のコミット日時 p+1に対するコメント 変更部分コードの集合 注）　F，p，p+1を指定すればレコードが一意に定まる 2019/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(1) 検索の概要 利用者から入力されたソースコード片と，データベースの中のソースコード部分との比較を行う ２つのコードの間に互いに類似している部分があれば，そのコードをマッチしたコードとする マッチしたコード 類似部分含む データベース内 の変更部分 コード 利用者から入力 されたコード 比較 2019/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(2) ソースコードの比較 基本方針 字句解析を行い，トークン列に変換して比較 空白，コメント，改行位置等を無視 識別子等を抽象化して比較 局所アラインメントによる類似部分の検出 ２つの系列から類似する部分系列を抽出可能 2019/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(3) トークン列への変換 変換の概要（C言語を想定） 演算子，予約語等はそれぞれ区別したトークンに変換 識別子・定数は，原則的に同一のトークンに変換 ただし，標準ライブラリ関数名は区別したトークンに変換 （予約語，標準ライブラリ関数名を合わせて『キートークン』と呼ぶ） 2019/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(4) 局所アラインメント 局所アラインメントの例 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/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(5) 類似性の判定 ２トークン列のアラインメントのスコアで判定 スコアが閾値αを超える２トークン列を類似しているとみなす αは入力トークンの個数Lに応じて次のように決定（経験的に決定） L<=30のとき α=0.6×L L>30のとき α=19 （一定） 2019/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(6) 検索効率の向上 局所アラインメントは時間計算量が大きい 2トークン列の長さの積に比例 トークン比較の効率化 利用者が，検索結果の中に必ず含まれていて欲しいキートークン（特性キートークンと呼ぶ）を指定 指定がない場合は入力に最初に出現するキートークンが特性キートークンになる 特性キートークンが含まれないデータベース内のコードは検索対照から除外　⇒　アラインメント回数の削減 データベースに字句解析済みのトークン列を登録することで，処理時間を短縮 2019/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(7) ソースコード比較の実例 入力側コード i = fopen( i , i ); if ( i == i ) { i ( i ); return( i ); } 変換後 fp = fopen("file1.c", "r"); if ( fp == NULL ) { message("error."); return(-1); } 2019/1/17 第136回　ソフトウェア工学研究会

Step2.データベースの検索(7) ソースコード比較の実例 入力側コード 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 ); } i (); } i = fopen( i , i ); if ( i == i ) { i ( i , i , i ); i ( i ); i ( i ); 特性キートークン 一致：25　不一致:1 ギャップ:4 赤字の部分が局所アラインメントの結果として検出される 入力トークン数＝27 ⇒閾値16 マッチ スコア＝20 2019/1/17 第136回　ソフトウェア工学研究会

Step3.検索結果の表示 表示項目 入力とマッチしたコード片Cに関するデータ 元のファイル名 Cが変更されたリビジョン（p, p+1） 変更後リビジョンp+1がリポジトリに格納された時のコメント Cと入力コード片とのアラインメントスコア 上の1，2を選択すると，リポジトリにアクセスし，そのファイルの該当するリビジョン間の差分を表示する 2019/1/17 第136回　ソフトウェア工学研究会

ソースコード修正支援システム 提案した手法に基づくソースコード修正支援システムの試作を行っている 対象言語 C言語 版管理システム CVS 構成ツール メイン部(CGI) データベース作成ツール 字句解析ツール トークン比較ツール 2019/1/17 第136回　ソフトウェア工学研究会

システムイメージ図 Web サーバ 利用者 CGI（メイン部） 本システム Webブラウザ ソース コード片 検索結果一覧・ 差分 CVS リポジトリ CGI（メイン部） データベース 作成ツール 検索 結果 ソース コード片 システムの構成はこの図のようになっています． 利用者はWebブラウザを通してCoDSを利用します． 利用者からソースコード片を入力として受け取り， DIMに基づく処理を行った後，検索結果一覧や差分等を 利用者に与えます． 検索用 データベース トークン 比較ツール トークン 列 字句解析ツール 2019/1/17 第136回　ソフトウェア工学研究会

適用例(1/3) 入力コード片 検索されるコード片の例 付随するファイル名， リビジョン番号をもとに， リポジトリにアクセスし，差分を表示 ptr = malloc(SIZE); if (ptr== NULL) { fprintf(stderr, "cannot allocate memory."); exit(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); 付随するファイル名， リビジョン番号をもとに， リポジトリにアクセスし，差分を表示 それでは、ここからは、本システムを用いた 適用実験について述べます。 このようなデータベースを用意し、 入力として次のようなコード片を与えました。 2019/1/17 第136回　ソフトウェア工学研究会

適用例(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 … 入力とマッチした部分の次のリビジョンまでの変更内容について， もう少し詳しく見ていきます． これは，ソースコードの差分と，それに関するコメントを 突き合わせることにより，バッファオーバランを修正したリビジョン間だったことが わかります． 2019/1/17 第136回　ソフトウェア工学研究会

適用例(3/3) コメントの参照・・・バッファオーバフローを修正 差分の参照・・・mallocの引数の修正 与えた入力に対して，類似した部分の履歴を検索できる 提示された差分と，それに関するコメントを参照することで，利用者は過去に起こったエラーの事例とその解決法を知ることができる 2019/1/17 第136回　ソフトウェア工学研究会

まとめ ソースコード修正支援手法の提案 本手法によって，手元にあるソースコードから，同様の部分の修正履歴を簡単に閲覧することが可能になった 版管理システムに蓄積された履歴をデータベース化 ソースコード片によるデータベース検索 検索結果の表示 本手法によって，手元にあるソースコードから，同様の部分の修正履歴を簡単に閲覧することが可能になった 2019/1/17 第136回　ソフトウェア工学研究会

今後の課題 データベース作成部分の改良 実際の保守作業に適用することによる本手法の有効性の評価 より意味のある単位での差分の取り出し 実際の保守作業に適用することによる本手法の有効性の評価 利用者が必要としているものを漏れなく取り出せるか？ 得られた結果のうち，実際に修正に利用できる割合はどのくらいか？ より妥当な検索結果を得るためのアラインメントスコア計算方法の改良 2019/1/17 第136回　ソフトウェア工学研究会

終

変更情報データベースの構築 あるソースファイルFの隣接する2つのリビジョン間(p~p+1)に着目 A A’ B B’ 2019/1/17 第136回　ソフトウェア工学研究会

変更情報データベースの構築 各ファイルにつき，各pから p+1までの変更部分コードを次々と取得し，データベースに登録 その他にも以下のような情報が登録される データベースの1レコード ファイル名F リビジョン番号p リビジョン番号p+1 p+1のコミット日時 p+1に対するコメント 変更部分コードの集合 注）　F，p，p+1を指定すればレコードが一意に定まる 2019/1/17 第136回　ソフトウェア工学研究会

スコアの閾値 スコアの式を前述したものに固定したとして 入力トークン数より大きい値にならないようにする L<30のとき α＝(0.6＊L)　の整数部分 L>=30 のとき α＝18 α=L とすると，入力全体と完全に一致するもののみ α=0.6＊Lのときは，検出部分のうち5分の4が一致している 入力トークン数より大きい値にならないようにする 入力トークン数が大きいときに，閾値が大きくなり過ぎないようにする 2019/1/17 第136回　ソフトウェア工学研究会

検索時間の測定 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/1/17 第136回　ソフトウェア工学研究会

検索時間の測定 特性キートークンが“if”の入力 いずれのデータベースにおいても，”ｉｆ”を含むコード片の個数が他のキートークンに比べて多い ⇒アラインメント回数大⇒検索時間大 計測環境 CPU: Pentium4 2GHz RAM: 1GB OS: FreeBSD4.5-Stable Webサーバ: Apache1.3.22 2019/1/17 第136回　ソフトウェア工学研究会

検索時間の評価 入力トークン数，データベースサイズが大きくなれば，比例的に検索時間が大きくなる 通常の使用には支障ない データベース内での出現率の高いif, else等のキートークンが特性キートークンの場合，検索時間は大 特性キートークンがそれ以外の時は，多少入力サイズが大きくても実用時間で検索可能 2019/1/17 第136回　ソフトウェア工学研究会

適用例(2/5) システム 入力 ptr = malloc(SIZE); if (ptr== NULL) { fprintf(stderr, ファイル名と リビジョン番号 入力 ptr = malloc(SIZE); if (ptr== NULL) { fprintf(stderr, "cannot allocate memory."); exit(1); } 差分についての コメント この入力をCoDSに与えると，このように検索結果が一覧表示されます （実際には元のファイル別の一覧になる） この部分に，差分についてのコメントが表示されます， さらに，ファイル名・リビジョン番号を指定することで， システム 2019/1/17 第136回　ソフトウェア工学研究会

適用例(3/5) 変更前 変更後 入力とのマッチ部分を強調表示 2019/1/17 第136回 ソフトウェア工学研究会 このように，該当するリビジョン間の差分を色付で表示します． この中の，赤い字の部分は入力としたコードとマッチした部分を示しています このようにして，入力としたソースコード片と類似した部分の過去の変更履歴を 閲覧することができます． 入力とのマッチ部分を強調表示 2019/1/17 第136回　ソフトウェア工学研究会