散列处理把源程序经过词法分析生成的token序列的各个子串映射为比本身短得多的散列值, 相同的子串得到同样的散列值。采用“ hashpjw” 散列算法能够尽可能地避免不同子串产生相同的数字序列, 从而把字符串的匹配问题转换为整数的匹配问题, 进而通过BIDE挖掘算法挖掘出相同的数字序列。采用“ hashpjw” 散列算法得到的数字序列示例如图2所示。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 采用“ hashpjw” 散列算法生成的数字序列实例Fig.2 Example of digital sequence mapped by “ hashpjw”

BIDE是一种采用双向扩展策略频繁闭合子集挖掘方法。前向扩展用于增加前缀模式并检查前缀模式的闭包, 后向扩展用于检查前缀模式的闭包并通过剪枝缩小搜索空间。因此与其他同类方法相比更为高效。BIDE及其子算法描述如下所示。

Algorithm:BIDE(SDB, min_sup, FCS)

输入:序列数据库SDB, 最小支持度阈值min_sup

输出:频繁闭合序列集合FCS

1.FCS=⌀;

2.F1← 频繁1模式序列;

3.foreach 频繁1模式 f1 in F1

4. SDB^f1← 为f1建立伪投影数据库;

5.foreach f1 in F1

6. 将f1作为前缀;

7. if(向后扫描不能将f1剪枝)

8. BEI← f1向后扩展事件的个数;

9. FCS← 调用bide算法产生闭合序列模式;

10.return FCS;

Algorithm: bide(S_p_SDB S_p, min_sup, BEI, FCS)

输入:投影序列数据库S_p_SDB, 前缀序列S_p, 最小支持度阈值min_sup, 后向扩展事件数BEI

输出:当前频繁闭合序列集合FCS

1.LFI← 扫描S_p_SDB找出S_p的本地频繁项;

2.FEI← S_p向前扩展项的个数;

3.if((BEO+FEI)==0)

4. FCS=FCS∪ {S_p}

5.foreach i in LFI

6. Spi← 用本地频繁项来增长S_p;

7. SD BSpi← 为 Spi建立伪投影数据库;

8.foreach i in LFI

9. 将 Spi作为前缀;

10. if(向后扫描不能将 Spi剪枝)

11. BEI← Spi向后扩展事件的个数;

12. FCS← 递归调用bide算法产生闭合序列模式;

13.return FCS;

本文应用BIDE算法, 从已经生成的序列数据库中查找支持度大于等于2的频繁序列, 这些频繁序列与程序之间的雷同代码相对应。识别出的学生程序间的一个雷同代码片段组实例如图3所示(其中, SEQ表示代码片段的数字序列, LEN表示代码片段的长度, SUP表示代码片段的支持度, FilePath表示代码片段所在程序的路径, Lines表示代码片段在程序中的所在行, RELAL表示代码片段在原程序函数中的行数)。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 BIDE算法挖掘出的雷同代码片段实例Fig.3 Example of similar code mined by BIDE

程序相似度的计算公式定义如下:

sim(A, B)=2×|A⋂B||A+B|1

式中:|A|和|B|分别为程序A和程序B中代码行数; A∩ B是经过BIDE挖掘算法后计算出的两个程序之间的相似代码行数; sim(A, B)是程序A和程序B之间的相似度值。

(1)统计每个源程序中的代码行数。

(2)计算程序之间相似代码的行数:对程序中的每行相似代码设置标志位, 若该行相似代码已经出现过, 则跳过处理, 否则继续处理, 从而得到程序中所有不重复出现的相似代码。

(3)计算程序之间的相似度, 查找程序之间对应的雷同代码:若计算出的sim(A, B)高于预定的阈值, 则认为程序A和程序B是雷同程序。

(4)排序算法:经过上述步骤(1)(2)(3)之后, 根据得到的程序之间的相似度, 按降序排序算法进行排序, 得到由高到底的雷同程序列表。

(5)输出雷同程序列表和相对应的雷同代码。

为了测试本文方法的检测效果, 选择5个实际的学生作业题目。这些程序已被第三方授课教师采用人工检测的方式确认了其中的雷同程序组。然而由于实际剽窃的程序组数有限, 本文还采用了人工注入的方式, 对每组题目由授课教师模拟学生常见的抄袭方式, 在已有程序的基础上进行修改, 如标识符重命名、插入和删除部分语句, 生成新的雷同程序组。最后将原程序和人工注入的程序集合统称为人工检测集合, 作为本实验的基准测试集, 如表1所示。分别采用MOSS和本文方法对每组程序进行雷同检测, 统计检测结果的误检率和漏检率。

表1

Table 1

表1(Table 1)

表1 基准测试集 Table 1 Benchmark 序号 题目 程序 个数 总代 码行 雷同组数 原有 注入 总计 1 最大公约数 45 1375 3 10 13 2 马克思手稿 41 698 1 8 9 3 数组最大值 28 922 3 10 13 4 字符串连接 33 962 2 9 11 5 成绩管理 69 2877 4 12 16

表1 基准测试集 Table 1 Benchmark

图4标注出来的代码为系统检测出的两程序之间对应的雷同代码, 雷同度为91.25%。

雷同检测结果的误检率和漏检率计算公式如下:

误检率=

|系统检测|-|系统检测⋂人工检测||系统检测|× 100%

漏检率=

|人工检测|-|系统检测⋂人工检测||人工检测|× 100%

式中:绝对值符号表示检测出的雷同程序组数; |系统检测∩ 人工检测|表示系统检测出基准测试集合中所提供的雷同程序组数。

根据实际经验, 由于初学者在程序设计时具有类似的实现思路, 并且常常需要使用指定的语法结构, 因此程序会存在一定的相似性。一般相似度为70%以下的程序组是雷同程序的可能性比较小。即使这些程序中可能存在剽窃, 也是经过了较大的修改, 加入了抄袭者自己的思考。因此, 本文重点分析MOSS和本文方法输出的相似度大于70%的雷同程序组, 结果如表2所示。表中∩ 表示|系统检测∩ 人工检测|。

由表2可以看出:两种方法对于相似度较高的代码均具有较高的准确性。对于相似度80%以上的雷同程序组的误检率为0。但是在实验中本文方法和MOSS均出现一次误检, 误检的两个程序比较类似于修改了的雷同程序, 而实际中是由相似的编程思路和编程风格导致的。对于这种相似度不是很高的雷同程序组而言, 教师最好进一步确认是否真正是雷同程序。但是对于相似度70%~80%的雷同程序组而言, 大多情况下是对抄袭程序进行了修改, 本文方法具有较低的误检和漏检。这是因为本文方法是在词法分析生成的token序列的基础上进行分析和BIDE挖掘的, 可以有效检测各种标识符重命名、插入和删除了部分语句的雷同代码片段。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 检测出的一组雷同程序实例Fig.4 Example of plagiarized programs

表2

Table 2

表2(Table 2)

表2 本文方法与MOSS的误检率和漏检率 Table 2 False positive rate and false negative rate of our method vs MOSS 程序组 方法 ≥ 90% 80%~89% 70%~79% 总计 误检率/% 漏检率/% 系统 ∩ 系统 ∩ 系统 ∩ 系统 ∩ 人工 1 本文 5 5 5 5 3 3 13 13 13 0 0 1 MOSS 5 5 4 4 4 4 13 13 13 0 0 2 本文 6 6 3 3 0 0 9 9 9 0 0 2 MOSS 6 6 3 3 0 0 9 9 9 0 0 3 本文 6 6 6 1 1 13 13 13 0 0 3 MOSS 6 6 4 4 1 1 11 11 13 0 15.38 4 本文 4 4 4 4 3 3 11 11 11 0 0 4 MOSS 4 4 4 4 3 3 11 11 11 0 0 5 本文 5 5 6 6 6 5 17 16 16 5.88 0 5 MOSS 5 5 6 6 5 4 16 15 16 6.25 6.25

表2 本文方法与MOSS的误检率和漏检率 Table 2 False positive rate and false negative rate of our method vs MOSS