[RFC PATCH] arm64: Make arch_randomize_brk avoid stack area

[RFC PATCH] arm64: Make arch_randomize_brk avoid stack area

[Jon Medhurst (Tixy)]

When a process is created, various address randomisations may end up
colluding to place the address of brk in the stack memory.

One consequence of this, is that even for processes that make no use of
brk, the output of /proc/*/maps may show the stack area listed as
'[heap]' rather than '[stack]'. Apart from being misleading to this causes
fatal errors with the Android run-time like:
"No [stack] line found in /proc/self/task/*/maps"

To prevent this problem pick a limit for brk that allows for the stack's
memory. At the same time we remove randomize_base() as that was only
used by arch_randomize_brk().

Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
from mmap ASLR") this problem shouldn't occur because the address chosen
for loading binaries is well clear of the stack, however, prior to that
the problem does occur because of the following...

The memory layout of a task is determined by arch_pick_mmap_layout. If
address randomisation is enabled (task has flag PF_RANDOMIZE) this sets
mmap_base to a random address at the top of task memory just below a
region calculated to allow for a stack which itself may have a random
base address. Any mmap operations that then happen which require an
address allocating will use the topdown allocation method, i.e. the
first allocated memory will be at the top of memory, just below the
area set aside for the stack.

When a relocatable binary is loaded into a new process by
load_elf_binary and randomised address are enabled, it uses a
'load_bias' of zero, so that when mmap is called to create a memory
region for it, a new address is picked (address zero not being
available). As this is the first memory region in the task, it gets the
region just below the stack, as described previously.

The loader then set's brk to the end of the elf data section, which will
be near the end of the loaded binary and then it calls
arch_randomize_brk. As this currently stands, this adds a random amount
to brk, which unfortunately may take it into the address range where the
stack lies.

Signed-off-by: Jon Medhurst <tixy@linaro.org>
---

I don't know if a change like this is needed for the latest Linux
versions - where it's more like defensive coding than solving a current
issue.

For earlier versions, like 3.18 LTS where I diagnosed the problem, I
don't know if this is a suitable fix, of if the later ASLR changes
should be backported (seems somewhat more invasive).

Perhaps this issue isn't important enough for LTS and is just needed for
people maintaining Android trees.

 arch/arm64/kernel/process.c | 23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index 8062482..7126a5a 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -382,13 +382,24 @@ unsigned long arch_align_stack(unsigned long sp)
 	return sp & ~0xf;
 }
 
-static unsigned long randomize_base(unsigned long base)
+unsigned long arch_randomize_brk(struct mm_struct *mm)
 {
 	unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
-	return randomize_range(base, range_end, 0) ? : base;
-}
+	unsigned long max_stack, range_limit;
 
-unsigned long arch_randomize_brk(struct mm_struct *mm)
-{
-	return randomize_base(mm->brk);
+	/*
+	 * Determine how much room do we need to leave available for the stack.
+	 * We limit this to a reasonable value, because extremely large or
+	 * unlimited stacks are always going to bump up against brk at some
+	 * point and we don't want to fail to randomise brk in those cases.
+	 */
+	max_stack = rlimit(RLIMIT_STACK);
+	if (max_stack > SZ_128M)
+		max_stack = SZ_128M;
+
+	range_limit = mm->start_stack - max_stack - 1;
+	if (range_end > range_limit)
+		range_end > range_limit
+
+	return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
 }
-- 
2.1.4

[RFC PATCH] arm64: Make arch_randomize_brk avoid stack area

[Jon Medhurst (Tixy)]

Sorry, the code patch has errors (I forgot to commit fixes before
running git format-patch), the correct code, which was in the kernel I
built and tested, is at the end of this email.

On Thu, 2016-04-28 at 14:03 +0100, Jon Medhurst (Tixy) wrote:
Some incorrect code...
> diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
> index 8062482..7126a5a 100644
> --- a/arch/arm64/kernel/process.c
> +++ b/arch/arm64/kernel/process.c
> @@ -382,13 +382,24 @@ unsigned long arch_align_stack(unsigned long sp)
>  	return sp & ~0xf;
>  }
>  
> -static unsigned long randomize_base(unsigned long base)
> +unsigned long arch_randomize_brk(struct mm_struct *mm)
>  {
>  	unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
> -	return randomize_range(base, range_end, 0) ? : base;
> -}
> +	unsigned long max_stack, range_limit;
>  
> -unsigned long arch_randomize_brk(struct mm_struct *mm)
> -{
> -	return randomize_base(mm->brk);
> +	/*
> +	 * Determine how much room do we need to leave available for the stack.
> +	 * We limit this to a reasonable value, because extremely large or
> +	 * unlimited stacks are always going to bump up against brk at some
> +	 * point and we don't want to fail to randomise brk in those cases.
> +	 */
> +	max_stack = rlimit(RLIMIT_STACK);
> +	if (max_stack > SZ_128M)
> +		max_stack = SZ_128M;
> +
> +	range_limit = mm->start_stack - max_stack - 1;
> +	if (range_end > range_limit)
> +		range_end > range_limit
> +
> +	return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
>  }

Corrected code...

 arch/arm64/kernel/process.c | 24 ++++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index 07c4c53..7e0f404 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -434,13 +434,25 @@ unsigned long arch_align_stack(unsigned long sp)
 	return sp & ~0xf;
 }
 
-static unsigned long randomize_base(unsigned long base)
+unsigned long arch_randomize_brk(struct mm_struct *mm)
 {
+	unsigned long base = mm->brk;
 	unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
-	return randomize_range(base, range_end, 0) ? : base;
-}
+	unsigned long max_stack, range_limit;
 
-unsigned long arch_randomize_brk(struct mm_struct *mm)
-{
-	return randomize_base(mm->brk);
+	/*
+	 * Determine how much room do we need to leave available for the stack.
+	 * We limit this to a reasonable value, because extremely large or
+	 * unlimited stacks are always going to bump up against brk at some
+	 * point and we don't want to fail to randomise brk in those cases.
+	 */
+	max_stack = rlimit(RLIMIT_STACK);
+	if (max_stack > SZ_128M)
+		max_stack = SZ_128M;
+
+	range_limit = mm->start_stack - max_stack - 1;
+	if (range_end > range_limit)
+		range_end = range_limit;
+
+	return randomize_range(base, range_end, 0) ? : base;
 }
-- 
2.1.4

[RFC PATCH] arm64: Make arch_randomize_brk avoid stack area

[Kees Cook]

On Thu, Apr 28, 2016 at 7:17 AM, Jon Medhurst (Tixy) <tixy@linaro.org> wrote:
> Sorry, the code patch has errors (I forgot to commit fixes before
> running git format-patch), the correct code, which was in the kernel I
> built and tested, is at the end of this email.

Please resend this as a v2 (with a changelog, etc). Conceptually, it
looks fine to me: it will limit the entropy of the brk base address
when close to the stack on old kernels and should be effectively a
no-op on modern kernels. However, I have some notes inline below.

Also, for v2, can you validate the text vs brk offset entropy on a 4.6
kernel before/after this patch?

This (aslr.c) may be helpful in running a few thousand iterations:

http://bazaar.launchpad.net/~ubuntu-bugcontrol/qa-regression-testing/master/files/head:/scripts/kernel-security/aslr/

$ for i in $(seq 10000); do ./aslr --report brk ; done | ...

>
> On Thu, 2016-04-28 at 14:03 +0100, Jon Medhurst (Tixy) wrote:
> Some incorrect code...
>> diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
>> index 8062482..7126a5a 100644
>> --- a/arch/arm64/kernel/process.c
>> +++ b/arch/arm64/kernel/process.c
>> @@ -382,13 +382,24 @@ unsigned long arch_align_stack(unsigned long sp)
>>       return sp & ~0xf;
>>  }
>>
>> -static unsigned long randomize_base(unsigned long base)
>> +unsigned long arch_randomize_brk(struct mm_struct *mm)
>>  {
>>       unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
>> -     return randomize_range(base, range_end, 0) ? : base;
>> -}
>> +     unsigned long max_stack, range_limit;
>>
>> -unsigned long arch_randomize_brk(struct mm_struct *mm)
>> -{
>> -     return randomize_base(mm->brk);
>> +     /*
>> +      * Determine how much room do we need to leave available for the stack.
>> +      * We limit this to a reasonable value, because extremely large or
>> +      * unlimited stacks are always going to bump up against brk at some
>> +      * point and we don't want to fail to randomise brk in those cases.
>> +      */
>> +     max_stack = rlimit(RLIMIT_STACK);
>> +     if (max_stack > SZ_128M)
>> +             max_stack = SZ_128M;
>> +
>> +     range_limit = mm->start_stack - max_stack - 1;
>> +     if (range_end > range_limit)
>> +             range_end > range_limit
>> +
>> +     return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
>>  }
>
> Corrected code...
>
>  arch/arm64/kernel/process.c | 24 ++++++++++++++++++------
>  1 file changed, 18 insertions(+), 6 deletions(-)
>
> diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
> index 07c4c53..7e0f404 100644
> --- a/arch/arm64/kernel/process.c
> +++ b/arch/arm64/kernel/process.c
> @@ -434,13 +434,25 @@ unsigned long arch_align_stack(unsigned long sp)
>         return sp & ~0xf;
>  }
>
> -static unsigned long randomize_base(unsigned long base)
> +unsigned long arch_randomize_brk(struct mm_struct *mm)
>  {
> +       unsigned long base = mm->brk;
>         unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;

This looks wrong. Shouldn't it be (STACK_RND_MASK + 1) << PAGE_SHIFT ?

STACK_RND_MASK is 0x7ff (32-bit) or 0x3ffff (64-bit):

#define STACK_RND_MASK                  (test_thread_flag(TIF_32BIT) ? \
                                                0x7ff >> (PAGE_SHIFT - 12) : \
                                                0x3ffff >> (PAGE_SHIFT - 12))

(4K paged PAGE_SHIFT is 12)

So the correct offset max would be 0x800000 (32-bit) and 0x40000000
(64-bit), instead of
0x7ff0001 and 0x3ffff0001.

Even with that correction, this looks wrong for 32-bit, which uses
0x2000000 natively:

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
        unsigned long range_end = mm->brk + 0x02000000;
        return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
}

Seems like arm64 compat is using 4 times less entropy than native arm?
(Note that STACK_RND_MASK is correct for arm64 compat: this matches
the default in fs/binfmt_elf.c that arm uses. It just seems like the
brk randomization is accidentally too small on arm64 compat since arm
uses a fixed value unrelated to stack randomization.)

0x02000000 arm native
0x00800000 arm64 compat  <- bug?
0x40000000 arm64


> -       return randomize_range(base, range_end, 0) ? : base;
> -}
> +       unsigned long max_stack, range_limit;
>
> -unsigned long arch_randomize_brk(struct mm_struct *mm)
> -{
> -       return randomize_base(mm->brk);
> +       /*
> +        * Determine how much room do we need to leave available for the stack.
> +        * We limit this to a reasonable value, because extremely large or
> +        * unlimited stacks are always going to bump up against brk at some
> +        * point and we don't want to fail to randomise brk in those cases.
> +        */
> +       max_stack = rlimit(RLIMIT_STACK);
> +       if (max_stack > SZ_128M)
> +               max_stack = SZ_128M;
> +
> +       range_limit = mm->start_stack - max_stack - 1;
> +       if (range_end > range_limit)
> +               range_end = range_limit;
> +
> +       return randomize_range(base, range_end, 0) ? : base;
>  }
> --
> 2.1.4
>

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

[RFC PATCH] arm64: Make arch_randomize_brk avoid stack area

[Jon Medhurst (Tixy)]

On Mon, 2016-05-02 at 12:34 -0700, Kees Cook wrote:
> On Thu, Apr 28, 2016 at 7:17 AM, Jon Medhurst (Tixy) <tixy@linaro.org> wrote:
[...]

> >  arch/arm64/kernel/process.c | 24 ++++++++++++++++++------
> >  1 file changed, 18 insertions(+), 6 deletions(-)
> >
> > diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
> > index 07c4c53..7e0f404 100644
> > --- a/arch/arm64/kernel/process.c
> > +++ b/arch/arm64/kernel/process.c
> > @@ -434,13 +434,25 @@ unsigned long arch_align_stack(unsigned long sp)
> >         return sp & ~0xf;
> >  }
> >
> > -static unsigned long randomize_base(unsigned long base)
> > +unsigned long arch_randomize_brk(struct mm_struct *mm)
> >  {
> > +       unsigned long base = mm->brk;
> >         unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
> 
> This looks wrong. Shouldn't it be (STACK_RND_MASK + 1) << PAGE_SHIFT ?

That value is the same as before my changes and it matches the gap left
for stack randomisation in arch/arm64/mm/mmap.c

> 
> STACK_RND_MASK is 0x7ff (32-bit) or 0x3ffff (64-bit):
> 
> #define STACK_RND_MASK                  (test_thread_flag(TIF_32BIT) ? \
>                                                 0x7ff >> (PAGE_SHIFT - 12) : \
>                                                 0x3ffff >> (PAGE_SHIFT - 12))
> 
> (4K paged PAGE_SHIFT is 12)
> 
> So the correct offset max would be 0x800000 (32-bit) and 0x40000000
> (64-bit), instead of
> 0x7ff0001 and 0x3ffff0001.

It seems to me there isn't a 'correct' and 'incorrect' range to use here
and that randomising brk is not directly related to stack randomisation,
they just have similar requirements and constraints.

Anyway, for stack randomisation, in fs/binfmt_elf.c,
randomize_stack_top() has

		random_variable = get_random_long();
		random_variable &= STACK_RND_MASK;
		random_variable <<= PAGE_SHIFT;

so stack top can be randomised by adding a number from zero to
(STACK_RND_MASK << PAGE_SHIFT) inclusive. As the end value passed to
randomize_range() is exclusive, then adding one to the last permissible
value seems the like the right, I.e. arm64's usage of

  (STACK_RND_MASK << PAGE_SHIFT) + 1

for brk is 'correct' in that it's consistent with what happens to the
stack. Though the different functions align values to pages@different
stages, so possibly neither that nor 

  (STACK_RND_MASK + 1)  << PAGE_SHIFT

when used for brk, would be the same as the stack code.


> Even with that correction, this looks wrong for 32-bit, which uses
> 0x2000000 natively:
> 
> unsigned long arch_randomize_brk(struct mm_struct *mm)
> {
>         unsigned long range_end = mm->brk + 0x02000000;
>         return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
> }
> 
> Seems like arm64 compat is using 4 times less entropy than native arm?
> (Note that STACK_RND_MASK is correct for arm64 compat: this matches
> the default in fs/binfmt_elf.c that arm uses. It just seems like the
> brk randomization is accidentally too small on arm64 compat since arm
> uses a fixed value unrelated to stack randomization.)
> 
> 0x02000000 arm native
> 0x00800000 arm64 compat  <- bug?
> 0x40000000 arm64

Well, it's a difference for which there probably isn't a good reason,
don't know if people would call it a bug.

As changing the range of values used for randomisation seems like a
separate issue I won't include any changes for that in my patch for
getting brk to avoid the stack.

-- 
Tixy

[RFC PATCH] arm64: Make arch_randomize_brk avoid stack area

[Kees Cook]

On Tue, May 3, 2016 at 4:13 AM, Jon Medhurst (Tixy) <tixy@linaro.org> wrote:
> On Mon, 2016-05-02 at 12:34 -0700, Kees Cook wrote:
>> On Thu, Apr 28, 2016 at 7:17 AM, Jon Medhurst (Tixy) <tixy@linaro.org> wrote:
> [...]
>
>> >  arch/arm64/kernel/process.c | 24 ++++++++++++++++++------
>> >  1 file changed, 18 insertions(+), 6 deletions(-)
>> >
>> > diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
>> > index 07c4c53..7e0f404 100644
>> > --- a/arch/arm64/kernel/process.c
>> > +++ b/arch/arm64/kernel/process.c
>> > @@ -434,13 +434,25 @@ unsigned long arch_align_stack(unsigned long sp)
>> >         return sp & ~0xf;
>> >  }
>> >
>> > -static unsigned long randomize_base(unsigned long base)
>> > +unsigned long arch_randomize_brk(struct mm_struct *mm)
>> >  {
>> > +       unsigned long base = mm->brk;
>> >         unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
>>
>> This looks wrong. Shouldn't it be (STACK_RND_MASK + 1) << PAGE_SHIFT ?
>
> That value is the same as before my changes and it matches the gap left
> for stack randomisation in arch/arm64/mm/mmap.c

True, I didn't mean it was part of your patch. It just jumped out at
me as something that didn't look right that should probably get fixed
too.

>> STACK_RND_MASK is 0x7ff (32-bit) or 0x3ffff (64-bit):
>>
>> #define STACK_RND_MASK                  (test_thread_flag(TIF_32BIT) ? \
>>                                                 0x7ff >> (PAGE_SHIFT - 12) : \
>>                                                 0x3ffff >> (PAGE_SHIFT - 12))
>>
>> (4K paged PAGE_SHIFT is 12)
>>
>> So the correct offset max would be 0x800000 (32-bit) and 0x40000000
>> (64-bit), instead of
>> 0x7ff0001 and 0x3ffff0001.
>
> It seems to me there isn't a 'correct' and 'incorrect' range to use here
> and that randomising brk is not directly related to stack randomisation,
> they just have similar requirements and constraints.

Well, I think it's a typo. The code seemed to be wanting to convert a
mask to a range, but when adding PAGE_SHIFT, it went in the wrong
place.

> Anyway, for stack randomisation, in fs/binfmt_elf.c,
> randomize_stack_top() has
>
>                 random_variable = get_random_long();
>                 random_variable &= STACK_RND_MASK;
>                 random_variable <<= PAGE_SHIFT;
>
> so stack top can be randomised by adding a number from zero to
> (STACK_RND_MASK << PAGE_SHIFT) inclusive. As the end value passed to
> randomize_range() is exclusive, then adding one to the last permissible

Well, no, this is using the mask correctly. It removes keeps the bits
it's interested in and then promotes them above the page size.

> value seems the like the right, I.e. arm64's usage of
>
>   (STACK_RND_MASK << PAGE_SHIFT) + 1
>
> for brk is 'correct' in that it's consistent with what happens to the
> stack. Though the different functions align values to pages at different
> stages, so possibly neither that nor
>
>   (STACK_RND_MASK + 1)  << PAGE_SHIFT
>
> when used for brk, would be the same as the stack code.

Anyway, this can be a separate fix. Your changes should make sense in
either place (well, it should be a no-op for current kernel, but
that's fine).

>> Even with that correction, this looks wrong for 32-bit, which uses
>> 0x2000000 natively:
>>
>> unsigned long arch_randomize_brk(struct mm_struct *mm)
>> {
>>         unsigned long range_end = mm->brk + 0x02000000;
>>         return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
>> }
>>
>> Seems like arm64 compat is using 4 times less entropy than native arm?
>> (Note that STACK_RND_MASK is correct for arm64 compat: this matches
>> the default in fs/binfmt_elf.c that arm uses. It just seems like the
>> brk randomization is accidentally too small on arm64 compat since arm
>> uses a fixed value unrelated to stack randomization.)
>>
>> 0x02000000 arm native
>> 0x00800000 arm64 compat  <- bug?
>> 0x40000000 arm64
>
> Well, it's a difference for which there probably isn't a good reason,
> don't know if people would call it a bug.

It's a behavioral change between native and compat which reduces the
entropy of brk randomization, so I'm comfortable to call it a bug. :)

> As changing the range of values used for randomisation seems like a
> separate issue I won't include any changes for that in my patch for
> getting brk to avoid the stack.

Sounds fine. Can you resend your change as a v2 with the changelog, etc?

Thanks!

-Kees

>
> --
> Tixy
>



-- 
Kees Cook
Chrome OS & Brillo Security

[PATCH] arm64: Make arch_randomize_brk avoid stack area

[Jon Medhurst (Tixy)]

When a process is created, various address randomisations could end up
colluding to place the address of brk in the stack memory. This would
mean processes making small heap based memory allocations are in danger
of having them overwriting, or overwritten by, the stack.

Another consequence, is that even for processes that make no use of
brk, the output of /proc/*/maps may show the stack area listed as
'[heap]' rather than '[stack]'. Apart from being misleading this causes
fatal errors with the Android run-time like:
"No [stack] line found in /proc/self/task/*/maps"

To prevent this problem pick a limit for brk that allows for the stack's
memory. At the same time we remove randomize_base() as that was only
used by arch_randomize_brk().

Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
from mmap ASLR") this problem shouldn't occur because the address chosen
for loading binaries is well clear of the stack, however, prior to that
the problem does occur because of the following...

The memory layout of a task is determined by arch_pick_mmap_layout. If
address randomisation is enabled (task has flag PF_RANDOMIZE) this sets
mmap_base to a random address at the top of task memory just below a
region calculated to allow for a stack which itself may have a random
base address. Any mmap operations that then happen which require an
address allocating will use the topdown allocation method, i.e. the
first allocated memory will be at the top of memory, just below the
area set aside for the stack.

When a relocatable binary is loaded into a new process by
load_elf_binary and randomised address are enabled, it uses a
'load_bias' of zero, so that when mmap is called to create a memory
region for it, a new address is picked (address zero not being
available). As this is the first memory region in the task, it gets the
region just below the stack, as described previously.

The loader then set's brk to the end of the elf data section, which will
be near the end of the loaded binary and then it calls
arch_randomize_brk. As this currently stands, this adds a random amount
to brk, which unfortunately may take it into the address range where the
stack lies.

Testing:

These changes have been tested on Linux v4.6-rc4 using 100000
invocations of a program [1] that can display the offset of a process's
brk...

$for i in $(seq 100000); do ./aslr --report brk ; done

This shows values of brk are evenly distributed over a 1GB range, both
before and after this change.

With Linux version 3.18 (where the collision of brk and stack can happen
and this change limits brk to avoid that) the distribution of brk values
after the change shows a slope where lower values for brk are more
common and upper values have about half the frequency of those.

[1] http://bazaar.launchpad.net/~ubuntu-bugcontrol/qa-regression-testing/master/files/2499/scripts/kernel-security/aslr/

Signed-off-by: Jon Medhurst <tixy@linaro.org>
Cc: <stable@vger.kernel.org> # 4.0 and earlier

---

Changes since RFC.
- Fixed compilation errors (finger trouble preparing original email)
- Updated commit message to included notes on testing
- Added CC stable for Linux '4.0 and earlier'

 arch/arm64/kernel/process.c | 24 ++++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index 8062482..26429a0 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -382,13 +382,25 @@ unsigned long arch_align_stack(unsigned long sp)
 	return sp & ~0xf;
 }
 
-static unsigned long randomize_base(unsigned long base)
+unsigned long arch_randomize_brk(struct mm_struct *mm)
 {
+	unsigned long base = mm->brk;
 	unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
-	return randomize_range(base, range_end, 0) ? : base;
-}
+	unsigned long max_stack, range_limit;
 
-unsigned long arch_randomize_brk(struct mm_struct *mm)
-{
-	return randomize_base(mm->brk);
+	/*
+	 * Determine how much room we need to leave available for the stack.
+	 * We limit this to a reasonable value, because extremely large or
+	 * unlimited stacks are always going to bump up against brk at some
+	 * point and we don't want to fail to randomise brk in those cases.
+	 */
+	max_stack = rlimit(RLIMIT_STACK);
+	if (max_stack > SZ_128M)
+		max_stack = SZ_128M;
+
+	range_limit = mm->start_stack - max_stack - 1;
+	if (range_end > range_limit)
+		range_end = range_limit;
+
+	return randomize_range(base, range_end, 0) ? : base;
 }
-- 
2.1.4

[PATCH] arm64: Make arch_randomize_brk avoid stack area

[Kees Cook]

On Wed, May 4, 2016 at 7:09 AM, Jon Medhurst (Tixy) <tixy@linaro.org> wrote:
> When a process is created, various address randomisations could end up
> colluding to place the address of brk in the stack memory. This would
> mean processes making small heap based memory allocations are in danger
> of having them overwriting, or overwritten by, the stack.
>
> Another consequence, is that even for processes that make no use of
> brk, the output of /proc/*/maps may show the stack area listed as
> '[heap]' rather than '[stack]'. Apart from being misleading this causes
> fatal errors with the Android run-time like:
> "No [stack] line found in /proc/self/task/*/maps"
>
> To prevent this problem pick a limit for brk that allows for the stack's
> memory. At the same time we remove randomize_base() as that was only
> used by arch_randomize_brk().
>
> Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
> from mmap ASLR") this problem shouldn't occur because the address chosen
> for loading binaries is well clear of the stack, however, prior to that
> the problem does occur because of the following...
>
> The memory layout of a task is determined by arch_pick_mmap_layout. If
> address randomisation is enabled (task has flag PF_RANDOMIZE) this sets
> mmap_base to a random address at the top of task memory just below a
> region calculated to allow for a stack which itself may have a random
> base address. Any mmap operations that then happen which require an
> address allocating will use the topdown allocation method, i.e. the
> first allocated memory will be at the top of memory, just below the
> area set aside for the stack.
>
> When a relocatable binary is loaded into a new process by
> load_elf_binary and randomised address are enabled, it uses a
> 'load_bias' of zero, so that when mmap is called to create a memory
> region for it, a new address is picked (address zero not being
> available). As this is the first memory region in the task, it gets the
> region just below the stack, as described previously.
>
> The loader then set's brk to the end of the elf data section, which will
> be near the end of the loaded binary and then it calls
> arch_randomize_brk. As this currently stands, this adds a random amount
> to brk, which unfortunately may take it into the address range where the
> stack lies.
>
> Testing:
>
> These changes have been tested on Linux v4.6-rc4 using 100000
> invocations of a program [1] that can display the offset of a process's
> brk...
>
> $for i in $(seq 100000); do ./aslr --report brk ; done
>
> This shows values of brk are evenly distributed over a 1GB range, both
> before and after this change.
>
> With Linux version 3.18 (where the collision of brk and stack can happen
> and this change limits brk to avoid that) the distribution of brk values
> after the change shows a slope where lower values for brk are more
> common and upper values have about half the frequency of those.
>
> [1] http://bazaar.launchpad.net/~ubuntu-bugcontrol/qa-regression-testing/master/files/2499/scripts/kernel-security/aslr/
>
> Signed-off-by: Jon Medhurst <tixy@linaro.org>
> Cc: <stable@vger.kernel.org> # 4.0 and earlier

Acked-by: Kees Cook <keescook@chromium.org>

-Kees

>
> ---
>
> Changes since RFC.
> - Fixed compilation errors (finger trouble preparing original email)
> - Updated commit message to included notes on testing
> - Added CC stable for Linux '4.0 and earlier'
>
>  arch/arm64/kernel/process.c | 24 ++++++++++++++++++------
>  1 file changed, 18 insertions(+), 6 deletions(-)
>
> diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
> index 8062482..26429a0 100644
> --- a/arch/arm64/kernel/process.c
> +++ b/arch/arm64/kernel/process.c
> @@ -382,13 +382,25 @@ unsigned long arch_align_stack(unsigned long sp)
>         return sp & ~0xf;
>  }
>
> -static unsigned long randomize_base(unsigned long base)
> +unsigned long arch_randomize_brk(struct mm_struct *mm)
>  {
> +       unsigned long base = mm->brk;
>         unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
> -       return randomize_range(base, range_end, 0) ? : base;
> -}
> +       unsigned long max_stack, range_limit;
>
> -unsigned long arch_randomize_brk(struct mm_struct *mm)
> -{
> -       return randomize_base(mm->brk);
> +       /*
> +        * Determine how much room we need to leave available for the stack.
> +        * We limit this to a reasonable value, because extremely large or
> +        * unlimited stacks are always going to bump up against brk at some
> +        * point and we don't want to fail to randomise brk in those cases.
> +        */
> +       max_stack = rlimit(RLIMIT_STACK);
> +       if (max_stack > SZ_128M)
> +               max_stack = SZ_128M;
> +
> +       range_limit = mm->start_stack - max_stack - 1;
> +       if (range_end > range_limit)
> +               range_end = range_limit;
> +
> +       return randomize_range(base, range_end, 0) ? : base;
>  }
> --
> 2.1.4
>
>



-- 
Kees Cook
Chrome OS & Brillo Security

[PATCH] arm64: Make arch_randomize_brk avoid stack area

[Catalin Marinas]

Hi Tixy,

On Wed, May 04, 2016 at 03:09:54PM +0100, Jon Medhurst (Tixy) wrote:
> Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
> from mmap ASLR") this problem shouldn't occur because the address chosen
> for loading binaries is well clear of the stack, however, prior to that
> the problem does occur because of the following...

[...]

> These changes have been tested on Linux v4.6-rc4 using 100000
> invocations of a program [1] that can display the offset of a process's
> brk...

[...]

> Signed-off-by: Jon Medhurst <tixy@linaro.org>
> Cc: <stable@vger.kernel.org> # 4.0 and earlier

I don't fully understand what we are supposed to do with this patch.
Should it only be applied to stable kernels prior to 4.0? Do we need it
in mainline? As you stated above, this problem does not exist in recent
kernels.

-- 
Catalin

[PATCH] arm64: Make arch_randomize_brk avoid stack area

[Jon Medhurst (Tixy)]

On Fri, 2016-05-06 at 12:19 +0100, Catalin Marinas wrote:
> Hi Tixy,
> 
> On Wed, May 04, 2016 at 03:09:54PM +0100, Jon Medhurst (Tixy) wrote:
> > Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
> > from mmap ASLR") this problem shouldn't occur because the address chosen
> > for loading binaries is well clear of the stack, however, prior to that
> > the problem does occur because of the following...
> 
> [...]
> 
> > These changes have been tested on Linux v4.6-rc4 using 100000
> > invocations of a program [1] that can display the offset of a process's
> > brk...
> 
> [...]
> 
> > Signed-off-by: Jon Medhurst <tixy@linaro.org>
> > Cc: <stable@vger.kernel.org> # 4.0 and earlier
> 
> I don't fully understand what we are supposed to do with this patch.
> Should it only be applied to stable kernels prior to 4.0? Do we need it
> in mainline? As you stated above, this problem does not exist in recent
> kernels.

Well, if you think it's worthwhile defensive programming against future
changes to elf loader, then it could go into latest kernels. Otherwise,
then yes, it's for Linux 4.0 and earlier. What's the process for that,
email it to stable at vger.kernel.org direct? Is that OK without an Ack
from an arm64 maintainer?

-- 
Tixy

[PATCH] arm64: Make arch_randomize_brk avoid stack area

[Catalin Marinas]

On Fri, May 06, 2016 at 12:51:00PM +0100, Jon Medhurst (Tixy) wrote:
> On Fri, 2016-05-06 at 12:19 +0100, Catalin Marinas wrote:
> > On Wed, May 04, 2016 at 03:09:54PM +0100, Jon Medhurst (Tixy) wrote:
> > > Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
> > > from mmap ASLR") this problem shouldn't occur because the address chosen
> > > for loading binaries is well clear of the stack, however, prior to that
> > > the problem does occur because of the following...
> > 
> > [...]
> > 
> > > These changes have been tested on Linux v4.6-rc4 using 100000
> > > invocations of a program [1] that can display the offset of a process's
> > > brk...
> > 
> > [...]
> > 
> > > Signed-off-by: Jon Medhurst <tixy@linaro.org>
> > > Cc: <stable@vger.kernel.org> # 4.0 and earlier
> > 
> > I don't fully understand what we are supposed to do with this patch.
> > Should it only be applied to stable kernels prior to 4.0? Do we need it
> > in mainline? As you stated above, this problem does not exist in recent
> > kernels.
> 
> Well, if you think it's worthwhile defensive programming against future
> changes to elf loader, then it could go into latest kernels.

I don't think we should bother with latest upstream. AFAICT, with
splitting ET_DYN ASLR from the mmap one, we shouldn't hit this issue.
And I wouldn't expect the two regions to be unified again in the future.

> Otherwise, then yes, it's for Linux 4.0 and earlier. What's the
> process for that, email it to stable at vger.kernel.org direct?

Usually emailing stable at vger.kernel.org with an explanation of why it is
not needed in mainline since it is not a back-port.

> Is that OK without an Ack from an arm64 maintainer?

I guess it's up to the stable maintainers but in any case:

Acked-by: Catalin Marinas <catalin.marinas@arm.com>

[PATCH for 4.0 and before] arm64: Make arch_randomize_brk avoid stack area

[Jon Medhurst (Tixy)]

From: Jon Medhurst <tixy@linaro.org>

When a process is created, various address randomisations could end up
colluding to place the address of brk in the stack memory. This would
mean processes making small heap based memory allocations are in danger
of having them overwriting, or overwritten by, the stack.

Another consequence, is that even for processes that make no use of
brk, the output of /proc/*/maps may show the stack area listed as
'[heap]' rather than '[stack]'. Apart from being misleading this causes
fatal errors with the Android run-time like:
"No [stack] line found in /proc/self/task/*/maps"

To prevent this problem pick a limit for brk that allows for the stack's
memory. At the same time we remove randomize_base() as that was only
used by arch_randomize_brk().

Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
from mmap ASLR") this problem shouldn't occur because the address chosen
for loading binaries is well clear of the stack, however, prior to that
the problem does occur because of the following...

The memory layout of a task is determined by arch_pick_mmap_layout. If
address randomisation is enabled (task has flag PF_RANDOMIZE) this sets
mmap_base to a random address at the top of task memory just below a
region calculated to allow for a stack which itself may have a random
base address. Any mmap operations that then happen which require an
address allocating will use the topdown allocation method, i.e. the
first allocated memory will be at the top of memory, just below the
area set aside for the stack.

When a relocatable binary is loaded into a new process by
load_elf_binary and randomised address are enabled, it uses a
'load_bias' of zero, so that when mmap is called to create a memory
region for it, a new address is picked (address zero not being
available). As this is the first memory region in the task, it gets the
region just below the stack, as described previously.

The loader then set's brk to the end of the elf data section, which will
be near the end of the loaded binary and then it calls
arch_randomize_brk. As this currently stands, this adds a random amount
to brk, which unfortunately may take it into the address range where the
stack lies.

Testing:

These changes have been tested on Linux 3.18 (where the collision of brk
and stack can happen) using 100000 invocations of a program [1] that can
display the offset of a process's brk...

$for i in $(seq 100000); do ./aslr --report brk ; done

This shows values of brk are evenly distributed over a 1GB range before
this change is applied. After this change the distribution shows a slope
where lower values for brk are more common and upper values have about
half the frequency of those.

[1] http://bazaar.launchpad.net/~ubuntu-bugcontrol/qa-regression-testing/master/files/2499/scripts/kernel-security/aslr/

Signed-off-by: Jon Medhurst <tixy@linaro.org>
Acked-by: Kees Cook <keescook@chromium.org>
Acked-by: Catalin Marinas <catalin.marinas@arm.com>
---

As mentioned in the commit message, the problem this patch fixes can't
occur in kernels with commit d1fd836dcf00, i.e Linux 4.1 and later.,
but earlier kernel versions need this fix.

I originally posted this to the ARM kernel list and arm64 maintainers,
see http://www.spinics.net/lists/arm-kernel/msg502238.html

 arch/arm64/kernel/process.c | 24 ++++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index 07c4c53..afea4b1 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -434,13 +434,25 @@ unsigned long arch_align_stack(unsigned long sp)
 	return sp & ~0xf;
 }
 
-static unsigned long randomize_base(unsigned long base)
+unsigned long arch_randomize_brk(struct mm_struct *mm)
 {
+	unsigned long base = mm->brk;
 	unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
-	return randomize_range(base, range_end, 0) ? : base;
-}
+	unsigned long max_stack, range_limit;
 
-unsigned long arch_randomize_brk(struct mm_struct *mm)
-{
-	return randomize_base(mm->brk);
+	/*
+	 * Determine how much room we need to leave available for the stack.
+	 * We limit this to a reasonable value, because extremely large or
+	 * unlimited stacks are always going to bump up against brk at some
+	 * point and we don't want to fail to randomise brk in those cases.
+	 */
+	max_stack = rlimit(RLIMIT_STACK);
+	if (max_stack > SZ_128M)
+		max_stack = SZ_128M;
+
+	range_limit = mm->start_stack - max_stack - 1;
+	if (range_end > range_limit)
+		range_end = range_limit;
+
+	return randomize_range(base, range_end, 0) ? : base;
 }
-- 
2.1.4

Patch "arm64: Make arch_randomize_brk avoid stack area" has been added to the 3.14-stable tree

[gregkh]

This is a note to let you know that I've just added the patch titled

    arm64: Make arch_randomize_brk avoid stack area

to the 3.14-stable tree which can be found at:
    http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
     arm64-make-arch_randomize_brk-avoid-stack-area.patch
and it can be found in the queue-3.14 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree,
please let <stable@vger.kernel.org> know about it.


>From tixy@linaro.org  Mon May 16 16:59:23 2016
From: "Jon Medhurst (Tixy)" <tixy@linaro.org>
Date: Tue, 10 May 2016 18:20:18 +0100
Subject: arm64: Make arch_randomize_brk avoid stack area
To: stable@vger.kernel.org
Cc: Catalin Marinas <catalin.marinas@arm.com>, Kees Cook <keescook@chromium.org>
Message-ID: <1462900818.3220.14.camel@linaro.org>


From: Jon Medhurst <tixy@linaro.org>

[As mentioned in the commit message, the problem this patch fixes can't
occur in kernels with commit d1fd836dcf00, i.e Linux 4.1 and later.,
but earlier kernel versions need this fix.]

When a process is created, various address randomisations could end up
colluding to place the address of brk in the stack memory. This would
mean processes making small heap based memory allocations are in danger
of having them overwriting, or overwritten by, the stack.

Another consequence, is that even for processes that make no use of
brk, the output of /proc/*/maps may show the stack area listed as
'[heap]' rather than '[stack]'. Apart from being misleading this causes
fatal errors with the Android run-time like:
"No [stack] line found in /proc/self/task/*/maps"

To prevent this problem pick a limit for brk that allows for the stack's
memory. At the same time we remove randomize_base() as that was only
used by arch_randomize_brk().

Note, in practice, since commit d1fd836dcf00 ("mm: split ET_DYN ASLR
from mmap ASLR") this problem shouldn't occur because the address chosen
for loading binaries is well clear of the stack, however, prior to that
the problem does occur because of the following...

The memory layout of a task is determined by arch_pick_mmap_layout. If
address randomisation is enabled (task has flag PF_RANDOMIZE) this sets
mmap_base to a random address at the top of task memory just below a
region calculated to allow for a stack which itself may have a random
base address. Any mmap operations that then happen which require an
address allocating will use the topdown allocation method, i.e. the
first allocated memory will be at the top of memory, just below the
area set aside for the stack.

When a relocatable binary is loaded into a new process by
load_elf_binary and randomised address are enabled, it uses a
'load_bias' of zero, so that when mmap is called to create a memory
region for it, a new address is picked (address zero not being
available). As this is the first memory region in the task, it gets the
region just below the stack, as described previously.

The loader then set's brk to the end of the elf data section, which will
be near the end of the loaded binary and then it calls
arch_randomize_brk. As this currently stands, this adds a random amount
to brk, which unfortunately may take it into the address range where the
stack lies.

Testing:

These changes have been tested on Linux 3.18 (where the collision of brk
and stack can happen) using 100000 invocations of a program [1] that can
display the offset of a process's brk...

$for i in $(seq 100000); do ./aslr --report brk ; done

This shows values of brk are evenly distributed over a 1GB range before
this change is applied. After this change the distribution shows a slope
where lower values for brk are more common and upper values have about
half the frequency of those.

[1] http://bazaar.launchpad.net/~ubuntu-bugcontrol/qa-regression-testing/master/files/2499/scripts/kernel-security/aslr/

Signed-off-by: Jon Medhurst <tixy@linaro.org>
Acked-by: Kees Cook <keescook@chromium.org>
Acked-by: Catalin Marinas <catalin.marinas@arm.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
---


I originally posted this to the ARM kernel list and arm64 maintainers,
see http://www.spinics.net/lists/arm-kernel/msg502238.html

 arch/arm64/kernel/process.c |   24 ++++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -350,15 +350,27 @@ unsigned long arch_align_stack(unsigned
 	return sp & ~0xf;
 }
 
-static unsigned long randomize_base(unsigned long base)
+unsigned long arch_randomize_brk(struct mm_struct *mm)
 {
+	unsigned long base = mm->brk;
 	unsigned long range_end = base + (STACK_RND_MASK << PAGE_SHIFT) + 1;
-	return randomize_range(base, range_end, 0) ? : base;
-}
+	unsigned long max_stack, range_limit;
 
-unsigned long arch_randomize_brk(struct mm_struct *mm)
-{
-	return randomize_base(mm->brk);
+	/*
+	 * Determine how much room we need to leave available for the stack.
+	 * We limit this to a reasonable value, because extremely large or
+	 * unlimited stacks are always going to bump up against brk at some
+	 * point and we don't want to fail to randomise brk in those cases.
+	 */
+	max_stack = rlimit(RLIMIT_STACK);
+	if (max_stack > SZ_128M)
+		max_stack = SZ_128M;
+
+	range_limit = mm->start_stack - max_stack - 1;
+	if (range_end > range_limit)
+		range_end = range_limit;
+
+	return randomize_range(base, range_end, 0) ? : base;
 }
 
 unsigned long randomize_et_dyn(unsigned long base)


Patches currently in stable-queue which might be from tixy@linaro.org are

queue-3.14/arm64-make-arch_randomize_brk-avoid-stack-area.patch