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

程序代码相似度比较的研究与实现 摘 要 计算机程序设计课程是计算机及其相关专业中非常重要的 一门 专业基础课程 ,因而程序设计课程 的教学 也 显得尤为重要。 为了提高学生的编程能力及为后续课程的学习打下坚实的基础，这就要求学生能够独立的完成编程设计作业。但由于 互联网 搜索的便利性及计算机数据的易复制性，导致 部分 学生在完成程序设计作业时采取搜索、抄袭他人代码的行为 ,该行为不但对学生 的 成长不利，同时也影响成绩考核的公平性 。本 系统不但能够 帮助教师检测学生的程序作业 是否存在 抄袭情况 ,同时对软件版权的鉴定也具有好的现实意义。 程序 代码相似度比较是 通过 利用一定的检测识别手段，判断两个程序 的源码之间所存在 的相似性， 以及 度量两者之间的相似程度 ，并根据相似程度判别两个程序的源码是否存在抄袭行为 。 针对 序源码相似性问题的检测方法，通过分析及研究相似代码的特点和类型、源程序的属性类型、源程序预处理以及相似度评价标准，采用 法来比较两个源程序文件在结构上的相似性。 同时设计出用于 检测 代码 相似度 的 软件，以提高教学考核的工作效率。 本 系统软件设计基于 发平台，采用面向对象的功能模块化设计思想，在结构度量的基础上，设计开发了文件读 取模块、预处理模块、相似度检测和结果输出模块等四大功能模块。界面简洁友好，检测结果按相似度高低排列并保存在指定的文件中。 关键词： 代码相似性 ;预处理过程 ;结构度量 ;相似度检测 is in is In to to a to of of to in to of an on of of is at of is of of to to of is of of of CS is to in At of in to of on of is so on to of in a 目 录 摘 要 . 1 章 绪论 .开发背景 .研究目的及研究意义 .程序代码相似度检测技术的研究现状 . 国外研究情况 . 国内研究情况 . 目前主流的代码抄袭检测系统 .论文组织简介 .章小结 . 2 章 程序代码相似度检测的理论基础 . 11 相关概念的引入 . 11 序抄袭描述 . 11 码相似度定义 .程序相似代码的分类和掩饰性行为 . 从源代码单个语句方面讨论相似代码的分类 . 从功能和内容方面讨论相似代码的分类 .识别相似代码的一般方法 . 已被成功运用的识别方法 . 从整体上判断代码相似的方法 .相似度度量算法的研究 . 属性计数技术 . 结构度量技术 . 散列值匹配算法 .章小结 . 3章 程序代码相似性识别方法的研究 .标代码相似性的识别 .于 法的识别方法 . 于加权属性相似性的识别 方法 . 加权属性识别方法的理论依据 . 源代码相似度计算 .章小结 . 4 章 程 序代码相似度检测系统的分析与设计 .运行流程 .流程说明 .软件架构 . 文件读取模块 . 预处理模块 . 似代码检测模块 . 相似度计算模块 . 结果输出模块 .章小结 . 5 章 程序代码相似度检测系统的实现 .开发环境与开发平台 . 开发环境 . 开发平台 .程序代码相似度检测的实现技术 . 术的优点 . 术的开发框架 . 三种常用的 程工具包 .程序代码相似度检测系统各功能模块的实现 . 文件读 取模块 . 程序代码预处理模块 . 相似代码检测模块 . 相似度计算模块 . 结果输出模块 .章小结 . 6 章 程序代码相似度检测系统的测试与运行 . 代码预处理的测试 .法的检测 .直接递归法和动态规划法求最长公共子序列的效率分析 .检测结果分析 . 检测精度分析 . 系统界面 . 测试结果综合分析 .章小结 . 7 章 结论与展望 .论 .望 .章小结 . 谢 . 错误 !未定义书签。 参 考 文 献 . 第 1 章 绪论 开发背景 随着信息技术的高速发展 ,信息技术与教育相结合已经越来越应用到现代教学上 ,针对计算机科学与技术专业的各类程序设计课程 ,就有统一的程序语言支撑平台来帮助教学 ,程序语言支撑平台为学生提供了一个综合统一在线练习平台 ,帮助学生提供编程能力 ,同时也帮助教师布置程序设计课程的作业和考试 ,这种利用信息技术实现教学自动化大大提高了教师批改作业和考试的效率。然而也正是因为信息技术的发展 ,从互联网上获取程序资源也越来越方便和快捷 ,有些 学生可能偷懒 ,直接从网上查找相关程序或者从同学那里 复制程序提交给程序语言支撑平台。教师如果去手工检查每个程序 ,需要进行两两对比 ,这样会耗费大量的时间和精力 ,而且学生通过将程序稍微修改 ,让人工检查变得更加困难。 这就要求我们提出一种新的 检测机制 ， 通过综合考虑程序抄袭时所采用的各种作弊手段，并结合现有抄袭检测技术，寻求一种快速的算法，并最终完成具有实际应用价值的软件 。 研究 本课题的目的就是 ： 根据程序语言的特性 ,实现一个 用于检测 程序 源代码相似度 的软件系统 ,并且 该系统通过与程序语言支撑平台进行整合 ,对每个学生提交的作 业与 相同题目的 其他 程序 进行 相似度值 的计算。本 系统 针对 代码 抄袭 行为的鉴定方法的原理 是： 首先 计算 给出的两段程序 源 代码之间的相似度值 ,并根据该值 判断两个程序 之 间是否 存在可能的 抄袭 行为 ,若该相似度 值越大 ,说明存在抄袭的可能性越高。 与 自然语言相比 ，程序语言 有其独特的特点。自然语言 的特点是 灵活多变 ,构成语言的词汇很多 ,且同一词汇在不同的语义环境下存在不同的含义，即使 具有 同一含义的词汇 组成也 是 多种多样 ,因而 检测自然语言的相似度会 非常困难 。 而程序语言由于 具 有固定的关键字 及 语法规则 ,因而所编写的程序的 结构 相对简单 ,所以对程序语言进行 源代码检测要 相对 容易 些 ,针对该问题，国内外对其 相似度检测也做了不少研究 ,一些系统也比较成熟。 当前 程序 源代码的 相似度检测主要 采用两大类技术 :属性计数技术和结构度量技术 。 属性计数技术主要是 通过统计程序源代码 的一些属性计数 ,并不考虑程序 的设计 流程结构 , 因而该方法对于检测两源码文件是否为存在拷贝问题最为有效，而一旦对拷贝的程序源码进行修改，例如添加一些无用变量、无用的注释代码等，其检测准确性 就会大大降低。 且随着程序抄袭或复制程度的 提高 ,很难做出正确的判断。 而 结构度量技术则 通过 分析 并计 算 程序 源码 结构信息 的类似性 ,因而 得到的检测结果更 能真实地反映程序源码 之间存在抄袭行为的可能性 。 现 属性计数技术基本 上 不再 应 用于 源码 相似度检测 ,且 成熟的程序代码抄袭检测系统 大 都采用了结构度量技术。 使用 结构度量技术 进行源码相似度检测 的 工作流程 大多 为：首先对程序代码做 预处理 ,去掉对相似度度量结果没有影响的部分 ,例如无用 空格、空行、注释语句等 ,然后根据一定转换规则对预处理后的代码文件进行语法分析 ,将其转换为表示程序结构信息的标记字符串 ,最后对标记字符串通过字符串串匹配算法 （ 例 如 法）进行 比较 处理 。所以转换规则 非常重要 ,转换规则必须能够将程序语言一些结构化信息体现出来 ,但值得注意的是 串匹配算法并不能体现程序源码 的全部 结构信息。 现比较成熟的程序源码 相似度检测系统 大都 采用串匹配算法来 进行 程序源代码的 相似度 的检测 ,该方法仅能够检测部分完全独立编写的程序 ,但对于一些代码抄袭的投机行为却不能进行正确的识别，例如在程序中添加一些无用结构（在程序源码中添加一些无用变量 ,无用赋值代码），或对控制流程 进行修改。这 些 修改 有时 并 没有 花费抄袭者大量时间和精力 ,但很成功的混靖代码段 ,使得串匹配算法计算出来的相似度很小 ,达 不 到相似 度检测的目的。 本研究将依据程序代码相似度检测基本理论 ,并从何利用属性计数 、结构度量计数和散列值匹配算法来计算相似度。 研究目的及研究意义 在计算机教学过程中，负责批阅作业的老师在批阅过程中总是要面对大量的程序代码，工作相当的繁重，而且人工校对效率非常低下，同时在检查中也会因为疲劳等原因出现很多疏漏。 部分学生 可能 因为 没有学好 该 课程或者 其他目的， 在完成程序设计作业时采取搜索、抄袭他人代码的行为 ,该行为不但对学生的成长不利，同时也会影响成绩考核的公平性 。 本 课题 旨在实现一个程序源码 相似度 检测的系统 ， 通过 该系统检测学生提交的编码课程作业 与给定答案的接近程度，并显示检测 结果。 同时 ，还可以根据度量值判断学生所写程序代码的标准化程度，从而辅助实现作业批改的自动化或试卷评阅的自动化。 程序代码相似度检测技术的研究现状 国外研究情况 程序代码相似性检测最早是处于重复代码的检测及优化而提出的， 在 20 世纪 70年代 ， 针对代码 重复及剽窃 行为， 出 了基于 属性计数法 工作原理的 软 件科学度量检测方法 。 量方法 的工作原理是： 以程序中出现的操作符和操作数为计数对象，以它们的出现次数 作为计数目标来计算程序容量和工作量。 而 根据 性计数法的工作原理 实现了第一个针对 码的剽窃检测系统。但由于属性计数法抛弃了太多的程序结构信息， 从而 导致检测 错误率太高。 针对该问题， 出了 结构度量法，其工作原理是 通过 增加程序 结构信息 的 检测 机制 ， 并 结合结构度量来检测剽窃 的 。 结构度量法的典型是 出的圈复杂度方法， 其工作原理是： 通过计算执行路径的数量来衡 量一个程序中的控制流。 由于 圈复杂度只给出了程序的一个结构特征即控制流， 在编写代码 相似度检测系统时，如果仅仅只是依据该原理则会导致检测正确率极低，因而在使用时 需要与其它特征结合使用， 其常在 属性计数法中 作为 一个度量指标 而存在 。 在实际应用中，往往是将结构度量法与属性计数法综合使用，例如 统 就是通过 结合属性计数法和结构度量法来实现对 序代码的剽窃检测。 而最近 开发的代码反剽窃 系统大都是通过对表达源程序结构的字符串进行比较 的工作原理实现的 ，如： 列等。 国内研究情况 在 1998 年 ，中国人民警官大学 就 研制了 序抄袭判定系统，能够检测序的相似度。 这个程序判定系统 将 言结构分为 ：控制类、变量类、运算符类及标准过程类 的四大类属性 。该系统的统计模块接受 程序，并统计程序的各种属性。在 其中的 比较模块中，首先比较所有程序的四个总属性值，如果两个程序有相似 的 可能 性 ，标上“可能相似” 的 标记，其次比较有相似可能的程序的各个属性值，如果 哪 个程序的相应属性之差的绝对值小于该属性的标准偏差，则将该属性值与其对应权值求和。比较完两个程序的所有属性 值 ，计算出最后的属性值 以 比较的属性的个数，便得到 不同 程序 之 间 的 相似程度。 2006 年，内蒙古师范大学在程序代码属性方法的 程序 代码相似度识别 与比较 的研究中，通过统计 和比较 两个程序代码的多种属性特征 及数值 ，运用空间向量之间的距离计算公式来得到程序代码的相似度。但是，在研究过程中没有考虑到各个属性之间的关系以及由于 程序属性 重要性不同 而导致权重不同的影响因素，舍弃甚至无视了 许多有用的信息，降低了 程序 识别 过程中 的准确度和精度，因此 在程序代码的相似度检测上仍然 有待于进一步 的改进和完善 。 从 目前 的 研究现状可以发现，国内自 1998 年应用属性检测程 序相似度以后，对这个课题所做得研究 相对 较 少。近年来，程序代码相似度的检测都是用各种方法综合程序的 属性计数和程序 的 结构度量 的 。最近 ，出现了从程序设计角度进行度量的方法。此外，也有人提出用神经网络来对 程序的相似度 进行检测 。 总之，目前 对程序 以源代码相似性识别方法研究进展并不明显，更多的是提出和讨论关于 程序中 重复代码 的 检测和优化 的 方法，这对代码相似性识别的研究有 较大的借鉴价值，在此基础上，尚未出现能够 针对程序 源代码相似度的具体或部分检测识别方法 的实现 。 目前主流的代码抄袭检测系统 (1)系统的作者是 以检测的程序语言有 C、 C+、 ，用户可以将 程序文件提交给系统，系统在检测完之后以网页的形式返回给用户。但由于作者并没有说明 该系统所使用的技术，因此对其实现细节我们一无所知。 (2)系统的作者是 理程序时，首先去除注释，随后 统一大小写，然后对 同义词 进行 替换，最 后进行相似度匹配。 不同版本的 使用的 代码 匹配 检测算法 也不 相 同， 本 仅仅只是 使用了 命令， 本使用的检测算法 则 是 法， 而 本 则是使用了法。 (3)系统的作者是 、 和 其对代码的相似度 检测也是使用了 法 ，而在使用形式上 同，它 的实现是使用 言编写，目前 仅 支持 C、 C+等 编程语言的检测 。 (4)系统的作者是 系统 则是通过使用 检测 字符串排列的 列相似性 算法 进行实现的 。 首先将程序源代码进行处理，使其通过一 种紧缩的格式 进行排列，随后系统将其中的一个 紧缩串 拆分 为若干份， 然后将拆分后的若干份的 每一部分到另一个程序的紧缩串中进行 匹配 ，由于这种处理方式与编程语言的语法规则及结构无关，因而这种处理算法使其能够支持大多数语言 。 论文组织简介 本论文共分为五个章节。 第一章主要 介绍 了程序 源代码 相似度检测系统的开发背景，研究目的及 实际使用意义，并介绍了当前主流 代码抄袭检测系统 的 基本 工作 原理及 所使用的 算法 。 第二章主要介绍 程序代码相似度检测 的工作理论 ，分析 了 程序相似代码的 特点并对其进行不同的 分类及 代码 抄袭 者 常用的 掩饰性行为， 列举了 检测 相似代码的一般方法 及工作原理 ，并 针 对程序代码相似度检测的度量方法 的不同特点进行详细的分析与介绍 。 第 三章给出了程序代码相似度检测系统的分析与设计，对该系统的功能模块作了概要分析。 第四章主要是关于程序代码相似度检测系统的实现，分析了系统各功能模块之间的联系，并对每个功能模块作了详细的介绍。 第五章给出了该系统的运行界面和测试结果，并对各算法的运行效率作了比较。 章小结 本章是绪论章节，本章主要是对本课题的研究背景进行阐述，并且根据本课题开发背景明确了本课题的研究意义，在此基础上分析了程序代码相似度检测技术的国内外研究现状，通过分析本课题国内外研究现状为本课题的研究提供研究方法和思路借鉴。本章的分 析对本课题后续的研究具有重要的指导意义。 第 2 章 程序代码相似度检测的理论基础 相关概念的引入 序抄袭描述 程序语言课程随计算机技术的发展在高校越来越重视 ,不仅计算机专业的学生学习程序语言 ,其他专业 ,甚至是非工科专业也开展了程序语言的课程 ,比如应用非常广泛的 C 语言程序课程。除了 C 语言程序设计课程外 ,C+,C#等高级程序语言课程也非常流行。程序语言课程的作业主要是以编程的方式来锻炼学生的程序思维能力 ,这就不可避免的出现了代码抄袭的问题。 程序代码的运行必须严格遵守程序 语言的规范 ,必须通过编译器的检测 ,这就使得程序代码源文件一般都是以电子稿形式进行提交与检测 ,互联网技术的普及 ,电子资料下载的快捷性 ,让许多学生能够轻而易举的从网上搜索到相关代码 ,进而抄袭。抄袭代码不仅让老师的教学事倍功半 ,更让学生失去了自己学习程序语言的一个途径。很多学生进行抄袭的时候会或多或少的修改一部分文字来迷惑老师 ,同样 ,程序代码的抄袭也是如此。同时 ,由于程序代码不像普通文本那样没有特别的规范 ,程序代码的修改必须保证代码正确运行的前提下才有作用。这就造成了代码抄袭过程中抄袭程度的不同和检测难度级别的不 同。 修改他人程序分成了七个难度级别。如下图 示。 图 袭程序代码修改的难度等级图 示不对源程序进行任何修改 ,这种抄袭最简单 ,不用费事 ,所以有不少抄袭属于这种情况。 示只修改了源程序的注释 ,这种抄袭也简单 ,因为修改注释肯定不会影响源程序的结果。 示修改了源程序的部分标示符 ,比如函数 ,宏 ,变量的名字 ,这种修改需要注意其他使用了这个标示符的地方也要做同样的修改 ,通过计算机的查找替换功能也较容易做到。 示修改程序变量声明的位置 ,这种修改需要注 意的是修改了变量的位置后要保持程序的编译正确并且结果也正确。 示用函数体代替函数调用 ,相当于减少函数 ,这种修改也需要验证编译和结果。 示修改程序语句 ,比如 i+变成 i+=l 这种等价替换。 示修改程序的控制逻辑 ,这种修改比较难 ,一般人也难以做到 ,抄袭者也很少这样去修改。 6这两种抄袭手段比较复杂 ,如果抄袭者做到这个级别 ,基本对程序语言有较深的掌握了。 . 袭程度也给出了 10 个难度级别 ,基本和 盖的范围一样 ,只是给出了更细分 的标准。 4*析了抄袭的一般规律 ,总结出抄袭转换基本是由两类转换构成 :一个是跟程序机构无关的词汇级修改 ,另一个是较复杂的结构级修改。 出的 属于词汇级修改 , 于结构级修改。 在实际的教学实践中 ,学生一般都是初学者 ,大多抄袭的学生仅仅在词汇上下工夫 ,如果说去修改程序的结构 ,往往费时又费力 ,阅读别人的程序也不是件容易的事情 ,这样结构级修改还不如自己动手写新的程序。也有一种情况就是 ,通过参考别人写的程序再通过自己理解写出的程序可能和原来 的程序