邓朝日 刘鹏辉 顾梦园

（中国电子科技集团公司第三十二研究所 上海 201808）

1 引言

指针分析是最基础的静态分析，解答了一个指针可能指向哪个对象的问题。上下文无关指针分析方法能够区分不同调用点的相同函数，合并所有调用。基于包含的指针分析方法［1］是其中一类重要的分析方法。二元决策图［2］在处理高度上下文敏感的指针分析时体现出较好的性能，但没有执行预定义约束，所以在进一步可扩展性分析［3～4］中没有体现出优越性。而Woongsik Choi等［5］发表的在调用图之上进行的上下文敏感指针分析和环消除算法（环消除算法）除了在时间分析效率上仍有改进空间之外，能够兼顾高上下文敏感性和高可扩展性。庆幸的是近二十年来出现很多基于包含的指针分析改进算法［6］，其中Fahndrich［7］、Pearce［8～9］、Harderkopf［10］、Pereira［11］陆续发表了不同的基于约束图进行的环消除算法。尤其Pereira［11］的横向传播（Wave Propagation，WP）最优秀，能大大提高分析的时间和空间效率。因而，本文将直观准确地表述上下文敏感横向算法并提出更有效实现环消除算法上下文敏感的WP算法。最后在CIL［12］下用OCaml语言实现分析，并对代码行范围20.000～290.000的6个程序进行分析，分析结果表明，上下文敏感的横向传播算法时间效率优于环消除算法。

2 约束图及约束图初始化

2.1 新的约束图

一方面，所有结点都有属性ct和cs：其中ct的值为上下文集，表示在该集下该变量被另一变量所指向，以上变量均为上下文无关；cs值为false时，结点所对应的变量上下文无关，相反上下文敏感。……