基于非精确图匹配的代码克隆检测方法研究

发布时间：2023-05-24 22:23

　　近年来,代码克隆检测在软件开发,维护以及bug检测中的意义越来越重要。目前对于存在文本差异的克隆检测,即学术界定义的级别3和级别4,现有方法存在检出率不高的问题。程序依赖图(PDG,Program Dependency Graph)包含源代码的语法和结构信息,因此基于PDG的方法能够发现一些其他方法难以发现的程序结构相似或者相同的代码。但是这类方法主要基于子图同构检测等精确图匹配算法,算法复杂度高且无法发现代码之间存在的局部相似性。因此,如何更快速,全面和准确地进行图相似性计算是基于PDG进行代码克隆检测面临的一大挑战。为此,本文首先对PDG对集合进行了本身结构的简化和过滤,并对非精确图匹配算法进行了深入研究,主要研究内容和贡献如下:(1)PDG预处理及过滤方法设计我们对代码分析工具生成的PDG进行了研究和分析,发现其中包含很多由于PDG生成工具配置而生成的与源代码信息无关的冗余节点,造成了 PDG规模的增加,影响后续的节点匹配工作。基于此,本文提出了一种PDG结构简化的启发式策略,对这些节点和边进行了剔除,并对代码块中第三方库函数调用的冗余子图进行了合并。另外,对所有的候选克隆对直接...

【文章页数】：81 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 研究背景及意义
    1.2 研究现状和发展趋势
        1.2.1 基于文本/Token的代码克隆检测方法
        1.2.2 基于语法结构的代码克隆检测方法
        1.2.3 基于特征的代码克隆检测方法
        1.2.4 基于机器学习的代码克隆检测方法
        1.2.5 其他代码克隆检测方法
    1.3 本文研究工作
        1.3.1 PDG的预处理及过滤方法设计
        1.3.2 基于WL图核的代码克隆检测方法设计
    1.4 论文组织
第2章 问题定义及相关工作
    2.1 预备知识
        2.1.1 代码表示形式
        2.1.2 代码克隆相关概念
        2.1.3 非精确图匹配算法
    2.2 问题定义
        2.2.1 一般代码克隆检测定义
        2.2.2 PDG代码克隆检测定义
    2.3 现有PDG克隆检测方法
        2.3.1 基于子图同构的PDG克隆检测方法
        2.3.2 基于程序切片的PDG克隆检测方法
        2.3.3 基于深度学习的PDG克隆检测方法
    2.4 本章小结
第3章 PDG预处理及过滤方法设计与实现
    3.1 问题分析
        3.1.1 问题描述
        3.1.2 解决思路
    3.2 PDG约简及过滤方法设计
        3.2.1 PDG的生成及数据格式
        3.2.2 PDG的结构约简
        3.2.3 PDG对初始集合的过滤
    3.3 实验结果与分析
        3.3.1 数据集及评估指标
        3.3.2 PDG结构约简实验
        3.3.3 PDG对初始集合过滤实验
    3.4 本章小结
第4章 基于WL图核的克隆检测方法设计与实现
    4.1 问题分析
        4.1.1 问题描述
        4.1.2 解决思路
    4.2 基于Weisfeiler-Lehman图核算法的克隆检测
        4.2.1 PDG中标签数值化
        4.2.2 PDG对相似度计算
        4.2.3 PDG克隆对判定
    4.3 实验结果与分析
        4.3.1 数据集及评估指标
        4.3.2 代码克隆检测实验结果及分析
    4.4 本章小结
第5章 总结
    5.1 本文工作
    5.2 本文贡献与创新之处
    5.3 下一步工作
参考文献
致谢
在读期间发表的学术论文与取得的研究成果
攻读学位期间参加的科研项目



本文编号：3822395