オブジェクトの動的支配関係解析を用いた シーケンス図の縮約手法の提案 大阪大学　大学院情報科学研究科 ○伊藤芳朗　渡邊結　石尾隆　井上克郎 大阪大学大学院情報科学研究科の伊藤です． 「オブジェクトの動的支配関係解析を用いたシーケンス図の縮約手法の提案」というタイトルで 発表を始めます． よろしくお願いします． 2008/06/19

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

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

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

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

実行履歴から図を 生成する際の問題点 プログラムの実行履歴のサイズは巨大 実験に使用した実行履歴 解析した結果も巨大になる メソッド呼び出し数3300 オブジェクト数320 解析した結果も巨大になる 一画面に表示できるメソッド呼び出しとオブジェクトはそれぞれ10程度 呼び出し元と呼び出し先のオブジェクトを一画面内に収めることができない ただし，実行履歴から図を生成する際には プログラムの実行履歴のサイズが巨大になるという問題点があります． 今回の実験で使用した実行履歴は短いシナリオを実行したものですが， メソッド呼び出し数が3300個，オブジェクト数が320個もありました． 他にもメソッド呼び出し数が1万個にも及ぶような実行履歴もあります． そのため，解析した結果も巨大なものとなってしまい， 結果を見るのも困難になってしまいます． 一画面にシーケンス図を表示しようとした場合， メソッド呼び出しとオブジェクトはそれぞれ10個程度しか表示することができません． また，呼び出し元オブジェクトと呼び出し先オブジェクトが離れている場合， メッセージ通信を一画面に収めることができなくなります． 2008/06/19

関連研究 実装の詳細のメソッドの自動フィルタリング[2] 概要を把握するための縮小表示[3] ユーティリティであるメソッドを自動で判別しシーケンス図から除去する シーケンス図上での呼び出し関係が途切れる 概要を把握するための縮小表示[3] 詳細な動作については把握できない 実行履歴の問題点に対する関連研究としてこのようなものがあります． 実装の詳細となるメソッドのみを取り出して要約を表示する手法というものがあり， それはユーティリティであるメソッドを自動でシーケンス図から除去することで 簡潔なシーケンス図を生成することができます． しかしこの手法では，シーケンス図上で呼び出し関係が途切れて表示されてしまいます． 他にも概要を把握するために縮小表示を作成する手法があります． ただし，縮小表示を作成するため詳細な動作は把握できないという 問題点があります． [2]Hamou-Lhadj, A. and Lethbridge, T.: Summarizing the Content of Large Traces to Facilitate the Understanding of the Behaviour of a Software System, Proceedings of the 28th International Conference on Software Engineering, pp.181-190, 2006. [3] Pauw, W. D., Jensen, E., Mitchell, N. Sevitsky, G., Vlissides, J. M. and Yang, J.: Visualizing the Execution of Java Programs. Revised Lectures on Software Visualization, International Seminar, pp.151-162, 2002. 2008/06/19

オブジェクトのグループ化 グループ間のメッセージ通信のみをシーケンス図に表示 全体の整合性を保ったまま シーケンス図を縮約する １グループを１オブジェクトとするため表示するオブジェクト数が減る グループ内のメッセージ通信が表示されないため表示するメッセージ通信の数が減る そのため本手法ではオブジェクトのグループ化によって シーケンス図の縮約を行います． 実行履歴からシーケンス図を生成する際に シーケンス図に出現するオブジェクトをグループ化し， グループ間のメッセージ通信のみをシーケンス図に表示します． 1グループを1オブジェクトとして表示することで， シーケンス図に出現するオブジェクトの数が減り， シーケンス図が横長になるのを防ぎます． またグループ間のメッセージ通信のみを表示することで， 表示するメッセージ通信の数も減ります． これはシーケンス図が縦長になるのを防ぎます． この方法で全体の整合性を保ったまま シーケンス図を縮約します． 全体の整合性を保ったまま シーケンス図を縮約する 2008/06/19

グループ化の例 2008/06/19 B F A B C D E A F G H I ここでグループ化の例を示します． このシーケンス図では， オブジェクトAはオブジェクトBとFだけを呼び出しています オブジェクトBはオブジェクトCDEを呼び出しています． オブジェクトFはオブジェクトGHを呼び出し， オブジェクトGHはオブジェクトIを呼び出します． （クリック） この場合， オブジェクトCDEはオブジェクトBを親とするグループに オブジェクトGHIはオブジェクトFを親とするグループにします． ここからグループ内の子供となるオブジェクトと グループ内のメッセージ通信を隠します． グループ化した後のシーケンス図はオブジェクトBFへのメッセージ通信のみを 表示するためシーケンス図は縦にも横にも縮約できます． このようにグループ化を行い，グループ内のオブジェクトを 隠してしまうことでシーケンス図の縮約ができます． 2008/06/19

提案するグループ化の条件 グループには代表となるオブジェクトを設定 グループ外からは代表オブジェクトにメッセージ通信を行うようにする １つのグループも１つのオブジェクトとみなして階層的なグループ化を行う 本手法ではグループ化の条件をこのように設定します． グループには代表となるオブジェクトを1つ設定します． グループ外のオブジェクトは代表オブジェクトへのメッセージ通信のみ可能で グループ内のほかのオブジェクトへはメッセージ通信が発生しないようにグループを 決定します． １つのグループも１つのオブジェクトとみなし，階層的なグループ化を行います． このようなグループを作ることで，全体の情報を損なわないで， 処理の流れを把握できる簡潔なシーケンス図を生成することができます． このグループ化を自動的に行うために支配関係解析を用います． 自動的にグループ化を行うために 支配関係解析を用いる 2008/06/19

支配関係解析 グラフから支配関係木を求めるアルゴリズム[4] 入口が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になります． この支配関係は木構造になります． 本手法ではこのアルゴリズムを用いてグループ化を行います． オブジェクトの 呼び出し関係グラフ 支配関係木 [4] Cooper, K. D., Harvey, T. J. and Kennedy, K.: A Simple, Fast Dominance Algorithm. http://www.cs.rice.edu/~keith/EMBED/ 2008/06/19

グループ化の手順(1/2) 実行履歴から動的なオブジェクト間の呼び出し関係のグラフを作る スレッドごとにグラフを作る mainメソッドを根とする 呼び出し元オブジェクトから呼び出し先オブジェクトへ辺を引く staticなオブジェクトは個別の仮オブジェクトとする 呼び出し元に関連性がない可能性があるため グループ化を行う手順を説明します． グループ化を行うとき， まず実行履歴から動的なオブジェクト間の呼び出し関係のグラフを作ります． このときグラフはスレッドごとに作ります． Javaアプリケーションではエントリポイントとなるmainメソッドが存在するため Mainをグラフの根とします． グラフはオブジェクト間の呼び出し関係を表すので， 呼び出し元オブジェクトから呼び出し先オブジェクトへと辺を引きます． このとき，staticなオブジェクトの場合，呼び出されるごとに 個別の仮オブジェクトとしてグラフに追加します． これはstaticなオブジェクトは呼び出し元に関連性がない可能性があるためです． このようにオブジェクト間の呼び出し関係のグラフを作ります． 2008/06/19

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

シーケンス図の縮約の例 C B E H I D G A F B F A 支配関係木 D E C H I G オブジェクト間の CDE F GHI A B C D E A F G H I C B E H I D G A F 呼び出し関係グラフ オブジェクト間の B F A 支配関係木 D E C H I G 先ほど使用したシーケンス図を使用してグループの決定と シーケンス図の縮約の例を示します このシーケンス図を元にオブジェクト間の呼び出し関係グラフを作ります． （クリック） オブジェクトAはオブジェクトBとFを呼び出すため オブジェクトAからBFへ辺を引きます． 他のオブジェクトもシーケンス図の呼び出し関係に基づいて 辺を引いて，オブジェクトの呼び出し関係グラフを作ります． 次にグラフから支配関係木を作ります． オブジェクトBとFを呼び出すのはオブジェクトAのみなので， オブジェクトAがオブジェクトBとFを子供とします． 他のオブジェクトも同様に木構造を作ります． ただし，オブジェクトIはオブジェクトGとHから呼び出されるため， オブジェクトGHではなく，その親であるオブジェクトFが支配するため オブジェクトFの子供となります． できた支配関係木のうち親となるオブジェクトと子供となるオブジェクトを 1グループとします． このとき親となるオブジェクトがそのグループの代表となります． オブジェクトBを親とするグループとオブジェクトFを代表とするグループの 2つができます． このとき，オブジェクトAを親，オブジェクトBFを子供とするグループも できるのですが，これをグループ化してしまうと 1つのグラフが1つのグループとなり，シーケンス図が1つのメッセージ通信だけに なってしまうため，グループ化しません． こうしてできたグループをもとに， シーケンス図の上部にはグループの代表となるオブジェクトだけを表示し， 代表オブジェクトへのメッセージ通信のみを取り出して表示することで， 縮約したシーケンス図を作ります． 2008/06/19

実装 実行履歴を解析し，グループ間のメッセージ通信のみ取り出すツールを作成 根であるmainメソッドに当たる頂点とその直接の子となるグループのみを取り出す 取り出した実行履歴をAmidaに入力し，シーケンス図を生成 対象 プログラム 作成した ツール Amida 本手法を実装しました． 対象となるプログラムから取得した実行履歴を解析し， オブジェクトのグループ化を行い， 根であるmainメソッドに当たる頂点とその直接の子となるグループのみを 取り出すツールを作成しました． シーケンス図の生成には先ほど紹介したAmidaを使用します． 実装したツール使用して実験を行いました． 実行履歴 簡略化されたシーケンス図 2008/06/19

実験概要(1/2) 実験の目的 実験対象 縮約の効果がどれほどあるか調べる 実行履歴ごとに効果の違いがあるかを調べる 図書管理システム 学生4グループが同じ設計仕様に基づいて作成した4個のシステム(A,B,C,D) 同じ手順で実行した実行履歴 今回行った実験の説明をします． 実験の目的は， 提案手法がどれぐらい縮約できるのかを調べることと， 実行履歴ごとの効果の違いを調べることです． そのために実験対象として図書管理システムというアプリケーションの実行履歴を 使用しました． このシステムは同じ設計仕様に基づいて学生4グループが違う実装で作成し， 全て同じ手順で実行したときの実行履歴を取得したものです． 2008/06/19

実験概要(2/2) 実験方法 評価方法 作成したツールを各実行履歴に対して適用する 出力された実行履歴の出現オブジェクト数とメッセージ通信数を取得し，適用前と比較する 評価方法 ツール適用後の出現オブジェクト数とメッセージ通信数の圧縮率で評価 実験方法は，実装したツールで各実行履歴に対して手法を適用し， 適用の前後で実行履歴に出現するオブジェクトの数とメッセージ通信の数を 比較しました． ツールの適用前後の値から出現オブジェクト数とメッセージ通信数の圧縮率を 求め，それを評価します． 2008/06/19

図のサイズの変化 出現オブジェクト数の変化 メッセージ通信数の変化 2008/06/19 70.9% 71.5% 68.4% 3.0% 60.4% 59.4% 58.3% 2.8% 実験結果です． 左側のグラフは，シーケンス図を生成した際に図に並ぶオブジェクトの数を表し， 右側のグラフは，グループ間のメッセージ通信の数を表します． 2つのグラフの青色の部分はツールの適用前で， 赤色の部分はツールの適用後を表しています． システムAでは，出現オブジェクト数が適用後は適用前の60.4％に， メッセージ通信数は70.9％にへりました． システムB，Cも同じぐらい減りました． しかし，システムDは，出現オブジェクト数が2.8％に，メッセージ通信数が3％に減り， 他と極端な差が出ています． システムDでは，mainの直下に存在するオブジェクトが他のオブジェクトを ほとんど支配してしまったため，この実装の方法では， 極端なグループ化がおこってしまいました． 次で具体的にどのように図が縮約したのかを説明します． 2008/06/19

シーケンス図の変化 2008/06/19 この図が縮約する前のシーケンス図です． 図のうち青色になっている部分を縮約します． 赤枠で囲われたオブジェクトのうち，一番左のオブジェクトを 代表オブジェクトとしてグループ化します．（クリック） このように代表オブジェクトへのメッセージ通信のみとなり 先ほどの図が縦にも横にも縮約されます． 2008/06/19

全体図の変化 適用前 適用後 約70% 約60% 2008/06/19 この図はシステムAのシーケンス図の全体図です． 1つのメッセージ通信が縦1ドット，横がオブジェクト1つにつき1ドットで 表示されています． 左側が適用する前のもので，右側が適用後のものです． 横方向が約60%に圧縮されています． この図のスクロールバーのサイズでしか判断できませんが， 縦方向も約70%に圧縮されています． 約60% 2008/06/19

グループの分布 子供の数が少ないグループ 子供の数が多いグループ グループの数は多い 子供が1つであるグループが大半 グループの数は少ない 各スレッドのmainオブジェクトなど システムAのグループとそのメンバーの数の分布を調べました． 分布図は支配関係木の頂点に対して子供の数を数えたものです． 子供の数が少ないグループと多いグループの2つに大きく分かれ， 子供の数が少ないグループの数が多く， 子供の数が多いグループの数は少ないといった結果が得られました． 子供の数が少ないグループでは，子供の数が1個であるグループが一番多く， グループ全体の86％になりました． 子供の数が多いグループはあわせても5%ほどで 呼び出し関係グラフで根としたmainオブジェクトなどが含まれていました． システムAの分布図 2008/06/19

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

考察 支配関係解析の効果は実行履歴によって大きく左右される 実行履歴中のオブジェクト数やメソッド呼び出し数が近いものでも結果に差が出る 全てのオブジェクトが1つのグループになってしまうことがあった 全体の動きが把握できない GUI上で閲覧者が注目するグループの中身だけを対話的に調査できるようにする 実験の考察です． 圧縮率は実行履歴によって大きく左右されることを確認しました． 極端な場合だと，全く圧縮できなかった場合と 逆に圧縮しすぎて1つのグループになってしまった場合がありました． その場合，グループ内の動きが分からないため動作の把握ができなくなって しまいました． これは実装を改良して，GUI上で閲覧者が注目するグループの中身だけを 対話的に調査できるようにすることで対応できると考えられます． 2008/06/19

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