1. 前言

KASAN是一個動態(tài)檢測內存錯誤的工具。KASAN可以檢測全局變量、棧、堆分配的內存發(fā)生越界訪問等問題。功能比SLUB DEBUG齊全并且支持實時檢測。越界訪問的嚴重性和危害性通過我之前的文章（SLUB DEBUG技術）應該有所了解。正是由于SLUB DEBUG缺陷，因此我們需要一種更加強大的檢測工具。難道你不想嗎？KASAN就是其中一種。KASAN的使用真的很簡單。但是我是一個追求刨根問底的人。僅僅止步于使用的層面，我是不愿意的，只有更清楚的了解實現原理才能更加熟練的使用工具。不止是KASAN，其他方面我也是這么認為。但是，說實話，寫這篇文章是有點底氣不足的。因為從我查閱的資料來說，國內沒有一篇文章說KASAN的工作原理，國外也是沒有什么文章關注KASAN的原理。大家好像都在說How to use。由于本人水平有限，就根據現有的資料以及自己閱讀代碼揣摩其中的意思。本文章作為拋準引玉，如果有不合理的地方還請指正。
注：文章代碼分析基于linux-4.15.0-rc3。

2. 簡介

KernelAddressSANitizer（KASAN）是一個動態(tài)檢測內存錯誤的工具。它為找到use-after-free和out-of-bounds問題提供了一個快速和全面的解決方案。KASAN使用編譯時檢測每個內存訪問，因此您需要GCC 4.9.2或更高版本。檢測堆?；蛉肿兞康脑浇缭L問需要GCC 5.0或更高版本。目前KASAN僅支持x86_64和arm64架構（linux 4.4版本合入）。你使用ARM64架構，那么就需要保證linux版本在4.4以上。當然了，如果你使用的linux也有可能打過KASAN的補丁。例如，使用高通平臺做手機的廠商使用linux 3.18同樣支持KASAN。

3. 如何使用

使用KASAN工具是比較簡單的，只需要添加kernel以下配置項。

CONFIG_SLUB_DEBUG=y

CONFIG_KASAN=y

為什么這里必須打開SLUB_DEBUG呢？是因為有段時間KASAN是依賴SLUBU_DEBUG的，什么意思呢？就是在Kconfig中使用了depends on，明白了吧。不過最新的代碼已經不需要依賴了，可以看下提交。但是我建議你打開該選項，因為log可以輸出更多有用的信息。重新編譯kernel即可，編譯之后你會發(fā)現boot.img（Android環(huán)境）大小大了一倍左右。所以說，影響效率不是沒有道理的。不過我們可以作為產品發(fā)布前的最后檢查，也可以排查越界訪問等問題。我們可以查看內核日志內容是否包含KASAN檢查出的bugs信息。

4. KASAN是如何實現檢測的？

KASAN的原理是利用額外的內存標記可用內存的狀態(tài)。這部分額外的內存被稱作shadow memory（影子區(qū)）。KASAN將1/8的內存用作shadow memory。使用特殊的magic num填充shadow memory，在每一次load/store（load/store檢查指令由編譯器插入）內存的時候檢測對應的shadow memory確定操作是否valid。連續(xù)8 bytes內存（8 bytes align）使用1 byte shadow memory標記。如果8 bytes內存都可以訪問，則shadow memory的值為0；如果連續(xù)N(1 =< N <= 7) bytes可以訪問，則shadow memory的值為N；如果8 bytes內存訪問都是invalid，則shadow memory的值為負數。

在代碼運行時，每一次memory access都會檢測對應的shawdow memory的值是否valid。這就需要編譯器為我們做些工作。編譯的時候，在每一次memory access前編譯器會幫我們插入__asan_load##size()或者__asan_store##size()函數調用（size是訪問內存字節(jié)的數量）。這也是要求更新版本gcc的原因，只有更新的版本才支持自動插入。
mov x0, #0x5678
movk x0, #0x1234, lsl #16
movk x0, #0x8000, lsl #32
movk x0, #0xffff, lsl #48
mov w1, #0x5
bl __asan_store1
strb w1, [x0]
上面一段匯編指令是往0xffff800012345678地址寫5。在KASAN打開的情況下，編譯器會幫我們自動插入bl __asan_store1指令，__asan_store1函數就是檢測一個地址對應的shadow memory的值是否允許寫1 byte。藍色匯編指令就是真正的內存訪問。因此KASAN可以在out-of-bounds的時候及時檢測。__asan_load##size()和__asan_store##size()的代碼在mm/kasan/kasan.c文件實現。

4.1. 如何根據shadow memory的值判斷內存訪問操作是否valid？

shadow memory檢測原理的實現主要就是__asan_load##size()和__asan_store##size()函數的實現。那么KASAN是如何根據訪問的address以及對應的shadow memory的狀態(tài)值來判斷訪問是否合法呢？首先看一種最簡單的情況。訪問8 bytes內存。

long *addr = (long *)0xffff800012345678;
*addr = 0;

以上代碼是訪問8 bytes情況，檢測原理如下：

long *addr = (long *)0xffff800012345678;
char *shadow = (char *)(((unsigned long)addr >> 3) + KASAN_SHADOW_OFFSE);
if (*shadow)
??? report_bug();
*addr = 0;

紅色區(qū)域類似是編譯器插入的指令。既然是訪問8 bytes，必須要保證對應的shadow mempry的值必須是0，否則肯定是有問題。那么如果訪問的是1,2 or 4 bytes該如何檢查呢？也很簡單，我們只需要修改一下if判斷條件即可。修改如下：
if (*shadow && *shadow < ((unsigned long)addr & 7) + N); //N = 1,2,4
如果*shadow的值為0代表8 bytes均可以訪問，自然就不需要report bug。addr & 7是計算訪問地址相對于8字節(jié)對齊地址的偏移。還是使用下圖來說明關系吧。假設內存是從地址8~15一共8 bytes。對應的shadow memory值為5，現在訪問11地址。那么這里的N只要大于2就是invalid。

4.2. shadow memory內存如何分配？

在ARM64中，假設VA_BITS配置成48。那么kernel space空間大小是256TB，因此shadow memory的內存需要32TB。我們需要在虛擬地址空間為KASAN shadow memory分配地址空間。所以我們有必要了解一下ARM64 memory layout。
基于linux-4.15.0-rc3的代碼分析，我繪制了如下memory layout（VA_BITS = 48）。kernel space起始虛擬地址是0xffff_0000_0000_0000，kernel space被分成幾個部分分別是KASAN、MODULE、VMALLOC、FIXMAP、PCI_IO、VMEMMAP以及linear mapping。其中KASAN的大小是32TB，正好是kernel space大小的1/8。不知道你注意到沒有，KERNEL的位置相對以前是不是有所不一樣。你的印象中，KERNEL是不是位于linear mapping區(qū)域，這里怎么變成了VMALLOC區(qū)域？這里是Ard Biesheuvel提交的修改。主要是為了迎接ARM64世界的KASLR（which allows the kernel image to be located anywhere in the vmalloc area）的到來。

4.3. 如何建立shadow memory的映射關系？

當打開KASAN的時候，KASAN區(qū)域位于kernel space首地址處，從0xffff_0000_0000_0000地址開始，大小是32TB。shadow memory和kernel address轉換關系是：shadow_addr = (kaddr >> 3)? + KASAN_SHADOW_OFFSE。為了將[0xffff_0000_0000_0000, 0xffff_ffff_ffff_ffff]和[0xffff_0000_0000_0000, 0xffff_1fff_ffff_ffff]對應起來，因此計算KASAN_SHADOW_OFFSE的值為0xdfff_2000_0000_0000。我們將KASAN區(qū)域放大，如下圖所示。

KASAN區(qū)域僅僅是分配的虛擬地址，在訪問的時候必須建立和物理地址的映射才可以訪問。上圖就是KASAN建立的映射布局。左邊是系統啟動初期建立的映射。在kasan_early_init()函數中，將所有的KASAN區(qū)域映射到kasan_zero_page物理頁面。因此系統啟動初期，KASAN并不能工作。右側是在kasan_init()函數中建立的映射關系，kasan_init()函數執(zhí)行結束就預示著KASAN的正常工作。我們將不需要address sanitizer功能的區(qū)域同樣還是映射到kasan_zero_page物理頁面，并且是readonly。我們主要是檢測kernel和物理內存是否存在UAF或者OOB問題。所以建立KERNEL和linear mapping（僅僅是所有的物理地址建立的映射區(qū)域）區(qū)域對應的shadow memory建立真實的映射關系。MOUDLE區(qū)域對應的shadow memory的映射關系也是需要創(chuàng)建的，但是映射關系建立是動態(tài)的，他在module加載的時候才會去創(chuàng)建映射關系。

4.4. 伙伴系統分配的內存的shadow memory值如何填充？

既然shadow memory已經建立映射，接下來的事情就是探究各種內存分配器向shadow memory填充什么數據了。首先看一下伙伴系統allocate page(s)函數填充shadow memory情況。

假設我們從buddy system分配4 pages。系統首先從order=2的鏈表中摘下一塊內存，然后根據shadow memory address和memory address之間的對應的關系找對應的shadow memory。這里shadow memory的大小將會是2KB，系統會全部填充0代表內存可以訪問。我們對分配的內存的任意地址內存進行訪問的時候，首先都會找到對應的shadow memory，然后根據shadow memory value判斷訪問內存操作是否valid。
如果釋放pages，情況又是如何呢？

同樣的，當釋放pages的時候，會填充shadow memory的值為0xFF。如果釋放之后，依然訪問內存的話，此時KASAN根據shadow memory的值是0xFF就可以斷，這是一個use-after-free問題。

4.5. SLUB分配對象的內存的shadow memory值如何填充？

當我們打開KASAN的時候，SLUB Allocator管理的object layout將會放生一定的變化。如下圖所示。

在打開SLUB_DEBUG的時候，object就增加很多內存，KASAN打開之后，在此基礎上又加了一截。為什么這里必須打開SLUB_DEBUG呢？是因為有段時間KASAN是依賴SLUBU_DEBUG的，什么意思呢？就是在Kconfig中使用了depends on，明白了吧。不過最新的代碼已經不需要依賴了，可以看下提交。
當我們第一次創(chuàng)建slab緩存池的時候，系統會調用kasan_poison_slab()函數初始化shadow memory為下圖的模樣。整個slab對應的shadow memory都填充0xFC。

上述步驟雖然填充了0xFC，但是接下來初始化object的時候，會改變一些shadow memory的值。我們先看一下kmalloc(20)的情況。我們知道kmalloc()就是基于SLUB Allocator實現的，所以會從kmalloc-32的kmem_cache中分配一個32 bytes object。

首先調用kmalloc(20)函數會匹配到kmalloc-32的kmem_cache，因此實際分配的object大小是32 bytes。KASAN同樣會標記剩下的12 bytes的shadow memory為不可訪問狀態(tài)。根據object的地址，計算shadow memory的地址，并開始填充數值。由于kmalloc()返回的object的size是32 bytes，由于kmalloc(20)只申請了20 bytes，剩下的12 bytes不能使用。KASAN必須標記shadow memory這種情況。object對應的4 bytes shadow memory分別填充00 00 04 FC。00代表8個連續(xù)的字節(jié)可以訪問。04代表前4個字節(jié)可以訪問。作為越界訪問的檢測的方法?？偣布釉谝黄鹗钦檬?0 bytes可訪問。0xFC是Redzone標記。如果訪問了Redzone區(qū)域KASAN就會檢測out-of-bounds的發(fā)生。
當申請使用之后，現在調用kfree()釋放之后的shadow memory情況是怎樣的呢？看下圖。

根據object首地址找到對應的shadow memory，32 bytes object對應4 bytes的shadow memory，現在填充0xFB標記內存是釋放的狀態(tài)。此時如果繼續(xù)訪問object，那么根據shadow memory的狀態(tài)值既可以確定是use-after-free問題。

4.6. 全局變量的shadow memory值如何填充？

前面的分析都是基于內存分配器的，Redzone都會隨著內存分配器一起分配。那么global variables如何檢測呢？global variable的Redzone在哪里呢？這就需要編譯器下手了。編譯器會幫我們填充Redzone區(qū)域。例如我們定義一個全局變量a，編譯器會幫我們填充成下面的樣子。
char a[4];
轉換

struct {

char original[4];

char redzone[60];

} a; //32 bytes aligned

如果這里你問我為什么填充60 bytes。其實我也不知道。這個轉換例子也是從KASAN作者的PPT中拿過來的。估計要涉及編譯器相關的知識，我無能為力了，但是下面做實驗來猜吧。當然了，PPT的內容也需要驗證才具有說服力。盡信書則不如無書。我特地寫三個全局變量來驗證。發(fā)現System.map分配地址之間的差值正好是0x40。因此這里的確是填充60 bytes。 另外從我的測試發(fā)現，如果上述的數組a的大小是33的時候，填充的redzone就是63 bytes。所以我推測，填充的原理是這樣的。全局變量實際占用內存總數S（以byte為單位）按照每塊32 bytes平均分成N塊。假設最后一塊內存距離目標32 bytes還差y bytes（if S%32 == 0，y = 0），那么redzone填充的大小就是(y + 32) bytes。畫圖示意如下（S%32 != 0）。因此總結的規(guī)律是：redzone = 63 – (S - 1) % 32

全局變量redzone區(qū)域對應的shadow memory是在什么填充的呢？又是如何調用的呢？這部分是由編譯器幫我們完成的。編譯器會為每一個全局變量創(chuàng)建一個函數，函數名稱是：_GLOBAL__sub_I_65535_1_##global_variable_name。這個函數中通過調用__asan_register_globals()函數完成shadow memory標記。并且將自動生成的這個函數的首地址放在.init_array段。在kernel啟動階段，通過以下代調用關系最終調用所有全局變量的構造函數。kernel_init_freeable()->do_basic_setup() ->do_ctors()。do_ctors()代碼實現如下：

static void __init do_ctors(void)

{

ctor_fn_t *fn = (ctor_fn_t *) __ctors_start;

for (; fn < (ctor_fn_t *) __ctors_end; fn++)

(*fn)();

}

這里的代碼意思對于輕車熟路的你再熟悉不過了吧。因為內核中這么搞的太多了。便利__ctors_start和__ctors_end之間的所有數據，作為函數地址進行調用，即完成了所有的global variables的shadow memory初始化。我們可以從鏈接腳本中知道__ctors_start和__ctors_end的意思。 #define KERNEL_CTORS()? . = ALIGN(8);????????????? ??????????? VMLINUX_SYMBOL(__ctors_start) = .; ??????????? KEEP(*(.ctors))??????????? ??????????? KEEP(*(SORT(.init_array.*)))?????? ??????????? KEEP(*(.init_array))?????????? ??????????? VMLINUX_SYMBOL(__ctors_end) = .; 上面說了這么多，不知道你是否產生了疑心？怎么都是猜?。〔碌哪軠蚀_嗎？是的，我也這么覺得。是騾子是馬，拉出來溜溜唄！現在用事實說話。首先我創(chuàng)建一個c文件drivers/input/smc.c。在smc.c文件中創(chuàng)建3個全局變量如下：

然后就隨便使用吧！編譯kernel，我們先看看System.map文件中，3個全局變量分配的地址。 ffff200009f540e0 B smc_num1 ffff200009f54120 B smc_num2 ffff200009f54160 B smc_num3 還記得上面說會有一個形如_GLOBAL__sub_I_65535_1_##global_variable_name的函數嗎？在System.map文件文件中，我看到了_GLOBAL__sub_I_65535_1_smc_num1符號。但是沒有smc_num2和smc_num3的構造函數。你是不是很奇怪，不是每一個全局變量都會創(chuàng)建一個類似的構造函數嗎？馬上為你揭曉。我們先執(zhí)行aarch64-linux-gnu-objdump –s –x –d vmlinux > vmlinux.txt命令得到反編譯文件。現在好多重要的信息在vmlinux.txt?，F在主要就是查看vmlinux.txt文件。先看一下_GLOBAL__sub_I_65535_1_smc_num1函數的實現。

匯編和C語言傳遞參數在ARM64平臺使用的是x0~x7。通過上面的匯編計算一下，x0=0xffff200009682c50，x1=3。然后調用__asan_register_globals()函數，x0和x1就是傳遞的參數。我們看一下__asan_register_globals()函數實現。

void __asan_register_globals(struct kasan_global *globals, size_t size)

{

int i;

for (i = 0; i < size; i++)

register_global(&globals[i]);

}

size是3就是要初始化全局變量的個數，所以這里只需要一個構造函數即可。一次性將3個全局變量全部搞定。這里再說一點猜測吧！我猜測是以文件為單位編譯器創(chuàng)建一個構造函數即可，將本文件全局變量一次性全部打包初始化。第一個參數globals是0xffff200009682c50，繼續(xù)從vmlinux.txt中查看該地址處的數據。struct kasan_global是編譯器幫我們自動創(chuàng)建的結構體，每一個全局變量對應一個struct kasan_global結構體。struct kasan_global結構體存放的位置是.data段，因此我們可以從.data段查找當前地址對應的數據。數據如下：

首先ffff200009682c50對應的第一個數據6041f509 0020ffff，這是個啥？其實是一個地址數據，你是不是又疑問了，ARM64的kernel space地址不是ffff開頭嗎？這個怎么60開頭？其實這個地址數據是反過來的，你應該從右向左看。這個地址其實是ffff200009f54160。這不正是smc_num3的地址嘛！解析這段數據之前需要了解一下struct kasan_global結構體。

/* The layout of struct dictated by compiler */

struct kasan_global {

const void *beg; ? ? ? ?/* Address of the beginning of the global variable. */

size_t size; ? ? ? ? ? ?/* Size of the global variable. */

size_t size_with_redzone; ? /* Size of the variable + size of the red zone. 32 bytes aligned */

const void *name;

const void *module_name; ? ?/* Name of the module where the global variable is declared. */

unsigned long has_dynamic_init; /* This needed for C++ */

#if KASAN_ABI_VERSION >= 4

struct kasan_source_location *location;

#endif

};

第一個成員beg就是全局變量的首地址。跟上面的分析一致。第二個成員size從上面數據看出是7，正好對應我們定義的smc_num3[7]，正好7 bytes。size_with_redzone的值是0x40，正好是64。根據上面猜測redzone=63-(7-1)%32=57。加上size正好是64，說明之前猜測的redzone計算方法沒錯。name成員對應的地址是ffff2000092bd6d0?？聪耭fff2000092bd6d0存儲的是什么。

所以name就是全局變量的名稱轉換成字符串。同樣的方式得到module_name的地址是ffff2000092bd6b8。繼續(xù)看看這段地址存儲的數據。

一目了然，module_name是文件的路徑。has_dynamic_init的值就是0，這是C++需要的。我用的GCC版本是5.0左右，所以這里的KASAN_ABI_VERSION=4。這里location成員的地址是ffff200009682c20，繼續(xù)追蹤該地址的數據。 ffff200009682c20 b8d62b09 0020ffff 0e000000 0f000000 解析這段數據之前要先了解struct kasan_source_location結構體。

/* The layout of struct dictated by compiler */

struct kasan_source_location {

const char *filename;

int line_no;

int column_no;

};

第一個成員filename地址是ffff2000092bd6b8和module_name一樣的數據。剩下兩個數據分別是14和15，分別代表全局變量定義地方的行號和列號。現在回到上面我定義變量的截圖，仔細數數列號是不是15，行號截圖中也有哦！特地截出來給你看的。剩下的struct kasan_global數據就是smc_num1和smc_num2的數據。分析就不說了。前面說_GLOBAL__sub_I_65535_1_smc_num1函數會被自動調用，該地址數據填充在__ctors_start和__ctors_end之間?，F在也證明一下觀點。先從System.map得到符號的地址數據。 ffff2000093ac5d8 T __ctors_start ffff2000093ae860 T __ctors_end 然后搜索一下_GLOBAL__sub_I_65535_1_smc_num1的地址ffff200009381df0被存儲在什么位置，記得搜索的關鍵字是f01d3809 0020ffff。 ffff2000093ae0c0 f01d3809 0020ffff 181e3809 0020ffff 可以看出ffff2000093ae0c0地址處存儲著_GLOBAL__sub_I_65535_1_smc_num1函數地址。這個地址不是正好位于__ctors_start和__ctors_end之間嘛！

現在就剩下__asan_register_globals()函數到底是是怎么初始化shadow memory的呢？以char a[4]為例，如下圖所示

a[4]只有4 bytes可以訪問，所以對應的shadow memory的第一個byte值是4，后面的redzone就填充0xFA作為越界檢測。a[4]只有4 bytes可以訪問，所以對應的shadow memory的第一個byte值是4，后面的redzone就填充0xFA作為越界檢測。因為這里是全局變量，因此分配的內存區(qū)域位于kernel區(qū)域。

4.7. 棧分配變量的readzone是如何分配的？

從棧中分配的變量同樣和全局變量一樣需要填充一些內存作為redzone區(qū)域。下面繼續(xù)舉個例子說明編譯器怎么填充。首先來一段正常的代碼，沒有編譯器的插手。

void foo()

{

char a[328];

}

再來看看編譯器插了哪些東西進去。

void foo() { ????char rz1[32]; ??? char a[328]; ??? char rz2[56]; ????int *shadow = （&rz1 >> 3）+ KASAN_SHADOW_OFFSE; ??? shadow[0] = 0xffffffff; ??? shadow[11] = 0xffffff00; ??? shadow[12] = 0xffffffff; ?------------使用完畢--------------? ??? shadow[0] = shadow[11] = shadow[12] = 0; }

紅色部分是編譯器填充內存，rz2是56，可以根據上一節(jié)全局變量的公式套用計算得到。但是這里在變量前面竟然還有32 bytes的rz1。這個是和全局變量的不同，我猜測這里是為了檢測棧變量左邊界越界問題。藍色部分代碼也是編譯器填充，初始化shadow memory。棧的填充就沒有探究那么深入了，有興趣的讀者可以自己探究。

5. Error log信息包含哪些信息？

從kernel的Documentation文檔找份典型的KASAN bug輸出的log信息如下。

輸出的信息很豐富，包含了bug發(fā)生的類型、SLUB輸出的object內存信息、Call Trace以及shadow memory的狀態(tài)值。其中紅色信息都是比較重要的信息。我沒有寫demo歷程，而是找了一份log信息，不是我想偷懶，而是鍛煉自己。怎么鍛煉呢？我想問的是，從這份log中你可以推測代碼應該是怎么樣的？我可以得到一下信息： 1)?程序是通過kmalloc接口申請內存的； 2)?申請的內存大小是123 bytes，即p = kamlloc(123); 3)?代碼中類似往p[123]中寫1 bytes導致越界訪問的bug； 4)?在3)步驟發(fā)生前沒有任何的對該內存的寫操作； 如果你也能得到以上4點猜測，我覺的我寫的這幾篇文章你是真的看明白了。首先輸出信息是有SLUB的信息，所以應該是通過kmalloc()接口；在打印的shadow memory的值中，我們看到連續(xù)的15個0和一個3，所以申請的內存size就是15x8+3=123；由于是往ffff8800693bc5d3地址寫1個字節(jié)，并且object首地址是ffff8800693bc558，所以推測是往p[123]寫1 byte出問題；由于log中將object中所有的128 bytes數據全部打印出來，一共是127個0x6b和一個0xa5（SLUB DEBUG文章介紹的內容）。所以我推測在3)步驟發(fā)生前沒有任何的對該內存的寫操作。

編輯：黃飛

?