基于失败测试用例相似性的补丁正确性预测

原文标题：Sredicting Patch Correctness Based on the Similarity of Failing Test Cases
原文作者：Tian H, Li Y, Pian W, et al
原文链接：https://dl.acm.org/doi/full/10.1145/3511096
发表期刊：ACM Transactions on Software Engineering and Methodology 2022
笔记作者：zhanS@SecQuan
笔记小编：cherry@SecQuan

分享一篇写在安全学术圈中的论文笔记，关于补丁正确性研判。该论文实验代码已开源：https://github.com/HaoyeTianCoder/BATS

可以通过检查每个生成的补丁是否实现了与它所解决的bug相关的代码更改（即：行为）来研判其正确性。这种bug通常是由失败的测试用例指定的。为了预测APR（Automated Program Repair）中的补丁正确性，本文提出了一个新颖而简单的假设，即：如何在补丁行为和失败测试明细（test specification）之间建立联系，也就是说相似的失败测试用例应该需要相似的补丁。因此，本文提出BATS，一种基于无监督学习的方法，通过对照失败的测试明细检查补丁行为来预测其正确性。

作者在文章中提到，现有补丁正确性研判存在如下两个问题：

（1）基于动态的方法需要执行测试用例，这是昂贵的。同时，受到oracle问题的挑战：给定一个测试用例，我们并不总是有一个准确的明细来规定输出应该是什么[1]。

（2）基于静态的方法通常需要大量的分析工作来识别足够的特征和属性。此外，基于机器学习的方法还需要许多标记的补丁样本。

本文的一个关键假设是：

当不同的程序无法通过类似的测试用例时，表明这些程序很有可能需要进行类似的代码更改。

因此，本文面临的一个关键挑战是：

句法相似性仅能针对1型或2型克隆（这里为啥会突然出现"克隆"呢？我感觉作者应该是想表达不同类型的代码相似性吧）。必须探索能够捕捉语义关系的相似性度量。

这篇文章的contribution写法有触及到我的知识盲区了，有意思。

值得参考！

本文所提模型BATS的框架如图1所示，该方法的核心是基于新补丁与已知正确补丁的相似性来预测补丁正确性。该方法的输入包括：（1）需要解决的bug，与之相关的失败测试用例，APR生成的看似合理的补丁；（2）历史bug，失败测试用例以及正确补丁。BATS的执行流程如下：

（1）对补丁和测试用例进行预处理；

（2）对补丁和测试用例进行向量化；

（3）计算待解决bug的失败测试用例与历史测试用例之间的成对相似度；

（4）选择最多top-k个相似性得分大于（应该指的就是上一步中的成对相似度）的历史测试用例，并将它们映射到其相关联的正确补丁；

（5）计算选定的历史已知正确补片之间的平均相似性；

（6）计算正在解决的bug的每个看似合理的补丁和来自前一步骤的已知正确补丁的平均相似度之间的成对相似度；

（7）如果看似合理的补片与正确补片的平均相似度（来自步骤5）的相似度大于某个阈值，则将该补片预测为正确的，否则BATS将该补片预测为不正确的。

（1）预处理

对测试用例进行token化。 将单个测试方法的源代码视为token序列，同时还使用驼峰命名法将token进一步分解为子token。

对补丁进行token化。 对补丁的token化方法与对测试用例的token化方法相同。但是，BATS考虑改变的行而不考虑它们的上下文，即：它只选择添加和删除的行，分别用+和-标记。为了保留关于添加和删除的行的信息，BATS保留+和-标记作为每个patch的一部分。

（2）嵌入

补丁的嵌入比较复杂。补丁由几个单独的块组成，而块的顺序与补丁无关。每个块可以作为一系列token嵌入到一个向量中。但是，如何将不同的块组合起来以获得一个表示整个片的向量呢？不同块的向量的简单连接不会产生唯一的向量。因为各个块没有特定的顺序，不同块的不同顺序会导致同一个补丁有不同的向量。因此，作者对不同块的向量求和以获得代表整个片的唯一向量，而不是连接不同块的向量。

为实现嵌入，BATS考虑了3种预训练模型：

• code2vec：用于嵌入测试用例。

• CC2Vec：用于嵌入生成的补丁。

• BERT：对于综合实验，使用BERT进行补丁嵌入？这里感觉没说明白，等看看后面怎么解释吧。

（3）查找相似的测试用例

BATS的主要假设是：相似的失败测试案例有相似的关联补丁。因此，该方法的第三步是从历史修复的错误中找到相似的测试用例，即：在应用相关修复之前失败的测试用例，并且与正在解决的当前bug的失败测试用例相似。（这一句是"即"字前面提到的"测试用例"一词的从句）

因此，BATS对待解决bug的每一个失败的测试用例，计算其与BATS在搜索空间中找到的所有测试用例之间的成对相似性。具体来说，通过计算测试用例在code2vec嵌入后的欧几里得距离以衡量他们之间的相似性。相似性域值设置为。BATS选择相似性大于的前k个测试用例。需要注意的是，历史失败测试用例不需要来自正在解决的bug的同一个项目的历史。

（4）失败测试用例与补丁映射

在找到一系列相似的失败测试用例后，需要将这些历史失败测试映射到它们相关联的正确补丁。在这部分，BATS基于假设：如果待解决bug的看似合理的补丁与这些历史上正确的补丁相似，那么它就是正确的，因为它们失败的测试用例也是相似的。为了便于将似是而非的补丁与这些历史上正确的补丁进行比较，BATS通过计算它们的嵌入向量的平均值来对历史上正确的补丁进行平均。

（5）补丁正确性预测

对于目标补丁，BATS计算其与上一步获取的历史上正确的补丁的平均值之间的相似性（通过欧几里得距离和余弦相似性衡量）。这里预定义一个阈值，如果相似性大于阈值，则被认为是正确的。

（6）示例

考虑来自Defects4J数据集的Chart-26，该bug导致22个测试用例失败。为修复这个错误，APR工具SOFix和KaliA分别生成了图2和图3所示的两个貌似合理的补丁。

首先，为了判断两个补丁是否正确，BATS在可用的搜索空间中查找与22个失败测试用例相似的测试用例。搜索空间包括Chart项目以及其他项目（如果可用）的历史记录。其次，由于是基于code2vec的相似性进行判断，BATS识别出两个与这22个失败测试中某几个相似性的测试用例：一个测试用例与bug Chart-4相关联，另一个与bug Chart-25相关联。作者对这两个测试用例进行人工分析后发现它们确实旨在检测未处理的空指针解引用。接着，在BATS将两个已识别的历史测试用例映射到相应的正确补丁后，它测量APR生成的补丁与这些相关正确补丁的相似度。最后，基于相似度评分和相似度阈值，BATS分别准确预测了SOFix和KaliA生成的补丁是正确的和不正确的。作者在手动检查应用于Chart-4（参见图4）和Chart-25（参见图5）的修复的历史正确补丁时，发现它们都实现了与SOFix建议的补丁（参见图2）相似的行为(即添加null检查)。相反，KaliA补丁（参见图3）则是建议进行无关的代码更改。

这篇文章进行了大量的实验来证明所提方法的有效性，这里就不再一一阐述，感兴趣的童鞋可以阅读原文。总的来说，这篇文章的核心就是相似性比较。通过找到与待解决bug失败的测试用例相似的测试用例，并将它们关联到正确的补丁；进一步基于这些补丁计算与ARP生成的补丁之间的相似性，进而判断ARP生成的补丁是否正确。

参考文献

[1] Tsimpourlas F, Rajan A, Allamanis M. Learning to encode and classify test executions[J]. arXiv preprint arXiv:2001.02444, 2020.

安全学术圈招募队友-ing 
有兴趣加入学术圈的请联系 secdr#qq.com