shrinkwrap: introduce new shrinkwrap option

[fzakaria]

Add a new command to patchelf --shrink-wrap which shrink-wraps thebinary file.

patchelf at the moment works by modifying the RUNPATH to help locate files to the store however it only does this generally for it's immediate DT_NEEDED.

There can be cases where binaries correctly run but are doing so just by chance that the linker has found the library previously during it's walk. To avoid this, lets pull up all DT_NEEDED to the top-level executable and immortalize them by having their entries point to very specific location.

Here is a simple example for bash: /nix/store/99dvxgs2vqcsa05b793ympydrqaxi19z-bash-interactive-5.1-p12/bin/bash

> patchelf --print-needed bash
libreadline.so.8
libhistory.so.8
libncursesw.so.6
libdl.so.2
libc.so.6

We then shrink-wrap it!

> patchelf --shrink-wrap /tmp/bash

Let's see the new DT_NEEDED list.

> patchelf --print-needed /tmp/bash
/nix/store/nzgv1p48v3ya3mcvkdd9w3kaifl2c4gl-readline-8.1p0/lib/libreadline.so.8
/nix/store/nzgv1p48v3ya3mcvkdd9w3kaifl2c4gl-readline-8.1p0/lib/libhistory.so.8
/nix/store/yilda176cq33hbv240mqzkf6ks6r9b1p-ncurses-6.2/lib/libncursesw.so.6
/nix/store/563528481rvhc5kxwipjmg6rqrl95mdx-glibc-2.33-56/lib/libdl.so.2
/nix/store/563528481rvhc5kxwipjmg6rqrl95mdx-glibc-2.33-56/lib/libc.so.6

Here is an example that was not built with Nix: /usr/bin/ruby

> patchelf --print-needed ruby
libruby-2.7.so.2.7
libc.so.6

> patchelf --shrink-wrap ruby

> patchelf --print-needed /tmp/ruby
/lib/x86_64-linux-gnu/libcrypt.so.1
/lib/x86_64-linux-gnu/libdl.so.2
/lib/x86_64-linux-gnu/libgmp.so.10
/lib/x86_64-linux-gnu/libm.so.6
/lib/x86_64-linux-gnu/libpthread.so.0
/lib/x86_64-linux-gnu/librt.so.1
/lib/x86_64-linux-gnu/libcrypt.so.1
x86_64-linux-gnu/libdl.so.2

[fzakaria]

Looks like there exists another bug in patchelf since x86_64-linux-gnu/libdl.so.2 is missing /lib/ prefix in my example. I am trying to find it.

[fzakaria]

Looks very similar the current bug to https://github.com/NixOS/patchelf/issues/115#issuecomment-645100954

[fzakaria]

@Mic92 let me know if you have any leads -- I am trying to look into it but I think it's something with the rewriting of gnu.version_r

[Mic92]

So this replaces DT_NEEDED files with absolute library paths? That would be very useful since it would make library loading a lot faster.

[fzakaria]

@Mic92 not only that but it also pulls up all DT_NEEDED during link time and makes it fixed in the upper executable. I'n practice even in Nixpkgs, some packages correctly run and link only because of the link order traversed. Pulling all the NEEDED up into the top executable makes it very easy to understand the closure of dependencies (at the moment this does not include dlopen)/

[Mic92]

cc @lheckemann

[Mic92]

I think haskell folks would be also interested in this because of quadratic complexity of some dynamic linked haskell programs.

[Mic92]

Ideally we could avoid using ld here - but I have to check how hard it would be to re-implement it. Reason is that we would be independent of the used libc and it might be more secure (I heard using ldd can execute code from the binary - I don't know if ld has the same issue). Maybe for a first prototype, where check the feasibility of this feature could use ld. Looking at https://github.com/ncopa/lddtree, which is implemented in bash, it might be actually not too complex.

[fzakaria]

Discussion over Matrix with @Mic92: The reason I wanted to use ld from the ELF file itself was to guarantee that the list resolved is what the dynamic linker would have done. Re-implementing that functionality seemed like an endeavor that was doomed to promise the same reproducibility.

@Mic92 did bring up the fact though that this may have issues during cross-compiling since it invokes the target linker. That seems like a valid point here that I will have to think about more.

https://github.com/NixOS/patchelf/issues/359 needs to be resolved as well. The other suggestions are valid and I will look into making them (i.e. popen, compiling the regex & handling errors).

@Mic92 brought up https://catonmat.net/ldd-arbitrary-code-execution as a possible exploit. I don't think that's a valid exploit at all, but just a misunderstanding what ldd in fact does.ldd doesn't do anything but in fact call the linker in the .interp with some environment variables so of course, if you have a custom linker it's going to call it. (that is because ldd doesn't do the actual determination of linking, it's just a wrapper script)

[trws]

I suppose that's a valid exploit of a sort, but ldd normally calls its own loader rather than the one in the binary. That's why this patch is set up to explicitly use the appropriate loader from the binary, it's immune to that issue.

Still, it's a good point that this will not work well in a cross-compilation scenario, having a way to directly access the information would be good, but I'm not sure if the method used by lddtree would be portable across libc implementations.

[Mic92]

I suppose that's a valid exploit of a sort, but ldd normally calls its own loader rather than the one in the binary. That's why this patch is set up to explicitly use the appropriate loader from the binary, it's immune to that issue.

Still, it's a good point that this will not work well in a cross-compilation scenario, having a way to directly access the information would be good, but I'm not sure if the method used by lddtree would be portable across libc implementations.

I think there should be an algorithm that is portable, otherwise compile-time ELF linker would be libc specific, which they are not according to my knowledge. (I mean the library loading part, there are indeed section added by linker that are only processed by certain libc's)

There can be cases where binaries correctly run but are doing so just by chance that the linker has found the library previously during it's walk. To avoid this, lets pull up all DT_NEEDED to the top-level executable and immortalize them by having their entries point to very specific location.

Can you construct an example where our current rpath approach, won't work? From my understanding we use ld.so to compute libraries - so if libraries they could be not interfered from RPATH than ld.so would be not able to give us the libraries for patching in the first place.

[Mic92]

An ugly workaround for cross compiling would be the use of qemu user emulation...

[trws]

It's probably only the actual relocation that can have issues, but attempting to use an ldd or an ld.so that's from a different libc causes the exploit you mentioned, and fails to list libraries. It's possible to walk the needed, rpath and runpath without using the loader, but determining if they can actually load may well not be feasible without a lot of work. I think that's what @haampie's libtree does, even abstracting out some BSD/Linux details, but I'm not sure what all that requires. It's also potentially important which set of string interpolations the loader supports. That's why starting this way is appealing, those questions are answered by the loader itself without us encoding all the exceptions.

[fzakaria]

@Mic92 for examples of motivation & discovering these issues I issued the following and it returns a few examples.

> find /nix/store -type f -executable -print | xargs libtree | grep "not found" --with-filename

Here was one such found from Zotero package:

❯ ~/Downloads/libtree_x86_64 /nix/store/2ng411lq8m2n9279zla1s1iz2bgzaxma-zotero-5.0.89/usr/lib/zotero-bin-5.0.89/libsoftokn3.so
libsoftokn3.so
├── libnspr4.so [runpath]
├── libnssutil3.so [runpath]
│   ├── libplds4.so [runpath]
│   │   └── libnspr4.so (collapsed) [runpath]
│   ├── libplc4.so [runpath]
│   │   └── libnspr4.so (collapsed) [runpath]
│   └── libnspr4.so (collapsed) [runpath]
├── libplc4.so (collapsed) [runpath]
├── libplds4.so (collapsed) [runpath]
└── libmozsqlite3.so not found: RPATH (empty) LD_LIBRARY_PATH (empty) RUNPATH "/nix/store/51hq0xxp9nng3xxfz7dpkhb9lzy7sz84-gcc-9.3.0-lib/lib":"/nix/store/yfdvbimd66prviwr7dq3cwx6gc7qzyy1-atk-2.36.0/lib":"/nix/store/96kgw3as9fl4i1ya9qi452l0si2j07l7-cairo-1.16.0/lib":"/nix/store/izq29d1nqgc348pi96rjlr8cvxysimsx-curl-7.73.0/lib":"/nix/store/sxbc3vwssygib7zamyd12hpgx3vlkmrp-cups-2.3.3-lib/lib":"/nix/store/a8fnf6pjn5vgdy4iyfcp7ra390qj2vkc-dbus-glib-0.110/lib":"/nix/store/92nq33qigk5nzwp7nhh4hkzbqrjpwpl4-dbus-1.12.20-lib/lib":"/nix/store/6c6wxiygil0anckb2z57zslgxcpzdllf-fontconfig-2.13.92-lib/lib":"/nix/store/65gyai5wljjjacsp28g9davg79in3ma2-freetype-2.10.4/lib":"/nix/store/f8nh02yh7j7q5vkgq48zniblk51kpr6y-gdk-pixbuf-2.40.0/lib":"/nix/store/0ds5gvys9awz8ab2mybyfhy7532yrhxa-glib-2.66.2/lib":"/nix/store/a6rnjp15qgp8a699dlffqj94hzy1nldg-glibc-2.32/lib":"/nix/store/lbaq8v4r1vzbadw02j0adfhin00pyyc8-gtk+3-3.24.23/lib":"/nix/store/cmzbw5bk1yva5zk4y61jjz9l3190q7a5-libX11-1.6.12/lib":"/nix/store/i3vs6nwn8x845bq1ky6w5rkph81qg50d-libXScrnSaver-1.2.3/lib":"/nix/store/wxvv4djzpf1kbhri5yxswq8xrvvs1vnv-libXcomposite-0.4.5/lib":"/nix/store/ddwbggavgxlfkkradyab73j3m1g8y7f3-libXcursor-1.2.0/lib":"/nix/store/50yrd3s46247gh7943bnzqn5ny7ck2pp-libxcb-1.14/lib":"/nix/store/32c65sxpjf7w655khcmgdck1glp3636k-libXdamage-1.1.5/lib":"/nix/store/622b1nj4bqhx8vl56215vp7b7apxn5px-libXext-1.3.4/lib":"/nix/store/ry8qbn7s4b6z3zad97f6n8x9bp0gxczx-libXfixes-5.0.3/lib":"/nix/store/pg8ak9bj087v258n97fy6qrq05nnx2zc-libXi-1.7.10/lib":"/nix/store/gpg620v348xc1yvccsq86fj1k7maap67-libXinerama-1.1.4/lib":"/nix/store/0k979a89ix8xz02jid2g475pwwclzp0c-libXrender-0.9.10/lib":"/nix/store/gwx569mpr1cr3vdd0mj65mrfblwq6sij-libXt-1.2.0/lib":"/nix/store/sqj1jrj90qadqzhcdm4xi6qxvn72wamm-libnotify-0.7.9/lib":"/nix/store/m43f498s2g5x4jgkqln3v2nrcknxkvlm-glu-9.0.1/lib":"/nix/store/pk0pb3ij8mk969zi6xgdc7mljzrdw9ja-libGL-1.3.2/lib":"/nix/store/mypq59dnk7ww21cx72nj9cgs8fa84f04-nspr-4.29/lib":"/nix/store/zl7qajvg2dx37cy8xiijylbxmg5vrc1d-nss-3.59/lib":"/nix/store/d3z71gzxxhrbkpyqldigb2jk3380dg2x-pango-1.47.0/lib":"/nix/store/51hq0xxp9nng3xxfz7dpkhb9lzy7sz84-gcc-9.3.0-lib/lib64": /etc/ld.so.conf "/usr/lib/x86_64-linux-gnu/libfakeroot":"/usr/local/lib/i386-linux-gnu":"/lib/i386-linux-gnu":"/usr/lib/i386-linux-gnu":"/usr/local/lib/i686-linux-gnu":"/lib/i686-linux-gnu":"/usr/lib/i686-linux-gnu":"/usr/local/lib":"/usr/local/lib/x86_64-linux-gnu":"/lib/x86_64-linux-gnu":"/usr/lib/x86_64-linux-gnu":"/lib32":"/usr/lib32":

Zotero correctly runs but here the shared object had the wrong paths. That means changes to the other libs could cause failure. You can also see that the RUNPATH is also pretty long alluding to the performance you mentioned.

Most of what I've discovered are from libraries

[fzakaria]

FWIW on my local /nix/store could not find any oddly built executables directly

#!/usr/bin/env ruby

Dir.glob('/nix/store/*/bin/*').each do|f|
    next if f.include?("trash")
    next unless File.executable?(f)
    output = `libtree #{f}`
    if output.include?("not found")
        puts f
    end
end

[haampie]

@fzakaria note that nixos is not (yet) properly supported by libtree, because it has to make a few assumptions about the default search paths of the runtime linker (e.g. /lib:/usr/lib). They can differ between distro's and I'm not sure how to properly retrieve them (even if you invoke the dynamic linker which I try not to do, it requires a very recent glibc to have ld.so --help print the default search paths). See https://github.com/haampie/libtree/issues/61

[JonathonReinhart]

Interesting! This is similar to what staticx tries to do to run programs bundled with their dependencies.

[Ericson2314]

I think there should be an algorithm that is portable, otherwise compile-time ELF linker would be libc specific, which they are not according to my knowledge. (I mean the library loading part, there are indeed section added by linker that are only processed by certain libc's)

Agreed. Let's just implement looking for SOs in the runpath ourselves. I don't really care if that doesn't do the exact same thing, we can add more complexity to better mimic what various ld.sos do later.

[fzakaria]

@Ericson2314 that could make sense in the NixOS context where maybe only looking through RUNPATH would make sense but using patchelf outside of NixOS I think it's a bigger task to replicate all the behavior of: RPATH, RUNPATH, default libs etc.. (I see @haampie mention how discovering even the default paths is challenging itself).

I really like the idea that shrink-wrap effectively "freezes" what the linker will have done which is effectively portable across distributions but I am open to continue discussing :)

I am planning to meet with @Mic92 to discuss -- if you are interesting reach out to me on Matrix (fzakaria) with your email to send you the invite.

[8573]

I'm glad to see a solution to https://github.com/NixOS/nixpkgs/issues/24844.

@Ericson2314, would you say your contention about correctness at https://github.com/NixOS/nixpkgs/issues/24844#issuecomment-491888236 is also relevant here?

[trws]

This does help with correctness in that sense, that's part of what we're trying to do here. There are a couple of different solutions we're exploring too, because this one depends on the libc doing sensible things more than might be ideal. This also doesn't solve the massive over-stat problem for libraries loaded by dlopen, or for other similar things like python modules. Some of the other approaches might, but they all have tradeoffs. This one seems to get 90+% of the way there for glibc and BSD-like libc applications though, which is pretty cool.

[fzakaria]

It would be interesting and doable to incorporate into nixpks only when it is glibc through a check in patchelf hook. I think @lheckemann is exploring this in the linked issue.

The fact that it is at the moment only usable by glibc is annoying but given that the majority of the code built by Nixpkgs is glibc, it would be 80/20 useful.

In order to continue investigation I've created https://github.com/fzakaria/shrinkwrap which is a simplified version of the tool in Python from some helpful code by @trws (I need to look into wrapping it with qemu for instance)

[Ericson2314]

Yeah per what @8573 quotes me saying before, I think it is hopeless trying to make this behavior-preserving in all cases, so that's why I advocate switching the goalposts focusing on simplicity to start and versitility (e.g. no assuming native).

[nh2]

I think haskell folks would be also interested in this because of quadratic complexity of some dynamic linked haskell programs.

@Mic92 What is this referring to? Don't all programs that have N builtInputs dependencies do O(n) many syscalls on startup dynamic linking (number of search paths * number of .sos)?

[nh2]

The fact that it is at the moment only usable by glibc is annoying

@fzakaria Can you clarify, what exactly is it that makes this improvement glibc-only?

Is this referring to the ld.so --help from https://github.com/NixOS/patchelf/pull/357#issuecomment-998261061?

[Mic92]

I think haskell folks would be also interested in this because of quadratic complexity of some dynamic linked haskell programs.

@Mic92 What is this referring to? Don't all programs that have N builtInputs dependencies do O(n) many syscalls on startup dynamic linking (number of search paths * number of .sos)?

I had false memory that haskell programs would link each haskell library as a shared object against the binary, which could create large RPATHs, but this seems wrong.

[Ericson2314]

I thought it would search the entire search path for every SO, so given we about as many RUNPATH entries as SOs, we can get quadratic that way.

[fzakaria]

@nh2 musl and other linkers do a different cache strategy then glibc. I've put a lot of the relevant information on a musl mailing list you can refer to https://www.openwall.com/lists/musl/2021/12/21/1

I have made a lot of progress on my shrinkwrap tool to explore this space prior to merging upstream into patchelf. Please take a look: https://github.com/fzakaria/shrinkwrap

I will explore running a nixpkg-hook to do similar functionality to that of patchelf and explore with binaries that have large RUNPATHS or NEEDED (i.e. chromium).

I have also added a virtual resolution strategy so that it can work in cross-compilation cases.

❯ ./result/bin/shrinkwrap /usr/bin/sed --link-strategy native
❯ ./sed_stamped --help
Usage: ./sed_stamped [OPTION]... {script-only-if-no-other-script} [input-file]...

  -n, --quiet, --silent

❯ ldd ./sed_stamped
	linux-vdso.so.1 (0x00007ffdabedb000)
	/lib/x86_64-linux-gnu/libnss_cache.so.2 (0x00007f999aef7000)
	/lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f999aed6000)
	/lib/x86_64-linux-gnu/libdl.so.2 (0x00007f999aed0000)
	/lib/x86_64-linux-gnu/libpcre2-8.so.0 (0x00007f999ae38000)
	/lib/x86_64-linux-gnu/libc.so.6 (0x00007f999ac73000)
	/lib/x86_64-linux-gnu/libselinux.so.1 (0x00007f999ac47000)
	/lib/x86_64-linux-gnu/libacl.so.1 (0x00007f999ac3a000)
	/lib64/ld-linux-x86-64.so.2 (0x00007f999afa3000)

❯ readelf -a ./sed_stamped| grep "Version needs section '.gnu.version" -A 10
Version needs section '.gnu.version_r' contains 3 entries:
 Addr: 0x0000000000003860  Offset: 0x003860  Link: 6 (.dynstr)
  000000: Version: 1  File: /lib/x86_64-linux-gnu/libacl.so.1  Cnt: 1
  0x0010:   Name: ACL_1.0  Flags: none  Version: 5
  0x0020: Version: 1  File: /lib/x86_64-linux-gnu/libselinux.so.1  Cnt: 1
  0x0030:   Name: LIBSELINUX_1.0  Flags: none  Version: 4
  0x0040: Version: 1  File: /lib/x86_64-linux-gnu/libc.so.6  Cnt: 6
  0x0050:   Name: GLIBC_2.14  Flags: none  Version: 9
  0x0060:   Name: GLIBC_2.7  Flags: none  Version: 8
  0x0070:   Name: GLIBC_2.4  Flags: none  Version: 7
  0x0080:   Name: GLIBC_2.3.4  Flags: none  Version: 6

[fzakaria]

Here is an interesting metric when trying to replicate the error as posted in Guix via this blog post on stat storm

strace -e openat,stat -c ./emacs_stamped --version
GNU Emacs 27.2
Copyright (C) 2021 Free Software Foundation, Inc.
GNU Emacs comes with ABSOLUTELY NO WARRANTY.
You may redistribute copies of GNU Emacs
under the terms of the GNU General Public License.
For more information about these matters, see the file named COPYING.
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
100.00    0.000950           9       104         1 openat
------ ----------- ----------- --------- --------- ----------------
100.00    0.000950           9       104         1 total

fmzakari@fmzakari-glaptop:~/code/github.com/fzakaria/shrinkwrap$ strace -e openat,stat -c /nix/store/vvxcs4f8x14gyahw50ssff3sk2dij2b3-emacs-27.2/bin/.emacs-27.2-wrapped --version
GNU Emacs 27.2
Copyright (C) 2021 Free Software Foundation, Inc.
GNU Emacs comes with ABSOLUTELY NO WARRANTY.
You may redistribute copies of GNU Emacs
under the terms of the GNU General Public License.
For more information about these matters, see the file named COPYING.
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
100.00    0.034121          18      1823      1720 openat
------ ----------- ----------- --------- --------- ----------------
100.00    0.034121          18      1823      1720 total

1823 vs. 104 calls~!

CC @tomberek

[nixos-discourse]

This pull request has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/content-addressed-nix-call-for-testers/12881/170