基于雪崩猜想的混淆构造

符号执行

定义：一种程序分析技术，采用抽象的符号代替精确值作为程序输入变量，通过约束求解器得出每个路径抽象的输出结果。（解方程）

1. 静态符号执行：不执行程序，将所有输入符号化。
2. 动态（混合）符号执行：尽可能地执行程序，尽可能少地引入符号变量。

分析流程大致如下：

极简示例

将下列C++源代码编译，并用符号执行框架angr进行分析。

#include<iostream>
using namespace std;
int main()
{
    int choice;
    cin >> choice;
    if(choice >= 0) {
        cout << "right path\n";
    } else {
        cout << "wrong path\n";
    }
    return 0;
}

找到right path的约束条件为：

In [2]: simgr.explore(find=0x401208)
Out[2]: <SimulationManager with 1 active, 1 found>

In [3]: simgr.found[0].solver.constraints
Out[3]: [<Bool (LShR((condition_56_32), 0x1f)[0:0] & 1) == 0>]

LShR操作表示逻辑右移，化简该条件可知约束为choice >= 0

符号执行框架组成

符号执行框架有很多，常用的有angr、klee、triton这三个。它们大都由以下几部分组成：

1. 文件加载器
2. 中间语言转换接口
3. 约束求解器（比如z3）
4. 模拟执行引擎（动态分析需要）

angr框架（v9.2.38）

angr是一个支持多架构的二进制文件动态符号执行分析工具

angr中常用的约束收集策略如下：

• BFS：默认的搜索方式，一层一层进行搜索。
• DFS：往深处走，其他的分支路径都推到后面再说。
• LengthLimiter：限制最深路径的深度。
• LoopSeer：将循环次数过多的情况延后处理。
• MemoryWatcher：监视每一步的内存分配释放情况。
• Veritesting：CMU论文提到的一种缓解路径爆炸方法的实现。

符号执行的缺陷

1. 路径爆炸：可能出现的程序执行路径过多，造成框架内存溢出，分析被迫停止。
2. 复杂约束求解：SMT求解器对非线性约束的求解速度较慢。
3. 符号内存建模：对类似array[symbolic variable]的寻址访问，会出现大量的可能执行路径，严重减缓框架的分析速度。

for-loop混淆构造路径爆炸

// 混淆前
if(sec == 0x123456)
    go()

// 混淆后
int ch1 = sec & 0xFF;
int ch2 = (sec & 0xFF00) >> 8;
int ch3 = (sec & 0xFF0000) >> 16;
char c1, c2, c3;
for (int i = 0; i < ch1; i++) c1++;
for (int i = 0; i < ch2; i++) c2++; 
for (int i = 0; i < ch3; i++) c3++; 
if (c1 == 0x12 && c2 == 0x34 && c3 == 0x56)  go();
// 总计有256^3条路径，构造路径爆炸问题

基于雪崩猜想构造路径爆炸

雪崩猜想

雪崩猜想又叫3n+1猜想、角谷静夫猜想等，猜想具体内容如下： $$ f(x)= \begin{cases} \frac{x}{2}&& \text{x为偶数} \newline 3x+1&& \text{x为奇数} \end{cases} $$

在x为正整数的情况下，经过不断地自迭代后，最终一定会进入4->2->1序列。

举例： 37->112->56->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1

基于雪崩猜想构造混淆的代码示例：

int a;
uint64_t b = (uint64_t)&a + rand();
// 使得符号执行引擎符号化b
for (int i = 0; i < 1000; i++)
{
    if (b & 1)
        b = 3 * b + 1;
    else
        b /= 2;
}
// 类似的还有3x+3猜想、3x+371猜想等
if (b <= 4)
    cout << "secret\n";
else
    cout << "fake path\n";

不动点问题构造路径爆炸

雪崩猜想构造路径爆炸的核心：多次迭代、分支判断和固定解。

数值分析中的不动点拥有类似的迭代结构，举例： $$f(x) = 1 + \frac{1}{x}$$

$$ \forall{x} \in R-{-0.618}, f(…f(f(x))) \approx 1.618 $$

不动点迭代的条件： $$|f’(x_0)|<1,x_0为不动点$$

举例:

$$f(x)= \begin{cases} \frac{3}{x-2}&& \text{某些条件} \newline \frac{4}{x-3}&& \text{某些条件取反} \end{cases}$$

最终可能会迭代到不动点-1

代码实验

# 3和4分别是第一个函数和第二个函数的另一个不动点
x = int(input("输入除3，4外的任意整数:"))
for i in range(100):
    if(x > 0):
        x = 3/(x-2)
    else:
        x = 4/(x-3)
    print(x,end=' ')
    if(i % 4 == 0):
        # 换行
        print()
 

代码结果如下：

存在的问题

1. 分支条件的选择：需要选择满足性质的函数使得在特定分支条件下仍能收敛到不定点。
2. 运算效率：与雪崩猜想猜想相比，不动点定理在实数域上进行运算，运算效率较低。
3. 浮点数精度判断问题：计算机计算浮点数存在误差。

参考文献

1. https://api.angr.io/
2. kcon2022 击败SOTA反混淆方法
3. Linear obfuscation to combat symbolic execution
4. Code obfuscation against symbolic execution attacks
5. 数值分析原理 吴勃英