78

チュートリアルプログラムの動的解析
石尾 隆
動的解析とは，プログラムの実行時情報を収集し，その実際の振舞いや性能を解析するための技術である．本稿では，ソースコードに対する解析と比べた場合の動的解析の特徴を述べ，コードカバレッジの計算や統計的デバッギン
グなどの動的解析手法を解説する．また，読者が解析手法を試すことができるように，Java プログラムの解析に役立つツールについても紹介する．

Dynamic analysis is a category of program analysis techniques that analyze execution traces of a program
to understand the behavior and the performance of the program. This paper explains several applicationsof dynamic analysis such as code coverage analysis and statistical debugging and their eﬀectiveness. The
paper also presents several available tools to analyze Java programs.

である．テストとは，対象プログラムの動作と開発者

1 はじめにが期待する動作とが一致しているかを調査する行為

プログラム解析（Program Analysis）は，人間がであり，デバッグとは，期待した動作と実際の動作が作成したプログラムの記述や構造，振舞いを解析し，異なる原因を調べる行為である．動的解析の技術のいソフトウェア開発に有益な情報を抽出するための技

くつかは，これらの疑問に答えるための情報を効果的術である．プログラム解析技術のうち，解析対象プロに収集する手段を提供する．その他の用途としては，グラムのソースコードや設計文書などのプロダクト

現在稼働しているプログラムの動作の可視化や，実行を解析する技術を静的解析（Static Analysis），プロ時性能の分析などが挙げられる．

グラムの実行を解析する技術を動的解析（Dynamic

本稿では，動的解析の例として，コードカバレッジ

Analysis）と呼ぶ．動的解析手法の多くは静的解析をの計算，統計的デバッギング，動的プログラムスライ

併用するため，境界は明確ではないが，最終結果を得

シングを紹介する．それぞれの手法は，現在も様々なるために解析対象プログラムを 1 度でも実行する必技術が開発されているが，本稿では，解析の仕組みの要がある技術は動的解析に属していると考えるとよ

理解しやすさを優先し，最新の動向ではなく，古典的い．たとえば，本稿で紹介するコードカバレッジの計な手法と具体例に基づいて解説を行う．

算は，プログラムに対するテスト実行から，テストの実施状況の指標を求める動的解析手法である．
動的解析の主な利用目的は，テストおよびデバッグ

本稿で登場する例やツールは，特に明記していない
限り，すべて Java を対象とした解析となっている．

Java は，プラットフォーム非依存で振舞いが定義されており，処理系による差異の少なさ，実装のしやす

Dynamic Program Analysis
Takashi Ishio, 大阪大学大学院情報科学研究科, Graduate School of Information Science and Technology,
Osaka University.
コンピュータソフトウェア, Vol.16, No.5 (1999), pp.78–83.
[解説論文] 1999 年 8 月 3 日受付.

さから，最も活発に動的解析が研究されている言語である．ツールも数多く提供されていることから，動的解析を学習するのにも適している．
本稿の構成は次の通りである．まず 2 章で用語を確認してから，3 章で動的解析の特徴を，4 章で代表Vol. 16 No. 5
的な手法を紹介する．5 章では動的解析の実現に役立
つツールを紹介し，6 章でまとめを述べる．

2 用語
本稿では，プログラムを，ある特定の環境で，特定の入力データの列を与えて 1 回実行するとき，その実行環境および入力データの列を指してテストケース（test case）と呼ぶ．動的解析の適用目的はテストに限らないが，プログラムの特定の機能を実行するために開発者が用意する入力データという意味で，多くの論文でも使用されている表現である．
あるテストケースの実行開始から終了までに実行された命令の列と，そのときのプログラムの状態の系列のうち，解析に必要な情報を記録したものを，そのテストケースに関する実行トレース（exexcution

1999

79

1: public class Number {2:public static void main(String[] args) {3:
Number v = new Number();4:for (int i=0; i<args.length; ++i) {5:
v = new Succ(v);6:}7:System.out.println(v.value());
8:}9:public int value() {10:
return 0;
11:
}
12: }
13: public class Succ extends Number {14:
private Number base;15:
public Succ(Number base) {16:
this.base = base;
17:
}
18:
public int value() {19:
return base.value() + 1;
20:
}
21: }

trace）と呼ぶ．実行トレースに含まれる情報は解析

図1

動的束縛を使ったプログラムの例

手法によって異なり，たとえば，4. 1 節で紹介する
コードカバレッジの計算では，実行された行番号の系
Number.main

列を実行トレースとする．また，メソッドの呼び出し関係を調べる手法では呼び出されたメソッドの名前のPrintStream.println

Number.<init>

Succ.<init>

Succ.value

系列が，実行時のデータの流れを追跡する手法では，各命令がアクセスした変数やオブジェクトの ID，配Number.value

列の添え字といった情報の系列が，それぞれ実行ト
レースとなる．

3 動的解析の特徴

図2

図 1 のプログラムの静的呼び出し関係グラフ．

<init> はコンストラクタを表す．

動的解析は，プログラムの実行トレースとして記録

も，それを実行した日時の情報や，スレッドの実行ス

された，実行中に起きた現象を解析する技術である．

ケジュールによってプログラムの動作が変化し，異なソースコードを対象とする静的解析技術との違いをる結果を出力する可能性がある．

表 1 に示す．静的解析と動的解析の最大の違いは，静静的解析と動的解析の違いを示す例として，Java的解析が「プログラムが起こしうる動作」を解析するにおけるメソッド呼び出しの解析を挙げる．静的解手法であるのに対し，動的解析が「プログラムが実際析を用いた呼び出し関係の抽出は，1 つのメソッド呼に起こした動作」を解析することである．静的解析で

び出し文に対応して実行されうるすべてのメソッド

は，プログラムが起こしうる動作を見逃さないようを列挙する．これに対して，動的解析では，ある特に，プログラムの動作を近似的に計算するため，現実

定のテストケースでの呼び出し関係を抽出する．図 1には起こらない動作まで計算結果に含めてしまうこに示すプログラムは，3 行目で変数 v に Number オブとがある．一方，動的解析は，プログラムの実行を解

ジェクトを代入するが，コマンドライン引数が存在析しているので，プログラムの動作を正確に反映したする場合は変数 v の中身を 5 行目で作成した Succ オ

結果が得られる．ただし，動的解析の結果は，毎回同ブジェクトに入れ替える．7 行目での v.value() メ一であるとは限らない．テストケースが同一であってソッドの呼び出しは，動的束縛の対象である．すなわコンピュータソフトウェア

80
表1
比較項目
解析に必要なもの
解析対象となる動作
解析結果の再現性
解析の基盤ツール
利用可能な情報の例

静的解析と動的解析が持つ主な性質

静的解析
コンパイル可能なソースコード
プログラムが起こしうる動作
解析対象が変更されない限り有効
コンパイラ
ソースコードの位置情報，制御構文，
データフローグラフ，コメントの内容

動的解析
実行可能なプログラム，テストケース
プログラムが起こした動作
解析結果が毎回同一であるとは限らない
デバッガ
命令の実行順序，実行回数，実行時間，変数の実際の値

羅するようにプログラムを実行することができれば，
Number.main

その動的解析の結果は，静的解析の結果に近づいていくことになる．静的解析では，プログラムの実行経路

PrintStream.println

Number.<init>

Succ.<init>

Succ.valueを列挙する際に，実際には発生しえない実行経路を多数抽出する場合がある [19] ことから，最終的な結果がNumber.value

完全に一致するとは限らない．多数のテストケースを用いた動的解析のほうが，プログラムの実際の動作に

図3

図 1 のプログラムに引数を 1 つ与えて実行したときの動的呼び出し関係グラフ

近い結果を得られる場合もある．ただし，あらゆるテストケースを網羅的に実行することは不可能であり，見逃しが生じる可能性を考慮する必要がある．スレッ

ち，この時点で変数 v に格納されているのが Number

ド間のデッドロックやメモリリークのように，見逃し

オブジェクトであれば Number クラスに定義されたが重大な障害を引き起こすと考えられる欠陥がプロ

value() メソッドを，Succ オブジェクトであった場

グラムに含まれているかどうかを調査する場合は，プ合は Succ クラスに定義された value() メソッドを実

ログラムの動作を網羅するために静的解析が用いら行する．そのため，静的な呼び出し関係の解析 [3] [28]れることが多い．

では，図 2 に示すような呼び出し関係が得られる．こ動的解析は，実際の動作を解析するという特徴にれに対して，1 つのテストケースとして，コマンドラ

基づいて，様々な目的に利用されている技術である．

イン引数を 1 つだけ与えてプログラムを実行した場合その種類は多岐に渡っており，本稿ですべてを紹介すの動的な呼び出し関係の解析を行うと，5 行目が 1 度ることはできないが，代表的な手法を表 2 に挙げる．

だけ実行され，Succ オブジェクトが v に代入される

実行経路の分析は，動的解析の基本的な手法であり，ため，図 3 に示すような呼び出し関係が得られる．こ観測した（あるいは観測中の）プログラムの動作を，の呼び出し関係グラフは，実行されなかった処理，た

開発者に有用な形で提示するための技術である．欠陥

とえば引数が与えられなかった場合の Number.mainの分析はデバッグを目的とした手法で，欠陥の原因をメソッドから Number.value メソッドへの呼び出し特定するための技術や，欠陥が発生した状況を再現しや，引数が 2 個以上あった場合に生じる Succ.value

分析するための技術がこれに含まれる．振舞い仕様

メソッドから自分自身への呼び出しに関する情報を含のマイニングは，変数の値域やメソッドの実行順序な

まない．つまり，一部の呼び出しは見逃していること

ど，ソースコードには書かれていない暗黙のルールをになるが，引数が 1 つの場合における正確な振舞い探索するための技術であり，主にプログラム理解に使を示したグラフとなり，この実行に関してデバッグ等

われている．

の調査を行いたい開発者にとっては，静的解析よりも有益な情報となる．
一般に，プログラムが取りうるあらゆる振舞いを網

動的解析手法には様々なものがあるが，プログラムの実行が完了してから実行トレースを解析する手法
をオフライン解析（oﬄine analysis），実行を継続しVol. 16 No. 5
表2
カテゴリ

手法の名称
コードカバレッジの計算

実行経路の分析

振舞いの可視化
フェイズ検出
統計的デバッギング

欠陥の分析

動的スライシング

Capture & Replay
プロトコルマイニング
振舞い仕様のマイニング

動的不変条件の検出Live Sequence Chart の抽出

1999

81

代表的な動的解析手法
手法の概要
実行されたプログラム文の割合から，テストの進捗状況を示す
数値を計算する． [4] [5]プログラムの実行内容をシーケンス図等の形式で可視化する．
[6] [21] [23] [29]プログラムが，ある処理の実行から別の処理に移ったタイミングを検出する． [24] [32]
成功した実行と，失敗した実行の差から，欠陥の原因となっているコードを自動的に特定する． [13] [20] [35]
開発者が指定した変数の値に影響を与えたプログラム文を特定する． [1] [30]あるオブジェクトの入出力をすべて記録し，オブジェクトの状態を再現する． [14]単一あるいは少数のオブジェクトに対するメソッド呼び出し順
序のルールを発見する． [11] [18]変数の実際の値から，各変数の値域や変数間の関係式などを不変条件として抽出する． [10]オブジェクト間のメソッド呼び出しパターンを解析し，パターンの出現順序を可視化する． [17]た状態で実行トレースを解析する手法をオンライン
解析（online analysis）と呼ぶ．オンライン解析は，
その時点までに得られた部分的な実行トレース情報
しか使用できないかわり，解析が終わった実行トレー
ス情報を蓄積する必要がなく，また，解析結果をプ
ログラムの実行制御などに反映することが可能であるという特徴を持つ [8]．表 2 に示した手法の中では，フェイズ検出手法 [24]，プロトコルマイニング [11] がオンライン解析に属する．最近の論文では，どちらに属しているかを明記していることが多いので，実行を停止できないソフトウェアに対する解析技法に興味がある場合は，オンライン解析と記述された論文を調べるとよい．

4 動的解析手法の紹介
本章では，動的解析手法として，コードカバレッジ

1: public class LeapYear {2:public static void main(String[] args) {3:
int year = Integer.valueOf(args[0]);4:String answer;
5:
if (year % 4 == 0) {6:
if (year % 100 == 0) {7:
if (year % 4*100 == 0) {8:
answer = "yes";
9:} else {10:answer = "no";
11:
}
12:
} else {13:
answer = "yes";
14:
}
15:
} else {16:answer = "no";
17:
}
18:
System.out.println(answer);
19:
}
20: }
図4

うるう年の判定を行うプログラム（誤りを含む）の計算，統計的デバッギング，動的プログラムスライ
シングを紹介する．これらの手法は，いずれもアイ

表す年がうるう年なら yes，そうでなければ no を出ディアは簡明であるが，現在の様々な研究の基盤と力する．うるう年の条件は，4 の倍数でありかつ 100

なっている古典的な手法である．

の倍数ではないこと，あるいは 400 の倍数であるこ

各手法の具体的な手順を示すために，図 4 に示す
例題プログラムを用いる．このプログラムは，うるう年の判定を実装しており，コマンドライン引数に 指定された数値 1 つを変数 year に代入し，その数値がとである．なお，この例題プログラムには，意図的に誤りを 1 つ混入させている．

コンピュータソフトウェア

82
4. 1 行カバレッジの計算

行カバレッジの値を計算するには，プログラムに含最初に紹介する動的解析は，ソフトウェアテストのまれた命令行の集合と，実際に実行された命令行の集基礎となっている動的解析手法，行カバレッジ（Line合が必要である．前者は静的解析によって，後者はプCoverage）の計算である．

ログラム実行の観測によって求める．

4. 1. 1 解析の目的

4. 1. 3 Cobertura を使ったカバレッジの計算

コードカバレッジとは，十分なソフトウェアテスト

行カバレッジの計算は，ソフトウェアテストの基礎を実施したかを評価するための網羅性の指標である．

となっていることもあり，様々なソフトウェアに組み

その 1 つ，行カバレッジ（Line Coverage）は，テス
トケース集合によって実行されたプログラムの行番号

込まれている．本稿では，無償で使えるソフトウェア
である Cobertura†1 を用いて，例題プログラムを解析の集合が，実行可能な命令行に対して占める割合を求する．Cobertura を使用したカバレッジ計算の手順めたものである．この割合が 100% になったというは，次のようになる．

ことは，すべての行が少なくとも 1 回はテスト実行されたことになる [4]．そのため，行カバレッジの計測
は，テストの実施状況を知る重要な解析手法となっている．本稿では，テスト技法そのものを扱うわけではないので，行カバレッジを 100%に近づけるようにテ
ストケースを作成する方法に関しては取り扱わない．

4. 1. 2 解析の方法

1. 解析対象プログラムに実行トレースを記録するための命令を埋め込む．

2. 1 つ以上のテストケースを実行し，実行トレースを記録する．

3. 実行トレースから，カバレッジ情報のレポートを生成する．
行カバレッジの計算には，プログラムに含まれた命テスト対象プログラムの実行可能な命令行の集合

令行の集合と，実行された行の集合が必要である．そを L とすると，ある 1 つのテストケース t に対するのため，まず，解析対象プログラムを分析し，実行可

行カバレッジ Ct は，t に関するプログラムの実行ト

能なすべての命令行を列挙し，実行トレースを記録す

レースに含まれる行の集合 Lt によって，次のようにるための命令を埋め込む．Microsoft Windows 環境

求められる．

では，Cobertura に付属しているバッチファイルを

Ct

=

|Lt |
|L|

以下のように実行する．

cobertura-instrument.bat
図 4 に示すプログラムの場合，変数宣言や記号（“}”）--destination instrumented bin

だけの行を取り除くことで，実行可能な命令を持つ行

コマンドに与えている引数--destination は，出の集合 L = {3, 5, 6, 7, 8, 10, 13, 16, 18} が得られる．

力先の指定である．bin ディレクトリ以下に配置さ

ここで，入力値 year として 2011 を与えてプログラ

れているプログラムを入力として，解析用命令をムを実行すると，Lyear=2011 = {3, 5, 16, 18} となる

追加したプログラムを instrumented という名前のことから，このテストの行カバレッジの値は次のようディレクトリに書き出す．このとき，処理を実行しになる．

たディレクトリには，プログラムの情報を格納した

Cyear=2011=|Lyear=2011 |4= = 0.444 · · ·|L|9cobertura.ser というファイルが生成される．
Cobertura は Java バイトコード変換を採用しておテストケース集合 T が与えられたときは，個々のテり，コンパイル後のバイトコードに埋め込まれている

ストケースで実行された行の和集合を使って行カバ

命令と行番号の対応情報を使って，命令行の集合を取レッジ CT の値を求める．

得し，各命令の直前に，実行トレースを記録するた

CT =

|

∪
t∈T

|L|

Lt |

めの命令を埋め込む．図 4 に示すコードにこの変換†1 http://cobertura.sourceforge.net/

Vol. 16 No. 5を適用した後，Java Decompiler †2 を使ってソースコードに変換し，行カバレッジに関するコードを抽出した結果を図 5 に示す．行末に “*” を付与した行が，Cobertura が挿入した命令である．このソースコー
ドを見ると，各行の命令の直前に，クラス名と行番号を引数としたメソッド呼び出しが挿入され，どの行を実行したかを記録するようになっていることが分かる．なお，Cobertura はブランチカバレッジも計算するため，実際の生成コードには，さらに条件分岐に関するロギング処理も加わる．
実行トレースの記録処理を埋め込んだプログラム
を用いて，通常のプログラム実行と同様にテストケー
スの実行を行う．この実行では，たとえば以下のように，Cobertura のライブラリファイルと変換後のクラスファイルを指定してプログラムを実行する．

java -cp "cobertura.jar;instrumented"
LeapYear 2011
プログラムの実行トレースは，バイトコード変換の際に生成された cobertura.ser というファイルに保存される．以下のコマンドで，このファイルとソース
コードを読み込み，引数--destination で指定されたディレクトリに HTML 形式のレポートを出力する．

cobertura-report.bat--destination report src

1999

83

public static void main(String[] args){
TouchCollector.touch("LeapYear", 3);*
int year = Integer.valueOf(args[0]);String answer;
TouchCollector.touch("LeapYear", 5);*
if (year % 4 == 0) {TouchCollector.touch("LeapYear", 6);*
String answer;
if (year % 100 == 0) {TouchCollector.touch("LeapYear", 7);*
String answer;
if (year % 4 * 100 == 0) {TouchCollector.touch("LeapYear", 8); *answer = "yes";} else {TouchCollector.touch("LeapYear", 10); *answer = "no";}} else {TouchCollector.touch("LeapYear", 13);*
answer = "yes";}} else {TouchCollector.touch("LeapYear", 16);*
answer = "no";}TouchCollector.touch("LeapYear", 18);*
System.out.println(answer);}
図5

Cobertura によってロギング命令が挿入された

コード．挿入された命令を行末の “*” で示している．

例題プログラムに引数 2011 を与えて実行したときのカバレッジの出力例を図 6 に示す．ソースコードのうなバイトコード上の表現の影響で，4. 1. 2 項で示し左端に行番号と，その行の実行回数が表示されており，

たカバレッジの値は 9 行中の 4 行を実行していたが，まだ実行されていない行，条件分岐の true と false

Cobertura の出力は 11 行中の 5 行となっている．

のどちらか一方がまだ実行されていない行が赤色で強Cobertura は出力ファイル cobertura.ser に実調表示されている．この図において，1 行目のクラス

行トレースのデータを蓄積していく．複数のテス宣言と，19 行目のメソッド終了の中括弧が実行可能

トケースがある場合は，それらを順番に実行して命令として表示されているが，これは Cobertura がいけば，カバレッジの値が増加していく様子を確Java バイトコードを解析対象としているために生じ認することができる．蓄積されたカバレッジ情報をている現象である．1 行目は LeapYear クラスのソー破棄する場合は，この出力ファイルを削除してからスコードには宣言されていない暗黙のコンストラク

cobertura-instrument.bat を再実行し，プログラタに対応しており，19 行目は戻り値のないメソッド

ムを一度も実行していない状態のファイルを作り直せで省略されている（がバイトコード上では命令としばよい．

て出現している）return 文に対応している．このよ4. 1. 4 手法の現状
行カバレッジの計算は非常に重要な意義を持ち，多†2 http://java.decompiler.free.fr/

くのプログラミング言語で，様々なツールが公開されコンピュータソフトウェア

84

ラクタを生成してしまう．そして，オブジェクトを生成しないクラスに関しては，コンストラクタが実行されていないために，行カバレッジが 100%に到達しないという結果になる．また，過剰なエラーチェックなど，意味のない条件分岐が記述されると，ブランチ
カバレッジも 100%に到達しないという状況が起きうる．100%に近づいたカバレッジが，既に十分な値であるかどうかを判断するには，コンパイラの挙動や対象プログラムの内容に関する知識が必要となる．
カバレッジ計算に関しては，実行トレースの計測コ
ストを削減するための研究が実施されている．その 1
つは，データフローに関するカバレッジを計算する
際，実行トレースとして記録しなければならないデー
タ量を静的解析によって減らす手法である [26]．また，
図6

Cobertura の出力した HTML ファイルの例．

Java を対象とした手法ではないが，ある一定間隔に例題プログラムの入力 year に 2011 を指定した場合のカ

時間を区切り，その区間内では実行順序を無視して，バレッジ情報を表示している．

実行していたコードの位置を高速に記録する手法が提案されている [9]．

ている．既に普及した技術の 1 つではあるが，行カ
バレッジの計算を適用する際には，2 つの注意点が存

4. 2 統計的デバッギング手法

在する．

テストを実行していくと，プログラムの誤りに行

まず，行カバレッジが 100%になっても，プログラ

き当たることがある．図 4 のプログラムは，2011 にムの実行条件を完全に網羅しているわけではない．

対しては正しく no を，2012 を入力した場合は正し

行カバレッジはプログラムの各行を 1 回だけ実行すく yes を出力する．しかし，2100 を入力した場合は，ればよいので，たとえば “if (x) y=readData();”2100 年はうるう年ではないにも関わらず，yes を出というように else 節を伴わない条件分岐が存在す

力してしまう．普通の開発環境であれば，デバッガをると，条件が真の場合のみ実行すれば，行カバレッ

起動し，この出力が得られた理由を分析することにな

ジは達成されることになる．このような行カバレッ

るが，本節では，行カバレッジの情報を用いた統計的ジの弱点を補う指標として，条件分岐で使われた真デバッギング手法の適用例を示す．

偽値の網羅性を用いるブランチカバレッジ（Branch

4. 2. 1 解析の目的

Coverage）や，実行パスを区別するパスカバレッジ

統計的デバッギング（Statistical Debugging） [36]（Path Coverage）などが存在する [5]．ただし，これは，プログラムの欠陥の原因を特定する Fault Local-

らの指標も完全ではなく，たとえばブランチカバレッ

ization と呼ばれる技術の 1 つで，プログラムの実行

ジの場合は，条件分岐以外，たとえば動的束縛や例外に成功した場合と失敗した場合の実行時情報が与え処理によって生じる実行の分岐は考慮されていないこられたとき，それらの振舞いの差分から，欠陥の原因とが多い．

となっているプログラム文（あるいはデータフロー等

カバレッジに関するもう 1 つの問題は，ソースコーの問題となる振舞い）を特定する手法である．開発者

ドと実行バイナリの差異である．本稿で示した例のは，プログラムに対して適切なテストを実行しさえす

ように，クラスにコンストラクタが宣言されていな

れば，欠陥の原因として疑わしいプログラム文の集合

い場合，Java コンパイラは引数を持たないコンストを特定することができ，それらのプログラム文を優先Vol. 16 No. 5
的に調査することが可能となる．

1999

85

を示している．実際に，この問題の原因は 7 行目の条

4. 2. 2 解析の方法

件分岐にある．剰余演算子 “%” と乗算演算子 “*” の統計的デバッギングの基本的な考え方は，Jones ら

優先順位は同じであるから [12]，“year % 4*100” と[13] が提案している Tarantura というツールに実装いう式は “(year % 4)*100” と解釈され，7 行目のされた，次のようなものである．

条件式は常に真となって 8 行目の処理が実行されて• ある文を実行したテストケースの多くが，正しい結果を出力していれば，その文と欠陥との関係
は弱い．

いる．
統計的デバッギングの利点は，多数のテストケースが存在しているとき，疑わしいプログラム文を自動的• ある文を実行したテストケースの多くが，誤っに抽出できることである．ただし，Tarantura の使うた結果を出力していれば，その文と欠陥との関係

計算式はテストケースごとの行カバレッジの差に基づは強い．

いているため，成功テストケースと失敗テストケース

Tarantura は，この考えに基づいて，プログラムのカバレッジが一致するとき，欠陥の原因を特定できに含まれる各文の安全度を計算する．この計算を行ない．たとえば，入力として 2000 を与えた場合のカうために，まず，開発者は，プログラムに対するテス

バレッジは 2100 の場合と完全に一致するが，出力はトケース集合 T を用意し，各テストケース t ∈ T を

yes で正しい．そのため，2011, 2012, 2100, 2000 の実行する．このとき，各テストケースについて個別に4 つのテストケースから計算を行うと，7 行目，8 行

行カバレッジを計測し，また，出力結果が予測通りで目に対する %passed の値が 0.33 となり，これらのあったものを成功テストケース P (passed)，そうで行に対する Saf ety の値が上昇する（プログラム中なかったものを失敗テストケース F (failed)

で最も低い値であることに変わりはない）．

として分類する．P ，F はそれぞれ少なくとも 1 つ存在し

4. 2. 3 手法の現状

なければならない．

統計的デバッギングに関しては，様々な拡張が存在

テスト実行が終わったら，プログラムの各文 s につしており，条件分岐によるコードブロック間の制御のいて，P に属する成功テストケースのうち，プログラ

移動に着目したモデル [35] や，データアクセス順序に

ム文 s を実行したものの割合を計算し，%passed(s)よる並列プログラムのデバッグ [20] などがある．統計とする．また，F に属する失敗テストケースのう的デバッギングは，故障の発生に再現性がない場合でち，プログラム文 s を実行したものの割合を計算し，あっても，故障が発生した場合の実行トレースが得ら%f ailed(s) とする．そして，プログラムの各文 s のれれば，故障が発生しなかった場合の実行トレースと安全度 Saf ety(s) を，以下の式で求める．

比較することで，その原因に近づける可能性がある．
そのため，現在も活発に研究が進められている．

Saf ety(s)=%passed(s)%passed(s) + %f ailed(s)統計的デバッギングの弱点は，4. 2. 2 項でも述べた通り，問題のある命令を実行しても，その影響が検出

Tarantura は，2011 年 9 月現在，残念ながら公開できなかったテストケースは成功として扱うため，原されていないが，テストケースごとの行カバレッジ

因の特定を阻害してしまうことがある．この問題はの情報を取得することができれば，テストケースご

Coincidental Correctness として知られており，実行との成功か失敗かの判定を人間が指定することで，トレースとして記録する情報を増やすことで対策す

Saf ety(s) の値を計算することができる．図 4 のプる手法が提案されている [31]．

ログラムに対して 2011, 2012, 2100 を入力し，実行
結果から手作業で Safety の値を計算した結果を表 3

4. 3 動的プログラムスライシングに示す．ここでは，7 行目および 8 行目の Saf ety の4. 2 節で紹介した統計的デバッギングは，プログラ

値が 0 となっており，欠陥の可能性が最も高いこと

ムの中から欠陥の原因である可能性がある文を提示コンピュータソフトウェア

86
表3

Tarantura の Saf ety 値の計算例

Source Code3: int year = Integer.valueOf(args[0]);4:String answer;
5:
if (year % 4 == 0) {6:
if (year % 100 == 0) {7:
if (year % 4*100 == 0) {8:
answer = "yes";
9:} else {10:answer = "no";
11:
}
12:
} else {13:
answer = "yes";
14:
}
15:
} else {16:answer = "no";
17:
}
18:
System.out.println(answer);
19:}
期待される出力:
実際の出力:
実行の成否:

Line Coverage
20112012 2100
x
x
x
x

x
x

x
x
x
x

x

x
x

x

x

no
no
P

yes
yes
P

no
yes
F

%passed1.0%f ailed
1.0

Saf ety
0.5

1.0
0.5
0
0

1.0
1.0
1.0
1.0

0.5
0.33
0
0

0.5

0

1.0

0.5

0

1.0

1.0

1.0

0.5

する手法であるが，実際にどの文が原因で，なぜ問題

係 T C (Test-Control) を次のように定義する [27]．

が起きるかを調べるのは開発者の仕事である．プログ• ある命令の実行 p が代入した変数 v の値が，そラムの実行から，欠陥の原因を分析する技術の 1 つれ以降の命令の実行 q までに上書きされることとして，動的プログラムスライシングを紹介する．

なく，q で使用されたとき，関係 DU (p, q) が成

4. 3. 1 解析の目的

り立つものとする．

動的プログラムスライシング（Dynamic Program• ソースコード上で，実行制御文 t の条件節の結Slicing） [1] は，ある特定のテストケースに対して，

果が命令 s を実行するかしないかを決定するとある実行時点での変数の値に影響を与えた命令列をき，命令 s のある実行時点を q とすると，q よ

特定するための手法である．影響を与えた命令とは，り前で q に最も近い t の実行時点 p について，

その変数の値を計算した命令と，命令を実行するか

関係 T C(p, q) が成り立つものとする．

どうかを判定した条件分岐命令である．変数の値は，関係 DC(p, q) および T C(p, q) は，それぞれ p か

通常，他の変数の値から計算されるので，時系列をさら q への有向辺と考えると，実行時点を頂点としたかのぼる形で推移的に影響を探索していき，なぜその有向グラフと考えることができる．このグラフを動的値が計算されたのかを示すことが，スライシングの目

依存グラフと呼ぶ．例として，図 4 のプログラムに的である．

2100 を入力した場合の実行系列に対する動的依存グ

動的プログラムスライシングもまた，デバッグ支援

ラフを図 7 に示す．図 7 において，実線の辺は，ラベ手法であるが，統計的デバッギングとは異なり，単体

ルに書かれた変数の値が到達したことによる DU 関のテストケースでの解析を行う．

係を表現しており，control というラベルの付いた4. 3. 2 解析の方法

点線の辺は T C 関係を表現している．

動的プログラムスライシングは，実行された命令間

動的プログラムスライシングは，実行された命令でのデータ依存関係，制御依存関係を計算する．まず，列を，時系列と逆方向にさかのぼる形で，問題の原因

データ依存関係 DU (Deﬁnition-Use) と制御依存関へと近づいていくアプローチである．開発者は，正しVol. 16 No. 5

1999

87

時間の実行が必要な処理に関しては，実行のオーバー
3: int year = Integer.valueOf(args[0]);year
5: if (year % 4 == 0) {ヘッドが通常のツールのみで行うデバッグ作業時間よりも長くなり，適用が困難であると考えられる．

4. 3. 3 手法の現状

year

動的プログラムスライシングのように，プログラ
controlyear

6: if (year % 100 == 0) {control

ムの実行を過去にさかのぼるアプローチは，デバッグ
において有望な技術として，活発に研究が行われている．
動的プログラムスライシングの拡張の 1 つとして，

7: if (year % 4*100 == 0) {control

変数の値まで実行トレースに記録しておき，「なぜ変数 answer には “yes” が代入されたか」といった対話的な質問方式で，動的依存グラフの辺を辿っていく

8: answer = "yes";

作業を支援する手法が提案されている [15]．また，ス
answer
18: System.out.println(answer);

ライシングのように過去にさかのぼるアプローチを突き詰め，実行トレースとして各命令を実行したときのメモリの完全な情報を保存し，プログラムの任意の

図7

y=2100 の実行に対する動的依存グラフ

時点の変数の状態を分析する Omniscent Debugging[16] も提案されている．

くない出力結果が得られた 18 行目の実行を基点に，これらの手法の実用化に向けての最大の障壁は，記answer が 8 行目から来たこと，その実行が 7 行目の録すべきデータ量が非常に多いことである．動的プロ

if 文によって定められたことをグラフ探索によってグラムスライシングに対しては，観測する必要がある

確認することができる．通常のデバッガが，ブレーク

データを事前に計算しておく手法 [34] が提案されていポイントとステップ実行を用いて問題を起こした命令

る．また，Omniscent Debugging に対しては，実行を特定する必要があるのに対し，問題が生じた時点かトレースを完全に記録するかわりに，「過去の状態にらさかのぼる探索となるため，原因の分析を容易に行戻す命令」を生成しておき，過去の状態が必要なときうことができる．

にそれらの命令を実行する手法 [2] が提案されている．

動的プログラムスライシングでは，データがどこで計算され，どこで使われたかを追跡する必要があるた

5 動的解析手法の構築

め，実行トレースとして，オブジェクトのフィールド

コードカバレッジの計算などの有名な手法は既にや配列の要素へのアクセスを記録しておく必要があ

様々なソフトウェアに組み込まれているが，動的解析

る．そのため，実装上は，計算コストが非常に高いの手法の研究を行う場合は，その目的に合った実行トが弱点である．オブジェクト ID などを実行トレース

レースの取得が必要である．本章では，動的解析の研として記録するためのコストについては，櫻井ら [25]

究において重要な要素となる，実行トレースの取得方

が Traceglasses というデバッグ支援ツールの提案の法とその注意点について述べる．

中で実験しており，プログラムの実行時間がおよそ 4
倍から 14 倍，最大で 93 倍になったと報告している．

5. 1 実行トレースを記録するためのツール

櫻井らの手法自体は動的プログラムスライシングとJava を解析対象とした場合に利用可能なツールには異なるが，この結果を踏まえると，実行トレースをは，以下のようなものがある．

記録する処理の実行時間が数秒程度と短い場合には，

jdb デバッガ jdb は，JDK に標準で付属してい動的プログラムスライシングは適用可能であるが，長るコマンドラインデバッガである．小さなプログ

コンピュータソフトウェア

88
jdb の初期化中です...

停止する．プログラムが一時停止している間は，> stop in LeapYear.main

プログラムの状態を観測するための様々なコマン

ブレークポイント LeapYear.main を保留しています。

ドが実行できる．その 1 つである monitor コマ

クラスがロードされた後に設定されます。

> run

ンドは，プログラムが一時停止したときに自動的

LeapYear 2100 を実行しますに実行したいコマンドを指定するもので，次のよ

uncaught java.lang.Throwable を設定しました
保留した uncaught java.lang.Throwable を設定しました

うにステップ実行命令である next コマンドを設>定してから，next コマンドでプログラムの実行

VM が起動しました: 保留した ブレークポイントを開始すると，ステップ実行による停止に対してLeapYear.main を設定しました

ブレークポイントのヒット: "スレッド=main", LeapYear.main(),line=3 bci=0

さらにステップ実行を行わせることができ，1 行
ずつプログラムを実行することができる．

monitor next

main[1] monitor next

next
jdb は，プログラムを一時停止したとき，停止しmain[1] next>
ステップ完了: "スレッド=main", LeapYear.main(), line=5 bci=10たスレッド名，メソッド名，実行直前の命令の行> >番号，バイトコード上での位置をメッセージとし

ステップ完了: "スレッド=main", LeapYear.main(), line=6 bci=16て書き出す．例として，上記の処理を行ったとき> >ステップ完了: "スレッド=main", LeapYear.main(), line=7 bci=23に jdb が出力したメッセージの列を図 8 に示す．

> >“ステップ完了 ... line=8 ...” という記述か

ステップ完了: "スレッド=main", LeapYear.main(), line=8 bci=32> >ら，8 行目の命令 “answer = "yes";” に到達しステップ完了: "スレッド=main", LeapYear.main(), line=18 bci=53たことが示されており，プログラムの実行が意図> > yesとは異なる結果になっていることを知ることがステップ完了: "スレッド=main", LeapYear.main(), line=19 bci=60> >できる．jdb が出力する行番号の列を保存し，分

アプリケーションは終了しました

析するツールを作成すれば，行カバレッジを計算することができる．この方式は，ステップ実行に

図8

jdb を用いたステップ実行の自動反復

よってプログラムの一時停止，実行再開を繰り返すので，実行効率は非常に悪い．教育用の数十ラムの実行に対して実行トレースを書き出すの行のプログラムであれば問題なく実行できるが，であれば，次のような手順で，簡単に実行するこ

一般的なプログラムを解析する用途には不向きとができる．

である．

まず，jdb を実行する．これは java コマンドJVMTI JVMTI [22] は Java Virtual Machine

で Java プログラムを実行する場合と同様で，たTool Interface の略称で，jdb を含めた様々なとえば jdb LeapYear 2100 のように入力する．

ツールが Java 仮想マシンと通信するためのインjdb が起動した時点ではプログラムはまだ実行さタフェースである．観測用の「エージェント」は，れていないので，次のように main の開始直後に

JDK に付属している C 言語用のヘッダファイル

停止するようブレークポイントを設定し，プログ

jvmti.h を使って C 言語などで作成することがラムの実行を指示する．

できる動的リンクライブラリの一種で，JVMTI

stop in LeapYear.mainの仕様に従った特定の名前の関数を用意しておく

runと，プログラムの実行開始，メソッド呼び出し，

このコマンドを実行すると，プログラムの実行

スレッドの実行開始などの様々なイベントの通知が開始され，main メソッドの先頭で実行が一時を仮想マシンから受け取ることができる．

Vol. 16 No. 5

1999

89

JVMTI は，Java 仮想マシンの外部からプログ

い形式で記述することができるため，ASM と比ラムの動作を観測するため，スレッドの制御やべると，バイトコードに詳しくない開発者でも容メモリ管理など，Java プログラムの制御情報を易に使うことができる．バイトコード書き換えと獲得することができる．また，jdb を経由していうアプローチを採用しているので，その他の利Java 仮想マシンを操作する場合に比べれば高速

点や弱点に関しては ASM と同様である．

であり，特定の目的に特化したツールを作成することができる．一方で，オブジェクトの参照や変AspectJ Java のアスペクト指向拡張である AspectJ †5 は，メソッド呼び出しの記録など，ある数の値などを取得する場合には，逐一仮想マシン

一定の範囲に限っては，実行時情報の記録に関内部のデータ構造にアクセスすることになり，実する処理を非常に簡単に記述することができる．

行時に大きなオーバーヘッドとなることがある．

記述したコードは，AspectJ の処理系によって

ASM ASM†3 はバイトコードの読み書きを行うたJava のバイトコードへと組み込まれるため，そめのライブラリである．本稿で紹介した Cober-の他の特徴は ASM や Javassist と同様である．

tura も内部ではこれを使用している．ライブラ

動的解析手法を自分で実装する場合，ツールの選び

リとしては，クラス構造がシンプルであること，方が重要である．まず，実行速度を重視するのであれ

Java Generics 情報を含むバイトコードも正しくば，実行トレースの記録はプログラム本体に埋め込む

扱えることが特徴である．実行トレースの記録ほうがよい．そのため，バイトコード書き換えにあたを記述するための特別な支援が用意されている

る ASM，Javassist，AspectJ が優れている．このう

わけではないので，たとえばメソッド呼び出しとち，メソッド単位など，粗い粒度の記録だけで十分なして invokestatic 命令を挿入するというよう

ら，学習コストの観点から AspectJ が優れている．

に，Java バイトコードに関する知識が必要であスレッドの切り替わりやメモリ管理など，プログ

る．学習コストと引き換えに，柔軟さは高い．

ラムの外にある情報をできるだけ正確に解析したい

バイトコード書き換えによって作成したコード

場合や，プログラムを書きかえることによる処理のは，対象プログラムの一部として実行されるた変化が気になる場合は，JVMTI が適している．jdb

め，JIT コンパイルなどの最適化の恩恵を受けは，利用は容易であるがオーバーヘッドが大きいのることができ，JVMTI に比べると実行速度は高で，JVMTI で利用可能な情報を知るための学習用と速となることが多い．プログラムのオブジェクトして使用し，本格的な解析を実施する場合は JVMTIの状態や，変数の値にアクセスしやすいことが特に移行するべきである．

徴である．一方で，スレッド間の同期制御など，解析対象のプログラムの記述の影響を受けやす5. 2 実行トレース記録時の注意

く，プログラムの振舞いを破壊しないように慎重実行トレースは，プログラムをある特定の実行環な実装が必要となる．また，バイトコード書き換

境，特定の入力データに対して実行したときに獲得でえ技術を用いてプログラムに処理を追加するよきる情報である．そのため，実行条件のわずかな違い

うなフレームワークと併用する場合は，バイトから，実行トレースの結果が変わってしまうことに注

コードの書き換え順序に注意する必要がある．
Javassist Javassist†4 は，バイトコード書き換え

意しなければならない．実行トレースに影響を与える

ツールの 1 つである．バイトコードとして書き• ユーザによる操作．ユーザの操作を記録，再生

加えたい処理の内容を Java のソースコードに近するツールなどを使用しない限り，完全に同一の†3 http://asm.ow2.org/†4 http://www.csg.is.titech.ac.jp/~chiba/
javassist/

要素を次に示す．

操作を繰り返すことはできない．マウス操作など†5 http://www.eclipse.org/aspectj/

コンピュータソフトウェア

90に対応して実行されるイベントハンドラは，異なムを実行することで，動的解析の特徴を理解すること

る回数実行されることがある．

が重要である．

• マルチスレッド処理におけるスレッド間のイン
タラクション．スレッド実行のスケジュールは実

参 考 文 献行時に決定されるため，スレッド間での命令の実[ 1 ] Agrawal, H. and Horgan, J. R.: Dynamic
Program Slicing, SIGPLAN Notices, Vol. 25,
No. 6(1990), pp. 246–256.
[ 2 ] Akgul, T., Mooney III, V. J., and Pande,S.: A Fast Assembly Level Reverse Execution
Method via Dynamic Slicing, Proceedings of the
26th ACM/IEEE International Conference on Software Engineering, May 2004, pp. 522–531.
[ 3 ] Bacon, D. F. and Sweeney, P. F.: Fast Static
Analysis of C++ Virtual Function Calls, Proceedings of the 1996 ACM SIGPLAN Conference on
Object-Oriented Programming Systems, Languages,
and Applications, October 1996, pp. 324–341.
[ 4 ] ボーリス・バイザー: ソフトウェアテスト技法, 日経
BP 出版センター, February 1994.
[ 5 ] Binder, R. V.: Testing Object-Oriented Systems:
Models, Patterns, and Tools, Addison-Wesley Professional, October 1999.
[ 6 ] Briand, L. C., Labiche, Y., and Leduc, J.: Towards the Reverse Engineering of UML Sequence
Diagrams for Distributed Java Software, IEEE
Transactions on Software Engineering, Vol. 32,
No. 9(2006), pp. 642–663.
[ 7 ] Cornelissen, B., Zaidman, A., van Deursen, A.,
Moonen, L., and Koschke, R.: A Systematic Surveyof Program Comprehension through Dynamic Analysis, IEEE Transactions on Software Engineering,Vol. 35, No. 5(2009), pp. 684–702.
[ 8 ] Dwyer, M. B., Kinneer, A., and Elbaum, S.:
Adaptive Online Program Analysis, Proceedings ofthe 29th ACM/IEEE International Conference on
Software Engineering, May 2007, pp. 220–229.
[ 9 ] Edwards, D., Wilde, N., Simmons, S., andGolden, E.: Instrumenting time-sensitive software
for feature location, Proceedings of the 17th IEEE
International Conference on Program Comprehension, May 2009, pp. 130–137.
[10] Ernst, M. D., Cockrell, J., Griswold, W. G.,
and Notkin, D.: Dynamically Discovering Likely
Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering,Vol. 27, No. 2(2001), pp. 99–123.
[11] Gabel, M. and Su, Z.: Online Inference and Enforcement of Temporal Properties, Proceedings ofthe 32nd ACM/IEEE International Conference on
Software Engineering, May 2010, pp. 15–24.
[12] Gosling, J., Joy, B., Steele, G., and Bracha,G.: Java Language Specification, The 3rd Edition,
Prentice Hall, June 2005.
[13] Jones, J. A., Harrold, M. J., and Stasko, J.:
Visualization of Test Information to Assist Fault
Localization, Proceedings of the 24th ACM/IEEEInternational Conference on Software Engineering,

行順序は，毎回入れ替わることがある．

• タイマによって起動される処理の実行回数およびタイミング．実行トレースを取得する処理自体にも時間がかかるので，処理のタイムアウトの発生にも影響することがある．

• ファイルやデータベースなどの外部データ．ファ
イルに格納されているデータや，計算機の日付情報などの変化が，処理に影響を与えることがある．
動的プログラムスライシングのように，ただ 1 つの実行トレースを解析する手法では，同じ対象ソフ
トウェアを同じように実行したつもりでも，上記のような要因から異なる実行トレースが生成され，適用結果が異なったものになる可能性がある．そのため，評価実験を計画する際には，注意が必要である．プ
ログラムの実行をできるだけ再現する方法について
は，デバッグ技法として Andreas Zeller が整理している [33]．なお，コードカバレッジの計算や，統計的
デバッギングのように，複数回実行した結果を集計する手法では，実行に再現性がないことは問題にはなら
ない．

6 まとめ
動的解析は，プログラムの実行を解析し，プログ
ラムの正確な振舞いを開発者に提示する技術である．
本稿ではテストとデバッグに役立つ代表的な技術を紹介したが，プログラム理解を目的とした研究も数多く実施されており，研究動向については Cornelissen
らのサーベイ論文 [7] にまとめられている．
本稿で紹介したような動的解析の基本的な手法は，簡明なアイディアに基づいており，既存ツールを使いこなすことができれば，自分で開発することもそれほど難しくはない．本稿によって動的解析に興味を持った場合は，様々な研究論文を読み進めるとともに，簡単な解析手法を手元の環境で試作し，様々なプログラ

Vol. 16 No. 5
May 2002, pp. 467–477.
[14] Joshi, S. and Orso, A.: SCARPE: A Techniqueand Tool for Selective Capture and Replay of Program Executions, Proceedings of the 23rd IEEE International Conference on Software Maintenance,
October 2007, pp. 234–243.
[15] Ko, A. J. and Myers, B. A.: Debugging Reinvented: Asking and Answering Why and Why Not
Questions about Program Behavior, Proceedings ofthe 30th ACM/IEEE International Conference on
Software Engineering, May 2008, pp. 301–310.
[16] Lewis, B.: Debugging Backwards in Time, Proceedings of the 5th International Workshop on Automated Debugging, September 2003.
[17] Lo, D. and Maoz, S.:
Mining ScenarioBased Triggers and Eﬀects, Proceedings of the
23rd IEEE/ACM International Conference on Automated Software Engineering, September 2008,
pp. 109–118.
[18] Lo, D., Ramalingam, G., Ranganath, V. P., andVaswani, K.: Mining Quantiﬁed Temporal Rules:
Formalism, Algorithms, and Evaluation, Proceedings of the 16th Working Conference on Reverse
Engineering, October 2009, pp. 62–71.
[19] Ngo, M. N. and Tan, H. B. K.: Detecting Large
Number of Infeasible Paths through Recognizing
Their Patterns, Proceedings of the the 6th Joint
Meeting of the 11th European Software Engineering
Conference and the 15th ACM SIGSOFT Symposium on the Foundations of Software Engineering,
September 2007, pp. 215–224.
[20] Park, S., Vuduc, R. W., and Harrold, M. J.: Falcon: Fault Localization in Concurrent Programs,
Proceedings of the 32nd ACM/IEEE International
Conference on Software Engineering, May 2010,
pp. 245–254.
[21] Pauw, W. D., Jensen, E., Mitchell, N., Sevitsky, G., Vlissides, J. M., and Yang, J.: Visualizing
the Execution of Java Programs, Revised Lectures
on Software Visualization, International Seminar,
2001, pp. 151–162.
[22] Prasad, C. K., Ramchandani, R., Rao, G., andLevesque, K.: Creating a Debugging and Proﬁling
Agent with JVMTI, June 2004.
[23] Quante, J. and Koschke, R.: Dynamic Object
Process Graphs, Journal of Systems and Software,Vol. 81(2008), pp. 481–501.
[24] Reiss, S. P.: Dynamic Detection and Visualization of Software Phases, Proceedings of the International Workshop on Dynamic Analysis, 2005,
pp. 1–6.
[25] 櫻井孝平, 増原英彦, 古宮誠一: Traceglasses: 欠陥の効率よい発見手法を実現するトレースに基づくデバッ
ガ, 情報処理学会論文誌 プログラミング (PRO), Vol. 3,

1999

91

No. 3(2010), pp. 1–17.
[26] Santelices, R. and Harrold, M. J.: Eﬃciently
Monitoring Data-ﬂow Test Coverage, Proceedings ofthe 32nd IEEE/ACM International Conference on
Automated Software Engineering, November 2007,
pp. 343–352.
[27] 下村隆夫: プログラムスライシング技術と応用, 共
立出版, July 1995.
[28] Sundaresan, V., Hendren, L., and Razaﬁmahefa, C.: Practical Virtual Method Call Resolution
for Java, Proceedings of the 2000 ACM SIGPLAN
Conference on Object-Oriented Programming Systems, Languages, and Applications, October 2000,
pp. 264–280.
[29] Systa, T.: Understanding the Behavior of Java
Programs, Proceedings of the 7th Working Conference on Reverse Engineering, November 2000,
pp. 214–223.
[30] Tallam, S., Tian, C., and Gupta, R.: Dynamic
Slicing of Multithreaded Programs for Race Detection, Proceedings of the 24th IEEE International
Conference on Software Maintenance, September
2008, pp. 97–106.
[31] Wang, X., Cheung, S. C., Chan, W. K., andZhang, Z.: Taming Coincidental Correctness: Coverage Reﬁnement with Context Patterns to Improve Fault Localization, Proceedings of the 31st
IEEE/ACM International Conference on Software
Engineering, May 2009, pp. 45–55.
[32] Watanabe, Y., Ishio, T., and Inoue, K.: Featurelevel Phase Detection for Execution Trace Using
Object Cache, Proceedings of the International
Workshop on Dynamic Analysis, 2008, pp. 8–14.
[33] Zeller, A.: Why Programs Fail: a Guide to
Systematic Debugging, Morgan Kaufmann, October
2005.
[34] Zhang, X., Tallam, S., and Gupta, R.: Dynamic
Slicing Long Running Programs Through Execution
Fast Forwarding, Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations ofSoftware Engineering, November 2006, pp. 81–91.
[35] Zhang, Z., Chan, W. K., Tse, T. H., Jiang,B., and Wang, X.: Capturing Propagation of Infected Program States, Proceedings of the 7th Joint
Meeting of the 12th European Software Engineering
Conference and the 17th ACM SIGSOFT Symposium on the Foundations of Software Engineering,
August 2009, pp. 43–52.
[36] Zheng, A. X., Jordan, M. I., Liblit, B., andAiken, A.: Statistical Debugging of Sampled Programs, Advances in Neural Information Processing
Systems 16, Thrun, S., Saul, L., and Schölkopf,
B.(eds.), MIT Press, Cambridge, MA, June 2004.