1、動(dòng)態(tài)程序分析方法與工具目錄動(dòng)態(tài)程序分析方法與工具11.前言21.1研究背景21.2基本概念31.3研究?jī)r(jià)值和意義41.4研究路線42.研究方法42.1 檢索方案42.2 系統(tǒng)文獻(xiàn)綜述法62.3 文獻(xiàn)計(jì)量法73. 文獻(xiàn)計(jì)量分析93.1 年限分析93.2 期刊分布93.3 載文比分析103.4 期刊類型分布113.5 作者分析113.6 關(guān)鍵詞分析134.動(dòng)態(tài)程序分析144.1 動(dòng)態(tài)程序分析方法144.2 動(dòng)態(tài)程序分析工具264.3 動(dòng)態(tài)程序分析在軟件測(cè)試中的應(yīng)用265.未來(lái)研究展望265.1 錯(cuò)誤定位新理論和新技術(shù)的引入與集成265.2 程序算法檢測(cè)新的發(fā)展形態(tài)275.3 軟件運(yùn)行平臺(tái)的新發(fā)展2

2、76. 結(jié)束語(yǔ)27參考文獻(xiàn)27摘要：關(guān)鍵字：程序分析、動(dòng)態(tài)程序分析、文獻(xiàn)計(jì)量方法1. 前言1.1 研究背景軟件是一種十分特殊的人工制品：它是人類“智力活動(dòng)”的產(chǎn)物，是對(duì)客觀事物的虛擬反應(yīng)，是知識(shí)的固化和凝練1。迄今為止，軟件已有了50多年發(fā)展歷史，但對(duì)于一個(gè)給定的軟件，我們目前還不能完全了解它的特性。軟件分析就是以軟件特性為關(guān)注點(diǎn)的研究領(lǐng)域。經(jīng)過(guò)這么多年的發(fā)展，目前軟件生命周期中的許多活動(dòng)（分析，設(shè)計(jì)，實(shí)現(xiàn)，測(cè)試，部署，維護(hù)等）都離不開(kāi)分析技術(shù)。盡管軟件分析的能力有限，但它仍然是軟件領(lǐng)域十分有用的技術(shù)。下面將談到兩個(gè)概念，“驗(yàn)證”和“確認(rèn)”。“驗(yàn)證”是要回答“軟件制品是否與軟件需求規(guī)約一致”的

3、問(wèn)題，而“確認(rèn)”則是回答“軟件的特性是否符合用戶需求”。在英文中，“驗(yàn)證”是“Do the thing right”，而用“Do the right thing”來(lái)解釋“確認(rèn)”。驗(yàn)證就是所謂的軟件分析技術(shù)，而確認(rèn)則是軟件測(cè)試技術(shù)。軟件分析包括對(duì)文檔（需求規(guī)約、設(shè)計(jì)文檔、代碼注釋等）的分析、對(duì)運(yùn)行程序的分析，等等。而程序分析中，根據(jù)“是否需要運(yùn)行程序”為準(zhǔn)則，可以將程序分析技術(shù)劃分為靜態(tài)分析技術(shù)和動(dòng)態(tài)分析技術(shù)兩大類，本文主要嘗試對(duì)動(dòng)態(tài)程序分析涉及的主要方法和工具進(jìn)行總結(jié)和歸類，并討論動(dòng)態(tài)程序分析技術(shù)在軟件測(cè)試中的應(yīng)用和發(fā)展。本文總共分為6部分，第一部分是前言，主要對(duì)研究背景、涉及到的一些基本概念

4、、研究的價(jià)值和意義、研究路線等進(jìn)行了說(shuō)明。第二部分主要闡述了本文所涉及到的兩種研究方法：文獻(xiàn)計(jì)量方法和系統(tǒng)文獻(xiàn)綜述方法。第三部分是根據(jù)文獻(xiàn)計(jì)量方法的策略，對(duì)檢索到的文獻(xiàn)進(jìn)行具體的分析。第四部分是本文的核心內(nèi)容，主要總結(jié)和歸納現(xiàn)有的動(dòng)態(tài)程序分析技術(shù)方法和工具，并討論了動(dòng)態(tài)程序分析方法和工具在軟件測(cè)試中的應(yīng)用。第五部分結(jié)合本文所有信息對(duì)動(dòng)態(tài)程序分析技術(shù)的發(fā)展趨勢(shì)進(jìn)行展望。最后一部分是結(jié)束語(yǔ)，歸納總結(jié)了本文的研究思想和路線。1.2 基本概念1) 軟件分析軟件分析是對(duì)軟件進(jìn)行人工或者自動(dòng)分析，以驗(yàn)證、確認(rèn)或發(fā)現(xiàn)軟件性質(zhì)（或規(guī)約、約束）的過(guò)程或活動(dòng)。包括對(duì)文檔（需求規(guī)約、設(shè)計(jì)文檔、代碼注釋等）的分析、對(duì)

5、運(yùn)行程序的分析，等等。12) 程序分析程序分析是指對(duì)計(jì)算機(jī)程序行為進(jìn)行自動(dòng)分析的過(guò)程，主要包括靜態(tài)分析和動(dòng)態(tài)分析兩種策略，它是以某種語(yǔ)言書(shū)寫(xiě)的程序?yàn)閷?duì)象，對(duì)其內(nèi)部的運(yùn)作流程進(jìn)行分析。3) 動(dòng)態(tài)程序分析動(dòng)態(tài)程序分析是通過(guò)運(yùn)行具體程序并獲取程序的輸出或者內(nèi)部狀態(tài)等信息來(lái)驗(yàn)證或發(fā)現(xiàn)軟件性質(zhì)的過(guò)程。4) 靜態(tài)程序分析靜態(tài)程序分析是指在不運(yùn)行軟件前提下進(jìn)行的分析過(guò)程。5) 軟件測(cè)試：軟件測(cè)試是一組活動(dòng)，執(zhí)行這組活動(dòng)的目的是發(fā)現(xiàn)程序中可能存在的潛在錯(cuò)誤，驗(yàn)證在指定條件下程序運(yùn)行的情況，方法則是給出指定的輸入和期望的結(jié)果，觀察實(shí)際的運(yùn)行結(jié)果和期望結(jié)果之間的差異，從而對(duì)軟件的執(zhí)行正確程度做出判斷。（IEEE標(biāo)

6、準(zhǔn)610.12-1990中，對(duì)軟件測(cè)試是這樣定義的：軟件測(cè)試是在指定的條件下操作測(cè)試系統(tǒng)或組件，觀察和記錄結(jié)果，并對(duì)測(cè)試系統(tǒng)或組件的不同方面做出評(píng)估的過(guò)程。）6) 文獻(xiàn)計(jì)量方法文獻(xiàn)計(jì)量方法是一種以各種文獻(xiàn)外部特征為研究對(duì)象的量化分析方法，主要用于科學(xué)文獻(xiàn)的研究，能夠揭示各門(mén)學(xué)科的發(fā)展水平。7) 系統(tǒng)文獻(xiàn)綜述方法系統(tǒng)文獻(xiàn)綜述(systematic literature review),簡(jiǎn)稱系統(tǒng)綜述,是主要在醫(yī)學(xué)領(lǐng)域和社會(huì)學(xué)研究領(lǐng)域針對(duì)某一個(gè)研究性問(wèn)題開(kāi)展的基于文獻(xiàn)的系統(tǒng)化綜述方法,并于2004年引入軟件工程領(lǐng)域.系統(tǒng)文獻(xiàn)綜述的過(guò)程包含3個(gè)主要的階段: 制定綜述方案、開(kāi)展綜述、形成綜述報(bào)告。1.3

7、 研究?jī)r(jià)值和意義為了保證軟件開(kāi)發(fā)的質(zhì)量，業(yè)界在軟件測(cè)試和軟件分析階段投入了大量的人力物力，而動(dòng)態(tài)程序分析在軟件分析中扮演著極其重要的角色。本文對(duì)動(dòng)態(tài)程序方法和工具進(jìn)行了分析與總結(jié)，并討論了其在軟件測(cè)試當(dāng)中的應(yīng)用，不僅豐富了自己在該領(lǐng)域中的知識(shí)，增長(zhǎng)了見(jiàn)聞，同時(shí)有利于人們?cè)诜治鲕浖囟ǖ馁|(zhì)量屬性時(shí)，選取合適的技術(shù)和工具。1.4 研究路線首先提出該領(lǐng)域的幾個(gè)需要最終回答的問(wèn)題，然后確定關(guān)鍵字以及檢索策略，接著對(duì)檢索得到的論文進(jìn)行篩選，然后對(duì)篩選過(guò)后剩下的論文進(jìn)行數(shù)據(jù)提取和分析，最后形成報(bào)告。同時(shí)，我們借助EndNote文獻(xiàn)管理工具對(duì)我們檢索到的文獻(xiàn)進(jìn)行管理，方便我們閱讀和使用。2. 研究方法2.1

8、 檢索方案2.1.1 研究問(wèn)題通過(guò)該系統(tǒng)評(píng)價(jià)最終所要回答的問(wèn)題,同時(shí)可能需要進(jìn)一步明確所感興趣的研究方法(intervention)和研究結(jié)果(outcome)等其他限定條件. 1) 現(xiàn)有程序分析的方法和工具有哪些？2) 動(dòng)態(tài)程序分析的方法和工具有哪些？ 3) 動(dòng)態(tài)程序分析方法在軟件測(cè)試中的應(yīng)用有哪些？ 4) 動(dòng)態(tài)程序分析中有哪些未解決的問(wèn)題？2.1.2 搜索策略根據(jù)所要研究的問(wèn)題和關(guān)鍵詞確定查詢語(yǔ)句，并根據(jù)查詢結(jié)果,確定是否需要進(jìn)行二級(jí)查詢(比如引入新的關(guān)鍵詞或者添加新的論文集和期刊)。 確定關(guān)鍵詞：Program Analysis , Software Analysis, Dynamic

9、Program Analysis, Software Testing.邏輯表達(dá)式：(dynamic program analysis) AND (method OR tool)；(software analysis OR program analysis) AND (method OR tool) ；(software analysis OR program analysis) AND (software testing); dynamic program analysis;(software analysis) OR (program analysis);運(yùn)用的搜索引擎為Google, Go

10、ogle Scholar, IEEE Xplore；另外在四川大學(xué)圖書(shū)館IEEE Digital Library，CNKI數(shù)據(jù)庫(kù)，萬(wàn)方數(shù)據(jù)庫(kù)，學(xué)位論文庫(kù)、期刊EI和SCI、國(guó)際會(huì)議論文集中進(jìn)行檢索，檢索年限為2004年（包括2004）至2013年。文獻(xiàn)資料收集來(lái)源一般包括了圖書(shū)，期刊，報(bào)紙以及網(wǎng)絡(luò)資源。由于圖書(shū)的出版周期較長(zhǎng)并不能有效反應(yīng)該學(xué)科領(lǐng)域的研究進(jìn)展情況；網(wǎng)絡(luò)資源豐富而且反應(yīng)速度最快，但信息噪音最強(qiáng)；報(bào)紙資源的研究深度尚淺。因此，本文選擇以國(guó)內(nèi)外期刊，會(huì)議等作為文獻(xiàn)資料的來(lái)源。通過(guò)檢索，經(jīng)過(guò)去重操作，得到相關(guān)論文1066篇。2.1.3 篩選方案1) 長(zhǎng)文優(yōu)于短文。對(duì)于短文或者Poste

11、r,通過(guò)DBLP查詢作者是否有相關(guān)的工作發(fā)表在其他地方,若有,則引用相對(duì)比較完整的論文,若沒(méi)有,則將相應(yīng)的短文或者Poster排除掉；2) 學(xué)位論文只要博士論文；3) 期刊只搜EI和SCI論文；4) 國(guó)際會(huì)議最好是國(guó)外國(guó)際會(huì)議，或主要成員是外國(guó)學(xué)者；5) 若論文的目的是提出一種形式化驗(yàn)證技術(shù),則將該論文包含進(jìn)來(lái)；若論文的目的不是提出一種形式化驗(yàn)證技術(shù),而是基于已有的一種形式化驗(yàn)證技術(shù)提出了新的軟件形式化驗(yàn)證技術(shù)和方法，則也將該論文包含進(jìn)來(lái);6) 雖然論文中沒(méi)有涉及到具體的形式化驗(yàn)證技術(shù),但提出了關(guān)于形式化驗(yàn)證技術(shù)新的方法論,同樣也將這類論文包含進(jìn)來(lái);7) 同時(shí)對(duì)于內(nèi)容重復(fù)的文章:同一作者類似的

12、文章發(fā)表在多個(gè)地方或者一篇綜述很好地概括了一系列的相關(guān)研究,只選擇了那些我們認(rèn)為更具代表性的文章。通過(guò)幾輪篩選，最終確定下來(lái)的文獻(xiàn)有108篇。2.1.4 數(shù)據(jù)提取和分析 對(duì)于檢索到的有關(guān)程序分析的論文，我們對(duì)入選的論文根據(jù)提出的問(wèn)題進(jìn)行分類、分析和總結(jié)。閱讀過(guò)程中重點(diǎn)提取技術(shù)報(bào)告數(shù)據(jù)、專利、軟件工具（網(wǎng)站、軟件、描述性語(yǔ)言），應(yīng)用案例、方法等。2.1.5 完成報(bào)告在上述工作的基礎(chǔ)上完成最終的報(bào)告. 2.2 系統(tǒng)文獻(xiàn)綜述法系統(tǒng)文獻(xiàn)綜述(systematic literature review),簡(jiǎn)稱系統(tǒng)綜述,是主要在醫(yī)學(xué)領(lǐng)域和社會(huì)學(xué)研究領(lǐng)域針對(duì)某一個(gè)研究性問(wèn)題開(kāi)展的基于文獻(xiàn)的系統(tǒng)化綜述方法,并于

13、2004年引入軟件工程領(lǐng)域.系統(tǒng)文獻(xiàn)綜述的過(guò)程包含3個(gè)主要的階段: 制定綜述方案主要進(jìn)行綜述需求分析,明確綜述的目的,設(shè)計(jì)開(kāi)展綜述的規(guī)程,以指導(dǎo)后期的文獻(xiàn)收集等工作; 開(kāi)展綜述根據(jù)綜述方案預(yù)定的目標(biāo),按照綜述步驟進(jìn)行文獻(xiàn)收集,主要工作包括確定主要的文獻(xiàn)來(lái)源、確定收錄標(biāo)準(zhǔn)、實(shí)現(xiàn)文獻(xiàn)質(zhì)量評(píng)價(jià)、開(kāi)展數(shù)據(jù)抽取與綜合; 形成綜述報(bào)告對(duì)于綜述進(jìn)行總結(jié). 圖-系統(tǒng)文獻(xiàn)綜述法框架圖如上圖，系統(tǒng)文獻(xiàn)綜述法細(xì)致劃分可劃分為四部分：計(jì)劃、選擇、提取和結(jié)果，最后形成系統(tǒng)性的報(bào)告。2.3 文獻(xiàn)計(jì)量法文獻(xiàn)計(jì)量法是一種以各種文獻(xiàn)外部特征為研究對(duì)象的量化分析方法，以文獻(xiàn)的量為研究對(duì)象，以文獻(xiàn)文本為基本特征。它是借助文獻(xiàn)的各種

14、特征數(shù)量，采用數(shù)學(xué)與統(tǒng)計(jì)學(xué)方法來(lái)描述、評(píng)價(jià)和預(yù)測(cè)科學(xué)技術(shù)的現(xiàn)狀與發(fā)展趨勢(shì)的圖書(shū)情報(bào)學(xué)分支學(xué)科2。下面通過(guò)幾個(gè)方面對(duì)它進(jìn)行介紹：1) 性質(zhì)上：文獻(xiàn)計(jì)量分析法的特征在于其輸出量必定是量化信息內(nèi)容，是一種基于數(shù)學(xué)和統(tǒng)計(jì)學(xué)的定量分析方法。2) 方法論基礎(chǔ)上：文獻(xiàn)計(jì)量法是以數(shù)學(xué)和統(tǒng)計(jì)學(xué)方法論為基礎(chǔ)，在其應(yīng)用過(guò)程中再利用推理和比較的方法對(duì)文獻(xiàn)的分布趨勢(shì)進(jìn)行預(yù)測(cè)。3) 研究對(duì)象上：文獻(xiàn)計(jì)量法研究的對(duì)象主要是文獻(xiàn)的外部形式特征，只適用于有實(shí)體形態(tài)的科學(xué)文獻(xiàn)，比如具有著者、引文、詞匯等文獻(xiàn)特征的部分。4) 應(yīng)用領(lǐng)域上：文獻(xiàn)計(jì)量法是圖書(shū)館學(xué)、情報(bào)學(xué)的特殊研究方法，主要用于科學(xué)文獻(xiàn)的研究，對(duì)各門(mén)學(xué)科都使用。在發(fā)展的

15、幾十年中，文獻(xiàn)計(jì)量法的應(yīng)用領(lǐng)域不斷拓寬，其內(nèi)容包括作者分布規(guī)律、文獻(xiàn)分散增長(zhǎng)規(guī)律、引文分析等。通過(guò)引文分析，了解學(xué)科發(fā)展動(dòng)態(tài)；在學(xué)科核心期刊測(cè)定中的應(yīng)用，通過(guò)統(tǒng)計(jì)分析確定核心期刊的范圍；在圖書(shū)情報(bào)系統(tǒng)管理領(lǐng)域等情報(bào)探索系統(tǒng)研究中也得到廣泛應(yīng)用。5) 研究的側(cè)重點(diǎn)：它側(cè)重于分析文獻(xiàn)形式特征的“量”，它從定量的角度分析文獻(xiàn)規(guī)律，知識(shí)間接反映內(nèi)容的相關(guān)關(guān)系。研究步驟：確定研究范圍，抽取樣本，界定分析單元，對(duì)分析單元做量化統(tǒng)計(jì)，最后根據(jù)統(tǒng)計(jì)結(jié)果建立反映其趨勢(shì)變化的規(guī)律性結(jié)論。圖-文獻(xiàn)計(jì)量法研究步驟3. 文獻(xiàn)計(jì)量分析為了觀察整個(gè)程序分析領(lǐng)域的研究情況，于是此文獻(xiàn)計(jì)量分析的樣本數(shù)據(jù)不僅包括了程序分析技術(shù)中

16、的動(dòng)態(tài)分析，同時(shí)也囊括了靜態(tài)程序分析相關(guān)文獻(xiàn)。3.1 年限分析對(duì)采集到的論文的年份，數(shù)量特征進(jìn)行統(tǒng)計(jì)分析，可以在一定程度上根據(jù)文獻(xiàn)的增長(zhǎng)情況得到近10年間關(guān)于“程序分析技術(shù)”研究的總體研究水平和發(fā)展速度，如圖1所示：圖1 程序分析研究論文數(shù)量變化從圖1中可以看出自2004年以來(lái)關(guān)于程序分析技術(shù)的研究文獻(xiàn)數(shù)量大致呈現(xiàn)上升趨勢(shì)，2004至2007關(guān)于此項(xiàng)研究的文獻(xiàn)相對(duì)比較少，數(shù)量波動(dòng)不是很大，2008年數(shù)量相比2007年產(chǎn)生了驟變，2009至2012文獻(xiàn)數(shù)量維持著相對(duì)較高的水平，并且在2011年達(dá)到最高值，而2013數(shù)量相對(duì)減少。3.2 期刊分布論文的期刊分布和載文比可以在一定程度上反映出一段時(shí)期

17、內(nèi)該領(lǐng)域研究的成熟度。因此，對(duì)程序分析研究論文的期刊分布和載文比進(jìn)行統(tǒng)計(jì)分析可知，自2004年以來(lái)，共有317種期刊刊載了相關(guān)的論文刊載程序分析研究論文的期刊數(shù)量呈現(xiàn)逐年增長(zhǎng)的趨勢(shì)，刊載種數(shù)的增加，說(shuō)明研究涉及的領(lǐng)域越來(lái)越多，分布更加廣泛。圖2 程序分析研究論文期刊分布從圖2可以看出，刊載程序分析研究論文的期刊種數(shù)從2004年到2010年逐年增加，2011有所下降，而2012年，急劇增加，2013年又回到平穩(wěn)狀態(tài)。3.3 載文比分析圖3 程序分析研究論文載文比情況從載文比（該時(shí)段論文總數(shù)/該時(shí)段的期刊總數(shù)）來(lái)看，除了2011年載文比達(dá)到3.5以外，其他年度載文比斗小于3，特別在2012年，達(dá)到

18、最低0.66，這表明程序分析研究論文還沒(méi)有向一些特定的期刊集中，研究文獻(xiàn)在期刊分布上還比較分散，該研究的發(fā)展還不夠成熟。3.4 期刊類型分布對(duì)刊載論文的期刊類型分布進(jìn)行分析，可以了解到軟件分析研究的主要集中在哪些類型的期刊，從另外一個(gè)方面也能看到該研究領(lǐng)域發(fā)展到了哪一個(gè)程度。我們對(duì)搜集到的740篇論文進(jìn)行期刊類型分布統(tǒng)計(jì)，如下圖。圖4 程序分析研究論文刊載期刊類型分布情況根據(jù)圖4可以看出，程序分析研究論文主要集中在Conference Proceedings和Journal Article上，其次是在Generic和Thesis上，Conference Paper, Patent 和 Web

19、Page上相對(duì)較少。3.5 作者分析作者分布情況可以體現(xiàn)在該領(lǐng)域研究的廣度以及深度。作者數(shù)越多，說(shuō)明該研究領(lǐng)域越廣，某一個(gè)作者出現(xiàn)的頻次越高，說(shuō)明該作者在這個(gè)領(lǐng)域研究得比較深入。通過(guò)對(duì)搜集到的論文進(jìn)行作者分布統(tǒng)計(jì)（包含第一作者，第二作者，第三作者），共有2074位作者參與該領(lǐng)域的研究，對(duì)出現(xiàn)頻次比較高的作者進(jìn)行統(tǒng)計(jì)，列出了前18位作者，如下表。表1 軟件分析研究論文作者分布情況表（前23位）位次作者頻次1肖慶42Amp33徐寶文24張路25Alzamil, Z.A26Wei, Hua27Bruda, S.D.28De Halleus, P.29Farn, Wang210Ganai, M.K.2

20、11Jianguo, Chen212Jie, Zhang213Kroening, D.214Li, J.J.215Ling Dong216Nail, R217Tillmann, N.218Zhiping, Shi219梅宏220Landwehr, J.221趙建華222ValeriyVyatkin223姜淑娟23.6 關(guān)鍵詞分析詞頻分析法師利用能夠揭示或表達(dá)文獻(xiàn)核心內(nèi)容的關(guān)鍵詞或主題詞在某一研究領(lǐng)域文獻(xiàn)中出現(xiàn)的頻次高低來(lái)確定該領(lǐng)域研究熱點(diǎn)和發(fā)展動(dòng)向的文獻(xiàn)計(jì)量方法。為了更客觀地對(duì)軟件分析研究領(lǐng)域的研究熱點(diǎn)進(jìn)行分析，我們?cè)谒鸭降?40篇論文中進(jìn)行關(guān)鍵詞統(tǒng)計(jì)分析。我們共獲得6187個(gè)關(guān)鍵詞，對(duì)這些

21、關(guān)鍵詞進(jìn)行頻度統(tǒng)計(jì)，按照頻次高低排序所得的前31位高頻詞的統(tǒng)計(jì)結(jié)果如表2所示。表2 軟件分析研究論文詞頻統(tǒng)計(jì)情況（前31位）位次關(guān)鍵詞詞頻1Formal verification262Software testing Program testing1963Program testing1964Model checking1205Software engineering886Software877Formal specification718System testing689Computer science6710Software quality6411Program diagnostics63

22、12Program verification6213Analytical models5214Computational modeling4915testing4916Application software4917Java4718Software systems4619Programming4520Program analysis4321Software reliability4022Educational institutions3823Automata3724Software tools3625Automatic testing3426Unified modeling language3

23、427Safety3028Embedded systems3029Algorithm design and analysis3030Program debugging2931Performance analysis29統(tǒng)計(jì)結(jié)果顯示，程序分析研究在形式化驗(yàn)證，軟件測(cè)試，程序測(cè)試，模型檢測(cè)，軟件工程等方面研究比較突出。軟件分析領(lǐng)域的研究主要集中在軟件模型，軟件測(cè)試，程序分析上。4. 動(dòng)態(tài)程序分析4.1 動(dòng)態(tài)程序分析方法4.1.1 錯(cuò)誤定位為了保證軟件開(kāi)發(fā)的質(zhì)量，工業(yè)界在軟件測(cè)試階段投入了大量的人力物力，其中最耗時(shí)代價(jià)最昂貴的任務(wù)之一就是調(diào)試過(guò)程，這是指對(duì)程序錯(cuò)誤進(jìn)行定位和修正的過(guò)程，而錯(cuò)誤定位又是

24、軟件調(diào)試過(guò)程中最耗時(shí)和困難的一步。所以，錯(cuò)誤定位過(guò)程中的任何改進(jìn)都可以在一定程度上降低調(diào)試成本。經(jīng)過(guò)多年的研究發(fā)展，在軟件領(lǐng)域出現(xiàn)了很多檢測(cè)程序缺陷的技術(shù)，本文主要討論的是基于實(shí)際執(zhí)行的動(dòng)態(tài)定位技術(shù)。該技術(shù)通過(guò)對(duì)源程序、測(cè)試結(jié)果以及各種程序行為特征信息的計(jì)算分析，給出造成故障的軟件缺陷在源代碼中的可能位置，輔助開(kāi)發(fā)人員進(jìn)行程序錯(cuò)誤的定位和修改。經(jīng)過(guò)研究者們的探索，按照使用和操縱的程序執(zhí)行信息的不同，目前的錯(cuò)誤定位方法該技術(shù)可以分為3類：基于行為特征對(duì)比的方法，基于程序狀態(tài)修改的方法和基于程序依賴關(guān)系的方法3。4.1.1.1 基于行為特征對(duì)比的方法程序行為特征同時(shí)也被稱作程序光譜，是程序執(zhí)行的統(tǒng)

25、計(jì)信息。經(jīng)過(guò)Reps，Harrold等人的實(shí)驗(yàn)研究，程序出現(xiàn)異常的行為特征不一定表示代碼存在缺陷，但錯(cuò)誤的程序運(yùn)行往往會(huì)表現(xiàn)出異常的行為特征?；谛袨樘卣鲗?duì)比的方法假設(shè)失敗的測(cè)試執(zhí)行會(huì)表現(xiàn)出異常的程序行為特征，那么成功執(zhí)行和失敗執(zhí)行中的行為特征的差異就可以用于指導(dǎo)錯(cuò)誤定位。其工作流程如下：首先，根據(jù)收集信息類型的需要，對(duì)源代碼進(jìn)行插樁并執(zhí)行程序，收集執(zhí)行信息。其次，判斷每個(gè)測(cè)試用例的執(zhí)行結(jié)果。接著，解析執(zhí)行信息，得到執(zhí)行行為特征。然后，根據(jù)給定的模型，建模程序?qū)嶓w的懷疑度（可能出錯(cuò)的程度）。最后，以程序?qū)嶓w排名的方式給出定位結(jié)果，將各個(gè)程序?qū)嶓w按照懷疑度大小從大到小排列，供開(kāi)發(fā)人員查看3。目前

26、，按照使用的行為特征信息的種類和策略，大致可以分為5類：基于語(yǔ)句或基本塊，基于謂詞，基于方法，基于定義使用對(duì)或信息流以及行為特征信息精煉的方法。1) 基于語(yǔ)句或基本塊2003年，Renieres和Reiss提出NNQ（Nearest Neighbor Queries）方法，假設(shè)存在一個(gè)失敗的執(zhí)行和很多成功的執(zhí)行，然后根據(jù)距離準(zhǔn)則挑選出一個(gè)程序光譜和失敗運(yùn)行最相似的成功運(yùn)行（即失敗執(zhí)行的最近鄰居），進(jìn)而比較它們光譜的不同之處以分離軟件錯(cuò)誤。與NNQ不同，Jones 和 Harrold 提出的Tarantula法，認(rèn)為只要是主要被失敗用例執(zhí)行的程序?qū)嶓w就值得被懷疑，同時(shí)，它也能容忍出錯(cuò)的程序?qū)嶓w偶

27、爾被成功用例執(zhí)行。他們使用常用的信息來(lái)輔助錯(cuò)誤定位，包括每個(gè)測(cè)試用例的執(zhí)行結(jié)果，程序?qū)嶓w（語(yǔ)句，分支或函數(shù)等）被每個(gè)測(cè)試用例覆蓋的信息以及程序的源代碼。對(duì)于程序?qū)嶓we，它的懷疑度計(jì)算公式為：其中，failed(e)和passed(e)分別表示失敗用例和通過(guò)用例執(zhí)行程序?qū)嶓we的個(gè)數(shù)，|Tf|和|Tp|表示測(cè)試組件中所有失敗用例和通過(guò)用例的個(gè)數(shù)。e的懷疑度取值范圍從0到1，數(shù)值越大，出錯(cuò)的可能性越大。開(kāi)發(fā)人員可以按照懷疑度從大到小的順序?qū)彶樵创a。不同于NNQ和Tarantula這些基于直觀或啟發(fā)式的計(jì)算方法，Wong等人提出了一個(gè)定義良好的統(tǒng)計(jì)方法Croaatab. 它利用覆蓋信息和測(cè)試結(jié)果為每

28、條可執(zhí)行語(yǔ)句w構(gòu)建一個(gè)交叉表，進(jìn)而計(jì)算卡方統(tǒng)計(jì)量和列聯(lián)相關(guān)系數(shù)M(w)。語(yǔ)句w的懷疑度定義如下：然后，Hao等人提出應(yīng)該考慮測(cè)試用例的相似性，并消除相似的測(cè)試用例對(duì)于定位結(jié)果的影響，于是提出了一種名為SAFL（Similarity Aware Fault Localization）的方法。最后，Naish等人總結(jié)了30多種基于語(yǔ)句的定位方法，首先構(gòu)造了一段名為ITE2（If-Then-Else-2）的程序，然后在這個(gè)程序中討論各種情形。這個(gè)程序可以用于刻畫(huà)錯(cuò)誤定位中的兩種重要場(chǎng)景：存在“噪聲”和信號(hào)“微弱”。基于在ITE2代碼模型上的分析，他們提出了兩種Optimal metric, 語(yǔ)句s的

29、懷疑度定義如下：Yingqi等人結(jié)合程序切片和貝葉斯方法來(lái)實(shí)現(xiàn)錯(cuò)誤定位4。首先，我們根據(jù)切片的標(biāo)準(zhǔn)執(zhí)行動(dòng)態(tài)切片，然后根據(jù)貝葉斯理論計(jì)算后驗(yàn)概率。最后，我們把后驗(yàn)概率作為語(yǔ)句的懷疑程度按照從大到小的順序進(jìn)行排列。此方法被應(yīng)用于6個(gè)開(kāi)源項(xiàng)目，通過(guò)實(shí)驗(yàn)，此方法在一定程度上可以提高錯(cuò)誤定位的精確度。統(tǒng)計(jì)錯(cuò)誤定位技術(shù)通過(guò)執(zhí)行大量的測(cè)試用例來(lái)預(yù)測(cè)程序錯(cuò)誤的位置，相關(guān)研究表明，通過(guò)測(cè)試用例數(shù)量和失敗測(cè)試用例數(shù)量之間失衡的程度可能會(huì)降低這種技術(shù)的有效性，然而，在實(shí)踐中失敗的測(cè)試用例往往小于通過(guò)的測(cè)試用例。于是Yichao等人提出了一種策略5，通過(guò)克隆失敗測(cè)試用例適當(dāng)?shù)臄?shù)量以達(dá)到通過(guò)測(cè)試用例的數(shù)量，最終產(chǎn)生平衡

30、的測(cè)試組件。分析表明，通過(guò)開(kāi)展克隆兩個(gè)具有代表性錯(cuò)誤定位技術(shù)的有效性可以在一定條件下得到改善。隨著研究的發(fā)展，很多研究者開(kāi)始探究多故障檢測(cè)技術(shù)。Cheng，Gong等人提出了一種有效的機(jī)制用于檢測(cè)多個(gè)故障6，當(dāng)一個(gè)故障被檢測(cè)到時(shí)，我們用它來(lái)解釋我們觀察到的故障，同時(shí)更新指標(biāo)（在檢測(cè)可疑序列時(shí)的一種準(zhǔn)則），以判斷在程序中是否存留其他故障。實(shí)驗(yàn)證明這個(gè)方法不僅提高了單故障定位器的效率，同時(shí)在很大程度上避免了放棄單故障檢測(cè)器而開(kāi)發(fā)多故障檢測(cè)器時(shí)的無(wú)效的工作與努力。針對(duì)動(dòng)態(tài)程序切片，Hofer等人提出了一種技術(shù)7，可以減少包含在動(dòng)態(tài)切片中的語(yǔ)句數(shù)目，這種技術(shù)是基于約束的計(jì)算，并且允許從不太可能是錯(cuò)誤的

31、根本原因的切片中移除語(yǔ)句。實(shí)驗(yàn)結(jié)果表明，在有關(guān)切片中得到的片段的數(shù)量，平均降幅超過(guò)28%。由于測(cè)試覆蓋信息不能識(shí)別那些程序?qū)嶓w，而這些實(shí)體的執(zhí)行影響了輸出，于是便削弱了實(shí)體之間的相關(guān)性。Yan，Lei等人為解決這個(gè)問(wèn)題8，提出了一項(xiàng)新的統(tǒng)計(jì)故障定位技術(shù)。該統(tǒng)計(jì)方法是利用一組測(cè)試運(yùn)行的程序切片來(lái)捕捉在輸出結(jié)果中程序?qū)嶓w執(zhí)行的影響，并且利用統(tǒng)計(jì)分析來(lái)衡量程序?qū)嶓w故障的可疑度。此外，他們還提出了一種近似后向動(dòng)態(tài)切片的新切片方法，以此來(lái)平衡切片的尺寸和精度，并將此切片方法應(yīng)用于統(tǒng)計(jì)方法。實(shí)驗(yàn)表明，在兩個(gè)標(biāo)準(zhǔn)的基準(zhǔn)測(cè)試下，我們的統(tǒng)計(jì)方法明顯優(yōu)于其他8個(gè)具有代表性的故障定位方法。2) 基于謂詞Liblit

32、和他的同事提出了CBI（Cooperative Bug Isolation）技術(shù)，用于定位已部署軟件中的錯(cuò)誤。基本思想是搜集用戶在使用軟件過(guò)程中產(chǎn)生的執(zhí)行信息，進(jìn)而通過(guò)分析這些數(shù)據(jù)將軟件缺陷分離出來(lái)。然后，在搜集這些執(zhí)行信息的同時(shí)，會(huì)對(duì)用戶使用的軟件性能有一定的影響，為了解決這個(gè)問(wèn)題，Liblite等人通過(guò)在源代碼上的變換，使用稀疏的隨機(jī)抽樣，較好地控制了客戶端的性能并返回執(zhí)行時(shí)的摘要信息。盡管CBI技術(shù)能夠從廣泛的系統(tǒng)中識(shí)別出一些錯(cuò)誤，但它只考慮了那些在失敗執(zhí)行中取值為真的謂詞，而對(duì)于一個(gè)總是取值為真的謂詞，CMI技術(shù)就喪失了它的判斷能力。Liu等人對(duì)謂詞在成功執(zhí)行和失敗執(zhí)行中的取值模式進(jìn)行

33、建模，然后基于統(tǒng)計(jì)學(xué)中假設(shè)檢驗(yàn)的原理，量化每個(gè)謂詞的錯(cuò)誤相關(guān)性，建立了SOBER方法。一個(gè)謂詞P的取值偏差在成功和失敗執(zhí)行中的差異越大，則謂詞P出錯(cuò)的可能性越大。令Y表示謂詞P的取值偏差在所有失敗執(zhí)行中的均值。SOBER使用如下公式計(jì)算P的懷疑度：其中，sp為謂詞P在所有成功執(zhí)行中謂詞的取值偏差的方差，Z是Y的標(biāo)準(zhǔn)化隨機(jī)變量。開(kāi)發(fā)者可以根據(jù)謂詞的懷疑度的大小審查源代碼，發(fā)現(xiàn)錯(cuò)誤的位置。然后，Zhang等人研究了短路求值和求值序列對(duì)于錯(cuò)誤定位技術(shù)的影響。他提出了一種基于謂詞的定位方法的改進(jìn)策略：DES（Debugging through Evaluation Sequences）策略，將每個(gè)謂詞

34、排名最高的取值序列作為該謂詞的排名，實(shí)驗(yàn)表明，DES可以提高基于謂詞的錯(cuò)誤定位技術(shù)的有效性而同時(shí)僅產(chǎn)生較小的額外性能開(kāi)銷。Zunwen，You等人提出了一項(xiàng)新的統(tǒng)計(jì)方法9，該方法是通過(guò)探測(cè)兩個(gè)在執(zhí)行過(guò)程中順序連接的謂詞的統(tǒng)計(jì)行為。如果謂詞被視為一個(gè)圖的頂點(diǎn)，那么這個(gè)圖的邊則表示程序在執(zhí)行過(guò)程軌跡中兩個(gè)順序連接謂詞的過(guò)渡。每個(gè)邊的標(biāo)簽代表每個(gè)轉(zhuǎn)變的頻率。對(duì)于每條邊，我們應(yīng)用假設(shè)檢驗(yàn)來(lái)評(píng)價(jià)在通過(guò)運(yùn)行邊緣評(píng)估偏倚和失敗運(yùn)行邊緣評(píng)估偏倚之間的差異。邊緣是根據(jù)從假設(shè)檢驗(yàn)中得到的故障相關(guān)程度來(lái)排列的。實(shí)驗(yàn)證明，我們提出的基于謂詞的故障定位技術(shù)優(yōu)于其他適當(dāng)運(yùn)用統(tǒng)計(jì)的故障定位技術(shù)。3) 基于方法對(duì)于面向?qū)ο蟮?/p>

35、語(yǔ)言，Dallmeier等人提出了基于方法調(diào)用序列的Ample技術(shù)，認(rèn)為只出現(xiàn)在通過(guò)執(zhí)行或失敗執(zhí)行中的方法調(diào)用子序列都應(yīng)該被懷疑。與在通過(guò)或失敗執(zhí)行中出現(xiàn)的子序列相比，這些子序列被分配較大的懷疑度值，遺失或增添的子序列都值得懷疑，因?yàn)樗鼈兌伎赡芤l(fā)程序故障。與Ample技術(shù)不同，Yilmaz等人提出使用時(shí)間光譜作為程序執(zhí)行的抽象。時(shí)間光譜是指程序?qū)嶓w（方法，函數(shù)等）運(yùn)行的時(shí)間特征信息，通常用于程序性能的評(píng)價(jià)和優(yōu)化。他們提出一種叫做TWT（Time Will Tell）的方法，首先收集成功執(zhí)行和失敗執(zhí)行的時(shí)間光譜，接著基于成功執(zhí)行的時(shí)間光譜建立程序行為模型，然后使用這個(gè)模型來(lái)識(shí)別失敗執(zhí)行和成功執(zhí)

36、行的偏離程度。SFL（Spectrum-based Fault Localization）是一種輕量級(jí)的自動(dòng)診斷技術(shù)，然而當(dāng)它應(yīng)用于面向?qū)ο蟪绦驎r(shí)，它的診斷精確度由于可疑語(yǔ)句被分布到不同的類中而受到限制，于是，Jingxuan，Tu等人提出了一種方法，利用方法調(diào)用異常來(lái)提高SFL技術(shù)在面向?qū)ο蟪绦蛑泄收隙ㄎ坏挠行?。其過(guò)程如下：首先，基于在通過(guò)和失敗運(yùn)行中方法調(diào)用序列的差異來(lái)計(jì)算每個(gè)類的可疑度；然后，利用每個(gè)類的可疑信息細(xì)化SFL可疑度序列，以提高面向?qū)ο筌浖收隙ㄎ坏男?。?shí)驗(yàn)表明，該方法能夠提高SFL技術(shù)的有效性。4) 基于定義使用對(duì)、分支或信息流Santelices等人認(rèn)為有些缺陷最好使

37、用語(yǔ)句覆蓋信息來(lái)定位，而有些最好使用分支或者定義使用對(duì)的覆蓋信息。首先需要計(jì)算一個(gè)程序?qū)嶓w的懷疑度，然后對(duì)于分支或者定義使用對(duì)，根據(jù)3條規(guī)則，將每條語(yǔ)句的可疑度定義為和它關(guān)聯(lián)的分支或定義使用對(duì)可疑度的最高值。然后采用max-SBD，avg-SBD和avg-BD 3種策略來(lái)獲得一個(gè)語(yǔ)句的可疑度得分。即是說(shuō)一個(gè)語(yǔ)句的可疑度得分可以是和它關(guān)聯(lián)的3種程序?qū)嶓w懷疑度得最大值，平均值或只是定義為和它關(guān)聯(lián)的分支和定義使用對(duì)懷疑度得平均值。實(shí)驗(yàn)表明，綜合使用多種覆蓋類型的信息，確實(shí)可以提高錯(cuò)誤定位技術(shù)的有效性。與Santelices等人提出的使用單一模型建模程序?qū)嶓w不同，Yu等人進(jìn)一步提出一個(gè)使用多個(gè)模型來(lái)捕

38、捉不同類型的錯(cuò)誤的方法LOUPE。假設(shè)對(duì)于任一類型的錯(cuò)誤，存在一種適合模型，它能夠較好識(shí)別出錯(cuò)誤語(yǔ)句，由于錯(cuò)誤類型事先未知，LOUPE方法建立了多個(gè)模型來(lái)捕捉語(yǔ)句的異常行為，并試圖選出相應(yīng)的適合模型。動(dòng)態(tài)信息流分析師一種更加重量級(jí)的方法，它考慮5種類型的依賴關(guān)系：動(dòng)態(tài)直接控制依賴，動(dòng)態(tài)直接數(shù)據(jù)依賴和3種過(guò)程間的依賴關(guān)系。由于動(dòng)態(tài)信息流分析能夠識(shí)別運(yùn)行時(shí)對(duì)象之間的信息流，所以也可以用來(lái)建模程序元素之間復(fù)雜的交互作用，于是Masri提出了一種基于動(dòng)態(tài)信息流分析的錯(cuò)誤定位方法。對(duì)于信息流f，懷疑度計(jì)算公式如下：然后，每條可執(zhí)行語(yǔ)句被賦予流經(jīng)它的懷疑度最大的信息流的值。并且，值得懷疑的信息流的源語(yǔ)句應(yīng)

39、該先于這條信息流上的其他語(yǔ)句被檢查。5) 行為特征信息的精煉由于受到很多因素的影響，在實(shí)踐中，基于行為特征對(duì)比的方法的有效性仍然會(huì)受到限制。Masri等人通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)了這類方法有效性下降的四個(gè)場(chǎng)景：錯(cuò)誤條件滿足，但程序故障并未出現(xiàn)（作者成為巧合正確性）；錯(cuò)誤語(yǔ)句被執(zhí)行，但程序故障并未出現(xiàn)（作者稱為弱巧合正確性）；程序故障和不止一個(gè)的不同類型的程序元素的組合有關(guān)；以及很多程序元素不在通過(guò)程序中出現(xiàn)，卻出現(xiàn)在所有的失敗執(zhí)行中。前三個(gè)場(chǎng)景可能會(huì)影響錯(cuò)誤定位技術(shù)的準(zhǔn)確性，后一個(gè)會(huì)影響精確性。為了進(jìn)一步提高定位技術(shù)的有效性，研究者提出了不同的精煉方法來(lái)減少各種因素的影響。針對(duì)弱巧合正確性，Wang等人受

40、后向動(dòng)態(tài)切片的啟發(fā)，將與程序輸出結(jié)果無(wú)關(guān)的實(shí)體的覆蓋信息去除，以精煉程序輸出特征。由于以上錯(cuò)誤定位技術(shù)只關(guān)注與評(píng)估單個(gè)的程序?qū)嶓w的懷疑度，而忽略了被感染的程序狀態(tài)在它們之間的傳播，于是Zhang等人提出使用控制流邊的信息來(lái)表示成功執(zhí)行和失敗執(zhí)行，然后比較它們的差異來(lái)建模每個(gè)基本塊對(duì)于程序故障的貢獻(xiàn)程度。由于基于頻譜定位技術(shù)中故障類型和數(shù)量，測(cè)試組件的質(zhì)量比較敏感，Gopinath等人10提出了一種新的技術(shù)，該技術(shù)應(yīng)用于基于光譜的協(xié)同規(guī)范分析，以更準(zhǔn)確地定位故障。他們的觀點(diǎn)是違反規(guī)范的不可滿足性分析，可被用于計(jì)算包含可能故障語(yǔ)句的不可滿足核心和生成有助于基于光譜的定位技術(shù)的測(cè)試用例。此方法是迭代

41、的，并且可以通過(guò)反饋回路獲取更加精確的故障定位。SAT-TAR是體現(xiàn)了我們這個(gè)技術(shù)針對(duì)Java程序的一個(gè)框架，并且包含了多故障檢測(cè)技術(shù)。實(shí)驗(yàn)證明，此項(xiàng)技術(shù)比state of the art方法更加準(zhǔn)確。4.1.1.2 基于程序狀態(tài)修改的方法基于程序狀態(tài)修改的方法通常是在程序執(zhí)行時(shí)獲得并修改程序的狀態(tài)，然后觀察修改后的測(cè)試結(jié)果，進(jìn)而找出對(duì)測(cè)試結(jié)果有影響的關(guān)鍵謂詞或語(yǔ)句。由于程序運(yùn)行時(shí)的狀態(tài)有多種可能性，所以這類方法經(jīng)常需要采取一些簡(jiǎn)化策略來(lái)提高錯(cuò)誤定位的效率。Delta Debugging方法是由Zeller提出的一種能自動(dòng)縮小程序的成功運(yùn)行過(guò)程和失敗運(yùn)行過(guò)程之間區(qū)別的技術(shù)。它采用分治思想，把軟

42、件配置（測(cè)試輸入，源程序等）變動(dòng)的集合進(jìn)行劃分，然后分別進(jìn)行測(cè)試。然后遞歸地把導(dǎo)致失敗配置的集合并入結(jié)果為通過(guò)配置的集合。這樣逐漸減小兩個(gè)集合之間的差異，最終確認(rèn)成功配置和失敗配置差別的一個(gè)最小集。2005年，此方法被應(yīng)用到程序狀態(tài)上，自動(dòng)化找出導(dǎo)致程序失敗的語(yǔ)句。改變分支的取值結(jié)果是改變運(yùn)行時(shí)變量的值的一種特殊情形。Jeffrey等人提出了Value Replacement方法：首先嘗試改變運(yùn)行時(shí)變量的值以得到成功用例，進(jìn)而將這種信息用于錯(cuò)誤定位。然后將使用的值替換成另外一個(gè)，并觀察是否會(huì)產(chǎn)生正確結(jié)果。Feng Li等人提出了一種新的基于狀態(tài)的錯(cuò)誤定位方法DelFal11。假設(shè)執(zhí)行軌跡的可用

43、性導(dǎo)致報(bào)告的程序執(zhí)行失敗，這種新方法依次選擇設(shè)置跟蹤點(diǎn)以便對(duì)程序執(zhí)行狀態(tài)高效自動(dòng)的探索來(lái)幫助開(kāi)發(fā)人員找到編程所觀察到的執(zhí)行失敗。每個(gè)這樣的集合跟蹤點(diǎn)，在每個(gè)軌跡點(diǎn)的程序狀態(tài)被象征性地改變。通過(guò)否定每種原子謂詞，去觀察同樣的故障是否發(fā)生在從源代碼中相應(yīng)的程序點(diǎn)符號(hào)執(zhí)行繼續(xù)進(jìn)行。這組跟蹤點(diǎn)是備選集合中的最小程序狀態(tài)集，這樣一組跟蹤點(diǎn)被稱為最小調(diào)試邊界集MDFS（Minimum Debugging Frontier Set）。根據(jù)符號(hào)執(zhí)行的結(jié)果，下一個(gè)MDFS是根據(jù)向前或向后移動(dòng)剩余程序軌跡而確定的。當(dāng)故障代碼被發(fā)現(xiàn)時(shí)，軌跡跟蹤過(guò)程會(huì)被縮短并繼續(xù)進(jìn)行下去。MDFS方法需要被提供執(zhí)行失敗的位置，但所需

44、的程序狀態(tài)的規(guī)范是可選的。有了這樣的規(guī)范，它可以實(shí)現(xiàn)更加精確的錯(cuò)誤報(bào)告。實(shí)驗(yàn)證明此方法在合理的時(shí)間內(nèi)可以有效的解釋故障。4.1.1.3 基于程序依賴關(guān)系的方法基于程序依賴關(guān)系的方法側(cè)重于使用程序的動(dòng)態(tài)依賴關(guān)系給出值得懷疑的語(yǔ)句的集合。這個(gè)集合包含錯(cuò)誤語(yǔ)句和調(diào)試上下文，由于這個(gè)集合通常會(huì)包含一些冗余的語(yǔ)句，所以需要使用一個(gè)技術(shù)來(lái)簡(jiǎn)化。Zhang等人從動(dòng)態(tài)角度提出隱式依賴（implicit dependence ）的概念，它只會(huì)將已經(jīng)觀測(cè)到的發(fā)生在謂詞和變量使用上的依賴關(guān)系加入切片中。進(jìn)一步，他們使用一種需求驅(qū)動(dòng)的策略來(lái)減小探測(cè)隱式依賴的開(kāi)銷。為了減小動(dòng)態(tài)切片的規(guī)模，研究著提出了許多種簡(jiǎn)化策略。G

45、upta等人整合了Delta Debugging技術(shù)來(lái)識(shí)別一個(gè)最小的故障相關(guān)的輸入，然后基于這個(gè)輸入計(jì)算動(dòng)態(tài)前向切片并以錯(cuò)誤輸出為準(zhǔn)則產(chǎn)生的動(dòng)態(tài)后向切片取交集，作為引發(fā)故障的砍片（chop）。Baah等人擴(kuò)展了程序依賴圖，通過(guò)測(cè)試用例的執(zhí)行信息估計(jì)節(jié)點(diǎn)間的統(tǒng)計(jì)依賴，建立了程序依賴圖PPDG（Probabilistic Program Dependence Graph）。它是基于概率圖模型的框架，首先產(chǎn)生依賴圖，然后得到標(biāo)記了子節(jié)點(diǎn)和父節(jié)點(diǎn)之間條件概率的變換程序依賴圖。與此同時(shí)，插樁源程序得到測(cè)試用例的執(zhí)行信息，通過(guò)學(xué)習(xí)執(zhí)行信息中的數(shù)據(jù)，最終得到PPDG。與PPDG不同，F(xiàn)eng和Gupta為每

46、種指令類型建立了通用模型。給定一組程序的執(zhí)行軌跡，并包括至少一個(gè)成功執(zhí)行和至少一個(gè)失敗執(zhí)行，可以基于動(dòng)態(tài)依賴圖建立基于貝葉斯網(wǎng)絡(luò)的錯(cuò)誤流圖（Error Flow Graph）和通用的概率模型。然后使用標(biāo)準(zhǔn)的推理算法從業(yè)節(jié)點(diǎn)沿著錯(cuò)誤流后向追溯尋找錯(cuò)誤可能性最大的可執(zhí)行語(yǔ)句。一種常用的定位錯(cuò)誤的方法是根據(jù)通過(guò)執(zhí)行和失敗執(zhí)行來(lái)計(jì)算程序塊的可疑度，但這種技術(shù)并沒(méi)有完全考慮到程序塊之間的以來(lái)關(guān)系，因此錯(cuò)誤定位的能力受到了限制。Wanzhi，Wen等人經(jīng)過(guò)研究12，打算利用程序切片技術(shù)和統(tǒng)計(jì)方法，該統(tǒng)計(jì)方法是從程序塊之間提取它們之間依賴關(guān)系并且喜歡它們的執(zhí)行歷史。然后根據(jù)統(tǒng)計(jì)方法對(duì)可疑程序塊進(jìn)行排序，并建

47、立一個(gè)程序切片譜。我們期望的是這個(gè)方法能夠直接促進(jìn)軟件故障定位有效性和精確度的改進(jìn)，從而減少軟件開(kāi)發(fā)和維護(hù)的成本。4.1.1.4 其他方法Wong等人提出了一種名為DStar（D*）的技術(shù)13，它可以自動(dòng)提示進(jìn)行錯(cuò)誤定位的可疑位置而不需要任何程序結(jié)構(gòu)或語(yǔ)義的先驗(yàn)信息。通過(guò)實(shí)驗(yàn)，DStar（D*）方法在24個(gè)程序錯(cuò)誤定位中，與其他38種不同的錯(cuò)誤定位技術(shù)相比，無(wú)論是單故障還是多故障，它都是最有效的。實(shí)驗(yàn)同時(shí)也表明，DStar（D*）方法隨著指數(shù)*的有效性增加，逐漸達(dá)到一個(gè)平穩(wěn)狀態(tài)。Yan Lei等人提出了一種名為BSSFL（Backward-Slice-based Statistical Fau

48、lt Localization）的錯(cuò)誤定位方法14。該方法假定測(cè)試預(yù)言存在來(lái)確定測(cè)試用例的結(jié)果是否是失敗或通過(guò)，但由于在現(xiàn)實(shí)中，測(cè)試預(yù)言并不總是存在，因此在這種情況下BSSFL是不可行的。在目前的研究中，變質(zhì)測(cè)試已被廣泛研究，以緩解測(cè)試預(yù)言問(wèn)題，因此，我們利用變質(zhì)測(cè)試進(jìn)行BSSFL。在此過(guò)程中，我們用后向切片和違反或不違反變質(zhì)測(cè)試組，而不是后向切片和失敗或通過(guò)的單個(gè)測(cè)試用例。此方法不需要測(cè)試用例的執(zhí)行結(jié)果，所以它可以擴(kuò)展到?jīng)]有測(cè)試預(yù)言存在的領(lǐng)域。實(shí)驗(yàn)表明，我們提出的方法在測(cè)試預(yù)言存在的情況下較現(xiàn)有的BSSFL技術(shù)效率更高。最近的研究表明，利用因果推斷技術(shù)來(lái)減少混雜偏倚以提高統(tǒng)計(jì)錯(cuò)誤定位（SFL

49、）在程序語(yǔ)句水平的有效性，然而由于非常大的程序和測(cè)試組件，會(huì)造成一定的影響，為降低影響，Gang Shu等人提出并評(píng)估了一種新的方法級(jí)SFL技術(shù)MFL15，該技術(shù)基于因果推斷，并采用了新的算法來(lái)選擇協(xié)變量以調(diào)節(jié)混雜偏倚的使用。同時(shí)，試圖確保這樣的協(xié)變量滿足能夠識(shí)別觀測(cè)數(shù)據(jù)的因果效應(yīng)的條件可交換性和積極性。實(shí)驗(yàn)表明，我們的方法比知名的SFL方法更有效，并且，我們的混雜因素選擇算法優(yōu)于兩種選擇。近來(lái)，隨著人工智能的快速發(fā)展，基于人工智能理論的故障診斷技術(shù)吸引了越來(lái)越多人的注意。Guoshun，Chen等人16認(rèn)為MAS（Multi-Agent Sysytem）具有較強(qiáng)的自主性，智能性和社會(huì)能力，很

50、適合用于診斷軟件系統(tǒng)，并很容易與現(xiàn)軟件密集型裝備現(xiàn)有的軟件測(cè)試方案進(jìn)行集成。于是，他們提出了一種新的基于MAS的故障診斷框架，此框架已應(yīng)用與真正的軟件診斷當(dāng)中，并且證明了它的有效性。（需要詳細(xì)列出這個(gè)四層框架）Roychowdhury等人提出了一種新的方法17，該方法基于伯努利分歧來(lái)自動(dòng)定位故障，所以，該方法是從信息論和機(jī)器學(xué)習(xí)中西吸取的概念，并將它應(yīng)用于軟件工程。經(jīng)過(guò)初步的實(shí)驗(yàn)研究，表明此方法給故障定位技術(shù)帶來(lái)了希望。Xiaomin，Wang等人18為了解決現(xiàn)有定位技術(shù)的限制性，提出了一種新的技術(shù)，建立一種新的行為模型，并提出相應(yīng)的故障定位技術(shù)。實(shí)驗(yàn)表明，這項(xiàng)新技術(shù)優(yōu)于其他SBFL故障定位技

51、術(shù)，并且，我們發(fā)現(xiàn)，這項(xiàng)技術(shù)的有效性來(lái)自于分層行為模型的指導(dǎo)。雖然基于頻譜的貝葉斯推理可以有效地根據(jù)通過(guò)/失敗測(cè)試案例來(lái)排列候選故障位置，但是診斷質(zhì)量高度依賴于地層測(cè)試組件的規(guī)模和多樣性。由于在實(shí)踐中測(cè)試組件通常不表現(xiàn)出必要的屬性，據(jù)此，Gampos等人19提出了一種技術(shù)用新的能夠優(yōu)化診斷質(zhì)量的測(cè)試案例來(lái)擴(kuò)展現(xiàn)有的測(cè)試組件。我們運(yùn)用概率理論概念中的熵來(lái)指導(dǎo)測(cè)試用例生成，使得在診斷排名中的不確定量達(dá)到最小化。我們的ENTBUG原型擴(kuò)展了基于搜索的測(cè)試用例生成工具EVOSUITE使用熵在其潛在的遺傳算法的實(shí)用度函數(shù)，我們將此技術(shù)應(yīng)用到了7個(gè)真正的故障定位當(dāng)中，實(shí)驗(yàn)結(jié)果表明，相對(duì)使用原始的測(cè)試組件，

52、該方法在診斷排名的熵上平均下降了49%，從而導(dǎo)致在尋找真正故障時(shí)下降了91%的檢查幅度。De Souza, H.A等人20提出了一項(xiàng)新的技術(shù)，該技術(shù)使用整合覆蓋數(shù)據(jù)來(lái)指導(dǎo)故障定位過(guò)程。通過(guò)排序的方法調(diào)用可疑對(duì)，被調(diào)查的路線排序方法列表隨之被創(chuàng)建。在每個(gè)方法中，單元覆蓋被用于定位故障。實(shí)驗(yàn)對(duì)4個(gè)包含了2000到80000行代碼中的55個(gè)BUG進(jìn)行了分析，結(jié)果表明，通過(guò)使用路線圖，故障定位過(guò)程的有效性得到了明顯提高：固定基本塊中的78%的故障被定為成功，比Tarantula技術(shù)高出40%。4.1.2 算法檢測(cè)在眾多的軟件系統(tǒng)和應(yīng)用中，許多被檢測(cè)到的缺陷都是由于程序設(shè)計(jì)或低效的編碼造成的。4.1.2

53、.1 冗余計(jì)算（Redundant Computation）冗余計(jì)算在軟件程序中是一種普遍發(fā)生的現(xiàn)象，在多數(shù)情況下，它是軟件缺陷發(fā)生的根源，消除冗余計(jì)算不僅可以提高程序性能，而且還能識(shí)別軟件程序中的潛在錯(cuò)誤。冗余計(jì)算在多數(shù)情況下都是由于程序算法設(shè)計(jì)的不足所造成的，針對(duì)這個(gè)問(wèn)題，Zakarya,A.Alzamil 21提出了一種動(dòng)態(tài)方法來(lái)理解程序的動(dòng)態(tài)行為。該方法能夠識(shí)別執(zhí)行程序語(yǔ)句中沒(méi)有輸出的計(jì)算，這些計(jì)算就被成為冗余計(jì)算。這種冗余計(jì)算能夠指導(dǎo)開(kāi)發(fā)者識(shí)別潛在的算法問(wèn)題。在他的實(shí)驗(yàn)中，通過(guò)RCAT (Redundant Computation Analysis Tool )搜索工具檢測(cè)C程序當(dāng)中

54、的冗余計(jì)算并且識(shí)別與冗余計(jì)算相關(guān)的潛在缺陷。表3-Initial Experiment Result表3所顯示的就是作者實(shí)驗(yàn)的結(jié)果，通過(guò)實(shí)驗(yàn)結(jié)果，我們可以看出，此方法可以幫助開(kāi)發(fā)者檢測(cè)冗余計(jì)算，并且指導(dǎo)開(kāi)發(fā)者提高程序的算法，開(kāi)發(fā)更加健壯的程序軟件。4.1.3 數(shù)據(jù)檢測(cè)類4.1.3.1 浮點(diǎn)數(shù)精度問(wèn)題（Floating-Point Accuracy Problems）在程序中使用浮點(diǎn)數(shù)，很容易造成舍入或?yàn)?zāi)難性取消等精度問(wèn)題。然而這些現(xiàn)象引發(fā)的錯(cuò)誤難以追查：程序不一定崩潰，程序結(jié)果不一定是顯然錯(cuò)誤的，但往往是有細(xì)微的錯(cuò)誤存在，如果開(kāi)發(fā)者進(jìn)一步使用這些值，就可能會(huì)造成災(zāi)難性的錯(cuò)誤。Florian等人

55、針對(duì)浮點(diǎn)數(shù)問(wèn)題，提出了一種支持程序員發(fā)現(xiàn)精度問(wèn)題的動(dòng)態(tài)程序分析方法22。他們使用二進(jìn)制轉(zhuǎn)換，將浮點(diǎn)數(shù)轉(zhuǎn)換到更高的精度，此外，還是用輕量級(jí)切片方法來(lái)追蹤錯(cuò)誤評(píng)估。他們通過(guò)捕獲到的比較典型的浮點(diǎn)數(shù)問(wèn)題和分析SPECFP2006浮點(diǎn)數(shù)基準(zhǔn)來(lái)評(píng)估我們的分析。在后者中，我們會(huì)通過(guò)工具來(lái)追尋一個(gè)災(zāi)難性的取消是如何導(dǎo)致精度完全失效進(jìn)而引發(fā)的毫無(wú)意義的一個(gè)結(jié)果。在試驗(yàn)中，他們利用VDBIF（Valgrind Dynamic Binary Instrumentation Framework）框架來(lái)執(zhí)行實(shí)驗(yàn)的分析并且將它運(yùn)用到大規(guī)模的基準(zhǔn)程序中。分析結(jié)果顯示，我們的分析能夠幫助開(kāi)發(fā)者追蹤和修正浮點(diǎn)數(shù)精度問(wèn)題。圖-

56、Result of the SPECFP2006 benchmarks with the “test” data sets4.2 動(dòng)態(tài)程序分析工具最近的研究表明，矛盾、重復(fù)或嘈雜的光譜可能影響SBFL指標(biāo)排名的準(zhǔn)確性，Danel等人23據(jù)此提出并開(kāi)發(fā)了一種新的SBFL工具，該工具可以通過(guò)測(cè)試用例預(yù)處理過(guò)濾掉矛盾，重復(fù)或其他嘈雜的光譜。實(shí)驗(yàn)表明，該帶有測(cè)試用例預(yù)處理的SBFL工具已經(jīng)成功改善了SBFL指標(biāo)在大多數(shù)研究中的性能。4.3 動(dòng)態(tài)程序分析在軟件測(cè)試中的應(yīng)用5. 未來(lái)研究展望作為軟件技術(shù)研究領(lǐng)域的核心內(nèi)容之一，動(dòng)態(tài)程序分析技術(shù)隨著軟件技術(shù)的發(fā)展而處于不斷發(fā)展之中，并受到如下幾個(gè)方面的推動(dòng)：

57、程序錯(cuò)誤定位新理論和新技術(shù)的引入與集成、程序算法檢測(cè)新的發(fā)展形態(tài)、軟件運(yùn)行平臺(tái)的新發(fā)展等等。5.1 錯(cuò)誤定位新理論和新技術(shù)的引入與集成1) 測(cè)試組件（test suite）的影響測(cè)試組件的組成會(huì)對(duì)錯(cuò)誤定位技術(shù)的有效性產(chǎn)生影響。當(dāng)前的錯(cuò)誤定位技術(shù)通常假設(shè)測(cè)試用例集滿足測(cè)試充分性準(zhǔn)則，足以滿足錯(cuò)誤定位的需要2) 多個(gè)缺陷的定位3) 定位結(jié)果的理解4) 錯(cuò)誤修復(fù)的建議5.2 程序算法檢測(cè)新的發(fā)展形態(tài)5.3 軟件運(yùn)行平臺(tái)的新發(fā)展6. 結(jié)束語(yǔ)本文從錯(cuò)誤定位、算法檢測(cè)、數(shù)據(jù)監(jiān)測(cè)等方面對(duì)動(dòng)態(tài)程序分析技術(shù)進(jìn)行歸納總結(jié)，并對(duì)未來(lái)的研究趨勢(shì)進(jìn)行展望。動(dòng)態(tài)程序分析在過(guò)去幾十年間取得了很大的進(jìn)步，研究者們貢獻(xiàn)了巨大的力量，但仍有很多問(wèn)題需要進(jìn)一步的深入研究。在錯(cuò)誤定位方面，例如缺乏用