利用静态提取的代码特征对过拟合补丁进行自动分类

原文标题：Automated classification of overfitting patches with statically extracted code features
原文作者：Ye H, Gu J, Martinez M, et al. 
原文链接：https://ieeexplore.ieee.org/abstract/document/9399306/
发表期刊：IEEE Transactions on Software Engineering
笔记作者：zhanS@SecQuan
笔记小编：cherry@SecQuan

一定是特别的缘分，让我从茫茫文海中发现了你->补丁合理性检测。

分享一篇我写在安全学术圈的论文阅读笔记，来自IEEE Transactions on Software Engineering的论文，题目为"Automated Classification of Overfitting Patches with Statically Extracted Code Features"。

自动程序修复（Automated Program Repair，APR）旨在降低手动修复软件缺陷的成本。然而，APR生成可能会生成大量过度拟合补丁，这些补丁除了使测试通过之外，并不能正确地修复缺陷。过拟合补丁问题导致生成的程序修复补丁价值低，严重影响了程序修复在实践中的适用性。因此，本文提出了一个名为ODS的模型（缘分呀，这不就是上一篇阅读笔记提到的模型吗？众里寻他千百度），用于检测过拟合补丁。ODS基于这样的假设，即：可以跨程序修复系统和跨软件项目进行过拟合补丁检测，因为存在捕获用于分类过拟合补丁的通用正确性属性的代码特征。

ODS模型的检测流程如图1所示，包括两个部分：训练和预测。

（1）训练阶段： ODS将一组有bug的代码及其对应的修补代码作为输入，每个代码都有一个正确性标签：过拟合或正确。ODS执行静态分析，提取出bug代码和补丁代码之间的AST差异，这些差异被编码为特征向量。对于每对源代码，ODS提取三类代码特征来形成特征向量。然后，训练监督学习模型。

（2）预测阶段： 对于一个新的补丁，首先以与训练补丁相同的方式提取代码特征。然后，将提取的代码特征输入ODS模型。对于每个补丁，ODS输出一个概率分数，表示其正确性的可能性。

给定一对有bug和打过补丁的源代码文件，首先计算每个受补丁影响的源代码文件的AST，然后在这些AST上执行AST差分算法。这将计算得到一组AST操作（称为edit-script），用于捕获一个AST（bug文件）到另一个AST（补丁文件）之间的转换。本文称这个列表为“AST diff”。接着，将AST diff转换成定长向量。对于一个补丁影响两个以上文件的多个AST diff（这意味着补丁修改不同的文件来修复错误），本文从每个AST diff中积累每个特征向量的发生情况（这是啥？），进而得到一组固定长度的特征向量，用以表示修复错误代码的补丁。

ODS提取的特征分为三类：代码描述特征、修复模式特征和上下文句法特征，分别如表1，2和3所示。

• 代码描述特征： 在表1中，作者给出了四类50个代码描述特征（这些特征都是二值特征）：

• 操作符：提取补丁代码中的一元、二元、按位和关系预算操作符。

• 变量：提取补丁代码中涉及的变量信息，如：作用域和类型。

• 语句：提取被补丁代码所影响的语句类型，如：控制流、赋值、引用、返回等。

• AST操作：通过结合a）4类AST层面的AST diff操作，包括：UPD（update）、ADD（add）、DEL（delete）和MOV（move）和b）被这3类操作所影响的代码元素，以提取AST操作特征。

例如，insertStmt特征表示补丁代码通过插入一条语句以对bug进行修复。

同时，ODS还从补丁周围的语句中提取特征。具体来说，考虑a）被修改的语句（称之为SRC特征），b）在被修改的语句之前的同一个代码块中最多3条语句（称之为FORMER特征），c）在被修改的语句之后的同一个代码块中最多3条语句（称之为LATTER特征）。

这样一来，对于每个补丁，ODS考虑的代码描述特征就有150个，SRC的50个特征+FORMER的50个特征+LATTER的50个特征。

• 补丁模式特征： 为了帮助ODS学习补丁的****语义信息，作者还引入了由人类专家提取的修复模式，也就是使用Sobreira等人[1]的修复模式分类法，基于对395个Defect4j人工编写的补丁的手动分析，它定义了修复模式和操作的列表。ODS集成了来自文章[2]的26种修复模式。表2给出了ODS考虑的26种修复模式。

• wrap系模式：在一个条件分支、try-catch、循环中是否包含缺陷语句。例如：wrapsIf表示潜在的bug语句存在于if条件分支中。

• exp系模式：出现在修改现有逻辑或算术表达式、返回表达式或布尔变量赋值的补丁中。

• cond系模式：添加或删除条件块。

• null系模式：与添加条件表达式或使用空检查扩展现有的条件表达式有关，包括正空检查（检查是否为空）和负空检查（检查是否为非空）。

• 其他模式：如，在不同的位置重复相同的更改（例如，copyPaste）；将现有代码移动到不同的位置（例如，codeMove）；删除或替换单行（例如，singleLine）等。

• 上下文句法特征： 表3给出了ODS中考虑的26个上下文语法特征。

• type相关特征：主要关注被修改语句的类型及其周围代码和父代码的类型。type特征是字符串类型的。例如，一条存在问题的语句的类型（typeOfFaultyStatement）可以是assignment，它的父语句的类型（typeOfFaultyStatementParent）可以是method或class。

• method特征：描述与方法调用相关的上下文，方法调用是否发生在try-catch块中。

• 相似性特征：描述在作用域中是否存在具有相同类型（例如，对象类型或基本类型）的对象或方法调用。

• 使用特征：关注类中是否存在从未使用或赋值的字段或变量。

接下来是特征向量化。需要注意，字符串类型的特征使用one-hot进行编码。对于来自一个补丁的多个AST差异，我们从每个AST差异中聚合每个特征的对应值。

图2的用处来了！！！ 图中灰色节点表示AST diff（也就是patch），ODS从被这些节点影响的节点上提取特征。对于这个补丁，提取的代码描述特征包括：opEqual（二元操作符“==”），uopDec（一元操作符“-”），localVar（局部变量temp），如图中绿钩表示。对于其他特征，如assingZero和opAdd，则没有被捕获，如图中红叉表示。同样的，ODS还从改变的AST的前后（图中的虚线箭头）提取代码描述特征。对于补丁模式特征，ODS只提取了两个，即wrapsIf和condaBlockOthersAdd。所有的特征都被转换成图2底部的向量表示（最后一列阶段了是不是，哈哈）。

在实现部分，ODS的分类器使用的是XGBoost。使用Coming[3]提取代码描述特征和上下文语法特征，使用ADD[4]提取代码修复模式特征。这两个根据的内部都使用GumTree[5]来提取AST diff。

这篇文章实验部分的开头概述值得学习。直接放图。

下面到了大家最关心的数据集时间。本文所用的数据集包括两个部分，一个是来自文章[6]的有标签数据集和来自文章[7]的无标签数据集。

在表5所示的3个基准测试中，存在数据不平衡问题。作者采用了SMOTE的少数策略，即只对正确的补丁重新采样到相同数量的过拟合补丁。

下面是一些我认为有意思的实验结果。这篇文章写得真不错，除了我没有太理解“从每个AST diff中积累每个特征向量的发生情况”，值得细品，哈哈。

参考文献： 

[1] Sobreira V, Durieux T, Madeiral F, et al. Dissection of a bug dataset: Anatomy of 395 patches from defects4j[C]//2018 IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE, 2018: 130-140.

[2] Madeiral F, Durieux T, Sobreira V, et al. Towards an automated approach for bug fix pattern detection[J]. arXiv preprint arXiv:1807.11286, 2018.

[3] Martinez M, Monperrus M. Coming: A tool for mining change pattern instances from git commits[C]//2019 IEEE/ACM 41st International Conference on Software Engineering: Companion Proceedings (ICSE-Companion). IEEE, 2019: 79-82.

[4] Madeiral F, Durieux T, Sobreira V, et al. Towards an automated approach for bug fix pattern detection[J]. arXiv preprint arXiv:1807.11286, 2018.

[5] Falleri J R, Morandat F, Blanc X, et al. Fine-grained and accurate source code differencing[C]//Proceedings of the 29th ACM/IEEE international conference on Automated software engineering. 2014: 313-324.

[6] Wang S, Wen M, Lin B, et al. Automated patch correctness assessment: How far are we?[C]//Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering. 2020: 968-980.

[7] Durieux T, Madeiral F, Martinez M, et al. Empirical review of Java program repair tools: A large-scale experiment on 2,141 bugs and 23,551 repair attempts[C]//Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2019: 302-313.

‍

‍