论文部分内容阅读
近年来,随着开源软件项目的兴起和迅猛发展,代码克隆检测已经成为软件工程领域一个越来越重要的研究课题,很多软件工程下游应用如代码重构、软件维护、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%,同时其时间消耗要比子图同构判定方法要少。