结构语义相似的程序识别方法研究

论文摘要

程序识别使用一个已知模式分析给定程序,从而识别给定程序的意图。程序识别在程序理解、软件系统分析、编译器优化、重复代码检查和软件缺陷检测等领域中有着广泛的应用。本文提出结构语义相似的程序识别方法。主要研究内容包括以下四部分:针对代码多样化给程序分析带来困难的问题,提出基于系统依赖图的程序标准化方法。改进了传统的系统依赖图表示,使其充分表示程序的语法结构与语义。并针对已有的指针分析算法不适合于程序标准化的问题,基于控制依赖树和改进的指向表示方法提出流敏感和上下文敏感的指针分析算法,提高指针分析和数据流分析的准确性,并使得指针分析结果可直接应用于程序标准化转换中。最后将改进的系统依赖图、指针分析算法与程序标准化过程有机结合,提出基于系统依赖图的程序标准化模型,根据程序标准化转换规则,对系统依赖图进行语义不变的转换,从而消除代码多样化。实验结果表明,本文提出的指针分析算法准确性高于已有的Emami指针分析算法的准确性,并且应用于程序标准化时可显著提高代码多样化消除率。本文的程序标准化方法的代码多样化消除率高于已有的Hattori与Ishi方法的代码多样化消除率,可以有效地消除代码多样化,提高程序分析的灵活性,为判定程序的结构语义相似奠定良好的基础。针对基于图提取子程序时间与空间开销巨大的问题,提出结构度量相似的候选子程序提取方法。在已有的代码相似度及编辑距离的定理和推论的基础上提出新的推论,将特征向量聚类应用于候选子程序提取中。首先,将代码表示为控制依赖树,通过基本代码标准化,消除影响度量值计算的代码多样化。然后,采用特征向量描述程序的结构信息,将复杂的图的相似度求解问题转换为简单的相似向量的聚类问题,快速提取可能与给定模式相似的候选子程序。实验结果表明,该方法能够过滤掉大部分不相似代码,并且可以识别含有代码多样化的代码,为大规模软件在语义级别上的程序识别奠定基础。针对已有的程序识别方法不能较好地在语义级别上识别程序,并且不能定量地衡量代码的语义相似度的问题,提出基于系统依赖图的语义级别的程序识别方法。在此基础上提出基于程序转换和语义分析的编程题自动评分方法,克服了传统的基于动态测试自动评分和基于软件度量分析的自动评分方法没有考虑学生程序是怎样实现编程任务的缺陷,为编程题自动评分提供新思路。实验结果表明,基于系统依赖图的语义级别的程序识别方法能够准确计算代码的语义相似度,较好地解决程序识别结果的表示和准确性问题。针对传统基于度量值的程序识别方法准确率低和基于图的程序识别方法复杂度高的问题,在上述研究的基础上,提出度量值和图相结合的程序识别方法。首先,将模式程序和用户程序表示为改进的系统依赖图。然后,以模块为单位,采用结构度量相似的候选子程序提取方法,缩小语义级别程序识别的搜索空间,提高算法的效率。最后,对可能相似的候选子程序进行高级代码多样化和精确的语义级别的程序匹配,识别语义相似的子程序。在此基础上提出语义级别的相似代码检测方法,为相似代码检测提供新思路。实验结果表明,度量值和图相结合的程序识别方法可以有效地处理大规模代码,不但能识别完全相同的代码,还可以识别包含代码多样化的相似代码,实现语义级别的程序识别,准确率和效率高于GPlag和integrated logic-domain model两种方法。综上所述,本文提出了结构语义相似的程序识别方法,解决了代码多样化的识别、识别结果的表示和准确性、识别方法的可扩展性等关键技术问题。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题来源
• 1.2 课题的目的和意义
• 1.3 程序识别在国内外的研究现状及分析
• 1.3.1 基于抽象模式的程序识别方法
• 1.3.2 基于文本的程序识别方法
• 1.3.3 基于度量值的程序识别方法
• 1.3.4 基于结构的程序识别方法
• 1.3.5 基于图的程序识别方法
• 1.3.6 已有程序识别方法的比较
• 1.4 问题描述及难点分析
• 1.4.1 结构语义相似的程序识别的定义
• 1.4.2 结构语义相似的程序识别的难点问题
• 1.5 主要研究内容
• 第2章 基于系统依赖图的程序标准化方法研究
• 2.1 引言
• 2.2 理论基础
• 2.2.1 代码多样化
• 2.2.2 系统依赖图
• 2.2.3 指针分析
• 2.3 改进系统依赖图表示程序的语法结构与语义
• 2.4 程序标准化转换中的指针分析算法
• 2.4.1 指针别名分析中指针指向表示法的改进
• 2.4.2 指针分析的数据流公式
• 2.4.3 指针赋值语句节点的指向分析算法
• 2.4.4 指针赋值语句节点的指向分析实例
• 2.4.5 基于控制依赖树的流敏感和上下文敏感的指针分析
• 2.5 基于系统依赖图的程序标准化
• 2.5.1 基于系统依赖图的程序标准化模型
• 2.5.2 基本代码标准化
• 2.5.3 高级代码标准化
• 2.6 实验结果及分析
• 2.6.1 指针分析准确性分析
• 2.6.2 代码多样化消除率
• 2.6.3 程序标准化中指针分析效果
• 2.7 本章小结
• 第3章 结构度量相似的候选子程序提取方法研究
• 3.1 引言
• 3.2 理论基础
• 3.2.1 结构相似度度量
• 3.2.2 位置敏感的哈希算法
• 3.2.3 相关定义及定理
• 3.3 结构度量相似的候选子程序提取
• 3.3.1 结构度量相似的候选子程序提取模型
• 3.3.2 问题的形式化定义
• 3.4 生成控制依赖树的特征向量
• 3.5 特征向量分组聚类
• 3.5.1 向量分组算法
• 3.5.2 基于LSH的相似结构分支检测
• 3.6 合并分支检测大的相似代码片段
• 3.7 计算复杂度分析
• 3.8 实验结果及分析
• 3.8.1 提取候选子程序的效果
• 3.8.2 代码多样化识别效果
• 3.9 本章小结
• 第4章 基于系统依赖图语义级别的程序识别方法研究
• 4.1 引言
• 4.2 编程题自动评分方法的研究现状
• 4.3 基于系统依赖图的语义级别的程序识别
• 4.3.1 基于系统依赖图的程序识别模型
• 4.3.2 程序的结构匹配
• 4.3.3 程序的语句匹配
• 4.4 基于程序转换和语义分析的编程题自动评分方法
• 4.4.1 难点问题及解决方法
• 4.4.2 实例分析
• 4.5 实验结果及分析
• 4.5.1 实验数据
• 4.5.2 基于程序转换和语义分析的编程题自动评分准确率
• 4.5.3 与基于动态测试的编程题自动评分方法的比较
• 4.6 本章小结
• 第5章 度量值和图相结合的程序识别方法研究
• 5.1 引言
• 5.2 相似代码检测方法研究现状
• 5.3 问题的形式化定义
• 5.4 度量值和图相结合的程序识别模型
• 5.5 以模块为单位提取候选子程序
• 5.6 语义级别的相似代码检测方法
• 5.7 度量值和图相结合的程序识别实例
• 5.8 MGCA的计算复杂度分析
• 5.9 实验结果及分析
• 5.9.1 实验设置
• 5.9.2 MGCA的相似度阈值设置
• 5.9.3 MGCA 的健壮性测试
• 5.9.4 代码多样化的识别效果
• 5.9.5 效率测试
• 5.9.6 应用MGCA分析GCC1.4 与GCC2.0
• 5.10 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的学术论文
• 致谢
• 个人简历