基于事件消息驱动的Petri网的类族测试用例生成技术的研究

在类族交互测试的正交阵列测试系统(OATS)生成测试用例的方法中,存在类的状态盲目组合而导致测试用例“爆炸”以及标准正交阵列不易扩充的问题。提出了基于EMDPN的类的状态组合的标记关联递推算法,通过类族之间的层次级别与状态级别的优选组合产生交互路径,在证明生成交互路径数定理的基础上,得到了基于EMDPN模型的扩展的正交阵列测试系统(EOATS)的类族交互测试用例的生成方法,优化OATS。在讨论类族交互测试的覆盖率问题时,给出了类族交互测试的同步消息序列测试标准(SMSC),阐明了新的EOATS方法具有良好的覆盖性。     

基于EDPN的类测试框架及测试用例生成技术的研究

针对基于状态的面向对象软件的类测试过程中存在的不可预测、不可达状态、状态组合“爆炸”和测试用例“爆炸”等问题,提出了基于EDPN模型的类测试、类的交互测试和类的层次测试框架,设计了相应的测试模型;提出了基于EDPN的有标记的唯一输入输出(UIO)测试用例的自动生成方法,生成状态转移路径序列,测试类的状态;提出了基于扩展的EDPN的状态组合的标记关联递推法,生成扩展的正交阵列表,测试类的交互;提出了基于扩展的EMDPN的协同路径(copaths)测试用例的生成方法,生成协同路径序列,测试类的层次。     

基于调用图的类间MM路径自动生成方法研究

在面向对象的软件测试中,类间集成测试尤其困难.方法/消息路径(MM路径)是由消息连接的方法执行序列,可以很好地体现面向对象软件由对象发送消息调用方法执行的交互过程,因此非常适于面向对象软件的集成测试.结合现有调用图构建算法,提出了一种基于调用图的面向对象软件类间MM路径自动生成方法,并通过大量实验,研究了采用类层次分析和安德森指向分析这2种典型调用图构建算法对生成MM路径的数量和时间花费的影响,进而分析了面向MM路径生成的测试用例集对被测程序的结构测试覆盖效果.实验结果表明:基于调用图的类间MM路径自动生成方法是确实可行的;采用安德森指向分析较类层次分析生成类间MM路径的数量平均增加13.11％,时间消耗却平均减少27.78％;此外,针对安德森指向分析生成的类间MM路径进行面向路径的测试用例自动生成,其生成的测试用例集对被测程序获得的结构覆盖率比采用类层次分析平均提高2％～7％.因此,对于基于调用图的面向对象软件类间集成测试路径生成,基于安德森指向分析较类层次分析生成类间MM路径的效率更高.     

基于同步有向图的同步测试序列生成方法

使用多测试单元的测试系统可以对多端口协议实现进行一致性测试，但是在进行这种一致性测试时，测试系统各个端口之间可能会出现同步问题，现在，解决同步问题常用的办法是在测试单元相应端口之间增加同步连接，然后通过此同步连接相互发送同步消息来进行同步，多端口协议和其它类型的分布式系统可以用有限状态机模型来描述，目前，同步问题被分为双端口同步问题，多端口同步问题，紧同步问题等多种类型，该文考虑两种有限状态机测试问题，第一种是面向端口的测试，不考虑有限状态机测试单元之间的通信问题，第二种面向组的测试，有限状态机中的各个端口被分成互不相关的多个组，属于不同组中的测试单元之间互不通信，该文提出了一种基于同步有向图的同步测试序列生成方法，这种生成方法适用于Pair同步，Port同步和组同步问题，并且，这种方法也可以用来判断如何在非同步测试序列中增加同步通信，将非同步测试序列转化为同步测试序列。     

基于UML交互概览图的测试线索的生成方法

针对单一UML模型测试不充分的问题,结合UML2.0交互概览图的特点开展测试方法研究,提出一种测试线索自动生成的方法。首先,给出UML类图、顺序图、交互概览图(OID)的形式化定义;通过提取交互概览图的流程信息和对象交互信息分别构造节点控制流图(NCFG)和消息序列图(MSD);将从MSD提取的消息路径嵌入到NCFG中,构造可测试交互概览图模型;最后采用两两覆盖准则生成测试线索。实验验证了该方法自动生成的测试线索在保证测试充分性的前提下可避免组合爆炸。     

基于UML交互概览图的测试线索的生成方法

针对单一UML模型测试不充分的问题,结合UML2.0交互概览图的特点开展测试方法研究,提出一种测试线索自动生成的方法。首先,给出UML类图、顺序图、交互概览图(OID)的形式化定义;通过提取交互概览图的流程信息和对象交互信息分别构造节点控制流图(NCFG)和消息序列图(MSD);将从MSD提取的消息路径嵌入到NCFG中,构造可测试交互概览图模型;最后采用两两覆盖准则生成测试线索。实验验证了该方法自动生成的测试线索在保证测试充分性的前提下可避免组合爆炸。     

一种类间交互测试的约束型标记驱动Petri网模型

面向对象软件测试的主要问题是考虑类间交互的集成测试,交互测试能检查出对象间的消息传递产生的不可达路径.设计了一种约束型标记驱动Petri网(C-LDPN)模型描述对象间的消息交互,给出了UML协作图转换为C-LDPN的规则.在定义对象活跃点以及对象活跃格局概念的基础上,根据对象所关联的变迁得出对象状态集上的等价类,提出一种消除C-LDPN中分支冲突的类间交互测试用例生成算法,求出对象的每个等价类中所有的活跃点数,得出对象的总状态数,用对象的分割连接子分割对象的状态域得到可达性C-LDPN,用合并连接子合并子对象得到标准型C-LDPN,最终生成类间交互测试用例--标记-变迁路径(LTPaths).     

从Rose的规约文件自动生成测试用例

对基于状态的类测试用例自动生成进行了研究，重点放在状态预测和测试消息序列生成上：类的动态行为用uML的状态图表示，测试时直接从Rational Rose的规约文件中读取状态图规约生成测试消息序列；对状态的预测使用状态不变量；生成消息序列时对算法进行优化，减少消息序列的冗余，从而缩短消息序列的路径长度。     

状态图中可同步测试序列生成策略

对于由通信有限状态机构成的状态图的可同步测试序列的生成策略，一种现有的方法是由状态图生成相应的积自动机，然后采用有限状态机的测试序列生成策略。这种方法存在组合空间爆炸问题和测试序列的同步问题。在定义了测试序列的两类同步问题的基础上，提出了基于多测试驱动的测试模型MTM和基于该模型的测试序列生成策略，该策略在不生成积自动机的情况下，通过同步锁和相应的策略解决两种类型的同步问题，避免了组合空间爆炸问题。     

基于界面状态因果图的测试用例生成

在可视化软件测试系统中,测试用例来源于引起对象状态转移的前置条件和触发事件,模拟界面控件状态由消息驱动产生转移变迁的执行特点形成界面状态因果图,提出了基于终态的测试树及其生成算法,讨论了利用这种测试树及相应覆盖准则生成测试用例的方法,最后给出了一个应用实例。     

基于 ROS 改进算法的无线传感器网络耗能研究

成对广播同步（PBS）是无线传感器网络同步研究的重要协议。无线传感器节点具有体积受限、通信能力有限、存储空间较低、能量有限等特点,对传统的时钟同步协议改进是非常有必要的。因此,研究无线传感器网络的时钟同步算法将具有重要的意义。文章建立在仅接收端（ROS）同步基础上实现范围广阔的网络同步,并且能够在无线传感器网络节点的能耗方向有着不可忽视的作用。通过对单簇网络同步的研究,提出多簇网络同步并对多簇网络同步在无线传感器网络同步中全网成对选择算法（NPA）和基于组的成对选择算法（GPA）做出研究,并且做出了仿真对比。结果显示：在传感器节点数目较少的情况下,NPA 算法与 GPA算法处理消息包数目的性能几乎相同;在网络中传感器节点数目比较多的情况下,GPA 算法明显优于 NPA 算法,信息处理过程中大大减少了消息包数目。最后,对广播同步技术在应用中所出现的问题,提出了基于此算法的新的研究方向。     

时钟同步的假设检验研究

时钟同步技术是分布式系统中非常活跃的研究领域之一，由于大多数分布式系统实际上是不同步的，因此需要采用容错时钟同步算法确保消息通信的有界延迟，而基于假设检验的时钟同步技术可以避免因错失对两个高概率不同步时钟进行同步调整而造成系统不正常使用的情况。该文讨论了时钟同步的假设检验问题。除了假设检验、两类错误概率，还给出了概率最小时钟偏差、时钟同步概率等概念。在时钟偏差的统计分布特性近似于服务正态分布的假设条件之下，提出了基于非中心t分布的时钟同步假设检验方案。最后，基于服务器和客户端之间双向消息通信传输模式，给出时钟偏差的估计和检验样本。     

无线传感器网络时间同步算法研究

时间同步技术是无线传感器网络中非常重要的协议之一,是保证传感器网络中各个节点协同工作的核心机制。根据有无参考节点将时间同步算法分为双向消息交换时间同步算法和分布式一致时间同步算法,其中双向消息同步机制广播消息交换算法和基于ACK帧的时间同步算法。这三类双向消息时间同步算法的时间同步消息发送数目逐级递减,能耗相对应降低;而分布式一致时间同步算法摒弃了参考节点的选择,同时同步所有的传感器节点,避免了参考节点失效而无法进行时钟同步的情况。基于现有研究的分析及归纳,最后给出了时间同步算法未来可能的研究方向。     

一种节能的基于TPSN算法改进的时间同步算法

时间同步是无线传感器网络中的一项重要支撑技术,而节点能量有限则是无线传感器网络的一个显著特征.节点进行时间同步的时候,如果同步过程消息传输过多,则会大大消耗节点的能量.对经典TPSN时间同步算法进行改进,提出一种低能耗的时间同步算法.     

无线传感器网络低功耗多跳广播时钟同步算法

为满足无线传感器网络低功耗的要求,提出一种双广播域同步的低功耗多跳广播时钟同步算法。该算法基于接收端-接收端同步机制,通过一对已同步节点间对等广播消息,只需多发送一次消息,即可将该对节点的同步范围扩大为两广播域的并集,并采用双根节点的层级结构将算法扩展到全网络范围。OMNeT++仿真结果表明,与MBS算法相比,该算法能有效降低全网络同步需要传输的报文个数。     

Testing the Schedulability of Synchronous Traffic for the Timed Token Medium Access Control Protocol

One of the key issues related to guaranteeing synchronous message deadlines in a timed token network (such as fiber distributed data interface) where the timed token medium access control protocol is used is the schedulability test of synchronous traffic (i.e., testing whether or not all synchronous messages can be transmitted before their deadlines, under a given setting of network parameters). Much work has been done on how to assign network parameters appropriately in order to guarantee timely transmission of synchronous traffic. As a result quite a few synchronous bandwidth allocation schemes and some good guidelines on selection of the target token rotation time have been proposed. In contrast, limited research has been conducted on how to effectively test whether or not given network parameters can guarantee timely transmission of all synchronous messages (of a considered synchronous message set) before their deadlines. The previous testing methods for synchronous message schedulability only provide a sufficient (but not necessary) test and therefore fail to always keep effective for any synchronous message set considered. In this paper, we propose two testing methods for determining the schedulability of a synchronous message set with message deadlines no longer than periods. The proposed tests perform better than any previous test in the sense that they are both sufficient and necessary. Some numerical examples are given to compare different testing methods, all of which have demonstrated the superiority of the proposed tests to other existing testing methods.     

PTP网络非对称时延抖动修正算法设计与分析

为了改进PTPV2时间同步网络非对称时延抖动对主从时钟同步精度的影响,设计了传输报文的非对称时延抖动修正算法。基本思路是在主从时钟交换报文信息中,找出最佳报文用于从时钟的调整。采用两级过滤先进增强时间恢复算法,即使发生网络传输阻塞,也能筛选出未受阻塞的幸运报文用于时钟偏差估计。新算法能够很容易集成到PTPV2协议中,而不会影响基本的报文信息交换。实际测试结果表明,新设计的时间恢复算法,在普通交换机网络中,可有效抑制非对称时延抖动,主从时钟同步精度也可优于100ns。     

A combinatorial testing strategy for concurrent programs

One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, called t‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy called t‐way testing. We present an algorithm that implements t‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate that t‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.