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

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

（1. 中國礦業大學 計算機科學與技術學院，江蘇 徐州 221116；2. 南通大學 計算機科學與技術學院，江蘇 南通 226019）

1 引言

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

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

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

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

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

2 問題描述

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

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

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

此外，由于別名機制存在，導致以上分析結果有漏報的可能，即

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

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

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

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

在運行時異常引發時，若程序沒有對應的異常處理程序，則程序會立即終止，并且與該異常相關的動態信息會保存在實時堆棧中，利用程序調試接口，將實時堆棧信息輸出到外部文件，用作后續的切片程序輸入。

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

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

圖1 一個實例程序foo

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

圖2 實例程序foo的控制流

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

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

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

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

3 本文方法框架

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

圖3 方法的框架

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

步驟2在步驟1結果的基礎上，以空指針異常的引發點為切片準則，結合實時堆棧信息進行后向靜態切片，進一步縮小定位空指針引用異常的可疑范圍。

步驟3在步驟2得到切片基礎上，分別進行空指針分析和別名分析。其中空指針分析目的是分析程序中值可能為空的引用型變量，即顯式存在的空指針賦值；別名分析目的是為了找出切片中所有引用型變量的指向信息，即空指針引發點依次關聯的所有別名。空指針分析和別名分析后分別得到異常引發根源的語句集合。

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

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

4 定位空指針異常

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

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

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

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

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

圖4 3種基本結構對應的方法調用組合

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

綜上所述，當空指針異常引發時，可以根據實時堆棧信息，結合靜態分析程序的結構，把程序中的所有方法按圖4中的3種模式進行分類。在設計的系統中，通過前向遍歷程序控制流程圖完成對方法的分類。

4.2 基于實時堆棧的靜態切片算法

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

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

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

算法1SliceUnderStaticTrace

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

4.3 空指針分析

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

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

算法2doNullnessAnalysis

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

4.4 別名分析

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

算法3doAliasAnalysis

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

5 實證研究

5.1 實驗設計

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

表1 實驗對象介紹

5.2 實驗結果及分析

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

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

表2 無實時堆棧信息指導的定位結果

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

表3 基于實時堆棧信息指導下定位結果

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

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

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

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

6 相關工作

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結束語

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

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

[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] 姜淑娟， 徐寶文， 史亮. 一種基于異常傳播分析的數據流分析方法[J]. 軟件學報， 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]. 軟件學報， 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] 徐寶文， 聶長海， 史亮等. 一種基于組合測試的軟件故障調試方法[J]. 計算機學報， 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.