（计算机应用技术专业论文）程序代码抄袭检测中串匹配算法的研究与实现.pdf

内蒙古师范大学硕士学位论文 中文摘要 学生程序作业的抄袭严重影响了教学效果，检测出抄袭的作业并对 存在抄袭的学生进行适当的惩罚，在一定程度上可以降低抄袭的发生次 数，进而提高学生程序设计类课程的学习效果，激发学生的学习热情。 如果程序作业抄袭检测通过人工来完成，可见找出存在抄袭嫌疑的作业 对象是一件繁琐、低效的工作。应用程序代码抄袭检测系统可以实现程 序代码抄袭的自动检测，为教师判定抄袭提供辅助，可以有效的减轻教 师的工作量。除此之外，该项技术还可以应用在软件的版权鉴定以及软 件的版本判定等方面。 本文首先介绍了有关程序代码抄袭检测技术的相关理论，包括程序 代码抄袭检测的实现过程、关键技术、检测效果以及一些现有的抄袭检 测系统。并对应用程序抄袭检测系统检测学生程序作业抄袭的可用性进 行了相关的探讨。 串匹配算法是程序代码抄袭检测中标记匹配的重要算法，程序代码 的编写特点决定了标记匹配结果不应该受模式串的长度及标记位置等 因素的影响，而传统的模式匹配无法准确解决这个问题。因此，本文主 要研究了适用在程序代码抄袭检测中的串匹配算法，通过分析几种抄袭 检测系统中标记匹配算法，包括动态程序设计方法、h e c k e l 算法、g s t 算法，总结了它们应用在抄袭柃测中的优点与不足，并对其中较为高效 的串匹配算法一g s t 算法及其改进算法r k r g s t 算法进行研究与实 王见。 内蒙古师范大学硕士学位论文 最后本文对g s t 及砌 一g s t 算法的实现程序进行了相关实验， 通过实验结果分析及实例演示表明该算法对于程序标记匹配过程适用。 关键词：程序代码抄袭检测，串匹配算法，k r 算法，g s t 算法，砌 一g s t 算法 内蒙古师范大学硕士学位论文 a b s t r a c t p l a g i a r i s mi ns t u d e n tp r o g r a mt a s k sm a k e sb a de f f e c tt ot e a c h i n g d e t e c t i n gp l a g i a r i s mt a s k sa n dp u n i s h i n gt h es t u d e n t sw h op l a g i a r i z eo t h e r s i sh e l p f u lt of a l l t h en u m b e ro fp l a g i a r i s m ，s ot h i sc a ni m p r o v et h es t u d y e f r e c t i n p r o g r a m m i n gc o u r s ea n di n s p i r et h es t u d e n t sw o r k i n gh a 珂 h o w e v e r d e t e c t i n gp l a g i a r i s mm a n u a l l ya n df i n d i n gs u s p i c i o u sp r o g r a m t a s ki st r o u b l e s o m ea n di n v a l i d a p p l i c a t i o nt h ed e t e c t i n gs o r w a r ec a n r e a l i z et h ea u t o m a t i cd i s p o s a l ，a n dh e l pt e a c h e rt oal a 玛ed e g r e e i no t h e r w a y s ，t h e 印p r o a c ha l s oc a na p p l yf o rd e t e c t i n gs o r w a r ee d i t i o na n d c o p y r i g h t t h i sd i s s e r t a t i o ni n t r o d u c e st h et h e o 哕a b o u td e t e c t i n gf o rp r o g m m c o d e ，i n c l u d i n gt h ei e a l i z a t i o n ，k e yt e c h n o l o g y ；d e t e c t i n ge f r e c ta n ds o m e 印p l i e ds y s t e m t h i sd i s s e r t a t i o na l s oa 玛u e st h eu s a b i l i t yo fa p p l i c a t i o nt h e d e t e c t i o ns y s t e mo nd e t e c t i n gs t l j d e n tt a s k s s t n gm a t c h i n ga r i t h m e t i ci sa ni m p o r t a n ta p p r o a c hi nt o k e n sm a t c h i n g o fd e t e c t i n gp l a g i a r i s mf o rp r o g r a mc o d e ，a n dt h ec h a r a c t e r i s t i co fp r o g r a m c o d ed e m a n dt h em a t c h i n gr e s u l ts h o u l dn o tc h a n g eb e c a u s eo ft h ep a t t e m l e n 酉ho rt h et o k e np o s i t i o no ro t h e rf a c t o r s t h ed is s e r t a t i o nm a i n l ys t u d i e s t h es t r i n gm a t c h i n ga r i t h m e t i ct h a ti s 印p r o p r i a t et od e t e c t i n gp l a g i a f i s mf o r p r o g r a m c o d e a n a l y z i n g s e v e r a la r i t h m e t i ct h a th a st a k e n b ys o m e d e t e c t i n gs y s t e m ，s u c h a st h e d y n a m i cp r o g r a m m i n ga p p r o a c h ，h e c h e l a r i t h m e t i ca n dg s ta r i t h m e t i c a n ds u m m a r i z et h e s ea r i t h m e t i c sm e r i ta n d s h o r t a g e a r e rt h ec o m p a r eo fa b o v ea r i t h m e t i c ，t h eg s ta r i t h m e t i ci sm o r e a p p r o p 订a t e s ot h i sd i s s e r t a t i o nr e s e a r c ha n dr e a l i z et h eg s ta 订t h m e t i ca n d t h ei m p r o v e m e n ta t h m e t i co fg s t r k r g s ta t h m e t i c 内蒙古师范大学硕士学位论文 t h ed i s s e r t a t i o nt a k e sc o n e l a t i v ee x p e r i m e n tf o rg s ta 1 1 d 砌 r g s t a r i t h m e t i c t h ee n e c t ss h o wt h a tt h e s et o wa r i t h m e t i ca r ea p p r o p r i a t et o p r o g r 锄t o k e n sm a t c h k e yw o r d s ：d e t e c t i n gp l a g i a r i s m f o rp r o g r 锄c o d e ， s t r i n gm a t c h i n g a t h m e t i c ，k ra r i t h m e t i c ，g s ta r i t h m e t i c ，r k r g s ta r i t h m e t i c 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果，尽我所知，除了文中特别加以标注和 致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含本人为获得内蒙古师范大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示感谢。 签名：二眦日期：咿云年月f 弓日 关于论文使用授权的说明 本学位论文作者完全了解内蒙古师范大学有关保留、使用学 位论文的规定：内蒙古师范大学有权保留并向国家有关部门或机 构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子 文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 张动撕导师鲐剥斟 7 日期：w 口鼋年月弓日 第一章绪论 1 1 研究意义 第一章绪论 由于信息技术的发展，特别是互联网的发展，获取信息资源就变得更加方便和 快捷，同时抄袭也就变得更加容易。在程序类课程中，作业是以电子文档的形式存 储的，因此，学生可以直接将互联网上或其它学生的作业拷贝过来，简单的修改或 不做任何修改直接交给教师。抄袭让学生养成懒惰的习惯，将使部分学生一无所获。 要抑制抄袭之风就要对抄袭行为严惩，首先就要找出存在抄袭行为的学生。如果通 过教师在大量程序作业中人工的进行比对，检查抄袭将是一件相当繁重的工作。程 序代码抄袭检测系统可以对大量的程序作业中的每一对程序代码进行比对，得到每 对程序的相似性情况，并将结果显示给用户。这些结果能帮助教师找出存在抄袭嫌 疑的作业对象并为进一步判定抄袭提供一定的参考，使用该系统将在很大程度上提 高教师检测抄袭的效率，节省大量的工作时间。 除此之外，在软件商业领域中，如果发生有一方认为另一方抄袭了其产品的内 部核心技术的情况，使用一种高效的抄袭检测系统对两个软件产品进行检测，其结 果将对最终的司法鉴定提供很大的帮助。目前，随着对知识产权的重视程度的提高， 以及对软件产品保护力度的加强，有关该项目的研究也越来越受到关注。 另外，如果检测的是自然语言文本文档，比如学生文本作业、论文等，使用抄 袭检测系统将能够发现论文中存在的抄袭。由于论文抄袭严重了影响了学术氛围和 技术进步，对论文抄袭的检测也受到了相关重视。目前，一些国外的抄袭检测系统 不仅能够检测程序的抄袭，同时也能检测文本的抄袭，但是它们大部分只是对提供 的文本集进行相似比对，而对于来自网络等的抄袭检测无能为力。近年来，国外对 来自网络的抄袭检测进行了相关的研究，也提供了一些相关检测，如g o 0 9 1 e 、 e b s c o h o s t 等在提供的页面上输入一段文字，可以在相应的数据库中查找包含该文 字的文章。 程序的源代码可以看作是有一些特殊规范的文本，所以可以将程序代码作为连 续的标记串来处理。在程序代码抄袭检测中可以将程序根据一定的特征抽取方法转 内蒙古师范大学硕士学位论文 换成保留程序重要特征的标记串，然后通过匹配这些标记串来得到相似程度的信息。 这样可以降低比较程序源代码的时间，提高了检测效率。 对于程序代码相似性研究不仅可以用来判定程序代码间的抄袭，还可以用在编 程规范化研究与编程题目自动评分的相关领域中。对于初学编程的学生，培养他们 规范的编写程序是教学中的重点之一，就像语言一样，如果用标准规范的方式交流 一定会比较方面。如果编写的代码不规范这样就会影响代码的可读性与重用性，因 此在编程规范化的研究中，可以将学生编写的程序与标准的程序代码进行相似性比 较，越相似就说明规范化的程度越高。自动评分会给教师减轻很大的负担，而且准 备率会提高，但是对于主观题目的自动评分不太容易实现，对于编程题目的评分也 主要依靠教师完成。如果将编程题目的主要信息抽取出来，然后与标准评分方案进 行相似性比对，则可以计算出编程题目的分数。 在上述应用领域中，串匹配算法起着重要作用。串匹配主要用于解决模式搜索 问题，然而传统的模式搜索不能解决两个文本中找出所有的相似部分的搜索问题， 要想将传统的串匹配算法应用在程序代码标记串相似性检测中还需要做适当的修改 与改进。因而，研究并实现程序抄袭检测技术中串匹配算法对于开发一个辅助教师 进行抄袭检测的系统有着重要的实际意义，对于其它有关字符串相似性判定的应用 领域也有着一定的参考价值。 同时，串匹配问题是计算机科学中的一个基本问题，也是复杂性理论中研究的 最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生 物学等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的 串匹配算法能显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重 要的理论价值和实际意义。 1 2 研究现状 1 2 1 国外研究现状 国外对程序抄袭检测技术的研究丌始比较早，始于7 0 年代。目前已有多个较有 效的抄袭检测系统，如：j p l a g ，m o s s 【2 】及y a p 3 1 等等。它们已经成功的应用于对 学生程序的抄袭检测以及文档的抄袭的检测中。 第一罩绪论 抄袭检测技术面临的最大问题就是找到一个有效的识别器( 标记化过程) ，能 够识别抄袭而非由于程序的编程内容及技术影响的必然相似。随着抄袭“技巧的 增加，要求抄袭检测技术不仅能够检测出修改变量名及增加注释等简单的修改，还 要能够检测出复杂一些的修改，如用函数或者过程代替若干语句，调整语句的顺序 等。这就要求抄袭检测系统能够实现如下功能： 能够找到一种有效的识别器，能够便于量化。 设计合适的方法便于对量化的信息进行比较。 找出一种有效度量相似性的方法。 抄袭检测系统的最终实现通过降低比较程序文本花费的时间实现辅助人工判别 的目的。 目前，现有的抄袭检测系统判定程序或文档抄袭的依据在于比较程序或文档的 相似性，它们越相似说明它们之间抄袭的可能性越大，量化后的结果表示就是相似 度。大多数抄袭检测系统都会给出这个值，一般来说，相似度越大说明抄袭的可能 性越大。 得到相似度过程就是实现上述各功能的过程：一是将源程序转换成能够描述程 序特征的标记( t o k e n ) ，这个标记可以是字符串也可以是向量、l 文档等。二是 对转换的标记进行匹配( 比较) ，找出它们中相似的部分。三是找出一个适合的公式 用于计算匹配结果，以得到相似度的值。在第二个过程中可以应用串匹配算法实现 对标记序列的匹配查找，然后使用某一的公式计算出相似度的值。因此，串匹配算 法在程序抄袭检测技术中起着重要的作用。 国外对应用在程序抄袭检测技术中的串匹配算法有着一定的研究，其中r k r g s t 算法已经成功的用在多个检测系统( j p l a g ，y a p 等) 中。同时，该算法还可 以用来检测生物序列的相似程度。该算法与其它用于检测串相似性的算法相比有着 检测效率高，速度快的优点，经过实验表明该算法的平均时间复杂度接近线性。 1 2 2 国内研究现状 1 9 8 8 年，中国人民警官大学的张文典和任冬伟4 】丌发了一个p a s c a l 语言程序 抄袭检测系统。在该系统中，将p a s c a l 语言属性分为四大类：控制类、变量类、 运算符类及标准过程类。首先，它的统计模块接收p a s c a l 语言源程序，并统计源 3 内蒙古师范大学硕士学位论文 程序中的上述四种属性，存入数据文件。其次，其比较模块首先比较所有程序的四 个总属性值，如果两个程序的四个总属性值的差的绝对值均小于相应的总属性的标 准偏差，就认为这两个程序有相似可能，为其作上“可能相似”标记，并将其文件 名输出。然后，再比较有相似可能的程序的各个属性值，如果两个程序的相应属性 之差的绝对值小于该属性的标准偏差，则计算： 豇= j i l 打+ d f ，其中j i l 豇为两个程序 间相似属性的统计值，d f 为属性的权值( 由用户根据问题确定其值) 。在比较完两 个程序的所有属性，计算出最后的 打值后，再计算s 砌f 肠，= j j i 豇m ，其中s 拥池，为 两个程序的相似程度，聊为比较的属性的个数。当两个程序问的相似程度，即s 砌妇， 值大于某一阈值时，说明这两个程序是相似的。 北京邮电大学【5 】采用了基于x m l 方法的结构度量方法进行相似度的计算，并 实现了相应的实验系统。该方法先根据程序代码生成标记字符串，这个标记字符串 生成过程是基于x m l 规范的且是有结构的，然后比较指定属性的信息是否相同或 相似，根据这些信息得到相似度。 此外，国内对编程题目及主观题目的相关研究也逐步深入。哈尔滨工业大学对 编程题目的自动评分系统进行了系统的研究【6 】，实现编程题自动评分需要对程序按 照相应的模型进行处理，该模型是基于程序语义等价的思想，对源程序进行分析， 转化为程序的系统依赖图，标准化学生程序和模板程序，消除程序中等价语义表达 形式的多样性，计算它们的语义相似程度，并应用具体评分策略给学生程序进行评 分。 北京大学计算机系的刘欣，胡嵩对软件的同源性进行了相关的研究f 丌。软件的同 源性用于判断某软件是否为另一软件的变体或是否有同一作者，以此作为法律判定 的一个依据。当前软件的同源性度量技术有以下三个方面：源代码级的同源性分析、 基于文本相似性的以及基于编程风格分析的。由此可以看出，对于软件的同源性方 面的研究要比程序代码相似度的检测要复杂。 另外，内蒙古师范大学计算机学院经过近几年对程序代码抄袭检测技术的不断 研究取得了一定的进展。基本实现了基于结构度量法的程序抄袭检测实验系统。在 论文【8 】中，使用了x m l 文档来标记程序的标记串，体现了程序的结构特征，然后使 用了g s t 串匹配算法对标记串进行匹配，找出匹配的位置及长度，进而计算相似度。 4 第一章绪论 1 3 本文的目标与组织结构 本文主要讨论程序代码抄袭检测中的串匹配算法，通过对程序代码抄袭检测相关 技术的分析以及对应用于现有抄袭检测系统中的若干串匹配算法的分析，总结了用 于检测程序相似性的串匹配算法应实现的功能。并重点研究了较为高效的匹配算法 g s t 及r k r g s t 算法，分析了这两种算法的实现原理及相关技术，并提出了具 体的实现方案。最后通过相关的实验印证了g s t 算法及r l 一g s t 算法在程序代 码抄袭检测中标记匹配的有效性。 本文共分为六章，各章的主要内容如下： 第一章为绪论，对本文研究的意义、研究的现状进行了介绍。 第二章主要介绍了程序抄袭检测的相关技术，包括程序抄袭检测的实现方法与 过程，以及目前国外已经实现的用于程序抄袭检测的系统介绍。其中还论述了有关 使用程序抄袭检测系统对学生程序作业进行抄袭检测的准确程度等问题。 第三章重点介绍了串匹配技术在程序抄袭检测技术中的应用。主要介绍了串匹 配的相关技术、在程序抄袭检测系统中串匹配算法要具体解决的问题以及在现有程 序代码抄袭检测系统中使用过的若干串匹配算法，并通过具体的实验来说明这些算 法应用在程序相似性检测中的性能差异。 第四章实现了应用在程序抄袭检测技术中的算法砌 一g s t 算法，并对该算法 的基本原理与相关的关键技术进行了介绍。 第五章通过实验验证g s t 算法及r k r g s t 算法在程序抄袭检测技术中的有 效性，并通过事例演示该算法的执行结果。 第六章为总结部分，总结了本文的研究内容、研究成果以及存在的不足。 5 内蒙古师范大学硕士学位论文 第二章程序代码抄袭检测技术概述 本章主要介绍程序代码抄袭检测的相关内容，包括程序代码抄袭的表现，实现 抄袭检测的方法，程序代码抄袭检测对学生程序作业抄袭检测的准确程度以及现有 的抄袭检测系统的相关介绍等。 2 1 相关技术概述 2 1 1 程序代码抄袭描述 根据p a 出e r 和h 锄1 b l e n 在文献 9 】中的论述，如果一个程序是对另一个程序的直 接拷贝或者少量的修改而来的，则可以认为这个程序是抄袭了另一个程序。在学生 程序抄袭中，比较普遍的抄袭是一个程序对另一个程序的直接拷贝，当然也有一些 比较“聪明”一些的同学，可能会将别人的程序拿过来做了一些简单的修改。包括 改变或增加一些注解或修改一些变量名等。1 9 8 7 年f a i d h i 和r o b i n s o n 【l o 】描述了抄袭 程序代码修改的六个难度级别l 1 一l 6 。l l 级是修改原程序中的注释语句；l 2 级是 修改原程序中的标识符，如变量的名字等；l 3 级是在不影响程序正确运行的情况下 改变程序中变量声明的位置；l 4 级是用过程定义代替过程调用语句；l 5 级用等价 语句修改程序语句；l 6 级修改控制逻辑。l 1 一l 4 级的修改比较容易，l 5 级和l 6 级的修改就需要一定的程序设计知识。因此，如果学生能达到这个级别的修改水平， 说明学生已经具备了一定的程序设计能力。 对程序代码修改的难度级别不仅仅是上述划分，e d w 刹l j o n e s 【l l j 也给出了抄 袭转换原来程序的1 0 个难度级别：逐字原样拷贝原程序；更改注释语句； 更改空行及程序的格式；重命名标识符；调整代码块中语句的顺序；调整 代码块中变量声明的位置；改变表达式语句巾操作符和操作数的顺序；改变 数据类型；增加多余的语句或变量；用等价的控制结构替换原控制结构。 1 9 9 9 年j o ya n dl u c k 【1 2 】将这些抄袭转换分成了两类：一类是不依赖于程序结构 的词汇级的抄袭，另一类是需要较多技巧的“结构级”的抄袭。 其实，对于大多数初学者的抄袭都属于“词汇级”的，如果有的学生的抄袭达 6 第二章程序代码抄袭检测技术概述 到了“结构级”的说明他具备了一定的程序设计知识，这种抄袭与“词汇级 的抄 袭不应等同对待，有时在教学中也是可以提倡的。因为，毕竟对于一个程序设计的 初学者，模仿别人的程序是学习的开始。 2 1 2 程序代码抄袭检测技术概述 数字文档可分为自然语言文本和形式语言文本。自然语言文本是以自然语言描述 的文本形式存在的，比如论文、说明书及小说等。自然语言一般没有形式化的语法约 束，语义具有歧义性，因此对于自然语言文本的抄袭检测具有一定的难度。形式语言 文本是用一些形式化的语言描述的文本，比如数据文件、计算机程序代码等。形式语 言由于具有严格的形式化语法、清晰的语义表达、较少的语言成份等特点，使得对形 式语言文本的分析处理比自然语言文本的相对容易，所以对于形式化语言文本的抄袭 检测的研究也比较早。自从1 9 7 6 年o t t s t e i n 【1 3 1 提出属性计数法( 甜m i u t ec o 啪t i n g ) 用于 程序抄袭检测后，先后又出现了很多用于形式化文本抄袭检测的系统如：g d e r 的 a c c u s e 【1 4 】系统以及f a i d h i 和r o b i n s o n 的系统【1 5 】，并取得较好效果。 程序代码抄袭检测技术主要基于计算程序的组成元素或者计算这些组成元素的 结构，以此来得到程序之间的相似程度。基于程序代码抄袭检测方法的实现，可以 分为以下三类： 1 、属性技术法( a t t 曲u t ec o u n t i n g ) 较早实现的基于计算程序的组成元素的程序抄袭检测方法是h a l s t e a d 【1 6 】度量方 法。该方法用词汇量、长度和容量来标志一段程序。对一段程序，首先考虑它的如 下四个基本属性： n l = 操作符的种类数目 n 2 = 操作数的种类数目 n 1 = 所有操作符总数目 n 2 = 所有操作数总数目 基于以上四个基本属性，定义： 词汇量 n = n 1 + n 2 长度 n = n 1 + n 2 根据词汇量和执行长度再计算出该段程序的“容量”：v 划l o ( n ) 。最后将以 7 内蒙古师范大学硕士学位论文 上信息用h a l s t e a d 特征向量表征出来：h ( n ，n ，v ) 。在一组程序中，每一个程序都用 这样的特征向量表示出来，最后通过测试这些特征向量之间的“距离 来得到程序 之间的相似性。计算特征向量之间的距离的方法有多种，如e u c l i d i 锄方法，得到的 距离越小说明程序之间相似的可能性越大。以上通过提取程序中的某些属性，来计 算程序之间的相似性的方法称为属性计数法。 由于某些元素的数量相同并不能充分表达两个程序之间的相似性，后来的应用 软件在此基础上又增加了一些属性，如：g r i e r 设计的a c c u s e 【1 4 】，除了h a l s t e a d 的四个属性外还增加了代码行数、变量声明和使用数以及在程序中使用的控制语句 的数量等2 0 个属性参数。该系统和同样采用属性计数法的f a i d h i r 0 b i n s o n 【1 5 】方法 己被v c 邪。和w i s e 测试【17 1 ，证明属性计数法对于两个几乎是拷贝的程序检测效果较 好。一旦在程序中加入了一些代码或者用同样的结构替代一部分代码段，采用属性 计数法的检测系统计算的结果不理想。 2 、结构度量法( s t m c t u i em e t r i c s ) 另外一种类型的抄袭检测系统是分析程序结构的结构度量法，该方法主要通过 下列两个过程来得到相似度( 见2 1 4 相似度的定义) 的值：一是基于程序的编程 语言对程序进行语法分析，然后生成一个标记串( t o k e l l ) 序列，将每一个程序都转 换为一个字符串序列。二是根据某种匹配算法比较这些标记串，得到相似的标记序 列，然后再根据匹配结果计算相似度的值。这个过程有以下难点：一个是如何更精 确地用标识串表示程序的结构信息；另一个就是找到一个有效、快速的字符串匹配 算法，使找到的匹配结果便于计算；另外就是找出有效度量相似度的方法。结构度 量法考虑了程序的结构特性，因此，对于某些“结构级”的抄袭检测效果较好。 还有一类自动抄袭检测系统依然是属性计数度量方法，但是这些系统中加进了 程序结构的描述。一个典型的例子就是d o n a l d o n ，l a n c a s t e r 和s p o s a t o 的系统【1 8 】， 该系统中使用了八个属性同时产生一个描述程序代码的字符串。在这个字符串中的 每个字母代表单个或多个程序结构中邻接的事件，如变量声明，任务声明及过程调 用等。如果字符串的描述精确匹配或者度量结果很相近，那么，这对程序被认为抄 袭并在可疑的代码段上加上标志。这些系统中由于比较了程序的结构，体现了结构 度量的方法。因此，他们的系统足两种技术的结合。 3 、其它方法 第二章程序代码抄袭检测技术概述 除了使用属性计数技术和结构度量技术外，有的系统使用了其它方法，如基于 x m l 模型的方法和基于聚类的方法。 基于l 模型的方法：该方法首先将源程序描述成煳l 文档，然后将l 文档转换成树结构，然后再将树结构转换成矩阵，最后对两个源程序经过转换得到 的矩阵进行比较得到相似度结果。该技术已经成功应用在抄袭检测系统x p d e c 【1 9 】 中，由于在将源程序描述成v i l 文档时只对程序的三个主要部分：头文件、全局 变量以及函数进行描述，因此这种方法仅适用于面向过程的程序设计编写的程序代 码。 还有一种方法是一种聚类方法( c l u s t 舐n ga p p r o a c h ) ，该方法首先将源程序用一 个描述这个程序的关键字( k e y w o r d s ) 集合来描述，然后使用一种相似度量方法 ( s i m i l 撕t ym e a s u r e ) 来对每一对描述进行评测，然后将大于或等于某个特定的c u t o f r 嘶t e r i o nv a l u e 程序对进行进一步计算，采用的方法是w m a j o 疋l u s t 算法，该算法是 基于图聚类( 黟印h - c l u s t 甜n g ) 的思想。目前，这一方法也成功应用在抄袭检测系 统p d e t e c t 【2 0 】中。 2 1 3 相似度的定义 度。一般情况下，这个值越大说明程序越相似，抄袭的可能性也就越大。 y a i i l l a m o t ot ，m a t s u s h i t am ，k 锄i y at 和i n o u ek 【2 1 】给出两个软件系统的相似 度的定义。对于两个软件p 和q ，尸由元素b ，p ：，以组成，用集合表示为： 岛，仍，) ，同样，q 由元素g 。，g ：，吼组成，用集合表示为 g 。，g ：，吼) 。这 里的元素研，仍，n 和吼，g ：，吼可以是软件p 和q 中的文件或代码行。 假设我们能够求出b 与g ，( 1 fs 埘，1 刀) 之间的匹配，所有匹配对( 只，g ，) 的 集合用b 表示，这里匙尸q ，与b 相关的尸和q 的相似性s 定义如下： 卵渤三掣一。 如图2 1 所示，这个定义表明，尸和q 之间的相似性是一个比值，这个比值 9 内蒙古师范大学硕士学位论文 是由b 中的元素个数除以尸和q 中元素个数的总和得到的。如果b 较小，则s 将减 小，如果b = 矽，则s = o 。此外，当尸和q 完全相同时，v f ( 易，吼) b ，s = 1 。 软件系统p软件系统q 图2 1 软件系统p 与q 之间的相似性 2 1 4 关于学生程序作业抄袭检测的相关问题探讨 对于学生的程序作业，有一定的相似性是肯定的。主要原因包括以下诸方面： 学生在同一老师或同一教学环境的影响下有着相似的编程传统和风格。 在程序设计课程学习过程中，学生都处在同样一个学习的阶段。 完成某一时期的作业被限定在某些固定的解决方法中，有着编程方法的局 限。 那么对于抄袭检测系统得到的检测结果，能否正确指导教师做出正确的评判? p r e c h e l t 【l 】认为抄袭检测系统j p l a g 检测出的结果中，相似度值在0 5 区间的程序 对可以认为不存在任何情况的抄袭，对于相似度为1 0 0 的程序对几乎就可以判定 为抄袭。那么，对于相似度值在4 0 左右的程序对，通过检测系统得出的结果就不 能轻易的判定抄袭与否。如果要判定是抄袭的，则还要经过人工的参与，包括分析、 确认与调查的过程【2 2 】。 但是在教学中，检测抄袭的主要目的还是找出那些“词汇级”的抄袭，特别是 没有任何修改的完全拷贝。往往这些情况在抄袭检测系统中得到的检测结果都在 l o o 左右。 学生的程序作业一般都比较短，对于某些特别简单的问题，编写的程序代码就 几十行。因此，对于同一个问题，如果使用同一个算法解决，程序之问的相似性肯 l o 第二章程序代码抄袭检测技术概述 定会很高。这时抄袭检测系统得出的结果是否仍然具有一定的辅助效力呢? 对于这 一问题，如果对于简单的程序仍然能够表现不同学生的编程风格即独创性，则可以 说明抄袭检测系统得出的结果是有一定的效力的。华南师范大学的王桂海1 2 3 1 对程序 代码行数不多于6 0 行的程序进行了实验，实验结果表明：多数的“简单程序”，尽 管因各种制约而构成多个层次相似，但过滤各种制约因素造成的相似性之后，编程 者的某些特征，甚至是重要的特征会保留着，仍然可以反映编程者的独创性。因此， 除了个别的简单程序，大多数程序都能够区分抄袭与编制程序的制约所带来的相似 性。 较复杂问题的程序设计，编制程序的制约所带来的相似性会小于简单问题的程 序设计。因此，对复杂问题的抄袭检测的检测效果要优于简单问题的检测。但是， 在教学过程中，判定学生抄袭都是一件严肃的事情。因此，对于相似度大的程序对 在判定抄袭之前还要经过人工的核对，以免误判。 2 2 现有抄袭检测系统简介 2 2 1p l a g u e 系统 p l a g u e 系统f 2 1 1 系统是g w h a l e 于1 9 8 8 年开发的，p l a g u e 的检测分为三个阶段： 第一个阶段：将程序转换成描述其结构特征的标识序列和结构度量列表。这些 结构特征包括循环、选择语句以及语句块等。 第二个阶段：比较结构特征，结合使用特定的函数找到最相似的程序对。预期 大多数程序都是不相似的，如果有程序对是相似的，将其留到下一个阶段进行处理。 第三个阶段，使用最长公共子序列算法( l c s ) 的改进算法对标识符序列进行 比较。 p l a g u e 系统使用了结构度量技术，且比较了程序问更详细的结构信息。其缺陷 主要有如下几个： p l a g u e 系统的方法仅可以用于p a s c a l ，p r o l o g ，b o u m es h e l l 和l l 锄a ，但扩 展到对其它语言的检测工作量很大。 p 1 a g u e 系统的检测结果是两列按h 和h t 索引排序的列表，需要对其作进 一步的解释，不能做到一目了然。 内蒙古师范大学硕士学位论文 差。 p l a g u e 系统执行效率不高，又依赖于太多的u n 工具，因此可移植性较 2 2 2m o s s m o s s ( m e a s u r eo fs o 脚a r es i m i l 撕t 、，) 【2 4 】系统是由a l e xa i k e i l 于l9 9 4 年开发 的，主要用于检测c ，c + + ，j a v a ，p a s c a l ，a d a ，m l ，l i s p ，s c h e m e 等八种编程语 言编写的程序代码的相似性。m o s s 抄袭检测系统可以检测增加空格、增加无关语 句、调整语句序列等的抄袭行为。它使用算法是基于文献【2 4 】的串匹配算法。描述 如下： 程序分割成长度为k 的邻接子字符串，参数k 由用户自己定义。如：k = 2 ， 则“l e 行可以分割成“l e 、“e f ，、“r ”。 每一个长度为k 的子字符串放入相应的哈希表中。 在哈希表中选择一个子集作为程序的指纹。 比较这些指纹。 m o s s 系统提供l i n u x 、w i n d o w s 等多种平台的服务，这个服务是在线的、免 费的。用户可以使用相应的命令发送请求。在命令中包含有待检测的文件夹或文件 的指定位置，编写语言等信息。连接成功后，m o s s 会将测试结果以网页的形式反 馈给用户。在反馈信息中，可以查看比较的程序对的相似度的值，并且对相似度大 于某个阈值的程序对的相似的代码段进行同种颜色的标记。 2 2 3s i m s l m ( s o 胁a r es i m i l 撕t y1 e s t o r ) 【2 5 】系统是由d i c kg r u n e 开发的，它支持的程序设 计语言有c 、j a v a 、p a s c a l 、m o d u l a 2 、“s p 、m i r a n d a 等，同时也可以对文本文件 进行检测。该系统采用的算法是一种应用于d n a 序列相似性检测的串匹配技术： 串排列( s t r i n ga l i 印m e n t ) 。 s i m 系统首先使用标准语法分析器将源程序转换成对应的语法分析树，然后通 过语法分析树得到一个字符串。接下来，s l m 通过在字符串的字符中间插入空格的 方法将这些字符串进行排列，这样就得到一系列的排列，然后将两个程序的字符串 得到的排列进行比较得到最大的匹配，这个比较使用的方法为动态程序设计方法 1 2 第二章程序代码抄袭检测技术概述 ( d ) r 1 1 锄i cp r o 乎狮瑚i n g ) 。 s m 系统运行的时间复杂度为d ( s 2 ) ，s 是s i m 系统开始比较前生成的语法分 析树的最大长度。实验结果表明，s i m 可以用来检测计算机科学专业低年级学生程 序作业中的抄袭，包括变量改名，调整语句或函数顺序，增加或删除空格和注释等。 s m 在检测较小的程序时，运行速度比较快，在检测5 6 个平均长度为3 4 1 5 字节的 程序中每两对之间的相似性时，花费的时间大约是3 5 分钟。 2 2 4 心系列 m i c h a e lw i s e 于1 9 9 2 年开发了y a p l ，不久又开发了更优越一些的y a p 2 ，1 9 9 6 年开发出了”的最终版本y a p 3 。y a p l 和y a p 2 用于对程序代码的抄袭检测， y a p 3 不仅可以对程序代码进行抄袭检测，还可用于对自然语言文本进行相似性的 计算。 y a p 系列【3 】比较两个程序后，会给出两个程序匹配结果即相似度的值，这个值 是一个在0 到1 0 0 之间的数，表示两个程序从无关到完全相同。 y a p 系列的基本操作过程是如下两个步骤：第一步是标识化处理，这三个版本 处理过程相同。详细的步骤如下： 删除程序中的注释； 将所有的大写字母转换成小写字母； 删除程序中所有不合法的标识符； 生成基本标记串表； 将同义词映射成相同的形式，如在c 语言中，将s t m c m p 映射为s t r 伽p 。 第二步是对标识化后的字符串进行匹配，得到一个最大匹配子串，然后再计算 相似度的值。这三个版本所采用的算法不同，分别是： y a p l ：混合使用了u n i x 通用程序和命令程序脚本，如d i f f 。 y a p 2 ：使用的是h e c k e l 算法。 y a p 3 ：使用的是r k r g s t ( r u n n i n gk a 叩r a b i ng r e e d ys t r i n gt i l i n g ) 算法。 r k r g s t 算法的基础算法是g s t 算法，该算法是由澳大利哑悉尼大学的 m i c h a e l j w i s e 设计的，被用在计算两个字符串之问的相似度的值。该方法被y a p 3 1 3 堕茎查塑苎奎兰堡兰篁笙窭 及j p l a g 等系统优化，同时该算法还用在比较d n a 序列。根据该算法的应用，可以 返回两个标记串的相似度的值以及那些相似的代码段。有关算法可参见第三章。 y a p 的作者w i s e 用实验验证系统后声称，y a p 可以处理程序抄袭中的如下几 种变换： 变换程序中的注释或程序的格式； 变换程序中使用的标识符； 改变操作数的顺序； 改变变量的数据类型； 用等价的表达式替换程序中原来的表达式。y a p 完全能检测到，也可能出 现很小的偏差； 在程序中增加无用的语句或变量。增加无用变量，y a p 完全能检测到；增 加无用的语句，y a p 检测结果的准确性可能会有很小的偏差； 改变程序中独立语句的顺序，y a p 检测此种变换会出现一些问题。 改变重复语句的结构，改变选择语句的结构，用过程体代替过程调用语句， y a p 能检测到大部分这三种变换； 引入非结构化的语句，y a p 检测结果的准确性可能会有很小的偏差； 组合原来的和复制后的程序段。 实验结果证明，y a p 用于检测学生程序作业中的抄袭是非常有效的。 2 2 5j p l a g j p l a g 【l 】是由德国卡尔斯鲁厄( k 砌s 九j h e ) 大学的l p r e c h e l t ，g m a l p o h l 和m p h i p p s e l l 用j a v a 语言编写的，在互联网上提供在线的程序代码抄袭检测服务。使用 的比较算法与y a p 3 相同，也是g r e e d ys 研n gt i l i n g ，但却优化了y a p 3 的时问复杂 度。 该系统也是用来度量一个程序集合中代码文件的相似性的，当前的版本支持 j a v a ，c ，c + + ，s c h 锄e 编写的源程序和自然语言文本。 j p l a g 是按如下两个步骤计算两个程序之间的相似度的： 由源程序生成标记字符串( t o k e i ls t r i n g ) ； 比较每一对由程序所生成的标记字符串，以此来计算每一对程序之间的相 1 4 第二章程序代码抄袭检测技术概述 似度。 在j p l a g 系统里，两个源程序文件a 和b 之间的相似性按如下公式计算： 洲2 等稀产 t e n g t h ， ii 彳l ，i 曰i ：代表文件a 和b 中符号串的长度 口，6 ：分别代表最大匹配串在a 和b 中的起始位置 l彪地叻是最大匹配的长度 内蒙古9 币范大学硕士学位论文 第三章程序代码抄袭检测技术中串匹配算法的应用 串( 即字符串) 是一种重要的数据结构，计算机非数值处理的对象经常是字符 串数据，如在汇编和高级语言的编译程序，源程序和目标程序都是字符串数据。在 文本编辑问题中经常需要在一个文本中找出所有出现的模式。比较典型的一个例子： 在文本中查找用户所需要的单词( 模式串) 。字符串匹配( s t r i n gm a t c h i n g ) 是在某 段文本( t e x t ) 内找出某个模式( p a t t e n l ) 出现的位置( 如果它在哪儿能出现的话) 【2 6 1 。该问题可以应用在关键字( 词) 查找、相似性比较等应用领域中。高效的串匹 配算法可以大大的的提高该问题的解决效率。近年来，随着串匹配算法的应用领域 的扩展，人们对串匹配算法的研究也越来越深入。 3 1 串匹配问题描述 串匹配问题描述如下：假设将文本串t 描述成一个长度为n 的字符型数组 t 【1 n 】，样本串p 描述成长度为m 的字符型数组p