Delta Debuggingの紹介

開発者なら誰でもデバッグ――プログラムコード内の不具合を見つけて修正する作業――が重要な工程であることを知っている。デバッグに徹した取り組みが、ソフトウェア開発のほかのどの工程にコストをかけるより重要な場合も多い。一つのバグの原因がわからないために開発者が長時間かかり切りになることもあり、デバッグ作業は予測不可能だ。しかも不幸なことに、これまでのデバッグはたいてい手作業だった。だが、それもDelta Debuggingの登場によって変わろうとしている。

現在は、デバッグ作業の工程のうち、部分的にでも自動化の恩恵を受けている工程は、ほとんどの場合、バグの存在を検出するテスト工程だけだ。gdbのようなデバッガツールもデバッグ作業の役に立つが、それもプログラム実行の検査と制御を行う受け身のツールに過ぎない。

ドイツ、ザールラント大学のAndreas Zeller教授のグループが開発したDelta Debuggingは、問題の原因を特定する作業を自動化、体系化する技術だ。この原因の特定作業こそ、手作業では、最も時間がかかり、繰り返しの多いうんざりする作業である。

foo.txtという入力ファイルを渡すと必ずクラッシュするプログラムがあるとしよう。プログラマはfoo.txtの何がいけないのか知る必要があるので、普通は、そのファイルを細かく分けて、とにかくプログラムが正常に実行されるまで再試行する、という退屈で機械的な作業から始めることになる。この試行錯誤によって、最終的には問題の原因がどこにあるかが判明する。

Delta Debuggingはこの作業を自動化する。問題の原因となる入力ファイルを渡すと、それを入念に加工した入力ファイルを使って、新しいテストを繰り返し実行する。最終的には、よく似ているが、問題が発生するものと発生しないもの、2つのファイルを返す。

この革新的な技術の実効性は、多くの実際の環境で証明されている。たとえば、Mozillaには、ある非常に大きなWebページを印刷するとクラッシュするというバグがあったが、このバグを絞り込むのに役立った。一つのselectタグが直接的な原因だった。

このような問題追跡機能だけでも画期的で、IDEにうまく組み込むことができればバグ探しにかける時間を大いに節約できるだろう。だが、Delta Debuggingはそれだけではない。

Delta Debuggingをインタラクティブなソフトウェアのテスト・フレームワークに統合すれば、マウスクリック、キーボード入力などのユーザ操作も、入力ファイル同様簡単に処理できる。これによって、オープンソースのバグ追跡システムにもたくさんある、膨大なバグレポートを単純化できる可能性は大きい。開発者は、バグテストのテストケースを最小限に抑えることができればかなり助かる。ダイアログにある値を入力したり、あるチェックボックスを選択したりすると問題が発生する、と報告されるよりも、Delta Debuggingアルゴリズムによって、あるチェックボックスが問題の原因でそれ以外は関係ない、と自動的に特定される方がずっと便利だ。

Delta Debuggingは、コードに直接適用することもできる。同じアプリケーションでも、あるリリースやリビジョンは問題なく動作するのに最新のものでは問題が発生するという場合、2つのリビジョンのソーソコードを基にDelta Debuggingアルゴリズムを適用できる。Delta Debuggingは前述と同様の手順によって、コード変更のさまざまな組み合わせを反復実行し、問題の原因となっているコードの相違点を突き止める。Delta Debuggingが誕生した1999年以来、この手法は、何万行もの変更を伴うdddと2つの連続するgdbリリースの統合の問題を修正するのに役立っている。

Delta Debuggingの適用の3番目は、マルチスレッドソフトウェアの処理だ。マルチスレッドソフトウェアは、共有環境において複数のインスタンスを同時に実行するプログラムで、異なるタスクを実行するものもある。このような複雑な環境では、特別なスケジューリング方法が使用される場合のみ、バグが発生するということが多い。たとえば、あるスレッドのステートメントの後で別のスレッドの別のステートメントを実行する場合などだ。また、スケジューリングはプログラム自体で制御するものではなく、通常は決定性ではないため、問題の発生は断続的で再現不可能だ。開発者にとっては悪夢である。こうした問題への対応は既に行われており、DejaVUのようなツールを使えばJavaプログラムを反復可能なスケジューリングで実行できる。Delta Debuggingは、バグの原因であるスケジューリングや隠れているスケジューリングを顕在化する。Delta Debuggingは前述したのとまさに同じアルゴリズムに沿って、今度は入力やコードではなくスケジューリングを対象に、DejaVUとして最終的にはスケジュール内のどこに危険が潜んでいるかを突き止める。

Delta Debuggingのこのような多様な適用方法は開発者の役に立つものだが、これまでに公開されている実装は、一部の特殊な状況を除き、実用ツールというよりはむしろ概念実証である。たとえば、問題の原因となる入力を単純化するEclipseプラグインが公開されているが、最新リリースのインストールは簡単にはできない。コード変更にDelta Debuggingを実装した最新のEclipseプラグインの誕生は、数ヵ月後に予定されている。

Delta Debuggingを具体化したもののうち、現在一番試しやすくて重要なものは、”パブリック・デバッグ・サーバ”AskIgorで、ここではプログラムの状態にDelta Debuggingが適用されている。

プログラムには”状態（ステート）”があり、これは変数とデータ構造の値で構成され、実行中に変化する。プログラム実行中のある瞬間の状態（あるいは少なくとも状態の関連部分）は、デバッガを使用して検出し検査できる。2つの実行のうち一方だけが失敗する場合、それぞれの任意の瞬間について、状態のスナップショットを取得できる。両者には必ず相違点があるはずだ。これらの相違点にDelta Debuggingを適用することで、失敗に関連する状態のサブセット（通常はいくつかの変数の集まり）を特定できる。これは開発者にとって貴重な情報だ。特に、2つの並列実行で違うときにプロセスが繰り返し発生するような場合は重要である。

AskIgorを使用するには、デバッグシンボルを含めてコンパイルしたLinux i386バイナリが必要だ。それからファイルのアーカイブをアップロードして、プログラムの実行環境を再現する。後は、成功する呼び出しと失敗する呼び出しを指定して、プロセスを実行するだけでいい。すると、サーバがサンドボックス内でソフトウェアを実行し、失敗の現象を推測し（その推測が間違っている場合は後で訂正できる）、プログラムの状態にDelta Debugging手順を適用する。数分後、結果が見事なHTMLレポートに表示される。それぞれの瞬間について、失敗を引き起こしている変数（通常は重要な関数のエントリポイント）の一覧が表示され、最後に失敗に至るまでの因果関係の連鎖が示される。チェックボックスを使って、原因と結果の特定のステップに関する詳細情報も表示できる。最終的には、不具合の発生が始まっている場所を突き止めることができる。

AskIgorの開発者たちは、この手法の能力を示す多くのケーススタディを報告している。その中に、GCCのあるリビジョンで単純な正しいCプログラムをコンパイルするとクラッシュする、というケースがあった。そこでGCCにこの手法を適用したところ、迅速に分析できたという。

また、AskIgorサイトにはサンプル付きガイドもあり、不具合のある単純なプログラムのサンプルと、AskIgorをデバッグ工程に活用するための詳しい説明が掲載されている。

AskIgorを強化しているソフトウェア（Delta Debugging技術をプログラム状態に適用して実装したソフトウェア）は、オープンソースとしてダウンロード可能だ。数ヵ月すれば、この技術で強化されたツールがもっと現れるだろう。プロジェクトリーダーのAndreas Zeller教授は、Delta Debuggingも含めたデバッグに関する書籍も執筆中で、これは2005年秋に刊行される予定だ。

Delta Debuggingは、確かな理論的基礎を持った極めて興味深いアプローチである。実用としての適用はまだ初期段階ではあるが、まもなく多くの利用者を得ることになるだろう。

原文