基于代码相似性算法的敌对题发现问题研究

肖崇星，李 郴，曹晓洒

（中国矿业大学（北京） 机电与信息工程学院，北京 100083）

基于代码相似性算法的敌对题发现问题研究

肖崇星，李 郴，曹晓洒

（中国矿业大学（北京） 机电与信息工程学院，北京 100083）

试卷中可能出现的敌对题问题，是影响试卷质量的一个重要因素，针对这一问题，文章在分析了C语言试卷中读程序题和编程题的特点及研究了常用程序代码相似性检测算法的基础上，给出了一种基于抽象语法树的敌对题发现算法，希望能较好地解决C语言自动组卷系统中出现的敌对题问题，从而进一步提高C语言自动组卷系统的组卷质量。

敌对题；代码相似性检测；抽象语法树

伴随着互联网和计算机新技术的发展，越来越多的教学环节向电子化和网络化转变，其中传统的手工出卷方式变成利用计算机技术自动生成试卷就是一个普遍的现象[1]。利用计算机组卷不仅减少了教师的工作量，而且提高了试卷评判环节的公平性。因此自动组卷系统目前已成为评价计算机教育资源管理系统好坏的重要标志，然而在组卷系统生成的试卷中，有时会发生敌对题问题，敌对题问题也叫“相互提示”问题，就是同一套试卷中若出现某一道试题的题目对另一道试题要求做答的答案产生提示性作用，就认为这套试卷中出现了敌对题的问题。针对上述问题，本文提出了基于抽象语法树的敌对题发现算法，希望能较好地处理C语言试卷中读程序题与编程题易出现敌对题的问题。

1 敌对题问题简述

敌对题问题是伴随着试卷的产生而出现的，前期人工组卷时可以人为尽量避免敌对题的出现，但随着计算机组卷逐渐代替人工组卷后，较多组卷算法对敌对题问题解决得不是很好，敌对题问题在试卷中出现的概率较高，并且由于组卷算法在其他方面的不断优化改进，使其在解决组卷过程中的其他问题比如知识点均匀分布，重难点分布等的效果有较大提高，从而使敌对题问题与组卷质量之间的矛盾日趋明显。

敌对题是组卷系统在组卷后期产生的一个问题，其特点如下：

（1）同一份试卷中一道试题的题目和另外一道试题的答案相似或者相同。

（2）同一份试卷中一道试题的题目内容对另外一道试题的答案产生了功能性的提示作用。

2 程序代码相似性检测常用算法

目前对于程序代码相似性的检测算法主要有基于属性计数的相似性检测算法和基于结构度量的相似性检测算法以及这两种相似性检测算法相结合的检测算法[2]。本章研究程序代码相似性检测算法，目的在于对C语言自动组卷系统生成的试卷中读程序题的代码与编程题的答案代码进行相似性分析，以检出试卷中可能出现的敌对题。

2.1 基于属性计数的相似性检测算法

基于属性计数的检测方法主要是从源代码中抽取出各种度量元素，如关键字、操作符数、循环数等，不考虑程序的内部结构。HALSTEAD提出的软件科学度量方法是最早和最典型的属性计数法，它从程序中提取出数个软件度量特征，并使用这些特征来比较程序，其提出的属性计数法中统计如下4个属性。

N1=所有操作符的总数；N2=所有操作数的总数；n1=操作符的种类数；n2=操作数的种类数。则定义程序的长度为N=N1+N2和词汇量n=n1+n2，在此基础上得到程序的容量V如下：V=Nlog2（n）。

最后得到HALSTEAD特征向量，即H（n，N，V）。通过计算2个特征向量的欧几里得距离即可获得其相似度。计算公式如下：D=sqrt（（n1-n2）2+（N1-N2）2+（V1-V0）2）。

欧几里得距离越大，表明要比较程序之间的差别性越大，反之则表明程序之间差别性越小，2个相同程序的相似度为0。

2.2 基于结构度量的相似性检测算法

因为属性计数法中比对结果的抽象，不能得到具体的相似地方，而且它没有考虑程序的结构内信息，若是改变了源程序的结构，这种程序比对方式的效率就会低下。而基于结构度量的相似性比对方法则要对程序的内部结构进行检测分析，如分析程序的控制结构、计算程序代码的嵌套深度、查找程序间数据的依赖情况等，之后通过文本分析，将程序代码处理成标记串。最后，相应的程序代码将变成一个字符串，之后采用串匹配算法比对得到的字符串，再依据比对的结果来决定要比对的程序是否相似。

2.3 基于属性计数的相似性检测算法与基于结构度量的相似性检测算法的结合

随着对相似性代码检测算法研究的不断深入，一些学者提出了将上述两种算法相结合的方法，并相继开发出了一些系统，比如Donaldson开发的相似性度量系统，但是两种相似性检测算法相结合的技术，最后阶段的相似性计算大多还是利用结构度量检测算法中串的比较方法或者是对它的改进方法，比如胡正军[3]、张丽萍等[4]用贪婪式字符串匹配算法来计算字符串之间的相似性问题，张鹏[5]采用的是最长公共子序列法等，从而时间或空间的开销相对也较大。

综上所述，基于属性计数的检测方法因为没有考虑到程序的结构内部信息，而使检测算法的效果相对较低。而基于结构度量的相似性检测方法和两种算法相结合的方法都要对程序的内部结构进行分析比对，将程序转换成标记串，然后按照串匹配的算法比对这些标记串，虽然相对提高了程序比对的精确度，但由于它们很大一部分是利用字符串匹配算法来计算源代码标准化产生的标记串的相似度，从而增加了空间和时间的开销。

针对上述情况，本文提出了一种基于抽象语法树的敌对题发现算法，其主要思想是在结构度量的相似性检测算法程序标准化步骤中采用抽象语法树作为程序的中间表示形式，将源代码进行转换，之后引入了空间向量模型[6]的思想，求其待比较程序的抽象语法树属性，最后采用编码理论中的汉明距离概念，由汉明距离编辑公式，获得一种新的计算代码相似性方法。

3 发现敌对题的设计策略

在C语言试卷发现敌对题的过程中，首先是把需要比对的试题程序代码进行语法分析而获得其相应的语法树，对获得的源程序的语法树结点进行分类统计计算，根据二进制逻辑加法运算统计语法树的结点属性向量，之后求取两个向量的汉明距离，最后通过汉明距离值/n与预设阈值的比较判定同一套试卷中读程序题的代码是否与编程题的答案代码相似。如果两个向量的汉明距离值/n大于预设阈值时，就认为这两道试题是敌对题的可能性较大。

其主要流程如图1所示。

图1 敌对题发现流程

3.1 程序代码预操作

预操作部分是指待检测程序文本在生成抽象语法树之前，对程序源代码进行去噪和等价结构的一致化。去噪是指将源程序代码去除掉所有的注释部分和程序代码中空的行，将多个连续的空格变成一个空格，等价结构的一致化是指将语义上等价的语句进行相关的统一化。针对C语言为例，其主要有以下几个方面：

（1）去掉程序中所有在符号“//”之后，“/* */”之间的程序注释内容。

（2）去除掉程序中存在的空行并将多个连续的空格变成一个空格。

（3）在保证语义的情况下，对能等价替换的语句进行统一化处理，如将i++和++i等替换为同一种形式等。

（4）将do-while和for这种功能相似的结构转换成同一种循环结构，switch-case结构转换成if-else判断结构等。

3.2 语法树结点的选择和生成

抽象语法树中的结点也就是后期程序的特征属性，这里我们可以选择以下结点[声明变量，常量，标识符，表达式语句，条件语句，循环结构,结构体及其数组，过程及函数等]来表示语法树的每个结点，父类结点的属性向量是其全部子类结点的属性向量的逻辑加法运算和。

3.3 特征向量提取及频度计算

在得到相应试题程序的抽象语法树后，就要针对相应的文件来提取里面的结构信息。这里是从该语法树中提取其相应的结点作为其特征向量属性，其结点为[声明变量，常量，标识符，表达式语句，条件语句，循环结构,结构体及其数组，过程及函数等]，得到如下两个特征向量。

表示待检查试题程序p和已有试题程序d的特征属性向量，其中wk和qk的值为0或1，0表示程序在这分量位置上的属性是没有的，1表示程序在这分量位置上的属性是有的，反之也可以类似决定。

3.4 相似度的计算

得到要比较代码的特征向量后，需要进行相似度的计算，在计算阶段采用汉明距离的计算公式，经过上一步得到相应语法树的特征向量如下，只是wk和qk的值为0或1。

和qk分别表示读程序题对应的特征向量p和编程题的答案对应的特征向量d中第k位的属性分量，要么为1，要么为0，⊕就是模2加运算。对于计算机中，模2加运算非常方便，运算速度非常快，时间复杂度有明显的降低。

用上述公式计算程序代码相似度是准确的，因为，它计算得出的数值在0～1之间，当两段程序代码完全相似时，sim(p,d)的值为1，当两段代码完全不相似时，sim(p,d)的值为0，准确地呈现出程序代码之间的区别，并且也同向量夹角余弦的计算原理相同。由此计算两段程序的抽象语法树相似度就可判断两段程序是否相似，若计算结果大于预设阈值，则认为这两段程序相似性的概率大。

3.5 判断是否为敌对题

根据得到的值来与相应的阈值进行比较，若结果大于等于预设阈值，则可以认为试卷中这两道试题是敌对题的可能性比较大，结合敌对题的另一个特点，分析其编程题的代码结构，从中提取出功能语句，与读程序题得到的功能语句进行比对得到一个值，最后对其两个值求其期望值，若最后的值大于等于阈值，就可认为其为敌对题，之后就需要替换试卷中的一道试题，以保证组卷质量。

4 结语

本文以组卷系统在生成的试卷中易出现敌对题问题为出发点，针对C语言自动组卷系统在组卷后期读程序题和编程题较易出现相互敌对的问题进行分析研究，设计了一个基于抽象语法树的敌对题判断模型，目的在于检出C语言试卷中的敌对题，从而提高C语言自动组卷系统的组卷质量。

[1]陈蕾.基于遗传算法的自动组卷系统研究与应用[D].成都：四川大学，2006.

[2]BAKER B S，GIANCARLO R. Sparse Dynamic Programming for Longest Common Subsequence from Fragments[J].Algorithms，2002（2）：231-254.

[3]胡正军.程序代码相似度检测方法研究与应用[D].长沙：中南大学，2012.

[4]张丽萍，刘东升，李彦臣，等.一种基于AST的代码抄袭检测方法[J].计算机应用研究，2011（12）：4616-4620.

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

[6]汪忠国，吴敏.基于向量空间模型的题库相似度检查算法[J].计算机系统应用，2010（3）：213-216.

Research on hostile problem detection based on code similarity algorithm

Xiao Chongxing, Li Chen, Cao Xiaosa
（Mechatronics and Information Engineering College of China University of Mining and Technology, Beijing 100083, China）

Hostile questions may appear in the test, which is one of the important factors affecting the quality of test paper, aiming at this problem, based on analyzing the characteristics of reading questions and programming questions C language test and researching the commonly used code detection based similarity algorithm, this paper gave an algorithm for discovering hostile items based on abstract syntax tree, in order to solve the problem of C hostile language automatic test system of the test paper, so as to further improve the quality of the C language automatic test system.

hostile question; code similarity detection; abstract syntax tree

肖崇星（1990—），男，河南驻马店，硕士研究生；研究方向：数据挖掘。