プログラム実行点の概念に基づくデバッグパターンの抽出と自動化

丸山 一貴



目次
第章

背景
バグの影響と原因                             
エンバグの防止                              
テストとデバッグ                             
デバッグ工程の改善                           
目的                                    
本論文の構成                               



第  章 デバッグパターン
デバッグ作業の分析                           デバッグ作業の概要                       
仮説検証ループ                          
デバッギの内部状態の取得                        


 デバッグ                         
デバッガの機能                          ケーススタデ ィ                              
ケース ：出力データの異常                   ケース ：配列のオーバラン                   


ケース ：マルチスレッドプログラム              まとめ                               デバッグパターン                             

実行制御の困難                          
パターンの存在                          デバッグパターンの定義                     パターンとしての関連研究                        
逆実行                               
イベント駆動型実行制御                     












第章




                        

























関数単位疑似逆実行

疑似逆実行                                 






従来手法                                  
新手法                                   
フック関数呼び出しの挿入                    


ユーザインタフェース                      
処理時間計測                           








第  章 プログラム実行点

実行点の概念                                
実行点の表現形式                              
動的ブレークポイント                           
タイムスタンプのインクリメント                     
第  章  および 
への実装



 への実装                                 

更新機構挿入のレベル                       タイムスタンプ更新コード                      の変更点
                         オーバヘッド                            


動的ブレークポイントの実装                    への実装                               

更新機構挿入のレベル                     


タイムスタンプ更新対象のバイトコード             タイムスタンプ更新コード                     


クラスファイル変換プログラム                  オーバヘッド                            
第章 実行点の応用：デバッグパターンの実装
実行点の印づけ                               
逆向きウォッチポイント                          
利用例                                
逆向きウォッチポイントの実装                  


逆向きウォッチポイントの処理時間                
タイムスタンプを用いた実行系列中の  分探索               分法のアルゴ リズム                                           分法と   との比較

 分法の条件の要件                        


第  章 マルチスレッドプログラムへの応用

非決定性の除去                              スレッド 切替の記録                           








スレッド の識別                          
ログの形式                            タイムスタンプ更新の排他制御                 スレッド 切替の再生                             による制約                         
デバッギ                              
オーバヘッド                               
まとめ                                   







第











各種の議論

実行点の表現形式                              
逆実行                                    
状態保存方式                            疑似逆実行方式                          
イベント駆動型実行制御                         





章





第





! "#!$ !                                                   %$$!!$#

アスペクト指向プログラミング章

結論
本研究の意義                               
展望                                                                                       





参考文献



謝辞



発表文献一覧





第章

背景

 バグの影響と原因
現状では、製品としてのソフトウェアの中で、バグを完全に追放したものはほとんど 存在しない。現代社会では生活のすみずみにまで計算機が普及しているため、バグは社会的に大きな影響を及ぼすこととなる。
例えば 、携帯電話端末に搭載された  &' のバグが発覚して端末の無償交換を行うことになれば 、これに要する直接的な費用だけでなく、企業イメージをも傷つけて大きな損失を招く。また、デーモン・プロセスのバッファがオーバランするよ
うなバグは結果として % のセキュリティホールとなり、これを悪用するワームの蔓延という事態を引き起こす。
家電のネットワークへの接続も進められており、今後もソフトウェアの利用範囲の拡大は避けられない。また、ソフトウェアそのものの複雑化も一層進行すると考えられる。これらより、バグはより増加し 、その影響は一層深刻になる。
そもそもバグが混入する（エンバグと呼ぶ）のは 、いつであろうか。ソフトウェアの開発工程は概ね  つの工程に分けられる。要求定義、設計、コーデ ィング、テスト、デバッグである。この中でエンバグが起こるのは要求定義、設計、コーデ ィングの各工程である 。
ここで、バグを駆逐するために  つの方針が考えられる。 つはエンバグを防止すること、もう  つはデバッグを確実にすることである。エンバグの防止を徹底す
ればデバッグは不要になると主張する向きもある ('$ ) が 、現実的とは言いがたい。従って、ソフトウェア開発ではこれら  つを共に実施することが重要となる。以下、第  節と第  節でそれぞれについて述べる。

 エンバグの防止
本節では、デバッグ工程よりも上流の工程でバグの混入を防ぐための、代表的な方法について述べる。
*!+ +,-#("$ ) はプログラムの仕様を記述する段階から自然言語を排し 、形式的言語で記述して曖昧さをなくすという手法である。この方法はパリの地下鉄 実際には、デバッグ工程におけるコーディング作業でもエンバグは発生するが 、ここでは触れないこととする。



第章

背景

で採用されている .' や、"/' と %0!- が開発した " のように一定の成果を挙げている (1 )。しかし既に市場で流通し 、バージョンアップ等の保守段階に達している多くのプログラムに適用することは難しい。
デザインパターン (2& ) は、オブジェクト指向プログラミングにおけるクラス階層の典型的な設計例を、パターンとして列挙している。プログラマは自分のソフトウェアの各コンポーネントを該当するパターンに当てはめることで、良い設計ための指針を得ることができる。良い設計の結果として、プログラマはコーデ ィン
グ工程で必要以上に複雑なコード を書くことがなくなり、間接的にコーデ ィング工程でのエンバグを抑止する効果があると考えられる。
オブジェクト指向言語はデータのカプセル化によって、オブジェクト内部の変数を外部からアクセスできないようにできる。また 、.3 の 4!5$- や 4#5$- のように ##! を用いてデータの妥当性をチェックする機能を持った言語もある。こうした機能を使えばバグの原因となった場所を特定するのに有効であるが 、##! を書く労力はプログラマが担わなくてはならないし 、##! はメ
ソッド 呼び出しのたびに評価されるのでオーバヘッド は大きいと考えられる。
.0!+ !!++（ 6 ）(/$) はソフトウェアを細かいサイクルで段階的に開発することで、工期の短縮とともに品質の向上を目指しており、そのために開発に関わる者が取り組むべき手順や姿勢について論じている。6 では開発計画や設計から具体的なコーデ ィングの段階まで様々な提言を行っているが 、デバッグに関するものとして重視すべきは  つある。 つはテストであり、プログラマが書く
テストは単体テストと呼ばれる。プログラマはメソッド の機能を確認するためのテストや見つかった問題を独立させるためのテストなど 、単体テストを書いて自分のコード の断片が正しいことを確認する。コーデ ィングに先だってテストを書くこともある。もう  つはペアプログラミングである。 人がコーデ ィングを担当し 、もう  人はそれを見ながらコーデ ィングの検証などを行って助言をする。これはコーディングと同時にコードレビューを行っていると考えることができる。6 の方法論
はソフトウェア開発の多くの現場で効果を発揮し 、バグを減らすことに貢献する。
これらの手法はいずれも一定の成果を挙げるが 、 つの手法だけでバグを駆逐することはできず、組み合わせて用いることが重要である。それでも網をかいくぐ る
バグはあり、それらはデバッグ工程で取り除かなくてはならない。

 テスト とデバッグ
バグ駆逐の  つの方法のうち、前節ではエンバグの防止について述べた。本節では確実なデバッグについて述べる。
要求定義、設計、コーデ ィングの各工程での努力にも関わらずエンバグが行われた場合、テスト工程でバグを発見し 、デバッグ工程で取り除かなければならない。
テストとデバッグの重要性は古くから認識されており、テスト・デバッグ工程はソ

デバッグ工程の改善

フトウェア開発において投入すべきリソース（ マンパワー、時間、コストなど ）の
7を占めていると言われる ("#, ) 。
コーデ ィング工程の成果物である未テストのソフトウェアは、テスト工程で仕様を満たすかど うかの検査を受ける。テストで発覚したバグはデバッグ工程へ送られ、駆逐される。しかし一般には、テストで全てのバグを発見するのは困難である。結果として、出荷製品にはバグが含まれたままとなり、ユーザからの報告によって発覚することとなる。
一方で、テストで発見されたが修正されなかったバグというのも存在する。出荷品質を高く保つため、本来はテストで発見されたバグは全て修正した上で出荷されるべきだが 、経営的判断によってデバッグが終了する前に出荷される場合がこれにあたる。
市場に流通しているソフトウェアの多くは、このような既知のバグ（ 存在することは分かっているが 、修正が完了していないバグ ）を抱えている。例えば '$!#の "! .04!! にはユーザから指摘されているバグで修正されていないものが存在する (8,9 :)。"! .04!! はこれまでのセキュリティホールとユーザの多さとから多数の情報が集められているが 、他の製品版ソフトウェアも同様の状況にあると考えられる。無料で入手できる '; や   < もバグのデータベースを公開 (';9 ) しており、発見されていてもなお修正されていないバグは多数存在する。これらの事実はテスト工程におけるバグ発見の困難とは別に、デバッ
グ工程におけるバグ修正も困難であることを示している。
デバッグ工程の時間を短縮してソフトウェア開発の効率を高めるために 、また、
ソフトウェアの信頼性をより高めるために、デバッグ工程のプログラマの作業を支援することが不可欠である。次節ではデバッグ工程改善の概要について述べる。

 デバッグ工程の改善
デバッグ工程全体は、個別のバグを修正するデバッグ作業と、複数のデバッグ作
業全体を管理する工程管理との、 つに分かれる。
一方のデバッグ作業をモデル化すると 、 つの入力から  段階の出力を生成するものと考えることができる。入力は 、バグの結果として現れるエラーの症状（ +# ）である。これにはエラーを発現させるための条件も含まれる。第 段階の出力はそのエラーが発現する経緯であり、第  段階の出力はエラーの根源を除去したソフトウェアである。
もう一方の工程管理については 、前述のバグデータベース (';9 ) のような追跡システムが利用されている。火星探査機 '!# ,=-! は火星に着陸後、 日に  回、コンピュータがリセットしてしまうという現象を起こした (< )。このバ
グは発射前のテストでも発生していたにも関わらず、開発陣は見落としてしまったという。こうした問題は追跡システムを適切に利用することで解決できる。

第章



背景

しかし 、個別のバグを解消するデバッグ作業には大きな問題が残されている。それは、この作業がその場限りの、 回だけのものだということである。デバッグ作
業はバグ固有の現象に基づいて行うので、特定の状況下でしか役に立たないと考えられがちであり、デバッグ作業は熟練が必要な職人芸であると思われてきた。このため、現在のデバッグ作業には以下のような欠点がある。

¯ その場限りの作業であるため、デバッグ作業の戦略と戦術（デバッグのノウハウ）を体系立てて整理し 、他人に伝えることができない。
¯ ケースバイケースで対処するため、自動化の余地がない。
一方で 、プログラマはデバッグ作業の中にある種のパターンが存在することを、経験的に知っている。例えば 、デバッグ中のプログラマは以下のようなことを呟くことがある。
「このようなエラーの症状は、あのようなバグに起因していることが多い。となれば 、以前も行ったあの方法でそれを確認し 、修正すべきコード を見つけ出せるはずだ。」
このプログラマの独り言の中で、エラーの症状から原因となるバグを推測している部分（前半の一文）はデバッグ作業の第  段階の出力（バグ発現の経緯）を生み出しており、人間の知性が必要となる。しかし 、その経緯を確かめて修正対象のコー
ド を見つけ出す部分（ 後半の一文）は典型的な作業と考えられ 、再利用と自動化の余地があるといえる。このような典型的な作業はデバッグにおける戦術であり、デバッグパターンと呼ぶことができる。

 目的デバッグにおけるプログラマの労力を軽減し 、デバッグ工程にかかる時間を短縮するために、デバッグ作業中にプログラマが行う典型的な作業を自動化するための基礎技術として、プログラム実行点の概念を用い、いくつかのデバッグパターンの提案と自動化を行うことを本研究の目的とする。
ここでいうプログラム実行点とは、プログラマが持っている、プログラムの実行がどこまで進んだかという実行状態のイメージを指している。詳細は第  章で述べる。

 本論文の構成
第  章では、デバッグ作業においてバグの原因を発見するための手続きを、「仮説
検証ループ 」として説明できることを述べる。デバッグのいくつかのケーススタディ
を通じて、プログラマが行っている思考プロセスとの対応を示し 、デバッグパター
ンの正確な定義を示す。



本論文の構成

第  章では、本研究の予備研究として位置付けられる、関数単位疑似逆実行に関する研究について述べる。
第  章では、本研究で扱う自動化のための基礎技術である、実行点（ 4# ）という概念について述べる。また、その表現方式を比較し 、本研究で採用するタイム
スタンプ方式について説明する。
第  章では、実行点のために必要となるタイムスタンプ機構を  と  のプログ
ラムに自動的に組み込む手法について述べる。また、実行速度とファイルサイズのオーバヘッド を示す。
第  章では、 種類のデバッグパターンについて紹介し 、実行点を用いてど のよ
うに実現するかを述べる。
第 章では、再現性のないデバッギとして  のマルチスレッドプログラムを取り上げ、デバッグパターンを適用するために必要なスレッド 切替の記録、再生の機構について述べ、オーバヘッド を示す。
第 章では、実行点のいくつかの表現形式の比較と、関連研究との比較を行う。
第 章では、本研究の結論を述べ、意義と展望について述べる。

第  章 デバッグパターン
本章では 、デバッグ作業の中のバグの原因を発見する手続きを「仮説検証ループ 」
として説明できることを述べる。デバッグのいくつかのケーススタデ ィを通じて、プログラマが行っている思考プロセスを明らかにし 、デバッグパターンの定義を与える。

 デバッグ作業の分析
バグは、端的にはコーデ ィングの誤りである。その誤りが変数の値の誤りとして伝搬してゆき、結果として、どこかの段階でエラーの症状を発現する。デバッグ作
業はバグの結果から原因を見つけ出すという時間に逆行する行為であり、本質的に困難である。

 デバッグ作業の概要
バグのほとんどはプログラマが論理的に正しくないコード を書いてしまったことに起因しているので、自分の書いた全てのコード を精読して論理的に正しいかど う
かを検証すれば良い。実際、あるバグを取り除く最後の段階では、該当箇所のコード を見て検証することになる。しかしながら大規模なプログラムでは、たとえそれが自分で書いたものであっても、最初からこの方法を採ることは難しい。従って、見るべき範囲を絞り込むことが必要になる。
範囲の絞り込みのため、プログラマは現れたバグの結果を見てその原因を推測する。例えば 、表示されるはずの文字が  行分足りないといったような、原因を推測しやすい結果が現れるバグでは、経験豊富なプログラマにとって推測は比較的容易である。そうでないバグでは、コード 中に印字命令を挿入したりデバッガを用いたりして、実行時のデバッグ対象プログラム（ 以下、デバッギと呼ぶ）の内部状態を検査することで、推測のための情報を手に入れる。
入手した情報を元にコード の該当箇所を調べると、エラー症状の直接的な原因を発見することができる。例えば 、表示が  行足りないのは、ループ継続の条件部で呼び出される関数の返り値がおかしいからだ、といった具合である（ 図  ）。次のステップとして、プログラマはその関数のコード を調べる。このように、結果から原因を推測することの繰り返しによって、真のバグを見つけ出すことができる。

第  章 デバッグパターン    


図 > エラー症状の直接的な原因の例
原因の推測では 、プログラマはエラー発現の経緯に関して仮説を設定している。
そしてコード の該当箇所を見るなどにより、その仮説を検証する。よって、真のバグを見つけ出すための繰り返しを、「仮説検証ループ 」と呼ぶことにする。



仮説検証ループはデバッギングを科学的手法と対比することで、以下のような  段階の手順が望ましいとしている ('$ )。
'$



エラーを安定させる（ 確実に再現させる）。



エラーの原因を見つける。



エラーを修正する。



修正を検査する。



同じようなエラーを探す。

本研究では第  の「エラー原因の発見」に注目しており、前述の仮説検証ループはここに含まれている。本論文の残りの部分では、この第  を指してデバッグ作業ということにする。
遠藤は 、この第  の段階におけるプログラマの行動を、 段階の仮説検証ループとして示している (.- )。


実験を繰り返してデータを採る。



エラー発現の経緯を推測し 、仮説とする。



仮説の検証方法を考案。



検証を行う。



デバッグ作業の分析
検証の結果、仮説が棄却された場合は  段階目に戻る。新たな仮説の設定が困
難な場合は  段階目に戻る。

これはデバッグ作業の分析として非常に有力である。しかし 、後述するケーススタ
デ ィで述べるように、現実のデバッグ作業では仮説検証ループの中に、別の、さらに細かいループが存在する。
よって、本論文ではデバッグ作業を以下の  つの段階に分類し 、以降はこれを仮説検証ループと呼ぶ。
第  段階 仮説設定のための情報収集を行う。ここには、エラー発現の条件を特定する作業（ 入力データの変化など ）や、プログラムのコード の観察も含まれる。
第  段階 収集した情報に基づいてエラー発現の経緯を推測し 、仮説を設定する。
第  段階 検証方法を考案する。
第  段階 検証を実施する。検証が困難な場合は第  段階へ戻り、別の検証方法を考案する。
第  段階 修正すべきコード を確認した場合は終了。そうでない場合は新たな仮説設定のため、第  段階に戻る。ここには、仮説が棄却された場合だけでなく、仮説が立証された場合の新たな仮説設定も含まれる。
この分類では、仮説検証ループは  つのループを持っている。 つは第 〜 段階のループであり、仮説を設定して検証し 、次の仮説を設定するというループである。
もう  つは第 〜 段階のループであり、ある仮説の検証方法を決定して検証を実施したものの、検証に失敗した場合には別の検証方法に切替えて、同一の仮説の検証を続行する、という場合に相当する。
遠藤の分類との相違点は以下の通りである。

¯ 遠藤の分類では、仮説が棄却された場合（エラー発現の経緯を正しく見抜けなかった場合）にループを繰り返すことになっている。本論文の分類では、仮説が立証された場合にも第 〜 段階のループを繰り返す。これは '$('$ )の言う、「仮説の洗練」にあたる。これは以下のような考え方のことである。
最初に立てる仮説は 、エラー症状の全てを説明できなくてもよい。一部の症状を説明することができたなら、その他の症状をも説明できるように、仮説を段階的に洗練させていけばよい。
この考え方を採り入れることで、本論文の分類はデバッグ作業をより包括的に説明することに成功した。

第  章 デバッグパターン¯ 本論文の分類では、仮説は変えずに検証だけをやり直す、第 〜 段階のループが存在する。実際のデバッグ作業では、検証のために選択した方法が不十分であることに気づいたり、あるいは余りにも時間的コストが高いことに気づいたりすることで 、検証方法の変更を余儀なくされることがある。この小さなループはこれを反映するためのものである。
本章の残りの部分では、この仮説検証ループの妥当性を示すために実際のデバッ
グ作業のケーススタデ ィを見ていき、最終的にデバッグパターンとその自動化の定義を与える。しかしその前に、第  段階と第  段階で必要となる、デバッギの内部状態の取得方法について述べておく。

 デバッギの内部状態の取得
実行時のデバッギの内部状態を取得する方法は、コード 中に印字命令を挿入する
方法（ 以下、 デバッグと呼ぶ）とデバッガを用いる方法とがある。

 デバッグ デバッグでは 、デバッギ中の必要な箇所に  における  のような、変数の値を表示する命令を追加しておく。これを再コンパイルして実行すれば 、デバッギがどこから期待通りに振舞わなくなっているかを調べることができる。
デバッグの経験が豊富なプログラマにとってはこれで十分な情報を取得できる場合も多い。しかし一般には、かなり単純で小規模なプログラムの、ごく簡単なバグを取る時にしか適用できない。大規模なプログラムや複雑なバグに対してこの方法を行うと、大量の  文を挿入して様々な変数の値を表示する必要が起こる上に、膨大な量の表示を解析しなくてはならない。

 デバッガの機能
デバッギの内部状態をより効率良く取得するため、デバッグを補助する専用のツー
ル 、デバッガが用いられる。デバッガは % とハード ウェアのサポートを利用して非常に豊富な機能を提供するが (1# ) 、主に利用されるのは以下のようなものである。括弧内に、代表的なデバッガである  /( ) での対応するコマンド 名を示す。

¯ デバッギの状態を検査するコマンド（ 状態検査コマンド ） 変数の値を表示（  ） 変数の値を変更（   ）ケーススタデ ィ¯ デバッギの実行を制御するコマンド（ 実行制御コマンド ） ステップ実行：実行をコード 行単位で進める（   、  ）
 ブレークポイント：特定のコード 行に制御が到達したらデバッギの実行を停止する（   ）

 ウォッチポ イント：特定の変数（ メモリ領域）にアクセスがあったらデバッギの実行を停止する（  ）デバッガを利用するプログラマは、これら状態検査コマンド と実行制御コマンドを相補的に利用してデバッグを行う。
デバッガによるデバッグ作業では、デバッギの再実行を繰り返して仮説検証ループを進めていく。これは $?$$ - と呼ばれる (1/-< )。

 ケーススタディ
本節では 、第  節で示した仮説検証ループの妥当性を示すため、 つの具体的なデバッグ作業を例に取り、仮説検証ループにどのように当てはめられるかを述べる。

 ケース ：出力データの異常
エラーの症状 デバッギはテキストデータを出力するプログラムであるが、出力デー
タが常に  行足りないというエラー症状を示していた。
仮説検証ループ（  回目） プログラマは  行足りないという実行結果から 、出力に関するループが  回足りないのではないかという疑いを持った。そこで、プログラマは  デバッグを実施して、その表示内容から出力ループの最後の  回が足りないことを確認した。
ここで 、プログラマは検証方法として  デバッグを選択したが 、他にもデバッガを用いて検証する方法がある（ 図  ）。例えば 、デバッガはブレークポイン
トのヒット回数を数えるので、その回数を利用する方法がある。また、デバッガの実行制御コマンド を利用して出力ループ終了直後に制御を移動し 、状態検査コマン
ド を利用して出力ループの制御変数の値を調べることで、出力ループの回数を確かめられるかもしれない。設定した仮説を検証する方法は複数存在し 、プログラマはその中で、そのケースに適していると考える方法を選択する。
仮説検証ループ（  回目） 次に調べなければならないのは、なぜ出力ループの最後の  回が足りないか、である。そこでプログラマは出力ループの継続条件部を調べ、以下のような記述を見つけた。

第  章 デバッグパターン

1. 情報収集

結果を見る（1行足りない）

2. 仮説設定

出力のループが1回足りない3. 検証方法考案

printfの挿入と出力のカウント

4. 検証実施

コード挿入、
再コンパイル、
出力の検査

デバッガの デバッガでループ
breakのhit count 終了直後へ行き、変数などを調べる

break,
ignore,cont, ...

break,
cont,print, ...

確かにループの回数が足りない

5. 結果判定

図 > ケース  の仮説検証ループ（  回目）

      
これは本来  であるべきところを  と書いてしまっているのではないかと考えた（ 図  の左側）。思考実験による検証を行った結果、エラー発現の経緯を合理的に説明できるので、これがバグであると確信し 、コード を修正して正しい出力となることを確かめ、デバッグを完了した。
このように、検証方法には思考実験のような、具体的な手作業が伴わないものも含める。
ここでは比較的単純なミスであったが 、もし出力ループの条件部が以下のようであったらど うであろうか。

  

この場合、関数  の返り値が正しいかど うかが問題となるので 、 回目の仮説検証ループの仮説は「関数の返り値が不正」ということになる（ 図  の右側）
。検証
方法として、 回目の仮説検証ループでも使用した  デバッグが利用可能である。しかし 、不幸にして関数  の    文が複雑な操作を行っているような場合には、 の出力を見ても仮説が検証できない可能性がある。その場合は 
デバッグによる仮説検証は断念し 、デバッガを用いた仮説検証方法を採用することになろう。このとき、第  段階で設定した仮説には何らの変更は生じていないが 、検証方法の変更によって第  段階と第  段階の間で小さいループが起こったと考えら
れる。



ケーススタデ ィ

1. 情報収集

ループ継続
条件部を見る

ループ継続
条件部を見る2. 仮説設定< と <= を間違っている関数の返り値がおかしい

3. 検証方法考案

思考実験

printfデバッグ

デバッガを
利用

4. 検証実施

思考実験を行う

printfを挿入

break if, etc.

5. 結果判定< と <= の書き間違いが原因だと確認

返り値の
異常を確認

図 > ケース  の仮説検証ループ（  回目）
考察 ケース  を通じて以下の  点を述べた。第  は、デバッグの基本である仮説
検証ループの繰り返しについて。第  は 、 つの仮説に対して複数の検証方法が考えられること。第  は 、プログラマはそれらの中から  つを選んでいること。第 は、選んだ検証方法が失敗した場合には別の検証方法を選択して、仮説の検証を継続できること。
ここでは仮説検証ループの例示のため、かなり細かく（まわりくど く）説明した。
実際にプログラマが行う手順では、仮説検証ループの  回目と  回目は明確には分かれていないかもしれない。また、誤りが自明な場合には仮説の検証を明確に行わないこともありうる。しかし 、その思考プロセスを詳細に分解すれば 、ここに示したような手続きを行っている。経験豊富なプログラマは自身の経験によって、途中を省略し 、より効率良くデバッグ作業を進めることができる。

 ケース ：配列のオーバラン
エラーの症状 デバッギは  で書かれており、最終的に  桁の自然数を出力するプ
ログラムとなるはずであった。しかし 、デバッギは信じられないほど 大きな数を出力した。
仮説検証ループ  回目の仮説検証ループでは 、計算のアルゴ リズムが間違っているという仮説に基づいて思考実験による検証を行ったが 、誤りは発見できなかった。
次に、アルゴ リズムをコードに移すに際して間違ったのではないかと疑った。そこ

第  章 デバッグパターン

1. 情報収集

この変数の値がおかしい2. 仮説設定

その値を代入した
operationが存在する

3. 検証方法考案

watchの利用

4. 検証実施

watch,
cont, ...

5. 結果判定

問題のoperationの発見

図 > ケース  の仮説検証ループ（  回目：〜 回目は省略）
で  回目の仮説検証ループでは、変数へ代入している箇所での右辺値がおかしい、という仮説を設定して  デバッグを試みたが、正常な値しか見つけられなかった。
そこで、 回目の仮説検証ループでは、他のオペレーションが意図しない代入を行っており、その結果として変数の値が上書きされるという仮説を設定した（ 図  ）。
検証方法として、デバッガのウォッチポイント（  / コマンドは  ）を利用する方法を考案し 、デバッガのコマンド を駆使して異常な値になる瞬間を見つけることができた。デバッギが文字列のために用意したバッファサイズを超える、長い文
字列を書き込んでしまったため、そのバッファの隣にあった変数が不幸にも上書きされてしまったことが分かった。バッファサイズを超える場合の例外処理を記述して動作を確認し 、デバッグを完了した。
考察 ケース  では、 プログラミングで頻出のバグを取り上げた。このような「意図しない代入」は、 のような実行時のチェックが不十分な言語以外でも起こる。
例えば 、 でマルチスレッドプログラムを作成したとする。複数のスレッドから代入される変数は、スレッド 切替のタイミングによっては、想定していない順序で代入されて正しくない値になってしまうことがある。あるいは、大規模なプログ
ラムでは代入のコードが他のコード に埋もれてしまい、そこで誤った値が代入されていることに気づかないこともありうる。
これらのいずれの場合でも、図  に示した仮説検証ループは有効である。すな
わち、異なるデバッグ局面でも仮説検証ループは再利用可能である。



ケーススタデ ィ   !" # $ "%&!   )  " "' ( 
 " &"      !" $%'

*



" &"







図 > ケース  のデバッギのコード（ 一部） ケース ：マルチスレッドプログラム
エラーの症状 デバッギは  で書かれており、サーバと通信を行う、@" を備
えたクライアントプログラムである。そのコード の一部を図  に簡略化して示す。
ユーザから @" へのテキスト入力を受けると入力データをサーバに送信する（ 図中の AB ）と同時に、その入力フィールド を一旦、編集禁止に設定する（ 図中の AB ）。
その後、サーバから再入力を指示する応答が送られてきたため、入力フィールド を再び編集可能に設定（ 図中の AB ）してユーザに再入力を促す。
サーバが再入力を指示したとき、このデバッギは  回に  回程度は正しく動作したが、残りの 回は入力フィールドが編集禁止のままになってしまう、というエラー症状を発現した。
仮説検証ループ 当初はコード に本質的な誤りがあるとは考えず、 の C-
8D である   の使用方法の誤りだと思い込んでしまった。
そこで、 回目の仮説検証ループでは、  使用方法の誤りによる、という仮説を設定した。リファレンスマニュアルを確認するという検証方法を実施したが、使用法に誤りは認められなかった。次に、デバッギのコード をマニュアルのサンプルコー
ド に近付けるよう変更する、という検証方法を行ったが 、これも成功しなかった。
そこで、デバッギのコード は元に戻し 、 箇所の  &"  の直後でその結果を表示するという、 デバッグによる検証方法を実施したが 、 &" は正常に機能していた。以上より、使用方法を誤ったという仮説は棄却し 、新たな仮説を模索することにした。

第  章 デバッグパターン

1. 情報収集

コードを見てよく考える

2. 仮説設定

スレッド切替が起こる（文の順序の誤り）

3. 検証方法考案

思考実験

4. 検証実施

思考実験を行う

5. 結果判定

文の順序の誤りを確認

図 > ケース  の仮説検証ループ（  回目：〜 回目は省略）
回目の仮説検証ループでは、図  の AB と AB 以外にも  &"  している箇所がある、という仮説を立てた。ソースコード 全体に対して ' （テキスト検索）を行う、という検証方法を実施したが 、上記以外の箇所は見つけられなかった。
よって第  の仮説も棄却した。
 回目の仮説検証ループでは、直ちに仮説を立てることができなかったので、第 段階の情報収集として、AB と AB を中心にデバッギのコード を見てよく考えることとした。正常に動作する場合もある、ということから、スレッド 切替のタイミングに依存したバグの可能性が高まった。デバッギは @" を持ち、サーバとの通信には専用のスレッドが割り当てられていることを思い出し 、AB と AB の間でスレッド 切替が発生しているのではないかと考えるに至った。そこで、AB と AB の順序が逆である、という仮説を設定した（ 図  ）。思考実験による検証を実施して合理的に説明されることを確かめ、仮説を立証した。コード を書き換えて正常に動作することを確認し 、デバッグを完了した 。


考察


ケース  に関連して、仮説検証ループにおける  つの重要な知見を示す。
仮説検証ループの繰り返しに適切なループの実行を追加することによって、仮説の設定が容易になる。この追加されるループを補助ループと呼ぶことにする。

 このバグの場合、 回目の仮説検証ループにおいて  箇所の  の直後で 
デバッグを行った際に   、  の順序で表示されれば 、バグに気づくであろう。しかしながら、  と  の間でスレッド 切替が発生する可能性があるので 、結果的にヒントを与えることにはなっても、厳密な検証とはならない。



ケーススタデ ィ

1. 情報収集現象としてはsetEditable(false)

コードを見てよく考える

2. 仮説設定

どのoperationがfalseにしたか

スレッド切替が起こる（文の順序の誤り）

3. 検証方法考案

watchの利用

思考実験

4. 検証実施

watch,
cont, ...

思考実験を
行う

5. 結果判定

promptAgain()の(3)を発見

文の順序の誤りを確認

追加された補助ループ

図  > ケース  のための補助ループ
そもそも 、スレッド 切替のタイミングに依存するバグはエラー発現の条件を固定することができないため、一般にデバッグは困難である。多くの場合は、ここで述べた  回目の仮説検証ループなどを行ってエラーに関連するコード 箇所をある程度絞った上で、コード を見て考えることになる。遠藤 (.- ) も指摘するように、仮説検証ループの中では第  段階の仮説設定が非常な難関である。従って第  段階での情報収集が重要となるが 、スレッド 切替に関する情報は一般には得られないため、仮説設定はなお一層困難になる。
そこで、 E&( ) のような、スレッド 切替を記録して再生する  &'を利用すれば 、前述の  回目の仮説検証ループの前に図  のような補助ループを実施でき、「スレッド 切替が起こる」という仮説設定が比較的容易になる。
 によって、 &"   が行われたあとで  &"   が行われることが確認されるからである 。なお、この戦略は前述のケース と同じであり、仮説検証ループの再利用に相当している。
 この例では  の利用箇所が  箇所しかないので、 の代わりに   を用いる検証方法も有効である。その場合は  箇所の   両方ともに   を設定し 、ど ちらのブレークポイントが先にヒットするかを調べれば良い。

第  章 デバッグパターンプログラマは仮説検証ループの検証方法に要するコストを見積もって、仮説検証ループを選択するということである。

この  を用いて問題の代入箇所を発見するという戦略には問題がある。
ケース  では  &"  が  回しか実行されないため、  で停止する回数も  回だけである。しかし一般には、  の停止回数は多い。作業そのものは単純であるが、それゆえに人間が行うにはややコストが高いものである。このため、スレッド 切替の記録、再生機構があったとしてもプログラマが高コストを嫌って  の戦略を避けることもあろう。その場合には、直ちに「コード を見て考える」という戦略を採ることになるが 、仮説を設定できなけ
れば  の戦略に頼らざ るを得ず、結果として時間を浪費することになる。

 まとめ

つのケーススタデ ィでの考察をまとめると、以下のようになる。

¯ デバッグ作業は仮説検証ループを繰り返すものと定義できる。
¯  つの仮説に対して複数の検証方法が存在する。プログラマは自身の能力に照らして、総合的なコストが最も低い方法を選択する。選択の結果、検証に失敗
した場合は別の検証方法に切替えて仮説の検証を続行する。
¯  つの仮説検証ループは、異なるデバッグ局面であっても共通して利用可能である（ 再利用可能である）。
¯ 仮説の設定を容易にするため、補助的な仮説検証ループを追加することができる。補助ループを用いるかど うかは  つの点に依存する。 つは 、プログラマ
がその補助ループに着眼できるか否か。いま  つは、その補助ループの検証方法に要するコストが高いか否か。検証方法の選択と同様、プログラマは自身の能力に応じて補助ループの採用を決定する。

 デバッグパターン
仮説検証ループにおいて、第  段階の仮説設定と第 〜 段階の仮説検証が最も重要な作業であり、デバッグの本質であると言える。そのうち、第  段階ではプログ
ラマの知識と経験、発想力が不可欠であり、計算機による支援は難しい。これに対して、第  段階には（ 検証方法が思考実験である場合を除けば ）支援の余地がある。
特にデバッガを用いた検証方法を選択した場合には、 点の余地が挙げられる。 つは、デバッガの実行制御がデバッグの本質とかけ離れた作業であること。もう  つは、その作業の意味に明らかなパターンが存在することである。



デバッグパターン

実行制御の困難

デバッガは強力なツールであるが 、その機能は % やハード ウェアのサポートを直接的に実現したもので、デバッグ中にプログラマが行いたいと考える高水準な作業内容との間には隔たりがある。従って、プログラマはデバッガコマンド をど う組
み合わせて希望の検証を実施するかをも考えなければならない。これはデバッグの本質とはかけ離れており、既存のデバッガの制限によるものである。
デバッガを利用した検証作業においては、特に実行制御に要するコストが高い。デバッガによる実行制御は第  節で述べた  種類のデバッガコマンド の組み合わせとなる。ステップ実行はデバッガで制御可能な最小単位の実行を実現するので、デバッギの実行は着実に  行ずつ進行し 、コマンド の組み合わせは必要ないと考えることもできる。しかしステップ実行の繰り返しは非常に低速であり、また、デバッ
ギの中で注目する必要がないと分かっている部分にまでも注意を割く事になる。ス
テップ実行だけで実行制御を組み立てることは現実的ではなく、ブレークポイント（ 前述の   ）やウォッチポイント（  ）のような、特定のイベント（ 行への到達や変数への代入）で駆動する機構と組み合わせることになる。プログラマは要所で変数の値を表示し 、その結果によって今後の実行制御の方針を決め、コマンドを組み立てる。
この組み立てはプログラマが常に直接指示しなくてはならない。コマンドを間違った場合にはデバッギを先頭から再実行して同じ 作業を繰り返す必要がある。また、検証に失敗して別の検証方法を試みる場合や、第  段階で設定した仮説が棄却された場合には 、新たな検証実施のために制御を再び別の点へ移動させることになる。
これは特に苦痛を伴う作業であり、実行制御はデバッグに要する時間の多くを占め、プログラマの拘束時間も長い。
さらに、そのときに行ったデバッガ操作はコマンド の羅列であり、その場限りのもので、再利用ができない。しかしその羅列の中には、デバッガを用いてどのような作業を行ったかという、コマンド 列よりも抽象化された明確な意味が存在する。

 パターンの存在
仮説検証ループに意味のパターンがありループ全体を再利用可能であったように、その一部である検証実施段階（ 第  段階）もまた意味のパターンを持ち、再利用可
能であることをプログラマは経験的に知っている。例えば 、以下のようなものが挙げられる。

¯ コマンド を間違って目標とする実行状態をうっかり通り過ぎてしまったので、以前の状態まで戻りたい。
¯ ある変数が予期しない値になっているときに、その値を代入したオペレーションを知りたい（ケース  で述べた、デバッガの  を用いる検証方法）。

第  章 デバッグパターン¯ 何が原因か見当がつかないときに、プログラムがどの段階まで正しく動いていたかを知りたい。
こうした典型的な作業は現在は完全に手動で行われているが 、近年の計算機の強力な処理能力を利用して自動化することができれば 、プログラマはデバッガを制御する苦痛から解放されて、仮説の設定と検証というデバッグ作業の本質に集中できるようになる。

 デバッグパターンの定義
以上より、仮説検証ループの第  段階（ 検証方法の選択）と第  段階（ 検証の実施）に内在する本質的な手続きをデバッグパターンと呼ぶことにする。具体的には
第  節で示した  つの例がこれにあたる。本論文ではデバッグパターンを自動化することによって、デバッグ作業中のプログラマを支援する方法について述べる。
デバッグパターンの自動化により、直接的にはデバッグ作業に要する時間の減少という利点がある。それだけでなく、仮説の検証における労力が低減されるため、プログラマにとっては仮説設定の心理的バリヤーが低下することになる。これにより、様々な仮説を積極的に検証することを可能にし 、確実なデバッグを促進する。
デバッグパターンは、オブジェクト指向プログラミングの設計におけるデザイン
パターン (2& ) と対比することができる。デザインパターンは典型的なオブジェ
クトの階層構造をパターンとしてまとめることで、設計のノウハウを再利用することを可能にした。デバッグパターンも同様に、デバッグ作業における本質的な手続
きをパターンとしてまとめ、デバッグのノウハウを再利用できるようにする。

 パターンとしての関連研究
関連研究の中には、デバッグパターンの  つとして位置付けられるものがある。



逆実行

実行を遡りたいというのは自然な欲求であり、逆実行には長い研究の歴史がある。
これらは状態保存による逆実行と、再実行を用いた疑似逆実行とに大別できる。いずれの方式にせよ、デバッガを用いた検証方法を選択した場合には、逆実行はプロ
グラマの手作業を自動化する有効なパターンと言える。



パターンとしての関連研究'  ' "
+  "    +  "     +   " +,"  ,!  - ! .  ,! - ! /    ,! ! 0  ,!"0 ! 1"0  ,! ! 2図  > $(



$

)

における実行制御コマンドイベント 駆動型実行制御や  / のような一般的なソースレベルデバッガは、実行制御をソースコー
ド のステート メントを単位として行う。これに対して、代入や関数呼び出し 、ループなどをイベントとして扱い、イベントを単位として実行制御を行う方法もある。
$##F( $) は、条件付ブレークポイントの条件をプログラマが ! に似た書式で記述できる仕組みを提案している。例えば 、図  のようなコマンド をデバッガに与えると、「関数 ' の中で  文に入るか  文から出るようなときにだけ実行を停止せよ。 のときであれば盤面を表示し 、変数  - と  - も表示せよ。それ以外のときは変数  と "0 と  を表示せよ。」という指示をしたことになる。
この仕組みも新たなデバッグパターンの  つとして位置付けられる。従来のソースコード 型実行制御よりもイベント駆動型実行制御の方が仮説の検証が行いやすい、という場合はこのパターンを用いてより容易に検証を実施できるからである。


/









ら (2G 9 G ) は   を提唱している。あるデバッギが正常終了するときと異常終了するときの入力データを  分探索的に比較して、入力デー
タの中から異常の原因となったデータを自動的に抽出するという手法である。また、入力や引数の違いによって生じるデバッギ内の変数の値を比較して、その伝播の関係を抽出することも行っている。これは非常に有用な手法であり、現代の計算機の強力な計算能力によってプログラマの労力を軽減するという観点で、本研究と近しいものと言える。
G!



第  章 デバッグパターン

この手法もまた、パターンの  つとして位置付けることができる。このようなパターンの自動化が提供されることで、これまでは検証方法が高コストであるために敬遠されてきた仮説も検証されやすくなる。この仮説検証ループを前述の補助ループのように用いれば 、後続の仮説の設定の敷居を下げる効果も期待できる。



第章

関数単位疑似逆実行

デバッグ作業における典型的なオペレーションとして代表的なものに逆実行がある。
通常のデバッガはデバッギをその実行順ど おりにしか動かすことができないので 、
現在位置の直前の情報を得るためにさえ、プログラマはデバッギの実行を停止させて先頭から再実行させなくてはならない。逆実行とは、デバッガやインタプ リタのサポートによって実行状態を過去の状態に戻す機能を言う。
本章では逆実行の技術の中から再実行による疑似逆実行を紹介し 、プログラマにとって有用な自動化である関数単位疑似逆実行とその高速化について述べる。一般
的な逆実行の手法と本研究との比較については第  節で述べる。

 疑似逆実行
プログラムの実行は変数への代入、すなわちメモリの書き換えの繰り返しで進行するので、逆実行のためにはメモリ内容の変遷を記録しなくてはならない。しかしデバッギに再現性があれば 、再実行して直前で停止することで疑似的に逆実行を実現することができる。デバッグ作業中のプログラマはこのプロセスを手動で行っており、疑似逆実行はこれを自動化していると考えられる。例えば行単位の疑似逆実行を行う場合、再実行の際に停止すべき行は現在行の直前ということになる（図 
中の ! ）。

beginningtargetnow
Progressofexecution

reverseexecution
pseudo reverse execution

図 > 疑似逆実行

第章



beginning

関数単位疑似逆実行

entranceoftargetparentnow
Progressofexecution

pseudo rev. exec.
(automatically)

forward exec.
(manually)

図 > 関数単位疑似逆実行
より粒度の低い単位として関数単位の疑似逆実行がある (8! )。これは逆実行の単位を関数呼び出しに定め、再実行の際に停止すべき行を現在実行中の関数の入口とするものである。この方式では現在の関数の入口までは自動的に戻ることができるので、プログラマはそこから順方向に実行を進めて目的の行まで移動することになる（ 図  ）。デバッガには  というコマンドがあり、現在の関数を終了するところまで実行を進めて親関数（ 現在実行中の関数を呼び出した関数）のフレー
ムへ戻ることができる。関数単位疑似逆実行はこの  を逆向きにしたものと考えることができ、人間が行うデバッグ作業において自然な場所と言え、十分にプ
ログラマの労力を軽減する機能である。

 従来手法
本節では 、寺田 (8! ) が実装した  での関数単位疑似逆実行の手法（ 以下、従来手法と呼ぶ）とその問題点について述べる。
従来手法では、再実行の際の移動先となる現在の関数の入口を識別するため、特別なカウンタ（ 以下、タイムスタンプと呼ぶ）を用意して関数呼び出しが起こった際にタイムスタンプをインクリメントする。この機構をプロファイル用関数 の再定
義で実現により、容易かつポータブルに実装することに成功している。
図  に例を示す。現在、関数 $ の  の部分を実行中とすると、その入口は図の通りである。図中の網かけの丸印はタイムスタンプ更新場所であり、左の数字がそのときのタイムスタンプ値を示す。この例では自分の呼び出しは  である。
 という値が分かればデバッガを用いてそこまで移動することができるが 、移動目標のタイムスタンプ値（ここでは  ）をどのようにして得るか、ということがプログラムの性能測定のために、関数呼び出しの入口で呼び出される関数。この呼び出しはコンの場合は  オプションを指定することで、
パイラによって自動的に挿入される。
という関数の呼び出しが挿入される。



従来手法



me
child1child2125

grandchild126

entrance 127
of me

128

now
timestamp updated

図 > 現在の関数の入口

n+2
depth
of n+1
stack
n

127

grandchild128

child2125me

図 > シミュレートするスタック問題である。現在点でのタイムスタンプ値は   ") の入口で更新した値であり、目標点から現在点までの間に何回更新されたか、すなわち何回の関数呼び出しがあったかは一般には知ることができない。
関数呼び出しには必ず  つのタイムスタンプ値が対応するので、関数呼び出しのスタックをシミュレートして呼び出し深さごとの最新タイムスタンプを保持すれば良い。関数 $ の呼び出しが深さ  とすると、シミュレートするスタックの深さ に相当する場所にはタイムスタンプ値として  が保持される（ 図  ）。深さ  H には   ") のタイムスタンプ値である  が 、深さ  H  には '"  " が呼び出されたときの  が残っている。$ の呼び出し時点でのタイムスタンプ値を知りたいときには、自分の呼び出し深さである  を見ると、目標とする関数呼び出しのタイムスタンプ値が手に入る。
しかし 、関数呼び出しの出口をトラップできないことから現在点の呼び出し深さ
が正確に分からないため、正しい深さを取得するための #$ 4## を導入することで解決している（ 図  ）。すなわち、現在の関数の入口に戻るためには #$ 4## と!50$ 4## の  パスが必要になる。
#$ 4## では、デバッガの持つスタック検査コマンド（  / では ）を用
いてスタックの深さを正確に知る。従って、#$ 4## では通常のデバッギの実行時間に加えて、デバッガによるスタック検査の時間がかかってしまう。

第章



begginningof exec.

target ofreverse exec.

関数単位疑似逆実行

reverse exec.
instructednormalexec.
pass 1:
scan pass
pass 2:re-exec. pass図 > 従来手法 (8!

) 新手法
従来手法はポータブルで、処理系を変更しないで済む実装方法を取った代償として、 パスを要するというパフォーマンス上の問題点を持っていた。本節では、移植性を失う代わりに、処理系を変更しないままで  パス問題を解決する新手法 ('8 )について述べる。

 フック関数呼び出しの挿入
パスの問題は関数呼び出しの出口を捕捉して、図  の通常実行中においても呼び出し深さを正確に保持することができれば解決する。そこで、関数呼び出しの出口（ 関数定義の末尾）にフック関数 $ ) を呼び出すコード を追加する。関数呼び出しの入口部分については、従来手法同様にプロファイル用関数の機構を流用し 、
フック関数 $  の呼び出しを挿入する。これらの挿入は、実装の容易さを考慮してアセンブリコードレベルで実装した。フック関数の定義を図  に示す。
この実装では関数呼び出しの出口の処理が    文の場合も兼ねているので、返り値を上書きしてしまわないよう、$ ) が使用するレジスタを全て保存した上で $ ) を呼び出し 、再びレジスタの内容を復元する、という手順で行っている（ 図  ）。以上により、 パスで現在の関数の入口へ戻ることに成功した。
 ユーザインタフェース
ユーザが利用する手段として、 / のフロントエンドである $+'"(8! ) に機能付加する形で実装した。利用例を図  に示す。図の状況は、関数  "   内をデバッガで実行しているところであり、下  程度に実行中のソースコードが表示されている。図中の下部で  というコメントで示してある網かけの部分が 、デバッガがこれから実行しようとする行を示している。ここで関数単位疑似逆実行



新手法



3"  4%5,6&#(7 )89
 ,:4%5,6&#(7; "   < $ $  <    <!" $ !""  $ $,:"  ;  $ $!" $ )!""  <<図 > フック関数の実装
return_label.L1:
pushl %eax
pushl %edx
pushl %ecx
call mcount2
popl %ecx
popl %edx
popl %eax
movl -24(%ebp), %ebx
movl %ebp, %esp
popl %ebp
ret

added for trapping
exit of function calls:
saving the return value,
calling mcount2,
and restoring the value.
original epilogue

図  > 関数呼び出しの出口のトラップを指示すると、コメント '   で示した場所、すなわち現在実行中の関数である  "    の先頭に制御が移動する。
実際にデバッガの一機能として利用される場合、ユーザが設定したブレークポイ
ントなどにより、単純に再実行を行ってもデバッギが期待通りの場所で停止するとは限らない。また、頻繁にブレークポイントにヒットしてしまうと再実行の際の実行速度が極端に低下する。
そこで 、再実行を行う前にユーザが設定したブレークポ イントを一旦全て無効

第章



関数単位疑似逆実行

図  > $+'" での利用例（ " ）にし 、逆実行が終了した後に再び有効（ 採っている。

）にする、という方法を処理時間計測新手法の処理時間を、以下の条件で計測した。デバッギとして #-5 を用い、
 行（  バイト ）のテキストファイル に対して =$ =4%>&=' を行って=" !=
へ出力した場合について、  回目の関数呼び出しで停止させ、その呼び出しの入口への逆実行に要する時間を計測した 。計測に用いた計算機は   6 '2; 、メモリ '/ 、:05  という構成で、時間の計測には I@ +5
での 4#- + を用いた。以下の  種類の処理時間を、従来手法と新手法について調べた。
通常実行 <' オプションと <' オプションでコンパイルしたデバッギを通常実行 。
この場合だけ、特に参考のために、<2* オプションでコンパイルしたデバッギの実行時間も計測した。

 上記のデバッギを、逆実行を実装した ! スクリプト（以下、ド ライバ
プログラムと呼ぶ）で  パスだけ実行。このスクリプトは 
れを介してデバッギを制御するので、この時間には ! と 含まれる。

を起動し 、こ/ の起動時間も/ カーネルを  したときのログファイルを連結したもの。
 逆実行の開始点と目標点が同一となるが 、処理のオーバヘッド を知るには十分である。

プロファイル用関数の仕組みを流用するので、  が必要になる。新手法用のデバッギは、これ
らオプションを指定して得られたアセンブ リコード をさらに変換して、実行コード を得る。



新手法



表 > 新手法と従来手法による  " の処理時間 ('8- +,!+ 0$
-!$!

 



 

 



 

, #$ 4##+,-

4+;
J



 

)

J

J

J

単位は秒

Perl

GDB

debuggeepass pass pass1
2
3

old method
7.068 7.38 7.068(sec.)
21.516

new method
7.022

7.022
(sec.)
14.044図  > 各手法の処理時間の内訳

  上記のデバッギで、ド ライバプログラムによって自分自身の関数呼び出しの入口へ逆実行した場合の実行時間。

    !  従来手法に関してのみ、#$ 4## を行わなかった場合の処理時間も計測した 。

計測の結果を表  に示す。関数呼び出しの出口を捕捉するようになったことで、
通常実行時のデバッギの実行速度は従来手法よりも低下しているとは言え、微々たるものである。
一方、表  より得られた実行時間の内訳は図  のようである。! と  / の起動に要した時間を除いた実行時間はおよそ  倍になっており、逆実行速度は パスから  パスになった分、減少し 、新手法の効果を示している。
前述の通り、関数単位疑似逆実行はデバッグ作業中のプログラマがよく行う作業のひとつを代行するものと言える。デバッグ作業では他にも実行制御のパターンが この場合に限っては最初から目標点のタイムスタンプが分かっているので、  を不要にしても目標点に制御を移動できる。



第章

関数単位疑似逆実行存在するが 、関数呼び出しのみでタイムスタンプを更新する手法では実行制御の移動先が限定されてしまう。実行制御の移動先として任意の場所を指示するためにはより一般的な表現が必要となる。



第  章 プログラム実行点
一般的な実行制御を自動化するために、プログラム実行点という概念を用いる。これはプログラムの実行状態をその進捗度として表すものである。本章では実行点の必要性とその表現方式について述べ、単純な応用である動的ブレークポイントを導入する。

 実行点の概念
デバッグを行っているとき、特にデバッガを用いているときに、多くのプログラ
マはデバッギの進捗度（デバッギの実行がどこまで進んだか ）を漠然とイメージしている。それは例えば 、「この関数の呼び出しから戻ってきた、この場所」といったようにソースコード に直接対応する形のこともあれば 、「木構造のトラバースで、このノード に到達したとき」などと、データ構造に対応する形のこともある。このようなデバッギの進捗度は、プログラムの実行過程における  点と考えられることか
ら、これをプログラム実行点と呼ぶことにする。
ここで、手続き型言語のプログラムが実行される場合について考えると、ソース
コード の各行を制御構造に従って順に実行していくので、プログラムの実行の完全なトレースは実行された行の時系列で表すことができる。これをプログラムの実行系列と呼ぶ。プログラムが入力データなどによって振舞を変える場合は、同一のプ
ログラムであっても実行系列は実行ごとに異なる。一般には、プログラムを実行するごとに特定の実行系列が生まれる。プログラム実行点は、このような特定の実行系列における絶対座標を表すものと考えることができる。

 実行点の表現形式
概念としてのプログラム実行点を具体的に表現する形式を考えると、以下の  通りの表現が考えられる。
ステップ実行の回数 ステップ実行はデバッガで制御可能な最小単位の実行を実現する。従ってこれを繰り返せば完全な実行系列を得ることができる。
デバッガコマンド 履歴 デバッガコマンド の履歴を再生すれば 、行った実行制御を再現して同一の実行点に移動できる。

第  章 プログラム実行点    )  * 

図 > ループ構造を持つデバッギ
real target(1) (2) (3) (1) (2) (3) (1) (2) (3)breakpoint hits

図 > ループ構造を持つデバッギの実行系列
行番号とブレークポイント のヒット 回数の組 デバッガはブレークポイントのヒット
回数をカウントしているので、行番号とこの回数の組。
行番号とタイムスタンプの組 制御点が上向きにジャンプするときにインクリメントされるカウンタ（タイムスタンプ ）と、行番号の組。
最初の  つには 、実行効率など の問題があるので採用しない。詳細は第  節で述べることとし 、以下では第  の選択肢に関する説明を行う。
実行点は実行系列における座標であるという考えに基づけば 、ソースコード の行
番号（正確には、ファイル名と行番号の組）が利用できるように思われる。実際、デバッガにおけるブレークポイントは行番号を利用する。しかし 、一般にブレークポ
イントはデバッギの実行中に何度もヒットする。このことから、行番号は実行系列における座標としては不十分である。
図  のようなループ構造を持つデバッギ #$ を例に採って考える。このループの本体が  回実行されるとすると、AB で示した行 #$> は実行系列中に  回登場
することになる（ 図  ）。
ファイル名と行番号が静的な情報に基づいているために 、実行系列中の複数の#$> を区別することができない。このような A=>B で表される位置を静的な

実行点の表現形式

position(test.c:2, 7)(test.c:2, 6)(test.c:2, 8)(1) (2) (3) (1) (2) (3) (1) (2) (3)(test.c:2)
location

図 > $ と 4#
位置と考え、    と呼ぶ。これは静的に K な情報で、ソースコード 中の一点を表すことができる。
これら複数の #$ を区別するため、$ に動的な情報を付加して動的な位置を表現する。実行系列中に同じ $ が登場する際に必ず更新されるカウンタを用いれば 、$ とカウンタの組は動的に K となり、実行系列中の  点を識別できるようになる。第  章での命名にならい、このカウンタをタイムスタンプと呼ぶ。そして、この動的な位置こそが実行点の概念を表したものである。   に対して !   と呼ぶことにし 、A=>9 +#+4B のように表すこととする。
この表現方法は '!5!++? らも  ! "#!$ !(': ) を用いた表現方法として挙げているが、彼らの実装は実行点の表現としては不十分である。
これについては第 章で述べる。
図  の例で 、実行制御の移動目標となる 4# での $ $ が であったとすると、その 4# は A#$>9 B と表せる。一方、それ以前に登場する  回のA#$>B はそれぞれ A#$>9 B と A#$>9 B となる（ 図  ）。
なお、ここではタイムスタンプの値が既知であることを前提にしている。4#
はデバッグ作業中に利用するため、タイムスタンプの値を含む 4# の情報は $?$$- における以前の実行で取得済みでなければならない。また、現時点では
デバッギは再現性を持つという前提である。再現性を持たないデバッギは第 章で扱う。
タイムスタンプの値は、プログラマがその値を推定して直接指定できるような性質のものではない。例えば「あのループの  回目に興味がある」と思っても、そのときのタイムスタンプ値を推定することは事実上不可能であり、デバッガを用いてその 4# まで到達して変数 $ $ の値を取得するしか方法はない。タイムスタンプ値は 、第  章で述べるような $?$$ - を基礎とするアプ リケー
ションから利用することを想定しており、プログラマが直接利用することは想定されていない。

第  章 プログラム実行点

を他の形式で表現することもできる。例えば 、実行制御には常にステッ
プ実行を用いると決めると、4# はステップ実行の回数として表される。また、デバッガのコマンド 履歴を完全に再現すれば同一の実行状態に到達できるので、これも 4# の表現たりうる。あるいは、実行を開始する前にソースコード の全ての行にブレークポイントを設定しておけば 、該当行に設定したブレークポイントのヒット回数を 4# として用いることもできる。これらの表現形式と、本研究で採用したタイムスタンプを用いた形式との比較は第 章で行う。
4#

 動的ブレークポイント
本節では 4# に対して設定できるブレークポイントを考え、これを動的ブレークポイントと呼ぶ。一方、通常のブレークポイントは $ に対して設定するので、これを静的ブレークポイントと呼ぶ。
動的ブレークポイントは  / の条件付ブレークポイントを用いれば簡単に実現できる。A#$>9 B に対して設定する場合は以下のような  / コマンド を用いればよい。

    )  $ $  ?
しかし条件付ブレークポイントの実装は、ブレークポイントにヒットするたびに条件をデバッガが評価して成否を決定するため、一般には多くのプロセススイッチが発生して実行速度が犠牲になる。効率の良い実装については、第  章で  と  への実装の詳細とともに述べる。
動的ブレークポイントは 4# の単純な応用であり、第  節で述べたデバッ
グパターンを実現するための基礎となるものである。各パターンの詳細については
第  章で述べる。

 タイムスタンプのインクリメント
タイムスタンプはループの実行のように、同一の $ が繰り返し実行され得る場合にインクリメントされなければならない。従って、 のソースコード の場合を例とすると、以下のような場所に制御が到達したときにインクリメントが起こる。

¯ 関数呼び出しの入口と出口（ 関数定義の先頭と末端）¯    文
¯ ループの繰り返し¯ 上にあるラベルへの ' 文によるジャンプ

タイムスタンプのインクリメント



関数呼び出しの入口でのインクリメントは、 回以上呼び出される関数の呼び出
しを区別するために必要となる。再帰的に定義された関数では再帰呼び出しからリターンした後で同一の $ を通過する可能性があるので、関数呼び出しの出口
でもインクリメントする。   文は関数呼び出しの出口と同様であるが 、返り値を持つ場合があり、実装上は別のものとして扱うことになる。



第章

 および   への実装

本章では、前章で述べたタイムスタンプ更新機構を  及び  のデバッギに自動的に組み込む方法 ('8 ) について述べる。

  への実装
第  章の次のステップとして、まずは  に対する実装を行った ('8 )。前章のタイムスタンプはデバッギ中に大域変数 $ $ として導入し 、これをインクリメントするコード をデバッギ中の制御ジャンプ命令の直前に追加する。コード の追加はコンパイラの中間コードレベルで行った。



更新機構挿入のレベル  

デバッギにタイムスタンプ機構を挿入するには、中間コードレベルを含めて以下の  つのレベルが考えられる。本節ではそれぞれ方法の比較を述べる。


ソースコードレベル



中間コードレベル

アセンブリコードレベル

第  のソースコードレベルとは、ソースコード 変換を用いて行う方法である。この方法はソースコード そのものを対象とするので、処理系や % 、プラットフォーム
を選ばないという利点があるが 、デバッグ中にプログラマから見えるコード は変換後のコード になってしまうという欠点がある。
第  の中間コードレベルでは、コンパイラが内部的に持っている中間コード を変換
してタイムスタンプ機構を挿入する。コンパイラはソースコード を入力として受け取ると一旦この中間コード に変換し 、最適化などを施した後で対象プラットフォー
ムのアセンブリコード として出力する（ 図  ）。例えば 、I@  +4!( )（  ）では 1#! 8!#! :（ 18: ）と呼ばれる中間コード を利用している。中間コードレベルで挿入すればポータビリティが失われることはないが 、特定の処理系に依存することになる。

第章





および  への実装

source code

lexical analysis
token
syntactic analysis
parse treeintermediate
code generationintermediate representation tree
optimizationintermediate representation tree
code emission
assembly code
assemblage

object code

図 > コンパイラの構成
第  のアセンブリコードレベルでは、図  の ##+? $- を変換する。これは実装が最も容易な方法であり、第  節で述べた関数単位疑似逆実行における新手法の実装で採用していたが 、各環境毎に実装する必要があるためポータビリティに欠ける。
以上より、第  の中間コードレベルで実装することとし 、対象とする処理系は様々なプラットフォームで広く利用されていることと  / との連係を考慮して、を選んだ。今回は実装時点での最新版である 5  を実装の対象とした。



タイムスタンプ更新コード

タイムスタンプ 更新場所に到達したときに図  のタイムスタンプ 更新マクロ
0-/ (@ を実行するように、デバッギが変換される。デバッギからデバッガへのトラッ
プが 、特定のタイムスタンプ値に到達したときにだけ起こるように工夫してある。
デバッギはコンパイラによって、全てのタイムスタンプ更新場所にマクロ 0-/ (@ を





への実装



 $ $  <    <!"  !"
3" 

0-/,(@ $ $     

図 > タイムスタンプ更新コード

syntactic analyzer(yyparse)
call
token
sourcecode

readlexical analyzer(yylex)call
parser actions

emit

RTL list

図 > 構文解析器の振舞
展開したコード の 18: を自動的に挿入される。さらに、このマクロのために、デバッ
ギの各ファイルの先頭部分には変数 $ $ と   の   宣言、関数 のプロトタイプ宣言が 18: として挿入される。これらの実体は別途ライブラリとして用意し 、コンパイラが自動的にリンクする。

 の変更点

図  ではコンパイラの処理のステージを列挙したが 、実際のコンパイラの処理は明確には分かれていない。 は構文解析器である関数 ++ が字句解析器である関数 ++  を呼び出し 、読み込んだトークンを構文解析して対応するアクショ
ンを呼び出し 、そのアクションが随時 18: を出力するようになっている（ 図  ）。
18: は双方向リスト構造をしているので、ここでいう出力とはそのリスト構造へ新しい 18: 式を追加することを意味する。
タイムスタンプ更新コード の追加は構文解析器のアクションで処理するため、追加の場所はソースコード の構造と対応づけて考える。前章で述べた通り、以下の 
種類の場所で追加する。

¯ 関数呼び出しの入口・出口

第章





および  への実装

¯    文
¯ ループの繰り返し¯ 上にあるラベルへの ' 文によるジャンプ
なお、この方法では、 '$ の呼び出しは一般のライブラリ関数の呼び出しと同等となり、タイムスタンプをインクリメントしない。従って、現在は '$
を含むコード（ '$ の呼び出しを含む実行系列）では 、4# の妥当性は保たれない。

構文解析器への変更
構文解析器である関数 ++ はコンパイラが新しいソースファイルを読み込む
たびに呼び出されるので、その処理の最初に変数 $ $ と   の   宣言、
関数  のプロトタイプ宣言を 18: リストへ追加する。
アクションへの変更
前章で挙げた、タイムスタンプを更新すべき  つの場合のそれぞれについて、どのアクションのどの部分で 0-/ (@ の 18: を挿入すれば良いかを述べる。
ループの繰り返し ループが繰り返される場合は  通りある。 つはループ本体の末尾に到達した場合で 、もう  つは  文が実行された場合である。これらを考慮して、 はループを図  のような 18: リストに展開する。 
はループ本体の末尾に到達したときのジャンプ先ラベルであり、
 は 文が実行されたときのジャンプ先ラベルである。ここでは  文を取り上げたが 、"<  文でもほぼ 同様になる。  文では特に 、  と
 が一致する。
タイムスタンプ更新場所であるループの繰り返しは本来ループ本体（図中の  ）の末尾に相当するが 、 文による繰り返しも一緒に扱うようにした方が実装が容易になるので、  の直後（ 図中の☆）で更新することにする。ループに入る最初の  回だけ余分に更新されることになるが 、全体の計算量に比べれば無視できる量である。
 文のときは、構文解析器はアクションである関数 "   を呼び出す。 と "<  のときは、 "   
 が呼び出され、これが "   を呼び出す。  の出力は"   内の関数 $  の呼び出しで行われるので 、その直後で0-/ (@ を展開した 18: を 18: リストの末尾に追加した。





への実装



(1) initialize
start_label☆

for( 1 ; 2 ; 3 )4(2) check conditions
true(4) body of loop

false

continue_label(3) increment expression
end_label

図 > ループ構造の 18: への展開（☆は更新コード 挿入位置）' 文に基づく ' 以外にも、 独自の拡張として $  と$+4-  がある。$  は #- $ において外側の関数内部のラベルへジャンプするものであり、$+4-  はジャンプ先のラベルを変数の値を用いて決定する。いずれも使用頻度は低いと考えられるので、今回の実装では考慮しなかった。また、本来はジャンプ先のラベルが下方にある場合はタイムスタ
ンプ更新は不要であるが 、実装を容易にするためジャンプ先ラベルの位置の判定を行わないことにした 。
通常の ' 文と $  の場合、構文解析器はアクションである関数
" ' を呼び出す。 " ' は $  かど うかを判定して、通常の ' の場合は直ちに " '   を呼び出すので、この呼び出し直前
で 0-/ (@ を追加するように変更した。
I"    文   文のときは構文解析器がアクション  "    を呼び出

すが 、返り値がある場合とない場合とでその後の動作が異なる。返り値がない場合は"    が呼ばれてそこから "     が呼ばれるが 、返り値がある場合は "    経由で "     が呼ばれ 、いずれの場合も最終的にはそこで関数定義のエピローグへ向かって " '  
によってジャンプすることになる。
0-/ (@ の追加は  つの場合が合流する関数 "     で行うこともできるが 、返り値がある場合、その段階では既にレジスタ内に計算済みの返り値が設定されており、そこでタイムスタンプ更新マクロを実行すると返り値を壊してし タイムスタンプの更新は、実行系列中に同一の   が再び登場するまでの間に少なくとも 
回登場すれば良いので 、更新し 過ぎてしまっても    の妥当性は失われない。ただし 、余分な更新を行うことで処理速度が多少犠牲になる。



第章



および  への実装

まうことになる。返り値が保存されている可能性のあるレジスタをスタックに退避してからタイムスタンプを更新するという方法もあるが 、ここでは    文の処理を開始する前である、 "    の最初で追加することにする。
関数呼び出しの入口 関数定義の先頭ではまず、関数名と型の情報などを登録する
   が呼ばれ、次に引数の名前と型を登録する  $ "   が呼ばれ 、定義本体である $+4- #+ の処理に移る。
関数呼び 出しの入口で 、かつ、関数定義のときにのみ 0-/ (@ が実行されるためには、$+4- #+ の処理に入る前に追加されることが望ましい 。そこで、
 $ "   の末尾で追加する。
関数呼び出しの出口 関数のエピローグ部分を処理するアクションは   である。このアクションは、   文が実行されたときのジャンプの目標となる     をエピローグ部分に設定する。    よりも下に 0-/ (@ を追加してしまうと、   文のときに余分なタイムスタンプ更新が発生するだけでなく、レジスタに保存された返り値を破壊する可能性があるので 、    より前に追加されなくてはならない。従って、関数   
の最初で追加する。

コンパイラド ライバへの変更
必要なときだけタイムスタンプ機構が組み込まれるように、 に新しいオプショ
ン <') を追加する。新しいオプションを設定するには、構造体 "   $ を修正して、コンパイラ本体である  のオプション設定に追加する。次に  の$ 関数のオプション解析ループの中に追加して、<') が指定された時だけ特別なフラグを立てるようにする。前述の 0-/ (@ 追加用のコード はこのフラグが立っている時だけ動作するようにしておく。
次に、 などの定義が含まれるライブラリを<') 指定時に自動的にコンパイ
ラがリンクするよう、各プラットフォーム用のヘッダファイルに含まれる .01 @#&/ マ
クロを修正する。例えば  50 であれば '='=   に含まれている。
追加されるコードに対する変更は全部で 行程度であった。このような変更を施した  の動作を以下のプラットフォームで確認した。別のプラットフォームへ移植するため 構文解析器による     の処理は、関数定義に限らず  文などで登場する場合も同様に行われるので、    のアクションで追加を行うと不要なタイムスタンプ更新が増え、実行性能に悪影響を与えてしまう。





への実装

 $ $$! $ $A 
$  A  .9





  
"
""

  
"
$

$!


A ,$ $ A
:AA ,$ $; AB
AB  AB
AB :AA ,$ $;A ,  A
:AA , ; AAB A.)
B A ),  B

図 > 追加されるアセンブリコード（  50（ 左）と #4!$5##（ 右））に必要なことは、プラットフォームごとのヘッダファイルに含まれるマクロを新たに  行書き直すだけである。

¯  50¯ #4!$5##¯ 4,50¯ #4!$5#5#!#
実際に追加された 18: によるアセンブリコード を、 50 と #4!$5## のそれぞれについて図  に示す。これらは、オプションとしてデバッグ用とタイムスタンプ機構導入用、最適化用である、<' <2 <') をつけて生成したコード である。

 オーバヘッド
タイムスタンプ機構によるオーバヘッド を計測した。表  は  D5 をデバッギとした場合の実行速度のオーバヘッドを示している。その他のベンチマークについては表  に示す。+4? 4 ベンチマークは空ループのみを持つデバッギで、実行時間のうちの大部分をタイムスタンプのインクリメントが占めており、タイム
スタンプ機構のオーバヘッド の最大値を示している。#- ベンチマークは #-5 を用いた。また、表中のプラットフォーム名については詳細を表  に示してある 。
  プラットフォームは既に失われており、残念ながら詳細な仕様は不明である。

第章



および  への実装

表 >  におけるオーバヘッド   D 4#"5

5 5%

4,

15



 


A

5 5% 54

B

A

B

A

B







A B

A B

A B

単位は秒（ 括弧内は比）表 >  におけるオーバヘッド  その他のベンチマーク
44 4#

+4? 45 5%

5 5% 54"515

 

 

A

A

B


A B

#-

5 5%

 
A

5 5% 54



D

5 5%

B

 
A 

B

 
A

B

  

 

A

ABB


A

5 5% 54

B

 
B

A

B





AB

AB

単位は秒（ 括弧内は比）表 >  におけるオーバヘッド  各プラットフォームの概要!+

!$,$!

%

4,

4,



'2;

:0 A$B"5!

'2;

:0 A$B"5!'2;:0 A$B15

1

IL

%515@!1'2;

!#5







への実装



表 >  におけるファイルサイズ増分
44 4#

+4? 45 5%"5A

5 5% 54

B


A

#-

5 5%

 

5 5% 54

D

5 5%

B





B

ABA

B


A B



 

B

A

 



A
5 5% 54

A



A B





B

A

15

AB

B

AB

単位はバイト（ 括弧内は比）タイムスタンプの更新回数は、+4? 4 で  回、#- で  回、
 D で   回となっている。 回のインクリメントにかかる平均時間はそれ
ぞれおよそ  ナノ秒、   ナノ秒、 ナノ秒であり、実用に耐える。
表  はそれぞれのベンチマークのファイルサイズの増分を示しており、これらも実用に耐える数値であり。



動的ブレークポイント の実装

第  節では 、デバッガの条件付ブレークポイントによる動的ブレークポイントの実装を紹介したが 、ここでは最低限のオーバヘッド での実装を示す。
まず、タイムスタンプ値が目標点のそれと等しくなる更新位置まで実行する（ #4 ）。すると 、そこから目標の 4# までの間に 、目標点と同じ $ が別の
4# として存在し得ないことが保証されているので、通常のブレークポイント
を用いて、さらに真の目標点まで実行すれば良い（ #4  ）。
図  におけるタイムスタンプ更新のタイミングを図  に示す。この例では目標点と同一の $ は実行系列中に  回登場する（ 図中の△印）。しかしタイムス
タンプが更新されるタイミングは、隣り合う $ の間に必ず  つ存在する。すなわち、タイムスタンプが目標値（ 目標 4# でのタイムスタンプ値）に更新されてから、目標 4# までの間には目標 $ は存在しない 。従って、前述の この場合の例では 、タイムスタンプ更新点の間に必ず目標点と同一の   が出現しているが 、出現しない場合ももちろん存在する。タイムスタンプは、その値が次に更新されるまでの間に、目標点と同一の   が  回または  回だけ出現することを保証する。

第章



timestamp = 6

および  への実装

timestamp = 8timestamp = 7(test.c:2, 6) (test.c:2, 7) (test.c:2, 8)

step 1step 2timestamp updated
target location (test.c:2)

図 > 動的ブレークポイントの実行手順と #4  は図のようになる。この方法は、$ $ と   の比較をデバッ
ギのコンテクストで実行し 、デバッガへのプロセススイッチを最小にしたものと言える。
#4 

への実装に実装した経験に基づいて、 プログラムに対してはコンパイラが生成した
クラスファイル（バイトコード ）を変換することでコード の追加を実現した。独立した ($ $ クラスを用意し 、タイムスタンプ機構に必要な要素はそのクラスの#$ ++! とした。





更新機構挿入のレベル   
へ実装する場合の選択肢として以下の  つのケースを検討した。



コンパイラ（ソースコードレベル ）クラスファイル（バイトコードレベル ）（バイトコード 実行レベル ）

 &'

 

（デバッグ インタフェースレベル ）

第  と第  は  における検討と同様の理由で候補から除外される。第  の  
（  !+ ! !$,$! ）は移植性に優れるが 、デバッガに組み込ん





への実装



で利用する形となり、デバッギとの間のプロセススイッチによる実行速度の大幅な低下が懸念されるためこれも除外される 。
バイトコード は  におけるアセンブリコード と同質のものであるが 、その形式は仕様 (:M ) によって定められており、ターゲットアーキテクチャに依存することが
ない。



タイムスタンプ更新対象のバイト コード

タイムスタンプ更新の対象となるバイトコード を検討する。
メソッド 呼び出しの入口と出口 入口に対応するバイトコードはないが 、メソッド 本
体の先頭がこれにあたる。出口には    バイトコード（ 命令コード： ）が該当する。

メソッド 本体の先頭ではなく、! !  のような、メソッドを起動する
バイトコード を対象とする方法もある。しかしこの方法には追加するコード
量がより大きくなるという欠点がある。また、変換していないクラスファイルのメソッド 呼び出し（ 例えばシステムライブラリの呼び出しなど ）までがタイ
ムスタンプ更新の対象となり、オーバヘッド を増加させてしまうという欠点もある。
条件分岐 バイトコード の仕様として上向きのジャンプが起こりうるので、以下の 
命令を対象に含める。 C（命令コード： ）から  $ （命令コード： ）までと、
（ 命令コード： ）、 （命令コード： ）が該当。
無条件ジャンプ '（ 命令コード ： ）と ' （ 命令コード ：

）
。

、
その他の制御ジャンプ （ 命令コード ： ）と  （ 命令コード ： ）（ 命令コード ：  ）が該当。
例外 例外に関するバイトコード には   （命令コード：  ）があるが 、これだ
けでは I!.0$4 のような、ユーザのコードが明示的に   しな
い例外に対処できない。よって、例外を発生（ ,! ）する場所ではなく、例
外を捕捉（ $$, ）する場所を対象としなければならない。タイムスタンプ更新コード は  ブロックの先頭に挿入する。

  にはデバッギに組み込んで同一プロセス内で動作する  !" と、デバッガとして外部プロセスで動作する " が定義されており、 !" で実装した場合はデバッガとのプロセススイッチは発生しない。しかしながら、現在の  による # の実装では  !" と " を同時に利用することができず、 !" で実装したタイムスタンプ機構と通常利用されるデバッガ  を同時に起動することができなくなる。

第章





および  への実装      ($ $
!  '   
  B   B    !"  

図  > ($ $ クラス'  ($ $ """ )  ($ $'  ($ $ $ 55!  ($ $ 

図  > 追加されるバイトコード
これらのうち、条件分岐と無条件ジャンプ、その他の制御ジャンプでは、各バイ
トコード はジャンプ先の番地をオフセットとして引数に保持している。これが負である場合（ 上向きジャンプの場合）に限って更新コード を挿入する。



タイムスタンプ更新コード($ $ クラスは図  のように定義されている。また、追加されるタイムス
タンプ更新コード は図  のようである。図中の 55 は制御ジャンプを起こすバイト
コード（ !  の直後のバイトコード ）の位置を示す。





への実装



表 >  におけるオーバヘッド/$,+!D, "8!

+4? 4  $+4!##  E##- +4-



E$D

, "8

!#!+-!

!#!+- 







A

AB









A

B

AB





 







A

B

A B











 A

B

A  B

A

B

AB











A

B

A B











AB





B


A

B

単位は秒（ 括弧内は比） クラスファイル変換プログラム
クラスファイルを変換するプログラムはバイトコード 解析ツール /.:( , ) を用いて  で記述し 、コード 量は  行程度である。このプログラムはタイムスタ
ンプ更新コード の挿入に加え、関連するフィールド 名などをコンスタントプールに追加する。
ユーザは、タイムスタンプによる実行制御の対象としたいコード を含むクラスファ
イルを、事前にこの変換プログラムで変換しておく。実行制御の対象としない場合
は変換しなくてよく、その分、実行時のオーバヘッド を減らすことができる。

 オーバヘッド
タイムスタンプ機構を組み込んだ  プログラムのオーバヘッド を計測する。対象のプログラムには 、オーバヘッド が最大になる空ループ のみを持つプ ログラム
（ +4? 4 ）と . &' () のベンチマークプログラムを用いる。また、計測を行った環境は +5""" '2; 、 '/ メモリ、:05 、 <5 である。
実行時間の計測は各ベンチマークを 回連続して実行し 、最短と最長の結果を除外した  回分の平均を求めた。結果を表  に示す。+4? 4 は最悪の場合を示しており、この実装方式での速度低下はたかだか  倍程度であると言える。しかし概ね  倍から  倍程度であり実用に耐える。

第章





および  への実装

表 >  におけるファイルサイズ増分/$,+!D!

+4? 4 

  $+4!##  E##B

A B





 

A

B

AB 

- +4-

E$D

B

 
A B

 



A

B

A B  



A




A

A


!#!+-B
A

B

A B 
AB

単位はバイト（ 括弧内は比）クラスファイルの大きさの合計を比べたものを表  に示す。元のファイルが極端に小さい空ループの場合に増分がやや顕著になるものの、多くの場合においてほとんど 変化がなく実用上の問題はないと考える。



第 章

実行点の応用：デバッグパター
ンの実装を用いて、実行系列中の任意の  点を特定できるようになった。これを用いた応用は  種類に大別できる。 つは人間が手動で行っていた手続きを自動化するような応用であり、もう  つは、それをさらに進めて、手動では到底できないよ
うな手続きを行うものである。これらはひど く乱暴な手法に見えるかも知れないが 、
近年の高速な計算機を利用することで、人間が手動で行うよりもずっと効率良くデバッグを行うための有用な手法である。
4#

 実行点の印づけ
通常のデバッグにおいてバグの原因である場所が曖昧にしか分かっていないとき、その場所の手前に（ 静的）ブレークポイントを設定して制御を移動し 、ステップ実行を繰り返し行う、という方法で制御点を動かす。大規模なプログラムの中をこの方法で移動していると、うっかりコマンド を間違って問題の場所を通り過ぎてしまうことがある。このようなときには、そこへ至る経路を覚えておくか書き留めるかしておき、デバッギを先頭から再実行してその経路を手動で追いかけなくてはならない。
こうした面倒を避けるためには、実行点、すなわち 4# に印づけをすることが有効である。デバッギの振舞が「ここまでは正しい」というときに動的ブレークポイ
ントを用いて印をつけ、後になってやり直したいようなことがあったらその 4#
まで簡単に戻ってくることができる。実行系列の中で、いわば「足場」のようなものを確保していると言える。
さらに 、印をつけたいくつもの 4# を区別するのに 、単なる " 番号ではな
く、自分でコメント文を書くことによって識別をより簡単にすることもできる。コ
メントとしては、例えばこんなものがあるだろう。
「今、右ブレースを読み込んだので、複合文の処理をするパーザアクションに制御が移るに違いない。」

第章



head

実行点の応用：デバッグパターンの実装

size

size

next
returnvalue

next
returnvaluesize

図 > $ による領域管理 逆向きウォッチポイント
メモリを動的に確保するようなプログラムを考える。$  のようなアロケータ関数でメモリを確保するものの、プログラマは誤って、確保した領域よりも大きな
データを書き込んでしまい、$  や  が使うような管理領域の情報を破壊してしまう。しかしその破壊操作は直ちにはエラーを引き起こさず、バグの影響はずっと後になって顕在化する。配列に、その確保した領域を越えてデータを書き込んでしまうときも同様で、プログラマは後になって代入した覚えのない変数の値がおかしくなっていることに気づく。
このような不正な書き込みを捕捉するために、デバッガにはデータアクセスブレー
クポイントという仕組みが備わっており、 / ではウォッチポイントと呼ばれている。おかしな値になってしまった変数に対してウォッチポイントを設定すると、その変数に対応するメモリ領域へ書き込みが発生する度にトラップが起こり、その内容が変更されたことをプログラマに通知する。
一般には変数は何度も書き換えられるものであり、その度にトラップが発生して、プログラマはそれぞれの書き込みで何が起こったかを検査しなくてはならない。しかしながら、多くの場合、ある問題を引き起こした書き込みというのはそのバグの影響が現れた時点から時間的に一番近いものが原因になっていて、実際に我々はそれを探すことを手作業で行っている。従って、ウォッチポイントによる直前のトラップまで自動的に制御を移す仕組みがあれば 、プログラマの作業がかなり軽減されることになる。この機構を「逆向きウォッチポイント 」('8 ) と呼ぶことにする。
この手続きは動的スライシング (2 ) を手動で生成することに相当する。この手法の利点は、プログラムの制御点を、ある変数が代入された 4# に実際に移すことができるという点にある。この際、 における N$#!- 4!#O (/ )の問題は考慮する必要がない。スライシングの技術はソースコード 解析によってい
るが 、デバッガのウォッチポイントハード ウェアの支援を受けて代入に関する完全に正確な情報を手に入れることができる。



逆向きウォッチポイント

 $!" 

)
*
D
8

,    $ , D  B   )8*  )  $ , D
$ ,  ) )  $ , D',+  " '  *  $ , D  B

9
E
?
F


図 > メモリ確保プログラム



利用例

における $  のような、メモリ確保をするプログラムを考える。関数
$   は引数で指定された大きさの領域を確保し 、確保した領域のアドレスを返す。$   は領域を線形リストで管理し 、新しい割り当ては =!#5= に基づいて行う。管理のために、割り当てられた領域にはヘッダ情報として、（  ）その領域の大きさと（  ）次に割り当てられた領域のヘッダへのポインタが格納されている（ 図  ）。関数 $  は、$   で確保した領域が不要になったときに、再利用できるようにヒープに返すのに用いる。このプログラムの $ 関
数を図  に示す。
このプログラムは、最初に行（  ）で  バイトの領域を   に確保する。次に、別の  バイトを  ) に確保し（  ）、それを解放するという操作を  回繰り返した後で、再度  ) に確保をする（  ）。そして関数 ' + を用いて   に文字列をコピー（ ）するときに、 ) の管理領域を破壊する。最後に  * に領域を確保して終了する。 * が確保された後のヒープの状態は 、図  のようになっているはずであるが 、このプログラムは #+  を引き起こす。早速、これをデバッグしてみる。


第章



head

実行点の応用：デバッグパターンの実装

size
next

area1
4bytes
size
next
area2
4bytes
size
next
area3
4bytes:図 > 本来のヒープの構造バグ発覚場所の特定
このプログラムをデバッガを用いて動かすと、バグは図  の行（ ）の$   を呼び出したところでエラーとして発覚していることが分かる。これは  * に領域を確保しようとしているところである。$   は =!#5= なので、 * は  ) のすぐ 後ろに割り当てられるべきである。$   は空き領域を探すために先頭（ " ）から   をたど っていって、 ) の   にアクセスしたはずである。そこで  ) の管理領域をデバッガで調べてみると以下のように表示された。

'" 
"<G <GHI)  E89B9??8
'" 
"<G <G 
I*    J B999F ) は  バイトのはずなのにかなり大きなものになっている。しかも線形リス
トの末尾のはずが 、その次のセルがひど く遠いところにあることになっている（ 図 ）。ここに至って、何らかの操作によって  ) の管理領域が破壊されたと推測
できる。



逆向きウォッチポイント
head



size
next

area1

0x804af9c
1751606885

size
damaged?
next

area2

0x6b6a69

図 > 破壊されたヒープ
逆向きウォッチポイント によるデバッグ
そこで 、注目する領域に最後に書き込んだ操作を知るために逆向きウォッチポイ
ントを用いる。 ) の管理領域（ 0  $ ）に対して逆向きウォッチポイントを行うと、以下のような出力が得られた。

2 " !
 9EE9D)
!
 E89B9??8',+  B?BDF? " ' 'B?BDFE8? " '    D8
D8
これで、最後の操作が行（ ）で呼び出された関数 ' + 内であり、 バイ
トしかない領域に大き過ぎるデータを書き込んだのが原因だと分かった。

通常のデバッグ
もし逆向きウォッチポイントがなかったら 、このデバッグはやっかいなものになる。実行の最初に通常のウォッチポイントを設定してからデバッグを始めると、対象領域はループを回る度に繰り返し書き換えられるので、デバッギは何度も停止してしまう。そして、止まる度に表示された値が正当なものであるかを調べ、デバッ
ガに継続を指示しなくてはならない。一般にはこの停止が何回起こるかは分からないので、プログラマは大量の時間と労力を浪費することになる。

第章



実行点の応用：デバッグパターンの実装
S

W1

W2 W3

. . . Wnpass 1
pass 2
S : point where reverse watch was instructed
Wi : points where watchpoint trap occurs

図 > 逆向きウォッチポイントのアルゴ リズム



逆向きウォッチポイント の実装

逆向きウォッチポイントは前章で述べた動的ブレークポイントと既存のデバッガ
を用いれば容易に実装することができる。図  にそのアルゴ リズムを示す。


逆向きウォッチポイントが指示された 4# （ 図中の " ）に動的ブレークポ
イントを設定する。
： デバッギを再実行し 、ウォッチポイントによるトラップで停止したと
きは、その 4# に印づけをするために、動的ブレークポイントを設定するために必要な情報である A=>9 +#+4B を取得する。図中の # から# がこれにあたる。それから実行を続行する。

 4## 

制御点が逆向きウォッチポ イントを指定した 4# に到達したら（ 動的ブ
レークポイントを設定したのでこれを知ることができる）、： もう一度デバッギを再実行し 、ウォッチポイントによる最後のトラップが発生した場所（図中の # ）に、新たに動的ブレークポイントを設定してから実行を続行する。

 4## 

目標の 4# である # で停止する。

逆向きウォッチポイントはデバッガとのインタラクションが必要になるので 、新しいデバッガは .04$ モジュールを用いた ! スクリプトで記述し 、 / のラッパーとして実装した。 / は  /5 を用いた。



逆向きウォッチポイント の処理時間

逆向きウォッチポイントの処理にかかる時間を計測した。デバッギには図  に示したものを用いた。この処理時間には以下のものが含まれる。



タイムスタンプを用いた実行系列中の  分探索

表 > 逆向きウォッチポイントの処理時間
!4 ¯ ! と /

$,44#- +A+#B

A#$B





 

 



 

 



の起動時間。

¯ 4## ： #+  で停止する、通常実行パス。
¯ 4## ： 逆向きウォッチポ イントの 4## 。デバッギを先頭から再実行し 、
ウォッチポイントで停止する度に、デバッガを用いて現在の 4# 情報である A=>9 +#+4B を取得、保存する。
¯ 4## ： 逆向きウォッチポイントの 4## 。4##  で取得したリストの最後の4# まで、動的ブレークポイントで用いて先頭から再び再実行する。
逆向きウォッチポイントの処理時間は 4##  におけるウォッチポイントの停止回数に依存するので、これを  回から   回まで変えて計測を行った。計測に用いた計算機は !  '2; 、:05  であり、I@ +5 で 4#- + を計った。結果を表  に示す。
デバッギそのものの実行時間は $ コマンドで計測できないほど微々たるものであったので、表  の結果は逆向きウォッチポイントの処理時間そのものであるとみなしても差し支えない。処理時間はウォッチポイントの停止回数にほぼ比例しており、停止回数はデバッギの総実行時間にほぼ比例すると考えられるので、実用上問
題のない実行時間であると考える。
逆向きウォッチポ イントは 、特定の条件を満たす 4# のリストを取得して 、そのうちの最後の 4# に制御を移動している、とみなすこともできる。逆向き
ウォッチポイントでは 、その条件として対象の変数へのウォッチポイントを用いたが 、条件付きブレークポイントのような他の条件も利用できるし 、制御の移動先として最後の点ではなく中間点を使うこともできる。次節ではその例を挙げる。

 タイムスタンプを用いた実行系列中の  分探索
ここまでは、これまでプログラマが手動で行ってきた手続きを自動化するというものであった。ここでは、手動では到底できないような手続きを実行する例につい
て述べる。

第章



実行点の応用：デバッグパターンの実装

逆向きウォッチポイントは特定の変数に対して設定したので、その変数を監視してバグの原因を自動的に探すことができた。これに対して本節では、ある条件が成立しなくなるときの 4# を自動的に探してバグ特定を補助する仕組みとして、タイムスタンプを用いた実行系列中の  分探索（ 以下、単に  分法と呼ぶ）を提案する。
タイムスタンプというのはステップ実行カウンタをもっと疎らにしたもので、その値はプログラム実行系列中における大まかな位置を表していると考えられる。例
えば 、タイムスタンプ値が  で始まり 
で終わるようなプログラムを考えると、その値が 
になる場所は実行系列において概ね半分の位置とみなせるということである。そこで、タイムスタンプ値をキーとする  分法を用いて実行系列中を移動することで、ある条件が不成立になるときの 4# を見つけられる。
この手法については既に 8+$, ら (8 ) によって提案されているが 、本研究ではこれを関数型プログラミングの領域から手続き型プログラミングの領域に持ち込むことに成功した。
条件の例として、双方向リストを構成するプログラムがあるとすると、そのリストの一貫性を調べるためのある種のアサーションをコード 中に用意しておけば 、それが最初に偽になるときの 4# を知ることができる。例えば 、リストの先頭から順方向リンクをたど って末尾まで行き、逆方向リンクをたど って先頭まで戻ってくることができる、といったアサーションが考えられるであろう。条件の満たすべ
き要件については第  節で述べる。
双方向リストのデータ構造の一貫性を調べるアサーションであれば 、デバッギ実
行中のその真偽は、通常、真から偽へ  回変化するだけであり、偽（異常な状態）になってから復旧することはまずあり得ない。しかし 、アサーションやデバッギによっては、デバッギ実行中に真になったり偽になったりを繰り返す場合もあり得る。そのようなときでも、この手法を用いれば 、いくつかある「真から偽への変化」のうちの  つは見つけることができる。




 分法のアルゴリズム

分法を実行するプログラムは、以下のようにしてデバッギを制御すれば良い。



タイムスタンプの値が左端と右端の値の中間値になる 4# へ、制御を移動する。最初は、左端の点は実行系列の先頭に等しく、右端の点は系列の末尾に
等しい。



条件を評価し 、¯ 真であれば 、現在点と右端の中間点へ移動し 、左端の点を新しい現在点に変更して対象領域を半分にする。



タイムスタンプを用いた実行系列中の  分探索
beginning

end

step 1
0

5000

10000

step 2
0

2500

5000

step 32500 3750 5000

図 >  分法の例

¯ 偽であれば 、左端と現在点の中間点へ逆実行を用いて戻り、右端の点を
新しい現在点に変更して対象領域を半分にする。


以上を繰り返す。

この例を図  に示す。タイムスタンプ値が まで増えるプログラムを扱うとする。#4  では、 と の中間値である まで進む。条件を評価して偽であったとすると、#4  に移り、デバッギを再実行して左端（タイムスタンプ値が ）と現在点（ ）の中間点まで戻る。タイムスタンプ値が  の場所で条件を評価して真になったとすると、#4  で現在点の右端の中間点（タイムスタンプ値が  ）へと進む。この手続きを繰り返すと、指定の条件が最初に偽になる 4#
が見つけられる。

 分法と   との比較

条件が不成立になる状況とは、プログラムが   ライブラリ関数で異常終了する場合と同等であると考えられるので、 つの利点を除いては、 分法は   を用いて実行を停止させることに等しい。 分法が優れる点のうちの  つは、 は必要になるかも知れない全ての場所（ $ ）に手動で挿入しなければならな
い、という点である。 分法では手動で挿入する必要はない。もう  点は 、挿入された   はその呼び出しが起こる度に条件を評価してしまう、という点である。
 分法を用いれば 、タイムスタンプの最大値（実行系列末尾でのタイムスタンプ値）
を  とすると評価の最大回数は   となるので、条件が複雑なものであれば 、条件の評価に要する時間は  分法の方が   よりも短くなる。
 分法の処理に要する時間の大半は、条件の評価とデバッギ自身の実行時間である。条件評価は高々   回であり、デバッギ自身の実行時間の合計も  回の実行
時間の高々   倍で済む。タイムスタンプとして  ビットの符号なし整数を用い
れば 、条件評価は  回以内、実行時間は  倍以内と見積もることができ、実現可

第章



実行点の応用：デバッグパターンの実装

true

C1 false
true

C2 falset0

t1 t2 t3tn
問題発覚

図  > 単調性を持たない条件の例
能な範囲にあるものと考える。

 分法の条件の要件

分法は条件が成立から不成立へと変化する瞬間（パルス信号における立ち下がりのような瞬間）を発見する手法である。実行の過程で立ち下がりが複数存在する
ような条件を選択した場合でも、 分法はその中の  つを見つけ出すことができる。
しかしそのためには、デバッギの実行の最後で不成立となるような条件を選ばなければならない。従って  分法の条件は、立ち下がりは何回存在しても良いが 、実行の最後で不成立となる、という要件を満たさなくてはならない。
本当のバグに関連する条件がこの要件を満たさない場合、顕在化する場所を発見するには  分法を何段階かに分けて適用することになる。図  のようなシナリオが考えられる。本当のバグは条件  におけるある変数を一時的に不正な値にする（ 図中の  ）。その不正な値は別の条件  の別の変数に伝播し（ 図中の  ）、 は正しい状態に戻り（図中の  ）、 は不成立となる。 を使って  分法でデバッギを調べても、 が要件を満たさないためにその立ち下がり（  ）を捉えることはできない。しかし条件として  を用いれば 、 の立ち下がり（  ）を見つけることはできる。その 4# では  はまだ不成立となっているから、 分法の開始時の右端をその 4#（  ）にし 、 を用いて  分法を行えば  の立ち下がり（  ）を捕捉できることになる。
前述の双方向リストの一貫性を検査する条件を選択した場合、リストのセルのつなぎ変えを行っている瞬間は条件が不成立になる。しかしこの場合の不成立は過渡的な状態であるから  分法の条件評価の対象外としなければならない。従って  分法の実現には、ある関数の実行中は条件評価を行わない、というような仕組みが必
要である。




第 章 マルチスレッドプログラムへの応用
これまでは再現性を持つデバッギに限って議論してきた。本章では、再現性を持たない（ 非決定的な）デバッギに対して、前章で述べた応用を適用するための方法について述べる。

 非決定性の除去
プログラムの非決定性の要因には、外的要因と内的要因が存在する。入力を伴うプログラムではそのタイミングが決定的であっても（ 同期式入力）、入力データが変化することによってプログラムは再現性を失う。ネットワークプログラムや @"（ !4,$ @#! "!$ ）のように非同期式入力を行う場合は、入力データだけでなく、入力が発生したタイミングも非決定性の要因となる。これらの要因は全て外的なものである。一方で、マルチスレッドプログラムではスレッド 切替が非決定性の要因となっており、これは内的な要因であると言える。
こうしたプログラムをデバッグする際には $?$$ - のやり方は通用しなくなってしまうが、可能な限り非決定性を排除し 、バグの再現性を高めてデバッグするのが定石である。外的要因による非決定性がある場合には、外界の環境を決定的にすれば良い。例えば同期式入力を伴うデバッギであれば 、確実にバグが発生する
入力データを用意して入力を固定することで再現性を持たせ、$?$$ - を行う。あるいは @" を持つプログラムでは、6(&! ) のような 6 C- ?#+のイベントを記録して再生するツールを利用することで、再現性を持たせることができる。非決定性が内的要因によっている、マルチスレッドプログラムのような場
合には、スレッド 切替のタイミングを記録して再生すれば良い ( )。
本章の残りの部分では、ユニプロセッサ上での  のマルチスレッドプログラムを対象として、  を用いたスレッド 切替の記録・再生の実装方法を述べ、オーバヘッド を示す。

第 章



debuggee

VM

マルチスレッドプログラムへの応用

JVMDI - Java VM Debug Interface

back-end

comm channel

JDWP - Java Debug Wire Protocol
front-end

JDI - Java Debug Interface

UI

図

> 



の構成 () スレッド 切替の記録にはデバッグ用のインタフェースとして、 "（   "!$ ）と
&' "（  &! '$,
 "!$ ）の  つが定義されている（図  ）。
一方の  " は通常のデバッガが利用するインタフェースであり、 が提供する
  < に付属のデバッガである " はこの  " を利用して書かれた  アプリ
ケーションである。従ってデバッギとは異なる &' で動作し 、% の上でも別プロセスとなる。
他方の &' " は、デバッガのコード をデバッギを動作させる &' に組み込んで動作させるためのインタフェースである。こちらは  のような  の言語で書く必要があるが 、デバッギとは同一のプロセスで動作する。
スレッド 切替を記録する際の時間的なオーバヘッド をなるべく小さくするという立場から、&' " を用いて記録することを選択した。
&' " はイベント駆動型で利用しなければならない。また、スレッド 切替を通知させるような仕組みも存在しない。そこで、基本的な記録のアルゴ リズムは図  のようになる。






スレッド の識別図  の AB では、スレッドが同一かど うかを識別している。  を利用して取得できるスレッド の識別子には、 オブジェクトとしてのハッシュ値とスレッド名とがある。
ハッシュ値は  回の実行の間では K であるが 、もう一度実行した場合には同じスレッドに異なるハッシュ値が割り当てられることもあり、$?$$ - の手法を利用するという観点からは不適当である。
スレッド 名は 、プログラマが指定しない場合はクラス (  " のコンストラクタが呼ばれた順に数字が割り振られるので、スレッド 切替を保存すれば繰り返し実行
しても変化しない。しかしスレッド 名はプログラマが自由な文字列を指定可能であり、同じ名前のスレッドが発生することもある。

スレッド 切替の記録



バイトコード 単位のステップ実行イベントの通知を設定  イベントの通知を待つステップ実行イベント 
ステップ回数前回のスレッド K 今回のスレッド )
ログに出力
前回のスレッド ← 今回のスレッド 





図

>

スレッド 切替を &'"で記録するアルゴ リズム

ここでは $?$$ - に基づく再実行を利用したデバッグパターンを考える
ので、スレッド の識別子にはスレッド 名を用いることとする。従って、プログラマ
はスレッドごとに異なる名前がつくようにデバッギを作成しなければならない。

 ログの形式
ログにはスレッド 名とステップ実行のカウントを記録する。ログの例を図  に示す。ログは  つのカラムからなり、第  カラムがスレッド 名、第  カラムがステッ
プ数である。ログは最初の行を除いて  行の組になっている。例えば  行目と  行目
が組であり、スレッド  がステップ数  から  まで実行されたことを意味する。
ログの  行目の前には本来 $
B という行が存在しなくてはならないが 、実装の都合上、出力されない。
図  の AB に示したログへの出力では、毎回  行が出力される。 行目は図  の○印であり、 行目は図  の△印である。○印の行は図  の「前回のスレッド 」、
すなわち「実行を中断するスレッド 」のステップ実行情報にあたる。△印の行は「今回のスレッド 」、すなわち「実行を再開するスレッド 」のステップ実行情報である。

タイムスタンプ更新の排他制御の実装では、図  に示したタイムスタンプ更新コード は $!$ #$ であり、マルチスレッドプログラムでは排他制御が必要になる。排他制御の実現には、
クラスファイル変換による方法と実行時に行う方法とがある。
 のソースレベルであれば 、図  に示したように + H " を用いれば


第 章



$


$
$


$
$

F
B
8
9
9
E
)8
)9
*B

図

>

マルチスレッドプログラムへの応用

← ○
← △

スレッド 切替ログの例（ 先頭部分のみ）

+ H "($ $ 
($ $  ($ $  ($ $ 


図

>

タイムスタンプ更新コード の排他制御（ソースレベル ）よく、クラスファイル変換プログラムは図のソースコード に相当するバイトコード
列を挿入すればよい。その代わり、マルチスレッドプログラム用の変換プログラムを別途用意することになり、プログラマは  種類の変換プログラムの使い分けが必要となる。あるいは 、デバッギがマルチスレッド であるか否かに関わらず、いずれの場合でも + H " 方式の変換プログラムを用いるという方針もあり得るが 、シングルスレッド のデバッギでは多大なオーバヘッド を発生するため、やはり好ましくない。
ここでは、デバッギがマルチスレッド か否かに関わらず同一のクラスファイル変換プログラムが利用できるように、排他制御を実行時、すなわちスレッド 切替の記録時に行うこととした。よって、スレッド 切替記録プログラム（ 以下、レコーダと呼ぶ）は図  のような手続きを行う。
図の AB により、デバッギのあるスレッドが $!$ #$ に入る際の通知を起こさせる。そのときは制御が AB に移り、&' " が提供するモニタである L 4
を取得して（図の AB ）、他のスレッドが $!$ #$ に入ることを抑制する。図のAB で「残りステップ数」に設定するという数字は、$!$ #$ であるタイム



スレッド 切替の再生 ($ $ に M "%  イベント（読み込みアクセスの  ）を設定)
  イベントの通知を待つ*M "%  イベント DL 4& モニタ取得スレッド ← 今回のスレッド 
8
残りステップ数 ← ?
  ステップ実行イベント モニタ取得スレッド  今回のスレッド 
残りステップ数<<9
E残りステップ数  Bモニタ取得スレッド ← 空文字列?
L 4&





図

>

レコーダの排他制御アルゴ リズム

スタンプ更新コード（図  ）を終了するまでのステップ数である 。その後、モニタ取得スレッドがステップ実行を行うと制御が図の AB に至り、$!$ #$ の実行が終了した場合（ 図の A B ）には取得していた L 4 を解放する（ 図の A B ）。
レコーダはデバッギの振舞を大きく変えてしまうように思えるかもしれない。タイムスタンプ保護のために排他制御は導入せざ るを得ず、前述の通り、クラスファ
イル変換プログラムによるか（ 第一の方法）、レコーダによるか（ 第二の方法）の 
つの選択肢がある。図  に示した第二の方法による排他制御の動作は、図  に示した第一の方法によるそれと同じであり、本質的な差異はないといえる。
&' " のイベント待ちループは単一なので、実際には図  と図  とを組み合わせたものがレコーダの動作となる。

 スレッド 切替の再生
スレッド 切替再生プログラム（ 以下、プレーヤ ）の振舞は簡潔である。常に  つのスレッドだけを実行可能とし 、スレッド 切替のタイミングで実行中のスレッド を スレッド 切替の記録時は    は使用されないため、図 $%& の  に到達
することはない。

第 章



マルチスレッドプログラムへの応用停止させ、次に動作すべきスレッド を再開させれば良い。図  の例では、 ステッ
プ目が終了したところで $ スレッド を停止させ、 スレッド を再開させる。
プレーヤに関する本質的な部分は以上であるが 、実際には   の制約によっていくつかの問題が発生する。

 による制約

第  節で、$?$$ - におけるスレッド の識別にスレッド 名を使わざ るを得ないという制約については述べた。これはレコーダ実装時に判明した制約であったが 、プレーヤ実装時に判明したその他の制約について述べる。

$% と &'$% の排他利用 レコーダは &' " で実装したので 、プレーヤも同様に実装すればスレッド 切替が自動的に再生されるデバッギ・プロセスが実現できる。このプロセスを、 " を利用するデバッガによって制御するのがスマー
トな実装である。しかしながら、 " と &' " を同時に利用できないという
現在の   の制約によって、この方法は選択できない。そこで、プレーヤ
は  " で記述した。
前述の通り、 " ではデバッギとデバッガが別プロセスとなるため、イベントの通知は % におけるプロセス切替の発生を意味する。バイトコード 単位のス
テップ実行ごとにプロセス切替を行うのは実行効率を著しく低下させると考えられる。そこで、 " における @ L C  の ""/ M   を用いて、イベントの発生が指定した回数に達するまでは通知しないようにしている。図 のステップ目が終了した時点を例に採ると、""/ M  9 とすれば良い。
新規スレッド 開始の不定性 スレッド 生成元によって (  " が呼び出されると新規スレッド の実行が実際に開始されるが 、そのタイミングには再現性がない。従って、プレーヤは新規スレッドが実行可能状態になるまで、他のスレッド を動作させることなく待たなくてはならない。
図  のログを例にとって考える。レコーダがログを記録した際には、 行目の直前に  スレッド の開始のイベント（ (  "@&!  ）が発生していた。
しかしながら、再生の際にプレーヤが $ スレッド を ステップ目まで動作させたとしても、 スレッド の (  "@&!  が発生するとは限らない。
そこで 、デバッギとは無関係な 0" (  " スレッド（ 図  ）を作成し 、このスレッド をステップ実行することで新規スレッド の開始を待ち合わせる機構
をプレーヤに採り入れた。0" (  " に関する問題点を以下に示す。

¯ 図の AB は本来、空文で十分である。しかし空文のループをコンパイルす
ると、自分自身に ' するというバイトコード 命令が  命令だけ出力さ

スレッド 切替の再生     0" (  "  " (  "   0" (  "  0" (  "   !"       B







図

> "-8,!-の実装

れ 、この命令はステップ実行することができない。このため、ここでは無意味な代入を行っている。

¯ プレーヤがこのスレッドを動作させるために、現在の実装ではレコーダを動作させる前にデバッギを手動で書き換え、以下の  行を挿入している。

0"(  "   0"(  " 

このため、レコーダ実行時にもこのスレッド は動作し 、オーバヘッド の要因となる。

¯ 0" (  " スレッドは終了することがないため、デバッギは自ら実行を終えることができない。現在は 、実行の終了時に画面に文字を出力する
ようなデバッギを利用し 、手動でレコーダを終了させている。
¯ この解決法には重大な欠点がある。それは、他のスレッド より先に0" (  " が開始するとは限らないという点である。実際には 、先に(  " を行った方が先に (  "@&!  を発生しているが 、保証されているわけではない。
なお、0" (  " クラスはデバッグ時の実行制御の対象とならないので、バ
イトコード 変換によるタイムスタンプ機構の挿入は不要である。

 の使用 スレッド 同士が  を用いて同期を取る場合、  を実行するスレッドはステップ実行の途中（  +,- としての  の実行の途中）で停止してしまい、スレッド 切替の契機となる @ &!  を発生しない。

第 章



マルチスレッドプログラムへの応用

この問題を回避するには、  を実行して待機状態に入ったスレッド はそのまま放置して次のスレッド をログの通りに実行し 、待機状態のスレッド の が終了したら（そのスレッド の @ &!  が発生したら ）一旦実行を止めておく、という措置が必要となる。現段階ではこの機能は実装していないた
め、  を利用するデバッギは扱うことができない。同様に、(  "も正常に動作しない。

$ メソッド のブレークポイント 停止位置 プレーヤは $ メソッドにブレークポ
イントを設定し 、停止するのを待ってから、最初のスレッド 切替までのステップ実行を設定するという実装を行っている。この際、ブレークポイントで停止する場所は 、必ず $ メソッド の  バイト目の直前（ 図  の AB の直前）である。これはメソッド の入口おけるタイムスタンプ更新を終了した場所であり、 ステップ分が既に終了したところと考えられるので、プレーヤは常に、最初のスレッド 切替までのステップ数から を引かなければならない。しかし実際には、この という数値を固定させることができない。デバッギによってはソースコード には存在しないステップ実行が現れる場合があり、デバッギに固有の数値を手作業で見つけ出す必要がある。
この現象は、ブレークポイントではなく 4  "&+&!  を利用することで回避できる可能性もあるが 、現時点では未検証である。

6 +N!O4 スレッド の開始 レコーダで取得したログでは、$ スレッドが終了すると (  "&"&!  が発生する。その直後に無名のスレッドが一時的に実行され、6 +N!O4 に名前を変えて、その (  "@&!  が発生する。しかしプレーヤでログ通りに実行しても、$ スレッドの (  "&"&! は発生せず、無名スレッド も 6 +N!O4 スレッド も開始されない。このため前述した 0" (  " のステップ実行による待機が繰り返され 、デバッギの実行が進まなくなってしまう。
現段階の実装ではこの問題を回避するため、$ スレッド の最後（ $ メソッ
ド の最後）で無意味な無限ループを行い、スレッドが終了しないようにしている。
本章で実装を試みたレコーダとプレーヤは、  が本来意図していない利用法をしていると言える。これらの制約はこうした利用法に由来していると考えられる。
マルチスレッドプログラムを決定的に動作させてデバッグしたい、という要求は明らかに存在しており、次世代の   ではこれら機能の実装が強く期待される。

 デバッギ
前述したような制約を回避できるデバッギの例として 1( !（図  ）を用意した。これは  つの子スレッド、 と ) を生成し（ 図の AB と AB ）、共有



スレッド 切替の再生    !" $! '@':;
/"B' 
3E) ==M " ($ $ N*,
D
""
8
" )
9
 
3E) ==M " ($ $ N
F' 
3E8 ==M " ($ $  N
)
$
*

F
9
! 
3E? ==4  " ($ $ OF38 ==  0" (  "
))
" 
)*
!  
39 ==4  " 0" (  "G O図 >$ メソッド の先頭部分のバイトコード（ ! による出力）

変数   にアクセスする。 は   に  ずつ  回足していき、) は
  から  ずつ  回引いていく（ 図の AB と AB ）。両方のスレッドが終了したときに   は となるはずだが、  にアクセスするとき（図の AB ）に排他制御を意図的に行わないようにしてあるので、途中でスレッド 切替が起こると
  は にならない。
$ スレッド は子スレッド の終了を待ってから   を表示する（ 図の A B ）。
このような待ち合わせには (  " を利用するのが普通だが、これは 
を呼び出してしまうため利用できない。そこで、子スレッド の自身の実行が終わったという記録を別の共有変数 " に残し（ 図の AB ）、$ スレッド はそれを監視する（ 図の AB ）ことで子スレッド の終了を知る。
このデバッギは、通常実行時には幸運にも   は常に となるが 、レコーダで動作させると概ね  程度の確率で とはならない。 とならない場合のログを用いてプレーヤを動作させ、プレーヤによる明示的なスレッド 切替の記録をログと対比して、レコーダとプレーヤが正常に動作することを確かめた。

第 章

マルチスレッドプログラムへの応用  1(   " (  "      " 






1( @' $    $     




! + H "  !" " "    !"     B   BB    " )

    !" $@':; !0" (  "   0" (  " 
1(    1(  
1(  )  
1( ) <)  "  )  @+ $    


*
D
8

9
E


図

 >

1( !



オーバヘッド表>

レコーダとプレーヤのオーバヘッド（ /D8#E ）通常実行（ "8 有効）
通常実行（ "8 無効）
レコーダ（ "8 無効）
プレーヤ（ "8 無効）

表

>

¢ 

 ¢  ¢ 
 ¢ 
単位は秒スレッド 切替再生時のデバッギ（ /D8#E ）とログの諸元
実行終了時のタイムスタンプ値
ログのサイズ
ログの行数
プレーヤのスレッド 切替の回数
プレーヤの実行バイトコード 数



バイト
 行

回
  命令  オーバヘッド
レコーダとプレーヤのオーバヘッドを計測した。+5""" '2; 、 '/ メ
モリ、:05 、 <5 上で動作させ、ストップウォッチによる手動計測を行った。計測の結果を表  に示す。
 種類の通常実行は実行時間が極めて短いため、同一の処理を 回繰り返し 、
測定結果を で割ることによって表の数値を得た。従って、&' の起動時間（ 秒程度）はこれらの結果にはほとんど含まれていない。レコーダはログを =" !=
に出力する設定で 、 回分の実行時間を測定した。プレーヤは、レコーダで取得した特定のログを用いてスレッド 切替の再生を行った。その際のデバッギとログに関する情報を表  に示す。
 種類の通常実行とレコーダの動作時には 0"(  " にたびたび制御が移るが 、プレーヤの動作時には 0" (  " は新規スレッド の開始を待つ場合にしか動作しない。実際には、0" (  " による待ち合わせはほとんど 発生しない。
レコーダやプレーヤが動作する時には "8 を動作させることができない。比較のため、通常実行では "8 を無効にした場合についても計測したが 、差は現れなかった。これには  つの理由が考えられる。第一は、1(   におけるループの回数が少なく、"8 の利点があまり活かされないということ。第二は 、スレッド の生成が合計で 回行われており、:0 では  スレッドごとにプロセスが生成されるため、このオーバヘッドが十分に大きいということである。



第 章

マルチスレッドプログラムへの応用 まとめ
本章では 、ポータブルなスレッド 切替の記録と再生に 、制限つきながら成功した。現状では 、  だけを用いて完全なスレッド 切替を実現することはできず、
E&() のように &' を変更することが必要になる。しかしながら、第 節で述べた制約を受け入れられるデバッギであれば 、表  に示したオーバヘッド
で、&' の変更を要しない、ポータブルなスレッド 切替の記録と再生が可能である。
特に &' " と  " が併用できるようになれば 、プレーヤのオーバヘッドが低減し 、実装も簡潔になることが期待される。
デバッグパターンはポータブルに実装することを目指してきた。マルチスレッド
プログラムに対するパターンの適用はポータブルに行うことができないが 、本章で提示した機能が   に追加されれば 、デバッグパターンの応用範囲を拡大していくことが可能である。



第 章

各種の議論

本章では最初に、第  節で先送りにした実行点の表現形式について議論し 、次に関連研究との比較を行う。

 実行点の表現形式
第  節で、4# には他の表現形式も可能であると述べた。本節では他の表現
形式と、本研究で採用したタイムスタンプ方式との比較について述べる。
ステップ実行の回数 ステップ実行はデバッガで制御可能な最小単位の実行を実現する。従ってこれを繰り返せば完全な実行系列を得ることができる。第  章の  つの応用は 、この表現形式を用いても実装可能である。/,(/ ) のデバッガはこの方法でステップ実行単位の疑似逆実行を実現している。しかしながら速度低下
はおよそ   倍となっており、これを補うためにチェックポイントを併用している。
デバッガコマンド 履歴 デバッガコマンド の履歴を再生すれば 、行った実行制御を再現して同一の 4# に移動できる。この表現形式では 4# に順序関係がな
いため、以前の実行で訪問した 4# に対して現在の 4# が（実行系列中で）前であるか後ろであるかが分からない。
「あの実行状態」に対する時間的な前後関係を把握することは、デバッグ作業では重要なことである。この順序性の欠如のため、
 つの応用のうち、 分法を実現することができない。
また、 つの 4# に対して複数の表現形式が存在することになる。例えば図 のようなデバッギを考える。      と     は共に AB の行に到達したときの 4# を表現する。よって以前の実行で訪問した 4# と
現在の 4# とが同一であるかど うかを知ることができない。
実行速度に関しては、この表現形式の方が優れる場合も存在する。図  のようなデバッギを考える。回数が非常に多いループがあるが関数  の行 AB に注目したいという場合、コマンド 履歴では     などとなり、興味のないループに関しては通常速度で実行することができる。一方、タイムスタンプ形式では興味ないループであってもタイムスタンプのインクリメントによって実行速度は低下する。コマンド 履歴形式のオーバヘッド を見積もることはできないが 、長い履歴ほど 高いオーバヘッド を発生させることは間違いない。

第 章



各種の議論

     B
$
  B
  



図

>

コマンド 履歴形式における同一 4# の複数表現の例

     B
$
  B   BBBBBBBB 





図

>

コマンド 履歴表現形式のデバッギの例



逆実行



ブレークポイント のヒット 回数 タイムスタンプの本質は重複して実行される $5 を区別することにある。デバッガはブレークポイントのヒット回数をカウントしており、これを利用すれば特定の $ に関してだけは全順序を持った 4#
が定義できる。しかしブレークポイントの設定を実行の途中で行った場合には、5$ の登場回数を正しくカウントしたことにならないので、再実行時に最初からブレークポイントを設定してもヒット回数が食い違ってしまう。このため、対象とする $ には実行に先だってブレークポイントを設定しなくてはならないが 、どの $ を対象とするかを事前に決めることは難しい。従って、ソースコード の全ての行に予めブレークポイントを設定することで 4# を表現することになる 。
これは明らかに現実的な方法ではないし 、ステップ実行と同等のオーバヘッドが発生する。また、この方法でも 4# に順序性がないため  分法は実現できない。
以上をまとめると、タイムスタンプによる表現形式には以下のような利点があると言える。
全順序性 全順序性を持ち、任意の 4# は他の 4# と時間順（実行系列における登場順）で比較することができる。この性質を利用して  分法が実現できる。

(  つの 4# の表し方は  つしか存在しない。4# と実行点の印
づけは  対  対応となる。
パフォーマンス 多くの場合、最も低いオーバヘッド で 4# を実現する。

 逆実行
本節では多数の逆実行の研究の中で、本研究と関連が深いと思われるものとの比
較を行う。



状態保存方式ら (*/ ) や ',!(', ) 、C# ら (C' ) はメモリの完全な履歴を保存することで 、プログラムの任意の実行状態にアクセスできるようにしている。
これらのシステムは巨大なログを扱わなければならない。本研究の方式ではデバッ
ギの再現性を仮定すれば 、行番号とタイムスタンプ値の組を保存するだけで同等の機能を提供できる。また、この仕組みは本研究との併用が可能であり、タイムスタ
ンプ方式のオーバヘッド を抑制することもできる。
*-+

 実際には空行やコメント行、変数の宣言など 、デバッガでステップ実行の対象とならない行にはブレークポイントは不要である。

第 章



図

表

> G4 (:*> !# #+

各種の議論

)

の例 (/')%! +"!# +  
     < 
<< < << < ら (:* 9 : ) は G4  を開発した。これは :#4 用の、逆実行可
能なアニメーション機能つきのソースコード ステッパーである。そのインタプ リタ
は完全な逆実行のために、:#4 プログラムの  式の評価順序を保存している。また、あるグラフィック出力をクリックすると、それを出力した 4# に制御を移動する機構も持っている（ 図  ）。本研究のシステムも、グラフィック出力が行われる
際にそのオブジェクトと 4# を結びつけて保存しておくことで同様の機能を提供することができる。タイムスタンプ機構は複数の言語に対応でき、小さいオーバ
ヘッド で実行できるが 、G4  のインタプリタは :#4 のサブセットしかサポートしておらず、動作も非常に遅いとされている (:* )。
/# # ら (/') は、逆演算を行う !# #+ を用いることで静的に推測できる情報は保存を行わないようにしている。!# #+ の例を表  に示す。!# #+ では、   のようなステート メントでは元の値を復元する
逆演算を定義できないので、変数の値を保存せざ るを得ない。ソースコードがない
ライブラリ関数の呼び出しが起こる時は、どの変数の値が変更されるかが分からないので、全ての変数を保存するとしている。また、条件分岐やループなどで制御が不連続にジャンプするときには、行番号を履歴として保存する。文献中には保存される履歴の量に関する記述はないが、実用的なほどに小さくなるとは考えられない。
:!+

イベント駆動型実行制御
表> /,の方法での順方向コマンド のオーバヘッド (/$++-

#

-

)



#4

 

$

 

0



=#,







数値は比



疑似逆実行方式

はステップ実行のカウンタと再実行を用いて、疑似逆実行する機能を持った  デバッガを開発した。/, は完全な !!# -! の実現を目指したので、直前のステート メントに容易に「逆向きステップ 」するためにステッ
プ実行のカウンタを必要としたが、4# の目的はプログラム実行系列中の  点を特定することなので、ステップ実行カウンタはオーバスペックである。また、ステッ
プ実行カウンタはデバッギの完全な実行系列をカウンタの形で保持していると考え
られ 、動的な情報だけで構成されている。本研究で提案するところの 4# は動的な情報であるカウンタの値だけを用いるのではなく、静的な情報である $ 、
すなわち A=>B と組み合わせることにより、低い更新頻度を実現したと言える。
実際、/, の方法では、最もオーバヘッド の少ない順方向のステップ実行でも 倍近くの時間を要している（ 表  ）。こうした高いオーバヘッド を抑えるため、状態保存方式を併用している。
/,(/)

イベント 駆動型実行制御

実行制御をソースコード のステート メントを単位として行うのではなく、代入や関数呼び出し 、ループなどをイベントとして扱い、イベントを単位として実行制御を行う方法がある。この実行制御を利用したデバッガである $( $ ) については第  節で述べたのでここでは繰り返さない。
イベント駆動型実行制御を行う際には、代入やループの実行などを識別するために本来のコードに追加コード を挿入するのが普通である。このような目的で行うコード の追加を #!+ という。本研究では第  章で述べたように、 ではコン
パイラ中間コードで、 ではバイトコード（ クラスファイル ）で #!+
$- を挿入した。ここではその他の挿入方法を採用する研究について述べる。
8+4! ら (8
9 G8/) はイベント型の #!+  である " を開発した。これはデバッグやプログラム理解、パフォーマンスの向上のために用いられる実行モニタリングシステムで 、 のソースコード を変換することで実現する。

第 章

各種の議論

1  0 $     %  0 $ 
&O&,@ ,(,&O&,L P
&O&,%'J,(,,(,B&,L P
&O&,L P
&O&,%"",(,B,(,BJ,(,)

図> "における #!+ $- の例 (8)変換によってコード は図  のようになる。& %' や & %"" は加算や代入のイベントを表し 、計算の経過をこれらのイベントに渡すため、一時変数 ( に代入している。ソースコード を対象とするため変換されたコード はプラットフォーム非依存であるが 、実行速度は    の場合で  倍、   の場合で   倍となる (G8/ )。図中の例のように代入や加算も独立したイベントとして扱うため
で 、4# システムを実現するのであれば制御フローに関するイベントだけを生成するように " の設定を変更すればよい。本研究では既存のソースレベルデバッ
ガを用いてきたプログラマが容易に移行できるように、プログラマが目にするソー
スコード は元のままであることを重視したため、ソースコード を変換の対象としなかった。
:!# ら (: ) はデバッギを解析、変更するツールのためのライブラリである ..:を作成した。..: を用いれば 、タイムスタンプ機構を実行コードレベルで挿入することもできる。しかしながら、この方法では特定のプラットフォームに依存することになるので、本研究では中間コードレベルを選択して  を変更した。

    
ら (': ) は $D !- !$, と $ $ で更新されるカ
ウンタ（ " ）を提案し 、プロセッサのプログラムカウンタを用いて A9 "B として、本研究の実行点と同等のものを表せるとしている。また、,!- ! #44!
がない環境でのウォッチポイントと疑似逆実行の実現方法について述べている。しかし 、" は実行系列中にまばらな目盛りをつけるためだけに使われており、関数呼び出しの出口で更新されないため実行点の表現として利用することはできない。
'!5!++?





  プログラマが行う作業を自動化するものとして、  (2G 9 G ) がある。これについては第  節で述べたので、ここでは繰り返さない。

 
は ;?  5$$# の中に N$$!!$#O を導入した。;?
 5$$# では !-$ の過程で部分木のコピーを生成していく。例えば 、ある式 が +- 関数  H に適用されるとすると、 のコピーが  つ作られて、H の  つの被演算子に使われる。
このことは、プログラムの実行時に単一の $ に対応する複数の 4# が（実行系列の中に ）生成されることと同じと考えられる。/! は、ある式にブレー
クポイントを設定したとき、その式のコピーが評価された場合にも実行が停止する
ような機能を開発した。
手続き型言語では 、このような $ と 4# の識別は極めて容易である。
なぜならば 、ある命令が配置されたメモリ上の番地がブレークポイントとして利用されるからである。/! の目的は複数の 4# を（ 元となる）単一の $
に帰着させることである。これに対して、本研究で提示したタイムスタンプ方式のプログラム実行点の目的は、複数の 4# に分散してしまう単一の $ を区別することである。
/!(/! )

アスペクト 指向プログラミング

オブジェクト指向プログラミングでは、あるデータ型のオブジェクトにアクセスするコード を、そのデータ型の定義と共に書く。これによってアクセスするコードの分散を防ぎ 、保守性を向上させている。
アスペクト指向プログラミング (<:' ) では、本質的に分散せざるを得ないコー
ド をアスペクトとして定義することにより、コード を ヶ所に集約することができる。例えば 、メソッド の出入りに関するログを出力しようとすると、そのためのコードはあらゆるメソッドに分散してしまう。そこで、そのログ出力のためのアスペクトを定義し 、ログ出力コードはアスペクト定義部にだけ記述して、各メソッドには記述しない。そしてアスペクトの処理系を用いて、各メソッド の出入口に自動的にログ
出力コード を挿入する。 のためのアスペクト処理系の  つ、#4$(<22 )
では、 というコンパイラで  ソースとアスペクトの定義をコンパイルする。
第  章で述べたタイムスタンプ機構の挿入は、プログラム実行点に関するアスペ
クトを定義して、 と  に対して異なる方法で実現したと考えることができる。
#4$ ではループの際の制御ジャンプを指定することができないので、現段階で

第 章は  への実装に利用できない。

各種の議論



第 章

結論

本研究では、ソフトウェア開発における最終的な誤り修正工程であるデバッグ工程の中で、プログラマが行っているデバッグ作業の分析を行い、プログラマの行動が「仮説検証ループ 」によって説明できることを示した。このループにある検証方法とその実施には典型的なパターンがあり、これをデバッグパターンと名付けて自動化することを目指した。
一般的なデバッグ方法である $?$$ - においては 、プログラマは往々にして少し前の場所に戻りたいと考えるものであり、逆実行と呼ばれる研究領域がある。これもデバッグパターンの一種として位置付けられる。そこで研究の初期段階として、既に提案されていた関数単位疑似逆実行をより高速化した。
これ自身は有用であるが 、より多くのデバッグパターンの自動化に応用できる、汎用の基盤技術をポータブルかつ高速に実装することが必要となった。その基盤としては、プログラマがデバッグ中に持っているプログラム実行点（ 4# ）という概念がふさわしい。この表現形式としてタイムスタンプ型を選択し 、 ではコンパ
イラ中間コード でのプログラム変換を、 ではバイトコード でのプログラム変換を用いて実装した。4# を利用して自動化されるデバッグパターンとして、「実
行点の印づけ 」と「逆向きウォッチポイント 」、「実行系列中の  分探索」について述べた。
以上の議論はデバッギの再現性を仮定したものであった。本質的に再現性を持たないデバッギである  のマルチスレッドプログラムを対象として前述の自動化を実現するため、スレッド 切替を記録、再生することで再現性を持たせる方法を検討して実装し 、小さなアプリケーションでその再現性を確認した。
以下では、本研究の意義と展望について述べる。

 本研究の意義
第  章では、デバッグは仮説を立ててそれを検証するという仮説・検証サイクル
によって成り立っていると述べた。そこで、デバッグ作業を、第一段階としての仮説設定フェーズと、第二段階としての仮説検証フェーズに分けて考える。効率的なデバッグとは定められた時間の中でこの二段階サイクルの回転数を上げることであると言える。
仮説設定フェーズはそのバグに固有の情報を検討する必要があり、パターンは存



第 章

結論

在するものの、それを発見して適用する過程では人間の知性が不可欠である。一方、仮説検証フェーズにはよりはっきりしたパターンが存在する。例えば逆向きウォッ
チポイントのように、最後に代入したオペレーションを見つけ出す、といったものである。これまでこの  つが分離して考えられて来なかったのは、デバッグの結果（バグの原因、すなわちデバッグ時の仮説）のみが示され、その過程については注目されてこなかったからである。しかしながら、その過程にはプログラマの知識と経験が豊富に含まれている。
本研究は誤りを修正するというデバッグ作業の過程に注目した。これにより、熟練のプログラマが行うデバッグ過程を自動化して作業時間を短縮することで仮説・検証サイクルの回転数を上げ、デバッグ効率を向上させるという直接的な効果を得た。また、今までのデバッグ作業はその場限りのものであったが 、デバッグ作業の再利用も可能となった。のみならず、熟練プログラマの技術を自動化という形で浮き彫りにすることで、それを他人、特に経験の浅いプログラマに供することができるようになり、知識や経験を共有する基盤を提供することに成功したと言える。
オブジェクト指向言語の設計では、クラスの用途に応じてどのような階層化と分離を行うべきかというノウハウがプログラマの中に蓄積されていた。これを体系づけて形にしたものがデザインパターンである。本研究で抽出したデバッグ作業の過程もプログラマの中に蓄積されていたものであり、逆向きウォッチポイントなどはデバッグパターンと呼ぶことができる。デザインパターンが今日広くプログラマに利用されているように、デバッグパターンも幅広いプログラマが利用可能なものである。ソフトウェア開発の現場にいる職業プログラマは前述の熟練プログラマであり、彼らにとっては労力の削減という恩恵だけでなく、作業時間の短縮によって次々と頭に浮かぶ様々な仮説を検証する機会を得ることができる。趣味としてフリーウェ
アを開発するような日曜プログラマとでも呼べる人々にとっては、作業時間の短縮だけでなく、より上級者が使う高度なデバッグパターンを習得できる。教養課程の学生のような入門教育を受けているプログラマにあっては、デバッガの繁雑な操作に振り回されることなく、デバッグ作業の本質を学びとることを可能にする。

 展望
デザインパターンでは  のパターンが示されている (2& )。デバッグパター
ンを有用な技術として確立するためには、何よりも多数のパターンを収集することが重要である。デバッグ作業をしているプログラマが自らの作業記録を残していくのが最善だが 、多くの場合は時間に追われており、そのような余裕はないと考えられる。そこで、パターン収集のために、6 におけるペアプログラミングをデバッグにも応用してペアデバッギングを行うのが有効だと思われる。すなわち、デバッグ作業を主に行うプログラマと、その作業の本質を確認して記録に残していくプログ
ラマの  人をペアにする。ペアプログラミングの有効性と同じ理由で、デバッグ作



展望



業そのものを改善することも期待できる。
デバッグパターンの収集と再利用を通じてデバッグ作業を分析するという動きが広がれば 、作業の第一段階である仮説の立案も研究の対象となることが期待される。
デバッグパターンのような自動化をすることはできないと思われるが 、場当たり的なものとして考えられがちなデバッグ工程を分析することを通じて、従来のソフト
ウェア工学のアプローチとは違う側面から、できる限りバグを回避するコーデ ィン
グが促進されることを期待する。



参考文献
(2

)

2! !

(/$

)

 - #4, 1 2!

?+$ !!+ $"                   9 44 9  < /$D!   

!" #    --#

長瀬訳：6 エクストリーム・プログラミング入門9 ピア
ソン・エデュケーション A
BB
C#?9     $              9 44   9  (/! )M# /! %$$!$# (/ )(/'(! 4$=$# "- C /D? - <, /! ,! !!+ $   9 & 9 44  9 

)

(/

 A

)

)

/ /#

# - 1 ' 1!# .0$  !!+#  9 & 9 I 9 44  9 

%



                   9 44   9  / /, .Æ$ !,+# ! /-!$5

D , - 2! !# "!+#$ 14?      &' (      #  & 9 44   9  ',!-- 44$# "

(

,

)

'!D#

,+$*)&+9 /? - .!

")%  & ,4>LL$#!$!L

(

$

)


 $        ,   9 44  

'!



9 

$##F $>  +-! !  "

第 章



遠藤知宏 動くべくして動く -. / 9 &  9 I  9 44
 
9 
 A連載：プログラマーの理想と現実 第  回B

(.- )(*/)

! " *-+ - , / /!

 "%1>  ?#+ ! !5     0 12      #  #  9

!+

(1

結論

)

  1!# .0$

"

44 9 # !,!9

 !9 - 8- 1#%#!#  "5   $3
       ,   9 44 9  -#! !$$ @# *!+ ',-#(2& )".!$, ++9 1$,!- 2+9 14, ,#9 - , &##-#     --# C#?9 

本位田・吉田監訳：オブジェクト指向における再利用のためのデザインパターン 9 ソフトバンク A BB
(2G

)

 A

1 2-!- - -!# G!

+4? *!5"-$ "5    04&    (   , &   (  *&5+9 44 9  
4 "           6 4 ( 7 6  /6    %0!- @!#? !## "$9  ("$ )  "$

石井康雄（ 編） ソフトウェアの製造9 日科技連ソフトウェア品質管理シ
リーズ 9 第  巻 日科技連9  ("#, )(G8/) : 3!?9 C? G,9 < 8+4!9 - '$, /!;     12     (    , &   9 44   9  

:,



(<22

, !$,$! ! !!+ .0$ '!

) !! <$;#9 .!D 2#-9 + 29 'D <!#9 3!? +9
- C+  !#-  9 & 



(<:'

"

) !!

<$;#9, %!

 #4$

9 44  9 :+49!

    '-,D!9

!# :4#9 5'!$ :!9 - , "!

,!#'-9 #4$5%!-       0#8 0    * 00+9 44  9  

!!++

(<

)

"

/! C <!, - 1 D&        -5-# C#? :+9 "$9 

福崎訳：プログラミング作法9 アス

キー出版局9 A

BB

 A



(:*

展望
)

2!?

:!++,-!$

,!#4,!

-44!

+ - '!$ /!

*!?
"

9 -!#9

G4/

>
!$

)

,

#D9

4





2!? :!+ 1!# %E$5%!- "!4!!#    0#8 0    9 

(:)

:

,4>LL(: )-     M

1!#9 , 9 : "      ! '"8 !##9 

(:





! ; 

#$!L@'/1.::C./&L 4$,-L-0,++# 1 :!# - .!$ $,!!

..:> '$,5"-4- .05     3              9 44   9  $ .- "(:M)

8+ :-,+ - *!D M&  )% 9    7 *5  + --#5C#?  9    '$!# !##9 ('$ )石川訳：
コード コンプ リート 完全なプログラミングを目指して 9 アスキー出版
局9 A BB(':

 ' '!5!++? - 8  :/$) '$

44

)

! "#!$" 9 



8,+#  ',! .!+I 9 44

(';)

A

                      0  (  9!

(',    9 

1%&"

5

&     ,   9 & 9

8, '; %!;
,4>LL.>  !$## &#; -; : 8 ;!L

('8

)

丸山一貴9 寺田実 タイムスタンプを用いたプログラム実行点のポジショ
ニング  情報処理学会第  回全国大会講演論文集9 


('8

)

丸山一貴9 寺田実 関数単位疑似逆実行の高速化 情報処理学会論文誌 プ
ログラミング 9 & 9 I " A1% B9 44  9 


('8 )<;D '!?+ - '! 8!-

, 1!#   &       < (  , *<5=+9 44 9  C$,4

"

第 章
('8 )結論<;D '!?+ - '! 8!- 8+#+4 /#- .0$

   4  
 12      #  * ;-5=+9 44 ! !  -  !!+# " 9 

(1/-<

)



'$, 1##9 < /##$,!9 - $K# ,## - <!+5    
 12      #  * ;-5+9 44  9+0 .0$ !4? - - "



(1#

)



, / 1#!

吉川訳：デバッガの理論と実装9 アスキー出版局9 A



(



)

 A

/ #!$ !B

8,-!-; 2 )!!+$. !4!

#4$!L#LE+

1$,!- ' +*! ()

#  , ; 9   A$-- ? &  - % #  ? ,4>LL(BB

1$,!- +9 1- #$,9  ,#9  



()

>, #  12 , C? P #9 "$9L-    

! *-9  '$!#?#+#9 "$  )9@ -   

 A$--   #!$ !B; 

,4>LL-4!E#$+L-4!L!-L-0E#,+()

 '$!#?#+#9 "$

)%   #     ,4>LLE#$+L4!-$#LE4-L(8 )

-!

8+$, - -!C 44 ! ! -!- ':)  4    9 & 9 I 9 44 

9 



(8!

)

寺田実 気くばりデバッガ  中島秀之（ 編）9 秋のプログラミングシンポ
ジウム「日本のプログラミング 」報告集9 44  情報処理学会9 


(8!

)

寺田実 デバッガのためのプログラム疑似逆実行方式 情報処理学会論文誌9 & 9 I 9 44   9 


(8,)

8,! :!,+,4>LL-    (  

40$+L!,+L4$,-L（ 現在は閉鎖）



(8

展望
)

<  8+4! -  : 3!?

             ,   9 44   9"#!+ 8 ! I" 



(&!

 =! +$

)

"



'!$ &!#

6     + !4,$ #! !$#! 12( , 9 '? ",4>LL+!#!!L(C')

 1 C# - 8,+#  ',!+$ '+!? ! !$##     @              9 44  9  

2#!# "

(G )-!# G! "# #5.3$ ,# !+ +4! !!+#   04& $    (   
4    ,   *4 $+9 44  9  
"



謝辞
指導教官の廣瀬通孝教授には、研究全体を見通す立場から重要なご助言を賜わりました。心よりお礼申し上げます。
電気通信大学の寺田実助教授には、学部  年から博士  年までの間、指導教官としてご 指導いただき、本論文に関する様々なアイデアやご 指摘をいただきました。
深く感謝致します。
@!#?  80#  . # の I C!- 助教授には、寺田助教授とは異なる視点から貴重なご指摘、ご批評をいただき、大変有難く、感謝致します。
大津・國吉研究室の永井おりが技官には、研究における事務手続き等にご尽力い
ただき、有難うございました。
また、東京大学の近山隆教授、稲葉雅幸教授、田中哲朗助教授、広田光一助教授には、予備審査において有益なご指摘を多数賜わり、論文の改良に役立てることができました。
東京大学 工学部 機械情報工学科 寺田研 卒業生の東京大学インテリジェント・モ
デリング・ラボラトリーの立山義祐氏、電気通信大学の塚原渉氏、株式会社日立製作
所の小林広和氏には、研究室輪講や勉強会などでご指導、ご意見をいただきました。
同卒業生の首藤達生君、樋口直志君、須山哲宏君、副田俊介君、西本圭介君、林芳樹君には、研究を進めていく上で率直なご意見と惜しみないご協力をいただきました。
電気通信大学 電気通信学部 情報通信工学科 寺田研 学部生の五十嵐知久君には、
ソフトウェア開発の現状についての知見を教えていただき、研究に役立てることができました。同学部生の高木一人君には、貴重なバグの例を供出していただきました。
以上の皆様のおかげで、本研究を進めることができました。ここに謝意を表した
いと思います。
最後に、ここにお名前を挙げきれなかった研究室の皆様と、情報工学輪講や情報処理学会プログラミング研究会など 、研究発表の場でご助言を下さった皆様に、心よりお礼申し上げます。



発表文献一覧
論文誌（ 査読あり）¯ 丸山 一貴9 寺田 実9 N関数単位疑似逆実行の高速化O9 情報処理学会論文誌 プロ
グラミング 9 &9 I" A1% B9 44 9 ¯ 丸山 一貴9 寺田 実9 Nクラスファイル変換による  プログラムの実行制御O9
情報処理学会論文誌 プログラミング 9 &9 I"A1% B9 44 9

国際会議（ 登壇発表・査読あり）¯ <;D '!?+9 '! 8!-9 N8+#+4 /#- .0$ !
!  -  !!+#O9#,4  ++9 4+!

!$-#  , *, "! C!D5 A

 9 

./@

B9 44 9 ,9 /5¯ <;D '!?+9 '! 8!-9 N

, 1!# C$,4O9

!$-#  , 8,!- "! !$  Q? 449

#9 80#9 @9 I+!  9 

! AQ"

国際会議（ポスター発表・査読あり）¯ <;D '!?+9 '! 8!-9 N# 4$=$  !!+ 8!$#-  44$#  +5+-O9 - 1#!$,*!+9 , ' ":I R  !$  !!++ :
- "+4+ A:"B9 

!-9 @,9 @9   9 

#



国内口頭発表（ 査読なし ）¯ 丸山 一貴9 寺田 実9 Nタイムスタンプを用いたプログラム実行点のポジショニ
ング O9 情報処理学会 第  回全国大会9 愛媛大学9 
年  月  日B9