基于程序依赖图的代码克隆检测算法研究

发布时间：2020-11-05 17:55

　　 近年来,随着开源软件项目的兴起和迅猛发展,代码克隆检测已经成为软件工程领域一个越来越重要的研究课题,很多软件工程下游应用如代码重构、软件维护、bug和恶意代码以及软件剽窃检测都需要将此作为第一步。目前高级别的代码克隆检测仍然是一项困难工作,PDG(Program Dependence Graph)代码克隆检测可应用于语法、语义和结构功能上相似代码检测,属于高级别代码检测。这类研究中存在着候选PDG对规模大以及子图同构判定时间长等问题。为此,本文在基于PDG结构优化、特征向量过滤和克隆判定算法上进行了深入研究。主要工作和贡献包括:(1)提出并实现了一个基于PDG的代码克隆检测工具CCSharp针对现有典型的基于PDG代码克隆检测方法存在PDG图规模较大、候选PDG对数多的问题,本文设计了 PDG图优化和候选PDG对过滤方法。首先,我们对PDG生成工具产生的PDG图进行结构优化,采取去除节点和合并节点的方式来降低PDG图规模,从而减少PDG同构判定的时间消耗。其次,在优化后的PDG上,我们设计了一种PDG特征向量过滤算法来去除掉非克隆的PDG对以降低候选PDG对数。最后,在优化和过滤方法基础上设计了一种基于PDG的代码克隆检测工具CCSharp。计算实验表明,PDG图优化方法能使PDG图规模平均缩小超过1/3;特征向量过滤方法比传统的GPALG过滤效果提高了上百倍;CCSharp方法同其他三种代码克隆检测工具相比,在less和Postgresq1数据集上分别能达到91.7%和99.3%的准确率以及91.7%和89.8%召回率。(2)提出并实现了一种基于图核相似度计算的机器学习PDG代码克隆检测方法虽然对传统PDG代码克隆检测方法进行优化和过滤之后,代码克隆检测时间有明显提升,但仍然存在处理时间消耗长的问题,我们尝试将非精确的图相似度计算方法(图核函数)和机器学习方法应用于PDG代码克隆检测中。对于一个或一组图核函数,我们设计一个或一组PDG相似度矩阵,作为机器学习方法的输入,再通过对数据集的人工标记后,应用SVM训练出一个分类模型来进行PDG克隆判定。计算实验表明,分类模型预测的精度能达到70%-95%,同时其时间消耗要比子图同构判定方法要少。
【学位单位】：中国科学技术大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP311.5
【部分图文】：

１．２．２基于ｔｏｋｅｎ的代码克隆检测技术??基于ｔｏｋｅｎ的代码克隆检测方法首先将整个源系统代码通过词法解析工具转??化为ｔｏｋｅｎ序列。源码经过转化后得到的一个个单词即称为ｔｏｋｅｎ，如图１．１。接??着扫描转化后的ｔｏｋｅｎ序列以寻找相似或者相同的ｔｏｋｅｎ子序列，子序列对应的??原代码的部分就被报为克隆代码。对比于基于文本的方法，基于ｔｏｋｅｎ的方法对??于检测具有不同格式的代码通常更有鲁棒性。??先进的基于ｔｏｋｅｎ的代码克隆检测技术很多如ＣＰ－Ｍｉｎｅｒ［１１］，ＣＣＦｉｎｄｅｒ［１（）＾??等，其中日本的Ｋａｍｉｙａ等人发表的ＣＣＦｉｎｄｅｒ工具的做法如下：首先通过一个词??法解析工具将所有源码文件的每一行代码都转化为一个个的ｔｏｋｅｎ并将所有文件??的ｔｏｋｅｎ连接合并为一个单一的ｔｏｋｅｎ序列。然后针对所感兴趣语言标识符的结??构和标准化方法对合并的大ｔｏｋｅｎ序列做一些ｔｏｋｅｎ的增加，删除和改变的变换。??变化的目的是将标识符包括类型，变量及常量都替换成特殊的＾１＾１１。这样的标??识符替换方法使得那些仅是变量名不同的代码块也可以被检测为克隆代码对。接??着，用一个基于子字符串的后缀树匹配算法在变化后的ｔｏｋｅｎ序列中寻找相似的??子序列

图２．１控制流程图（ＣＦＧ）??表２．１集￥?Ｓ中所有边的控制￥赖关系Ｓ中的边?控制依赖于?标签??１?Ｔ１?Ｆ２?Ｔ２?Ｆ??３??Ｔ系??数据依赖子图的构造过程中，图中节点所表个运算符级别的子图。这种子图在没有由调用所带来的副作用时几乎非常容易构建。

不管针对什么样的语言做的检测，使用什么样的ＰＤＧ生成工具和应用什么??样的克隆寻找和判定算法，绝大多数的方法都有着总体相似的代码克隆检测流??程。在图２．２中，我们给出了?ＰＤＧ代码克隆检测方法流程中的重要环节或步骤，??其中虚线部分表示在一些早期工作或是小规模数据集上的工作中并没有考虑的??降低克隆比较空间的步骤，但是在实际的代码克隆检测过程中这却是非常重要和??实际需要考虑的内容。??，一＇、?ｉ?：?ｒ—＾＾??、＿＿乂通过生成?丨降低克隆｜?ＰＤＧ对的?、＾??源代——＾工具产生——比较空间；——＾克隆判定——＾克隆??码?源码的?ｉ以减低时；?及克隆的?ｔ结果??＾＞?ＰＤＧ?丨间消耗?丨?聚类?＾＾??＼?Ｊ??」?Ｖ?Ｊ??图２．２?ＰＤＧ代码克隆检测的流程??基于ＰＤＧ代码克隆检测方法的总体流程主要包括三个重要的步骤，分别如??下：??（１）?ＰＤＧ生成：源代码中的程序语句作为一种高级抽象的逻辑和运算表示??并不能很好的简单被机器理解和支持。在代码的编译运行的过程中，是先将高级??语言通过各种编译器转化成计算机可以支持的汇编代码或机器指令，再生成相应??的二进制可执行代码运行的。相似地，在代码克隆检测方法中也首先需要将这些??高级语言转化成较容易理解和处理的形式。在基于ＰＤＧ的方法中
【相似文献】

相关期刊论文 前10条

1 张春英;张雪;;不确定属性图的子图同构及其判定算法[J];计算机科学;2013年06期

2 张一楠;邹兆年;李建中;;不确定图间α-β子图同构匹配算法[J];智能计算机与应用;2011年05期

3 陈新泉;;图同构的判定研究[J];集成技术;2013年06期

4 张硕;李建中;高宏;邹兆年;;一种多到一子图同构检测方法[J];软件学报;2010年03期

5 周克元;;图同构的一个算法[J];和田师范专科学校学报;2007年02期

6 刘富贵;;两图同构的一个必要条件和一个充要条件[J];武汉水运工程学院学报;1992年02期

7 刘波;房斌;张世勇;李直霖;;基于关系模型的子图同构检测算法设计与实现[J];计算机工程;2011年11期

8 王毅;丁函;任丹;;一种无向图同构的判定算法[J];科技创新与应用;2012年28期

9 侯爱民;郝志峰;胡传福;陆海鹏;;无向图同构的快速算法[J];华南理工大学学报(自然科学版);2011年10期

10 侯爱民;;图同构的一个充分必要条件[J];计算机工程与应用;2009年30期

相关博士学位论文 前4条

1 商慧亮;一种新的图同构判定算法[D];复旦大学;2009年

2 张硕;图数据库查询处理技术的研究[D];哈尔滨工业大学;2010年

3 侯爱民;哈密顿环与图同构问题的理论研究及算法设计[D];华南理工大学;2013年

4 商慧亮;一种新的图同构判定算法——电路模拟法[D];复旦大学;2009年

相关硕士学位论文 前10条

1 汪敏;基于程序依赖图的代码克隆检测算法研究[D];中国科学技术大学;2018年

2 刘杨;基于大图处理框架的分布式子图同构研究[D];北京邮电大学;2018年

3 吴楠;有向图子图同构计算算法研究[D];辽宁大学;2012年

4 李美云;子图同构问题中索引构建方法研究[D];燕山大学;2017年

5 王小涛;基于子图同构搜索的徽派建筑快速建模方法研究[D];合肥工业大学;2013年

6 李辰辰;基于非挖掘索引的图查询研究[D];辽宁大学;2014年

7 韩玉;基于图数据的子图同构算法研究[D];燕山大学;2015年

8 张一楠;图结构数据上的子图查询[D];哈尔滨工业大学;2011年

9 张海龙;图的同构问题算法研究[D];华中科技大学;2007年

10 潘佳文;PTC-SaaS中基于图匹配的租约推荐方法研究[D];东北大学;2012年

本文编号：2871987