PhASAR静态分析框架实战：跨过程数据流分析与污点追踪

1. 静态分析框架选型的思考为什么是 PhASAR第一次接触 PhASAR 是在做一个跨过程数据流分析的需求时。当时团队需要在一个中等规模的 C/C 代码库上追踪污点传播路径试过手写 AST 遍历也试过基于 Clang 的 AST Matcher 做规则匹配但都卡在同一个瓶颈上跨函数、跨编译单元的数据流追踪。手写方案在函数调用链稍微深一点的时候就彻底失控了Clang 的 AST Matcher 又只能做语法层面的模式匹配拿不到真正的数据流信息。PhASAR 解决的正是这个问题。它是一个基于 LLVM 的 C/C 静态分析框架核心能力是跨过程数据流分析。简单说它能帮你在整个程序的调用图上追踪一个值从产生到消亡的完整路径而不是只看单个函数内部。这个能力在漏洞挖掘、代码审计、程序理解等场景里非常关键。PhASAR 适合谁如果你已经写过一些 LLVM Pass对 IR 层面的基本概念比如 Value、Instruction、BasicBlock不陌生那 PhASAR 会让你事半功倍。如果你完全没碰过 LLVM直接上 PhASAR 会比较痛苦建议先花时间理解 LLVM IR 的基本结构。另外PhASAR 的文档和示例代码质量参差不齐很多细节需要读源码才能搞清楚所以它更适合有一定工程经验、愿意啃源码的开发者。这篇文章我会从整体设计思路、核心概念、实操流程、常见问题几个维度展开把我在实际使用中踩过的坑和总结的经验都放进来。代码示例会尽量完整方便你直接抄作业。2. PhASAR 整体架构与核心设计思路2.1 为什么选择 LLVM IR 作为分析基础PhASAR 选择在 LLVM IR 层面做分析而不是在源码层面。这个决策背后有几个关键考量。源码层面的分析需要处理宏展开、模板实例化、头文件包含等复杂问题不同编译器的前端行为还不一致。而 LLVM IR 是编译器前端和后端之间的中间表示已经完成了类型检查、宏展开、模板实例化等预处理工作表示形式统一且规范。在 IR 层面做分析相当于站在了一个标准化的中间层上不用操心各种语言特性的边界情况。另一个重要原因是 LLVM IR 的 SSAStatic Single Assignment形式。每个变量只被赋值一次使用-定义链use-def chain天然清晰。这对数据流分析来说太友好了——你不需要做复杂的 reaching definition 分析直接沿着 use-def 链走就行。PhASAR 的很多分析算法都依赖这个特性来简化实现。还有一个实际的好处LLVM 生态里有大量的工具和库可以直接复用。比如指针分析可以用 LLVM 自带的 AliasAnalysis 接口调用图可以用 LLVM 的 CallGraph 分析结果。PhASAR 在这些基础设施之上构建自己的分析框架省了很多重复造轮子的功夫。2.2 框架的分层结构PhASAR 的架构大致可以分为三层从下往上依次是IR 层直接操作 LLVM IR提供对 Instruction、Function、Module 等基本元素的封装。这一层负责把 LLVM 的原始数据结构转换成 PhASAR 内部更易用的表示形式。分析层包含各种分析算法的实现比如 IFDS/IDE 框架、单调框架Monotone Framework、类型层次分析等。这一层是 PhASAR 的核心也是使用者主要打交道的部分。问题层用户自定义的分析问题。你需要实现特定的接口定义自己的数据流事实fact和传播规则。PhASAR 提供了一套模板化的接口让你可以专注于问题逻辑本身而不用关心分析算法的调度和执行。这种分层设计的好处是关注点分离。分析算法的正确性和效率由框架保证你只需要关心我要分析什么问题和这个问题怎么用数据流语言描述。2.3 IFDS/IDE 框架的核心地位PhASAR 最核心的分析引擎是 IFDSInterprocedural Finite Distributive Subset和 IDEInterprocedural Distributive Environment框架。这两个框架来自 Reps、Horwitz 和 Sagiv 在 1995 年发表的经典论文是跨过程数据流分析的里程碑式工作。IFDS 解决的是有限分布子集问题。用人话说就是当你的数据流事实可以用一个有限集合表示并且传播函数满足分配律时IFDS 可以在多项式时间内给出精确解。典型的应用场景包括污点分析一个变量是否被污染、可达性分析一个指针可能指向哪些对象、活跃变量分析等。IDE 是 IFDS 的扩展它不仅能追踪事实是否存在还能追踪事实对应的值是什么。比如在常量传播分析中你不仅想知道某个变量是否是常量还想知道它的具体值是多少。IDE 通过引入一个额外的值域value domain来实现这一点。这两个框架的精妙之处在于它们把跨过程分析的复杂度从指数级降到了多项式级。传统的跨过程分析需要对每个调用上下文单独分析上下文数量一多就爆炸了。IFDS/IDE 通过图可达性算法和函数摘要summary机制避免了这种爆炸。注意IFDS 的分配律条件很关键。如果你的传播函数不满足分配律IFDS 给出的结果可能不精确。在实际使用中大部分污点分析和可达性分析都满足这个条件但某些涉及别名或路径敏感的分析可能需要额外处理。3. 核心概念与实操要点解析3.1 数据流事实与传播函数在 PhASAR 里做分析你首先要定义两样东西数据流事实Fact和传播函数Flow Function。数据流事实就是你关心的信息单元。比如在污点分析中事实可以是变量 x 被污染在类型分析中事实可以是变量 x 的类型是 T。PhASAR 要求事实类型是可哈希的、可比较的因为它需要在分析过程中做集合运算。传播函数定义了事实如何在程序语句之间传播。对于每条指令你需要告诉 PhASAR给定输入事实集合输出事实集合是什么。传播函数必须满足分配律即f(A ∪ B) f(A) ∪ f(B)。这个条件保证了 IFDS 算法的正确性。我刚开始用的时候经常把传播函数写得过于复杂试图在一个函数里处理所有情况。后来发现更好的做法是按指令类型拆分每条指令对应一个简单的传播规则。这样代码更清晰也更容易调试。3.2 调用图与函数摘要跨过程分析的核心是调用图。PhASAR 会自动从 LLVM IR 构建调用图但构建方式有几种选择直接影响分析的精度和效率。最直接的是基于名称的调用图把所有同名函数的调用都连到同一个节点。这种方式快但精度低遇到函数指针就抓瞎了。PhASAR 默认用的是 LLVM 的调用图分析会考虑函数指针的可能目标精度更高但构建时间更长。函数摘要Function Summary是 IFDS 框架的关键机制。当分析遇到一个函数调用时不需要重新分析被调用函数的函数体而是使用预先计算好的摘要。摘要描述了给定输入事实函数返回什么输出事实。这个机制让跨过程分析的复杂度从指数级降到了多项式级。PhASAR 支持两种摘要计算方式按需计算和预计算。按需计算在第一次遇到调用时计算摘要并缓存适合调用图稀疏的场景预计算在分析开始前把所有函数的摘要都算好适合调用图密集、重复调用多的场景。实测下来对于中等规模的项目10万行左右预计算方式总体更快因为避免了重复计算。3.3 指针分析的集成C/C 的指针是静态分析的最大难点之一。PhASAR 本身不实现指针分析而是依赖 LLVM 的 AliasAnalysis 接口。这意味着你的分析精度很大程度上取决于底层指针分析的精度。LLVM 提供了几种指针分析精度级别从低到高依次是分析级别精度速度适用场景NoAA无别名信息最快不涉及指针的分析BasicAA基础别名分析快简单指针场景TBAA类型别名分析中等有类型信息的场景ScopedNoAliasAA作用域别名分析中等有 noalias 标注的场景GlobalsAA全局变量别名分析慢全局变量多的场景实际使用中我一般先用 BasicAA 跑一遍如果发现漏报太多再升级到更精确的分析。全开最高精度虽然结果最准但分析时间可能翻好几倍需要根据实际需求权衡。实操心得PhASAR 的指针分析配置在Pass的构造函数里通过AliasAnalysis参数传入。如果你不显式指定它默认用 LLVM 的AAResults包装器会自动组合多种分析。这个默认配置在大多数场景下够用但如果你明确知道自己的代码没有复杂指针可以手动降级来提速。4. 从零搭建一个污点分析完整实操流程4.1 环境准备与编译PhASAR 的编译依赖 LLVM 和几个辅助库。我推荐用 LLVM 14 或 15这两个版本 PhASAR 支持得最好。太新的 LLVM 版本可能有 API 变动导致编译失败太老的版本又缺少一些新特性。编译步骤大致如下# 安装依赖以 Ubuntu 为例 sudo apt-get install cmake ninja-build graphviz doxygen # 下载 PhASAR 源码 git clone https://github.com/secure-software-engineering/phasar.git cd phasar # 创建构建目录 mkdir build cd build # 配置 CMake指定 LLVM 路径 cmake -G Ninja \ -DCMAKE_BUILD_TYPERelease \ -DLLVM_DIR/path/to/llvm/lib/cmake/llvm \ -DPHASAR_BUILD_UNITTESTSOFF \ .. # 编译 ninja编译过程大概需要 20 到 40 分钟取决于机器性能。如果遇到编译错误大概率是 LLVM 版本不匹配。可以先检查LLVM_DIR是否指向正确的路径然后确认 LLVM 版本是否在支持范围内。编译完成后你会得到几个可执行文件最重要的是phasar-cli这是命令行入口。还有一个phasar-llvm是旧版的入口新版本已经统一到phasar-cli了。4.2 定义污点分析问题假设我们要分析一个简单的 C 程序追踪用户输入source到敏感操作sink的传播路径。先定义事实类型// 污点事实表示某个值被污染 struct TaintFact { const llvm::Value *value; bool operator(const TaintFact other) const { return value other.value; } }; // 为 TaintFact 提供哈希函数 namespace std { template struct hashTaintFact { size_t operator()(const TaintFact f) const { return hashconst llvm::Value*()(f.value); } }; }然后定义 source 和 sink。Source 通常是scanf、fgets、read等输入函数sink 通常是system、exec、strcpy等危险函数。在 PhASAR 里你可以通过函数名匹配来识别它们// 判断是否是 source 函数 bool isSource(const llvm::Function *func) { static const std::setstd::string sources { scanf, fscanf, gets, fgets, read, recv }; return sources.count(func-getName().str()) 0; } // 判断是否是 sink 函数 bool isSink(const llvm::Function *func) { static const std::setstd::string sinks { system, popen, exec, strcpy, strcat, sprintf }; return sinks.count(func-getName().str()) 0; }4.3 实现传播函数传播函数是分析的核心逻辑。对于污点分析规则可以简化为如果 source 函数的返回值被赋值给某个变量该变量被污染如果被污染的变量参与运算运算结果被污染如果被污染的变量作为参数传给函数被调用函数的对应参数被污染如果被污染的变量被存入内存内存位置被污染如果被污染的变量被加载加载结果被污染在 PhASAR 的 IFDS 框架里你需要实现FlowFunction接口。核心方法是getNormalFlowFunction、getCallFlowFunction、getRetFlowFunction等分别处理函数内传播、调用传播、返回传播。class TaintFlowFunction : public FlowFunctionTaintFact { public: std::setTaintFact getNormalFlowFunction( const llvm::Instruction *curr, const llvm::Instruction *succ) override { std::setTaintFact result; // 如果当前指令是赋值且右操作数被污染则左操作数也被污染 if (auto *store llvm::dyn_castllvm::StoreInst(curr)) { // 处理 store 指令 // ... } // 如果当前指令是二元运算且任一操作数被污染则结果被污染 if (auto *binOp llvm::dyn_castllvm::BinaryOperator(curr)) { // 处理二元运算 // ... } return result; } // 其他 FlowFunction 方法的实现... };这里有个容易踩的坑传播函数必须处理所有可能的指令类型。如果你只处理了StoreInst和BinaryOperator遇到CallInst或LoadInst时事实就会丢失。我的做法是先写一个通用的保守传播规则——如果当前指令有操作数被污染就把结果也标记为污染。然后再针对特定指令类型做精细化处理。4.4 运行分析与解读结果分析问题定义好后通过 PhASAR 的Solver来运行// 创建分析问题 auto problem std::make_uniqueTaintAnalysisProblem(module); // 创建 IFDS 求解器 IFDSSolverTaintFact, TaintFlowFunction solver(*problem); // 运行分析 solver.solve(); // 获取结果 auto results solver.getResults(); for (const auto [inst, facts] : results) { if (isSinkCall(inst) !facts.empty()) { llvm::outs() 发现污点传播到 sink: *inst \n; } }PhASAR 还提供了结果可视化功能可以把分析结果导出成 DOT 格式用 Graphviz 渲染成图。对于理解复杂的传播路径这个功能非常有用。# 导出分析结果为 DOT 格式 phasar-cli -m target.bc --analysistaint --emit-dot --outputresult.dot # 用 Graphviz 渲染 dot -Tpng result.dot -o result.png注意事项PhASAR 的分析结果默认是可能语义即报告的是可能存在的污点传播而不是必然存在的。这意味着会有误报。要减少误报需要提高指针分析精度、增加路径敏感分析或者手动添加 sanitizer 规则比如识别strlen等不会传播污点的函数。5. 常见问题与排查技巧实录5.1 分析结果为空或明显不完整这是最常见的问题。分析跑完了但结果里什么都没有或者只有零星几条。排查思路如下第一步确认 IR 是否正确生成。PhASAR 分析的是 LLVM IR不是源码。如果你的编译命令没有加-emit-llvm或者优化级别太高导致 IR 被过度简化分析结果就会不准确。建议用-O0 -g -emit-llvm生成 IR保留完整的调试信息和原始结构。第二步检查 source 和 sink 的识别逻辑。很多时候问题出在函数名匹配上。C 的函数名会被 manglescanf可能变成_Z6scanfPKcz之类的形式。你需要用llvm::demangle还原函数名或者直接用Function::getName()拿到 mangled 名再做匹配。第三步确认传播函数覆盖了所有指令类型。前面提到过传播函数漏处理指令类型会导致事实丢失。可以在传播函数里加日志打印每条指令的处理情况看看事实是在哪一步丢的。5.2 分析时间过长或内存溢出PhASAR 的分析复杂度对程序规模很敏感。10 万行以下的程序通常几分钟内能跑完但超过 50 万行就可能需要几小时甚至更久。如果遇到性能问题可以从以下几个方面优化降低指针分析精度。指针分析是性能瓶颈的主要来源。如果不需要精确的别名信息可以降级到 BasicAA 甚至 NoAA。限制分析范围。PhASAR 支持指定分析的入口函数只分析从入口可达的函数。如果你的目标只是某个模块不需要分析整个程序这个选项能大幅减少分析时间。使用预计算摘要。前面提到过预计算摘要适合调用图密集的场景。虽然预计算本身需要时间但避免了重复计算总体可能更快。增加内存限制。IFDS 算法需要存储大量的中间结果内存消耗可能很大。如果机器内存不足可以调整 JVM 堆大小如果用的是 Java 版或者优化数据结构减少内存占用。5.3 误报太多怎么处理污点分析的误报主要来自几个方面指针别名导致的过度近似、路径不敏感导致的不可行路径、缺少 sanitizer 识别。减少误报的手段包括提高指针分析精度用更精确的别名分析减少指针目标的过度近似添加 sanitizer 规则识别那些会净化污点的函数比如strlen、atoi等不会传播污点的函数路径敏感分析PhASAR 支持一定程度的路径敏感分析可以过滤掉不可行路径手动审查结果对于关键路径人工审查仍然是必要的我的一般策略是先用低精度分析快速跑一遍拿到大致结果然后对可疑路径用高精度分析重新验证。这样在效率和精度之间取得平衡。5.4 常见问题速查表问题现象可能原因排查方法解决方案分析结果为空IR 生成不正确检查编译命令用-O0 -g -emit-llvm重新生成结果不完整传播函数漏处理指令加日志打印处理过程补全所有指令类型的处理分析时间过长指针分析精度过高查看分析配置降级指针分析精度内存溢出中间结果过多监控内存使用限制分析范围或优化数据结构误报太多指针别名过度近似检查别名分析结果提高精度或添加 sanitizer函数名匹配失败C 名称修饰打印实际函数名用 demangle 还原名称6. 进阶技巧与扩展方向6.1 自定义分析问题的模板化写法PhASAR 提供了模板化的分析问题接口让你可以复用通用的分析逻辑。比如你可以写一个通用的源到汇分析模板只需要指定 source 和 sink 的识别函数就能生成不同的分析问题。templatetypename SourceMatcher, typename SinkMatcher class GenericTaintAnalysis : public IFDSProblemTaintFact { SourceMatcher sourceMatcher; SinkMatcher sinkMatcher; public: GenericTaintAnalysis(llvm::Module *m, SourceMatcher sm, SinkMatcher sk) : IFDSProblemTaintFact(m), sourceMatcher(sm), sinkMatcher(sk) {} // 通用实现... };这种写法在需要分析多种不同类型的污点传播时特别有用避免了重复代码。6.2 与其他工具的集成PhASAR 的分析结果可以导出成多种格式方便与其他工具集成。除了前面提到的 DOT 格式还支持 JSON、CSV 等格式。你可以把结果导入到数据库里做进一步分析或者集成到 CI/CD 流程里做自动化检查。我自己的做法是把 PhASAR 分析集成到代码审查流程里每次提交代码时自动跑一遍污点分析如果发现新的污点传播路径就自动评论到代码审查工具里。这样能在代码合并前就发现问题比事后审计效率高得多。6.3 分析结果的验证静态分析的结果需要验证。PhASAR 本身不提供验证功能但你可以结合动态测试来验证。比如对于分析出的污点传播路径可以生成对应的测试用例用动态工具如 AddressSanitizer来确认是否真的存在漏洞。这种静态分析定位 动态测试验证的组合拳在实际漏洞挖掘中非常有效。静态分析帮你缩小范围动态测试帮你确认问题两者互补。实操心得PhASAR 的分析结果里包含了完整的传播路径信息你可以沿着路径逐条指令检查确认每一步传播是否合理。如果发现某一步传播不合理比如一个不可能被执行的指令那大概率是误报。这种人工审查虽然费时但对于关键路径是值得的。7. 我在实际使用中的几点体会PhASAR 的学习曲线确实比较陡。我刚开始用的时候光是搞清楚 IFDS 框架的接口就花了一周时间。但一旦理解了它的设计思路后面做各种分析就很快了。它的核心价值在于把跨过程分析的复杂性封装了起来让你可以专注于问题逻辑本身。一个让我印象深刻的点是 PhASAR 对 LLVM 生态的深度集成。它没有重新发明轮子而是充分利用了 LLVM 已有的基础设施。这种设计哲学值得学习——站在巨人的肩膀上而不是从零开始。另外PhASAR 的社区虽然不大但活跃度还可以。遇到问题在 GitHub 上提 issue通常几天内会有回复。源码里的注释和示例代码虽然不完美但仔细读还是能搞清楚大部分细节。最后分享一个小技巧如果你要分析的项目比较大建议先用-O0生成 IR然后用llvm-extract提取你关心的函数只分析这部分。这样能大幅减少分析时间而且结果更聚焦。等确认分析逻辑没问题后再对整个项目跑完整分析。