Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
From:   Andy Lutomirski <luto@amacapital.net>
Mime-Version: 1.0 (1.0)
Subject: Re: [PATCH v5] mm: Optional full ASLR for mmap(), mremap(), vdso and stack
Date:   Thu, 3 Dec 2020 09:42:54 -0800
Message-Id: <1CB9B4D1-1E32-42DC-A4E9-6E53C85365BF@amacapital.net>
References: <871rg6yf1i.fsf@oldenburg2.str.redhat.com>
Cc:     Topi Miettinen <toiwoton@gmail.com>,
        linux-hardening@vger.kernel.org, akpm@linux-foundation.org,
        linux-mm@kvack.org, linux-kernel@vger.kernel.org,
        Jann Horn <jannh@google.com>,
        Kees Cook <keescook@chromium.org>,
        Matthew Wilcox <willy@infradead.org>,
        Mike Rapoport <rppt@kernel.org>,
        Linux API <linux-api@vger.kernel.org>
In-Reply-To: <871rg6yf1i.fsf@oldenburg2.str.redhat.com>
To:     Florian Weimer <fweimer@redhat.com>
Precedence: bulk


> On Dec 3, 2020, at 9:29 AM, Florian Weimer <fweimer@redhat.com> wrote:
>=20
> =EF=BB=BF* Andy Lutomirski:
>=20
>> If you want a 4GB allocation to succeed, you can only divide the
>> address space into 32k fragments.  Or, a little more precisely, if you
>> want a randomly selected 4GB region to be empty, any other allocation
>> has a 1/32k chance of being in the way.  (Rough numbers =E2=80=94 I=E2=80=
=99m ignoring
>> effects of the beginning and end of the address space, and I=E2=80=99m
>> ignoring the size of a potential conflicting allocation.).
>=20
> I think the probability distribution is way more advantageous than that
> because it is unlikely that 32K allocations are all exactly spaced 4 GB
> apart.  (And with 32K allocations, you are close to the VMA limit anyway.)=


I=E2=80=99m assuming the naive algorithm of choosing an address and trying i=
t.  Actually looking for a big enough gap would be more reliable.

I suspect that something much more clever could be done in which the heap is=
 divided up into a few independently randomized sections and heap pages are r=
andomized within the sections might do much better. There should certainly b=
e a lot of room for something between what we have now and a fully randomize=
d scheme.

It might also be worth looking at what other OSes do.=