シーケンス図の生成のための実行履歴圧縮手法 情報科学研究科 コンピュータサイエンス専攻 井上研究室 博士前期課程2年 谷口考治 2005/02/18 修士論文発表会

発表の流れ 背景と動機 提案手法 適用実験 まとめ 後期課程での研究計画 オブジェクト指向プログラムの動作理解 実行履歴の圧縮手法 圧縮結果のシーケンス図としての可視化手法 適用実験 まとめ 後期課程での研究計画 2005/02/18 修士論文発表会

オブジェクト指向プログラムの概要 オブジェクト指向プログラム B-１ C-１ A-1 C-２ D-1 複数のオブジェクト間で相互にメッセージをやり取りすることによってプログラムが動作する クラスB B-１ C-１ クラスC クラスA A-1 メッセージ クラスD C-２ D-1 オブジェクト 2005/02/18 修士論文発表会

オブジェクト指向プログラムの動作理解 オブジェクト指向プログラムの特徴 １つの機能に多数のオブジェクトが関連する 動的束縛など、動的に決定される要素が多い オブジェクトの増加に伴い、メッセージ通信の構造が複雑化する ソースコードのみから、オブジェクトの動的な振る舞いを理解することは困難 オブジェクトの振る舞いを理解するためには、オブジェクトの動的な振る舞いを記述したドキュメントが必要 2005/02/18 修士論文発表会

オブジェクトの振る舞いの記述 UML：シーケンス図 オブジェクト間の２種類のメッセージを時系列にそって表現 オブジェクトの生成 メソッド呼び出し この図を用いることでオブジェクトの振る舞いを理解することができる 1:A 2:B 3:C 4:D 5:D メソッド呼び出し オブジェクト生成 2005/02/18 修士論文発表会

プログラムからの図の生成 設計段階でのシーケンス図の不備 シーケンス図と作成されたプログラムの動作が異なる 詳しく書かれていない 設計時にシーケンス図が作成されない オブジェクトの振る舞いを理解するためには、実際のプログラムに対応したシーケンス図が必要 プログラムを解析しシーケンス図を作成 実行時の動的なオブジェクトの振る舞いを図示するために、動的解析を基に図の生成を行う 2005/02/18 修士論文発表会

動的解析の問題点 動的解析から得られる情報は膨大な量 情報を削減する手法が必要 プログラム中のループや再帰を毎回記録 全ての情報を提示しても、容易には理解できない 情報を削減する手法が必要 本研究では、実行履歴中から繰り返しになっている部分を検出し、繰り返し全体を簡潔に表現しなおす 2005/02/18 修士論文発表会

2005/02/18 修士論文発表会

研究目的とアプローチ 目的 アプローチ オブジェクト指向プログラムの理解支援 繰り返し部分の圧縮による、実行履歴の抽象化 実行時のオブジェクトの動的な振る舞いを図示 アプローチ 繰り返し部分の圧縮による、実行履歴の抽象化 圧縮結果を基にしたシーケンス図の生成 2005/02/18 修士論文発表会

シーケンス図作成手順 実行履歴の取得 実行履歴の圧縮 圧縮結果を用いたシーケンス図生成 2005/02/18 修士論文発表会

Step1：実行履歴の取得 実行履歴 取得方法 「メソッドの開始」と「メソッドの終了」の２つのイベント系列 「メソッドの開始」イベント メソッドの呼び出しを受けたオブジェクトのID パッケージ名・クラス名 メソッド名 引数の型 返り値の型 メソッドの終了イベント メソッド終了記号 取得方法 Java 仮想マシン・プロファイラインタフェース (JVMPI)を利用 2005/02/18 修士論文発表会

void amida.Main(0).main(java.lang.String[]){ void amida.sequencer.gui.MainFrame(1).<init>(){ void amida.sequencer.gui.SearchDialog(2).<init>(){ amida.sequencer.gui.MainFrame amida.sequencer.gui.MainFrame(0).getInstance(){ } void amida.sequencer.gui.SearchDialog$1(3).<init>(amida.sequencer.gui.SearchDialog){ void amida.sequencer.gui.SearchDialog$2(4).<init>(amida.sequencer.gui.SearchDialog){ void amida.logcompactor.gui.WorkingSetFrame(5).<init>(java.lang.String){ void amida.logcompactor.gui.WorkingSetCanvas(6).<init>(int){ void amida.logcompactor.gui.WorkingSetCanvas(7).<init>(int){ void amida.logcompactor.gui.LogTextAreaFrame(8).<init>(){ void amida.logcompactor.gui.SearchDialog(9).<init>(){ void amida.logcompactor.gui.SearchDialog$1(10).<init>(){ void amida.logcompactor.gui.SearchDialog$2(11).<init>(java.lang.String){ void amida.logcompactor.gui.SearchDialog$2(11).<init>(java.lang.String){ パッケージ名 クラス名 オブジェクトＩＤ メソッド名 引数の型 返り値の型 2005/02/18 修士論文発表会

Step2：実行履歴の圧縮 Step1で取得した実行履歴はループや再帰呼び出しのメソッド呼び出しを全て記録している これら全てをシーケンス図中に示すと、巨大な図ができあがってしまう 実行履歴の繰り返し部分を検出し、繰り返し全体を抽象化した表現に置き換える 置き換えられた部分は、任意に展開し、元の情報を参照できるようにする 圧縮による情報の欠落の影響を小さくする 2005/02/18 修士論文発表会

提案する圧縮ルール 繰り返し圧縮ルール 再起構造の圧縮ルール R1 : 同一部分系列の繰り返し 2005/02/18 修士論文発表会

実行履歴の木構造としての表現 各圧縮ルールを説明するために、実行履歴を木構造に置き換えたものを用いる void A(1).a(){ int B(2).b(){ } int C(3).c(){ int B.b() 2 int C.c() 3 2005/02/18 修士論文発表会

R1：同一部分系列の繰り返し 実行履歴中の完全に同一な繰り返しを圧縮 ２ 繰り返し全体の代表 void A.a() 1 int B.b() 2 void C.c() 3 ２ void A.a() 1 void C.c() 3 void A.a() 1 void C.c() 3 int B.b() 2 int B.b() 2 繰り返し1回目 繰り返し2回目 2005/02/18 修士論文発表会

R2：オブジェクトが異なる系列の繰り返し オブジェクトのみが異なる繰り返しを圧縮 ２ 繰り返し全体の代表 void A.a() 1,4 int B.b() 2,5 void C.c() 3,6 ２ void A.a() 1 void C.c() 3 void A.a() 4 void C.c() 6 int B.b() 2 int B.b() 5 繰り返し1回目 繰り返し2回目 2005/02/18 修士論文発表会

R3：欠損を含む系列の繰り返し 呼び出し構造の一部が欠けている繰り返しを圧縮 ２ 繰り返し全体の代表 void A.a() 1,4 int B.b() 2 void C.c() 3,6 ２ ? void A.a() 1 void C.c() 3 void A.a() 4 void C.c() 6 int B.b() 2 繰り返し1回目 繰り返し2回目 2005/02/18 修士論文発表会

R4：再帰構造 再帰構造を圧縮 再帰構造全体を簡潔に表現できるように組み替える void A.a() 1 void A.a() 1,2,3 int B.b() 4,5,6 R ? R-top void A.a() 2 int B.b() 6 void A.a() 3 int B.b() 5 int B.b() 4 2005/02/18 修士論文発表会

Step3：シーケンス図の作成 圧縮された実行履歴を用いてシーケンス図を作成する 圧縮された部分やその回数などを図中に表示 2005/02/18 修士論文発表会

void A.a() 1 int B.b() 2 A(1) B(2) a() b() int 2005/02/18 修士論文発表会

R1 A(1) B(2) 2 void A.a() 1 void A.a() 1 int B.b() 2 int B.b() 2 ２ int B.b() 2 int B.b() 2 int B.b() 2 A(1) B(2) a() b() 2 2005/02/18 修士論文発表会

R2 A(1) B(2,3) 2 void A.a() 1 void A.a() 1 int B.b() 2 int B.b() 3 ２ int B.b() 2 int B.b() 3 int B.b() 2,3 A(1) B(2,3) a() b() 2 2005/02/18 修士論文発表会

R3 A(1) B(2,3) C(4) 2 void A.a() 1 void A.a() 1 int B.b() 2 int B.b() ２ int B.b() 2 int B.b() 3 int B.b() 2,3 int C.c() 4 ? int C.c() 4 A(1) B(2,3) C(4) a() b() 2 ? c() 2005/02/18 修士論文発表会

R4 A(1,2) B(3,4) a() b() void A.a() 1 void A.a() 1,2 void A.a() 2 R-top R4 void A.a() 1,2 void A.a() 2 int B.b() 4 R ? void A.a() 1,2 int B.b() 3,4 int B.b() 3 A(1,2) B(3,4) rec a() a() rec a() b() 2005/02/18 修士論文発表会

適用実験 次の４つのプログラムの各機能から実行履歴を取得 各実行履歴に対してＲ４→Ｒ１→Ｒ２→Ｒ３の順序で圧縮ルールを適用 jEdit：テキストエディタ テキストファイルの読み込み Gemini：コードクローン分析ツール ファイル指定、クローン解析、クローン情報表示 Scheduler：スケジュール管理ツール 日にち指定、スケジュール記述 LogCompactor：本ツールの実行履歴圧縮部 実行履歴の読み込み、表示、R２の実行 各実行履歴に対してＲ４→Ｒ１→Ｒ２→Ｒ３の順序で圧縮ルールを適用 それぞれのルールを適用して、実行系列の圧縮率を評価 圧縮結果からシーケンス図を作成 設計時に作成された図と比較 2005/02/18 修士論文発表会

圧縮結果(1/2) 2005/02/18 修士論文発表会

圧縮結果(2/2) 2005/02/18 修士論文発表会

2005/02/18 修士論文発表会

統合されたオブジェクト群 圧縮された繰り返し 2005/02/18 修士論文発表会

シーケンス図の比較実験 プログラム設計時に書かれたシーケンス図とツールから生成されたシーケンス図の比較 実験手順 設計時のシーケンス図 対象プログラム：scheduler 対象機能：スケジュールの編集 メソッドレベルまで詳細に記述されている 実験手順 ツールから生成されたシーケンス図中から、対象機能に該当する図を切り出す 図に違いがあるかを調べる 違いがあればその原因を考察 2005/02/18 修士論文発表会

2005/02/18 修士論文発表会

設計に無いメソッド呼び出し 設計に無いオブジェクト 2005/02/18 修士論文発表会

比較結果 ほぼ同様の流れのシーケンス図が生成された 生成した図には設計時の図にはないオブジェクト、メソッド呼び出しがあった ソースコード内には対応するメソッド呼び出し、オブジェクトが存在 設計時の図とプログラムの動作が異なる 2005/02/18 修士論文発表会

まとめ オブジェクト指向プログラムの理解支援 デバッグ環境への応用なども行っている 実行時のオブジェクトの動的な振る舞いを図示 実行時の情報は膨大 実行履歴を圧縮することにより、情報の削減 圧縮後の実行履歴からシーケンス図を作成 デバッグ環境への応用なども行っている 特別研究報告　浅利勇太：シーケンス図を用いて実行履歴を可視化するデバッグ環境の試作 2005/02/18 修士論文発表会

後期課程での研究計画 オブジェクト指向プログラムの実行時動作の解析 静的解析情報を利用した解析 マルチスレッド環境における複数スレッドにまたがったオブジェクト関係の解析と図示 2005/02/18 修士論文発表会

後期課程での研究計画 静的解析情報を利用した解析 制御構造の利用 静的なクラス関係の利用 さらなるシーケンス図の抽象化が可能 ループや分岐構造の情報を用いて、より高度な実行履歴の抽象化やシーケンス図中への表示などを可能にする 静的なクラス関係の利用 同じ親クラスのメソッドをオーバーライドしたメソッドや、同じインタフェースのメソッドを実装したメソッドを同一のメソッドとみなして圧縮する さらなるシーケンス図の抽象化が可能 2005/02/18 修士論文発表会

後期課程での研究計画 複数スレッドにまたがったオブジェクト関係の解析 通常はスレッドごとに動作の解析を行ったほうが、オブジェクトの振る舞いは理解しやすい 複数のスレッドが協調して動作する場合 複数のスレッドを同時に解析し、それらの関連性を視覚的に表現する A B C A B C 2005/02/18 修士論文発表会

おわり 2005/02/18 修士論文発表会

本手法の応用例 デバッグ環境の試作 ブレークポイントで停止した際に、そこまでの実行系列をシーケンス図で表示する 圧縮手法を適用することで、簡潔な図を作成 2005/02/18 修士論文発表会

2005/02/18 修士論文発表会

Gemini実行履歴圧縮後のメソッド出現状況 圧縮結果(3) 時間 呼ばれたメソッドの種類 Gemini実行履歴圧縮後のメソッド出現状況 さらなる繰り返し圧縮ルールが必要である 2005/02/18 修士論文発表会

静的構造を利用した圧縮 for(int i = 0; i < num < i++){ A1.a(); if (i == 1) X4.x(); C3.c(); } void A.a() 1 int B.b() 2 繰り返し1回目 繰り返し2回目 void C.c() 3 void X.x() 4 2005/02/18 修士論文発表会

2005/02/18 修士論文発表会

2005/02/18 修士論文発表会

後期課程での研究計画 オブジェクトが関連する機能の判定 ある機能に対してどのオブジェクトが動作するか 実行時のオブジェクトを機能的なまとまりを持つオブジェクト群に分類 複数の実行履歴を基に、それらがどの機能に関与するかを検出 2005/02/18 修士論文発表会