Static Analysis 09-Pointer Analysis Foundations I

Static Analysis 09-Pointer Analysis Foundations I

HC_Plantern 27 2022-11-11

目录

参考

重点

  • Understand Rules for pointer analysis
  • Understand PFG (Pointer flow graph)
  • Understand Algorithm for pointer analysis

Notations

首先关注前四种语句,Call 语句下节课讲

介绍一些数学表示

Pointer Analysis: Rules

主要解释 Rule 一列中的内容。横线上的内容是前提 (Premises) ,横线下的内容是结论 (Conclusion) 。

New 语句:将新建的对象加入 pt(x)pt(x)
Assign 语句:将 xx 指向 yy 指向的对象。
Store 和 Load: 同上

How to Implement Pointer Analysis

指针分析是在指针间传递指向关系。最开始的指向关系都来自于 new 语句。

指针分析的关键:当 pt(x)pt(x) 变化时,也要更新 xx 相关的其他指针

Pointer Flow Graph

Pointer Flow Graph (PFG) of a program is a directed graph that expresses how objects flow among the pointers in the program.

指针流图的两大要素是 Node 和 Edge

  • Node: Pointer = V ⋃ (O × F)
    • A node n represents a variable or a field of an abstract object
  • Edges: Pointer × Pointer
    • An edge xyx \to y means that the objects pointed by pointer xx may flow to (and also be pointed to by) pointer yy

Example

假设 c 和 d 一开始都指向 oio_i,根据上述规则,我们能够从左侧的程序语句从上到下构建出右侧的指针流图。

所有 b 所指向的对象更新时,都要传递到 e 中。这是一个求传递闭包 (transitive closure) 的过程。

假如我们考虑 j 位置的一条新语句b = new T();

PFG 的构建和传递指针关系这两个步骤是相互依赖的。指针分析过程中需要不断在这两个步骤之间循环往复。

Pointer Analysis: Algorithms

Introduction

  • 由于做流不敏感分析。输入为Set,丢失了语句的顺序关系也没关系。
  • WorkList:保存接下来要处理的指向信息,与BFS中的队列作用类似。
  • Each worklist entry n,pts\left \langle n, pts \right \rangle is a pair of pointer nn and points-to set ptspts, which means that ptspts should be propagated to pt(n)pt(n)
    • E.g.,[x,{oi},y,{oj,ok},oj.f,{ol}]E.g., [\langle x, \{o_i\} \rangle, \langle y, \{o_j, o_k\} \rangle , \langle o_j.f, \{o_l\} \rangle \dots]

四个红框部分对应之前提到的四种基本语句—— New, Assign, Store 和 Load

Handling of New and Assign

Init and adding edges

首先考虑两种简单的语句:New和Assign。

  • 前三行代码做初始化的工作,并针对所有的 New 语句,将所有的初始指向关系加入WorkList。注意 pt(n)pt(n) 初始化后为空集{}\{\},随着算法的迭代会增加元素。
  • 之后的两行代码处理 Assign 语句,添加y->x的边到PFG中。添加边的具体算法如下

Propagate

Propage() 之前要先去重

解释 Propagate() 具体做的事情

Detial-Differential Propagation

为什么要去重?

  • 去重与否不影响正确性
  • 主要是为了避免冗余的操作

在真实的指针分析中,对象的数量非常巨大(上亿),我们通过Differential Propagation来消除冗余。

Solve(𝑆)
    ...
    while WL is not empty do
        remove 𝑛, 𝑝𝑡𝑠 from WL
        Δ = pts – pt(n) // Differential Propagation
        Propagate(n, Δ) // Differential Propagation

Example:

首先是a->c->d的传递路线

如果不考虑 Differential Propagation,在 b->c->d 的传递路线中,{o1,o3}\{o_1, o_3\}
之前已经在c所指向的集合中了,但依然需要参与传播,这是冗余的。

如果去重,只需要传播 {O5}\{O_5\} 这一项即可。

Handling Store and Load

Example

以这个程序为例讲解算法。

1 b = new C(); 
2 a = b;
3 c = new C(); 
4 c.f = a;
5 d = c;
6 c.f = d; 
7 e = d.f;

结果如下图,过程看视频