スライド 1

木構造の比較に基づく
メソッド呼び出し履歴の変化の可視化手法
井上研究室
伊藤芳朗
2010/02/15
1
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
概要
 背景
►オブジェクト指向プログラムの解析
►メソッド呼び出し履歴の比較
 提案手法
►木構造の比較に基づくメソッド呼び出し履歴の変化の可
視化手法
 実験
►ソースコードの変更による影響を確認
 まとめ
2010/02/15
2
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
背景
 オブジェクト指向プログラム
►オブジェクト同士の相互作用としてシステムの振る舞いを
捉える考え方
►実行時の動作を理解するのは難しい
 クラスの継承
 多態性（ポリモーフィズム）
 オブジェクト指向プログラムの動作理解
►メソッド呼び出し履歴等の動的情報の解析が有効
 オブジェクト間のメソッド呼び出し関係を可視化
2010/02/15
3
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
シーケンス図生成システム Amida
 Javaプログラムのメソッド呼び出し履歴を取得し，
シーケンス図を生成するシステム
►メソッド呼び出し履歴はメソッド名，オブジェクトID，スレッ
ドIDなどの情報の系列
►メソッドの呼び出し関係をシーケ
ンス図で表示
►ループや再帰呼び出しを
圧縮する機能を持つ
 シーケンス図が巨大になるのを防ぐ
谷口，石尾，神谷，楠本，井上: “プログラム実行履歴からの簡潔なシーケンス図の作成手法” ，コンピュ
ータソフトウェア，Vol.24，No.3 (2007)，pp.153-169．
2010/02/15
4
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
シーケンス図
 オブジェクト間のメッセージ通信を時系列に沿って表現する
 システムの設計時に作成される
 プログラムの動作の理解に有効
A
B
2010/02/15
C
D
E
F
G
H
I
5
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
プログラムの振る舞いの比較の必要性
 ソースコードを変更すると実行時の動作が変わる
►デバッグ作業でのソースコードの変更
 ソースコードの変更が正しいかの確認したい
 予想していない動作の変化を発見したい
 実行時の動作はメソッド呼び出し履歴に記録される
 メソッド呼び出し履歴を比較すれば動作の変化がわ
かる
►ソースコードの変更前後で同じシナリオを実行する
►ソースコードの変更による動作の変化が表れる
2010/02/15
6
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
メソッド呼び出し履歴の比較の問題点
 メソッド呼び出し履歴は巨大
►人間が比較すると時間がかかってしまう
 予想していない変更点の発見が困難
 メソッド呼び出し履歴ごとに生成したオブジェクトのID
が異なる
►オブジェクトIDは生成順序やメモリ上の配置などを元に実
行ごとに決定するため
►同じ役割のオブジェクトの対応が取れない
2010/02/15
7
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
提案手法
 2つのメソッド呼び出し履歴を比較し，動作の変化を
検出する
►ソースコードの変更前後で同じシナリオを実行したメソッド
呼び出し履歴を取得
►メソッドの呼び出し関係を木構造にして比較
 動作の変化を可視化する
►可視化にはAmidaを利用し，シーケンス図を生成する
 メソッド呼び出し履歴全体のシーケンス図を生成
 動作の変化である部分を強調表示
2010/02/15
8
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
木構造への変換
 メソッド呼び出し履歴を木構造に変換する
►1つのメソッド呼び出しを1つのノードにする
►メソッドの実行中に呼ばれたメソッドを子ノードとして親子
関係を作る
►これをメソッド呼び出し関係木と呼ぶ
A
0
B
1
C
D
E
F
G
0
2
3
4
1
5
2010/02/15
6
2
5
3
4
6
9
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
メソッド呼び出し関係木の比較
 一方のメソッド呼び出し関係木の中から部分木を取
り出し，一致する部分木があるか判定する
►トップダウン方式で比較していく
►部分木が一致したら，ノードにマークをつける
 マークのついた部分木は変化していない部分である
►全ての部分木で探索が終わったら比較が終わる
 最終的にマークのないノードが変化した部分だとわかる
2010/02/15
10
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
部分木の一致条件
 部分木T1 とT2 が以下の全てを満たすと一致する
► T1 の根
ｒ1 と T2 の根ｒ2 が一致する
► ｒ1 と
ｒ2 の子ノードの数が一致する
► ｒ1 の i 番目の子ノードｒ1i を根とする部分木 T1i とｒ2の i 番目の
子ノードｒ2i を根とする部分木 T2i が一致する
 ノードｒ1 とｒ2 が以下の全てを満たすと一致する
► メソッド呼び出し名が等しい
► 引数の型が等しい
► 返り値の型が等しい
► 呼び出し元オブジェクトのクラス名が等しい
► 呼び出し先オブジェクトのクラス名が等しい
2010/02/15
11
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
メソッド呼び出し関係木の比較の例
 左側の木の部分木に一致する部分木を探す
1. ノード1と一致するノードを探す
2. ノード1の子ノードが一致するか調べる
3. ノード3の子ノードが一致するか調べる
 一致する部分のないノードは変化した部分とする
0
1
2
2010/02/15
0
1
5
3
4
6
2
7
3
4
12
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
シーケンス図へ可視化
 メソッド呼び出し履歴全体をシーケンス図にする
►変化した部分を強調して表示
►変化した部分を自動で探索
 シーケンス図が巨大になると探すのが困難
 変化した部分に関係する一連のメソッド呼び出しを抜き出す
0
1
2
3
4
5
3
6
5
6
抽出
2010/02/15
13
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
適用実験
 実験の目的
►提案手法で実際にソースコードの変更による影響を確認
する
 実験対象
►画像編集ソフトJHotDrawのメソッド呼び出し履歴
 バージョン7.3と7.3.1で同じシナリオを実行
– プログラムを起動し，三角形を1つ描き保存せずに終了する
 評価方法
►バージョン間の変更点を発見できるか
バージョン
2010/02/15
イベント数
ファイルサイズ(KB)
7.3
55789
5580
7.3.1
49127
4858
14
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
実験結果
 実際にソースコードの変更を動作の変化として表示
できた
►3つのクラスで変更点を発見
 新しいメソッドの追加(DefaultDrawingEditorクラス)
 メソッドの処理の変更(AbstractToolクラス)
 コンストラクタの処理の変更(DefaultDrawingViewクラス)
 ソースコードが変更されていないのに動作の変化があ
ると判定された
►実行時に派生クラスが変わっていたため
2010/02/15
15
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
スクリーンショット
2010/02/15
16
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
考察
 提案手法のメリット
►全体の流れが追える
 メソッドを追加したときにどのような影響が出たのかが分かる
►ソースコードの変更以外での変化を捉えられる
 設定ファイルや入力データの変更による動作の変化
– 入力による振る舞いの変化の理解
– バグ検出に応用
2010/02/15
17
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
まとめ
 まとめ
►木構造の比較に基づくメソッド呼び出し履歴の変化の可
視化手法を提案した
 プログラムの変更による動作の変化を検出
 検出した動作の変化をシーケンス図に視覚化
►実験を行い，動作の変化からソースコードの変更点を発
見した
 今後の課題
►比較計算にかかる時間の削減
 アルゴリズムの改良
 Amidaのループ圧縮処理と組み合わせる
2010/02/15
18
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Download Report