卫军超　耿楠

摘要：针对传统相似度算法应用在程序设计课程作业检测中精度较低这一问题，通过研究最长公共子序列等算法，发现其优缺点，在分析的基础上，结合结构度量技术和属性技术两种技术，提出一种性能较好的程序相似度计算方法。方法首先对源程序进行初步处理，将程序中的注释语句和空格删除，再次确定常用元素及常用结构，然后利用Lex统计、抽取程序元素；利用開源代码ucc生成语法树，之后抽取相应的语法结构；最后生成特征向量，并计算代码相似度。实验结果表明该方法比最长公共子序列算法精度提高了10.6%。

关键词：属性计数法；结构度量技术 ；相似度度量

中图分类号： TP311 文献标志码： A 文章编号：1009-3044（2017）05-0039-02

Abstract： To solve the problem of the low precision of testing for similarity of program codes in traditional ways， this thesis proposes an improved technique to make such a test on the combination of technology of attribute counting and that of structure calculation through studying and comparing several different methods of calculating the Longest Common Subsequence. Firstly， source program is processed primarily， annotation statements and spaces are deleted， and common elements and structures get confirmation； next， statistics are made by means of Lex， program elements are extracted， and abstract syntax trees get to be generated using UCC； then， grammar structures are extracted； lastly， eigenvector is produced and the similarity can get calculated. The experimental result shows that the new method is 10.6 percent more precise than those of calculating the Longest Common Subsequence.

Key words： attribute counting； structure measurement； similarity measurement

在程序设计课程教学中，尤其是在上机编程训练过程中，需要学生通过独立地编程练习来提高程序设计能力，然而实际的情况是部分学生存在不同程度地抄袭他人的作业。在这种情况下，教师要批阅学生的作业，同时要甄别抄袭程度，通过手工操作很难准确完成。因此，在程序设计类课程中，要甄别学生作业是否抄袭采用计算机自动度量的办法，具有很重要的现实意义。

早在二十世纪七十年代时，Ottenstein[1]就已经是开始使用属性计数法，通过其对抄袭检测系统的使用，人们对于属性计数法的重视程度不断提高。设计的抄袭检测系统使用了Halstead提出的属性计数法，该系统应用于FORTRAN语言源程序的相似度检测；利用属性计数技术设计的相似度检测系统没有考虑程序的结构信息，导致误判率较高。而结构度量技术克服了属性计数法带来的一些问题，因此在实际过程中应用比较广泛，如：Sim、JPag、YAP3[2，3]、和MOSS[4]等。从国内外的研究现状可以发现，国内对于相似度检测的起步晚、研究少，且绝大多数的重点在中文分词和语义的研究上，应用于论文抄袭检测。国外的抄袭检测系统较多且比较成熟，可是大多数研究汇集在文本转换和串匹配算法方面。源程序的抄袭和一般的文本抄袭有差异，不同结构的代码可以实现相同的功能。一些学生为了躲避抄袭检测，采用比较高级的抄袭方法，如添加冗余代码、控制结构等价变换等，即源代码中的部分内容用等价功能的语句进行替换，如将if语句修改成switch语句，将while循环语句改为for循环等，这样修改会降低串匹配算法的有效性。

针对于上述问题的存在，本文在对集中相似性检测方法进行了研究，并在研究的基础上提出一种能够有效改进这些方法，并且可以实现检测效能的方法。

1 相关研究

当前，对于相似度度量技术的使用中，主要是形成了两种度量技术，一种是属性计数法，另外一种是机构度量技术，这两种方法各有特色，在相似度检测中发挥了巨大的功能。

1）属性计数法

属性计数法是Halstead提出的软件科学度量方法。在属性计数法的使用中，主要是设计到几个数值的表示。首先是表示所用到的操作符的种类数，这个是用[η1]进行表示，对于用到的操作数的种类数就是利用[η2]表示。值得注意的是，在这个过程中对于操作符的总数和操作数的总数也是需要进行计数，分别是用[N1]，[N2]进行表示。对于代码的总行数来说，在公式计算的过程中，是用L进行表示。

该方法的缺点是若是抄袭者插入一些不相关的关键字、变量、完全无关的函数，该算法便很难检测，而对于不属于抄袭的源代码，因为属性个数相近，可能会产生较大的误判概率。

属性计数法抛弃了绝大多数的程序结构信息，而结构度量技术恰恰弥补了属性计数法的这一缺陷。

2）结构度量技术

结构度量技术对于程序之间的相似度的检验，主要是通过分析其程序的特征结构来进行度量。具体来说，结构度量技术主要是通过分析各个程序中嵌套深度、控制结构的内容等之间存在的不同分析相似性的高低。在该方法操作的过程中，第一步就是对程序的结构进行分析，这是整个操作中最为重要的步骤，不仅如此，在分析的过程中，还要保证能够将程序语言中的元素特点进行转换，主要是转换成标记序列。经过一系列的操作，两个程序就的长度逐渐缩小，并且几乎就是以字符串的形式存在，这样，就能够对其中算法较少的字符串进行相似度的比较，并且可以根据比较的结果得出两个程序之间相似的程度，这个方法较为可靠，获得结果也是比较有典型性。

代码相似度度量技术各有优缺点，属性计数算法运行时间复杂度较低，但其抛弃太多程序结构信息，其性能较低；而结构度量技术检测源代码性能较高，但是时间复杂度也较高。因此，本文旨在探索一种综合属性计数和结构度量技术优点而时间复杂度相对较低的相似度计算方法。

2 基于程序结构度量的常见相似度计算方法

对于程序结构度量相似度的算法，主要是通过对于程序的结构信息、执行的流程判定程序等进行分析，并在比较分析的基础上得出其相似度的判定结论。当前，在结构度量技术中比较常用的方法，首先就是Levenshtein距离，其次还有最长公共子序列和串的散列值匹配算法等，这些方法在使用的过程中各有特色，本文会对其进行一一介绍。

2.1 Levenshtein距离

Levenshtein距离又称为编辑距离（ED：Edit Distance），是俄国科学家Vladimir Levenshtein在二十世纪六十年代中提出来的一种相似度比较算法。在这个算法中，主要是通过比较最少编辑次数确定其相似程度。具体来说，是将需要对比的两个字符串进行转换，也就是将其中的一组字符串经过一系列的编辑转换成另外一个字符串。包括对于这个字符串进行的插入、替换以及删除等编辑操作，保證经过编辑之后，两个字符串之间没有差别。如果使用的编辑次数较少就可以实现将一个字符串转换成另一个，那么两者之间的相似性程度就是比较高[5]。Levenshtein距离可用如下算法求得：设对于待检测源码字符串串[S，T]的编辑距离为[D（|S|，|T|）]，其编辑距离相似度[sim（S，T）]计算公式是：

2.2 最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）[6]方法主要是通过对于进行相似度检测的两个字符串进行删除操作，在操作的过程中对于字符的顺序不改变，经过一系列的删除之后，获得其中字符长度最长的字符序列，并对其进行比较。如果源程序的字符串中存在的最长公共子序列长度愈长，那就说明两个字符串之间的相似程度越高。

G.Whale基于最长公共子序列算法对源代码进行了相似度比较，开发了Plague系统，实现了程序的自动抄袭检测。

参考文献：

[1] Ottenstein K J. An Algorithmic Approach to the Detection and Prevention of plagiarism[J]. CSD-TR200， 1976，103（2）.

[2] Michael J.Wise. YAP3：Improved Detection of Similarities in Computer Program and other Texts[J] . Department of Computer Science， University of Sydney， 2003， 10（3）.

[3] Wise. M. J. Detectiom of similarities in student programs. SIGSCI Technical Symposium， Kansas City， USA， 1992.

[4] Clough. P. Plagiarism in natural and programming languages：An overview of current tools and technologies. Research Memoranda：CS-00-05， Deoartment of Computer Sicencce， University of Sheffield， 2000.

[5] 郑凯，欧阳林艳，林强，等.LCS算法与编辑距离算法的研究[J].信息通信，2015，31（5）.

[6] 古平，张锋，周海涛.一种程序源代码相似度度量方法[J].计算机工程，2012，38（6）.