Tar-codec: a fast and secure tar parser for the Rust ecosystem

Starting with 0.131, uv uses tar-codec to parse source distributions.

tar-codec is roughly twice as fast as our previous tar implementation (astral-tokio-tar) while also reducing uv's exposure to parser differentials and other security risks.

This blog post is about tar-codec itself: what it is, and what compelled us to build and optimize it. Read on if you, too, would like to know too much about tar archives.

Background: uv and tar #

What follows is an extended digression on the tar format. If all you care about is tar-codec, skip to it.

As a Python packaging tool, uv is in the business of resolving and installing Python packages. uv requests installable distributions from various sources (principally package indices like PyPI) and installs them on the user's behalf. This is how you go from uv add urllib3 to something you can actually import and use in your own Python codebase.

Installable distributions come in two primary forms:

"Built"2 distributions, also known as bdists or (most commonly) wheels, are essentially ZIP archives containing structured metadata and a fixed layout. Installers handle these by (more or less) plopping their contents into the right destination directory.

Many people think that bdist is short for "binary distribution," since wheels often contain compiled native code. This one common way to use wheels, but wheels can also contain pure Python. They're just another (and frequently better) way to package and install a distribution.

"Source" distributions, also known as sdists, are essentially tar archives. Unlike built distributions, a source distribution is essentially3 just a rollup of a source tree's state at release time.

By definition, source distributions execute arbitrary code at installation time. This makes them very powerful, but brittle (missing build tools or dependencies) and also a security risk (an attacker who controls the sdist can run code without the user needing to import anything).

Wheels are generally produced by running a build backend on a source distribution. Examples of that include uv's own uv_build, maturin, and flit.

Consequently, at a bare minimum, a Python package installer needs to understand at least two different archive formats: ZIP for wheels, and tar for sdists.

We've already talked a bit before about ZIPs on the Astral blog, and we'll certainly be talking about them again soon enough. But today we'll be focusing on tar.

It's fair to ask: why does uv want a new tar parser?

In short: security and performance, but mostly security.

Up until 0.13, uv used astral-tokio-tar for its tar operations, including both parsing and creation (in uv build). astral-tokio-tar is itself a fork of edera-dev/tokio-tar, which is a fork of vorot93/tokio-tar, which is a fork of dignifiedquire/async-tar, which is an async adaptation of composefs/tar-rs.

Around a year ago, we began to receive a number of security reports in astral-tokio-tar. This spurred us into looking more into our compression and archive handling stack, where we found additional problems.

Many of these boiled down to differentials that could cause a full parser desynchronization4: given an identical tarball, uv, pip, and other package tooling could be made to see different contents for the same package distribution. We found this particularly concerning in the context of archives that would appear "safe" to an index (like PyPI) but could extract dangerously when parsed by an installer like uv or pip.

This could the take the form of an "append" differential (where the attacker can append new files or new contents to existing files for a specific victim parser), or even a "full" differential (where the attacker can fully separate the extraction contents for each parser):

Click to enlargeActual sizeClose

Click to enlargeActual sizeClose

In the context of uv, the attacker model for these kinds of vulnerabilities is somewhat subtle: tar is only used for source distributions which, per above and unlike wheels, are assumed to execute arbitrary code at build time. Consequently, Python packaging mostly considers tar differentials to be a minor concern, since any attacker who would use them has a much more direct and official route towards writing arbitrary contents to disk (or executing arbitrary code).

Still, these findings unnerved us, and we embarked on a project to eliminate every differential we could find in astral-tokio-tar.

tar-codec grew directly out of that effort: we ultimately came to the conclusion that the tokio-tar family was too lenient by design, and that retrofitting constraints to it would be more troublesome and error-prone (including for existing non-Astral users of its APIs) than developing our own, ground-up implementation of tar. This would also give us the opportunity to systematically understand the tar format, and ensure that our assumptions around which aspects are (or aren't) differential risks hold true.

Similarly, we determined that our performance goals around tar parsing would be impossible to meet in the existing code base, at least not without refactors that would be tantamount to a rewrite.

It's important to understand that one does not simply build a tar parser from scratch. One must first understand how the tar format evolved into its current state5.

tar is an interesting format. Or more precisely, it's an interesting family of formats.

To summarize, there are three (and a half) variants that matter in practice:

There's UNIX V7 tar, which is the "original" tar. Very few tar implementations write this format by default anymore, but virtually all still read it. For example, Python's tarfile module will happily parse V7 tar files.

The UNIX V7 format is not widely used anymore because it comes with significant limitations on per-member file sizes (approximately 8 GiB) and path lengths (100 bytes).

Then there's the UStar/pax tar family6. This family is widely supported by tar implementations for both reading and writing. As far as tar goes, UStar and pax are what passes for a "gold standard" in terms of clarity of specification and documentation.

At this juncture, the main thing to know about the UStar/pax family is that it's derived from the UNIX V7 format, but with certain restrictions lifted:

GNU tar is documented in the GNU tar manual, but is not standardized per se. The source code of GNU tar (the CLI) is the de facto standard for GNU tar.

Like UStar/pax, GNU tar is derived from UNIX V7 tar. It's also derived from an early draft of UStar.

Also like pax, GNU tar makes file sizes and path/link lengths (effectively) unlimited. It does so in a completely different and much funnier way than pax does.

Click to enlargeActual sizeClose

If you've ever written a parser for a binary format before, then you probably have a preconception for what a binary format should look like. To first, second, and third approximations, binary formats tend to look something like this:

Click to enlargeActual sizeClose

Within this, too, certain idioms appear: binary formats typically use some form of TLV encoding, use different magics to signal different endiannesses, &c.

The tar format does not look like this, regardless of the variant. tar is fundamentally a block format, owing to its origins as a tape archival format8.

As a block format, a tar archive is comprised of one or more fixed-length blocks. There is no file-level header; instead, many of its blocks are headers, while other blocks contain actual member9 data:

Click to enlargeActual sizeClose

In all flavors of tar, all blocks (including the header blocks) are always 512 bytes. Each header block declares metadata for the member that follows it. This includes important things like the size of the member and its filepath.

Member contents don't always fit cleanly into multiples of 512 bytes, so a tar that wants to encode a file member of N bytes will allocate ceil(N / 512) blocks and pad out the remainder of the last block. This doesn't affect extraction, since the reader knows (via the header block) exactly how many bytes out of the allocated space are actual file content.

Conventionally, the padding or "holes" in a tar archive are filled with NUL bytes. However, nothing stops a tar producer from filling them with uninitialized memory, or lines from the Bee Movie, or anything else. A recurring theme with tar (of all flavors) is that it has no opinions about what goes in the holes of the format. This malleability makes it very prone to parser differentials, since it gives the attacker ample space to place surprising data.

tar's block design also makes it relatively space-inefficient10 by modern standards. For example, a 513-byte file occupies an absolute minimum of 1,536 bytes when encoded as a tar member: one 512-byte block for the header, and two blocks for the content (one of which has only 1 "real" byte, followed by 511 bytes of padding). Similarly, a tar archive containing 1000 one-byte files requires a minimum of 1025 KiB of encoding (1 MiB for the headers and contents, and then 1 KiB for the trailing zero blocks).

So far, this all sounds pretty sane. It's not a "normal" file format by modern standards, but there's a simple state machine one could write to formalize a parse for the tar example above:

Click to enlargeActual sizeClose

Unfortunately, it's not that simple. The state machine above is accurate for a V7 tar, but not for anything else in the tar format family.

To understand why, we have to remember V7 tar's limitations. All of those limitations come down to the C structure that represents a V7 member header, which we've annotated here:

struct v7_header { // The member's path. Observe that this can be no more than 100 bytes; // NUL termination isn't required, since it's a fixed-size field. char name[100];

// The member's mode, as an octal string. // Note that only the first 4 octal digits (12 bits) have well-defined semantics in pax. char mode[8];

// The member's owner's UID and GID, as octal strings. char uid[8]; char gid[8];

// The size of the member, as an octal string. // V7 treats this as NUL-terminated, so the largest // interoperable value in it is 77777777777\0. char size[12];

// The member's mtime, as an octal string. char mtime[12];

// A checksum for the member header itself. char chksum[8];

// '\0' for a regular file, '1' for a hard link, // and '2' for a symbolic link. char linkflag;

// When linkflag is '1' or '2', this is the link's destination. // Like name this is limited to 100 bytes. char linkname[100];

// 255 bytes of the header are unused. char pad[255]; };

Three big limitations stand out, and each member of the tar family tries to solve them in various different ways:

Let's see how each family works around these.

UStar's half-solution is to preserve the existing physical header block, while impressing some of its fields and padding into new roles.

struct ustar_header { // Unchanged. char name[100]; char mode[8]; char uid[8]; char gid[8]; char size[12]; char mtime[12]; char checksum[8];

// linkflag is now typeflag, and encodes, inter alia, // '5' for a directory. char typeflag[1];

// Unchanged. char linkname[100];

// "ustar\0" char magic[6];

// "00" char version[2];

// The user and group names for the member. char uname[32]; char gname[32];

// For chardev/blockdev members, the device's major and minor numbers. char devmajor[8]; char devminor[8];

// If nonempty, a prefix to prepend to name (joined by a /). char prefix[155];

// 12 remaining bytes of the header are unused. char pad[12]; };

This partially lifts the member name restriction (by raising it to 255 bytes), but retains the file size and linkn