程序代码相似度评判系统的设计与实现

摘 要：程序代码相似性的识别是利用一定的检测识别手段，判断两个源程序代码之间的相似性，并度量两个程序代码之间的相似程度。代码抄袭是程序设计课程中频繁出现的一种作弊行为，检测源代码的抄袭对验证学生程序作业的独创性非常重要。本文针对计算机教学考核中对程序设计客观性和真实性的要求，应用最长公共子序列算法来对比两个源程序文件在结构上的相似性，同时设计可用于教学考核的程序代码相似度评判系统。

关键词：源代码；相似度评判；抄袭检测；最长公共子序列

中图分类号：TP309

程序代码相似性度量技术主要用于代码的抄袭检测上，主要来确定一个程序是否是通过复制另外一个程序得来。在本质上，本技术是通过对这两个程序代码的相似度进行分析衡量，根据衡量的结果给出一个相似度的数值表示，然后由此数值来判断这两个程序是否存在互相抄袭的现象。程序代码的相似性度量算法主要研究如何更准确地把程序的结构用字符串形式表示，并选择一个快速的、有效的字符串匹配算法，以提高相似性度量的准确性，同时尽量减少代码相似性度量算法的复杂度。

1 最长公共子串程序代码相似度评判方法

最长公共子串指的是给定的一组字符串的长度最大的共有的子字符串。若将字符串看成是由若干个子串组成，则两个字符串中存在的相同的子串就是它们的公共子串，因而，它们的相似度可用所有公共子串的长度占整个串的百分比表示。

LCS算法的具体实现过程主要可以分为以下两个部分：

（1）

（2）

Xi=x1，…，xi即X序列的前i个字符（1≤i≤m）（前缀）；

Yj=y1，…，yj即Y序列的前j个字符（1≤j≤n）（前缀）；

Length（i，j）表示Xi和Yj的最长公共子序列的长度。

（1）求出最长公共子序列的长度Length（i，j）

利用最长公共子序列问题的子问题重叠性质，定义一个标志位数组变量f（i，j），将子字符串中字符的匹配结果保存在其中，以避免多次的重复运算。由公式（1）可以知道：

若i=0或j=0，则Length（i，j）=0；

若xi=bj，则Length（i，j）=Length（i-1，j-1）+1，f（i，j）=“”；

若xi≠yi，且Length（i-1，j）=Length（i，j-1），则Length（i，j）=Length（i-1，j），f（i，j）=“”；

若xi≠yi，且Length（i-1，j）

由于计算每个数组单元的时间复杂度为O（1），所以求解Length（i，j）的时间复杂度为O（M*N）。

（2）求出最长公共子序列LCS（X，Y）

根据上述过程中计算最优值时得到的最长公共子序列长度，搜索在上述求解Length（i，j）的过程中保存的匹配结果f（i，j），构造最优解。

若i或j为0，返回空字符串；

若f（i，j）=“”，则Xi，Yj的最长公共子序列是Xi-1，Yj-1的最长公共子序列在尾部加上xi得到的子序列；

若f（i，j）=“”，则Xi，Yj和Xi-1，Yj有着相同的最长公共子序列；

若f（i，j）=“”，则Xi，Yj和Xi，Yj-1有着相同的最长公共子序列；

用LCS（X，Y）保存每次比较得到的公共子序列，比较结束后得到两个字符串的最长公共子序列。在求解LCS（X，Y）过程中，因为每次递归调用都会使i或j减1，因此计算的时间复杂度为O（m+n）。为了使运行方便，程序中可以将“”，“”，“”替换为某些方便判别的标记，比如数字。结合LCS算法以及DUPOC工具的判别思想，逐行分析程序语句，可以直观的得到程序代码之间的相似的部分。

2 系统总体设计

2.1 系统概述

本系统具体的各个部分操作如下：

（1）文件导入，一对一对比的源代码的文件的采集。

（2）源文件具体信息采集，获取源文件的具体信息并显示。

（3）文件夹导入，导入文件夹中的所有源代码文件。

（4）文件列表显示，显示批处理源文件的列表。

（5）相似度阀值设置，根据实际情况设置合适的相似度阀值，可以经过反复比较后确定，以达到预期的效果。

（6）数据预处理，获取导入的源文件中的代码，并对其进行扫描并预处理，除去注释等冗余信息。

（7）代码比较，用LCS算法得出经过预处理的两段程序代码的最长公共子序列，并得出相似度信息。

（8）批处理，用LCS算法结合设定的相似度阀值对所选文件夹下的源代码文件与指定源代码文件进行对比并得出相似度信息。

（9）源代码相似度信息，显示单文件对比和批处理的结果，单文件对比包括最长公共子序列和相似度百分比。批处理包括最长公共子序列以及符合阀值设定范围的文件的信息。

（10）分析结果输出，将批处理得到的分析结果自动输出到文本文件里面，方便用户查看。

（11）使用说明，帮助菜单项中包括使用说明，给用户方便的使用本系统提供帮助。

2.2 系统逻辑层次设计

（1）界面层给用户提供了一个操作界面，通过界面层，用户可以输入数据或者操作命令，系统则显示出相关数据。主要功能划分为若干独立应用程序模块。

（2）逻辑层是系统设计过程中的关键和难点。本课题中，根据数据的相关性及不同的职能，将其划分成多个对象，这样做的目的可以重复利用对象中的Provider和方法，减少冗余，层次清晰。逻辑层主要负责对各类应用的数据请求进行封装。

2.3 概要设计

软件的结构采用了典型的三层设计，在View接口里的操作都可以从BLL层交互一次数据，而BLL层的操作则是从DAL层抽象而来的。

这样的概要设计可以实现三层结构，三层结构的优势在于任何一层的修改都可以独立于其他三层，这样的设计有效的降低了系统的耦合度。使得程序的适应性极大的提高。

2.4 总体功能模块设计

根据系统的设计要求，系统的总体功能设计必须齐全，保证客户需求，本课题中将系统划分为以下几个功能模块：

（1）单文件对比模块：负责定位两个独立的源代码文件，并将文件中的代码信息读入，然后使用最长公共子串算法进行处理。

（2）文件基础信息显示模块：负责读取并显示源代码文件的基础信息。

（3）代码相似度显示模块：显示独立对比时的两个源代码文件的相似度。

（4）批处理模块：快速读取指定目录中的所有源代码文件，并进行LCS处理。

（5）文件打印模块：将使用最长公共子序列算法处理过的源文件代码的相似度对比信息打印到文件中。

3 系统详细设计

依据系统设计目标和功能模块的设计结果，采用Visual C++10.0来实现各个模块的功能。本系统采用基于对话框的设计方法来实现。

3.1 主界面设计

主程序界面是应用程序与其他功能模块的连接平台，涵盖了程序的所有功能模块，如下图所示：

图1 主界面

3.2 单文件对比模块设计

在对两个源代码文件进行比较时，首先分别对输入的源代码进行分析，去除其中的注释等冗余字段，然后使用最长公共子串算法进行比较，分析两段源代码的最长公共子序列，然后进一步求相似程度，比较的结果将显示在源代码相似度信息模块。

关键代码如下所示（位于文件Solute.cpp）：

void CSolute：：LCS（int i，int j，char *x，int **c）

{

CString str；

if（i==0||j==0）

return；

if（c[i][j]==c[i-1][j-1]+1）

{

LCS（i-1，j-1，x，c）；

str.Format（"%c"，x[i]）；

s=s+str；

}

else if（c[i][j]==c[i-1][j]）

LCS（i-1，j，x，c）；

else

LCS（i，j-1，x，c）；

}

3.3 源代码文件具体信息模块设计

对于单文件对比模块导入的两段源代码文件，本模块会将两个文件的创建时间和文件的大小等信息显示出来。

3.4 源代码相似度信息模块设计

经过最长公共子序列算法运算得到的程序代码相似度的结果会显示在本模块，显示的内容包括最长公共子序列的内容和长度，以及源文件代码相似度的百分比表示。

3.5 批处理模块1-阈值选择设计

批处理模块用来选择批处理源文件所在的文件夹，并能用相似度阀值来控制批处理模块的结果和输出，通过控制相似度阀值来控制对批处理模块中源文件代码的相似度要求，最后根据最长公共子序列算法以及设定的阀值来计算最后的结果并输出。

3.6 批处理模块2-文件列表设计

本模块会将批处理模块源代码文件所在目录的所有源文件的名称整理并以列表的形式显示出来，使用户能够直观的了解相关情况。

3.7 实验结果与截图

首先对比完全相同的两段源代码。

图2 实验结果截图1

然后将此源代码与对这段源代码进行大量变量替换和少量位置变换得到的源代码进行对比。

图3 实验结果截图2

以上仅为大量的实验的代表，不过也足以表明本系统在对学生上机程序作业相似性的检测上还是比较有效的。

4 结束语

本系统选用可视化的编程工具Microsoft Visual Studio 2010作为前台开发工具，使用Microsoft MFC库作为整体运行环境，整体设计以软件工程思想为指导思想，采用VC++开发，使用最长公共子序列算法来分析程序代码的相似性问题，实现了对程序代码相似度评判的功能。

目前，系统已经完成，能够安全稳定的运行。本系统实现了程序代码相似度评判的基本功能，但系统同时也存在许多不足之处，比如无法有效检测变换了顺序的源程序代码片段，有待于进一步完善。

参考文献：

[1]熊浩，晏海华，黄永刚.一种基于BP神经网络的代码相似性检测方法[J].计算机科学，2010（03）.

[2]陈浩，王广南，孙建华.一种基于图的程序行为相似性比较方法[J].计算机应用研究，2010（02）.

[3]Boywer Kevin W， Hall Lawrence O. Experience using 'MOSS' to detect cheating on programming assignments[C].San Juan，Puerto Rico： 29th ASEE/IEEE Frontiers in Education Conference，1999.

[4]Andrew Granville.Detecting plagiarism in Java code[D].Supervisor：Yorick Wilks，2002.

[5]Prechelt L，Malpohl G，Philippsen M.Finding plagiarisms among a set of programs with JPlag[J].Journal of Universal Computer Science，2002（11）.

[6]Alex Aiken，Saul Schleimer，Daniel S Wilkerson. Winnowing：Local algorithms for document fingerprinting[C].Proceedings of the ACM SIGMOD International Conference on Management，2003.

[7]陈媛媛.基于抽象语法树的编程题自动评分系统的研究与应用[D].大连海事大学，2011.

[8]张鹏，C程序相似代码识别方法的研究与实现[D].大连理工大学，2008.

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

[10]邓爱萍.程序源代码复制检测技术研究[D].湖南大学，2008.

[11]于海英.程序代码相似度度量的研究与实现[J].计算机工程，2010（04）.

[12]张丽萍，刘东升，李彦臣.基于语法树的程序代码复制检测方法及其评价机制的研究[J].内蒙古大学学报（自然科学版），2010（05）.

[13]邓爱萍，徐国梁，肖奔.基于串匹配方法的源代码复制检测技术研究[J].科学技术与工程，2007（10）.

[14]熊浩，晏海华，赫建营.一种基于静态词法树的程序相似性检测方法[J].计算机应用研究，2009（04）.

[15]张莉，周祖林.代码相似性检测在程序设计教学中的应用[J].计算机教育，2009（13）.

作者简介：李潇阳（1991-），女，上海人，硕士生，研究方向：环境监测与评价；通讯作者：郑有飞（1959-），男，无锡人，博士生导师，研究方向：农业气象。

作者单位：南京信息工程大学 环境科学与工程系，南京 210044