结合混合符号执行的导向式灰盒模糊测试技术

戴 渭,陆余良,朱凯龙

(国防科技大学 电子对抗学院,合肥 230037)

0 概述

模糊测试是一种重要的软件漏洞分析技术,其向程序提供大量的特殊或者随机的测试用例,然后监控程序运行过程中的异常情况,通过人工辅助分析异常测试用例数据,从而定位软件中的漏洞位置。模糊测试是一种简单有效的强制性技术,虽然测试存在盲目性,但是因为模糊测试具有良好的可伸缩性,所以它在应对大型应用程序时,相较于其他漏洞分析技术具有更高的效率和更低的开销,随着软件的规模和复杂度不断增大,模糊测试具有其他漏洞挖掘技术无法比拟的优势[1]。因此,模糊测试是漏洞分析技术在现实应用中的主流,也是发现漏洞最多的技术。

导向式灰盒模糊测试是指能够快速达到程序目标区域且发现漏洞的模糊测试技术。当目标只集中在程序中的某一部分时,普通的模糊测试会将大量时间浪费在不相关的区域,而无法集中在期望的区域,导向式模糊测试可以将大量的时间预算用于达到这些特定的目标位置,以及对这些区域进行更多、更集中的测试,从而更加高效地发现目标区域的漏洞,并且减少不必要的开销。文献[2]提出的导向式灰盒模糊测试器AFLGO是在模糊测试框架AFL[3]的基础上,通过前期对程序进行静态分析得到的控制流图(Control Flow Graphs,CFGs)以及函数调用图(Call Graph,CG)来计算每个基本块到若干个目标位置的距离,将目标的可达性作为一种优化,使用启发式算法来提升距离更近的种子的能量,使其生成的测试用例能快速达到程序的目标区域,从而实现了模糊测试的导向性。

符号执行作为一种重要的程序分析方法,可以为程序测试提供高覆盖率的测试用例,以触发深层的程序错误[4]。由于在符号执行过程中,针对代码执行路径会生成相应路径的约束条件,如果软件较大或存在大量循环操作,可能导致路径约束非常大,甚至呈现爆炸式增长[5]。混合符号执行[6]是结合了符号执行和具体执行的一种动态符号执行技术,其主要思想是生成具体的输入来执行目标程序,目标是通过自动生成测试用例来尽量覆盖程序中的可行路径,进而发现程序内的缺陷[7]。在程序运行的过程中,收集路径约束条件,按顺序搜索程序路径,利用约束求解器求解上一执行中收集到的约束集,从而得到下一次执行的测试用例;在下一次执行结束后,按一定的策略选择其中某一分支判断点进行约束取反,得到新的约束集,再用约束求解器对其进行求解,得到下一执行的测试用例。如此反复,可以避免执行重复路径,从而以尽可能少的测试集达到高测试覆盖的目的[4]。

导向式符号执行是利用符号执行、程序分析和约束求解等重型技术来系统有效地搜索可行路径的状态空间[9]。一旦识别出能够到达目标的可行路径,就生成满足相应路径约束的测试用例。导向式符号执行已被用于到达程序的高危区域,例如关键系统调用[9]、覆盖补丁位置[10-11]以及崩溃再现[12]等。导向式符号执行技术与导向式模糊测试技术相比,缺点很明显,它需要重量级的程序分析和约束求解,要花费巨大的开销与时间,不适用于现实中的大型程序[1],但相较于导向式模糊测试,它能够对程序进行更加深入的理解,在不考虑路径爆炸和时间开销的情况下,能够覆盖更全的程序路径。而导向式模糊测试因为具有随机性,在面对魔术字节等检查语句时,难以生成通过检查的测试用例,导致对路径的覆盖率较低。

本文对导向式模糊测试和混合符号执行技术进行研究,结合混合符号执行与导向式模糊测试技术,将符号执行只应用于导向式模糊测试不能通过的程序路径,辅助测试用例的生成,从而继承符号执行的优点,保证模糊测试的高效率和良好的可伸缩性,提高导向式模糊测试对程序目标区域的覆盖率,以对目标区域进行更深入和更有效的检测。

1 导向式灰盒模糊测试技术

在导向式灰盒模糊测试中,目标区域为由若干个目标函数组成的函数集,其基本思想是以种子到目标区域的距离为依据,控制种子的能量,距离越近,能量也越大,变异生成的测试用例就越多,这样生成的测试用例能够快速达到目标区域,从而达到导向的目的。通过静态分析得到被测程序的CFGs以及CG,以此计算程序基本块到目标区域的距离,通过跟踪种子在程序中所执行的基本块,定义种子到目标位置的距离,以距离的大小来分配种子在遗传变异中的能量,即生成测试用例的数量,从而实现模糊测试的导向性,整体架构如图1所示。

图1 导向式灰盒模糊测试技术框架Fig.1 Framework of directed gray-box fuzzing test technology

对一个程序进行导向式模糊测试,目标区域为程序中的若干个函数组成的函数集,模糊测试的流程如下:

1)在目标程序运行之前,对程序进行静态分析,通过CFGs和CG计算程序所有基本块到目标区域的距离,将计算得到的距离信息插桩进入目标程序。

2)从种子集中按顺序选取一个种子,执行程序,根据它执行的基本块和基本块的距离信息来计算种子到目标区域的距离。

3)通过动态调控函数动态地调控种子的能量,以此来调控变异生成测试用例的数量。

4)如果变异生成的测试用例执行了新的路径,则将此测试用例加入种子集,如果产生Crash,则加入Crash集合,直到该种子生成的测试用例达到预定数量。

5)如果模糊测试长时间没有产生新的状态转换,启用混合符号执行,产生覆盖了新路径的种子,加入种子队列,参与模糊测试。

重复流程2)～流程5),当种子集中的所有种子都被选取为一次迭代,继续从头开始选取种子进行下一次迭代,直到时间结束。流程1)～流程4)为本文设计的基于动态能量调控的导向式模糊测试技术,实现了模糊测试的导向性。流程5)为本文要着重研究的技术,辅助导向式模糊测试用例生成的混合符号执行技术。

2 导向式灰盒模糊测试技术实现

2.1 导向式模糊测试

为实现模糊测试的导向性,本文设计了基于动态能量调控的导向式模糊测试,主要分为静态分析和动态执行两个部分。

静态分析的输入为目标程序和给定的目标区域(若干个函数组成的函数集),结果是插桩了基本块到目标区域距离信息的二进制程序;首先计算程序基本块到目标区域的距离,通过给定的目标程序源代码(或者二进制程序)构建程序的CG和每个函数的CFGs,再根据给定的目标区域计算基本块到目标的距离,输出程序所有基本块到目标区域的距离信息。

动态执行的目标为插桩后的二进制程序,输入为选定的种子集,输出为导致目标产生Crash的测试用例,或者达到预定时间。在得到静态分析的结果后,将种子集输入执行插桩程序,跟踪程序的基本块转换,并且记录执行的所有基本块距离之和,以此来计算出所有种子级别的目标距离。在进行模糊测试时,从种子集中依次选取种子,使用动态能量调控技术并根据种子距离为种子分配不同的能量,种子到目标距离越近,分配的能量就越多,种子根据能量变异生成不同数量的测试用例执行目标程序,同时继续跟踪程序的基本块执行情况和距离信息,如果产生了新种子,则加入种子集参与循环。

2.1.1 种子到目标区域距离的计算

为实现模糊测试的导向性,使更加接近目标区域的种子生成更多的测试用例,需要计算一个种子到目标区域的距离,再根据距离来决定这个种子能够生成多少测试用例。为精确地计算种子到目标区域的距离,本文对程序静态分析技术进行了研究和拓展,首先运用静态分析获取程序的CFGs和CG,用于计算函数级别和基本块级别的距离。使用CFGs和CG中的最短路径的边数来表示函数间和基本块间的距离,通过Dijkstra’s算法[13]即可分别计算目标区域中每个目标函数到各个基本块的最短距离,但这种表示方法不够准确,因为两个函数间可能不止一种调用方法,被调用函数也可能不止一个进入点,这样相邻函数间的边应该被赋予不同的权值,它们的可达路径不止一种,不能直接简单地用边的条数来表示距离。为了更好地定义相邻函数间的距离,用Nf来表示被调用函数在调用方法中的个数,Nb表示被调用函数在调用函数中出现次数,用d′1和d′2表示Nf和Nb的影响因子,d′f则表示两个相邻函数之间边的权值。通过程序和CG即可计算出函数间边的权值,将其作为两个相邻函数之间的距离,再利用Dijkstra’s算法来分别计算每个目标函数到所有函数的最短距离,这样便得到了加权后每个函数在调用图中分别到各个目标函数的最短距离df(f,tf)。

(1)

(2)

d′f(f1,f2)=d′1·d′2

(3)

1)函数级别距离计算

函数级别的距离计算用来计算CG中的每个函数到所有目标函数的平均距离。对于一个函数f到多个目标函数的距离计算,根据它到每个目标函数的最短距离,使用调和平均值来计算出它到目标函数的平均距离作为到目标区域的距离,得到函数级别距离的计算公式:

(4)

其中,df(f,tf)为函数f到目标函数tf的最短距离,Tf为所有目标函数的集合,R(f,Tf)为函数f能够达到的所有目标函数的集合。

2)基本块级别距离计算

虽然种子的距离是程序间的,但是本文的计算只需要对CG和每个程序间CFGs进行一次分析,将基本块级别的计算近似到了函数级别的计算。在同一个程序间CFGs中,将相邻基本块之间的边作为它们的距离,两个基本块之间距离为它们之间的最短路径的边数。不在同一个CFGs的基本块目标距离通过基本块能够调用的函数来确定,以调用函数的函数级距离的常数倍来近似计算,当一个基本块没有可以调用的函数时,就通过它所能达到的所有可以调用函数的基本块来确定。基本块到目标区域的距离计算公式如下:

db(b,Tb)=

(5)

其中,db(b,Tb)表示基本块b到目标区域的距离,Btf为目标函数的基本块集合,N(b)为基本块b可以调用的函数集合,且满足∀b∈T,N(b)≠φ,db(b,t)为两个基本块b、t之间最短路径的连接边数,a为一个常数。

3)种子级别的距离计算

前两个级别的距离计算是在静态分析阶段进行的,而种子级别的距离计算则是在模糊测循环开始后动态地实现的。本文通过跟踪种子执行了哪些基本块来计算种子到目标区域的距离,在AFL和LibFuzzer[14]等灰盒模糊测试器中,使用了轻量级的插桩来获取程序的覆盖信息,这种插桩能够获取基本块的转换信息,以及粗略的分支命中计数,本文在此基础上进行拓展,将得到的所有基本块距离向量加入程序的插桩,得到插桩后的二进制程序,这样就可以追踪种子执行的基本块,计算出种子到目标区域的平均距离:

(6)

最后将得到的种子距离归一化来得到最终的距离向量:

(7)

其中,dmax(s,Tb)和dmin(s,Tb)分别为所有种子中离目标最大的距离和最小的距离。

2.1.2 种子的动态能量调控技术

种子的能量调控用来调控一个选中的种子的变异次数,如果当前的种子距离目标区域更加接近,那么就要给它分配更多的能量,变异生成更多的测试用例,这样就能够更大概率生成所期望的测试用例(到达目标区域)。本文使用基于蚁群算法[15]的动态能量调控函数来动态地调控种子的能量。

蚁群算法是一种用来寻找最优化路径的概率型算法,它具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法,它的基本方法如下:

1)N只蚂蚁从一个出发点到四周搜索食物,N只蚂蚁都搜索完毕为一轮迭代。

2)每只蚂蚁在行进的路上释放信息素,信息素的量和解的质量成正比,当找到食物时回到出发点,在路径留下信息素,留下的量和距离成正相关,在第一次搜寻时,所有的路径具有相同的信息素,同时每次迭代后信息素按比例减少。

3)蚂蚁选择一个路径的概率和信息素的量成正比。

4)量高的路径在每次迭代中信息素浓度越来越高,经过的蚂蚁也越来越多,而质量差的路径信息素慢慢变得越来越少,这样在迭代中,蚂蚁从刚开始的随机搜寻慢慢地往最优解收敛,从最开始的接受较差解到最后的只接受更优解,在一定程度上缓解过早收敛的问题。

设定模糊测试中的种子为蚂蚁搜索的路径,种子与目标的距离远近设定为解的质量,即距离越近,质量越高,那么每次迭代留下来的信息素也就越多。将蚂蚁选择路径的概率用作能量调控,通过迭代次数的增加,信息素的量在增加,这个种子的能量也在慢慢增加,由此来实现动态能量调控函数。

基于蚁群算法的动态能量调控函数如下:

t:迭代次数

si:种子i

di:种子i到目标区域的距离

τi:ti路径上的信息素

ρ:信息素蒸发系数0<ρ<1

Ei(t):第t次迭代时si的启发度

τi(0)=C

Δτi(t)=Q·Ei(t)·(1-di),Q为常数

τi(t+1)=(1-ρ)τi(t)+Δτi(t)

Pi(t)=(1-di)·(1-ei)+ei

其中,τi(t)为种子si在模糊测试第t轮迭代时路径上的信息素,Ei(t)为种子si在第t轮迭代时的启发度(即蚁群算法中选取一个路径的概率),Pi(t)为种子si在第t轮迭代时的能量,启发度Ei(t)的大小和信息素的多少成正相关,而Ei(t)决定着能量Pi(t)的大小。被测程序刚刚开始运行时,种子集中所有种子的信息素为相同的数值,那么它们的路径也都有着相同的启发度和能量,到了新一轮迭代时,上一轮的信息素会以按照蒸发系数ρ的比率减小,同时会增加新得到的信息素Δτi(t),Δτi(t)大小根据种子到目标的距离远近以及上一轮信息素的多少来决定,这样在一轮轮的迭代下,距离目标更近种子的路径上的信息素会越来越多,能量也会越来越大,不同种子的能量便在迭代之中产生了差距。

2.2 混合符号执行

导向式模糊测试可以快速地生成测试用例到达程序目标区域,继而发现目标区域中不同的路径,但是某些带有特定值检查的语句对于模糊测试是非常具有挑战性的。当模糊测试长时间没有触发新的状态转换时,主要原因是因为模糊测试器无法生成特定的输入满足代码中的复杂检查,混合符号执行利用约束求解器,将达到但无法满足复杂检查的现有输入转换为达到并满足此类检查的新输入。当调用混合符号执行时,跟踪每一个新加入种子队列的种子,以识别模糊测试无法满足的状态转换,当这种转换被识别时,混合符号执行产生输入通过这种状态转换。

在目标区域中,某条语句需要输入的测试用例中的某段偏移位置为特定的值才能通过,面对这种魔术字节,模糊测试很难随机地生成通过检查的测试用例,导致无法覆盖这条分支,从而无法触发这条路径上可能的崩溃点。

函数示例如下:

int main (void)

{

…

if (x=0xACDB3061)

CRASH

…

}

混合执行结合了具体执行和符号执行,是动态符号执行的一种。其主要思想是用具体输入执行程序,在程序运行的过程中,通过程序插桩手段收集路径约束条件,按顺序搜索程序路径,利用约束求解器求解上一执行中收集到的约束集,从而得到下一次执行的测试用例;在下一次执行结束后,按一定的策略选择其中某一分支判断点进行约束取反,得到新的约束集,再用约束求解器对其进行求解,得到下一执行的测试用例[16]。混合执行的优点在于,它能够探索和查找约束求解器可以满足的任何路径的输入,这使得它有助于识别复杂比较(包括某些哈希函数)的解决方案[17]。在多数情况下模糊测试可以覆盖大部分的路径,它只需通过一些简单高效的突变策略就能快速地找到更多的新路径,而混合符号执行只需解决更困难的约束。

当模糊测试长时间没有触发新的路径时,本文便认为模糊测试遇到了难以通过的状态变换,此时启用混合符号执行,调用最近覆盖了新的路径而加入队列的种子,符号化地跟踪这些种子,识别模糊测试无法满足的状态转换,使用混合符号执行产生满足这种状态变换的测试用例,将结果加入种子队列继续进行模糊测试。这种方法能够避免符号执行的路径爆炸。

在启用混合符号执行时,将种子符号化建模为一种符号状态,使应用程序的二进制代码转换为中间表示,确定程序代码对符号状态的影响,这种符号状态使用符号变量表示来自用户的输入或者其他非常量数据,例如来自环境的数据,其他的值被建模为具体值(如一些常量)。符号变量是一个变量,它可以产生许多可能的具体解,随着具体的执行,符号约束被添加到这些变量中,这些约束是对符号值的潜在解的限制性陈述(如x>0),分析引擎在整个执行过程中跟踪符号状态中的所有具体值和符号值。在到达的程序中的任何节点上,都可以执行约束求解来确定满足状态中所有可能的符号约束,当使用满足这些约束的具体值来代替符号值时,就是一个满足这个约束的测试用例。当跟踪到有条件的控制流转换时,会检查反转这个条件是否会导致发现新的状态变换,如果可以,则将生成一个示例输入通过新的状态转换而不是沿着原来的控制流执行。这样就能够到达程序中未被覆盖过的位置,在产生输入之后,会继续沿着匹配的路径寻找新的状态转换。

混合符号执行使用了预约来确保能够保持执行结果与跟踪的种子所执行的结果相同,同时保持发现新的状态转换的能力。在预约束执行中,输入的每个字节都被约束为与种子的实际字节相匹配,当发现新的基本块转换时,短暂地取消预约束,求解出满足变换的输入。如混合符号执行首先约束输入中的所有字节,匹配跟踪的输入,当执行到魔术字节的检查时,识别到一个之前未识别的状态转换,此时删除开始添加的预约束,获取这个位置的路径约束(x=0xACDB3061),这样便可以生成一个在特定位置包含了魔术字节的输入,通过这个路径转换。

在得到了通过新的状态转换的测试用例后,将其加入种子集,并将新加入的种子优先选择继续进行模糊测试,重复整个导向式模糊测试的循环。

3 实验与评估

为实现和评估混合符号执行在导向式模糊测试中的效果,本文在模糊测试框架AFL的基础上设计了导向式模糊测试器AFL-Ant。该设计以python脚本的形式实现距离计算器,输入为程序的CFGs、CG以及目标函数集,用networkx包来解析图形,再使用Djikstra’s 算法来计算基本块到目标的距离,计算并输出基本块距离信息BB-distance。AFL-Ant 拓展了AFL的插桩,将BB-distance 插桩到目标程序的基本块,在记录基本块转换的同时,也记录所执行基本块的距离累积值,该项目使用 ASAN[18]构建。AFL-Ant 的模糊测试器基于2.40b版本的 AFL,它通过记录的基本块距离累计值来计算当前的种子距离,使用本文所设计的基于蚁群算法的动态能量调控方法来调控种子能量。同时设计了基于Angr[19]的混合符号执行引擎,这个引擎是基于Mayhem[20]和S2E[21]拓展和改进的。为评估结合混合符号执行的导向式模糊测试器在模糊测试中对目标区域的覆盖效果,本文通过补丁检测来测试它的能力。

结合当前最近的导向式模糊测试器AFLGO所做的工作,本文选取了GNU Diffutils和GNU Binutils[22]两组工具集作为目标程序,选取了它们在特定版本的补丁,将补丁所覆盖的位置作为目标区域,设置了相同的初始种子集,分别使用AFL和AFL-Ant对它们进行导向式模糊测试,测试时间设置为8 h,最终比较它们在模糊测试中所覆盖的目标区域基本块的数量。

GNU Diffutils工具集测试工具为Diff、sdiff、diff3、cmp,程序大小为42 930行,选定补丁版本为2016-11-09—2017-05-12的175份commits。

GNU Binutil工具集测试工具为addr2line、ar、cxxfilt、elfedit、nm、objcopy、objdump、ranlib、readelf,程序大小为68 830行,选定补丁版本为2017-04-12—2017-08-11的181份commits。补丁情况如表1所示。

表1 补丁测试中的基本块覆盖情况Table 1 Basic block coverage in patch testing 块

表1展示了补丁测试的结果,Diffutils的补丁基本块数量为166块,在实验中,AFLGO覆盖了其中的61块,而AFL-Ant覆盖了69块,相比于AFLGO提高了13.1%;Binutils的补丁基本块数量为852块,AFLGO在实验中覆盖了其中的163块,而AFL-Ant覆盖了其中的178块,相比于AFLGO提高了9.2%。合计AFL-Ant在补丁测试中对目标区域基本块的覆盖数量为247块,相较于AFLGO的224块提高了10.2%。

图2统计了两个导向式模糊测试器测试结果的交叉情况,两个测试器总共覆盖了补丁中的252个基本块,其中有219块是它们共同覆盖到的。在AFLGO覆盖的基本块中,有5个是AFL-Ant未覆盖到的,而AFL-Ant能够覆盖28个AFLGO无法覆盖到的基本块。

图2 补丁测试覆盖情况文氏示意图Fig.2 Venn schematic diagram of patch test coverage

为了评估AFL-Ant和AFLGO在覆盖目标区域的效率,在219个共同覆盖的基本块中,随机选取了其中的120块,将其分为了3组作为新的目标区域,用AFL-Ant和AFLGO分别对每组进行导向式模糊测试,实验的时间上限设置为2 h,比较它们每组实验中覆盖所有目标所花费的时间。

实验结果如表2所示,AFL-Ant在3组实验中均能覆盖到目标区域的所有基本块,而在第3组实验中,AFLGO未能在2 h内覆盖所有的目标基本块。同时,AFL-Ant覆盖所有基本块的时间均比AFLGO更快,这归功于它更加高效的动态能量调控方法以及混合符号执行辅助通过复杂节点能力。

表2 补丁测试时间Table 2 Patch test time min

通过上述实验可以看出,使用了混合符号执行的AFL-Ant能够提高对目标区域的覆盖率,发现更多的程序状态变换,同时能够覆盖目标区域,更加高效地去挖掘漏洞。

4 结束语

本文对混合符号执行技术在导向式模糊测试中的应用进行研究,提出一种新的导向式模糊测试策略,即使用混合符号执行辅助导向式模糊测试的测试用例生成的方法,帮助导向式模糊测试到达一些脆弱的区域。实验结果表明,该方法能够提高导向式模糊测试对目标区域的覆盖率,加快到达并覆盖整个目标区域的速度,提高发现目标区域漏洞的概率。本文导向式模糊测试中使用CG和CFGs来进行种子的距离计算,但未考虑到间接调用关系,导致间接调用的函数间距离计算不够准确,在未来工作中将通过改进静态分析方法识别程序中的间接调用关系来完善种子的距离计算过程。同时,可将静态分析技术和本文提出的混合符号执行引擎结合,以更大概率地去触发程序漏洞。