基于资源扩展活动图的并发测试用例生成方法

朱晓程 薛 静 杨 彬 闫雪丽

北京航天自动控制研究所，北京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 结论

从生成并发测试用例的目的出发，提出了扩展活动图的描述方法，分析基于活动图的并发测试覆盖策略，从而提出基于扩展活动图的并发软件测试用例生成方法。利用该方法生成的测试用例能够检测多线程软件共享资源保护异常、任务同步缺陷等并发软件问题，减少测试用例数量，防止用例数量爆炸，提高软件测试质量与效率。未来，利用该方法结合扩展活动图的形式化描述及模型工具，可以进一步研究测试用例生成的自动化工具，使本方法的应用更准确、更效率。