AddressSanitizer簡介

AddressSanitizer是Google用于檢測內存各種buffer overflow(Heap buffer overflow, Stack buffer overflow, Global buffer overflow)的一個非常有用的工具。該工具是一個LLVM的Pass，現已集成至llvm中，要是用它可以通過-fsanitizer=address選項使用它。AddressSanitizer的源碼位于/lib/Transforms/Instrumentation/AddressSanitizer.cpp中，Runtime-library的源碼在llvm的另一個項目compiler-rt的/lib/asan文件夾中。

AddressSanitizer算法

具體的算法可以參考WIKI(https://github.com/google/sanitizers/wiki/AddressSanitizerAlgorithm),在此對AddressSanitizer算法做一個簡短的介紹。AddressSanitizer主要包括兩部分：插樁(Instrumentation)和動態運行庫(Run-time library)。插樁主要是針對在llvm編譯器級別對訪問內存的操作(store，load，alloca等)，將它們進行處理。動態運行庫主要提供一些運行時的復雜的功能(比如poison/unpoison shadow memory)以及將malloc,free等系統調用函數hook住。其實該算法的思路很簡單，如果想防住Buffer Overflow漏洞，只需要在每塊內存區域右端（或兩端，能防overflow和underflow）加一塊區域（RedZone），使RedZone的區域的影子內存（Shadow Memory)設置為不可寫即可。具體的示意圖如下圖所示。

內存映射

AddressSanitizer保護的主要原理是對程序中的虛擬內存提供粗粒度的影子內存(每8個字節的內存對應一個字節的影子內存)，為了減少overhead，就采用了直接內存映射策略，所采用的具體策略如下：Shadow=(Mem >> 3) + offset。每8個字節的內存對應一個字節的影子內存，影子內存中每個字節存取一個數字k,如果k=0，則表示該影子內存對應的8個字節的內存都能訪問，如果0

圖1： 虛擬地址映射圖

插樁

為了防止buffer overflow，需要將原來分配的內存兩邊分配額外的內存Redzone，并將這兩邊的內存加鎖，設為不能訪問狀態，這樣可以有效的防止buffer overflow(但不能杜絕buffer overflow)。一下是在棧中插樁的一個例子。

未插樁的代碼：

插樁后的代碼：

動態運行庫

在動態運行庫中將malloc/free函數進行了替換。在malloc函數中額外的分配了Redzone區域的內存，將與Redzone區域對應的影子內存加鎖，主要的內存區域對應的影子內存不加鎖。

free函數將所有分配的內存區域加鎖，并放到了隔離區域的隊列中(保證在一定的時間內不會再被malloc函數分配)。

AddressSanitizer源碼分析

AddressSanitizer主要有三種層面的變量：Stack Variable(局部變量)，Global Variable, Heap Variable。由于每種變量的生命周期（life time)不同，所以對不同種類的變量處理也是不同的。下面分別從Global Variable，Stack Variable，Heap Variable三個層次來分析AddressSanitizer源碼的邏輯結構。

Global Variable

Global Variable存放在程序的數據段。在該算法的實現過程中，處理GlobalVariale的是AddressSanitizerModule類，該類繼承自llvm的ModulePass，所以我們先看一下AddressSanitizerModule類的runOnModule(Module &M)方法的處理過程，該過程首先進行一些初始化，然后我們可以看到對Global的插樁方法InstrumentGlobals()方法。

圖2： RunOnModule

在InstrumentGlobals()方法中，主要是分成兩步：首先，重新聲明一個GlobalVariable，這個GlobalVariable包含以前的GlobalVariable和一個RedZone；然后，調用runtime-library將新聲明的這個GlobalVariable的RedZone區域加鎖。我們先來看第一步的具體實現，如圖3所示。

圖3： 生成包含RedZone的新的GlobalVariable

下面，我們首先看一下一個Struct結構，該結構記錄GlobalVariable存儲的首地址，數據的大小，Redzone的大小，Module的名字等信息，便于在Runtime-library中使用。該結構在AddressSanitizerModule和runtime-library中都有相應的定義：

然后我們可以看到對GlobalVariable進行插樁來實現RedZone的Poison和整個GlobalVariable的Poison操作。

具體的Poison RedZone和Poison GlobalVariable的實現在Runtime-library中：

Stack Variable

Stack Variable保存在棧區，在棧中的數據我們需要控制好變量的聲明周期(lifetime),當調用一個函數時，會開辟一個棧，棧中的數據會有相應的redzone和shadow memory，并將redzone的shadow memory Poison，當函數結束（正常返回，異常），棧被銷毀，需要將數據和redzone清空，其相應的shadow memory也要UnPoison掉。

對于Stack Variable，AddressSanitizer算法中實現了AddressSanitizer類，該類是繼承了llvm的FunctionPass，該Pass能夠處理每一個函數，在處理每個函數的時候，處理每一個load，store等能夠訪問內存的指令，在這些指令執行前進行插樁，看其訪問的內存是不是被poison。

下面我們主要看一下AddressSanitizer::runOnFunction(Module &M)函數中主要的插樁過程。

在每次訪問內存時，都會查看影子內存的值，看其是否是0，如果是0則表示都能訪問具體的插樁在instrumentMop函數中，

其中具體的處理過程在instrumentAddress函數中：

Heap Variable

Heap Variable保存在堆區，其分配的函數是malloc函數，該部分的主要代碼在runtime-library中，該庫中主要是先將malloc的庫函數hook住，然后自己定義malloc函數，定義分配策略。

具體的分配策略定義在compiler-rt/lib/asan/asan-allocator.cc文件中，感興趣可以看一下。