AST / CFG / PDG / IFDS 详解

摘要

零、先记住一句话

名字	回答什么问题	一句话
AST 抽象语法树	代码”长什么样”？	把源码解析成树，知道哪段是函数、哪段是 if
CFG 控制流图	代码”怎么执行”？	画出执行路径，知道下一步会走哪
PDG 程序依赖图	代码”谁依赖谁”？	画出数据和控制依赖，知道值从哪来
IFDS 污点算法	污点”能不能流到终点”？	在 PDG 上跑的跨函数求解算法

CPG = AST + CFG + PDG 合在一张图里。Joern 用的就是 CPG。

---

一、一个运行示例

整篇文章围绕这段代码：

def handler(req):
    name = req.get("name")                          # ① 从 HTTP 取输入
    pwd  = req.get("pwd")                           # ②
    if len(pwd) < 8:                                # ③ 判断长度
        return "weak"                               # ④ 过短拒绝
    sql = "SELECT * FROM u WHERE n='" + name + "'"  # ⑤ 拼 SQL（漏洞在这）
    db.execute(sql)                                 # ⑥ 执行 SQL（sink）
    return "ok"                                     # ⑦

这是一段经典的 SQL 注入雏形。我们要让工具自动发现”第 ⑥ 行有注入”。

---

二、AST — 抽象语法树

2.1 定义

AST 把代码解析成一棵树，每个节点是一个语法元素，父子关系 = 语法嵌套关系。

2.2 我们示例的 AST 长这样

2.3 AST 能回答什么

• “这是不是一个函数调用？” ✅
• “它的第二个参数是什么？” ✅ —— 往下走一层拿到 argument 子树
• “整个函数里有几个 if？” ✅ —— 递归遍历树

2.4 AST 回答不了什么

• “if 条件不成立时，下一步执行第几行？” ❌ —— AST 只有”包含”关系，没有”执行顺序”
• “sql 的值从哪里来？” ❌ —— AST 只能告诉你”sql 是一个变量”，不知道它被谁赋过值

应用场景：代码格式化（Prettier/Black）、语法高亮、简单的 lint 规则（”禁止用 eval”只要找到 AST 里有 Call(eval) 即可）、SAST 的结构规则（如 WeakCryptoPyRule：只要有 hashlib.md5( 就报）

---

三、CFG — 控制流图

3.1 定义

CFG 把代码画成有向图，节点是”基本块”或语句，边代表”执行完 A 接着执行 B”。

3.2 我们示例的 CFG

3.3 CFG 能回答什么

• “从函数入口能到达第 ⑥ 行吗？” ✅ 路径是 ①→②→③(False)→⑤→⑥
• “第 ④ 行之后还会执行第 ⑥ 行吗？” ❌ ④ 是 return，走不到 ⑥
• “函数里有没有死代码？” ✅ 遍历一遍没人指向的节点就是死代码

3.4 CFG 回答不了什么

• “第 ⑥ 行执行时 sql 的值受哪些变量影响？” ❌ —— CFG 只关心”走到哪”，不关心”值从哪来”

应用场景：可达性分析（Reachability）、单元测试覆盖率（测试走了哪些边）、未认证路由检测（CFG 告诉你路由函数体里哪些分支”没经过 auth 检查就返回”）

---

四、PDG — 程序依赖图

这是污点分析的核心，一定要理解。

4.1 定义

PDG 由两部分组成：

子图	全称	表达什么
DDG	Data Dependence Graph	数据依赖：A 写变量 v，B 读 v，则 B 数据依赖 A
CDG	Control Dependence Graph	控制依赖：A 是条件语句，B 的执行与否由 A 决定，则 B 控制依赖 A

4.2 我们示例的 PDG

*DDG 数据依赖CDG 控制依赖

边的含义是**”我需要你的值才能工作”**：

① name = req.get("name")      ← 写入 name
         ↓ name 被⑤读
⑤ sql = "..." + name + "..."  ← 写入 sql，读 name
         ↓ sql 被⑥读
⑥ db.execute(sql)             ← 读 sql

② pwd = req.get("pwd")        ← 写入 pwd
         ↓ pwd 被③读
③ if len(pwd) < 8

核心链条：① name → ⑤ sql → ⑥ db.execute(sql)，这就是污点传播路径。

边的含义是**”我的执行与否由你决定”**：

③ if len(pwd) < 8
    ├──(True分支)──→ ④ return "weak"
    └──(False分支)──→ ⑤ sql=...
                      ⑥ db.execute
                      ⑦ return "ok"

④⑤⑥⑦ 都控制依赖 ③（如果 ③ 的条件不同，它们执行与否就不同）。

4.3 PDG 能回答什么（关键！）

污点分析要回答的问题就是”DDG 上是否存在一条路径”：

第 ⑥ 行 db.execute(sql) 的参数 sql，是否可能最终来自外部输入？

沿 DDG 反向追：

⑥ 的 sql ←(DDG)← ⑤ 的 sql ←(DDG)← ⑤ 里用到的 name ←(DDG)← ① 的 name ←(DDG)← req.get(...)

✅ 能追到 req.get(...)，这就是用户输入！所以第 ⑥ 行是 SQL 注入漏洞。

4.4 AST、CFG、PDG 的差异对比

对同一行代码 sql = "..." + name + "..."：

问题	用 AST	用 CFG	用 PDG/DDG
这是一个赋值语句？	✅	❌	❌
这行执行后下一行是什么？	❌	✅	❌
这行的 name 值从哪来？	❌	❌	✅
这行写的 sql 会被谁用？	❌	❌	✅

三种图各答各的问题，合在一起才构成 CPG。

---

五、CPG — 三合一

5.1 CPG 就是把 AST/CFG/PDG 的节点合并、所有边保留

同一个”语句”节点，可以：

• 通过 AST 边（蓝色实线）往下找参数（”这个 execute 的第一个参数是 sql 变量”）
• 通过 CFG 边（绿色粗线）往后找下一句（”execute 之后是 return”）
• 通过 DDG 边（橙色虚线）往前找数据来源（”sql 的值来自上一句的拼接，上一句的 name 又来自 req.get”）
• 通过 CDG 边（紫色点线）判断控制条件（”这行是否受某个 if 条件控制”）

5.2 本项目如何查询 CPG

Joern 的 Scala DSL 对应到三种图：

// AST：直接获取子节点
sinkCall.argument.order(1)

// CFG：获取执行顺序的下一个节点
node.cfgNext

// DDG：获取数据流前驱/后继
sinkCall.reachingDef

// 一键调用：把 DDG 边跑通，找 source → sink 的所有路径
sinks.reachableByFlows(sources)

最后这一行就是在 DDG 上跑图搜索，寻找”有没有一条边路径从某个 source 节点走到 sink 节点”。

---

六、IFDS — 让污点追踪变得可扩展的算法

6.1 为什么需要 IFDS

上面第 4.3 节我们手工追了一次污点：从第 ⑥ 行反查到 req.get。看起来简单，但真实代码有两个难点：

1. 跨函数：sql 可能是调用另一个函数返回的 → 要追进那个函数
2. 跨文件 / 跨模块：req 可能来自几层调用栈外的路由处理函数

IFDS（Interprocedural, Finite, Distributive, Subset problem）是 1995 年 Reps/Horwitz/Sagiv 提出的算法，它把”能否从 source 流到 sink”这个问题建模为一个图可达性问题，并且在多项式时间内完成跨过程分析。

6.2 IFDS 图解

6.3 IFDS 解决的四件事

缩写	英文	含义	简单理解
IFDS	Interprocedural	跨过程	能追进/追出函数
IFDS	Finite	有限数据域	“污点/不污点” 这种有限状态
IFDS	Distributive	可分配	多个污点可以独立追踪再合并
IFDS	Subset	子集语义	用集合表示”当前哪些变量被污染了”

6.4 IFDS 的核心思想：超图上的可达性

IFDS 把代码看成一张超级图（supergraph）：

• 每个函数内部是一张 CFG + PDG
• 跨函数通过”调用边”和”返回边”连接

然后追踪一个叫做 dataflow fact 的东西（比如”变量 x 现在是污点”），问：

从 source 处的 fact {x tainted} 出发，沿图走，能不能到达 sink 处的 fact {y tainted}？

这就是 IFDS 求解器要算的。能到达 = 漏洞存在。

6.5 在本项目中的体现

TaintRuleBuilder.scala 里这一行：

sinks.iterator.reachableByFlows(sources.iterator).l

就是对 Joern 的 IFDS 求解器发出查询：”从这批 source 节点出发，在 CPG 的数据流子图上，能到达这批 sink 节点中哪些？”

返回的 Path 里每一步都是 IFDS 找到的中间节点，本项目把它转成 FlowStep 列表输出到报告里。

6.6 IFDS 的局限

IFDS 不是万能的：

• 动态类型不友好：Python 没类型注解时，IFDS 可能不知道 a.foo() 调的是哪个方法，断链
• 容器追踪弱：list.append(taint); x = list[0] 这种容器内污点不一定传得过来（本项目用 FaasSemantics 手动补了很多此类规则）
• 性能：代码大到一定程度会很慢

本项目在 IFDS 之外还加了一个”3 跳反向赋值追溯“的句法兜底（TaintRuleBuilder.sinkArgIdentifierTainted）——当 IFDS 失败时，简单遍历一下 sink 附近方法内的赋值链也能抓回不少漏报。

---

七、一图总览

---

八、推荐阅读

• 论文：Yamaguchi et al. Modeling and Discovering Vulnerabilities with Code Property Graphs (S&P 2014) —— CPG 原论文
• 论文：Reps, Horwitz, Sagiv. Precise Interprocedural Dataflow Analysis via Graph Reachability (POPL 1995) —— IFDS 原论文
• 书：Appel, Modern Compiler Implementation —— AST/CFG/数据流分析的教科书级解释
• 工具：Joern Docs —— 本项目用的 CPG 引擎
• 工具：CodeQL Documentation —— 对比学习另一派污点分析

---

附：术语速查

术语	英文全称	本文中的意思
AST	Abstract Syntax Tree	抽象语法树，描述”代码语法结构”
CFG	Control Flow Graph	控制流图，描述”执行顺序”
PDG	Program Dependence Graph	程序依赖图，DDG + CDG
DDG	Data Dependence Graph	数据依赖图，变量读写依赖
CDG	Control Dependence Graph	控制依赖图，条件决定执行
CPG	Code Property Graph	AST + CFG + PDG 三合一
IFDS	Interprocedural, Finite, Distributive, Subset	跨过程污点分析的经典算法
Source	—	污染入口节点（如 request.args）
Sink	—	危险出口节点（如 db.execute）
Sanitizer	—	清洗节点（如 html.escape）
Taint	—	污点；”这个值可被攻击者控制”的标记