一种基于功能的程序表示研究

陈功

（四川大学计算机学院，成都 610065）

0 引言

随着软件技术的迅速发展，软件仓库的规模变得越来越庞大，软件仓库中大量的软件工件为软件开发人员从中挖掘出有用的信息，并应用于软件工程活动提供了可能。软件仓库中的源程序就是软件工程的重要研究对象之一。为了有效地挖掘出程序中隐含的信息，关键在于找到一种合适的程序的中间表示方法。

为了解决软件工程中的实际问题，国内外研究者们对于程序的表示方法也进行了许多尝试。2006年Koschke[1]在研究中使用基于抽象语法树的方法来进行代码克隆检测。2013年Wu[2]等人采用基于程序依赖图的方法来分析程序中的克隆。2015年White[3]等人将循环神经网络应用于程序语言中，获取token的词向量表示，并应用于代码推荐系统中。

深度学习[4]作为当前的研究热点之一，在自然语言处理、语音识别以及图像处理等领域都取得了突破性的进展。近年来，软件工程领域的研究者们也开始尝试将深度学习应用于软件工件中[5-6]。本文利用深度学习自动提取特征的特点，提出了一种基于功能的程序表示方法，得到可以反映程序特征的矩阵表示。

1 算法思想

我们的核心问题是将程序在一个固定维度的实数值空间表示出来，进而才可以将其作为典型的有监督学习算法的输入。尽管程序可能包含了很多特征，如代码风格、时空间复杂度等，在这里我们将首要关注程序最基本的方面——功能。给定一个程序A，以及它的前置条件P，我们希望能够通过学习A的特征从而预测当P成立时，运行A得到的结果，即程序A的后置条件Q。一般地，我们将P和Q表示成一个实值向量，该向量包含了程序在某个特定时刻的状态（即程序中变量的值），这里的（P,A,Q）被称为霍尔三元组。我们提出以霍尔三元组集合作为深度网络的输入来学习程序的特征，采用的主要方法是同时找到程序的状态和程序在特征空间的对应的点，在这个空间上，程序可以视作是程序的前置条件到后置条件的一个线性映射。

更具体地说，给定一个三元组（P，A，Q），如果fP和fQ分别是前置条件P和后置条件Q的m维的特征表示，那么它们的关系可以通过等式1联系起来：

于是，我们得到了一个m维的矩阵MA作为程序A的特征表示，我们希望通过学习得到的P，Q到特征空间f的映射以及fP到fQ的线性映射MA具备较好的泛化能力，即对于给定的程序A以及前置条件P，可以预测其后置条件Q。

2 网络结构

本文方法的网络结构如图1所示。

图1

我们的网络总体上可以分为四层，输入层、输出层以及两个隐含层，输入层到第一个隐含层对应图中的编码器（Encoder），第二个隐含层到输出层对应图中的解码器（Decoder），分别完成了程序的前置条件P和后置条件Q到特征空间f的映射，隐含层之间的权重系数就是程序特征的矩阵表示。对于给定的程序A，我们多次记录程序中变量的值以及运行之后的值，得到大量的三元组（P,A,Q），以此作为数据集来训练我们的模型。

3 模型训练

假设提取到的程序的前置条件P和后置条件Q均是d维的向量，利用自编码器思想，我们建立一个从前置条件P到m维的特征表示fP的非线性映射，这种映射被称为编码器。如传统的自编码网络一样，我们使用如下的非线性特征映射：

式中的We∈Rm×d,be∈Rm，Φ是一种非线性函数。之后，同传统的自编码器做法一样，我们可利用fP重构出原始的输入P：

式中的Wd∈Rd×m,bd∈Rd，ψ是一种非线性函数。到这一步，我们可以利用等式（1）得到后置条件Q在特征空间的表示fQ，进而重构出由模型得到的后置条件Q：

为了训练模型中的参数，我们建立这样一个损失函数L()

θ：

该损失函数由三个部分组成，其中lpred表示了在给定前置条件的情况，我们预测出程序的后置条件的准确程度，lauto反映了我们的自编码器将输入P编码再解码后重构得到的P̂与原始输入P之间的误差，R是正则项，λ是正则化参数。我们的训练目标就是使得取得最小值。

4 结语

本文介绍了一种基于功能的程序的表示方法。该方法从程序的功能出发，通过收集运行程序得到的霍尔三元组（P，A，Q）作为深度网络的输入，经过训练同时得到程序的前置条件和后置条件在新特征空间的表示，使得程序的执行可以视作一个线性的映射过程。同时我们还获得了程序的矩阵表示，该矩阵可以应用于很多的软件工程任务中，如代码克隆检测、代码自动评分、测试用例自动生成等。该方法同其他方法相比最大的优势在于利用深度网络自动提取程序的特征。在下一步的研究工作中，我们将从实际的软件工程任务出发，来验证该方法的有效性。

参考文献：

[1]Koschke R,Falke R,Frenzel P.Clone Detection Using Abstract Syntax Suffix Trees[C].Reverse Engineering,2006.Wcre'06.Working Conference on.IEEE,2006:253-262.

[2]吴军华,王佳利.基于依赖图的程序克隆分析及近似解求解方法[J].南京工业大学学报(自科版),2013,35(5):52-56.

[3]White M,Vendome C,Linares M,Poshyvanyk D.Toward Deep Learning Software Repositories.MSR'15.

[4]Bengio Y,Courville A,Vincent P.Unsupervised Feature Learning and Deep Learning:A Review and New Perspectives[J]，2012.

[5]Hindle A,Barr E T,Su Z,et al.On the Naturalness of Software[J].Communications of the Acm,2016,59(5):122-131.

[6]Allamanis M,Sutton C.Mining Source Code Repositories at Massive Scale Using Language Modeling[J]，2013:207-216.