KLEE

原⽂地址:https://www.usenix.org/legacy/event/osdi08/tech/full_papers/cadar/cadar.pdf

作者:Cristian Cadar, Daniel Dunbar, Dawson Engler - Stanford University

翻译:IZAY01

0. 概述

KLEE 是我们推出的一款全新的符号执⾏⼯具,它能够对于各种与环境有密集交互的程序,自动生成实现路径高覆盖率的测试用例。借助于KLEE,我们对 GNU 的核⼼组件中的 89 个独⽴程序进⾏了全方位的测试——这些程序为数百万个 Unix 平台构建了核⼼⽤⼾态环境,可以被认为是当下经过了最为严格的测试的程序的集合。KLEE 为其⽣成的测试⽤例的路径覆盖率很高——平均每个程序达到了 90% 以上(中位数更是超过了 94%)。这个成绩⼤⼤超越了开发者⼿动编写的测试集。而当我们对与其相似的 75 个 BUSYBOX 嵌⼊式系统套件中的程序进⾏测试时,结果表现得更为出⾊。在其中的 31 个程序中,路径覆盖率达到了 100%。

同时,我们也将 KLEE 作为⼀个漏洞扫描器使用,将其应⽤到了 452 个软件应⽤上(这其中包含了超过430,000 ⾏代码),并在其中发掘了 56 个严重的漏洞。其中包含了三个在 15 年间都未曾被发现过的 COREUTILS 中的漏洞。最后,我们使⽤ KLEE 交叉测试了据称是完全相同的 BUSYBOX 和 COREUTILS 的程序集,并在其中找到了逻辑错误和⼤量的不同之处。

1. 简介

诸如程序功能性错误在内的许多编码错误,在不执⾏⼀些程序代码的情况下是很难被发现的。动态测试对于程序来说⼗分重要,但是不论是随机⽣成测试⽤例还是⼈⼯测试的⽅式,都存在实现困难且执⾏效率低下的问题。所以近年来业内对于如何使⽤符号执⾏来⾃动⽣成测试⽤例,做出了许多研究与⼯作。在宏观上,符号执⾏中的变量不再是⼿动⽣成或随机⽣成的具体值,而是在程序执⾏的过程中,作为⼀个未定值的“符号”。符号执行将被测程序的具体输⼊替换成了符号值,并且将相应的指令操作替换成了对于符号的操作。当程序的执⾏路径分⽀含有符号化的变量时,(概念上的)系统会将每条路径分⽀都遍历⼀遍。此时,其中的每条分⽀路径,都包含了⼀系列到达此分⽀所需要的符号值的约束条件,我们称其为“路径约束”。每当⼀条路径执⾏完毕或是触发错误时,⼀个包含了具体值的测试⽤例就会被⽣成。对于已确定的代码,将这条测试⽤例以具体值的形式作为同⼀份已测试的程序的输⼊,程序就会以原先测试时同样的路径执⾏并触发同样的错误。

以上结果总归是可以被保证的。然而,当研究者确定了符号执⾏对于一部分程序能够做到良好的测试覆盖率和漏洞 查找效果时,⼀个新的问题就出现了:符号执⾏对于实际的软件能否做到相同的测试效果呢?我们关注的核⼼问题有两点:1、路径爆炸;2、对于程序与诸如OS、NET等相关环境还有⽤⼾的交互的处理(外部环境问题)。⼤多数过去的研究与⼯作(包括我们的⼯作),通常只报告了⼀组有限的⼿⼯基准测试结果,并且基本没有包括任何关于覆盖率的数据,因此对这两个问题都没有太⼤的帮助。

本篇论⽂主要论述了我们的两点突破。⾸先,我们推出了⼀个全新的、对于各式各样的软件能够发挥强大的深⼊测试能⼒的符号执⾏⼯具—— KLEE。其吸收了我们团队在前⼀个⼯具 EXE 上所积累的数年的经验教训。KLEE 采⽤各种约束求解优化,紧凑地表⽰程序状态,并使⽤试探搜索法获得较⾼的代码覆盖率。此外,KLEE 使⽤了直截了当的⽅案来处理外部环境问题。以上这些特性能够将 KLEE 的性能提⾼⼀个数量级,并做到“开箱即⽤”地检查各种系统交互密集型程序。

其次,我们证实了使⽤ KLEE ⾃动⽣成的测试⽤例,对各种真实的、复杂的和环境密集型的程序,达到了很高的覆盖率。我们最深⼊的⼀次评估,是将 KLEE 应⽤于面向 GNU COREUTILS 的最新稳定版本(版本6.10)中的全部 89 个程序的测试之中。这其中包含了约 80,000 ⾏库代码,和实际实⽤程序中的 61,000 ⾏代码。这些程序在运⾏时,与其所在的外部环境进⾏了⼤量的交互,以实现各种功能。包括管理⽂件系统(例如 ls 、 dd 、 chmod ),显⽰和配置系统属性(例如 logname 、 printenv , hostname ),控制命令调⽤(例如 nohup 、 nice 、 env ),处理⽂本⽂件(例如 sort 、 od 、 patch )等等。它们构建了众多 Unix 系统上的核⼼⽤⼾级环境。数百万⼈每天都在使⽤这些程序,它们中出现的 bugs 能够被及时修复,同时还能定期发布新版本。此外,这些程序与外部环境频繁的交互,正是相当于面向符号执⾏的压⼒测试——而这正是⼀直以来符号执⾏最为薄弱的能⼒。

此外,寻找 COREUTILS 中的 bugs 是⼀项困难的⼯作。因为 COREUTILS 可以称之为现今经过了最为完备的测试的开源程序套件(举例来讲,在 Unix 下,你还有使用的⽐ ls 更频繁的程序吗?)。1995 年对于⼀部分 COREUTILS 程序的随机测试时发现,与 7 个商⽤ Unix 系统相⽐,它们的故障率要明显更低。最后⼀个 COREUTILS 漏洞被上报到SecurityFocus 或 美国国家漏洞数据库,已经是三年前的事情了。

另外,我们同时测试了另外两个 Unix 程序套件:BUSYBOX ——⼀个⼴泛应⽤于嵌⼊式系统的发⾏版,以及 MINIX 的最新发⾏版。最后,我们对 HISTAR 操作系统内核代码进⾏了测试,作为与⽤⼾态程序代码测试的对⽐。

我们的实验分为三类:

  1. 进⾏密集测试以查找 bugs,同时获得较⾼的覆盖率(面向 COREUTILS、HISTAR 和 75 个 BUSYBOX 程序);
  2. 快速运⾏于⼤量应⽤程序来查找 bugs(面向另外的 204 个 BUSYBOX 程序和 77 个 MINIX 程序);
  3. 交叉检查等效程序,以查找更深层的程序错误(面向 67个 BUSYBOX 程序与 COREUTILS 中的 67 个等效程序)。

由此,我们共在超过 452 个程序上运⾏了 KLEE,其中包含了超过 430,000 ⾏代码。据我们所知,这⽐此前的符号执⾏测试、⽣成用例的⼯作,所检查的代码和程序个数要多出了⼀个数量级。

通过实验,我们得到了如下结论:

  1. KLEE 在⼤量复杂程序的测试中,达到了很⾼的覆盖率。其⾃动⽣成的测试⽤例覆盖到了 COREUTILS 中 84.5% 的代码⾏,和 BUSYBOX 中(除去库代码)90.5% 的代码⾏。在对于这些程序的测试中,平均能够覆盖 90% 以上的代码⾏(中位数超过 94%)。并在 16 个 COREUTILS 和 31 个BUSYBOX 程序中达到了 100% 的覆盖率;
  2. KLEE 可以得到⽐起持续集中化的⼿动测试,要显著提⾼的代码覆盖率。在⼤约 89 小时的运⾏中,KLEE ⽣成的对 COREUTILS 的代码覆盖测试⽤例的覆盖率,超出了开发者⾃⼰的测试套件(这是一份持续构建了15年的测试套件)16.8%!
  3. KLEE 在原生应⽤程序上达成了⾼覆盖率的测试结果。 唯⼀的例外是 COREUTILS 中的 sort 函数,需要进⾏⼀次操作来缩减过大的缓冲区,而这会给约束求解器带来了麻烦。
  4. KLEE 还在一些经过了严格测试的代码中,发现了严重 bug。其在 COREUTILS 中发现了10个致命 bugs(包括三个 15 年来都没有被发现的 bug),这些 bugs 造成的程序崩溃次数超过 2006、2007 和 2008 年上报的总和。同时,KLEE 还发现了 BUSYBOX 中的 24 个 bugs,MINIX 中的 21 个 bugs 以及 HISTAR 中的⼀个安全漏洞——共计 56 个严重的 bugs。
  5. KLEE 测试⽤例可以在程序的原代码版本上运⾏(⽐如⽤ gcc 编译得到的)——这⼤⼤简化了调试和错误报告。 例如,所有 COREUTILS 中发现的 bugs 都在两天内得到确认并修复,并且 KLEE ⽣成的测试⽤例也包含在其重新发布的版本中。
  6. KLEE 的能⼒也不仅限于发掘低级编程错误:当⽤于交叉检查据称完全相同的 BUSYBOX 和 GNU COREUTILS 程序时,KLEE ⾃动发现了逻辑错误,和两者的⼤量不⼀致之处。
  7. KLEE 同时也可以应⽤于⾮⽤⼾态程序代码。当应⽤于 HISTAR 内核的测试中时,它的平均代码⾏覆盖率达 76.4%(有磁盘 IO)和 67.1%(⽆磁盘 IO),并发现了⼀个严重的漏洞。

下⼀节将概述我们的⽅法。第 3 节我们将介绍 KLEE,并重点介绍其关键的优化。第 4 节讨论如何对程序运行环境进⾏建模。本⽂的核⼼是第 5 节,于此我们呈现了实验结果。最后,第 6 节介绍了相关⼯作,并在第 7 节作出总结。

2. 综述

本节引导读者通过对 MINIX 中的 tr 工具进行测试来阐述 KLEE 的工作原理。虽然这个小工具的源码只有短短 169 行,但其中的 83 行都是代码。而这 83 行代码恰能很好的用来说明我们测试程序中遇到的两个普遍性问题。

  1. 复杂性tr 的主要功能是从它接收到的输入中转换和删除字符。它将它的功能意图很好地隐藏在了隐式的输入解析代码、棘手的边界条件,和难以追溯的控制流之下。图1中,我们给出了一个具有代表性的代码片段。
  2. 环境依赖性。来自系统环境中的输入值控制了大部分 tr 代码的执行流。命令行参数决定了哪些子程序被执行,输入值则决定了哪条 if 分支被执行,而程序执行则取决于从文件系统读入的能力。同时,程序要能够得当地处理无效或非法的输入。对所有重要的值和边界情况进行测试,这并非一件易事。
1 : void expand(char *arg, unsigned char *buffer) { 					8
2 : 	int i, ac; 														9
3 : 	while (*arg) { 													10*
4 : 		if (*arg == ’\\’) { 										11*
5 : 			arg++;
6 : 			i = ac = 0;
7 : 			if (*arg >= ’0’ && *arg <= ’7’) {
8 : 				do {
9 : 					ac = (ac << 3) + *arg++ − ’0’;
10: 					i++;
11: 				} while (i<4 && *arg>=’0’ && *arg<=’7’);
12: 				*buffer++ = ac;
13: 			} else if (*arg != ’\0’)
14: 				*buffer++ = *arg++;
15: 		} else if (*arg == ’[’) { 									12*
16: 		arg++; 														13
17: 		i = *arg++; 												14
18: 		if (*arg++ != ’-’) { 										15!
19: 			*buffer++ = ’[’;
20: 			arg −= 2;
21: 			continue;
22: 		}
23: 		ac = *arg++;
24: 		while (i <= ac) *buffer++ = i++;
25: 		arg++; /* Skip ’]’ */
26: 		} else
27: 			*buffer++ = *arg++;
28: 	}
29: }
30: . . .
31: int main(int argc, char* argv[ ]) { 								1
32: 	int index = 1; 													2
33: 	if (argc > 1 && argv[index][0] == ’-’) { 						3*
34: 		. . . 														4
35: } 																	5
36: 	. . . 															6
37: 	expand(argv[index++], index); 									7
38: 	. . .
39: }

图1:以上是本文所检查的具有代表性的 MINIX tr 的代码片段。既复杂又隐晦,且难以通过检查或测试进行验证。右侧编号记录了出现于第十八行的错误所经过的执行流的代码行顺序。

这段代码还具有另外两个被测程序中普遍存在的特性。首先,它含有 bugs,而这正是 KLEE 生成测试用例与进行检测的目的。其次,KLEE 能够于其上很快达成可观的路径覆盖率:KLEE 在两分钟内为其生成了 37 条测试用例,覆盖了程序中的所有路径。

KLEE 有两个目标:(1)覆盖所有程序中的路径;(2)在输入触发程序错误时,能够探测每个危险操作(如解引用、断言)。KLEE 通过符号执行来达成目标:不同于直接执行程序时,指令自操作数获取具体值。符号执行生成到达这条路径所要求的变量值的约束条件。而当 KLEE 探测到错误发生,或程序进行了 exit 系统调用时,KLEE 就对当前路径的约束条件进行约束求解,由此为程序的原始版本生成能够完全复现路径的测试用例。

KLEE 的设计,旨在生成测试用例,使得原始程序所遵循的路径始终遵循 KLEE 测试时所采用的相同路径(即没有误报)。然而,KLEE 所检查的代码和 bugs 中的不确定性,在实践过程中产生了误报。结合 gdb 和 gcov 等标准工具,在 KLEE 之外重新运行测试的能力,对于诊断此类错误并验证我们的结果来说非常宝贵。

接下来我们会展示 KLEE 的使用方法,并给出关于 KLEE 工作方式的综述。

2.1 使用方式

使用者可以很方便地使用 KLEE 来开始他的对于许多真实程序的测试任务:通常情况下 KLEE 是不需要源代码层面的定制,或是一些人工修改,就能够很好的完成工作的。用户首先需要使用公开发布的 LLVM for GNU C,将程序的源码编译成 LLVM 字节码。如我们使用了如下命令编译 tr

llvm-gcc --emit-llvm -c tr.c -o tr.bc

然后,用户在生成的 LLVM 字节码的层面上运行 KLEE。并可以对被测程序指定符号输入的数量、大小和类型。对于 tr,我们使用如下命令:

klee --max-time 2 --sym-args 1 10 10 --sym-files 2 2000 --max-fail 1 tr.bc

这条命令的第一个参数 --max-time,告诉 KLEE 对于 tr.bc 至多运行两分钟测试。其余参数则描述了符号化输入。--sym-args1 10 10 参数说明了我们使用 0 来填充三个命令行参数。其中,第一个命令行参数长度为 1 字符,其余两个长度为 10 字符。--sym-files 2 2000 则用于说明要使用标准输入和一个文件,这两者都包含了 2000 字节的符号化数据。最后,--max-fail 1 参数规定了,在每条测试路径上最多只能出现一次失败的系统调用(详见 4.2 节)。

2.2 使用 KLEE 进行符号执行

当对 tr 进行测试时,KLEE 成功找到了如图 1 第 18 行中的缓冲区溢出,并生成了能够触发该溢出的测试用例(tr [ "" "")。依照上一节中的参数,KLEE 是这样对 tr 进行测试的:

  1. KLEE 构建了符号化的命令行参数。这些命令行参数仅有“以 \x00 结尾”这一项约束条件。其余的约束条件则是:命令行参数的数量是 0~3 个,它们的大小则分别是 1、10、10。然后,KLEE 以这些初始约束条件来调用 main 函数。
  2. 当 KLEE 运行到第 33 行对应的 argc > 1 的分支时,它使用其约束求解器 STP 来查看在当前路径条件下,可以有哪些执行方向。对于这个分支,有两个可能的执行方向;KLEE 此时 fork 一份新的执行进程,同时跟踪这两条路径,并为它们分别添加 argc > 1argc ≤ 1 的约束条件。
  3. 当有多条可用路径时,KLEE 必须决定先对哪条路径进行符号执行。相应的算法我们会在 3.4 节再论述。我们暂定会触发 bug 的路径此时被优先执行。这样一来,KLEE 会向 arg 的内容添加更多的约束条件,并总共 fork 五次(对应图中标记了“*”的代码行):第 33 行处 fork 两次,然后在第 3、4 行各 fork 一次,最后在 expand 函数中的第 15 行处fork 一次。
  4. 对于每一次危险操作(如指针的解引用),KLEE 都会检查是否有满足当前路径约束条件的值能够触发错误。在注解出的那条路径中,KLEE 在第 18 行之前没有探测到错误。但是同时 KLEE 确信这条路径上存在能够使得 arg 的读入值越界的输入:在第 15 行处进入 true 分支之后,arg 两次递增,且没有检查字符串是否结束。此时若字符串已结束的话,递增的索引会导致越过 C 字符串末尾的“\x00”并指向无效的内存。
  5. 此时 KLEE 会生成包含了 argc 和 argv 具体值的测试用例(例如 tr [ "" "")。这样一来,当再次运行原始版本的 tr 时,同样的 bug 会再次被触发。然后,会再添加一个使得 bug 不被触发的约束条件后,对当前路径继续进行符号执行。

3. KLEE 的软件架构

KLEE 是对我们此前作品 EXE 完全重构的结果。概括来说,KLEE 是符号执行的控制系统和 LLVM 字节码解释器之间的混合体。每个符号化进程都有一个寄存器文件、栈、堆、程序计数器和路径约束条件。 为了避免与 Unix 进程产生概念上的混淆,我们将 KLEE 的符号化进程的表示称为 state。同时,被测程序被编译为 LLVM IR——这是一种类似于 RISC 的虚拟指令集。KLEE 直接对 LLVM IR 进行解析,并不采用近似(如在 bit 层面的精度)地将其中的指令映射为约束条件。

3.1 基本架构

在任意时刻,KLEE 都可能正在执行大量 state。KLEE 的核心是其解释器中的主循环,该循环选择要运行的 state,然后在该 state 的上下文中符号化地执行一条指令。主循环将一直执行到没有剩余 state,或达到用户定义的超时方才停止。

与一般的进程不同,state 的存储(寄存器、栈和堆的对象)存放的是约束条件表达式(树),而不是具体的数据值。表达式树的叶子是符号变量或常量,内部节点则来自 LLVM IR 定义的操作(例如,算术运算,位运算,比较操作和内存访问操作)。而常数表达式的存储位置被认为是具体的

对于大部分指令的符号执行过程是直截了当的。例如,以符号化的方式执行如下 LLVM IR 指令:

%dst = add i32 %src0, %src1

此时,KLEE 将从 %src0 寄存器和 %src1 寄存器读取加数,并向 %dst 寄存器写入新约束表达式 Add(%src0,%src1)。为了提高执行效率,生成表达式的代码将检查所有给定的操作数是否都为具体值(即为常量),如果是,则就地执行操作,并返回对应的常量表达式。

条件分支路径接收布尔表达式作为分支条件,并根据其值的真假,来更改 state 的指令指针。KLEE 通过向约束求解器发起查询,以确定分支条件沿当前路径是否能够推定真假;若分支条件能够确定真假,则用适当的地址值更新指令指针。否则,两个分支路径都是有可能的:此时 KLEE 会克隆当前 state,以便对两个路径都进行探索,并相应地更新每个路径上的指令指针和路径条件。

潜在的危险操作会隐式地生成新的分支路径,以检查是否存在任何可能导致错误的输入值。例如,除法指令会生成一个检查“除 0 错误”的分支路径。这种分支路径实际上与一般分支路径没有什么不同。因此,即使当检查成功(即检测到错误)时,符号执行仍会继续在错误路径上进行,并将检查的否条件添加为路径约束条件(例如,除数不为零)。如果检测到错误,则 KLEE 会生成一个测试用例以触发该错误,同时终止该 state。

与其他危险操作一样,KLEE 也会为读取和写入指令生成相应的检查:其任务是检查操作地址是否指向未越界的、有效内存对象。但是,读取和写入指令会带来额外的复杂性。被测程序使用的内存最直接的表示形式是一维的字节数组。在这种情况下,读取和写入指令将被简单地分别映射到对于数组的读取和写入表达式上。不巧的是,我们的约束求解器 STP 几乎无法求解其结果约束(不过我们知道的其他约束求解器也同样做不到)。因此,和在 EXE 中的做法一样,KLEE 将被测程序中的每个内存对象映射到了不同的 STP 数组(在某种意义上,可以说成是将一维地址空间映射到了分段的地址空间)。因为这种表示形式使得 STP 可以忽略所有未被已知约束表达式引用的数组,故由此极大地提高了性能。

许多操作(例如边界检查或对象级写时复制)需要对象特定的结构信息。如果一个指针可以指向多种不同的对象,则这类操作将变得难以处理。为了简洁性,KLEE 避开了下述问题。在当前 state 中的已经解引用的指针 p 可以指向 N 种对象时,KLEE 会将此 state 克隆 N 次。对于每个 state,它将 p 设定为指向其中一种特定对象类型的指针,然后执行合适的的读取或写入操作。尽管这种方法对于处理那些可能指向很多种对象的指针来说开销过大,然而实际上,我们测试过的大多数程序仅会使用指向单种对象的符号化指针。并且针对这种情况,KLEE 也进行了相应的优化。

3.2 精小的 state 表示

在实际的测试中 state 的数量增长是非常迅速的:即使是对于一些小型程序的测试中,仅仅在最开始几分钟内,很多情况下也会并发地生成数以万计的 state。当我们使用 1GB 内存容量对 COREUTILS 进行符号执行时,记录下来的并发状态最大数量为 95982(对于 hostid),每个工具的最大并发 state 的平均值为 51385。路径爆炸问题使得每个 state 占用的内存大小变得至关重要。

由于 KLEE 会跟踪所有内存对象,因此它可以在对象级别(而不是页面粒度)实现写时复制,从而大大降低了每个 state 的内存需求。同时通过将堆实现为不可变的映射,堆结构本身的某些部分也可以在多个 state 之间共享(类似于在 fork() 上共享页表的某些部分)。此外,可以在常数时间内克隆此堆结构——这对于这种操作的频率来说是很重要的。

这种做法与 EXE 形成鲜明对比——EXE 中的每个 state 都要使用一个本机 OS 进程。将 state 的表示与操作交由 KLEE 内部处理的方法,可通过减少每个 state 的开销,并允许 state 在对象(而不是页面)级别共享内存来显着增加可同时探索的 state 数。此外,这大大简化了在所有 state 下的缓存和启发式搜索的实现。

3.3 查询优化

几乎所有情况下,都是约束求解的开销凌驾于其它所有事务之上——这不足为奇,因为 KLEE 会为 NP 完全性逻辑生成复杂的查询。因此,我们在简化约束表达式的技巧上花费了很多精力,并且在达到 STP 之前最好消除查询操作(没有查询是最快的查询)。简化查询的做法可以加快约束求解的速度,同时减少内存消耗并提高查询缓存的命中率(请参见下文)。我们做出的主要的查询优化如下:

表达式重写。最基本的优化反映了编译器中的优化:例如,简单的算术化简(x + 0 = x),计算开销的降低(x * 2^n = x << n),线性化简(2*x - x = x)。

约束集简化。符号执行通常涉及向路径条件添加大量约束条件表达式。程序的一般结构意味着,对相同变量的多个约束的结合,会使得总的约束条件更接近具体值。例如,通常会添加不精确的约束(例如x < 10),然后在一段时间后添加约束 x = 5。当将新的等式约束添加到约束集时,KLEE 会通过重写先前的约束来主动简化约束集。在此示例中,将 x 的值替换为第一约束的做法,将约束条件化简为 true,而 KLEE 则将其消除。

求解隐含的具体值。当将诸如 x + 1 = 10 的约束添加到路径的约束条件时,符号化的变量 x 在这条路径上实际已经是具体值了。 KLEE 能够在确定这一点(在这种情况下,x = 9)的同时,用 x 的具体值写回内存中。这样可以确保对该内存的后续访问请求可以返回开销很小的常量表达式。

独立的约束条件。就引用的内存位置而言,许多约束条件并不重叠。约束条件的独立性(继承自 EXE)要求的是要基于约束变量集引用的符号变量,来将其划分成不相交的独立子集。通过显式跟踪这些子集,KLEE 可以在在一次查询被发送到约束求解器之前,高频地消除不相关的约束。例如,对于给定的约束集 {i < j,j < 20,k > 0},查询 i = 20 是否仅需要前两个约束条件。

反例缓存。冗余的查询在符号执行过程中出现的频次很高,简单的缓存可以有效地消除大量冗余的查询。但是,由于约束集的特殊结构,构建更复杂的缓存是可能的。反例缓存将约束集映射到反例(即变量赋值),同时在一组约束条件无解时,使用特殊的标记。这种映射存储在自定义数据结构中,该数据结构派生自 Hoffmann 和 Hoehler 的 UBTree 结构[28]。使用这种自定义的数据结构能够高效地搜索约束集的子集和超集的缓存条目。通过以这种方式存储缓存内容,反例缓存获得了三种额外的消除冗余查询的方式。在下面的示例中,我们假设反例缓存当前具有 {i < 10,i = 10}(无解)和 {i < 10,j = 8}(有解,变量分配为 i→5, j→8)的约束条件。

  1. 当约束集的子集无解时,原约束集也无解。向无解的约束集添加约束不能让其因此就有解。例如,给定上述缓存,对于 {i <10,i = 10,j = 12} 这一组约束条件,我们能够迅速确定其不能被满足。
  2. 当约束集的超集具有解时,则其解也满足原约束集。从约束集中删除约束不会就使得该解无效。例如,分配 i→5,j→8 分别满足 i < 10j = 8
  3. 当约束集的子集有解时,此解也可能也是原约束集的解。这是因为额外的约束通常不会就使得子集的解无效。因为检查潜在的解的开销很小,所以 KLEE 尝试用所有的解去替换约束集的子集。如果找到,则返回满足的解。例如,约束集 {i < 10,j = 8,i ≠ 3} 仍可以通过 i→5, j→8 来满足。

为了证明这些优化方案的有效性,我们进行了一项实验—— COREUTILS 应用程序在关闭了这两个优化的情况下运行了5分钟的符号执行。然后,我们重新运行了完全相同的,且具有约束独立性的执行工作,并且针对相同数量的指令分别和一起启用了反例缓存。该实验是在大量 COREUTILS 程序样本上完成的。表 1 中的结果显示了实验结果的均值。

Optimizations Queries Time (s) STP Time (s)
None 13717 300 281
Independence 13717 166 148
Cex. Cache 8174 177 156
All 699 20 10

表 1:在 COREUTILS 上进行 KLEE 求解器优化的性能比较。每个程序在没有优化的情况下运行 5 分钟,然后在给定的优化下以相同的工作负载重新运行。表中结果是所有程序的平均值。

不出所料,独立性优化本身不会消除任何查询,但是它执行的简化将整个符号执行的运行时间减少了将近一半(45%)。反例缓存将运行时间和 STP 查询数量都减少了40%。但是只有两个优化被同时开启时,才会显示其真正威力。 在这种情况下,由于首先通过独立性优化简化了查询,因此反例缓存的命中率大大提高。在对样本的测试中,STP 查询的平均次数减少到原始数量的 5%,平均运行时间减少了超过一个数量级。

对于 STP 时间(解决查询所花费的时间)主导运行时间的程度也是值得注意的。对于原始运行,STP 的用时平均占整体执行时间的 92%(组合优化将此减少了几乎300%)。启用两个优化后,该百分比下降到41%。最后,图2显示了 KLEE 优化的效果,是随时间而增加、反例缓存的填充和查询大小的增加,其优化的速度也随之提高的。

SC_20210218_115506.png

图2:随着时间的流逝,缓存的填充和查询变得更加复杂,KLEE 求解器优化的效果随之变得更加有效。规范化了已执行指令的数量,以便可以在所有程序中聚合数据。

3.4 state 调度

KLEE 通过交错选择以下两种搜索启发式方法,来选取对于每条指令要运行的 state。

随机路径选择:维护一个二叉树,记录所有 active state 所遵循的程序路径,即树的叶子是当前 state,内部节点是执行分支的位置。 通过从树根遍历此树并随机选择要在分支点遵循的路径来选择 state。因此,当到达分支点时,无论子树的大小如何,每个子树中的 state 集都具有相等的被选择概率。此策略具有两个重要属性。首先,它偏爱分支树中层级较高的 state。 这些 state 对其符号输入的约束较少,因此具有更大的自由来获取未覆盖的代码。其次,也是最重要的一点是,当程序的某些部分快速创建新 state(“fork 暴涨”)时,这种策略可以避免资源耗尽——高密度循环包含一个符号化时会导致这一现象。注意,简单地随机选择 state 也是没有属性的。

覆盖率优化搜索:尝试尽力选择那些有着即将覆盖新代码的可能性的 state。KLEE 使用启发式方法为每个 state 计算权重,然后根据这些权重随机选择一个 state。 当前,这些启发式方法要纳入计量到的是:到一条尚未被覆盖指令的最小距离,state 的调用堆栈,以及该 state 最近是否覆盖到了新代码。

KLEE 以循环方式使用每种策略。这种做法虽然会增加那些采取了定制策略来实现较高覆盖率时所花费的时间,但也可以防止个别策略被阻塞。此外,由于策略是从相同的 state 池中选取的,因此对它们进行交替使用可以提高整体效率。

执行单个指令的时间,在简单指令(例如加法)和可能使用约束求解器或派生执行(分支,内存访问)的指令之间的差异很大。KLEE 通过由最大指令数和最大时间量所定义的“时间片”,来控制 state 的运行时间,确保频繁执行昂贵指令的 state 不会占主导地位。

4. 环境建模

当代码从其环境中读取值(命令行参数,环境变量,文件数据和元数据,网络数据包等)时,我们从概念上讲希望返回读取可合法产生的所有值,而不仅仅是单个具体值。当向所处环境写入内容时,相应的影响应仍会反映在后续读取中。这些行为的组合使被检查的程序能够探索所有可能的动作,并且仍然没有误报。

机械地讲,我们通过将访问环境的调用,重定向到能够充分理解所需动作的语义的模型,进而生成所需约束以处理环境建模问题。至关重要的是,这些模型是用普通的 C 代码编写的,用户可以轻松地对其进行自定义、扩展甚至替换,而无需了解 KLEE 的内部结构。我们用了大约 2500 行代码来定义大约 40 个系统调用的简单模型(例如,open, read, write, stat, lseek, ftruncate, ioctl)。

4.1 例:对文件系统进行建模

对于每个文件系统操作,我们检查该操作是针对磁盘上的实际具体文件还是符号文件。对于具体文件,我们只需在运行的操作系统中调用相应的系统调用即可。对于符号文件,我们模拟了该操作对每个 state 专有的简单符号文件系统的影响。

图 3 给出了 read() 模型的概略图,省略了处理软链接、对标准输入的读取操作,和失败的详细信息。该代码维护在文件 open() 处创建的一组文件描述符,并为每个文件记录相关的文件是符号文件还是具体文件。如果 fd 引用了一个具体文件,我们将使用操作系统通过调用 pread() 来读取其内容(第7-11行)。我们使用 pread() 将来自 KLEE 多个 state 的访问复用到一个实际的基础文件描述符。如果 fd 引用了符号文件,则 read() 从保存文件内容的底层符号缓冲区将内容复制到用户提供的缓冲区中(第13-19行)。这样可以确保访问同一文件的多个 read() 调用使用一致的符号值。

1 : ssize t read(int fd, void *buf, size t count) {
2 : 	if (is invalid(fd)) {
3 : 		errno = EBADF;
4 : 		return −1;
5 : }
6 : struct klee fd *f = &fds[fd];
7 : if (is concrete file(f)) {
8 : 	int r = pread(f−>real fd, buf, count, f−>off);
9 : 	if (r != −1)
10: 		f−>off += r;
11: 	return r;
12: } else {
13: 	/* sym files are fixed size: don’t read beyond the end. */
14: 	if (f−>off >= f−>size)
15: 		return 0;
16: 	count = min(count, f−>size − f−>off);
17: 	memcpy(buf, f−>file data + f−>off, count);
18: 	f−>off += count;
19: 	return count;
20: 	}
21: }

图3:KLEE 的 read() 模型示意图。

我们的符号文件系统很粗糙,仅包含一个目录,其中包含N个符号文件。 KLEE用户同时指定数字N和这些文件的大小。 该符号文件系统与实际文件系统共存,因此应用程序可以同时使用符号文件和具体文件。当程序以具体名称调用 open 时,我们(尝试)打开实际文件。因此,调用:

int fd = open("/etc/fstab", O_RDNLY);

将 fd 设置为指向实际配置文件 /etc/fstab

另一方面,以不受限制的符号名称调用 open() 会依次匹配 N 个符号文件中的每个符号文件,并且也会失败一次。例如,给定 N = 1,使用符号命令行参数argv [1]调用 open() :

int fd = open(argv[1], O_RDNLY);

将产生两条路径:一条路径 fd 指向环境中的单个符号文件,另一条路径将 fd 设置为 -1 表示错误。

毫不奇怪,选择哪种模型接口对模型的复杂性影响很大。与其在系统调用级别拥有模型,不如在 C 标准库级别(fopen,fread 等)进行建模。这样做具有潜在的性能优势,对于具体的代码,我们可以在本地运行这些操作。 但是,主要缺点是标准库包含大量函数 —— 为每个函数编写模型的工作十分繁琐且容易出错。通过仅对简单得多的低级系统调用 API 进行建模,我们只需编译 C 标准库的许多实现之一(我们使用uClibc [6]),即可获得更丰富的功能,并让它去关心正确性。作为副效果,我们也同时检查了库中是否有错误。

4.2 失败的系统调用

实际环境可能会以意外方式失败(例如,write() 由于磁盘已满而失败)。此类故障通常会导致无法预料且难以诊断的错误。即使应用程序确实尝试处理它们,回归套件也很少充分地使用此代码。 为了帮助捕获此类错误,KLEE 将有选择地通过以受控方式使系统调用失败来模拟环境故障(类似于[38])。 我们将这种模式设置为可选,因为并非所有应用程序都关心故障 —— 一个简单的应用程序可能会忽略磁盘崩溃,而邮件服务器会花费大量代码来处理故障。

4.3 测试用例的重新运行

通过将 KLEE 生成的测试用例提供给我们提供的重放驱动程序,可以在未修改的本机二进制文件上重新运行它们。各个测试用例描述了符号环境的一个实例。驱动程序使用此描述来创建实际的操作系统对象(文件,管道,ttys,目录,链接等),其中包含测试用例中使用的具体值。然后,它使用测试用例中的具体命令行参数执行原始程序。我们最大的挑战是使系统调用在 KLEE 之外失败 —— 我们构建了一个简单的程序,该程序使用 ptrace 调试接口跳过应该失败的系统调用,而不是返回错误。

5. 评估

本节描述了我们对 COREUTILS(第5.2节)和 BUSYBOX(第5.3节)深入的覆盖测试实验,以及在快速漏洞挖掘过程中所发现的漏洞(第5.4节)。我们使用 KLEE 通过交叉检查等效工具(第5.5节)来发现深层的逻辑错误,并以给出 HISTAR 的测试结果作结(第5.6节)。

5.1 覆盖方法

我们使用行覆盖率作为 KLEE 产生的测试用例有效性的保守度量。因为 gcov 报告的可执行行覆盖率具有权威性,所以我们选择了它作为测试标准。当然,它完全低估了 KLEE 的符号执行路径遍历有多彻底,因为它忽略了 KLEE 会探索具有所有可能价值的许多不同独特路径这一事实。我们希望基于路径的指标会取得更大的成功。

我们在每个程序的独立版本上运行 KLEE 生成的测试用例,并使用 gcov 来衡量覆盖率。独立于 KLEE 运行测试的做法消除了 KLEE 自身的 bug 可能会产生的影响,并验证了生成的测试用例是否覆盖到了它所声明的代码。

注意,我们的覆盖范围结果仅考虑程序本身所含有的代码。这个过程是不计入库代码的,因为这样做会使得难以对测试结果作出解释:

  1. 由于很多应用程序经常调用相同的库函数,因此许多相同的库代码会被重复计入。
  2. 这会不公平地低估覆盖率。通常,应用程序调用的库函数的大部分实际上是无效代码,因为库代码是通用的,而调用指令却不是。例如,printf 非常复杂,但是调用 printf(“hello”) 只会使用到 printf 函数体中的一小部分代码(而不会使用用于打印整数,浮点数,格式等的代码)。

但是,在测量应用程序的原始大小时,我们确实包括了库代码:KLEE 必须成功处理该库代码(并且这样做没有功劳),才能在工具本身中执行代码。 我们通过计算全局优化后最终可执行文件中可执行代码行的总数,来计算可执行代码行(ELOC)的大小,从而消除了未调用的函数和其他无效代码。该度量通常比简单的行数(使用wc -l)小三倍。

在我们的实验中,KLEE 仅通过针对在主应用程序代码中命中新语句或分支的路径生成测试用例,从而将其生成的测试用例最小化。对于希望提高库代码覆盖率的用户,可以更改此设置。

5.2 GNU COREUTILS

现在,我们给出所有 89 个 GNU COREUTILS 实用程序的 KLEE 覆盖结果。

图4按可执行代码行(ELOC)细分了这些工具,包括该工具调用的库代码。 虽然相对较小,但这些工具不是玩具,最小的五种工具的ELOC在2K和3K之间,一半以上的工具(52)的工具在3K和4K之间,而十种的工具在6K以上。

SC_20210218_142732.png

图4:直方图显示了具有给定数量的可执行代码行(ELOC)的COREUTILS工具的数量。

包括我们在内的以前的工作,已经在少数手动选择的基准上评估了基于约束的执行。 报告整个 COREUTILS 套件的结果,无论是最差还是最好的,都使我们无法手动选择结果,或者通过使用脆弱的优化而无意间作弊。

几乎所有工具都使用相同的命令进行了测试(第2.1节中说明了命令参数):

./run <tool-name> --max-time 60
				  --sym-args 10 2 2
				  --sym-files 2 8
				  [--max-fail 1]

如–max-time选项所指定,我们将每个工具运行了大约60分钟(有些在此限制之前完成,在之后的三分钟内完成)。 对于这些值的覆盖率结果不令人满意的八个工具,我们查阅了手册页,并增加了参数和文件的数量和大小。 我们发现这很容易做到,因此大概是工具实施者或用户也是如此。 这些运行完成后,我们通过使系统调用失败来改进它们(请参见第4.2节)。

行覆盖率结果

表2中的前两列给出了汇总的行覆盖率结果。平均而言,我们的测试覆盖了每个工具中90.9%的行(中位数:94.7%),所有工具的整体(总计)覆盖率为84.5%。 我们在16种工具上获得100%的行覆盖率,在56种工具上获得90%的行覆盖率,在77种工具上占80%的覆盖率(占所有工具的86.5%)。 所有工具的最低覆盖率是62.6%。

SC_20210218_143514.png

表2:在KLEE和开发人员测试的给定范围内达到行覆盖率的COREUTILS工具的数量(不包括库代码)。 最后一行显示了每种方法实现的总覆盖率以及每个应用程序的平均覆盖率和中值覆盖率。

我们认为,如此高的覆盖率“开箱即用”的广泛应用令人信服地显示了该方法的强大功能,尤其是因为它遍及整个工具套件,而不是专注于某些特定的应用程序。

重要的是,KLEE生成的测试用例很少,因此覆盖率很高:对于我们的不失败的测试,它总共需要进行3,321次测试,平均每个工具需要37次(中位数:33)。 所需的最大数量是129(对于“ [”工具),而工具 six 需要的数量是 5。作为路径复杂性的粗略度量,我们使用gcov计算了每个测试用例运行的静态分支的数量(即,执行的分支计数一次,否则 无论分支动态运行了多少次)。 平均路径长度为76(中位数:53),最大值为512,(选择随机数)160为至少250个分支。

图5显示了在有或没有失败的系统调用调用的情况下,每种工具实现的KLEE覆盖率。命中系统调用故障路径对于获得高覆盖率的工具的最后几行很有用,而不是显着改善总体结果(从79.9%提高到84.5%)。 一个例外是pwd,它要求系统调用失效率从惨淡的21.2%达到72.6%。 单个工具的第二个最佳改进是df工具,其额外覆盖率要低了13.1%。

SC_20210218_143333.png

图5:每个应用程序在没有失败系统调用的情况下的线路覆盖。

5.2.2与开发人员测试套件的比较

COREUTILS中的每个实用程序都带有广泛的手动编写的测试套件,每次添加新的错误修复程序或其他功能时,该套件都会扩展。 如表2所示,KLEE在所有综合指标上均轻松胜过开发人员测试:总行覆盖率(84.5%对67.7%),每个工具的平均覆盖率(90.9%对68.4%)和每个工具的中值覆盖率(94.7%对72.5%) 。 在更详细的级别上,KLEE在16种工具上的覆盖率达到100%,在56种工具上的覆盖率超过90%,而开发人员测试在单个实用程序上的覆盖率达到100%(true),而在7种工具上覆盖率达到90%以上。 24种工具的覆盖率低于60%,而KLEE始终达到60%以上。 总的来说,运行KLEE的89小时(每个应用大约1个小时)比15年内构建的测试套件的覆盖范围大16.8%!

图6给出了KLEE与开发人员测试的相对视图,方法是从KLEE命中的行中减去手动测试命中的行,然后将其除以可能的总数。 大于零的条形表示KLEE胜过了手动测试(以及成功率)。 下面的条显示相反的意思。 在绝大多数应用程序中,KLEE常常胜过手动测试。

SC_20210218_143832.png

图6:KLEE和COREUTILS手动测试套件之间的相对覆盖率差异,是通过从KLEE测试(Lklee)中减去手动测试(Lman)覆盖的可执行代码行,然后除以总可能值而得出的:(Lklee-Lman)

为了防止行覆盖率出现隐性偏差,我们还比较了手册和KLEE测试套件的分支覆盖率(由gcov报告)。 虽然两个测试套件的绝对覆盖率都下降了,但KLEE在开发人员测试方面的相对改进仍然存在:KLEE总体分支覆盖率达到76.9%,而开发人员的测试仅获得56.5%。

最后,需要注意的是,尽管KLEE的运行在覆盖率方面大大超过了开发人员的测试,但KLEE仅检查低级错误和违反用户级断言的情况。 相反,开发人员测试通常会验证应用程序的输出是否与预期的相匹配。 我们通过对照不同实现产生的输出来验证这些实用程序的输出来部分解决此限制(请参见第5.5节)。

漏洞挖掘

KLEE在COREUTILS中发现了十个独特的错误(通常是内存错误崩溃)。 图7提供了用于触发它们的命令行。 前三个错误至少自1992年以来就存在,因此从理论上讲,任何COREUTILS分布最高为6.10都应崩溃。 其他的则是较新的,不会使较旧的COREUTILS发行版本崩溃。 虽然开发人员的未发布版本中已修复了一个(以序列形式)错误,但其他错误已在报告后的两天内得到确认并修复。 此外,KLEE生成的针对新错误的测试用例的版本已添加到官方的COREUTILS测试套件中。

SC_20210218_144137.png

图7:在Pentium机器上使用SELinux在Fedora Core 7和Fedora Core 7上运行时,KLEE生成的命令行和输入(为便于阅读而进行了修改)在COREUTILS 6.10版中导致程序崩溃。

作为说明性示例,我们讨论了图7中调用“ pr -e t2.txt”击中的pr中的错误(用于在打印前对文件进行分页)。包含该错误的代码如图8所示。 遇到错误,每个输入制表符的字符数和每个c制表符的字符数等于制表符宽度(我们称其为T)。 行2665使用行602上的宏计算宽度=(T-输入位置mod T)。错误的根本原因是错误的假设,即0≤x mod y <y,仅适用于正整数。 当输入位置为正时,宽度将小于T,因为0≤输入位置mod T <T。 但是,在存在退格的情况下,输入位置可能变为负值,因此(-T <输入位置mod T <T)。 因此,宽度可以高达2T − 1。

 602: #define TAB WIDTH(c , h ) ((c ) − ((h )%(c )))
...
1322: clump buff = xmalloc(MAX(8,chars per input tab));
. . . // (set s to clump buff)
2665: width = TAB WIDTH(chars per c, input position);
2666:
2667: if (untabify input)
2668: {
2669: 	for (i = width; i; −−i)
2670: 		*s++ = ’ ’;
2671: 	chars = width;
2672: }

图8:pr的代码片段,如果每个输入选项卡的字符数==每个c的字符数且输入位置<0,则可能通过指针s导致块状buff的内存溢出。

当代码分配大小为T的缓冲区块buff(第1322行),然后通过指针s(最初设置为块buff)将宽度字符写入此缓冲区(行2669–2670)时,就会出现该错误。 因为宽度可以大到2T -1,所以可能发生内存溢出。

这是一个象征性执行能力,可以发现很难手动推理的代码中的复杂错误,这是一个典型的例子-该错误至少在1992年就存在于pr中,当时COREUTILS首次添加到CVS存储库中。

5.2.4 与随机测试的比较

我们认为,COREUTILS手动测试非常全面。 但是,我们与随机测试进行比较,既可以预防缺陷,也可以了解基于约束的推理与盲目随机猜测的比较。 我们试图通过构建一个使用与KLEE相同的命令行,并为输入的指定类型,数量和大小范围生成随机值的工具来进行比较。 然后,它使用与KLEE相同的重播基础结构在这些值上运行检查的程序。 出于时间原因,我们随机选择了15个基准测试(如图9所示)并使用与KLEE运行时相同的命令行运行了65分钟(以始终超过给KLEE的时间)。

SC_20210218_144634.png

图9:针对15种随机选择的COREUTILS实用程序的随机测试,手动测试和KLEE测试的内容。 手动测试平均胜过随机,而KLEE胜过两者。

图9显示了通过随机,手动和KLEE测试实现的这些程序的覆盖范围。 毫不奇怪,考虑到COREUTILS程序的复杂性和COREUTILS维护人员的共同努力,手动测试的覆盖率远胜于随机测试。 KLEE轻松击败了两者。

由于gcov会带来一些开销,因此我们还进行了第二个实验,其中我们在没有gcov的情况下在本地运行了每个工具65分钟(使用与第一次运行相同的随机种子),记录了生成的测试用例的数量,然后使用gcov重新运行了相同的数量。 此运行完全消除了gcov开销,总体而言,它生成的测试比初始运行多44%。

但是,这44%的额外测试仅将每个工具的平均覆盖率提高了1%,而15个实用工具中有11个没有任何改善-这表明大多数应用程序都存在随机性。 我们在以前的工作中已经多次看到这种模式:随机很快就能得到情况,然后一遍又一遍地重新审视它们。 直观地讲,即使要满足单个32位相等性,也需要正确地猜测40亿个值中的一个。 正确获得一系列这样的条件是没有希望的。 诸如csplit(性能最差的工具)之类的实用程序很好地说明了这种动态:它们的输入具有结构,并且盲目猜测满足其规则的值的难度导致大多数输入被拒绝。

一个出乎意料的结果是,对于这15个程序中的11个,KLEE探索终止的路径(即,被检查的代码调用exit())仅比random慢几倍! KLEE大致在同一时间探索了三个程序的终止路径,实际上,对于其他三个程序(seq,tee和nohup)实际上要更快。我们对这些数字感到惊讶,因为我们假设基于约束的工具在每个路径上的运行速度要比原始测试慢几个数量级,但是随着时间的推移(具有所有值),它具有探索更多独特路径的优势。因为它没有卡住。尽管四个程序的开销都符合预期(约束求解器的开销使路径的运行速度比本地执行慢了7倍至220倍),但其他程序的性能折衷却更加细微。假设我们在程序的深处有一个分支。要使用传统测试覆盖正确和错误的方向,就需要从头到尾运行两次程序:一次是正确的路径,一次是错误的路径。相比之下,虽然KLEE比本地执行慢地运行每个指令,但它只需要在分支之前运行一次指令路径,因为它在分支点派生执行(鉴于其对象级写时复制实现,这是一种快速操作)。随着路径长度的增加,这种避免冗余重新运行路径前缀的能力变得越来越重要。

话虽如此,读者应该将随机和KLEE的每路径成本视为非常粗略的估算。首先,KLEE基础架构随机用于运行测试,这增加了约13ms的每次测试开销,而仅从脚本中调用程序的开销约为1ms。该代码在沙盒目录中运行每个测试用例,创建一个干净的环境,并创建具有随机内容(例如文件,管道,tty的内容)的各种系统对象。然后,它使用看门狗运行经过测试的程序以终止无限循环。尽管专用的测试工具必须执行大致类似的操作,但是大概可以节省几毫秒。但是,此固定成本仅对短暂的程序运行至关重要,例如在代码退出并出现错误时。在随机可以真正取得进展并探索更深的程序路径的情况下,重新运行路径前缀的低效率开始占主导地位。此外,我们保守地计算KLEE的路径完成率:当其时间到期时,它所创建的状态中大约有30%仍然存在,并且我们对此不作保证。

5.3 BUSYBOX实用程序

BUSYBOX是嵌入式系统的标准UNIX实用程序的广泛使用的实现,其目标是小的可执行文件[1]。 尽管经常提供较少的功能,但它的目的是复制COREUTILS功能。 我们在错误修正的BUSYBOX 1.10.2版本上进行了实验。 我们使用与检查COREUTILS时相同的命令行在BUSYBOX“ coreutils”子目录(14K行代码,另外16K库代码)中运行75个实用程序8,但我们没有使系统调用失败。

如表2所示,KLEE的性能甚至优于COREUTILS:总线覆盖率超过90.5%,平均每把工具覆盖93.5%,中位数为97.5%。 它在31个组件中获得了100%的覆盖率,在55个组件中获得了90%以上的覆盖率。

BUSYBOX的手动测试套件不如COREUTILS全面(实际上,许多应用程序似乎没有任何测试)。 因此,KLEE击败开发人员测试的因素大约为两个:总线路覆盖率90.5%,而开发人员套件仅44.8%。 开发人员仅在一个基准cp上做得更好。

5.4问题发现:MINIX所有BUSYBOX工具

为了证明KLEE在发现错误中的适用性,我们使用KLEE在一系列短期内检查了全部279个BUSYBOX工具和84个MINIX工具[4]。 这360个应用程序涵盖了广泛的功能,例如网络工具,文本编辑器,登录实用程序,归档工具等。尽管KLEE在这些运行期间生成的测试不足以实现高覆盖率(由于建模不完整),但我们 确实很快发现了许多错误:已经报告了BUSYBOX中的21个错误和MINIX中的21个错误(许多其他报告正在等待检查)。 图10给出了BUSYBOX错误的命令行。 除已在未发布的树中修复的日期外,所有错误都是内存错误,并已得到迅速修复。 我们还没有收到MINIX开发人员的回音。

SC_20210218_145403.png

图10:KLEE生成的命令行和输入(为便于阅读而进行了修改),导致BUSYBOX中的程序崩溃。 当多个应用程序由于共享(未处理)相同的代码段而崩溃时,我们将其按阴影进行分组。

5.5 检查工具等效性

到目前为止,我们一直专注于寻找不需要了解程序预期行为的通用错误。 现在,我们展示如何进行更深入的检查,包括在有限的探索路径上验证全部功能的正确性。

KLEE不做任何近似:它的约束条件可以精确到一个位。 如果KLEE到达断言,并且其约束求解器指出在给定当前路径约束的情况下该断言的错误分支无法执行,则证明当前路径上不存在任何可能违反断言,KLEE中的模错误或不确定性的值 在代码中。重要的是,KLEE会针对程序员表达为C代码的任何条件(从简单的非空指针检查到验证程序输出的正确性)进行此类证明。

可以利用此属性执行更深入的检查,如下所示。假设我们有两个过程f和f′,它们采用一个参数,并且意图实现相同的接口。我们可以通过简单地向它们提供相同的符号参数并断言它们返回相同的值来验证每个路径的功能等效性:assert(f(x)== f’(x))。每次KLEE遵循到达此断言的路径时,它都会检查该路径上是否存在任何违反它的值。如果发现不存在,则证明它在该路径上具有等效功能。言外之意,如果一个函数在路径上是正确的,那么等效性证明了另一个函数也是正确的。相反,如果函数沿路径和assert激发计算不同的值,则KLEE将产生一个测试用例来证明这种差异。这些都是强大的结果,完全超出了传统测试的范围。查看KLEE的一种方法是,它自动将通过C程序的路径转换为定理证明者可以推理的形式。结果,证明路径等价仅需要几行C代码(上面的断言),而不是在定理证明中进行大量的手工操作。

请注意,等效结果仅适用于KLEE探索的有限路径集。 像传统测试一样,它无法对丢失的路径做出声明。 但是,如果KLEE能够耗尽所有路径,则表明功能完全等效。 尽管通常很难处理,但是可以用这种方法测试许多隔离的算法,至少可以达到某些输入大小。

我们使用图11中的人为示例帮助使这些点具体化,该示例交叉检验了琐碎的模实现(mod)与以2的幂(mod opt)对模进行了优化的模实现。 它首先使输入x和y成为符号,然后使用assert(第14行)检查差异。 两个代码路径到达此断言,具体取决于对2的幂的测试(第2行)是否成功。 (沿途,当y = 0时,KLEE会生成一个零除测试用例。)真实路径使用求解器来检查约束(y&-y)== y隐含了(x&(y-1)) == x%y适用于所有值。 此查询成功。 错误的路径检查了虚假重言式,即约束(y&-y)≠ y暗示x%y == x%y也成立。 然后,KLEE检查运行终止,这意味着KLEE仅使用几行代码就证明了对所有非零值的等效性。

1 : unsigned mod_opt(unsigned x, unsigned y) {
2 : 	if((y & −y) == y) // power of two?
3 : 		return x & (y−1);
4 : 	else
5 : 		return x % y;
6 : }
7 : unsigned mod(unsigned x, unsigned y) {
8 : 	return x % y;
9 : }
10: int main() {
11: 	unsigned x,y;
12: 	make_symbolic(&x, sizeof(x));
13: 	make_symbolic(&y, sizeof(y));
14: 	assert(mod(x,y) == mod_opt(x,y));
15: 	return 0;
16: }

图11:说明等效性检查的简单程序。 当y 不等于 0时,KLEE证明总等价。

这种方法在广泛的环境中很有用。 大多数标准化接口(例如库,网络服务器或编译器)都具有多种实现方式(标准化的部分动机和结果)。 此外,在其他常见情况下,存在多个实现:

  1. f是简单的参考实现,而f是现实世界中的优化版本。
  2. f’是f的修补版本,旨在仅消除错误(因此应该严格减少崩溃次数)或重构代码而无需更改功能。
  3. f具有一个逆数,这意味着我们可以更改等效检查以验证f -1(f(x))≡x,例如:assert(uncompress(compress(compress(x))== x))。

实验结果。 我们证明了该技术可以通过对67个COREUTILS工具与据称等效的BUSYBOX实现进行交叉检查,从而找到更深的正确性错误并扩展到实际程序。 例如,给定相同的输入,wc的BUSYBOX和COREUTILS版本应输出相同数量的行,字和字节。 实际上,BUSYBOX和COREUTILS工具都旨在符合IEEE标准1003.1 [3],该标准规定了它们的行为。

我们建立了一个简单的基础架构,以使交叉检查自动进行。 给定两个工具,它将重命名所有全局符号,然后将它们链接在一起。 然后,它在相同的符号环境(相同的符号参数,文件等)下运行,并将打印的数据与stdout进行比较。 当检测到不匹配时,它会生成一个测试用例,可以直接运行以确认差异。

表3显示了KLEE发现的不匹配的子集。 前三行显示了硬性正确性错误(已由开发人员迅速修复),而其他三行则大多显示出缺少的功能。 作为一个严重正确性错误的示例,第一行提供的输入内容表明,在BUSYBOX的comm上运行时,其行为就像两个不同的文件是相同的一样。

SC_20210218_152809.png

表3:在等效工具的BUSYBOX和COREUTILS版本之间发现的KLEE不匹配的很小子集。 前三个是严重的正确性错误。 其他大多数都揭示了缺少的功能

5.6 HiStar 系统内核

我们还通过使用KLEE来检查HiStar [39]内核,从而将KLEE应用于检查非用户态程序代码。 我们使用了基于用户模式HISTAR内核的简单测试驱动程序。 驱动程序创建核心内核数据结构,并通过访问用户内存的单个页面来初始化单个进程。 然后,它调用图12中的测试函数,该函数使用户存储器具有符号性,并使用完全符号性的参数执行预定义数量的系统调用。 由于系统调用号是在第一个参数中编码的,因此此简单的驱动程序有效地测试了内核中的所有(序列)系统调用。

1 : static void test(void *upage, unsigned num calls) {
2 : 	make_symbolic(upage, PGSIZE);
3 : 	for (int i=0; i<num calls; i++) {
4 : 		uint64_t args[8];
5 : 		for (int j=0; j<8; j++)
6 : 			make_symbolic(&args[j], sizeof(args[j]));
7 : 		kern_syscall(args[0], args[1], args[2], args[3],
8 : 					 args[4], args[5], args[6], args[7]);
9 : 	}
10: 	sys_self_halt();
11: }

图12:用于HISTAR的测试驱动程序:它使用户存储器的单个页面成为符号,并执行带有完全符号参数的用户指定数量的系统调用。

尽管设置是限制性的,但实际上我们发现它可以快速生成测试用例(系统调用向量和内存内容的序列),这些用例覆盖了很大一部分内核代码并揭示了有趣的行为。 表4显示了在有磁盘和无磁盘的情况下运行时从核心内核获得的覆盖率。 当使用磁盘进行配置时,大多数未发现的代码仅在存在大量内核对象时才被触发。 目前在我们的测试环境中不会发生这种情况; 我们正在研究在测试过程中充分行使此代码的方法。 为了快速比较,我们通过同一驱动程序运行了100万次随机测试(类似于第5.2.4节)。 如表4所示,对于有(+ 17.0%)和没有(+ 28.4%)磁盘的运行,KLEE的测试所覆盖的范围要比随机测试大得多。

Test Random KLEE ELOC
With Disk 50.1% 67.1% 4617
No Disk 48.0% 76.4% 2662

表4:HISTAR内核的运行范围,最多可运行三个系统调用,并配置为带磁盘和不带磁盘。 为了进行比较,我们对一百万次试验使用随机输入进行了相同的运行。

KLEE基于约束的推理使它能够在HISTAR的32位版本中发现一个棘手的关键安全漏洞。 图13显示了包含该错误的函数的代码。 如果加法溢出,则应该将功能safe addptr的* of设置为true。 但是,由于输入为64位长,因此使用的测试不足(应为(r <a) || (r < b)

安全addptr函数在将数据复制到用户空间或从用户空间复制数据之前先验证用户的内存地址。 内核例程获取用户地址和大小,并计算是否允许用户访问该范围内的内存。 此例程使用溢出来防止计算可能溢出时进行访问。 因此,计算溢出中的此错误使恶意进程可以访问其控制范围之外的内存区域。

6. 相关工作

许多最新的工具都基于符号执行[11、14-16、20-22、24、26、27、36]。 我们对比了KLEE如何处理环境和路径爆炸问题。

1 : uintptr t safe addptr(int *of, uint64 t a, uint64 t b) {
2 : 	uintptr t r = a + b;
3 : 	if (r < a)
4 :			*of = 1;
5 : 	return r;
6 : }

图13:包含重要安全漏洞的HISTAR功能。 如果加法溢出,则该函数应该将* of设置为true,但是对于32的版本,对于很大的b值,可能会将* of设置为true。

据我们所知,传统的符号执行系统[17、18、32]在严格意义上是静态的,根本不与运行环境交互。 他们要么无法处理利用环境的程序,要么需要完整的工作模型。 测试生成的最新工作[16,26,36]确实允许外部交互,但是迫使他们使用完全具体的过程调用参数,这限制了他们可以探索的行为:具体的外部调用将完全按照其所做的工作,而不是执行 它可能做的所有事情。 在KLEE中,我们努力在这两种选择之间实现功能平衡; 我们既允许与外部环境的交互,又提供一个模型来模拟与符号环境的交互。

相反,路径爆炸问题引起了更多关注[11、22、24、27、34]。 与第3节中提出的搜索启发式类似,过去提出的搜索策略包括Best First Search [16],Generational Search [27]和Hybrid Concolic Testing [34]。 正交于搜索启发式,研究人员通过组成路径测试路径[8,24]并跟踪程序读取和写入的值来解决路径爆炸问题[11]。

像KLEE一样,其他符号执行系统也会在将查询发送到底层约束求解器之前实现其自身的优化,例如[36]中介绍的简单语法转换和[27]中讨论的约束包含优化。

与符号执行系统相似,模型检查器已被用来在软件的设计和实现中查找错误[10、12、19、25、29、30]。 这些方法通常需要大量的人工来构建测试工具。 但是,这些方法在某种程度上是KLEE的补充:KLEE生成的测试可用于驱动模型检查的代码,类似于Java PathFinder所采用的方法[31,37]。

以前,我们表明符号执行可以通过交叉检查同一库函数的各种实现来找到正确性错误[15]; 本文表明该技术可扩展到实际程序。 在我们最初的工作之后,其他人应用了类似的想法来发现应用程序中的正确性错误,例如网络协议实现[13]和PHP脚本[9]。

7. 结语

我们的长期目标是采用一个任意程序,并按惯例获得90%以上的代码覆盖率,并在测试用例中将所有有用输入压碎。 尽管要实现此目标还有很长的路要走,但我们的结果表明,该方法在各种实际代码中都可以很好地工作。 我们的系统KLEE自动生成测试,平均开箱即用地覆盖了大约160种复杂的系统密集型应用程序中的90%以上的行(合计超过80%)。 这一覆盖范围大大超过了其相应的手写测试套件,其中包括一套历时15年的测试套件。

总共,我们使用KLEE检查了452个应用程序(带有超过430K行代码),在其中发现了56个严重的错误,其中包括10个COREUTILS,这可以说是测试最严格的开源应用程序集合。 据我们所知,这比以前的符号测试生成工作所检查的代码和独特的程序要多一个数量级。 此外,由于KLEE的约束条件没有近似值,因此其推理可以证明路径的属性(或查找没有误报的反例)。 我们使用此功能既可以证明在许多真实的,据称完全相同的应用程序中的路径等效,也可以在其中找到功能正确性错误。

我们描述的技术应与其他工具很好地配合使用,并在处理各种应用程序时提供类似的帮助。

致谢

我们感谢GNU COREUTILS开发人员,特别是COREUTILS维护人员Jim Meyering迅速确认了我们所报告的错误并回答了许多问题。 我们同样感谢BUSYBOX的开发人员,尤其是BUSYBOX维护人员Denys Vlasenko。 我们还要感谢HISTAR的设计师Nickolai Zeldovich在检查HISTAR方面的巨大帮助,包括为我们编写了用户级驱动程序。 我们感谢OSPD审稿人Shepard Terence Kelly,以及Philip Guo对案文的宝贵评论。 这项研究得到了DHS资助FA8750-05-2-0142,NSF TRUST资助CCF-0424422和NSF CAREER奖励CNS-0238570-001的支持。 丛林研究生奖学金部分支持Cristian Cadar。