On Sat, Dec 20, 2014 at 9:40 AM, Andy Lutomirski <luto@xxxxxxxxxxxxxx> wrote:
> The theory behind vdso randomization is that it's mapped at a random
> offset above the top of the stack. To avoid wasting a page of
> memory for an extra page table, the vdso isn't supposed to extend
> past the lowest PMD into which it can fit. Other than that, the
> address should be a uniformly distributed address that meets all of
> the alignment requirements.
>
> The current algorithm is buggy: the vdso has about a 50% probability
> of being at the very end of a PMD. The current algorithm also has a
> decent chance of failing outright due to incorrect handling of the
> case where the top of the stack is near the top of its PMD.
>
> This fixes the implementation. The paxtest estimate of vdso
> "randomisation" improves from 11 bits to 18 bits. (Disclaimer: I
> don't know what the paxtest code is actually calculating.)
>
> It's worth noting that this algorithm is inherently biased: the vdso
> is more likely to end up near the end of its PMD than near the
> beginning. Ideally we would either nix the PMD sharing requirement
> or jointly randomize the vdso and the stack to reduce the bias.
>
> In the mean time, this is a considerable improvement with basically
> no risk of compatibility issues, since the allowed outputs of the
> algorithm are unchanged.
>
> As an easy test, doing this:
>
> for i in `seq 10000`
> do grep -P vdso /proc/self/maps |cut -d- -f1
> done |sort |uniq -d
>
> used to produce lots of output (1445 lines on my most recent run).
> A tiny subset looks like this:
>
> 7fffdfffe000
> 7fffe01fe000
> 7fffe05fe000
> 7fffe07fe000
> 7fffe09fe000
> 7fffe0bfe000
> 7fffe0dfe000
>
> Note the suspicious fe000 endings. With the fix, I get a much more
> palatable 76 repeated addresses.
>
> Cc: stable@xxxxxxxxxxxxxxx
> Signed-off-by: Andy Lutomirski <luto@xxxxxxxxxxxxxx>
Thanks for fixing this! :)
Reviewed-by: Kees Cook <keescook@xxxxxxxxxxxx>
-Kees
> ---
> arch/x86/vdso/vma.c | 45 +++++++++++++++++++++++++++++----------------
> 1 file changed, 29 insertions(+), 16 deletions(-)
>
> diff --git a/arch/x86/vdso/vma.c b/arch/x86/vdso/vma.c
> index 009495b9ab4b..1c9f750c3859 100644
> --- a/arch/x86/vdso/vma.c
> +++ b/arch/x86/vdso/vma.c
> @@ -41,12 +41,17 @@ void __init init_vdso_image(const struct vdso_image *image)
>
> struct linux_binprm;
>
> -/* Put the vdso above the (randomized) stack with another randomized offset.
> - This way there is no hole in the middle of address space.
> - To save memory make sure it is still in the same PTE as the stack top.
> - This doesn't give that many random bits.
> -
> - Only used for the 64-bit and x32 vdsos. */
> +/*
> + * Put the vdso above the (randomized) stack with another randomized
> + * offset. This way there is no hole in the middle of address space.
> + * To save memory make sure it is still in the same PTE as the stack
> + * top. This doesn't give that many random bits.
> + *
> + * Note that this algorithm is imperfect: the distribution of the vdso
> + * start address within a PMD is biased toward the end.
> + *
> + * Only used for the 64-bit and x32 vdsos.
> + */
> static unsigned long vdso_addr(unsigned long start, unsigned len)
> {
> #ifdef CONFIG_X86_32
> @@ -54,22 +59,30 @@ static unsigned long vdso_addr(unsigned long start, unsigned len)
> #else
> unsigned long addr, end;
> unsigned offset;
> - end = (start + PMD_SIZE - 1) & PMD_MASK;
> +
> + /*
> + * Round up the start address. It can start out unaligned as a result
> + * of stack start randomization.
> + */
> + start = PAGE_ALIGN(start);
> +
> + /* Round the lowest possible end address up to a PMD boundary. */
> + end = (start + len + PMD_SIZE - 1) & PMD_MASK;
> if (end >= TASK_SIZE_MAX)
> end = TASK_SIZE_MAX;
> end -= len;
> - /* This loses some more bits than a modulo, but is cheaper */
> - offset = get_random_int() & (PTRS_PER_PTE - 1);
> - addr = start + (offset << PAGE_SHIFT);
> - if (addr >= end)
> - addr = end;
> +
> + if (end > start) {
> + offset = get_random_int() % (((end - start) >> PAGE_SHIFT) + 1);
> + addr = start + (offset << PAGE_SHIFT);
> + } else {
> + addr = start;
> + }
>
> /*
> - * page-align it here so that get_unmapped_area doesn't
> - * align it wrongfully again to the next page. addr can come in 4K
> - * unaligned here as a result of stack start randomization.
> + * Forcibly align the final address in case we have a hardware
> + * issue that requires alignment for performance reasons.
> */
> - addr = PAGE_ALIGN(addr);
> addr = align_vdso_addr(addr);
>
> return addr;
> --
> 2.1.0
>
--
Kees Cook
Chrome OS Security
--
To unsubscribe from this list: send the line "unsubscribe stable" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html