Hybrid fuzzing学习笔记

前言

Hybrid fuzzing(混合模糊测试)说白了就是fuzzing+符号执行。fuzzing产生的输入质量低难以触发复杂路径,符号执行能产生高质量输入但是overhead高。因此就产生了将这两种方式结合的技术–Hybrid fuzzing。注意这里的符号执行不是symbolic execution,而是concolic symbolic,或者说动态符号执行。

符号执行

符号执行原理和发展历程看这篇就差不多,klee和angr可以再去读一下论文。

符号执行,我个人理解分为source-based和binary-only两种,klee、symcc属于source-based,可以从源码层面编译成ir时插桩,QSYM、SymQEMU、Angr这种属于binary-only。看百度的一篇blog将符号执行分成了IR-level、Instruction-level和Compilation based三种,比如symcc、symqemu就属于Compilation based。但是对于工作/挖洞来说,binary-only这种直接对binary进行符号执行的应用更广泛,比如各种大型软件中的so等。

-w1060

binary-only的通常用qemu来模拟执行,过程大概是把binary翻译成TGC ops,然后对TGC ops插桩或处理,再解释执行。当然也有QSYM这种直接动态插桩的。之前fuzz so是用的AFL的qemu-mode,现在看的话还有SymQEMU或者QSYM可以用。但是还没有实际测试效果,之前qemu-mode fuzz的结果不太好,感觉有机会可以测试下这个。

Fuzzing

fuzzing看的少一点,也就看了AFL和Hawkeye这种directed-fuzz,比较感兴趣的是coverage统计策略和变异策略。

AFL的coverage是通过一个bitmap来实现的,其实本质上就是个map,然后加一个bucket统计每个block命中次数,达到一定数量就不会对这个block访问次数很敏感。变异策略的话很多文章,就不说了。

还有一个Hawkeye,是directed-fuzz,改进的afl-go,简单来说就是指定一个sink,他会从main开始朝着sink移动。首先通过通过cg和cfg收集信息计算一个block distance,然后插桩记录需要的source到sink的trace。变异时,seed的trace和所需trace相似度高的变异优先级高。很多蛮有意思的细节可以看下。

Paper summary

KLEE:Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs

基于LLVM,从LLVM IR层面做分析收集信息,求解器使用STP。klee解释IR执行,解释过程中收集符号信息,所以klee不依赖插桩。
主要策略有:

  1. 记录registers, stack and heap objects
  2. 对路径爆炸问题,先存储状态,然后根据所需sink去求解所需表达式,计算结果也是可共享的。条件分支如果都有可能走则存储两个状态。这里可能造成路径爆炸,不过这里klee用了写时复制,存储state会节约很多空间。
  3. 对于状态调度/选择,比如刚才的条件分支的两个状态,随机对分支路径进行执行。同时还有启发式算法,选择权重高的分支进行调度。
  4. 对于间接引用,当一个被间接引用的指针p可以指向n个目标,KLEE将当前状态克隆n次。(太草了)
  5. 查询优化:在到达STP前简化表达式并减少查询。简化表达式可以加快求解、减小内存开销并提高查询缓存的命中率。查询优化的主要方法:1.add等表达式重写 2.约束集简化 3.隐含的值具体化 4.约束独立 5.缓存取反值(?)
  6. 重写了40多个系统调用,处理了了一些符号数值丢失的问题
    待解决的问题:
  7. 路径爆炸
  8. 间接调用

https://zhuanlan.zhihu.com/p/350222671
https://blog.csdn.net/cutedog2012/article/details/79537942

Angr

博大精深,真要研究还是要看源码的,太难了

随便说一点浅显的东西,一个Binary Analysis Framework,将binary转为VEX IR,更多的是用它来做约束求解,比如driller。也有一些CTF题目用angr做求解,参考之前的angr学习文章。

QSYM

binary-only,汇编层面动态插桩,省去了反汇编到IR那步,由Pin解释执行插桩好的汇编,感觉思路确实很巧,但是过程中可能有很多很难得工作这个还不理解。

整体架构:

SymCC

source-based,编译时插桩,具体todo

SymQEMU: Compilation-based symbolic execution for binaries

binary-only,基于QEMU,在TCG ops上插桩收集符号信息。symqemu流程是首先将binary翻译成TCG ops,然后对ops插桩,再编译成机器码执行。这样就少了angr和s2e中将binary反汇编成VEX IR或者LLVM bitcode那步,就会快很多。

与之前工作的比较:

整体架构:

Angora

LLVM Pass静态插桩,结合DataFlowSanitizer动态污点分析,符号执行用梯度下降求解,不用约束器了所以速度快很多,这是最大的卖点。
还有个byte-level的taint tracking也很牛,把输入的每个字节和到达sink的字节做映射,这样就能方便的追踪sink和source的关系。这里有个有意思的东西,使用了roBDD(类似字典树)的数据结构存bit vector,这个确实很巧

1

Proudly powered by Hexo and Theme by Hacker
© 2021 LFY