• Thomas Garnier's avatar
    mm: SLUB freelist randomization · 210e7a43
    Thomas Garnier authored
    Implements freelist randomization for the SLUB allocator.  It was
    previous implemented for the SLAB allocator.  Both use the same
    configuration option (CONFIG_SLAB_FREELIST_RANDOM).
    
    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.
    
    This security feature reduces the predictability of the kernel SLUB
    allocator against heap overflows rendering attacks much less stable.
    
    For example these attacks exploit the predictability of the heap:
     - Linux Kernel CAN SLUB overflow (https://goo.gl/oMNWkU)
     - Exploiting Linux Kernel Heap corruptions (http://goo.gl/EXLn95)
    
    Performance results:
    
    slab_test impact is between 3% to 4% on average for 100000 attempts
    without smp.  It is a very focused testing, kernbench show the overall
    impact on the system is way lower.
    
    Before:
    
      Single thread testing
      =====================
      1. Kmalloc: Repeatedly allocate then free test
      100000 times kmalloc(8) -> 49 cycles kfree -> 77 cycles
      100000 times kmalloc(16) -> 51 cycles kfree -> 79 cycles
      100000 times kmalloc(32) -> 53 cycles kfree -> 83 cycles
      100000 times kmalloc(64) -> 62 cycles kfree -> 90 cycles
      100000 times kmalloc(128) -> 81 cycles kfree -> 97 cycles
      100000 times kmalloc(256) -> 98 cycles kfree -> 121 cycles
      100000 times kmalloc(512) -> 95 cycles kfree -> 122 cycles
      100000 times kmalloc(1024) -> 96 cycles kfree -> 126 cycles
      100000 times kmalloc(2048) -> 115 cycles kfree -> 140 cycles
      100000 times kmalloc(4096) -> 149 cycles kfree -> 171 cycles
      2. Kmalloc: alloc/free test
      100000 times kmalloc(8)/kfree -> 70 cycles
      100000 times kmalloc(16)/kfree -> 70 cycles
      100000 times kmalloc(32)/kfree -> 70 cycles
      100000 times kmalloc(64)/kfree -> 70 cycles
      100000 times kmalloc(128)/kfree -> 70 cycles
      100000 times kmalloc(256)/kfree -> 69 cycles
      100000 times kmalloc(512)/kfree -> 70 cycles
      100000 times kmalloc(1024)/kfree -> 73 cycles
      100000 times kmalloc(2048)/kfree -> 72 cycles
      100000 times kmalloc(4096)/kfree -> 71 cycles
    
    After:
    
      Single thread testing
      =====================
      1. Kmalloc: Repeatedly allocate then free test
      100000 times kmalloc(8) -> 57 cycles kfree -> 78 cycles
      100000 times kmalloc(16) -> 61 cycles kfree -> 81 cycles
      100000 times kmalloc(32) -> 76 cycles kfree -> 93 cycles
      100000 times kmalloc(64) -> 83 cycles kfree -> 94 cycles
      100000 times kmalloc(128) -> 106 cycles kfree -> 107 cycles
      100000 times kmalloc(256) -> 118 cycles kfree -> 117 cycles
      100000 times kmalloc(512) -> 114 cycles kfree -> 116 cycles
      100000 times kmalloc(1024) -> 115 cycles kfree -> 118 cycles
      100000 times kmalloc(2048) -> 147 cycles kfree -> 131 cycles
      100000 times kmalloc(4096) -> 214 cycles kfree -> 161 cycles
      2. Kmalloc: alloc/free test
      100000 times kmalloc(8)/kfree -> 66 cycles
      100000 times kmalloc(16)/kfree -> 66 cycles
      100000 times kmalloc(32)/kfree -> 66 cycles
      100000 times kmalloc(64)/kfree -> 66 cycles
      100000 times kmalloc(128)/kfree -> 65 cycles
      100000 times kmalloc(256)/kfree -> 67 cycles
      100000 times kmalloc(512)/kfree -> 67 cycles
      100000 times kmalloc(1024)/kfree -> 64 cycles
      100000 times kmalloc(2048)/kfree -> 67 cycles
      100000 times kmalloc(4096)/kfree -> 67 cycles
    
    Kernbench, before:
    
      Average Optimal load -j 12 Run (std deviation):
      Elapsed Time 101.873 (1.16069)
      User Time 1045.22 (1.60447)
      System Time 88.969 (0.559195)
      Percent CPU 1112.9 (13.8279)
      Context Switches 189140 (2282.15)
      Sleeps 99008.6 (768.091)
    
    After:
    
      Average Optimal load -j 12 Run (std deviation):
      Elapsed Time 102.47 (0.562732)
      User Time 1045.3 (1.34263)
      System Time 88.311 (0.342554)
      Percent CPU 1105.8 (6.49444)
      Context Switches 189081 (2355.78)
      Sleeps 99231.5 (800.358)
    
    Link: http://lkml.kernel.org/r/1464295031-26375-3-git-send-email-thgarnie@google.comSigned-off-by: default avatarThomas Garnier <thgarnie@google.com>
    Reviewed-by: default avatarKees Cook <keescook@chromium.org>
    Cc: Christoph Lameter <cl@linux.com>
    Cc: Pekka Enberg <penberg@kernel.org>
    Cc: David Rientjes <rientjes@google.com>
    Cc: Joonsoo Kim <iamjoonsoo.kim@lge.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    210e7a43
Kconfig 66.7 KB