基于后缀语法树的代码抄袭检测研究

摘要

随着信息技术的不断发展，抄袭正变得越来越容易和难以防范。在程序设计类课程作业和在线测试的考评中，学生相互抄袭的现象也普遍存在。澳大利亚蒙纳什(Monash)大学对其学生中的代码抄袭现象进行调查统计显示：高达85.4％的学生承认抄袭过他人的作业。日益严重的抄袭现象已经严重地破坏了正常的教学秩序，也影响了教学质量和学生素质的提高。为了扼制不良学风，对高效率的代码抄袭检测方法进行研究显得日趋必要。
　　 本文在分析目前国内外程序代码抄袭检测研究的基础上，针对学生C语言程序代码作业中常见的抄袭方法，提出一种基于后缀树的程序代码抄袭检测方法。首先制定基于ANTLR的C语言文法文件，利用ANTLR生成C语言的词法及语法分析器，并对程序代码进行词法和语法分析，生成C程序代码的后缀语法树。其次对生成的后缀语法树进行遍历和优化，去除语法树中的冗余信息，得到一个字符串序列，该字符串序列标准化地表示了程序代码中的信息。第三，采用改进后的贪婪字符串匹配算法，对后缀树字符串序列进行了匹配计算，通过一个确定了决策函数计算出两个字符串序列的相似值，并以此为依据来度量两个程序代码之间相似程度。最后根据给定的阈值来判断两个程序之间是否存在抄袭嫌疑。
　　 基于上述方法，设计并实现了一个C语言程序代码抄袭检测实验系统，该实验系统可以检测程序集合中任意两个程序代码之间的相似度。选用了不同的方法对实验系统的有效性和可靠性进行测评。实验结果表明，该方法能够检测出C语言代码中存在的多种抄袭手段，并有较高的检测效率。与国外成熟的的检测系统MOSS对比，该实验系统在检测精度和准确性方面都有较高的优越性和可靠性。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景及意义

1.2 国内外研究状况和发展趋势

1.3 本文的主要工作

1.4 本文的组织结构

第二章 背景知识与相关研究

2.1 抄袭检测技术概述

2.2 程序代码抄袭手段分析

2.3 代码抄袭检测相关概念

2.3.1 相似性和相似度

2.3.2 代码抄袭检测技术分类

2.4 字符串匹配常用算法

2.5 现有的抄袭检测系统

2.5.1 Plague系统

2.5.2 YAP系列

2.5.3 SIM系统

2.5.4 MOSS系统

2.5.5 JPlag系统

2.6 本章小结

第三章 基于后缀语法树的代码抄袭检测方法

3.1 检测模型

3.2 源代码的形式化

3.2.1 ANTLR介绍

3.2.2 ANTLTR生成的后缀语法树

3.2.3 制定文法文件

3.3 语法树的遍历和优化

3.3.1 消除冗余和干扰信启

3.3.2 缩短后缀语法树字符串序列的长度

3.4 对GST算法的改进

3.4.1 算法选择

3.4.2 GST算法相关概念

3.4.3 GST算法描述

3.4.4 面向ANTLR生成的后缀语法树对GST算法的改进

3.5 相似性计算

3.6 阈值的选取

3.7 本章小结

第四章 抄袭检测系统的设计与实现

4.1 设计思路

4.2 系统设计框架

4.2.1 前期准备

4.2.2 系统框架

4.3 本章小结

第五章 系统测评

5.1 评价指标

5.2 实验数据的收集

5.3 本章小结

第六章 结束语

6.1 工作总结

6.2 不足之处与下一步的工作

参考文献

攻读学位期间发表的论文

致谢