判断两段程序之间是否存在抄袭
3星 · 超过75%的资源 需积分: 9 97 浏览量
2010-06-19
11:00:36
上传
评论
收藏 27KB DOCX 举报 
判断两段程序之间是否存在抄袭
08 信管 20081000445 谭永鹏
程序代码相似度度量技术主要应用在代码的剽窃检测上。判断一个程序是否是从另一
个程序复制而来，实质上是对这两个程序的相似度进行度量，根据度量的结果给出一个相
似度的数值表示， 再由这个数值判断这两个程序之间是否存在抄袭。
1 程序代码相似度度量技术
早在 20 世纪 70 年代初， 就出现了一批比较典型的程序源代码剽窃检测系统。
Halstead 的软件科学度量方法是最早和最典型的属性计数法。 这种度量方法以程序中出现
的操作符和操作数为计数对象，以它们的出现次数作为计数目标来计算程序容量和工作量
但是，单纯的属性计数法抛弃了太多的程序结构信息，导致检测结果的错误率太高。
McCabe 提出的圈复杂度方法是一种典型的结构度量法。它通过计算执行路径的数量来衡量
一个程序中的控制流。圈复杂度只给出了程序的一个结构特征即控制流， 往往需要与其它
特征结合使用， 因此常作为属性计数法中的一个度量指标。在实际应用中，很多代码剽窃
检测系统将两种度量方法相结合。最近提出的系统大都是通过对表达源程序结构的字符串
进行比较来达到剽窃检测的目的。综上所述，应用于程序代码剽窃检测系统中的代码相似
度度量方法可分成两类： 属性计数技术和结构度量技术。
1.1 属性计数技术
在剽窃检测算法的发展过程中，大多数工作集中在 Halstead 的软件科学理论。 这些基
于软件科学度量的算法是从程序中提取出数个软件度量特征，计算每一个程序的 n 个不同
的软件度量指标，以便于将程序映射到一个 n 维的笛卡尔空间， 然后利用向量空间模型来
度量程序代码相似性。
① 常用的属性计数法度量指标
在属性计数技术中，有以下 6 个常用的代码相似度度量指标， 被描述为一个 “6 元组”
向量。
(1)容量： 容量被认为是任何算法实现的大小的反映， 常使用 Halstead 的软件科学度
量方法来量化。该方法首先对程序代码中的词元进行词频统计：n1=用到的操作符的种类数；
n2=用到的操作数的种类数；N1=出现的所有操作符总数；N2=出现的所有操作数总数。然
后用如下公式计算程序容量 V=N
log
2
n
式中： N=N1+N2——程序长度； n= n1+n2 ——程序所用的词汇量。
(2) 控制流：控制流常用 McCabe 提出的圈复杂度来度量。圈复杂度是一种为程序逻辑
复杂性提供定量测度的软件度量方法，用于计算程序的基本的独立路径数目。该方法首先
将程序代码转换为一个带有惟一入口和出口结点的控制流图。这种方法具有语言依赖性，
这意味着在创建控制流图前，必须理解编写代码的语言的语法和语义。在程序控制流程图
中，节点表示程序中一个顺序代码单元，边表示程序中产生的分枝。一个有 e 条边和 n 个
节点的控制流图 G， 其圈复杂度定义为 V(G)= e-n+2p
其中： p= 控制流图中的模块数。
(3)结构： 这个度量标准考虑到使用一些指标去阐明模块之间的耦合程度。
(4)数据依赖： 用与度量程序控制流相似的方法， 数据依赖也能被度量。在流程图中 ，
用结点来阐明谓词子句和变量定义。
(5)嵌套深度： 这是一个简单的度量标准， 通过赋给每个代码行一个深度值，返回一
个程序的平均嵌套深度。平均值是由这些深度值的总和除以程序中语句的个数计算而来。
(6)控制结构： 给出现在程序中的每一种类型的控制结构赋予一个权值， 例如给一个
评论1
最新资源