陳偉
(四川大學(xué)計(jì)算機(jī)學(xué)院,成都 610065)
動(dòng)態(tài)程序分析技術(shù)在錯(cuò)誤定位中的應(yīng)用
陳偉
(四川大學(xué)計(jì)算機(jī)學(xué)院,成都 610065)
錯(cuò)誤定位是軟件調(diào)試過(guò)程中的一個(gè)關(guān)鍵問(wèn)題。為了降低調(diào)試成本,輔助開發(fā)人員定位和修復(fù)程序錯(cuò)誤,基于動(dòng)態(tài)分析的錯(cuò)誤定位技術(shù)通過(guò)選擇測(cè)試用例,運(yùn)行待測(cè)程序,跟蹤并分析程序執(zhí)行過(guò)程及結(jié)果,給出造成錯(cuò)誤的程序缺陷在源代碼中的可能位置。歸納總結(jié)基于動(dòng)態(tài)分析的錯(cuò)誤定位領(lǐng)域的相關(guān)成就,并且從故障性質(zhì)研究、多方式結(jié)合和新技術(shù)引入研究三方面展望基于動(dòng)態(tài)分析的錯(cuò)誤定位技術(shù)的發(fā)展趨勢(shì),并進(jìn)行總結(jié)。
程序分析;錯(cuò)誤定位;軟件調(diào)試;程序依賴關(guān)系
在工業(yè)界,為了能確保軟件的質(zhì)量,他們?cè)跍y(cè)試和維護(hù)中投入了不少的精力。在整個(gè)軟件開發(fā)周期中,測(cè)試和維護(hù)所需要的成本比例非常之高,而在測(cè)試和維護(hù)過(guò)程中,調(diào)試是其最困難的一部分,而錯(cuò)誤定位又是調(diào)試階段中耗費(fèi)最大的一步。所以,通過(guò)改進(jìn)在定位過(guò)程中的任何一方面都可以在一定程度上降低調(diào)試的開銷。根據(jù)定位過(guò)程“是否需要運(yùn)行軟件”為準(zhǔn)則,錯(cuò)誤定位技術(shù)可以分為基于動(dòng)態(tài)的和基于靜態(tài)的,基于動(dòng)態(tài)分析的錯(cuò)誤定位(Dynamic Analysis-Based Fault Localization,DABFL)是指開發(fā)者設(shè)計(jì)測(cè)試用例,并根據(jù)設(shè)計(jì)的測(cè)試用例去并運(yùn)行程序,然后根據(jù)程序的執(zhí)行軌跡和行為特征信息給出錯(cuò)誤的可能位置。
本文同時(shí)采用文件計(jì)量法和文獻(xiàn)綜述法,根據(jù)提出的有關(guān)該領(lǐng)域的幾個(gè)需要回答的問(wèn)題,然后確定關(guān)鍵字以及檢索策略進(jìn)行文獻(xiàn)檢索,接著根據(jù)篩選原則對(duì)檢索得到的論文進(jìn)行篩選,然后對(duì)篩選過(guò)后剩下的論文進(jìn)行數(shù)據(jù)提取和分析,最后形成報(bào)告。然后主要對(duì)基于動(dòng)態(tài)分析的錯(cuò)誤定位技術(shù)所涉及到的一些方法和模型進(jìn)行歸納總結(jié),并根據(jù)現(xiàn)有的研究情況,對(duì)未來(lái)動(dòng)態(tài)程序分析技術(shù)在錯(cuò)誤定位中的應(yīng)用研究趨勢(shì)進(jìn)行展望。
文獻(xiàn)計(jì)量法總共分為五步:確定研究范圍、抽取樣本、界定分析單元、對(duì)分析單元做量化統(tǒng)計(jì)和建立反應(yīng)其趨勢(shì)變化的規(guī)律總結(jié)。
1.1 檢索方案
首先確定三個(gè)研究問(wèn)題:1)現(xiàn)有錯(cuò)誤定位技術(shù)有哪些?2)動(dòng)態(tài)程序分析技術(shù)在錯(cuò)誤定位中的應(yīng)用有哪些?3)基于動(dòng)態(tài)程序分析的錯(cuò)誤定位方法的研究趨勢(shì)是什么?然后確定關(guān)鍵詞:程序分析(Program Analysis)、動(dòng)態(tài)程序分析(Dynamic Program Analysis)、錯(cuò)誤(故障)定位(Fault Localization),接著在關(guān)鍵論文數(shù)據(jù)庫(kù)中進(jìn)行文獻(xiàn)檢索,檢索年限為2004-2016年。然后對(duì)檢索得到的論文根據(jù)一定的原則進(jìn)行篩選和去重。最后得到有關(guān)錯(cuò)誤定位的文獻(xiàn)有200多篇,這200多篇作為文獻(xiàn)計(jì)量統(tǒng)計(jì)的輸入數(shù)據(jù)。而文獻(xiàn)綜述只選擇其中的一部分重要參考文獻(xiàn)進(jìn)行綜述。我們對(duì)得到的200多篇文獻(xiàn)通過(guò)工具進(jìn)行分析,得到了一些客觀的分析結(jié)果。
1.2 結(jié)果分析
(1)年限分析
對(duì)采集到的論文的年份、數(shù)量特征進(jìn)行統(tǒng)計(jì)分析,可以在一定程度上根據(jù)文獻(xiàn)的增長(zhǎng)情況得到近12年間關(guān)于“程序分析在錯(cuò)誤定位中的應(yīng)用”研究的總體研究水平和發(fā)展速度。通過(guò)分析可知,自2004年以來(lái)關(guān)于“程序分析在錯(cuò)誤定位中的應(yīng)用”的研究文獻(xiàn)數(shù)量大致呈現(xiàn)上升趨勢(shì)。2004至2008關(guān)于此項(xiàng)研究的文獻(xiàn)相對(duì)比較少,數(shù)量波動(dòng)也不是很大;2009年數(shù)量相比2008年,論文數(shù)量增加了一倍多,然后繼續(xù)呈現(xiàn)一個(gè)上升的增長(zhǎng)趨勢(shì),一直到2016。
(2)期刊分布和載文比
論文的期刊分布和載文比可以在一定程度上反映出一段時(shí)期內(nèi)該領(lǐng)域研究的成熟度。因此,對(duì)“程序分析在錯(cuò)誤定位中的應(yīng)用”研究論文的期刊分布和載文比進(jìn)行統(tǒng)計(jì)分析可知,自2004年以來(lái),刊載程序分析研究論文的期刊數(shù)量大致呈現(xiàn)逐年增長(zhǎng)的趨勢(shì),刊載種數(shù)的增加,說(shuō)明研究涉及的領(lǐng)域越來(lái)越多,分布更加廣泛。
(3)期刊類型分布
對(duì)刊載論文的期刊類型分布進(jìn)行分析,可以了解到“程序分析在錯(cuò)誤定位中的應(yīng)用”研究的主要集中在哪些類型的期刊,從另外一個(gè)方面也能看到該研究領(lǐng)域發(fā)展到了哪一個(gè)程度。我們對(duì)搜集到的200多篇論文進(jìn)行期刊類型分布統(tǒng)計(jì),得知在期刊分布上還比較分散研究論文主要集中在Conference Paper和Journal Article上,占據(jù)總論文數(shù)量的69.88%。其次是在Conference Proceeding和Thesis,分別占據(jù)22.89%和7.23%。
(4)作者分析
作者分布情況可以體現(xiàn)在該領(lǐng)域研究的廣度以及深度。作者數(shù)越多,說(shuō)明該研究領(lǐng)域越廣,某一個(gè)作者出現(xiàn)的頻次越高,說(shuō)明該作者在這個(gè)領(lǐng)域研究得比較深入。通過(guò)對(duì)搜集到的論文進(jìn)行作者分布統(tǒng)計(jì)(包含第一作者,第二作者,第三作者),共有600多名作者參與該領(lǐng)域的研究,對(duì)出現(xiàn)頻次比較高的作者進(jìn)行統(tǒng)計(jì),發(fā)現(xiàn)Zhang,Zhenyu、Wong,W.Eric、徐寶文名列前三。
(5)關(guān)鍵詞分析
我們對(duì)搜集到的200多篇論文中的關(guān)鍵詞進(jìn)行統(tǒng)計(jì)分析,共獲得956個(gè)關(guān)鍵詞,對(duì)這些關(guān)鍵詞進(jìn)行頻度統(tǒng)計(jì),按照頻次高低排序所得的前3位高頻詞的統(tǒng)計(jì)結(jié)果是Fault Localization、Program Debugging和Debugging。統(tǒng)計(jì)結(jié)果顯示,錯(cuò)誤定位也叫做故障定位、錯(cuò)誤診斷或缺陷定位,主要應(yīng)用在程序調(diào)試程序測(cè)試中。從關(guān)鍵詞的頻度可以看出,動(dòng)態(tài)程序分析技術(shù)(這里指自動(dòng)化調(diào)試)主要技術(shù)是統(tǒng)計(jì)分析(Statistical Analysis)和程序切片分析(Program Slicing)。
2.1 輕量級(jí)錯(cuò)誤定位方法
在輕量級(jí)錯(cuò)誤定位方法中,我們只關(guān)注覆蓋信息,程序?qū)嶓w之間的依賴關(guān)系一般不涉及,然后使用統(tǒng)計(jì)方法或數(shù)據(jù)挖掘的方法進(jìn)行信息的處理。根據(jù)故障定位方式等信息,輕量級(jí)錯(cuò)誤定位方法可以分為基于執(zhí)行覆蓋(Coverage-Based Fault Localization,CBFL)和基于模型(Model-Based Fault Localization,MBFL)兩大類。
(1)基于執(zhí)行覆蓋的錯(cuò)誤定位方法
①基于語(yǔ)句或基本塊
Renieres和Reiss[1]提出了一種程序光譜對(duì)比的錯(cuò)誤定位方法,在程序測(cè)試過(guò)程中,首先假設(shè)其存在很多個(gè)成功的執(zhí)行和一個(gè)失敗的執(zhí)行,然后根據(jù)距離準(zhǔn)則來(lái)選擇一個(gè)和失敗運(yùn)行最相似的成功運(yùn)行的程序光譜,最后根據(jù)光譜差異性來(lái)分離程序缺陷。Jones和Harrold等人[2]認(rèn)為,如果一個(gè)程序?qū)嶓w被大部分的失敗用例執(zhí)行過(guò),那么就應(yīng)該被考察,于是提出了Tarantula錯(cuò)誤定位方法,于此同時(shí),他們開發(fā)了一個(gè)工具原型,通過(guò)故障可疑度來(lái)定位錯(cuò)誤。
②基于謂詞
Liblit等人[3]提出了CBI(Cooperative Bug Isolation)錯(cuò)誤定位技術(shù),也被稱為L(zhǎng)iblit05,是一種基于謂詞覆蓋的互操作分離故障技術(shù)。該技術(shù)通過(guò)利用謂詞的真假取值,然后對(duì)比與其后某個(gè)錯(cuò)誤的出現(xiàn)存在的關(guān)聯(lián)性,于此同時(shí),利用插樁技術(shù)來(lái)獲取謂詞的覆蓋信息。然后,Zhang等人[4]把短路求值和求值序列考慮在內(nèi),通過(guò)分析他們之間的關(guān)系,提出了一種基于謂詞的錯(cuò)誤定位方法的DES(Debugging through Evaluation Sequences)改進(jìn)策略,有效地提高了錯(cuò)誤定位的效率。
③基于方法
Dallmeier等人[5]認(rèn)為在失敗執(zhí)行中,如果某一個(gè)類調(diào)用了成功執(zhí)行中不同的方法,那么是不是應(yīng)該更值得被考察和懷疑,據(jù)此他們提出了一種基于方法調(diào)用序列的技術(shù),被稱為Ample技術(shù)。寧國(guó)秀等人[6]針對(duì)C源程序提出一種基于函數(shù)調(diào)用路徑的數(shù)據(jù)流分析技術(shù),主要分析程序中的數(shù)據(jù)流信息,他們結(jié)合程序切片,根據(jù)函數(shù)調(diào)用路徑,進(jìn)一步分析數(shù)據(jù)流的變化,從而定位錯(cuò)誤。
(2)基于模型的錯(cuò)誤定位方法
①基于統(tǒng)計(jì)模型
Liu等人[7]基于參數(shù)統(tǒng)計(jì)中的分布函數(shù),提出了基于統(tǒng)計(jì)模型SOBER的故障定位方法。該方法需要獲取謂詞在成功失敗執(zhí)行中的取值模式,然后根據(jù)該取值模式進(jìn)行建模,最后根據(jù)假設(shè)檢驗(yàn)原理,進(jìn)一步具體分析,以此量化謂詞在取值上的偏差,并將此偏差結(jié)果作為謂詞的懷疑度。Yu等人[8]進(jìn)一步提出了一種錯(cuò)誤的定位方法,被稱為L(zhǎng)OUPE。它可以同時(shí)利用到多個(gè)模型,根據(jù)每個(gè)模型適用的情況,來(lái)定位不同類型的錯(cuò)誤。因?yàn)殄e(cuò)誤類型最開始是不知道的,所以LOUPE方法通過(guò)建立了多個(gè)模型來(lái)獲取程序語(yǔ)句的不正常行為和狀態(tài)信息,然后從上一步獲取的信息中選出適合的模型來(lái)定位錯(cuò)誤。
②基于時(shí)間頻譜模型
Yilmaz等人[9]利用時(shí)間光譜作為程序執(zhí)行特征的抽象,同時(shí)運(yùn)用了高斯混合模型,對(duì)成功執(zhí)行的時(shí)間頻譜進(jìn)行聚類分析,進(jìn)而對(duì)每個(gè)類進(jìn)行高斯分布建模,通過(guò)利用時(shí)間頻譜信息,查找程序函數(shù)中隱藏的錯(cuò)誤,該方法被稱為TWT(Time Will Tell)方法。
③基于程序狀態(tài)模型
徐寶文等人[10]考慮了值向量,他們認(rèn)為,待測(cè)系統(tǒng)和測(cè)試用例可以用值向量來(lái)表示,然后對(duì)其測(cè)試結(jié)果和附加測(cè)試用例的測(cè)試結(jié)果進(jìn)行對(duì)比分析,進(jìn)而尋找錯(cuò)誤的可能位置。Delta Debugging方法是由Zeller提出的,該方法能夠自動(dòng)減小程序成功和失敗運(yùn)行過(guò)程之間的區(qū)別。它采用分治的思想和遞歸思想,逐漸減小兩個(gè)集合之間的差異,最終確認(rèn)成功和失敗配置差異的一個(gè)最小集。
④基于其他行為模型
Guoshun,Chen等人[11]認(rèn)為MAS(Multi-Agent System)具有較強(qiáng)的自主性和智能性,同時(shí)具有較強(qiáng)的社會(huì)能力,容易與軟件密集型裝備現(xiàn)有的軟件測(cè)試方案進(jìn)行集成。于是,他們提出了一種新的基于MAS的故障診斷框架,整個(gè)錯(cuò)誤診斷系統(tǒng)被分為四部分:System Management Agent(SMA)、Pre-Processing Agent(PPA)、Fault Localization Agent(FLA)和Failure Analysis Agent (FAA)。SMA層直接與用戶進(jìn)行交互,為用戶提供軟件錯(cuò)誤斬?cái)嘞到y(tǒng)的接口,并且與Sevice Agent之間相互合作。PPA層包括了Lexical Analyzer Agent和Syntax Analyzer Agent,它主要的功能就是生成語(yǔ)法樹(Syntax tree)。FLA層包括Syntax Tree Analyzer Agent(STAA)和Automatic Instrumentation Agent(AIA)。STAA自動(dòng)分析源代碼的儀器精確度,AIA自動(dòng)接收STAA的結(jié)果,然后插入探測(cè)函數(shù),并記錄執(zhí)行信息。FAA層包括了Coverage Analyzer Agent和Query Agent,主要用來(lái)實(shí)現(xiàn)語(yǔ)句和分支覆蓋測(cè)試,并自動(dòng)查詢覆蓋率是否滿足需求,程序是否為目標(biāo)程序。此框架已應(yīng)用與真正的軟件診斷當(dāng)中,并且證明了它的有效性。
王克朝等人[12]通過(guò)利用插樁,構(gòu)建了一種程序譜構(gòu)建模型,通過(guò)該模型,可以明顯提高源代碼的處理效率,該模型中的有窮自動(dòng)機(jī)能夠準(zhǔn)確識(shí)別插樁點(diǎn),有效提高錯(cuò)誤定位的速度。通過(guò)實(shí)驗(yàn)驗(yàn)證,該技術(shù)可以在一定程度上提高錯(cuò)誤定位的效率。
2.2 重量級(jí)錯(cuò)誤定位方法
重量級(jí)錯(cuò)誤定位方法需要分析程序?qū)嶓w之間的依賴關(guān)系,包括數(shù)據(jù)依賴、控制依賴以及其他依賴關(guān)系,于此同時(shí),相對(duì)輕量級(jí)錯(cuò)誤定位方法,它需要耗費(fèi)更高的時(shí)間和空間代價(jià)。
(1)基于依賴關(guān)系的錯(cuò)誤定位方法
Baah等人考慮了程序依賴圖,他們?cè)诔绦蛞蕾噲D上,通過(guò)增加結(jié)點(diǎn)和邊的概率信息,建立了概率程序依賴圖PPDG(Probabilistic Program Dependence Graph),用來(lái)反映程序元素之間的的行為。Feng和Gupta等人[13]基于動(dòng)態(tài)依賴圖建立基于貝葉斯網(wǎng)絡(luò)的錯(cuò)誤流圖EFG (Error Flow Graph)和通用的概率模型。然后基于標(biāo)準(zhǔn)的推理算法從葉節(jié)點(diǎn)沿著錯(cuò)誤流后向追溯尋找錯(cuò)誤可能性最大的可執(zhí)行語(yǔ)句。
(2)基于程序切片的錯(cuò)誤定位方法
早前是由Weiser提出了一種被稱為程序切片的概念,它是用來(lái)描述影響程序某個(gè)執(zhí)行點(diǎn)上特定變量的語(yǔ)句的集合。Zhang等人[14]提出了一種動(dòng)態(tài)切片錯(cuò)誤定位方法,定義切片準(zhǔn)則,計(jì)算數(shù)據(jù)切片、全切片和相關(guān)切片,進(jìn)而有效分離出錯(cuò)誤相關(guān)語(yǔ)句,以此來(lái)達(dá)到定位錯(cuò)誤的目的。另外,通過(guò)比較三種單點(diǎn)切片(后向切片、前向切片、雙向切片)的不同,他們還提出了一種基于多點(diǎn)切片的錯(cuò)誤定位方法。文萬(wàn)志等人[15]為了解決并發(fā)程序中數(shù)據(jù)共享錯(cuò)誤定位問(wèn)題,他們使用關(guān)系構(gòu)造靜態(tài)并發(fā)序列切片和動(dòng)態(tài)并發(fā)序列切片,來(lái)提高在程序數(shù)據(jù)共享錯(cuò)誤定位上的準(zhǔn)確率。
軟件錯(cuò)誤定位方法研究是軟件調(diào)試過(guò)程中的一個(gè)熱點(diǎn)問(wèn)題。本文首先對(duì)該領(lǐng)域的文獻(xiàn)進(jìn)行了文獻(xiàn)計(jì)量分析,然后從輕量級(jí)和重量級(jí)兩個(gè)角度歸納總結(jié)了現(xiàn)有的基于動(dòng)態(tài)分析的錯(cuò)誤定位方法,闡述了具有代表性的錯(cuò)誤定位技術(shù)。我們發(fā)現(xiàn),不涉及程序?qū)嶓w依賴關(guān)系,使用統(tǒng)計(jì)學(xué)方法對(duì)程序語(yǔ)句、分支、函數(shù)或類等的懷疑度進(jìn)行計(jì)算并排序,進(jìn)而定位錯(cuò)誤的研究成果最多,而需要分析程序?qū)嶓w之間依賴關(guān)系的錯(cuò)誤定位方法相對(duì)較少。研究者多數(shù)借助抽象和簡(jiǎn)化來(lái)研究錯(cuò)誤定位,從而忽略了故障固有的一些特性。同時(shí)采用多種方式相結(jié)合的技術(shù)也會(huì)提高錯(cuò)誤定位的效率,例如動(dòng)態(tài)分析和靜態(tài)分析相結(jié)合,不同方法相結(jié)合。于此同時(shí),開發(fā)者們也開始利用數(shù)據(jù)挖掘、人工智能、機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)等新技術(shù)來(lái)進(jìn)行錯(cuò)誤定位,在未來(lái),這些新技術(shù)是一個(gè)發(fā)展趨勢(shì),值得深一步的研究。
[1]M.Renieres,S.P.Reiss.Fault Localization with Nearest Neighbor Queries.in Automated Software Engineering,2003.Proceedings. 18th IEEE International Conference on,2003,pp.30-39.
[2]J.A.Jones,M.J.Harrold,J.Stasko.Visualization of Test Information to Assist Fault Localization.in Software Engineering,2002.ICSE 2002.Proceedings of the 24rd International Conference on,2002,pp.467-477.
[3]B.Liblit,M.Naik,A.X.Zheng,A.Aiken,M.I.Jordan.Scalable Statistical Bug Isolation.in ACM SIGPLAN Notices,2005:15-26.
[4]Z.Zhang,B.Jiang,W.Chan,T.Tse,X.Wang.Fault Localization Through Evaluation Sequences.Journal of Systems and Software,vol. 83,pp.174-187,2010.
[5]V.Dallmeier,C.Lindig,A.Zeller.Lightweight Defect Localization for Java.in ECOOP 2005-Object-Oriented Programming,ed: Springer,2005,pp.528-550.
[6]寧國(guó)秀,牟永敏,申閆春,張志華.基于函數(shù)調(diào)用路徑的數(shù)據(jù)流分析錯(cuò)誤定位.計(jì)算機(jī)仿真,2016.
[7]C.Liu,L.Fei,X.Yan,J.Han,S.P.Midkiff.Statistical Debugging:A Hypothesis Testing-Based Approach.Software Engineering, IEEE Transactions on,vol.32,pp.831-848,2006.
[8]K.Yu,M.Lin,Q.Gao,H.Zhang,X.Zhang.Locating Faults Using Multiple Spectra-Specific Models.in Proceedings of the 2011 ACM Symposium on Applied Computing,2011,pp.1404-1410.
[9]C.Yilmaz,A.Paradkar,C.Williams.Time Will Tell:Fault Localization Using Time Spectra.in Proceedings of the 30th International Conference on Software Engineering,2008:81-90.
[10]X.Baowen,N.Changhai,S.Liang,C.Huo-Wang.A Software Failure Debugging Method Based on Combinatorial Design Approach for Testing.Chinese Journal of Computers,vol.29,pp.132-138,2006.
[11]C.Guoshun,M.Sasa,X.Mingfei.A Kind of Software Fault Diagnosing Framework Based on Multi-Agent.in Quality,Reliability, Risk,Maintenance,and Safety Engineering(ICQR2MSE),2012 International Conference on,2012,pp.760-762.
[12]王克朝,李兵,王甜甜,陳京浩.基于插樁技術(shù)的程序譜構(gòu)建方法.科學(xué)技術(shù)與工程,2014.
[13]M.Feng,R.Gupta.Learning Universal Probabilistic Models for Fault Localization.in Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering,2010:81-88.
[14]X.Zhang,H.He,N.Gupta,R.Gupta.Experimental Evaluation of Using Dynamic Slices for Fault Location.in Proceedings of the Sixth International Symposium on Automated Analysis-Driven Debugging,2005,pp.33-42.
[15]文萬(wàn)志,程實(shí).并發(fā)序列切片.科技創(chuàng)新與應(yīng)用,2015.
Application of Dynamic Program Analysis Techniques in the Fault Localization
CHEN Wei
(College of Computer Science,Sichuan University,Chengdu 610065)
Fault localization is a key research topic in the software debugging.In order to reduce the cost of debugging and assist the developers to locate and repair program faults,dynamic analysis-based fault localization techniques identify possible locations of faults by selecting test case,running programs and analyzing the program’s running process and results.Summarizes the achievements in the field of dynamic analysis-based fault localization,summarizes this technique and discusses its development trend from the view of fault properties,multiple methods combination and new technique.
Program Analysis;Fault Localization;Software Debugging;Program Dependency
1007-1423(2017)05-0034-05
10.3969/j.issn.1007-1423.2017.05.009
陳偉(1991-),男,重慶人,碩士研究生,研究方向?yàn)榍度胧綔y(cè)試與開發(fā)
2016-11-24
2017-03-10