全上克，杨新锋

0 引言

随着信息技术的高速发展，信息技术与教育教学的结合已经越来越紧密，针对各类程序设计课程，就有统一的程序语言支撑平台来帮助教学，程序语言支撑平台为学生提供了一个综台统一在线练习平台，帮助学生提供编程能力，同时也帮助教师布置程序设计课程的作业和考试，这种利用信息技术实现教学自动化大大提高了教师批改作业和考试的效率[1]。然而也正是因为信息技术的发展，从互联网上获取程序资源也越来越方便和快捷，有些学生可能直接从网上查找相关程序或者从同学那里直接复制程序提交给程序语言支撑平台。教师如果去手工检查每个程序，需要进行两两对比，这样会耗费大量的时间和精力。

从早在20世纪70年代初开始，就有学者研究阻止大规模拷贝程序的技术和软件，出现了一批比较典型的程序源代码剽窃检测系统[2]。从国内外的研究现状可以发现，国内在对程序相似度判别的研究做的非常少，大部分集中在对中文分词和语义的研究上。而国外虽然有很多成熟的系统，也发展结构化度量等成熟的技术，但都是基于文本转换和串匹配算法来实现代码相似度检测的。程序代码的抄袭跟普通文本抄袭还有不同，不同的代码可能实现同样的功能.有些聪明的抄袭者会使用一些技巧对代码进行修改，比如for循环变成while循环、添加很多中间变量，这样会降低串匹配算法的有效性。如何找到一种更合适的方法来检测更智能的抄袭是本文研究的重点[3]。

1 程序代码抄袭描述

由于程序代码不像普通文本那样没有特别的规范，程序代码的修改必须保证代码不像普通文本那样没有特别的规范，程序代码的修改必须保证代码正确运行的前提下才有作用。这就造成了代码抄袭过程中抄袭程度的不同和检测难度级别的不同[4]。

2 代码相似度定义

代码相似度表示一个程序与另外一个程序之间的相似程度，很明显100%相似就是完全相等。两个程序是否存在抄袭关系就是通过代码相似度来进行度量的，相似度越高，抄袭的可能性越大[5]。

使用属性计数法来进行源代码的剽窃检测时，首先对能表示程序特性的度量指标进行统计，生成其特征向量。然后可用向量空间模型的夹角来度量向量之间的相似性[6]。

令P1表示候选程序，其词频向量为P1( w1,w2,...,wn),P2表示检测程序，其词频向量为P2 (x1,x 2,....,xn),其中 wi, xi(1＜= i ＜= N)表示各特征值的词频，则程序段P1和P2之间的相似度Sim (P1,P2)用向量空间模型的余弦公式来度量，代码相似度定义如公式

由公式（1）可知， Sim( P1,P2)越接近 1，说明比较的2个程序P1与P2相似越密切；若等于1，则说明2个程序是同一个程序或完全相同，或者是在没有改变程序结构和标识符个数的情况下拷贝生成的另一个程序；反之亦然，但由于 C语言程序的总体结构相同（使用同样的操作符号和关键字）， Sim(P 1,P 2) =0的情况很难达到。

3 代码相似度检测方法的设计

3.1 属性计数法

1）常用元素的选定

在计算特征向量之间的相似度时，向量中的元素需要谨慎挑选。在挑选一段程序里面的常用属性的时候，应该选取一些具有特征意义的，本文挑选出以下几个属性作为特征向量里面的元素：（1）代码行数；（2）数组个数：统计出程序里定义了多少个数组；（3）自定义变量：统计程序里面不重复出现的自定义变量个数；（4）自定义变量总数：查找程序里面出现的自定义变量总数；（5）关键字：计算一下程序里面出现了多少次关键字；（6）数值常量：常量分为数值常量和字符常量；（7）字符常量：字符常量里面包括单个字符和字符串；（8）运算符。

2）获取元素的方法

在统计程序里面一些元素的时候，我们可以利用Lex，Lex是非常著名的词法分析工具，描述规则采用正则表达式[7]。描述词法分析器的文件*.l，经过lex编译后，生成一个lex.yy.c的文件，然后由C编译器编译生成一个词法分析器。词法分析器，简单来说，其任务就是输入的各种符号，转换成相应的标识符（token），转化后的标识符很容易被后续阶段处理，其过程如图1所示：

图1 Lex工作原理图

这样我们在 Lex下面写出想要抽取元素的规则就行，Lex会生成对应这些规则的C语言代码。

3.2 结构度量法

1）常用程序结构的选定

在抽取程序常用结构的时候，我们同样得找一些具有代表性的结构，比如for循环，while循环，if-else等常用结构，选定的结构为：（1）if-else结构出现的次数；（2）函数个数；（3）for循环个数；（4）while循环个数；（5）do-while循环个数；（6）调用函数次数。

2）获取常用结构的方法

当我们需要从一个程序里抽取常用逻辑结构的时候，我们需要构建C语言语法树，构建好C语言语法树后，从相应的语法树上面抽取逻辑结构，该部分的难点在于如何构建语法树[8]。

在构建语法树的时候，采用了开源代码ucc的方法，利用ucc来将程序生成相应的语法结构。将语法结构存到一个*.txt文件中，然后从这个文件中抽取逻辑结构，可以继续采用Lex来抽取。

3.3 特征向量的生成

总前说述，我们已经能够生成每个程序相应的特征向量P(x1,x2...x14)。x1（代码行数），x2（自定义数组个数），x3 (自定义变量个数)，x4 (自定义变量使用总数)，x5(关键字个数)，x6(数值常量个数)，x7(字符字符串常量个数)，x8(运算符个数)，x9(if-else结构个数)，x10(函数个数)，x11(for循环个数)，x12(while循环个数)，x13(do-while循环个数)，x14(调用函数次数)。

4 代码相似度检测方法的实现

4.1 获取常用元素的实现

在常用元素的获取过程中，关键难点在于如何获取自定义变量的个数（x3）以及自定义变量使用的总数(x4)和关键字个数(x5)。

在获取自定义变量个数的时候我们将重复出现的同一个变量只能当作一个，这边需要我们进行一个去重操作。用一个数组来维护自定义变量，检测到一个单词时，先到这个数组里面判断一下这个单词是否存在，如果存在，x3不变，否则就让x3加1。

算法伪代码描述：

根据样例输入我们得出的结果与之匹配，样例我们只是利用一部分程序，并不是完全的程序，因为我们抽取元素的时候并不需要将整个程序里面的信息都抽取出来，我们只是抽取一部分符合条件的，我们在抽取过程中会过滤掉头文件行、宏定义行、注释行等。

4.2 获取程序常用结构的实现

在获取程序常用结构的时候，关键是如何生成相对应程序的语法树，只有先生成了语法树才能从中抽取程序结构信息[9]。生成语法树采用ucc生成。ucc会将相应的程序生成语法树，语法树存放在*.asm文件中[10]。样例如下：

在生成语法树之后，可以针对相应的文件来抽取里面的结构信息，抽取的结构及方法如下：

（1）if-else结构:生成的语法树结构形式如if...then...else...end-else...end-if我们可以采用直接提取 if个数，else个数，然后最后对相应的个数除以2。

（2）函数个数：在每一个函数的开头，都会有一个function，形式如 function 函数名，我们可以直接抽取function的个数，因为每个函数只可能出现一次function。

（3）for循环个数: for循环生成语法树格式如for...end-for我们可以提取for个数和end-for个数，两者个数肯定是相等的。

（4）while循环个数：while结构跟for循环结构类似，while...end-while我们同样提取while和end-while的个数就行。

（5）do-while循环个数：do-while循环结构是do(判断条件){......}，我们可以通过查找 do出现的次数来确定有多少个do-while循环。

（6）调用函数次数：在程序内部有许多调用的函数，比如printf, scanf以及自己写的一些函数，在调用函数的时候语法数格式如：call函数名（.......）。

程序结构信息提取出来后我们可以将这些结构元素和4.1节提取出来的基本元素结合，这样会形成一个特征向量，这个向量就是这个程序对应的特征向量。每个程序就可以利用此方法来生成特征向量。0.890713。52006)812106)

4.3 计算程序间特征向量的相似度

这一节主要介绍下如何计算程序间的相似度。有两段样例程序如下：

程序样例一：

程序样例二：

程序样例一：2806261110613（基本元素）812106（结构元素）

程序样例二：20373095210（基本元素）452006（结构元素）

程序样例一计算出来的特征向量p1(2806261110613

程序样例二计算出来的特征向量p2(203730952104

由于结构元素相比于基本元素，结构相似显得更加重要，经过二分法计算，将基本元素设为43.2%，结构元素设为56.8%较为合适。利用公式1计算出来的相似度结果为：

5 总结

程序代码相似度检测方法的研究主要是应用于代码抄袭检测，代码抄袭检测必须能够检测各种程度的抄袭情况，并给出抄袭代码段，方便教师监督学生的学习情况，这对高校程序语言课程的教学有重大实际意义，大大减轻了教师的教学负担。同时代码相似度检测还能应用于软件版权的判断上，具有重大的商业价值。

[1]张文典，任冬伟.程序抄袭判定系统[J].小型微型计算机系统，1988,9(10):34-39

[2]王继远.一种用于软件作业评判系统的程序结构分析算法的设计与实现[D].北京邮电大学,2007

[3]王宁.编程题自动评分系统中结构体的研究与实现[D].哈尔滨工业大学,2006

[4]程金宏.程序代码相似度自动度量研究[D].内蒙古师范大学,2007

[5]赵长海，金茂忠.基于编译优化和反汇编的程序相似性检测方法[D].北京航空航天大学，2008

[6]王成，刘金刚.一种改进的字符串匹配算法[J].计算机工程，2006,32（2):62-64.

[7]Alfred,V.A.等著；赵建华等译.编译原理 第2版[M].北京:机械工业出版社，2009.1

[8]于海英，赵俊岚.最长公共子序列算法在程序代码相似度度量中的应用[J].内蒙古大学学报(自然科学版),2008，39(2):60-64

[9]邓爱萍.程序代码相似度度量算法研究[J].计算机工程与设计，2008，29(17):72-76

[10]于海英.程序代码相似度度量的研究与实现[J].计算机工程，2010，36(4):88-92