序論

現代社会では生活のすみずみにまで計算機が普及しているため、バグは社会的に大きな影響を及ぼすこととなり、デバッグを確実に行うことは極めて重要である。

デバッグ工程での労力のほとんどは、個別のバグを修正するデバッグ作業に割かれるが、デバッグ作業における大きな問題は、この作業がその場限りの、1回だけのものだということである。このため、現在のデバッグ作業には2つの欠点がある。第一は、その場限りの作業であるため、デバッグのノウハウを体系立てて整理し、他人に伝えることができないこと。第二は、ケースバイケースで対処するため、自動化の余地がないこと。

一方で、プログラマはデバッグ作業の中にある種のパターンが存在することを、経験的に知っている。このような典型的な作業はデバッグにおける戦術であり、デバッグパターンと呼ぶことができる。

デバッグパターンを定義するため、デバッグ作業の中のバグの原因を発見する手続きを説明するものとして「仮説検証ループ」を提案し、その中の「検証方法の選択」と「検証の実施」に内在する本質的な手続きをデバッグパターンと呼ぶことにする。また、このループによって、デバッグの自動化に関連する他のいくつかの研究もデバッグパターンの一種として解釈できる。

以上より、本論文の目的は、デバッグにおけるプログラマの労力を軽減し、デバッグ工程にかかる時間を短縮するために、デバッグ作業中にプログラマが行う典型的な作業を自動化するための基礎技術として、プログラム実行点の概念を用い、いくつかのデバッグパターンの提案と自動化を行うことである。

プログラム実行点

プログラム実行点とは、プログラマが持っている、プログラムの実行がどこまで進んだかという実行状態のイメージを指しており、通常、デバッグ中のプログラマはこれを意識している。そこで、本研究では実行点を行番号とタイムスタンプの組として表現することを提案する。タイムスタンプとは、制御が上向きにジャンプするときにインクリメントされるカウンタであり、デバッギ（デバッグ対象プログラム）の変数として追加される。

以下のようなコードでループ本体（2行目）が3回実行される場合、本体の1回目の実行点は (test.c:2, 0) であり、2回目は (test.c:2, 1)、3回目は (test.c:2, 2) となる。test.c　(1) while(i ＜ a){　(2) i += b; (3) }

一般には、このループ構造に到達したときにタイムスタンプの値がいくつになっているかは分からないので、プログラマが直接指定することはできない。タイムスタンプの値を含む実行点の情報は、デバッグ中に行った以前の実行で取得済みでなければならない。この意味で、デバッギは再現性を持つという前提がある。デバッガを用いたデバッグでは、デバッギの再実行を繰り返しながらバグを追及していくことが基本であり、これをcyclic debuggingと呼ぶ。cyclic debuggingではデバッギの再現性は通常の前提である。

タイムスタンプ機構の実装 − C

タイムスタンプ更新機構をCのデバッギに自動的に組み込む方法について述べる。タイムスタンプはデバッギ中に大域変数timestampとして導入し、これをインクリメントするコード（タイムスタンプ更新コード）をデバッギ中の制御ジャンプ命令の直前に追加する。コードの追加はコンパイラの中間コードレベルで行い、実装の対象はGCC-2.95.2とした。

タイムスタンプ更新コードの追加は構文解析器のアクションで処理するため、追加の場所はソースコードの構造と対応づけて考え、以下の4種類の場所で追加する。

関数呼び出しの入口・出口return文ループの繰り返しgoto文によるジャンプ

タイムスタンプ更新コードにより、実行速度の低下とコードサイズの増大が発生する。これらのオーバヘッドを、sedとawkをベンチマークとして計測したところ、実行速度は約1.6倍の速度低下、ファイルサイズはおよそ1.1倍から1.4倍の増大であった。これらは実用上、問題とはならないオーバヘッドであるといえる。

タイムスタンプ機構の実装 − Java

Javaプログラムに対してはコンパイラが生成したクラスファイル（バイトコード）を変換することでコードの追加を実現した。独立したTimestampクラスを用意し、タイムスタンプ機構に必要な要素はそのクラスのstaticメンバーとした。タイムスタンプ更新の対象となるバイトコードは、以下の通りである。

[メソッド呼び出しの入口と出口]

入口に対応するバイトコードはないが、メソッド本体の先頭がこれにあたる。出口にはreturnバイトコード群が該当。

[条件分岐]

バイトコードの仕様として上向きのジャンプが起こりうるので、関係する16命令を対象に含める。

[無条件ジャンプ]

gotoとgoto_wが対象となる。

[その他の制御ジャンプ]

jsrとret、jsr_wが該当。

[例外]

catchブロックの先頭に挿入する。

クラスファイルを変換するプログラムはバイトコード解析ツールBCELを用いてJavaで記述した。プログラマは、タイムスタンプによる実行制御の対象としたいコードを含むクラスファイルを、事前にこの変換プログラムで変換しておく。

タイムスタンプ機構を組み込んだJavaプログラムのオーバヘッドを、SPEC JVM98のベンチマークプログラムを用いて計測した。実行速度は約1.3倍、ファイルサイズはおよそ1.2から1.3倍となった。Cの場合と同様、実用上の問題はないと考えられる。

実行点の応用 − デバッグパターンの例

実行点を用いることで、デバッグ作業中にプログラマが手動で行っていた作業を自動化することができる。これは前述のデバッグパターンの自動化であり、ここでは3つのパターンを紹介する。これらは2種類に大別できる。1つは人間が手動で行っていた手続きを自動化するような応用であり、もう1つは、それをさらに進めて、手動では到底できないような手続きを行うものである。これらはひどく乱暴な手法に見えるかも知れないが、近年の高速な計算機を利用することで、人間が手動で行うよりもずっと効率良くデバッグを行うための有用な手法である。

第一は「実行点の印づけ」である。大規模なプログラムの中をデバッガで移動していると、うっかりコマンドを間違って、あるいはバグの原因となる場所の推測を誤っていて、問題の場所を通り過ぎてしまうことがある。このようなときには、そこへ至る経路を覚えておくか書き留めるかしておき、デバッギを先頭から再実行してその経路を手動で追いかけなくてはならない。こうした面倒を避けるためには、デバッギの振舞が「ここまでは正しい」というときにその実行点を記録しておく（印づけをする）ことが有効である。

第二は「逆向きウォッチポイント」である。Cプログラムにおける配列のバッファオーバランや、マルチスレッドプログラムにおける共有変数への誤った代入によるバグを追及するには、変数への書き込みを捕捉するウォッチポイントを用いる。一般には変数は何度も書き換えられるものであり、その度にトラップが発生して、プログラマはそれぞれの書き込みで何が起こったかを検査しなくてはならない。しかしながら、多くの場合、ある問題を引き起こした書き込みというのはそのバグの影響が現れた時点から時間的に一番近いものが原因になっていて、実際に我々はそれを探すことを手作業で行っている。これを自動化する機構が逆向きウォッチポイントである。

第三は「タイムスタンプを用いた実行系列中の2分探索」である。ここまでは、これまでプログラマが手動で行ってきた手続きを自動化するというものであったが、これは手動では到底できないような手続きを実行する例である。デバッギは正しく動作していないが、原因について全く手がかりがないというとき、プログラマはデバッギの実行をある程度まで進めて不正になっているかどうかを調べる。もし正しければさらに実行を進め、そこでまた調べる。正しくなければデバッギの実行を最初からやり直して少し手前で停止させ、そこでまた調べる、ということを繰り返す。これを自動的に行うパターンがこの2分探索である。

マルチスレッドプログラム

これまでは再現性を持つデバッギに限って議論してきたが、再現性を持たないデバッギに対しても、適切な記録、再生機構によって再現性を持たせることで前述のパターンを適用することができる。マルチスレッドプログラムの場合には、スレッド切替のタイミングを記録して再生すれば良い。ユニプロセッサ上でのJavaのマルチスレッドプログラムを対象として、JPDAを用いたスレッド切替の記録、再生機構を実装し、オーバヘッドを計測した。

結論

本研究は誤りを修正するというデバッグ作業の過程に注目し、熟練のプログラマが行うデバッグ過程を自動化してデバッグ効率を向上させるという直接的な効果を得た。また、今までのデバッグ作業はその場限りのものであったが、デバッグ作業の再利用も可能となった。のみならず、熟練プログラマのデバッグ技術を抽出することで、知識や経験を共有する基盤を提供することに成功したと言える。

設計におけるデザインパターンが今日広くプログラマに利用されているように、デバッグパターンも幅広いプログラマが利用可能なものである。職業プログラマは作業時間の短縮によって、次々と頭に浮かぶ様々な仮説を検証する機会を得る。日曜プログラマとでも呼べる人々は、より上級者が使う高度なデバッグパターンを習得できる。入門教育を受けているプログラマは、デバッガの繁雑な操作に振り回されることなくデバッグ作業の本質を学びとることが可能となる。

本論文は「プログラム実行点の概念に基づくデバッグパターンの抽出と自動化」と題し、これまでほぼ完全に手動で行われてきたプログラムのデバッグ作業について分析を行い、その一部を抽出して自動化するための研究をまとめたもので、以下の9章からなる。

第1章「背景」では、研究の背景、研究全体の概要と論文の構成について述べている。

第2章「デバッグパターン」では、プログラマが行うデバッグ作業についてその思考プロセスを分析して新しい枠組を提示し、作業の一部に再利用の可能性と自動化の余地が存在することを述べ、デバッグパターンの定義を与えている。デバッグパターンの抽出と自動化によって、熟練プログラマの経験に基づいた高度なデバッグ手法がプログラマ間で共有できることと、作業時間の短縮が実現されることを述べている。また、従来の研究成果のいくつかがその枠組で説明できることを示している。

第3章「関数単位疑似逆実行」では、研究全体の中で予備実験としての色彩を持つ関数単位疑似逆実行の実装に関する知見について述べている。逆実行は従来広く研究されてきた分野であるが、そのオーバヘッドの大きさから実用に供されてこなかった。本論文ではこれを、典型的な実行制御であるデバッグパターンの1つと位置付けている。本章では、プログラムの再現性を仮定し、実行制御における制御の移動先を関数呼び出しに限定した先行研究について紹介した上で、対象プログラムの変換を利用することで、実用レベルのオーバヘッドで同機能が提供されることを示している。また、その結果をもって実行制御の自動化の有効性を述べ、関数呼び出しに限らない、より一般的な実行制御の基盤が必要であると論じている。

第4章「プログラム実行点」では、前章の論点を受けて、一般的な実行制御の基盤として実行点という概念の利用を提案している。この概念はデバッグ中のプログラマの多くが、プログラムの実行進捗度を把握するために用いているイメージである。本章では実行点の具体的な表現方法として4種類を挙げ、その中で行番号とタイムスタンプを用いた表現が適当であるとし、その手法について述べている。

第5章「C及びJavaへの実装」では、前章で提案した実行点の具体的表現をポータブルに実現するため、第3章で用いたプログラム変換による手法を提案し、実装している。Cプログラムに対してはコンパイラの中間言語レベルでの変換を利用し、Javaプログラムに対してはバイトコードレベルでの変換を用いている。また、それぞれの実装について実行速度とファイルサイズのオーバヘッドを計測し、実用的なレベルであることを示している。

第6章「実行点の応用：デバッグパターンの例」では、デバッグ作業における典型的な3種類の処理を示し、利用例とともに実行点を用いた実装方法について述べている。

第7章「マルチスレッドプログラムへの応用」では、再現性のないプログラムの例としてJavaのマルチスレッドプログラムを挙げ、スレッド切替のタイミングを記録、再生することで前章のデバッグパターンが適用可能であると論じている。また、Javaの持つデバッガインタフェースを用いて記録と再生が制限つきながらポータブルに実現できることを示し、デバッグパターンの応用範囲が十分広いことを述べている。

第8章「各種の議論」では、第4章で示した実行点の表現方法について、他の3種類の表現方法との相違を論じ、行番号とタイムスタンプによる表現が適切であることを示している。また、自動デバッグやプログラム変換に関する先行研究との比較を行い、本研究の位置付けを述べている。

第9章「結論」では、本研究の成果をまとめ、その意義と今後の展望を述べている。

以上これを要するに、本論文ではソフトウェアの信頼性向上のために重要となるデバッグについて、これまでのようなプログラマ個人の能力のみに依存した方法ではなく、プログラマ間でその知識と経験を共有し、より効率的なデバッグを行うための方法を提案し、実用的なオーバヘッドでの実装を通して有効性を証明しており、その成果は情報工学上貢献するところが少なくない。

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる。