【翻译】Naive Differences of Executable Code

Naive Differences of Executable Code

作者：Colin Percival

原文链接：bsdiff.dvi

摘要

随着发现严重安全漏洞的频率的增长以及对这些漏洞的利用频率的增长，使得应用程序比以往的更新频率更高。虽然直接对二进程文件更新比使用源码进行更新更加便利，但是由于指针在二进制文件中的广泛分布，使得很难去产生一个紧凑的补丁文件。

早期的方式依赖于对特定平台可执行文件的内部结构的了解，与其相反的是，我们找到了一种普遍的方式，它可以为任何可执行文件构建出一个极具竞争力的小补丁。

1. 介绍

从历史上来看，二进制文件是通过两个基础的操作来构建的，即复制和插入。使用子串匹配或者哈希技术【引用：MA00】，新文件的部分内容和旧文件是匹配的，这部分的内容进行复制，剩余的新的字节被存储在补丁文件中，最终通过插入的方式进行合成。因此以这种方式生成补丁的程序可以被认为是由两种指令组成的，即复制和插入。

不幸的是，任何源码的修改都会导致整个可执行文件的变化。添加或者删除少量的代码或数据，都会改变代码块的相对位置，然后通过跳过修改的区域来调整相对分支的位移，因此，位于修改区域之后的任何数据都会有不同的地址，从而导致整个文件中的数据指针被修改。这会导致通过传统的复制和插入的方式生成的补丁文件要比需要的大很多；在一个500kB的可执行文件中，一行代码的补丁会被翻译成一个50kB的补丁文件。

解决这个问题的其中一种方式就是依赖于对可执行文件内部结构的了解。例如在旧的可执行文件中某个指针的地址A，到了新的可执行文件中变成了地址B，那么其他指向地址A的指针也很可能会发生相同的变化。因此，通过有效的反汇编整个文件，记录每类替换的第一个实例，可以预测到未来的替换，从而消除了记录它们的必要【参考：BMM99】。然而，这种必要的反汇编意味着使用该方式的任何工具都将完全依赖于平台。

2. BSDiff

为了使用一种便携的方式来解决 “指针问题” ，我们提出了两项重要的观测结果：第一，在可执行文件的未被直接修改的区域中，差异通常是非常稀疏的。不仅修改后的地址只构成编译后的代码的一小部分，而且这地址也很可能只在其最重要的最低的一个或两个字节中被改变。第二，数据和代码通常只在块中移动，因此引用位置会导致大量不同的（旁边的）地址被调整相同的量。这两个观测结构说明了一个很重要的事实，即可执行文件的两个版本中对应相同源代码的区域能够互相匹配，字节差异大多数为0，即使不为0也会比其他值更频繁的使用某些值——-简单来说，字节差异的字串是可以被高度压缩的。

现在我们使用下述的方式构建补丁文件。首先，我们读取旧文件然后执行某种排序方法构建索引，可以使用哈希方式【引用：Tr99】或者后缀排序(例如，【引用：LS999】)。然后，我们使用这种索引，遍历新文件并找到一组与旧文件的区域完全匹配的区域。为了后续显而易见的原因，我们只记录这样的区域，它至少包含8个和前向匹配项不匹配的字节（例如，如果前一个匹配项是new[x...x+k] = old[y...y+k]，我们需要找一个这样的匹配项new[x'...x'+k'] = old[y'...y'+k']，它包含至少8个不同的i，然后new[x'+i] != old[x'+i+(y-x)]）。

传统的二进制补丁工具会直接将完美匹配转换为补丁文件。相反，我们通过在每个方向上拓展匹配项来生成一组不相交的 “近似匹配项” ，但需要满足以下要求，前向拓展的每个后缀（以及后向拓展的每个前缀）至少匹配其字节的50%。这些近似匹配块能够大致对应于从源码中未修改区域派生的可执行代码块，而新文件中不属于近似匹配的区域将大致对应于源代码的修改处。这个拓展匹配项的处理过程就是为什么我们要忽略任何不比前一个匹配项 “更好” 的8个字节的匹配项。

现在补丁文件有三个部分构造而成：首先，一个控制文件包含添加和插入指令；然后，一个差异文件，包含近似匹配项中的字节差异；最后，一个额外文件，包含了非近似匹配项中的部分。每一个添加指令明确一个在旧文件中的偏移量以及一个长度，然后从旧文件中读取适量数量的字节，并添加到差异文件中。插入指令仅明确一个长度，即需要从额外文件中读取的字节数。虽然这三个文件加一起比原始目标文件大，但是控制文件和差异文件是可以被高度压缩的，特别是bzip2性能会非常好（可能是因为这两个文件的高度结构化性质）。

我们实现了这种方式的一个工具，名字叫做 “BSDiff” 。

3. 性能

为了评估BSDiff在可执行文件的两个版本间变化时的性能，我们使用了19对DEC UNIX Alpha二进制文件，这些文件使用Exediff的阐述，其工作特定于该平台【参考：BMM99】。在表1中，我们列出了这些二进制文件对的新版本的原始大小、新版本的压缩大小、当前最出色的免费二进制补丁工具XDelta【参考：Ma00】生成的补丁大小、应用广泛的商业工具.RTPatch【参考：Ps01】生成的补丁大小、由Exediff生成的补丁大小、以及由BSDiff生成的补丁大小。为了公平比较，我们使用了bzip2（块排序压缩器）压缩了BSDiff的补丁文件，而不是用gzip（Lempel-Zif压缩器）进行压缩。

除了两个版本的差异非常小的情况，即Apache的1.2.4->1.3.0的情况，没有任何一种差分方法优于直接压缩新文件。在Apache的1.3.0->1.3.1情况中，BSDiff略优于Exediff，其他场景非常明显：XDelta的补丁文件最大，Exediff的补丁文件最小，而BSDiff和.RTPatch分别排在第二小和第二大。考虑到19对用例，取由原始文件大小的平方根加权的算术平均值，我们发现平均下来bzip2提供2.8倍 压缩，XDelta提供5.2倍压缩，.RTPatch提供10.2倍压缩，Exediff提供13.7倍压缩，BSDiff提供11.6倍压缩。不包括Apache的1.2.4->1.3.0的升级（我们注意到这两个版本的源码共享部分少于一半，所以这么大的补丁包也就不足为奇了），XDelta提供了平均5.3倍的压缩，.RTPatch提供了11.6倍的压缩，Exediff提供了16.8倍压缩，BSDiff提供了13.0倍的压缩。

但是，比上述升级（功能升级）更重要的是安全升级。这是根本上不同的，因为源码的修改通常非常小—-通常只有一行。我们将i836平台的FreeBSD 的4.7-RELEASE和RELENG_4_7的快照进行比较。总共有97个修改的二进制文件，总大小为36397575个字节。其中bzip2能压缩到13566233字节（压缩率为2.7），XDelta产生的补丁文件为3288540字节（压缩率11.0），.RTPatch产生的补丁文件为749710字节（压缩率47.7），然后是BSDiff产生的补丁文件总共621277字节，压缩率为58.3。

4. 总结

我们发布了一种生成二进制补丁的算法，该算法应用于可执行文件的两个版本，始终比当前卓越的二进制补丁工具生成的补丁更小；当应用于安全更新的版本时，生成的二进制补丁非常小。

虽然它的性能与特定平台的工具的性能并不能匹配，但我们相信BSDiff可能是独立于平台的工具中的最佳性能的工具。

5. 致谢

作者衷心感谢Robert Muth搜索了四年前的备份以查找【引用：BMM99】中使用的语料库。

作者还要感谢Commonwealth Scholarship Commission的支持，该委员会正在资助他在牛津大学的学习。

6. 可用性

BSDiff在开源协议下从https://www.daemonology.net/bsdiff/提供使用。

引用

【BMM99】 B.S. Baker, U. Manber, and R. Muth, Compressing Differences of Executable Code, ACM SIGPLAN Workshop on Compiler Support for System Software, 1999.

【LS99】 N.S. Larsson, K. Sadakane, Faster Suffix Sorting, LU-CS-TR:99-214, Department of Computer Science, Lund University, 1999.

【Ma00】 J.P. MacDonald, File System Support for Delta Compression, Master’s Thesis, University of California at Berkeley, 2000.

【Ps01】 Pocket Soft Inc, .RTPatch, http://www.pocketsoft.com, 2001.

【Tr99】 A. Tridgell, Efficient Algorithms for Sorting and Synchronization, Ph.D. Thesis, The Australian National University, 1999.