1. 介绍

• 假设有一个程序  和一个补丁版本 ，为  生成样本输入执行  中修补的漏洞，通过添加与漏洞相关的输入约束条件，然后生成违反这些约束的输入，将其沿着通往漏洞点的路径传递，结果是会触发漏洞。使用数据流分析得出路径条件，然后解决此类问题条件使用决策过程 STP 来产生一个新的程序输入。由于生成的程序输入旨在违反添加的约束，因此可能会导致由于某种形式的内存损坏而崩溃。
• 使用可能导致崩溃的输入作为起点，再次使用数据流分析来构建路径条件，然后用于使用决策过程生成新输入。
• 通过调试器附加到一个正在运行的进程，然后将测试用例交付给程序。这种方式会遵循一组静态规则来发现漏洞类型。这些规则试图确定输入数据的哪些部分覆盖了哪些敏感数据，因此可以用来控制程序的执行。一旦确定结果，这些值将用于漏洞类型的模板生成漏洞利用。
• 通过API，例如 printf。一旦这些 API 功能的效果产生形式化后，指定漏洞利用所需的条件，然后通过调用函数确定漏洞类型。这种方法仅限于所有必然的内存损坏的漏洞，比如printf格式化字符串漏洞。
• 自动为漏洞生成签名，并使用这些签名来描述是否有漏洞。
• 现在常见的还有数据流分析、污点传播、约束求解和符号执行等方法。

约束

• 用户输入的数据破坏了存储的指令指针、函数指针或写目标地址的地址和源值；    
• 可以启用ASLR，但没有其他漏洞利用保护；
• 使用数据流分析和约束求解来检测控制流劫持漏洞；
• 需要漏洞利用自动生成并执行；
• 应该可靠地将漏洞归类为可利用漏洞和不可利用漏洞（比如DoS），这一点至关重要。

2. 问题定义

操作系统和架构

1. EIP寄存器：指令指针寄存器；
2. EBP寄存器：栈数据相关；
3. ESP寄存器：栈数据相关；
4. EFLAGS寄存器：关乎程序执行流；

• 汇编语言、内存存储方式；
• ELF文件格式；

构造函数和析构函数

$ objdump -s -j .ctors a.out

a.out:     file format elf32-i386

Contents of section .ctors:
 8049f00 ffffffff 00000000                    ........
$ objdump -s -j .dtors a.out

a.out:     file format elf32-i386

Contents of section .dtors:
 8049f08 ffffffff 00000000                    ........
$ nm ./a.out | grep '__[C|D]TOR'
08049f04 d __CTOR_END__
08049f00 d __CTOR_LIST__
08049f0c D __DTOR_END__
08049f08 d __DTOR_LIST__

Contents of section .init_array:
 8049f00 d0830408 fc830408                    ........
Contents of section .fini_array:
 8049f08 b0830408 10840408                    ........

• 包括但不限于ASLR、NX（DEP）、Canary、堆的基本保护机制及绕过方式

程序定义

指令定义

路径定义

内存定义

CPU寄存器定义

漏洞利用定义

•  是直接破坏  中的一个或多个字节的指令序列（ 是一组不应该被用户输入污染的内存位置）；
•  是破坏内存位置  的指令序列，其地址是我们应该注入的payload地址；
•  是漏洞注入进程的payload。

AEG模型

• 首先，它必须能够分析程序的内存状态，以便找到合适的位置注入我们的payload。它必须确定用户输入对内存造成影响的输入点，还必须能够发现输入后程序路径的结束点。从这些信息中，它将生成一个输入，填充所选定的输入点缓冲区；
• 其次，必须检测  中被用户输入污染的位置，以便重定向到payload处，这将再次要求算法确定输入字节数，在程序的崩溃位置前进行修改；
• 最后，必须能够根据前面的模型创建一个公式：输入  破坏  中的值导致重定向到恶意代码 。

3. 自动漏洞利用算法

• 阶段一包含迭代检测和污点分析。通过跟踪程序来分析程序执行的路径，分析并记录与当前路径条件相关信息，直到发现可利用漏洞点为止；
• 一旦发现漏洞点，就开始第二阶段。包含四个任务：
1. 确定漏洞的类型。如果是指令存在漏洞，我们尝试间接利用；如果是函数指针类型，那么我们尝试直接利用函数指针；
2. 然后构建我们第一个漏洞利用公式：输入  破坏  中的值导致重定向到恶意代码 。在污点分析过程中就应该过滤处理这些缓冲区，我们将这些位置作为下一个公式的跳板；
3. 随后我们构造第二个公式用于约束存储的指令指针（间接利用）或函数指针（直接利用）。对于直接利用，我们限制EIP的值；而对于间接利用，我们限制  的操作数的值；
4. 然后我们结合两个公式，计算所有的内存位置的路径条件。这个最终公式表达了对程序  利用所需的条件。
• 阶段三使用决策程序来尝试生成满意的利用脚本。

第一阶段 检测和运行时分析

• 执行跟踪。这种方法将程序运行过程中的指令、寄存器和修改的内存储存在数据库中。有些调试器还提供了一些其他的功能，例如Ollydbg、gdb。这种方法很有用，因为它对程序运行性能影响很小，缺点就是需要大量的磁盘来保存数据；
• 仿真。现在有很多工具可以模拟硬件功能，在虚拟环境中执行程序，例如QEMU，它允许控制仿真系统运行，并在运行期间分析数据流和路径条件信息；
• 二进制检测。这是一种代码注入技术，即二进制插桩。注入的代码负责观察被检测的程序。

• Valgrind：与其他二者的主要区别是将程序的汇编代码转化为中间语言  表示，然后再提供给客户端分析，这种中间语言类似于RISC。这意味着分析客户端不必显式的添加x86汇编。因为需要转换中间语言，所以性能方面会有所折扣：

举个例子, x86汇编代码如下:
addl %eax, %ebx

IR中间语言表示如下:
------ IMark(0x24F275, 7) ------
t3 = GET:I32(0) # get %eax, a 32-bit integer
t2 = GET:I32(12) # get %ebx, a 32-bit integer
t1 = Add32(t3,t2) # addl
PUT(0) = t1 # put %eax

• DynamoRIO：有跨平台和C++支持，但没有Pin支持的操作系统多；
• Pin：有跨平台和C++支持，更少的性能开销。但没有  中间语言，可能写起来会更冗长一些。

1: ins_operands= extractOperands(ins)
2: ins_dsts= extractDestinations(ins)
3: ins_srcs= extractSources(ins)

4: for idx ∈ len(insdsts) do
5:     srcIndices = extractSources(ins, idx)
6:     sources = vector()
7:     for idx ∈ srcIndices do
8:         sources.append(inssrcs[idx])
9:     end for
10:    ins_dsts[idx].sources= sources
11: end for

12: if setsEFlags(ins) then
13:     eflags = eflagsWritten(ins)
14:     PIN_InsertCall(AFTER, updateEflagsOperands(eflags, ins))
15: end if

16: if isConditionalBranch(ins) then
17:     cond = getCondition(ins)
18:     operands = getConditionOperands(eflagsRead(condition))

19:     PIN_InsertCall(BRANCH TAKEN, addConditionalConstraints(cond, operands))
20:     PIN_InsertCall(AFTER, addConditionalConstraints(!cond, operands))
21: else if writesMemory(ins) or writesRegister(ins) then
22:     if writesMemory(ins) then
23:         PIN_InsertCall(BEFORE, ins, checkWriteIntegrity(ins))
24:     end if

25:     PIN_InsertCall(BEFORE, ins, taintAnalysis(ins))
26:     PIN_InsertCall(BEFORE, ins, convertToFormula(ins))
27: end if

28: instructionType = getInstructionType(ins)

29: if instructionType == ret then
30:     PIN_InsertCall(BEFORE, ins, checkRETIntegrity(ins))
31: else if instructionType == call then
32:     PIN_InsertCall(BEFORE, ins, checkCALLIntegroty(ins))
33: end if

• Line 1-3：这部分的目的是解析寄存器和源操作数、目的操作数列表；
• Line 4-11：虽然Pin提供了确定指令读和写的位置的功能，但为了准确的表示每条指令的语义还需要额外处理。从第 5 行开始使用 extractSources 函数获取影响目标的源索引向量处理。这个函数本质上是一个目标索引到源索引的映射，必须是我们希望处理的 x86 指令。第 7-9 行，遍历这些索引并从 inssrc中提取来源信息。第 10 行这个向量存储在当前目的地的源属性中；
• Line 12-15：确定指令是否修改了 EFLAGS 寄存器，如果当前指令修改了 EFLAGS 寄存器，我们提取被修改的指令的索引。第 14 行使用 Pin 提供的函数插入对 updateEflagsOperands 函数的调用；
• Line 16-20：处理条件分支指令，取决于 EFLAGS 中一个或多个索引值的指令记录。在这个算法中，我们只考虑条件指令的直接影响改变控制流程，即条件分支。x86 中的一些条件分支指令指令集有jl、jg、jb等。第 17 行使用 getCondition 函数提取指令表达的条件。例如，如果指令是 jl，那么提取的条件即“小于”。第 18 行，检索最后设置该指令所依赖的 EFLAGS 索引的指令的操作数。例如，jl 指令检查符号标志是否等于溢出标志位。第 19 行，插入调用以将条件添加到我们的全局存储中，并在第 20 行插入调用以添加否定条件，然后将在运行时存储条件的正确版本，具体取决于走哪条路径；
• Line 21-27：如果一条指令不是条件分支，那么我们检查它是否为写操作或者它是寄存器。如果指令是写操作，我们插入一个函数检查写入完整性。此函数将确定指令参数是否可被用户污染；
• Line 28-33：对于直接修改 EIP 寄存器的指令，我们必须检查值是否可被污染。在执行指令 ret 和 call 之前Integrity 函数将进行检查，确定它们是否被用户输入污染。

污点分析

1: for dst ∈ ins_dsts do
2:     latticePos = TOP

3:     for src ∈ dst.sources do
4:         latticePos = meet(latticePos, L(src))
5:     end for

6:     L(dst) = latticePos
7: end for

• Line 1-2：遍历每个目标操作数并计算其“格”位置，将格位置初始化为 TOP的一个临时变量来指示处理尚未发生的事件；
• Line 3-5：对于每个目标地址，都会遍历影响其值的源列表。格目标地址的位置被计算为其所有源的格位置的交汇点。
• Line 6-7：一旦找到当前目的地址的格位置，它就会被存储起来，并且处理下一个目的地址的指令。

1: insComplexity = getInsComplexity(ins)
2: for dst ∈ ins_dsts do
3:     latticePos = TOP

4:     for src ∈ dst.sources do
5:         latticePos = meet(latticePos, L(src))
6:     end for

7:     if latticePos != untainted then
8:         latticePos = meet(latticePos, insComplexity)
9:     end if

10:    L(dst) = latticePos
11: end for

• Line 1：检索与当前指令类型相关的复杂性类。getInsComplexity 将希望处理的每条指令映射到新格表示分配、线性算术或非线性算术的位置；
• Line 2：与前面的算法一样；
• Line 3-6：与前面的算法一样；
• Line 8-9：至此已经根据来源计算了目的地址的格位置。然后我们将该值与指令的格位置相交，以给出最终格目的地址的位置。我们需要检查源上的格位置是否受到污染，如果指令的源是未受污染的，那么指令的格位置都是未受污染的。

构建路径条件

mov [12345], eax ; a = b
mov ebx, 10 ; c = 10
add ebx, [12345] ; d = c + a
mov edx, ebx ; e = d

1: for idx ∈ len(ins_dsts) do
2:     varId = generateUniqueId()
3:     updateVarId(ins_dsts[idx]], varId)

4:     rhs = makeFormulaFromRhs(ins, idx)
5:     storeAssignment(varId, rhs)
6: end for

• Line 1-3：分别处理指令的每个目标操作数，并从生成开始与该目的地关联的唯一名称；
• Line 4-5：提取与目标 ins_dsts[idx] 关联的源，并在这些源上生成一个公式，描述指令对目的地址的影响。最后计算符号公式 varId = rhs 并将其存储以供之后处理。

第二阶段 构建漏洞利用公式

1. 对已知直接影响 EIP 的参数进行完整性检查失败：我们在运行时挂钩所有 ret 和 call 指令，并检查指针是否被污染；
2. 对写入指令的目标地址和源值的完整性检查失败：与前一种情况一样，我们挂钩所有写入内存的指令来检测可能导致间接利用的漏洞；
3. 操作系统的错误信号：如果发生内存损坏，则可能是程序试图读取、写入或执行此内存时，程序被操作系统终止，例如 SIGKILL、SIGABRT 或 SIGSEGV；
4. 执行已知的“错误”地址：当发生潜在危险的内存损坏时，仅触发 libc 等库中的某些错误处理程序，例如堆分配检查时的错误输出函数。

1: if crashIns.type == WRITE then
2:     exploitType = indirect
3:     continueExecutionUntil(indirectControlIns)
4: else
5:     exploitType = direct
6: end if

7: shellcodeBuffers = buildShellcodeBuffers(registers) 
8: scBuf = None
9: for buf ∈ shellcodeBuffers do
10:     if buf.size ≥ len(shellcode) then
11:         scBuf = buf
12:         break
13:     end if
14: end for

15: if scBuf == None then
16:     exit("No shellcode buffer large enough for shellcode")
17: end if

18: scConstraintFormula = buildFormula Shellcode(shellcode, scBuf) 
19: ι = getTrampolineForRegister(scBuf.jmpRegister, trampolineAddrs)

20: if exploitType == direct then
21:     eipControlFormula = buildFormula InsPointerControl(registers.ESP, ι) 
22: else
23:     dst = crashInsdsts[0]
24:     src = dst.sources[0]
25:     eipControlFormula = buildFormula WriteControl(dst, src, indirect mEIP, ι) 
26: end if

27: eipAndScConstraints = createConjunct(eipControlFormula, scConstraintFormula)
28: exploitFormula = eipAndScConstraints

29: for varId ∈ eipAndScConstraints.variables do
30:     pc = buildPathCondition(varId) 
31:     exploitFormula = createConjunct(exploitFormula, pc)
32: end for

33: return exploitFormula

• Line 1-6：通过决定生成哪种类型的漏洞利用（直接或间接）开始算法。要是我们生成一个间接利用的漏洞，这个地址必须作为indirectControlIns 提供；
• Line 7-14：处理在第一阶段收集的污染信息，生成可能存在利用的地址列表，遍历返回的 payload 所在的缓冲区，直到找到足够大的缓冲区来存储 payload；
• Line 18：建立一个公式，选择缓冲区所需的约束等于提供的payload；
• Line 19：根据我们决定使用的缓冲区和指向它的寄存器，选择地址列表中的跳板指令。这些指令可以有很多方法获得，比如Metasploit框架或者其他小工具；
• Line 20-26：此时我们生成的公式将直接控制指令指针（直接利用）或控制写指令的源/目的操作数（间接利用）；
• Line 27-32：payload缓冲区公式与控制指令公式的结合，然后从程序输入为该公式中的每个变量构建路径条件；
• Line 33：返回变量路径条件公式。

第三阶段 求解漏洞利用公式

4. 具体实现

二进制检测

• 提取目的地址和源值，然后将这些传递给一个运行时分析例程，该例程查询对象来确定这些位置是否被污染。
• 污点分析算法可挂钩与之相关的系统调用，例如read、write、open。Pin允许我们在程序运行系统调用前插桩，这样就可以用于确定某些内存是否被我们的输入所污染。一旦一个位置被标记为受污染，指令级检测代码就可以传递污染信息，包含当前进程上下文。
• 除了系统调用，我们还在线程创建和从操作系统接收到的信号上挂钩。在多线程应用程序中，我们有必要确定何时创建和销毁线程，以及在调用我们的分析例程时识别当前活动的线程。线程不共享寄存器，所以被其中一个线程污染的寄存器不应该被标记为被其他线程污染。当一个线程创建后，可以在污点分析引擎中实例化一个新对象，该对象表示其寄存器的污点状态；当线程被销毁时，该对象被删除。
• 由于 Pin 不使用 ，因此要求我们对每条指令进行一些额外的处理以确定所需的模拟函数并提取指令操作数，具体操作方式可以查看官方文档。
• Pin中的x86Simulator类包含我们希望分析的函数中的每条汇编指令。它包含一个或多个变体，具体取决于它的操作数类型。例如，一条 mov 指令有两个操作数，它可以从内存到到寄存器、从寄存器到寄存器或从寄存器到内存。
• 可以通过检查某些指令的参数来检测潜在的漏洞。对于直接利用，我们要求 ret 指令中 ESP 寄存器指向的值被污染，或者调用指令使用的内存/寄存器被污染；对于间接利用，我们必须检查写目标地址是否被污染。
• 记录操作数何时修改 EFLAGS 寄存器，然后在这些操作数上生成约束。当遇到条件跳转，检查 EFLAGS 寄存器是否在当前指令时被写入被修改寄存器列表中来检测指令是否写入 EFLAGS 寄存器。
• 可以为每个条件跳转插入两个回调条件：一个在从真实条件产生的路径上，另一个为假条件的路径。

运行时分析

• 检查读取的内存位置是否被污染，如果不是，则目标位置是未污染的。
• 在运行时通过检测EFLAGS寄存器的位来监测程序执行流。
• 通过分析函数当前 ESP 值以确定该地址处的内容是否为污染。如果发现内存位置或寄存器被污染，我们可以检索关联的对象，使用该位置并开始生成利用。
• 检查可利用的写指令，要求目标地址和源地址被污染。因此，对于像 mov DWORD PTR [eax], ebx 这样的指令，我们必须检查 EAX 中的值是否为污染，而不是 EAX 指向的地址的内容。或者EBX 中的值被污染了。

生成利用

• 为了构建漏洞利用公式，必须处理在运行时分析期间收集的信息。此阶段实现的工作主要是寻找合适的payload 缓冲区，和控制 EIP 所需的内容，并为所需的内容构建路径条件。为了建立这样一个公式，条件是发现需要更改哪些字节，然后构建它们的路径条件，附加指定的约束，对构成 payload 位置和劫持 EIP 而修改的位置执行此过程。
• 对于直接利用，检索与该位置关联的对象ESP 寄存器或栈中指针。对于间接利用，我们提取对象与写入目标地址和源值相关联。将地址传递到我们在二进制检测阶段的分析例程。
• 为了生成漏洞利用，我们需要运行所有可能的 payload。我们可以生成多个利用公式，然后对每个公式使用不同的payload。
• 一旦构建了所有可能的 payload 缓冲区集合，我们就可以遍历寄存器并找到那些可以通过寄存器跳转指令访问的 payload 缓冲区。我们还处理列表，用于发现不受地址随机化影响的 payload 缓冲区。算法应该尽可能使用寄存器跳转指令访问到的缓冲区。
• 在生成直接漏洞利用时，我们希望修改目标地址而不是该地址的值。可以间接的从寄存器、内存地址和常量的组合中得到最终的有效地址。