并发程序测试及其关键技术研究

The development and application of concurrent softwares have become increasingly widespread with the use of multi-core technique and the provision of built-in support for cocurrent programming in modern programming languages. Testing is an important approach to ensuring concurrent software qulity. The theories and methods of testing concurrent programs will be investigated for some key problems in this field. This research will focus on the following aspects:(1)Present an improved reachability testing approach to generating test cases that can kill concurrent mutants effectively and enhance the capability of detecting synchroniztion faults.(2)With the technique of program analysis including program slicing,identify the interaction relations between synchronization events and investigates a reduction approach based on variable strength reachability testing to increase the efficiency of testing concurrent programs.(3)Propose a regression reachability approach based on program change impact analysis including program slicing and variable strength combinatorial strategy to increase the productivity.(4) Develop a prototype tool kit and implement the main algorithms for generating test cases,reducing test suites and generating regression test cases for concurrent programs, and then conduct empirical study and verify correctness,effectiveness and performances of these algorithms.

多核技术的普及和高级编程语言对并发设施的支持，使得并发软件的开发和使用日益广泛。并发软件测试是保障并发软件质量的重要手段。针对目前该领域中的若干关键问题，研究并发软件测试的理论和方法，研究内容包括：(1)对现有可达性测试方法进行改进，提出可有效杀死并发变体的并发程序测试用例生成方法，提高探测并发程序中同步类错误的能力；(2) 在上述工作的基础上，融合程序切片等分析技术分析同步事件之间的交互关系，提出基于可变强度并发程序可达性测试的约简方法，提高并发程序测试效率；(3) 提出基于并发程序切片等程序影响性分析和可变强度组合覆盖的并发程序回归可达性测试方法，降低回归测试成本，提高并发软件的生产率；(4) 实现上述并发程序测试用例生成、约简以及回归测试用例生成的工具原型，获取相关实验数据，对上述测试方法的正确性、有效性和性能进行验证。

多核技术的普及和高级编程语言对并发设施的支持，使得并发程序的开发和使用日益广泛。并发程序测试是保障并发程序质量的重要手段。为提高探测并发程序错误的能力和效率，本项目在并发程序测试用例集的生成及约简、并发程序回归测试用例生成等方面进行了研究，取得了如下的主要研究成果：. （1）提出一种基于拆分策略的可达性测试方法，该方法通过拆分相关代码，生成细粒度的同步序列，探测并发程序中因共享变量访问异常引起的同步错误。该方法的主要算法是一个启发式的基于共享变量以及条件同步信息的拆分点选取及排序算法。实验结果表明，该方法可有效提高并发程序同步错误的探测能力，并发变体杀死率由原可达性测试方法的68.4%提高至97.5%，采用第1次拆分点并发变体杀死率为70.8%。 . （2）提出一种可变强度可达性测试方法，该方法通过程序切片等技术分析同步事件之间的交互关系，获取合适的分组信息。在此基础上采用归并算法实现可变强度可达性测试。实验结果表明，该方法在不影响探测能力的前提下，可有效地减少同步序列数，提高测试效率。. （3）提出一种基于约束求解的原子违背和原子集合违背探测方法。该方法将并发交织的可行性转变成一组约束，从而将探测同步错误的同步序列生成问题转为约束求解问题。实验结果表明，与常用的并发错误探测工具Pecan相比，该方法无误报，且有效地降低了漏报率。. （4）提出一种基于修改影响性分析的回归可达性测试方法。实验结果表明，与现有可达性测试方法相比，该方法在保证并发缺陷探测能力不损失的前提下，可有效减少可达性测试过程中产生的同步序列数，提高测试效率。. （5）提出一种基于Hadoop MapReduce的并行可达性测试方法。实验结果表明，该方法可减少可达性测试时间,且具有较强的可扩展性和容错性。. （6）研究一种基于程序可达图的并发程序切片方法，实现并发程序切片原型系统。实验结果表明，该方法提高了并发程序切片的精度。