木構造の比較に基づく メソッド呼び出し履歴の変化の可視化手法 井上研究室 伊藤芳朗 井上研究室の伊藤です． 「木構造の比較に基づくメソッド呼び出し履歴の変化の可視化手法」というタイトルで 発表を始めます． よろしくお願いします． 2010/02/15

概要 背景 提案手法 実験 まとめ オブジェクト指向プログラムの解析 メソッド呼び出し履歴の比較 木構造の比較に基づくメソッド呼び出し履歴の変化の可視化手法 実験 ソースコードの変更による影響を確認 まとめ 発表の概要はこのようになっています． まず背景として，オブジェクト指向プログラムの解析と メソッド呼び出し履歴の比較について 説明します． 次に，提案手法である「木構造に基づくメソッド呼び出し履歴の変化の可視化手法」について そのあと，適用実験とその結果． 最後にまとめと今後の課題について説明します．

背景 オブジェクト指向プログラム オブジェクト指向プログラムの動作理解 オブジェクト同士の相互作用としてシステムの振る舞いを捉える考え方 実行時の動作を理解するのは難しい クラスの継承 多態性（ポリモーフィズム） オブジェクト指向プログラムの動作理解 メソッド呼び出し履歴等の動的情報の解析が有効 オブジェクト間のメソッド呼び出し関係を可視化 本研究の背景にはオブジェクト指向プログラムの解析があります． オブジェクト指向とは，オブジェクト同士の相互作用として システムの振る舞いを捉える考え方のことです． オブジェクト指向プログラムは継承や多態性など， 動的に決定される要素が多く， 実行時の動作を理解するのは難しいという問題点があります． そのため，プログラムの動作を理解するには ソースコードなどの静的な情報の解析よりも， メソッド呼び出し履歴などの動的な情報の解析が有効です． 動的解析ではオブジェクト間のメソッド呼び出し関係を 可視化する手法などが提案されています．

シーケンス図生成システム Amida Javaプログラムのメソッド呼び出し履歴を取得し，シーケンス図を生成するシステム メソッド呼び出し履歴はメソッド名，オブジェクトID，スレッドIDなどの情報の系列 メソッドの呼び出し関係をシーケ ンス図で表示 ループや再帰呼び出しを 圧縮する機能を持つ シーケンス図が巨大になるのを防ぐ われわれの研究室では，シーケンス図生成システムAmidaを開発しました． AmidaはJavaプログラムを対象としたシステムで， プログラム実行時のメソッド呼び出し履歴を取得し，シーケンス図を生成します． メソッド呼び出し履歴はメソッド名やオブジェクトID， スレッドIDなどの情報の系列で， メソッドの呼び出し関係をシーケンス図で表示します． それによって，時系列に沿ったオブジェクト間のメソッド呼び出し関係や プログラムの実行時に決定される情報が分かります． メソッド呼び出し履歴には，サイズが巨大になりがちという特徴があるため， 生成したシーケンス図を解析し，ループや再起呼び出しという冗長な部分を 圧縮し表示する機能を持ちます． 谷口， 石尾， 神谷， 楠本， 井上: “プログラム実行履歴からの簡潔なシーケンス図の作成手法” ， コンピュータソフトウェア，Vol.24，No.3 (2007)，pp.153-169．

シーケンス図 オブジェクト間のメッセージ通信を時系列に沿って表現する システムの設計時に作成される プログラムの動作の理解に有効 B C D E A F G H I 次にAmidaが生成するシーケンス図について説明します． シーケンス図は，図の上部に横方向にオブジェクトを並べ， 縦方向は時間の経過を表します． 横方向の矢印はメッセージ通信を表していて，送信元から送信先に矢印を引きます． メッセージを受けたオブジェクトが処理している区間は長方形で表します． 処理が終わったときに，返り値がある場合は送信元のオブジェクトまで 矢印を引きます． シーケンス図は本来システムの設計段階において設計図として作成されますが， このように，実行時のオブジェクト間の相互作用をシーケンス図として可視化することで， プログラムの理解に役立ちます．

プログラムの振る舞いの比較の必要性 ソースコードを変更すると実行時の動作が変わる 実行時の動作はメソッド呼び出し履歴に記録される デバッグ作業でのソースコードの変更 ソースコードの変更が正しいかの確認したい 予想していない動作の変化を発見したい 実行時の動作はメソッド呼び出し履歴に記録される メソッド呼び出し履歴を比較すれば動作の変化がわかる ソースコードの変更前後で同じシナリオを実行する ソースコードの変更による動作の変化が表れる プログラムは，ソースコードを変更すると， 実行時の動作が変わります． 例えば，デバッグ作業でソースコードを変更したときには ソースコードの変更が正しいのか，予想していない動作の変化がないのか， といったテストが必要になります． そこで，ソースコードの変更前後のプログラムの振る舞いを比較する必要があります． プログラム実行時の動作はメソッド呼び出し履歴に記録されるため， メソッド呼び出し履歴を比較することで，動作の変化がわかるのではないかと考えました． 比較するときにソースコードの変更前後で同じシナリオを実行することで ソースコードの変更の影響による動作の変化が表れます．

メソッド呼び出し履歴の比較の問題点 メソッド呼び出し履歴は巨大 メソッド呼び出し履歴ごとに生成したオブジェクトのIDが異なる 人間が比較すると時間がかかってしまう 予想していない変更点の発見が困難 メソッド呼び出し履歴ごとに生成したオブジェクトのIDが異なる オブジェクトIDは生成順序やメモリ上の配置などを元に実行ごとに決定するため 同じ役割のオブジェクトの対応が取れない ただし，メソッド呼び出し履歴の比較を行う際には2つの問題点があります． 1つはプログラムのメソッド呼び出し履歴のサイズは巨大であるという点です． 人間が変更部分を探す場合，メソッド呼び出し履歴をそのまま比較しようとすると， 膨大な量となるため予想していないような変更を発見するのが困難です． もう1つはメソッド呼び出し履歴ごとに生成された オブジェクトIDが異なるという点です． オブジェクトIDは生成順序やメモリ上の配置などを元に 実行ごとに決定されるためです． その結果，オブジェクト間の対応をオブジェクトIDでは取れなくなり， 計算機に単純に比較させることが難しくなります．

提案手法 2つのメソッド呼び出し履歴を比較し，動作の変化を検出する 動作の変化を可視化する ソースコードの変更前後で同じシナリオを実行したメソッド呼び出し履歴を取得 メソッドの呼び出し関係を木構造にして比較 動作の変化を可視化する 可視化にはAmidaを利用し，シーケンス図を生成する メソッド呼び出し履歴全体のシーケンス図を生成 動作の変化である部分を強調表示 そこで本研究では，2つのメソッド呼び出し履歴の比較を行い， 動作の変化を検出し，可視化する手法を提案します． 本手法では，まずソースコードを変更した前後で同じシナリオを実行した メソッド呼び出し履歴を取得し， メソッドの呼び出し関係を木構造にして比較を行い， 動作の変化を検出します． そして，Amidaを利用してシーケンス図を生成し， 動作の変化を可視化します． このとき，メソッド呼び出し履歴全体をシーケンス図にし， 動作の変化である部分を強調表示します．

木構造への変換 メソッド呼び出し履歴を木構造に変換する 1つのメソッド呼び出しを1つのノードにする メソッドの実行中に呼ばれたメソッドを子ノードとして親子関係を作る これをメソッド呼び出し関係木と呼ぶ B C D E A F G 2 3 4 1 5 6 2 3 4 1 5 6 まず，メソッド呼び出し履歴を木構造に変換します． このとき，1つのメソッド呼び出しを1つのノードにし， あるメソッドの実行中に呼ばれたメソッドは子ノードとして 親子関係を作ります． このシーケンス図の場合，オブジェクトAへの0という呼び出しを ノード0として木構造を作ります． オブジェクA0からはオブジェクトBへの１というメソッドと オブジェクトFへの5というメソッドがあるため， ノード0の子ノードは1と5になります． このとき先に呼ばれるメソッドを木構造の左側に配置します． そしてこれをメソッド呼び出し関係木と呼びます．

メソッド呼び出し関係木の比較 一方のメソッド呼び出し関係木の中から部分木を取り出し，一致する部分木があるか判定する トップダウン方式で比較していく 部分木が一致したら，ノードにマークをつける マークのついた部分木は変化していない部分である 全ての部分木で探索が終わったら比較が終わる 最終的にマークのないノードが変化した部分だとわかる 次に木構造の比較の説明です． 一方の木構造の中から部分木を取り出し， もう一方の木構造の中に一致する部分木があるかを判定して， 比較を行います． このとき，比較はトップダウンに行い， 一致する部分木が見つかると2つの部分木に， この部分木には一致するものがあるとマークをつけます． これが変化していない部分になります． この探索を全ての部分木で行います． 探索が終わった時点で，マークのないノードが 変化したメソッド呼び出しだとわかります．

部分木の一致条件 部分木T1 とT2 が以下の全てを満たすと一致する ノード ｒ1 と ｒ2 が以下の全てを満たすと一致する ｒ1 と ｒ2 の子ノードの数が一致する ｒ1 の i 番目の子ノード ｒ1i を根とする部分木 T1i と ｒ2の i 番目の子ノード ｒ2i を根とする部分木 T2i が一致する ノード ｒ1 と ｒ2 が以下の全てを満たすと一致する メソッド呼び出し名が等しい 引数の型が等しい 返り値の型が等しい 呼び出し元オブジェクトのクラス名が等しい 呼び出し先オブジェクトのクラス名が等しい 比較を行う際の部分木の一致条件について説明します． 部分木が一致する条件は， 部分木ラージT1とラージT2が以下の全てを満たすときとします． ・T1の根r1とT2の根r2が一致する ・r1とr2の子ノードの数が一致する ・r1のi番目の子ノードr1iを根とする部分木T1iとr2のi番目の子ノードr2iを根とする部分木T2iが一致する またこのときのノードr1とr2の一致する条件は以下の全てを満たすときとします ・メソッド呼び出し名が等しい ・引数の型が等しい ・返り値の型が等しい ・呼び出し元オブジェクトのクラス名が等しい ・呼び出し先オブジェクトのクラス名が等しい

メソッド呼び出し関係木の比較の例 左側の木の部分木に一致する部分木を探す 一致する部分のないノードは変化した部分とする ノード1と一致するノードを探す ノード1の子ノードが一致するか調べる ノード3の子ノードが一致するか調べる 一致する部分のないノードは変化した部分とする 実際に例を用いて説明します． この図では，番号が同じノードは一致するとします． 左側の四角で囲まれたノード1を根とする部分木の比較を行います． (クリック)まず木構造の根から比較していきます． ノード1とノード0は異なるため一致しません． (クリック)次にノード0の子ノードを見ていきます． するとノード1が同じであるため，根と同じノードが見つかります． ノード1の子ノードの数は共に2であるため，子ノードの数も一致します． (クリック)次に子ノードを根とする部分木の比較に移ります． 1番目のノードは共にノード2であり，子ノードがないため一致します． 2番目のノードは共にノード3なので，ノード3の比較に移ります． (クリック)図のとおり，ノード3の子ノードも一致するため， ノード3を根とする部分木も一致し， (クリック)ノード1を根とする部分木が一致するとわかりマークをつけます． (クリック)この図では他に一致する部分木がないため，残りの部分にはマークがつかず， 変化した部分とわかり強調表示を行います． 1 5 1 7 2 3 6 6 6 2 3 4 4

シーケンス図へ可視化 メソッド呼び出し履歴全体をシーケンス図にする 変化した部分を強調して表示 変化した部分を自動で探索 シーケンス図が巨大になると探すのが困難 変化した部分に関係する一連のメソッド呼び出しを抜き出す 1 2 3 4 5 6 3 5 6 比較が終わるとシーケンス図として可視化します． メソッド呼び出し履歴全体をシーケンス図として可視化し， 変化した部分を強調表示します． たとえば図のようにオブジェクト3からオブジェクト5への メソッド呼び出しとそれ以降のメソッド呼び出しが 変化した部分であるならその部分だけを赤色にして表示します． (クリック) また，シーケンス図のサイズが巨大になることを考慮し， シーケンス図の中から変化した部分を探索し，抽出して表示します． このときに，変化した部分に関係する一連のメソッド呼び出しを抜き出します． この図では，変化した部分はオブジェクト3から5へのメソッド呼び出し以降なので， 呼び出し元であるオブジェクト3から表示します． 抽出

適用実験 実験の目的 実験対象 評価方法 提案手法で実際にソースコードの変更による影響を確認する 画像編集ソフトJHotDrawのメソッド呼び出し履歴 バージョン7.3と7.3.1で同じシナリオを実行 プログラムを起動し，三角形を1つ描き保存せずに終了する 評価方法 バージョン間の変更点を発見できるか 本手法の適用実験を行いました． 実験の目的は，提案手法で実際にソースコードの変更による影響を 確認することです． 実験対象としては，画像編集ソフトのJHotDrawを選びました． 使用したのはバージョン7.3と7.3.1の2つです． この2つのバージョンで，プログラムを起動し，キャンバスに三角形を1つ描画し， 保存せずに終了するという簡単なシナリオを実行しました． 取得したメソッド呼び出し履歴は表のようになりました． メソッド呼び出しの数はバージョン7.3で55789個，バージョン7.3.1では49127個． （ファイルサイズはバージョン7.3で5580KB，バージョン7.3.1で4858KBでした．） バージョン イベント数 ファイルサイズ(KB) 7.3 55789 5580 7.3.1 49127 4858

実験結果 実際にソースコードの変更を動作の変化として表示できた ソースコードが変更されていないのに動作の変化があると判定された 3つのクラスで変更点を発見 新しいメソッドの追加(DefaultDrawingEditorクラス) メソッドの処理の変更(AbstractToolクラス) コンストラクタの処理の変更(DefaultDrawingViewクラス) ソースコードが変更されていないのに動作の変化があると判定された 実行時に派生クラスが変わっていたため 実験結果です． 取得したメソッド呼び出し履歴を比較し，メソッド呼び出し履歴が変化した部分を 調査した結果，バージョン間の変更点を見つけることができました． 発見したのは新しくメソッドが追加されたクラスと メソッドの処理が変更されたクラス，コンストラクタの処理が変更されたクラスの 3つを発見しました． 今回の実験では，変化した部分であると表示されたものの中に ソースコードが変更されていないのに動作が変化したものがありました． これは実行時に派生クラスのオブジェクトが変わっていたために， 呼び出し先オブジェクトのクラス名が違うと判断され，動作の変化と認識していました．

スクリーンショット これが今回Amidaを改造して実装したツールのスクリーンショットです． 図の上部にオブジェクトを並べます． そして図の中央がシーケンス図になります． また，右側の図はシーケンス図の縮小図になります． シーケンス図が巨大になるため，縮小表示しても巨大なサイズになります． 図のシーケンス図の赤色で表示された部分が変化した部分であると 本手法で判断された部分です．

考察 提案手法のメリット 全体の流れが追える ソースコードの変更以外での変化を捉えられる メソッドを追加したときにどのような影響が出たのかが分かる ソースコードの変更以外での変化を捉えられる 設定ファイルや入力データの変更による動作の変化 入力による振る舞いの変化の理解 バグ検出に応用 考察です． （プログラムの変更点を探すなら実行せずとも，） （ソースコードを解析すればいいのですが，） 本手法のメリットには， 全体の流れが追えるという点があります． たとえば，デバッグ作業のときにメソッド呼び出しを追加した場合， どのような影響が出たのか，を図で示すことができます． もう1つは，ソースコードの変更以外での変化を捉えることできるという点です． 同じソースコードでも設定ファイルの変更や 入力データの変更による動作の変化を検出することで， 振る舞いの変化を理解することができます． バグを探す際には入力の値を変えて実行し，動作を解析する必要があるため， 入力の異なるメソッド呼び出し履歴を集めて比較することで， バグ検出にも応用のできるかもしれません．

まとめ まとめ 今後の課題 木構造の比較に基づくメソッド呼び出し履歴の変化の可視化手法を提案した プログラムの変更による動作の変化を検出 検出した動作の変化をシーケンス図に視覚化 実験を行い，動作の変化からソースコードの変更点を発見した 今後の課題 比較計算にかかる時間の削減 アルゴリズムの改良 Amidaのループ圧縮処理と組み合わせる まとめです． 木構造の比較に基づくメソッド呼び出し履歴の変化の可視化手法を提案しました． 実験を行い，動作の変化からソースコードの変更点を発見しました． 今後の課題として， 探索アルゴリズムの改良があります． 現在の比較計算は実行に時間がかかりすぎるため， アルゴリズムを最適化することで改善できると考えています． また，Amidaのループ圧縮処理と組み合わせて， ノード数を減らし，計算にかかる時間を減らせられないかと考えています． 以上で発表を終わります．