基于數(shù)據(jù)流分析的Java 空指針引用異常缺陷檢測(cè)?

王國(guó)峰 唐云善 徐立飛

（1.南瑞集團(tuán)有限公司（國(guó)網(wǎng)電力科學(xué)研究院有限公司） 南京 210003）（2.南京南瑞信息通信科技有限公司 南京 210003）

1 引言

源代碼的安全是計(jì)算軟件安全的基石，而源代碼的缺陷檢測(cè)正是穩(wěn)固此塊基石的重要方式［1］。據(jù)中國(guó)國(guó)家信息安全漏洞庫(kù)統(tǒng)計(jì)，由空指針引用異常（Null Pointer Dereference，NPD）造成的安全漏洞引發(fā)了許多嚴(yán)重的安全問(wèn)題，諸如系統(tǒng)崩潰、越權(quán)操作、拒絕服務(wù)和執(zhí)行惡意代碼等［2～3］。目前對(duì)于NPD 漏洞的檢測(cè)主要分為動(dòng)態(tài)檢測(cè)和靜態(tài)檢測(cè)兩種方式［4～5］。其中靜態(tài)檢測(cè)無(wú)需運(yùn)行程序，直接通過(guò)語(yǔ)法和詞法等技術(shù)手段對(duì)編譯后的文件進(jìn)一步分析，即可找出程序中可能存在的缺陷。這種檢測(cè)方式速度快、效率高，廣受業(yè)界青睞［6～7］。

在現(xiàn)有的關(guān)于NPD 缺陷靜態(tài)檢測(cè)方法中，Zhang 等［8］通過(guò)對(duì)缺陷報(bào)告的分析，排除一些明顯的誤報(bào)，來(lái)提升對(duì)NPD 缺陷的檢測(cè)準(zhǔn)確度，但噪聲報(bào)告同時(shí)也會(huì)對(duì)優(yōu)化結(jié)果產(chǎn)生二次影響。畢學(xué)軍等［9］通過(guò)在控制流的基礎(chǔ)上利用變量區(qū)間來(lái)表示狀態(tài)的前提條件，對(duì)程序中不可達(dá)路徑進(jìn)行處理，從而達(dá)到減少誤報(bào)的目的。但該方法未能進(jìn)一步解決狀態(tài)出現(xiàn)ERROR 情況下，導(dǎo)致分支不可達(dá)下的缺陷漏報(bào)問(wèn)題。楊睿等［10］基于NPD 缺陷狀態(tài)機(jī)模型，通過(guò)函數(shù)摘要的生成傳遞與使用支撐數(shù)組空指針故障的全局分析與檢測(cè)，從而減少漏報(bào)。但其考慮的函數(shù)摘要并不完善，對(duì)Java代碼中的諸多函數(shù)類(lèi)型如返回值、I/O 操作類(lèi)型等均未涉及，因此該方法僅適用于數(shù)組的NPD檢測(cè)上。

針對(duì)上述問(wèn)題，本文提出了一種基于數(shù)據(jù)流分析的Java空指針引用異常缺陷檢測(cè)方法，該方法根據(jù)NPD 缺陷模式的缺陷特征，設(shè)計(jì)了對(duì)應(yīng)的數(shù)據(jù)流值、格值計(jì)算規(guī)則和傳遞函數(shù)，以此來(lái)確保數(shù)據(jù)流值在程序控制流圖（Control Flow Graph，CFG）上按照設(shè)定的傳遞函數(shù)進(jìn)行前向分析，然后遍歷CFG上每個(gè)節(jié)點(diǎn)的數(shù)據(jù)流值，找出格值為ERROR 的變量，報(bào)出NPD 缺陷故障點(diǎn)。最后，文章通過(guò)對(duì)比試驗(yàn)驗(yàn)證了該方法的有效性及性能效果。

2 空指針引用異常缺陷

2.1 缺陷模式

缺陷模式指一類(lèi)缺陷產(chǎn)生時(shí)程序所呈現(xiàn)的共同的語(yǔ)法或語(yǔ)義特征，描述了程序的一種屬性，滿足該屬性則產(chǎn)生缺陷［11］。NPD 缺陷模式則是描述了被引用的指針指向了無(wú)效的內(nèi)存區(qū)域的屬性。當(dāng)缺陷模式確定后，被用來(lái)檢測(cè)某一程序是否違反了程序語(yǔ)法或語(yǔ)義規(guī)則的屬性，即被稱為該缺陷模式的缺陷特征［12］。NPD 缺陷模式的缺陷特征就是被引用的指針，因此，通過(guò)檢測(cè)該指針變量是否為空指針，即可判定是否產(chǎn)生NPD缺陷。

2.2 空指針引用異常缺陷實(shí)例

Java 語(yǔ)言中沒(méi)有指針這個(gè)概念，因而Java 中的空指針用空值句柄（Handle）來(lái)表征［13］?？罩羔樢脛t表明對(duì)一個(gè)空值句柄的方法、字段或者域的調(diào)用，在此調(diào)用過(guò)程中，編譯器則會(huì)拋出Null Pointer Exception錯(cuò)誤，即空指針引用異常。

結(jié)合圖1 的NPD 代碼實(shí)例，變量a 和變量c 的初始化均為空值null。若第8 行變量num1 的值大于b.hashCode（），則變量b 加上字符串“world”的值將賦給變量a，此時(shí)a 不再是空值null，從而第15 行系統(tǒng)打印函數(shù)對(duì)a 的調(diào)用不會(huì)報(bào)錯(cuò)，但若第8 行的if 條件語(yǔ)句的判斷為false，則a 的值依然為null，從而導(dǎo)致第15行出現(xiàn)NPD錯(cuò)誤。

圖1 NPD缺陷代碼實(shí)例

程序第11 行，a 加c 之后的值賦給變量d，由于a和c均為空值null，從而變量d的值也為空值null，這就導(dǎo)致第12行的d.length（）調(diào)用語(yǔ)句引發(fā)對(duì)變量d的NPD，以及第14行也同時(shí)出現(xiàn)NPD錯(cuò)誤。

3 空指針引用異常缺陷檢測(cè)流程

NPD 缺陷檢測(cè)流程如下所示，共分為五個(gè)步驟。其中步驟3至步驟5為本文的主要工作。

步驟1：對(duì)待分析源碼進(jìn)行掃描，通過(guò)詞法、語(yǔ)法分析構(gòu)建源碼的抽象語(yǔ)法樹(shù)模型；

步驟2：通過(guò)抽象語(yǔ)法樹(shù)模型將源碼轉(zhuǎn)化成三地址碼這種代碼的中間表示；

步驟3：通過(guò)多次遍歷三地址碼，構(gòu)建程序CFG，并設(shè)計(jì)NPD 缺陷模式的數(shù)據(jù)流值、數(shù)據(jù)流值的交匯計(jì)算規(guī)則和數(shù)據(jù)流的傳遞函數(shù)；

步驟4：在CFG 上，根據(jù)傳遞函數(shù)計(jì)算CFG 中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)流值，完成數(shù)據(jù)流前向分析；

步驟5：遍歷CFG 上各節(jié)點(diǎn)分析后的數(shù)據(jù)流值，根據(jù)NPD 缺陷模式狀態(tài)劃分，找到格值為ERROR的變量，報(bào)出NPD缺陷代碼片段。

4 空指針引用異常缺陷檢測(cè)算法

4.1 NPD缺陷模式數(shù)據(jù)流值

NPD缺陷模式數(shù)據(jù)流值是一個(gè)對(duì)，由被分析變量及其格值組成的pair<變量名，格值>。根據(jù)NPD的缺陷模式，本文設(shè)計(jì)的格值集合一共有三個(gè)定值，即S=｛NULL，NOTNULL，ERROR｝。其中定值NULL表示Java句柄中被分析變量在前趨數(shù)據(jù)流節(jié)點(diǎn)的格值為NULL；定值NOTNULL 表示Java 句柄中被分析變量在前趨數(shù)據(jù)流節(jié)點(diǎn)的格值為NOTNULL；定值ERROR 表示當(dāng)前Java句柄中被分析變量產(chǎn)生了空指針引用異常缺陷。

圖2 所示格圖的頂元素為格值ERROR，表明所有檢測(cè)變量均出現(xiàn)了NPD 缺陷，這個(gè)分析結(jié)果是安全的但會(huì)出現(xiàn)大量誤報(bào)；格圖的底元素為格值NOTNULL，表明所有檢測(cè)變量均未出現(xiàn)NPD缺陷，這個(gè)分析結(jié)果是不安全的且會(huì)出現(xiàn)大量漏報(bào)；其他數(shù)據(jù)流值則是無(wú)序的空值NULL。NPD缺陷檢測(cè)的數(shù)據(jù)流分析屬于may分析，所以只需在格圖上找到最小不動(dòng)點(diǎn)，即可得到分析的最優(yōu)結(jié)果。

圖2 數(shù)據(jù)流值格圖

4.2 數(shù)據(jù)流值交匯計(jì)算規(guī)則

當(dāng)程序經(jīng)過(guò)諸如分支判斷語(yǔ)句時(shí)，數(shù)據(jù)流會(huì)分成多個(gè)分支，進(jìn)而需要在分支語(yǔ)句結(jié)束后對(duì)同一變量的格值完成交匯操作，記作Fmeet。數(shù)據(jù)流值交匯操作時(shí)的計(jì)算規(guī)則如下：

Fmeet(NULL,NULL)=NULL，表示空值與空值交匯后是空值；

Fmeet(NULL,NOTNULL)=NULL，表示空值與非空值交匯的最小上界是空值；

Fmeet(NOTNULL,NOTNULL)=NOTNULL，表示非空值與非空值交匯后是非空值；

Fmeet(ERROR,NULL)=ERROR，表示ERROR與空值交匯的最小上界是ERROR；

Fmeet(ERROR,NOTNULL)=ERROR，表示ERROR與非空值交匯的最小上界是ERROR；

Fmeet(ERROR,ERROR)=ERROR，表示ERROR與ERROR交匯后是ERROR。

4.3 NPD缺陷檢測(cè)的數(shù)據(jù)流前向分析

NPD 缺陷檢測(cè)的數(shù)據(jù)流前向分析主要由三個(gè)部分組成：數(shù)據(jù)流的傳遞、數(shù)據(jù)流的交匯以及格值的計(jì)算。其中數(shù)據(jù)流動(dòng)的規(guī)則又稱為傳遞函數(shù)，它表征在一個(gè)分析語(yǔ)句之前和之后的數(shù)據(jù)流值受該分析語(yǔ)句的語(yǔ)義約束［14］。對(duì)于傳遞函數(shù)，本文設(shè)定的基本塊（Basic Block）中只有一條程序語(yǔ)句，且一條程序語(yǔ)句對(duì)應(yīng)的一條三地址碼語(yǔ)句記作一條Unit，包含多個(gè)程序語(yǔ)句的傳遞函數(shù)就可以將各個(gè)語(yǔ)句對(duì)應(yīng)的傳遞函數(shù)組合起來(lái)得到。傳遞函數(shù)接受的輸入是一個(gè)從程序變量到格中抽象值中元素的映射，而函數(shù)的返回值也是這樣一個(gè)映射［15］。數(shù)據(jù)流傳遞函數(shù)的設(shè)計(jì)如下：

式（1）中，Unit 表示CFG 中Unit 圖上的一個(gè)節(jié)點(diǎn)。｛（x，LatticeValue）｝就是數(shù)據(jù)流值。對(duì)傳遞函數(shù)的規(guī)則描述如下：

1）如果Unit是一個(gè)賦值語(yǔ)句，則會(huì)計(jì)算賦值語(yǔ)句右側(cè)部分的格值，并與賦值語(yǔ)句的左側(cè)變量組成計(jì)算后的數(shù)據(jù)流值傳入下一條Unit；

2）如果Unit 是一個(gè)調(diào)用語(yǔ)句（包括虛擬調(diào)用，靜態(tài)調(diào)用，特殊調(diào)用），則會(huì)計(jì)算調(diào)用語(yǔ)句的傳入?yún)?shù)的格值，并與調(diào)用主體組成計(jì)算后的數(shù)據(jù)流值傳入下一條Unit。

根據(jù)傳遞函數(shù)，具體的算法如圖3所示。

圖3 NPD缺陷檢測(cè)的數(shù)據(jù)流傳遞算法

算法1 首先將CFG 上的每個(gè)節(jié)點(diǎn)流入數(shù)據(jù)流值（FlowMapIn）和流出數(shù)據(jù)流值（FlowMapOut）初始為空的哈希集合，將CFG 上的每一條語(yǔ)句（Unit）存到工作表里（WorkList），然后對(duì)每一條語(yǔ)句執(zhí)行前向分析以確定語(yǔ)句中是否存在狀態(tài)約束轉(zhuǎn)換（第1行～23行）。

若當(dāng)前分析語(yǔ)句是賦值語(yǔ)句，且賦值語(yǔ)句的左側(cè)元素是局部變量，算法1 則會(huì)調(diào)用算法2 獲取當(dāng)前變量的數(shù)據(jù)流值，并將計(jì)算后的格值傳遞給下一條分析語(yǔ)句的輸入數(shù)據(jù)流值（第8行～13行）。

若當(dāng)前分析語(yǔ)句是調(diào)用語(yǔ)句，且調(diào)用語(yǔ)句的調(diào)用主體是局部變量，算法1 則會(huì)調(diào)用算法2 獲取此變量的數(shù)據(jù)流值，并將計(jì)算后的格值傳遞給下一條分析語(yǔ)句的輸入數(shù)據(jù)流值（第14行～19行）。

當(dāng)工作表里的語(yǔ)句全部遍歷完成后算法1 終止，進(jìn)而得到CFG上的每個(gè)節(jié)點(diǎn)的格值。

其中格值計(jì)算算法如圖4的算法2所示。算法2的輸入為FlowMapIn和StatementValue。

圖4 NPD缺陷檢測(cè)的格值計(jì)算算法

StatementValue 為待計(jì)算語(yǔ)句部分，它可能是賦值語(yǔ)句的右側(cè)部分或者調(diào)用語(yǔ)句的傳入?yún)?shù)。算法2會(huì)根據(jù)待計(jì)算部分進(jìn)行分類(lèi)計(jì)算。

若待計(jì)算部分是一個(gè)整形常量或字符常量則會(huì)返回NOTNULL（第15行～20行）；

若待計(jì)算部分為空或者構(gòu)建語(yǔ)句，則會(huì)返回NULL（第21行～26行）；

若待計(jì)算部分是一個(gè)局部變量，算法2 則會(huì)遍歷流入的數(shù)據(jù)流值，判斷此處的局部變量在先前節(jié)點(diǎn)中的格值，若先前的格值是NULL 或者ERROR，那此時(shí)對(duì)該變量的調(diào)用則為NPD 缺陷，從而返回ERROR，若先前的格值是NOTNULL，則返回NOTNULL，其他情況返回NULL（第6行～14行）；

若待計(jì)算部分為調(diào)用表達(dá)式，算法2 則會(huì)遞歸調(diào)用該算法，獲取計(jì)算后的格值（第27行～30行）；

若待計(jì)算部分是一個(gè)二元操作表達(dá)式，則會(huì)先計(jì)算二元操作符兩側(cè)成分的格值，當(dāng)兩側(cè)成分的格值均為NOTNULL 時(shí)，則返回NOTNULL，當(dāng)兩側(cè)成分的格值中有一側(cè)是NULL，且不為ERROR 時(shí)，則返回NULL，當(dāng)兩側(cè)成分的格值中有一側(cè)是ERROR時(shí)，則返回ERROR（第31行～39行）。

最后，當(dāng)工作表里的待計(jì)算語(yǔ)句部分全部計(jì)算完成后算法2 終止。此外，數(shù)據(jù)流值交匯計(jì)算的算法如圖5的算法3所示。

圖5 NPD缺陷檢測(cè)的數(shù)據(jù)流值交匯計(jì)算算法

4.4 實(shí)例解析

按照第4 節(jié)的數(shù)據(jù)流分析算法，對(duì)圖1 的NPD缺陷代碼實(shí)例進(jìn)行分析，得到圖6所示結(jié)果。

圖6 NPD實(shí)例數(shù)據(jù)流分析

其中，虛線指向的是各語(yǔ)句的輸出數(shù)據(jù)流值。從圖中可以得到OUT［6］的數(shù)據(jù)流值中變量num1的格值為ERROR，OUT［7］的數(shù)據(jù)流值中變量$stack1的格值為ERROR，OUT［8］的數(shù)據(jù)流值中變量$stack2 的格值為ERROR。這就表明圖1 所示的NPD 實(shí)例中，第12 行、14 行和15 行出現(xiàn)了NPD 錯(cuò)誤，這與2.2節(jié)的分析結(jié)果是完全一致的。

5 試驗(yàn)結(jié)果分析

以本文上述的NPD 缺陷檢測(cè)方法實(shí)現(xiàn)的檢測(cè)工具ASCA-Java進(jìn)行試驗(yàn)，對(duì)比目前業(yè)界主流的開(kāi)源和商業(yè)檢測(cè)工具SpotBugs、PMD 和Fortify，分析本文所提方法的有效性和實(shí)際性能表現(xiàn)。

5.1 試驗(yàn)環(huán)境及測(cè)試數(shù)據(jù)

試驗(yàn)環(huán)境：JDK 版本為1.8，操作系統(tǒng)為Mac OS 10.14.6，CPU為因特爾-酷睿i7-8559u四核八線程處理器，主頻2.7GHz，內(nèi)存32G，硬盤(pán)容量1T。

測(cè)試數(shù)據(jù)：本實(shí)驗(yàn)以美國(guó)國(guó)家安全機(jī)構(gòu)（NSA）旗下的軟件安全中心發(fā)布的Juliet test suite java 項(xiàng)目開(kāi)源測(cè)試集為檢測(cè)對(duì)象。

5.2 結(jié)果分析

通過(guò)表1 可以看出，本文提出的基于數(shù)據(jù)流分析的NPD 缺陷檢測(cè)法能夠有效地檢測(cè)出代碼中的NPD缺陷，與以抽象語(yǔ)法樹(shù)為分析基礎(chǔ)的檢測(cè)工具SpotBugs和PMD相比，本方法具有更高的準(zhǔn)確率和更低的誤報(bào)率，由于本方法暫不支持過(guò)程間的數(shù)據(jù)流分析，所以漏報(bào)率稍高于商業(yè)工具Fortify，但檢測(cè)效率要高于Fortify和其他兩款開(kāi)源檢測(cè)工具。

表1 NPD缺陷檢測(cè)試驗(yàn)結(jié)果對(duì)比

6 結(jié)語(yǔ)

本文提出了一種基于數(shù)據(jù)流分析的NPD 缺陷檢測(cè)方法，并通過(guò)所開(kāi)發(fā)的測(cè)試工具進(jìn)行對(duì)比試驗(yàn)證明了該方法的有效性。在準(zhǔn)確率和誤報(bào)率上，該方法要優(yōu)于Java開(kāi)源檢測(cè)工具SpotBugs和PMD，且在對(duì)比的三個(gè)檢測(cè)工具中耗時(shí)最短。本文的下一步工作重點(diǎn)是研究基于過(guò)程間的數(shù)據(jù)流分析來(lái)進(jìn)一步降低缺陷檢測(cè)的漏報(bào)率。