04|工作列表与不动点:哪些节点要重算,什么时候能停?
第 03 篇的例子没有循环,从 n1 算到 n7 一遍就结束。一旦有回边,先算的节点在后面的节点算完之后输入可能又变了,“每个节点算一遍”就不够。
1. 一次算不完:为什么需要工作列表
一个节点的 IN 来自前驱的 OUT;前驱的 OUT 又可能因为更前面的节点而改变。有环时这条链会绕回来:节点 n 算完之后,它的某个前驱后来更新了,n 的输入随之变化,n 的输出也得重算;n 的输出变了,它的后继又得重算。
工作列表(worklist)就是管理这件事的机制:保存“待处理”的节点,每次取一个出来计算,把变化传给后继,后继因此需要重算就放进列表。直白地说,它是一张待办清单,谁的输入变了,谁就上清单。
2. 入队规则
本文从入口开始、按需发现节点。一个节点入队有两种情况:
- 首次可达:第一次被分析到,即使输入还是空集。
- 输入改变:已经可达,但 IN 变了,之前算出的 OUT 可能不再正确。
两条补充规则:已在队列中的节点不重复加入,只更新它的 IN;本文采用 FIFO(先进先出),先入队的先处理。
入队的是“接收变化的节点”,也就是本次传播的后继。当前节点计算 OUT,传播给后继;后继的 IN 变了,后继入队。有自环时,后继也可能是当前节点自己。
3. 循环例子的完整轨迹
input() 产生污点,sink(z) 检查 z;flag 与 again() 的结果是未知布尔值,again() 不修改 x、y、z:
String x = input();
String y = "safe";
String z = "safe";
while (flag) {
z = y;
y = x;
flag = again();
}
sink(z);把初始化合记为 P,循环条件记为 H,z=y 记为 Z,y=x 记为 Y,更新条件并跳回循环头记为 C,sink(z) 记为 S:
规则沿用第 03 篇:赋值先覆盖左侧变量的旧事实,再根据右侧是否带污点决定是否加入;H、C、S 保留输入集合,汇合取并集。C → H 是回边(back edge),把循环体中的信息送回循环头。本例只分析局部变量的显式污点传播。
假设 P 处理完毕后 IN[H] = {x},队列为 [H],其他节点尚不可达。H 的后继按 Z、S 的顺序处理。下表把“当前节点处理”和“后继传播”合在一行:谁被取出、算出什么、传给谁、谁的 IN 变了、谁入队。H 的两行对应同一次出队,分别展示对 Z、S 的传播,“处理后队列”都记录 H 处理完全部后继后的状态。表有 16 行,对应 13 次出队。
| 取出节点 | 当前 IN | 输出与更新 | 后继节点 | 后继原 IN | 后继新 IN | 是否入队 | 处理后队列 |
|---|---|---|---|---|---|---|---|
| H | {x} | 首次到达 Z、S | Z | 未可达 | {x} | 是 | [Z,S] |
| H | {x} | 首次到达 Z、S | S | 未可达 | {x} | 是 | [Z,S] |
| Z | {x} | OUT={x} | Y | 未可达 | {x} | 是 | [S,Y] |
| S | {x} | 暂未发现 z 的污点 | — | — | — | 否 | [Y] |
| Y | {x} | OUT={x,y} | C | 未可达 | {x,y} | 是 | [C] |
| C | {x,y} | 输出传播给 H | H | {x} | {x,y} | 是 | [H] |
| H | {x,y} | 输出传播给 Z、S | Z | {x} | {x,y} | 是 | [Z,S] |
| H | {x,y} | 输出传播给 Z、S | S | {x} | {x,y} | 是 | [Z,S] |
| Z | {x,y} | OUT={x,y,z} | Y | {x} | {x,y,z} | 是 | [S,Y] |
| S | {x,y} | 仍未发现 z 的污点 | — | — | — | 否 | [Y] |
| Y | {x,y,z} | 保留三项 | C | {x,y} | {x,y,z} | 是 | [C] |
| C | {x,y,z} | 输出传播给 H | H | {x,y} | {x,y,z} | 是 | [H] |
| H | {x,y,z} | 输出传播给 Z、S | Z | {x,y} | {x,y,z} | 是 | [Z,S] |
| H | {x,y,z} | 输出传播给 Z、S | S | {x,y} | {x,y,z} | 是 | [Z,S] |
| Z | {x,y,z} | OUT 与上次相同 | Y | {x,y,z} | {x,y,z} | 否 | [S] |
| S | {x,y,z} | 发现 z 可能有污点 | — | — | — | 否 | [] |
表分三段读。第一圈(前 6 行):H 首次可达 Z、S;Z 的 IN 是 {x},z=y 没有产生 z;Y 的 y=x 产生 y,OUT 变成 {x,y};C 把 {x,y} 送回 H,H 的 IN 从 {x} 变成 {x,y},重新入队。第二圈(中间 6 行):H 把 {x,y} 传给 Z、S;这次 Z 的输入有 y,z=y 产生 z,OUT 变成 {x,y,z};沿 Y、C 再送回 H。第三圈(后 4 行):H 把 {x,y,z} 传给 Z、S;Z 的 OUT 与上次相同,Y 不再入队;S 取出时 IN 是 {x,y,z},发现 z 可能有污点,队列为空,结束。
S 一共处理了三次,前两次都“暂未发现 z”。中间结果不是最终结果:z 要从 Z 经 Y、C、H 绕一圈才到 S,S 的输入每变一次就要重算一次,最后一次才看到 z。这些步骤描述分析器的调度顺序,不是程序的某一次实际执行;循环头的集合合并了不同轮次的信息。
4. 什么时候可以停:队列为空与不动点
一次完整处理的顺序是:取出节点 n;计算 OUT,首次计算或结果变化时保存;把首次得到或变化的 OUT 传给后继,后继首次可达或 IN 改变时入队,已排队的只更新 IN;检查队列,为空则结束。刚取出最后一个节点时队列可能暂时为空,但仍要做完计算与传播才能判断。
停止条件:当前节点的计算、传播、入队全部完成后,工作列表为空。
这里有两个相关但不同的概念:
- 工作列表为空:没有待处理的节点。
- 不动点(fixed point):对所有可达节点再算一遍,IN 和 OUT 都不会变。
在初始化正确、图和规则不变、变化都完整传播的前提下,队列为空就能判定达到不动点。反过来不成立:节点因 IN 变化入队只表示需要重算,OUT 未必会变。例如 x="safe" 的 IN 从 ∅ 变为 {x} 时节点会入队,但两种输入的 OUT 都是 ∅;若其他节点也无需更新,此时已经是不动点,队列里却还留着这个节点等待确认。
另外,最后一次计算发生了变化也可以结束。表格最后一行 S 的 OUT 从 {x,y} 更新为 {x,y,z},但 S 没有后继,保存结果后队列仍为空。不动点要求的是“从现在的状态再算结果不变”,不是“最后一次计算没有变化”。
把所有节点的状态装进一个大状态 X,把入口条件、语句转移和后继合并合起来看作 F,数据流问题就是方程 X = F(X):满足方程时再算一遍结果也不变。对固定的有限图和有限高度域,从底元素开始并设置入口边界,转移与合并单调,且所有待处理项最终都得到处理,求得的是这套方程的最小不动点(least fixed point),即最精确的解。本例以不可达为底,入口另设为可达空集。最小不动点仍可能包含抽象规则引入的额外可能性:第 03 篇在分支汇合后保留 y 的污点,却不再区分它来自哪条分支;求解器把方程算完整,不等于恢复了合并时丢失的信息。标准迭代依据见 Static Program Analysis 第 4—5 章。
5. 为什么一定会停
即使存在 H → Z → Y → C → H 这样的环,也不会无限重算。两个条件合起来保证终止,都来自第 03 篇的格:
单调性(monotonicity):输入 A ⊆ B 时,输出满足 transfer(A) ⊆ transfer(B)。IN 通过并集合并只会增加,单调保证同一节点历次计算的 OUT 也不会减小。表中 Z 的 OUT 依次是 {x}、{x,y,z}、{x,y,z},每一步都不比上一步小。
单调不要求语句只能增加事实。y="safe" 的规则删除 y:
| 输入 | 输出 |
|---|---|
A = {y} | f(A)=∅ |
B = {x,y} | f(B)={x} |
输入满足 A⊆B,输出满足 ∅⊆{x},它单调;但它确实删除了污点。单调比较的是不同输入经过同一函数后的结果,不是同一次计算中的 IN 与 OUT。
有限高度(finite height):严格上升链的步数有统一的有限上界。本例只有 x、y、z,{x} ⊆ {x,y} ⊆ {x,y,z} 这样的上升链(ascending chain)每一步至少新增一个变量,从空集开始最多三步。
单调保证集合只朝一个方向变,有限高度保证朝这个方向走不了几步;每个节点只在首次可达或 IN 变化时入队,所以入队总次数有限,队列最终一定会空。
6. 伪代码
IN[entry] = 可达且为空集;其他节点不可达
worklist = [entry];OUT 均未计算
while worklist 非空:
n = 取出一个节点
newOut = transfer(n, IN[n])
if OUT[n] 未计算过,或 newOut != OUT[n]:
OUT[n] = newOut
for s in successors(n):
newIn = 将 newOut 合并入 IN[s]
if s 首次可达,或 newIn != IN[s]:
IN[s] = newIn
若 s 不在队列中,将 s 入队两处细节容易写错。
IN 的更新在去重判断之前。 已排队的节点也要接收新事实,否则它出队时读到的是旧输入。表中 S 第三次出队前,IN 已在 H 的传播中更新为 {x,y,z}。
“首次可达”不能省略。 若把所有节点的 IN 预置为空集、只在集合变化时入队:n1 的 OUT 是 ∅,合并到 n2 的 IN 仍是 ∅,集合没变,n2 不入队;但 n2 还没被处理过,若它含 x=input(),这条来源就永远不会被分析。首次可达与输入改变是两个独立的入队原因。其他实现可以用别的初始化策略保证首次处理,但不能只删掉这个判断。
7. 调度策略:FIFO、LIFO 与优先队列
入队条件决定“哪些节点需要处理”,调度策略决定“下一次取谁”。换一种取出顺序,传播规则不变。
| 策略 | 取出规则 | H 依次加入 Z、S 后 | 特点 |
|---|---|---|---|
| FIFO(先进先出) | 取最早加入的节点 | 先取 Z | 新任务排在队尾,便于按传播过程手算 |
| LIFO(后进先出) | 用栈取最近加入的节点 | 先取 S | 优先沿最近产生变化的方向继续 |
| 优先队列(priority queue) | 取优先级最高的节点 | 取决于 Z、S 的优先级 | 可利用图结构排序,需维护优先级 |
若固定优先级从高到低为 H、Z、Y、C、S,就会先把循环中的变化传完再处理 S。P 之后的出队顺序变为:
H → Z → Y → C → H → Z → Y → C → H → Z → S共出队 11 次,S 只处理一次;FIFO 表出队 13 次,S 处理三次。S 在排队期间仍接收 IN 的更新,出队时直接读到 {x,y,z},两种调度的最终 IN/OUT 相同。顺序影响成本,但这个例子不能证明某种策略对所有图都更快。
实际实现常按图结构设置优先级。逆后序(reverse postorder,RPO)把深度优先遍历完成节点的顺序反过来:在无环图上它是拓扑顺序,前驱先于后继处理;有环时仍需重算。Clang 的 ForwardDataflowWorklist 就按逆后序取出节点,并避免同一节点重复排队。
在固定图、有限高度域和单调规则下,从相同入口边界与底状态出发、保证所有待处理项最终得到处理,完整求解得到同一个最小不动点,与调度顺序无关。若因预算耗尽提前停止,或引入第 10 节的加宽,这个结论不再直接成立。
8. 与其他迭代方式的关系
轮询迭代(round-robin iteration)每轮按固定顺序重算所有节点,直到完整一轮没有变化。工作列表只处理首次可达或输入变化的节点:若只有 H 的 IN 变了,轮询仍扫描全部节点,工作列表只处理 H,OUT 不变就结束。
混沌迭代(chaotic iteration)每次选一个节点、用当前最新状态更新它,不要求统一顺序,只要求需要处理的节点不被永久遗漏。本文的工作列表是它的一种实现:C 更新了 H 的 IN,H 出队时直接使用新输入。“混沌迭代”说的是怎样更新状态,“工作列表”进一步说明怎样记录和选择待处理节点。参见 Static Program Analysis 第 5.3 节。
Kildall 算法是在格上合并数据流信息、用工作列表继续传播的经典形式,本文伪代码沿用这类思路。Kildall 1973 年论文第 3 节的待处理项包含节点和传入信息,本文先把信息合并到 IN 再将节点入队;状态保存方式不同,求解方式相同。
9. 复杂度
本例只有 x、y、z,IN 从空集最多严格增加三次,加上首次处理,每个节点最多处理四次。这是上界:表中 H 处理三次,Y 两次;多个变化在出队前合并时只需处理一次。
一般地,设图有 N 个节点、E 条边,每份事实集合最多严格上升 h 次(不含首次):
- 计算节点输出:每个节点首次一次,之后最多 h 次,共不超过
N(h+1)次。 - 沿边合并输入:OUT 首次计算后最多变化 h 次,每条边最多传播
h+1次,共不超过E(h+1)次。
h 是“最多增加几次”,不是格的元素个数:本例有 8 种可能的集合,但 h=3。设一次转移、合并或比较的成本上界为 c(含必要的集合复制),时间复杂度为:
O((N + E) · (h + 1) · c)集合越大,合并和比较越慢,c 不能一律当成常数。上述估计针对 FIFO,假设入队、出队和“是否已排队”的标记查询都是 O(1);二叉堆优先队列每次入队出队另加 O(log N)。类似推导见 CMU 数据流框架讲义第 13—14 页。
空间:去重后队列最多容纳 N 个节点,连同标记占 O(N);若一份事实集合占 b 个存储单元,所有节点的 IN/OUT 占 O(Nb);图占 O(N+E)。合计 O(Nb + N + E)。
10. 补充:无限高度域与加宽
第 4 节的最小不动点与第 5 节的终止论证都假定域有有限高度。若域允许无限上升链,单调就不足以保证终止。用整数区间域(interval domain)为每个变量记录 [下界, 上界],分析计数循环 i=0; while(again()) i=i+1;(无溢出的数学整数)。循环头的区间每轮严格变大:
| 轮次 | 回边贡献 | 循环头(与入口 [0,0] Join 后) |
|---|---|---|
| 首次 | 无 | [0,0] |
| 第 2 轮 | [1,1] | [0,1] |
| 第 3 轮 | [1,2] | [0,2] |
| … | … | 上界每轮加一,链无穷 |
加宽(widening)记为 ∇,通过主动扩大结果保证收敛。一种区间加宽是在 Join 后比较新旧边界,把向外移动的边界推到相应的无穷:[0,1] ∇ [0,2] = [0,+∞)。之后回边贡献 [1,+∞),与入口 Join 仍为 [0,+∞),第 4 轮停止。本例保留了下界 0;一般情况下加宽可能丢掉仍然有效的有限边界。加宽位置、阈值与收窄(narrowing)见 Static Program Analysis 第 6 章。
11. 用 Soot 核对
复用第 02 篇的独立工程,在仓库根目录运行:
& './examples/static-analysis/run.ps1' -JdkHome 'C:/path/to/jdk-11'TaintWorklist.java 读取 BriefUnitGraph,实现上述规则和 FIFO 队列;遇到未知语句直接报错,避免把模型缺失当作安全。实际输出保存于 taint.txt:
- 原始分支:n6 的 IN 为
[x,y],与第 03 篇第 3 节的逐点表一致。 - 安全赋值变体:sink 输入不含 y。
- 循环:sink 输入为
[x,y,z],11 个实际节点共处理 22 次。
正文的 P、H、Z、Y、C、S 是为推演分组的教学节点,Soot 按单条 Jimple 语句编号:P = n1—n4,H = n5,Z = n6,Y = n7,C = n8—n9(flag=again() 与 goto),S = n10—n11(sink 与 return)。同一 FIFO 顺序下,P 的四个节点各处理 1 次,H、Z 及 S 的两个节点各 3 次,Y 及 C 的两个节点各 2 次,合计 4 + 12 + 6 = 22 次。
实现时有两处与第 6 节对应:出队就应清除“正在排队”的标记,使自环变化能重新调度当前节点;转移与合并不能原地修改仍被其他状态引用的集合。安全赋值变体中 Soot 移除了未使用的 x 接收变量,只保留丢弃返回值的 input 调用,因此实测 sink 处是空集合——分析结果应对应实际 IR 中的变量。示例用 retrieveActiveBody() 取方法体后直接调用求解器,并设置 jb 的 use-original-names 便于对照;若要随 Soot 流水线执行,可放入 BodyTransformer 注册到 jtp,见 Soot 的 Pack 与阶段说明。
本篇要点
- 有环时一遍算不完,工作列表按需安排重算:节点首次可达或 IN 改变时入队,已排队的只更新 IN,谁的输入变了就调度谁。
- 循环例子 13 次出队、S 处理三次,前两次“未发现 z”是中间结果;z 要绕一圈才到 S。
- 队列为空可判定不动点;完整求解得到最小不动点,求解完整不等于恢复合并损失。
- 单调 + 有限高度保证终止:单调让集合只朝一个方向变,有限高度让它走不了几步。单调不要求只增加事实。
- FIFO、LIFO、优先队列(如逆后序)只改变取出顺序和成本,完整求解的最小不动点相同;提前停止或引入加宽时除外。
- 时间上界
O((N+E)·(h+1)·c),h 是格高度不是元素个数;配套 Soot 核对与循环例子的处理次数一致。
数据流求解到此完整。下一篇把事实集合换成“变量对应的数值”,看同一套框架在值域上会丢失什么。
