WASTK:一种针对源代码抄袭检测的加权抽象语法树核方法外文翻译资料

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

WASTK:一种针对源代码抄袭检测的加权抽象语法树核方法

傅德强，徐艳艳，郝浩然，杨博阳

（北京林业大学 信息科学与技术学院，北京100083）

摘 要:在本文中，我们介绍了一种源代码抄袭检测方法，名为WASTK（加权抽象语法树内核），用于计算机科学教育。与其他抄袭检测方法不同，WASTK考虑了程序之间的相似性以外的一些方面。WASTK首先将程序的源代码转换成抽象语法树，然后通过计算两个抽象语法树的树核来获得相似度。为了避免由教师给出的简单代码片段或框架引起的误判，应用了类似于信息检索领域中的TF-IDF（词频-逆向文件频率）的想法。抽象语法树中的每个节点由TF-IDF分配权重。WASTK在不同的数据集上进行评估，结果是比其他流行的方法（如Sim和JPlag）表现更好。

WASTK: A Weighted Abstract Syntax Tree Kernel Method for Source Code Plagiarism Detection

（Deqiang Fu,Yanyan Xu,Haoran Yu,and Boyang Yang）

（School of Information Science and Technology, Beijing Forestry University,Beijing 100083）

Abstract:In this paper, we introduce a source code plagiarism detection method, named WASTK (Weighted Abstract Syntax Tree Kernel),for computer science education. Different from other plagiarism detection methods, WASTK takes some aspects other than thesimilarity between programs into account. WASTK firstly transfers the source code of a program to an abstract syntax tree and then gets the similarity by calculating the tree kernel of two abstract syntax trees. To avoidmisjudgment caused by trivial codesnippets or frameworks given by instructors, an idea similar to TF-IDF (Term Frequency-Inverse Document Frequency) in thefield of information retrieval is applied. Each node in an abstract syntax tree is assigned a weight by TF-IDF.WASTK is evaluated on different datasets and, as a result, performs much better than other popular methods like Sim and JPlag.

1. 引言

由于互联网的发展，源代码剽窃已经成为计算机科学教育领域的一个大问题^[1]。有些学生通常会尝试从同学那里复制源代码，或者从互联网上搜索类似的源代码作为他们的作业而不进行修改。抄袭严重降低了教育质量。学生被剥夺了创新和独立思考的能力，这也可能导致学术上的不诚实。

正如传统的离线计算机科学教育中发生的那样，在线教育也遭受抄袭。此外，当学生提交的数量远远超过传统的离线案例中的数量时，在线教育平台更难找到反对源代码剽窃的方法。因此，检测源代码抄袭成为任课教师日常工作的重任^[2]。

为了自动检测源代码剽窃，该领域的研究人员已经考虑了三个问题^[3–5]。

问题1。计算机程序是结构化的和分层的。寻找一种合理的方法来衡量一对程序之间的相似性需要仔细对待。

问题2。对于抄袭目的的程序修改几乎是不变的。可以高可信度地找到常见的失真，例如，评论更改，空白填充，标识符重命名，代码重新排序和代数表达。

问题3。每对程序之间的比较需要很长时间，导致效率低下。

此外，还存在一些需要考虑的其他事实。

问题4。教师可以为学生提供编程作业的框架。提供的框架将为每对程序之间的相似性做出很大贡献。

问题5。简单问题的解决方案可能相似。例如，一百名没有任何通信的学生可能会为计算两个变量之和的任务生成非常相似的程序。

为了解决这两个问题，本文提出了两种准确的源代码抄袭检测方法，命名为ASTK（抽象语法树内核）和WASTK。在这项工作中，它们被呈现为抽象语法树^[6]。在ASTK中，一种称为树内核的方法^[7]用于测量一对程序之间的相似性。此外，与传统的树核方法不同，为了突出非平凡部分的重要性并减少由教师提供的短样本源代码和源代码所造成的影响，WASTK为每个树节点赋予权重。灵感来自TF-IDF的想法^[8]，较低的权重被赋予由编码分配框架提供的公共代码和代码的部分，并且较高的权重被分配给那些区分的代码部分。

本文的其余部分安排如下。第二部分介绍以前的相关工作。第三部分说明了ASTK和WASTK的方法。我们在Section中展示了实验结果和相应的分析4。最后，在章节5中，我们总结了这项工作，并就未来可能的工作进行了一些讨论。

1. 相关工作

存在一些抄袭检测措施。根据Mozgovoy在2006年确定的类别^[9]，主要有基于指纹和基于内容比较的方法。内容比较技术有三个子类别，包括字符串匹配算法，参数化匹配算法和解析树比较算法。

MOSS（软件相似性度量），由加州大学伯克利分校于2003年提出^[10]，作为一种建议的基于指纹的测量，将每个程序划分为k-gram。每个gram都由一些长度为k的子环组成。我们根据通过哈希运算生成的重叠指纹数来判断抄袭的可能性。

有一些著名的字符串匹配算法，包括Plague，Yap3（第三版Plague）、JPLAG和FDPS（快速抄袭检测系统）^〔11〕。这些方法首先把程序转换成corre-响应令牌序列。然后他们使用从不同程序生成的序列相似性作为通过标记间比较发现的剽窃证据。由Whale于1988年提出，是第一个将文件转换为令牌序列并使用字符串匹配技术进行比较的人^[12]。由Wise在1996年提出的YAP3，由于使用Running Karp-Rabin贪婪字符串拼贴（RKR-GST）的更快转换方法，性能优于Plague^[13]。Malpohl在2006年提出的JPlag的运行速度甚至超过作为另一种类似于YAP3的算法，需要更多关注。关于Mozgovoy等人提出的效率问题。在2007年^[15]，它使用索引数据结构来存储支持更快搜索的匹配。

Baker于1995年提出的DUP工具是一个参数化的匹配算法。它首先使用词汇分析器扫描一个程序。然后它将所有标识符和常量修改为相同的符号并一起输出转换后的程序参数候选列表。相似性是确定的根据是两个变型之间的p-匹配进行开采文件，其中p表示参数^[16]。

Sim和Brass基于解析树比较算法。Sim，由Gitchell和Tran于1999年提出，通过词法分析器得到一个标记序列，并将序列比对计算为相似性^[17]。为了不受标识符或声明命令的影响，2014年，Kikuchi等人。提出了一种修改方法，该方法使用具有词法元素的标记的句法元素，并且该方法不包括标记中的标识符名称或文字值[4]。 黄铜，由Belkhouche等人提出。在2004年，是一个解析树比较算法的应用。它将每个文件表示为二叉树和符号表（数据字典），包含文件^[18]中使用的变量和数据结构。

1. 提议的方法

定义1（抽象语法树）。抽象语法树是一种树形式的源代码的抽象语法结构。

图像1显示了从简短示例代码创建的抽象语法树的示例。左侧部分是两行中的源代码，右侧部分是词法和语法分析后的相应抽象语法树。很容易发现一小段源代码有一个大的抽象语法树，只有叶节点显示源代码的符号。所有叶节点的有序遍历结果将获得源代码。

图 1 一段源代码及其对应的抽象语法树

定义2（树内核）。树内核是一种计算树结构和测量自然语言处理（NLP）中两个内容之间相似性的算法，这是Collins和Duffy在2001年首次提出的^[7]。

在两棵树T1和T2之间，一个内核（T1，T2）可以是表示为两个向量之间的内积：

每棵树T代表了向量h(?) =(ℎ 1 (?)，ℎ 2 (?)，。。。，ℎ ? (?))。

定义3（TF-IDF）。在信息检索中，TF-IDF是一个数值统计模型，旨在反映重要信息一个词对文档集合中的文献^〔8〕。

TF-IDF包括两部分：TF是“词频”的缩写，IDF是”逆向文件频率“的缩写。文档频率。“TF（t,d）表示在所有文档集中包含单词的文档的频率。idf是df的倒数。TF专注于文档中单词的重要性，而IDF关注的是所有文件中文字的普遍性。TF-IDF有助于解决问题4和5。

WASTK的过程如图2所示。所提出的方法首先将程序转换为抽象语法树。受TF-IDF思想的启发，计算每个子树的权重，在文档中给出高频率的表达，但在其他文档中低频率的权重较高，并且给出在所有文档中（在所有文档中）较低权重的表达式。最后，在节点上应用树核计算权重以确定是否发生抄袭。设计方法的细节如图所示2。

图 2 加权抽象语法树内核

• 1. 调整抽象语法树的结构

为了解决问题1，程序被解析为抽象语法树，以进一步理解语义。

然后对每个抽象语法树应用一些调整。正如问题所述2，替换数组的变量名和大小声明是剽窃的常见方法。要解决此问题，所有变量令牌都将替换为统一令牌。数组大小声明的标记和数组元素的索引也是统一的。

因为将表达式重新表达为不同的表达式并非易事，所以通过修改表达式很少会出现关于剽窃的问题。遗弃了与抽象语法树中的子树相关的表达式的结构信息。子树上叶子节点的有序遍历的结果字符串被用作子树的替换。此外，简化的抽象语法树可以减少运行ASTK和WASTK所需的时间，从而有助于解决问题3。

经过调整，图1中的抽象语法树是转换为图3所示的新树。所有变量名称替换为“temp”，因为节点“exp”是一种表达式，它被调整为叶节点，并且将in orderTraversalofelafnode表示为上一个带有根“exp”的子树；即虚线部分图3中是从原始抽象语法中删去的树。

图 3 调整后的语法树

• 1. 调整抽象语法树的结构

在ASTK中，所有节点上的权重等于1。但是，在WASTK中，节点的权重取决于TF-IDF。实际上，这是ASTK和WASTK之间的唯一区别。在WASTK中，认为抽象语法树节点上的权重反映了相应的子树代码片段的重要性。遇到问题4 和5 考虑到，较低权重被赋予表示出现在许多其他程序中的共同表达的节点。

程序中经常出现不同类型的符号和表达式。它们没有丰富的语义并且可以被当作停止单词，停止单词集合展示在表1中。

表 1 停止词列表

设T代表抽象语法树。对每一个子树T，有一个权重W_s,T。它的有序遍历代表一个单词s。如果该单词s是一个停用词，则s的权重则调整为0，即w为0。相反的，如不是停用词，W_s,T按照如下式子计算：

通过定义3，TF和IDF可以根据如下式子计算：

其中Cnt代表子树的频率，n代表子树个数，c(s)代表含s的抽象语法树的子树个数。N代表从相关的任务代表生成的抽象语法树。

• 1. 计算树核与相似度。通过定义二，其距离计算如下：

更高效的计算方法如下：

C(s1，s2)如下计算：

1) 如果s1与s2都是叶结点

其中，树是一个避免变化的衰减因子靠近根部产生过大影响[6]。AS高度增加，子树的内核值受（树）大小的限制，其中大小是子树。单词是按顺序表示的字符串子树上的遍历。距离计算定义如下：

Lev代表字符串a与b的距离。|a|是字符串a的长度。不同于传统的树核，表达的相似性不等于0、而是被两种表达的编辑距离。通过使用这种定义，表达式等级的改进可被ASTK和WASTK发掘。

2) 如果s1和s2的根不同，则：

3) 如果s1和s2的根都是叶节点，则：

4) 否则：

n(s)代表了子树的数量，st(s，i)是根节点的第i个子树。因为s1的根和s2

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19768]，资料为PDF文档或Word文档，PDF文档可免费转换为Word