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

蓄積されたオブジェクトの動作履歴を用いた
実行履歴削減手法の提案と評価
脇阪 大輝1,a)

石尾 隆1,b)

井上 克郎1,c)

概要：ソフトウェアは開発期間中にテストを実施されるが，テストによって発見されなかった欠陥はソフ
トウェア利用者のもとで障害を引き起こす．障害を開発環境で再現する場合，プログラムの動作を詳細に記録した実行履歴が有用であるが，詳細な実行履歴のデータ量は膨大なものとなってしまう．そこで本研
究では，プログラムが開発期間中には観測されていない動作をしそうなときにのみ実行履歴を記録することによって，実行履歴の量を削減する手法を提案する．提案手法では，プログラムを事前に何度か実行し，
オブジェクトの動作を Dynamic Object Process Graph（DOPG）として抽出しておく．利用者の環境での実行では，DOPG として記録された動作と一致しないオブジェクトが入力となっているメソッドの実
行のみに対して，実行履歴の記録を行う．評価実験では，DaCapo ベンチマークに含まれる 4 つのアプリ
ケーションについて，実行履歴の量を 22.8%から 67.23%に減らせることを確認した．
キーワード：動的解析，実行履歴，障害再現

1. はじめにけばよい [9]．しかし，プログラムの動作を詳細に再現することが可能な実行履歴は，そのデータ量が非常に大きく

ソフトウェアに含まれる欠陥を発見，除去するために，なる．したがって，利用者の環境で動作するプログラムか

開発期間中には静的解析や動的解析の技術を利用したテら，詳細な情報を含む実行履歴を記録することは現実的にストが実施される．しかし，すべての欠陥が，事前のテスは好ましくない．プログラムのすべての実行履歴を記録す

トによって発見されるとは限らない．完全なテストは難し

るのではなく，必要のない記録をせずに実行履歴の量を減く，欠陥が残存したままのソフトウェアがリリースされる

らすことが求められる．

ことが多々ある [3], [8]．欠陥を含んだソフトウェアは，と本研究では，メソッドの入力となるオブジェクトの動作

きに本番環境での稼働時に，その欠陥によって障害を引きが同一であれば，そのメソッドの動作も同一であると仮定

起こす．

し，入力となるオブジェクトが既知の動作をしているメ

障害を引き起こした欠陥を修正するために，開発者は，

ソッドの実行の履歴を記録しないことで，実行履歴の量をまず生じた障害を開発環境で再現することを試みる．障害

削減する手法を提案する．提案手法では，対象のプログラを再現するための手掛かりとして，ソフトウェア利用者のムをあらかじめ実行し，その実行において出現したオブ

証言や，障害発生時に出力されるエラーログなどが用いら

ジェクトの動作と，実行されたメソッドとその入力となっれる [15]．そのような情報だけでは欠陥の特定が困難であたオブジェクトの組を蓄積する．その後，本番環境でプロる場合には，プログラムの動作についてのより詳細な情報

グラムを実行するとき，その実行で出現したオブジェクトを含む実行履歴が必要とされる．実行履歴を用いて，障害の動作と，あらかじめ蓄えておいたオブジェクトの動作を発生時のプログラムの内部状態や実行経路を再現すること比較する．比較した結果，オブジェクトの動作が蓄えたオで，障害の原因となる欠陥箇所の特定を容易にする．

ブジェクトの動作と異なっているとき，そのオブジェクトリリース後に発生する障害を開発環境で迅速に再現するは未知の動作をしているとみなす．提案手法では，この未ために，本番環境でのプログラムの実行履歴を記録してお知の動作をしているオブジェクトを入力に含むメソッドを
実行履歴の記録対象とする．

1
a)
b)
c)

大阪大学大学院情報科学研究科
h-wakisk@ist.osaka-u.ac.jp
ishio@ist.osaka-u.ac.jp
inoue@ist.osaka-u.ac.jp

c 1959 Information Processing Society of Japan⃝

提案手法を評価するために行った評価実験では，実行履
歴中に含まれるイベントのうち，提案手法によってどの

1

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

程度の数を記録するだけで済むかを計測した．また，プロ

入力など，実行を再現するために最低限必要な動作情報のグラムの事前の実行では観察されなかった動作をするメ

みを，実行履歴として記録する手法がある [1], [3], [16]．こソッドの実行を，提案手法によって実行履歴の記録対象にれらの手法は，プログラムの動作情報を実行履歴から読みできているかを調査した．実験の結果から，4 つの Java込み，それを用いてプログラムを再実行することで，プロ

アプリケーションに対して，実行履歴の量を約 22.8%からグラム利用者の環境での実行を再現する．たとえば，プロ67.23%に減らすことができた．また，そのうちの 2 つでグラムへの外部入力のみを実行履歴として記録しておき，は，事前の実行には観察されなかった動作をするメソッド

次にプログラムを実行する際に，プログラムへの外部入力の実行の約 9 割を実行履歴の記録対象とすることができた．

を実行履歴で置き換える．これにより，プログラムの動作

本論文の構成は次の通りである．まず，2 章で研究の背すべてを詳細に記録した場合と比較して，少ない実行履歴

景について述べる．3 章で提案手法である実行履歴削減手でプログラムの実行を再現できる．しかし，このような手法を説明し，4 章では実施した評価実験について説明する．

法は，プログラムを最初から実行するという手法の性質上，最後に 5 章ではまとめと今後の課題について述べる．

実行時間が非常に長いサーバーアプリケーション等の実行

2. 背景
2.1 実行履歴を用いたデバッグを再現するには不向きである．本研究では，メソッド実行の単位で実行履歴を記録することで，プログラム実行の部
分的な再現に対応している．

プログラムの実行履歴は，プログラムがどのような動作

また，プログラムに障害が発生してから，その原因となをしたかを記録したもので，プログラムの実行中に発生しる欠陥を含んでいそうなプログラムの箇所を推定し，そのたイベントが時系列順に並んでいる．実行履歴の形式は，部分だけから実行履歴を取得する手法がある [2]．この手プログラムの欠陥修正に用いる方法に対して，適当なもの

法では，実行履歴を記録する範囲を小さく抑えることがでが選ばれる．たとえば，単純にプログラムの異常終了した

きる一方で，初めてプログラムに障害が発生してからも，

位置をプログラムの修正に用いる場合であれば，プログラ

欠陥の場所を推定するために，欠陥を含むプログラムを稼

ム終了時に実行中であったメソッドを示すスタックトレー

働させ続ける必要がある．提案手法では，プログラムに初スを実行履歴として用いる．

めて障害が生じたときには，既にそのときの実行履歴が記

Omniscient Debugging[10] は，あるプログラムの実行か録できていることを目指している．また，欠陥を含んでいら取得した実行履歴を用いて，後からそのプログラムの実

そうな箇所をソースコードの位置として推定しても，その行の，任意の時点の状態を再現する手法である．このよう箇所が何度も実行される場合，すべてが障害に関係するとなデバッグ手法を実現するためには，プログラムの動作は限らない．提案手法では，同じメソッドでも，障害に関の詳細，たとえば，メソッドの呼出しやオブジェクトの生係しそうにない実行については，実行履歴を記録しないこ成，フィールドの読み書き等を含んだ実行履歴が必要でとが可能である．

ある．並列プログラムのデバッグにおいては，Omniscient

実行履歴に対してファイル圧縮技術 [6] や，実行履歴の圧

Debugging のような再現技術が有効でないこともあると指縮技術 [7] を適用することで，ファイルサイズを小さくす

摘されているが [11]，そうではないプログラムのデバッグ

ることも行われている．本研究で得られる実行履歴にも，においては有効であるとされている [12]．本研究においてこれらの技術を適用することは可能である．

も，Omniscient Debugging が有効であるようなプログラ
ムのデバッグを支援することを想定している．
利用者のもとでプログラムに障害が生じたとき，その原因となる欠陥を発見するためにも，実行履歴が利用される．

2.3 実行履歴の比較の取組み
本研究のアプローチは，実行履歴の比較を行っている以下の事例に基づいている．

プログラムの利用者が，プログラムを実行すると同時に，宗像らの研究 [13] では，プログラム中に出現するオブ実行履歴を取得しておき，障害が生じたときにその実行履

ジェクトに関しての履歴をオブジェクト間で比較すること

歴を開発者が確認し，欠陥の特定に役立てる．しかし，実によって，同じクラスに属するオブジェクトであっても，行履歴の記録は，プログラムの実行時性能に悪影響を及ぼ

その動作は少数のグループに分類できることを明らかにしす．それはたとえば，プログラムの実行速度の著しい低下

た．本研究では，オブジェクトの動作が同一であれば，そであったり，使用ディスク領域の増大である．このようなれらのオブジェクトが関わるプログラムの実行もまた同種性能への悪影響を避けるために，実行履歴の量を少量にとの動作になると仮定した．

どめる方法が必要である．

Dallmeier らの研究 [5] では，プログラムの passing runと failing run の実行履歴から抽出したオブジェクトの動

2.2 実行履歴削減の取組み
実行履歴の量を小さくするために，プログラムへの外部

c 1959 Information Processing Society of Japan⃝

作モデルを比較することによって，プログラムに含まれる欠陥に対する修正案を自動生成している．本研究でも，プ

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

ログラムに障害が生じるときには，その実行に関わるオブジェクトが過去には観測されていない動作をしている可能性があることに着目し，オブジェクトの動作が異なっている部分のプログラム実行を実行履歴として記録する．

3. 提案手法
本研究では，Java プログラムを対象とし，記録する実行履歴の量を減らすために，未知の動作に着目して，実行

1 : public static void main(String[] argv){
2 :String exp = argv[0];3 :Stack stack = new Stack();
4 :for(int i=0;i<exp.length();i++){5 :char c = exp.charAt(i);6 :
if(isOperand(c)){
7 :stack.push(Character.digit(c, 10));8 :}else{9 :calc(stack, c);
10:
}
11:
}
12: }

履歴を取得する手法を提案する．提案手法では，事前の実行としてプログラムの簡易な実行を行い，出現したオブ
ジェクトの動作を抽出し，実行されたメソッドとその入力となったオブジェクト集合との組を記録する．後の実行では，出現したオブジェクトの動作と，事前の実行でのオブジェクトの動作を比較し，メソッド実行開始時に実行履歴
取得の対象かどうかを判定することで，事前の実行に含ま20:static void calc(Stack stack, char operator){
21:
switch(operator){
22:
case ‘+’:23:
stack.push(stack.pop() + stack.pop());
24:
break;
25:
case ‘*’:
26:
...
27:
}
28:}

れない動作の詳細な実行履歴を記録する．

図 1

例として用いるプログラム

3.1 提案手法で用いる実行履歴
提案手法で用いる実行履歴は，少なくとも以下のイベン
トを含んでいる必要がある．

Call ⟨t, thread, o, m, l⟩． メソッド呼出しを表す．
Entry ⟨t, thread, o, m, P ⟩． メソッド実行の開始を表す．
Exit ⟨t, thread, m⟩． メソッド実行の終了を表す．
Return ⟨t, thread, m⟩． メソッド呼出しからの復帰を
表す．

表 1

実行履歴の例

イベント

t

o

m

Entry

1

None

main

l

Call

2

2

Stack

3

Return

3

2

Stack

3

Call

4

1

length4

Return5

1length

4

Call

6

1

charAt5

Return7

1

charAt5

すべてのイベントに含まれる t, thread は，それぞれ，イ

Call

8

None

isOperand

6

ベントが発生した順序を表すタイムスタンプと，イベント

Return9

None

isOperand

6が発生したスレッドの ID である．o はメソッド呼出しや

Call

10

2

push

7

その実行におけるレシーバオブジェクトの ID である．m

Return
..
.

11

2

push

7

は呼び出されたまたは実行されたメソッドを示す．l は実P{0}

行されたメソッド呼出し命令のプログラム中での位置を一意に示す ID である．P = {p1 , . . . , pn } はメソッド実行にベント，Exit イベント，Return イベントを用いる．メソッ

与えられた引数の値の列である．例として，図 1 に示すプ

ド実行とその入力となったオブジェクト集合の取得には，

ログラムは．コマンドラインから与えられた逆ポーランド

Entry イベントの引数情報を用いる．

記法の数式を計算するものである．引数に数式 “1 2 +” を

3.2.1 オブジェクトの動作の抽出与えたとすると，被演算子である 1，2 が順にスタックへ

実行履歴を用いて，オブジェクトごとの動作を抽出する．

格納され，その後，calc メソッドの中で足し算が行われ，オブジェクトの動作は，Dynamic Object Process Graph

その結果がスタックへ格納される．このときに得られる実（DOPG）[14] として抽出する．DOPG は，オブジェクトに

行履歴の一部が表 1 のようになる．タイムスタンプ t の値

対するメソッド呼出しの順序を示す，動的に生成される有によって，各イベントの発生順序が示される．なお，表中向グラフである．1 つのオブジェクトごとに 1 つの DOPG

では，static メソッドの実行におけるレシーバオブジェクが作成される．本手法で用いる DOPG は，以下の種類の

ト o を None と表記し，命令位置 l を図 1 の行番号を用い頂点をもつ．

て表記している．

call 頂点． メソッド呼出し位置に対応する頂点．
entry 頂点． メソッドの開始を示す頂点．

3.2 事前の実行

exit 頂点． メソッドの終了を示す頂点．

事前にプログラムを実行して実行履歴を取得し，オブstart 頂点． オブジェクトの生存期間の最初を示す頂点．

ジェクトの動作とメソッドの実行のパラメータについてのend 頂点． オブジェクトの生存期間の最後を示す頂点．

情報を収集する．オブジェクトの動作の抽出では，Call イ

call 頂点は，DOPG に対応するオブジェクトのメソッドを

c 1959 Information Processing Society of Japan⃝3

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

直接呼び出す，あるいはそのようなメソッドを間接的に呼

start
seq

び出す Call イベントのメソッド呼出し位置 l の値ごとに存

call
Stack()#3

在する．同じメソッドを呼び出していても，l の値が異なseqれば，それぞれ独立した頂点となる．entry 頂点は，Callcallpush()#7

イベントに対応して実行されたメソッドの開始を表す頂点

seq
seq

である．exit 頂点は，そのメソッドの終了を表す．start 頂

callpop()#23.1

点と end 頂点は，DOPG 全体での開始，終了をそれぞれ

seq

が示す．

call
pop()#23.2

DOPG は以下のような種類の辺をもつ．

seq

seq 辺． メソッド呼出しの順序を示す辺．

call
push()#23

call 辺． メソッド呼出しを示す辺．

seq

return 辺． メソッド呼出し元への復帰を示す辺．
seq 辺は call 頂点と任意の種類の頂点をつなぐ辺で，そ

end

図 2

れぞれの頂点に対応するメソッド呼出しの順序を示す．

図 1 のプログラムを引数 “1 2 +′′ で実行したときの Stack オ
ブジェクトについての DOPG

call 辺は，call 頂点と entry 頂点をつなぐ辺である．また，return 辺は，exit 頂点と call 頂点をつなぐ辺である．例え

表 2ば，methodA の Call イベントに対応する call 頂点から出

イベント

o

m

る call 辺は，methodA 内での動作を表すグラフの entry 頂

Entry

1

methodA{2, 3}

点につながる．return 辺は，methodA 内での動作を表す

Entry

1

methodA{null, 3}

Entry

None

methodB{1}

グラフの exit 頂点から，methodA の Call イベントに対応

Entry イベントの系列の例
Pする call 頂点への辺である．
オブジェクトが単一のスレッドからのみ使用されている

表 3

記録するメソッドとその入力となるオブジェクト集合の組

場合，DOPG は定義 [14] に従って作成する．図 2 は，図 1のプログラムを引数 “1 2 +′′ で実行したときの，Stack オ

mnmethodA0{1}

1{2, null}

2{3}

ブジェクトについての DOPG を示したものである．
マルチスレッドでオブジェクトが使用される場合は，オ

methodB

ブジェクトに対するイベントをタイムスタンプ t の値の順

Om,n

0

{}

1

{1}

に並べ，単一スレッドの実行履歴とみなして DOPG を作成する．具体的には，あるオブジェクトについて，スレッド

した実行履歴から Om,n を取得した結果は，表 3 のようにごとのコールスタックがあるとしたとき，任意の時点におなる．表中の methodB はクラスメソッドで，レシーバオ

いて，高々１つのスレッドのコールスタックにしか要素がブジェクトがないものの例である．この場合，OmethodB,0

存在しないとき，それらの呼出しがシングルスレッドで時は空となる．

系列順に発生したとみなす．提案手法では，複数のスレッドから同時にメソッドが実行されているオブジェクトにつ3.3 後の実行

いては，その動作を DOPG として抽出することができな

プログラムの後の実行では，実行と同時に，出現していい．本手法では，そのようなオブジェクトを動作の抽出のるオブジェクトの動作と事前の実行でのオブジェクトの対象外とした．

動作を比較する．また，メソッドの実行が開始されるとき

3.2.2 実行されたメソッドとその入力となったオブジェに，そのメソッドの動作を実行履歴取得対象とするかどう

クト集合の取得
オブジェクトの動作に加え，実行されたメソッドの引数かの判定を行う．本章では，オブジェクトの動作の比較の方法についてと，実行履歴取得対象の判定方法について説を記録する．これには Entry イベントを用い，レシーバオ

明する．

ブジェクトの ID である o および引数のオブジェクトの ID

3.3.1 オブジェクトの動作の比較である P を取得する．入力が null である場合には，null

オブジェクトの動作の比較は，事前の実行で得られたをオブジェクト ID の代わりとする．数値などのオブジェ

DOPG と，後の実行におけるオブジェクトの Call イベン

クト以外の入力は無視する．結果として，メソッド m のトと Return イベントを用いて行う．事前の実行で得られ第 n 引数に与えられたオブジェクト ID の集合 Om,n を得

た DOPG をプッシュダウンオートマトンとみなし，初期

る．ただし，n = 0 はレシーバオブジェクトを表すものと状態を start 頂点とし，後の実行におけるオブジェクトのする．例えば，表 2 のような Entry イベントのみを取り出

Call イベントと Return イベントによって，オートマトン

c 1959 Information Processing Society of Japan⃝4

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

を状態遷移させる．オートマトンに遷移が定義されていな

表 4

例として用いるオブジェクトに対するイベント列
イベント

いような入力が与えられたときにはオートマトンの状態を

mlsink とし，これはオブジェクトとオートマトンの表す動作

Call

Stack

3

が一致していないことを表す．

ReturnStack

3

実行中のプログラムに出現したオブジェクト o に対して，

Call

push

7

Returnpush

7

動作の一致している DOPG 集合 Do を対応付ける．オブ

Call

push

7

ジェクト o が出現した時点において，この Do を，事前のReturnpush

7

実行で得られた DOPG のうち，オブジェクト o と同じク

Call

pop

23.1

ラスに属する DOPG の集合として初期化する．オブジェ

Returnpop

23.1

クト o に対する Call イベントまたは Return イベントが発

Call

pop

23.2

生したとき，すべての d ∈ Do に対して，状態遷移処理を行Return

pop

23.2

Call

push

23

Return

push

23

Call
..
.

push

7

う．そして，状態が sink となった DOPG d をすべて Do
から除外する．
あるオブジェクト o と DOPG d の，動作の比較のための
状態遷移処理は，DOPG の頂点の１つを現在の状態とし，その現在の状態を発生したイベントに応じて遷移させることで行う．まず，d の start 頂点を初期状態とする．オブ状態の頂点から Call イベントに対応する call 頂点への seq
辺が存在すれば，その call 頂点を現在の状態とする．そのる．また，その call 頂点から entry 頂点への call 辺が存在する場合には，その entry 頂点を現在の状態とする．最後に，Call イベントに対応する call 頂点をスタックにプッシュする．オブジェクト o に対して，Return イベントが発生した場合には，スタックから call 頂点を１つ取り出し，それを現在の状態とする．このときに，もし d に Return

現在の状態

start
seq

seq

call
Stack()#3

call
Stack()#3

call
Stack()#3

seq

seq

seq

call
push()#7

callpush()#7

callpush()#7

seq

ジェクト o に対して Call イベントが発生した場合，現在のような seq 辺が存在しない場合，現在の状態を sink とす

start

start

現在の状態

seq

seq

seq

seq

seq

seq

call
pop()#23.1

callpop()#23.1

callpop()#23.1

seq

seq

seq

call
pop()#23.2

callpop()#23.2

callpop()#23.2

seq

seq

seq

call
push()#23

callpush()#23

callpush()#23

seq

seq

seq

に対応する exit 頂点が存在しない場合には，現在の状態を

end

end

end

sink とする．

(a)

(b)

(c)

比較方法の例として，図 1 のプログラムに入力として現在の状態

図 3 DOPG の操作例

”1 2 + 3 + ” を与えたときの実行で出現する Stack オブ
ジェクト o を，図 2 に示す DOPG d と比較する．o は，表 4

る call 頂点への seq 辺が，図 3（c）の状態の call 頂点からに示されるイベントを順に発生させられる．まず，DOPGは存在していないため，状態は sink となる．この瞬間か

d の start 頂点を現在の状態とみなし，スタックは空の状

らオブジェクト o は，DOPG d の表す動作と一致していな態にする（図 3（a））．最初のイベントは，l = 3 でのコンい動作をしていると判定される．d は，Do から取り除かストラクタの Call イベントであるため，現在の状態である

れ，Do = ∅ となる．

start 頂点から，seq 辺でつながれた，その Call イベントに

3.3.2 実行履歴取得対象の判定

対応する call 頂点へ現在の状態を更新し（図 3（b）），ス

メソッドの実行が開始されたとき，そのメソッド内でのタックにこの call 頂点にプッシュする．この call 頂点は，イベントを実行履歴取得対象とするかどうかを判定する．

call 辺を持っていないため，entry 頂点への状態遷移は生じ

判定は，メソッドの入力に含まれるオブジェクトのうち，ない．次のイベントは Return イベントなので，スタック

事前の実行でそのメソッドの入力となったどのオブジェク

から call 頂点を取り出し，それを現在の状態とする．このトとも動作が一致しないものが含まれるかどうかで行う．

例では，現在の状態は変化しない．次の Call イベントでも以下に判定方法を詳細に説明する．

同様に，現在の状態が l = 7 の call 頂点へ遷移する．以降

メソッド m の実行が開始されたとき，メソッド m ののイベントに関しても同様に状態を遷移していくことで，第 n 引数に与えられたオブジェクト pn と動作が一致し

l = 23 である push メソッドの Return イベントが生じたている DOPG 集合を Dpn とする．また，事前の実行でところで，図 3（c）のようになる．そしてその次の l = 7

記録しておいた，メソッド m の第 n 引数に与えられたである push メソッドの Call イベントでは，それに対応す

オブジェクト集合 Om,n に含まれるオブジェクトの動作

c 1959 Information Processing Society of Japan⃝5

情報処理学会研究報告
IPSJ SIG Technical Reportを表す DOPG 集合を Dmn とする．このとき，メソッド

評価実験は，DaCapo ベンチマーク [4] に含まれる 4 つ

m が実行履歴取得対象であるかどうかを表す R(m) は，の Java アプリケーションを対象に行った．DaCapo ペン

R(m) = ∃n{Dpn ∩ Dmn = ∅} と表される．n は 0 ≤ n ≤チマークは，様々なアプリケーションを実行できるベン

メソッド m の引数の数，であり，n = 0 はレシーバオブ

チマークソフトである．実行時の引数により，実行するア

ジェクトを表す．つまり，メソッドの入力となる各オブ

プリケーションを選択できる．また，アプリケーションのジェクトに，事前の実行でそのメソッドに入力として与え実行の規模も，small，default，large から選択することがられたオブジェクトのどの動作とも一致しない動作をしてできる．実行の規模とは，たとえば画像処理を行うアプリ

いるものが存在する場合に，そのメソッドが実行履歴取得

ケーションである batik では，処理を行う画像の枚数で表対象となる．また，メソッドの引数が null である場合にされる．実験の対象としたアプリケーションは，DaCapo

は，事前の実行でその引数に null が入力されているかを

ベンチマークに含まれるアプリケーションのうち，batik，Om,n より調べ，null が一度も入力されていないとき，実fop，luindex，pmd の 4 つである．

行履歴の取得対象とする．事前の実行で実行されていない
メソッドについては，その入力のオブジェクトの動作に関わらず，無条件に実行履歴取得対象とする．

4.1 実験方法
提案手法では，プログラムの実行履歴を取得する必要が3.3.1 項の例を用いて，実行履歴取得対象の判定の例を示ある．本研究では，表 5 のイベント情報を含む実行履歴をす．まず，図 1 のプログラムに数式 ”1 2 +” を与え，それを使用し，評価実験を行った．この実行履歴は，それを用い事前の実行とする．この実行では，1 つの Stack オブジェクてプログラムの実行を再現することができるようなイベン

トが出現し，その Stack オブジェクトの動作を表す DOPG

ト情報を含んでいる．

が，図 2 である．calc メソッドの入力となったオブジェク

評価実験は，DaCapo ベンチマークの，small 規模での実トの DOPG 集合にそれが含まれることになる．つまり，行をプログラムの事前の実行として用い，small よりも規その Stack オブジェクトの ID を 2 とすると，Dcalc1 = {2}模の大きい default の実行を本番環境での実行として用いとなる．そして，同じプログラムに数式 ”1 2 + 3 + ” をる．これは，事前の簡易な実行より，本番環境での実行の与えたときの実行を後の実行とする．この実行でも 1 つの方がその規模は大きいという想定に基づいている．small

Stack オブジェクトが出現するので，それと動作が一致す

規模での実行で，DOPG とメソッドの入力となったオブ

る DOPG 集合を持たせ，Call イベントと Return イベン

ジェクト集合の抽出を行う．default 規模の実行では，各オトが発生したときに比較を行う．3.3.1 項で示したように，

ブジェクトに対して，DOPG との動作の比較を行い，各メ

l = 23 の push メソッドの Return イベントが発生するまソッド実行が実行履歴取得対象となるかの判定を行う．

で，この Stack オブジェクトは図 2 の DOPG と動作が一

また，small 実行の実行経路をメソッドごとにまとめ，致しているとみなされるが，その次に l = 7 での push メ

default 規模の実行の各メソッド実行の実行経路と比較す

ソッド呼出しの Call イベントが発生したとき，動作が不一る．各メソッド実行の実行パスを記録する．実行経路は，

致であるとみなされる．この瞬間，この Stack オブジェク

メソッド実行中に通過したバイトコード上のラベル集合とトと動作の一致している DOPG の集合は空となる．このして求める．つまり分岐命令の結果が異なる場合には，異後に calc メソッドの実行が開始されるとき，calc メソッド

なる実行経路として扱う．一方で，ループ文の繰り返し回の第 1 引数となる Stack オブジェクトと動作の一致してい数の違いは，実行経路の違いに含めない．評価実験では，る DOPG の集合 Dp1 は空となるため，R(calc) は真とな

small 規模の実行には存在しない実行経路をたどる，default

り，この calc メソッドの実行は実行履歴取得の対象である規模の実行のメソッド実行を未知の振舞いをするメソッドと判定される．一方，Stack オブジェクトが DOPG と動作実行とする．

が一致しているとみなされている間の calc メソッドの実行
は，実行履歴取得対象にならない．

4. 評価実験
本研究では，提案手法の以下の特性を評価するために実験を行った．
実行履歴の削減能力 実行履歴の量をどの程度削減することが可能であるか．
未知の振舞いの記録能力 事前の実行では観測されていな

4.2 制限評価実験では，以下のオブジェクトを，DOPG 抽出の対象から除外した．

• 実行履歴にメソッド呼出しイベントが 1 つも含まれないオブジェクト• 複数のスレッドから同時にメソッドを呼出されているオブジェクト• String クラスのインスタンスであるオブジェクト

いプログラムの動作に限定して実行履歴を記録できString 型は，メソッド呼出しによって内部の状態が変化せるか．

ず，メソッドの呼出し順序を比較する意味が少ないうえc 1959 Information Processing Society of Japan⃝6

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

評価実験で利用した実行履歴に含まれるイベント

提案手法によって，23.7%から 62.4%の割合のメソッド実

イベント種類意味

行が実行履歴の取得対象となったことがわかる．U B の値

Call

メソッド呼出しは各アプリケーションの未知の振舞いをするメソッド実行

Entry/Exit

メソッド実行の開始および終了

Parameter

Call/Entry イベントの引数

Returnメソッド呼出しからの復帰

Field Read/Write

フィールドの読込みおよび書込みた場合には，R の値と U B の値が等しくなる．しかし，実Array Read/Write

配列への読込みおよび書込み

験結果では，R の値が U B の値よりも大きくなっている．

Label

ラベルへのジャンプ命令

これは，small 規模での実行と同じ動作をしているメソッ

New

配列・オブジェクトの生成

ド実行を，実行履歴の取得対象としてしまっていることを

Object Initialized

オブジェクトの初期化表す．それを示すように，U BR の値は小さくなっている．

Throw

例外のスロー
例外のキャッチ

small 規模では実行されないメソッドを取り除いた U BR

CatchInstanceOf

instanceof 演算の実行

Monitor Enter/Exit

排他制御の開始および終了の割合を示しているので，本手法によって，未知の振舞いをするメソッド実行のみを実行履歴の取得対象として選べの値はすべてのアプリケーションで約 0%となった．このような余分に実行履歴を取得してしまうようなメソッド実行に対しては，あきらかに実行経路が事前実行と異ならな
いようなメソッドを，あらかじめ実行履歴の取得対象からに，プログラム実行中に生成と消滅を繰り返し，大量のオ外しておくことで，対応できるものもあると考えられる．

ブジェクトが出現する．よって提案手法を Java プログラ

例えば，ただフィールドの値を取得および更新を行うだけ

ムに適用するにあたり，String 型のオブジェクトは手法のの，getter，setter が挙げられる．

対象外とした．

RU B の値は，未知の振舞いをするメソッド実行のうち，提案手法によって実行履歴を取得できたメソッド実行の割

4.3 評価尺度評価実験で用いる評価尺度を以下のように定義する．

合を示している．small 規模では実行されないメソッドは，
必ず実行履歴の取得対象とすることができるので，この値

R 実行履歴の取得対象となるメソッド実行の割合

はすべてのアプリケーションで大きくなっている．その未知の振舞いをするメソッド実行の割合

ようなメソッドの影響をなくして計算した RU B ′ の値は，

UB

U BR 実行履歴の取得対象となるメソッド実行のうち，未知の振舞いをするメソッド実行の割合
未知の振舞いをするメソッド実行のうち，実行履

RU B

luindex と pmd では大きくなっている．これは，未知の振舞いをするメソッド実行の多くを，提案手法により実行履
歴の記録対象とできていることを示している．一方，batik

歴の取得対象となるメソッド実行の割合と fop ではこの値が小さくなっている．これは batik と fop′

で，未知の振舞いをするメソッド実行を実行履歴取得対象

RU B

small 規模の実行では実行されなかったメソッドを除外したときの RU B 値にできず，多くを取りこぼしていることを示している．提提案手法では，small 規模では実行されなく default 規模案手法では，入力にオブジェクトを含まないようなメソッの実行では実行されるようなメソッドが，必ず実行履歴のドの実行を，実行履歴取得対象に含めることができない．

取得対象となる．また，このようなメソッド実行は，必ず

例えば，fop においては，このような取りこぼしたメソッ

未知の振舞いをしているメソッド実行とみなされる．このド実行の多くが，org.apache.fop.util.CharUtilities

ようなメソッド実行の数によっては，RU B の値が大きくクラスのメソッドで，isAdjustableSpace メソッド，classOf

影響を受けるため，そのようなメソッドの影響を受けない

メソッド，isAnySpace メソッド，isNonBreakableSpace メ′

ように RU B の値を用いる．

ソッドの実行であった．これらのメソッドはすべてクラス
メソッドで，引数にもオブジェクトを取らない．このよう

4.4 実験結果および考察に提案手法は，int 型や char 型等のプリミティブな引数の評価実験の結果について説明する．表 6 では，small 規

値によってメソッドの振舞いに直接影響を受けるメソッド

模の実行のイベント数と，抽出した DOPG の数，そしてには対応できない．このようなプリミティブな型の値の違実験で無視したオブジェクトの数を示している．１度もいによって生じる実行経路は，単体テストで事前に網羅しメソッドを呼出されず，DOPG 作成が不可能であるオブやすいものと考えられる．したがって本研究では，このよ

ジェクトの数は，この表に含まれていない．なお，複数の

うなメソッドの実行履歴を記録する必要性は少ないとしてスレッドからメソッドを同時に呼び出されているオブジェいる．

クトは，pmd において 1 つ存在し，他のアプリケーション
では存在しなかった．
評価実験の結果を表 7 に示す．実験結果の R の値から，

c 1959 Information Processing Society of Japan
⃝

表 8 は，実験で用いた実行履歴に含まれるイベントのうち，実行履歴取得対象となったイベントの数を示している．
これは，あるメソッドが実行履歴取得対象であるとされた

7

情報処理学会研究報告
IPSJ SIG Technical Report
表 6ンまたはメソッドに対して，提案手法が効果的であるのか

small 規模の実行のイベント数および DOPG 数
イベント数

DOPG 数

対象外オブジェクト数

を詳細に調査することが考えられる．また，その結果から，

batik

168,534,669

171,138

4,812

余分な記録や記録漏れへの対応を考える必要があるとも考

fop

74,328,761

208,113

23,141

えている．さらに，プログラムの実行と同時に本手法を適luindex

73,106,032

15,295414

pmd

17,303,153

27,3825,703

用したときに生じるオーバーヘッドを計測し，手法の実用性について考察する必要がある．
謝辞 本研究は，科研費 課題番号:25220003 および科研

表 7 評価実験の結果 （単位：%）′費 課題番号:23680001 の助成を得た．

R

UB

U BR

RU B

RU B

batik

26.3

22.2

84.4

99.9

18.5

fop

23.7

2.2

8.2

87.3

5.1

参考文献

luindex

58.6

8.2

13.9

99.9

97.1

[1]

pmd

62.4

2.5

4.0

98.1

92.2

表 8

[2]

実行履歴削減量

総イベント数記録イベント数

記録割合

batik

712,010,905

227,794,693

31.99%

fop

417,587,236

95,211,219

22.80%

luindex2,160,725,683

1,025,008,169

47.43%

pmd

1,425,282,440

958,311,316

67.23%

[3]

[4]
[5]

ときに，そのメソッドの Entry イベントから Exit までのイベントを記録するとして計算した．取得対象でないとされたときは Entry イベントから Exit イベントまでのイベ

[6]
[7]

ントを，Entry と Exit イベントを含めて，記録対象から除外した．実行履歴中の各イベントが，すべて同じサイズで[8]あると仮定すれば，表中の記録割合が提案手法適用後の実行履歴のサイズを示している．luindex や pmd では，他と比較して記録割合の値が大きくなっている．これらのアプ[9]

リケーションは，default 規模の実行に比べ，small 規模の実行のイベント数が非常に少ない．したがって少ないイベ[10]ントを記録することで，多くのイベントを記録を減らした[11]という点で，提案手法が有効であったと考えることができる．事前の実行がより豊富であれば，より多くの記録を削[12]減することができる可能性もある．

5. まとめと今後の課題[13]

プログラム利用者のもとで発生する障害を開発環境で再現するためには，実行履歴が有用であるが，詳細な動作の情報を含む実行履歴はデータ量が非常に大きい．そこで，[14]

事前にプログラムを実行しておき，そのときの動作とは一致しない動作をしそうなメソッド実行についてのみ実行履[15]

歴を記録することで，実行履歴の量を削減する手法を提案[16]

した．評価実験では，実行履歴の量が 22.8%から 67.23%の量に減らすことができることを確認した．また，2 つのア

J. Bell, N. Sarda, and G. Kaiser. Chronicler:
Lightweight recording to reproduce ﬁeld failures. In
Proc. of ICSE, pp. 362–371, 2013.
T M. Chilimbi, B. Liblit, K. Mehra, A. V Nori, andK. Vaswani. Holmes: Eﬀective statistical debugging via
eﬃcient path proﬁling. In Proc. of ICSE, pp. 34–44,
2009.
J. Clause and A. Orso. A technique for enabling andsupporting debugging of ﬁeld failures. In Proc. of ICSE,
pp. 261–270, 2007.
DaCapo. http://www.dacapobench.org/.
V. Dallmeier, A. Zeller, and B. Meyer. Generating ﬁxes
from object behavior anomalies. In Proc. of ASE, pp.
550–554, 2009.
gzip. http://www.gzip.org/.
A. Hamou-Lhadj and T. C. Lethbridge. Compression
techniques to simplify the analysis of large execution
traces. In Proc. of IWPC, pp. 159–168, 2002.
H. Jaygarl, S. Kim, T. Xie, and C. K. Chang. Ocat:
Object capture-based automated testing. In Proc. of
ISSTA, pp. 159–170, 2010.
S. Joshi and A. Orso. Scarpe: A technique and tool for
selective capture and replay of program executions. In
Proc. of ICSM, pp. 234–243, 2007.
Bil Lewis. Debugging backwards in time. In Proc. of
IWAD, pp. 225–235, 2003.
Jan Lönnberg, Mordechai Ben-Ari, and Lauri Malmi.
Java replay for dependence-based debugging. In Proc.
of PADTAD, pp. 15–25, 2011.
S. Mirghasemi, J. J Barton, and C. Petitpierre. Querypoint: moving backwards on wrong values in the buggy
execution. In Proc. of ESEC/FSE, pp. 436–439, 2011.
宗像聡, 石尾隆, 井上克郎.
類似した振舞いのオブジェクトのグループ化によるクラス動作シナリオの可視化. 情報処理学会研究報告，2009SE-163，Vol.2009，No.31, pp. 225–232, 2009.
J. Quante and R. Koschke. Dynamic object processgraphs. Journal of Systems and Software, Vol. 81, No.4,
pp. 481–501, 2008.
R. Salkeld and G. Kiczales. Interacting with dead objects. In Proc. of OOPSLA, pp. 203–216. ACM, 2013.
M. Wu, F. Long, X. Wang, Z. Xu, H. Lin, X. Liu,
Z. Guo, H. Guo, L. Zhou, and Z. Zhang. Languagebased replay via data ﬂow cut. In Proc. of FSE, pp.
197–206, 2010.

プリケーションで，事前の実行では確認されていない動作をするメソッドの実行の多くを，実行履歴の記録対象とすることができていることを確認した．
今後の課題としては，より多くの種類のアプリケーションに対して提案手法を適用し，どのようなアプリケーショ

c 1959 Information Processing Society of Japan⃝

8