【技术分享】浅谈angr的缓解状态爆炸策略

admin 2022年4月13日23:00:25安全文章评论23 views9567字阅读31分53秒阅读模式

【技术分享】浅谈angr的缓解状态爆炸策略

 

【技术分享】浅谈angr的缓解状态爆炸策略

前言

angr是有名的符号执行工具。众所周知,符号执行最大的问题就是状态爆炸。因此,angr中也内置了很多缓解符号执行的策略。本文主要介绍angr里的一些内置机制是如何缓解状态爆炸的。

 

【技术分享】浅谈angr的缓解状态爆炸策略

概述

据我对angr的了解,angr缓解状态爆炸的策略约有以下几种:

(1)simProcedure:重写一些可能导致状态爆炸的函数。
(2)veritesting:动态符号执行和静态符号执行的结合
(3)Lazy Solve:跳过不必要的函数
(4)Symbion:具体执行和符号执行的结合

simProcedure

为了使得符号执行实践性更强,angr用python写的summary替换了库函数。这些summary成为Simprocedures。Simprocedures可以缓解路径爆炸,反过来也可能引入路径爆炸。比如,strlen的参数是符号字符串。

但是,angr的simprocedure并不完善。如果angr出现了预期以外的行为,可能是由于不完整的simprocedure导致的。为此,官网给出了几种解决方案:

(1)禁用simprocedure(虽然也有可能引入路径爆炸,需要限制下函数的输入)
(2)写一个hook来代替其中的几个simprocedure
(3)修复simprocedure

下面介绍一个simprocedure的例子

from angr import Project,SimProcedureproject = Project("example/fauxware/fauxware")class BugFree(SimProcedure):    def run(self,argc,argv):        print("Program running with argc=%s and argv=%s" %(argc,argv))        return 0# 将二进制中的main函数替换为bug free函数project.hook_symbol("main",BugFree())simgr = project.factory.simulation_manager()simgr.run()

当程序执行到main函数时,会去执行BugFree函数,就只会打印一个信息,然后返回。

当进入函数时,参数的值会从哪里进来呢?不管有多少个参数,只要定义个run函数,simprocedure就通过调用约定,自动地提取程序状态里的参数给你。返回值也是一样的,run函数的返回值也会通过调用约定放到状态里的。

事实上,最经常使用simprocedure的地方是用来替换库函数。

关于数据类型,你可能会发现run函数打印出了SAO BV64 0xSTUFF的类。这个是SimActionObject。这个只是bitvector的wrapper。他会在simprocedure里追踪。(在静态分析里很有用)

另外,也许你还会注意到run函数返回的是python的int 0,这个会被自动处理为word大小的bitvector。你可以返回一个普通的数字或者一个SimActionObject。

当你想要去写一个procedure去处理浮点数时,你需要手动指定调用约定。只需要为hook提供一个cc(调用约定)。

cc = project.factory.cc_from_arg_kinds((True,True),ret_fp=True)project.hook(address, ProcedureClass(cc=mycc))

如何退出SimProcedure呢?我们已经知道了最简单的方法去做这个,就是从run函数返回。实际上,从run函数返回是调用了self.ret(value)。self.ret()是一个知道如何从一个函数返回的函数。

SimProcedures可使用许多不同的函数:

  • ret(expr):从函数返回

  • jump(addr):跳到二进制中的地址

  • exit(code):终止程序

  • call(addr,args,continue_at):在二进制中调用

  • inline_call(procedure,*args):调用SimProcedure(inline)并返回结果

如果要在SimProcedure加个条件分支的话,需要直接在SimSuccessors那边的节点上添加。

self.successors.add_successor(state,addr,guard,jumpkind)

如果我们调用二进制中的一个函数,并且在SimProcedure后重新执行呢?有个叫SimProcedure Continuation的框架可以实现这个。当你使用self.call(addr,args,continue_at) ,其中addr是你需要call的地址,args是需要调用的函数的参数的元组,continue_at是另外一个simProcedure的方法。

下面来看看一个例子,这个例子是将所有共享库初始化的例子,来实现一个full_init_state。initializers是一个初始化队列。每次从里头去一个共享库的地址,然后执行self.call。如果初始化队列为空,则跳转到程序的entry执行。

class LinuxLoader(angr.SimProcedure):    NO_RET = True    IS_FUNCTION = True    local_vars = ('initializers',)
def run(self): self.initializers = self.project.loader.initializers self.run_initializer()
def run_initializer(self): if len(self.initializers) == 0: self.project._simos.set_entry_register_values(self.state) self.jump(self.project.entry) else: addr = self.initializers[0] self.initializers = self.initializers[1:] self.call(addr, (self.state.posix.argc, self.state.posix.argv, self.state.posix.environ), 'run_initializer')

hook symbols,可以使用符号表直接来进行hook。比如,要替换rand函数为一个具体的列表值,可以用以下代码实现。

>>> class NotVeryRand(SimProcedure):...     def run(self, return_values=None):...         rand_idx = self.state.globals.get('rand_idx', 0) % len(return_values)...         out = return_values[rand_idx]...         self.state.globals['rand_idx'] = rand_idx + 1...         return out
>>> project.hook_symbol('rand', NotVeryRand(return_values=[413, 612, 1025, 1111]))

user hooks,除了hook 库函数以外,也可以hook二进制中的普通函数。例子如下,0x1234是函数的地址。length参数控制程序的控制流。在函数执行完这个例子后,下一步就是从hooked的地址的5个字节后面开始执行。

>>> @project.hook(0x1234, length=5)... def set_rax(state):...     state.regs.rax = 1

Veritesting

Veritesting方法来源于论文Enhancing Symbolic Execution with veritesting,论文作者是mayhem的团队。

论文链接见此:https://dl.acm.org/doi/pdf/10.1145/2927924

AngrCTF的第12个挑战,就是关于如何使用angr的veritesting模式来缓解路径爆炸。只需要在新建simulation_manager对象时,加上veritesting的参数就可以了。

simulation = project.factory.simgr(initial_state, veritesting=True)

简单说下这个veritesting的原理。

从高层面来说,有两种符号执行,一种是动态符号执行(Dynamic Symbolic Execution,简称DSE),另一种是静态符号执行(Static Symbolic Execution,简称SSE)。动态符号执行会去执行程序然后为每一条路径生成一个表达式。而静态符号执行将程序转换为表达式,每个表达式都表示任意条路径的属性。基于路径的DSE在生成表达式上引入了很多的开销,然而生成的表达式很容易求解。而SSE虽然生成表达式容易,但是表达式难求解。veritesting就是在这二者中做权衡,使得能够在引入低开销的同时,生成较易求解的表达式。

先来看个简单的例子,下面的7行代码中,有着2^100次条可能的执行路径。每条路径都要DSE单独地去分析,从而使得实现100%的覆盖率是不太现实的。实际上,只要两个测试样例,就可以达到100%的路径覆盖率。一个包含75个B的字符串和一个没有B的字符串。然而,在2的100次方状态空间里找到这两个测试样例是很难的。

【技术分享】浅谈angr的缓解状态爆炸策略

veritest只要47s就能到达bug函数,而其他的符号执行工具比如klee,S2E,Mayhem使用状态合并的策略跑1个小时,都没跑完。Veritest从DSE开始,一旦遇到一些简单的代码,就切换到SSE的模式。简单的代码指的是不含系统调用,间接跳转或者其他很难精确推断的语句。在SSE模式下,首先动态恢复控制流图,找到SSE容易分析的语句和难以分析的语句。然后SSE算法推断出从易分析的节点到难分析节点路径的影响。最后,Veritesting切换回DSE模式去处理静态不好解决的情况。

lazy

这个思路有点像chopped symbolic execution论文里提到的。论文地址:https://dl.acm.org/doi/abs/10.1145/3180155.3180251

论文里是在klee实现的,开源于:https://github.com/davidtr1037/chopper

在angr里也有类似的操作,只需要设置状态为LAZY_SOLVES就可以了。

s = proj.factory.entry_state(add_options={angr.options.LAZY_SOLVES})

依然简单说下原理。拿论文中的例子,下面的程序是libtasn1库里的代码片段。第8行的get_length()函数会导致堆溢出。整体是一个while循环。这个函数会去用get_length去获取当前数据的长度。get_length函数会去扫描输入字符串,并且转为ASN.1 域。然后注意14行,会去递归地迭代执行。或者触发第11行的append_value函数。这个函数会在AST上创建节点。然后还会去多次扫描输入的字符串,检查多次元素,并分配内存给节点。这里会产生状态爆炸主要是由于多次的嵌套调用,只符号执行函数get_length(get_length的参数为长度为n的字符串),会导致4*n条不同路径。函数append_value会调用多次求解器,同样也会影响符号执行引擎的效率。最后导致无法发现第8行的堆溢出漏洞。

【技术分享】浅谈angr的缓解状态爆炸策略

lazy solves就是应对这种情况而诞生的。它的核心思想是执行过程中的大部分函数和漏洞实际上并不相关。就好比这个程序里,漏洞是由于21行的剩下字节的错误更新导致当调用get_length时会有内存越界读。也就是说这个bug很构造ASN.1表示的那些函数没啥关系(比如append_value)。因此,我们可以快速的跳过这些不相关的函数。

Lazy Solves策略实际上是在符号执行过程中先跳过函数调用。如果遇到的漏洞点和前面的函数有依赖关系,再会去求解相关的函数的依赖。由于漏洞只和一小部分函数有关联,所以这种策略在一定程度上缓解了状态爆炸。

Symbion

Symbion来自论文:SYMBION: Interleaving Symbolic with Concrete Execution

他的核心思想主要是在具体执行和符号执行相互切换的一个过程。他的应用场景特别适合:假设只需要符号执行一个程序的特定函数,但是到这个函数前有很多初始化的步骤想要跳过。因为这些步骤和分析无关或者angr不能很合适地模拟。比如,程序是运行在一个嵌入式系统上,而你有访问debug接口的权限,但不太容易复现硬件的环境。

这里的例子是angr博客里的,下面的代码有四个恶意行为。所有这些行为依赖于硬编码的配置。我们可以在地址0x400cd6看到配置的使用方法:二进制里第一个做决定的点。

【技术分享】浅谈angr的缓解状态爆炸策略

我们的目标是要去分析二进制的恶意行为以及如何触发它们。我们可以看到第二个payload在基本块400d6a处,我们如何到达它?还有基本块0x400d99呢?这就是符号执行要做的事情。

思路是让binary自动unpack,并且具体执行到0x400cd6的地方,然后同步状态到angr,然后定义一个符号变量,去符号化探索后面的程序。

然而,这个二进制是packed的,并且内存会被unpacking 进程覆盖。软件的断点都会被覆盖。所以我们手动逆向二进制,并且确定了我们可以从程序的开始运行到0x85b853,to have a new stub available at 0x45b97f。最终就等待4个断点在那个地址命中,我们就可以获取在400cd6的unpacked code了。

下面的代码是官方给出的示例。我也试着跑了一下,但由于avatar2和某些angr的库不兼容,最后跑出来的结果和github里的某个issue一样。

import subprocessimport osimport noseimport avatar2 as avatar2
import angrimport claripyfrom angr_targets import AvatarGDBConcreteTarget

# First set everything upbinary_x64 = os.path.join(os.path.dirname(os.path.realpath(__file__)), os.path.join('..', '..', 'binaries', 'tests','x86_64', 'packed_elf64'))
# Spawning of the gdbserver analysis environment(这里GDB_SERVER_IP和PORT应该要自己设置)print("gdbserver %s:%s %s" % (GDB_SERVER_IP,GDB_SERVER_PORT,binary_x64))subprocess.Popen("gdbserver %s:%s %s" % (GDB_SERVER_IP,GDB_SERVER_PORT,binary_x64), stdout=subprocess.PIPE, stderr=subprocess.PIPE, shell=True)
# Instantiation of the AvatarGDBConcreteTargetavatar_gdb = AvatarGDBConcreteTarget(avatar2.archs.x86.X86_64, GDB_SERVER_IP, GDB_SERVER_PORT)
# Creation of the project with the new attributes 'concrete_target'p = angr.Project(binary_x64, concrete_target=avatar_gdb, use_sim_procedures=True)# 从entry开始使用具体执行entry_state = p.factory.entry_state()entry_state.options.add(angr.options.SYMBION_SYNC_CLE)entry_state.options.add(angr.options.SYMBION_KEEP_STUBS_ON_SYNC)
simgr = p.factory.simgr(state)
## Now, let's the binary unpack itself(concrete execution)simgr.use_technique(angr.exploration_techniques.Symbion(find=[0x85b853]))exploration = simgr.run()new_concrete_state = exploration.stashes['found'][0]
# 为啥这样可以找到unpack code ?confusing# Hit the new stub 4 times before having our unpacked code at 0x400cd6for i in xrange(0,4): simgr = p.factory.simgr(new_concrete_state) simgr.use_technique(angr.exploration_techniques.Symbion(find=[0x85b853])) exploration = simgr.run() new_concrete_state = exploration.stashes['found'][0]
## Reaching the first decision point#获取了unpack code后,开始去找符号执行开始的地方simgr = p.factory.simgr(new_concrete_state)simgr.use_technique(angr.exploration_techniques.Symbion(find=[0x400cd6])exploration = simgr.run()new_concrete_state = exploration.stashes['found'][0]# 定义符号化的参数,并把符号化的变量存到相应的内存区域# Declaring a symbolic bufferarg0 = claripy.BVS('arg0', 8*32)
# The address of the symbolic buffer would be the one of the# hardcoded malware configurationsymbolic_buffer_address = new_concrete_state.regs.rbp-0xc0
# Setting the symbolic buffer in memory!new_concrete_state.memory.store(symbolic_buffer_address, arg0) simgr = p.factory.simgr(new_concrete_state)
print("[2]Symbolically executing binary to find dropping of second stage" + "[ address: " + hex(DROP_STAGE2_V2) + " ]")# 符号执行# Symbolically explore the malware to find a specific behavior by avoiding# evasive behaviorsexploration = simgr.explore(find=DROP_STAGE2_V2, avoid=[DROP_STAGE2_V1, VENV_DETECTED, FAKE_CC ])# Get our synchronized state back!new_symbolic_state = exploration.stashes['found'][0] print("[3]Executing binary concretely with solution found until the end " +hex(BINARY_EXECUTION_END))
simgr = p.factory.simgr(new_symbolic_state)# 具体执行到结尾# Concretizing the solution to reach the interesting behavior in the memory# of the concrete process and resume until the end of the execution.simgr.use_technique(angr.exploration_techniques.Symbion(find=[BINARY_EXECUTION_END], memory_concretize = [(symbolic_buffer_address,arg0)], register_concretize=[]))
exploration = simgr.run()# 求解的结果new_concrete_state = exploration.stashes['found'][0]

总的来说,代码可以划分为以下几个步骤:

(1)从entry开始具体执行到0x85b853。(困惑这里的0x85b853是啥?)

(2)连续具体执行四次,终点依然是0x85b853(获取unpacked code?)

(3)具体执行到0x400dc6(决策点的位置)

(4) 从0x400dc6开始符号执行到DROP_STAGE2_V2

(5)再具体执行到结尾,同时把符号化的地址具体化。

 

【技术分享】浅谈angr的缓解状态爆炸策略

总结

angr里可能还有其他缓解状态爆炸的思路,比如driller,这里我就没有展开来讲。也可以发现,在缓解状态爆炸的路上,通常都是结合了多种方法来实现的。在各种程序分析技术中切换,或许是未来符号执行发展的路线。

参考资料

1、Simprocedure:(1)angr CTF:http://angr.oregonctf.org/
2、Veritesting(1)论文:https://dl.acm.org/doi/pdf/10.1145/2927924
(2)angr CTF 第12个挑战:https://ycdxsb.cn/eefc86dd.html
3、Lazy Solve(1)论文:https://dl.acm.org/doi/abs/10.1145/3180155.3180251
(2)其他开源工具:https://github.com/davidtr1037/chopper
4、Symbion相关(1)官方文档:https://docs.angr.io/advanced-topics/symbion
(2)论文:https://ieeexplore.ieee.org/abstract/document/9162164
(3)博客:http://angr.io/blog/angr_symbion/
(点击“阅读原文”查看链接)【技术分享】浅谈angr的缓解状态爆炸策略


- 结尾 -
精彩推荐
系统故障致12万+Coinbase用户深陷恐慌?
【技术分享】源码解析angr的模拟执行
【技术分享】二进制角度构造Java反序列化Payload
【技术分享】如何高效地捡漏反序列化利用链?
【技术分享】浅谈angr的缓解状态爆炸策略
戳“阅读原文”查看更多内容

本文始发于微信公众号(安全客):【技术分享】浅谈angr的缓解状态爆炸策略

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年4月13日23:00:25
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  【技术分享】浅谈angr的缓解状态爆炸策略 http://cn-sec.com/archives/533910.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: