一、路径爆炸初探
什么是路径爆炸？
路径爆炸，说白了就是程序的状态空间太大了，大到你的电脑根本算不过来。
我刚开始接触符号执行时，对这个概念的理解很模糊。直到有一次，我拿一个只有几十行代码的C程序跑angr，结果等了半小时还没出结果。我当时就懵了——这么小的程序，怎么会跑不动？
后来我才明白，这就是路径爆炸在作祟。
你想想看，angr在做符号执行时，每遇到一个条件分支（比如if-else），就会把当前状态分裂成两个。如果程序里有n个分支，理论上就会有2ⁿ条路径。当n=10时，是1024条；当n=20时，是100万条；当n=30时，是10亿条。指数增长就是这么恐怖。
核心定义：路径爆炸是指符号执行过程中，由于程序分支数量的指数级增长，导致状态空间过大，无法在合理时间内完成分析的现象。
为什么angr会遇到路径爆炸？
angr本质上是一个符号执行引擎。它的工作方式是：把程序的每条路径都当作一个独立的状态来维护。每个状态包含寄存器值、内存内容、路径约束等信息。
问题出在哪里呢？
- 分支无处不在——循环、条件判断、函数调用，甚至异常处理都会产生分支
- 状态膨胀——每个新状态都要复制父状态的全部信息，内存消耗巨大
- 路径合并困难——不同路径到达同一代码位置时，angr默认不会自动合并
我记得有一次分析一个网络协议解析器，代码里有个switch语句，case分支有40多个。angr直接给我创建了40多个状态，每个状态还要继续往下走...结果你猜怎么着？内存直接爆了。
避坑指南：我曾经天真地以为，只要给虚拟机分配足够多的内存就能解决问题。结果128GB内存照样被吃光。路径爆炸不是硬件能硬扛的，必须从算法层面解决。
一个简单的路径爆炸示例
来看一个最典型的例子。这个程序虽然简单，但足以让你直观感受到路径爆炸的威力。
// path_explosion.c
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
int x = 0;
int i;
for (i = 0; i < 10; i++) {
if (rand() % 2) {
x += 1;
} else {
x -= 1;
}
}
if (x == 0) {
printf("x is zero\n");
} else {
printf("x is not zero\n");
}
return 0;
}这个程序循环10次，每次根据随机数决定x加1还是减1。最后判断x是否为0。
如果用angr来分析这个程序，会发生什么？
angr会把rand() % 2当作符号值来处理。每次循环都会产生两个分支：一个走加1路径，一个走减1路径。循环10次，就是2¹⁰ = 1024条路径。
嗯，1024条路径看起来还好对吧？但注意，这只是10次循环。如果循环次数增加到20次，就是100万条路径。30次，10亿条。40次，1万亿条。
我实际测试过，用angr分析这个程序（循环10次），在我的笔记本上跑了大概3分钟才出结果。如果循环20次，直接跑了一小时还没完，我只好强制终止了。
小技巧：如果你想快速验证路径爆炸的效果，可以用angr的exploration_technique中的LoopSeer来观察循环展开的过程。它能告诉你angr到底创建了多少个状态。
路径爆炸的直观展示
下面这张图展示了路径爆炸的核心逻辑。你可以看到，随着分支数量的增加，路径数量是如何呈指数级增长的。
从这张图可以清楚看到：当分支数量小于10时，路径数量还在可接受范围内。一旦超过15，路径数量就开始疯狂增长。到了20个分支，就是百万级别了。
在实际的二进制分析中，一个稍微复杂点的程序，分支数量轻松上百。这就是为什么路径爆炸是符号执行领域最头疼的问题之一。
路径爆炸的常见场景
根据我的经验，以下场景最容易触发路径爆炸：
| 场景 | 原因 | 典型例子 |
|---|---|---|
| 循环展开 | 每次循环迭代产生分支 | 字符串处理、数据校验 |
| switch语句 | 大量case分支 | 协议解析、命令分发 |
| 递归调用 | 每层递归产生新状态 | 树遍历、深度优先搜索 |
| 符号化输入 | 输入长度不确定导致分支爆炸 | 网络数据包解析 |
关键认知：路径爆炸不是angr的bug，而是符号执行这个技术路线固有的挑战。理解这一点很重要——你不能指望换个工具就能解决，而是要学会如何与路径爆炸共存、对抗。
好了，这一章我们初步认识了路径爆炸。说白了就是：程序分支太多，状态空间太大，电脑算不过来。下一章我会聊聊，面对路径爆炸，我们有哪些实用的应对策略。