基于死锁的并发类单元测试用例自动生成

臧 丽 娜

(北京化工大学信息科学与技术学院 北京 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