Real-time embedded software testing method based on extended finite state machine

The reliability of real-time embedded software directly determines the reliability of the whole real-time embedded sys- tem, and the effective software testing is an important way to ensure software quality and reliability. Based on the analysis of the characteristics of real-time embedded software, the formal method is introduced into the real-time embedded software testing field and the real-time extended finite state machine （RT-EFSM） model is studied firstly. Then, the time zone division method of real-time embedded system is presented and the definition and description methods of time-constrained transition equivalence class （timeCTEC） are presented. Furthermore, the approaches of the testing sequence and test case generation are put forward. Finally, the proposed method is applied to a typical avionics real- time embedded software testing practice and the examples of the timeCTEC, testing sequences and test cases are given. With the analysis of the testing result, the application verification shows that the proposed method can effectively describe the real-time embedded software state transition characteristics and real-time requirements and play the advantages of the formal methods in accuracy, effectiveness and the automation supporting. Combined with the testing platform, the real-time, closed loop and automated simulation testing for real-time embedded software can be realized effectively.

基于EFSM的智能车间制造系统生产物流建模与仿真

制造业的生产物流方式处于不断变革中,对其建模仿真可为制造系统规划设计、分析及改造提供决策支持。依“人-机-物-环-法”分类给出了智能车间制造系统中实体元素的描述,结合EFSM(extended finite state machine)和组件化建模思想,建立了生产和物流组件化EFSM模型;阐述了智能车间多作业生产的建模过程以及组件模型实例化方法;通过EFSM-DEVS(discrete event system specification)模型自动转换及DEVS引擎完成了仿真运行。仿真结果表明:该方法所建立的模型更符合车间实际状况,适用性更广;组件化建模思想能构造更具扩展性的软件;建模及仿真运行的3D可视化使软件直观性更好,其仿真结果与AnyLogic保持一致。

基于EFSM模型的铁路信号安全软件单元测试技术研究

铁路信号安全软件内部逻辑复杂,通过充分的单元测试能够更好地发现和排除软件内部的缺陷。文章分析单元测试常用方法,并结合铁路信号安全软件单元测试技术要求,提出一种基于扩展有限状态机(EFSM,Enhanced Finite State Machine)模型的黑白盒融合单元测试方法。使用自动化测试工具Cantata,以无线超时降级场景为实例,验证该方法是否可以满足测试场景的完备性,并且关注软件结构是否被完全覆盖。根据覆盖结果,对未覆盖原因进行分析,判断是否存在异常场景,并针对未覆盖分支补充测试场景,丰富了测试案例,从而保障了铁路信号系统的可靠性。

自适应EFSM可执行测试序列生成

基于扩展有限状态机(EFSM)模型自动生成测试序列可以提高测试效率.由于EFSM模型包含丰富的变量和谓词条件,它们之间的冲突可能导致自动生成的测试序列不可执行.对EFSM变迁及变迁之间的关联关系进行了详细的讨论和分析,定义了一个邻接变迁关联图,提出了一种自适应EFSM可执行测试序列生成算法.新算法首先根据变量和谓词包含情况对变迁进行分类,然后深入挖掘了邻接变迁之间的关联关系,最后,基于自适应预测搜索函数启发式引导可达性分析树扩展生成可执行的测试序列.实验数据表明,与宽度优先可达性分析方法相比,新算法可以有效降低可达性分析过程中产生状态空间爆炸问题的概率,从而提高测试序列自动生成的效率.在最坏的情况下,新算法的计算时空复杂度也等同于宽度优先算法.

基于EFSM的自检测试

在 EFSM (Extended Finite State Machine)的测试中 ,通常需要一些特征序列来判断当前的状态 ,以确定是否存在转换错误 .由于 EFSM中转换可执行条件的存在 ,使这些序列的生成比较困难 .本文引入了自检测试思想 ,通过比较待测实现与从 EFSM得到的直接实现的执行结果 ,来确定是否到达了正确的状态 。

利用逆向判定性缩短EFSM的测试序列的长度

在一个以扩展的有限状态机 (EFSM)为模型描述的协议测试系统中 ,测试序列的可执行性是一个重要的问题。同时 ,还要考虑到测试序列的优化问题。文中以EFSM为协议的描述模型 ,引入了逆向判定性的概念 ,并利用这一概念对转换可执行性分析 (TEA)方法进行了改进 ,缩短了生成的测试序列的长度 ,并且减小了所需的TEA树扩展空间。

基于监控理论的EFSM设计方法

随着扩展有限状态机(EFSM)模型在计算机科学和工程领域的广泛应用,EFSM的设计逐渐成为一个重要的问题。目前EFSM的设计仍然主要依赖于个人经验,缺乏理论基础。由于EFSM中每个转移的谓词可以看作此转移的一个监控器,所以可以用离散事件系统的监控理论为EFSM设计提供理论基础。首先定义了有限状态机(FSM)导出的EFSM及其产生的语言。然后,基于监控理论中的受控对象和监控器,提出了一种设计EFSM的方法,用离散事件系统监控理论为EFSM设计提供理论依据。最后用两个实际例子说明了提出方法的可用性和有用性。

基于无关变量分离的EFSM测试数据进化生成

扩展有限状态机(EFSM)相比于有限状态机(FSM)能够更加精确地刻画系统的动态行为,因而广泛作为各种控制流与数据流系统的测试模型。在EFSM模型的测试中,使用搜索的方法获得触发目标测试路径的测试数据是近年来的一个研究热点。为进一步提高搜索效率,在遗传算法(GA)的基础上提出一种自动分离测试路径中无关输入变量的方法,该方法通过分析模型中变量与迁移间的关系,判定不影响子路径中谓词条件的无关输入变量,进而从个体中将其分离以实现搜索空间的自动缩减,提升测试数据生成效率。对几种具有不同复杂度的基准EFSM模型进行实验后的结果表明,该方法生成有效测试数据的成功率均达到98. 2%以上,且与未分离输入变量的遗传算法相比,所需平均迭代次数减少44. 7%～85. 9%,平均运行时间减少24. 1%～85. 5%。

基于覆盖准则的多轮测试用例优先排序方法

针对测试用例优先排序中存在的覆盖准则选择困难、确定最优准则序列难等问题,提出了一种基于扩展有限状态机模型的最优覆盖准则序列排序方法(CWTCP)。该方法首先运用鲸鱼优化算法挑选出最优覆盖准则序列,为后续的排序提供了有力支持;其次将覆盖准则序列依次应用在多轮排序中,以应对可能出现的平局问题。为了验证CWTCP方法的有效性,在5个扩展有限状态机模型上进行了实验,采用平均故障检测百分比(APFD)作为度量标准。实验结果表明,CWTCP的平均APFD值为0.918,比随机算法的相应值高了19.8%。

EFSM模型的字符串类型测试数据自动生成

基于软件描述模型的测试数据自动生成研究中,字符串类型测试数据生成是一个研究热点和难点。EFSM模型是一种重要的软件描述模型。分析了EFSM模型的特点,针对面向EFSM模型目标路径的字符串测试数据生成,建立了字符串输入变量模型和操作模型,结合静态测试的特点,给出了通过字符串变量模型在目标路径上的符号执行结果生成字符串类型测试数据的方法。实验结果表明,该方法能够达到预期效果,提高测试生成效率。

含过程调用EFSM模型测试数据生成

针对含过程调用EFSM模型测试数据生成中过程调用的不可执行问题,提出了一种能对过程调用进行处理以实现模型的测试数据自动生成方法。该方法将被调子过程描述为一个EFSM模型,将表示主过程及子过程的EFSM模型合并为一个新的模型,合并后的模型符合EFSM模型规范,采用遗传算法对该模型进行测试数据自动生成。实验结果表明,该方法能够较好地解决含过程调用EFSM模型的测试数据自动生成问题。

EFSM模型字符串测试数据自动生成研究

字符串测试数据自动生成是目前的研究难点,还没有很好地解决方法。针对这个问题,提出了一种将符号执行约束求解与搜索算法相结合实现基于EFSM模型的字符串测试数据自动生成方法。将测试数据候选字符集中的字符通过取余编码转换为整数;将目标路径上字符串约束转换成整数约束,通过约束求解获得中间解;采用搜索算法生成字符串测试数据。该方法能很好地减小字符串的搜索范围,有效地减少搜索算法的执行时间。实验结果表明,该方法达到了预期的效果,提高了测试数据生成效率。

基于遗传算法的面向多样性EFSM测试序列生成方法

为提高扩展有限状态机(EFSM)测试用例生成的效率及效果,提出了一种基于遗传算法的面向多样性EFSM测试用例集生成方法.在优化遗传算法个体编码和操作算子的基础上,引入EFSM测试序列集多样性度量,利用遗传算法,不断增加测试序列集中测试序列间的差异程度.同时在方法中增加测试序列可行性判别机制,以保证最终测试序列均为能产生测试数据的可执行序列.实验结果表明,与未考虑多样性的EFSM测试序列生成方法相比,面向多样性的方法不仅能够生成可执行并满足测试覆盖准则的测试序列集,而且有效减少了测试序列集生成的时间开销,同时缩小了所需最小测试用例集的规模.

基于分支界限搜索的EFSM协议测试序列生成算法

针对EFSM中状态迁移不确定导致的协议一致性测试序列生成困难的问题,提出了一种协议一致性测试序列生成算法。该算法基于互异代表系理论为每个协议状态变迁赋权值,再基于分支界限法搜索生成的协议测试序列,将协议一致性测试序列的生成转换为寻找最小权值状态变迁路径的问题。该算法克服了无赋权要求的宽度优先搜索的缺陷,降低了测试序列的搜索与生成时间复杂度,提高了测试序列生成的效率。

基于UML状态图的类测试用例自动生成方法

UML作为面向对象软件开发的事实上的标准建模语言，近年来得到了广泛的应用 ，基于UML的测试也成为面向对象软件测试的研究热点。该文把基于扩展的有限状态机EFSM 的唯一输入输出UIO测试用例自动生成方法和UML的类的状态图相结合，提出了一种基于UML 状态图的类的测试用例自动生成方法。

语用层次仿真组件组合性质分析

针对语法和语义层次组合存在对仿真环境的匹配及组合结果实用性不强的问题,在语用组合与仿真语境研究的基础上,给出仿真语境空间形式化定义,提出一种基于语境空间匹配指数的静态语用组合性质分析方法。对扩展有限状态自动机进行分析,设计支持语境约束的仿真组件模型形式化描述,建立仿真组件模型与着色Petri网(CPN)之间的映射,并利用CPN Tools工具实现组合模型的动态语用可组合性质分析。应用结果表明,语用层次的仿真组件静态、动态组合性质分析,可为仿真组件发现、仿真建模优化、组合结果有效性判定等关键问题提供量化、直观的依据。

面向协议一致性测试的测试序列生成方法研究

考虑到协议一致性测试中基于扩展有限状态自动机（EFSM）模型的测试序列生成仍然是一个尚无理想方法解决的开放性问题，提出了一种面向协议一致性测试的基于EFSM模型的测试序列生成方法。此方法将EFSM模型转换成确定化的EFSM（DEFSM）模型，并在转换过程中对EFSM模型中的条件和操作冲突进行检测并加以消除，此外，通过测试序列生成附加模块的协助，可将变量及其条件判定从DEFSM模型中分离出来，使得处理后的DEFSM模型等同于有限状态自动机（FSM）模型，从而将EFSM的描述优势和基于FSM模型的测试序列生成优势进行有效的结合。理论和实验分析结果显示了此方法的有效性。

专用指令集处理器模型的研究

针对现有专用指令集处理器(ASIP)模型的不足和ASIP的特点,提出了一个新型的ASIP模型——xpMODEL.它以指令行为作为设计核心,引入指令行为有限状态机IB-EFSM建立指令操作的时序调度机制,通过原语操作完成行为中对处理器资源的调用,有效地对指令的流水化操作进行了建模.在对处理器资源的建模中,利用资源库描述处理器的部件、存储和连接,并通过抽象层和行为层的部件双层建模形式有效地支持了对ASIP中专用硬件和外围部件的描述.介绍了xpMODEL对一些复杂执行机制,如forwarding技术、动态调度技术、分支预测技术和中断技术建模的支持,说明了其建模能力相对于现有的ASIP模型的优势.

基于UML状态图的类测试用例实现的研究和设计

UML状态图能有效的表现系统的并发控制和类的嵌套,但用其实现的类测试用例复杂。研究了UML状态图和扩展有限状态机这两种方法在软件测试中状态转换的特点,利用扩展有限状态机状态转挟单一线索化的特点降低UML状态图在类测试用例生成中的复杂性。以一个坐标图形显示类的测试用例生成为例,详细讨论了结合扩展有限状态机状态转换特点的UML状态图在面向对象测试技术中的应用。

面向Web服务器端敏感路径的客户端扩展有限状态机测试生成

为对Web应用进行有效的测试,本文提出了一种面向Web应用服务器端敏感路径覆盖的客户端扩展有限状态机测试用例生成方法。针对Web应用客户端扩展有限状态机模型,以Web应用服务器端的敏感路径覆盖为目标,利用Memetic演化算法实现客户端扩展有限状态机模型的测试用例自动生成,对Web应用进行测试。同时,为解决由模型生成的抽象测试用例不可直接执行的问题,提出了一种基于Selenium的测试脚本自动构建方法,通过分析扩展有限状态机模型迁移的特征,利用谱聚类算法实现迁移聚类,依据映射规则将聚类之后的迁移映射为测试脚本,形成迁移脚本库,将抽象测试用例转换为可执行的测试用例。实验结果表明:基于Selenium的测试脚本自动构建能有效地将抽象测试用例转化为可执行的测试脚本;面向Web服务器端敏感路径的客户端扩展有限状态机测试用例生成方法能有效地实现Web服务器端敏感路径的覆盖,对服务器端的敏感路径进行测试。