程序代码相似度度量算法研究

1、第 29 卷 第 17 期计算机工程与设计Computer Engineering and Design2008 年 9 月Sept. 2008Vol . 2 9No . 1 7程序代码相似度度量算法研究邓爱萍(湖南人文科技学院 计算机科学技术系，湖南 娄底 417000)摘 要：代码剽窃是程序设计课程中经常出现的一种作弊行为，检测剽窃的源代码、验证学生程序作业的原创性在教学中 很重要。程序代码的相似度度量是剽窃检测的关键技术。通过对现有程序代码相似度度量技术进行研究后，基于 Karp-Rabin 和最长公共子串算法思想，提出了一种改进的源代码相似度度量算法，即串的散列值匹配算法。关键词：源代

2、码; 相似度度量; 剽窃检测; 串匹配算法; 散列值匹配文章编号：1000-7024 (2008) 17-4636-04中图法分类号：TP311.52 文献标识码：AStudy on similarity measurement of program codeDENG Ai-ping(Department of Computer Science, Hunan Institute of Humanitles, Science and Technology, Loudi 417000, China)Abstract：Code plagiarism is one kind of cheat beha

3、vior, which appears frequently in the programming curriculum. Detection of source code plagiarism is important to verify the originality of students project works. The code similarity measurement is the key technology in the plagiarizing detection. The similarity measurement of program code is studi

4、ed first, then the strings hash value matching arithmeticwhich based on Karp-Rabin and longest common substring algorithm is provided, and the results show the improved arithmetic is effective.Key words：source code; similarity measure; plagiarism detection; string matching arithmetic; hash value mat

5、ching1996 年指出，对于仅仅使用属性计数法的检测算法，增加向量维数并不能改善错误率。改进属性计数法的措施就是加入程 序的结构信息，结合结构度量来检测剽窃。McCabe 提出的圈 复杂度方法是一种典型的结构度量法。它通过计算执行路径 的数量来衡量一个程序中的控制流。圈复杂度只给出了程序 的一个结构特征即控制流，往往需要与其它特征结合使用，因 此常作为属性计数法中的一个度量指标。其它的结构度量法 还有分析控制结构、计算代码嵌套深度、分析数据依赖关系等。 在实际应用中，很多代码剽窃检测系统将两种度量方法相结 合。Donaldson et al.开发的 ACCUSE 系统结合属性计数法和结 构

6、度量法来实现对 Fortran 程序代码的剽窃检测。最近提出的 系统大都是通过对表达源程序结构的字符串进行比较来达到 剽窃检测的目的，如：Plague, JPlag, SIM, MOSS,YAP 系列等。另外，Faith 和 Robinson 提出使用 24 个分量来评估代码的 相似程度，前 10 个是主要针对初学者的低级的剽窃，其它的 用于有经验的剽窃；Jankowitz 方法通过对代码中的主程序和 方法进行语法分析，得到静态执行树，用于对代码的分析等。 综上所述，应用于程序代码剽窃检测系统中的代码相似度度量方法可分成两类：属性计数技术和结构度量技术。1.1 属性计数技术在剽窃检测算法的发展

7、过程中，大多数工作集中在 Hal- stead 的软件科学理论。这些基于软件科学度量的算法是从程 序中提取出数个软件度量特征，计算每一个程序的 n 个不同0引言程序代码相似度度量技术主要应用在代码的剽窃检测上。判断一个程序是否是从另一个程序复制而来，实质上是 对这两个程序的相似度进行度量，根据度量的结果给出一个 相似度的数值表示，再由这个数值判断这两个程序之间是否 存在抄袭。另外，还可以根据度量值判断学生所写程序代码 的标准化程度，从而辅助实现作业批改的自动化或试卷评阅 的自动化。程序代码相似度度量算法研究的主要内容是如何 更精确地用字符串表示程序的结构，并选择有效、快速的字 符串匹配算法，以

8、减少相似度度量的时间复杂度，提高相似 度度量的准确性。1程序代码相似度度量技术早在 20 世纪 70 年代初，就有学者研究阻止大规模拷贝程 序的技术和软件，出现了一批比较典型的程序源代码剽窃检 测系统1-4。Halstead 提出的软件科学度量方法是最早和最典型 的属性计数法。Halstead 度量方法以程序中出现的操作符和操 作数为计数对象，以它们的出现次数作为计数目标来计算程 序容量和工作量。Rottenstone 在 1976 年首次将 Halstead 的软 件科学度量方法投入应用，实现了第一个针对于 Fortran 代码 的剽窃检测系统。但是，单纯的属性计数法抛弃了太多的程 序结构信

9、息，导致检测结果的错误率太高。Verso 和 Wise 在收稿日期：2007-09-16E-mail：ld_dengaiping作者简介：邓爱萍 (1977)，女，湖南涟源人，硕士，讲师，研究方向为计算机辅助教育技术。：；：；：、，,<的软件度量指标，以便于将程序映射到一个 n 维的笛卡尔空间，然后利用向量空间模型来度量程序代码相似性。1.1.1 常用的属性计数法度量指标在属性计数技术中，有以下 6 个常用的代码相似度度量 指标，被描述为一个“6 元组”向量。(1)容量：容量被认为是任何算法实现的大小的反映，常使 用 Halstead 的软件科学度量方法来量化。该方法首先对程序 代码中的

10、词元进行词频统计 1=用到的操作符的种类数 2= 用到的操作数的种类数 1= 出现的所有操作符总数 2= 出 现的所有操作数总数。然后用如下公式计算程序容量部结构进行分析比较来判断两段程序代码的相似性。结构度量技术中使用的相似度度量方法主要有：点阵图法、Levensh- tein 距离、最长公共子序列法、最长公共子串法。1.2.1 点阵图(dotplot) 法点阵图 5 是一种视觉展示两个代码块 (或任意文本) 之间 字符串匹配模式的技术。重要的是，点阵图不是一种特定的 语言，因此它不要求了解被比较的代码的语法和语义。这一 点使得点阵图法具有很大的灵活性。点阵图的主要优势是它依赖于人的视觉系统

11、去检测相似 模式。然而，简单的用人眼去揭露剽窃，如何量化每个比较结 果的问题成为了点阵图的主要缺点。它意味着解释一个人复 制了多少别人的代码将不能由值来表示。点阵图法的操作过 程是：首先，选择两个程序并将其处理为标记序列；然后连接 这两个序列；最后对生成的序列进行自我比较。例如，有如下两个序列：(1)= 1+ 2程序长度log2式中汇量。= 1+ 2 程序所用的词(2) 控制流：控制流常用 McCabe 提出的圈复杂度 (cyclo-matic complexity)来度量。圈复杂度是一种为程序逻辑复杂性 提供定量测度的软件度量方法，用于计算程序的基本的独立 路径数目。该方法首先将程序代码转换

12、为一个带有惟一入口 和出口结点的控制流图。这种方法具有语言依赖性，这意味 着在创建控制流图前，必须理解编写代码的语言的语法和语 义。在程序控制流程图中，节点表示程序中一个顺序代码单 元，边表示程序中产生的分枝。一个有 条边和 个节点的控 制流图 G，其圈复杂度定义为序列 1：test this序列 2：we must test this now将两个序列连接成为一个：test this we must test this now，其匹配点阵图如图 1 所示。图中所有点所在的对角斜线(包括 主对角线) 表示结构上的一个相似。从图中可看出，序列 2 中 的子序列”test this”在序列 1 中

13、被找到。这说明了序列 1 有被 剽窃了的可能性。同时，这个例子表明，用点阵图方法对程序 代码进行相似度度量，其结果不受改变代码块顺序的影响，同 时也不受对代码段进行简单分离操作的影响。test this we must test this now testthis we musttest(2)=其中 = 控制流图中的模块数。+2(3) 结构：这个度量标准考虑到使用一些指标去阐明模块之间的耦合程度。(4)数据依赖：用与度量程序控制流相似的方法，数据依赖 也能被度量。在流程图中，用结点来阐明谓词子句和变量定 义。Bieman 和 Debnath 建议用广义程序图(generalised progr

14、am graph，GPG)的形式来表示。(5)嵌套深度：这是一个简单的度量标准，通过赋给每个代 码行一个深度值，返回一个程序的平均嵌套深度。平均值是 由这些深度值的总和除以程序中语句的个数计算而来。(6) 控制结构：给出现在程序中的每一种类型的控制结构 赋予一个权值，例如给一个 if.then 结构赋予权值 3，所有权值 的总和常用来表示一个程序的复杂度。1.1.2 相似度计算使用属性计数法来进行源代码的剽窃检测时，首先对能 表示程序特性的度量指标进行统计，生成其特征向量。其后 可用向量空间模型的夹角余弦公式来度量向量之间的相似性。thisnow图 1 点阵图示例1.2.2 Levenshte

15、in 距离Levenshtein 距 离 又 称 为 编 辑 距 离，是 俄 国 的 科 学 家 Vladimir Levenshtein 在 1965 年提出的，常用于字符串相似度 比较。这个算法的含义是计算两个字符串之间的距离有多远。 即从源字符串变化到目标字符串最少需要进行多少次包括添 加、修改、删除在内的操作。两个字符串的编辑距离越大，则 相似度越小。Levenshtein 距离可用如下算法求得：设*为有限字符串的集合，对于任意串 ,* ，设 =令 P1 表示候选程序，其词频向量为 P1( 1, 2, 3,n)，P2 表i i(1<=，创建 和 的( +1)× (+1)

16、 阶匹配关系阵=)1 2D(0. ,0.1 2示待检测程序，其词频向量为 P2( 1, 2, 3,n)，其中i<=N) 表示各特征值的词频，则程序段 P1 和 P2 之间的相似度Sim(P1 ，P2)用向量空间模型的余弦公式来度量，公式为1,若 =若 <>0,Temp, = 0= 0( = 1, = 1)若若,×D , = ,= 1(3)1,=min D1 ,D1 ,D11 +, 0< <= ; 0 <=212则 S 和 T 的 Levenshtein 距离 LevD(S,T)为 D ( , )的值，其相似度 sim(S,T)22= 1= 11.2

17、 结构度量技术采用结构度量技术的剽窃检测系统中，通过对程序的内2*,sim(S,T) = 1(4)+,，式中：| |,| | 字符串 , 的长度。编辑距离通常被用于句子的快速模糊匹配领域，但是其 规定的编辑操作不够灵活，也没有考虑语句的同义替换。1.2.3 LCS(longest common subsequence) 算法LCS 算法即求两个字符串的最长公共子序列算法。最长 公共子序列是将两个给定字符串分别删去零个或多个字符后 得到的最长的相同字符序列。子序列与子串的区别在于子序 列不必是原字符串中的连续字符。例如，字符串 abcabcabb 与 bcacacbb 的最长公共子序列为 bca

18、cabb。显然，采用 LCS 算法 检测不出调整了代码块顺序的剽窃。Plague 系统就是基于最长公共子序列算法对源代码进行 相似性比较，从而对程序进行抄袭识别。1.2.4 最长公共子串最长公共子串问题指的是求出给定的一组字符串的长度 最大的共有的子字符串。若将字符串看成由若干个子串组成， 那么两个字符串中相同的子串为它们的公共子串，因而，它们 的相似度可用所有公共子串在整个串中所占的百分比表示。YAP3，一个对学生提交的程序和其它文本作业进行剽窃 检测的系统，以及 JPlag 系统都采用了RKR-GST6(running-karp- rabin greedy-string-tiling)一种

19、贪婪式字符串匹配算法来寻 找两段程序代码的最大公共子串。并由此计算出两段程序代 码 A、B 的相似度 sim(A,B)串，其中每相邻的两个子串之间有 1个字符是完全重叠的。例：有程序代码 P1：public P1( int i) / constructor iVar = i ; 对代码规格化，生成 token 串：public(int)=;。取 值为 6，生成子串：public, ublic(, blic(i, lic(in, ic(int, c(int), (int) , int)=, nt)=; , t)=;。该方法产生的子串的数量为 token 串长度- (1) 。的取值是一个噪声阈值，

20、算法不能检测出长度小于 的匹配。在系统中可提出一个保证阈值 ，只有长度大于或等于 的公共子串，才被当成是一个匹配，即 值是用户想检测的 复制信息的粒度。2.3 子串散列把所有长度为 的子串映射成比其本身短得多的散列值， hash 函数必须能尽量防止不同的字符串产生相同的指纹。基 于 Karp-Rabin 算法思想7，采用如下 hash 函数Hash (+ 1)= mod (21asc + 2 2asc +1+20asc(6)+1+ 1,)式中：asc 字符 的编码一个足够大的素数。该式很容易从第 个子串的散列值快速地计算出第 +1个子串的散列值Hash (+ ) =mod(2(Hash (+

21、1)- 21asc )+ asc(7)+1 +2+1sim(A,B) = 2× )+ ,(5)+2.4 相似度度量进行相似度度量时，一个散列的子串子集被选作整个 to- ken 串的特征值，即指纹。指纹可用不同的方法选择，一个经 常使用的方法是对于固定的尺寸 使用 0 mod 方法8，也就是 说，如果一个子串的散列值与 的模等于 0，那么这个子串被选 择作为一个指纹，并加入 token 串的指纹集。两段代码的相似度度量公式如下=, ,式中：| |,| | 代码 , 的字符长度；match () ,在 A 中起始位置为 ，在 B 中起始位置为 ，长度为 length 的公共子串；公共子

22、串集合。由于算法循环求取了两个标记串中未被匹配部分的所有长度大于指定最小匹配长度的最大公共子串，所以该算法比 之 LCS 算法的最大优点是能检测出调整了代码块顺度的剽 窃。RKR-GST 算法的最差运行时间复杂度为 O(n3)。(8)| 代码 , = 2+式中：| |,| | 代码 , 中选择的指纹数 |中相同的指纹数。2串的散列值匹配算法从现有源代码剽窃检测系统的应用实践来看，程序代码相似度度量技术各有优缺点，属性计数技术由于抛弃了太多程序 结构信息，其性能较低，而结构度量技术主要采用字符串匹配 算法来计算源代码标准化产生的标记(token)串的相似度，其时 间复杂度较高。本节基于 Karp

23、-Rabin 随机串匹配算法思想和最 长公共子串算法，提出一种改进的字符串相似度度量方法。2.1 算法基本思想由于最长公共子串算法需要一个一个字符地进行比较， 所以算法的运行时间复杂度较高，若将字符串分割成若干个 长度为 的相互重叠的子串，以此作为比较的最小单位，并用 Hash 函数将这些子串映射成为一个 hash 值，那么那些相同的 子串将具有相同的 hash 值，而算法也从字符串的匹配转化为 对整数的比较，从而达到降低复杂度的目的。2.2 代码分割进行代码分割，将程序转化而成的标记串分割为相互重 叠的子串，即把标记串分解成若干个长度为 K 的连续子字符对于长度为 的 token 串 A 和

24、长度为 的 token 串 B，分割成的子串个数分别为+1和+1，若选取所有的子串作为指纹，则该算法对指纹的散列值进行比较的最差时间复杂度为+1+1 ，约为。相似度度量算法如下：/输入：二维数组 hashArray, hashArrayi 为第 i 个 token 串 的散列值数组/其中第一个元素为散列值个数，其它元素为散列值/输出：相似度 similarity iLen=hasharrayi0;1111112222223 jLen=hasharrayj0;simNumber=0; / 两个 token 串的相同散列值个数for (int r = 1; r <=iLen; r+) noS

25、imNumber=0; /当前没有匹配的数的个数if (jLen=hasharrayj0)tp=hasharrayj;else tp=temp;for (int w = 1; w <= jLen; w+) if (hasharrayir = tpw) simNumber+;r+;if (r>iLen) break;else temp+noSimNumber=tpw; /for wjLen= noSimNumber; /for rsimilarity = 2 * simNumber / (hasharrayi0 + hasharrayj0);return similarity;表 1

26、 运行时间表/ms序代码的相似性，现在的程序复制检测都需要综合属性计数和结构度量两方面的信息来度量代码的相似性。由于性计数 技术的度量精确度不高以及现有结构度量技术时间复杂度较 高，本文提出一种改进的算法即串的散列值匹配算法来度量 程序代码的相似性，并对算法进行了验证。本算法具有较好 的精度和效率，若利用该算法开发出相应的教学软件，对于程 序设计课程的教学和考试具有十分重要的意义。3实验分析与比较参考文献:1Clough P. Plagiarism in natural and programming languages: an overview of current tools and te

27、chnologiesR. Internal Report CS-00-05, University of Sheffield, 2000.Gitchell D, Tran N. Sim: A utility for detecting similarity in com- puter programs C. New Orleans, Louisiana, USA: The 30th SIGCSE Technical Symposium on Computer Science Educa- tion,1999:266-270Boywer Kevin W, Hall Lawrence O. Exp

28、erience using 'MOSS' to detect cheating on programming assignmentsC. San Juan, Puerto Rico: 29th ASEE/IEEE Frontiers in Education Confe- rence,1999:18-22.陈金宏, 刘东升. 程序代码相似度自动度量技术研究研究综述J.内蒙古师范大学学报,2006,35(4):457-461.Andrew Granville.Detecting plagiarism in Java codeD. Super- visor:Yorick Wilks

29、,2002.Prechelt L,Malpohl G,Philippsen M.Finding plagiarisms among a set of programs with JPlagJ. Journal of Universal Computer Science,2002,8(11):1016-1038.李旭. 基于匹配方法的文档复制检测系统研究 D. 秦皇岛: 燕山大学,2005.Alex Aiken, Saul Schleimer, Daniel S Wilkerson. Winnowing: Local algorithms for document fingerprintingC. Proceedings of the ACM SIGMOD International Conference on Manage- ment, 2003.为了对串的散列值匹配算法的运行效率进行验证，本文设计了一个实验，实验对 10 个学生用 C 语言编写的折半查找 程序进行两两相似度度量，记录所需运行时间。算法采用 Java 语言实现，在 Pentium 4 CPU 2.4GHz，512MB 内存，Windows XP 环境下进行。由于将