03|数据流分析与格:状态怎样传播和合并
第 02 篇建好了 CFG。现在为节点添加污点状态,计算哪些来源可能到达 sink。
1. 节点的输入、输出与初始状态
沿用上一例,input() 产生不可信数据,sink(y) 检查 y;集合 {x,y} 表示两者分别可能有污点。
本篇只处理单方法、局部变量、显式赋值与正常控制流。布尔参数不携带污点;调用不展开,input 与 sink 使用明确模型。第 04 篇的配套实现对未知语句直接报错,避免将缺失模型悄悄当作安全。
对每个节点 n,记录:
- IN[n]:语句执行前可能有污点的变量。
- OUT[n]:语句执行后可能有污点的变量。
- 可达标记:是否已有入口路径到达该节点。不可达与可达但集合为空分开保存。
可以把 IN、OUT 看作语句前后的两块黑板:语句读取 IN、写出 OUT,再传给后继。
入口可达,IN 为空集;其他节点初始不可达。这里只在可达节点执行规则。
2. 转移规则与合并规则
沿用第 01 篇的转移规则。输入集合为 S,S\{y} 表示删除 y,∪ 为并集,∅ 为空集。
| 语句 | 输出规则 | 输入 {x,y} 时 |
|---|---|---|
flag := @parameter0(参数绑定) | S\{flag}:布尔参数不携带污点 | {x,y} |
x=input() | S∪{x} | {x,y} |
y="safe" | S\{y} | {x} |
y=x | 先删除旧 y;若输入 S 含 x,再加入 y | {x,y} |
| 分支、跳转、sink、return | 保留 S | {x,y} |
复制规则必须读取赋值前的 x。例如 x=x 不会消除自己的污点;若先修改输入集合再检查右侧,就可能实现错。
本例是向前分析(forward analysis):信息沿执行方向流动,从前驱的 OUT 计算后继的 IN。合并处取所有可达前驱的并集:
IN[n] = 所有可达前驱 OUT 的并集(入口另有边界条件)
OUT[n] = 当前语句的转移规则(IN[n])3. 把 n1—n7 算完
| 节点 | 语句简写 | IN | OUT |
|---|---|---|---|
| n1 | 参数绑定 flag | ∅ | ∅ |
| n2 | x=input() | ∅ | {x} |
| n3 | y="safe" | {x} | {x} |
| n4 | if flag==false goto n6 | {x} | {x} |
| n5 | y=x | {x} | {x,y} |
| n6 | sink(y) | {x,y} | {x,y} |
| n7 | return | {x,y} | {x,y} |
关键在 n6:它既可以从 n4 直接到达,也可以从 n5 到达。
n4 → n6 贡献 {x}
n5 → n6 贡献 {x,y}
IN[n6] = {x} ∪ {x,y} = {x,y}只要一条路径让 y 带污点,汇合后就要保留这种可能性。这是 may 分析:判断某事实是否可能成立。
4. “保证已初始化”为什么反而取交集?
换一个问题,用集合表示在所有到达路径上都已初始化的变量。下面是用于说明规则的伪代码;类似的未确定赋值读取在 Java 中会被编译器拒绝。
声明 x、y,尚未赋值
x = 1
if flag:
y = 2
使用 x、y| 到达汇合点的路径 | 保证已初始化 |
|---|---|
| 执行 y=2 | {x,y} |
| 跳过 y=2 | {x} |
只有 x 在两条路径上都有保证,所以合并为 {x,y}∩{x}={x},∩ 读作交集。这是 must 分析:要求某事实在所有所考虑的到达路径上成立。
污点并集放弃了“y 一定安全”,初始化交集放弃了“y 一定已初始化”,两者都损失信息。下面用偏序描述这种精度变化,再用格统一解释合并。
不可达前驱不应削弱初始化保证。尚未到达的节点与“可达但没有任何保证”不能混为一谈;第 7 节会结合顶、底元素解释这一点。
5. 用偏序比较信息精度
先看同一对集合 {x}、{x,y},但赋予它们不同含义:
| 分析 | {x} 的含义 | {x,y} 的含义 | 哪个提供更多信息 |
|---|---|---|---|
| 可能有污点 | 只有 x 被列为可能有污点,排除了 y | x、y 都可能有污点 | {x},排除了更多可能性 |
| 保证已初始化 | 只保证 x | 同时保证 x、y | {x,y},提供了更多保证 |
本系列固定约定:越往上越不精确。 a ⊑ b 读作“a 在偏序下小于或等于 b”,表示 a 至少和 b 一样精确,也可以读成“a 不比 b 更粗”。
于是两种分析选择不同的集合关系:
| 集合的语义 | 本文的偏序定义 | 例子 |
|---|---|---|
| 可能有污点 | A ⊑ B 当且仅当 A ⊆ B | {x} ⊑ {x,y} |
| 保证已初始化 | A ⊑ B 当且仅当 A ⊇ B | {x,y} ⊑ {x} |
⊆ 读作“是……的子集”,允许相等;⊇ 读作“是……的超集”。
偏序(partial order)须满足三个条件:
- 自反性:
a ⊑ a,读作“a 小于或等于它自己”。 - 反对称性:若
a ⊑ b且b ⊑ a,则a=b。 - 传递性:若
a ⊑ b且b ⊑ c,则a ⊑ c。
偏序不要求任意两个元素都能比较。按包含关系,{x} 和 {y} 互不包含;它们排除了不同的可能性。全序(total order)还要求任意两个元素可比较,例如整数上的 ≤。
6. 幂集与格图怎么看?
令 D={x,y}。幂集(power set)𝒫(D) 就是 D 的所有子集组成的集合:
𝒫({x,y}) = { ∅, {x}, {y}, {x,y} }𝒫 读作“幂集”,∅ 是空集,外层花括号列出四个元素,其中每个元素本身也是集合。
下面两张图都使用这四个元素。线段连接相邻的可比较元素,向上表示按 ⊑ 变大,即信息变粗;它们不是程序执行箭头。
污点图的顶部表示“x、y 都可能有污点”;初始化图的顶部表示“不能保证任何变量已初始化”。两者都是各自域中最粗的结果。
7. Join:为什么这样合并?
对于 a、b,上界(upper bound)是同时位于它们上方或与它们相等的元素。上界中最小的一个叫最小上界(least upper bound),也叫 Join,写作 a ⊔ b,读作“a Join b”。
Join 可看作“同时装下两边的最小盒子”。污点集合 {x} 与 {y} 的 Join 是 {x,y}:覆盖两边,又没有多加变量。
| 场景 | 两个输入 | Join 的结果 | 运算 |
|---|---|---|---|
| 可能有污点 | {x} 与 {y} | {x,y} | 并集 ∪ |
| 保证已初始化 | {x} 与 {y} | ∅ | 交集 ∩ |
对应地,最大下界(greatest lower bound)叫 Meet,记为 ⊓,读作“a Meet b”。在污点图中是交集,在初始化图中是并集。这两种分析的路径汇合都使用上表的 Join。
每一对元素都存在 Join 和 Meet 的偏序集叫格(lattice)。若任意子集都有最小上界和最大下界,则是完全格(complete lattice)。有限格自动满足这一条件,本节的四元素幂集就是完全格。格保证任意两个结果都有唯一的最小上界,可用来定义合并。
最大元素写作 ⊤,读作 top;最小元素写作 ⊥,读作 bottom。污点域的顶、底分别是 D、∅,初始化保证域反过来。
污点域的 ∅ 表示没有变量可能有污点,可达的安全程序点也可以取得这个结果。本篇用独立的可达标记区分空集合与不可达;若将不可达加入整体状态域,它还需要自己的最小元素。
初始化保证按反向包含排序,底是 D。传统集合实现以 D 初始化非入口节点,再通过交集逐步撤销保证;入口则设置为实际已初始化的参数等。初始的 D 只是求解起点,保证要等求解完成才成立。若采用独立不可达状态,未到达节点暂不贡献,首次到达时接收前驱保证,后续再取交集。不能把所有节点预置为空集,否则交集会把真实的保证抹掉。
8. 补充:为什么别的教材叫 Meet?
有些教材选择“越往上越精确”。把整个偏序反过来,就是序对偶(order duality):原顺序的最小上界变成新顺序的最大下界。
例如 Cornell 的迭代数据流讲义使用从顶开始的下降迭代。读法应服从该资料自身的格约定。
以可能有污点为例:
约定(⇔ 读作“当且仅当”) | 精度向上怎样变化 | 路径汇合 | 运算名字 |
|---|---|---|---|
A⊑B ⇔ A⊆B | 更粗 | 并集 | Join |
A⊑B ⇔ A⊇B | 更精确 | 并集 | Meet |
阅读其他资料时,先确认 ⊑、顶底元素和图的方向;运算名称会随顺序反转,可能污点的保守合并仍取并集。
本篇要点
- IN/OUT 保存语句前后的状态;可达标记区分“未到达”和“已到达但无污点”。
y=x覆盖旧 y,但必须读取赋值前的 x;自赋值保留污点。- 可能污点取并集,初始化保证取交集;合并方式取决于事实的含义。
- 偏序比较精度,本系列向上更粗;格上的 Join 是同时容纳两边结果的最小上界。
- 污点域的空集与不可达不同;初始化保证的空集也不能随意用作所有节点的初值。
数据流方程和合并规则已经明确。遇到循环时,怎样安排重算,又怎样判断所有结果已经稳定?下一篇用工作列表的完整轨迹回答。
