二进制符号执行与KLEE-Native
KLEE作为符号执行工具，通过在自定义运行时环境中模拟LLVM位码来生成高覆盖率测试用例。然而与简单模糊测试工具不同，它并非漏洞自动化发现的标配工具。尽管学术界持续改进，安全研究人员仍难以驾驭KLEE。我们的工作正致力于弥合这一鸿沟！
本次项目聚焦KLEE-Native——通过对机器代码进行LLVM位码提升（lifting），实现在二进制程序快照上运行的KLEE分支版本。
优势与挑战并存
KLEE的最大优势恰是其主要弱点：它操作LLVM位码。这种设计最明显的优势是能运行在Clang编译器工具链支持的所有语言（C/C++/Swift/Rust等）上。但更微妙的好处常被忽视：由于运行时支持代码可用C/C++实现并编译为位码，这些代码能与被测系统（SUT）共同接受符号路径探索。
这种设计带来惊人灵活性。例如KLEE运行时可将I/O相关系统调用（read/write等）实现为普通C函数，这些函数会像SUT代码一样参与符号执行，共同提升代码覆盖率。这使得KLEE能"透视"操作系统内核，探索可能导致边界条件的复杂路径。
但位码操作的劣势同样明显：通常KLEE需要程序源码，而由于构建系统、配置和依赖项的复杂性，获取位码极其困难。即使获得位码，研究人员仍需手动注入KLEE API调用、链接运行时库、对外部库依赖进行建模。面对大型代码库时这些任务令人望而生畏。虽然McSema可在无源码时作为黑盒方案，但二进制控制流图恢复的局限性和准确性问题常导致结果不可用。
KLEE-Native的二进制快照机制
我们首先聚焦于获取任意程序的位码，采用从机器码提升到位码（而非源码编译）的技术路径。基于GRR风格的动态快照机制，KLEE-Native能深入程序执行流启动分析，这是主线KLEE无法实现的。
快照技术实现
默认情况下，KLEE-Native在首条指令执行前捕获程序内存和寄存器状态。这意味着需要模拟main函数前的初始化代码（如加载共享库），这显然不够理想。为避免模拟这类确定性流程，我们通过ptrace在用户指定虚拟地址注入INT3断点指令。
在此模式下，目标进程原生执行直至触发断点。此时快照器接管控制权，将进程内存和兼容Remill的寄存器结构转储到工作区目录，后续可根据该目录重建原始进程的内存映射：
|
|
对于启用地址空间随机化（ASLR）的二进制文件，--dynamic参数指示快照器将断点地址视为主二进制文件内的偏移量。我们通过解析/proc/[pid]/maps文件获取加载基址，经简单运算即可定位断点：
|
|
技术细节：CPUID指令检测会引发有趣副作用。Libc通过CPUID检测CPU特性（如决定是否使用SSE4优化的memset）。如果在CPUID原生执行后获取快照，必须指定AVX架构选项，否则这类指令可能无法正确提升。
机器码到位码的动态提升
获取快照后，可通过以下命令要求KLEE-Native动态提升并执行程序：
|
|
下图展示klee-exec的控制流：
[控制流程图描述…]
高层来看，KLEE-Native即时解码并提升轨迹（trace）——即包含机器码逻辑片段的LLVM函数对象。这些轨迹包含模拟机器码的LLVM指令，以及对Remill intrinsics和其他提升轨迹的调用。
intrinsic调用可能由KLEE的"特殊函数处理"能力接管，使得运行时位码能直接访问KLEE执行器和状态。例如Remill的内存读写intrinsics就通过该机制与快照地址空间交互。
当模拟malloc等函数时，轨迹从libc实现创建，执行可顺畅继续。一切看似美好……
直到brk和mmap等系统调用出现，我们必须处理这些指令。
运行时即内核
KLEE-Native将所有机器码（包括原始系统调用指令）提升到位码。通过Remill，系统调用指令转换为对__remill_async_hyper_call intrinsic的调用。该函数语义虽未由Remill定义，但其设计初衷是实现执行底层操作所需的硬件/OS特定功能。
在KLEE-Native中，我们实现该intrinsic函数，将执行流从提升的位码交回运行时位码，其中每个Linux系统调用都有对应的封装实现。这些封装器通过ABI类型定位系统调用号和参数，并存储返回值。以下是运行时实现的POSIX open系统调用封装示例：
[系统调用封装代码片段…]
该封装器执行实际OS内核会做的错误检查（如确保文件路径名可从快照地址空间读取、检查路径长度等）。此时我们发挥KLEE的优势：如果被检测数据包含符号值，所有这些错误检查路径都会参与符号探索。
至此，我们已完成机器码到位码的动态提升，并实现系统调用模拟。这意味着我们可以运行提升后的机器码，使其像源码编译的位码那样与KLEE运行时交互。
malloc调用继续执行并分配内存块，但执行速度开始显著下降……
通过准虚拟化恢复源码级抽象
操作机器码意味着必须处理所有细节。这在处理看似简单的libc函数时尤为棘手，例如strcpy/strcmp/memset等函数的汇编实现包含SIMD指令。模拟这些复杂指令的时间消耗远超模拟简化版本。更不用说当这些函数处理符号数据时可能引发的状态爆炸问题。
我们通过准虚拟化libc解决该问题。即在快照程序中引入基于LD_PRELOAD的拦截库，重定义常见libc函数。在该库中，准虚拟化函数是原始POSIX函数的薄封装，执行它们会触发快照前的原始函数调用。
这些函数的核心价值是提供统一入口点供快照阶段定位和修补。例如下例中，快照器会将JMP指令替换为NOP，使得malloc在被KLEE-Native模拟时实际触发INT 0x81中断：
[LD_PRELOAD拦截示例…]
模拟过程中触发中断时，我们检查中断向量号并挂钩到对应的准虚拟化libc运行时函数。当准虚拟化版本无法处理所有情况时，我们支持回退机制——通过递增程序计数器并跳过RETN指令，使原始libc函数得以执行。
当前拦截库支持的libc函数及其中断向量号如下：
[支持的libc函数列表…]
至此，malloc调用已触发中断并挂钩到KLEE中的准虚拟化版本。我们为何需要这种机制？
通过libc拦截器建模堆内存
在模拟malloc过程中调用mmap/brk会进行内存分配布局。虽然这精确反映了机器码指令，但对漏洞发现并不高效。问题在于：mmap的粒度过于粗糙。
虽然可以观测所有内存访问，但难以确定分配块的起止边界，导致边界检查（如检测溢出/下溢）异常困难。此外，当内存分配呈现为不透明块时，对重复释放（double-free）和释放后使用（use-after-free）等漏洞的检测也无从谈起。
因此我们拦截malloc等内存分配例程，构建透明内存模型来划分内存区域。该方案使KLEE-Native能轻松分类和报告堆漏洞。独特之处在于我们发明了全新的地址编码格式：
[自定义地址编码结构体…]
通过准虚拟化malloc分配的区块并不真实存在于传统地址空间，而是存在于分配列表（allocation list）中。这种结构使单个分配块易于访问、追踪和操作，极大简化了边界检查、重复释放检测和溢出/下溢检测。更重要的是，分配列表支持就地扩展分配块来修复堆缓冲区溢出等问题。
改进分支策略：主动具体化
我们的符号执行方案与KLEE经典的分支调度模型不同。KLEE作为"动态符号执行器"，而KLEE-Native更接近SAGE风格的静态符号执行器。
KLEE-Native的分支策略采用主动具体化（eager concretization）和深度优先探索，且不牺牲完备性——通过状态延续（state continuation）机制，我们随时可以回退到执行历史点请求下一次具体化。这与KLEE或Manticore等工具主动生成大量可行状态再通过调度器选择的策略截然不同。
状态延续类似Python生成器，在分支发生前打包执行状态副本和生成后续具体化所需的元数据。执行器可向延续请求下一个可行状态，每个请求返回的新状态都已进行某些条件的具体化（故称"主动具体化"）。
当前我们将状态延续存储在栈中，这使得KLEE-Native优先"深度探索"而非"广度探索"。当状态执行完成（如退出或遇到不可恢复错误），我们从栈顶延续获取下一个状态，直到延续耗尽才弹出并转向下一个延续。未来我们将探索更多策略。
[分支策略示意图…]
该方案的动机源于处理符号内存地址的需求。我们发现KLEE在符号内存地址处理上无法穷尽所有路径——它会具体化地址，但不够完备。这其实符合预期，因为符号内存本就是难题。
具体内存的实现很简单（本质是地址到字节值的映射），但当地址可能对应多个值时该如何处理？我们决定最佳策略是建立通用机制立即具体化地址，同时保留其他可能性，将实质性策略交给策略处理器实现（如采样、最小/最大值等策略）。
实战应用：漏洞自动化分类
由于完全控制模拟地址空间和内存分配，KLEE-Native能轻松分类各类内存破坏漏洞，特别适合漏洞分类场景。我们的主动具体化策略确保始终聚焦目标代码路径。
以Google Fuzzer Test Suite中的CVE-2016-5180（ChromeOS利用链中使用的c-ares堆缓冲区单字节溢出漏洞）为例：
首先在main函数设置动态断点获取快照：
|
|
然后执行分析：
|
|
此时KLEE-Native成功检测到单字节堆溢出。相比AddressSanitizer或Valgrind，KLEE-Native的特殊性在于策略处理器——例如对内存访问违规的策略之一是将溢出字节替换为符号值。随着执行继续，我们可通过分析最终符号溢出字节的范围来评估漏洞严重性，帮助研究人员区分有限溢出和可能形成"任意写"原语的危险状态。
在KLEE-Native中，未定义行为可成为符号执行的新源头，使得在缺乏威胁模型和逆向工程的情况下进行漏洞分类成为可能。
未来展望
本项目产出的KLEE-Native能够：
- 具体/符号化执行二进制文件
- 建模堆内存
- 复现CVE漏洞
- 精确分类堆漏洞
该项目为探索符号执行新应用场景奠定基础，我们还将研究不同提升策略对执行速度的影响。正如所有符号执行文章所言：KLEE既是问题，也是解决方案。