ACM通信

研究突出了

灭虫器:自动纠正内存错误与高概率

文/吉恩·诺瓦克，埃默里·d·伯格，本杰明·g·佐恩
ACM通信，2008年12月，第51卷第12期，87-95页
10.1145/1409360.1409382
评论

用C和c++编写的程序容易出现内存错误，包括缓冲区溢出和悬浮指针。这些错误可能导致崩溃、错误的执行和安全漏洞，众所周知，修复这些错误的成本很高。跟踪它们在源代码中的位置是困难的，即使程序的全内存状态是可用的。一旦错误最终被发现，修复它们仍然具有挑战性:即使是关键的安全敏感漏洞，从最初报告到发布补丁的平均时间接近1个月。

我们介绍了Exterminator，一个自动纠正基于堆的内存错误而无需程序员干预的系统。灭虫器利用随机化来高精度地查明错误。从这些信息中，灭虫师得到运行补丁修复当前和后续执行中的这些错误。此外，Exterminator通过合并多个用户生成的补丁，支持协作错误纠正。我们提出了分析和经验的结果，证明了Exterminator在检测和纠正注入和实际故障方面的有效性。

回到顶部

1.简介

在C和c++中使用手动内存管理和未检查的内存访问会使用这些语言编写的应用程序容易出现一系列内存错误。这包括缓冲区溢出(读取或写入超出已分配区域)和悬浮指针(程序在内存仍然存在时释放内存)。内存错误会导致程序崩溃或产生不正确的结果。更糟糕的是，攻击者经常能够利用这些内存错误获得对系统的未经授权访问。

调试内存错误是出了名的困难。重新生成错误需要公开错误的输入。由于已部署程序的输入通常不可用，开发人员必须编造这样的输入，或者通过代码检查发现问题。一旦测试输入可用，软件开发人员通常使用像Purify这样的堆调试工具来执行应用程序⁷Valgrind,¹⁰这可能会使执行速度降低一个数量级。当bug最终被发现时，开发人员必须构建并仔细测试一个补丁，以确保它在不引入任何新bug的情况下修复了bug。这个过程既昂贵又耗时。例如，根据赛门铁克(Symantec)的数据，从发现一个严重的、远程可采企业应用程序的内存错误和补丁发布是28天。¹⁷

由于记忆错误很难发现和修复，研究人员提出了许多解决方案，大致可分为两类:检测，防止错误被利用，并可能使它们更容易调试;还有容忍度，误差的影响被减轻了。停止运行故障系统是基于编译器的方法，可能需要访问源代码，并在程序执行非法操作(如缓冲区溢出)时中止程序。^{1，2，6，9}

容错运行时系统，试图隐藏错误的影响，也被提出。Rinard的failure-oblivious系统也是基于编译器的，但是会生成读值并删除或缓存非法写入，以供以后重用。^13，14Rx系统¹²使用日志记录和重放，具有潜在的扰动，以提供容错能力。我们之前的作品《DieHard》^3.，4使用堆过度供应、布局随机化和可选的基于投票的复制来减少错误产生影响的可能性(参见3.1节的概述)。顽固的提供概率内存安全，使应用程序产生一种错觉，即拥有一个具有定义良好的概率的无限堆。贡献:本文介绍灭鼠药，这是一个运行时系统，它不仅可以容忍，而且还可以检测、隔离和纠正两类基于堆的内存错误，概率很高。Exterminator既不需要源代码也不需要程序员的干预，可以修复现有的错误而不引入新的错误。据我们所知，这是第一个这样的系统。

灭虫器依赖于一个有效的概率调试分配器我们称之为DieFast．DieFast是基于DieHard的分配器，它确保堆是独立随机的。然而，虽然DieHard只能概率地容忍错误，但DieFast却能概率地检测到错误。

当Exterminator发现错误时，它会转储一个堆的图像它包含堆的完整状态。根除者的概率误差隔离算法处理一个或多个堆图像，试图定位错误的来源。这种错误隔离算法具有较低的假阳性和假阴性率。可以区分缓冲区溢出和悬浮指针错误，因为它们往往会产生不同的堆损坏模式。

一旦Exterminator定位到缓冲区溢出，它就会确定溢出对象的分配位置和溢出的大小。对于悬浮指针错误，Exterminator会确定悬浮对象的分配和删除位置，并计算释放对象的时间有多早。

有了这些信息，Exterminator通过生成运行补丁．这些补丁在一个上下文中运行纠正分配器．纠正分配器通过填充对象防止溢出，并通过延迟对象释放防止悬浮指针错误。这些操作造成的空间开销很小，因为Exterminator的运行时补丁针对每个错误的特定分配和回收地点进行了定制。

在Exterminator完成补丁生成后，它既存储补丁以在后续执行中纠正错误，又在运行程序中触发补丁更新以修复当前执行中的错误。灭虫剂的补丁也组成直接，使协作bug修正:运行Exterminator的用户可以自动合并他们的补丁，从而系统地、持续地提高应用的可靠性。

灭虫器可以在三种不同的模式下工作迭代模式对于运行相同的输入，a复制模式可以随时纠正错误，而且累积模式这纠正了同一应用程序的多次运行中的错误。

我们通过实验证明，为了减少运行时开销(约25%)，Exterminator可以有效地隔离和纠正注入的和实际的内存错误，包括Squid Web缓存服务器和Mozilla Web浏览器中的缓冲区溢出。

回到顶部

2.内存错误

不正确的程序会出现与堆对象相关的各种错误，包括悬空指针，当堆对象仍然存在时释放它;无效的释放，即程序释放一个从未被分配器返回的对象;双释放，其中一个堆对象被多次释放，而不进行中间分配;未初始化的读取在这种情况下，程序尽管正确地使用了所有指针，但还是读取了从未初始化的内存;而且球出界线写道，其中要写入的内存地址是通过使用指向对象的有效指针而不是错误的偏移量或索引来计算的，因此计算的地址位于对象之外。我们使用这个术语缓冲区溢出引用与基指针的偏移量为正且太大的越界写操作。(在实践中，偏移量为负的越界写入似乎不太常见。)

如果处理不当，像双重释放和无效释放这样的错误会导致分配器元数据不一致，是一个潜在的安全漏洞。这些错误可能导致堆损坏或程序突然终止。越界写入和悬空指针可能导致分配器元数据或应用程序对象的损坏。未初始化的读取，因为读取的值不是由语言语义指定的，会以任意方式影响应用程序的执行。由于良好的分配器设计可以减轻双释放和无效释放的影响，缓冲区溢出和悬浮指针错误是目前最常被利用的堆错误，因此也是最重要的解决方法。

虽然DieHard在概率上容忍堆对象的悬浮指针和缓冲区溢出，但Exterminator同时检测并永久纠正它们。灭虫者的分配器(DieFast)分享死忠的免疫双重免费和无效免费。清除程序目前不处理未初始化的读取、对象边界外的读取或带负偏移量的超出边界的写入。

回到顶部

3.软件架构

Exterminator的软件架构扩展和修改了DieHard，以启用其错误隔离和纠正属性。本节首先介绍DieHard，然后介绍Exterminator如何扩展其堆布局，以跟踪识别和纠正内存错误所需的信息。其次，它提出了DieFast，一个概率调试分配算法，暴露错误的除虫器。最后，介绍了灭虫的三种操作模式。

3.1.顽固的概述

DieHard系统包括一个基于位图的，完全随机的内存分配器，它提供概率内存安全．^3.以Exterminator为基础的最新版本的DieHard会自适应地将堆的大小调整为米比应用程序所需的最大值大几倍⁴(见图1)．这个版本的DieHard从越来越大的块中分配内存miniheaps．每个小堆都包含一个大小的对象。DieHard分配新的小堆，以确保对于每个大小，分配的对象与总对象的比例永远不会超过1/米．每个新的小堆都是之前最大的小堆的两倍大，因此容纳的对象数量是之前最大的小堆的两倍。

分配随机探测给定大小类的小堆位图，其中0位表示可用来回收的空闲对象，并将其设置为1。这个操作需要O(1)预期时间。释放有效对象将重置适当的位，这也是一个常量时间操作。DieHard在过度配置的堆中使用随机化，使得缓冲区溢出很可能会占用空闲空间，而最近释放的对象不太可能很快被重用。

DieHard可选地使用复制来增加成功执行的概率。在这种模式下，它向应用程序进程的多个副本广播输入，每个副本都使用不同的随机种子初始化。投票人拦截并比较副本之间的输出，只实际生成多个副本同意的输出。每个副本堆的独立随机化使得内存错误的概率独立。因此，复制以指数方式降低了内存错误影响输出的可能性，因为错误破坏大多数副本的可能性很低。

3.2.灭虫器的堆布局

图2显示“灭虫器”的堆布局，其中每个对象包含用于错误隔离和校正的五个字段对象id，分配而且回收地点，回收时间，它记录对象被释放的时间淡一点．

的对象id。n表示对象是n分配的对象。Exterminator使用对象id在多个程序执行中跨堆识别对象。这些id是必需的，因为对象地址不能用于在不同的随机堆之间标识它们。站点信息字段捕获分配和释放的调用上下文:最近的五个返回地址的最低有效字节的32位散列。金丝雀位表示对象是否被金丝雀填充(参见3.3节)。所有这些元数据在分配对象时初始化，并在释放对象后持续存在，直到在其位置上分配新对象。

这个带外元数据加上分配位的空间开销是16字节加上每个对象的2位空间开销。这个数量与典型的基于自由列表的内存管理器(如Lea分配器)相当，它在每个对象前附加一个8或16字节的头(在32或64位系统上)。⁸

3.3.一个概率调试分配器

灭虫者使用了一种新的概率调试分配器，我们称之为DieFast。DieFast使用与DieHard相同的随机堆布局，但扩展了其分配和回收算法，以检测和暴露错误。与以前的调试分配器不同，DieFast有许多不同寻常的特性，专门用于Exterminator上下文中。

3.3.1.隐式围栏

许多现有的调试分配器用篱笆桩填充已分配对象金丝雀价值观)。因此，它们可以通过检查这些围栏桩的完整性来检测超出对象开始或结束的写操作。这种方法有增加空间需求的缺点。结合基于diehard的堆已经增加的空间需求，填充的额外空间开销可能大得无法接受。

DieFast利用两个事实来获得栅栏柱的效果，而不需要任何额外的空间开销。首先，因为它的堆布局是无头的，一个篱笆桩有双重作用:一个对象后面的篱笆桩充当下一个对象前面的篱笆桩。第二，因为已分配对象的间隔是(平均)米当堆上有1个释放的对象时，我们使用释放的空间作为栅栏。

3.3.2.随机的金丝雀

传统的调试金丝鸟包括值，例如十六进制值OxDEADBEEF，它们很容易在调试会话中与正常程序数据区分开来。然而，确定性选择金丝雀的一个缺点是，程序总是可能使用金丝雀模式作为数据值。由于DieFast使用位于空闲空间而不是已分配空间的金丝雀，如果数据值在已分配对象中是常见的，那么固定的金丝雀将导致较高的假阳性率。

DieFast在启动时使用一个随机的32位值设置。由于canary值和堆地址都是随机的，每次执行都不同，任何固定的数据值(类似地，任何给定的指针)与canary发生冲突的概率都很低;这确保了较低的假阳性率(参见定理2)。为了增加检测到错误的可能性，DieFast总是将canary值的最后一位设置为1。如果金丝雀被解引用，设置这个位将导致对齐错误，但仍然保持与金丝雀意外碰撞的概率较低(1/2³¹)．

3.3.3.概率围栏

直观地说，暴露悬浮指针错误最有效的方法是用金丝雀值填充所有释放的内存。例如，将canary值解引用为指针可能会触发分割违规或对齐错误。

不幸的是，读取随机值并不一定会导致程序失败。例如，在浓缩咖啡基准，一些对象持有bitset。用随机值填充释放的bitset不会导致程序终止，但可能会影响计算的正确性。

当从一个充满金丝雀的悬吊对象中读取会导致程序运行错误时，很难隔离错误。在最坏的情况下，堆的一半可能被释放的对象填充，所有对象都被金丝雀值覆盖。所有这些对象都可能成为悬浮指针错误的潜在来源。

在累积模式下，Exterminator通过在每次释放对象时做出随机选择来防止这种情况;它不是总是用金丝雀填充被释放的对象并设置相关的金丝雀位，而是有概率地执行这种填充和位设置操作p．这种概率方法似乎降低了灭虫者发现错误的能力。但是，它需要隔离只读悬浮指针错误，在这种情况下金丝雀本身保持不变。因为需要大量的迭代或复制来隔离这些错误，所以当不以累积模式运行时，Exterminator总是用金丝雀填充已释放的对象(参见第5.2和7.2节进行讨论)。

3.3.4.概率错误检测

每当DieFast分配内存时，它检查要返回的内存，以验证它应该包含的任何金丝雀(由金丝雀bitset表示)都是完整的。如果不是，除了发出错误信号(参见3.4节)，DieFast还会为该内存块设置分配位。这种“坏对象隔离”确保对象在未来分配时不会被重用，而保留其内容以供Exterminator后续使用。通过检查每个分配上的canary完整性，DieHard可以预计在大约H分配,H是堆上对象的数量。

每次释放后，DieFast都会检查前面和后面的对象。对于每一种食物，DieFast都会检查它们是否免费。如果是，它执行与上面相同的金丝雀检查。回想一下，因为DieFast的分配是随机的，所以这些相邻对象的标识在每次运行时都是不同的。检查每个空闲对象上的后续对象和前一个对象，允许DieFast对附近的任何越界写操作执行廉价的检查，包括“跨步”对象写操作(例如，(我+ 32))可能会跳过后面的物体。

3.4.操作方式

除虫器可以在三种操作模式下使用:一种适合测试或所有程序输入都可用于重复执行的迭代模式，一种复制模式适合测试和受限部署场景，一种累积模式适合广泛部署。所有这些都依赖于堆映像的生成，Exterminator检查堆映像以隔离错误并计算运行时补丁。

如果Exterminator在执行程序时发现错误，或者DieFast发出错误信号，那么Exterminator会强制进程发出堆映像文件。该文件类似于核心转储，但包含更少的数据(例如，没有代码)，并且组织起来是为了简化处理。除了完整的堆内容和堆元数据之外，堆映像还包括当前分配时间(即到目前为止分配的数量)。

3.4.1.迭代模式

灭虫器的迭代模式不需要复制。要查找单个bug，首先通过命令行选项调用Exterminator，指示它在检测到错误时立即停止。除虫器然后在“重播”模式下对相同的输入重新执行程序(但使用一个新的随机种子)。在这种模式下，Exterminator从初始堆映像读取分配时间，以便在该点中止执行;我们称之为amalloc断点．然后，Exterminator开始执行并忽略在到达malloc断点之前引发的DieFast错误信号。

一旦到达malloc断点，Exterminator将触发另一个堆映像转储。这个过程可以重复多次以生成独立的堆映像。然后，消灭程序执行事后错误隔离和运行时补丁生成。少量的迭代通常就足以让Exterminator为单个错误生成运行时补丁，如我们在第7.2节中所示。当使用包含这些更改的纠正内存分配器(在6.3节中详细描述)运行时，这些补丁会自动修复隔离错误。

3.4.2.复制模式

当所有输入都可用时，上面描述的迭代模式工作良好，因此重新运行执行是可行的。然而，当应用程序部署在现场时，这样的输入可能不可用，并且重放可能不切实际。复制的操作模式允许Exterminator在程序运行时纠正错误，而不需要多次迭代。

作为图3显示，Exterminator(就像DieHard)可以同时运行多个不同的随机副本(作为单独的进程)，向所有人广播输入并对输出进行投票。但是，Exterminator使用基于diefast的堆，每个堆都有一个校正分配器。这个组织让Exterminator发现并修复错误。

在复制模式下，当DieFast发出错误信号或投票人检测到发散的输出时，Exterminator会发送一个信号，为每个副本触发堆图像转储。如果任何副本由于分段错误而崩溃，除虫程序也会转储堆映像。

如果DieFast发出错误信号，转储堆映像的副本不必停止执行。如果它们的输出继续一致，则可以继续与错误隔离进程并发执行。一旦运行时补丁生成过程完成，它就向正在运行的副本发出信号，让其重新加载运行时补丁。因此，同一进程中的后续分配将在不中断执行的情况下动态地进行修补。

3.4.3.累积模式

虽然复制模式可以在部署的应用程序中动态地隔离和纠正错误，但它可能并不适用于所有情况。例如，复制具有高资源需求的应用程序可能会导致不可接受的开销。此外，多线程或非确定性应用程序可以显示不同的分配活动，从而导致对象id在多个副本之间发散。为了支持这些应用，Exterminator使用了第三种操作模式，累积模式，该模式隔离错误，无需复制或多次相同的执行。

当在累积模式下操作时，Exterminator会根据分配和回收站点而不是单个对象对对象进行分组，因为对象在不同的执行中不再保证相同。

由于来自给定站点的对象只是偶尔会导致错误，而且通常是低频率的错误，为了识别这些低频率的错误而不产生高的假阳性率，Exterminator需要比复制或迭代模式执行更多的执行。Exterminator不是存储多次运行的堆映像，而是计算每次运行的相关统计信息，并将其存储在补丁文件中。与每个堆映像的几十或几百兆字节相比，每次执行保留的数据大约是几千字节。

回到顶部

4.迭代和复制错误隔离

灭虫器采用两种不同的错误隔离算法:一组用于复制和迭代模式，另一组用于累积模式。

当以复制或迭代模式操作时，Exterminator的概率错误隔离算法通过在多个堆图像之间搜索差异来操作。灭虫器依靠存储在已释放对象中的损坏金丝雀来指示错误的存在。损坏的金丝雀(被覆盖的金丝雀)可能意味着两件事。如果所有堆映像中的同一个对象(由对象id标识)具有相同的损坏，则错误很可能是一个悬浮指针。如果多个释放对象中的金丝雀被损坏，则错误很可能是缓冲区溢出。消除程序限制溢出和悬浮指针错误的误报数量。

4.1.缓冲区溢出检测

除虫器检查堆图像，寻找堆之间的差异，包括覆盖的金丝雀和活动对象。如果一个对象在堆中不相等，则Exterminator将其视为候选对象受害者溢出的。

为了识别受害对象，Exterminator在所有堆中通过对象id进行标识，比较等价对象的内容。灭虫员建造溢出面具这包括在所有堆中发现的差异。但是，因为相同的逻辑对象在多个堆之间可能存在合理的差异，所以Exterminator必须注意不要将这些情况视为溢出。

首先，释放的对象在堆中可能不同，因为它只在某些堆中填充了金丝雀。灭虫者使用金丝雀位图来识别这种情况。

其次，一个对象可以包含指向其他对象的指针，这些对象随机地位于它们各自的堆上。灭虫器使用确定性和概率技术来区分整数和指针。简单地说，如果一个被解释为指针的值指向堆区域内的所有堆，并且指向相同的逻辑对象，那么Exterminator认为它是相同的逻辑指针，因此不存在差异。Exterminator还处理指针指向动态库的情况，这些动态库位于Linux的新版本的伪随机基址。

最后，对象可以包含在不同流程之间合理不同的值。这些值的例子包括进程id、文件句柄、伪随机数和依赖于地址的数据结构中的指针(例如，一些红黑树实现)。当Exterminator检查一个对象并在所有堆的同一位置上遇到任何不同的单词时，它会认为它是合理的不同，而不是缓冲区溢出的迹象。

对于小型溢出，忽略跨多个堆的相同对象的覆盖而错过溢出的风险很低:

定理1。设k为堆图像的数量，S为堆图像的长度(以对象数量为单位)溢出的字符串，H表示堆上的对象数量。那么溢出在所有k堆上覆盖一个对象的概率为

证明。这一结果适用于比通常更强大的对手，而不是假设单个连续溢出，我们允许攻击者任意覆盖任何溢出年代不同的对象。考虑一个给定的对象一个．在每个堆上，年代对象是随机损坏的。物体的概率我在单个堆上损坏是吗(S / H)．调用E_我．对象的事件我在所有的堆上都是腐坏的;的概率P(E_我)是(S / H)^k．在所有堆中至少有一个对象损坏的概率为P(_我E_我.)，通过一个直接的并界，它是最大的年代_我P（E_我) =H×(S / H）^k．

我们现在限定了缓冲区溢出的最坏情况假负率;也就是说，因为没有覆盖任何金丝雀而找不到缓冲区溢出的几率。

定理2。设M为堆乘数，因此堆的满数永远不会超过1/M。长度为b字节的溢出通过与金丝雀进行比较而无法检测到的可能性最大：

证明。每个堆至少为(米1) / Mfree。自从DieFast用金丝雀填满了自由空间P= 1/2，每个装满金丝雀的堆的分数至少为(米1) / 2米．随机写的字没有落在金丝雀身上的可能性k因此，堆最多(1)米1) / 2米）^k．溢出字符串也可以匹配canary值。由于金丝雀是随机选择的，这种情况的概率最多为(1/256)。^b．

4.2.罪魁祸首识别

此时，Exterminator已经确定了溢出的可能受害者。对于每个受害者，它扫描堆图像以寻找匹配的的罪魁祸首，该对象很可能是溢出到受害者的源。因为Exterminator假设在迭代或复制模式下操作时溢出是确定的，因此罪魁祸首必须是相同的距离d在每一个堆图像中都远离受害者的字节。此外，Exterminator要求溢出的值在整个图像中有一些相同的字节，并根据它们的相似度对它们进行排序。注意，虽然除虫者只考虑正的值d，这些值可以任意大。

消除程序检查每一个其他堆映像的候选罪魁祸首，并检查相同的对象d字节。如果该对象是自由的，应该被金丝雀填充，但它们不是完整的，那么它会将这对罪犯-受害者添加到候选列表中。

我们现在限定了假阳性率。因为缓冲区溢出可能是不连续的，所以堆中溢出之前的每个对象都是潜在的罪魁祸首。但是，每增加一个堆，这个数字就会大大降低。

定理3。相同距离的物体(可能的罪魁祸首)的预期数量d从任何给定的受害者对象穿过k堆

证明。在不丧失通用性的前提下，假设受害对象占用每个堆中的最后一个槽。因此，一个对象可以在任何剩余的空间中n＝H1插槽。它在同一个槽里的概率k堆是p= 1 / (H1)^k1。这是一个二项分布E(可能的罪犯)=np1 / (H1）^k2.

如果只有一个堆映像，则all (H-1)物体是潜在的罪魁祸首，但一个额外的图像将任何受害者的预期罪魁祸首数量减少到仅1 (1/(H1）⁰)，有效地消除了误报的风险。

一旦“灭虫器”确定了一个“罪犯-受害者”对，它就会记录该“罪犯”的溢出大小为所观察到的最大值d给一个受害者。灭虫专家还会给每个罪犯-受害者配对打分，根据他们的信心，这是一个真正的溢出。这个分数是1 (l/256)^年代,在那里年代是跨所有对检测到的溢出字符串的长度之和。直观地说，仅在少数堆图像中检测到的小溢出字符串(例如1字节)会得到较低的分数，而在许多堆图像中出现的大溢出字符串会得到较高的分数。

在溢出处理完成并且至少有一个罪魁祸首获得非零分之后，Exterminator会为排名最高的罪魁祸首的溢出生成一个运行时补丁。

4.3.悬浮指针隔离

隔离悬浮指针错误分为两种情况:程序可以读和写将其部分或完全覆盖，或者只覆盖读通过悬浮指针。Exterminator不能在迭代或复制模式下处理只读悬浮指针错误，因为它需要太多的副本(例如，大约20个;见第7.2节)。但是，它直接处理覆盖的悬垂对象。

当一个已释放的对象在多个堆映像中被相同的值覆盖时，Exterminator将此错误分类为悬浮指针覆盖。(如定理1所示，对于缓冲区溢出，这种情况不太可能发生。)然后，Exterminator生成适当的运行时补丁，如6.2节所述。

回到顶部

5.累积误差隔离

与迭代和复制模式不同，累积模式侧重于检测、隔离和纠正现场发生的错误。在这种情况下，复制、相同的输入和确定性执行都是不可行的。更糟糕的是，程序错误可能以固有的难以检测的方式表现出来。例如，读取写入自由对象的金丝雀的程序可能立即失败，或者在一段时间内错误地执行。

在这种模式下，我们的错误检测方法是将异常程序事件(如提前终止、引发意外信号等)视为内存在执行过程中损坏的证据。在假设错误需要纠正之前，我们通过统计证据的积累来应对这些情况下错误重现性的缺乏。消除程序通过计算多次执行累积的摘要信息，而不是通过对多个堆映像进行操作，以累积模式隔离内存错误。

5.1.缓冲区溢出检测

灭虫器的缓冲区溢出隔离算法分三个阶段进行。首先，它通过查找覆盖的金丝雀值来识别堆损坏。其次，对于每个分配站点，它计算来自该站点的对象可能是损坏源的概率估计值。第三，它结合这些来自多次运行的独立估计，以确定持续出现的可能导致腐败的网站。

Exterminator的随机分配器允许我们计算堆中某些属性的概率。例如，给定小堆大小和小堆的数量，就可以估计一个对象出现在给定小堆上的概率。如果来自某个分配站点的对象是溢出的来源，那么这些对象将比预期更频繁地出现在包含损坏的小堆上。Exterminator跟踪来自每个分配站点的对象在多次运行时出现在损坏的小堆上的频率。利用这些信息，它使用一种统计假设检验来确定经常发生腐败的站点，而不是随机的机会，并将它们确定为溢出的罪魁祸首(参见Novark¹¹更多详情)。

一旦Exterminator识别到错误的分配位置，它就会生成一个运行时补丁来纠正错误。为了找到正确的pad大小，它从当前运行期间发现的损坏开始向后搜索，直到找到从站点分配的对象。然后，它使用该对象和腐败结束之间的距离作为pad大小。

5.2.悬浮指针隔离

与缓冲区溢出一样，Exterminator的悬浮指针隔离器通过多次运行计算摘要信息。为了迫使每次运行有不同的效果，Exterminator以一定的概率用金丝雀填充释放的对象p把每次执行都变成一系列伯努利审判。在这种情况下，如果程序通过悬浮指针读取金丝雀数据，程序可能会崩溃。因此，为该对象写入金丝雀增加了程序稍后崩溃的可能性。相反，如果一个对象没有提前释放，那么用金丝雀覆盖它对程序的失败或成功没有影响。然后，Exterminator使用与其缓冲区溢出算法相同的假设测试框架来识别悬浮指针错误的来源。

的选择p反映了缓冲区溢出算法的精度与悬浮指针隔离之间的权衡。由于溢出隔离依赖于检测损坏金丝雀，因此值较低p增加运行的次数(虽然不是失败)，以隔离溢位。的值较低p通过降低某些分配站点(分配大量对象的站点)总是观察到一个指示值的风险，提高悬浮指针隔离的精度。我们现在设置p= 1/2，尽管一些悬浮指针错误可能需要较低的值p收敛:在合理的次数内收敛

然后，除虫器通过从已确定的分配地点找到最老的金丝雀对象，并计算从它被释放到程序失败之间的分配数量，来估计所需的寿命延长。然后，纠正分配器将与此分配/回收站点对应的所有对象的生命周期延长两倍。

回到顶部

6.误差修正

我们现在描述Exterminator如何使用来自错误隔离算法的信息来纠正特定的错误。除虫程序首先为每个错误生成运行时补丁。然后，它依赖于使用该信息的纠正分配器，填充分配以防止溢出，并延迟释放以防止悬浮指针错误。

灭虫器纠正记忆错误的能力有几个内在的局限性。灭虫器只能纠正有限溢出，因为它试图通过有限的过度分配来遏制任何给定的溢出。类似地，Exterminator通过在释放特定对象之前插入有限延迟来纠正悬浮指针错误。最后，当Exterminator用于定位这些错误的证据被销毁时，例如当溢出覆盖堆的大部分时，或当具有悬浮指针错误的程序运行时间长到重新分配悬浮对象时，Exterminator无法纠正内存错误。

6.1.缓冲区溢出校正

对于Exterminator遇到的每个罪犯-受害者对，它生成一个运行时补丁，由分配站点散列和包含溢出所需的填充量(d+溢出字符串的大小)。如果已经为给定的分配站点生成了运行时补丁，那么Exterminator将使用到目前为止遇到的最大填充值。

6.2.悬浮指针校正

悬浮指针的运行时补丁由其分配站点散列和延迟其释放的时间量组成。灭虫器计算这个延迟如下。让t记录悬吊物的释放时间，和T为程序崩溃或Exterminator检测到堆损坏的分配时间。灭虫者没有办法知道这个物体应该活多久，所以计算一个精确的延迟是不可能的。相反，它将对象的生命周期(延迟其释放时间)延长两倍于其提前释放时间与崩溃或检测时间之间的距离，加上1:2 × (Tt) + 1。

需要注意的是，这种回收延迟不会增加对象的生存期，而是增加它们的生存期拖．¹⁵举例来说，一个对象可能存在1000个分配期，然后过早地释放10个分配期。如果程序立即崩溃，Exterminator将延长其生命周期21个分配，将其正确生命周期(1010个分配)增加不到1%(1021/1010)。

6.3.更正内存分配器

纠正内存分配器合并了上面描述的运行时补丁，并在适当的时候应用它们。

在启动时，或在接收到重新加载信号(第3.4节)时，纠正分配器从指定的文件加载运行时补丁。它构建了两个哈希表垫表将分配地点映射到垫块大小，以及延期表将分配和回收站点对映射到一个延迟值。因为Exterminator可以重新加载运行时补丁文件并动态地重新构建这些表，所以它可以在不中断程序执行的情况下向正在运行的程序应用补丁。这方面的除虫者的操作可能特别有用的系统，必须保持持续运行。

在每次释放时，纠正分配器检查要释放的对象是否需要延迟。如果它找到对象的分配和回收位置的延迟值，它将推入延迟优先队列指针和实际释放它的时间(当前分配时间加上延迟值)。

纠正分配器检查每个分配的延迟队列，看是否有任何对象现在应该被释放。然后检查当前分配站点是否有相关的pad大小。如果是，它将pad大小添加到分配请求中，并将分配请求转发到底层分配器。

6.4.协作的校正

应用程序的每个用户可能会遇到不同的错误。为了允许整个用户社区自动提高软件的可靠性，Exterminator提供了一个支持协作校正的简单实用程序。这个实用程序接受许多运行时补丁文件作为输入。然后，它通过计算任何分配站点所需的最大垫大小和任何给定分配站点/回收站点对的最大延迟量来组合这些补丁。结果是一个新的运行时补丁文件，它涵盖了所有观察到的错误。因为补丁文件的大小受程序中分配站点的数量的限制，我们希望这些文件是紧凑和实用的传输。例如，Exterminator为注入错误生成的运行时补丁的大小浓缩咖啡只有130K(用gzip压缩时是17K)。

回到顶部

7.结果

我们的评估回答了以下问题:(1)使用Exterminator的运行时开销是多少?(2) Exterminator在发现和纠正内存错误(包括注入错误和实际错误)方面的效果如何?

7.1.灭虫器运行时开销

我们用SPECint2000套件评估灭虫器的性能¹⁶运行参考工作负载，以及一套分配密集型基准测试。我们使用后一套基准，一方面是因为它们在内存管理研究中被广泛使用，另一方面是因为它们的高分配强度强调内存管理性能。对于所有的实验，我们修复了Exterminator的堆倍增器(值米) 2点。

所有结果都是在一个静态的双处理器Linux系统上运行5次的平均值，该系统有3GB RAM，每个3.06 GHz Intel Xeon处理器(超线程活动)配备512K L2缓存。我们观察到的实验方差小于1%。

我们专注于非复制模式(迭代/累积)，我们希望这是Exterminator性能的关键限制因素和最常见的使用场景。

我们将Exterminator (DieFast加上更正分配器)的运行时与GNU libc分配器进行比较。这个分配器基于Lea分配器，⁸这是最快的。⁵图4表明，与此分配器相比，Exterminator的性能降低了0% (186.狡猾的)至132% (cfrac)，几何平均值为25.1%。虽然Exterminator的开销对于分配密集型套件来说是巨大的(几何平均值:81.2%)，其中计算分配和回收上下文的开销占主导，但它的开销在SPEC基准测试中明显不那么明显(几何平均值:7.2%)。

7.2.内存错误纠正

7.2.1.故障注入

为了测量Exterminator在隔离和纠正错误方面的有效性，我们使用了伴随DieHard发行版的错误注入器来注入缓冲区溢出和悬浮指针错误。对于每个数据点，我们使用随机种子运行注入器，直到触发错误或发散输出。接下来，我们使用这个种子确定地触发Exterminator中的一个错误，我们以迭代模式运行该错误。然后，我们测量隔离和生成适当的运行时补丁所需的迭代次数。图像的总数量(迭代加上第一次运行)对应于在复制模式下运行Exterminator时所需的副本数量。

注意，Exterminator纠正内存错误的方法在存在补丁时不会增加额外的执行时间开销。但是，通过填充分配或延迟释放，它会消耗额外的空间。

缓冲区溢出:对象中的对象有意缩小大小，从而触发了三个不同大小(4、20和36字节)的10个不同的缓冲区溢出浓缩咖啡基准。在每种情况下，需要三张图像来隔离和纠正这些错误。注意，这个结果比分析的最坏情况要好得多:对于三个图像，定理2将遗漏溢出的最坏可能性限制在42%(第4.1节)，但我们观察到假阴性率为0%。我们观察到的最大空间开销总共增加了2816字节。

悬浮指针错误:然后触发了10个悬浮指针错误浓缩咖啡除虫器在迭代和累积模式中运行。回想一下，在迭代模式下，Exterminator总是用金丝雀填充释放的对象，而在累积模式下运行时，它是概率性地这样做的(参见3.3节)。

在迭代模式下，Exterminator只运行了四次就成功地隔离了错误。在另外四场比赛中，浓缩咖啡不通过悬浮指针进行写操作。相反，它通过悬挂指针读取金丝雀值，将其视为有效数据，然后崩溃或中止。由于堆中没有损坏，Exterminator无法隔离错误源。在剩下的两次运行中，向悬挂的对象写入canaries会触发一连串错误，破坏堆的大部分部分。在这些情况下，损坏破坏了Exterminator隔离错误所需的信息。

然而，在累积模式下，概率金丝雀填充使Exterminator能够隔离所有注入错误，包括只读悬浮指针错误。对于没有发生大规模堆损坏的运行，Exterminator需要执行22到30次才能隔离和纠正错误。在每种情况下，在错误的位点对越过似然阈值之前，必须观察到15次失败。因为对象是随机覆盖的，所以产生15个失败所需的运行次数是不同的。当写入金丝雀会破坏堆的很大一部分时，Exterminator需要18次失败和34次运行。在某些运行中，执行会持续足够长的时间，以便分配器重用罪魁祸首对象，防止Exterminator观察到它被覆盖。

派生的运行时补丁的空间开销从32到1024字节不等(一个256字节的对象被四个释放延迟)。这个量占应用程序所消耗最大内存的不到1%。

7.2.2.真正的错误

我们还用两个应用程序中的实际bug测试了Exterminator: Squid Web缓存服务器和Mozilla Web浏览器。

Squid Web缓存:版本2.3s5的Squid有一个缓冲区溢出;某些输入会导致Squid在使用GNU libc分配器或Boehm-Demers-Weiser收集器时崩溃。

我们在Exterminator迭代模式下运行Squid三次，输入触发缓冲区溢出。除虫器在每次运行中继续正确执行，但溢出损坏了金丝雀。Exterminator的错误隔离算法将单个分配站点识别为罪魁祸首，并生成精确为6个字节的pad，修复错误。Mozilla Web浏览器:我们还在Mozilla 1.7.3/Firefox 1.0.6及更早版本中的已知堆溢出上测试了Exterminator的累积模式。此溢出(bug 307259)发生的原因是Mozilla在处理域名中的Unicode字符时出现错误。Mozilla不仅是多线程的，这会导致不确定的分配行为，而且移动鼠标时的细微差异也会导致分配序列的分散。因此，复制模式和迭代模式都不能跨多个运行识别等价的对象。

我们执行了两个案例研究，代表了使用Exterminator累积模式的合理场景。在第一项研究中，用户启动Mozilla并立即加载一个触发错误的页面。此场景对应于一个概念验证输入可用的测试环境。在第二项研究中，用户首先在选择的页面中导航(每次运行都不同)，然后访问触发错误的页面。这个场景近似于错误被随意触发的部署使用。

在这两种情况下，除虫器正确地识别溢出没有假阳性。在第一种情况下，Exterminator需要运行23次才能隔离错误。在第二种情况下，需要跑34次。我们认为这个场景需要更多的运行，因为产生溢出对象的站点分配更多正确的对象，这使得很难将其识别为错误的对象。

回到顶部

8.结论

本文介绍了Exterminator，一种自动纠正C和c++程序中基于堆的内存错误的系统。Exterminator完全在运行时级别上对未修改的二进制文件进行操作，并由三个关键组件组成:(1)DieFast，一个概率调试分配器，(2)一个概率错误隔离算法，以及(3)一个纠正内存分配器。灭虫器的概率错误隔离隔离的来源和范围的记忆错误，可证明低的假阳性和假阴性率。它的纠正内存分配器包含了错误隔离算法生成的用于纠正内存错误的运行时补丁。除虫器不仅适合在测试过程中使用，而且可以自动更正部署的程序。

回到顶部

致谢

我们感谢山姆·盖耶、迈克·希克斯、埃里克·莱内德-米勒、莎拉·奥森托斯基、马丁·里纳德和盖伊·斯蒂尔的宝贵反馈。本材料基于英特尔、微软研究和国家科学基金会职业奖CNS-0347339和CNS-0615211支持的工作。本材料中表达的任何意见、发现和结论或建议都是作者的观点，并不一定反映美国国家科学基金会的观点。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2008 ACM, Inc.

---

没有找到条目