空指针解引用静态检测方法研究

论文摘要

C语言中的指针机制使程序员可以直接访问内存地址,具有很高的灵活性。但是由于指针操作不当而引起的动态内存错误也有很多,空指针解引用就是其中的一类。这些错误的存在导致了软件质量和可靠性的下降,而且采用传统的测试方法进行检测很难奏效。静态分析方法不需要运行程序,而是通过对程序代码的分析检查程序中隐藏的错误。本文采用静态分析技术对C程序中的空指针解引用错误进行检测。我们首先基于一种流敏感、上下文敏感的指针分析算法给出了一个表达式左值的计算方法。根据这一方法,我们可以判断任意给定的两个表达式是否为别名。然后,结合上述流敏感、上下文敏感的别名分析,本文针对C程序中的空指针解引用错误给出了一种需求驱动的后向数据流分析算法。算法首先假设已知程序中的某处发生了空指针解引用错误,然后从该结点出发,逆着控制流的方向追踪空值的赋值过程,最终通过错误表达式集合是否为空来判断初始结点处是否发生了错误。我们根据这一过程构造后向的数据流分析方程,最后通过不动点计算理论计算数据流方程的解。在求解过程中,本文使用传统的worklist算法框架对不动点进行迭代计算。我们在SUIF2编译平台上实现了这一算法,并对一些C程序进行了分析,实验结果表明算法具有较高的检测精度。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 空指针解引用故障模型分析
• 1.2.2 动态内存错误检测方法
• 1.3 课题研究的主要内容和框架
• 1.3.1 课题研究主要内容
• 1.3.2 研究框架
• 1.4 本文的组织结构
• 第二章 空指针解引用检测相关研究
• 2.1 程序静态分析概述
• 2.1.1 程序控制流分析术语
• 2.1.2 过程调用图和过程间分析
• 2.2 数据流分析研究
• 2.2.1 数据流问题分类
• 2.2.2 数据流分析算法
• 2.3 本章小结
• 第三章 一种表达式别名分析方法
• 3.1 指针分析中的关键问题
• 3.1.1 指向信息的表示
• 3.1.2 指针分析精度
• 3.1.3 现有指针分析方法比较
• 3.2 基于指向图的表达式左值计算
• 3.2.1 指向图构成与元素的表示
• 3.2.2 表达式左值计算公式
• 3.3 算法实现
• 3.3.1 符号表处理
• 3.3.2 指针表达式左值计算
• 3.4 本章小结
• 第四章 需求驱动的空指针解引用静态分析
• 4.1 基本思想
• 4.1.1 分析过程示例
• 4.1.2 空指针解引用的类型状态规约
• 4.2 指针语言抽象
• 4.3 需求驱动的后向数据流分析
• 4.3.1 数据流框架与查询
• 4.3.2 空指针解引用数据流传播规则
• 4.3.3 基本块映射函数计算
• 4.3.4 空指针解引用算法实现
• 4.4 实验
• 4.4.1 试验结果与分析
• 4.4.2 相关工作与比较
• 4.5 本章小结
• 第五章 结束语
• 致谢
• 参考文献
• 作者在学期间取得的学术成果