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