搜索
上海交通大学软件学院程序代码抄袭检测系统PRP论文董浩亮、张坤、杨文剑2008-7-13程序代码抄袭检测系统2008年7月13日2/19目录1摘要..................................................................................................................................32引言..................................................................................................................................33常用作弊手法...................................................................................................................34相关工作..........................................................................................................................45设计与实现......................................................................................................................46实现..................................................................................................................................67实验..................................................................................................................................88扩展应用........................................................................................................................13参考文献................................................................................................................................14附录........................................................................................................................................15A.软件架构说明.................................................................................................................15B.软件使用说明.................................................................................................................16C.使用截图........................................................................................................................18程序代码抄袭检测系统2008年7月13日3/191摘要本项目主要用以解决程序设计课程中作业抄袭的问题，项目给出了一个可以检测出一批作业集中相似或相同的程序的软件的设计、实现以及实验，并且解决了列出抄袭的具体位置列出以及抄袭结果的归类等问题。2引言本项目来源于实际教学的需要，在各程序设计类课程中，由于计算机数据的易复制性，导致许多学生抄袭他人程序作业。抄袭他人作业不仅不利于本人，也影响了成绩的公平性。然而使用传统人工方法检查作业抄袭不仅费时，且不准确。本项目意在开发一款智能抄袭检测系统，能够快速、高效、准确得查找到相类似的程序源代码，减少低年级同学学习程序过程中的抄袭现象。本项目将考虑到各种程序抄袭作弊手段，并结合现有的文章抄袭检测技术，寻求一种快速的算法，并最终完成具有实际应用价值的软件，投入到软件学院今后的教学活动中。3常用作弊手法目前，人们一般将程序抄袭定义为：一个程序经过少量修改后得到功能相同或相似的另一个程序(1)。经过对于十几个已经被确认是抄袭的程序分析和研究后，我们认为程序在被直接复制后，为了躲避侦测，主要有以下几种手法：1)增加或删除程序注释2)更改程序变量名、函数名、类名等3)更改变量类型4)更改函数位置5)将子过程展开，嵌入至调用子过程的函数中6)添加无效语句、变量7)以等效语句替代原语句8)以等价表达式替代原表达式以上作弊方式，要被侦测出的难度依次增大。目前，基于现有的技术，较易检测出前5种作弊方式。对于第7、8种作弊方式，相对来说形式多样，比如将for循环改为while循环，将i++写作i+=1等，要检测出此类作弊方式，不仅技术难度大，且在某些情况下不能断定这类相似程序就是经过抄袭得来的，因此本项目所解决的主要是前5种作弊方式。程序代码抄袭检测系统2008年7月13日4/194相关工作程序代码抄袭检测的研究可以追溯至20世纪70年代(2)，因此目前已经有一些相对成熟的技术和系统。主要的检测技术有三种，一种是基于属性技术，另一种是基于结构度量(3)。前者的方式主要是统计程序中一些特征值的数量，例如某种操作符、变量或循环体、判断体所出现的频率。后者则主要判断程序是否具有相同的结构。第三种方式则是结合前两种判定方法，给出一个综合的判定。第一种方式虽然便于实现，运行效率也高，但是其检测的准确程度往往不尽如人意，会造成大量的误判。因此本项目选择使用第二种方式作为检测的核心技术。下面列举一些目前已有的主流的代码抄袭检测系统：1.MeasureofSoftwareSimilarity该系统的网址为~aiken/moss.html，作者是AlexAiken，可以检测的程序语言有C、C++、JAVA、Pascal、Ada、ML、Lisp、Scheme等，用户可以将程序文件提交给系统，系统在检测完之后以网页的形式返回给用户。但是作者并没有提及该系统所使用的技术，因此对其实现细节我们一无所知。2.YetAnotherPlague该系统的作者是MichaelWise。从其给的技术资料看，YetAnotherPlague处理程序时，首先去除注释，随后归一化大小写，再进行同义词替换，最后进行相似度匹配。不同版本的YetAnotherPlague所使用的匹配方式也不同，1.0版本仅使用了Unix的diff等命令，2.0版本使用的是Heckel算法，3.0版本使用的是(RunningKarpRabinGreedyStringTiling算法。(4)3.JPlag该系统的作者是PrccheltL、MalpohlG和PhippsenM．JPlag在算法上与YetAnotherPlague3使用的算法相同，而在使用形式上JPlag与MeasureofSoftwareSimilarity相同，它使用JAVA语言编写，目前支持检测的语言有JAVA、C、C++。4.SoftwareSimilarityTestor该系统的作者是DickGrune，该系统使用了一种用户检测DNA序列相似性的字符串排列算法。系统首先通过一种类似于编译器的程序，将程序源代码表示为另一种紧缩的格式，这种处理算法使得其支持大多数语言，随后系统将期中一个程序的紧缩串分为若干分，每一部分到另一个程序的紧缩串中进行匹配。结合目前现有的并且相对成熟的论文抄袭检测技术，本项目使用一种被称作winnowing的算法作为检测算法，在此之前辅以一些处理方式，解决上述五种常用的作弊手段。并且提出计算相似度的方法。本项目还对原winnowing算法做了一定修改，使之能满足“查找到具体抄袭位置”、“去除教师给定代码”等扩展功能。5设计与实现1)运行流程：程序代码抄袭检测系统2008年7月13日5/19图1：程序运行流程2)流程说明处理的方法得到结果过滤处理把程序中所有的注释，空行，空格等全部去掉，只留下关键的文字部分A。替换处理把A中除关键字之外的所有变量全部替换掉(用一个字母v来表示)，这样得到字符串B。进行winnowing计算B中是以整个工程文件为单位所汇聚的一个长字符串，然后根据刚才论述的winnowing算法进行计算得到Fingerprinter。相似度比较特征值相等表示特征值所在位置的一定范围内代码的相似，而位置是之前就记录好的了。结果归类将程序相似的几个集合归为一类3)软件架构：为了提升程序的运行效率，同时又为了保证程序清晰的架构，本项目采用C++语言编写，整个程序分为若干个模块，每个模块对应的类以及详细说明可以参见附录部分。下面给出简要的说明：预处理模块：对程序源代码进行过滤处理和替换处理，负责这部分工作的C++类有AnalyCode.CPP。Winnowing计算模块：对预处理好的程序源代码进行Fingerprint的计算，负责这项工作的类是Winnowing.CPP，计算Winnowing的算法6.1节中给出详细说明。另外在这个过程中还会去除与教师代码相同部分的代码，负责这项工作的类是Teacher.CPP，去除教师代码这项工作的算法将在6.2节中给出详细说明。相似度计算模块：对两个Fingerprint集合计算其相似度，负责这一模块的类是FProcessor.CPP，在这一过程中分为两步，第一步是求出两个集合的交集，相关算法在6.3节中给出，第二步根据两个集合模和交集模的大小计算其相似度，相关算法在6.4节中给出。程序代码抄袭检测系统2008年7月13日6/19结果归类模块：将多个两两相似的程序归为一类，以方便用户浏览，负责这一工作的类是ReportInHtml.CPP，相关算法在6.5节中给出。结果输出模块：将结果以html语言的形式输出，负责这一工作的类也是ReportInHtml.CPP6算法实现程序实现主要分为以下几步：1.指纹提取2.去除与教师代码相同的指纹3.指纹匹配4.计算相似度5.抄袭结果的归类。下面着重就这五个关键步骤进行讨论1)指纹提取算法本项目使用了一种被成为Winnowing的算法作为指纹的提取算法。Winnowing的概念是UniversityofIllinois的SaulSchleimer，UCBerkeley的DanielS.Wilkerson和AlexAiken提出的，我们的算法是根据他们的论文LocalAlgorithmsforDocumentFingerprinting进行修改加工而成的。(5)算法处理过程如下：处理方法得到结果一段字符串Adorunrunrun,adorunrun，首先我们将其进行过滤处理adorunrunrunadorunrun，假设我们取它的5-gram进行分离计算对每5个字母进行分离，从开头到末尾adorudorunorunrrunruunrunnrunrrunruunrunnrunarunaduna