| Message ID | 1469557346-5534-2-git-send-email-william.c.roberts@intel.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
Hi William! On Tue, Jul 26, 2016 at 11:22:26AM -0700, william.c.roberts@intel.com wrote: > From: William Roberts <william.c.roberts@intel.com> > > This patch introduces the ability randomize mmap locations where the > address is not requested, for instance when ld is allocating pages for > shared libraries. It chooses to randomize based on the current > personality for ASLR. Now I see how you found the randomize_range() fix. :-P > Currently, allocations are done sequentially within unmapped address > space gaps. This may happen top down or bottom up depending on scheme. > > For instance these mmap calls produce contiguous mappings: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40026000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40027000 > > Note no gap between. > > After patches: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x400b4000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40055000 > > Note gap between. > > Using the test program mentioned here, that allocates fixed sized blocks > till exhaustion: https://www.linux-mips.org/archives/linux-mips/2011-05/msg00252.html, > no difference was noticed in the number of allocations. Most varied from > run to run, but were always within a few allocations of one another > between patched and un-patched runs. Did you test this with different allocation sizes? > Performance Measurements: > Using strace with -T option and filtering for mmap on the program > ls shows a slowdown of approximate 3.7% I think it would be helpful to show the effect on the resulting object code. > Signed-off-by: William Roberts <william.c.roberts@intel.com> > --- > mm/mmap.c | 24 ++++++++++++++++++++++++ > 1 file changed, 24 insertions(+) > > diff --git a/mm/mmap.c b/mm/mmap.c > index de2c176..7891272 100644 > --- a/mm/mmap.c > +++ b/mm/mmap.c > @@ -43,6 +43,7 @@ > #include <linux/userfaultfd_k.h> > #include <linux/moduleparam.h> > #include <linux/pkeys.h> > +#include <linux/random.h> > > #include <asm/uaccess.h> > #include <asm/cacheflush.h> > @@ -1582,6 +1583,24 @@ unacct_error: > return error; > } > > +/* > + * Generate a random address within a range. This differs from randomize_addr() by randomizing > + * on len sized chunks. This helps prevent fragmentation of the virtual memory map. > + */ > +static unsigned long randomize_mmap(unsigned long start, unsigned long end, unsigned long len) > +{ > + unsigned long slots; > + > + if ((current->personality & ADDR_NO_RANDOMIZE) || !randomize_va_space) > + return 0; Couldn't we avoid checking this every time? Say, by assigning a function pointer during init? > + > + slots = (end - start)/len; > + if (!slots) > + return 0; > + > + return PAGE_ALIGN(start + ((get_random_long() % slots) * len)); > +} > + Personally, I'd prefer this function noop out based on a configuration option. > unsigned long unmapped_area(struct vm_unmapped_area_info *info) > { > /* > @@ -1676,6 +1695,8 @@ found: > if (gap_start < info->low_limit) > gap_start = info->low_limit; > > + gap_start = randomize_mmap(gap_start, gap_end, length) ? : gap_start; > + > /* Adjust gap address to the desired alignment */ > gap_start += (info->align_offset - gap_start) & info->align_mask; > > @@ -1775,6 +1796,9 @@ found: > found_highest: > /* Compute highest gap address at the desired alignment */ > gap_end -= info->length; > + > + gap_end = randomize_mmap(gap_start, gap_end, length) ? : gap_end; > + > gap_end -= (gap_end - info->align_offset) & info->align_mask; > > VM_BUG_ON(gap_end < info->low_limit); I'll have to dig into the mm code more before I can comment intelligently on this. thx, Jason.
> -----Original Message----- > From: Jason Cooper [mailto:jason@lakedaemon.net] > Sent: Tuesday, July 26, 2016 1:03 PM > To: Roberts, William C <william.c.roberts@intel.com> > Cc: linux-mm@vger.kernel.org; linux-kernel@vger.kernel.org; kernel- > hardening@lists.openwall.com; akpm@linux-foundation.org; > keescook@chromium.org; gregkh@linuxfoundation.org; nnk@google.com; > jeffv@google.com; salyzyn@android.com; dcashman@android.com > Subject: Re: [PATCH] [RFC] Introduce mmap randomization > > Hi William! > > On Tue, Jul 26, 2016 at 11:22:26AM -0700, william.c.roberts@intel.com wrote: > > From: William Roberts <william.c.roberts@intel.com> > > > > This patch introduces the ability randomize mmap locations where the > > address is not requested, for instance when ld is allocating pages for > > shared libraries. It chooses to randomize based on the current > > personality for ASLR. > > Now I see how you found the randomize_range() fix. :-P > > > Currently, allocations are done sequentially within unmapped address > > space gaps. This may happen top down or bottom up depending on scheme. > > > > For instance these mmap calls produce contiguous mappings: > > int size = getpagesize(); > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40026000 > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40027000 > > > > Note no gap between. > > > > After patches: > > int size = getpagesize(); > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x400b4000 > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40055000 > > > > Note gap between. > > > > Using the test program mentioned here, that allocates fixed sized > > blocks till exhaustion: > > https://www.linux-mips.org/archives/linux-mips/2011-05/msg00252.html, > > no difference was noticed in the number of allocations. Most varied > > from run to run, but were always within a few allocations of one > > another between patched and un-patched runs. > > Did you test this with different allocation sizes? No I didn't it. I wasn't sure the best way to test this, any ideas? > > > Performance Measurements: > > Using strace with -T option and filtering for mmap on the program ls > > shows a slowdown of approximate 3.7% > > I think it would be helpful to show the effect on the resulting object code. Do you mean the maps of the process? I have some captures for whoopsie on my Ubuntu system I can share. One thing I didn't make clear in my commit message is why this is good. Right now, if you know An address within in a process, you know all offsets done with mmap(). For instance, an offset To libX can yield libY by adding/subtracting an offset. This is meant to make rops a bit harder, or In general any mapping offset mmore difficult to find/guess. > > > Signed-off-by: William Roberts <william.c.roberts@intel.com> > > --- > > mm/mmap.c | 24 ++++++++++++++++++++++++ > > 1 file changed, 24 insertions(+) > > > > diff --git a/mm/mmap.c b/mm/mmap.c > > index de2c176..7891272 100644 > > --- a/mm/mmap.c > > +++ b/mm/mmap.c > > @@ -43,6 +43,7 @@ > > #include <linux/userfaultfd_k.h> > > #include <linux/moduleparam.h> > > #include <linux/pkeys.h> > > +#include <linux/random.h> > > > > #include <asm/uaccess.h> > > #include <asm/cacheflush.h> > > @@ -1582,6 +1583,24 @@ unacct_error: > > return error; > > } > > > > +/* > > + * Generate a random address within a range. This differs from > > +randomize_addr() by randomizing > > + * on len sized chunks. This helps prevent fragmentation of the virtual > memory map. > > + */ > > +static unsigned long randomize_mmap(unsigned long start, unsigned > > +long end, unsigned long len) { > > + unsigned long slots; > > + > > + if ((current->personality & ADDR_NO_RANDOMIZE) || > !randomize_va_space) > > + return 0; > > Couldn't we avoid checking this every time? Say, by assigning a function pointer > during init? Yeah that could be done. I just copied the way others checked elsewhere in the kernel :-P > > > + > > + slots = (end - start)/len; > > + if (!slots) > > + return 0; > > + > > + return PAGE_ALIGN(start + ((get_random_long() % slots) * len)); } > > + > > Personally, I'd prefer this function noop out based on a configuration option. Me too. > > > unsigned long unmapped_area(struct vm_unmapped_area_info *info) { > > /* > > @@ -1676,6 +1695,8 @@ found: > > if (gap_start < info->low_limit) > > gap_start = info->low_limit; > > > > + gap_start = randomize_mmap(gap_start, gap_end, length) ? : > > +gap_start; > > + > > /* Adjust gap address to the desired alignment */ > > gap_start += (info->align_offset - gap_start) & info->align_mask; > > > > @@ -1775,6 +1796,9 @@ found: > > found_highest: > > /* Compute highest gap address at the desired alignment */ > > gap_end -= info->length; > > + > > + gap_end = randomize_mmap(gap_start, gap_end, length) ? : gap_end; > > + > > gap_end -= (gap_end - info->align_offset) & info->align_mask; > > > > VM_BUG_ON(gap_end < info->low_limit); > > I'll have to dig into the mm code more before I can comment intelligently on this. > > thx, > > Jason.
On Tue, 2016-07-26 at 11:22 -0700, william.c.roberts@intel.com wrote: > From: William Roberts <william.c.roberts@intel.com> > > This patch introduces the ability randomize mmap locations where the > address is not requested, for instance when ld is allocating pages > for > shared libraries. It chooses to randomize based on the current > personality for ASLR. > > Currently, allocations are done sequentially within unmapped address > space gaps. This may happen top down or bottom up depending on > scheme. > > For instance these mmap calls produce contiguous mappings: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40026000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40027000 > > Note no gap between. > > After patches: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x400b4000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40055000 > > Note gap between. I suspect this randomization will be more useful for file mappings than for anonymous mappings. I don't know whether there are downsides to creating more anonymous VMAs than we have to, with malloc libraries that may perform various kinds of tricks with mmap for their own performance reasons. Does anyone have convincing reasons why mmap randomization should do both file and anon, or whether it should do just file mappings?
<snip> RESEND fixing mm-list email.... > > -----Original Message----- > > From: Jason Cooper [mailto:jason@lakedaemon.net] > > Sent: Tuesday, July 26, 2016 1:03 PM > > To: Roberts, William C <william.c.roberts@intel.com> > > Cc: linux-mm@vger.kernel.org; linux-kernel@vger.kernel.org; kernel- > > hardening@lists.openwall.com; akpm@linux-foundation.org; > > keescook@chromium.org; gregkh@linuxfoundation.org; nnk@google.com; > > jeffv@google.com; salyzyn@android.com; dcashman@android.com > > Subject: Re: [PATCH] [RFC] Introduce mmap randomization > > > > Hi William! > > > > On Tue, Jul 26, 2016 at 11:22:26AM -0700, william.c.roberts@intel.com wrote: > > > From: William Roberts <william.c.roberts@intel.com> > > > > > > This patch introduces the ability randomize mmap locations where the > > > address is not requested, for instance when ld is allocating pages > > > for shared libraries. It chooses to randomize based on the current > > > personality for ASLR. > > > > Now I see how you found the randomize_range() fix. :-P > > > > > Currently, allocations are done sequentially within unmapped address > > > space gaps. This may happen top down or bottom up depending on scheme. > > > > > > For instance these mmap calls produce contiguous mappings: > > > int size = getpagesize(); > > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x40026000 > > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x40027000 > > > > > > Note no gap between. > > > > > > After patches: > > > int size = getpagesize(); > > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x400b4000 > > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x40055000 > > > > > > Note gap between. > > > > > > Using the test program mentioned here, that allocates fixed sized > > > blocks till exhaustion: > > > https://www.linux-mips.org/archives/linux-mips/2011-05/msg00252.html > > > , no difference was noticed in the number of allocations. Most > > > varied from run to run, but were always within a few allocations of > > > one another between patched and un-patched runs. > > > > Did you test this with different allocation sizes? > > No I didn't it. I wasn't sure the best way to test this, any ideas? > > > > > > Performance Measurements: > > > Using strace with -T option and filtering for mmap on the program ls > > > shows a slowdown of approximate 3.7% > > > > I think it would be helpful to show the effect on the resulting object code. > > Do you mean the maps of the process? I have some captures for whoopsie on my > Ubuntu system I can share. > > One thing I didn't make clear in my commit message is why this is good. Right > now, if you know An address within in a process, you know all offsets done with > mmap(). For instance, an offset To libX can yield libY by adding/subtracting an > offset. This is meant to make rops a bit harder, or In general any mapping offset > mmore difficult to find/guess. > > > > > > Signed-off-by: William Roberts <william.c.roberts@intel.com> > > > --- > > > mm/mmap.c | 24 ++++++++++++++++++++++++ > > > 1 file changed, 24 insertions(+) > > > > > > diff --git a/mm/mmap.c b/mm/mmap.c > > > index de2c176..7891272 100644 > > > --- a/mm/mmap.c > > > +++ b/mm/mmap.c > > > @@ -43,6 +43,7 @@ > > > #include <linux/userfaultfd_k.h> > > > #include <linux/moduleparam.h> > > > #include <linux/pkeys.h> > > > +#include <linux/random.h> > > > > > > #include <asm/uaccess.h> > > > #include <asm/cacheflush.h> > > > @@ -1582,6 +1583,24 @@ unacct_error: > > > return error; > > > } > > > > > > +/* > > > + * Generate a random address within a range. This differs from > > > +randomize_addr() by randomizing > > > + * on len sized chunks. This helps prevent fragmentation of the > > > +virtual > > memory map. > > > + */ > > > +static unsigned long randomize_mmap(unsigned long start, unsigned > > > +long end, unsigned long len) { > > > + unsigned long slots; > > > + > > > + if ((current->personality & ADDR_NO_RANDOMIZE) || > > !randomize_va_space) > > > + return 0; > > > > Couldn't we avoid checking this every time? Say, by assigning a > > function pointer during init? > > Yeah that could be done. I just copied the way others checked elsewhere in the > kernel :-P > > > > > > + > > > + slots = (end - start)/len; > > > + if (!slots) > > > + return 0; > > > + > > > + return PAGE_ALIGN(start + ((get_random_long() % slots) * len)); } > > > + > > > > Personally, I'd prefer this function noop out based on a configuration option. > > Me too. > > > > > > unsigned long unmapped_area(struct vm_unmapped_area_info *info) { > > > /* > > > @@ -1676,6 +1695,8 @@ found: > > > if (gap_start < info->low_limit) > > > gap_start = info->low_limit; > > > > > > + gap_start = randomize_mmap(gap_start, gap_end, length) ? : > > > +gap_start; > > > + > > > /* Adjust gap address to the desired alignment */ > > > gap_start += (info->align_offset - gap_start) & info->align_mask; > > > > > > @@ -1775,6 +1796,9 @@ found: > > > found_highest: > > > /* Compute highest gap address at the desired alignment */ > > > gap_end -= info->length; > > > + > > > + gap_end = randomize_mmap(gap_start, gap_end, length) ? : gap_end; > > > + > > > gap_end -= (gap_end - info->align_offset) & info->align_mask; > > > > > > VM_BUG_ON(gap_end < info->low_limit); > > > > I'll have to dig into the mm code more before I can comment intelligently on > this. > > > > thx, > > > > Jason.
> -----Original Message----- > From: Rik van Riel [mailto:riel@redhat.com] > Sent: Tuesday, July 26, 2016 1:12 PM > To: kernel-hardening@lists.openwall.com; jason@lakedaemon.net; linux- > mm@vger.kernel.org; linux-kernel@vger.kernel.org; akpm@linux- > foundation.org > Cc: keescook@chromium.org; gregkh@linuxfoundation.org; nnk@google.com; > jeffv@google.com; salyzyn@android.com; dcashman@android.com; Roberts, > William C <william.c.roberts@intel.com> > Subject: Re: [kernel-hardening] [PATCH] [RFC] Introduce mmap > randomization > > On Tue, 2016-07-26 at 11:22 -0700, william.c.roberts@intel.com wrote: > > From: William Roberts <william.c.roberts@intel.com> > > > > This patch introduces the ability randomize mmap locations where the > > address is not requested, for instance when ld is allocating pages > > for shared libraries. It chooses to randomize based on the current > > personality for ASLR. > > > > Currently, allocations are done sequentially within unmapped address > > space gaps. This may happen top down or bottom up depending on scheme. > > > > For instance these mmap calls produce contiguous mappings: > > int size = getpagesize(); > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x40026000 > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x40027000 > > > > Note no gap between. > > > > After patches: > > int size = getpagesize(); > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x400b4000 > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > > 0x40055000 > > > > Note gap between. > > I suspect this randomization will be more useful for file mappings > than for anonymous mappings. > > I don't know whether there are downsides to creating more anonymous > VMAs than we have to, with malloc libraries that may perform various > kinds of tricks with mmap for their own performance reasons. > > Does anyone have convincing reasons why mmap randomization should do > both file and anon, or whether it should do just file mappings? Throwing this out there, but If you're mmap'ing buffers at known offsets in the program then folks know where to write/modify. Jason Cooper mentioned using a KConfig around this (amongst other things) which perhaps Controlling this at a better granularity would be beneficial. > > -- > All rights reversed
My apologies in advance if I misunderstand the purposes of this patch. IIUC, this patch adds a random gap between various mmap() mappings, with the goal of ensuring that both the mmap base address and gaps between pages are randomized. If that's the goal, please note that this behavior has caused significant performance problems to Android in the past. Specifically, random gaps between mmap()ed regions causes memory space fragmentation. After a program runs for a long time, the ability to find large contiguous blocks of memory becomes impossible, and mmap()s fail due to lack of a large enough address space. This isn't just a theoretical concern. Android actually hit this on kernels prior to http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=7dbaa466780a754154531b44c2086f6618cee3a8 . Before that patch, the gaps between mmap()ed pages were randomized. See the discussion at: http://lists.infradead.org/pipermail/linux-arm-kernel/2011-November/073082.html http://marc.info/?t=132070957400005&r=1&w=2 We ended up having to work around this problem in the following commits: https://android.googlesource.com/platform/dalvik/+/311886c6c6fcd3b531531f592d56caab5e2a259c https://android.googlesource.com/platform/art/+/51e5386 https://android.googlesource.com/platform/art/+/f94b781 If this behavior was re-introduced, it's likely to cause hard-to-reproduce problems, and I suspect Android based distributions would tend to disable this feature either globally, or for applications which make a large number of mmap() calls. -- Nick On Tue, Jul 26, 2016 at 11:22 AM, <william.c.roberts@intel.com> wrote: > From: William Roberts <william.c.roberts@intel.com> > > This patch introduces the ability randomize mmap locations where the > address is not requested, for instance when ld is allocating pages for > shared libraries. It chooses to randomize based on the current > personality for ASLR. > > Currently, allocations are done sequentially within unmapped address > space gaps. This may happen top down or bottom up depending on scheme. > > For instance these mmap calls produce contiguous mappings: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40026000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40027000 > > Note no gap between. > > After patches: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x400b4000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40055000 > > Note gap between. > > Using the test program mentioned here, that allocates fixed sized blocks > till exhaustion: https://www.linux-mips.org/archives/linux-mips/2011-05/msg00252.html, > no difference was noticed in the number of allocations. Most varied from > run to run, but were always within a few allocations of one another > between patched and un-patched runs. > > Performance Measurements: > Using strace with -T option and filtering for mmap on the program > ls shows a slowdown of approximate 3.7% > > Signed-off-by: William Roberts <william.c.roberts@intel.com> > --- > mm/mmap.c | 24 ++++++++++++++++++++++++ > 1 file changed, 24 insertions(+) > > diff --git a/mm/mmap.c b/mm/mmap.c > index de2c176..7891272 100644 > --- a/mm/mmap.c > +++ b/mm/mmap.c > @@ -43,6 +43,7 @@ > #include <linux/userfaultfd_k.h> > #include <linux/moduleparam.h> > #include <linux/pkeys.h> > +#include <linux/random.h> > > #include <asm/uaccess.h> > #include <asm/cacheflush.h> > @@ -1582,6 +1583,24 @@ unacct_error: > return error; > } > > +/* > + * Generate a random address within a range. This differs from randomize_addr() by randomizing > + * on len sized chunks. This helps prevent fragmentation of the virtual memory map. > + */ > +static unsigned long randomize_mmap(unsigned long start, unsigned long end, unsigned long len) > +{ > + unsigned long slots; > + > + if ((current->personality & ADDR_NO_RANDOMIZE) || !randomize_va_space) > + return 0; > + > + slots = (end - start)/len; > + if (!slots) > + return 0; > + > + return PAGE_ALIGN(start + ((get_random_long() % slots) * len)); > +} > + > unsigned long unmapped_area(struct vm_unmapped_area_info *info) > { > /* > @@ -1676,6 +1695,8 @@ found: > if (gap_start < info->low_limit) > gap_start = info->low_limit; > > + gap_start = randomize_mmap(gap_start, gap_end, length) ? : gap_start; > + > /* Adjust gap address to the desired alignment */ > gap_start += (info->align_offset - gap_start) & info->align_mask; > > @@ -1775,6 +1796,9 @@ found: > found_highest: > /* Compute highest gap address at the desired alignment */ > gap_end -= info->length; > + > + gap_end = randomize_mmap(gap_start, gap_end, length) ? : gap_end; > + > gap_end -= (gap_end - info->align_offset) & info->align_mask; > > VM_BUG_ON(gap_end < info->low_limit); > -- > 1.9.1 >
Hi William, On Tue, Jul 26, 2016 at 08:13:23PM +0000, Roberts, William C wrote: > > > From: Jason Cooper [mailto:jason@lakedaemon.net] > > > On Tue, Jul 26, 2016 at 11:22:26AM -0700, william.c.roberts@intel.com wrote: > > > > Performance Measurements: > > > > Using strace with -T option and filtering for mmap on the program ls > > > > shows a slowdown of approximate 3.7% > > > > > > I think it would be helpful to show the effect on the resulting object code. > > > > Do you mean the maps of the process? I have some captures for whoopsie on my > > Ubuntu system I can share. No, I mean changes to mm/mmap.o. > > One thing I didn't make clear in my commit message is why this is good. Right > > now, if you know An address within in a process, you know all offsets done with > > mmap(). For instance, an offset To libX can yield libY by adding/subtracting an > > offset. This is meant to make rops a bit harder, or In general any mapping offset > > mmore difficult to find/guess. Are you able to quantify how many bits of entropy you're imposing on the attacker? Is this a chair in the hallway or a significant increase in the chances of crashing the program before finding the desired address? thx, Jason.
> -----Original Message----- > From: Nick Kralevich [mailto:nnk@google.com] > Sent: Tuesday, July 26, 2016 1:41 PM > To: Roberts, William C <william.c.roberts@intel.com> > Cc: jason@lakedaemon.net; linux-mm@vger.kernel.org; lkml <linux- > kernel@vger.kernel.org>; kernel-hardening@lists.openwall.com; Andrew > Morton <akpm@linux-foundation.org>; Kees Cook <keescook@chromium.org>; > Greg KH <gregkh@linuxfoundation.org>; Jeffrey Vander Stoep > <jeffv@google.com>; salyzyn@android.com; Daniel Cashman > <dcashman@android.com> > Subject: Re: [PATCH] [RFC] Introduce mmap randomization > > My apologies in advance if I misunderstand the purposes of this patch. > > IIUC, this patch adds a random gap between various mmap() mappings, with the > goal of ensuring that both the mmap base address and gaps between pages are > randomized. > > If that's the goal, please note that this behavior has caused significant > performance problems to Android in the past. Specifically, random gaps between > mmap()ed regions causes memory space fragmentation. After a program runs for > a long time, the ability to find large contiguous blocks of memory becomes > impossible, and mmap()s fail due to lack of a large enough address space. Yes and fragmentation is definitely a problem here. Especially when the mmaps() are not a consistent length for program life. > > This isn't just a theoretical concern. Android actually hit this on kernels prior to > http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=7dbaa46 > 6780a754154531b44c2086f6618cee3a8 > . Before that patch, the gaps between mmap()ed pages were randomized. > See the discussion at: > > http://lists.infradead.org/pipermail/linux-arm-kernel/2011- > November/073082.html > http://marc.info/?t=132070957400005&r=1&w=2 > > We ended up having to work around this problem in the following commits: > > > https://android.googlesource.com/platform/dalvik/+/311886c6c6fcd3b531531f59 > 2d56caab5e2a259c > https://android.googlesource.com/platform/art/+/51e5386 > https://android.googlesource.com/platform/art/+/f94b781 > > If this behavior was re-introduced, it's likely to cause hard-to-reproduce > problems, and I suspect Android based distributions would tend to disable this > feature either globally, or for applications which make a large number of mmap() > calls. Yeah and this is the issue I want to see if we can overcome. I see the biggest benefit being on libraries loaded by dl. Perhaps a random flag and modify to linkers. Im just spit balling here and collecting the feedback, like this. Thanks for the detail, that helps a lot. > > -- Nick > > > > On Tue, Jul 26, 2016 at 11:22 AM, <william.c.roberts@intel.com> wrote: > > From: William Roberts <william.c.roberts@intel.com> > > > > This patch introduces the ability randomize mmap locations where the > > address is not requested, for instance when ld is allocating pages for > > shared libraries. It chooses to randomize based on the current > > personality for ASLR. > > > > Currently, allocations are done sequentially within unmapped address > > space gaps. This may happen top down or bottom up depending on scheme. > > > > For instance these mmap calls produce contiguous mappings: > > int size = getpagesize(); > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40026000 > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40027000 > > > > Note no gap between. > > > > After patches: > > int size = getpagesize(); > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x400b4000 > > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = > 0x40055000 > > > > Note gap between. > > > > Using the test program mentioned here, that allocates fixed sized > > blocks till exhaustion: > > https://www.linux-mips.org/archives/linux-mips/2011-05/msg00252.html, > > no difference was noticed in the number of allocations. Most varied > > from run to run, but were always within a few allocations of one > > another between patched and un-patched runs. > > > > Performance Measurements: > > Using strace with -T option and filtering for mmap on the program ls > > shows a slowdown of approximate 3.7% > > > > Signed-off-by: William Roberts <william.c.roberts@intel.com> > > --- > > mm/mmap.c | 24 ++++++++++++++++++++++++ > > 1 file changed, 24 insertions(+) > > > > diff --git a/mm/mmap.c b/mm/mmap.c > > index de2c176..7891272 100644 > > --- a/mm/mmap.c > > +++ b/mm/mmap.c > > @@ -43,6 +43,7 @@ > > #include <linux/userfaultfd_k.h> > > #include <linux/moduleparam.h> > > #include <linux/pkeys.h> > > +#include <linux/random.h> > > > > #include <asm/uaccess.h> > > #include <asm/cacheflush.h> > > @@ -1582,6 +1583,24 @@ unacct_error: > > return error; > > } > > > > +/* > > + * Generate a random address within a range. This differs from > > +randomize_addr() by randomizing > > + * on len sized chunks. This helps prevent fragmentation of the virtual > memory map. > > + */ > > +static unsigned long randomize_mmap(unsigned long start, unsigned > > +long end, unsigned long len) { > > + unsigned long slots; > > + > > + if ((current->personality & ADDR_NO_RANDOMIZE) || > !randomize_va_space) > > + return 0; > > + > > + slots = (end - start)/len; > > + if (!slots) > > + return 0; > > + > > + return PAGE_ALIGN(start + ((get_random_long() % slots) * > > +len)); } > > + > > unsigned long unmapped_area(struct vm_unmapped_area_info *info) { > > /* > > @@ -1676,6 +1695,8 @@ found: > > if (gap_start < info->low_limit) > > gap_start = info->low_limit; > > > > + gap_start = randomize_mmap(gap_start, gap_end, length) ? : > > + gap_start; > > + > > /* Adjust gap address to the desired alignment */ > > gap_start += (info->align_offset - gap_start) & > > info->align_mask; > > > > @@ -1775,6 +1796,9 @@ found: > > found_highest: > > /* Compute highest gap address at the desired alignment */ > > gap_end -= info->length; > > + > > + gap_end = randomize_mmap(gap_start, gap_end, length) ? : > > + gap_end; > > + > > gap_end -= (gap_end - info->align_offset) & info->align_mask; > > > > VM_BUG_ON(gap_end < info->low_limit); > > -- > > 1.9.1 > > > > > > -- > Nick Kralevich | Android Security | nnk@google.com | 650.214.4037
> -----Original Message----- > From: owner-linux-mm@kvack.org [mailto:owner-linux-mm@kvack.org] On > Behalf Of Jason Cooper > Sent: Tuesday, July 26, 2016 2:00 PM > To: Roberts, William C <william.c.roberts@intel.com> > Cc: linux-mm@kvack.org; linux-kernel@vger.kernel.org; kernel- > hardening@lists.openwall.com; akpm@linux-foundation.org; > keescook@chromium.org; gregkh@linuxfoundation.org; nnk@google.com; > jeffv@google.com; salyzyn@android.com; dcashman@android.com > Subject: Re: [PATCH] [RFC] Introduce mmap randomization > > Hi William, > > On Tue, Jul 26, 2016 at 08:13:23PM +0000, Roberts, William C wrote: > > > > From: Jason Cooper [mailto:jason@lakedaemon.net] On Tue, Jul 26, > > > > 2016 at 11:22:26AM -0700, william.c.roberts@intel.com wrote: > > > > > Performance Measurements: > > > > > Using strace with -T option and filtering for mmap on the > > > > > program ls shows a slowdown of approximate 3.7% > > > > > > > > I think it would be helpful to show the effect on the resulting object code. > > > > > > Do you mean the maps of the process? I have some captures for > > > whoopsie on my Ubuntu system I can share. > > No, I mean changes to mm/mmap.o. Sure I can post the objdump of that, do you just want a diff of old vs new? > > > > One thing I didn't make clear in my commit message is why this is > > > good. Right now, if you know An address within in a process, you > > > know all offsets done with mmap(). For instance, an offset To libX > > > can yield libY by adding/subtracting an offset. This is meant to > > > make rops a bit harder, or In general any mapping offset mmore difficult to > find/guess. > > Are you able to quantify how many bits of entropy you're imposing on the > attacker? Is this a chair in the hallway or a significant increase in the chances of > crashing the program before finding the desired address? I'd likely need to take a small sample of programs and examine them, especially considering That as gaps are harder to find, it forces the randomization down and randomization can Be directly altered with length on mmap(), versus randomize_addr() which didn't have this restriction but OOM'd do to fragmented easier. > > thx, > > Jason. > > -- > To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to > majordomo@kvack.org. For more info on Linux MM, > see: http://www.linux-mm.org/ . > Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
On Tue, Jul 26, 2016 at 2:02 PM, Roberts, William C <william.c.roberts@intel.com> wrote: > > >> -----Original Message----- >> From: Nick Kralevich [mailto:nnk@google.com] >> Sent: Tuesday, July 26, 2016 1:41 PM >> To: Roberts, William C <william.c.roberts@intel.com> >> Cc: jason@lakedaemon.net; linux-mm@vger.kernel.org; lkml <linux- >> kernel@vger.kernel.org>; kernel-hardening@lists.openwall.com; Andrew >> Morton <akpm@linux-foundation.org>; Kees Cook <keescook@chromium.org>; >> Greg KH <gregkh@linuxfoundation.org>; Jeffrey Vander Stoep >> <jeffv@google.com>; salyzyn@android.com; Daniel Cashman >> <dcashman@android.com> >> Subject: Re: [PATCH] [RFC] Introduce mmap randomization >> >> My apologies in advance if I misunderstand the purposes of this patch. >> >> IIUC, this patch adds a random gap between various mmap() mappings, with the >> goal of ensuring that both the mmap base address and gaps between pages are >> randomized. >> >> If that's the goal, please note that this behavior has caused significant >> performance problems to Android in the past. Specifically, random gaps between >> mmap()ed regions causes memory space fragmentation. After a program runs for >> a long time, the ability to find large contiguous blocks of memory becomes >> impossible, and mmap()s fail due to lack of a large enough address space. > > Yes and fragmentation is definitely a problem here. Especially when the mmaps() > are not a consistent length for program life. > >> >> This isn't just a theoretical concern. Android actually hit this on kernels prior to >> http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=7dbaa46 >> 6780a754154531b44c2086f6618cee3a8 >> . Before that patch, the gaps between mmap()ed pages were randomized. >> See the discussion at: >> >> http://lists.infradead.org/pipermail/linux-arm-kernel/2011- >> November/073082.html >> http://marc.info/?t=132070957400005&r=1&w=2 >> >> We ended up having to work around this problem in the following commits: >> >> >> https://android.googlesource.com/platform/dalvik/+/311886c6c6fcd3b531531f59 >> 2d56caab5e2a259c >> https://android.googlesource.com/platform/art/+/51e5386 >> https://android.googlesource.com/platform/art/+/f94b781 >> >> If this behavior was re-introduced, it's likely to cause hard-to-reproduce >> problems, and I suspect Android based distributions would tend to disable this >> feature either globally, or for applications which make a large number of mmap() >> calls. > > Yeah and this is the issue I want to see if we can overcome. I see the biggest benefit > being on libraries loaded by dl. Perhaps a random flag and modify to linkers. Im just > spit balling here and collecting the feedback, like this. Thanks for the detail, that > helps a lot. Android N introduced library load order randomization, which partially helps with this. https://android-review.googlesource.com/178130 There's also https://android-review.googlesource.com/248499 which adds additional gaps for shared libraries. > >> >> -- Nick >> >> >> >> On Tue, Jul 26, 2016 at 11:22 AM, <william.c.roberts@intel.com> wrote: >> > From: William Roberts <william.c.roberts@intel.com> >> > >> > This patch introduces the ability randomize mmap locations where the >> > address is not requested, for instance when ld is allocating pages for >> > shared libraries. It chooses to randomize based on the current >> > personality for ASLR. >> > >> > Currently, allocations are done sequentially within unmapped address >> > space gaps. This may happen top down or bottom up depending on scheme. >> > >> > For instance these mmap calls produce contiguous mappings: >> > int size = getpagesize(); >> > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = >> 0x40026000 >> > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = >> 0x40027000 >> > >> > Note no gap between. >> > >> > After patches: >> > int size = getpagesize(); >> > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = >> 0x400b4000 >> > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = >> 0x40055000 >> > >> > Note gap between. >> > >> > Using the test program mentioned here, that allocates fixed sized >> > blocks till exhaustion: >> > https://www.linux-mips.org/archives/linux-mips/2011-05/msg00252.html, >> > no difference was noticed in the number of allocations. Most varied >> > from run to run, but were always within a few allocations of one >> > another between patched and un-patched runs. >> > >> > Performance Measurements: >> > Using strace with -T option and filtering for mmap on the program ls >> > shows a slowdown of approximate 3.7% >> > >> > Signed-off-by: William Roberts <william.c.roberts@intel.com> >> > --- >> > mm/mmap.c | 24 ++++++++++++++++++++++++ >> > 1 file changed, 24 insertions(+) >> > >> > diff --git a/mm/mmap.c b/mm/mmap.c >> > index de2c176..7891272 100644 >> > --- a/mm/mmap.c >> > +++ b/mm/mmap.c >> > @@ -43,6 +43,7 @@ >> > #include <linux/userfaultfd_k.h> >> > #include <linux/moduleparam.h> >> > #include <linux/pkeys.h> >> > +#include <linux/random.h> >> > >> > #include <asm/uaccess.h> >> > #include <asm/cacheflush.h> >> > @@ -1582,6 +1583,24 @@ unacct_error: >> > return error; >> > } >> > >> > +/* >> > + * Generate a random address within a range. This differs from >> > +randomize_addr() by randomizing >> > + * on len sized chunks. This helps prevent fragmentation of the virtual >> memory map. >> > + */ >> > +static unsigned long randomize_mmap(unsigned long start, unsigned >> > +long end, unsigned long len) { >> > + unsigned long slots; >> > + >> > + if ((current->personality & ADDR_NO_RANDOMIZE) || >> !randomize_va_space) >> > + return 0; >> > + >> > + slots = (end - start)/len; >> > + if (!slots) >> > + return 0; >> > + >> > + return PAGE_ALIGN(start + ((get_random_long() % slots) * >> > +len)); } >> > + >> > unsigned long unmapped_area(struct vm_unmapped_area_info *info) { >> > /* >> > @@ -1676,6 +1695,8 @@ found: >> > if (gap_start < info->low_limit) >> > gap_start = info->low_limit; >> > >> > + gap_start = randomize_mmap(gap_start, gap_end, length) ? : >> > + gap_start; >> > + >> > /* Adjust gap address to the desired alignment */ >> > gap_start += (info->align_offset - gap_start) & >> > info->align_mask; >> > >> > @@ -1775,6 +1796,9 @@ found: >> > found_highest: >> > /* Compute highest gap address at the desired alignment */ >> > gap_end -= info->length; >> > + >> > + gap_end = randomize_mmap(gap_start, gap_end, length) ? : >> > + gap_end; >> > + >> > gap_end -= (gap_end - info->align_offset) & info->align_mask; >> > >> > VM_BUG_ON(gap_end < info->low_limit); >> > -- >> > 1.9.1 >> > >> >> >> >> -- >> Nick Kralevich | Android Security | nnk@google.com | 650.214.4037
On Tue, Jul 26, 2016 at 09:06:30PM +0000, Roberts, William C wrote: > > From: owner-linux-mm@kvack.org [mailto:owner-linux-mm@kvack.org] On > > Behalf Of Jason Cooper > > On Tue, Jul 26, 2016 at 08:13:23PM +0000, Roberts, William C wrote: > > > > > From: Jason Cooper [mailto:jason@lakedaemon.net] On Tue, Jul 26, > > > > > 2016 at 11:22:26AM -0700, william.c.roberts@intel.com wrote: > > > > > > Performance Measurements: > > > > > > Using strace with -T option and filtering for mmap on the > > > > > > program ls shows a slowdown of approximate 3.7% > > > > > > > > > > I think it would be helpful to show the effect on the resulting object code. > > > > > > > > Do you mean the maps of the process? I have some captures for > > > > whoopsie on my Ubuntu system I can share. > > > > No, I mean changes to mm/mmap.o. > > Sure I can post the objdump of that, do you just want a diff of old vs new? Well, I'm partial to scripts/objdiff, but bloat-o-meter might be more familiar to most of the folks who you'll be trying to convince to merge this. But that's the least of your worries atm. :-/ I was going to dig into mmap.c to confirm my suspicions, but Nick answered it for me. Fragmentation caused by this sort of feature is known to have caused problems in the past. I would highly recommend studying those prior use cases and answering those concerns before progressing too much further. As I've mentioned elsewhere, you'll need to quantify the increased difficulty to the attacker that your patch imposes. Personally, I would assess that first to see if it's worth the effort at all. > > > > One thing I didn't make clear in my commit message is why this > > > > is good. Right now, if you know An address within in a process, > > > > you know all offsets done with mmap(). For instance, an offset > > > > To libX can yield libY by adding/subtracting an offset. This is > > > > meant to make rops a bit harder, or In general any mapping > > > > offset mmore difficult to > > find/guess. > > > > Are you able to quantify how many bits of entropy you're imposing on > > the attacker? Is this a chair in the hallway or a significant > > increase in the chances of crashing the program before finding the > > desired address? > > I'd likely need to take a small sample of programs and examine them, > especially considering That as gaps are harder to find, it forces the > randomization down and randomization can Be directly altered with > length on mmap(), versus randomize_addr() which didn't have this > restriction but OOM'd do to fragmented easier. Right, after the Android feedback from Nick, I think you have a lot of work on your hands. Not just in design, but also in developing convincing arguments derived from real use cases. thx, Jason.
On 07/26/2016 02:44 PM, Jason Cooper wrote: >> > I'd likely need to take a small sample of programs and examine them, >> > especially considering That as gaps are harder to find, it forces the >> > randomization down and randomization can Be directly altered with >> > length on mmap(), versus randomize_addr() which didn't have this >> > restriction but OOM'd do to fragmented easier. > Right, after the Android feedback from Nick, I think you have a lot of > work on your hands. Not just in design, but also in developing convincing > arguments derived from real use cases. Why not just have the feature be disabled on 32-bit by default? All of the Android problems seemed to originate with having a constrained 32-bit address space.
On Tue, Jul 26, 2016 at 1:59 PM, Jason Cooper <jason@lakedaemon.net> wrote: >> > One thing I didn't make clear in my commit message is why this is good. Right >> > now, if you know An address within in a process, you know all offsets done with >> > mmap(). For instance, an offset To libX can yield libY by adding/subtracting an >> > offset. This is meant to make rops a bit harder, or In general any mapping offset >> > mmore difficult to find/guess. > > Are you able to quantify how many bits of entropy you're imposing on the > attacker? Is this a chair in the hallway or a significant increase in > the chances of crashing the program before finding the desired address? Quantifying the effect of many security changes is extremely difficult, especially for a probabilistic defense like ASLR. I would urge us to not place too high of a proof bar on this change. Channeling Spender / grsecurity team, ASLR gets it's benefit not from it's high benefit, but from it's low cost of implementation (https://forums.grsecurity.net/viewtopic.php?f=7&t=3367). This patch certainly meets the low cost of implementation bar. In the Project Zero Stagefright post (http://googleprojectzero.blogspot.com/2015/09/stagefrightened.html), we see that the linear allocation of memory combined with the low number of bits in the initial mmap offset resulted in a much more predictable layout which aided the attacker. The initial random mmap base range was increased by Daniel Cashman in d07e22597d1d355829b7b18ac19afa912cf758d1, but we've done nothing to address page relative attacks. Inter-mmap randomization will decrease the predictability of later mmap() allocations, which should help make data structures harder to find in memory. In addition, this patch will also introduce unmapped gaps between pages, preventing linear overruns from one mapping to another another mapping. I am unable to quantify how much this will improve security, but it should be > 0. I like Dave Hansen's suggestion that this functionality be limited to 64 bits, where concerns about running out of address space are essentially nil. I'd be supportive of this change if it was limited to 64 bits. -- Nick
On Wed, Jul 27, 2016 at 09:59:35AM -0700, Nick Kralevich wrote: > On Tue, Jul 26, 2016 at 1:59 PM, Jason Cooper <jason@lakedaemon.net> wrote: > >> > One thing I didn't make clear in my commit message is why this is good. Right > >> > now, if you know An address within in a process, you know all offsets done with > >> > mmap(). For instance, an offset To libX can yield libY by adding/subtracting an > >> > offset. This is meant to make rops a bit harder, or In general any mapping offset > >> > mmore difficult to find/guess. > > > > Are you able to quantify how many bits of entropy you're imposing on the > > attacker? Is this a chair in the hallway or a significant increase in > > the chances of crashing the program before finding the desired address? > > Quantifying the effect of many security changes is extremely > difficult, especially for a probabilistic defense like ASLR. I would > urge us to not place too high of a proof bar on this change. > Channeling Spender / grsecurity team, ASLR gets it's benefit not from > it's high benefit, but from it's low cost of implementation > (https://forums.grsecurity.net/viewtopic.php?f=7&t=3367). This patch > certainly meets the low cost of implementation bar. Ok, I buy that with the 64bit-only caveat. > In the Project Zero Stagefright post > (http://googleprojectzero.blogspot.com/2015/09/stagefrightened.html), > we see that the linear allocation of memory combined with the low > number of bits in the initial mmap offset resulted in a much more > predictable layout which aided the attacker. The initial random mmap > base range was increased by Daniel Cashman in > d07e22597d1d355829b7b18ac19afa912cf758d1, but we've done nothing to > address page relative attacks. > > Inter-mmap randomization will decrease the predictability of later > mmap() allocations, which should help make data structures harder to > find in memory. In addition, this patch will also introduce unmapped > gaps between pages, preventing linear overruns from one mapping to > another another mapping. I am unable to quantify how much this will > improve security, but it should be > 0. One person calls "unmapped gaps between pages" a feature, others call it a mess. ;-) > I like Dave Hansen's suggestion that this functionality be limited to > 64 bits, where concerns about running out of address space are > essentially nil. I'd be supportive of this change if it was limited to > 64 bits. Agreed. thx, Jason.
> > In the Project Zero Stagefright post > > (http://googleprojectzero.blogspot.com/2015/09/stagefrightened.html) > > , > > we see that the linear allocation of memory combined with the low > > number of bits in the initial mmap offset resulted in a much more > > predictable layout which aided the attacker. The initial random mmap > > base range was increased by Daniel Cashman in > > d07e22597d1d355829b7b18ac19afa912cf758d1, but we've done nothing to > > address page relative attacks. > > > > Inter-mmap randomization will decrease the predictability of later > > mmap() allocations, which should help make data structures harder to > > find in memory. In addition, this patch will also introduce unmapped > > gaps between pages, preventing linear overruns from one mapping to > > another another mapping. I am unable to quantify how much this will > > improve security, but it should be > 0. > > One person calls "unmapped gaps between pages" a feature, others call > it > a mess. ;-) It's very hard to quantify the benefits of fine-grained randomization, but there are other useful guarantees you could provide. It would be quite helpful for the kernel to expose the option to force a PROT_NONE mapping after every allocation. The gaps should actually be enforced. So perhaps 3 things, simply exposed as off-by-default sysctl options (no need for special treatment on 32-bit): a) configurable minimum gap size in pages (for protection against linear and small {under,over}flows) b) configurable minimum gap size based on a ratio to allocation size (for making the heap sparse to mitigate heap sprays, especially when mixed with fine-grained randomization - for example 2x would add a 2M gap after a 1M mapping) c) configurable maximum random gap size (the random gap would be in addition to the enforced minimums) The randomization could just be considered an extra with minor benefits rather than the whole feature. A full fine-grained randomization implementation would need a higher-level form of randomization than gaps in the kernel along with cooperation from userspace allocators. This would make sense as one part of it though.
Hi Daniel, On Fri, Jul 29, 2016 at 06:10:02AM -0400, Daniel Micay wrote: > > > In the Project Zero Stagefright post > > > (http://googleprojectzero.blogspot.com/2015/09/stagefrightened.html) > > > , we see that the linear allocation of memory combined with the > > > low number of bits in the initial mmap offset resulted in a much > > > more predictable layout which aided the attacker. The initial > > > random mmap base range was increased by Daniel Cashman in > > > d07e22597d1d355829b7b18ac19afa912cf758d1, but we've done nothing > > > to address page relative attacks. > > > > > > Inter-mmap randomization will decrease the predictability of later > > > mmap() allocations, which should help make data structures harder > > > to find in memory. In addition, this patch will also introduce > > > unmapped gaps between pages, preventing linear overruns from one > > > mapping to another another mapping. I am unable to quantify how > > > much this will improve security, but it should be > 0. > > > > One person calls "unmapped gaps between pages" a feature, others > > call it a mess. ;-) > > It's very hard to quantify the benefits of fine-grained randomization, ? N = # of possible addresses. The bigger N is, the more chances the attacker will trip up before finding what they were looking for. > but there are other useful guarantees you could provide. It would be > quite helpful for the kernel to expose the option to force a PROT_NONE > mapping after every allocation. The gaps should actually be enforced. > > So perhaps 3 things, simply exposed as off-by-default sysctl options > (no need for special treatment on 32-bit): I'm certainly not an mm-developer, but this looks to me like we're pushing the work of creating efficient, random mappings out to userspace. :-/ > a) configurable minimum gap size in pages (for protection against > linear and small {under,over}flows) b) configurable minimum gap size > based on a ratio to allocation size (for making the heap sparse to > mitigate heap sprays, especially when mixed with fine-grained > randomization - for example 2x would add a 2M gap after a 1M mapping) mmm, this looks like an information leak. Best to set a range of pages and pick a random number within that range for each call. > c) configurable maximum random gap size (the random gap would be in > addition to the enforced minimums) > > The randomization could just be considered an extra with minor > benefits rather than the whole feature. A full fine-grained > randomization implementation would need a higher-level form of > randomization than gaps in the kernel along with cooperation from > userspace allocators. This would make sense as one part of it though. Ok, so here's an idea. This idea could be used in conjunction with random gaps, or on it's own. It would be enhanced by userspace random load order. The benefit is that with 32bit address space, and no random gapping, it's still not wasting much space. Given a memory space, break it up into X bands such that there are 2*X possible addresses. |A B|C D|E F|G H| ... |2*X-2 2*X-1| |--> <--|--> <--|--> <--|--> <--| ... |--> <--| min max For each call to mmap, we randomly pick a value within [0 - 2*X). Assuming A=0 in the diagram above, even values grow up, odd values grow down. Gradually consuming the single gap in the middle of each band. How many bands to use would depend on: * 32/64bit * Average number of mmap calls * largest single mmap call usually seen * if using random gaps and range used If the free gap in a chosen band is too small for the request, pick again among the other bands. Again, I'm not an mm dev, so I might be totally smoking crack on this one... thx, Jason.
> > It's very hard to quantify the benefits of fine-grained > > randomization, > > ? N = # of possible addresses. The bigger N is, the more chances the > attacker will trip up before finding what they were looking for. If the attacker is forcing the creation of many objects with a function pointer and then trying to hit one, the only thing that would help is if the heap is very sparse with random bases within it. They don't need to hit a specific object for an exploit to work. The details of how the randomization is done and the guarantees that are provided certainly matter. Individual random gaps are low entropy and they won't add up to much higher entropy randomization even for two objects that are far apart. The entropy has no chance to build up since the sizes will average out. I'm not saying it doesn't make sense to do this (it's a feature that I really want), but there are a lot of ways to approach fine-grained mmap randomization and the design decisions should be justified and their impact analyzed/measured. > > but there are other useful guarantees you could provide. It would be > > quite helpful for the kernel to expose the option to force a > > PROT_NONE > > mapping after every allocation. The gaps should actually be > > enforced. > > > > So perhaps 3 things, simply exposed as off-by-default sysctl options > > (no need for special treatment on 32-bit): > > I'm certainly not an mm-developer, but this looks to me like we're > pushing the work of creating efficient, random mappings out to > userspace. :-/ Exposing configuration doesn't push work to userspace. I can't see any way that this would be done by default even on 64-bit due to the extra VMAs, so it really needs configuration. > > a) configurable minimum gap size in pages (for protection against > > linear and small {under,over}flows) b) configurable minimum gap size > > based on a ratio to allocation size (for making the heap sparse to > > mitigate heap sprays, especially when mixed with fine-grained > > randomization - for example 2x would add a 2M gap after a 1M > > mapping) > > mmm, this looks like an information leak. Best to set a range of > pages > and pick a random number within that range for each call. A minimum gap size provides guarantees not offered by randomization alone. It might not make sense to approach making the heap sparse by forcing it separately from randomization, but doing it isn't leaking information. Obviously the random gap would be chosen by picking a maximum size (n) and choosing a size between [0, n], which was the next potential variable, separate from these non-randomization-related guarantees. > > c) configurable maximum random gap size (the random gap would be in > > addition to the enforced minimums) > > > > The randomization could just be considered an extra with minor > > benefits rather than the whole feature. A full fine-grained > > randomization implementation would need a higher-level form of > > randomization than gaps in the kernel along with cooperation from > > userspace allocators. This would make sense as one part of it > > though. > > Ok, so here's an idea. This idea could be used in conjunction with > random gaps, or on it's own. It would be enhanced by userspace random > load order. > > The benefit is that with 32bit address space, and no random gapping, > it's still not wasting much space. > > Given a memory space, break it up into X bands such that there are 2*X > possible addresses. > > |A B|C D|E F|G H| ... |2*X-2 2*X-1| > |--> <--|--> <--|--> <--|--> <--| ... |--> <--| > min max > > For each call to mmap, we randomly pick a value within [0 - 2*X). > Assuming A=0 in the diagram above, even values grow up, odd values > grow > down. Gradually consuming the single gap in the middle of each band. > > How many bands to use would depend on: > * 32/64bit > * Average number of mmap calls > * largest single mmap call usually seen > * if using random gaps and range used > > If the free gap in a chosen band is too small for the request, pick > again among the other bands. > > Again, I'm not an mm dev, so I might be totally smoking crack on this > one... > > thx, > > Jason. Address space fragmentation matters a lot, not only wasted space due to memory that's explicitly reserved for random gaps. The randomization guarantees under situations like memory exhaustion also matter. I do think fine-grained randomization would be useful, but I think it's unclear what a good approach would be, along with what the security benefits would be. The malloc implementation is also very relevant. OpenBSD has fine-grained mmap randomization with a fair bit of thought put into how it works, but I don't think there has been much analysis of it. The security properties really aren't clear.
> -----Original Message----- > From: Nick Kralevich [mailto:nnk@google.com] > Sent: Wednesday, July 27, 2016 10:00 AM > To: Jason Cooper <jason@lakedaemon.net> > Cc: Roberts, William C <william.c.roberts@intel.com>; linux-mm@kvack.org; > linux-kernel@vger.kernel.org; kernel-hardening@lists.openwall.com; > akpm@linux-foundation.org; keescook@chromium.org; > gregkh@linuxfoundation.org; jeffv@google.com; salyzyn@android.com; > dcashman@android.com > Subject: Re: [PATCH] [RFC] Introduce mmap randomization > > On Tue, Jul 26, 2016 at 1:59 PM, Jason Cooper <jason@lakedaemon.net> wrote: > >> > One thing I didn't make clear in my commit message is why this is > >> > good. Right now, if you know An address within in a process, you > >> > know all offsets done with mmap(). For instance, an offset To libX > >> > can yield libY by adding/subtracting an offset. This is meant to > >> > make rops a bit harder, or In general any mapping offset mmore difficult to > find/guess. > > > > Are you able to quantify how many bits of entropy you're imposing on > > the attacker? Is this a chair in the hallway or a significant > > increase in the chances of crashing the program before finding the desired > address? > > Quantifying the effect of many security changes is extremely difficult, especially > for a probabilistic defense like ASLR. I would urge us to not place too high of a > proof bar on this change. > Channeling Spender / grsecurity team, ASLR gets it's benefit not from it's high > benefit, but from it's low cost of implementation > (https://forums.grsecurity.net/viewtopic.php?f=7&t=3367). This patch certainly > meets the low cost of implementation bar. > > In the Project Zero Stagefright post > (http://googleprojectzero.blogspot.com/2015/09/stagefrightened.html), > we see that the linear allocation of memory combined with the low number of > bits in the initial mmap offset resulted in a much more predictable layout which > aided the attacker. The initial random mmap base range was increased by Daniel > Cashman in d07e22597d1d355829b7b18ac19afa912cf758d1, but we've done > nothing to address page relative attacks. > > Inter-mmap randomization will decrease the predictability of later > mmap() allocations, which should help make data structures harder to find in > memory. In addition, this patch will also introduce unmapped gaps between > pages, preventing linear overruns from one mapping to another another > mapping. I am unable to quantify how much this will improve security, but it > should be > 0. > > I like Dave Hansen's suggestion that this functionality be limited to > 64 bits, where concerns about running out of address space are essentially nil. I'd > be supportive of this change if it was limited to > 64 bits. Sorry for the delay on responding, I was on vacation being worthless. Nick, very eloquently, described what I failed to put in the commit message. I was thinking about this on vacation and also thought that on 64 bit the fragmentation shouldn't be an issue. @nnk, disabling ASLR via set_arch() on Android, is that only for 32 bit address spaces where you had that problem?
On Tue, Aug 2, 2016 at 9:57 AM, Roberts, William C <william.c.roberts@intel.com> wrote: > @nnk, disabling ASLR via set_arch() on Android, is that only for 32 bit address spaces where > you had that problem? Yes. Only 32 bit address spaces had the fragmentation problem.
<snip> > > > > No, I mean changes to mm/mmap.o. > From UML build: NEW: 0000000000001610 <unmapped_area>: 1610: 55 push %rbp 1611: 48 89 e5 mov %rsp,%rbp 1614: 41 54 push %r12 1616: 48 8d 45 e8 lea -0x18(%rbp),%rax 161a: 53 push %rbx 161b: 48 89 fb mov %rdi,%rbx 161e: 48 83 ec 10 sub $0x10,%rsp 1622: 48 25 00 e0 ff ff and $0xffffffffffffe000,%rax 1628: 48 8b 57 08 mov 0x8(%rdi),%rdx 162c: 48 03 57 20 add 0x20(%rdi),%rdx 1630: 48 8b 00 mov (%rax),%rax 1633: 4c 8b 88 b0 01 00 00 mov 0x1b0(%rax),%r9 163a: 48 c7 c0 f4 ff ff ff mov $0xfffffffffffffff4,%rax 1641: 0f 82 05 01 00 00 jb 174c <unmapped_area+0x13c> 1647: 48 8b 7f 18 mov 0x18(%rdi),%rdi 164b: 48 39 d7 cmp %rdx,%rdi 164e: 0f 82 f8 00 00 00 jb 174c <unmapped_area+0x13c> 1654: 4c 8b 63 10 mov 0x10(%rbx),%r12 1658: 48 29 d7 sub %rdx,%rdi 165b: 49 39 fc cmp %rdi,%r12 165e: 0f 87 e8 00 00 00 ja 174c <unmapped_area+0x13c> 1664: 49 8b 41 08 mov 0x8(%r9),%rax 1668: 48 85 c0 test %rax,%rax 166b: 0f 84 93 00 00 00 je 1704 <unmapped_area+0xf4> 1671: 49 8b 49 08 mov 0x8(%r9),%rcx 1675: 48 39 51 18 cmp %rdx,0x18(%rcx) 1679: 0f 82 85 00 00 00 jb 1704 <unmapped_area+0xf4> 167f: 4e 8d 14 22 lea (%rdx,%r12,1),%r10 1683: 48 83 e9 20 sub $0x20,%rcx 1687: 48 8b 31 mov (%rcx),%rsi 168a: 4c 39 d6 cmp %r10,%rsi 168d: 72 15 jb 16a4 <unmapped_area+0x94> 168f: 48 8b 41 30 mov 0x30(%rcx),%rax 1693: 48 85 c0 test %rax,%rax 1696: 74 0c je 16a4 <unmapped_area+0x94> 1698: 48 39 50 18 cmp %rdx,0x18(%rax) 169c: 72 06 jb 16a4 <unmapped_area+0x94> 169e: 48 8d 48 e0 lea -0x20(%rax),%rcx 16a2: eb e3 jmp 1687 <unmapped_area+0x77> 16a4: 48 8b 41 18 mov 0x18(%rcx),%rax 16a8: 48 85 c0 test %rax,%rax 16ab: 74 06 je 16b3 <unmapped_area+0xa3> 16ad: 4c 8b 40 08 mov 0x8(%rax),%r8 16b1: eb 03 jmp 16b6 <unmapped_area+0xa6> 16b3: 45 31 c0 xor %r8d,%r8d 16b6: 49 39 f8 cmp %rdi,%r8 16b9: 0f 87 86 00 00 00 ja 1745 <unmapped_area+0x135> 16bf: 4c 39 d6 cmp %r10,%rsi 16c2: 72 0b jb 16cf <unmapped_area+0xbf> 16c4: 48 89 f0 mov %rsi,%rax 16c7: 4c 29 c0 sub %r8,%rax 16ca: 48 39 d0 cmp %rdx,%rax 16cd: 73 49 jae 1718 <unmapped_area+0x108> 16cf: 48 8b 41 28 mov 0x28(%rcx),%rax 16d3: 48 85 c0 test %rax,%rax 16d6: 74 06 je 16de <unmapped_area+0xce> 16d8: 48 39 50 18 cmp %rdx,0x18(%rax) 16dc: 73 c0 jae 169e <unmapped_area+0x8e> 16de: 48 8b 41 20 mov 0x20(%rcx),%rax 16e2: 48 8d 71 20 lea 0x20(%rcx),%rsi 16e6: 48 83 e0 fc and $0xfffffffffffffffc,%rax 16ea: 74 18 je 1704 <unmapped_area+0xf4> 16ec: 48 3b 70 10 cmp 0x10(%rax),%rsi 16f0: 48 8d 48 e0 lea -0x20(%rax),%rcx 16f4: 75 e8 jne 16de <unmapped_area+0xce> 16f6: 48 8b 70 f8 mov -0x8(%rax),%rsi 16fa: 4c 8b 46 08 mov 0x8(%rsi),%r8 16fe: 48 8b 70 e0 mov -0x20(%rax),%rsi 1702: eb b2 jmp 16b6 <unmapped_area+0xa6> 1704: 4d 8b 41 38 mov 0x38(%r9),%r8 1708: 48 c7 c0 f4 ff ff ff mov $0xfffffffffffffff4,%rax 170f: 49 39 f8 cmp %rdi,%r8 1712: 77 38 ja 174c <unmapped_area+0x13c> 1714: 48 83 ce ff or $0xffffffffffffffff,%rsi 1718: 4d 39 e0 cmp %r12,%r8 171b: 48 b8 00 00 00 00 00 movabs $0x0,%rax 1722: 00 00 00 1725: 4d 0f 43 e0 cmovae %r8,%r12 1729: 4c 89 e7 mov %r12,%rdi 172c: ff d0 callq *%rax 172e: 48 85 c0 test %rax,%rax 1731: 4c 0f 45 e0 cmovne %rax,%r12 1735: 48 8b 43 28 mov 0x28(%rbx),%rax 1739: 4c 29 e0 sub %r12,%rax 173c: 48 23 43 20 and 0x20(%rbx),%rax 1740: 4c 01 e0 add %r12,%rax 1743: eb 07 jmp 174c <unmapped_area+0x13c> 1745: 48 c7 c0 f4 ff ff ff mov $0xfffffffffffffff4,%rax 174c: 5a pop %rdx 174d: 59 pop %rcx 174e: 5b pop %rbx 174f: 41 5c pop %r12 1751: 5d pop %rbp 1752: c3 retq OLD: 0000000000001590 <unmapped_area>: 1590: 55 push %rbp 1591: 48 89 e5 mov %rsp,%rbp 1594: 53 push %rbx 1595: 48 8d 45 f0 lea -0x10(%rbp),%rax 1599: 4c 8b 47 20 mov 0x20(%rdi),%r8 159d: 48 25 00 e0 ff ff and $0xffffffffffffe000,%rax 15a3: 48 8b 00 mov (%rax),%rax 15a6: 4c 89 c6 mov %r8,%rsi 15a9: 48 03 77 08 add 0x8(%rdi),%rsi 15ad: 4c 8b 98 b0 01 00 00 mov 0x1b0(%rax),%r11 15b4: 48 c7 c0 f4 ff ff ff mov $0xfffffffffffffff4,%rax 15bb: 0f 82 e8 00 00 00 jb 16a9 <unmapped_area+0x119> 15c1: 4c 8b 57 18 mov 0x18(%rdi),%r10 15c5: 49 39 f2 cmp %rsi,%r10 15c8: 0f 82 db 00 00 00 jb 16a9 <unmapped_area+0x119> 15ce: 4c 8b 4f 10 mov 0x10(%rdi),%r9 15d2: 49 29 f2 sub %rsi,%r10 15d5: 4d 39 d1 cmp %r10,%r9 15d8: 0f 87 cb 00 00 00 ja 16a9 <unmapped_area+0x119> 15de: 49 8b 43 08 mov 0x8(%r11),%rax 15e2: 48 85 c0 test %rax,%rax 15e5: 0f 84 91 00 00 00 je 167c <unmapped_area+0xec> 15eb: 49 8b 53 08 mov 0x8(%r11),%rdx 15ef: 48 39 72 18 cmp %rsi,0x18(%rdx) 15f3: 0f 82 83 00 00 00 jb 167c <unmapped_area+0xec> 15f9: 4a 8d 1c 0e lea (%rsi,%r9,1),%rbx 15fd: 48 83 ea 20 sub $0x20,%rdx 1601: 48 8b 02 mov (%rdx),%rax 1604: 48 39 d8 cmp %rbx,%rax 1607: 72 15 jb 161e <unmapped_area+0x8e> 1609: 48 8b 4a 30 mov 0x30(%rdx),%rcx 160d: 48 85 c9 test %rcx,%rcx 1610: 74 0c je 161e <unmapped_area+0x8e> 1612: 48 39 71 18 cmp %rsi,0x18(%rcx) 1616: 72 06 jb 161e <unmapped_area+0x8e> 1618: 48 8d 51 e0 lea -0x20(%rcx),%rdx 161c: eb e3 jmp 1601 <unmapped_area+0x71> 161e: 48 8b 4a 18 mov 0x18(%rdx),%rcx 1622: 48 85 c9 test %rcx,%rcx 1625: 74 06 je 162d <unmapped_area+0x9d> 1627: 48 8b 49 08 mov 0x8(%rcx),%rcx 162b: eb 02 jmp 162f <unmapped_area+0x9f> 162d: 31 c9 xor %ecx,%ecx 162f: 4c 39 d1 cmp %r10,%rcx 1632: 77 6e ja 16a2 <unmapped_area+0x112> 1634: 48 39 d8 cmp %rbx,%rax 1637: 72 08 jb 1641 <unmapped_area+0xb1> 1639: 48 29 c8 sub %rcx,%rax 163c: 48 39 f0 cmp %rsi,%rax 163f: 73 4b jae 168c <unmapped_area+0xfc> 1641: 48 8b 42 28 mov 0x28(%rdx),%rax 1645: 48 85 c0 test %rax,%rax 1648: 74 0c je 1656 <unmapped_area+0xc6> 164a: 48 39 70 18 cmp %rsi,0x18(%rax) 164e: 72 06 jb 1656 <unmapped_area+0xc6> 1650: 48 8d 50 e0 lea -0x20(%rax),%rdx 1654: eb ab jmp 1601 <unmapped_area+0x71> 1656: 48 8b 42 20 mov 0x20(%rdx),%rax 165a: 48 8d 4a 20 lea 0x20(%rdx),%rcx 165e: 48 83 e0 fc and $0xfffffffffffffffc,%rax 1662: 74 18 je 167c <unmapped_area+0xec> 1664: 48 3b 48 10 cmp 0x10(%rax),%rcx 1668: 48 8d 50 e0 lea -0x20(%rax),%rdx 166c: 75 e8 jne 1656 <unmapped_area+0xc6> 166e: 48 8b 48 f8 mov -0x8(%rax),%rcx 1672: 48 8b 40 e0 mov -0x20(%rax),%rax 1676: 48 8b 49 08 mov 0x8(%rcx),%rcx 167a: eb b3 jmp 162f <unmapped_area+0x9f> 167c: 49 8b 4b 38 mov 0x38(%r11),%rcx 1680: 48 c7 c0 f4 ff ff ff mov $0xfffffffffffffff4,%rax 1687: 4c 39 d1 cmp %r10,%rcx 168a: 77 1d ja 16a9 <unmapped_area+0x119> 168c: 48 8b 47 28 mov 0x28(%rdi),%rax 1690: 4c 39 c9 cmp %r9,%rcx 1693: 49 0f 42 c9 cmovb %r9,%rcx 1697: 48 29 c8 sub %rcx,%rax 169a: 4c 21 c0 and %r8,%rax 169d: 48 01 c8 add %rcx,%rax 16a0: eb 07 jmp 16a9 <unmapped_area+0x119> 16a2: 48 c7 c0 f4 ff ff ff mov $0xfffffffffffffff4,%rax 16a9: 5b pop %rbx 16aa: 5d pop %rbp 16ab: c3 retq <snip>
> -----Original Message----- > From: Jason Cooper [mailto:jason@lakedaemon.net] > Sent: Tuesday, July 26, 2016 2:45 PM > To: Roberts, William C <william.c.roberts@intel.com> > Cc: linux-mm@kvack.org; linux-kernel@vger.kernel.org; kernel- > hardening@lists.openwall.com; akpm@linux-foundation.org; > keescook@chromium.org; gregkh@linuxfoundation.org; nnk@google.com; > jeffv@google.com; salyzyn@android.com; dcashman@android.com > Subject: Re: [PATCH] [RFC] Introduce mmap randomization > > On Tue, Jul 26, 2016 at 09:06:30PM +0000, Roberts, William C wrote: > > > From: owner-linux-mm@kvack.org [mailto:owner-linux-mm@kvack.org] On > > > Behalf Of Jason Cooper On Tue, Jul 26, 2016 at 08:13:23PM +0000, > > > Roberts, William C wrote: > > > > > > From: Jason Cooper [mailto:jason@lakedaemon.net] On Tue, Jul > > > > > > 26, > > > > > > 2016 at 11:22:26AM -0700, william.c.roberts@intel.com wrote: > > > > > > > Performance Measurements: > > > > > > > Using strace with -T option and filtering for mmap on the > > > > > > > program ls shows a slowdown of approximate 3.7% > > > > > > > > > > > > I think it would be helpful to show the effect on the resulting object > code. > > > > > > > > > > Do you mean the maps of the process? I have some captures for > > > > > whoopsie on my Ubuntu system I can share. > > > > > > No, I mean changes to mm/mmap.o. > > > > Sure I can post the objdump of that, do you just want a diff of old vs new? > > Well, I'm partial to scripts/objdiff, but bloat-o-meter might be more familiar to > most of the folks who you'll be trying to convince to merge this. Ahh I didn't know there were tools for this, thanks. > > But that's the least of your worries atm. :-/ I was going to dig into mmap.c to > confirm my suspicions, but Nick answered it for me. > Fragmentation caused by this sort of feature is known to have caused problems > in the past. I don't know of any mmap randomization done in the past like this. Only the ASLR stuff, which has had known issues on 32 bit address spaces. > > I would highly recommend studying those prior use cases and answering those > concerns before progressing too much further. As I've mentioned elsewhere, > you'll need to quantify the increased difficulty to the attacker that your patch > imposes. Personally, I would assess that first to see if it's worth the effort at all. Yes agreed. > > > > > > One thing I didn't make clear in my commit message is why this > > > > > is good. Right now, if you know An address within in a process, > > > > > you know all offsets done with mmap(). For instance, an offset > > > > > To libX can yield libY by adding/subtracting an offset. This is > > > > > meant to make rops a bit harder, or In general any mapping > > > > > offset mmore difficult to > > > find/guess. > > > > > > Are you able to quantify how many bits of entropy you're imposing on > > > the attacker? Is this a chair in the hallway or a significant > > > increase in the chances of crashing the program before finding the > > > desired address? > > > > I'd likely need to take a small sample of programs and examine them, > > especially considering That as gaps are harder to find, it forces the > > randomization down and randomization can Be directly altered with > > length on mmap(), versus randomize_addr() which didn't have this > > restriction but OOM'd do to fragmented easier. > > Right, after the Android feedback from Nick, I think you have a lot of work on > your hands. Not just in design, but also in developing convincing arguments > derived from real use cases. > > thx, > > Jason.
<snip> > > > > > I would highly recommend studying those prior use cases and answering > > those concerns before progressing too much further. As I've mentioned > > elsewhere, you'll need to quantify the increased difficulty to the > > attacker that your patch imposes. Personally, I would assess that first to see if > it's worth the effort at all. > > Yes agreed. > For those following or those who care I have some preliminary results from a UML test bench. I need to set up better testing, this I know :-P and test under constrained environments etc. I ran 100,000 execs of bash and checked pmap for the location of libc's start address. I recorded this and kept track of the lowest address it was loaded at as well as the highest, the range is aprox 37 bits of entropy. I calculated the Shannon entropy by calculating the frequency of each address that libc was loaded at per 100,000 invocations, I am not sure if this is an abuse of that, considering Shannon's entropy is usually used to calculate the entropy of byte sized units in a file (below you will find my city script). Plotting the data, it looked fairly random. Number theory is not my strong suit, so if anyone has better ways of measuring entropy, I'm all ears, links appreciated. I'm going to fire up some VMs in the coming weeks and test this more, ill post back with results if they differ from UML. Including ARM tablets running Android. low: 0x40000000 high: 0x401cb15000 range: 0x3fdcb15000 Shannon entropy: 10.514440 #!/usr/bin/env python # modified from: http://www.kennethghartman.com/calculate-file-entropy/ import math import sys low=None high=None if len(sys.argv) != 2: print "Usage: file_entropy.py [path]filename" sys.exit() d = {} items=0 with open(sys.argv[1]) as f: for line in f: line = line.strip() line = line.lstrip("0") #print line items = items + 1 if line not in d: d[line] = 1 else: d[line] = d[line] + 1 x = int("0x" + line, 16) if low == None: low = x if high == None: high = x if x < low: low = x if x > high: high = x #print str(items) #print d print ("low: 0x%x" % low) print ("high: 0x%x" % high) print ("range: 0x%x" % (high - low)) # calculate the frequency of each address in the file # XXX Should this really be in the 64 bit address space? freqList = [] for k,v in d.iteritems(): freqList.append(float(v) / items) #print freqList # Shannon entropy ent = 0.0 for freq in freqList: if freq > 0: ent = ent + freq * math.log(freq, 2) ent = -ent print ('Shannon entropy: %f' % ent ) <snip>
On Tue 2016-07-26 11:22:26, william.c.roberts@intel.com wrote: > From: William Roberts <william.c.roberts@intel.com> > > This patch introduces the ability randomize mmap locations where the > address is not requested, for instance when ld is allocating pages for > shared libraries. It chooses to randomize based on the current > personality for ASLR. > > Currently, allocations are done sequentially within unmapped address > space gaps. This may happen top down or bottom up depending on scheme. > > For instance these mmap calls produce contiguous mappings: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40026000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40027000 > > Note no gap between. > > After patches: > int size = getpagesize(); > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x400b4000 > mmap(NULL, size, flags, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x40055000 > > Note gap between. Ok, I guess you can do it... but... what will be the effect on available address space for a process? By doing this, won't you fragment it horribly? This might be nasty on 32-bit systems... Best regards, Pavel
Hi! > Inter-mmap randomization will decrease the predictability of later > mmap() allocations, which should help make data structures harder to > find in memory. In addition, this patch will also introduce unmapped > gaps between pages, preventing linear overruns from one mapping to > another another mapping. I am unable to quantify how much this will > improve security, but it should be > 0. > > I like Dave Hansen's suggestion that this functionality be limited to > 64 bits, where concerns about running out of address space are > essentially nil. I'd be supportive of this change if it was limited to > 64 bits. Yep, 64bits is easier. But notice that x86-64 machines do _not_ have full 64bits of address space... ...and that if you use as much address space as possible, TLB flushes will be slower because page table entries will need more cache. So this will likely have performance implications even when application does no syscalls :-(. How do you plan to deal with huge memory pages support? Best regards, Pavel
diff --git a/mm/mmap.c b/mm/mmap.c index de2c176..7891272 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -43,6 +43,7 @@ #include <linux/userfaultfd_k.h> #include <linux/moduleparam.h> #include <linux/pkeys.h> +#include <linux/random.h> #include <asm/uaccess.h> #include <asm/cacheflush.h> @@ -1582,6 +1583,24 @@ unacct_error: return error; } +/* + * Generate a random address within a range. This differs from randomize_addr() by randomizing + * on len sized chunks. This helps prevent fragmentation of the virtual memory map. + */ +static unsigned long randomize_mmap(unsigned long start, unsigned long end, unsigned long len) +{ + unsigned long slots; + + if ((current->personality & ADDR_NO_RANDOMIZE) || !randomize_va_space) + return 0; + + slots = (end - start)/len; + if (!slots) + return 0; + + return PAGE_ALIGN(start + ((get_random_long() % slots) * len)); +} + unsigned long unmapped_area(struct vm_unmapped_area_info *info) { /* @@ -1676,6 +1695,8 @@ found: if (gap_start < info->low_limit) gap_start = info->low_limit; + gap_start = randomize_mmap(gap_start, gap_end, length) ? : gap_start; + /* Adjust gap address to the desired alignment */ gap_start += (info->align_offset - gap_start) & info->align_mask; @@ -1775,6 +1796,9 @@ found: found_highest: /* Compute highest gap address at the desired alignment */ gap_end -= info->length; + + gap_end = randomize_mmap(gap_start, gap_end, length) ? : gap_end; + gap_end -= (gap_end - info->align_offset) & info->align_mask; VM_BUG_ON(gap_end < info->low_limit);