王　宁,李润东

(湖南工程学院 计算机与通信学院，湘潭 411104)



OnlineJudge中反抄袭机制的研究和实现

王宁,李润东

(湖南工程学院 计算机与通信学院，湘潭 411104)

OnlineJudge中的反抄袭机制可以检测到其在使用过程中的作弊现象，为了更深入地了解OnlineJudge的反作弊的实现原理，以HUSTOJ(众多OJ中的一种)为研究对象，剖析其中的SIM相似度检测软件的运行机制，以及在HUSTOJ中实现反作弊的方法.实验结果直观的表明了SIM相似度检测软件的有效性.

OnlineJudge；反抄袭；HUSTOJ；SIM；相似度检测

OnlineJudge[1]，即在线评判系统(简称OJ),被广泛的运用到现代教育教学中，尤其是在计算机类的学科的教学中，老师将题目发布到OJ系统中去，学生通过web端提交代码至服务器，服务器接受到用户提交的代码之后，进行编译、运行、评判后将结果返回给web端，将结果非常直观的反馈给学生.

OJ系统方便了老师的教学，但是有些学生将别人的代码进行修改之后提交给OJ，这就产生了作弊的现象，这就阻碍了OJ系统在教学中的应用，因此需要一套可以对提交的代码进行相似度检测工具来杜绝此类现象的发生.HUSTOJ[2]，是众多OJ中的一种，它使用开源的SIM软件[3-4]来对代码进行相似度的检测，很好的解决了这个问题.

图1　HUSTOJ

1　SIM介绍

1.1相似度检测的常用方法

相似度检测一般有如下两种方法[5]：

1.1.1属性计数法

属性计数法通过提取两段代码中的运算符，操作符，行数，字符数，程序注释等相关属性的数量，并将它们表示为N元组，对N元组进行规范化，并计算他们的欧几里得距离，由此来判断源码的相似度.缺点：如果抄袭者加入一些多余的关键字，变量，甚至一些冗余的源码，系统便很难检测，而对于不属于抄袭甚至完全不相关的源码，由于属性个数相近的原因可能存在较大的误判概率.

1.1.2结构度量法

结构度量法从程序的结构上进行分析，避开了任何冗余代码，主要分2个步骤：

(1)首先对源码进行词法或语法分析并产生符号序列，在此过程中将同义词映射为统一的形式，将自定义的标识符转换为标准符号，删除空白符号和注释，将大小写字母转化为小写等；

(2)采用相关字符串匹配技术比较前面产生的符号序列，并求出其相似度.

1.2SIM工作原理

1.2.1SIM的工作方法

SIM属于结构度量法，首先，SIM将提交的源代码用linux下的Lex词法分析工具[6]进行压缩，Lex将源代码转换成相应的标识符(token)，转化之后的标识符很容易的被后续阶段处理，源代码就表示成为了另外一种紧缩的格式，并建立相应的向前引用表，再采用一种检测DNA序列相似性的算法，将压缩串分成若干份，将每份压缩串与另外的压缩串中进行匹配，匹配出来的子串将被删除，直到不出现匹配的子串为止.在OJ中，系统只将当前用户与对应题目的以往用户的正确代码进行匹配，如果相似度达到某个阀值，就会在相对应的数据库中留下相关的记录.

1.2.2SIM软件中主要文件以及作用

sim.c获得命令行参数，检查参数，初始化语言，预计算表.

compare.c进行比较

tokenarray.c使用lex对输入进行处理.TokenArray[]记录着所有输入的标识符.

pass1.c读取文件

pass2.c找到每个运行线程的确切位置

pass3.c打印出相似度.

1.2.3SIM软件的工作步骤

(1)文件读取

用Lex词法分析工具对每个文件的输入进行标识.每个标示占一个字节，可能会占满8位.标识符存储在TokenArray[]这个数组里面，如果溢出了，那么再分配内存.为了尽可能的优化pass2，一个办法就是去记住每行开始的那个标识符的位置.标识符的位置存储在nl_buff[]这个数组里面，如果一样，也可以进行再分配.如果由于缺少内存而失败，nl_buff[]会被舍弃，pass2会继续的读取文件.

(2)建立向前引用表

文本通过对每个子串和它右边的子串来进行比较，通过hash表可以更加的快速的去执行.一旦整个文本被读入，一张向前引用表就被建立.

(3)确定运行线程的集合

如果在一个新文件中，在给定的位置找到一个正确的运行，就调用add_run()函数，跳过这个新文件，阻止重复的运行.

(4)确定每个运行的线程的确切的位置

(5)按顺序打印出的结果

2　反抄袭在HUSTOJ中的实现

2.1HUSTOJ的运行机制

在HUSTOJ中，web端和core的连接方式默认是通过数据库连接 ，交互的过程主要是以下四个步骤：

(1)有新的代码提交至服务器时，web端向solution表中插入记录;

(2)core轮询solution表，当发现有新的记录时执行相应的操作;

(3)core更新solution表的result字段;

(4)web端轮询solution表将result字段显示出来.

流程图如图2所示.

图2　HUSTOJ工作流程图

2.2在HUSTOJ中启用SIM

在HUSTOJ的配置文件中有一个OJ_SIM_ENABLE=1的配置项，用来确定是否使用SIM进行代码相似度的检测.

有一个专门的sim表存放着相关的信息，如图3所示.

图3　sim表结构

如果启用了这个配置项，那么core在进行处理的时候，会调用SIM来进行代码相似度的检测，并将结果更新至sim表中.

Core中使用SIM去进行代码相似度检测的关键代码如下:

intget_sim(intsolution_id,intlang,intpid,int&sim_s_id) {

charsrc_pth[BUFFER_SIZE];

//charcmd[BUFFER_SIZE];

sprintf(src_pth, "Main.%s",lang_ext[lang]);

intsim=execute_cmd("/usr/bin/sim.sh%s%d",src_pth,pid);

if(!sim) {

execute_cmd("/bin/mkdir../data/%d/ac/",pid);

execute_cmd("/bin/cp%s../data/%d/ac/%d.%s",src_pth,pid,solution_id,

lang_ext[lang]);

//ccppwill

if(lang== 0)

execute_cmd("/bin/ln../data/%d/ac/%d.%s../data/%d/ac/%d.%s",pid,

solution_id,lang_ext[lang],pid,solution_id,

lang_ext[lang+ 1]);

if(lang== 1)

execute_cmd("/bin/ln../data/%d/ac/%d.%s../data/%d/ac/%d.%s",pid,

solution_id,lang_ext[lang],pid,solution_id,

lang_ext[lang- 1]);

}else{

FILE*pf;

pf=fopen("sim", "r");

if(pf) {

fscanf(pf, "%d%d", &sim, &sim_s_id);

fclose(pf);

}

}

if(solution_id<=sim_s_id)

sim= 0;

returnsim;

}

当用户提交代码给服务器的时候，core读取配置文件，如果在配置文件中启用了SIM相似度检测，那么core在判题的过程中调用以上代码，调用/usr/bin/sim.sh来进行代码相似度的检测，当发现是抄袭的代码时，讲结果记录到数据库中.

3　实验结果

在实验过程中，我们将已经通过的代码进行如下的“抄袭”的处理.

已经通过的代码：

#include

intmain()

{

inta[5],i,j,max;

for(i=0;i<5;i++)

{

scanf("%d",&a[i]);

}

for(j=0;j<5;j++)

{

for(i=0;i<5-j-1;i++)

{

if(a[i]>a[i+1])

{

max=a[i];

a[i]=a[i+1];

a[i+1]=max;

}

}

}

for(i=0;i<5;i++)

{

printf("%d",a[i]);

}

printf(" ");

return0;

}

我们对已经通过的代码进行两次处理,处理过的代码一在其基础上修改了变量的名称，结构没有变，预测是完全抄袭；处理过的代码二在其基础上修改了变量名以及程序的结构，预测属于部分抄袭.

将处理过的代码提交给OJ系统，web端显示的结果如下：

然后查看数据库中的sim表中的记录：

可以很清楚的看出处理过的代码一的相似度是100，处理过的代码二的相似度是92，结果是比较准确的.

由结果可以得出结论，在HUSTOJ中，SIM可以有效的去对用户提交上来的源代码进行相似度检测！

4　结束语

通过对OnlineJudge中所采用的反作弊机制的

分析， 以及实验模拟， 可以看出SIM代码相似度检测软件可以很好的去解决用户在使用OJ的过程中存在的抄袭现象，可以有效的减少抄袭现象的发生.

[1]陈荣钦,胡永良,应建健,郭贤海. 在线评测系统中的源码相似度检测研究与实现[J]. 实验技术与管理,2014(4):109-111.

[2]张浩斌. 基于开放式云平台的开源在线评测系统设计与实现[J]. 计算机科学,2012(S3):339-343.

[3]DickGrune.http://www.dickgrune.com/[EB/OL].

[4]胡正军. 程序代码相似度检测方法研究及应用[D].中南大学硕士学位论文,2012.

[5]庄奇东,王键闻,张楠,张爽,任娜.OnlineJudge系统的优化[J]. 计算机系统应用,2011(8):115-121.

ResearchandImplementofAnti-copyingMechanismonOnlineJudge

WANGNing,LIRun-dong

(CollegeofComputerandCommunication,HunanInsitituteofEngineering,Xiangtan411104,China)

Theanti-copyingmechanismofOnlineJudgecandetectthecheatinginOnlineJudgeduringtheusage.Tostudythetheoryofanti-copyingmechanism,thisarticleusesHUSTOJastheresearchobjecttoanalyzetheoperatingmechanismoftextsimilaritytesterSIMinthesystemandthewayofachievingit.TheresultofexperimentshowstheeffectivenessoftextsimilaritytesterSIM.

OnlineJudge;anti-plagiarism;HUSTOJ;SIM;similaritydetection

2015-09-28

湖南省教育厅普通高等学校教学改革研究项目(湘教通[2014]247-414).

王宁(1982-),男,讲师,研究方向:无线网络及应用.

TP393

A

1671-119X(2016)01-0045-04