The Best of Both Worlds: Combining Learned Embeddings with Engineered Features for Accurate Prediction of Correct Patches
Haoye Tian1, Kui Liu2, Yinghua Li and Abdoul Kader Kaboré, 1, Anul Koyuncu3, Andrew Habib1, Li Li4, Junhao Wen5, Jacques Klein and Tengawendé F. Bissyandé1
1University of Luxembourg
2Huawei
3Sabanci University
4Monash University
5Chongqing University
引用
Tian H, Liu K, Li Y, et al. The best of both worlds: Combining learned embeddings with engineered features for accurate prediction of correct patches[J]. ACM Transactions on Software Engineering and Methodology, 2023, 32(4): 1-34.
论文：https://dl.acm.org/doi/full/10.1145/3576039
仓库：https://github.com/HaoyeTianCoder/Panther
摘要
大量关于自动程序修复的文献提出了大量自动补丁生成方法，以测试预言（Test Oracle）为基准（例如测试套件）对补丁的正确性进行验证。然而，由于这样的预言并不完备，使得补丁验证的结果可能并不正确。针对这一情况，大量前沿工作探索如何通过利用动态信息和手工启发式方法提升补丁正确性验证的准确性。在本文中，作者着重探索了学习嵌入（Learned Embeddings）在补丁验证中的作用，并尝试将学习嵌入与工程特征（Engineered Feature）相结合来评估补丁验证的正确性。为了了解不同学习嵌入的特质以选择最适合补丁正确性验证任务的相似度计算，本文系统研究了多种不同的基于代码更改的学习方法，并将学习嵌入与工程特征相结合来评估其补丁验证的正确性。实验结果证明了利用学习嵌入优化本文提出的补丁验证框架——Leopard——的可能性。与最先进的依赖于动态信息的方法PATCH-SIM相比，深度学习嵌入可以带来互补/更好的性能。通过结合深度学习嵌入和工程特征，Panther——Leopard与深度学习嵌入结合后的升级版本——在AUC、+Recall和-Recall等指标方面均优于Leopard，能够准确识别更多（不）正确的补丁，这些补丁不能被分类器仅使用学习嵌入或工程特征来预测。本文的最后，作者使用可解释的机器学习（Machine Learning，ML）技术SHAP实证性地对学习嵌入和工程特征在补丁正确性预测中发挥的作用进行了评估。
1 引言
近年来，随着软件的日益普及，自动程序修复（Automatic Program Repari，APR）技术获得了蓬勃的发展。其中，一部分自动修复技术选择对程序语义进行建模，通过合成执行约束以构造正确补丁。这种方法虽然能够保证正确性，但通常无法扩展到大型程序。另一部分自动修复研究则采用“（动态）生成和验证”方法框架，即首先根据一定的策略生成候选补丁，之后再根据给定的测试预言（Test Oracle）验证候选补丁的正确性。由于缺少精确的程序规范和完美的测试预言，现代自动修复技术通常采用测试套件作为预言近似地判定候补补丁的正确性；只要修复后的程序能够通过测试套件中的所有测试，那么这个补丁就被认为是正确的。然而，由于测试套件（1）仅能覆盖程序规格中的一部分，且（2）可能存在不符合程序预期的情况，因此利用测试套件作为测试预言往往会选出错误的补丁。这一现象被称为自动修复中的“过拟合”现象。
过拟合补丁已然成为了“生成验证”式自动修复技术的所面临的关键挑战。在本文中，作者广泛地研究和评估通过深度学习技术获得的源代码嵌入（简称“学习嵌入”）和工程特征在正确预测补丁方面的有效性。具体问题包括：哪些工程特征集和学习嵌入能够提升补丁正确性验证的性能？以及，将学习嵌入和工程特征结合是否能够产生更好的效果？具体地，本文的工作包括
（1）探索了何种学习模型更适用于自然语言令牌（Token）或源代码令牌。本研究兼顾了预训练模型和模型的再训练。
（2）开展了系统实证研究，探索在使用学习嵌入的情况下正确补丁的最小变化假设是否依然成立。作者设计并实施了大规模实验，采用统计学方法对正确补丁与错误补丁产生的相似性分数之间的差异进行了评估。
（3）开展了探索性实验，评估了选择错误代码学习嵌入和补丁代码片段之间的截止相似性分数（Cutoff Similarity Score）的可能性，进而设计启发式方法过滤掉不正确的补丁。
（4）研究了学习嵌入在分类训练管道中的判别能力。本文提出了一种名为Leopard自动修复框架，能够学习使用学习嵌入预测补丁正确性。作者通应用10组交叉验证将Leopard与SOTA方法进行了对比，发现Leopard是对SOTA方法的补充，甚至在不正确的补丁的过滤方面能够超过SOTA方法。
（5）探索了将学习嵌入和工程特征的相结合以提高提升补丁验证正确性的可能性，并根据实验结果实现了Leopard的升级版本Panther。实验结果表明学习嵌入和工程特征的结合是可能的，能够有效提升补丁验证的正确性。
（6）解释了特征和分类器背后的预测原因，采用可解释的ML方法SHAP对补丁正确性判定过程中各个组件发挥的效果进行了分析。
2 研究方法
本研究的总体目标是探究进而理解不同代码表示在补丁正确性验证方面所发挥的作用。作者首先关注自动修复领域的一个普遍假设，即能够使待修复片段产生最小变化的补丁更有可能是正确的。为了量化补丁的变化，作者利用不同的代码表示学习方法学习代码的特征，通过调整这些特征提取错误代码和修补代码的向量，并计算向量之间的相似度值。根据得到的相似度分布，作者通过定义简单的阈值提出由自动修复技术生成的不正确的补丁。鉴于学习表示能够揭示与生成正确补丁所必须得代码属性，作者提出通过利用补丁的特征表示进一步训练分类器来对候选补丁进行进一步的筛选。图1概述了该类工作流程的可能方案。为了能够将补丁表示成机器学习算法所要求的格式，作者首先使用图1中所示的学习方法为有缺陷的代码和修补代码生成向量。之后，作者通过应用减法、乘法、余弦相似度和欧几里得相似度来交叉向量，得到补丁的深度学习特征。
图1 Panther研究框架概览
学习嵌入和工程特征能够从不同的角度表示补丁。为了提高补丁验证的正确性，作者进一步提出了三种方法集成学习（Ensemble Learning）、朴素向量拼接（Naïve Vector Concatenation）和深度组合（Deep Combination）。结合这两个特征（即学习嵌入和工程特征）来获得包含更加丰富的补丁信息的表示。在获得代表给定补丁的向量后，图1所示的工作流程将利用随机森林或深度神经网络（Deep Neural Network，DNN）等不同的机器学习算法训练得到能够将候选补丁区分为正确和不正确补丁的二元分类器。最后，作者还利用SHAP方法对不同组分优化补丁验证过程中发挥的作用进行了解释。本研究可分为以下四个部分 ：
（1）关于如何过滤不正确补丁的假设和对应的实证研究（RQ-1和RQ-2）；
（2）利用学习表示和工程特征为输入训练出来的基于机器学习的分类器在预测补丁正确性时的有效性(RQ3)；
（3）将学习表示与工程特征相结合在预测补丁正确性方面的有效性（RQ-4）；
（4）学习嵌入和工程特征在预测补丁正确性方面的所各自做出的贡献（RQ-5）。
2.1 研究问题
RQ-1：不同的表示学习模型所产生错误代码和修补代码之间相似值分布是否存在可比性？程序修复的一个普遍假设是，错误修复通常会导致最小的更改。该研究问题探究学习嵌入是否能通过计算向量表示之间的余弦相似度来评估变化程度。
RQ-2：相似度分布在多大程度上可以推断出能够用于过滤掉不正确的补丁截止值？在RQ-1的基础上，作者以基于向量表示的余弦相似度为依据对补丁进行排名，利用预先定义好的相似性阈值来过滤不正确的补丁。
RQ-3：能否以代码输入的嵌入表示作为输入训练处能够识别正确补丁的预测器？在本研究问图中，作者评估了使用静态嵌入表示为特征构建的预测器的补丁识别性能，并探究其是否可以提供与动态方法相当的性能，例如利用了执行信息的方法PATCH-SIM。
RQ-4：利用学习嵌入和工程特征的组合预测补丁正确性的是否最优？作者在本研究问题中探究通过学习输入和工程特征提升补丁正确性识别的精度的可能性。
RQ-5：哪些特征对预测补丁正确性来说最有价值？在本研究问题中，作者发挥SHAP解释模型的能力来量化对不同特征对预测补丁正确性的贡献。
2.2 数据集
作者在前驱工作的基础上建立补丁数据集，从五个不同的基准集中收集补丁数据，分别是Bugs.jar、Bears、Defects4J、QuixBus和ManySStuBs4J。这些数据集中的补丁都由开源项目的开发人员手工编写。除人工补丁外，作者还考虑了集成到RepairThemAll框架中的、由自动生成工具生成的补丁。此外，研究还容纳了Liu等人在近期发布了一个补丁标记数据集，一共涵盖16个自动修复系统补丁标记数据集。表1展示了本研究在实验中使用的补丁数据集的所有信息。
表1 本研究采用的Java补丁数据集
2.3 模型输入预处理
图2 来自Defect4J的补丁片段
图3 从图2所示的补丁片段中提取出的错误代码片段
图4 从图2所示的补丁片段中提取出的修复代码片段
数据集中的样本是补丁。图2展示Defects4J数据集中的一个补丁片段。本研究所需要的数据样本是成对的错误代码和修复代码。为此，在开展机器训练之前，作者首先对补丁数据进行预处理，将其中的错误代码和修复代码提取出来。以图2所示的补丁片段为例，作者保留所有删除的行（即以“-”开始的行）和补丁上下文行（尚未修改的代码，即那些开头没有“-”、“+”或“@”的代码行），从而提取得到补丁片段的错误代码，如图3所示；类似地，修补的代码片段则由添加的行（即从“+”开始的行）和与错误代码相同的上下文代码行构成，样例如图4所示。
2.4 内嵌模型设置
图5 使用BERT，Doc2Vec，Code2Vec生成学习嵌入
表示学习算法（Representation Learning Algorithm）能够从一组训练数据构建词汇表，并进而利用词汇表将一组代码令牌（Code Token）转化成数值向量的形式，这些数值向量也就是所谓的“学习嵌入”。图5展示了作者为错误代码和修复代码生成学习嵌入的过程。考虑到预训练嵌入模型所需的巨大开销，作者直接利用现有预训练模型实现代码片段的嵌入，进而实现分类器的训练过程。考虑到不同的训练数据和训练目标，作者采用四个文献中常见的预训练模型——BERT，Doc2Vec，Code2Vec和CC2Vec——作为基线模型生成学习嵌入。
3 实验评估
3.1 指标
召回率。作者采用Tian等人在评估他们的BATS系统所使用的召回率（Recall）的定义。其中 TP 表示真阳性，FN表示假阴性，FP表示假阳性，TN表示真阴性。本文采用的召回率可以细分为两类：
+Recall衡量识别正确补丁的程度，即识别到的正确补丁占所有正确补丁的比率。
-Recall衡量滤掉错误补丁的程度，即过滤掉的错误补丁占所有错误补丁的比率。
准确性和精度。本文采用的数据集的正负样本的比例是平衡的（1.3：1）。因此，作者采用准确性和精度来评估方法对补丁进行分类的性能。
曲线下面积(AUC)和F1度量。作者以学习嵌入和工程特征为输入样本训练了一些基于机器学习的分类器。为了评估这些分类器，作者使用两个常用的指标——AUC和F1度量——来量化分类器在补丁正确性验证任务中的性能。
RQ-1错误代码和修复代码与原代码片段相似性
目标：本研究问题探究不同学习嵌入获取代码片段和修复片段相似点的能力。作者针对两个子问题开展实验，综合回答RQ-1：
RQ-1.1 在嵌入的层面，正确修复的代码与错误代码是否类似？
RQ-1.2 错误代码在多大程度上比错误修补的代码更类似于正确修补的代码？
RQ-1.1的实验设计：作者使用前文提到的四个基线嵌入模型为表2所示的5个修复基准中的36k个补丁片段生成学习嵌入。在那些学习嵌入的基础上，作者进一步计算表示错误和正确修补代码片段的向量之间的余弦相似度。
表2 用于计算错误代码片段和正确代码片段之间相似度分数的补丁数据集
图7 正确修补的代码片段和错误代码片段之间相似度得分的分布
图8 放大正确代码片段和错误代码片段之间相似度得分分布的视图
RQ-1.1的结果：图7展示了具有不同嵌入模型和不同数据集的样本的相似性分布的箱线图。Doc2Vec和code2vec 模型产生了低于BERT 和CC2Vec模型的相似性值。图8进一步聚焦缩放每个嵌入模型实验的箱线图区域。不难观察到，当用BERT嵌入补丁时，Defects4J 数据集中补丁的相似性分布类似于Bugs.jar和Bears数据集，但与数据集ManySStBs4J 和 QuixBugs不同。作者通过Mann-Whitney-Wilcoxon（MWW）检验证实Defects4J、Bugs.jar和Bears的中位数分数的相似性确实具有统计学意义。MWW 测试进一步证实了 Defects4J 和 MostSStBs4J/QuixBus分数之间差异的统计显着性。
RQ-1.1的结论：有错误和正确修补的代码片段的学习嵌入显示出高余弦相似度分数；通用预训练的BERT自然语言模型比专门用于代码更改的CC2Vec模型捕获更多的相似性变化。
RQ-1.2的实验设计：为了比较正确修补代码片段与错误修补代码片段的相似度分数，作者考虑将数据集与正确的补丁和具有错误补丁的数据集相结合。作者使用了Liu等人发布的数据集，包含16个修复工具为184个Defects4J缺陷生成的674个神似（Plausible）但并不正确的补丁。
RQ-1.2的结果：图9显示了正确补丁和错误补丁的余弦相似度分数的分布。由于对于使用的184个正确的Defects4J 补丁，code2vec未能解析最相关的代码片段。因此，作者将比较重点放在其他三个嵌入模型上。总体而言，作者观察到正确修补和错误修补的代码片段的余弦相似度分数的分布有很大不同。该差异在MWW检验证实中值具有统计学意义。
图9 不正确补丁和正确补丁中代码片段的相似度得分分布比较
RQ-1.2的结论：使用 BERT、CC2Vec和Doc2Vec 学习代码片段的嵌入产生相似度分数，给定一个错误的代码，正确修补的代码和错误修补的代码之间存在很大差异。该结果表明，可以利用相似度分数来区分正确的补丁和不正确的补丁。
RQ-2：基于相似阈值过滤不正确的补丁
表3 Bears+Bugs.jar+Dects4J正确斑块相似度得分分布统计
目标：根据与第一个研究问题发现，作者认为可以以截止相似性分数为基准过滤掉部分不正确的候选补丁，因此RQ的主要目标就是探索通过截断值过滤不正确补丁的可行性。
实验设计：作者给予RQ-1实验中相似度分数的分布选取截断阈值。表3总结了正确补丁的相似度分数分布分布分布相关的统计数据。鉴于先前实验中补丁不正确的差异，作者选择使用第一个四分位数值作为推断的阈值。
结果：通过将修补代码和错误代码之间具有最高（Top-1）相似度分数的补丁视为正确，本文提出的方法能够分别帮助BERT、CC2Vec、Doc2Vec额外识别出10%、9%、10%的正确补丁。总体上，本文提出的方法还将正确分类错误补丁的准确率达96%，错误分类正确补丁的概率只有1.5%
RQ-2结论：构建余弦相似度分数，代码片段学习嵌入可以帮助过滤掉 CC2Vec 的 31.5% 和错误补丁的 BERT的94.9%之间的34.9%。虽然 BERT实现了过滤错误补丁的最高召回率，但它产生的学习嵌入导致识别正确补丁的召回率较低（5.5%）。
RQ-3：使用监督学习实现正确补丁分类
目标：本RQ的目标是探究使用机器学习算法推断联合学习嵌入和工程特征提升补丁预测正确性的可行性。为此，作者构建了一个补丁正确性预测框架Leopard，并从以下三个子问题入手检验Leopard的有效性：
RQ-3.1 Leopard能否通过基于代码学习嵌入训练分类器来预测补丁的正确性?
RQ-3.2 Leopard最先进的动态分类方法（如PATCH-SIM)相比可靠性如何？
RQ-3.3 Leopard 的学习嵌入在多大程度上提供了与工程特征不同的预测结果？
RQ-3.1 的实验设计：为了执行实验，作者首先组织了一个有标数据集。为此，作者依托文献中的标记数据集，从三个独立的团队提供的数据集中收集了标记补丁。作者总共收集了2,687个补丁，删除重复项后，剩下2,244个补丁。其中97个补丁未能获得到工程特征。最终，本研究构建了一个包含2,147个有标补丁数据的数据集，如表4所示。遵循文献中的相关工作，作者使用10轮交叉验证方案将本文方法和SOTA作比较。
表4 用于评估基于机器学习的补丁正确性预测器的数据集
RQ-3.1 的结果：表5显示了10组交叉验证设置的结果，报告了用于评估预测变量的所有经典指标：准确度、精度、召回率、F1-Measure、曲线下面积。应用于BERT 嵌入的 XGBoost在大多数指标上都产生了最佳性能,而DNN在精度上实现了最佳性能。
表5 Leopard中六个ML分类器的学习嵌入评估
RQ-3.2的实验设计：PATCH-SIM是预测APR工具补丁正确性方面最先进的工作，是一种基于动态的方法，使用新的生成测试生成修补程序的执行轨迹。作者将PATCH-SIM应用于本问题的数据集上。然而，PATCH-SIM 只能在649个补丁执行。为了避免比较中的潜在偏差，作者使用Leopard对649个补丁进行了独立实验。
RQ-3.2的结果：表6展示了预测补丁正确性的比较结果。在召回方面，PATCH-SIM实现了78.9%，略高于Leopard的BERT嵌入+随机森林。然而，PATCH-SIM的准确率、精准度、和AUC测量分别仅为38.8%、24.7% 和 52.8%，远不如Leopard
表6 将 Leopard (BERT Embedding + ML 分类器) 与 PATCH-SIM 的评估进行比较
RQ-3.2的结论：在学习嵌入上训练的Leopard的ML预测器发现的正确补丁与最先进的PATCH-SIM互补。在过滤掉错误补丁方面，Leopard模型甚至优于PATCH-SIM。
RQ-3.3 的实验设计：因此，在本研究中，作者使用来预测更大数据集上的正确补丁，基于2,147个补丁，使用10组交叉验证开展实验。
RQ-3.3的结论：使用工程特征的ML分类器可以在识别补丁正确性方面达到与基于嵌入的分类器相当的性能。然而，在这两种情况下都有可能提高预测性能，因为它们的正确预测并不完全重叠：学习嵌入导致识别未使用工程特征召回的正确/不正确的补丁，反之亦然。
RQ-4：结合学习嵌入和工程特征，以更准确地分类正确的补丁
目标：根据先前研究问题的见解，将工程特征与学习嵌入进行了比较，作者探究能够通过结合两个特征集来优化正确补丁预测。
实验设计：在这项研究中，作者研究了三种不同的方法，包括集成学习、朴素向量链接和深度组合，并实现在Leopard的升级版本Panther中。
表7 比较将正确补丁与组合特征分类为单一特征的结果
结果：表7显示了使用组合特征与使用单个特征集时正确性识别的性能比较。比较关注三个主要指标：+Recall、-Recall和AUC。对于+Recall（即回忆正确的补丁），具有集成学习的随机森林和基于 XGBoost的分类器在83.7%下获得了最高的值，比单个特征集提高了1到6个百分点。关于-Recall，最好的分类器是基 DNN的特征的深度组合，实现了最高的召回率。关于 AUC，基于XGBoost的集成学习分类器在82.2%下表现出最佳性能，提高了2-5个百分点，
RQ-4的结论：利用学习嵌入和工程特征有助于提高预测 APR 工具补丁正确性的性能。与每个单独的分类器相比，独立训练的分类器合并实现了更高的性能，但不会增加分类器无法识别的正确/不正确的补丁。
RQ-5：解释为何组合特征能够改进补丁预测效果
目标：作者在RQ中使用可解释机器学习技术分析使用特征的贡献。在本研究中，作者聚焦于Shapley值，能够量化每个特征的贡献。。
实验设计：作者考虑使用 XGBoost学习算法训练分类器的情况。使用 SHAP 值作为特征重要性的度量，作者研究了有助于组合模型预测的最重要特征。作者进一步将这些重要特征与分类器仅使用学习嵌入或仅使用工程特征进行训练时贡献最大的特征进行比较。最后，作者提出了由不同特征集识别的三个特定补丁，以观察特征对预测的贡献。
图10 结合学习嵌入和工程特征构建的分类器的前 10 个贡献特征（基于SHAP值）
结果：图10展示了前10个贡献最大的特征。名为 B-i的特征指的是使用BERT 学习的i个特征。在贡献最大的特征中，来自学习和工程特征集的特征的出现表明这两种类型的特征不仅相关，而且在生成的分类器中也得到了利用。
RQ-5的结论：根据SHAP解释的结果，作者能够确认组合工程和学习特征集会产生影响分类器预测的交互，从而提高正确性预测中的精度和召回率。
转述：钱瑞祥
