動的解析情報を利用したJavaプログラムからのシーケン

シーケンス図の生成のための
実行履歴圧縮手法
情報科学研究科
コンピュータサイエンス専攻
井上研究室
博士前期課程2年
谷口考治
2005/02/18
修士論文発表会
1
発表の流れ

背景と動機


提案手法





オブジェクト指向プログラムの動作理解
実行履歴の圧縮手法
圧縮結果のシーケンス図としての可視化手法
適用実験
まとめ
後期課程での研究計画
2005/02/18
修士論文発表会
2
オブジェクト指向プログラムの概要

オブジェクト指向プログラム

複数のオブジェクト間で相互にメッセージをやり取りすること
によってプログラムが動作する
クラスB
B-１
C-１
A-1
クラスA
オブジェクト
メッセージ
クラスC
C-２
D-1
クラスD
2005/02/18
修士論文発表会
3
オブジェクト指向プログラムの動作理解

オブジェクト指向プログラムの特徴




１つの機能に多数のオブジェクトが関連する
動的束縛など、動的に決定される要素が多い
オブジェクトの増加に伴い、メッセージ通信の構造が複雑化する
ソースコードのみから、オブジェクトの動的な振る舞いを理解
することは困難

オブジェクトの振る舞いを理解するためには、オブジェクトの動的な振る
舞いを記述したドキュメントが必要
2005/02/18
修士論文発表会
4
オブジェクトの振る舞いの記述

UML：シーケンス図

オブジェクト間の２種類のメッセージを時系列にそって表現



オブジェクトの生成
メソッド呼び出し
この図を用いることでオブジェクトの振る舞いを理解することができ
る
1:A
2:B
3:C
メソッド呼び出し
オブジェクト生成
4:D
5:D
2005/02/18
修士論文発表会
5
プログラムからの図の生成

設計段階でのシーケンス図の不備



シーケンス図と作成されたプログラムの動作が異なる
詳しく書かれていない
設計時にシーケンス図が作成されない

オブジェクトの振る舞いを理解するためには、実際のプ
ログラムに対応したシーケンス図が必要

プログラムを解析しシーケンス図を作成

実行時の動的なオブジェクトの振る舞いを図示するために、動
的解析を基に図の生成を行う
2005/02/18
修士論文発表会
6
動的解析の問題点

動的解析から得られる情報は膨大な量



プログラム中のループや再帰を毎回記録
全ての情報を提示しても、容易には理解できない
情報を削減する手法が必要

本研究では、実行履歴中から繰り返しになっている部
分を検出し、繰り返し全体を簡潔に表現しなおす
2005/02/18
修士論文発表会
7
2005/02/18
修士論文発表会
8
研究目的とアプローチ

目的

オブジェクト指向プログラムの理解支援


実行時のオブジェクトの動的な振る舞いを図示
アプローチ


繰り返し部分の圧縮による、実行履歴の抽象化
圧縮結果を基にしたシーケンス図の生成
2005/02/18
修士論文発表会
9
シーケンス図作成手順
1.
2.
3.
実行履歴の取得
実行履歴の圧縮
圧縮結果を用いたシーケンス図生成
2005/02/18
修士論文発表会
10
Step1：実行履歴の取得

実行履歴


「メソッドの開始」と「メソッドの終了」の２つのイベント系列
「メソッドの開始」イベント






メソッドの終了イベント


メソッドの呼び出しを受けたオブジェクトのID
パッケージ名・クラス名
メソッド名
引数の型
返り値の型
メソッド終了記号
取得方法

Java 仮想マシン・プロファイラインタフェース (JVMPI)を利用
2005/02/18
修士論文発表会
11
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>(){
voidvoid
amida.logcompactor.gui.SearchDialog(9).<init>(){
amida.logcompactor.gui.SearchDialog$2(11).<init>(java.lang.String){
void amida.logcompactor.gui.SearchDialog$1(10).<init>(){
}
void amida.logcompactor.gui.SearchDialog$2(11).<init>(java.lang.String){
}
返り値の型
パッケージ名
2005/02/18
クラス名
オブジェクトＩＤ
修士論文発表会
メソッド名
引数の型
12
Step2：実行履歴の圧縮

Step1で取得した実行履歴はループや再帰呼び出しのメ
ソッド呼び出しを全て記録している
 これら全てをシーケンス図中に示すと、巨大な図ができあ
がってしまう

実行履歴の繰り返し部分を検出し、繰り返し全体を抽象化
した表現に置き換える
 置き換えられた部分は、任意に展開し、元の情報を参照
できるようにする

2005/02/18
圧縮による情報の欠落の影響を小さくする
修士論文発表会
13
提案する圧縮ルール

繰り返し圧縮ルール




R1 : 同一部分系列の繰り返し
R2 : オブジェクトのみが異なる系列の繰り返し
R3 : 欠損を含む系列の繰り返し
再起構造の圧縮ルール

R4 : 再帰構造
2005/02/18
修士論文発表会
14
実行履歴の木構造としての表現

各圧縮ルールを説明するために、実行履歴を木構造
に置き換えたものを用いる
void A.a()
1
void A(1).a(){
int B(2).b(){
}
int C(3).c(){
}
}
2005/02/18
修士論文発表会
int B.b()
int C.c()
2
3
15
R1：同一部分系列の繰り返し

実行履歴中の完全に同一な繰り返しを圧縮
void A.a()
1
void C.c()
3
int B.b()
2
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回目
2005/02/18
繰り返し2回目
修士論文発表会
繰り返し全体の代表
16
R2：オブジェクトが異なる系列の繰り
返し

オブジェクトのみが異なる繰り返しを圧縮
void A.a()
1
void C.c()
3
int B.b()
2
void A.a()
4
void C.c()
6
void A.a()
1,4
void C.c()
3,6
int B.b()
2,5
int B.b()
5
２
繰り返し1回目
2005/02/18
繰り返し2回目
修士論文発表会
繰り返し全体の代表
17
R3：欠損を含む系列の繰り返し

呼び出し構造の一部が欠けている繰り返しを圧縮
void A.a()
1
void C.c()
3
void A.a()
4
void C.c()
6
void A.a()
1,4
void C.c()
3,6
?
int B.b()
2
int B.b()
2
２
繰り返し1回目
2005/02/18
繰り返し2回目
修士論文発表会
繰り返し全体の代表
18
R4：再帰構造

再帰構造を圧縮

再帰構造全体を簡潔に表現できるように組み替える
void A.a()
1
void A.a()
2
void A.a()
3
R-top
void A.a()
1,2,3
int B.b()
6
R
?
void A.a()
1,2,3
int B.b()
5
int B.b()
4,5,6
int B.b()
4
2005/02/18
修士論文発表会
19
Step3：シーケンス図の作成

圧縮された実行履歴を用いてシーケンス図
を作成する

圧縮された部分やその回数などを図中に表示
2005/02/18
修士論文発表会
20
void A.a()
1
int B.b()
2
A(1)
B(2)
a()
b()
int
2005/02/18
修士論文発表会
21
void A.a()
1
void A.a()
1
R1
２
int B.b()
int B.b()
int B.b()
2
2
2
A(1)
B(2)
a()
b()
2
2005/02/18
修士論文発表会
22
void A.a()
1
void A.a()
1
R2
int B.b()
int B.b()
2
3
２
int B.b()
2,3
A(1)
B(2,3)
a()
b()
2
2005/02/18
修士論文発表会
23
void A.a()
1
void A.a()
1
２
int B.b()
int B.b()
2
3
R3
int B.b()
2,3
?
int C.c()
4
int C.c()
4
A(1)
B(2,3)
C(4)
a()
b()
? c()
2
2005/02/18
修士論文発表会
24
void A.a()
1
void A.a()
2
int B.b()
4
R-top
R4
R
A(1,2)
int B.b()
3,4
B(3,4)
rec a()
rec a()
2005/02/18
?
void A.a()
1,2
int B.b()
3
a()
void A.a()
1,2
b()
修士論文発表会
25
適用実験

次の４つのプログラムの各機能から実行履歴を取得
 jEdit：テキストエディタ


Gemini：コードクローン分析ツール



日にち指定、スケジュール記述
LogCompactor：本ツールの実行履歴圧縮部


ファイル指定、クローン解析、クローン情報表示
Scheduler：スケジュール管理ツール


テキストファイルの読み込み
実行履歴の読み込み、表示、R２の実行
各実行履歴に対してＲ４→Ｒ１→Ｒ２→Ｒ３の順序で圧縮ルールを適用
 それぞれのルールを適用して、実行系列の圧縮率を評価
圧縮結果からシーケンス図を作成
 設計時に作成された図と比較
2005/02/18
修士論文発表会
26
圧縮結果(1/2)
jEdit
250,000
228,764
Gemini
250,000
217,351
200,000
208,360
150,000
150,000
100,000
100,000
50,000
50,000
57,365
16,889
16,510
0
圧縮前
R4
R１
R2
0
R3
圧縮前
Scheduler
5,000
4,500
4,000
3,500
3,000
2,500
2,000
1,500
1,000
500
0
205,483
200,000
178,128
4,398
R4
R１
1,954
1,762
R2
R3
208
105
R2
R3
LogCompactor
14,000
4,398
3,995
12,000
11,994
10,000
8,874
8,426
8,000
6,000
4,000
238
147
2,000
0
圧縮前
2005/02/18
R4
R１
R2
R3
圧縮前
修士論文発表会
R4
R１
27
圧縮結果(2/2)
jEdit-2
18,000
16,889
Gemini-2
16,510
2,500
16,000
2,000
14,000
1,954
1,762
12,000
1,500
10,000
8,000
1,000
6,000
4,000
500
2,000
0
R2
0
R3
R2
Scheduler-2
250
R3
LogCompactor-2
238
250
208
200
200
147
150
150
105
100
100
50
50
0
R2
2005/02/18
R3
0
R2
修士論文発表会
R3
28
2005/02/18
修士論文発表会
29
統合されたオブジェクト群
圧縮された繰り返し
2005/02/18
修士論文発表会
30
シーケンス図の比較実験

プログラム設計時に書かれたシーケンス図とツールから
生成されたシーケンス図の比較


設計時のシーケンス図
 対象プログラム：scheduler
 対象機能：スケジュールの編集
 メソッドレベルまで詳細に記述されている
実験手順



ツールから生成されたシーケンス図中から、対象機能に該当する
図を切り出す
図に違いがあるかを調べる
違いがあればその原因を考察
2005/02/18
修士論文発表会
31
2005/02/18
修士論文発表会
32
設計に無いメソッド呼び出し
2005/02/18
設計に無いオブジェクト
修士論文発表会
33
比較結果


ほぼ同様の流れのシーケンス図が生成された
生成した図には設計時の図にはないオブジェク
ト、メソッド呼び出しがあった


ソースコード内には対応するメソッド呼び出し、オブ
ジェクトが存在
設計時の図とプログラムの動作が異なる
2005/02/18
修士論文発表会
34
まとめ

オブジェクト指向プログラムの理解支援


実行時のオブジェクトの動的な振る舞いを図示
実行時の情報は膨大



実行履歴を圧縮することにより、情報の削減
圧縮後の実行履歴からシーケンス図を作成
デバッグ環境への応用なども行っている

特別研究報告浅利勇太：シーケンス図を用いて実
行履歴を可視化するデバッグ環境の試作
2005/02/18
修士論文発表会
35
後期課程での研究計画

オブジェクト指向プログラムの実行時動作の解析


静的解析情報を利用した解析
マルチスレッド環境における複数スレッドにまたがった
オブジェクト関係の解析と図示
2005/02/18
修士論文発表会
36
後期課程での研究計画

静的解析情報を利用した解析

制御構造の利用


静的なクラス関係の利用


ループや分岐構造の情報を用いて、より高度な実行履歴の抽象化
やシーケンス図中への表示などを可能にする
同じ親クラスのメソッドをオーバーライドしたメソッドや、同じインタ
フェースのメソッドを実装したメソッドを同一のメソッドとみなして圧縮
する
さらなるシーケンス図の抽象化が可能
2005/02/18
修士論文発表会
37
後期課程での研究計画

複数スレッドにまたがったオブジェクト関係の解析


通常はスレッドごとに動作の解析を行ったほうが、オブ
ジェクトの振る舞いは理解しやすい
複数のスレッドが協調して動作する場合
A
B
C

2005/02/18
複数のスレッドを同時に解析し、それらの関連性を視覚的に表現
する
修士論文発表会
38

おわり
2005/02/18
修士論文発表会
39
本手法の応用例

デバッグ環境の試作


ブレークポイントで停止した際に、そこまでの実行系
列をシーケンス図で表示する
圧縮手法を適用することで、簡潔な図を作成
2005/02/18
修士論文発表会
40
2005/02/18
修士論文発表会
41
圧縮結果(3)
呼
ば
れ
た
メ
ソ
ッ
ド
の
種
類
時間
Gemini実行履歴圧縮後のメソッド出現状況

2005/02/18
さらなる繰り返し圧縮ルールが必要である
修士論文発表会
42
静的構造を利用した圧縮
for(int i = 0; i < num < i++){
A1.a();
if (i == 1)
X4.x();
C3.c();
}
void A.a()
1
void C.c()
3
int B.b()
2
繰り返し1回目
2005/02/18
void A.a()
1
void X.x()
4
void C.c()
3
int B.b()
2
繰り返し2回目
修士論文発表会
43
2005/02/18
修士論文発表会
44
2005/02/18
修士論文発表会
45
後期課程での研究計画

オブジェクトが関連する機能の判定

ある機能に対してどのオブジェクトが動作するか


2005/02/18
実行時のオブジェクトを機能的なまとまりを持つオブジェクト群に
分類
複数の実行履歴を基に、それらがどの機能に関与するかを検出
修士論文発表会
46

Download Report