プログラムの変更前後での 実行履歴の差分検出手法

Presentation on theme: "プログラムの変更前後での 実行履歴の差分検出手法"— Presentation transcript:

1 プログラムの変更前後での 実行履歴の差分検出手法
大阪大学大学院情報科学研究科 ○伊藤芳朗　渡邊結　石尾隆　井上克郎 大阪大学大学院情報科学研究科の伊藤です． 「プログラムの変更前後での実行履歴の差分検出手法 」というタイトルで 発表を始めます． よろしくお願いします． 2010/03/18

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

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

4 実行履歴 プログラム実行時のメソッド呼び出し系列 実行時に決定される情報が記録されている サイズが巨大になりがち
画像編集ソフトで簡単な操作をしただけで5万回のメソッド呼び出し @1 0 void org.jhotdraw.samples.draw.Main(0).main(java.lang.String[]){ @1 1 void org.jhotdraw.app.DefaultSDIApplication(1).<init>(){ @1 2 void org.jhotdraw.app.AbstractApplication(1).<init>(){ @1 } @1 3 void org.jhotdraw.samples.draw.DrawApplicationModel(2).<init>(){ @1 4 void org.jhotdraw.app.DefaultApplicationModel(2).<init>(){ @1 5 void org.jhotdraw.app.DefaultApplicationModel(2).setName(java.lang.String){ @1 6 void org.jhotdraw.beans.AbstractBean(2).firePropertyChange(){ 次に実行履歴について説明します． 実行履歴とは，プログラム実行時のメソッド呼び出しの系列を記録したものです． 実際に実行した情報を記録するため実行時に決定される情報が記録されます． 下の図がその例になります． このようにスレッド番号，タイムスタンプ，返り値の型，クラス名， オブジェクトID，メソッド名，引数の型といった情報が記録されています． しかし，実行履歴にも問題点があります． 実行履歴はサイズが巨大になりがちという点です． 実行履歴はプログラムの開始から終了までの間の メソッド呼び出しをすべて記録するため，膨大な量となってしまいます． そのため，実行履歴を解析した結果も巨大になってしまいます． 今回の実験で使用した画像編集ソフトの実行履歴は約5万回の メソッド呼び出しが記録されていました． @1 0 void org.jhotdraw.samples.draw.Main(0).main(java.lang.String[]){ クラス名 メソッド名 引数の型 返り値の型 スレッド番号 タイムスタンプ オブジェクトＩＤ

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

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

7 Amidaのスクリーンショット これがAmidaのスクリーンショットです． GUIの上部にオブジェクトを並べます．
また，右側はシーケンス図の縮小図になります． この図はループ圧縮処理を適用した結果であり， この青で囲まれた部分がループを圧縮している部分を示しています．

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

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

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

11 木構造への変換 実行履歴をメソッド呼び出し関係木に変換する 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を配置します． オブジェクトAからはオブジェクトBへの１というメソッドと オブジェクトFへの5というメソッドがあるため， ノード0の子ノードは1と5になります． このとき先に呼ばれるメソッドを木構造の左側に配置し， 順序木とします． メソッド呼び出し関係木

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

13 部分木の一致条件 部分木の一致条件 ノードの一致条件 部分木の形状が完全に一致する 2つの木の対応する位置にあるノードが1対1で対応する
呼び出し元のオブジェクトが一致する メソッド呼び出しイベントが一致する メソッド呼び出し名，オブジェクト名，引数の型，返り値の型が全て一致する スレッド番号，タイムスタンプ，オブジェクトIDは実行履歴ごとに異なるため一致条件に使用しない 比較を行う際の部分木の一致条件について説明します． 部分木の一致には以下の点を調べて判定します． 部分木の形状が完全に一致するか． 部分木に含まれる全てのノードが1対1で対応しているか． このときのノード同士の一致は以下の情報から判定します． 呼び出し元のオブジェクトが一致するか． ノード同士のメソッド呼び出し名，オブジェクト名，引数の型， 返り値の型が一致するかです． スレッド番号，タイムスタンプ，オブジェクトIDは実行履歴ごとに 異なる可能性があるため，一致の条件には使用しません．

14 メソッド呼び出し関係木の比較の例 左側の木の部分木に一致する部分木を探す 一致する部分のないノードは変化した部分とする
ノード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

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

16 スクリーンショット これが今回Amidaを改造して実装したツールのスクリーンショットです．
この図の赤色で表示された部分が変化した部分であると 本手法で判定された部分です． 右側の縮小図でも同様に赤色で表示します．

17 適用実験 実験の目的 実験対象 提案手法で実際にソースコードの変更による振る舞いの変化を確認する 画像編集ソフト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

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

19 実験対象の詳細 JHotDrawのバージョン間の変更 取得した実行履歴 変更があったのは全部で45個のクラス
「メソッド呼び出しに影響のある変更がされたクラス」について調査 実験では3個のクラスを全て発見することができた コメントのみの変更 15 メソッド呼び出しに影響のない変更 8 メソッド呼び出しに影響のある変更 22 実行履歴に現れなかったクラス 12 変更されたメソッドが呼び出されなかったクラス 7 変更されたメソッドが呼び出されたクラス 3 実験対象であるJHotDrawについて調べてみました． まず，2つのバージョンで変更があったのは全部で45個のクラスでした． そのうちコメントのみが変更されていたのが15個， メソッド呼び出しに影響がない変更がされたのが8個のクラスで， 残りの22個のクラスはメソッド呼び出しに影響がある変更がされていました． 次に取得した実行履歴について調べてみました． メソッド呼び出しに影響がある変更がされた22個のクラスを実行履歴の中から探したところ， 10個のクラスを見つけることができました． そのため，実行履歴に現れなかったクラスは22個でした． さらに10個のクラスのメソッド呼び出しを調べたところ， 7個のクラスでは変更されたメソッドは呼び出されていませんでした． そのため，変更されたメソッドが呼び出されていたのは3個のクラスでした． 今回の実験ではこの3個のクラスをツールからもらさず見つけることができました． （メソッド呼び出しに影響がない変更：定数名の変更，import文の削除など）

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

21 提案手法の現状と今後の課題 実行時間の削減 マルチスレッドへの対応 クラス名の変更への対応 今後の課題としては以下の3つの点があります．
1つ目は実行時間の削減． 2つ目はマルチスレッドへの対応． 3つ目はクラス名の変更の対応． この3つについて現状と対策の説明をします．

22 実行時間の削減 比較計算に時間がかかる 対策 実験で使用した実行履歴で約11分 ハッシュを使用する Amidaのループ圧縮と組み合わせる
前処理として部分木のハッシュ値を求め，比較を行う Amidaのループ圧縮と組み合わせる ループ圧縮によりメソッド呼び出し関係木のノード数を減らす ループ圧縮にも計算時間が必要なため，効果を調べる必要がある まず，1つ目の実行時間の削減です． 現在の比較計算には計算に時間がかかりすぎるという欠点があります． 今回の実験で使用した実行履歴の比較では比較計算だけに約11分かかっていました． ツールの利便性を上げるためにもっと早い時間で比較を行う必要があります． 対策としては，ハッシュ値を計算する方法を考えています． 比較の前処理で各部分木のハッシュ値を求めておき，比較を行う際には ハッシュ値を使うことで比較にかかる時間を減らすことができます． もう1つの方法として，Amidaのループ圧縮処理と組み合わせる方法を考えています． ループ圧縮によりメソッド呼び出し関係木のノード数を減らすことで， 比較計算にかかる時間を減らすことができます． ただし，この方法ではループ圧縮の処理に計算時間が必要となるため， 全体として効果的なのか，もしくは，どのような状況で効果的かを調べる必要があります．

23 マルチスレッドへの対応 スレッド名が同じスレッドを比較 対策 スレッド単位でメソッド呼び出し関係木を構築し比較
スレッド名を変更されると比較計算ができない 対策 どのスレッドがどこで生成されたかを解析する スレッドオブジェクトのコンストラクタ呼び出しで区別 呼び出し元が同じスレッド同士を比較する スレッド名が変わっても対応が取れる 2つ目は，マルチスレッドへの対応です． 現在，複数のスレッドが実行履歴中に存在する場合， スレッドごとにメソッド呼び出し関係木を構築しています． そして，比較を行う際にはスレッド名が同じスレッドを比較しています． しかし，この方法ではプログラムが変更したときに スレッド名が変更してしまうと比較計算が行われません． そこで，対策として，どのスレッドがどこで生成されたかを解析します． そして，スレッドオブジェクトのコンストラクタ呼び出しをしているメソッドを取得し， 呼び出し元のメソッドが同じスレッド同士を比較します． こうすることで，スレッド名が変わってもスレッドの対応が取れるのではないかと考えています．

24 クラス名の変更への対応 クラス名だけが変わり，内部の振る舞いが変わっていない場合 対策 現在は全て変化として表示
「クラス名の変更も変化として表示すべき」 クラス名の変更以外の変化が分かりづらくなる 対策 比較時に変更情報を与える クラス名が違っても振る舞いが同じならば変化と判定しない 変更情報を事前に知る必要がある 最後に，クラス名の変更への対応です． クラス名だけが変わり，内部の振る舞いが変わっていない場合， 現在は「クラス名の変更も変化として表示すべきである」とし， 全て変化として表示を行います． しかし，クラス名の変更が分かっている場合では， クラス名の変更以外の変化があるのかわかりづらくなります． そのため，クラス名の変更に対応して変化の表示を行うことができるようにしたいと考えています． 対策として，比較を行うときに，クラス名の変更情報を与えます． 与えられた変更情報を用いて比較を行い， クラス名が違っても振る舞いが同じならば変化と判定しないようにします． ただし，この方法では変更情報を事前に知る必要があります．

25 まとめ まとめ プログラムの変更前後での実行履歴の差分検出手法を提案した 実験を行い，動作の変化からソースコードの変更点を発見した
プログラムの変更による動作の変化を検出 検出した動作の変化をシーケンス図に視覚化 実験を行い，動作の変化からソースコードの変更点を発見した 3個のクラスの変更を発見できた まとめです． プログラムの変更前後での実行履歴の差分検出手法を提案しました． 実験を行い，動作の変化からソースコードの変更点を発見しました． 以上で発表を終わります．

26 終

27 メソッド呼び出し履歴の例 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>(){ ここで実行履歴の例を挙げます． 実行履歴はこのように，帰り値の型，パッケージ名，クラス名， オブジェクトID，メソッド名，引数の型といった情報が記録されています． これはあるプログラムを実行したときの実行履歴の先頭部分だけを 抜き出したものですが，これだけでもどのような動作が 行われているのかを理解するのは困難です． さらに，実際に取得した実行履歴には膨大な数のメソッド呼び出しが 記録されているため，それを理解するのはより困難になります．

28 Amidaのスクリーンショット ここで実行履歴からシーケンス図を生成する例として，
AmidaはJavaプログラムを対象としたシステムで，プログラムを動的解析し， 実行履歴を取得します．そして，その実行履歴からシーケンス図を生成します． また生成したシーケンス図を解析し，ループや再起呼び出しとなる部分を 圧縮し表示する機能を持ちます．

29 シーケンス図の生成 メソッド呼び出し履歴のメソッド間の呼び出し関係からシーケンス図の生成 A(1).a() { B(1).b() {
C(1).c1() { } C(2).c2() { D(1).d1() { D(1).d2() { B-1 C-1 C-2 D-1 A-1 シーケンス図 メソッド呼び出し履歴

30 実行履歴の変化の要因 同じシナリオを実行しても実行履歴が変化する場合がある ソースコードの変更 実行環境の変化 入力データの変化
メソッド呼び出しの追加や削除 実行環境の変化 実行環境ごとに動作を変えている 入力データの変化 外部ファイルのデータによって処理が変わる

31 diffコマンドを用いた比較 1362c1362 690 void org.jhotdraw.draw.DefaultDrawingView$2(75).<init>(org.jhotdraw.draw.D --- 690 void org.jhotdraw.draw.DefaultDrawingView(71).initComponents(){ 1364c1364,1366 691 void org.jhotdraw.draw.DefaultDrawingView(71).initComponents(){ 691 org.jhotdraw.draw.DefaultDrawingView$EventHandler org.jhotdraw.draw.Defa 692 void org.jhotdraw.draw.DefaultDrawingView$EventHandler(75).<init>(org.jhot 693 void org.jhotdraw.draw.DefaultDrawingView$EventHandler(75).<init>(org.jhot 1366,1368d1367 692 org.jhotdraw.draw.DefaultDrawingView$EventHandler org.jhotdraw.draw.Defa 693 void org.jhotdraw.draw.DefaultDrawingView$EventHandler(76).<init>(org.jhot 694 void org.jhotdraw.draw.DefaultDrawingView$EventHandler(76).<init>(org.jhot 1370a1370 694 void org.jhotdraw.draw.DefaultDrawingViewTransferHandler(76).<init>(){ 1372c1372 695 void org.jhotdraw.draw.DefaultDrawingViewTransferHandler(77).<init>(){ 695 void org.jhotdraw.draw.DefaultDrawingView(71).setBackground(java.awt.Colo これはバージョンの異なるプログラムで同じシナリオを実行した メソッド呼び出し履歴を取得し，それをdiffコマンドを使って比較した結果の一部です． このように，違いがあるのはすぐにわかりますが，具体的にどこが変化したのかを 把握するのは困難です． この例では，2行目のメソッド呼び出しが1つ追加されています． そのため，それ以降のメソッド呼び出しでメソッド呼び出しのカウントとオブジェクトIDが変わり， 多くの違いが出現しています．

32 部分木の一致条件 部分木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の一致する条件は以下の全てを満たすときとします ・メソッド呼び出し名が等しい ・引数の型が等しい ・返り値の型が等しい ・呼び出し元オブジェクトのクラス名が等しい ・呼び出し先オブジェクトのクラス名が等しい

33 オブジェクトの違いによる動作の変化 呼び出し先オブジェクトはクラスBかCになる public abstract class A{
public abstract int getNo(); } public class D{ public void init(A a){ ･･･ i = a.getNo(); } public class B extends A{ public int getNo(){ ･･･ } 呼び出し先オブジェクトはクラスBかCになる 実行時に決まる 実行履歴には実行時のオブジェクトが記録される public class C extends A{ public int getNo(){ ･･･ }

34 スクリーンショット（比較対象）

35 スクリーンショット（変化）

36 コメントのみの変更 15 メソッド呼び出しに影響のない変更 8 メソッド呼び出しに影響のある変更 22 変更箇所を発見できたクラス 3 変更箇所変更を発見できなかったクラス 7 実行履歴に現れなかったクラス 12