空指針異常的自動故障定位方法

姜淑娟，王興亞，張艷梅，李威，鞠小林，2，劉穎祺

（1. 中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116；2. 南通大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 南通 226019）

1 引言

多數(shù)高可信領(lǐng)域?qū)浖到y(tǒng)的穩(wěn)定性、健壯性和可靠性都有嚴(yán)格的要求。異常處理機制是Java、C++等高級程序設(shè)計語言提供的一種用來保障軟件可靠性的重要措施。程序異常一般可以分為2類：第一類是應(yīng)用異常，由程序員在應(yīng)用程序中顯式定義異常的拋出條件及異常類型，并在異常條件滿足時引發(fā)；第二類是運行時異常，指在程序運行時由于違反系統(tǒng)的約束條件而隱式地引發(fā)。例如，數(shù)組越界訪問異常、空指針引用異常等就屬于運行時異常。異常若不能被程序正確捕獲并處理，則可能導(dǎo)致程序崩潰。第一類異常是由于程序員自定義的，因而比較容易處理。目前，針對應(yīng)用異常的研究有很多，如對應(yīng)用異常進行分析，在程序設(shè)計、測試和維護等方面為開發(fā)人員提供有價值的信息[1～3]。然而第二類異常由于其引發(fā)條件是在程序的運行過程中隱式滿足，因此，在設(shè)計程序時很難發(fā)現(xiàn)程序的缺陷。由于運行時異常的引發(fā)不像應(yīng)用異常的引發(fā)那樣可以預(yù)測，為此開發(fā)人員很少為運行時異常設(shè)計處理程序。因而運行時異常一旦發(fā)生，程序很難通過自身的異常處理機制來處理，經(jīng)常需要人工的干預(yù)來檢查并定位引發(fā)異常的根源。運行時異常由于其引發(fā)條件的隱蔽性和不確定性，定位該類異常并排除程序相關(guān)缺陷存在一定的困難。針對運行時異常的研究是當(dāng)前故障定位研究熱點之一。以Java程序為例，由于Java編譯器并不對運行時異常進行檢測，即在一個方法中異常引發(fā)時只有2種處理方式：一是在方法內(nèi)指定與之匹配的處理程序；二是在方法的異常界面中指定該方法可能傳播出該類異常。因此，當(dāng)在程序的執(zhí)行過程中引發(fā)運行異常時，如果沒有匹配的異常處理程序來處理，將導(dǎo)致程序崩潰。

空指針異常是一類常見的運行時異常。例如Java中調(diào)用值為null對象的任何方法，都會引發(fā)空指針異常，而Java語言中的函數(shù)調(diào)用、別名引用等機制使在程序中查找和定位可能為空的指針對象非常困難。

僅使用靜態(tài)方法來檢查程序潛在故障的方法有很多，典型的如文獻[4～7]所述。這些方法大多要求用戶提供程序的注解且無法解決靜態(tài)分析結(jié)果不精確的問題。采用靜態(tài)分析與動態(tài)信息相結(jié)合的方法是解決靜態(tài)分析結(jié)果不精確問題的一個很有效的方法[8～10]，但已有這些方法用于收集動態(tài)信息需要花費很大的代價。如果首先通過空指針分析確定程序中所有的值可能為空的對象，便可以縮小查找空指針異常的錯誤值來源的范圍。Sinha等[11]提出一種利用堆棧信息從當(dāng)前異常引發(fā)位置后向遍歷程序，查找賦空值語句，進而檢查這些空值語句以確定空指針異常的引發(fā)原因的方法。這種方法需要遍歷整個程序，當(dāng)程序規(guī)模很大時，需耗費大量的時間。而且，他們的方法沒有考慮對象別名對分析結(jié)果的影響。別名的存在影響了錯誤定位結(jié)果的準(zhǔn)確度。別名分析可以幫助獲取更為準(zhǔn)確的引用型變量指向信息、提高靜態(tài)分析精度。

程序切片通過分析特定語句的依賴關(guān)系，抽取控制依賴與數(shù)據(jù)依賴的語句。通過計算空指針異常引發(fā)點的切片，可以排除與空指針異常引發(fā)無關(guān)的程序語句，因而程序切片具有簡化問題、縮小分析范圍的優(yōu)勢[12，13]。

基于上述分析，在對程序切片、程序的數(shù)據(jù)流和依賴性分析進行了較為深入研究的基礎(chǔ)上[14～16]，提出一種定位當(dāng)前運行時空指針異常引發(fā)根源的方法。該方法將靜態(tài)分析技術(shù)與實時堆棧信息相結(jié)合，針對異常引發(fā)點的程序切片開展空指針分析和別名分析以定位空指針異常。具體而言，方法分為2個階段：1) 在實時堆棧信息的指導(dǎo)下對程序進行約減，在此基礎(chǔ)上進行程序切片；2) 對切片后的程序進行空指針分析和別名分析。本方法所使用的動態(tài)信息是已有的實時堆棧信息，不需要額外的工作量。將該方法應(yīng)用到開源項目的空指針異常的定位中，實驗結(jié)果表明該方法可提高空指針異常的定位效率和精度。

2 問題描述

空指針異常的定位與檢測問題可以從理論上描述為對問題D={P，M，A}的求解。這里P是待檢測的程序，M是空指針異常的模式集合，A是定位空指針異常的算法。P可以描述為程序語句的集合；空指針異常模式用狀態(tài)機描述為M=＜N，T，C＞。狀態(tài)集合N={Nstart，Nexception，Nend，Nnot，Nmaybe}，表示空指針異常模式可能到達的狀態(tài)，狀態(tài)變遷T={＜ni，nj＞|ni，nj∈N}，狀態(tài)變遷條件為C：N×C→N。對象X引發(fā)空指針異常是指對象的狀態(tài)從初始狀態(tài)Nstart經(jīng)過一系列的狀態(tài)變遷，最終到達狀態(tài)Nexception。此外，空指針異常檢測算法描述為A={ρ(L，X)，Ψ}，其中，ρ計算程序P在執(zhí)行到L處時變量X的程序切片，Ψ為當(dāng)前實時堆棧中方法調(diào)用的摘要信息。

如果已知程序的空指針異常引發(fā)點并獲得異常引發(fā)時的實時堆棧信息，那么，依據(jù)檢測算法A可以檢測引發(fā)空指針異常的原因。但傳統(tǒng)的基于靜態(tài)分析的程序切片方法因為考慮程序所有可能的執(zhí)行情況，從而容易產(chǎn)生誤報，即

其中，～D(P，M，A)表示變量X的取值x不會引發(fā)異常模式M。FP(X)表示對變量X的誤報。

此外，由于別名機制存在，導(dǎo)致以上分析結(jié)果有漏報的可能，即

其中，D(P，M，A)表示變量X取值x會引發(fā)異常模式M。FN(X)表示對變量X的漏報。

以圖1中的一段Java程序為例說明上述問題。圖1中的程序包含4個簡單方法：method1， method2，method3， method4，一個構(gòu)造方法foo及一個main方法。運行時輸入“1”將會在語句 9引發(fā)一個空指針異常，程序?qū)K止，此時實時堆棧信息如下所示。

實時堆棧信息表明程序執(zhí)行觸發(fā)一個空指針異常。當(dāng)前堆棧中依次存在3個方法：method 1、method 4和main。main方法在語句25調(diào)用了method 4，method 4在語句19調(diào)用了method 1。由于method 1在執(zhí)行語句9時，對象obj1是一個null值，從而引發(fā)了一個空指針異常。

由此可見，當(dāng)引發(fā)運行異常時，Java實時環(huán)境在實時堆棧中保存了當(dāng)前程序執(zhí)行時方法之間的調(diào)用關(guān)系及執(zhí)行順序。這些信息包括引發(fā)運行時異常的語句所在的行號、該語句所在的方法名、以及程序從 main方法開始運行到該語句所調(diào)用并且沒有正常退出的方法。如果一個方法被調(diào)用過但已經(jīng)正常退出，則不會顯示在實時堆棧中。實時堆棧中的信息可以輔助開發(fā)人員定位并修復(fù)引發(fā)該異常的故障。而無需考慮那些在當(dāng)前運行中根本不可能被調(diào)用的方法，進而大大減少空指針分析的工作量，最終提高故障定位的效率和準(zhǔn)確率。

在運行時異常引發(fā)時，若程序沒有對應(yīng)的異常處理程序，則程序會立即終止，并且與該異常相關(guān)的動態(tài)信息會保存在實時堆棧中，利用程序調(diào)試接口，將實時堆棧信息輸出到外部文件，用作后續(xù)的切片程序輸入。

然而由于實時堆棧信息粒度較粗糙，因此需要結(jié)合程序的靜態(tài)分析得到的信息開展空指針異常定位。堆棧信息中僅僅包括本執(zhí)行中所涉及到的方法以及方法調(diào)用語句，并不包括方法內(nèi)部的控制流信息。另外，對于當(dāng)前執(zhí)行中被調(diào)用并且已經(jīng)正常返回的方法并不出現(xiàn)在實時堆棧中。因此，只利用實時堆棧信息查找空指針異常引發(fā)的原因，會漏掉那些在本次執(zhí)行過程中運行過但在實時堆棧中沒有顯示的方法，導(dǎo)致可能不能全面地理解程序執(zhí)行時復(fù)雜的控制流，也無法進行全面的別名分析。

例如，圖 1實例中的實時堆棧信息表明 main方法調(diào)用了method 4方法，而method 4方法調(diào)用了method 1方法，最終在method 1方法中(程序第9行)引發(fā)了空指針異常。在堆棧信息提示的3個方法中，只有method 1方法對obj1進行了賦值操作，而無法判斷賦值操作一定會引發(fā)空指針異常。因此，僅利用實時堆棧信息查找空指針異常的引發(fā)原因是不夠的，需要通過分析程序的執(zhí)行過程，獲取更多的運行時信息(如控制流、數(shù)據(jù)流等)來輔助空指針分析和別名分析，以降低故障定位的誤報和漏報。

圖1 一個實例程序foo

圖2顯示了實例程序foo的過程間的控制流。對于輸入“1”的執(zhí)行路徑如下：21a，28，29，30，31，32，21b，22，23，24a，14，15，16，24b，25a，17，18a，4，5，6，9。通過回溯分析當(dāng)前程序的執(zhí)行，可知引發(fā)語句9空指針異常的賦值空值語句在程序語句 30中(obj2=null)，在語句 6中將obj2的空值復(fù)制給obj1，最后，該空值obj1在語句9中被引用，從而觸發(fā)了空指針異常。然而當(dāng)空指針異常引發(fā)時，程序構(gòu)造方法(foo)中的語句 30不在實時堆棧中。

圖2 實例程序foo的控制流

此外，根據(jù)實時堆棧信息和程序結(jié)構(gòu)可以斷言：method 2根本不可能執(zhí)行。如果把那些根本不可能執(zhí)行的方法和語句刪除，則會大大降低程序分析的復(fù)雜度，減少進行故障定位的工作量。由于程序切片技術(shù)具有簡化問題、縮小范圍的優(yōu)點[12，13]，因此，可以先在實時堆棧信息指導(dǎo)下，結(jié)合程序的靜態(tài)結(jié)構(gòu)，首先，將當(dāng)前測試中肯定沒有執(zhí)行的方法排除，對剩下的程序利用實時堆棧進行切片，然后，再對切片后的程序進行靜態(tài)分析，進而找到引發(fā)該空指針異常的根源。

雖然切片后的程序較切片前有所減少，但是仍不足以精確定位到引發(fā)空指針異常的錯誤值來源的語句。例如，由圖2可知，如果在執(zhí)行語句9之前先執(zhí)行了語句8，則語句9就不會引發(fā)空指針異常。因此，在進行空指針異常故障定位時應(yīng)該從切片后的程序中刪除那些不產(chǎn)生空引用的語句。

此外，別名分析也有助于進一步提升故障定位的精度，降低漏報的可能。例如分析圖1中的實例程序，可以發(fā)現(xiàn)foo的構(gòu)造函數(shù)中語句30中的obj2和引發(fā)空指針異常的語句9中的obj1互為別名，方法method 2中語句12中的obj2和引發(fā)空指針異常的語句9中的obj1也互為別名。另外，在程序中還有一些引用變量，它們也可能是空值，但與引發(fā)空指針異常的變量并不互為別名，它們與當(dāng)前空指針異常中的空值也沒有直接關(guān)系，則應(yīng)該從切片集合中暫時去掉這些變量，如語句31中的obj3。

綜上分析，先在實時堆棧信息指導(dǎo)下進行程序切片，然后再進行空指針分析和別名分析，可以提高空指針異常故障定位的精度和效率。

3 本文方法框架

利用實時堆棧信息針對待分析源代碼進行約減，排除當(dāng)前不可能執(zhí)行代碼(方法)，進而在約減后的代碼上進行切片。從前面的分析可知，在程序切片的基礎(chǔ)上進行空指針分析和別名分析能夠有效降低空指針異常定位的誤報率和漏報率。本文方法定位的是在當(dāng)前執(zhí)行下產(chǎn)生空指針異常故障來源語句。具體而言，包含如下過程：1) 基于實時堆棧信息對程序中的方法進行分類，排除在當(dāng)前肯定未被執(zhí)行的方法，即在發(fā)生空指針異常的這次運行中，這些方法沒有被執(zhí)行；2) 在實時堆棧信息的指導(dǎo)下進行程序切片；3) 對切片后的程序進行空指針分析和別名分析；4) 對空指針分析結(jié)果和別名分析結(jié)果進行合并(集合交運算)，進而得出故障定位結(jié)果報告。方法框架如圖3所示。

圖3 方法的框架

步驟 1依據(jù)實時堆棧中的信息，通過靜態(tài)分析程序的控制流程圖，對程序中的方法按其在當(dāng)前執(zhí)行中是否被執(zhí)行進行分類。排除在當(dāng)前運行中肯定不執(zhí)行的方法。

步驟2在步驟1結(jié)果的基礎(chǔ)上，以空指針異常的引發(fā)點為切片準(zhǔn)則，結(jié)合實時堆棧信息進行后向靜態(tài)切片，進一步縮小定位空指針引用異常的可疑范圍。

步驟3在步驟2得到切片基礎(chǔ)上，分別進行空指針分析和別名分析。其中空指針分析目的是分析程序中值可能為空的引用型變量，即顯式存在的空指針賦值；別名分析目的是為了找出切片中所有引用型變量的指向信息，即空指針引發(fā)點依次關(guān)聯(lián)的所有別名?？罩羔樂治龊蛣e名分析后分別得到異常引發(fā)根源的語句集合。

步驟 4把空指針分析的結(jié)果與別名分析的結(jié)果進行集合交運算，進一步排除可能誤報的情形，從而得到更小的可疑語句集合，進而得到空指針異常的分析報告。

最終，基于上述框架，利用開源軟件soot提供的程序靜態(tài)分析接口，設(shè)計并實現(xiàn)一個用于空指針異常分析的故障定位工具。

4 定位空指針異常

4.1 基于堆棧信息的程序約減

一般情況下，程序執(zhí)行發(fā)生異常，一定是程序執(zhí)行過的語句當(dāng)中存在錯誤，而那些未被執(zhí)行的語句則不會導(dǎo)致本次執(zhí)行失敗。因此，可以考慮排除程序中未被執(zhí)行的語句。在空指針異常故障定位系統(tǒng)中，排除那些在當(dāng)前運行中肯定不被執(zhí)行的方法。具體方法如下。

對程序中的方法按其在當(dāng)前運行時是否被執(zhí)行過進行分類。可以分為：1) 肯定被執(zhí)行的方法；2) 可能被執(zhí)行的方法；3) 肯定不被執(zhí)行的方法。

考慮現(xiàn)代程序語言的基本結(jié)構(gòu)只有3種，順序結(jié)構(gòu)，選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。由3種基本結(jié)構(gòu)構(gòu)成的程序中，方法調(diào)用情況對應(yīng)可以分為3種，如圖4所示。圖4中方法FucE()中語句Refx(陰影部分)，表示對象x的引用，若執(zhí)行到此處(陰影部分)時x為空，則必然引發(fā)空指針異常。分析過程為：1) 對于圖4(a)，若語句Refx引發(fā)空指針異常，則在實時堆棧中保存的方法有funE和main。由于funA位于程序主干上，與發(fā)生異常的 funE是順序結(jié)構(gòu)，是funE的后向必經(jīng)節(jié)點，可知funA必定被執(zhí)行過，因此 funA歸為肯定執(zhí)行的方法類別。另外，funB和funC分別位于程序的2個分支上，在沒有實時跟蹤程序執(zhí)行的情況下，無法斷定它們是否一定被執(zhí)行，因此，可以把funB和funC歸為可能執(zhí)行的方法類別；2) 對于圖4(b)，若語句Refx引發(fā)空指針異常，則在實時堆棧中保存的方法有 funE和main。由于funA與funE分別處于2個程序控制流分支，因此 funA是肯定不執(zhí)行的方法；3) 對于圖4(c)，若語句Refx引發(fā)空指針異常，在實時堆棧中保存的方法有funE和main。由于funE肯定被執(zhí)行了，而funA處于funE后向必經(jīng)節(jié)點，因此funA是肯定被執(zhí)行的方法。但是如果在 funE第一次執(zhí)行時就引發(fā)了空指針異常，則 funB不會被執(zhí)行；如果funE在循環(huán)發(fā)生后引發(fā)空指針異常，則funB一定被執(zhí)行。因此，圖4(c)中的funA歸類為肯定被執(zhí)行的方法，funB歸類為可能被執(zhí)行的方法。

例如，圖2中的實例程序的控制流圖，當(dāng)程序在語句9異常終止時，main函數(shù)在節(jié)點25a處終止。由控制流圖可知，節(jié)點 21、22和 23都是從 main的入口到達節(jié)點25a的必經(jīng)節(jié)點，并且節(jié)點21和23又各自分別調(diào)用了類foo的構(gòu)造方法和method 3方法，因此，可以確定它們都被調(diào)用過并且已正常返回。對于節(jié)點24，由于實時堆棧信息并沒有包含方法內(nèi)控制流信息，因此，無法判斷從節(jié)點 23到達節(jié)點25是否經(jīng)過了節(jié)點24，則方法method 3是可能執(zhí)行的方法。

圖4 3種基本結(jié)構(gòu)對應(yīng)的方法調(diào)用組合

再如，圖2的main方法中語句26調(diào)用了方法method 2，而main方法中語句26在當(dāng)前執(zhí)行過程中是不可能執(zhí)行的語句，因此，可以斷定方法method 2在當(dāng)前執(zhí)行過程中沒有被調(diào)用過，則其對obj2的修改在當(dāng)前執(zhí)行中也沒有任何意義。

綜上所述，當(dāng)空指針異常引發(fā)時，可以根據(jù)實時堆棧信息，結(jié)合靜態(tài)分析程序的結(jié)構(gòu)，把程序中的所有方法按圖4中的3種模式進行分類。在設(shè)計的系統(tǒng)中，通過前向遍歷程序控制流程圖完成對方法的分類。

4.2 基于實時堆棧的靜態(tài)切片算法

由上一節(jié)的分析可知，程序中存在一些沒有執(zhí)行過的方法和語句，并且這些方法和語句對本次執(zhí)行不產(chǎn)生任何影響，則切片時可以不對其進行跟蹤，由此也就不需要分析其依賴關(guān)系。

考慮圖1中的實例程序，肯定被執(zhí)行的方法有main、method 4和method 1，肯定沒有執(zhí)行的方法有method 2，可能被執(zhí)行的方法有method 3。因此，在構(gòu)建系統(tǒng)依賴圖時可以忽略掉方法method 2，約減之后的系統(tǒng)依賴圖較約減之前有明顯簡化。

本文改進了靜態(tài)切片算法，其切片準(zhǔn)則為＜P，V， CS＞，其中CS為一個實時堆棧信息，可以是空指針異常引發(fā)時的調(diào)用序列，或人工添加的一條調(diào)用序列(前提是該調(diào)用序列必須是可行的)。改進的靜態(tài)程序切片算法的主要思想是：在約減的系統(tǒng)依賴圖的基礎(chǔ)上進行反向遍歷，查找切片準(zhǔn)則中的數(shù)據(jù)依賴和控制依賴語句，同時不去分析當(dāng)前執(zhí)行中一定不會執(zhí)行的那些方法。具體如算法1所示。

算法1SliceUnderStaticTrace

算法1是一個典型的2步遍歷的切片算法[13]。從切片準(zhǔn)則語句開始，第一步為不沿參數(shù)輸出邊對系統(tǒng)依賴圖(SDG)進行反向遍歷，第二步為不沿參數(shù)輸入邊和調(diào)用邊對 SDG進行反向遍歷。遍歷的節(jié)點構(gòu)成的集合即為切片。算法 1中的子函數(shù)markreachingvertice的第7)行和第8)行針對待分析程序的方法執(zhí)行情況進行處理，首先對跟蹤的每條邊w→v進行判斷：如果起點w所在的方法M被標(biāo)記為“肯定不被執(zhí)行”的時候，切片算法就不需要跟隨這條邊進入一個不可能執(zhí)行的方法中。

4.3 空指針分析

空指針分析是分析并找出代碼中可能為空的引用型變量，在空指針異常故障定位中發(fā)揮著十分關(guān)鍵的作用。在Java中，值為null的對象調(diào)用任何方法都會引發(fā)空指針異常，空指針引用在程序中較為隱蔽，因而空指針異常是Java中最難查找和調(diào)試的一種異常。如果能找出程序中所有的值可能為空的對象，則會大大縮小查找空指針異常的錯誤值來源的范圍。利用開源軟件soot[17]中提供的編程接口實現(xiàn)的空指針分析功能。具體而言，在程序切片后的程序上，找出代碼中可能為空值的引用型變量并將其標(biāo)出，以便于找到引發(fā)空指針異常的錯誤值來源。實際上，對于一個包含引用型變量v的語句，可利用soot提供的編程接口，實現(xiàn)對變量v取值的判斷，即v是否可能為空。

算法2給出了基于soot實現(xiàn)針對對象的空指針分析過程。算法的基本思想是：首先，根據(jù)前面的切片結(jié)果獲取待分析的代碼；然后，分析這些代碼中的引用型變量的取值情況；最后，根據(jù)分析結(jié)果生成xml文件，結(jié)果中標(biāo)簽＜alwaysNullList＞內(nèi)的行號表示對應(yīng)的代碼行中存在空變量；標(biāo)簽＜NullUnknown＞內(nèi)的行號表示對應(yīng)的代碼行中存在可能為空的變量。具體分析過程如算法2所示。

算法2doNullnessAnalysis

算法2的關(guān)鍵過程為第5行至第12行。先根據(jù)切片結(jié)果獲取待分析的所有引用型變量，然后結(jié)合數(shù)據(jù)流方程和它們所在的代碼行分析這些引用變量是否為空。算法中方法 is AlwaysNull和 is UnknownNull是采用 soot的空指針分析原理實現(xiàn)的。最后的分析結(jié)果以xml格式保存到外部存儲器。

4.4 別名分析

別名分析指的是找出引用型變量的指向信息，根據(jù)指向信息判斷2個引用型變量是否互為別名。為了進一步提高空指針異常故障定位的精度并減少誤報，本文方法在完成切片的基礎(chǔ)上，利用開源軟件soot提供的編程接口，針對引發(fā)空指針異常的對象進行了別名分析，充分考慮了別名對引用型變量指向信息的影響，便于能進一步鎖定引發(fā)空指針異常的錯誤語句，從而提高空指針異常故障定位的精度并降低誤報率。具體而言，別名分析算法利用soot編程接口，4.2節(jié)中切片分析結(jié)果，依次抽取需要檢測代碼行，然后，檢測這些代碼中的引用型變量和引發(fā)空指針異常的變量是否存在別名關(guān)系。提取與指定代碼行變量存在別名關(guān)系的變量所在行，并按照空指針分析結(jié)果的xml文件格式保存別名分析的結(jié)果，具體過程如算法3所示。

算法3doAliasAnalysis

算法 3展現(xiàn)了別名分析算法(doAliasAnalysis)的詳細(xì)流程。首先，根據(jù)類名和行號，獲取可能引發(fā)空指針異常的所有變量，分析這些變量的指針信息(1)～5)行)；其次，根據(jù)切片分析過程的結(jié)果獲取有待檢測的引用型變量，依次分析這些變量的指針信息(6)～10)行)；第三，根據(jù)各個變量的指針信息，判斷變量間的別名關(guān)系(11)～16)行)；最后，將生成別名分析結(jié)果以xml文件(17)行)格式輸出到外部存儲器。

5 實證研究

5.1 實驗設(shè)計

為了驗證提出的空指針異常故障定位方法的有效性，依據(jù)所提出的方法設(shè)計并實現(xiàn)了一個原型工具。并在一組開源程序上開展空指針異常故障定位實驗。實驗對象如表1所示。實驗選取開源軟件ant的7個不同版本，源程序代碼行數(shù)為77 980行至179 889行。以空指針異常作為研究目標(biāo)，從相應(yīng)的缺陷數(shù)據(jù)庫中獲取了各自的空指針異常，包括BugID、空指針異常引發(fā)的文件及所在異常語句行號。實驗?zāi)康氖球炞C所提方法能否有效定位這些異常，是否存在誤報和漏報的情形。

表1 實驗對象介紹

5.2 實驗結(jié)果及分析

為了驗證方法的有效性，依據(jù)第4節(jié)所述方法，首先，對程序進行約簡，排除不可能執(zhí)行的方法，接著，在實時堆棧信息基礎(chǔ)上，計算切片準(zhǔn)則，并采取一種后向切片方法計算程序切片；然后基于程序切片分別進行空指針分析和別名分析，并將兩者的計算得到的可疑語句集合進行交運算。最終定位空指針異常引發(fā)的根源。

具體而言，基于表1中的程序分別設(shè)計了2組實驗：第一組實驗中不利用實時堆棧信息，直接針對所有源代碼進行切片，然后再進行空指針分析和別名分析；第二組實驗在實時堆棧信息指導(dǎo)下進行故障定位，即先利用實施堆棧信息對源程序進行約簡(通過排除不可能執(zhí)行的方法縮減懷疑的范圍)，進而在約簡后的程序上切片，然后再進行空指針分析和別名分析。以上2組實驗的最終結(jié)果分別如表2和表3所示。

表2 無實時堆棧信息指導(dǎo)的定位結(jié)果

由表2可見，基于切片后的空指針分析和別名分析可以有效地縮小可疑語句范圍。例如，定位編號5 652的空指針異常，通過切片計算把可疑范圍從77 980行縮減到1 394行，進而對切片進行空指針分析和別名分析，分別將可疑范圍縮小到873行和 53行。最后對空指針分析和別名分析的結(jié)果進行集合交運算，得到可疑語句數(shù)為44行。

表3 基于實時堆棧信息指導(dǎo)下定位結(jié)果

由表3可見，在實時堆棧信息指導(dǎo)下，先對程序進行縮減，然后再進行程序切片同樣可以大幅度縮小故障定位的范圍。例如，編號為32 200的空指針異常，先在實時堆棧信息指導(dǎo)下，用4.1節(jié)闡述的方法，對152 483行源代碼進行約簡，并進行切片，得到16 372行，這比表2中不進行源代碼縮減情況下的切片(17 574行)要少很多行，這意味著，在縮減后的程序上進行程序切片可以減少切片計算的工作量，并得到更小的可疑語句集合。

針對表2和表3中的數(shù)據(jù)，采用Wilcoxon配對檢驗，結(jié)果表明，在實時堆棧信息指導(dǎo)下對程序約簡后的切片規(guī)模比直接在源程序上所得切片規(guī)模有比較顯著的縮小(p-value= 0.064 1)，且空指針分析的規(guī)模也有較顯著降低(p-value= 0.064 1)，但是在表 3中的別名分析結(jié)果較表 2略有減少(p-value= 0.034 98)，而最終故障定位結(jié)果則差別不大(p-value= 0.448 9)。

綜合表2和表3的分析，雖然最終定位程序空指針異常的結(jié)果2種方法比較接近，但是，由于提出的程序縮減方法可以顯著減少(置信度水平為93.6%)計算切片分析程序規(guī)模，因此，可以減少切片計算時分析程序、計算程序依賴關(guān)系的時間。總地來看，本文方法增加了程序縮減所需時間，減少了計算程序切片所需的時間。

由4.1節(jié)分析可知，程序中所有的方法均可通過程序一次失敗執(zhí)行時產(chǎn)生的堆棧信息分為肯定被執(zhí)行的方法、可能被執(zhí)行的方法和肯定不被執(zhí)行的方法3類。在隨后的切片過程中，只對程序中上述前2類方法進行依賴關(guān)系分析，并在此基礎(chǔ)上進行程序切片，以用于后續(xù)的錯誤定位。因此，可以獲得當(dāng)前執(zhí)行過程中所有與狀態(tài)異常語句有依賴關(guān)系的語句，并以此進行錯誤定位。然而，如果程序執(zhí)行失敗是由程序未執(zhí)行某些語句引發(fā)的，由于本文方法缺乏針對程序中未執(zhí)行方法的分析，構(gòu)造的依賴關(guān)系并不完備，因而存在漏報的可能。除此之外，通過手工分析可疑語句集合中的語句，對照堆棧信息，發(fā)現(xiàn)引起當(dāng)前空指針異常的語句均在可疑語句集合之中，并且從錯誤賦值語句開始到異常引發(fā)點的路徑都包含在程序切片之中。因此，本文方法所得結(jié)果是正確的。

6 相關(guān)工作

目前針對程序故障定位的研究，很多學(xué)者提出了不同的解決方法。常用的方法主要有純靜態(tài)分析方法和動靜結(jié)合分析的方法。

使用靜態(tài)的故障定位方法檢查潛在故障的方法有：Hovemeyer等[4]使用前向過程間數(shù)據(jù)流分析和注解發(fā)現(xiàn)與空指針引用相關(guān)的 BUG。Evans[5]生成了LCLint來結(jié)合注解檢查在C程序中的錯誤，如內(nèi)存泄漏和別名。ESC/Java[6]是一個編譯時間的程序檢查器，它檢查在注解語言中的設(shè)計描述與實際代碼之間的不一致和潛在的實時錯誤。與本文技術(shù)不同的是，上面這些技術(shù)要求用戶提供程序的注解，它們所提供的故障定位的質(zhì)量依賴于注解。

Bush[7]通過檢查C程序中一個內(nèi)存錯誤的外部類來進行準(zhǔn)確的過程間分析，包括空引用。這種技術(shù)的特點是采用過程自底向上的分析方法計算摘要，在每一個過程內(nèi)部進行前向路徑敏感分析來剪除那些不可達路徑。然而，這種方法是一個純靜態(tài)的，也同樣有靜態(tài)方法所存在的公共問題。Nanda和 Sinha[18]提出了一種上下文敏感和路徑敏感的過程間分析方法，用于識別潛在的空指針引用。Xie和Engler[19]提出了一種用于查找系統(tǒng)錯誤（如空指針引用未釋放鎖）的方法。然而，這些方法是純靜態(tài)的，也同樣有靜態(tài)方法所存在的公共問題。與這些方法不同的是，將動態(tài)生成的信息（實時堆棧信息）與靜態(tài)分析相結(jié)合，可以避免純靜態(tài)方法的問題。此外，本文技術(shù)在故障定位之前先進行實時堆棧信息指導(dǎo)下的程序切片，減少了搜索空間。

Rountev等[8]討論了靜態(tài)分析不精確，并提出用于評估這種不準(zhǔn)確的方法。解決靜態(tài)分析不準(zhǔn)確問題的一個公共方法是結(jié)合靜態(tài)分析和動態(tài)分析。

Hangal和Lam開發(fā)了一個工具DIDUCE[9]，嘗試通過動態(tài)程序常量檢測去推測BUG，收集動態(tài)常量是一個非常昂貴的分析，不適用于大型程序。相反，本文方法使用現(xiàn)成的動態(tài)信息(實時堆棧信息)查找故障。

Tom 等[10]提出了一種結(jié)合靜態(tài)分析和動態(tài)分析的方法來發(fā)現(xiàn)Java程序中實時錯誤。該方法首先進行前向過程間符號執(zhí)行來發(fā)現(xiàn)可能揭露 BUG的約束，然后試圖生成測試用例來觸發(fā)該BUG。然而，本文方法是后向分析，從發(fā)現(xiàn)BUG的一條語句（異常引發(fā)點）開始，使用有效的實時堆棧信息來指導(dǎo)后向的分析。

Baah等[20]提出了一種通過建立概率程序依賴圖來進行錯誤定位的方法。該方法首先通過靜態(tài)分析方法生成程序依賴圖，然后通過測試用例的執(zhí)行信息中的數(shù)據(jù)來評估節(jié)點間的統(tǒng)計依賴關(guān)系，從而得到概率程序依賴圖，最終將其運用于錯誤定位中。與本文方法的不同之處在于：1)該方法的靜態(tài)分析方面主要體現(xiàn)在程序依賴圖的建立；2)在動態(tài)分析方面，上述方法利用的是測試用例的執(zhí)行信息，需要收集程序的動態(tài)運行信息，而本文方法不需要收集這些信息，可以在實時堆棧中直接獲得。

Zhang等[21]提出了一種靜態(tài)分析與后向動態(tài)切片相結(jié)合的錯誤定位方法。該方法通過計算可執(zhí)行語句的信賴度值來確定語句產(chǎn)生正確值的概率，其中，信賴度值越大表示語句產(chǎn)生的正確值的概率越高，然后通過剪去信賴度值中較大的值為1的語句來縮減動態(tài)切片的大小。2種方法的主要區(qū)別在于縮減搜索范圍的方法不同，本文是通過實時堆棧信息來縮減搜索范圍，兩者有各自的適用之處。

Sinha等[11]提出了一種方法來定位那些在Java程序中由于不正確賦值導(dǎo)致實時異常的故障。該方法基于實時堆棧信息，從當(dāng)前異常引發(fā)點開始，進行后向靜態(tài)數(shù)據(jù)流分析，依次查找對可疑對象賦空值的語句。而本文方法優(yōu)勢有2點。1) 利用堆棧信息，結(jié)合對程序結(jié)構(gòu)的分析，首先排除當(dāng)前執(zhí)行中肯定不會執(zhí)行的方法，對剩下的程序進行切片，并在切片基礎(chǔ)上進行空指針分析和別名分析。對程序的刪減不會引起漏報，因為異常引發(fā)“原因”語句肯定包含在本次執(zhí)行語句當(dāng)中。而且這種刪減使程序切片的速度得以提升；2)在切片基礎(chǔ)上采用別名分析，有助于提高故障定位的精度，避免誤報和漏報。不足之處在于，Sinha的方法還能找到可能在下次運行中引發(fā)當(dāng)前異常的那些賦空值語句。而本文方法只關(guān)注與引發(fā)空指針異常的本次執(zhí)行的那些賦空值語句。然而，本文方法縮減和別名分析工作可以較顯著地提高故障定位的效率。

程序切片是在軟件調(diào)試中廣泛應(yīng)用的技術(shù)。Gupta等[22]通過在靜態(tài)切片中引入動態(tài)信息， 提出了一種混合切片方法。該方法利用斷點、函數(shù)調(diào)用圖等程序調(diào)試過程中的動態(tài)信息，提高了程序切片的質(zhì)量和精度。該方法與本文方法相同之處是兩者都利用了現(xiàn)成的動態(tài)信息，文獻[22]中動態(tài)信息是程序調(diào)試過程中產(chǎn)生的，而本文是空指針異常引發(fā)時產(chǎn)生的。2種方法的不同之處是在程序切片之后，又進行了空指針分析和別名分析來完成故障定位。

目前，許多學(xué)者提出了一些基于測試的錯誤定位方法，典型的包括下列幾種方法。

Renieris等[23]提出了一種基于相似程序光譜的最近鄰執(zhí)行軌跡(NNQ）方法。在NNQ方法中，對于一個失敗的執(zhí)行和許多成功的執(zhí)行，根據(jù)距離準(zhǔn)則從成功執(zhí)行中選擇一條程序光譜和失敗執(zhí)行最近的成功執(zhí)行，通過比較兩者光譜的不同從而分離軟件錯誤。Jones等[24，25]提出了一種Tarantula方法，該方法通過計算程序?qū)嶓w的懷疑度值，并將其進行排序從而對源代碼進行審查，直至找到軟件錯誤的所在。Santelices等[26]提出了一種基于多重覆蓋的錯誤定位的策略，該方法指出覆蓋信息類型的選取會對錯誤定位方法的有效性產(chǎn)生很大的影響，綜合使用多種覆蓋類型的信息，能夠提高錯誤定位方法的有效性，該方法僅組合計算了語句的懷疑度值，在本質(zhì)上與 Tarantula方法一致。徐寶文等[27]提出了一種基于組合測試的故障定位方法。該方法根據(jù)組合測試的結(jié)果，補充一些附加測試用例重新進行測試，然后對結(jié)果進行分析，從而可以迅速地鎖定很小范圍導(dǎo)致故障的原因。

以上方法皆是根據(jù)測試時程序執(zhí)行特征的統(tǒng)計信息來進行錯誤定位的，需要收集程序的動態(tài)執(zhí)行信息，而本文方法不需要收集這些執(zhí)行信息，而是直接使用現(xiàn)成的實時堆棧信息，因此，與基于測試的錯誤定位方法不同的是，本文方法在收集動態(tài)信息方面不會花費較多的資源和精力，具有一定的優(yōu)越性。

7 結(jié)束語

針對 Java程序中空指針異常經(jīng)常發(fā)生并且難以定位其引發(fā)的根源的問題，提出了一種動態(tài)信息與靜態(tài)分析相結(jié)合的故障自動定位的新方法。該方法首先在實時堆棧信息指導(dǎo)下從異常引發(fā)點開始進行后向程序切片，減少了搜索空間；然后，對切片后的程序進行空指針分析和別名分析；最后，用可視化工具顯示分析結(jié)果和相關(guān)源代碼。該方法既能在一定程序上克服靜態(tài)分析結(jié)果不精確的不足，又能彌補實時堆棧信息過于粗糙無法單獨應(yīng)用的不足，而且也不需要花費額外的代價來收集動態(tài)信息。

將該方法應(yīng)用到開源項目中的空指針異常的定位，實驗結(jié)果表明對空指針異常故障定位方面有較好的效果。需要指出的是本文方法是針對程序的一次執(zhí)行過程中的實時堆棧信息分析，難以獲取全面的依賴關(guān)系，所以存在漏報的可能。因此，下一步工作是進一步研究如何利用靜態(tài)分析技術(shù)獲取程序的其他依賴信息，并開展形式化分析和理論證明，以拓展本文方法的普適性。同時，將本文方法拓展到其他類型的運行時異常的故障定位中，比如數(shù)組越界異常等；提出有效的方法克服實時堆棧信息在故障定位方面的不足，提高故障定位的準(zhǔn)確率；本文方法還需要進行大量的實驗進行驗證；進一步完善本文的原型工具，為后續(xù)的故障定位提供有價值的信息。

[1] SINHA S， HARROLD M J. Analysis and testing of programs with exception-handling constructs[J]. IEEE Transactions on Software Engineering， 2000， 26(9)：849-871.

[2] JIANG S J， XU B W， SHI L. An approach to analysis exception propagation[A]. Proceedings of the 8th IASTED International Conference on Software Engineering and Applications[C]. Anaheim， USA，2004.300-305.

[3] ROBILLARD M P， MURPHY G C. Static analysis to support the evolution of exception structure in object-oriented systems[J]. ACM Transactions on Software Engineering and Methodology， 2003，12(2)：191-221.

[4] HOVEMEYER D， SPACCO J， PUGH W. Evaluating and tuning a static analysis to find null pointer bugs[A]. Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering[C]. Lisbon， Portugal， 2005.13-19.

[5] EVANS D. Static detection of dynamic memory errors[A]. Proceedings of the ACM SIGPLAN Conference on Programming Languages，Design， and Implementation[C]. Pennsylvania， USA， 1996.44-53.

[6] FLANAGAN C， LEINO K R M， LILLIBRIDGE M，et al. Extended static checking for Java[A]. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation[C].Berlin， Germany， 2002.234-245.

[7] BUSH W R， PINCUS J D， SIELAFF D J. A static analyzer for finding dynamic programming errors[J]. Software： Practice and Experience，2000， 30(7)：775-802.

[8] ROUNTEV A， KAGAN S， GIBAS M. Evaluating the imprecision of static analysis[A]. Proceedings of the 5th ACM SIGPLAN- SIGSOFT Workshop on Program Analysis for Software Tools and Engineering[C]. Washington， DC， USA， 2004.14-16.

[9] HANGAL S， LAM M S. Tracking down software bugs using automatic anomaly detection[A]. Proceedings of the International Conference on Software Engineering[C]. Orlando， Florida， USA， 2002. 291-301.

[10] TOMB A， BRAT G P， VISSER W. Variably interprocedural program analysis for runtime error detection[A]. Proceedings of the International Symposium on Software Testing and Analysis[C]. London，England， United Kingdom， 2007.97-107.

[11] SINHA S， SHAH H， GORG C，et al. Fault localization and repair for Java runtime exceptions[A]. Proceedings of the International Symposium on Software Testing and Analysis[C]. Chicago， Illinois， USA，2009.153-164.

[12] WEISER M. Program slicing[J]. IEEE Transactions on Software Engineering， 1984， 10(4)：352-357.

[13] KOREL B， LASKI J. Dynamic program slicing[J]. Information Processing Letters， 1988， 29(3)：155-163.

[14] 姜淑娟， 徐寶文， 史亮. 一種基于異常傳播分析的數(shù)據(jù)流分析方法[J]. 軟件學(xué)報， 2007，18(1)：74-84.JIANG S J， XU B W， SHI L. An approach of data-flow analysis based on exception propagation analysis[J]. Journal of Software， 2007，18(1)：74-84.

[15] 姜淑娟， 徐寶文， 史亮等. 一種基于異常傳播分析的依賴性分析方法[J]. 軟件學(xué)報， 2007， 18(4)：832-841.JIANG S J， XU B W， SHI L，et al. An approach to analyzing dependence based on exception propagation analysis[J]. Journal of Software，2007， 18(4)：832-841.

[16] JIANG S J， ZHANG H C， WANG Q T，et al. A debugging approach for Java runtime exception based on program slicing and stack traces[A]. Proceedings of the 10th International Conference on Quality Software[C]. Zhangjiajie， China， 2010.393-398.

[17] VALLéE-RAI R， LAM P， VERBRUGGE C，et al. Soot(postersession)：a Java byte code optimization and annotation framework[A]. Proceedings of the 15th ACM SIGPLAN Conference on Object-oriented Programming， Systems， Languages， and Applications[C]. Minneapolis，Minnesota， USA， 2000.113-114.

[18] NANDA M G， SINHA S. Accurate inter-procedural null-dereference analysis for Java[A]. Proceedings of the 31st International Conference on Software Engineering[C]. Vancouver， Canada， 2009.133-143.

[19] XIE Y， ENGLER D R. Using redundancies to find errors[A]. Proceedings of the 10th ACM SIGSOFT Symposium on Foundations of Software Engineering[C]. Charleston， SC， USA， 2002.51-60.

[20] BAAH G K， PODGURSKI A， HARROLD M J. The probabilistic program dependence graph and its application to fault diagnosis[J].IEEE Transactions on Software Engineering， 2010， 36(4)： 528-545.

[21] ZHANG X Y， GUPTA N， GUPTA R. Pruning dynamic slices with confidence[A]. Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Impl- ementation[C]. Ottawa，Ontario， Canada， 2006.169-180.

[22] GUPTA R， SOFFA M L. Hybrid slicing： an approach for refining static slices using dynamic information[A]. Proceedings of the 3rd ACM SIGSOFT Symposium on Foundations of Software Engineering[C].Washington， DC， USA， 1995.29-40.

[23] RENIERIS M， REISS S P. Fault localization with nearest neighbor queries[A]. Proceedings of the 18th IEEE/ACM International Conference on Automated Software Engineering[C]. Montreal， Canada， 2003.30-39.

[24] JONES J A， HARROLD M J. Empirical evaluation of the Tarantula automatic fault localization technique[A]. Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering[C]. Long Beach， CA， USA， 2005.273-282.

[25] JONES J A， HARROLD M J， STASKO J. Visualization of test information to assist fault localization[A]. Proceedings of the 24th International Conference on Software Engineering[C]. Orlando， Florida， 2002.467-477.

[26] SANTELICES R， JONES J A， YU Y B，et al. Lightweight fault-localization using multiple coverage types[A]. Proceedings of the 31st International Conference on Software Engineering[C]. Vancouver，Canada， 2009.56-66.

[27] 徐寶文， 聶長海， 史亮等. 一種基于組合測試的軟件故障調(diào)試方法[J]. 計算機學(xué)報， 2006， 29(1)： 132-138.XU B W， NIE C H， SHI L，et al. A software failure debugging method based on combinatorial design approach for testing[J]. Chinese Journal of Computers， 2006， 29(1)： 132-138.