Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

ParmeSan: Sanitizer-guided Greybox Fuzzing

作者:Sebastian Österlund, Kaveh Razavi, Herbert Bos, Cristiano Giuffrida

单位:Vrije Universiteit Amsterdam

出处:Usenix Securiy 2020

原文:ParmeSan: Sanitizer-guided Greybox Fuzzing

摘要

Fuzzing的关键问题之一是在哪里寻找漏洞。考虑到错误覆盖率通常与代码覆盖率相关,覆盖率指导的fuzzer会不加选择地进行优化以覆盖尽可能多的代码。由于代码覆盖率过高地估计了错误覆盖率,因此这种方法不太理想,可能会导致错误的平均暴露时间(TTE)。定向fuzzer尝试通过将fuzzer定向到具有潜在漏洞的基本块来解决此问题。这种方法可以极大地降低特定漏洞的TTE,但是可能会大大降低总体漏洞覆盖率。

在本文中,作者介绍了sanitizer指导的模糊测试,这是该领域的一个新设计点,专门针对错误覆盖进行了优化。为此,作者做出的主要观察是,尽管现有sanitizer通常用于检测fuzzer引起的错误条件,但它们还可以作为一种通用且有效的机制来识别有趣的基本块以指导fuzzing。 作者设计并实现了sanitizer指导的fuzzer——ParmeSan。其大大降低了实际错误的TTE,发现错误的速度比现有的基于覆盖率的fuzzer器(Angora)快37%,比定向的fuzzer(AFLGo)快288%,并同时保有相同的bug集。

1 背景&介绍

1.1 现有问题

  • 由于代码覆盖率与错误覆盖率密切相关,目前的fuzzer试图在给定的时间内覆盖尽可能多的代码
  • 代码覆盖率是错误覆盖率的过高估计,要花费大量时间来覆盖许多不感兴趣的代码路径
  • 定向fuzzer试图通过将程序转向更易受错误(例如,新编写或修补的代码以及API边界)影响的位置来解决此问题但不足以覆盖整个错误范围

1.2 作者的发现

  • 使用编译器清理程序的知识在运行时检测许多错误-检错框架可在目标中插入检查范围广泛的可能错误(例如,越界访问或整数溢出)程序。现有的模糊测试人员通常主要使用sanitizer来改善错误检测和分类。作者认为,通过改善目标程序中错误覆盖率的近似值,可以进一步利用它们。通过应用定向的模糊测试主动引导模糊测试过程触发sanitizer检查,作者可以触发与覆盖率指导的fuzzer相同的错误,同时需要更少的代码覆盖率,从而缩短了错误的暴露时间(TTE)。此外,由于诸如LLVM之类的编译器附带了许多具有不同检测功能的sanitizer,因此作者只需选择适当的sanitizer,就可以将fuzzer引导到特定的错误和行为类别或一般的错误类别。例如,TySan的检查可以将模糊测试引导到非常具体的错误(例如,类型混淆)-模仿定向的fuzzing,但是具有隐式指定的目标-而ASan的普遍的检查可以将fuzzing引导向更常见的内存错误类别-模仿覆盖率指导的模糊测试

1.3 作者的工作

在本文中,作者利用这种见识来构建ParmeSan,这是第一个由sanitizer引导的fuzzer。 ParmeSan依靠现成的sanitize程序检查来自动最大化目标错误类别的错误覆盖率。与现有解决方案相比,这使ParmeSan可以更有效地以较低的TTE查找错误,例如内存错误。像覆盖率指导的fuzzer一样,ParmeSan并不局限于特定的API或代码区域,而是旨在发现这些错误,无论它们在哪里。但是,与覆盖指导的fuzzer不同,它不是通过盲目覆盖程序中的所有基本块来实现的。而是将探索引导至重要的执行路径,从而有最大的机会在最短的时间内触发错误。 为了设计和实施ParmeSan,作者需要一种从给定的sanitizer中自动提取有趣目标的方法。 ParmeSan通过将程序的带有sanitizer的版本与基准进行比较,从而以黑盒的方式定位sanitizer检查,并使用修剪启发法清除不感兴趣的检查(不太可能包含错误),从而解决了这一难题。其次,作者需要一种方法来自动构建精确的(过程间的)控制流图(CFG),以将模糊测试引导至目标。静态CFG构造方法本质上是不精确的,尽管足以用于​​现有的专用fuzzer,但不适合达到sanitizer在整个程序中的许多检查要求。 ParmeSan通过使用高效,精确的动态构造CFG来应对这一挑战。最后,作者需要一种在这些构件之上设计fuzzer的方法。 ParmeSan通过采用两阶段定向的模糊测试策略解决了这一挑战,在该策略中,模糊测试器交错两个阶段(针对CFG构建进行模糊测试,对目标点进行模糊测试)并利用两者之间的协同作用。例如,由于第一个CFG构建阶段需要数据流分析(DFA),因此作者使用可用的DFA信息来加快第二个错误查找阶段。基于DFA的模糊测试不仅有助于查找新代码,类似于最新的覆盖范围指导的模糊测试,而且还可以有效地翻转sanitizer检查并触发错误。

在本文中,作者做出了以下贡献: * 演示了一种依靠现有编译器清理程序遍历找到有趣的fuzzing目标的通用方法。 * 演示了一种动态方法来构建精确的控制流图,以将输入引向目标。 * 设计并实现了ParmeSan,这是第一个由sanitizer引导的fuzzer,它采用了两阶段定向的模糊策略,可以有效地实现所有有趣的目标。 * 通过实验评估,作者的方法可以在更短的时间内找到与最新的覆盖指导和定向模糊测试相同的错误。

Overview

主要包括三个部分:目标获取,动态CFG和fuzzing部分。

第一个组件是目标获取(target acquisition): * 它收集了作者希望fuzzer达到的许多有趣目标。目标集是由给定的sanitizer在给定程序上操作生成的。 作者使用简单的静态分析策略将程序的检测版本与基准进行比较,并自动在整个程序中查找由sanitizer放置的检测对象。 接下来,目标获取使用启发式地修剪以清除不感兴趣的对象(例如,不太可能包含错误的“热”路径)并派生出较小的有趣目标集,以进行有效的模糊测试。

第二个组件是动态CFG: * 它在目标程序执行期间维护了精确的、可识别输入的CFG抽象,适用于“许多目标定向的模糊测试”。 在执行过程中会在CFG上添加观察到执行的边,并依靠DFA来跟踪输入和CFG之间的依赖关系。从而动态CFG组件可以跟踪与输入有关的CFG变化,并向输入突变提供反馈,在该输入突变中,输入字节可能会影响给定输入的CFG。

最后一个组件,即ParmeSan fuzzer: * 使用一个已检测的二进制文件,一组目标,一个初始距离计算以及一组种子作为输入。从输入种子开始,以获得初始的已执行基本块集以及这些基本块所覆盖的条件。然后,它尝试使用动态CFG组件提供的精确距离信息,将执行从目标获取组件引向目标。在每次试验中,ParmeSan fuzzer 将从访问条件列表中优先解决该条件,从而使到目标基本块的距离最佳。 由于作者已经需要DFA进行CFG构造,因此作者也可以使用它来解决分支约束。在ParmeSan中,这种直觉不仅用于查找新代码以有效地达到目标(类似于基于DFA的覆盖率指导的fuzzer),还用于快速翻转已达到的目标sanitizer检查并触发错误。fuzzer的输出包括生成的错误输入。

Target acquisition

目标获取组件依靠现成的编译器sanitizer来找到有趣的目标。关键思想是将fuzzer引导至触发sanitizer中的错误条件,并以定向方式查找实际错误。 通过以通用方式实施分析,作者表示可以使用任何现有或将来的sanitizer来收集可能有趣的目标,并且可以根据使用的sanitizer轻松地将fuzzing管道重新定位到不同类的bug。

1 Finding instrumented points

诸如LLVM之类的编译器框架将前端代码(以诸如C,Rust等语言编写)转换为与机器无关的中间表示(IR)。分析和转换过程(例如sanitizer)通常在IR级别起作用。假设作者将一个应用程序转换为LLVM IR:现有的sanitizer通道可以对IR进行检测,以添加sanitizer检查并启用运行时错误检测。例如,清单1中的代码片段已使用UBSan工具进行了增强,以检测指针溢出。 UBSan过程在加载指针(位于%6)之前添加了条件分支。如果满足添加的条件(即发生溢出),则添加的分支将调用错误处理函数__ubsan_handle_pointer_overflow()。

sanitizer以两种不同的方式检测程序。一些工具只是简单地更新内部数据结构(例如,影子内存),而其他工具是在sanitizer使用与内部sanitizer数据结构进行交互的分支条件(例如,ASan的出入限制检测)或检测到实际错误时使用的。程序的即时状态(例如清单1)。作者的目标是将模糊测试指向sanitizer更新其内部数据结构(即有趣的代码路径)和sanitizer引入的条件分支的点,如果解决则意味着作者已经发现了一个错误。

由于存在许多不同的sanitizer,如果要经常添加这些目标,作者希望使用一种与sanitizer无关的分析方法来收集这些目标。为此,作者对带有和不带有sanitizer的目标程序的IR差异(diff)进行了黑盒分析。为了包括不包含条件的已检测基本块,作者添加了由sanitizer检测的所有先前的基本块。对于包含条件的已检测基本块,作者同时包含已检测基本块和具有条件的基本块(即,通常是sanitizer的错误检查功能)。作者发现这是一种简单的策略,可以产生一种通用且有效的方式来获取与所有现有(以及将来)的LLVMsanitizer兼容的目标。

2 Sanitizer effectiveness

为了验证作者使用sanitizer作为有趣目标的方法是否正确,作者检测了许多应用程序,并确认目标sanitizer检查可以检测到实际的错误。在表1中,作者针对多种已知漏洞测试了三种不同sanitizer的有效性。 AddressSanitizer(ASan)能够发现缓冲区溢出和释放后使用的错误。 UndefinedBehaviorSanitizer(UBSan)能够检测未定义的行为,例如使用未对齐或空指针,整数溢出等。TypeSanitizer(TySan)能够在访问C / C ++对象时检测类型混淆。使用错误类型的指针。

表1显示了sanitizer是否捕获了该错误以及未包含在检测到的基本块的路径中的程序的基本块数。例如,如果将一个深层基本块视为目标(即包含目标分支),则必须覆盖其所有前身。但是,不需要覆盖不在目标路径上的非目标基本块,因为作者的分析估计这些块中没有错误。通过计算以这种方式可以忽略(非目标)的基本块的数量,作者获得了一个度量标准,用于估计有多少基本块与触发sanitizer错误无关,因此在进行模糊测试时无需覆盖这些基本块。此度量标准使作者可以估算sanitizer指导的模糊测试与针对不同sanitizer的传统的面向覆盖的模糊测试相比。

在许多情况下,可以忽略很大一部分代码覆盖范围。例如,在使用TySan的libxml2中,作者可以忽略80%的基本块,并且仍然可以找到错误。但是,如表1中的修剪指标所示,不同的sanitizer仪器在多少应用中存在很大差异。一些sanitizer,例如UBSan和TySan,专门研究了它们的作用,产生了少量目标。其他sanitizer(例如ASan)可以检测到许多基本块,因此,如果作者将每个检测点都视为目标,那么最终将导致覆盖率指导的模糊测试。

因此,面临的挑战是限制要考虑的获取目标的数量,同时仍保持触发实际错误的有趣目标。为了应对这一挑战,作者的解决方案是采用修剪启发法来清除候选目标集中的目标部分。作者对许多修剪启发式算法进行了实验,最终在作者当前的ParmeSan原型中仅包含两个简单但有效的启发式算法:

  • Profile-guided pruning:
    • 限制目标数量的第一个试探方法是执行配置文件引导的目标修剪。
    • 通过对ASAP 应用类似的方法,分析目标程序并删除所有在热路径上(即由分析输入达到的)sanitizer检查。由于热路径不太可能包含残留到生产中的错误,因此该策略可以有效地修剪目标集,同时也更喜欢“深度” /难以达到的目标。 虽然这种修剪机制可能会删除一些有效的目标,但ASAP的作者指出(以最保守的估计),仍然可以检测到80%的错误。
  • Complexity-based pruning:
    • 限制目标数量的第二种启发式方法是进行基于复杂性的修剪。
    • 由于清理程序通常会在一个简单的分支之外添加其他工具,因此作者会根据清理程序添加/修改的指令数量(差异启发式)来对函数评分,并将得分高于其他指令的目标标记为更有趣。
    • 直觉是,清理程序在函数内更改的指令越多,函数的复杂性就越高,因此遇到清理程​​序针对的漏洞类别的机会也就越大。
    • 作者使用ASan在LAVA-M 上使用这种启发式方法,在base64中的前3个目标位于函数lava_get(),lava_set()和emit_bug_reporting_address()中,其中前2个函数是LAVA-M中触发已注入错误的函数。当基于分析选择要修剪的目标时,会考虑该分数。这样,目标获取组件就可以将目标保留在冷代码中。

Dynamic CFG

为了使sanitizer指导的模糊策略有效,ParmeSan必须能够有效地将执行引导至目标获取步骤所标识的代码。 为此,ParmeSan需要精确的CFG来估计任何给定的基本块与目标之间的距离。 构建精确的CFG是作者动态CFG组件的作用。 作者首先展示如何在模糊过程中动态提高CFG的精度(第5.1节)。 然后,使用改进的CFG,ParmeSan需要利用距离度量来确定给定执行跟踪与由sanitizer检测到的有趣代码块相距多远的代码路径的优先级(第5.2节)。 为了进一步提高ParmeSan距离度量的质量,作者在CFG中添加了动态(数据流)分析(DFA)信息,以确保通过选择当前输入字节来始终满足某些有趣的条件(第5.3节)。

1. CFG construction

先前的定向fuzzer依赖于静态生成的CFG进行距离计算。在对许多目标进行定向模糊测试时,静态生成的CFG会导致结果不准确。对于ParmeSan,作者改为选择动态生成的CFG。特别是,作者从LLVM静态生成的CFG开始,然后在程序在模糊测试过程中动态添加边缘来逐步提高精度。例如,当作者发现无法在编译期间静态解决的间接调用时,就会发生边的这种添加。

为了执行可伸缩的距离计算,作者使用起点和目标之间的条件数,因为条件是模糊器试图解决的本质。与完整的CFG相比,此策略可生成紧凑的条件图(CG)-仅包含条件的紧凑CFG。 ParmeSan在运行时同时维护CG和CFG,但仅将CG用于距离计算。 作者将AFL边缘覆盖跟踪策略重新用于作者的紧凑型CG设计。在为每个基本块分配随机生成的标识符后,作者首先从CFG收集它们。请注意,节点数是静态的,并且永远不会改变。另一方面,CFG中的边缘是动态的,当遇到不存在的边缘时,作者会将其添加到CFG和CG中。具体来说,对于执行所需的每个边缘,作者记录边缘标识符(先前和当前基本块标识符的哈希),如果边缘尚未出现在CFG中,则只需添加它。当将边缘添加到CFG时,作者只需要更新CG的子集,只为新边缘的相邻条件添加缺失的边缘。

2. Distance metric

距离度量可以帮助模糊器确定下一步需要探查CFG的哪些部分,以使其更接近所关注的基本块。 由于距离计算会很快遇到可伸缩性问题,因此作者将给定分支条件c到导致有趣基本块的分支条件的距离定义为d(c),用一种递归方法计算。在给定输入执行跟踪的情况下,ParmeSan使用距离度量来确定应尝试翻转的分支(通过修改输入),从而将执行转向有趣的基本块。

3. Augmenting CFG with DFA

通过根据输入将间接调用目标固定到单个目标,动态CFG可以进一步改善距离计算。 如果既要知道要到达的sanitizer检查,又知道确定间接调用目标的输入字节,则可以对输入字节进行修复,以知道间接调用的目标。 这种简单的改进会严重影响距离计算的精度。 如果程序具有许多可能的目标的间接调用,则此优化主要有益。

Evaluation

1 ParmeSan vs. directed fuzzers

首先将其与最新的定向灰箱模糊器进行比较,并显示仅DFA信息的可用性就可以显着改善定向模糊。 作者重现了AFLGo和Hawkeye涵盖的许多基准,显示了ParmeSan在传统的定向环境中的表现。作者比较了ParmeSan,AFLGo和HawkEye在OpenSSL和Binutils中已知错误的崩溃复制方面的比较。手动以代码中导致崩溃的点为目标,并让fuzzer生成输入以重现崩溃(即ParmeSan跳过其目标获取步骤)。

如表所示,在所有情况下重现这些错误时,ParmeSan的性能均优于HawkEye和AFLGo。对于大多数来说,ParmeSan的速度是其两倍以上,而在最坏的情况下(CVE-2016-4490),其复制错误的速度仍比AFLGo快30%以上。添加DFA信息使ParmeSan可以专注于解决条件问题,包括到达目标以及目标本身的方式,从而导致更具针对性的变异策略(所需执行次数更少),从而可以更快地崩溃崩溃。作者得出的结论是,即使对于传统的定向模糊测试,ParmeSan也可以显着改善最新的bug暴露时间(TTE)。

2 Coverage-guided fuzzers

作者评估发现自己的fuzzing策略发现(许多)错误的速度要比最新的覆盖率指导的模糊器更快。专门与Angora进行了比较,后者在所考虑的数据集上是最快的开源竞争对手,例如,比QSYM更快。

为了证明sanitizer指导的模糊测试可以有效地发现现实中的错误,作者在Google模糊测试套件中评估了ParmeSan 。该数据集包含许多已知的错误,覆盖率基准以及对23个真实库的断言检查。作者证明了ParmeSan能够以明显更少的时间触发与面向覆盖的模糊器相同的错误。在此套件中,始终将ASan用于ParmeSan的目标获取步骤,因为它功能强大且可检测到一些最常见的内存错误。

在所有基准测试中,使用套件提供的种子作为初始语料库。由于数据集包含许多难以触发的错误,因此以48小时的超时运行实验,以使fuzzer有机会获得这些错误。例如,Angora平均花费47小时触发freetype2中的整数溢出。此外,该套件将运行时清理程序添加到每个应用程序中以检测错误。作者使用套件中使用的默认参数编译并运行每个程序。

表3显示了来自Google模糊测试套件数据集的多个错误的平均暴露时间(TTE)。作者强调作者评估了整个测试套件,但是为了简洁起见,省略了48个小时内没有模糊器发现的11个错误,以及带有12个非常容易发现但没有任何异常结果的bug的openthread集(当然,确实将它们包括在作者的几何平均值计算中,以避免产生偏差)。评估分为两个部分。第一部分,整个管道,使用整个ParmeSan管道,并使用ASan自动获取目标。作者将ParmeSan与基线Angora(即无目标)和sanitizer指导的AFLGo(即与ParmeSan具有相同目标)进行了比较。作者看到ParmeSan的性能明显优于AFLGo和Angora,TTE的geomean速度分别提高了288%和37%。

在表4中,作者展示了ParmeSan和4种不同的最新fuzzer在暴露时间(TTE)的分支覆盖率:AFLGo,NEUZZ ,QSYM 和An-戈拉。在本实验中,作者使用1个实例运行所有的模糊器,除了QSYM使用2个AFL实例和1个QSYM实例(根据作者建议的设置)在分配了一个CPU的Docker容器内。请注意,结果中没有包含NEUZZ和ParmeSan所需的预处理时间。对于ParmeSan,预处理时间为正常编译时间的顺序(如表8所示)。套件中的每个基准测试都在启用sanitizer的情况下运行(根据测试套件)。

3 Sanitizer impact

作者评估分析中使用的特定sanitizer如何影fuzzing的最终结果。作者证明了使用的sanitizer确定了ParmeSan可以找到的错误的类别,从而使作者能够集中精力处理特定类型的错误。

表3显示了ParmeSan在内存泄漏错误方面表现最差。这首先表明作者的sanitizer分析对最终结果有重大影响。由于作者使用ASan进行目标获取,因此模糊测试将定向到可能无效的内存使用。这仍然涵盖了分配内存的实际使用,但是理想情况下,作者希望将模糊测试定向到分配内存的调用。作者对内存泄漏错误进行了重复实验,但是现在使用LeakSanitizer(LSan)而不是ASan来进行目标捕获(请参见表5)。

LSan在运行时跟踪分配的内存对象,并在程序终止时生成内存泄漏的摘要。LSan不会修改IR,而是拦截对链接之类的malloc之类的函数的库调用。取而代之的是,作者创建了一个自定义的LLVM传递,将伪调用插入到被拦截函数的钩子中,从而产生与标准LSan相同的行为,同时仍在相关位置更改IR。这是一个将来可以轻松实现自动化的过程,并且仅是当前实施的限制。使用作者的自定义LSan通行证进行目标捕获,与使用ASan进行目标捕获相比,libssh,libxml,openssl,proj4中的内存泄漏错误的平均TTE会发生显着变化,与之相比,几何上的改进为32%。同样,对于freetype2中的整数溢出,作者看到使用正确的清除程序来捕获错误(即UBSan)进行目标捕获,可以显着提高性能,在20小时而不是47小时内发现错误。

如表5所示,用于目标采集的sanitizer之间形成了鲜明的对比。作者使用一定类型的已知错误运行许多应用程序,同时使用三种不同的sanitizer(ASan,UBSan和TySan)自动查找目标。请注意,触发错误还需要进行sanitize(因为错误通常不会使程序崩溃)。为了消除由每个sanitizer的开销引起的差异,作者始终使用同一组运行时sanitizer(ASan + LeakSan + UBsan,它能够检测所有选定的错误)对程序进行检测,而与目标程序无关收购。

如表5所示,检测到错误的sanitizer将始终使ParmeSan在最短的时间内找到错误。总体而言,作者看到使用覆盖了bug的sanitizer并检测了最少的目标集,使ParmeSan可以更快地找到bug。例如,CVE-2018-13785是libpng中难以触发的整数溢出。在这里,作者看到了最重要的改进,即选择了正确的sanitizer。具体地说,使用UBsan,作者平均在32分钟内触发了该错误,但是使用其他sanitizer,ParmeSan并未将触发该错误的站点视为目标,因此查找该错误所需的时间要长得多。错误,同时使用正确的sanitizer进行目标捕获可将性能提高一个数量级。 对于pcre2中的Free-After-Use漏洞,ASan和TySan都在检测漏洞的位置。由于TySan获得的目标数量少于ASan,因此输入生成的速度比ASan更快地转向包含实际错误的目标,从而在更短的时间内触发了错误。 CVE-2011-1944是libxml2中的整数溢出,很容易触发。在这里,作者再次看到,不那么需要工具的sanitizer使ParmeSan在最短的时间内触发了该错误。 另一方面,对于CVE-2014-0160(HeartBleed),作者看到所选的sanitizer对触发错误的速度没有太大的影响。这主要是由于ASan为作者提供了许多目标。请注意,在进行模糊测试时,由于其他内存错误,作者发现了许多其他与HeartBleed不相关的崩溃。但是,对于CVE-2015-8317(在libxml上读取的越界堆),即使作者获得了很多目标,作者也看到了重大改进。 从这些实验中作者可以得出有趣的见解,即ParmeSan能够基于用于目标获取的sanitizer来针对特定类型的错误,从而可以更有效地对应用程序进行模糊处理。例如,pcre2中的free-after-free错误可能会表现为类型混淆错误。使用Tysan​​进行目标获取,作者能够更快地触发错误20%。作者已经将分析重点放在了少数常见的现成的sanitizer上。有关不同sanitizer和行为的更全面概述,作者想指出Song&al的工作。

4 New bugs

作者将ParmeSan应用到发现新的错误中,并使用库选择将结果与众多最新的模糊测试器进行比较。 作者从OSS-Fuzz 和三个目标应用程序(jhead,pbc,protobuf-c)中随机抽取了应用程序样本,并在最近的模糊测试中对其进行了评估,其中作者能够 发现新的错误。 作者将ParmeSan设置为从OSS-Fuzz示例中模糊应用程序主分支上的最新提交。 总共,ParmeSan能够发现736个崩溃,根据调用堆栈,作者确定了47个崩溃是唯一的。 在这些崩溃中,有37个是在(有些)过时的pbc库中发现的,而其中10个是在最新的,模糊不清的库中发现的。 在OSS-Fuzz应用程序,jhead和protobuf-c中发现的错误已全部分类并解决。

个人评价

这篇文章的着眼点在于给fuzzer提速,主要针对code coverage guided fuzzer,在保持检测结果的同时,通过sanitizer来指导fuzzer,大幅度提速。角度新颖,值得借鉴。