序列覆盖阵及其应用研究

With the widespread application of softwares and the diversified demands of users, software is expected to not only fulfill its basic functions, but also be more simple, convenient and comfortable. Thus, event-driven softwares have emerged and become more and more popular as the mainstream of software products. Event-driven softwares need to deal with all types of events, which may appear in different orders. Theoretically, since the software may deal with these events in all possible orders, the software failure resulted from the unpredicatable interactions might bring huge troubles to the tester. In order to minimize the test suites to effectively detect the impact of event sequences, event-sequence testing based on sequence covering arrays has been proposed recently. It is an effective combinatorial testing method. With a small number of test cases, sequence covering arrays as test scenarios can efficiently test systems while keeping the fault detection ability. The study on the results and related constructions of sequence covering array, as a newly proposed combinatorial structure is rare. In this project, we will explore the construction and applications of sequence covering array, and mainly focus on its combinatorial constructions and existences.

随着软件的普遍应用和人们需求的变化，软件已不再单单追求它的功能，人们希望软件的使用更加简单、方便、舒适。这样，基于事件驱动型的软件应运而生，而且越来越普遍，逐渐成为软件的主流产品。事件驱动型软件要处理各种类型的事件，并且这些事件有不同的排列顺序。理论上讲，因为软件可能会按照所有可能的顺序处理这些事件集合，所以我们看到不曾预料到的交互操作会导致软件的失败，这将会给软件测试者带来很大的麻烦。为尽可能少地使用测试用例来有效检测事件序列组合对系统产生的影响，人们提出了基于序列覆盖阵的事件序列测试方法，其是一种有效的组合测试方法。以序列覆盖阵作为测试方案，可以设计较少的测试用例来有效保证错误检测能力。序列覆盖阵作为新引入的一种组合结构，研究结果和构造方法甚少。本项目将讨论和研究序列覆盖阵的构造及其相关应用，主要关注组合构造以及存在性结果。

近年来，基于事件驱动型的软件应运而生，而且越来越普遍，逐渐成为软件的主流产品。为尽可能少地使用测试用例来有效检测事件序列组合对系统产生的影响，人们提出了基于序列覆盖阵的事件序列测试方法。本项目以序列覆盖阵为切入点，探讨与其相关的其他组合构形的构造方法和存在性结果，主要研究内容包括强度为3的序列覆盖阵、具有定位和检测错误功能的序列覆盖阵、混合水平检测阵、独立错误的一致水平检测阵、单纯正交表和循环连续正交表。项目取得了如下重要研究结果。.1. 给出了强度为3的序列覆盖阵的存在性结果，找到了强度为3的序列覆盖阵存在的一个上界。结合组合递归方法和计算机搜索，构造了若干最优强度为3的序列覆盖阵。.2. 首次给出了混合水平检测阵的最优性判别准则，深刻揭示了混合水平检测阵的组合和统计特性，并利用启发式优化算法和组合方法编制了最优混合水平检测阵。为了实际使用，给出了若干最优混合水平检测阵的存在性结果。.3. 完全确定了指标大于等于2的单纯正交表SOA（3,5，v）存在性谱。.4. 对于独立错误的一致水平检测阵，建立了其存在的最小下界，并给出了其达到下界的组合特性刻画。利用这种组合刻画，给出了几类达到下界的最优检测阵。.5. 针对一类只在循环相邻因素间存在交互作用的系统，我们提出了解决此类组合测试问题的组合结构--循环连续正交表,并给出了若干构造方法和无穷类. 证明了对于t=2,3,4和任意正整数k和v, 循环连续正交表均存在。. 本项目所取得的研究成果一方面将推动组合设计理论有关离散结构的存在性结果和构造方法的发展；另一方面，将为不同的软件测试需求提供相关的组合测试用例集。