軟件故障定位

1、傳統(tǒng)調(diào)試技術(shù)軟件開發(fā)者使用的典型的軟件調(diào)試技術(shù)主要有兩種：(1)在程序中插入打印語句使得程序輸出用以被分析的附加信息，可以對(duì)程序的運(yùn)行時(shí)狀態(tài)有一個(gè)粗略了解。一個(gè)通常的做法是插入打印語句以指 示某個(gè)控制條件到達(dá)了某個(gè)特定程序點(diǎn)；另一個(gè)通常做法是插入打印語 句以輸出變量的值。當(dāng)程序被執(zhí)行的時(shí)候，程序生成可以被開發(fā)者檢查的 附加調(diào)試輸出。缺點(diǎn)：調(diào)試輸出可能相當(dāng)?shù)拇?，打印語句的放置和輸出的 檢查都是非組織和臨時(shí)的,分析和放置位置也通常是基于直覺的(2)另一種技術(shù)是使用符號(hào)調(diào)試器。一個(gè)符號(hào)調(diào)試器是一個(gè)用來調(diào)試其他程序的計(jì)算機(jī)程序，符號(hào)調(diào)試器支持例如斷點(diǎn)、單步跳過、狀態(tài)修改等。斷 點(diǎn)允許程序員停止在某一個(gè)

2、特定的程序點(diǎn)以檢查當(dāng)前狀態(tài)；單步跳過允許程序員前進(jìn)到當(dāng)前斷點(diǎn)之后的下一條指令，并且在那條指令設(shè)置新的 斷點(diǎn)；許多調(diào)試器還允許程序員不僅能夠查看變量的當(dāng)前狀態(tài) ，還能改變 它的值然后繼續(xù)執(zhí)行。通常地，開發(fā)者會(huì)在他感覺可能是程序錯(cuò)誤位置的 地方設(shè)置斷點(diǎn)，然后他會(huì)檢查斷點(diǎn)處的狀態(tài)，他還可以單步跳過程序查看 每一條語句在每一個(gè)執(zhí)行時(shí)的狀態(tài)變化。主要的定位方法故障定位技術(shù)有很多種，但是根據(jù)定位故障的過程中“是否需要運(yùn)行軟件 的準(zhǔn)那么，可以將故障定位技術(shù)分為以下兩類：(1)基于靜態(tài)分析的故障定位技術(shù)(SABFL):靜態(tài)方法不用運(yùn)行軟件，而是依據(jù) 程序語言的語法和語義，靜態(tài)地分析軟件結(jié)構(gòu)和程序?qū)嶓w之間的依賴

3、關(guān)系 ，以發(fā) 現(xiàn)不符合系統(tǒng)約束的程序?qū)嶓w，從而進(jìn)行故障定位。(2)基于測(cè)試的故障定位技術(shù)(TBFL):該方法首先需要設(shè)計(jì)測(cè)試用例，然后運(yùn) 行軟件程序，最后根據(jù)軟件程序的動(dòng)態(tài)執(zhí)行信息和輸出結(jié)果進(jìn)行故障定位。其典 型思路是：將程序的失敗運(yùn)行和成功運(yùn)行進(jìn)行比照，從而發(fā)現(xiàn)失敗運(yùn)行中的哪些 點(diǎn)偏離了成功運(yùn)行，找到的這些偏離點(diǎn)很有可能就是軟件故障位置所在。這些不 同定位方法都采用了各自不同的運(yùn)行特征進(jìn)行比照。以下是基于測(cè)試的故障定位技術(shù)：(一)基于距離度量的故障定位方法：根本思想是：通過一定的距離計(jì)算方法，從眾多的成功運(yùn)行中找出與失敗運(yùn) 行最相近的一個(gè)成功運(yùn)行，利用某一種度量方法來計(jì)算此成功運(yùn)行與失敗運(yùn)行

4、之 間的差異值，利用得出的最小差異值進(jìn)行故障定位。該技術(shù)大都是在源程序上運(yùn) 行大量的測(cè)試用例，并收集程序運(yùn)行過程中的覆蓋信息，利用這些信息來進(jìn)行故 障定位。此方法包括(1) Delta調(diào)試技術(shù)把一次程序執(zhí)行看做是一系列程序狀態(tài)的轉(zhuǎn)變(程序狀態(tài)可以理解為在程序 執(zhí)行某個(gè)時(shí)刻出現(xiàn)的變量以及這些變量的取值 )。程序從初始狀態(tài)開始執(zhí)行，每執(zhí) 行一步，程序當(dāng)前狀態(tài)就會(huì)發(fā)生改變，從當(dāng)前狀態(tài)轉(zhuǎn)換到下一個(gè)程序狀態(tài)，如此進(jìn) 行，最后到達(dá)了個(gè)錯(cuò)誤的狀態(tài)，標(biāo)志著程序執(zhí)行失敗。每一個(gè)程序狀態(tài)都它的前一 個(gè)狀態(tài)衍生而來，但是，可能只有一小局部狀態(tài)與計(jì)算下一個(gè)狀態(tài)是相關(guān)的 ，同理， 也并不是所有程序狀態(tài)都與執(zhí)行失敗相關(guān)。

5、Delta調(diào)試最重要的步驟就是找出與程序執(zhí)行失敗相關(guān)的那些狀態(tài)，得到一條原 因-結(jié)果鏈。比擬一次成功執(zhí)行和一次失敗執(zhí)行的狀態(tài)序列,它們之間的差異就是 一條原因-結(jié)果鏈。采用二分法將原因-結(jié)果鏈上的狀態(tài)應(yīng)用到成功的執(zhí)行路徑中 如果運(yùn)行成功,就表示那一局部代碼不存在故障,否那么，那局部代碼可能是可疑的 故障點(diǎn)。經(jīng)過這樣的反復(fù)測(cè)驗(yàn)，最終可以將可疑故障點(diǎn)縮小到一個(gè)非常小的范圍。優(yōu)點(diǎn)：delta調(diào)試完全依賴丁對(duì)程序狀態(tài)的研究，而不考慮對(duì)程序結(jié)構(gòu)的分 析不僅可以找出程序中的錯(cuò)誤，還提供了糾錯(cuò)方案。缺點(diǎn)：對(duì)丁大局部程序而言， 一次執(zhí)行涉及到成千上萬個(gè)狀態(tài)，比擬程序狀態(tài)的做法只適用丁較小的程序。(2)“并 集

6、 模型：在失敗運(yùn)行的覆蓋語句集中查找可疑故障語句。其思想是，從失敗運(yùn)行的覆蓋語句集中去掉那些出現(xiàn)在成功運(yùn)行的覆蓋語句集的并集。如果給定一個(gè)成功運(yùn)行的集合S和一個(gè)失敗運(yùn)行f，將S中出現(xiàn)的語句覆蓋集的并集 記為失敗運(yùn)行中出現(xiàn)的語句覆蓋集記為該模型的計(jì)算公式如式所示：f -Us。(3)“交集模型： 找到能判別這個(gè)失敗運(yùn)行的特征， 其思想是： 從所有成功運(yùn) 行的覆蓋.語句集的交集中去掉那些出現(xiàn)在失敗運(yùn)行的覆蓋語句集 /中的語句，將 得到的差異語句集作為可疑語句集。其計(jì)算公式如式所示：1，- f。缺點(diǎn)：并集模型和交集模型的定位效果不是很理想。因?yàn)楹芏鄷r(shí)候故障語句會(huì)同時(shí)出現(xiàn)在失敗運(yùn)行和成功運(yùn)行中，當(dāng)我們對(duì)

7、這些語句集合進(jìn)行集合運(yùn)算時(shí) 故障語句經(jīng)常會(huì)被誤刪。特別是當(dāng)大量運(yùn)行存在的情況下，利用該方法得到的結(jié) 果集極有可能是空集或者根本就不包含故障語句。(4)近鄰模型該方法首先選擇一個(gè)失敗運(yùn)行，然后找到一個(gè)與此失敗運(yùn)行的覆蓋信息最 相近的成功運(yùn)行。利用失敗運(yùn)行和與其最相近的成功運(yùn)行，從失敗運(yùn)行的執(zhí)行語 句集中將那些出現(xiàn)在成功執(zhí)行語句集中的語句剔除，剩余的其他語句集即可作為 故障報(bào)告。近鄰模型提供了兩種方法來度量失敗運(yùn)行和成功運(yùn)行之間覆蓋信息的 相似程度。一種叫做binary distancing，計(jì)算所選擇的失敗運(yùn)行與一個(gè)特殊的成功運(yùn)行之間的差異語句集合。該方法可以定義為“失敗運(yùn)行與成功運(yùn)行執(zhí)行語 句

8、集的不對(duì)稱距離的基數(shù)或者對(duì)稱距離的基數(shù)。另一種是記錄每一個(gè)運(yùn)行所執(zhí) 行到的每一口條語句(或根本塊)的執(zhí)行次數(shù)，然后按照?qǐng)?zhí)行次數(shù)對(duì)語句進(jìn)行排序 計(jì)算兩個(gè)運(yùn)行得到的有序序列之間的距離，該距離是將其中一個(gè)序列轉(zhuǎn)化為另一 個(gè)序歹0時(shí)所花費(fèi)的代價(jià)。優(yōu)點(diǎn)：近鄰模型得出的結(jié)論是：用近鄰模型選擇的成功運(yùn)行通常比隨機(jī)選擇 的成功運(yùn)行更有利丁故障定位，而且該模型在定位故障方面比并集和交集模型更缺點(diǎn)：近鄰模型通過計(jì)算兩類運(yùn)行(成功運(yùn)行和失敗運(yùn)行)的語句集合之間 的距離來尋找與失敗運(yùn)行最相近的成功運(yùn)行，但是它卻無法區(qū)分執(zhí)行了相同語句 但是語句執(zhí)行順序不一樣的運(yùn)行。近鄰模型的改良：Wang人在的近鄰模型根底上提出了一種

9、新的差異度量 方法，即利用程序控制流所對(duì)應(yīng)的兩條路徑，求解兩條路徑之間的最小差異作為 故障報(bào)告。它針對(duì)近鄰模型不能識(shí)別語句執(zhí)行順序的缺乏提出將語句執(zhí)行順序作 為衡量執(zhí)行序列相似度的因素之一，將某條語句的一個(gè)執(zhí)行實(shí)例看做一個(gè)事件 ， 那么每個(gè)運(yùn)行就可以看作是多個(gè)事件的執(zhí)行序列，對(duì)失敗運(yùn)行的事件執(zhí)行序列和 成功運(yùn)行的事件執(zhí)行序歹0進(jìn)行對(duì)齊比擬操作，得出這兩個(gè)運(yùn)行中分支走向不同的 分支事件，這就是Wang等人方法中使用的“差異。 還給出了定性判斷任意兩個(gè) 差異之間的大小的差異度量方法。根據(jù)最小差異選擇一個(gè)與失敗運(yùn)行最相似的成 功運(yùn)行,用二者之間的差異作為故障報(bào)告。優(yōu)點(diǎn)：對(duì)分支語句故障的定位效果比 近

10、鄰模型要好。缺點(diǎn)：對(duì)丁賦值語句故障的定位效果卻不甚理想。 當(dāng)程序故障并 不包含在最小差異中時(shí)，利用該方法進(jìn)行故障定位將得不到理想的效果。(二)基丁排序的故障定位方法上面的方法的相同點(diǎn)在丁 ：認(rèn)為程序中只有一局部語句是可疑的故障點(diǎn)，賦 予它們相同的故障可疑值，認(rèn)為應(yīng)該花費(fèi)同樣多的代價(jià)檢查這些可疑點(diǎn)。而另一 類研究那么認(rèn)為：程序中的每一局部都是可疑的故障點(diǎn)，根據(jù)它們?cè)谶\(yùn)行時(shí)的參與 度和表現(xiàn)不同，賦予它們不同的故障可疑值，然后將故障可疑值降序排列，程序員 按照排序由大到小檢查程序，直至找到故障。基丁排序的故障定位方法的思想是：通過分析程序的動(dòng)態(tài)運(yùn)行信息來進(jìn)行 故障定位。它通常是比擬兩類運(yùn)行(成功運(yùn)行

11、和失敗運(yùn)行)中程序狀態(tài)特征的統(tǒng)計(jì) 信息，直接定位到故障語句。該技術(shù)的區(qū)別在丁使用哪些程序運(yùn)行特征來進(jìn)行對(duì) 比分析。目前常用的程序?qū)嶓w主要有：語句和分支，它們的主要載體是程序頻譜信 息，主要利用程序頻譜(信息來獲取程序?qū)嶓w的特征信息。 利用這些信息來計(jì)算程 序?qū)嶓w(語句或分支)的可疑度，然后根據(jù)可疑度大小對(duì)被檢測(cè)的程序?qū)嶓w (語句 或分支)進(jìn)行降序排序。開發(fā)人員在調(diào)試的過程中可以根據(jù)排序表從前至后始查 找程序故障，起到了一定的輔助作用。(1) Tarantula方法采用的思想是：如果一條語句在失敗的執(zhí)行中出現(xiàn)的次數(shù)比在成功的執(zhí)行中 出現(xiàn)的次數(shù)多的話，那么該語句是故障語句的可能性就比擬大。試題的疑

12、心度具 體算法如下：suspicinesSe) = %f(e)%p(e) %f(e)其中， f (e)表示失效測(cè)試用例中執(zhí)行語句數(shù)/失效測(cè)試用例的總數(shù)，p(e)表示成功測(cè)試用例中執(zhí)行語句數(shù)/成功測(cè)試用例的總數(shù)。Tarantula是目前大家公認(rèn)的最好的基丁統(tǒng)計(jì)的故障定位方法。缺點(diǎn)：該方法要求兩種測(cè)試用例要能夠覆蓋盡可能多的代碼。此外，Tarantula方法難以發(fā)現(xiàn)像賦值語句這樣的程序初始化錯(cuò)誤。也不能區(qū)分一個(gè)失效測(cè)試用例在另一個(gè)測(cè) 試用例中的作用，或者一個(gè)成功測(cè)試用例在另一個(gè)測(cè)試用例中的作用。多程序譜模型(LOUPE)：這種方法是對(duì)Tarantula的一種改良，即在Tarantula所使用的程序

13、譜上增加了依賴對(duì)的覆蓋信息構(gòu)成了多程序譜。所謂多程序譜就是參加了程序執(zhí)行過程中控制依賴和數(shù)據(jù)依賴的覆蓋信息，并根據(jù)這些信息來總體計(jì)算某個(gè)語句的可疑值。(2) Wong方法Wong等人認(rèn)為隨著語句成功執(zhí)行次數(shù)的增加，其對(duì)可疑度奉獻(xiàn)率逐漸減小。該方法將語句i成功執(zhí)行次數(shù)劃分為3個(gè)區(qū)間0,2，3,10，11，+00)。區(qū)間0,2奉獻(xiàn)率權(quán)重為1,區(qū)間3,10的權(quán)重為0.1,區(qū)間11,+00)奉獻(xiàn)率權(quán)重為a (a 0.1),其可疑度計(jì)算公式為： suspiciness (e) = f (e) _ f (passed(e)f(i)表示語句i失敗執(zhí)行的次數(shù)，可以計(jì)算出語句i成功執(zhí)行對(duì)可疑度的奉獻(xiàn)值，最后用語

14、句失敗執(zhí)行奉獻(xiàn)值減去成功執(zhí)行奉獻(xiàn)值，即可得到該語句i的可疑度。 例如,一個(gè)語句失敗執(zhí)行的次數(shù)為5,它對(duì)可疑度的奉獻(xiàn)值為5,成功執(zhí)行的次數(shù)為6,它對(duì)可疑度的奉獻(xiàn)值為2.4,最后得到語句i的可疑度為5-2.4=2.6。缺點(diǎn)：受測(cè)試用例集中正確測(cè)試用例數(shù)和錯(cuò)誤測(cè)試用例數(shù)之比影響較大。(三)程序切片方法(1)靜態(tài)切片程序切片是一種常用的調(diào)試方法，通過切片減少調(diào)試搜索的范圍，一個(gè)測(cè)試 用例執(zhí)行結(jié)果失效是由丁程序語句中執(zhí)行了不正確的變量值而引起的，這種錯(cuò)誤往往出現(xiàn)在與該變量語句配對(duì)的靜態(tài)切片中。切片方法是一種最初的比擬直觀的方法，故障會(huì)出現(xiàn)在一個(gè)失效的測(cè)試用例執(zhí)行的切片中。公式：dice=Sf-Sp表示在

15、測(cè)試用例中失效執(zhí)行的語句的集合除去測(cè)試用例中成功執(zhí)行的語句的集 合，即丁它們的差集。缺點(diǎn)：這種技術(shù)的缺點(diǎn)是可能出現(xiàn)某些可疑語句不包含在切片中的情況，定位效果不理想。問題是如果切片規(guī)模較大時(shí)，有效性會(huì)降低，而且這種算法的時(shí)間開銷 會(huì)很大,最重要的是， 他無法對(duì)在切片中的語句進(jìn)行可疑度排名而直觀的提供應(yīng) 開發(fā)人員作為參考。(2)動(dòng)態(tài)切片為了彌補(bǔ)靜態(tài)切片的缺乏，引入了動(dòng)態(tài)切片方法.定義切片準(zhǔn)那么：靜態(tài)切片不關(guān)心程序的輸入，它的切片準(zhǔn)那么形如,其中i為程序中的一條語句,V表示該語句中使用的變量集合；與靜態(tài)切片不同，動(dòng)態(tài)切片需要一個(gè)特定的輸入，它的切片準(zhǔn)出形如,其中I表示程序的一 個(gè)輸入,i和V所表示的

16、意思與靜態(tài)切片準(zhǔn)那么相同。定義切片： 根據(jù)切片準(zhǔn)那么， 通過抽取與切片準(zhǔn)那么存在數(shù)據(jù)依賴或控制依賴關(guān)系的 語句， 得到的一個(gè)程序片段， 叫做原程序的一個(gè)切片.減少了故障定位的檢查范圍。優(yōu)點(diǎn)：在故障定位過程中，往往需要忽略那些對(duì)暴露故障無關(guān)的語句，而程序切片 正是對(duì)程序做了這樣的提取，讓程序員集中精力去檢查那些與錯(cuò)誤相關(guān)的代碼。缺點(diǎn)：對(duì)丁大型程序而言,經(jīng)過各種切片算法得到的切片往往非常大,反而會(huì)降低 其效率。Naish等人將其應(yīng)用到軟件故障定位中，并根據(jù)切片方法提出語句可疑度計(jì)算公式：., 廠、2 xJatled(i)suspict o usness (i) = - - - -failed (i

17、) + failed _ unexecnte(i) + passed(i)總的來說，基丁排序的故障定位技術(shù)大概有三個(gè)步驟：1)收集某種粒度的實(shí)體的程序執(zhí)行路徑；2)分析成功的執(zhí)行路徑和失敗的執(zhí)行路徑，計(jì)算每個(gè)實(shí)體的故障可疑值；3)按照故障可疑值降序排列程序?qū)嶓w，作為程序員檢查程序的依據(jù)。 這種技術(shù)根據(jù)程序不同局部在程序執(zhí)行時(shí)的表現(xiàn)行為和參與度，給每個(gè)局部賦予 不同的故障可疑值，建議程序員對(duì)程序故障可疑值的大小花費(fèi)不同的代價(jià)檢查程 序。(四) 概率統(tǒng)計(jì)分析方法(1)基丁統(tǒng)計(jì)的定位方法SBI(statistical bug isolation),通過計(jì)算一個(gè) 謂詞P能夠蘊(yùn)含程序失效的可能性Fail

18、ure(p)來定位，用公式表示如下：failure pfailure p i，passed(p)Passed(p)表示P背觀測(cè)到為真的成功測(cè)試用例個(gè)數(shù)，failure(p)表示p被觀測(cè) 到為真的失效測(cè)試用例個(gè)數(shù)。優(yōu)點(diǎn)：SBI方法能夠隔離程序中的多重錯(cuò)誤。缺點(diǎn)： 只是記錄一個(gè)實(shí)體在執(zhí)行過程中是否被覆蓋到 ，缺乏以捕獲每個(gè)測(cè)試用例的行 為信息。(2) SOBE由法：改善SBI的缺乏。它記錄每一個(gè)運(yùn)行中每個(gè)實(shí)體的執(zhí)行次數(shù)，構(gòu)造了一個(gè)失效和成功測(cè)試用例行為的統(tǒng)計(jì)模型，使用這個(gè)統(tǒng)計(jì)模型評(píng)估每個(gè)實(shí) 體以確定它們是否可疑。SOBER!義賦值偏差來估計(jì)在每個(gè)運(yùn)行時(shí)謂詞被賦值為 真的幾率。 更確切地，如果p是一個(gè)謂詞，:T(p)是它在每次運(yùn)行時(shí)被賦值為真 可能性，Ip) =nt/(nt+nf)其中nt表示尸被賦值為真的數(shù)量