湖南大学生研究性学习和创新性试验计划湖南第一师范学院教务处

1、湖南省大学生研究性学习和创新性实验计划项 目 申 报 表项目名称: ACM竞赛程序源代码复制检测系统的设计与实现学校名称湖南第一师范学院学生姓名学 号专 业性 别入 学 年 份刘 洋计算机科学与技术男2012易长庚计算机科学与技术男2012 陈 祥计算机科学与技术男2011刘聪华计算机科学与技术女2011指导教师 田祖伟职称 教授项目所属一级学科计算机科学与技术学生曾经参与科研的情况1、参加过全国信息技术应用能力竞赛；2、参加过湖南省第八届、第九届大学生计算机程序设计竞赛；指导教师承担科研课题情况 1、主持湖南省自然科学基金项目并行编程环境中事务存储的语义与优化研究（编号：11JJ3075）；

2、 2、主持湖南省科技计划项目基于传感网技术的井下人员定位与生产环境动态监控系统研究（编号：2011GK3139）； 3、主持湖南省教育厅青年项目多核环境下基于OpenMP的事务存储关键技术研究（编号：08B014），已结题； 4、主持湖南省科技厅科技计划项目低功耗SOC设计与验证技术研究（编号：2008GK3134）， 已结题； 5、主持江苏省网络监控工程中心开放基金课题基于PE文件输入表的信息隐藏技术研究（编号：KJR1208 ） 6、参与国家自然科学基金项目基于视觉感知的数字图像主动伪装技术研究（编号：61073191），排名第三；7、参与湖南省自然科学基金项目基于视觉感知的抗几何攻击图像

3、水印研究（编号：10JJ6090），排名第二；项目研究和实验的目的、内容和要解决的主要问题一、项目研究和实验的目的 高级语言程序设计是计算机等相关专业一门专业必修课程，学生程序设计能力的提高需要通过大量的编程训练。由于源程序代码的易复制性和易修改性，部分学生会复制并修改其他学生的程序代码,这将影响学生程序设计能力的提高，并影响成绩的公平性。在ACM程序设计竞赛中，在线评判系统的服务器端只对竞赛选手提交的源代码进行黑盒测试，不会对源代码进行分析和比较，因此，竞赛选手可能作弊，复制并进行简单的修改后向服务器提交源代码，这将极大地影响竞赛的公平性。为了避免或减少对源程序代码的抄袭现象，确保竞赛公平公

4、正，必须对选手提交的源代码在服务器端进行复制检测。本项目通过开发一款智能的程序源代码复制检测系统，实现高效、快速地检索相似的源代码文件。 程序源代码复制是指一个学生完全或稍作修改拷贝另一个学生的程序并把该程序当作自己的提交给老师或在线评判系统的服务器端。复制检测，即判断所提交的一个源代码文件的内容是否抄袭、剽窃或者复制于另外一个或者多个文件。为了逃避复制检测，在复制源代码后往往会进行增加或删除程序注释语句、修改变量、函数等标识符的名字、添加冗余语句、移动函数位置、不相关语句的交换等作弊行为，这给复制检测增加了难度。 目前， 国外对程序源代码的复制检测技术已取得了一定的进展，而国内发表的相关文献

5、尚少，真正实用的系统更少。在国内外各种ACM竞赛以及各高校的ACM在线评判系统中，服务器端并不会检测所提交的代码，只会检测程序运行结果的正确性而作出判断，最终结果中不排除存在抄袭现象的可能。此系统的开发将很好地解决这个问题，确保程序设计竞赛的公平公正。二、项目研究和实验内容1.复制检测相关理论和方法的研究 对现有的源代码复制检测系统进行分析研究，学习和研究源代码复制检测中的关键技术以及现有技术中存在的问题。2.源程序中无效代码的识别和删除技术，特征码的提取 由于程序源代码易于复制和修改，为了逃避复制检测，在复制源代码后往往会进行增加或删除程序注释语句、修改变量、函数等标识符的名字、添加冗余语句

6、、移动函数位置、不相关语句的交换等作弊行为，因此，在检测前必须对源代码进行预处理，通过删除源代码中的无效语句、标识符统一替换等操作后，再进行特征值的提出。3.相似度的计算 程序源代码复制检测的核心内容就是计算给定的一段程序代码与另一段程序代码之间的相似度。相似度越大，程序代码雷同成分越多；相似度越小，程序代码雷同成分越少。本项目拟采用基于N-gram的源代码相似度计算方法。 4.检测系统的开发 设计一个程序源代码复制检测系统，对提出的算法的准确性和复杂性进行验证。三、项目研究和实验待解决的主要问题 1、源程序中无效代码的识别和删除技术。 2、基于N-gram的源代码相似度计算。 3、综合分析统

7、计结果，将分析结果和雷同或疑似抄袭的部分进行可视化操作。 4、采用代码属性向量的加权思想提高分析精确度。5、收集大量实际代码进行测试并分析出合理阈值。国内外研究现状和发展动态 程序源代码相似度计算与检测是利用一定的检测手段度量两个程序源代码间的相似程度,并判定一个源代码是否复制了另一个源代码。 目前，常用的代码复制检测技术可分为两类：属性计数法和结构度量法。Halstead 提出的软件科学度量方法是最早和最典型的属性计数法。Halstead 度量方法以程序中出现的操作符和操作数为计数对象，以它们的出现次数作为计数目标来测算程序容量和工作量。Ottenstein 在1976年首次将 Halste

8、ad 的软件科学度量方法投入应用，实现了第一个针对于 Fortran 程序代码的剽窃检测系统。但是，单纯的属性计数法抛弃了太多的程序结构信息，导致检测结果的错误率太高，由其对于非常短小的程序来说是无效的。Verco 和 Wise 在 1996 年指出，对于仅仅使用属性计数法的检测算法增加向量维数并不能改善错误率。改进属性计数法的措施就是加入程序的结构信息，结合结构度量技术来检测剽窃1。McCabe 提出的圈复杂度方法是一种典型的结构度量法。它通过计算执行路径的数量来衡量一个程序中的控制流。圈复杂度只给出了程序的一个结构特征即控制流，往往需要与其它特征结合使用，因此常作了属性计数法中的一个度量指

9、标。其他的结构度量法还有分析控制结构、计算代码嵌套深度、分析数据依赖关系等等。在实际应用中，很多代码剽窃检测系统将两种度量方法相结合。Donaldson et al. 开发的 ACCUSE 系统2结合属性计数法和结构度量法来实现对Fortran 程序代码的剽窃检测。ACCUSE 最初是由 USAF 学院的 Sam Grier 于 1981 年开发,用于 Pascal 程序的复制检测。最近提出的系统大都是通过对表达源程序结构的字符串进行比较来达到剽窃检测的目的。如：Plague3、YAP4系列、MOSS5、 JPlag6、和 SIM7。这些源代码复制检测系统都没有详细介绍其具体的检测算法,提供的

10、服务和功能也各有特色。另外,Faidhi 和 Robinson8提出使用 24 个分量来评估代码的相似程度，前 10 个是主要针对初学者的低级的剽窃，其它的用于有经验的剽窃；Jankowitz 方法通过对代码中的主程序和方法进行语法分析，得到静态执行树，用于对代码的分析；等等。此外，还有人提出用神经网络来检测程序复制9。 国内目前针对源代码复制检测的研究比较少，使用的技术跟代码克隆检测是相似的。在代码克隆检测方面，已经有很多相关的算法和工具。参考文献1 Verco K.L., Wise M. J. . Software for Detecting Suspected Plagiarism: C

11、omparing Structure and Attribute-counting Systems. In: the 1st Australian Conference on Computer Science Education, 1996:3-5 .2 J. L. Donaldson, A. Lancaster , P. H. Sposato. A plagiarism detection system. ACM SIGSCI Bulletin 13(1), 1981,21-25.3 P.Clough. Plagiarism in natural and programming langua

12、ges: an overview of current tools and technologies. Department of Computer Science, University of Sheffield, 2000,1-31.4 Michael J.Wise. YAP3: Improved detection of similarities in computer program and other texts. In : SIGCSE Technical Symposium, Philadelphia, Pennsylvania, USA,1996,130-134.5 Boywe

13、r, Kevin W. & Hall, Lawrence O. Experience using MOSS to Detect Cheating on Programming Assignments.In: 29th ASEE/IEEE Frontiers in Education Conference, San Juan, Puerto Rico, 1999, 18-22.6 L.Prechelt, G.Malpohl, M.Philippsen. Finding plagiarisms among a set of programs with Jplag. J. of Univer

14、sal Computer Science, 2000,8(11):1016-1038.7 D.Gitchell, N.Tran. Sim: A Utility for Detecting Similarity in Computer Programs.In:the 30th SIGCSE Technical Symposium on Computer Science Education, New Orleans,Louisiana, USA, 1999:266-270.8 J. A. Faidhi , S. K. Robinson. An empirical approach for dete

15、cting program similarity and plagiarism within a university programming environment. Computing in Education,1987,11(1):11-19.9 S.Singhe, F.J.Tweedie. Neural Networks and Disputed Authorship: New Challenges. In:the 4th International Conference on Artificial Neural Networks,1995, 2428.本项目学生有关的研究积累和已取得

16、的成绩本系统已经实现C/C+源代码基于字符串的分析和检测系统。项目的创新点和特色在国内外ACM赛事都沿用一套非常严谨的比赛规则：ACM/ICPC (对赛题中的结果要求绝对的正确。系统不会分析选手所提交的代码，只检测程序运行的结果)。针对上述赛事，若选手提交的代码成功通过经典评测系统的检测，则利用本系统将此代码与在它之前通过的代码进行分析比较，若出现完全或者特别严重的雷同现象，则可判定为抄袭或者进行人为干预，增强了比赛结果的可靠性。主要创新点和特色如下：1.源程序中无效代码的识别和删除技术；2.基于程序设计语言关键词的词法分析技术；3.基于N-gram的源代码相似度计算算法；4.源程序有效代码中

17、相似内容的标识并可视化技术；项目的技术路线及预期成果一、技术路线重点研究程序设计语言中源代码标识符的特点和类型、源代码预处理技术、相似源代码的检测技术。系统先通过预处理程序删除程序中的无效代码（程序中的注释、文件包含等内容），然后采用基于程序设计语言关键词的词法分析技术对源程序中的有效代码进行分析，针对不同的程序设计语言进行关键词的统计与分析，采用基于N-gram的源代码相似度计算算法进行相似度的计算，并实现对源程序代码相似度的自动获取, 对原样复制 、修改注释语句、更改源程序排列方式、改变源程序空白区域、变量重命名、交换源程序中不相关的语句的顺序等进行检测。主要处理步骤如下：1、将无效代码删除，并将两份代码分词处理；2、对代码进行简单的词法分析，统一替换变量名；3、对关键字的统计与分析；4、对物理结构和程序容量的统计