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

[Kees Cook]

On Wed, Feb 28, 2018 at 9:13 AM, Ilya Smith <blackzert@xxxxxxxxx> wrote:
>> On 27 Feb 2018, at 23:52, Kees Cook <keescook@xxxxxxxxxxxx> wrote:
>> What are the two phases here? Could this second one get collapsed into
>> the first?
>>
>
> Let me explain.
> 1. we use current implementation to get larger address. Remember it as
> âright_vmaâ.
> 2. we walk tree from mm->mmap what is lowest vma.
> 3. we check if current vma gap satisfies length and low/high constrains
> 4. if so, we call random() to decide if we choose it. This how we randomly choose vma and gap
> 5. we walk tree from lowest vma to highest and ignore subtrees with less gap.
> we do it until reach âright_vmaâ
>
> Once we found gap, we may randomly choose address inside it.
>
>>> +       addr = get_random_long() % ((high - low) >> PAGE_SHIFT);
>>> +       addr = low + (addr << PAGE_SHIFT);
>>> +       return addr;
>>>
>>
>> How large are the gaps intended to be? Looking at the gaps on
>> something like Xorg they differ a lot.
>
> Sorry, I canât get clue. What's the context? You tried patch or whats the case?

I was trying to understand the target entropy level, and I'm worried
it's a bit biased. For example, if the first allocation lands at 1/4th
of the memory space, the next allocation (IIUC) has a 50% chance of
falling on either side of it. If it goes on the small side, it then
has much less entropy than if it had gone on the other side. I think
this may be less entropy than choosing a random address and just
seeing if it fits or not. Dealing with collisions could be done either
by pushing the address until it doesn't collide or picking another
random address, etc. This is probably more expensive, though, since it
would need to walk the vma tree repeatedly. Anyway, I was ultimately
curious about your measured entropy and what alternatives you
considered.

-Kees

-- 
Kees Cook
Pixel Security