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

《程序代码相似度度量算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、串的散列值匹配算法。关键词：源代码;相似度度量;剽窃检测;串匹配算法;散列值匹配文章编号：1000-7024(2008)17-4636-04中图法分类号：TP311.52文献标识码：AStudyonsimilaritymeasurementofprogramcodeDENGAi-ping(DepartmentofComputerScience,HunanInstituteofHumanitles,ScienceandTechnology,Loudi417000,China)Abstract：Codeplagiar

3、ismisonekindofcheatbehavior,whichappearsfrequentlyintheprogrammingcurriculum.Detectionofsourcecodeplagiarismisimportanttoverifytheoriginalityofstudents’projectworks.Thecodesimilaritymeasurementisthekeytechnologyintheplagiarizingdetection.Thesimilaritymeasurem

4、entofprogramcodeisstudiedfirst,thenthestring’shashvaluematchingarithmeticwhichbasedonKarp-Rabinandlongestcommonsubstringalgorithmisprovided,andtheresultsshowtheimprovedarithmeticiseffective.Keywords：sourcecode;similaritymeasure;plagiarismdetection;stringmatch

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

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

7、分析等。综上所述，应用于程序代码剽窃检测系统中的代码相似度度量方法可分成两类：属性计数技术和结构度量技术。1.1属性计数技术在剽窃检测算法的发展过程中，大多数工作集中在Hal-stead的软件科学理论。这些基于软件科学度量的算法是从程序中提取出数个软件度量特征，计算每一个程序的n个不同0引言程序代码相似度度量技术主要应用在代码的剽窃检测上。判断一个程序是否是从另一个程序复制而来，实质上是对这两个程序的相似度进行度量，根据度量的结果给出一个相似度的数值表示，再由这个数值判断这两个程序之间是否存在抄袭。另外，还可以根

8、据度量值判断学生所写程序代码的标准化程度，从而辅助实现作业批改的自动化或试卷评阅的自动化。程序代码相似度度量算法研究的主要内容是如何更精确地用字符串表示程序的结构，并选择有效、快速的字符串匹配算法，以减少相似度度量的时间复杂度，提高相似度度量的准确性。1程序代码相似度度量技术早在20世纪70年代初，就有学者研究阻止大规模拷贝程序的技术和软件，出现了一批比较典型的程序源代码