论文部分内容阅读
在软件开发过程中,各种拷贝-粘贴-修改的编辑操作非常普遍。这种方式的代码重用往往使得代码基中出现很多重复或者相似的代码片段,也就是所谓的克隆代码。它虽然方便了开发者,但是也带来了一定的资源消耗,增加了软件维护的难度。学术界和工业界早在上世纪90年代就开始对代码克隆进行分析并研究代码克隆的检测方法,并且取得了不错的效果。但是随着软件规模的不断增长,先前的方法便出现了资源使用的瓶颈甚至无法在单机上工作。例如,由于需要把由不同公司或者组织开发的上千万行的软件代码进行相似度的比较,如果不能在一个合适的时间范围内获取代码克隆将使检测方法的有效性大打折扣。本文在论述了传统克隆代码检测方法的基本原理和关键技术的基础上,提出了新的基于索引和改进的字符序列匹配的克隆代码检测方法,并通过实验证实了本文方法在大规模软件代码检测中具有较好的效果。主要工作包括:(1)提出了基于索引的克隆代码检测方法。该方法将代码文本依次规范化为lexeme序列和语句段,利用语句段哈希值查找文本以及结构相似的克隆代码。由于在检测过程中lexeme序列被持久化,避免了重复生成中间序列和再次分段从而大大提高了检测速度。(2)提出了基于改进的Smith-Waterman算法的代码克隆检测方法,即在lexeme序列表示的基础上利用序列匹配算法检测文本或者结构相似的克隆代码。该方法通过调整得分矩阵有效解决了传统Smith-Waterman算法中存在的马赛克问题,同时通过改进回溯过程可获取最佳的局部代码相似序列。(3)本文在四个以Java语言开发的软件代码上进行实验。实验证实,与传统方法相比,将基于索引的方法在不牺牲原有精确率和召回率的基础上提高了代码的检测效率;而将改进前和改进后的Smith-Waterman方法分别用于检测克隆代码,则发现改进后的方法的精确率提高了1%左右、召回率提高了2%左右。