Re: [RFC v1] mm: SLAB freelist randomization

[Kees Cook]

On Thu, Apr 7, 2016 at 2:14 PM, Jesper Dangaard Brouer
 wrote:
>
> On Wed, 6 Apr 2016 14:45:30 -0700 Kees Cook  wrote:
>
>> On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
> [...]
>> > re-used on slab creation for performance.
>>
>> I'd like to see some benchmark results for this so the Kconfig can
>> include the performance characteristics. I recommend using hackbench
>> and kernel build times with a before/after comparison.
>>
>
> It looks like it only happens on init, right? (Thus must bench tools
> might not be the right choice).

Oh! Yes, you're right. I entirely missed that detail. :) 0-cost
randomization! Sounds good to me. :)

-Kees

>
> My slab tools for benchmarking the fastpath is here:
>  
> https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_bulk_test01.c
>
> And I also carry a version of Christoph's slab bench tool:
>  
> https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_test.c
>
> --
> Best regards,
>   Jesper Dangaard Brouer
>   MSc.CS, Principal Kernel Engineer at Red Hat
>   Author of http://www.iptv-analyzer.org
>   LinkedIn: http://www.linkedin.com/in/brouer



-- 
Kees Cook
Chrome OS & Brillo Security

Re: [RFC v1] mm: SLAB freelist randomization

[Kees Cook]

On Thu, Apr 7, 2016 at 2:14 PM, Jesper Dangaard Brouer
 wrote:
>
> On Wed, 6 Apr 2016 14:45:30 -0700 Kees Cook  wrote:
>
>> On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
> [...]
>> > re-used on slab creation for performance.
>>
>> I'd like to see some benchmark results for this so the Kconfig can
>> include the performance characteristics. I recommend using hackbench
>> and kernel build times with a before/after comparison.
>>
>
> It looks like it only happens on init, right? (Thus must bench tools
> might not be the right choice).

Oh! Yes, you're right. I entirely missed that detail. :) 0-cost
randomization! Sounds good to me. :)

-Kees

>
> My slab tools for benchmarking the fastpath is here:
>  
> https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_bulk_test01.c
>
> And I also carry a version of Christoph's slab bench tool:
>  
> https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_test.c
>
> --
> Best regards,
>   Jesper Dangaard Brouer
>   MSc.CS, Principal Kernel Engineer at Red Hat
>   Author of http://www.iptv-analyzer.org
>   LinkedIn: http://www.linkedin.com/in/brouer



-- 
Kees Cook
Chrome OS & Brillo Security

Re: [RFC v1] mm: SLAB freelist randomization

[Jesper Dangaard Brouer]

On Wed, 6 Apr 2016 14:45:30 -0700 Kees Cook  wrote:

> On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
[...]
> > re-used on slab creation for performance.  
> 
> I'd like to see some benchmark results for this so the Kconfig can
> include the performance characteristics. I recommend using hackbench
> and kernel build times with a before/after comparison.
> 

It looks like it only happens on init, right? (Thus must bench tools
might not be the right choice).

My slab tools for benchmarking the fastpath is here:
 
https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_bulk_test01.c

And I also carry a version of Christoph's slab bench tool:
 
https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_test.c

-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Principal Kernel Engineer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [RFC v1] mm: SLAB freelist randomization

[Jesper Dangaard Brouer]

On Wed, 6 Apr 2016 14:45:30 -0700 Kees Cook  wrote:

> On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
[...]
> > re-used on slab creation for performance.  
> 
> I'd like to see some benchmark results for this so the Kconfig can
> include the performance characteristics. I recommend using hackbench
> and kernel build times with a before/after comparison.
> 

It looks like it only happens on init, right? (Thus must bench tools
might not be the right choice).

My slab tools for benchmarking the fastpath is here:
 
https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_bulk_test01.c

And I also carry a version of Christoph's slab bench tool:
 
https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_test.c

-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Principal Kernel Engineer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [kernel-hardening] Re: [RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

That's a use after free. The randomization of the freelist should not
have much effect on that. I was going to quote this exploit that is
applicable to SLAB as well:
https://jon.oberheide.org/blog/2010/09/10/linux-kernel-can-slub-overflow

Regards.
Thomas

On Thu, Apr 7, 2016 at 9:17 AM, Yves-Alexis Perez  wrote:
> On mer., 2016-04-06 at 14:45 -0700, Kees Cook wrote:
>> > This security feature reduces the predictability of
>> > the kernel slab allocator against heap overflows.
>>
>> I would add "... rendering attacks much less stable." And if you can
>> find a specific example exploit that is foiled by this, I would refer
>> to it.
>
> One good example might (or might not) be the keyring issue from earlier this
> year (CVE-2016-0728):
>
> http://perception-point.io/2016/01/14/analysis-and-exploitation-of-a-linux-ker
> nel-vulnerability-cve-2016-0728/
>
> Regards,
> --
> Yves-Alexis
>

Re: [kernel-hardening] Re: [RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

That's a use after free. The randomization of the freelist should not
have much effect on that. I was going to quote this exploit that is
applicable to SLAB as well:
https://jon.oberheide.org/blog/2010/09/10/linux-kernel-can-slub-overflow

Regards.
Thomas

On Thu, Apr 7, 2016 at 9:17 AM, Yves-Alexis Perez  wrote:
> On mer., 2016-04-06 at 14:45 -0700, Kees Cook wrote:
>> > This security feature reduces the predictability of
>> > the kernel slab allocator against heap overflows.
>>
>> I would add "... rendering attacks much less stable." And if you can
>> find a specific example exploit that is foiled by this, I would refer
>> to it.
>
> One good example might (or might not) be the keyring issue from earlier this
> year (CVE-2016-0728):
>
> http://perception-point.io/2016/01/14/analysis-and-exploitation-of-a-linux-ker
> nel-vulnerability-cve-2016-0728/
>
> Regards,
> --
> Yves-Alexis
>

Re: [kernel-hardening] Re: [RFC v1] mm: SLAB freelist randomization

[Yves-Alexis Perez]

On mer., 2016-04-06 at 14:45 -0700, Kees Cook wrote:
> > This security feature reduces the predictability of
> > the kernel slab allocator against heap overflows.
> 
> I would add "... rendering attacks much less stable." And if you can
> find a specific example exploit that is foiled by this, I would refer
> to it.

One good example might (or might not) be the keyring issue from earlier this
year (CVE-2016-0728):

http://perception-point.io/2016/01/14/analysis-and-exploitation-of-a-linux-ker
nel-vulnerability-cve-2016-0728/

Regards,
-- 
Yves-Alexis



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

Re: [kernel-hardening] Re: [RFC v1] mm: SLAB freelist randomization

[Yves-Alexis Perez]

On mer., 2016-04-06 at 14:45 -0700, Kees Cook wrote:
> > This security feature reduces the predictability of
> > the kernel slab allocator against heap overflows.
> 
> I would add "... rendering attacks much less stable." And if you can
> find a specific example exploit that is foiled by this, I would refer
> to it.

One good example might (or might not) be the keyring issue from earlier this
year (CVE-2016-0728):

http://perception-point.io/2016/01/14/analysis-and-exploitation-of-a-linux-ker
nel-vulnerability-cve-2016-0728/

Regards,
-- 
Yves-Alexis



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

Re: [RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

Thanks for the feedback Kees. I am preparing another RFC version.

For the config, I plan on creating an equivalent option for SLUB. Both
can benefit from randomizing their freelist order.

Thomas

On Wed, Apr 6, 2016 at 2:45 PM Kees Cook  wrote:
>
> On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
> > Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
> > SLAB freelist.
>
> It may be useful to describe _how_ it randomizes it (i.e. a high-level
> description of what needed changing).
>
> > This security feature reduces the predictability of
> > the kernel slab allocator against heap overflows.
>
> I would add "... rendering attacks much less stable." And if you can
> find a specific example exploit that is foiled by this, I would refer
> to it.
>
> > Randomized lists are pre-computed using a Fisher-Yates shuffle and
>
> Should the use of Fisher-Yates (over other things) be justified?
>
> > re-used on slab creation for performance.
>
> I'd like to see some benchmark results for this so the Kconfig can
> include the performance characteristics. I recommend using hackbench
> and kernel build times with a before/after comparison.
>
> > ---
> > Based on next-20160405
> > ---
> >  init/Kconfig |   9 
> >  mm/slab.c| 155 
> > +++
> >  2 files changed, 164 insertions(+)
> >
> > diff --git a/init/Kconfig b/init/Kconfig
> > index 0dfd09d..ee35418 100644
> > --- a/init/Kconfig
> > +++ b/init/Kconfig
> > @@ -1742,6 +1742,15 @@ config SLOB
> >
> >  endchoice
> >
> > +config FREELIST_RANDOM
>
> I think I would name this "SLAB_FREELIST_RANDOM" since it's
> SLAB-specific, unless you think it could be extended to the other
> allocators in the future too? (If so, I'd mention the naming choice in
> the commit log.)
>
> > +   default n
> > +   depends on SLAB
> > +   bool "SLAB freelist randomization"
> > +   help
> > + Randomizes the freelist order used on creating new SLABs. This
> > + security feature reduces the predictability of the kernel slab
> > + allocator against heap overflows.
> > +
> >  config SLUB_CPU_PARTIAL
> > default y
> > depends on SLUB && SMP
> > diff --git a/mm/slab.c b/mm/slab.c
> > index b70aabf..6f0d7be 100644
> > --- a/mm/slab.c
> > +++ b/mm/slab.c
> > @@ -1229,6 +1229,59 @@ static void __init set_up_node(struct kmem_cache 
> > *cachep, int index)
> > }
> >  }
> >
> > +#ifdef CONFIG_FREELIST_RANDOM
> > +/*
> > + * Master lists are pre-computed random lists
> > + * Lists of different sizes are used to optimize performance on different
> > + * SLAB object sizes per pages.
> > + */
> > +static freelist_idx_t master_list_2[2];
> > +static freelist_idx_t master_list_4[4];
> > +static freelist_idx_t master_list_8[8];
> > +static freelist_idx_t master_list_16[16];
> > +static freelist_idx_t master_list_32[32];
> > +static freelist_idx_t master_list_64[64];
> > +static freelist_idx_t master_list_128[128];
> > +static freelist_idx_t master_list_256[256];
> > +static struct m_list {
> > +   size_t count;
> > +   freelist_idx_t *list;
> > +} master_lists[] = {
> > +   { ARRAY_SIZE(master_list_2), master_list_2 },
> > +   { ARRAY_SIZE(master_list_4), master_list_4 },
> > +   { ARRAY_SIZE(master_list_8), master_list_8 },
> > +   { ARRAY_SIZE(master_list_16), master_list_16 },
> > +   { ARRAY_SIZE(master_list_32), master_list_32 },
> > +   { ARRAY_SIZE(master_list_64), master_list_64 },
> > +   { ARRAY_SIZE(master_list_128), master_list_128 },
> > +   { ARRAY_SIZE(master_list_256), master_list_256 },
> > +};
> > +
> > +void __init freelist_random_init(void)
> > +{
> > +   unsigned int seed;
> > +   size_t z, i, rand;
> > +   struct rnd_state slab_rand;
> > +
> > +   get_random_bytes_arch(, sizeof(seed));
> > +   prandom_seed_state(_rand, seed);
> > +
> > +   for (z = 0; z < ARRAY_SIZE(master_lists); z++) {
> > +   for (i = 0; i < master_lists[z].count; i++)
> > +   master_lists[z].list[i] = i;
> > +
> > +   /* Fisher-Yates shuffle */
> > +   for (i = master_lists[z].count - 1; i > 0; i--) {
> > +   rand = prandom_u32_state(_rand);
> > +   rand %= (i + 1);
> > +   swap(master_lists[z].list[i],
> > +   master_lists[z].list[rand]);
> > +   }
> > +   }
> > +}
>
> For below...
>
> #else
> static inline freelist_random_init(void) { }
>
> > +#endif /* CONFIG_FREELIST_RANDOM */
> > +
> > +
> >  /*
> >   * Initialisation.  Called after the page allocator have been initialised 
> > and
> >   * before smp_init().
> > @@ -1255,6 +1308,10 @@ void __init kmem_cache_init(void)
> > if (!slab_max_order_set && totalram_pages > (32 << 20) >> 
> > PAGE_SHIFT)
> > slab_max_order = 

Re: [RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

Thanks for the feedback Kees. I am preparing another RFC version.

For the config, I plan on creating an equivalent option for SLUB. Both
can benefit from randomizing their freelist order.

Thomas

On Wed, Apr 6, 2016 at 2:45 PM Kees Cook  wrote:
>
> On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
> > Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
> > SLAB freelist.
>
> It may be useful to describe _how_ it randomizes it (i.e. a high-level
> description of what needed changing).
>
> > This security feature reduces the predictability of
> > the kernel slab allocator against heap overflows.
>
> I would add "... rendering attacks much less stable." And if you can
> find a specific example exploit that is foiled by this, I would refer
> to it.
>
> > Randomized lists are pre-computed using a Fisher-Yates shuffle and
>
> Should the use of Fisher-Yates (over other things) be justified?
>
> > re-used on slab creation for performance.
>
> I'd like to see some benchmark results for this so the Kconfig can
> include the performance characteristics. I recommend using hackbench
> and kernel build times with a before/after comparison.
>
> > ---
> > Based on next-20160405
> > ---
> >  init/Kconfig |   9 
> >  mm/slab.c| 155 
> > +++
> >  2 files changed, 164 insertions(+)
> >
> > diff --git a/init/Kconfig b/init/Kconfig
> > index 0dfd09d..ee35418 100644
> > --- a/init/Kconfig
> > +++ b/init/Kconfig
> > @@ -1742,6 +1742,15 @@ config SLOB
> >
> >  endchoice
> >
> > +config FREELIST_RANDOM
>
> I think I would name this "SLAB_FREELIST_RANDOM" since it's
> SLAB-specific, unless you think it could be extended to the other
> allocators in the future too? (If so, I'd mention the naming choice in
> the commit log.)
>
> > +   default n
> > +   depends on SLAB
> > +   bool "SLAB freelist randomization"
> > +   help
> > + Randomizes the freelist order used on creating new SLABs. This
> > + security feature reduces the predictability of the kernel slab
> > + allocator against heap overflows.
> > +
> >  config SLUB_CPU_PARTIAL
> > default y
> > depends on SLUB && SMP
> > diff --git a/mm/slab.c b/mm/slab.c
> > index b70aabf..6f0d7be 100644
> > --- a/mm/slab.c
> > +++ b/mm/slab.c
> > @@ -1229,6 +1229,59 @@ static void __init set_up_node(struct kmem_cache 
> > *cachep, int index)
> > }
> >  }
> >
> > +#ifdef CONFIG_FREELIST_RANDOM
> > +/*
> > + * Master lists are pre-computed random lists
> > + * Lists of different sizes are used to optimize performance on different
> > + * SLAB object sizes per pages.
> > + */
> > +static freelist_idx_t master_list_2[2];
> > +static freelist_idx_t master_list_4[4];
> > +static freelist_idx_t master_list_8[8];
> > +static freelist_idx_t master_list_16[16];
> > +static freelist_idx_t master_list_32[32];
> > +static freelist_idx_t master_list_64[64];
> > +static freelist_idx_t master_list_128[128];
> > +static freelist_idx_t master_list_256[256];
> > +static struct m_list {
> > +   size_t count;
> > +   freelist_idx_t *list;
> > +} master_lists[] = {
> > +   { ARRAY_SIZE(master_list_2), master_list_2 },
> > +   { ARRAY_SIZE(master_list_4), master_list_4 },
> > +   { ARRAY_SIZE(master_list_8), master_list_8 },
> > +   { ARRAY_SIZE(master_list_16), master_list_16 },
> > +   { ARRAY_SIZE(master_list_32), master_list_32 },
> > +   { ARRAY_SIZE(master_list_64), master_list_64 },
> > +   { ARRAY_SIZE(master_list_128), master_list_128 },
> > +   { ARRAY_SIZE(master_list_256), master_list_256 },
> > +};
> > +
> > +void __init freelist_random_init(void)
> > +{
> > +   unsigned int seed;
> > +   size_t z, i, rand;
> > +   struct rnd_state slab_rand;
> > +
> > +   get_random_bytes_arch(, sizeof(seed));
> > +   prandom_seed_state(_rand, seed);
> > +
> > +   for (z = 0; z < ARRAY_SIZE(master_lists); z++) {
> > +   for (i = 0; i < master_lists[z].count; i++)
> > +   master_lists[z].list[i] = i;
> > +
> > +   /* Fisher-Yates shuffle */
> > +   for (i = master_lists[z].count - 1; i > 0; i--) {
> > +   rand = prandom_u32_state(_rand);
> > +   rand %= (i + 1);
> > +   swap(master_lists[z].list[i],
> > +   master_lists[z].list[rand]);
> > +   }
> > +   }
> > +}
>
> For below...
>
> #else
> static inline freelist_random_init(void) { }
>
> > +#endif /* CONFIG_FREELIST_RANDOM */
> > +
> > +
> >  /*
> >   * Initialisation.  Called after the page allocator have been initialised 
> > and
> >   * before smp_init().
> > @@ -1255,6 +1308,10 @@ void __init kmem_cache_init(void)
> > if (!slab_max_order_set && totalram_pages > (32 << 20) >> 
> > PAGE_SHIFT)
> > slab_max_order = SLAB_MAX_ORDER_HI;
> >
> > +#ifdef CONFIG_FREELIST_RANDOM
> 

Re: [RFC v1] mm: SLAB freelist randomization

[Kees Cook]

On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
> Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
> SLAB freelist.

It may be useful to describe _how_ it randomizes it (i.e. a high-level
description of what needed changing).

> This security feature reduces the predictability of
> the kernel slab allocator against heap overflows.

I would add "... rendering attacks much less stable." And if you can
find a specific example exploit that is foiled by this, I would refer
to it.

> Randomized lists are pre-computed using a Fisher-Yates shuffle and

Should the use of Fisher-Yates (over other things) be justified?

> re-used on slab creation for performance.

I'd like to see some benchmark results for this so the Kconfig can
include the performance characteristics. I recommend using hackbench
and kernel build times with a before/after comparison.

> ---
> Based on next-20160405
> ---
>  init/Kconfig |   9 
>  mm/slab.c| 155 
> +++
>  2 files changed, 164 insertions(+)
>
> diff --git a/init/Kconfig b/init/Kconfig
> index 0dfd09d..ee35418 100644
> --- a/init/Kconfig
> +++ b/init/Kconfig
> @@ -1742,6 +1742,15 @@ config SLOB
>
>  endchoice
>
> +config FREELIST_RANDOM

I think I would name this "SLAB_FREELIST_RANDOM" since it's
SLAB-specific, unless you think it could be extended to the other
allocators in the future too? (If so, I'd mention the naming choice in
the commit log.)

> +   default n
> +   depends on SLAB
> +   bool "SLAB freelist randomization"
> +   help
> + Randomizes the freelist order used on creating new SLABs. This
> + security feature reduces the predictability of the kernel slab
> + allocator against heap overflows.
> +
>  config SLUB_CPU_PARTIAL
> default y
> depends on SLUB && SMP
> diff --git a/mm/slab.c b/mm/slab.c
> index b70aabf..6f0d7be 100644
> --- a/mm/slab.c
> +++ b/mm/slab.c
> @@ -1229,6 +1229,59 @@ static void __init set_up_node(struct kmem_cache 
> *cachep, int index)
> }
>  }
>
> +#ifdef CONFIG_FREELIST_RANDOM
> +/*
> + * Master lists are pre-computed random lists
> + * Lists of different sizes are used to optimize performance on different
> + * SLAB object sizes per pages.
> + */
> +static freelist_idx_t master_list_2[2];
> +static freelist_idx_t master_list_4[4];
> +static freelist_idx_t master_list_8[8];
> +static freelist_idx_t master_list_16[16];
> +static freelist_idx_t master_list_32[32];
> +static freelist_idx_t master_list_64[64];
> +static freelist_idx_t master_list_128[128];
> +static freelist_idx_t master_list_256[256];
> +static struct m_list {
> +   size_t count;
> +   freelist_idx_t *list;
> +} master_lists[] = {
> +   { ARRAY_SIZE(master_list_2), master_list_2 },
> +   { ARRAY_SIZE(master_list_4), master_list_4 },
> +   { ARRAY_SIZE(master_list_8), master_list_8 },
> +   { ARRAY_SIZE(master_list_16), master_list_16 },
> +   { ARRAY_SIZE(master_list_32), master_list_32 },
> +   { ARRAY_SIZE(master_list_64), master_list_64 },
> +   { ARRAY_SIZE(master_list_128), master_list_128 },
> +   { ARRAY_SIZE(master_list_256), master_list_256 },
> +};
> +
> +void __init freelist_random_init(void)
> +{
> +   unsigned int seed;
> +   size_t z, i, rand;
> +   struct rnd_state slab_rand;
> +
> +   get_random_bytes_arch(, sizeof(seed));
> +   prandom_seed_state(_rand, seed);
> +
> +   for (z = 0; z < ARRAY_SIZE(master_lists); z++) {
> +   for (i = 0; i < master_lists[z].count; i++)
> +   master_lists[z].list[i] = i;
> +
> +   /* Fisher-Yates shuffle */
> +   for (i = master_lists[z].count - 1; i > 0; i--) {
> +   rand = prandom_u32_state(_rand);
> +   rand %= (i + 1);
> +   swap(master_lists[z].list[i],
> +   master_lists[z].list[rand]);
> +   }
> +   }
> +}

For below...

#else
static inline freelist_random_init(void) { }

> +#endif /* CONFIG_FREELIST_RANDOM */
> +
> +
>  /*
>   * Initialisation.  Called after the page allocator have been initialised and
>   * before smp_init().
> @@ -1255,6 +1308,10 @@ void __init kmem_cache_init(void)
> if (!slab_max_order_set && totalram_pages > (32 << 20) >> PAGE_SHIFT)
> slab_max_order = SLAB_MAX_ORDER_HI;
>
> +#ifdef CONFIG_FREELIST_RANDOM
> +   freelist_random_init();
> +#endif /* CONFIG_FREELIST_RANDOM */

Rather than these embedded ifdefs, I would create stub function at the
top, as above.

> +
> /* Bootstrap is tricky, because several objects are allocated
>  * from caches that do not exist yet:
>  * 1) initialize the kmem_cache cache: it contains the struct
> @@ -2442,6 +2499,98 @@ static void cache_init_objs_debug(struct kmem_cache 
> *cachep, struct page *page)
>  #endif
>  }
>
> +#ifdef 

Re: [RFC v1] mm: SLAB freelist randomization

[Kees Cook]

On Wed, Apr 6, 2016 at 12:35 PM, Thomas Garnier  wrote:
> Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
> SLAB freelist.

It may be useful to describe _how_ it randomizes it (i.e. a high-level
description of what needed changing).

> This security feature reduces the predictability of
> the kernel slab allocator against heap overflows.

I would add "... rendering attacks much less stable." And if you can
find a specific example exploit that is foiled by this, I would refer
to it.

> Randomized lists are pre-computed using a Fisher-Yates shuffle and

Should the use of Fisher-Yates (over other things) be justified?

> re-used on slab creation for performance.

I'd like to see some benchmark results for this so the Kconfig can
include the performance characteristics. I recommend using hackbench
and kernel build times with a before/after comparison.

> ---
> Based on next-20160405
> ---
>  init/Kconfig |   9 
>  mm/slab.c| 155 
> +++
>  2 files changed, 164 insertions(+)
>
> diff --git a/init/Kconfig b/init/Kconfig
> index 0dfd09d..ee35418 100644
> --- a/init/Kconfig
> +++ b/init/Kconfig
> @@ -1742,6 +1742,15 @@ config SLOB
>
>  endchoice
>
> +config FREELIST_RANDOM

I think I would name this "SLAB_FREELIST_RANDOM" since it's
SLAB-specific, unless you think it could be extended to the other
allocators in the future too? (If so, I'd mention the naming choice in
the commit log.)

> +   default n
> +   depends on SLAB
> +   bool "SLAB freelist randomization"
> +   help
> + Randomizes the freelist order used on creating new SLABs. This
> + security feature reduces the predictability of the kernel slab
> + allocator against heap overflows.
> +
>  config SLUB_CPU_PARTIAL
> default y
> depends on SLUB && SMP
> diff --git a/mm/slab.c b/mm/slab.c
> index b70aabf..6f0d7be 100644
> --- a/mm/slab.c
> +++ b/mm/slab.c
> @@ -1229,6 +1229,59 @@ static void __init set_up_node(struct kmem_cache 
> *cachep, int index)
> }
>  }
>
> +#ifdef CONFIG_FREELIST_RANDOM
> +/*
> + * Master lists are pre-computed random lists
> + * Lists of different sizes are used to optimize performance on different
> + * SLAB object sizes per pages.
> + */
> +static freelist_idx_t master_list_2[2];
> +static freelist_idx_t master_list_4[4];
> +static freelist_idx_t master_list_8[8];
> +static freelist_idx_t master_list_16[16];
> +static freelist_idx_t master_list_32[32];
> +static freelist_idx_t master_list_64[64];
> +static freelist_idx_t master_list_128[128];
> +static freelist_idx_t master_list_256[256];
> +static struct m_list {
> +   size_t count;
> +   freelist_idx_t *list;
> +} master_lists[] = {
> +   { ARRAY_SIZE(master_list_2), master_list_2 },
> +   { ARRAY_SIZE(master_list_4), master_list_4 },
> +   { ARRAY_SIZE(master_list_8), master_list_8 },
> +   { ARRAY_SIZE(master_list_16), master_list_16 },
> +   { ARRAY_SIZE(master_list_32), master_list_32 },
> +   { ARRAY_SIZE(master_list_64), master_list_64 },
> +   { ARRAY_SIZE(master_list_128), master_list_128 },
> +   { ARRAY_SIZE(master_list_256), master_list_256 },
> +};
> +
> +void __init freelist_random_init(void)
> +{
> +   unsigned int seed;
> +   size_t z, i, rand;
> +   struct rnd_state slab_rand;
> +
> +   get_random_bytes_arch(, sizeof(seed));
> +   prandom_seed_state(_rand, seed);
> +
> +   for (z = 0; z < ARRAY_SIZE(master_lists); z++) {
> +   for (i = 0; i < master_lists[z].count; i++)
> +   master_lists[z].list[i] = i;
> +
> +   /* Fisher-Yates shuffle */
> +   for (i = master_lists[z].count - 1; i > 0; i--) {
> +   rand = prandom_u32_state(_rand);
> +   rand %= (i + 1);
> +   swap(master_lists[z].list[i],
> +   master_lists[z].list[rand]);
> +   }
> +   }
> +}

For below...

#else
static inline freelist_random_init(void) { }

> +#endif /* CONFIG_FREELIST_RANDOM */
> +
> +
>  /*
>   * Initialisation.  Called after the page allocator have been initialised and
>   * before smp_init().
> @@ -1255,6 +1308,10 @@ void __init kmem_cache_init(void)
> if (!slab_max_order_set && totalram_pages > (32 << 20) >> PAGE_SHIFT)
> slab_max_order = SLAB_MAX_ORDER_HI;
>
> +#ifdef CONFIG_FREELIST_RANDOM
> +   freelist_random_init();
> +#endif /* CONFIG_FREELIST_RANDOM */

Rather than these embedded ifdefs, I would create stub function at the
top, as above.

> +
> /* Bootstrap is tricky, because several objects are allocated
>  * from caches that do not exist yet:
>  * 1) initialize the kmem_cache cache: it contains the struct
> @@ -2442,6 +2499,98 @@ static void cache_init_objs_debug(struct kmem_cache 
> *cachep, struct page *page)
>  #endif
>  }
>
> +#ifdef CONFIG_FREELIST_RANDOM
> 

Re: [kernel-hardening] [RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

Yes, sorry about that. It will be in the next RFC or PATCH.

On Wed, Apr 6, 2016 at 1:54 PM, Greg KH  wrote:
> On Wed, Apr 06, 2016 at 12:35:48PM -0700, Thomas Garnier wrote:
>> Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
>> SLAB freelist. This security feature reduces the predictability of
>> the kernel slab allocator against heap overflows.
>>
>> Randomized lists are pre-computed using a Fisher-Yates shuffle and
>> re-used on slab creation for performance.
>> ---
>> Based on next-20160405
>> ---
>
> No signed-off-by:?
>

Re: [kernel-hardening] [RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

Yes, sorry about that. It will be in the next RFC or PATCH.

On Wed, Apr 6, 2016 at 1:54 PM, Greg KH  wrote:
> On Wed, Apr 06, 2016 at 12:35:48PM -0700, Thomas Garnier wrote:
>> Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
>> SLAB freelist. This security feature reduces the predictability of
>> the kernel slab allocator against heap overflows.
>>
>> Randomized lists are pre-computed using a Fisher-Yates shuffle and
>> re-used on slab creation for performance.
>> ---
>> Based on next-20160405
>> ---
>
> No signed-off-by:?
>

Re: [kernel-hardening] [RFC v1] mm: SLAB freelist randomization

[Greg KH]

On Wed, Apr 06, 2016 at 12:35:48PM -0700, Thomas Garnier wrote:
> Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
> SLAB freelist. This security feature reduces the predictability of
> the kernel slab allocator against heap overflows.
> 
> Randomized lists are pre-computed using a Fisher-Yates shuffle and
> re-used on slab creation for performance.
> ---
> Based on next-20160405
> ---

No signed-off-by:?

Re: [kernel-hardening] [RFC v1] mm: SLAB freelist randomization

[Greg KH]

On Wed, Apr 06, 2016 at 12:35:48PM -0700, Thomas Garnier wrote:
> Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
> SLAB freelist. This security feature reduces the predictability of
> the kernel slab allocator against heap overflows.
> 
> Randomized lists are pre-computed using a Fisher-Yates shuffle and
> re-used on slab creation for performance.
> ---
> Based on next-20160405
> ---

No signed-off-by:?

[RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
SLAB freelist. This security feature reduces the predictability of
the kernel slab allocator against heap overflows.

Randomized lists are pre-computed using a Fisher-Yates shuffle and
re-used on slab creation for performance.
---
Based on next-20160405
---
 init/Kconfig |   9 
 mm/slab.c| 155 +++
 2 files changed, 164 insertions(+)

diff --git a/init/Kconfig b/init/Kconfig
index 0dfd09d..ee35418 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1742,6 +1742,15 @@ config SLOB
 
 endchoice
 
+config FREELIST_RANDOM
+   default n
+   depends on SLAB
+   bool "SLAB freelist randomization"
+   help
+ Randomizes the freelist order used on creating new SLABs. This
+ security feature reduces the predictability of the kernel slab
+ allocator against heap overflows.
+
 config SLUB_CPU_PARTIAL
default y
depends on SLUB && SMP
diff --git a/mm/slab.c b/mm/slab.c
index b70aabf..6f0d7be 100644
--- a/mm/slab.c
+++ b/mm/slab.c
@@ -1229,6 +1229,59 @@ static void __init set_up_node(struct kmem_cache 
*cachep, int index)
}
 }
 
+#ifdef CONFIG_FREELIST_RANDOM
+/*
+ * Master lists are pre-computed random lists
+ * Lists of different sizes are used to optimize performance on different
+ * SLAB object sizes per pages.
+ */
+static freelist_idx_t master_list_2[2];
+static freelist_idx_t master_list_4[4];
+static freelist_idx_t master_list_8[8];
+static freelist_idx_t master_list_16[16];
+static freelist_idx_t master_list_32[32];
+static freelist_idx_t master_list_64[64];
+static freelist_idx_t master_list_128[128];
+static freelist_idx_t master_list_256[256];
+static struct m_list {
+   size_t count;
+   freelist_idx_t *list;
+} master_lists[] = {
+   { ARRAY_SIZE(master_list_2), master_list_2 },
+   { ARRAY_SIZE(master_list_4), master_list_4 },
+   { ARRAY_SIZE(master_list_8), master_list_8 },
+   { ARRAY_SIZE(master_list_16), master_list_16 },
+   { ARRAY_SIZE(master_list_32), master_list_32 },
+   { ARRAY_SIZE(master_list_64), master_list_64 },
+   { ARRAY_SIZE(master_list_128), master_list_128 },
+   { ARRAY_SIZE(master_list_256), master_list_256 },
+};
+
+void __init freelist_random_init(void)
+{
+   unsigned int seed;
+   size_t z, i, rand;
+   struct rnd_state slab_rand;
+
+   get_random_bytes_arch(, sizeof(seed));
+   prandom_seed_state(_rand, seed);
+
+   for (z = 0; z < ARRAY_SIZE(master_lists); z++) {
+   for (i = 0; i < master_lists[z].count; i++)
+   master_lists[z].list[i] = i;
+
+   /* Fisher-Yates shuffle */
+   for (i = master_lists[z].count - 1; i > 0; i--) {
+   rand = prandom_u32_state(_rand);
+   rand %= (i + 1);
+   swap(master_lists[z].list[i],
+   master_lists[z].list[rand]);
+   }
+   }
+}
+#endif /* CONFIG_FREELIST_RANDOM */
+
+
 /*
  * Initialisation.  Called after the page allocator have been initialised and
  * before smp_init().
@@ -1255,6 +1308,10 @@ void __init kmem_cache_init(void)
if (!slab_max_order_set && totalram_pages > (32 << 20) >> PAGE_SHIFT)
slab_max_order = SLAB_MAX_ORDER_HI;
 
+#ifdef CONFIG_FREELIST_RANDOM
+   freelist_random_init();
+#endif /* CONFIG_FREELIST_RANDOM */
+
/* Bootstrap is tricky, because several objects are allocated
 * from caches that do not exist yet:
 * 1) initialize the kmem_cache cache: it contains the struct
@@ -2442,6 +2499,98 @@ static void cache_init_objs_debug(struct kmem_cache 
*cachep, struct page *page)
 #endif
 }
 
+#ifdef CONFIG_FREELIST_RANDOM
+enum master_type {
+   match,
+   less,
+   more
+};
+
+struct random_mng {
+   unsigned int padding;
+   unsigned int pos;
+   unsigned int count;
+   struct m_list master_list;
+   unsigned int master_count;
+   enum master_type type;
+};
+
+static void random_mng_initialize(struct random_mng *mng, unsigned int count)
+{
+   unsigned int idx;
+   const unsigned int last_idx = ARRAY_SIZE(master_lists) - 1;
+
+   memset(mng, 0, sizeof(*mng));
+   mng->count = count;
+   mng->pos = 0;
+   /* count is >= 2 */
+   idx = ilog2(count) - 1;
+   if (idx >= last_idx)
+   idx = last_idx;
+   else if (roundup_pow_of_two(idx + 1) != count)
+   idx++;
+   mng->master_list = master_lists[idx];
+   if (mng->master_list.count == mng->count)
+   mng->type = match;
+   else if (mng->master_list.count > mng->count)
+   mng->type = more;
+   else
+   mng->type = less;
+}
+
+static freelist_idx_t get_next_entry(struct random_mng *mng)
+{
+   if (mng->type == less && mng->pos == mng->master_list.count) {
+   

[RFC v1] mm: SLAB freelist randomization

[Thomas Garnier]

Provide an optional config (CONFIG_FREELIST_RANDOM) to randomize the
SLAB freelist. This security feature reduces the predictability of
the kernel slab allocator against heap overflows.

Randomized lists are pre-computed using a Fisher-Yates shuffle and
re-used on slab creation for performance.
---
Based on next-20160405
---
 init/Kconfig |   9 
 mm/slab.c| 155 +++
 2 files changed, 164 insertions(+)

diff --git a/init/Kconfig b/init/Kconfig
index 0dfd09d..ee35418 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1742,6 +1742,15 @@ config SLOB
 
 endchoice
 
+config FREELIST_RANDOM
+   default n
+   depends on SLAB
+   bool "SLAB freelist randomization"
+   help
+ Randomizes the freelist order used on creating new SLABs. This
+ security feature reduces the predictability of the kernel slab
+ allocator against heap overflows.
+
 config SLUB_CPU_PARTIAL
default y
depends on SLUB && SMP
diff --git a/mm/slab.c b/mm/slab.c
index b70aabf..6f0d7be 100644
--- a/mm/slab.c
+++ b/mm/slab.c
@@ -1229,6 +1229,59 @@ static void __init set_up_node(struct kmem_cache 
*cachep, int index)
}
 }
 
+#ifdef CONFIG_FREELIST_RANDOM
+/*
+ * Master lists are pre-computed random lists
+ * Lists of different sizes are used to optimize performance on different
+ * SLAB object sizes per pages.
+ */
+static freelist_idx_t master_list_2[2];
+static freelist_idx_t master_list_4[4];
+static freelist_idx_t master_list_8[8];
+static freelist_idx_t master_list_16[16];
+static freelist_idx_t master_list_32[32];
+static freelist_idx_t master_list_64[64];
+static freelist_idx_t master_list_128[128];
+static freelist_idx_t master_list_256[256];
+static struct m_list {
+   size_t count;
+   freelist_idx_t *list;
+} master_lists[] = {
+   { ARRAY_SIZE(master_list_2), master_list_2 },
+   { ARRAY_SIZE(master_list_4), master_list_4 },
+   { ARRAY_SIZE(master_list_8), master_list_8 },
+   { ARRAY_SIZE(master_list_16), master_list_16 },
+   { ARRAY_SIZE(master_list_32), master_list_32 },
+   { ARRAY_SIZE(master_list_64), master_list_64 },
+   { ARRAY_SIZE(master_list_128), master_list_128 },
+   { ARRAY_SIZE(master_list_256), master_list_256 },
+};
+
+void __init freelist_random_init(void)
+{
+   unsigned int seed;
+   size_t z, i, rand;
+   struct rnd_state slab_rand;
+
+   get_random_bytes_arch(, sizeof(seed));
+   prandom_seed_state(_rand, seed);
+
+   for (z = 0; z < ARRAY_SIZE(master_lists); z++) {
+   for (i = 0; i < master_lists[z].count; i++)
+   master_lists[z].list[i] = i;
+
+   /* Fisher-Yates shuffle */
+   for (i = master_lists[z].count - 1; i > 0; i--) {
+   rand = prandom_u32_state(_rand);
+   rand %= (i + 1);
+   swap(master_lists[z].list[i],
+   master_lists[z].list[rand]);
+   }
+   }
+}
+#endif /* CONFIG_FREELIST_RANDOM */
+
+
 /*
  * Initialisation.  Called after the page allocator have been initialised and
  * before smp_init().
@@ -1255,6 +1308,10 @@ void __init kmem_cache_init(void)
if (!slab_max_order_set && totalram_pages > (32 << 20) >> PAGE_SHIFT)
slab_max_order = SLAB_MAX_ORDER_HI;
 
+#ifdef CONFIG_FREELIST_RANDOM
+   freelist_random_init();
+#endif /* CONFIG_FREELIST_RANDOM */
+
/* Bootstrap is tricky, because several objects are allocated
 * from caches that do not exist yet:
 * 1) initialize the kmem_cache cache: it contains the struct
@@ -2442,6 +2499,98 @@ static void cache_init_objs_debug(struct kmem_cache 
*cachep, struct page *page)
 #endif
 }
 
+#ifdef CONFIG_FREELIST_RANDOM
+enum master_type {
+   match,
+   less,
+   more
+};
+
+struct random_mng {
+   unsigned int padding;
+   unsigned int pos;
+   unsigned int count;
+   struct m_list master_list;
+   unsigned int master_count;
+   enum master_type type;
+};
+
+static void random_mng_initialize(struct random_mng *mng, unsigned int count)
+{
+   unsigned int idx;
+   const unsigned int last_idx = ARRAY_SIZE(master_lists) - 1;
+
+   memset(mng, 0, sizeof(*mng));
+   mng->count = count;
+   mng->pos = 0;
+   /* count is >= 2 */
+   idx = ilog2(count) - 1;
+   if (idx >= last_idx)
+   idx = last_idx;
+   else if (roundup_pow_of_two(idx + 1) != count)
+   idx++;
+   mng->master_list = master_lists[idx];
+   if (mng->master_list.count == mng->count)
+   mng->type = match;
+   else if (mng->master_list.count > mng->count)
+   mng->type = more;
+   else
+   mng->type = less;
+}
+
+static freelist_idx_t get_next_entry(struct random_mng *mng)
+{
+   if (mng->type == less && mng->pos == mng->master_list.count) {
+