Revisit ordering of segments in the program header table on AArch32

[langston-barrett]

To fix the issues in #48, @travitch suggests we revisit the segment ordering in https://github.com/GaloisInc/renovate/blob/master/renovate/src/Renovate/BinaryFormat/ELF.hs. Specifically:

It seems like at the very least EXIDX has to come before the first loadable segment, and perhaps even be the first (the documentation I found was unclear)
It could be the case that we need per-architecture layouts (I hope we can avoid it, but that is the worst case)
It might be that we can just make sure we leave EXIDX as the first segment if it is present
Ah one important thing to note: EXIDX needs to be an early segment, but its position in the file (represented by the offset in the output of readelf) need not be first. The ordering of segments is just their position in the program headers table

[langston-barrett]

We have determined that the program headers are in the first LOAD segment of the binary. From readelf -a

  Start of program headers:          52 (bytes into file)
[...]
  Size of this header:               52 (bytes)
[...]
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x065a14 0x00075a14 0x00075a14 0x00588 0x00588 R   0x4
  LOAD           0x000000 0x00010000 0x00010000 0x65fa0 0x65fa0 R E 0x10000

[langston-barrett]

My first plan of attack is to just put PHDR at index 1 and EXIDX at index 0 if EXIDX is present in the binary.

[langston-barrett]

WIP branch: https://github.com/GaloisInc/renovate/tree/lb/fix-aarch32-tls

[langston-barrett]

With the code on that branch, I was able to maintain the index of EXIDX, but the binary still segfaults when run, at the same point as the one in #48.

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x065864 0x00075864 0x00075864 0x00570 0x00570 R   0x4
  PHDR           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  LOAD           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  LOAD           0x000000 0x00010000 0x00010000 0x65dd8 0x65dd8 R E 0x10000
  LOAD           0x066b7c 0x00086b7c 0x00086b7c 0x02384 0x02384 RW  0x10000
  NOTE           0x000114 0x00010114 0x00010114 0x00044 0x00044 R   0x4
  TLS            0x066b7c 0x00086b7c 0x00086b7c 0x00010 0x00030 R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x8
  GNU_RELRO      0x066b7c 0x00086b7c 0x00086b7c 0x00484 0x00484 R   0x1
  LOAD           0x07e000 0x00089000 0x00089000 0x03fd8 0x03fd8 R E 0x1000
  LOAD           0x098000 0x00030000 0x00030000 0x01000 0x01000 RW  0x1000

[langston-barrett]

@travitch and I now think that the problem is that the program is reading this address from the aux vector, and it's incorrect:

https://github.com/torvalds/linux/blob/242b23319809e05170b3cc0d44d3b4bd202bb073/fs/binfmt_elf.c#L258

The relevant call is here:

https://github.com/torvalds/linux/blob/242b23319809e05170b3cc0d44d3b4bd202bb073/fs/binfmt_elf.c#L1227

The variable load_addr gets calculated here (note we skip the ET_DYN branch because this is a static executable):

https://github.com/torvalds/linux/blob/242b23319809e05170b3cc0d44d3b4bd202bb073/fs/binfmt_elf.c#L1120

This calculation happens the first time we hit a PT_LOAD segment in the program header table:

https://github.com/torvalds/linux/blob/242b23319809e05170b3cc0d44d3b4bd202bb073/fs/binfmt_elf.c#L1006

In the refurbished binary, the new text segment (with the new program headers at the beginning) is the first PT_LOAD segment in the table. We're going to try ensuring that the original .text segment (which has the orginal program headers) comes first. This should work OK, because the original program headers still have the correct address of the TLS segment (the program is segfaulting in __renovate___libc_setup_tls, probably because it's reading data from somewhere other than the TLS segment).

[langston-barrett]

@travitch I was mistaken above when I said:

In the refurbished binary, the new text segment (with the new program headers at the beginning) is the first PT_LOAD segment in the table.

It's actually a LOAD segment that's generated at the same time as the new PHDR segment:

renovate/renovate/src/Renovate/BinaryFormat/ELF.hs

Line 532 in 3cedd6a

{ E.elfSegmentType = E.PT_LOAD

So after coming back and re-reading, I think I've generated a set of unsatisfiable constraints for segments in the binary :) Maybe we ruled one of these out and I just don't remember.

1. EXIDX must come before any LOAD segment in the table
2. A PHDR segment, if present, must come before any LOAD segment in the table
3. Renovate generates a PHDR and a LOAD segment at the same virtual address and offset, and the latter follows the former immediately in the table (see above)
4. The program header table in the original binary is in the original code segment (which is LOAD), but has no PHDR segment
5. We want to try making the original code segment the first LOAD segment in the binary

So to accomplish (5) (so that the aux vector value comes out right), we would have to make the LOAD segment that accompanies the PHDR segment either:

• not LOAD (but there's a comment saying this doesn't work), or
• not come immediately after the PHDR segment in the table.

Is one of those two options what you were thinking? Or am I missing something?

[langston-barrett]

Making the LOAD segment that accompanies PHDR into NULL resulted in a segfault in exactly the same place:

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x065864 0x00075864 0x00075864 0x00570 0x00570 R   0x4
  PHDR           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  NULL           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  LOAD           0x000000 0x00010000 0x00010000 0x65dd8 0x65dd8 R E 0x10000

So maybe we're back to the drawing board again...?

refurbished-null.exe.zip

[travitch]

I think that our last debugging session revealed a single simpler statement of the constraint: the load_address (calculated here https://github.com/torvalds/linux/blob/dd0d718152e4c65b173070d48ea9dfc06894c3e5/fs/binfmt_elf.c#L1120), which is computed based on the first LOAD segment, must point to the program headers.

• On x86, it happened to be the case that the layout algorithm always placed the new text segment after the original one. Possibly this could be related to the EXIDX section messing up our segment index calculations. This happened to mean that the first LOAD segment was the original one, which happened to have a program header table as its first contents. Note that it was the original table, and not the one that we added later that included the segment with our new code. The TLS setup code in glibc would use the stale table to set up TLS (but that was fine, because the new contents were not relevant for setting up TLS).
• For ARM, for some reason the first LOAD segment contains our new code, but that segment does not have the PHDRs as the first item.

Note that the kernel code computing the load_addr only cares about the first PT_LOAD segment. There can be other non-PT_LOAD segments before it (see https://github.com/torvalds/linux/blob/dd0d718152e4c65b173070d48ea9dfc06894c3e5/fs/binfmt_elf.c#L1012).

The experiment I was suggesting was to force our new text segment on ARM to come after the original one (which would put us back into the x86 case where the glibc TLS setup code sees the wrong program header table, but at least one structured correctly). If that works, we can always:

1. Put our new segment before the original segment
2. Stuff the program headers into the beginning of that segment

Note that if we do that, we need to be a bit careful about computing what the start address of the code will be (i.e., we need to account for the program header table sitting in front of it).

[langston-barrett]

@travitch I think that this is not true:

first LOAD segment contains our new code

based on this output from readelf:

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
[...]
  [ 4] .text             PROGBITS        00010170 000170 050024 00  AX  0   0 16
[...]
  [33] .extratext        PROGBITS        00089000 07e000 003fd8 00  AX  0   0 32
[...]
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x065864 0x00075864 0x00075864 0x00570 0x00570 R   0x4
  PHDR           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  LOAD           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  LOAD           0x000000 0x00010000 0x00010000 0x65dd8 0x65dd8 R E 0x10000
  LOAD           0x066b7c 0x00086b7c 0x00086b7c 0x02384 0x02384 RW  0x10000
  NOTE           0x000114 0x00010114 0x00010114 0x00044 0x00044 R   0x4
  TLS            0x066b7c 0x00086b7c 0x00086b7c 0x00010 0x00030 R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x8
  GNU_RELRO      0x066b7c 0x00086b7c 0x00086b7c 0x00484 0x00484 R   0x1
  LOAD           0x07e000 0x00089000 0x00089000 0x03fd8 0x03fd8 R E 0x1000
  LOAD           0x098000 0x00030000 0x00030000 0x01000 0x01000 RW  0x1000

It looks like the first LOAD segment contains the new program headers, but not the new code (which is at 07e000, in the second-to-last segment).

[travitch]

Then we still need to satisfy load_addr = (elf_ppnt->p_vaddr - elf_ppnt->p_offset);

[travitch]

Where "satisfy" means that the address of the program header table in that LOAD segment must be the load_addr

[langston-barrett]

nit: Based on https://github.com/torvalds/linux/blob/dd0d718152e4c65b173070d48ea9dfc06894c3e5/fs/binfmt_elf.c#L258, I think we need this address to be the address of the program header table:

load_addr + exec->e_phoff == (elf_ppnt->p_vaddr - elf_ppnt->p_offset) + exec->e_phoff

where elf_ppnt is the first LOAD segment. I will look into what it would take to make that true. Thanks for helping me clarify that bit about the first LOAD segment and the relative ordering of the new/old code segments!

[langston-barrett]

To confirm this theory, I tried out this calculation for the original and
refurbished binary:

Original binary

ELF Header:
[...]
  Size of this header:               52 (bytes)
  Start of program headers:          52 (bytes into file)
[...]
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x065864 0x00075864 0x00075864 0x00570 0x00570 R   0x4
  LOAD           0x000000 0x00010000 0x00010000 0x65dd8 0x65dd8 R E 0x10000

meaning:

• elf_ppnt->p_vaddr = 0x010000
• elf_ppnt->p_offset = 0x000000
• exec->e_phoff = 52 = 0x000034

so

(elf_ppnt->p_vaddr - elf_ppnt->p_offset) + exec->e_phoff = 0x010000 + 0x000034 = 0x010034

This makes sense, because the first LOAD segment is at offset 0x00000,
meaning it begins with the ELF header (of size 0x000034), followed immediately
by the program headers. All of this gets mapped into memory at the virtual
address 0x010000.

Refurbished binary

  Start of program headers:          667648 (bytes into file)
[...]
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x065864 0x00075864 0x00075864 0x00570 0x00570 R   0x4
  PHDR           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  LOAD           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000

meaning:

• elf_ppnt->p_vaddr = 0x00900000
• elf_ppnt->p_offset = 0x0a3000
• exec->e_phoff = 667648 = 0x0a3000

resulting in

(elf_ppnt->p_vaddr - elf_ppnt->p_offset) + exec->e_phoff = 0x00900000 - 0x0a3000 + 0x0a3000 = 0x00900000

but this should be right! This really is the virtual address of the program
header table.

[langston-barrett]

To confirm my calculations, I ran both binaries through GDB with this script:

qemu-arm -g 12345 "$1" & 
gdb-multiarch -batch -x debug.gdb refurbished.exe

set arch arm
set endian little
target remote localhost:12345
break __renovate__dl_aux_init
continue
p *(int (*)[2]) $r0

In summary, it looks like my calculation was right for the original binary, but somehow off for the refurbished binary (by 0xb000). Time to dig deeper...

Note that 0x3 is AT_PHDR: https://github.com/lattera/glibc/blob/895ef79e04a953cac1493863bcae29ad85657ee1/elf/elf.h#L1151

and we're looking at the aux vector, which is an array of these: https://github.com/lattera/glibc/blob/895ef79e04a953cac1493863bcae29ad85657ee1/elf/elf.h#L1122

Original

$1 = {0x3, 0x10034}

Refurbished

$1 = {0x3, 0xae000}

It's worth noting that this address has this value over the lifetime of the program, this isn't modified during execution.

[langston-barrett]

I also ran both programs through a Linux kernel modified with this patch. What we see in the output is that the kernel is setting a correct value for AT_PHDR, but that the binary is seeing a different value at runtime.

diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index 9fe3b51c1..2025c9b49 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -252,6 +252,8 @@ create_elf_tables(struct linux_binprm *bprm, const struct elfhdr *exec,
         */
        ARCH_DLINFO;
 #endif
+    printk("Setting AT_PHDR=0x%lx (load_addr=0x%lx, exec->e_phoff=0x%lx)\n", load_addr + exec->e_phoff, load_addr, exec->e_phoff);
 #endif
+    printk("Setting AT_PHDR=0x%lx (load_addr=0x%lx, exec->e_phoff=0x%lx)\n", load_addr + exec->e_phoff, load_addr, exec->e_phoff);
+    printk("Setting AT_PHNUM=%d\n", exec->e_phnum);
        NEW_AUX_ENT(AT_HWCAP, ELF_HWCAP);
        NEW_AUX_ENT(AT_PAGESZ, ELF_EXEC_PAGESIZE);
        NEW_AUX_ENT(AT_CLKTCK, CLOCKS_PER_SEC);
@@ -574,6 +576,7 @@ static unsigned long load_elf_interp(struct elfhdr *interp_elf_ex,
        unsigned long error = ~0UL;
        unsigned long total_size;
        int i;
+    printk("Unexpected: calling load_elf_interp\n");
 
        /* First of all, some simple consistency checks */
        if (interp_elf_ex->e_type != ET_EXEC &&
@@ -920,6 +923,7 @@ static int load_elf_binary(struct linux_binprm *bprm)
 
        /* Some simple consistency checks for the interpreter */
        if (interpreter) {
+        printk("Unexpected: found an ELF interpreter\n");
                retval = -ELIBBAD;
                /* Not an ELF interpreter */
                if (memcmp(interp_elf_ex->e_ident, ELFMAG, SELFMAG) != 0)
@@ -945,6 +949,7 @@ static int load_elf_binary(struct linux_binprm *bprm)
                                break;
 
                        case PT_LOPROC ... PT_HIPROC:
+                printk("Passing a header of type %d to arch-specific handling code\n", elf_ppnt->p_type);
                                retval = arch_elf_pt_proc(interp_elf_ex,
                                                          elf_ppnt, interpreter,
                                                          true, &arch_state);
@@ -1118,6 +1123,7 @@ static int load_elf_binary(struct linux_binprm *bprm)
                if (!load_addr_set) {
                        load_addr_set = 1;
                        load_addr = (elf_ppnt->p_vaddr - elf_ppnt->p_offset);
+            printk("load_addr=0x%lx (with elf_ppnt->p_vaddr=0x%lx and elf_ppnt->p_offset=0x%lx)\n", load_addr, elf_ppnt->p_vaddr, elf_ppnt->p_offset);
                        if (elf_ex->e_type == ET_DYN) {
                                load_bias += error -
                                             ELF_PAGESTART(load_bias + vaddr);

Original

load_addr=0x10000 (with elf_ppnt->p_vaddr=0x10000 and elf_ppnt->p_offset=0x0)
Setting AT_PHDR=0x10034 (load_addr=0x10000, exec->e_phoff=0x34)
Setting AT_PHNUM=7

Refurbished

load_addr=0x85d000 (with elf_ppnt->p_vaddr=0x900000 and elf_ppnt->p_offset=0xa3000)
Setting AT_PHDR=0x900000 (load_addr=0x85d000, exec->e_phoff=0xa3000)
Setting AT_PHNUM=11

[langston-barrett]

To confirm that we're looking at the same entry in the aux vector from the kernel and binary side, I wrote this script to print out the aux vector before we reach _dl_aux_init: https://gist.github.com/langston-barrett/5573d64ae0c9953e2fa0fe26847a5e1e. The output on the refurbished program is this:

AUX VECTOR
----------
AT_PHDR = 0xae000
AT_PHENT = 0x20
AT_PHNUM = 0xb
AT_PAGESZ = 0x1000
AT_BASE = 0x0
AT_FLAGS = 0x0
AT_ENTRY = 0x10230
AT_UID = 0x3e9
AT_EUID = 0x3e9
AT_GID = 0x3e9
AT_EGID = 0x3e9
AT_HWCAP = 0x1fb8d7
AT_CLKTCK = 0x64
AT_RANDOM = -0x103c0
AT_HWCAP2 = 0x1f
AT_NULL = 0x0

Once again confirming that this really is the right aux vector entry, and really does have the wrong value, as early as __libc_start_main.

[langston-barrett]

Here's the entire aux vector from the kernel:

0x10 = 0x1d7
0x6 = 0x1000
0x11 = 0x64
0x3 = 0x900000
0x4 = 0x20
0x5 = 0xb
0x7 = 0x0
0x8 = 0x0
0x9 = 0x101b8
0xb = 0x0
0xc = 0x0
0xd = 0x0
0xe = 0x0
0x17 = 0x0
0x19 = 0xbec62fb5

Notice that a bunch of the entries seem different, for example AT_PHENT (4) and AT_PHNUM (5) are the same betwen them, but AT_PHDR (3) is not, nor is AT_ENTRY (9). Even the order of the entries is different. I'm getting suspicious that QEMU's calculation of this for the user-space emulator is wrong. That calculation is here: https://github.com/qemu/qemu/blob/9e7f1469b9994d910fc1b185c657778bde51639c/linux-user/elfload.c#L2469

[travitch]

Are you sure that code is relevant here? My impression was that that code is for qemu user mode where you give qemu a binary and it emulates it by dynamic translation to the host architecture. In the system emulation mode (where you have a kernel running from a disk image), I don't think that this code runs. In the system emulator, qemu never touches your binary directly.

[langston-barrett]

After a short discussion on Mattermost we confirmed that the QEMU user-mode code might be the point of failure, because what we're seeing is that Linux is calculating the correct value under full-system emulation, but the binary is getting the wrong value under user-mode emulation. A little more digging is needed, then we'll have to see if we can write some code that produces program headers that can run both in QEMU user-mode and in full-system mode, or if we'll be reduced to always testing via full-system emulation.

[langston-barrett]

To confirm that this really is caused by a discrepancy between QEMU user-mode and system-mode, I ran a refurbished binary with an infinite loop at the end of main on a Linux kernel in full-system emulation to be sure that execution got there. It did! So now we need to:

1. Start testing with QEMU full-system emulation, or
2. Find the bug in QEMU's PHDR calculation and
   a) Work around it, or
   b) Fix it and use a bleeding edge version of QEMU in our tests

These all seem reasonably high-effort, but 2a has the potential of being the lowest effort, so I'll start there.

[langston-barrett]

Here's a QEMU bug report, just in case some kind soul comes along and fixes the issue quickly: https://bugs.launchpad.net/qemu/+bug/1885332

[langston-barrett]

So it looks like QEMU is calculating

AT_PHDR = min_i(phdr[i].vaddr - phdr[i].offset) + exec->phoff

where min_i is the minimum over all indices i of LOAD segments. For the refurbished binary with the following LOAD segments,

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  LOAD           0x0a3000 0x00900000 0x00900000 0x00160 0x00160 R   0x1000
  LOAD           0x000000 0x00010000 0x00010000 0x65de8 0x65de8 R E 0x10000
  LOAD           0x066b7c 0x00086b7c 0x00086b7c 0x02384 0x02384 RW  0x10000
  LOAD           0x07e000 0x00089000 0x00089000 0x03f44 0x03f44 R E 0x1000
  LOAD           0x098000 0x00030000 0x00030000 0x01000 0x01000 RW  0x1000

This yields

AT_PHDR = (0x00089000 - 0x07e000) + 0x0a3000 = 0xb000 + 0x0a3000 = 0xae000

as expected.

If we set this equal to the kernel's calculation, we can generate the constraint we would have to satisfy to work around this bug:

(elf_ppnt->p_vaddr - elf_ppnt->p_offset) + exec->e_phoff =
  min_i(phdr[i].vaddr - phdr[i].offset) + exec->phoff

=>

elf_ppnt->p_vaddr - elf_ppnt->p_offset = min_i(phdr[i].vaddr - phdr[i].offset)

In English: The virtual address of the first LOAD segment minus its offset must be the minimal difference between any LOAD segment's address and offset.