分享一篇关于补丁正确性验证相关的论文，来自ACM Transactions on Software Engineering and Methodology的论文，题目为Context-Aware Code Change Embedding for Better Patch Correctness Assessment。**它，开源了！**https://github.com/Ringbo/Cache
尽管能够成功地修复越来越多的实际错误，现有的APR（Automated Program Repair，自动程序修复）技术仍然受到长期存在的过拟合问题的挑战，即：生成补丁能够通过所有测试，但实际上是不正确的。在现有的APCA（Automated Patch Correctness Assessment自动补丁正确性评估）技术中，动态APCA技术所需的时间成本很高，因为要执行test cases；静态APCA的准确性一直是个问题。因此，各种嵌入方法被提出，通过嵌入从生成的补丁的变更代码中提取的令牌序列来评估补丁正确性。然而，现有技术很少考虑生成补丁的上下文信息和程序结构，而这些信息对于补丁正确性评估至关重要。在本文中，作者提出了一种基于深度学习的APCA方法Cache ，该方法基于一种考虑程序结构的、上下文敏感的代码变更嵌入方法。
对于如图1所示的代码补丁示例，现有的基于表征学习的方法，比如CC2Vec，会将整行视为一个token序列并嵌入每个token来分别处理添加和删除的行。也就是说，对于第5行的bug代码行，会将其单独转换成token序列[int, len, =, thisBuf, length, -, strLen]；对于第6行的补丁代码，会将其单独转换成token序列[int, len, =, size, -, strLen, +, 1]。这种方法存在两个缺点：
缺点1：没有考虑代码行的上下文信息（同一个方法中有关的其他代码行）。这些信息非常重要，因为文章[1]表明，针对AST节点类型，在不同的上下文中，为修复bug而更改代码的频率有很大差异。例如，在Method Declaration的上下文中，插入Expression Statement的频率比If Statement高十倍。对于图1所示的代码片段，如果没有变量size的类型和值信息，我们很难判断此修改是否正确。但是，如果可以考虑第1行，我们将获得"变量size与strLen具有相同类型"这一知识。此外，如果考虑第9行，我们会知道"变量strLen是一个整数"。这些关于补丁环境的事实可以帮助我们更好地理解代码变化，从而便于我们更精确地嵌入补丁。
缺点2：程序结构信息的丢失。当前的技术将语句视为一个token序列，并分别嵌入每个token。然而，以同样的方式对待程序中的关键字和其他token（例如，变量名），则可能会忽略token的特定功能，从而忽略程序的内在结构。例如，iIF和For这样的关键字表示条件语句或循环体的开始。文章[2]的研究结果表明，错误元素的自然性（naturalness）在各种类型的语句中是不同的。也就是说，对于不同的语句类型，在特定补丁中采用修复动作（例如，添加、删除或替换）的频率是不同的。具体来说，超过一半的赋值语句需要代码替换来修复bug，而条件语句的相应比例低于40%。
为克服上述两个问题，本文：
（1）使用code diff工具[2]来分离bug方法中的已更改和未更改部分，其中整个未更改部分被用作上下文。在图1所示的例子中，作者将该方法中除第5行和第6行之外的所有其他行都视为上下文。这样做可以对第1行和第9行的信息进行编码，以帮助更好地进行补丁正确性评估。
（2）使用AST路径[3]（Code2Vec模型）来嵌入补丁，这在很大程度上保留了原始程序的结构，因为AST路径中的任何两个连续节点都与解析的AST中的父子关系是固有的。
Cache的框架如图2所示。在介绍框架之前，需要说明文章中的两个定义：
定义1：AST。一个代码片段的AST被定义为元组<N, L, T, r, Ω, Ψ>。N：非叶子节点集；L：叶子节点集；T：L的token集；r∈N，表示root节点；Ω：N→(N∪L)*，用于将非叶子节点映射到它们的子节点；Ψ：L→T，用于将叶子节点映射到对应的token。
定义2：AST path。AST path被定义为节点序列，，。对于每一个连续的节点对和，总能够保证或。也就是说，AST path是指通过一系列非叶子节点连接两个叶子节点的路径。
接下来对图2进行详细解释。模型已bug方法和patch方法作为输入，识别出有bug的子树及其对应的修复子树。bug方法AST的其余子树被是作为独立的部分以作为上下文信息。本文采用基于AST的代码表征方法对AST进行嵌入，然后使用五个预定义的函数来集成表示，进一步使用基于深度学习的分类器来生成最终结果。
给定bug方法和patch方法对，首先使用Gumtree工具生成AST。接着通过AST diff工具定位中已经更改（更新或删除）的节点和在中新增的节点，以此来确定二者的共同祖先节点N。也就是说，根节点是N的中的子树被认为是bug子树，根节点是N的中的子树被认为是patch子树，而中剩余节点被认为是提供上下文信息的单独的树。因此，对于一个方法对，Cache生成3个AST，分别是：、和。
如图3所示，补丁修改了VariableDeclaration语句中的BinaryExpression。Cache首先识别高亮（红色）的VariableDeclaration节点为祖先节点，而其余蓝色椭圆形节点被视作为，左边的红色椭圆型节点被视作为，右边的红色椭圆型节点被视作为。图中的蓝色虚线表示AST path。
对于、和，首先使用PatchMiner[4]从三者中提取全部的AST path。如果两个AST节点中有多条路径，则选择节点数最少的一条[5]。同时，采集叶子节点的token以作为嵌入的特征，因为代码token保留了来自原始程序的语义信息（如，变量的名称），并且已经被证明可以帮助提高基于AST路径的模型的精确率和召回率[6]。
接着，使用如图4所示的框架进行AST path嵌入。给定一个AST path，首先对两个叶节点的token和整个AST path进行编码，以生成AST path的表示。然后，利用原始AST中所有AST路径的向量表示，通过注意力模型自动学习每条路径上的注意力权重，并生成整个AST的向量表示。注意机制用于动态选择这些AST path上的分布。
AST path和token嵌入。 首先，根据驼峰（camel case）命名法和下划线（underscore）命名法对token进行sub-token划分。使用一个学习矩阵（我也没看懂这是个啥，反正就叫learned matrix）来嵌入sub-token。所有sub-token的向量之和作为token的向量。同时，还基于节点类型构建了一个AST嵌入矩阵（是不是指训练词向量？）。接着，将向量化后的AST path序列中的节点送到Bi-LSTM中，以输出AST path表征向量。最后，将两个叶子节点的token向量和AST path表征向量拼接以最为最终的AST path表征。
AST path嵌入部分的形式化表达如下（公式实在难敲，看原文吧，反正我是看懂了的）。这里插一句，刚开始我一直没太理解和的作用，后来回顾两个定义和图3发现：本文提到的token是指叶子节点中的代码内容（也就是图3中的矩形框，图4中的红色向量），而则是用来嵌入节点类型的（图4中的绿色向量），对应图3中的椭圆形节点。
**基于注意力机制的特征提取。**对于给定的AST path表示，使用全连接层和注意力机制，将它们聚合成整个一个向量（），以表示整个AST。实际上就是将AST中所有AST path的表征经过注意力机制收成一个向量，以表示整个AST。
形式化表达还是直接看原文吧。
这里提出一个疑问，下图的第一句提到：通过比较生成的补丁与原始存在bug的补丁进行比较，以判断其正确性。但是，后一句却解释到：需要给定的是bug和patch方法的向量表示。所以第一句应该说的是：比较patch和bug吧？
给定的两个向量：（bug方法的表征向量）和（patch方法的表征向量），通过如下5中方法对二者进行整合，以从不同角度刻画它们之间的差异性：
（1）：元素层面的加操作，即和相加。
（2）：元素层面的减操作，即和相减。
（3）：哈达玛乘积操作，即和之间做哈达玛乘积。
（4）：余弦相似性操作，即和之间的相似性。
（5）：双线性模型，由Tanenbaum等人[7]提出，用于有效整合两个向量之间的特征。
上面5中方法分别能够得到5个向量，接着将它们进行连接，如公式（3）所示。
如果对一个bug的修改涉及多个方法，则将每一个函数的相加以表示整个补丁。
本文所用的分类器由两个全连接层+softmax组成，损失函数如下：
其中，表示分类为补丁是不正确的概率。
下面是本文的部分实验结果，感兴趣的小伙伴可以阅读原文部分，写得确实挺不错的，思路新颖，描述简洁易懂。
参考文献
[1] Wen M, Chen J, Wu R, et al. Context-aware patch generation for better automated program repair[C]//Proceedings of the 40th international conference on software engineering. 2018: 1-11.
[2] Liu K, Kim D, Koyuncu A, et al. A closer look at real-world patches[C]//2018 IEEE International Conference on Software Maintenance and Evolution (ICSME). IEEE, 2018: 275-286.
[3] Alon U, Zilberstein M, Levy O, et al. code2vec: Learning distributed representations of code[J]. Proceedings of the ACM on Programming Languages, 2019, 3(POPL): 1-29.
[4] Kovalenko V, Bogomolov E, Bryksin T, et al. Pathminer: a library for mining of path-based representations of code[C]//2019 IEEE/ACM 16th International Conference on Mining Software Repositories (MSR). IEEE, 2019: 13-17.
[5] Alon U, Zilberstein M, Levy O, et al. A general path-based representation for predicting program properties[J]. ACM SIGPLAN Notices, 2018, 53(4): 404-419.
[6] Alon U, Brody S, Levy O, et al. code2seq: Generating sequences from structured representations of code[J]. arXiv preprint arXiv:1808.01400, 2018.
[7] Tenenbaum J B, Freeman W T. Separating style and content with bilinear models[J]. Neural computation, 2000, 12(6): 1247-1283.
