Finding Non-determinism with nixbuild.net

Posted on January 13, 2021 by Rickard Nilsson

During the last decade, many initiatives focussing on making builds reproducible have gained momentum. reproducible-builds.org is a great resource for anyone interested in how the work progresses in multiple software communities. r13y.com tracks the current reproducibility metrics in NixOS.

Nix is particularly suited for working on reproducibility, since it by design isolates builds and comes with tools for finding non-determinism. The Nix community also works on related projects, like Trustix and the content-addressed store.

This blog post summarises how nixbuild.net can be useful for finding non-deterministic builds, and announces a new feature related to reproducibility!

Repeated Builds

The way to find non-reproducible builds is to run the same build multiple times and check for any difference in results, when compared bit-for-bit. Since Nix guarantees that all inputs will be identical between the runs, just finding differing output results is enough to conclude that a build is non-deterministic. Of course, we can never prove that a build is deterministic this way, but if we run the build many times, we gain a certain confidence in it.

To run a Nix build multiple times, simply add the –repeat option to your build command. It will run your build the number of extra times you specify.

Suppose we have the following Nix expression in deterministic.nix:

let
  inherit (import <nixpkgs> {}) runCommand;
in {
  stable = runCommand "stable" {} ''
    touch $out
  '';

  unstable = runCommand "unstable" {} ''
    echo $RANDOM > $out
  '';
}

We can run repeated builds like this (note that the --builders "" option is there to force a local build, to not use nixbuild.net):

$ nix-build deterministic.nix --builders "" -A stable --repeat 1
these derivations will be built:
  /nix/store/0fj164aqyhsciy7x97s1baswygxn8lzf-stable.drv
building '/nix/store/0fj164aqyhsciy7x97s1baswygxn8lzf-stable.drv' (round 1/2)...
building '/nix/store/0fj164aqyhsciy7x97s1baswygxn8lzf-stable.drv' (round 2/2)...
/nix/store/6502c5490rap0c8dhvfwm5rhi22i9clz-stable

$ nix-build deterministic.nix --builders "" -A unstable --repeat 1
these derivations will be built:
  /nix/store/psmn1s3bb97989w5a5b1gmjmprqcmf0k-unstable.drv
building '/nix/store/psmn1s3bb97989w5a5b1gmjmprqcmf0k-unstable.drv' (round 1/2)...
building '/nix/store/psmn1s3bb97989w5a5b1gmjmprqcmf0k-unstable.drv' (round 2/2)...
output '/nix/store/g7a5sf7iwdxs7q12ksrzlvjvz69yfq3l-unstable' of '/nix/store/psmn1s3bb97989w5a5b1gmjmprqcmf0k-unstable.drv' differs from previous round
error: build of '/nix/store/psmn1s3bb97989w5a5b1gmjmprqcmf0k-unstable.drv' failed

Running repeated builds on nixbuild.net works exactly the same way:

$ nix-build deterministic.nix -A stable --repeat 1
these derivations will be built:
  /nix/store/wnd5y30jp3xwpw1bhs4bmqsg5q60vc8i-stable.drv
building '/nix/store/wnd5y30jp3xwpw1bhs4bmqsg5q60vc8i-stable.drv' (round 1/2) on 'ssh://eu.nixbuild.net'...
copying 1 paths...
copying path '/nix/store/z3wlpwgz66ningdbggakqpvl0jp8bp36-stable' from 'ssh://eu.nixbuild.net'...
/nix/store/z3wlpwgz66ningdbggakqpvl0jp8bp36-stable

$ nix-build deterministic.nix -A unstable --repeat 1
these derivations will be built:
  /nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv
building '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' (round 1/2) on 'ssh://eu.nixbuild.net'...
[nixbuild.net] output '/nix/store/srch6l8pyl7z93c7gp1xzf6mq6rwqbaq-unstable' of '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' differs from previous round
error: build of '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' on 'ssh://eu.nixbuild.net' failed: build was non-deterministic
builder for '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' failed with exit code 1
error: build of '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' failed

As you can see, the log output differs slightly between the local and the remote builds. This is because when Nix submits a remote build, it will not do the determinism check itself, instead it will leave it up to the builder (nixbuild.net in our case). This is actually a good thing, because it allows nixbuild.net to perform some optimizations for repeated builds. The following sections will enumerate those optimizations.

Finding Non-determinism in Past Builds

If you locally try to rebuild a something that has failed due to non-determinism, Nix will build it again at least two times (due to --repeat) and fail it due to non-determinism again, since it keeps no record of the previous build failure (other than the build log).

However, nixbuild.net keeps a record of every build performed, also for repeated builds. So when you try to build the same derivation again, nixbuild.net is smart enough to look at its past build and figure out that the derivation is non-deterministic without having to rebuild it. We can demonstrate this by re-running the last build from the example above:

$ nix-build deterministic.nix -A unstable --repeat 1
these derivations will be built:
  /nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv
building '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' (round 1/2) on 'ssh://eu.nixbuild.net'...
[nixbuild.net] output '/nix/store/srch6l8pyl7z93c7gp1xzf6mq6rwqbaq-unstable' of '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' differs from previous round
error: build of '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' on 'ssh://eu.nixbuild.net' failed: a previous build of the derivation was non-deterministic
builder for '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' failed with exit code 1
error: build of '/nix/store/6im1drv4pklqn8ziywbn44vq8am977vm-unstable.drv' failed

As you can see, the exact same derivation fails again, but now the build status message says: a previous build of the derivation was non-deterministic. This means nixbuild.net didn’t have to run the build, it just checked its past outputs for the derivation and noticed they differed.

When nixbuild.net looks at past builds it considers all outputs that have been signed by a key that the account trusts. That means that it can even compare outputs that have been fetched by substitution.

Scaling Out Repeated Builds

When you use --repeat, nixbuild.net will create multiple copies of the build and schedule all of them like any other build would have been scheduled. This means that every repeated build will run in parallel, saving time for the user. As soon as nixbuild.net has found proof of non-determinism, any repeated build still running will be cancelled.

Provoking Non-determinism through Filesystem Randomness

As promised in the beginning of this blog post, we have new a feature to announce! nixbuild.net is now able to inject randomness into the filesystem that the builds see when they run. This can be used to provoke builds to uncover non-deterministic behavior.

The idea is not new, it is in fact the exact same concept as have been implemented in the disorderfs project by reproducible-builds.org. However, we’re happy to make it easily accessible to nixbuild.net users. The feature is disabled by default, but can be enabled through a new user setting.

For the moment, the implementation will return directory entries in a random order when enabled. In the future we might inject more metadata randomness.

To demonstrate this feature, let’s use this build:

let
  inherit (import <nixpkgs> {}) runCommand;
in rec {
  files = runCommand "files" {} ''
    mkdir $out
    touch $out/{1..10}
  '';

  list = runCommand "list" {} ''
    ls -f ${files} > $out
  '';
}

The files build just creates ten empty files as its output, and the list build lists those file with ls. The -f option of ls disables sorting entirely, so the file names will be printed in the order the filesystem returns them. This means that the build output will depend on how the underlying filesystem is implemented, which could be considered a non-deterministic behavior.

First, we build it locally with --repeat:

$ nix-build non-deterministic-fs.nix --builders "" -A list --repeat 1
these derivations will be built:
  /nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv
building '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' (round 1/2)...
building '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' (round 2/2)...
/nix/store/h1591y02qff8vls5v41khgjz2zpdr2mg-list

As you can see, the build succeeded. Then we delete the result from our Nix store so we can run the build again:

rm result
nix-store --delete /nix/store/h1591y02qff8vls5v41khgjz2zpdr2mg-list

We enable the inject-fs-randomness feature through the nixbuild.net shell:

nixbuild.net> set inject-fs-randomness true

Then we run the build (with --repeat) on nixbuild.net:

$ nix-build non-deterministic-fs.nix -A list --repeat 1
these derivations will be built:
  /nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv
building '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' (round 1/2) on 'ssh://eu.nixbuild.net'...
copying 1 paths...
copying path '/nix/store/vl13q40hqp4q8x6xjvx0by06s1v9g3jy-files' to 'ssh://eu.nixbuild.net'...
[nixbuild.net] output '/nix/store/h1591y02qff8vls5v41khgjz2zpdr2mg-list' of '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' differs from previous round
error: build of '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' on 'ssh://eu.nixbuild.net' failed: build was non-deterministic
builder for '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' failed with exit code 1
error: build of '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' failed

Now, nixbuild.net found the non-determinism! We can double check that the directory entries are in a random order by running without --repeat:

$ nix-build non-deterministic-fs.nix -A list
these derivations will be built:
  /nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv
building '/nix/store/153s3ir379cy27wpndd94qlfhz0wj71v-list.drv' on 'ssh://eu.nixbuild.net'...
copying 1 paths...
copying path '/nix/store/h1591y02qff8vls5v41khgjz2zpdr2mg-list' from 'ssh://eu.nixbuild.net'...
/nix/store/h1591y02qff8vls5v41khgjz2zpdr2mg-list

$ cat /nix/store/h1591y02qff8vls5v41khgjz2zpdr2mg-list
6
1
2
5
10
7
8
..
9
4
3
.

Future Work

There are lots of possibilities to improve the utility of nixbuild.net when it comes to reproducible builds. Your feedback and ideas are very welcome to [email protected].

Here are some of the things that could be done:

  • Make it possible to trigger repeated builds for any previous build, without submitting a new build with Nix. For example, there could be a command in the nixbuild.net shell allowing a user to trigger a repeated build and report back any non-determinism issues.

  • Implement functionality similar to diffoscope to be able to find out exactly what differs between builds. This could be available as a shell command or through an API.

  • Make it possible to download specific build outputs. The way Nix downloads outputs (and stores them locally) doesn’t allow for having multiple variants of the same output, but nixbuild.net could provide this functionality through the shell or an API.

  • Inject more randomness inside the sandbox. Since we have complete control over the sandbox environment we can introduce more differences between repeated builds to provoke non-determinism. For example, we can schedule builds on different hardware or use different kernels between repeated builds.

  • Add support for listing known non-deterministic derivations.