上下文敏感的横向传播方法∗

邓朝日 刘鹏辉 顾梦园

（中国电子科技集团公司第三十二研究所 上海 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时，结点所对应的变量上下文无关，相反上下文敏感。例a⊇ ｛ρb｝，若b具备上下文无关性，a具备上下文敏感性，则图中有结点a（cs为true，ct为空）和b（false和ρ分别是cs和ct的值），既在上下文ρ下，b被a所指向。白色圆圈代表该变量上下文敏感，黑色圆圈代表该变量上下文无关。

另一方面，边分为三种类型：普通边（实线箭头）；返回边（调用返回用虚线箭头表示），表示接收返回变量值的变量的边被返回变量所指向；调用边（函数被调用用实线箭头表示），即形参的边的边被实参所指向。边E（v，w，γ，ρ）上的标识为ρ（ρ为⊺时边上无标识）。v、w分别为边头和尾结点；γ为类别：普通边值为1，调用边值为2、返回边值为3；若变量v要被变量w包含（在ρ下），则1为γ的值，且上下文集为ρ；若该边为函数调用（在点m处），则2为γ的值，m为ρ的值，其中实参为v、形参为w；若调用返回为该边类型，则3为γ的值，m为ρ的值，其中返回变量为v、获取其值的变量为w。如（b，a，1，ρ）为普通边，对应于a⊇ρb；（b，f。，2，ι）为调用边，（f·，a，3，ι）为返回边，均对应于a⊇ （fb）1。

2.2 初始化约束图

上下文敏感是指，a既不是被取地址的局部变量，或全局变量，也不是堆变量。上下文无关是指a是被取地址的局部变量、或全局变量，再或者堆变量。假设函数的指针以及函数的调用图［5］已经被上下文无关指针分析求出，变量无重名。

⊺即为初始的约束集中值的上下文标识，也是初始的约束集中变量约束的上下文标识，ρι=（ι，⊺，⊥）是一个上下文，其对应每个调用点ι。ρ1=（1，⊺，⊥）是点1的上下文、ρ2=（2，⊺，⊥）是点2的上下文。y，x，q，p均为上下文无关，w，v，d，s，c，a，e，b，t，均为上下文敏感。

图1（a）用相同名字的结点代替集中的所有变量，所有结点的cs属性被初始化；值约束将继而被设置，其右侧变量的属性将被设置相应的值，例如⊺为b中ct的值，该结果是由a⊇⊺b导致的；后为每个变量约束添一边到图，此边的属性将被初始化，例如（e，c，1，⊺）的增加是由c⊇⊺e所导致；函数调用约束继而被增加，例如，边（t，v，3，1）、（a，s，2，1）和（b，t，2，1）的增加是由v⊇（fa，b）1所导致。

当⊺为右下标为x的ct属性值时（例如指向集中的xρ），在指向集中x是结点x的表示方式。

3 横向传播（具备上下文敏感性）

文中未说明符号同文献［5］、文献［11］。

3.1 新的横向传播方法框架

新WP方法如Algorithm 1，其为条件始终为真的while循环：输入为一原始约束图G=（V，E），输出为图中各结点到其指向集的映射；先调用Algo⁃rithm2在图中探索并合并环；再调用Algorithm4进行差异传播［6］；后调用Algorithm5处理复杂约束以添加新边，如无新边添加终止循环。

Algorithm1

1：while true

2：｛Algorithm 2；Algorithm4；Algorithm5

3：if no edge has been added

4：break｝

3.2 环探测和消除

Algorithm3结合文献［5］中的探测环方法：探测只由ρ值为⊺的普通边组成的环（第2行条件）。

Algorithm2 Input：G=（V，E）

1：I←0

2：for all v such that D（v）≠⊥

3：Algorithm 3

4：for all v such that R（v）≠v

5：unify（v，R（v））

如图1（b），探测出由（e，c，1，⊺）（c，e，1，⊺）组成的环，合并c，e为c，则c，e指向集为q⊺。

unify合并环的触发条件：环内每个结点的cs赋为false的前提是，环内有上下文无关的节点数量为一个及其以上；每个结点源的指向集共同组成环内节点的指向集；选一结点为代表。

Algorithm3.Input：a node v。

3.3 差异传播

Algorithm4（差异传播）结合规则［5］trans1、trans2、param1、param2、ret1、ret2、ret3，其对不同边及变量的cs属性等其他条件而采用对应操作。如Algorithm4第8～13行处理普通边，第6～9行处理规则trans1。

图1（b）经差异传播后如图1（c）。因（a，s，2，1）为调用边且s的cs值为true，则其上差异传播由Al⁃gorithm4第17～19行处理（param1），后｛pρ1｝为s的指向集；类似的，通过在（d，t，2，2）、（c，s，2，2）、（b，t，2，1）上进行差异化传播，｛xρ1，yρ2｝和｛pρ1，qρ2｝分别是t和s的指向集。因t的值等于true，同样v的cs值也等于true且（t，v，3，1）是返回边，又由于x.ct|1=ρ1|1=（1，⊺，⊥）|1=⊺（Restriction操作［5］），则据Algo⁃rithm4第27～29行处理（ret1），后v指向集为｛x⊺｝；在（t，w，3，2）上差异传播后，w指向集为｛y⊺｝。

Algorithm4第35～38行：在w、v均不上下文敏感的情况下，trans2、ret3呈现出：要v指向w，则需要置ct等于⊺；在w是上下敏感的且v是上下文无关的情况下，v可直接指向w指向的变量。

3.4 复杂约束的处理

算法5（即Algorithm5）结合ret1～3［5］和load1～2，用来处理复杂约束（除函数调用外）。

如处理复杂约束*s⊇t后，图1（c）变为图1（d）。｛pρ1，qρ2｝为s的指向集，如图1（c）所示。例如，因为pρ1中t的cs值是true，且图1（c）中无（t，p，1，ρ 1），所以按照算法5（既Algorithm5）第6～8行处理，添加该边并在此边上执行一次差异传播，如Algo⁃rithm5第15行，后p的指向集为｛x⊺｝；

图1 示例源程序的分析示例

因处理复杂约束*s⊇t后，再执行一次Algo⁃rithm 1while循环后，已无新边可添加，分析结束。

4 实验

因新算法用WP方法［11，15］改进环消除算法［5］，WP方法不影响被改进方法的精度，其目的是提高分析的效率。因此新算法的时效数据是实验要重点进行验证的指标项。

为了验证新算法的时间和环消除效率，测试方法与文献［4］保持一致。其中实验环境如下：主机内存12GB；CPU为Intel Core i7，主频为3.91GHz；实验代码用OCaml语言和BuBDDy［14］的hash-consing实现，并在CIL［12］下分析，实验数据为为先后6次分别对sqlite、python、tar、named、povray、make等程序开展的分析结果数据进行平均计算，测试结果如表2给出了6次分析的平均值及其波动范围。

其中，表1各列含义如下。

第3列为为程序中所有可能上下文；

第4列为上下文敏感变量数量；

第5列为上下文无关变量数量；

第6列代码行数（预处理后）。

另外，通过依次对同一个源程序进行环消除算法和新算法分析，并对比各自所消耗的时间记录于表2。经过分析，新算法的时间效率相比于环消除算法有所提升。

表1 实验源程序列表

表2 分析时间

5 结语

本文通过结合WP方法和环消除算法提出一新算法。测试说句体现环消除效率以及时间效率被新算法改善，同时能够保证换消除技术的精确性。未来将致力于在专业领域中实践该新算法。