湖南省大学生研究性学习和创新性实验计划项目结题报告.docx

《湖南省大学生研究性学习和创新性实验计划项目结题报告.docx》由会员分享，可在线阅读，更多相关《湖南省大学生研究性学习和创新性实验计划项目结题报告.docx（20页珍藏版）》请在优知文库上搜索。

1、湖南1大学生研究性学理能扇牲奖剑划项目结题报告项目名称：ACM竞赛程序源代码复制检测系统的设计与实现项目编号：学生姓名：刘洋易长庚刘慧凤曾嘉佩所在学校和院系：湖南第一师范学院信工院项目实施时间：2014年6月一2016年3月指导教师：田祖伟联系电话：填表日期：20表年3月30日湖南省教育厅2016年制一、基本情况项目名称ACM竞赛程序源代码复制检测系统的设计与实现立项时间2014年6月完成时间2016年3月项目主要研究人员序号姓名学号专业班级所在院(系)项目中的分工1刘洋12计科1班信工院算法设计2易长庚12计科1班信工院代码实现3刘慧凤13计科1班信工院代码实现4曾嘉佩13计科1班信工院系统

2、测试二、研究成果简介项目研究的目的、意义；研究成果的主要内容、重要观点或对策建议；成果的创新特色、实践意义和社会影响；研究成果和研究方法的特色。限定在2000字以内。1、项目研究的意义通过几代人的不懈努力，人类最伟大的发明之一计算机，已经成为了人们生活中不可或缺的必备工具，也间接地成为了社会衡量和选取人才的标准之一。因此，现代初高等教育也在不断地加强青少年的计算机高级应用水平，几乎所有高校都已开设或正在筹备开设计算机软件应用或计算机程序设计类学科课程。但是，不少学生出于对程序设计的懒惰甚至惧怕心理，在面对程序设计类作业时,采取各种手段复制抄袭网络上或同学朋友的源代码，以应付老师和学校的检查。这

3、种行为严重影响了学校的教学质量，而且极不利于学生提高自身的计算机应用水平，减少了毕业求职时的筹码。针对上述现象，国外教育机构的调查结果表明：有高达85.4%的学生承认抄袭过别人的编程作业。随着程序源代码的抄袭现象越来越普遍，抄袭手段越来越多样化，单纯地依靠学校和老师对学生的思想教育和人工辨别检测已难以抑制抄袭现象的蔓延，高等院校急需更高效、准确的检测方法来检测抄袭行为，遏制抄袭现象地继续发生。但是，判断程序源代码是否抄袭是一项耗时、复杂的工作，若一个班级有n名学生，就必须对其所有的n份作业进行n(n-l)2次对比判断，尤其是当程序设计类作业的难易程度不同时，即无法准确查出抄袭者，又无法确保因难

4、易程度等因素的不同而造成的误判断，往往只能依靠老师的经验和检查的仔细程度来大致控制检测的准确率，这无疑增加了老师的工作时间和复杂度，且收效甚微。利用高效率的程序源代码抄袭检测工具才能有效地解决这个问题，因此，开发ACM竞赛程序源代码复制检测系统具有一定的实用价值。2、研究成果的主要内容（1）程序源代码抄袭检测技术、抄袭手段分类及应对不同情况的分级处理方法，现有检测系统原型及其主要算法研究。程序源代码抄袭检测主要是通过对比两段程序源代码，计算这两段程序源代码之间的相似度并得到一个0.0到1.0之间的相似度值，再通过设置阈值（可由系统自动计算或用户设置）来划分出是否有抄袭行为嫌疑的程序代码片段，进

5、而判断目标程序源代码中是否存在抄袭行为。目前较常用的程序源代码检测技术一般为属性计数法和结构度量法两种。属性计数法是统计程序源代码中所包含的各种属性（即成员变量），并将其映射到给定的向量空间中，再计算这两段程序源代码之间的相似度值。但该方法即使在向量维度上进行优化，准确度仍然较低，误判断较多。VercO等人也指出“单纯地增加向量的维数并不能减少检测的错误率，提高检测精度二结构度量法是将程序源代码进行预处理成特殊的数据序列，再利用相似度计算公式计算出相似度值。相比属性计数法，该方法可将程序源代码中的结构和语义加入检测判断过程，提高检测准确度。基于结构度量法的检测算法通常包括以下两个步骤：1）程序

6、源代码预处理。即将程序源代码进行标准格式化、注释和冗余空白字符过滤、关键字标识符替换、常量替换、数据类型等价替换和统一大小写等。目前常用的预处理方法包括：基于String的方法、基于TOken的方法和基于AGT（AbstractGrammarTree,抽象语法树）的方法等。基于String的算法，即将程序源代码以行为单位分割成若干字符串的集合，每个程序代码片段包含相邻的字符串，判断两两程序代码片段的字符串是否相同，再根据程序代码片段相似度判断是否存在抄袭行为。该算法检测准确率不高，代表算法有1995年Baker提出的参数化匹配算法。基于Token的算法，即对程序源代码进行词法分析，生成Toke

7、n序列，再对比检测两段程序源代码的TOken序列中相同的片段。该算法效率很高，但准确度仍然较低。基于AGT的算法，即利用工具对程序源代码进行词法语法分析，得到该段程序源代码的抽象语法树，判断两段程序源代码的抽象语法树中的子树是否相似，再根据相似子树的相似性判断相似度。该算法准确度较高，但冗余较大，效率较低。2)相似度计算。即对程序源代码预处理后，得到其对应的数据序列，再根据两段程序源代码的数据序列进行相似度计算。目前常用的相似度计算方法有向量模型法和字符串匹配算法两类，如点阵图法、序列匹配算法、LCS(LongestCommonSubsequence,最长公共子序列)算法、GST(Greedy

8、-String-Tiling)算法和RKR-GST(Running-Karp-RabinGreedy-String-Tiling)算法、WinnoWing算法、余弦度量法等。上述两种方法虽在一定程度上能够检测出程序源代码中的相似处，但效率和准确率都比较低，不能非常有效地应对所有的抄袭手段。且这些算法过于依赖阈值，阈值的设置直接地影响了算法的准确度，而某一算法的阈值需要经过大量实验才能较精确地确定，当情况发生变化时，阈值或需重新设置，这无疑增大了算法设计实现和程序开发的难度。(2)基于N-gram检测算法研究N-gram是一种统计语言模型，其定义为：设Z为一个字母表，S是一个由Z中的字母组成的字

9、符串。ISl表示S的长度，Siu是S中第i个字母(i从1开始)，E同是S中从第i到第j个字母组成的S的子字符串，N是一个整数，且N不大于S,则S中的N-gram就是长度为N的S的邻接子字符串，如：S11,i+N.i,S11jNioG(S,N)表示字符串S中所有的N-gram的集合，长度为ISl的字符串可以生成L=IS卜N+1个N-gram,如：S=detection，S=12,N=5,则G(S,N)=(l,detec)，(2,etect),(3,tecti),(4,ectio),(5,CtiOn)oN-gram适用于语音识别、文字识别、文本分类、信息检索、机器翻译和中文分词等领域，且于1995

10、年被M.Damashek首次应用于文本相似度度量，近几年被证明适用于文本抄袭检测，能有效地提高文本抄袭检测的准确率，且优于普通字符串匹配算法。N-gram算法统计N-gram集合中每个元素出现的频率，而忽略了该元素在程序源代码中的原始位置，使得检测抄袭时能够较好地降低因抄袭者使用代码块及其内部语句重排序和表达式拆分等较高级抄袭手段对检测准确度造成的影响。同时，对生成N-gram前的预处理也可以较有效地检测大部分低中级抄袭手段，使得N-gram算法在一定程度上能够达到较理想的检测准确度。（3）基于Ngram算法检测系统的底层检测计算框架的设计和实现，采用分级处理方法提高检测系统针对性的代码实现。

11、为了提高检测系统的检测准确率和针对性，本文采用了Ngram算法与分级处理的方法对系统进行了实现和优化。Ngram算法是一种统计语言模型，适用于语音识别、文字识别、文本分类、信息检索、机器翻译和中文分词等领域。N-gram可以很好地保持程序源代码的结构和语义，在此基础上进行抄袭检测，可以有效地提高检测的准确度。几乎所有的检测算法都需要为其设置阈值，而阈值的概念对于一般普通的用户而言较抽象晦涩，使其无法达到最理想的值，这也极大程度地影响了最后相似度的计算结果。分级处理是将抽象的阈值形象具体化，即将程序源代码按难易程度划分（可由系统根据程序源代码规模自动计算或用户选择设置），帮助用户在使用系统时更方

12、便清晰的设置恰当合理的“阈值”，提高用户体验和检测针对性。系统实现有五个重要步骤：a）读取程序源代码数据。使用JaVa的JDK内置的K）相关API,读取程序源代码。b）预处理。根据难易程度的不同，对待检测程序源代码进行不同复杂度地格式化预处理，预处理方式由用户选择填写传入的相关参数确定。c）生成标记。根据程序源代码使用的程序设计语言的语法规则和关键字,将其转换为对应的标记序列，可以较好的压缩待比较数据的空间占用大小，提高检测系统的运行效率，还可以保持程序源代码中原有的结构和语义，即结构化。d）生成N-gram。将标记序列转换为N-gram集合，统计每个N-gram出现的频率，并将得到的N-gr

13、am文本存入数据库中。e）计算相似度。从数据库中查询区其他程序源代码的N-gram文本，与待对比的程序源代码生成的N-gram频度向量依次进行相似度计算，得到相似度值。本文采用了较为灵活的架构设计，尽量做到能够根据用户不同的需求（即选择传入的不同参数）进行较为恰当地处理和检测，但又不需要用户做出太多太复杂的操作，在保证系统检测的准确度、针对性和效率的同时，有较好的用户交互和体验。同时开发了大部分表示层和中间层，让系统有较高的扩展性，也为第三方开发者提供了二次开发的接口和服务。1）预处理预处理主要用于去除程序源代码中的混淆、无用数据，并按照用户指定的程序设计语言编码标准及风格格式化该该程序源代码

14、，同时可检测表22中修改排版的抄袭手段。本文包含的预处理方式有以下几种：a）删除程序源代码中的注释语句。b）将一行包含多条语句的代码转化成每行一句。c）将本为一行的多行代码转化成一行。d）删除代码中的多余空白字符（空格、Tab）oe）将所有字母转化成小写字母。前三种预处理方式可由用户选择是否进行，这样可以有效地避免对格式规范的程序源代码进行无用的预处理操作，提高系统的检测效率。系统将会根据用户提供的难易程度进行一种或多种预处理，即分级处理（3.2节），得到的程序源代码有效地去除了原程序源代码中的注释和多余空白字符，在保证生成标记和N-gram过程中数据的有效性的前提下，直接地过滤了多余无用字符

15、对检测的影响，且格式规范,有利于提高检测系统的准确性。2）生成标记预处理后的程序源代码有很好的符合对应程序设计语言类型标准的代码结构，在此基础上进行标记生成，能够在保证程序源代码结构和语义的同时，压缩代码的数据量，减小其所占的内存空间，提高检测的效率。生成标记的方法分为精确标记生成和模糊标记生成两种。精确标记生成，即将语句用原意标记精确替换。若原语句声明了一个int类型的变量，经过精确标记生成后得到的语句为IT；若原语句声明了一个long类型的变量，经过精确标记生成后得到的语句则为LG。该种标记生成方法可以非常精确的保留原程序源代码的语义，但无法应对抄袭者替换等价数据类型的抄袭手段。模糊标记生成，即将语句用类似标记模糊替换。若原语句声明了一个double类型的变量，经过模糊标记生成后得到的语句为FT；若原语句声明了一个float类型的变量，经过模糊标记生成后得到的语句同样为FT。该种标记生成方法弥补了精确标记生成方法的缺点，但无法完全保留原程序源代码的语义，更容易产生误判断。因此,本项目根据分级处理的结果,在不同难易程度使用不同的标记生成方法,尽量避免判断误差。3）生成N-gramN-gram算法的处理过程能够较好地解决传统的基于TOken的程序源代码抄袭检测技术的问题，提高检测的准确率。gram原代表