1. 神经网络语言模型在代码分析中的应用研究综述

\begin{abstract} 深度学习在自然语言处理领域的成功应用使得人们越来越多地关注其在程序语言上的迁移,许多研究者借助神经网络语言模型在代码分析任务上也取得了显著成效。本文旨在介绍当前深度学习背景下的语言模型在软件工程、代码分析领域的应用,具体包括四个方面:代码克隆检测、代码脆弱性检测、自动化代码修补、恶意应用检测。 \end{abstract} %%%%%%%%% ABSTRACT \renewcommand\abstractname{abstract} \begin{abstract} Deep Learning has been applied to many NLP tasks successfully, which prompts a lot of transfering application in Software Engineering(SE). Considering the analogy between natural language and programming language, many researchers have developed efficient tools or framework relying on some prominent models used to solve NLP tasks. This paper is a survey of those application in SE and code analysis in the context of deep learning, which is composed of code clone detection, code defection detection, automatic code fixing and malware detection. \end{abstract} %%%%%%%%% BODY TEXT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{引言}\label{sec:Introduction}

近年来,深度学习被成功应用于自然语言处理(NLP)的一些列任务中,大大改进了传统方法的正确率,例如语音识别、基于统计的机器翻译等应用都在其帮助下提升了可用性。而这些技术的一个关键组件就是神经网络语言模型。

尽管自然语言和程序语言有很多相似性,程序语言特有的丰富结构信息使得问题变得特殊。事实上,软件工程社区已经成功地将深度学习应用于API挖掘、代码迁移以及代码分类。本文旨在介绍当前软件工程和代码分析中的几大主流应用对NLP技术的应用情况。

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{背景} \label{sec:RelatedWorks}

统计语言模型(Statistical Language Model)即是用来描述词、语句乃至于整个文档这些不同的语法单元的概率分布的模型,能够用于衡量某句话或者词序列是否符合所处语言环境下人们日常的行文说话方式。统计语言模型对于复杂的大规模自然语言处理应用有着非常重要的价值,它能够有助于提取出自然语言中的内在规律从而提高语音识别、机器翻译、文档分类、光学字符识别等自然语言应用的表现。

好的统计语言模型需要依赖大量的训练数据,在上世纪七八十年代,基本上模型的表现优劣往往会取决于该领域数据的丰富程度。IBM 曾进行过一次信息检索评测,发现二元语法模型(Bi-gram)需要数以亿计的词汇才能达到最优表现,而三元语法模型(TriGram)则需要数十亿级别的词汇才能达成饱和。本世纪初,最流行的统计语言模型当属 N-gram,其属于典型的基于稀疏表示(Sparse Representation)的语言模型;近年来随着深度学习的爆发与崛起,以词向量(WordEmbedding)为代表的分布式表示(Distributed Representation)的语言模型取得了更好的效果,并且深刻地影响了自然语言处理领域的其他模型与应用的变革。

在软件工程(SE)中,从源代码或可执行路径中产生了大量序列数据,其中的关键词(term,对应自然语言中的“词”的概念)可能是软件的中的字符短语或是方法调用,这些序列(对应“句子”的概念)可以是几行代码,或者是方法调用序列。由于模型表示的是短语的分布,像n-gram这样的统计语言模型就有了用武之地,可用来预测序列在下一个短语(term)。

卷积神经网络(CNN)在图像领域的目标识别和NLP领域都取得了最先进的效果。在NLP中,字符的局部特征,即n-gram,被广泛用于各种任务中的特征。甚至有人证明,只要有足够的训练数据,CNN能在文本分类任务上超出传统NLP方法。

首先需要解决的是程序表示问题(representation)。 程序分析背景下的许多应用所采用的技术都依赖于人为定义的特征,而一些研究者提出了基于学习的检测系统,其中用来表示源代码中的短语和片段的一切都是从项目本身挖掘到的。

\section{语言建模} 概率语言模型是一种语言中句子的概率分布。长久以来,概率语言模型对于许多NLP任务都是很有效的抽象方法。而近年来,该技术也在许多SE任务中成效显著,比如代码推荐、生成可读的字符串作为测试输入以减少人力测试代价、预测注释以改进代码搜索和代码分类、改进错误报告、生成可用的测试样例来提高覆盖率、提高风格一致性来辅助代码可读性和可维护性、代码迁移、合成API实现、代码复查、错误定位、推荐方法和类名。

概率语言模型是方便对一门语言中的句子(如多行代码或方法调用栈)进行处理的表示。这种易处理性是通过分解联合分布并分析概率实现的。然而,n-gram有明显的局限。比如,他们仅仅是对短语共现次数的统计,而很难具备超出训练时观测的特定特征的泛化能力。此外,该方法所考虑的上下文的数量也有限。他们提出了一种特别的语言模型,将源代码中的term映射到连续向量空间,并称之为“嵌入”。 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{代码克隆检测}\label{sec:HC} 对软件维护和迭代来说,代码克隆检测是一个重要问题。依赖于深度学习,他们的代码分析建立了一个自动化关联词法级别和句法级别模式的框架。

复制和粘贴代码以及修改复制的片段会得到文本上相似的代码段。其句法恰能反映其相似性。另一方面,当开发者未知情况下开发了和某个已存在的代码意图相似的实现,他可能创造出了句法不同但功能相似的克隆。检测代码相似性在许多应用中都十分重要,例如检测可选的库、辅助程序理解、检测恶意软件、检测抄袭或者版权侵犯、检测基于上下文的不一致等。

Martin、Michele等人\cite{white2016deep}设计了一套基于学习的模型,该模型使用从项目中挖掘到的特征来表示源代码的词和片段。接下来的几节将介绍其相关工作和方法概要。 \subsection{相关工作} 首先需要将源代码转换为适于评估相似性的表示。比如为了表示代码段,传统的基于树的克隆检测工具使用人为设计的特征,针对特定的程序结构。这样一来,标识符中的域信息就被丢弃了,打破了原本能在词法级和句法级共同学习到的信息的关联。此外,这些特征(如程序结构的出现次数)对代码段表示过程施加了很大成分的先验知识。然而,他们有理由认为不同应用领域、不同开发阶段的软件系统有其独特的模式,而这些模式恰能揭示代码克隆检测中的一些问题。而统一的特征空间未必能完全捕捉到这些模式,而代码本身才是真正能体现这些模式的。将检测过程中原本手工完成的步骤自动化恰能放宽原始数据表示过程的先验知识。挖掘有效的源代码特征、分析源代码中的标识符、适应不同的项目的工程方法等都是基本的SE研究问题。 \subsection{方法概要} 进行代码克隆检测,对源代码的表示方法分为两方面:1)将源代码中的短语映射到连续值向量上,这样源代码中用法相似的短语所对应的向量也是相似的。这种从短语到向量的映射从根本上区别于基于token的方法中使用的token抽象。2)该基于学习的表示方法为代码段设计了不同粒度的判别式特征,而不是简单地依赖于那些根据语言的结构元素设计的直观特征,比如基于树的方法。

该方法的本质是重回抽象本身,处理SE中不同级别的不同细节。如同语言建模中利用短语序列的模式,他们对源代码的建模也利用代码中短语结构的基于经验的特征。为达到这个目的,他们使用循环神经网络(RtNN)进行词法级分析,使用递归神经网络(RvNN)进行句法级分析。将编译器前端和深度神经网络和深度学习组合的目的是为了构建一个能链接词法级和句法级挖掘到的模式的框架。而克隆检测是该框架下很重要的应用。 代码段是指源代码的连续片段,由源代码文件、起止行数来定义。代码克隆是和一个克隆类型相似的不少于两个的代码段。候选则是克隆检测器报告的代码克隆。

\mypara{代码克隆检测} 通常来说有四种克隆类型: \begin{enumerate} \item 完全相同的片段,仅注释和布局的变化; \item 完全相同的片段,除了 第一类还有标识符名和字符值的变化; \item 句法相似,语句不同。除了第二类外还有语句增删改。 \item 句法不相似,但实现了相同功能。其中一二三类都反映了文本级的相似性,而第四类反映的是功能级的相似性。 \end{enumerate} 克隆检测方法一般先把源代码转化成表示,再计算相似度,因此可以根据表示的方法的不同进行分类。例如基于文本的方法只对源代码做很小的转化,而后通过比较文本序列来计算相似度。因此,基于文本的方法的限制在于,如果代码段之间的区别不是因果性的,比如系统性地对标识符进行重命名,该类方法不能识别出这是代码克隆。

基于token的方法对高级别的抽象进行处理,缓和基于文本的粗糙匹配规则的不足。这类方法从句法上分析代码,并生成token流,比较子序列来计算相似度。匹配子序列改进了识别效果,但使用token抽象容易报告很多假阳性。他们的基于学习的方法与基于token的方法至少有两点不同:1)token抽象将每个短语映射到一个(离散)类别,很有效地“收纳”了这些短语,而他们的方法将短语映射到特征空间中的连续值向量,其中相似度被编码为向量间的距离。2)他们的方法吸收了上下文(例如句法),超出了token抽象使用基于树的方法能做的。

基于树的方法度量句法表示中子树的相似度。他们的主要相关工作就是Jiang等人的Deckard,它将解析树(parse tree)转化成“特征向量”并对相似向量进行聚类(使用局部感知哈希)来检测克隆。他们使用抽象语法树(AST)而不是解析树,且Deckard区分“相关”和“不相关”节点,而他们将AST中的所有非空节点都视作相关。指定特定节点子集为相关等价于手工编辑片段的抽象。特征向量中的每个元素都代表着对应的子树中相关节点的出现次数,因此向量维数就是认为跟近似给定的树相关的树模式的个数。这和他们的方法的根本区别在于,他们试图从数据中学习判别式特征,而不是对特征有先验。此外,特征向量在逼近结构信息的同时忽略了标识符中的域信息。而AST方法中对标识符和变量名并没有特别处理。

基于图的方法使用静态程序分析将代码转化为程序依赖图(PDG),它是一种数据和控制依赖的中间表示。Gabel等人通过来自PDG的语义信息增强Deckard。他们将子图映射到对应的结构语法(将从母语句的类派生的节点定义为关键节点)并使用Deckard来检测克隆。Chen等人使用依赖树的“几何特征”来评估方法的相似度,之后再使用方法级的相似度检测安卓市场的应用克隆。他们首先从安卓应用包中提取方法,再将方法转化为控制流图(CFG)。通过将每个CFG节点映射到三维坐标来为每个方法计算“中心点”,维数则代表着结构。通过将方法映射到设计好的特征的三维空间,他们对代码表示施加了强大的先验。他们认为中心的定义可以扩展,这样中心就能被invoke语句影响,但这种增强是针对安卓应用克隆检测的,而他们提出的方法免去了人为设计这些特征的必要,毕竟这耗时且受限。

\subsection{深度学习代码段} 深度学习是组成学习算法的代表,机器学习的新生领域。循环神经网络能有效地对任意结构进行建模,比如预测自然语言句子的情感倾向。他们将克隆检测作为递归学习过程,从而合适地表示作为上层组件组成部分的代码段。递归学习内部是组合式的。

基于学习的方法分为两部分: \begin{enumerate} \item 词法级:使用循环神经网络将代码段的短语映射到嵌入; \item 句法级:使用递归神经网络将任意长的嵌入序列编码来提取代码段的特征。 \end{enumerate}

\subsubsection{深度学习代码:词法级} 循环神经网络(RtNN)十分适合对源代码语料的短语序列进行建模,假设词典为$ V$,则$| V|=m$个短语。假定使用者定义的超参数$n$为隐藏单元个数。RtNN由一个输入层$x \in \mathbb R^{m\times n}$ 、一个隐藏层$z \in \mathbb R^n$和一个输出层$y \in \mathbb R^m$。调整$n$会改变模型的容量。输入层会整合当前输入的短语$t(i)$和上一时刻的状态$z(i-1)$: \begin{equation}\label{equ:one} x(i) = [t(i);z(i-1)] \end{equation} 该输入向量乘上一个矩阵$\alpha,\beta \in \mathbb R^{n\times (m+n)}$,并输入给一个非线性向量函数$f$,比如: \begin{equation}\label{equ:function} z(i) = f(\alpha t(i)+\beta z(i-1)) \end{equation} 该状态向量乘上另一个矩阵$\gamma \in \mathbb R^{m\times n}$并进行归一化从而计算基于短语的后验概率: \begin{equation}\label{equ:output} y(i) = p(t|x(i))=softmax(\gamma z(i)) \end{equation} \equref{equ:one}-\equref{equ:output}定义了RtNN。其中\equref{equ:four}展示了其内部的分解关系以及输入是怎么通过前面的输入经过非线性变换产生的: \begin{equation}\label{equ:four} y(i) =softmax(\gamma f(\alpha t(i)+\beta f(\alpha t(i)+\beta (\dots))) \end{equation} 模型$\theta ={\alpha,\beta,\gamma}$使用交叉熵目标函数来训练,这里不再赘述细节。在软件语言建模中,可使用$argmax_k x_k y_k(i)$来预测某行代码的下一个词(term)。然而,深度学习模型的价值不仅在于它们的输出,它们的内部组件同样有用。本研究中基于RtNN的软件语言模型最重要的组件就是\equref{equ:function}中的嵌入矩阵$\alpha \in \mathbb R^{n\times m}$。$\alpha$的每一行都对应着一个词,每一行的特征空间即压缩着$V$中的每个词的语义表示。这样一来,模型就为语料中使用方式相似的词分配来相似的向量。假定每个词是one-hot方式编码的,则\equref{equ:function}中的矩阵-向量乘积$\alpha t$等价于将$V$中的每一个词映射到$\alpha$对应的某一行,这样也就把代码段的词序列映射到了嵌入序列。到这里,他们已经将代码段表示为了任意长的嵌入序列。 \subsubsection{深度学习代码:句法级} 不同于传统方法,对于给定的代码段,信息会从非叶子节点经过非叶子节点流动到层级结构的根节点。这种自底而上的信息流类似于传统结构导向的方法计算特征向量的过程或者基于指标的方法中计算指标。然而,他们为叶子节点挖掘表示,且非叶子节点并不是指示性的共现次数。特征空间是在区分不同代码段的过程中催生的。此外,在自底向上传播的信息合成计算出来特征向量或指标后,传统方法终止并将源代码表示传给匹配检测算法以找到相似代码段。某种意义上,他们认为自底而上的信息流对合适的代码表示来说必要但不充分。因此,他们的终止条件不同。在他们的方法中,只有当模型能收敛到一个能在不同粒度级别合理地表示程序结构的解决方案时,才算终止。该方法的核心在于一项准则:词法级信息西欧南瓜节点传输到结构根节点,而监督信号从根节点反向传播给整个结构。

\subsection{从AST到绝对二叉树} 编译器的前端将程序分解成若干组成部分,并根据语言的句法生成中间代码。这些组成部分称为程序构造,而不依赖于上下文的语法定义了程序构造的句法。AST就是一种程序层级句法结构的中间代码。而他们的最终目的是对任意长序列的词法元素进行编码。假定每个AST节点都有一个特殊属性repr来储存向量表示,即具备该节点及其内含的句法元素序列的编码。他们的目标是让相似的代码有相似的编码。他们的学习方法基于AST,它能以任意数量的层级压缩任意数量的子节点,但这里有个问题。他们的的学习器只接受定长输入,因此他们需要把AST转化为绝对二叉树从而固定输入长度,之后将学习器在不同的层级迭代地应用于模型。

AST节点的度数是0、1、2或者大于2。根据定义,度数为0和2的节点满足绝对二叉树对节点的要求。但度数为1(情况1)和大于2(情况2)的节点的子树则需要转化以将局部子树更新为绝对二叉树。转化的第一步就是扫描AST并删除元信息(例如Java代码段AST的Javadoc节点)以及空的匿名类的声明、空的矩阵初始化、空的块、空的类、空的编译单元以及空语句。在他们扫描AST查找空节点的同时,还要寻找有相同母节点的特有名称类型。学习器将对AST节点成对进行编码;因此,他们需要通过访问非叶子节点、检查它们的子节点、折叠临近节点、一致的变量类型到一个样例,来避免对相同变量类型进行编码。比如,true true,true true true等都会变成true。折叠这些序列需要冒着丧失某些分辨率的风险,但能帮助控制二叉树的深度。

接下来,为了获得二叉树,情况2的子树(度数大于2的节点)需要重新组织以保证子节点合理分布。对于每种非叶子节点类型,他们定义了一种基于语法的方法来系统地重新组织这些节点。例如,if语句的实例可以有两或三个子节点。他们通过引入人为设计的非子节点类型比如Branches来补充语法。

对于度数较大的非子节点类型,他们将其子节点组织为二叉列表。Block节点的子节点由语句序列组成。

在他们使用新的语法将情况2的实例转化后,便从原始的AST的到了二叉树,但这个二叉树不一定是绝对二叉树,毕竟有的节点有且仅有一个子节点。换句话说,他们需要处理情况1的节点(度数为1的节点)。他们采用自顶向下的方式转化二叉树,当遇到情况1的节点时他们将该节点和其子节点合并为一个新节点。之后再从这个新节点出发迭代这个过程。自顶向下的方法保证了有且仅有一个子节点的母节点最终会被整合为一个节点。该整合过程根据优先序列表执行,该列表为每种非子节点类型给出了值。当合并两个节点时,根据当前节点和其子节点的优先值来决定给新节点分配的是当前节点还是子节点的节点类型。这项设计源于对表示程序构造来说母节点通常比子节点更具代表性、信息更丰富。他们通过经验观察来决定这个表的顺位。通过这个顺位来保证: \begin{enumerate} \item 特定粒度级别受到保护且不回被其他节点覆盖; \item 当整合两个节点时,相较于通用类型,更青睐于能传达更果信息的类型; \item 前一步创造的处理情况2的人造非叶子节点不会替代原始语法中的非叶子节点。 \end{enumerate}

\subsection{从二叉树到橄榄树} 将二叉树转换为“橄榄树”,即使用挖掘到的表示来标注该绝对二叉树的结果。考虑这条语句:int foo = 42;。假定每个AST节点有一个特殊属性repr。通过选择矩阵中的特定行作为嵌入,他们可初始化每个叶子节点的该属性,而非叶子节点则初始化为空。到这一步,他们已经使用词法级挖掘到的模型来初始化嵌入序列。接下来,他们使用子编码器来结合这些嵌入。自编码器的经典模型就是一个有一个输入层$x$、一个隐藏层$z$、一个输出层$y$的神经网络: \begin{equation}\label{equ:autoencoder1} z=g(\varepsilon x+\beta_z) \end{equation} \begin{equation}\label{equ:autoencoder2} y=h(\delta z+\beta_y) \end{equation} 其中编码器是$\varepsilon=[\varepsilon_l,\varepsilon_r]\in \mathbb R^{n\times 2n}$;解码器是$\delta = [\delta_l;\delta_r]\in \mathbb R^{2n\times n}$;$\beta_z\in\mathbb R^n$和$\beta_y\in\mathbb R^{2n}$是偏置项。将词法级和句法具挖掘到的模式绑定在一起的纽带是$n$,它和\equref{equ:function}中的控制隐藏层大小的$n$是同一个。$g$是一个非线性向量函数,而$h$则是一个恒等函数。在学习器直接受定长大小的输入,促使AST到绝对二进制树的转化。具体来说,自编码器的输入是对两个兄弟节点的编码,即$x=[x_l;x_r]\in R^{2n}$。换句话说,语言模型将词法级的元素转换为嵌入,而自编码器将任意两个嵌入压缩为一个维度不变的向量作为词嵌入。而其输出$y=[\hat x_l;\hat x_r]\in \mathbb R^{2n}$则被看作是模型对输入的重建。训练该模型包括评估原始输入向量和重建向量的距离: \begin{equation}\label{equ:distance} E(x_l,x_r;\varepsilon,\delta,\beta_z,\beta_y)=||x_l-\hat x_l||^2_2+||x_r-\hat x_r||^2_2 \end{equation} 如果模型能学习到输入的判别式特征,就能泛化并可靠地重建任意输入向量。

由于树中的所有节点都有着相同的维数,他们可以对整个绝对二叉树迭代地进行自编码,即递归神经网络(RvNN)。

分析标识符的技术通常使用隐式语义分析(LSA)。而深度学习较LSA有三点明显优势:1)自编码器是非线性降维器;2)使用非线性转换、迭代应用自编码器操作输入而不是使用线性分解输入;3)该迭代考虑短语的顺序。另一方面,分析结构的技术不考虑标识符,而他们将之作为先验知识。不同于使用通用的结构元素,他们的学习框架的表示能力是基于标识符和变量类型的l判别能力的。因此,即使句法的相似性很弱,深度学习仍能识别出短语的相似性。 Socher等人将迭代自编码器应用于自然语言的情感分析。其创新性在于为使用句子级的标记训练模型来对句子感情进行分类所设计半监督扩展。

一旦模型训练好,推理过程就很直接了。识别克隆等价于比较两个代码段的表示,而且可在不同粒度级别比较。具体来说,给定代码段,他们首先构造AST树,再转化为绝对二叉树。如果绝对二叉树中有k个叶子节点,就有k-1个非叶子节点。因此,对序列编码需要进行k-1次矩阵与向量的乘法之后再应用一个向量函数得到代码段的表示。自然情况下,绝对二叉树的结构决定了节点表示的组合顺序。对代码克隆检测来说,需要决定的只是决定两个代码段接近程度、用来判断是否为克隆的一个阈值。

\section{软件缺陷预测} 软件缺陷预测是预测有漏洞的代码区域,以帮助开发者发现bug从而决定测试的优先级顺序。为了建立正确的预测模型,之前的研究集中于手动设计特征来对代码的特点进行编码,并探索了不同的机器学习算法。现存的传统特征往往无法捕捉到程序语义级别的区别,而这恰是构造正确的预测模型所需要的。 为了弥补程序语义和缺陷特征之间的差别,Song Wang等人\cite{wang2016automatically}利用有效的基于表示的学习算法,深度学习技术,来从源代码自动学习语义表示。利用了深度置信网络(DBN)来从抽象语法树(AST)中提取短语向量,再从中学习语义特征。 在10个开源项目上进行了评估,结果显示,和传统特征相比,其自动学习得到的语义特征能有效改进项目内缺陷预测(within-project defect prediction,WPDP)和项目间缺陷预测(cross-project defect prediction,CPDP)。 DBN是生成式图模型,它学习得到一个能以较高概率重构训练数据的表示。通过构造深层结构,它能学习得到数据的上层表示。他们已经看到DBN在许多领域的成功应用,包括语音识别、图像分类、自然语言理解和语义搜索。 为了使用DBN从代码段中学习到特征,他们将代码段转化成token的向量,并保留结构和上下文信息,再使用这些向量作为DBN的输入。

\begin{figure}[t!] \begin{overpic}[width=\columnwidth]{DBN.png} \end{overpic} \caption{深度置信网络结构及输入样例File1.java和File2.java。尽管这两段代码的token一样,但token之间结构和上下文的区别使得DBN生成不同的特征来区分这两个文件} \label{fig:DBN} \end{figure} \subsection{深度置信网络} 深度置信网络是生成式图模型,它通过多层神经网络能从训练数据中学习得到表示,并能从该表示中以大概率重构出输入数据的语义和内容。DBN包括一个输入层和若干隐藏层。最顶层是输出层,使用特制来表示输入数据。每层都包含若干随机节点。根据使用需要,层的数量和节点数量都可以相应调整。这里学习到的语义特征的数量就是顶层节点的数量。DBN的设计思想就是通过调整不同层不同节点间的权重,使得网络能从生成的特征重构出输入数据。 DBN对输入层和隐藏层的联合分布进行建模,如下所示: \begin{equation}\label{equ:dbn1} P(x,h^1,\dots,h^l)=P(x|h^1)(\prod_{k=1}^l P(h^k|h^{k+1})) \end{equation} 其中$x$是来自输入层的数据向量,$l$是隐藏层个数,而$h^k$是第$k$层的数据向量$(1\leq k\leq l)$。$P(h^k|h^{k+1})$是相邻的$k$和$k+1$层的条件分布。

为了计算$P(h^k|h^{k+1})$,DBN中的每两个相邻层都作为\emph{受限波尔兹曼机}(RBM)来训练。RBM是两层、无向、双方的图模型。其中第一层包括数据变量的观测值,即\emph{可视节点}(visible nodes),第二层为隐含变量,即\emph{隐藏节点}(hidden nodes)。$P(h^k|h^{k+1})$的计算方式如下: \begin{equation}\label{equ:dbn2} P(h^k|h^{k+1})=\prod{j=1}^{n_k}P(h_j^k|h^{k+1}) \end{equation} \begin{equation}\label{equ:dbn3} P(h_j^k=1|h^{k+1})=sigmoid(b_j^k+\sum{a=1}^{nk+1}W{a_j}^kh_a^{k+1}) \end{equation} 其中$n_k$是第$k$层节点数,$sigmoid(c)=\frac{1}{1+e^{-c}}$,$b$是偏置矩阵,$b_j^k$是第$k$层节点$j$的偏置,而$W^k$是第$k$层和$k+1$层之间的权重矩阵。

DBN通过迭代过程自动学习$W$和$b$。$W$和$b$的更新是用的是log似然随机梯度下降: \begin{equation}\label{equ:dbn3} W{ij}(t+1)=W{ij}(t)+\eta \frac{\delta\log (P(v|h))}{\delta W{ij}} \end{equation} \begin{equation}\label{equ:dbn3} b_k^o(t+1)=b_k^o(t)+\eta \frac{\delta\log (P(v|h))}{\delta b_k^o} \end{equation} 其中$t$是第$t$次迭代,$\eta$是学习率,$P(v|h)$是给定隐藏层条件下可见层的条件概率,$i$和$j$是RBM不同层的两个节点,$W{ij}$是它们之间的权重,$b_k^o$是第$k$层节点$o$的偏置。

在开始训练前,首先初始化RBM两层之间的$W$矩阵,并将偏置$b$置零。之后就可以根据某项指标慢慢调整这些参数,比如迭代次数或者重构的输入数据和原始的输入数据之间的错误率。 \subsection{方法} 现有研究常用的文件级脆弱性检测流程中,第一步是将数据标记为“buggy”或者“clean”,如果一个文件包含bug就标为“buggy”,否则标为“clean”。第二步是收集这些文件对应的传统特征。有特征和标签的样本被用于训练机器学习分类器。最后,训练好的模型被用于预测新的样本是“buggy”还是“clean”。

我们称用于构建模型的样本集合为训练集,用于评估训练好的模型效果的集合为测试集。在进行项目内脆弱性检测时,训练和测试集都来自相同项目A。而在执行跨项目脆弱性检测时,训练集来自项目A(源),而测试集来自项目B(目标)。

使用DBN从源代码中自动生成语义特征并利用这些特征改进脆弱性检测。该方法使用训练集和测试集中源代码的token作为输入,从中生成语义特征,并用于构建和评估脆弱性预测模型。具体来说,该方法对训练和测试集中的每个文件的源代码提取token向量。DBN要求输入数据是整数向量,因此首先建立tokenx到整数的映射,再将token向量转化为整数向量。为了得到语义特征,首先利用训练集的整数向量构建DBN模型。之后,使用DBN来从训练集、测试集的整数向量自动生成语义特征。最后,基于生成的语义特征,在训练集上构建脆弱性预测模型,并在测试集上评估。

该方法主要分为四步:

\begin{enumerate} \item 将源代码处理为token; \item 将token映射到整数标识符,作为DBN的预期输入; \item 利用DBN来自动化地生成语义特征; \item 构造缺陷预测模型,并基于从训练数据生成的语义特征预测缺陷。 \end{enumerate}

\subsubsection{处理源代码} 为了让DBN学习语义特征,他们首先需要从源代码中提取句法信息。这里使用了Java的抽象语法树(AST)来提取句法信息。提取了三种AST节点作为token: \begin{enumerate} \item 函数调用及类的实例创建节点; \item 声明节点,如函数声明、类型声明及enum声明; \item 控制流节点,比如while语句、catch语句、if语句、throw语句等。控制流节点作为其语句类型保存,比如if语句就计作if。 \end{enumerate} 总的来说,对每一个文件他们都能得到这样三种类型token对应的向量。

该方法没有包含在以上三个类型外的AST结点,比如指派和内部类型声明,因为这些往往是特定方法或者类型特有的,也就不能泛化至整个项目。加上它们的话会弱化其他结点的重要性。

考虑到方法、类、数据类型名都是项目特有的,不同项目中的相同名字要么很少要么功能不同。因此,对于跨项目的脆弱性检测,提取了三种类型的AST结点。而对于类型1和2的AST结点,使用的是AST结点的类型,如“方法声明”和“方法调用”,而不是它们的名字。以项目xcerces为例,作为一个XML处理器,它包含许多叫做getXXX和setXXX的方法,其中XXX指的是XML特有的关键词,包括charset、type和href。这些方法每个都只包含一个方法调用语句,其形式要么是getAttribute(XXX)要么是setAttribute(XXX)。方法getXXX和setXXX并不存在于其他项目中,而getAttribute(XXX)和setAttribute(XXX)在其他项目中也有不同意义,因此,使用它们的名字getAttribute(XXX)和setAttribute(XXX)没什么用。但知道这里存在方法声明结点却很有用,且每个方法声明结点下面只有一个方法调用结点,因为只有一个方法调用的方法不大可能有bug。这种情况下,相较于使用方法名,使用AST结点的类型如“方法声明”和“方法调用”更有用,因为它们能提供部分语义信息。

\subsubsection{处理噪声和映射token} \begin{enumerate} \item {处理噪声}:脆弱性数据往往有噪声且存在误标问题,研究表明这些噪声会显著影响脆弱性检测的效果。为了修剪噪声数据,Kim等人提出了一种叫做最近表噪声识别(Closest List Noise Identification,CLNI)的误标数据检测方法。该方法识别出每个样本的k近邻并查看其标签。如果一定数量的近邻的标签相反,则当前样本会被标记为噪声。然而,这种方法并不能直接应用于我们的数据,因为该方法是基于传统数值特征的欧式距离,而我们的特征是语义token两个特征的值之间的差异只代表了这两个特征属于不同的token。为了检测并消除误标数据,以帮助DBN学习bug文件和正常文件之间语义信息的常用知识,我们采取了编辑距离相似度计算算法来定义样本间的距离。编辑距离对token和token顺序都很敏感。对于token序列A和B,编辑距离$d(A,B)$指的是将A转化为B需要的编辑操作的最小权重序列。$d(A,B)$越小,即A和B越相似。基于编辑距离相似度,我们使用CLNI来除去可能误标的数据。因为我们的目标并不是找到最佳训练或测试集,也就没有在CLNI调参上花费太大精力。我们使用推荐的参数且效果不错。在使用传统特征的基准实验中,我们也使用CLNI来去除误标数据。此外,我们过滤掉了不常用的AST结点,它们可能是为特定文件设计的因此难泛化到其他文件。对于一个项目来说,如果一个token的出现次数小于3就被筛除。我们只对出现次数大于等于3的token进行编码,这在NLP领域也是常用的手段。 \item 映射特征:DBN只接受数值向量作为输入,且输入向量是等长的。为了使用DBN生成语义特征,我们首先要建立整数到token的映射,并将token向量编码成整数向量。每个token都有独一无二的整数识别符,而每个不同的方法名和类名都作为不同的token处理。由于整数向量可能长度不同,我们将所有向量用0填充至最长向量的长度。增加0并不影响结果,仅仅是对表示的转换,以保证被DBN所接受。使用\figref{fig:DBN}中的代码段举例说明,如果我们至考虑“File1”和“File2”,“File1”和“File2”的token向量将分别被映射为$[1,2,3,4]$和$[2,3,1,4]$。通过该编码过程方法调用信息和类间信息就被表示为了整数向量。此外,由于token顺序不变,一些程序结构信息也被保留。 \end{enumerate} \subsubsection{训练DBN和生成特征} \begin{enumerate} \item 训练DBN:为了生成区分bug文件和正常文件的语义特征,我们首先需要使用训练数据训练DBN。为了训练有效的DBN模型,我们需要调节三个参数,它们是:1)隐藏层数量,2)每个隐藏层结点的数量,3)训练迭代次数。使用DBN来为NLP或图像识别任务生成特征的相关工作指出DBN生成的特征对这些参数很敏感。为了简化我们的模型,每层的结点树相同。通过这些隐藏层和结点,DBN能获取难观测到的特征并抓取到语义上的差异。对于每个节点,DBN学习从该节点转移至顶层节点的概率。通过反向传播验证,DBN通过调整不同层节点间权重使用生成的特征重构输入数据。DBN要求输入数据的值在0到1之间,而映射过程使得我们的输入向量有任意整数值。为了能满足输入范围要求,我们使用min-max归一化来将训练、测试集中的数据归一化。在我们的映射操作中,不同token的整数值仅仅是标识符。映射值是1的token和映射值是2的token仅意味着这两个结点不同且独立。因此,归一化后的数值仍能作为token标识符,因为相同的标识符值仍相同。 \item 生成特征:在我们训练完DBN后,权重$w$和偏置$b$都固定下来了。我们分别输入归一化后训练、测试集的整数向量到DBN中,就能从DBN的输出层的到训练、测试集对应的语义特征。 \subsubsection{构建模型和进行脆弱性检测} 在获得训练集、测试集中每个文件的语义特征后,我们构建并训练脆弱性检测模型,再使用测试集来评估该模型的表现。

\end{enumerate}

\section{代码漏洞修补} 在软件工程领域,对自动修补程序漏洞的研究一直很活跃。修复一个错误可能需要对整个程序进行分析。在实际应用中,许多错误都源于程序员往往由于对编程语言经验不足或不重视细节,他们成这样的错误为常见编程错误。这可以类比到自然语言中的语法错误。编译器能检测到这些错误,但它们的报错信息往往不准确。Rahul Gupta等人\cite{kruthiventi2017deepfix}提出了一个端到端的解决方案,称为Deepfix,在不借助任何外部定位或修复工具的情况下修复程序错误。Deepfix的核心是基于attention机制的序列到序列多层神经网络,他们训练该模型以预测错误出现位置以及对应的正确语句。

和之前的研究相比,Deepfix可解决任意未见过的编程任务。修补重要的错误需要对程序文本的长期依赖关系进行推理,因此Deepfix使用序列到序列模型对长时关系进行建模。该技术在大量C语言程序上取得了一定效果。

\subsection{程序表示} 将程序错误修复问题作为序列到序列学习问题。这样一来,程序就要表示成序列。程序文本包括不同类型的token,比如数据类型、关键字、特殊字符(比如分号)、函数名和变量。其中数据类型、关键字、特殊字符、库函数名组成了不同程序的共享词典。对于其他类型的token,他们首先定义了一个固定大小的池,之后为每个程序构建独立的编码映射表,即通过把每个特定的标识符(变量或函数名)随机映射到池中的特定名字。他们选择了一个足够大的池,能为任意数据集中的程序创建这样的映射表。这种转化并不改变程序的语义,并且是可逆的。他们根据字符的类型来映射到特定的token,比如把整型的字符映射到NUM,把字符串型的字符映射到STR。他们使用特殊的token 来标注token序列的结束。

他们把每个程序视作token序列X。他们的网络需要预测的是另一个序列Y来修复X中的错误。然而,他们处理的都是几百行的程序,想要正确预测大小的目标序列会很困难。为了解决这个问题,他们对行数进行编码,即L行的语句S表示为$(l,s)$,其中$l$和$s$表示L和S的分词结果。即$k$行程序P会被表示为$(l_1,s_1),\dots,(l_k,s_k)$,其中$l_1,\dots l_2$是行号,$s_1,\dots s_2$是相应行的token序列。现在可以训练网络来预测一个修复,包括行号$l_i$和修复语句$s_i$的关联语句$a_i’$。该输出相比代表整个要修复的程序的序列来说小得多,可能也更容易预测。

\subsection{网络结构} \begin{figure}[t!] \begin{overpic}[width=\columnwidth]{seq2seq.png} \end{overpic} \caption{DeepFix的迭代修复策略} \label{fig:DeepFix} \end{figure} 编码器RNN处理对输入序列进行编码,加入了attention的解码器RNN负责生成输出序列。编码器和解码器都由$N$个堆叠的门限循环单元(GRU)组成。编码器将输入序列的每个token映射到称为“标注”(annotation)的实值向量上。对于输入序列$x1,\dots,x{}$,在时刻$t$隐藏单元的激活值的计算如下: \begin{align} &ht^{(1)}={GRU}(h{t-1}^{(1)},xt) \ &h_t^{(n)}={GRU}(h{t-1}^{(n)},h_t^{(t-1)}),\forall n\in {2,\dots,N} \end{align} 解码器网络使用编码器网络的最后状态来初始化,更新方法如下: \begin{align} &dn^{(n)}={GRU}(d{t-1}^{(n)},dt^{(n-1)}),\forall n\in {2,\dots,N} \ &h_t^{(1)}={GRU}(d{t-1}^{(1)},z_t) \end{align} 其中$zt$是时刻$t-1$的输出$\hat y{t-1}$的级联,上下文向量$ct$的定义如下: \begin{align*} &c_t=\sum{j=1}^{Tx} a{tj}hj^{(N)}\ &a{tj}=\frac{\exp(e{tj})}{\sum{k=1}^{Tx} \exp(e{tk})}\ &e{tk}=\phi(d{d-1},hk^{(N)}) \end{align*} 上下文向量$c_t$实际上是输入序列标注$h_1^{(N)},\dots,h{Tx}^{(N)}$使用归一化权重$a{tj}$的加权和,其中$j\in{1,\dots,Tx}$。而能量$e{tj}$使用前馈网络实现的软对齐模型$\phi$,它和其他组件一起训练。直观上解释,这些权重或者能量值决定了对于从隐藏层状态$h_{t-1}$计算当前解码器的隐藏层状态$d_t$来说不同标注的重要程度。 \begin{figure} \begin{overpic}[width=\textwidth]{cnn.png} \end{overpic} \caption{恶意应用检测网络框架} \label{fig:cnn} \end{figure} \subsection{迭代修复} 为了保证预测任务的简单性,他们设计的网络一次只修复一个错误。然而,程序可能有多个错误,Deepfix使用一种简单但是有效的迭代策略来修复程序中的多个错误。

给定输入程序分词后的表示,网络要预测一个修复。一个仲裁器接收该修复和输入程序,整合它们得到更新后的程序。仲裁器的工作是通过检查更新后的程序没有导致更多的报错来决定是否接受该修复。一旦该修复被接受,Deepfix将更新后的程序再次输入到网络中。该迭代策略的停止条件为以下之一: \begin{enumerate} \item 仲裁器判断更新后的程序没有错误需要修复; \item 网络认为输入的程序是正确的,并给出特殊的token“fixed”; \item 仲裁器拒绝该修复; \item 达到预设的迭代数上限。 \end{enumerate}

除了决定替换某行的语句,网络还可能决定在某行前/后插入语句,或者是删除某条语句。因为他们最终是要修复实际程序,仲裁器要从应用修复后的token序列中重构出程序文本。它使用分词时构造的程序特定的编码映射表来反向替换回原始的标识符。它使用修复中的行号,并在输入程序的对应行用原始的字符替换回类似NUM和STR这样的特殊token。如果仲裁器不能重构出程序就会拒绝该修复。

该修复策略有几大优点: \begin{enumerate} \item 程序被完整地表示并输入网络。识别并修复程序错误常需要能推导长时依赖性的全局分析。而该网络结构能选择性地将“注意力”集中在程序的任意部分,因此能推理出结构和句法约束,从而预测错误位置和对应的修复。 \item 输入和输出都包含行号,缩小了粒度,也降低了预测任务的复杂度。 \item Deepfix的修复策略十分通用。例如,如果他们试图修复逻辑错误,只需要使用有测试套件的测试引擎作为仲裁器。如果某修复使得程序通过更多的测试则被接受。 \end{enumerate}

\section{恶意应用检测}

使用人为设计的特征的机器学习方法被广泛用于动态和静态恶意应用检测,这些特征包括API调用、intent、permission和指令,使用不同的分类器,如支持向量机、朴素贝叶斯、k近邻。

和使用上层的、人为设计的特征相比,基于n-gram的恶意应用检测使用的是底层的操作码序列作为特征。这些特征可用于训练分类器来区分恶意、良性应用。n-gram的长度以及分类使用的n-gram序列的数量都会影响分类器的正确率。然而,增大其中任意一个都会导致所需计算资源的大幅上涨,这显然也是标准基于n-gram的恶意应用检测方法的缺陷。n-gram方法还需要特征选择来降低特征向量的维数,否则的话,长n-gram将导致百万元素长度的特征向量。

Niall McLaughlin等人\cite{mclaughlin2017deep}提出了一种使用CNN的安卓恶意应用分类系统。通过对反汇编得到的操作码序列进行静态分析来识别恶意应用。指示恶意应用的特征是网络自动从原始操作码学习到的,也就不需要人工设计特征。该模型采用端到端的方式,即特征学习和分类是共同训练的,相较基于n-gram的检测方法简化了步骤。,也不需要在训练时遍历百万数量级的n-gram。该网络还利用了现有方法在计算上处理不了的长n-gram特征。一旦训练完毕,该网络可以在GPU上有效执行,迅速扫描大量文件。

\figref{fig:cnn}展示了网络的整体结构。可以看到网络输入为反编译得到的操作码序列,之后将其映射到对应的embedding上,再对串联的embedding序列进行卷积、激活、采样操作,最终输出分类结果。 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{总结与展望}\label{sec:Conclusion} 随着深度学习技术在自然语言处理领域的不断发展,研究者们有望在未来利用该技术解决软件工程以及安全领域的诸多问题。

results matching ""

    No results matching ""