相似度进而对学生提交的虚拟实验方案进行抄袭检测的系统对于减轻老师的实验作业管理工作量、提高实验老师的工作效率、监督学生的实验作业质量都具有重要的意义。
2 华 中科 技 大学硕士学位论 文 1.2 国内外相关研究 目前国内外学者进行复制检测的电子文档主要集中在源程序文件和自然语言文本两类上而在两类的复制检测过程中都涉及到序列相似度的度量下面分别介绍各类相似度的度量技术。
1.2.1 复制检测的研究现状 复制检测Copy Detection又称剽窃检测Plagiarism Detection也有人称为副本检测Duplicate Detection它不但是实施知识产权保护Intellectual Property Protection的一种重要手段也是提高信息检索Information Retrieval效率的一种有效方法。
所谓复制检测就是判断一个文件的内容是否抄袭、剽窃或者复制于另外一个或者多个文件。
剽窃不仅仅意味着原封不动地照搬还包括对原作的移位变换、同义词替换以及改变说法重述等方式2。
根据被检测文档的类型将复制检测分为两类一类是源程序的复制检测另一类是自然语言文本的复制检测。
程序复制检测和自然语言文本复制检测方法有很多是相似的而且有的检测工具能够同时检测程序复制和文本复制例如悉尼大学Wise开发的YAP3Yet Another Plague Three3。
但是二者也有不同之处所有的计算机程序都受到严格的形式化语法限制但是自然语言文本由于没有形式化语法限制以致存在很多含义模糊的表达程序中有些内容如变量名称可以随意替换而语义不变但是自然语言文本中的字词不能任意替换程序的结构信息清晰获取容易而自然语言文本的结构特征的获取比较困难。
可见自然语言文本复制检测技术比程序代码的复制检测的难度更大一些。
1.2.2 源程序相似度度量技术 程序代码相似度检测的研究在国外开始得相对较早。
早在20世纪70年代初就有学者开始研究防止程序抄袭的技术和软件。
Faidhi等用图形的形式描述了修改别人程序代码的难度级别将难度划分为L0到L6的七个不同级别4。
Edward则将抄袭转换原来程序的难度级别分为十级5。
Joy等将这些抄袭转换分成了两类一类是不依赖于程序结构的词汇级抄袭另一类是需要较多技巧的结构级抄袭。
Jones的1到 3 华 中科 技 大学硕士学位论 文 7级转换以及Faidhi和Robinson的L0到L5级转换都属于“词汇级”抄袭转换Joy等的“结构级”抄袭对应他们更高级别的抄袭转换即Jones的8到10级以及Faidhi和Robinson的L6级6。
这些难度级别的定义和划分可以用来衡量一个源程序复制检测算法的优劣能检测出越多转换的算法认为它的查全率越高。
程序代码相似度度量的方法主要是通过计算程序代码的组成元素信息或者组成元素的结构信息来度量程序代码之间的相似程度。
根据所提取信息的不同程序代码相似度的度量方法大致分为两类属性计数技术和结构度量技术。
1属性计数技术 1976年Purdue大学的Ottenstein首次提出了应用属性计数法Attribute Counting获取相似度的方法。
他首次使用Halstead向量进行程序相似度识别并开发出了一个用来检测Fortran程序相似度的系统。
该系统直接统计Halstead提出的可以衡量程序特征的四个基本参数n1n2NlN2基于这四个基本属性定义词汇量nn1n2长度NN1N2然后根据程序段的词汇量和执行长度计算出它的“容量V”公式为VNlog2n最后用Halstead特征向量将以上信息表征出来HnNV。
在一组程序中每一个程序都用这样的特征向量表示出来通过度量这些特征向量之间的“距离”来得到程序之间的相似性度量得到的距离越小说明程序之间相似的可能性越大78。
为了得到更加准确的度量结果人们又提出了使用更多属性来度量两个源代码间的相似程度使得各种基于属性计数的源代码复制检测系统越来越复杂如Faidhi提出增加两个程序中控制流结构的数量这一属性4而Grier设计的Accuse系统统计的属性包括程序中的代码行数变量声明和使用的数目控制语句的数目等9。
然而实践证明对于结构化程序设计语言所编制的程序来说如果单纯地使用属性计数法进行复制检测由于抛弃了太多的程序结构信息将导致错误率过高。
Verco和Wise指出即使增加属性的向量维数也不能提高属性计数法的错误率。
改进的措施就是加入程序的结构信息的匹配也就是结合结构度量Structure Metrics也称为控制流Control-flow来度量程序的相似度10。
2结构度量技术 4 华 中科 技 大学硕士学位论 文 通过分析程序结构来度量程序代码之间相似度的方法称为结构度量法Structure Metrics该方法主要通过下列两个过程来得到相似度的值第一步是基于程序的编程语言类型对程序进行语法分析以生成一个标记串Token序列即将每一个程序都转换为一个字符串序列第二步是根据某种匹配算法比较这些标记串得到相似的标记序列根据匹配结果计算相似度的值。
McCabe提出了圈复杂度的结构度量技术它是通过计算执行路径的数量来度量程序中的控制流这种技术需要对程序进行预处理给出程序的控制流图控制流图中的边或弧是执行路径节点表示一个处理语句或一个判断的入口。
根据得到的控制流图计算出全复杂度来度量源程序间的相似程度11。
1992年Wise在Plague的基础上开发了YAP系列工具最早的两个版本YAP1和YAP2主要用于源程序的复制检测而最终版本YAP3既可以用于源程序也可以用于文本文档的检测。
实验结果证明YAP系统工具能检测出变换程序中的注释或程序的格式、变换程序中使用的标识符、改变变量的数据类型、改变操作数的顺序等数十种抄袭变换是一个有效的学生程序的复制检测系统312。
1994年Aiken在Berkeley开发了MossMeasure of Software Similarity系统用来识别CCJavaPascalAdaMLLisp或Scheme等语言编制的源程序的相似度。
MOSS系统返回一个百分比比值来表示程序对的相似度还能将最长匹配区域显示出来13。
1999年美国威奇托市堪萨斯州立大学的David等人共同开发了SIM系统该系统可用于检测程序或软件项目中的代码抄袭。
它直接使用用于检测DNA序列相似度的一种字符串匹配算法。
该系统能检测出多种程序抄袭行为并且在检测小规模的程序时速度非常快14。
还有的系统混合使用了结构度量技术和属性计数技术其中之一就是Donaldson的抄袭检测系统该系统统计了属性计数法中的8个属性同时也生成了表示程序结构的字符串这个字符串中的每一字母表示程序的一个或多个结构信息如果这个生成的字符串能精确匹配或者比较相近那么就认为这两个程序之间存在抄袭15。
今年来国内也出现了很多源程序的复制检测。
邓爱萍等人提出了对学生程序设计作业进行源代码复制检测的一种实现方案并且提出忽略程序表面的差异而集 5 华 中科 技 大学硕士学位论 文 中在程序的实质相似性上能提高检测的准确性同时也减少了对不同编程语言的适应性16。
文献17中提出了一种属性加权的识别方法采用代码属性向量的加权思想增强属性元素中具有隐蔽性相似代码的影响因素使相似代码评估更具有客观性改善和提高了识别的质量和准确性。
张鹏等人提出融合粗糙集理论的分类处理能力与本体论的数据描述能力提出了一种基于本体粗糙集的个体相似度度量方法并将其应用于程序代码的相似度度量上。
实验结果显示该方法在程序代码相似度度量上具备较好的实际效果18。
赵长海等人了一个程序代码相似性检测系统BuaaSim采用编译优化和反汇编技术将源程序转化为汇编指令集合删除和替换汇编指令中对程序本质特征影响不大的易变元素使用一个与指令顺序无关的决策函数即使程序相似度19。
1.2.3 自然语言文档相似度的度量技术 自然语言文本与程序
上一篇:
【精品】第3章流程控制
下一篇:
缅怀先烈 铭记历史