作者：evilpan
原文鏈接：https://mp.weixin.qq.com/s/giV6FcKK5wm2KnbYQxtvLA

本文主要介紹Buddy System、Slab Allocator的實現機制以及現實中的一些漏洞利用方法，從攻擊者角度加深對Linux內核內存管理機制的理解。

前言

網上已經有很多關于Linux內核內存管理的分析和介紹了，但是不影響我再寫一篇:) 一方面是作為其他文章的補充，另一方面則自己學習的記錄、總結和沉淀。所謂條條大路通羅馬，本文只作為其中一條路，強烈建議想去羅馬的朋友看完文末所列舉的參考文章。

伙伴系統

伙伴系統即Buddy System，是一種簡單高效的內存分配策略。其主要思想是將大塊內存按照一定策略去不斷拆分（在到達最小的塊之前），直至存在滿足指定請求大小的最小塊。其中塊的大小由其相對根塊的位置指定，通常稱為order(階)。一個最簡單的拆分方式就是以2為指數進行拆分，例如定義最小塊的大小為64K，order上限為4，則最大塊的大小為：

64K * 2^4 = 1024K

最大塊的order為4，最小塊的order為0。對于請求大小為k的塊，最小塊為N，則其order值為align(k)/N。為什么叫buddy system呢？假設一個大塊A所分解成的兩個小塊B和C，其中B和C就相互為彼此的天使 buddy。只有彼此的buddy才能夠進行合并。

使用Buddy算法的的應用有很多，其中Linux內核就是一個，此外jemalloc也是使用Buddy技術的一個現代內存分配器。

維基百科中有一個很直觀的例子：Buddy memory allocation。Linux內核中的伙伴系統塊大小為一頁，通常是4096字節。最大的order一般是10，即MAX_ORDER為11。

  /* Free memory management - zoned buddy allocator.  */
  #ifndef CONFIG_FORCE_MAX_ZONEORDER
  #define MAX_ORDER 11
  #else
  #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
  #endif
  #define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

在Linux內核中，分配和釋放較大內存都是直接通過伙伴系統，即：

struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);

order為0-10，指定從哪一階伙伴中分配，order為n則分配2^n頁大小的內存。操作系統中可以通過procfs查看伙伴系統的分配情況，如下：

$ cat /proc/buddyinfo
Node 0, zone      DMA      1      1      0      0      2      1      1      0      1      1      3
Node 0, zone    DMA32   3416   4852   3098   3205   3209   3029     33     22     15      7     52
Node 0, zone   Normal  29330 192053 148293  90568  33732   9018   2688    411    942    999   1852
Node 1, zone   Normal    107   1229  18644  76650  46053   8383   4398   5486   1751    497     84

此外，還有/proc/pagetypeinfo也可用于查看內存頁的信息。

Slab分配器

上面說到，由于效率原因，伙伴系統中分配內存是以頁為單位的，即使所分配的object大小為1byte，也需要分配一頁，這樣就導致了比較大的內存碎片。因此Linux引入了Slab分配器，加速對object的分配和釋放速度，同時也減少碎片空間。

最初接觸的時候心里通常有個大大的問號：Slab是什么？理解這個問題至關重要，經過翻閱多種資料和文章，可以大概這么回答：

Slab是一種緩存策略
Slab是一片緩沖區
Slab是一個或者多個連續的page

在內核代碼中，我們能看到SLAB、SLOB、SLUB，其實都是兼容SLAB接口的具體分配器。目前默認使用的是SLUB，因此經常將其混稱。按照引入Linux內核的時間劃分如下：

from：https://events.static.linuxfound.org/sites/events/files/slides/slaballocators.pdf

說句題外話，SLOB (Simple List Of Blocks) 可以看做是針對嵌入式設備優化的分配器，通常只需要幾MB的內存。其采用了非常簡單的first-fit算法來尋找合適的內存block。這種實現雖然去除了幾乎所有的額外開銷，但也因此會產生額外的內存碎片，因此一般只用于內存極度受限的場景。

數據結構

在本文中，我會盡量少粘貼大段的代碼進行分析，但Slub分配器是比較依賴于實現而不是設計的，因此數據結構的介紹是難免的。

page

描述一個頁的數據結構就是struct page。為了節約空間，page使用了大量的union結構，針對不同用處的頁使用不同的字段。

Slab是一個或者多個連續頁組成的內存空間，那么本質上指向一個Slab的數據結構不是別的，就是struct page *，對應Slab中的信息可以通過第一個page的某些字段描述。記住這點對后面的理解很重要。

kmem_cache

kmem_cache是Slab的主要管理結構，申請和釋放對象都需要經過該結構操作，部分重要字段如下：

  /*
   * Slab cache management.
   */
  struct kmem_cache {
      struct kmem_cache_cpu __percpu *cpu_slab;
      /* Used for retriving partial slabs etc */
      unsigned long flags;
      unsigned long min_partial;
      int size;       /* The size of an object including meta data */
      int object_size;    /* The size of an object without meta data */
      int offset;     /* Free pointer offset. */
  #ifdef CONFIG_SLUB_CPU_PARTIAL
      int cpu_partial;    /* Number of per cpu partial objects to keep around */
  #endif
      ...
      struct kmem_cache_node *node[MAX_NUMNODES];
}

重點關注cpu_slab和node。

cpu_slab包含當前CPU的Slab。這是個__percpu的對象，什么意思呢？我的理解是內核為了加速當前CPU的訪問，會對每個CPU保存一個變量，這樣在當前CPU訪問該變量時候就可以免去加鎖的開銷。在調試中發現該變量的值是個類似0x18940這樣比較小的數，這個地址是沒有映射的，訪問percpu變量需要通過raw_cpu_ptr宏去獲取實際的地址。

node數組中包括其他CPU的Slab。為什么叫做node？其實這是NUMA系統中的node概念。NUMA是為了多核優化而產生的架構，可以令某個CPU訪問某段內存的速度更快。node的定義是“一段內存，其中每個字節到CPU的距離相等”，更加通俗的解釋是：“在同一物理總線上的內存+CPUs+IO+……”，更多細節可以參考NUMA FAQ。

kmem_cache_cpu

cpu_slab是kmem_cache_cpu結構，如下：

  struct kmem_cache_cpu {
      void **freelist;    /* Pointer to next available object */
      unsigned long tid;  /* Globally unique transaction id */
      struct page *page;  /* The slab from which we are allocating */
  #ifdef CONFIG_SLUB_CPU_PARTIAL
      struct page *partial;   /* Partially allocated frozen slabs */
  #endif
  #ifdef CONFIG_SLUB_STATS
      unsigned stat[NR_SLUB_STAT_ITEMS];
  #endif
  };

freelist指向第一個空閑的對象(假設為x)，page指向x所在slab(的第一頁)。這里的page有以下特點： - objects = slab的對象數 - inuse = objects - frozen = 1 - freelist = NULL

partial主要包含本地部分分配的slab。partial指向的page有以下特點： - next指向下一個slab(page) - freelist指向slab中第一個空閑object - inuse = slab中已使用的object個數 - frozen = 1

其中第一個page的pbojects記錄了partial objects數。

kmem_cache_node

struct kmem_cache_node {
    spinlock_t list_lock;
    ...
#ifdef CONFIG_SLUB
    unsigned long nr_partial;
    struct list_head partial;
    ..
#endif
};

這個數據結構根據配置的SL[OAU]B分配器而異，對于SLUB而言，使用的字段就只有兩個，nr_partial和partial。其中partial是Linux內核中可插拔式通用雙鏈表結構，使用內核中雙鏈表的接口進行操作。nr_partial表示partial雙鏈表中的元素個數，即slab的個數。

partial->next指向的page結構，用于該結構的page有如下特點：

frozon = 0
freelist指向slab中第一個空閑object
inuse表示對應slab使用中的object個數
通過lru字段索引鏈表中的下一個/前一個page

前三點沒什么好說的，大家都差不多。需要關注的是第四點，這里不像cpu partial那樣通過next指針連接頁表，而是通過lru字段：

struct page {
...
      /*
       * Third double word block
       *
       * WARNING: bit 0 of the first word encode PageTail(). That means
       * the rest users of the storage space MUST NOT use the bit to
       * avoid collision and false-positive PageTail().
       */
      union {
          struct list_head lru;   /* Pageout list, eg. active_list
                       * protected by zone_lru_lock !
                       * Can be used as a generic list
                       * by the page owner.
                       */
     ...

分配和釋放

終于講到了重點。關于slub的分配和釋放有很多文章介紹過，而且風格不同，有的是對著代碼逐行分析，有的是畫圖介紹，這里我僅按照我自己的理解去說，如有謬誤歡迎指出。

對象的分配和釋放涉及到幾個指針，分別是：

p1: 對象的虛擬地址(void *)
p2: 對象地址所對應的page(struct page*)
p3: 對象所屬的slab(struct page*)
p4: 對象所屬的cache控制體(struct kmem_cache*)

一個虛地址所對應的頁首地址是是通過PAGE_MASK，因為頁是對齊的，但需要注意頁首地址并不是page指針所指向的地方。p1->p2的轉換通過virt_to_page實現。

p2->p4可以通過page->slab_cache得到，這也是p1->p4函數virt_to_cache的操作。

分配

對象的分配，不考慮特殊情況的話(比如超過N頁的對象直接通過伙伴系統分配)，一般流程如下：

kmem_cache_cpu->freelist不為空，直接出鏈返回；
kmem_cache_cpu->page->freelist不為空，則出鏈，更新cpu_slab->freelist，然后返回；
kmem_cache_cpu->partial不為空，取出第一個slab，更新cpu_slab的freelist和page，取出對象然后返回；
kmem_cache_node->partial不為空，取出第一個，類似3更新cpu_slab的freelist和page并返回；
上面都是空的，則通過伙伴系統分配新的slab，掛到kmem_cache_cpu中，然后goto 1；

釋放

對象的釋放相對復雜，和釋放之前對象所處的位置以及釋放后cache情況有關。假設待釋放的object地址為p1，p1對應的page為p2，p1對應的slab為p3，參考上面的幾個指針定義，大致有以下路徑：

p3就是當前CPU的kmem_cache_cpu->freelist所對應的slab，即p1位于當前cpu的kmem_cache_cpu->freelist所在的page中(p2 == cpu_slab->page)，此時可以直接釋放到freelist上并返回；
p3位于當前CPU的kmem_cache_cpu->partial鏈表中，或者其他CPU的kmem_cache_cpu->freelist/partial中。此slab處于凍結狀態，將p1鏈入p3->freelist中；
p3位于kmem_cache_node->partial鏈表中，此時釋放分為兩種情況： 3.1 釋放p1后，p3的狀態為半滿。此時正常將p1鏈入p3的freelist中。 3.2 釋放p1后，p3的狀態為全空。此時除了將p1鏈入p3的freelist以外，還需要判斷node中slab數是否超過規定值(node->nr_partial >= min_partial)。如果超過則需要將p3移出node->partial鏈表，并將p3釋放給伙伴系統。
p3是一個全滿的slab，不被任何kmem_cache管理。釋放后p3變成一個半滿的slab(更新freelist)，同時p3會被加入到當前CPU的kmem_cache_cpu.partial中。加入之前需要判斷cpu partial中的空閑對象是否超過了規定值(partial.pobjects > cachep.cpu_partial)，并進行相應的處理： 4.1 如果沒超過，直接鏈入cpu partial即可 4.2 如果超過，則將cpu partial中所有slab解凍，將其中所有半滿的slab交由node進行管理；將其中所有空的slab回收給伙伴系統；最后再將slab鏈入到partial中。

其中3的判斷是為了避免node partial中存放了太多空slab；4的判斷是為了避免cpu partial中存放太多空slab以及加快搜索速度。

slab分配和釋放的過程大致就是這樣，上面的圖主要來自窩窩的smcdef大神，其中還有一張大圖可以配合觀看理解：http://www.wowotech.net/content/uploadfile/201803/4a471520078976.png

調試

slab分配器是如此復雜，因此Linux內核中提供了很多調試措施，開啟特定的調試編譯選項后可以在object前后加上red zone檢測越界，也可以檢測slab的引用錯誤。

在用戶態中，我們可以通過vfs進行調試。比如可以用slabinfo或者slabtop命令查看當前的slab分配情況，這些命令實際上是讀取了/proc/slabinfo信息以及/sys/kernel/slab/*中的信息。

slabtop輸出示例：

 Active / Total Objects (% used)    : 25864761 / 26174849 (98.8%)
 Active / Total Slabs (% used)      : 661098 / 661098 (100.0%)
 Active / Total Caches (% used)     : 93 / 158 (58.9%)
 Active / Total Size (% used)       : 4921033.80K / 5046143.93K (97.5%)
 Minimum / Average / Maximum Object : 0.01K / 0.19K / 295.08K

  OBJS ACTIVE  USE OBJ SIZE  SLABS OBJ/SLAB CACHE SIZE NAME
18380583 18380583 100%    0.10K 471297       39   1885188K buffer_head
1785462 1711901   0%    0.19K  42511       42    340088K dentry
1705350 1629533   0%    1.06K  56845       30   1819040K ext4_inode_cache
589064 567016   0%    0.57K  21038       28    336608K radix_tree_node
530112 495734   0%    0.06K   8283       64     33132K kmalloc-64
475728 429025   0%    0.04K   4664      102     18656K ext4_extent_status
357632 355306   0%    0.06K   5588       64     22352K pid
258944 245861   0%    0.03K   2023      128      8092K kmalloc-32
247494 246414   0%    0.20K   6346       39     50768K vm_area_struct
231794 230768   0%    0.09K   5039       46     20156K anon_vma
174780 169836   0%    0.13K   5826       30     23304K kernfs_node_cache
164224 159505   0%    0.25K   5132       32     41056K filp
146688 143610   0%    0.02K    573      256      2292K kmalloc-16
120480 117291   0%    0.66K   2510       48     80320K proc_inode_cache
101376  97721   0%    0.01K    198      512       792K kmalloc-8
 86310  85793   0%    0.19K   2055       42     16440K cred_jar
 78122  75197   0%    0.59K   1474       53     47168K inode_cache
 48512  46984   0%    0.50K   1516       32     24256K kmalloc-512

直接從實現角度分析也許理解得不是很深刻，下面就來看幾個實際的攻擊案例，它們都巧妙地利用了上面提到的slab分配器的特性進行內存布局。

案例1：內核堆溢出漏洞利用

第一種類型是內核堆溢出漏洞。假如我們使用kmalloc分配了一個大小為30字節的對象，根據配置不同很可能會使用到名為kmalloc-32的kmem_cache去進行分配。因此，如果我們使用對象時寫入超過32字節的數據，就可能產生堆溢出。

堆溢出的直接后果就是覆蓋了slab中后面一個object塊的數據，如果后面的object對象中被覆蓋的部分包含函數指針，那么就有可能劫持內核控制流，跳轉到任意地址。如下圖所示：

這是最簡單的情況。實踐中的主要問題是，如何保證攻擊者分配的含函數指針的對象(簡稱 victim obj)就在溢出對象(簡稱 vuln object)的后面。

創建對象前slab的freelist可能是亂七八糟的，因此我們可以先申請足夠多的object，在分配流程中進入到第5步，直接從伙伴系統分配，此時slab的freelist應該也是連續的。

即便我們可以保證freelist連續，要知道內核分配對象可不是一個個分配的，可能一個函數中就有多處分配對象，也就是說分配vuln object的時候肯定有個object跟著，姑且稱之為xo。這時候如何利用呢？一個辦法就是自己構造freelist。具體來說，就是：

依次分配3個object(同樣的slab) A、B、C；此時freelist指向D的下一個object(D)；
我們希望freelist為A->C->B，因此需要依次釋放B、C、A
這樣，再次申請vuln object時其進入A，跟著的xo就進入到了C，我們的victim objcet就可以進入B，即在A的后面

這樣，只要有合適的堆占位對象(如tty_struct)，就能穩定利用這類堆溢出漏洞了。

案例2：CVE-2018-9568(WrongZone)漏洞利用

這里不涉及漏洞的詳細細節，只需要知道這個漏洞的核心是類型混淆，即Slab-A中分配的對象，錯誤地用Slab-B進行了釋放(這也是為什么這個漏洞名為WrongZone的原因)。

在WrongZone漏洞中，Slab-B比Slab-A要大(實際上Slab-A存放的是TCPv4 socket，而Slab-B存放的是TCPv6 socket，后者包含前者，并增加了一些額外字段)。而且因為RCU，Slab的free object中指向下一個free object的指針(x + offset)是包含在object末尾的。

釋放、鏈入freelist，實際上是將當前freelist的值寫入x + offset，并且將freelist重新指向剛釋放的object。由于錯誤釋放，在修改objA的offset時，超出了范圍，寫到下一個對象里面了。開啟KASAN或者SLUB_DEBUG_ON/MEMCG_KMEM可以看到出錯信息，否則很難觸發明顯的異常。

假設類型混淆對象為objA，從slabA中分配。實際的利用計劃是這樣的： 1. 令objA在釋放前所在的slabA為全滿狀態 2. 釋放objA，根據上面的分析，此時slabA會被鏈入B的cpu partial中。這意味著后續從B分配對象時候會出現從SlabA取對象的時候 3. 依次釋放slabA中的其他對象，令最后的布局如下：

follow_sk是位于objA后面的對象，我們不釋放它，防止slab變空被回收。

這樣一來，再在Slab-B中分配對象時候，就可能出現讀取fragment中的值作為下一個free對象的情況。fragment中的值可以通過堆噴方式填充，這樣就有可能令其在分配時讀取一個我們能控制的值作為slab_alloc的返回從而進行進一步提權，或者出現顯式的kernel panic。

這個利用的關鍵點就是對于全滿slab中對象釋放的處理，將slab鏈入cpu partial的時候并不會考慮slab是否正確，因為slab本身也只是一段連續的空間而已。當然該漏洞還有其他利用方法，比如將其轉化為UAF，這里就不再贅述了。

總結

在我們平時學習相對復雜的系統時，僅僅了解實現文檔只能算是走出第一步；閱讀代碼并且上機調試可以將理解加深一個層次，知道“what's inside“；不過，如果能從攻擊者的角度去分析和利用(濫用)，那理解又會加深一個層次，真正做到”inside out“。魔鬼隱藏在細節之中，把一個知識點融會貫通，也是挺有趣的事情。

參考文章

Buddy memory allocation
圖解SLUB/lukuen
圖解SLUB/smcdef
WrongZone從利用到修復——百度安全實驗室

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1153/

Paper - 安全技術精粹

Linux 內核內存管理與漏洞利用

目錄

前言