A backdoor in xz [LWN.net]

A backdoor in xz

Posted Mar 30, 2024 21:19 UTC (Sat) by mbunkus (subscriber, #87248)
In reply to: A backdoor in xz by MarcB
Parent article: A backdoor in xz

Really? I always think of zstd as worse but orders of magnitude faster than xz, and worse but in-different-universes-kind-of-faster than bzip9 (all at default settings).

After reading another comment in this thread about using zstd for systemd's journal, I did a short test with a 1.6 GB journal export file (journalctl -o export …). The results were roughly:

| Type         | Size | Time  |
|--------------|------|-------|
| uncompressed | 1.6G | —     |
| gzip         | 78M  | 6.9s  |
| bzip2        | 58M  | 1m34s |
| zstd         | 62M  | 0.9s  |
| zstd -9      | 51M  | 3.9s  |
| xz           | 43M  | 4.5s  |

With the exception of zstd -9 all other compressors used their default settings.

(As stated in journalctl's man page, the "export" format is mostly text with a small amount of binary data for structure)

I'd be interested in situations where zstd compresses better than xz. Do you have some concrete numbers?

to post comments

A backdoor in xz

Posted Mar 31, 2024 0:29 UTC (Sun) by MarcB (subscriber, #101804) [Link] (3 responses)

At work, it was a large mail archive; essentially write-only - if we ever have to read it, something went wrong (legally speaking :-)

For linux-6.8.2.tar (1.4G), I get 137MiB for xc -9 and and 133MiB for zstd --ultra -22.

A backdoor in xz

Posted Mar 31, 2024 12:15 UTC (Sun) by mbunkus (subscriber, #87248) [Link] (2 responses)

Ooooh I hadn't been aware zstd has compression levels higher than 9. Good to know.

I did a couple more tests with this knowledge; here's the updated table:

| Type             | Size |     Time |
|------------------|-----:|---------:|
| uncompressed     | 1.6G |        — |
| gzip             |  78M |     6.9s |
| bzip2            |  58M |  1m34.1s |
| zstd             |  62M |     0.9s |
| zstd -9          |  51M |     3.9s |
| zstd -19         |  44M |  3m38.6s |
| zstd --ultra -22 |  41M | 21m43.1s |
| xz               |  43M |     4.5s |
| xz -9            |  43M |    15.6s |

So yes, you can get zstd down to below xz, at least with content that is mostly text, but now the duration completely flips upside down with xz looking good with 5s & zstd being so far out of this world that it isn't funny anymore.

Note, though, that xz is multi-threaded & zstd all the others don't seem to be: zstd only used a single core even on --ultra -22 whereas xz -9 used eight of my 32 cores. That being said, "zstd -19" uses 14.6 times the amount of time, "zstd --ultra -22" is at an unbelievable 83.5 times, making it still slower per core than "xz -9".

Does multi-core processing matter? Let's take build pipelines such as a build server for a distribution such as Debian as an example. If they want to achieve high utilization of their resources, they have to run stuff in parallel. This means that they can either assign a single core to each build VM & run a lot of build VMs in parallel, or they can assign multiple cores to each build VM & run fewer of them. In the latter case having a compression step that can only make use of a single core & that takes x times the time of another compressor with similar results in compression ratio, that yields rather low utilization.

Don't get me wrong; I really like zstd & the tradeoffs it makes. I use it as my default compressor in most day-to-day use cases for its impressive speed, especially interactively. But when file size is a concern (e.g. a lot of countries out there where internet traffic is mostly mobile & therefore both slow & expensive at the same time), xz pretty much always wins, no matter how you look at it. It's really no big surprise for me it has gained such wide-spread usage in the OSS world.

A backdoor in xz

Posted Mar 31, 2024 17:46 UTC (Sun) by andresfreund (subscriber, #69562) [Link] (1 responses)

> Note, though, that xz is multi-threaded & zstd all the others don't seem to be: zstd only used a single core even on --ultra -22 whereas xz -9 used eight of my 32 cores.

zstd -T0 will do the same.

A backdoor in xz

Posted Mar 31, 2024 18:12 UTC (Sun) by mbunkus (subscriber, #87248) [Link]

Indeed; I somehow totally missed that when glancing over zstd's options earlier today. Thanks for pointing that out.

Interestingly it does worse than "xz -T0" does wrt. how many cores it can effectively use. On my 32-core system with the same 1.6 GB input file "zstd --ultra -22 -T0" starts out using four cores but drops down to & stays at three cores after a handful of seconds. Therefore processing still takes 7m38s. Using a file or STDIN as input makes no difference. I guess zstd simply cannot segment the source as much as xz does.

Now "xz -T0" (which is the default in recent xz versions) also only uses eight cores on the same machine. Then again even with "-9" it is worlds faster both per core & in total than "zstd --ultra -22".

Then again, I'm really not trying to argue that xz is better than zstd, even though I probably sound like it. I just tried to answer the question why the OSS community has adopted xz as widely as it has, simply to satisfy my own curiosity. Also it's good to know the strengths & weaknesses of the various tools at our disposal.