A fast and secure tar parser for the Rust ecosystem
78 points by yossarian
78 points by yossarian
This is a very interesting article with great explanations and diagrams. I think the state machine diagrams really help make sense of what's going on. Thanks for sharing!
As an only tangentially related point, the post mentions:
Extracting an archive (of any format) onto disk is its own can of worms, with its own differential risks18. Another one of our early observations is that every archive implementation tends to have its own extract-to-disk implementation, with its own edge cases.
We built archive-trait to address that. archive-trait exposes Archive and ArchiveBuilder traits (along with associated types and machinery) that allow any format to expose uniform APIs for reading and creating archives. We then built archive-trait's own filesystem extraction on top of cap-std, giving us the ability to "anchor" extraction into a single directory and avoid a large class of link and path traversal footguns.
This reminds me of an exploit that I learned about that I found quite clever. It was used to get the ability to add unauthorized 3rd party apps to a Kindle (the one I'm thinking of is the Kindle Touch but maybe applied to others as well). My recollection of it off the top of my head is as follows: system updates came packaged as a compressed tar file. The system would untar the update, then find a signature inside of the archive to decide if it was an approved software update based off of the signature matching a public key that was stored in something like /etc/authorized_keys. If the public key matched, then it would run the update; otherwise, it would delete it. Well, turns out there was a bug in the untar program, and you could craft a malicious tar file that had path (along the lines of) ../../../etc/authorized_keys, and when this was untarred it would clobber the original list of public keys, thus allowing a provided update payload to run.
It's a somewhat different class of vulnerability in tar files than the OP was discussing, but I guess it just goes to show that there's a lot that goes into these things to keep them secure.
Yeah, the layer beneath archive handling (of taking abstract "members" and turning them into contents on disk) is in a sense way harder: every OS and FS applies its own semantics/quirks that make it impossible to say with confidence that an archive, even an obvious one, will extract the same way on different hosts.
(The exception to this would maybe be an archive containing only printable ASCII paths, all relative, with extremely conservative limits on path lengths. But too many real-world uses of archives reasonably violate these constraints.)
Hm very interesting. This seems like a tight rope to walk, since compatibility and avoiding parser differentials are fundamentally opposed (i.e. more features supported is more potential differences).
Without knowing much about Python packaging, I wonder if there are something like 100K or 500K source tarballs in PyPI? If so, I wonder what the "minimum tar" necessary to parse those is. It seems like potentially a more bounded problem - parse the things that are in PyPI.
And then maybe reject input at PyPI upload time (although I understand why this is hard in a social sense)
I asked Gemini and practically speaking the "writers" include GNU tar, OS X tar which is more like BSD, Python's tarfile module, and Go's tar module. All of them use SOME extensions, e.g. for long filenames, but I also wonder if the union of all features they emit is meaningfully smaller than "all tar extensions" !
Also reminding myself that this post also has a bunch of background on the various tar format extensions, in the context of OCI: https://www.cyphar.com/blog/post/20190121-ociv2-images-i-tar/
I also wonder if tar files that appear in practice in Docker/OCI are of different dialects than PyPI, or it's all basically the same set of tools creating them.
I wonder if there are something like 100K or 500K source tarballs in PyPI?
The homepage advertises 10 million releases across a million projects, and most of those would have an sdist: according to https://dev.to/munimv2/does-pypis-long-tail-still-ship-wheels-a-full-head-vs-tail-census-of-6000-latest-releases-1pf6, out of the top 3000 projects 95% have an sdist and out of a random sample of 2850, 91% had an sdist, the historical trend would likely have been more sdist and sdist-only distributions. So probably 8 or 9 million source tarballs.
Turns out PyPI puts package metadata on BigQuery. 9.8m .tar.gz files. Mean of 1.2MB, so, 12TB of traffic if you just wanted to fetch and parse all of them (probably half that if you cap at 99%ile size). I wouldn't do that myself but OpenAI could certainly do so without blinking.
| ext | n_files | total_tb | median_bytes | mean_bytes | p99_bytes |
|---|---|---|---|---|---|
| .tar.gz | 9862381 | 11.99 | 32495 | 1216159.0 | 28042670 |
| .zip | 110489 | 0.11 | 42320 | 966581.0 | 19725143 |
| .tar.bz2 | 3851 | 0.0 | 50655 | 641260.0 | 9156228 |
| .tgz | 226 | 0.0 | 57863 | 513786.0 | 6710606 |
| null | 49 | 0.0 | 68406 | 580108.0 | 12080860 |
Ah this is interesting, and it's along the lines of what I was thinking.
I've worked on "J8 Notation" intermittently over the last few years -- basically I would like to make something largely compatible with CSV/TSV and HTML5/XML, but as well-specified as JSON [1]
So I was hoping to do some data-driven experiments (most likely aided by LLMs), to see what the frontier between "compatible" and "well-specified" is ...
I would also add "declarative" -- I like that this tar-codec work seems to be based on explicit state machines. I hope to find time to look into it more.
So basically I am curious what kind of metalanguage can express formats like CSV TSV HTML5 XML, while also being compatible with say 99.999% of some corpus that we can argue to be representative.
And you can ask the same question of tar -- PyPI and OCI would be great test corpora. So basically I would like A fast and secure tar parser for the Rust ecosystem -> A fast and secure tar parser for all ecosystems :-) (C and C++, Python, Ruby, etc.)
As mentioned in the article, these problems are NOT related to memory safety, so the same benefit would extend to C and C++, and all languages that use them.
(Aside: I think many people have PyPI mirrors, perhaps of all 12 TB? For those with fewer computing resources, maybe you could get that data with HTTP range requests -- maybe that depends on gzip --rsyncable or some such thing ...)
[1] JSON only has a couple holes in its spec, which have been addressed by follow-on RFCs I believe. Many of the "JSON is a minefield" problems are particular to the representation of values within a programming language, which is an inherent issue -- not part of the JSON spec.
Maybe Kaitai Struct (6 comments)
Hm yeah that thread has a good wiki-like repo: https://github.com/dloss/binary-parsing
A list of generic tools for parsing binary data structures, such as file formats, network protocols or bitstreams
I remember looking at Hammer many years ago.
I probably shouldn't have said "declarative" -- what I mean more is probably "the most powerful language which can be inverted with respect to push-pull", e.g. comparing the styles of Go HTTP parsing (pull, with goroutines) and nginx / node.js (push, event driven)
And I would mix declarative with this powerful language. e.g. Oils is regular languages + a bunch of procedural recursive-descent style code (+ algebraic data types). The procedural code is "irreducible" -- it can't be purely declarative.
But I would like to invert it, and I see that problem in many other places too. In that sense, the algorithm is de-coupled more from the code gen.
I wonder, what are the origins of octal strings being used instead of proper integers in a bunch of Old Unix Things?
The PDP family had word sizes of 18, 12, and 36 bits, so octal notation was very common. The PDP-11 was a rare 16-bit architecture but was full of octal nonetheless (e.g. the front panel switches used octal grouping, assembly immédiates defaulted to octal, addresses and device registers were in octal, …) so octal would have been quite natural to unix developers. In fact the original binary data formatter was od, octal dump, and is so old it was reportedly why the bourne shell uses do…done rather than do…od.
And the fields in PDP-11 machine code instructions for things like register numbers and addressing modes are aligned to octal digits, so it isn’t too hard to read an octal dump without a disassembler. (In arm32 they are aligned to hex digits.)
s/parser differentials/parser differences/g:
Claude doesn't know how English works.
"Parser differential" is a term of art for parsers interpreting the same input differently, especially when that causes security vulnerabilities. It was originally coined 15 years ago as "parse tree differential attack" in The Halting Problems of Network Stack Insecurity (Sassaman, Patterson, Bratus, Shubina; 2011) to label an existing method most famously employed in PKI Layer Cake (Kaminsky, Patterson, Sassaman; 2010).