空指引引用錯(cuò)誤例解

空指引引用錯(cuò)誤例解

指針是c、c.+和其他語言的靈活增加，但指針使用不充分會(huì)導(dǎo)致程序錯(cuò)誤和安全隱患。其中,空指針引用(nullpointerdereference,NPD)是一種最常見的指針使用不當(dāng)?shù)谋憩F(xiàn)。NPD錯(cuò)誤不僅會(huì)導(dǎo)致程序崩潰,有時(shí)還可能成為安全漏洞。據(jù)中國國家信息安全漏洞庫統(tǒng)計(jì),由NPD錯(cuò)誤造成的安全漏洞每年有70個(gè)左右被報(bào)告出來,這些漏洞甚至出現(xiàn)在Linux、WindowsServer、VMware、Apache等重要的基礎(chǔ)軟件中,造成拒絕服務(wù)、非法權(quán)限提升、執(zhí)行任意代碼等嚴(yán)重安全問題。一種直接預(yù)防NPD錯(cuò)誤的方法是在每條指針解引用語句之前加入判斷語句,確保指針不為空時(shí)再執(zhí)行解引用操作。該方法雖然保險(xiǎn),但也會(huì)帶來一些問題:1)在多線程執(zhí)行的程序中有時(shí)并不有效目前的錯(cuò)誤檢測方法分為動(dòng)態(tài)檢測和靜態(tài)檢測。動(dòng)態(tài)檢測難以保證100%的代碼覆蓋率,且輸入樣例難以構(gòu)造;靜態(tài)檢測則在代碼覆蓋率方面有優(yōu)勢,檢測錯(cuò)誤時(shí)更有針對性。在技術(shù)方面,靜態(tài)檢測除了傳統(tǒng)的流分析,還常常與程序驗(yàn)證、模型檢測、定理證明、符號(hào)執(zhí)行等技術(shù)相結(jié)合,以獲得更高的檢測精度使用靜態(tài)方法檢測NPD錯(cuò)誤是近年來研究的重點(diǎn)。Xie等綜上,目前的工具和方法還有如下問題:要么過程間分析不完整,要么開銷巨大;過程內(nèi)分析不精確,路徑覆蓋率不夠或者指針指向估計(jì)不準(zhǔn);對涉及調(diào)用庫函數(shù)的代碼普遍分析不準(zhǔn);無法解決由exit等函數(shù)造成的特殊控制流問題針對這些問題,本文提出一種過程內(nèi)流敏感、路徑敏感和過程間上下文敏感的多敏感NPD錯(cuò)誤靜態(tài)檢測方法。該方法結(jié)合傳統(tǒng)靜態(tài)分析方法和符號(hào)執(zhí)行方法,按照程序執(zhí)行的順序進(jìn)行分析,記錄并推斷指針變量的指向信息,采用一種折中的路徑敏感分析方法,在函數(shù)內(nèi)進(jìn)行路徑遍歷,將路徑上的分支條件和指針信息轉(zhuǎn)換成約束表達(dá)式,并用約束求解器求解可滿足性來判斷路徑是否可達(dá);利用在函數(shù)退出點(diǎn)進(jìn)行信息合并的方法減少信息記錄的數(shù)目,并減輕不能跨函數(shù)路徑遍歷造成的精度損失。另外,對沒有源代碼的庫函數(shù)以及部分普通函數(shù)使用人工標(biāo)注錯(cuò)誤觸發(fā)條件的手段,提高分析精確度和效率。與符號(hào)執(zhí)行方法相比,本文方法減少了計(jì)算量和信息記錄數(shù)量。實(shí)驗(yàn)證明該方法分析時(shí)間短、資源消耗少、檢測精度高。1有限狀態(tài)機(jī)fsm根據(jù)出錯(cuò)指針的可見域及其定值和解引用位置,NPD錯(cuò)誤的具體形式可以歸結(jié)為4種類型,分別是:1)局部變量為NULL;2)全局變量為NULL;3)函數(shù)參數(shù)為NULL;4)函數(shù)返回值為NULL。在實(shí)際編程中,特別是當(dāng)使用他人編寫的接口或者庫函數(shù)時(shí),后兩種錯(cuò)誤形式更易發(fā)生且更難檢查。4種NPD錯(cuò)誤代碼的示例如圖1所示。NPD錯(cuò)誤僅與指針的指向有關(guān),與其他類型變量的取值無關(guān)。為提高分析效率,本文方法只對指針類型變量(包括全局指針、局部指針以及作為函數(shù)參數(shù)的指針)進(jìn)行建模,忽略其他類型的變量。本文用有限狀態(tài)機(jī)(finitestatemachine,FSM)表示NPD錯(cuò)誤模型。在檢測NPD錯(cuò)誤時(shí),只需知道指針是否為空,所以指針的指向狀態(tài)可簡化為“空(Null)”和“非空(NotNull)”兩種狀態(tài),考慮到靜態(tài)分析的不確定性,再添加一種“可能為空(MayBeNull)”的狀態(tài)。該FSM有{Null,NotNull,MaybeNull,MayBeError,Error}5種狀態(tài),其中Null是起始狀態(tài),MayBeError和Error為終態(tài),完整的狀態(tài)轉(zhuǎn)換如圖2所示。該FSM狀態(tài)轉(zhuǎn)換條件如表1所示。檢測時(shí)每個(gè)指針變量都要記錄一個(gè)FSM。全局指針在聲明后會(huì)默認(rèn)初始化為NULL,而局部指針變量在聲明后根據(jù)內(nèi)存棧上的當(dāng)前值指向一個(gè)隨機(jī)的地址。無論是指向NULL,還是指向隨機(jī)的地址,此時(shí)對指針進(jìn)行解引用都是不正確的。為減少狀態(tài),假設(shè)局部指針在聲明時(shí)也默認(rèn)初始化為NULL。因此,本文指定FSM的初始狀態(tài)為Null,當(dāng)某個(gè)FSM的狀態(tài)變?yōu)镋rror或者M(jìn)ayBeError,則說明檢測出了一個(gè)NPD錯(cuò)誤或者可能的NPD錯(cuò)誤。2路徑敏感的分析方法在程序內(nèi),一條分支語句會(huì)形成兩條可執(zhí)行路徑。隨著分支語句的增多,組合后的可執(zhí)行路徑數(shù)量將呈指數(shù)級(jí)增長。圖3是包含多路徑程序的一個(gè)例子。其中,圖3(a)代碼對應(yīng)的控制流圖如圖3(b)所示,兩條分支語句組成“真-真”、“真-假”、“假-真”、“假-假”4條路徑。路徑不敏感的方法不區(qū)分路徑,在分析到第9行時(shí)會(huì)認(rèn)為p可能為空,然后對第10行報(bào)告NPD錯(cuò)誤。這是一個(gè)誤報(bào),因?yàn)榉治隹芍?要觸發(fā)該NPD,需要執(zhí)行“假-真”路徑,但因?yàn)閍不能既等于0又不等于0,所以“假-真”路徑實(shí)際上不可能被執(zhí)行。路徑敏感的方法區(qū)分不同路徑,同時(shí)考慮分支條件組合,可以避免該類誤報(bào)。路徑敏感的方法記錄所有路徑的信息,分析結(jié)果精確,但也面臨路徑組合爆炸的問題。為避免路徑組合爆炸并減少誤報(bào),本文提出一種新型的路徑敏感的分析方法。本文方法分析函數(shù)內(nèi)路徑的可達(dá)性并剪枝,只分析可達(dá)路徑上存在的NPD錯(cuò)誤,最后在函數(shù)退出點(diǎn)將多條路徑的信息合并成一條,供調(diào)用函數(shù)使用。2.1路徑可達(dá)性分析本文方法使用約束求解的方式計(jì)算路徑可達(dá)性,剔除不可達(dá)的路徑,以減少分析量,提高檢測精度,減少誤報(bào)。本文方法按照深度優(yōu)先遍歷函數(shù)控制流圖(controlflowgraph,CFG)的順序來分析函數(shù)。分析過程中需要記錄從程序起點(diǎn)到當(dāng)前分析的基本塊之間的路徑。每當(dāng)分析完一個(gè)基本塊并將要開始分析另一個(gè)基本塊時(shí),需計(jì)算路徑的可達(dá)性。方法是將路徑上的分支條件組合成一條布爾型的約束表達(dá)式,并用SMT-Solver求解該表達(dá)式的可滿足性,若可滿足則認(rèn)為該路徑可達(dá)。如圖3(a)中的函數(shù)foo有5個(gè)基本塊,圖3(b)上已編號(hào)1~5。當(dāng)分析路徑為1→2時(shí),即分析到第一個(gè)if的真分支,路徑可達(dá)性表達(dá)式為a!=0,該表達(dá)式可滿足,說明該路徑可達(dá)。當(dāng)分析路徑為1→3→4→5(即“假-真”路徑)時(shí),則路徑可達(dá)性的約束表達(dá)式為(a==0)&&(a!=0),由于該表達(dá)式不可滿足,就說明該條路徑不可達(dá)。當(dāng)判斷出某條路徑不可達(dá)時(shí),就放棄分析該條路徑及由該路徑向后延伸的路徑。與符號(hào)執(zhí)行的方法不同,由于本文方法只對指針建模,所以在分析時(shí)無法估算其他類型變量的范圍。在建立路徑可達(dá)性表達(dá)式時(shí),如果分支條件中包含指針變量,則使用分析值替換變量(MaybeNull既可以是空,也可以非空),對于分支條件中其他類型的變量,不對其范圍進(jìn)行限制。2.2路徑敏感的檢驗(yàn)如果有多條可達(dá)路徑會(huì)對函數(shù)下文造成更改(即修改了全局指針指向,通過函數(shù)參數(shù)中的高維指針修改了低維指針的指向,返回指針變量供調(diào)用函數(shù)使用),且更改不同,則需要在函數(shù)退出前進(jìn)行信息合并。對某個(gè)指向會(huì)被修改的指針變量p,具體的合并規(guī)則如下:1)如果每條路徑上都有修改且修改均為Null,則改為Null;2)如果每條路徑上都有修改且修改均為NotNull,則改為NotNull;3)如果有某條路徑上的修改為MayBeNull,則改為MayBeNull;4)如果p之前狀態(tài)不為Null,有但不是所有路徑上的修改為Null,則改為MayBeNull;5)如果p之前狀態(tài)為Null,有但不是所有路徑上的修改為NotNull,則改為MayBeNull;6)其他情況不做修改。比如某全局指針開始時(shí)的狀態(tài)為Null,函數(shù)中有兩條執(zhí)行路徑,一條路徑上將狀態(tài)改為了NotNull,而另一條未做修改,則根據(jù)上述規(guī)則5),在函數(shù)退出時(shí)將狀態(tài)改為MayBeNull。因此,分析后面的程序時(shí),如果直接出現(xiàn)對該指針的解引用,可以發(fā)現(xiàn)一個(gè)可能的NPD錯(cuò)誤。路徑敏感是可以跨函數(shù)的,對于有多條可執(zhí)行路徑的被調(diào)函數(shù),要將所有路徑的信息單獨(dú)記錄下來再回到調(diào)用函數(shù)去分析,該方法精確,但開銷巨大。文獻(xiàn)[7,9]中使用“可能指向”來表示多條分支對指針指向修改的不同,但它們的方法是路徑不敏感的,等價(jià)于分層而不是深度優(yōu)先遍歷CFG,即每次分析一個(gè)分支語句,待分支匯合后再繼續(xù)分析后面的程序,相當(dāng)于每分析一個(gè)分支就進(jìn)行一次信息合并,如果此時(shí)將某指針指向設(shè)為“可能為空”,且之后分支中出現(xiàn)該指針的解引用,則無法確定NPD錯(cuò)誤是否發(fā)生在可達(dá)路徑上。本文方法選擇在函數(shù)退出點(diǎn)進(jìn)行信息合并,相比不合并,本文方法開銷更少,且精度相差不多,相比每個(gè)分支后合并,可以降低誤報(bào)。3過程前后的性能敏感指針為參數(shù)或者返回值的函數(shù)普遍存在,分析這類函數(shù)中的NPD錯(cuò)誤必須考慮函數(shù)被調(diào)位置的上下文。上下文不敏感的方法一般不考慮這些因素,如圖1(c)中的foo函數(shù),上下文不敏感的方法會(huì)對foo報(bào)告一個(gè)潛在的NPD錯(cuò)誤,條件是假設(shè)foo的參數(shù)s可能為空。但如果程序中所有調(diào)用foo的位置傳入的均不是空指針,就是誤報(bào)。為減少誤報(bào),本文提出一種新型的上下文敏感的分析方法。本文方法在分析函數(shù)調(diào)用時(shí)將指針指向傳遞給被調(diào)函數(shù),而當(dāng)分析無源代碼的庫函數(shù)調(diào)用時(shí),根據(jù)事先人工標(biāo)注的行為進(jìn)行處理。分析函數(shù)調(diào)用時(shí)的處理流程圖如圖4所示。3.1被調(diào)函數(shù)的位置分析被調(diào)函數(shù)時(shí),首先記錄主調(diào)函數(shù)的分析位置,然后向被調(diào)函數(shù)傳入指針類型實(shí)參的狀態(tài),并跳轉(zhuǎn)到被調(diào)函數(shù)進(jìn)行路徑敏感的過程內(nèi)分析,分析完成后再跳回到主調(diào)函數(shù)之前記錄的位置繼續(xù)分析。如果被調(diào)函數(shù)返回指針,則將返回的指針狀態(tài)傳遞給主調(diào)函數(shù)中接受返回值的變量。例如圖1(c)中的代碼,分析到第6行的foo(a)時(shí),有一個(gè)局部指針a,其狀態(tài)為Null。將a的狀態(tài)作為實(shí)參傳給foo,之后開始對foo函數(shù)進(jìn)行分析。在foo中,有一個(gè)可見的指針,即其形參s,其狀態(tài)與之前傳入的實(shí)參相同,為Null。繼續(xù)分析到第2行,在該處對s解引用,根據(jù)FSM轉(zhuǎn)換規(guī)則,s的狀態(tài)機(jī)變?yōu)镋rror,即發(fā)現(xiàn)一個(gè)NPD錯(cuò)誤。3.2靜態(tài)分析時(shí)程序的標(biāo)定當(dāng)被調(diào)函數(shù)為庫函數(shù)或者內(nèi)嵌函數(shù)(built-in)時(shí),無法定位源代碼。本文的做法是對這些函數(shù)事先進(jìn)行人工標(biāo)注,標(biāo)注內(nèi)容包括該函數(shù)是否返回空指針和觸發(fā)該函數(shù)中NPD錯(cuò)誤的條件。比如malloc函數(shù)通常會(huì)返回非空指針,但在內(nèi)存不夠分配時(shí),會(huì)返回空指針,所以將malloc的返回值標(biāo)為MayBeNull,在分析時(shí)如果遇到malloc函數(shù)調(diào)用,則直接將獲得其返回值的指針變量狀態(tài)設(shè)為MayBeNull。又比如計(jì)算字符串長度的strlen函數(shù),在參數(shù)為空指針時(shí)就會(huì)觸發(fā)NPD錯(cuò)誤,所以將strlen函數(shù)的NPD錯(cuò)誤觸發(fā)條件標(biāo)記為參數(shù)為空指針,在分析時(shí)如果遇到strlen,則直接判斷實(shí)參指針的狀態(tài)是否為Null或者M(jìn)ayBeNull。除了解決沒有源代碼的問題,本文還利用人工標(biāo)注信息解決特殊控制流的問題。exit、assert等函數(shù)會(huì)改變程序正常的執(zhí)行流,當(dāng)程序執(zhí)行到exit時(shí)就會(huì)退出,不再執(zhí)行后面的代碼。靜態(tài)分析方法如果將這些函數(shù)當(dāng)成普通函數(shù)繼續(xù)分析,則不能得到正確的分析結(jié)果。本文的做法是對exit等影響程序正常執(zhí)行的函數(shù)進(jìn)行標(biāo)注,分析中一旦遇到這些函數(shù),就終止分析當(dāng)前路徑,并回溯到路徑分叉點(diǎn)開始分析新路徑。另外,人工標(biāo)注還能減少分析工作量,對于普通的函數(shù),即使有源代碼,也可進(jìn)行標(biāo)注。分析已標(biāo)注的函數(shù)時(shí),可直接使用標(biāo)注信息,不用再分析該函數(shù),類似于提取函數(shù)摘要4實(shí)驗(yàn)與分析4.1真實(shí)工程檢測方法評(píng)價(jià)使用LLVM編譯框架從發(fā)現(xiàn)錯(cuò)誤的能力和對真實(shí)工程的測試情況兩方面對檢測方法進(jìn)行評(píng)價(jià)。使用Splint和ClangStaticAnalyzer作為比較對象。4.2執(zhí)行程序中的誤報(bào)測試工具檢測能力的樣例來自SAMATEReferenceDataset(SRD),該數(shù)據(jù)集由包含錯(cuò)誤和漏洞的程序組成,被設(shè)計(jì)用于檢測程序分析工具的能力。本文從SRD中選擇了7個(gè)具有代表性的樣例,每個(gè)樣例包含1個(gè)真實(shí)的NPD錯(cuò)誤以及若干個(gè)用來測試誤報(bào)的“偽NPD錯(cuò)誤”。3個(gè)工具對測試樣例錯(cuò)誤的檢測情況如表2所示。由于Splint和ClangStaticAnalyzer可以檢測多種錯(cuò)誤,本文只統(tǒng)計(jì)其報(bào)告的NPD錯(cuò)誤。同一個(gè)位置的NPD錯(cuò)誤報(bào)告均按1次統(tǒng)計(jì)。需要說明的是,原始的34667號(hào)樣例使用printf打印字符串觸發(fā)NPD,但打印字符串空指針是未定義行為(undefinedbehavior)由表2可以看出:對所選的7個(gè)樣例程序,NPD-Checker沒有漏報(bào),且誤報(bào)很少,只在一個(gè)測試樣例上出現(xiàn)了誤報(bào);Splint出現(xiàn)了較多的誤報(bào)和漏報(bào);ClangStaticAnalyzer則出現(xiàn)了一半漏報(bào)。ClangStaticAnalyzer漏報(bào)主要是因?yàn)閷旌瘮?shù)調(diào)用的分析不準(zhǔn)。比如對38733號(hào)樣例,其沒考慮到fopen可能返回NULL,以及fclose在接受NULL作為參數(shù)時(shí)會(huì)發(fā)生NPD錯(cuò)誤;對38772和38997號(hào)樣例,其沒有考慮到calloc分配內(nèi)存失敗會(huì)返回NULL。Splint相比ClangStaticAnalyzer分析能力較弱,但是其約束條件較松,可將很多可能的NPD錯(cuò)誤報(bào)出,減少了漏報(bào),但增加了誤報(bào)。Splint的誤報(bào)主要是因?yàn)槠渲贿M(jìn)行函數(shù)內(nèi)分析,不進(jìn)行跨函數(shù)分析,并且在函數(shù)內(nèi)分析時(shí)沒有考慮路徑可達(dá)性。比如對38772號(hào)樣例,其認(rèn)為對goodB2G_sink函數(shù)傳遞空指針會(huì)觸發(fā)NPD,但goodB2G_sink函數(shù)會(huì)先行判斷指針是否為空。對34667號(hào)樣例,程序在一個(gè)if語句的假分支中將指針設(shè)為NULL,在分支之后解引用,但分支條件是一個(gè)恒為真的表達(dá)式,所以不可能發(fā)生NPD錯(cuò)誤。NPDChecker之所以會(huì)出現(xiàn)誤報(bào)是因?yàn)楸疚姆椒ㄖ粚χ羔樈?沒有對其他變量建模。對34667號(hào)樣例,由于if語句中的條件表達(dá)式是關(guān)于整形變量的,所以沒有計(jì)算其范圍,在使用SMT-Solver求解可滿足性時(shí)約束太松,導(dǎo)致真假分支均可滿足,所以產(chǎn)生了誤報(bào)。4.3不同算法的analyze幾個(gè)常見的開源代碼的行數(shù)統(tǒng)計(jì)以及兩個(gè)工具對它們的分析結(jié)果如表3所示。測試時(shí)沒有使用Splint作為比較對象,主要是因?yàn)镾plint只進(jìn)行過程內(nèi)分析,理論時(shí)間與另外兩個(gè)工具不是一個(gè)數(shù)量級(jí),且誤報(bào)太多,對比性不強(qiáng)。從表3可以看出:1)NPDChecker檢測時(shí)花費(fèi)的時(shí)間小于ClangStaticAnalyzer,這是因?yàn)楸疚姆椒ㄖ恍枰涗浿羔樧兞康男畔?且狀態(tài)少,而ClangStaticAnalyzer使用符號(hào)執(zhí)行的方法,需要計(jì)算各種變量的范圍,計(jì)算量大。2)NPDChecker有幾個(gè)誤報(bào),誤報(bào)數(shù)量比ClangStaticAnalyzer稍多。分析代碼發(fā)現(xiàn)這些誤報(bào)均為不可達(dá)路徑上的錯(cuò)誤,誤報(bào)原因如前所述。分析ClangStaticAnalyzer的檢測結(jié)果后可找到一個(gè)有