基于抽象语法树的代码抄袭检测方法的改进*

刘飞翔，龙冬冬，欧幸茹，陈昌奉

(吉首大学信息科学与工程学院，湖南 吉首 416000)

随着数据开源的不断扩大，代码抄袭现象在程序设计类课程作业中频频出现.为了保证程序设计类课程教学质量和规范软件开发行为，国内外研究人员设计了各种类型的代码抄袭检测方法，其中源代码的抽象语法树(Abstract Syntax Tree，AST)能有效地表示出源码中的重要语法特征信息，被广泛应用在代码抄袭检测中[1-5].然而，不同源代码的AST中存在数量不一、结构不一的子树和节点，会导致基于AST的代码抄袭检测效果不佳[6].此外，在代码语义表达方面的局限性，也会使得基于AST的代码抄袭检测方法无法准确检测出语义层面的代码抄袭[7].针对以上问题，笔者拟设计将加权简化语法树和子树匹配相结合的程序代码抄袭检测方法，以期实现对源代码语义层面抄袭的检测，同时提高检测准确率.

1 AST简介

AST也称语法树，它由源代码经过词法分析和语法分析生成[8]，树上的每个节点都表示源代码的一种结构.基于AST的抄袭检测大多是对两者的每一棵子树进行遍历对比，从而得出相似度.因为子树的对比顺序不会影响对比结果，所以此方法能有效应对标识符重命名、代码重排序等抄袭手段[9].

代码抄袭检测首先需要对源文件进行编译，借助开源语法分析器(ANother Tool for Language Recognition，ANTLR)和GNU编译器套件(GNU Compiler Collection，GCC)等工具，经过词法分析、语法分析等一系列过程后生成对应源码的AST；接着对语法树子树上的信息进行特征提取，将信息转化成特征向量、Hash值或者特征标记串集合等形式；然后选取如编辑距离、欧氏距离、树核函数等方法计算子树的距离，从而得到相似度；最后通过与阈值进行对比来判定是否存在抄袭[10].

2 基于AST的代码抄袭检测方法的改进

改进的基于AST的代码抄袭检测方法(简称IAST)充分利用词频-逆词频[11](Term Frequency-Inverse Document Frequency，TF-IDF)设置语法树不同节点的权值，并根据生成的语法树中的不同结构成分分别设置公式以实现对源代码的相似度计算.此方法的实现主要分为3个阶段，即加权简化语法树、生成特征向量和相似距离、计算代码相似度.

2.1 加权简化语法树

数据集中的每一份代码都对应着一棵AST，每棵语法树上都存在数量不一的子树.用A表示一棵语法树，AI表示语法树A的第I棵子树，树上的节点记为a，子树AI的节点的权值记为Fa,AI.根据TF-IDF的定义，对子树AI进行中序遍历得到子树节点，若子树节点都是不能表示语义信息的非关键节点，则认为子树AI在语义上没有贡献，设置该子树的权值为0；若子树节点并非都是非关键节点，则权值Fa,AI的计算公式为

Fa,AI=WTF(a,AI)·WIDF(a,AI),

(1)

其中WTF表示子树节点的词频，WIDF表示子树节点的逆词频.由TF-IDF的定义可知，WTF(a,AI)和WIDF(a,AI)的计算公式分别为

(2)

(3)

其中：f(a,AI)表示节点a在AST的AI中出现的频数；f(AI)表示子树AI中的节点总数；c(a)表示包含节点a的子树总数；p表示AST的子树总数，也可以表示数据集中代码文件的总数.

对AST进行加权简化之后，代码样本中存在的框架部分会被赋予较低的权重，在检测时可以降低正例样本被检测为负样本的概率，有助于提高抄袭检测的准确度.

2.2 生成特征向量和相似距离

将遍历数据集中所有语法树得到的关键节点类型的集合作为特征项，则子树的特征向量由它所包含的特征项表示，子树根节点的特征向量由除根节点之外的所有节点的特征向量综合表示，这样子树根节点的特征向量能综合表示子树所含的信息量.

提取代码样本A和B，将样本A和B分别用节点a和b表示.设样本A和B包含的节点个数分别为m和n，则样本A和B的节点表示形式分别为

A={a1,a2,…,am},B={b1,b2,…,bn}.

设样本A和B包含的子树个数分别为p和q，则样本A和B的子树表示形式分别为

A={A1,A2,…,Ap},B={B1,B2,…,Bq}.

设子树样本AI和BJ包含的节点个数分别为k和l，则子树AI和BJ用节点分别表示为

AI={a1,a2,…,ak},BJ={b1,b2,…,bl},

其中ai和bj分别为样本A的第i个子节点和样本B的第j个子节点.设节点的特征向量为x=(x1,x2,…,xt)，其中xi为节点对应的特征项，t为特征项的个数，那么样本A中节点a与样本B中节点b对应的特征向量分别为

特征向量间距离的计算公式为

(4)

2.3 计算代码相似度

(1)节点相似度计算.

在代码抄袭检测过程中，可以将代码节点的相似度计算分为语义相似度计算和文本相似度计算[12]，通过赋予合适的权重计算出节点相似度.

在抄袭检测过程中，为了显著划分抄袭和非抄袭的界限，引入如下函数：

(5)

节点语义相似度sims的计算公式为

(6)

节点文本相似度simt可以表示样本对应的各个节点之间的权重相关度，具体计算公式为

(7)

在实际的代码抄袭检测过程中，语义相似度和文本相似度都很重要，综合考虑这2类相似度，得到节点a和b之间的相似度的计算公式为

sim(a,b)=α1sims(a,b)+α2simt(a,b).

(8)

由于样本A中的节点ai可能与样本B中的多个节点存在相似关系，因此样本A中的节点ai与样本B中的节点的相似度取样本A中的节点ai与样本B中的所有节点的相似度的最大值，样本B的节点相似度计算同样本A.计算公式为

(9)

(10)

(2)子树相似度计算.

在获取节点相似度之后，可根据AST的结构特征计算2份样本代码之间的子树相似度.由于某一子树可能包含多个子节点，因此子树之间的代码相似度计算公式为

(11)

类似于节点相似度计算方法，样本A和B之间的子树相似度的计算公式分别为

(12)

(13)

(3)代码相似度计算.

利用(5)～(13)式可以计算出样本A和B对应的AST的节点相似度和子树相似度，于是代码样本A和B对应的语法树相似度，即代码A和B之间的相似度计算公式为

(14)

2.4 算法实现流程

在IAST中，首先利用语法分析工具生成源代码的AST，并通过对变量名进行统一等方式实现AST的简化；接着采用TF-IDF算法对语法树中的节点进行赋权；然后提取语法树中节点的类型去重集合作为特征项，并统计所有节点的特征向量；最后通过计算每棵子树的距离实现抄袭判定.基于IAST的代码抄袭检测方法的实现流程如图1所示.

图1 基于IAST的代码抄袭检测算法流程

算法实现流程如下：

Step 1 初始化.设置语义和文本相似度配比参数α1，α2及抄袭判定阈值θ.

Step 2 语法分析.使用ANTLR对源代码进行语法分析，得到AST.

Step 3 节点整合.对语法分析树中的节点进行整合，得到简化后的AST.

Step 4 权重赋值.采用TF-IDF((1)～(3)式)对简化后的AST中的节点进行权重赋值.

Step 5 特征向量和相似距离生成.对AST进行特征提取，得到表征节点的特征向量，并利用(4)式计算源代码之间的相似距离.

Step 6 相似度计算.利用(14)式计算源代码两两之间的相似度，并通过与阈值进行比较来判定抄袭是否存在.

3 实验部分

3.1 实验环境

本实验操作系统为Windows10，搭载6核处理器，16 GB内存，1T硬盘.实验主体程序代码使用python语言完成.

3.2 实验数据

采用C语言程序代码作为实验数据，数据集包含10个编程题的源代码及对应的12种抄袭手段产生的代码，源码修改方式与对应的抄袭类型见表1.

表1 源码修改说明

3.3 评估方法

采用准确率[13](E)对实验结果进行评估.准确率是指检测结果正确的样本数占总样本的比例，其计算公式为

其中：CTP表示检测结果正确的抄袭代码样本数；CTN表示检测结果正确的非抄袭代码样本数；CFP表示检测结果错误的抄袭代码样本数；CFN表示检测结果错误的非抄袭代码样本数.

3.4 实验结果

基于实验给出的数据集，设置相似度配比系数和阈值，得到不同系数对应的抄袭检测准确率(表2).

表2 不同系数对应的抄袭检测结果

由表2可知，当α1=0.75，α2=0.25时，准确率比其他相似度配比的更高，且在该相似度配比下当θ=0.5时，准确率比其他相似度系数阈值的更高.于是，将语义和文本相似度的配比分别设置为0.75和0.25，阈值设置为0.5，再对数据集中不同抄袭类型的代码分别进行检测，用准确率衡量检测效果.将IAST与基于AST的抄袭检测方法[7](Z-AST)进行对比，得到不同抄袭代码类型的检测准确率(表3).

表3 基于不同抄袭类型的检测结果

由表3可知，IAST对Type-1和Type-2类型的代码抄袭行为检测准确率均高于0.9，对Type-3和Type-4类型的检测准确率相对较低，分别为0.878和0.650，但是其有效性较Z-AST的高.由此可见，IAST能有效检测Type-1～4类型的代码抄袭行为.

4 结语

针对传统基于AST代码抄袭检测中存在的问题，笔者设计了改进的基于AST的代码抄袭检测方法.该方法通过将源代码AST分解为子树，再检测子树的语义相似度和文本相似度，从而确定代码之间的相似度.实验结果表明，IAST能有效地检测Type-1～2及部分Type-3～4类型的代码抄袭，对于数据类型替换、代码结构等价替换等传统的基于AST的代码抄袭检测方法无法判别的抄袭行为同样具有较好的检测效果.另外，与Z-AST在相同的小量级别的代码数据集上进行对比时，该方法的检测有效性更高.值得一提的是，IAST虽然对语法树结构作了一定的简化，但是采用的相似度计算方法仍要对每棵子树进行遍历，方法的时间复杂度仍然较高，因此笔者接下来将针对这一问题继续展开研究.