ソフトウェア変更作業の 見積りと支援に関する研究 大学院情報科学研究科 コンピュータサイエンス専攻 井上研究室 早瀬 康裕

研究の背景 様々な種類の大量のソフトウェアが蓄積されている 蓄積されたソフトウェアを変更する機会は多い 変更を効率的に行いたい 商用ソフトウェア オープンソースソフトウェア 蓄積されたソフトウェアを変更する機会は多い 変更を効率的に行いたい ソースコードの一部分を変更する場合を対象

ソフトウェアの変更の分類 不具合を 解決 要求を実現 使用しているソフトウェアを 変更 修正保守 予防保守 完全化保守 適応保守 調達した ソフトウェアを 変更 完成ソフトウェアを変更 カスタマイズ 部品を変更して導入 ホワイトボックス 再利用

ソフトウェア保守 ソフトウェア保守とは… 納入後，ソフトウェアに対して加えられる，フォールト修正，性能または他の性質改善，変更された環境に対するプロダクトの適応のための改訂 [36] 長期間使用されるソフトウェアでは，総所有コストのうち保守コストが半分以上となることが知られている[44][51] 保守作業にかかる労力を正確に見積る必要がある [36] S. Mamone. The ieee standard for software maintenance. SIGSOFT Softw. Eng. Notes, 19(1):75–76, 1994. [44] S. R. Schach. Software Engineering. Asken Associates, 1990. [51] S. Yip and T. Lam. A software maintenance survey. In First Asia-Pacific Conference on Software Engineering, pp. 70–79, 1994.

ソフトウェア保守の見積り 関連研究 問題点 Fioravanti ら[14] Sneed [46] Jorgensen [26] 適応保守の見積りに有用なメトリクスを提案し，実際に見積りを行った． Sneed [46] 保守による影響範囲の大きさを様々な要因で補正して，工数を見積る手法を提案した． Jorgensen [26] 実際の保守作業で様々なメトリクス値を収集し，見積りに有効なメトリクスと見積り手法を調べた 変更行数と工数との相関が高いことを明らかにした． 問題点 適用できる保守作業が限られる 保守作業の工程の早い段階で利用できない 保守工程の後半でしか得られない情報を用いるため

既存ソフトウェアのカスタマイズ 調達したソフトウェアを変更することで要求を実現 実現した機能を共有したい →オープンソースソフトウェア開発 新規にソフトウェアを開発するより低コスト 実現した機能を共有したい →オープンソースソフトウェア開発 版管理システム 変更された ソフトウェア 変更された ソフトウェア 蓄積された ソフトウェア 蓄積された ソフトウェア 蓄積された ソフトウェア 蓄積された ソフトウェア 様々な目的を持つ 世界中に分散した 開発者 変更された ソフトウェア

オープンソースソフトウェア開発支援 リポジトリマイニング ソースコードを対象としたマージ機能 版管理システムに蓄積された情報から有用な情報を抽出して開発者に提示 ソースコードを対象としたマージ機能 Westfechtel [49] 構文上のマージアルゴリズムを提案 開発者はタグ付けされたソースコードを編集する必要がある Binkley ら [8] 手続きを持つ簡単な言語を対象とした，意味的なマージアルゴリズムを提案 問題点 版管理システムに組込まれていない 専用のエディタを必要とする ソースコードのままエディタで編集できない [49] B.Westfechtel. Structure-oriented merging of revisions of software documents. In Proc. of the 3rd intl. workshop on Softw. configuation management, pp. 68–79. [8] D. Binkley et al. Program integration for languages with procedure calls. ACM Trans. Softw. Eng. Methodol., 4(1):3–35, 1995.

論文の構成 第1章: まえがき 第2章: 影響波及解析を利用した保守作業の労力見積りに用いるメトリクスの提案 [1-3] 第3章: 構文木の差分を用いた版管理システム向きマージ機能 [1-1,1-2] 第4章: むすび 概要のみ [1-1] Yasuhiro Hayase, Makoto Matsushita, Katsuro Inoue: ”Revision Control System Using Delta Script of Syntax Tree”, 12th International Workshop on Software Configuration Management (SCM 2005), pp. 133-149, Lisbon, Portugal, September 5-6, 2005 (国際会議) [1-2] 早瀬康裕, 松下誠, 井上克郎: ”構文木の差分を用いた版管理システム向きマージ機能”, 情報処理学会論文誌, Vol.48, No.2, pp. 858-867, 2007 年2 月. (学術論文) [1-3] 早瀬康裕, 松下誠, 楠本真二, 井上克郎, 小林健一, 吉野利明: ”影響波及解析を利用した保守作業の労力見積りに用いるメトリクスの提案”, 電子情報通信学会論文誌D [採録決定] (学術論文)

2章 影響波及解析を利用した 保守作業の労力見積りに用いる メトリクスの提案

背景 ソフトウェア保守作業の労力見積りは困難 保守作業に適した見積り手法がない 文書が整備されていないことが多い 熟練者の経験に依存 →作業者によって結果が異なる．客観的根拠に欠ける． 新規開発の見積り手法を流用 →変更するソフトウェアを考慮しない． 文書が整備されていないことが多い 保守作業の早い段階で見積りを行いたい →利用できる情報が少ない

研究の目的 保守労力を見積るためのメトリクス「保守ポイント」を提案 指針 限られた情報で正確な見積りを行う ソフトウェア保守作業をモデル化 必要な情報: ソースコードと，作業により変更されるモジュール 指針 ソフトウェア保守作業をモデル化 モデル上で保守作業量を反映する値を計算

一般的な保守作業 入力: プロダクトと変更要求 保守プロセスは以下の3つのステップから成る 出力: 変更されたプロダクト システム理解 変更箇所特定 テスト範囲特定 変更 テスト 変更された プロダクト 変更要求 入力: プロダクトと変更要求 保守プロセスは以下の3つのステップから成る システム理解 影響範囲 (=変更とテストが必要な範囲) の特定 変更 テスト 出力: 変更されたプロダクト 主要なコスト要因[13][15][19][38] 理解やテストの労力は，対象の複雑さに依存する[10][30]

プロダクトのモデル化 プロダクトを有向グラフとしてモデル化する 頂点はプロダクトを構成するモジュール 有向辺は，モジュール間の影響波及関係 メソッド，クラス，パッケージなど 複雑さを表す値 eff を持つ 有向辺は，モジュール間の影響波及関係 辺の起点のモジュールを変更したときに，終点のモジュールに何らかの作業が必要になる関係 影響波及の強さを表す重み wを持つ モジュール1 eff = 2 モジュール3 eff = 4 w = 0.5 モジュール2 eff = 2 w = 0.5 w = 0.7

プロダクトモデルの詳細 モジュールの複雑さ eff 影響波及の強さ w そのモジュールだけを変更するときの作業量を反映する値 本研究の実験では，McCabe の循環的複雑度と LOC(行数)を用いた 影響波及の強さ w 0 から 1 までの値 (1に近いほど影響波及が強いことを表す) 本研究の実験では定数を用いた

保守ポイント 影響範囲内の複雑さを表現するメトリクス 保守作業の労力は，主に変更されるモジュールとその影響範囲に依存 プロダクトモデル上で影響範囲の複雑さを計算

保守ポイントの計算方法 保守ポイントの計算式 Gp : プロダクトモデルのグラフ R : 保守作業によって変更されるモジュールの集合 eff(m) : モジュール m の複雑さ imp(R, m) : R によってモジュール m が受ける影響の強さ (0以上1以下) (次ページ以降で説明)

影響の強さ imp(R, m) (1/2) 経路 p = (s1, s2, s3, … , si) の重み v(p) = Πw(sj) モジュールm1が変更されたときにm2が受ける影響の強さ モジュール1 eff = 2 モジュール3 eff = 4 w = 0.5 モジュール2 eff = 2 0.5×0.7=0.35 w = 0.5 w = 0.7

影響の強さ imp(R, m) (2/2) 変更要求 R からモジュール m への影響の強さ 多くのモジュールから影響を受けるほど，理解およびテストしなければならない割合が増える

保守ポイントの計算例 下のプロダクトモデルで， R={モジュール1, モジュール2} であるときの保守ポイントの値 eff(モジュール1) + eff(モジュール2) + (1-(1-0.5)×(1-0.7))×eff(モジュール3) = 2 + 2 + 0.85×4 = 7.4 モジュール1 eff = 2 モジュール3 eff = 4 w = 0.5 モジュール2 eff = 2 w = 0.5 w = 0.7

評価実験 目的 実験設定 保守ポイントの値と労力との関係を調査 被験者： 情報科学研究科の大学院生 6 人 作業対象： 酒屋問題 [50] のJavaによる実装 8 クラス， 25 メソッド， 309 行 作業内容 欠陥修正 2 件，機能追加 3 件 各被験者が5件の作業を終えるまでの時間 1時間43分 ～ 5時間2分 →個々の作業に費やした時間の割合を労力の値とする [50] 山崎. 共通問題によるプログラム設計技法解説. 情報処理, 25(9):934–935, 1984.

評価1: 相関の調査 相関係数を計算 保守ポイントの計算方法 →保守ポイントは単純和より労力との相関が高い 労力 メトリクス (保守ポイント，単純和(変更されたメソッドの複雑度の和)，変更行数) 保守ポイントの計算方法 頂点: メソッド 辺の重み: 定数 0.3 頂点の複雑さ: McCabe の循環的複雑度と LOC 保守ポイント [McCabe] 単純和 [LOC] 変更 行数 労力との 相関係数 0.82 (<0.01) 0.73 (<0.01) 0.77 (<0.01) 0.65 (<0.01) 0.87 (<0.01) 符号付 順位和検定 二乗誤差: 101 (<0.01) MRE: 105 (<0.01) 二乗誤差: 95 (<0.01) MRE: 86 (<0.01) →保守ポイントは単純和より労力との相関が高い

評価2: クロスバリデーション 見積り精度を擬似的に評価 評価基準 小さいほど良い 大きいほど良い 30件のデータをランダムに3群に分割 2群を線型回帰分析の学習に，残りの1群を見積りに使用 学習・見積りに用いる群を入れ替えて，全ての組み合わせで実行 評価基準 MAE: 絶対誤差の平均 MMRE: 相対誤差の絶対値の平均 PRED(25): 相対誤差が 25% 以下である割合 PRED(50): 相対誤差が 50% 以下である割合 小さいほど良い 大きいほど良い 保守ポイント [McCabe] 単純和 [McCabe] 保守ポイント [LOC] 単純和 [LOC] 変更行数 MAE 0.07840 0.09270 0.09405 0.1177 0.07868 MMRE 0.9616 1.427 1.263 1.766 0.8266 PRED(25) 0.3667 0.3000 0.3333 0.1667 PRED(50) 0.6667 0.6000 0.5000

2章のまとめ 保守作業の労力見積りのためのメトリクスを提案 保守対象のソフトウェアプロダクトをモデル化 モデル上での影響範囲内の複雑さから計算 メトリクスと労力との相関を評価 他のメトリクスよりも労力と高い相関を持つ

3章 構文木の差分を用いた 版管理システム向きマージ機能

版管理システム 機能 ほとんどのオープンソースソフトウェア開発で使われている 例: CVS, subversion ソースコードやドキュメントなどの開発履歴を保存 複数人による同時開発をサポート ほとんどのオープンソースソフトウェア開発で使われている 例: CVS, subversion

版管理システムを用いた複数人での開発 X2 X3 取得 X リポジトリ X1 X 編集 格納 開発者Ａ X1 取得 最新版 (X1)の取得 このまま格納すると 開発者Aの変更が失われる 開発者Ｂ X X2 版管理システム によるマージ X3 編集

問題 既存の版管理システムは，マージを行単位で行っていた 行単位のマージは，不正確な場合がある 同じ行が変更されていると，衝突しなくて良い変更が衝突する 衝突すべき変更が，行が違うことにより見逃される システムがマージに失敗したときは，開発者が手で直さねばならず，負担となっている

ソースコードの構造を考慮したマージ 木構造の差分計算とマージを行う ソースコードを解析し，構文木に基いた木構造のデータを作成する 2つの木の差分を編集操作の列(編集スクリプト)として計算する 編集スクリプトを適用対象の木に適用する. 差分の計算元 差分の計算先 編集 スクリプト ソースコード ソースコード ソースコード ソースコード 適用対象 マージ結果

評価実験 提案手法が有効に働くかを検証した サンプルコードに対する適用 実際の開発履歴に対する擬似的な適用 典型的な同時変更を作成して動作を確認 実際の開発履歴に対する擬似的な適用 オープンソースソフトウェアのリポジトリから，マージが行なわれたと考えられる事例を取得 行単位のマージと提案手法とで比較

実際の開発履歴に対する擬似的な適用 実際のリポジトリからマージが行なわれたと考えられる事例を取得 提案手法と行単位の手法とを比較 結果 対象リポジトリ Eclipse プロジェクト（22606 ファイル，162683リビジョン） Jakarta プロジェクト（19420 ファイル， 103358 リビジョン） 84件のマージ事例を取得 提案手法と行単位の手法とを比較 提案手法では，出力に正しいマージ結果が含まれれば成功とみなした 結果 行単位のマージ 件数 提案手法 成功 71 失敗 13 9 4

行単位のマージが失敗した場合の詳細 →提案手法は 1 件を除いて正しい結果を出力できた 行単位のマージが失敗した原因 件数 提案手法 同じ行への空白文字の追加削除 4 成功 意味的な変更と整形 1 改行コードの変更 重なりあった編集 2 後の変更が最初の変更を上書き 失敗 意味的な衝突 編集に失敗したファイルの格納 →提案手法は 1 件を除いて正しい結果を出力できた

むすび 既存のソフトウェアに対する変更を効率的に行う方法を提案 保守労力の見積りメトリクス「保守ポイント」 保守作業の早い段階で得られる情報から計算可能 労力と高い相関を持つことを確認 同時に更新されたソースコードを木構造によってマージする手法 実際のソフトウェア開発のデータでも有効に動作することを確認

版管理システムを用いたソフトウェア開発 自由に 書換えられる ファイル リポジトリ リポジトリから ファイルを取得 開発履歴を 保存する データベース 自由に 書換えられる ファイル リポジトリから ファイルを取得 開発者 編集 新しいファイル ファイル 編集されたファイル リポジトリへ格納

問題点1 不要な衝突 開発者 A と B が同じファイルを編集している マージ失敗 同じ行を編集すると変更点が衝突 問題点1 不要な衝突 開発者 A と B が同じファイルを編集している 同じ行を編集すると変更点が衝突 行が同じでも衝突するとは限らない マージ失敗 int refs=0; int refs; int reference_count=0; int reference_count;

問題点2 衝突の見逃し 開発者 A と B が同じファイルを編集している 不正なマージ結果 衝突すべき変更を，行が違うために見逃す 問題点2 衝突の見逃し 開発者 A と B が同じファイルを編集している 衝突すべき変更を，行が違うために見逃す A が変数を削除 B が削除された変数を利用するコードを追加 int num, sum; int num, sum; ： avg = sum/num; int num, sum, avg; int num, sum, avg; ： avg = sum/num; 不正なマージ結果

研究の目的 精度の高いマージシステムを作り，開発者の負担を軽減する マージ時の不要な衝突を避ける マージによって引き起こされる問題を減らす 行よりも細かい単位でマージ処理を行う マージによって引き起こされる問題を減らす 変数の利用と定義が対応していることをチェック

1. ソースコードをツリーに変換 ソースコードを構文解析し，ツリーにする ツリーの頂点に ID を付ける ツリーの頂点には文字列が格納される ツリーから元のソースコードに戻せるように，空白文字の頂点も作る ツリーの頂点に ID を付ける ID の付けかた 直前のバージョンと頂点の対応を計算して， 対応すると判断された頂点同士には同じ ID を付ける 頂点の対応については FastMatch アルゴリズム [11] を改変したものを使用 変数を利用している部分から，定義している部分へリンクを張る Block { int i; i; } 空白 Declare 空白 Statement 空白 int 空白 i variable

2. ツリーの差分計算 EditScript アルゴリズム [11] を採用 二つの木の差分を，編集操作の列(編集スクリプト)として求める近似アルゴリズム 編集操作 頂点の追加: insert(新ID, 文字列, 親ID, index) 葉頂点の削除: delete(ID) 頂点に格納された文字列を更新: update(ID, 新文字列) 部分木を移動: move(ID, 移動先の親ID, index) 編集操作にはコストが定義されている insert のコスト = delete のコスト = moveのコスト =1 update のコストは変更前後の値によって 0以上 2以下の値 提案手法では (1 – 文字列の共通部分の長さ*2/書換え前後の文字列の長さの和)*2 時間計算量 O(ne+e2) (e は差の大きさ) 良い近似を得るための条件: e << n

3. マージ ツリー A とツリー B の差分スクリプト S を A でないツリー C に適用することで実現 問題:編集操作は引数となる ID を持つ頂点が ツリー C に存在するとは限らない 類似した頂点を探す 親や子が共通 兄弟が共通 よく似た頂点が見つかれば代用する 見つからなければ編集操作を適用しない

どれが正しいかをシステムが決めることは出来ない マージ結果の選択 類似頂点の探し方には，複数の方法がある マージ結果は複数存在しうる どれが正しいかをシステムが決めることは出来ない 解決方法 複数のマージ結果が得られた場合には，適用できた操作の数で整列し，開発者が選択する

マージの例 C1 C2 A B 0 if 0 if update(6, i) move(5, 1, 0) delete(4) 1 then 2 doA 8 doC 9 z 3 x 4 else 8 doA C1 C2 A B 0 if 0 if update(6, i) move(5, 1, 0) delete(4) 1 then 4 else 1 then 2 doA 5 doB 5 doB 2 doA 3 x 6 y 代用できる 頂点がない 6 i 3 x 頂点8がやや類似しているため，操作を適用しない場合と，代用して操作を適用した場合の 2つのツリーを作る C 0 if D1 D2 D3 update(6, i) move(8, 1, 0) delete(4) update(6, i) move(5, 1, 0) delete(4) update(6, i) move(5, 1, 0) delete(4) 0 if 0 if 0 if Consider tree A and B. <Enter> The delta from tree A to tree B is this script. <Enter> There is another tree C. <Enter> Please consider applying this script to tree C. <Enter> The target of the operation “update” is node 6. <LP> But no similar node is in tree C. So the update operation can’t be applied. <Enter> Next operation “move” targets node 5, and node 8 in tree C is a little similar to node 5. So the system builds two trees one with the operation applied, and one without the operation applied. <Enter> The last operation “delete” targets node 4. But the node 4 in tree C2 has child node. So the system makes both of trees to which the operation is not applied and the sub-tree whose root is node 4 is deleted. As a result of application, three trees D1 to D3 are generated. The developer chooses one of them. 1 then 4 else 1 then 1 then 1 then 4 else 8 doC 2 doA 2 doA 2 doA 8 doC 2 doA 8 doC C2 の頂点4は子頂点を持つため，操作を適用しない場合と，頂点4を根とする部分木を削除する場合の 2つのツリーを作る 9 z 3 x 3 x 3 x 9 z 3 x 9 z 開発者が1つを選択する

システムを使って解決する問題1 行単位のマージでは，同じ行の編集で衝突していた マージ失敗 int refs=0; int refs; int reference_count=0; int reference_count;

問題1 に提案手法を使った場合 マージ成功 元の行 ソースコード に変換 Declare int refs = Declare Declare Declare int reference_count = int refs Declare ソースコード に変換 int reference_count int reference_count=0;

システムを使って解決する問題2 行単位のマージでは，宣言されていない変数を使う問題を見逃していた 不正なマージ結果 int num, sum; int num, sum; ： avg = sum/num; int num, sum, avg; int num, sum, avg; ： avg = sum/num; 不正なマージ結果

問題2 に提案手法を使った場合 変数の参照先が無いことを検知 Declare List int num sum Declare List リンク切れ int num sum variable int num sum avg Declare List int num sum avg variable

システムの実装 既存の版管理システム subversion を拡張し，提案するマージ機能を実現した subversion よりよい CVS を目標として新規開発されている版管理システム 特徴 サーバ・クライアント型システム クライアント側での差分計算・マージ処理 ソースコードをツリーに変換した状態でリポジトリに格納 ツリー表現には XML を使う 拡張で開発者の作業手順を変更しない

システムの概要 XMLのマージ機能 ソースコードとXMLの変換 subversion クライアント 差分計算 制約検査して FMES, xmdiff 制約検査して 違反数で整列 差分適用 subversion サーバ XMLのマージ機能 リポジトリ 開発者 ソースコードとXMLの変換 ソースコードに変換 頂点対応の計算 (FMESの前段階) XMLへ変換

取得と格納 取得時の処理 格納時の処理 subversion クライアント 差分計算 制約検査して FMES, xmdiff 差分適用 違反数で整列 差分適用 開発者 subversion サーバ 取得時の処理 格納時の処理 リポジトリ ソースコード 頂点 ID 付き XMLファイル 取得した XMLファイル 編集 ソースコードに変換 頂点対応の計算 (FMESの前段階) 編集した ソースコード 頂点ID無し XMLファイル XMLへ変換

マージ マージ時の処理 subversion クライアント 開発者 差分計算 制約検査して FMES, xmdiff 差分適用 違反数で整列 サーバ 差分 マージ結果 のXML マージ結果の XML(複数) マージ結果 のXML マージ結果の ソースコード (整列済) 最新版の XMLファイル リポジトリ マージ結果 のXML マージ結果の XML(整列済) 頂点 ID 付き XMLファイル 取得した XMLファイル 開発者に提示 ソースコードに変換 頂点対応の計算 (FMESの前段階) 編集した ソースコード 頂点ID無し XMLファイル XMLへ変換

実験結果: マージに要した時間

まとめと今後の課題 まとめ 今後の課題 既存の版管理システムの問題点を提示 解決法としてソースコードの木構造によるマージを提案 実験により提案手法の有効性を確認 今後の課題 ソースコード以外のドキュメント形式への対応