0 概述

自1988年第一例缓冲区溢出漏洞攻击——莫里斯蠕虫爆发以来，针对内存漏洞的攻击方法便层出不穷，相应的防护手段也不断推陈出新^[1]，内存漏洞的攻防博弈成为网络空间安全领域的热点问题之一。

在早期的代码注入攻击中，渗透测试人员利用溢出漏洞向内存中注入恶意代码并篡改保存在内存中的跳转地址，使程序的控制流转向所注入的恶意代码中。为了解决这一问题，现代操作系统开始引入一种名为数据执行保护（Data Execution Prevention，DEP）的保护机制，其将内存中的数据和代码进行严格区分，渗透测试人员注入的恶意代码只能被当作数据解析而无法被执行，从而使得常规的代码注入攻击难以发挥作用。

随着攻防技术的相互促进与发展，代码重用攻击（Code Reuse Attack，CRA）开始兴起^[2-4]，渗透测试人员利用内存漏洞改变程序的执行流程，通过将内存空间中已有的分散代码片段（称为gadget）进行链接，构造出具备特定功能的程序逻辑从而实现攻击的目的，能够达到与传统代码注入攻击相同的效果。

代码重用攻击在实施过程中较为繁杂，通常需要一些工具辅助人工来完成gadget序列的构建，学术界也提出了很多自动化的构建方案，但都存在诸多问题使其难以得到广泛应用。短期内，代码重用攻击在实施过程中存在的问题将使得攻击成本增加，恶意攻击者不得不付出大量的时间来构建攻击载荷，从长远来看，这也不利于防御机制的进一步发展。因此，加快代码重用攻击的实现过程，快速构建攻击载荷，能够方便渗透测试人员对系统进行评估测试，从而构建更加安全有效的防御系统。

本文提出一种基于表达式树的gadget语义分析方法，通过表达式树变体描述gadget修改寄存器和内存读写的情况，从而提高gadget语义分析的效率，加快gadget序列的构建过程。

1 研究背景 1.1 代码重用攻击

代码重用攻击是一种利用漏洞改变程序在内存中的原有代码执行流程以实现攻击目的的漏洞利用技术。以一个存在栈溢出漏洞的程序为例，在传统的攻击方法中，渗透测试人员需要向栈中注入恶意代码，并修改程序的返回地址，使程序的控制流转移到恶意代码的起始地址，这种方法称为代码注入攻击。但是，现代操作系统已经广泛采用数据不可执行（DEP）等防御机制，代码注入攻击对此难以实现攻击目的，因此，代码重用攻击成为当前的主流攻击方式。

代码重用攻击和代码注入攻击之间既有一些共性特征也存在差异，它们都是利用计算机内存漏洞的攻击方式，均会篡改一些影响程序执行的关键数据，如栈中的返回地址、函数指针等，以此实现超出程序设计者预期的功能逻辑。两者的区别在于渗透测试人员执行恶意代码的方法不同，代码重用攻击无需向内存中注入外部代码，只需重用程序中已经存在的指令片段，这些指令片段能够完成一定的计算和赋值等功能，因此也被称为gadget，通过多个gadget的拼接，渗透测试人员可以实现一些特定的意图。代码重用攻击通常会使程序的控制流转向特定的gadget，并按设定的顺序依次执行gadget，其实现过程如图 1所示。

对于现代操作系统中某个存在缓冲区溢出问题的程序，为了绕过ASLR和DEP保护，渗透测试人员需要进行以下3个步骤：

1）利用内存信息泄露漏洞得到需要调用的函数的地址和存在问题的缓冲区位置。

2）构建gadget序列以调用该函数。

3）根据gadget序列构造攻击载荷并传递给程序。

上述过程的核心是选择合适的gadget序列。渗透测试人员在实现某些功能前需要初始化一些寄存器，例如，在64位Windows操作系统中进行函数调用前需要在RCX、RDX、R8和R9寄存器以及栈中设置参数。对于每一个需要初始化的寄存器，都要找到一个能够对其进行修改的gadget，因此，在典型的代码重用攻击中要调用某个函数，构造的gadget序列通常要包含：

1）寄存器写gadget，向RCX、RDX、R8和R9寄存器中写入指定的值。

2）能够调用特定函数的gadget。

要从程序中找到这些gadget，需要确定gadget的部分语义，例如能否修改栈顶指针、能否修改特定的寄存器、是否有函数调用以及调用了哪个函数等信息。gadget序列的构建过程还会受到一些因素的影响，其中，最主要的影响是多个gadget使用同一寄存器或同一内存空间的情况，这会导致寄存器或某一内存空间在赋值和使用时出现数据不一致的问题，这也被称为gadget的副作用。由于gadget副作用的存在，手工构造gadget序列的过程极为繁琐复杂。自SHACHAM提出ROP^[3]以后，自动化构建gadget序列的研究就开始展开，但截至目前，gadget工具的自动化效果并不理想，多数工具只实现了自动化搜索gadget并进行语义分析的功能。对于ROP及其变种，gadget搜索主要通过指令特征定位到特定的指令位置，再通过切片的方式实现，该方法的优化存在局限性。

1.2 gadget语义分析技术研究现状

由于机器指令的指令集过于复杂，并且与硬件结合过于紧密，直接对其进行分析时难度较大。因此，现有工具通常会将gadget的指令转换成IR（Intermediate Representation），再以形式化的方法来确定gadget所执行的操作。

SCHWARTZ等人设计了能够对二进制文件自动生成ROP载荷的工具Q^[5-6]，其主要思想是将搜索到的gadget以一种更容易处理的中间形式表示，使用编译器编译时的指令匹配思路，结合中间形式在gadget集合中选择合适的gadget来实现用户描述功能。Q将gadget按功能进行分类，并设计一种QooL语言，与gadget的类别相对应。Q在判定某个gadget是否属于特定功能的gadget类别时，采用程序验证领域中程序最弱前置条件的计算方法^[7-9]，具体如下：gadget $ \mathcal{L}$和后置条件$\mathcal{B} $的最弱前置条件WP（$ \mathcal{L}$，$\mathcal{B} $）是一个能够判断gadget在执行后能否满足条件O的布尔值，如果WP（$ \mathcal{L}$，$\mathcal{B} $）恒为真，则gadget属于后置条件B对应的类别。这种将语义进行分类的思想也被许多gadget工具所采用。

BARFgadget^[10]用2种方式实现gadget分类和验证的功能，其仿照Q将gadget按功能分类，并为每一个类别定义一些判断条件。在分类功能中，创建一个随机化的初始状态，通过BARF中的IR模拟器执行二进制代码对应的REIL指令以得到执行gadget后的状态，确定gadget读写了哪些寄存器以及是否修改了内存和标志位，并根据这些信息对gadget的功能进行初步分类；在验证功能中，根据预先定义的约束条件，通过约束求解的方式进一步验证gadget是否具有前一阶段确定的功能类别。

PSHAPE^[11]使用VEX作为中间语言，并结合VEX指令的特点，将PUT、ST和GET指令中的寄存器进行展开，用由寄存器构成的表达式替换临时变量，展开的过程中根据寄存器的传递关系，每次更新寄存器的最终值并且记录寄存器解引用的情况。Ropper和PSHAPE的思路基本一致，针对PUT、ST和GET 3种操作寄存器和内存的指令，提取指令所依赖的表达式，最后使用约束求解器求解栈指针的偏移。angrop基于angr框架开发，其充分利用了angr提供的功能，将寄存器符号化，创建一个空白的初始状态，使用符号执行得到执行gadget后的状态，根据新状态中寄存器和内存的值获取gadget读写寄存器和内存的情况。

ROPgenerator^[12]使用REIL作为中间语言，在将gadget的指令转换成REIL指令后，会对每一条指令进行分析，所有对寄存器和内存的操作会被作为有向图的一个节点，节点中包含操作的表达式，通过节点之间的边来表示寄存器之间的依赖关系，在遇到条件指令时，在边上添加条件的约束信息。最后，从有向图中提取出条件和表达式的键值对以得到gadget的语义摘要。

BOP（Block Oriented Programming）^[13]是一种非控制数据攻击，其gadget是遵循程序原有执行流的代码块，但若要实现特定意图，还需程序能够执行到具有特定语义的基本块上，并且在执行时满足一些特定的约束。自动化工具BOPC对程序的基本块进行了抽象，其将寄存器符号化，在angr框架上进行符号执行，通过对符号执行后状态的判断来得到gadget的关键信息。

1.3 问题分析

代码重用攻击的实施过程较为繁杂，通常需要一些工具辅助人工来完成gadget链的构建，当前已经有很多自动化的构建工具，本文总结6种经典gadget工具的所用技术和实现方法，如表 1所示。

以上gadget工具采用的gadget语义分析技术主要基于静态分析和动态符号执行，一般而言，前者具有更高的效率，后者更容易实现。实际中在进行gadget语义分析时，主要面临如下2个问题：

1）gadget语义分析主要服务于gadget链的构建，其关注的核心内容与其他领域不同，而在当前学术界公开发表的论文中，与gadget语义分析相关的文献资料较少，因此，分析确定gadget的语义是首先要解决的问题。

2）在多数情况下，gadget的数量可能达到数十万，而单个gadget也可能是大段的代码块，需要尽可能地优化gadget的语义分析方法，因此，对现有gadget语义分析方法进行改进，加快语义分析的进程，也是gadget语义分析时需要解决的问题。

针对上述第一个问题，本文分析现有gadget工具的源码，根据各工具分析的gadget语义，定义gadget语义摘要的概念，以明确gadget语义分析的内容；针对第二个问题，本文提出一种基于表达式树的gadget语义分析技术，用一种表达式树变体描述寄存器和内存读写的表达式信息，以提高语义分析的效率。

gadget序列的自动化生成需要完成gadget的搜索、gadget语义摘要的计算与gadget的选择和拼接等功能。gadget搜索已经广泛应用于工程实践中，对于ROP及其变种^[14-16]，采用的算法大多基于Galileo方法^[3]，很难有优化的空间^[17]；对于gadget的选择和拼接，由于某一阶段gadget的选择可能会影响之后所有的gadget选择，并且使用不同的gadget选择策略会产生不同的效果，对gadget长度的影响难以估量，因此，很难用一种通用且有效的方法实现自动化；对于gadget的语义分析，其内容不够明确，当前gadget工具使用的语义分析方法或是设计的结构过于复杂，依托的框架也过于庞大，因此存在优化的可能性。

本文明确gadget语义分析的内容，提出一种基于表达式树的方法，以描述寄存器和内存读写的表达式信息。在该方法中，对描述表达式信息的数据结构进行优化，使其能够快速得到表达式所依赖的寄存器。在各个工具实现的搜索功能和语义摘要的计算功能各不相同的情况下，设计一个实验系统进行对比与分析。

2 基于表达式树的gadget语义摘要计算 2.1 gadget语义摘要

在实际的代码重用攻击过程中，构建一个可用的gadget链并不需要gadget蕴含的全部语义信息。事实上，自动化构建gadget链通常会采用启发式算法，只需考虑gadget副作用的影响和部分关键语义，如系统调用、控制流转移等信息，明确需要分析的gadget语义，并对其进行简化或提炼即能够加快语义分析的进程。为了进一步明确构建gadget序列过程中需要确定的语义，本文分析常用gadget工具的源代码，如表 2所示，其中，“√”表示工具分析了语义，“×”表示未分析。

在表 2中，regw、memr和memw分别表示寄存器写、内存读和内存写操作，expr表示能否为相应的寄存器或内存进行定量分析，生成能够被解析的表达式，sp offset表示栈指针的偏移值，transfer表示控制流转移情况，包括系统调用syscall、库函数调用libcall和条件转移cond。

由于多数gadget工具没有实现gadget链构建功能，因此在上述工具中，只有使用符号执行进行语义分析的2个工具angrop和BOPC对控制流转移情况进行了分析。在实际确定控制流转移情况的过程中，如果目的地址是一个常量，可以通过单条指令的机器码结合指令的地址计算得到；如果目的地址是一个寄存器或内存，可以通过寄存器和内存的表达式得到。

为进一步明确gadget语义，本文定义gadget的语义摘要为：用于表述gadget核心语义和功能的关键信息，包括寄存器和内存的读写情况以及栈指针的偏移。其中，寄存器的读写情况包括被修改的寄存器名、最后一次写入的值及其依赖的寄存器或内存空间，内存的读写情况包括被读取或写入的内存空间的位置、内存地址、写入的值及其依赖的寄存器或内存空间。

2.2 特殊表达式树设计

通过对现有gadget工具的源码进行分析，得出多数gadget工具对gadget进行表达式分析时使用的数据结构不易于处理，尤其对于较长的gadget，分析效率会降低，原因是现有gadget工具表示寄存器数值的方式过于简单，或是使用简单的表达式替换，这使得gadget语义分析不能很好地解析寄存器或内存的表达式。此外，现有gadget工具使用较为复杂的图结构，在维护寄存器和内存读写情况的过程中需要遍历多个节点，并通过多次计算来确定依赖寄存器或内存的信息，在gadget数量较多时其影响较为显著。

gadget工具能从部分二进制文件（如一些大于10 MB的共享库）中搜索到较多的gadget，这时需要计算大量的语义摘要，因此，要尽可能地加快语义摘要的计算速度。符号执行或模拟执行的方法将耗费较长时间，现有工具所使用的静态分析技术同样存在优化的空间。

为了能够支持多种平台，gadget工具一般会将gadget翻译成中间语言，再对中间语言进行语法分析，在语法分析中较为突出的一个问题就是对数学表达式的描述和分析，通常使用表达式树来解决该问题。为了说明中间语言转换成表达式树的可行性，本文以VEX、REIL两类使用最为广泛的中间语言为例，对其中常用的几种指令进行表达式形式转换。

表 3所示为VEX中最常见的8种指令及其表达式形式，将GET、PUT、LD、ST和ITE这5种指令转换成赋值表达式，其中，ITE是条件赋值指令，类似于C语言的条件运算符。将算术指令和类型转换指令转换成算术表达式，多数运算操作都是一元或者二元运算，部分浮点运算操作使用了3个或者4个操作数，并调用了VEX中的辅助函数（helper function），但通常对gadget的语义分析只关心通用寄存器，而辅助函数没有副作用，不会影响寄存器的值，因此，不需要精确地定义其表达式，可以将它转换成多叉树的形式。

表 4所示为REIL中最常见的7种指令及其表达式形式，将STR、LDM、STM、BISZ和JCC这5种指令转换成赋值表达式，其中，BISZ是条件赋值指令，类似于C语言的条件运算符，JCC是条件跳转指令，可以看作是对IP的条件赋值。将算术指令和逻辑指令转换成算术表达式，所有的运算操作都是二元运算，可以很容易地转换成树的形式。

在传统的表达式树中，每一个叶节点对应一个操作数，每一个非叶节点对应一个数学运算，整个表达式树会对应一个算数表达式，而无需考虑特定的子表达式树。但是，gadget的语义分析可能涉及多个寄存器或中间变量，多数情况下需要考虑中间变量的表达式，还需要记录表达式对应的目标变量，因此，本文对传统的表达式树进行一些修改，设计一种特殊的表达式树以表示gadget的语义，具体为：树中有Val和Expr两类节点，Val节点可以是寄存器或内存的初值、常量值和运算符，Expr节点是一棵子表达式树，每一棵子表达式树对应一条IR指令，其根节点必定是一个代表运算符的Val节点，Expr节点中保存了目标变量的信息，这样一个gadget就转化成一棵或多棵表达式树。

由于一个gadget可能多次修改某一寄存器或内存空间，因此需要区分每一次修改寄存器的情况，将寄存器或内存的初始值标记为如同“eax_0”的形式，即在寄存器名或内存地址后加下划线“_”和修改次数“0”。以指令“add eax，ebx”对应的VEX IR为例，如图 2所示，可以得到如图 3所示的表达式树，其中，圆圈代表Val节点，方框代表Expr节点。

与传统的表达式树相同，本文表达式树能够通过访问叶节点来确定表达式的操作数，进而得到gadget的副作用信息，获取表达式所依赖的寄存器或内存空间。与传统表达式树的不同之处在于，该表达式树维护了表达式对应的目标变量，并能通过Expr节点方便地提取某个中间变量对应的表达式值，这为获取部分变量的约束提供了便利。特别地，当gadget的长度较长时，构造的表达式树深度也会增加，在极端情况下会近似成为一条链表，这时确定依赖寄存器的效率会大幅降低。为了能够快速得到依赖寄存器的信息，本文采用以空间换时间的思路，在将IR指令转化成表达式树的过程中，为每一个Expr节点维护依赖寄存器的信息。

2.3 语义分析的执行流程

本文提出一种基于表达式树的gadget语义摘要计算方法，在将二进制转化成中间语言IR后，根据中间语言需要满足SSA（Static Single Assignment）的特点构造2.2节所述的表达式树，根据该表达式树生成gadget语义摘要，执行流程如图 4所示。

在生成表达式树以后，为每一个寄存器和中间变量构建一个键为名称、值为表达树的键值对，为每一个寄存器构建一个修改次数的计数器，此时获取特定寄存器或中间变量的值只需要先通过键值对访问对应的表达式树，然后解析表达式树即可。在解析树时先通过叶节点访问该寄存器或中间变量的依赖寄存器信息，再将对应的Expr节点转换回数学表达式作为约束条件进行求解即可得到对应的寄存器值。对于栈寄存器的偏移值，从栈寄存器对应的Expr节点出发，自顶向下遍历Expr节点并收集约束条件，即可通过约束求解器求出偏移值。

2.4 SemExpr的设计与实现

当前有多种方案能够实现IR翻译和分析功能，如S2E、BARF和angr等框架。其中，S2E使用QEMU进行整个计算机模拟，但这需要较多的系统资源；BARF使用REIL^[18]作为中间语言，当前REIL难以支持很多指令，其中包括gadget中比较常见的指令，如retf，因此，BARF在功能上略显不足；angr使用VEX IR^[19]作为中间语言，相对于REIL，VEX支持的指令集更多，相对于汇编语言，VEX提取语义信息更快捷，因此，其更适合计算gadget的摘要信息，并且已经有angrop、Ropper和PSHAPE等开源工具，这使得angr的实现和评估更为简单。

本文在Ropper的基础上构建原型系统SemExpr，如图 5所示，其中主要包括pyvex和Z3两个开源项目。pyvex是python版本的IR翻译工具，能够将二进制文件转换成VEX IR；Z3是一个高效的SMT（Satisfiability Modulo Theories）求解器，集成了多种约束求解算法。

SemExpr由3个模块构成，加载模块使用了Ropper原有的加载代码，能够读取PE文件和ELF文件的代码段；搜索模块会根据指定的命令行参数，搜索以ret、jmp指令或系统调用结尾的gadget，并去掉重复的gadget；语义模块会对gadget进行分析，得到gadget的表达式树以及各寄存器的表达式，生成约束条件，根据约束条件计算sp的偏移值。系统执行流程如下：

1）加载二进制文件，解析文件头，得到代码段中的字节序列和对应的地址。

2）根据命令行参数，从第1步所得字节序列中搜索具有特定机器码的位置，通过Galileo算法得到gadget，将所有的gadget放到一个集合中以去除相同的gadget。

3）为每个gadget创建一个图结构，利用pyvex得到gadget的VEX IR形式，根据VEX IR指令具有IRStmt、IRExpr和IROp 3层结构的特点，在IROp中得到能够被Z3解析的表达式形式，在IRExpr中构建单个的表达式树结构并根据表达式形式构建约束条件，在IRStmt中将构建的单个表达式树添加到gadget对应的图中。

4）找到sp对应的表达式树，遍历该表达式树，得到树中的全部约束条件。

5）将约束条件作为输入，使用Z3进行求解，得到sp的偏移值。

6）返回gadget的语义摘要信息。

3 实验与评估 3.1 实验系统的设计与实现

现有gadget工具基于Galileo算法均实现了各自的gadget搜索功能，但其搜索参数，如指令长度限制和字节数限制各不相同，并且在搜索后还定义了不同的筛选策略，因此，它们搜索得到的gadget数量也不尽相同。此外，各个工具计算的语义摘要内容略有不同，导致难以对各工具进行对比实验和评估。

针对上述问题，本文设计一个如图 6所示的实验系统gadgetAnalysis，以评估本文设计的gadget语义摘要计算方法的性能。该实验系统由搜索模块、转换模块和语义模块构成，其中，搜索模块用于搜索gadget，在实现时对gadget搜索工具ROPgadget^[20]进行略微修改，使用户能够设定gadget长度的上下限；转换模块用于将ROPgadget的搜索结果转换成各工具能够分析的数据结构，部分工具会在确定语义前对gadget进行筛选，为了提高对比实验的准确性，本文将筛选部分全部去除；语义模块能够对搜索到的gadget进行分析，确定gadget的语义，实现时将各gadget工具的语义分析部分进行提取和修改，只计算本文定义的语义摘要，但是对于PSHAPE，其使用基于字符串替换的语义分析，最后只能得到嵌套的VEX形式的表达式，不能用于gadget序列构建。

3.2 结果与分析

选取Windows和Linux下常见的共享库和软件，设定gadget的指令数为2~10，统计各工具计算语义摘要的时间以及能够处理的gadget数量，进行10次实验取平均值得到如表 5所示的结果。根据表 5的实验结果，从计算时间、能处理的gadget数量和能否生成可用的表达式3个方面衡量各工具的性能，结果如表 6所示。从表 6可以看出，angrop计算时间最长，由于其使用了符号执行，计算的语义最多，面对一些特殊的指令时反而无法处理，因此能处理的gadget数量最少；ROPgenerator虽然计算时间最短，但受限于REIL指令，其能处理的gadget数量较少；PSHAPE计算时间较短，能处理的gadget数量也最多，但其生成的表达式不能被解析；Ropper能处理的gadget数量较多，但其计算时间较长；相较于Ropper，SemExpr在计算时间上取得了明显改进，其能取得较好的效果。

4 结束语

本文针对当前自动化方案构造gadget序列时效率较低的问题，对主流gadget工具计算的语义信息进行提炼，并定义gadget语义摘要的概念，提出一种基于表达式树的gadget语义摘要计算方法。以VEX、REIL 2种中间语言为例，说明中间语言转换成表达式树的可行性，并实现一种原型系统SemExpr。在此基础上，本文设计用于测量gadget语义摘要计算效率的实验系统gadgetAnalysis，仿真结果验证了SemExpr在计算gadget语义摘要时具有较好的性能。在对gadget进行语义分析后，如何根据语义分析的信息来拼接gadget以构建具有特定功能的gadget链，是代码重用攻击实现自动化的瓶颈之一。对于该问题，目前只能通过一些启发式算法来构建具备简单功能的gadget序列，设计算法构建具有指定复杂逻辑的gadget序列将是下一步的研究方向。