（计算机应用技术专业论文）程序代码相似度中的代码转换技术的研究.pdf

内蒙古师范大学硕士学位论文 中文摘要 程序代码的分词转换技术是实现程序代码相似度判别系统的一 个重要技术，一个好的分词转换技术不仅可以提高相似度判别系统中 对程序进行相似度计算的速度，还可以提高相似度计算的精度，这对 相似度判别系统的发展具有重要的现实意义。 在程序代码相似度判别系统中，程序代码的分词转换技术得到了 广泛的应用。我们可以把一个程序看作一个文本串，然后再通过一定 的文法分析将这个文本串转换成描述程序基本信息的标记( t o k e n ) 串。所以对程序相似性的比较就转变成比较两个程序的标记串。而比 较标记串的过程就是程序代码的分词转换的过程。 本研究首先介绍了关于程序代码相似度判别技术，包括程序代码 相似度判别的定义与分类，国内外研究发展的现状以及现有的程序代 码相似度判别系统的相关介绍。然后对程序代码分词转换过程中所用 到算法情况进行了介绍，包括分词算法，字符串匹配算法等。 本研究设计了一个实验系统，该实验系统主要由四部分组成，第 一部分，完成实验系统对程序代码的预处理及分词功能，预处理即去 掉那些在程序中存在，但对相似度判别无影响的信息，如程序中的注 释语句、连续的空格、空行等，接着对预处理后的程序代码进行分词； 第二部分，创建程序代码转换所需的词表；第三部分，将程序代码的 预处理及分词之后的程序采用字符串匹配算法转换为字符串标识；第 四部分是通过用户界面可得到源程序代码转换后的结果输出。 最后，通过一些实验对该实验系统进行简单的验证与分析。其中 实验的数据来自于学生所做的程序作业，实验结果反映出该实验系统 不仅可以支持多种程序语言的转换，而且转换后的实验结果可用于基 于字符串相似度判别的算法中，为后续的研究，即对转换后的标记串 进行相似度计算，从而得到相似程度的数据，提供了可靠的测试信息。 关键词：程序代码转换，相似度，词表，字符串匹配算法 a b s t r a c t 1 1 1 es e g n l e n t i n gp r o g r a m m i n gc o d ei sav e 巧i m p o r t a n tt e c l l l l i c a lt o r i 瑚【p l e m e n tt 1 1 es y s t e mo fd e t e c t i n gp r o 留舢i n gc o d es i m i l a r av e 巧 g o o dt e c h n i c a l o fs e g m e n t i n gw o r d sc 锄p r o v i d ef l a s t e r a n de x a c t e r m e t h o dt ot h es y s t e mo fd e t e c t i n gp r 0 掣籼i n gc o d es i m i l 跳i ti sv e 拶 i m p o r t a n te a e c tt od e t e c t i n gp r o 铲a 姗m g c o d es l m l l a r 1 i nm es y s t e mo ft h ed e t e c t i n gp r o g r a m m i n g c o d es i m i l 鸩t h e t e c h n i c a lo fs e g m e n t i n gw o r d sc a nu s es ow i d e l y f i r s u y ，w ec a nl o o kt h e p r o 窒期m m i n gc o d ea st h e t e x ts t r i n g ，t h e nu s eg r a m m a ra n a l y s l sm e t h o d t 0 c o n v 舐s u c ht e x ts t r i n gt ot h et o k e nw h a tc a l ld e s c 抽eb a s i ci n f i o m a t i o n a n dp r o p e r t i e so ft h ep r o 伊舢i n gc o d e s u c ht h i sp r o c e s sj u s tl s w o r d s e g m e n t i n ga n dc o n v e r t i n g n i sp a p e ri n t r o d u c e st h et e 6 h n o l o g yo fd e t e c t i n gp r o g r 猢i n g c o d e s i m i l 繇s u c ha sd e t e c t i n g s i m i l a rd e f i n i t i o n a 1 1 d d e t e c t i n g s i m i l a r t e c h n 0 1 0 9 ys o r t s t h e n“i n t r o d u c e sd e t e c t i n g s i m i l a rt e c h n o l o g y s d e v e l o p m e n ti no v e r s e a sa n di n t e m a l a tl a s t ，m ep a p e ri n t 】似l u c e sv e 巧 u s e 觚a r i t l u n e t i cf o rp r o g r 猢i n gc o d es e g m e n t i n ga n dc o n v e r t i n g t h e y a r e ：s e g i n e n t 堍w o r d s 撕恤1 e t i c ，c h a r a c t e r 嘶n gm a t c h l n ga r l t h r n e t l c e t c i np r o 铲撇i n gc o d es e g m e n t i n ga n dc o n v e r t i n gr e s e a r c h ，w bi m p l e m e n t ae x p e r i m e n ts y s t e m ，i t s c t i o n sc o n t a i nf o u rp a r t s ，f i r s tp a r to f 如n c t i o n i s p r o g r u n m i n g c o d ep r o c e s s i n ga n ds e g m e n t i n g ，p r o c e s s l n gj u s t 1 s r e m o v i n gu n u s e 如lc o n t e n t ，s u c ha sc o m m e n t s ，s p a c ea n ds oo n ；s e c o n d p a r to ff - u n c t i o ni sc r e a t i n gaw o r dd i c t i o n a 巧f o rp r o 酽a 衄m g c o n v e r t l n g t h i r dp 龇o f 如n “o ni su s i n gc h a r a c t e rs t r 堍m a t c g 撕m m e t i ct o c o n v e r tp r o g r a m m i n gc o d et ot h et o k e n f o n hp a r to f 如n c t i o n 研n to u t t h ec o n v e r t i n gr e s u l t sv i ag u io ft h es y s t e m a tl a s t ，w em u s tt e s t a n d a n a l y z e o u re x p e r i m e n ts y s t e mv i aar e a s o n a b l e 锄ds c i e n t i f i ce x p e r i m e n t a t i o n a 1 l e x p e r i m e n t a t i o nd a t ac o m e 仃o m s t u d e n t sh o m e w o r k t e s tr e s u l tt e nu s “ss y s t e mc a ns u p p o r tm u l t i p l ep r o 铲a j i 皿i n gl a n g u a g ec o n v e r t i n g ，a n d t 1 1 er e s u l ta sc h a r a c t e rs t r i n g 啪e ，i tc 锄b eu s e df o rd e t e c t i n gs i m i l a r a 打c h m e t i cb a s eo nc h a r a c t e r 蚰血gd e t e c t i l l g t h i se x p e r i m 铋tp r o v i d e s s 诎l et e s t i n g m f o m a t i o n a n ds u c hi n f o n i l a t i o ni sv 吲i m p o r t a n tf o r r e s e a r c h i n gd e t e c t i n gp r o g r 舢i n g c o d es i m i l a rs y s t e m k e yw o r d s ：p r o g r a m m i n gc o d ec o n v e n i n g ， s i m i l 虬w o r dl i s t ， c h a r a c t e rs t r i n ga r i t t m e t i c 内蒙古师范大学硕士学位论文 图表、公式及算法目录 图1 1 程序代码相似度计算逻辑模型图一5 图2 1 软件系统p 与q 之间的相似性8 图3 1 最大匹配法框图1 9 图3 2 串模式匹配示例2 3 图3 3g s t 算法伪代码2 8 图4 1 逆向最大匹配算法3 3 图4 2 分词词表3 6 图4 3 程序代码转换实验系统界面3 8 图4 4 转换形式4 0 图5 1 转换后代码相似度计算结果分布4 3 图5 2 源代码相似度度量值4 4 图5 3j p l a g 的p a s e r l o g 4 4 表5 1 程序分析转换准确率统计表4 2 表5 2 程序转换速度值对比4 5 公式2 1 7 公式3 1 2 1 公式3 2 21 公式3 3 2 1 公式3 4 2 1 公式3 5 21 公式3 6 2 2 公式3 7 2 6 公式3 8 2 6 公式3 9 2 6 公式3 1 0 2 9 公式3 1 1 2 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果，尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得内蒙古师范大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示感谢。 签名：磐墨缮聋旧期：枷9 年月刁日 、| 关于论文使用授权的说明 本学位论文作者完全了解内蒙古师范大学有关保留、使用学位论 文的规定：内蒙古师范大学有权保留并向国家有关部门或机构送交论 文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文 的内容相一致。 保密的学位论文在解密后也遵守此规定。 鲐磐谢锄张刳科 日期：小牌月歹7 日 第一章绪论 第一章绪论 1 1 引言 随着计算机相关专业的学生程序作业的抄袭现象越来越频繁，发现这些抄袭行 为，维护学风，就成为各位师教义不容辞的责任。当然，发现程序代码抄袭是一个非 常耗时而且辛苦的工作。假设对n 个程序进行判断，那么就需要对 胁( n 一1 ) 2 程序 进行对比。而且，学生们为了避免被发现，他们会修改所抄袭的程序，使抄袭后的程 序尽可能的不被发现。所以，为了快捷高效的发现程序代码作业的抄袭行为，一些机 构开始对程序代码相似度判别技术进行了系统的研究。 程序代码相似度判别技术的研究主要指的是模式匹配的问题，其中用到匹配算 法较多的环节是代码的分词转换。因此本文研究的主要方向就是程序代码的分词转换 技术。当然，要先了解程序代码分词转换技术，就需要知道为什么要进行程序代码的 相似度判别。最初，相似度识别问题的提出是出现在学校里，主要利用计算机来检测 学生的程序代码作业的抄袭现象，以减少教师劳动强度。然而，随着计算机技术的飞 速发展，这种程序代码抄袭的现象出现在了商业活动中，随之而来的是所采用的抄袭 手段也越来越复杂，因此对程序代码相似度判别的重要性也日渐突出，下面我们分析 一些常见的抄袭类型从而加深对相似度判别的理解，以便更好的研究程序代码分词转 换技术。 早在1 9 8 7 年f a i d h ia n dr o b i n s o n 提出了程序变换谱系图，列出了可能出现 的程序变换方法及级别划分。谱系图将程序变换方法( 在不影响结果的情况下) 分为 如下七个等级： l 0 是不做修改； l 1 是修改注释与空格； l 2 是修改标志符； l 3 是修改变量位置； l 4 是过程合并； l 5 是修改程序语句； l 6 是修改控制逻辑。 内蒙古师范大学硕士学位论文 可以肯定的说，这些变换是一个从简单到相对复杂的过程，但无论如何变换， 都是对程序的表面做的修改，不会对程序的属性和结构有本质的影响。因此在研究 程序代码分词转换的过程中，应该遵循这特点，在对其进行转换的时候，要保证 程序的本质属性不变，并最大限度的排除其他不相关因素的干扰，例如分词转换过 程中，删除多余的空格，注释，忽略不相关的标志符的转换等手段。这样将一个精 简且能够充分表现程序本质属性的转换结果呈现给相似度算法，从而进行相似度判 别。这里我们只专注于程序代码的分词转换技术。通过初步分析，可以确定在对程 序代码分词转换的过程中，要遵循下列原则： 1 清除源程序中对判别没有影响的内容，使程序尽量简洁。 2 不改变原程序的属性。( 例如，语法结构，逻辑控制) 3 程序转换后的形式不能比程序源代码还复杂。 1 2 国内外的研究现状 1 2 1 国外情况 国外对程序代码相似度判别的研究主要集中在程序代码的抄袭检测上。早在2 0 世纪7 0 年代，国外就有学者开始研究程序代码相似度判别技术和软件。 1 9 7 6 年，h a l s t e a d 乜1 首先提出了用属性计数的方法检测程序代码的抄袭问题， 1 9 7 7 年，o t t e n s t e i n 口1 使用h a l s t e a d 的这个方法设计了最早的自动程序抄袭检测系 统，这个系统是用于检测f o r t r a n 语言编写的源程序之间的抄袭的。 为了得出更准确的结果，人们在开发相似度判别系统中不断考虑到程序的属性、 程序的结构信息等等。这些系统随着时间的推移变得越来越复杂。目前，大部分程序 抄袭检测系统都使用了属性计数技术，结构度量技术，或者同时使用了属性计数技术 与结构度量技术。如f a i d h i 和r o b i n s o n 的抄袭检测系统，g r i e r h l 设计的a c c u s e 程序抄袭检测系统，使用了属性计数技术。如p l a g u e 嗍，s i m 旧，y a p 3 口3 等抄袭检测系 统无一例外地都使用了结构度量技术。p a r k e r 嘲和c 1 0 u g h 口3 等人分别对上述的各种程 序复制检测方法作了详细的介绍和评述。除了这两种度量技术外，还有人提出了用神 经网络来检测程序代码复制问题n 引。 1 2 2 国内情况 1 9 8 8 年，中国人民警官大学的张文典、任冬伟研制了一个p a s c a l 程序抄袭判定 2 第一章绪论 系统n ，能够识别p a s c a l 程序的相似度。将p a s c a l 语言结构分为四大类属性：控 制类、变量类、运算符类及标准过程类。该系统的统计模块接受p a s c a l 源程序，并 统计程序的各种属性，存入数据文件。比较模块，首先比较所有程序的四个总属性值， 如果两个程序的四个总属性值的差的绝对值均小于相应的总属性的标准偏差，就认为 这两个程序有相似可能，将其标上“可能相似 标记，并将其文件名输出。第二遍比 较有相似可能的程序的各个属性值，如果两个程序的相应属性之差的绝对值小于该属 性的标准偏差，则计算：h i t = h i t + d i ，其中h i t 为两个程序间相似属性的统计，d i 为 属性的权值( 由使用者根据问题而定) 。在比较完两个程序的所有属性，计算出最后 的h i t 值后，计算s i m i l a r = h i t m ，其中s i m i l a r 为两个程序的相似程度，m 为比较 的属性个数。当两个程序间的相似程度，即s i m i l a r 值大于某一限度值( 由使用者反 复修改反复比较确定) ，说明这两个程序是相似的。 此外，国内一些大学也开始注重对程序抄袭检测的研究，如南京师范大学的一篇 硕士论文电子作业管理和作业抄袭检测技术研究n 羽、广东工业大学的硕士论文程 序作业自动评测的研究与实现n 3 3 等文章中都提到了关于程序代码抄袭检测的自动 化。但是，这些研究多数仍处在起步阶段，有些还不深入。 另外，国内对程序代码相似度的研究主要集中在程序设计类课程的自动评分系统 的研究上n 4 。1 8 1 、( 如程序的智能考试系统等) 。 1 2 3 国内外研究现状比较分析 从国内外的研究现状可以发现，国内在对程序相似度判别的研究做的非常少， 大部分集中在对中文分词和语义的研究上。而国外已经有了很成熟的技术供我们借 鉴。因此说，本对该课题的研究具有一定的意义。尽管，我们只研究程序相似度判别 中的程序代码分析转换部分，该部分同样是非常重要的。因为只有经过科学合理的程 序代码转换，相似度判别算法才能根据转换后的标识串形式更加快速准确地进行相似 度的计算，从而得到具有可信价值的相似度判别结果。另一方面，本研究不仅可以用 在程序代码相似度判别系统中，还可以应用于智能搜索等其他领域中。这样看来，程 序代码转换技术的研究是一个具有长期性的可持续性的研究。 1 3 本研究的意义 在现存的程序代码相似度判别系统中，大部分是b s 结构的系统，例如：m 0 s s n9 l ， s i m 6 1 ，j p l a g 乜等。这些系统都采用各自独立的相似度算法对学生的程序作业进行相 3 内蒙古师范大学硕士学位论文 似度计算，而且每个系统都在做重复的工作就是对程序代码进行分词转换，在转 换过程中不能对多数的程序语言兼容。为了解决以上问题，将复杂问题量化且简单化， 本研究将程序相似度判别系统分成两个部分：第一部分，对程序代码进行分析并转换。 第二部分，对转换后的形式利用相似度算法进行比较并计算相似度。这里我们主要研 究的是第一部分程序代码的分析并转换。本研究主要利用词表解决系统对程序代 码语言的兼容性问题，即针对不同的程序语言代码，配置不同的转换词表，对所要转 换的程序代码进行文本搜索，之后与词表中的词条进行匹配，得到一个可以进行相似 度判别的字符串标识的结果。此外，针对不同的程序代码语言建立不同的词表，可以 实现对大部分程序代码语言进行转换。个精简且准确的程序代码转换技形式，不仅 能够充分表现出程序的特点，而且可将转换结果呈现给相似度算法。故本文的研究具 有一定的现实意义。 1 4 本研究的内容 本研究的主要工作就是对已有的程序代码文件，尽可能快速准确地将其转换成可 以用来进行相似度计算的字符串标识。在这过程中我们要用到分词、权重技术、字符 串匹配技术等。由于c 语言是国际上广泛流行的高级计算机程序设计语言，所以本课 题将主要以c 语言为研究对象。 该研究的主要内容如下： 1 预处理及分词 首先要对程序代码做预处理。所谓预处理是指去掉那些在程序中存在，但对相似 度判别无影响的信息。如程序中的注释语句、连续的空格、空行等，这样可以减小程 序代码的长度。接着对预处理后的程序进行分词，将程序中用到的关键字、标点符号、 操作符等区分出来。 2 转换 首先定义词表，将c 语言关键字、标点符号等元素以一定的规则定义为所对应 的标记。然后，将预处理及分词后的程序代码与机器词表中的词条进行一一对应，最 后把程序转换成一个字符串标识。转换结果可用于基于字符串相似度判别的算法中， 为下一步的深入研究，即对转换后的标记串进行相似度计算，从而得到相似程度的数 据，提供了可靠的测试信息。 以上介绍的研究内容主要包括程序代码的预处理及分词、标识转换两部分，这两 部分在相似度计算中所处的位置如图卜1 ： 4 第一章绪论 1 5 几个重要概念 图卜1 程序代码相似度计算逻辑模型图 程序代码转换( s o u r c ec o d ec o n v e r t ) ：在不改变计算机程序语言的物理结构和逻 辑结构的前提下，将程序代码转换成简单标识串，以提供方便、快速的对两段或多段 程序进行比较。 词表：从宏观上说，词表是全部主题词按字顺排列，并添加必要的标注项和显示 词间等同、等级或相关关系的参照项，是主体结构。从微观说，词表是由词条目按字 顺排列构成的有机集合( 程序代码中的词表指程序语言中由关键字，预定义标识符等 构成的集合) 。 词的权重计算：权重是指一个词在程序中出现的频率。计算词的权重可知该词在 程序中与该程序主体的关联性。词的权重计算主要应用于分词技术中。 系统评价；所谓系统评价就是完成一个系统的开发时，要利用一些手段和方法对 系统进行可行性评估。最后利用些模型把测试结果清晰的反应出来。系统评价是用 科学的方法来评价所研究系统的可行性以及缺点。 1 6 本文的组织结构 本文共分为六章，各章内容如下： 第一章为绪论部分，首先介绍了本研究的研究背景，接着详细讲述了国内外的研 究现状，最后介绍了本研究所涉及的主要内容、研究意义及相关的概念。 第二章首先介绍了程序代码相似度的定义，程序代码相似度的分类，并概述了用 内蒙古师范大学硕士学位论文 于程序代码相似度的相关技术以及国外的一些程序抄袭检测系统。 第三章介绍了本研究要用到相关算法和编程技术。其中，分词转换技术中包含了 分词算法、词的权重计算和基于字符串相似度判别的算法。 第四章介绍了本研究中的程序转换实验系统，并详细的介绍了实验系统中的程序 预处理及分词模块和转换模块。 第五章使用学生的程序代码作业对实验系统进行了测试，并对本实验系统的可行 性、合理性、有效性进行了分析，最后与j p l a g n 鲫系统进行了对比，来评价实验系统 的性能。 第六章对本研究的工作进行了总结，指出了实验系统的不足，并提出了今后进一 步的研究内容及方向。 6 第二章程序代码相似度判别技术概述 第二章程序代码相似度判别技术概述 程序代码相似度判别系统功能模块可由程序代码分词转换和相似度判别两部分 组成。本章主要介绍了程序代码相似度的相关知识、相关技术以及现有的相似度判别 系统中对程序代码相似度判别技术的应用情况。 2 。1 相似度的定义与分类 2 1 1 相似度的定义 相似度( s i m i l a r i t y ) ：利用一定的检测方法度量两个对象间的相似程度。主要包 括文本相似度和程序代码相似度，通常用一个数值( 0 0 一1 o ) 或百分比值( 0 1 0 0 ) 来表示。用其来标识两个文本或程序间的相似程度，进而检测出文本的相似性或程序 的相似性。 程序代码的相似度：与软件系统的相似度定义相同，y a m a m o t ot ，m a t s u s k t am ， k 锄i y at 和i n o u ek 硷q 给出了两个软件系统相似度的定义。对于两个软件p 和q ，p 由元素a ，岛，组成，用集合表示为： a ，见， ，同样，q 由元素口。，9 2 ，巩 组成，用集合表示为 鳜，g ：，吼 。这里的元素a ，p ：，和g 。，g ：一，吼可以是软件 p 和q 中的文件或代码行。 假设我们能够求出a 与g ，( 1 f 朋，1 行) 之间的匹配，所有匹配( a ，g ，) 的集 合用玛表示，这里尽量p q ，与咫相关的p 和q 的相似性s 定义如下： 卵加逝坐端地劂 ， 如图2 1 所示，这个定义表明，尸和q 之间的相似性是一个比值，这个比值是由 匙中的元素个数除以p 和q 中元素个数的总和得到的。如果匙较小，则s 将减小， 如果b = ，则s = 0 。此外，当p 和q 完全相同时，v f ( 易，g ，) r s ，s = 1 。 7 内蒙古师范大学硕士学位论文 2 1 。2 相似度的分类 图2 一l 软件系统p 与q 之间的相似性 相似度判别技术分为两大类，文本相似度技术和程序代码相似度技术。文本相似 度判别技术主要应用在文本挖掘、文本分类、文本复制检测、信息检索等方面，在这 里不做具体介绍。程序代码相似度判别技术主要应用在程序代码的相似度判别中，主 要用来比较程序代码段之间的相似程度。 程序代码相似度判别技术主要基于计算程序代码的组成元素信息或者计算这些 组成元素的结构信息，通过计算这些信息来比较程序代码之间的相似程度。基于程序 代码相似度判别方法的实现可以分为以下三类： 1 、属性技术法( a t t r i b u t ec o u n t i n g ) 较早实现的基于计算程序的组成元素的程序相似度判别方法是h a l s t e a d 1 3 提出 的度量方法。该方法用词汇量、长度和容量来标志一段程序。对一段程序，首先考虑 它的如下四个基本属性： ，n 1 = 操作符的种类数目 n 2 = 操作数的种类数目 n l = 所有操作符总数目 n 2 = 所有操作数总数目 基于以上四个基本属性，定义： 词汇量 n = n 1 + n 2 8 第二章程序代码相似度判别技术概述 长度n = n 1 + n 2 根据词汇量和执行长度再计算出该段程序的“容量 ：v = n1 0 9 ：( n ) 。最后将以上 信息用h a l s t e a d 特征向量表征出来：h ( n ，n ，v ) 。在一组程序中，每一个程序都用这 样的特征向量表示出来，通过测试这些特征向量之间的“距离来得到程序之间的相 似性。计算特征向量之间的距离的方法有多种，如e u c l i d i a n 方法，得到的距离越小 说明程序之间相似的可能性越大。以上通过提取程序中的某些属性，来计算程序之间 的相似性的方法称为属性计数法。 由于某些元素的数量相同并不能充分表达两个程序之间的相似性，后来的应用软 件在此基础上又增加了一些属性，如：g r i e r h l 设计的a c c u s e ，除了h a l s t e a d 2 3 的四 个属性外还增加了代码行数、变量声明和使用数以及在程序中使用的控制语句的数量 等2 0 个属性参数。该系统和同样采用属性计数法的f a i d h i r o b i n s o n u l 方法已被 v e r c o 和w is e 测试瞳2 1 ，证明属性计数法对于两个几乎是拷贝的程序检测效果较好。一 旦在程序中加入了一些代码或者用同样的结构替代一部分代码段，采用属性计数法的 检测系统计算的结果不理想。 2 、结构度量法( s t r u c t u r em e t r i c s ) 另外一种类型的相似度判别系统是分析程序结构的结构度量法，该方法主要通过 下列两个过程来得到相似度的值：一是基于程序的编程语言对程序进行的语法分析， 然后生成一个标记串( t o k e n ) 序列。将每一个程序都转换为一个字符串序列。二是 根据某种匹配算法比较这些标记串，得到相似的标记序列，然后再根据匹配结果计算 相似度的值。这个过程有以下难点：一个是如何更精确地用标识串表示程序的结构信 息；另一个就是找到一个有效、快速的字符串匹配算法。使找到的匹配结果便于计算； 另外就是找出有效度量相似度的方法。结构度量法考虑了程序的结构特性，因此，对 于某些“结构级 的相似度判别效果较好。 还有一类自动相似度判别系统依然是属性计数度量方法，但是这些系统中加进 了程序结构的描述。一个典型的例子就是d o n a l d o n ，l a n c a s t e r 和s p o s a t o 口3 1 的系统， 该系统中使用了八个属性同时产生一个描述程序代码的字符串。在这个字符串中的每 个字母代表单个或多个程序结构中邻接的事件，如变量声明、任务声明及过程调用等。 如果字符串的描述精确匹配或者度量结果很相近，那么，这对程序被认为抄袭并在可 疑的代码段上加上标志。这些系统中由于比较了程序的结构，体现了结构度量法的特 点。因此，他们的系统是两种技术的结合。 9 内蒙古师范大学硕士学位论文 3 、其它方法 除了使用属性计数技术和结构度量技术外，有的系统使用了其它方法，如基于 x m l 模型的方法和基于聚类的方法。 基于x m l 模型的方法：该方法首先将源程序描述成x m l 文档，然后将删l 文档 转换成树结构，然后再将树结构转换成矩阵，最后对两个源程序经过转换得到的矩阵 进行比较得到相似度结果。该技术已经成功应用在相似度判别系统x p d e c 瞳4 1 中，由于 在将源程序描述成糊l 文档时只对程序的三个主要部分：头文件、全局变量以及函数 进行描述，因此这种方法仅适用于面向过程的程序设计编写的程序代码。 还有一种方法是一种聚类方法( c l u s t e r i n ga p p r o a c h ) ，该方法首先将源程序 用一个描述这个程序的关键字( k e y w o r d s ) 集合来描述，然后使用一种相似度量方法 ( s i m i l a r i t ym e a s u r e ) 来对每一对描述进行评测，然后将大于或等于某个特定的 ( c u t o f fc r i t e r i o nv a l u e ) 程序对进行进一步计算，采用的方法是w 腮j o r c l u s t 算法，该算法是基于图聚类( g r a p h c l u s t e r i n g ) 的思想。目前，这一方法也成功应 用在相似度判别系统p d e t e c t 口5 3 中。 2 2 常见的相似度判别系统 国外用于程序代码相似度判别系统有很多，现以时间为序将国外的一些相似度判 别系统及其所用到的设计列举如下： 2 2 1a c c u s e 1 9 8 1 年a c c u s e 系统由u s a f 学院的s 锄g r i e r 4 3 开发，采用七个参数来分析两个 程序的相似度( 设计者认为考察的参数越多，两个程序的区别越大) ，通过相似度分 析值使用者可以对两个程序做进一步的判断。七个参数为： 、唯一的操作符数 、唯一的操作数数 、总的操作符数 、总的操作数数 、代码行数 、已经定义了的变量数 1 0 第二章程序代码相似度判别技术概述 、总的控制语句数。 属性相似度的计算涉及增量的计算，公式 in c r e m e n t = ，i m p o r t a n c e v a lu e ( p c o u n t a p c o u n t b ) 其中p c o u n t a 是第一个程序的属性的个数，p c o u n t b 是第二个程序的属性的个数。 如果p c o u n t a - p c o u n t b 小于或等于根据该参数确定的“w i n d o w 值( 窗口大小，参数 不同，取值不同，由使用者确定) ，接下来可以进行相似度计算。i m p o r t a n c ev a l u e 是该属性的重要度值，即权值( 由使用者根据具体问题而定) ，增量得到后，可以由 此计算相似度值( 公式未公布) 。a c e u s e 的输出为五个表： 、需要统计的2 0 个属性的名称和统计值； 、与计算相似度有关的7 个属性名称和统计值； 、相似度值列表； 、有同样相似度值的程序对的频率分布图； 、所有相似度值大于或等于2 8 的程序对名称。 属性计数的方法抛弃了太多的程序结构信息，导致错误率太高。因此人们开始了 由属性计数向控制流( 结构度量) 技术或两者结合技术的转变； 2 2 2pfa g u e 1 9 8 8 年p l a g u e 嗍系统，它使用程序的结构度量的检测方法，、且对更详细的结构信 息进行比较。p 1 a g u e 工作分为三个阶段：第一个阶段：创建每一个文件的标识符序 列和结构度量列表构成程序的结构特征。结构度量包括程序中所使用的结构，如：循 环选择结构及语句块。结构特征采用了归纳的规则表达式的形式。第二阶段：比较 结构特征( 0 ( n 2 ) 次) ，使用语言细节距离函数的结合得到最邻近的程序对。预期大多 数程序都是不相邻的，如果有程序对是相邻的，将其留到下一个阶段进行处理。第三 阶段，使用最长公共子序列算法的变体对标识符序列进行比较。 p l a g u e 的缺陷包括： 、p l a g u e 方法不适合其他语言( 仅可以用于p a s c a l ，p r 0 1 0 9 ，b o u r n es h e l l a n d l l a m a 程序) ，且耗费时间太多。 、p 1 a g u e 的结果是两列按h 和h t 索引排序的列表，需要作进一步的解释，不 内蒙古师范大学硕士学位论文 能做到一目了然。p 1 a g u e 手册对如何解释提供了指南。 、p l a g u e 执行效率不高，又依赖于太多的u n i x 工具，因此在可移植性方面存 在问题。 2 2 3y a p 系列 y a p l 、y a p 2 和y a p 3 - y a p ( y e ta n o t h e rp 1 a g u e ) 系列工具是在p 1 a g u e 的基础上开发的。m i c h a e lw i s e 在1 9 9 2 年开发y a p 的第一个版本y a p l 啪3 ，之后推 出改进版y a p 2 啪1 ，最后在1 9 9 6 年推出最终版y a p 3 嘲。y a p l 和y a p 2 主要用于程序复 制检测，而y a p 3 阳1 即可以用于程序也可以用于文本文档检测。所有的y a p 系统以同样 的方式工作，操作分为两个阶段：第一阶段由每一源程序生成标识符文件；第二阶段 比较标识符文件对。文件中的标识符具有重要的意义，代表了程序设计语言的语言结 构或库函数，忽略常量和用户定义的标识符。一个小的程序作业通常可能有 1 0 0 5 0 0 个代码，而一个大的程序可能有4 0 0 7 0 0 个代码。尽管对每一种语言是 分别进行标识符化的，但它们的执行步骤相同： 、程序作业预处理： 删除注释和输出语句 删除用于自定义标识符中的非法字母 将大写字母转换为小写字母 。 形成原始标识符列表这步工作是由u n i x 工具t r 和s e d 来做的。 、转变某些同义词为常用形式。例如：在c - y a p 中，将s t r n c m p 映射为s t r c m p 。 这样的操作类似于将词映射到它们的上位词中。 、找出函数过程语句块。在l i s p - y a p 中这一步无需太多的精力，而在c j a p 中结合使用了u n i x 工具c t a g s 和a w k 。 、按调用顺序展开函数块。重复的函数块仅被展开一次，随后对该函数的调用 用一个有序的标识符替代，这样可以禁止标识符个数的无限膨胀。 、根据给定的词汇表，从程序作业中找出要标识符化的部分。 1 2 第二章程序代码相似度判别技术概述 2 2 4m o s s 1 9 9 4 年m o s s 口8 1 系统( m e a s u r eo f s o f t w a r es i m i l a r i t y ) 是由a 1 e xa i k e n 于1 9 9 4 年在b e r k e l e y 开发，用来识别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 n 鄙能够给出匹配程序代码相似度识别的代码长度的百分比值并将最长匹配区域 显示出来。 2 2 5j pia g j p l a g n 刚系统是由德国卡尔斯鲁厄( k a r l s r u 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 n 用j a v a 语言编写的，在互联网上提供程序抄袭检测服务的系统。使 用的比较算法与y a p 3 口3 相同，也是采用g r e e d ys t r i n gt i l i n g 算法，但却优化了 y a p 3 的时间复杂度。 该系统也是用来度量一个程序集合中代码文件的相似性的，当前的版本支持 j a v a ，c ，c + + ，s c h e m e 编写的源程序和自然语言文本。 j p l a g 通过比较文本字节和语法程序结构，在识别程序相似度时功能很强大。 它是按如下两个步骤计算两个程序之间的相似度的： 、由源程序生成标记字符串( t o k e ns t r i n g ) ； 、比较每对由程序所生成的标记字符串，以此来度量每一对程序之间的相似 度。 在第二个步骤里，每一个标记字符串又被分成更小的称为“t i l e 的子串，最后 将串流的比率转换成两个程序之间相似度的值。 j p l a g 的比较过程如下：当读入待比较的程序集后，先将每一个程序转换成标记 字符串。在使用比较算法之前，这些标记串中的每个标记都被转换成单一的字符，然 后使用g s t ( g r e e d ys t r i n gt i l i n g ) 算法作比较。当程序比较完成后，系统提供给 用户一个索引页，其中包括程序的详细信息，如程序所在的目录名、源程序所使用的 语言、文件扩展名、比较的文件数量以及相似性较高的程序等等。当用户选择其中的 一对相似性较高的程序后，系统会高亮显示出该对程序中相似的源代码行。 内蒙古师范大学硕士学位论文 2 2 6b a n dit 1 9 9 5 年b a n d i t 嘲1 是由曼彻斯特的v i c t o r i a 大学的m a l c o l ms h u t e ，k o s h o r m i s t r y ，h a y d n r o b i n s o n 和a d r i a nw e s t 联合开发的。它是计算机科学程序设计实验 的一部分。b a n d i t 收集学生的作业，将当前学生交的作业与先前学生交的作业相比 较找出抄袭者。程序代码( 至少有几十或几百行) 被分解成词汇标识符串，独立的程 序结构，注释和变量名。通过比较标识符串和查找相似标识符序列获取相似度值。相 似标识符序列的查找是使用d o t p l o t 乜钔方法实现的，该方法中一个程序的标识符串用 x 轴表示，另一个用y 轴表示。交叉处是两个标识符匹配处。检测器查找共有的标识 符序列的不问断的对角线。该方法易识别并能有效处理如由于插入、删除而造成的对 角线的中断和改变标识符的重新安排等操作。该工具在实现时，由于语言不同仅仅是 处理的标识符输入不同，其余的分析操作几近相同。b a n d i t 产生的结果是源程序中 匹配标识符序列的长度和位置。匹配序列越长，越值得使用者深思。最值得怀疑的情 况是，从顶部开始，快速下滑到一个较复杂区，然后继续下滑。b a n d i t 绘制出一个 程序和相似度值图，能够用来快速地识别潜在的相似程序。b a n d i t 也提供了图形界 面，将程序代码显示在屏幕上，可以通过比较快速识别。设计者声称唯一能够愚弄 b a n d i t 的方式是重新安排程序中所有的标识符以致没有值得怀疑的结构线索保留， 要做到这样需要对程序代码充分了解，而这也是程序设计作业要求学生做到。 2 2 7d u p d u p 【3 0 】系统是由b r e n d ab a k