オブジェクトの動的支配関係解析を 用いたシーケンス図の縮約 井上研究室 伊藤芳朗 井上研究室の伊藤です． 「オブジェクトの動的支配関係解析を用いたシーケンス図の縮約」というタイトルで 発表を始めます． よろしくお願いします． 2008/2/22 特別研究発表会

概要 背景 提案手法 実験 実行履歴からのシーケンス図の生成 オブジェクトの動的支配関係解析を用いたシーケンス図の縮約 提案手法を実装したシステムを作成し実行履歴の圧縮率を調べた 発表の概要はこのようになっています． まず背景として，実行履歴からのシーケンス図の生成について説明します． 次に，オブジェクトの動的支配関係解析を用いたシーケンス図の縮約手法を 説明します． 提案手法では動的な実行履歴中のオブジェクトの支配関係を利用した グループ化手法を提案します． 最後に提案手法を実装したシステムを作成し，適用実験を行いましたので その結果を報告します． 特別研究発表会 2008/2/22

背景 オブジェクト指向プログラムの解析 プログラムの実行履歴を取得し，UMLのシーケンス図として可視化 実行時の動作を理解するのは難しい 動作の理解には実行履歴等の動的情報の解析が有効 プログラムの実行履歴を取得し，UMLのシーケンス図として可視化 時系列にそったオブジェクト間のメソッド呼び出し関係 プログラムの実行時に決定される情報 本研究の背景を説明します． 背景にはオブジェクト指向プログラムの解析があります． オブジェクト指向プログラムは動的に決定される要素が多く， 実行時の動作を理解するのは難しいのですが， その動作を理解するには実行履歴などの動的情報の解析が有効です． そこで，プログラムの実行履歴を取得し，UMLのシーケンス図として 可視化する手法があります． シーケンス図を使うことで，時系列に沿ったオブジェクト間のメソッド呼び出し関係や プログラムの実行時に決定される情報が分かります． 特別研究発表会 2008/2/22

シーケンス図 オブジェクト間のメッセージ通信を時系列に沿って表現する システムの設計時に作成される プログラムの動作の理解にも有効 B C D E A F G H I シーケンス図の説明をします． シーケンス図は，図の上部に横方向にオブジェクトを並べ， 縦方向は時間の経過を表します． 横方向の矢印はメッセージ通信を表していて，送信元から送信先に矢印を引きます． メッセージを受けたオブジェクトが処理している区間は長方形で表します． 処理が終わったときに，戻り値がある場合は送信元のオブジェクトまで 矢印を引きます． このシーケンス図は本来システムの設計時に作成されますが， オブジェクト間の動作を示すため，プログラムの理解にも有効です． 特別研究発表会 2008/2/22

シーケンス図生成システム Amida 対象プログラムの実行履歴を取得し，シーケンス図を生成するシステム シーケンス図のループや再帰呼び出しを圧縮する機能を持つ ここで実行履歴からシーケンス図を生成する例として， われわれの研究室が開発したシーケンス図生成システムAmidaの紹介をします． AmidaはJavaプログラムを対象としたシステムで，プログラムを動的解析し， 実行履歴を取得します．そして，その実行履歴からシーケンス図を生成します． また生成したシーケンス図を解析し，ループや再起呼び出しとなる部分を 圧縮し表示する機能を持ちます． 谷口， 石尾， 神谷， 楠本， 井上: “プログラム実行履歴からの簡潔なシーケンス図の作成手法” ， コンピュータソフトウェア，vol.24，No.3 (2007)，pp.153-169． 特別研究発表会 2008/2/22

実行履歴から図を 生成する際の問題点 プログラムの実行履歴のサイズは巨大 解析した結果も巨大になる 出現オブジェクトの数が多いことが原因の1つ シーケンス図が横長になってしまう 外部から参照されないオブジェクトをグループ化することでシーケンス図を簡潔にする ただし，実行履歴から図を生成する際には プログラムの実行履歴のサイズが巨大になるという問題点があります． そのため，解析した結果も巨大なものとなり， 人が見るのに向かなくなってしまいます． その原因の1つに，シーケンス図に出現するオブジェクトの数が多いことが 挙げられます． オブジェクトの数が多いほどシーケンス図は横長なものとなり， 矢印の先を追うのが大変になってしまいます． そこで外部から参照されないオブジェクトをグループ化することで シーケンス図を簡潔にする手法を提案します． 特別研究発表会 2008/2/22

提案手法 オブジェクトをグループ化し，グループ間のメッセージ通信のみをシーケンス図に表示する １グループを１オブジェクトとするため表示するオブジェクト数が減る グループ内のメッセージ通信が表示されないため表示するメッセージ通信の数が減る 提案手法の説明に入ります． 実行履歴からシーケンス図を生成する際に シーケンス図に出現するオブジェクトをグループ化し， グループ間のメッセージ通信のみをシーケンス図に表示します． 1グループを1オブジェクトとして表示することで， シーケンス図に出現するオブジェクトの数が減り， シーケンス図が横長になるのを防ぎます． またグループ間のメッセージ通信のみを表示するため， 表示するメッセージ通信の数も減ります． これはシーケンス図が縦長になるのを防ぎます． 特別研究発表会 2008/2/22

グループ化の条件 グループには代表となるオブジェクトを設定 グループ外からは代表オブジェクトにメッセージ通信を行うようにする 1つのグループも１つのオブジェクトとみなして階層的なグループ化を行う グループ化により，外部から参照されないオブジェクトを隠すために， グループ化の条件をこのように設定しました． グループには代表となるオブジェクトを1つ設定します． グループ外のオブジェクトは代表オブジェクトへのメッセージ通信のみ可能で グループ内のほかのオブジェクトへはメッセージ通信が発生しないようにグループを 決定します． １つのグループも１つのオブジェクトとみなし，階層的なグループ化を行います． このようなグループを作ることで，全体の情報を損なわないで， 処理の流れを把握できる簡潔なシーケンス図を生成することができます． 全体の整合性を保ったまま シーケンス図を縮約できる 特別研究発表会 2008/2/22

グループ化の例 特別研究発表会 2008/2/22 B F A B C D E A F G H I グループ化の例を示します． このようなシーケンス図があった場合， グループの外部からメッセージ通信を受けてはいけないので， （クリック） オブジェクトB,C,D,EはオブジェクトBを代表としたグループに， オブジェクトF,G,H,IはオブジェクトFを代表としたグループになります． ここからグループ間のメッセージ通信のみ取り出すので，（クリック） グループ化した後のシーケンス図はこのように縦も横も小さくなります このグループ化の判断には支配関係解析を用います． 特別研究発表会 2008/2/22

支配関係解析 グラフから支配関係木を求めるアルゴリズム[1] 入口が1つの有向グラフに適用可能 頂点aに到達するどの経路も必ず頂点bを通るとき，bはaを支配するという 4 1 2 3 5 6 8 7 6 4 8 3 7 5 2 1 支配関係解析とは，グラフから支配関係木を求めるアルゴリズムです． 入り口が1つである有向グラフに適用できます． ある頂点aに到達するどの経路も必ず頂点bを通るとき bはaを支配しているといいます． この左のグラフの場合， 7の頂点は5を通る経路と6を通る経路の2つの経路があるため， 7を支配する頂点は3になります． この支配関係は木構造になります． 本手法ではこのアルゴリズムを用いてグループ化を実現します 呼び出し関係グラフ 支配関係木 [1] Cooper, K. D., Harvey, T. J. and Kennedy, K.: A Simple, Fast Dominance Algorithm. http://www.cs.rice.edu/~keith/EMBED/ 特別研究発表会 2008/2/22

動的支配関係解析を用いた グループ化 実行履歴から動的な呼び出し関係のグラフを作る グラフから支配関係木を求める 親を代表オブジェクト，子をメンバーとしてグループを設定する グループ外からは グループ内のオブジェクトを 呼び出せない 階層的なグループ化が可能 6 4 8 3 7 5 2 1 グループ化を行うとき， まず実行履歴から呼び出し関係のグラフを作ります． 次にそのグラフに支配関係解析を適用して，支配関係木を求めます． 支配関係木の親となる頂点を代表， 子となる頂点をメンバーとしてグループを設定します． 代表となる頂点も別の親を持つため，階層的なグループ化が行えます． この支配関係はオブジェクト間の呼び出し関係に基づいているため 例えば，6から8へ行くような グループ外からグループ内のオブジェクトへのメッセージ通信は 存在しません． 特別研究発表会 2008/2/22

実装 実行履歴を解析し，グループ間のメッセージ通信のみ取り出すツールを作成 一番外側のグループ内のメッセージ通信以外は全て取り除く 取り出した実行履歴をAmidaに入力し，シーケンス図を生成 対象 プログラム 作成した ツール Amida 本手法を実装しました． 対象となるプログラムから取得した実行履歴を解析し， オブジェクトのグループ化を行い，一番外側にできるグループ内の メッセージ通信のみを取り出し，出力するツールを作成しました． シーケンス図の生成には先ほど紹介したAmidaを使用します． 実行履歴 簡略化されたシーケンス図 特別研究発表会 2008/2/22

実験概要 実験の目的 縮約の効果がどれほどあるか調べる 実行履歴ごとに効果の違いがあるかを調べる 実験対象 図書管理システム 実験方法 学生4グループが同じ設計仕様に基づいて作成した4個のシステム(A,B,C,D) 同じ手順で実行した実行履歴 実験方法 作成したツールを各実行履歴に対して適用する 出力された実行履歴の出現オブジェクト数とメッセージ通信数を取得し，適用前と比較する 今回行った実験の説明をします． 実験の目的は， 提案手法がどれぐらい縮約できるのかを調べることと， 実行履歴ごとの効果の違いを調べることです． そのために実験対象として図書管理システムというアプリケーションの実行履歴を 使用しました． このシステムは同じ設計仕様に基づいて学生4グループが違う実装で作成し， 全て同じ手順で実行したときの実行履歴を取得したものです． 実験方法は，実装したツールで各実行履歴に対して手法を適用し， 適用の前後で実行履歴に出現するオブジェクトの数とメッセージ通信の数を 比較しました． 特別研究発表会 2008/2/22

図のサイズの変化 出現オブジェクト数の変化 メッセージ通信数の変化 特別研究発表会 2008/2/22 70.9% 71.5% 68.4% 3.0% 60.4% 59.4% 58.3% 2.8% 実験結果です． 左側のグラフは，シーケンス図を生成した際に図に並ぶオブジェクトの数を表し， 右側のグラフは，グループ間のメッセージ通信の数を表します． 2つのグラフの青色の部分はツールの適用前で， 赤色の部分はツールの適用後を表しています． システムAでは，出現オブジェクト数が適用後は適用前の60.4％に， メッセージ通信数は70.9％にへりました． しかし，システムDは，出現オブジェクト数が2.8％に，メッセージ通信数が3％に減り， 他と極端な差が出ています． 次で具体的にどのように図が縮約したのかを説明します． 特別研究発表会 2008/2/22

実際の図の変化 適用前 適用後 特別研究発表会 2008/2/22 この図が縮約する前のシーケンス図です． 図のうち青色になっている部分を縮約します． 赤枠で囲われたオブジェクトのうち，一番左のオブジェクトを 代表オブジェクトとしてグループ化します．（クリック） このように代表オブジェクトへのメッセージ通信のみとなり 先ほどの図が縦にも横にも縮約されます． （クリック） この図はシステムAのシーケンス図を縮小した図です． 左側が適用する前のもので，右側が適用後のものです． 横方向が約60%に圧縮されています． この図からはわかりにくいですが，縦方向も同様に圧縮されています． 特別研究発表会 2008/2/22

オブジェクトの比較 隠れたオブジェクト 残ったオブジェクト 一時オブジェクト 局所的に使われているオブジェクト 例：検索実行時に作成されるオブジェクト 残ったオブジェクト 動作制御を行うオブジェクト インターフェイス関連のオブジェクト 一部のデータオブジェクト 同じ処理が繰り返えされていた 適用の前後でオブジェクトの比較を行いました． 局所的に使われていたり，特定のオブジェクトしか呼び出さないような オブジェクトは隠すことができました． 使用した実行履歴では，検索機能の実行時に作成される 一時オブジェクトはグループ化され，シーケンス図に表示されなくなりました． 逆に，残ったオブジェクトとしては， 動作制御を行うオブジェクトとインターフェイス関連のオブジェクトが 残りました． これらのオブジェクトはこのシステムの重要な部分なので， シーケンス図に残ったことから，いい結果が出たと考えられます． ただし，一部のデータオブジェクトも残っていました． このオブジェクトへの処理は同じ処理が繰り返されている場合が多く， このオブジェクトも隠せたらより見やすいシーケンス図になったと思います． 特別研究発表会 2008/2/22

考察 支配関係解析の効果は実行履歴によって大きく左右される 実行履歴中のオブジェクト数やメソッド呼び出し数が近いものでも結果に差が出る 全てのオブジェクトが1つのグループになってしまうことがあった 全体の動きが把握できない 実装に問題がある 図上で階層的にグループ化の解除をすることで対応できる 実験の考察です． 圧縮率は実行履歴によって大きく左右されることを確認しました． 極端な場合だと，全く圧縮できなかった場合と 逆に圧縮しすぎて1つのグループになってしまった場合がありました． その場合，グループ内の動きが分からないため動作の把握ができなくなって しまいました． ただし，これは実装の問題で， 図上で階層的にグループ化の解除をすることで対応できると考えられます． 特別研究発表会 2008/2/22

まとめ まとめ 今後の課題 動的支配関係解析を用いたオブジェクトのグループ化によりシーケンス図を縮約する手法を提案した 実験を行い，実際に縮約できることを確認した 今後の課題 グループ化とグループ化解除ができるようにする グループ内のメッセージ通信を削除しているため階層化が無意味になっている 他の手法と組み合わせてシーケンス図の縮約ができるようにする Amidaのループ圧縮手法など 最後にまとめます． 動的支配関係解析を用いたオブジェクトのグループ化によりシーケンス図を 縮約する手法を提案しました 実験を行い，実際に圧縮できることを確認しました 今後の課題として グループ化とグループ化の解除ができるようにし， 極端なグループ化がおきた場合や，グループ内の動作を確認したい場合にも その場で確認できるようにします． 他の手法と組み合わせて，よりシーケンス図を縮約できるようにします 例えばAmidaのループ圧縮と組み合わせることで， さらにシーケンス図を縮約することが可能になります． この2つを行うために，本手法をAmidaに実装することを予定しています． これで発表を終わります． 特別研究発表会 2008/2/22