base address for shared libs

Vasiliy,

At least on rhel5/openvz kernels, 32-bit processes get their shared libs loaded at different kinds of addresses on i686 vs. x86_64 kernels.

Here's an example:

32-bit kernel and userland (OpenVZ container):

$ ldd /bin/ls
        librt.so.1 => /lib/librt.so.1 (0x00a99000)
        libtermcap.so.2 => /lib/libtermcap.so.2 (0x00c1a000)
        libc.so.6 => /lib/libc.so.6 (0x0014d000)
        libpthread.so.0 => /lib/libpthread.so.0 (0x00617000)
        /lib/ld-linux.so.2 (0x0012e000)

64-bit kernel, 32-bit userland (OpenVZ container):

$ ldd /bin/ls
        librt.so.1 => /lib/librt.so.1 (0xb7fcf000)
        libtermcap.so.2 => /lib/libtermcap.so.2 (0xb7fca000)
        libc.so.6 => /lib/libc.so.6 (0xb7eae000)
        libpthread.so.0 => /lib/libpthread.so.0 (0xb7e5b000)
        /lib/ld-linux.so.2 (0xb7fe6000)

Notice how the 32-bit kernel produces addresses that are safer against attacks via C strings (contain NULs). This is the approach I used in -ow patches (using 0x00110000 as the base address, considering vm86 needs for the first 1 MB + 64 KB). I'd like 64-bit kernels to do the same when running 32-bit binaries.

Can you please look into this and likely fix it for mainline, as well as for rhel6/openvz when we're ready to move to those kernels? A fix for rhel5/openvz would also be welcome if it's easy to do.

Thanks,

Alexander

Solar,

[...]

I'll look into it. However, I don't know whether upstream is OK with force zeroing high order byte of libs address and artificially limiting effective task's vm size. If not, it's probably should be made configurable via kernel.randomize_va_space sysctl.

Thanks,

Vasiliy

Vasiliy, all -

I think you misunderstood me. I don't suggest forcing the high order byte to be zero; I merely suggest that the starting address should be 0x00110000. If the combined size of shared libs plus the random offset exceed 15 MB - 64 KB, then some addresses won't have their high order byte at NUL, and that's life. I think this is what happens on i686 kernels now, and I'd like the same to be happening with x86_64 kernels running 32-bit programs.

I think something like 8 MB may be used for randomization (11 bits at 4 KB page size), which leaves almost 7 MB for shared libs until we no longer have NULs on some of their addresses. So programs with relatively few shared libs will benefit not only from randomization, but also from the NULs.

A drawback is that we'd be unnecessarily limiting the amount of randomization for programs that have lots of shared libs (way beyond 7 MB).

Or maybe we should use 4 MB for randomization (10 bits), leaving almost 11 MB for NUL-protected shared libs.

Oh, when vm86 is disallowed, I think we can start at mmap_min_addr, which gives us an extra megabyte (if mmap_min_addr is relatively low, like 96 KB, which is what we use on Owl). Similarly, when mmap_min_addr is not 0 and we're not running with CAP_SYS_RAWIO, perhaps we can start at mmap_min_addr because some low addresses would not be available to the process anyway (even if it wanted to use them to run DOS).

I'd appreciate comments and other opinions on all of the above.

What does PaX do here?

Thanks,

Alexander

Solar,

Ah, sure. Best effort vs. enforcement.

BTW, vm86 support is not even compiled on x86-64, even for x86-32 compatibility:

config VM86

	bool "Enable VM86 support" if EXPERT
	default y
	depends on X86_32

I didn't hear PaX does some NUL protection of lib addresses. I'll look into this.

Thanks,

Vasiliy

Solar,

Spender's reaction:

"The PaX position on the null bytes in mmap addresses is: the tradeoff between stopping certain vulns involving string functions and having low entropy for every other vuln type, and having the same high entropy for all types is weighed in favor of the latter."

Vasiliy

Solar,

The problem with ASCII-armor is that it contradicts good ALSR entropy. E.g. with 12 bits of entropy the maximum library size to fit in low 16 MB is zero bytes.

PaX has 16 bits of entropy, so ASCII-armor would only hurt entropy.

Ubuntu (and most of distros) has 12 bits. Kees says it makes sense to enable ASCII-armor for exec-shield only, as e-s already has very poor entropy.

Upstream has 8 bits for some reason, but AFAICS every distro increase the limit.

It makes sense to have e.g. 10 bits of entropy for 32-bit environments, but it would help only for tiny programs (hopefully, most of Owl programs). It would not work for any python/GUI/Java, Apache with many modules, TomCat, etc.

pipacs' position is that exploitation of C-string buffer overflows is rather rare nowadays, and heap overflows, buffer overflows, math miscalculation, etc. are much more often => C-string buffer overflow is not something which worth specific protection.

IMO it makes sense for Owl to have e.g. 10 bits of entropy for libs and use ASCII-armor. But it makes very little sense for upstream. Or even use 16 bits as PaX does and don't use ASCII-armor at all. ASCII-armor has rather limited usage - prevention of ret2libc via exploitation of C-string buffer overflows. But it is already included in ASLR, which does much more. Probably we should concentrate on more generic things, like ASLR?

Solar, what do you think?

Thanks,

Vasiliy Kulikov
http://www.openwall.com - bringing security into open computing environments

Vasiliy,

Thank you for conducting and summarizing this research. It helps. Most of the things I was aware of, but a few I was not (specific entropy sizes of different kernels).

Yes, so we have to choose between 10 and 11.

Yes, there's a tradeoff here.

For programs with many/large libs, we would not get ASCII-armor for some of the libs, but we would still have our 10 bits of ASLR. So we'd lose at the tradeoff - having sold some entropy, but having received only partial ASCII-armor - but we would not completely leave those programs unprotected.

Arguably, in those large-app cases mostly remote attacks are relevant, and for them 10 bits is already somewhat difficult. It is not obvious whether there's a lot of difference between 10 and 16 bits for them or not. If they're crashing from the first attempt or otherwise make the attack easy to notice, then 10 bits may be enough. If they don't crash and don't show any misbehavior, nor logging, then 16 may not be enough.

Also, 16 bits means that libs are scattered over a 256 MB range, which reduces the maximum continuous allocation size accordingly. I think many (upstream, RHEL) would find this cost prohibitive and would go for less entropy anyway.

Arguably, ASCII-armor is more effective than entropy against some local attacks. 16 bits is easy to search locally anyway (well, not exactly "search 16 bits" - rather, you have a 63% chance of success in 65536 tries, but it's good enough for our discussion). However, if you have no read access to the program binary (say, mode 4711), but you do to the libraries (say, mode 755), then ret2libc may be the most reliable attack to use.

I do feel that overflows via C strings became relatively less common, yet they're still of some relevance.

Blocking further attempts to run a program binary after SIGSEGV or not doing it is also part of the tradeoff. With this in place, local attacks on ASLR may become ineffective - however, 10 bits would likely be enough then.

I think it makes sense for upstream because we have little chance to get upstream to accept higher entropy (lowering the maximum continuous allocation size).

I think it'd be great to have this as an option. In fact, the code could simply try to do ASCII-armor, but also allow one to configure more than 11 bits of entropy, in which case the ASCII-armor would be usually ineffective. That is, start at max(0x00110000, mmap_min_addr), but add to this a random page-aligned offset in a configurable range (configurable as number of entropy bits). When the setting is 11 or less (and mmap_min_addr is not set unusually high), ASCII-armor is guaranteed for libs not exceeding a certain size. When the setting is 12 to 14, ASCII-armor is not guaranteed in any case (but may happen in some cases nevertheless). For 15+, you have to use a different starting address or use two ranges (if the random number has no "1" bits beyond bits 0-13, then use the low range, otherwise use a high range).

What specific address range(s) does PaX use?

Yes.

Is it? Not exactly. Just invoke the binary thousands of time, and you have a good chance to hit the right libc code.

I'd like us to support both. Sounds easy enough to do.

Thanks again,

Alexander

Vasiliy,

I think this should be configurable in the 0 to 19 bits range. The default might be 15, which would mostly fit under the starting address of non-PIE binaries, taking up only a megabyte above them (you'd need to use two ranges - 127 MB and 1 MB). So the cost in reduction of maximum continuous allocation size would be negligible for non-PIE (just 1 MB).

The starting address of 0x00110000 could also be configurable. When dosemu and Win16 apps in Wine are not needed (are these the users of this range?), you could simply start at mmap_min_addr and fit all 128 MB before the binary start.

Alexander

Solar,

On Fri, Aug 12, 2011 at 08:21 +0400, Solar Designer wrote:
[...]

[...]

Yes, I agree this is a trade-off and depends on program needs (address space size) and security threads.

However, some upstream guys don't agree it should be configurable:

https://lkml.org/lkml/2006/5/19/219

https://lkml.org/lkml/2006/5/22/207:

"Because if it is configurable, someone _will_ configure it wrong, and then ask us why it does not work."

And similar.

Probably it worth trying to bring up the discussion of configurable ASLR entropy again - the code to configure it is simple anyway. However, I expect one nasty answer: "everybody should use x86-64 for good ASLR and other things, for x86-32 it is bad anyway, so don't bother to fix things broken by design."

So, to summarize:

For upstream we want to start mmap addresses allocation from 0x1100000, bottom up. Probably, make entropy configurable.

For Owl we want to make entropy size configurable. Depending on the entropy, use ASCII-armor or fallback to the default allocator instantly.

Correct?

Vasiliy

This is easily dealt with by limiting the allowable range to "correct" values. Say, instead of 0 to 19 use 9 to 18 or 10 to 16. Then we'll need to patch only the allowable range and not any code in Owl.

Yes, please - with a patch.

You may simply reply that you disagree. Maybe someone else will as well.

You meant from 0x110000 (one zero less).

Huh? I don't think you used the right words here.

Yes.

Not exactly. Both for upstream and for Owl, when the entropy size exceeds what we can provide ASCII-armor for, we start at 0x110000 anyway, but we just happen to go to non-armored addresses if we get such random numbers. For example, if we're configured to use 12 bits and our binary uses just one library of 3 MB in size, then there's an approx. 75% chance that on a given invocation of the binary we have ASCII armor for the library anyway. This is just not guaranteed.

Alexander

There are 2 allocation logics, top down and bottom up:

http://lxr.free-electrons.com/source/mm/mmap.c#L1372

http://lxr.free-electrons.com/source/mm/mmap.c#L1444

If use top down logic (start from 0x01000000 as the end of the library) then some gap at 0x00110000 will be wasted. With bottom up logic I'll simply have the last library partly being in ASCII-armor zone, the end of it will be located after 0x01000000, but no waste of vm space.

Or you mean anything else?

OK. However, I don't see much sense in sizes between 10 and 16. If we want to use ASCII-armor or warried about vm-hungry apps, then use 10 bits. If not, use all power of ASLR.

But if use distros with their default 12 bits in containers, it makes sense to protect them with a probabilistic measure, though.

Thanks,

Vasiliy

You're right. I just didn't realize the words "bottom up" were used in kernel source to mean that.

Why not use 14 in such cases, which still fits in the below-binary range and thus does not reduce the maximum continuous allocation size?

I don't understand what you mean here. The distros' default 12 bits - are they patched into those distros' kernels? If so, they do not apply to use in containers (where only userlands are used).

Alexander

Oh, sure. Please ignore this statement :-)

Vasiliy

Solar,

Looking into RHEL6 kernel:

    void arch_pick_mmap_layout(struct mm_struct *mm)
    {
        ...
            if (!(current->personality & READ_IMPLIES_EXEC)
                && mmap_is_ia32())
                mm->get_unmapped_exec_area = arch_get_unmapped_exec_area;
        ...
    }

    #define SHLIB_BASE	0x00110000

    unsigned long
    arch_get_unmapped_exec_area(struct file *filp, unsigned long addr0,
            unsigned long len0, unsigned long pgoff, unsigned long flags)
    {
        ...
        if (!addr)
            addr = !should_randomize() ? SHLIB_BASE :
                randomize_range(SHLIB_BASE, 0x01000000, len);
        ...
    }

Looks like it is considered as a way to easily mmap libraries in CS limited area by exec-shield, and not as a C-string barrier.

The comment says the common bottom-up doesn't support randomization:

/*
* Bottom-up (legacy) layout on X86_32 did not support randomization, X86_64
* does, but not when emulating X86_32
*/

So, IMO the bottom-up layout allocator should be patched.

Thanks,

Vasiliy

Solar,

This is a patch, which should solve the problem. Note that the default base address allocation policy for the mainline is top-down, so 0x00110000 was not considered even in x86-32. Now it should work for both 32-bit systems and 32-bit tasks in 64-bit systems.

I used some code from Exec Shield part of RHEL6 patch.

Shortly:

By default the kernel calculates a random gap size (8 bits of entropy for 32 bits and 28 for 64 bits) and skips this size from the top addresses. Then it merely fills the address space (top-down) with libraries without any gaps between the libraries.

In Exec Shield the base address for each library is a random value from 0x00110000-0x01000000. If it fails, a simple bottom-up algo is used, whitout any gaps AND any random. IMO it is weird as for some specific library sequences the base addresses are somewhat guessable (I haven't got strict numbers, though).

So, I've implemented an analog of upstream's top-down allocation algo, but bottom-up, with the same gap (with the same entropy).

index 1dab519..20d6085 100644
@@ -131,6 +131,10 @@ void arch_pick_mmap_layout(struct mm_struct *mm)
 	} else {
 		mm->mmap_base = mmap_base();
 		mm->get_unmapped_area = arch_get_unmapped_area_topdown;
+		if (mmap_is_ia32()) {
+			mm->get_unmapped_exec_area = arch_get_unmapped_exec_area;
+			mm->lib_mmap_base = 0x00110000 + mmap_rnd();
+		}
 		mm->unmap_area = arch_unmap_area_topdown;
 	}
 }

index 027935c..5f2dca9 100644
@@ -225,9 +225,13 @@ struct mm_struct {
 	unsigned long (*get_unmapped_area) (struct file *filp,
 				unsigned long addr, unsigned long len,
 				unsigned long pgoff, unsigned long flags);
+	unsigned long (*get_unmapped_exec_area) (struct file *filp,
+				unsigned long addr, unsigned long len,
+				unsigned long pgoff, unsigned long flags);
 	void (*unmap_area) (struct mm_struct *mm, unsigned long addr);
 #endif
 	unsigned long mmap_base;		/* base of mmap area */
+	unsigned long lib_mmap_base;		/* base of mmap libraries area (includes zero symbol) */
 	unsigned long task_size;		/* size of task vm space */
 	unsigned long cached_hole_size; 	/* if non-zero, the largest hole below free_area_cache */
 	unsigned long free_area_cache;		/* first hole of size cached_hole_size or larger */

index f024c63..8feaba9 100644
@@ -394,6 +394,9 @@ arch_get_unmapped_area_topdown(struct file *filp, unsigned long addr,
 			  unsigned long flags);
 extern void arch_unmap_area(struct mm_struct *, unsigned long);
 extern void arch_unmap_area_topdown(struct mm_struct *, unsigned long);
+extern unsigned long
+arch_get_unmapped_exec_area(struct file *, unsigned long,
+		unsigned long, unsigned long, unsigned long);
 #else
 static inline void arch_pick_mmap_layout(struct mm_struct *mm) {}
 #endif

--

Solar,

One note: if watch for ldd output, approx. every 20th output shows that some library gets 0xffAABBCC address. If watch for the real task's maps (via /proc/pid/maps), all libs are located before 0x01AABBCC.

I don't know for sure how ldd allocated memory, but I suspect it wastes too much 0x00AABBCC addresses, so sometimes there is no place for them.

So, I don't think it is an issue.

Thanks,

Vasiliy Kulikov
http://www.openwall.com - bringing security into open computing environments