使用LLM开展自动化程序修复
转载一篇我发表在安全学术圈的论文阅读笔记。
LLM已经成为一种潮流，必须跟上！
分享一篇使用LLM进行自动化程序修复的论文，题目为"Copiloting the Copilots: Fusing Large Language Models with Completion Engines for Automated Program Repair"。
在自动程序修复APR过程中，用通用编程语言为真实世界的系统合成正确的补丁是具有挑战性的。最近的大型语言模型已经被证明是帮助开发者完成各种编码任务的有用的“副驾驶”（我理解作者想表达的是：他们提出的模型与拉力赛里面的领航员的作用类似），并且已经被直接应用于补丁合成。然而，大多数LLM将程序视为token序列，这意味着它们不知道目标编程语言的底层语义约束。这导致大量静态无效的生成补丁，阻碍了该技术的实用性。为此，本文提出了Repilot。作者的关键见解是：许多LLM产生自回归输出（即：token by token，也就是一个一个生成token），类似于人类编写的程序，可以通过Completion Engine显著增强和引导（这个Completion Engine的作用我理解类似于代码补全？）。Repilot通过LLM和Completion Engine之间的交互来协同合成候选补丁，1）删除LLM建议的不可行标记，以及2）基于Completion Engine提供的建议主动完成token。
【LLM通常包含大量可用的开源代码库作为其训练数据集的一部分。将LLM应用于APR并不是使用LLM将有错误的代码翻译成正确的代码，而是直接将其用于从周围的上下文中合成正确的补丁。】
虽然现有的用于APR技术的LLM实现了最先进的错误修复性能，但是它们以黑盒方式使用LLM，其中底层LLM根据令牌分布生成程序，而没有对代码的任何结构或语义理解。为了突出当前LLM对于APR工具的局限性，在图1中，作者展示了LLM可能生成不正确补丁的3个场景。（1）生成不可行token。在图1.1中，LLM有很高的概率（> 90%）生成字符串来完成asString方法。然而，asString不是对象t的有效字段访问，也不是当前错误方法作用域的一部分。在这种情况下，使用asString生成的补丁永远不会正确，因为它无法通过编译。通过直接使用模型概率，LLM可能会使用无效token生成许多补丁，并降低生成正确的带有End （0.2%）的补丁的可能性。（2）难以生成稀有token。LLM通常不能一步生成完整的标识符名称，因为它使用子词token化[1]将不常用的词分解成更小的子词。这些不常见的单词在代码中表现为罕见的标识符，其中标识符名称是多个单词的大小写或下划线组合（例如，图1.2中的asEndTag）。因此，LLM需要逐步生成这些标识符，不仅需要多次迭代，而且每一步都需要准确的输出。由于先前的方法基于概率进行采样，因此完成罕见token来修复bug的可能性非常低。（3）没有明确考虑类型。除了可能生成超出范围的标识符之外，LLM不能访问各种类型的信息，这些信息为有效的标识符提供了提示。在图1.3中，asEndTag()的返回类型是EndTag，它的定义没有明确地提供给LLM的直接上下文。因此，LLM不知道EndTag的正确成员字段，可能会生成包含不符合所需类型的标识符的无效补丁。相反，完成Completion Engine可以完全访问项目，并可以通过对程序的抽象语法树进行静态分析，轻松计算出asEndTag()的返回类型。通过将代码视为文本标记序列，重要的类型信息不会被编码。
【Repilot首先使用LLM来提供在补丁中生成下一个令牌的概率，然后查询Completion Engine，以通过动态地将无效token的概率归零来修改概率列表。然后，可以从新的概率列表中进行采样，以选择下一个token。例如，Repilot直接删除了图1.1中的String和Name token，因为根据Completion Engine它们是不可行的，但仍然接受正确的Endtoken。在图1.2中，Completion Engine识别出asEndTag是前缀asEnd的唯一有效延续，因此Repilot直接完成这个token，而不查询LLM。】
论文的第三章是预备知识，全是一堆形式化表达，我知道你不想看（我也不想）。
所以，咱就简单放两个图意思意思吧。
Repilot专注于修复单块bug，其中补丁是通过在完美的缺陷定位下更改代码的连续部分来获得的。Repilot可以针对多块bug进行扩展，方法是用单独的填充token同时替换所有块位置，并使用LLM生成替换块。如图4所示，在本文中，作者将修复问题视为完形填空任务[2]：首先用屏蔽的span token（<span>）替换有缺陷的块，然后使用LLM从周围的代码上下文中直接合成固定的块来替换span token，从而形成补丁。
图5显示了Repilot如何合成一个程序，该程序作为原始错误程序的修复部分。生成循环由一个循环组成，该循环通过语言模型和Completion Engine之协同生成的新token来更新生成。生成循环通过将当前生成作为输入送给模型以作为开始（1），该循环开始于将当前生成，作为输入应用到语言模型(1)，该语言模型返回从建议的下一个token到其对应概率的映射的搜索空间。Repilot随后进入token选择阶段，从搜索空间中重复采样token，检查其可行性，并修剪搜索空间，直到token被接受。每次采样一个token时，Repilot首先检查它是否命中Memorization（2），该Memorization存储已知可行或不可行的token。不可行token的Memorization包括使用文章4.3中讨论的前缀树数据结构（Trie）。当token命中Memorization并且不可行时，通过将该token的概率设置为零（3）来修剪搜索空间，并且下一次采样将在更新的搜索空间上进行。通过这种方式，在token选择阶段不会再次对同一token进行采样。如果令牌没有命中Memorization，搜索空间在Completion Engine（4）的指导下被修剪。如果Completion Engine拒绝采样的token，Repilot会将其概率归零。否则，它被接受，并且该token选择过程终止。Memorization在前述两种情况（即：token被拒绝和被接受）下都得到更新（5）。token被接受后（6），进一步利用Completion Engine，尝试主动完成token（7）。最后，Repilot将所有新生成的token追加到当前生成的token中，并开始新的循环，直到生成完整的补丁。当模型生成特殊令牌end-token时，循环停止。
算法1详细说明了这个过程。
- Completion引导的搜索空间修剪
算法2解释了Completion Engine如何帮助修剪模型的搜索空间。函数GuidedPrune将Completion Engine CE、当前程序prog、当前插入符号位置caret和由模型给出的概率映射token作为输入，并产生token next-token作为程序prog在位置caret的延续。该函数由whileloop（第2行到第11行）组成，其中Repilot首先根据概率对可能的next-token进行采样（第3行），相应地更新当前程序（第4行），并将插入符号移动到next-token之后。Repilot然后使用等式（3.5）中定义的函数complete调用Completion Engine，给定程序和插入符号位置。如果结果不是unknow但没有完成（第8行），则意味着在next-token之后不能形成可能的延续，因此next-token被认为是不可行的，故在这一轮搜索中被修剪（第9行），然后循环继续（第10行）。否则，认为token是可行的，并返回next-token（第11行）。
- 专为快速搜索而设计的Memorization
算法2涉及的测试和剪枝操作会影响修复任务的效率。为此，作者通过几种Memorization技术来提高模型的分析速度。
**记录拒绝的token。**修复一个bug需要生成大量的样本，这意味着相同的程序和（第4到5行）可能会在算法2中重复出现。因此，可以通过将第9行删除的所有token存储在一个变量中来记录它们，同时将它们的概率置零。
**记录接受的token。**除了被拒绝的token，还需要记住变量中之前被接受的token，以避免在第7行到第8行查询Completion Engine所产生的开销。
**为被拒绝的token构建前缀树。**语言模型词汇表中的许多token是另一个的前缀。如果一个token被拒绝，意味着在该token之后不能形成可能的延续以获得静态有效的程序，那么任何共享这种前缀的token都应该被拒绝。出于这个原因，需要构建并保持更新所有被拒绝的token的前缀树（Trie）。给定prog和caret，并检查Trie中的任何token是否是是算法2中第3行之后的next-token的前缀。如果是，Repilot直接跳到下一次循环，避免进一步分析。
- 主动的Completion
Completion Engine不仅能够确定由模型建议的可能的next-token的可行性，而且还能够主动建议当前程序的潜在延续，而无需查询模型，就像开发人员如何从自动Completion中受益一样。
算法3描述了主动的Completion。函数ActivelyComplete接受三个输入：CE、prog和caret，并输出一系列token completion-toks作为prog在caret的延续。最初，给定prog和caret（第2行）获得completion结果，并检查它是否是unknown（第3行）。如果completions == unknown，结果被设置为一个空字符串，这意味着不会产生额外的completion（第4行）。否则，Repilot计算所有completion的公共前缀（第6行）。注意，结果变量完成的类型是编程语言字母表中的字符序列，因此Repilot进一步调整completion以适应模型的词汇表（第7行）。最后，在第8行返回结果。
下面从作者的实验部分找两个例子来说明Repilot对bug代码的修复流程：
图7展示了Defects4J 1.2中一个只有Repilot可以修复的独特bug （Closure-133）。通过使用全局变量NO_UNREAD_TOKEN添加新的赋值语句来修复该bug；但是该变量很难生成，因为它不会出现在错误位置的上下文中。Repilot首先使用CodeT5生成unread的初始前缀。然后使用Completion Engine，Repilot识别Token是唯一语义正确的延续，并直接执行主动completion以返回unreadToken。类似地，对于生成NO_UNREAD_TOKEN，Repilot首先生成NO_，然后使用主动completion来直接生成该罕见的标识符，而不必重复从LLM采样。现有的基于LLM和NMT的APR工具很难生成这种修复，因为LLM或NMT模型可能无法完成这种罕见的标识符，它需要多个连续步骤来生成。
图8显示了Defects4J 2.0中一个只有Repilot可以修复的独特bug。首先，Repilot生成直到插入符号位置的补丁。然后，Completion Engine从Token.EndTag到String。使用这些信息，Repilot可以正确地删除不属于String类的token（例如，name和text）。因此，生成的补丁包含toLowerCase()的有效String类方法，该方法正确地修复了这个错误。与Defects4J 1.2中以前的独特错误修复类似，以前的基于LLM的APR工具可能会浪费大量时间来生成语义不正确的延续，因为它们无法访问类型信息。此外，基于NMT的APR工具通过静态抓取所有可访问的字段来过度近似有效标识符的列表，可能不会生成此修复，因为删减的标识符（如：name）对于不同的对象类型也可能是有效的。Repilot使用完成引擎来分析部分程序，并实现复杂类型传播以进行有效的修剪。
参考文献
[1] Sennrich R, Haddow B, Birch A. Neural machine translation of rare words with subword units[J]. arXiv preprint arXiv:1508.07909, 2015.
[2] Xia C S, Zhang L. Less training, more repairing please: revisiting automated program repair via zero-shot learning[C]//Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2022: 959-971.
安全学术圈招募队友-ing
有兴趣加入学术圈的请联系 secdr#qq.com
