ACM通信
实践
SAGE:用于安全测试的白盒模糊
在jpg解析器(通常是操作系统的一部分)读取图像数据、对其进行解码、使用解码后的数据创建新的数据结构并将这些数据传递给计算机中的图形卡之后，该图像将显示在屏幕上。
来源:美国国家航空航天局
大多数通信读者可能会认为“程序验证研究”主要是理论性的，对整个世界几乎没有影响。再想想。如果你是在一台运行Windows操作系统的电脑上读到这篇文章的(超过93%的电脑用户，也就是超过10亿人)，那么你已经在不知不觉中受到了这一行工作的影响，这正是我们想要的方式。
每个月的第二个星期二，也被称为“补丁星期二”，微软会发布一系列安全公告和相关的安全补丁，这些补丁将部署在全球数亿台机器上。每份安全公告都要花费微软及其用户数百万美元。如果一个月的安全更新只花费你0.001美元(十分之一美分)的电费或生产力损失，那么这个数字乘以10亿人就是100万美元。当然，如果恶意软件在你的机器上传播，可能会泄露你的一些私人数据，那么你付出的代价可能远远超过0.001美元。这就是为什么我们强烈建议你应用那些讨厌的安全更新。
许多安全漏洞都是在解析在互联网上传输的文件和数据包的代码中编程错误的结果。例如，微软Windows包括用于数百种文件格式的解析器。
如果你是在电脑上阅读这篇文章，那么如图所示图1在JPG解析器(通常是操作系统的一部分)读取图像数据、对其进行解码、使用解码后的数据创建新的数据结构并将这些数据传递给计算机中的图形卡之后显示在屏幕上。如果实现该jpg解析器的代码包含一个错误，例如缓冲区溢出，可以由损坏的jpg图像触发，那么在您的计算机上执行该jpg解析器可能会被劫持来执行一些其他代码，这些代码可能是恶意的，并且隐藏在jpg数据本身中。
这只是可能存在的安全漏洞和攻击场景的一个示例。本文其余部分讨论的安全错误主要是缓冲区溢出。
寻找价值百万的虫子
如今，黑客发现软件产品中的安全漏洞主要有两种方法。首先是二进制代码检查(使用优秀的反汇编程序，二进制代码就像源代码一样)。
第二点是黑箱起毛这是一种黑盒随机测试，它随机地改变格式良好的程序输入，然后用这些修改后的输入测试程序，3.希望触发一个错误，如缓冲区溢出。在某些情况下，语法用于生成格式良好的输入。这还允许编码特定于应用程序的知识和测试生成启发式。
黑盒模糊法是一种简单而有效的软件安全漏洞查找技术。通过这种方式已经发现了数千个安全漏洞。在微软，fuzzing对于每个产品的每个不受信任的接口都是强制性的，就像安全开发生命周期中规定的那样，7它记录了关于如何开发安全软件的建议。
虽然黑盒模糊可以非常有效，但它的局限性是众所周知的。例如，条件语句的then分支
只有1 / 232如果输入变量x具有随机选择的32位值。这直观地解释了为什么黑盒模糊通常提供较低的代码覆盖率，并可能遗漏安全漏洞。
介绍Whitebox Fuzzing
几年前，我们开始开发黑盒模糊的替代方案，叫做白盒起毛．5它建立在系统动态测试生成的最新进展之上4并将其范围从单元测试扩展到整个程序安全测试。
从一个格式良好的输入开始，白盒模糊包括象征性地执行测试下的程序动态，收集来自执行过程中遇到的条件分支的输入约束。然后系统地对收集到的约束条件进行否定并使用约束解算器，其解决方案被映射到执行不同程序执行路径的新输入。这个过程重复使用novel搜索技术尝试遍历程序的所有(实际上是许多)可行执行路径，同时使用方法检查许多属性运行时检查(例如Purify, Valgrind，或者AppVerifier)。
例如，符号执行前面的程序片段，输入变量的初始值为0x以其他的条件语句的分支，并生成路径约束x + 3 13．一旦这个约束被否定并解决，它就屈服了X = 10，提供一个新的输入，使程序遵循然后条件语句的分支。这允许我们练习和测试额外的代码以寻找安全漏洞，甚至不需要特定的输入格式知识。此外，这种方法可以自动发现和测试“极端情况”，即程序员可能无法正确分配内存或操作缓冲区，从而导致安全漏洞。
理论上，系统的动态测试生成可以实现程序路径的全覆盖，即:程序验证．然而，在实践中，搜索通常是不完整的，因为在测试的程序中执行路径的数量是巨大的，而且由于复杂的程序语句(指针操作和浮点操作等)，对外部操作系统和库函数的调用，以及大量的约束都不能在合理的时间内完美解决，符号执行、约束生成和约束求解可能是不精确的。因此，我们不得不探索实际的权衡。
圣人
白盒模糊首先在工具SAGE中实现，SAGE是可伸缩自动引导执行的缩写。5因为SAGE的目标是大型应用程序，其中一次执行可能包含数亿条指令，所以符号执行是它最慢的组件。因此，SAGE实现了一种新的定向搜索算法代搜索这样可以最大化每次符号执行生成的新输入测试的数量。给定一个路径约束，所有该路径中的约束被系统地一个一个地否定，与通往它的路径约束的前缀结合在一起，并试图由约束求解器求解。这样，一次符号执行就可以生成数千个新测试。(相比之下，标准的深度优先或宽度优先搜索将只否定每个路径约束中的最后一个或第一个约束，并且每次符号执行最多生成一个新测试。)
SAGE对微软产生了显著的影响。它结合并扩展了多年来开发的程序分析、测试、验证、模型检查和自动定理证明技术。
所示的程序图2接受四个字节作为输入，并在变量的值时包含错误问大于等于4。从一些初始输入开始好， SAGE在动态执行符号执行时运行此程序。因为在第一次运行期间所采取的程序路径是由所有的其他的在程序的分支中，这个初始运行的路径约束是约束的结合我0b,我1一个,我2d而且我3.！．每个约束都被一个一个地消去，与通往它的路径约束的前缀连用，然后用约束求解器求解。在这种情况下，所有四个约束都是可解决的，导致四个新的测试输入。图2还显示了函数的所有可行程序路径的集合前．最左边的路径表示程序的初始运行，第0代的路径标记为0。通过系统地对第0代路径约束中的每个约束求反并求解，得到4个第1代输入。通过重复这个过程，最终枚举出这个示例的所有路径。实际上，搜索通常是不完整的。
SAGE是第一个在x86二进制级别上执行动态符号执行的工具。它是在跟踪重放基础设施TruScan之上实现的，8它消耗由iDNA框架生成的跟踪文件1并虚拟地重新执行记录的运行。TruScan提供了几个特性，这些特性极大地简化了符号执行，包括指令解码、提供程序符号信息接口、监视各种输入/输出系统调用、跟踪堆和堆栈帧分配以及跟踪程序结构中的数据流。多亏了脱机跟踪，SAGE中的约束生成是完全确定的，因为它与捕获记录运行期间遇到的所有不确定事件的结果的执行跟踪一起工作。工作在x86二进制级别允许SAGE用于任何程序，无论其源语言或构建过程如何。它还确保了“你所模糊的就是你所运送的，因为编译器可能会执行可能影响安全性的源代码更改。
SAGE使用了几个优化，这些优化对于处理庞大的执行跟踪至关重要。例如，一个具有45,000个输入字节的Excel符号执行将执行近10亿个x86指令。为了扩展到这样的执行跟踪，SAGE使用了几种技术来提高约束生成的速度和内存使用:符号式缓存确保结构上等价的符号项映射到相同的物理对象;无关约束消除通过删除不与否定约束共享符号变量的约束，减少约束求解器查询的大小;本地约束缓存跳过已经添加到路径约束的约束;翻转次数限制建立由特定程序分支生成的约束可以翻转的最大次数;使用一种廉价的语法检查，约束包容消除了在同一程序分支注入的其他约束在逻辑上隐含的约束(很可能是由依赖输入的循环的连续迭代产生的)。
圣人架构
中描述了SAGE的高级体系结构图3．给定一个(或多个)初始输入Input0， SAGE首先用AppVerifier运行测试中的程序，看看这个初始输入是否触发了一个错误。如果没有，SAGE将收集在此运行期间执行的唯一程序指令列表。接下来，SAGE象征性地使用该输入执行程序，并生成一个路径约束，用输入约束的组合来表征当前程序的执行。
然后，实现分代搜索，该路径约束中的所有约束都被一个一个地否定，与通往它的路径约束的前缀一起放置，并尝试由约束求解器求解(我们目前使用Z3 SMT求解器)2)．所有可满足的约束都映射到N新的输入，根据增量指令覆盖率进行测试和排名。例如，如果使用new执行程序Input1然后发现100条新指令Input1得到100分，以此类推。接下来，选择得分最高的新输入来执行(昂贵的)符号执行任务，然后重复这个循环，可能永远重复下去。请注意，所有SAGE任务都可以在多核机器上并行执行，甚至可以在一组机器上并行执行。
构建SAGE这样的系统还面临许多其他挑战:如何从符号执行中的不精确中恢复，如何有效地检查许多属性，如何利用复杂输入格式的语法(如果可用)，如何处理路径爆炸，如何精确地推断指针，如何处理浮点指令和依赖输入的循环。由于篇幅限制，我们不能在这里讨论这些挑战，但作者的网页提供了访问其他解决这些问题的论文。
一个例子
2007年4月3日，微软发布了一个带外关键安全补丁(MS07-017)，用于解析动画格式游标的代码。这个漏洞最初是在2006年12月由Determina Security Research的Alex Sotirov报告给微软的，然后在漏洞代码出现后公开。9这是微软自2006年1月以来发布的第三个带外补丁，表明了该漏洞的严重性。微软SDL策略博客指出，对该代码进行大量的黑盒模糊处理未能发现该错误，现有的静态分析工具也无法在没有大量误报的情况下发现该错误。6
相比之下，SAGE在从一个格式良好的ANI文件开始的几个小时内合成了一个显示错误的新输入文件，尽管对ANI格式一无所知。从一个格式良好的ANI文件库中任意选取一个种子文件，并在一个小型测试程序上运行SAGE，该程序调用user32.dll解析ANI文件。初始运行在10072个符号输入字节上执行了1,279,939条x86指令后，生成了一个包含341个分支约束的路径约束。SAGE在7小时36分钟和7706个测试用例后创建了一个崩溃的ANI文件，使用2GHz AMD Opteron 270双核处理器的一个核心，运行32位Windows Vista和4GB RAM。
SAGE的影响
自2007年以来，SAGE在许多大型微软应用程序中发现了许多与安全相关的漏洞，包括图像处理器、媒体播放器、文件解码器和文档解析器。值得注意的是，在微软Windows 7的开发过程中，SAGE发现了大约三分之一由文件模糊发现的错误。因为SAGE通常是最后运行的，这些bug会被其他任何事情遗漏，包括静态程序分析和黑盒模糊。
找到所有这些漏洞为微软节省了数百万美元，也为全世界节省了时间和精力，避免了为超过10亿台电脑打昂贵的安全补丁。运行的软件你的PC受到SAGE的影响。
自2008年以来，SAGE已经在大约100多台机器/核心上全天候运行，自动模糊了微软安全测试实验室中的数百个应用程序。这是300多机器年和任何可满足模理论(SMT)求解器的最大计算使用量，到目前为止已经处理了超过10亿个约束。
SAGE在发现bug方面是如此有效，以至于我们第一次面对动态测试生成的“bug分类”问题。我们相信这种有效性来自于能够模糊大型应用程序(而不仅仅是以前动态测试生成的小单元)，这反过来允许我们发现由多个组件的问题引起的错误。SAGE也很容易部署，这要归功于x86二进制分析，而且它是全自动的。现在，微软的各个小组每天都在使用SAGE。
结论
SAGE对微软产生了显著的影响。它结合并扩展了多年来开发的程序分析、测试、验证、模型检查和自动定理证明技术。
在实践中，黑盒模糊和白盒模糊哪个最好?两者都提供了不同的成本/精度权衡。Blackbox简单、轻量级、简单、快速，但代码覆盖率有限。白盒更智能，但更复杂。
哪种方法更有效地找到bug ?视情况而定。如果应用程序从未进行过模糊化，那么任何形式的模糊化都有可能发现bug，简单的黑盒模糊化是一个很好的开始。然而，一旦低挂的虫子消失了，寻找下一个虫子就必须变得更聪明。然后是时候使用白盒模糊和/或用户提供的指导，例如，使用输入语法。
底线是什么?实际上，两者都要使用。我们在微软就是这样做的。
致谢
微软不同部门的许多人都为SAGE的成功做出了贡献;超出了空间所允许的范围。欲查看详细名单，请访问queue.acm.org/detail.cfm ? id = 2094081．
相关文章
在queue.acm.org
黑匣子调试
詹姆斯·a·惠特克，赫伯特·h·汤普森
http://queue.acm.org/detail.cfm?id=966807
安全问题解决了?
约翰Viega
http://queue.acm.org/detail.cfm?id=1071728
开放与封闭:哪个资源更安全?
理查德•福特
http://queue.acm.org/detail.cfm?id=1217267
参考文献
1.Bhansali, S.， Chen, W.， De Jong, S.， Edwards, A.和Drinic, M.用于指令级跟踪和程序分析的框架。在第二届虚拟执行环境国际会议论文集(2006)。
2.de Moura, L.和Bjorner, N. Z3:一个有效的SMT求解器。在系统构造与分析的工具与算法论文集；计算机科学课堂讲稿。斯普林格出版社，2008,337340。
3.Forrester, J.E.和Miller, B.P.对Windows NT应用程序使用随机测试的稳健性的实证研究。在4号会议记录thUsenix Windows系统研讨会(华盛顿州西雅图，2000年8月)。
4.高德froid, P.， Klarlund, N.和Sen, K. DART:定向自动随机测试。在程序设计语言设计与实现学报(2005), 213223。
5.Godefroid, P.， Levin, m.y.和Molnar, D.自动白盒模糊测试。在网络与分布式系统安全论文集，(2008)， 151166。
6.Howard, M.动画光标安全漏洞的教训;http://blogs.msdn.com/sdl/archive/2007/04/26/lessons-learned-fromthe-animated-cursor-security-bug.aspx．
7.霍华德，M.和利普纳，S.。安全开发生命周期．微软出版社，2006年。
8.Narayanasamy, S, Wang, Z, Tigani, J, Edwards, A.和Calder, B.使用重放分析自动分类良性和有害数据竞赛。在编程语言的设计与实现(2007)。
9.Sotirov, A. Windows动画游标堆栈溢出漏洞，2007;http://www.determina.com/security.research/vulnerabilities/ani-header.html．
©2012 acm 0001-0782/12/0300 $10.00
本论文部分或全部的电子版或硬拷贝供个人或课堂使用的许可是免费的，前提是副本不是为了盈利或商业利益而制作或分发的，并且副本的第一页上必须有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有署名的摘要。以其他方式复制，重新发布，在服务器上发布，或重新分发到列表，需要事先特定的许可和/或费用。请求发布权限permissions@acm.org或传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2012 ACM, Inc.
没有找到条目