Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

vmTools.debClosureGenerator: Fix non-determinism in dependency graph #107958

Merged
merged 1 commit into from Jan 10, 2021

Conversation

ztzg
Copy link
Contributor

@ztzg ztzg commented Dec 30, 2020

Motivation for this change

By default, Perl versions since 5.8.1 use randomization to make hashes resistant to complexity attacks.

That randomization makes building VM images such as ubuntu1804x86_64 non-deterministic because the (imported) derivations built by deb/deb-closure.pl are not stable.

This can easily be observed by repeating the following sequence of commands and noting the path of the image's .drv file:

nix-instantiate -E '(import <nixpkgs> {}).vmTools.diskImageFuns.ubuntu1804x86_64 {}'
nix-store --delete /nix/store/*ubuntu-18.04-bionic-amd64.nix

One source of non-determinism is the handling of Provides/Replaces, which depends on the order of iteration over %packages. Here is a diff showing the corresponding change in output:

 >>> awk
-virtual awk: using original-awk
-    original-awk: libc6 (>= 2.14)
+virtual awk: using mawk
+    mawk: libc6 (>= 2.14)
 [...]
-    mawk: libc6 (>= 2.14)
->>> libc6

This patch sorts packages by name for Provides/Replaces processing, which seems to result in stable output.

(If the above turns out not to be sufficient, one could also set the PERL_HASH_SEED and PERL_PERTURB_KEYS environment variables, documented in perlrun, to disable Perl's built-in randomization. Complexity attacks are not an issue as we control and trust all inputs.)

Things done
  • Tested using sandboxing (nix.useSandbox on NixOS, or option sandbox in nix.conf on non-NixOS linux)
  • Built on platform(s)
    • NixOS
    • macOS
    • other Linux distributions
  • Tested via one or more NixOS test(s) if existing and applicable for the change (look inside nixos/tests)
    • nixos/tests/os-prober.nix
    • nixos/tests/virtualbox.nix
  • Tested compilation of all pkgs that depend on this change using nix-shell -p nixpkgs-review --run "nixpkgs-review wip"
    • (None?)
  • Tested execution of all binary files (usually in ./result/bin/)
  • Determined the impact on package closure size (by running nix path-info -S before and after)
  • Ensured that relevant documentation is up to date
    • (None?)
  • Fits CONTRIBUTING.md.

By default, Perl versions since 5.8.1 use randomization to make hashes
resistant to complexity attacks.

That randomization makes building VM images such as ubuntu1804x86_64
non-deterministic because the (imported) derivations built by
deb/deb-closure.pl are not stable.

This can easily be observed by repeating the following sequence of
commands and noting the path of the image's .drv:

    nix-instantiate -E '(import <nixpkgs> {}).vmTools.diskImageFuns.ubuntu1804x86_64 {}'
    nix-store --delete /nix/store/*ubuntu-18.04-bionic-amd64.nix

One source of non-determinism is the handling of Provides/Replaces,
which depends on the order of iteration over %packages.  Here is a
diff showing the corresponding change in output:

     >>> awk
    -virtual awk: using original-awk
    -    original-awk: libc6 (>= 2.14)
    +virtual awk: using mawk
    +    mawk: libc6 (>= 2.14)

    -    mawk: libc6 (>= 2.14)
    ->>> libc6

This patch sorts packages by name for Provides/Replaces processing,
which seems to result in stable output.

(If the above turns out not to be sufficient, one could also set the
PERL_HASH_SEED and PERL_PERTURB_KEYS environment variables, documented
in 'perlrun', to disable Perl's built-in randomization.  Complexity
attacks are not an issue as we control and trust all inputs.)
@SuperSandro2000
Copy link
Member

nix-instantiate -E '(import <nixpkgs> {}).vmTools.diskImageFuns.ubuntu1804x86_64 {}'
nix-store --delete /nix/store/*ubuntu-18.04-bionic-amd64.nix

I've run those commands 3 times and the output is deterministic for me. Am I missing something?

@ztzg
Copy link
Contributor Author

ztzg commented Dec 30, 2020

nix-instantiate -E '(import <nixpkgs> {}).vmTools.diskImageFuns.ubuntu1804x86_64 {}'
nix-store --delete /nix/store/*ubuntu-18.04-bionic-amd64.nix

I've run those commands 3 times and the output is deterministic for me. Am I missing something?

@SuperSandro2000: Well, yes; you're missing my nice demo :)

More seriously: I have tried in multiple (Linux-based) environments, and have never seen the same /nix/store/*-ubuntu-18.04-bionic-amd64.drv three times in a row. That being said, it's a possibility: I sometimes see repeats, too, and the number of combinations doesn't seem to be very high.

I just ran it 10 times; here is what I am seeing (NixOS, sandboxed):

/nix/store/2mxm76g659d0pb4w1vdypg90592nd4my-ubuntu-18.04-bionic-amd64.drv
/nix/store/njfg4qapz840szplbbr4wkxh0wnzl28f-ubuntu-18.04-bionic-amd64.drv
/nix/store/njfg4qapz840szplbbr4wkxh0wnzl28f-ubuntu-18.04-bionic-amd64.drv
/nix/store/0v06kxjl0a2za5k7258fp24gkmfqgfpg-ubuntu-18.04-bionic-amd64.drv
/nix/store/0v06kxjl0a2za5k7258fp24gkmfqgfpg-ubuntu-18.04-bionic-amd64.drv
/nix/store/njfg4qapz840szplbbr4wkxh0wnzl28f-ubuntu-18.04-bionic-amd64.drv
/nix/store/2mxm76g659d0pb4w1vdypg90592nd4my-ubuntu-18.04-bionic-amd64.drv
/nix/store/0v06kxjl0a2za5k7258fp24gkmfqgfpg-ubuntu-18.04-bionic-amd64.drv
/nix/store/2mxm76g659d0pb4w1vdypg90592nd4my-ubuntu-18.04-bionic-amd64.drv
/nix/store/2mxm76g659d0pb4w1vdypg90592nd4my-ubuntu-18.04-bionic-amd64.drv

I also see the same kind of thing on a RHEL7 box (single-user installation).

@SuperSandro2000
Copy link
Member

After running it like 10 times I finally got a hash mismatch.

@ztzg
Copy link
Contributor Author

ztzg commented Jan 1, 2021

After running it like 10 times I finally got a hash mismatch.

Interesting. No idea how to explain the relative stability in your environment.

@ztzg
Copy link
Contributor Author

ztzg commented Jan 8, 2021

Hi @SuperSandro2000,

What do you think would be the next steps for this PR? Would you have specific reviewers to suggest?

Thanks, -D

@Mic92 Mic92 merged commit 82115f0 into NixOS:master Jan 10, 2021
@ztzg
Copy link
Contributor Author

ztzg commented Jan 10, 2021

Great; thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants