基于死鎖的并發(fā)類單元測試用例自動生成

臧 麗 娜

(北京化工大學信息科學與技術(shù)學院 北京 100029)

基于死鎖的并發(fā)類單元測試用例自動生成

臧 麗 娜

(北京化工大學信息科學與技術(shù)學院 北京 100029)

自動生成多線程程序的單元測試用例是一種能節(jié)約測試成本的技術(shù)。為提高并發(fā)類單元測試用例生成效率，先依據(jù)死鎖故障的特征分析出并發(fā)類中潛在的死鎖代碼，然后再針對這些代碼自動生成測試用例。實驗在7個常用Java類庫中的并發(fā)類上進行驗證。實驗結(jié)果顯示提出的方法(CTCG)不僅找到了現(xiàn)有死鎖故障，而且當檢測到死鎖故障時，其所生成的測試用例數(shù)更少，其所花費的時間更少,提高了并發(fā)類單元測試用例自動生成的效率。

并發(fā)類 死鎖 單元測試 測試用例生成

0 引 言

單元測試關(guān)注檢查和驗證組成軟件系統(tǒng)的最小單元，如類、方法、模塊等。單元測試已被證明在故障檢測中有巨大價值[1]。并發(fā)故障的檢測不僅依賴于程序的輸入，還依賴于線程的調(diào)度。由于多線程程序的不確定性[2]，使得傳統(tǒng)單元測試在檢測并發(fā)故障時的有效性較低[3]。并發(fā)類是指在一個類中，其變量或方法使用了同步機制來支持多個線程對其并發(fā)訪問。并發(fā)類是組成多線程程序的基本單元，是多線程程序開發(fā)和測試的基礎(chǔ)。A. Nistor等首次提出了對多線程代碼自動生成測試用例的方法—Ballerina[4]方法，該方法隨機地選擇并發(fā)類中的兩個方法生成測試用例，由于該方法未考慮并發(fā)故障的特點和對象進入線程前的狀態(tài)對測試結(jié)果的影響，使得該方法在檢測到一個并發(fā)故障時的開銷過大。S. Steenbuck等開發(fā)了ConSuite[5]工具來生成并發(fā)類的單元測試用例，該工具使用基于搜索的方法以線程、線程訪問的共享變量、線程訪問共享變量的同步點的所有組合為覆蓋準則，并以這種覆蓋準則為指導來生成測試用例。但該工具會隨著并發(fā)類的規(guī)模及復雜度的增加而產(chǎn)生較大的時間和空間開銷。另外Ballerian方法和ConSuite工具都只能生成包含一個被測對象的測試用例，使得其檢測故障的能力有限。M. Pradel等在研究并發(fā)類的回歸測試[6]時隨機生成并執(zhí)行大量的測試用例來衡量并發(fā)類的性能，其測試用例生成方法仍采用Ballerina方法的思想，并未對并發(fā)類的單元測試用例生成方法和效率進行改進和提升。

死鎖[7]是常見且不易被檢測的并發(fā)故障。靜態(tài)分析[8-9]和動態(tài)分析[10-11]是檢測死鎖的兩種常用方法。靜態(tài)分析方法常產(chǎn)生大量誤報，動態(tài)分析方法則由于線程間的交互問題會產(chǎn)生較大的時間開銷。一種能充分利用兩種方法優(yōu)勢的技術(shù)是將動靜態(tài)方法結(jié)合起來使用[12]，但這種方法是以測試用例存在為前提來對程序進行測試，并不考慮測試用例的生成問題。并發(fā)程序中測試用例生成的問題越來越成為并發(fā)程序測試研究的一個瓶頸。

基于此，本文針對并發(fā)類中的死鎖故障，提出了一種單元測試用例自動生成方法CTCG。本文的最小可測單元為并發(fā)類中的方法，首先依據(jù)死鎖故障特征對并發(fā)類進行分析，以得到潛在死鎖對，然后再針對潛在死鎖對生成測試用例，最后通過實驗，驗證了本文方法的有效性。

1 相關(guān)工作

死鎖[7]是指兩個或兩個以上的線程(進程)在執(zhí)行過程中，因爭奪資源而造成的一種相互等待的現(xiàn)象，若無外力作用，它們都將無法推進下去。

鎖序圖是一個描述了線程對鎖的占用請求關(guān)系的有向圖，用G=(V,E)表示，其中頂點V表示鎖結(jié)點集，一條從結(jié)點l1指向結(jié)點l2的有向邊e表示線程在占有鎖l1時去請求鎖l2，E是e的集合。

別名指多個變量共享同一存儲區(qū),這些共享內(nèi)存的變量互為別名。在面向?qū)ο蟪绦蛑校饎e名的原因有對象表達式的創(chuàng)建，寫實例域表達式的創(chuàng)建，讀實例域表達式創(chuàng)建，直接賦值表達式的創(chuàng)建，函數(shù)調(diào)用。又因是對類進行分析，所以本文采用對象敏感、內(nèi)容敏感、流不敏感的別名分析方法[13]。

門鎖：假設(shè)線程t1在請求占有鎖l1時，必須先請求占有鎖l，線程t2在請求占有鎖l2時，必須先請求占有鎖l，則稱鎖l為線程t1中鎖l1，線程t2中鎖l2的門鎖。用t→lΔL表示線程t在請求占有鎖l時，其已占有的鎖集為L，下面的公式表示兩個線程在請求占有鎖時是否有門鎖。

guarded(t1,l1,t2,l2)iff?L1,L2

t1→l1ΔL1∧t2→l2ΔL2?alias(L1,L2)

(1)

2 死鎖分析

要有效地生成測試用例來觸發(fā)并發(fā)故障，可通過生成較少的測試用例且又不影響檢測質(zhì)量的方法來檢測死鎖故障。

2.1 死鎖分析的前置條件

2.2 形參型死鎖

并發(fā)類中，依據(jù)變量的不同可分為不同的鎖變量。全局鎖是指類的某全局量被作為鎖變量。對象鎖是指在編程中創(chuàng)建的實例對象調(diào)用方法被多線程訪問，在任一個時刻，只有一個線程可以訪問該對象。如在Java中，同步方法的this對象即為對象鎖。形參鎖是指類中方法的形參在方法體內(nèi)由于調(diào)用了同步方法而變成了鎖變量。在本文中，如果類的某成員變量在方法體中被作為了鎖變量，那么該成員變量被視為形參鎖，因為絕大部分的成員變量都可以通過set方法來傳入?yún)?shù)。

定義1 形參型死鎖 當用戶傳入了某些特定參數(shù)后，使得程序出現(xiàn)了死鎖，稱這種死鎖為形參型死鎖。

如對java.lang.StringBuffer類，當用戶進行了如圖1的調(diào)用時，在線程t1中，變量a是對象鎖，變量b是形參鎖，線程t1在請求完鎖a后又去請求鎖b，在線程t2中，變量b是對象鎖，變量a是形參鎖，線程t2在請求完鎖b后又去請求鎖a，此時程序便出現(xiàn)了死鎖。形參型死鎖一方面和用戶傳入的參數(shù)有關(guān)，另一方面還和對象鎖相關(guān)，但不會和全局鎖發(fā)生死鎖。

圖1 形參型死鎖示例

形參型死鎖模式：兩個線程t1、t2分別調(diào)用了并發(fā)類CUT中的兩個方法m1(…,pi,…)、m2(…,pj,…)，且兩個線程中的調(diào)用對象不同，每個線程在請求占有了對象鎖后，又去請求占有形參鎖pi和pj，且pi和pj的類型和CUT的類型匹配，此時稱程序存在形參型死鎖。

2.3 死鎖檢測

定義2 占用請求關(guān)系 用四元組(t,m,li,lj)表示占用請求關(guān)系，t為線程，m為線程t調(diào)用的方法，li和lj表示鎖變量，占用請求關(guān)系表示在某個時刻，線程t在調(diào)用方法m時，在占有了鎖li后又去請求占有鎖lj，其中稱是隸屬于方法m的鎖變量對。

定義3 前序鎖 線程t在調(diào)用方法m時，在請求占有鎖l之前已經(jīng)占有的鎖稱為鎖l的前序鎖，鎖l的前序鎖集用Ll表示。

類型匹配：如果類C1是類C2的子類，或類C1和類C2是同一個類，或類C1是類C2的父類，則稱類C1和類C2類型匹配。

定義4 潛在死鎖對 在兩組占用請求關(guān)系(t1,mi,li,lj)和(t2,mj,ls,lk)中，如果鎖變量對和有構(gòu)成死鎖環(huán)的可能，則稱{(t1,mi,li,lj),(t2,mj,ls,lk)}為一個潛在死鎖對。

對并發(fā)類CUT，由其源碼可得到各個方法的鎖序圖，有方法mi和mj的鎖序圖gi和gj，可枚舉出圖gi和gj中的鎖變量對，用和表示。如果鎖li和鎖lk的前序鎖集交集不為空，則無潛在死鎖。若交集為空，則如果鎖li、lj、ls和lk均不為形參鎖變量且li和ls別名、lj和lk別名時，有潛在死鎖，稱這類死鎖為普通死鎖；如果鎖li、lj、ls和lk中有一個形參鎖，設(shè)為鎖li，如果鎖lj和lk別名且鎖li和ls的類型相匹配，有潛在死鎖，稱這類死鎖為混合死鎖；如果鎖li、lj、ls和lk中有兩個及以上形參鎖變量，假設(shè)li和lk為形參鎖，那么當li和ls類型匹配、lj和lk類型匹配時，有潛在死鎖。具體算法如下所示:

Algorithm: ProDeadLockDetect

輸入：并發(fā)類CUT

輸出：潛在死鎖對PDL

0:PDL←φ

1: for allmi∈CUTdo

2:gi←StaticAnalysis(obi,CUT)

//得到方法mi的鎖序圖，obi是方法mi的調(diào)用對象

3: for allli∈gi.Vdo

//鄰接表存儲鎖序圖

4: for alllj∈gi.Vdo

5:l←lj

6: ifl.next=lido

7:Lli←Lli∪{l}

//得到前序鎖

8:l←l.next

9: end for

10: for allli∈gi.Vdo

11: ifli.next=φthen

12: Delete(li,gi)

//刪除gi中的單結(jié)點

13: else do

14:lj←li

15:pli←pli∪{lj,lj.next}

//得到鎖變量對

16:lj=lj.nextwhileli.next=φ

17: end for

18: end for

19: for all ∈pl∧∈pldo

20: ifLli∩Llk≠φdo

// 無門鎖

21: if mayalias(li,ls)∧mayalias(lj,lk) do

// 普通死鎖

22:PDL←PDL∪{(t1,mij,li,lj),(t2,mks,lk,ls)}

23: if.hasParaLock(li,ls)∧ matchtype(li,ls)∧mayalias(lj,lk).

// 混合死鎖

24: if.hasParaLock(lj,lk)∧matchtype(lj,lk)∧ mayalias(li,ls)

// 混合死鎖

25:PDL←PDL∪{(t1,mij,li,lj),(t2,mks,lk,ls)}

26: if hasParaLock(li,ls)∧matchtype(li,ls)∧

27: hasParaLock(lj,lk)∧matchtype(lj,lk)

// 形參型死鎖

28:PDL←PDL∪{(t1,mij,li,lj),(t2,mks,lk,ls)}

29: end for

3 測試用例生成

并發(fā)類CUT的單元測試用例由串行前綴和并發(fā)后綴兩部分組成。串行前綴初始化CUT，并調(diào)用CUT中的方法以使CUT的實例達到一個可能會觸發(fā)后綴中死鎖故障的狀態(tài)。并發(fā)后綴是線程調(diào)用潛在死鎖對中的方法，是可以和其他后綴并發(fā)執(zhí)行的調(diào)用序列，每個測試用例有兩個后綴，每個后綴分別調(diào)用潛在死鎖方法對中的一個方法，如此一個測試用例可用一個三元組表示(p,s1,s2)，p表示前綴，在后綴執(zhí)行之前執(zhí)行，s1和s2表示后綴。圖1即為一個測試用例的例子，其中0-1行為串行前綴，2-13行為并發(fā)后綴。每個測試用例可用一系列的方法調(diào)用序列(c1,c2,…,cn)表示，其中每個方法調(diào)用ci由一個方法簽名、一個輸入變量列表和一個輸出變量組成。調(diào)用的輸入變量表示傳遞給方法的參數(shù)，輸出變量表示方法調(diào)用的返回值。本文方法規(guī)定構(gòu)造函數(shù)調(diào)用作為方法調(diào)用，其輸出變量是一個新的對象，域訪問作為方法其潛在的輸入變量是使用對象，輸出變量為域值。如果每個調(diào)用cj的輸入都是調(diào)用ci的輸出，且i

串行前綴生成：對潛在死鎖對PDL中每個元素{(t1,mij,li,lj),(t2,mks,lk,ls)}若為普通死鎖類型，生成一個實例對象ob，且ob調(diào)用使得li和ls別名、lj和lk別名的方法；若為混合死鎖類型，生成一個實例對象ob，ob調(diào)用使得li和ls別名的方法，同時將對象lk傳遞給參數(shù)lj?；騩b調(diào)用使得lj和lk別名的方法，同時將對象livi傳遞給參數(shù)ls；若為形參型死鎖類型，生成兩個實例化對象obi和obj，如果形參鎖是CUT的成員變量，對象obi和obj還要調(diào)用CUT中可為形參鎖賦值的方法，將obi作為參數(shù)傳給obj調(diào)用的賦值方法，將obj作為參數(shù)傳給obi調(diào)用的賦值方法。

并發(fā)后綴生成：串行前綴中若生成一個實例化對象ob，則在后綴s1和s2中，對象ob只需分別調(diào)用{(t1，mi，vi，vj),(t2，mj，vk，vs)}中的方法mi和mj；串行前綴中若生成了兩個實例化對象obi和obj且形參鎖變量非CUT的成員變量，則將obi作為形參鎖的實參傳給obj.mj，將obj作為形參鎖的實參傳給obi.mi。

除前文已確定的參數(shù)，其余參數(shù)采用其他自動化測試用例生成方法中的參數(shù)生成策略[4]。

4 實驗驗證

為驗證本文方法CTCG的有效性，提出了以下2個問題進行實驗驗證：

1) 基于靜態(tài)分析的潛在死鎖代碼分析是否找到了潛在死鎖故障？

2) 測試用例生成的效率如何？

4.1 實驗設(shè)計

為驗證上述問題，本文借助Randoop[16]串行測試用例生成工具和JPF(Java PathFinder)[17]并發(fā)故障檢測工具來實現(xiàn)并發(fā)測試用例的生成和死鎖故障的檢測。實驗以7個常用Java類庫中的類為被測對象，其所在類庫的版本信息、代碼行數(shù)、使用鎖的方法數(shù)、總方法數(shù)及死鎖信息，如表1所示，其中最后一列表示死鎖在jdk 的bug庫中id或相關(guān)文獻對其描述。本文對每個發(fā)現(xiàn)的潛在死鎖對都做了測試用例生成實驗，每次以生成的測試用例檢測到死鎖故障或限定時間到達來結(jié)束本次生成。本文采用邊生成邊執(zhí)行的策略來生成的執(zhí)行測試用例。

表1 被測類基本信息

4.2 實驗結(jié)果與分析

本文通過與并發(fā)類中已知的死鎖故障進行對比來驗證本文靜態(tài)分析方法的效果。表2給出靜態(tài)結(jié)果分析表，從表中可看出本文所采用的靜態(tài)分析方法雖然找到了潛在的死鎖故障，但還是有一定的誤報。誤報的原因是本文的分析是基于可能的別名關(guān)系，這使得一些可能的別名關(guān)系并不能實現(xiàn)，還有一些測試用例在執(zhí)行時JPF運行超出內(nèi)存。

表2 靜態(tài)分析結(jié)果表

圖2給出了每個CUT在檢測到死鎖故障時所生成的測試用例。由于Ballerina方法不加分析，直接對被測類生成測試用例，使得其檢測到一個故障所生成的測試用例數(shù)隨被測類方法數(shù)呈指數(shù)級上升，如對Logger類，其要生成約105～106個測試用例，耗時500個小時才能檢測到死鎖，所以本文未和其進行對比。從圖3可知，檢測到一個死鎖所要生成的測試用例數(shù)是可接受的。

圖3給出了檢測到死鎖時生成和執(zhí)行測試用例的時間。對比圖2發(fā)現(xiàn)雖然EventQueue類比Logger類生成的測試用例多，但其執(zhí)行時間卻比Logger類少，這是因為并發(fā)程序的執(zhí)行時間與線程間調(diào)度序列的個數(shù)及每個調(diào)度序列的長度相關(guān)，線程間調(diào)度序列的數(shù)目隨著方法對中可并發(fā)執(zhí)行原語數(shù)的增加而呈指數(shù)級的上升。當CUT比較復雜時，執(zhí)行它的測試用例所花費的時間也會較多。從實驗結(jié)果可看出檢測到一個潛在死鎖對中的死鎖故障所用的時間在20～160 s之間。

圖2 檢測到死鎖時生成的測試用例數(shù)目

圖3 檢測到死鎖時生成和執(zhí)行測試用例時間

表3給出了本文方法CTCG與ConSuite方法在檢測到死鎖故障時所執(zhí)行的調(diào)度序列數(shù)及時間開銷。由于除了id為3、4的并發(fā)類外，其它并發(fā)類中的死鎖故障均需要兩個實例對象才能觸發(fā)，而Ballerina方法和ConSuite方法都是只能生成一個實例對象的測試用例，所以無法檢測到這些死鎖故障。Ballerina方法和ConSuite方法只生成一個實例對象的測試用例是因為它們想較多地覆蓋一個實例對象的狀態(tài)[4]。從實驗數(shù)據(jù)上看，本文方法CTCG與ConSuite相比在測試用例生成數(shù)上提升了71.1%至79.2%，平均所用時間與ConSuite方法相比節(jié)省了31.3%至45.2%。平均所用時間提升得沒有測試用例數(shù)高是因本文方法CTCG靜態(tài)分析上也花費了一定的時間開銷。

表3 調(diào)度序列和平均時間開銷表

5 結(jié) 語

為了提高針對死鎖的并發(fā)類單元測試用例生成效率，本文先對并發(fā)類進行靜態(tài)分析，以得到潛在死鎖代碼，然后再針對這些代碼自動地生成測試用例。實驗結(jié)果表明本文所用的靜態(tài)分析方法均檢測了并發(fā)類中已有的死鎖故障。在測試用例生成上，本文方法CTCG所生成的測試用例能檢測到Balleria方法和ConSuite方法無法檢測的死鎖故障，在測試用例數(shù)和時間開銷上也有較大提升。

[1] Microsoft. Unit Testing [EB/OL].[2015-11-12]. https://msdn.microsoft.com/en-us/library/aa292197(v=vs.71).aspx.

[2] Tai K C. Testing of concurrent software[C]// Computer Software and Applications Conference, 1989. COMPSAC 89. Proceedings of the, International. IEEE Xplore, 1989:62-64.

[3] Ricken M, Cartwright R. ConcJUnit: unit testing for concurrent programs[C]// International Conference on Principles and Practice of Programming in Java, Pppj 2009, Calgary, Alberta, Canada, August. 2009:129-132.

[4] Nistor A, Luo Q, Pradel M, et al. Ballerina: Automatic generation and clustering of efficient random unit tests for multithreaded code[C]// International Conference on Software Engineering. IEEE Press, 2012:727-737.

[5] Steenbuck S, Fraser G. Generating Unit Tests for Concurrent Classes[C]// IEEE Sixth International Conference on Software Testing, Verification and Validation. IEEE, 2013:144-153.

[6] Pradel M, Huggler M, Gross T R. Performance regression testing of concurrent classes[C]// Proceedings of the 2014 International Symposium on Software Testing and Analysis. ACM, 2014:13-25.

[7] Havelund K, Rosu G. Monitoring Java Programs with Java PathExplorer[J]. Electronic Notes in Theoretical Computer Science, 2001, 55(2):200-217.

[8] Agarwal R, Bensalem S, Farchi E, et al. Detection of deadlock potentials in multithreaded programs[J]. Ibm Journal of Research & Development, 2010, 54(5):3:1-3:15.

[9] Deshmukh J, Emerson E A, Sankaranarayanan S. Symbolic Deadlock Analysis in Concurrent Libraries and Their Clients[C]// ACM International Conference on Automated Software Engineering. IEEE, 2009: 480-491.

[10] Eslamimehr M, Palsberg J. Sherlock: scalable deadlock detection for concurrent programs [C]// Proceedings of the 22ndACM SISOFT International Symposium on Foundations of Software Engineering. New York, ACM. 2014: 353-365.

[11]SorrentinoF.PickLock:ADeadlockPredictionApproachunderNestedLocking[C]//InternationalSymposiumonModelCheckingSoftware.Springer-VerlagNewYork,Inc. 2015.

[12]WuZ,LuK,WangX,etal.CollaborativeTechniqueforConcurrencyBugDetection[J].InternationalJournalofParallelProgramming, 2015, 43(2):260-285.

[13]NaikM,ParkCS,SenK,etal.Effectivestaticdeadlockdetection[C]//InternationalConferenceonSoftwareEngineering.IEEEComputerSociety, 2009:386-396.

[14]LuS,ParkS,SeoE,etal.Learningfrommistakes:acomprehensivestudyonrealworldconcurrencybugcharacteristics[J].AcmSigarchComputerArchitectureNews, 2008, 36(3):329-339.

[15]PradelM,GrossTR.Fullyautomaticandprecisedetectionofthreadsafetyviolations[J].AcmSigplanNotices, 2012, 47(6):521-530.

[16]PachecoC,LahiriSK,ErnstMD,etal.Feedback-DirectedRandomTestGeneration[C]//InternationalConferenceonSoftwareEngineering. 2007:75-84.

[17]CeccarelloM,ShafieiN.ToolstogenerateandcheckconsistencyofmodelclassesforJavaPathFinder[J].AcmSigsoftSoftwareEngineeringNotes, 2012, 37(6):1-5.

[18]WilliamsA,ThiesW,ErnstMD.StaticDeadlockDetectionforJavaLibraries[J].LectureNotesinComputerScience, 2005, 3586:602-629.

AUTOMATIC GENERATION OF CONCURRENT CLASS UNIT TEST CASES BASED ON DEADLOCK

Zang Li’na

(CollegeofInformationScienceandTechnology,BeijingUniversityofChemicalTechnology,Beijing100029,China)

Automated generation of multithreaded program unit test cases is a technology to save test costs. In order to improve the efficiency of concurrent unit test case generation, the article analyzes the potential deadlock code in the concurrency class according to the characteristics of deadlock failure, and then automatically generates test cases for these codes. The experiment is carried out on the concurrent class of 7 commonly used Java class libraries. Experimental results show that the proposed method (CTCG) not only finds an existing deadlock failure, but also generates fewer test cases and less time when a deadlock failure is detected,and improve the efficiency of the automatic generation of concurrent class unit test cases.

Concurrent class Deadlock Unit test Tests generating

2016-04-21。國家自然科學基金項目(61472025，61170082)。臧麗娜，碩士生，主研領(lǐng)域：軟件測試。

TP311.5

A

10.3969/j.issn.1000-386x.2017.04.001