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

发布时间：2017-08-31 18:12

  本文关键词：程序代码相似性度量方法研究

  更多相关文章： 相似性度量 GST算法 token特征串 抽象语法树 抄袭检测

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

• 摘要2-3
• Abstract3-7
• 第一章 绪论7-11
• 1.1 研究背景及意义7
• 1.2 国内外研究现状及其分析7-9
• 1.2.1 国外研究现状7-8
• 1.2.2 国内研究现状8-9
• 1.2.3 研究现状分析及发展趋势9
• 1.3 本文的主要工作9-10
• 1.4 本文的组织结构10-11
• 第二章 程序代码抄袭检测研究概述11-18
• 2.1 代码抄袭种类描述11-12
• 2.2 相似性度量相关概念12-13
• 2.2.1 相似度定义12-13
• 2.2.2 抄袭检测概念13
• 2.3 相似性度量技术概述13-15
• 2.3.1 属性计数法14
• 2.3.2 结构度量法14-15
• 2.3.3 其他方法15
• 2.4 现有的相似度检测系统15-17
• 2.4.1 Plague系统15-16
• 2.4.2 MOSS系统16
• 2.4.3 SIM系统16-17
• 2.4.4 JPlag系统17
• 2.5 本章小结17-18
• 第三章 字符串匹配算法比较和改进研究18-28
• 3.1 基本概念18
• 3.2 Knuth-Morris-Pratt算法18-19
• 3.3 Longest Common Subsequence算法19-20
• 3.4 动态程序设计20-21
• 3.5 Rabin-Karp算法21
• 3.6 Greedy String Tiling算法21-23
• 3.7 对GST算法的改进23-27
• 3.8 本章小结27-28
• 第四章 基于抽象语法树的程序代码抄袭检测28-39
• 4.1 抽象语法树概述28-29
• 4.1.1 抽象语法树28
• 4.1.2 本文研究抄袭检测流程28-29
• 4.2 代码预处理29-30
• 4.3 生成抽象语法树30-37
• 4.3.1 算法描述30-31
• 4.3.2 算法实现结果31-34
• 4.3.3 数据存储结构描述34
• 4.3.4 AST算法及存储结构分析34-37
• 4.4 相似性度量37-38
• 4.5 本章小结38-39
• 第五章 相似度检测的实验与结果分析39-47
• 5.1 实验环境和实验数据39-40
• 5.1.1 实验环境39
• 5.1.2 实验数据39-40
• 5.2 实验结果分析40-46
• 5.2.1 源程序与待检测程序检测结果分析40-43
• 5.2.2 测试集任意两程序匹配检测结果分析43-46
• 5.2.3 实验数据说明46
• 5.3 本章小结46-47
• 第六章 总结与展望47-48
• 6.1 总结47
• 6.2 展望47-48
• 致谢48-49
• 参考文献49-52
• 作者简介52
• 攻读硕士学位期间研究成果52-53

【参考文献】

中国期刊全文数据库 前6条

1 赵长海;晏海华;金茂忠;;基于编译优化和反汇编的程序相似性检测方法[J];北京航空航天大学学报;2008年06期

2 张鹏;王国胤;陶春梅;罗海;;基于本体粗糙集的程序代码相似度度量方法[J];重庆邮电大学学报(自然科学版);2008年06期

3 于海英;;字符串相似度度量中LCS和GST算法比较[J];电子科技;2011年03期

4 熊浩;晏海华;赫建营;赵长海;;一种基于静态词法树的程序相似性检测方法[J];计算机应用研究;2009年04期

5 张丽萍;刘东升;李彦臣;钟美;;一种基于AST的代码抄袭检测方法[J];计算机应用研究;2011年12期

6 张文典,任冬伟;程序抄袭判定系统[J];小型微型计算机系统;1988年10期

中国硕士学位论文全文数据库 前4条

1 王继远;一种用于软件作业评判系统的程序结构分析算法的设计与实现[D];北京邮电大学;2007年

2 侯敏;程序代码复制检测中特征串提取技术研究[D];内蒙古师范大学;2009年

3 赵彦博;基于抽象语法树的程序代码抄袭检测技术研究[D];内蒙古师范大学;2010年

4 胡正军;程序代码相似度检测方法研究及应用[D];中南大学;2012年

，

本文编号：767117