代码特征自动提取方法
史志成1,2，周
宇1,2,3+
1.南京航空航天大学计算机科学与技术学院，南京210016
2.南京航空航天大学高安全系统的软件开发与验证技术工信部重点实验室，南京210016
3.南京大学软件新技术国家重点实验室，南京210023+通信作者E-mail:*************** 摘
要：神经网络在软件工程中的应用极大程度上缓解了传统的人工提取代码特征的压力。已有的研究往往
将代码简化为自然语言或者依赖专家的领域知识来提取代码特征，简化为自然语言的处理方法过于简单，容易造成信息丢失，而引入专家制定启发式规则的模型往往过于复杂，可拓展性以及普适性不强。鉴于以上问题，提出了一种基于卷积和循环神经网络的自动代码特征提取模型，该模型借助代码的抽象语法树（AST ）来提取代码特征。为了缓解因AST 过于庞大而带来的梯度消失问题，对AST 进行切割，转换成一个AST 序列再作为模型的输入。该模型利用卷积网络提取代码中的结构信息，利用双向循环神经网络提取代码中的序列信息。整个流程不需要专家的领域知识来指导模型的训练，只需要将标注
类别的代码作为模型的输入就可以让模型自动地学习如何提取代码特征。应用训练好的分类编码器，在相似代码搜索任务上进行测试，Top1、NDCG 、MRR 的值分别能达到0.560、0.679和0.638，对比当下前沿的用于代码特征提取的深度学习模型以及业界常用的代码相似检测工具有显著的优势。
关键词：代码特征提取；代码分类；程序理解；相似代码搜索文献标志码：A
中图分类号：TP391
Method of Code Features Automated Extraction
SHI Zhicheng 1,2,ZHOU Yu 1,2,3+
1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
2.Key Laboratory for Safety-Critical Software Development and Verification,Ministry of Industry and Information Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
3.State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China
Abstract:The application of neural networks in software engineering has greatly ead the pressure of traditional method of extracting code features manually.Previous code feature extraction models usually regard code as natural language or heavily depend on the domain knowledge of experts.The method of transferring code into natural
计算机科学与探索
1673-9418/2021/15(03)-0456-12doi:10.3778/j.issn.1673-9418.2005048
基金项目：国家重点研发计划（2018YFB1003902）；国家自然科学基金（61972197）；中央高校基本科研业务费专项资金（NS2019055）；
江苏高校“青蓝工程”。
This work was supported by the National Key Rearch and Development Program of China (2018YFB1003902),the National Natural Science Foundation of China (61972197),the Fundamental Rearch Funds for the Central Universities of China (NS2019055)and the Qing-Lan Project of Jiangsu Higher Education Institutions.收稿日期：2020-05-26
修回日期：2020-07-29
含有马的成语Journal of Frontiers of Computer Science and Technology
史志成等：代码特征自动提取方法
在“大代码”背景的驱动下，如何高效地提取代码特征并对其进行编码以快速地处理海量数据的需求已日益迫切。如今，深度学习在自然语言处理的很多领域已经取得了突破性的进展，人工智能也逐渐从“感知智能”迈向“认知智能”，机器不仅能够感知客观世界所释放的信息，更能够对这些信息像人一样进行理解和分析。Hindle等人[1]已经论证了程序语言和自然语言类似，具备众多可供分析的统计属性，代码语言可以和自然语言一样能够被机器理解和分析。因此，许多学者简单地将代码作为自然语言来处理。例如，代码被表示为一个字符串序列应用在克隆检测[2-3]、漏洞定位[4]以及代码作者分类（code authorship classification）[5]的任务当中。尽管代码和自然语言有很多共性的特征，都是由一系列单词组成且都能表示成语法树的形式，然而代码有许多自己专有的特性，代码具有更强的逻辑结构，自定义的标志符，且标志符之间存在长距离依赖等。简单地将代码视作自然语言进行处理难免会造成信息丢失。为了使模型更适合处理代码语言，部分学者借助软件工程的领域知识，制定了一些启发式规则来静态地提取代码特征，例如在应用程序接口（application programming interface，API）推荐领域，Zhou等人[6]就将用户查询后得到的反馈信息作为构建API向量的一维特征来提高查询效果，然而这些静态提取代码特征的方式有以下三个弊端：
（1）完全依赖研究人员的先验知识来提取特征，所提取的特征数目有限。
用典
（2）当代码库过于庞大和复杂，特征规则的制定也会相应变得复杂，难以适用于对海量且结构复杂的代码数据进行处理。
（3）规则的制定往往是面向特定任务的，可迁移性差。
因此，近几年许多研究使用深度学习模型来自动提取代码的特征[7-10]，以摆脱对人工提取特征的依赖。这些模型很多借助代码的抽象语法树（abstract syntax tree，AST）来提取特征，通过对AST内部节点之间的依赖关系进行提取，来获得代码的结构信息，而不是简单地根据代码的标志符序列提取语义信息。然而这些方法有一个明显的弊端，就是都将树的二维结构转化成一维的序列结构进行预处理，如Alon等人[10]将AST处理成一个路径集合，Hu等人[8]以及White等人[9]直接使用先序遍历的方式获得AST 节点的展开序列作为模型的输入，这些降维的处理方式一定程度上会造成节点之间某些依赖关系的丢失。
因此，为了更充分地提取代码的结构信息，部分学者提出了一些不降维而直接处理AST的树形深度学习模型。如Wan等人[11]使用Tree-LSTM（tree-structured long short-term memory networks）进行注释生成，Mou 等人[12]使用TBCNN（tree-bad convolutional neural network）模型进行代码分类。然而这些树形深度学习模型仍然有两个局限性：（1）与自然语言的长文本类似，在AST规模十分庞大的情境下，很容易在模型的训练过程中出现梯度消失的情况[13-15]，因此无论是Wan等人使用Tree-LSTM或者Mou等人使用的TBCNN
language is too simple and can easily cau information loss.However,the model with heuristic rules designed by experts is usually too complicated and lacks of expansibility and generalization.In regard of the problems above, this paper propos a model bad on convolutional neural network and recurrent neural network to extract code features through abstract syntax tree(AST).To solve the problem of gradient vanishing caud by the huge size of AST,this paper splits the AST into a quence of small ASTs and then feeds the trees into the model.The model us convolutional neural network and recurrent neural network to extract structure information and quence information respectively.The whole procedure doesn t need to introduce the domain knowledge of experts to guide the model training and the model will automatically learn how to extract features through the codes which have been labeled classification.This paper us the task of similar code arch to test the performance of the trained encoder, the metric of Top1,NDCG and MRR is0.560,0.679and0.638respectively.Compared with recent state-of-the-art feature extraction deep learning models and common similar code detection tools,the propod model has significant advantages.
Key words:code feature extraction;code classification;program comprehension;similar code arch
457
Journal of Frontiers of Computer Science and Technology计算机科学与探索2021,15(3)
都会很容易丢失那些存在长期依赖关系节点之间的部分信息。（2）Wan等人使用的Tree-LSTM要将AST 先转化为二叉树再进行编码，该预处理操作破坏了AST原始的结构且转化后树的深度将会大幅增加，加剧梯度消失问题。
本文结合TBCNN以及Zhang等人[16]提出的ASTNN （AST-bad neural network）模型构建了一个基于卷积和循环神经网络的自动代码特征提取模型（convo-lutional and recurrent neural network，CVRNN）。模型的输入是代码的AST，为了提高AST初始词向量的质量，还针对AST设计了一个专门的词向量预训练模型，预训练词向量不仅能提升后面实验部分代码分类以及相似代码搜索的实验结果，还能在模型的训练过程中加速模型的收敛。借鉴ASTNN切割AST的思想，模型并未直接对整棵AST进行处理，而是根据“if”“while”“for”以及“function”这4个代表程序控制块的AST节点将AST切割成一系列子树，再利用TBCNN模型对这些子树进行卷积运算。子树的规模远小于原先的AST，因此可以有效地解决节点长期依赖导致的梯度消失问题。之后，采用双向循环神经网络[17]，内部神经元采用LSTM[18]，来提取代码块之间的序列信息，将每个时间步生成的代码向量存放到一个向量矩阵中，最终采用最大池化得到代码向量。为了验证CVRNN模型生成的代码向量的质量，还在CVRNN模型基础之上设计了两个具体的应用模型，代码分类以及相似代码搜索模型。实验结果表明，CVRNN模型不仅能够高效地自动提取代码的特征，且所提取的特征具有很强的迁移能力，不仅适用于代码分类任务，
其分类训练后得到的编码器在相似代码搜索任务上也有很好的效果。
本文的主要贡献是：
（1）提出了一个基于AST的词向量训练模型。
（2）提出了一个基于卷积和循环神经网络的自动代码特征提取的深度学习模型。
（3）构建了一个高效的用于搜索相似代码的系统，且该项目所使用的数据集以及代码已在github上开源（/zhichengshi/CVRNN）。
1代码特征提取模型
这部分主要分为两个子模型进行介绍：
（1）基于树的词向量训练模型。
（2）基于卷积和循环神经网络的特征提取模型。
1.1基于树的词向量训练模型
词嵌入技术是将自然语言文本中的单词嵌入到低维空间的一种向量表示方法[19]。近几年，许多学者也将该方法成功应用在处理代码的任务中，如API推荐[20-21]、漏洞检测[22]等。然而这些词嵌入技术简单地将代码视为序列化的文本进行处理，往往采用类似Word2vec[23]滑动窗口的方式建立特定单词的上下文情境，并以此为依据来生成相应的词向量，如Zhang 等人[16]就通过先序遍历的方式获得AST的节点序列，然后使用Word2vec生成词向量，而代码元素之间的依赖关系其实是一种二维的树形结构，应用这种方法获取词的情境难免会导致代码的部分结构信息难以编码进最终生成的词向量中。Mou等人[12]在对AST中节点进行编码时只将当前节点的孩子节点作为情境，这种情境信息的提取方式仍然不完备。因此本文借鉴Pérez等人[24]构造树中节点上下文情境的方法，结合当前节点的祖先节点、兄弟节点以及子孙节点作为情境，在提取祖先节点以及子孙节点作为情境的过程中分别设置一个向上以及向下探测的参数来控制提取情境的深度，并设计了一个词向量训练模型根据提取的情境来生成AST节点的词向量。为了提高相似代码搜索的准确率以及提高模型的训练速度，将不考虑AST叶子节点的信息即代码中的标志符信息，因此该模型更侧重于对代码结构信息的提取。相似代码搜索任务使用的数据集来源于leetcode编程网站，代码分类任务所使用的数据集是Mou等人[12]提供的104数据集，该数据集共包含104个类别的代码，每个类别下包含500个样本。在分类训练的过程中并没有使用AST叶子节点的信息，原因有二：（1）由于代码中的标志符是程序员自定义的，而据观察104数据集中的词汇与leetcode上的词汇并不重叠，使用叶子节点反而会引入噪音。（2）leetcode上的代码所使用的变量名仅仅起一个命名的作用并没有语义表示的功能，更多的是采用a、b、temp等不携带语义信
息的单词作为变量名。AST的生成工具使用的是srcml（www.srcml/），该工具不检查代码的正确性，因此即使编译不能通过的代码也能生成AST，提高了模型的容错性。在代码分类以及相似代码搜索的任务中所使用的代码都是C/C++编写的，而srcml用来表示这两种语言所定义的节点只
458
史志成等：代码特征自动提取方法
有60个，加入叶子节点后词汇表的大小将扩充至上万，因此不使用叶子节点将大大提高模型的收敛速度。
图1展示了整个词向量的训练过程。选取节点b 作为当前节点，向上探测寻找祖先节点的深度设置为1，向下探测子孙节点的深度设置为2，因此得到祖先节点情境信息a ，兄弟节点情境信息c ，以及子孙节点情境信息(d ,e ,f ,g ,h )，将这三类情境节点合并得到(a ,c ,d ,e ,f ,g ,h )作为节点b 的情境信息。在模型的训练过程中，首先使用正态分布对词汇表矩阵进行初始化，得到矩阵D ∈R
n ×f
，其中n 表示词汇表
的大小，f 表示词向量的维度。模型的输入分为两部分，情境节点以及当前节点在词汇表中的索引，通过查找词汇表可以得到情境节点以及当前节点的词向量表示，分别对应图1中的context embedding 以及current vector ，之后context embedding 经过两层全连接神经网络得到变换后的情境向量context vector ，使用交叉熵作为损失函数，Adam 作为优化器进行梯度下降。为了使生成的context vector 能够与current vector 进行交叉熵运算，输出层输出向量的维度与词汇表中向量的维度相同。整个计算过程的数学公式如下：
h =tanh(v ∙W 1+b n )y ′=soft max(h ∙W 2)
H y ′(y )=-∑i y ′i ∙lb y i
其中，v ∈R
1×f
表示情境向量，h 表示经过隐层后得
到的输出向量，W 1∈R f ×k
是隐层的权值矩阵，用来将
维度是f 的向量映射成k 维向量，b ∈R
1×k
是隐层网
络的偏置项。W 2∈R
k ×v
是输出层的权值矩阵，y ′∈Rqq炫
1×v
是输出层的输出向量，y ∈R 1×v 是当前节点的词向量，y ′i 表示向量y ′在第i 个维度上的值，y i 同理。
1.2
基于卷积和循环神经网络的CVRNN 模型
1.2.1
AST 切割
为了防止AST 规模过大，带来梯度消失问题。
并未直接将AST 作为模型的输入，而是先将AST 进行切割，得到AST 的子树序列输入到模型之中，详细步骤如下。
首先，定义一个用于存储AST 分裂节点的集合S ={if,while,for,function,unit}。其中“if ”用来提取条件子树，“while ”“for ”用于提取循环子树，“function ”用来提取方法体子树，“unit ”是未切割前AST 的根节点，AST 剩余的节点都在“unit ”子树上，如下展示了具体的切割算法：
算法1split AST
输入：the root of the AST 。输出：a quence of small ASTs 。1.Function SPLIT(root)2.T =[root]3.N =[]
4.N =dfs(root,nodes)
5.for node in N do
6.if node ∈{function,if,while,for}then
朱允炆下落
7.T.append(node)
8.if node.parent ≠None then 9.parent=node.parent ve(d d d for 14.
return T
16.function DFS(root,nodes)17.
nodes.append(root)
Fig.1Node embedding training model 图1
词向量训练模型
459
Journal of Frontiers of Computer Science and Technology计算机科学与探索2021,15(3)
18.for child in root do
19.dfs(child,nodes)
吉林大学法学院该算法以AST的根节点作为输入。首先用根节
点初始化一个数组T，然后通过深度优先遍历获得
有声英语绘本
节点序列N，对N中的节点进行遍历，若节点属于集
合{function,if,while,for}，该节点连同其子节点将会
被切割取出存储到T中。值得注意的是，当出现嵌
套的情况，例如“if”子树中还包含“for”子树，“for”子
树将会从“if”子树上提前切割下来，因为深度优先遍
历将先访问“for”再访问“if”节点，两个独立的子树根
节点将按序存储到T中。
1.2.2卷积以及循环神经网络模型
在介绍CVRNN模型之前，先详细地阐述一下
Mou等人[12]提出的基于树的卷积神经网络TBCNN。
图2展示了该模型执行的具体流程。首先应用词嵌
入技术将AST中的节点转化成向量表示，不同的是，
该方法只使用了被表示节点的孩子节点作为情境，
没有考虑到兄弟节点以及祖先节点的信息，具体的
词嵌入公式如下：
vec(p)=tanh æ
è
ç
ö
ø
÷∑
i
l
i
W
i∙vec(c i)+b
其中，p表示双亲节点，c
i
表示p的第i个孩子节点，
W
i 是c
i勇创佳绩
的权值矩阵，l
i=
#node under c i
#node under p（孙子节点的
数目除以孩子节点的数目）是系数，b是偏置项。然后通过设置一个固定深度的滑动窗口遍历整个AST，再引入最大池化得到一个形状与原先一样的AST，接着使用动态池化[25]以及两层全连接神经网络得到
最终的代码向量。图3展示了CVRNN的模型架构，以下是该模型的算法执行逻辑：
首先根据1.1节得到的词向量表将AST中的节点表示为向量，再使用TBCNN模型对AST进行卷积得到编码后的向量，然后使用双向循环神经网络并以LSTM作为神经元对得到的向量序列进行编码以提取代码的序列信息。标准的循环神经网络（recurrent neural network，RNN）是单向的，其编码受限于过去的信息，采用双向RNN则能够同时使用过去和未来两个方向的信息。在后面的实验中，将会对这两种不同的策略进行对比。给定一棵代码的AST，假设该AST被切割成n棵子树，这些子树经过TBCNN编码后将得到一个向量序列TV∈R n×k，k表示向量的维度，n表示子树的数目。在某个时间步t，LSTM的计算公式如下：
i
t=σ(W i[h t-1,e t]+b t)
f
t=σ(W f[h t-1,e t]+b f)
o
t=σ(W o[h t-1,e t]+b o)
c
t=tanh(W c[h t-1,e t]+b o)
c
t=f t∙c t-1+i t∙c t
h
t=o t∙tanh(c t)
其中，σ是sigmoid激活函数，c
t
表示新状态，h
t∈R1×m表示输出向量，由当前时间步两个方向的向量
拼接而成的向量，W
i
、W
f
、W
o
是权值矩阵，b
t
、b
f
、
b
o
是偏置项。i
狐狸列那的故事t
表示输入门，决定e
t
中哪一部分将
被保留添加到c
t
中，f
t
表示遗忘门，决定e
t
的哪一部
Fig.2TBCNN model
图2TBCNN
模型
Fig.3CVRNN model
图3CVRNN模型
460
