Automated Repair of Programs From Large Language Models

Zhiyu Fan, Xiang Gao, Martin Mirchev, Abhik Roychoudhury, Shin Hwei Tan

引用

Zhiyu Fan, Xiang Gao, Martin Mirchev, Abhik Roychoudhury and Shin Hwei Tan. 2023. Automated Repair of Programs From Large Language Models. ICSE ‘23: Proceedings of the 45th International Conference on Software Engineering, May 2023, Pages 1469-1481. https://doi.org/10.1109/ICSE48619.2023.00128

论文：https://doi.org/10.1109/ICSE48619.2023.00128

摘要

这篇论文中，我们以探讨自动化程序修复（Automated Program Repair，APR）技术如何提高大型语言模型生成代码的可靠性为目标，系统地研究了使用ARP技术是否能修复语言模型在LeetCode竞赛中产生的错误解决方案。经研究发现：(1) 自动生成的代码与人类编写的解决方案存在共同的编程错误，表明APR技术有潜力修复自动生成的代码；(2) 鉴于统计故障定位方法提供的错误位置信息，新发布的支持代码编辑的Codex编辑模式在修复错误解决方案方面，与现有的Java修复工具TBar和Recoder相似或更优。通过分析这些工具的实验结果，我们提出以下几点建议：(1) 提升APR工具以超越补丁空间的限制是有益的；(2) 随着大型语言模型通过更多数据训练可以推导出更多的修复模式，未来的APR工具可能需要将重点从添加更多修复模式转向基于合成/语义的修复方法；(3) 结合语言模型与APR来筛选补丁成分的研究值得探索。

1 引言

近年来，设计基于人工智能的系统来自动解决编程任务引起了广泛关注。其中，以Transformer为基础的大型语言模型，如Codex和AlphaCode，在生成Python、Java和C等编程语言的代码方面表现出色。尽管Transformer模型在解决许多编程任务上取得了成功，但其成功率仍然相对较低。主要的问题在于，这些模型缺乏对任务的描述和对程序语义的深入理解。Transformer模型将代码生成视为序列到序列的转换，将描述和代码视为token序列，因而无法捕捉程序的深层语义特征。相比之下，生成完整的程序需要理解任务描述的全部内容，这通常包含复杂的逻辑，而解决编程任务依赖于深入的算法推理。尽管系统地研究语言模型在解决编程任务中效率低下的原因很重要，但关于语言模型自动生成程序中的缺陷的特性研究却鲜有，这在理解如何进一步改进这些自动生成的程序方面留下了空白。

自动化程序修复（Automated Program Repair，APR）是一个新兴领域，旨在自动修正编程错误。APR技术接受一个有错误的程序和一个正确性规范作为输入，通过轻微修改程序使其满足给定的规范，生成修复后的程序。例如，基于语义的修复工具（如SemFix、Angelix）通过符号执行生成补丁，而基于搜索的修复工具（如GenProg、TBar）在预定义的搜索空间中寻找正确的补丁。APR在修复实际的错误方面显示出了前景，但由于语义推理的复杂性和多行修复时的搜索空间爆炸，它们通常仍限于生成小补丁（通常是一行修复）。语言模型的强项和弱点促使我们思考：自动化程序修复（APR）是否能提升基于大语言模型生成的代码的可靠性？总的来说，本文有以下贡献：

系统地研究了来自语言模型的错误程序的自动化修复。首次将新发布的Codex编辑模式作为自动化修复工具的有效性的评估和研究。提出了LMDefects，一个包含113个Java编程任务的新数据集。其中，46个任务已被Codex成功解决，67个任务仍然未解。

2 技术介绍

2.1 Codex模型

Codex模型支撑了GitHub Copilot的核心功能，它能根据自然语言提示完成程序。Codex支持多种编程语言（如Python、C/C++、Java）。其训练数据包含自然语言和来自GitHub的数十亿行公开代码。在本研究中，我们使用预训练的Codex code-davinci-002和Codex-e code-davinci-edit-001模型，它们均基于2021年6月前的数据进行训练。研究的整体流程如图1所示。

图1：Codex生成自动修复程序的工作流程

在实验部分，我们使用Codex为每个任务生成初始解，并在公开示例测试用例上验证生成解的正确性。对于未解决的编程任务，我们会应用基于测试的修复工具（使用公共测试）来修复Codex产生的错误解。修复后的解会被（1）公共测试和（2）LeetCode平台中保留的（私有）测试用例进行验证。为了回答我们的研究问题，我们构建了一个名为LMDefects的数据集，包含LeetCode中的113个编程任务。

2.2 LeetCode平台

LeetCode是一个在线编程竞赛平台，包含2300多个不同难度的问题，从简单到困难。它还有一个活跃的论坛，可以找到每个编程任务的正确解（这对于手动分析错误解至关重要）。每个任务用自然语言文本描述，并附带1-3个公共测试，提供输入-输出对示例。当提交解决方案给LeetCode时，它会运行一组私有测试来验证提交的正确性。LeetCode每周和每两周发布一次新的编程任务。在研究中，我们仅考虑简单和中等难度的问题，因为Codex无法解决大多数困难问题（我们还排除了七个需要定制数据结构的任务，这些结构Codex可能无法处理）。为了防止收集的数据集被用作Codex训练集，我们只考虑2021年6月之后发布的竞赛（这是Codex训练数据提取的截止日期）。

3 实验评估

3.1 实验设置

研究问题。在本文中，我们研究以下问题：

RQ1：自动生成的代码中常见的错误模式是什么？

RQ2：APR工具能否有效地修复来自Codex的代码？

RQ3：Codex编辑模式能否修复程序错误？

评估数据集。我们选择的实验数据来自编程竞赛平台的竞赛或手写编程任务。我们从2021年7月4日到2022年4月6日爬取了LeetCode的所有竞赛，包括40周的竞赛和20次双周竞赛。LMDefects数据集中共有60个简单任务和53个中等难度任务。我们不使用现有的数据集，原因如下：(1) Codex已经在GitHub上进行了训练，其中包含许多先前编程任务的解决方案（如APPS、CodeContest）；(2) 有些编程任务没有公开的测试用例，这是自动化程序修复（APR）技术的先决条件，如HumanEval；(3) 大多数APR工具仅支持Java程序，而HumanEval数据集则包含Python程序。

提示和参数。Codex模型接受输入提示，即自然语言文本和代码片段的组合，其中自然语言文本描述编程任务，代码片段是模型完成代码的基础。我们评估Codex在零样本提示（提示中不包含示例输入/输出）的设置下。虽然公共测试用例也可以嵌入提示（即n-shot提示），但我们将其作为自然语言描述的一部分提供给APR工具，而不是直接嵌入提示。图2中的第1-3行展示了我们为LeetCode编程任务1使用的示例提示。

图2：未匹配算法的示例，取自Leetcode周竞赛280的编程任务minimumOperations

根据这个提示，我们运行Codex生成50个候选解决方案，并选择概率最高的前五个（通过Codex的最佳参数）。选择的解决方案首先通过运行公共测试（如图2中的第14-17行，我们手动将公共测试转化为JUnit测试）进行验证，然后通过提交到LeetCode进行私有测试验证。我们遵循先前工作的设置。具体来说，我们(1) 设置温度为0.8（在生成50个候选解决方案时性能最佳），(2) 设置停止序列为"public"、"class"、"//"、"System.out.print"。我们将"最大令牌长度"设置为2048。

ARP工具。为了评估修复工具能否修复Codex生成的错误解决方案，我们选择了两个Java APR工具进行评估，因为Java APR工具已被广泛研究，并且许多是开源的。在所有开源Java APR工具中，我们选择了TBar和Recoder，原因如下：(1) 它们分别代表了不同方法的最新代表，TBar代表基于搜索和模式的APR工具，而Recoder是基于学习的方法；(2) 这些工具在Defects4J 基准上报告了最高的正确修复率（几乎所有的Java APR工具都已在该基准上评估过）。由于TBar和Recoder都是测试驱动的APR工具，我们使用程序描述中的公共测试用例来引导修复过程，而私有测试用例用于验证修复后的解决方案。我们以默认设置运行TBar和Recoder，一旦发现能够通过所有公开测试的补丁，修复过程就会停止。我们设定超时时间为15分钟，这与先前针对编程作业自动化修复工作的时限规定一致。鉴于Codex编辑模式（Codex-e）能够通过生成程序编辑来修改现有代码，我们探讨Codex-e是否能作为一种自动化程序修复（APR）工具，并将其与TBar和Recoder进行比较。

RQ1 自动生成的代码中常见的错误模式是什么？

实验设计。在应用自动化程序修复（APR）技术修复自动生成的解决方案之前，我们首先通过分析Codex生成的解决方案中的典型错误，来探讨其可行性。对于LMDefects中Codex能够解决的编程任务，我们首先让五种自动生成的解决方案在公开测试上运行，并提交到LeetCode在线评测平台，使用私有测试进行验证。如果Codex生成的解决方案s未能通过所有公开和私有测试，我们将其视为错误解决方案。如果一个编程任务的所有五种自动生成解决方案都是错误的，我们则认为这个任务未被解决。总共有46个编程任务被Codex解决。我们研究了剩余67个未解决编程任务中导致编译错误或测试失败的335个错误解决方案S buggy。

对于每个错误解决方案s buggy ∈ S buggy，两位标注者（论文的两位作者）分别和手动修复，首先参考LeetCode论坛中的其他解决方案寻找修复提示，然后构建最小的修复补丁以修复错误。为每个错误解决方案构建的修复补丁由两位标注者交叉验证，确保修复后的解决方案s f ixed能够被LeetCode平台接受。我们的目标是为每个错误解决方案构建一个“黄金标准”修复补丁s f ixed，从而获取s buggy与s f ixed之间的“差异”。基于这个“差异”，两位作者手动将每个s buggy分类到表Ⅰ中的缺陷类别中。每个s buggy被分配到一个缺陷类别。在构建黄金标准或分类缺陷过程中如有任何分歧，标注者会与其他作者讨论以解决分歧（最初有14个分歧，全部成功解决）。

表Ⅰ 错误解决方案的缺陷分类

分析。我们根据Codeflaws（一个包含编程竞赛参与者错误提交的基准）中的类别来推导缺陷分类。详细的分类及其定义见表Ⅰ。它显示了“Easy”和“Medium”难度的错误解决方案分别属于哪些类别。每个缺陷类别的示例代码可以在补充材料中找到。自动生成代码中的缺陷分类与Codeflaws中的相似。具体来说，Codeflaws和我们的数据集都包含了需要多段修复或多段修复的情况。此外，对于单段修复，两个数据集共享相似的变异操作，如运算符变异和变量变异。这表明Codex犯了与人类参与者类似的编程错误。这是可以预期的，因为Codex是通过大量可能存在bug的人类编写程序进行训练的。除了上述单段和多段错误，语法错误和算法相关错误在Codex生成的解决方案中也很普遍。我们进行了手动分析，以研究这些错误的根本原因。

语法错误。我们的手动分析显示，导致编译错误的自动生成程序通常因为代码不完整，或调用了未定义的变量/函数/类。为了降低Codex生成不完整代码的可能性，我们选择Codex允许的最大令牌长度（即2048个令牌）来生成50个候选解决方案。尽管提供了最大长度作为代码生成的边界，Codex仍然生成了平均长度为628个令牌的不完整代码。研究使用代码补全技术修复由Codex生成的不完整代码的可行性是值得的。对于未定义函数的程序，需要合成函数体来解决编译错误。未来的研究可以探索使用程序合成技术来解决未定义函数，或者逐个函数地使用Codex来合成函数体。除了这些编译错误，我们还发现Codex容易生成由于程序结尾缺少/多余括号而导致编译失败的程序（总共有23个这样的情况）。由于括号匹配问题可以轻松修复（使用正则表达式匹配机制），我们手动修复了这些问题，并将这些缺陷进一步分类到表Ⅰ中的缺陷类别中。

算法不匹配。在所有错误解决方案中，有191个使用了错误的算法来解决给定任务，包括超时（Time Limit Exceeded）。生成不符合用户意图的解决方案的问题被称为不匹配问题。所有被分类为“算法不匹配”的缺陷都受到不匹配问题的影响。

自动生成代码的负面症状。已知自动生成的补丁存在某些反模式（导致无意义补丁的程序变换）。受此启发，我们分析了Codex生成的代码是否包含不太可能是正确程序的负面症状，我们主要关注“算法不匹配”和“语法错误”类别：

名称表示错误算法：在“算法不匹配”类别中，Codex倾向于生成使用特定变量名的解决方案，这表明使用的算法/数据结构是错误的。图2显示了使用“dp”变量的例子，其中使用的算法（即“dp”指动态规划）是错误的。我们认为Codex使用动态规划来解决问题，因为它被GitHub上其他名为“minimumOperations”的不同编程任务误导。类似地，我们观察到其他变量名，如“pq”（优先队列）、“q”（队列），可能表示使用了错误的数据结构。相似代码块：我们注意到当Codex难以为给定提示找到高质量的解决方案时，它倾向于反复生成相似的代码块（代码克隆，变量名、语句使用和控制结构有轻微变化）。图3显示了一个解决方案，其中5-8行和9-12行有相似的代码块（仅变量名不同）。不相关的辅助函数：尽管我们重用了Codex的设置来添加停止序列（一旦到达函数结束就停止代码生成），但我们观察到Codex仍然可能生成与给定提示无关的冗余辅助函数。

图3：相似代码块生成示例（“++”表示突出显示），取自Leetcode编程任务minimumSum

回答RQ1，自动编写的程序与人类编写的程序存在共同的错误，且表现出一些负面症状，包括：（1）名称导致的算法错误；（2）相似代码库；（3）不相关的辅助函数。

RQ2 ARP工具在修复Codex生成代码方面成效如何？

实验设计。对于Codex模型生成的可编译的错误解决方案，我们使用TBar和Recoder来评估它们生成补丁的能力。在补丁验证阶段，自动产生的补丁被归类如下：

合理的补丁：指使错误解决方案通过给定的公共测试的补丁。

正确的补丁：指使错误解决方案通过公共测试和私有测试，并被LeetCode接受的补丁。

表II TBAR和Recorder制作的补丁和固定任务数量

结果。表II显示了TBar和Recoder分别生成的补丁数量和正确修复的编程任务数量。尽管TBar在简单和中等难度任务中分别生成了16个和22个可能的补丁，但它只产生了6个简单任务和3个中等任务的正确补丁。相比之下，Recoder生成的可能补丁较少（简单任务16个，中等任务20个），但正确补丁更多（简单任务6个，中等任务5个）。表III的“正确修复任务”列显示了TBar和Recoder正确修复的编程任务数量。值得注意的是，每个编程任务对应于选择的五个错误解决方案。如果这些解决方案中的任何一个被正确修复（被LeetCode接受），则认为该任务已被解决。总体而言，Recoder修复了8个编程任务，而TBar仅修复了6个。结合两者，APR工具帮助Codex解决了更多简单任务（4个）和中等任务（5个）。

分析。我们进一步分析了两种APR工具修复的缺陷类型。表III显示了每种缺陷类别下可以正确修复的解决方案数量，其中“TBar”和“Recoder”列分别显示了对应工具产生的补丁数量。对于每个类别，修复工具可能不会通过最小程度地修改程序来修复缺陷（即，工具可能使用与“缺陷子类别”列中显示的最小修复不同的运算符来修复）。结果显示，现有的APR工具在生成需要多行编辑的复杂补丁方面仍然有限。图4展示了Recoder在两个例子中超越TBar的情况。在第一个例子中，尽管TBar具有“修改字面表达式”模式，但由于补丁空间有限，它无法找到正确的字面值进行替换。在第二个例子中，TBar未能生成正确的补丁，因为它不具备“插入语句”模式。

表III 由TBAR和Recorder正确修复的解决方案数量

图4 两个Recorder修复而TBar未修复的解决方案

对于需要多行修复的任务，TBar和Recoder都无法生成任何正确的补丁，原因之一是广泛采用的统计故障定位技术在TBar和Recoder中专注于单独识别每行错误，而忽视了可疑行之间的程序依赖。例如，修复图5中的bug需要（1）将s.length() -2改为s.length()，以及（2）简化if条件。使用统计故障定位，APR工具会为第4行和5-6行分别生成补丁（而没有注意到在修复5-6行的if条件后，for循环条件不再需要第4行的额外“-2”以防止“IndexOutOfBoundException”）。

回答RQ2，现有的基于模式和基于学习的自动修复程序（ARP）在修复自动生成的代码方面效果不佳，面临的挑战包括：（1）搜索空间有限；（2）无法生成多编辑补丁；（3）缺乏对程序依赖关系的认识。

RQ3 Codex编辑模式能否修复程序错误？

实验设计。最近，OpenAI 发布了 Codex 的一种新的编辑模式，该模式能够修改现有程序的内容。Codex 编辑模式将程序和自然语言指令作为输入，并根据指令输出编辑后的程序。由于 Codex-e 可以编辑程序内容，一个自然的问题是‘Codex-e 能否在正确指令的帮助下修复错误的程序？’我们设计了三种策略来构建 Codex-e 的编辑指令。

Codex-ebug：我们告诉 Codex-e 给定程序中存在一个错误，并要求 Codex-e 修复它。指令简单地给出为“修复程序中的错误”。

Codex-eline：我们遵循现有的自动程序修复技术，这些技术使用统计故障定位技术（Ochiai），对生成的错误解决方案进行处理，以获得一系列候选修复行号。然后将这些候选行号作为修复提示提供给 Codex-e。给 Codex-e 的指令被表述为“修复第 N 行”。 Codex-estm：考虑到像 Codex 这样的大型语言模型是通过普通自然语言进行训练的，我们进一步研究了如果直接使用可疑语句而不是可疑行号作为指令，Codex-e 会如何响应。我们使用可疑行的程序文本，例如第 s1 行，并将指令表述为“修复 s1”。

例如，修复makeFan-cyString中的常量变异错误时，我们给Codex-e line指令“修复第6行”，给Codex-e stm指令“修复'i -= 2;'”。对于每个错误的解决方案（排除产生语法错误的），我们选择最可疑的10个语句，让Codex-e为每个语句生成5种可能的编辑（即Codex-e尝试在50次尝试内修复错误）。与常规Codex模式下的初始解决方案生成类似，我们将温度设置为0.8，以提高找到正确编辑的可能性。

表Ⅳ 使用Codex-E正确修复的解决方案数量

结果。表Ⅳ展示了三种策略的结果，其中Codex-e bug、Codex-e line和Codex-e stm列分别显示了使用相应编辑指令找到的正确补丁数量。使用“修复程序中的错误”作为指令时，Codex-e bug仅了解到程序中的错误存在，但没有提供故障位置信息。令人惊讶的是，即使在有限的指导下，Codex-e bug成功生成了15个正确的补丁，其中4个涉及多段修改（详细示例见补充材料）。相比之下，Codex-e line修复了9个需要单段修复的解决方案和2个需要多段修复的解决方案。与Codex-e bug和Codex-e line相比，Codex-e stm表现出最佳效果，成功修复了16个错误的程序。我们归因于Codex-e stm使用了可能引导语言模型（如Codex）匹配相关语句的程序文本。

分析。此外，我们还对Codex-e生成的补丁进行了手动分析。结果表明，Codex-e能够灵活地生成补丁。先前的自动化程序修复（APR）研究显示，如果能获得精确的故障定位结果，其性能会显著提升。相比之下，现有的APR工具严格地试图在给定的错误行号处生成补丁，忽视了在相关上下文中修复错误的可能性。Codex-e则没有这样的限制。在Codex-estm修复的16个正确问题中，有8个（50%）是通过编辑超出给定指令中提供的语句范围来修复的。与传统APR工具相比，灵活的故障定位是Codex-e能够生成更多正确补丁的重要特性。在给定特定故障位置（Codex-estm）时，Codex-e的有效性几乎可以与无位置指导（Codex-e bug）时相当。

我们进一步研究了APR和Codex-e产生的补丁搜索空间是否互补，通过评估不同工具产生的补丁成分。补丁成分被定义为构建相应补丁所使用的运算符/操作数（如变量、常量、运算符等）。如果APR和Codex-e产生的补丁成分互补，它们的结合将更有可能生成正确的补丁。为此，对于每个错误的解决方案，我们首先通过参考第三部分构建的“正确”补丁（即“ground truth”补丁）获取所需的补丁成分I_correct。然后，我们分析不同工具产生的补丁成分，以评估它们是否能互补。

回答RQ3，在提供特定故障位置（Codex-estm）的情况下，Codex-e 的有效性几乎可以与不提供任何位置指导（Codex-ebug）时的有效性相媲美。

转述：刘佳凯