Slashdot Mirror
Delta Compression for Linux Security Patches?
cperciva asks: "For people without fast internet connections, it is often impractical to download large security patches. In order to avoid to reduce patch sizes, some operating systems -- starting with FreeBSD over a year ago, and recently followed by Mac OS X and Windows XP SP2 -- have started to use delta compression (also known as binary diffs, which constitutes a portion of my doctoral thesis), and can often reduce patch sizes by over a factor of 50. In light of the obvious benefits, I have to ask: When will Linux vendors follow suit?"
Certainly for your primary commercial auto-updated Linux distributions it does, but for anything else it usually doesn't. What makes more sense (because it's easier) is breaking up media and programs, and distributing them separately so you don't have to update one when you update the other. Some projects do this already, and even package their sources this way.
Personally I'd prefer to see binary distributions move to a model of using something like cvs, so you can just do a cvs up (or equivalent) and update everything. Some files would have to be marked to always be overwritten, while config files would be merged. This solves both your differential update problem (if the right system is used - I'm thinking that's pretty much not CVS but I don't know if there's a way to make it do all of that - CVS doesn't handle binaries amazingly intelligently from what I understand) and your updates in general. Plus, you can use it both for source and binary updates.
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
... their biggest customers start using dialup.
You mean to tell me that beast I downloaded was just a diff? Jesus H. Christ!
As soon as binary diffs get hacked into RPM then it might happen. binary diffs of one rpm to another later version wont really work as binary diffs are only small when they are produced on uncompressed, unecrypted data. The real issue is that linux doesnt really need binary diffs. Linux distros already have fine grain packages ( lots of little packegs not a few bigs ones). Security updates usally just require a one or very few packegs to be updated. Binary diffs only really make sense when you have huge packages that require a whole new package for upgrade. I bet the average RPM is about the same size as the minium binary diff from MS.
The folks at mindvision made an installer/installer creation tool that allowed one to scan two different sets of files and directories to find differences between them (binary differences) and it would just package up those differences in the installer archive. In fact you could use it to diff and package delta between several versions at once. When the user ran the installer (really and updater) it would apply the binary patch to the file set as needed.
I was using this tool over 7 years ago now on Mac OS so I don't see what is so new about this concept... but I am glad is looks like it starting to be used more.
Now with broadband being so popular, and still on the rise, is this really an issue?
Yes, it is. I just switced to broadband less than two months ago. A lot of my friends are still on dialup. Also, do not forget rural areas which do not have access to broadband. You would be surprised how many people still have dialup, I believe the number of broadband users just recently surpassed the number of dialup users. This means, obviously, that nearly half of all internet users are still on dialup.
Linux makes it very easy to install new packages and upgrade packages from sources father away from the vendor. If a vendor tried to release a patch using delta versioning, it could totally wreck a system. Since neither RPM nor DPKG are designed to handle checking md5sum hashs against each file, and making sure the patch can be installed safely, it will have to wait until this feature is incomporaited into either system.
This signature was left intentionally blank.
SUSE already does this.
RPM in general, however, doesn't nicely support this feature. Either RPM needs to be extended/modified, or a new format needs to be made. While I favor a new format for many reasons other than this, modifying RPM is probably the best solution in order to provide backwards compatibility.
On that topic, why does almost everybody distribute source code as gzipped tars instead of bzip2'ed tars (just about everybody that does use bzip2 also distributed gzips)? Sure, in the beginning gzip made more sense for people on slow machines, but nowadays the difference in the time it takes to decompress is trivial, whereas the compression benefits of bzip2 on text are phenomenal in my experience.
delta based patch distribution on linux platform is quite easy. Just use RSYNC to sync application file to the source. I have used this technique of patching (i.e. RSYNC), to provide updates/patches to a in-house built application. Work very nicely.
Consensus is good, but informed dictatorship is better
If the update is just a patch to the source, there's sometimes a minor revision made and an updated gentoo ebuild file and source code patch added to the portage tree, which is of course done via rsync. All in all, it's decently efficient. This mostly(I think) happens with unstable package versions, where a security update may make it into portage before the official project bumps their release, but that's not the case with stable stuff.
I think for basic systems, compile time complaints are slightly exaggerated. My -original- celeron 450 isn't shabby at all at compiling most of the more basic system packages and server apps. Even glibc and gcc build with relative ease, and when I set up distcc amongst my three systems, it became even less of a hassle. Even without distcc, the time to clear out 50 packages of updates on a mail server is surprisingly low on a low-powered system.
Please help metamoderate.
Ok before I get berated by the karma (whoring) police I do realize these are not binary diffs. But, seriously, linux has been using diff's as a way to save bandwidth before Windows even offered 'updates'. Another example of Windows 'innovation' I guess.
Yes, I see how it is neat that there is a binary version of this process with Windows but linux is primarily a source based operating system. It is that way becuase the software is designed to be compiled for a variety of systems and setups and work with all of them.
I do understand the authors question though, but it really should be reworded. Linux is not a OS in the sense that Windows is an OS. He should perhaps be more correctly asking when one of the 'binary' distributions of Linux (or of a Linux 'based' OS to be exact) will plan on offering this. Binary packages are really only offered on a per distribution basis with the binaries not being very compatible between distro's and systems (although some basic compatibility is generally there). As to that question who knows and who cares I use Gentoo, and after trying almost every one of the binary distro's
"Take that Lisa's beliefs!" - Homer Simpson
Delta compression requires the vendor to create a delta for each older version that you can upgrade from. So if a package has had ten updates, the next yupdate will need to have eleven deltas. I don't think so. Unless you want to do something like Windows Update where an agent scans your binaries and compares the difference with the update and then downloads individual files ... but that's a lot more complicated and isn't justified by the bandwidth savings.
SUSE already does this.
Nope. SuSE's "patches" are created by packaging all the files which are affected by a security fix; those files are packaged intact, without any delta compression.
Now, this is certainly a step forward from the common (eg, Debian, RedHat) approach of having people download a complete new package, including copies of files which haven't changed at all, but SuSE's approach is still suboptimal by more than an order of magnitude.
Tarsnap: Online backups for the truly paranoid
Um, I don't know about you, but I don't want to recompile for a security patch. I didn't even compile my system in the first place, it's just binaries.
...toggle their diffs in from the front panel.
Sheesh, evil *and* a jerk. -- Jade
XDelta3 recently reached its first public release.
http://xdelta.org/xdelta3.html
XDelta3 is a library which is designed to foster exactly this kind of functionality. If distrobutions integrate the xdelta functionality into their package management framework we would be well on our way to what the poster is looking for.
Used to do this back in ye olde DOS shareware days. I think RTPatch was the most common of the commercial ones.
Opportunity knocks. Karma hunts you down.
But if you're posting to Slashdot on a Friday night, you probably don't have a friend's house to go over to.
It works beautifully but I can't help but think it is a waste of bandwidth.
What makes you think you need to take a server out of production while code compiles on it? I never have.
Firstly, linux programs tend to be smaller than windows programs (do one thing, and do it well). Even a huge beast like tetex is 'only' 14.4MB -- compare to SP2... This has reduced the demand for delta compression.
Secondly, in the windows world people release rarely. However, the opposite is true in the linux world -- projects with daily releases are not unheard of, and weekly releases are fairly common. This means enumerating patches (v 3.4 -> v. 3.7) is infeasible in Linux where it is feasible in Windows.
More sophisticated algorithms than delta checksums do exist (as I guess you know if your thesis is on them) -- rolling checksums have been used in several projects I know of. However, there is a widespread rumour that these techniques are patented. I have never seen any evidence, but it puts a damper on any implementations.
There is a semi-vapourware project implementing all of this (part of the apache project IIRC). However the project fizzled away several years ago.
http://www.daemonology.net/bsdiff/
bsdiff and bspatch are tools for building and applying patches to binary files. By using suffix sorting (specifically, Larsson and Sadakane's qsufsort) and taking advantage of how executable files change, bsdiff routinely produces binary patches 50-80% smaller than those produced by Xdelta, and 15% smaller than those produced by
http://sourceforge.net/projects/diffball
A general delta compression/differencing suite for any platform that supports autoconf/automake, written in c, w/ builtin support for reading,writing, converting between multiple file formats, and an easy framework to drop in new algorithms.
If I understand correctly, a binary diff goes a few steps further than a patch. It stores insertions and deletions while a typical patch (like IPS) only stores replacements, which is optimal for files patched in a hex editor and even most database files but not for recompiled files where everything can change in location.
While it's more difficult to set up a system with Gentoo than Windows 2000, it's easier to maintain.
This is probably because of portage. Precompiled packages coming from all differnet sources can be a bitch to maintain. Mandrake is my example for this if you ever want to update a package they don't have RPMs for. And as for compile time, I'd rather let the computer sit for a hour or two overnight compiling a huge package than having to deal with the dependencies myself.
Especially since the license of bsdiff is not even close to a BSD license (don't let the name of BSD Protection License fool you). Unless the license is changed to something like BSD, BSDiff is not going to be implemented anywhere except in closed source software. Debian cannot even package this software becauses it is non-free.
I guess the bottom line is if you want to have something accepted in open source *and* in propriatary software, you want to license under BSD. You want to cater to one group (closed source in this case), you will lose the other.
What's so new about it? I remember working with InstallShield, RTPatch, and others, way back in the Windows 3.11 days... New? <yawn>
Enter "deltup" a tool that looks at to tarrballs and gives you a diff between the 2 that you can use to "transform the old tarball to a exact copy of the new tarball", it even preserves MD5 checksums compatibility. Now some enterprising gentoo user create a "dynamic deltup server" that automates the creation of these delta files, and people can reuse the delta files that other people used.
Using this technique in combination with gentoo portage people can reduce there traffic with on average 75%.
Have a look at the following URL's for more information:
http://forums.gentoo.org/viewtopic.php?t=215262
m e.html
http://linux01.gwdg.de/~nlissne/deltup-status.ati
Rigolo
Here's a snippet from a patch description used by the online update, to give you some idea of what it does:
This signature is not in the public domain.
Apparently, most distributions have you download the entire package for each update, although there are efforts underway to break up sections a bit more (if I'm wrong, I apologize - I use BSD).
It sounds like what's really needed is to build packages of just the updated files. The install manifest would just specify the files in the archive, so there shouldn't be any complaints about missing files. Or does that show my ignorance?
Actually, if you wanted a more general scheme, the update server would build packages on the fly. The updater would send a list of files in a package to the server, which would return a set of files that need updating. You could use this to upgrade any system, regardless of distribution. You would just have to update the database for whatever to show that it was at the latest version.
Yes, this would take up a lot more CPU time, and be pretty slow on response time, but the savings in bandwidth should be worth it. All the time the servers were waiting for the network card could be used compressing files.
Java: the bastard demon spawn of C++ and Ada
Sure it is always nice to have faster downloads. But is it worth the extra work involved in setting this up both at the distribution point and on the client side?
I am not being rethorical. I am just wondering.
I'm quite sure Novell has been doing it in the past. At least with the older versions of Netware (3.x and 4.x versions).
You had the whole Novell NOS + couple of services in, lets say 100Mb or so, and you needed to update tons of NLM's. Just needed to download a quite small patch file (over a POTS line) that usually could fit on a floppy or so) and then it updated the loose NLM's.
Nothing new I guess..
As somebody pointed out before in this article, there is rsync which minimizes transmitted data using some xdelta-like algorithm. This is not really new, and some sites offer anonymous rsync downloads for exact this reason.
(Rumours were that some people actually use rsync in the following way to get the latest Debian ISOs from a collection of old, already downlod packages: They cat'ed all their packages together to one huge binary file and then ran rsync against the remote ISO image and that local file. Since most data was already in that file, only transmission of a few megabytes of new data and some data arranging had to happen....)
Here I uttered a few quick&dirty thoughts (which most certainly somebody else has had before, as usual) on how rsync could help in mass patching, don't know if they are worth reading for you... .)
Not all diffs are alike. The simplest diffs are literal - "find string of bytes to replace and replace them with newbytes."
Back in 1985, Apple did something a bit more sophisticated for their System Update 2.0 patch.
Their binary files were structured. The particular structure was called a "resource fork" and had a collection of hundreds or thousands of usually-tiny "resources" which could be individually modified. As a made-up example, replace String ID 50 in the file "System" to "Version 2.0" where it previously was "Version 1.0" or replace one linked-in graphic with another.
The patch program updated, deleted, and added individual resources.
This is important for historical reasons:
If Microsoft or anyone else gets the funny idea to patent "replacing parts of a structured file in an update mechanism" as a broad-scope patent and the USPTO grants the patent [which they probably will, out of ignorance], the patent will need to be challenged and narrowed significantly.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
The method I came up with was to use essentially the rsync algorithm, but I reversed it so that the computationally expensive parts were performed on the client side. The results of each computation were stored on the server side as a "patch" so that the computation was performed only once. This provided a patch system that was dynamic but without generating large server load.
The advantages are:
1. Patches are generated dynamically so the files can be in any state (truncated, too big, filled with garbage, missing enitirely, etc).
2. The heavy computation is performed on the client side so that patch generation does not drive up server load.
3. Computed patches are stored and reused, so a database of patches it quickly built up.
4. Patches are efficient (based on binary diff).
A detailed example follows; knowledge of rsync is required for understanding.
For example, let's suppose you are releasing a new content upgrade. A particular file's signature has changed from F4A3 to 26B1. (For brevity I am using a 16-bit signature, in practice it is much much larger.) When the first client connects to the patch server it receives the updated list of file signatures. The client notices that the file is now old so it requests a patch for F4A3->26B1. The patch does not exist yet, so the reverse-rsync algorithm activates and the client calculates the F4A3->26B1 patch. When that patch has been generated it is returned to the patch server and all future clients can just download the patch and skip the reverse-rsync. After applying a patch, the result is checked to make sure that you actually ended up with 26B1. If you did not, extra rounds of patching are performed.
Some Notes: These extra rounds are consequences of rsync and a security check as well to prevent bad patches from being uploaded to the server. And, normally the release maintainer would "pre-seed" the patch server by patching a clean current version to the new version just before release.