流程图生成的源代码相似检测使用过程挖掘

文摘

源代码相似检测计算机程序设计教学中有着广泛的应用前景和软件知识产权保护。在计算机程序设计课程的教学,学生可以利用一些复杂的代码混淆技术来源,例如,不透明的谓词,循环展开,内联函数和概述,减少代码片段之间的相似性和避免剽窃检测。现有的源代码相似度检测方法只考虑源代码的静态特性,使得它难以应付更复杂的代码混淆技术。在本文中,我们提出一个新颖的源代码相似度检测方法通过考虑动态特性在运行时使用过程挖掘的源代码。更具体地说,鉴于两块源代码,他们运行日志通过源代码插装和执行。接下来,过程挖掘是用于获得两块源代码的流程图通过分析他们收集运行日志。最后,相似的两块源代码是衡量计算这两个流程图的相似性。实验结果表明,该方法可以处理更复杂的模糊技术包括不透明谓词和循环展开内联函数和概括,不能由现有的正常工作。因此,我们认为,我们的方法可以更有效地打败常用的代码混淆技术的源代码相似比现有最先进的检测方法。

1。介绍

研究研究源代码相似度检测,可以追溯到1970年代,这样的技术已经广泛的应用于计算机编程的源代码剽窃检测教学和软件知识产权保护。现有代码相似性检测技术主要涉及属性计算(1)和结构指标(2- - - - - -13]。结构指标主要包含基于字符串的最常用的方法,基于树和基于代码相似性度量方法。在当前计算机程序设计课程教学,在线法官(OJ)系统(14)实现网上提交和自动编程的评估作业已广泛应用。同时,橙汁使用代码相似性检测工具发现剽窃在编程任务。支持代码相似性检测,大多数现有的橙汁系统使用基于字符串和基于树的检测方法。然而,antiobfuscation这些方法的有效性较弱,因为他们只能处理一些简单的代码混淆技术(15- - - - - -18]。在计算机程序设计教学中,学生有时使用一些复杂的代码混淆技术,例如,不透明的谓词,循环展开,内联函数和概述,减少代码片段之间的相似性。然而,现有的方法不能处理这些复杂的模糊技术。这个问题的主要原因是现有方法测量代码相似度只有源代码的静态特性,如文本或结构,他们不考虑源代码运行时的动态特性。因此,现有方法无法应对上述复杂的模糊技术。

为了解决这个问题,我们提出一个新的源代码相似度检测方法对计算机编程教学使用过程挖掘。源代码的动态特性是通过运行的代码,并使用它们为基础测量两个代码片段之间的相似性。具体地说,鉴于两块源代码,我们首先获得他们的运行日志由源代码插装和运行。接下来,过程挖掘是用于获得他们的流程图,以反映在运行时动态特性。最后,相似性可以衡量两个流程图图相似度算法和相似性值作为最后的这两块代码的相似。

本文的其余部分的结构如下。部分2介绍了代码混淆技术的分类和现有代码相似性检测方法。部分3提出了基本思路和整体框架源代码的相似性检测方法基于过程挖掘。接下来,节4详细介绍了方法,我们的方法的有效性通过实验验证部分5。最后,整个工作部分进行了总结6。

2。相关工作

antiobfuscation的性能是一个重要的指标来评估代码相似性检测(19]。因此,我们首先总结本节最常用的代码混淆技术。然后,我们介绍了现有的源代码相似度检测方法和他们对抗代码混淆技术的能力,在此基础上,我们总结现有方法的问题。

2.1。代码混淆

琼斯总结了十个常用方法剽窃编程作业的学生(20.]。在此基础上,提出了两个代码混淆技术在文献[15,21]。总之,主要有十四种模糊技术,如图1从简单到困难:(1)逐字复制;(2)改变评论;(3)改变空白和格式;(4)重命名标识符;(5)重新排序代码块;在代码块(6)重新排序语句;(7)取代常量;(8)改变运营商或操作数的顺序表达式;(9)改变数据类型;(10)中添加多余的语句; (11) splitting expressions; (12) replacing control structures with equivalent structures; (13) loop unrolling; (14) function inlining and outlining.

我们进一步详细分类添加多余的语句和循环展开。首先,添加多余的语句可分为添加顺序语句,增加可及分支机构,和不透明谓词。具体来说,添加顺序语句是指添加顺序执行的代码,可以在不影响运行结果;添加可及分支是指添加多余的添加可执行的分支,在不改变结果;不透明谓词(21]是一种控制流混淆技术,它将不可到达的路径或分支添加到源代码不改变最终结果。第二,循环展开分为部分展开,全面展开,它降低了周期和数量的增加源代码通过复制一个循环体中的代码15]。

2.2。源代码相似度检测

第一种方法的源代码相似度量属性计算(22),主要措施的相似性计算各种指标的源代码。因为太多的结构信息的源代码被丢弃,这些方法的准确性较低。因此,研究人员提出的方法基于结构指标,主要是基于字符串、树和图。

基于字符串的源代码相似度检测方法比较的文本代码。现在这种方法相对成熟,有一些常用的软件系统,比如JPlag [2],苔藓[3],Sim卡(4]。同样,在克隆检测方面,基于字符串的复制检测系统可用于大型代码提出(23]。虽然源代码基于字符串的相似度检测方法具有较高的时空效率,他们很少反映代码的语义和句法信息。因此,这些方法很难对抗一些复杂的代码混淆技术。

基于树的相似度检测方法的源代码转换成一个树结构和测量树木之间的相似性。例如,AST-CC算法[5将源代码转换成一个抽象语法树,提高语法树的效率比较通过转换存储格式。这种方法比基于字符串的代码相似性检测方法antiobfuscation能力更强。此外,在代码克隆检测方面,基于树的代码克隆检测方法也提出了(24,25]。然而,基于树的方法主要是测量通过子树的相似性。结果是,他们无法对抗结构模糊技术(20.),如添加多余的语句和循环展开。因此,这种方法只能解决简单的代码混淆技术。

基于源代码相似度检测方法将代码转换为图结构和比较图之间的相似度。目前,现有方法使用两种类型的图表:程序依赖图(PDG)和控制流图(CFG)。首先,刘等人提出的GPLAG PDG构造一个(6)根据源代码和计算两个pdg之间的相似性。虽然PDG包含语义信息的源代码,GPLAG只能检测两个单独的函数而不是多个函数之间的相似性(7]。与此同时,它仍然是容易保持语义的代码陷阱技术,如不透明谓词(8)函数内联和概述(9]。此外,在代码克隆检测方面,PDG和程序切片用于发现代表克隆(PDG同构子图26]。第二,林等人提出使用CFG显示源代码的控制结构10)和代码片段之间的相似性计算分析CFG的k-length流路径。同样,邱et al。27)提出一个容错图匹配方法。匹配两个cfg是通过匹配的子路径的基本块(一个语句顺序执行序列只有一个入口和一个出口)的两个代码,然后代码相似度的加权相似度计算每条路径。在这些方法中,源代码控制逻辑的反映可能的执行路径的代码。然而,由于这种方法不能得到的实际运行路径源代码,他们仍然无法抗拒一些复杂的代码混淆技术,如模糊谓词和重新排序的代码块。此外,一种方法测量跨编程语言代码相似性提出了基于源代码的静态流程图(11]。同样,这种方法只考虑静态字符的代码流,使得它难以对抗不透明谓词和内联函数和概述。总之,基于代码相似性检测方法不能处理一些代码混淆技术包括不透明谓词,循环展开和其他一些复杂的代码混淆技术。

3所示。一种方法概述

3.1。基本思想

现有工作措施源代码相似的静态特性,如源代码的文本或结构,而不考虑运行时动态特性的源代码。图2显示了一个示例的源代码打印的和1 + 2 + 3 +…+ 100,以及剽窃的代码使用了两个模糊技术:循环展开和添加多余的语句。两个代码片段所示图2(一)和图2分别(c)。添加冗余语句之后,这两个代码片段的文本和结构有差异。把流程图为例。源代码的流程图如图2(b),混淆代码的流程图如图2(d)。两个陷阱的使用减少了相似性的流程图和混淆代码的源代码。因此,传统的来源相似度检测方法基于静态特性的代码不能处理这些模糊技术。为了解决这个问题,我们建议获得源代码的动态特性通过代码的运行和使用的动态特性来衡量两个代码片段之间的相似性。

源代码的动态特性是该方法的关键。两个代码片段,我们首先获得他们的运行由源代码插装和运行日志。然后,我们使用过程挖掘获取流程图表明他们在运行时动态特性。过程挖掘提取过程相关信息的事件日志发现、监控和改进的实际流程(28]。过程挖掘的执行序列活动的执行日志基于现有流程实例可以开采获得活动之间的依赖关系和执行订单。因此,流程模型,表示活动之间的逻辑关系。借款流程挖掘的想法,如果我们把一段代码的输出日志通过运行一次作为一个流程实例的活动序列,得到一组输出日志多次运行代码后,这些日志可以用作输入的过程挖掘算法得到一个流程图反映的实际运行的进程代码。基于上述分析,我们建议使用过程挖掘的流程图通过开采产生的输出日志运行源代码和以流程图为代码的动态特性。因此,相似性流程图可以用来衡量相似性的源代码。通过这种方式,两块代码的更精确的相似。

3.2。框架设计

一个通用框架源代码相似检测使用过程挖掘如图3。首先,两块源代码预处理去除多余的语句。然后,一些输出语句自动插入这两种预处理代码片段(这个过程被称为“代码插装”)。通过运行两个代码片段,可以获得他们的运行日志。接下来,这两个代码片段的流程图通过挖掘这两个代码片段的日志流程挖掘算法。最后,图相似度度量算法用来计算这两个流程图之间的相似性,和价值被认为是最后的这两个代码片段之间的相似性。

4所示。建议的方法

源代码相似度检测方法详细介绍了基于过程挖掘这部分根据上述框架。这种方法主要包含以下四个步骤:(1)根据pdg预处理多余的语句;(2)自动源代码插装;(3)代码流程图生成基于过程挖掘;(4)代码相似度计算流程图。此外,给出三个例子显示了方法的有效性在打击上述三个复杂的代码混淆技术。

4.1。基于pdg预处理多余的语句

添加多余的语句是一种常见的代码混淆技术。例如,冗余变量声明语句可以减少两个代码片段的相似性。因此,有必要删除多余的语句。橙汁中的代码学生提交的作业系统,通常是最后一个语句返回或者一个输出声明。因此,如果PDG源代码转换为,PDG中的节点可以按照深度优先的顺序遍历,PDG的最终节点对应于最后的声明,和一个新的图形。语句对应的节点图中不可以被视为多余的语句,可以删除。因此,如果没有多余的语句之间的数据依赖和控制依赖和核心代码,我们可以将代码转换为PDG并找到多余的语句。算法1介绍了PDG-based预处理算法去除多余的语句,把源代码ocPDG成G(V,E,μ,δ)。在该算法中,V是声明的集合节点,E依赖节点之间的边的集合在吗V,μ声明的类型映射函数节点,δ是类型映射函数(数据依赖和控制依赖)的边缘(6]。

我们把图中的代码片段4(一)作为一个例子。考虑到代码片段得到最大价值的两个变量:一个和b的语句行2 8和9是多余的语句和他们没有数据依赖过去返回声明在第10行。图4PDG (b)是生成的代码片段,和图4PDG (c)是后删除多余的语句。最后,多余的语句行2,8,9中。

4.2。自动源代码插装

需要一定的运行日志获取代码片段的过程挖掘的流程图。然而,没有足够的打印语句,可以显示代码的流程作业。因此,有必要将一些打印语句插入到代码片段输出一些代码的运行日志。与此同时,输出日志需要指示的执行路径的代码片段,这样他们可以用作输入的过程挖掘算法。通过现有的仪器软件PDG以及节点的定义(6),我们定义两种基本类型的源代码插装语句:分配和输出。(1)分配(类型₁,……,类型_n)代表变量声明或变量赋值。类型₁,……,类型_n的变量类型是分配,类型_我∈{程序语言提供的变量类型}。(2)输出代表的print语句的代码片段。

基于两个仪表语句,我们给出以下规则源代码插装。(1)仪表语句分配(类型_我)插入后赋值和变量声明语句。如果没有数据之间的依赖多个连续赋值语句在一个基本块(27),一个仪表语句插入后最后一个赋值语句,同时所有的变量类型赋值语句合并;也就是说,分配(类型₁,……,类型_n)插入到这些语句的结束。(2)为输出语句,输出仪表插入。(3)仪器相同类型的语句顺序编号。

图5自动的显示了一个示例源代码插装Java代码的一块基于上述仪器的规则。代码的前四行是连续赋值语句在一个基本块。线1和2中的赋值语句没有数据依赖,于是他们相结合,Assign1 (int, int)根据第一条规则插入。线3和4的报表数据依赖和两个仪表语句,例如,Assign2(扫描仪)和Assign3 (int),分别后插入它们。因为有两个基本模块如果分支(5 - 9行),两个分配仪表语句插入在每一个基本块赋值语句。输出语句的最后一句话,输出仪表插入。

4.3。使用过程挖掘源代码生成流程图

的输出日志可以通过运行代码与源代码插装(插装代码)。然后,过程挖掘算法可用于矿井由输出日志分配和输出仪表语句的实际运行过程的代码所表示的过程模型。

现有的过程挖掘算法主要包括ɑ算法和启发式算法(28]。其中,ɑ算法无法处理短循环与一个或两个的长度。结果,算法无法处理的情况下循环中只有一次或两次执行代码的流程图。启发式挖掘算法(28考虑事件的频率和序列构建流程模型时,实际的运行过程,如循环和分支在源代码中可以挖掘。因此,我们使用启发式挖掘算法挖掘输出日志和生成代码流程图基于因果网络(28]。由于流程图是采自产生的输出日志运行源代码,它可以显示代码的动态特性。因此,我们称这样的流程图代码动态流程图,定义如下。

定义1。CDFC(代码动态流程图)= (V,E),V是一组分配或输出节点和E⊆V×V边的集合表示节点的顺序关系吗V。

仪表的输出日志通过每个正在运行的代码可以被视为一个流程实例的运行日志所需的过程挖掘算法。与此同时,每个分配和输出运行日志的工具代码(简称仪表输出)可以被视为一个活动的执行流程实例。序列组成的分配和输出被称为仪表的输出序列,它被认为是输入过程挖掘算法。基于这个想法,我们提出了CDFC挖掘算法,获得的日志通过运行工具代码作为输入,并输出相应的CDFC基于因果网络。插装代码需要多次运行,因此需要一组输出日志的过程挖掘算法可以获得。然后,CDFC获得使用启发式挖掘算法根据发生时间和依赖分配和输出在仪表输出序列。算法2显示了CDFC采矿过程基于启发式的过程挖掘算法。

算法2第一项直接后(2 - 6行)每两个相邻的数分配或输出在仪表输出序列。然后,之间的依赖关系(10和16行)计算两个仪表输出。最后,构建仪表输出之间的连接。因此,根据直接获得的代码流程图后数量和依赖项的值(11 - 13行,17 - 19行)。

图6给出一个示例,图6(一)显示了两个仪器仪表的输出序列代码如图5。通过两个测试用例输入5和3,分别得到了两个不同的仪器输出序列。作为显示在图6(一),要么分配4、分配5在每个仪表输出序列中执行。因此,一个互斥的分支包括在CDFC获得基于算法2,如图6 (b)。

4.4。基于图编辑距离CDFC相似性度量

两个代码片段之间的相似性可以测量两个CDFCs之间的相似性。因为CDFC是一个有向图,可以使用定向图的相似性度量方法。近年来,研究者已经提出了很多方法图相似度衡量,其中图编辑距离(GED) [29日)是一种常用的算法。GED强度计算的转换需要一个图像变换到另一个,因此这两个图形之间的不同措施。我们使用GED-based算法来计算两个CDFCs的相似性。

让CDFC₁= (V₁,E₁)和CDFC = (V₂,E₂)。图的定义CDFC之间的编辑距离₁和CDFC₂显示如下:

其中,λ_最小值表示最低成本和路径中所有完整的编辑路径;γ(CDFC₁,CDFC₂从CDFC)表示所有编辑路径₁对CDFC₂;和c (e_j)表示编辑的成本e_j。在拟议的方法,分配CDFC节点,如果变量的类型分配节点的变量类型的子集是另一个,这两个分配节点表示相同的节点。因为每条边CDFC点从一个节点到另一个的成本更换(⟶ ),删除(⟶ε),除了(ε⟶ )节点是一样的删除(⟶ε),添加(ε⟶ )的边缘。摘要操作成本函数的节点和边缘的设置。

两个CDFCs基于GED的图形编辑距离计算算法3。其基本思想是使每一个可能的编辑操作是通过处理CDFC的节点₁一个接一个。具体地说,一个搜索树建立动态和遍历搜索树的过程相当于解决一个编辑路径的过程。

在算法3,第一个顶点的CDFC₁选择通过遍历搜索树。操作和成本的价值替换和删除每个顶点在CDFC₂存储在一个初始空集(5 - 8行)。然后,运行成本最低的节点将会被遍历根据启发式搜索算法,和更换和删除剩余的节点插入操作开放组(17和18行)。毕竟节点的操作更换和删除在CDFC₁处理后完成,其余节点CDFC吗₂插入(研讨会行)。最后,编辑距离路径λ_最小值的CDFC₁和CDFC₂是获得。

考虑到源代码CDFC的流程图₁= (V₁,E₁)和流程图CDFC混淆的代码₂= (V₂,E₂),λ_最小值CDFC之间的编辑距离吗₁和CDFC₂。| CDFC | = | CDFC。V| + | CDFC。E|表示模块的价值CDFC, | CDFC。V在CDFC |表示节点的数目,| CDFC。E|表示的总和CDFC中所有边的长度。源代码和混淆的相似代码可以计算

4.5。有效对抗代码混淆

在本节中,我们分析了该方法的有效性在打击三个代码混淆技术相对复杂,不透明的谓词,循环展开,内联函数和概括,通过三个例子。

首先,用不透明的谓词,遥不可及的路径可以添加到减少两个代码片段的相似性。图中的代码片段2作为一个例子,一个遥不可及的如果分支添加(10 - 12行)在图2(c)。此外,图2 - 4行的语句2(一)代表一个循环结构,在图2 - 8行语句2(c)构成了代码混淆结果从运行时通过复制循环体代码不会改变。图中的源代码和混淆代码2插入工具代码,该方法如图7(一)和7(d),因为如果混淆代码的分支将无法执行,中的代码如果分公司将不会被执行。此外,由于循环结构改变,仪表输出的代码序列是不同的在运行这两个工具代码片段。有一百零二行源代码插装的输出序列,虽然只有22行代码混淆的仪器输出序列,如图7(b)和7分别(e)。的CDFCs启发式过程挖掘算法获得的两个代码片段所示7(c)和7分别(f)。因为变量类型Assign2CDFC源代码中节点的一个子集Assign2节点的CDFC混淆代码,两者之间的相似性CDFCs根据算法是100%3。因此,该方法可以对抗中使用的不透明谓词和循环展开图的例子2。

其次,我们分析了该方法的有效性在打击函数内联和概述。图8显示了一个示例的源代码的最大值之间的两个输入整数。混淆代码使用如果分支结构作为一个方法调用的源代码,并添加一个新的函数。因此,这两个代码片段之间的文本相似度降低。然而,CDFCs通过该方法仍然是一样的,如图8 (c)。因此,该方法可以打击内联函数和列提纲,本例中使用。

5。实验和评价

我们进行的一组实验来评估的有效性和效率提出了源代码相似度检测方法在计算机程序设计教学。首先,介绍了实验装置在5.1。在实验中使用的数据集是在5.2中引入的。接下来,在5.3中,对抗代码混淆技术的有效性提出的方法与现有的源代码相似度测量方法。此外,验证了该方法的效率与Sim和GPLAG 5.4。最后,给出了实验的结论。

5.1。实验装置

一双源代码和混淆代码,他们建议的方法和现有的相似度计算的最先进的方法。因为Sim和GPLAG是基于字符串的代表和基于相似性度量方法,分别,我们选择这两种方法相比,我们的方法。因此,我们可以验证该方法的有效性在源代码相似度检测和对抗代码混淆技术的能力。

我们进行了三个实验。首先,一个数据集的源代码,我们使用三个模糊技术在第一个实验中修改源代码:不透明的谓词,循环展开,内联函数和概述。通过这种方式,我们可以构建源代码和混淆代码对。然后,每一对的相似代码建议的方法计算,Sim, GPLAG来验证该方法的有效性在打击上述三个模糊技术。

第二,以验证该方法的实用性源代码相似度检测,实验2的antiobfuscation能力评估建议的方法通过一些常用的模糊技术,现有的方法可以对抗。具体来说,Sim, GPLAG,该方法用于比较平均相似性混淆代码的源代码和处理7个常用的代码混淆技术。

前两个实验证明该方法的能力对抗单个代码混淆技术。进一步验证该方法的有效性与多个代码混淆技术,我们选择更复杂的源代码和使用一些模糊的技术来处理源代码第三实验。然后,我们使用Sim, GPLAG和我们的方法来计算代码在antiobfuscation相似性和比较它们的有效性。

GPLAG,此外,Sim的效率相比,我们的方法是在第四实验来验证该方法的效率。

5.2。数据集

我们把代码提交的作业学生橙汁系统作为数据集。因为代码混淆技术的学生所使用的数据集是不完整的,我们混淆代码手动和源代码构建三集。应该注意的是,每个运动问题OJ系统包含一组测试用例,在每个测试用例的输入数据可以作为该方法运行时的输入源代码。因此,通过运行所有测试用例,仪表的输出序列的代码。

第一个代码集是用于第一个实验。我们随机选择20 Java编程问题从我们的橙汁系统和把他们分成四组,因此每个小组有五个问题。然后,代码修改作业的学生选择随机使用三个模糊技术:不透明的谓词,循环展开,内联函数和概述。因此,对于每个模糊技术,组成的一组实验数据二十对源代码和混淆代码在四组。

第二个代码集是用于第二个实验。我们随机选择20 Java从我们的橙汁系统中等长度的问题。与此同时,代码赋值随机选择的一个学生是混淆使用以下七个代码混淆技术:(1)改变评论;(2)重命名标识符;(3)在代码块重新排序语句;(4)取代控制结构等效结构;(5)取代常量;(6)改变数据类型;(7)分裂表达式。因此,有七个不同的混淆代码片段为每个问题。 For each obfuscation technique, twenty pairs of source code and obfuscated code are obtained in this experiment.

第三个代码集是用于第三个实验。我们选择从我们的橙汁系统复杂性高的三个问题。同时,我们选择一个随机代码分配一个学生对于每个问题,并使用以下五个代码混淆技术修改代码:重命名标识符,在代码块重新排序语句,不透明的谓词,用等效结构,取代控制结构和函数内联和概述。因此,三对源代码和混淆代码在这个实验中获得的。

5.3。实验结果

图9显示了第一个实验的结果,纵轴代表平均相似性源代码和混淆代码为每个组的五个问题,和横坐标轴代表四个代码组。源代码是由不透明谓词混淆,循环展开,内联函数和概述。不透明谓词和循环展开模糊技术冗余的字符串添加到源代码,而内联函数和概述扰乱秩序的字符串在源代码中。与此同时,pdg的结构也发生了变化。因此,antiobfuscation Sim和GPLAG在打击这三种代码混淆技术比建议的方法较差。本文的方法可以获得的实际流代码通过运行代码,因此它可以检测不透明谓词。源代码混淆的循环展开内联函数和概述,一些冗余的代码,与最终的数据依赖返回或打印语句的代码可能被添加到代码混淆。因此,这部分的冗余代码不能删除的预处理,使该方法的相似度结果略低。然而,该方法的检测精度仍比Sim和GPLAG。总之,与Sim和GPLAG相比,该方法具有更好的有效性在打击不透明谓词和循环展开以及函数内联和概述。

图10显示源代码之间的相似性和混淆代码由三个代码相似性检测方法在第二个实验中。其中,纵轴代表的平均相似度20对源代码和混淆代码混淆的一个代码混淆技术,与横坐标轴代表七个代码混淆技术。可以看出Sim, GPLAG,该方法可以处理简单的代码混淆技术包括改变评论和重命名标识符;Sim不能对抗调整语句的代码块的顺序,用等效结构代替控制结构,取代常数,和改变数据类型,而GPLAG和该方法可以打败这四个模糊技术。此外,这三个方法不能完全反对分裂表达式,因为这种模糊处理技术将一个复杂的表达式为多个简单的表达式和添加多行代码与数据的依赖。综上所述,该方法可以打败代码混淆技术可以由现有的方法。

图11显示了第三个实验的结果,纵轴代表之间的相似度值由多个模糊源代码,代码混淆技术。Sim卡的代码相似度值都小于60%。GPLAG不能在代码块重新排序影响语句,用等效结构代替控制结构,因此代码相似性检测效果优于Sim卡。然而,GPLAG措施相似的代码的静态PDG源代码,并且不能获得源代码的实际运行的特点。因此,GPLAG无法对抗不透明谓词和内联函数和概括,使每组的源代码相似度低于我们的方法。

5.4。效率评价

我们使用三组的源代码和混淆代码对第三个实验来评估该方法的效率。具体来说,我们计算每组的平均字节代码的长度和节点的数量在每个生成CDFC和比较建议的方法的执行时间与Sim和GPLAG。实验是在电脑上进行3.0 GHz Intel (R)的核心(TM) i5 - 7267 u的CPU, 8 G的内存,并赢得10。每组实验进行十次,平均运行时间作为结果。实验结果如表所示1。Sim是最快的,因为它是一个基于字符串相似性测量方法。在拟议的方法中,源代码插装,运行代码,这个过程需要挖掘,因此执行时间超过Sim和GPLAG。然而,该方法可以提供可接受的性能检测代码的相似的作业在计算机程序设计教学。

6。结论

在计算机程序设计课程的教学,学生作业提交的代码通过在线评判系统通常是解决一个特定问题的代码。这种代码通常是简短的,整体复杂性不高。然而,学生可能使用一些复杂的代码混淆技术,如不透明谓词,循环展开,内联函数和概括,以减少源代码之间的相似性。针对源代码相似度检测在计算机程序设计教学中,我们提出一个方法来衡量源代码基于采矿过程相似。通过运行源代码和输出日志的挖掘,显示的实际流动的动态特性得到源代码,用于计算相似的代码。结果表明,该方法不仅可以对抗代码混淆技术,现有方法可以失败,但也更复杂的不透明谓词和循环展开内联函数和概述,现有方法不能失败。因此,该方法与现有方法相比antiobfuscation能力更强。从效率的角度来看,该方法的复杂性比现有的方法,因为它涉及到代码插装代码运行,过程挖掘和图形相似性度量。因此,性能需要进一步改善。然而,该方法可以满足代码相似性检测的实际需求在计算机程序设计教学。 Meanwhile, the proposed approach can be combined with the existing approaches in the practical application of OJ and other systems. For example, some existing approach can be used first to measure the code similarity. Then, the proposed approach can be used further when the obtained similarity is lower than a given threshold. In addition, the dynamic flow chart of the source code obtained by process mining represents the dynamic feature of the source code by the graphical process, which can also provide the basis for code plagiarism.

作为一个改善现有的静态分析的方法,该方法探讨了源代码基于动态特性的相似性度量。然而,仍存在一些问题,需要进一步调查。首先,这种方法不可能战胜一些更复杂的模糊技术,如添加顺序语句有数据依赖的核心过程,添加可及分支机构和分裂表达式。其次,该方法的效率需要进一步提高由于其较高的时间复杂度。因此,以下可能的未来应该探索工作。首先,结合现有的静态相似度检测方法,代码相似性检测方法结合静态和动态特性可以调查。此外,还有一些工作,使用机器学习技术30.]来衡量相似的源代码和获得更高的精度。因此,我们可以加强我们的建议的方法通过机器学习技术,特别是深度学习技术(31日]。第二,源代码插装语句和规则的建议的方法相对简单。因此,两个代码片段,获得的相似性可能高于在某些情况下他们真正的相似性。因此,源代码插装语句和规则可以进一步优化来获得更准确的相似性和处理更复杂的代码混淆技术。最后,这种方法的效率需要进一步提高,适用于大规模的相似性检测源代码。

数据可用性

我们把学生作业提交的代码橙汁系统作为数据集,和一个加密版本的数据集可以从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项研究是由教育部人文社会科学研究青年基金项目(“User-Steering教育多源数据集成方法研究大数据环境”与格兰特19 yjczh240数量和“动态演化研究政府的网络口碑的跟踪和评价方法在处理紧急事件基于大数据”与格兰特18号yjazh017);青岛社会科学规划研究项目(批准号QDSKL1901123);国家自然科学基金委(格兰特数字U1931207, 61902222, 31671588);科学。&技术。中国山东省发展基金(批准号2016 zdjs02a11 ZR2017MF027);山东省泰山学者计划(tsqn201909109和ts20190936);SDUST研究基金(批准号2015 tdjh102);教育教学研究“星座”项目山东科技大学(批准号QX2018M22);和SDUST优秀教学团队建设计划(批准号JXTD20180503)。

引用

1. s .恩格斯诉看到,m·克雷格“剽窃检测采用基于功能的神经网络,”ACM SIGCSE公告,39卷,不。1、品种马非常,2007页。视图:出版商的网站|谷歌学术搜索
2. l . Prechelt g . Malpohl和m . Philippsen”中发现剽窃与JPlag一组项目,“通用计算机科学杂志》上,8卷,不。11日,第1038 - 1016页,2002年。视图:谷歌学术搜索
3. k·w·鲍耶和l . o .大厅,“体验使用苔藓检测作弊编程作业,”学报99教育前沿。29日5年边疆教育会议。设计科学和工程教育的未来。会议论文集,3卷,页在18到22岁,圣胡安,公关,美国,1999年11月。视图:出版商的网站|谷歌学术搜索
4. d . Gitchell和n . Tran“Sim卡”,ACM SIGCSE公告没有,卷。31日。1,第270 - 266页,1999。视图:出版商的网站|谷歌学术搜索
5. j·冯、b .崔和k .夏”代码比较算法基于AST的剽窃检测”新兴智能数据和网络技术1卷,第397 - 393页,2013年。视图:谷歌学术搜索
6. c . c . Liu, j·汉et al .,“检测抄袭的软件程序依赖图的分析,”第12届ACM SIGKDD国际会议程序知识发现和数据挖掘,页872 - 881年,费城,宾夕法尼亚州,美国,2006年8月。视图:谷歌学术搜索
7. >、h·h·严和x w·张,“代码相似性检测的程序依赖图,”《计算机工程国际会议和信息系统,第261 - 255页,维也纳,奥地利,2016年5月。视图:谷歌学术搜索
8. y . c . Jhi x, x贾et al .,”价值取向的程序软件剽窃检测、表征及其应用”美国第33软件工程国际会议火奴鲁鲁,页756 - 765年,美国,2011年5月,你好。视图:谷歌学术搜索
9. 朱x, y . c . Jhi s . et al .,“检测软件通过基于系统调用的胎记,盗窃”《会议25日计算机安全应用程序,页149 - 158,东京,日本,2009年12月。视图:谷歌学术搜索
10. 我的。Lim, h .公园,美国崔,t·汉“盗窃的方法检测Java程序控制流信息,通过分析”信息与软件技术,51卷,不。9日,第1350 - 1338页,2009年。视图:出版商的网站|谷歌学术搜索
11. 问:歌曲,研究跨语言代码相似性检测方法基于程序流程图、山东科技大学、青岛,中国,2019。
12. p . j .明氏,d . Wu Liu和朱,“Deviation-based obfuscation-resilient程序与应用程序软件剽窃检测等价性检查,”IEEE可靠性,卷65,不。4、1647 - 1664年,2016页。视图:出版商的网站|谷歌学术搜索
13. d .傅y徐、h . Yu和b·杨”Wastk:加权抽象语法树内核源代码剽窃检测方法,”科学的规划卷,2017年,页1 - 8,2017。视图:出版商的网站|谷歌学术搜索
14. 沃斯克,m . Antczak j . Badura A . Laskowski和t .胸骨,“在线评判系统和他们的应用程序的一项调查,“Acm计算调查,51卷,不。1,猴,2018页。视图:出版商的网站|谷歌学术搜索
15. c . Ragkhitwetsagul j . Krinke d·克拉克,“比较代码相似性分析器,”经验软件工程,23卷,不。4、2464 - 2519年,2018页。视图:出版商的网站|谷歌学术搜索
16. 诉j·马林和c·r·Rivero”框架从源代码,生成程序依赖图”第四届ACM SIGSOFT学报》国际研讨会伟湖,页30-36,FL,美国,2018年11月。视图:出版商的网站|谷歌学术搜索
17. m·诺瓦克,d . Kermek和m .快乐,“校准的源代码相似度检测工具客观比较,”学报》第41届国际会议在信息和通信技术,页0794 - 0799,电子和微电子学、奥帕,克罗地亚,2018年5月。视图:谷歌学术搜索
18. m . j . Mišićd . v . Nikolov j .Ž。Protićet al .,“销售税的并行化算法源代码相似度检测,”24日电信论坛程序IEEE,页1 - 4,贝尔格莱德,塞尔维亚,2016年11月。视图:谷歌学术搜索
19. m·诺瓦克m .快乐,和d . Kermek”源代码相似度检测和检测工具使用在学术界:系统回顾,“Acm交易计算教育,19卷,不。3,27-37,2019页。视图:出版商的网站|谷歌学术搜索
20. e·l·琼斯,“指标剽窃监测为基础,计算科学学院杂志》上,16卷,不。4、253 - 261年,2001页。视图:谷歌学术搜索
21. g·迈尔斯和c . Collberg”检测软件通过整个程序路径胎记,盗窃”在计算机科学的课堂讲稿卷,3225年,第415 - 404页,2004年。视图:出版商的网站|谷歌学术搜索
22. g .鲸鱼”,软件度量和剽窃检测。”系统和软件杂志》上,13卷,不。2、131 - 138年,1990页。视图:出版商的网站|谷歌学术搜索
23. t . Kamiya s Kusumoto, k .井上“CCFinder:口令multilinguistic大型源代码,代码克隆检测系统”IEEE软件工程,28卷,不。7,654 - 670年,2002页。视图:出版商的网站|谷歌学术搜索
24. m··l·江z苏,“可伸缩语义检测克隆”学报30软件工程国际会议(ICSE ' 08),页321 - 330,纽约,纽约,美国,2008年5月。视图:谷歌学术搜索
25. l .江z苏,g . Misherghi et al .,“迪卡:可伸缩的和准确的基于树的检测代码克隆,”软件工程学报》第29届国际会议上2007年5月,明尼阿波利斯,美国。视图:出版商的网站|谷歌学术搜索
26. r . Komondoor和s·霍维兹”,在源代码中使用切片来识别重复,”第八届国际研讨会静态分析学报》上,页40-56,巴黎,法国,2001年7月。视图:谷歌学术搜索
27. d .秋,j .太阳,h·李,“改善Java程序的相似性测量基于控制流图的最优匹配,”软件工程和知识工程的国际期刊,25卷,不。7,1171 - 1197年,2015页。视图:出版商的网站|谷歌学术搜索
28. l . Maruster a·j·m·m·Weijters w·m·p·v·d·阿尔斯特et al .,“采矿过程:发现直接后继流程日志,”《发现科学国际会议,DS 2002,吕贝克,德国,2002年11月。视图:谷歌学术搜索
29. z Abu-Aisheh, r . Raveaux j.y. Ramel et al .,”一个精确的图形编辑距离算法解决模式识别问题,”学报》国际会议模式识别应用程序和方法,1卷,页271 - 278,里斯本,葡萄牙,2015年1月。视图:谷歌学术搜索
30. 黄z . j . Tang g .山j .倪y . Chen和c·王,”一个高效passenger-hunting推荐框架与多任务学习,”IEEE物联网》第六卷,没有。5,7713 - 7721年,2019页。视图:出版商的网站|谷歌学术搜索
31. 赵,d . m . Zhang和h·w·黄,“深上优于图像实例分割水分是盾构隧道衬砌,”隧道与地下空间技术,卷95,不。1、1 - 11,2020页。视图:出版商的网站|谷歌学术搜索

版权

版权©2020张冯et al。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。