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

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

1 引言

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

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

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

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

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

2 問(wèn)題描述

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

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

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

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

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

以圖1中的一段Java程序?yàn)槔f(shuō)明上述問(wèn)題。圖1中的程序包含4個(gè)簡(jiǎn)單方法：method1， method2，method3， method4，一個(gè)構(gòu)造方法foo及一個(gè)main方法。運(yùn)行時(shí)輸入“1”將會(huì)在語(yǔ)句 9引發(fā)一個(gè)空指針異常，程序?qū)?huì)終止，此時(shí)實(shí)時(shí)堆棧信息如下所示。

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

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

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

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

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

圖1 一個(gè)實(shí)例程序foo

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

圖2 實(shí)例程序foo的控制流

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

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

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

綜上分析，先在實(shí)時(shí)堆棧信息指導(dǎo)下進(jìn)行程序切片，然后再進(jìn)行空指針?lè)治龊蛣e名分析，可以提高空指針異常故障定位的精度和效率。

3 本文方法框架

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

圖3 方法的框架

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

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

步驟3在步驟2得到切片基礎(chǔ)上，分別進(jìn)行空指針?lè)治龊蛣e名分析。其中空指針?lè)治瞿康氖欠治龀绦蛑兄悼赡転榭盏囊眯妥兞浚达@式存在的空指針賦值；別名分析目的是為了找出切片中所有引用型變量的指向信息，即空指針引發(fā)點(diǎn)依次關(guān)聯(lián)的所有別名?？罩羔?lè)治龊蛣e名分析后分別得到異常引發(fā)根源的語(yǔ)句集合。

步驟 4把空指針?lè)治龅慕Y(jié)果與別名分析的結(jié)果進(jìn)行集合交運(yùn)算，進(jìn)一步排除可能誤報(bào)的情形，從而得到更小的可疑語(yǔ)句集合，進(jìn)而得到空指針異常的分析報(bào)告。

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

4 定位空指針異常

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

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

對(duì)程序中的方法按其在當(dāng)前運(yùn)行時(shí)是否被執(zhí)行過(guò)進(jìn)行分類(lèi)?？梢苑譃椋?) 肯定被執(zhí)行的方法；2) 可能被執(zhí)行的方法；3) 肯定不被執(zhí)行的方法。

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

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

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

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

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

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

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

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

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

算法1SliceUnderStaticTrace

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

4.3 空指針?lè)治?/h3>

空指針?lè)治鍪欠治霾⒄页龃a中可能為空的引用型變量，在空指針異常故障定位中發(fā)揮著十分關(guān)鍵的作用。在Java中，值為null的對(duì)象調(diào)用任何方法都會(huì)引發(fā)空指針異常，空指針引用在程序中較為隱蔽，因而空指針異常是Java中最難查找和調(diào)試的一種異常。如果能找出程序中所有的值可能為空的對(duì)象，則會(huì)大大縮小查找空指針異常的錯(cuò)誤值來(lái)源的范圍。利用開(kāi)源軟件soot[17]中提供的編程接口實(shí)現(xiàn)的空指針?lè)治龉δ堋＞唧w而言，在程序切片后的程序上，找出代碼中可能為空值的引用型變量并將其標(biāo)出，以便于找到引發(fā)空指針異常的錯(cuò)誤值來(lái)源。實(shí)際上，對(duì)于一個(gè)包含引用型變量v的語(yǔ)句，可利用soot提供的編程接口，實(shí)現(xiàn)對(duì)變量v取值的判斷，即v是否可能為空。

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

算法2doNullnessAnalysis

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

4.4 別名分析

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

算法3doAliasAnalysis

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

5 實(shí)證研究

5.1 實(shí)驗(yàn)設(shè)計(jì)

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

表1 實(shí)驗(yàn)對(duì)象介紹

5.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

針對(duì)表2和表3中的數(shù)據(jù)，采用Wilcoxon配對(duì)檢驗(yàn)，結(jié)果表明，在實(shí)時(shí)堆棧信息指導(dǎo)下對(duì)程序約簡(jiǎn)后的切片規(guī)模比直接在源程序上所得切片規(guī)模有比較顯著的縮小(p-value= 0.064 1)，且空指針?lè)治龅囊?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%)計(jì)算切片分析程序規(guī)模，因此，可以減少切片計(jì)算時(shí)分析程序、計(jì)算程序依賴(lài)關(guān)系的時(shí)間?？偟貋?lái)看，本文方法增加了程序縮減所需時(shí)間，減少了計(jì)算程序切片所需的時(shí)間。

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

6 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語(yǔ)

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

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

[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é)報(bào)， 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] 姜淑娟， 徐寶文， 史亮等. 一種基于異常傳播分析的依賴(lài)性分析方法[J]. 軟件學(xué)報(bào)， 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] 徐寶文， 聶長(zhǎng)海， 史亮等. 一種基于組合測(cè)試的軟件故障調(diào)試方法[J]. 計(jì)算機(jī)學(xué)報(bào)， 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.