基于超級塊支配圖插裝的軟件測試工具設計與實現

摘 要:通過超級塊支配圖來分析軟件測試探針的合理插裝位置，可有效地減少插裝探針數量，降低代碼插裝對程序的影響。基于超級塊支配圖的代碼插裝原理，設計一種針對C語言的軟件自動測試工具(SAT)，介紹了該工具中詞法語法分析器、靜態分析器、代碼插裝器等主要功能模塊的具體實現方案，同時對SAT的插裝性能進行了分析。

關鍵詞:代碼插裝; 覆蓋測試; 超級塊支配圖

中圖分類號:TP311 文獻標志碼:A

文章編號:1001-3695(2010)03-0923-05

doi:10.3969/j.issn.1001-3695.2010.03.032

Design and implementation 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 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 instrumented 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 dominator graph

軟件測試是保證軟件質量的重要手段，可分為手工測試和自動化測試。隨著軟件規模的不斷擴大，手工測試已無法滿足測試的需要，應用測試工具進行自動化測試能夠完成許多手工測試難以實現的測試，達到有效縮短軟件開發及測試時間、保證軟件質量的目的[1]，已成為軟件質量和可靠性保證的關鍵技術手段。代碼覆蓋測試工具是目前軟件測試的重要工具之一[2]，它提供有效的覆蓋信息用于量度測試完整性[3]和輔助測試員設計測試用例，從而提高測試效率。

代碼覆蓋測試工具通常是對被測試的元素[4](如語句、程序塊、分支、謂詞、分支-謂詞等)進行探針插裝，通過運行帶有探針的被測程序獲得程序運行的執行信息。但探針的插入會對被測程序產生負面影響，如使被測試程序的代碼量增加、執行效率降低等。因此如何設計合理的插裝策略、減少插裝探針對被測程序的影響，是覆蓋工具設計的關鍵問題之一[5，6]。近年來，多個文獻中提到多種代碼覆蓋測試工具:文獻[3，7～9]介紹了一款C語言的覆蓋測試工具ATAC，該工具支持基本塊、判定、C-uses、P-uses等多種覆蓋準則;文獻[10]介紹了基于程序插裝的動態測試技術實現的Safepro軟件測試工具，具體討論了動態測試的模型、數據流模型和動態跟蹤數據的編碼和解碼技術、插裝庫設計與插裝策略等內容，但這些工具都存在插裝探針冗余問題;文獻[6]介紹了一款利用程序控制流前支配樹信息進行插裝的測試工具Dyninst，能有效地減少探針，但由于缺乏后支配樹的信息，它的插裝策略仍然存在冗余。而超級塊支配圖融合了前支配樹和后支配樹信息，可以有效地減少插裝探針。

本文介紹了一個C語言的塊覆蓋軟件測試工具(SAT)的設計方案與實現，它采用超級塊支配圖對插裝探針個數進行有效優化，減少了代碼插裝對被測程序性能的影響，同時提供圖形化的界面，顯示各個函數的塊測試覆蓋率，定位未覆蓋的塊，便于測試員直觀地進行覆蓋分析，以補充新的測試用例，提高測試覆蓋率。

1 代碼插裝技術原理

SAT的插裝策略是基于超級塊支配圖[11]性質實現的，因此本章首先對超級塊支配圖的相關定義和性質進行闡述。

1.1 超級塊支配圖的定義及性質

定義1 基本塊支配圖是一個用二元組〈N，E〉表示的有向圖，N是節點集合，E是邊集合。支配圖中的任一個節點n∈N表示程序的一個基本塊[12];邊e∈E用有序的節點對表示，記為〈ni，nj〉，表示ni直接前支配nj(或ni直接后支配nj)。

性質1 基本塊支配圖上的祖先節點支配后裔節點。

證明 由基本塊支配圖定義可知。

定義2 對于給定的基本塊支配圖G=〈N，E〉，圖中的強連通分量的節點集合定義為超級塊。

性質2 一個超級塊可能包含一個或多個基本塊。

證明 由強連通分量的定義可知。

設基本塊支配圖中的超級塊集合為{Sm|m≤k，k=超級塊總數}，超級塊Sm具有Cm個基本塊，即Sm={nmi|i≤Cm}，可得:

性質3 SmN且∪klSm=N，Sm∩Sn=(m≤k，n≤l，m≠n)。

證明 由超級塊定義可知。

性質4 在一次執行中，如果超級塊Sm中的一個基本塊被執行，那么Sm中其他基本塊也被執行了。

證明 假設在一次執行中，超級塊Sm{nmi|i≤Cm}中的nmi節點被執行。

a)若Cm=1，結論成立。

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。根據基本塊支配關系定義[12]:基本塊nmi支配nmj，可知如果nmj被執行，則nmi也被執行;基本塊nmj支配nmi，可知如果nmi被執行，則nmj也被執行。故可得，對于超級塊中任意兩個基本塊，如果一個被執行，另一個也必然被執行。因此，超級塊中的一個基本塊被執行，那么超級塊中其他基本塊也被執行了。

定義3 如果超級塊Sm中的一個基本塊直接前支配(或者后支配)超級塊Sn中另一個基本塊，那么稱超級塊Sm直接支配超級塊Sn。

定義4 超級塊支配圖(super block dominator graph， SBDG)可以用二元組〈S，D〉表示，其中S是節點集合，D是邊集合。圖中的節點Sm∈S表示程序的一個超級塊。邊〈Sm，Sn〉∈E表示超級塊Sm直接支配超級塊Sn。對于給定的超級塊支配圖，刪除不影響其節點可達性的邊[13]，即可得到它的等效圖。以下本文中所說的超級塊支配圖均指其等效圖。

性質5 超級塊支配圖上，孩子節點執行了，意味著父節點也就執行了。

證明 假設存在超級塊Sm={nmi|i≤Cm}，超級塊Sn={nni|i≤Cn}，且Sm是Sn的孩子節點。根據超級塊支配關系定義，Sn中必然存在一個基本塊(可設為nni)直接前支配(或者后支配)Sm中另一個基本塊(可設為nmi)。根據基本塊支配關系定義，nmi如果執行， nni就必然執行，且由性質2可知，nmi如果執行，則Sm中所有的節點必然執行;nni如果執行，則Sn中所有節點必然執行，故該性質得證。

以圖1(a)的例子程序為例，其程序控制流圖如圖1(b)所示，根據支配節點算法[14]，可得其基本塊支配圖為圖1(c)。根據定義2，圖1(c)中的強連通區域為超級塊，如基本塊1、2、10組成超級塊，詳細的超級塊集合如圖1(d)所示，且可得超級塊支配圖為圖1(e)，其等效圖為圖1(f)。

1.2 插裝方法

在普通的覆蓋測試工具實現中，要獲取各基本塊的覆蓋信息就必須對所有基本塊都進行插裝，如對圖1的例子，需要對基本塊1~10全部進行插裝，共10個探針。而利用以上超級塊定義與性質，則只需要對一部分基本塊進行插裝即可獲得所有基本塊覆蓋信息。依據超級塊性質4， 要獲得某超級塊中基本塊覆蓋信息，只需在同一個超級塊內插入一個探針。同時在超級塊支配圖上，依據性質5可得，如果一個測試用例覆蓋超級塊U的同時，還必須至少覆蓋U的一個孩子節點，那么U就不需要插裝，這些做法可減少冗余插裝。例如圖1的例子程序，采用超級塊支配圖插裝，則需插裝的基本塊為1、4、7、8共四個探針。可見，采用超級塊支配圖的方式，可明顯減少插裝探針的數量。

2 SAT工具的總體設計

SAT是一款利用超級塊支配圖插裝實現的C語言塊覆蓋測試工具，整體設計如圖2所示。主要功能組件有:

a)詞法語法分析器。詞法語法器讀入預處理后的C語言，構建程序語法分析樹，并保存各個記號(token)的行列信息。其中C語言經過預處理后已展開為無注釋行，完成宏定義的替換，#include文件已經插到文件相應位置處，只保留條件編譯為真的代碼文件。

b)靜態分析器。通過遍歷語法分析樹，根據程序結構將源程序按基本塊為單元進行劃分，并將基本塊的靜態信息按照一定的編碼格式保存于靜態文件(sat文件，數據編碼如圖3(a))中，同時獲取程序控制流信息，為自動生成測試結果作準備。

c)代碼插裝器。根據程序控制流信息獲取各函數的超級塊支配圖，并依據插裝算法確定探針插裝位置，在語法分析樹的相應位置插入特殊的探針節點，最后從插裝后的語法分析樹中反解析出插裝后的代碼。

d)覆蓋分析器。通過對比靜態文件和跟蹤文件獲取覆蓋信息，定位未覆蓋代碼，報告測試覆蓋率。

3 主要功能模塊的實現

3.1 詞法、語法分析器

詞法語法分析器是代碼覆蓋測試工具的重要組件。首先它根據詞法規則將源程序中的若干字符劃分為若干記號[13]， 為了便于提取程序塊的靜態信息，詞法語法分析器記錄了各記號的靜態信息(行列信息)然后根據記號識別相應的語法規則，并執行相應的語義動作，建立源代碼的語法分析樹。其工作及實現原理如圖4所示。

在SAT中，詞法分析器采用手工編程實現。語法分析器是通過編寫C語言語法說明文件，利用Bison[15]工具處理后得到的。其中，語法說明文件中定義了語法結構規則以及語法分析樹的語句，其核心是由一條或多條語法規則構成的規則段。該規則段定義了輸入流應滿足的語法規則以及相應的動作程序。

3.2 靜態分析器

靜態分析器通過掃描語法分析樹，確定基本塊開始和結束的邊界，進行程序基本塊的劃分，劃分算法如下所示:

a)確定入口語句，所用規則為:

(a)程序或者函數的入口點是入口語句;

(b)任何能由條件轉移或無條件轉移語句轉移到的語句都是入口語句;

(c)緊跟在轉移語句或條件轉移后面的語句是入口語句。

b)函數調用語句單獨作為一個基本塊。

c)對于每個入口語句，其基本塊由它和直到下一個入口語句(但不包含該入口語句)或程序結束的所有語句組成。

靜態分析器將各個基本塊的所在文件、行、列信息保存于靜態文件中，同時保存基本塊的控制流關系，以獲取各函數的程序控制流圖。

3.3 代碼插裝器

3.3.1 探針位置的選擇

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

probe(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;

visit_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 1;

}

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;

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);

}}

3.3.2 插裝探針的設計

針對需要插裝的每一個基本塊，SAT插裝器在語法分析樹上選擇合適的位置，進行探針函數的插裝，最后將插裝后的語法分析樹解析成插裝后的源代碼。插裝后的源碼作為新的測試代碼進行編譯。編譯時，插裝探針函數以靜態庫的方式連入被測程序，生成帶有插裝探針的可執行文件; 測試時，通過運行該可執行文件，插裝的探針語句可將所監測塊的執行情況按照一定編碼格式保存于動態跟蹤文件(.trace文件，數據編碼如圖3(b))中。下面依據獲取基本塊動態跟蹤信息的需要，討論插裝探針函數的設計與插裝位置選擇。

1)初始化探針，int level=int xSaT(int oldlevel，0)

插入于每個函數的起始位置，返回變量level來惟一標志所在函數層次，記錄函數調用深度，用于解決函數調用時基本塊覆蓋信息的提取，識別待測元素所在函數層次關系。

2)塊插裝探針，int xSaT(int level， int blk)

其中level為所在函數的層次;blk表示該塊的序號，每執行一次則根據上文介紹的編碼規則在動態跟蹤文件中更新該塊的被執行次數。對于順序語句，探針插入于需插裝的基本塊之前;對于分支語句，為了使引入的探針語句不影響源代碼語義，采用逗號運算符“，”把探針語句和分支語句的條件表達式連接起來，構成逗號表達式，形式如下:

探針語句，條件表達式

該逗號表達式的計算順序是從左到右，先計算探針語句，然后計算分支表達式，逗號表達式的值為最右邊的條件表達式的值，從而插入后不會影響原代碼的語義。

3.4 覆蓋分析器

覆蓋分析器負責讀入靜態文件和動態跟蹤文件生成覆蓋測試報告，包括以下兩個功能:

a)定位未覆蓋的代碼段。依據超級塊的性質4和5，并結合動態跟蹤文件，可獲取未覆蓋的基本塊，同時結合靜態文件中的基本塊行列信息，可定位為未覆蓋的代碼段。

b)測試覆蓋率報告。對各個函數進行測試覆蓋率計算，方法如下:

測試覆蓋率=至少被執行一次的基本塊數量函數中基本塊總數×100%

4 應用結果分析

在完成SAT系統設計與實現后，本文用一個實例展示SAT的功能，并對SAT的探針插裝個數及探針插入對程序執行時間的影響進行了實驗測試。

4.1 功能分析

本文以三角形分類程序為例介紹SAT的功能，源代碼如下所示:

#include 〈stdio.h〉

int triang (int i ，int j ，int k) {

int tri = 0;

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 =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 \\");

scanf (\"%d %d %d\"，a，b，c);

t=triang(a，b，c);

if (t==1) printf (\"triange is scalene \\");

else if (t==2) printf (\"triange is isosceles\\");

else if (t==3) printf (\"triange is equilateral\\");

else if (t==4) printf (\"this is not triange \\");

}

由于篇幅關系，這里列出插裝后的部分代碼，如下所示:

if (( i <= 0 )‖(xSaT(sat，2)，( j <= 0 ) )‖(xSaT(sat，3)，( k <= 0 ) )) {

xSaT(sat，4);

return 4 ;

}

其中:xSaT是探針函數，sat為表示函數層次的變量。通過執行一個測試例子:輸入整數11、12、13，調用SAT工具得到未覆蓋代碼如圖5(a)中深色部分代碼，顯示執行上述用例后測試覆蓋率如圖5(b)所示。

4.2 SAT性能分析

4.2.1 探針數目對比

目前的代碼覆蓋工具(如ATAC等)都是通過對每個基本塊進行插裝來獲取覆蓋信息。相比于這些工具，SAT采用了超級塊支配圖來選擇插裝探針的位置，在不丟失覆蓋信息的情況下減少了探針的個數。為此本文選擇四組軟件測試文獻中常用的測試程序[7，16]，將SAT與ATAC、Dyninst等工具的插裝方式進行了實驗比對，結果如表1所示。從表中可以看出，SAT插入的探針個數最少， 這將大大減少程序插裝給被測程序造成的負面影響。

表 1 插裝探針對比

被測程序基本塊個數

探針插裝探針個數

ATACDyninstSAT

schedule1531535451

prinf_token2242249189

spiff1 3121 312505474

space2 7502 750793739

4.2.2 執行時間對比

探針的引入，必然對被測程序的執行效率產生影響，本文選擇spiff程序，將SAT與ATAC工具進行執行時間實驗，分別對比在無插裝、使用ATAC插裝和使用SAT插裝三種情況下，執行相同的測試用例的執行時間，結果如表2所示。從表中可以看出，與ATAC相比，SAT在執行時間上減少了31%。

表 2 執行時間比較

被測程序無插裝運行時間/sATAC插裝執行時間/sSAT插裝后執行時間/s時間減少/%

spiff46.45390.20270.4531

5 結束語

本文設計并實現了一種基于超級塊插裝的C語言自動化測試工具SAT，通過選定插裝位置和優化設計插裝策略，有效地減小了探針代碼對程序運行性能的影響，并實現了未覆蓋代碼定位，測試覆蓋率自動化分析。

參考文獻:

[1]FEWSTER M， GRAHAM D. Software test automation[M].[S.l.]: Addison-Wesley Professional，1999.

[2]YANG Qian， LI J J， WESISS D. A survey ofcoverage based testing tools[C]//Proc of International Workshop on Automation of Software Test. 2006:99-103.

[3]HORGAN J R， LONDON S. A data flow coverage testing tool for C[C]//Proc of the 2nd Symposium on Assessment of Quality Software Development Tools.1992:2-10.

[4]FRANKL P G， WEYUKER E J. An applicable family of data flow testing criteria[J].IEEE Trans on Software Engineering， 1998，14(10):1483-1498.

[5]LI J J， WEISS D M， YEE H. An automatically-generated run-time instrumenter to reduce coverage testing overhead[C]//Proc of the 3rd International Workshop on Automation of Software Test.2008:49-56.

[6]TIKIR M M， HOLLINGSWORTH J K. Efficient instrumentation for code coverage testing[C]//Proc of ACM SIGSOFT International Symposium on Software Testing and Analysis.2002:86-96.

[7]LYU M R， HORGAN J R， LONDON S. A coverage analysis tool for the effectiveness of software testing[J]. IEEE Trans on Reliability，1994，43(4):527-535.

[8]HORGAN J R， LONDON S. Data flow coverage and the C language[C]//Proc of Testing， Analysis， and Verification Symposium.1991:87-97.

[9]HORGAN J R， LONDON S， LYU M R. Achieving software quality with testing coverage measures[J]. Computer，1994， 27(9):60-69.

[10]孫昌愛，金茂忠.基于程序插裝的動態測試技術實現[J].小型微型計算機系統，2001，22 (12):1475-1479.

[11]AGRAWAL H. Dominators， super blocks， and program coverage[C]//Proc of the 21st Symposium on Principles of Programming Languages.1994:25-34.

[12]AHO A V， SETHI R， ULLMAN J D. Compilers:principles， techniques， and tools[M].[S.l.]: Addison Wesley， 1986.

[13]MOYLES D M， THOMPSON G L. An algorithm for finding a minium equivalent graph of a digraph[J]. Journal of the ACM， 1969， 16(3):455-460.

[14]LENGAUER T， TARJAN R E. A fast algorithm for finding dominators in a flow graph[J]. ACM Trans on Programming Languages and Systems，1979， 1(1):121-141.

[15]Bsion[EB/OL]. http://www.gnu.org/software/bison/.

[16]WONG W E， QI Y， ZHAO L. Effective fault localization using code coverage[C]//Proc of the 31st IEEE Computer， Software， and Applications Conference.2007: 449-456.