基于神经机器翻译的程序自动修复

这是一篇来自ICSE' 21的论文，题目为："CURE: Code-Aware Neural Machine Translation for Automatic Program Repair"。这篇论文已经开源：https://github.com/lin-tan/CURE。

自动程序修复对提高软件可靠性至关重要。最近，神经机器翻译（NMT）技术已经被用于自动修复软件缺陷。尽管前景看好，但这些方法有两个主要限制。它们的搜索空间通常不包含正确的修正，搜索策略忽略了软件知识，如：严格的代码语法。因此，现有的基于NMT的技术不如最好的基于模板的方法。

对于基于搜索的APR方法（包括基于NMT的技术）生成正确的修复需要满足两个条件：（1）正确的修复必须在搜索空间中，其中搜索空间是APR方法可以生成的所有补丁的集合；（2）搜索策略必须有效，才能在合理的时间内找到正确的修复。假设搜索空间中有一个正确的补丁，则搜索空间较小是可取的，这样更容易找到正确的补丁。

但是，与自然语言文本相比，源代码有其自身的特点，如：严格的语法、代码语义和无限数量的可能标识符。这些特性给NMT模型自动修复错误带来了独特的挑战。

首先，源代码严格的语法对于NMT模型来说很难学习。一个主要原因是现有的技术从错误代码片段和对应的修复后的正确代码片段（通常每个错误几行到几十行）中学习，并且不使用整个源代码库（通常每个项目几百万行代码）。因此，现有的基于NMT的APR方法对编程语言严格的语法和开发人员如何编写代码的总体情况了解有限。导致：(1)现有技术未能利用大量可用的源代码，以及(2)它们只看到部分代码片段（仅这部分代码片段通常在语法上是不正确的），没有对完整的方法、类和项目的全局观。例如，对于将while (x) {替换为while (y) {的修复，左括号{在此代码片段中语法不正确，因为缺少右括号}。同时，现有模型未能学习开发人员如何编写代码。现有的基于NMT的APR技术能够生成可编译但明显不正确的补丁，因为它们看起来不像开发人员编写的代码。这些不可编译和可编译但不正确的补丁降低了APR模型的准确性和效率，阻止了APR模型更快地生成更多正确的补丁。

其次，如果使用单词级tokenization，无限数量的可能标识符导致代码的NMT技术需要处理巨大的词汇表，其中词汇表包含NMT模型识别的所有唯一token。考虑到NMT体系结构的复杂性，对于基于NMT的APR模型来说，使用巨大的词汇表在计算上太昂贵了。然而，由于词汇量有限，他们的搜索空间并不包含所有正确的修正。

因此，作者提出了一种基于NMT的方法，专门用于解析、分析、建模和搜索源代码（相对于自然语言文本）以自动修复错误。该方法（CURE）不仅改善了搜索空间（包含更多正确补丁的更小的搜索空间），而且使用了更有效的搜索策略来查找正确的补丁并将其排名更高。

CURE的框图如图2所示，主要涉及3种策略：

（1）Programming language models：

将预训练和微调工作流应用于APR任务。具体来说，预训练的语言模型为许多NLP任务带来了巨大的改进，它们从大量的自然语言文本中学习单词序列的概率分布；然后，通过向其添加额外的模型（例如，为分类任务添加分类器）来微调以应用于特定任务。语言模型向添加到其中的模型提供输入序列的矢量化表示。由于预训练语言模型通常是在较大的数据集上训练的（因为它是无监督的学习并且不需要基础事实），所以它向添加的模型提供了关于句子结构（例如，句法）和关于什么是类人（你没有看错，我没有写错，就是类人，human-like）文本（例如，可读性）的更多信息，这显著提高了针对特定任务的微调模型生成文本的质量。

（2）Code-aware search strategy：

当使用NMT模型来生成token序列以形成补丁时，理想地应该优选具有最高分数的序列，例如：序列中每个token的平均对数概率。由于这是非常昂贵的，在实践中，人们使用搜索策略在每一步选择适当的令牌。Beam Search是NMT的一种常见搜索策略，它在每一步都保持最可能的n个序列，其中n是beam size。

NLP任务的beam size通常为5到20。由于源代码比自然语言具有更多可能的标识符和更大的搜索空间，APR的NMT模型通常需要更大的beam size（100到1000）来生成足够的候选补丁。然而，对于较大的beam size，标准的beam search选择了许多坏的补丁：要不是不可编译的，要不是在长度上远远不正确的。

为了应对这一挑战，作者提出了两种解决方案：有效标识符检查策略和长度控制策略。首先，由于源代码是一种形式语言，所以只允许有效的标记，包括范围内的关键字和变量。无效的token使得打了补丁的程序不可编译，更不用说通过测试用例了。因此，作者提出并设计了一种有效标识符检查策略来改进标准的beam search，该策略执行静态分析来识别所有有效标识符，然后强制beam search只生成有效令牌序列。

对于较大的beam size，beam search会找到许多非常短的序列，如{和try { ，这些都是用于修复bug的不正确的代码片段。由于训练数据中的正确修复通常与有缺陷的行具有相似的长度，所以使用长度控制策略来惩罚太短和太长的序列，以促使CURE生成与有缺陷的行具有相似长度的补丁。

（3） Subword tokenization：

CoCoNuT [2]模型提出的增强单词级tokenization通过使用camel字母、下划线和数字来拆分长标识符，减少了代码的词汇大小。然而，许多复合词（如：二分搜索法的"binsearch"）不包含这些特殊字符。之前的解析方法将"binsearch"保留为一个单词，即OOV，而不是将其分解为"bin"和"search"，这两个单词都在词汇表中。因此，作者使用字节对编码（BPE），一种子词tokenization技术，来标记复合词和生僻词，以进一步解决OOV问题。

模型实现细节：

CURE由三个阶段组成：训练、推理和验证。在训练阶段，CURE从开源项目中提取方法，称为PL（Programming Language）训练数据，并将它们tokenization（图2中的步骤1a）。CURE使用子词级tokenization，它产生一个更小但更准确的搜索空间，包含更多正确的补丁。CURE使用这些tokenization的方法来训练一个新的编程语言模型（Programming Language Model），该模型学习具有正确语法的、类似开发者的源代码（步骤2）。CURE还将从开源项目的提交历史中提取的错误行、上下文和正确修复tokenize为token序列(步骤1b)，这些token被称为补丁训练数据。使用这些序列来微调k个APR模型的集合（步骤3）。每个APR模型都结合了PL模型和上下文感知神经机器翻译（CoNuT）模型[3]。

在推断阶段，用户提供一个有缺陷的项目以及要修复的有缺陷的代码行的位置。这些是现有APR工具需要的标准输入。CURE tokenize这些错误和上下文行（步骤1c），然后分析源代码以提取错误行范围内的有效标识符列表（步骤4）。补丁生成模块使用新的代码感知beam search策略生成候选补丁列表（步骤5）。该算法在运行中丢弃许多不相关的补丁（即，一旦生成无效令牌就可丢弃），并惩罚不太可能正确的补丁（例如，在长度上与错误行非常不同的修复），这节省了大量资源，并允许CURE更深入地搜索正确的补丁。

• 在训练时，CURE需要两种不同的训练数据：

首先，GPT PL模型是在从开源Java项目中提取的数百万种方法上训练出来的。其次，CURE为APR任务微调PL模型。这一步需要APR特定的训练数据（即，错误的行、上下文和正确的修复）。这里作者使用了CoCoNuT模型的数据，https://github.com/lin-tan/CoCoNut-Artifact。

• 代码表征和Tokenization：

**单词级别的tokenization：**为了将错误行、上下文行和修复行tokenize为token序列，CURE首先使用增强的单词级tokenization [3]以空格、camel字母、下划线、字符串和数字（除了0和1）分隔代码行。

**Out-of-vocabulary问题：**单词级tokenization后的词汇量大于NLP中常用的词汇量，测试集仍然包含2%的OOV（Out-of-vocabulary）token。排除稀有token对于源代码来说是有问题的，因为OOV token很可能是重要的特定于项目的token。排除这样的token使得NMT模型很难修复这些新项目中的错误。

**子词Tokenization：**为了解决OOV问题并减少词汇量，本文使用了BPE，这是一种无监督的学习算法，通过迭代合并最频繁的字节对来找到语料库中最频繁的子词。BPE已经在许多自然语言处理任务中使用，它有助于减少词汇量和有效缓解OOV问题。

图3是推理阶段tokenization的示例。以-开头的是bug代码行（作为输入），以+开头的是正确的修复。当使用增强的单词级tokenization时，charno是一个OOV token，所以导致部分现有模型无法正确修复；而使用本文的子词tokenization方法，charno被拆分为两个均在单词表中出现的词，其中char@@表示该token需要和后面的token连接。

• 编程语言模型：

PL模型优化了token序列成为真实世界代码片段的概率，翻译成人话就是：让token序列更像程序员写的而不是机翻。作者使用Generative Pre-trained Transformer（好家伙，这就是GPT的全称）进行PL建模。

预先训练PL模型允许将编程语言学习与补丁学习分开。优势是双重的：第一，GPT学习是无监督的，只需要完整的方法；因此，可以自动和准确地提取大量数据来训练它。第二，在微调过程中，APR模型已经知道PL语法，这使得微调更加有效。

PL模型的目标如下，原文才能体现精髓（就是不想翻译了）

• 使用PL微调APR模型：

在预训练PL模型之后，CURE通过将GPT PL模型与NMT模型组合作为APR模型来微调用于APR任务的PL模型。作者使用CoNuT作为NMT模型。通过更新如下平均对数似然公式中的两个参数来微调APR模型，其中表示bug代码行，表示上下文，表示正确的修复，都是token序列。

为了防止PL模型丢失它在预训练期间学习的信息，作者包括语言建模（即：）作为微调过程的辅助目标，同时提高微调模型的泛化能力。最终，通过最大化组合平均对数似然来微调APR模型：

其中，是从bug方法开始到正确修复中最后一个token的token序列；是的前缀。在训练阶段，APR模型将预训练的GPT模块（PL模型）和补丁训练数据作为输入。补丁训练数据由错误行、上下文和正确的修复组成。训练APR模型多个epoch以获得权重和的最佳组合。

在推理阶段，APR模型只能访问有问题的行及其上下文，并输出一系列表示补丁的token。图4显示了本文的组合APR模型的架构的简化视图，以及如何在推理过程中使用该模型。该APR模型由两部分组成：PL模型（GPT）和NMT模型（CoNuT）。

首先，CURE生成上下文行的GPT表示（图4步骤1）。由于GPT模型是根据完整的方法训练的，因此GPT模型的输入需要是一个完整的方法。如果直接将错误代码行的第一个token提供给GPT模型（如图4中的int），GPT模型将为它生成一个错误的嵌入。因此，GPT模型在错误方法中为所有token生成一个嵌入。

CoNuT模型包含两个编码器。错误行编码器仅以错误行的表示作为输入。因此，CURE从错误方法嵌入中提取对应于错误行嵌入的子序列（图4中的黄色框），并将其发送给错误行编码器（步骤2a）。第二个编码器用于上下文，将整个错误方法的嵌入（图4中的紫色方框）作为输入（步骤2b）。CURE在将两个编码器的输出发送到注意机制和令牌生成器之前合并这两个编码器的输出（步骤3）。

为了生成token，注意机制和令牌生成器需要编码器和解码器的输出。在推理开始时，还没有生成任何修复的token。CoCoNuT用一个初始的<START> token开始解码序列。但是，作者认为最好在错误行之前用上下文的最后一个token初始化序列，以提供额外的上下文信息。为了获得这个token的嵌入，本文将错误行之前的上下文传递给GPT模型（步骤4），然后将最后一个token的嵌入(即：{)提供给解码器（步骤5）。解码器生成token的表示，该表示被转发给注意机制（步骤6）。

注意力机制将来自两个编码器的输出和解码器的输出相结合，以形成从最后一个token（即：{）到bug方法的注意力映射。接着，token generation模块输出修复序列的第一个token，也就是步骤8中的double。该token随后被用于解码器的输出（步骤9）。随后，解码器以{ double为输入开始下一轮迭代（步骤10-15），然后生成token sum。迭代直到序列的最后一个token <EOS>生成。

咋后面还有内容？

• 集成学习：

Lutellier等人的工作[3]表明，集成学习，即：组合多个模型，使得基于NMT的APR方法能够修复更多的错误：当模型的数量从1增加到20时，正确修复的错误的数量从22增加到44。因此本文将(1)具有不同超参数的模型和(2)具有两种不同架构（CoNuT和FConv [4]）的模型组合起来用于集成学习。GPT PL模型是通用的，因为它代表了整个PL。因此，每个APR模型从相同的PL模型开始，对其进行微调，并将其与具有不同超参数的CoNuT或FConv架构相结合（图2步骤3）。

为了平衡计算成本和调整效率，作者使用随机搜索在合理的范围内挑选不同的超参数值（例如，卷积层数、卷积维数和dropout），并在每一个epoch调整模型。基于每个模型对验证数据的困惑（perplexity，即：模型预测实例的程度的度量），选择前k个模型用于集成学习，并保持训练它们直到收敛。

• 代码敏感的beam search策略和补丁生成：

普通的beam search的一个主要问题是，它只考虑模型提供的对数概率来生成下一个token。由于关于代码的其他信息（例如，作用域内的变量）对于APR模型是不可用的，所以它经常为作用域外的变量生成高分，从而产生不可编译的候选补丁。

因此，本文设计了两种技术——有效标识符检查和长度控制，使beam search具有代码感知能力。

**有效标识符检查：**在特定的Java代码片段中，只有少数token是有效的，因为正确的代码必须遵循Java语法和编译规则。为了只生成有效的标识符，CURE首先使用静态分析来解析和提取有效的标识符。然后CURE将这些标识符tokenization（例如，max_ending_here转换成[max,_,ending,_,here]），并在所有前缀和它们有效的后续token之间建立映射，如图5所示。这个映射对于beam search了解"在生成序列max_ending_后，由于由于max_ending_here是有效的，所以here是下一个有效token"至关重要。

在每个解码步骤中，NMT模型输出词汇中所有token的概率分布。CURE新的有效标识符检查策略首先分析已经生成的token序列以获得需要生成的下一个token的前缀。如果生成的token序列不包含任何前缀（即：下一个token是新标识符的开始），则前缀将被设置为空字符串。然后，根据所有可能的前缀及其有效的后续token之间的映射，有效标识符检查策略修改概率分布，并将无效token的概率设置为。这样一来，有效标识符检查策略丢弃了许多不可能的节点，增加了找到正确补丁的可能性。

图6说明了其工作原理。max_ending_here=Math.max(0,max_ending_here)是正确的修复，步骤1-6已经生成了输出序列max_ending_here=。使用beam size 2简化图示说明。正确定位的路径用绿色箭头标记，beam search策略考虑的节点用浅灰色表示。

在步骤7的过程中，APR模型给出的最可能的节点是... max和... Match，其中...表示已经生成的max_ending_here=。在步骤8中，... Match .（图6a左子图的绿色路径）的平均对数似然比... max _和... max CaMeL小，所以普通的beam search放弃了它，导致包含正确修复的整个子树被排除。相反的，在使用有效标识符检查策略后，... max CaMeL的平均对数似然被置为，因为以max CaMeL开头的标识符都是无效的。而... Match .被保留，离生成正确修复又近了一步。

**长度控制：**在训练数据中，大多数正确修复的长度与错误行的长度相似。作者发现，在拥有270万补丁的训练数据中，75%的bug的长度差异小于或等于5个token。这意味着大多数情况下，正确的修复是对有问题的代码行进行小的修改，更复杂的更改不太常见。

因此，使用长度控制策略，通过惩罚短补丁和长补丁来生成具有类似长度的bug行的补丁。在每个解码步骤中，长度控制策略计算已经生成的序列的长度。如果当前长度比错误行小得多，则降低<EOS>的对数似然，以防止该补丁到达末尾。如果当前长度已经比错误的行大得多，则增加了<EOS>的对数似然以提示这个补丁结束。

为了确定惩罚值，本文利用补丁训练数据中的长度差分布来计算每个长度差的对数概率，表示为函数。通过向token <EOS>添加以下惩罚来修改它的对数似然：

图6b是对长度控制策略的说明。该bug与图6(a)中的一样，但是具有更大的beam search size——1000。在步骤2中，序列{ }到达<EOS> token。使用普通beam search，补丁{ }具有较低的平均对数似然，但是仍然在top 1000中，故将被添加到候选补丁，因为beam search size很大。这种低分数补丁占据了有价值的位置，并且阻止了正确的补丁被选择。而在本文中，由于完整序列{ }比错误序列短得多，因此<EOS> token受到很大的惩罚，并且不被选作候选节点（不包括在1000个最高平均对数似然候选项中），从而允许搜索策略沿着其他路径更深入地搜索。

• 补丁验证：

在APR模型生成候选补丁之后，将token序列重构为代码语句。首先将以@@结尾的token连接到它们的后继token，这是从子词到词的重构。然后，从错误的代码文件中提取出供体（donor）代码，以重构抽象的token（0数字和字符串）。

重构的语句按其标记的平均对数似然排序，然后插入到有错误的代码文件中以替换有错误的行。每个修补的项目都被编译以过滤不可编译的修补程序；运行测试套件，直到找到满足两个条件的修补程序：(1)通过错误项目通过的所有测试用例，以及(2)通过至少一个在错误项目上失败的测试用例。

参考文献

[1] Long F, Rinard M. An analysis of the search spaces for generate and validate patch generation systems[C]//Proceedings of the 38th International Conference on Software Engineering. 2016: 702-713.

[2] Lutellier T, Pham H V, Pang L, et al. Coconut: combining context-aware neural translation models using ensemble for program repair[C]//Proceedings of the 29th ACM SIGSOFT international symposium on software testing and analysis. 2020: 101-114.

[3] Lutellier T, Pham H V, Pang L, et al. Coconut: combining context-aware neural translation models using ensemble for program repair[C]//Proceedings of the 29th ACM SIGSOFT international symposium on software testing and analysis. 2020: 101-114.

[4] Gehring J, Auli M, Grangier D, et al. Convolutional sequence to sequence learning[C]//International conference on machine learning. PMLR, 2017: 1243-1252.