revert PIE randomization?

revert PIE randomization?

[Hugh Dickins]

There's a lot of gaps in my understanding, but I think 2.6.20-rc's
59287c0913cc9a6c75712a775f6c1c1ef418ef3b (randomize PIE binaries)
needs to be reverted for now.

Running any 2.6.20-rc kernel on i386 openSUSE 10.2, my kernel builds
occasionally fail with an ld.so error when building some .o or .ko
(then succeed when restarted in the same tree immediately after): e.g. 

  LD [M]  fs/vfat/vfat.o
Inconsistency detected by ld.so: rtld.c: 1217: dl_main:
 Assertion `_rtld_local._dl_rtld_map.l_libname' failed!
make[2]: *** [fs/vfat/vfat.o] Error 127

I guessed a TLB problem, but no, bisection points to the random PIE
patch.  I've no idea how it arrives at the particular failure seen,
but the code does look wrong to me:

		vaddr = elf_ppnt->p_vaddr;
		if (loc->elf_ex.e_type == ET_EXEC || load_addr_set) {
			elf_flags |= MAP_FIXED;
		} else if (loc->elf_ex.e_type == ET_DYN) {
			/* Try and get dynamic programs out of the way of the
			 * default mmap base, as well as whatever program they
			 * might try to exec.  This is because the brk will
			 * follow the loader, and is not movable.  */
			if (current->flags & PF_RANDOMIZE)
				load_bias = randomize_range(0x10000,
							    ELF_ET_DYN_BASE,
							    0);
			else
				load_bias = ELF_ET_DYN_BASE;
			load_bias = ELF_PAGESTART(load_bias - vaddr);
		}
		error = elf_map(bprm->file, load_bias + vaddr, elf_ppnt,
				elf_prot, elf_flags);

Isn't that randomization, anywhere from 0x10000 to ELF_ET_DYN_BASE,
sure to place the ET_DYN from time to time just where the comment says
it's trying to avoid?  I assume that somehow results in the error reported.

No problem yet seen on x86_64 or ppc64, I suppose because the address
space is so much larger.  No problem seen before openSUSE 10.2, while
running 2.6.19-rc-mm which contained the patch: hmm, the oS /bin/bash
is a "shared object" rather than the familiar "executable", maybe that
has something to do with it.  No problem seen if I revert that patch;
nor if I add on the patch below, which does a much more limited
randomization - but my guess is others will improve upon it.

(I probably have my priorities wrong, going up from ELF_ET_DYN_BASE
because I don't like calling the top of a range _BASE: with stack
coming randomly down on most arches, maybe it'd better go below.

And I notice that Andi added a personality & ADDR_NO_RANDOMIZE check
into randomize_stack_top: I cannot see why that's necessary there,
but if it is, then should the ET_DYN case add it too?)

Hugh

--- 2.6.20-rc3/fs/binfmt_elf.c	2007-01-01 10:30:40.000000000 +0000
+++ linux/fs/binfmt_elf.c	2007-01-05 17:01:31.000000000 +0000
@@ -509,6 +509,12 @@ out:
 #define STACK_RND_MASK 0x7ff		/* with 4K pages 8MB of VA */
 #endif
 
+/*
+ * Though STACK_RND_MASK was introduced to govern randomizing the stack,
+ * it should also be appropriate to govern randomizing the ET_DYN base.
+ */
+#define ELF_ET_DYN_HIBASE (ELF_ET_DYN_BASE + ((STACK_RND_MASK+1)<<PAGE_SHIFT))
+
 static unsigned long randomize_stack_top(unsigned long stack_top)
 {
 	unsigned int random_variable = 0;
@@ -855,9 +861,8 @@ static int load_elf_binary(struct linux_
 			 * might try to exec.  This is because the brk will
 			 * follow the loader, and is not movable.  */
 			if (current->flags & PF_RANDOMIZE)
-				load_bias = randomize_range(0x10000,
-							    ELF_ET_DYN_BASE,
-							    0);
+				load_bias = randomize_range(ELF_ET_DYN_BASE,
+							ELF_ET_DYN_HIBASE, 0);
 			else
 				load_bias = ELF_ET_DYN_BASE;
 			load_bias = ELF_PAGESTART(load_bias - vaddr);

Re: revert PIE randomization?

[Linus Torvalds]

On Sat, 6 Jan 2007, Hugh Dickins wrote:
> 
> Isn't that randomization, anywhere from 0x10000 to ELF_ET_DYN_BASE,
> sure to place the ET_DYN from time to time just where the comment says
> it's trying to avoid?  I assume that somehow results in the error reported.

Hmm.. It's certainly the case that it would appear that the randomization 
might put the binary just under the heap, and cause conflicts with brk 
and the mmap heap.

You're right. I'm inclined to just revert it, modulo some comments from 
others. Marcus?

		Linus

Re: revert PIE randomization?

[Marcus Meissner]

On Sat, Jan 06, 2007 at 01:04:02PM -0800, Linus Torvalds wrote:
> 
> 
> On Sat, 6 Jan 2007, Hugh Dickins wrote:
> > 
> > Isn't that randomization, anywhere from 0x10000 to ELF_ET_DYN_BASE,
> > sure to place the ET_DYN from time to time just where the comment says
> > it's trying to avoid?  I assume that somehow results in the error reported.
> 
> Hmm.. It's certainly the case that it would appear that the randomization 
> might put the binary just under the heap, and cause conflicts with brk 
> and the mmap heap.
> 
> You're right. I'm inclined to just revert it, modulo some comments from 
> others. Marcus?

After thinking about this, yes.

I would rather have a working range used here (perhaps like Hugh suggested),
but feel free to revert the original patch if you are not confident with it.

Ciao, Marcus

Re: revert PIE randomization?

[Ingo Molnar]

* Marcus Meissner <meissner@suse.de> wrote:

> > You're right. I'm inclined to just revert it, modulo some comments 
> > from others. Marcus?
> 
> After thinking about this, yes.
> 
> I would rather have a working range used here (perhaps like Hugh 
> suggested), but feel free to revert the original patch if you are not 
> confident with it.

i'm wondering why you had to try to reinvent the wheel, instead of 
picking up exec-shield's remaining bits of randomization implementation 
from Fedora, which was tested for a long time and achieves PIE 
randomization and more?

	Ingo

Re: revert PIE randomization?

[Marcus Meissner]

On Sat, Jan 06, 2007 at 10:45:05PM +0100, Ingo Molnar wrote:
> 
> * Marcus Meissner <meissner@suse.de> wrote:
> 
> > > You're right. I'm inclined to just revert it, modulo some comments 
> > > from others. Marcus?
> > 
> > After thinking about this, yes.
> > 
> > I would rather have a working range used here (perhaps like Hugh 
> > suggested), but feel free to revert the original patch if you are not 
> > confident with it.
> 
> i'm wondering why you had to try to reinvent the wheel, instead of 
> picking up exec-shield's remaining bits of randomization implementation 
> from Fedora, which was tested for a long time and achieves PIE 
> randomization and more?

Because it is i386 only last time I checked.

And it requires relaying out the heap (which you did only for i386), with
architecture specific code, which I was too afraid to touch.

Ciao, Marcus

Re: revert PIE randomization?

[David Woodhouse]

On Sat, 2007-01-06 at 20:11 +0000, Hugh Dickins wrote:
> And I notice that Andi added a personality & ADDR_NO_RANDOMIZE check
> into randomize_stack_top: I cannot see why that's necessary there,
> but if it is, then should the ET_DYN case add it too?)

While I think of it... it seems that ADDR_NO_RANDOMIZE isn't "inherited"
across exec of 32-bit binaries on x86_64 or ppc64. The personality flags
get wiped out when we detect a 32-bit ELF executable and set the
personality to PER_LINUX32.

This causes suboptimal behaviour from userspace code which checks
whether it can set ADDR_NO_RANDOMIZE with a sys_personality() call, and
if so re-execs itself. Run on x86_64 or ppc64, these go into an endless
loop because it always gets cleared in the exec.

I've seen such code in two places recently (Macaulay2 and sbcl, iirc).

-- 
dwmw2

Re: revert PIE randomization?

[Kees Cook]

Hi Hugh,

Hugh Dickins said:
> Inconsistency detected by ld.so: rtld.c: 1217: dl_main:
>  Assertion `_rtld_local._dl_rtld_map.l_libname' failed!

I'm trying to reproduce the problem you saw (so that I can then test 
your proposed fix).  However, I haven't had any luck.  I've got a 
pie-compiled version of bash, and I've been running it in a loop for a 
while now with the original randomization patch.  (I can clearly see the 
base address bouncing around.)

I'm at just over 10 million exec's, and I haven't hit the problem.  :(

Do you have any clues on how to trigger this more reliably?

Also, does anyone have any thoughts on why x86 uses a ELF_ET_DYN_BASE 
below the libraries, where as x86_64 uses one above them?  From this, 
I'd expect x86_64 to collide with the libraries at times.  I need more 
help understanding the memory layouts, I guess.  :)

Thanks,

-- 
Kees Cook                                            @outflux.net

Re: revert PIE randomization?

[Hugh Dickins]

On Wed, 21 Mar 2007, Kees Cook wrote:
> Hugh Dickins said:
> > Inconsistency detected by ld.so: rtld.c: 1217: dl_main:
> >  Assertion `_rtld_local._dl_rtld_map.l_libname' failed!
> 
> I'm trying to reproduce the problem you saw (so that I can then test 
> your proposed fix).  However, I haven't had any luck.  I've got a 
> pie-compiled version of bash, and I've been running it in a loop for a 
> while now with the original randomization patch.  (I can clearly see the 
> base address bouncing around.)
> 
> I'm at just over 10 million exec's, and I haven't hit the problem.  :(
> 
> Do you have any clues on how to trigger this more reliably?

It was in doing kernel builds that I hit it, nothing special: an
overnight cycle of kernel building would collapse in a few hours.
openSUSE 10.2.

If that doesn't reproduce it for you, let me know and I'll try again
with the original patch, to reproduce it here: maybe something else
has changed in 2.6.21-rc to affect it.

> 
> Also, does anyone have any thoughts on why x86 uses a ELF_ET_DYN_BASE 
> below the libraries, where as x86_64 uses one above them?  From this, 
> I'd expect x86_64 to collide with the libraries at times.  I need more 
> help understanding the memory layouts, I guess.  :)

Andi would tell definitively, but I guess it's merely that with so
much more address space to play with, x86_64 can divide up that space
more satisfactorily.

But don't be misled: try "ulimit -s unlimited" and I expect you'll
find i386 allocating mmap addresses (hence libraries) from the
opposite end, below ELF_ET_DYN_BASE.

Hugh

Re: revert PIE randomization?

[Kees Cook]

On Wed, Mar 21, 2007 at 08:01:50PM +0000, Hugh Dickins wrote:
> It was in doing kernel builds that I hit it, nothing special: an
> overnight cycle of kernel building would collapse in a few hours.
> openSUSE 10.2.

I wonder it was the combination of the base addr randomization patch and 
something specific to the openSuSE loader that was sparking the 
failures?  I ran about 22 million execs on Ubuntu Feisty (patched to 
re-include the base addr randomization), with a PIE bash, and never saw 
it.  Hmpf.

> Andi would tell definitively, but I guess it's merely that with so
> much more address space to play with, x86_64 can divide up that space
> more satisfactorily.
> 
> But don't be misled: try "ulimit -s unlimited" and I expect you'll
> find i386 allocating mmap addresses (hence libraries) from the
> opposite end, below ELF_ET_DYN_BASE.

Is there any explicitly documented per-arch "here is the memory layout 
of a process"?  I haven't been able to find anything like this.  I 
suspect it would be a good reference to have; so if no one has any 
hints, I'll try to get something written up.

-- 
Kees Cook                                            @outflux.net