Skip to content
  • Thomas Garnier's avatar
    mm: SLAB freelist randomization · c7ce4f60
    Thomas Garnier authored
    Provides an optional config (CONFIG_SLAB_FREELIST_RANDOM) to randomize
    the SLAB freelist.  The list is randomized during initialization of a
    new set of pages.  The order on different freelist sizes is pre-computed
    at boot for performance.  Each kmem_cache has its own randomized
    freelist.  Before pre-computed lists are available freelists are
    generated dynamically.  This security feature reduces the predictability
    of the kernel SLAB allocator against heap overflows rendering attacks
    much less stable.
    
    For example this attack against SLUB (also applicable against SLAB)
    would be affected:
    
      https://jon.oberheide.org/blog/2010/09/10/linux-kernel-can-slub-overflow/
    
    
    
    Also, since v4.6 the freelist was moved at the end of the SLAB.  It
    means a controllable heap is opened to new attacks not yet publicly
    discussed.  A kernel heap overflow can be transformed to multiple
    use-after-free.  This feature makes this type of attack harder too.
    
    To generate entropy, we use get_random_bytes_arch because 0 bits of
    entropy is available in the boot stage.  In the worse case this function
    will fallback to the get_random_bytes sub API.  We also generate a shift
    random number to shift pre-computed freelist for each new set of pages.
    
    The config option name is not specific to the SLAB as this approach will
    be extended to other allocators like SLUB.
    
    Performance results highlighted no major changes:
    
    Hackbench (running 90 10 times):
    
      Before average: 0.0698
      After average: 0.0663 (-5.01%)
    
    slab_test 1 run on boot.  Difference only seen on the 2048 size test
    being the worse case scenario covered by freelist randomization.  New
    slab pages are constantly being created on the 10000 allocations.
    Variance should be mainly due to getting new pages every few
    allocations.
    
    Before:
    
      Single thread testing
      =====================
      1. Kmalloc: Repeatedly allocate then free test
      10000 times kmalloc(8) -> 99 cycles kfree -> 112 cycles
      10000 times kmalloc(16) -> 109 cycles kfree -> 140 cycles
      10000 times kmalloc(32) -> 129 cycles kfree -> 137 cycles
      10000 times kmalloc(64) -> 141 cycles kfree -> 141 cycles
      10000 times kmalloc(128) -> 152 cycles kfree -> 148 cycles
      10000 times kmalloc(256) -> 195 cycles kfree -> 167 cycles
      10000 times kmalloc(512) -> 257 cycles kfree -> 199 cycles
      10000 times kmalloc(1024) -> 393 cycles kfree -> 251 cycles
      10000 times kmalloc(2048) -> 649 cycles kfree -> 228 cycles
      10000 times kmalloc(4096) -> 806 cycles kfree -> 370 cycles
      10000 times kmalloc(8192) -> 814 cycles kfree -> 411 cycles
      10000 times kmalloc(16384) -> 892 cycles kfree -> 455 cycles
      2. Kmalloc: alloc/free test
      10000 times kmalloc(8)/kfree -> 121 cycles
      10000 times kmalloc(16)/kfree -> 121 cycles
      10000 times kmalloc(32)/kfree -> 121 cycles
      10000 times kmalloc(64)/kfree -> 121 cycles
      10000 times kmalloc(128)/kfree -> 121 cycles
      10000 times kmalloc(256)/kfree -> 119 cycles
      10000 times kmalloc(512)/kfree -> 119 cycles
      10000 times kmalloc(1024)/kfree -> 119 cycles
      10000 times kmalloc(2048)/kfree -> 119 cycles
      10000 times kmalloc(4096)/kfree -> 121 cycles
      10000 times kmalloc(8192)/kfree -> 119 cycles
      10000 times kmalloc(16384)/kfree -> 119 cycles
    
    After:
    
      Single thread testing
      =====================
      1. Kmalloc: Repeatedly allocate then free test
      10000 times kmalloc(8) -> 130 cycles kfree -> 86 cycles
      10000 times kmalloc(16) -> 118 cycles kfree -> 86 cycles
      10000 times kmalloc(32) -> 121 cycles kfree -> 85 cycles
      10000 times kmalloc(64) -> 176 cycles kfree -> 102 cycles
      10000 times kmalloc(128) -> 178 cycles kfree -> 100 cycles
      10000 times kmalloc(256) -> 205 cycles kfree -> 109 cycles
      10000 times kmalloc(512) -> 262 cycles kfree -> 136 cycles
      10000 times kmalloc(1024) -> 342 cycles kfree -> 157 cycles
      10000 times kmalloc(2048) -> 701 cycles kfree -> 238 cycles
      10000 times kmalloc(4096) -> 803 cycles kfree -> 364 cycles
      10000 times kmalloc(8192) -> 835 cycles kfree -> 404 cycles
      10000 times kmalloc(16384) -> 896 cycles kfree -> 441 cycles
      2. Kmalloc: alloc/free test
      10000 times kmalloc(8)/kfree -> 121 cycles
      10000 times kmalloc(16)/kfree -> 121 cycles
      10000 times kmalloc(32)/kfree -> 123 cycles
      10000 times kmalloc(64)/kfree -> 142 cycles
      10000 times kmalloc(128)/kfree -> 121 cycles
      10000 times kmalloc(256)/kfree -> 119 cycles
      10000 times kmalloc(512)/kfree -> 119 cycles
      10000 times kmalloc(1024)/kfree -> 119 cycles
      10000 times kmalloc(2048)/kfree -> 119 cycles
      10000 times kmalloc(4096)/kfree -> 119 cycles
      10000 times kmalloc(8192)/kfree -> 119 cycles
      10000 times kmalloc(16384)/kfree -> 119 cycles
    
    [akpm@linux-foundation.org: propagate gfp_t into cache_random_seq_create()]
    Signed-off-by: default avatarThomas Garnier <thgarnie@google.com>
    Acked-by: default avatarChristoph Lameter <cl@linux.com>
    Cc: Pekka Enberg <penberg@kernel.org>
    Cc: David Rientjes <rientjes@google.com>
    Cc: Joonsoo Kim <iamjoonsoo.kim@lge.com>
    Cc: Kees Cook <keescook@chromium.org>
    Cc: Greg Thelen <gthelen@google.com>
    Cc: Laura Abbott <labbott@fedoraproject.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    c7ce4f60