Re: [ 09/48] x86_64, vdso: Fix the vdso address randomization algorithm

[Ben Hutchings]

On Fri, 2015-05-15 at 10:05 +0200, Willy Tarreau wrote:
> 2.6.32-longterm review patch.  If anyone has any objections, please let me know.
> 
> ------------------
> 
> From: Andy Lutomirski <luto@xxxxxxxxxxxxxx>
> 
> commit 394f56fe480140877304d342dec46d50dc823d46 upstream
> 
> 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.
> 
> Reviewed-by: Kees Cook <keescook@xxxxxxxxxxxx>
> Cc: stable@xxxxxxxxxxxxxxx
> Signed-off-by: Andy Lutomirski <luto@xxxxxxxxxxxxxx>
> [bwh: Backported to 2.6.32:
>  - The whole file is only built for x86_64; adjust context and comment for this
>  - We don't have align_vdso_addr()]

Signed-off-by: Ben Hutchings <ben@xxxxxxxxxxxxxxx>

> Signed-off-by: Willy Tarreau <w@xxxxxx>
[...]

-- 
Ben Hutchings
It is impossible to make anything foolproof because fools are so ingenious.

Attachment: signature.asc
Description: This is a digitally signed message part