静态分析系列:从程序表示到过程间求解
2026/9/30大约 4 分钟
这个系列从一段 Java 污点程序出发,介绍程序表示、数据流规则、过程间求解,以及精度与计算成本。面向熟悉 Java、第一次接触静态分析的开发者,按一门课的方式顺读。
第 02、04 篇与第 11 篇配有可运行的 Soot 示例,其余篇目通过计算推演和原始文献讲解。
怎样读这门课
- 先按下面的阅读路线或依赖图选篇;跳读选择(05、09/10、11 与 07)只在总览维护,正文不再另写入学须知。
- 结尾有要点或总结:读完先合上页面自己复述一遍,再对照。
- 遇到公式先看紧跟其后的直白说法,再回头看公式;每个符号首次出现时都给了读法。所有术语集中在术语表,忘了就查。
- 每篇的表格推演(逐点事实表、工作列表表、摘要步骤表)都可以手算:先盖住结果列,自己算一遍,再对照。这比读三遍更有效。
- 第 02、04 篇和第 11 篇有可运行示例,建议实际跑一次,把输出和正文的表对上。
- 09、10 是专题,第一遍可以跳过;05 是值分析基础,只关心污点分析的读者可以先跳过,到 08 之前再补。
知识总览
篇目与主题
| 篇目 | 核心问题 | 学完应能做什么 |
|---|---|---|
| 01 状态、抽象与近似 | 分析保存什么,近似怎样影响结论? | 理解状态、转移与合并,区分过近似与欠近似、可靠性与精度 |
| 02 编译流程与分析工具 | Soot 怎样把 Java 变成分析对象? | 对照源码、字节码、Jimple、CFG;Coverity/Clang 为可选对照 |
| 03 数据流分析与格 | 状态怎样传播,为什么这样合并? | 手算分支的 IN/OUT,用 may/must 理解偏序、格与 Join |
| 04 工作列表与不动点 | 哪些节点需要重算,什么时候可以停? | 逐行跟踪工作列表,解释收敛,比较调度策略与迭代算法,估算复杂度并用 Soot 核对 |
| 05 常量传播与表达式求值 | 能否确定一个变量的值? | 计算常量状态,识别合并丢失的变量关联 |
| 06 调用关系与上下文 | 信息跨方法后怎样正确返回,调用目标从哪里来? | 区分调用图、ICFG、参数映射与调用上下文;对比 CHA 与基于指向的调用图 |
| 07 IFDS 事实传播 | 何时能把集合拆成单事实求解? | 验证分配性,读懂双调用 ESG,跟踪匹配返回、摘要与递归去重 |
| 08 IDE 值传播 | 如何复用输入到输出的值变换? | 组合、合并边函数,解释跳转函数与两阶段求解 |
| 09 符号执行与 Clang | 如何排除条件冲突的路径? | 推演符号状态,并对应到 Clang 的状态与检查器 |
| 10 IDE 求解器工程优化 | 大量中间条目怎样存、查、回收? | 解释论文的访问布局、回收条件及实验基线,定位稀疏化与按需求解等其他路线 |
| 11 对象、别名与指针分析 | 两个变量何时可能指向同一对象? | 手算 Andersen 式指向集合与字段传播,解释上下文敏感与上下文敏感堆,用指向结果精化调用图 |
阅读路线
- 首次系统阅读:01—08 顺读,再读 11,最后选读 09、10。
- 先建立整体认识:01→02→03→04。
- 以污点理解 IFDS:01→02→03→04→06→07。
- 深入值计算:补上 05,再进入 08→10。
- 关心路径精度:06→09;09 的 IFDS/IDE 比较部分在 07、08 后阅读。
- 走向真实 Java 污点分析:06→11(07 可选,只在说明事实域为何看不到字段时用到),再接后续的污点分析实践与覆盖边界两篇。
依赖图中的实线表示前置知识,虚线表示比较部分的额外前提。09、10、11 是独立专题,05 也不是学习过程间污点传播的必修前提。
实践与后续专题
配套工程使用公开版 Soot 4.7.1 与 JDK 11,包含程序表示、污点传播、Spark 指向分析的实现及预期输出。
第二阶段把贯穿全系列的污点例子推进到真实 Java 分析器的形态。11 对象、别名与指针分析已完成;12 污点分析实践(访问路径、净化与库模型)与 13 分析覆盖边界(调用图、反射与 soundiness)已定题与提纲,尚未成篇。
