学位论文 > 优秀研究生学位论文题录展示

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

作　者: 封战胜
导　师: 苏小红
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: GCC抽象语法树 控制流分析 数据流分析 控制流图 系统依赖图
分类号: TP311.11
类　型: 硕士论文
年　份: 2009年
下　载: 142次
引　用: 1次
阅　读: 论文下载
 

内容摘要


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

全文目录


摘要  4-5
Abstract  5-8
第1章 绪论  8-14
  1.1 课题研究的背景与意义  8-9
  1.2 基于程序语义分析方法的静态分析工具国内外研究现状  9-12
    1.2.1 程序缺陷检测工具国内外研究综述  9-11
    1.2.2 程序切片工具国内外研究综述  11-12
  1.3 课题研究的主要内容及章节安排  12-14
第2章 课题相关的理论基础  14-25
  2.1 GCC文本抽象语法树  14-15
    2.1.1 GCC抽象语法树结构  14-15
    2.1.2 GCC抽象语法树分类及常见符号含义  15
  2.2 控制流图  15-19
    2.2.1 控制流图概述  15-16
    2.2.2 语句的控制流图描述  16-19
  2.3 系统依赖图SDG  19-20
  2.4 面向对象系统依赖图及分层切片模型  20-23
  2.5 标准模板库STL  23-24
  2.6 本章小结  24-25
第3章 程序静态信息提取研究  25-30
  3.1 抽象语法树文本标准化  25
    3.1.1 抽象语法树文本标准化的原因  25
    3.1.2 标准化抽象语法树文本算法描述  25
  3.2 消除抽象语法树文本中的冗余信息  25-27
    3.2.1 消除AST文本中冗余信息的原因  25-26
    3.2.2 消除AST文本中冗余信息算法描述  26-27
  3.3 基于面向对象技术的源程序静态信息提取  27-28
    3.3.1 采用面向对象技术的原因  27-28
    3.3.2 对源程序设计语言的分类  28
    3.3.3 类之间的调用关系  28
  3.4 本章小结  28-30
第4章 程序系统依赖图生成方法研究  30-51
  4.1 生成系统依赖图的总体流程  30-31
  4.2 预处理  31-36
    4.2.1 确定语句范围  31-32
    4.2.2 switch语句标准化  32-33
    4.2.3 for语句标准化  33
    4.2.4 函数调用语句标准化  33-35
    4.2.5 语句排序  35-36
  4.3 控制依赖分析和控制依赖子图生成  36-38
    4.3.1 控制依赖子图  36-37
    4.3.2 跳转语句的处理  37-38
  4.4 控制流图的生成  38
  4.5 数据依赖分析和数据依赖子图生成  38-50
    4.5.1 到达—定值信息相关概念  38-40
    4.5.2 计算语句的REF、DEF 、GEN和KILL集合  40-43
    4.5.3 计算语句的IN、OUT集合  43-44
    4.5.4 建立数据依赖边  44
    4.5.5 计算过程间的数据流  44-46
    4.5.6 指针分析  46-50
    4.5.7 变量别名分析和数组变量分析  50
  4.6 本章小结  50-51
第5章 系统实现及测试分析  51-63
  5.1 系统总体设计与实现  51-54
  5.2 系统应用环境  54-55
  5.3 系统测试与分析  55-62
    5.3.1 源程序1 的测试与分析  55-57
    5.3.2 源程序2 的测试与分析  57-60
    5.3.3 源程序3 的测试与分析  60-62
    5.3.4 实验结果对比分析  62
  5.4 本章小结  62-63
结论  63-65
参考文献  65-69
致谢  69

相似论文

  1. 基于多样化对象所有权的软件可信性质研究,TP311.52
  2. 基于反编译的恶意代码检测关键技术研究与实现,TP309
  3. ARM反编译中的类型分析技术研究,TP368.1
  4. 基于告警关联的告警子系统的设计与实现,TN915.06
  5. 代码逆向分析中的语句恢复与算法识别技术研究,TP311.52
  6. C/C++程序安全检查工具中数据流分析器的设计与实现,TP311.11
  7. 全局数组数据流分析技术的研究与实现,TP338.6
  8. JSP跨站脚本漏洞静态检测技术的研究与实现,TP311.10
  9. Java数组越界检测系统的设计与实现,TP311.5
  10. GCC抽象语法树的解析及控制依赖子图的建立方法研究,TP311.11
  11. TD类漏洞及死锁检测系统的设计与实现,TP393.08
  12. 基于CFG多态蠕虫特征自动提取模型研究,TP393.08
  13. 自动化单元测试录制框架的研究与实现,TP311.52
  14. 考虑指针别名的静态分析技术研究,TP311.11
  15. 基于嵌入式软件的覆盖测试技术研究,TP311.52
  16. PHP程序静态分析系统的设计与实现,TP311.52
  17. 基于二进制可执行文件的控制流分析研究,TP309
  18. 基于程序切片的数据库变更影响分析系统的设计与实现,TP311.13
  19. 基于语法树结构优化和控制流图比对的软件同源性检测技术研究,TP311.52
  20. 高等职业卫生学校学生宿舍管理系统的设计,TP311.52

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 程序设计方法
© 2012 www.xueweilunwen.com