阅读推荐 2022-08-01 JIGSAW

admin 2022年8月2日11:00:49评论99 views字数 4337阅读14分27秒阅读模式

八月第一天为大家推荐的是来自加州大学河滨分校宋程昱研究组尹恒研究组联合投稿的关于自动化测试的工作JIGSAW: Efficient and Scalable Path Constraints Fuzzing,目前该工作已发表在IEEE S&P 2022。

阅读推荐 2022-08-01 JIGSAW

工作的开始

影响fuzzer性能的一个重要指标是吞吐量,比如每秒钟可以测试多少个输入?一些研究人员甚至认为吞吐量是最重要的指标。2018年,Brandon Falk发表了一个叫向量化模拟(vectorized emulation)的技巧,实现了fuzzing吞吐量的重大突破。通过利用数据并行化,这个方法能够在Xeon Phi 7210处理器上同时测试4096个输入,从而将OpenBSD DHCP客户端的fuzzing吞吐量提高到每秒钟5百万个输入。这样做的结果是,仅仅通过一个简单的byte flipper, Branch Falk写的fuzzer能够找到一些比较复杂的漏洞比如说CVE-2018-8206 [1]。

作者着迷于这个方法,直到有一天,灵光乍现,一个想法突然冒出来:为什么不直接fuzz路径约束(path constraints)呢?


益处

从某种意义上,路径约束可以看成与目标分支相关的一段程序切片。如果把路径约束转换为DNF(disjunctive norm form)形式,那么每一个子条件可以看成一些关系运算的集合,集合中的每个关系运算通过逻辑与(AND)相连接,而每个关系运算可以看成一个不含分支的纯函数(pure and straight-line function)。比如这个写成DNF形式的路径约束:(x > 5 && y < 10) || (x < 1 && y > 100), 它的第一个子条件(x>5 && y<10) 由两个关系运算组成 (x>5和y<10), 每个关系运算(如x > 5)都可以看成一个不含分支的函数。Fuzz路径约束(纯函数的集合)相比fuzz整个待测程序有以下好处:

  • 首先,很显然,调用简单的函数比运行整个程序快几个数量级。

  • 第二,当测试这些函数的时候,作者通过寄存器和内存传递输入。而当作者测试整个程序时,通过文件传递输入,前者规避了文件系统的瓶颈,比后者快很多。

  • 第三,这些函数不更改全局状态,因此运行时没有side effects。当作者在这些函数上测试新的输入的时候,不需要重置任何状态(比如使用snapshot或者forking)。同理,当在多核处理器上测试这些函数的时候,也不需要担心数据竞争和同步。

  • 最后,因为这些函数没有分支,于是可以方便地利用指令级的并行运算来进一步提升性能(比如利用SIMD指令)。



技术细节

因为作者已经有了一个基于LLVM IR的快速约束收集器SymSan [2], 作者决定先使用LLVM的即时编译(JIT)引擎将路径约束编译成原生函数,然后再fuzz这些函数。使用LLVM即时编译引擎的一个坏处是它非常慢,如果不做任何优化,那么大部分时间都将被消耗在即时编译上。


1.  代码缓存 

一个自然的想法是将已经编译过的函数缓存起来,这样就不用重复编译相同的路径约束了。但是作者发现如果直接使用整个约束作为key去索引缓存,缓存的命中率不高。为了解决这个问题,作者注意到,很多约束尽管不一样,但是实际上在进行同样的比较操作(比如a>10, b>20, 30>c)。因此,只需要把符号操作数和常数操作数作为函数参数,就可以用同样的函数去求解这些看似不同的路径约束。比如下面这个函数就可以用来求解a > 10, b > 20或是30 > c

gt(x, y) { return y – x;}

下表显示了不同的缓存策略的性能效果(求解20,000个来自readelf程序的路径约束)

阅读推荐 2022-08-01 JIGSAW

图片来源:https://chengyusong.github.io/fuzzing/2022/05/03/jigsaw.html


2.  Fuzzing 算法

接下来的问题是,如何fuzz/求解路径依赖呢?根据FuzzySat这个工作的研究,有很多启发式算法可以用来fuzz/求解路径约束。在JIGSAW中,作者使用了Angora的梯度下降搜索算法。这主要是基于两个原因:

  1. 梯度下降算法足够通用,可以用来处理大部分约束。

  2. 使用这个算法不需要存储中间结果(也就是,不需要维护一个输入队列)。

使用这个搜索算法非常直接,作者只需要把关系运算换成一个损失函数就可以了( ϵ=1)。

阅读推荐 2022-08-01 JIGSAW

图片来源:https://chengyusong.github.io/fuzzing/2022/05/03/jigsaw.html


需要注意的是,梯度下降搜索不是最有效率的算法。根据FuzzySat这篇文章的实验结果,RedQueen用到的input-to-state推理可能更快。但是梯度下降更加通用也更容易实现。


3. 进一步提高可扩展性

到这一步作者已经有了一个简单fuzzer用来求解路径约束。为了让fuzzer在多核场景下的扩展性更好,作者进行了一些优化来减少可能的锁竞争。首先,每个线程都使用自己的LLVM即时编译引擎,避免了资源共享。其次,作者使用了无锁队列来分配求解任务。第三,作者使用了无锁哈希表来实现代码缓存。最后,作者使用了Google的TCMalloc以减少malloc和free带来的底层锁竞争。


性能

符号执行的性能

JIGSAW能提高Fuzzer的性能吗?因为JIGSAW需要收集和求解路径约束,这个问题实际上是,JIGSAW能提高符号执行,具体的说,concolic执行的性能吗?为了回答这个问题,作者做了与SymCC类似的实验。首先,为了更好的实验复现性,作者采用了NEUZZ这个工作中使用的种子集, 然后对于每一个种子输入文件,作者让参加比较的每个Fuzzer/符号执行器去翻转在执行路径上遇到的符号分支。作者记录了每个Fuzzer执行这个任务所需要的时间,结果如下:

阅读推荐 2022-08-01 JIGSAW

图片来源:https://chengyusong.github.io/fuzzing/2022/05/03/jigsaw.html


在这里,JIGSAW和Z3-10s(10s是Z3求解器超时设定)使用的都是作者的SymSan约束收集器,SymCC也使用Z3作为求解器,超时也设置为10s。Fuzzolic使用的是FuzzySat作为约束求解器。JIGSAW和Angora的比较是最有意思的,因为两者都是使用梯度下降算法求解约束,只不过JIGSAW是在编译过的函数上执行算法,而Angora是在整个待测程序上执行算法。从结果可以明显地看出JIGSAW执行的效率是最高的,它比其他的符号执行器和Fuzzer都要快10倍以上。那么,JIGSAW的代码覆盖怎么样呢?作者使用SanitizerCoverage测量了各个工具的BasicBlock覆盖,结果如下:


阅读推荐 2022-08-01 JIGSAW

图片来源:https://chengyusong.github.io/fuzzing/2022/05/03/jigsaw.html


从代码覆盖结果可以看出,JIGSAW比Z3的求解能力略逊一筹,作者表示解决这个问题是他们接下来的工作之一。


约束求解的性能

JIGSAW可以被看成是一个约束求解器, 一个自然的问题是,跟其他约束求解器相比,它的性能怎么样呢?为了回答这个问题,作者收集了来自14个程序的大约一千万条路径约束,并统计了各个求解器的求解时间。求解时间分布如下图所示:


阅读推荐 2022-08-01 JIGSAW


作者比较的求解器包括最流行的Z3, KLEE中使用的STP, 在2020年SMT Competition中获奖的Bitwuzla, 以及Yices2。因为JIGSAW使用的是搜索的办法求解约束,同时还比较了Bitwuzla的本地搜索模式(Bitwuzla-LS)。从结果可以看出,对于可满足的路径约束(SAT queries),JIGSAW的性能比其他求解器有明显的优势。对于不可满足的路径约束(UNSAT queries),JIGSAW的性能不佳。这是因为JIGSAW使用的梯度下降搜索算法无法判断约束是否满足,于是它只能不停的尝试搜索直到超时结束。这个问题能够通过让JIGSAW使用更高级的搜索算法得以解决。


作者在这个实验中发现,绝大部分JIGSAW能够求解的约束,都能够在1000次迭代内找到答案,于是作者将JIGSAW的超时设置为1000次迭代,并比较了各个约束求解器的求解速度,结果如下:


阅读推荐 2022-08-01 JIGSAW


在这个实验中,为了公平起见,作者将Z3的超时设置为50ms。这是因为Z3在50ms下有跟JIGSAW-1K相类似的求解能力。同理,Bitwuzla的超时被设置为6ms,而Bitwuzla-LS的超时被设置为100K次迭代。由此可以看出,JIGSAW的求解速度跟其他求解器相比都有明显优势。


Fuzzing性能

作者把SymSan+JIGSAW组成的高性能符号执行器和AFL++进行了基于种子交换的简单配对,并把得到的混合Fuzzer提交给Google的Fuzzbench服务进行了测试。打分结果显示,在average normalized score和average rank两个指标下,JIGSAW都取得了最高的排名。


阅读推荐 2022-08-01 JIGSAW

图片来源:https://anonysp2022.github.io/


下一步工作计划:

作者的短期目标是让JIGSAW使用更高级的搜索算法并支持更多的约束类型,长期目标是让SymSan+JIGSAW作为解决concolic execution中遇到诸多瓶颈问题(比如路径爆炸问题)的一个基础。



论文下载:https://www.cs.ucr.edu/~csong/oakland22-jigsaw.pdf

项目开源:https://github.com/R-Fuzz/jigsaw

p.s 作者目前开源的是C++版本,作者说Rust版本需要做一些清理工作后放出来

再p.s 本文部分内容翻译自宋程昱老师的blog(略有删改) [3]



参考链接:

  1.  CVE-2018-8206

    link: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-8206

  2. SymSan: Time and Space Efficient Concolic Execution via Dynamic Data-Flow Analysis @USENIX 2022

    link:https://www.cs.ucr.edu/~csong/sec22-symsan.pdf

  3. JIGSAW: Fuzzing Path Constraints

    link:https://chengyusong.github.io/fuzzing/2022/05/03/jigsaw.html



原文始发于微信公众号(安全研究GoSSIP):阅读推荐 2022-08-01 JIGSAW

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年8月2日11:00:49
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   阅读推荐 2022-08-01 JIGSAWhttp://cn-sec.com/archives/1215679.html

发表评论

匿名网友 填写信息