基于超級塊支配圖插裝的軟件測試工具設(shè)計與實現(xiàn)

1、基于超級塊支配圖插裝的軟件測試工具設(shè)計與實現(xiàn)    摘 要:通過超級塊支配圖來分析軟件測試探針的合理插裝位置,可有效地減少插裝探針數(shù)量,降低代碼插裝對程序的影響?；诔墘K支配圖的代碼插裝原理,設(shè)計一種針對C語言的軟件自動測試工具(SAT),介紹了該工具中詞法語法分析器、靜態(tài)分析器、代碼插裝器等主要功能模塊的具體實現(xiàn)方案,同時對SAT的插裝性能進行了分析。 關(guān)鍵詞:代碼插裝; 覆蓋測試; 超級塊支配圖 中圖分類號:TP311 文獻標(biāo)志碼:A 文章編號:1001-3695(2010)03-0923-05 Design and implementation

2、of software testing tool based on super block dominator graph XU Xiao-feng?a, CHEN yan?b, LI Yi-Yang?a , LIN Xiao-peng?a, GUO Dong-hui?a,b? (a.Dept. of Physics, b.School of Information Science & Technology, Xiamen University, Xiamen Fujian 361005, China) Abstract:This paper described the design

3、and implementation of a coverage testing tool (SAT). It emphasized on the realization of main modules: lexer and parser, static analyzer, and code instrumenter. Compared to other tools that instruments each basic block, SAT used super block dominator graph to check which basic block should be instru

4、mented so that both the number of instrumentation probes and runtime overhead of instrumentation are reduced effectively. Finally,used an example to show the functionalities of the tool as well as the discussed performance of SAT. Key words:code instrumentation; coverage testing; super block dominat

5、or graph 軟件測試是保證軟件質(zhì)量的重要手段,可分為手工測試和自動化測試。隨著軟件規(guī)模的不斷擴大,手工測試已無法滿足測試的需要,應(yīng)用測試工具進行自動化測試能夠完成許多手工測試難以實現(xiàn)的測試,達到有效縮短軟件開發(fā)及測試時間、保證軟件質(zhì)量的目的1,已成為軟件質(zhì)量和可靠性保證的關(guān)鍵技術(shù)手段。代碼覆蓋測試工具是目前軟件測試的重要工具之一2,它提供有效的覆蓋信息用于量度測試完整性3和輔助測試員設(shè)計測試用例,從而提高測試效率。 代碼覆蓋測試工具通常是對被測試的元素4(如語句、程序塊、分支、謂詞、分支-謂詞等)進行探針插裝,通過運行帶有探針的被測程序獲得程序運行的執(zhí)行信息。但探針的插入會對被測程序產(chǎn)生

6、負面影響,如使被測試程序的代碼量增加、執(zhí)行效率降低等。因此如何設(shè)計合理的插裝策略、減少插裝探針對被測程序的影響,是覆蓋工具設(shè)計的關(guān)鍵問題之一5,6。近年來,多個文獻中提到多種代碼覆蓋測試工具:文獻3,79介紹了一款C語言的覆蓋測試工具ATAC,該工具支持基本塊、判定、C-uses、P-uses等多種覆蓋準則;文獻10介紹了基于程序插裝的動態(tài)測試技術(shù)實現(xiàn)的Safepro軟件測試工具,具體討論了動態(tài)測試的模型、數(shù)據(jù)流模型和動態(tài)跟蹤數(shù)據(jù)的編碼和解碼技術(shù)、插裝庫設(shè)計與插裝策略等內(nèi)容,但這些工具都存在插裝探針冗余問題;文獻6介紹了一款利用程序控制流前支配樹信息進行插裝的測試工具Dyninst,能有效地減

7、少探針,但由于缺乏后支配樹的信息,它的插裝策略仍然存在冗余。而超級塊支配圖融合了前支配樹和后支配樹信息,可以有效地減少插裝探針。 本文介紹了一個C語言的塊覆蓋軟件測試工具(SAT)的設(shè)計方案與實現(xiàn),它采用超級塊支配圖對插裝探針個數(shù)進行有效優(yōu)化,減少了代碼插裝對被測程序性能的影響,同時提供圖形化的界面,顯示各個函數(shù)的塊測試覆蓋率,定位未覆蓋的塊,便于測試員直觀地進行覆蓋分析,以補充新的測試用例,提高測試覆蓋率。 1 代碼插裝技術(shù)原理 SAT的插裝策略是基于超級塊支配圖11性質(zhì)實現(xiàn)的,因此本章首先對超級塊支配圖的相關(guān)定義和性質(zhì)進行闡述。 1.1 超級塊支配圖的定義及性質(zhì) 定義1 基本塊支配圖是一個

8、用二元組?N,E表示的有向圖,N是節(jié)點集合,E是邊集合。支配圖中的任一個節(jié)點nN表示程序的一個基本塊12;邊eE用有序的節(jié)點對表示,記為n?i,n?j,表示n?i直接前支配n?j(或n?i直接后支配n?j)。 性質(zhì)1 基本塊支配圖上的祖先節(jié)點支配后裔節(jié)點。? 證明 由基本塊支配圖定義可知。 定義2 對于給定的基本塊支配圖G=N,E,圖中的強連通分量的節(jié)點集合定義為超級塊。 性質(zhì)2 一個超級塊可能包含一個或多個基本塊。 證明 由強連通分量的定義可知。 設(shè)基本塊支配圖中的超級塊集合為S?m|mk,k=超級塊總數(shù),超級塊S?m具有C?m個基本塊,即S?m=n?mi?|iC?m,可得: 性質(zhì)3 S?m

9、?N且klS?m=N,S?mS?n=?(mk,nl,?mn)?。 證明 由超級塊定義可知。 性質(zhì)4 在一次執(zhí)行中,如果超級塊S?m中的一個基本塊被執(zhí)行,那么S?m中其他基本塊也被執(zhí)行了。 證明 假設(shè)在一次執(zhí)行中,超級塊S?mn?mi?|iC?m中的n?mi?節(jié)點被執(zhí)行。 a)若?C?m=1?,結(jié)論成立。 b)若?C?m>1,任取n?mi?,n?mj?S?m(n?mi?n?mj?),由定義2得,n?mi?與n?mj?強連通,即基本塊n?mi?支配n?mj?,且基本塊n?mj?支配n?mi?。根據(jù)基本塊支配關(guān)系定義12:基本塊n?mi?支配n?mj?,可知如果n?mj?被執(zhí)行,則n?mi?也

10、被執(zhí)行;基本塊n?mj?支配n?mi?,可知如果n?mi?被執(zhí)行,則n?mj?也被執(zhí)行。故可得,對于超級塊中任意兩個基本塊,如果一個被執(zhí)行,另一個也必然被執(zhí)行。因此,超級塊中的一個基本塊被執(zhí)行,那么超級塊中其他基本塊也被執(zhí)行了。 定義3 如果超級塊S?m中的一個基本塊直接前支配(或者后支配)超級塊S?n中另一個基本塊,那么稱超級塊S?m直接支配超級塊S?n。? 定義4 超級塊支配圖(super block dominator graph, SBDG)可以用二元組?S,D表示,其中S是節(jié)點集合,D是邊集合。圖中的節(jié)點S?mS表示程序的一個超級塊。邊S?m,S?nE表示超級塊S?m直接支配超級塊S

11、?n。對于給定的超級塊支配圖,刪除不影響其節(jié)點可達性的邊13,即可得到它的等效圖。以下本文中所說的超級塊支配圖均指其等效圖性質(zhì)5 超級塊支配圖上,孩子節(jié)點執(zhí)行了,意味著父節(jié)點也就執(zhí)行了。  證明 假設(shè)存在超級塊S?m=n?mi?|iC?m,超級塊S?n=n?ni?|iC?n,且S?m是S?n的孩子節(jié)點。根據(jù)超級塊支配關(guān)系定義,S?n中必然存在一個基本塊(可設(shè)為n?ni?)直接前支配(或者后支配)S?m中另一個基本塊(可設(shè)為n?mi?)。根據(jù)基本塊支配關(guān)系定義,n?mi?如果執(zhí)行, n?ni?就必然執(zhí)行,且由性質(zhì)2可知,n?mi?如果執(zhí)行,則S?m中所有的節(jié)點必然執(zhí)行;n?ni?如果執(zhí)

12、行,則S?n?中所有節(jié)點必然執(zhí)行,故該性質(zhì)得證。 以圖1(a)的例子程序為例,其程序控制流圖如圖1(b)所示,根據(jù)支配節(jié)點算法14,可得其基本塊支配圖為圖1(c)。根據(jù)定義2,圖1(c)中的強連通區(qū)域為超級塊,如基本塊1、2、10組成超級塊,詳細的超級塊集合如圖1(d)所示,且可得超級塊支配圖為圖1(e),其等效圖為圖1(f)。 1.2 插裝方法 在普通的覆蓋測試工具實現(xiàn)中,要獲取各基本塊的覆蓋信息就必須對所有基本塊都進行插裝,如對圖1的例子,需要對基本塊110全部進行插裝,共10個探針。而利用以上超級塊定義與性質(zhì),則只需要對一部分基本塊進行插裝即可獲得所有基本塊覆蓋信息。依據(jù)超級塊性質(zhì)4,

13、要獲得某超級塊中基本塊覆蓋信息,只需在同一個超級塊內(nèi)插入一個探針。同時在超級塊支配圖上,依據(jù)性質(zhì)5可得,如果一個測試用例覆蓋超級塊?U的同時,還必須至少覆蓋U的一個孩子節(jié)點,那么U?就不需要插裝,這些做法可減少冗余插裝。例如圖1的例子程序,采用超級塊支配圖插裝,則需插裝的基本塊為1、4、7、8共四個探針?？梢?采用超級塊支配圖的方式,可明顯減少插裝探針的數(shù)量。 2 SAT工具的總體設(shè)計 SAT是一款利用超級塊支配圖插裝實現(xiàn)的C語言塊覆蓋測試工具,整體設(shè)計如圖2所示。主要功能組件有: a)詞法語法分析器。詞法語法器讀入預(yù)處理后的C語言,構(gòu)建程序語法分析樹,并保存各個記號(token)的行列信息。

14、其中C語言經(jīng)過預(yù)處理后已展開為無注釋行,完成宏定義的替換,#include文件已經(jīng)插到文件相應(yīng)位置處,只保留條件編譯為真的代碼文件。 b)靜態(tài)分析器。通過遍歷語法分析樹,根據(jù)程序結(jié)構(gòu)將源程序按基本塊為單元進行劃分,并將基本塊的靜態(tài)信息按照一定的編碼格式保存于靜態(tài)文件(sat文件,數(shù)據(jù)編碼如圖3(a)中,同時獲取程序控制流信息,為自動生成測試結(jié)果作?準備。? c)代碼插裝器。根據(jù)程序控制流信息獲取各函數(shù)的超級塊支配圖,并依據(jù)插裝算法確定探針插裝位置,在語法分析樹的相應(yīng)位置插入特殊的探針節(jié)點,最后從插裝后的語法分析樹中反解析出插裝后的代碼。? d)覆蓋分析器。通過對比靜態(tài)文件和跟蹤文件獲取覆蓋信息

15、,定位未覆蓋代碼,報告測試覆蓋率。 3 主要功能模塊的實現(xiàn) 3.1 詞法、語法分析器 詞法語法分析器是代碼覆蓋測試工具的重要組件。首先它根據(jù)詞法規(guī)則將源程序中的若干字符劃分為若干記號13, 為了便于提取程序塊的靜態(tài)信息,詞法語法分析器記錄了各記號的靜態(tài)信息(行列信息)然后根據(jù)記號識別相應(yīng)的語法規(guī)則,并執(zhí)行相應(yīng)的語義動作,建立源代碼的語法分析樹。其工作及實現(xiàn)原理如圖4所示。 在SAT中,詞法分析器采用手工編程實現(xiàn)。語法分析器是通過編寫C語言語法說明文件,利用Bison15工具處理后得到的。其中,語法說明文件中定義了語法結(jié)構(gòu)規(guī)則以及語法分析樹的語句,其核心是由一條或多條語法規(guī)則構(gòu)成的規(guī)則段。該規(guī)則

16、段定義了輸入流應(yīng)滿足的語法規(guī)則以及相應(yīng)的動作?程序。? 3.2 靜態(tài)分析器 靜態(tài)分析器通過掃描語法分析樹,確定基本塊開始和結(jié)束的邊界,進行程序基本塊的劃分,劃分算法如下所示: a)確定入口語句,所用規(guī)則為: (a)程序或者函數(shù)的入口點是入口語句; (b)任何能由條件轉(zhuǎn)移或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句都是入口語句; (c)緊跟在轉(zhuǎn)移語句或條件轉(zhuǎn)移后面的語句是入口語句。 b)函數(shù)調(diào)用語句單獨作為一個基本塊。 c)對于每個入口語句,其基本塊由它和直到下一個入口語句(但不包含該入口語句)或程序結(jié)束的所有語句組成。 靜態(tài)分析器將各個基本塊的所在文件、行、列信息保存于靜態(tài)文件中,同時保存基本塊的控制流關(guān)系,

17、以獲取各函數(shù)的程序控制流圖。 3.3 代碼插裝器 從覆蓋測試工具的使用目的上來看,插入的探針越多,可獲得的有效覆蓋信息就越詳細。同時代碼插裝必然會對源代碼程序的執(zhí)行效率產(chǎn)生影響,所以要盡可能地避免插裝冗余,通過選擇合適的探針插裝位置可以減少插裝的冗余度。依據(jù)靜態(tài)分析器獲取的程序控制流信息,SAT可獲得程序超級塊支配圖,并確定需要插裝的基本塊,即在超級塊支配圖中,對于給定的超級塊?U?,可以通過兩條準則判定是否需要插裝:a)如果?U的孩子節(jié)點少于兩個,則U?需要插裝;b)如果存在一條從程序入口到出口的路徑,能夠不經(jīng)過超級塊支配圖中?U的任何孩子節(jié)點,則U?需要被插裝。詳細判定算法如下12: pr

18、obe(U) if U has fewer than two children in the super block dominator graph then return true; mark all nodes in the control flow graph as unvisited; mark a respresentative basic block, r, of U as unvisited; mark a representatives of the children of U in the super block dominator graph as visited; vis

19、it_predecessors (r); visit_successors (r); if both the entry and the exit nodes of the flow graph are marked as visited then return true; else return false; visit_predecessors (n) for each immediate predecessor, p, of node n in the flow graph do if p is not marked as visited then mark p as visited;

20、visit_predecessor(p); visit_successor ( n) for each immediate successor, s, of node n in the flow graph do if s is not marked as visited then   mark s as visited; visit_predecessor(s); ? 針對需要插裝的每一個基本塊,SAT插裝器在語法分析樹上選擇合適的位置,進行探針函數(shù)的插裝,最后將插裝后的語法分析樹解析成插裝后的源代碼。插裝后的源碼作為新的測試代碼進行編譯。編譯時,插裝探針函數(shù)以靜態(tài)庫的方式連入被測

21、程序,生成帶有插裝探針的可執(zhí)行文件; 測試時,通過運行該可執(zhí)行文件,插裝的探針語句可將所監(jiān)測塊的執(zhí)行情況按照一定編碼格式保存于動態(tài)跟蹤文件(.trace文件,數(shù)據(jù)編碼如圖3(b)中。下面依據(jù)獲取基本塊動態(tài)跟蹤信息的需要,討論插裝探針函數(shù)的設(shè)計與插裝位置選擇。? 1)初始化探針,int level=int xSaT(int oldlevel,0) 插入于每個函數(shù)的起始位置,返回變量level來惟一標(biāo)志所在函數(shù)層次,記錄函數(shù)調(diào)用深度,用于解決函數(shù)調(diào)用時基本塊覆蓋信息的提取,識別待測元素所在函數(shù)層次關(guān)系。 2)塊插裝探針,int xSaT(int level, int blk) 其中l(wèi)evel為所在

22、函數(shù)的層次;blk表示該塊的序號,每執(zhí)行一次則根據(jù)上文介紹的編碼規(guī)則在動態(tài)跟蹤文件中更新該塊的被執(zhí)行次數(shù)。對于順序語句,探針插入于需插裝的基本塊之前;對于分支語句,為了使引入的探針語句不影響源代碼語義,采用逗號運算符“,”把探針語句和分支語句的條件表達式連接起來,構(gòu)成逗號表達式,形式如下: 探針語句,條件表達式 該逗號表達式的計算順序是從左到右,先計算探針語句,然后計算分支表達式,逗號表達式的值為最右邊的條件表達式的值,從而插入后不會影響原代碼的語義。 3.4 覆蓋分析器 覆蓋分析器負責(zé)讀入靜態(tài)文件和動態(tài)跟蹤文件生成覆蓋測試報告,包括以下兩個功能: a)定位未覆蓋的代碼段。依據(jù)超級塊的性質(zhì)4和

23、5,并結(jié)合動態(tài)跟蹤文件,可獲取未覆蓋的基本塊,同時結(jié)合靜態(tài)文件中的基本塊行列信息,可定位為未覆蓋的代碼段。 b)測試覆蓋率報告。對各個函數(shù)進行測試覆蓋率計算,方法如下: 測試覆蓋率=至少被執(zhí)行一次的基本塊數(shù)量函數(shù)中基本塊總數(shù)×100% 4 應(yīng)用結(jié)果分析 在完成SAT系統(tǒng)設(shè)計與實現(xiàn)后,本文用一個實例展示SAT的功能,并對SAT的探針插裝個數(shù)及探針插入對程序執(zhí)行時間的影響進行了實驗測試。 4.1 功能分析 本文以三角形分類程序為例介紹SAT的功能,源代碼如下所示: #include stdio.h int triang (int i ,int j ,int k) int tri = 0;

24、 if (i<=0)(j<=0)(k<=0) return 4; if (i=j)tri+=1; if (i=k)tri+=2; if (j=k)tri+=3; if (tri = 0 ) if (i+j<=k)(j+k<=i)(i+k<=j) tri = 4 ; else tri =1; return tri; if (tri > 3 ) tri =3; else if (tri = 1 )&&( i +j > k ) tri =2; else if(tri = 2 )&&( i +k > j ) tri

25、=2; else if(tri = 3 )&&( j +k > i ) tri =2; else tri = 4; return tri ; void main () int a,b,c,t; printf ("enter 3 integers for sides of triangles n"); scanf ("%d %d %d",&a,&b,&c); t=triang(a,b,c); if (t=1) printf ("triange is scalene n"); else if

26、(t=2) printf ("triange is isoscelesn"); else if (t=3) printf ("triange is equilateraln"); else if (t=4) printf ("this is not triange n"); 由于篇幅關(guān)系,這里列出插裝后的部分代碼,如下所示: if ( i <= 0 )(xSaT(sat,2),( j <= 0 ) )(xSaT(sat,3),?( k <= 0 ) )? xSaT(sat,4); return 4 ; 其中:xSaT

27、是探針函數(shù),sat為表示函數(shù)層次的變量。通過執(zhí)行一個測試例子:輸入整數(shù)11、12、13,調(diào)用SAT工具得到未覆蓋代碼如圖5(a)中深色部分代碼,顯示執(zhí)行上述用例后測試覆蓋率如圖5(b)所示。 4.2 SAT性能分析 目前的代碼覆蓋工具(如ATAC等)都是通過對每個基本塊進行插裝來獲取覆蓋信息。相比于這些工具,SAT采用了超級塊支配圖來選擇插裝探針的位置,在不丟失覆蓋信息的情況下減少了探針的個數(shù)。為此本文選擇四組軟件測試文獻中常用的測試程序7,16,將SAT與ATAC、Dyninst等工具的插裝方式進行了實驗比對,結(jié)果如表1所示。從表中可以看出,SAT插入的探針個數(shù)最少, 這將大大減少程序插裝給

28、被測程序造成的負面影響。 表 1 插裝探針對比 被測程序基本塊個數(shù) 探針插裝探針個數(shù) ATACDyninstSAT schedule1531535451 prinf_token2242249189 spiff1 3121 312505474 space2 7502 750793739 探針的引入,必然對被測程序的執(zhí)行效率產(chǎn)生影響,本文選擇spiff程序,將SAT與ATAC工具進行執(zhí)行時間實驗,分別對比在無插裝、使用ATAC插裝和使用SAT插裝三種情況下,執(zhí)行相同的測試用例的執(zhí)行時間,結(jié)果如表2所示。從表中可以看出,與ATAC相比,SAT在執(zhí)行時間上減少了31%。 表 2 執(zhí)行時間比較 被測程序

29、無插裝運行時間/sATAC插裝執(zhí)行時間/sSAT插裝后執(zhí)行時間/s時間減少/% 5 結(jié)束語 本文設(shè)計并實現(xiàn)了一種基于超級塊插裝的C語言自動化測試工具SAT,通過選定插裝位置和優(yōu)化設(shè)計插裝策略,有效地減小了探針代碼對程序運行性能的影響,并實現(xiàn)了未覆蓋代碼定位,測試覆蓋率自動化分析。  參考文獻: 1FEWSTER M, GRAHAM D. Software test automationM.S.l.: Addison-Wesley Professional,1999. 2YANG Qian, LI J J, WESISS D. A survey ofcoverage based tes

30、ting toolsC/Proc of International Workshop on Automation of Software Test. 2006:99-103. 3HORGAN J R, LONDON S. A data flow coverage testing tool for CC/Proc of the 2nd Symposium on Assessment of Quality Software Development Tools.1992:2-10. 4FRANKL P G, WEYUKER E J. An applicable family of data flow

31、 testing criteriaJ.IEEE Trans on Software Engineering, 1998,14(10):1483-1498. 5LI J J, WEISS D M, YEE H. An automatically-generated run-time instrumenter to reduce coverage testing overheadC/Proc of the 3rd International Workshop on Automation of Software Test.2008:49-56. 6TIKIR M M, HOLLINGSWORTH J K. Efficient instrumentation for code coverage testingC/Proc of ACM SIGSOFT International Symposium on Software Testing and Analysis.2002:86-96. 7LYU M R, HORGAN J R, LONDON S. A coverage analysis tool for the effectiveness of software testingJ. IEEE Trans on Reliability,1994,43(4):527-5