Reproducible Builds: The Sources of Nondeterminism in Compiler Output

A reproducible build is one where the same source, built with the same toolchain and the same declared inputs, produces a bit-identical artifact. The definition sounds like a property compilers either have or lack. In practice it is a property of the entire build system, and the failures are almost never in the compiler proper. They are in the parts of the environment that nobody declared as an input: the clock, the working directory, the order in which a filesystem returns directory entries, the identity of the user who ran the build, and the concurrency schedule of the build tool.

The value of achieving it is direct. If a build is reproducible, any party can rebuild from source and compare the artifact they produced against the one shipped, which converts a signature that says “someone with this key produced these bytes” into a claim that can be checked against “these bytes are the ones this source produces”. That is the property that makes independent verification possible at all, and it is what the relationship in provenance attestation and digest binding is trying to assert.

The taxonomy of leaks

Every nondeterminism source falls into one of four buckets: time, environment, ordering, and state.

Time. The most common leak is the build timestamp embedded in the artifact. __DATE__ and __TIME__ in C, #define of a build date in a generated header, an ISO timestamp in a package manifest produced by a packaging tool, and the mtime stored in every tar or zip member. Debian’s reproducible builds project addressed this by introducing a convention, later standardized as SOURCE_DATE_EPOCH: a variable holding a POSIX timestamp that build tools should use in place of the current time, and that packagers should set to the timestamp of the newest source change. Tools that honor it clamp any embedded timestamp to that value, and archive writers set member mtimes from it.

The convention is only half the fix; the other half is that every tool in the pipeline must honor it. A compiler that substitutes SOURCE_DATE_EPOCH for __DATE__ and a linker that writes a build id derived from the current time will still produce different outputs, and finding the last non-honoring tool in a chain of twenty is most of the work of making a project reproducible.

Environment. The absolute path of the build directory ends up in debug information, in assertion messages, and in __FILE__ expansions. A build in /home/alice/project and a build in /build/ci/project produce objects whose .debug_line sections differ, and the difference propagates into the linked binary. Prefix-map options on compilers exist to remap the build root to a fixed string, and the fix is to remap consistently, including for any generated assembler or generated code.

Environment variables leak in subtler ways. LC_ALL and related locale settings change sort order in tools that sort text. PYTHONHASHSEED changes the iteration order of Python sets and dicts built from strings, which changes generated code. Umask changes permission bits. The hostname changes embedded identifiers. The user and group name are encoded in tar headers unless forced to numeric zero. None of these are compiler behavior, all of them reach the output.

Ordering. Filesystem iteration order is not sorted and is not stable across filesystems. A build script that globs a directory and concatenates the results in the order returned produces a different artifact on a different machine. The same applies to parallel build tools that emit output in completion order rather than dependency order, and to any link step that processes archives in the order they appear on the command line when that order came from a wildcard. The fix is to sort explicitly at every point where a set is turned into a sequence, and the failure is easy to miss because it does not reproduce on the machine where it was written.

State. Parallelism, caching, and incremental compilation introduce results that depend on scheduling. A compiler that allocates assembler symbol names from a global counter, in a build where translation units are compiled in parallel, produces different symbol suffixes depending on which unit got there first. Archives that embed an index of members in insertion order differ when the order of insertion differs. Build caches keyed on mtime rather than content produce different artifacts for the same source.

There is also a state leak peculiar to languages with randomized hashing or randomized initialization order. Compilers that support a random seed option expose a knob, and builds that leave it unset get a different seed each time; several toolchains have addressed this by defaulting to a deterministic seed unless explicitly told otherwise.

What normalization looks like

A build that has been made reproducible typically contains a normalization step after the artifact is produced, which rewrites the parts of the file format that carry environmental residue. For an ELF binary the relevant pieces are the .comment section, the build-id, the debug paths, and any embedded timestamps. For an archive, the member order, the mtimes, the uid and gid, and the mode bits.

# Sorted, deterministic archive: fixed mtime, numeric owners, no recursion surprises.
find . -type f -name '*.py' -print0 | LC_ALL=C sort -z | \
  tar --null --files-from=- --format=gnu \
      --sort=name --mtime="@${SOURCE_DATE_EPOCH}" \
      --owner=0 --group=0 --numeric-owner \
      --pax-option=exthdr.name=%d/PaxHeaders/%f,delete=atime,delete=ctime \
      -cf - | gzip -n > src.tar.gz
# gzip -n omits the filename and mtime that gzip would otherwise store.

Each flag in that command removes one leak: --sort=name fixes member order, --mtime fixes timestamps, the numeric owner flags fix identity, the pax option drops extended attributes that carry access times, and -n prevents gzip from storing the original name and timestamp in its header. A pipeline missing any of these produces an archive that differs between two runs even when the file contents are identical, and each omission is a different diff to diagnose.

The normalizations that cannot be done after the fact are the ones inside compiled output, because by then the information is baked into instruction operands and relocations. Those have to be fixed at the source of variation: remapped paths, fixed seeds, and deterministic symbol naming in the compiler.

The measurement problem

Reproducibility is a claim about all builds, not about two. A single successful pair of matching builds establishes that the pipeline can be deterministic on that pair of hosts; it does not establish that a build on a differently configured host will match. The practical way to strengthen the claim is diversity: rebuild on a different OS version, a different CPU architecture, a different filesystem, and a different time zone, and require the digest to match. The variations that break the result identify which leaks remain.

The second measurement problem is the toolchain itself. A reproducible build normally fixes the compiler version, because different compiler versions legitimately produce different output. That means the compiler becomes an input whose provenance matters, and a build that pins a compiler binary without recording which compiler binary is reproducible only relative to an unverified assumption. Bootstrapping a toolchain reproducibly is a recursive problem with a known solution shape: a small bootstrap binary, then a chain of stages that must converge, which Debian and several other distributions have documented.

Where reproducibility does not help

Reproducibility is orthogonal to correctness and to safety. Two builds matching proves that the source produces the artifact; it says nothing about whether the source is the source the maintainer intended to publish, whether a dependency was compromised, or whether the artifact behaves. An attacker who modifies the source before the build gets a perfectly reproducible build of malicious code, and signatures over that artifact will verify.

Nor does it help when the artifact must contain a genuinely varying element, such as a cryptographic key generated at build time or a device-specific configuration. The usual resolution is to exclude such elements from the artifact or to generate them at first run, and a build that cannot is honestly non-reproducible; claiming otherwise by pinning a fake value is a correctness bug.

What reproducibility buys is a sharp reduction in the trust placed in the builder. Combined with a signed attestation it lets a consumer who distrusts the build platform verify independently, and combined with hermetic isolation it makes the environment part of the declared input rather than an ambient variable. The isolation half of that pair is covered in hermetic build isolation and two-party verification; the leak taxonomy here is what that isolation has to control for.