01|程序分析的基本构成:状态、抽象与近似
静态分析根据程序结构和语义规则推导行为,无需实际运行程序。检查用户输入是否流入敏感操作,可以先跟踪赋值关系。
1. 分析保存和计算什么
1.1 从程序行为确定分析目标
约定 input() 返回不可信数据,sink() 检查实参是否携带该来源。先只考虑方法内的显式赋值和正常控制流:
void run(boolean flag) {
String x = input();
String y = "safe";
if (flag) {
y = x;
}
sink(y);
}目标性质是:是否存在一次执行,使来自 input 的数据经赋值到达 sink 的实参?
flag 为 true 时,y=x 把输入传给 y;为 false 时,y 保持常量 "safe"。因此存在从 input 到 sink 的传播。它是否构成 SQL 注入等漏洞,还取决于 sink 的具体操作和安全处理规则。
这个例子只有两条路线,可以逐一检查。面对循环、递归和大量输入,穷举执行通常不可行;在图灵完备的程序模型中,许多非平凡行为性质还不可判定。不存在一个通用算法能对所有程序精确回答“输入是否会到达 sink”这类问题(Rice 定理),静态分析因此需要近似程序行为。Static Program Analysis 第 1 章
1.2 具体状态、抽象状态与抽象域
具体程序状态(concrete state)描述某次执行在某个时刻的情况,包括程序位置、变量和内存中的值等。固定在 sink 之前,一次执行可能有 flag=true, x="alice", y="alice",另一次则可能有 flag=false, x="bob", y="safe"。
input 也可能恰好返回 "safe",仅凭字符串内容无法判断来源。本例在语义模型中给值附上来源标记,让标记随赋值传播;这个标记由模型定义,Java 字符串本身没有这样的字段。
只关心来源时,可以忽略字符串的每个字符,用集合保存可能有污点的变量。集合里的一个元素叫一条事实(fact):事实 x 表示“x 可能有污点”,若干事实组成的集合就是分析实际保存的抽象状态(abstract state):
| 抽象状态 | 它表示什么 |
|---|---|
∅ | x、y 都不带污点 |
{x} | x 可能有污点,y 不带污点 |
{y} | y 可能有污点,x 不带污点 |
{x,y} | x、y 分别可能有污点,不保留它们与条件之间的关联 |
{x,y} 允许两个变量同时有污点、只有一个有污点或都没有污点。它概括了允许出现的情况,其中可能包含程序实际上到不了的状态。
具体状态是一张运行快照,抽象状态则用一行简写概括许多快照,省去与分析目标无关的细节。
这四个元素构成示例的抽象域(abstract domain),即分析允许保存的全部抽象状态。令变量事实域 D={x,y},其幂集 𝒫(D)={∅,{x},{y},{x,y}} 就是所有子集组成的集合。空集 ∅ 表示“执行到了这里,但没有变量带污点”;第 03 篇另用可达标记表示“还没有执行到这里”。
用 γ(S) 表示抽象状态 S 所容许的具体状态集合,γ 读作 gamma。在固定程序点,S 中的变量允许带污点,S 外的变量必须干净,其他具体值不受这个域约束。
于是 γ({x}) ⊆ γ({x,y}):前者排除了 y 有污点的情况,更精确。⊆ 读作“是……的子集”;容许的具体状态越少,结果越精确。
1.3 转移函数与分支合并
转移函数(transfer function)描述一条语句怎样改变状态。在这个抽象域中,它计算污点集合的变化。
设语句前的抽象状态为 S:
| 语句 | 抽象转移规则 | 含义 |
|---|---|---|
x=input() | S∪{x} | 加入来源事实 |
y="safe" | S\{y} | 覆盖赋值清除旧 y 的污点 |
y=x | 从 S 删除旧 y;若赋值前 x 在 S 中,再加入 y | 根据右侧的来源决定新 y |
∪ 表示并集,S\{y} 表示从 S 删除 y。规则必须读取赋值前的右侧状态,例如自赋值 x=x 应保留原来的来源。
沿程序计算:
x=input() 后: {x}
y="safe" 后: {x}
执行 y=x 的分支末尾: {x,y}
跳过赋值的分支末尾: {x}两条控制流到达同一位置,称为控制流汇合(control-flow merge)。若此处只保存一个“可能有污点”集合,必须取并集:
{x,y} ∪ {x} = {x,y}取交集会得到 {x},从而排除 y 有污点;但 flag 为 true 的真实执行恰好会让 y 带污点,因此这种规则会漏掉目标传播。
并集保留了两条路径上的全部可能污点,也没有加入其他变量。在这个抽象域中,它是同时覆盖两边结果的最精确元素。
2. 抽象怎样影响精度
2.1 合并丢失条件关联
原程序的汇合结果 {x,y} 保留了 y 可能有污点,却没有保留 “y 有污点只发生在 flag=true 的分支”。修改最后一行即可暴露这项损失:
// 前面的来源、初始化和条件赋值均不变,flag 也未被修改
if (!flag) sink(y);flag 为 true 时,y 带污点,但 !flag 为假,进不了 sink。flag 为 false 时,能进入 sink,y 却仍是安全常量。两条真实路径都不会把污点送入 sink。
若合并时已经忘记条件,分析器便可能把 {x,y} 送入 sink,产生一条不存在的危险传播报告。这是误报(false positive)。若采用上一节错误的交集合并,在原程序中反而会遗漏真实传播,这是漏报(false negative)。
2.2 保留路径信息的收益与代价
可以保留带条件的两份状态:(flag=true,{x,y}) 和 (flag=false,{x})。遇到 !flag 时,前一份条件冲突,只有后一份可以进入 sink。
这种区分路径、在后续计算中利用路径条件的能力,称为路径敏感性(path sensitivity)。
代价是需要管理更多状态和约束。k 个相互独立的二分支最多产生 2^k 种分支选择组合,实际引擎通常通过合并或共享状态控制数量。能排除多少不可行路径,还取决于条件表达和求解能力。
3. 近似结果支持什么结论
3.1 过近似与欠近似
设 R 是指定入口条件下某程序点的真实可达状态集合。近似可以扩大这个集合,也可以只保留其中一部分:
欠近似 U ⊆ 真实结果 R ⊆ 过近似 O- 过近似(over-approximation)覆盖 R,允许包含不可达状态。
- 欠近似(under-approximation)只包含 R 中的状态,允许遗漏可达状态。
因此,过近似可用于证明模型内没有目标危险,欠近似可用于证明存在目标危险;下面用集合关系说明。
这里比较的都是具体状态集合。对于分析输出的变量集合 S,需要先用 γ(S) 解释它代表哪些状态,再与 R 比较。
沿用原程序,在 sink 前只看 (flag, y 的来源) 两项、忽略其他变量(这叫投影),所有输入允许的真实结果为:
R = {(true, 不可信), (false, 安全)}
O = {(true, 不可信), (true, 安全),
(false, 不可信), (false, 安全)}
U = {(false, 安全)}O 丢掉了条件与来源的关联;U 只保留安全分支,漏掉真实危险执行。这里比较的是同一投影上的状态集合,目标性质也只依赖这些信息。
令 Bad 表示违反目标性质的状态集合,∩ 为交集。由包含关系直接得到:
| 观察到的结果 | 过近似 O | 欠近似 U |
|---|---|---|
| 与 Bad 没有交集 | O∩Bad=∅ 推出 R∩Bad=∅,可证明模型内不存在目标危险 | U∩Bad=∅ 不能排除 R 的其他部分有危险 |
| 与 Bad 有交集 | 可能来自 O\R,需确认是否真实可达 | U∩Bad≠∅ 推出 R∩Bad≠∅,可证明存在真实危险 |
| 主要用途 | 安全性证明、保守筛查候选问题 | 错误存在性证明、寻找真实反例 |
代入上面的例子,令 Bad 为“y 的来源不可信”:U∩Bad=∅,但 R 里有 (true, 不可信),所以欠近似说“没问题”不可信;O 与 Bad 有交集,其中 (true, 不可信) 真实可达、(false, 不可信) 则来自 O\R,所以过近似说“有问题”时还要逐条确认。
错误性逻辑(Incorrectness Logic)用欠近似支持错误存在性推理。O’Hearn,Incorrectness Logic
欠近似要求留下的状态确实可达。只探索少量路径,却对库行为做了过近似,或没有确认路径条件可满足,仍可能报告虚构行为。确认一条复杂路径可行也可能很昂贵;进一步生成具体触发输入,还需要相应的求解能力。
3.2 可靠性与精确度是不同要求
本系列以保守的过近似分析为主。分析可靠(sound),指在规定语义、入口和模型下满足 R⊆γ(S):结果覆盖全部真实可达状态。抽象转移也应保持覆盖关系,才能避免遗漏模型内的目标危险。抽象解释为这种语义对应与正确性论证提供了框架。Cousot 与 Cousot,Abstract Interpretation
精确度(precision)按容许的状态比较:若 γ(S₁)⊆γ(S₂),则 S₁ 至少与 S₂ 一样精确。可靠过近似越接近 R,额外状态越少;删除真实状态会破坏可靠性,不能作为有效的精度改进。
实现中的覆盖要求贯穿模型、规则和求解:遗漏一个调用目标、用交集合并可能污点,或把尚未传播完的集合当成最终结果,都可能漏报。
求解超时后,只有工具另行给出保守结果,才能继续使用相应保证。实际的“没有告警”还可能来自规则未启用或结果被过滤;用它证明安全,需要先确认分析完整覆盖并检查了目标性质。
3.3 may/must 不等于过近似/欠近似
两组概念比较的对象不同:
- may/must说明事实是“可能成立”还是“在所有相关路径上都保证成立”。
- 过近似/欠近似说明所表示的状态或行为集合与真实结果的包含方向。
例如,“保证已初始化”的事实集合从 {x,y} 减为 {x},保证减少,却允许更多具体状态:y 可以已初始化,也可以未初始化。因此,must 分析也可以通过扩大所容许的状态来做保守过近似。
判断近似方向,要先解释一个事实集合代表哪些具体情况,再比较这些情况与真实行为。具体的 may/must 合并与信息顺序在第 03 篇展开,重算与收敛在第 04 篇说明。
本篇要点
- 抽象状态概括一组具体状态,转移函数计算语句带来的变化。
- 可能污点在汇合处取并集;丢失条件关联可能误报,保留路径条件需要更多状态。
- 可靠过近似满足
R⊆γ(S),可证明模型内没有目标危险;欠近似可证明危险存在。 - may/must 描述事实的含义,过近似/欠近似描述行为集合的包含方向。
将这些规则用于分析器,还需要构建程序表示、求解并解释结果:
下一篇先解决第一步:Java 字节码、Jimple 与控制流图。
