：動態切片；程序譜；可疑度；程序耦合度；Dynamicslicingisanimportantmethodofprogramdebugging，Becauseonlytheinputspecificimplementationoftheprogramandrelatedinformationintheprogramisconsidered，therefore,comparedwiththestaticslicing,theresultofthedynamicslicingismoreaccurate.Atpresent,therearemanymethodstocalculatethedynamicslicing,suchastheforwardslicing,thebackwardslicing,thebidirectionalslicing,etc..Duetosliceremovingprogramimplementationindependentparts,sowhenprogramexecutionerroroccurredTheErrorstatementsearchspacecompressionforserialslices,tendingtosavealotoftime.Thepositioningerrorinthemainresearchcontentisautomaticfaultlocalization,thiskindofmethodmainlybyingoodtestcaseset,andthenthroughaprogramstatementcoverageinformationcalculatedsuspiciousdegreeofprogramstatements,finally,accordingtothesuspiciousdegreedetermineswhichstatementsshouldcheck。However,thestructureoftheprogramitselfisignoredonlythroughtheprogram'ssequence.Sosuspiciousdegreeshouldhavebeencalculated,basedonthecouplingbetweenthefunctionoftheprogramagain,thatiscalledthecorrectionofthedegreeoftheprogramstatementThesuspiciousdegreeoffaultlocationmethodbasedonprogramslicingspectrumcalculationstatement,arecalculatedasafunctionofcouplingdegree.Firstly,designthemethodofbidirectionalsliceatheorycanbeused,inordertogettheprograminterrelatedvariables.Then,thecouplingdegreeofthefunctioniscalculatedbytheexistingalgorithm,andfinallythedegreeofthecouplingdegreeiscombinedwiththepreviousdegreeofskepticismasthefinaldegreeof：dynamicslicing;Spectrumprogram;Suspiciousdegree;Couplingdegreeprogram; Bidirectionalsliced 第一章程序切片技 程序切片技術的概 基本術 動態切 第二章頻譜故障頻譜故障的研 計算函數懷疑度實 第三章利用函數間的耦合度改進懷疑 懷疑度的設 實驗效 第四章本系統的一些改 基于行的切片序列的獲 基于動態切片計算函數間耦合 結束 致 參考 附錄一 附錄二 附錄三特性選 程序切片技術的概程序切片技術的程序切片技術是M.Weiser在他的1979年的博士 研究，以此達到對整個程序理解和認識的目的。后來在1981年和1984年，M.Weiser博士 程序切片主要通過尋找程序內部的相關特性，從而分解程序，然后對分解所得的程序某個給定輸入的條件下源程序執行路徑上所有對程序某條語句或點上的變量有影S（，）VN（V所在的語句程序的某個位置N處所定義或的變量或變量的集合V的狀態”（是程序切片最基本的形態，的程序切片都可以通過對這個標準進行擴展而得到。程序切片技術的發展階M.weiser個程序CFGCFG中每個節點相關變量的集合來獲得程序切片。給定切片準則C,M.weiser方法的計算步驟如下：1進行第一次循環，計算基于程序依賴圖（pdg）程序P的PDGGp,Gp的結點表示出現在程序P中的賦值語句和控制謂組件間的依賴，一條邊表示控制依賴或數據依賴（流依賴。PDG反映的是過程內的SDG不僅要考慮過程內語句的相互依賴關系，而且還要考慮過程與過程之間的起來的過程依賴圖（PrDG）組成。SDG類似于PDG，但它還包括表示由于調用而形程序切片技術的應基本術程序依賴圖和靜態切個節點與之對應，每一個控制謂詞表達式（如if-then-else，while-do語句中的條件表達式向邊，即數據依賴邊和控制依賴邊。從節點n到節點mn的直線直接依賴于節點mm與n之間不存在該值得重新定義。從節點n到節點mn的執行與否受到節點m3.21Figure1.1例子程序 Figure1.2程序1所對應的程序Pnv相關的靜態后向切片是由程序P中所有可能影響變量vn（1）n處變量v的所有可到達定義節點，然后以這些節點為起點變量程序依賴圖，變量過程所到的10的變量Y3.2執行歷史和動態切片準所經過的節點組成。和靜態切片不同的是，EH序相同。例如當輸入N=22<1,2,3,4,5-1Figure1.3動態切動態切片方法基本步驟:(1)（2）(3)優缺點 方法簡單，但是可能會包含沒有影響的多余語動態切片方法基本步驟:(1)(3)從圖中被標記的節點開始遍歷，但是僅僅沿著被標記的依賴邊進行遍歷，優缺點：對方法1動態切片方法(1)(2)優缺點 切片比較準確，但是所需的臨時空間比較Figure1.4例子程序 Figure1.5程序3的動態切動態切片方法(1)(2)Figure1.53小第二章頻譜故障頻譜故障的研頻譜故障定位方法的基本思基于風險評估函數的故障定位設程序PG={s1,s2,…,sn}n個程序實體，PGi（1≤i≤n）i個程序實體；測試用TS={t1,t2,…,tm}mTSj（1≤j≤m）TSj矩陣RE表示測試用例集TS在程序PG執行的，REj=p（1≤j≤m）表示測試用例TSj執行結果為pass，REj=f（1≤j≤m）表示測試用例TSj執行結果為fail。矩陣MS表示測試用例TS在程序PG的特定方面的執行信息，執行剖面MSi,j=1表示TSjPGi個程序實體，MSi,j=01表示TS中第j個測試用例在程序執行過程中沒有執行PGi個程序實體。 Ai={aiaiaiaisi的測試用例集TS在程序PG執行的頻譜情況，矩陣 其中aiaiai 頻譜故障基本元間關系Figure2.1頻譜故障基本元間關目前常見的風險評估函數進一步理解風險評估函規律1：ai =0預示著程序實體Si在本次測試中并不是程序PG的故障程序實體。規律2：ai >0預示著程序實體Si在本次測試中可能是程序PG的故障程序實體。規律3：ai取值情況與程序實體Si是否為程序PG的故障程序實體之間沒有必然的關 簡單的為aef、aep乘以一個權重參數固然可以更改風險評估函數RT的可疑度度量值，aef/faep/p從一定程度上反映了語句是故障的可能性，因此在調整aef，aep取值時我們按照α*aef、β*aep的比例進行調整，即調整后的a,a 計算函數懷疑度實ubuntu12.04+gcov使用gcov動態獲取程序的動態執行切片，將正確實例的結果存入correct.data,錯誤的結果存入wrong.data,使用令為grep'\s*[0-9][0-9]*:\s*[1-9][0-9]*' src.c.gcov|awk'{print$2}'|awk-F':''{print$1}'>> correct.data(wrong.data)使用命令./suspicious測試實例個數錯誤實例個數正確實例個數程序所包含語（suspicious.c代碼見附錄）實驗結果演示Figure2.1Figure2.21第三章利用函數間的耦合度改進懷懷疑度的設基本思想：函數的耦合度是度量系統內各個模塊間依賴度的大小，Pg_ones耦合度越小，那么該函數體內錯誤和變化對系統的影響就越小。對一個變量來說，它的耦合度就是所有語句中能夠對其執行產生影響和它的執行會影響到哪些語句；對一個函數來講，它的耦合度是函數體內所有輸出變量耦合度的集合。目前存在兩種求解該類切片的方法：基于行和基于頂點的兩類方法。本節主要討論兩種利用耦合都改進懷疑度的如果語句i，j分別屬于函數fun1，fun2，susp(i)表示語句i的懷疑度，coupling(fun1)表示函數fun1的耦合度。則改進之后的susp'的必要條件是：1）如果susp(i)<=susp(j)且coupling(fun1)<=coupling(fun2);則susp'(i)<susp'(j)2）susp(i)<=susp(j)且coupling(fun1)>coupling(fun2);則susp'(j)-susp'(i)<susp(j)-susp(i);據此可以設計函數f(susp,coupling)=susp*(1+coupling)。以E表示程序出錯，F表示函數出錯，S表示語句出錯P(E|F)=coupling(f);則 因為對于一個程序來說P(E)固定的，據此可以設計函數實驗效該實驗基于平臺ubuntu12.043.1的懷疑度，第四行是經過2計算出的懷疑度，通過比較可以發現如果我們在實踐的過程中，重點檢查懷疑度top218用了2之后我們僅僅需要檢查7行語句，更重要的一點是錯誤語句16包含在了這7行之中（源代碼couple.c代碼見附錄。需要注意的是1的表現并不是很好，究其原因如下：假設susp(j)<susp(i);如果語句ji，即susp’(j)>susp’(i);因為susp(i)*(1+coupling(fun1))-susp(j)*(1+coupling)<susp(i)-susp(j)則susp(i)*coupling(fun1)<susp(j)*coupling(fun2)Coupling(fun2)>susp(i)/susp(j)*coupling(fun1)>a*coupling(fun1)(a>1)；所以使得語句j反超語句i的難度變大了。反過來說，在第二章的懷疑度計算非常準確的情況下，該才會Figure3.1程序2.1利用2改進的懷疑度計算結實驗的改利用二測試了程序3.1（如圖3.2，發現錯誤語句10的排位并沒有變化（圖3.3do1，do2函數與main函數相關的語73.36，4do1，2do2，do1與main的依賴7,7,7,7,0,0；do2與main0,0,0,0,7,7；N(main→do2)=(0+0+7+7+7+7)/6≈2;為該度量計算出的結果如圖3.4所示可以發現語10（錯誤語句）Figure3.1Figure3.31Figure3.2例子程序1利Figure3.31第四章本系統的一些改基于行的切片序列的獲所需切片的性4.2 4.1構造依賴新函數調用時，創建一個新節點，并按照1）（1）外當前指針所指向的變量名，以使得后面的數據依賴能找到的變量值，對指針的1：int*p=&a；不應該存在m4→m3的依賴關系，反之，M7中b2中對a的賦值而這是不合理的。2：Figure4.32：int*p=q;該語句一定依賴于對q3Figure4.5(2)與傳統依賴圖不同的是，在構造依賴圖時在程序的與調用點各自增加了函數的輸入參數節點和調用該函數可能會改變上層的哪些節點Figure4.7函數處方形圖中每一個節點是該函數所需的參數的新定值點（函數的參數會4.95，4.10Figure4.94.10add，出來傳遞的參數不同外，函數體能的4卻不能做出簡化，因為他們所依賴的參數節點不同。在面向過程的設計過程中函數是一定會被被多次調用（例如遞歸調用為了做出簡化，上述數據流4.11的返回值處設置一個list，M6→A2.list[1]此時我們知道按照他的第一個參數節點找依賴關系。M7→A2.list[2]2在第三章中可以發現采用基于動態切片計算出來的函數耦合度確實提升了實驗的效6，通過靜態切片計算出依賴關系fun1:fun2:main1,main3,main4,main6Figure4.12當考慮輸入a=1Figure4.137反之，當a!=12^32aa=1N(fun1→main)=3;N(fun2→main)=4;2^32-1N(fun1→main)=4，N(fun2→main)=3;那么通過學習概率論可知，預測N(fun1→main)=4，N(fun2→main)=3的可能性比較大。當程序中分支語句比較多的N（B→A）X1，X2，X3，（3剔除那些離期望值比較遠X估計E()X估計E()小 也充分認識到了博客這一新興的方式給我們生活帶來的樂趣，雖然我的 信其中的酸甜苦辣最終都會化為甜美的甘泉。這次做 我歷時將近兩個月時間終于把這篇寫完了，在這段充滿奮斗的歷程中，帶給我的學生生涯無限的和收獲。在的寫作過程中遇到了無數的和，都在同學和老師的幫助下度過了。尤其要強烈感謝我的指導老師—周老師，沒有他對我進行了不厭其煩的指導和幫助，無私的為我進行的修改和改進，就沒有我這篇的最終同時，我也要感謝本所的各位學者的專著，如果沒有這些學者的研究成果的啟發和幫助，我將無法完成本篇的最終寫作。至此，我也要感謝我的朋友和同學，他們在我寫的過程中給予我了很多有用的素材，也在的排版和撰寫過程中提供熱情金無足赤，人無完人。由于我的學術水平有限，所寫難免有不足之處，懇請各位參考文獻（三號、黑體、頂格PamGreen,PeterC.R.Lane,AustenRainer,Sven-BodoScholz.AnIntroductiontoSlice-BasedCohesionandCouplingMetrics[D]UniversityofHertfordshire,2009鞠.基于切片譜的錯誤定位框架影響因素分析[D].南通大學.程序切片技術及其應用[B].:科學,.基于依賴性分析的程序切片技術研究[D].江蘇:東南大學,HaoD.,XieT.,ZhangL.,etal.Testinputreductionforresultinspectiontofacilitatefaultlocalization[J].AutomatedSoftwareEngineering.2010Masri,W.Faultlocalizationbasedoninformationflowcoverage.Softw.Test.Reliab..基于熱路徑的程序切片技術在錯誤定位中的應用[D].湖南:月.程序錯誤的框架設計與實現[D].大連:大連海事大學許高陽.基于層次切片的軟件錯誤研究與實現[D].江蘇:東南大.面向Java程序錯誤定位的動態切片技術的研究與應用[D].湖南:湖南大學2000惠軍緒.動態切片技術的研究[D].江蘇:GlenfordJ.Myers,CoreySandler,TomBadgett,ToddM.Thomas.TheArtofSoftwareTesting(2ndEdition)[M].2004.面向對象程序切片技術及其在軟件度量和軟件測試中的運用.[D]江蘇大學博 HuangJC.An~ProachtoProgramtestingComputingSurveys[J].SeP.1975.7(3):1自尼.動態程序切片在面向對象軟件測試中的應用[D].:大于全江.多故障環境下的頻譜實證分析[D],大學附錄程序gcov工具將實例以結果正確和錯誤分類到correct.data和輸出：程序中每條語句的懷疑度（0）structsuspicious{intdoubleint**MS,**MA;structsuspicious*t;intpnumber;//intfnumber;//錯誤實例數inttnumber;//正確實例數intsnumber;//程序語句函數pnumberfnumbertnumbervoid{FILE*file=fopen("correct.data","r");inttemp;intoldtemp=0;intpresent=0;inti,j;{}{} printf("MS矩陣如下:\n");{printf("%d",MS[j][i]);}}int{inti,j;{} {printf("%d",MA[j][i]);}}voidcal(doublea,double{intintef,ep;doubleef1,ep1;{}}intcompare(constvoid*a,constvoid*{structsuspicious*aa=(structsuspicious*)a;structsuspicious*bb=(structsuspicious*)b;return(aa->suspicious-bb->suspicious)>=0?-1:1;}voidprint(int{intdoubleold=0.0;intrank=1;{}}intmain(intargc,char*{inti;{}{}t=malloc(snumber*sizeof(structsuspicious));{}fill_ms();//MSfill_ma();//MAprint(5);//輸出topcount*/return0;}Couple.cpp根據切片結果算出耦合度，然后修正suspicious.c計算出來的懷疑度結usingnamespaceint**N;//N[][]isthenumberofN(func1-->func2)structsuspicious{intdoubleold_susp;intold_rank;doublenew_susp;map<string,int>m;//m[]is structattribute{intsize;//sizeisthesizeoffunc;inthead,tail;//函數開始與結尾處intn;//nisthenumberoffunction;double*coupling;voidread_slice(char*{FILE*charfileName[255];//255intsize,head,tail;for(inti=0;i<n;i++){strings=fileName;}charvalue[255],func1[255],func2[255],oldfunc1[255],oldfunc2[255];chartemp;//代表{,}'\n'intdata;//set<int>s;{ memcmp(func2,oldfunc2,sizeof(func2)))&&{intx=m.find(oldfunc1)->second;inty=m.find(oldfunc2)->second;}while(fsc