Naı̈ve Differences of Executable CodeColin Percival
Computing Lab, Oxford University
colin.percival@comlab.ox.ac.uk

Abstract
The increasing frequency with which serious security
flaws are discovered and the increasing rapidity withwhich they are exploited have made it necessary for programs to be updated far more frequently than in the past.
While binary updates are generally far more convenient
than source code updates, the distribution of pointersthroughout executable files makes it much harder to produce compact patches.
In contrast to earlier work which relies upon knowledgeof the internal structure of a particular platform’s executable files, we describe a naı̈ve method which produces competitively small patches for any executablefiles.

1

Introduction

Historically, binary patches have been constructed using
two basic operations, copying and insertion. Using either substring matching or hashing techniques [Ma00],
portions of the new file are matched with portions of
the old file; those regions are copied, while the remaining “new” bytes are stored in the patch file and inserted. Patches generated in this manner can therefore beconsidered as programs consisting of two instructions,
COPY and INSERT.
Unfortunately, any source code modification will usuallycause changes throughout an executable file. Adding orremoving a small number of bytes of code or data willchange the relative position of blocks of code, adjusting the displacement of relative branches which jumpover the modified region; similarly, any data located after the modified region will have a different address,
causing data pointers to be modified throughout the file.
This causes patches generated with the traditional copyand-insert method to be much larger than necessary; aone-line source code patch in a 500kB executable could

translate into a 50kB patch file.
One solution to this problem relies upon knowledge ofthe internal structure of an executable file. If a pointer toaddress A in the old executable file changes to point ataddress B in the new executable file, it is very likely that
other pointers to address A will also change in the samemanner. As a result, by effectively disassembling theentire file and recording the first instance of each such
substitution, one can predict future substitutions, thereby
obviating the need to record them [BMM99]. However,the necessary disassembly means that any tools using
this approach will be entirely platform-dependent.

2BSDiff

In order to solve the ‘pointer problem’ in a portablemanner, we make two important observations: First, inthe regions of an executable file not directly affected bya modification, the differences will generally be quite
sparse. Not only will the modified addresses constitute only a small portion of the compiled code, but addresses are most likely to only change in their least significant one or two bytes. Second, data and code tends
to be moved around in blocks; consequently, localityof reference will lead to a large number of different(nearby) addresses being adjusted by the same amount.
These two observations lead to the important fact that
if the regions in two versions of an executable program
which correspond to the same lines of source code arematched against each other, the bytewise differences will
be mostly zero, and even when non-zero will take certain
values far more often than others — in short, the stringof bytewise differences will be highly compressible.
We now construct binary patches as follows. First,
we read the old file and perform some sort of indexing, either based on hashing [Tr99] or suffix sorting(e.g., [LS99]). Next, using this index, we pass throughthe new file and find a set of regions which match exactly
against regions of the old file. For reasons which will

become evident later, we only record regions which contain at least 8 bytes not matching the forward-extensionof the previous match (i.e., if the previous match is
new[x . . . x + k] = old[y . . . y + k], we look for a match
new[x0 . . . x0 + k 0 ] = old[y 0 . . . y 0 + k 0 ] with at least 8
distinct i such that new[x0 + i] 6= old[x0 + i + (y − x)]).
Conventional binary patch tools would translate thisset of perfect matches directly into a patch file. Instead, we generate a pairwise disjoint set of “approximate matches” by extending the matches in each direction, subject to the requirement that every suffix of theforward-extension (and every prefix of the backwardsextension) matches in at least 50% of its bytes. These
approximate matches will now roughly correspond toblocks of executable code derived from unmodified regions of source code, while the regions of the new filewhich are not part of an approximate match will roughly
correspond to modified lines of source code. This process of extending the matches is why we ignore any
matches which are not “better” than the previous matchby 8 bytes.
The patch file is then constructed of three parts: First, acontrol file containing ADD and INSERT instructions;second, a ‘difference’ file, containing the bytewise differences of the approximate matches; and third, an ‘extra’ file, containing the bytes which were not part of an
approximate match. Each ADD instruction specifies anoffset in the old file and a length; the appropriate numberof bytes are read from the old file and added to the same
number of bytes from the difference file. INSERT instructions merely specify a length; the specified numberof bytes is read from the extra file. While these three files
together are slightly larger than the original target file,the control and difference files are highly compressible;
in particular, bzip2 tends to perform remarkably well(probably due to the highly structured nature of these
two files).
We have implemented this method in a tool named‘BSDiff’.

3 Performance
To evaluate the performance of BSDiff when moving between two versions of an executable, we use 19 pairsof DEC UNIX Alpha binaries used in the exposition ofExediff, the working of which is specific to that platform [BMM99]. In Table 1 we list for each of thesepairs the original size of the new version, the com-pressed size of the new version, the size of patch produced by the currently pre-eminent free binary patchtool, Xdelta [Ma00], the size of patch produced by awidely used commercial tool, .RTPatch [Ps01], the sizeof patch produced by Exediff, and the size of patch produced by BSDiff. In the interest of a fair comparision,
we recompressed Exediff’s patches with bzip2 (a blocksorting compressor) rather than gzip (a Lempel-Zif compressor) where it was advantageous.
With the exception of two cases where the the difference was exceptionally small, the Apache 1.2.4 → 1.3.0
case, where none of the methods were superior to simply compressing the new binary, and the Apache 1.3.0 →1.3.1 case, where BSDiff was slightly superior to Exediff, there is a very clear pattern: XDelta gives the largest
patches, and Exediff gives the smallest patches, while
BSDiff and .RTPatch come in second smallest and second largest respectively. Considering all 19 pairs, andtaking the arithmetic mean weighted by the square rootof the original file size, we find that bzip2 gives 2.8-foldcompression, XDelta gives 5.2-fold compression, .RTPatch gives 10.2-fold compression, Exediff gives 13.7fold compresion, and BSDiff gives 11.6-fold compression on average. Excluding the Apache 1.2.4 → 1.3.0
upgrade (we note that those two versions share less thanhalf of their source code, so the large patches are not surprising), XDelta gives an average of 5.3-fold compression, .RTPatch gives an average of 11.6-fold compression, Exediff gives 16.8-fold compression, and BSDiff
gives 13.0-fold compression.
More important than the above consideration of upgrading between versions (“feature updates”), however, issecurity updates. These are fundamentally different,in that the source code modifications are typically extremely small — often as small as a single line. We takethe i386 build of FreeBSD 4.7-RELEASE and a snapshot of the RELENG 4 7 security branch as a corpus forcomparison here. In total, there are 97 modified binaries, with a total size of 36397575 bytes, which bzip2
can compress to 13566233 (a factor of 2.7). Xdelta produces patches totalling 3288540 bytes (a factor of 11.0),
and .RTPatch produces patches totalling 749710 bytes (afactor of 47.7), while BSDiff produces patches totalling
621277 bytes, a reduction by a factor of 58.3.

4 Conclusions
We have presented an algorithm for generating binary
patches which, applied to two versions of an executable

Program
alto: identical binaries
alto: gcc -O2 → gcc -O3
alto: changed reg. alloc.
alto: extra printf
agrep: 4.0 → 4.1
glimpse: 4.0 → 4.1
glimpseindex: 4.0 → 4.1
wgconvert: 4.0 → 4.1
agrep: 3.6 → 4.0
glimpse: 3.6 → 4.0glimpseindex: 3.6 → 4.0
netscape: 3.01 → 3.04
gimp: 0.99.19 → 1.00.00
iconx: 9.1 → 9.3
gcc: 2.8.0 → 2.8.1
rcc (lcc): 4.0 → 4.1
apache: 1.3.0 → 1.3.1
apache: 1.2.4 → 1.3.0
rcc (lcc): 3.2 → 3.6
Average Compression

Uncompressed
4669444669444505604669442621445242884423683686402621445242884423686250496
1646592
5488642899968
811008679936671744434176100%

Compressed
148024148024148024148024
114388222548
193883
1575361145022221781938922396661
64272523305670830122182618070817936915509035.5%

Xdelta
137
78390
97923
50613
14631
109252
98632
75230
80346
1774341449271100430463878139409549250889
111421
19192084456
19.4%.RTPatch
n/a
34755
34571
7524
5910
37951
25764
20712
58124
14054910551035175930187951195
140284265
48033
21686734098
9.8%

Exediff
155
20793
15845
6237
3531
23200
18473
15688
41554
10435079085
284608185962
38121
76072
303
40460
22723322019
7.3%

BSDiff
142
33633
23246
6299
6066
31720
21559
15806
53490
13021097782
30243128427844961
121371289
38278
18098133136
8.6%

Table 1: Sizes of updates produced by bzip2, Xdelta, .RTPatch, Exediff, and BSDiff
program, consistently generates patches considerably
smaller than those produced by the currently preeminent
binary patch tools; when applied to security updates, thepatches produced are extraordinarily compact.
While its performance does not quite match that of aplatform-specific tool, we believe that BSDiff probably
attains close to the best possible performance from aplatform-independent tool.

5Acknowledgements

The author would like to sincerely thank Robert Muth
for searching through four year old backups to find thecorpus used in [BMM99].
The author would also like to acknowledge support fromthe Commonwealth Scholarship Commission, which isfunding his studies at Oxford University.

6Availability

BSDiff is available under an open source license fromhttp://www.daemonology.net/bsdiff/
The files used for the performance comparisons above
are available from the author on request.

References[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 ofCalifornia 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.