使用哈希值和标识符冲突率的克隆代码检测的误检消除方法

边奕心　王甜甜　苏小红　马培军

摘要：针对采用基于token的克隆代码检测方法检测语法相似的克隆代码时存在的部分误检问题，提出一种使用哈希值和标识符冲突率来消除克隆代码检测的部分误检的方法。该方法首先通过语句的哈希值判断语句结构的相似性，然后计算标识符冲突率，通过冲突率的变化，来确定误检消除的方向和消除情况。对于存在误检的克隆代码，最终通过修改克隆代码的相对行号来消除误检。实验结果表明，提出的方法可以消除由于插入结构相同的语句而引起的克隆代码的误检问题，并在此基础上，有效消除了语句形式一样但由于语句顺序颠倒而引起的克隆代码误检问题，提高了克隆代码检测及克隆代码相关缺陷检测的准确性，有利于后续克隆代码重构的研究。

关键词：克隆代码； 哈希值； 标识符冲突率； 误检； 重构

中图分类号：TP311 文献标识码：A 文章编号：2095-2163（2013）05-0046-04

0引言

克隆代码（Cloned Code），又称作重复代码（Duplicated Code），是指源代码文件中多个相同或相似的代码片段[1]。

克隆代码在大多数情况下是有害无益的，因其增加了软件系统代码的长度，使得软件系统愈加复杂、难以维护，同时系统运行效率也会降低，并且给软件引入大量的程序缺陷。

近年来，代码克隆的研究已成为软件工程领域的前沿课题。各国的软件研究人员竞相提出了多种检测克隆代码的方法，并陆续开发了多款自动检测大规模软件系统中克隆代码的工具[2]。国际上研究克隆代码检测的国家主要有日本、美国、英国等。国内研究克隆代码检测的科研院所主要有南京大学[3]、大连理工大学[4]和汕头大学[5]等。ZhenminLi和Shan Lu 等人在文献[6]中将数据挖掘与克隆代码检测结合，开发了克隆代码检测工具CP-Miner。另外，高效的序列模式挖掘算法既可显著提升检测速度，降低时间复杂性，也可以容忍经过增、删、改和变量重命名的克隆代码片段，并且对“拷贝-粘贴-修改”行为所导致的变量重命名不一致的软件缺陷也能即时进行检测。

但是，通过分析实际的程序却发现该方法存在一些误检问题。首先，如图1中程序所示（图中++用于标记克隆的语句）。其中可以看出，（a）和（b）中的第5行克隆语句的映射发生了错误（（a）中的第5行语句应该映射到（b）中第5行语句的下一行语句）。其次，如图2中程序所示。从中可以看出，由于语句顺序颠倒，图2（a）和（b）中的语句3和4的映射发生了错误。克隆代码片段的映射错误，不仅会导致后续对克隆代码相关缺陷检测的误检，如图3所示（由图1中的克隆代码检测的误检引起），而且会导致错误的语句相似度分析，从而影响克隆代码重构的准确性。

为解决上述问题，本文提出了使用语句哈希值和标识符冲突率来消除克隆代码部分误检的方法。该方法不仅可以处理由于插入相同语法结构的语句而导致的克隆代码的误检问题，而且还可以消除语句形式一样但由于语句顺序颠倒而引起的克隆代码误检问题。通过分析实际的程序代码证明本文方法可以增强克隆代码检测能力及提高克隆代码相关缺陷检测的准确性。

1.1基于频繁子序列挖掘克隆代码检测模型

基于频繁子序列挖掘克隆代码检测模型[3]可将程序代码转化为token串，再将token串转化为数字序列（每一行语句映射成一个数字），相同结构的语句则映射成相同的数字，如图1所示，生成数字序列数据库。引入数据挖掘算法中频繁子序列挖掘技术，将重复代码检测转化为序列挖掘问题，解决了以往算法时间复杂度过高，且不能识别经过修改的拷贝-粘贴代码的缺点。

1.2克隆代码相关软件缺陷检测模型

克隆代码检测的目的是为了解决与克隆代码相关的问题。基于序列挖掘的C克隆代码及相关软件缺陷检测模型在克隆代码检测后，根据其生成的克隆代码集合以及克隆代码相关源程序信息，进行了克隆代码相关缺陷的检测。

1.3标识符冲突率

为了识别标识符不一致的情况，通过计算克隆代码对的标识符冲突率来判断标识符不一致的发生位置。每个标识符的映射冲突率的计算公式如式（1）所示

该模型基本思路如下：首先对C源代码进行克隆代码检测，然后计算克隆代码对中每个标识符的冲突率。对于具有冲突的标识符，在上面两步的基础上，根据冲突发生的代码行位置，判断当前语句行的下一条语句与当前语句行的哈希值是否相等，如果相等，则将对应位置标识符作为当前匹配的标识符，计算标识符冲突率。如果新的标识符冲突率为零，说明发生了误检，则根据记录的语句行号调整克隆代码标记的相对行号。如果新的标识符冲突率不为零，则继续对当前行的上一条语句计算标识符冲突率。如果当[JP3]前语句行的下一条及上一条语句均已完成了标识符冲突率的计算，结果仍不为零，则表明没有发生误检，输出当前的检测结果即可。

2.2算法举例

以图1所示程序为例，在消除误检之前，输出如图3所示的缺陷检测结果。此种误检产生的原因是由于插入了一条语句所致，CloSpan算法可以成功识别插入或删除语句的克隆代码，但图1 （b） 中插入的是与克隆语句结构相同的语句，这种结构相同的语句则映射成相同的数字。以图1为例，即语句ll_puts （ buf ） 和语句va_end（args）均映射成相同的数字（76781968），数据挖掘之后，算法就误将语句（b）中的ll_puts （ buf ）与（a）中的va_end（args）当作克隆语句，进行匹配。这种错误的匹配将导致后续克隆代码相关缺陷检测的误检，仍如图3所示。

基于本文方法，首先，根据当前的标识符冲突率（1/4），记录当前冲突发生的位置（语句的行号），判断当前语句的下一条语句与当前语句的哈希值是否相等，即两条语句是否是结构相同；然后，将下一条语句对应位置的标识作为将匹配的标识符，重新计算标识符冲突率。如果冲突率为零，则说明当前语句的下一条语句是真正的克隆语句，进而，将当前语句的行号与下一条语句的行号交换，修正克隆代码检测结果。结果如图6所示。

这种方法不仅消除了插入语句的克隆代码的误检，而且，还消除了语句结构相同（数字相同）而语句顺序颠倒产生的误检。如果冲突率不为零，则说明当前语句的下一条语句不是真正的克隆语句。此时，本文方法继续判断当前语句的上一条语句与当前语句的哈希值是否相等，即两条语句是否为相同结构的语句，如果相等，则将上一条语句对应位置的标识符作为被匹配的标识符，重新计算标识符冲突率。如果冲突率为零，则说明当前语句的上一条语句是真正的克隆语句，进而，将当前语句的行号与下一条语句的行号交换，修正克隆代码检测结果。如果当前语句行的下一条及上一条语句计算完成标识符冲突率后，结果仍不为零，则表明没有发生误检，即输出当前的检测结果。

文中采用克隆代码检测工具CPBugdetector[7]分别对Linux_2.6.6源程序中的arch、net和kernel模块进行克隆代码及相关缺陷检测。比较消除误检之前和消除误检之后的缺陷检测结果如表1所示。

针对基于token的克隆代码检测方法进行语法相似的克隆代码检测时存在的部分误检问题，本文提出了一种克隆代码检测的部分误检消除的方法。该算法通过语句哈希值的比较找到结构相同的语句，再根据标识符冲突率确定误检消除情况。实验结果表明，本文算法能够消除传统克隆代码检测方法中的部分误检，提高了克隆代码检测的准确性。