A Unified Debugging Approach via LLM-Based Multi-Agent Synergy

Info

  • Pub: Arxiv
  • Authors: Cheryl Lee, Chunqiu Steven Xia, Jen-tse Huang, Zhouruixin Zhu, Lingming Zhang, Michael R. Lyu
  • Institutions: CUHK, University of Illinois Urbana-Champaign
  • Repo: Not yet

Abstract

  • 自动化软件测试
  • 基于LLM的调试工具的挑战
    • 上游故障定位影响下游修复
    • 处理复杂逻辑错误的不足
    • 忽略程序的上下文
  • 通用的协同化debug框架
  • LLM可以从一般软件工程原则(rubber duck)受益
  • 克服了过拟合问题

Intro

Threat model

  • 可能存在bug的程序
  • 知道该程序的功能
  • 工具（LLM）生成plausible的patch尝试修复bug

Pervious works

debug的两个步骤

  1. Fault Localization
  2. Automated Program Repair
    FL分析测试输出以定位问题-静态/突变分析-高度依赖人工测试用例
    APR通过预定义的debug模式或符号执行-基于人工用例-搜索空间有限,在跨编程语言转换时需要重新实现修复模式
    基于学习的FL基于源代码,执行特点和测试结果定位bug
    基于学习的APR使用神经机器翻译MMT将有缺陷的代码翻译为修复
    基于LLM的FL和APR
    基于学习/LLM的debug具有下面的挑战:
  3. 不完美的FL
    现有工作都假设FL工具能够准确定位bug位置,但不能完全满足
  4. 复杂的逻辑漏洞
    对于依赖模式识别的LLM模型,具有复杂逻辑的漏洞可能比小型模型差
  5. 缺少上下文
    大部分LLM都是在文件级别的源代码训练的缺少分析文件之间的函数和代码依赖关系的能力
    忽略了变量范围,函数定义和外部库等

Contribution

提出FixAgent:通过LLM多智能体协同的第一个统一、自动化的调试框架

  1. Agent协同:每个Agent用rubber方法详细解释步骤
  2. 中间变量跟踪:显式跟踪错误程序中的关键变量,并讨论如何指导任务完成.rubber不需要逐行解释以节省context
  3. 程序上下文构建:根据规范和描述和依赖关系构建上下文,并和错误程序一起提供,同时指示Agent对上下文有更多的关注

OJxcyB.png

Motivations

Fault location(FL)

  • FL工具会报FP-不必要的修补-引入新的bug
  • 完美的FL不存在
  • FL工具会报FN-大多数FL+APR假定每个程序只包含一个bug
    • 识别涉及多行的bug具有挑战性
    • APR工具依赖于插桩FL，只能检测出单行bug
  • 依赖于测试用例的FL无法识别“xx不存在”的错误，real world的bug复杂多样需要更多的定位调试

Fixing

  • 目前的LLM可以完成debug
  • 可以在没有先验知识的情况下修复有缺陷的程序
  • 在修复逻辑bug上存在困难
    OJxdds.png
  • 可以顺利运行但WA
  • 逻辑的漏洞超出了LLM的理解力，因此需要更好的释放能力的设计

Context

  • 现有的APR只关心源代码和测试结果，忽略了上下文

Design

OJxlIN.png

  • FL：识别错误的代码语句，并标记在错误程序中
  • APR：生成一个patch
  • Reviewer/Revisitor：分析检查为什么原代码是有问题的
  • 每个agent具有独立的中间变量追踪和构建后的程序context
  • Crafter：生成人工测试用例以外的测试输入以避免过拟合
  • 流式工作，每个agent接收upstream的信息并传给downstream

Prompt

每个Agent的prompt包含一个三元组

  1. 角色设定：角色的描述和任务目标
  2. 程序规范：错误程序、失败的测试用例、程序上下文和前一个Agent的信息
  3. 任务指令：给出的执行步骤和详细说明

中间变量跟踪-改进版的rubber duck

  • 提示每一个Agent跟踪关键的中间变量，并和预期结果进行比较
  • 在resp中明确进行跟踪，并解释推导
  • 改进版的rubber不是逐行解释而是专注于核心逻辑和重要状态
  • 分解复杂问题为简单问题，并且提高推理能力
  • 增强了决策的透明度以增强可读性

核心：将一个多逻辑模块的复杂程序分解为多个中间状态

上下文构建

主要集中在两种信息：

  1. 需求
  2. 依赖关系

程序需求

如果具有详细文档，则通过下面的方式描述预期行为

  1. 程序功能
  2. 输入/输出
  3. 精度要求和其他信息

如果没有文档但实现的功能（算法）是众所周知的：请求一个通用LLM对该算法给出描述。

依赖关系

解析程序的依赖关系并且提取依赖文件的代码，并放在程序顶部.这样LLM可以先看依赖代码再看错误程序,并且可以为程序构建上下文.

OJxuyt.png

其他

测试输入生成(crafter)

单独设立一个Agent作为crafter
当一个可能正确的测试用例生成后，这里根据人类编写的测试用例迁移生成新的测试样例,以避免LLM的过拟合.这里同样使用profile-spec-instruction做prompt
prompt包含一些测试用例，帮助llm更好执行新任务
prompt要求crafter考虑和示例不同的测试用例，特别考虑：

  • 语义缺陷

  • 边界值

  • 重复输入

  • 边缘情况

  • crafter还需要解释测试用例的基本原理

  • 引导crafter挖掘多样化的输入和长测试输入

  • 长测试输入被llm限制：使用缩写表示长测试输入

由于LLM不能很好解决算术问题，需要用外部方式计算输入的预期输出。

Feedback Re-sampling

如果生成了错误的补丁，则重新反馈到第一步FL生成另一个补丁。
对于反馈context包含的数量有一个上限m，只保留最近m个失败的sample

考虑一个场景，假设最多允许个sample，目标是修复程序。
此前已经有个补丁提出，分别为
其中为通过测试数量最多的失败补丁
为了生成，将和对应的错误信息放进prompt的spec部分
最终的spec包含
在通过m次(max_retry)或者patch通过所有测试后，输出为最终解决方案

Evualation

Setup

Framework

FixAgent在公共数据集上进行比较
指标:

  • 正确patch的数量
  • plausible的补丁数量
    Dataset
  • Codeflaws:3902错误程序(2952一行错误),C language,没有给出patch
  • QuixBugs:40个包含单行错误的经典算法 Java/Python
  • ConDefects: 1254个Java和1625个Python
    ConDefect是最近的,因此不可能作为LLM的语料

Baseline

10 APR和6 LLM
或许可以加上一些国产的大模型?

Implementation

  • 在Base LLM部分,变量跟踪提示转化为“think step by step”
  • Base LLM 包含了程序规范
  • LLM设置
    • p=1.0
    • temperature=1
    • 每个LLM baseline只生成最多3个补丁(m=3)
  • 只有给出的补丁结果语义上等同数据集给出的补丁,才认为是正确的
  • 对于Quix生成的结果进行手动检查,但Codeflaw没有给出patch,因此只给出正确率
    • 生成补丁数量太多
    • 没有给出bug位置,LLM会倾向于重写代码

RQ1

  1. 和SOTA的APR工具比较
  2. 和基本的LLM比较
  3. 不同编程语言的比较

baseline FL的分类

  • 标准FL:传统的基于频谱的FL
  • 完美FL:假设APR工具知道真实的错误位置
    在软件工程和自动程序修复（APR）领域中，”标准FL”（Standard Fault Localization）和”完美的FL”（Perfect Fault Localization）是评估自动修复工具性能时常用的两种错误定位技术。
  1. 完美的故障定位（Perfect Fault Localization）:
  • 定义：完美的故障定位是一种理想化的错误定位方法，假设我们已经精确地知道了代码中错误发生的具体位置。这种情况下，错误定位技术能够直接指向导致测试失败的确切代码行或代码块。
  • 优势：提供了一种最佳情况下的评估环境，可以用来测试APR工具在已知错误位置时的修复能力，从而评估其修复技术的效果。
  • 用途：在研究中，完美的FL常用于基准测试，帮助研究者理解在理想条件下，修复工具的潜力和性能极限。
  1. 标准的故障定位（Standard Fault Localization）:

  • 定义：标凘的故障定位是指在真实场景中使用的故障定位方法，这些方法通过分析程序执行的测试用例（包括通过和失败的测试）来推断可能的错误位置。常见的技术包括谱系错误定位（Spectrum-based Fault Localization, SFL），它通过统计代码在失败和成功的测试用例中执行的频率来推测错误位置。

  • 优势：更接近实际应用的场景，可以提供关于APR工具在处理实际错误时的实用性和效果的信息。

  • 用途：在实际的软件开发和自动修复研究中，标准FL是更常见的选择，因为它能够模拟修复工具在面对真实世界错误时的表现。
    区别：

  • 准确性：完美的FL提供了错误位置的准确信息，而标准的FL的准确性取决于使用的具体技术和测试用例的质量。

  • 应用场景：完美的FL通常用于理论研究和基准测试，以评估APR方法的理论性能；标准的FL则更多用于评估工具在实际应用中的表现。

  • 实用性：在真实世界的软件开发中，很少能获得完美的FL信息，因此标准的FL在实际应用中更为常见和实用。
    结果

  • Codeflaw上FixAgent显著优于其他APR和LLM

  • QuixBug优于所有的方法

    • Java修复了39/40
    • Python修复了All

  • LLM在不知道bug位置的情况下也能表现出很强的效果,而APR通常需要完美FL的假设或者FL工具

  • Codeflaw这种对于上下文和语义的理解要求更高,因此FixAgent的效果更突出

  • 由于FixAgent关注关键变量中间值,使得问题在最终输出前就被关注和发现

RQ2

使用ConDefect检查FixAgent使用不同的LLM的比较
使用FixAgent对于Raw LLM有20%的改进,而且是非侵入式

RQ3

衡量每个Agent对FixAgent的贡献,以及如果移除了该Agent,对于效果的影响
结果:
context对于Fix的影响最重要,提供了底层问题域和推断功能的潜力
结论:
传统的 CoT 提示虽然在鼓励逐步推理方面是有效的，但并没有以最小化推理应变的方式固有地优先考虑信息。相反，我们的策略简化了llm分析程序逻辑的过程。使用一个代理来替换多智能体协同具有相似的负面影响，这减少了 28 个合理和正确的修复。劳动分工反映了软件中公认的原则：专业化，迫使每个代理专注于自己的任务并减少认知负荷。

Discussion

Limitation

  • FixAgent显著依赖Base LLM的性能和能力,只是在Base基础上更好发挥能力,而不能代替LLM做决策
  • LLM存在概率问题,在引入的外部的计算测试用例的输出的Agent中不能保证准确输出期望值.解决类似于数学推理的问题代表了llm面临的重大挑战之一。我们的方法无法克服其固有的局限性；因此，必须引入附加信息，例如正确代码或手动计算的答案，以获得生成输入的输出并形成完整的测试用例。

Validity

LLM内可能阅读过数据集的知识,具有先验
缓解方式:

  1. 选用最近最新的数据集
  2. 使用不太可能作为LLM的训练集的一部分
  3. 和Raw LLM做比较体现出优势

Conclusion

我们提出了FixAgent，这是第一个通过LLM代理协同的统一调试框架。它以端到端的方式进行故障定位、补丁生成和错误后分析。我们的见解是 LLM 可以从开发人员识别的软件工程原则中受益。因此，我们遵循橡胶鸭调试的原理，详细解释代码，创建新的设计，释放llm的调试能力，减轻以前的挑战。对两个广泛使用的数据集的评估证明了FixAgent相对于APR工具和基于LLM的竞争对手的优越性，对最近收集的数据(避免数据泄漏)的额外实验进一步表明，与基本llm相比，我们在调试方面的泛化和有效性。我们的代码和生成的补丁是公开的，以供进一步研究和复制

Resource

https://github.com/iridium-soda/Paper_slides/blob/main/A%20Unified%20Debugging%20Approach%20via%20LLM-Based%20Multi-Agent%20Synergy.key

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

Comment Here~