二分法（ソフトウェアエンジニアリング）

二分法は、ソフトウェア開発において、特定の動作変更をもたらす変更セットを識別するために使用される方法です。これは主に、バグを導入したパッチを見つけるために使用されます。別の応用分野は、間接的にバグを修正したパッチを見つけることです。

特定の回帰をもたらした変更セットを見つけるプロセスは、 1997 年にCray Researchの Brian Ness と Viet Ngo によって「ソース変更分離」として説明されました。回帰テストは、 1 つ以上の変更セットを含むエディションの Crayコンパイラに対して実行されました。既知の回帰を含むエディションは、開発者が問題に対処するまで検証できませんでした。ソース変更分離により、原因が 1 つの変更セットに絞り込まれ、その後、変更の作成者が修正に取り組む間、エディションから除外して、この問題に関してエディションをブロック解除できました。Ness と Ngo は、この分離を実行するための線形検索とバイナリ検索の方法を概説しました。^[1]

コード二分法の目的は、特定の変更セットを見つけるための労力を最小限に抑えることです。コード二分法では、コード リポジトリ内のリビジョン管理によって通常保存されるコード履歴へのアクセスに依存する 分割統治アルゴリズムを採用しています。

コード履歴は、トポロジカルにソートできる有向非巡回グラフの構造を持ちます。これにより、次のような分割統治法検索アルゴリズムを使用できます。

• 候補となる修正の検索空間を分割する
• 問題となっている行動をテストする
• テスト結果に応じて検索空間を縮小する
• 最大で1つの二分可能なパッチ候補を含む範囲が残るまで、上記の手順を繰り返します。

二分法は、アルゴリズムの複雑さがのLSPACEにあり、は検索空間内の修正回数を表し、二分探索 に似ています。 ${\displaystyle O(\log N)}$${\displaystyle N}$

コードの二分化では、検索空間内の各リビジョンを個別に構築およびテストできることが望ましいです。

二分アルゴリズムがテスト対象の動作の変更を引き起こした単一の変更セットを識別するには、動作が検索空間全体で単調に変化する必要があります。合格/不合格テストなどのブール関数の場合、これは、検索空間の開始と終了の間のすべての変更セットで動作が 1 回だけ変化することを意味します。

検索空間全体に、テストされる動作が偽と真の間で変化する複数の変更セットがある場合、二分アルゴリズムはそのうちの 1 つを見つけますが、それが検索空間の開始と終了の間の動作の変化の根本原因であるとは限りません。根本原因は、別の変更セットである場合もあれば、検索空間全体にわたる 2 つ以上の変更セットの組み合わせである場合もあります。この問題に対処するために、自動化ツールでは、二分検索中に特定の変更セットを無視できます。

二分法は手動でも実行できますが、その主な利点の 1 つは簡単に自動化できることです。^{[1]そのため、既存の}テスト自動化プロセスに適合できます。徹底的な自動回帰テストで失敗すると、自動二分法がトリガーされ、障害が特定されます。Ness と Ngo は、自動的に分離された不良な変更セットをビルドから自動的に除外できる Cray の継続的デリバリースタイルの環境でのその可能性に注目しました。^[2]

リビジョン管理システムFossil、Git、Mercurial には、コードの二分化のための機能が組み込まれています。^{[3] [4] [5]}ユーザーは、リビジョン管理システムがテストするリビジョンを提案するリビジョンの範囲を指定して二分化セッションを開始し、テストされたリビジョンが「良好」か「不良」かをシステムに伝え、特定の「不良」リビジョンが特定されるまでこのプロセスが繰り返されます。BazaarやSubversionなどの他のリビジョン管理システムは、プラグイン^[6]または外部スクリプトを通じて二分化をサポートしています。^[7]

Phoronix Test Suite は、パフォーマンスの低下を見つけるために自動的に二分法を実行できます。

• デルタデバッグ（バグの最小限の原因を見つける一般化）
• 注釈 § ソース管理(ファイル内の行を編集した変更セットの特定)