指针分析（五）

2022-12-01 | 阅读：次

上下文敏感的指针分析算法

该算法与上下文不敏感的指针分析算法类似，主要是在指针、对象和方法中多出了一个上下文属性。而上下文敏感中最重要的部分就是多出的Select函数，该函数用于生成上下文。

不同的Select函数会产生不同的指针分析变种

Select函数中包含调用者上下文、调用点、接收对象、调用方法，根据对这些参数的使用会产生不同的上下文敏感的变种

上下文不敏感可以看作是上下文敏感的一种特殊情况：

Select(c,l,c':o,m)=[]

每个上下文包含了一个调用链。每次方法调用都会将调用者的上下文后加该调动点以形成被调用者的上下文，是对调用栈的一种抽象。

//c=[l',...,l'']
Select(c,l,c':o,m)=[l',...,l'',l]

也称(k-)CFA

这种方式带来一个问题：对于递归函数会产生无穷多的上下文，从而无法分析。

设置上下文长度的最大值k，每个上下文由调用链的最后k个调用点组成。一般该k值都很小，方法上下文和堆上下文的k值可以不同。例如方法上下文的k值一般为2，堆上下文的k值一般为1

例如k=1时

Select(c,l,c':o,m)=[l]

k=2时

//c=[l',l'']
Select(c,l,c':o,m)=[l'',l]

使用包含堆上下文的调用对象来形成被调用者的上下文。

通过堆不同对象的操作来区分数据流

//c=[o_j,...,o_k]
Select(c,l,c':o_i,m)=[o_j,...,o_k,o_i]

通过调用的接收对象的类型和堆上下文来构成上下文。

类型敏感是对象敏感的粗粒度抽象，在k相同的情况下精度不大于对象敏感。

类型敏感通过相同类型的调用点的合并来提高速度。在实践中，类型敏感的精度和对象敏感的精度相差不大