OptiROP: ROP gadgets 搜寻神 器
议程 Return-Oriented-Programming(ROP) gadget & shellcode OptiROP: 期望, 思路, 设计和实现 通过语义寻找 ROP gadgets 语义 gadgets 现场演示 总结
攻击 & 防御 软件攻击 使用软件 / 设计的缺陷来利用系统 / 应用软件 通过恶意输入来触发漏洞使得攻击代码得以执行 利用的缓解手段 接受软件可能是错误, 但是难于被利用 已经提出了多种缓解机制, 并被应用到现代系统中 数据执行保护 (DEP) 被广泛地采用 确保来自于攻击者的数据是不可执行的, 因此输入中不能嵌入恶意的载荷 (payload) 应用到硬件, 并且被广泛应用到各种场合
绕过 DEP Return-Oriented-Programming(ROP) 被用来对抗 DEP 确保攻击代码不再嵌入到输入中, 因此能够有效地对抗基于 DEP 的防护 成为了现在编写 shellcode 的主要技术手段
ROP 的概念 非基于代码注入的攻击 : 重用在漏洞程序内存空间中的代码 使用代码片段 (ROP gadgets) 并且将它们串在一起来执行期望的操作 ROP gadget 大多来自于无意识的指令 是图灵完备的
ROP 实例 使得 EAX=0x1234 的 ROP gadgets 序列
ROP shellcode 将 gadgets 串在一起来实现传统方式的代码注入 shellcode 通常通过多个步骤来实现 阶段 -0 shellcode(rop 的形式 ) 将阶段 -1 的载荷所在内存的属性重新映射为可执行 将控制流转移至阶段 -1( 传统的 shellcode)
ROP shellcode 将是未来的主流方法吗? 在 ROP gadgets 加载无 ROP shellcode 这一阶段, 加入了更多的限制 Windows 8 的 ROP 防御手段强制限定了谁 / 在哪里能够调用 VirtualAlloc()/VirtualProtect() 来使内存在运行过程中变为可执行 迫使阶段 -0 做更多的工作 未来的系统可能完全禁止代码注入 不再有阶段 -1 传统形式的 shellcode 了, 转而采用完全基于 ROP 的 shellcode? IOS 已经实现了这一防护手段 可写页具有不可执行属性, 并且仅标记页能够执行 ROP 是 shellcode 的唯一选择
ROP 工具 ROP 编程很困难 如何寻找通过串在一起能够实现目标的 gadgets? 完全 ROP 的 shellcode 是十分困难的 有能够帮助利用编写者来实现寻找并串接 gadgets 的 ROP 工具 ROP 工具不是十分有帮助 给定一个包含 gadgets 的二进制程序, 搜集所有可利用的 gadgets 让用户来从中选择需要的 gadgets 大多数停在这里, 并且无法自动寻找需要的 gadgets, 无法将它们自动串接 对于利用编写者而言, 此阶段是一个需要手动参与的乏味工作
Gadget 种类
传统 ROP 工具的机理 收集 gadgets 定位所有返回指令 (RET) 向前翻一些字节寻找合法的指令序列 记录确认的 gadgets 根据用户需求, 寻找合适的 gadgets 遍历收集的 gadgets, 将它们和用户条件进行匹配 ( 通常使用搜寻 gadget 文本的正则表达式 )
搜寻 gadget 的例子 ROPME 寻找 LOAD gadgets
寻找 ROP gadgets 的问题 (1) 基于语法的搜寻 : 好处 便于实现并且是一个通用方法 现有 ROP gadget 搜寻工具已经证明了这种方法的正确性, 并且采用了这种方法 基于语法的搜寻 : 问题 不完备 : 不是返回所有合适的 gadgets 返回过多无关的 gadgets 费时 : 需要反复搜寻 浪费 gadgets: 有时 gadgets 很少, 必须合理利用
寻找 ROP gadgets 的问题 (2) 问题 : 将 ebx 复制到 eax 的 gadgets(eax = ebx)? ( 实际上 ) 答案 : 基于语法 ( 正则表达式 ) 寻找收集到的 gadgets mov eax,? -> mov eax, ebx; ret xchg eax,? -> xchg eax, ebx; ret lea eax,? -> lea eax, [ebx]; ret 问题 1: 有其他可用的吗? xchg ebx, eax; ret Imul eax, ebx, 1; ret 落了其他的吗? 问题 2: 寻找这个简单的 gadget 需要多少次查询和努力???
寻找 ROP gadgets 的问题 (2) 问题 3: 仍然寻找将 ebx 拷贝至 eax (eax=ebx) 的 gadgets 哪些语法查询能够寻找到下面的 gadget? 问题 4: 变换栈指针的 gadget ROPME 尝试下列 所有 查询 xchg esp % xchg r32 esp %? esp % 有漏掉的查询吗? leave
其他问题 没有合适的 gadgets 的语义信息 哪个寄存器被修改了? 哪个 Eflags 位被修改了? 栈指针改变了多少字节? 没有工具能够根据需要的语义串接起所有能用的 gadgets 例如 :xor eax, eax; ret + xchg edx, eax; ret edx=0 例如 :mov esi, 0xfffffff8; ret + lea eax, [esi+edx+8]; ret eax=edx
OptiROP 拯救了利用编写者!
OptiROP 的期望 基于语义搜寻 ROP gadgets 基于语义查询而不是基于语法查询 依赖于 gadgets 的语义, 而不是它们的字面 ( 语法 ) 例如 :eax=[ebx] -> mov eax, [ebx] & xchg [ebx], eax 例如 :esi=edi -> lea esi, [edi] & imul esi, edi, 1 允许用户提供条件 : 修改的寄存器, 改变的栈指针的值, 提供寻找到的 gadgets 的详细的语义信息 mov eax, edx; add esp, 0x7c; ret -> 修改的寄存器 :eax, AF, CF, OF, SF, ZF ->esp += 0x80 如果没有原始 gadget(natural gadget), 则将可用的 gadgets 串在一起 挑选合适的 gadgets 串在一起形成需要的 gadget 例如 :xor eax, eax; ret + xchg edx, eax; ret edx = 0 (x86+x86-64) * (Windows PE + MacOSX Mach-O + Linux ELF + Raw binary)
OptiROP vs 其他工具
Gadgets 的种类
OptiROP 的方案 在收集的 gadget 代码的基础上, 生成语义逻辑算式 允许语义查询 : 描述所需 gadget 的高层次的操作 使用 SMT 求解器来匹配 / 搜寻基于 gadgets 的逻辑算式的语义查询 合并 ( 不同 gadgets 的 ) 逻辑算式来生成所需语义的操作
存在的挑战 机器指令 ( 语义 ) 重叠 mov eax, ebx <=> lea eax, [ebx] 指令可能存在多种隐含的副作用 push eax <=> ([esp] = eax; esp -= 4)
解决方案 将机器码标准化为中间代码 (IR) IR 必须简单, 无重叠 IR 语义表达明确, 无歧义 IR 支持静态单赋值形式 (SSA) 以便于生成逻辑算式 将机器码转换为我们选用的 IR 优化得到的 IR 从 IR 的输出得到逻辑算式
LLVM 介绍 LLVM 项目 开源 : http://www.llvm.org 构建编译器的一个框架 LLVM 中间语言 (IR) 有很多优化的模块可以利用
LLVM 模型
LLVM IR 独立于目标架构 类似于 RISC, 三地址代码 基于寄存器的系统, 带有无限数量的虚拟寄存器 寄存器具有类似高级语言的类型 void, float, integer(i1, i32, i64) 指针具有类型 支持静态单赋值形式 (SSA) 基本块有单一的入口和出口 能够从源代码编译到 LLVM IR: LLVM 字节码
LLVM 指令 31 种简单 无重叠的操作码 在 integer 和 float 类型数据上的算术操作 add, sub, mul, div, rem, 位操作 and, or, xor, shl, lshr, ashr 分支指令 低层面的控制流是非结构化的, 于汇编语言类似 分支的目的地址必须显示给出 :( ret, br, switch, 内存访问指令 其他指令 icmp, phi, select, call,
LLVM IR 示例
优化 LLVM 字节码 LLVM 框架的核心组件 优化实施在合并的 / 选取的 LLVM passes 字节码上 收集 / 形象化信息的优化 转化字节码的优化 其他优化 在 LLVM 3.2 中有 182 种 passes 可用
为何选择 LLVM IR? 其 IR 有利于规范化过程 仅使用 LLVM 指令的一个子集 忽略与源代码上层信息有关的指令 处理 IR 输出的轻量级的框架 可以优化由机器码转化为 LLVM IR 这一阶段产生的 LLVM 字节码
机器码转化为 LLVM IR 类似于构建 机器语言 的编译器前端 机器语言的非结构化特性带来的困难 间接分支指令的目标地址 自修改代码 从机器码构包含基本块 (BB) 的建控制流图 (CFG) 将每一个 BB 的所有指令转化为 LLVM IR 参照对应平台 ( 例如 :Intel/AMD) 的 ISA 手册
x86 代码转化为 LLVM IR
LLVM 字节码的优化 常量的传播 (-const prop) (x=14; y=x+8) => (x=14; y=22) 去除失效的存储指令 (-dse) (y=3; ; y=x+1) => ( ; y=x+1) 合并指令 (-inst combine) (y=x+1; z=y+2) => (z=x+3) 简化 CFG(-simplify cfg) 去除孤立的 BB 如果某 BB 仅有一个前置节点, 并且此前置节点仅有一个后置节点, 则将此 BB 融合到其前置节点中 融合进包含一个非条件跳转的 BB
SMT 求解器 基于决策过程的理论验证器 适用于不同理论的逻辑算式 验证一个逻辑算式的可满足性 / 合理性 能够表述计算机程序的行为 如果满足, 能够生成模型实例
Z3 SMT 求解器 构建 Z3 应用的工具和框架 开源项目 : http://z3.codeplex.com 支持 Linux 和 Windows C++, Python 接口 支持 BitVector 理论 模型化算术和逻辑操作 支持 Array 理论 模型化内存访问 支持量词 Exist 和 ForAll
构建逻辑算式 转换算术和数据移动指令 转换控制流
构建逻辑算式 (2) 注意 : 小心逻辑算式的潜在矛盾
构建逻辑算式的步骤 将机器码规范化到 LLVM IR LLVM IR 简单, 无重叠, 无歧义 ( 语义明确 ) 生成逻辑算式时,LLVM 支持静态单赋值 (SSA) 将机器码转换到 LLVM IR 优化得到的 LLVM 字节码 从 LLVM 字节码生成逻辑算式
从 LLVM IR 生成逻辑算式 编写一个 LLVM pass 将字节码转换为 SMT 逻辑算式 按由 LLVM 字节码表示的基本块遍历 CFG 按指令生成算式, 将每条指令转化为 SMT 算式 根据指令来应用 BitVector 或者 Array 理论 BitVector 来模型化算术和逻辑操作 Array 来模型化内存访问
OptiROP 模型 准备阶段 给定可执行二进制文件的情况下由 OptiROP 自动完成 寻找 gadgets, 然后生成并记录 gadget 算式 还记录改变的寄存器和栈指针的变化值 搜寻阶段 用户参与 : 语义查询和筛选条件 从准备阶段收集到的 gadget 代码和算式中寻找 gadgets
准备阶段 (1) 按照传统方式来寻找 gadgets 定位所有返回指令 (RET) 向前翻一些字节 ( 字节数是可以配置的 ), 验证 ( 到 RET 的 ) 原始操作码是否是一个合法的指令序列 记录下所有找到的 gadgets
准备阶段 (2) 阶段 1 中找到的每一个 gadget(asm 格式 ), 生成一个 SMT 算式 规范化 gadget 代码 ( 机器码 -> LLVM 字节码 ) 优化 gadget 代码 (LLVM 字节码 -> 优化的 LLVM 字节码 ) 在规范化 + 优化的代码基础上生成 SMT 算式 ( 优化 LLVM 字节码 -> SMT 算式 ) 对于每一个 gadget, 记录改变的寄存器和栈指针 (ESP/RSP) 的变化值 SMT 算式结尾处寄存器内容的改变, 认为是寄存器改变 通过 SMT 求解器, 根据 gadget 算式计算栈指针的变化值
栈指针变化值 由求解器计算出栈指针最终和初始值之间的差值 ESP_1 ESP 阶段 1: 获取一个 model( 总是被满足的 ) 阶段 2: 带入不同的差异值来求解 另一个 model 可被满足的 :ESP_1-ESP == FIXED -> esp 的改变值是确定 不可满足 :esp 的改变值不确定 ( 依赖于上下文 )
栈指针改变值 - 示例
原始 gadgets(1) Gadgets 大多和寄存器相关 P1: Gadget 将寄存器赋值为另一个寄存器 例 :xor eax, eax; or eax, ebx; ret; -> eax=ebx P2: Gadget 将寄存器设置为一个常量 ( 固定值 ) 例 :mov edi, 0x0; lea eax, [edi]; pop edi; ret -> eax=0 从搜集的 gadget 代码和算式中寻找原始 gadgets(p1 & P2)
原始 gadgets(2) 自然的 原始 gadgets PN1: Gadget 将寄存器设置为另一个寄存器 例 :xor eax, eax; add eax; ebx; ret ->eax=edx PN2: Gadget 将寄存器设置为一个常量 ( 固定值 ) 例 :or ebx, 0xffffffff; xchg eax, ebx; ret -> eax=0xffffffff Free Gadget: 将寄存器设置为从栈顶弹出的值的 POP gadget( 因此能够获得任意常量 ) 例 :push 0x1234 + pop eax; inc ebx; ret; -> eax=0x1234 串起的 原始 gadgets PC1: Gadget 将寄存器设置为另一个寄存器 例 : (lea ecx, [edx]; ret)+(mov eax, edx; ret) -> eax=edx PC2: Gadget 将寄存器设置为一个常量 ( 固定值 ) 例 : (or ebx, 0xffffffff; ret) + (xchg eax, ebx; ret) -> eax=0xffffffff PC3: 衍生为相等关系的 gadget: 从运算的等式衍生而来, 同时需要约束来实现目标 gadget 例 : (imul ecx, [esi], 0x0; ret) +(add ecx, eax; ret) -> ecx=eax
搜寻自然 gadget: PN1 利用求解器来验证两个算式等价
搜寻自然 gadget: PN2 和寻找栈指针改变值的方法类似, 使用 SMT 求解器来寻找一个寄存器的值是否为常量
串起的 gadget 尝试串起自然 gadget, 实现更高层次的 gadget PC1 + PC2: 将简单的 PN1 & PN2 合并在一起 例 : (mov ebx, edx; ret) + (xchg ebx, ecx; ret)+(lea eax, [ecx]; ret) -> eax=edx 例 : (imul ecx, [esi], 0x0; ret) + (xchg ecx, eax; ret) -> eax=0 例 : (#push 0x1234; ret) + (pop ebp; ret) + (xchg ebp, eax; ret)-> eax = 0x1234 PC3: 相等衍生关系的 gadget: 从运算的等式衍生而来, 同时需要约束来实现目标 gadget 例 : (imul ecx, [esi], 0x0; ret) +(add ecx, eax; ret) -> ecx=eax 例 : (#push 0xffffedcc; ret)+(pop edx; ret)+(xor eax, eax; ret)+(sub eax, edx; ret) -> eax=0x1234
搜寻串起的 gadget: PC1+PC2(1) 思路 : 串接 (r2=r1) + (r3=r2) -> r3 = r1 Gadgets 可以是 PN1 或者是 PN2 类型 例 : (mov ebx, edx; ret) + (xchg ebx, ecx; ret) + (lea eax, [ecx]; ret) -> eax = edx; 例 : (imul ecx, [esi], 0x0; ret) + (xchg ecx, eax; ret)- >eax = 0 结合 free register gadget 将寄存器赋予任意值 例 : (# push 0x1234; ret) + (pop ebp; ret) + (xchg ebp, eax; ret) -> eax=0x1234
搜寻串起的 gadget: PC1+PC2(2) 算法 : 构建 PN1 & PN2 gadget 树, 然后找节点间连通路径 ( 图论 ) 例 :eax = {ebx, edx, esi, ebp}; edx={edi, ecx, CONSTANT}: 连通路径 ecx->eax: (edx=ecx) + (eax=edx) -> (eax=ecx) 连通路径 CONSTANT -> eax: (edx=constant)+(eax=edx) -> (eax=constant)
搜寻串起的 gadget: PC3(1) PC3: 相等衍生关系的 gadget: Gadget 衍生自运算的等式 需要约束来实现目标 gadget 例 : (# xor eax, eax; inc eax; ret) + (imul eax, edx; ret) + (add eax, ebx; ret) -> eax = 0x1234 例 : (mov eax, 0x13; ret) + (# push 0x1221; ret) + (pop edx; ret) + (add eax, ebx; ret) -> eax=0x1234
搜寻串起的 gadget: PC3(2) 基于已知的约束 (fixed & free registers) 来生成 SMT 算式, 然后求解 free registers 的一个实例 例 : (# push 0xfffffff8; ret) + (pop esi; inc ebp; ret) + (lea eax, [edx+esi+0x8]; ret) -> eax=edx 例 : (xor eax, eax; ret) + (not eax; ret) + (and eax, edx; ret) + (add eax, ebx; ret) -> eax = edx
LOAD gadget r1 = r2 PN1 或 PC2 或 PC3 合并的 PUSH r1 gadget 和 r2 的 Free register gadget 合并所有方法 (r3=r2) + (r4=0) + (r1=r4+r3) -> r1 = r2 r1 = CONSTANT PN2 或 PC2 或 PC3 合并所有方法 (r3=0x10) + (r2=0x38) + (r1=r2-r3) -> r1 = 0x28 r1 = [r2] 将为寄存器设置为内存地址的 gadget 和读内存值的 gadget 串在一起 (r3 = r2) + (r4 = [r3]) + (r1 = r4) -> r1 = [r2]
STORE gadget 查询 [r1] = r2 查询 [CONSTANT] = r2 和 LOAD gadget 相似 : 使用 / 串接原始 gadgets
ADJUST gadget r1 += CONSTANT (r += 8) + (r += 8) + (r += 1) -> r += 17 (add eax, 8; ret) + (add eax, 8; ret) + (inc eax; ret) -> eax += 17 寻找所有某特定寄存器相关的 fixed register gadget 用 SMT 求解器求解使得结果是 CONSTANT 的一个线性等式实例 尝试获取线性变量的最小值 算式 :a1*8 + a2*1 == 17 & (a1 + a2) = MIN -> a1 = 2, a2=1
CALL gadget call r 将 (r = r1) + (CALL r1) 串接 call [r] 将 (r = r1) + (CALL [r1]) 串接 call [CONSTANT] 将 (r1 = CONSTANT) + (CALL [r1]) 串接
现场演示
OptiROP 用到的性能优化 快速路径优化 快速路径优先执行, 缓慢路径后执行 (x3) 在算式无法推导时, 才使用 SMT 求解器求解 缓存处理过的算式, 避免重新运算 (x2) 并行搜索 (x8) 多线程, 每一个线程独立对算式进行验证 尽可能的进行预运算 (x10) 改变的寄存器, 栈指针变量, 取固定值的寄存器, 取任意值的寄存器 在选择查询中运用代码切片 (x2)
代码切片 仅考虑影响关键位置取值的指令 在相关寄存器上实施切片能够减少需要验证的算式的数量 切片是在 gadget 的算式上完成的, 而不是在前面的步骤中
OptiROP 的实现 Web + 命令行接口 将 x86 代码转化为 LLVM IR 的框架 从 LLVM 中间代码转化为 SMT 算式的框架 在 SMT 算式上实施代码切片的框架 支持独立的反汇编引擎来反汇编机器码 ( 规范化阶段 ) (x86+x86-64) * (Windows PE + MacOSX Mach-O + Linux ELF + Raw binary) 使用 Z3 求解器来处理逻辑算式 ( 谓词 ) 用 Python & C++ 实现
未来工作 更多串接 gadgets 的方法 更高层次的 gadgets 完全基于编译器的实现 支持其他硬件平台 : ARM ( 其他?) 将 OptiROP 部署为一个独立的利用编写工具集 未来开放 ( 在修正 bug/ 代码之后 ) 关注 http://optirop.coseinc.com
总结 OptiROP 是一种寻找 ROP gadgets 的创新方法 支持自然和简便的语义问题 用户提供的条件能够过滤掉不需要的 gadgets 在没有自然 gadgets 的情况下, 会串接所选的 gadgets (x86+x86-64) * (Windows PE + MacOSX Mach-O + Linux ELF) 基于命令行和网站的工具 内部使用编译技术和 SMT 求解器 将会免费公布
OptiROP vs 其他
参考
提问 & 回答