如何编写使Angr符号执行因路径爆炸失败的C函数

原代码无效的原因 #

你之前写的Collatz代码没达到预期效果，问题出在两点：

1. collatz_conjecture函数里的while循环只执行一次就return了，根本没形成循环分支，Angr处理起来毫无压力；
2. 用了rand()和srand(time(NULL))，Angr对这类依赖外部随机的函数，要么会简化成具体值，要么不会生成大量符号分支，自然不会触发路径爆炸。

可行的实现方案 #

方案1：嵌套符号条件分支（静态分支爆炸） #

直接用符号参数a生成多层独立的条件判断，分支数会以2^n的指数级增长，当n足够大时，Angr的路径处理能力会直接被撑爆：

int target(int a) {
    // 写15-20层判断，总分支数会到32768到1048576级
    if (a & 1) {} else {}
    if (a & 2) {} else {}
    if (a & 4) {} else {}
    if (a & 8) {} else {}
    if (a & 16) {} else {}
    if (a & 32) {} else {}
    if (a & 64) {} else {}
    if (a & 128) {} else {}
    if (a & 256) {} else {}
    if (a & 512) {} else {}
    if (a & 1024) {} else {}
    if (a & 2048) {} else {}
    if (a & 4096) {} else {}
    if (a & 8192) {} else {}
    if (a & 16384) {} else {}
    
    printf("%d\n", a);
    return 0;
}

方案2：循环生成动态符号分支 #

通过循环让符号变量每次迭代都产生新分支，循环次数越多，路径数指数级增长：

int target(int a) {
    int x = a;
    // 循环20次即可产生100万+分支，直接耗尽Angr的资源
    for (int i = 0; i < 20; i++) {
        if (x & (1 << i)) {
            x += 1;
        } else {
            x -= 1;
        }
    }
    printf("%d\n", a);
    return x;
}

方案3：修正你的Collatz代码 #

如果坚持用Collatz猜想，需要修改两处：去掉循环内的return，并且用符号参数作为初始值（而非随机数），让每次循环的奇偶判断都成为符号分支：

unsigned long long collatz_conjecture(unsigned long long num) {
    while (num != 1) {
        if (num % 2 == 0) {
            num /= 2;
        } else {
            num = num * 3 + 1;
        }
        // 移除这里的return，让循环真正执行
    }
    return num;
}

int target(int a) {
    // 把符号参数a作为Collatz的初始输入，而非随机数
    unsigned long long ret = collatz_conjecture((unsigned long long)a);
    if (ret != 1) {
        return 0;
    }
    printf("%d\n", a);
    return 1;
}

这种情况下，Angr会尝试跟踪Collatz序列的所有可能路径分支，而序列的长度不确定，最终会因路径数量爆炸导致超时失败。

内容的提问来源于stack exchange，提问作者buxxxi