情報処理学会研究報告
IPSJ SIG Technical Report

1. ま え が きプログラムの変更前後での実行履歴の差分検出手法

開発者は，デバッグ作業などにおいてソースコードを変更したとき，プログラムの振舞いの変化が意図したものであるかを確認する必要がある．そのために，ソースコードを変更

伊
石

藤
尾

芳

朗†1
隆†1

渡 邊
結†1
井 上 克 郎†1した前後で同じ操作手順を実行し，振舞いの差異を調査することになるが，欠陥の修正によってデータの値などが変化した影響は，様々なデータを経由してプログラムの出力などに間接的に影響を与える3) ため，直接の観測が難しい 場合がある．一方で，オブジェクト指
向プログラムの振舞いを理解するためには，プログラムの実行を観測し，実際の振舞いを開発者は，デバッグ作業などにおいてソースコードを変更したとき，プログラムの振舞いの変化が意図したものであるかを確認する必要がある．そのために，ソース
コードを変更した前後で同じ操作手順を実行し，振舞いの差異を調査することになるが，外部から観測が困難な変更については，実行中に生じる膨大な量のメソッド呼び出しの系列を比較するなどの作業が必要である．そこで本研究では，ソースコードを変更した前後で同じ操作手順を実行して得られた 2 つの実行履歴に対して，それらの間の差分を木構造の比較により検出，可視化する手法を提案する．画像編集ソフト
JHotDraw を対象にケーススタディを実施した結果，可視化された差分と，バージョン間の変更点を対応づけられることを確認した．

可視化することが有効であることが知られている19) ．実行時の振舞いの変化を可視化することでソースコードの変更による直接的な影響を確認可能するために，実行履歴を記録し，その変化を可視化することが有効であると考えられる．
本研究では，ソースコードを変更した前後で同じ操作手順を実行して実行履歴を取得し，その実行履歴の差分を検出する手法を提案する．検出した実行履歴の差分を可視化することで，プログラムの振舞いの変化が意図したものと一致しているかを判断することが可能になる．具体的には，取得した 2 つの実行履歴中のメソッド呼び出し関係をそれぞれ順序木によって表現し，2 つの木の比較を行うことで実行履歴の差分を検出する．実行履歴を可視化

Detecting Diﬀerence between the Execution Trace
Extracted from Two Versions of a Program

する際には，利用者がわかりやすいように実行履歴の差分を強調表示する．また，実行履歴の差分を抽出することでプログラムの振舞いの変化を発見しやすくする．本手法の対象とするソースコードの変更の場面は主にデバッグ作業を想定している．デバッグ作業によるソー

Yoshiro Ito,†1 Yui Watanabe,†1 Takashi Ishio†1and Katsuro Inoue †1

スコードの変更では，差分は小さくなると考えられるため，木構造の差分だけを検出し，可視化する．
我々の研究グループでは，java プログラムの実行履歴からシーケンス図を生成するシス

It is necessary to conﬁrm whether the change of behavior of a program isintended when developers modify souce code for debugging. To check the difference of the behavior of the program, they execute the modiﬁed program under the same operating condition. However, it is necessary to compare a hugeamount of method call events in execution traces when they can not directly
observe their behavior. This paper proposes a method to detect and visualize
the diﬀerence by comparing tree structures between the two execution traces
that are obtained by executing the two versions of a program under the same
operating condition. We conducted a case study for a drawing editor JHotDraw. As a result, we conﬁrm that the visualized diﬀerence of the execution
traces corresponding to the source code diﬀerence.

テム Amida20) を開発している．本研究ではこの Amida を改造することで提案手法を実装した．そして，実際に画像編集ソフト JHotDraw9) の 2 つのバージョンで同じシナリオを実行した実行履歴を取得し，提案手法を適用した結果，表示された差分から 2 つのバージョン間での変更の影響を特定できることを確認した．
以降，2 節ではこの研究の背景を述べ，3 節で提案手法の説明をする．4 節では行ったケー
ススタディとその結果について述べ，5 節では関連研究を紹介する．最後に 6 節で本研究の†1 大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka University1

c 2010 Information Processing Society of Japan情報処理学会研究報告
IPSJ SIG Technical Report
1:A
a()

2:B
b()

3:C

c()

<init>()

4:D<init>()

5:D

d()
d()

図1

シーケンス図まとめと今後の課題を述べる．

2. 背

図2

シーケンス図生成システム Amida

景
した実行履歴を基にシーケンス図の生成を行うツール Amida を開発している20) ．Amida

2.1 オブジェクト指向プログラム
オブジェクト指向プログラムでは，クラスを用いて処理の抽象化を行い，また継承や多態

は Java プログラムのメソッド呼び出しを実行履歴として取得するプロファイラと，その実性などを利用して，オブジェクト間のメソッド呼び出しによってソフトウェアの機能を実現

行履歴を解析してシーケンス図を生成，表示するビューアからなるツールである．図 2 はする．このようなシステムの振舞いを理解するためには，ソースコードのような静的な情報

Amida のスクリーンショットで，図の左側にシーケンス図が表示されている．ただし，実を解析する手法と，実行履歴のような動的な情報を解析する手法がある．ソースコードを解

行履歴から生成したシーケンス図は巨大なサイズになってしまうため，上部にオブジェクト析する手法では動的束縛などの動作を完全には知ることができない場合があるため，実際にを表示し，その下にシーケンス図の一部分を表示する．図の右側はシーケンス図の縮小図をソフトウェアを実行し，どのオブジェクトが呼び出されたかを記録した実行履歴を解析する表している．また，Amida にはシーケンス図上の繰り返し処理や再起呼び出しなどのルー手法が有効であり19) ，実行履歴をシーケンス図などの形式で可視化する手法が広く研究さ

プの部分を圧縮して表示する機能が実装されている．

4),18),20)

れている

．

2.3 実行履歴の比較

シーケンス図は Uniﬁed Modeling Language(UML)17) で定義されているインタラクショ

プログラムの実行履歴は実行時の動作を記録したものであるため，利用者が同じシナリオ

ン図の 1 つで，オブジェクト間のメソッド呼び出しやオブジェクトの生成などのメッセージで実行しても実行履歴が変化する場合がある．その要因はソースコードの変更，実行環境の通信を，時系列に沿って示した図である．この図を作成することで，設計者はシステムが実変化，入力データの変化の 3 つに分類できる．

際に動作する際のオブジェクト間の関連を，他の設計者や開発者に示すことが可能である．

ソースコードが変更された場合，変更に応じてプログラムの振舞いが変わるため，実行履

プログラムの振舞いの可視化の研究においても，その動作を示すために利用されている．

歴が変化する．例えば，メソッド内にメソッド呼び出しを 1 つ追加すると，追加されたメ

2.2 Amida

ソッド呼び出しと，そのメソッド内で呼び出される他のメソッド呼び出しが実行履歴に追加

我々の研究グループは，オブジェクト指向プログラムにおけるオブジェクト実行時の振される．また，メソッドのオーバーライド関係の変更を行うと，呼び出し側のコードが変更
されていなくとも，動的束縛によって動作が変わることがある．

舞いを視覚的に表現し，プログラムの理解支援を行うために，プログラムの実行時に観測

2c 2010 Information Processing Society of Japan情報処理学会研究報告
IPSJ SIG Technical Report

同じ実行をした 2 つの実行履歴を比較した場合，実行履歴の差分が検出されたときに，そ対象とするプログラムの実行を観測し，オブジェクト間のメソッド呼び出しに関する情報を

こになんらかの変化があり，その変化に注目することで，ソースコードの変化や入力データ記録する．本手法では，Amida のプロファイラを使用して実行履歴を取得する．Amida での変化などのプログラムの振舞いの変化の要因を発見できると考えられる．

は，個々のメソッド呼び出しについて，メソッド開始時にスレッド番号，タイムスタンプ，本研究では，実行履歴の変化の要因のうち，デバッグ作業におけるソースコードの変更に

クラス名，オブジェクト ID，メソッド名，引数の型，返り値の型を呼び出された順に記録よるものを取り扱う．欠陥の修正によるメソッド呼び出しやデータの値などの変化は様々なする．コンストラクタの呼び出しは，<init>という名前のメソッド呼び出しとして表現してデータを経由してプログラムの出力などに間接的に影響を与える3) ため，ソースコード編

いる．また，メソッド終了時には終了記号を記録する．引数の型を記録するのは，メソッド集による直接の影響を確認しておくことが，修正の妥当性を確認するために重要となる．

がオーバーロードされて同名のメソッドが複数存在する場合に，メソッドを特定するためでプログラムの開始から終了までのすべてのメソッド呼び出しを記録すると，膨大な量になあり，実行時に引数として与えられた値については記録しない．これらの情報を用いることることが知られている12),14),15) ．しかし，バグ修正におけるソースコードの変更は，多くで，実行時に呼び出されたオブジェクトとメソッドを特定し，メソッド間の呼び出し関係を

7)の場合 1 つあるいは 2 つのファイルに対するものであり ，実行履歴の変化は，実行履歴全木構造に変換することが可能となる．

体の中でもごく一部にのみ現れるものであると推測される．そのため，実行履歴の差分を自

3.2 メソッド呼び出し関係木の構築
最初に，取得した実行履歴を，メソッドの呼び出し関係を表現した順序木に変換する．実

動的に検出，可視化することにより，ソースコード編集による影響を，開発者が効果的に確

行履歴は，呼び出された全てのメソッドの開始と終了を記録しているため，あるメソッド

認することが可能であると期待される．

M1 が別のメソッド M2 を呼び出す場合，実行履歴の中では，メソッド M1 の開始，メソッ

3. 提 案 手 法

ド M2 の開始，メソッド M2 の終了，メソッド M1 の終了の順に記録される．そのため，

本研究では，2 つの実行履歴を比較し，実行履歴の差分の位置を特定する手法を提案する．

メソッドの開始と終了の順序から全てのメソッドの呼び出し関係が分かる．このメソッド呼び出し間の関係を木構造にし，これをメソッド呼び出し関係木と呼ぶ．

特定した実行履歴の差分を可視化することで，ソースコードの変更によるプログラムの振舞

メソッド呼び出し関係木のノードは実行履歴に記録されている 1 つのメソッド呼び出しいの変化が意図したものと一致しているかを判断することが可能になる．具体的には，取得した実行履歴からオブジェクト間のメソッド呼び出し関係を取得し，順序木に変換する．

イベントとする．実行履歴中で，あるメソッド M1 が直接メソッド M2 を呼び出している

そして，ソースコードの変更前後の順序木の実行履歴の比較を行い，ノード間の対応関係を場合，メソッド M1 の呼び出しを親，メソッド M2 の呼び出しを子とする．また，あるメ求めることで実行履歴の差分を検出する．

ソッド M1 がメソッド M2 とメソッド M3 を M2 ， M3 の順で呼ぶとする．このとき，メ
ソッド M2 と M3 の呼び出される順番を，そのままノードの順序として保存する．

検出した実行履歴の差分をシーケンス図を用いて可視化することで利用者に分かりやす
い形で提供する．ただし，可視化する際に実行履歴の差分だけを可視化しても，その部分が3.3 実行履歴の差分の検出

どのような状況で呼び出されたのかが判断できないため，実行履歴全体をシーケンス図とし次に，2 つの実行履歴から得られた 2 つのメソッド呼び出し関係木の比較を行う．ソースて生成し，実行履歴の差分を強調して表示する．また，実行履歴が膨大になることを考慮

コードの変更や実行環境の変化，入力データなどの要因により実行履歴は変化するが，デし，可視化した実行履歴の中から振舞いが変化した部分のみを抽出した可視化も行う．

バッグ作業におけるソースコードの変更によって生じる変化は小さいと仮定し，メソッド呼提案手法は，Java プログラムの実行履歴を可視化するシステムである Amida の存在をび出し関係木の比較には，トップダウン方式を採用し，木の根から順番に処理を進めていく．

念頭に置いて，Java プログラムの実行履歴に対応した手法となっているが，同様のメソッ

メソッド呼び出し関係木の比較では，一方のメソッド呼び出し関係木から部分木を取り出し，もう一方のメソッド呼び出し関係木からその部分木と一致する部分を探索する．部分木

ド呼び出し情報が取得可能な実行環境を持つプログラミング言語などにも適用可能である．

3.1 実行履歴の取得

Ta と Tb があり，それぞれの根となるノードを ra ，rb とするとき，2 つの部分木が等しい

提案手法が対象とする実行履歴は，実行されたメソッド呼び出しイベントの系列である．

条件は以下のように設定する．

3

c 2010 Information Processing Society of Japan情報処理学会研究報告
IPSJ SIG Technical Report

T1• ノード ra と rb が等しい．
• ra と rb の子ノードの数が等しい．

1• ra の i 番目の子ノードを根とする部分木と rb の i 番目の子ノードを根とする部分木が等しい．

2

ここで，ノード ra と rb が等しいとは，次の 2 つの条件を両方とも満たす場合である．

㽢

0

6

4

• ノード ra と rb のクラス名，メソッド名，引数の型名の列，戻り値の型名が等しい．
• ノード ra と rb の呼び出し元クラス名（ra と rb の親ノードのクラス名）が等しい．

0

1

5
3

T2

2

7
3
4

図 3 メソッド呼び出し関係木の比較

なお，クラス名や型の一致は，完全限定名の比較により判定する．
ノードの一致条件には，オブジェクト ID を使用しない．オブジェクト ID はメモリアド

3.4 実行履歴の差分の可視化

レスと生成順序を元に付与されるので，複数のスレッドが同時に実行される状況では同じ役

実行履歴の変化を検出したときに，変化部分をそのまま利用者に提示しても，オブジェク

割のオブジェクトでも実行ごとにオブジェクト ID が変わってしまう可能性があるためであト間のメッセージ通信や，他のオブジェクトとの関連性を理解することは難しい．そこで，る．オブジェクト ID を比較しても，2 つのメソッド呼び出し関係木から同じ動作をするオ

実行履歴をシーケンス図として可視化し，変化となる部分を強調して表示する．
シーケンス図の生成手法は Amida20) を参考にし，3.3 節で求めたマークの有無で強調表

ブジェクトの対応をとることができない．
部分木の一致の条件から，等しい部分木の探索にはまず根となるノードと等しいノードを示を行うかどうかを判定する．本手法では，メソッド呼び出し関係木のノードは 1 つのメ探索する．図 3 は 2 つの部分木が等しいかを探索する例である．図中のノードの番号が等

ソッド呼び出しであり，ノード単位で変化部分であるかどうかの検出を行う．そのため，強しいとき，ノードの一致条件を満たしているとする．図の T1 のうち四角形で囲まれた部分

調表示をするノードをシーケンス図にする際に，そのノードのオブジェクトへのメソッド呼木が，T2 の中に一致する部分木があるかを探索する．まず，根であるノード 1 と一致する

び出しと呼び出されたオブジェクトの実行区間を強調して表示する．また，強調表示はシーノードを探索する．この探索はトップダウンに行うため，まず部分木 T2 の根であるノード

ケンス図上で表示する色を変えることで行う．

0 と等しいか判定を行う．しかし，この 2 つのノードは一致しないため，ノード 0 の子ノー

図 4 は図 3 にメソッド呼び出し関係木で示した 2 つの実行履歴をそれぞれシーケンス図

ドに移る．次のノードは共に 1 であるため，根となるノードと等しいノードを発見することとして可視化し，実行履歴上の変化を強調表示したものである．図 4 では，ノード i をオブができた．ここで，発見したノードが根となる部分木が探索したい部分木と一致するかを判

ジェクト i へのメソッド呼び出しとして記述している．図 3 のノード 1 を根とする部分木

定する．根となる 2 つのノードの子ノードの数を調べると共に等しいため，子ノードを根とは一致するとマークされるため，オブジェクト 0 からオブジェクト 1 への呼び出しとオブする部分木がそれぞれ等しいかの判定を行う．同様に，ノード 2 を根とする部分木とノージェクト 1 からオブジェクト 2，3 への呼び出し，オブジェクト 3 からオブジェクト 4 へのド 3 を根とする部分木が一致するかを判定する．図 3 では，ノード 2 を根とする部分木と呼び出しは通常の表現で記述する．しかし，メソッド呼び出し関係木のそれ以外のノードはノード 3 を根とする部分木は共に等しいため，部分木 T1 と T2 に含まれるノード 1 を根と一致する部分がないため，図 4 のように赤色で強調表示を行う．

する部分木は等しいと分かる．一致する部分木が見つかった場合，2 つの部分木に含まれる

3.5 実行履歴の変化部分の探索と抽出表示

全てのノードに一致する部分があることをマークしておく．

可視化したシーケンス図のサイズが巨大であれば，差分も膨大な数になる可能性がある．

この後，他の全ての部分木でも同様の探索を行う．全ての部分木で探索が終わったときそこで，可視化したシーケンス図から差分を取り出して表示を行う．このとき，メソッド呼に，一致する部分木があれば，その部分木に含まれるノードはマークされている．そのたび出し関係木内のノードを全て調べることで実行履歴の差分を探索する．ただし，該当する

め，マークされていないノードは一致する部分がない，すなわち，実行履歴の変化部分であメソッド呼び出しだけを表示すると，呼び出し元となるオブジェクトやその前後のメソッドると分かる．

呼び出しが分からないため，実用性に欠ける．そのため，差分として検出されて部分木の親4

c 2010 Information Processing Society of Japan情報処理学会研究報告
IPSJ SIG Technical Report
0

1

2

3

4

5

T1

6

0

1

2

3

4

実行した実行履歴を取得した．

7

T2

実験に使用したシナリオは以下の通りである．

(1)

プログラムを起動する．

(2)

三角形描画のボタンをクリックする．

(3)

キャンバスの中央でマウスをドラッグし三角形を描画する．

(4)

Alt キーと F4 キーを同時に押してウィンドウを閉じる指示を出す．(Microsoft Windows において Alt+F4 はウィンドウを閉じるショートカットキーである．)

図 4 シーケンス図の比較(5)

編集した図形データを保存するかどうかを問い合わせるダイアログが表示されるので，「保存しない」をクリックし，プログラムを終了する．

ノードを根とする部分木の単位で，シーケンス図による可視化を行うものとした．このとき実行履歴を取得する際には，java，javax，sun のパッケージに含まれるライブラリへのに，親となるオブジェクトへのメソッド呼び出しが同一の場合，同一のシーケンス図が複数表示されないように重複したメソッド呼び出しを表示しないようにする．

呼び出しを除外した．
シナリオを実行し，取得した実行履歴の概要を表 1，2 に示す．表 1 では，取得した実行

3.6 マルチスレッドへの対応方法

履歴全体のデータを，表 2 では，実行履歴のうちのスレッドごとのデータを示している．

マルチスレッドで実行されたプログラムについては，スレッド単位でメソッド呼び出し関係木を構築する．Java プログラムの場合は，スレッドオブジェクトに名前が与えられるた

4.2 実 験 方 法め，そのスレッド名の対応関係により，同一名称のスレッドの呼び出し関係木の間で比較を取得した実行履歴に Amida を改造して作成したツールを適用し，出現した実行履歴の差行うものとした．スレッドの生成処理が変更されない限り，スレッドの名前は複数回の実行分から，実際にソースコードが変更されている箇所を特定できるか確認をする．

でほとんど変化がなく，著者らのこれまでいくつかのプログラムに対して分析を行ってきた

4.3 実 験 結 果

経験の範囲では，スレッドの名前を用いた対応関係により問題を生じたことがない．

2 つの実行履歴の比較を行い，差分の表示を行った．実行履歴の比較とシーケンス図の生
成までの実行時間を調査したところ，およそ 11 分 30 秒かかった．

使用するスレッドの数が状況によって変わるようなプログラムではこの方式は採用できな
いため，スレッドの取りうる組に対してメソッド呼び出し関係木の比較を行い，一致するノード数が多いものを対応関係で結び付ける必要がある．それぞれのメソッド呼び出し関係バージョン

木の根のノードから順番にメソッド呼び出しを比較していくアルゴリズムであるため，同一

表1
スレッド数

7.3
7.3.1

のスレッド生成処理で作られたスレッド間での比較以外には，スレッドの対応関係の計算のコストは，それほど大きな問題とはならないと推測している．

4
4

取得した実行履歴
イベント数
ファイルサイズ (byte)

55,78949,127

5,713,797
4,974,072

表 2 スレッドごとの実行履歴の内訳
バージョン
スレッド名
イベント数

4. ケーススタディ

7.3

本手法によって，2 つの実行履歴の差分を検出し，可視化が行えているかを確認し，差分として検出された部分から実際にソースコードが変更を確認できるかを調べるために適用
7.3.1

実験を行った．

4.1 実 験 対 象
実験対象として画像編集ソフト JHotDraw9) のバージョン 7.3 と 7.3.1 で同じシナリオを

5

main
AWT-EventQueue
Thread-3pool-1-thread-1
main
AWT-EventQueue
Thread-3pool-1-thread-1

21
55,651
2
116
21
48,9892116

c 2010 Information Processing Society of Japan情報処理学会研究報告
IPSJ SIG Technical Report

2 つの実行履歴に含まれるスレッド数は共に 4 であり，同じスレッド名を持つスレッド同士で比較を行った．このとき，4 個のスレッドのうち，main，Thread-3，pool-1-thread-1の 3 個のスレッドでは，全てのメソッド呼び出しが一致しており，差分は見つからなかった．
スレッド AWT-EventQueue では，差分が検出されたので，このスレッドでの実行履歴の差分を参考に，ソースコードの変更点を探した．探す際に，実行履歴の差分の探索機能を使用したが，発見された差分は 300 箇所以上あったため，探索は途中で終了した．
その結果，実際に差分からソースコードの変更点を発見することができた．具体的には，

org.jhotdraw.draw.AbstractTool クラスと org.jhotdraw.draw.DefaultDrawingEditor クラス，org.jhotdraw.draw.DefaultDrawingView クラスの 3 つである．

AbstractTool クラス
AbstractTool クラスでは，バージョン 7.3 から 7.3.1 に変わるときに，メソッド createActionMap の処理が変更された．具体的には，バージョン 7.3.1 ではメソッドの中の処理を全て削除し，null 値を返すだけになっていた．そのため，バージョン 7.3 では，メソッド

createActionMap の呼び出しから他のメソッド呼び出しを行っていたが，バージョン 7.3.1
では，メソッド createActionMap が呼び出されてすぐに終了している．

DefaultDrawingEditor クラス

図5

DefaultDrawingEditor クラスでは，バージョン 7.3 から 7.3.1 に変わるときに，新しくDefaultDrawingEditor クラスの変更による実行履歴の変化

メソッドが 6 つ追加され，うち 2 つのメソッドがコンストラクタから呼び出されていた．そのため，コンストラクタ呼び出しで 2 つのメソッド呼び出しが増え，そのメソッド呼び出し歴に記録され，本手法で差分と判断された．

が差分であると判断された．

その他の変化の検出

図 5 は実際に生成したシーケンス図である．DefaultDrawingEditor クラスのコンストラク

今回の適用実験では，多くの差分を検出し，そこから 3 つのクラスのソースコードの変タ呼び出しの処理の一部であるが，メソッド setDefaultAttribute の呼び出しは変更されてい更を発見したが，その他にもソースコードの変更とは関係がない実行履歴の差分を複数検ないため強調表示されていないが，メソッド createInputMap とメソッド createActionMap

出した．その原因はソースコードの変更が変更されていないクラスに影響を与えたことでの呼び出しは変更されているため，強調表示されている．またメソッド createActionMap

あった．具体的には IncreaseHandleDetailLevelAction クラスの初期化処理の動作が変わっでは，さらに DeleteAction クラスのコンストラクタを呼び出しているが，メソッド create-ていた．IncreaseHandleDetailLevelAction クラスのコンストラクタは DrawingEditor ク

ActionMap は新しく追加されたメソッドなので赤色に強調表示されている．

ラスが引数に指定されているが，バージョン 7.3 の実行時には DrawingEditorProxy クラ

DefaultDrawingView クラス

スのオブジェクトが，バージョン 7.3.1 では，DefaultDrawingEditor クラスのオブジェク

DefaultDrawingView クラスでは，バージョン 7.3 と 7.3.1 の間でコンストラクタの呼びトが渡されていた．その結果，呼び出し先オブジェクトのクラス名が異なるため，差分と判断されていた．

出しに変化があった．実際には，コンストラクタ内での処理は変わっていなかったが，クラス内のメンバ変数が変更されていた．そのため，コンストラクタの呼び出しが行われた際

4.4 考に，メンバ変数の初期化の処理がバージョン間で異なっていた．その動作の変化が，実行履

適用実験では，3 つのクラスで変更箇所を発見することができた．今回取得した実行履歴

6

察

c 2010 Information Processing Society of Japan情報処理学会研究報告
IPSJ SIG Technical Report

は起動後に図形を 1 つ描画し終了するという簡単なものであったが，本手法によって，ソー位として得られるため，出力が開発者にとって意味のある単位であり，シーケンス図等を用

スコードの変更によるプログラムの振舞いの変化を検出できた．実験時には，差分を抽出しいた可視化手法との組み合わせが容易であるという利点がある．

たシーケンス図を主に使って調査したが，シーケンス図の内容のうち，動作が変化した部分

Kuhn ら10) は，実行履歴を，各時刻でのメソッド呼び出しのスタックの深さによって表を探す必要がなく，どのように変化したのかを調べることに注力することができた．強調表

現される数値の列として抽象化し，類似度の計算や可視化を行う手法を提案している．この示されているとはいえ，巨大な 1 枚のシーケンス図から差分を探すにはそれなりの労力が必手法を用いると，大規模な実行履歴に含まれている類似した実行系列を開発者が目視で確認要であり，差分だけを別図として抽出する機能がなければ，調査は困難であったと思われる．

することができる．一方で，本研究の目的である，デバッグにおけるプログラムの変更など

本手法は，実行履歴をシーケンス図として可視化するため，ソースコードの変更によってによって生じる実行履歴のわずかな差異を検出する用途には不向きであると考えられる．

プログラムの振舞いにどのような影響が出たかを表示することができる．例えば，デバッグ

分析対象を GUI アプリケーションに絞った実行履歴の比較手法としては，Smit ら16) は，作業のときに実装クラスを変更した場合，変更箇所が他のオブジェクトにどのような影響をユーザの GUI 操作から起動された一連のメソッドを 1 機能だとみなし，その区間単位で実与えるのかを図で示すことができる．ソースコードの変更は 1 箇所だけであっても，他の場

行履歴を対応づける手法を提案している．Smit らの手法もまた最長共通部分列を取り出す所でプログラムの動作が変化するため，その影響を確認する必要がある．このような場合に手法であるが，本研究にもこのアイディアを取り込むことは可能であり，それによって，実本手法では，影響がある部分を変化部分として検出するため有効だと言える．

行シナリオ（ユーザの操作）の差異による影響を効果的に抽出できる可能性がある．

ソースコードが変更されていなくても，実行環境や入力データによるプログラムの振舞い

木構造の差分を求める手法は 2 つの木の編集距離やアライメント，包含関係を求める手法の変化を本手法は検出することができる．入力データとシナリオを用意して実行し，実行履などが数多く研究されている1) ．木構造の差分を求める近似アルゴリズムに FMES2) とい歴を取得すれば，入力データの違いによるプログラムの振舞いの違いは動作の変化として検う手法がある．このアルゴリズムは比較する 2 つの木の間で，ノードのマッチング計算を行出できる．バグを探す際には，入力の値を変更して実行し，動作を解析する必要があるため，う．ノードを葉と内部ノードに区別し，類似度が閾値以下のノード同士はマッチしないとい

複数の実行履歴を取得し，本手法を応用することでバグ検出に利用できると考えられる．

う仮定を置いて計算する．n を比較する 2 つの木の葉の合計とし，e を木の差の大きさとす
ると計算量は O(ne + e2 ) になり，e が小さいほどよい近似解が得られる．デバッグ時のソー

5. 関 連 研 究

スコードの変更は少なく，実行履歴の差分も小さいと考えられるため，この手法の条件に合致している．ただし，FMES では木構造の差分の近似解を求めるため，差分を正しく判断で本研究では，実行履歴の可視化手法と組み合わせることを前提とし，木構造の比較に基づ
8)

く実行履歴の比較手法を提案している．実行履歴の比較手法として，Hoﬀman らは実行きない可能性がある．また，本手法のようにトップダウンに比較する SimpleTreePattern-

履歴をイベント系列とみなし，2 つのイベント系列の最長共通部分列を求める手法を提案しMatchingArgorithm11) がある．この手法は二分木にしか適用できないが，文字列探索のている．最長共通部分列を求める手法は主に文章比較に使われ，2 つの文字列の中から最長

Knuth-Morris-Pratt 法を利用した手法である．

となる共通部分を探索することで差分を見つける手法である．本研究における木構造の比較

本研究は，実行履歴の差分を開発者に提示することを目的としているため，実行履歴から

では，メソッド呼び出し関係木の根から比較するため，あるメソッド X から Y を直接呼作られた木は一致しているか，あるいは不一致であるかのどちらかである．一方，プログラ

び出すプログラムがメソッド X から Z を呼び，Z が Y を呼び出すように修正されたと

ムの実行時の動作を監視して異常を検出する，欠陥の位置を特定するなどの研究では，入力

き，この修正は「X からの呼び出しが変わった」と認識される．これに対して，イベント

データや環境のわずかな差異を吸収して，同じ実行履歴として扱うための手法も様々に研究系列として比較した場合は，Y の実行そのものに対しては，対応関係を計算することが可されている．たとえば，Reiss 13) は，システムの性能を計測することを目的として，10 ミ

能である．ただし，イベント系列の比較では，逆に，実際には無関係な呼び出し階層に偶然

リ秒の時間単位で呼び出されたメソッドの数や確保されたオブジェクトの数を集計したベク

同じ系列が出現すると，それらを対応づける可能性もある．メソッド呼び出し関係木の比較

トルを作成しておき，ベクトルの変化によってプログラムの動作の変化を検出する手法を提から得られる差分は，必ずある 1 つのメソッドの実行が開始されてから終了するまでの単案している．また，Diep らは，欠陥の位置を自動特定する手法において意味がないと思わ7

c 2010 Information Processing Society of Japan情報処理学会研究報告
IPSJ SIG Technical Report6) M. Diep, S. Elbaum, and M. Dwyer. Trace normalization. In Proceedings of the2008 19th International Symposium on Software Reliability Engineering, pp. 67–76,
2008.
7) M.Hamill and K.Goseva-Popstojanova. Common trends in software fault and failure data. IEEE Transactions on Software Engineering, Vol.35, No.4, pp. 484–496,
2009.
8) K. J. Hoﬀman, P. Eugster, and S. Jagannathan. Semantics-aware trace analysis.
In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language
Design and Implementation, pp. 453–464, 2009.
9) JHotDraw. http://sourceforge.net/projects/jhotdraw/.
10) A.Kuhn and O.Greevy. Exploiting the analogy between traces and signal processing. In Proceedings of the 22nd IEEE International Conference on Software
Maintenance, pp. 320–329, 2006.
11) H.T. Lu and W.Yang. A simple tree pattern-matching algorithm. In Proceedingsof the Wrokshop on Algorithm and Theory of Computation, December 2000.
12) W.D. Pauw, D.Lorenz, J.Vlissides, and M.Wegman. Execution patterns in objectoriented visualization. In Proceedings of the 4th Conference on Object-Oriented
Technologies and Systems, pp. 219–234, April 1998.
13) S.P. Reiss. Dynamic detection and visualization of software phases. In Proceedingsof the 3rd International Workshop on Dynamic Analysis, pp. 1–6, 2005.
14) S.P. Reiss and M.Renieris. Encoding program executions. In Proceedings of the
23rd International Conference on Software Engineering, pp. 221–230, May 2001.
15) T.Richner and S.Ducasse. Using dynamic information for the iterative recoveryof collaborations and roles. In Proceedings of the 18th International Conference on
Software Maintenance, pp. 34–43, October 2002.
16) M.Smit, E.Stroulia, and K.Wong. Use case redocumentation from gui event traces.
In Proceedings of the 2008 12th European Conference on Software Maintenance andReengineering, pp. 263–268, 2008.
17) Uniﬁed ModelingLanguage(UML)1.5 speciﬁcation, March 2003. OMG.
18) T.Systä, K.Koskimies, and H.Müller. Shimba - an environment for reverse engineering java software systems. Software Practice and Experience, Vol.31, No.4, pp.
371–394, 2001.
19) N. Wilde and R. Huitt. Maintenance support object-oriented programs. IEEE
Transactions on Software Engineering, Vol.18, No.12, pp. 1038–1044, 1992.
20) 谷口考治, 石尾隆, 神谷年洋, 楠本真二, 井上克郎. プログラムの実行履歴からの簡潔なシーケンス図の生成手法. コンピュータソフトウェア, Vol.24, No.3, pp. 153–169,
2007.

れる動作の差異を取り除くために，実行した文のカバレッジが等しいような条件分岐による差異はまとめてしまうという手法 5) と，メソッド呼び出しの順序が異なっても結果として得られる状態が同じであれば動作は同じとみなして呼び出し順序を正規化する手法 6) を提案している．

6. ま と め
本研究では，プログラムの変更前後での実行履歴の差分検出手法を提案した．提案した手法はデバッグ時のソースコードのわずかな変更によって生じる実行時のメソッドの呼び出し
関係の変化を検出し，可視化して表示する．バージョンの異なるオープンソースソフトウェ
アを対象にしたケーススタディにより，バージョン間の変更点を発見することに成功した．
今後の課題として，木構造の比較にかかる時間の削減が挙げられる．実行履歴はプログラ
ムの実行から終了までの全てのメソッド呼び出しを取得をするため巨大になりがちであるが，本手法ではメソッド呼び出しの数が多くなるほど比較計算に時間が多くかかってしまう．そこで木構造の比較アルゴリズムを改良し，計算コストを減らすことを考えている．例
えば，前処理として部分木のハッシュ値を計算することで比較計算にかかる時間を削減できる．また，Amida のループ圧縮機能を利用し，木構造に含まれる繰り返し処理によるノードを事前に減らすことで比較計算にかかる時間を削減する手法を検討している．
謝辞 本研究は，文部科学省科学研究費補助金若手研究（B）（課題番号:21700030）の助
成を得た．

参

考

文

献

1) P.Bille. A survey on tree edit distance and related problems. Theoretical Computer
Science, Vol. 337, pp. 217–239, June 2005.
2) S. S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom. Change detection in hierarchically structured information. In Proceedings of the ACM SIGMODInternational Conference on Management of Data, pp. 493–504, 1996.
3) H.Cleve and A.Zeller. Locating causes of program failures. In Proceedings of the27th International Conference on Software Engineering, pp. 342–351, 2005.
4) J.K. Czyz and B.Jayaraman. Declarative and visual debugging in eclipse. Eclipse
Technology Exchange, 2007.
5) M.Diep, S.Elbaum, and M.Dwyer. Reducing irrelevant trace variations. In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software
Engineering, pp. 477–480, 2007.

8c 2010 Information Processing Society of Japan