若干軟件缺陷定位技術(shù)的比較與分析ComparisonandAnalysisofSeveralSoftwareDefectLocationTechnologies若干軟件缺陷定位技術(shù)的比較與分析III摘要軟件缺陷定位是目前軟件測試中的一個熱點問題，也是軟件測試中最耗費時間和資源的一項工作，它的目的在于有效地檢測出軟件的錯誤所在。傳統(tǒng)的軟件缺陷定位方法主要是插入輸出語句法和設(shè)置斷點法，通過人工來進行調(diào)試，非常耗費時間，效率也不高，而且在大規(guī)模程序中很難實現(xiàn)。為了降低開發(fā)成本，減輕開發(fā)人員的負擔(dān)，軟件缺陷定位技術(shù)可以通過獲取程序執(zhí)行中的信息或者分析程序的源代碼來確定程序中錯誤代碼的可疑位置。文中對現(xiàn)有的軟件缺陷定位方法原理進行了介紹，并給出了軟件錯誤定位的有效性度量。關(guān)鍵詞：軟件缺陷定位；程序分析；程序依賴；程序切片；覆蓋分析AbstractSoftwaredefectlocationisahotissueinsoftwaretesting,anditisalsothemosttime-consumingandresource-intensiveworkinsoftwaretesting.Itspurposeistoeffectivelydetectsoftwareerrors.Thetraditionalsoftwaredefectlocationmethodismainlytoinserttheoutputstatementmethodandsetthebreakpointmethod.Itisverytime-consumingandinefficienttodebugbymanual,anditisdifficulttoimplementinlarge-scaleprograms.Inordertoreducedevelopmentcostsandreducetheburdenondevelopers,softwaredefectlocationtechnologycandeterminethesuspiciouslocationoferrorcodesintheprogrambyobtaininginformationinprogramexecutionoranalyzingthesourcecodeoftheprogram.Inthispaper,theprincipleofexistingsoftwaredefectlocationmethodisintroduced,andtheeffectivenessmeasureofsoftwareerrorlocationisgiven.Keywords:Softwaredefectlocation;programanalysis;programdependency;programslicing;coverageanalysis目錄TOC\o"1-3"\u摘要 iAbstract ii目錄 iii第一章引言 11.1研究背景、現(xiàn)狀 11.1.1研究背景 11.1.2研究現(xiàn)狀 11.2研究內(nèi)容 21.2.1軟件缺陷定位相關(guān)概念 21.2.2主要內(nèi)容 21.3研究意義 3第二章基于覆蓋分析的軟件缺陷定位 42.1示例程序 42.2Tarantula 52.1.1基本概念 52.1.2示例程序結(jié)果 62.3Wong 62.2.1基本概念 62.2.2示例程序結(jié)果 72.4Ochiai 72.3.1基本概念 72.3.2示例程序結(jié)果 82.5小結(jié) 8第3章基于程序切片的軟件缺陷定位 93.1靜態(tài)切片技術(shù) 93.1.1靜態(tài)程序切片準則 93.1.2基于數(shù)據(jù)流方程的靜態(tài)切片 93.2動態(tài)切片技術(shù) 103.2.1動態(tài)程序切片準則 113.2.2前向動態(tài)切片與后向動態(tài)切片 113.3小結(jié) 12第4章基于程序依賴的軟件缺陷定位 134.1程序依賴的相關(guān)概念 134.1.1程序依賴圖 134.1.2控制依賴與數(shù)據(jù)依賴 134.2PPDG 144.2.1示例程序 144.2.2程序依賴圖 154.2.2程序節(jié)點狀態(tài)及概率分布 154.2.2示例程序結(jié)果 164.2小結(jié) 17第5章總結(jié) 185.1軟件缺陷定位技術(shù)的有效性度量 185.1.1評測標準數(shù)據(jù)集 185.1.2評測標準 185.2研究展望 19參考文獻 20致謝 22PAGE22第一章引言1.1研究背景、現(xiàn)狀1.1.1研究背景隨著現(xiàn)代化科技技術(shù)的高速發(fā)展，計算機的技術(shù)已經(jīng)廣泛應(yīng)用于科研、教育、金融、科技、航空、航天等領(lǐng)域，相應(yīng)的軟件也成為其不可或缺的一部分。但是近年來，軟件的安全性受到了很大的質(zhì)疑，在社會各界，由于軟件安全性所帶來的危害層出不窮，而且這種危害趨勢正以我們無法預(yù)計的速度增長。特別是在一些涉及到國家機密和軍事的場合，軟件的安全性更是重中之重。隨著面向?qū)ο蟆?gòu)件軟件、分布式軟件等新技術(shù)的興起，軟件的安全性和可靠性變得日益重要，并成為制約軟件技術(shù)與發(fā)展的重要因素[11]。在實際的軟件研制過程中，總是存在各種各樣的問題，這些問題使得軟件的使用未能達到預(yù)期的效果。為了讓用戶能夠獲得更好的體驗，軟件開發(fā)人員需對其進行相應(yīng)的改進和維護，軟件測試是提高軟件可靠性的重要手段，人們在軟件測試方面的投入在不斷地增加。在軟件測試過程中，軟件缺陷定位是最耗費時間和精力的，可以說一個有效的軟件缺陷方法可以很好的提高軟件的可靠性和安全性。1.1.2研究現(xiàn)狀近年來，軟件缺陷定位取得了很多不錯的成果，目前的大多數(shù)缺陷定位方法都是在語句或語句塊上進行的。包括基于覆蓋分析的軟件缺陷定位，基于程序切片的軟件缺陷定位和基于狀態(tài)依賴的軟件缺陷定位[1]。以往的大多數(shù)研究主要是針對單缺陷定位方法，但是在實際情況中，軟件的缺陷并不是單獨存在的，軟件的各個實體間存在著緊密的聯(lián)系，因此出現(xiàn)了軟件的多缺陷定位方法。現(xiàn)在的大多數(shù)多缺陷定位方法不但能夠用于單缺陷問題，而且在多缺陷方面也具有很好的定位效果。1.2研究內(nèi)容1.2.1軟件缺陷定位相關(guān)概念定義1：軟件是一系列按照特定順序組織的計算機數(shù)據(jù)和指令的集合。一般來講軟件被劃分為編程語言、系統(tǒng)軟件、應(yīng)用軟件和介于這兩者之間的中間體。簡單來說，軟件就是程序加文件的集合體。定義2：軟件測試是一種用來促進鑒定軟件的正確性、完整性、安全性和質(zhì)量的過程。也即是說，在規(guī)定的條件下對程序進行操作，已發(fā)現(xiàn)程序錯誤，衡量軟件質(zhì)量，并對其是否能滿足設(shè)計要求進行評估的過程。定義3：軟件缺陷指軟件中存在的各種問題，表現(xiàn)為用戶所需要的功能沒有完全實現(xiàn)。定義4：程序P是為實現(xiàn)特定目標或是解決特定問題而用計算機語言編寫的命令序列的集合。程序P包含若干個語句或是代碼塊，記為P={c1,c2,}。定義5：測試用例集T={tj=（ij，oj）|1≤j≤m},其中tj第j個測試用例，ij表示該用例的輸入，oj表示期待該用例的輸出。定義5：成功測試用例Ts是指當(dāng)輸入is時所運行得到的輸出o，與期望得到的輸出結(jié)果os相同，即o，s=os.定義6：失敗測試用例Tf是指輸入if時運行得到的結(jié)果o，與期望輸出of不一致。即of，≠of.定義7：運行信息集X（tj）表示程序P運行測試用例tj時的運行信息，包括語句覆蓋，分支覆蓋等。定義7：軟件缺陷定位即應(yīng)用適當(dāng)?shù)能浖毕荻ㄎ环椒◤亩_定軟件缺陷所在的語句位置。1.2.2主要內(nèi)容軟件缺陷定位主要分為靜態(tài)缺陷定位和動態(tài)缺陷定位。靜態(tài)缺陷定位是指通過程序分析等方法來獲取被測程序中的相關(guān)依賴關(guān)系，在不用執(zhí)行測試用例的情況下，確定缺陷語句所在的位置。動態(tài)缺陷定位是通過執(zhí)行測試用例來獲得信息，通過分析執(zhí)行軌跡和運行結(jié)果，并運用相關(guān)的模型來確定缺陷所在的語句位置。本文主要是在實際的案例程序中來運用不同的軟件缺陷定位方法，從而確定軟件缺陷所在的大概位置。并對不同的軟件缺陷定位技術(shù)進行比較和分析。1.3研究意義傳統(tǒng)的軟件缺陷定位方法主要是插入輸出語句法和設(shè)置斷點法，主要是通過人工來進行調(diào)試，非常耗費時間，效率也不高，而且在大規(guī)模程序中也很難實現(xiàn)。目前越來越多的研究人員開始對于自動化軟件缺陷定位進行了研究，通過覆蓋分析，程序切片，程序依賴等方法來對軟件缺陷進行定位。其目的是減少軟件開發(fā)者定位軟件缺陷的成本，提高軟件缺陷定位的效率。第二章基于覆蓋分析的軟件缺陷定位基于覆蓋分析的軟件缺陷定位方法主要統(tǒng)計測試用例的執(zhí)行信息，根據(jù)成功測試用例和失敗測試用例在程序語句上的覆蓋差異計算每個語句的可疑值，并根據(jù)可疑值的高低確定語句的檢查次序[3]。目前該方法已經(jīng)成為軟件缺陷定位的主流方法，包括Tarantula[4],Wong[5，6],Ochiai[3，4，5]，Optiml[9,10],Jaccard[3，4]等方法。2.1示例程序使用表2.1中的程序max[2]來比較分析各種軟件缺陷定位方法。該程序的功能是輸入三個整數(shù)，然后輸出這三個整數(shù)的最大值。表2.1示例程序max.c//programmax.c#include<stdio.h>intmain(){intx,y,z,max

;缺陷示例P1：s8修改為m=yt1t2t3t4t5t6321132534453123425缺陷示例P2：s4修改為if(y<x-1)s8修改為m=yt1t2t3t4t5t6321132534453123425S1

:

printf("pleaseinputthreeintegers");S2:scanf("%d%d%d",&x,&y,&z);S3

:max=x

;S4

:if(y<x){S5

:if(x>z)S6

:max=x;S7

:elseif(x<z)S8

:max=z;}S9

:else{if(y>z)S10

:max=y;S11

:elseS12

:if(y<z)S13

:max=z;}S14

:printf("%d\n",max);成功/失效11111111111111111111111111111111111111111111sssssf11111111111111111111111111111111111111111111fssssf本文將文獻中的mid程序改為max程序，求三個整數(shù)中的最大值。同時給出了兩個缺陷程序。示例程序P1給出了一個缺陷將s8修改為m=y，示例程序P2給出了兩個缺陷將第四條語句修改為if(y<=x-1)；再將第八條語句修改為m=y。測試用例集T={t1，t2，t3，t4，t5}，如果測試成功就用s表示，否則就用f表示。對于P1而言，Ts={t1，t2，t3，t4}，Tf={t5}。對于P而言，Ts={t1，t2，t3，t4}，Tf={t5}。表格中的數(shù)字表示程序執(zhí)行測試用例集時的運行時信息X，即語句覆蓋信息，如果執(zhí)行該用例時語句Si被執(zhí)行，就將單元格數(shù)值置為1，否則空白。2.2TarantulaTarantula[4]方法首先是由Jone和Harrold等人提出，并取得了不錯的錯誤定位效果。他們認為只要是某個語句被失敗用例覆蓋。那么就值得懷疑，同時，他也容忍出現(xiàn)錯誤的語句偶爾的被成功用例覆蓋。2.1.1基本概念該方法使用常用的信息來確定缺陷所在的位置，其中包括每個測試用例的執(zhí)行結(jié)果、程序?qū)嶓w（分支、語句或函數(shù)）被每個測試用例覆蓋的信息以及程序的源代碼[7]。對于程序?qū)嶓we，它的語句可以度度量公式2.1[8]如下：aef(aef+anf)Tarantula=（2.1）aefaes(aef+aef)+(aes+ans)aef語句被測試用例集合中失效測試用例執(zhí)行的次數(shù).anf語句沒有被測試用例集合中失效測試用例執(zhí)行的次數(shù).aes語句被測試用例集合中成功測試用例執(zhí)行的次數(shù).ans語句沒有被測試用例集合中成功測試用例執(zhí)行的次數(shù).2.1.2示例程序結(jié)果表2.1Tarantula方法分析示例程序結(jié)果語句示例程序P1示例程序P2S10.500.50S20.500.50S30.500.50S40.500.50S50.500.50S60.000.50S71.000.50S81.000.50S90.000.50S100.000.50S110.000.50S120.000.50S130.000.50S140.500.502.3WongWong等人在Tarantula方法的基礎(chǔ)上進一步分析了成功測試用例次數(shù)對于程序缺陷定位的影響。認為成功測試用例覆蓋次數(shù)越多的語句對于語句可疑度的影響就越小，并進而提出了Wong1(s),Wong2(s)和Wong3(s)這三個公式。2.2.1基本概念該方法主要是通過確定某條語句被失敗測試用例和成功測試用例覆蓋的次數(shù)差，來計算該條語句的可疑度。對于程序?qū)嶓we，它的語句可以度度量公式2.2[5]如下：Wong=(aef–aes)(2.2)aef語句被測試用例集合中失效測試用例執(zhí)行的次數(shù).aes語句被測試用例集合中成功測試用例執(zhí)行的次數(shù).2.2.2示例程序結(jié)果表2.2Wong方法分析示例程序結(jié)果語句示例程序P1示例程序P2S1-3.00-1.00S2-3.00-1.00S3-3.00-1.00S4-3.00-1.00S50.00-1.00S6-1.00-1.00S71.00-1.00S81.00-1.00S9-3.00-1.00S10-3.00-1.00S11-1.00-1.00S12-2.00-1.00S13-2.00-1.00S14-3.00-1.002.4OchiaiAbreu[9]等人受到分子生物學(xué)基因相似度公式和聚類分析思想的啟發(fā)，提出了Jaccard方法和Ochiai方法，研究表明Ochiai方法的軟件缺陷定位效果要優(yōu)于Tarantula方法。2.3.1基本概念對于程序?qū)嶓we，它的語句可以度度量公式2.3[1]如下：aefOchiai=（2.3）Nf*[aef+aes]aef語句被測試用例集合中失效測試用例執(zhí)行的次數(shù).aes語句被測試用例集合中成功測試用例執(zhí)行的次數(shù).Nf失敗測試用例個數(shù).2.3.2示例程序結(jié)果表2.3Ochiai方法分析示例程序結(jié)果語句示例程序P1示例程序P2S10.410.58S20.410.58S30.410.58S40.410.58S50.500.58S60.000.58S71.000.58S81.000.58S90.000.58S100.000.58S110.000.58S120.000.58S130.000.58S140.410.582.5小結(jié)從表2.1,表2.2和表2.3中可以看出，上述三種方法對于示例程序P1都能很好地確定軟件缺陷語句所在的位置，將修改語句賦值為最高的可疑度，從而在檢查缺陷時，優(yōu)先檢查該語句。但是對于示例程序P2，三種方法都未能很好地確定缺陷語句和非缺陷語句，因此需要手工對于程序進行調(diào)試，從而進一步確定軟件缺陷所在的位置。Naish[10]等人用模型和實驗相結(jié)合的方式來評估了36中不同可疑度度量公式的覆蓋分析方法，結(jié)果表明Tarantula方法與CBI方法等價，Wong方法和其他九種方法等價。覆蓋分析方法的優(yōu)點在于可以很直觀的看到語句的可疑程度，不需要程序化建模，計算的復(fù)雜度較低，通常適用于分析大規(guī)模的程序。該方法也存在一定的問題，通常情況下只能統(tǒng)計語句間的關(guān)聯(lián)，而不能充分分析語句元素間的互相作用；并且該方法一般只檢測可疑語句或是謂詞，而不能對缺陷狀態(tài)進行描述。第3章基于程序切片的軟件缺陷定位程序切片技術(shù)(programslice)這一概念最早是由Weiser在1979年提出的，此后又出現(xiàn)了許多不同的定義以及用于計算切片的方法。程序切片技術(shù)軟件維護、程序調(diào)試、測試、代碼理解以及逆向工程等方面有許多的應(yīng)用[12]。程序切片技術(shù)[13]是一種根據(jù)特定計算提取程序中相關(guān)語句的分解技術(shù)，他可以通過單一的錯誤運行來縮小錯誤的搜索域。程序切片方法主要包括靜態(tài)程序切片技術(shù)和動態(tài)程序切片技術(shù)。3.1靜態(tài)切片技術(shù)Moreno[14]提出一種名為Lobster的靜態(tài)缺陷定位方法，該方法將軟件缺陷報告中的信息引入到軟件缺陷定位靜態(tài)定位方法中來，利用堆棧信息和文本檢索相結(jié)合的方法進行缺陷定位。靜態(tài)軟件缺陷定位[15]主要是通過靜態(tài)分析程序的控制流和數(shù)據(jù)流，對程序進行分解，從而降低軟件錯誤定位的搜索域，由于靜態(tài)程序切片定位方法比較保守，所以目前來說，精度不是很高。3.1.1靜態(tài)程序切片準則靜態(tài)切片準則[16]一般是一個二元組C=（A,V），其中A表示程序中的某個點（一條語句），它表示程序中的某條語句，V表示程序中的變量的一個子集。對于某個靜態(tài)切片準則C，靜態(tài)切片有可能影響關(guān)注點A處V中變量的所有語句組成。同時，程序的切片還可以是任意一個對A點處V中變量具有與程序相同影響的計算機程序。3.1.2基于數(shù)據(jù)流方程的靜態(tài)切片相關(guān)定義：控制流圖[16]（ContralFlowGraph）簡稱CFG圖，它是一個有向圖，表示為四元組G=（V,E,s,e）,V是每個語句的變量集合，E是邊的集合，s是開始節(jié)點，e是結(jié)束節(jié)點。如果從n→m存在控制流，那么邊（n,m）∈E。數(shù)據(jù)流的切片算法[16]：（1）初始化所有節(jié)點的相關(guān)集合，置為空集合；（2）把變量集合V中的所有變量放入relevant(n)

;(relevant(n)就是每個節(jié)點的數(shù)據(jù)流信息)（3）對n的直接前驅(qū)m的relevant(m)的定義如下：relevant(m)=relevant(n)-def(m)

;//排除所有在m點的定義性變量；if(relevant(n)∩def(m)≠0)//如果在m點定義了n節(jié)點中的相關(guān)變量

;relevant(m)=relevant(m)∪ref(m)

;//包含進m點的引用性變量；因為節(jié)點m定義了一個在節(jié)點n引用的相關(guān)變量，將節(jié)點m包含進片內(nèi)。（4）在CFG中對m點的直接前驅(qū)重復(fù)操作（3），直到到達n的初始化集合或相關(guān)變量集合relevant(n)為空。表3.1源程序P3關(guān)于節(jié)點<8,a>的relevant集合源程序P3ref(n)def(n)relevant(n)1.b=2

;2.c=3

;3.d=1

;4.a=d

;5.d=b+d

;6.b=b+2

;7.a=b+c

;8.printf(“%d”,a)

;db,dbb,cabcdadbabb,cb,cb,cb,cb,ca從表3.1中可以看出基于數(shù)據(jù)流的靜態(tài)切片方法下的切片節(jié)點集合為{1,2,6,7,8}。該算法最大的缺點就是必須為每個切片計算節(jié)點的相關(guān)集合，并且這種數(shù)據(jù)信息不能被其他切片重用。3.2動態(tài)切片技術(shù)動態(tài)切片方法使用的是當(dāng)前動態(tài)的數(shù)據(jù)流和控制流來進行分析，因此程序的切片依賴于具體的數(shù)據(jù)輸入，沿著執(zhí)行路徑的依賴關(guān)系來進行分析，在實際應(yīng)用中，動態(tài)切片技術(shù)具有較高的空間復(fù)雜度，切片體積較小，可能會出現(xiàn)丟失錯誤語句的情況[17]。動態(tài)切片方法還可以分為前向切片方法和后向切片方法。3.2.1動態(tài)程序切片準則動態(tài)切片準則[16]可以用一個三元組來表示C=(I,A,V)，I表示一個程序的輸入，V表示程序中變量的子集，對于給定的動態(tài)程序切片標準C，動態(tài)切片由所有程序中直接影響或間接影響關(guān)注點A處的關(guān)于V中變量的語句構(gòu)成。3.2.2前向動態(tài)切片與后向動態(tài)切片前向切片F(xiàn)orward是包括被該變量值影響的所有執(zhí)行語句；后向切片Backward包括影響該變量值的所有執(zhí)行語句。對于示例程序max.c，當(dāng)用t6測試示例程序P1，t1測試示例程序P2時，發(fā)現(xiàn)在S14處出現(xiàn)錯誤的max值時，對其執(zhí)行反向切片的結(jié)果如下表：表3.2反向切片結(jié)果反向切片Backwardt6測試示例程序P1(S8修改為m=y){S14，S8，S7，S5，S4，S3，S2，S1}t1測試示例程序P2(s4修改為if(y<x-1))(s8修改為m=y){S14，S10，S9，S4，S3，S2，S1}對于示例程序max.c，當(dāng)用t6測試示例程序P1，t1測試示例程序P2時，發(fā)現(xiàn)在S14處出現(xiàn)錯誤的max值時，對其第一個參數(shù)x執(zhí)行前向切片的結(jié)果如下表：表3.2前向切片結(jié)果參數(shù)程序前向切片F(xiàn)orwardxt6測試示例程序P1(S8修改為m=y){S1，S2，S3，S8，S14}xt1測試示例程序P2(s4修改為if(y<x-1))(s8修改為m=y){S1，S2，S3，S10，S14}3.3小結(jié)靜態(tài)程序切片包含所有可能的程序執(zhí)行語句，但是動態(tài)程序切片是根據(jù)某一具體的測試用例的執(zhí)行軌跡來收集運行時的信息。動態(tài)切片與靜態(tài)程序切片相比，可以很明顯的減小程序切片的大小[18，19]。靜態(tài)程序切片是基于數(shù)據(jù)相關(guān)性的一種方法，它的切片中的語句數(shù)量會較多，但是動態(tài)切片是對于具體執(zhí)行來動態(tài)的獲取數(shù)據(jù)和控制依賴信息，并且它的精度也會更高，因此目前動態(tài)程序切片方法的使用要相對廣泛。第4章基于程序依賴的軟件缺陷定位由于覆蓋分析方法未對程序執(zhí)行狀態(tài)及其轉(zhuǎn)移進行分析，因此無法有效的分析失效感染狀態(tài)傳播的問題，科研人員在此基礎(chǔ)上提出了基于依賴分析的軟件缺陷定位方法。該方法的思想與覆蓋分析方法基本一致，區(qū)別在于統(tǒng)計成功測試用例和失敗測試用例狀態(tài)的時候加以考慮程序?qū)嶓w間的依賴關(guān)系[8]。依賴關(guān)系是指在一個程序中，若在事件B發(fā)生之前，事件A必須發(fā)生，那么就說事件B就依賴于事件A[20]。程序依賴包括控制依賴和數(shù)據(jù)依賴。4.1程序依賴的相關(guān)概念4.1.1程序依賴圖程序依賴圖[16]（ProgramDependenceGraph）簡稱PDG，可以表示為G=(V,E)，其中G表示一個有向圖，V表示程序中語句節(jié)點的集合，E是程序中的兩條語句節(jié)點a、b間的依賴關(guān)系，根據(jù)a、b間的依賴關(guān)系來制作有向邊，程序中的每條語句都是CFG中的一個節(jié)點。4.1.2控制依賴與數(shù)據(jù)依賴控制依賴：直觀來說，如果一個條件語句b可以影響另一條語句a的執(zhí)行，那么就說語句a控制依賴于語句b。數(shù)據(jù)依賴：如果存在一條路徑a→b,變量x在a點定義，在b點使用，并且該變量在該條路徑上一直未被重新定義，那么就稱語句b數(shù)據(jù)依賴于語句a。Zhang[21]等人認為錯誤的程序狀態(tài)會沿著控制依賴向后傳播，通過抽象控制流來傳播基本塊的感染狀態(tài)，因此提出了CP（CapturePropagation）方法。該方法首先對程序進行控制依賴分析，進而建立控制依賴流圖CFG，再計算每條控制依賴邊傳播錯誤的可疑值，最后，按照拓撲排序的基本過程，利用后續(xù)基本塊的可移值逆向推導(dǎo)前驅(qū)基本塊的可疑值。數(shù)據(jù)依賴主要用來描述程序中賦值語句等號左邊數(shù)據(jù)依賴于賦值等號右邊的關(guān)系，而控制語句主要描述的是循環(huán)語句，條件語句等語句塊對嵌套在其中的語句的控制關(guān)系[16]。4.2PPDGBaah等人[22]對程序依賴圖進行了擴展，通過分析測試用例的執(zhí)行信息節(jié)點間的統(tǒng)計依賴，進而建立了概率程序依賴圖PPDG(ProbablisticProgramDependenceGraph).4.2.1示例程序使用表4.1中的源程序mid[2]來比較分析PPDG缺陷定位方法。該程序的功能是輸入三個整數(shù)，然后輸出這三個整數(shù)的中間值。表4.1示例程序mid.c//programmax.c#include<stdio.h>intmain(intargc,char*argc){intx,y,z,m

;缺陷示例P3：s5修改為m=yt1t2t3t4t5t6335123321555534213缺陷示例P4：s5修改為if(y<x-1)s9修改為m=yt1t2t3t4t5t6335123321555534213S1

:x=atoi(argv[1])

;S2:y=atoi(argv[2])

;S3

:z=atoi(argv[3])

;S4

:m=z

;S5

:if(y<z){S6

:if(x<y)S7

:m=y

;S8

:elseif(x<z)S9

:m=x

;}S10

:else{S11

:if(x>y)S12

:m=y

;S13

:elseif(x>z)S14

:m=x

;}S15

:printf("%d\n",m);成功/失效1111111111111111111111111111111111111111111111111111sssssf111111111111111111111111111111111111111111111111111111fssssf本章應(yīng)用文獻[2]中的mid程序為例，來詳細介紹以程序依賴為基礎(chǔ)的軟件缺陷定位方法。同時給出了兩個缺陷程序。示例程序P3給出了一個缺陷將第五條修改為m=y，示例程序P4給出了兩個缺陷將第五條語句修改為if(y<=x-1)；再將第九條語句修改為m=y。測試用例集T={t1，t2，t3，t4，t5}，如果測試成功就用s表示，否則就用f表示。對于P1而言，Ts={t1，t2，t3，t4}，Tf={t5}。對于P而言，Ts={t1，t2，t3，t4}，Tf={t5}。表格中的數(shù)字表示程序執(zhí)行測試用例集時的運行時信息X，即語句覆蓋信息，如果執(zhí)行該用例時語句Si被執(zhí)行，就將單元格數(shù)值置為1，否則空白。4.2.2程序依賴圖在程序狀態(tài)圖中，每一個節(jié)點都表示程序語句，實線表示控制依賴，虛線表示數(shù)據(jù)依賴，Di表示數(shù)據(jù)依賴節(jié)點，True和False表示謂詞的狀態(tài)。 圖4.2示例程序P3的程序依賴圖4.2.2程序節(jié)點狀態(tài)及概率分布在PPDG中，每一個節(jié)點都有其對應(yīng)的狀態(tài)集合，并且每一個狀態(tài)都對應(yīng)一個概率值。下表是示例程序P3的節(jié)點狀態(tài)和概率分布。其中1表示該語句被執(zhí)行，0表示不被執(zhí)行；數(shù)據(jù)流di表示語句間的邏輯關(guān)系，di(a)表示第i條語句定義了變量a；如果語句s5的狀態(tài)為{d3(a),1}就表示該語句使用了第三條語句定義的變量a或者該語句未被執(zhí)行。表4.2示例程序P3節(jié)點狀態(tài)集合及其概率分布節(jié)點狀態(tài)集合概率分布s1s2s31,0P(s1)P(s2)P(s3)s4d3(z),0P(s3|s4)d5d2(y)d3(z),0P(d5|s2,s3)s5<,>,=,=,0P(s5|d5)d6d1(x),d2(y),0P(d6|s1,s2)s6<,>,=,=,0P(s6|s5,d6)s7d2(y),0P(s7|s6,s2)d8d1(x),d3(z),0P(d8|s1,s3)s8<,>,=,=,0P(s8|d8,s6)s9d2(y),0P(s9|s8,s2)上表中節(jié)點狀態(tài)的概率為條件概率，因為該節(jié)點的概率會受到其前驅(qū)節(jié)點的影響。如果該節(jié)點存在前驅(qū)節(jié)點，那么狀態(tài)概率為前驅(qū)節(jié)點在當(dāng)前節(jié)點的條件概率，否則該狀態(tài)概率為成功測試用例中出現(xiàn)該狀態(tài)的次數(shù)與該節(jié)點被執(zhí)行次數(shù)的比值。4.2.2示例程序結(jié)果使用失敗測試用例t6執(zhí)行示例程序P3，所得程序狀態(tài)軌跡如下表所示：表4.3PPDG分析示例程序P3的結(jié)果節(jié)點狀態(tài)成功條件概率S11P(s1=1)=P(s2=1)=P(s3=1)=1S21P(s4=d3(z)|s2=1)=1

S31P(d5=d2(y),d3(z)|s2=1)=1P(d5=d2(y),d3(z)|s3=1)=1S4d3(z)P(s5=<|d5=d2(y),d3(z))=0.6D5d2(y),d3(z)P(d6=d1(x),d2(y)|s1=1)=0.6P(d6=d1(x),d2(y)|s2=1)=0.6S5<P(s6=>|d6=d1(x),d2(y))=0.33P(s6=>|s5=<)=0.33D6d1(x),d2(y)P(d8=d1(x),d3(z)|s1=1)=0.4P(d8=d1(x),d3(z)|s3=1)=0.4S6>P(s8=<|d8=d1(x),d3(z)=0.5P(s8=<|s6=>)=1D8d1(x),d3(z)P(s9=d2(y)|s2=1)=0.2S8<P(s15=d4(m)|s4=d3(z))=0.4S9d2(y)S15d4(m)在使用PPDG方法進行軟件缺陷定位時，對于失敗測試用例的各個節(jié)點狀態(tài)，與成功測試概率相對比，然后對其概率進行排序，其中概率值最低的語句可疑值最高。從上表中可以看出，對于失敗測試用例t6的狀態(tài)集合而言，當(dāng)前驅(qū)節(jié)點s2被執(zhí)行時，語句s9具有最低的概率，因此第九條語句與第二條語句間存在的數(shù)據(jù)依賴關(guān)系最可疑。4.2小結(jié)基于依賴分析方法的軟件缺陷定位不僅可以給出程序語句的可疑值，也考慮了在失敗測試用例下，程序錯誤狀態(tài)的傳播，同時控制依賴和數(shù)據(jù)依賴的相關(guān)信息也可以幫助理解失敗測試用例產(chǎn)生的上下文信息。第5章總結(jié)5.1軟件缺陷定位技術(shù)的有效性度量5.1.1評測標準數(shù)據(jù)集目前大多數(shù)軟件缺陷定位研究都采用的是實驗驗證的方法來判斷該技術(shù)是否有效，一般會使用評測數(shù)據(jù)集來檢驗[23]。西門子套件（SiemensSuite）是目前來說使用最廣泛的評測數(shù)據(jù)集，最早是為了研究控制流和數(shù)據(jù)流的準則對軟件錯誤探測能力的影響而創(chuàng)建[24]。該數(shù)據(jù)集中共包含七組為不同軟件功能而設(shè)計的C程序，由人工注入的方式來創(chuàng)建這些程序的錯誤版本，其中包括對語句的修改等等，從而來模擬現(xiàn)實中可能會出現(xiàn)的錯誤。SiemensSuite中的錯誤都是有人工添加的，其中包含的程序規(guī)模較小，因此不能作為大型程序中出現(xiàn)軟件錯誤的標志。Space解釋器程序是專門為歐洲航天局開發(fā)的，其中有大量的可執(zhí)行代碼和測試用例，還有許多的關(guān)聯(lián)版本，每個版本都含有一個程序開發(fā)中的錯誤，因此可以作為大規(guī)模程序中出現(xiàn)軟件錯誤的標志[7]。5.1.2評測標準軟件缺陷定位的評測標準是用于測定缺陷定位技術(shù)的定位準確度的。（1）分數(shù)值法（EXAMSource），Renieris和Reiss最早采用該方法來評測缺陷定位的效果。分數(shù)值法是指用戶在定位到程序的錯誤語句時未檢測的代碼數(shù)占總的程序代碼數(shù)的百分比，其分數(shù)越高就表示定位效果越好[7’23]。（2）累積檢查語句（CumulativeNumberofStatementsExamined）是指如果程序中存在n個錯誤，并且分布在不同的錯誤版本中，累積檢查語句數(shù)就表示檢測出不同版本中的n個錯誤總共需要檢查的語句數(shù)，總語句數(shù)越少就表示軟件錯誤定位效果越好。5.2研究展望本文通過廣泛的閱讀相關(guān)資料和文獻，并且檢索了權(quán)威的論文數(shù)據(jù)庫，對于軟件缺陷定位方法進行了比較和分析，從而得到了以下的結(jié)論：首先，錯誤定位方法可以分為動態(tài)和靜態(tài)定位方法。在不需要分析程序的依賴關(guān)系，只要獲得成功和失敗測試用例的覆蓋信息，應(yīng)用統(tǒng)計學(xué)的方法對程序的語句實體可疑度進行計算，然后按照高低排序來定位錯誤程序?qū)嶓w的研究最多，應(yīng)用也是最為廣泛的，但是在大數(shù)據(jù)時代，使用數(shù)據(jù)挖掘或機器學(xué)習(xí)方法來獲得程序?qū)嶓w可疑度的研究較少。其次，基于程序切片的軟件缺陷定位考慮了程序?qū)嶓w間的依賴關(guān)系，而PPDG方法又在程序依賴的基礎(chǔ)之上，考慮了測試用例節(jié)點間的統(tǒng)計信息。但是這些方法都僅僅考慮了程序的動態(tài)信息，大多數(shù)研究人員都是應(yīng)用大量的測試用例來獲得程序運行時的動態(tài)信息，并且需要記錄大量的相關(guān)信息，因此很難保證軟件測試的充分性，可能會存在漏報的情況。而靜態(tài)錯誤定位方法只是分析程序的控制流和數(shù)據(jù)流，不需要獲取大量的測試信息，因此動靜結(jié)合的方法可能會是未來軟件缺陷定位技術(shù)發(fā)展的一個方向。目前軟件的規(guī)模越來越大，復(fù)雜程度也是越來越高，程序的執(zhí)行信息在不斷地增長，軟件錯誤定位也越來越困難。數(shù)據(jù)挖掘可以對海量的信息進行處理，機器學(xué)習(xí)也具備自適應(yīng)學(xué)習(xí)能力，近年來數(shù)據(jù)挖掘和機器學(xué)習(xí)技術(shù)在不斷地發(fā)展，因此采用數(shù)據(jù)挖掘和機器學(xué)習(xí)的方法來進行軟件缺陷定位也是值得研究的。參考文獻[1]周明泉.江國華.一種基于頻譜信息并結(jié)合碰集和遺傳算法的軟件缺陷定位方法.計算機科學(xué).2018-09.[2]JanssenT,AbreuR,GemundAJC.Zoltar

:AtoolsetforautomaticfaultLocalization//Proceedingsofthe2009IEEE/ACMInternationalConferenceonAutomatedsoftwareEngineering.Washington,USA,2009

.[3]陳翔，鞠小林，文萬志，顧慶.基于程序頻譜的動態(tài)軟件缺陷定位方法研究[J].軟件學(xué)報，2014-12.[4]JonesJA,HarroldMJ.EmpiricalevalutionoftheTarantulaautomaticfault-Locationtechnique.Proceedingsofthe20thIEEE/ACMInternationalConferenceonAutomatedSofewareEngineering.LongBeach,CA,USA.2005.273-282.[5]WongWE,WeiTingting,QiYu.ACrosstab-basedstatisticalmethodforeffectivefaultlocalization[C].InternationalConferenceonSofewareTesting,2008

:42-51.[6]蔡蕊，張仕，余曉菲，蔣建民.基于程序頻譜的缺陷定位方法.計算機系統(tǒng)應(yīng)用,2019-01.[7]虞凱，林夢香.自動化軟件錯誤定位技術(shù)研究進展.計算機學(xué)報，2011-08.[8]王克朝，王甜甜，蘇小紅，馬培軍.軟件錯誤自動定位關(guān)鍵科學(xué)問題及研究進展.計算機學(xué)報,2015-11.[9]舒挺，黃明獻，丁佐華，王磊，夏勁松.基于條件概率模型的缺陷定位方法[J].軟件學(xué)報，2017-07.[10]NaishL,LeeHJ,RamamohanaraoK.Amodalforspectra-based