Re: [RFC PATCH] Randomization of address chosen by mmap.

[Kees Cook]

On Tue, Feb 27, 2018 at 5:13 AM, Ilya Smith <blackzert@xxxxxxxxx> wrote:
> This is more proof of concept. Current implementation doesn't randomize
> address returned by mmap. All the entropy ends with choosing mmap_base_addr
> at the process creation. After that mmap build very predictable layout
> of address space. It allows to bypass ASLR in many cases.

I'd like more details on the threat model here; if it's just a matter
of .so loading order, I wonder if load order randomization would get a
comparable level of uncertainty without the memory fragmentation,
like:
https://android-review.googlesource.com/c/platform/bionic/+/178130/2
If glibc, for example, could do this too, it would go a long way to
improving things. Obviously, it's not as extreme as loading stuff all
over the place, but it seems like the effect for an attack would be
similar. The search _area_ remains small, but the ordering wouldn't be
deterministic any more.

> This patch make randomization of address on any mmap call.
> It works good on 64 bit system, but usage under 32 bit systems is not
> recommended. This approach uses current implementation to simplify search
> of address.

It would be worth spelling out the "not recommended" bit some more
too: this fragments the mmap space, which has some serious issues on
smaller address spaces if you get into a situation where you cannot
allocate a hole large enough between the other allocations.

>
> Here I would like to discuss this approach.
>
> Signed-off-by: Ilya Smith <blackzert@xxxxxxxxx>
> ---
>  include/linux/mm.h |   4 ++
>  mm/mmap.c          | 171 +++++++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 175 insertions(+)
>
> diff --git a/include/linux/mm.h b/include/linux/mm.h
> index ad06d42adb1a..f81b6c8a0bc5 100644
> --- a/include/linux/mm.h
> +++ b/include/linux/mm.h
> @@ -25,6 +25,7 @@
>  #include <linux/err.h>
>  #include <linux/page_ref.h>
>  #include <linux/memremap.h>
> +#include <linux/sched.h>
>
>  struct mempolicy;
>  struct anon_vma;
> @@ -2253,6 +2254,7 @@ struct vm_unmapped_area_info {
>         unsigned long align_offset;
>  };
>
> +extern unsigned long unmapped_area_random(struct vm_unmapped_area_info *info);
>  extern unsigned long unmapped_area(struct vm_unmapped_area_info *info);
>  extern unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info);
>
> @@ -2268,6 +2270,8 @@ extern unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info);
>  static inline unsigned long
>  vm_unmapped_area(struct vm_unmapped_area_info *info)
>  {
> +       if (current->flags & PF_RANDOMIZE)
> +               return unmapped_area_random(info);

I think this will need a larger knob -- doing this by default is
likely to break stuff, I'd imagine? Bikeshedding: I'm not sure if this
should be setting "3" for /proc/sys/kernel/randomize_va_space, or a
separate one like /proc/sys/mm/randomize_mmap_allocation.

>         if (info->flags & VM_UNMAPPED_AREA_TOPDOWN)
>                 return unmapped_area_topdown(info);
>         else
> diff --git a/mm/mmap.c b/mm/mmap.c
> index 9efdc021ad22..58110e065417 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -45,6 +45,7 @@
>  #include <linux/moduleparam.h>
>  #include <linux/pkeys.h>
>  #include <linux/oom.h>
> +#include <linux/random.h>
>
>  #include <linux/uaccess.h>
>  #include <asm/cacheflush.h>
> @@ -1780,6 +1781,176 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
>         return error;
>  }
>
> +unsigned long unmapped_area_random(struct vm_unmapped_area_info *info)
> +{
> +       // first lets find right border with unmapped_area_topdown

Nit: kernel comments are /* */. (It's a good idea to run patches
through scripts/checkpatch.pl first.)

> +       struct mm_struct *mm = current->mm;
> +       struct vm_area_struct *vma;
> +       struct vm_area_struct *right_vma = 0;
> +       unsigned long entropy;
> +       unsigned int entropy_count;
> +       unsigned long length, low_limit, high_limit, gap_start, gap_end;
> +       unsigned long addr, low, high;
> +
> +       /* Adjust search length to account for worst case alignment overhead */
> +       length = info->length + info->align_mask;
> +       if (length < info->length)
> +               return -ENOMEM;
> +
> +       /*
> +        * Adjust search limits by the desired length.
> +        * See implementation comment at top of unmapped_area().
> +        */
> +       gap_end = info->high_limit;
> +       if (gap_end < length)
> +               return -ENOMEM;
> +       high_limit = gap_end - length;
> +
> +       info->low_limit = 0x10000;
> +       if (info->low_limit > high_limit)
> +               return -ENOMEM;
> +       low_limit = info->low_limit + length;
> +
> +       /* Check highest gap, which does not precede any rbtree node */
> +       gap_start = mm->highest_vm_end;
> +       if (gap_start <= high_limit)
> +               goto found;
> +
> +       /* Check if rbtree root looks promising */
> +       if (RB_EMPTY_ROOT(&mm->mm_rb))
> +               return -ENOMEM;
> +       vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
> +       if (vma->rb_subtree_gap < length)
> +               return -ENOMEM;
> +
> +       while (true) {
> +               /* Visit right subtree if it looks promising */
> +               gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
> +               if (gap_start <= high_limit && vma->vm_rb.rb_right) {
> +                       struct vm_area_struct *right =
> +                               rb_entry(vma->vm_rb.rb_right,
> +                                        struct vm_area_struct, vm_rb);
> +                       if (right->rb_subtree_gap >= length) {
> +                               vma = right;
> +                               continue;
> +                       }
> +               }
> +
> +check_current_down:
> +               /* Check if current node has a suitable gap */
> +               gap_end = vm_start_gap(vma);
> +               if (gap_end < low_limit)
> +                       return -ENOMEM;
> +               if (gap_start <= high_limit &&
> +                   gap_end > gap_start && gap_end - gap_start >= length)
> +                       goto found;
> +
> +               /* Visit left subtree if it looks promising */
> +               if (vma->vm_rb.rb_left) {
> +                       struct vm_area_struct *left =
> +                               rb_entry(vma->vm_rb.rb_left,
> +                                        struct vm_area_struct, vm_rb);
> +                       if (left->rb_subtree_gap >= length) {
> +                               vma = left;
> +                               continue;
> +                       }
> +               }
> +
> +               /* Go back up the rbtree to find next candidate node */
> +               while (true) {
> +                       struct rb_node *prev = &vma->vm_rb;
> +
> +                       if (!rb_parent(prev))
> +                               return -ENOMEM;
> +                       vma = rb_entry(rb_parent(prev),
> +                                      struct vm_area_struct, vm_rb);
> +                       if (prev == vma->vm_rb.rb_right) {
> +                               gap_start = vma->vm_prev ?
> +                                       vm_end_gap(vma->vm_prev) : 0;
> +                               goto check_current_down;
> +                       }
> +               }
> +       }

Everything from here up is identical to the existing
unmapped_area_topdown(), yes? This likely needs to be refactored
instead of copy/pasted, and adjust to handle both unmapped_area() and
unmapped_area_topdown().

> +
> +found:
> +       right_vma = vma;
> +       low = gap_start;
> +       high = gap_end - length;
> +
> +       entropy = get_random_long();
> +       entropy_count = 0;
> +
> +       // from left node to right we check if node is fine and
> +       // randomly select it.
> +       vma = mm->mmap;
> +       while (vma != right_vma) {
> +               /* Visit left subtree if it looks promising */
> +               gap_end = vm_start_gap(vma);
> +               if (gap_end >= low_limit && vma->vm_rb.rb_left) {
> +                       struct vm_area_struct *left =
> +                               rb_entry(vma->vm_rb.rb_left,
> +                                        struct vm_area_struct, vm_rb);
> +                       if (left->rb_subtree_gap >= length) {
> +                               vma = left;
> +                               continue;
> +                       }
> +               }
> +
> +               gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : low_limit;
> +check_current_up:
> +               /* Check if current node has a suitable gap */
> +               if (gap_start > high_limit)
> +                       break;
> +               if (gap_end >= low_limit &&
> +                   gap_end > gap_start && gap_end - gap_start >= length) {
> +                       if (entropy & 1) {
> +                               low = gap_start;
> +                               high = gap_end - length;
> +                       }
> +                       entropy >>= 1;
> +                       if (++entropy_count == 64) {
> +                               entropy = get_random_long();
> +                               entropy_count = 0;
> +                       }
> +               }
> +
> +               /* Visit right subtree if it looks promising */
> +               if (vma->vm_rb.rb_right) {
> +                       struct vm_area_struct *right =
> +                               rb_entry(vma->vm_rb.rb_right,
> +                                        struct vm_area_struct, vm_rb);
> +                       if (right->rb_subtree_gap >= length) {
> +                               vma = right;
> +                               continue;
> +                       }
> +               }
> +
> +               /* Go back up the rbtree to find next candidate node */
> +               while (true) {
> +                       struct rb_node *prev = &vma->vm_rb;
> +
> +                       if (!rb_parent(prev))
> +                               BUG(); // this should not happen
> +                       vma = rb_entry(rb_parent(prev),
> +                                      struct vm_area_struct, vm_rb);
> +                       if (prev == vma->vm_rb.rb_left) {
> +                               gap_start = vm_end_gap(vma->vm_prev);
> +                               gap_end = vm_start_gap(vma);
> +                               if (vma == right_vma)

mm/mmap.c: In function âunmapped_area_randomâ:
mm/mmap.c:1939:8: warning: âvmaâ may be used uninitialized in this
function [-Wmaybe-uninitialized]
     if (vma == right_vma)
        ^

> +                                       break;
> +                               goto check_current_up;
> +                       }
> +               }
> +       }

What are the two phases here? Could this second one get collapsed into
the first?

> +
> +       if (high == low)
> +               return low;
> +
> +       addr = get_random_long() % ((high - low) >> PAGE_SHIFT);
> +       addr = low + (addr << PAGE_SHIFT);
> +       return addr;
> +}
> +
>  unsigned long unmapped_area(struct vm_unmapped_area_info *info)
>  {
>         /*

How large are the gaps intended to be? Looking at the gaps on
something like Xorg they differ a lot.

Otherwise, looks interesting!

-Kees

-- 
Kees Cook
Pixel Security