基于GCC抽象语法树文本的C源程序语义分析方法研究

摘要

本文致力于完成C语言源程序的系统依赖图的构造，系统依赖图是静态分析工具的基础，在逆向工程中具有重要意义。系统依赖图的构造可以归结为控制流分析和数据流分析，控制流分析主要是求取语句间的控制依赖关系，可以归结为父亲-孩子关系的求解。数据流分析主要是求取语句间的数据依赖关系，可以归结为到达-定值信息的求解。
　　本文提出了一种基于GCC抽象语法树文本的构造系统依赖图的新方法，首先，对GCC抽象语法树进行了深入的研究，统计出GCC抽象语法树中各个符号的含义，为后续研究奠定了基础。其次，对GCC抽象语法树文本进行了标准化及消除文本中与控制流分析和数据流分析无关的冗余信息。再次，用面向对象的思想来进行静态信息提取。最后，在构造系统依赖图时，本文没有采用传统构造系统依赖图的流程，而是首先建立了控制依赖图，其次在控制依赖图的基础上构建控制流图，再次在控制流图的基础上构建数据流图。同时本文给出了各个步骤的具体算法描述，其中包含了自己的算法及对以往算法的改进。为了提高数据流的精度，介绍了一些提高数据流精度的方法，比如指针分析、变量别名分析等等。另外，本文在设计系统时，也对每个过程的相关信息进行了统计，为用户查询模块奠定了基础。
　　本文最后一章给出了系统的详细设计，并对源程序进行了测试，验证了算法的可行性，通过与以往研究的对比，说明了该方法的优越性。

目录

基于GCC抽象语法树文本的C源程序语义分析方法研究

RESEARCH ON SEMANTIC ANALUSISOF C PROGRAM BASED ON GCC ABSTRACTSYNTAX TREE TEXT

摘要

Abstract

第1章 绪论

1.1 课题研究的背景与意义

1.2 基于程序语义分析方法的静态分析工具国内外研究现状

1.2.1程序缺陷检测工具国内外研究综述

1.2.2程序切片工具国内外研究综述

1.3 课题研究的主要内容及章节安排

第2章 课题相关的理论基础

2.1 GCC文本抽象语法树

2.1.1 GCC抽象语法树结构

2.1.2 GCC抽象语法树分类及常见符号含义

2.2 控制流图

2.2.1 控制流图概述

2.2.2 语句的控制流图描述

2.3 系统依赖图SDG

2.4 面向对象系统依赖图及分层切片模型

2.5 标准模板库STL

2.6 本章小结

第3章 程序静态信息提取研究

3.1 抽象语法树文本标准化

3.1.1 抽象语法树文本标准化的原因

3.1.2 标准化抽象语法树文本算法描述

3.2 消除抽象语法树文本中的冗余信息

3.2.1 消除AST文本中冗余信息的原因

3.2.2 消除AST文本中冗余信息算法描述

3.3 基于面向对象技术的源程序静态信息提取

3.3.1 采用面向对象技术的原因

3.3.2 对源程序设计语言的分类

3.3.3 类之间的调用关系

3.4 本章小结

第4章 程序系统依赖图生成方法研究

4.1 生成系统依赖图的总体流程

4.2预处理

4.2.1 确定语句范围

4.2.2 switch语句标准化

4.2.3 for语句标准化

4.2.4函数调用语句标准化

4.2.5 语句排序

4.3 控制依赖分析和控制依赖子图生成

4.3.1 控制依赖子图

4.3.2 跳转语句的处理

4.4控制流图的生成

4.5 数据依赖分析和数据依赖子图生成

4.5.1 到达—定值信息相关概念

4.5.2 计算语句的REF、DEF 、GEN和KILL集合

4.5.3 计算语句的IN、OUT集合

4.5.4 建立数据依赖边

4.5.5 计算过程间的数据流

4.5.6 指针分析

4.5.7 变量别名分析和数组变量分析

4.6 本章小结

第5章 系统实现及测试分析

5.1 系统总体设计与实现

5.2 系统应用环境

5.3 系统测试与分析

5.3.1源程序1的测试与分析

5.3.2 源程序2的测试与分析

5.3.3 源程序3的测试与分析

5.3.4 实验结果对比分析

5.4 本章小结

结论

参考文献

攻读学位期间发表的学术论文

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致谢

未标题

未标题