Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Muzz: Thread-aware Grey-box Fuzzing for Effective Bug Hunting in Multithreaded Programs

作者:Hongxu Chen^4^ ^1^, Shengjian Guo^2^, Yinxing Xue^4^, Yulei Sui^3^, Cen Zhang^1^, Yuekang Li^1^, Haijun Wang^5^, and Yang Liu^1^

单位:^1^Nanyang Technological University, ^2^Baidu Security, ^3^University of Technology Sydney, ^4^University of Science and Technology of China, and ^5^Ant Financial Services Group

出处:USENIX Security ‘20

原文:https://www.usenix.org/system/files/sec20-chen-hongxu.pdf

Abstract

灰盒模糊测试已经被广泛应用在现实存在的软件系统上并发现了成千上万的漏洞,这一切都要归功于其轻量级的代码插桩、快速的代码覆盖率反馈以及动态的模糊测试种子调整策略。然而,直接将灰盒模糊测试应用在输入依赖的多线程程序上的效果可能很差,这是因为在现实中多线程相关的错误通常都隐藏在复杂的程序控制流中。同时,现有的灰盒模糊测试也并不关心可能影响多线程程序执行状态的线程交错。

因此,作者提出了一个新的面向多线程程序的灰盒模糊测试框架Muzz,其采用了三种线程敏感的代码插桩,包括代码覆盖率插桩、线程上下文插桩以及线程调度插桩。在模糊测试的过程中,这些插桩产生的运行时反馈可以帮助Muzz探索线程交错相关的多线程程序执行状态。作者在12个现实存在的多线程程序上评估了Muzz。评估结果表明,Muzz在生成多线程相关的模糊测试种子以及检测并发漏洞与错误这两方面的表现都优于AFL。其中,Muzz一共发现了8个新的并发漏洞与19个新的并发错误。

1 Introduction

与顺序程序相比,多线程程序更容易包含严重的代码缺陷。一方面,线程交错的不确定性可能导致例如数据竞争与死锁的并发错误。这些错误可能导致程序产生异常结果或者被意外挂起。另一方面,一些在特定程序输入与线程交错的前提下产生的错误可能导致并发漏洞,造成例如内存破坏与信息泄漏的后果。

现有的灰盒模糊测试并不能很好地检测输入依赖的用户态多线程程序中包含的并发错误与漏洞。因此,作者提出了一个专用的灰盒模糊测试框架Muzz,其通过探索程序输入与线程交错相关的多线程程序执行状态来检测并发错误。作者将这些多线程相关的目标并发错误归为两类:

  • 并发漏洞($V_m$):该类对应的是在多线程环境下产生的内存破坏漏洞,这些漏洞可以在模糊测试的阶段中被发现;
  • 并发错误($B_m$):该类对应的是例如数据竞争与死锁的并发错误。Muzz通过重放生成的模糊测试种子并使用例如TSan的并发错误检测工具来检测这些错误。

其中,并发错误并不能在模糊测试的阶段中被发现,这是因为其并不一定会导致内存破坏,造成多线程程序的崩溃。

2 Background and Motivation

20200914152424

给定目标程序$P_o$与初始模糊测试种子$Q_s$,灰盒模糊测试首先通过代码插桩来记录P~o~中的代码覆盖率,随后其进入模糊测试的循环:1)种子选取决定了接下来被测试的种子$t$;2)种子调度决定了被选取的种子$t$接下来被变异的次数$M$;3)种子变异通过变异被选取的种子$t$生成新的种子$t’$;4)在重复执行的过程中,针对每个新生成的种子$t’$,灰盒模糊测试执行其$N_c$次并记录执行的统计信息;5)种子分类根据代码插桩的统计信息以及代码覆盖率的反馈来评估被执行的种子$t’$,即确定该种子是否可以触发并发漏洞,或者是否是有效且需要得到保留的。

20200914152438

为了检测多线程相关的错误,灰盒模糊测试需要生成不同的模糊测试种子来在多线程环境下执行不同的程序路径。然而,现有的灰盒模糊测试甚至难以生成可以探索多线程代码片段的种子。同时,即便一些种子确实可以探索多线程的代码片段,这些种子依旧有可能难以满足特定的前提条件,从而无法探索存在问题的多线程程序执行状态。

作者为被执行的模糊测试种子提供了细粒度线程敏感的运行时反馈以探索多线程的代码片段,并探索存在问题的多线程程序执行状态。作者根据运行时的反馈来决定种子是否需要得到保留,因此灰盒模糊测试将会保留更多探索多线程代码片段的种子。本质上,这提供了一种针对多线程代码片段的倾向性覆盖率反馈。

20200914152511

作者通过在多线程相关的基本块中增加更多的代理指令来提供更多的线程交错反馈,并通过增加线程的上下文信息来区分不同的线程。在灰盒模糊测试的重复执行过程中,模糊测试种子可能会表现出不确定的行为,即种子由于随机性的影响在多线程环境下的重复执行过程中执行不同的程序路径。因此,作者还通过增加线程调度来随机化实际的线程交错。

3 System Overview

20200914152535

Muzz包含四个主要组件:1)线程敏感的静态分析引导的插桩;2)动态模糊测试;3)并发漏洞分析;4)并发错误检测。在插桩的过程中,Muzz首先生成线程敏感的跨过程控制流图(ICFG),并识别可疑的线程交错代码片段。基于这些结果,Muzz采用了三种代码插桩:

  • 代码覆盖率插桩:该插桩是一种通过在可疑的线程交错代码片段中增加更多代理指令的分层插桩,是记录线程交错相关的多线程程序执行状态覆盖率的主要插桩;
  • 线程上下文插桩:该插桩是一种通过记录例如线程fork与join的线程操作函数上下文来区分不同线程ID的轻量级插桩;
  • 线程调度插桩:该插桩是一种在线程函数入口动态调整每个线程优先级的轻量级插桩,其通过增加线程调度来随机化实际的线程交错。

在动态模糊测试的过程中,Muzz通过优化种子选取与重复执行的过程来生成更多多线程相关的种子。并发漏洞分析组件被应用在造成多线程程序崩溃的模糊测试种子上以检测并发漏洞,而并发错误检测组件则是在例如TSan与Helgrind的工具的帮助下检测并发错误。

4 Static Analysis Guided Instrumentation

4.1 Thread-aware Static Analysis

考虑例如POSIX标准Pthread的线程API的语义,Muzz生成了包含五类多线程信息的ICFG:

  • $TFork$是例如$pthread_create$的线程fork函数调用点的集合;
  • $TJoin$是例如$pthread_join$的线程join函数调用点的集合;
  • $TLock$是例如$pthread_mutex_lock$的线程lock函数调用点的集合;
  • $TUnLock$是例如$pthread_mutex_unlock$的线程unlock函数调用点的集合;
  • $TShareVar$是不同线程间共享变量的集合。

可疑的线程交错代码片段是根据三个条件决定的:

  • 语句在$TFork$调用之后且在$TJoin$调用之前被执行;
  • 语句在$TLock$调用之前或者在$TUnLock$调用之后被执行;
  • 语句至少读写了不同线程间共享的一个变量。

4.2 Coverage-oriented Instrumentation

对可疑的线程交错代码片段中的每条指令进行插桩可能会极大地影响多线程程序的执行效率,其代价很高。同时,由于许多线程交错实际上并没有改变共享变量的取值,这些线程交错也并没有必要去探索。因此,Muzz对可疑的线程交错代码片段中的每条指令进行等概率的插桩。

由于并发错误与漏洞通常来源于具有更高循环复杂度的多线程代码片段,Muzz基于循环复杂度的定义为每个可疑的线程交错代码片段计算出基础插桩概率$P_e(f)$,其中$N(f)$是控制流图中节点,即基本块的个数,$E(f)$是控制流图中边的个数:

$P_e(f) = min{\frac{E(f) - N(f) + 1}{10}, 1.0}$

对于不在可疑的线程交错代码片段中的基本块,Muzz以$P_s(f)$的概率插桩这些基本块的入口指令:

$P_s(f) = min {P_e(f), 0.5}$

对于在可疑的线程交错代码片段中的基本块,Muzz以$P_m(f,b)$的概率插桩这些基本块中的每条指令,其中$N_m(b)$是代码片段中例如load与store的内存操作指令的条数,$N(b)$是代码片段中指令的总条数:

$P_m(f,b) = min{P_e(f) \cdot \frac{N_m(b)}{N(b)}, 0.33}$

20200914152558

4.3 Threading-context Instrumentation

由于代码覆盖率插桩并不考虑线程的ID,Muzz采用线程上下文插桩来区分不同线程ID并作为额外的运行时反馈。这些上下文是在$TLock$、$TUnLock$与$TJoin$调用的时候被记录的。

4.4 Schedule-intervention Instrumentation

线程调度插桩的目标是随机化实际的线程交错。为了在多线程程序的执行过程中增加线程调用,Muzz采用例如POSIX的$ptherad_setschedparam$等API在$TFork$调用的时候为每个线程指定一个随机的优先级。

5 Dynamic Fuzzing

5.1 Seed Selection

种子选取决定了接下来被变异的模糊测试种子,Muzz采取的策略是优先选择探索了新的代码覆盖率或者线程上下文的种子。

20200914152629

5.2 Repeated Execution

由于随机的线程交错,多线程程序可能会表现出不确定的行为。因此,Muzz会重复执行模糊测试种子$N_c(t)$次,其中$C_m(t)$是该种子在之前的执行中探索过的线程上下文的个数:

$N_c(t) = 8 + min{32, 8 \cdot C_m(t)}$

6 Evaluation

作者的评估面向三个研究问题:

  • RQ1:Muzz可以生成更加有效的模糊测试种子来探索更多的多线程程序执行状态吗?
  • RQ2:Muzz检测并发漏洞的能力如何?
  • RQ3:在检测并发错误的方面,Muzz生成的模糊测试种子的效果如何?

6.1 Evaluation Setup

作者在评估中使用了四个灰盒模糊测试框架:1)Muzz;2)MAFL;3)AFL;4)MOpt。其中MAFL是Muzz的变体,其采用了AFL而非Muzz的代码覆盖率插桩。

20200914152648

6.2 Seed Generation (RQ1)

20200914152704

在为多线程程序生成多线程相关的模糊测试种子的方面,Muzz的表现都优于其它三个灰盒模糊测试框架,其采用的三种线程敏感的代码插桩以及动态模糊测试的策略都对这些种子的生成产生了促进作用。

6.3 Vulnerability Detection (RQ2)

20200914152716

在探索多线程相关的程序崩溃状态以及检测并发漏洞的方面,Muzz的表现都优于其它三个灰盒模糊测试框架。

6.4 Concurrency-bug Revealing (RQ3)

作者通过重放Muzz生成的模糊测试种子并使用例如TSan、Helgrind与UFO的并发错误检测工具来检测这些错误,以在两个小时的重放时间中尽可能地检测出更多的并发错误。

20200914152757

在检测并发错误的方面,Muzz的表现都优于其它三个灰盒模糊测试框架。