相似度检测技术在计算机实验教学中的应用研究

张华++周学权++张淼++郑宏珍++初佃辉

摘 要计算机实验教学平台是现代实验教学改革的一个重要内容。然而，在以往的实验教学模式中，仅凭教师检查很难发现学生作业是否抄袭。为了解决此问题，本文将基于数字指纹的代码相似度检测算法应用到程序设计实验教学平台中。实践表明，学生之间的抄袭现象得到控制，教师的评判工作量也大大降低。

【关键词】相似度检测 实验教学 代码抄袭

1 计算机实验教学中存在的问题

在程序设计、数据结构与算法等课程的实验教学中，部分学生由于没有学好课程或者出于其他目的，会抄袭其他同学的作业。在这种情况下，教师在检查学生实验作业的同时，还要在大量的作业中检查抄袭现象，这无疑地增加了教师的工作量，有时甚至很难通过手工操作完成。因此，实现代码相似度的自动检测，具有很重要的现实意义。

国外对代码相似度检测的研究起步较早。MOSS，Jplag，SIM和YAP系列等系统都是比较著名的代码相似度检测工具。其中MOSS和Jplag还有支持WEB访问的调用接口。国内也出现了不少具有相似度检测功能的在线实验平台，如哈工大的高级语言程序设计能力训练平台及考试系统、国防科大的Trustie、浙大的PTA、成都琛石科技的实验楼等。

基于以上对代码相似度检测算法和系统研究现状的分析，本文结合基于数字指纹的代码相似度检测算法完成代码相似度检测模块的设计与实现。

2 相似度检测需求分析与设计

2.1 需求分析

应用于程序设计实验教学平台中的代码相似度检测模块应符合以下要求：

（1）应当基于一种可靠的代码相似度计算方法；

（2）所基于的算法应易于移植（可针对不同语言）；

（3）友好的用户界面，方便教师对学生在线提交的作业进行抄袭检查；

（4）输出信息中应明确给出所有具有抄袭嫌疑的代码。

只有达到这样的要求，才能减轻教师的工作量并在有效降低抄袭率的情况下提高实验教学的质量。

2.2 流程设计

代码相似度检测是程序设计实验平台的核心子功能，教师通过选择学期号、课程号、实验号和编码语言，对学生上传的源代码进行相似度的检测，代码检测流程如图1所示。可以看出，送入相似度检测内核的文件不仅是根据学期号、课程号和实验号获得的代码文件，有时还要有检测范围选择。同班检测时，是最小的检测范围，仅仅针对检测目录下相同班号的代码文件进行检测；同届检测，对检测目录下的所有文件进行检测；隔届检测，则需要引入往届学生提交的代码作为参考文件来进行检测。

2.3 算法设计

借鉴论文中的思想，将数字指纹提取算法作为抄袭检测模块的核心。基于数字指纹的代码相似度检测算法的具体步骤如下：

Step 1 预处理：对程序源代码进行过滤和替换处理。首先，把程序中所有的注释、空行、宏命令、与代码语义无关的内容全部去掉。

Step 2 分词：将代码中所含的不同类型的符号之间加上间隔符“空格”，若原来就有空格的则予以保留。

Step 3 格式化：将用户自定义的标识符替换成UDEF，将数据类型替换成DTYPE，将标准输出printf及内容替换成printf（），将cout及内容替换成cout<<，并且删除代码中词语词之间的空格。

Step 4 数值化：将代码重叠切分成长度为g的特征片段，根据哈希函数计算得到数值集合。假设起始位置为i，对于长度为g的特征片段，其哈希值计算公式如下：

（1）

其中Ci是该片段中某个字符对应的ASCII码，g是片段长度即指纹粒度，M是一个很大的数。

Step 5 指纹化：从获得的数值序列中去掉无效数值集合（由代码编写规则产生的相同代码片段，经数值化处理生成的集合）后，对有效数值序列进行重叠切分，并采用最小Hash法获取最终的数字指纹序列，即对有效数值序列进行重叠切分，窗口大小为w，其次在每个切分过后的数值片段中选择最小的Hash值，其中每个位置的数值只能被选择一次。

Step 6 相似度计算：获取两段代码的数字序列后，通过二者间最长公共子序列求得相似度值。

（2）

其中F（A）、F（B）为分别表示代码A和B的数字指纹序列，|LCS（F（A），F（B））|表示指纹序列之间的最长公共子序列。

3 算法应用

上述相似度检测算法在我校数据结构实践教学平台中进行了应用。教师进入如图2所示的代码查重頁面，通过下拉框选择学期号、课程号、实验题号（大实验标题序号，子实验标题序号），点击“提交”便会得到一个要检测的文件清单。点击“查看结果”则启动相似度检测功能，并返回如图3所示的检测结果，这里只截取了其中的一条。File1和File2分别对应相似度检测模块所检测的两个文件，Matched代表这两个文件的相似程度。点击任意一侧的蓝色链接，还可以具体查看该侧代码和另一侧代码相似的部分，并以红色标出，方便教师对抄袭行为进行详细鉴定，保证实验的质量和成绩的公平性。

4 结束语

本文实现的基于数字指纹的代码相似度检测算法可以应用到程序设计实验教学平台中。一方面，能够给出源程序间的相似度值，减少教师的工作量；同时，还能给出相似代码的具体位置，以便教师进一步人工比对，保证公平性。下一步将开发对多文档程序的相似度检测模块，并设计更加优化的相似度检测算法。

参考文献

[1]Ottenstein K J.An algorithmic approach to the detection and prevention of plagiarism[J].Acm Sigcse Bulletin，1976，8（04）：30-41.endprint

[2]Parker A，Hamblen J O.Computer algorithms for plagiarism detection[J].IEEE Transactions on Education， 1989，32（02）：94-99.

[3]Aiken A.Moss：a system for detecting software plagiarism.http：//theory.stanford.edu/～aiken/moss/.

[4]Prechelt L，Malpohl G，Philippsen M.Finding plagiarisms among a set of programs with Jplag[J].Journal of Universal Computer Science，2002，8（11）：1016-1038.

[5]Gitchell D，Tran N.Sim：A Utility for Detecting Similarity in Computer Programs[C].Proceedings of the 30th SIGCSE Technical Symposium.New Orleans，LA，USA，1999.

[6]Wise M J.Detection of similarities in student programs：YAPing may be preferable to Plagueing[C].Proceedings of the 23th SIGCSE Technical Symposium. Kansas City，USA，1992，24（01）：268-271.

[7]Thomas Lancaster，Fintan Culwin.A Comparison of Source Code Plagiarism Detection Engines[J].Computer Science Education，2004，14（02）：101-112.

[8]哈尔滨工业大学.高级语言程序设计能力训练平台.http：//sc.hit.edu.cn/train.

[9]国防科学技术大学.Trustie创新实践社区.https：//www.trustie.net.

[10]浙江大学.程序设计类实验辅助教学平台.https：//pta.patest.cn/.

[11]成都琛石科技.實验楼.https：//www.shiyanlou.com/.

[12]Schleimer S，Wilkerson D S，Aiken A.Winnowing：local algorithms for document fingerprinting[C].ACM SIGMOD International Conference on Management of Data.ACM，2003：76-85.

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

[14]黄柳柳，黄河燕，史树敏.面向代码相似度检测的指纹选取方法[J].计算机工程与应用，2010，46（27）：169-171.

[15]邓爱萍.程序代码相似度度量算法研究[J].计算机工程与设计，2008，29（17）：4636-4638.

作者简介

张华（1978-），男，内蒙古自治区通辽市人。硕士学位。讲师。主要研究方向为在线教学、服务大数据。

周学权（1979-），男，广东省惠州市人。硕士学位。讲师。主要研究方向为个性化教学、服务大组合与优化。

张淼（1979-），女，内蒙古自治区包头市人。硕士学位。讲师。主要研究方向为有效教学、密码学及其应用。

作者单位

哈尔滨工业大学（威海）计算机科学与技术学院 山东省威海市 264209endprint