指针分析是指通过对程序的静态分析来近似地求取程序中指针变量确定或可能指向的目标,它在程序静态分析领域中非常重要,并且很有挑战性,其结果被广泛应用于程序的优化、安全分析和验证等方面。 由于C语言允许通过指针进行间接内存访问,但并不进行边界检查,因此可能存在缓冲区溢出。缓冲区溢出漏洞是最严重的软件安全弱点之一,发现和消除软件中的缓冲区溢出漏洞已成为信息安全领域的一个研究热点。静态分析能够在软件发布前发现软件中的缓冲区溢出漏洞,并且不会降低软件运行的效率。为了进行静态缓冲区溢出分析,必须首先进行高效而精确的指针分析,以确定指针可能指向的目标缓冲区。 对于缓冲区溢出静态分析,已有的指针分析算法存在复杂度太高或者分析精度太低的不足。本文针对缓冲区溢出静态分析的需求,提出了一个基于过程间指向副作用嵌入调度的流不敏感、上下文敏感指针分析算法,它分为两个阶段:自底向上阶段嵌入调度指向副作用,删除导致指向副作用的指针赋值语句,将整个程序转化成一个没有过程间指向副作用的程序;自顶向下阶段对转化后的程序进行CGBCI(Constraint-Graph-Based Context-Insensitive)指针分析,获得上下文敏感的指向结果。这个算法的优点是能够取得与完全过程嵌入等价的上下文敏感性质,对每个函数至多分析两次,所以不会导致复杂度呈指数增长。 基于LLVM编译器平台,我们实现了此算法,并应用此指针分析算法实现了一个缓冲区溢出静态分析工具。实验结果表明我们上下文敏感的指针分析算法能够提高缓冲区溢出静态分析的精度,具有较高的分析效率。