基于資源擴展活動圖的并發測試用例生成方法

朱曉程 薛 靜 楊 彬 閆雪麗

北京航天自動控制研究所，北京100854

并發軟件設計的運用已越來越普遍，它能夠提高程序執行效率與系統資源的利用率，但與此同時，由于并發軟件執行時行為的不確定性，造成軟件問題更加復雜且難以解決。并發軟件的發展對軟件測試技術提出了更高的要求，目前，并發軟件測試主要存在以下問題：

1)程序執行的不確定性，與順序執行的程序相比，可測試性低，并發問題難以定位與測試；

2)隨機輸入程序執行過程的并發事件序列的不確定性測試[1](Non-deterministic Testing)，難以保證測試的充分性，測試效果不理想；

3)控制程序執行過程并發事件序列的確定性測試[1](Deterministic Testing)，不同的同步序列生成方法選擇，可能會使得并發測試用例數量爆炸，影響測試效率。

模型驅動測試方法可實現測試前移，滿足軟件測試驗證與軟件設計開發的并行研制需求，改變軟件測試滯后于軟件開發的基本狀況。因此，基于模型的測試用例生成方法也越來越迎合該行業技術發展的要求。活動圖是UML[2](統一建模語言)中一種重要的、用于描述系統工作流程的模型圖，它描述系統活動的順序及控制流，并且能夠表述同時發生的活動。這使得活動圖適用于建立工作流模型、分析用例以及分析多線程應用程序。

數據競爭是并發軟件最常見的故障，且多數并發故障的本質是由于共享資源的不合理保護，產生數據競爭問題而造成的，因此，針對并發軟件特性提出對活動圖進行資源屬性的擴展，提出了基于資源擴展活動圖的并發測試用例生成方法，通過該方法提高并發測試用例的生成質量與效率。

1 活動圖定義及組成

UML定義活動圖是一種UML行為圖，它用于描述控制或對象流的流，重點描述流的順序和條件。

活動圖的基本組成元素包括：初始節點、活動節點、活動終點、轉換、判定、分叉與合并。

1)初始節點，用實心圓表示活動圖的開始，只有1個；

2)活動終點，1個實心圓外加1個圓圈，可以有多個；

3)活動節點，表示工作流程中執行的步驟，彼此間通過轉換連接；

4)轉換，是有向連接線，用于描述活動節點間的轉換關系，前一個活動節點結束，沿著轉換連接進入下一個活動節點執行；

5)判定，用菱形表示，輸入為一個轉換，輸出為一個轉換，判定條件用于指導下一步執行的轉換；

6)分叉與合并，都是用加粗的水平線段表示，其中分叉用于描述2個或2個以上并發運行的分支，可以用于描述程序的并發處理，分叉包括一個輸入轉換和不少于2個的輸出轉換；合并，與分叉相對出現，用于描述并發運行的分支都達到合并點后，控制才往下繼續執行，合并包括不少于2個的輸入轉換和一個輸出轉換。

活動圖基本元素表示如圖1所示：

圖1 活動圖基本組成元素

2 并發測試策略

活動、轉換是活動圖中的核心，軟件測試應至少保證每個活動及表達活動驅動關系的轉換被執行一次，即基本路徑覆蓋原則[3]。除此之外，針對并發系統，應關注共享資源使用、任務同步關系處理的考核，鑒于此，提出并發處理的測試覆蓋策略：

1)資源等待覆蓋：每一個共享資源，對于使用它的每一個并發任務至少要等待一次資源獲取；

2)資源釋放覆蓋：每一個共享資源，對于使用它的每一個并發任務至少要獲取它一次，驗證資源釋放；

3)任務同步覆蓋：具有邏輯依賴關系的任務，不同任務間的同步關系至少被覆蓋一次。

事實上，任務優先級的設置也是并發軟件設計的重要方面，隨著硬件技術的發展，多核處理器的運用對并發軟件設計產生了影響，考慮并發測試本身的難度，降低測試分析的復雜性，對于任務優先級設置及多核處理的影響的考核，可以進行單獨的測試分析與設計，在此不進行過多關注，同時為了便于活動圖對并發系統的描述，做以下抽象：

1)對共享資源的保護采用統一的方式；

2)任務間的同步操作采用統一的方式；

3)軟件執行的硬件為單核處理器；

4)任務數為可表達測試覆蓋原則及用例生成方法的最小集合。

活動圖中路徑及任務同步序列的全覆蓋，會隨著任務對象及活動的增長呈現爆發式增長，測試用例數量會相當龐大。因此需要研究一種方法，它能夠在選取較少測試用例集的情況下，具有較充分的測試驗證能力。

3 活動圖建模及測試用例生成方法

3.1 活動圖形式化定義

利用活動圖進行建模，首先應對活動圖進行形式化的符號描述，以便于算法的描述。

定義1[4]活動圖D是一個六元組，D=(A,T,W,G,F,J)，其中，

A={a0 ,a1 , …,am}是一個有限活動集;

T={t0 ,t1, …,tn}是一個有限轉換集;

W包含于(A×T)∪(T×A)是活動圖的轉換關系 ;

G(t)是轉換的條件表達式;

F={f0,f1,…,fm}是一個有限分叉集，其中元素為活動圖中并發路徑的起始點；

J={j0,j1,…,jn}是一個有限合并集，其中元素為活動圖中并發路徑的終止點；

集合A中有且只有一個元素a0∈A是初始節點；

集合A中至少有一個元素af∈A是活動終點；對于任何t′∈T,(t′,a0)不屬于W， 且(af,t′)不屬于W。

定義2活動圖中的路徑集合L是活動圖D中活動與轉換的有向序列集合：

L={l0,l1,…,ln}；

li=a0-t1->a2-t2->fi…-tx->ji-tq->ap-tp->af；

其中,ai∈A，是活動集中的元素；tj∈T，是轉換集中的元素；fi∈F，是分叉集中的元素；ji∈J，是合并集中的元素。

定義num(x)為集合X中元素個數，則對于任意路徑L，滿足num(ai)>=1；

若路徑元素li、lj中同時包含任意元素fi，則定義li與lj為并發路徑。

定義3活動圖中活動執行的優先級關系：

ai

ai>aj，表示活動ai晚于aj執行；

ai||aj，表示活動aj與aj無執行順序的制約關系，并發執行。

其中,ai、aj∈A，是活動集中的元素。

3.2 測試用例生成方法

3.2.1 基本路徑測試用例生成

為了描述基本路徑用例生成方法，舉例活動圖如下，其中，為了簡化路徑表達，將活動圖中節點進行抽象，轉化為活動圖的簡化流圖。活動圖及簡化流圖如圖2所示。

圖2 活動圖及簡化流圖示例

基本路徑覆蓋原則：活動圖中從初始狀態到終止狀態間每條路徑被覆蓋一次，對于循環路徑，只覆蓋一次。

定義活動圖簡化流圖的基本路徑集合為LS={lsi|i=0，1，…，n}；

圖2基本路徑集合LS中元素有2條，如下：

ls1=0→1→2→4

ls2=0→1→3→4。

定義測試用例集為TC={tci|,對于任意ri至少存在一個tci，ri運行時tci被執行}。

3.2.2 基本并發路徑測試用例生成

對于一個描述并發任務的活動圖，路徑測試覆蓋策略應考慮分叉以后任務間活動的關系，分叉的后繼節點(與分叉有直接連接關系的節點，順序上在分叉之后)在執行的順序關系上應進行排列組合，才能保證用例的充分性。圖3為一個描述并發系統的活動圖及簡化流圖。

圖3 并發活動圖及簡化流圖示例

基本并發路徑覆蓋原則：在基本路徑覆蓋原則的基礎之上，對分叉節點的后繼節點的排列組合進行覆蓋，如分叉后繼節點a1、a2，并發路徑的覆蓋為a1→a2，a2→a1，對分叉后非直接連接的節點a3，滿足a1

通過上述原則生成圖的12條基本并發路徑集合LS：

ls1=0→1→2→3→4→5→6→7→8

ls2=0→1→2→3→4→6→5→7→8

ls3=0→1→2→3→5→4→6→7→8

ls4=0→1→2→3→5→6→4→7→8

ls5=0→1→2→3→6→4→5→7→8

ls6=0→1→2→3→6→5→4→7→8

ls7=0→1→2→4→3→6→5→7→8

ls8=0→1→2→4→3→5→6→7→8

ls9=0→1→2→4→5→3→6→7→8

ls10=0→1→2→5→3→6→4→7→8

ls11=0→1→2→5→3→4→6→7→8

ls12=0→1→2→5→4→3→6→7→8

3.2.3 并發測試用例規模計算

通過基本并發路徑覆蓋原則生成并發測試用例，當系統中并發活動數量、并發線程數量增多，按照任意順序對活動進行排列組合，會導致用例數量急劇增長。

定義4軟件系統中并發任務數量為m，分叉節點到合并節點間活動數量為n，每個并發任務的活動數量的集合為Q={qi|qi為每個并發任務中活動的數量，1≤i≤m}。

通過基本并發路徑覆蓋原則生成的測試路徑數量為

利用圖3對上述計算公式進行驗證。

從分叉到合并節點間(即簡化流圖中)的任務數m=3；

從分叉到合并節點間的活動數n=4；

每個并發任務的活動數量為集合Q={q1=2,q2=1,q3=1}；

從上述推導中可以得出，滿足基本并發路徑覆蓋原則生成的測試用例數量隨著并發活動的總數成階乘級別增長，有限數量的并發活動即可造成測試用例數量爆炸。

3.3 基于資源擴展活動圖的并發測試用例生成方法

3.3.1 資源擴展活動圖

通過之前的實驗分析，揭露了普通活動圖描述并發系統存在缺點：

1)活動圖的抽象層次較高，能夠表述活動的并發關系，但對共享資源使用缺少描述，進而難以利用普通活動圖生成充分的并發測試用例;

2)基本路徑覆蓋的測試策略對并發任務間的同步關系及共享資源的訪問沖突的考核缺少針對性;

3)基本并發路徑覆蓋的測試策略產生的測試用例隨并發活動數成階乘級別增長。

鑒于以上分析，思考將活動圖進行擴展以達到在滿足測試充分性的條件下盡量減少用例數量的目的。對于并發任務而言，并發任務間的活動若無資源訪問、同步通信的耦合關系，二者的全排列組合不會影響軟件的操作結果及輸出，也就是說這些活動全排列組合產生的測試用例，從測試效果上存在用例重復設計。若將共享資源的使用引入活動圖中，定義擴展活動圖，不僅能夠更準確地描述并發系統工作流程，更重要的是能夠排除無耦合關系活動間的全排列組合產生的路徑，很大程度上減少測試用例數量，提高測試的效率及準確性。

在活動圖中引入資源狀態，資源狀態為用于描述被多個活動訪問的共享資源，通過引入資源狀態描述并發任務間與資源相關的耦合關系，以排除無耦合關系的并發測試路徑。

定義5資源擴展活動圖Dr是一個七元組，Dr=(A,T,W,G,F,J,R)，其中，R為活動圖中共享資源狀態集合，R={ri|ri在活動圖中至少被2個并發活動所訪問,i=1,2…,n}。其余元素定義同定義1。

將圖3進行資源擴展，假使圖中動作狀態a2、a3間的共享資源為r1，a4、a5間的共享資源為r2，資源擴展活動圖見圖4左側。基于前文所示的并發測試覆蓋策略，使每個任務對資源的訪問至少考核一次資源等待、一次資源釋放操作。資源擴展活動圖的簡化流圖應凸顯共享資源的并發訪問，簡化無資源關聯的任務關系。因此，簡化流圖的繪制相對于普通活動圖做以下改變：

1)以資源作為中心，簡化流圖的數量與資源的數量一一對應；

2)并發關系不再以“分叉”為起點，改以共享資源為起點；

3)無資源關聯的并發活動由并發結構變換為順序結構；

4)活動在不同簡化流圖中按照一致順序排列；

5)圖中并發活動按照BFS(廣度優先搜索)遍歷順序編號。

圖4左側資源擴展活動圖通過以上規則繪制簡化流圖如圖4右側。

圖4 資源擴展活動圖及簡化流圖示例

3.3.2 資源擴展活動圖用例生成

資源擴展活動圖的每一個簡化流圖與一個共享資源一一對應，對每一個子流圖只需關注該圖中資源的并發使用關系，對于并發訪問的活動，無需進行活動的全排列組合，只通過循環排列即可滿足一次資源等待、一次資源釋放的測試覆蓋策略。所謂循環排列，即將訪問同一資源的活動用一個循環隊列來存儲，記錄循環隊列原始頭，順序從隊列頭訪問置隊列尾，形成一次排列，結束后，將頭元素出隊循環插入隊尾，按此規律生成全部排列直至再次訪問到原始頭結束。此過程示意圖如圖5。

圖5 測試路徑生成示意圖

通過上述用例生成方法，生成圖4的各子流圖中并發測試路徑集合。

子流圖1：

ls11=0→1→2→3→4→5→6→7 (首路徑)

ls12=0→1→3→2→4→5→6→7

子流圖2：

ls21=0→1→2→3→4→5→6→7 (首路徑)

ls22=0→1→2→3→5→4→6→7

按照3.3.1中資源擴展活動圖的繪制原則產生各簡化流圖中的首路徑是彼此重復的，生成的測試路徑數量總和應為各子流圖路徑數量減去重復路徑數。將子流圖1和2的測試路徑取并集，獲得圖4測試路徑集合：

ls1=0→1→2→3→4→5→6→7

ls2=0→1→3→2→4→5→6→7

ls3=0→1→2→3→5→4→6→7

實際上，ls2與ls3可以通過ls4= 0→1→3→2→5→4→6→7進行替代，進一步減少用例數量。但活動與資源的關系可以是無序網型拓撲結構，合并方式靈活，但會增加用例設計的復雜性，考慮用例生成效率，不再對路徑做進一步復雜合并，本方法已較大程度地篩檢了重復用例數，提高了用例設計的效率。如此例相較于未經資源擴展的活動圖3(測試路徑數12個)，生成的測試路徑數明顯減少。

在測試用例數與測試路徑數一一對應的關系下，通過上述方法生成的測試用例數量：

其中，R為共享資源集合；num(R)為集合元素總數；pi∈P，P={pi|pi為訪問共享資源ri的活動數}。

從上述推導中可以得出，基于資源擴展活動圖的并發測試用例生成方法生成的用例數量與訪問共享資源的活動總數為線性關系，相較于未擴展的活動圖的基本路徑覆蓋方法，用例數量明顯減少，有效地防止了測試用例數量爆炸的問題。

4 實例驗證

選取航天某型號主控軟件的部分功能作為實例驗證該方法的有效性。主控軟件的時間同步功能為：接收上級指控系統的時間信息，更新本機時間，將更新后時間發送至本系統內其他設備，同時軟件界面更新時間顯示。與該功能相關的并發任務有4個，分別是接收信息任務RecvTask、發送任務SendTask、軟件功能主任務MainTask及界面更新任務UpdateTask，各任務功能均為循環執行，在程序退出前不結束執行。

該功能相應的活動圖見圖6。

圖6 主控軟件時間同步功能活動圖

按照本文定義4，生成測試路徑的相關參數值分別為：

并發任務數量m=4；

分叉節點到合并節點間活動數量n=6；

每個并發任務的活動數量的集合Q={1，3，1，1}。

按照改進前的用例生成方法計算測試用例數量N=120。

按照本文的方法生成測試用例，分析程序共享資源的使用情況，見表1。

表1 資源使用情況

繪制資源擴展活動圖，見圖7。

圖7 主控軟件時間同步功能資源擴展活動圖

通過繪制資源擴展活動圖的簡化流圖，獲得測試路徑包括4條，如下：

ls1=0→1→2→3→4→5→6→7→8

ls2=0→1→7→3→4→5→6→2→8

ls3=0→1→2→4→3→5→6→7→8

ls4=0→1→2→3→4→6→5→7→8

使用上述測試路徑對被測軟件該部分處理進行考核，發現界面更新的時間值顯示異常，存在時間值為0的閃現情況。問題發生的原因為MainTask在更新時間值時首先將存儲時間的變量復位為0，但未進行共享資源保護處理。經需求分析，此變量復位為0的處理為多余處理，刪除程序中的相關語句，該軟件問題得到解決。

通過上述實例證明，本文方法能夠在減少測試用例數量的同時生成充分、有效的測試用例。

5 結論

從生成并發測試用例的目的出發，提出了擴展活動圖的描述方法，分析基于活動圖的并發測試覆蓋策略，從而提出基于擴展活動圖的并發軟件測試用例生成方法。利用該方法生成的測試用例能夠檢測多線程軟件共享資源保護異常、任務同步缺陷等并發軟件問題，減少測試用例數量，防止用例數量爆炸，提高軟件測試質量與效率。未來，利用該方法結合擴展活動圖的形式化描述及模型工具，可以進一步研究測試用例生成的自動化工具，使本方法的應用更準確、更效率。