GitNexus PDG深潜：CFG、REACHING_DEF、CDG与污点分析原理，一篇讲透的完整指南

GitNexus PDG深潜：CFG、REACHING_DEF、CDG与污点分析原理，一篇讲透的完整指南

【免费下载链接】GitNexusGitNexus: The Zero-Server Code Intelligence Engine - GitNexus is a client-side knowledge graph creator that runs entirely in your browser. Drop in a git repository (Github, Gitlab, Azure, Local) or ZIP file, and get an interactive knowledge graph with a built in Graph RAG Agent. Perfect for code exploration项目地址: https://gitcode.com/GitHub_Trending/gi/GitNexus

GitNexus 是一款零服务器的代码智能引擎（Zero-Server Code Intelligence Engine）：把一个 git 仓库或 ZIP 拖进浏览器，就能得到带 Graph RAG Agent 的交互式代码知识图谱。它还有一个常被新手忽略的"隐藏大招"——--pdg程序依赖图（Program Dependence Graph）层。本文带你深潜 GitNexus 的 PDG 内核，用大白话讲清楚CFG（控制流图）、REACHING_DEF（到达定义数据流分析）、CDG（控制依赖图）和污点分析四层是如何一步步搭起来、又如何回答"这段代码改坏了哪里""用户输入流向了哪"这类硬核问题的。🔍

为什么需要 PDG：从"调用关系"到"数据流动"

普通的代码知识图谱只记录结构关系：谁调用谁、谁继承谁。它回答不了两类关键问题：

• 🎯影响分析：我改了第 42 行这个变量赋值，函数里后面哪些语句会受影响？
• 🎯安全追踪：用户从req.body输入的污点数据，一路"流动"到了exec()这样的危险调用吗？

这两类问题属于程序分析（Program Analysis）的领地。GitNexus 用一套分层 substrate（底层地基）来回答它们，而且全部由纯函数求解器驱动——无 I/O、无日志、确定性输出，同样代码每次分析结果字节级一致。

PDG 全景图：四层地基一次看全

GitNexus 的 PDG 按里程碑（M1–M5）分层构建，每一层都站在上一层的肩膀上。核心分层如下：

这些层都藏在同一个CodeRelation表里（以边类型区分），默认不开启--pdg的分析运行完全不受影响——输出与未启用时字节级相同。

分层设计的详细文档可以直接查阅项目内的专家技能文档：gitnexus-pdg-query.md 和 gitnexus-taint-analysis.md。

L1 · CFG 控制流图：把函数拆成"基本块"拼图

基本块是什么？

基本块（Basic Block）是一段"直线执行"的语句：进去之后必须一路执行到底，中途不会跳转也不会被打断。GitNexus 为每个函数自动合成两个特殊块：

• ENTRY（入口，固定是 0 号块）
• EXIT（出口）

块与块之间由控制流边连接，每条边带一个"跳转原因"标签。这些标签直接决定了图的语义：

谁来建图：解析 Worker + 语言访问器

CFG 构建遵循一个重要的工程契约：Worker 建图，主线程求解。

1. 解析 Worker（拥有 AST 的地方）里，每种语言实现一个CfgVisitor，配合语言无关的累加器 cfg-builder.ts 把语句流切成基本块、连好边，顺便采集每语句的def/use 事实（谁被定义、谁被使用）；
2. 产出的FunctionCfg是纯 JSON 可序列化数据——不含任何 AST 节点引用，通过cfgSideChannel传回主线程；
3. 主线程绝不重新解析代码（这是为了避免重解析导致的 OOM），只运行纯求解器。

数据模型定义在 types.ts：FunctionCfg（函数级 CFG）、BasicBlockData（基本块）、CfgEdgeData（边）、StatementFacts（语句 def/use 事实）、BindingEntry（变量绑定表）。其中绑定表用整数索引代替变量名，序列化体积比"每次出现都记名字"小约 4 倍。

L2 · REACHING_DEF 到达定义：追踪"赋值→使用"的流动

经典问题，双引擎求解

到达定义（Reaching Definitions）是编译器里的经典分析：某个变量在第 A 行的赋值，能否"活着"地流到第 B 行的使用？

教科书答案是GEN/KILL 工作列表迭代：每个基本块有一组"生成"（新赋值）和"杀死"（重新赋值使旧值失效）集合，反复迭代直到不动点。

GitNexus 在 reaching-defs.ts 中实现了一个更聪明的双求解器：

• 密集工作列表（GEN/KILL）：适合小函数和无循环函数，简单直接；
• SSA 稀疏求解器：基于 Cytron 支配前沿 + φ 函数放置 + 栈式重命名，没有不动点迭代，一次遍历出结果，对含深循环的大函数渐近更快、内存更稳。

生产环境由computeInSetsAuto自动分派：函数足够大且有循环 → 走 SSA；否则 → 走密集求解。两条路径被等价性模糊测试锁死为输出完全一致。

输出：语句粒度的 def→use 事实

最终产物是DefUseFact数组——每一条都精确到"块:语句"位置：

变量 x 在 第3块:第2句 的定义 → 到达了 第5块:第0句 的使用

这些事实就是 L3 污点分析和pdg_query的flows模式的数据底座。为防止病态代码（N 个分支定义 × N 个后续使用 = N² 条事实）撑爆内存，每个函数默认截断在 4000 条边（emit.ts 中的DEFAULT_PDG_MAX_REACHING_DEF_EDGES_PER_FUNCTION），且截断是可观察的——绝不悄悄丢弃。

L5 · CDG 控制依赖图："受谁控制"的依赖边

从后支配到控制依赖

到达定义解决的是数据依赖，而 CDG（Control Dependence Graph，控制依赖图）解决的是控制依赖：一个块之所以执行，是因为前面某个分支块"决定"了它。

形式化定义（Ferrante–Ottenstein–Warren §3.1.1）：块B控制依赖于分支块C，当且仅当存在边C → B'，使得B后支配B'但不后支配C本身。

GitNexus 在 control-dependence.ts 中采用了工业界（LLVM、Joern、WALA 同款）的高效做法：控制依赖 = 反向 CFG 的支配前沿。在 post-dominators.ts 构建的后支配树上自底向上计算，复杂度 O(N + E + 输出)。

一个精妙细节：T/F 分支极性

每条 CDG 边都带一个T/F标签（控制边对应分支的哪一侧）。有趣的是，if (!ok) return;这样的守卫式写法中，return 走的是条件的T臂，而受保护的主逻辑走F臂——极性取决于守卫的写法，不能想当然。这正是 CDG 能帮你精准定位**守卫子句（guard clause）**的原因。

L3/L4 · 污点分析：从 source 到 sink 的"数据侦探"

函数内污点：两条规则 + 精准消毒

propagate.ts 实现前向污点传播，模型只有两条规则：

1. 语句内直达：exec(req.body)——source 和 sink 同句出现，直接命中；
2. 工作列表传播：被污染的(变量, 定义点)沿 REACHING_DEF 的 def→use 事实流动，每到达一个 sink 参数位就产出一条 finding。

消毒器（Sanitizer）的"种类集合"模型 ✨

这是 GitNexus 污点引擎最见功力的设计。朴素的二元 kill（"消毒一次就全干净"）会酿成大祸：

• const safe = escape(req.body); db.query(safe)—— HTML 转义不能中和 SQL 注入！

所以 GitNexus 的污点携带一个已中和 sink 种类集合：escape()只中和xss类 sink，不中和sql类。res.send(safe)被正确抑制，而db.query(safe)依然会被报告。

另一处精妙：exec(escape(x))与exec(x)必须能区分。采集阶段（SiteRecord）记录了嵌套调用结构，污点引擎据此判断消毒器是否恰好横插在这个 sink 的这条路径上；多条路径取交集（cond ? escape(b) : b的直通分支会把保护全部抵消）。

跨函数污点：Sharir–Pnueli 摘要法

跨过程分析没有采用全量 IFDS 建表，而是业界（Meta Pysa、Mariana Trench 同款）的函数摘要法：每个函数先压缩成一个紧凑摘要（参数→返回值、参数→sink、参数→callee 参数位等六种边），再在已解析的CALLS调用图上做不动点组合，见 interproc-solver.ts。求解单元是(函数, 参数, source)，被污染参数撞上param→sink摘要边时产出 finding。

实战：如何用 pdg_query 查询依赖

索引时加--pdg，随后就能通过 MCP 的pdg_query工具直接查询。两种模式对应两条边：

target（文件路径或函数名）必填——查询永远锚定 + 分页有界，避免无锚点的全图扫描。GitNexus 还可以作为 MCP Server 接入 AI 编码工具，让 Agent 在改代码前自动做依赖查询，如图所示：

工程细节：为什么它"不会翻车"

这套分析引擎面对真实仓库的"恶意"输入做了大量防护，值得新手借鉴：

• 🛡️纯求解器契约：computeReachingDefs、computeTaintFlows等全是纯函数——无图、无 I/O、输出显式排序，快照测试稳定，边 ID 由内容派生；
• 🛡️每函数配额：CFG 边默认 5000 条、REACHING_DEF 4000 条、CDG 5000 条，超限即截断并打标truncated，可观察、不静默；
• 🛡️嵌套深度护栏：CFG 递归下降深度超过 500 层（机器生成代码才会触发）时抛出确定性的CfgNestingDepthError，只隔离该函数，而不是让整个 Worker 栈溢出；
• 🛡️迭代预算：密集求解器对病态深循环嵌套有访问预算，超预算时回退到 SSA 求解器或安全截断——宁可不报，不报错误结果。

源码导航：想深潜看哪里？

想自己动手读代码，按下面这条线走效率最高：

1. 数据模型：types.ts — 所有 PDG 相关类型的定义与注释
2. 建图：cfg-builder.ts — 语言无关的 CFG 累加器
3. 数据流求解：reaching-defs.ts — 双求解器到达定义
4. 控制依赖：control-dependence.ts + post-dominators.ts
5. 污点引擎：propagate.ts（函数内）与 interproc-solver.ts（跨函数）
6. 图发射：emit.ts — 把求解结果写成持久化图边
7. 查询消费端：pdg-impact.ts —pdg_query与影响分析如何遍历这些边
8. 基准测试：bench/cfg/ 与 bench/impact-pdg/ — 各层的性能基线与验收场景

写在最后

GitNexus 的 PDG 子系统是一个教科书级分层案例：CFG 打地基 → 到达定义铺数据流 → CDG 补控制流 → 污点分析站在两者之上，四层各司其职、纯函数可测试、配额可观察。对新手来说，理解这套分层之后，再去看任何静态分析工具（Joern、WALA、CodeQL）都会发现"基本块—数据流—依赖图"这套骨架如出一辙。想快速上手，不妨先对一个小仓库跑一次analyze --pdg，再用pdg_query查一条flows，亲眼看看赋值如何"流"过整个函数。🚀

【免费下载链接】GitNexusGitNexus: The Zero-Server Code Intelligence Engine - GitNexus is a client-side knowledge graph creator that runs entirely in your browser. Drop in a git repository (Github, Gitlab, Azure, Local) or ZIP file, and get an interactive knowledge graph with a built in Graph RAG Agent. Perfect for code exploration项目地址: https://gitcode.com/GitHub_Trending/gi/GitNexus