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

Javaプログラムの実行履歴に基
づくシーケンス図の作成
谷口考治†,石尾隆†,神谷年洋‡,
楠本真二†,井上克郎†
†大阪大学大学院情報科学研究科
‡科学技術振興機構さきがけ
2004/11/11
FOSE2004
1
発表の流れ

背景と動機


提案手法




オブジェクト指向プログラムの理解支援
実行履歴の取得と圧縮
圧縮結果を元にした図の作成
適用実験
まとめと今後の課題
2004/11/11
FOSE2004
2
オブジェクト指向プログラムの動作
概要

オブジェクト指向プログラム

複数のオブジェクト間で相互にメッセージをやり取
りすることによってプログラムが動作する
クラスB
B-1
C-1
クラスA
A-1
オブジェクト
メッセージ
クラスC
C-2
D-1
クラスD
2004/11/11
FOSE2004
3
オブジェクト指向プログラムの理解

オブジェクト指向プログラムの動作理解の問題
点

1つの機能を実現するために、複数のオブジェクトが
協調して動作する


動的に決定する要素が多い


実際にメソッドを実行するオブジェクトが動的に決まる等
メッセージ通信が複雑になる

2004/11/11
複数のオブジェクトの動作を追いながら全体を理解しなけれ
ばない
オブジェクト数が増加するにつれて、メッセージ通信の回数
が増え、より複雑になる
FOSE2004
4
シーケンス図による動作理解

UMLのシーケンス図



A-1
B-1
C-1
C-2
D-1
通常は設計時に作成さ
れる
オブジェクト間の関係を
時系列にそって表現
オブジェクト指向プログラ
ムの理解に非常に有用
シーケンス図

プログラムからシーケンス図を作成することで、プログラム理解
を支援することができる
2004/11/11
FOSE2004
5
静的解析と動的解析

静的解析からシーケンス図を作成する研究は既に行わ
れている*



オブジェクトの依存関係から、起こりうる全ての呼び出しを抽出
入力値に依存するシーケンスは特定できない
プログラムの動的解析からシーケンス図を自動作成

プログラム実行時の動作理解の支援を行う
*Paolo Tonella and Alessandra Potrich: Reverse Engineering of the Interaction Diagrams form C++ Code.
Proceedings of International Conference on Software Maintenance (ICSM2003), pp.159-168 (2003).
2004/11/11
FOSE2004
6
動的解析から行う場合の問題点

動的解析から得られる実行時のメソッド呼び出し
情報は膨大な量になる



プログラム中のループ、再帰構造によって発生するメ
ソッド呼び出しを全て記録
全てをシーケンス図に表示するのは有用ではない
本手法では実行履歴中から繰り返しになってい
る部分を検出し、圧縮を行う
2004/11/11
FOSE2004
7
動的解析が有効な状況

動的解析の特徴




プログラムの実際の動作(入力値に依存した動作)を
解析する
全体のソースコードがなくても解析できる
実行できるシステムにしか適用できない
動的解析情報からシーケンス図を作成するとい
う手法を有効に使える状況


2004/11/11
保守
テスト・デバッグ
FOSE2004
8
研究目的とアプローチ

目的


オブジェクト指向プログラムの理解支援
アプローチ


2004/11/11
動的解析情報を用いたシーケンス図の作成
繰り返し部分の圧縮による、簡潔な図の提示
FOSE2004
9
シーケンス図作成手順
解析対象となる機能に対応した入力を決定
実行履歴の取得
1.
2.
プログラムを動作させメソッド呼び出しの実行履
歴を取得

実行履歴を解析
3.
繰り返し部分を圧縮

4.
シーケンス図生成
2004/11/11
FOSE2004
10
Step2:実行履歴の取得

実行履歴


「メソッドの開始」と「メソッドの終了」の2つのイベント系列
「メソッドの開始」イベントでは以下の情報を記録





メソッドの呼び出しを受けたオブジェクトのID
パッケージ名・クラス名
メソッド名
引数の型
返り値の型

メソッドの終了イベントでは終了記号を記録

実装ではJVMPIを用いて実行履歴を取得
2004/11/11
FOSE2004
11
実行履歴の例
void MDI(582355424).initComponents(){
void MDI(582355424).initMenuBar(){
void MDI$2(582052416).MDI$2(MDI){
}
void MDI$3(582057008).MDI$3(MDI){
}
void MDI$4(582065224).MDI$4(MDI){
}
void MDI$5(582071192).MDI$5(MDI){
}
void MDI$6(582075824).MDI$6(MDI){
}
void ccfinder/CCFinderManager(44820192).CCFinderManager(java/awt/Container){
}
}
void ccfinder/CCFinderManager(582205384).CCFinderManager(java/awt/Container){
返り値の型
パッケージ名
2004/11/11
クラス名
オブジェクトID
FOSE2004
メソッド名
引数の型
12
void A(1).a(){
int B(2).b(){
}
}
A[1]
B[2]
a()
b()
int
2004/11/11
FOSE2004
13
Step3:実行履歴の解析

Step2で取得した実行履歴はループや再帰呼び出しのメソッド呼び
出しを全て記録している


これら全てをシーケンス図中に示すと、巨大な図ができあがってしまう
実行履歴の繰り返し部分を検出し、圧縮する




繰り返し部分を可能な限り検出する
情報の損失を少なくする
図として表現しやすくする
展開して元の実行履歴も参照できるようにする

2004/11/11
圧縮結果から任意の部分を展開することで、一部分についての詳細な実行
情報を得られる
FOSE2004
14
提案する圧縮ルール




2004/11/11
R1 : 同一部分系列の繰り返し
R2 : オブジェクトが異なる(ただし同一クラスの)系列
の繰り返し
R3 : 欠損を含む系列の繰り返し
R4 : 再帰構造
FOSE2004
15
R1:同一部分系列の繰り返し

実行履歴中の完全に同一な繰り返しを圧縮
B(2).b(){
C(3).c(){
}
}
D(4).d(){
}
B(2).b(){
C(3).c(){
}
}
D(4).d(){
}
・・・


2004/11/11
B(2).b(){
C(3).c(){
}
}
D(4).d(){
}
n
元の実行履歴の情報を損なうことがない
繰り返しを検出できる部分は少ない
FOSE2004
16
R2:オブジェクトが異なる系列の
繰り返し

オブジェクトのみが異なる繰り返しを圧縮
B(2).b(){
C(3).c(){
}
}
D(4).d(){
}
B(5).b(){
C(6).c(){
}
}
D(7).d(){
}
・・・


2004/11/11
B(2,5).b(){
C(3,6).c(){
}
}
D(4,7).d(){
}
n
R1より多くの繰り返しを検出できる
オブジェクト単体へのシーケンスを表現できなくなる
FOSE2004
17
R3:欠損を含む系列の繰り返し

呼び出し構造の一部が欠けている繰り返しを圧縮
B(2).b(){
C(3).c(){
}
}
D(4).d(){
}
B(2).b(){
}
D(4).d(){
}
・・・
B(2).b(){
? C(3).c(){
}
}
D(4).d(){
}
n
内部で流れの違う繰り返しも発見できる
 欠損するメソッドは、呼ばれる場合と呼ばれない場合がある
と表現され、シーケンスの正確性に欠ける

2004/11/11
FOSE2004
18
R4:再帰構造

再帰構造を圧縮

再帰構造全体を簡潔に表現できるように組み替える
A(1).a(){
A(2).a(){
A(3).a(){
B(4).b(){
}
}
B(5).b(){
}
}
B(6).b(){
}
}
A(1,2,3).a(){
recursive A(1,2,3).a(){
}
B(4,5,6).b(){
}
}
再帰呼び出し回数の差を緩和することで、この手法以降に適
用する繰り返し圧縮ルールの効果が高くなることも期待できる

2004/11/11
FOSE2004
19
A(1).a(){
A(2).a(){
A(3).a(){
B(4).b(){
}
}
B(5).b(){
}
}
B(6).b(){
}
}
A(7).a(){
A(8).a(){
B(9).b(){
}
}
B(10).b(){
}
}
2004/11/11
R4
A(1,2,3).a(){
recursive A(1,2,3).a(){
}
B(4,5,6).b(){
}
}
A(7,8).a(){
recursive A(7,8).a(){
}
B(9,10).b(){
}
}
A(1,2,3,7,8).a(){
recursive A(1,2,3,7,8).a(){
}
B(4,5,6,9,10).b(){
}
}
2
R2
FOSE2004
20
Step4:シーケンス図の作成

圧縮した実行履歴を元にシーケンス図を
作成

圧縮により、付加された情報をシーケンス図
中に表示

2004/11/11
繰り返しになっている部分やその回数など
FOSE2004
21
A(1).a(){
B(2).b(){
}
B(2).b(){
}
}
A(1).a(){
B(2).b(){
}
}
R1
A[1]
2
B[2]
a()
b()
2
2004/11/11
FOSE2004
22
A(1).a(){
B(2).b(){
}
B(3).b(){
}
}
A(1).a(){
B(2,3).b(){
2
}
}
R2
A[1]
B[2,3]
a()
b()
2
2004/11/11
FOSE2004
23
A(1).a(){
B(2).b(){
C(4).c(){
}
}
B(3).b(){
}
}
A(1).a(){
B(2,3).b(){
? C(4).c(){
2
}
}
}
R3
A[1]
B[2,3]
C[4]
a()
b()
? c()
2
2004/11/11
FOSE2004
24
A(1).a(){
A(1).a(){
B(2).b(){
}
}
B(2).b(){
}
}
A(1).a(){
recursive A(1).a(){
}
B(2).b(){
}
}
R4
A[1]
B[2]
a()
rec a()
rec a()
2004/11/11
b()
FOSE2004
25
適用実験

次の4つのプログラムの各機能から実行履歴を取得

jEdit:テキストエディタ


Gemini:コードクローン分析ツール


実行履歴の読み込み、表示、R2の実行
各実行履歴に対してR4→R1→R2→R3の順序で圧縮ルールを適用


日にち指定、スケジュール記述
LogCompactor:本ツールの実行履歴圧縮部


ファイル指定、クローン解析、クローン情報表示
Scheduler:スケジュール管理ツール


テキストファイルの読み込み
それぞれのルールを適用して、実行系列の圧縮率を評価
圧縮結果からシーケンス図を作成

2004/11/11
設計時に作成された図と比較
FOSE2004
26
圧縮結果(1/3)
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
R1
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
R1
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
圧縮前
2004/11/11
R4
R1
R2
圧縮前
R3
FOSE2004
R4
R1
27
圧縮結果(2/3)
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
2004/11/11
R3
0
R2
FOSE2004
R3
28
圧縮結果(3/3)
呼
ば
れ
た
メ
ソ
ッ
ド
の
種
類
Gemini実行履歴圧縮後のメソッド出現状況
時間

2004/11/11
さらなる繰り返し圧縮ルールが必要である
FOSE2004
29
シーケンス図の比較

プログラム設計時に書かれたシーケンス図とツールから
生成されたシーケンス図の比較


2004/11/11
対象プログラム:scheduler
対象機能:スケジュールの編集
FOSE2004
30
2004/11/11
FOSE2004
31
設計時にはない
オブジェクト
設計時にはない
メソッド呼び出し
2004/11/11
FOSE2004
32
比較結果


ほぼ同様のシーケンスが描画できている
設計時には書かれていないが、実装時に付け足されたメ
ソッド呼び出しも描画した
2004/11/11
FOSE2004
33
まとめ

オブジェクト指向プログラムの理解支援と
して、動的解析情報からシーケンス図を作
成する手法を提案し実装した


2004/11/11
提案した実行履歴圧縮手法により実行履歴の
大部分を圧縮
圧縮後の実行履歴からシーケンス図を作成
FOSE2004
34
今後の課題


新しい圧縮ルールの考案と評価
シーケンス図の評価


実行履歴の分割


より多くのサンプルとの比較実験
登場するオブジェクト・メソッドを元に、実行履
歴を分割
マルチスレッドの単一図上への表現
2004/11/11
FOSE2004
35

デモ
2004/11/11
FOSE2004
36