07|IFDS:把集合传播拆成匹配路径上的事实传播
第 06 篇的双调用里,期望是 b 可能有污点、c 没有。若把第 04 篇的工作列表直接用在 ICFG 上,A、B 在 id 入口会并成同一份事实,污点沿两条返回边送回,c 也被判脏;遍历还可能从 A 的调用接到 B 的返回。精度上要分开不同调用点的事实、只承认匹配的返回,代价上又希望 id 不必按调用点反复分析——过程间求解需要同时照顾这两端。
IFDS(Interprocedural Finite Distributive Subset)由 Reps、Horwitz 与 Sagiv 于 1995 年提出(原始论文)。名称即定义:问题建在过程间控制流图上(Interprocedural),事实域有限(Finite),每条边上的流函数对合并满足分配律(Distributive),每个程序点的结果是事实的子集(Subset)。满足这些条件时,求解可化为图可达:只沿调用与返回匹配的路径合并,并把每个方法的分析结果写成可复用摘要。本篇用它处理上述双调用。
1. 全景:IFDS 是什么
IFDS 是求解框架,不是某一种具体分析:污点传播、变量是否可能未初始化等问题,只要满足适用条件,都能写成同一种形式,交给同一个求解器。它由三部分组成:
- 适用条件规定哪些分析问题可以交给它。
- 爆炸超图(ESG)把问题表示成一张图:“某个事实在某处成立”变成“图上某个节点可达”。
- 制表算法在图上求解,只承认调用与返回匹配的路径,并为每个方法生成可复用的摘要。
求解器的输入和输出如下:
- 输入:第 06 篇的 ICFG;一个有限的事实域 D,本篇的事实是“某个局部变量可能有污点”;每条边上的流函数(flow function),这是 IFDS 文献对转移函数的叫法;以及程序入口处的初始事实。
- 输出:每个程序点上可能成立的事实集合,合并时只计入调用与返回匹配的路径。
与前后篇的关系:第 04 篇的工作列表在单个方法内求不动点。IFDS 的求解器属于同一类算法,但每个程序点保存的内容从“事实集合”换成了“方法入口事实到当前事实的关系”,方法的结果因此能写成摘要(第 4.5 节)。第 08 篇再让每个事实携带一个值。
全篇使用第 06 篇的双调用例子:
static String id(String p) { return p; }
String a = input();
String b = id(a); // A
String c = id("safe"); // B
sink(b);
sink(c);约定 input() 产生污点,sink() 检查污点,id 无副作用;只追踪局部变量的显式传播和正常返回。分析采用 may 语义,路径合并取并集。期望的结果是 b 可能有污点,c 没有。
把第 04 篇的算法直接用在 ICFG 上得不到这个结果:A、B 两次调用的事实在 id 入口合并成一个集合 {p},出口的 {p,ret} 沿两条返回边都送回调用者,c 也得到污点。
2. 适用条件:什么问题能交给 IFDS
名称中的 Finite、Distributive、Subset 各是一项要求,Interprocedural 说明问题定义在 ICFG 上:
| 条件 | 含义 | 本篇例子 | 不满足的情况 |
|---|---|---|---|
| ICFG 已给定(Interprocedural) | 求解前已知每个调用点可能调用哪些方法 | id 是静态目标 | 调用目标未知或缺少调用边,对应的传播不会被计算 |
| 事实域有限(Finite) | D 中事实的个数有限 | 每个局部变量一个事实 | 形如 a.f.f.…、长度不设上限的字段访问序列有无限多个 |
| 流函数满足分配律(Distributive) | f(A∪B)=f(A)∪f(B),每个事实可以单独计算 | y=x | “p、q 同时成立才产生 r”,见第 2.1 节 |
| 结果是事实子集(Subset) | 每个程序点的结果是 D 的一个子集,只回答事实是否成立 | 可能有污点的变量集合 | 第 05 篇的环境为每个变量记录一个值 |
合并方式上,本篇取并集。交集合并的 must 类问题可以对事实集合取补集,转成并集问题求解,本篇不展开。
局部变量污点、可能未初始化变量这类“某个事实是否成立”的问题满足全部条件。第 05 篇的常量传播有两处不满足:结果是变量到值的环境;z=x+y 由 x、y 两个值共同决定,该篇第 5 节已算出先合并与分别执行的结果不同。第 08 篇的 IDE 放宽“子集”一项,分配律的要求仍然保留。
四项条件中,分配律需要对每条流函数逐一验证。
2.1 分配律:先合并再转移,结果一样吗?
分配律(distributivity)要求流函数 f 对任意 A、B 都有:
f(A ∪ B) = f(A) ∪ f(B)即先合并再转移,与分别转移再合并,结果相同。这使逐事实计算能够恢复整份集合的结果。
以 y=x 为例,x、y 是不同局部变量:
| 输入 S | f(S) |
|---|---|
∅ | ∅ |
{x} | {x,y} |
{y} | ∅ |
{z} | {z} |
{x,y} | {x,y} |
取 A={x}、B={y},左边为 {x,y},右边也是 {x,y}∪∅。一般地,删除旧 y 对每个输入事实独立生效,生成新 y 只依赖 x,因此这条规则对任意 A、B 都分配。
一个反例是“只有同时包含 p、q 才新增 r”:
g({p}) = {p}
g({q}) = {q}
g({p,q}) = {p,q,r}
g({p}) ∪ g({q}) = {p,q} ≠ g({p,q})这条规则需要两个事实联合触发,不能在原事实域上拆成独立单事实边。若重新设计复合事实域,需要重新验证有限性、语义与分配律。
3. 表示:把问题变成一张图
若事实域为 D={a,b,c,...},可能的集合有 2^|D| 个;|D| 表示事实数量,每个事实有选或不选两种情况。逐一保存“某个输入集合经过方法得到什么集合”可能很昂贵。分配律成立时,每个事实可以单独计算、最后合并,一条语句乃至整个方法的效果都能表示成事实之间的关系,画出来就是图上的边。
3.1 单事实边与辅助事实 Λ
第 2.1 节 y=x 的表中,输入 {x} 得到 {x,y},可以画成 x→x、x→y 两条边。x=input() 则在空集合上也会产生 x,这个 x 没有输入事实可以作为边的起点。为这种无条件生成引入辅助事实 Λ,读作 lambda:它沿可达路径传播,为新事实提供起点,不代表程序变量。
对并集分配函数:
f(S) = f(∅) ∪ 所有 d∈S 的 f({d}) 的并集因此可构造表示关系(representation relation):
Λ→Λ:沿路径携带辅助事实。Λ→d:表示d∈f(∅),即无条件生成。d→d':表示单事实 d 产生 d',且 d' 不是无条件生成的;按定义,已由Λ→d'表达的结果不再画d→d'。
y=x 的边是 Λ→Λ、x→x、x→y 以及其他非 y 事实的恒等边。没有 y→y,因为旧 y 被覆盖。x=input() 则有 Λ→x 和辅助边,并保留其他变量事实;同样没有 x→x,旧 x 也被覆盖。
3.2 单个方法的 ESG
把程序点上的事实分别展开为节点,得到 ESG(Exploded Supergraph,爆炸超图)。节点 (n,d) 表示语句 n 执行前的事实 d,边由表示关系给出。“爆炸”指原来的 |N| 个程序点最多展开为 |N|×(|D|+1) 个节点。
旧 y 被赋值覆盖,因此图中没有它的出边。这里仅展示 D={x,y};其他未被修改的事实各有自己的恒等边。
ESG 可以只按需要展开。某位置多个事实可达时,将它们收集起来就恢复了该处的事实集合。对没有调用的单个方法,入口不带初始事实时,从 (入口,Λ) 沿边能到达 (n,d),等价于第 04 篇算出的 d∈IN[n]。
3.3 跨方法的四类流函数
跨方法时,ICFG 的调用边、返回边和调用到返回边各需要一个流函数,加上方法内部的普通流函数,共四类。在第 1 节的例子中,用 ret 表示抽象返回事实,各方法的局部变量事实带所属方法,避免同名混淆。
| 类别 | 本例的映射 | 作用 |
|---|---|---|
| 普通流 | 来源 Λ→a;id 内 p→ret | 方法内部语句 |
| 调用流 | A 的 a→p;B 仅传辅助事实 | 实参映射到被调入口 |
| 返回流 | A 的 ret→b;B 的 ret→c | 返回到相应接收变量 |
| 调用到返回流(第 06 篇的“旁路”) | 保留调用者其他事实,删除接收变量旧事实 | 表达不经被调局部状态传播的效果 |
把这四类边放到程序点上,就得到本例的 ESG。图中省略了始终同行的 Λ 恒等边和未受影响事实的恒等边,只保留与污点有关的部分:
main 的每个方框是一个程序点,框内是该处的事实,自上而下依次是 A 之前、retA(同时为 B 之前)和 retB;底部方框里的 c 就是节点 (retB,c)。被调 id 位于中间,两个节点是它的入口与出口。a 经 A 的调用流映射到 p,再由 ret 返回为 b;a 本身沿旁路绕过 id 保留下来。虚线 ret→c 是 B 的返回流边,但 B 没有送入 p 的污点,因此 (retB,c) 没有匹配的到达路径。粗线 〈p,exit,ret〉 是求解时登记的路径边,不属于 ESG 本身,第 4.1 节定义。
3.4 可实现路径:哪些路径才算数
在这张图上做普通 BFS 会走通 (A 之前,a) → (entry,p) → (exit,ret) → (retB,c),错误地污染 c:这条路径从 A 进入 id,却从 B 返回。
可实现路径(realizable path)要求每次返回都匹配调用点,允许有尚未返回的调用。它遵守调用栈的规则:后进入的方法先返回,并且回到调用它的位置。上面那条路径不满足这个要求。
IFDS 要求的答案由此确定:从 (main 入口,Λ) 出发,沿可实现路径能到达 (n,d),事实 d 就在程序点 n 成立。
4. 求解:制表算法
求解器要找出可实现路径上的全部可达节点,但不记录调用栈。它为每个方法计算“入口事实到当前事实”的关系,遇到调用时直接使用被调方法已算出的关系。这个算法叫 tabulation(制表)算法,得名于它逐条登记这些关系。
4.1 三类记录
求解器保存三类主要记录:
- 路径边(path edge)
〈d₁,n,d₂〉:从当前方法入口事实 d₁,沿该方法内调用与返回已配平的路径,可到达(n,d₂)。它可以跨越很多条程序边。 - 入口记录 Incoming:哪些调用点、调用者路径边在等待某个被调入口事实的结果。
- 出口摘要 Summary:某入口事实能够产生哪些出口事实。
路径边记下的是“带着 d₁ 进入这个方法,走到 n 时 d₂ 成立”。保留 d₁,是为了在出口处知道结果由哪个入口事实造成,从而只把它交给传入过该事实的调用点。第 3.3 节图中的 〈p,exit,ret〉 说明 ret 的污点来自入口的 p:A 传入了 p,B 没有。到达出口的路径边就是摘要 p→ret;本例的路径边只跨一步,一般可跨多步。
求解器推进路径边,到达出口后生成摘要,再按 Incoming 找到等待结果的调用者并回填。
这种 Incoming 配合被调入口摘要的写法见 Naeem、Lhoták 与 Rodriguez 对 IFDS 的实用扩展,Heros 等实现采用它。原论文则将摘要记在调用点一侧,处理出口时扫描调用者路径边;两者结果相同。
4.2 走完一次摘要生成与应用
以下省略始终同行的辅助边,只追踪新增的污点关系;第一次进入 id 时也要分析 Λ 入口,以发现方法内部可能无条件产生的事实。本例 id 不产生新的来源。entry、exit 指 id 的入口与出口。
| 步骤 | 当前任务 | 新记录 | 后续动作 |
|---|---|---|---|
| 1 | 调用者执行 input | 〈Λ,A,a〉 | 调度 A |
| 2 | A 调用 id(a) | 登记 A 等待 (id,p);建立 〈p,entry,p〉 | 调度 id 入口;旁路得到 〈Λ,retA,a〉 |
| 3 | id 执行 return p | 〈p,exit,ret〉;摘要 p→ret | 查找等待该入口事实的调用 |
| 4 | 将摘要用于 A | 〈Λ,retA,b〉 | 继续调用者,retA 处含 a、b |
| 5 | B 调用 id(safe) | 不产生入口 p 的污点;旁路得到 〈Λ,retB,a〉、〈Λ,retB,b〉 | Λ 摘要没有 ret 污点,故不生成 〈Λ,retB,c〉 |
| 6 | 到达两个 sink | b 有污点,c 没有 | 队列为空,结束 |
调用先到时,Incoming 记录等待关系,摘要生成后再回填;摘要先到时,新调用登记后立即应用它。求解器必须处理这两种时序,才能让结果不受队列顺序影响。
4.3 算法骨架
以下是正常控制流、静态目标、单出口模型下的算法骨架。propagate 只将未见过的路径边加入集合和工作列表。
从种子建立 〈Λ, entryMain, Λ〉
while 工作列表非空:
取出路径边 〈d1, n, d2〉
if n 是调用点:
按旁路流函数传播到返回位置
for 每个调用目标 q、每个调用流结果 dq:
登记 Incoming(q,dq) 中的调用点与调用者路径边
propagate(〈dq, entry(q), dq〉)
将已有 Summary(q,dq) 通过该调用的返回流应用到调用者
else if n 是方法出口:
将入口事实 d1 到出口事实 d2 的关系加入 Summary
将新摘要应用到 Incoming 中所有对应调用
else:
沿普通边和流函数产生后继路径边应用摘要时,保留调用者原路径边的入口事实,再将被调出口事实通过返回流映射到接收变量,得到新的调用者路径边。多出口、异常以及库调用需要扩展对应的流函数和调度规则。
4.4 递归如何停止?
考虑概念方法 idRec(p,k):k 为零时直接返回 p,否则递归调用 idRec(p,k-1) 并返回结果。污点域不追踪 k 的具体数值。
- 入口 p 沿直接返回分支产生摘要
p→ret。 - 递归调用登记等待同一
(idRec,p)的结果,并复用这个摘要。 - 递归返回又得到
p→ret,但它已经存在,不再制造新任务。
求解器反复加入新关系,直到得到闭包。有限的事实与程序点限制了关系数量,递归调用因而可以通过关系去重来处理。
4.5 与第 04 篇的关系:同一类不动点算法
制表算法与第 04 篇的工作列表是同一类算法:有新结果就入队,队列为空时结束。两者迭代的对象不同:
| 对比项 | 第 04 篇的工作列表 | 制表算法 |
|---|---|---|
| 每个程序点保存 | 一个事实集合 IN[n] | 一组路径边 〈d₁,n,d₂〉 |
| 队列中的条目 | 节点 | 路径边 |
| 何时入队 | 节点首次可达,或 IN 改变 | 出现未见过的路径边 |
| 为什么会停 | 规则单调,格的高度有限 | 路径边数量有限,每条只入队一次 |
| 结束时 | 再算一遍,IN、OUT 不变 | 再应用一遍规则,不出现新的路径边或摘要 |
路径边的 d₁、d₂ 各有 |D|+1 种取值(含 Λ),总数不超过 |N|×(|D|+1)²。把已登记的路径边和摘要看作状态,算法骨架的规则只向其中添加记录,从种子开始得到的是在这些规则下封闭的最小集合,对应第 04 篇第 4 节的最小不动点。
差别集中在表的第一行。第 04 篇在 id 入口只有一个集合,A、B 两次调用的事实合并后无法再分开。路径边按入口事实分别记录,方法的结果成为入口事实的函数,所以能写成摘要,再由各调用点按自己传入的事实取用。没有调用时,两者算出的结果相同(第 3.2 节)。
5. 保证:精度与复杂度
在第 2 节的条件下,IFDS 精确求得全部可实现路径(第 3.4 节)的合并结果,称为 MRP(Meet over all Realizable Paths)。Meet 沿用文献的顺序约定,本篇实际取并集。“精确”指结果恰好等于这些路径上事实的并集:不匹配的返回不会带来多余的事实,可实现路径上的事实也不会遗漏。
可实现只要求调用栈匹配,并不保证分支条件可满足。第 06 篇 flag 与 !flag 的例子仍会产生不可行的候选路径。
MOP(Meet over all Paths)对图中所有路径合并,过程间裸图可能包含不匹配返回;MRP 排除这些路径。
一般情形的时间界为 O(|E|·|D|³):E 是 ICFG 的边集,D 是普通事实域,假定每条 ESG 边可在常数时间枚举。固定 E 时,事实数翻倍会使这个上界增长八倍;将访问路径、对象和条件编码进 D 会增加成本。特定问题可有更好的界,见原论文的复杂度分析。
6. 边界与延伸
6.1 条件不满足时
| 不满足的条件 | 后果 | 常见处理 |
|---|---|---|
| 分配律 | 直接拆成单事实传播可能漏算,第 2.1 节联合触发的 r 就会丢失 | 重新设计事实域,或构造满足分配律的保守近似并证明其覆盖关系 |
| 事实域有限 | 路径边可以不断新增,求解可能不终止 | 限制事实的形式,例如给字段访问序列设长度上限 |
| 结果是事实子集 | “事实是否成立”无法表达每个事实对应的值 | 改用第 08 篇的 IDE |
| ICFG 已给定 | 缺失的调用边上没有传播,结果可能漏报 | 按第 06 篇第 3 节构造调用图,其假设随之成为结论的前提 |
6.2 后续篇目接什么
6.3 选读:用括号表示调用与返回
将调用边标为左括号 (A,对应返回边标为右括号 )A,其他边标为空串。可实现路径要求每个右括号匹配最近的未配对左括号,允许留下未返回的调用;路径边则汇总两端配平的同层路径。
判断图中是否存在标签串属于某个上下文无关语言的路径,叫 CFL 可达性(CFL-reachability)。IFDS 可视为 ESG 上的括号语言可达性问题,见 Reps 的综述。
字段读写也可用另一类括号表示。若要求调用与字段两类括号各自精确匹配,一般问题不可判定,需要近似或限制模型;第 11 篇末尾的按需别名分析也面对这一问题。
本篇要点
- IFDS 是过程间数据流分析的求解框架,由适用条件、ESG 和制表算法三部分组成:输入 ICFG、有限事实域和流函数,输出各程序点的事实集合。
- 适用条件是事实域有限、流函数满足分配律、结果是事实子集。直接拆分非分配性规则可能漏算。
- ESG 展开程序点与事实,无条件生成借助 Λ;答案是可实现路径上的可达节点,普通遍历会从 A 进入、从 B 返回而污染 c。
- 制表算法用路径边、Incoming、Summary 求解并复用摘要,与第 04 篇的工作列表同属不动点算法;两种到达时序都须处理,重复关系不再入队。
- IFDS 精确求得给定问题的 MRP,但不保证分支条件可满足。一般时间界为
O(|E|·|D|³)。
下一篇在事实边上附加值变换。
