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

臧 麗 娜

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

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

臧 麗 娜

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

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

并發類 死鎖 單元測試 測試用例生成

0 引 言

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

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

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

1 相關工作

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

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

別名指多個變量共享同一存儲區,這些共享內存的變量互為別名。在面向對象程序中，引起別名的原因有對象表達式的創建，寫實例域表達式的創建，讀實例域表達式創建，直接賦值表達式的創建，函數調用。又因是對類進行分析，所以本文采用對象敏感、內容敏感、流不敏感的別名分析方法[13]。

門鎖：假設線程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 死鎖分析

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

2.1 死鎖分析的前置條件

2.2 形參型死鎖

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

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

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

圖1 形參型死鎖示例

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

2.3 死鎖檢測

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

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

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

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

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

Algorithm: ProDeadLockDetect

輸入：并發類CUT

輸出：潛在死鎖對PDL

0:PDL←φ

1: for allmi∈CUTdo

2:gi←StaticAnalysis(obi,CUT)

//得到方法mi的鎖序圖，obi是方法mi的調用對象

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中的單結點

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 測試用例生成

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

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

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

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

4 實驗驗證

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

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

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

4.1 實驗設計

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

表1 被測類基本信息

4.2 實驗結果與分析

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

表2 靜態分析結果表

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

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

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

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

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

表3 調度序列和平均時間開銷表

5 結 語

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

[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)。臧麗娜，碩士生，主研領域：軟件測試。

TP311.5

A

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