路径敏感的跨过程别名分析的设计与实现

论文摘要

别名分析在提高数据流分析精度和构建性能良好的程序分析工具方面发挥着重要作用。本文在分析已有别名分析框架的基础上，提出并实现了一种路径敏感的跨过程别名分析方法。首先，通过对比分析不同跨过程别名分析的方法，设计并实现了一种基于函数别名模式的记忆式分析方法。该方法采用扩充变量来解决函数别名模式的抽象表示问题，并在此基础上通过构建表达式映射表来计算别名模式以及设计别名模式的相容性判定策略。其次，针对别名分析的路径敏感特征，提出并实现了一种检测控制流图中不可达路径的方案，该方案通过ANTLR提供的树遍历器遍历分支语句表达式的抽象语法树，以达到静态计算表达式真假值的目的。最后，进行了函数别名模式相容以及不可达路径检测的实例分析，结果表明本文实现的方法可以高效地进行跨过程别名分析，并在分析过程中能够有效地检测出不可达路径，进而指导数据流的精确分析。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 程序分析和静态检查
• 1.1.2 别名分析的相关工作
• 1.2 C/C++静态安全检查工具
• 1.3 本文工作及内容组织
• 第二章 相关工具技术及别名分析框架
• 2.1 相关工具和技术
• 2.1.1 ANTLR概述
• 2.1.2 抽象语法树
• 2.1.3 符号表
• 2.1.4 二叉决策图
• 2.2 别名分析框架和方法
• 2.2.1 别名分析框架
• 2.2.2 别名信息的表示
• 2.2.3 过程内别名分析
• 2.2.4 跨过程别名分析
• 第三章 跨过程分析的设计与实现
• 3.1 跨过程分析的整体设计
• 3.1.1 跨过程分析的三种方法
• 3.1.2 基于记忆式的跨过程分析框架
• 3.2 基于记忆式的别名模式设计
• 3.2.1 别名模式的基础
• 3.2.2 别名模式的表示
• 3.2.3 影响别名模式的因素
• 3.2.4 别名模式的计算
• 3.2.5 别名模式的相容性判定
• 3.3 跨过程分析中相关问题的处理
• 3.3.1 被调函数到调用点的别名信息反映射
• 3.3.2 函数返回值的处理
• 3.3.3 函数递归调用及函数指针的处理
• 3.3.4 类成员函数的处理
• 3.4 别名分析提供的接口
• 3.5 本章小结
• 第四章 路径敏感分析的设计与实现
• 4.1 不可达路径研究的基础
• 4.1.1 数据流分析的三种解
• 4.1.2 不可达路径的定义和分类
• 4.1.3 不可达路径检测的意义及相关工作比较
• 4.2 检测不可达路径的设计与实现
• 4.2.1 检测不可达路径的设计框架
• 4.2.2 假分支AST的重构及优化
• 4.2.3 条件表达式的检测策略
• 4.2.4 语义检测不可达路径的实现
• 4.2.5 路径优化策略
• 4.3 本章小结
• 第五章 实例分析
• 5.1 函数别名模式相容的实例分析
• 5.2 不可达路径检测的实例分析
• 第六章 结束语
• 致谢
• 参考文献