基于抽象语法树的软件语义分析方法研究

摘要

随着计算机科学技术的发展，软件质量面临着新的任务和考验，软件语义分析作为一种提高软件质量的重要手段受到了社会的广泛关注。但是，目前主要的软件语义分析方法普遍存在着时间复杂度高、结果不准确的问题。论文提出了一种重建抽象语法树的算法，在很大程度上减少了抽象语法树的节点个数；然后，在该抽象语法树的基础上，提出了一种系统依赖图的优化算法，有效地降低了系统依赖图的规模；最后，论文基于简化的系统依赖图的可达性算法计算程序的切片，完成整个软件的语义分析。论文提到的软件语义方法对提高软件语义分析的速率和准确率具有很重要的意义。
　　论文首先对GCC（GNU Compiler Collection，GNU编译器集合）产生的抽象语法节点的结构以及每部分的含义进行了简单介绍。针对GCC编译器产生的抽象语法树节点结构混乱，冗余节点多的问题，论文提出了一种基于 GCC标准化文件的抽象语法树重建算法，通过对GCC产生的抽象语法树进行节点规范化、删除冗余节点等操作后，生成只包含有用节点的GCC标准化文件，基于该文件重建程序的抽象语法树，有效地减小了抽象语法树的节点规模。其次，论文提出了一种基于控制依赖图构建程序控制流图的算法，打破了传统系统依赖图中先建立控制流图，再建立控制依赖图的常规流程。如果用户只需要控制依赖关系，则可省略后续部分的操作，给软件语义分析带来了良好的灵活性。再次，在该抽象语法树的基础上，提出了一种基于依赖图等价代换的SSDG（simplified system dependence graph，简化的系统依赖图）构建算法，采用依赖图等价代换的思想，用程序依赖图代替系统依赖图，有效地降低了构建系统依赖图的复杂度。最后，论文采用基于SSDG可达性算法计算程序的动态切片，通过将程序执行过程分解为循环和非循环的两种情况，有效地避免了图的可达性算法中无法正确标记循环边的缺陷，并且图的可达性算法能够有效地避免数据流方程算法中因反复迭代造成的时间复杂度高的缺陷。
　　论文采用VS2010仿真平台对文中提到算法进行模拟实现，实验证明，论文提到的软件语义分析算法与传统的分析算法相比，能够高效准确地计算程序切片。

目录

封面

声明

中文摘要

英文摘要

目录

第1章绪论

1.1选题背景及意义

1.2软件语义分析相关技术研究现状及分析

1.4主要研究内容

1.5论文组织结构

第2章基于GCC标准化文件的抽象语法树重建算法

2.1 软件分析方法介绍

2.2引入抽象语法树的原因

2.3抽象语法树相关问题及分析

2.4抽象语法树的重建算法研究

2.5本章小结

第3章基于依赖图等价代换的SSDG构建算法

3.1控制依赖图的生成算法

3.2控制流图的生成算法

3.3数据依赖图

3.4程序依赖图

3.5基于依赖图等价代换的SSDG生成算法

3.6本章小结

第4章基于SSDG可达性的动态切片生成算法

4.1程序切片相关理论介绍

4.2引入程序切片的意义

4.3基于数据流方程的切片算法

4.4 基于SSDG可达性的动态切片生成算法

4.3本章小结

第5章实验及结果分析

5.1 实验目的

5.2实验参数

5.3实验环境

5.4实验过程

5.5实验结果分析

5.6本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢