From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Message-ID: <1431723779.6315.127.camel@decadent.org.uk>
Subject: Re: [ 09/48] x86_64, vdso: Fix the vdso address randomization
 algorithm
From: Ben Hutchings <ben@decadent.org.uk>
To: Willy Tarreau <w@1wt.eu>
Cc: linux-kernel@vger.kernel.org, stable@vger.kernel.org,
	Kees Cook <keescook@chromium.org>,
	Andy Lutomirski <luto@amacapital.net>
Date: Fri, 15 May 2015 22:02:59 +0100
In-Reply-To: <20150515080530.680848837@1wt.eu>
References: <20150515080530.680848837@1wt.eu>
Content-Type: multipart/signed; micalg="pgp-sha512";
	protocol="application/pgp-signature"; boundary="=-WVJ06AS9ynXLYt9SBgIG"
Mime-Version: 1.0
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <stable.vger.kernel.org>


--=-WVJ06AS9ynXLYt9SBgIG
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 m=
e know.
>=20
> ------------------
>=20
> From: Andy Lutomirski <luto@amacapital.net>
>=20
> commit 394f56fe480140877304d342dec46d50dc823d46 upstream
>=20
> 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.
>=20
> 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.
>=20
> 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.)
>=20
> 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.
>=20
> 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.
>=20
> As an easy test, doing this:
>=20
> for i in `seq 10000`
>   do grep -P vdso /proc/self/maps |cut -d- -f1
> done |sort |uniq -d
>=20
> used to produce lots of output (1445 lines on my most recent run).
> A tiny subset looks like this:
>=20
> 7fffdfffe000
> 7fffe01fe000
> 7fffe05fe000
> 7fffe07fe000
> 7fffe09fe000
> 7fffe0bfe000
> 7fffe0dfe000
>=20
> Note the suspicious fe000 endings.  With the fix, I get a much more
> palatable 76 repeated addresses.
>=20
> Reviewed-by: Kees Cook <keescook@chromium.org>
> Cc: stable@vger.kernel.org
> Signed-off-by: Andy Lutomirski <luto@amacapital.net>
> [bwh: Backported to 2.6.32:
>  - The whole file is only built for x86_64; adjust context and comment fo=
r this
>  - We don't have align_vdso_addr()]

Signed-off-by: Ben Hutchings <ben@decadent.org.uk>

> Signed-off-by: Willy Tarreau <w@1wt.eu>
[...]

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

--=-WVJ06AS9ynXLYt9SBgIG
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIVAwUAVVZfCOe/yOyVhhEJAQoLCRAAtbq9TdJJABy7aK6wysnLLSj48iFtNvwe
D+Q2KVJfQbe59T3mfFhfrT15NgKOZS3Lwe5qodcLXh0pThqpi49nxOUNMs73UcDe
2P0jtqtaUycPgiXUdf1xnWU6X4YVNv4B+V6FJXx9W3RD4Vjk3xFzud+LylQgdvB0
9fU/HjXqeyqUleQ1z6LOlZ032kg0S96WVZO8xAx0/vFpoATlKjh7Em59m+sIGME1
PuZpDuLao3FDYesK7W9hPt4LWWYKHuWvZBL9uW1gTGvNXsLCtqBo2In5ePcTWZXI
41PTnEas1vJ9m0n3mM7hYsyCaDMiJW2BfRJ+MQWrmddaKw2TSnpCDrAgmuD2uHPN
uPjucnSRlnH1jiNr+tVPrHPJJjBrkaHFws2kQFmOKDNCUNEpiMIIqoPK8bQ/YL3W
5rWBa5KRXmBTqImBDHddMmf5CNmAt767a7aK9Ltd6Ml46oLGf2ahNHGZxqcngh+C
B5Ti21P7Qec6CyZX1jk2QR/g01IYo1yszUjUcx+0Lwgq07OCOFgRaxTMRMhQ2Rt1
FigFAsG9AYvgcS80N0vV93yV7vyWD79AzMYiFM1HiMU8g9yVLH65LNdTls0lwTrG
RiXwH6Fvev+YqBM54EVw6dKGDRGT4UytaKtRXmk8kJhMBIkrlCMpMICUXJ7TDzcA
wR6OGBIuTsc=
=BUR9
-----END PGP SIGNATURE-----

--=-WVJ06AS9ynXLYt9SBgIG--