程序代码相似性度量方法研究

摘要

计算机信息技术的飞速发展，使得资源的获取和使用也变得更加的快捷方便。但与此同时，信息资源之间的抄袭也变得越来越简单和难以防范。例如在计算机的程序设计类课程中，进行程序作业完成提交及在线测试时，学生之间进行彼此抄袭的现象非常的普遍。这种现象严重影响了教学质量、制约了学生素质的提高发展，更加无法确保考核的公平公正性。此外，在软件商业领域中，软件产品发生版权争端的事件也时有发生。对程序代码相似性度量方法及其应用的进一步深入高效研究，将在很大程度上扼制在程序设计类课程中存在的普遍的抄袭现象，加大对软件商业领域中软件产品的知识产权保护力度。
　　本文分析了目前国内外在程序相似性度量领域的相关研究，对常用的相似性度量检测方法做了综合的对比分析。并在此基础上对程序代码相似性度量方法进行了以下的相关研究。首先，对于传统字符串匹配算法GST算法在进行串匹配时需要逐个比较串的每个字符、造成时间复杂度相对较大的问题，提出了一种基于Java多线程并行匹配的设计方式，以此对GST算法的匹配过程进行了改进，有效的提高了算法进行匹配检测的时间效率;然后，针对GST算法时间复杂度和参加检测匹配的字符串长度成正比的特点，对能够代表程序语义结构的token序列，提出一种设计思想:在对其语义没有影响的条件下对其长度进行缩短，可以进一步降低匹配的时间复杂度;最后，针对利用工具生成抽象语法树时会包含大量的冗余信息，容易造成资源的极大浪费的问题，设计并实现了一种构造抽象语法树的算法，该算法通过先创建父节点后创建子节点，再将其关联的方式，将程序中类、方法等体现程序语义结构的有用信息进行抽象语法树的构造，并且设计了类信息表和方法信息表进行数据的存储和更新，方便数据的使用。通过抽象语法树的算法设计，在构造生成语法树后，可以遍历解析语法树使其生成能够表示程序语义结构的token序列串，再结合改进的字符串匹配算法GST进行相似度的计算，得到最终的相似性度量分析结果。
　　根据上述的方法理论，本文设计并且实现了一个基于Java语言的程序代码相似度检测系统，该系统可以计算源程序对之间的相似度。在同等测试程序集和程序对的基础上和Moss系统的抄袭检测结果进行了对比分析。实验结果表明，本文的研究内容，可以有效的检测出大部分抄袭手段，并且具有较高的检测时间效率。在代码检测的精度和准确度方面都具有较高的可靠性。

目录

摘要

英文摘要

第一章 绪论

1．1 研究背景及意义

1．2 国内外研究现状及其分析

1．2．1 国外研究现状

1．2．2 国内研究现状

1．2．3 研究现状分析及发展趋势

1．3 本文的主要工作

1．4 本文的组织结构

第二章 程序代码抄袭检测研究概述

2．1 代码抄袭种类描述

2．2 相似性度量相关概念

2．2．1 相似度定义

2．2．2 抄袭检测概念

2．3 相似性度量技术概述

2．3．1 属性计数法

2．3．2 结构度量法

2．3．3 其他方法

2．4 现有的相似度检测系统

2．4．1 Plague系统

2．4．2 MOSS系统

2．4．3 SIM系统

2．4．4 JPlag系统

2．5 本章小结

第三章 字符串匹配算法比较和改进研究

3．1 基本概念

3．2 Knuth-Morris-Pratt算法

3．3 Longest Common Subsequence算法

3．4 动态程序设计

3．5 Rabin-Karp算法

3．6 Greedy String Tiling算法

3．7 对GST算法的改进

3．8 本章小结

第四章 基于抽象语法树的程序代码抄袭检测

4．1 抽象语法树概述

4．1．1 抽象语法树

4．1．2 本文研究抄袭检测流程

4．2 代码预处理

4．3 生成抽象语法树

4．3．1 算法描述

4．3．2 算法实现结果

4．3．3 数据存储结构描述

4．3．4 AST算法及存储结构分析

4．4 相似性度量

4．5 本章小结

第五章 相似度检测的实验与结果分析

5．1 实验环境和实验数据

5．3．1 实验环境

5．1．2 实验数据

5．2 实验结果分析

5．2．1 源程序与待检测程序检测结果分析

5．2．2 测试集任意两程序匹配检测结果分析

5．2．3 实验数据说明

5．3 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

致谢

参考文献

作者简介

攻读硕士学位期间研究成果

声明