程序的执行信息是智能模糊测试的基础。目前,研究者常利用动态污染分析技术跟踪程序的执行过程^[5,6]。该技术给输入数据的每一位设定污染标签。在程序的执行过程中,污染标签将会通过污染传播算法进行复制。污染传播算法是污染分析的核心^[7],决定污染标签如何传递。通常,污染传播算法包括读、写和赋值。例如, A是一个带有污染标签的变量, B是一个没有污染标签的变量。表达式“ B=A”将会使得 A的污染标签被复制给 B。当执行结束后,可以利用污染标签的传播来分析输入数据与结果的关系。

为了实现动态污染分析,程序的执行需要通过额外的工作来进行控制,例如对每个输入数据进行污染标记。谛听系统采用二进制插桩技术实现动态污染分析。具体过程如下:

1) 系统记录输入的文件名称、文件描述符等信息。

2) 系统对文件的读、写和诸如内存映射等相关系统调用进行插桩,以便为输入数据建立污染标签。例如,在内存中输入文件的第三位数据将会被标记为“input(3)”。

3) 系统将对内存和寄存器的读、写指令进行插桩从而实现污染标签的传播。这是动态污染分析中最重要的一步。使用一种特殊的数据结构——依赖(Dep)来存储有污染标记数据的标签来源。在每个指令中,如果系统发现有数据被标注了污染标签,系统将会读取该数据的Dep, 之后根据指令的操作更新Dep或是给其他数据标记污染标签并写入Dep。例如,在加法操作中,如果一个操作数是8, 另一个操作数是有污染标签的变量并且Dep为“input(3)”, 那么用于存储该指令结果的变量也将被标注污染标签,其Dep中将会存储“add(input(3), 8)”。

4) 当遇到条件跳转指令时,系统将会检查控制条件的值,如果该值有污染标记,那么该值的Dep将会作为该条件跳转语句的Dep, 该条件跳转和Dep都会写入执行记录中。当单个输入文件的测试执行完毕,谛听系统的污染分析模块将会分析执行记录。该模块将会提取条件跳转指令以及相应的Dep。之后分析模块将会在Dep中搜寻诸如“input( x)”( x代表一个数字)这样的字段。由于该数据影响条件跳转的结果,所以该数据将会作为后续操作的目标。

混合符号执行^[1,8]起源于符号执行^[9]。符号执行通过对符号的跟踪实现对程序的分析。在符号执行中,系统维护一张符号表,不同的符号对应不同的变量,以此将程序抽象为对符号的处理,将程序的执行过程抽象成一系列的路径约束。路径约束中的一些条件将会被取反从而得出新的路径约束。利用约束求解器,根据这些新的路径约束得出新的测试用例。混合符号执行是真实值执行和符号执行的混合体。在混合执行中,程序是以真实值来执行的,所以路径约束的表示是以真实值为基础的。但是由于混合符号执行需要动态对程序进行插桩,所以整个测试所需要的执行时间被延长了。

为了解决这个问题,本文中实现了一种并行化的架构,使得测试可以同时在多个主机上执行。为了避免多主机并行处理时取反操作可能存在的重复,本文中提出了一种新的可用于并行化系统的混合符号执行算法。在混合符号执行中,新的测试用例是基于对原有路径约束的求反而生成的,所以取反算法变得十分重要。在单机系统中,由于进行取反操作的主机具有所有的测试信息,故单机取反算法较为简单。但是在许多主机同时工作的分布式环境中,取反算法就比较复杂,原因在于,在不同的测试用例中有一部分内容是相同的,而这些用例是在不同的主机上测试和取反,因此协调取反操作比较困难。为了解决这个问题, Godefroid P等^[1]提出为每个测试用例赋予一个边界变量来限制每个主机取反的范围,但是其方法存在一个问题: 每次取反仅对一个条件取反,这就使得当输入程序有魔数检验或是校验和检验时,在很多路径约束还未进行取反操作时便终止了,导致最终生成的测试用例数量很少。考虑到以文件作为输入的程序大多带有这种魔数检验或是校验和检验,本文提出了一种改进的取反算法。该算法在获取路径约束后会对多个条件进行取反。为了保证取反操作没有超出边界值限制的范围,该算法将对多个条件的取反分解成若干轮操作,每轮操作仅对一个条件取反。

在图1所示的代码中, buf是一个长度为4的字符串,如果它的初始值为“test”, 那么任何一个 n++(自增)操作都不会执行, n的最终值依旧为0。该算法将会生成新的测试用例来改变if条件中相应的值。当“test”被作为种子用例执行后系统将会根据获取的执行信息,对“test”进行多轮取反并生成相应的测试用例,由于代码中有4个条件判断语句,所以可取反操作总数为4。其中第一轮取反生成的测试用例为“aest”、 “tbst”、 “tect”和“tesd”,他们的边界值分别为1、 2、 3和4。第二轮结果为“abst”、 “tbct”和“tecd”, 它们的边界值分别为2、 3、 4。以此类推,直至所有的边界值都达到可取反操作总数。这些新生成的用例首先被分配给不同的主机进行检测和打分,之后分配给不同的主机根据进行混合符号执行,并根据不同的边界值进行取反操作。

图1

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图1 示例代码

在现实软件中,有些缺陷是由于对分支的设计不合理导致的,对于这种程序,一旦执行某些特定的分支便会导致程序执行异常,而更多的缺陷或漏洞的触发则需要同时具备2个条件:

1) 存在该缺陷的语句的分支被执行;

2) 在执行该语句时,有相应的数据可以触发该缺陷。

以典型的strcpy函数导致的缓冲区溢出漏洞为例,触发该漏洞需要2个条件:

1) 程序执行存在该语句的跳转分支;

2) 传入该函数的第二个参数所指向内存区中的字符串长度大于第一个参数所指向的内存空间的大小。

使用混合符号执行技术的主要目的在于,通过程序执行路径的取反操作,提高生成测试用例的分支覆盖能力,但是如果缺乏合适的数据,就可能出现存在缺陷的语句被执行但是由于没有合适的数据导致该缺陷并未被触发的情况。为了解决这一问题,本文提出了一种复合化的测试用例生成方式。在利用符号执行生成初始测试用例的基础上添加一些易于触发常见类型漏洞的数据,如用于触发格式串漏洞的“% n”符号和常用于触发缓冲区溢出漏洞的内容为“ A”的字符串等,以此来创造满足第二个条件的机会。由于漏洞存在的不确定性,在生成时添加数据的位置和长度是某一特定范围以内的随机值。

谛听系统采用客户机/服务器结构(图2)。其中服务器端控制整个测试。客户端用于执行特定的测试并且产生新的测试用例。服务器和客户端通过TCP/IP网络通信。

图2

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图2 谛听系统架构图

服务器维护主机列表、测试用例表和未打分表等数据结构,并且管理每个主机的测试。当测试开始时,服务器开启监听,所有的客户端主机主动连接服务器。当所有连接都建立后,服务器将会收集连接的主机信息形成一个主机列表,并且向该列表中所有的主机发送测试相关的信息。之后测试将会在各个客户端开始。谛听系统的具体工作流程如下:

在测试执行前,服务器首先阅读本地的配置文件以获取被测程序名称和种子用例名称,并把种子用例加入测试用例表。之后谛听系统进入执行循环,循环退出条件为测试用例表和未打分列表都为空,并且当前所有客户端主机都处于空闲状态。执行循环步骤如下:

1) 如果当前有空闲客户主机,服务器从测试用例表中获取当前覆盖率得分最高的用例(第一次时为种子用例)并发送给空闲主机。客户端在动态插桩工具的控制下执行测试用例。谛听系统中包含一个动态插桩工具(Paragrind)。该工具会对open、 read等系统调用进行插桩,以此对输入数据标记污染标签,之后会插桩每个指令来实现污染传播算法。执行的结果会以文本形式保存;

2) 客户端将从执行结果中提取条件跳转信息,并将其抽象为可作为约束求解器的输入的路径约束;

3) 客户端根据1.2中所提出的求反算法对路径约束中的部分条件数值进行求反从而生成新的路径约束。该步骤是测试用例生成的核心;

4) 客户端利用约束求解器对新的路径约束进行求解,并以求解结果为基础生成新的测试用例。如果有新用例生成,客户端将会把用例发回服务器。有时新的路径约束无法生成测试用例,此时客户端会将信息发给服务器,并转到步骤1;

5) 服务器在收到新的测试用例后,将其放入未打分列表。如果当前有空闲主机,则从未打分列表中取出一个用例发送给该主机;

6) 服务器检查是否有主机完成打分任务。如果有则根据该用例分数将其从未打分列表移入测试用例列表。结束后转到步骤1。

服务器的主要工作是管理测试工作。在谛听系统中,谛听系统使用1个Task类来表示1个任务,用2个Task链表来表示当前正在执行的测试任务, 1个为测试任务,另1个为打分任务。Task类中存有该任务的执行主机、测试用例等信息。Task类将测试用例与测试主机联系在一起,是测试管理的核心。

使用Input类来表示测试用例,建立了2个Input类的列表: 测试用例表、未打分列表。在Input类中存储了测试用例的编号、覆盖率得分、测试时是否有崩溃等信息。

使用Host类来表示客户主机,建立一个Host类的列表(主机列表)表示当前所有的主机。在Host类中有套接字描述符、当前主机状态等信息。当有一个新的客户主机和服务器建立网络连接时, Host列表将会添加一个新节点用于表示该主机。

谛听系统使用Paragrind来获取程序执行信息。Paragrind基于二进制动态插桩框架Valgrind^[10]开发,其核心功能是动态污染传播。首先,它将插桩特定系统调用以对输入数据标记污染标签。之后,该插件将会插桩每条可能会传播污染标签的指令,检查操作数据是否污染标签。如果存在污染标签,目的数据也将会被标记,同时会根据源数据和指令操作生成目的数据的依赖。在遇到条件跳转时,如果条件数据带有污染标签,该跳转将会被写入执行信息记录中。单个测试结束后,执行信息中的记录就是以污染数据为基础的表达式。该记录代表着输入数据和程序执行之间的关系。

如何处理路径约束是系统中的一个关键部分。谛听建立了1个列表用于存储路径约束。

1) 谛听提取路径约束。

2) 谛听会对路径约束进行化简。因为约束中有冗余或可抵消的信息,如果直接计算比较复杂且较难处理。例如,有些表达式的形式为“32to8(8to32(expression))”, 在该表达式中从32位到8位的转换与8位到32位的转化可以抵消,化简之后就只剩下了“expression”。

3) 化简后的表达式需要转化为约束求解器的输入。该步骤的关键是取反。如1.2中所描述,谛听系统使用一种在边界值限定下的多轮取反算法。

新测试用例的生成分为2个部分: 1) 初始测试用例的生成; 2) 随机数据的添加。

第1部分产生的初始测试用例是基于求反后的路径约束。谛听使用STP^[11]作为约束求解器来计算路径约束。通常求反后的路径约束并不能满足,因为路径被改变了,但是决定路径执行的数值并没有改变,此时约束求解器就会根据这些路径算出一个满足路径的数值集合。谛听将会根据这个数据集合生成初始测试用例。第2部分是在初始测试用例的基础上添加随机数据。首先,系统将检测初始用例的长度并在其范围内选定一个数值作为数据填充的位置; 之后获取一个随机值作为随机数据的长度,随机数据的填充是为了提升触发漏洞的机率,因此填充数据不应太小。但是为了尽可能地保留原有的混合符号执行的计算结果,填充的随机数据应尽可能不覆盖条件跳转相关的数据。本系统把与条件跳转相关的最后一位数据作为界限,如果位置位于界限之前则将长度值限定在较小的范围内(20B^[12,13]); 如果位于界限以后则将长度值限定在相对较大的范围内(100~200B^[12,13])。

新用例生成后,会被分配给一个客户机进行缺陷检测和覆盖性评价。在这个步骤中,客户机会在动态插桩工具Paragrind的控制下执行测试用例。该过程包括2个方面:

1) 检测是否会触发软件缺陷或漏洞;

2) 对生成测试用例的覆盖能力进行评价,由于求反是对跳转条件的操作,所以谛听使用测试用例遍历的跳转条件数量作为覆盖率的分数。

测试开始前,需要确保客户端主机已经安装了被测的软件。为了体现本系统的有效性,本实验的3个软件都可以通过apt-get命令直接下载并安装。同时需要在服务器中预先准备好作为测试最初输入的种子文件,该文件可以是符合被测软件格式要求的合法文件,也可以是内容不为空的非法文件。

1) 基本数据

表1记录了本实验中各项基本数据。其中,生成测试用例数量是指整个实验过程中在种子文件基础上生成的所有测试用例的数量; 覆盖得分是指被测程序处理某个测试用例时经过的跳转条件的个数; 初始覆盖得分是指被测程序处理种子文件时的覆盖得分; 最高覆盖得分是指被测程序处理所有测试用例后得到的最高覆盖得分; 平均覆盖得分是对所有测试用例的覆盖得分的数学平均值; 跳转条件的总数是指被测程序中所含的跳转条件的总数量。

表1

表1

表1 实验基本数据 被测程序 生成测试用例的总数 初始覆盖得分 最高覆盖得分 平均覆盖得分 跳转条件的总数 rdjpgcom 31 963 12 655 23 074 17 277 38 962 tbl 36 057 98 804 123 072 106 820 227 497 mcrypt 135 582 87 300 126 876 104 673 201 234

表1 实验基本数据

图3描绘了初始覆盖得分、平均覆盖得分和最高覆盖得分在全局条件跳转中所占的百分比。

图3

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图3 覆盖率分析

表1和图3中的数据表明,谛听系统对于所测软件所生成的测试用例的覆盖率都高于种子文件。尤其是,对于输入格式较为复杂的程序(rdjpgcom、 mcrypt), 所生成的测试用例相对于种子测试用例可以达到更高的覆盖率(59.22%、 63.05%)。

2) 发现漏洞

在测试过程中,谛听系统发现mcrypt软件中的一个未知漏洞,该漏洞属于严重的缓冲区溢出类型,攻击者可以通过构造特殊的文件利用该漏洞使被攻击主机执行任意代码。由于该与漏洞相关的缓冲区事先经过检查和限制,所以如果使用传统的随机模糊测试将很难发现该漏洞。另外,谛听触发了mcrypt的一个已知漏洞(CVE-2012-4409), 该漏洞是由于软件在对待解密文件中加盐(salt)过长时无法正常处理导致的缓冲区溢出。