改进版field-sensitive指针分析算法

1.Introduction

这篇paper是SVF团队对PKH field-sensitive指针分析算法 ${}^{[2]}$ 的优化，在使用SVF时如果用该优化后的算法，添加运行参数 -sfrander，聚焦的是Andersen算法之上的field-sensitive（不考虑flow-sensitivity）。PKH算法的推导规则如下所示，在不考虑field-sensitivity时，只有 addrof 规则会在pts集合中生成新的address-taken variable，而现在 field 规则也会生成新的address-taken variable。

在该规则下，对于指针运算 q = p + j (p, q 是指针类型，j 是整数类型)，如果 p 是结构体指针或者指向数组，那么对于该类指令的处理等效于 q = p。

PKH算法的一个示例如下所示：

源代码：

typedef struct A {
	int idx; /* f0 */ 
	A* next; /* f1 */ 
} A;

A* p, q;
for(...){
	p = malloc(...);//o
	q = &p->next;
	p = q;
}

约束：

• { o } ⊆ p \{o\} \subseteq p {o}⊆p

• $p+1\subseteq q$ ($p+1$ 表示 p->next，即 p 的第1个field)

• $q\subseteq p$

求解过程如下图所示：

可以看到程序存在链表结构，其中会出现带正整数的环路（$p\stackrel{1}{\to }q$, $q\to p$，环路数值为1，这种环全称positive weight cycle，即PWC）。可以看到运行时:

• 不断有新的address-taken vairable被生成。为了避免无限生成，PKH设置了最大field访问层数。

• field-insensitive中用到的强连通分量分析不能直接用在PWC上，因为PWC中每个node的pts可能不同。

为了解决这个问题，作者提出了DEA算法，这是一个stride-based representation来压缩field object，与PKH的对比如下图所示，图中address-taken variable $o.f_3$, $o.f_5$, $o.f_7$ 都会被压缩为1个address-taken variable $o.f_{3+2k}$。这样一来减少了传播过程中的pts集数量以及求解 load/store 时新建的 copy 边数量。同时，像 $r$, $p_1$, $p_2$ 这样关键变量的pts集合没有发生改变。

2.Approach

2.1.Stride-based Field Representation

Definition 1 (Stride-based Field Representation, 简称SFR)：对于pts集中的address-taken variable，作者这里表示为三元组 $\sigma =<o,i,S>$，$o$ 为address-taken variable本身，$i$ 表示访问第 $i$ 个field，$S$ 为一个集合表示偏移量。$\sigma$ 的field expansion可以表示为：

F X ( σ ) = { { o } i f    S = ∅ ∧ i = 0 { o . f i ∣ j = i + ∑ n = 1 ∣ S ∣ k n . s n , j ≤ m a x , k n ∈ N , s n ∈ S } o t h e r w i s e FX(\sigma) = \left\{ \begin{aligned} &\{o\} && {if \; S = \empty \land i = 0} \\ &\{o.f_i | j = i + \sum\limits_{n = 1}^{|S|}k_n.s_n, j \leq max, k_n \in N, s_n \in S\} & & {otherwise}\\ \end{aligned} \right. FX(σ)=⎩ ⎨ ⎧​​{o}{o.fi​∣j=i+n=1∑∣S∣​kn​.sn​,j≤max,kn​∈N,sn​∈S}​​ifS=∅∧i=0otherwise​

以下面例子为例，右边PKH算出 $p_2$ 的pts集为 $o.f_3$, $o.f_5$, $o.f_6$, …。这个集合可以表示为 $o_{3+2k_1+3k_2}$ ($k_1$, $k_2$ 为正整数)，其中 $p_2$ 相对 $r$ 的field偏移量至少为2，r的field偏移量至少为1，因此 $p_2$ 可以表示为 σ 2 = < o , 3 , { 2 , 3 } > \sigma_2 = <o, 3, \{2, 3\}> σ2​=<o,3,{2,3}>。

Definition 2 (Overlapping and disjointed SFR)：overlapping表示为两个SFR至少会访问同一个address-taken variable相同的偏移量1次，记为 $\sigma \cap {\sigma }^{{}^{\prime }}\ne \varnothing$。反之，则是disjointed。

SFR的推理规则如下，可以看出：

• $pts$ 集合里的元素都是SFR形式的 $\sigma$ 而不是object $o$。

• addrof 依旧会新建address-taken variable，但是对于 field 指令 p = q->fi，新创建的SFR object $\sigma =<o,i+j,S\cup S^{{}^{\prime }}>$ 只有不为当前 $pts(p)$ 内任一元素的子集时才会被添加（依旧有可能有不同SFR object存在overlapping）。

2.1.1.示例1

对于前面倒数第二图中的示例，PKH会不断新建object $o.f_i$，而DEA总共创建了3个SFR object ${\sigma }_1$, ${\sigma }_2$, ${\sigma }_3$。具体过程为：

• 初始时 $r$, $p_1$ 的pts集合为 σ 1 = { o , 1 , { 0 } } \sigma_1 = \{o, 1, \{0\}\} σ1​={o,1,{0}}。

• 计算 $strides(p_2\stackrel{fiel{d}_2}{⟵}{p}_1)$ 和 $strides(q_1\stackrel{fiel{d}_1}{⟵}{q}_2)$ 时前者属于两个PWC（大圈和小圈），总权重分别为 $2,3$。后者只属于1个PWC总权重 $3$，因此计算结果分别为 { 2 , 3 } \{2, 3\} {2,3} 和 { 3 } \{3\} {3}

• 处理 $p_2\stackrel{fiel{d}_2}{⟵}{p}_1$ 时新建 σ 2 = < o , 2 + 1 , { 0 } ∪ { 2 , 3 } > = < o , 3 , { 0 , 2 , 3 } > \sigma_2 = <o, 2 + 1, \{0\} \cup \{2, 3\}> = <o, 3, \{0, 2, 3\}> σ2​=<o,2+1,{0}∪{2,3}>=<o,3,{0,2,3}>。

• 处理 $q_1\stackrel{fiel{d}_1}{⟵}{q}_2$ 时，此时分析了几个copy之后，假设 p t s ( q 2 ) = { σ 2 } pts(q_2) = \{\sigma_2\} pts(q2​)={σ2​}，第一次处理该edge时，新建 σ 3 = < o , 3 + 1 , { 0 , 2 , 3 } ∪ { 3 } > = < 0 , 4 , { 0 , 2 , 3 } > \sigma_3 = <o, 3 + 1, \{0, 2, 3\} \cup \{3\}> = <0, 4, \{0, 2, 3\}> σ3​=<o,3+1,{0,2,3}∪{3}>=<0,4,{0,2,3}>。

• 算法稳定后分析结果如上图所示。

2.1.2.示例2

改进后的 store 和 load 处理规则如下所示，添加 copy 边时，需要注意可能存在不同SFR object存在overlap情况。作者用 $M_{o.f_i}$ 表示包含 $o.f_i$ 的所有SFR object。处理 load 时，如果 $\sigma \in pts(q)$，那么对于 $FX(\sigma )$ 中的任意 $o.f_i$ 都有可能存在其它 ${\sigma }^{{}^{\prime }}$ 引用了 $o.f_i$，因此除了 $\sigma$ 外，${\sigma }^{{}^{\prime }}$ 也会和 $p$ 存在 copy 关系。

下图示例中处理 load $r\stackrel{store}{⟵}p$ 时， p t s ( p ) = { σ 1 } pts(p) = \{\sigma_1\} pts(p)={σ1​}，但是 σ 1 ∩ σ 2 = { o . f 4 } \sigma_1 \cap \sigma_2 = \{o.f_4\} σ1​∩σ2​={o.f4​}，因此除了添加 copy $r\stackrel{copy}{⟵}{\sigma }_1$ 外还有 $r\stackrel{copy}{⟵}{\sigma }_2$。

2.2.完整算法

完整算法如下图所示，这是基于wave propagation的Andersen算法实现：

3.Evaluation

3.1.Implementation

对于C++，virtual call p->foo() 会被翻译成指令序列

• vtptr = *p：该 load 通过 p 获得virtual table pointer。

• vfn = &vtptr->idx：该 field 通过索引 idx 以及vtable entry获取target function。

• fp = *vfn：该 load 获取function address。

• fp(p)：函数调用指令。

关于virtual call，以下面示例为例：

class Base {
public:
    // 虚函数
    virtual void show() {
    }

    // 非虚函数
    void display() {
    }

    // 虚析构函数，保证正确的析构顺序
    virtual ~Base() {}
};

// 派生类
class Derived : public Base {
public:
    // 重写虚函数
    void show() override {
    }

    // 重写非虚函数（注意，这不是多态的）
    void display() {
    }
};

int main() {
    // 基类指针指向派生类对象
    Base* basePtr = new Derived();

    // 虚函数调用（根据对象类型，调用 Derived 类的函数）
    basePtr->show();    // 输出：Derived class show function
    // 非虚函数调用（根据指针类型，调用 Base 类的函数）
    basePtr->display(); // 输出：Base class display function

    // 释放内存
    delete basePtr;

    return 0;
}

编译成IR后 basePtr->show(); 的指令如下：

%3 = load %class.Base*, %class.Base** %basePtr, align 8
%4 = bitcast %class.Base* %3 to void (%class.Base*)***
# 对应vtptr = *p
%vtable = load void (%class.Base*)**, void (%class.Base*)*** %4, align 8
# vfn = &vtptr->idx
%vfn = getelementptr inbounds void (%class.Base*)*, void (%class.Base*)** %vtable, i64 0
# fp = *vfn
%5 = load void (%class.Base*)*, void (%class.Base*)** %vfn, align 8
# fp(p)
call void %5(%class.Base* noundef nonnull align 8 dereferenceable(8) %3)

而 basePtr->display() 对应的指令为

%6 = load %class.Base*, %class.Base** %basePtr, align 8
# 对应Base::display方法，也就是直接确定调用目标不存在多态
call void @_ZN4Base7displayEv(%class.Base* noundef nonnull align 8 dereferenceable(8) %6)

benchmark信息如下图所示。

3.2.结果

PKH和DEA处理的变量数量如下图所示，可以看到数量有了大幅缩小。

时间开销对比如下图所示，柱状图每个元素左柱为PKH，右柱为DEA，可以看到时间开销DEA远少于PKH。

参考文献

[1].Lei Y, Sui Y. Fast and precise handling of positive weight cycles for field-sensitive pointer analysis[C]//Static Analysis: 26th International Symposium, SAS 2019, Porto, Portugal, October 8–11, 2019, Proceedings 26. Springer International Publishing, 2019: 27-47.

[2].Pearce D J, Kelly P H J, Hankin C. Efficient field-sensitive pointer analysis of C[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 2007, 30(1): 4-es.