2014, Vol. 31
2. 广东工业大学 网络信息与现代教育技术中心，广东 广州 510006
2. Center of Internet Information and Modern Education, Guangdong University of Technology, Guangzhou 510006, China
自从多核处理器面世以来，人们越来越多地提到“并发”这个术语，并发就是支持两个或者多个动作同时存在[1].并发程序的发展推动着计算机技术的发展，采用并发机制是提升软件运行速度的重要手段.并发程序在设计上与顺序程序的原则和模式大致相同，不同的是并发程序存在一定程度的不确定性，这样的不确定性[2-3]增加了潜在的交互和失败模式的数量，从而导致测试并发正确性十分困难.
当前所面临的主要挑战在于:并发潜在错误的发生并不具有确定性，而是随机的；能够发现这些潜在的错误，一定要具备更广泛的覆盖度和更长的运行时间.测试并发应用程序需要测试其正确性.目前主要通过静态分析[4-5]、动态分析[6]和模型检查[7-8]3种方法来测试并发应用程序的正确性.静态分析直接分析程序源代码，容易生成许多误报，并且需要付出很大精力才能将误报降至最低.动态分析是在程序执行过程中测试程序的运行状态，其缺点是只有在执行路径中检测错误，并且需要依赖测试用例来覆盖更广的代码.模型检查即用于验证有限状态并发系统正确性的方法，但是在大多数情况下，很难自动从代码中提取出模型.另一方面，由并发程序不确定性行为的影响并发程序测试也可以分为确定性测试[9]和不确定性测试[10].确定性测试方法是测试输入时包括控制并发执行的事件序列并按照确定的序列执行.而不确定性测试方法是测试输入时不包括控制并发执行的事件序列.针对不确定性测试方法，濮方琍[11]提出一种改进的不确定性测试方法，改进后的方法运用并行控制流程图确定全同步对集合及延迟点，提高了测试的效率，但是并没有发现潜在的并发错误.
本文是在不确定性测试方法的基础上，提出了一个并发正确性测试方法，在测试过程中动态收集局部并发测试信息，通过激化并发程序资源竞争增大线程间交错的几率，增大并发程序的不确定性最大限度地发现程序中存在的并发错误问题，该测试方法可以发现更多的并发程序潜在错误.
1 并发程序分析 1.1 并发程序错误分析在并发程序中需要考虑同时有多个执行流程的情况，以及如何对这些执行流程进行协调以完成指定的计算任务.此外，还有错误性能问题，这些问题正是由于在线程并发执行过程中的不确定性和异步性而直接导致的.也正是因为这两种属性，多线程程序中包含的错误具有不确定性.例如，如果多个线程交替执行，那么可能会使得错误不会暴露出来，但如果在对执行环境进行调整时改变了线程的执行顺序，就会开始出现错误.即使没有对硬件做任何改变并且以同样的环境来执行同一并发程序，并发的错误形式也是不同的.如果要发现并发错误，就需要考虑所有不同的执行方式.并发程序中容易出现数据竞争是因为多个线程同时读取同一个内存位置并都想进行更新写入内存，同时并发程序所处的运行环境影响并发程序的调度算法的执行[12-13].并发程序中并发错误的产生是由于并发程序没有按照特定的内存更新顺序来运行.
对并发程序的代码进行修改时，很可能会引入新的错误.虽然代码在正常运行时发现了一个错误，但在调试器下运行代码时，仍可能出现无法定位的问题，这是因为调试器的单步执行特性可能会掩盖正在分析的错误.即使在消除了所有由于修改代码而引入的错误后，代码仍有可能无法获得与串行版本一样的结果.如果结果只存在细微的偏差，或许是由于舍入造成的误差，因为在多线程的情况下，将各个线程计算结果合并起来的顺序与在串行代码中合并结果的顺序并不相同.如果结果偏差很大，那么极有可能是因为在使用线程时引入了某个逻辑错误.
1.2 并发程序不确定性测试方法不确定性测试方法是将并发程序在多次执行过程中运行同步序列从而证明并发执行的正确性.不确定测试方法首先要确定影响并发执行的因子从而建立测试用例; 其次也需要综合考虑内存访问模式和CPU使用率.针对多线程同时读取和写入同一个内存位置的并发程序来说，内存使用率不同会导致并发程序的运行结果不一致[14-15].在共享内存的模式下，多个线程中执行的工作将会使得处理资源一直处于忙碌的状态，并且增加了同步操作的数量.测试并发程序时其所处的内存容量也是需要考虑的输入数据之一.采用不确定性测试方法进行测试时只能依赖于并发程序随机经历的同步序列，因为在测试开始时已经建立的相同测试数据和运行环境是不能进行变更的.
不确定性测试方法的测试步骤:首先选取适合的运行环境和输入测试用例；其次，在输入测试用例的前提下运行并发程序，运行过程中记录和观察并发程序的运行结果和所遍历的同步序列；然后判断执行结果和同步序列是否正确，如果执行结果不是预期的效果或者同步序列不正确，都可以判定并发程序有错误；最后反复运行并发程序在相同的测试用例和测试环境下，直到没有发现错误此时结束测试.此不确定性测试方法的流程图如图 1所示.
|
图 1 不确定性测试流程图 Figure 1 Flow chart of non-deterministic test |
不确定性测试的前提是准备好测试用例和对于何时结束测试的条件判定.从以上分析可知，不确定性测试方法的优点是简单易操作，缺点是无法来判定测试数据的覆盖率，因为需要反复多次的遍历同一同步序列，而且缺乏在测试结果的基础上进一步的分析错误和指导下一阶段选择的测试数据.为此本文在不确定性测试方法的基础上，利用动态规划算法的思想，动态收集并发错误信息进行分析后加剧临界资源竞争生成新的测试数据，从而发现并发程序产生的错误.
2 改进后的并发正确性测试方法 2.1 并发正确性测试不确定性的测试方法会漏掉一些并发错误，通常是由于并发程序在运行时时序的不确定性而无法检测出并发程序中存在的错误.但实际上并发程序在测试运行时的时序是确定的，当共享资源被多个线程访问操作时，线程对于共享资源没有进行任何的同步操作，也不包含能保证线程以正确顺序发生的指令.但是运行时所有线程都以正确的顺序运行.因此，是测试数据没有捕捉由于时序的不确定性而导致的并发错误.虽然虚拟机的线程调度程序可以在线程运行的任何时刻切换线程，并以不同的顺序运行线程.但是实际上线程调度程序往往很少进行线程切换，因为测试过程中并发任务很少，线程的一次运行基本已经在调度程序线程之前完成.不确定性测试方法只是对多线程交错情况的某些交错情况进行了测试，长期使用后才会发现更多的并发错误.为了能够在早期发现这些错误需要在测试的过程中通过加剧进程对资源的竞争程度.
在不确定性测试的基础上，采用动态规划算法的基本思想，将测试一个并发程序正确性的问题分解为若干个并发程序代码段，按顺序测试每个并发程序代码段，首个并发程序代码的测试结果，为其他的并发程序代码段提供有用的测试信息.为了保证整个并发程序正确，需要每个并发程序代码段都正确.根据每个并发程序代码段所特有的并发特性生成不同的测试用例.
为此在并发程序正确性测试方法使用之前，需要对并发程序局部化划分.将并发程序分类归纳为多个并发程序段.如图 2所示，首先将并发程序P抽象为m个临界区域，临界区域就是并发程序段.需要测试每个并发程序段的正确性才能最后判定程序P是否并发正确.当一线程进入临界区域时，它能进行下一步操作的必要条件是要拥有资源的使用权，不然必须等待其他线程释放资源的使用权.并发错误的产生一个主要的原因就是没有处理好对临界区域的访问互斥问题.另外对临界区域的资源共享也会引发各种并发错误.没有对临界资源的竞争将不能称之为是并发程序，而只是顺序程序.
|
图 2 并发程序分区图 Figure 2 Chart of concurrency program partition |
本文改进后的并发正确性测试方法是在不确定测试方法的基础上，首先对并发程序中并发交互代码段进行分类，对每类并发测试段设计其测试规则.其次在测试的过程中逐渐增加程序的并发任务，激化资源竞争程度.最后反复多次地运行程序进行测试以发现潜在的并发错误.改进后的测试流程图如图 3所示.
|
图 3 并发正确性测试流程图 Figure 3 Flow chart of the concurrency correctness testing |
该方法具体的测试流程步骤如下：
(1) 将并发程序进行分解，分解为m个不同的并发代码段，然后针对并发代码段设计测试用例进行测试，将测试结果记录下来.
(2) 对测试数据进行初始化，调整程序的并发任务激化程序对临界资源的竞争.再次建立相同的测试环境，使用同一测试用例进行测试.记录下程序运行错误时的信息，同时将信息返回给被测试的程序.如果在测试过程中出现错误就说明并发代码段存在错误.不然将重新调整测试数据增加并发任务重复进行测试.
(3) 重复进行测试，结束对并发代码段的测试的必要是并发错误出现或者是超过了最大的测试次数.
(4) 对其余并发代码段进行同样的测试.
为了最大程度地发现潜在的并发错误就需要通过增加并发任务来加剧临界资源的紧张度.并发测试程序正确性测试方法是在测试的过程中加入适当的并发任务.例如在测试过程中等待一定时间间隔之后，开始增加并发任务.为了获得临界资源使用权，并发程序就会一直处于无限的等待和释放中，从而增加对临界资源竞争激烈度.如果超过了最大测试次数，并发程序没有任何错误产生时会增加并发任务，增加临界资源的竞争度，直到错误重现或者预先配置的最大测试数完成.第i次测试过程中，对临界资源增加并发任务CE：CE i+1 (1≤i≤J)，J为测试的最大次数.第一轮测试一次性注入全部资源，以后每次测试一定时间间隔内增加并发任务.随测试次数的叠加，增加的并发任务越来越多，使得进程间的资源竞争逐渐紧张是由于更多的进程都处于准备状态来抢夺资源使用权.如果并发错误出现，或者已经到达最大测试次数J，就结束对该并发测试段的检测，否则继续进行测试.
并发任务和最大测试次数是预先配置的.假设在完成J次测试之后并发错误还没有重现，就认为错误已经被纠正了.最大测试次数是随着对并发程序正确率要求的程度来确定的，J设置越大就是表明对并发程序的质量要求越严格，显然重复测试的次数越多，测试需要的时间也就越长.这时需要根据被测并发程序的特点，设置最佳测试次数可以提高测试的效率和准确性.
3 实验结果采用改进后的并发正确性测试方法针对广东省教育部门协议采购电子管理系统中的采购订单这一模块进行测试.采购订单的业务逻辑为已提交的采购订单不允许修改.当打开一个会话窗口测试，逻辑是没有问题的.
测试情景为：打开两个采购订单界面，提交其中一个采购订单，提交成功以后，状态变成已提交，当前界面不允许修改，测试通过.这时再导航到后面已经打开的FORM，状态是审批退回，可以修改成功.这样的后果是已经提交的采购订单还可以任意修改，产生并发错误.
实验环境为：CPU：Intel奔腾SU2700；内存：2GB；操作系统：Microsoft Windows 2000 Service Pack3.
3.1 实验步骤实验环境中使用本文提出改进后的方法进行测试，在测试之前编写测试用例进行测试，并记录发生并发错误时的现场测试环境.
(1) 根据产生并发错误的现场，设置测试的最大次数为100和初始的并发任务为2，重现建立测试环境，运行测试用例.
(2) 逐渐增加并发任务，观察并发错误的次数并记录下来.
(3) 同样的实验环境下使用不确定性测试方法进行测试.
(4) 同样的实验环境下使用濮方琍改进后的不确定性方法进行测试.
(5) 观察发生并发错误的次数并记录下来.
(6) 对实验结果进行比较与分析.
3.2 实验结果与分析通过在相同的测试环境下利用不确定性测试方法、并发正确性测试方法和文献[11]方法进行测试，分别记录并发错误发生的次数，实验结果如表 1和图 4所示.
|
表 1 实验结果对照表 Table 1 Table of the experimenal results |
|
图 4 内存使用率比较图 Figure 4 Comparison chart of memory utilization |
从表 1中数据可以看出，当运行并发程序多次时，本文改进后的方法比文献[11]的方法可以发现更多的并发错误，由于在测试过程中随着测试次数的增多，增加的并发任务也越来越多，从而进程间的资源竞争逐渐增多，增加了并发错误发生的几率，因而可以发现更多的并发错误.从图 4中可以看出，当使用改进后的方法进行测试时，CPU的使用率相对较低，这是因为改进后的测试方法是在测试结果的基础上进一步地分析错误，同时指导下一阶段的测试数据，减少了无用的测试数据，从而内存的占有率降低；濮方琍的方法缺乏对测试数据的选择造成内存的占有率高.
4 结论目前不确定性测试方法中存在的不足之处是缺少在测试结果的基础上进一步分析错误和指导下一阶段选择的测试数据.本文改进后的测试方法是在使用了动态规划思想的基础上，在测试结果的基础上进一步分析错误和指导下一阶段选择的测试数据，同时通过增加并发任务来激发并发程序的资源竞争，从而将并发错误在早期暴露出来，发现更多并发错误.实验结果表明该方法比文献[11]方法更有优势，可以更多地发现并发程序的错误同时提高了测试执行效率.该方法在测试用例的选择上还需进一步的研究和实验，有待进一步的改进.
| [1] |
Clay Breshears. The Art of Concurrency[M]. New York: O'Reilly Media, 2009.
|
| [2] |
钟远明, 奚建清. Snapshot加锁机制的研究[J].
广东工业大学学报, 2001, 18(2): 16-17.
Zhong Y M, Xi J Q. Research on snapshot locking scheme[J]. Journal of Guangdong University of Technology, 2001, 18(2): 16-17. |
| [3] |
吴熳娜. 一个自适应的并发程序测试方法[D]. 杭州: 浙江大学计算机科学与技术学院, 2010.
http://cdmd.cnki.com.cn/Article/CDMD-10335-2010049267.htm
|
| [4] |
张健. 精确的程序静态分析[J].
计算机学报, 2008, 31(9): 49-53.
Zhang J. Sharp static analysis of programs[J]. Chinese Journal of Computers, 2008, 31(9): 49-53. |
| [5] |
张斌. 并发程序分析与测试辅助技术研究[D]. 南京: 东南大学计算机科学与工程学院, 2003.
|
| [6] |
顾庆, 韩杰. 一个面向分布式程序的测试系统框架[J].
软件学报, 2000, 11(8): 53-59.
Gu Q, Han J. Test system framework for distributed software system[J]. Journal of Software, 2000, 11(8): 53-59. |
| [7] |
林梦香, 吴国仕. 程序模型检查器综述[J].
计算机科学, 2009, 36(4): 12-15.
Lin M X, Wu G S. Survey on model checker for programs[J]. Computer Science, 2009, 36(4): 12-15. |
| [8] |
Biberstein M, Farchi E, Ur S. Choosing Among Alternative Pasts[C]//Proceedings of the 17th International Parallel and Distributed Processing Symposium. [s. l] IEEE Computer Society Press, 2003. 289(4): 22-26.
|
| [9] |
王海宾. Java并发程序的测试方法系统设计与实现[D]. 大连: 大连理工大学计算机科学与技术学院, 2008.
|
| [10] |
卢超. 并发软件测试理论与技术研究[D]. 武汉: 华中科技大学计算机科学与技术学院, 2007.
http://cdmd.cnki.com.cn/Article/CDMD-10487-2009033584.htm
|
| [11] |
濮方琍. 并行程序测试的关键技术研究[D]. 武汉: 华中科技大学计算机科学与技术学院, 2009.
http://cdmd.cnki.com.cn/Article/CDMD-10487-2010042263.htm
|
| [12] |
刘攀, 曾红卫, 等. 基于FSM的测试理论方法及评估[J].
计算机科学, 2011, 34(6): 16-18.
Liu P, Zeng H W. FSM-Based testing theory method and evaluation[J]. Computer Science, 2011, 34(6): 16-18. |
| [13] |
潘敏学, 李倩. 死锁检测工具的能力分析与综合应用[J].
计算机科学与探索, 2010, 4(2): 153-164.
Pan M X, Li Q. Capability analysis and integrated application of deadlock detection tools[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(2): 153-164. |
| [14] |
霍敏霞, 丁晓明. 基于Petri网的并发程序测试用例产生方法[J].
计算机科学, 2011, 38(9): 135-138.
Huo M X, Ding X M. Test case generation method for concurrent programs based on Petri net[J]. Computer Science, 2011, 38(9): 135-138. |
| [15] |
单方, 陈璞. 一个软件测试过程管理工具[J].
广东工业大学学报, 1999, 16(2): 89-91.
Shan F, Chen P. A software test process management Tool[J]. Journal of Guangdong University of Technology, 1999, 16(2): 89-91. |