就像死亡和税收一样,代码错误是生活中不幸的事实。几乎每个程序在发布时都带有已知错误,而且可能所有程序最终都会出现仅在部署后才被发现的错误。造成这种可悲状况的原因有很多。
一个问题是许多应用程序是用内存不安全的语言编写的。C 的变体,包括 C++ 和 Objective-C,尤其容易受到内存错误的影响,例如缓冲区溢出和悬空指针(释放后使用错误)。其中两个在 SANS 前 25 名列表中:不检查输入大小的缓冲区复制 (http://cwe.mitre.org/top25/index.html#CWE-120) 和缓冲区大小计算错误 (http://cwe.mitre.org/top25/index.html#CWE-131);另请参见基于堆的缓冲区溢出 (http://cwe.mitre.org/data/definitions/122.html) 和释放后使用 (http://cwe.mitre.org/data/definitions/416.html)。
这些错误可能导致崩溃、错误执行和安全漏洞,并且众所周知地难以修复。
使用 Java 等内存安全语言而不是 C/C++ 编写新应用程序将有助于缓解这些问题。例如,由于 Java 使用垃圾回收,Java 程序不易受到释放后使用错误的影响;同样,由于 Java 始终执行边界检查,因此 Java 应用程序不会遭受由缓冲区溢出引起的内存损坏。
话虽如此,安全语言并非万能药。Java 程序仍然会遭受缓冲区溢出和空指针解引用,尽管它们会在发生时立即抛出异常,这与基于 C 的对应程序不同。针对这些异常的常见方法是中止执行并打印堆栈跟踪(甚至打印到网页!)。Java 也与其他任何语言一样容易受到并发错误的影响,例如竞争条件和死锁。
不使用安全语言既有实际原因,也有技术原因。首先,通常不可行重写现有代码,因为成本和时间投入,更不用说引入新错误的风险了。其次,依赖垃圾回收的语言不适合需要高性能或大量使用可用物理内存的程序,因为垃圾回收始终需要额外的内存。6 这些包括操作系统级服务、数据库管理器、搜索引擎和基于物理学的游戏。
虽然工具可以提供帮助,但它们无法捕获所有错误。静态分析器近年来取得了巨大进步,但仍有许多错误无法触及。为了避免用误报报告淹没开发人员,大多数现代静态分析器报告的错误远少于它们可能报告的错误。换句话说,它们牺牲了假阴性(未能报告真实错误)以换取更低的误报率。这使得这些工具更易于使用,但也意味着它们将无法报告真实错误。Dawson Engler 及其同事为 Coverity 的“不健全”静态分析器做出了完全相同的选择。4
在过去十年中,测试工具的最新技术也取得了显著进展。随机模糊测试可以与静态分析相结合,以探索导致失败的路径。这些工具现在已成为主流:例如,Microsoft 的驱动程序验证程序可以测试设备驱动程序代码是否存在各种问题,现在还包括随机并发压力测试。
然而,正如 Dijkstra 的名言,“程序测试可以用来证明错误的存在,但永远不能证明它们的缺失!” 在某个时候,测试将无法发现新错误,而不幸的是,这些错误只会在软件发布后才被发现。
找到错误只是第一步。一旦发现错误——无论是通过检查、测试还是分析——修复错误仍然是一个挑战。任何错误修复都必须极其谨慎地进行,因为任何新代码都存在引入更多错误的风险。开发人员必须构建并仔细测试补丁,以确保它修复了错误而没有引入任何新错误。这可能既昂贵又耗时。例如,根据赛门铁克的数据,从发现远程可利用的内存错误到发布企业应用程序补丁的平均时间为 28 天。12
在某个时候,修复某些错误 просто перестает иметь экономический смысл。跟踪它们的来源通常既困难又耗时,即使程序的完整内存状态和所有输入都可用。显然,必须修复严重错误。对于其他错误,修复它们的好处可能被创建新错误的风险以及程序员时间和延迟部署的成本所抵消。
一旦有缺陷的软件被部署,追踪和修复错误的问题就会呈指数级增长。用户很少提供详细的错误报告,允许开发人员重现问题。
对于部署在台式机或移动设备上的软件,获取足够的信息来查找错误可能很困难。发送整个核心文件通常是不切实际的,尤其是在移动连接上。通常,人们可以期望的最好结果是一些日志消息和一个包含堆栈跟踪和线程上下文信息的迷你转储。
即使是这些有限的信息也可以提供有价值的线索。如果某个特定函数出现在崩溃期间观察到的许多堆栈跟踪中,则该函数很可能是罪魁祸首。Microsoft Windows 包括一个应用程序调试器(以前称为 Watson,现在称为 Windows 错误报告),用于执行此类分类,不仅适用于 Microsoft,也适用于通过 Microsoft 的 Winqual 计划的第三方应用程序。Google 还提供了一个名为 Breakpad 的跨平台工具,可用于为任何应用程序提供类似的服务。
然而,对于许多错误来说,这些工具提供的信息价值有限。例如,内存损坏错误通常在实际错误发生数百万条指令后才会触发故障,这使得堆栈跟踪毫无用处。对于空指针异常通常也是如此,错误通常发生在存储空指针之后很久。
在服务器上,情况稍微好一些。服务器应用程序通常生成日志消息,其中可能包含有关程序为何失败的线索。不幸的是,日志文件可能非常大,难以管理。仔细研究日志并尝试将它们与源代码关联起来可能非常耗时。更糟糕的是,这项工作可能不会产生任何有用的结果,因为日志是不完整的——也就是说,它们可能根本没有提供足够的信息来缩小特定错误的来源范围,因为日志消息不够或类型不正确。
伊利诺伊大学和加州大学圣地亚哥分校最近的工作可能会导致开发工具来解决其中一些问题:SherLog13 自动化了从日志消息到错误源代码路径追踪错误的过程;LogEnhancer14 自动扩展日志消息,以帮助进行崩溃后调试。(有关日志记录的更多信息,请参见 2011 年的 文章,《日志分析的进展和挑战》11。)
尽管取得了这些进展,但查找错误实际上变得比以往任何时候都更加困难。当程序是顺序执行时,查找错误已经很具挑战性,但现在,随着多线程程序、异步和多核的出现,情况变得更加糟糕。由于事件和线程交错的不同时序,这些非确定性程序的每次执行都与上次完全不同。这种情况使得重现错误成为不可能,即使有所有输入事件的完整日志——无论如何,在实践中记录这些日志太昂贵了。
让我们暂时换个角度谈谈汽车(我们稍后会回到软件话题)。作为当前情况的类比,想想汽车刚出现的时候。多年来,安全最多只是事后才考虑的事情。在设计新车时,主要考虑因素是美观和高性能(想想尾翼和 V-8 发动机)。
最终,交通事故导致立法者和汽车制造商开始考虑安全因素。20 世纪 60 年代后期,安全带成为美国汽车的强制性标准配置,20 世纪 70 年代是保险杠,20 世纪 80 年代是气囊。现代汽车结合了各种安全功能,包括夹层挡风玻璃、碰撞缓冲区和防抱死制动系统。现在几乎无法想象任何公司会在没有这些基本安全功能的情况下交付汽车。
软件行业正处于类似于 20 世纪 50 年代汽车行业的地位,交付具有大量马力和尾翼但没有任何安全措施的软件。今天的软件甚至配备了转向柱上的装饰性尖刺,以确保用户在应用程序崩溃时会受到痛苦。
手动内存管理与未检查的内存访问的有效结合使 C 和 C++ 应用程序容易受到各种内存错误的影响。这些错误可能导致程序崩溃或产生不正确的结果。攻击者也经常能够利用这些内存错误来获得对系统的未授权访问。由于应用程序访问的大部分对象都在堆上,因此与堆相关的错误尤其严重。
许多内存错误发生在程序错误地释放对象时。当堆对象在仍然存活时被释放时,就会出现悬空指针,从而导致释放后使用错误。当程序错误地释放堆栈对象或堆对象中间的地址时,就会发生无效释放,即释放从未由分配器返回的对象。当堆对象被多次释放而没有中间分配时,就会发生双重释放。乍一看,这种错误似乎无伤大雅,但在许多情况下,会导致堆损坏或程序终止。
其他内存错误与已分配对象的使用有关。当分配的对象大小不够大时,当要读取或写入的内存地址位于对象外部时,可能会发生越界错误。越界写入也称为缓冲区溢出。当程序读取从未初始化的内存时,会发生未初始化读取;在许多情况下,未初始化的内存包含来自先前分配对象的数据。
鉴于行业知道它正在交付带有错误的软件,并且环境很危险,那么为产品配备安全带和气囊可能是有意义的。理想的情况是对于已部署应用程序中出现的任何问题,既具有弹性,又具有及时的纠正措施。
让我们关注 C/C++/Objective-C 应用程序——在服务器、台式机和移动平台上运行的应用程序的大部分——以及内存错误,这是用这些语言编写的应用程序的首要难题。配备安全功能的内存分配器可以在保护软件免受崩溃方面发挥关键作用。
第一类错误——由于误用free或delete——可以通过使用垃圾回收直接补救。垃圾回收的工作原理是仅回收它分配的对象,从而消除无效释放。它仅在通过从“根”(全局变量和堆栈)遍历指针无法再访问对象时才回收对象。这消除了悬空指针错误,因为根据定义,不可能有指向已回收对象的指针。由于它自然地只回收这些对象一次,因此垃圾回收器也消除了双重释放。
虽然 C 和 C++ 在设计时没有考虑垃圾回收,但可以插入一个保守的垃圾回收器,并完全防止与释放相关的错误。这里的保守一词意味着,由于垃圾回收器不一定知道哪些值是指针(因为我们身处 C 语言领域),因此它保守地假设,如果一个值看起来像指针(它在正确的范围内并且正确对齐)并且行为像指针(它仅指向有效对象),那么它可能是一个指针。
Boehm-Demers-Weiser 保守垃圾回收器是此目的的绝佳选择:它速度相当快且空间效率高,并且可以通过将其配置为将对 free 的调用视为 NOP(空操作)来替换内存分配器。
当然,垃圾回收可能不适合所有 C/C++ 应用程序。它可能会减慢某些应用程序的速度,并导致不可预测的暂停或抖动。它也可能不适用于资源受限的环境(例如移动设备),因为垃圾回收通常比显式内存管理需要更多的内存才能提供相同的吞吐量。6 例如,Objective-C 中的保守垃圾回收在台式机上可用,但在 iOS(iPhone 或 iPad)上不可用。
虽然垃圾回收器消除了与释放相关的错误,但它们无法帮助预防第二类内存错误:与误用已分配对象(例如缓冲区溢出)有关的错误。
可以查找缓冲区溢出的运行时系统通常会带来惊人的高开销,这使得它们不太适合已部署的代码。诸如 Valgrind 的 MemCheck 之类的工具非常全面且有用,但它们在设计上是重量级的,并且执行速度会降低几个数量级。8
基于编译器的方法可以通过避免不必要的检查来大幅降低开销,尽管它们需要重新编译应用程序的所有代码,包括库。Google 最近发布了 AddressSanitizer (http://code.google.com/p/address-sanitizer/wiki/AddressSanitizer),这是一种编译器和运行时技术的组合,可以查找许多错误,包括溢出和释放后使用错误。虽然 AddressSanitizer 比 Valgrind 快得多,但其开销仍然相对较高(约 75%),使其主要用于测试。
所有这些方法都基于这样的想法,即遇到错误时最好的做法是立即中止。这是经典方法,即只是弹出一个窗口,指示发生了可怕的事情,您是否希望它向 Redmond/Cupertino 等地发送通知。这种故障停止行为在测试中当然是可取的,但它通常不是用户想要的。大多数应用程序程序都不是安全关键系统,并且在运行中中止它们对于用户来说可能是一种不愉快的体验,尤其是在这意味着他们丢失了工作的情况下。简而言之,用户通常希望他们的应用程序在可能的情况下具有容错能力。
事实上,用户不希望的确切行为是错误持续且重复地发生。Jim Gray 在他 1985 年的经典文章“为什么计算机停止工作以及可以做些什么?”5 中区分了两种错误。第一种是行为可预测且重复出现的错误——也就是说,每次程序遇到相同的输入并经历相同的步骤序列时,它们都会发生。这些是 玻尔错误,以玻尔原子命名,类似于经典原子模型,其中电子像行星一样围绕原子核旋转。玻尔错误在调试程序时非常有用,因为它们更容易重现并找到其根本原因。
第二种错误是海森堡错误,以海森堡不确定性原理命名,旨在表示量子力学中固有的不确定性,这种错误是不可预测的,并且无法可靠地重现。如今最常见的海森堡错误是并发错误(又名竞争条件),这些错误取决于调度事件出现的顺序和时间。海森堡错误通常也对观察者效应敏感;通过插入调试代码或在调试器中运行来查找错误的尝试通常会扰乱导致错误的事件序列,使其消失。
Jim Gray 指出,玻尔错误非常适合调试,但用户宁愿他们的错误是海森堡错误。为什么?因为玻尔错误对于用户来说是致命的:每次用户做同样的事情,他或她都会遇到相同的错误。另一方面,对于海森堡错误,当您再次运行程序时,错误通常会消失。这与用户已经在 Web 上表现出的行为完美匹配。如果他们转到网页并且该网页没有响应,他们只需单击“刷新”,通常就可以解决问题。
因此,改善用户生活的一种方法是将玻尔错误转换为海森堡错误——如果我们能弄清楚如何做到这一点的话。
我和我在马萨诸塞大学阿默斯特分校的研究生,与我在微软研究院的同事 Ben Zorn 合作,在过去几年中一直在研究保护程序免受错误影响的方法。该研究的第一个成果是一个名为 DieHard (http://diehard-software.org/) 的系统,该系统使内存错误不太可能影响用户。DieHard 完全消除了某些错误,并将其他错误转换为(罕见的)海森堡错误。
要了解 DieHard 的工作原理,让我们回到汽车类比。使汽车不太可能相互碰撞的一种方法是将它们间隔得更远,以便在出现问题时提供足够的制动距离。DieHard 通过接管所有内存管理操作并在大于所需空间的空间中分配对象来提供这种“防御性驾驶”。
这种事实上的填充增加了小溢出最终会进入未分配空间的可能性,在那里它不会造成任何危害。然而,DieHard 不仅仅是在对象之间添加固定量的填充。这会为足够小的溢出提供很好的保护,而对其他溢出则提供零保护。换句话说,这些溢出仍然是玻尔错误。
相反,DieHard 通过在堆上随机分配对象来提供概率性内存安全。DieHard 自适应地调整其堆的大小,使其略大于应用程序所需的最大大小;默认值为 1/3。2,3 DieHard 从越来越大的块(称为迷你堆)中分配内存。
通过在所有迷你堆中随机分配对象,DieHard 使许多内存溢出变得良性,其概率自然会随着溢出大小的增加和堆变得越来越满而降低。效果是,在大多数运行 DieHard 的情况下,小溢出很可能没有影响。
DieHard 的随机分配方法还降低了free垃圾回收解决的与释放相关的错误。DieHard 使用位图(存储在堆外部)来跟踪已分配的内存。设置为 1 的位表示给定的块正在使用中;0 表示可用。
这种使用位图管理内存的方式消除了双重释放的风险,因为将位重置为 0 两次与重置一次相同。将堆元数据与堆中的数据分开保存,使得不可能意外地损坏堆本身。
最重要的是,DieHard 大大降低了悬空指针错误的风险,这些错误实际上消失了。如果堆中有 100 万个已释放的对象,那么您将立即重用刚刚释放的对象的机会实际上是百万分之一。相比之下,大多数分配器会立即回收已释放的对象。使用 DieHard,即使在 10,000 次重新分配之后,仍然有 99% 的机会不会重用悬空对象。
由于 DieHard 以(摊销)恒定时间执行其分配,因此它可以在性能方面几乎没有额外成本的情况下提供额外的安全性。例如,在浏览器中使用它不会造成可感知的性能影响。
在微软研究院,使用 DieHard 的变体预防了 Microsoft Office 数据库中约 30% 的错误,而对性能没有可感知的影响。从 Windows 7 开始,Microsoft Windows 现在附带了一个 FTH(容错堆),它直接受到 DieHard 的启发。通常,应用程序使用默认堆,但在程序崩溃超过一定次数后,FTH 会接管。与 DieHard 一样,FTH 将堆元数据与堆分开管理。它还添加了填充和延迟分配,但它不提供 DieHard 的概率容错,因为它不随机化分配或释放。FTH 方法特别有吸引力,因为它就像一个气囊:当一切正常时,它实际上是不可见的且无成本的,但在需要时提供保护。
容忍错误是提高已部署软件有效质量的一种方法。如果软件不仅可以容忍故障,还可以纠正故障,那就更好了。我们开发了 Exterminator,它是 DieHard 的后续系统,它正是这样做的。9,10
Exterminator 使用扩展版本的 DieHard 来检测错误(称为 DieFast)。虽然 DieHard 概率性地容忍错误,但 DieFast 也概率性地检测它们。当 Exterminator 发现错误时,它会转储一个堆映像,其中包含堆的完整状态,但不包含实际内容。然后,Exterminator 处理一个或多个堆映像,以定位错误的来源。随机化意味着每个堆映像都将具有完全打乱的对象,这使得 Exterminator 可以应用概率性错误隔离算法,根据生成的堆损坏模式来识别缓冲区溢出和悬空指针错误。然后,它可以计算出发生了哪种错误以及错误发生在哪里。
Exterminator 不仅将此信息发送回程序员,以便他们可以修复软件,而且它还通过运行时补丁自动纠正错误。例如,如果它检测到某个对象导致了八个字节的缓冲区溢出,它将始终为这些对象(通过其调用站点和大小来区分)分配八字节的填充。如果对象被过早释放,Exterminator 将推迟其回收。Exterminator 可以从多次运行或多个用户的结果中学习,因此它可以用于主动推送补丁,以防止其他用户遇到它已经在其他地方检测到的错误。
我的团队和其他人(特别是麻省理工学院的 Martin Rinard、伊利诺伊大学的 Vikram Adve、加州大学圣地亚哥分校的 Yuanyuan Zhou、威斯康星大学的 Shan Lu 以及华盛顿大学的 Luis Ceze 和 Dan Grossman)在为其他类别的错误构建安全系统方面取得了巨大进展。我们最近发表了关于预防并发错误的系统的工作,其中一些错误我们可以自动消除 (http://plasma.cs.umass.edu/emery/software)。
Grace 是一个运行时系统,它消除了使用 fork-join 并行性的并发程序的并发错误。它劫持线程库,在“幕后”将线程转换为进程,并使用虚拟内存映射和保护来强制执行行为,即使在多核处理器上也能产生顺序执行的错觉。1 Dthreads(确定性线程)是 Posix 线程库的完整替代品,它为多线程代码强制执行确定性执行。7 换句话说,使用 Dthreads 运行的多线程程序永远不会出现竞争;每次使用相同的输入执行都会生成相同的输出。Dthreads 使用与 Grace 类似的机制,并添加了确定性锁定和基于差异的冲突解决,使其能够支持任意多线程程序。
我们期待着在不远的将来,这种更安全的运行时系统将成为常态。正如我们现在几乎无法想象没有众多安全功能的汽车一样,我们最终也开始为软件采用类似的理念。有缺陷的软件是不可避免的,在可能的情况下,我们应该部署安全系统,以减少其对用户的影响。
1. Berger, E. D., Yang, T. Liu, T., Novark, G. 2009. Grace:用于 C/C++ 的安全多线程编程。在第 24 届 SIGPLAN 面向对象程序设计系统语言和应用程序会议 (OOPSLA’09) 会议论文集中:81–96。
2. Berger, E. D., Zorn, B. G. 2006. DieHard:不安全语言的概率性内存安全。在2006 年 SIGPLAN 程序设计语言设计与实现会议 (PLDI) 会议论文集中:158–168。
3. Berger, E. D., Zorn, B. G. 2007. 高效的概率性内存安全。马萨诸塞大学阿默斯特分校计算机科学系技术报告 UMCS TR-2007-17。
4. Bessey, A., Block, K., Chelf, B., Chou, A., Fulton, B., Hallem, S., Henri-Gros, C., Kamsky, A., McPeak, S., Engler, D. 2010. 数十亿行代码之后:使用静态分析在现实世界中查找错误。《 通讯》53(2):66–75。
5. Gray, J. 1985. 为什么计算机停止工作以及可以做些什么?Tandem TR-85.7;http://www.hpl.hp.com/techreports/tandem/TR-85.7.html。
6. Hertz, M., Berger, E. D. 2005. 量化垃圾回收与显式内存管理的性能。《第 20 届 SIGPLAN 面向对象程序设计、系统、语言和应用程序年会会议论文集 (OOPSLA’05):313–326。
7. Liu, T., Curtsinger, C., Berger, E.D. 2011. Dthreads:高效的确定性多线程。《第 23 届 操作系统原理研讨会 (SOSP ’11) 会议论文集》:327–336。
8. Nethercote, N., Seward, J. 2007. Valgrind:用于重量级动态二进制插桩的框架。在 SIGPLAN 程序设计语言设计与实现会议 (PLDI) 会议论文集中:89–100。
9. Novark, G., Berger, E. D., Zorn, B. G. 2007. Exterminator:以高概率自动纠正内存错误。在 SIGPLAN 程序设计语言设计与实现会议 (PLDI) 会议论文集中:1–11。
10. Novark, G., Berger, E. D., Zorn, B. G. 2008. Exterminator:以高概率自动纠正内存错误。《 通讯》51(12):87–95。
11. Oliner, A., Ganapathi, A., Xu, W. 2011. 日志分析的进展和挑战。《》9(12);https://queue.org.cn/detail.cfm?id=2082137。
12. 赛门铁克。2006 年。《互联网安全威胁报告》,第 X 卷(9 月);http://www.symantec.com/threatreport/archive.jsp。
13. Yuan, D., Mai, H., Xiong, W., Tan, L., Zhou, Y., Pasupathy, S. 2010. Sherlog:通过连接运行时日志中的线索进行错误诊断。在第 15 届编程语言和操作系统体系结构支持会议 (ASPLOS ’10) 会议论文集:143–154。
14. Yuan, D., Zheng, J., Park, S., Zhou, Y., Savage, S. 2012. 通过日志增强提高软件可诊断性。《 计算机系统汇刊》30(1):4:1–4:28。
喜欢还是讨厌?请告诉我们
EMERY BERGER 是马萨诸塞大学阿默斯特分校计算机科学系的副教授,他在那里领导 PLASMA 实验室。他于 2002 年在德克萨斯大学奥斯汀分校获得计算机科学博士学位,并在微软研究院担任访问科学家,在加泰罗尼亚理工大学/巴塞罗那超级计算中心担任高级研究员多年。Berger 的研究领域涵盖编程语言、运行时系统和操作系统,尤其关注透明地提高可靠性、安全性和性能的系统。他是包括 Hoard 和 DieHard 在内的各种广泛使用的软件系统的创建者。他是 的高级会员,并且是 Transactions on Programming Languages and Systems 的副编辑。
© 2012 1542-7730/12/0700 $10.00
最初发表于 Queue vol. 10, no. 7—
在 数字图书馆 中评论这篇文章
Alex E. Bell - UML 热:诊断与恢复
传染病研究所最近发表研究,证实 UML 热1 的多种不同变种持续在全球蔓延,不分青红皂白地感染软件分析师、工程师和经理。已经观察到,这种热病最严重的副作用之一是显著增加了软件产品的开发成本和持续时间。这种增加主要归因于生产力下降,因为受热病影响的个人将时间和精力投入到对生产可交付产品几乎没有或没有价值的活动中。例如,开放环路热病的患者继续为未知的利益相关者创建 UML(统一建模语言)图。
George Brandman - 企业补丁
软件补丁管理已发展成为一个业务关键问题——从风险和财务管理角度来看都是如此。根据 Aberdeen Group 最近的一项研究,企业在 2002 年在操作系统补丁管理上花费了超过 20 亿美元1。Gartner 研究进一步指出,管理良好的 PC 的运营成本每年比未管理的 PC 大约低 2,000 美元2。您可能会认为,随着临界质量和更复杂的工具的出现,大型组织中每个端点的管理成本会更低,但实际上可能并非如此。
Joseph Dadzie - 理解软件补丁
软件补丁是当今计算环境中日益重要的一个方面,因为软件运行的卷、复杂性和配置数量已大大增加。软件架构师和开发人员尽一切努力构建安全、无错误的软件产品。为了确保质量,开发团队利用他们掌握的所有工具和技术。例如,软件架构师将安全威胁模型融入到他们的设计中,QA 工程师开发自动化测试套件,其中包括复杂的代码缺陷分析工具。