基于后缀数组的克隆代码检测研究

摘要

克隆代码是指软件中相同或相似的源代码段，其在软件开发与维护中具有重要的影响。近十年来，克隆代码的检测已成为软件维护中的一项重要研究内容。学者们也相继提出了许多克隆检测方法与技术，也实现了一些优秀的检测工具。然而，随着软件规模不断增大，现有克隆检测技术在时空效率上仍然不高。
　　本文基于后缀数组这一简单而高效的数据结构，结合Type-1和Type-2函数克隆的句法特征，以重点开展具有低时空复杂度的克隆检测技术的设计研究。首先，根据函数克隆的相似性定义，设计相应的词法分析程序以消除源代码表面上的差异，识别并标记其中的函数或方法，进而转换成标准化的Token串。其次，采用前缀倍增算法构造Token串的后缀数组。然后，根据比较单元为函数这一特征，改进现有的计算最长公共前缀算法，以构造出公共函数前缀数组。接着，设计重复函数子串的查找算法，进而检测出Token串中所有的重复函数子串。最后，结合词法分析阶段的位置信息，以克隆群的形式过滤并反馈软件中的函数克隆。
　　基于上述研究成果，本文设计并实现了一款与程序设计语言无关的克隆检测工具FCD。本文也利用FCD检测了24款C语言的开源软件，从多个维度深入地分析了这些系统的克隆特点。通过大量的实验结果验证了FCD具有很低的时空复杂度，能快速地地检测大规模软件系统，同时保证了较为理想的误报率与漏报率。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．2 研究意义

1．3 研究目标

1．4 本文的贡献及内容安排

第2章 相关工作

2．1 克隆代码的相关术语

2．2 克隆代码的产生原因

2．3 国内外研究现状及分析

2．3．1 克隆代码的检测研究

2．3．2 克隆检测的相关应用

2．3．3 其它的重要研究内容

第3章 克隆代码的检测方法

3．1 源代码的转换

3．1．1 源代码的单词化

3．1．2 函数的识别及标记

3．2 重复子串的查找

3．2．1 后缀数组等概念

3．2．2 重复子串查找算法的设计

第4章 克隆检测工具的实现

4．1 检测前端

4．2 检测后端

第5章 实验结果的分析与比较

5．1 度量单位(Metric)

5．2 检测的时空效率

5．2．1 时间复杂度

5．2．2 空间复杂度

5．3 检测的准确性

5．4 一些有意义的发现

第6章 结论与展望

6．1 研究结论

6．2 研究的不足

6．3 研究展望

参考文献

致谢

攻读学位期间发表的论文