Status update from the Reproducible Builds project

Reproducible builds are extremely useful. There are more benefits. For example, suppose you have a build server compiling software packages. If your builds are not reproducible and you want to debug a core dump, but you have no debug information, you are out of luck (well, you could dive into the assembly code, but it's inconvenient). If you want to keep debug information, you need to store them for every single build (what a waste of storage...) because the binary for each build is different. Not so with reproducible builds, you could simply check out the old version and compile it with debug information!

Not just Linux; FreeBSD and NetBSD have been along the ride for a while: https://reproducible-builds.org/who/

I've filed this as https://bugs.debian.org/869557 and will work on this soon.

Why do you care about the order of packages in Packages?

What does "build reproducibly" even mean in this context?

Not yet. Could you file a bug report?

Guix and Nix are input-reproducible. Given the same input description (input being the source files and any dependencies) an output comes out. Builds are then looked up in a build cache based on the hash of al lathe combined inputs. However. The _output_ of Nix artifacts are not reproducible. Running the same input twice will yield a different result.

Nix does some tricks to improve output reproducibility like building things in sandboxes with fixed time, and using tarballs without modification dates but output bit-by-bit reproducible is not their goal. They also don't have the manpower for this.

Currently, a build is built by a trusted builderver for which you have the public key. And you look up the built by input hash but have no way to check if the thing the builderver is serving is legit. It's fully based on trust.

However, with debian putting so much effort in reproducible output, Nix can benefit too. In the future, we would like to get rid of the 'trust-based' build servers and instead move to a consensus model. Say if 3 servers give the same output hash given an input hash, then we trust that download and avoid a compile from source. If you still don't trust it, you can build from source yourself and check if the source is trustworthy.

Summary: Nix does not do bit-by-bit reproducibility, but we benefit greatly from the work that debian is doing. In the future we will look at setting up infrastructure for buildservers with an output-hash based trust model instead of an input based one. However this will take time.

Feel Free to ask any other questions.

In the context of "reproducible builds", it means that if you compile the same source code with the same compiler and build system, the output will be completely identical, bit by bit. This is surprisingly hard to achieve in practice.

Once they have reproducible builds, they can easily prove that each binary package was built from the corresponding source code package: just have a third party compile the source code again and generate the binary package, and it should be identical (except for the signature). This reduces the need to trust that the build machines haven't been compromised.

It has a similar meaning to research. What it means is that you can reproduce (compile in most cases) from source code the same bit-for-bit identical binary independently. While this might sound like something that should be trivial to do, it turns out to be far from trivial (timestamps and other environment information leaks into binaries all the time).

There's a website that describes this project in much more detail as well as how they worked around the various problems they found. https://reproducible-builds.org/

In addition to all the siblings; this is also important in research - which increasingly uses computers. If you provide a paper, source code, dataset and description of the system(s) used - can someone reproduce your research?

It would certainly be convenient if you can point to a version/snapshot of Debian (or another distribution) - and it would then be possible to take your (say C) source code and compile and run the same binary used for research.

It's true that often getting the algorithm more-or-less right is enough - but the more research is augmented by computing devices, the more important it becomes to maintain reproducibility - and the more complex and capable these computer devices (say a top-100 supercomputer, software stack in C++ on top of MPI, some Fortran numeric libraries etc) become - the harder it becomes to maintain it.

Imagine verifying research done today by repeating experiments in 50 years.

No, the same architecture.

It has taken, and continues to take, a suprising amount of work to make two builds of a program produce the same output.

There are many sources of issues. For example: date and time stored in output, program's output effected by order in which files are read from a directory (and is not having a fixed ordering), hash tables based on the pointer and the high objects are stored having different ordering on different executions, parallel programs behaving differently on different runs, and others.

It's about being able to reproduce the binary from source. You might think this is pretty much impossible in the Debian context, but things like timestamps, and underspecified dependencies can end up shifting a build's result over time.

If we want to insist that open source code is secure by source code analysis, we need a verifiable build chain, that the code and binaries an analysis uses are the same as what we get later.

It means each time you build the same code in a known setup, you get bit for bit the same binary. That allows you to assure that the code that's shipped actually matches the source code.

It sounds trivial, but the full paths and timestamps that get added at multiple points in the process are enough to screw this up, and those are the easy problems.

I think it's for security. It means that there's a deterministic relationship between the source of a program and its final compiled artifacts.

If software has reproducible builds that means that third-parties can independently verify that artifacts have been built safely from sources, without any sneaky stuff snuck in.

It means ensuring that anyone can verify that a binary was created from a given set of source code, by recompiling it and getting the exact same file.

What do you mean by "cryptographically show"? With reproducible builds, anyone that has repeated a build can verify that a claimed binary matches, and could sign a statement saying so. But I don't think there are solutions that don't include someone repeating the build, or a clear way of proving that you actually did repeat the build.

Yes. The first standard for securing computer systems mandated some protections against this. They were partly made by Paul Karger who invented the compiler subversion Thompson wrote about a decade later. Most just focused on that one thing where Karger et al went on to build systems that were secure from ground up with some surviving NSA pentesting and analysis for 2-5 years. Independently, people started building verified compilers and whole stacks w/ CPU's. They were initially simple with a lot to trust but got better over time. Recently, the two schools have been merging more. Mainstream INFOSEC and IT just ignores it all slowly reinventing it piece by piece with knock offs. It's hard, has performance hit, or is built in something other than C language so don't do it. (shrugs)

Here's several examples:

VLISP for Scheme48 whose papers are here: https://en.wikipedia.org/wiki/PreScheme

C0 compiler + whole stack correctness in Verisoft http://www.verisoft.de/VerisoftRepository.html

CompCert Compiler for C http://compcert.inria.fr/

CakeML Subset of Standard ML https://cakeml.org/

Rockwell-Collins doing crypto DSL compiled to verified CPU http://www.ccs.neu.edu/home/pete/acl206/slides/hardin.pdf

Karger's original paper with the attack from 1970's: https://www.acsac.org/2002/papers/classic-multics.pdf

Myer's landmark work on subversion in high-assurance security from 1980: http://csrc.nist.gov/publications/history/myer80.pdf

My framework I developed studying Karger back when I was building secure things:

http://pastebin.com/y3PufJ0V

No. Or at least this doesn't provide that. I think in theory you could make a crypto compiler that proves the binary is isogonal to the source, but I suspect the verification effort wouldn't be much less than recompiling.

Just curious: how does one do that? Hash both the binary and source code files, that THAT hash, then sign it? Or am I completely off?

On NixOS python is patched so that if the environment variable DETERMINISTIC_BUILD is present the interpreter set the bytecode timestamps to 0. I suppose they did something similar.

Also, Debian binary packages don't ship prebuilt python bytecode, which is compiled at installation time. (just to reply to the specific example)

Sometimes by eliminating the timestamps (don't put __DATE__ and __TIME__ in C code, for instance), but when that isn't possible:

https://reproducible-builds.org/specs/source-date-epoch/

Why would the randomness in unit tests affect the binary? RNGs are invoked when the tests are run, not when they're built, and anyway, test code shouldn't be part of the final binary.

My take on that is that those devs are probably fooling themselves about the state of their test suite. I'm working on a codebase like that right now - it's in generally a relatively good state, but just this week I've run into a moderately nasty bug involving global state not getting properly reset which the tests didn't cover because their specific execution order happened to work.

Or just seed the PRNG with some digest of the relevant source code (perhaps as simple as the version number). Doesn’t solve the problem that your tests can suddenly break on unrelated changes, but does solve the problem that your tests can break without any changes.

Down-voted because that's not an argument against reproducible builds. The outputs can be bit-for-bit identical but still use an RNG for fuzz testing.

Non-determinism should be on a leaf of the DAG.