形式陈述
Andersen分析用包含约束近似指针可能指向的地址。固定一个指针核心语言,语句规范化为取地址、复制、一次解引用读写和分配;不允许从任意整数伪造地址。具体读写按存储语义 理路 可变状态语义 Semantics of mutable state · Store semantics 把位置到值的存储纳入配置并随求值更新的语义。 执行。
静态分析将每个变量存储位置和每个堆分配站点看作一个抽象单元,构成有限集合Cell。同一分配站点的许多运行时对象被合并;基础版本不区分语句执行位置或调用上下文。对每个单元x,pt ( x ) ⊆ Cell 表示它可能保存的指针目标。
四类语句生成以下约束:
语句
约束
x=&a
a ∈ pt ( x )
x=y
pt ( y ) ⊆ pt ( x )
x=*y
对每个 a ∈ pt ( y ) ,pt ( a ) ⊆ pt ( x )
*x=y
对每个 a ∈ pt ( x ) ,pt ( y ) ⊆ pt ( a )
x=new@h 给出 h ∈ pt ( x ) ;新对象字段的初始化要另按语句建模。空指针可使用专门标记,但不得把“pt为空”未经说明等同于“确定为空指针”:前者还可能表示没有被推到的有效地址事实。
取有限函数格 P ( Cell ) Cell ,定义 Φ ( p t ) 为保留已有目标、加入取地址/分配及允许初始存储的种子、再按当前pt触发全部复制和load/store约束所得的映射。它对逐点包含序单调。有限偏序的非空有向子集有最大元,因此这里的单调性也保证Scott连续;从全空映射迭代,有限步稳定在全部约束的最小解 理路 最小不动点语义 Least-fixed-point semantics · Least fixed point semantics · Kleene fixed-point semantics 以递归定义的有限展开链之上确界选取不凭空加入行为的最小语义解。 。只向集合添加目标,不因后面的赋值覆盖而删除,因为流不敏感结果要同时覆盖所有执行时刻。
直觉
每条包含边都保留信息流方向:x=y让y的可能目标流到x,却不要求x原有的目标也反向流到y。解引用则先问指针可能指到哪些单元,再为这些单元建立新的传播关系。
所以约束图不一定一次建完。刚发现a属于pt(y)时,x=*y才暴露出新的边 a → x ;若后来pt(a)继续增长,这条边还要继续传新事实。
图片加载失败
例子与边界
写穿一层指针,再读回来
考虑
text p = &a
q = &b
r = p
*r = q
s = *p
1 2 3 4 5
这里a、b也是有地址的存储单元。起初各pt集合为空,取地址先产生pt(p)={ a } 、pt(q)={ b } 。复制r=p让a进入pt(r)。
因为a在pt(r)中,存储 *r=q 激活包含边 q → a ,于是b进入pt(a)。又因为a在pt(p)中,加载 s=*p 激活边 a → s ,使b最终进入pt(s)。稳定结果为
pt ( p ) = pt ( r ) = { a } , pt ( q ) = pt ( a ) = pt ( s ) = { b } . pt(b)仍为空;程序没有向单元b写入其他地址。不要把“q指向b”误读成“b指向q”,也不要把pt(a)与地址a自身混为一层。
新边必须携带旧事实
若先求得pt(q)={ b } ,之后才因r发现a而加入边 q → a ,只订阅q未来的变化会漏掉已经存在的b。可靠工作队列需要两个对称入口:新增事实时沿已有边传播;新增边时立即传播源端已有的全部事实。加载/存储的条件约束同样既处理旧目标,也登记未来目标。
流不敏感会保留已经覆盖的目标
text x = &a
x = &b
y = x
1 2 3
本分析给pt(x)=pt(y)={ a , b } 。真实执行到最后时x和y只指b,但分析有意丢掉语句顺序,不能进行“第二次赋值杀掉a”的强更新。这个伪别名来自流不敏感,而非包含方向做错。
相反,若程序为 p=&a; q=&b; r=p; r=q,包含分析保留pt(p)={ a } 、pt(q)={ b } ,只有pt(r)={ a , b } 。Steensgaard合一分析 理路 Steensgaard 合一式指针分析 Steensgaard pointer analysis · Unification-based points-to analysis 把可能别名合成等价类为什么更快,又会在哪个小程序上丢掉精度。 会用更粗的目标等价类换取更低成本;这组例子可以精确比较差别。
推论与应用
一套有界工作队列
维护每个x的目标集合及包含后继列表。发现新事实 ( a , x ) 后,将它加入队列一次。弹出时,一方面沿x已有的包含边传播a,另一方面检查以x为指针的load/store约束,为a生成新的包含边。每条新边在安装时推送源端现有目标。
若程序大小为n,抽象单元及规范化语句数量均为 O ( n ) ,最多有 O ( n 2 ) 个“单元、目标”事实和 O ( n 2 ) 条包含边。适当去重后,每个事实沿每条相关边传播、每条新边接收旧事实的总工作可按三元组合计为 O ( n 3 ) ,空间为 O ( n 2 ) 。反复重扫全部约束的教学实现虽然也终止,不应未经计数就冒充这个工作队列界。
这给出抽象解释 理路 抽象解释 Abstract interpretation · Theory of sound static approximation 以具体与抽象语义、可靠转移和不动点逼近统一组织静态程序分析的数学框架。 的具体覆盖关系。固定把具体位置映到变量单元或分配站点的映射 β : Loc → Cell ,令 γ ( p t ) 包含所有满足下述条件的允许存储:每条有效具体指针边 ℓ → ℓ ′ 都有 β ( ℓ ′ ) ∈ p t ( β ( ℓ ) ) 。pt按包含序扩大时,γ ( p t ) 也只扩大。初始种子必须覆盖允许输入存储,不能默认为外部指针都不存在。
对满足全部约束的pt,四类具体步保持这个覆盖关系:取地址直接加入代表;复制用包含传播;load/store按所有可能目标覆盖实际被访问的那个单元。分配产生的具体位置归到其站点,初始化另按语句覆盖。因此 γ ( p t ) 对具体一步转移封闭。再按执行长度作数学归纳 理路 数学归纳法 Mathematical induction · Weak induction 由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。 ,以初始种子为零步基例、上述局部保持为后继步,便得到全部有限可达存储的may-points-to覆盖。
最小约束解不等于最精确的全部流不敏感语义。路径相关性、不同指针事实能否同时成立、语句规范化引入的临时值,仍可能造成额外近似。可靠的共同目标是不能漏真实地址,不是保证每条静态边都能在某次执行实现。
字段敏感扩展可用 ( h , f ) 表示抽象对象h的字段f;把全部字段合成一个槽更省空间,却可能让不同字段的目标串在一起。和调用图联合求解时,新函数地址也会激活新的参数/返回约束,因此不能预先假定调用图永远不变。
对象敏感分析 理路 对象敏感指针分析 Object-sensitive pointer analysis · Object sensitivity 为什么用接收者的分配身份区分方法实例,比仅记调用位置更适合某些面向对象程序。 进一步按接收者身份区分方法中的变量与参数传播。字段敏感区分“同一对象的哪个字段”,接收者上下文区分“同一方法正在处理哪个抽象对象”;两者可以组合,却不是同一项精度选择。
练习与解答
在主例最后增加 t=*r,能否断定pt(t)只有b?答案可以:pt(r)只有a,故新增边 a → t ;pt(a)只有b,传播后pt(t)={ b } 。若再加入 r=&c 和 c=&d,则pt(r)扩大为 { a , c } ,加载多出 c → t ,pt(t)变成 { b , d } 。验收要指出是哪条新地址事实激活了哪条新包含边,而不是直接猜最终集合。
参考资料
Lars Ole Andersen, Program Analysis and Specialization for the C Programming Language , DIKU博士论文,1994:包含式points-to分析
Anders Møller and Michael I. Schwartzbach, Static Program Analysis ,2026-09-30版,§§11.1–11.3:分配站点抽象、四类约束及按需生成边的三次求解器