二进制符号执行与KLEE-Native
KLEE的优势与局限
KLEE是一款符号执行工具，通过在自定义运行时环境中模拟LLVM位码，智能生成高覆盖率的测试用例。然而，与简单的模糊测试工具不同，它并非自动化漏洞发现的首选工具。尽管学术界持续改进，KLEE对漏洞猎手而言仍难以采用。我们的工作旨在弥合这一差距！
KLEE的最大优势也是其最大弱点：它操作LLVM位码。操作位码的最明显优势是KLEE可以运行在Clang编译器工具链能编译的任何目标上：C、C++、Swift、Rust等。然而，KLEE方法的一个更微妙好处常被忽视：操作位码意味着“支持代码”或“运行时”可以用C或C++实现，编译为位码，链接到被测系统（SUT），然后与SUT本身一样接受符号路径探索。
这提供了灵活性和强大功能。例如，KLEE运行时可以将I/O相关系统调用（read、write等）实现为普通的C函数。这些函数像SUT一样接受符号探索，并有助于代码覆盖。这使得KLEE能够“窥视”OS内核，探索可能导致棘手边缘情况的路径。
现在来看操作位码的缺点。通常，KLEE用于有可用源码的程序，但由于构建系统、配置和依赖关系带来的困难，从源码获取位码并不容易。即使位码可用，漏洞研究人员可能必须手动将KLEE API调用注入源码，链接KLEE运行时，并可能存根或手动建模外部库依赖。处理大型代码库和复杂构建系统时，这些任务变得令人生畏。当源码不可用时，McSema是一个黑盒选项，但二进制控制流图恢复的局限性和偶尔的不准确性可能无法产生可接受的结果。
KLEE-Native运行于二进制程序快照
首先，我们专注于为任何程序获取位码，我们采取的方法是操作从机器码提升的位码，而不是编译的源码。使用基于快照的动态方法（如GRR），我们可以深入程序执行启动KLEE-Native，这在主线的KLEE中是不可能的。
快照
默认情况下，KLEE-Native快照器在第一指令执行前捕获程序的内存和寄存器状态。这意味着KLEE-Native需要模拟主函数前的代码（例如，加载共享库），这并不理想。为避免模拟那种确定性设置，我们实现了一个功能，通过ptrace在用户指定的虚拟地址注入INT3断点指令。
在此模式下，目标进程本机执行直到命中断点指令。一旦命中，快照器重新获得目标控制，随后将目标进程内存和与Remill兼容的寄存器状态结构转储到“工作区”目录。然后可以从该工作区重新创建原始进程的内存映射。
|
|
对于地址空间布局随机化（ASLR）二进制文件，--dynamic标志指示快照器将断点地址解释为主程序二进制文件内的偏移量。为此，我们使用一个巧妙技巧：解析目标进程的/proc/[pid]/maps文件以发现加载程序的基础虚拟地址。进行一些算术运算，瞧，我们有了断点位置！
|
|
动态将机器码提升为位码
现在我们有了快照，我们可以要求KLEE-Native动态提升并执行程序。我们可以用以下命令做到：
|
|
下图显示了klee-exec的控制流。
在高层次上，KLEE-Native即时解码并提升跟踪，这些跟踪是简单的LLVM函数对象，包含提升机器码的逻辑段。跟踪包含模拟机器码的LLVM指令以及对Remill内在函数和其他提升跟踪的调用。
内在函数调用可能由KLEE的“特殊函数处理程序”能力处理，这允许运行时位码直接访问KLEE的执行器和状态。例如，Remill的内存读写内在函数使用特殊函数处理程序与快照地址空间交互。
当模拟像malloc这样的函数时，跟踪是从libc的实现创建的，执行能够顺利继续。世界一切都好。我们看到光明，一切都有意义……
……开玩笑的！brk和mmap来了，现在我们必须执行系统调用。我们该怎么办？
运行时是内核和机器
KLEE-Native将所有机器码提升到原始系统调用指令。使用Remill，系统调用指令通过调用运行时位码中的内在函数__remill_async_hyper_call来处理。Remill不指定此函数的语义，但意图是它应实现执行低级操作所需的任何硬件或OS特定功能。
在我们的案例中，KLEE-Native实现了__remill_async_hyper_call函数，因此它将执行从提升的位码传递回运行时位码，其中每个Linux系统调用包装器都被实现。
系统调用包装器由应用程序二进制接口（ABI）类型参数化，该类型查找系统调用号和参数并存储返回值。以下是SysOpen函数的示例，它包装了由KLEE运行时实现的POSIX open系统调用。
模拟open系统调用的片段
此包装器执行实际OS内核会做的一些错误检查。（即，确保文件路径名可以从快照地址空间读取，检查路径长度等。）这里我们发挥KLEE的优势：如果任何被测试的数据是符号的，所有这些错误检查路径都接受符号探索。
我们现在已经动态将机器码提升为位码，并且我们模拟了系统调用。这意味着我们可以运行提升的机器码，并让它以与从源码编译的位码相同的方式与KLEE自己的运行时“对话”。
我们对malloc的调用继续执行并分配一块内存。生活再次美好，但事情开始变慢。而且，我的意思是非常非常慢。
通过半虚拟化恢复源码级抽象
操作机器码意味着我们必须处理一切。这在翻译看似良性的libc函数时是有问题的。例如，strcpy、strcmp和memset需要大量的提升工作，因为它们的汇编由SIMD指令组成。模拟形成这些函数的复杂指令最终比模拟简单版本更耗时。如果这些函数操作符号数据，这甚至不解决可能发生的大量状态分叉。
我们半虚拟化libc来解决这个问题。这意味着我们向快照程序引入一个基于LD_PRELOAD的库，让我们拦截和定义我们自己版本的常见libc函数。在拦截器库中，我们的半虚拟化函数是POSIX原型的薄包装器，执行它们会导致在快照前调用原始POSIX函数。
它们的目的是成为我们在快照阶段找到并修补的单一入口点。在以下示例中，快照器将用NOP指令修补JMP，以便当由KLEE-Native模拟时，malloc最终调用INT 0x81。
LD_PRELOAD malloc拦截器
当在模拟期间命中中断时，我们检查中断向量号并挂钩到相应的半虚拟化libc运行时函数。有时我们的半虚拟化libc函数版本无法处理所有情况，因此我们支持回退机制，将控制权交给原始libc函数。为此，我们将模拟程序计数器加一，并跳过RETN指令，从而导致原始函数被执行。
以下是我们LD_PRELOAD库当前拦截的libc函数。每个数字（例如，malloc的0x81）是对应于该函数半虚拟化版本的中断向量号。
具有半虚拟化等效项的libc函数
太好了！我们对malloc的调用反而命中了中断，我们能够挂钩到其在KLEE中的半虚拟化版本。我们到底用它做什么，为什么我们关心？
用libc拦截器建模堆内存
在模拟malloc期间对mmap或brk的调用将为分配布局内存。虽然这是提升机器码指令的准确表示，但它不是用于查找漏洞的高效模型。问题：mmap非常粗粒度。
每次内存访问都可以看到，但不清楚给定分配的开始或结束位置。因此，很难进行边界检查以检测溢出和下溢。此外，当分配是不透明的块时，对像双重释放和释放后使用这样的漏洞类没有监督。
这就是为什么我们拦截malloc和其他分配例程，以制定一个明确的内存模型，划分内存分配。这种方法使得KLEE-Native能够轻松分类和报告堆漏洞。这种方法的独特之处在于，我们为分配发明了一种全新的地址格式，以使我们的生活更轻松。它包含关于每个分配的元数据，这使得在我们的内存模型中简单定位。
显示我们自定义地址编码组件的联合
由我们半虚拟化malloc支持的分配并不真正“存在”于传统地址空间中。相反，它们存在于分配列表中。这些结构允许单个分配共存，以便它们易于访问、跟踪和操作，这使得边界检查、双重释放检测和溢出/下溢检测极其透明。此外，分配列表使我们能够灵活地从基于堆的缓冲区溢出等问题中恢复，通过扩展支持“分配”在原地。
万岁！我们使用分配列表实现了目标分配内存的清晰表示。但等等。这不应该是一个符号执行引擎吗？所有这些实际上只是具体执行。发生了什么？
急切具体化以改进分叉模型
我们的符号执行方法偏离了KLEE使用的典型调度和分叉模型。KLEE是“动态符号执行器”，而KLEE-Native更接近SAGE，一个静态符号执行器。
KLEE-Native的分叉方法倾向于急切具体化和深度优先探索。关键在于我们可以在不牺牲全面性的情况下做到这一点。意思是，总是可以返回到执行中的先前点并请求下一个可能的具体化，如果那是我们的策略。这不同于像KLEE或Manticore这样的东西，它们急切分叉（即，生成大量可行状态，然后委托调度器随时间选择它们）。
我们创建的机制，以实现急切具体化而不牺牲分叉潜力，使用状态延续实现。状态延续就像Python生成器。在KLEE-Native中，它们打包并保存在任何分叉前的执行状态副本，以及产生下一个可能具体化所需的任何元数据（从而给我们全面性）。然后执行器可以从给定延续请求下一个可能的分叉状态。因此，每个请求给我们返回一个新的执行状态，其中某些条件已被具体化（因此术语“急切具体化”）。
目前，我们将状态延续存储在堆栈上。结果是KLEE-Native在“变宽”之前“变深”。这是因为在每个状态可能被分叉的点，我们创建一个延续，从该延续获取第一个状态，并将其推入堆栈。当一个状态执行完成时（例如，它退出，或遇到不可恢复的错误），我们查看堆栈上的最后一个延续并要求其下一个状态。这个过程继续直到一个延续耗尽。如果发生这种情况，它被弹出，我们转到堆栈上的下一个延续。未来，我们将探索替代策略。
急切具体化时如何分叉
我们的方法是由需要处理符号内存地址驱动的。我们开始添加符号，但无法总是让KLEE探索所有路径。KLEE正在具体化内存地址，但并非全面方式。这诚然是预期的，因为符号内存是一个难题。
实现具体内存很容易，因为本质上有一个地址到字节值的映射。然而，当一个地址可以取许多值时，这意味着什么？我们决定最好的策略是创建一个通用机制，立即具体化地址而不丢弃所有其他可能性，然后留给策略处理程序做出更实质性的方法。更实质性策略的示例可能是采样、最小/最大等。
太好了！我们现在可以探索程序的状态空间。让我们去狩猎。
在现实世界中应用KLEE-Native
因为我们控制模拟地址空间和内存分配，用KLEE-Native分类不同类型的内存破坏漏洞变得容易，漏洞分类是其绝佳用例。此外，我们的急切具体化策略确保我们将坚持感兴趣的代码路径。
以下是来自Google fuzzer-test-suite的CVE-2016-5180。它是c-ares中的一个单字节写入堆缓冲区溢出，用于ChromeOS漏洞利用链。
我们首先在main处用动态断点快照程序：
|
|
然后简单地运行klee-exec命令：
|
|
这里我们得到KLEE-Native检测到单字节堆溢出。
那么，与AddressSanitizer或Valgrind相比，什么使KLEE-Native特别？这是我们的策略处理程序发挥作用的地方。处理像这样的内存访问违规的一个策略是用符号字节替换溢出字节。随着执行继续，我们可能通过报告最后符号溢出字节的范围来诊断错误的严重性。这可以让漏洞研究人员区分允许有限溢出可能性的状态与可能允许写-什么-哪里原语的状态。
在KLEE-Native中，未定义行为可以成为符号执行的新来源。这使得无需事先了解威胁模型和繁琐的逆向工程即可进行漏洞分类。
再见！
我的实习产生了KLEE-Native；一个版本的KLEE，可以具体和符号地执行二进制文件，建模堆内存，复现CVE，并准确分类不同的堆错误。该项目现在定位为探索由KLEE-Native独特符号执行方法实现的应用。我们还将研究不同提升策略可能带来的执行时间加速。与所有关于符号执行的文章一样，KLEE既是问题也是解决方案。