2.靜態(tài)分析介紹

2.1 圖介紹

Figure1-Graph.png

過(guò)程間控制流圖ICFG（Inter-procedural Control-Flow Graph）：如圖b，可用于進(jìn)行基于路徑敏感的分析（path-sensitive analysis）。

指針賦值圖PAG（Pointer Assignment Graph）：如圖c，可用于進(jìn)行空值分析。此圖可看出存在一條路徑，使得變量b被賦值為空，會(huì)產(chǎn)生一個(gè)對(duì)應(yīng)的空值報(bào)告。

數(shù)值流圖VFG（Value-Flow Graph）：如圖d，可用于進(jìn)行污點(diǎn)分析，可用來(lái)跟蹤單個(gè)的內(nèi)存對(duì)象。

2.2 圖分析精確度

Whole-Program —— Inter-procedural Analysis：考慮調(diào)用邊和返回邊 Context-Sensitive：即從哪里調(diào)用過(guò)來(lái)的 Flow-Sensitive：保存整個(gè)控制流路徑

2.3 數(shù)據(jù)流分析算法和worklist算法

以Reaching Definitions Analysis為例。

問(wèn)題定義：給變量v一個(gè)定義d（賦值），存在一條路徑使得程序點(diǎn)p能夠到達(dá)q，且在這個(gè)過(guò)程中不能改變v的賦值。

應(yīng)用舉例：檢測(cè)未定義的變量，若v可達(dá)p且v沒(méi)有被定義，則為未定義的變量。

抽象表示：設(shè)程序有n條賦值語(yǔ)句，用n位向量來(lái)表示能reach與不能reach。

2.3.1 公式分析

什么是definition？ D: v = x op y 類似于賦值。

Transfer Function：OUT[B] = gen_B U (IN[B] - kill_B) ——怎么理解，就是基于轉(zhuǎn)換規(guī)則而得到。

解釋：基本塊B的輸出 = 塊B內(nèi)的所有變量v的定義（賦值/修改）語(yǔ)句 U （塊B的輸入 - 程序中其它所有定義了變量v的語(yǔ)句）。本質(zhì)就是本塊與前驅(qū)修改變量的語(yǔ)句 作用之和（去掉前驅(qū)的重復(fù)修改語(yǔ)句）。

Control Flow：IN[B] = U_{p a_predecesso_of_B} Out[P] ——怎么理解，就是基于控制流而得到。

解釋：基本塊B的輸入 = 塊B所有前驅(qū)塊P的輸出的并集。注意，所有前驅(qū)塊意味著只要有一條路徑能夠到達(dá)塊B，就是它的前驅(qū)，包括條件跳轉(zhuǎn)與無(wú)條件跳轉(zhuǎn)。

1-Reaching_Definition.png

2.3.2 算法

目的：輸入CFG，計(jì)算好每個(gè)基本塊的kill_B（程序中其它塊中定義了變量v的語(yǔ)句）和gen_B（塊B內(nèi)的所有變量v的定義語(yǔ)句），輸出每個(gè)基本塊的IN[B]和OUT[B]。

方法：首先所有基本塊的OUT[B]初始化為空。遍歷每一個(gè)基本塊B，按以上兩個(gè)公式計(jì)算塊B的IN[B]和OUT[B]，只要這次遍歷時(shí)有某個(gè)塊的OUT[B]發(fā)生變化，則重新遍歷一次（因?yàn)槌绦蛑杏醒h(huán)存在，只要某塊的OUT[B]變了，就意味著后繼塊的IN[B]變了）。

2-可達(dá)性分析算法.png

2.3.3 實(shí)例

抽象表示：設(shè)程序有n條賦值語(yǔ)句，用n位向量來(lái)表示能reach與不能reach。

說(shuō)明：紅色-第1次遍歷；藍(lán)色-第2次遍歷；綠色-第3次遍歷。

結(jié)果：3次遍歷之后，每個(gè)基本塊的OUT[B]都不再變化。

3-遍歷實(shí)例.png

現(xiàn)在，我們可以回想一下，數(shù)據(jù)流分析的目標(biāo)是，最后得到了，每個(gè)程序點(diǎn)關(guān)聯(lián)一個(gè)數(shù)據(jù)流值（該點(diǎn)所有可能的程序狀態(tài)的一個(gè)抽象表示，也就是這個(gè)n位向量）。在這個(gè)過(guò)程中，我們對(duì)個(gè)基本塊，不斷利用基于轉(zhuǎn)換規(guī)則的語(yǔ)義（也就是transfer functions，構(gòu)成基本塊的語(yǔ)句集）-OUT[B]、控制流的約束-IN[B]，最終得到一個(gè)穩(wěn)定的安全的近似約束集。

2.3.4 worlist算法

本質(zhì)：對(duì)迭代算法進(jìn)行優(yōu)化，采用隊(duì)列來(lái)存儲(chǔ)需要處理的基本塊，減少大量的冗余的計(jì)算。

4-worklist.png

3.k-Miner 設(shè)計(jì)與實(shí)現(xiàn)

Figure2-K-Miner Overview.png

如圖是K-Miner的整體架構(gòu)圖，K-Miner是基于LLVM和SVF（過(guò)程間靜態(tài)數(shù)值流分析）的靜態(tài)分析框架，主要包含以下三個(gè)工作流程：

（1）K-Miner首先接收兩個(gè)輸入，一個(gè)是內(nèi)核代碼，另一個(gè)是內(nèi)核的配置文件，這個(gè)配置文件記錄了一些內(nèi)核特性，用來(lái)告訴前端解析器，哪些內(nèi)核模塊需要編譯，哪些模塊不需要編譯。編譯器根據(jù)這兩個(gè)輸入去構(gòu)建抽象語(yǔ)法樹(shù)（AST），并把它轉(zhuǎn)化為中間表示語(yǔ)言（IR），作為后續(xù)的輸入。

（2）把上一步得到的IR作為輸入，去遍歷所有系統(tǒng)調(diào)用，對(duì)于每一個(gè)系統(tǒng)調(diào)用，K-Miner會(huì)生成輔助后面分析的數(shù)據(jù)結(jié)構(gòu)，比如調(diào)用圖(CG)、控制流圖(CFG)、指針?lè)治鰣D（PAG）、數(shù)值流圖（VFG）等，有了這些結(jié)果，就可以對(duì)每一個(gè)系統(tǒng)調(diào)用進(jìn)行相應(yīng)的漏洞分析。

（3）對(duì)于第二步中的分析結(jié)果，如果檢測(cè)到有內(nèi)存漏洞，則在這一階段中產(chǎn)生相應(yīng)的分析報(bào)告，包含相應(yīng)的內(nèi)核版本、配置文件、系統(tǒng)調(diào)用以及程序執(zhí)行路徑等。

Figure3-K-Miner-Core Analysis.png

整個(gè)工具核心的分析流程大概分為四步：

（1）Kernel Memory Context Pre-Analysis: 首先對(duì)要分析的內(nèi)核上下文進(jìn)行一些預(yù)處理，包括初始化內(nèi)核的上下文信息、跟蹤堆分配的信息、建立系統(tǒng)調(diào)用的上下文信息。

（2）Per-Syscall Value-Flow Analysis: 然后對(duì)內(nèi)核的每個(gè)系統(tǒng)調(diào)用做獨(dú)立的分析。為了獲得更加精確的系統(tǒng)調(diào)用的上下文，作者通過(guò)分析函數(shù)調(diào)用圖確定函數(shù)指針的可達(dá)性，并結(jié)合流敏感的指針?lè)治黾夹g(shù)進(jìn)一步進(jìn)行約束，最后結(jié)合全局內(nèi)核上下文進(jìn)行分析，得到較為精簡(jiǎn)的每一個(gè)系統(tǒng)調(diào)用的可達(dá)函數(shù)的集合，從而得到一個(gè)更加完整、精確的上下文。

（3）Analysis Sanitizer: 在拿到足夠多的上下文信息后，這一步會(huì)從漏洞挖掘角度做一個(gè)精確的數(shù)據(jù)流分析，以減少工具的誤報(bào)。文章以檢測(cè)dangling pointer為例，結(jié)合VFG圖、PAG圖等信息，尋找某個(gè)局部結(jié)點(diǎn)（也就是局部變量）存在無(wú)效的引用并找到對(duì)該結(jié)點(diǎn)的引用對(duì)象，如果找到這樣的引用，就表明它是一個(gè)懸空指針漏洞。最后將該漏洞所經(jīng)過(guò)的路徑信息和相應(yīng)的結(jié)點(diǎn)等保存下來(lái)，以便后續(xù)處理。

（4）Reporting Engine: ?對(duì)上一步輸出的漏洞信息進(jìn)行簡(jiǎn)單的去重以及格式等處理，輸出最后的漏洞報(bào)告。

4.實(shí)驗(yàn)與分析

作者選擇了五個(gè)版本的Linux內(nèi)核代碼進(jìn)行測(cè)試，總共測(cè)試了300多個(gè)系統(tǒng)調(diào)用，測(cè)試的漏洞類型為DP（Dangling Pointer）、 UAF（Use After Free）和DF（Double Free）。

環(huán)境：CPU：Xeon E5-4650、8核處理器、2.4GHz的主頻。內(nèi)存32G。

（1）工具測(cè)試時(shí)間評(píng)估：結(jié)果表明，對(duì)于分析每一個(gè)系統(tǒng)調(diào)用，K-Miner平均大約需要25分鐘測(cè)試時(shí)間。

Table1-Experiment-Time.png

（2）工具內(nèi)存消耗評(píng)估：結(jié)果表明，對(duì)于分析每一個(gè)系統(tǒng)調(diào)用，K-Miner平均使用內(nèi)存在8.7G到13.2G之間，最大值達(dá)到26G。由于作者采用了對(duì)內(nèi)核進(jìn)行分割分析的思想，所以最終的內(nèi)存消耗還是在可接受的范圍的。

Table2-Experiment-Memory Used.png

（3）漏洞挖掘結(jié)果：結(jié)果表明，K-Miner總計(jì)發(fā)現(xiàn)了29個(gè)可能的漏洞，以及539個(gè)疑似的警告。根據(jù)工具的結(jié)果結(jié)合人工分析，作者發(fā)現(xiàn)了兩個(gè)真實(shí)的漏洞（CVE-2014-3153、CVE-2015-8962）。另外在人工分析中，作者發(fā)現(xiàn)大部分結(jié)果為工具誤報(bào)，特別是UAF類型的誤報(bào)偏高，作者提到有一部分原因是因?yàn)闄z查是否為NULL這種條件分支也會(huì)被識(shí)別為潛在的UAF。

5.評(píng)價(jià)

誤報(bào)較嚴(yán)重，文章中介紹的一系列優(yōu)化策略沒(méi)有在實(shí)驗(yàn)中體現(xiàn)其優(yōu)劣；K-Miner每次只分析一個(gè)syscall，沒(méi)有分析除syscall以外的代碼，如驅(qū)動(dòng)模塊，且忽視了由于多個(gè)syscall導(dǎo)致的并發(fā)漏洞。

值得學(xué)習(xí)的是K-Miner的數(shù)值流分析算法和漏洞建模策略，還有內(nèi)核劃分的思想。

二、K-Miner源碼分析

K-Miner是采用C++實(shí)現(xiàn)，看代碼的難點(diǎn)就是類太多，繼承關(guān)系復(fù)雜，容易看暈。

1.初始化

K-Miner的一大亮點(diǎn)就是初始化。K-Miner代碼的三分之一都在進(jìn)行初始化。

為什么要初始化？靜態(tài)分析是以syscall入口開(kāi)始進(jìn)行靜態(tài)分析的，直接跳過(guò)了系統(tǒng)啟動(dòng)的boot階段，所以syscall中出現(xiàn)的全局變量可能沒(méi)有經(jīng)過(guò)初始化，這樣直接進(jìn)行靜態(tài)分析會(huì)很不準(zhǔn)確。

K-Miner是怎么做的呢？我就簡(jiǎn)單總結(jié)一下，首先遍歷搜索系統(tǒng)啟動(dòng)階段中負(fù)責(zé)初始化的函數(shù)——InitCall，再找到InitCall中包含的函數(shù)和全局變量，所有InitCall都大致按照優(yōu)先級(jí)進(jìn)行排序（也即系統(tǒng)啟動(dòng)時(shí)的執(zhí)行順序）。找Initcall中函數(shù)和全局變量的過(guò)程進(jìn)行了兩次，第一次遍歷的是SVF簡(jiǎn)單構(gòu)造的調(diào)用圖，第二次是采用SVF Andersen指針?lè)治錾筛鼫?zhǔn)確的調(diào)用圖。接著找到待分析的目標(biāo)Syscall中包含的函數(shù)和全局變量（記為globalvars），找到對(duì)globalvars進(jìn)行初始化的InitCall集合（記為Initcall-S），在對(duì)應(yīng)的Syscall開(kāi)頭添加對(duì)Initcall-S的調(diào)用，這樣每次分析目標(biāo)Syscall時(shí)，都會(huì)先執(zhí)行Initcall對(duì)全局變量進(jìn)行初始化。

初始化時(shí)還做了其他工作。例如，將alloc/free/lock/unlock這四類函數(shù)全部替換為ExternalLinkage的同名同類型函數(shù)，以便于后序的數(shù)值流分析。

2.漏洞檢測(cè)

K-Miner使用5個(gè)pass來(lái)挖掘這5個(gè)漏洞。都采用了典型的worklist算法來(lái)進(jìn)行數(shù)據(jù)流分析和路徑遍歷。

Pass簡(jiǎn)介：通常，采用PassManager來(lái)管理用戶實(shí)現(xiàn)的pass，PassManager中的Run()函數(shù)會(huì)自動(dòng)按順序調(diào)用doInitialization()、doFinalization()、runOnModule()這3個(gè)函數(shù)，所以一般用戶需要自己實(shí)現(xiàn)這3個(gè)函數(shù)，doInitialization()函數(shù)在your_pass中最先執(zhí)行，一般用于初始化；runOnModule()是主要的分析部分；doFinalization()在分析完成后做收尾工作。

5-pass關(guān)系.png

總體流程：UseAfterReturn漏洞采用的是數(shù)據(jù)流分析，MemLeak、UAF、DoubleFree、DoubleLock漏洞采用的是Source-Sink分析。所以UseAfterReturnChecker Pass是單獨(dú)實(shí)現(xiàn)的，完成數(shù)值流分析和漏洞檢測(cè)的整個(gè)過(guò)程。而MemLeakChecker、UseAfterFreeChecker、DoubleFreeChecker、DoubleLockChecker Pass都是繼承了同一個(gè)類SrcSnkAnalysis，首先由SrcSnkAnalysis類進(jìn)行source-sink分析，具體過(guò)程是遍歷souce點(diǎn)，以source點(diǎn)為起點(diǎn)正向遍歷SVFG稀疏值流圖，一直走到sink點(diǎn)，將所有能夠到達(dá)的sink點(diǎn)保存起來(lái)，包括走到這個(gè)sink點(diǎn)的正向路徑。這個(gè)時(shí)候source和sink點(diǎn)并不是對(duì)應(yīng)上的，也就是說(shuō)操作的對(duì)象不一定是同一個(gè)，再遍歷該source點(diǎn)可達(dá)的sink集合，反向走，看能不能走到source點(diǎn)，能走到則將路徑信息保存到sinkPaths。再由MemLeakChecker、UseAfterFreeChecker、DoubleFreeChecker、DoubleLockChecker Pass對(duì)sinkPaths進(jìn)行漏洞檢測(cè)，并保存漏洞。

2.1 UseAfterReturn

Figure4-Dangling Pointer.png

漏洞說(shuō)明：如圖4所示，子圖a模擬了一個(gè)具有指針懸空漏洞的系統(tǒng)調(diào)用，在add_x函數(shù)中，局部指針變量p被賦值給全局指針變量global_p；在remove_x函數(shù)中，把全局指針變量global_p置空，但是在do_foo函數(shù)中，我們可以看到，只有在滿足特定條件（③）下才執(zhí)行remove_x函數(shù)，因此存在指針懸空的漏洞。

檢測(cè)UAR漏洞：首先從局部變量（local node）開(kāi)始前向遍歷VFG，如果函數(shù)的exit個(gè)數(shù)大于函數(shù)入口個(gè)數(shù)，即判定有對(duì)該local node的引用離開(kāi)了有效區(qū)域。例如，對(duì)于local_x結(jié)點(diǎn)，add_x一個(gè)入口，add_x一個(gè)exit，do_foo一個(gè)exit，最后發(fā)現(xiàn)一條路徑使得local_x離開(kāi)了有效區(qū)域：local_x->①->②->③->⑤->⑥。然后反向遍歷VFG，找到對(duì)該local node的引用，則為懸垂指針。找到一條⑥->⑤->③->②->global_p，即存在一個(gè)指針懸空漏洞。此外，由于有了PAG圖，在反向查找的時(shí)候就可以避免訪問(wèn)不屬于當(dāng)前跟蹤的內(nèi)存對(duì)象的邊（例如：⑤->④）。最后把該bug所經(jīng)過(guò)的路徑信息和相應(yīng)的節(jié)點(diǎn)等保存下來(lái)，以便后續(xù)處理。

2.2 MemLeak、UseAfterFree、DoubleFree、DoubleLock

6-漏洞建模.png

前面已經(jīng)提到過(guò)，MemLeakChecker、UseAfterFreeChecker、DoubleFreeChecker、DoubleLockChecker Pass只需對(duì)sinkPaths進(jìn)行漏洞檢測(cè)，并保存漏洞。這4類漏洞的有兩個(gè)不同點(diǎn)，一是對(duì)source點(diǎn)、sink點(diǎn)的定義不同，只要定義好了source和sink點(diǎn)，調(diào)用SrcSnkAnalysis類即可得到source點(diǎn)到sink點(diǎn)的路徑——sinkPaths；二是對(duì)漏洞的建模，以下是漏洞的具體判定條件：

（1）MemLeak

• 遍歷sinkPaths，也即所有從指定source點(diǎn)到任意sink點(diǎn)的路徑，只要找到1個(gè)sink點(diǎn)是解引用（釋放）結(jié)點(diǎn)，則沒(méi)有內(nèi)存泄露漏洞（這個(gè)判定有漏報(bào)，如果存在一條路徑?jīng)]有釋放內(nèi)存，也會(huì)導(dǎo)致內(nèi)存泄露）。

• 沒(méi)有遇到釋放點(diǎn)，則包含漏洞，調(diào)用handleBug(root)，創(chuàng)建NeverFreeBug bug漏洞類，設(shè)定leakptr位置（即root結(jié)點(diǎn)的所在文件名、所在函數(shù)名、所在源碼行數(shù)、變量名）—sourceLoc、從root結(jié)點(diǎn)到syscall開(kāi)頭的路徑—apiPath、分析時(shí)長(zhǎng)—time。

（2）UseAfterFree

• SrcSnkAnalysisContext::sortPaths()：流敏感的SinkPaths，即fsSinkPaths。將 sinkPaths 中的元素按照?qǐng)?zhí)行流順序排列，插入到fsSinkPaths（將NullStoreNode 放 fsSinkPaths 的后面，感覺(jué)較低效，判斷可達(dá)性—AnalysisContext::isReachable需要判斷VFG_edges值流路徑上，前面每個(gè)結(jié)點(diǎn)是否相同，判斷過(guò)程復(fù)雜）。

• 遍歷 fsSinkPaths 中任意兩個(gè)元素 item1、item2，若item1為釋放點(diǎn)、item2為使用點(diǎn)、且兩點(diǎn)的值流路徑可達(dá)，則為UAF漏洞，item2為 NullStoreNode則無(wú)漏洞。（可能存在誤報(bào)，就算item2為使用點(diǎn)，item1

（3）DoubleFree

• 遍歷 fsSinkPaths 中任意兩個(gè)元素 item1、item2，若item1和item2都是釋放點(diǎn)、且兩點(diǎn)的值流路徑可達(dá)，則為Double-Free漏洞，item2為 NullStoreNode則無(wú)漏洞。（可能存在誤報(bào)，就算item2也為釋放點(diǎn)，item1和item2之間可能還有清零點(diǎn)）。

• 調(diào)用handleBug(root, item1, item2)，創(chuàng)建DoubleFreeBug 漏洞類，設(shè)定懸垂指針—souce、釋放點(diǎn)—sink1、釋放點(diǎn)—sink2的位置（所在的文件名、函數(shù)名、行數(shù)）、從root結(jié)點(diǎn)到syscall開(kāi)頭的路徑—apiPath、分析時(shí)長(zhǎng)—time。

（4）DoubleLock

• 遍歷 fsSinkPaths 中任意兩個(gè)元素 item1、item2，若item1和item2都是加鎖點(diǎn)、且兩點(diǎn)的值流路徑可達(dá)、且item2不在 nonCriticalPaths 集合中，則為Double-Lock漏洞；若item2為解鎖結(jié)點(diǎn)，則無(wú)漏洞，進(jìn)一步若item1和item2可達(dá)，則item2可達(dá)的所有結(jié)點(diǎn)都加入到 nonCriticalPaths。

• 調(diào)用handleBug(root, item1, item2)，創(chuàng)建DoubleLockBug 漏洞類，設(shè)定鎖對(duì)象—souce、加鎖點(diǎn)—sink1、加鎖點(diǎn)—sink2的位置（所在的文件名、函數(shù)名、行數(shù)）、從root結(jié)點(diǎn)到syscall開(kāi)頭的路徑—apiPath、分析時(shí)長(zhǎng)—time。

3. 優(yōu)化

如何使得檢測(cè)效率更高？

重訪函數(shù)：使用不同的pass時(shí)，可能會(huì)使用不同的輸入多次訪問(wèn)同一函數(shù)，該函數(shù)又會(huì)調(diào)用其他函數(shù)并重復(fù)轉(zhuǎn)發(fā)結(jié)果，效率低下。改進(jìn)就是，對(duì)函數(shù)的所有可能上下文僅處理一次并存儲(chǔ)中間結(jié)果，如果某分析使用給定context來(lái)查詢某個(gè)函數(shù)entry node，該分析會(huì)先檢查是否已訪問(wèn)過(guò)該node，重用之前的結(jié)果。

并行：使用OpenMP 實(shí)現(xiàn)部分的并行。說(shuō)白了就是簡(jiǎn)單的使用了OpemMP庫(kù)函數(shù)，把作者認(rèn)為能夠并行的代碼框起來(lái)，讓編譯器去自動(dòng)化并行。

參考：

白澤帶你讀論文丨K-Miner: Uncovering Memory Corruption in Linux

【讀書(shū)筆記】ndss2018_K-Miner_ Uncovering Memory Corruption in Linux