DEAR: A Novel Deep Learning-based Approach for Automated Program Repair
Yi Li , Shaohua Wang∗ , Tien N. Nguyen
引用
Yi Li, Shaohua Wang, and Tien N. Nguyen. 2022. DEAR: A Novel Deep Learning-based Approach for Automated Program Repair. In 44th International Conference on Software Engineering (ICSE ’22), May 21–29, 2022, Pittsburgh, PA, USA. ACM, New York, NY, USA, 13 pages. https://doi.org/10.1145/3510003.3510177
论文：https://ieeexplore.ieee.org/document/9793900
仓库：https://github.com/AutomatedProgramRepair-2021/dear-auto-fix
摘要
现有深度学习（DL）自动程序修复（APR）模型在修复一般软件缺陷方面存在局限性。我们提出DEAR，支持一次性修复多个连续语句中一个或多个代码块的一般性错误。我们设计了新型故障定位（FL）技术，结合传统频谱FL与深度学习和数据流分析。然后，我们采用两层树状LSTM模型，循环训练，并使用分治策略学习正确的代码转换。我们在三个数据集上评估DEAR，相较于基线技术，DEAR在Defects4J数据集上提高了42%-683% 的自动修复数量。在BigFix数据集上，DEAR比DL-based APR模型多修复了31-145个缺陷。在CPatMiner数据集上，DEAR比最先进的DL-based APR模型多修复了71和164个缺陷，其中包括52和61个多代码块/多语句缺陷。
1 引言
尽管现有的最先进的基于DL的APR方法取得了成功，但在修复涉及到对文件的同一部分或不同部分中的多个语句或不同文件（称为代码块）进行多个语句的修复时仍然存在局限性。因此，使用现有的基于DL的APR工具来修复多代码块/多语句bug可能是不准确的。在本文中，我们旨在通过引入DEAR，该模型支持一次性对属于一个或多个有缺陷代码块中的一个或多个有缺陷语句进行一般性缺陷修复。为此，我们提出了以下关键技术贡献：
首先，我们开发了一种针对多代码块、多语句错误的故障定位（FL）技术，将传统的基于频谱的FL（SBFL）与DL和数据流分析相结合。DEAR使用SBFL方法识别可疑有缺陷语句的排名列表。然后，通过微调预训练的BERT模型，使用该列表的有缺陷语句来推导需要一起修复的有缺陷代码块，以学习语句之间的修复关系。我们还设计了一个扩展算法，以有缺陷代码块中的有缺陷语句 s 为种子，并扩展以包括 s 周围其他可疑连续语句。为实现这一点，我们使用一个RNN模型对语句进行分类为有缺陷或无缺陷，并使用数据流分析进行调整，然后形成有缺陷代码块。
其次，在扩展步骤之后，我们已经确定了所有带有有缺陷语句的有缺陷代码块。我们开发了一种组合方法来学习并生成多代码块、多语句的修复。在我们的方法中，从有缺陷语句开始，我们使用分治策略来学习抽象语法树（AST）中的每个子树转换。具体来说，我们使用基于AST的差异技术来推导细粒度的、基于AST的变化以及在训练数据中有缺陷和修复代码之间的映射。
第三，我们使用了一个基于树的、两层的长短期记忆（LSTM）模型，其中包括一个注意力层和循环训练帮助DEAR在周围代码的上下文中学习正确的代码修复更改。对于我们的故障定位确定的每个有缺陷AST子树，我们将其编码为一个向量表示，并将该LSTM模型应用于推导修复后的代码。在第一层中，它学习修复上下文，即包围有缺陷AST子树的代码结构。在第二层中，它使用上下文作为额外的权重来学习修复该有缺陷子树的代码转换。
最后，为了为每个有缺陷子树 B 构建周围上下文，在训练中，我们包含其他有缺陷子树修复后的AST子树（而不是这些有缺陷子树本身），其理由是修复后的子树实际上代表了 B 的正确周围代码。我们进行了实验，评估了DEAR在三个大型数据集上的性能：Defects4J、BigFix和CPatMiner数据集基线DL-based方法包括DLFix、CoCoNuT、SequenceR、Tufano19、CODIT和CURE。DEAR相对于在所有三个数据集上表现最佳的基线CURE，使用仅Top-1补丁，分别多修复了31%（即+11）、5.6%（即+41）和9.3%（即+31）的bug。在Defects4J上，它在修复的bug数量方面超过了42%至683%。在BigFix上，它使用Top-1补丁比这些基线修复了31-145个更多的bug。在CPatMiner中，DEAR修复的667个bug中，有169个（25.3%）是多代码块/多语句的。DEAR修复的bug比现有的DL-based APR工具CoCoNuT、DLFix和CURE分别多修复了71、164和41个。我们还将DEAR与8种最先进的基于模式的APR工具进行了比较，结果表明DEAR生成的结果与顶级基于模式的APR工具相媲美且互补。在Defects4J上，DEAR修复了12个bug（共47个），其中包括7个顶级基于模式的APR工具无法修复的多代码块/多语句的bug。
简而言之，本文的主要贡献包括：
A. 推进基于DL的APR用于多代码块/多语句修复的一般性错误：DEAR推动了基于DL的APR用于一般性错误的进展。我们展示了基于DL的APR可以达到与其他APR方向可比较且互补的结果。
B. 先进的基于DL的APR技术：1）一种将基于频谱的FL与DL和数据流分析相结合的新颖FL技术，用于多代码块、多语句修复；2）一个具有分治策略的组合方法，用于学习和生成多代码块、多语句修复；以及3）通过注意力层和循环训练进行增强的两层LSTM模型的设计和协调。
C. 广泛的实证评估：1）DEAR优于现有的基于DL的APR工具；2）DEAR是第一个在修复的bug数量上与最先进的基于模式的工具达到相同水平并产生互补结果的基于DL的APR模型；3）我们的数据和工具是公开可用的。
图1：一个通用的修复方案，涉及多个依赖性变更
2 方法
2.1 方法概述
图2：训练过程概述
2.1.1 训练过程
训练的输入包括修复前后的源代码（如图2所示），将其解析为AST。输出包括两个训练好的模型，一个用于上下文学习，另一个用于树转换学习（修复）。
上下文学习。第一步是构建训练的修复前后上下文。通过分治策略，我们使用CPatMiner 来得出已更改、已插入和已删除的子树。因此，对于有缺陷语句的AST子树，我们将其映射到相应的修复子树。对于每个有缺陷子树和相应的修复子树，我们构建方法的整个AST的两个AST作为上下文，一个是修复前的，另一个是修复后的，并在树形LSTM上下文学习模型的输入层和输出层上同时使用它们进行训练。
树转换学习。我们首先使用CPatMiner 来得出子树映射。为了学习修复bug的树转换，每个有缺陷子树T自身及其修复后的子树 T′在第二个基于树的LSTM的输入层和输出层上同时用于训练。此外，作为上下文的权重，即上下文学习模型中作为向量计算的权重，也作为这一步骤的额外输入。
2.1.2 修复过程
图3：修复过程概述
图3说明了修复过程。输入包括有缺陷的源代码和一组测试用例。
故障定位和有缺陷代码块检测。我们首先使用SBFL工具定位具有可疑分数的有缺陷语句。有缺陷代码块检测算法使用这些语句来得出需要一起修复的有缺陷代码块。
多语句扩展。由于SBFL可能会为一个代码块返回一个语句，我们的目标是扩展以可能包括更多连续的有缺陷语句。为了实现这一点，我们结合使用RNN和数据流分析来检测更多有缺陷语句。
基于树的代码修复。对于从多语句扩展中检测到的有缺陷语句，我们一次对多个有缺陷子树进行修复。
2.2 训练过程
在CPatMiner中，我们使用一个分治策略来将有bug的子树与对应的修复子树配对，而不是将整个有bug的方法与修复后的方法进行配对。首先，我们使用CPatMiner工具来获取修复的变化。如果一个子树对应一个语句，我们称之为语句子树。根据CPatMiner的结果，我们使用以下规则将有bug的子树与对应的修复子树配对：
1.有bug的子树（S-子树）是具有更新或删除操作的子树。
2.如果一个有bug的S-子树被删除，我们将其与一个空树配对。
3.如果一个有bug的S-子树被标记为更新（即，它被更新或者它的子节点可能被插入、删除或更新），我们将这个有bug的S-子树与其对应的修复S-子树配对。
4.如果一个S-子树被插入且其父节点是另一个S-子树，我们将其与该父S-子树配对。如果父节点不是一个S-子树，则我们将一个空树配对到对应的插入S-子树。
图4：构建上下文以训练上下文学习模型
在上下文构建中，对每对有bug的AST和修复后的AST进行变量的α-重命名。我们使用GloVe单词嵌入模型对每个AST节点进行向量编码。然后，对每对有bug的S-子树和修复S-子树，使用TreeCaps对其进行节点摘要以捕捉树结构，并得到向量表示。最终，这些向量用作后续树转换学习的加权输入（图4）。我们对DLFix中的两层基于树的LSTM模型进行了改进，添加了注意力层和循环训练。模型现在包含编码器层、解码器层和注意力层（图5）。编码器和解码器使用Child-Sum基于树的LSTM来学习在AST中表达的修复上下文。每个子树循环一次以捕获结构。
图5：基于注意力和树结构的LSTM模型循环训练过程
我们还使用循环训练进行进一步的改进。循环训练旨在通过持续训练和重新训练来强调输入和输出之间的映射，以帮助模型更好地学习它们之间的映射。在一个buggy代码可以通过多种方式修复为不同的修复代码，或者多个buggy代码可以修复为一个修复代码的情况下，这是有帮助的。这使得常规的基于树的LSTM不够准确。通过循环训练，将输入和最可能的输出对的配对强调起来，以减少此类一对多或多对一关系的噪声。
图6：树变换学习过程
图6说明了树变换学习过程。我们使用带有注意力层和循环训练的基于树的LSTM模型来学习每个有bug的S-子树 Tb 的代码转换。在步骤1中，我们为所有代码标记建立单词嵌入。每个有bug的S-子树（Tb）和修复后的S-子树（Tf）中的每个AST节点都用其向量表示进行标记（图6）。接下来，我们使用在图4中上下文学习中计算得到的摘要向量 Vs 和 Vs' 作为权重，并分别对每个节点的向量在有bug的S-子树 的S-子树 Tf 中执行交叉乘积。交叉乘积后的结果用作树形LSTM模型的输入和输出层，以学习代码转换。
2.3 修复过程
我们首先对Google预训练的BERT模型进行微调，目的是让它能够理解语句之间的修复关系。这一微调使得BERT能够识别在同一个补丁中一起修复的错误块。微调过程中，我们使用了一对一对的语句，通过BERT构建向量表示，从而学习语句之间的修复关系。接着，我们使用经过微调的BERT模型进行块检测，以确定哪些代码块需要一起修复。
另外，为了处理可能只包含一条语句的有错误块，我们引入了多语句扩展算法：这一算法结合了深度学习和数据流分析，首先使用基于GRU的RNN模型进行训练，以判断语句是否有错误。然后，通过数据流分析调整结果，即使RNN模型将语句标记为非错误，但如果存在数据依赖关系，则仍将其标记为有错误。
算法1： 多语句扩展算法
多语句扩展算法的步骤如下：首先，它通过包括 buggyS 前的 N 条语句和 buggyS 后的 N 条语句（在第2行的Expand2N-CandidatesList中）生成一个有错误语句的候选列表。在当前的实现中， N =5。然后，它使用RNN模型作为分类器，以预测候选列表中的每个语句（除了有错误的S）是否有错误（RN- NClassifier在第3行）。为了训练该RNN模型，我们使用训练数据中有错误块中的有错误语句。我们使用TreeCaps 对语句进行编码。
在DataDepAnalysis（第4行）中，为了调整来自RNN模型的结果，我们获取了围绕有错误语句 buggyS 的有错误块，其中包括由RNN模型预测为有错误的之前和之后的语句（第7行）。然后，我们逐语句从候选列表中心有错误语句开始向上（第8行，通过TopHalf）和向下（第9行，通过BotHalf）检查。在DDExpandHunk中，我们继续扩展（向上或向下）当前有错误块 buggyHunk，以包括由RNN模型视为有错误或与中心有错误语句 buggyS 存在数据依赖关系的语句（第13-14行）。如果遇到没有数据依赖关系的非错误语句或用尽列表，则停止该过程（向上或向下）（第15行）。最后，返回包含连续有错误语句的有错误块。
图7： 多语句扩展示例
在图7中，SBFL工具在第4行返回有错误的语句。所有语句通过GloVe [29]编码为向量集，并由RNN模型进行分类。我们从第4行开始向上扩展，以包括第3行（即使RNN模型将其预测为非错误），因为第3行通过变量 c 与第4行存在数据依赖关系。我们包含第5行，因为RNN模型预测第5行为有错误。此时，我们停止向上和向下扩展，因为我们遇到了没有与第4行存在数据依赖关系的非错误语句，即第1-2行和第6-7行被排除在外。最终结果包括第3-5行的语句作为有错误块。
在使用RNN进行有错误语句预测方面，我们使用GloVe编码来表示语句，并通过基于GRU的RNN模型进行训练和预测。训练好的基于GRU的RNN模型用于扩展算法的第3行，以预测块中的语句是否有错误。该模型以GloVe标记向量的形式接收语句。它以多时间步的方式处理块中所有语句的向量，并将它们标记为有错误或非错误。
图8说明了这个过程。在推导出方法中的有错误块之后，DEAR使用训练好的LSTM模型一次性对所有有错误块中的所有有错误语句进行代码修复。
图8： 基于树的代码修复
3 实验评估
RQ1 在Defects4J上与基于DL的APR模型的比较
表1： 与带有故障定位的Defects4J上基于DL的APR模型进行比较
表2： 与带有故障定位的Defects4J上基于DL的APR模型的详细比较
使用故障定位。使用故障定位工具Ochiai时，我们评估了APR模型。表1和表2分别展示了DEAR和基线模型之间的比较结果。DEAR在自动修复缺陷和生成通过所有测试用例的可行补丁方面表现更佳。具体来说，DEAR相对于Sequencer、CODIT、Tufano19、DLFix、CoCoNuT和CURE分别提升了213%、683%、236%、57%、42%和31%，可以自动修复更多的缺陷。在Defects4J数据集上，DEAR也能够自动修复其他工具无法解决的bug。表2显示了DEAR与顶级DL基线（DLFix、CoCoNuT、CURE）相比，针对不同类型的bug的比较结果。
没有故障定位。我们还比较了DEAR与其他工具在没有第三方故障定位工具影响下的修复能力。所有比较的工具（表3）都指向了正确的修复位置并执行了修复。如表中所示，如果知道修复位置，DEAR的修复能力也比那些基线更高（53个bug对比44、40和48）。重要的是，它可以修复20个多个代码块/多个语句的bug（共53个修复的bug中的37.7%），而CoCoNuT、DLFix和CURE只能修复7、5和10个这样的bug。
表3： 与Defects4J上无故障定位（即正确位置）的DL-based APR模型进行比较
RQ2 在大型数据集上与基于DL的APR模型的比较结果
表4： 与DL APR在大型数据集上的比较
表4显示，DEAR可以修复比任何DL-based APR基线更多的bug，在两个大型数据集上。使用top-1补丁，DEAR可以修复CPatMiner中总共4415个bug中的15.1%。它比具有top-1补丁的基线修复了40-322个更多的bug。在BigFix上，它可以使用top-1补丁修复总共2594个bug的14.1%。它可以比那些使用top-1补丁的基线修复31-145个更多的bug。
表5： 与DL APR在跨数据集上的比较
表5显示，DEAR在跨数据集设置中也优于基线，在该设置中我们在CPatMiner上训练模型然后在BigFix上进行测试，反之亦然。
表6： 详细分析：在CPatMiner数据集上与基于DL的APR模型的Top-1结果比较
表6显示了关于不同bug类型的CPatMiner的详细比较结果。可以看出，DEAR可以在两个大型数据集上的每一种bug位置上自动修复更多的bug。在667个修复的bug中，DEAR已经修复了169个类型为2-5的多个代码块或多个语句的bug（即总修复bug的25.33%）。DEAR修复的bug比基线CoCoNuT、DLFix和CURE分别多出71、164和41个，并且在每种bug类型中修复的bug也更多。 DEAR比CoCoNuT、DLFix和CURE分别多修复了52、61和40个多个代码块/多个语句的bug，以及20、104和2个一个代码块/一个语句的bug。对于其他工具修复的多语句bug（类型2和5），修复的语句是独立的。这个结果表明一次修复每个单独的语句是行不通的。
RQ3 与基于模式的APR模型的比较结果
表7： 与基于模式的APR模型的比较
表8： 与基于模式的APR模型的详细比较
如表7所示，DEAR在bug数量方面与顶级基于模式的工具Hercules和Tbar表现相当。表8显示了关于不同bug类型的比较细节。可以看出，DEAR修复了7个Hercules错过的多个/混合语句bug（类型2、4-5）。进一步调查发现，Hercules旨在修复重复的bug，即代码块必须具有相似的语句。这7个bug是非重复的，即错误的代码块具有不同的错误语句或一个错误的代码块具有多个非相似的错误语句。对于类型1和3，由于其不正确的修复，DEAR比Hercules少修复了9个单语句bug。总的来说，DEAR修复了Hercules错过的12个bug：Chart-7,16,20,24; Time-7; Closure-6,10,40; Lang-10; Math-41,50,91。
与Tbar相比，DEAR修复了15个更多的多个代码块/多个语句bug。Tbar并不设计为一次修复多个语句，而是一次修复一个语句，因此，当这15个bug需要对多个语句进行依赖性修复时，其效果不佳。Tbar可以修复的3个类型2的bug是那些独立修复的单个语句的bug。同样的原因也适用于SimFix。Tbar修复了11个更多的正确的单代码块/单语句bug。
RQ4 敏感性分析
表9： 在Defects4J数据集上的敏感性分析
（1）有无代码块检测对修复的影响。表9所示，在没有代码块检测的情况下，DEAR可以自动修复35个bug。通过代码块检测，DEAR可以修复14个更多的多代码块bug（类型3-5）。由于不正确的代码块检测，它会少修复两个类型1的bug。简而言之，代码块检测是有用的，因为多代码块/多语句的bug需要一次性对多个代码块进行依赖性修复。
（2）多语句扩展的影响。如表9所示，在没有扩展的情况下，DEAR在Defects4J中修复了43个bug。通过扩展，它在类型2、4、5中修复了7个更多的多语句bug，同时类型3的bug减少了两个，类型1的bug减少了一个。在这两种类型中修复的bug数量较少的原因是，多语句扩展可能会将单语句bug错误地扩展为多语句bug。即便如此，DEAR仍然可以修复更多的bug，显示了多语句扩展的有效性。、
（3）带注意力和循环训练的基于树的LSTM模型的影响。为了衡量注意力和循环训练的影响，我们从DEAR中移除了这两个机制以生成一个基线。我们的结果表明，在Defects4J中，DEAR在所有bug类型上比基线修复了7个更多的bug（增加了17.5%）。这个结果表明了这两种机制的有用性。
（4）训练数据大小的影响。表10显示了训练数据的大小对DEAR性能的影响。如表10所示，训练数据越多，DEAR的准确性越高。这是预期的，因为DEAR是一种数据驱动的方法。但即使使用较少的训练数据（70%/30%），DEAR的top-1结果仍然达到了11.7%，这仍然高于DLFix（top-1为11.4%）和Sequencer（top-1为7.7%）；这两者都使用了更多的训练数据（90%/10%拆分）。
表10： 训练数据大小的影响
RQ5 时间复杂度与参数
图9： 在CPatMiner中的一个关于多块/多语句修复示例
DEAR在CPatMiner上的训练时间为+22小时，对于每个候选补丁，在CPatMiner上的预测需要2.4-3.1秒。在BigFix上，DEAR的训练时间为18-19小时，对于每个候选补丁，在BigFix上的预测需要3.6-4.2秒。在Defects4J上的预测每个候选补丁只需要2.1秒，因为这是一个更小的数据集。每个测试用例的测试执行时间为+1秒。对于每个bug修复，测试验证需要2到20分钟。
最佳基线CURE修复的bug比DEAR少（RQ1和RQ2），并且在CPatMiner和BigFix上需要的训练参数是DEAR的7倍和7.3倍。具体来说，DEAR和CURE在CPatMiner上分别需要0.39M和3.1M训练参数，在BigFix上分别需要0.42M和3.5M参数。因此，DEAR的复杂度比CURE低，同时取得了更好的结果。
举例说明。图9展示了DEAR的一个正确修复示例。它正确检测到两个有多个语句的bug代码块。DEAR利用了同一方法中现有的变量名（第8行的modifiableRootModel），在第11-12行组成了修复的代码。DL-based基线Sequencer和CoCoNuT 将代码视为序列，并没有很好地推导出此修复的结构性变化。DLFix一次只修复一个语句，因此不起作用（第2行和第3行的修复彼此依赖）。对于基于模式的APR，对于此bug没有修复模板。
转述：何晨曦
