QSYM 内存模型深度剖析：符号数据如何从输入流转到分支条件

【免费下载链接】qsymQSYM: A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing项目地址: https://gitcode.com/gh_mirrors/qs/qsym

QSYM 是一款为混合模糊测试（Hybrid Fuzzing）量身定制的实用化符号执行引擎（Concolic Execution Engine），它的核心秘密就藏在内存模型里。本文从零开始剖析 QSYM 内存模型，带你完整看懂一条"符号数据"从输入文件流入内存、随指令传播、最终生成分支条件的全过程，适合想理解符号执行引擎工作原理的新手与安全研究者。

先认识 QSYM：混合模糊测试背后的符号引擎

传统模糊测试（Fuzzing）靠随机变异输入来碰运气，而符号执行能把"分支条件"翻译成数学约束，直接算出能走到新路径的输入。QSYM 的定位是实用化：它不像经典符号执行那样追求 100% 的符号化，而是刻意把大量"不划算"的操作直接具体化，只对值得求解的分支投入算力，从而在真实程序上跑出远超传统方案的速度。

QSYM 的整体链路可以概括为四步：

1. 输入符号化——通过系统调用挂钩，把输入字节变成符号变量；
2. 指令级传播——基于 Intel PIN 动态插桩，让符号随机器指令"流动"；
3. 分支约束生成——在条件跳转处构造表达式并交给求解器；
4. 反路径求解——否定当前路径条件，生成能探索新代码的输入。

接下来我们沿着这四步，逐一拆解 QSYM 内存模型。

QSYM 内存模型：一张按页组织的"符号表"

QSYM 内存模型的核心类Memory定义在 memory.h 中，实现位于 memory.cpp。它的设计非常巧妙：为进程的每一页内存维护一张表达式指针表。

std::unordered_map<ADDRINT, ExprRef*> page_table_; ExprRef* stack_page_; // 栈页 ExprRef* unmapped_page_; // 未映射页（统一哨兵） ExprRef* zero_page_; // 零页（vdso 等只读区） ExprRef* brk_page_; // 堆（brk）区域

• 地址按kPageShift = 12右移得到页索引，页内偏移用addr & kPageMask得到；
• 每个地址对应一个ExprRef，也就是一个"表达式指针"——NULL 表示该内存是具体值（Concrete），非 NULL 表示它承载着符号表达式；
• 未映射、栈、堆、vdso 等区域各有专门的页对象，isUnmappedAddress通过比对页指针即可 O(1) 判断地址是否可读。

这套设计把"符号内存"和"真实内存"松耦合：真实内存由进程自己管理，QSYM 只维护一张平行的符号影子表。程序怎么读写内存，影子表就怎么记录符号，互不干扰。

第一步：输入数据如何变成符号变量

QSYM 通过 libdft 拦截read、pread64、readlink等系统调用（见 syscall_desc.cpp 中__NR_read对应的postReadHook）。当一个输入文件被读入缓冲区后，QSYM 会在该缓冲区上调用makeExpr(addr, size)：

inline void makeExpr(ADDRINT addr) { ExprRef e = g_expr_builder->createRead(off_++); // 取一个递增的输入偏移 setExprToMem(addr, e); }

这里出现了 QSYM 内存模型的第一个关键角色——Read表达式。ReadExpr（定义在 expr.h）就是"输入文件的第 i 个字节"的化身，它内部只保存一个index_，对应输入文件偏移，并且把isConcrete_置为 false，表示这是一个真正的符号变量。每个输入字节对应一个唯一的 Read 表达式，这一一映射正是"符号数据"的源头。

第二步：符号如何沿指令传播

有了符号源头，接下来就是 QSYM 的核心工作——指令级符号传播。QSYM 用 XED 解码每条指令（analysis.cpp 中的analyzeInstruction），把机器指令翻译成语义操作，例如：

• ADD→Add表达式，同时更新 EFLAGS 标志位；
• CMP→Sub表达式，用于后续条件跳转；
• MOV→ 直接搬运寄存器/内存的表达式。

传播过程由两个模块协同完成：插桩回调（instrument.cpp）负责在每条指令前/后提取表达式并计算结果，表达式构建器（expr_builder.cpp）负责构造新的表达式节点。

多字节读写时，内存模型会逐字节取出表达式再拼接。getExprFromMem(addr, size)的实现逻辑是：对每个字节分别取表达式（NULL 则用真实字节值构造常量），再通过createConcat按大端序拼接成一个完整的位向量表达式。反之，setExprToMem(addr, size, e)会把一个宽表达式用createExtract切分成逐字节的子表达式写回影子表。

表达式节点本身构成一棵有向无环图（DAG），例如x + 1 < 8会表示成：

Ult( Add( Read(3), Constant(1) ), Constant(8) )

每个节点记录bits()（位宽）、子节点、哈希值和依赖集。所有非叶子表达式都维护uses_反向引用，一旦某个Read表达式被具体化（concretize()），依赖它的上层表达式会沿 DAG 自底向上"级联具体化"，这是 QSYM 高效化简的关键机制之一。

第三步：分支条件如何从内存"长"出来

当程序执行到条件跳转（Jcc）指令时，QSYM 的插桩回调instrumentJcc（instrument.cpp）会被触发。它读取 EFLAGS 寄存器中对应的标志位表达式（CF/ZF/SF/OF 等），依据跳转类型组合出完整的分支条件表达式，然后调用：

g_solver->addJcc(e, taken, pc);

solver.cpp中的addJcc是决策核心：

1. 若表达式已具体化，直接忽略（不浪费求解器）；
2. 通过isInterestingJcc判断该分支是否"值得求解"——QSYM 会结合 AFL 的覆盖率位图（bitmap）来判断这条路径是否探索过，只有有趣的分支才进入求解流程；
3. 对有趣分支调用negatePath，把当前路径约束取反，交给 Z3 求解新输入；
4. 把当前分支约束加入路径条件栈（addConstraint），供后续分支继续累积。

negatePath会借助依赖森林（dependency.cpp中的DependencyForest）只重放与该分支相关的约束，而不是全部路径约束，这是 QSYM 相对早期符号执行工具的重大性能优化——把"重放整条路径"降级为"重放相关子路径"。

第四步：求解与"静默具体化"策略

求解阶段由 Z3 的QF_BV（无量词位向量）求解器完成，超时 10 秒（见 solver.cpp 的kSolverTimeout）。求解成功就把新输入写入输出目录，供下一次模糊测试迭代使用。

但 QSYM 内存模型真正的精髓是实用主义：它并不强行让所有数据都保持符号化。遇到求解代价过高的运算（如复杂除法、非平凡非线性运算）时，concretizeMem/concretizeReg会执行"静默具体化"——把符号表达式替换成当前真实值，并把Equal(expr, value)作为约束记录下来（g_solver->addValue），从而既不丢精度，又大幅降低求解压力。

此外还有三层轻量优化支撑性能：

• 范围约束（Range Set）：expr.h中每个表达式维护有符号/无符号两个区间集合，简单比较可以直接用区间判定，绕开 Z3；
• 表达式缓存（Cache）：expr_cache.cpp用哈希去重相同表达式，避免 DAG 无限膨胀；
• 交换律归一化：构建器责任链（Commutative → Symbolic → Common → ConstantFolding → Cache → Base，见 expr_builder.cpp）保证x+1与1+x归并为同一表达式。

一张图看懂符号数据流

把上面四步串起来，QSYM 内存模型中的数据流就是一条清晰的流水线：

小结：QSYM 内存模型的三条设计哲学

回顾整条链路，QSYM 内存模型的设计哲学可以浓缩为三点：

1. 影子内存，按页并行：用页表结构给真实内存"照镜子"，符号与具体值互不干扰；
2. 懒符号化 + 主动具体化：只在系统调用处生成符号，遇到昂贵运算果断具体化并保留约束；
3. 求解最小化：依赖森林、区间传播、表达式缓存三管齐下，把 Z3 调用次数压到最低。

对于想深入学习符号执行或混合模糊测试的读者，建议顺着 memory.h → expr.h → instrument.cpp → solver.cpp 的顺序精读源码，你会发现 QSYM 内存模型的每一处设计，都在回答同一个问题：如何用最小的求解代价，让符号数据走完从输入到分支的最后一公里。

【免费下载链接】qsymQSYM: A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing项目地址: https://gitcode.com/gh_mirrors/qs/qsym