【毕业学位论文】（Word原稿）程序代码相似度比较的研究与实现-软件工程

中图分类号： 学校代码： 10055 密级： 硕 士 专 业 学 位 论 文 程序代码相似度比较的研究与实现 of 摘要 摘 要 对计算机和有关专业来讲，计算机程序设计课程是一门非常重要的课程，我们无法联想计算机专业的学生不会编程会怎么样，因而对计算机和有关专业来说，程序设计课程的均显得非常重要。在程序设计的课程中，实际编程实力非常重要，为 了升高同学的编程实践能力，同时为后续课程的研习和为今后步入社会打下坚固的根蒂，要求学生能够独立的完成老师布置的相关编程设计作业。但是在教学过程中，我们发现由于计算机数据的易复制性及互联网搜索的便利性，为了完成程序设计作业，部分学生采取搜索、抄袭他人代码的行为。这种行为不但不利于学生的成长，同时也对成绩考核的公平性产生一定的影响。于是我们策划了一个用于检测代码相似度的系统，该系统具备深入的使用价值，在教学中能够辅助教师检测学生提交的功课是否存在剽窃行为 ,在现实生活总可以用来对软件版权的进行鉴定。 程序代码相似 度的比较，指的是在现实生活中，检测手段的使用，这两项措施的程序源代码之间的相似程度， 并根据相似程度判别标准来判断两个程序的源码是否存在抄袭行为。 本文研究了检测 首先通过对源属性类型，和类似的代码类型特征，相似性评估标准及源程序的分析和研究，预处理，设计了一种利用 来比较的相似性，在两个源文件的结构。使用该系统检测代码相似度，可以大大的提高教学考核的工作效率。 本文采用 用面向对象的功能模块化设计，基于结构的测量，设计和开发的文件读取模块，预处 理模块，相似性检测和结果输出模块四大模块。界面简洁、友好，检测结果按相似的排名和保存在指定的文件。 关键词： 检测 代码相似性 ;预处理 ;结构度量 ; 法 or of a is a we of in is in to of of a to we as be in to It is to of on of So we a of of in to in be of in of of of to of to of of of by of of CS to a to in of to we of of . is in a in 录 目 录 摘 要 . . 1 章 绪 论 . 1 开发背景 . 1 研究目的及研究意义 . 2 程序代码相似度检测技术的研究现状 . 3 国外研究情况 . 3 国内研究情况 . 3 目前主流的程序代码相似度检测系统 . 4 论文组织简介 . 5 章小结 . 5 第 2 章 程序代码相似度检测的理论基础 . 6 相关概念的引入 . 6 程序抄袭描述 . 6 代码相似度定义 . 8 程序相似代码的分类和掩饰性行为 . 9 从源代码单个语句方面讨论相似代码的分类 . 9 从内容和功能两个方面研究相似代码的分类 . 10 识别相似代码的一般方法 . 11 已被成功运用的识别方法 . 11 从整体上判断代码相似的方法 . 12 相似度度量算法的研究 . 13 属性计数技术 . 13 结构度量技术 . 15 目录 散列值匹配算法 . 18 章小结 . 20 第 3 章 程序代码相似性识别方法的研究 . 21 标代码相似性的识别 . 21 于 法的识别方法 . 22 于加权属性相似的识别方法 . 23 权属性识别方法的理论依据 . 23 代码相似度计算 . 26 章小结 . 28 第 4 章 程序代码相似度检测系统的分析与设计 . 29 运行流程 . 30 流程说明 . 30 软件架构 . 31 文件读取模块 . 31 预处理模块 . 31 似代码检测模块 . 33 相似度计算模块 . 35 结果输出模块 . 35 章小结 . 36 第 5 章 程序代码相似度检测系统的实现 . 37 开发环境与开发平台 . 37 开发环境 . 37 开发平台 . 37 程序代码相似度检测的实现技术 . 37 术的优点 . 37 术的开发框架 . 38 程序代码相似度检测系统各功能模块的实现 . 39 目录 文件读取模块 . 40 程序代码预处理模块 . 40 相似代码检测模块 . 41 相似度计算模块 . 42 结果输出模块 . 42 章小结 . 43 第 6 章 程序代码相似度检测系统的测试与运行 . 44 代码预处理的测试 . 44 法的检测 . 45 直接递归法和动态规划法求最长公共子序列的效率分析 . 45 检测结果分析 . 49 检测精度分析 . 49 系统界面 . 54 试结果综合分析 . 54 章小结 . 55 第 7 章 结论与展望 . 56 论 . 56 望 . 56 章小结 . 57 参 考 文 献 . 58 致 谢 . 60 个人简历 . 错误 !未定义书签。 在学期间发表的学术论文与研究成果 . 错误 !未定义书签。 第 1 章 绪论 第 1 章 绪 论 开发背景 信息技术的快速发展使得其 广泛 应用于教学中。作为信息技术的应用之一，程序语言平台的建立，一方面方便老师布置程序设计的作业和考试，以及提高教师批改作业的效率，另一方面有助于学生学习过程中不断练习，提高编程能力。然而，正是由于信息技术的快速发展，学生从互联网上获得相应程序资源的便利性不断增加 ，再加之适当的修改， 这使得查重的难点不断增大。 所以我们需要创造一个 新的检测系统，检测机构应结合现有的剽窃检测技术，结合程序抄袭是抄袭，要找到一个快速和精确的算法，并 依据该算法设计出具有实际应用价值的软件，能够检测精准的判断是否存在抄袭行为 。 因此， 本文的主要目的是根据具体程序语言的特征，设计并实现整合程序语言的的支持平台，对学生提交的作业进行相似度查重，从技术层面减少学生抄袭的可能性。 在本文中，检测代码相似度的 系统 主要 针对 该检测系统的主要原理是：先将要检测的代码和参照的代码输入系统，通过系统 计算出的两段程序源代码的相似度值 ， 根据系统设计的相关评价标 准来判断两个程序语言是否存在抄袭。如果两个程序的相似度较高，则抄袭的可能性越大。 我们平时进行交流的语言属于自然语言。由于自然语言灵活多变的特征，构成自然语言的词汇较大，不同词汇的组合形成不同的意思表达。即便是同一语言，由于所处语言环境的不同，其代表的含义也会存大很大差别。因此，对自然语言进行查重是十分困难的。与自然语言相比，程序语言有固定的语法规则，编写结构相对简单。正是由于程序语言独特的特征，检测其源代码相对容易些。 随着国内外对程序语言的相似度检测研究的不断深入 ， 已经出现一些相对成熟的检测系统 。 目前， 关于源代码的相似度检测技术大致分为两类：度量结构技术和属性计数技术。 属性计数技术 并不考虑程序的设计流程结构 ,而是对 程序源第 1 章 绪论 代码的一些属性 进行统计 计数 , 因而该方法能够有效的检测出两源码文件是否为存在拷贝（ 为，但是抄袭者一旦修改拷贝的程序源码 ，例如添加一些 无用的注释代码 、 无用变量 等，其检测 的 准确性就会大大降低 ，因此很难得出正确的结论 。 而结构度量技术 主要是通过对两组源代码的结构的相似性进行分析，得出的检测结构更为真实可靠。 基于此，目前关于源代码相似度检测技术主要采用结构测量技术。 结构测试技术 检测源代 码相似度 的工作原理如下： 首先，基于检测的程序代码进行预处理的需要，消除冗余代码不影响相似性度量的结果， 如无用 空行、 空格、注释语句等 ， 然后按照语法转换规则预处理代码，将其转变为包含程序结构信息的字符串，最后通 常 法等 字符串匹配算法处理标记字符串。从此过程中我们可以看出转换规则的重要性，但是我们也应该注意字符串匹配算法并不能包含全部的程序源码的结构信息。 目前大多数程序代码抄袭检测系统都使用了结构度量技术方法。 该方法仅能够 对 部分完全独立编写的程序 进行检测 ,但 却不能正确识别 一些代码抄袭的投机行为 ， 如在程序中 添加一些无用的赋值代码和变量 。 这些修改无须花费太多精力却可以成功混淆代码段，使得按照字符串匹配算法计算出来的相似度较小，从而不能达到检测相似度的目的。 本研究将依据程序代码相似度检测基本理论 ,并从何利用属性计数计数、结构度量计数和散列值匹配算法来计算相似度。 研究目的及研究意义 在计算机教学过程中，负责批阅作业的老师在批阅过程中总是要面对大量的程序代码 ，工作强度较大，并且人工检测由于自身局限（如效率低下或者疲劳）容易出现相似度难以检测出等情况 。部分学生 出于种种原因 ，基于计算机数据的易复制性及互联网 搜索的便利性， 在完成程序设计作业时采取搜索、抄袭他人代码的行为 。该行为不仅不利于成绩考核的公平性，也不利于学生熟练掌握知识。 本文的研究目的 在 于设计并 实现一个程序源码相 似度检测的系统，通过检测学生提交的编码课程作业与给定答案的接近程度， 检测是否存在抄袭行为 。并且，通过度量技术实现程序的自动校第 1 章 绪论 正。 程序代码相似度检测技术的研究现状 国外研究情况 最早的检测程序代码相似度检测和优化是重复的代码，在第二十世纪70 年代，霍尔斯特德代码抄袭和重复性的行为提出了一种软件科学指标检测方法 ， 霍尔斯特德 方法基于属性计数法的工作原理，将程序中的操作数和操作符作为计数目标，将计数结果作为标准。再此基础上， 现了第一个针对 码的检测系统。随后， 结构最典型的测量方法是圈复杂度 方法 ， 该方法 由 心思想是：通过执行路径数的计算控制程序流的测量。由于圈复杂度提供了一个程序 控制流 ，如果 在编写代码相似度检测系统时 仅依据该原理则会 产生极低的 检测正确率， 因此，在实际应用中结合其他特征。 在实际 应用中，往往 采用 结构度量法与属性计 数法 相结合 的方法。 最近开发的代码的防抄袭系统主要工作原理的基础上，比较的源程序，如结构表达式字符串：苔藓，鼠疫， ，狂吠， 列等。 国内研究情况 1998 年初，中国人民警官大学发展了 序抄袭判定系统用以检测 序的相似性 。 为了保证检测的正确性 ，将 言结构 按 性质分为四类：可变类，控制类，标准的过程和算子类。 首先，检测 统计模块统计程序的各种性质。 在统计比较模块，比较模块四个一般属 性的程序比较的属性的值，如果总的值非常接近，两个程序可能是类似的，称为“类似”的标记。结束后的总资产价值的比较，每个属性是一个类似于可能的值的过程中，如果标准差小于两个程序对应的属性的属性的比较结果，属性值和其相应的权重的总和。 按照上述形式依次比较程序的全部属性，计算出属性值 比较属性的个数除以 2006 年，内蒙古师范大学 在辨别程序代码相似度的科学研究中，使用第 1 章 绪论 了空间向量的间隔公式来计算程序代码的相似水平。但是，这个研究没有考虑各个属性之间的关系和重要性，忽略了很 多有用的信息，从而使得相似度检测的精度和准确度大大降低，有待于进一步改善。 基于上述国内的研究现状，我们可以看出，国内程序相似度检测方面的研究相对较少。近年来，随着属性技术和程序结构相结合的新的检测方法的出现，出现了研究程序相似度检测研究的热潮。在研究方法上，有学者提出用神经网络的方法来检测程序的相似水平。 总之，目前的研究识别源代码相似度的方法并没有明显的创新，更是对检测和重复的代码优化方法的探讨，为识别代码的参考值的相似性。 目前主流的 程序代码相似度 检测系统 （ 1） 统 作 者是 该系统 可检测的编程语言 包括 C， C+， 系统在检测网页返回到用户。但由于作者没有说明该系统的技术的使用，所以我们不知道在所有的实现细节。 （ 2） 统 这 是 由 计实现的 。该系统在处理程序时，通过删除注释、大小写统一、替换同义词等步骤比较代码的相似度。该系统不同版本所使用的程序检测算法也存在不同。 （ 3） 统 本 系统 是 由 、 和 计实现 ， 采用了 法 对代码的相似度进行检测，在相同的形式使用的相似性度量的软件，使用 言， ，目 前仅支持 C、 C+、 编程语言的检测。 （ 4） 统 由 计实现的 ，该系统的核心 思想是 衡量 序相似的序列检测串排列。 首先将 待检测的 程序源代码进行 预 处理， 使其排列为一种紧缩的格式 ，随后系统将其中 的一个紧缩串 进行 拆分 ，拆分 为若干份，然后，各部分的几份分割和另一个程序的紧缩字符串匹配后，不是因为这样的结构和语法规则 。 和编程语言 相比，该 算法能够 检测 大多数的语言。 第 1 章 绪论 论文组织简介 本论文共分为五个章节。 第一部分 主要 介绍了程序相似度检测系统开发的背景，国内外关于程序相似度检测的技术，并介绍了程序相似度检测的核心理念和算法。 第二部分主要讲述了 程序代码相似度检测的 相关概念和 工作理论，分析了 程序抄袭行为的 特点并对其进行分类 ，并介绍了 代码抄袭者常用的掩饰性行为，列举了 常用的检测相似代码的方法及工作原理， 并对其各类度量方法进行分类和详细介绍。 第三章给出了程序代码相似度检测系统的分析与设计 思路 ，对该系统的功能模块作了 简要 分析。 第四章主要是关于程序代码相似度检测系统的实现，分析了系统各功能模块之间的联系，并对每个功能模块作了详细的介绍。 第五章给出了该系统的运行界面和测试结果，并对各算法的运行效率作了比较。 章小结 本章 属于绪论 ， 主要介绍了本课题的研究背景和研究意义。 在此基础上 ， 对国内外的 程序代码相似度检测技术的 进行分析 ，通过分析本课题国内外 的技术和系统为本课题的研究提供研究思绪和 借鉴。 第 2 章 程序代码相似度检测的理论基础 第 2 章 程序代码相似度检测的理论基础 相关概念的引入 程序抄袭描述 程序语言课程随计算机技术的发展在高校越来越重视 ,不仅计算机专业的学生学习程序语言 ,其他专业 ,甚至是非工科专业也开展了程序语言的课程 ,比如应用非常广泛的 C 语言程序课程。除了 C 语言程序设计课程外 ,C+,C#等高级程序语言课程也非常流行。程序语言课程的作业主要是以编程的方式来锻炼学生的程序思维能力 ,这就不可避免的出现了代码抄袭的问题。 程序代码的运行必须严格遵守程序语言的规范 ,必须通过编译器的检测 ,这就使 得程序代码源文件一般都是以电子稿形式进行提交与检测 ,互联网技术的普及 ,电子资料下载的快捷性 ,让许多学生能够轻而易举的从网上搜索到相关代码 ,进而抄袭。抄袭代码不仅让老师的教学事倍功半 ,更让学生失去了自己学习程序语言的一个途径。很多学生进行抄袭的时候会或多或少的修改一部分文字来迷惑老师 ,同样 ,程序代码的抄袭也是如此。同时 ,由于程序代码不像普通文本那样没有特别的规范 ,程序代码的修改必须保证代码正确运行的前提下才有作用。这就造成了代码抄袭过程中抄袭程度的不同和检测难度级别的不同。 修改 他人程序分成了七个难度级别。如下图 示。 第 2 章 程序代码相似度检测的理论基础 图 袭程序代码修改的难度等级图 示不对源程序进行任何修改 ,这种抄袭最简单 ,不用费事 ,所以有不少抄袭属于这种情况。 示只修改了源程序的注释 ,这种抄袭也简单 ,因为修改注释肯定不会影响源程序的结果。 示修改了源程序的部分标示符 ,比如函数 ,宏 ,变量的名字 ,这种修改需要注意其他使用了这个标示符的地方也要做同样的修改 ,通过计算机的查找替换功能也较容易做到。 示修改程序变量声明的位置 ,这种修改需要注意的是修改了变量的位置后要保持程序的编译 正确并且结果也正确。 示用函数体代替函数调用 ,相当于减少函数 ,这种修改也需要验证编译和结果。 示修改程序语句 ,比如 i+变成 i+=l 这种等价替换。 示修改程序的控制逻辑 ,这种修改比较难 ,一般人也难以做到 ,抄袭者也很少这样去修改。 两种剽窃意味着更复杂的，如果有人这样做，这是语言的深层把握。 . 袭程度也给出了 10 个难度级别 ,基本和 盖的范围一样 ,只是给出了更细分的标准。 4*析了抄袭的一般 规律 ,总结出抄袭转换基本是由两类转换构成 :一第 2 章 程序代码相似度检测的理论基础 个是跟程序机构无关的词汇级修改 ,另一个是较复杂的结构级修改。 滨孙 认为从 词汇级的修改，结构级修改包括 在实际的教学实践中 ,学生一般都是初学者 ,大多抄袭的学生仅仅在词汇上下工夫 ,如果说去修改程序的结构 ,往往费时又费力 ,阅读别人的程序也不是件容易的事情 ,这样结构级修改还不如自己动手写新的程序。也有一种情况就是 ,通过参考别人写的程序再通过自己理解写出的程序可能和原来的程序有相似之处 ,但这种不应当看做是抄袭 ,这是一种实实在在的学习 过程 。所以抄袭的学生大多是前几个词汇层面的修改，这是比较容易检测。 代码相似度定义 相似度：用于评价两个源码之间相关程度。通过利用特殊的测试机制及方法，衡量源码的相似程度。一般用一个数值 ,=,0;iX=ij= cicj i,j0;X 假设输入序列为 X= 2,X m、 Y= 2,Y n。输出 数组 为： c， b， 中 bij表示 求得 cij值 的 子问题 ， cij表示 j 的公共子序列的长度， h表示 问题的 最优解 。 法的模式匹配流程图如图 示。 第 4 章 程序代码相似度检测系统的分析与设计 图 法流程图 相似度计算模块 加权属性相似度计算模块包括属性统计和 计算属性 相似度 等功能 。其中 ，属性相似度计算模块 是由 性相似度计算模块 和 物理属性相似度计算模块组成 。加权属性相似度计算模块由显示区和操作区两部分构成 , 显示区 是显示 源代码和对应属性的区域 , 操作区则是针对所要识别的源代码进行操作 的区域 , 以 满足 识别源代码相似性的基本需求。 根据两个程序的最长公共子串，对两个程序进行相似度的计算，这项工作通过以下公式来实现： ,B) = (2*最长公共子序列长度 )/(A， B 文本的总长度 ) 结果输出模块 将结果按相似度的高低排序后写入指定的文件，以 便教师查看检测结果。 输入序列 X=2, ,序列 Y=2, ,cij=0 cij=c1 cij=cj,ci 开始 i=0 或 j=0 j 结束 i=m,j=n N N N Y Y Y 第 4 章 程序代码相似度检测系统的分析与设计 章小结 本 章是系统的分析和设计章节，本章是整个系统研究的重点章节，本章 分析了系统的运行流程以及对整个流程进行了说明， 划分了不同的功能模块，并对每个模块进行了设计。 第 5 章 程序代码相似度检测系统的实现 第 5 章 程序代码相似度检测系统的实现 开发环境与开发平台 开发环境 目前， 大多数学生 是在 境下进行 程序编译 、 调试和运行 。为了实用需要 ， 因此，本文 采用 P 操作系统作为程序相似代码识别系统的运行环境。 开发平台 本系统采用 作为开发平台。 程序代码相似度检测的实现技术 术的优点 一个 被普遍使用的网络汇编 语言 , 它 具有便捷 、面向对象、 可移植性、健壮性安全性等特点， 具有很高的性能。 简单性： 除了 C/C+中 某些偶然发生的出错功能。并将 常使用的功能 （如对字符串的操作） 加以简化。 面向对象性：面向对象的 便是容许 开发者 策划实现出能够重用的组件，或者直接利用 已 编好的 组件， 能够增加系的可 维护 性 。 网络性： 跟着 网络 的成长 而 发展，它的很多公用与应用均 与网络相关。 可移植性： 编译程序时 没有 编译 为 机器语言，而是编译 为 与操作系统独立 的 “字节码 ”。 为了实现 言 的可移植性 ， 运行 序必须按照 。 运行 序时， 字节码被 时编译器编译为 能够被目标平台接受的 机器语言。因此， 利用 够 使序在 跨平台 运行 。 鲁棒性 ： C/C+中易出错 、影响程序稳定 的功能删除了，如指第 5 章 程序代码相似度检测系统的实现