使用哈希值和标识符冲突率的克隆代码
检测的误检消除方法#
边奕心，王甜甜，苏小红，马培军**
5 （哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001）
摘要：针对采用基于token 的克隆代码检测方法检测语法相似的克隆代码时存在的部分误检
问题，本文提出一种使用哈希值和标识符冲突率来消除克隆代码检测的部分误检的方法。该
方法首先通过语句的哈希值判断语句结构的相似性，然后计算标识符冲突率，通过冲突率的
变化，来确定误检消除的方向和消除情况。对于存在误检的克隆代码，最终通过修改克隆代
10 码的相对行号来消除误检。实验结果表明，本文方法可以消除由于插入结构相同的语句而引
起的克隆代码的误检问题，并在此基础上，有效消除了语句形式一样但由于语句顺序颠倒而
引起的克隆代码误检问题，提高了克隆代码检测及克隆代码相关缺陷检测的准确性，有利于
后续克隆代码重构的研究。
关键词：克隆代码；哈希值；标识符冲突率；误检；重构
 0 引言
克隆代码(Cloned Code)，又被称作重复代码(Duplicated Code)，是指源代码文件中多个
35 相同或相似的代码片段[1]。
克隆代码在大多数情况下是有害的，它增加了软件系统代码的长度，使得软件系统愈加
复杂、难以维护，系统运行效率降低，并且给软件引入大量的程序缺陷。多种自动检测大规
模软件系统中克隆代码的工具[2]。ZhenminLi 和Shan Lu 等人在文献[3]中将数据挖掘与克隆
代码检测结合，开发了克隆代码检测工具CP-Miner。高效的序列模式挖掘算法既明显提高
40 检测的速度，降低了时间复杂性，还可以容忍经过增、删、改和变量重命名的克隆代码片段，
并且对“拷贝-粘贴-修改”行为导致的变量重命名不一致的软件缺陷进行了检测。但是，通
基金项目：国家自然科学基金(61073052);高等学校博士学科点专项科研基金项目资助(20092302110040)
作者简介：边奕心，(1979-)，女，博士生，软件工程
通信联系人：苏小红，（1966-），女，博士，教授，博士生导师，主要研究方向：程序分析，软件缺陷检
测，信息融合，图像处理与模式识别. E-mail: sxh@hit.edu.cn
 过分析实际的程序发现该方法存在一些误检问题。首先，如图1 中程序所示(图中++用于标
记克隆的语句)。可以看出，(a)和(b)中的第5 行克隆语句的映射发生了错误（(a)中的第5 行
语句应该映射到(b)中第5 行语句的下一行语句）。
其次，如图2 45 中程序所示。可以看出，由于语句顺序颠倒，图2(a)和(b)中的语句3 和4
的映射发生了错误。
克隆代码片段的映射错误，不仅会导致后续对克隆代码相关缺陷检测的误检，如图3
所示（由图1 中的克隆代码检测的误检引起），而且会导致错误的语句相似度分析，从而影
响克隆代码重构的准确性。
50
图1 CPBugDetector 检测出来的linux2.6.6/arch/ppc64/boot/prom.c 中的克隆代码
Fig.1 Cloned code in linux2.6.6/arch/ppc64/boot/prom.c detected by CPBugDetector
1
2
3
4
5
6
7
+ + if(error < 0)
{
+ + goto out_putf;
}
+ + lastdirent = buf.previous;
+ + error = buf.error;
+ + if ( lastdirent )
{
+ + put_user ( file -> f_pos , & lastdirent -> d_off ) ;
+ + error = count - buf . count ;
}
(a)
1
2
3
4
5
6
7
+ + if(error < 0)
{
+ + goto out_putf;
}
+ + error = buf.error;
+ + lastdirent = buf.previous;
+ + if ( lastdirent )
{
+ + put_user ( file -> f_pos , & lastdirent -> d_off ) ;
+ + error = count - buf . count ;
}
(b)
图2 CPBugDetector 检测出来的linux2.6.6/arch/s390/kernel/compat_linux.c 中的克隆代码
55 Fig.2 Cloned code in linux2.6.6/arch/s390/kernel/compat_linux.c detected by CPBugDetector
行
号
语 句 哈希值 行
号
语 句 哈希值
1
2
3
4
5
6
7
8
+ + va_list args;
+ + int i;
+ + va_start(args,fmt);
+ + i = vsprintf(buf,fmt,args);
+ + va_end(args);
+ + return i;
(a)
21501776
105405920
73109296
197641792
76781968
86935968
1
2
3
4
5
6
+ + va_list args;
char buf [ 256 ] ;
+ + int i;
+ + va_start(args,fmt);
+ + i = vsprintf(buf,fmt,args);
+ + ll_puts ( buf ) ;
va_end(args);
+ + return i;
(b)
21501776
45655227
105405920
73109296
197641792
76781968
76781968
86935968
 图3 克隆代码相关缺陷检测的误检
Fig.3 The false positive of cloned code related bugs detection
60
为解决上述问题，本文提出了使用语句哈希值和标识符冲突率来消除克隆代码部分误检
的方法。该方法不仅可以处理由于插入相同语法结构的语句而导致的克隆代码的误检问题，
而且还可以消除语句形式一样但由于语句顺序颠倒而引起的克隆代码误检问题。通过分析实
际的程序代码证明本文方法可以提高克隆代码检测及克隆代码相关缺陷的准确性。
65 1 相关研究
1.1 基于频繁子序列挖掘的克隆代码检测模型
基于频繁子序列挖掘克隆代码检测模型[3]将程序代码转化为token 串，将token 串转化
为数字序列（每一行语句映射成一个数字），相同结构的语句被映射成相同的数字，如图1
所示，生成数字序列数据库，引入数据挖掘算法中频繁子序列挖掘技术，将重复代码检测转
70 化为序列挖掘问题，解决了以往算法时间复杂度过高且不能识别修改了的拷贝-粘贴代码的
缺点。
1.2 克隆代码相关软件缺陷检测模型
克隆代码检测的目的是为了解决与克隆代码相关的问题。基于序列挖掘的C 克隆代码
及相关软件缺陷检测模型在克隆代码检测后，根据其生成的克隆代码集合以及克隆代码相关
75 源程序信息，进行了克隆代码相关缺陷的检测。
1.3 标识符冲突率
为了识别标识符不一致的情况，通过计算克隆代码对的标识符冲突率来判断标识符不一
致的发生的位置。每个标识符的映射冲突率的计算公式如式2-3 所示
0 F1 =1- MF1apping 1
ConflictRatio( A ) max{Occurrence( A')| A' ( A)}
Occurrence( A )
∈
≤ ∈ <
∈
(2-3)
 80 2 使用语句哈希值和标识符冲突率的克隆代码检测的误检消除算法
2.1 算法模型
本文提出的算法模型如图3 所示。误检消除算法描述如图4 所示。
该模型基本思路如下：首先对C 源代码进行克隆代码检测，然后计算克隆代码对中的
每个标识符冲突率。对于具有冲突的标识符，在上面两步的基础上，根据冲突发生的代码行
85 位置，判断当前语句行的下一条语句与当前语句行的哈希值是否相等，如果相等，则将对应
位置标识符作为当前匹配的标识符，计算标识符冲突率。如果新的标识符冲突率为零，说明
发生了误检，则根据记录的语句行号调整克隆代码标记的相对行号。如果新的标识符冲突率
不为零，则继续对当前行的上一条语句计算标识符冲突率。如果当前语句行的下一条及上一
条语句都计算完标识符冲突率，结果仍不为零，则表明没有发生误检，输出当前的检测结果。
90
图3 使用哈希值和标识符冲突率的克隆代码误检消除算法模型
Fig. 3 The model of the method to eliminate false positives of cloned code detection with hash value and identifier
conflict ratio
95
 图4 算法描述
Figure 4 the algorithm description
100 2.2 算法举例
以图1 中所示程序为例，在消除误检之前，输出如图3 所示的缺陷检测结果。这种误检
产生的原因是由于插入了一条语句引起的，CloSpan 算法可以成功的识别插入或删除语句的
克隆代码，但图1 (b) 中插入的是与克隆语句结构相同的语句，这种结构相同的语句被映射
成相同的数字，以图1 为例，即语句ll_puts ( buf ) 和语句va_end(args)被映射成相同的数字
105 （76781968），在挖掘之后，算法就误把语句(b)中的ll_puts ( buf )与(a)中的va_end(args)当
作克隆语句，进行匹配。这种错误的匹配将导致后续克隆代码相关缺陷检测的误检，如图3
所示。根据本文方法，首先，根据当前的标识符冲突率（1/4），记录当前冲突发生的位置
（语句的行号）,判断当前语句的下一条语句与当前语句的哈希值是否相等，即两条语句是
否是结构相同，然后，将下一条语句对应位置的标识作为被匹配的标识符，重新计算标识符
110 冲突率。如果冲突率为零，则说明当前语句的下一条语句是真正的克隆语句，进而，将当前
语句的行号与下一条语句的行号交换，修正克隆代码检测结果。结果如图5 所示。这种方法
不仅消除了插入语句的克隆代码的误检，而且，还消除了语句结构相同（数字相同）而语句
顺序颠倒产生的误检。如果冲突率不为零，则说明当前语句的下一条语句不是真正的克隆语
句。此时，本文方法判断当前语句的上一条语句与当前语句的哈希值是否相等，即两条语句
115 是否是相同结构的语句，如果相等，则将上一条语句对应位置的标识符作为被匹配的标识符，
重新计算标识符冲突率。如果冲突率为零，则说明当前语句的上一条语句是真正的克隆语句，
进而，将当前语句的行号与下一条语句的行号交换，修正克隆代码检测结果。如果当前语句
行的下一条及上一条语句都计算完标识符冲突率，结果仍不为零，则表明没有发生误检，输
 出当前的检测结果。
1
2
3
4
5
6
7
8
+ + va_list args;
+ + int i;
+ + va_start(args,fmt);
+ + i = vsprintf(buf,fmt,args);
+ + va_end(args);
+ + return i;
(a)
1
234
56
+ + va_list args;
char buf [ 256 ] ;
+ + int i;
+ + va_start(args,fmt);
+ + i = vsprintf(buf,fmt,args);
ll_puts ( buf ) ;
+ + va_end(args);
+ + return i;
(b)
120 图5 误检消除之后的克隆代码
Fig.5 The cloned code after false positives elimination
3 实验结果
我们采用采用克隆代码检测工具CPBugdetector[4]分别对Linux_2.6.6 源程序中的arch、
125 net 和kernel 模块进行克隆代码及相关缺陷检测。比较消除误检之前和消除误检之后的缺陷
检测结果。结果如表1 所示。
学术论文网Tag：代写论文 代写毕业论文 论文发表 代写毕业设计