1. 前言
KASAN是一個動態檢測內存錯誤的工具。KASAN可以檢測全局變量、棧、堆分配的內存發生越界訪問等問題。功能比SLUB DEBUG齊全并且支持實時檢測。越界訪問的嚴重性和危害性通過我之前的文章(SLUB DEBUG技術)應該有所了解。正是由于SLUB DEBUG缺陷,因此我們需要一種更加強大的檢測工具。難道你不想嗎?KASAN就是其中一種。KASAN的使用真的很簡單。但是我是一個追求刨根問底的人。僅僅止步于使用的層面,我是不愿意的,只有更清楚的了解實現原理才能更加熟練的使用工具。不止是KASAN,其他方面我也是這么認為。但是,說實話,寫這篇文章是有點底氣不足的。因為從我查閱的資料來說,國內沒有一篇文章說KASAN的工作原理,國外也是沒有什么文章關注KASAN的原理。大家好像都在說How to use。由于本人水平有限,就根據現有的資料以及自己閱讀代碼揣摩其中的意思。本文章作為拋準引玉,如果有不合理的地方還請指正。
注:文章代碼分析基于linux-4.15.0-rc3。
2. 簡介
KernelAddressSANitizer(KASAN)是一個動態檢測內存錯誤的工具。它為找到use-after-free和out-of-bounds問題提供了一個快速和全面的解決方案。KASAN使用編譯時檢測每個內存訪問,因此您需要GCC 4.9.2或更高版本。檢測堆棧或全局變量的越界訪問需要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即可,編譯之后你會發現boot.img(Android環境)大小大了一倍左右。所以說,影響效率不是沒有道理的。不過我們可以作為產品發布前的最后檢查,也可以排查越界訪問等問題。我們可以查看內核日志內容是否包含KASAN檢查出的bugs信息。
4. KASAN是如何實現檢測的?
KASAN的原理是利用額外的內存標記可用內存的狀態。這部分額外的內存被稱作shadow memory(影子區)。KASAN將1/8的內存用作shadow memory。使用特殊的magic num填充shadow memory,在每一次load/store(load/store檢查指令由編譯器插入)內存的時候檢測對應的shadow memory確定操作是否valid。連續8 bytes內存(8 bytes align)使用1 byte shadow memory標記。如果8 bytes內存都可以訪問,則shadow memory的值為0;如果連續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是訪問內存字節的數量)。這也是要求更新版本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的狀態值來判斷訪問是否合法呢?首先看一種最簡單的情況。訪問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;
紅色區域類似是編譯器插入的指令。既然是訪問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字節對齊地址的偏移。還是使用下圖來說明關系吧。假設內存是從地址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區域,這里怎么變成了VMALLOC區域?這里是Ard Biesheuvel提交的修改。主要是為了迎接ARM64世界的KASLR(which allows the kernel image to be located anywhere in the vmalloc area)的到來。
4.3. 如何建立shadow memory的映射關系?
當打開KASAN的時候,KASAN區域位于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區域放大,如下圖所示。
KASAN區域僅僅是分配的虛擬地址,在訪問的時候必須建立和物理地址的映射才可以訪問。上圖就是KASAN建立的映射布局。左邊是系統啟動初期建立的映射。在kasan_early_init()函數中,將所有的KASAN區域映射到kasan_zero_page物理頁面。因此系統啟動初期,KASAN并不能工作。右側是在kasan_init()函數中建立的映射關系,kasan_init()函數執行結束就預示著KASAN的正常工作。我們將不需要address sanitizer功能的區域同樣還是映射到kasan_zero_page物理頁面,并且是readonly。我們主要是檢測kernel和物理內存是否存在UAF或者OOB問題。所以建立KERNEL和linear mapping(僅僅是所有的物理地址建立的映射區域)區域對應的shadow memory建立真實的映射關系。MOUDLE區域對應的shadow memory的映射關系也是需要創建的,但是映射關系建立是動態的,他在module加載的時候才會去創建映射關系。
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,明白了吧。不過最新的代碼已經不需要依賴了,可以看下提交。
當我們第一次創建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為不可訪問狀態。根據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個連續的字節可以訪問。04代表前4個字節可以訪問。作為越界訪問的檢測的方法。總共加在一起是正好是20 bytes可訪問。0xFC是Redzone標記。如果訪問了Redzone區域KASAN就會檢測out-of-bounds的發生。
當申請使用之后,現在調用kfree()釋放之后的shadow memory情況是怎樣的呢?看下圖。
根據object首地址找到對應的shadow memory,32 bytes object對應4 bytes的shadow memory,現在填充0xFB標記內存是釋放的狀態。此時如果繼續訪問object,那么根據shadow memory的狀態值既可以確定是use-after-free問題。
4.6. 全局變量的shadow memory值如何填充?
前面的分析都是基于內存分配器的,Redzone都會隨著內存分配器一起分配。那么global variables如何檢測呢?global variable的Redzone在哪里呢?這就需要編譯器下手了。編譯器會幫我們填充Redzone區域。例如我們定義一個全局變量a,編譯器會幫我們填充成下面的樣子。
char a[4];
轉換
struct {
char original[4];
char redzone[60];
} a; //32 bytes aligned
如果這里你問我為什么填充60 bytes。其實我也不知道。這個轉換例子也是從KASAN作者的PPT中拿過來的。估計要涉及編譯器相關的知識,我無能為力了,但是下面做實驗來猜吧。當然了,PPT的內容也需要驗證才具有說服力。盡信書則不如無書。我特地寫三個全局變量來驗證。發現System.map分配地址之間的差值正好是0x40。因此這里的確是填充60 bytes。 另外從我的測試發現,如果上述的數組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)。因此總結的規律是:redzone = 63 – (S - 1) % 32
全局變量redzone區域對應的shadow memory是在什么填充的呢?又是如何調用的呢?這部分是由編譯器幫我們完成的。編譯器會為每一個全局變量創建一個函數,函數名稱是:_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) = .; 上面說了這么多,不知道你是否產生了疑心?怎么都是猜啊!猜的能準確嗎?是的,我也這么覺得。是騾子是馬,拉出來溜溜唄!現在用事實說話。首先我創建一個c文件drivers/input/smc.c。在smc.c文件中創建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的構造函數。你是不是很奇怪,不是每一個全局變量都會創建一個類似的構造函數嗎?馬上為你揭曉。我們先執行aarch64-linux-gnu-objdump –s –x –d vmlinux > vmlinux.txt命令得到反編譯文件。現在好多重要的信息在vmlinux.txt。現在主要就是查看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個全局變量全部搞定。這里再說一點猜測吧!我猜測是以文件為單位編譯器創建一個構造函數即可,將本文件全局變量一次性全部打包初始化。第一個參數globals是0xffff200009682c50,繼續從vmlinux.txt中查看該地址處的數據。struct kasan_global是編譯器幫我們自動創建的結構體,每一個全局變量對應一個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。看下ffff2000092bd6d0存儲的是什么。
所以name就是全局變量的名稱轉換成字符串。同樣的方式得到module_name的地址是ffff2000092bd6b8。繼續看看這段地址存儲的數據。
一目了然,module_name是文件的路徑。has_dynamic_init的值就是0,這是C++需要的。我用的GCC版本是5.0左右,所以這里的KASAN_ABI_VERSION=4。這里location成員的地址是ffff200009682c20,繼續追蹤該地址的數據。 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之間。現在也證明一下觀點。先從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作為越界檢測。因為這里是全局變量,因此分配的內存區域位于kernel區域。
4.7. 棧分配變量的readzone是如何分配的?
從棧中分配的變量同樣和全局變量一樣需要填充一些內存作為redzone區域。下面繼續舉個例子說明編譯器怎么填充。首先來一段正常的代碼,沒有編譯器的插手。
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,可以根據上一節全局變量的公式套用計算得到。但是這里在變量前面竟然還有32 bytes的rz1。這個是和全局變量的不同,我猜測這里是為了檢測棧變量左邊界越界問題。藍色部分代碼也是編譯器填充,初始化shadow memory。棧的填充就沒有探究那么深入了,有興趣的讀者可以自己探究。
5. Error log信息包含哪些信息?
從kernel的Documentation文檔找份典型的KASAN bug輸出的log信息如下。
輸出的信息很豐富,包含了bug發生的類型、SLUB輸出的object內存信息、Call Trace以及shadow memory的狀態值。其中紅色信息都是比較重要的信息。我沒有寫demo歷程,而是找了一份log信息,不是我想偷懶,而是鍛煉自己。怎么鍛煉呢?我想問的是,從這份log中你可以推測代碼應該是怎么樣的?我可以得到一下信息: 1)?程序是通過kmalloc接口申請內存的; 2)?申請的內存大小是123 bytes,即p = kamlloc(123); 3)?代碼中類似往p[123]中寫1 bytes導致越界訪問的bug; 4)?在3)步驟發生前沒有任何的對該內存的寫操作; 如果你也能得到以上4點猜測,我覺的我寫的這幾篇文章你是真的看明白了。首先輸出信息是有SLUB的信息,所以應該是通過kmalloc()接口;在打印的shadow memory的值中,我們看到連續的15個0和一個3,所以申請的內存size就是15x8+3=123;由于是往ffff8800693bc5d3地址寫1個字節,并且object首地址是ffff8800693bc558,所以推測是往p[123]寫1 byte出問題;由于log中將object中所有的128 bytes數據全部打印出來,一共是127個0x6b和一個0xa5(SLUB DEBUG文章介紹的內容)。所以我推測在3)步驟發生前沒有任何的對該內存的寫操作。
編輯:黃飛
?
評論
查看更多