1.2国内外研究状况和发展趋势
程序代码的复制检测是计算机软件理论与计算机应用技术中的一个重要的科学
问题。最初应用于冗余代码的重复检测与代码优化等研究,后来则被广泛应用于抄
袭检测和代码重构的研究,今天程序代码的相似度研究还被应用于防范病毒的入侵
检测领域。上个世纪的70年代,国外就已经有研究人员对代码克隆、冗余代码的重
复检测和代码优化等技术展开了研究,这些技术后来被应用到程序代码复制检测领
域,同时也产生了一些识别程序代码抄袭或者大规模拷贝的软件。目前常用的程序
代码复制检测技术主要分为两类:基于属性计数(Attribute Counting:AC)的方法
和基于结构度量(Structure Metrics:SM)的方法。
基于AC的方法主要针对程序代码的各种统计属性进行处理,没有过多地考虑程
序代码的结构信息。Halstead提出的软件科学度量方法是目前为止最早的属性计数法
【31。该方法首先提出了软件度量的标准,然后基于该标准定义了多个软件度量特征,
通过对程序代码中的这些软件度量特征进行统计计数生成其特征向量,在此基础上
构建特征向量空间,这样程序代码便被映射到了一个11维的笛卡儿空间,之后运用
向量空间模型运用向量夹角余弦公式来度量向量之间的相似性,并以此为依据进而
度量程序对之间可能的“抄袭行为”。此后的基于AC方法的复制检测技术也多是基
于这种软件科学理论进行研究的。在Sallies所提出的检测技术中就采用了基于AC
的检测方法,在构建特征向量时,将度量指标定义为一个由容量、控制流、数据依
赖、嵌套深度、控制结构六部分组成的六元组向量降51。但是由于该方法较少考虑到
程序代码的结构和具体的语义信息,其检测的效率虽然较高但精度较差,错判的情
况多有发生。后来有人提出通过增加向量的维数来改善其检测精度,但效果并不明
显,Verco和Wise在其1976年发表的论文中指出,“通过单纯的增加向量的维数并
不能改善检测的错误率【6p。
而基于SM的方法则将程序内部结构加入了分析比较,由于该方法包更多的程
序内部的结构信息和部分语义信息,因此用来判断相似性将会很大程度上提高检测
的准确性。一般的SM方法检测机制主要包括两个关键步骤:
一个是程序标准化,即将源代码进行转化。例如将所有用户自定义标识符转换
成特定符号、过滤掉空白冗余与注释项、把大小写字母进行统一等等。具体的手段
又可以分为:token-based、string-based、syntax tree-based、semantic.based等。
String-based:首先源代码通常按行分割成字符串,每个程序片段包含相邻接的字
2
2022-09-06 14:25:52
2.29MB
语法树
1