MultiMend: Multilingual Program Repair with Context Augmentation and Multi-Hunk Patch Generation

技術的概要：MultiMend

1. 問題

テストや検証の進歩にもかかわらず、ソフトウェアのデバッグは依然として人手と時間を要するプロセスです。機械学習に基づく自動プログラム修復（APR）は有望な解決策として登場しましたが、既存の技術は以下のような重大な課題に直面しています：

• 言語依存性： 多くのツールは単一のプログラミング言語に特化しています。
• 限られたコンテキスト： 現在のアプローチは、修復のコンテキストをエラーの直近の行やそれを包含する関数に制限する傾向があります。しかし、修復に関連する情報はファイルやプロジェクトの遠く離れた部分に存在する可能性があります。
• マルチハンクバグへの困難： ほとんどのAPRモデルは、単一の連続した場所（シングルハンク）の欠陥を修正することに焦点を当てています。実際のバグは、しばしば複数の非連続な場所（マルチハンク）での修正を必要とし、これにより探索空間と検証の複雑さが指数関数的に増大します。
• 外部データベースへの依存： 多くのツールは修正例の外部データベースに依存しており、これはすべてのプロジェクトで利用可能とは限りません。

2. 手法（MultiMend）

MultiMend は、上記の制限を克服するために設計された、学習ベースの多言語APRアプローチであり、コンテキスト増強（Context Augmentation）とマルチハンクパッチ生成という2つの主要な革新を通じて実現されています。

アーキテクチャと手順：

1. ベースモデルとファインチューニング：

   • コード用事前学習言語モデルであるCodeT5-smallをベースとして使用します。
   • ココヌット（CoCoNuT）のプロセスに従い、オープンソースリポジトリ（コミット履歴）から抽出された大規模な多言語データセット（Java、Python、C、JavaScript）でモデルをファインチューニングします。
   • チェックポイントアンサンブル戦略を採用します：複数の専門モデルを訓練する代わりに、MultiMendは訓練中に同じモデルの複数の「スナップショット（チェックポイント）」を使用して、多様な候補リストを生成します。

2. RAG（検索拡張生成）によるコンテキスト増強：

   • 外部データベースから例を検索する手法とは異なり、MultiMendは欠陥のあるソースファイル内で直接コンテキストの検索を行います。
   • メカニズム：
     • 即時コンテキスト外のファイル行は、密な埋め込みモデルを使用してベクトル（埋め込み）化されます。
     • 推論中、欠陥のある「ハンク」もベクトル化され、同じファイルから最も意味的に類似した行（上限 $r$ まで）を復元するために使用されます。
     • これら復元された行は、関数のコンテキストとともにモデルの入力に注入され、外部データなしで関連する修復の「材料」を提供します。

3. マルチハンクパッチの生成と検証：

   • 複数の場所に影響を与えるバグに対して、MultiMendは検証の組み合わせ爆発（$t^h$、ここで $t$ はハンクあたりのパッチ数、$h$ はハンク数）を回避するための体系的な戦略を採用します。
   • 検証戦略：
     • まず、すべてのハンクに均一に適用可能な単一のパッチを特定しようと試みます。
     • 失敗した場合、各ハンクごとにパッチを検証し、失敗したテストのサブセットを解決する部分的な修正を維持します。
     • これらの部分的な修正を反復的に組み合わせることで完全なパッチを形成し、必要な検証数を劇的に削減します（数百万から数百へ）。

3. 主な貢献

• 多言語ツール： Java、Python、C、JavaScriptのバグを単一のモデルを使用して修復できるMultiMendの導入。
• 言語非依存のコンテキスト増強： 欠陥のあるファイル自体内で意味的類似性に基づくRAGを使用し、モデルの入力を強化することで、外部の修正データベースへの依存を排除。
• 体系的なマルチハンク戦略： 複数の場所での変更を必要とするバグに対して効率的にパッチを生成・検証する手法。これにより、シングルハンクモデルの能力を複雑なシナリオに拡張。
• 包括的な評価： 6つの異なるベンチマークで、5,500以上の実際のバグを対象とした広範なテスト。

4. 実験結果

MultiMendは、Defects4J、QuixBugs、Codeflaws、BugAID、BugsInPy、RunBugRunなどのベンチマークで、18の最先端（SOTA）ツールと比較して評価されました。

• 全体的な有効性：
  • MultiMendは、最初の妥当なパッチのみを考慮して2,227個のバグを正しく修正しました。
  • そのうち、1,545個のパッチは開発者が提供したパッチ（グランドトゥルース）と同一でした。
  • Defects4J v1.2（Gammaに次ぐ2位）を除くすべてのベンチマークで、大多数のSOTAツールを上回るか同等の性能を示しました。
• マルチハンク性能：
  • システムは121個のマルチハンクバグを正常に修正し、他のツールが頻繁に無視するか完全な修正に失敗する複雑な欠陥に対処する能力を実証しました。
• コンポーネントの貢献：
  • 除去実験により、コンテキスト増強がすべてのベンチマークで性能を向上させ、これなしでは発見されなかった23個の追加の正しいパッチを生成したことが示されました。
  • マルチハンク戦略は、コードの複数の部分で変更を必要とするバグを解決するために不可欠でした。
• 効率性：
  • モデルは上位候補（トップ10〜トップ100）で高い修正率を維持しており、パッチのランキングが良いことを示しています。
  • 妥当なパッチを見つけるまでの平均時間は低く（中央値で約3秒）でしたが、ハンク数の多いバグは検証によりこの時間を増加させる可能性があります。

5. 意義と結論

MultiMend は、大規模な外部例データベースに依存することなく、堅牢で多言語かつ効率的なツールを構築できることを実証することで、APR分野における重要な進歩を表しています。

• 技術的革新： ソースファイル自体に適用されたRAGと、インテリジェントなマルチハンク検証戦略の組み合わせは、関連するコンテキストの欠如と分散型バグの複雑さという、分野の2つのボトルネックを解決します。
• 実用的な影響： 多様な言語やシナリオで開発者のパッチと同一のパッチを生成する能力により、MultiMendはソフトウェア保守における手作業の負担を軽減するための実用的な解決策を提供します。
• 将来： 著者らは、より大きなコンテキストウィンドウを持つモデルの使用、対話型ワークフロー（指示付きLLM）との統合、パッチランキングメカニズムの改善が、将来の研究に向けた有望な方向性であると提案しています。

要約すると、MultiMendはAPRにおける新しい最先端を確立し、インテリジェントなコンテキスト増強と複雑なバグの効率的な管理が、実世界のシナリオにおいてより高い成功率をもたらすことを証明しました。